KR101619739B1 - 고속 모션 추정 방법 및 이를 이용한 비디오 인코딩 장치 - Google Patents

Abstract

본 발명은 비디오의 시간적 중복성을 제거하기 위한 모션 추정의 속도를 향상시키는 방법 및 장치에 관한 것이다. 본 발명에 따른 고속 모션 추정 방법은, 입력 프레임을 복수의 모드에 대응하는 블록들로 분할하는 단계와, 블록들 중에서 코딩하고자 하는 현재 블록에 대한 상위의 모드를 갖는 블록에 대한 코딩 비용을 계산하는 단계와, 코딩 비용을 기준으로 현재 블록의 스킵 여부를 결정하는 단계와, 결정 단계에서 스킵하지 않을 것으로 결정된 현재 블록에 대하여 모션 벡터를 구하는 단계로 이루어진다.

인터 프레임 코딩, 모션 추정, 매크로블록, 블록 모드, H.264, 조기 중단

Description

고속 모션 추정 방법 및 이를 이용한 비디오 인코딩 장치{Method for fast motion estimation and video encoding apparatus using the same}

본 발명은 비디오 압축 방법에 관한 것으로, 보다 상세하게는 비디오의 시간적 중복성을 제거하기 위한 모션 추정의 속도를 향상시키는 방법 및 장치에 관한 것이다.

인터넷을 포함한 정보통신 기술이 발달함에 따라 문자, 음성뿐만 아니라 화상통신이 증가하고 있다. 기존의 문자 위주의 통신 방식으로는 소비자의 다양한 욕구를 충족시키기에는 부족하며, 이에 따라 문자, 영상, 음악 등 다양한 형태의 정보를 수용할 수 있는 멀티미디어 서비스가 증가하고 있다. 멀티미디어 데이터는 그 양이 방대하여 대용량의 저장매체를 필요로 하며 전송 시에 넓은 대역폭을 필요로 한다. 따라서 문자, 영상, 오디오를 포함한 멀티미디어 데이터를 전송하기 위해서는 압축코딩기법을 사용하는 것이 필수적이다.

데이터를 압축하는 기본적인 원리는 데이터의 중복(redundancy) 요소를 제거하는 과정이다. 이미지에서 동일한 색이나 객체가 반복되는 것과 같은 공간적 중복이나, 동영상 프레임에서 인접 프레임이 거의 변화가 없는 경우나 오디오에서 같은 음이 계속 반복되는 것과 같은 시간적 중복, 또는 인간의 시각 및 지각 능력이 높은 주파수에 둔감한 것을 고려한 심리시각 중복을 제거함으로써 데이터를 압축할 수 있다.

이러한 동영상 압축 기법의 표준화를 위하여, MPEG(Moving Picture Experts Group)-2, MPEG-4, H.264 등 다양한 비디오 코딩 표준들이 등장하고 있다. 도 1에 도시된 바와 같이, 모든 비디오 코딩 기술들은 인접한 비디오 프레임들 간의 시간적 중복성을 제거하기 위하여 블록 모션 추정(block motion estimation)이라는 기법을 채택하고 있다. 예를 들어, 현재 프레임(10) 내의 어떤 블록(30)을 부호화하기 위해서는, 현재 프레임(10)과 다른 시간적 위치에 있는 참조 프레임(20)에서 상기 블록(30)과 매칭되는 블록(40)을 찾는다. 이 후, 현재 프레임(10)의 블록(30)과 참조 프레임(20)의 블록(40) 간의 차분(residual)를 구한 후, 이 차분을 부호화함으로써 부호화 효율을 높이는 것이다. 여기서, 블록들 간의 변위는 모션 벡터로서 표시되며, 모션 벡터에 의하여 참조 프레임(20)에 관한 모션 보상이 이루어진다.

최근의 비디오 코딩 표준인 H.264는 코딩 효율의 측면에서 이전의 표준들을 훨씬 능가하는 것으로 알려져 있다. H.264는 인터 프레임 코딩에 있어서, 4x4에서 16x16에 이르는 가변 블록 크기를 채용하는데, 이는 고정된 크기의 매크로블록(MB)을 코딩하는 종래의 기법에 비하여 코딩 효율에 있어서 상당한 향상을 나타낸다.

또한, 이외에도 다중 참조 기법, 1/4 픽셀 정밀도의 모션 벡터 추정, 다양한 방향들에 대한 인트라 프레임 코딩 기법, 및 적응적 디블록 필터링 기법 등 다양한 새로운 기술들이 H.264에 채용되고 있다.

그러나, 이러한 새로운 기법들이 코딩 효율의 향상에 상당히 기여한 것은 사실이지만, 이에 따라 H.264 인코더에는 훨씬 높은 연산 복잡성이 요구되는 문제도 아울러 존재한다. 특히, 상기 가변 블록 크기를 결정하는 과정에서 매우 많은 연산량이 소요된다.

인터 프레임 코딩에 있어서, 최적의 코딩 성능을 나타내는 블록의 크기를 찾기 위하여는, 하나의 매크로블록을 다양한 크기의 서브블록들로 나누고, 나누어진 서브블록들 각각에 대하여 실제 코딩을 수행하는 반복적인 과정이 필요하다.

인터 블록 모드의 결정에서 사용되는 블록의 크기들은 다섯 가지의 서로 다른 모드를 갖는다. 그것은 "움직임 없음"을 나타내는 모드(MD0), 16x16 크기의 블록 모드(MD1), 16x8 크기의 블록 모드(MD2), 8x16 크기의 블록 모드(MD3) 및 8x8 크기의 블록 모드(MD8)를 포함한다. 물론, 상기 8x8 크기의 블록 모드(MD8)는 다시 8x8, 8x4, 4x8 및 4x4 크기의 블록 모드로 세분화될 수 있다.

H.264는 다양한 크기의 블록 모드들 중 최적의 블록 모드를 결정하기 위하여 R-D(rate-distortion) 최적화라는 기법을 사용한다. 가능한 모든 모드들에 대하여 R-D 최적화를 수행하기 위하여, H.264는 일반적으로 인트라/인터 모드들 각각과 연관된 R-D 코딩 비용을 모두 계산한 후에 상기 코딩 비용이 최소가 되는 모드를 찾는다. 그러나, 이러한 방법은 시각적 화질 및 코딩 비트레이트의 관점에서 최적의 결과를 얻을 수 있지만, 필연적으로 매우 많은 연산량을 소요할 수 밖에 없다.

이러한 과도한 연산량을 감소시키기 위하여, 많은 고속 모드 결정 알고리즘들이 제안된 바 있다.

먼저, "Fast intermode decision in H.264/AVC video coding, IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 7, pp. 953-958, Jul. 2005"라는 문서에 기재된 기술은 모드 결정의 조기 종료를 위하여, 에지 맵을 이용한 균질성 감지 및 SAD를 사용하여 시간적 유사성 감지 기술을 제안한다. 에지 정보를 사용하는 에지 맵은 소벨(Sobel) 연산자와 함께 각각의 프레임에 대하여 생성된다.

또한, "Fast inter mode selection in the H.264/AVC standard using a hierarchical decision process, IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 2, pp. 186-195, Feb. 2008"라는 문서에 기재된 기술은 라그랑지안에 의하여 결정되는, 모드 선택 프로세스의 조기 종료의 서로 다른 레벨들을 제공하는 계층적 구조를 제안한다.

또한, "A novel inter mode decision algorithm for H.264/AVC, in Proc. IEEE CISP May 2008, pp. 334-338"라는 문서에 기재된 기술은 조기 종료를 위한 3개의 조건들을 갖는 스킵 모드 결정을 사용하는 고속 인터 모드 결정 알고리즘과, R-D 코딩 비용 문턱값을 사용하는 고속 인트라 모드 결정 알고리즘을 제안한다.

그러나, 이와 같은 종래의 기술들이, 매우 많은 연산량을 요하는 통상의 모션 추정 기법에 비해서는 다소간 연산량을 감소시키기는 하지만, 고속 모션 추정을 위해서 사용되는 부가적인 연산량도 무시할만한 정도는 아니다. 따라서, 고속 모션 추정에서 추가되는 알고리즘에 의한 연산량을 최소화하면서도 정확한 모션 추정이 가능한 방법을 강구할 필요가 있는 것이다.

본 발명은 상기한 필요성을 감안하여 창안된 것으로, 연산량을 최소화하면서도 정확한 모션 추정이 가능한 고속 모션 추정 기법을 제공하는 것을 목적으로 한다.

본 발명의 기술적 과제들은 이상에서 언급한 기술적 과제로 제한되지 않으며, 언급되지 않은 또 다른 기술적 과제들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

상기 기술적 과제를 달성하기 위한 본 발명의 일 실시예에 따른, 고속 모션 추정 방법은, (a) 입력 프레임을 복수의 모드에 대응하는 블록들로 분할하는 단계; (b) 상기 블록들 중에서, 코딩하고자 하는 현재 블록에 대한 상위의 모드를 갖는 블록에 대한 코딩 비용을 계산하는 단계; (c) 상기 코딩 비용을 기준으로 상기 현재 블록의 스킵 여부를 결정하는 단계; 및 (d) 상기 결정 단계에서 스킵하지 않을 것으로 결정된 현재 블록에 대하여 모션 벡터를 구하는 단계를 포함한다.

상기 기술적 과제를 달성하기 위한 본 발명의 일 실시예에 따른, 비디오 인코딩 장치는, 입력 프레임을 복수의 모드에 대응하는 블록들로 분할하는 블록 분할부; 상기 블록들 중에서, 코딩하고자 하는 현재 블록에 대한 상위의 모드를 갖는 블록에 대한 코딩 비용을 계산하는 비용 계산부; 상기 코딩 비용을 기준으로 상기 현재 블록의 스킵 여부를 결정하는 스킵 결정부; 상기 스킵 결정부에 의하여 스킵 하지 않을 것으로 결정된 현재 블록에 대하여 모션 벡터를 구하는 모션 추정부; 상기 입력 프레임에서, 상기 구한 모션 벡터에 의해 참조 프레임을 보상한 모션 보상 프레임을 차분하여 잔차 프레임을 얻는 차분기; 및 상기 잔차 프레임을 부호화하는 수단을 포함한다.

본 발명에 따르면 통상의 모션 추정 기법이나, 종래의 고속 모션 추정 기법에 비하여, 연산량을 상당히 감소시킬 수 있는 장점이 있다. 그럼에도 불구하고, 모션 추정의 에러를 크게 발생시키지 않기 때문에 고속 모션 추정에 따른 화질의 저하를 방지할 수 있는 효과가 있다.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예를 상세히 설명한다. 본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 것이며, 단지 본 실시예들은 본 발명의 개시가 완전하도록 하며, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다. 명세서 전체에 걸쳐 동일 참조 부호는 동일 구성 요소를 지칭한다.

도 2는 본 발명의 일 실시예에 따른 모션 추정 방법을 구현하는 비디오 인코딩 장치(100)의 구성을 도시한 블록도이다.

비디오 인코딩 장치(100)는 블록 분할부(110), 비용 계산부(130), 스킵 결정부(140), 모션 추정부(150), 모션 보상부(160), 차분기(165), 공간적 변환부(170), 양자화부(180) 및 엔트로피 부호화부(190)를 포함하여 구성될 수 있다.

블록 분할부(110)는 입력 프레임을 모션 벡터의 할당 단위인 블록, 즉 매크로블록 또는 서브 매크로블록의 크기로 분할한다. 상기 매크로블록은 16x16의 픽셀 크기를 갖는 블록(16x16 블록)이고, 상기 서브 매크로블록은 그 보다 작은 크기의 블록이다. H.264에서 상기 서브 매크로블록에는 16x8 블록, 8x16 블록 및 8x8 블록이 존재하며, 상기 8x8 블록은 다시 8x4 블록, 4x8 블록 및 4x4 블록으로 나뉘어질 수 있다. H.264에서는 16x16 블록, 16x8 블록, 8x16 블록, 8x8 블록을 각각 모드 1(이하, MD1), 모드 2(이하, MD2), 모드 3(이하, MD3) 및 모드 8(이하, MD8)로 정의하고 있으며, 움직임이 없는 모드(즉, 모션 벡터가 0인 모드)를 모드0(이하, MD0)으로 정의하고 있다. 이와 같이, H.264에서는 다양한 블록들의 크기에 따라서 실제 코딩을 수행한 후, 코딩의 결과가 가장 좋은 블록 및 그 블록에 대한 모션 벡터를 선택하는 방식을 택한다. 본 발명의 일 실시예에 있어서, 블록 분할부(110)는 상기 H.264 표준에서와 마찬가지의 방식으로 계층적 구조로 매크로블록을 분할한다.

비용 계산부(130)는 특정 모드의 블록을 기초로 인터 프레임 코딩을 수행한 결과 발생하는 코딩 비용을 계산하여, 스킵 결정부(140)에 제공한다. 일반적으로, 특정한 코딩 방식을 수행하기 위하여 소요되는 코딩 비용은 다음의 수학식 1과 같이 정의될 수 있다.

여기서, E는 영상의 에러를, B는 비트량을 각각 나타낸다. 구체적으로, 상기 E는 특정 모드의 블록을 기초로 인터 프레임을 수행한 경우의 SAD(sum of absolute difference)(원래 영상과 코딩 후 복원된 영상 간의 에러의 합)이고, B는 상기 특정 모드의 블록을 코딩하기 위하여 필요한 비트량이다. 상기 λ는 라그랑지안 계수로서 에러의 크기의 감소에 중시할지, 또는 비트량의 크기의 감소를 중시할지를 조절하는 파라미터이다.

수학식 1과 같은 계산을 위해서, 비용 계산부(130)는 양자화부(180)로부터 출력되는 신호, 즉 인코딩된 데이터의 비트량(B)을 계산하고, 상기 인코딩된 데이터를 복원하여 원래 영상과의 차이를 계산하여 에러(E)를 계산할 수 있다.

스킵 결정부(140)는 비용 계산부(130)로부터 제공되는 상위 모드의 블록들에 대한 코딩 비용을 바탕으로, 현재 모드의 블록에 대한 스킵 여부를 결정한다. 도 3은 이와 같은 블록 모드에 대한 계층 구조를 보여준다. 예를 들어, MD1은 상위 계층(계층 3)에 속하고, MD2 및 MD3은 중간 계층(계층 2)에 속하며, MD8은 하위 계층(계층 1)에 속한다. 이와 같은 계층 관계는 해당 모드의 블록들 간의 포함 관계에 의하여 정의될 수 있다. 즉, MD1은 MD2나 MD3를 포함할 수 있고, MD2나 MD3는 MD8을 포함할 수 있기 때문에 도 3과 같은 계층이 정의될 수 있는 것이다. MD2와 MD3는 동일한 면적을 가지고 상호 포함 관계를 형성할 수 없기 때문에 동일한 계층에 대등하게 형성된다.

스킵 결정부(140)는 개념적으로는, 다음과 같은 수학식 2에 따라서 스킵 여부를 결정한다. 여기서 TH는 소정의 임계치를 의미한다.

수학식 2가 성립된다면, 현재 모드에 가까운 상위 모드가 움직임이 없는 모드(MD0)에 비하여 코딩 비용이 높다(잘 맞지 않는다)는 의미이고, 이는 현재 스킵 여부를 결정하고자 하는 모드(이하, 현재 모드)의 코딩 비용도 다소 높을 수 있을 것이라는 것을 의미한다. 이와 같이 현재 모드의 코딩 비용이 어느 정도 높을 것으로 예상되는 경우에는 굳이 현재 모드에 관한 모션 추정 과정을 거치지 않는 것이 타당할 것이다. 물론, 이와 같은 판단이 항상 정확한 것은 아니라고 하더라도, 다수의 모드들 중에서 상기 현재 모드가 선택되지 않을 뿐이고 그 이외의 다른 모드가 선택될 것이다. 이와 같이, 간단한 판단 알고리즘에 의해서 가변 블록 매칭 기반의 모션 추정의 계산량을 상당히 감소시킬 수 있다. 게다가, 상기 판단 알고리즘에서 사용되는 각각의 모드에 대한 코딩 비용은, 본 발명을 수행하기 위하여 별도로 계산되어야 하는 값이 아니라, 가변 블록 매칭 기법을 사용하는 H.264 등의 코덱에서는 이미 계산되어 있는 값이다. 따라서, 종래의 고속 모션 추정 기술들과 달리 추가적인 계산의 부담을 덜 수 있다.

스킵 결정부(140)는 스킵할 것으로 결정된 모드의 블록은 모션 추정부(150)에 제공하지 않고, 스킵하지 않을 것으로 결정된 모드의 블록만을 모션 추정 부(150)에 제공하게 된다. 스킵 결정부(140)에서 수행되는 모드 스킵의 구체적인 실시예와, 상기 임계치(TH)를 결정하는 방법에 관해서는 보다 자세히 후술하기로 한다.

모션 추정부(150)는 참조 프레임을 참조하여, 스킵하지 않을 것으로 결정된 모드의 블록들에 대한 모션 벡터를 구한다. 상기 참조 프레임은 현재의 입력 프레임에 대해 시간적으로 이전 또는 이후의 프레임일 수 있다. 본 발명에 있어서 모션 추정의 구체적인 프로세스는 기존의 코덱들에 있어서와 마찬가지이므로 구체적인 설명은 생략하기로 한다. 다만, 일 예로서, 모션 추정부(150)는 주어진 모드의 블록을 상기 참조 프레임의 특정 탐색 영역 내에서 픽셀단위로 움직이면서 그 에러가 최저가 되는 경우의 변위를 모션 벡터로 결정할 수 있다.

모션 보상부(160)는 모션 추정부(150)로부터 제공되는 다양한 모드의 블록들에 대한 모션 벡터들을 이용하여 참조 프레임에 대하여 모션 보상을 수행함으로써 모션 보상 프레임(motion compensated frame)을 얻는다.

한편, 차분기(165)는 상기 입력 프레임에서, 상기 모션 벡터에 의해 참조 프레임을 보상한 모션 보상 프레임을 차분하여 잔차 프레임(residual frame)을 얻는다. 본 발명의 일 실시예에 있어서, 상기 잔차 프레임을 부호화하는 수단으로는 공간적 변환부(170), 양자화부(180) 및 엔트로피 부호화부(190)가 사용된다.

공간적 변환부(170)는 소정의 공간적 변환법을 이용하여, 상기 잔차 프레임을 주파수 도메인으로 변환한다. 이러한 공간적 변환법으로는 주로 DCT(Discrete Cosine Transform)가 사용되며, 때로는 웨이브렛 변환(wavelet transform)이 사용 되기도 한다. 공간적 변환 결과 구해지는 계수들을 변환 계수라고 하는데, 공간적 변환으로 DCT를 사용하는 경우 DCT 계수라고 하고, 웨이브렛 변환을 사용하는 경우 웨이브렛 계수라고 한다.

양자화부(180)는 공간적 변환부(170)에서 구한 변환 계수를 양자화한다. 양자화(quantization)란 임의의 실수 값으로 표현되는 상기 변환 계수를 일정 구간으로 나누어 불연속적인 값(discrete value)으로 나타내고, 이를 소정의 인덱스로 매칭(matching)시키는 과정을 의미한다. 특히, 공간적 변환 방법으로 웨이브렛 변환을 이용하는 경우에는 양자화 방법으로서 임베디드 양자화(embedded quantization)가 이용되기도 한다.

엔트로피 부호화부(190)는 양자화부(180)에 의하여 양자화된 변환 계수와, 모션 추정부(150)에 의하여 제공되는 모션 벡터를 무손실 부호화하여 출력 비트스트림을 생성한다. 이러한 무손실 부호화 방법으로는, 산술 부호화(arithmetic coding), 가변 길이 부호화(variable length coding), 허프만 부호화 등이 있다.

지금까지 도 2의 각 구성요소는 소프트웨어(software) 또는, FPGA(field-programmable gate array)나 ASIC(application-specific integrated circuit)과 같은 하드웨어(hardware)를 의미할 수 있다. 그렇지만 상기 구성요소들은 소프트웨어 또는 하드웨어에 한정되는 의미는 아니며, 어드레싱(addressing)할 수 있는 저장 매체에 있도록 구성될 수도 있고 하나 또는 그 이상의 프로세서들을 실행시키도록 구성될 수도 있다. 상기 구성요소들 안에서 제공되는 기능은 더 세분화된 구성요소에 의하여 구현될 수 있으며, 복수의 구성요소들을 합하여 특정한 기능을 수행하는 하나의 구성요소로 구현할 수도 있다.

이하에서는, 스킵 결정부(140)에서 모드를 스킵하는 구체적인 실시예에 대해서 설명하기로 한다. 본 발명에서는 스킵되는 모드로서 MD2 및 MD8을 고려한다.

1. MD2의 스킵

통상의 영상에 있어서 MD2가 최적으로 선택되는 경우는 10-15%로 그리 높지 않은 편이다. 따라서, 특정 조건하에 MD2를 스킵하더라도 영상의 품질 저하의 우려는 상대적으로 낮을 수 있다. 예를 들어, 스킵 결정부(140)는 다음의 수학식 3이 만족되는 경우에는 MD2를 스킵하고, 그렇지 않은 경우에는 MD2를 고려한다(즉, 모션 추정부(150)에서 모션 추정을 수행한다).

이 경우에, 상기 임계치 TH₁은 경험적 또는 실험적으로 결정될 수 있겠지만, 일 실시예로서 다음의 수학식 4에 의하여 결정될 수 있다.

TH ₁ = D_ΔPSNR - (α×D_ΔBR + β×D_ΔT)

(α>β, α+β=1)

상기 수학식 4에서, 파라미터 PSNR, BR 및 T는 각각, 최대 신호대 잡음비(Peak Signal to Noise Ratio), 비트 레이트 및 인코딩 시간을 나타낸다. 또한, D_Δ는 종래의 고속 모션 추정 기법을 사용한 경우의 해당 파라미터의 변화량과 본 발명에 따른 고속 모션 추정 기법을 사용한 경우의 해당 파라미터의 변화량 사이의 차이를 의미한다.

한편, 수학식 4에 의하여 임계치 TH₁을 결정한다고 하더라도, 상기 임계치는 소정의 범위 내에 속하도록 하는 것이 바람직하다. 다음의 표 1은 MD2를 스킵하여 코딩한 영상 Foreman, Akiyo 및 Stefan에 있어서, SR(skip ratio)과 AR(accuracy)을 표시한다. 상기 SR은 본 발명을 적용한 경우 TH₁에 따라 MD2에서 스킵되는 경우의 비율을 나타내고, AR은 정확한 모드 선택이 이루어지는 비율을 나타낸다. 여기서, CIF 해상도의 50개 프레임의 영상이 사용되었으며, QP(양자화 파라미터)는 28로 선택되었다.

표 1에서 보는 바와 같이, SR 및 AR 간에는 매우 심한 트레이드-오프(trade-off)가 존재한다. 따라서, TH₁이 0.9인 경우에는 정확도는 높지만 연산량 감소가 충분하지 않고, TH₁이 0.4인 경우에는 연산량 감소는 충분하지만 정확도에 있어서 상당한 손실이 발생하게 된다. 따라서, 수학식 4에 의하여 TH₁을 계산하는 경우에도, 전체적인 TH₁의 범위는 대략 0.5에서 0.8의 범위가 되도록 하는 것이 바람직하다.

2. MD8 의 스킵

일반적으로, 인터 프레임 코딩의 모드 결정에 있어서 MD8이 최적의 모드로 선택되는 경우는 높지 않거나 어떤 영상에서는 매우 낮다. 그럼에도 불구하고 MD8에 대한 계산 복잡성은 매우 높다고 알려져 있다. 이를 확인하기 위하여 우리는 알려진 대표 영상들을 샘플로 하여, 전체 모드들 중에서 MD8을 제거한 경우 계산량의 감소를 살펴 보았다. 그 결과, 영상에 따라서 차이가 있기는 하지만 대략 47%의 연산량 감소가 나타났다. 다시 말하면, 고속 모션 추정에 있어서 MD8에 대한 계산 복잡성을 줄이는 것은 매우 중요하다는 것을 의미한다. 그런데, 위에서 MD2가 스킵되는 경우와 그렇지 않은 경우가 있었으므로 MD8의 스킵 여부를 결정하는 알고리즘은 다시 두 가지로 나뉘어질 수 있다.

2.1 MD2 가 없는 경우

스킵 결정부(140)가 MD2를 스킵할 것으로 결정한 경우에는, MD2에 대하여 계산되는 코딩 비용은 존재하지 않는다. 따라서, 이 경우에는 MD8의 상위 모드인 MD2 및 MD3 중에서 MD2는 이용될 수 없으므로 MD2 대신에 MD1을 이용한다. 예를 들어, 스킵 결정부(140)는 다음의 수학식 5와 같이, MD1 및 MD3을 이용하여 MD8의 스킵 여부를 결정할 수 있다.

상기 임계치 TH₂도 역시 전술한 수학식 4에 따라 계산될 수 있다.

한편, TH₁에서와 마찬가지로, TH₂의 가용한 범위를 선택하기 위하여, 영상 Foreman, Akiyo 및 Stefan에 대하여 계산된 SR(skip ratio)과 AR(accuracy)는 다음의 표 2에 나타낸 바와 같다.

표 2에서 전체적으로 살펴볼 때, TH₂가 0.7 근처인 경우에는 지나치게 낮은 AR을 나타내므로, TH₂는 대략 0.8 내지 0.9 정도 범위에서 결정되는 것이 바람직하다고 생각된다.

2.2 MD2 가 있는 경우

스킵 결정부(140)가 MD2를 스킵하지 않을 것으로 결정한 경우에는, MD2에 대하여 계산되는 코딩 비용은 이미 존재한다. 따라서, 이 경우에는 MD8의 상위 모드인 MD2 및 MD3를 모두 이용하여 MD8의 스킵 여부를 결정할 수 있다. 예를 들어, 스킵 결정부(140)는 다음의 수학식 6과 같이, MD2 및 MD3을 이용하여 MD8의 스킵 여부를 결정할 수 있다.

상기 임계치 TH₃도 역시 전술한 수학식 4에 따라 계산될 수 있다.

한편, TH₁에서와 마찬가지로, TH₃의 가용한 범위를 선택하기 위하여, 영상 Foreman, Akiyo 및 Stefan에 대하여 계산된 SR(skip ratio)과 AR(accuracy ratio)는 다음의 표 3에 나타낸 바와 같다.

표 3은 표 1이나 2와 비교할 때, 상당히 높은 AR을 보여준다. 따라서, 0.2 내지 0.7 범위 내에서의 적절한 임계치를 선택하는 것이 가능할 것이다.

도 4는 본 발명의 일 실시예에 따른 모션추정 방법을 구체적으로 도시하는 흐름도이다.

먼저, 블록 분할부(110)는 입력 프레임을 복수의 모드에 대응하는 블록들로 분할한다(S41).

비용 계산부(130)는 상기 블록들 중에서, 코딩하고자 하는 현재 블록에 대한 상위의 모드를 갖는 블록에 대한 코딩 비용을 계산한다(S42).

스킵 결정부(140)는 상기 코딩 비용을 기준으로 상기 현재 블록의 스킵 여부를 결정한다. 구체적으로, 스킵 결정부(140)는 A/B가 임계치(TH)를 상회하는지를 판단한다(S43). 여기서, A는 상위의 모드를 갖는 블록에 대한 코딩 비용을, B는 움직임이 없는 모드에 대한 코딩 비용을 각각 의미한다. 이러한 코딩 비용들은 수학식 1의 예와 같은 방식으로 계산될 수 있다.

구체적으로, 상기 현재 블록이 16x8 모드인 경우에는, 상기 상위의 모드를 갖는 블록은 16x16 모드의 블록인 것이 바람직하다.

또한, 상기 현재 블록이 8x8 모드인 경우에는, 다음의 두 가지 경우로 나뉘어질 수 있다.

첫째, 상기 8x8 모드의 상위에 있는 16x8 모드의 블록이 스킵된 경우에는, 상기 상위의 모드를 갖는 블록에 대한 코딩 비용은, 16x16 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인 것이 바람직하다(수학식 5 참조).

둘째, 상기 8x8 모드의 상위에 있는 16x8 모드의 블록이 스킵되지 않은 경우에는, 상기 상위의 모드를 갖는 블록에 대한 코딩 비용은 16x8 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인 것이 바람직하다(수학식 6 참조).

한편, S43의 판단 결과, 상기 A/B가 임계치를 상회하는 경우(S43의 예)에는, 스킵 결정부(140)는 상기 현재 블록을 스킵하고 다음 순위의 블록을 선택한다(S44). 여기서, 순위란 예를 들어, MD0, MD1, MD2, MD3, MD8과 같이 계층적 구조에 따른 순위일 수 있다. 스킵 결정부(140)는 상기 다음 순위의 블록에 대해서도 마찬가지로, S43의 판단 과정을 수행하게 된다.

S43의 판단 결과, 상기 A/B가 임계치를 상회하지 않는 경우(S43의 아니오)에는, 모션 추정부(150)는 상기 현재 블록에 대하여 모션 벡터를 구하는 과정, 즉 모션 추정 과정을 수행한다(S45).

마지막으로, 모든 순위의 모드에 대하여 이러한 과정이 완료되었으면(S46의 예) 종료되고, 그렇지 않다면(S46의 아니오), 다음 순위의 블록을 선택하는 과정(S45)을 반복한다.

다음의 표 4는 고속 모션 추정에 있어서, 가장 최근에 발표된 종래기술과 본 발명을 다양한 영상들에 적용한 결과를 보여준다. 상기 종래기술은 "Fast inter-mode decision in an H.264/AVC encoder using mode and Lagrangian cost correlation, IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 2, pp. 302-306, Feb. 2009"이다.

상기 표 4를 참조하면, 본 발명은 종래의 고속 모션 추정 기술에 비하여, 인코딩 시간(T)은 한층 더 단축시키면서도, 화질(PSNR)의 감소나 비트 레이트(BR)의 증가를 거의 유발하지 않음을 알 수 있다. 오히려 화질(PSNR) 면에 있어서는, 전체 블록 모드를 고려하는 H.264 방식에 비하여 약간이나마 증가하는 결과를 보여준다. 또한, 본 발명을 적용하는 경우에 기존의 H.264 방식에 비하여 증가하는 비트 레이트는 0.4%로서 거의 미미함을 알 수 있다.

이상 첨부된 도면을 참조하여 본 발명의 실시예를 설명하였지만, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명이 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 실시될 수 있다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야 한다.

도 1은 블록 모션 추정 기법을 사용하는 인터 프레임 코딩의 기본 개념을 보여주는 도면이다.

도 2는 본 발명의 일 실시예에 따른 모션 추정 방법을 구현하는 비디오 인코딩 장치의 구성을 도시한 블록도이다.

도 3은 다양한 블록 모드들 간의 계층 구조를 보여주는 도면이다.

도 4는 본 발명의 일 실시예에 따른 모션추정 방법을 구체적으로 도시하는 흐름도이다.

(도면의 주요부분에 대한 부호 설명)

100: 비디오 인코딩 장치 110: 블록 분할부

130: 비용 계산부 140: 스킵 결정부

150: 모션 추정부 160: 모션 보상부

165: 차분기 170: 공간적 변환부

180: 양자화부 190: 엔트로피 부호화부

Claims (21)

1. (a) 입력 프레임을 복수의 모드에 대응하는 블록들로 분할하는 단계;

   (b) 상기 블록들 중에서, 코딩하고자 하는 현재 블록을 포함하는 상위 계층의 모드를 갖는 블록에 대한 코딩 비용을 계산하는 단계;

   (c) 상기 상위 계층의 모드를 갖는 블록에 대한 코딩 비용을, 움직임이 없는 모드에 대한 코딩 비용으로 나눈 값이 소정의 임계치를 넘는 경우에, 상기 현재 블록을 스킵할 것으로 결정하는 단계; 및

   (d) 상기 결정 단계에서 스킵하지 않을 것으로 결정된 현재 블록에 대하여 모션 벡터를 구하는 단계를 포함하는, 고속 모션 추정 방법.
2. 제1항에 있어서,

   상기 코딩 비용은

   영상의 에러 및 비트량의 선형 조합으로 계산되는, 고속 모션 추정 방법.
3. 제1항에 있어서,

   상기 현재 블록을 스킵할 것으로 결정된 경우에는, 상기 현재 블록에 대한 다음 순서의 블록에 대하여 상기 (c) 단계를 반복하는 단계를 더 포함하는, 고속 모션 추정 방법.
4. 삭제
5. 제1항에 있어서,

   상기 임계치는

   PSNR(peak signal-to-noise ratio), 비트 레이트 및 인코딩 시간의 차이 값의 선형 조합에 의하여 계산되는, 고속 모션 추정 방법.
6. 제1항에 있어서,

   상기 현재 블록은 16x8 모드의 블록이고, 상기 상위의 모드를 갖는 블록은 16x16 모드의 블록인, 고속 모션 추정 방법.
7. 제1항에 있어서,

   상기 현재 블록은 8x8 모드의 블록인, 고속 모션 추정 방법.
8. 제7항에 있어서,

   상기 상위의 모드를 갖는 블록에 대한 코딩 비용은 16x8 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인, 고속 모션 추정 방법.
9. 제7항에 있어서,

   상기 현재 블록의 상위 모드 중 하나인 16x8 모드의 블록이 스킵된 경우에는,

   상기 상위의 모드를 갖는 블록에 대한 코딩 비용은 16x16 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인, 고속 모션 추정 방법.
10. 제1항에 있어서,

    상기 임계치는

    스킵 비율(skip ratio)과 정확도 비율(accuracy ratio)의 트레이드 오프(trade-off)에 의하여 결정되는, 고속 모션 추정 방법.
11. 입력 프레임을 복수의 모드에 대응하는 블록들로 분할하는 블록 분할부;

    상기 블록들 중에서, 코딩하고자 하는 현재 블록을 포함하는 상위 계층의 모드를 갖는 블록에 대한 코딩 비용을 계산하는 비용 계산부;

    상기 상위 계층의 모드를 갖는 블록에 대한 코딩 비용을, 움직임이 없는 모드에 대한 코딩 비용으로 나눈 값이 소정의 임계치를 넘는 경우에, 상기 현재 블록을 스킵할 것으로 결정하는 스킵 결정부;

    상기 스킵 결정부에 의하여 스킵하지 않을 것으로 결정된 현재 블록에 대하여 모션 벡터를 구하는 모션 추정부;

    상기 입력 프레임에서, 상기 구한 모션 벡터에 의해 참조 프레임을 보상한 모션 보상 프레임을 차분하여 잔차 프레임을 얻는 차분기; 및

    상기 잔차 프레임을 부호화하는 수단을 포함하는 비디오 인코딩 장치.
12. 제11항에 있어서,

    상기 잔차 프레임을 부호화하는 수단은,

    상기 잔차 프레임을 주파수 도메인으로 변환하여 변환 계수를 생성하는 공간적 변환부;

    상기 변환계수를 양자화하는 양자화부; 및

    상기 양자화의 결과와 상기 모션 벡터를 무손실 부호화하는 엔트로피 부호화부를 포함하는 비디오 인코딩 장치.
13. 제11항에 있어서,

    상기 코딩 비용은

    영상의 에러 및 비트량의 선형 조합으로 계산되는, 비디오 인코딩 장치.
14. 제11항에 있어서,

    상기 스킵 결정부는

    상기 현재 블록을 스킵할 것으로 결정된 경우에는, 상기 현재 블록에 대한 다음 순서의 블록에 대하여 스킵 여부를 결정하는, 비디오 인코딩 장치.
15. 삭제
16. 제11항에 있어서,

    상기 임계치는

    PSNR(peak signal-to-noise ratio), 비트 레이트 및 인코딩 시간의 차이 값의 선형 조합에 의하여 계산되는, 비디오 인코딩 장치.
17. 제11항에 있어서,

    상기 현재 블록은 16x8 모드의 블록이고, 상기 상위의 모드를 갖는 블록은 16x16 모드의 블록인, 비디오 인코딩 장치.
18. 제11항에 있어서,

    상기 현재 블록은 8x8 모드의 블록인, 비디오 인코딩 장치.
19. 제18항에 있어서,

    상기 상위의 모드를 갖는 블록에 대한 코딩 비용은 16x8 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인, 비디오 인코딩 장치.
20. 제18항에 있어서,

    상기 현재 블록의 상위 모드 중 하나인 16x8 모드의 블록이 스킵된 경우에는,

    상기 상위의 모드를 갖는 블록에 대한 코딩 비용은 16x16 모드의 블록에 대한 코딩 비용과 8x16 모드의 블록에 대한 코딩 비용의 평균인, 비디오 인코딩 장치.
21. 제11항에 있어서,

    상기 임계치는

    스킵 비율(skip ratio)과 정확도 비율(accuracy ratio)의 트레이드 오프(trade-off)에 의하여 결정되는, 비디오 인코딩 장치.

Images