KR100578682B1

KR100578682B1 - 가변 블록 크기를 이용한 계층적 움직임 추정 장치 및방법

Info

Publication number: KR100578682B1
Application number: KR1020007007345A
Authority: KR
Inventors: 라비 크리쉬나머시; 야-퀸 쟝; 티하오 치앙; 송 슈동
Original assignee: 미디어텍 인크.
Priority date: 1997-12-31
Filing date: 1998-12-31
Publication date: 2006-05-12
Anticipated expiration: 2018-12-31
Also published as: CN1125409C; JP4205858B2; AU2014099A; CN1290381A; US6560371B1; WO1999034330A1; EP1042735A1; KR20010033798A; JP2002500401A

Abstract

본 발명은 블록에 기초한 움직임 추정에 대한 움직임 벡터를 결정하는 데에 계산상의 복잡성을 감소시키기 위하여, N-스케일 타일링과 함께 M진 피라미드 분해를 사용한 장치 및 방법에 관한 것이다.

Description

가변 블록 크기를 이용한 계층적 움직임 추정 장치 및 방법 {HIERARCHICAL MOTION ESTIMATION APPARATUS AND METHOD USING VARIABLE BLOCK SIZES}

본 출원은 1997년 12월 31일에 출원된 09/002,258의 부분연속 출원이다.
본 발명은 일반적으로 이미지 시퀀스를 엔코딩하기 위한 시스템에 관한 것이며, 보다 구체적으로는 블록에 기초한 움직임 추정을 위한 움직임 벡터를 결정하는 데 있어 계산상 복잡성을 감소시키고, 움직임 추정의 정확도를 증가시키기 위하여 "다중 스케일 블록 타일링"을 사용하는 장치 및 그에 따른 방법에 관한 것이다.

비디오 이미지 시퀀스와 같은 이미지 시퀀스는 일반적으로, 이미지 프레임 시퀀스 또는 화상 시퀀스를 포함한다. 움직이는 물체를 포함하는 비디오의 재현은 일반적으로, 초당 30개의 이미지 프레임의 프레임 속도를 요구하는데, 각각의 프레임이 메가바이트를 초과하는 정보를 포함할 지도 모른다. 결과적으로, 이같은 이미지 시퀀스의 전송 및 저장은, 상당한 량의 전송 대역폭 또는 저장 용량을 요구한다. 필요한 전송 대역폭 또는 저장 용량을 감소시키기 위하여, 프레임 시퀀스는 시퀀스내의 리던던시 정보(redundant information)가 저장되지 않거나 전송되지 않도록 압축된다. 텔레비전, 화상 회의 및 CD-ROM 기록은 효율적인 비디오 시퀀스 엔코딩으로부터 유리해질 수 있는 응용 예이다.

일반적으로, 이미지 시퀀스를 엔코딩하기 위하여, 하나의 프레임에서 다음 프레임의 장면에서 물체의 움직임에 관한 정보는 엔코딩 처리에 있어서 중요한 역할을 한다. 대부분의 이미지 시퀀스내의 연속되는 프레임 사이에 존재하는 높은 리던던시로 인하여, 실제 데이터 압축은 움직임 추정/보상으로 공지된 기술을 사용하여 달성될 수 있다. 간략하게, 엔코더는 코딩된 영역에 대하여 시프트되는 영역과 관련하여 차이점만을 엔코딩한다. 즉, 움직임 추정은 하나 이상의 기준 프레임에 대하여 현재 프레임 내의 영역(예를 들어 블록 또는 매크로블록)에 대한 움직임의 방향 및 크기(움직임 벡터)를 결정하는 처리이다. 반면에, 움직임 보상은 현재 프레임의 예측(예측 이미지)을 생성하기 위하여 움직임 벡터를 사용하는 처리이다. 현재 프레임과 예측 프레임 사이의 차이는 오차 신호(에러 신호)를 야기하며, 이것은 현재 프레임 자체보다는 실질적으로 적은 정보를 포함한다. 따라서, 단지 오차 신호 및 해당 움직임 벡터만을 전송 및 엔코딩함으로써, 비트를 코딩하는데 있어서 상당한 절약이 실현된다.

설명을 위하여, 움직임을 포함하는 시퀀스에 있어서 현재 프레임은 현재 프레임과 바로 앞의 프레임 사이의 차를 나타내는 오차 신호와 바로 앞의 프레임을 사용하여 재구성될 수 있다. 전송기 및 엔코더는 이전의 프레임, 오차 신호 및 해당 움직임 벡터를 수신기로 전송한다. 수신기에서, 현재 프레임은, 이전의 프레임을 오차 신호 및 움직임 벡터와 조합함으로써, 재구성된다. 결과적으로, 두 개의 전체 프레임이 아니라, 단지 (1) 하나의 프레임 및, 그와 연관된 움직임 벡터를 갖는 차 정보가 전송 및 수신된다.

그러나, 엔코더 설계자는 오차 신호를 최소화하기 위하여(즉 코딩 비트를 감소) 움직임 추정 방법의 정확성을 증가시키거나, 또는 계산상 오버헤드를 최소화하기 위하여 움직임 추정 처리에 있어서 낮은 정확성 레벨을 수용하는 2가지 옵션 중 하나를 선택하여야 한다. 즉, 프레임 시퀀스로부터의 움직임 벡터를 결정하는 것은 움직임 정보를 결정하기 위해 프레임들 사이에서 철저한 탐색을 요구한다. 철저한 탐색이 증가할수록 더 많은 계산 사이클을 이용하여 보다 정확한 움직임 벡터의 세트를 생성한다.

예를 들어 많은 시스템은 소위 블록에 기초한 방법을 사용하여 움직임 정보를 결정한다. 간단한 블록에 기초한 방법에 있어서, 현재 프레임은 다수의 화소 블록(본 명세서에서는 이하 "현재 블록"이라 함)으로 분할된다. 이러한 각각의 현재 블록에 대하여 탐색은 현재 블록에 "최상으로" 매칭하는 화소의 블록에 대하여 이전의 프레임내의 선택된 탐색 영역내에서 수행된다. 이러한 탐색은 이전 프레임의 선택된 탐색 영역내의 유사한 크기의 화소 블록과 선택된 현재 블록을 반복적으로 비교함으로써, 일반적으로 수행된다. 블록 매칭이 발견되면, 현재 프레임 내의 현재 블록의 위치에 관련하여 이전 프레임 내의 탐색 영역내 매칭 블록에 대한 위치는 움직임 벡터를 정의한다. 이러한 방법, 즉 각각의 현재 블록을 전체 선택된 탐색 영역에 비교하는 방법은 전체 탐색 방법 또는 소모적인 탐색 방법(exhaustive search approach)으로 공지되었다. 소모적인 탐색 방법을 사용하여 움직임 벡터를 결정하는 것은 특히 계산 집약적이며, 특히 탐색 영역이 큰 경우에 그러하다. 이와 같이, 이러한 시스템은 프레임을 처리하는 데에 상당히 느리고 제조에 있어서도 값비싼 경향이 있다.

이에 따라 기술 분야에서는 블록에 기초한 움직임 추정을 위한 움직임 벡터를 결정하는 데 있어서의 계산상 복잡성을 감소시키기 위한 장치 및 그에 따른 방법에 대한 요구가 존재하게 된다.

본 발명의 실시예는, 블록에 기초한 움직임 추정을 위한 움직임 벡터를 결정하는 데 있어서의 계산상 복잡성을 감소시키고 움직임 추정 방법의 정확성을 향상시키기 위하여, "다중 스케일 블록 타일링(multi-scale block tiling)(N-스케일 타일링)"을 사용하는 장치 및 방법에 관한다. 보다 구체적으로, 본 발명은 이미지 시퀀스 내의 각각의 이미지 프레임을 M진(M-ary) 피라미드로 분해한다. 이어, N-스케일 타일링이 M진 피라미드에서 사용되어 계층적 움직임 추정을 달성한다. N-스케일 타일링은 "N"개의 상이한 "타일링 블록" 크기를 사용하여 프레임의 현재 블록에 대한 움직임 추정을 수행하는 처리이다. 예를 들어 N이 3으로 설정되면, 3개의 움직임 벡터가 각 프레임 내의 각각의 블록에 대하여 생성되며, 즉 블록은 3개의 상이한 블록 크기 또는 스케일로 "타일링"된다. 따라서, N-스케일 타일링을 사용한 계층적 움직임 추정은, 엔코더가 고찰 중의 프레임 내의 작은 형상의 움직임과 큰 구조물의 움직임들 사이를 구별할 수 있도록 하여준다.

본 발명의 추가의 특징 및 장점은 실시예에 대한 다음의 설명 및 첨부된 도면으로부터 보다 명확하여 질 것이다.

도 1은 블록에 기초한 움직임 추정에 대한 움직임 벡터의 결정에 있어서의 계산상 복잡성을 감소시키기 위한, 본 발명의 엔코더에 대한 블록도를 도시한다.

도 2는 블록에 기초한 움직임 추정을 위한 움직임 벡터를 결정하는 데 있어서의 계산상 복잡성을 감소시키기 위한 방법의 흐름도를 도시한다.

도 3은 일반적인 평균 피라미드에 대한 블록도를 도시한다.

도 4는 M진 피라미드를 생성하는 양자화 처리에 대한 블록도를 도시한다.

도 5는 여러 블록으로 분할 또는 분류된 입력 프레임을 도시한다.

도 6은 본 발명의 엔코딩 시스템을 도시한다.

도 7은 3-스케일 타일링을 사용한 화소의 블록에 대한 블록도를 도시한다.

도 8은 본 발명에 따른 제 2 실시예의 장치에 대한 블록도를 도시한다.

도 9는 웨이브릿 트리를 그래프적으로 도시한다.

도 10은 이미지에 대한 M진 피라미드를 생성하기 위한 방법의 흐름도를 도시한다.

도 11은 N-스케일 타일링을 사용하여 M진 피라미드에 대한 움직임 추정을 수행하기 위한 방법의 흐름도를 도시한다.

도 1은 블록에 기초한 움직임 추정에 대한 움직임 벡터를 결정하는 데 있어서의 계산상 복잡성을 감소시키기 위한 본 발명의 장치(100)의 블록도를 도시한다. 본 발명의 바람직한 실시예는 엔코더를 사용하여 아래에서 설명되지만, 본 발명이 일반적으로 이미지 처리 시스템에서 사용될 수 있다는 것을 이해해야 한다. 더욱이, 본 발명은 다양한 코딩 표준에 따르는 엔코더에서 사용될 수 있다. 이러한 표준은 동화상 전문가 그룹 표준(예를 들어 MPEG-1(11172-*) 및 MPEG-2(13818-*), H.261 및 H.263)을 포함하지만, 이에 한정되지는 않는다.

장치(100)는 엔코더 또는 보다 복잡한 블록에 기초한 움직임 보상된 코딩 시스템의 일부이다. 상기 장치(100)는 움직임 추정 모듈(140), 움직임 보상 모듈(150), 선택적 분할 모듈(151), 전처리 모듈(120), 비율 제어 모듈(130), 변환 모듈(예를 들어 DCT 모듈)(160), 양자화 모듈(170), 코더(예를 들어 가변길이 코딩 모듈)(180), 버퍼(190), 역 양자화 모듈(175), 역 변환 모듈(예를 들어 역 DCT 모듈)(165), 감산기(115) 및 가산기(155)를 포함한다. 엔코더(100)가 여러 모듈을 포함하지만 기술 분야의 당업자는 다양한 모듈에 의해 수행되는 기능은 도 1에 도시된 것처럼 각각의 모듈로 분리되도록 요구되지 않는다는 것을 인지할 수 있을 것이다. 예를 들어 움직임 보상 모듈(150), 역 양자화 모듈(175) 및 역 DCT 모듈(165)을 포함하는 모듈 세트는 일반적으로 "내장형 디코더"로 공지되었다.

도 1은 MPEG 표준에 따라 디지털화되고 휘도 및 두 개의 상이한 칼라 신호(Y, Cr, Cb)로 표현되는 경로(110) 상의 입력 이미지(이미지 시퀀스)를 도시한다. 이러한 신호는 추가로 각각의 화상(프레임)이 여러 매크로 블록에 의해 표현되는 방식으로 여러 층으로 나뉘어 진다. 각각의 매크로 블록은 4개의 휘도 블록, 하나의 Cr블록, 하나의 Cb블록으로 나뉘어 지며, 하나의 블록은 8 * 8 샘플 어레이로 정의된다. 화상을 블록 단위로 분할하는 것은 두 개의 연속된 화상 사이의 변화를 분간하기 위한 능력을 향상시키고, (아래에 설명된) 작은 크기의 변환 계수의 제거를 통해 이미지 압축을 향상시킨다.

다음의 설명은 MPEG 표준 용어를 사용하지만; 본 발명의 매크로블록 또는 블록의 용어는 코딩의 기초를 위하여 사용되는 소정 크기 또는 모양의 화소 블록을 묘사하기 위한 것임이 이해될 것이다. 대체로 말하면, "매크로블록"은 하나의 화소만큼 작을 수 있거나 전체 비디오 프레임만큼 클 수도 있다.

바람직한 실시예에 있어서, 디지털화된 입력 이미지 신호는 전처리 모듈(120)에서 하나 이상의 전처리 단계를 거친다. 보다 구체적으로 전처리 모듈(120)은 피라미드 생성기(122) 및 블록 분류기(124)를 포함한다. 상기 M진 피라미드 생성기(122)는 각각의 프레임을 다수의 상이한 해상도, 즉 해상도의 M진 피라미드로 필터링하고 양자화하기 위하여 평균 필터(123a) 및 양자화기(123b)를 사용하며, 각 프레임의 상이한 해상도는 아래에서 설명되는 계층적 방식으로 상관된다. 이러한 해상도 피라미드를 사용하여, 블록 분류기(124)는 높은 액티비티 또는 낮은 액티비티의 영역으로 영역(블록)을 빠르게 분류할 수 있다. 전처리 모듈(120)에 의해 수행되는 기능에 대한 상세한 설명은 아래에 제공된다.

경로(110)상의 입력 이미지는 또한 움직임 벡터를 추정하기 위한 움직임 추정 모듈(140)에도 수신된다. 움직임 벡터는 현재 화상내의 블록의 좌표 위치로부터 기준 프레임 내의 좌표까지의 오프셋을 제공하기 위하여 움직임 보상에 의해 사용되는 2차원 벡터이다. 움직임 벡터의 사용은 현재 프레임 내의 변화만이 코딩 및 전송되기 때문에 채널 상에서 전송되는 정보의 양을 감소시킴으로써, 이미지 압축을 크게 향상시킨다. 바람직한 실시예에 있어서, 움직임 추정 모듈(140)은 또한 전처리 모듈(120)로부터 정보를 수신하여, 움직임 추정 처리의 성능을 향상시킨다.

움직임 추정 모듈(140)로부터의 움직임 벡터는 샘플 값의 예측에 대한 효율성을 향상시키기 위한 움직임 보상 모듈(150)에 의해 수신된다. 움직임 보상은 이전에 디코딩된 샘플 값을 포함하는 과거 및/또는 미래의 기준 프레임에 오프셋을 제공하는 데에 움직임 벡터를 사용하고 예측 에러를 생성하는 데에 사용되는 예측을 수반한다. 즉, 움직임 보상 모듈(150)은 이전에 디코딩된 프레임과 움직임 벡터를 사용하여, 경로(152) 상의 현재 프레임에 대한 추정(움직임 보상된 예측 또는 예측된 이미지)을 구성한다. 상기 움직임 보상된 예측은 감산기(115)를 통해 현재 매크로블록내의 경로(110) 상의 입력 이미지에서 감산되어 경로(153) 상의 에러 신호(e) 또는 예측 오차를 형성한다.

상기 예측 오차 신호는 변환 모듈, 예를 들어 DCT 모듈(160)로 전달된다. 상기 DCT 모듈은 순방향 이산 코사인 변환 처리를 예측 에러 신호의 각 블록에 제공하여, DCT 계수의 8*8 블록 세트를 형성한다. 상기 이산 코사인 변환은 DCT 계수가 코사인에 기초한 함수 세트에 대한 진폭을 나타내는 역변환 가능한 이산 직교 변환이다.

결과적인 DCT 계수의 8*8 블록은 양자화(Q) 모듈(170)에 의해 수신되며, 여기에서 DCT 계수는 양자화된다. 양자화 처리는, 양자화 값 세트 또는 정수 값을 형성하기 위하여 적절한 사사오입(rounding)을 하는 스케일로 DCT 계수를 나눔으로써, DCT 계수가 표현되는 정확성를 감소시킨다. 양자화 값은 (시각적으로 가중된 양자화로 공지된) 기본 함수의 가시성에 기초한 기준을 사용하여, 각각의 DCT 계수에 대하여 개별적으로 설정될 수 있다. 이러한 값으로 DCT 계수를 양자화함으로써, 많은 DCT 계수는 제로로 변환되며, 이에 따라 이미지 압축 효율을 향상시킨다.

이어, 양자화된 DCT 계수의 결과적인 8*8 블록은 코더, 예들 들어 가변 길이 코딩 모듈(180)에 의해 신호 접속부(171)를 통해 수신되며, 여기(180)에서 양자화된 계수의 2차원 블록은 계수를 1차원 스트링의 양자화 DCT 계수로 변환하기 위하여 "지그-재그" 순으로 스캐닝된다. 가변 길이 코딩(VLC) 모듈(180)은 양자화된 DCT 계수의 스트링 및, 매크로블록 타입 및 움직임 벡터와 같은 매크로 블록에 대한 모든 부가적인 정보를 엔코딩한다. 따라서 VLC 모듈(180)은 입력 이미지를 유효 데이터 스트림으로 변환하는 최종 단계의 변환을 수행한다.

데이터 스트림은 버퍼, 예를 들어 FIFO(First In-First Out) 버퍼(190)로 수신된다. 상이한 화상 타입 및 가변 길이 코딩의 사용 결과는 최대 비트율이 가변한다는 것이다. 즉, 각각의 프레임을 코딩하기 위해 사용된 비트의 수가 상이할 수 있다. 따라서, 고정 비율의 채널을 포함하는 응용에 있어서, FIFO 버퍼는 비트 율을 평탄화하기 위하여 엔코더 출력을 채널에 매칭시키는 데에 사용된다. 따라서, FIFO 버퍼(190)로부터의 경로(195)상의 출력 신호는 입력 이미지(110)의 압축된 표현이며, 상기 경로에서 출력 신호는 저장 매체 또는 원격 통신 채널로 전송된다.

비율 제어 모듈(130)은 데이터 스트림을 전송한 이후에 (도시되지 않았지만 수신기 또는 목표 저장 장치 내의) 디코더측에서의 오버플로우 및 언더플로우를 방지하기 위하여, FIFO 버퍼(190)에 입력되는 데이터 스트림의 비트율을 모니터링하고 조정하는 역할을 한다. 고정 비율의 채널은 일정한 비율로 비트를 (도시되지 않은) 디코더 내의 입력 버퍼로 이송한다고 가정된다. 화상 비율에 의해 결정되는 규칙적 간격으로, 상기 디코더는 순간적으로 다음 화상에 대한 모든 비트를 입력 버퍼로부터 제거한다. 만약 입력 버퍼 내에 너무 적은 비트가 존재한다면, 즉, 다음 화상에 대한 모든 비트가 수신되지 않았다면, 입력 버퍼는 언더플로우되어 에러를 야기한다. 유사하게, 너무 많은 비트가 입력 버퍼에 존재한다면, 즉 입력 버퍼의 용량이 화상 시작들 사이에서 초과된다면, 입력 버퍼는 오버플로우되어 오버플로우 에러를 야기한다. 따라서, 비율 제어 모듈(130)의 임무는 엔코더에 의해 생성된 비트의 개수를 제어하여 이에 따라 오버플로우 및 언더플로우 상황을 방지하기 위하여 버퍼(190)의 상태를 모니터링하는 것이다.

게다가, 양자화 모듈(170)로부터의 양자화된 DCT 계수의 결과적인 8*8 블록은 역 양자화 모듈(175) 및 역 DCT 모듈(165)에 신호 접속부(172)를 통해 수신된다. 간략하게, 이러한 단계에서, 엔코더는 후속하는 엔코딩을 위한 기준 프레임으로서 데이터가 사용되도록 데이터를 디코딩함으로써, 이미지 시퀀스의 I 프레임 및 P 프레임을 생성한다.

도 2는 블록에 기초한 움직임 추정에서 움직임 벡터를 결정하는 데 있어서의 계산상 복잡성을 감소시키기 위한 방법(200)의 흐름도를 도시한다. 즉, 방법(200)은 매칭이 발생할 수 있는 초기 영역을 빨리 한정함으로써 블록에 기초한 움직임 추정을 향상시킨다.
더 구체적으로는, 방법(200)은 단계 205에서 시작하여 M진 피라미드(또는 M진 평균 피라미드)가 이미지 시퀀스 내의 각각의 이미지 프레임에 대하여 생성되는 단계(210)로 진행한다. M진 피라미드의 생성 방법에 대한 상세한 설명은 도 3, 도 4 및 도 10을 참조하여 아래에 제공된다.

보다 구체적으로, 도 10은 이미지에 대한 M진 피라미드를 생성하기 위한 방법(1000)의 흐름도를 도시한다. 상기 방법은 단계 1005에서 시작하여, 원래 이미지가 평균 피라미드의 이미지로 분해되는 단계 1010로 진행한다.

도 3은 일반적인 평균 피라미드(300)에 대한 블록도를 도시하며, 여기에서 평균 피라미드는 다수의 레벨(310,320,330)을 포함한다. 최하위 레벨(310)은 "x"로 표현된 다수의 화소(311)를 가지는 이미지 시퀀스로부터의 원래 이미지 프레임이다. 일반적으로, 이러한 화소는 화소 값을 표현하기 위하여 할당된 다수의 비트에 의하여 한정되는 범위를 가지는 화소 값으로 표현된다. 예를 들어 8 비트가 할당되었다면, 화소 값은 256개의 가능한 값 중 하나의 값을 취한다.

평균 피라미드에 있어서, 다음의 높은 레벨은 저역 통과 필터 및 양방향의 두 개의 팩터에 의한 다운샘플링에 의해 생성되며, 이에 의해 하위 레벨의 4개의 화소값(자식)으로부터 높은 레벨에 대한 단일의 화소 값(부모)을 생성한다. 이것은 도 3에서 설명되며, 여기에서 4개의 화소 세트(312a-312d) 각각이 레벨(320)의 단일 화소 값(321)을 생성하는 데에 사용된다. 차례로, 4개 화소 값의 세트(322a)는 레벨(330)의 단일 화소 값(331)을 생성하는 데에 사용되며, 기타도 그러하다. 본 발명이 3개의 레벨을 가지는 평균 피라미드로 한정되는 것이 아님을 알 수 있을 것이다. 일반적으로 레벨의 개수는 이미지의 크기 및 다음의 낮은 해상도를 갖는 이미지를 생성하도록 선택된 다운샘플링 팩터에 의해 한정된다. 따라서, 평균 피라미드의 레벨의 개수는 특정한 적용에 대하여 선택될 수 있다.

평균 피라미드에 있어서, 부모 화소 값은 자신의 4개의 자식 화소 값의 평균을 취함으로써 유도되며, 이에 따라 평균 피라미드로 지칭된다. 그러나, 다른 방법 및 매트릭이 다른 타입의 피라미드를 생성하는 데에 사용될 수 있으며, 예를 들어 4개의 자식 화소 값의 중앙값에 기초하는 방법이 사용될 수 있다. 대안적으로, 자식 화소를 둘러싼 더 큰 영역은 가중 처리된 평균에 대하여 사용될 수 있으며 일반적인 저역 통과 피라미드를 얻는다.

도 10을 참조하여, 이어 방법(1000)은 단계 1020에서 상기 평균 피라미드로부터 M진 피라미드를 생성한다. 즉, "M진 피라미드"에 있어서, 화소 값은 각각의 양자화된 화소 값이 "M"개의 가능한 화소 값만을 취하는 방식으로 양자화된다. 예를 들어 M이 2와 같다면, 각각의 양자화된 화소 값은 0 또는 1의 값을 취하며, 즉 "이진 피라미드"를 야기한다.

도 4는 3진(ternary) 피라미드를 생성하는 양자화 처리의 블록도를 도시하며, 여기에서 M은 3이 된다. 보다 구체적으로, 8비트의 화소 값 255(410a)이 자식 화소와 부모 화소 사이의 차이에 기초하여 2 비트 화소 값 10(420a)으로 양자화된다. 즉 차이가 부모(430a)와 각각의 부모의 자식(410a-410d) 사이에서 계산되며, 각각의 4개의 차이가 3개의 가능한 값 10,00, 및 01로 양자화된다. 따라서, 화소 값(128)(410b 및 410c)은 화소 값 00(420b 및 420c)으로 양자화되고 화소 값 0(410d)은 화소 값 01(420d)로 양자화된다. 이러한 표현 레벨은 움직임 추정에 사용될 수 있는 비트 방식의 XOR에 기초한 비용 함수(cost function)에 적합하다. 그것들은 또한 특징 검출 및 블록 분류에 유용하다. M진 피라미드는 화소 값의 정확성을 감소시키며, 이에 따라 이미지내의 "특징"의 빠른 검출을 허용한다. 특징은 높은 액티비티 또는 강도의 영역, 즉 물체의 가장자리로 한정된다. 레벨(410 및 430)은 평균 피라미드의 레벨이 되는 반면에, 레벨(420)은 M진 피라미드(여기에서 M=3)의 레벨이 된다는 것이 주지되어야 한다. 이러한 피라미드 모두는 도 4에 도시된 것과 같은 부가 레벨을 가질 수 있지만, M진 피라미드는 평균 피라미드보다 한 레벨 낮은 레벨을 가질 것이다. 즉 단일의 M진 피라미드 레벨(420)을 형성하기 위하여 이것은 두 개의 평균 피라미드 레벨(410, 430)을 필요로 한다.

게다가, 화소 값을 표현하기 위하여 사용된 비트 수에 있어서의 상당한 감소는 움직임 추정 처리에서의 계산상 오버 헤드 감소로 전환된다. 예를 들어, 화소 값이 취할 수 있는 가능한 적은 값만이 존재하여 전체적인 블록 매칭 처리를 간략화시키기 때문에, 움직임 추정 처리에서 수행되는 블록 매칭 동작은 가속화될 수 있다.

M이 소정의 값을 가질 수 있을 지라도, "낮은 차수의" M진 피라미드, 예를 들어 2진 피라미드 분해가 "높은 차수의" M진 피라미드, 예를 들어 3진 피라미드보다 잡음에 더 민감하다는 것을 알 수 있다. 즉, 2진 피라미드로 양자화된 화소 값은 단지 두 개의 가능한 값 중 하나의 값을 취할 수 있기 때문에, 잡음은 에러를 유도할 수 있으며, 여기에서 화소 값이 0 대신에 1의 값을 가지거나, 1 대신 0의 값을 가지는 것과 같이 그릇되게 해석될 수 있다. 그러나, "높은 차수의" M진 피라미드는 보다 많은 계산상의 오버헤드를 요구한다. 따라서, M진 피라미드 분해는 M이 2 보다 클 때 최선으로 사용된다는 것이 관찰되었을 지라도, 특정 M진 피라미드 분해의 선택은 종종 특정 응용의 요구에 의해 요구된다. M진 피라미드가 생성되면, 방법(1000)은 단계 1030에서 종료하고 도 2의 단계 220으로 복귀한다.

단계 210의 중요한 특징은 이미지 시퀀스의 입력 이미지 각각에 대하여 M진 피라미드를 생성한다는 것이다. 이와 같이, 바람직한 실시예가 M진 평균 피라미드를 생성한다고 하더라도, 다른 타입의 M진 피라미드, 예를 들어 M진 중앙 피라미드, M진 저역 통과 피라미드 등의 다른 타입이 본 발명에서 사용될 수 있다.

대안적으로 본 발명의 M진 평균 피라미드 분해의 개념은 방정식 형태로 표현될 수 있다. (i,j)가 이미지 프레임상의 화소 위치를 나타내고 I(i,j)가 위치(i,j)에서의 강도를 나타낸다고 하자, 나아가, l은 피라미드내의 레벨을 나타내고, 0≤l≤L이며, L은 피라미드내의 최고 레벨이다. 이어, 평균 피라미드 X^l(i,j), 1≤l≤L은 다음과 같이 구현된다.

(1)

여기에서 X⁰(i,j)=I(i,j)이다.

도 2를 참조하여, 평균 피라미드로부터, 블록내의 특징과 같은 정보는 아래의 단계 220에서 추출될 수 있다. 실시예에 있어서, 블록은 매크로 블록의 8*8 서브블록이지만, 본 발명이 이같은 블록 크기에 한정되지 않는다는 것이 이해될 것이다. 특히, 가장자리와 같은 특징은 블록 내의 강도 변화로부터 추출될 수 있다. 이같은 변화는 0≤l≤L-1 레벨에서의 평균값과 레벨 l+1에서의 평균값 사이의 차이를 계산함으로써, 표현된다. 그러나, 강한 특징을 얻기 위하여 그리고, 빠른 움직임 추정을 용이하게 하기 위하여, 이러한 차이는 M진 피라미드를 형성하도록 양자화된다. M진 피라미드의 각 레벨은 가장자리 및 제로 크로싱과 같은 이미지 특징을 식별하기 위하여 또는 움직임 추정을 구현하기 위하여 사용될 수 있는 이미지에 대한 패턴을 설명한다.

예를 들어, 이미지의 이진 피라미드 B^l(i,j)는 다음;

(1a),

처럼 설정될 수 있으며, 여기에서, l은 이진 피라미드내의 레벨을 나타낸다. 상기 식 1a가 이진 피라미드의 두 개의 값("0" 및 "1")을 정의하는 특정한 조건(양자화 단계)을 설명할 지라도, 다른 조건 또는 양자화 단계는 특정 응용에 따라 이진 피라미드의 두가지 값("0" 및 "1")을 정의하기 위하여 사용될 수 있다.

대안적으로, 이미지의 3진 피라미드 Y^l(i,j)가 형성될 수 있다. 예를 들어, M진(M=3) 피라미드의 패턴 값은 Y^l(i,j);

(2)

로 나타낼 수 있다.

괄호[·]의 변수를 λ로 나타내자. 예를 들어, 임계치 T를 가지는 3진 피라미드의 경우를 고려하면 Y^l(i,j)는 다음과 같이 정의된다.

(3)

양자화 임계치 T(예를 들어 바람직한 실시예에서 T는 5로 선택됨)가 특정 응용에 대하여 적절하게 선택된다면, 이러한 정의는 잡음-강도(noise-robustness)의 평균을 가진다. 즉, "불감대(dead zone)"를 정의하는 것이, 예를 들어 |λ|<T인 것이 가능하며, 여기에서 잡음에 기인한 화소 값에서의 미세한 변화는 효율적으로 제거된다. 따라서 제로 근처에서 불감대를 가지는 소정의 M진 피라미드(M>2)는 잡음 감도 문제를 최소화시킨다.

상대적으로 단조로운 영역(flat area)(낮은 액티비티의 영역)에 있어서, Y^l(i,j)는 상당히 많은 제로(0)를 포함하는 반면에, 가장자리를 포함하는 영역에서 Y^l(i,j)는 많은 1을 포함한다. 입력 이미지가 M진 피라미드로 분해되면, 입력 이미지의 블록은 M진 피라미드, Y^l(i,j)를 사용하여 특징 추출을 위한 목적으로 분류될 수 있다. 즉, M진 피라미드는 상당한 계산상의 오버헤드를 초래하지 않고 입력 이미지에서의 특징을 빠르게 검출하는 데에 사용될 수 있다. 검출된 특징은 아래에서 설명한 바와 같이 움직임 추정 처리 또는 예를 들어, 분할 모듈(151)을 사용하여 다른 이미지 처리 단계, 예를 들어 이미지내의 (물체와 같은) 영역의 분할을 향상시키기 위하여 사용될 수 있다. 분할은 중요한 이미지 처리 단계이며, 여기에서 이미지내의 중요한 영역은 특정 처리를 수용하도록 식별될 수 있다. 예를 들어 화상 회의 응용 동안 사람의 얼굴은, 코딩 비트의 더 큰 할당을 수용하는 것과 같은 특정 이미지 처리를 요구할 수 있다. 부가적으로, 분할은 커다란 물체를 식별하는 데에 사용될 수 있으며, 전체적인 움직임 추정은 이러한 커다란 물체상에서 수행될 수 있다.

앞의 설명이 3진 피라미드를 일례로서 사용하고 양자화 임계치 또는 레벨이 특징 식별 및 분류를 위해 할당될 수 있는 하나의 가능한 방법을 나타낸다는 것을 이해할 수 있을 것이다. 일반적으로 M ≥2인 M진 피라미드는 특정한 응용의 요구 및/또는 이미지 시퀀스의 내용에 의존하는 양자화 임계치의 특수한 할당이 사용될 수 있다.

도 2를 참조하여, M진 피라미드가 생성된 후, 방법(200)은 프레임 내의 블록이 M진 피라미드의 관점에서 낮은 액티비티 또는 높은 액티비트로 분류되는 단계 220로 진행한다. 바람직한 실시예에 있어서, "분류 블록 크기"는 128 비트에 의해 표현된 64 M진 화소 값을 가지는 8*8 블록이다. 여기에서 8*8 블록이 25개 이상의 화소 값이 제로가 아닐 경우에 높은 액티비티의 블록으로 분류된다면, "액티비티 임계치"가 25로 설정된다. 그렇지 않은 경우, 8*8 블록은 낮은 액티비티의 블록으로 분류된다. 부가적인 높은 블록 분류는 예를 들어 매크로블록을 높은 액티비티 또는 낮은 액티비트 매크로블록으로 분류함으로써 수행될 수 있다. 바람직한 실시예에 있어서, 높은 액티비티로서 분류된 적어도 하나의 서브 블록을 가지는 매크로블록은 높은 액티비티를 갖는 매크로블록으로 분류된다. "분류 블록 크기" 및 "액티비티 임계치"가 특정 응용에 따라 조정될 수 있으며 바람직한 실시예에서 선택된 값들로 한정되지 않는다는 것이 이해될 것이다.

도 2를 참조하여, 블록 분류 이후에, 방법(200)은 블록 분류가 움직임 추정 처리를 향상시키기 위하여 사용되는 단계 230로 진행한다. 일반적으로, 중요한 이미지 특징을 가지는 영역에서의 움직임 추정은 애퍼추어(aperture) 문제(예를 들어 이미지의 내용이 인접한 블록과 매우 유사한 고른 영역)에 기인하여 적은 변화를 가지는 상대적으로 "단조로운 영역(flat area)"에서의 움직임 추정보다는 더 신뢰적이다. 이에 따라, 상기 언급된 분류 방법은 일반적으로 움직임 추정의 신뢰도를 증가시키기 위해 사용된다. 그러나, 움직임 추정 응용에서의 M진 피라미드의 사용에 앞서 블록의 내용으로 상기 블록을 미리 분류하는 것이 필요하지 않다는 것을 알 수 있을 것이다.

즉, M진 피라미드에 대한 본 발명이 다양한 타입 또는 상이한 구조의 움직임 추정 방법의 수행력을 향상시키기 위하여 직접 사용될 수 있다(도 2에 점선으로 표기되었음)는 것을 이해할 것이다.

특히, 움직임 추정은 일반적으로, 래스터(raster) 스캔 순으로 한 블록씩 수행된다. 계산적인 오버헤드 또는 비용은 일반적으로 움직임 추정 처리 동안에 모든 블록에 대하여 균일하게 분포된다. 본 발명에 있어서, "가장자리" 블록( 높은 액티비티 블록)에서의 움직임 추정은 우선 Y^l(i,j) 및/또는 X^l(i,j)에 의존하는 비용 함수를 사용하여 수행될 수 있다. 이러한 방법은 이미지내의 특징을 강조하는 것을 허용하고, 센서 잡음, 양자화 잡음 및 휘도 변화가 존재하는 경우에 강하고 신뢰적인 움직임 추정을 제공한다. 비용 함수의 예는 피라미드의 M진 레벨상에서의 비트 단위(bit-wise)의 XOR 연산을 포함하며, 이것은 특정 구조에서 빠른 방법으로 수행될 수 있다. 비용 함수는 "최상의 매칭"을 결정하기 위해 사용된다. 시간 t(현재 프레임)에서 M진 값의 블록, Y^l(i,j,t) 및 시간 t-1(이전의 프레임)에서 다른 M진 값의 블록, Y^l(m,n,t-1)을 고려하도록 한다. 비용 함수는 다음;

에서의 1 값들의 수

과 같이 표현되며, ⓧ는 비트 단위의 XOR 연산을 나타낸다. 이러한 비용 함수는 원래의 8비트 화소 강도 값에 대하여 사용되는 표준 "절대 차" 비용 함수와 비교하여 실질적인 계산을 절약시킨다. 이러한 절차는 M진 피라미드에 걸쳐 계층적으로 수행된다.

다시 말하면, 움직임 추정 방법은 높은 액티비티의 블록에서 시작한다. 도 5는 다수의 블록(510)으로 분할 및 분류된 입력 프레임(500)을 도시한다. 바람직한 실시예에 있어서, 두 개의 블록(510a)은 높은 액티비티 블록으로 분류된다. 이와 같이 움직임 추정은 이러한 두 개의 블록에 대하여 우선적으로 수행된다. 실제로, 이러한 높은 액티비티 블록(높은 정확성의 "가장자리" 블록)이 매우 높은 정확도의 움직임 벡터를 가장 잘 제공할 것 같기 때문에, 계산 비용은 이러한 두 개의 블록에 대하여 증가될 수 있다. 따라서, 보다 철저한 움직임 추정이 이미지 프레임(500)내의 다른 블록보다 이들 두 블록에서 수행되며, 예를 들어 높은 액티비티의 블록은 보다 정확한 움직임 벡터를 얻기 위해 나뉘어질 수 있으며, "반 화소(half-pel)"의 움직임 추정은 이같은 두 개의 블록에서 수행될 수 있거나 더 세밀한 탐색 방법이 사용될 수 있다.

이어, 움직임 추정이 높은 액티비티의 블록에 대하여 완료된 이후, 움직임 추정은 이미지의 낮은 액티비티의 블록(낮은 정확성의 "블록")으로 전파된다. 그러나, 이러한 전파는 분류로부터 획득되는 물체 세그먼트 또는 영역에 의존하여 지능적으로 수행된다. 이러한 전파는 인접한 블록의 움직임에 대한 초기화로서 가장자리 블록의 움직임을 사용하고 이러한 초기화를 세밀화하기 위하여 상대적으로 적은 탐색 범위를 사용함으로써 수행될 수 있다. 즉, 움직임 추정 처리는 블록(510b)으로 전파되며(예컨대, 나선형 순서로), 여기에서 초기 탐색 영역은 높은 액티비티 블록의 움직임 벡터로부터 유도된다. 이어, 이러한 전파 방식은 "가장자리" 블록에 인접하여 놓여있지 않은 "단조로운" 블록, 예를 들어 블록(510c) 등으로 확장되며, 세밀한 탐색 범위가 상대적으로 적어지기 때문에 빠른 계산의 장점을 가진다. 게다가, 움직임 추정은 엔코딩하기에 더욱 원활하고 용이해질 것이며, 이것은 움직임 정보가 비트 스트림의 상당 부분을 형성하는 매우 낮은 비트율(VLBR) 응용에서의 주요 장점이 된다. 게다가, 이러한 더욱 원활한 움직임 추정은 시간상의 보간 응용에서 보다 더 잘 수행되는 것으로 예측될 수 있다.

최종적으로, 반 화소 세밀화가 움직임 추정의 정확도를 증가시키기 위하여 사용될 때, 이러한 분류 방법 역시 계산상 절약이 이루어진다. 상기 반 화소 세밀화는 "가장자리" 블록에 대하여만 수행되며, 상대적으로 이미지의 단조로운 영역의 이미지에 대하여는 수행되지 않는다.

본 발명의 대안적인 실시예는 움직임 추정을 달성하기 위하여 M진 피라미드에서 "N-스케일 타일링"을 사용한다. 특히, 이러한 대안적인 실시예에서는, 4-레벨의 이진 피라미드가 다음;

(5)

과 같이 구성되며, 여기에서 X^l(i,j)는 l 번째 레벨의 위치(i,j)에서의 그레이 레벨을 나타내며 X₀(i,j)은 원래 이미지를 나타낸다.

다음으로, 4-레벨의 이진 피라미드 이미지는 다음;

(6)

에 따라 형성되며, 여기에서 0≤l≤2이고,

(7)

이다.

본 발명의 N-스케일 타일링 실시예가 식 7로 표현되는 피라미드의 최상위 레벨을 가지는 수정된 이진 피라미드를 사용할 수 있다는 것이 주지되어야 한다. 그러나, 본 발명의 N-스케일 타일링 실시예는 상술된 바와 같이(예컨대, 식 1, 1a 또는 2) M진 피라미드와 병행하여 구현될 수 있거나, 본 출원과 1998년 6월 29일자로 동시 출원되었으며 본 명세서에서 참조되는 출원 번호 제 09/106,706호의 "스케일링 가능한 계층적 움직임 추정을 수행하기 위한 장치 및 방법"의 제목을 가진 특허 출원서(대리인 도킷 SR 12545)에 개시된 다른 수정된 피라미드와 병행하여 구현될 수 있다.

도 11은 N-스케일 타일링을 사용하여 M진 피라미드상에서 움직임 추정을 수행하기 위한 방법(1100)의 흐름도를 도시한다. 특히, 상기 방법(1100)은 단계 1105에서 시작하여, 피라미드의 최상위 레벨에서부터 시작하는 N-스케일 타일링이 이진 피라미드(예시를 위해 M=2)에 대하여 수행되는 단계 1110으로 진행한다. 일반적으로 움직임 추정은 현재 블록(예를 들어 16*16화소의 매크로 블록)의 움직임 또는 변위를 추정하기 위해 수행되며, 전체 프레임은 오버랩핑되지 않은 다수의 현재 블록으로 나뉘어진다. 그러나, N-스케일 타일링은 도 7에 도시된 것과 같이 "N"개의 상이한 "타일링 블록" 크기를 사용하여 프레임의 현재 블록에 대한 움직임 추정을 수행하는 처리이다.

도 7은 3-스케일 타일링이 수행되는 화소 블록(710)에 대한 블록도이다. 보다 구체적으로, 블록(710)은 프레임 내의 여러 8*8 블록 중 하나이다. 바람직한 실시예에 있어서, 움직임 추정은 3개(N=3)의 상이한 블록 크기, 예를 들어 8*8 블록 크기(710), 8*4 블록 크기(720) 및 4*8 블록 크기(730)를 사용하여 수행된다. 따라서 3개의 움직임 벡터가 각각의 프레임내의 각각의 8*8 블록에 대하여 생성되며, 즉 블록은 세개의 상이한 블록 크기 또는 스케일을 사용하여 "타일링"된다.

본 발명의 바람직한 실시예에 있어서, 3-스케일 타일링(N=3)은 초기에 최상위 레벨(M진 피라미드의 최하 해상도)에서 수행되며, 이에 따라 각각의 블록에 대하여 3개의 움직임 벡터를 생성한다.

단계 1120에서, 방법(1100)은 다음 레벨이 M진 피라미드의 최하위 레벨인 지의 여부를 질의한다. 상기 질의가 부정적으로 대답되면, 상기 방법(1100)은 3개의 움직임 벡터가 하위 레벨로 전달되는, 즉 각각의 스케일에 대하여 하나의 움직임 벡터가 M진 피라미드의 낮은 레벨로 전달되는 단계 1130으로 진행한다. 이어, 방법(1100)은 낮은 레벨로 전달되는 다른 3개의 움직임 벡터를 생성하기 위하여 높은 레벨로부터 수신된 움직임 벡터에 기초하여 세밀화가 수행되는, 다음 낮은 레벨을 위한 단계 1110으로 복귀하며, 여기에서 움직임 벡터는 각각의 레벨 등에서 세밀화된다.

그러나, 단계 1120에서의 질의가 긍정적으로 대답되면, 방법(1100)은 레벨 0(M진 피라미드의 최하위 레벨(최상위 해상도))으로 전달될 단지 하나의 움직임 벡터가 레벨 1로부터 선택되는 단계 1140으로 진행한다. 레벨 0으로 전달될 레벨 1로부터 움직임 벡터를 선택하는 것은 블록에 대하여 움직임 보상된 예측 에러를 최소화하는 움직임 벡터에 기초한다. 최대 해상도에서의 목표 블록 크기는 16*16이라는 것이 주지되어야 한다. 이어, 단계 1140에서 전달된 움직임 벡터를 사용하여 최종 움직임 벡터가 각각의 16*16 블록에 대하여 단계 1150에서 결정되며 방법은 단계 1160에서 종료한다.

M진 피라미드와 병행한 N-스케일 타일링의 구현에 대한 특징은 (M=2일 때) 불 영역(Boolean domain)에서 움직임 추정을 수행할 수 있는 능력을 포함한다. 이러한 특징은 프레임 버퍼와 움직임 추정기(140) 사이의 데이터 전송 시간을 감소시킨다. 게다가, 3-스케일 타일링을 사용하여 움직임 추정을 수행하는 것은, 엔코더가 고찰중에 있는 프레임 내의 작은 특징의 움직임과 큰 구조물의 움직임을 판별하는 것을 허용한다. 예를 들어, 움직임 벡터가 작은 타일링 블록, 예를 들어 8*8 블록 대신에 4*8 또는 8*4 블록에 상관하는 현재 블록에 대하여 선택되면, 현재 블록 내의 "특징" 또는 서브블록의 움직임이 존재한다고 추론할 수 있다. 따라서, 프레임의 현재 블록에 대하여 궁극적으로 선택된 움직임 벡터와 관련하여 상이한 타일링 스케일의 기여도를 측정하기 위한 히스토그램을 셋업할 수 있다. 히스토그램은 구조 내의 큰 구조물 또는 작은 특징 등의 움직임을 유추하기 위하여 분석될 수 있다.

바람직한 실시예가 3-스케일을 사용할 지라도 스케일 개수 "N"이 상이한 블록 크기에 따라 사용될 수 있다는 것이 이해될 것이다. 게다가, 본 발명은 각각의 블록에 대하여 임의 개수의 움직임 벡터가 레벨에서 레벨로 전달될 수 있도록 수정될 수 있다.

3-스케일 타일링을 사용한 상술한 계층적 움직임 추정 방법은 식으로 표현될 수 있다. 즉, Fm을 이미지 프레임 시퀀스 내의 m번째 이미지 프레임으로 하고, 여기에서 각각의 프레임은 크기"s"의 오버랩핑되지 않은 블록으로 분할된다. 결과적인 분할 또는 타일링은 해상도 l에서

로 표현된다. 해상도 l에서 이미지 프레임(m) 내의 좌표 x=[x₁,x₂]^T를 가지는 화소의 강도 값은

로 나타내어진다. s=[s₁,s₂]^T가 주어진 경우, 이미지 위치 x에서 상부 좌측 코너의 화소 블록은

으로 언급된다. 프레임(m)의 블록(

)으로부터의 화소와 프레임(m-1)의 블록(

)내의 해당 화소 사이의 절대 차의 합(SAD:Sum of Absolute Difference)은 다음;

(8)

과 같이 표현될 수 있다. 프레임(m)의 블록(

)으로부터의 화소와 프레임(m-1)의 블록(

)내의 해당 화소 사이의 XOR 불 연산의 합(

)은 다음;

(9)

(10)

과 같이 나타내어질 수 있다.

F^0.s를 카디낼리티(cardinality) k를 가지는 최대 해상도의 이미지 상에서 정의된 타일링이라 하자. 낮은 해상도의 이미지에 대하여, 3-스케일 타일링은

,

, 및

로서 고려된다. s1=[s1/2,s2]^T 및 s2=[s1,s2/2]^T이지만 다른 나머지 블록 크기도 사용될 수 있다는 것이 주지되어야 한다.

우선 4-레벨 피라미드(0-3)레벨 중 레벨 3에서의 움직임 벡터 필드

,

및

는 다음,

과 같이 정의되며, 여기에서

Ω³={v:-d³≤v≤d³}

이며, 이때, -d³ 및 d³은 각각 -M/8 및 M/8이고 M은 탐색 윈도우 내의 화소 개수이다. 이어 레벨 2 및 레벨 1에 대하여, 낮은 해상도 l+1에서 높은 해상도l(l=2 및 l=1)까지 움직임 벡터 필터는 다음;

에 따라 전파된다. 즉, 낮은 해상도로부터의 움직임 벡터 필드는 움직임 벡터 필드에 대한 세밀화를 수행하기에 앞서 두배가 된다.

이어, 해상도 1의 움직임 벡터 필드는 다음;

과 같이 세밀화되며, 여기서,Ω_l={v:-d^l≤v ≤d^l}고 -d^l 및 d^l은 각각 -3 및 3이다.

최종적으로 레벨 0에 대하여,

Ω₀={v:-d⁰≤v≤d⁰}이고 -d⁰ 및 d⁰은 각각 -3 및 3이다.

3-스케일 타일링과 함께 이진 피라미드를 사용한 본 발명의 계층적 움직임 추정은 계산상 비싸지 않은 효율적인 움직임 추정 방법을 제공한다. 설명을 위하여, 비디오 이미지의 폭 및 높이를 각각 W와 H로 하도록 한다. 탐색 윈도우는 ±M개의 화소를 가진다. 종래의 전체-탐색 블록 매칭 방법은 단일 화소 매칭을 위하여 한번의 감산 및 1 번의 누산 및 1번의 절대값 연산을 요구한다. 따라서, 계산상의 복잡성(프레임당 연산)은 다음;

(24)

과 같이 근사화된다.

본 발명에 대하여, 동일한 전체 탐색 방법이 사용된다. 레벨 0에서의 블록 크기는 16*16이다. 8*8의 동일한 블록 크기가 레벨 1, 레벨 2 및 레벨 3에서 사용된다. 레벨 0, 레벨 1 및 레벨 2에서의 효율적인 탐색 범위는 ±3으로 설정된다. 레벨 3에서의 효율적인 탐색 범위는 ±M/8로 설정된다.

레벨 3에서, 계산상의 복잡성은 다음;

(25)

과 같이 근사화된다.

레벨 2 및 레벨 1에서, 각각의 8*8 블록은 4개의 16비트 벡터에 의해 표현될 수 있다. 16비트 XOR 불 연산은 하나의 16비트 XOR 어레이, 65536개의 엔트리를 가지는 듀얼 포트 룩업 테이블(LUT)을 사용하여 구현될 수 있다. 이어 8*8 블록은 기본 매칭을 위하여 4/64회의 누산을 요구한다. 유사하게 8*4 블록은 기본 매칭을 위하여 2/32 회의 누산을 요구한다. 이어, 레벨 2 및 레벨 1에서의 계산상 복잡성은 다음;

(26)

과 같이 근사화된다.

레벨 0에서, 16*16블록은 기본 매칭을 위하여 16/256회의 누산을 요구한다. 계산상의 복잡성은 다음;

(27)

과 같이 근사화된다.

따라서, 본 발명의 계산상 복잡성 C_HMEBP는 다음;

(28)

과 같이 근사화된다.

최종적으로, C_HMEBP와 C_FULL 사이의 비는 다음;

(29)

과 같이 표현된다.

따라서, 식(29)은 종래의 전체 탐색 방법과 비교하여 낮은 계산상 복잡성을 증명한다.

본 발명이 M진 피라미드의 최대 레벨에 걸쳐 N-스케일 타일링을 일관적으로 사용하였을지라도, 본 발명이 이에 한정되는 것이 아님을 주지하여야 한다. 실제로, N-스케일 타일링은 M진 피라미드의 각 레벨 내에서 조정될 수 있다. 즉, 상이한 N-스케일 타일링을 각 레벨 내의 상이한 세트의 블록에 대하여 사용할 수 있다. 예를 들어, 블록이 특히 중요하다면, 8*8 블록에 대하여 5스케일 타일링(예를 들어 하나의 8*8타일링 블록, 두 개의 4*8 타일링 블록 및 8*4 타일링 블록)을 사용할 수 있다. 반대로, 블록이 M진 피라미드의 동일 레벨에서 특별히 중요하지 않다면, 계산 사이클의 개수를 감소시키기 위하여 8*8블록에 대하여 1-스케일 타일링(예들 들어 하나의 8*8 타일링 블록)을 사용한다. 따라서, 상술한 블록 분류(높은 액티비티 및 낮은 액티비티)는 M진 피라미드의 각 레벨에서의 각 블록에 대하여 사용되는 N-스케일의 레벨을 규정하기 위하여 사용될 수 있다. 실제로, 다른 임의의 블록 분류 방법이 본 발명과 함께 사용될 수 있다.

대안적으로, 가변 타일링 블록 크기를 가지는 상술한 계층적 움직임 벡터 추정 방법이 도 3에 도시된 바와 같이 평균 피라미드로 구현될 수 있다. 즉, 움직임 추정은 M진 피라미드 대신에 평균 피라미드 상에서 직접 수행된다.

설명을 위하여, 평균 피라미드의 최상위 레벨에서, 움직임 추정은 고찰 중인 현재 프레임에 대한 큰 특징의 움직임과 작은 특징의 움직임을 구별하기 위하여 두 개의 상이한 블록 크기를 사용하여 수행된다. 보다 구체적으로, 4-레벨 평균 피라미드가 상술한 식(5)에 따라 구현되고, 여기에서 X^l(i,j)는 l번째 레벨의 위치(i,j)에서의 그레이 레벨을 나타내며 X⁰(i,j)는 원래 이미지를 나타낸다.

계층적 움직임 추정은 이어 평균 피라미드의 조악한 레벨로부터 미세한 레벨까지 수행된다. 최대 해상도의 16*16의 목표 블록을 가정하면, 계층적 움직임 추정은 레벨 3에서 시작하며 탐색은 두 개의 블록 크기, 예를 들어 4*4 블록 및 8*8 블록(추가된 개수의 타일링 블록 및/또는 타일링 블록 크기가 사용될 수 있다)에 대하여 수행된다.

이어 레벨 2 및 레벨 1에서, 각각의 후보 움직임 벡터가 두 개의 상이한 스케일로 세밀화되며, 각 스케일로부터의 최상의 움직임 벡터가 추가의 세밀화를 위하여 다음 레벨로 전달된다. 최종적으로, 레벨 0에서, 움직임 보상된 예측 에러의 최소화 원칙에 따라 각각의 블록에 대한 세밀화를 위한 하나의 움직임 벡터가 선택된다. 평균 피라미드 및 가변 타일링 블록 크기를 사용한 이러한 계층적 움직임 추정의 계산상 비용은 종래의 계층적 움직임 추정 방법보다는 적지만, M진 피라미드와 가변 타일링 블록 크기를 사용한 위의 계층적 움직임 추정 방법보다는 크다.

도 8은 본 발명을 병합하는 웨이브릿(wavelet)에 기초한 엔코더(800)를 도시한다. 상기 엔코더는 블록 움직임 보상기(BMC) 및 움직임 벡터 코더(804), 감산기(802), 이산 웨이브릿 변환(DWT) 코더(806), 비트율 제어기(810), DWT 디코더(812) 및 출력 버퍼(814)를 포함한다.

일반적으로, 상술한 바와 같이 입력 신호는 비디오 신호(비디오 시퀀스의 프레임을 정의하는 2차원 어레이의 화소(펠))이다. 낮은 비트율 채널을 통해 이미지를 정확하게 전송하기 위하여, 비디오 프레임 시퀀스내의 공간 및 시간적인 리던던시는 실질적으로 감소되어야 한다. 이것은 일반적으로 연속된 프레임 사이의 차이만을 코딩 및 전송함으로써, 달성된다. 엔코더는 3가지의 기능를 갖는데; 첫째, BMC 및 그것의 코더(804)를 사용하여 프레임 사이에서 발생하는 움직임을 나타내는 다수의 움직임 벡터를 생성하고; 둘째, 움직임 벡터와 조합된 재구성 버전의 이전 프레임을 사용하여 현재 프레임을 예측하고; 셋째, 예측된 프레임은 현재 프레임에서 감산되어 움직임 벡터와 함께 코딩되고 수신기로 전송될 잔여 프레임을 생성한다.

이산 웨이브릿 변환은 웨이브릿 계층적인 서브밴드의 분해를 수행하여 입력 이미지에 대한 종래의 웨이브릿 트리(wavelet tree) 표현을 형성한다. 이같은 이미지 분해를 수행하기 위하여, 이미지는 고수평-고수직(HH:high horizontal- high vertical), 고수평-저수직(HL: High horizontal- low vertical), 저수평-고수직(LL: low horizontal- high vertical) 및 저수평-저수직(LL:low horizontal- low vertical)의 주파수 서브밴드로 2배 서브샘플링을 사용하여 분해된다. 상기 LL 서브밴드는 추가로 2배 서브샘블링되어 HH, HL, LH, 및 LL 서브밴드를 형성한다. 이러한 서브샘플링은 재귀적으로 수행되어, 도 9에 도시된 것과 같은 서브밴드의 어레이를 형성하며, 도 9에는 3개의 서브샘플링이 사용되었다. 바람직하게 6개의 서브샘플링이 실제로 사용된다. 서브밴드 사이의 부모-자식 의존도는 부모 노드의 서브밴드에서 자식 노드의 서브 밴드까지를 나타내는 화살표로 도시된다. 최하위 주파수 서브밴드는 상부 좌측 LL₁에 있으며, 최상 주파수 서브밴드는 바닥 우측 HH₃에 있다. 이러한 예에 있어서, 모든 자식 노드는 하나의 부모를 가진다. 서브밴드 분해에 대한 상세한 설명은 1993년 12월의 IEEE Trans. on Signal Processing, Vol. 41, No. 12, 3445-62쪽에 J.M.Shapiro에 의해서 "웨이브릿 계수의 제로트리를 사용한 내장형 이미지 코딩"에 개시되었다.

도 8의 DWT 코더는 "폭-우선"의 패턴 또는 "깊이-우선"의 패턴으로 웨이브릿 트리의 계수를 코딩한다. 폭 우선의 패턴은 비트 플레인 패턴 단위로 웨이브릿 트리를 횡단(traverse)하는데, 즉 모든 부모 노드를 양자화한 이후에 모든 자식을 양자화하고 이어서 모든 손자를 양자화한다. 대조적으로, 깊이 우선의 패턴은 자식(상단 아래)을 통해 LL₁ 서브밴드나 또는 LL₁ 서브 밴드(바닥 위)를 통해 자식의 뿌리로부터 각각의 트리를 횡단한다. 비율 제어기(810)에 의한 적절한 양자화 레벨의 선택은 상술한 바와 같으며, 시퀀스의 각 프레임 내의 각 매크로블록에 대하여 비트율을 제어한다. 이와 같이, 본 발명은 상이한 변환을 사용하는 다양한 타입의 엔코더에 적용될 수 있다.

도 6은 본 발명의 엔코딩 시스템(600)을 도시한다. 엔코딩 시스템은 범용 컴퓨터(610) 및 다양한 입력/출력 장치(620)를 포함한다. 상기 범용 컴퓨터는 중앙 처리 장치(CPU, 612), 메모리(614) 및 이미지 시퀀스를 수신 및 엔코딩하기 위한 엔코더(616)를 포함한다.

바람직한 실시예에 있어서, 상기 엔코더(616)는 단순히 상술한 바와 같은 엔코더(100, 800)이다. 상기 엔코더(616)는 통신 채널을 통해 CPU(612)에 결합된 물리적인 장치이다. 대안적으로, 엔코더(616)는 소프트웨어 응용 (또는 소프트웨어와 하드웨어의 조합, 예를 들어 ASIC)에 의해 표현될 수 있으며, 이것은 저장 장치, 예를 들어 자기 또는 광학 디스크로부터 로드되며, 컴퓨터의 메모리(612)에 상주한다. 이와 같이, 본 발명의 엔코더(100)는 컴퓨터 판독가능 매체상에 저장될 수 있다.

컴퓨터(610)는 키보드, 마우스, 카메라, 캠코더, 비디오 모니터, 임의 개수의 이미지 생성 장치 또는 이에 한정되는 것은 아니지만 테이프 드라이브, 플로피 드라이브, 하드 디스크 또는 컴팩트 디스크 드라이브를 포함하는 저장 장치와 같은 여러 입력 및 출력 장치(620)에 결합된다. 입력 장치는 엔코딩된 비디오 비트 스트림을 생성하기 위하여 컴퓨터에 입력을 제공하고 또한 저장 장치 또는 이미지 생성 장치로부터의 비디오 이미지 시퀀스를 수신하는 역할을 한다. 최종적으로 엔코딩 시스템으로부터의 엔코딩된 신호가 (도시되지 않은) 디코딩 시스템으로 전달되도록 하는 통신 채널(630)이 도시되었다.

본 발명의 가르침을 구현하는 다양한 실시예가 본 명세서에 도시되고 설명되었을 지라고, 기술 분야의 당업자는 이러한 가르침을 구현하는 다른 변화된 실시예를 용이하게 구현할 수 있을 것이다.

Claims

이미지 시퀀스에 대하여 움직임 추정을 수행하기 위한 방법에 있어서,

(a) 상기 이미지 각각에 대하여 여러 레벨을 가지는 M진 피라미드(M-ary pyramid)를 생성하는 단계 - 여기서, 각각의 이미지는 다수의 블록들로 분할됨 - ;

(b) 다수의 타일링 블록 크기들에 기초하여 다수의 움직임 벡터들을 생성하는 단계; 및

(c) 상기 각각의 블록에 대한 상기 다수의 움직임 벡터들 중 적어도 하나를 상기 M진 피라미드의 하위 레벨로 전달하는 단계를 포함하는 것을 특징으로 하는 방법.
제 1 항에 있어서, 상기 M진 피라미드 생성 단계(a)는 상기 각각의 이미지에 대하여 이진 피라미드를 생성하는 것을 특징으로 하는 방법.
제 1 항에 있어서, 상기 M진 피라미드 생성 단계(a)는,

(a1) 이미지에 대한 평균 피라미드를 생성하는 단계; 및

(a2) 상기 평균 피라미드로부터 상기 M진 피라미드를 생성하는 단계를 포함하는 것을 특징으로 하는 방법.
제 3 항에 있어서, 상기 M진 피라미드 생성 단계(a2)는 상기 평균 피라미드의 자식 화소와 부모 화소 사이의 차이들을 양자화하는 단계를 포함하는 것을 특징으로 하는 방법.
제 4 항에 있어서, 상기 M진 피라미드는 이진 피라미드이며, 상기 이진 피라미드는,

에 따라 형성되며, 여기에서 l은 상기 M진 피라미드의 레벨이며, B^l(i,j)는 위치(i,j)에서의 값인 것을 특징으로 하는 방법.
제 1 항에 있어서, 상기 움직임 벡터들 생성 단계(b)는 상기 M진 피라미드의 최상위 레벨에서부터 상기 M진 피라미드의 하위 레벨로 계층적으로 수행되는 것을 특징으로 하는 방법.
제 6 항에 있어서, 상기 움직임 벡터들 생성 단계(b)는 상기 각각의 블록에 대한 3개의 타일링 블록 크기에 대하여 수행되어, 상기 각각의 블록에 대한 3개의 움직임 벡터를 생성하는 것을 특징으로 하는 방법.
제 1 항에 있어서, 상기 전달 단계(C)는,

(c1) 상기 M진 피라미드의 최하위 레벨보다 높은 모든 레벨에 대하여 상기 M진 피라미드의 상위 레벨로부터 각각의 블록에 대한 상기 3개의 움직임 벡터를 전달하는 단계; 및

(c2) 최하위 레벨 바로 위의 레벨로부터 각각의 블록에 대한 상기 3개의 움직임 벡터중 단지 하나의 움직임 벡터만을 상기 M진 피라미드의 최하위 레벨로 전달하는 단계를 포함하는 것을 특징으로 하는 방법.
이미지 시퀀스에 대한 움직임 추정을 수행하기 위한 장치에 있어서,

상기 각각의 이미지에 대하여 여러 레벨을 가지는 M진 피라미드를 생성하기 위한 M진 피라미드 생성기 - 여기서, 각각의 이미지는 다수의 블록들로 분할됨 -; 및

상기 M진 피라미드 상에서 계층적 움직임 추정을 수행하기 위한 움직임 추정 모듈을 포함하며,

여기서 다수의 움직임 벡터들이 다수의 타일링 블록 크기들에 따라 생성되고 상기 각각의 블록에 대한 상기 움직임 벡터들 중 적어도 하나가 상기 M진 피라미드의 하위 레벨로 전달되는 것을 특징으로 하는 움직임 추정 수행 장치.
적어도 하나의 입력 프레임을 가지는 이미지 시퀀스를 엔코딩하기 위한 장치에 있어서, 상기 장치는

다수의 블록들로 분할되는 현재 입력 프레임의 예측 이미지를 생성하기 위한 움직임 보상기;

입력 프레임과 상기 예측 이미지 사이의 차이 신호에 변환을 적용하기 위한 변환 모듈 -상기 변환은 다수의 계수를 생성함-;,

다수의 양자화된 계수를 생성하기 위해 적어도 하나의 양자화 스케일을 사용하여 상기 다수의 계수를 양자화하기 위한 양자화기; 및

상기 양자화된 계수를 비트스트림으로 코딩하기 위한 코더를 포함하며,

상기 움직임 보상기는

상기 입력 프레임에 대해 다수의 레벨을 가지는 M진 피라미드를 생성하기 위한 M진 피라미드 생성기;및

상기 M진 피라미드상에서 계층적 움직임 추정을 수행하기 위한 움직임 추정 모듈을 구비하며,

여기서, 다수의 타일링 블록 크기들에 따라 다수의 움직임 벡터들이 생성되고 상기 블록 각각에 대한 상기 움직임 벡터들 중 적어도 하나가 상기 M진 피라미드의 하위 레벨로 전달되는 것을 특징으로 하는 이미지 시퀀스 엔코딩 장치.