다시점 비디오 부호화를 위한 2단계 움직임 추정 기법

Ⅰ. 서 론

정보 통신 기술의 발달로 다양한 비디오 콘텐츠들에 대한 수요가 증가하고 있고 이러한 콘텐츠들을 다양한 사용자들의 요구에 맞게 제공하고 있다. 그리고 다시점 비디오는 다양한 사용자들의 요구를 충족시킬 수 있는 3차원 영상으로 주목을 받고 있다[1]-[4]. 더불어 동영상의 고속 전송에 대한 사용자의 요구가 증가함에 따라 이에 따른 가장 큰 문제점은 동영상 데이터 크기이다.

방대한 다시점 비디오의 데이터를 압축하기 위하여 움직임 추정을 활용하는데, 일반적으로 비디오 압축과 관련 있는 국제 표준안들에서는 움직임 추정을 사용하여 비디오 데이터를 압축한다.

비디오 인코더에서 가장 많은 계산량을 차지하는 움직임 추정 부분은 비디오 영상들이 지니고 있는 특성, 즉 영상 프레임들 사이에 존재하는 중복된 데이터와 각각의 영상 프레임 내에 존재하는 중복된 데이터들을 제거하기 위하여 움직임 추정 기법을 사용한다. 특히, 각 영상 프레임과 여러 영상 프레임 사이에 존재하는 중복된 데이터들은 참조되는 프레임의 데이터를 이용하여 움직임 추정과 보상을 수행하여 각각의 블록의 움직임 벡터를 추정한다. 그리고 추정된 움직임 벡터를 이용하여 보상된 영상과 원본 영상과의 차이를 부호화하여 동영상을 압축한다.

일반적으로 움직임 벡터를 추정하기 위하여 블록 정합 기법을 사용한다[5][6]. 가장 단순한 블록 정합 기법인 FS은 참조 블록의 탐색 영역내의 모든 탐색 점들을 조사하여 블록 정합 오차를 최소인 점을 현재 블록의 움직임 벡터로 결정함으로서 최적의 움직임 벡터를 추정할 수 있지만 많은 계산량을 요구하기 때문에 실시간 비디오 응용분야 적용되는데 어려움이 있다.

FS의 계산 복잡도를 해결하기 위하여 고속 블록 정합 기법들이 개발되고 있다. 모든 블록 정합 기법들은 지역적 최소값(Local Minimum Problem)을 가지고 있는데, 지역적 최소값은 블록 정합 오차가 최소인 점에서 멀어질수록 블록 정합 오차가 커진다는 가정 하에 개발되었기 때문이다.

대표적인 고속 추정 기법으로는 넓은 탐색 간격의 초기 패턴으로 시작하여 점점 단계를 좁히면서 세밀하게 탐색하는 3단계 탐색 기법[7], 탐색 영역의 중심에 실제 움직임 벡터들이 집중되어 있다는 사실을 이용하여 네 번의 탐색 단계를 모두 실행하지 않고 탐색 단계 중간에 마지막 탐색 단계를 실행하여 움직임 벡터를 결정하는 4단계 탐색 기법 [8], 움직임 벡터 분포가 다이아몬드 모양이라는 사실과 움직임 벡터가 탐색 영역의 원점에 치우쳐 존재한다는 사실을 이용한 기법인 다이아몬드 기법[9], 탐색 점들 사이의 거리를 일정하게 구성한 육각형 탐색 기법[10], 움직임 벡터들의 공간적 상관성을 활용한 움직임 벡터 필드 적응적 탐색 기법[11] 그리고 H.264에서 적용된 비대칭 다중 육각형 탐색 기법 [12] 등이 있다. [7-12]의 기법들은 단일 시점영상에서 사용되는데 다시점 비디오 압축 시, 계층적 탐색 기법에서 사용하는 여러 탐색 패턴 중 일부로 사용될 수 있다.

다시점 비디오 부호화 시 요구되는 계산 복잡도는 비디오 촬용인 사용된 카메라의 수 , 영상 프레임 수, 영상 크기에 비례하여 기하급수적으로 증가한다. 이러한 계산 복잡도를 줄이기 위해 제안된 고속 움직임 추정 기법으로는 JMVC (joint multi-view video coding)의 TZ기법 [13], 육각형 모양의 탐색 패턴을 이용한 TZH[14], 중심 지향적 움직임 추정 기법(CBMS; center biased motion estimation)[15] 등이 있다.

본 논문에서 다시점 비디오 압축 시 사용되는 움직임 추정 계산 복잡도를 줄이기 위하여 2단계 움직임 추정 기법을 개발하였다. 제안된 2단계 움직임 추정 기법은 현재 블록의 움직임 벡터를 추정하기 전에 이전 화면의 대응 블록을 이용한 예측 , 메디안 예측, 이웃한 참조 화면을 이용한 예측, 상위 모드를 이용한 예측을 이용하여 현재 블록의 초기 탐색 시작점을 결정한다는 사실과 정확한 초기 탐색 시작점을 사용한 경우 탐색 영역 전역에 탐색 점들을 배치하여 조사할 필요가 없다는 사실들을 이용한 움직임 추정 방법으로 점점 범위를 좁혀 가면서 2 단계 만에 현재 블록의 움직임 벡터를 추정한다.

본 논문은 Ⅱ장에서 다시점 비디오 부호화를 위한 고속 움직임 추정 기법들을 기술한다. Ⅲ장에서 제안한 움직임 추정 기법을 설명하고 Ⅳ장에서 제안 기법의 성능을 평가하기 위하여 실험 결과를 비교한다. Ⅴ에서 결론을 기술한다.

Ⅱ. 본 론

다시점 비디오는 영상 크기가 단일 시점 영상들 보다 크고, 여러 대의 카메라를 이용하여 여러 시점에서 동시에 촬영된 동영상이다. 그리고 다시점 비디오 압축 시 발생하는 계산량은 이용된 카메라의 수, 영상 프레임 수 그리고 영상 크기에 비례하여 기하급수적으로 많아진다. 이러한 문제점을 해결하기 위하여 개발된 고속 움직임 추정 기법으로는 TZ기법, TZH 기법, CBMS기법 등이 있다.

2-1 TZ 기법

다시점 비디오 부호화의 성능을 향상시키기 위해 JMVC에서 개발한 움직임 추정기법이 TZ기법이다. TZ 기법은 계층적 탐색 기법으로 초기 그리드 탐색, 래스터 탐색, 정교한 탐색으로 이루어져 있다. 각각의 탐색들은 많은 계산량을 요구하고 있다.

TZ의 초기 그리드 탐색은 탐색 영역 [96,-96]에 [그림 1](a)의 초기 그리드 탐색 패턴을 이용하여 stride length i ( i=1, 2, 4, 8, 16, 32, 64) 영역에 탐색 점들을 배치하여 최소 비용 함수를 가진 점을 조사한다. [그림 1](a)는 stride length 1, 2, 4, 8영역에 탐색 점들을 배치한 것이다. 초기 그리드 탐색 을 수행한 후 현재 블록의 움직임이 크다고 예상되면 [그림 1](b)의 래스터 탐색 패턴을 이용하여 최소 블록 정합 오차를 가진 점을 결정한다. 그리고 마지막으로 초기 그리드 탐색 패턴을 사용하여 정교한 탐색을 수행하여 움직임 벡터를 추정한다.

Fig. 1.

Search patterns of TZ method

2-2 TZH 기법

TZH 기법은 TZ 기법의 변형으로 TZH는 초기 그리드 탐색 패턴으로 [그림 2]를 사용한 기법이다. TZH 기법은 [그림 1](a) 다이아몬드 그리드 탐색 패턴 대신 육각형 모양을 이용한 그리드 탐색 패턴을 사용한다.

Fig. 2.

Search patterns of TZH method

TZH 기법과 TZ 기법은 전체 탐색 영역에 일정한 간격으로 탐색 점들을 배치하여 움직임 벡터를 추정하므로 현재 블록이 움직임이 작거나 없는 블록이면 초기 그리드 탐색에서 불필요한 움직임 추정을 수행한다. 그리고 초기 그리드 탐색 후, TZH 기법과 TZ 기법은 모두 [그림 1](b)의 래스터 탐색 패턴을 사용하여 전체 탐색 영역에 가로 세로 탐색 점들을 배치하여 최소 비용 함수를 가진 점을 탐색한다. TZH 기법과 TZ 기법 모두 초기 그리드 탐색 패턴과 래스터 탐색 패턴에서 전체 탐색 영역에 일정한 간격으로 탐색 점들을 배치하여 움직임 벡터를 추정함으로써 불필요한 계산량을 사용한다.

2-3 중심 지향적 움직임 추정 기법 (CBMS)

중심 지향적 움직임 추정 기법은 TZH 기법과 TZ 기법의 초기 그리드 탐색에서 전체 탐색 영역에 일정한 간격으로 탐색 점들을 배치하고 탐색 점들을 검사하여 불필요한 계산량을 발생시키는 문제점을 개선하기 위한 기법이다. 중심 지향적 움직임 추정 기법은 영상 블록 움직임이 대각선 방향 보다는 수직방향 또는 수평방향으로 움직임이 많다는 사실과 탐색 원점의 중심에 움직임 벡터가 많이 분포한다는 사실을 이용한 기법으로 [그림 3] 탐색 패턴들을 이용하여 초기 움직임 추정을 수행한다. 그러나 중심 지향적 움직임 추정 기법 또한 현재 블록의 움직임이 크다고 예상되면 [그림 1](b)의 래스터 탐색 패턴을 이용함으로 불필요한 계산량을 요구한다.

Fig. 3.

Search patterns of TZH method

Ⅲ. 제안 기법

TZ 기법, TZH 기법은 초기 그리드 탐색 시, 전체 탐색 영역에 다이아몬드 모양 또는 육각형 모양의 그리드 탐색 패턴을 이용하여 일정한 간격으로 탐색 점들을 배치하고 조사하여 다음 단계를 위한 최소 비용 함수를 가진 점을 찾은 후, 래스터 탐색을 수행한다. 래스터 탐색도 전체 탐색 영역에 탐색 점들을 일정한 간격으로 수직 방향과 수평 방향으로 배치하고 조사하여 최적의 탐색 점들 찾는다. 이것은 초기 그리드 탐색에서 전체 탐색 영역에 탐색 점들을 규칙적으로 배치하여 조사할 필요가 없다는 것을 의미한다. 그리고 TZ 기법, TZH 기법 그리고 CBMS기법들은 현재 블록이 움직임이 크다고 예상되면 래스터 탐색을 수행하는데 여러 실험 결과 래스터 탐색은 영상 화질 향상에 거의 영향을 주지 않으면서 많은 계산량을 요구한다. 즉, 많은 움직임 추정 시간을 필요로 하지만 영상 화질 면에 있어서 거의 효과가 없었다.

제안 기법은 계산량을 줄이기 위하여 현재 블록의 움직임이 작은 블록인 경우, 현재 블록의 움직임 벡터는 약 98% 정도 참조 프레임의 움직임 벡터 또는 현재 블록의 이웃하는 블록의 움직임 벡터와 같고 움직임이 빠른 블록에서는 약 50%가 같다[16]. 이러한 사실들을 이용하여 초기 탐색 시작점을 중심으로 탐색 점들을 배치하여 움직임 벡터를 추정한다.

현재 블록을 위한 움직임 벡터를 추정하기 전, 제안 기법은 현재 블록의 초기 탐색 시작점을 결정하기 위하여 움직임 벡터의 시공간적 상관성을 이용한 메디안 예측, 이웃한 참조 화면을 이용한 예측, 이전 화면의 대응 블록을 이용한 예측 한다. 결정된 초기 탐색 시작점을 탐색 원점으로 [그림 4](a)를 이용하여 탐색 점들을 배치한다. 제안 기법은 전체 탐색 영역 전역에 일정하고 규칙적으로 탐색 점들을 배치하여 조사하는 것은 많은 움직임 추정 시간을 필요로 하지만 영상 화질 향상에 거의 효과가 없기 때문에 기존의 기법들과 달리 전체 탐색 영역에 탐색 점들을 배치하지도 않고 래스터 탐색을 수행하지 않는다. 제안 기법은 현재 블록의 움직임 벡터를 추정하기 위하여 다음과 같은 알고리즘을 수행한다.

Fig. 4.

Search patterns of Proposed method

제안 기법에서는 [그림5] 블록들의 움직임 벡터들과 (0,0)을 후보 벡터로 이용하여 탐색 시작점을 결정한다. [그림5]에서 t-2 프레임의 MV0과 t-1 프레임의 MV1은 시간적 상관성을 가진 블록들의 움직임 벡터들이고 현재 프레임의 MV2, MV3 와 MV4는 공간적 상관성을 가진 블록들의 움직임 벡터들이다.

Fig. 5.

Candidate Vectors

만약 MV0=MV1=MV2=MV3=MV4 이면, 이들의 움직임 벡터를 탐색 시작점으로 결정한다. 시간적 상관성을 가진 블록들의 움직임 벡터 MV0 = MV1 또는 공간적 상관성을 가진 블록들의 움직임 벡터 MV2 = MV3= MV4 또는 MV2, MV3 와 MV4 중에서 2개가 일치하는 경우, MV2, MV3 와 MV4의 메디안 움직임 벡터 MVmedian를 구한 후, MV1, MVmedian 그리고 (0,0)에서 정합 오차 값을 구하여 최소 정합 오차를 가진 점을 탐색 시작점으로 결정한다. 그렇지 않으면 (0,0)을 탐색 시작점으로 결정한다.

[단계 1] 초기 탐색 시작점 예측 : 현재 블록과 공간적 또는 시간적 상관성을 지닌 블록들의 움직임 벡터들을 이용하여 메디안 예측, 이웃하는 참조 화면을 이용한 예측, 이전 화면의 대응 블록을 이용한 예측을 수행한다. 여러 예측을 통하여 탐색 시작점을 결정한다.

[단계 2] 단계1의 탐색 시작점을 중심으로 [그림 4](a)를 이용하여 탐색 시작점을 중심으로 8개의 탐색 점들을 배치하고 최소 비용 오차를 가진 점을 결정한다.

[단계 3] 단계 2의 최소 블록 정합 오차를 가진 점을 중심으로 stride length가 1인 영역에 [그림 4](b)와 같이 4개의 ▲탐색 점들을 배치하고 조사하여 최소 비용 함수를 가진 점을 현재 블록의 움직임 벡터로 결정한다.

Ⅳ. 실험 결과

제안 기법의 성능을 평가하기 위해 사용된 실험 영상으로 Uli, Exit, Ballroom, Race1 그리고 Flamenco2를 사용하였다. Exit, Ballroom, Race1 그리고 Flamenco2의 영상 크기는 640×480이고 Uli의 영상크기는 1024×76인 Uli이다. 1차원 배열의 영상인 Exit, Ballroom, Race1, Uli는 8개의 카메라를 사용하였고 2차원 배열 영상인 Flamenco2는 5개의 카메라를 이용하였다. 실험조건은 표 1에 나타내었다[17]-[20].

Table 1.

Experiment Conditions

Table 2.

Simulation Results – PSNR

제안 기법의 성능을 비교하기 위하여 영상 화질을 나타내는 PSNR(peak-signal-to-noise ratio)과 움직임 추정 시간을 이용하였다.

제안 기법, TZ 기법, TZH 기법 그리고 CBMS 기법의 영상화질을 표 3에 나타내었고 움직임 추정 시간을 표4에 나타내었다. 또한 실험 영상 Ballroom( QP:37, 프레임 수 :100)의 영상 화질과 움직임 추정시간에 대한 성능 비교는 각각 표5, 표6에 나타내었다 .

Table 3.

Simulation Results – total motion estimation time

Fig. 5.

Experiment Multi-view Videos

Table 5.

Ballroom(QP:37) – PSNR

Table 6.

Ballroom(QP:37) – motion estimation time

실험 영상 Exit, Flamenco에서 TZ 기법 보다 제안 기법은 움직임 추정 시간을 각각 약 50%, 62% 줄이면서 영상 화질은 거의 같다. Uli에서 제안 기법은 TZ 기법 보다 움직임 추정 시간을 약 70% 감소시키면서 영상 화질은 거의 같다. 움직임이 빠른 영상인 Ballroom에서 제안 기법은 TZ 기법 보다 움직임 추정 시간을 약 50% 감소시키면서 영상화질은 거의 같다. 움직임이 크고 불규칙한 Race1에서 제안 기법은 TZ 기법 보다 움직임 추정 시간을 약 80% 감소시키지만 영상 화질 면에서 약 0.2(dB) 저하를 보였다.

모든 실험 영상에서 TZH 기법 보다 제안 기법은 움직임 추정 시간을 약 50% 이상 감소시키면서 영상 화질 면에서 Race1을 제외한 실험 영상에서 TZH 기법과 같은 화질을 보인다. Race1에서 제안 기법은 TZH 기법 보다 영상 화질 면에서 약 0.2(dB) 저하를 보인다.

CBMS 기법 보다 제안 기법은 움직임 추정 시간을 약 7~16% 이상 감소시키면서 영상 화질은 거의 같다. 움직임이 빠르고 불규착한 Race1에서 제안 기법은 CBMS기법 보다 영상 화질 면에서 약 0.2(dB) 저하를 보인다.

TZ 기법, TZH 기법, CBMS기법 보다 제안 기법이 Race1에서 영상 화질이 약 0.2(dB) 저하를 보인 이유는 전제 탐색 영역에 탐색 점들을 배치하여 움직임 벡터를 추정하는 래스터 탐색 패턴을 사용하지 않았기 때문이다.

실험 영상 Ballroom( QP:37, 프레임 수 :100)일 때 FS와 제안 기법의 움직임 추정 시간을 비교한 경우, 제안 기법은 약 99% 움직임 추정 시간을 감소하였지만 거의 비슷한 화질을 보였다. Ballroom( QP:37, 프레임 수 :100)에서 제안 기법이 FS보다 약 99% 움직임 추정 시간을 감소시키는데 이를 시간으로 계산한 결과 944시간 30분 에 해당 된다. 만약 QP가 22, 27, 32이면 움직임 벡터 추정 시간을 각각 약 1000시간 이상 감소시킨다.

Ⅴ. 결 론

본 논문에서는 다시점 비디오의 부호화 성능을 향상시키기 위한 움직임 추정 기법을 제안하였다. 다시점 비디오 압축 시 요구되는 계산 복잡도를 감소시키기 위하여 2단계 움직임 추정 기법을 제안하였다.

제안 한 2단계 움직임 추정 기법은 현재 블록의 움직임 추정을 수행하기 전, 움직임 벡터들의 상관성을 이용한 메디안 예측, 상위 모드를 이용한 예측, 이전 화면의 대응 블록을 이용한 예측 , 이웃한 참조 화면을 이용한 예측을 수행하여 현재 블록의 초기 탐색 시작점을 결정한다. 그리고 불필요한 계산량을 요구하는 래스터 탐색은 수행하지 않는다.

본 논문에서 제안한 움직임 추정 기법의 성능을 FS 기법, TZ기법, TZI 기법 그리고 CBMS 기법들의 성능과 비교하였을 때, 움직임 추정 시간에 있어서 제안 기법은 FS 기법, TZ기법, TZI 기법 그리고 CBMS 기법보다 각각 약 99%, 50~80%, 50%, 약 7~16% 이상을 감소시키면서 거의 같은 화질을 유지하였다.

참고문헌

• A. Smolic, K. Mueller, P. Merkle, C. Fehn, P. kauff, P. Eisert, and T. Wiegand, "3D Video and Free Viewpoint Video - Technologies, Applications and MPEG Standards," Proc. of IEEE International Conference on Multimedia and Exposition, Jul. 2006. [https://doi.org/10.1109/ICME.2006.262683]
• ITU-T Rec. & ISO/IEC 14496-10 AVC, "Advanced Video Coding for Generic Audio Visual services," 2005.
• ISO/IEC JTC1/SC29/WG11 N10357, "Vision on 3D Video," Feb. 2009.
• A. Vetro, P. Pandic, H. Kimata, A. Smolic, and Y. Wang, "Joint Multi-view Video Model (JMVM) 8.0," Joint Video Team of ISO/IEC JTC21/SC29/WG11 and ITU-T SG16 Q.6, JVT-AA207, Switzerland, Apr. 2008.
• H. G. Muamann, P. Pirch and H. H. Grallert, “Advance in picture coding,” Proceedings of the IEEE, Vol. 73, No. 4, pp. 523-548, 1985 [https://doi.org/10.1109/PROC.1985.13183]
• J. L. Mitchell, W. B. Pennebaker, and C. E. Fogg, MPEG Video Compression Standard, pp. 283-312, Chapman & Hall, 1996 [https://doi.org/10.1007/0-306-46983-9_13]
• T. Koga, K. Iinuma, A. Hirano, and Y. Ishiguro, “Motion Compensated Interframe Coding for Video Conference," NTC81, pp.G5.3.1-5.3.5, 1981.
• L. M. Po and W. C. Ma, "A Novel Four Search Algorithm for Block Motion Estimation," IEEE Transactions on Circuit and Systems for Video Technology, Vol. 6, pp. 313-317, 1996. [https://doi.org/10.1109/76.499840]
• J.Y. Tham, S. Ranganath, and A.A. Kassim, "A Novel Unretricted Center-Biased Diamond Search Algorithm for Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 8, pp.369-377, 1998. [https://doi.org/10.1109/76.709403]
• C, Zhu, X. Lin, and L.P. Chau, “Hexagon based Search Pattern for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, pp. 349-355, 2002. [https://doi.org/10.1109/TCSVT.2002.1003474]
• P. I. Hosur, K. K. Ma, "Report on Performance of Fast Motion Estimation using Motion Vector Field Adaptive Search Technique," ISO/IEC/JCTI/SC29/WG11 M5453, 1999(12).
• Z. Chen, P. Zhou, and Y. He, " Fast Integer pel and Fractional pel Motion Estimation in for JVT," in JVT of ISO/ICE/ MPEG and ITU-T VCEG, 6th meeting, 2002.
• TANG Xiu-lil, OAT Sheng-kui, and CAT Can-hui, "An Analysis of TZSearch Algorithm in JMVC," pp. 516-519, 2010. [https://doi.org/10.1109/ICGCS.2010.5543008]
• N. Purnachand, Luis Nero Alves, and Antonio Navarro, "Improvements to TZ search motion estimation algorithm for multiview video coding," IWSSIP 2012, pp. 388-391, 2012.
• H. S. Yoon, M. Y. Kim, “Center Biased Motion Estimation Method for Multi-video view video coding,” Korean Institute of Information Scientists and Engineers Vol. 41, No. 11, pp. 679-704, 2013.
• H. S. Yoon, M. Y. Kim, “Motion Estimation Method Based on Correlations of Motion Vectors for Multi-view Coding .”Journal of korea Multimedia Society Vol. 21, No. 10, pp. 1131-1141, 2018.
• ISO/IEC JTC1/SC29/WG11, Requirements on Multi-view Video Coding Doc. N7282, 2005
• ISO/IEC JTC1/SC29/WG11, Call for Proposals on Multi-view Video Coding Doc. N7327, 2005
• J. Daase, U. Goelz, P. Kauff, K. Mueller, O. Sxhreer, and A. Smolic, Fraunhofer HHI Test Data Sets for MVC, ISO/IEC JTC1/SC29/WG11, Doc MPEG2005/M11894, 2005.
• A. Vetro, M. McGuire, W. Matusik, A. Behrens, J. Lee, and H. Pfister, Multi-view Video Test Sequences from MERL, ISO/IEC JTC1/SC29/WG11, Doc M12077, 2005.