KR101036731B1

KR101036731B1 - 손실 및 무손실 2차원 데이터 압축을 위한 가역 변환

Info

Publication number: KR101036731B1
Application number: KR1020050107656A
Authority: KR
Inventors: 스리드하르 스리니바산
Original assignee: 마이크로소프트 코포레이션
Priority date: 2004-12-17
Filing date: 2005-11-10
Publication date: 2011-05-24
Also published as: BRPI0506084B1; RU2413983C2; EP1672517A2; RU2005135847A; AU2005237142A1; BRPI0506084A8; BRPI0506084A; CA2526762A1; KR20060069254A; CN1791222B; US20060133683A1; EP1672517A3; JP2006197572A; MXPA05012403A; AU2005237142B2; JP4874642B2; EP1672517B1; US7471850B2; CN1791222A; CA2526762C

Abstract

2D 변환 및 그 역은 계산의 복잡성을 감소(즉, 중요한 다수의 연산을 감소)시키기 위해 구성된 리프팅 단계들의 시퀀스로서 구현된다. 이러한 변환 쌍은 DCT와 유사한 에너지 압축 속성들을 가지며, 또한 무손실이고 스케일-프리(scale-free)이다. 2D 데이터 블럭의 열들과 행들에 분리가능하게 적용되는 1D DCT 변환들로서 구현된 분리가능한 DCT 변환과 비교해서, 변환들의 연산들은 2x2 하다마드 변환, 및 리프팅 회전들을 포함하는 2x2 변환들을 포함하는 기본 변환들의 캐스케이드로 재구성된다. 이러한 기본 변환들은 리프팅 연산의 시퀀스로서 구현된다.

리프팅 연산, 스케일-프리, 역변환, 압축, 하다마드 변환

Description

손실 및 무손실 2차원 데이터 압축을 위한 가역 변환{REVERSIBLE TRANSFORM FOR LOSSY AND LOSSLESS 2-D DATA COMPRESSION}

도 1은 종래 기술에서의, 종래의 블럭 변환 기반 코덱의 블럭도.

도 2는 종래 기술에서의, 2단계로 구현되는 2D 4x4 DCT의 블럭도.

도 3은 종래 기술에서의, 1D 4x4 DCT의 신호 흐름 그래프.

도 4는 종래 기술에서의, 리프팅을 사용하는 정규화된 2-포인트 하다마드 변환의 신호 흐름 그래프.

도 5는 종래 기술에서의, 보통의 2-포인트 하다마드 변환의 신호 흐름 그래프.

도 6은 개선된 가역 2D 변환에 기초한 인코더의 흐름도.

도 7은 개선된 가역 2D 변환에 기초한 디코더의 흐름도.

도 8은 가역 2x2 하다마드 변환의 정규화된 리프팅 기반 구현의 신호 흐름 그래프.

도 9는 도 8의 정규화된 가역 2x2 하다마드 변환을 실현하기 위한 C 프로그래밍 언어에서의 프로그램 목록.

도 10은 도 8의 정규화된 가역 2x2 하다마드 변환의 역에 대한 신호 흐름 그래프.

도 11은

변환의 정규화된 리프팅 기반 구현의 신호 흐름 그래프.

도 12는 도 11의 정규화된

변환을 실현하기 위한 C 프로그래밍 언어의 프로그램 목록.

도 13은 도 11의

변환의 역에 대한 정규화된 리프팅 기반 버전의 신호 흐름 그래프.

도 14는

변환의 정규화된 리프팅 기반 구현의 신호 흐름 그래프.

도 15는 도 14의 정규화된

변환을 실현하기 위한 C 프로그래밍 언어에서의 프로그램 목록.

도 16은 도 14의

변환의 역의 정규화된 리프팅 기반 버전의 신호 흐름 그래프.

도 17은 변환 및 역변환 연산들에 대한 본원 설명에서의 2x2 데이터의 순서화를 도시하는 도면.

도 18은 4x4 데이터 입력의, 행과 열에 각각 적용된 1D 수직 DCT 및 1D 수평 DCT로서 분리가능하게 구현된 2D DCT를 설명하는 신호 흐름 그래프.

도 19는 2단계의 수평 및 수직 변환 연산들을 인터리브함으로써 구현되는 가역의, 스케일-프리 2D 변환을 도시하는 신호 흐름 그래프.

도 20은, 도 8의 2x2 하다마드 변환이 도 6의 인코더에서의 개선된, 가역 2D 변환의 구현의 제1 스테이지에 적용되는 4x4 데이터 블럭의 포인트들을 도시하는 도면.

도 21은 도 8의 2x2 하다마드 변환, 도 11의

변환, 및 도 14의

변환이 도 6의 인코더에서의 개선된, 가역 2D 변환의 구현의 제2 스테이지에 적용되는 4x4 데이터 블럭의 포인트들을 도시하는 도면.

도 22는 도 8의 2x2 하다마드 변환, 도 11의

변환, 및 도 14의

변환이 도 7의 디코더에서의 개선된, 가역 2D 변환의 구현의 제1 스테이지에 적용되는 4x4 변환 계수 블럭의 포인트들을 도시하는 도면.

도 23은 도 6의 인코더 및 도 7의 디코더에서 포워드 및 역 2D 변환을 위한 변환 계수들의 순서화를 도시하는 도면.

도 24는 도 6 및 7의 개선된 공간-도메인 래핑(lapping) 변환을 갖는 블럭 변환 기반 코덱을 구현하기 위한 적합한 컴퓨팅 환경의 블럭도.

도 25는 도 11 및 14에 도시된 가역 2x2 변환들의 정규화된 리프팅 기반 구현을 위한 구조의 신호 흐름 그래프.

<도면의 주요 부분에 대한 부호의 설명>

120: 포워드 변환

130: 양자화/엔트로피 코드

110: 인코더

150: 디코더

170: 역변환

[참고문헌 1] N. Ahmed, T. Natarajan, and K.R. Rao, "Discrete Cosine Transform," IEEE Transactions on Computers, C-23(January 1974), pp.90-93

[참고문헌 2] "IEEE Standard Specificaion for the Implenetations of 8x8 Inverse Discrete Cosine Transform," IEEE Std. 1180-1990, December 6, 1990

본 발명은 일반적으로 블럭 변환 기반 디지털 미디어(예를 들어, 비디오 및 이미지) 압축에 관한 것이다.

블럭 변환 기반 코딩

변환 코딩은 많은 오디오, 이미지 및 비디오 압축 시스템들에서 사용되는 압축 기술이다. 압축되지 않은 디지털 이미지 및 비디오는 전형적으로 2차원(2D) 그리드에 배열된 이미지 또는 비디오 프레임의 위치들에서 화소 또는 컬러의 샘플들로서 표현 또는 포착된다. 이것은 이미지 또는 비디오의 공간 도메인 표현으로 지칭된다. 예를 들어, 이미지들에 대한 전형적인 포맷은 그리드로 배열된 24비트 컬러 화소 샘플들의 스트림으로 이루어진다. 각 샘플은 특히 RGB, 또는 YIQ 등의 컬러 공간 내에 있는 그리드에서 화소 위치의 컬러 성분들을 나타내는 수이다. 각종 이미지 및 비디오 시스템들은 각종 상이한 색, 샘플링의 공간 및 시간 해상도를 사용할 수 있다. 마찬가지로, 디지털 오디오는 전형적으로 시간-샘플링된 오디오 신 호 스트림으로서 표현된다. 예를 들어, 전형적인 오디오 포맷은 일정한 시간 간격에 취해진 오디오 신호의 16비트 진폭 샘플들의 스트림으로 이루어진다.

압축되지 않은 디지털 오디오, 이미지 및 비디오 신호들은 상당한 저장 및 전송 용량을 소비할 수 있다. 변환 코딩은 신호의 공간 도메인 표현을 주파수 도메인(또는 다른 변환 도메인) 표현으로 변환함으로써 디지털 오디오, 이미지 및 비디오의 사이즈를 감소시킨 후, 변환 도메인 표현의 어느 정도 일반적으로 덜 인식가능한 주파수 성분들의 해상도를 감소시킨다. 이에 의해, 일반적으로 공간 도메인의 이미지나 비디오, 또는 시간 도메인의 오디오의 컬러 또는 공간 해상도를 감소시키는 것에 비해 디지털 신호의 열화가 훨씬 덜 인식가능하게 된다.

특히, 도 1에 도시된 전형적인 블럭 변환-기반 코덱(100)은 압축되지 않은 디지털 이미지의 화소들을 고정된 사이즈의 2차원 블럭들(X₁, ... X_n)로 분할하는데, 각 블럭은 다른 블럭들과 중첩이 가능하다. 공간 주파수 분석을 행하는 선형 변환(120-121)은 각 블럭에 적용되는데, 이것은 블럭 내의 이격된 샘플들을, 블럭 간격에 대한 주파수 대역들에 대응하여 디지털 신호의 세기를 일반적으로 나타내는 주파수(또는 변환) 계수들의 세트로 변환한다. 압축을 위해, 변환 계수들은 선택적으로 양자화(130)될 수 있고(예를 들어, 계수 값들의 최하위 비트들을 버리거나 아니면 고 해상도 수 세트의 값들을 저 해상도에 매핑하는 등에 의해 해상도를 감소시킴), 또한 엔트로피 또는 가변 길이가 압축된 데이터 스트림으로 코딩된다(130). 디코딩시, 변환 계수들은 역변환되어(170-171) 원래 컬러/공간 샘플 링된 이미지/비디오 신호(재구성된 블럭들

)를 거의 재구성할 것이다.

블럭 변환(120-121)은 크기 N의 벡터 x에 대한 수학적 연산으로서 정의될 수 있다. 대부분, 연산은 선형 곱셈으로, 변환 도메인 출력 y=Mx(M은 변환 매트릭스)를 생성한다. 입력 데이터가 임의의 길이이면, N 크기의 벡터들로 분할되고 각 세그먼트에 블럭 변환이 행해진다. 데이터 압축을 위해, 가역 블럭 변환들이 선택된다. 즉, 매트릭스 M은 비가역이다. 다차원에서(예를 들어, 이미지 및 비디오에 대해), 블럭 변환들은 일반적으로 분리가능한 연산들로서 구현된다. 매트릭스 곱셈은 데이터의 각 디멘젼(즉, 행열 모두)을 따라 분리가능하게 적용된다.

압축을 위해, 변환 계수들(벡터 y의 성분들)은 선택적으로 양자화될 수 있고(예를 들어, 계수 값들의 최하위 비트들을 버리거나 아니면 고 해상도 수 세트의 값들을 저 해상도에 매핑하는 등에 의해 해상도를 감소시킴), 또한 엔트로피 또는 가변 길이가 압축된 데이터 스트림으로 코딩된다.

디코더(150)에서의 디코딩시, 도 1에 도시된 바와 같이, 상기 연산들의 역(양자화 해제/엔트로피 디코딩(160) 및 역 블럭 변환(170-171))이 디코더(150) 측에 행해진다. 데이터 재구성시, 역 매트릭스 M^-1(역변환(170-171))이 체배기로서 변환 도메인 데이터에 적용된다. 변환 도메인 데이터에 적용되는 경우, 역변환은 원래 시간-도메인 또는 공간-도메인 디지털 미디어를 거의 재구성한다.

많은 블럭-변환 기반 코딩 응용들에서, 양자화 인수에 따라 손실 및 무손실 압축 모두를 지원하기 위해 변환이 가역인 것이 바람직하다. 예를 들어 양자화가 없으면(일반적으로 양자화 인수 1로 표현됨), 가역 변환을 사용하는 코덱은 디코딩시 입력 데이터를 정확하게 재생할 수 있다. 그러나, 이러한 응용들의 가역성의 요건은 코덱이 설계될 수 있을 때의 변환의 선택을 제약한다.

특히 MPEG 및 윈도우 미디어 등의 많은 이미지 및 비디오 압축 시스템들은 DCT(Discrete Cosine Transform)에 기초한 변환을 이용한다. DCT는 근접-최적 데이터 압축을 야기하는 적합한 에너지 압축 속성들을 갖는 것으로 알려져 있다. 이러한 압축 시스템들에서, 각각의 이미지 블럭들을 재구성하기 위한 압축 시스템의 인코더 및 디코더 모두의 재구성 루프에서 역 DCT(IDCT)가 사용된다. DCT는 참고문헌 1에 설명되어 있다. 예시적인 IDCT의 구현은 참고문헌 2에 설명되어 있다.

가역 2D 데이터 압축기를 구현하는데 사용되는 종래의 데이터 변환들은 일반적으로 이하의 주요 단점들 중 하나 이상을 겪고 있다.

1. 복합 엔트로피 코딩 방식을 요하는, 변환 계수들 사이의 비동등 표준;

2. DCT 등의 최적 변환들에 대한 불충분한 근사값들; 및

3. 고 계산 복잡성.

종래의 2D 변환 구현

데이터의 행들에 1D 변환을 수행하고 이어서 데이터의 열들에 1D 변환을 수행함으로써(아니면 그 반대), 분리가능한 2D 변환이 일반적으로 구현된다. A.K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, 1989 참조. 매트릭스 표기에서, T는 변환 매트릭스를 나타내고, X는 2D 데이터라고 하자. T를 갖는 분리가능한 2D 변환은 이하의 수학식 1의 Y로 정의된다.

사실상, 행-방식 및 열-방식 변환들은 별개일 수 있다. 예를 들어, 데이터 매트릭스는 정사각이 아닐 수 있고(예를 들어 4x8 사이즈), 또는 행-방식 및 열-방식 변환들은 각각 DCT 및 DST(Discrete sine transform)일 수 있다. 이 경우, 전후 체배기들은 상이하고(예를 들어, T₁ 및 T₂) 변환 Y는 수학식 2로 주어진다.

예를 들어, 도 2는 2개의 스테이지로 구현된 2D 4x4 DCT를 도시한다. 제1 스테이지에서, 데이터 매트릭스의 열들은 4 포인트 1D DCT를 사용하여 변환된다. 제2 스테이지에서 4포인트 1D DCT들은 열들을 따라 적용된다. 무한 계산 정확성에 따라, 이 순서는 출력의 변화 없이 스위칭될 수 있다.

4 포인트 1D DCT는 도 3에 도시된 신호 흐름 그래프에 도시된 바와 같이, 4 입력 데이터 값들에 일련의 곱셈 및 덧셈 연산들로서 구현될 수 있다. 이 도면에서의 값들 c 및 s는 각각 π/8의 코사인 및 사인이다. 분리가능한 변환 접근법은 손실 코덱에서도 잘 동작한다. 무손실 코덱들은 실현하기가 더 어렵다. 단위 양자화에 의해서도, 분리가능한 역 DCT 즉 IDCT와 관련하여 상술된 분리가능한 2D DCT는 원래 입력에 정확히 일치하는 비트를 생성하는 것을 보장하지 않는다. 이것은 도 3의 제수들이 인코더와 디코더 사이에서 버려지지 않을 수 있는 라운딩 에러(rounding error)들을 발생시키기 때문이다.

리프팅

블럭 변환 기반 코덱으로 무손실 압축을 달성하기 위해, 상기 4x4 2D DCT를 무손실 변환으로 대체할 필요가 있다. 각 1D 변환이 무손실 또는 가역인 경우에만 분리가능한 변환이 사용될 수 있다. 가역 1D 변환들에 대해 다수의 선택이 존재하지만, "리프팅"에 기초한 선택들이 지금까지 가장 바람직하다. 리프팅은 연속적인 "전단(shears)"을 사용하여 매트릭스-벡터 곱셈을 행하는 프로세스이다. 전단은 식별 매트릭스 플러스 하나의 논제로 비대각 원소(non-zero off-diagonal element)인 매트릭스와 피연산자 벡터의 곱으로서 정의된다. 하나 이상의 벡터 계수들의 부호 역전은 일반성이 소실되지 않고, 이 프로세스 동안 어디에서나 발생할 수 있다.

리프팅은 과거의 사다리꼴 또는 격자 필터 구조들을 통해 구현되었다. 리프팅 또는 연속 전단 기반 기술들은 그래픽에서 사용되었다. A. Tanaka, M. Kameyama, S. kazama, and O.Watanabe, "A rotation method for raster image using skew transformation," Proc IEEE Conf on Computer Vision and Pattern Recognition, pages 272-277, June 1986; 및 A.W. Paeth, "A fast algorithm for general raster rotation," Proceedings of Graphics Interface '86, pages 77-81, May 1986을 참조하라. 사실, 가우스 조르단 소거법(Gauss-Jordan elimination)이 리프팅의 징후라고 주장될 수 있다.

하나의 간단한 2 포인트 연산은 하다마드 변환이고, 변환 매트릭스

로 주어진다. 리프팅 기반(가역) 1D 하다마드 변환을 구현하기 위해 2가지 접근법이 흔히 사용된다. 하나는 도 4에 도시된 바와 같이, 리프팅 단계에서 정규화된 또는 스케일-프리 하다마드 변환을 구현하는 것이다. 제2 접근법은 도 5에 도시된 바와 같이, 2개의 변환 계수들 사이에서 척도를 다르게 하는 것이다.

리프팅이 갖는 문제점들

리프팅은 문제점이 존재한다. 우선 도 4에 도시된 하다마드 변환에서는, 2개의 변환 계수들이 정규화된다. 이것은 4 또는 8 포인트 DCT 등의 멀티-스테이지 변환을 실현하기 위해 바람직하다. 그러나, 이러한 구현은 2가지 중요한 문제점을 가지는데, 우선, 각각의 2 포인트 하다마드 변환은 3개의 중요한(즉, 계산적으로 고가의) 리프팅 단계를 요구하고, 둘째로, 리프팅 단계에서의 라운딩 에러들에 의해 로우 통과 에너지가 고 주파수 기간으로 "누설"되어 압축 효율이 감소된다. 이러한 제1 접근법에서, 근사값

및

를 사용하여 AC 기반 함수가 [0.75 - 0.7188]이 된다. 요구되는 [0.7071 0.7071]과의 불일치가 과도하게 큰 것 같지 않지만, 진폭 64의 DC 신호는 2 단위의 AC 응답을 생성하고, 이는 인코드하기에 고가인(expensive-to-encode) 고주파 대역으로 누설된다.

제2 접근법(도 5)은 보통의 리프팅 단계이다. 그러나, 로우 통과 기간은

의 인수만큼 확대되는 반면, 하이 통과 기간은 1/

만큼 축소된다(또는 그 반대). 2개의 계수들의 해상도는 1비트만큼 다르다. 2개의 디멘젼에서, 하이-하이 기간은 로우-로우 기간에 비해 2비트 만큼 해상도가 작다. 캐스케이드된 변환 스테이지들은 단지 불일치를 증가시킨다. 계수들의 범위가 다르기 때문에 엔트로피 코딩은 구현하기 어렵다.

요약하면, 리프팅 기반 무손실 변환이 갖는 문제점은 다음과 같다:

1. 보다 복잡한 엔트로피 코딩 메카니즘을 위해 행하는, 변환 계수들 사이의 가능한 비동등 스케일링(scaling).

2. DC의 AC 대역으로의 누설과 같은 바람직하지 않은 영향을 일으킬 수 있는 원하는 변환 기반 함수들에 대한 불충분한 근사값들.

3. 원하는 변환을 잘 근사화시키기 위해 리프팅 기반 구현이 설계되는 경우에 특히, 잠재적으로 높은 계산 복잡성.

디지털 미디어 인코더/디코더 시스템은 상기 문제점들 및 종래 변환의 단점을 다루는 본원에 설명된 여러가지 구현들을 갖는 분리가능한 2D 블럭 변환에 기초한다. 특히, 분리가능한 2D 변환과 그 역의 쌍에 대한 기술된 구현은 계산 복잡성을 감소시키기 위해(예를 들어, 중요한 다수의 동작들을 감소) 구성된 일련의 리프팅 단계들을 갖는다. 이러한 변환 쌍은 DCT와 유사한 에너지 압축 속성들을 갖고, 또한 무손실이고 스케일-프리이다. "무손실"이라는 용어는, 양자화가 없다고 가정 하고, 변환에 입력된 원래 정수가 역 변환에 의해 정수 변환 계수들로부터 에러 없이 복구될 수 있다는 것을 의미한다. "스케일-프리"라는 것은 변환 쌍들의 기초 함수들이 동등하게 스케일링된다는 것을 나타내며, 또한 결과로서의 변환 매트릭스가 직교라는 것을 의미한다.

이러한 변환 쌍의 하나의 상술된 구현은 4x4 변환으로서 존재하지만, 또한 다른 사이즈로도 확장될 수 있다(예를 들어, 8x8 등). 또한, 계층 피라미드 및 대형 변환을 실현하기 위해 변환쌍의 캐스케이드들이 사용될 수 있다. 예를 들어, 하나의 상술된 구현은 변환의 2레벨 캐스케이드를 사용한다. 제2 변환 스테이지에서, 마크로블럭 내에서 생성된 16개의 DC 계수들에 변환이 행해진다. 변환이 DCT와 유사하기 때문에, 우수한 속도-왜곡 성능 및 압축 효율을 갖는 무손실에서 손실로의 디지털 미디어 코덱(예를 들어, 양자화 파라미터가 무손실 설정에서 손실 설정으로 변경될 수 있는 코덱)을 실현하기 위해 사용될 수 있다.

본 발명의 추가의 특징 및 이점은 첨부 도면을 참조하여 계속한 실시예들의 이하 상세한 설명으로부터 명백해질 것이다.

이하의 설명은 개선된, 가역의 스케일-프리 2D 변환을 사용하는 디지털 미디어 압축 시스템 또는 코덱에 관한 것이다. 설명을 위해, 개선된 변환을 포함하는 압축 시스템의 실시예는 이미지 또는 비디오 압축 시스템이다. 대안적으로, 개선된 변환은 또한 기타 2D 데이터에 대한 압축 시스템 또는 코덱으로 포함될 수 있다. 변환은 디지털 미디어 압축 시스템이 특정 코딩 포맷으로 압축된 디지털 미디어 데이터를 인코딩하는 것을 요하지 않는다.

1. 인코더/디코더

도 6 및 7은 후술되는 개선된, 가역의 스케일-프리 2D 변환(650)에 기초하여 대표적인 2차원(2D) 데이터 인코더(600) 및 디코더(700)에 사용된 프로세스들의 일반적인 도면이다. 상기 도면들은 2D 데이터 인코더 및 디코더를 포함하는 압축 시스템에서 이러한 변환을 사용 및 응용하는 것에 대한 일반화된 또는 단순화된 설명을 제시한다. 이러한 변환에 기초한 대안의 인코더들에서는, 이러한 대표적인 인코더 및 디코더에 도시된 것보다 부가적이거나 소수의 프로세스들이 2D 데이터 압축을 위해 사용될 수 있다. 예를 들어, 몇몇 인코더/디코더는 또한 컬러 변환, 컬러 포맷, 스케일 가능 코딩, 무손실 코딩, 마크로블럭 모드 등을 포함할 수 있다. 개선된 2D 변환은 압축 시스템(인코더 및 디코더)이 무손실에서 손실로 변하는 양자화 파라미터에 기초할 수 있는 양자화에 따라, 2D 데이터의 무손실 및/또는 손실 압축을 제공하게 한다.

2D 데이터 인코더(600)는 인코더에 대한 입력으로서 제시된 2D 데이터(610)의 (전형적인 입력을 위해) 보다 압축된 표현인 압축 비트스트림(620)을 생성한다. 예를 들어, 2D 데이터 입력은 이미지, 비디오 시퀀스의 프레임, 또는 기타 2차원을 갖는 데이터일 수 있다. 2D 데이터 인코더는 입력 데이터를 마크로블럭들로 타일링(tiling)하고(630), 마크로블럭은 이러한 대표적인 인코더에서 사이즈가 16x16인 화소들이다. 2D 데이터 인코더는 각 마크로블럭을 4x4 블럭들로 더 타일링한다(632). "포워드 오버랩(forward overlap)" 연산자(640)는 블럭들 사이의 각 에지에 적용되는데, 그 후에 가역의 스케일-프리 변환을 사용하여 각각의 4x4 블럭이 변환된다(650). 이어서, 각 4x4 변환 블럭의 DC 계수(660)에 유사한 프로세싱 체인(타일링, 포워드 오버랩, 이어서 4x4 블럭 변환)이 수행된다. 결과로서의 DC 변환 계수들 및 AC 변환 계수들은 양자화되고(670), 엔트로피 코딩되고(680) 패킷화된다(690).

디코더는 역 프로세스를 수행한다. 디코더 측에서, 각각의 패킷으로부터 변환 계수 비트들이 추출되는데(710), 그로부터 계수들은 스스로 디코딩되고(720) 양자화 해제된다(730). DC 계수들(740)은 역변환을 적용함으로써 재생성되고, DC 계수들의 면은 DC 블럭 에지들에 걸쳐 적용된 적합한 평활화 연산자를 사용하여 "역 오버래핑"된다. 이어서, 4x4 역변환(750)을 DC 계수들, 및 비트스트림으로부터 디코딩된 AC 계수들(742)에 적용함으로써 전체 데이터가 재생성된다. 마지막으로, 결과로서의 이미지 면들의 블럭 에지들은 역 오버랩 필터링된다(760). 이것은 재구성된 2D 데이터 출력을 생성한다.

2. 개선된, 가역의 스케일- 프리 변환 구현

예를 들어, A. K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, 1989에 기재된 바와 같이, 분리가능한 2D 변환은 1D로 순서화된 데이터에 작용하여 유사한 순서화 벡터 결과를 생성하는 1D 변환으로서 구현될 수 있다. 등가의 변환 매트릭스는 분리가능한 경우에 사용되는 전후 체배기의 크로네커 곱에 의해 생성된다. x 및 y가 수학식 2의 2D 표시로부터 재순서화된 데이터 및 변환 벡터들을 나타내는 경우, 그 관계는 이하의 수학식 3으로 주어진다.

여기서,

이다.

수학식 2에 도시된 2D 변환의 분리가능한 구현이 수학식 3에서보다 (근사적 의미에서) 계산적으로 더 효과적이지만, 후자의 표시가 바람직한 속성들을 유도하는 특정 경우가 있다. 예를 들어, 수학식 3에 기초한 구현은 수학식 2에서보다 레이턴시가 낮은데, 그 이유는 단일 스테이지 매트릭스 곱셈(이는 여러 디지털 신호 처리기(DSP)에 고유하게 지원되는 동작임) 때문이다. 본원에 설명된, 개선된, 가역 스케일-프리 변환에 대해, 2x2 단계들의 1D 표시는 스케일-프리 가역 구조를 유도한다.

또한, 분리가능한 2D 변환은 보다 간단한 1D 변환들의 캐스케이드로서 구현될 수 있다. 변환 매트릭스들 T₁ 및 T₂는 수학식 4와 같이 분해될 수 있다고 가정한다.

매트릭스 곱셈 연산의 연관성을 사용하여 다음과 같이 2D 변환(수학식 2)을 재순서화하고,

캐스케이드된 1D 구현을 유도한다.

DCT 등의 변환들은 기본 2 포인트 회전 연산들의 캐스케이드로서 공식화될 수 있다. 2D DCT는 특정 바람직한 속성들을 소유하도록 수학식 6의 구조를 사용하여 공식화될 수 있으며, 이는 더 상세히 설명될 것이다.

A. 2D 하다마드 변환

1D 동작으로서 구현되는 2D 하다마드 변환은 크로네커 곱(Kronecker product)에 의해 생성된다.

흥미롭게는, 단지 보통의 리프팅 단계들을 사용하여 수학식 7에 대응하는 스케일-프리 가역 변환을 실현할 수 있다. 이러한 형태의 구현은 도 8의 신호 흐름 그래프(800)로서 도시된다. 몇몇 용장 연산들을 제거하는 대응 C++ 코드는 도 9에 도시된다. 이러한 코드 목록(900)에서, "swap(x,y)"은 독립 변수의 값들을 교환하는 함수이다.

상기로부터, 정규화된 가역 2D 하다마드 변환이 단지 보통의 리프팅 단계들을 사용하여 공식화될 수 있다는 것을 알 수 있지만, 이것은 틀림없이 "보다 간단한" 1D 하다마드 경우에는 가능하지 않다. 변환 매트릭스 자체는 거듭제곱(involutory)이고(즉,

은 자신의 역이다), 무손실 재구성은 리프팅 단계들이 조심스럽게 리버스(reverse)되어 임의의 라운딩 효과를 정밀하게 재생시키도록 요구한다. 구성(800)의 역(1000)은 도 10에 제시된다 - 구성(1000)은 이 경우의 포워드 변환과 동일하다. 변환 계수들 B 및 C는 신호 흐름 그래프에서 변경되는 것을 주의하라.

도 6의 인코더(600)에서의 가역의 스케일-프리 2D 변환(650)은 4x4 DCT에 대한 근사값을 사용한다. 이하의 설명은 변환(650)의 전체 변환 프로세스가 2x2 하다마드 변환이고, 아래와 같은 3개의 기본 2x2 변환 연산들의 캐스케이드로서 실현될 수 있다는 것을 증명한다.

여기서 2 포인트 회전 매트릭스 T_R은 수학식 9로 주어진다.

수학식 8의 1D 구현들은 (4개의 소수자리로 근사화된) 전후(pre and post) 변환 매트릭스의 크로네커 곱을 계산함으로써 얻어진다.

캐럿 ＾은 원하는 변환 매트릭스를 나타낸다. 실제 구현 결과의 근사값들은 캐럿을 갖지 않는다. 2x2 하다마드 변환에서, 원하는 변환 매트릭스 및 그 근사값은 동일하다. 따라서,

은 임의의 모호함 없이, 1D로 구현된 2x2 하다마드 변환을 나타내는데 사용된다. 다음,

및

의 리프팅 구현을 살펴보자.

B.

의 구현

변환(1100)의 스케일-프리, 리프팅 기반 구현은 도 11의 신호-흐름 그래프로서, 도 12의 C++ 코드 프로그램 목록(1200)에 도시된다. 첫번째 및 마지막 리프팅 스테이지들은 하다마드 변환 경우와 동일하다는 것을 알 수 있다. 보통의 전단 이외에, 2개의 중요한 리프팅 회전이 중간 스테이지에 적용된다. 중요한 각각의 회전은 3단계로 구현되는데, 3을 곱하고 3 또는 4비트만큼 비트 시프트하는 것이다. 따라서,

은 6개의 중요한 리프팅 단계들을 사용함으로써 가역의, 스케일-프리 방식으로 실현될 수 있다.

결과의 1D 변환 매트릭스

은 아래 수학식 12에 도시되는데, 이것은 수학식 10의

의 원래 공식과 거의 일치한다. 결과의 변환 매트릭스의 제2 및 제4 열들은 합해서 0이 되는데, 이것은 DC의 AC 대역들로의 누설이 없다는 것을 의미한다. 요구된 2D 회전들은 구성에서 단지 근사화되지만 이러한 바람직한 속성이 실현된다.

변환 매트릭스

은 거듭제곱(즉, 자신의 역임)이지만, 라운딩 에러는 신호 흐름 그래프 또는 코드의 2개의 연속 응용시 상쇄되지 않는다.

의 무손실 역은 신호 흐름 그래프에서 또는 C++ 코드에서 리프팅 단계들을 리버스함으로써 도출되어, 포워드 변환측 라운딩 에러들을 복제한다.

의 역(1300)의 신호 흐름 그래프는 도 13에 도시되고, 코드는 마찬가지로 도출될 수 있다.

C.

의 구현

변환(1400)은 2가지의 회전을 포함하는데, 그들 중 어느 것도 하다마드 변환이 아니다. 흥미롭게도,

는

보다 소수의 중요한 리프팅 단계들에 의해 실현될 수 있다. 이것은 자신이 갖는 T_R의 크로네커 곱의 대칭 속성들 때문이다.

변환(1400)의 신호 흐름 그래프 및 그것의 C++ 코드 실현의 프로그램 목록(1500)은 도 14 및 도 15에 각각 도시되어 있다.

3개의 중요한 리프팅 단계들에 의해 구현되는, 단지 하나의 중요한 회전은

를 실현하도록 요구된다. 이러한 회전은 스케일-프리 1D 2-포인트 하다마드 변환에 대응한다.

여기에 고려된 다른 변환들에 의하면, 수학식 13에 도시된

는 거듭제곱이지만, 조금도 자신의 정확한 역은 아니다.

의 무손실 역(1600)은 도 16에 도시된 바와 같이, 포워드 변환에 사용되는 신호 흐름 그래프를 리버스함으로써 얻어진다.

D. 상기 2x2 변환 구현을 위한 표기법 및 그것의 도출

이러한 3가지의 가역 스케일-프리 변환들을 사용하는 가역의, 스케일-프리 2D 변환에 대한 본원 설명에서는, 이하의 요점들이 적용된다. 우선, 2x2 데이터의 순서화(1700)의 결과로서의 상기 신호 흐름 그래프 및 C++ 코드는 도 17에 도시된 바와 같다. 공간 도메인 포인트들은 좌측에 도시되고 대응하는 주파수 도메인 포인트들은 우측에 도시된다. 이하의 가역, 스케일-프리 2D 변환 설명을 용이하게 하기 위해, 4개의 계조 레벨을 사용하여 4개의 데이터 포인트들을 나타내는 컬러 코딩이 여기에 도입된다.

종종, 2 포인트 변환들 또는 회전들은 수학식 14의 연산으로 정의된다.

이것은 거듭제곱 형태(수학식 15) 대신이다.

상기 2개의 형태는 실질적으로 동일한데, 그 이유는 제2 변환 계수의 부호만이 다르기 때문이다. 후자의 수학식 15가 여기에 사용되지만, 이 문서의 전체 도 출은 전자의 수학식 14와 동일하게 적용가능하다.

위에서 정의된 기본 2x2 변환들

,

의 구조는 각각의 2-포인트 변환이 회전이라는 것을 유념하여 구성된다. 또한, 2개의 2-포인트 회전들의 크로네커 곱은 수학식 16으로서 주어진다.

그 후 수학식 17과 같은 연산자 H가 정의된다.

H는 비 정규화된 더블 버터플라이(double butterfly) 연산을 나타내고 리프팅을 사용하여 효과적으로 구현될 수 있다.

이하의 팩토리화(factorization)가 적용된다.

이에 기초하여, 타입 T의 크로네커 곱은 3단계의 캐스케이드로 구현될 수 있다.

A. 리프팅 단계들을 사용하여 H에 의해 정의된 더블 버터플라이 연산.

B. 컴포넌트들의 제1 쌍 사이, 및 컴포넌트들의 제2 쌍 사이의 2 포인트 회전들, 및

C. 단계 a에서 수행된 더블 버터플라이의 역

특별한 경우

에 있어서, 도 8의 신호 흐름 그래프(800)로 도시되고 상술된, 보다 간단한 분해가 존재한다. 다른 경우에 있어서(예를 들어,

및

), 도 25에 도시된 흐름 그래프(2500)와 같은 결과 구조가 일반화될 수 있다.

상기 변형들의 3개의 신호 흐름 그래프(및 그 역)를 살펴보고, 그 구조에 있어서 기본적인 유사성을 관찰해보자. 변환의 제1 스테이지는 a-d 및 b-c 계수들 사이의 리프팅 연산이다. 마찬가지로 최종 스테이지는 역 리프팅 프로세스이다(부호 및 계수 교환을 감소). 따라서, 역 변환의 제1 스테이지는 A와 D 사이, 또한 B와 C 사이의 리프팅 연산이고, 최종 단계에서는 리버스 연산을 행한다. 대각 요소들 사이의 리프팅 단계들은 여기에 제시된 결합 2D 2x2 변환의 구별되는 특징이다.

다음 섹션은 4x4 DCT/IDCT에 가까운 무손실, 스케일-프리 변환의 구성에 관해 논의한다. 변환의 예시적인 실시예가 이 상세한 기술 논의에서 제시되지만, 기타 2x2 기본 가역 리프팅 기반 변환들의 추가 정의를 갖는 동일한 절차를 사용하여 원하는 속성을 갖는 고차원 가역 변환 실시예들을 생성할 수 있다.

E. 무손실, 스케일- 프리 변환

4-포인트 DCT는 도 3의 신호 흐름 그래프에 도시된 바와 같은 4개의 버터플 라이 연산들의 시퀀스로 감소될 수 있다. 제1 스테이지는 입력 데이터에 대해 2-포인트 하다마드 연산을 수행하는 2개의 버터플라이들(예를 들어, 입력 데이터 인덱스 0과 3; 및 제2의 입력 인덱스 1과 2 중 하나의 2-포인트 하다마드)을 포함한다. 제2 스테이지는 짝수 주파수 성분(인덱스 0과 2)을 발생시키는 제1 스테이지의 로우 패스 결과들에 대한 2 포인트 하다마드 연산, 및 홀수 주파수 성분(인덱스 1과 3)을 발생시키는 2포인트 π/8 회전을 포함한다.

2차원에서, DCT는 분리가능하게 구현될 수 있는데, 4x4 입력 데이터의 각 열의 수직 1D 4-포인트 DCT에 이어 행들의 수평 1D 4-포인트 DCT이다(또는 그 반대). 이것은 도 18의 분리가능한 DCT 구현(1800)으로 도시된다. 대안적으로, 상술된 두개의 1D DCT 단계들은 도 19의 인터리브된 DCT 구현(1900)으로서 도시된 바와 같이, 수학식 5의 이론을 사용하여, 수평 및 수직 사이에 인터리브될 수 있다.

또한, 상기 접근법을 따라가면, 대응하는 수평 및 수직 스테이지들이 더 결합될 수 있다. 예를 들어, 제1 스테이지는 "내부" 및 "외부" 입력 요소들에 대한 2 포인트 하다마드 변환이다. 수평 및 수직 스테이지들은 16개의 입력 데이터 요소들에 대한 2x2 2D 하다마드 변환의 4 응용들에 병합될 수 있고, 각 변환은 입력 포인트들의 대칭 세트에 적용된다. 마찬가지로, 제2 스테이지 수평 및 수직 단계들은 2x2 하다마드 변환 및 3개의 2x2 변환들로 합체될 수 있는데, 이들 중 2개는 전치(transpose)이다. 후자의 3개의 2x2 변환들은 사실상 앞서 정의된

및

의 2D 재매핑이라는 것을 알 수 있다.

보다 구체적으로는, 가역의 스케일-프리 2D 변환(650)(도 6)은 2x2 하다마드,

및

변환들의 구성으로 변환 연산들을 재구성함으로써 구현된다. 이러한 변환(650)의 2개의 스테이지는 도 20 및 도 21에 각각 도시된 바와 같이 수행된다. 각 스테이지는 스테이지 내에서 임의의 시퀀스로, 또는 동시에 수행될 수 있는 4개의 2x2 변환들을 포함한다.

역 2D 변환(750)(도 7)에 있어서, 스테이지들은 순서대로 리버스되고, 변환의 각 스테이지 내의 단계들은 포워드 변환 프로세스의 단계들의 역을 사용한다. 상술한 바와 같이, 가역의 2x2 하다마드 변환

은, 약간 정확하거나 무손실 면에서(in a bit exact or lossless sense), 그 자신의 역이다. 따라서, 역 포톤 변환(inverse Photon transform)의 제2 스테이지는 도 20에 도시된 바와 같이, 포워드 포톤 변환(forward Photon transform)의 단지 제1 스테이지이다. 역 포톤 변환의 제1 스테이지(2200)는 도 22에 도시되어 있다. 이 스테이지 내의 4개의 단계들(포워드 변환의 경우에 있어서는, 임의의 순서로 또는 동시에 실행될 수 있음)은, 앞서 정의되고 2D 2x2 스페이스로 다시 재매핑된 바와 같이,

,

및

의 역들을 적용한다.

도 20 및 도 21에 도시된 포워드 개선된 2D 변환(650)의 단계들을 따를 때, 결과로서의 변환 계수들은 도 23에 도시된 바와 같이 순서화된다. 도 22 및 도 20의 단계들을 사용하여 그 순서대로 역변환된 계수들에 대해서 동일한 순서화(2300)가 추정된다.

상술된 포워드 2D 변환(650)의 개선된 구현은 각각의 4x4 블럭에 대해 5개의

의 적용, 2개의

의 적용 및 하나의

의 적용을 포함한다. 이러한 변환들의 동일한 수의 적용들은 역 2D 변환(750)의 구현에 포함된다. 따라서, 무손실 포워드 또는 역 2D 변환을 실현하기 위해, 중요한 리프팅 단계들의 총수는 각 블럭에 대해 5x0+2x6+1x3=15이다. 이것은 화소당 대략 하나의 중요한 단계이다. 중요한 단계는 형태 (3xx+r)>>k의 연산이고, x는 피연산자, r 및 k는 라운딩 및 비트 시프트를 결정하는 상수들이다. k는 2, 3, 또는 4 중 어느 하나이다. 마찬가지로, 블럭당 17개의 1자리 우측 시프트(single-place right shifts), 즉 (x>>1)가 있다. 덧셈, 뺄셈 및 부정은 본 개관에서는 중요하지 않다.

비교로, 도 18에 도시된 2D DCT의 분리가능한 구현(1800)을 생각해보자. 각각의 4 포인트 DCT는 도 3에 도시된 바와 같이 3개의 2 포인트 정규화된 하다마드 연산들을 사용하여 구현되고, π/8 만큼의 회전은 3개의 중요한 리프팅 단계들을 사용하여 구현된다. 포워드 또는 역변환 중 하나에 대한 4x4 블럭당 중요한 리프팅 동작들의 총수는 2x4x3=24이다. 1자리 우측 시프트들의 총수도 또한 24이다. 결과로서의 변환이 1/4 내지 2(또는 무리수 범위 기반 함수들을 제외하지 않는 경우에는 4)의 범위의 표준을 갖는 기본 함수들을 생성한다는 사실을 고려하지 않으면, 이 수들은 개선된 포워드 변환(650) 및 역변환(750) 구현들보다 약 50% 높다. 대조적으로, 개선된 변환(650)의 모든 기본 함수들은 단위 표준이다.

F. 4:2:0 컬러스페이스에 대한 개선된 변환

인코더(600)(도 6) 및 디코더(700)(도 7)의 하나의 예시적인 구현에서는, YUV 4:2:0 컬러스페이스를 사용하여 이미지(또는 비디오 프레임) 내의 화소들의 컬러를 나타낸다. 이러한 예시의 코덱에서는, YUV 4:2:0 컬러스페이스의 마크로블럭은 휘도(Y) 채널의 화소들의 16x16 타일(tile), 및 색차(U 및 V) 채널들의 8x8 타일로서 정의된다. 이들은 상기 변환(650)을 사용하여 코딩된 변환인 4x4 블럭들로 더 분할된다. 4x4 변환(650)은 휘도 채널들의 DC 계수들에 적용된다. 그러나, 색차의 단지 2x2 샘플들만이 마크로블럭 내에서 이용가능하다. 그 후 예시의 코덱은 상술된 바와 같이 가역의 스케일-프리 2x2 하다마드 변환인

을 각 마크로블럭 내의 DC 색차값들에 적용한다. 이에 의해, 예시적인 코덱 포맷의 마크로블럭 구조가 보존되고, 4:2:0 포맷을 다루기 위한 코덱에 추가의 변환이 도입될 필요가 없다.

G. 라운딩 에러의 감소

라운딩 에러들은 우측 비트-시프트를 포함하는

,

및

변환들의 리프팅 단계들에 도입된다. 이러한 라운딩 에러들은 공지된 바이어스를 갖고, 변환 코스에 걸쳐 작성될 수 있다. 예를 들어, 형태 x+=(y>>1)의 단계는 수학적 등가물 x:=x+ y/2에 비해 x값에서 -1/4의 바이어스를 유도한다는 것이 알려져 있다. 그 이유는, (y>>1)이 2로 나누고 끝수를 잘라버리는 것이기 때문인데, 이것은 y가 짝수일 때 정확하고 y가 홀수일 때 1/2 만큼 벗어난다. 따라서, 확률적으로, -1/4 만큼 바이어스된다. 라운딩 에러들은 리프팅을 포함하는 정수-대-정수 변환들에서 불가피하지만, 전반적인 시스템에서 바이어스를 감소시키기 위해 바람직하다.

C++ 코드 발췌로서 앞서 도시된

,

및

의 공식들은 분할되거나 우측 비트-시프트된 피연산자들에 가변 인수들을 부가한다. 이러한 인수들은 바이어스를 최소화하도록 선택된다. 특히, 도 9의 C++ 코드 목록(900)을 사용하여 (바이어스되지 않은 입력에 대해)

의 제1 스테이지 연산을 한 후의 4개의 변환 계수들에서의 바이어스는 [1/4 -1/4 -1/4 -1/4]가 되도록 도시될 수 있다. 개선된 2D 변환(650)(도 6)에서의

의 제2 스테이지 적용은 제1 스테이지의 DC값들에, 즉 거의 1/4로 바이어스된 계수들에 대해 행해진다. 제2 스테이지 연산의 결과는 [3/4 -1/4 -1/4 -1/4]의 바이어스를 생성한다. 제1 계수는 DC의 DC이기 때문에, 크도록 기대되고 비교적 높은 3/4의 바이어스는 코딩 성능에 영향을 미치지 않는다.

및

에서의 중요한 리프팅 단계들은 변환 바이어스를 최소화하는 라운딩 인수들을 선택할 자유를 제공한다.

에 대한 C++ 코드 목록(1500)(도 15)은 때때로 오프-센터 라운딩 룰(off-center rounding rules)(예를 들어 a+=(3b+5)>>3)이, 특히 입력 데이터 자체가 바이어스되는 경우에, 전체 바이어스를 감소시키는 것을 나타낸다. 개선된 2D 변환 단계들

및

에 있어서, 모든 입력들은 -1/4로 바이어스된다.

일반적으로, 코덱의 정의는 비트스트림 디코더의 정의로 제한된다. 이러한 룰에 대한 예외는 무손실 코덱을 위해 만들어지는데, 그 이유는 인코더 및 디코더가 손실 없이 재구성될 입력 데이터에 대해 완전히 매치되어야 하기 때문이다. 손실에서 무손실로의 코덱의 경우에, 예외는 인코더와 디코더측 모두에 대해 정의된다. 그러나, 인코더가 완전 손실 모드에서 동작되는 경우, 코덱 사양서에 정의된 기본적인 성능보다 나은 성능을 제공할 수 있는 몇몇 지름길 또는 개선안들이 가능할 수 있다.

인코더 성능을 향상시키는 한가지 방법은 계수 바이어스를 바꾸는 것에 관한 것이다. 각각의 4x4 블럭에 대해 이하의 절차를 수행함으로써 인코더(600)/디코더(700)의 몇몇 실시예들에서 바이어스의 효과를 감소시킬 수 있다.

1. m=2^k을 곱하여 4x4 블럭을 확대한다(일반적으로 m=4에서 잘 작용함)

2. 블럭에 대해 개선된 2D 변환(650)을 수행한다.

3. 초기에 희망했던 양자화 파라미터의 m배인 양자화기를 사용하여 블럭을 양자화한다(예를 들어, 단계 1에서 원했던 QP(quantization factor)가 8이고 m=4인 경우 32의 QP를 사용한다)

디코더(700) 측에서 변경이 없지만, 동일한 비트레이트에서의 보다 나은 PSNR 수가 가능하다. 물론, 이것은 무손실 인코딩에서는 작용하지 않는다.

3. 컴퓨팅 환경

개선된 가역, 스케일-프리 2D 변환을 갖는 상술된 코덱은, 특히 컴퓨터; 이미지 및 비디오 레코딩, 송수신 기기; 휴대용 비디오 플레이어; 화상 회의 등의 예 를 포함하여 디지털 미디어 신호 프로세싱이 행해지는 각종 장치들 중 임의의 것에서 수행될 수 있다. 디지털 미디어 코딩 기술들은 도 24에 도시된 바와 같이, 하드웨어 회로 뿐만 아니라 컴퓨터 또는 다른 컴퓨팅 환경 내에서 실행되는 디지털 미디어 프로세싱 소프트웨어에서 구현될 수 있다.

도 24는 상술된 실시예들이 구현될 수 있는 적합한 컴퓨팅 환경(2400)의 일반화된 예를 도시한다. 본 발명은 다양한 범용 또는 특수 목적의 컴퓨팅 환경에서 구현될 수 있기 때문에, 컴퓨팅 환경(2400)은 발명의 용도 또는 기능의 범위에 어떤 제약도 암시하도록 의도되지 않는다.

도 24를 참조하면, 컴퓨팅 환경(2400)은 적어도 하나의 프로세싱 유닛(2410) 및 메모리(2420)를 포함한다. 도 24에서, 이러한 대부분의 기본 구성(2430)은 점선 안에 포함된다. 프로세싱 유닛(2410)은 컴퓨터-실행가능 명령어들을 실행하고 실제 또는 가상 프로세서일 수 있다. 멀티 프로세싱 시스템에서, 다수의 프로세싱 유닛은 프로세싱 능력을 증가시키는 컴퓨터-실행가능 명령어들을 실행시킨다. 메모리(2420)는 휘발성 메모리(예를 들어, 레지스터, 캐시, RAM), 불휘발성 메모리(예를 들어, ROM, EEPROM, 플래시 메모리 등), 또는 상기 두가지의 몇몇 조합일 수 있다. 메모리(2420)는 상술된 인코더/디코더 및 변환들을 구현하는 소프트웨어(2480)를 저장한다.

컴퓨팅 환경은 추가 특징들을 가질 수 있다. 예를 들어, 컴퓨팅 환경(2400)은 저장장치(2440), 하나 이상의 입력 장치(2450), 하나 이상의 출력 장치(2460), 및 하나 이상의 통신 접속(2470)을 포함한다. 버스, 컨트롤러, 또는 네트워크 등 의 내부접속 메카니즘(도시하지 않음)은 컴퓨팅 환경(2400)의 컴포넌트들을 상호 접속한다. 전형적으로, 오퍼레이팅 시스템 소프트웨어(도시하지 않음)는 컴퓨팅 환경(2400)에서 실행되는 다른 소프트웨어에 대한 오퍼레이팅 환경을 제공하고, 컴퓨팅 환경(2400)의 컴포넌트들의 액티비티들을 조정한다.

저장장치(2440)는 제거가능 또는 불휘발성일 수 있고, 자기 대스크, 자기 테이프 또는 카세트, CD-ROM, CD-RW, DVD, 또는 정보를 저장하는데 사용될 수 있고 컴퓨팅 환경(2400) 내에서 액세스될 수 있는 임의의 다른 매체일 수 있다. 저장장치(2440)는 개선된 SDLT로 코덱을 구현하는 소프트웨어(2480)에 대한 명령어들을 저장한다.

입력 장치(들)(2450)은 키보드, 마우스, 펜, 또는 트랙볼 등의 터치 입력 장치, 음성 입력 장치, 스캐닝 장치, 또는 입력을 컴퓨팅 환경(2400)에 제공하는 또 다른 장치일 수 있다. 음성을 위해, 입력 장치(들)(2450)는 아날로그 또는 디지털 형태로 오디오 입력을 받아들이는 사운드 카드 또는 유사 장치, 또는 오디오 샘플들을 컴퓨팅 환경에 제공하는 CD-ROM 판독기일 수 있다. 출력 장치(들)(2460)는 디스플레이, 프린터, 스피커, CD-라이터, 또는 컴퓨팅 환경(2400)으로부터의 출력 제공하는 또 다른 장치일 수 있다.

통신 접속(들)(2470)은 통신 매체를 통해 또 다른 컴퓨팅 엔티티와의 통신을 가능하게 한다. 통신 매체는 컴퓨터-실행가능 명령어들, 압축 오디오 또는 비디오 정보, 또는 변조 데이터 신호의 다른 데이터 등의 정보를 전달한다. 변조 데이터 신호는 신호 내의 정보를 인코드하는 방식으로 설정 또는 변경된 하나 이상의 특성 들을 갖는 신호이다. 예로서, 통신 매체는 전기, 광학, RF, 적외선, 음향, 또는 기타 반송파로 구현되는 유선 또는 무선 기술들을 포함하나, 이에 한정되지 않는다.

본원의 디지털 미디어 프로세싱 기술들은 일반적인 컴퓨터-판독가능 매체의 문맥으로 기술될 수 있다. 컴퓨터-판독가능 매체는 컴퓨팅 환경 내에서 액세스될 수 있는 임의의 이용가능 매체일 수 있다. 예로서, 컴퓨팅 환경(2400)에서, 컴퓨터-판독가능 매체는 메모리(2420), 저장장치(2440), 통신 매체, 및 상기의 임의의 조합들을 포함하나, 이에 제한되지 않는다.

본원의 디지털 미디어 프로세싱 기술들은 타겟인 실제 또는 가상 프로세서에 대해 컴퓨팅 환경에서 실행되는, 프로그램 모듈들 내에 포함된 명령어들 등의 컴퓨터-실행가능 명령어들의 일반적으로 문맥으로 기술될 수 있다. 일반적으로, 프로그램 모듈들은 특정 추상 데이터 타입들을 구현하거나 특정 태스크를 수행하는 루틴, 프로그램들, 라이브러리들, 오브젝트들, 클래스들, 컴포넌트들, 데이터 구조들 등을 포함한다. 프로그램 모듈들의 기능은 각종 실시예들에서 원하는 프로그램 모듈들 사이에서 결합 또는 분리될 수 있다. 프로그램 모듈들에 대한 컴퓨터-실행가능 명령어들은 로컬 또는 분산 컴퓨팅 환경 내에서 실행될 수 있다.

표현을 위해, 상세한 설명은 "결정한다", "발생한다", "조정한다, 및 "적용한다" 라는 용어들을 사용하여 컴퓨팅 환경에서의 컴퓨터 동작들을 기술한다. 이러한 용어들은 컴퓨터에 의해 수행되는 동작들에 대한 고급 추상화들이고, 사람이 행하는 작용들과는 혼동되어서는 안된다. 이러한 용어들에 대응하는 실제 컴퓨터 동작들은 구현에 따라 변한다.

본 발명의 원리가 적용될 수 있는 많은 가능한 실시예들의 관점에서, 그러한 실시예들과 같은 본 발명은 이하의 청구범위 및 그 등가물들의 범위 및 정신 내에 있다.

본 발명에 따르면, 개선된, 가역의 스케일-프리 2D 변환을 사용하는 디지털 미디어 압축 시스템 또는 코덱이 제공된다.

Claims

데이터 압축 인코딩 또는 디코딩을 위한 2차원 디지털 미디어 데이터를 처리하는 방법으로서,

상기 2차원 디지털 미디어 데이터의 입력을 수신하는 단계;

상기 디지털 미디어 데이터의 2차원 블럭에 수평 및 수직적으로 적용된 1차원 변환으로서 정의된 가역의(reversible), 스케일-프리(scale-free) 2차원 블럭 변환을 이용하여, 상기 디지털 미디어 데이터의 블럭 변환 기반(block transform-based) 데이터 압축 인코딩 또는 디코딩을 수행하는 단계 - 상기 디지털 미디어 데이터의 상기 2차원 블럭의 상기 변환은,

상기 수평 및 수직의 1차원 변환들로부터의 연산들을 인터리빙(interleaving)하는 2개 이상의 스테이지들의 각각에서, 리프팅(lifting) 단계들로 구현된 기본 변환들의 세트로 재배열된 각각의 스테이지의 상기 연산들을 상기 2차원 블럭의 값들의 독립적인 서브세트들에 적용하는 단계

에 의해서 실현됨 - ; 및

상기 인코딩된 또는 디코딩된 디지털 미디어 데이터를 출력하는 단계

를 포함하는, 방법.
제1항에 있어서,

제1 스테이지에서, 상기 2차원 블럭 값들의 독립적인 4-값 서브세트들에 2x2 하다마드 변환(Hadamard transform)을 적용하는 단계를 더 포함하는, 방법.
제2항에 있어서,

상기 4-값 서브세트들은,

상기 2차원 블럭의 코너들에 있는 4개의 값들의 그룹;

상기 2차원 블럭의 중앙에 있는 4개의 값들의 그룹;

상기 2차원 블럭의 수평 에지 중앙들에 있는 4개의 값들의 그룹; 및

상기 2차원 블럭의 수직 에지 중앙들에 있는 4개의 값들의 그룹

을 포함하는, 방법.
제1항에 있어서,

제2 스테이지에서, 상기 2차원 블럭 값들의 독립적인 4-값 서브세트들에 변환 세트를 적용하는 단계 - 상기 변환 세트 중 적어도 하나는 3개의 스테이지들의 캐스케이드(cascade) 형태로 구현됨 - 를 더 포함하며, 상기 3개의 스테이지는,

리프팅 단계들을 사용하여 연산자 H (
)에 의해 정의된 더블 버터플라이(double butterfly) 연산;

컴포넌트 값들의 제1 쌍 사이, 및 컴포넌트 값들의 제2 쌍 사이 각각에서의 2-포인트 회전들(rotations); 및

상기 더블 버터플라이 연산의 역(reverse)

을 포함하는, 방법.
제1항에 있어서,

제2 스테이지에서, 변환 세트를 상기 2차원 블럭 값들의 독립적인 4-값 서브세트들에 적용하는 단계를 더 포함하며,

상기 변환 세트는 2x2 하다마드 변환, 2-포인트 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱(Kronecker Product)으로서 도출된 2x2 홀수 회전 변환(2x2 odd rotate transform), 및 상기 2 포인트 회전 매트릭스들의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환(2x2 odd-odd rotate transform)을 포함하는, 방법.
제1항에 있어서,

라운딩 에러 바이어스(rounding error bias)를 감소시키면서,

분할 또는 우측-비트-시프트(right-bit-shift)를 포함하는 버터플라이 연산에 있어서, 각각의 상기 버터플라이 연산 이전에 분할되거나 또는 우측 비트 시프트되는 피연산자들에 가변 인수(varying factor)를 부가하는 단계를 더 포함하는, 방법.
제1항에 있어서,

손실 압축에 대한 라운딩 에러 바이어스를 감소시키면서,

상기 변환 전에, 인수(factor)를 곱함으로써 상기 2차원 블럭을 스케일링(scaling)하는 단계;

상기 변환을 수행하는 단계; 및

결과적으로 생긴 변환 계수들을, 상기 인수가 곱해진 원하는 양자화기와 동일한 양자화기에 의해 양자화하는 단계

를 더 포함하는, 방법.
2차원 디지털 미디어 데이터 처리의 역을 수행하는 방법으로서,

인코딩된 디지털 미디어 데이터의 입력을 수신하는 단계;

상기 인코딩된 디지털 미디어 데이터의 2차원 블럭에 수평 및 수직적으로 적용된 1차원 역변환으로서 정의된 가역의, 스케일-프리 2차원 역 블럭 변환(inverse block transform)을 이용하여, 상기 인코딩된 디지털 미디어 데이터의 블럭 변환 기반(block transform-based) 데이터 압축 해제를 수행하는 단계 - 상기 인코딩된 디지털 미디어 데이터의 상기 2차원 블럭의 상기 역변환은,

상기 수평 및 수직의 1차원 역변환들로부터의 연산들을 인터리빙하는 2개 이상의 스테이지들 각각에서, 리프팅 단계들로서 구현된 기본 변환들의 세트로서 재배열된 상기 각각의 스테이지에서의 상기 연산들을 상기 2차원 블럭의 값들의 독립적인 서브세트들에 적용하는 단계

에 의해서 실현됨 - ; 및

압축 해제된 2차원 디지털 미디어 데이터를 출력하는 단계

를 포함하는, 방법.
제8항에 있어서,

제1 스테이지에서, 변환 세트를 상기 2차원 블럭 값들의 독립적인 4-값 서브세트들에 적용하는 단계를 더 포함하며,

상기 변환 세트는 2x2 하다마드 변환, 2-포인트 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱으로서 도출된 2x2 홀수 회전 변환, 및 상기 2 포인트 회전 매트릭스들의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환을 포함하는, 방법.
제9항에 있어서,

상기 4-값 서브세트들은 상기 2차원 블럭의 상부 좌측, 상부 우측, 하부 좌측 및 하부 우측에서의 4개의 값들의 그룹들을 포함하는, 방법.
제9항에 있어서,

상기 2x2 하다마드 변환, 2x2 홀수 회전 변환, 및 2x2 홀수-홀수 회전 변환은,

식에 의해 주어지고, 4개의 소수자리로 근사화되는, 방법.
제8항에 있어서,

제2 스테이지에서, 2x2 하다마드 변환을 상기 2차원 블럭 값들의 독립적인 4-값 서브세트들에 적용하는 단계를 더 포함하는, 방법.
2차원 디지털 미디어 데이터의 2차원 블럭들에 수직 및 수평적으로 적용된 4-포인트 변환으로서 정의된 가역의, 스케일-프리 2차원 변환을 사용하여 블럭 변환 기반 코딩에 의해 상기 디지털 미디어 데이터의 압축을 수행하는 압축 시스템의 인코더로서,

인코딩될 2차원 디지털 미디어 데이터를 버퍼링하는 버퍼 메모리; 및

수평 및 수직의 1차원 4-포인트 변환으로부터의 연산들을 인터리빙하는 2개 이상의 스테이지들의 각각에서, 리프팅 단계들로서 구현된 기본 2x2 변환들의 세트로서 재배열된 상기 각각의 스테이지에서의 상기 연산들을 상기 2차원 블럭의 독립적인 4-값 서브세트들에 적용함으로써 상기 디지털 미디어 데이터의 2차원 블럭들에 상기 2차원 변환을 적용하는 프로세서 - 상기 프로세서는 또한, 상기 2차원 블럭의 상기 변환에 의해서 생성된(produced) 변환 계수들을 엔트로피 인코딩함 -

를 포함하는, 인코더.
제13항에 있어서,

상기 기본 변환들은 2x2 하다마드 변환, 2-포인트 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱으로서 도출된 2x2 홀수 회전 변환, 및 상기 2 포인트 회전 매트릭스들의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환을 포함하는, 인코더.
제13항에 있어서,

제1 스테이지에서 상기 프로세서는, 상기 디지털 미디어 블럭의 코너들, 중앙, 상부/하부 에지들, 및 좌측-우측 에지들에서의 4-값 세트들을 포함하는 각각의 상기 디지털 미디어 블럭의 4-값 서브세트들에 2x2 하다마드 변환을 적용하는, 인코더.
제13항에 있어서,

제2 스테이지에서 상기 프로세서는, 2x2 하다마드 변환을 각각의 상기 디지털 미디어 블럭의 상부 좌측에 있는 4-값 서브세트에 적용하고, 2x2 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱으로서 도출된 2x2 홀수 회전 변환 및 2x2 하다마드 변환을 각각의 상기 디지털 미디어 블럭의 상부-우측 및 하부-좌측에 있는 4-값 서브세트들에 적용하고, 상기 2 포인트 회전 매트릭스와 그 자신의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환을 각각의 상기 디지털 미디어 블럭의 하부-우측에 있는 4-값 서브세트에 적용하는, 인코더.
가역의, 스케일-프리 2차원 변환의 역을 사용하여 블럭 변환 기반의 디코딩에 의해, 압축된 2차원 디지털 미디어 데이터의 압축 해제를 수행하는 압축 시스템의 디코더로서,

상기 압축된 2차원 디지털 미디어 데이터의 블럭들의 변환 계수들을 버퍼링하는 버퍼 메모리; 및

수평 및 수직의 1차원 4-포인트 역변환으로부터의 연산들을 인터리빙하는 2개 이상의 스테이지들의 각각에서, 리프팅 단계들로서 구현된 기본 2x2 변환들의 세트로서 재배열된 상기 각각의 스테이지에서의 상기 연산들을 상기 2차원 블럭의 독립적인 4-값 서브세트들에 적용함으로써 상기 디지털 미디어 데이터의 2차원 블럭에 상기 가역의, 스케일-프리 2차원 변환의 상기 역을 적용하고, 상기 블럭들의 상기 변환 계수들을 엔트로피 디코딩하는 프로세서

를 포함하는, 디코더.
제17항에 있어서,

상기 기본 변환들은 2x2 하다마드 변환, 2-포인트 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱으로서 도출된 2x2 홀수 회전 변환, 및 상기 2 포인트 회전 매트릭스들의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환을 포함하는, 디코더.
제18항에 있어서,

제1 스테이지에서 상기 프로세서는, 2x2 하다마드 변환을 각각의 상기 디지털 미디어 블럭의 상부 좌측에 있는 4-값 서브세트에 적용하고, 2-포인트 하다마드 변환 및 2 포인트 회전 매트릭스의 크로네커 곱으로서 도출된 2x2 홀수 회전 변환 및 2x2 하다마드 변환을 각각의 상기 디지털 미디어 블럭의 상부-우측 및 하부-좌측에 있는 4-값 서브세트들에 적용하고, 상기 2 포인트 회전 매트릭스들의 크로네커 곱으로서 도출된 2x2 홀수-홀수 회전 변환을 각각의 상기 디지털 미디어 블럭의 하부-우측에 있는 4-값 서브세트에 적용하는, 디코더.
제18항에 있어서,

제2 스테이지에서 상기 프로세서는, 상기 디지털 미디어 블럭의 코너들, 중앙, 상부/하부 에지들, 및 좌측-우측 에지들에서의 4-값 세트들을 포함하는 상기 각각의 디지털 미디어 블럭의 4-값 서브세트들에 2x2 하다마드 변환을 적용하는, 디코더.