KR100859073B1 - 움직임 추정 방법 - Google Patents

Abstract

본 발명은 움직임 추정 방법에 관한 것으로, 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성하는 단계와, 찾고자 하는 대상 블록의 주파수 신호 특성에 따라 평균 피라미드 중에서 어느 하나의 레벨을 탐색 레벨로 설정하는 단계와, 탐색 레벨에서 최소의 블록 정합 차이값을 가지는 후보 지점을 설정하는 단계와, 설정한 후보 지점에 대하여 평균 피라미드 중에서 최하위 레벨에서 움직임 벡터를 찾는 단계를 포함하며, 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입해 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 이점이 있다.

움직임 추정, 움직임 보상, 이미지 부호화, 움직임 벡터

Description

움직임 추정 방법{MOTION ESTIMATION METHOD}

도 1은 본 발명에 따른 움직임 추정 방법이 적용된 비디오 부호화기의 일 예를 보인 구성도,

도 2는 움직임 추정 방법 중에서 TSS 방법에 의한 움직임 추정 과정을 보여주는 도면,

도 3은 움직임 추정 방법 중에서 BS 방법에 의한 움직임 추정 과정을 보여주는 도면,

도 4는 움직임 추정 방법 중에서 계층적 블록 정합 방법에 의한 움직임 추정 과정을 보여주는 도면,

도 5는 본 발명에 따른 움직임 추정 방법에 의한 움직임 추정 과정을 보여주는 도면,

도 6은 본 발명에 따른 움직임 추정 방법을 단계별로 설명하기 위한 흐름도.

본 발명은 움직임 추정에 관한 것으로, 더욱 상세하게는 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입한 움직임 추정 방법 에 관한 것이다.

일반적으로 동영상 정보를 처리하는 시스템은 비디오 부호화기를 사용하며, 비디오 부호화기는 비디오 신호의 움직임을 추정하여 비디오 신호를 처리한다. 비디오 신호의 움직임 추정은 인접한 프레임간의 시간적 중복성을 제거하여 높은 압출율을 얻을 수 있는 방법이다.

움직임 보상기법은 움직임 추정기법을 통하여 입력 비디오 신호의 가장 유사한 영상신호를 시간적으로 이전 프레임으로부터 예측하고, 예측된 비디오 신호와 입력 비디오 신호와의 차를 변환 부호화하는 방법이다.

현재 MPEG-2, MPEG-4, H.263과 H.264를 포함하는 대부분의 비디오 코딩 표준은 움직임 보상 예측 코딩법에 기초하고 있는데, 시간적 중복은 움직임 보상에 의해 제거하고 공간적 중복은 변환 코딩에 의해 제거한다.

시간적 중복을 제거하는 과정을 좀더 자세히 살펴보면, 프레임을 구성하는 구성단위, 예를 들면 각 매크로 블록(Macro Block)이 다음 시간의 프레임에서 해당 매크로 블록의 위치가 얼마만큼 이동했는지를 나타내는 움직임 추정치(Motion Vector)를 구하는 움직임 추정(Motion Estimation)을 한다. 움직임 추정이 끝나면 움직임 보상(Motion Compensation)을 하여 시간적 필터링(Filtering)을 통해 프레임간 시간적 중복성을 제거한다.

이러한 시간적 중복을 제거하는 과정은 매우 많은 연산을 필요로 하는데, 연산량을 줄이기 위한 여러 알고리즘들이 제안되고 있다. 크게 움직임 벡터 후보점의 갯수를 줄이는 방법을 통해서 계산을 줄이는 방법이 있고, 블록 정합 코스트 계산 을 통해서 줄이는 방법이 있으며, 움직임 벡터의 서브 샘플링 방법이 있다.

움직임 추정을 위한 기법의 여러 가지 알고리즘들 중에서 블록 정합 알고리즘(Block Matching Algorithm: BMA)이 계산에 있어서 비교적 간단하기 때문에 가장 많이 사용된다. 블록 정합 알고리즘은 이전 프레임의 탐색 영역내에서 현재 블록의 가장 유사한 블록을 찾는 방법이다. 기본적인 방법인 전역 탐색 블록 정합 알고리즘(Full Search Block Matching Algorithm: FSBMA)은 성능면에서 최적이지만 계산량이 많고 하드웨어 부담이 커진다는 단점이 있으므로 계층적 블록 정합 알고리즘(Hierarchical Search Block Matching Algorithm: HSBMA)과 같은 고속 알고리즘을 사용하게 된다.

계층적 블록 정합 알고리즘 기법은 입력영상과 이전영상을 몇 단계의 해상도 영상으로 나누어 움직임 추정을 하는 방법으로서 기본 아이디어는 우선 저해상도의 영상으로부터 큰 스케일의 움직임 벡터 후보를 얻은 후 고해상도 영상에서 최적의 움직임 벡터를 찾는 기법이다.

그런데, 기존의 계층적 블록 정합 알고리즘 기법 또한 비교적 계산량이 많아서 움직임 추정을 위한 동작시간이 많이 걸리고 전력소모가 많은 문제가 있었다. 움직임 추정은 동영상 압축의 성능에 매우 중요한 역할을 하지만 계산량이 많기 때문에 실시간 동영상 인코딩을 위해서는 움직임 추정의 연산량을 줄일 수 있는 알고리즘이 필요하다.

본 발명은 이와 같은 종래의 문제점을 해결하기 위하여 제안한 것으로, 계층 적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입, 즉 복잡한 택스쳐를 포함하는 영상 블록, 균일한 영역으로 이루어진 영상 블록 등의 블록 특성을 반영하여 계층의 레벨을 조정함으로써, 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 데 그 목적이 있다.

이와 같은 목적을 실현하기 위한 본 발명에 따른 움직임 추정 방법은, 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성하는 단계와, 찾고자 하는 대상 블록의 주파수 신호 특성에 따라 평균 피라미드 중에서 어느 하나의 레벨을 탐색 레벨로 설정하는 단계와, 탐색 레벨에서 최소의 블록 정합 차이값을 가지는 후보 지점을 설정하는 단계와, 설정한 후보 지점에 대하여 평균 피라미드 중에서 최하위 레벨에서 움직임 벡터를 찾는 단계를 포함한다.

이하, 본 발명의 바람직한 실시 예를 첨부된 도면들을 참조하여 상세히 설명한다. 아울러 본 발명을 설명함에 있어, 관련된 공지 구성 또는 기능에 대한 구체적인 설명이 본 발명의 요지를 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략한다.

도 1은 본 발명에 따른 움직임 추정 방법을 적용한 비디오 인코더의 구성을 보여주는 블록도이다.

비디오 인코더(100)는 비디오 프레임들간의 움직임을 추정하여 비디오 프레임들의 시간적 중복을 제거하고, 시간적 중복이 제거된 프레임들을 공간적 변환하 여 공간적 중복을 제거하며, 공간적 중복이 제거된 프레임들을 양자화하여 비트스트림을 생성한다. 이를 위하여 비디오 인코더(100)는 움직임 추정부(101), 움직임 보상부(103), 공간적 변환부(105), 양자화부(107), 움직임 정보 인코딩부(111) 및 비트스트림 생성부(109)를 포함한다.

움직임 추정부(101)는 움직임 보상부(103)에서 현재 프레임(current frame)의 움직임을 보상하여 시간적 중복을 제거할 때 사용되는 움직임 벡터들을 찾는다. 움직임 벡터는 현재 프레임의 블록과 이에 매칭되는 참조 프레임의 블록간의 위치 차이로 정의할 수 있다. 참조 프레임으로 원래의 비디오 프레임이 이용될 수도 있으며, 코딩된 프레임을 디코딩하여 재구성한 프레임을 참조 프레임으로 이용할 수 있다.

이와 같은 움직임 추정부(101)에 의해 움직임 벡터를 찾는 과정을 살펴보면, 평균 피라미드 구조의 레벨을 찾고자 하는 블록의 주파수 신호 특성에 따라 결정하는 단계, 탐색 지점을 선정하고 그 진행 과정을 설정하는 방법들을 필요에 따라 사용하여 이전 단계에서 결정된 레벨 상의 MAD(Maximum absolute difference)를 최소화시키는 지점을 찾는 단계, 이전 단계에서 찾은 지점에서 최하위 레벨에 대하여 전역 검색을 수행하여 움직임 벡터를 찾는 단계를 포함한다.

움직임 보상부(103)는 움직임 추정부(101)에 의하여 구해진 움직임 벡터를 이용하여 현재 프레임의 시간적 중복을 제거한다. 이를 위하여 움직임 보상부(103)는 참조 프레임과 움직임 벡터를 이용하여 예측 프레임을 생성하고, 현재 프레임과 예측 프레임을 비교하여 잔여 프레임(residual frame)을 생성한다.

공간적 변환부(105)는 잔여 프레임을 변환시켜 변환 계수들을 얻는다. 공간적 변환 알고리즘은 정지 이산코사인변환(Discrete Cosine Transform) 또는 웨이브렛변환을 사용한다.

양자화부(107)는 공간적 변환부(105)를 통해 얻은 변환 계수들을 양자화한다. 양자화의 세기는 비트레이트에 따라 결정된다.

움직임 정보 인코딩부(111)는 움직임 추정부(101)에 의해 구해진 움직임 벡터를 인코딩하여 정보량을 줄여 움직임 정보를 생성한다. 움직임 정보는 비트스트림에 포함된다.

비트스트림 생성부(109)는 양자화된 변환 계수들과 인코딩된 움직임 벡터를 포함한 비트스트림을 생성한다. 여기서, 양자화된 변환 계수들을 바로 비트스트림에 포함시키지 않고, 스캐닝과 스케일링 및 엔트로피 코딩 등을 거쳐 생성된 텍스쳐 정보를 비트스트림에 포함시킨다.

이와 같이 구성된 비디오 인코더에 적용할 수 있는 본 발명에 따른 움직임 보상 방법에 대해 도 2 내지 도 6을 참조하여 보다 상세히 설명하기로 한다.

먼저, 본 발명에 따른 움직임 보상 방법을 설명하기에 앞서 본 발명의 이해를 돕기 위하여 움직임 추정을 위한 여러 가지 알고리즘들 중에서 본 발명의 기초가 되는 블록 정합 방법에 대해 살펴보기로 한다.

탐색 지점의 위치 선정 및 그 위치의 진행 과정을 설정하는 방법에 관련된 블록 정합 방법으로는 3단 탐색(Three Step Search, TSS), 2진 탐색(Binary Search, BS), 2차원 대수 탐색(Two Dimensional Logarithmic search, TDL), 4단 탐색(Four Step Search, FSS), 교차 탐색(Cross Search Algorithm, CSA) 등이 있고, 계산을 간단히 하기 위한 계층적 블록 정합 알고리즘(HSBMA)이 있다.

TSS, BS, TDL, FSS, CSA 등은 모두 중심 지점에서 일정 영역 안에서 최소의 블록 정합 차이값을 갖는 최적의 움직임 벡터를 찾는 것을 목표로 하며, 계산량을 줄이기 위하여 전체 영역을 모두 탐색하는 방법 대신에 여러 단계로 그 탐색 영역을 구분하여 최적 해에 근접한 해를 찾는다. 각 방법들은 각 단계에서 탐색 후보들을 기하학적으로 어떻게 설정하는지에 따라 구분된다.

이 중에서 TSS는 도 2에 나타낸 바와 같이, 초기 단계크기가 정해진 후 탐색 영역의 중심점에서 단계크기만큼 떨어진 8개의 블록들을 비교 후보로 정하는 단계, 탐색중심점은 이전 단계의 후보들 중 최소 블록 정합 차이를 가지는 지점으로 바꾸고 단계크기는 반으로 줄이는 단계, 단계크기가 1보다 작아질 때까지 이전 단계들을 반복하는 단계로 이루어진다.

BS는 도 3에 나타낸 바와 같이, 9개의 후보지점을 각각 탐색 영역의 중심점과 4모서리와 4변의 중심점에 설정하고, 각 점들을 중심으로 하여 탐색 영역들을 도 3과 같이 설정하는 단계, 9개의 후보지점에서 최소의 블록 정합 차이를 가지는 지점에 해당하는 탐색 영역에서 전역 검색을 수행하는 단계로 이루어진다.

계층적 블록 정합 알고리즘(HSBMA)은 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성한다. 그 다음으로는 서브 샘플링되어 작은 이미지 크기를 가지는 높은 레벨에서부터 블록 정합을 수행하여 작은 크기의 블록 정합 차이를 갖는 후보들에 대해여 추가적으로 낮은 레벨에서 블록 정합을 수행하는 식 으로 움직임 벡터를 탐색한다.

이러한 계층적 블록 정합 알고리즘에 대해 도 4를 참조하여 단계별로 살펴보면, 먼저 L 레벨의 평균 피라미드를 생성한다. 레벨 0이 원 영상이라 하고, 레벨 L-1이 최상위 레벨의 영상이라 하고, l을 레벨이라 하며, x, y를 영상의 위치라고 할 때, 상위 레벨의 영상은 하위 레벨의 영상과 다음의 수학식 1과 같은 관계를 가진다.

다음으로, 최소의 블록 정합 차이값을 가지는 N개의 후보를 최상위 레벨에서 설정한다. 예로서, 도 4의 왼쪽 그림과 같이 레벨 2에서 최소의 블록 정합 차이값을 가지는 2개의 후보를 설정, 그 중심 지점을 설정한다.

그리고, 그 하위 레벨에서는 설정된 후보들의 주위에 대하여만 다시 최소의 블록 정합 차이값을 가지는 일정 수의 후보들을 선정한다. 이때 최소 블록 정합 차이값을 가지는 블록을 찾기 위하여 TSS를 사용한다. 이 과정을 최하위 레벨에 이를 때까지 반복한다. 예로서, 도 4의 가운데 그림과 같이 레벨 1에서 기 설정된 중심 지점으로 주위 일정 크기의 창 내에서 다시 최소 블록 정합 차이값을 가지는 지점을 탐색한다.

그리고, 최하위 레벨의 후보에 대해서는 전역 검색을 수행하여 최종 해를 구한다. 예로서, 도 4의 오른쪽 그림과 같이 이전 단계에서 결정된 지점을 중심으로 전력 검색을 수행한다.

한편, 본 발명에 따른 움직임 보상 방법은 전술한 바와 같은 움직임 보상 기법 중에서 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입하여 움직임 보상의 계산량을 줄이고 성능을 개선하는 것을 목표로 한다.

도 5 및 도 6을 참조하면, 계층적 블록 정합 알고리즘과 같이 다른 크기를 가지는 영상으로 이루어진 여러 레벨(L 레벨)의 평균 피라미드를 생성한다. 즉 부호화할 현재 블록과 이전 프레임이 원래 해상도를 가지는 하위 레벨(lower level), 하위 레벨의 원래 영상을 수평 및 수직으로 각각 2:1로 데시메이팅(decimation)하여 해상도를 낮춘 중간 레벨(Middle level) 및 중간 레벨의 영상을 다시 한번 수평 및 수직으로 각각 2:1로 데시메이팅하여 해상도를 낮춘 상위 레벨(Upper level)을 생성한다.

다음으로, 찾고자 하는 대상 블록이 위의 평균 피라미드 구조를 적용했을 때 상위 레벨로 올라감에 따라 평균되고 서브샘플링되는 과정에서 그 이미지 블록의 주파수 정보가 A%(예로서, 80%)이상 손실되지 않는 최상위 레벨을 탐색 레벨로 설정한다(S210).

이를 결정하기 위하여 도 5에 나타낸 바와 같이 대상 블록을 FFT(Fast Fourier Transform) 분석하여 에너지의 A% 손실을 가져오는 저주파 블록의 크기를 구한다. 위 블록 크기가 변의 길이 기준으로 원 대상 블록의 1/N일 때 레벨은

이 된다. 이때

는 버림을 의미한다.

그리고, 단계 S210에서 설정한 레벨에서 최소의 블록 정합 차이값을 가지는 1개의 후보를 설정한다. 이때 최소 블록 정합 차이값을 가지는 블록을 찾기 위하여 TSS, TDL, FSS, BS, CSA 등 여러 가지의 탐색 방법을 이용한다. 예로서, 도 5에 나타낸 바와 같이 대상 블록이 상위 레벨로 평균되고 서브샘플링되는 과정에서 A%이하의 주파수 정보 손실을 갖는 최상위 레벨 X에서 최소 블록 정합 차이값을 갖는 지점, 즉 MAD를 최소화시키는 지점을 찾는다(S220).

이후, 단계 S220에서 설정된 후보에 대하여 최하위 레벨에서 전역 검색을 수행하여 최종 해를 구한다. 예로서, 도 5에 나타낸 바와 같이 해당 지점에서 레벨 0으로 내려와 전역 검색을 수행하여 움직임 벡터를 찾는다(S230).

지금까지는 본 발명의 일 실시 예에 국한하여 설명하였으나 본 발명의 기술이 당업자에 의하여 용이하게 변형 실시될 가능성이 자명하다. 이러한 변형된 실시 예들은 본 발명의 특허청구범위에 기재된 기술사상에 당연히 포함되는 것으로 해석되어야 할 것이다.

전술한 바와 같이 본 발명은 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입, 즉 복잡한 택스쳐를 포함하는 영상 블록, 균일한 영역으로 이루어진 영상 블록 등의 블록 특성을 반영하여 계층의 레벨을 조정함으로써, 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 효과가 있다.

Claims (4)

1. (a) 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성하는 단계와,

   (b) 찾고자 하는 대상 블록의 주파수 신호 특성에 따라 상기 평균 피라미드 중에서 어느 하나의 레벨을 탐색 레벨로 설정하는 단계와,

   (c) 상기 탐색 레벨에서 최소의 블록 정합 차이값을 가지는 후보 지점을 설정하는 단계와,

   (d) 상기 설정한 후보 지점에 대하여 상기 평균 피라미드 중에서 최하위 레벨에서 움직임 벡터를 찾는 단계

   를 포함하는 움직임 추정 방법.
2. 제 1 항에 있어서,

   상기 (b) 단계는, 상기 대상 블록이 상기 평균 피라미드를 적용했을 때 상위 레벨로 올라감에 따라 평균되고 서브샘플링되는 과정에서 그 이미지 블록의 주파수 정보가 설정값이상 손실되지 않는 최상위 레벨을 상기 탐색 레벨로 설정하는

   움직임 추정 방법.
3. 제 1 항에 있어서,

   상기 (c) 단계는, 3단 탐색(Three Step Search, TSS), 2진 탐색(Binary Search, BS), 2차원 대수 탐색(Two Dimensional Logarithmic search, TDL), 4단 탐색(Four Step Search, FSS), 교차 탐색(Cross Search Algorithm, CSA) 중에서 어느 하나의 방법을 사용하는

   움직임 추정 방법.
4. 제 1 항에 있어서,

   상기 (d) 단계는, 상기 최하위 레벨에서 전역 검색을 수행하여 상기 움직임 벡터를 찾는

   움직임 추정 방법.

Images