에지기반 다단계 타일영역분할기법을 이용한 자동 포토모자이크

2.1 전처리 과정

전처리 과정에서는 포토모자이크의 메인이 될 사진 선정, 타일영역조각에 대체될 사진들의 데이터베이스 생성 및 초기 타일영역 분할이 수행된다. 메인사진 선정과 동시에 메인사진의 전체 크기를 지정한다. 본 논문에서는 어떠한 분야에도 적용하기 쉬운 A4 용지의 크기를 사용하는 것으로 간주한다. 대체사진 데이터베이스는 일반적으로 많은 수의 사진으로 생성하는데 사진의 개수가 적으면 검색하는 과정에서 시간이 적게 걸린다는 장점을 가지지만 중복 검색될 수 있는 확률이 높아져 출력영상의 질이 떨어질 수 있다는 문제점이 있다. 영역분할은 메인영상에 일정한 타일 크기로 영역을 분할하는 단계이다. 이 단계에서 분할된 타일영역의 개수를 정해야 하며 전체 타일의 개수에 따라 분할할 영역의 수는 가로와 세로의 크기가 정해진다.

초기 분할된 타일영역은 Mi(j, k)표현할 수 있는데 M은 메인영상을 의미하며 i는 메인사진의 번호를 의미하며 i= 0,1,2........n의 양의 정수로 표현된다. 메인영상 i에 대해 j는 타일영역의 행 번호를 k는 열 번호를 의미한다. j×k는 분할된 타일영역의 수이다. 그림 1은 본 논문에서 사용될 메인영상이며 그림 2는 초기 분할된 영상으로 M1(12, 8)으로 표현된다.

Fig. 1.

Main image

Fig. 2.

Initial divided image(depth 1)

2.2 에지검출 및 다단계 타일영역 분할

에지 검출과정은 메인사진에 대해 에지를 검출하는 단계이다[9]. 먼저 전체 메인사진에 대해 에지를 검출한 후 분할 된 타일영역에 에지가 있는지를 검사한다. 에지가 있다고 판단되는 타일영역은 다시 일정크기로 분할되는 과정을 되풀이 하게 된다. 그러나 타일영역이 계속 분할되는 경우 영역이 너무 작아지게 되고 그에 대응하는 대체사진 또한 작아지므로 오히려 사진의 해상도가 떨어져 최종 영상의 질이 저하되는 역효과를 갖게 되므로 일정 분할 후에는 분할을 멈추도록 해야 한다.

분할하는 과정을 depth로 표현하면 초기 분할은 depth 1, 두 번째 분할은 depth 2 등 N차 depth로 나타낼 수 있으며 본 논문에서는 이를 depth의 길이 N으로 표현한다.

depth의 길이는 처음 메인화면 분할 시 타일영역 크기와 대체 사진 수에 따라 달라지므로 depth의 길이 N은 타일영역분할과정에서 결정된다. 그림 3은 영역 분할하는 과정을 나타낸 흐름도이다. 에지가 존재하고 depth길이가 초기 정한 값보다 크게 되면 영역분할이 멈추게 된다. 그러나 타일영역에서 에지가 존재하고 초기 설정한 depth길이보다 짧을 때는 영역분할이 계속 진행되며 재귀호출이 계속된다. 그림 3의 시작단계에서 분할영역은 depth 1에서의 분할영역을 의미하며 마지막 단계인 영역 재분할은 depth 2, depth 3영역으로의 분할을 의미한다.

Fig. 3.

Multi-step tile-region division procedure

2.3 특징추출 및 저장

분할된 타일영역의 특징과 유사한 대체사진을 선정하기 위해서 본 논문에서는 사용되는 특징은 HSI값을 이용한다. HSI에서 각각의 글자는 Hue(색상), Saturation(채도), Intensity(명도)를 나타낸다. HSI모델은 인간이 색을 인식하는 방식과 깊은 관계가 있으며 색상, 채도 및 명도를 지정하여 원하는 색상을 자연스럽게 선택할 수 있다는 장점을 갖는다[10][11].

그림 4는 그림 1의 메인영상에 대하여 에지검출을 수행한 후 빨간색 분할영역에 대한 HSI특징을 나타낸다. 왼쪽은 분할영역을 나타내며, 오른쪽 상단은 HSI값에 대한 텍스트를, 오른쪽 하단은 HSI에 대한 히스토그램을 나타낸다. 분할된 영역을 기준으로 H, S, I 각각에 대해 최종 평균값을 구한다.

Fig. 4.

HSI for tile region

메인영상은 2.2절에 의해 분할영역에 에지가 검출된 경우 재분할이 수행되기 때문에 그림 4에서와 같이 분할영역 각각에 대해 특징 값을 트리구조로 저장한다. 이에 반해 대체영상은 영상전체에 대한 특징 값이 추출되어 저장된다. 그림 5는 대체사진에 대하여 추출한 HSI 값을 나타낸다. 메인사진에 대해서는 분할영역을 중심으로 특징이 추출되며 대체사진에 대해서는 대체사진 전체를 중심으로 특징이 추출됨을 알 수 있다.

Fig. 5.

HSI for replacement image

2.4 대체사진추출

2.3절에서 설명한 바와 같이 데이터베이스에는 메인사진 각 분할영역에 대한 HSI와 후보사진에 대한 일의 분할영역의 HSI값이 저장되어 있다. 후보사진 검색과정에서는 메인사진 분할영역 특징과 대체사진의 특징을 비교하여 가장 유사한 대체사진을 추출하여 대체하는 과정을 수행한다. 이를 위해 본 논문에서는 수백 장의 대체사진 중에서 먼저 후보사진그룹을 검출 한 다음 후보사진 그룹 중에서 최종 한 장의 사진을 검출한다. 수 백, 수 천 장의 영역과 사진 간에 정확하게 유사도를 구분하기 위해서는 최단경로를 구한다. 분할된 영역에 대한 최단경로가 동일한 경우가 발생되기 때문에 그 후에 유클리디안 거리를 사용하여 유사도를 찾아내는 것이다. 2.3절에서 추출된 특징은 H, S, I 세 개이며 이들 간의 우선순위는 H, S, I이다.

먼저 후보사진그룹을 검출하기 위해서 본 논문에서는 맨해튼거리를 이용하여 최단경로를 계산한다. 맨해튼 거리는 식 (1)과 같이 표현할 수 있는데 두 점 A, B가 있다면 A는 (x₁,y₁), B는 (y₁,y₂)로 표현되고 이들간의 거리를 d 라 가정한다.

식 (1)을 일반화 하면 A는 (x_i1,x_i2,x_i3,…,x_i*n), B는 (y_i1,y_i2,y_i3,…,y_i*n)가 된다. 따라서 이들 간의 유사도는 식 (2)로 나타낼 수 있다.

식 (2)의 맨해튼 거리공식을 이용하여 분할영역에 배치 될 대체사진최단경로가 구해지고 분할영역에 배치될 사진들의 후보가 결정이 된다. 그 후 유클리디안 거리를 이용하여 맨해튼 거리에서 발생된 최단경로의 유사도를 비교한다. 유클리디안 공식은 다음과 같다. 두 점 P, Q가 있다면 이는 다음과 같이 식 (3)으로 표현할 수 있다.

이때 유클리디안 공식은 식 (4)와 같이 표현할 수 있으며 식 (5)와 같이 일반화시킬 수 있다.

2.5 포토모자이크생성

2.4절 식 (4), 식 (5)에 의해 추출된 대체사진을 메인영상 내 각 분할영역에 삽입하여 최종 포토모자이크를 완성하게 된다.

3.1 에지검출결과에 의한 다단계 분할

메인영상에 대해 에지검출이 수행되며 프리윗 검출자에 의해 수행된 결과를 그림 5에 나타내었다. 그림 5에서 에지가 존재하는 영역은 그림 3의 알고리즘에 따라 재분할이 이루진다. 그림 6은 그림 5에서 에지가 존재하는 영역에 대해 재분할한 영역(depth 2)을 나타낸다. 그림 5에서 R영역은 에지가 존재하지 않으므로 그림 6에서 영역분할이 이루어지지 않았으며 U, L, M, D는 에지가 존재하기 때문에 각각 네 개씩의 영역(U1,U2,U3,U4/L1 L2 L3 L4/M1 M2 M3 M4/ D1 D2 D3 D4)으로 분할됨을 알 수 있다.

Fig. 5.

Initial tile section

Fig. 6.

Depth 2 tile section

그림 7은 그림 6에서 에지가 존재하는 영역에 대해 다시 분할을 수행한 결과 즉, depth 3의 분할영역 나타낸다. 그림 6에서 U3가 다시 네 개의 영역(U31 U32 U33 U34)으로 분할되었으며, L1 L2 L3 L4영역은 모두 에지가 존재하여 각각 네 개씩의 영역으로 분할되었다. M영역에 대해서는 M1과 M3만이 에지가 존재하여 각각 네 개의 영역으로 분할되었다. D영역에 대해서는 D1 D2 D3 D4 모두 에지가 존재하여 각각 네 개씩의 영역으로 분할됨을 알 수 있다.

Fig. 7.

Depth 3 tile section

분할과정에 따라 그림 5 초기분할 depth 1에서 사용될 대체사진은 96개, 그림 6의 depth 2에서 사용될 대체사진은 210개이며, 그림 7의 depth 3에서 대체사진은 651개임을 알 수 있다.

3.2 depth별 영상품질 비교

2절의 알고리즘에 의해 대체사진이 추출되고 추출된 사진이 그림 4의 메인사진에 대체되면서 최종 포토모자이크가 완성된다. 여기서는 depth별로 그림 4의 특정영역에 대체되는 사진을 비교하여 영상품질을 비교하고자 한다. 그림 8은 depth 1에서 추출된 대체사진을 나타낸다. 대체 사진은 영역당 1장씩 4장이 추출되었으며, U, L, M, D영역에는 에지가 있음에도 불구하고 영역 당 한 장의 사진으로 대체되기 때문에 머리 영역, 귀부분이 명확하게 표현되지 않음을 알 수 있다. 그림 9는 depth 1에서 완성된 포토모자이크이며 전체적으로 그림 4의 메인영상을 제대로 표현하지 못하고 있음을 알 수 있다.

Fig. 8.

Replacement images in depth 1

Fig. 9.

Photographic in depth 1

그림 10은 depth 2에서 추출된 대체사진을 나타낸다. 대체 사진은 그림 5에서 에지가 존재하지 않은 R 영역을 제외한 U, L, M, D영역이 각각 네 개씩의 영역 U1,U2,U3,U4/L1 L2 L3 L4/M1 M2 M3 M4/ D1 D2 D3 D4으로 분할되어 16장의 대체 사진이 삽입되어 그림 10과 같이 표현됨을 알 수 있다. 그림에서와 같이 depth 2에서는 depth 1에 비해 에지성분이 많이 포함된 U, L, M 영역이 훨씬 상세히 표현되고 있음을 볼 수 있다. 그림 11은 depth 2에서 완성된 포토모자이크이며 전체적으로 그림 4의 메인영상을 완벽하게 표현하지 못하고 있지만 그림 9에 비해 훨씬 자연스럽게 표현되었음을 알 수 있다.

Fig. 10.

Replacement images in depth 2

Fig. 11.

Photographic in depth 2

그림 12는 depth 3에서 추출된 대체사진을 나타낸다. 에지가 존재하는 U3, L1, L1 L2 L3 L4, M1, M3, D1 D2 D3 D4이 각각 4개의 영역으로 분할되어 전체 12*4 =48개의 영역으로 재분할되었으며 48장의 대체사진이 삽입됨을 알 수 있다. 그림에서와 같이 depth 3에서는 depth 1에 비해 에지성분이 많이 포함된 U, L, M 영역이 훨씬 명확하게 표현되고 있음을 볼 수 있다. 그림 13은 depth 3에서 완성된 포토모자이크이며 전체적으로 그림 4의 메인영상을 대체사진으로 완벽하게 표현하고 있음을 알 수 있다.

Fig. 12.

Replacement images in depth 3

Fig. 13.

Photographic in depth 3

3.2 기존방법과의 비교

본 논문에서는 초기에 12*8의 영역분할 즉, 96장의 사진에서 시작하여 최종 depth 3에서 651장의 사진을 모두 소진하게 되는 구조이다. 그러나 기존 포토모자이크 생성방법에서는 650장의 사진에 대해 영역분할을 하므로 처음에 한번 30*20정도로 영역분할을 한 후 각 영역에 맞는 대체사진을 추출하여 모자이크를 완성하게 된다. 그림 14는 기존 방법에서와 같이 초기에 30*20으로 분할한 영역을 나타낸다. 그림 15는 기존방법에 의해 생성된 포토모자이크를 나타낸다. 빨간색으로 나타낸 영역에 대해 제안된 알고리즘에 의한 그림 13과 비교했을 때 얼굴영역, 팔 영역, 귀 영역, 이마부분 등에서 선명하지 못하고 부자연스럽다는 것을 알 수 있다. 또한 처음부터 많은 영역으로 분할하다보니 배경부분에 너무 많은 대체사진이 포함되고 대체사진들이 선명하게 나타나지 않아 사진들을 구별하기 어렵다는 문제점이 있다. 그에 비해 그림 13은 배경사진들이 선명하게 보이며 구별하기 용이함을 알 수 있다.

Fig. 14.

30*20 division image

Fig. 15.

30*20 photographic mosaic