KR100867995B1

KR100867995B1 - 동영상 데이터 인코딩/디코딩 방법 및 그 장치

Info

Publication number: KR100867995B1
Application number: KR1020070001386A
Authority: KR
Inventors: 정세윤; 서정일; 김규헌; 강경옥; 홍진우; 이영렬; 김대연; 김동균; 오승준; 심동규; 안창범
Original assignee: 한국전자통신연구원; 광운대학교 산학협력단
Priority date: 2006-01-07
Filing date: 2007-01-05
Publication date: 2008-11-10
Also published as: KR20070074487A; US20090067503A1

Abstract

본 발명은 동영상 데이터 인코딩/디코딩 방법 및 그 장치를 개시한다.

본 발명의 동도을 인코더와 디코더에 포함시켜, 인코더에서 입력 동영상에 대한 벡터와 이 코드북상의 벡터들 중 가장 유사한 벡터의 인덱스만을 부호화하고, 디코더에서 이를 복호화하는 것을 특징으로 한다. 따라서 압축률을 높이고 디코더의 복잡도를 감소시킬 수 있다.

잔여 변환 계수, 인덱스, 코드북, 벡터, 최적 벡터 탐색

Description

동영상 데이터 인코딩/디코딩 방법 및 그 장치{Method and apparatus for video data encoding and decoding}

도 1은 본 발명의 바람직한 일실시예에 따른 단일 경로 동영상 데이터 인코딩 장치의 구성을 나타낸 블록도이다.

도 2는 본 발명의 바람직한 일실시예에 따른 코드북 생성부의 구성을 나타낸 블록도이다.

도 3은 본 발명의 바람직한 일실시예에 따른 최적 벡터 탐색부에서 잔여 변환 계수와 가장 유사한 벡터를 코드북에서 탐색하는 과정을 도시한 도면이다.

도 4는 본 발명의 바람직한 일실시예에 따른 프레임별 코드북 재정렬 과정을 나타낸 도면이다.

도 5는 본 발명의 바람직한 일실시예에 따른 이중 경로 동영상 데이터 인코딩 장치의 구성을 나타낸 블록도이다.

도 6은 본 발명의 바람직한 일실시예에 따른 단일 경로 동영상 데이터 디코딩 장치의 구성을 나타낸 블록도이다.

도 7은 본 발명의 바람직한 일실시예에 따른 이중 경로 동영상 데이터 디코딩 장치의 구성을 나타낸 블록도이다.

도 8은 본 발명의 바람직한 일실시예에 따른 코드북 생성 및 재정렬 과정을 설명하는 흐름도이다.

도 9는 본 발명의 바람직한 일실시예에 따른 동영상 데이터의 잔여 변환 계수 인코딩 방법을 설명하는 흐름도이다.

도 10은 본 발명의 바람직한 일실시예에 따른 동영상 잔여 변환 계수 데이터 디코딩 방법을 설명하는 흐름도이다.

도 11은 본 발명의 바람직한 일실시예에 따른 동영상 데이터 인코딩 방법의 실험 결과를 나타낸 도면이다.

본 발명은 동영상 데이터의 인코딩/디코딩 방법 및 그 장치에 관한 것으로, 보다 상세하게는, DCT(Discrete Cosine Transform) 후 양자화된 잔여 변환 계수의 부호화시에, 코드북에 존재하는 벡터들 중 잔여 변환 계수와 가장 유사한 벡터의 인덱스만을 부호화하여 압축률을 높이고 디코더의 복잡도를 줄인 데이터 인코딩/디코딩 방법 및 그 장치에 관한 것이다.

기존의 영상 신호의 압축 표준 중 하나인 H.264/MPEG-4 AVC(Advanced Video Coding)는 다중 참조 움직임 보상(multiple reference motion compensation), 루프 필터링(loop filtering), 가변 블록 크기 움직임 보상(variable block size motion compensation), CABAC과 같은 엔트로피 코딩 등 압축 효율을 증가시키기 위한 다양한 기술을 채택하고 있다.

H.264 표준안에 따르면, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 DCT와 양자화한 결과에 의한 잔여 변환 계수를 최대한 짧은 1차원의 배열로 나타내기 위해 지그재그 스캔(zig-zag scan)과 Run-Level 방법을 수행하여 출력된 심볼을 엔트로피 부호기에서 최종적으로 부호화한다.

일반적으로 4x4 블록 내의 각 점에서 0 이 아닌 잔여 변환 계수가 존재할 확률은 좌측 상단(DC)이 가장 높고 대체적으로 수평과 수직 방향으로 대칭적인 분포를 갖는다. 이런 특성을 이용하기 위해 DC 잔여 변환 계수로부터 시작하는 지그재그 스캔 순서를 사용하여 1차원 배열로 표현한다. 이렇게 재배열된 잔여 변환 계수들은 많은 수의 0 값들은 포함하고 있어 Run-Level 부호화를 이용하여 보다 간결하게 표현한다. 여기서 Run은 0 이 아닌 잔여 변환 계수의 앞에 있는 0의 개수를 의미하고, Level은 0이 아닌 잔여 변환 계수의 크기를 의미한다. 이렇게 Run-Level 부호화에 의해 출력된 각각의 Run과 Level의 쌍은 엔트로피 부호기에 의해 독립된 심볼로 부호화한다.

종래 기술에 따르면, 예측 차 신호 블록 내의 화소간 상관성이 높을 경우 인코딩에 적은 비트가 필요하게 되고 상관성을 갖지 않는 예측 차 신호의 인코딩에는 많은 비트가 필요하게 된다. 또한 디코더에서 역양자화 및 역DCT 과정을 거쳐야하므로 계산 복잡도가 증가한다.

본 발명은 DCT 또는 다른 변환(transform) 후 양자화된 잔여 변환 계수의 부호화 시에, 미리 다른 영상들로부터 학습(training)을 통하여 구성된 잔여 변환 계 수의 코드북에서, 코드북의 각 인덱스(index)에 해당되는 Nx1 벡터들 중 잔여 변환 계수와 가장 유사한 벡터의 인덱스만을 부호화하여 압축률을 높이는 동영상 데이터 인코딩 방법 및 그 장치를 제공하는 것을 목적으로 한다.

본 발명은 인덱스에 대응하는 역양자화 및 역DCT된 잔여 계수의 값을 미리 테이블화하여 저장하여 수신한 인덱스에 대응하는 잔여 계수를 테이블 룩업으로 찾도록 함으로써 디코더의 복잡도를 줄이는 디코딩 방법 및 그 장치를 제공하는 것을 목적으로 한다.

본 발명의 다른 목적 및 장점들은 하기의 설명에 의해서 이해될 수 있으며, 본 발명의 실시예에 의해 보다 분명하게 알게 될 것이다. 또한, 본 발명의 목적 및 장점들은 특허 청구 범위에 나타낸 수단 및 그 조합에 의해 실현될 수 있음을 쉽게 알 수 있을 것이다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 일 실시예에 따른 동영상 데이터 인코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 단계; 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 단계; 및 상기 탐색된 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 인코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블 록을 변환 및 양자화하여 잔여 변환 계수를 생성하는 단계; 및 상기 잔여 변환 계수 블록을 엔트로피 부호화하기 위한 경로를 선택하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 인코딩 방법은, 잔여 계수 각각에 대응하는 벡터들을 생성하는 단계; 및 상기 벡터들의 공간 근접도를 기초로 상기 벡터들을 그룹화하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 디코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수 각각에 대응하고 인덱스가 할당된 벡터들을 수신하는 단계; 및 상기 벡터들을 엔트로피 복호화하고 상기 인덱스와 매칭하여 저장하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 디코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터에 매칭된 인덱스 정보를 포함한 비트스트림에서 상기 인덱스를 추출하는 단계; 및 상기 추출된 인덱스를 기초로 상기 잔여 블록을 복원하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 디코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 복호화하는 제1 경로 및 상기 잔여 변환 계수에 대응하는 인덱스를 복호화하는 제2 경로의 경로 정보가 포함된 비트스트림으로부터 상기 경로 정보를 추출하는 단계; 및 상기 제1 경로가 선택된 경우, 상기 잔여 변환 계수를 엔트로피 복호화, 역양자화 및 역변환하여 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 복원하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수 블록에 대응하는 벡터를 생성하는 단계; 샘플 영상의 잔여 변환 계수 블록들에 대응하는 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 단계; 상기 탐색된 참조 벡터에 대응하는 인덱스를 엔트로피 부호화하는 단계; 상기 참조 벡터들 중에서 상기 인덱스에 대응하는 벡터를 역탐색하는 단계; 및 상기 역탐색된 벡터를 복원한 상기 잔여 변환 계수 블록을 역양자화 및 역변환하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 동영상 데이터 코딩 방법은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 엔트로피 부호화하기 위한 경로를 선택하는 단계; 상기 선택된 경로 정보를 부호화하는 단계; 및 상기 경로 정보를 기초로 상기 부호화된 잔여 변환 계수를 복호화하는 단계;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 인코더는, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 양자화 변환부; 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 최적 벡터 탐색부; 및 상기 탐색된 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 엔트로피 부호화부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 인코더는, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화하여 잔여 변환 계수를 생성하는 양자화 변환부; 및 상기 잔여 변환 계수를 엔트로피 부호화하기 위한 경로를 선택하는 경로 선택부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 인코더는, 잔여 계수 각각에 대응하는 벡터들을 생성하는 벡터 생성부; 및 상기 벡터들의 공간 근접도를 기초로 상기 벡터들을 그룹화하는 그룹화부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 디코더는, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수 각각에 대응하고 인덱스가 할당된 벡터들을 수신하여 엔트로피 복호화하는 엔트로피 복호화부; 및 상기 벡터들을 상기 인덱스와 매칭하여 저장하는 저장부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 디코더는, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터에 매칭된 인덱스 정보를 포함한 비트스트림에 서 상기 인덱스를 추출하는 엔트로피 복호화부; 및 상기 추출된 인덱스를 기초로 상기 잔여 블록을 복원하는 복원부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 코덱은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수 블록에 대응하는 벡터를 생성하는 양자화 변환부; 샘플 영상의 잔여 변환 계수 블록들에 대응하는 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 최적 벡터 탐색부; 상기 탐색된 참조 벡터에 대응하는 인덱스를 엔트로피 부호화하는 엔트로피 부호화부; 상기 참조 벡터들 중에서 상기 인덱스에 대응하는 벡터를 역탐색하는 역최적 벡터 탐색부; 및 상기 역탐색된 벡터를 복원한 상기 잔여 변환 계수 블록을 역양자화 및 역변환하는 역양자화 변환부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위한 본 발명의 바람직한 다른 실시예에 따른 코덱은, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 엔트로피 부호화하기 위한 경로를 선택하는 경로 선택부; 상기 선택된 경로 정보를 부호화하는 엔트로피 부호화부; 및 상기 경로 정보를 기초로 상기 부호화된 잔여 변환 계수를 복호화하는 복호화부;를 포함하는 것을 특징으로 한다.

상기의 기술적 과제를 해결하기 위해 본 발명은 본 발명의 동영상 데이터 인코딩, 디코딩 및 코딩 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는 것을 특징으로 한다.

이하 본 발명의 바람직한 실시예가 첨부된 도면들을 참조하여 설명될 것이다. 도면들 중 동일한 구성요소들에 대해서는 비록 다른 도면상에 표시되더라도 가능한 한 동일한 참조번호들 및 부호들로 나타내고 있음에 유의해야 한다. 하기에서 본 발명을 설명함에 있어, 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다.

도 1을 참조하면, 본 발명에 따른 동영상 부호화 단일 경로 장치(100)는 움직임 추정부(102), 움직임 보상부(104), 인트라 예측부(106), 감산부(107), 변환/양자화부(108), 최적 벡터 탐색부(110), 엔트로피 부호화부(112), 역최적 벡터 탐색부(114), 역양자화/역변환부(116), 가산부(117), 프레임 메모리(118) 및 필터(120)를 포함한다.

움직임 추정부(102)는 상기 프레임 메모리(118)에 저장된 참조 프레임의 영상에서 현재 매크로 블록과 가장 유사한 영역을 독출하는 움직임 추정을 수행한다. 즉, 참조 프레임에서 현재 매크로블록의 위치를 중심으로 하는 소정 영역을 탐색하여, 탐색 영역 내에서 현재 매크로블록과의 차이가 최소가 되는 영역을 가장 유사한 영역으로 선택한다. 또한, 상기 가장 유사한 영역과 현재 매크로 블록과의 공간상의 위치 차이를 움직임 벡터 형태로 출력한다.

움직임 보상부(104)는 상기 출력된 움직임 벡터를 이용하여 상기 프레임 메 모리(118)에 저장된 참조 프레임의 영상에서 현재 매크로 블록과 가장 유사한 영역을 독출하여 인터 예측된 예측 블록을 생성한다. 이와 같이, 상기 움직임 추정부(102) 및 움직임 보상부(104)는 상호 작용하여 인터 예측을 수행하는 인터 예측부로서 동작한다.

상기 인터 예측 과정은 16x16 크기의 매크로 블록뿐만 아니라, 16x8, 8x16, 8x8, 8x4, 4x8 및 4x4 크기의 블록에 대하여 수행될 수 있다.

인트라 예측부(106)는 현재 프레임 내의 상관 관계를 이용하여 인트라 예측을 수행한다.

감산부(107)는 인터 예측이 수행되어 현재 부호화할 블록에 대응되는 예측 블록이 형성되면, 상기 현재 블록과 상기 예측 블록과의 차이를 계산하여 예측 차 블록인 잔여 블록을 출력한다.

변환/양자화부(양자화 변환부)(108)는 상기 인터 예측 과정에서 출력된 예측 차 블록을 DCT 및 양자화 과정을 거쳐 잔여 변환 계수 블록으로 출력하고 상기 잔여 변환 계수 블록을 지그재그 스캔과 Run-Level 부호화에 의해 1차원의 배열로 재배열한다.

최적 벡터 탐색부(110)는 변환/양자화의 결과로 출력되는 상기 잔여 변환 계수 블록의 1차원 배열인 벡터에 대해 코드북 내에서 가장 유사한 벡터를 찾아 해당 벡터에 매칭된 인덱스를 검출한다. 이에 대한 상세한 설명은 도 3을 참조하여 후술하겠다.

엔트로피 부호화부(112)는 상기 잔여 변환 계수 블록의 벡터에 대응하는 매 칭된 인덱스를 VLC(Variable Length Coding)로 부호화하여 최종적인 비트스트림으로 출력한다.

역최적 벡터 탐색부(114)는 상기 매칭된 인덱스에 대응하는 벡터를 코드북에서 역으로 탐색하여 해당 벡터를 선택한다.

역양자화/역변환부(116)(이하 역양자화 변환부)는 선택된 상기 해당 벡터를 역양자화 및 역변환하여 예측 차 블록인 잔여 블록을 출력한다.

가산부(117)에서는 상기 잔여 블록과 인터 예측 또는 인트라 예측된 블록과 가산하고, 필터(120)를 통해 영상이 복원된다.

도 2는 본 발명의 바람직한 일실시예에 따른 코드북 생성부의 구성을 나타낸 블록도로서, 벡터 양자화(Vector Quantization)를 이용하여 코드북을 생성한다.

도 2를 참조하면, 코드북 생성부(200)는 벡터 생성부(210), 그룹화부(220), 인덱스 할당부(230) 및 저장부(240)를 포함한다.

벡터 생성부(210)는 잔여 계수 각각에 대응하는 벡터들을 생성한다. 샘플로서 실제 영상들의 DCT와 양자화 후 출력된 수많은 4x4 블록 단위의 잔여 변환 계수들을 공간상의 16x1 벡터로 재정의하는 것이다.

상기 잔여 계수는, 움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수, 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중의 어느 하나일 수 있다. 이하 본 발명에서는 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수에 대해 설명하겠으며. 그 외 잔여 계수에도 동일하게 적용할 수 있을 것이다.

그룹화부(220)는 잔여 변환 계수들에 대해 군집분석 알고리즘을 적용하여 군집화(Clustering)를 수행한다. 군집화는 상기 재정의된 각 벡터들의 16차원 공간상의 위치에 의거하여 근접한 공간에 위치하는 객체끼리 그룹핑하여 코드북을 생성하는 과정이다. 예로서, K-means 알고리즘을 사용할 수 있다.

본 발명의 바람직한 일 실시예에 따라 상기 그룹핑은 MC-Transform(Motion Compensated-Transform) 코더의 잔여 계수(Residual data) 또는 트랜스폼된 신호의 양자화 후 잔여 신호 또는 트랜스폼된 잔여 신호(Transformed Residual Signal)에 대한 군집화(Clustering)를 포함한다.

또한, 잔여 변환 계수들은 양자화 파라미터(Quantization parameter)에 상당히 의존적인 성향을 띠므로 양자화 파리미터에 따라 적절한 군집수를 분포하는 것이 바람직하다. 예로서, 양자화 파라미터의 범위를 소정의 범위로 나누고 각각의 범위에 알맞은 군집수로 군집화할 수 있다.

군집화된 코드북은 후에 할당될 인덱스의 수(M)와 잔여 블록의 차원(N)에 의해 벡터들을 M×N 테이블화된다.

저장부(240)는 최종적으로 생성된 코드북을 초기 코드북(initial codebook)으로서 저장한다. 이후 코드북이 재정렬되는 경우, 재정렬된 벡터에 대한 코드북이 저장된다.

인덱스 할당부(230)는 상기 코드북 내의 벡터들에 인덱스 및 상기 인덱스의 이진화 값인 빈 스트링(Bin string)을 할당한다. 인덱스를 엔트로피 기법인 CABAC으로 부호화 하기 위해서는 인덱스의 이진화(Binarization) 과정이 필요하다. 이 과정은 입력된 심볼을 0과 1의 조합의 빈 스트링(Bin string)으로 표현하는 과정이다. 빈 스트링(Bin string)의 길이가 짧을수록 해당 심볼은 최종적으로 짧은 비트로 부호화된다. 따라서 인덱스를 효율적으로 이진화(Binarization) 하기 위해 군집화 과정이 끝난 후 군집 밀도가 높은 순으로 벡터를 정렬하여 군집 밀도가 높은 벡터일수록 짧은 빈 스트링을 갖도록 하는 것이 바람직하다. 일 예로서, 이진화 방법으로 Unary/3rd order Exponential Golomb 코딩을 사용할 수 있다. 본 발명에서는 Unary를 상위 4개의 벡터에 대해서 사용하였다.

표 1은 군집화된 각 16x1 벡터와 상기 벡터에 매칭시켜 할당한 해당 인덱스를 상기 방법으로 이진화한 후 결정된 빈 스트링을 나타낸 코드북의 예이다. 예외적으로, 잔여 변환 계수가 모두 0이 나오는 경우가 상당히 많아 이 경우와 그 외의 경우를 1비트(bit)의 플래그로 구분하여 부호화 효율을 높였다.

도 3은 본 발명의 바람직한 일실시예에 따른 최적 벡터 탐색부에서 잔여 변환 계수와 가장 유사한 벡터를 코드북에서 탐색하는 과정을 도시한다.

도 3을 참조하면, 4번 인덱스에 대응하는 벡터가 선택되었음을 알 수 있다. 가장 유사한 벡터의 결정은 수학식 1과 같이 유클리언 디스턴스(Euclean Distance) 식을 이용한다.

수학식 1을 이용하여 상기 잔여 변환 계수와 상기 코드북의 모든 벡터와의 거리(Distance)를 구한 후, 가장 작은 값을 갖는 벡터를 최적의 벡터로 결정한다. 만약 거리가 0이라면 다음 벡터와의 거리를 구하지 않고 해당 벡터를 최적의 벡터로 결정한다.

여기서 C는 코드북 내의 임의의 16x1 벡터를 나타내며, R은 잔여 변환 계수를 나타낸다. Distance는 코드북 내의 임의의 벡터와 잔여 변환 계수간의 유클리언 디스턴스(Euclean Distance)를 나타낸다.

최소 거리를 갖는 벡터가 결정되면 결정된 벡터의 인덱스는 엔트로피 부호화부로 입력되어 부호화된다.

도 4를 참조하면, 프레임별 코드북 재정렬 과정은 매 프레임을 압축하면서 각 인덱스(index)에 대응되는 잔여 변환 계수의 선택 횟수를 저장하여 한 프레임의 부호화가 종료되었을 때, 코드북의 백터를 선택 횟수가 가장 많은 순으로 정렬하여 시간과 영상에 적응적으로 인덱스를 부호화하는데 더 짧은 비트를 소모하게 한다. 즉, 인덱스(index)가 커지면 빈 스트링(bin string)의 길이가 커지기 때문에 부호기에서 바로 전 영상에서 각 인덱스의 확률 분포를 계산하여 현재 영상의 프레임에서 그 확률을 이용하여 확률이 가장 높았던 인덱스의 번호에 기초하여 벡터들을 내림차순으로 재정렬함으로써 상위부터 인덱스 0부터 재시작하도록 테이블을 재변환 (Table reordering)을 해주는 과정이다.

이 코드북 재정렬 과정은 동일한 코드북을 저장하고 있는 디코더에서도 인코 더와 마찬가지로 수행된다. 따라서 부가적인 파라미터의 전송이 전혀 필요 없게 되는 장점이 있다.

그러나 이 방법은 디코더에서도 한 프레임 단위로 코드북의 재정렬(reordering)이 필요하여 계산 복잡도가 높아지는 단점이 있다. 이러한 계산의 복잡도를 줄이기 위해서 코드북의 약 상위 20개의 인덱스만 정렬한다. 이 방법은 기존 방법과 성능의 향상을 가져올 수 있는 장점이 있다.

코드북(410)은 정렬 전의 코드북으로, 한 프레임이 부호화되는 경우 이용된 인덱스들의 횟수가 결정된 결과를 보여주고 있다. 여기서 횟수(430)는 코드북에서 이용된 벡터의 횟수를 나타낸다.

코드북(420)은 상기 횟수(430)의 크기에 따라 재정렬되어진 결과이다. 이용 횟수가 많은 인덱스 3번 벡터와 그보다 이용 횟수가 적은 인덱스 2번 벡터의 위치가 바뀌면서 이용 횟수가 많은 인덱스 3번 벡터가 더 짧은 빈 스트링(bin string)을 갖게 된다. 예외적으로 잔여 변환 계수가 모두 0인 벡터는 대부분의 모든 프레임에서 이용되는 횟수가 가장 많기 때문에 코드북 재정렬 대상에서 제외되며 항상 코드북의 인덱스 0에 위치한다(미도시).

도 5를 참조하면, 동영상 부호화 이중 경로 장치(500)는 동영상 부호화 단일 경로 장치(100)와 유사한 구조를 가지고 있으나, 변환/양자화부(510)에서 DCT 및 양자화 과정으로부터 생성된 잔여 변환 계수 블록이 2개의 분기점(경로 1 및 경로 2)으로 나누어 다음 과정이 진행된다는 점에 차이를 갖는다.

상기 동영상 부호화 이중 경로 장치(500)는 변환/양자화부(510), 최적 벡터 탐색부(520), 엔트로피 부호화부(530), 역최적 벡터 탐색부(540), 역양자화/역변환부(550), 가산부(560) 및 경로 선택부(570)를 포함한다. 여기서 동영상 부호화 단일 경로 장치(100)와 동일한 기능을 수행하는 구성에 대한 설명은 생략하겠다.

경로 선택부(570)는 잔여 변환 계수를 엔트로피 부호화하기 위한 경로를 선택하여 해당 경로로 진행하게 한다.

경로 1은 상기 동영상 부호화 단일 경로 장치(100)와 동일한 방법으로 상기 잔여 변환 계수 블록의 1차원 배열인 16x1 벡터를 최적 벡터 탐색부(520)를 통해 코드북 내에서 가장 유사한 벡터를 찾아 해당 벡터의 인덱스를 엔트로피 부호화부(530)를 통해 엔트로피 부호화한다.

경로 2는 상기 잔여 변화 계수 블록이 상기 최적 벡터 탐색부(520)의 코드북 을 참조하여 해당 인덱스를 선택한 후 변환하는 과정 없이, 원 데이터 그대로 엔트로피 부호화부(530)를 통해 기존의 표준화된 압축 방법으로 부호화한다.

경로를 선택하는 방법은 경로 1을 이용하였을 때의 레이트-디스토션 코스트(RDcost; Rate-Distortion cost)를 경로 2를 이용하였을 때의 RDcost와 비교하여 더 작은 RDcost를 발생시키는 방법을 현재 매크로블록의 잔여 변환 계수의 부호화 과정에 이용한다.

또한 매크로블록 당 1 비트(bit)의 경로 표현을 위한 정보인 플래그 비트(flag bit)를 디코더에 보내어 어느 경로를 사용하였는지 알 수 있도록 하여 해 당 경로에 따라 복호화할 수 있도록 한다.

RDcost는 라그랑지안 비용 함수(Lagrangian cost function)을 이용하여 수학식 2와 같이 계산되어진다. Rates는 잔여 변환 계수의 부호화시 소모되는 비트량이고, Distortion은 SSD(Sum of Square Difference)를 이용하여, 원본 매크로 블록과 복원된 매크로 블록의 왜곡 정도를 나타낸다. B(k,l)은 원본 매크로 블록의 (k,l)번째 픽셀 값을 나타내고, B'(k,l)은 복원된 매크로 블록의 (k,l)번째 픽셀 값을 나타낸다. λ는 양자화 계수(Quantization Parameter)에 의해 결정되는 상수이다.

경로 1로 부호화된 벡터의 인덱스는 역 최적 벡터 탐색부(540)에 의해 대응하는 벡터를 찾아 역변환/역양자화부(550)에서 역양자화/역변환 과정을 거친 후 가산부(560)에서 인터 예측 블록과 가산하여 영상을 복원한다.

경로 2로 부호화된 잔여 변환 계수는 역변환/역양자화(550)에서 역양자화 및 역변환 과정을 거친 후 상기 가산부(560)에서 인터 예측 블록과 가산하여 영상을 복원한다.

도 6은 본 발명의 바람직한 일실시예에 따른 단일 경로 동영상 데이터 디코 딩 장치의 구성을 나타낸 블록도이다.

도 6을 참조하면, 복호화 단일 경로 장치(600)는 엔트로피 복호화부(610), 역최적 벡터 탐색부(620), 역양자화/역변화부(630), 가산부(640), 인트라 예측부(650) 및 움직임 보상부(660)를 포함한다.

엔트로피 복호화부(610)는 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터에 매칭된 인덱스 정보를 포함한 비트스트림을 수신한 경우, 비트스트림을 엔트로피 복호화하여 인덱스를 출력한다.

역최적 벡터 탐색부(620)는 엔트로피 복호화부로부터 출력된 인덱스에 대응되는 벡터를 기 저장하고 있는 코드북에서 찾아 해당 벡터로부터 잔여 변환 계수 블록을 복원한다.

상기 코드북은 미리 인코더로부터 다수의 샘플 영상에 대한 잔여 변환 계수의 벡터들을 군집화한 MxN 테이블의 코드북을 수신하여 복호화한 후 저장한 테이블이다. 여기서, M은 인덱스의 수이고, N은 잔여 변환 계수의 차원(dimension)이다. 본 발명은 디코더의 복잡도를 줄이기 위해 상기 코드북의 각 인덱스에 매칭하는 잔여 변환 계수 벡터를 미리 역양자화 및 역변환하여 잔여 계수를 생성해 놓을 수도 있다. 따라서 이 경우 수신한 인덱스에 대응하는 잔여 계수를 역변환 및 역양자화 과정 없이 직접 테이블 룩업(Lookup)(참조)에 의하여 가져올 수 있다.

또한 인코더에서와 마찬가지로 프레임 단위로 수신한 인덱스의 선택 횟수에 의한 확률을 계산하고, 확률 분포가 높은 순으로 코드북을 재정렬하고 인덱스를 재 할당한다.

역영자화/역변환부(630)는 상기 복원된 잔여 변환 계수 블록을 역양자화 및 역변환을 수행하여 잔여 계수 블록을 생성한다.

움직임 보상부(660)는 예측 블록을 생성하고, 생성된 예측 블록은 상기 가산부(640)를 통해 상기 잔여 계수 블록과 더해져서 영상이 복원된다.

도 7은 본 발명의 바람직한 일실시예에 따른 이중 경로 동영상 데이터 디코딩 장치의 구성을 나타낸 블록도이다. 여기서 전술된 동영상 복호화 단일 경로 장치(600)와 동일한 기능을 수행하는 구성에 대한 설명은 생략하겠다.

도 7을 참조하면, 동영상 복호화 이중 경로 장치(700)는 엔트로피 복호화부(710), 역최적 벡터 탐색부(720), 역양자화부/역변환부(730) 및 가산부(760)를 포함한다.

엔트로피 복호화부(710)는 수신한 비트스트림에서 경로 정보를 추출한다. 비트스트림 내의 1 비트의 경로 표현을 위한 플래그 비트가 디코딩되어 해당 비트에 따라 경로가 선택적으로 바뀌게 된다.

상기 엔트로피 복호화부(710)는 경로 1이 선택된 경우 상기 복호화 단일 경로 장치(600)와 동일한 방법으로 비트스트림을 엔트로피 복호화하여 인덱스를 추출한다. 경로 2가 선택된 경우 잔여 변환 계수의 블록을 엔트로피 복호화한다.

역최적 벡터 탐색부(720)는 추출된 인덱스에 대응하는 벡터를 코드북을 탐색하여 선택한다.

역양자화/역변환부(730)는 상기 선택된 벡터에 대응하는 잔여 변환 계수 블 록 및 경로 2에서의 잔여 변환 계수 블록에 대해 역양자화 및 역변환을 수행하여 잔여 계수 블록을 생성한다.

움직임 보상부(780)는 예측 블록을 생성하고, 생성된 예측 블록은 가산부(760)에 의해 경로 1이나 2를 통해 출력된 잔여 계수 블록과 더해져서 영상이 복원된다.

도 8을 참조하면, 코드북 생성 과정은 먼저, 샘플 영상에 대해 움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수, 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중의 어느 하나의 잔여 계수에 대응하는 벡터를 생성한다(S810).

다음으로 상기 벡터들의 공간 근접도를 기초로 그룹화한 코드북을 저장한다(S820). 코드북은 인덱스의 수(M)와 상기 잔여 블록의 차원(N)에 의해 벡터들을 M×N 테이블화한 것이다.

그룹화된 벡터들에는 인덱스 및 인덱스의 이진화 값인 빈 스트링을 할당한다(S830).

최초 인덱스 및 빈 스트링이 할당된 초기 코드북은 입력 동영상의 프레임마다 코드북에서 선택된 인덱스의 선택 횟수가 계산되어, 프레임 당 확률 분포에 따라 코드북의 벡터들이 내림차순으로 재정렬되고 인덱스도 재할당된다(S840).

도 9는 본 발명의 바람직한 일실시예에 따른 동영상 데이터의 잔여 변환 계 수 인코딩 방법을 설명하는 흐름도이다.

도 9를 참조하면, 입력되는 동영상 데이터의 현재 블록과 예측 블록의 차에 해당하는 잔여 블록은 변환/양자화부에 의해 변환 및 양자화되어 잔여 변환 계수에 대응하는 1차원의 배열인 벡터가 생성된다(S910).

최적 벡터 탐색부는 기 저장된 참조 벡터들이 테이블화된 코드북으로부터 상기 벡터와 가장 유사한 최적 벡터를 탐색하여 선택한다(S920).

다음으로 선택된 참조 벡터에 매칭된 인덱스를 엔트로피 부호화부가 엔트로피 부호화하여 최종 비트스트림을 생성한다(S930).

한편 부호화할 벡터의 최적 벡터 탐색 및 인덱스 부호화하는 경우와 인덱스 선택 과정 없이 잔여 변환 계수를 엔트로피 부호화하는 경우를 RDcost 계산에 의해 그 값이 작은 경로를 선택할 수 있는 경로 선택 과정이 추가될 수 있다.

이 경우 상기 과정과 달리 선택적으로 종전과 같이 잔여 변환 계수 블록을 엔트로피 부호화할 수 있다(S940).

도 10은 본 발명의 바람직한 일실시예에 따른 동영상 잔여 변환 계수 데이터의 디코딩 방법을 설명하는 흐름도이다.

도 10을 참조하면, 엔트로피 복호화부는 코드북을 이용하여 인덱스가 부호화된 비트스트림을 수신하고, 엔트로피 복호화한다(S1010).

비트스트림 내에 포함된 경로 정보인 경로 표현을 위한 플래그 비트를 디코딩하여 해당 비트에 따라 경로를 선택적으로 바꾼다(S1020).

예를 들어, 만약 플래그(flag)가 0인 경우, 인덱스가 복호화되어 디코더에 기저장된 인코더 내의 코드북과 동일한 코드북에서 상기 인덱스에 대응하는 최적 벡터를 역탐색하여 잔여 변환 계수 블록을 출력한다(S1030).

만약 플래그(flag)가 1인 경우, 엔트로피 복호화부로부터 잔여 변환 계수 블록이 복호화되어 역양자화 단계로 진행한다.

복호화된 잔여 변화 계수 블록은 역양자화/역변환부에서 역양자화 및 역변환되어 잔여 계수 블록을 생성한다(S1040).

움직임 보상부는 비트스트림에 포함된 동영상 데이터를 이용하여 인터 예측을 수행하여 예측 블록을 생성한다(S1050).

역양자화/역변환부에서 생성된 잔여 계수 블록과 움직임 보상부에서 생성된 예측 블록을 가산하여 영상을 복원한다(S1060).

도 11을 참조하면, (a)는 Foreman 영상의 R-D 곡선을 도시하고, (b)는 Mobile 영상의 R-D 곡선을 도시한다.

Foreman 영상의 R-D 곡선(a)과 Mobile 영상의 R-D 곡선(b)은 본 발명에서 제안된 동영상 데이터 인코딩 방법(단일 경로 및 이중 경로)과 H.264 참조(reference) 부호화기인 JM(Joint Medel)8.6의 CABAC과 CAVLC와의 성능을 분석하고 있다.

상기 영상들의 실험 조건은 300프레임(352x288 30Hz)이고, QP 24, 30, 36에서 테스트하였으며, 그 외에 가변 크기 움직임 추정, 율-왜곡 최적화, IPPP 구조, 30장 주기의 인트라 프레임, 참조 프레임 5장, ± 16 움직임 벡터 탐색 영역 등이 있다.

H.264 CAVLC와 비교하여 본 발명의 동영상 데이터 인코딩 방법 모두 0.3dB~0.5dB 높은 결과를 보였으며, H.264 CABAC과는 비슷한 성능을 보였다.

본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어 분산 방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다. 그리고, 본 발명을 구현하기 위한 기능적인(functional) 프로그램, 코드 및 코드 세그먼트들은 본 발명이 속하는 기술분야의 프로그래머들에 의해 용이하게 추론될 수 있다.

지금까지 본 발명에 대하여 바람직한 실시예들을 중심으로 살펴보았다. 여기서 특정한 용어들이 사용되었으나, 이는 단지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미 한정이나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다.

그러므로 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 따라서 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다.

본 발명에 따라 DCT와 양자화 후 출력되는 잔여 변환 계수에 대응하는 인덱스를 부호화하여 전송함으로써 압축률을 향상시킬 수 있다.

또한, 상기 인덱스에 대응하는 역양자화 및 역DCT (또는 트랜스폼)된 잔여 계수의 값을 미리 테이블화하여 저장하는 경우, 수신한 비트스트림에 포함된 인덱스에 대응하는 잔여 계수를 테이블 룩업으로 찾을 수 있기 때문에 역DCT 및 역양자화 과정을 생략함으로써 디코더의 계산 복잡도를 낮출 수 있다.

뿐만 아니라 종전과 동일한 방법의 인코딩 및 디코딩과 코드북을 이용한 인코딩 및 디코딩을 선택할 수 있도록 구성함으로써 효율적인 인코딩 및 디코딩이 가능하다.

Claims

현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 단계;

샘플 영상의 잔여 변환 계수들에 대응하는 벡터들을 군집분석 알고리즘을 통해 군집화하여 인덱스를 할당한 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 단계; 및

상기 탐색된 참조 벡터에 할당된 인덱스를 엔트로피 부호화하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제1항에 있어서, 상기 탐색 단계는,

상기 벡터와 상기 각 참조 벡터들 간의 유클리언 디스턴스를 계산하는 단계; 및

상기 계산 값이 최소인 참조 벡터를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화하여 잔여 변환 계수를 생성하는 단계; 및

상기 잔여 변환 계수를 엔트로피 부호화하는 제1 경로, 및 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 제2 경로 중 하나의 경로를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제3항에 있어서, 상기 경로 선택 단계는,

상기 제1 경로의 제1 레이트-디스토션 코스트(RDcost)를 계산하는 단계;

상기 제2 경로의 제2 레이트-디스토션 코스트(RDcost)를 계산하는 단계; 및

상기 제1 레이트-디스토션 코스트와 제2 레이트-디스토션 코스트 값을 비교하여 그 값이 작은 경로를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제3항에 있어서,

상기 선택된 경로에 관한 정보를 부호화하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수, 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중 어느 하나의 잔여 계수에 대응하는 벡터들을 생성하는 단계; 및

상기 벡터들을 군집분석 알고리즘을 통해 군집화하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제6항에 있어서,

상기 군집분석 알고리즘은, 공간상의 위치를 기초로 근접한 공간에 위치하는 벡터들을 군집화하는 알고리즘을 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제6항에 있어서,

상기 벡터들에 인덱스 및 상기 인덱스의 이진화 값인 빈 스트링을 할당하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제8항에 있어서, 상기 군집화 단계는,

상기 인덱스의 수(M)와 상기 잔여 블록의 차원(N)에 의해 상기 벡터들을 M×N 테이블화 하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제8항에 있어서,

상기 벡터들의 프레임 당 확률 분포를 기초로 상기 벡터들을 내림차순으로 정렬한 후 인덱스를 재할당하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
제10항에 있어서, 상기 인덱스 재할당 단계는,

상위 벡터 일부에 대해서만 수행되는 것을 특징으로 하는 동영상 데이터 인코딩 방법.
움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수, 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중의 어느 하나의 잔여 변환 계수 각각에 대응하고, 군집분석 알고리즘을 통해 군집화되어 인덱스가 할당된 벡터들을 수신하는 단계; 및

상기 벡터들을 복호화하여 상기 인덱스와 매칭하여 저장하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제12항에 있어서,

상기 벡터들의 프레임 당 확률 분포를 기초로 상기 벡터들을 내림차순으로 정렬한 후 인덱스를 재할당하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제12항에 있어서,

상기 인덱스와 매칭하여 저장되는 복호화 값은, 상기 인덱스가 할당된 잔여 변환 계수 벡터이거나, 또는 상기 잔여 변환 계수 벡터를 역양자화 및 역변환한 잔여 계수인 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제13항에 있어서, 상기 인덱스 재할당 단계는,

상위 벡터 일부에 대해서만 수행되는 것을 특징으로 하는 동영상 데이터 디 코딩 방법.
샘플 영상의 잔여 변환 계수들에 대응하고 군집분석 알고리즘을 통해 군집화되어 인덱스가 할당된 참조 벡터들 중, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스 정보를 포함한 비트스트림에서 상기 인덱스 정보를 추출하는 단계; 및

상기 추출된 인덱스 정보를 기초로 상기 잔여 블록을 복원하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제16항에 있어서, 상기 복원 단계는,

기 저장된 참조 벡터들 중 상기 인덱스와 동일한 인덱스에 매칭된 참조 벡터를 탐색하는 단계; 및

상기 탐색된 참조 벡터를 역양자화 및 역변환하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제16항에 있어서, 상기 복원 단계는,

기 저장된 참조 벡터들을 미리 역양자화 및 역변환한 잔여 계수들 중 상기 인덱스와 동일한 인덱스에 매칭된 잔여 계수를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제17항에 있어서,

상기 참조 벡터들을 프레임 당 수신되는 벡터들의 확률 분포를 기초로 내림차순으로 재정렬한 후 인덱스를 재할당하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록이 변환 및 양자화된 잔여 변환 계수를 수신하여 상기 잔여 블록을 복원하는 제1 경로, 및 상기 잔여 변환 계수에 대응하는 인덱스를 수신하여 상기 인덱스를 기초로 상기 잔여 블록을 복원하는 제2 경로의 경로 정보가 포함된 비트스트림으로부터 상기 경로 정보를 추출하는 단계; 및

상기 추출된 경로 정보를 기초로 상기 잔여 블록을 복원하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제20항에 있어서, 상기 복원 단계는,

상기 제1 경로 정보가 추출된 경우, 상기 변환 및 양자화된 잔여 변환 계수를 역양자화 및 역변환하는 단계; 및

상기 제2 경로 정보가 추출된 경우, 기 저장된 참조 벡터들 중 상기 인덱스와 동일한 인덱스에 매칭된 참조 벡터를 역양자화 및 역변환하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
제20항에 있어서, 상기 복원 단계는,

상기 제1 경로 정보가 추출된 경우, 상기 변환 및 양자화된 잔여 변환 계수를 역양자화 및 역변환하는 단계; 및

상기 제2 경로 정보가 추출된 경우, 기 저장된 참조 벡터들을 미리 역양자화 및 역변환한 잔여 계수들 중 상기 인덱스와 동일한 인덱스에 매칭된 잔여 계수를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 디코딩 방법.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 단계;

샘플 영상의 잔여 변환 계수들에 대응하는 벡터들을 군집분석 알고리즘을 통해 군집화하여 인덱스를 할당한 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 단계;

상기 탐색된 참조 벡터에 부여된 인덱스를 엔트로피 부호화하는 단계;

상기 참조 벡터들 중에서 입력 스트림으로부터 추출된 인덱스와 동일한 인덱스가 할당된 참조 벡터를 역탐색하는 단계; 및

상기 역탐색된 참조 벡터를 역양자화 및 역변환하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 코딩 방법.
제23항에 있어서,

프레임 당 생성되는 벡터들의 확률 분포를 기초로 상기 참조 벡터들을 내림차순으로 정렬한 후 인덱스를 재할당하는 단계;를 더 포함하는 것을 특징으로 하는 동영상 데이터 코딩 방법.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 엔트로피 부호화하는 제1 경로, 및 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 제2 경로 중 하나의 경로를 선택하는 단계;

상기 선택된 경로에 관한 정보를 부호화하는 단계; 및

상기 경로 정보를 기초로 상기 잔여 블록을 복원하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 코딩 방법.
제25항에 있어서, 상기 경로 선택 단계는,

상기 제1 경로의 제1 레이트-디스토션 코스트(RDcost)를 계산하는 단계;

상기 제2 경로의 제2 레이트-디스토션 코스트(RDcost)를 계산하는 단계; 및

상기 제1 레이트-디스토션 코스트와 제2 레이트-디스토션 코스트 값을 비교하여 그 값이 작은 경로를 선택하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 코딩 방법.
제25항에 있어서, 상기 복원 단계는,

상기 경로 정보를 추출하는 단계;

상기 추출된 경로 정보가 제1 경로인 경우, 상기 변환 및 양자화된 잔여 변환 계수를 역양자화 및 역변환하는 단계; 및

상기 추출된 경로 정보가 제2 경로인 경우, 기 저장된 참조 벡터들 중 상기 인덱스와 동일한 인덱스에 매칭된 참조 벡터를 역양자화 및 역변환하는 단계;를 포함하는 것을 특징으로 하는 동영상 데이터 코딩 방법.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 변환 및 양자화부;

샘플 영상의 잔여 변환 계수들에 대응하는 벡터들을 군집분석 알고리즘을 통해 군집화하여 인덱스를 할당한 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 최적 벡터 탐색부; 및

상기 탐색된 참조 벡터에 할당된 인덱스를 엔트로피 부호화하는 엔트로피 부호화부;를 포함하는 것을 특징으로 하는 인코딩 장치.
제28항에 있어서, 상기 최적 벡터 탐색부는,

상기 벡터와 상기 각 참조 벡터들 간의 유클리언 디스턴스를 계산하고, 상기 계산 값이 최소인 참조 벡터를 선택하는 것을 특징으로 하는 인코딩 장치.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화하여 잔여 변환 계수를 생성하는 변환 및 양자화부; 및

상기 잔여 변환 계수를 엔트로피 부호화하는 제1 경로, 및 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 제2 경로 중 하나의 경로를 선택하는 경로 선택부;를 포함하는 것을 특징으로 하는 인코딩 장치.
제30항에 있어서, 상기 경로 선택부는,

상기 제1 경로의 제1 레이트-디스토션 코스트(RDcost), 및 상기 제2 경로의 제2 레이트-디스토션 코스트(RDcost)를 계산하는 계산부;를 포함하고,

상기 제1 레이트-디스토션 코스트와 제2 레이트-디스토션 코스트 값을 비교하여 그 값이 작은 경로를 선택하는 것을 특징으로 하는 인코딩 장치.
제30항에 있어서,

상기 선택된 경로에 관한 정보를 부호화하는 엔트로피 부호화부;를 더 포함하는 것을 특징으로 하는 인코딩 장치.
움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수, 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중 어느 하나의 잔여 변환 계수 각각에 대응하는 벡터들을 생성하는 벡터 생성부; 및

상기 벡터들을 군집분석 알고리즘을 통해 군집화하는 그룹화부;를 포함하는 것을 특징으로 하는 인코딩 장치.
제33항에 있어서,

상기 군집분석 알고리즘은, 공간상의 위치를 기초로 근접한 공간에 위치하는 벡터들을 군집화하는 알고리즘을 포함하는 것을 특징으로 하는 인코딩 장치.
제33항에 있어서,

상기 벡터들에 인덱스 및 상기 인덱스의 이진화 값인 빈 스트링을 할당하는 인덱스 할당부;를 포함하는 것을 특징으로 하는 인코딩 장치.
제33항에 있어서, 상기 그룹화부는,

상기 인덱스의 수(M)와 상기 잔여 블록의 차원(N)에 의해 상기 벡터들을 M×N 테이블화 하는 것을 특징으로 하는 인코딩 장치.
제35항에 있어서, 상기 인덱스 할당부는,

상기 벡터들의 프레임 당 확률 분포를 기초로 상기 벡터들을 내림차순으로 정렬한 후 인덱스를 재할당하는 것을 특징으로 하는 인코딩 장치.
움직임 보상 변환된 잔여 변환 계수, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환한 잔여 변환 계수 및 상기 잔여 블록을 변환 및 양자화한 잔여 변환 계수 중의 어느 하나의 변환 계수 각각에 대응하고, 군집분석 알고리즘을 통해 군집화되어 인덱스가 할당된 잔여 변환 계수 벡터들을 수신하여 엔트로피 복호화하는 엔트로피 복호화부; 및

상기 엔트로피 복호화된 잔여 변환 계수 벡터들을 상기 인덱스와 매칭하여 저장하는 저장부;를 포함하는 것을 특징으로 하는 디코딩 장치.
제38항에 있어서,

상기 벡터들의 프레임 당 확률 분포를 기초로 상기 벡터들을 내림차순으로 정렬한 후 인덱스를 재할당하는 인덱스 할당부;를 더 포함하는 것을 특징으로 하는 디코딩 장치.
제38항에 있어서, 상기 저장부는,

상기 엔트로피 복호화된 잔여 변환 계수 벡터들을 역양자화 및 역변환한 잔여 계수들을, 상기 인덱스와 매칭하여 저장하는 것을 특징으로 하는 디코딩 장치.
샘플 영상의 잔여 변환 계수들에 대응하고 군집분석 알고리즘을 통해 군집화되어 인덱스가 할당된 참조 벡터들 중, 현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스 정보를 포함한 비트스트림에서 상기 인덱스 정보를 추출하는 엔트로피 복호화부; 및

상기 추출된 인덱스 정보를 기초로 상기 잔여 블록을 복원하는 복원부;를 포함하는 것을 특징으로 하는 디코딩 장치.
제41항에 있어서, 상기 복원부는,

기 저장된 참조 벡터들 중 상기 인덱스와 동일한 인덱스가 매칭된 벡터를 탐색하는 역최적 벡터 탐색부; 및

상기 탐색된 벡터를 역양자화 및 역변환하는 역양자화 및 역변환부;를 포함하는 것을 특징으로 하는 디코딩 장치.
제41항에 있어서,

상기 복원부는, 기 저장된 참조 벡터들을 미리 역양자화 및 역변환하여 복원한 잔여 계수들 중 상기 인덱스와 동일한 인덱스에 매칭된 잔여 계수를 선택하는 것을 특징으로 하는 디코딩 장치.
제42항에 있어서,

상기 참조 벡터들은, 프레임 당 생성되는 벡터들의 확률 분포를 기초로 내림차순으로 정렬된 후 인덱스를 재할당받는 것을 특징으로 하는 디코딩 장치.
제41항에 있어서, 상기 엔트로피 복호화부는,

현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 수신하여 상기 잔여 블록을 복원하는 제1 경로 및 상기 잔여 변환 계수에 대응하는 인덱스를 수신하여 상기 인덱스를 기초로 상기 잔여 블록을 복원하는 제2 경로의 경로 정보가 포함된 비트스트림으로부터 상기 경로 정보를 추출하는 것을 특징으로 하는 디코딩 장치.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수에 대응하는 벡터를 생성하는 변환 및 양자화부;

샘플 영상의 잔여 변환 계수 블록들에 대응하는 벡터들을 군집분석 알고리즘을 통해 군집화하여 인덱스를 할당한 참조 벡터들 중 상기 벡터와 가장 유사한 참조 벡터를 탐색하는 최적 벡터 탐색부;

상기 탐색된 참조 벡터에 할당된 인덱스를 엔트로피 부호화하는 엔트로피 부호화부;

상기 참조 벡터들 중에서 입력 스트림으로부터 추출된 인덱스와 동일한 인덱스가 할당된 참조 벡터를 역탐색하는 역최적 벡터 탐색부; 및

상기 역탐색된 참조 벡터를 역양자화 및 역변환하는 역양자화 및 역변환부;를 포함하는 것을 특징으로 하는 코딩 장치.
제46항에 있어서, 상기 탐색부는,

상기 벡터와 상기 각 참조 벡터들 간의 유클리언 디스턴스를 계산하는 계산부;를 포함하고,

상기 계산 값이 최소인 참조 벡터를 선택하는 것을 특징으로 하는 코딩 장치.
현재 블록과 예측 블록의 차에 해당하는 잔여 블록을 변환 및 양자화한 잔여 변환 계수를 엔트로피 부호화하는 제1 경로, 및 샘플 영상의 잔여 변환 계수들에 대응하는 참조 벡터들 중 상기 잔여 변환 계수에 대응하는 벡터와 가장 유사한 참조 벡터에 매칭된 인덱스를 엔트로피 부호화하는 제2 경로 중 하나의 경로를 선택하는 경로 선택부;

상기 선택된 경로에 관한 정보를 부호화하는 엔트로피 부호화부; 및

상기 경로 정보를 기초로 상기 잔여 블록을 복원하는 복호화부;를 포함하는 것을 특징으로 하는 코딩 장치.
제48항에 있어서, 상기 경로 선택부는,

상기 제1 경로의 제1 레이트-디스토션 코스트(RDcost) 및 상기 제2 경로의 제2 레이트-디스토션 코스트(RDcost)를 계산하는 계산부;를 포함하고,

상기 제1 레이트-디스토션 코스트와 제2 레이트-디스토션 코스트 값을 비교하여 그 값이 작은 경로를 선택하는 것을 특징으로 하는 코딩 장치.
제48항에 있어서, 상기 복호화부는,

상기 경로 정보를 추출하고, 추출된 경로에 따라 상기 제1 경로의 변환 및 양자화된 잔여 변환 계수 및 상기 제2 경로의 상기 인덱스를 복호화하는 엔트로피 복호화부;

상기 제2 경로에 따라 기 저장된 참조 벡터들 중 상기 인덱스와 동일한 인덱스에 매칭된 참조 벡터를 탐색하는 역최적 벡터 탐색부;

상기 탐색된 참조 벡터를 역양자화 및 역변환하는 역양자화 및 역변환부;를 포함하는 것을 특징으로 하는 코딩 장치.
제1항 내지 제27항 중 어느 한 항에 기재된 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.