적응적 계수 스캔 순서 document_id A220623010107

본 발명은 전반적으로 블록 변환-기반 디지털 미디어(block transform-based digital media)(예컨대, 영상 및 이미지) 압축에 관한 것이다. 블록 변환 기반 코딩의 개요 변환 코딩은 많은 음성, 이미지 및 영상 압축 시스템에 이용되는 압축 기법이다. 비압축 디지털 이미지 및 영상은 일반적으로 2디멘션(2D) 그리드에 배열되는 이미지 또는 영상 프레임에서의 위치에서 픽쳐 요소 또는 컬러의 샘플들로 표현되거나 캡쳐된다. 이것은 이러한 이미지 또는 영상의 공간 도메인 표현으로 지칭된다. 예컨대, 이미지에 대한 전형적인 포맷은 하나의 그리드로 배열되는 24-비트 컬러 픽쳐 요소 샘플들의 스트림으로 구성된다. 각각의 샘플은 컬러 공간 중 RGB 또는 YIQ와 같은 공간내의 그리드에서의 픽셀 위치에서 컬러 성분을 표시하는 번호이다. 다양한 이미지 및 영상 시스템은 샘플링의 여러 상이한 컬러, 공간 및 시간 해상도를 이용할 수 있다. 이와 유사하게, 디지털 음성은 일반적으로 시간-샘플링 음성 신호 스트림으로 표현된다. 예컨대, 전형적인 음성 포맷은 정규 시간 간격으로 취해진 음성 신호의 16-비트 크기 샘플들의 스트림으로 구성된다. 비압축 디지털 음성, 이미지 및 영상 신호는 상당한 저장 및 전송 용량을 소모할 수 있다. 변환 코딩은 신호의 공간-도메인 표현을 주파수-도메인(또는 기타 유사 변환 도메인) 표현으로 변환하여 디지털 음성, 이미지 및 영상의 사이즈를 줄이고, 일반적으로 이러한 변환 도메인 표현의 약간 덜 인지할 수 있는 주파수 성분의 해상도를 줄인다. 이것은 통상 공간 도메인에서의 이미지 혹은 영상, 또는 시간 도메인에서의 음성의 컬러 또는 공간 해상도를 줄이는 것에 비해 디지털 신호에서의 훨씬 덜 인지할 수 있는 저하를 발생시킨다. 보다 구체적으로, 도 1에 도시되어 있는 전형적인 블록 변환 기반 코덱(100)은 비압축 디지털 이미지의 픽셀을 고정 사이즈의 2디멘션 블록(X1, ... Xn)으로 분할하는데, 각각의 블록은 다른 블록과 오버래핑할 수 있다. 공간-주파수 분석을 수행하는 선형 변환(120 - 121)은 각각의 블록에 적용되어, 블록내의 공간 샘플을 한 세트의 주파수(또는 변환) 계수로 변환하는데, 이 계수는 일반적으로 블록 간격에서 대응 주파수 대역에서의 디지털 신호의 강도를 표시한다. 압축에 있어서, 변환 계수는 선택적으로 양자화(130)될 수 있고(즉, 계수 값들의 최소 중요 비트들을 드롭하거나 또는 이와 달리 고 해상도 번호 세트에서의 값들을 저 해상도로 매핑하는 것과 같이 해상도가 줄어들 수 있고), 또한 압축 데이터 스트림으로 엔트로피 또는 가변-길이 코드화(130)될 수 있다. 디코딩시에, 변환 계수는 원래의 컬러/공간 샘플링 이미지/영상 신호를 거의 재생(재생 블록 )하도록 역변환(170 - 171)할 것이다. 블록 변환(120 - 121)은 사이즈 N의 벡터 x에 대한 수학 연산으로 규정될 수 있다. 가장 흔하게, 이 연산은 1차 곱셈으로 M이 변환 메트릭스인 변환 도메인 출력 y = Mx를 생성한다. 입력 데이터가 임의로 긴 경우에, 이 입력 데이터는 N 사이즈 벡터로 세그먼트되고, 블록 변환은 각각의 세그먼트에 적용된다. 데이터 압축을 위해, 가역 블록 변환이 선택된다. 달리 말하면, 메트릭스 M은 가역적이다. (예를 들어, 이미지 및 영상에 대한) 멀티디멘션에 있어서, 블록 변환은 일반적으로 가분 연산으로 구현된다. 메트릭스 곱셈은 데이터의 각 디멘션(즉, 행 및 열)을 따라 가분적으로 적용된다. 압축에 있어서, 변환 계수(벡터 y의 성분)는 선택적으로 양자화될 수 있고(즉, 계수 값들의 최소 중요 비트들을 드롭하거나 또는 이와 달리 고 해상도 번호 세트에서의 값들을 저 해상도로 매핑하는 것과 같이 해상도가 줄어들 수 있고), 또한 압축 데이터 스트림으로 엔트로피 또는 가변-길이 코드화될 수 있다. 디코더(150)에서의 디코딩시에, 이러한 연산의 역과정(양자화 해제/엔트로피디코딩(160) 및 블록 역변환(170 - 171))은 도 1에 도시된 바와 같이 디코더(150)측에서 적용된다. 데이터를 재생하는 동안에, 역 메트릭스M-1(역변환(170 - 171))은 변환 도메인 데이터에 대해 승수로 적용된다. 변환 도메인 데이터에 적용되는 경우에, 역변환은 원래의 시간-도메인 또는 공간-도메인 디지털 미디어를 거의 재생한다. 이용되는 변환은 간단한 DPCM 타입 예측기/수정기일 수 있거나, 또는 웨이브렛 혹은 DCT(이산 코사인 변환)와 같이 더 복잡한 구조일 수 있다. 통상 이용되는 표준 JPEG/MPEG2/MPEG4, JPEG2000 및 윈도우 미디어 비디오(WMV)는 제각기 DCT, 웨이브렛 및 정수화-DCT를 이용한다. 추가로, WMV는 블록 내부 및 프레임 내부에 대해 영상 및 레이트-일그러짐 이점을 제공하는 랩 평활화 오페레이터(lapped smoothing operator)를 이용한다. 블록 변환에 관련하여 랩 평활화 오퍼레이터는 1992년 메사추세츠주 보스턴 아텍 하우스에서 발간한 H. S. Malvar의 "Signal Processing with Lapped Transforms"에 개시되어 있는 타입의 랩 변환을 모방하려 한다. 계수 스캔 패턴 JPEG, MPEG2, MPEG4 및 WMV를 포함하는 많은 블록 변환-기반 코덱은 특정한 블록에 대응하는 양자화 계수를 인코딩하기 위해 런 렝스 코딩 기법을 이용한다(예를 들어, 1993년 뉴욕주 반 노스트란드 라인홀드에서 발간한 W. B. Pennebaker 및 J. L. Mitchell의 "JPEG : Still Image Compression Standard"를 참고하기 바란다). 런 렝스 코딩은 사전설정된 패턴에 따라 양자화 변환 계수의 블록을 스캔하여 진행된다. 이와 같은 일례는 도 3에 도시되어 있는 연속 "지그재그" 스캔 패턴이다. 유사한 연속 지그재그 스캔 패턴이 JPEG 및 MPEG2/4에 광범위하게 이용되지만, 연속적이기 위해 스캔 패턴에 고유하게 요구되는 것은 없다. 런 렝스 코딩 기법은 하위 변환(underlying transform)의 통계를 이용한다. 일반적으로, 큰 계수는 (종래에 좌상 코너에 표시되는) "DC"값에서 발생하고, 더 드물고 작은 계수는 DC로부터 먼 거리에서 발생한다. 예컨대, 이점은 양자화 후에 제로 값을 갖기 위해 변환 블록의 변환 계수 대부분에서 공통적이다. 많은 스캔 패턴은 제로가 아닌 값을 더 가지기 쉬운 계수들에 높은 우선 순위를 제공한다. 달리 말하면, 이와 같은 계수들은 스캔 패턴에서 더 일찍 스캔된다. 이런 식으로, 제로가 아닌 계수들은 함께 묶이기 쉽고, 제로 값 계수들의 하나 이상의 긴 그룹이 뒤따른다. 특히, 이것은 더 효율적인 런/레벨/라스트 코딩을 가능하게 하지만, 다른 유형의 엔트로피 코딩 또한 재순서화시에 이점을 제공한다. 블록 디멘션, 및 이미지가 인터레이스 또는 순차 포맷에 존재하는지에 따르는 것과 같이 제한된 세트의 사전설정 또는 정적인 스캔 패턴들 중에서 선택하는 영상 압축 시스템은 "Scan Patterns For Interlaced Video Content"란 명칭으로 2004년 11월 15일 출원된 Lin 등의 미국 특허 출원 제 10/989,844호와, "Scan Patterns For Progerssive Video Content"란 명칭으로 2004년 11월 15일 출원된 Liang 등의 미국 특허 출원 제 10/989,594호에 개시되어 있다.