KR101037070B1 - 전역탐색기법에 의한 고속 움직임 예측 방법 - Google Patents

Abstract

본 발명은 전역탐색기법에 의한 고속 움직임 예측 방법에 관한 것이다. 본 발명에 따른 전역탐색기법에 의한 고속 움직임 예측 방법은 (a) 현재 프레임 내의 기준블록을 다수의 서브블록으로 나누는 단계; (b) 이전 프레임의 DCT(Discrete Cosine Transform; 이산 코사인 변환) 계수를 이용하여 상기 서브블록 각각에 대한 기울기의 크기를 산출하는 단계; 및 (c) 상기 산출된 기울기의 크기에 따라 상기 서브블록에 대한 매칭순서를 결정하는 단계를 포함한다.

이에 따라, DCT 계수를 이용하여 영상 복잡도를 산출함으로써 화질 저하 없이 종래의 고속 전역탐색방법에 비해 빠르게 움직임 벡터를 산출할 수 있다.

전역탐색, 고속 움직임 예측, DCT

Description

전역탐색기법에 의한 고속 움직임 예측 방법{Fast Motion Estimation Method Using Full Search}

본 발명은 전역탐색기법에 의한 고속 움직임 예측 방법에 관한 것으로, 보다 구체적으로는 영상의 복잡도를 이용하여 고속으로 움직임 예측을 수행하는 것에 관한 것이다.

비디오 압축 기술은 대역폭 크기의 제한으로 인해 많은 데이터를 전송해야 하는 예컨대, 비디오폰, 이동통신, 및 디지털 멀티미디어 방송(DMB)와 같은 모바일 통신 시스템에 요구된다.

MPEG-X 또는 H.26X과 같은 비디오 압축 규격은 이러한 요구에 부응하여 꾸준히 개발 및 발전 되어 왔다.

비디오 압축 기술의 핵심은 시간적 중복을 제거하기 위한 움직임 예측이라고 할 수 있다. 이러한 움직임 예측기법 중에서 전역탐색기법(Full Search Algorithm)이 주로 많이 사용되는데, 이는 하드웨어적 구현이 편리하다는 장점을 갖기 때문이 다.

전역탐색기법은 주어진 탐색 범위 내의 모든 후보블록 중에서 최소 매칭 에러 값을 갖는 블록을 찾아서 움직임 예측을 수행한다.

그러나, 전역탐색기법은 연산이 복잡하다는 단점을 갖는다. 이러한 문제점을 해결하기 위해, 탐색 포인트의 개수를 유지하면서도 전역탐색기법의 연산의 복잡도를 감소시키는 고속 전역탐색기법들이 제안되고 있다. 일반적으로 고속 움직임 예측기법들은 탐색 포인트를 생략하기 때문에 영상의 품질이 떨어지지만, 고속 전역탐색기법들의 성능은 전역탐색기법과 거의 동일하다는 장점을 갖는다.

그러나, 고속 전역탐색기법은 여전히 고속탐색기법에 비해 연산이 복잡하기 때문에 움직임 예측에 소요되는 시간이 많다.

따라서, 본 발명의 목적은 DCT 계수를 이용하여 영상 복잡도를 산출함으로써 화질 저하 없이 종래의 고속 전역탐색방법에 비해 빠르게 움직임 벡터를 산출하는 것이다.

상기 목적은 본 발명에 따라, 전역탐색기법에 의한 고속 움직임 예측 방법에 있어서, (a) 현재 프레임 내의 기준블록을 다수의 서브블록으로 나누는 단계; (b) 이전 프레임의 DCT 계수를 이용하여 상기 서브블록 각각에 대한 기울기(Gradient)의 크기를 산출하는 단계; 및 (c) 상기 산출된 기울기의 크기에 따라 상기 서브블록에 대한 매칭순서를 결정하는 단계를 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법에 의해 달성될 수 있다.

한편, 상기 목적은 본 발명에 따라, 전역탐색기법에 의한 고속 움직임 예측 방법에 있어서, (a) 현재 인터 프레임(Inter Frame)내의 기준블록을 다수의 서브블록으로 나누는 단계; (b) 이전 인트라 프레임(Intra Frame)의 DCT 계수를 이용하여 상기 서브블록 각각에 대한 기울기의 크기를 산출하는 단계; (c) 상기 산출된 기울기의 크기순서에 따라 상기 서브블록에 대한 매칭스캔순서를 결정하는 단계; 및 (d) 부분 에러 제거 방법(PDE, Partial Distortion Elimination)을 통해 매칭을 수행하여 움직임 벡터를 산출하는 단계를 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법에 의해 달성될 수 있다.

여기서, 상기 (b) 단계에서 상기 서브블록 각각에 대한 기울기는 다음 식에 따라 산출될 수 있다.

G_P1= │2(2F_1.0 + F_3.0) - F_5.0 - F_7.0│ + │2(2F_0.1 + F_0.3) - F_0.5 - F_0.7│.

(여기서, G_P1은 기울기 크기, F_{u ,v}는 주파수 블록의 위치 (u,v)에서의 DCT 계수를 의미함)

한편, 상기 (b) 단계에서 상기 서브블록 각각에 대한 기울기는 다음 식에 따 라 산출될 수 있다.

.

(여기서, G_P2는 기울기의 크기를 의미하고, F₀은 8*8 크기 블록에서 DCT DC 계수, F₁~F₆₃은 DCT AC 계수이며, 물리적으로 AC 계수는 신호의 변화 또는 변동을 의미함)

그리고, 상기 서브블록은 8*8 크기의 블록이고, 상기 이전 프레임은 인트라 프레임일 수 있다.

한편, 상기 고속 움직임 예측 방법은, (d) 상기 기준블록과 검색창 내에 기 설정된 후보블록 간의 매칭 에러를 산출하여 최소 매칭 에러를 설정하는 단계; 및 (e) 상기 (c) 단계에서 결정된 매칭순서에 따라 상기 기준블록과 후보블록 간의 매칭 에러를 산출하는 단계로서, 상기 매칭 에러의 중간합이 상기 최소 매칭 에러보다 큰 경우, 해당 검색점에 대한 매칭 에러의 산출을 중단하고 다음 과정으로 진행하는 단계를 더 포함할 수 있다.

그리고, 상기 (e) 단계는, 상기 산출된 매칭 에러가 상기 최소 매칭 에러보다 작은 경우, 상기 최소 매칭 에러보다 작은 상기 매칭 에러를 상기 최소 매칭 에러로 설정하는 단계를 포함할 수 있다.

이상 설명한 바와 같이, 본 발명에 따르면, DCT 계수를 이용하여 영상 복잡도를 산출함으로써 화질 저하 없이 종래의 고속 전역탐색방법에 비해 빠르게 움직임 벡터를 산출할 수 있다.

이하, 도면을 참조하여 본 발명의 구체적인 실시예들에 대해 설명하기로 한다.

본 발명은 영상 복잡도를 이용한 적응적 매칭 스캔 방법에서, DCT 계수를 이용하여 영상복잡도를 산출하여 연산의 복잡도를 줄이도록 한 것이다. 또한, 부분에러제거방법(PDE, Partial Distortion Elimination)을 이용하여 움직임 벡터를 찾아냄으로써 고속으로 움직임 벡터를 산출하도록 한다.

도 1은 본 발명의 일 실시예에 따른 비디오 부호화 장치를 개략적으로 도시한 것이다. 본 실시예에 따른 비디오 부호화 장치는 MPEG-4와 같은 동영상 표준에 적용 가능한 것으로, 제1 DCT 변환부, 기울기 산출부, 움직임 예측부, 제2 DCT 변환부, 양자화부, 및 엔트로피 코딩부를 포함한다.

도 1을 참조하면, 인트라 픽쳐(I 픽쳐)는 제1 DCT 변환부, 양자화부, 및 엔트로피 코딩부를 거쳐 부호화되고, 인터 픽쳐(P 픽쳐 또는 B 픽쳐)는 움직임 예측부, 제2 DCT 변환부,양자화부, 및 엔트로피 코딩부를 거쳐 부호화된다.

기울기 산출부는 제1 DCT 변환부에서 산출한 이전 프레임의 DCT 계수를 이용하여 현재 부호화하고자 하는 현재 프레임의 기준 블록의 기울기의 크기를 산출하 고, 움직임 예측부는 기울기 산출부에서 산출한 기울기 값을 이용하여 매칭 순서를 결정한 후 후보 블록과의 매칭을 수행한다. 기울기 산출부와 움직임 예측부에서 수행하는 기울기 산출 및 움직임 예측에 대한 구체적인 내용은 후술하기로 한다.

도 2는 본 발명의 일 실시예에 따른 전역탐색기법에 의한 고속 움직임 예측 방법에 관한 흐름도이다.

본 발명에 따른 전역탐색기법에 의한 고속 움직임 예측 방법은 영상의 복잡도를 이용하여 매칭 스캔 순서를 재정렬하여 전역탐색의 계산량을 감소시킨다. 탐색 영역 안에서 기준 블록과 후보 블록의 매칭 에러는 기준 블록의 기울기 크기(즉, 영상의 복잡도)에 비례한다고 사실에 기초하여 본 발명은 종래 순차적으로 행렬기반의 매칭을 수행하는 대신 각 서브블록의 영상의 복잡도에 기초하여 매칭 순서를 결정한다.

우선, 움직임 예측부는 코딩하고자 하는 현재 프레임의 기준블록(즉, 매크로블록; MB)을 다수의 서브블록으로 나눈다(S10). 예컨대, 기준블록의 크기가 16*16이라고 할 때, 서브블록은 8*8, 4*4가 될 수 있을 것이다.

한편, 기울기 산출부는 각 서브블록의 영상의 복잡도를 산출한다(S11). 영상의 복잡도를 산출하는 방법은 다양하게 존재할 수 있으며, 일반적으로 인접화소와의 절대치 차를 이용하는 것이 대부분이다. 이 방법은 일일이 화소별 뺄셈과 덧셈을 수행하기 때문에 비교적 연산이 복잡하다는 단점이 있다. 예컨대, 이 방법은 매크로블록마다 768개의 덧셈/뺄셈과 512개의 절대값 연산을 수행해야 한다.

본 발명에서는 이러한 단점을 극복하고자, 이전 프레임에서 산출한 DCT 계수 로부터 블록의 기울기(즉, 영상의 복잡도)를 유도하여 간단하게 서브블록에 대한 기울기의 크기를 산출할 것을 제안한다.

이하, 본 발명의 제1 실시예에 따른 기울기 산출방법에 대해 설명한다.

DCT 계수와 블록의 기울기 크기의 다음과 같이 유도할 수 있다.

위 식에서, G는 기울기를 의미하고, (8)은 8*8을 의미하며, h는 수평, v는 수직, F_{u ,v}는 주파수 블록의 위치 (u,v)에서의 DCT 계수를 의미한다. 위 식의 유도과정은 공지되어 있으므로 이에 대한 구체적인 설명은 생략하기로 한다.

본 발명의 제1 실시예에서는 위의 식을 기초로, 블록의 기울기와 DCT계수와의 관계를 다음과 같이 나타낸다.

G_P1= │2(2F_1.0 + F_3.0) - F_5.0 - F_7.0│ + │2(2F_0.1 + F_0.3) - F_0.5 - F_0.7│

여기서, G_P1은 기울기 크기, F_{u ,v}는 (u,v)에서의 DCT 계수를 의미한다

도 3은 본 실시예에 따라 서브블록에 대한 기울기 산출 결과의 예를 나타낸 것이다. 도 3을 참조하면, 16*16 크기의 기준 블록을 8*8 크기의 4개의 서브블록으로 나누고, 각각의 서브블록에 대해 기울기를 산출하였으며, 기울기의 크기가 큰 순서대로 서브블록을 (1)(2)(3)(4)로 표시하였다.

움직임 예측부는 기울기 산출부의 산출결과에 따라 서브블록을 기울기 크기 순으로 정렬한 후(S12), 그 순서대로 전영역에 대한 매칭스캔을 수행한다(S13). 즉, 도 3과 같이 (1)→(2)→(3)→(4) 순으로 매칭을 수행한다.

다만, 인터-코딩에서는 수학식 3에서 사용 가능한 DCT 계수가 존재하지 않는다. 따라서, 인터 코딩 시에는 인트라 픽쳐에서 산출된 DCT 계수를 이용하여 기울기를 산출한다.

따라서, 인트라 픽쳐에서 산출된 DCT 계수를 저장한 후, 이를 이후 인터 픽쳐의 움직임 예측 시 사용한다. 시간적으로 인접한 픽쳐는 매우 유사하며, 유사한 주파수 특성을 갖기 때문에 이전 픽쳐의 DCT 계수를 사용하더라도 문제되지 않는다.

이와 같이, 본 발명은 인트라 필드의 DCT 계수를 인터 필드의 움직임 예측에 사용하여, 움직임 벡터 산출에 소요되는 시간을 획기적으로 감소시킬 수 있다.

이하, 본 발명의 제2 실시예에 따른 블록의 기울기 산출방법에 대해 설명한다.

본 발명의 제2 실시예에서는 하다마드 AC(Hadamard Transform Alternating Current) 계수와 기울기 크기의 관계를 이용하여 기울기의 크기를 산출한다.

하다마드 AC 계수와 기울기 크기의 관계는 다음과 같이 유도할 수 있다.

여기서, G'[f(x,y)]는 (x,y)에서의 기울기를 의미하며, H는 HT Kernel을 의미하며, 4*4 크기의 블록에 대한 기울기 산출에 대한 식이다. TC는 변환 계수를 의미하고, (i,j)는 블록 인덱스를 나타낸다. 위 식의 유도과정은 공지되어 있으므로 이에 대한 구체적인 설명은 생략하기로 한다.

위 식을 보면, 기울기의 크기가 하드마드 AC 계수의 절대 합으로 대체될 수 있음을 알 수 있다.

따라서, DCT 계수도 동일한 방법으로 간주하면, DCT 계수와 기울기의 상관관계는 다음과 같이 나타낼 수 있다.

여기서, G_P2는 기울기의 크기를 의미하고, F₀은 8*8 크기 블록에서 DCT DC 계수, F₁~F₆₃은 DCT AC 계수이다. 물리적으로, AC 계수는 신호의 변화 또는 변동을 의 미한다.

움직임 예측부는 기울기 산출부의 산출결과에 따라 서브블록을 기울기 크기 순으로 정렬한 후(S12), 순서대로 전영역에 대한 매칭스캔을 수행한다(S13).

도 4는 도 2의 S13단계를 구체적으로 나타낸 것으로, 본 발명의 일 실시예에 따른 매칭 수행방법을 도시한 흐름도이다.

우선, 움직임 예측부는 현재 기준블록과 검색창 내의 기 설정된 후보블록 간의 SAD를 산출하여 초기 최소 매칭 에러(SAD_MIN)를 설정한다.

그리고, 도 2에서 기울기 순서에 따라 결정된 매칭 순서에 따라 기준블록과 후보블록 간의 매칭 에러를 산출한다.

본 발명에서는 매칭 수행시 부분에러제거방법을 이용하여 고속으로 움직임 벡터를 산출할 수 있도록 한다. 즉, 도 4에 도시된 바와 같이, 각 후보 블록 간의 매칭 에러 산출 도중에 중간 매칭 에러(SADMIN)가 최소 매칭 에러(SAD_MIN)보다 크면 현재 후보 블록에 대한 매칭 에러 산출을 종료하고 다음 후보블록으로 이동한다(S23, S24).

이에 따라 탐색을 조기에 종료할 수 기회가 생기며, 서브블록의 매칭 순서가 잘 정렬되어 있다면, 이러한 조기 종료의 가능성은 더 높아지기 때문에 속도에 대한 성능이 더욱 우수해질 것이다.

한편, 현재 후보블록에 대해 산출된 매칭 에러(SAD_CUR)가 최소 매칭 에러(SAD_MIN)보다 작다면 그 작은 매칭 에러(SAD_CUR)를 최소매칭에러로 교체하여 설정 다(S21, S22).

이러한 탐색 과정은 모든 후보 블록에 대해 수행되며, 현재 후보블록이 마지막 후보블록인 경우, 현재의 최소 매칭 에러(SAD_MIN)에 대응하는 검색점을 움직임 벡터로 결정한다(S23, S24, S25).

이러한 탐색과정은 현재 프레임의 모든 기준블록에 대해 수행되며, 모든 블록에 대해 움직임 벡터 산출이 완료되면, 다음 프레임에 대해 움직임 벡터 산출을 수행한다(S26, S27).

이와 같이, 본 발명은 간단한 기울기 산출방법과 부분에러제거방법을 함께 적용함으로써 화질면에서 전역탐색과 동등한 성능을 유지하면서도 종래에 비해 월등히 속도면에서 우수한 성능을 갖는다.

실험 결과

본 실험은 MPEG-4 VM 참조 소프트웨어에서 수행하였으며, 그 결과는 아래 표 1에 나타냈다.

표 1에서 각 수치는 전역탐색방법에 PDE 방법을 적용하였을 때에 비해 각 방법들이 LineSAD 측면에서 얼마나 속도가 빨라지는가를 나타낸다. 여기서, LineSAD는 SAD를 계산한 라인의 수를 의미한다.

표 1을 보면, 본 발명이 LineSAD 측면에서 종래의 방법과 비슷하다. 그러나, 매크로블록 1개를 부호화하기 위해 종래의 방법(Kim's)은 768개의 덧셈/뺄셈 연산과 512개의 절대값 연산이 기울기 크기의 산출에 필요하다.

반면, 본 발명의 제1 실시예에 따른 기울기 산출 방법(Proposed 1)은 28개의 덧셈/뺄셈 연산과 8개의 절대값 연산과 18개의 시프트 연산만이 필요할 뿐이다.

또한, 본 발명의 제2 실시예에 따른 기울기 산출 방법(Proposed 2)은 252개의 덧셈/뺄셈 연산과 252개의 절대값 연산이 필요하고 이것은 종래에 비해 더 나은 수치이다.

이는 IP(Inter Period)가 2일 때의 수치이고, 본 발명은 IP가 늘어난다고 해도 계산량이 늘지 않기 때문에 성능은 더욱 나아진다.

본 발명의 제1 실시예와 제2 실시예를 비교하면, 성능은 제2 실시예에 따른 방법이 더 우수하지만, 제1 실시예에 따른 방법은 부호화에 필요한 연산의 개수가 작다는 점에서 장점을 갖는다.

아래 표 2는 매크로블록 하나를 부호화하기 위해 필요한 계산량을 보여주는 표이다.

위 표를 보더라도 본 발명에서 제안하는 방법이 종래에 비해 월등히 연산개수가 작음을 확인할 수 있다.

전술한 실시예에서는 16*16 크기의 기준블록을 8*8 크기의 서브블록으로 나누는 것을 일 예로 설명하였으나, 다른 크기의 블록으로 적용될 수 있음은 물론이다.

전술한 본 발명은 소프트웨어 알고리즘으로 구현 가능하며, 해당 알고리즘이 저장된 메모리, 해당 알고리즘이 실행되는 프로세서 등을 포함하는 장치에 의해서도 구현 가능하다. 또한, 영상을 처리하여 표시하는 모든 디스플레이에 적용 가능하다.

특히, 본 발명은 비디오 압축기술을 사용하는 모든 어플리케이션, 예컨대, 모바일 방송을 지원하는 핸드폰 및 여러 DMB 플레이어, 카메라, HDTV, IPTV, PC 등 비디오 압축기술을 필요로 하는 많은 기기들에 적용될 수 있다.

비록 본 발명의 몇몇 실시예들이 도시되고 설명되었지만, 본 발명이 속하는 기술분야의 통상의 지식을 가진 당업자라면 본 발명의 원칙이나 정신에서 벗어나지 않으면서 본 실시예를 변형할 수 있음을 알 수 있을 것이다. 발명의 범위는 첨부된 청구항과 그 균등물에 의해 정해질 것이다.

도 1은 본 발명의 일 실시예에 따른 비디오 부호화 장치를 개략적으로 도시한 것이다.

도 2는 본 발명의 일 실시예에 따른 전역탐색기법에 의한 고속 움직임 예측 방법에 관한 흐름도이다.

도 3은 본 실시예에 따라 서브블록에 대한 기울기 산출 결과의 예를 나타낸 것이다.

도 4는 도 2의 S13단계를 구체적으로 나타낸 것으로, 본 발명의 일 실시예에 따른 매칭 수행방법을 도시한 흐름도이다.

Claims (8)

1. 전역탐색기법에 의한 고속 움직임 예측 방법에 있어서,

   (a) 현재 프레임 내의 기준블록을 다수의 서브블록으로 나누는 단계;

   (b) 이전 프레임의 부호화 과정에서 기 산출되었던 상기 이전 프레임의 DCT 계수를 이용하여 상기 서브블록 각각에 대한 기울기의 크기를 산출하는 단계; 및

   (c) 상기 산출된 기울기의 크기에 따라 상기 서브블록에 대한 매칭순서를 결정하는 단계를 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.
2. 전역탐색기법에 의한 고속 움직임 예측 방법에 있어서,

   (a) 현재 인터 프레임 내의 기준블록을 다수의 서브블록으로 나누는 단계;

   (b) 이전 인트라 프레임의 부호화 과정에서 기 산출되었던 상기 이전 인트라 프레임의 DCT 계수를 이용하여 상기 서브블록 각각에 대한 기울기의 크기를 산출하는 단계;

   (c) 상기 산출된 기울기의 크기순서에 따라 상기 서브블록에 대한 매칭스캔순서를 결정하는 단계; 및

   (d) 부분 에러 제거 방법(PDE, Partial Distortion Elimination)을 통해 매칭을 수행하여 움직임 벡터를 산출하는 단계를 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.
3. 제1항 또는 제2항에 있어서,

   상기 (b) 단계에서 상기 서브블록 각각에 대한 기울기는 다음 식에 따라 산출되는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법:

   G_P1= │2(2F_1.0 + F_3.0) - F_5.0 - F_7.0│ + │2(2F_0.1 + F_0.3) - F_0.5 - F_0.7│.

   (여기서, G_P1은 기울기 크기, F_{u ,v}는 주파수 블록의 위치 (u,v)에서의 DCT 계수를 의미함)
4. 제1항 또는 제2항에 있어서,

   상기 (b) 단계에서 상기 서브블록 각각에 대한 기울기는 다음 식에 따라 산출되는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법:

   

   .

   (여기서, G_P2는 기울기의 크기를 의미하고, F₀은 8*8 크기 블록에서 DCT DC 계수, F₁~F₆₃은 DCT AC 계수이며, 물리적으로 AC 계수는 신호의 변화 또는 변동을 의미함)
5. 제1항 또는 제2항에 있어서,

   상기 서브블록은 8*8 크기의 블록인 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.
6. 제1항에 있어서,

   상기 이전 프레임은 인트라 프레임인 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.
7. 제1항에 있어서,

   상기 고속 움직임 예측 방법은,

   (d) 상기 기준블록과 검색창 내에 기 설정된 후보블록 간의 매칭 에러를 산출하여 최소 매칭 에러를 설정하는 단계; 및

   (e) 상기 (c) 단계에서 결정된 매칭순서에 따라 상기 기준블록과 후보블록 간의 매칭 에러를 산출하는 단계로서, 상기 매칭 에러의 중간합이 상기 최소 매칭 에러보다 큰 경우, 해당 검색점에 대한 매칭 에러의 산출을 중단하고 다음 과정으로 진행하는 단계를 더 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.
8. 제7항에 있어서,

   상기 (e) 단계는, 상기 산출된 매칭 에러가 상기 최소 매칭 에러보다 작은 경우, 상기 최소 매칭 에러보다 작은 상기 매칭 에러를 상기 최소 매칭 에러로 설정하는 단계를 포함하는 것을 특징으로 하는 전역탐색기법에 의한 고속 움직임 예측 방법.

Images