KR20070033345A

KR20070033345A - 전역 움직임 벡터를 검색하는 방법

Info

Publication number: KR20070033345A
Application number: KR1020067025484A
Authority: KR
Inventors: 웨이 피엔 리
Original assignee: 코닌클리케 필립스 일렉트로닉스 엔.브이.
Priority date: 2004-06-04
Filing date: 2005-05-31
Publication date: 2007-03-26
Also published as: EP1757103A1; JP2008502196A; CN1965583A; US20070223588A1; WO2005120075A1

Abstract

본 발명은 비디오 시퀀스의 화상과 관련된 전역 움직임 벡터를 검색하는 방법에 관한 것으로, 미리 정해진 축을 따라 화상들

의 투사들을 계산하는 단계(PROJ); 적어도 하나의 이전의 투사된 화상과 관련된 적어도 하나의 이전의 전역 움직임 벡터에 기초하여 현재 투사된 화상

과 관련된 현재의 전역 움직임 벡터 공식(I)의 예측

을 결정하는 단계(PRED); 상기 예측된 현재의 전역 움직임 벡터를 기초로 하여 움직임 벡터 검색 세트를 결정하는 단계(SS); 상기 미리 결정된 축을 따라 후보 움직임 벡터

의 이동된 이전의 투사된 화상(F(k-1))과 다음의 투사된 화상

사이의 왜곡값을 계산하는 단계(CAL)를 포함하며, 상기 계산 단계는, 상기 움직임 벡터 검색 세트의 상기 다른 후보 움직임 벡터들에 대해 반복되고, 상기 현재의 전역 움직임 벡터는 상기 왜곡값을 최소화하는 상기 후보 움직임 벡터가 된다.

움직임 벡터, 벡터 검색, 움직임 추정

Description

전역 움직임 벡터를 검색하는 방법{Method of searching for a global motion vector}

본 발명은 비디오 시퀀스의 화상과 관련된 전역 움직임 벡터(global motion vector)를 검색하는 방법 및 장치에 관한 것이다. 이것은 예로써, 카메라, 핸드폰, 또는 개인용 디지털 보조 수단(Personal Digital Assistant, PDA)과 같은 이동 장치들에 사용될 수 있다.

움직임 추정에 대한 종래의 접근법은 왜곡 측정에 따른 현재 블록과 몇몇의 후보 블록들의 세트 사이에서 블록 매칭을 수행하고, 그 후 가장 작은 왜곡을 나타내는 후보 블록을 선택하는 것이다. 후보 블록들은 수평 및 수직 요소들이 정수 또는 비정수인 샘플들의 어느 하나가 될 수 있는 전이 움직임으로 인해 선택된다. 움직임 벡터(MV)는 현재 화상에서의 현재 블록으로서 참조 화상에서 동일한 위치를 갖는 블록과 비교하여 참조 화상에서의 후보 블록의 상대적인 위치를 정의한다. 블록 매칭 프로세스는 현재의 화상에 포함된 현재의 블록과 참조 블록에 포함된 후보 블록 사이에서의 왜곡값을 계산하는 단계를 포함한다. 이 계산 단계는, 예로써, 이들 두 블록들 사이의 절대적인 오류 차이의 합계(SAD)를 계산하는 것에 기반한다. 종래에 있어서, 후보 블록이 발견되어야 하는 검색 영역은 미리 정해진 크기, 일반적으로 정해진 수의 행(row)을 가지며, 상기 검색 영역 내 모든 후보 블록들은 검사되어야 한다.

소위 전역 움직임 추정의 경우에 있어서, 전역 움직임 벡터는 식(1)에 보여지는 바와 같이, 수평(또는 수직) 방향에 따라 입력 화상(f)의 수평(또는 수직) 합계에 대응하는, 투사된 화상(F)에 의해 결정된다.

(1)

여기서, i는 화상의 행을 나타내고, j는 화상의 열을 나타내며, N은 화상의 행의 수를 나타내고, k는 시간을 나타낸다.

식(2)에 보여지는 바와 같이, 현재 화상

에 대한 현재의 전역 수직 움직임 벡터는 수직 축을 따라 제 1 방향으로 후보 움직임 벡터

의 이동된 이전 투사된 화상

과, 제 1 방향과 반대인 제 2 방향으로 후보 움직임 벡터

의 이동된 다음 투사된 화상

사이의 절대적인 차이의 합계(SAD)가 가장 작은 후보 수직 전역 움직임 벡터

와 동일하다.

여기서 M은 화상의 행의 수이고,

는 수직의 검색 세트이다.

식 (2)에 따르면, 최소의 절대적인 차이의 합계(SAD)를 결정하기 위해 검색 세트

내에 모든 후보 움직임 벡터

를 검사하는 것이 필요하다. 이 방법은 때때로 완전 검색(full-search) 방법이라고 불린다. 그러나, 이러한 완전 검색 방법은 고화상도 화상의 경우에 특히 비싸다.

본 발명의 목적은 종래 기술의 검색 방법보다는 덜 계산 집중적인, 전역 움직임 벡터에 대한 검색 방법을 제안하는 데 있다.

이를 위해, 본 발명에 따른 검색 방법은,

미리 결정된 축을 따라 화상들의 투사를 결정하는 단계;

적어도 하나의 이전 투사된 화상과 관련된 적어도 하나의 이전 전역 움직임 벡터를 기초로 하여 현재의 투사된 화상과 관련된 현재의 전역 움직임 벡터의 예측을 결정하는 단계;

상기 예측된 현재의 전역 움직임 벡터를 기초로 하여 움직임 벡터 검색 세트를 결정하는 단계;

상기 미리 결정된 축을 따라 이동된 후보 움직임 벡터의 이전 투사된 화상과 다음의 투사된 화상 사이의 왜곡값을 계산하는 단계로서, 상기 계산 단계는 상기 움직임 벡터 검색 세트의 다른 후보 움직임 벡터들에 대해 반복되고, 상기 현재의 전역 움직임 벡터는 상기 왜곡값을 최소화하는 상기 후보 움직임 벡터가 되는 단계를 포함하는 것을 특징으로 한다.

결과로서, 검색 세트는 단지 전역 움직임 벡터의 예측 주변에 한정된 수의 후보 움직임 벡터들만을 포함한다. 반면에 검색 세트는 하위 임계값

과 상위 임계값

사이에 포함되므로 종래 기술에서 훨씬 더 광범위하다. 그러므로, 본 발명은 검색 방법의 계산 비용을 절감할 수 있게 한다.

본 발명의 실시예에 따르면, 예측된 현재의 움직임 벡터는 이전 투사된 화상과 관련된 이전의 전역 움직임 벡터이다.

본 발명의 보다 상세한 실시예에 따르면, 예측된 현재의 전역 움직임 벡터는 이전 투사된 화상들의 세트와 관련된 이전의 전역 움직임 벡터들의 세트의 추정이다.

본 발명의 실시예에 따르면, 검색 세트는

가 예측된 전역 움직임 벡터의 값이고, n은 양수값인 범위

를 포함한다.

유익하게는, 검색 세트는 q가 0과는 다른 정수이고, 상기 움직임 벡터 후보(들)이 하위 임계값

과 상위 임계값

사이의 범위 내에서, 움직임 벡터 후보(들)

을 더 포함한다.

본 발명은 또한 본 발명에 따른 검색 방법을 수행하기 위한 장치와 관련된다.

그것은 현재 화상과 관련된 현재의 전역 움직임 벡터를 결정하기 위한 장치 및 현재의 전역 움직임 벡터를 기초로 이동 장치의 움직임을 보상하기 위한 수단으로서, 화상들의 시퀀스를 디스플레이하는 스크린을 포함하는 이동 장치와 관련한다.

본 발명은 화상들을 부호화하는 비디오 부호화기와 관련한다. 상기 부호화기는 부호화된 화상들을 제공하는 부호화부, 상기 부호화된 화상들로부터 복호화된 화상들을 제공하는 복호화부, 움직임 보상된 화상들을 전달하도록 구성된 예측부, 상기 움직임 보상된 화상들을 상기 복호화된 화상들에 부가하기 위한 가산기, 상기 예측부의 입력으로 제공되는 상기 가산기의 출력, 상기 움직임 보상된 화상들을 상기 입력 화상들로부터 감하는 감산기 및 전역 움직임 벡터들을 상기 예측부로 제공하는 장치를 포함한다.

본 발명은 마지막으로 상기 방법을 수행하는 프로그램 명령어들을 포함하는 컴퓨터 프로그램 제품과 관련한다.

본 발명의 이러한 것들 및 다른 양상들은 이하 본 명세서에서 설명된 실시예와 관련하여 분명하고, 명료해질 것이다.

본 발명은 첨부된 도면과 관련하여 예로서 보다 상세하게 설명될 것이다.

도 1은 본 발명에 따른 전역 움직임 벡터들에 대한 검색 방법의 블록도이다.

도 2는 본 발명에 따른 감소된 움직임 벡터 검색 세트의 예시도이다.

도 3은 본 발명에 따른 검색 방법을 수행하는 부호화 장치의 블록도이다.

현재, 고기능의 제품에서 소개되는 특성들은 저기능 제품 및 심지어는 이동 제품들로 이동하려는 경향이 있다. 그러나 이러한 움직임은 일반적으로 이러한 특성들의 보다 경제적인 수행 또는 시장에 맞는 몇몇의 변형들을 요구한다. 프레임 레이트 변환, 비월투사 방식의 프로그레시브 변환 및 스테디 샷(steady shot)은 저기능 및/또는 이동 제품에서 소개될 수 있는 특징들의 예이다.

본 발명은 투사된 화상들을 기초로 하는 화상들의 시퀀스 내의 전역 움직임 벡터들을 얻기 위해 요구되는 계산 전력을 감소하는 데 목적이 있다. 전체 움직임 추정의 관점에서, SAD 동작의 수는 이전에 논의된 바와 같이 후보 움직임 벡터들의 수와 동일하다. 후보 움직임 벡터들의 수는 검색 세트 및 요구된 전역 움직임 벡터들의 해상도 모두에 비례한다. 후보 움직임 벡터들의 수의 중요한 감소는 전역 움직임 벡터의 예측이 이루어질 때 실현된다. 그러므로 상기 예측을 수행하는 검색 방법은 보다 일관성있는 움직임 추정을 가능하게 한다.

본 발명에 따른 전역 움직임 벡터에 대한 검색 방법은 먼저 이전의 식(1)에 설명된 바와 같이, 수평 또는 수직의 축을 따라 입력 화상들 f(i,j)의 투사들 F(i)를 계산하는 단계(PROJ)를 포함한다.

그것은 현재 투사된 화상

과 관련된 현재의 전역 움직임 벡터

의 예측

을 결정하는 단계(PRED)를 더 포함한다. 현재의 전역 움직임 벡터의 예측은, 예로써, 적어도 하나의 이전 투사된 화상과 각각 관련된 적어도 하나의 이전의 전역 움직임 벡터에 기반한다.

본 발명의 실시예에 따르면, 현재의 전역 움직임 벡터의 예측은 이전 투사된 화상 F(k-1)과 관련된 이전의 전역 움직임 벡터

와 동일하다.

본 발명의 보다 상세한 실시예에 따르면, 현재의 전역 움직임 벡터의 예측은 이전 투사된 화상들의 세트

와 관련된 이전의 전역 움직임 벡터들의 세트

의 추정과 동일하며, 여기서 m은 1보다 정확히 큰 정수이다. 추정은, 예를 들면, 라그랑지 리니어 보외법(Lagrange linear extrapolation)에 기반한다. 더 높은 강력함은 이러한 추정 기술의 사용으로 인해 실현된다.

본 발명에 따른 방법은 현재의 전역 움직임 벡터의 예측에 기반한 움직임 벡터 검색 세트를 결정하는 단계 SS를 포함한다. 전역 움직임 벡터의 검색은 예측된 전역 움직임 벡터의 주변에 있는 지역 검색 세트에서 수행된다.

본 발명의 실시예에 따르면, 검색 세트는 초기의 검색 범위

을 포함하며, 여기서

는 움직임 벡터의 예측값이고, n은 정수이다. 이러한 경우, 검색 세트는 완전한 화소 해상도를 위한 2n+1 값을 포함한다. 전역 움직임 벡터의 정확성은 주로 초기 검색 세트의 크기, 즉, n의 값에 따른다.

n이 반드시 정수인 것은 아니라는 것을 해당 기술 분야의 당업자에게 명백한 것이다. 예를 들면, 보다 정확한 전역 움직임 추정이 요구된다면, 이것은 보간법 기술(interpolation technique)을 사용하여 서브 화소 기반에서 투사된 화상을 이동할 수 있다. 이것은 비정수인 전역 움직임 벡터가 된다.

검색 세트의 후보 움직임 벡터들이 같은 거리일 필요가 없음은 해당 기술분야에서의 당업자에게 또한 명백할 것이다. 예를 들면, 후보 움직임 벡터들 사이의 거리는 2차 방정식 또는 대수 함수에 기반할 수 있다. 이는 전역 움직임 벡터의 더 나은 튜닝이 될 것이다.

초기 검색 세트 외부의 몇몇 후보 움직임 벡터들을 선택하는 것은 방법의 강력함을 증가시킨다. 이를 위해, 검색 세트는 추가적인 후보 움직임 벡터들을 더 포함한다. 이것은 검색 방법이 실제의 전역 움직임 벡터를 수집하는 방법에 영향을 미친다. 테스트 벡터들의 세트의 예가 도 2에 주어진다. 후보 움직임 벡터들의 전체 세트는 다음의 공식에 설명되어 있다.

여기서,

는 움직임 벡터 단위로서, 비정수가 될 수 있다.

검색 세트의 추가적인 후보 움직임 벡터가 같은 거리일 필요가 없음은 해당 기술 분야에서의 당업자에게 명백할 것이다. 또한, 그것들은 이전과 같은 2차 방정식 또는 대수 함수에 기반하여 결정될 수 있다.

검색 방법의 최대 효율을 위한 최적의 후보 움직임 벡터들의 세트는 다음과 같이 계산된다.

가능한 후보 움직임 벡터들의 총 수는:

초기 검색 세트에서의 후보 움직임 벡터들의 수 :

방법의 효율성은 다음과 같다 :

최적의 검색 세트는 다음과 같이 비롯된다:

그리고, 최대 효율성은:

검색 방법은 마지막으로 수평 또는 수직의 축을 따라 이동된 후보 움직임 벡터

의 이전 투사된 화상

과 다음의 투사된 화상

사이의 왜곡값을 계산하는 단계(CAL)을 포함하며, 여기서 r은 정수 또는 널(null)인 정수이다.

예를 들면, 2의 프레임 레이트 상향 변환의 경우, 프레임은 시간의 새로운 인스턴트(중간에서의 경우)에 보간되어야 하고, 왜곡값은 식(2)에서 이전에 설명된 바와 같이, 수평 또는 수직의 축을 따라 제 1 방향으로 후보 움직임 벡터

의 이동된 이전 투사된 화상

과 제 1 방향과는 정반대인 제 2 방향으로 후보 움직임 벡터

의 이동된 다음의 투사된 화상

의 사이에서 계산된다.

이동이 대칭적일 필요가 없음은 해당 기술분야의 당업자들에게 명백할 것이다. 예를 들면, 3의 프레임 페이트 상향 변환의 경우에, 이는 원래의 프레임 시간의 각각 1/3 및 2/3에서 화상들을 보간해야 한다.

다른 예로서, 이전 투사된 화상

은 또한 현재 투사된 화상

과 관련하여 이동될 수 있다(즉, 움직이지 않은 투사된 화상). 이 방법은 예로써, 화상 안정화에 사용될 수 있는 저비용 해결책이다.

계산 단계는 움직임 벡터 검색 세트의 다른 후보 움직임 벡터들에 대해 반복되어진다. 현재의 전역 움직임 벡터는 마지막으로 왜곡값을 최소화하는 후보 움직임 벡터이다.

전체 움직임 추정은 완료 화상에서의 움직임에 대한 계량(metric)이다. 즉, 다소 동일한 움직임을 갖는 큰 또는 다수의 대상들의 평균 또는 주요한 움직임이다. 그것은 대상들 또는 카메라의 패닝(즉, 전이)의 감지에서 애플리케이션을 발견한다. 이는 스테디 샷(steady shot)으로서 카메라 시스템에 이용될 수 있으며, 이때, 서든 카메라(sudden camera) 움직임들은 보상된다. 디스플레이 시스템에 있어서, 그것은 디-인터레이싱(de-interlacing) 또는 프레임 레이트 상향 변환(frame-rate up-conversion)에 대한 움직임 추정을 위해 개선(refinement)으로서 팬-줌 모델(pan-zoom model)의 일부가 될 수 있다.

그러한 것으로서 상기 움직임 추정은, 시퀀스의 화상들의 적절한 분할을 통해 비디오 시퀀스의 움직임을 보상하는 데 충분하다. 도 3에서는 비디오 부호화기의 예를 도시하고 있다. 이러한 비디오 부호화기는 입력 분할된 화상들 f로부터 양자화된 분할된 화상들을 생성하기에 적합한 양자화 블록(Q)을 갖는 직접적인 주파수 변경 블록을 연속하여 포함하는 제 1 블록(T/Q)과, 양자화된 분할된 화상들로부터 부호화된 분할된 화상들(BS)을 생성하는 데 적합한 엔트로피 코딩 블록(EC)을 포함한다.

비디오 부호화기는 또한 역 양자화 블록(IQ)과 복호화된 분할된 화상들을 제공하는 역 주파수 변경 블록(IT)을 연속하여 포함하는 복호화부를 포함한다.

부호화기는 움직임 보상된 분할된 화상들을 생성하기 위한 움직임 보상부(MC)를 갖는 이미지 메모리(MEM)를 연속하여 포함하는 예측부를 포함한다. 이것은 복호화된 분할된 화상들을 움직임 보상된 분할된 화상에 부가하기 위한 가산기와 움직임 보상된 분할된 화상들을 입력 분할된 화상들 f로부터 감하는 감산기를 포함하고, 이때 감산기의 결과는 블록(T/Q)으로 전달된다. 비디오 부호화기는 마지막으로 전역 움직임 벡터들을 예측부로 제공하기 위해 본 발명에 따른 전체 움직임 추정 장치를 포함한다.

본 발명의 몇몇 실시예는 단지 예로써 상기 설명되었고, 변형 및 변경들이 첨부된 청구항에 의해 정의된 바와 같은 발명의 영역으로부터 벗어나지 않고 변형 설명된 실시예로써 이루어질 수 있음이 해당 기술분야의 당업자에게 명백할 것이 다. 또한, 청구항에서, 소괄호 사이에 위치된 임의의 참조 표시는 청구항을 한정하는 것으로 해석되어서는 안된다. 용어 "포함하는"은 청구항에 열거된 것들과는 다른 요소들 또는 단계들의 존재를 배제하지 않는다. 용어들의 단위 표현은 복수 개를 배제하지 않는다. 본 발명은 몇몇의 별개의 요소들을 포함하는 하드웨어 및 적절하게 프로그래밍된 컴퓨터에 의해서 수행될 수 있다. 몇몇의 수단을 열거하는 장치 청구항에서, 이러한 몇몇의 수단들은 하드웨어의 하나 및 동일한 아이템에 의해 구체화될 수 있다. 측정들이 상호 다른 독립 청구항에서 인용된 단순한 사실은 이러한 측정의 조합이 이점으로서 사용될 수 없음을 나타내지 않는다.

Claims

비디오 시퀀스의 화상과 관련된 전역 움직임 벡터(global motion vector)를 검색하는 방법에 있어서,

미리 정해진 축을 따라 화상들(f)의 투사들을 계산하는 단계(PROJ);

적어도 하나의 이전 투사된 화상과 관련된 적어도 하나의 이전 전역 움직임 벡터에 기초하여 현재 투사된 화상(F(k))과 관련된 현재의 전역 움직임 벡터
의 예측
을 결정하는 단계(PRED);

상기 예측된 현재의 전역 움직임 벡터에 기초하여 움직임 벡터 검색 세트를 결정하는 단계(SS);

상기 미리 결정된 축을 따라 후보 움직임 벡터
의 이동된 이전 투사된 화상
과 다음의 투사된 화상
사이의 왜곡값을 계산하는 단계(CAL)로서, 상기 계산하는 단계는 상기 움직임 벡터 검색 세트의 다른 후보 움직임 벡터들에 대해 반복되고, 상기 현재의 전역 움직임 벡터는 상기 왜곡값을 최소화하는 상기 후보 움직임 벡터가 되는, 상기 계산 단계를 포함하는, 전역 움직임 벡터 검색 방법.
제 1 항에 있어서,

상기 예측된 현재의 전역 움직임 벡터는 상기 이전 투사된 화상
과 관련된 상기 이전의 전역 움직임 벡터
인, 전역 움직임 벡터의 검색 방법.
제 1 항에 있어서,

상기 예측된 현재의 전역 움직임 벡터는 이전의 투사된 화상들의 세트와 관련된 이전의 전역 움직임 벡터들의 세트에 대한 추정인, 전역 움직임 벡터의 검색 방법.
제 1 항에 있어서,

상기 검색 세트는
가 상기 예측된 전역 움직임 벡터이고, n은 양수인 범위
를 포함하는, 전역 움직임 벡터의 검색 방법.
제 4 항에 있어서,

상기 검색 세트는 q가 0과는 다른 정수이고, 상기 움직임 벡터 후보(들)이 하부의 임계값과 상부의 임계값 사이에 있는 범위 내에서, 움직임 벡터 후보(들) (
)을 더 포함하는, 전역 움직임 벡터의 검색 방법.
비디오 시퀀스의 화상과 관련된 전역 움직임 벡터를 검색하는 장치에 있어서,

미리 결정된 축을 따라 화상들의 투사들을 계산하는 수단;

적어도 하나의 이전 투사된 화상과 관련된 적어도 하나의 이전 전역 움직임 벡터를 기초로 하여 현재 투사된 화상과 관련된 현재의 전역 움직임 벡터를 예측하는 수단;

상기 예측된 현재의 전역 움직임 벡터를 기초로 움직임 벡터 검색 세트를 결정하는 수단; 및

상기 미리 결정된 축을 따라 후보 움직임 벡터의 이동된 이전 투사된 화상과 다음의 투사된 화상 사이의 왜곡값을 계산하는 수단으로서, 상기 계산은 상기 움직임 벡터 검색 세트의 상기 다른 후보 움직임 벡터들에 대해 반복되고, 상기 현재의 전역 움직임 벡터는 왜곡값을 최소화하는 상기 후보 움직임 벡터가 되는, 상기 계산 수단을 포함하는, 전역 움직임 벡터 검색 장치.
이동 장치로서,

화상들의 시퀀스를 디스플레이하기 위한 스크린;

현재의 화상과 관련된 현재의 전역 움직임 벡터를 결정하기 위한 제 6 항에 청구된 장치; 및

상기 현재의 전역 움직임 벡터를 기초로 상기 이동 장치의 움직임을 보상하기 위한 수단을 포함하는, 이동 장치.
화상들(f)을 부호화하는 비디오 부호화기에 있어서,

부호화된 화상들(BS)을 제공하는 부호화부(T/Q, EC);

상기 부호화된 화상들로부터 복호화된 화상들을 제공하는 복호화부(IQ/IT);

움직임 보상된 화상들을 전달하도록 구성된 예측부(MEM, MC);

상기 움직임 보상된 화상들을 상기 복호화된 화상들에 부가하는 가산기로서, 상기 가산기의 출력을 상기 예측부의 입력으로 제공하는 가산기;

상기 움직임 보상된 화상들을 상기 입력 화상들로부터 감하는 감산기; 및

전역 움직임 벡터들을 상기 예측부에 제공하는 제 6 항에 청구된 장치를 포함하는, 비디오 부호화기.
프로그램이 프로세서에 의해 실행될 때, 제 1 항에 청구된 방법을 수행하기 위한 프로그램 명령어들을 포함하는, 컴퓨터 프로그램 제품.