변환 블록들의 효율적 코딩 및 디코딩 document_id A220623107196

블록 변환 기반 코딩( Block Transform - Based Coding ) 변환 코딩은 다수의 오디오, 이미지 및 비디오 압축 시스템들에서 사용되는 압축 기법이다. 압축되지 않은 디지털 이미지 및 비디오는 전형적으로 2차원(2D) 격자(grid)로서 배열된 이미지 또는 비디오 프레임 내의 위치들에서 화소(picture element)들 또는 색(color)들의 샘플들로서 표현되거나 캡처된다. 이것은 이미지 또는 비디오의 공간-도메인 표현(spatial-domain representation)으로 불린다. 예를 들면, 이미지들에 대한 전형적인 포맷은 격자로서 배열된 24 비트 색 화소 샘플들의 스트림으로 이루어진다. 각 샘플은, 특히, RGB, 또는 YIQ와 같은 색공간 내에서 격자 내의 픽셀 위치에서의 색 컴포넌트들을 나타내는 숫자이다. 다양한 이미지 및 비디오 시스템들이 샘플링의 여러 가지 상이한 색, 공간 및 시간 해상도(resolution)들을 사용할 수 있다. 유사하게, 디지털 오디오는 전형적으로 시간-샘플링된 오디오 신호 스트림으로서 표현된다. 예를 들면, 전형적인 오디오 포맷은 규칙적인 시간 간격으로 취해진 오디오 신호의 16 비트 진폭 샘플들의 스트림으로 이루어진다. 압축되지 않은 디지털 오디오, 이미지 및 비디오 신호들은 상당한 저장 및 전송 용량을 소비할 수 있다. 변환 코딩은 신호의 공간-도메인 표현을 주파수-도메인(또는 다른 유사한 변환 도메인) 표현으로 변환하고, 그 후 변환-도메인 표현의 어떤 일반적으로 덜 인지되는 주파수 컴포넌트들의 해상도를 감소시킴으로써 디지털 오디오, 이미지 및 비디오의 크기를 감소시킨다. 이것은 일반적으로 공간 도메인에서의 이미지들 또는 비디오의, 또는 시간 도메인에서의 오디오의 색 또는 공간 해상도를 감소시키는 것에 비하여 디지털 신호의 열화가 훨씬 덜 인지되게 한다. 보다 구체적으로, 도 1에 도시된 전형적인 블록 변환 기반 코덱(block transform-based codec)(100)은 압축되지 않은 신호 이미지의 픽셀들을 고정 크기의 2차원 블록들(Xl, ... Xn)로 분할하고, 각 블록은 어쩌면 다른 블록들과 중첩(overlap)한다. 공간-주파수 분석을 하지 않는 선형 변환(120-121)이 각 블록에 적용되고, 이는 블록 내의 간격을 둔 샘플들(spaced samples)을 일반적으로 블록 간격에 걸쳐서 대응하는 주파수 대역들에서 디지털 신호의 강도를 나타내는 주파수(또는 변환) 계수들의 세트로 변환한다. 압축을 위하여, 변환 계수들은 선택적으로 양자화(130)되고(즉, 계수 값들의 최하위 비트들을 버리거나(drop) 또는 보다 높은 해상도 숫자 세트 내의 값들을 보다 낮은 해상도로 매핑하는 것 등에 의해 해상도가 저하되고), 또한 압축된 데이터 스트림으로 엔트로피(entropy) 또는 가변 길이(variable-length) 코딩된다(130). 디코딩 시에, 변환 계수들은 역으로 변환(170-171)하여 원본 색/공간 샘플링된 이미지/비디오 신호를 거의 재구성할 것이다(재구성된 블록들 ). 블록 변환(120-121)은 크기 N의 벡터 x에 대한 수학적 연산으로 정의될 수 있다. 대체로, 그 연산은 선형 곱(linear multiplication)으로, 변형 도메인 출력 y = Mx를 생성하고, 여기서 M은 변환 행렬이다. 입력 데이터가 임의로 길 경우, 그것은 N 크기의 벡터들로 분할(segment)되고 각 세그먼트에 블록 변환이 적용된다. 데이터 압축을 위하여, 가역(reversible) 블록 변환들이 선택된다. 즉, 행렬 M은 가역적(invertible)이다. (예컨대, 이미지 및 비디오에 대한) 다중 차원(multiple dimensions)에서, 블록 변환들은 전형적으로 분리 가능한 연산들로서 구현된다. 행렬 곱은 데이터의 각 차원(즉, 행들과 열들 모두)을 따라서 개별적으로 적용된다. 압축을 위하여, 변환 계수들(벡터 y의 컴포넌트들)은 선택적으로 양자화되고(즉, 계수 값들의 최하위 비트들을 버리거나(drop) 또는 보다 높은 해상도 숫자 세트 내의 값들을 보다 낮은 해상도로 매핑하는 것 등에 의해 해상도가 저하되고), 또한 압축된 데이터 스트림으로 엔트로피 또는 가변 길이 코딩된다. 디코더(150)에서의 디코딩 시에는, 도 1에 도시된 바와 같이, 디코더(150) 측에서 이들 연산들의 역(inverse)(역양자화(dequantization)/엔트로피 디코딩(160) 및 역 블록 변환(inverse block transform)(170-171))이 적용된다. 데이터를 재구성하는 동안, 역행렬 M-1(역변환(170-171))이 승수(multiplier)로서 변환 도메인 데이터에 적용된다. 변환 도메인 데이터에 적용될 때, 역변환은 원본 시간-도메인 또는 공간-도메인 디지털 미디어를 거의 재구성한다. 다수의 블록 변환-기반 코딩 응용들에서, 변환은 양자화 팩터(quantization factor)에 따라서 손실 및 무손실 압축 모두를 지원하도록 가역적인 것이 바람직하다. 예를 들어 양자화가 없는 경우에(일반적으로 1의 양자화 팩터로서 표현됨), 가역 변환을 이용하는 코덱은 디코딩 시에 입력 데이터를 정확히 재생할 수 있다. 그러나, 이들 응용에서 가역성의 필요 조건은 코덱이 설계될 수 있는 변환들의 선택을 제한한다. 그 중에서도 특히, MPEG 및 윈도 미디어와 같은, 다수의 이미지 및 비디오 압축 시스템들은 이산 코사인 변환(DCT : Discrete Cosine Transform)을 기반으로 한 변환들을 이용한다. DCT는 근최적의(near-optimal) 데이터 압축으로 귀결되는 우수한 에너지 집중(energy compaction) 특성들을 갖는 것으로 알려져 있다. 이들 압축 시스템들에서, 역(inverse) DCT(IDCT)는 개개의 이미지 블록들을 재구성하기 위한 압축 시스템의 인코더 및 디코더 양쪽 모두에서의 재구성 루프(recontruction loops)에서 이용된다. 광역 변환 계수들의 엔트로피 코딩 넓은 동적 범위(wide dynamic range) 입력 데이터는 이미지를 인코딩하는 처리 중에 생성된 한층 더 넓은 동적 범위 변환 계수들을 초래한다. 예를 들면, N×N DCT 연산에 의해 생성된 변환 계수들은 원본 데이터의 동적 범위에 N을 곱한 것보다 더 큰 동적 범위를 갖는다. (저손실 또는 무손실 압축을 실현하는 데 이용되는) 작은 또는 1(unity) 양자화 팩터들의 경우, 양자화 변환 계수들의 범위도 크다. 통계적으로, 이들 계수들은 도 2 및 3에 도시된 바와 같은 라플라스 분포를 갖는다. 도 2는 넓은 동적 범위 계수들에 대한 라플라스 분포를 보여준다. 도 3은 전형적인 좁은 동적 범위 계수들에 대한 라플라스 분포를 보여준다. 종래의 변환 코딩은 입력 데이터(전형적으로 8 비트)의 작은 동적 범위, 및 비교적 큰 양자화기들(예컨대 4 이상의 수치 값들)에 대하여 조정(tune)되어 있다. 따라서 도 3은 그러한 종래의 변환 코딩에서의 변환 계수들의 분포를 나타낸다. 또한, 그러한 종래의 변환 코딩에서 이용되는 엔트로피 코딩은 런-레벨(run-level) 인코딩의 변형(variant)일 수 있고, 여기서 제로의 연속(a succession of zeros)은 제로가 아닌 기호(non-zero symbol)와 함께 인코딩된다. 이것은 제로의 런들(runs of zeros)(높은 확률로 나타남)을 표현함은 물론, 기호간 상관 관계(inter-symbol correlations)를 캡처하는 효과적인 수단일 수 있다. 한편, 종래의 변환 코딩은 도 2에 도시된 것과 같은 넓은 동적 범위 분포들을 압축하는 데 덜 적합하다. 기호들은 어떤 다른 값보다 더 높은 확률로 제로이지만(즉, 제로에서 분포 최고치), 넓은 동적 범위 분포에 대하여 정확히 제로인 계수의 확률은 아주 작다. 따라서, 제로들은 빈번히 발생하지 않고, 후속되는 제로가 아닌 계수들 사이의 제로의 수에 기초하는 런 길이 엔트로피 코딩 기법들은 넓은 동적 범위 입력 데이터에 대하여 매우 비효율적이다. 넓은 동적 범위 분포는 또한 좁은 범위 분포와 비교하여 증가된 알파벳의 기호들을 갖는다. 이 증가된 기호 알파벳으로 인해, 기호들을 인코딩하는 데 이용되는 엔트로피 테이블(들)은 클 필요가 있을 것이다. 그렇지 않다면, 기호들 중 다수가 결국 이스케이프 코딩될(escape coded) 것이고, 이는 비효율적이다. 보다 큰 테이블들은 보다 많은 메모리를 필요로 하고 또한 보다 높은 복잡도를 초래할 수 있다. 따라서 종래의 변환 코딩은 변통성(versatility)이 부족하다 - 좁은 동적 범위 분포를 갖는 입력 데이터에 대해서는 잘 동작하지만, 넓은 동적 범위 분포에서는 잘 동작하지 않는다. 그러나, 좁은 범위 데이터에서, 양자화된 변환 계수들의 효율적인 엔트로피 코딩을 찾는 것은 중요한 프로세스이다. 이 단계에서 달성될 수 있는 임의의 성능 이득들(압축 효율 및 인코딩/디코딩 속도의 모든 면에서의 이득들)은 전체 품질 이득들로 변환된다. 상이한 엔트로피 인코딩 방식들은, 그 방식들이 컨텍스트 정보(contextual information)의 사용, (산술 코딩과 같은) 보다 높은 압축, (허프만(Huffman) 코딩 기법에서 발견되는 것과 같은) 보다 낮은 계산 필요 조건, 및 간결한 코드 테이블들의 세트를 이용하여 인코더/디코더 메모리 부담을 최소화하는 것과 같은 개별 효율성 조건들을 성공적으로 이용하는 능력에 의해 특징지어진다. 이들 특징들 모두를 만족시키지 않는 종래의 엔트로피 인코딩 방법들은 변환 계수들을 인코딩하는 충분한 효율성을 나타내지 않는다.