비디오 시퀀스 압축용 인코딩 방법(Encoding method for the compression of a video sequence)

공개특허 10-2004-0068302
- 1 -
(19)대한민국특허청(KR)
(12) 공개특허공보(A)
(51) 。Int. Cl.7
H04N 7/26
(11) 공개번호
(43) 공개일자
10-2004-0068302
2004년07월30일
(21) 출원번호 10-2004-7009659
(22) 출원일자 2004년06월18일
번역문 제출일자 2004년06월18일
(86) 국제출원번호 PCT/IB2002/005266 (87) 국제공개번호 WO 2003/055223
(86) 국제출원출원일자 2002년12월05일 (87) 국제공개일자 2003년07월03일
(30) 우선권주장 01403318.7 2001년12월20일 EP(EP)
(71) 출원인 코닌클리케 필립스 일렉트로닉스 엔.브이.
네델란드왕국, 아인드호펜, 그로네보드스베그 1
(72) 발명자 보트레빈센트
네델란드, 아아 아인드호펜 5656, 홀스트란 6
비네티에르마리옹
네델란드, 아아 아인드호펜 5656, 홀스트란 6
(74) 대리인 이병호
심사청구 : 없음
(54) 비디오 시퀀스 압축용 인코딩 방법
요약
본 발명은 3차원 웨이블릿 변환에 의한 비디오 시퀀스의 압축을 위한 인코딩 방법에 관한 것이다. 본 방법은 계층 피
라미드를 구성하는 변환 계수를 유도하는 계층 서브밴드 인코딩 처리에 기초한다. 루트가 근사 서브밴드의 픽셀로 형
성되고 이들 픽셀 각각의 자손이 고차 서브밴드의 픽셀로 형성되는 시공간 방향 트리는 상기 피라미드 안의 시공간
관계를 정의한다. 웨이블릿 변환의 초기 서브밴드 구조는, 인코딩 처리에서, 트리 내에 형성된 부모-자손 의존성을 고
려하는 순서로 서브밴드를 차례로 주사하는 것에 의해 보존되고, 계수의 최상위 비트의 순차 전송을 위해 트리의 각
계수에 플래그 '온/오프'가 부가된다. 본 발명에 따르면, 부가적인 특정한 한 비트 플래그가 그 계수의 전체 상태에 관
한 정보를 제공하기 위해 각 서브밴드에 제공되고, 이 때, 각 서브밴드의 부모-자손 의존성에 관한 상기 부가 정보는
상기 플래그가 두 가능한 값들 중 제 1 값을 가지면 상기 서브밴드를 처리하고 상기 플래그가 상기 두 값들 중 제 2 값
을 가지면 상기 서브밴드를 스킵하도록 사용된다.
대표도
도 1
색인어
비디오 압축, 인코딩,
명세서
공개특허 10-2004-0068302
- 2 -
기술분야
본 발명은, 3-차원(3D) 웨이블릿 변환에 의해 분해되어 상기 변환의 분해 레벨들에 대응하는 소정 수의 연속하는 해
상도 레벨들을 가져오는 프레임들의 그룹들(GOF들)로 분할된 비디오 시퀀스의 압축을 위한 인코딩 방법으로서, 상기
방법은 각 GOF의 화상 요소들(픽셀들)의 원래의 세트로부터 계층 피라미드를 구성하는 변환 계수들을 이끌어내는
계층 서브밴드 인코딩 처리에 기초하며, 루트가 상기 3D 웨이블릿 변환으로부터 유발된　근사 서브밴드(approximat
ion subband)의 픽셀들로 형성되고 이들 픽셀의 각 자손들(offsprings)이 이들 루트 픽셀들에 의해 정의되는 화상 볼
륨(volume)에 대응하는 고차 서브밴드들의 픽셀들로 형성되는 시공간 방향 트리는 상기 계층 피라미드 내부의 시공
간 관계를 정의하며, 상기 3D 웨이블릿 변환의 초기 서브밴드 구조는 상기 시공간 트리에 형성된 부모-자손 의존성들
을 고려하는 순서로 상기 서브밴드를 차례로 주사(scanning)함으로써 보존되고, 특정한 일 비트 플래그가 상기 계수
들의 최상위 비트들의 순차 전송을 고려하여 상기 시공간 트리의 각 계수에 부가되며, 이들 플래그들은 이들 중 적어
도 하나가 픽셀들의 세트 상태를 설명하고 적어도 다른 하나가 단일 픽셀의 상태를 설명하도록 하는, 상기 인코딩 방
법에 관한 것이다.
배경기술
이종 네트워크(heterogeneous networks)에 대한 비디오 스트리밍은 높은 스케일러빌러티 능력(scalability capabili
ty)을 필요로 하는데, 즉, 이것은 비트 스트림의 일부가 시퀀스의 안전한 디코딩 없이 디코딩될 수 있고 낮은 공간 또
는 시간 해상도(공간 스케일러빌러티, 시간 스케일러빌러티)에서 또는 낮은 품질(SNR 또는 비트율 스케일러빌러티)
로 초기 비디오 정보를 재구성하도록 재결합될 수 있어야 한다는 것을 의미한다. 이들 세 종류의 스케일러빌러티(공
간, 시간, SNR) 모두를 달성하기 위한 편리한 방법은, 입력 비디오 시퀀스의 모션 보상 이후, 상기 시퀀스의 3차원(3D
, 또는 2D t) 웨이블릿 분해이다. WO 01/84847(PHFR000044)호는 비디오 코딩의 풀리 스케일러블(fully scalable)
방법을 설명하는데, 이에 따르면 시간(공간) 스케일러빌러티는 각각의 시간 해상도 레벨(최고의 공간 해상도 레벨)에
서 모션 추정을 수행함으로써 얻어진다. 결과적으로 생성되는 시공간 트리의 계층적 인코딩은 FSZ(Fully Scalable Z
erotree)로 명명된 기술에 기초한 새로운 인코딩 모듈에 의해 수행된다. 이 풀리 스케일러블 코딩 방법의 개략은 『P
roceedings of IEEE Signal Processing Society, 2001 International Conference on Image Processing, Thessal
oniki, Greece, October 7-10, 2001, pp. 1017-1020』의 Bottreau, M. Benetiere, B. Felts 및 B. Pesquet-Pope
scu에 의한 'A Fully Scalable 3D Subband Video Codec'에서도 설명되어 있다.
이 이전 기술은 소위 SPIHT(Set Partitioning In Hierarchical Trees algorithm)의 영향을 받은 것으로, 그 원리가
먼저 설명되어야 한다. 예를 들면 『IEEE Transactions on Circuits and Systems for Video Technology, vol.6, n
°3, June 1996, pp.243-250』의 A. Said 및 W.A. Pearlman에 의한 'A new, fast, and efficient image codec bas
ed on set partitioning in hierarchical tree'과 이것의 3D 경우로의 확장인 예를 들면 『Proceedings of Data Com
pression Conference, March 25-27, 1997, Snowbird, Utah, USA, pp.251-260』의 B.J. Kim 및 W.A. Pearlman
에 의한 'An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees(SPI
HT)'에 설명된 원래의 SPIHT 알고리즘은: 진폭의 감소에 따른 계수의 부분 정렬(partial sorting)과, 자연 화상 고유
의 자기 유사성을 탐사하는 것에 의한 웨이블릿 분해의 스케일을 걸친 중요한 정보의 누락의 예측이라는 중요한 개념
에 근거하고 있다. 이것은, 웨이블릿 분해의 가장 낮은 스케일에서 계수가 중요하지 않은 경우에는, 다른 스케일에서
같은 영역에 대응하는 계수도 높은 확률로 중요하지 않다라는 것을 의미한다. 기본적으로는, SPIHT는, 다른 해상도
로 같은 화상 영역에 대응하는 픽셀들의 세트와, 0을 향한 시공간 분해 트리 안에서 발견된 가장 중요한 레벨에서의 '
중요한 레벨'이라고 불리는 값을 비교하는 것으로 이루어진, 반복 알고리즘이다. 소정의 레벨 또는, 비트플레인(bitpla
ne)에 대해, 두 패스(passes)가 수행된다: 제로트리 또는 서브트리를 검색하고, 그리고, 중요하지 않은 및 중요한 계
수를 정렬하는 정렬 패스(sorting pass)와, 중요한 계수의 정밀도 비트를 전송하는 개량 패스(refinement pass). SPI
HT 알고리즘은, 분해의 최고 레벨에서 최저 레벨로, 웨이블릿 계수를 검사한다. 이것은, 첫 번째로, 증가한 해상도로,
최소 스케일의 서 브밴드 안에 배치된 중요 세부(important details)에 대응하는 계수를 고려하고, 그리고, 정밀한 세
부(finer details)에 대응하는 최소의 계수를 시험하는 것에 대응한다. 이것은, 알고리즘의 '계층' 지정을 정당화한다:
복수의 비트는 이들이 나타내는 세부의 중요성을 감소시키는 것에 의하고 전송되고, 그리고, 이와 같이, 순차 비트스
트림(stream)이 형성된다.
공간(또는, 3D의 경우에는 시공간) 방향 트리라고 칭해지는 트리 구조(tree structure)는, 웨이블릿 계수의 계층 피라
미드 안의 공간(또는, 시공간) 관계를 정의한다. 트리의 루트는, 최저의 해상도에서의 근사 서브밴드('루트' 서브밴드)
의 픽셀로 구성되고, 한편으로는, 루트 픽셀에 의해 정의된 화상 영역(3D의 경우에는 화상 볼륨)에 대응하는 고차원
서브밴드의 픽셀은, 이 픽셀의 자손을 구성한다. SPIHT 알고리즘의 3D 버전에서는, 리프(leaf)의 임의의 서브밴드의
각 픽셀이 8의 자손 픽셀을 갖고, 그리고, 각 픽셀은 1개의 부모만을 갖는다(이 규칙에는 1개의 예외가 있고: 루트의
경우에는, 8중 1 픽셀은 자손을 갖지 않는다). 이하의 표기는, 부모－자손 관계를 기술한다:
O(x,y,z): 노드(x,y,z)의 직접적인 자손의 좌표 세트;
공개특허 10-2004-0068302
- 3 -
D(x,y,z): 노드(x,y,z)의 모든 자손들의 좌표 세트;
H(x,y,z): 모든 시공간 방향 트리 루트의 좌표 세트(최고 피라미드 레벨의 노드: 시공간 근사 서브밴드);
L(x,y,z)=D(x,y,z)-O(x,y,z)
(도 1에 3차원 경우의 이들 의존성을 나타내는데, 표기는 다음과 같다. TF＝시간 프레임, TAS＝시간 근사 서브밴드,
CFTS＝시공간 근사 서브밴드 안의 계수(또는, 루트 계수), TDS.LRL＝분해의 최후의 해상도 레벨에 있어서 시간 상
세 서브밴드, TDS.HR＝고해상도에 있어서 시간 상세 서브밴드이다).
SPIHT 알고리즘은, LIS(중요하지 않은 세트의 리스트)), LIP(중요하지 않은 픽셀의 리스트) 및, LSP(중요한 픽셀의
리스트)의, 3개의 리스트를 사용한다. 이들 모든 리스트에 있어, 각 엔트리는 좌표(x,y,z) 세트로 식별된다. LIP와 LIS
에 있어서, (x,y,z)는, 유일한 계수를 가리키지만, 한편, LIS에서는, 시공간 트리의 서브트리인 계수 D(x,y,z) 또는 L(x
,y,z)의 세트를 나타낸다. 이들을 구별하기 위해, LIS 엔트리는, D(x,y,z)를 나타내는 경우에는 타입 A이고, L(x,y,z)을
나타내는 경우에는 타입 Ｂ이다. 제 1의 패스(정렬 패스) 동안, LIP의 모든 픽셀은 테스트되고, 중요하게 된 것은 리스
트 LSP로 이동된다. 마찬가지로, 중요하게 된 LIS의 세트는 리스트 LIS로부터 삭제되고, LIS의 끝에 배치된 서브세트
로 분할되고, 각각이 차례로 시험될 것이다. LSP는, '정제될' 중요한 픽셀의 리스트를 포함하고, 계수의 제 n 비트는,
이것이 레벨ｎ에 관하여 중요한 경우에는, 전송된다.
비디오 코딩 시스템의 글로벌 압축율을 향상시키기 위해서, 제로트리 인코딩 모듈에 산술적 인코더를 부가하는 것이
일반적이다. 다른 방법에서는, 대부분의 시간, 계층적이고 산술적인 코딩 모듈이 분리된 것으로 생각된다. 이들을 단
일 코딩 시스템에서 효율적으로 결합하기 위해, 원래의 SPIHT 알고리즘에 약간의 수정이 가해진다. SPIHT에서 리스
트 LIS, LIP 및 LSP의 사용이 분류 작업(classification task)을 용이하게 하지만, 이들 리스트는 계수의 지리적 구조(
geographic organization)에는 방해가 된다. 제로트리에 대한 주사의 때에 행해지는 철저한 검색(in-depth search)
은, 서브밴드 내부의 용장도(redundancy)를 활용하지 않고, 산술 코딩이 관련된 관계(context)의 결정을 어렵게 한다
(이 관계는 현재의 픽셀에 대해 약간의 영향을 끼칠 수 있는 정보 특히 인접한 픽셀에 관한 정보이다). 논리적 상태의
세트에 의해 행해지는 리스트 LIS, LIP, LSP의 조작은, 픽셀의 조작의 순서의 예측을 어렵게 한다. 다른 시공간 서브
밴드에서 오는 동일한 3D 자손 트리에 속하는 픽셀은 인코딩되고, 차례로 리스트 안에 넣어지고, 이것은, 다른 서브밴
드의 픽셀을 혼합하는 효과를 갖는다. 이와 같이, 동일한 서브밴드의 픽셀간의 지리적인 상호 의존성이 손실된다. 더
욱, 시공간 서브밴드는, 시간 또는 공간 필터링의 결과이기 때문에, 시퀀스의 프레임은, 세부(details)의 방향을 부여
하는, 특권이 있는 축에 따라 필터링된다. SPIHT 알고리즘이 적용되면, 주사는 지리적인 순서를 고려하지 않기 때문
에, 이 방향 의존성도 손실된다.
또한, 리스트 LIS, LIP, LSP의 시험의 결과로부터의 비트 및 계수의 부호는, 상당히 다른 통계적인 성질을 갖는다. 1
개의 리스트에 대한 관련된 관계는, 전체적으로 서로 상이할 수 있다. 예를 들면, LIP가 중요하지 않은 픽셀들의 세트
를 가리키는 때는, 픽셀이 중요하지 않은 픽셀들의 세트에 의해 둘러싸이고 있는 경우에는, 그것도 중요하지 않을 가
능성이 크다고 생각하는 것이 합리적이지만, 그러나, LSP에 대해서는, 중요성의 특정한 레벨에서, 인접한 개량 비트
가 1(0)인 경우에는, 시험된 픽셀의 개량 비트가 1(0)인 것이 반드시 추론될 수 있는 것은 아니다.
이미 언급된 문헌 WO 01/84847호에서 설명된 기술을 사용함으로써, 3D 웨이 블릿 변환의 초기 서브밴드 구조가 보
존될 수 있으며, 각 계수에 부가되는 마커, 또는 플래그는 이 계수가 어느 리스트(LIS, LIP 또는 LSP)에 속하는지를
나타낸다. 보다 구체적으로는, 상기 특허 문헌에서 고려된 방법에 있어서, 전체적인 시공간 트리는 각각의 새로운 비
트플레인에 대해 완전히 주사된다. 제 1의 비트플레인의 끝에서, 3D 볼륨의 자손 의존성이 평가된다(따라서 이 제 1
의 주사는 아주 중요하고 도 2에서 설명되는 자손 의존성의 계산 순서를 전적으로 고려해야만 하는데, 도 2에서 SA는
공간축(s), TA는 시간축(t), R은 루트, FC는 제 1의 자식들(children), SC는 제 2의 자식들, 그리고 TC는 제 3의 자
식들이다). 상기 방법에 따르면, 서브밴드는 부모-자손 관계를 고려하는 순서로 차례로 주사되며, 적어도 두 개, 바람
직하게는 네 개의 상이한 플래그가 시공간 트리의 계수에 부가된다:
A) 그들의 적어도 1개의, 바람직하게는 2개가 세트(트리 또는 서브트리)의 상태를 기술한다:
- D(x,y,z)가 여전히 중요하지 않은 경우에는, DIRECT_SET_INSIG(또는 FS1);
- L(x,y,z)가 여전히 중요하지 않은 경우에는, INDIRECT_SET_INSIG(또는 FS2)
B) 적어도 다른 1개 바람직하게는 2개의 다른 것이 단일 픽셀의 상태를 기술한다:
- 현재의 픽셀이 중요한 경우에는, SIG( 또는, FP3);
공개특허 10-2004-0068302
- 4 -
- 현재의 픽셀이 중요하지 않은 경우 또는 그 중요성이 분석될 경우에는 (제로트리 안에 포함되지 않은 픽셀에 디폴
트(default)가 주어진다), INSIG(또는, FP4).
본 방법의 주요 단계는 다음과 같다:
1. 초기화:
- 플래그 FP4가 최하위의 시공간 서브밴드의 전 계수에 놓여지고,
- 플래그 FS1은, 상기 최하위의 시공간 서브밴드의 7/8의 계수에 놓여진다.
2. MSL(시공간 분해 트리 안에서 발견된 최상위 레벨( m aximum s ignificance l evel)을 계산하고 출력한다.
3. n=MSL로부터 0으로, 시공간 트리의 완전 탐사(full exploration)를 행하고(이하에 설명하는 바와 같이, 2 개의 주
요 어프로치가 가능하다: 공간적으로 구동된 해상도 스케일러빌러티와, 시간적으로 구동된 해상도 스케일러빌러티),
시공간 트리의 각 계수(x,y,z)에 대하여, 이하의 동작을 행한다:
a) 세트 중요성:
1) 플래그 FS1이 '온'이면, 출력＝S n(D(x,y,z)).
S n(D(x,y,z))＝1이면:
- 각각의 에 대해서, 플래그 FP4를 두고;
- (x,y,z)로부터 플래그 FS1을 제거하고;
- 이면, 플래그 FS2를 둔다.
2) 플래그 FS2가 '온'이면, 출력=S n(L(x,y,z)).
S n(L(x,y,z))=1이면:
- 각각의 에 대해서, 플래그 FP1을 두고;
- (x,y,z)로부터 플래그 FS2를 제거한다.
b) 픽셀 중요성:
(1) 플래그 FP3이 온이면, 출력=(x,y,z)의 n번째 비트.
2) 플래그 FP4가 온이면, 출력=S n(x,y,z).
S n(x,y,z)=1이면:
플래그 FP3을 온으로 두고;
부호(x,y,z)를 출력하고;
플래그 FP4를 제거한다.
이 프레임은, 세부(details)의 방향을 부여하는, 특권이 있는 축(공간적 또는 시간적)을 따라 필터링된다. 이들 방향은,
동일 방향을 따라 서브밴드를 주사하는 것에 의해 보다 좋게 고려될 수 있다. 지시된 방법을 사용하여, 공간축 또는
시간축의 어느 쪽인 선택된 특권이 있는 축에 의존한 계수의 시공간 볼륨을 탐사하는 2개의 주된 방법이 있다. 따라서
, 2 형식의 '멀티-스케일러블' 비트스트림을 얻을 수 있는데, 첫 번째 것은 공간 해상도에 의해 도출되고, 두 번째 것은
시간 해상도에 의해 도출된다:
공개특허 10-2004-0068302
- 5 -
(A) 공간적으로 구동된 해상도 스케일러빌러티:
이 기구(scheme)에서, 도 3에 도시된 바와 같이, 차례로 공간적인 해상도가 완전하게 탐사되기 때문에, 각 비트플레
인에 대해서, 트리 주사가 공간적으로 방향 결정되고, 각 공간 스케일 안에서 모든 시간 해상도가 연속적으로 주사된
다. 다시 말하면, 시간 주파수는 공간 주파수보다도 높다. 비트스트림의 일부를 스킵(skip)하는 가능성을 갖도록, 비트
스트림 안에 해상도 플래그가 도입된다. 주사 전략(scanning strategy)은, 도 4에 도시된 바와 같이 구성된 비디오 비
트스트림을 유도하는데, 여기에서, 라인 s와 ｔ는, 공간 및 시간 분해 레벨(SDL 및 TDL)에 각각 대응하고, 플래그 A
는 2개의 비트플레인을 분리하는 플래그이고, 플래그 B는 2개의 공간 분해 레벨을 분리하는 플래그이다.
(B) 시간적으로 구동된 해상도 스케일러빌러티:
이 기구에서, 도 5에 도시된 바와 같이, 차례로 시간적인 해상도가 완전하게 탐사되기 때문에, 각 비트플레인에 대해
서, 트리 주사가 시간적으로 방향 결정되고, 각 시간 스케일 안에서 모든 공간 해상도가 연속적으로 주사된다. 이 주사
전략은, 도 4와 비교하여 도 6에 도시된 바와 같이 구성된 비디오 비트스트림을 유도한다(여기서, 플래그 B는 2개의
시간 분해 레벨을 분리한다). 양 경우에 있어서, 3개 형식의 스케일러빌러티(시간, 공간 해상도, SNR)를 얻을 수 있다:
시공간 주사가 비트플레인 반복 루프에 삽입되기 때문에 SNR 스케일러빌러티는 여전히 이용가능하고, 시간 및 공간
스케일러빌러티는 t max가능 프레임율과 s max가능 디스플레이 사이즈를 가지고 각각 제공되는데, 여기서 t=1은 최
소 프레임율에 대응하고, s=1은 최소 디스플레이 사이즈에 대응한다.
본 방법에 의하면, 고정된 서브밴드 주사(리스트의 주사를 대체)와 플래그의 인식 덕분에, 코히어런트한 지리적 관계
가 각 모델에 대해 회복된다: 3D 웨이블릿 변환의 초기 서브밴드 구조는 보존되고, 각 계수에 부가된 플래그는 이 계
수가 어느 리스트(LIS, LIP 또는 LSP)에 속하는지를 나타낸다. SPIHT의 계층적이고 논리적인 구조는 보존되고, 동시
에 한 리스트에서 다른 리스트로 계수를 이동하는 것은 그 플래그를 변경하는 것에 의해 '가상적으로' 수행되고, 판독
의 순서는 SPIHT 알고리즘의 로직에 의해 수행되는 변화에 의존하지 않는다. 표준적인 SPIHT 알고리즘과 엔트로피
코딩을 결합하는 것보다 현재의 픽셀에 대한 이웃하는 영향을 더 잘 활용하는(그리고 비트플레인 어프로치와 일치하
여, 개량 패스에서 원래의 SPIHT 알고리즘에서 유래하는 비트로부터가 아니라, 변환된 이미지로부터 직접적으로 발
생되는 '자연적인' 관계를 유도하는) 본 방법은, 상기 관계가 인코딩되고 있는 비트에 실질적으로 관련될 때, 압축율을
향상시키고 그에 따라 코딩 효율을 향상시킨다.
그러나, 모든 시공간 트리 서브밴드의 소모적인 주사(exhaustive scanning)는 다음과 같은 문제점을 급격하게 유도
한다: 낮은 디코딩 비트율에서도, 큰 계산 부하가 관측되는데, 이것은 요즘의 비디오 어플리케이션의 요구사항과 상
반되는 것이다.
발명의 상세한 설명
따라서, 본 발명의 목적은 이 결점을 회피하는 인코딩 방법을 제공하는 것이 다.
이 때문에, 본 발명은 본원의 도입부에서 정의된 인코딩 방법으로서, 시공간 트리의 각 서브밴드에, 그 계수의 전체
상태에 관한 정보를 제공하기 위해, 부가적인 특정한 한 비트 플래그가 부가되고, 각 서브밴드의 부모-자손 의존성에
관한 상기 부가 정보는 하기의 결정을 위해 사용되는 것을 더 특징으로 인코딩 방법에 관한 것이다:
- 각 서브밴드는, 그 부가 플래그가, '온'으로 칭해지는, 두 가능한 값들 중 제 1 값을 가질 때, 처리되어야만 하고, 그
계수의 적어도 하나는 계수 플래그 '온'을 가지며;
- 각 서브밴드는, 그 부가 플래그가, '오프'로 칭해지는' 두 가능한 값들 중 제 2 값을 가질 때, 스킵되어야만 하고, 모
든 그 계수 플래그는 '오프'이다.
이렇게 제안된 기술적 해결책은, 특정 서브밴드가 이 플래그에 따른 임의의 다른 서브밴드에 관련되지 않는 것으로
나타나면, 그 인코딩/디코딩 처리가 스킵되어, 과중하고 불필요한 계산을 피하게 되도록, 각각의 시공간 서브밴드에
대해, 임의의 계산 이전에, 그 부모-자손 의존성을 부가하는 것을 가능하게 한다. 제시된 발명은 FSZ 출력 비트스트
림의 임의의 수정으로 귀결되지 않고 따라서 나중의 재구성된 비디오에서 어떠한 품질 열화도 나타나지 않는다.
이하, 본 발명이 첨부된 도면을 참조로 설명될 것이다.
도면의 간단한 설명
공개특허 10-2004-0068302
- 6 -
도 1은 시공간 방향 트리에서 3D의 경우의 부모-자손 의존성의 예를 도시하 는 도면.
도 2는 시공간 트리에서 서브밴드의 계층을 도시하는 도면.
도 3은 시공간 트리의 공간적으로 구동된 주사를 도시하는 도면.
도 4는 순서가 정해진 3D SPIHT에 의해 가능하게 되는 비트스트림 구조를 도시하는 도면.
도 5는 시공간 트리의 시간적으로 구동된 주사를 도시하는 도면.
도 6은 상기 주사를 통해 얻어지는 비트스트림의 구성을 도시하는 도면.
실시예
상기 설명된 바와 같이, FSZ 기술에서, 웨이블릿 분해로부터 유도되는 전체 시공간 트리는 비트플레인에 의해 완전히
주사된 비트플레인(또는 중요한 레벨)이고, 모든 부모-자손 의존성(도 1에 도시됨)은 제 1의 비트플레인 처리동안 확
립된다. 이 계층적 관계는 모든 나머지 비트플레인에 대해(인코더 및 디코더 양측에서, 인코더와 디코더 둘 다는 동일
한 순서를 엄격하게 고려하기 때문에 인코더와 디코더 사이에는 어떠한 차별도 만들어지지 않는다) 후속되는 서브밴
드 주사 순서를 결정한다. 상기 언급된 WO 01/84847에서 설명된 바와 같이, FSZ 알고리즘의 주요 단계는 다음과 같
다:
(A) 초기화 단계, 이 단계 동안 최저의 시공간 서브밴드 계수만이 주사 처리의 시작을 인에이블링하는 플래그에 의해
특징지워지고, 모든 다른 서브밴드들 계수는 0으로 초기화된다;
(B) 주사 단계, 이 단계 동안 시공간 트리의 완전 탐사가 상기 시공간 트리 에 형성된 부모-자손 의존성을 엄격하게
고려하는 순서로 각 비트플레인에 대해 수행된다.
이 철저한 주사(in-depth scanning)동안, 시공간 서브밴드 계수의 상태가 그들의 설명 플래그를 온 또는 오프함으로
써 가상적으로 변경된다. 시공간 트리의 주사는 완전히 소모적인 것이다: 모든 서브밴드는, 그 계수의 상태에 대한 어
떠한 사전 가정없이, 리뷰되는데, 이것은 각 서브밴드에 대해, 모든 계수들이 분석됨을 의미한다. 그러나, 상기 FSZ
기술을 상세히 검사하면, 네 개의 가능한 플래그(직접적인 자손의 중요하지 않은 세트에 대한 FS1==DIRECT_SET_I
NSIG, 직접적이지 않은 자손의 중요하지 않은 세트에 대한 FS2==INDIRECT_SET_INSIG, 중요한 픽셀에 대한 FP3
==SIG, 중요하지 않은 픽셀에 대한 FP4==INSIG)의 어느 것도 ON(0과 등가)이 아닌 특별한 경우에, 어떠한 정보도
비트스트림에서 출력되지 않고, 어떠한 계수 상태도 변경되지 않는다. 다시 말하면, 이러한 계수의 처리가 어떠한 부
가 정보도 가져오지 못하기 때문에 이것은 소용없게 된다. 이 계산적인 부하 오버헤드는 서브밴드가 이러한 계수만을
포함할 때 특히 중요하게 된다. 또한, 이 상황은, 최하의 것을 제외한 모든 서브밴드가 0으로 초기화되기 때문에, 제 1
의 비트플레인에 대해서 아주 빈번하다.
본 발명에 따르면, 각 서브밴드에 그 계수의 전체 상태를 나타내는 플래그(SCAN)를 부가하는 것이 제공된다. 온되면
(즉, 서브밴드의 적어도 하나의 계수가 0과는 상이한 플래그를 가지면), 이 플래그는 서브밴드의 처리를 허용한다. 오
프되면(즉, 모든 계수들 플래그가 0이면), 어떠한 비트도 출력되지 않을 것이고 어떠한 비트도 변경되지 않을 것이라
는 것을 알기 때문에, 서브밴드는 스킵된다. 원래의 FSZ 방법의 두 주요 단계를 고려하면, 본 발명에 따라, 최하의 시
공간 서브밴드(이 루트 서브밴드는 어떠한 경우에도 주사되어야만 한다)에 대해 ON으로 그리고 모든 다른 서브밴드
들에 대해 OFF로 SCNA 플래그를 초기화시키는 것이 제안된다. 루트 서브밴드 계수로부터 시작하여, 본 방법은 FSZ
에서 정의된 룰에 따라 자손의 플래그를 업데이트할 것이다. 이 때, 이들 자손 계수를 포함하는 서브밴드의 SCAN 플
래그는, (하위의 비트플레인에 대한) 또 다른 정렬 패스동안 이들이 분석될 것이기 때문에, ON으로 설정된다.
요약하면, 본 발명은 하기와 같은 수정된 FSZ 방법을 제공하는데, 원래의 FSZ 방법은 상기 문헌에서 설명되었으며,
부가된 부분은 이탤릭체로 표시된다:
1. 초기화:
- 플래그 FP4가 최하위의 시공간 서브밴드의 전 계수에 놓여지고;
- 플래그 FS1은, 상기 최하위의 시공간 서브밴드의 7/8의 계수에 놓여지고;
- 플래그 SCNA이 최하위 시공간 서브밴드에 대해 ON으로 놓여지고;
공개특허 10-2004-0068302
- 7 -
- 모든 다른 시공간 서브밴드에 대해 플래그 SCAN을 OFF로 놓는다.
2. MSL을 계산하고 출력한다.
3. n=MSL로부터 0으로, 시공간 트리의 완전 탐사(full exploration)를 행하고,각 서브밴드에 대해:
A) 플래그 SCAN이 OFF이면, 상기 서브밴드를 스킵하고 시공간 트리의 다음 서브밴드로 직행한다;
B)플래그 SCAN이 ON이면 , 시공간 트리의 각 계수(x,y,z)에 대해, 다음의 동작이 제공된다:
a) 세트 중요성:
1) 플래그 FS1이 '온'이면, 출력＝S n(D(x,y,z)).
S n(D(x,y,z))＝1이면:
- 각각의 에 대해서, 플래그 FP4를 두고;
- (x,y,z)로부터 플래그 FS1을 제거하고;
- 이면, 플래그 FS2를 두고;
- 각 를 포함하는 각 서브밴드에 대해 플래그 SCAN을 온으로 각각 둔다.
2) 플래그 FS2가 '온'이면, 출력=S n(L(x,y,z)).
S n(L(x,y,z))=1이면:
- 각각의 에 대해서, 플래그 FS1을 두고;
- (x,y,z)로부터 플래그 FS2를 제거하고;
- 각 를 포함하는 각 서브밴드에 대해 플래그 SCAN을 온으로 각 각 둔다.
b) 픽셀 중요성:
(1) 플래그 FP3이 온이면, 출력=(x,y,z)의 n번째 비트.
2) 플래그 FP4가 온이면, 출력=S n(x,y,z).
S n(x,y,z)=1이면:
플래그 FP3을 온으로 두고;
부호(x,y,z)를 출력하고;
플래그 FP4를 제거한다.
본 발명에 따른 방법을 구현하는 것에 의한 이점은, 마지막 출력 비트스트림의 어떠한 수정 없이도, FSZ 방법의 복잡
성이 아주 현저하게 감소한다는 것이다. 복잡성의 감소는, 인코딩/디코딩 비트율이 낮다는 것을 고려하면 아주 중요
한데, 여기서 가장 중요한 비트플레인만이 처리되고 많은 서브밴드는 임의의 부모-자손 의존성에 의해 다른 것에 아
직 연결되지 않았다, 즉, 많은 서브밴드가 OFF로 설정된 그들의 플래그(SCAN)를 여전히 가지며, 따라서 원래의 FSZ
알고리즘에서 수행된 것과는 대조적으로, 분석되지 않는다.
공개특허 10-2004-0068302
- 8 -
(57) 청구의 범위
청구항 1.
3-차원(3D) 웨이블릿 변환에 의해 분해되어 상기 변환의 분해 레벨들에 대응하는 소정 수의 연속하는 해상도 레벨들
을 가져오는 프레임들의 그룹들(GOF들)로 분할된 비디오 시퀀스의 압축을 위한 인코딩 방법으로서, 상기 방법은 각
GOF의 화상 요소들(픽셀들)의 원래의 세트로부터 계층 피라미드를 구성하는 변환 계수들을 이끌어내는 계층 서브밴
드 인코딩 처리에 기초하며, 루트가 상기 3D 웨이블릿 변환으로부터 유발된　근사 서브밴드(approximation subban
d)의 픽셀들로 형성되고 이들 픽셀의 각 자손들(offsprings)이 이들 루트 픽셀들에 의해 정의되는 화상 볼륨(volume)
에 대응하는 고차 서브밴드들의 픽셀들로 형성되는 시공간 방향 트리(spatio-temporal tree)는 상기 계층 피라미드
내부의 시공간 관계를 정의하며, 상기 3D 웨이블릿 변환의 초기 서브밴드 구조는 상기 시공간 트리에 형성된 부모-자
손 의존성들을 고려하는 순서로 상기 서브밴드를 차례로 주사(scanning)함으로써 보존되고, 특정한 일 비트 플래그가
상기 계수들의 최상위 비트들의 순차 전송을 고려하여 상기 시공간 트리의 각 계수에 부가되며, 이들 플래그들은 이
들 중 적어도 하나가 픽셀들의 세트 상태를 설명하고 적어도 다른 하나가 단일 픽셀의 상태를 설명하도록 하는, 상기
인코딩 방법에 있어서,
상기 인코딩 방법은 그 외에도, 특정한 한 비트 플래그가 상기 시공간 트리의 각 서브밴드에 부가되어 상기 계수들의
전체 상태에 관한 정보를 제공하고, 각 서브밴드의 부모-자손 의존성들에 관한 상기 부가 정보는 다음의 결정, 즉
- 각 서브밴드는 상기 부가 플래그가 두 가능한 값들 중 '온'이라 불리는 제 1 값을 가질 때 처리되어야 하고, 상기 계
수들의 적어도 하나는 계수 플래그 '온'을 가지며;
- 각 서브밴드는 상기 부가 플래그가 두 가능한 값들 중 '오프'라 불리는 제 2 값을 가질 때 스킵되어야 하고, 모든 상
기 계수 플래그들은 '오프'인 결정을 위해 사용되는 것을 더 특징으로 하는, 인코딩 방법.
청구항 2.
제 1 항에 있어서,
두 플래그들이 픽셀들의 세트 상태를 설명하며, 상기 시공간 트리의 각 계수(x,y,z)에 대해, D(x,y,z)가 여전히 중요하
지 않으면(insignificant) FS1이고, L(x,y,z)가 여전히 중요하지 않으면 FS2이며,
상기 D(x,y,z)는 노드(x,y,z)의 모든 자손들의 좌표 세트이고 L(x,y,z) = D(x,y,z) - O(x,y,z)이고, 상기 O(x,y,z)는 상
기 노드(x,y,z)의 직계 자손(direct offspring)의 좌표 세트이며,
두 플래그들이 단일 픽셀의 상태를 설명하며, 현재의 픽셀이 중요하면 FP3이고, 중요하지 않거나 또는 그 중요성(sig
nificance)이 분석되면 FP4이고,
상기 인코딩 방법은, 상기 플래그 FP4가 최하위 시공간 서브밴드의 모든 계수들로 놓여지는(put) 초기화 단계 이후,
상기 플래그 FS1은 상기 최하위 시공간 서브밴드의 7/8 계수들로 놓여지고, 상기 부가 플래그는 상기 최하위 시공간
서브밴드에 대한 두 값들 중 제 1 값('온')으로 놓여지고, 모든 다른 서브밴드들에 대 해 제 2 값('오프')으로 놓여지며,
최대 최상위 레벨(MSL : maximum significance level)이 계산되며, 상기 주사 순서에 따라 구현되는 상기 시공간 트
리의 조사(exploration)는 비트플레인 n=MSL에서 아래로 0까지로부터, 상기 시공간 트리의 전체 조사를 행하는 단
계를 포함하고,각 서브밴드에 대해:
A) 상기 부가 플래그가 상기 값들 중 제 2 값을 가지면, 상기 서브밴드를 스킵하고 상기 시공간 트리의 다음 서브밴드
로 직행하고;
B) 상기 부가 플래그가 상기 값들 중 제 1 값을 가지면,상기 시공간 트리의 각 계수(x,y,z)에 대해, 다음의 동작들,
즉
a) 세트 중요성:
1) 플래그 FS1이 온이면, 출력=S n(D(x,y,z))이고.
S n(D(x,y,z))==1이면:
- 각 에 대해서, 플래그 FP4를 두고;
공개특허 10-2004-0068302
- 9 -
- (x,y,z)로부터 플래그 FS1을 제거하고;
- 이면, 플래그 FS2를 두며;
- 상기 부가 플래그를 각 를 포함하는 각 서브밴드에 대한 상기 값들 중 제1 값으로 각각두
고,
2) 플래그 FS2가 온이면, 출력=S n(L(x,y,z))이고,
S n(L(x,y,z))==1이면:
- 각 에 대해서, 플래그 FS1을 두고;
- (x,y,z)로부터 플래그 FS2를 제거하고;
- 상기 부가 플래그를, 각 를 포함하는 각 서브밴드에 대한 상기 값들 중 제 1 값으로 각각 두고
,
b) 픽셀 중요성:
1) 플래그 FP3이 온이면, 출력=(x,y,z)의 n번째 비트이고,
2) 플래그 FP4가 온이면, 출력=S n(x,y,z)이고,
S n(x,y,z)==1이면:
- 플래그 FP3을 온으로 두고;
- 부호(x,y,z)를 출력하고;
- 플래그 FP4를 제거하는 동작들이 제공되는 것을 더 특징으로 하는, 인코딩 방법.
도면
공개특허 10-2004-0068302
- 10 -
도면1
도면2
공개특허 10-2004-0068302
- 11 -
도면3
도면4
공개특허 10-2004-0068302
- 12 -
도면5
도면6