모션 추정 검색 범위 및 확장된 모션 벡터 범위의 동적 선택 방법, 및 인코더 document_id A220623066543

디지털 비디오는 많은 양의 저장 및 전송 용량을 소비한다. 통상의 미처리(raw) 디지털 비디오 시퀀스는 초당 15 또는 30 프레임을 포함한다. 각각의 프레임은 수만 또는 수십만 개의 픽셀(펠(pel)이라고도 함)을 포함하며, 각각의 픽셀은 픽처의 작은 요소를 표현한다. 미가공 형태에서, 컴퓨터는 일반적으로 픽셀을 총 24 비트인 3 샘플의 세트로서 표현한다. 따라서, 미처리 디지털 비디오 시퀀스의 초당 비트 수 또는 비트 레이트는 초당 5백만 비트 이상일 수 있다. 많은 컴퓨터 및 컴퓨터 네트워크는 미처리 디지털 비디오를 처리하기 위한 자원이 부족하다. 이 때문에, 엔지니어들은 디지털 비디오의 비트 레이트를 줄이기 위해 압축(코딩 또는 인코딩이라고도 함)을 이용한다. 압축은 비디오를 보다 낮은 비트 레이트 형태로 변환함으로써 비디오의 저장 및 전송 비용을 줄인다. 신장(디코딩이라고도 함)은 압축된 형태로부터 오리지널 비디오의 버전을 재구성한다. "코덱"은 인코더/디코더 시스템이다. 압축이 무손실이어서 비디오의 품질이 저하되지 않을 수 있지만, 비트 레이트의 감소는 비디오 데이터의 가변성(때때로 엔트로피라고 함)의 고유 양에 의해 제한된다. 또는, 압축은 손실이 있어서 비디오의 품질이 저하될 수 있지만, 달성 가능한 비트 레이트의 감소는 더 크다. 유손실 압축은 종종 무손실 압축과 함께 이용되는데, 유손실 압축은 정보의 근사값을 확보하며, 무손실 압축은 근사값을 표현하기 위해 적용된다. 유손실 압축의 기본 목표는 양호한 레이트 왜곡(rate-distortion) 성능을 제공하는 것이다. 따라서, 특정 비트 레이트에 대해, 인코더는 최고 품질의 비디오를 제공하려고 시도한다. 또는, 오리지널 비디오에 대한 특정 레벨의 품질/충실도에 대해, 인코더는 최저 비트 레이트의 인코딩된 데이터를 제공하려고 시도한다. 실제로는, 인코딩 시간, 인코딩 복잡성, 인코딩 자원, 디코딩 시간, 디코딩 복잡성, 디코딩 자원, 전체 지연, 및/또는 품질/비트 레이트 변화의 유연성과 같은 고려 사항들 또한, 코덱 설계시에 행해지는 결정들은 물론, 실제 인코딩 동안 행해지는 결정들에 영향을 미친다. 일반적으로, 비디오 압축 기술들은 "인트라 픽처" 압축 및 "인터 픽처" 압축을 포함한다. 인트라 픽처 압축 기술들은 개별 픽처들을 압축하며, 인터 픽처 압축 기술들은 선행 및/또는 후속 픽처(종종 참조 또는 앵커 픽처라고 함) 또는 픽처들을 참조하여 픽처들을 압축한다. 인터 픽처 압축 기술들은 종종, 비디오 시퀀스 내의 시간 중복을 이용함으로써 비트 레이트를 줄이기 위해 모션 추정 및 모션 보상을 이용한다. 모션 추정은 픽처들 사이의 모션을 추정하기 위한 프로세스이다. 하나의 일반적인 기술에서, 모션 추정을 이용하는 인코더는 현재 픽처 내의 현재 샘플들의 블록과, 참조 픽처인 다른 픽처 내의 검색 영역 내의 동일 크기의 후보 블록을 매칭시키려고 시도한다. 인코더가 참조 픽처 내의 검색 영역에서 정확한 또는 "충분히 근접한" 매칭을 발견하는 경우, 인코더는 현재 및 후보 블록들 사이의 위치 변화를 모션 데이터(모션 벡터("MV") 등)로서 파라미터화한다. 통상적으로, 모션 벡터는 좌측 또는 우측 공간 변위를 나타내는 수평 성분 및 상향 또는 하향 공간 변위를 나타내는 수직 성분을 갖는 2차원 값이다. 일반적으로, 모션 보상은 모션 데이터를 이용하여 픽처들을 참조 픽처(들)로부터 재구성하는 프로세스이다. 도 1은 예시적인 인코더에서의 예측 픽처의 일부에 대한 모션 추정을 나타낸다. 8x8 샘플 블록, 16x16 블록(종종 "매크로블록"이라 함) 또는 다른 단위의 현재 픽처에 대해, 인코더는 예측자로서 사용하기 위해 참조 픽처에서 유사한 단위를 찾는다. 도 1에서, 인코더는 현재 예측 픽처(110)에서 16x16 매크로블록(115)에 대한 모션 벡터를 계산한다. 인코더는 참조 픽처(130)의 검색 영역(135)에서 검색한다. 검색 영역(135) 내에서, 인코더는 예측 픽처(110)의 매크로블록(115)을 다양한 후보 매크로블록과 비교하여 양호하게 매칭되는 후보 매크로블록을 발견한다. 인코더는 예측자 매크로블록에 대한 모션 벡터를 상술하는 정보를 출력한다. 인코더는 오차(에러 신호라고도 함)를 결정하기 위해 현재 단위와 그의 모션 보상 예측치 간의 샘플마다의 차이를 계산한다. 오차는 주파수 변환되고, 양자화되고, 엔트로피 인코딩된다. 선형 에너지 집중(energy-compacting) 변환으로서, 주파수 변환은 에너지가 보다 낮은 주파수 계수들에 집중되는 변환 계수들을 생성하는 경향이 있다. 예측 픽처의 전체 비트 레이트는 오차들의 비트 레이트에 크게 의존한다. 오차들이 간단하거나(즉, 정확하거나 양호한 매칭들을 발견하는 모션 추정으로 인해) 유손실 압축이 오차들의 복잡성을 크게 줄이는 경우에, 오차들의 비트 레이트는 낮다. 성공적인 모션 추정으로 절약된 비트들은 다른 곳에서 품질을 향상시키거나 전체 비트 레이트를 줄이는 데 사용될 수 있다. 한편, 복잡한 오차들의 비트 레이트는 더 높을 수 있으며, 오차들의 복잡성을 줄이기 위해 적용되는 유손실 압축의 정도에 의존한다. 예측 픽처가 후속 모션 보상을 위한 참조 픽처로서 사용되는 경우, 인코더는 예측 픽처를 재구성한다. 오차들을 재구성할 때, 인코더는 역 양자화를 이용하여 양자화된 변환 계수들을 재구성하고 주파수 역변환을 수행한다. 인코더는 모션 보상을 수행하여 모션 보상된 예측자들을 계산하며, 예측자들을 재구성된 오차들과 결합한다. 통상적으로 인코더들은 인코딩 시간의 많은 부분을, 모션 추정을 수행하여 양호한 매칭들을 발견함으로써 레이트 왜곡 성능을 향상시키려고 시도하는 데 소비한다. 일반적으로, 참조 픽처 내의 큰 검색 범위의 사용은 인코더가 양호한 매칭을 발견하는 기회를 향상시킨다. 그러나, 인코더는 잠재적으로 현재 블록을 큰 검색 범위 내의 모든 가능한 공간적으로 변위된 블록과 비교한다. 대부분의 시나리오에서, 인코더는 인코딩될 모든 블록 또는 매크로블록에 대해 큰 검색 범위 내의 모든 가능한 모션 벡터를 검사하기 위한 시간 또는 자원들이 부족하다. 특히, 코덱이 큰 변위들에 대한 모션 벡터들을 허가하는 경우, 최상의 모션 벡터에 대한 큰 검색 범위를 통한 검색의 계산 비용은 인코딩될 콘텐츠가 고화질 비디오일 때 특히 엄청날 수 있다. 다양한 기술들은 인코더들이 모션 추정을 고속화하는 것을 돕는다. 일 유형의 기술에서, 사용자 설정, 프로파일 설정, 또는 레벨 설정은 모션 벡터 범위를 특정 크기로 직접 설정한다. 모션 벡터 범위는 모션 벡터들의 허가된 크기들을 지시한다. 이와 달리 참조 픽처에 대해 전반적인 검색을 수행하는 인코더에 대해, 모션 벡터 범위는 모션 벡터 범위 밖의 모션 벡터들을 배제함으로써 검색 범위를 사실상 제한한다. 사용자는 명령 라인 파라미터, 사용자 인터페이스 제어 등을 이용하여 모션 벡터 범위를 설정하여, 디폴트 값을 무효화한다. 예를 들어, 고품질의 오프라인 인코딩을 위해, 큰 모션 벡터 범위(따라서, 큰 검색 범위)가 사용된다. 또한, 저품질의 실시간 인코딩을 위해, 보다 작은 모션 벡터 범위(따라서 보다 작은 검색 범위)가 사용된다. 이러한 설정들은 인코딩 시간 및 자원들에 대한 문제를 해결하지만, 이들은 모션 벡터 범위 또는 검색 범위를 인코딩되는 비디오 콘텐츠의 모션 특성 변화에 적응시키지 못한다는 점에서 유연성이 없다. 결과적으로, 소정의 시나리오들에서, 큰 모션 벡터 범위 및 검색 범위는 일련의 로우 모션(low-motion) 픽처들에 대해 불필요하다. 또한, 작은 모션 벡터 범위 및 검색 범위는 일련의 하이 모션(high-motion) 픽처들에 대해 부적합하다. 계층적 모션 추정에서, 인코더는 (예를 들어, 4:1 다운샘플링된 픽처들을 이용하여) 저 해상도에서 하나 이상의 모션 벡터를 찾고, 모션 벡터(들)를 보다 높은 해상도(예를 들어, 정수 픽셀)로 스케일 업하고, 스케일 업된 모션 벡터(들) 주위의 이웃(들)에서 보다 높은 해상도에서 하나 이상의 모션 벡터를 찾는 것 등을 행한다. 이것은 인코더가 보다 높은 해상도에서의 소모적인 검색을 생략할 수 있게 하지만, 저 해상도에서의 검색을 정당화할 모션이 없거나 거의 없는 경우에는 낭비적인 긴 저해상도 검색에 이를 수 있다. 이러한 계층적 모션 추정 또한, 모션 벡터 범위 및 검색 범위를 인코딩되는 비디오 콘텐츠에서의 모션 특성 변화에 적응시키지 못한다. 다른 인코더들은 픽처의 현재 블록 또는 매크로블록에 대한 모션 추정을 수행할 때 동일 픽처 내의 공간적으로 바로 인접한 블록들의 모션 벡터들을 고려함으로써 검색 범위를 동적으로 조정한다. 이러한 인코더들은 현재 블록 또는 매크로블록에 대한 모션 벡터 검색 프로세스를 치밀하게 집중시킴으로써 모션 추정을 크게 고속화한다. 그러나, 소정의 시나리오들(예를 들어, 강한 국지화된 모션, 불연속 모션 또는 다른 복잡한 모션)에서, 이러한 모션 추정은 적절한 성능을 제공하지 못할 수 있다. 일반적으로, 인코더들은 모션 추정 동안 왜곡 메트릭(distortion metric)을 이용한다. 왜곡 메트릭은 인코더가 모션 추정 선택에서의 후보 블록의 사용과 연관된 품질 및 레이트 비용들을 평가하는 것을 돕는다. 하나의 일반적인 왜곡 메트릭은 절대차들의 합("SAD")이다. 참조 픽처 내의 후보 블록에 대한 SAD를 계산하기 위해, 인코더는 현재 및 후보 블록들 간의 오차의 절대값들의 합을 계산하는데, 여기서의 오차는 현재 블록과 후보 블록 간의 샘플마다의 차이이다. 낮은 계산 복잡성은 SAD의 이점이다. 그러나, SAD는 소정의 사례들에서 전체 레이트 왜곡 비용의 부정확한 근사치이다. 특히, 현재 블록과 후보 블록 간에 크지만 균일한 샘플 차이들이 존재하는 경우에, SAD는 실제 왜곡을 부정확하게 근사화한다. SAD는 오차들에 대해 수행되는 주파수 변환들의 에너지 집중 효과들을 설명하지 못한다. 현재 블록이 후보 블록에 비해 크지만 균일한 샘플 값들의 차이들을 갖는 것으로 가정한다. 아마도, 인코딩 동안의 주파수 변환은 0이 아닌 DC 계수 값에서의 균일한 샘플 차이들을 캡처하여 격리할 것이다. (DC 계수는 최저 주파수 변환 계수이다.) 에너지 집중 효과들로 인해, 후보 블록 선택의 전체 레이트 왜곡 비용은 아마도 작다. 그러나, SAD는 큰 비용을 부정확하게 나타낸다. 따라서, 소정의 비디오 인코더들은 절대 하다마드 변환 차이들의 합("SAHD")을 왜곡 메트릭으로 이용하거나, 다른 절대 변환 차이들의 합("SATD")을 메트릭으로 이용한다. 참조 픽처 내의 후보 블록에 대한 SAHD를 계산하기 위하여, 인코더는 현재 블록을 하다마드 변환하고, 후보 블록을 하다마드 변환한 후, 하다마드 변환 블록들 간의 차이들의 절대값들의 합을 계산한다. 또는, 인코더는 오차를 계산하고, 오차를 하다마드 변환하고, 하다마드 변환된 오차의 절대값들의 합을 계산한다. 나중에 압축에서 사용되는 주파수 변환은 종종 하다마드 변환이 아니다. 오히려, 하다마드 변환은 인코더가 나중에 오차들에 대해 사용하는 주파수 변환의 에너지 집중을 근사화하지만, 하다마드 변환은 계산하기가 더 간단하다. SAHD는 균일한 전체 샘플값 시프트들을 설명하므로, 모션 추정에서 SAHD를 사용하는 것은 종종 SAD를 사용하는 것보다 레이트 왜곡 성능을 향상시키지만, SAHD를 사용하는 것은 또한 계산 복잡성을 증가시킨다. 단일 하다마드 변환이 비교적 간단하지만, 왜곡 메트릭을 계산할 때 하다마드 변환을 수행하는 것은 모션 추정의 전체적인 계산 복잡성을 크게 증가시키는데, 이는 통상적으로 인코더들이 인코딩 시간의 많은 부분을 모션 추정 동안 상이한 후보 블록들을 평가하는 데 소비하기 때문이다. 제곱 에러들의 합("SSE"), 평균 제곱 에러("MSE") 및 평균 분산은 다른 왜곡 메트릭들이다. SSE에서, 인코더는 오차의 값들을 제곱한 후에 제곱 값들을 합한다. MSE에서, 인코더는 제곱 값들의 평균을 계산한다. 평균 분산의 하나의 정의는 다음과 같다. 여기서, 는 오차 내의 I 오차 값들 의 평균이다. 평균 분산은 현재 블록과 후보 블록 간의 전반적인 차이들을 어느 정도 설명한다. SSE, MSE 및 평균 분산은 소정 사례들에서 수용 가능한 레이트 왜곡 성능을 산출하지만, 왜곡을 측정하는 계산의 복잡성을 증가시킨다. 소정의 디코더들은 모션 추정 동안 레이트 왜곡 비용을 왜곡 메트릭으로서 계산한다. 레이트 왜곡 비용은 왜곡 항 및 레이트 항을 가지며, 하나의 팩터(종종 라그랑지 승수라고 함)가 레이트 항을 왜곡 항에 대해 스케일링한다. 레이트 항은 모션 벡터 정보 및/또는 오차 정보에 대한 추정된 또는 실제의 비트 레이트 비용일 수 있다. 왜곡 항은 오리지널 샘플들과 재구성된 샘플들(주파수 변환, 양자화, 역 양자화, 및 주파수 역변환에 이어서 재구성된 샘플들)의 비교에 기초할 수 있다. 또는, 왜곡 항은 소정의 다른 왜곡 크기 또는 추정치일 수 있다. 레이트 왜곡 비용은 통상적으로 상이한 모션 추정 선택들의 레이트 왜곡 성능의 가장 정확한 평가를 제공하지만, 특히 상이한 양자화 파라미터들이 각각의 상이한 모션 추정 선택에 대해 평가되는 경우에 최고의 계산 복잡성을 또한 갖는다. 대부분의 경우에, 인코더는 모션 추정 전반에서 동일한 왜곡 메트릭을 사용한다(예를 들어, SAD만을 사용하거나, SAHD만을 사용한다). 이것은 유연하지 않으며, 사용되는 메트릭에 따라서는 계산이 비효율적이거나 열악한 레이트 왜곡 성능에 이를 수 있다. 다른 하나의 접근법은 모션 추정에서 SAD를 이용하여 상위 x개 후보 모션 벡터들을 발견한 후에 레이트 왜곡을 이용하여 상위 x개 후보 모션 벡터들의 각각을 평가하는 것이다. 예를 들어, 상위 3개 후보가 레이트 왜곡 비용을 이용하여 평가된다. 이것은 모션 추정의 시작부터 레이트 왜곡 비용을 이용하는 계산 비용을 피하지만, 소정의 사례들에서 인코더는 SAD의 결여로 인해 양호한 후보들을 놓치는 대신에, 열악한 후보들을 선정하게 된다. 인코더가 시작에서 상위 x개 후보에 대해 SAHD를 이용한 후에 레이트 왜곡 비용을 이용하는 경우, 인코더는 양호한 후보들을 발견할 가능성이 크지만, 계산 복잡성은 크게 증가한다. 또 다른 접근법에서, 인코더는 계층적 모션 추정의 정수 픽셀 단계에서 SAD를 이용하고, 계층적 모션 추정의 1/2 픽셀 및 1/4 픽셀 단계들에서 SAHD를 이용한다. 또한, 이것은 모션 추정의 시작부터 SAHD를 이용하는 계산 비용을 피하지만, 많은 경우에 인코더는 SAD의 결여로 인해 양호한 후보들을 놓친다. 이러한 기술들과 별도로, 많은 인코더는 수용 가능한 양의 시간 내에 양호한 매칭을 발견할 가능성이 있는 것으로 간주되는 특수화된 모션 벡터 검색 패턴들 또는 다른 전략들을 이용한다. 모션 추정을 고속화하거나 향상시키기 위한 다양한 다른 기술이 개발되어 왔다. 디지털 비디오에 대한 비디오 압축의 임계적인 중요성을 가정하면, 모션 추정이 충분히 개발된 분야임은 놀랄만한 것이 아니다. 그러나, 종래의 모션 추정 기술들의 이익들이 무엇이든 간에, 이들은 아래의 기술들 및 도구들의 이점들을 갖지 못한다. 003c#발명의 요약003e# 본 출원은 모션 추정 동안 검색 범위들 및/또는 모션 벡터 범위들을 선택하기 위한 기술들 및 도구들에 관한 것이다. 예를 들어, 비디오 인코더는 이전 픽처의 모션 벡터들에 대한 모션 벡터 분포 정보를 이용하여 현재 픽처에 대한 모션 벡터 범위를 선택한다. 많은 경우에, 모션 벡터 범위는 현재 픽처에 대한 모션 추정의 검색 범위를 사실상 제한한다. 이러한 방식으로, 비디오 인코더는 다양한 모션 레벨을 갖는 비디오 시퀀스들에 대한 모션 추정의 성능을 향상시킨다. 설명되는 기술들 및 도구들의 제1 양태에 따르면, 비디오 인코더는 제1 검색 범위에 의해 제한되는 모션 추정을 수행하며, 이는 다수의 모션 벡터를 생성한다. 인코더는 모션 벡터들에 대한 모션 벡터 분포 정보를 계산한다. 예를 들어, 인코더는 히스토그램에서 모션 벡터들을 추적하고, 분포 정보를 위해 얼마나 많은 모션 벡터들이 다수의 인터벌 각각 내에 있는지를 카운트한다. 이어서, 인코더는 제2 검색 범위를 선택하고, 제2 검색 범위에 의해 제한되는 모션 추정을 수행한다. 설명되는 기술들 및 도구들의 제2 양태에 따르면, 비디오 인코더는 제1 모션 벡터 범위 및 제1 검색 범위에 의해 제한되는 모션 추정을 수행한다. 인코더는 제1 모션 벡터 범위 및 모션 추정의 결과들을 비디오 비트 스트림 내에서 시그널링한다. 제2 모션 벡터 범위를 선택한 후, 인코더는 제2 모션 벡터 범위 및 제2 검색 범위에 의해 제한되는 모션 추정을 수행한다. 인코더는 제2 모션 벡터 범위 및 제2 모션 추정의 결과들을 비디오 비트 스트림 내에서 시그널링한다. 설명되는 기술들 및 도구들의 제3 양태에 따르면, 인코더는 모션 추정을 수행하기 위한 모션 추정기, 주파수 변환기, 양자화기, 엔트로피 인코더, 및 모션 추정을 제한하는 검색 범위들을 선택하기 위한 모션 추정 제어기를 포함한다. 현재 픽처에 대해, 상기 선택은 다수의 이전 모션 벡터에 대한 모션 벡터 분포 정보에 적어도 부분적으로 기초한다. 이 요약은 개념들의 선택을 간단한 형태로 소개한다. 개념들은 아래의 상세한 설명에서 더 설명된다. 이 요약은 본 발명의 중요한 특징들 또는 본질적인 특징들을 식별하고자 하는 의도도 없고, 본 발명의 범위를 제한하는 데 사용하고자 하는 의도도 없다. 상기 및 다른 목적들, 특징들 및 이점들은 첨부된 도면들을 참조하여 진행되는 아래의 상세한 설명으로부터 보다 명확해질 것이다.