_00_01_논문지 겉표지목차(앞).hwp

Journal of Digital Contents Society Vol. 9 No. 2 June. 2008(pp. 305-315) 탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 곽노윤 * 요 약 기제안된 적응형 계층 육각 탐색은 적응형 육각 탐색에 기반한 고속의 계층형 블록 정합 알고리즘의 일종이다. 적응형 계층 육각 탐색은 고속 움직임 탐색이 가능한 적응형 육각 탐색의 장점을 유지하면서 도 시공간 움직임 활동도가 높은 비디오 시퀀스에서 흔히 발생되는 국부 최소 문제를 적응적으로 경감 시킬 수 있는 것이 특징이다. 본 논문은 적응형 계층 육각 탐색의 예측 화질을 개선하기 위해 이 탐색 의 수평 편향 패턴과 수직 편향 패턴을 효과적으로 확장하는 방법을 제안함에 그 목적이 있다. 본 논문 에서는 서로 다른 움직임 특성을 갖는 복수의 동영상 시퀀스들에 대한 컴퓨터 시뮬레이션 결과를 토대 로 예측 화질과 연산 시간 측면에서 제안된 방법의 성능을 분석 평가하였다. 시뮬레이션 결과는 제안 된 방법이 작은 움직임 탐색과 큰 움직임 탐색에 모두 적합함을 보여주었다. 제안된 방법은 육각 탐색 패턴의 확장 과정에서 추가적인 연산량 증가를 초래했지만 이 연산량의 증가에 상응하는 예측 화질 개 선을 기할 수 있었다. Performance Improvement of Adaptive Hierarchical Hexagon Search by Extending the Search Patterns Noyoon Kwak* Abstract Pre-proposed AHHS(Adaptive Hierarchical Hexagon Search) is a kind of the fast hierarchical block matching algorithm based on the AHS(Adaptive Hexagon Search). It is characterized as keeping the merits of the AHS capable of fast estimating motion vectors and also adaptively reducing the local minima often occurred in the video sequences with higher spatio-temporal motion activity. The objec tive of this paper is to propose the method effectively extending the horizontal biased pattern and t he vertical biased pattern of the AHHS to improve its predictive image quality. In the paper, based on computer simulation results for multiple video sequences with different motion characteristics, the performance of the proposed method was analysed and assessed in terms of the predictive image q uality and the computational time. The simulation results indicated that the proposed method was b oth suitable for (quasi-) stationary and large motion searches. While the proposed method increased the computational load on the process extending the hexagon search patterns, it could improve the predictive image quality so as to cancel out the increase of the computational load. Keywords : Motion Estimation, BMA, AHS, AHHS, Hexagon Search, Extended AHHS 1. 서론 블록 정합 알고리즘(BMA : Block Matching Algorithm)은 MPEG-1/2/4, H.261, H.263, 그리 고 최근의 H.264/AVC 등으로 대표되는 국제 동 제일저자(First Author) : 곽노윤 접수일자:2008년03월20일, 심사완료:2008년04월07일 * 백석대학교 정보통신학부 nykwak@bu.ac.kr 영상 압축 표준들에서 프레임간 부호화를 위한 움직임 추정(motion estimation) 기술로 널리 채 택되어 있다[1]. 전역 탐색(Full Search) 기반 BMA의 높은 연산 부담은 소프트웨어 기반 응 용 분야에서 실시간 구현을 어렵게 만드는 문제 가 있다. 이에 따라 단계적으로 예상 변위를 줄 여서 정합 연산량을 감소시킴과 동시에 정확한 움직임 벡터를 탐색하려는 의도에서 출발한 고 속 BMA들이 다수 제안되어 있다. 이러한 고속 BMA들은 매우 다양한 군들로

306 디지털콘텐츠학회 논문지 제9권 제2호(2008. 6) 분류할 수 있다. 그 중에서 3단계 탐색(3SS : T hree-step Search)[2], 2-D 대수적 탐색(2-D Lo garithmic Search)[3], 공액축 탐색(Conjugate Di rection Search)[4], 1D 기울기 감소 탐색(1D Gr adient Descent Search)[5] 등은 매우 고전적인 유형에 속한다. 이들은 전역 탐색(FS)에 비해 연 산 시간을 큰 폭으로 단축했고 이후에 등장한 고속 알고리즘들의 토대가 되었으나 탐색된 움 직임 벡터의 신뢰성이 상대적으로 저급한 것이 흠이다. 이러한 문제점에 대한 하나의 대안으로, 서로 상이한 해상도를 갖는 다단계 계층들 간에 서 점진적으로 움직임을 탐색하는 계층 탐색(Hi erarchical Search)[6][7][8] 계열의 방식들이 많 이 제안되어 있다. 계층 탐색은 고속화 측면에서 적잖은 기여를 하였으나 상위 계층에서 국부 최 소(local minima)에 빠질 경우에 그 영향이 하위 계층에 전달되고 하위 계층에서는 이를 상쇄시 킬 수 없는 그 나름의 한계가 있다. 또 다른 접근법으로는 대부분의 움직임 벡터 들이 전체 탐색 영역의 중심 주위에 분포한다는 분석을 바탕으로 다양한 중심 기반 탐색 방식들 이 제안되어 있다. 여기에는 3단계 탐색(3SS)[2] 의 중심 주변의 탐색 성능을 개선한 N3SS(New Three-Step Search)[9], E3SS(Efficient Three-S tep Search)[10], 4SS(Four-Step Search)[11] 등 이 있으며, 그 외에도 다이아몬드 탐색(DS : Dia mond Search)[12][13], 육각 기반 탐색(HEXBS : Hexagon Based Search)[14] 등이 이 계열에 속 한다. 한편 최근에는 다이아몬드 패턴과 육각 탐 색 패턴을 결합하여 탐색 전략을 수정하거나 또 는 육각 탐색 패턴의 모양이나 크기 혹은 방향 등을 변형하여 육각 기반 탐색(HEXBS)[14]의 성능을 개선한 방법들이 다수 제안되고 있다. 대 표적인 것으로는 AHS(Adaptive Hexagon Searc h, 적응형 육각 탐색)[15][16], PHS(Predict Hexa gon Search)[17], CHS(Cross-Hexagon Search) [18], FHS(Flatted-Hexagon Search)[19], 3DPH S(3D Predict Hexagon Search)[20] 등이 있다. 육각 기반 탐색(HEXBS)[14]의 가장 큰 장점은 움직임이 작은 동영상 시퀸스에서 매우 고속으 로 수렴하는 특성을 갖고 있다는 것이다. 반면에 움직임이 큰 경우에는 국부 최소에 빠지는 확률 이 현저히 높은 결점을 갖고 있다. 물론, 육각 기반 탐색(HEXBS)의 변종들[15][16][17][18][19] [20]도 탐색 패턴의 종류를 다변화시키거나 탐색 전략을 부분적으로 수정한 것에 지나지 않기 때 문에 이러한 결점을 효과적으로 억제하지 못하 고 있다. 또한 그 종류는 많지만 각 방식들 상호 간에 괄목할만한 성능 차이가 나지 않는 한계가 있다. 이와 같은 범주에 포함되지만, 이들 중에 서도 AHS[15][16]는 여타의 육각 탐색들과 마찬 가지로 고속 수렴의 장점을 갖고 있고, 왜곡 평 가 척도의 기울기 감소 방향에 따라 육각 탐색 의 방향을 수직 혹은 수평으로 적응적으로 전환 하는 특성에 기인하여 평균적으로 양호한 성능 을 제공하는 것으로 평가받고 있다[16][20]. 그러 나 이 또한 움직임이 큰 경우에 국부 최소에 잘 빠지는 육각 탐색 계열의 단점을 회피하지 못하 고 있다. 이러한 단점을 보완하고자 본 논문의 연구자는 시공간 움직임 활동도(spatio-temporal motion activity)를 이용하여 AHS[15][16]에 계 층 탐색(hierarchical search) 개념을 도입한 적 응형 계층 육각 탐색(AHHS : Adaptive Hierarc hical Hexagon Search)[21]을 기 제안한 바 있 다. AHHS는 작은 움직임 탐색에서 제공하는 A HS의 양호한 예측 화질과 고속 수렴 특성을 그 대로 유지할 수 있다. 더욱이, 움직임이 큰 경우 에는 AHS에 비해 예측 화질과 탐색 시간 측면 모두에서 공히 개선된 성능을 제공하는 장점이 있다. 그러나 AHHS는 전역 탐색과 비교할 때, 움직임이 큰 경우엔 여전히 큰 화질 저하 폭이 존재하는 문제가 있다. 본 논문은 이러한 문제를 보완하기 위한 것으로, 큰 움직임 탐색 시에 AH HS의 수평 편향 패턴과 수직 편향 패턴을 효과 적으로 확장하는 방법을 제안하고자 한다. 이를 통해 고속 수렴 특성을 유지하면서도 큰 움직임 탐색 시, 예측 화질을 좀 더 개선하고자 한다. 2. 관련 연구 2.1. 적응형 육각 탐색(AHS) 2.1.1 기본 탐색 패턴 AHS[15][16]는 (그림 1)과 같은 한 개의 십자 형 초기 탐색 패턴과 두 종류의 육각 탐색 패턴 을 사용한다. 편의상 각 패턴을 구성하는 탐색점 들은 패턴 종류와 위치에 따라 내부점(inner point), 중심점(center point), 정점(vertex) 및 표

탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 307 면점(surface point)으로 구분한다. (그림 1)(a)의 십자형의 초기 탐색 패턴은 중 심점과 정점만으로 구성되는데, 0 위치는 중심 점이고 1, 2, 3, 4 위치는 정점들이다. 그리고 (그림 1)(b)와 (그림 1)(c)는 8개의 후 보 탐색점들로 구성된 두 종류의 육각 탐색 패 턴을 나타낸 것이다. 각 탐색점들은 수평 및 수 직 방향으로 편향된 패턴(biased pattern) 상에 분포된다. (그림 1)(b)는 수평축에 편향된 방향으 로 후보 영역을 탐색하는 수평 편향 패턴(HBP : Horizontal Biased Pattern)을 나타낸 것이고, (그림 1)(c)는 수직축에 편향된 수직 편향 패턴 (VBP : Vertical Biased Pattern)을 나타낸 것이 다. 공히, 정점은 2 와 5 위치이고 표면점은 3, 4, 6, 7 위치이며 내부점은 0 과 1 이 된다. 특 히, 0 은 중심점으로 정의한다. 가 3 번, 4 번, 6 번, 7 번 위치에서 발생한다면 다음 탐색 패턴은 현재의 HBP에서 VBP로 변경 된다. 한편, (그림 1)(a)의 초기 탐색 패턴을 적 용한 후, 그 다음 탐색 패턴으로 VBP가 선택된 경우, (그림 1)(c)의 VBP를 적용하여 패턴 내의 각 후보점들에 대해 SSD를 계산한 후, 앞서 설 명한 HBP와 유사한 방식으로, 각 최소 SSD의 위치에 적합한 HBP와 VBP를 계속적으로 적용 하여 최종 움직임 벡터를 구한다. (그림 2)는 최 소 SSD의 위치에 따라 HBP와 VBP를 적응적으 로 선택하여 탐색하는 과정을 예시한 것이다. 2.1.2 탐색 과정 및 전략 AHS의 왜곡 평가 척도는 최소 SSD(Sum of Square Difference)와 SAD(Sum of Absolute Di fference) 중 어느 하나를 택일해서 사용한다. 가 령, SSD가 왜곡 평가 척도로 사용될 경우, 최소 SSD를 갖는 위치가 이후 탐색 패턴의 중심점으 로 선택된다. AHS[15][16]의 탐색 과정을 (그림 1)을 참조하여 단계적으로 설명하면 다음과 같 다. 우선, 기 결정된 탐색 범위내의 중심 위치(0,0) 에 (그림 1)(a)의 초기 탐색 패턴을 적용하여 탐 색 패턴내의 각 후보점들에 대하여 SSD 값을 계산한다. 계산된 SSD들 중에서 최소값이 초기 탐색 패턴의 중심점 0 에 위치할 경우, 탐색을 중지하고 영벡터를 최종 움직임 벡터로 삼는다. 그러나 최소 SSD가 1 번 혹은 3 번의 위치에서 발생할 경우엔 다음 단계의 탐색 패턴으로 (그 림 1)(b)의 HBP가 선택된다. 그렇지 않고 2 번 혹은 4 번의 위치에서 발생할 경우 (그림 1)(c) 의 VBP가 선택된다. 이때, HBP가 다음 탐색 패 턴으로 선택된 경우, (그림 1)(b)의 HBP를 적용 하여 패턴 내의 각 후보점들에 대해 SSD를 계 산한다. 최소 SSD가 내부점 0 혹은 1 에 위치 하면, 탐색을 중지하고 해당 위치의 벡터를 최종 움직임 벡터로 삼는다. 그렇지 않고 2 번과 5 번 위치에서 발생한다면 연이어 HBP가 그 다음 단 계의 탐색 패턴으로 선택된다. 반면에 최소 SSD (a)초기탐색패턴 (b)수평편향패턴 (c)수직편향패턴 (그림 1) AHS의 기본 탐색 패턴 (a)hbp 계속 탐색 (b)hbp에서 VBP로 변경 (c)vbp 계속 탐색 (d)vbp에서 HBP로 변경 (그림 2) 최소 SSD의 위치에 따른 HBP와 VBP의 선택 및 탐색 2.2. 적응형 계층 육각 탐색(AHHS) 적응형 계층 육각 탐색(AHHS)[21]은 적응형 육각 탐색(AHS)[15][16]에 기반한 고속의 계층 형 블록 정합 알고리즘의 일종이다.

308 디지털콘텐츠학회 논문지 제9권 제2호(2008. 6) AHS[15][16]는 왜곡 평가 척도의 기울기 감소 방향에 따라 육각 탐색 패턴의 방향을 적응적으 로 전환함에 힘입어 고속 움직임 추정이 가능하 면서도 상대적으로 개선된 성능을 제공하고 있 다. 그러나 이 방식도 육각 탐색 계열이기 때문 에 움직임이 큰 동영상 시퀀스에서 연산 시간의 증가하고 국부 최소에 빠질 빈도가 높은 문제를 회피할 수가 없다. 이러한 문제를 개선하기 위 해, AHHS는 먼저 현 매크로블록에 시공간적으 로 인접한 매크로블록들의 움직임 벡터를 이용 하여 시공간 움직임 활동도(spatio-temporal motion activity)를 정의한다. 이렇게 정의한 시 공간 움직임 활동도가 높을 경우, 피라미드형의 다단계 계층 공간상에서 AHS의 탐색 패턴들을 적응적으로 적용하는 계층 육각 탐색(HHS : Hierarchical Hexagon Search)을 수행하고, 그렇 지 않을 경우엔 원영상에서 기존의 AHS를 수행 한다. AHHS는 고속 움직임 탐색이 가능한 적응형 육각 탐색의 장점을 유지하면서도 시공간 움직 임 활동도가 높은 비디오 시퀀스에서 흔히 발생 되는 국부 최소 문제를 적응적으로 경감시킬 수 있다. 또한 상위 계층에서 추정된 움직임 벡터로 전역 움직임 정보를 제공하고, 하위 계층으로 갈 수록 국부 움직임에 대한 상세한 움직임 벡터를 얻을 수 있다. 이와 같은 움직임 추정 기법상의 특성에 의해 기존의 AHS이 갖고 있던 단점을 어느 정도 보완할 수 있다. 또한 상하 계층들 간 에 탐색 범위를 부분적으로 중첩함으로 통해 계 층형의 단점을 일부 개선할 수도 있다. 그러나 전역 탐색과 비교할 때, 작은 움직임 탐색 시엔 거의 대등하거나 근접한 예측 화질을 제공하는 반면에 움직임이 큰 경우엔 여전히 큰 화질 저하 폭이 존재한다. 따라서 큰 움직임 탐 색 시, AHHS의 고속 수렴 특성을 그대로 유지 하면서도 예측 화질을 좀 더 개선할 필요가 있 다. 본 논문은 이러한 필요성에 부응하기 위한 일환으로 큰 움직임 탐색 시에 AHHS의 수평 편향 패턴과 수직 편향 패턴을 효과적으로 확장 하는 방법을 제안하고자 한다. 제안된 방법은 육 각 탐색 패턴의 확장 과정에서 추가적인 연산량 증가를 초래하지만 이 연산량의 증가에 상응하 는 예측 화질 개선을 기대할 수 있다. 3. 제안된 탐색 패턴 확장 방법 제안된 방법(Extended AHHS)은 움직임을 추 정할 현 매크로블록에 시공간적으로 인접한 블 록들의 움직임 벡터를 이용하여 움직임 활동도 를 정의한 후, 움직임 활동도가 기설정된 임계치 보다 낮은 경우 기존의 AHS를 수행한다. 그렇 지 않고 움직임 활동도가 기설정된 임계치 보다 높거나 같을 경우, 웨이블렛 변환의 다단계 저주 파 부영상들로 구성된 피라미드 계층 구조상에 서 수평 편향 패턴과 수직 편형 패턴을 확장하 는 EHHS(Extended Hierarchical Hexagon Sear ch)를 수행한다. (그림 3) 제안된 Extended AHHS 알고리즘의 순서도 확장된 계층 육각 탐색(EHHS)은 각 계층마다 최적 국부 정합점(즉, 최소 SSD를 갖는 위치)에 의해 형성된 기존의 탐색 패턴에 차순위 국부 정합점(즉, 차순위로 작은 SSD를 갖는 위치)을 중심으로 새롭게 형성한 탐색 패턴을 추가하여 탐색 패턴의 크기를 확장함으로써 움직임 벡터 추정의 고속화를 유지함과 동시에 국부 최소화 를 효과적으로 경감할 수 있다.

탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 309 3.1. 시공간 움직임 활동도 제안된 방법(Extended AHHS)에서는 AHHS 와 마찬가지로 이전 프레임과 현재 프레임에서 움직임을 추정할 현 매크로블록에 (그림 4)와 같 이 시공간적으로 인접한 매크로블록들의 움직임 벡터를 읽어와 시공간 움직임 활동도(spatio-tem poral activity)를 정의한다. 시공간 움직임 활동 도는 수평 성분 및 수직 성분 로 구성되는데, 각각 식(1)과 식(2)과 같이 구할 수 있다. (그림 4) 시공간 움직임 활동도의 정의에 사용되는 인접 매크로블록들 (1) (2) 시공간 움직임 활동도의 수평 성분 은 식(1)과 같이, 현 프레임의 수평 움직임 활동 도 와 이전 프레임의 수평 움직임 활 동도 을 이용하여 구한다. 여기서 는 현재 프레임에서 현 매크로블록의 좌상단, 상단 및 좌측에 인접한 매크로블록들의 움직임 벡터의 수평 성분 절대값들,, 을 합산한 것이다. 그리고 는 이전 프 레임에서 현 매크로블록의 대응 위치와 그 블록 의 하단 및 우측에 인접한 매크로블록들의 움직 임 벡터의 수평 성분 절대값들,, 을 합산한 것이 다. 식(2)의 시공간 움직임 활동도의 수직 성분 도 이와 유사한 방법으로 구할 수 있 다. 이때, 최초의 프레임이나 각 프레임의 가장 자리에 위치한 매크로블록들은 시공간적으로 인 접한 6개의 움직임 벡터들을 모두 사용할 수 없 는 상황이 발생하는데, 그 중 어느 것을 사용할 수 없을 경우, 해당 움직임 벡터를 영벡터로 간 주하고 시공간 움직임 활동도를 계산한다. 이후, 이 시공간 움직임 활동도의 수평 성분과 수직 성분 중 적어도 어느 하나가 기설정된 임 계치( )보다 크거나 같을 경우, 원영상과 두 장의 저주파 부영상들로 구성된 3단계 계층 공 간상에서 AHS의 탐색 패턴들을 적응적으로 이 용하여 계층 육각 탐색(HHS)을 수행하고, 그렇 지 않고 움직임 활동도가 임계치( )보다 작을 경우에는 원영상에서 기존의 AHS를 수행한다. 이때 기설정된 임계치( )는 실험적으로 결정한 값 1.5를 사용한다. 3.2. 다단계 계층 공간의 구성 계층 육각 탐색(HHS)을 수행하기 위해선 저 주파 부영상으로 구성된 다단계 계층 공간이 필 요하다. 이를 위해 연속된 두 프레임에 대해 각 각 두 번의 웨이블렛 변환을 수행한 후, 이 과정 에서 얻어지는 각 계층에서의 저주파 성분의 부 영상들을 저장한다. 이후, 원영상과 단계적으로 생성된 두 장의 저주파 부영상들로 구성된 피라 미드형의 3단계 계층 공간을 생성한다. (그림 5) 는 2회에 걸친 연속된 웨이블렛 변환을 통해 영 상을 분해하는 과정을 예시한 것이다. 최종 단계 의 저주파 부영상이 최상위 계층 영상이 되고 그 직전 단계의 저주파 부영상이 중간 계층 영

310 디지털콘텐츠학회 논문지 제9권 제2호(2008. 6) 상이 되며, 원영상이 최하위 계층 영상이 된다. (그림 5) 웨이블렛 변환에 의한 영상 분해 과정 AHHS에서는 웨이블렛 변환의 고속화를 기하 기 위해 필터 탭의 길이가 2인 하르 기저(Haar basis)[22]를 이용한다. 3단계 계층 공간은 저주 파 부영상만으로 구성되기 때문에 불필요한 연 산을 배제하기 위해 고주파 분해용 변환은 생략 하고 저주파 부영상에 대한 웨이블렛 변환만을 수행한다. 3.3. 확장된 계층 육각 탐색(EHHS) 제안된 방법에서는 앞서 설명한 바와 같이 시 공간 움직임 활동도가 높을 경우, 피라미드 계층 구조상에서 확장된 수평 편향 패턴과 수직 편형 패턴을 이용하여 확장된 계층 육각 탐색(EHHS : Extended Hierarchical Hexagon Search)을 수 행한다. 이하, EHHS의 탐색 패턴 확장 방법은 다음 절에서 설명하고, 본절에서는 계층들 간의 움직임 탐색 방법에 국한해 설명하기로 한다. EHHS를 수행할 시, 탐색 블록 크기는 최하위 계층 영상에서 16 16의 매크로블록을 사용한다. 이에 따라 중간 계층 영상에서는 8 8, 최상위 계 층 영상에서는 4 4로서, 계층이 증가함에 따라 그 크기가 옥타브(octave)적으로 감소된다. 움직 임 탐색 범위는 최상위 계층에서 ±4, 중간 계층 에서 ±4, 최하위 계층에서 ±2를 사용한다. 이 경 우 모든 계층의 탐색을 완료했을 시 최대 ±26의 탐색 범위를 가질 수 있는데, 중간 계층과 최하 위 계층에서 최종 움직임 벡터를 기준할 때 ±16 을 초과하는 움직임 벡터가 발생하는 위치는 탐 색 후보점에서 제외시킨다. 한편, 이와 같이 중간 계층 및 최하위 계층에 서 탐색 범위를 ±1보다 큰 값으로 설정하면 상 하 계층들 간에 탐색 범위가 부분적으로 중첩된 다. 이것은 상위 계층에서 발생한 국부 최소 문 제가 하위 계층으로 전달되더라도 하위 계층에 서 이를 부분적으로 상쇄하기 위한 것이다. 그러 나 탐색 범위의 과도한 중첩은 연산 시간 측면 에서 비효율성을 초래하기 때문에 적절한 상호 절충 관계(trade off)를 형성해야 한다. EHHS는 원영상과 두 장의 저주파 부영상들 로 구성된 3단계 계층 공간상에서 상하 계층들 간에 탐색 범위를 부분적으로 중첩시키면서 최 종 움직임 벡터를 구한다. 즉, 최상위 계층에서 최하위 계층 방향으로 진행하면서 점진적으로 움직임 벡터의 추정 정밀도를 재조정하여 최종 움직임 벡터를 결정한다. 이때, 상위 계층에서 탐색한 움직임 벡터의 2 배를 그 다음 하위 계층의 초기값으로 사용한다. 이러한 과정을 최하위 계층까지 반복하여 최종 적으로 부호화할 움직임 벡터를 탐색하게 된다. 앞서 설명했듯이 제안된 방법은 움직임 활동 도가 기설정된 임계치 보다 높거나 같을 경우에 만 국한해서 EHHS를 수행한다. 반면에 움직임 활동도가 낮은 경우에는 탐색 패턴을 확장하지 않고 기존의 AHS를 그대로 적용한다. 움직임 활동도가 낮으면 AHS의 예측 화질이 매우 양호 한 편이므로 굳이 탐색 패턴 확장을 통해 얻을 수 있는 예측 화질의 개선 효과가 탐색 시간의 증가에 비해 그리 크지 않기 때문이다. 3.4. EHHS의 탐색 패턴 확장 EHHS의 탐색 패턴 확장 방법은 차순위 국부 정합점 을 이용하다는 것이 핵심이다. 설명의 편 의상 임의의 탐색 패턴 내에서 최소 SSD를 갖 는 탐색점을 최적 국부 정합점, 차순위로 작은 SSD를 갖는 탐색점을 차순위 국부 정합점 이라 명하기로 한다. (그림 1)(c)의 초기 탐색 패턴을 미리 지정된 탐색 영역내의 중심점(0,0)에 위치하여 탐색 패 턴내의 각 후보점들에 대하여 SSD 값을 계산한 다. 계산된 SSD 값들 중에서 최적 국부 정합점이 초기 탐색 패턴의 중심점 에 위치할 경우, 현 매 크로블록에 대한 탐색 과정을 중지하고 이를 이 용해 최종 움직임 벡터를 결정한다. 그러나 최적 국부 정합점이 초기 탐색 패턴의 중심점에 위치 하지 않을 경우, 최적 국부 정합점과 차순위 국 부 정합점 각각 기준삼아 2개의 육각 탐색 패턴 을 형성한 후, 이 2개의 패턴을 중첩시켜 확장된 형태의 새로운 탐색 패턴을 만든다. 이를 좀 더 상술하면, 최적 국부 정합점 또는 차순위 국부

탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 311 정합점이 초기 탐색 패턴의 (그림 1)(a)의 1 혹 은 3 의 위치에서 발생할 경우 HBP를 탐색 패 턴으로 선택하고, 탐색점이 초기 탐색 패턴의 2 혹은 4 의 위치에서 발생할 경우 VBP를 선택한 다. 이를 통해 구한 이 두 육각 탐색 패턴의 합 집합을 확장된 탐색 패턴으로 삼고 각 탐색 후 보점들의 SSD를 계산하여 최적 국부 정합점의 위치를 탐색한다. 최적 국부 정합점이 HBP 또는 VBP의 내부점 에 포함될 경우, 탐색을 종료하고 이를 이용해 최종 움직임 벡터를 결정한다. 그렇지 않을 경우, 최적 국부 정합점과 차순위 국부 정합점을 이용하여 재차 새로운 확장 패턴 을 구한다. 부연컨대, 최소 SSD값을 갖는 위치 가 정점 들에서 발생할 경우, 육각 탐색 패턴의 방향은 그대로 유지된다. 반면에 최소 SSD 값을 갖는 위치가 표면점 들에서 발생할 경우, HBP에 서 VBP로 또는 VBP에서 HBP로 탐색 패턴의 방향이 변경된다. 이를 통해 구한 이 두 육각 탐 색 패턴의 합집합을 새로운 확장 탐색 패턴으로 삼고 각 탐색 후보점들의 SSD를 계산하는 과정 을, 최적 국부 정합점이 확장 탐색 패턴의 내부 점에서 발견될 때까지 반복적으로 수행한다. (그림 6)은 EHHS의 탐색 패턴 확장 과정을 예시한 것이다. 여기서, 회색의 도형은 최적 국 부 정합점의 위치에서 육각 탐색을 적용한 것이 고, 흑색의 도형은 차순위 국부 정합점의 위치에 서 적응형 육각 탐색을 적용한 것이다. (그림 6) 움직임 벡터 (-2,3)을 가정한 EHHS의 탐색 패턴 확장 과정 (그림 6)에서 이제 곧 탐색할 매크로블록의 실제 움직임 벡터가 (mx, my)=(-2,3)이라고 가 정할 때, 우선, 탐색 영역의 중심인 (0,0)에서부 터 탐색을 시작한다. 5개의 탐색 후보점들 각각 에 대하여 SSD를 계산한 후, 최소 SSD를 갖는 최적 국부 정합점을 찾고 이어서 차순위로 작은 최소 SSD 값을 갖는 차순위 국부 정합점을 찾 는다. 만약 최적 국부 정합점이 (0,0)에 위치한다 면, 탐색 과정은 종료되고 최종 움직임 벡터는 (0,0)이 된다. 반면에 (0,0)을 제외한 다른 4개의 후보점들 중에서 최적 국부 정합점과 차순위 국 부 정합점이 발생되면 계속된 후속 탐색이 필요 하다. 예컨대, 탐색 영역의 중앙에 위치한 (0,0)을 중 심으로 펼친 초기 탐색 패턴에서 최적 국부 정 합점의 좌표가 (1,0)이고 차순위 국부 정합점의 좌표가 (0,1)일 때, 이 두 점의 좌표값을 시작으 로 다시 확장된 육각 탐색을 전개하여 새로운 최적 국부 정합점과 차순위 국부 정합점을 구한 다. 최적 국부 정합점이 내부점 들에서 검출되면 그 좌표를 최종 움직임 벡터로 삼고, 그렇지 않 다면 이 최적 국부 정합점과 차순위 국부 정합 점을 이용하여 또 다시 확장된 육각 패턴을 전 개한다. 이때, 차순위 국부 정합점이 내부점 에 서 검출되면 이를 제외시키고 그 다음 순위의 SSD 값을 갖는 점을 차순위 국부 정합점의 대 용으로 삼는다. 이후, 최적 국부 정합점의 좌표와 차순위 국부 정합점의 좌표를 중심으로 다시 확장된 육각 패 턴을 전개하여 (그림 6)과 같이 최적 국부 정합 점 (-1,2)와 차순위 국부 정합점 (3,0)를 구한다. 이 두 정합점을 시작으로 다시 확장된 육각 탐 색을 펼친 결과 (-2,3)에서 최적 국부 정합점이 검출되고, (-3,2)에서 차순위 국부 정합점이 검출 된다. 앞에서와 마찬가지로 (-2,3)과 (-3,2)을 이 용하여 탐색 패턴을 확장한 후에 구한 최적 국 부 정합점이 (-2,3)일 경우를 가정할 때, 최적 국 부 정합점 (-2,3)은 내부점 이므로 이것을 최종 움직임 벡터로 삼는다. 결론적으로, (그림 6)은 탐색을 시작한 초기에 는 움직임이 오른쪽 방향으로 추정되었다가 육 각 탐색 패턴이 확장되면서 국부 최소 문제가 극복되어 왼쪽 하단에서 최종 움직임 벡터가 발 견된 사례를 예시한 것이다. 이 경우, 오른쪽 방

312 디지털콘텐츠학회 논문지 제9권 제2호(2008. 6) 향은 국부 최소점이 존재할 가능성이 높은 위치 로서, 차순위 국부 정합점에 기반한 탐색 패턴의 확장을 통해 국부 최소를 극복하고 (-2,3)에 있 는 실제 움직임 벡터를 탐색한 것이다. 다시 말 해서 (그림 6)은 AHS나 AHHS을 적용할 경우 에 국부 최소에 빠질 가능성이 높은 반면, 제안 된 방법을 적용할 경우에 정확한 움직임 벡터를 찾을 수 있는 예시의 일례이다. 4. 실험 결과 및 고찰 본 연구에서는 제안된 방법(Extended AHHS) 의 타당성을 평가하기 위해, 서로 다른 동적 특 성을 갖는 복수의 동영상 시퀀스들을 대상으로 I ntel Core 2 Duo 2.16GHz(2GB DDR2 667 SDR AM)에서 Microsoft Visual C/C++ 6.0을 이용하 여 컴퓨터 시뮬레이션을 수행하였다. 시험용 동 영상 시퀀스들은 256 계조의 휘도 영상들로서, 각기 다른 움직임 특성을 갖는 <표 1>과 같은 전형적인 시퀀스들로 구성되어 있다. <표 1> 시험용 동영상 시퀀스의 목록과 특징 속 성 시퀀스 Salesman (#0 #40) FlowerGarden (#40 #80) TableTennis (#100 #140) Football (#0 #30) Susie (#40 #95) 크 기 360 288 작은 움직임 발생 352 224 352 224 720 480 720 480 움직임의 특징 동일한 방향으로 지속적인 카메라 패닝 발생 각 구간별로 큰 움직임과 작은 움직임 이 혼재 다수의 객체가 등장 상대적으로 움직임이 크고 불규칙 크기가 큰 단일 객체가 등장 일정한 방향으로 큰 움직임 발생 원영상의 해상도를 기준으로 할 때, 기존의 방 법과 제안된 방법의 탐색 블록 크기는 16 16이 고, 탐색 범위는 ±16이며 왜곡 평가 척도는 SSD(Sum of Square Difference)를 사용하였다. <표 2>는 원영상과 예측 영상 간에 있어서 각 방법의 평균 PSNR(Peak Signal to Noise Ratio) 을 나타낸 것이다. <표 3>은 한 프레임을 처리 할 시에 소요되는 각 방법의 평균 연산 시간을 비교한 것이다. (그림 7)은 5개의 동영상 시퀀스에 대한 각 방법의 프레임별 PSNR을 비교한 것이다. 상대적으로 움직임이 작은 Salesman 시퀀스 와 FlowerGarden 시퀀스의 경우, 제안된 방법 ( Extended AHHS )은 물론이거니와 기존의 AHS[15][16]와 AHHS[21]도 모두 전역 탐색 (Full Search)에 근접하는 매우 양호한 결과를 제공하면서도 매우 고속으로 수렴하는 특성을 보이고 있다. 또한, (그림 7)(a)에서 볼 수 있듯 이 Salesman 시퀀스에서는 2-D 대수적 탐색 (Logarithmic Search)[3] 조차도 전반적으로 양 호한 결과를 제공하고 있다. 반면에 움직임이 상대적으로 큰 Football 및 Susie 시퀀스의 경우, 제안된 방법이나 기존의 AHS 및 AHHS는 공히 국부 최소에 빠지는 빈 도가 높은 편임을 알 수 있다. 그렇지만 제안된 방법은 AHS나 AHHS에 비해 예측 화질(PSNR) 측면에서 개선된 성능을 제공하고 있다. 특히 AHS와 비교할 때, 제안된 방법은 비슷한 연산 시간을 소요하면서도 Football 및 Susie 시퀀스 에서 각각 약 1.52[dB] 및 2.37[dB] 정도의 화질 개선 효과가 있다. <표 2> 각 방법의 평균 PSNR 비교 [db] Algorithms Sequences Salesman (#0 #40) FlowerGarden (#40 #80) TableTennis (#100 #140) Football (#0 #30) Susie (#40 #95) Algorithms Sequences Salesman (#0 #40) FlowerGarden (#40 #80) TableTennis (#100 #140) Football (#0 #30) Susie (#40 #95) Full Search Logarithmic Search[3] AHS AHHS [15,16] [21] Extended AHHS 35.24 34.98 35.21 35.20 35.20 24.58 21.02 24.38 24.36 24.39 31.11 29.72 30.20 30.39 30.45 24.20 23.07 21.93 23.21 23.44 35.66 34.13 32.43 34.50 34.80 <표 3> 각 방법의 평균 연산시간 비교 [msec] Full Search Logarithmic Search[3] AHS [15,16] AHHS [21] Extended AHHS 1094 37 4 7 8 819 27 6 9 10 819 27 3 4 5 4108 138 58 42 56 4108 138 52 43 53 실시간 구현 측면에서 볼 때, 움직임이 작은

탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 313 시퀀스의 경우, 제안된 방법이나 기존의 AHS 및 AHHS는 기본적으로 고속 수렴 특성을 갖고 있기 때문에 다소의 절대 시간의 증가는 그 부 담이 미미하다고 볼 수 있다. 하지만 움직임이 클 경우, AHS와 같은 중심 기반 탐색들은 연산 시간이 비교적 큰 폭으로 증가함에도 불구하고 국부 최소 문제에 적절하 게 대응하지 못하고 있다. 이것을 <표 3>과 (그 림 7)의 Football 시퀀스 및 Susie 시퀀스에서 극명하게 확인할 수 있다. 제안된 방법은 AHS 와 같은 중심 기반 탐색에 준하는 고속 수렴 특 성을 제공할 뿐만 아니라 특히 움직임이 큰 시 퀀스에서는 AHS와 비슷한 탐색 시간 내에 비교 적 큰 폭의 개선된 예측 화질을 제공함을 확인 할 수 있다. 한편, AHHS와 그 성능을 비교할 때, 제안된 방법은 움직임이 큰 Football 및 Susie 시퀀스에 서 각각 약 1.33배 및 1.23배 정도의 연산 시간 을 소요하면서 각각 0.23[dB] 및 0.30[dB] 정도 의 화질 개선 효과가 있다. 통상적으로 볼 때, 이것은 연산량의 증가에 상응하는 유의미한 수 준의 화질 개선 폭이라고 할 수 있으나 만족스 런 결과라고 보기 어렵다. 따라서 AHHS 계열의 접근법에서 단순히 탐 색 패턴의 확장 방법만으로는 움직임이 큰 시퀀 스의 국부 최소 문제를 근원적으로 해결할 수 없음을 알 수 있다. (b)flowergarden(#40 #80) (c)tabletennis(#100 #140) (d)football(#0 #30) (a)salesman(#0 #40)

314 디지털콘텐츠학회 논문지 제9권 제2호(2008. 6) (e)susie(#40 #95) (그림 7) 동영상 시퀀스들에 대한 각 방법의 프레임별 PSNR 비교 5. 결론 예비 연구[21]를 통해 AHHS가 기존의 육각 탐색 방법들의 단점을 극복하는 유의미한 접근 법이 될 수 있음을 확인한 바 있었다. 제안된 방 법(Extended AHHS)은 AHHS의 화질 예측 성 능을 좀 더 개선하기 위한 것이다. 부언컨대, 제 안된 방법은 AHHS의 최적 국부 정합점에 의해 형성된 기존의 탐색 패턴에 차순위 국부 정합점 을 중심으로 새롭게 형성한 탐색점들을 추가하 여 탐색 패턴을 확장하는 것이 특징이다. 이를 통해 움직임 벡터 추정의 고속화를 도모함과 동 시에 국부 최소화를 부분적으로 경감시킬 수 있 었다. 서로 다른 움직임 특성을 갖는 복수의 동 영상 시퀀스들을 대상으로 컴퓨터 시뮬레이션을 수행하여 예측 화질과 연산 시간 측면에서 제안 된 방법의 성능을 분석 평가하였다. 시뮬레이션 결과에 따르면, 제안된 방법은 제 안된 방법은 시퀀스의 움직임 유형에 상관없이 기존의 AHHS에 비해 평균적으로 약 1.11 1.33 배 정도의 연산 부담이 발생했다. 그렇지만 이 연산량의 증가에 상응하는 예측 화질 개선을 기 대할 수 있었다. 제안된 방법은 AHS에 준하는 고속 수렴 특성 을 제공할 뿐만 아니라 특히 움직임이 큰 시퀀 스에서는 AHS와 비슷한 탐색 시간 내에 비교적 큰 폭으로 개선된 예측 화질을 제공함을 알 수 있었다. 한편, AHHS와 그 성능을 비교할 때, 제안된 방법은 움직임이 큰 동영상 시퀀스에서 연산량 의 증가에 상응하는 유의미한 화질 개선 효과를 기대할 수 있었다. 그러나 제안된 알고리즘은 AHHS에 기반한 블록 정합 알고리즘의 일종이기에 움직임 추정 을 위한 연산 시간이 입력 영상에 의존적이고, 각 계층의 저주파 부영상으로 구성된 다단계 계 층 공간을 저장하기 위한 기억 공간을 추가로 필요한 단점이 있다. 제안된 방법은 상위 계층에 서 추정된 움직임 벡터로 전역 움직임 정보를 제공하고, 하위 계층으로 갈수록 국부 움직임에 대한 상세한 움직임 벡터를 얻을 수 있다. 이와 같은 움직임 추정 기법상의 특성에 의해 기존의 AHS이 갖고 있던 단점을 어느 정도 보완할 수 있었다. 또한 상하 계층들 간에 탐색 범위를 부 분적으로 중첩함으로 통해 계층형의 단점을 일 부 개선할 수도 있었다. 그러나 제안된 방법은 하위 계층에서는 국부 최소 문제를 충분하게 상 쇄시킬 수 없는 계층형의 단점이 여전히 남아 있을 뿐만 아니라 국부 최소 인근에서 고착되는 육각 탐색 계열의 한계를 여전히 갖고 있다. 한편 제안된 방법의 접근법은 기존의 중심 기 반 탐색 방법들에 용이하게 적용할 수 있는 확 장성을 갖고 있다. 그러나 단순히 탐색 패턴의 확장 방법만으로는 움직임이 큰 시퀀스의 국부 최소 문제를 근원적으로 해결할 수 없음을 확인 할 수 있었다. 이러한 사실은 향후 진행될 후속 연구의 접근 방식을 선정함에 좋은 참고 사항이 될 수 있을 것으로 판단된다. 참 고 문 헌 [1] Fernando Pereira and Touradj Ebrahimi, The Mpeg- 4 Book, Prentice Hall, 2002. [2] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishig uro, "Motion-compensated Interframe Coding for Vi deo Conferencing," in Proc. NTC81, New Orleans, LA, pp. C9.6.1-9.6.5, Nov. 1981. [3] J. R. Jain and A. K. Jain, Displacement Measuremen t and Its Application in Interframe Image Coding, IEEE Trans. Commun., vol. COM-29, pp. 1799-180 8, Dec. 1981. [4] R. Srinivasan and K. R. Rao, Predictive Coding Base d on Efficient Motion Estimation, in Proc. ICC 1984,

탐색 패턴 확장에 의한 적응형 계층 육각 탐색의 성능 개선 315 pp. 516-520, May 1984. [5] Lurng-Kuo Liu and E. Feig, A Block-based Gradien t Descent Dearch Algorithm for Block Motion Estim ation in Video Coding, IEEE Trans. on Circuits sys t. Video Technol., vol. 6, no. 4, pp. 419-422, Aug. 1996. [6] S. Panchanathan, E. Chan and X. Wang, Fast Multir esolution Motion Estimation Scheme for a Wavelet Transform Video Coder, SPIE, vol. 2308, pp. 674-6 81, 1994. [7] 김성만, 이규원, 정학진, 박규태, 웨이브렛 변환 영역에 서의 2단계 가변 블록 다해상도 움직임 추정, 한국통 신학회논문지, vol. 22, no. 7, pp. 1487-1504, 1997. 7. [8] 곽노윤, 황병원, 카메라 패닝 보상 기반 계층적 블록 정합 알고리즘, 정보처리학회논문지, 제6권, 제8호, pp. 2271-2280, 1999. 8. [9] R. Li, B. Zeng, and M. L. Liou, A New Three-step Search Algorithm for Block Motion Estimation, IE EE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438-442, Aug. 1994. [10] X. Jing and L.-P. Chau, An Efficient Three-step Search Algorithm for Block Motion Estimation, IE EE Trans. Multimedia, vol. 6, no. 3, Jun. 2004. [11] L. M. Po and W. C. Ma, A Novel Four-step Search Algorithm for Fast Block Motion Estimation, IEEE Trans. Circuit Syst. Video Technol., vol. 6, pp. 313-317, Jun. 1996. [12] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, A Novel Unrestricted Center-biased Di amond Search Algorithm for Block Motion Estimati on, IEEE Trans. on Circuits Syst. Video Technol., vol. 8, pp. 369-377, Aug. 1998. [13] S. Zhu and K.-K Ma, A New Diamond Search Alg orithm for Fast Block-matching Motion Estimatio n, IEEE Trans. Image Processing, vol. 9, pp. 287-29 0, Feb. 2000. [14] C. Zhu, X. Lin, and L. P. Chau, Hexagon-based Search Pattern for Fast Block Motion Estimation, IEEE Trans. on Circuits Syst. Video Technol. vol. 12, pp. 349-355, May 2002. [15] K. Han and B. Chun, Adaptive Hexagon Search Pattern for Block Motion Estimation, in Proc. IEEE Syst. Man Cybern. Conf., vol. 2, pp. 1406-1409, Oct. 2003. [16] 전병태, 김병천, 고속 움직임 추정을 위한 적응형 육 각 탐색 방법, 한국통신학회논문지, 제27권, 제7A호, pp. 828-835, 2004. 7. [17] T.-H. Tsai and Y.-N. Pan, A Novel Predict Hexag on Search Algorithm for Fast Block Motion Estimat ion on H.264 Video Coding, IEEE Asia-Pacific Con ference on Circuits and Systems, pp. 609-612, Dec. 2004. [18] 남현우, 개선된 크로스-육각 패턴을 이용한 고속 블 록 정합 움직임 추정 알고리즘, 한국컴퓨터정보학회 논문지, 제11권, 제4호, pp. 77-85, 2006. 9. [19] T.-Y Chen, T-H Chen, S.-F. Huang, and Y.-F Li, An Adjustable Multipath Flatted-Hexagon Search Algorithm for Block Motion Estimation, in Proc. IE EE IIH-MSP '06, pp. 431-434., Dec. 2006. [20] T.-H, Tsai and Y.-N. Pan, A Novel 3-D Predict Hexagon Search Algorithm for Fast Block Motion Estimation on H.264 Video Coding, IEEE Trans. on Circuits Syst. Video Technol., vol. 16, no. 12, pp. 1542-1549, Dec. 2006. [21] 곽노윤, 시공간 움직임 활동도를 이용한 적응형 계층 육각 탐색, 디지털콘텐츠학회논문지, 제8권, 제4호, pp. 441-449, 2007. 12. [22] Ingrid Daubechies, Ten Lectures on Wavelets, Soci ety for Industrial and Applied Mathematics, pp. 10-1 6, 1992. 곽 노 윤 1994년 : 한국항공대학교 항공전자 공학과(공학사) 1996년 : 한국항공대학교 대학원 항공전자공학과(공학석사) 2000년 : 한국항공대학교 대학원 항공전자공학과(공학박사) 2000년~현 재 : 백석대학교 정보통신학부 부교수 2002년~현 재 : 멀티미디어 기술사 관심분야 : 영상 신호 처리, 가상 착의 시스템, 가상 성형 시스템, 영상 워핑 및 모핑, 객체 기반 비디오 코덱, 컴퓨터 그래픽스 응용 등