Advanced
Enhanced Binary Block Matching Method for Constrained One-bit Transform based Motion Estimation
Enhanced Binary Block Matching Method for Constrained One-bit Transform based Motion Estimation
Journal of Broadcast Engineering. 2015. Mar, 20(2): 257-264
Copyright © 2015, The Korean Society of Broadcast Engineers
  • Received : November 17, 2015
  • Accepted : March 26, 2015
  • Published : March 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
형 도 김
제 창 정
jjeong@hanyang.ac.kr

Abstract
본 논문에서는 개선된 이진 블록 매칭 방법을 사용한 제한된 1비트 변환 (Constrained One-bit Transform : C1BT) 알고리듬을 제안한다. 이진 영상 기반의 움직임 예측은 기존의 정합 오차 기준인 SAD (Sum of Absolute Difference)를 사용한 움직임 예측의 방대한 계산량을 줄이기 위해 정합오차 기준을 이진 논리 연산을 사용하는 NNMP (Number of Non-Matching Points)를 사용하여 움직임 예측의 속도를 향상시키고 하드웨어 구현을 용이하게 하는 방법이다. C1BT 알고리듬은 기존의 1BT알고리듬이 원본의 픽셀값을 1개의 비트만으로 표현하며 발생하는 단점을 보완하여 이진 영상 기반의 움직임 예측의 정확도를 향상시킨 알고리듬이다. 이 논문에서는 이진 블록 기반의 움직임 예측이 작은 크기의 정합블록을 사용할 때 더욱 정확한 정확도를 갖는 방법을 제안하였다. 기존의 C1BT기반의 움직임 예측의 결과와 제안하는 알고리듬의 결과를 비교해 보았을 때 PSNR측면에서 더 우수한 성능을 갖는 것을 볼 수 있다.
Keywords
Ⅰ. 서 론
최근의 빠르게 발전하고 있는 디스플레이 기술에 따라고 해상도 영상에 대한 수요 또한 증가하고 있다. 디지털 동영상은 방대한 정보량을 가지고 있어 유선 또는 무선 네트워크를 통한 전송이나 디지털 미디어 장치에 저장하기에 큰 어려움이 있다. 따라서 디지털 동영상을 압축하여 정보량을 줄이는 동영상 압축기술이 필수적으로 사용되어 진다. 디지털 동영상의 정보량을 효과적으로 줄이기 위한 많은 기술들 중 동영상을 구성하는 연속된 영상들의 화면 간의 중복 특성을 사용하여 현재 영상을 예측하고 예측 영상을 통해 화면을 압축하여 큰 압축 효율을 얻는 화면 간 압축(Inter frame coding) 기술이 널리 사용되고 있다. 화면 간 영상압축 기술로 대표적으로 사용되고 있는 방법은 블록단위 움직임 예측 기술이다. 블록 단위 움직임 예측은 현재 부호화를 수행하는 영상을 특정한 크기의 블록단위로 나누어 각 블록에 가장 적합한 블록을 참조영상에서 가져와 영상의 위치정보를 사용하여 동영상을 압축하는 방법이다. 블록 정합 오차 기준으로 SAD (Sum of Absolute Difference)를 사용한 전역 탐색 알고리듬 (Full Search Algorithm : FSA)이 최적의 블록단위 움직임 예측 결과를 갖는 기준으로 사용되어 지고 있다. FSA는 현재 부호화를 수행하는 블록과 최적의 정합 블록을 찾기 위해 참조 영역안의 모든 후보 블록들과 블록 정합오차를 계산하는 방법이다. SAD를 블록 정합 오차 측정 방법으로 사용하는 전역 탐색 알고리듬은 방대한 계산량을 필요로 하며 이러한 방대한 계산량을 줄이기 위해 많은 고속 움직임 예측 알고리듬 들이 제안되어 왔다.
영상의 이진 변환을 사용한 움직임 예측 방법은 기존의 SAD를 사용한 FSA알고리즘의 화면 간 예측에 필요한 방대한 계산량을 줄이기 위해 제안된 고속 움직임 예측 알고리듬이다. 영상의 이진 변환은 원본의 디지털 영상을 픽셀 단위의 이진 변환 또는 블록 단위의 이진 변환 과정을 사용한다. 영상의 이진 변환의 결과로 영상의 각 픽셀을 표현하는데 몇 개의 비트만을 사용하는 이진 영상이 생성된다. 이진 변환을 통해 생성된 이진 영상은 블록 정합 오차 측정 방법으로 기존의 높은 계산 복잡도를 갖는 SAD연산 대신, 이진 논리연산을 사용하여 낮은 계산 복잡도를 갖는 NNMP(Number of Non-Matched Points)연산을 사용하여 고속 움직임 예측을 수행한다.
이진 변환 알고리듬으로는 1비트 변환 (One-bit Transform : 1BT) [1] 알고리듬, 2비트 변환 (Two-Bit Transform : 2BT) [2] 알고리듬과 1비트 변환 알고리듬을 개선한 제한된 1비트 변환 (Constrained One-bit Transform : C1BT) [3] 알고리듬 등이 있다.
1비트 변환 알고리듬은 가장 먼저 제안된 이진 변환알고리듬으로 원본영상의 각 픽셀들을 다중 대역 통과 필터 커널을 통해 생성된 문턱값들과 비교하여 하나의 이진 픽셀을 생성하는 알고리듬이다. 2비트 변환 알고리듬은 1비트 변환 알고리듬이 픽셀단위 변환을 수행하는 것과 달리 블록단위로 문턱값을 계산하여 이진 변환을 수행한다. 또한 문턱값으로 블록 평균과 근사 표준편차 값을 사용하여 2개의 이진 영상을 생성하여 움직임 예측의 정확도를 개선 시켰다. 제한된 1비트 변환 알고리듬은 기존의 1비트 변환 알고리듬의 변환 과정에서 발생하는 문제점을 개선하기 위해 CM(Constrain Mask)이진 값을 생성하여 움직임 예측의 정확도를 개선시킨 알고리듬이다.
블록 단위 움직임 예측은 영상을 특정 크기의 블록 단위로 분할을 하여 각 블록 마다 예측영상을 생성하는 방법이다. 영상을 분할할 때 작은 크기의 블록을 사용하면 영상을 구성하는 블록의 개수가 증가하여 화면 간 예측의 계산 복잡도는 증가하지만 영상을 더욱 세밀한 단위로 나누어 보상을 하기 때문에 더욱 정확한 영상의 예측을 수행할 수 있다. 이진 변환 알고리듬을 사용한 움직임 예측에서는 영상을 분할하는데 작은 단위의 블록을 사용하는 경우 블록정합 오차를 측정하기 위한 비교 지표가 되는 이진 픽셀의 개수가 줄어들어 움직임 예측의 정확도가 크게 떨어지게 된다. 본 논문에서는 제한된 1비트 움직임 예측알고리듬을 사용한 움직임 예측을 기반으로 작은 크기의 단위 블록을 사용하여 예측을 수행할 때 정확도가 떨어지는 단점을 보완하여 화면 간 예측의 정확도를 향상시키는 방법에 대해 제안한다.
Ⅱ. 기존의 이진 변환 기반 움직임 예측 알고리듬
- 1. 1비트 변환 알고리듬 기반의 움직임 예측
1비트 변환 알고리듬은 원본의 입력영상을 이진 영상으로 변환하기 위해 17 × 17 크기의 다중대역 필터 커널을 통해 원본의 영상을 필터링 하여 이진 값 결정에 사용되는 문턱값을 생성한다. 다중대역 필터 커널 K 는 다음 식(1)과 같이 정의된다.
PPT Slide
Lager Image
이진 영상의 픽셀 값은 다음의 식(2)와 같이 필터 커널 K 를 통해 생성된 문턱값과 비교를 하여 결정된다.
PPT Slide
Lager Image
위의 식(2)에서 F ( i , j )는 원본영상의 위치 i , j 에서의 픽셀 값을 의미하며
PPT Slide
Lager Image
는 해당 위치에서의 문턱값을 의미한다. 위의 과정으로 이진 픽셀값 B ( i , j )이 생성되며 영상의 모든 픽셀을 이진 값으로 변환하여 이진 영상 B 가 생성된다.
이진영상 B 를 사용하여 움직임 예측을 수행하기 위해 블록 정합 오차 계산 방법으로 다음의 식(3)과 같이 이진 연산을 통해 블록정합 오차를 계산하는 NNMP(Number of Non-Matched Points) 알고리듬을 사용한다.
PPT Slide
Lager Image
식(3)에서 Bt Bt -1 은 각각 현재 이진영상과 참조 이진영상을 의미하며 ⊕은 이진 XOR연산을 의미한다. m n 값은 참조 영상에서 후보블록의 위치를 의미하며 s 값은 참조 영역의 크기를 의미하고 N 은 정합 블록의 크기를 나타낸다. 위의 식(3)을 통해 두 이진 블록에서 다른 이진 값을 갖는 픽셀의 수가 NNMP값이 계산된다.
- 2. 제한된 1비트 변환 알고리듬 기반의 움직임 예측
제한된 1비트 변환 알고리듬은 기존의 1비트 변환 알고리듬의 단점을 보완하여 움직임 예측의 정확도를 개선시킨 알고리듬이다. 기존의 1비트 변환 알고리듬은 픽셀의 이진값을 생성하기 위해 필터 커널 K 를 사용하여 생성한 픽셀의 문턱값과 비교하여 문턱값보다 원본 픽셀값이 크고 작음을 1과 0으로 표현한다. 1비트 변환에서 위의 과정을 통해 생성된 이진 값은 값의 표현의 한계로 인하여 움직임 예측에서 픽셀값의 비교에 어려움이 발생한다. 이러한 기존의 1비트 변환 알고리듬이 가지고 있는 단점을 보완하기 위해 제한된 1비트 변환 알고리듬은 입력 문턱값 D 를 사용하여 현재 이진값이 유효한지를 나타내는 Constraint Mask(CM) 이진값을 추가로 생성한다. 제한된 1비트 변환 알고리듬의 변환은 다음 식 (4)과 같이 정의 된다.
PPT Slide
Lager Image
위의 식(4)에서 F ( i , j )는 원본 영상의 위치 i , j 에서의 픽셀 값을 나타내며
PPT Slide
Lager Image
는 식(1)의 필터 커널 K 를 통해 생성된 문턱값을 나타낸다. 식(2)와 식(4)를 통해 생성된 두 이진 영상 B CM 을 사용한 블록 단위 움직임 예측을 위해 블록 정합 오차 계산식으로 다음의 식(5)를 사용한다.
PPT Slide
Lager Image
위의 식에서 ⊙은 이진 AND연산을 의미하며 ║은 이진 OR연산을 의미한다. 위의 식을 통하여 현재 블록의 두 이진픽셀중 적어도 하나의 CM 값이 1인 픽셀들의 이진 값 Bt 와 참조블록의 이진값 B t–1 을 비교하여 다른 이진 값을 갖는 픽셀의 수를 계산한다.
Ⅲ. 제안하는 알고리듬
기존의 블록단위 움직임 예측은 특정한 크기의 단위 블록으로 영상을 나누어 화면 간 예측을 수행한다. 영상을 나누는 단위 블록의 크기는 영상을 얼마나 세밀하게 나누어 보상을 해나가는지를 의미한다. 영상의 움직임 예측 과정에서 영상을 나누는 단위 블록의 크기를 줄인다면 영상의 세밀한 예측과 보상을 통해 움직임 예측의 정확도가 향상되는 것을 기대해 볼 수 있다. 다음의 표 1 에서는 블록 매칭 오차 측정으로 SAD알고리듬을 사용한 FSA 알고리듬에서 영상을 나누는 단위 블록을 16 × 16 크기의 블록으로 사용한 결과와 8 × 8크기의 블록으로 사용한 결과를 비교하고 있다.
SAD를 사용한 FSA에서 단위 블록의 크기에 따른 PSNR 결과Table 1. PSNR results of SAD FSA using differenct block size
PPT Slide
Lager Image
SAD를 사용한 FSA에서 단위 블록의 크기에 따른 PSNR 결과 Table 1. PSNR results of SAD FSA using differenct block size
위의 표 1 에서 보는 바와 같이 블록단위 움직임 예측에 작은 크기의 매칭블록을 사용하는 것이 영상을 더욱 세밀하게 보상하여 PSNR측면에서 좋은 결과를 갖는 것을 볼 수 있다.
하지만 이진 변환을 기반으로 하는 블록단위 움직임 예측은 두 블록의 절대적인 픽셀 값의 차이를 측정하는 것이 아니라 계산된 문턱값과의 상대적인 값의 높고 낮음을 비교해 보는 것으로 작은 매칭 블록을 사용하는 경우 비교의 지표가 되는 픽셀의 개수가 줄어들어 움직임 예측의 정확도가 떨어지거나 화면 간 예측의 정확도 개선 효과가 크지 않다. 다음의 표 2 는 기존의 이진 변환 기반의 움직임 예측에서 16 × 16 크기의 매칭블록과 8 × 8 크기의 매칭블록을 사용한 결과이다.
다른크기의 블록을 사용한 기존의이진 변환기반의 움직임 예측PSNR 결과Table 2. PSNR results of binary transform motion estimation using different block size
PPT Slide
Lager Image
다른크기의 블록을 사용한 기존의이진 변환기반의 움직임 예측PSNR 결과 Table 2. PSNR results of binary transform motion estimation using different block size
위의 표 2 의 결과를 확인해 보면 기존의 움직임 예측에 8 × 8 작은 블록을 사용하는 경우 기존의 1비트 변환 알고리듬에선 예측의 정확도가 감소하고 제한된 1비트 변환 알고리듬은 조금 향상된 결과를 갖는 것을 볼 수 있다.
이번 장에서는 이진 변환 기반의 블록매칭 알고리듬을 통한 화면 간 예측 과정에서 화면의 분할을 8 × 8 크기의 단위블록을 사용하며, 8 × 8 크기의 단위블록을 사용하여 영상을 분할하는 경우 움직임 추정의 정확도가 떨어지는 단점을 보완하여 화면 간 예측의 정확도를 크게 향상시키는 방법에 대하여 제안한다. 기존의 이진 변환 기반의 움직임 추정의 과정에서는 영상을 분할하는 단위 블록과 블록 단위의 움직임 추정의 과정에서 현재 블록과 후보 블록과의 블록 정합 오차과정에서 사용하는 정합블록의 크기를 동일한 크기의 블록을 사용한다.
본 논문에서 제안하는 개선된 이진 블록 정합 방법은 이진 블록 정합의 과정에서 정합 블록의 크기를 영상을 분할하는 단위 블록의 크기와 다른 크기를 사용하여 움직임 추정의 정확도를 향상시키는 방법이다. 다음의 그림 1 은 기존의 이진 변환 기반의 움직임 추정의 과정을 나타낸다. 기존의 움직임 추정의 과정에서는 그림 1 에서와 같이영상을분할하고있는 단위 블록의 크기와 동일한 크기의 정합 블록을 사용하여 참조 영상의 후보 블록과 블록 정합 오차를 측정한다.
PPT Slide
Lager Image
기존의 블록 매칭 알고리듬 Fig. 1. Conventional block-matching algorithm
그림 2 는 본 논문에서 제안하는 블록 매칭 알고리듬 과정에 대하여 나타내고 있다. 본 논문에서 보다 정교한 움직임 추정을 위해 제안하는 개선된 이진 블록 정합 방법은 그림 3 에서와 같이 영상을 분할하고 있는 단위 블록을 중심으로 단위블록의 주변 이진 픽셀들을 포함하는 정합 블록을 사용하여 참조 영상에서의 후보 블록과 이진 블록 정합 과정을 수행한다.
PPT Slide
Lager Image
제안하는 블록 매칭 알고리듬 Fig. 2. Proposed block-matching algorithm
PPT Slide
Lager Image
블록 N과 블록 W Fig. 3. The block N and block
위의 그림 3 에서 N 은 현재 영상을 분할하는 단위 블록의 크기를 타나내며 W 는 블록 정합에 사용되는 블록의 크기를 나타낸다. 기존의 방법에서 움직임 예측, 보상에 사용하는 블록의 크기를 8 × 8로 정하는 경우 블록의 정합을 비교를 할 때 지표로서 사용되는 픽셀의 수 또한 8 × 8개가 된다. 위의 방법을 통해 블록 정합 비교에 사용되는 블록의 크기를 W × W 로 키우는 경우 블록 정합의 비교 지표가 되는 픽셀의 개수 또한 W × W 로 증가하여 더욱 정확한 블록의 비교를 수행 할 수 있다.
Ⅳ. 실험 결과
본 논문에서 제안된 알고리듬 기반의 움직임 예측과 기존의 이진 변환 기반의 움직임 예측의 결과를 PSNR ( dB )의 측면에서 비교해 보았다. 실험에 사용된 디지털 동영상은 CIF (352 × 288)의 크기를 갖는 10개의 시퀀스를 사용하였으며 움직임 예측의 측정에 영상의 휘도 성분만을 고려하였다. 실험의 조건으로는 탐색 범위로 ± 16를 사용하였다. 먼저 표 3 에서 제안된 알고리듬에서 블록 정합에 사용되는 블록의 크기 W 를 10에서 16까지 증가시키면서 움직임 예측의 결과를 확인해 보았다. 실험에서 이진 값 CM 을 생성하는데 필요한 문턱값은 10을 사용하였다.
제안하는 알고리듬에서W값에 따른 PSNR 결과 비교Table 3. PSNR results of proposed algorithm based motion estimation using differentWvalue
PPT Slide
Lager Image
제안하는 알고리듬에서 W값에 따른 PSNR 결과 비교 Table 3. PSNR results of proposed algorithm based motion estimation using different W value
위의 표 3 에서 보는 바와 같이 제안된 알고리듬에서 W 값을 14로 사용하는 경우 가장 좋은 결과를 갖는 것을 볼 수 있다. W 값이 16인 경우 블록 정합 비교에 가장 많은 이진 픽셀 값을 사용하지만 움직임 예측의 정확도 측면에서 성능이 떨어짐을 볼 수 있다.
제안하는 알고리듬의 성능개선의 효과를 확인하기 위해 표 4 5 에서는 기존의 알고리듬 기반의 움직임 예측 결과와 제안하는 알고리듬의 움직임 예측 결과를 PSNR측면에 비교하였다. 표 4 에서는 기존의 이진 변환 알고리듬과 SAD를 사용한 움직임 예측에서 8 × 8크기의 블록을 사용할 때의 결과를 비교해 보았다.
기존의 이진 변환 움직임 예측과 제안하는 알고리듬 기반의 움직임 예측 PSNR 결과 비교Table 4. PSNR results of conventional binary motion estimation and proposed algorithm
PPT Slide
Lager Image
기존의 이진 변환 움직임 예측과 제안하는 알고리듬 기반의 움직임 예측 PSNR 결과 비교 Table 4. PSNR results of conventional binary motion estimation and proposed algorithm
기존의 이진 변환 움직임 예측과 제안하는 알고리듬 기반의 움직임 예측 PSNR 결과 비교Table 5. PSNR results of conventional binary motion estimation and proposed algorithm
PPT Slide
Lager Image
기존의 이진 변환 움직임 예측과 제안하는 알고리듬 기반의 움직임 예측 PSNR 결과 비교 Table 5. PSNR results of conventional binary motion estimation and proposed algorithm
다음의 표 5 에서는 기존의 알고리듬 기반의 움직임 예측에 16 × 16크기의 블록을 사용한 결과와 제안하는 알고리듬의 결과를 비교 하였다.
위의 실혐 결과들을 통해서 본 논문에서 제안하는 알고리듬이 8 × 8 크기의 움직임 예측 블록을 사용한 기존의 제한된 1비트 변환알고리듬의움직임 예측결과보다 약0.595dB 향상된 결과를 갖는 것을 확인할 수 있다. 이는 본 논문에서 제안하는 움직임 예측의 블록 정합 비교에서 블록의 크기를 늘려 비교 기준이 되는 픽셀의 개수를 증가시키는 방법이 움직임 예측의 정확도를 향상시키는 것을 확인해 준다. 또한 블록의 크기를 더욱 키우는 것이 반드시 움직임 예측의 정확도를 향상 시키지 않는 것을 확인 할 수 있다.
Ⅴ. 결 론
본 논문에서는 제한된 1비트 변환 알고리듬을 기반으로 영상의 정확한 움직임 예측, 보상을 위해 8 × 8크기의 보상 블록을 사용하고 정확한 움직임 예측을 위해 크기를 키운 정합 블록을 사용하는 방법을 제안하였다. 실험의 결과에서 본 논문에서 제안하는 알고리듬이 8 × 8 크기의 움직임 예측 블록을 사용하는 기존의 제한된 1비트 변환 알고리듬 보다 PSNR(dB) 측면에서 약 0.595dB 정확도를 향상시키는 것을 확인할 수 있었다.
BIO
김 형 도
- 2013년 2월 : 한양대학교 전자통신컴퓨터공학과 졸업
- 2015년 2월 : 한양대학교 일반대학원 전자통신컴퓨터공학 석사
- ORCID : http://orcid.org/0000-0003-4117-3082
- 주관심분야 : 비디오 압축, 영상처리
정 제 창
- 1980년 2월 : 서울대학교 전자공학과 졸업
- 1982년 2월 : KAIST 전기전자공학과 석사
- 1990년 : 미국 미시간대학 전기공학과 공학박사
- 1980년 ~ 1986년 : KBS 기술연구소 연구원 (디지털 및 뉴미디어 연구)
- 1990년 ~ 1991년 : 미국 미시간대학 전기공학과 연구교수 (영상 및 신호처리 연구)
- 1991년 ~ 1995년 : 삼성전자 멀티미디어 연구소 (MPEG, HDTV, 멀티미디어 연구)
- 1995년 ~ 현재 : 한양대학교 전자통신컴퓨터공학과 교수 (영상통신 및 신호처리 연구실)
- 1998년 11월 : 과학기술자상 수상
- 1990년 12월 : 정보통신부장관상 수상
- 2007년 : IEEE Chester Sall Award 수상
- 2008년 : ETRI Journal Paper Award 수상
- 2011년 5월 : 제46회 발명의 날 녹조근정훈장 수훈
- ORCID : http://orcid.org/0000-0002-3759-3116
- 주관심분야 : 영상처리, 영상압축, 3DTV
References
Natarajan B. , Bhaskaran V. , Konstantinides K. 1997 “Low-complexity block-based motion estimation via one-bit transforms,” IEEE Trans. Circuits Syst. Video Technol. 7 (4) 702 - 706    DOI : 10.1109/76.611181
Ertürk A. , Ertürk S. 2005 “Two-bit transform for binary block motion estimation,” IEEE Trans. Circuits Syst. Video Technol. 15 (7) 938 - 946    DOI : 10.1109/TCSVT.2005.848340
Urhan O. 2007 “Constrained one-bit transform-based motion estimation using predictive hexagonal pattern,” J. Electron. Imaging 16 (3) 033019 -    DOI : 10.1117/1.2769321
Çelebi A. , Akbulut O. , Urhan O. , Ertürk S. 2009 “Truncated Gray-Coded Bit-Plane Matching Based Motion Estimation and its Hardware Architecture,” IEEE Trans. Circuits Syst. Video Technol. 55 (3) 1530 - 1536
Celebi A. , Lee H.-J. , Erturk S. 2010 “Bit plane matching based variable block size motion estimation method and its hardware architecture,” Consum. Electron. IEEE Trans. 56 (3) 1625 - 1633    DOI : 10.1109/TCE.2010.5606306
Ertürk S. 2011 “Exploiting the full potential of Two-Bit Transform based motion estimation,” IEEE Int. Conf. Consum. Electron. (7) 643 - 644
Choi C. , Jeong J. “Low complexity truncated Gray-coded bit plane matching based multiple candidate motion estimation,” 2011 3rd Eur. Work. Vis. Inf. Process. 2011 73 - 76
Choi C. , Jeong J. “Constrained two-bit transform for low complexity motion estimation,” IEEE Int. Conf. Consum. Electron. Jan. 2013 350 - 351