Photomosaics Using Principal Component Analysis

주성분 분석을 사용한 포토모자이크

^※

전영재^*, 오경수^*, 조성현^**

숭실대학교 미디어학부^*, 홍익대학교 게임학부^**

{dkreformer, oks}@ssu.ac.kr, [email protected]

Photomosaics Using Principal Component Analysis

The Global School of Media, Soongsil University^* School of Games, Hongik University^**

요 약

본 논문에서는 주성분 분석을 사용한 포토모자이크 생성 기법을 제안한다. 후보 이미지 집 합의 주성분 분석 결과인 주성분과 계수를 사용하여 후보 이미지 검색을 보다 빠르고 정확하게 포토모자이크를 생성한다. 두 이미지를 하나의 주성분으로 투영해서 계산된 두 계수가 유사하 면 두 이미지의 본래 정보 역시 유사하기 때문에, 본 논문에서 제안하는 주성분 분석을 사용하 는 계수 비교 방법은 이미지의 색상 정보와 위치 정보를 동시에 비교할 수 있다. 계수 비교 방 법은 모든 색상 비교 방법보다 빠르고, 평균 색상 비교 방법보다 정확하게 포토모자이크를 생 성한다. 본 논문에서 제안하는 포토모자이크 알고리즘은 그래픽스 하드웨어의 가속을 받아 수 행되므로 실시간에 입력 영상을 처리할 수 있다.

ABSTRACT

We propose a photomosaic method using PCA(Principal Component Analysis), which uses PCA results to find the most similar candidate fast and correctly. When two images are projected onto a certain principal component, if their coefficients are similar, they are also likely to be similar. Thus our photomosaic method using PCA can take care of both colors and shapes of images. Our method using coefficient comparison is faster than the one using all color comparison and more correct than the one using average comparison. Our hardware accelerated photomosaic algorithm can handle video images in real-time.

Keywords : Photomosaics, Principle Component Analysis, Real-time Rendering

접수일자 : 2011년 01월 06일 심사완료 : 2011년 02월 07일 교신저자(Corresponding Author) : 조성현

※ 이 논문은 2008학년도 홍익대학교 학술연구진흥비에 의하여 지원되었음.

1. 서 론

포토모자이크(photomosaics) 또는 포토그래픽 모자이크 (photographic mosaics)는 사진과 모자 이크의 합성어다[1]. 포토모자이크는 하나의 큰 그 림을 작은 타일로 나누고 각 타일(tile)을 유사한 다른 이미지로 대체하는 이미지 생성 기법이다. 본 논문에서는 후보 이미지 집합의 주성분 분석 결과 를 사용하는 포토모자이크 생성 기법을 제안한다.

주성분 분석은 임의의 고차원 데이터 집합을 저차 원으로 축소할 수 있는 기법이다[2]. 주성분은 다 양한 성분의 표현이 가능한 방향 정보로 사용된다.

주성분들은 수학적 방법으로 계산되며 각각의 주성분들은 서로 직교인 기저이다. 데이터를 주성 분으로 투영하여 계수들을 얻을 수 있으며, 계수의 개수만큼 원본 데이터는 차원이 축소된다. 특정 주 성분으로 투영한 계수가 비슷하면 원본 데이터도 비슷한 특징이 있다.

본 논문에서는 후보 이미지 집합으로부터 후보 이미지들을 가장 잘 나타내는 주성분들을 계산하고 주성분 이미지로 저장한다. 주성분 이미지로 임의 의 입력 이미지를 투영하여 얻어진 계수는 입력 이미지와 색상과 모양이 가장 유사한 후보 이미지 를 찾는 데에 사용된다.

본 논문에서 제안하는 포토모자이크 방법의 렌 더링 과정은 모두 그래픽스 연산 장치(GPU)상에 서 처리되며 실시간에 수행되는 성능을 보여준다.

따라서 실시간으로 갱신되는 영상을 입력 이미지로 사용하여 포토모자이크 출력 영상을 사용자가 실시 간에 확인할 수 있다.

본 논문의 2절에서는 포토모자이크에 관한 다양 한 연구에 대해서 설명하고, 3절에서는 본 논문에 서 제안하는 포토모자이크 방법에 대해서 설명한 다. 주성분 분석을 이용한 포토모자이크 방법은 주 성분 분석을 수행하는 전처리와 포토모자이크를 렌 더링하는 2 단계로 나누어진다. 4절에서는 사용하 는 주성분 개수에 따른 포토모자이크의 성능과 다 른 포토모자이크 방법과의 화질을 비교한다.

2. 관련연구

포토모자이크는 하나의 사진을 여러 개의 작은 타일로 분할하고 각각의 분할된 타일의 색상정보를 조사한 다음, 색상이 유사한 또 다른 사진으로 대 체하는 방식이다. 따라서 포토모자이크는 원거리에 서 관찰하면 모자이크를 수행하기 전과 다름없어 보이지만 근거리에서는 각각의 타일 영역이 다른 사진으로 대체되어있음을 확인할 수 있는 작품양식 이다.

포토모자이크 생성은 작은 사진들을 입력 사진 의 색상에 맞춰서 선택하고 배치, 정렬하는 작업을 필요로 한다. 컴퓨터 그래픽스 분야에서 수학적 계 산을 통해 이런 작업들을 자동으로 수행하는 연구 가 많이 진행되었다. 자동화를 위한 연구는 목표에 따라 타일화 방식, 후보 이미지 생성 방식, 후보 이미지 비교 및 검색 방식에 관한 연구로 나눌 수 있다.

일반적으로 포토모자이크의 타일은 정방형으로 배치한다. 정방형 타일은 계산이 빠르다는 장점이 있지만, 원본 이미지의 세밀한 모양을 전부 표현할 수 없다는 단점이 있다. 직소 모자이크는 임의의 입력 모양에 대해서 임의의 타일을 가능한 한 빽 빽하게 배치하였으나[3], 다수의 층으로 타일을 쌓 고 모양에 따라 회전하여 포토모자이크를 생성하는 방법도 있다[4]. 두 층 이미지 타일 모자이크는 무 게중심 보로노이 다이어그램(Centroidal Voronoi Diagram)과 입력 이미지 외곽선의 경사도를 사용 하여 다층 포토모자이크의 단점인 외곽선 표현 문 제를 개선하였다[5]. 그 밖에 비디오 영상을 모자 이크로 만드는 기법도 소개 되었다[6].

포토모자이크의 후보 이미지로는 임의의 다른 이미지를 사용하기도 하지만 추상적인 이미지 정보 를 사용하기도 한다. 입력 이미지를 작은 붓 선으 로 추상화하거나[7], 명도의 변화를 표현하기 위해 이미지의 크기를 변경하여 입력 이미지를 하프톤 (Halftone)으로 표현하기도 하였으며[8], 보다 다양 한 색상과 모양으로 구성된 후보 타일들을 정방형

으로 배치하여 표현하는 모자이크 방식도 소개되었 다[9].

원본 이미지와 유사한 포토모자이크를 생성하기 위해서는 가능한 많은 후보 이미지들을 필요로 한 다. 또한 실시간에 포토모자이크 결과를 생성하기 위해서는 후보 이미지들과의 비교 연산이 빠르게 수행되어야 한다. GPU를 사용하여 후보 타일 중 에서 입력 이미지와 유사한 타일을 선택하는 연구 도 진행되었다[10]. 여기에서는 입력 이미지의 각 타일과 후보 이미지들 간에 텍셀 단위로 비교가 이루어지기 때문에 이미지의 색상 뿐 아니라 모양 까지 고려하여 포토모자이크를 생성할 수 있으며, 그래픽스 하드웨어의 가속을 받기 때문에 기존 CPU 기반의 알고리즘보다 성능은 향상되었지만 비교 연산의 수행이 오래 걸리기 때문에 비실시간 으로 수행된다.

일반적으로 포토모자이크의 후보 이미지 검색은 전역 검색이 사용되지만 후보 이미지의 빠른 검색 을 위해 대극(antipole) 트리 구조[11]을 사용한 포 토모자이크 기법이 제안되기도 하였다[12]. 그러나 여전히 실시간에 수행되는 수준은 아니었으며, 원 본 이미지 타일과 후보 이미지 색상의 평균값을 비교하기 때문에 모든 색상을 비교하는 방식에 비 해 정확도가 떨어진다.

주성분 분석과 포토모자이크에 관한 많은 연구 는 지금까지 독립적으로 진행되었으나, 본 논문에 서는 포토모자이크 생성을 위하여 주성분 분석의 계수를 사용하는 방법을 제안한다.

3. 주성분 분석을 사용한 포토모자이크

본 논문에서는 후보 이미지 집합의 주성분을 사 용하는 포토모자이크 방법을 제안한다. 기존의 포 토모자이크 방법들은 현재 이미지 타일과 가장 유 사한 후보 이미지를 찾기 위해 색상 비교를 수행 한다. 이런 방법들은 이미지들의 해상도가 높아질 수록 많은 계산을 필요로 한다. 계산을 보다 빠르

게 하기 위해 이미지 색상의 평균값을 사용할 수 있으나 이미지의 모양을 무시하기 때문에 정확도가 상대적으로 떨어진다.

[그림 1]은 본 논문에서 제안하는 방식의 시스템 개요를 보여준다. 본 논문에서는 기존의 방식과 달 리 주성분에 투영하여 계산한 계수를 비교하여 가 장 유사한 후보 이미지를 선택한다.

[그림 1] 제안된 포토모자이크 시스템

이를 위해 먼저 후보 이미지 집합의 주성분을 계산하고 영향력이 높은 성분을 주성분 이미지로 선택한다. 여기에서 2차원 배열로 되어있는 이미지 정보를 사용하여 주성분 분석을 수행하였기 때문에 주성분 이미지라고 표현한다. 그 다음 입력 이미지 의 모든 타일에 대해서 주성분 이미지로 투영하여 계수를 계산한다. 마지막으로 본 논문에서는 모든 색상 비교를 하는 대신 입력 이미지 타일의 계수

와 후보 이미지의 계수를 비교하여 가장 유사한 후보 이미지를 선택한다.

3.1 주성분 분석

주성분 분석은 임의의 고차원 정보 집합에 대해 정보를 유지하면서 저차원으로 차원을 감소시키는 정보 처리 방법이다[2]. 고차원 정보의 주성분, 즉 주축을 통계적인 방법으로 계산하고 구해진 주축 방향으로 정보를 투영하는 것으로 차원이 축소된 다. 예를 들어 2차원 이미지들의 집합에 대해서 주 성분 분석을 수행하면 이미지 해상도만큼의 차원을 저차원으로 압축할 수 있다. 우리는 줄어든 차원만 큼의 주성분들과 그 주성분들로의 투영 결과인 계 수들의 가중 합으로 원본 이미지를 복원할 수 있 다. 같은 방식으로 임의의 이미지를 다른 이미지 집합의 주성분을 사용해서 재연할 수도 있다.

두 가지 정보를 주성분으로 투영하여 얻어진 계 수들이 서로 유사하면 원본 정보도 유사하다는 사 실에 착안하여 본 논문에서는 새로운 포토모자이크 생성 방법을 제안하였다. 계수는 사용하는 주성분 의 개수만큼 생성하기 때문에 모든 색상을 비교하 는 방법보다 빠르고 평균 색상을 사용하는 방법보 다 정확한 결과를 얻을 수 있다.

3.2 전처리 단계

전처리 단계에서는 동일한 해상도를 가지는 후 보 이미지 집합에 대해 주성분 분석을 수행한다.

포토모자이크 생성 알고리즘의 수행 속도를 고려하 여 본 논문의 실험에서는 주성분을 8개로 제한하 였다. 따라서 후보 이미지 집합에 대한 주성분 이 미지는 8개를 사용한다. 본 논문에서는 전처리 단 계에서 8*8의 해상도를 가지는 후보 이미지 256개 를 입력으로 8개의 주성분과 후보 이미지별로 8개 의 계수를 생성한다. 계산된 계수는 입력 이미지 타일의 계수 값들과 비교하여 가장 유사한 후보 이미지를 검색하는 데에 사용한다.

3.3 포토모자이크 렌더링 단계

포토모자이크 렌더링 단계는 유사 후보이미지 검색 후 포토모자이크 렌더링으로 진행된다. 본 논 문의 포토모자이크 알고리즘은 GPU상에서 수행되 므로 알고리즘에 사용되는 자료들은 전부 텍스쳐 형태로 사용한다. 본 논문에서 제안하는 포토모자 이크 방법은 실시간에 수행되며 이미지뿐 아니라 실시간 영상을 입력으로 사용할 수도 있다.

3.3.1 유사 후보이미지 검색

포토모자이크를 수행하기 위해서는 먼저 입력 이미지를 타일로 나누는 과정이 필요하다. 타일의 모양을 결정하는 방법에는 여러 가지 방법이 있지 만, 본 논문에서는 계산의 간소화를 위해 정방형으 로 입력 이미지를 구획하였다. 그 다음 유사 후보 이미지 검색을 위해서는 입력 이미지 타일들의 계 수를 계산한다. 즉, 입력 이미지의 각 타일을 후보 이미지 집합의 주성분으로 투영하여 계수를 계산하 였다. 투영은 이미지간의 내적으로 동일한 위치의 텍셀 간 곱셈 결과를 전부 합산하는 내적 계산으 로 수행된다.

[그림 2]는 이미지의 모든 타일을 첫 번째 주성 분 이미지 B0에 투영하는 예를 보여준다. i번째 타 일 을 j번째 주성분 에 투영한 계수 는 식(1)을 사용하여 계산한다. 여기서 n은 타일과 주 성분 이미지의 텍셀의 수이며 _와 _{는 각각} 타일 이미지와 주성분 이미지의 k번째 텍셀을 가 리킨다.

각 주성분에 대한 모든 입력 이미지 타일들의 계수 값은 한 개의 텍스쳐로 저장된다. 따라서 계 수 값을 저장한 텍스쳐는 사용하는 주성분의 개수 만큼 8개가 생성된다. 특정 주성분으로 투영한 계 수 값들이 서로 유사한 이미지들은 서로 색상과 모양이 유사할 확률이 높다.

하나의 입력 이미지 타일과 유사한 후보 이미지 를 찾기 위해 입력 이미지 타일의 계수 값을 후보

[그림 4] 주성분 개수에 따른 포토모자이크 결과 이미지들의 계수 값과 비교하여, 계수 값의 차이가

가장 적은 후보 이미지를 포토모자이크의 결과로 사용한다. 입력 이미지의 모든 타일에 대해서 위와 같은 비교를 수행한다. 주성분을 여러 개 사용하는 경우에는 가장 유사한 후보 이미지를 보다 정확하 게 찾을 수 있다.

[그림 2] 주성분에 투영한 계수 계산

_{  }



계수를 비교하여 현재 타일과 가장 유사한 후보 이미지의 순번을 [그림 3]의 ID텍스쳐로 저장한다.

후보 이미지는 일반적으로 그래픽스 하드웨어에서 개별적으로 불러들일 수 없을 만큼 많이 사용하기 때문에 볼륨 텍스쳐를 사용하였다. ID텍스쳐의 값 은 볼륨 텍스쳐를 읽을 때 깊이 값으로 사용한다.

[그림 3] ID 텍스처를 사용한 포토모자이크 결과

3.3.2 최종 렌더링

최종 렌더링 수행 시 먼저 렌더링하고자 하는 픽셀의 텍스쳐 좌표를 사용하여 ID텍스쳐를 읽는 다. ID텍스쳐는 후보 이미지의 순서인 ID를 저장 하고 있으므로 볼륨 텍스쳐로 부터 해당 후보 이 미지를 읽어올 수 있다. 우리는 모든 픽셀에 대해 서 [그림 3]과 같이 각 ID를 읽은 후, 그 값을 깊 이 값으로 사용하여 볼륨 텍스쳐를 참조한다. 참조 된 후보 이미지를 해당 위치에 그대로 렌더링해서 포토모자이크 결과가 생성된다.

4. 실험 결과

본 논문에서 제안하는 포토모자이크 방법에서는 Microsoft DirectX 3D 9.0을 그래픽스 라이브러리 로 사용하였으며, Nvidia GeForce 460 그래픽 카 드를 사용하였다. 포토모자이크 방법의 출력 해상 도는 768x768로 고정하였으며, 4096개의 8x8 타일 로 나누었다. 타일을 실제로 생성하지 않고 텍스쳐 좌표로 구간을 나누기 때문에 입력 이미지 혹은 영상은 해상도를 자유롭게 사용할 수 있다.

[그림 4]는 각각 1, 2, 4, 8개의 주성분을 사용한 포토모자이크 결과를 보여준다. 주성분의 수가 증 가 할수록 포토모자이크 결과가 원본 이미지와 유 사하다는 것을 알 수 있다.

[표 1]은 입력으로 실시간 웹캠 영상을 사용하였 을 때 주성분 개수에 따른 포토모자이크의 렌더링 성능을 보여준다. 주성분의 수가 증가 할수록 렌더 링 속도는 떨어지지만, 포토모자이크 작업이 GPU 상에서 수행되기 때문에 웹캠으로 입력받은 영상을 실시간에 포토모자이크로 출력을 할 수 있다는 것 을 알 수 있다.

[그림 5]는 평균 색상을 사용한 방식과 본 논문 에서 제안하는 방식의 결과를 보여준다. 본 논문에 서 제안하는 방식이 평균 색상을 사용한 방식보다 원본 이미지에 유사한 결과를 생성한다는 것을 알

수 있다.

주성분개수 렌더링 속도(fps)

1 1450

2 550

4 450

8 230

[표 1] 주성분개수에 따른 성능비교

[그림 5] 생성 방식에 따른 포토모자이크 결과

5. 결 론

본 논문에서는 포토모자이크 생성에서 가장 중 요한 유사 후보 이미지 선택 방법을 개선하였다.

즉, 특정 주성분으로 투영한 원본 이미지 타일의 계수와 후보 이미지들의 계수를 비교하여 원본 이 미지 타일과 제일 유사한 후보 이미지를 선택한다.

본 논문에서 제안하는 계수 비교 방식은 모든 색상 값을 비교하는 방식보다 수행 속도가 빠르며, 주성분 분석을 사용하여 입력 이미지 타일의 모양 까지 고려하였기 때문에 평균 색상 값을 비교하는 방식보다 정확한 결과를 얻을 수 있다는 것을 알 수 있었다. 제안된 포토모자이크 방법은 하드웨어 가속을 받아 실시간에 수행되므로 실시간 영상을 포토모자이크로 생성하는 것도 가능하다.

본 논문에서는 계산의 편의를 위해 원본 이미지 의 모양을 고려하지 않고 정방형 타일로 구획하였 다. 또한 후보 이미지의 계수와 비교는 선형적으로 이루어지기 때문에 모든 후보 이미지와 비교를 완 료해야만 최종 유사 이미지를 선택할 수 있다. 모 든 색상을 비교하는 방식보다 월등히 계산속도가 빠르지만, 선형적 탐색의 특성으로 인하여 후보 이 미지의 수가 증가하면 최종 포토모자이크 생성에 시간이 오래 걸리게 된다. 그러나 대극(antipole) 트리를 사용하여 후보 이미지 집합을 미리 분류해 두면 보다 빠른 포토모자이크 결과를 얻을 수 있 을 것이다.

참고문헌

[1] R. Silvers and M. Hawley, Photomosaics.

New York, NY, USA: Henry Holt and Co.

Inc., 1997.

[2] I. T. Jolliffe, Principal Component Analysis, Springer-Verlag, 1986.

[3] J. Kim and F. Pellacini, “Jigsaw Image Mosaics,” in SIGGRAPH ’02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, New

York, NY, USA: ACM, pp.657–664, 2002.

[4] J. Park, K. Yoon, and S. Ryoo,

“Multi-layered Stack Mosaic with Rotatable Objects,” in Computer Graphics International, pp.12–23, 2006.

[5] 강동완, 박영섭, 서상현, 윤경현, “원 영상의 세 부 묘사를 유지하는 두 층 이미지 타일 모자이 크 방법에 대한 연구”, 멀티미디어학회논문지, 9권, 10호, pp.1282-1295, 2006.

[6] A. W. Klein, T. Grant, A. Finkelstein, and M. F. Cohen, “Video Mosaics,” in NPAR ’02:

Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering. New York, NY, USA: ACM, pp.21–28, 2002.

[7] P. E. Haeberli, "Paint by Numbers: Abstract Image Representations," in Proceedings of SIGGRAPH '90, Computer Graphics, Annual Conference Series, pp.207-214, 1990.

[8] Adam Finkelstein and Marisa Range, "Image Mosaics," Lecture Notes in Computer Science 1375: pp.11–22, 1998.

[9] V. Ostromoukhov and R. D. Hersch, "Artistic Screening," in Proceedings of SIGGRAPH '95, Computer Graphics, Annual Conference Series, pp.219-228, 1995.

[10] 강동완, 윤경현, “프로그래밍 가능한 GPU를 이 용한 포토모자이크”, 한국컴퓨터그래픽스학회논 문지, 14권, 1호, pp.17-25, 2008.

[11] D. Cantone, A. Ferro, A. Pulvirenti, D. R.

Recupero, and D. Shasha, “Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces,”

IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp.535–550, 2005.

[12] G. D. Blasi and P. Maria, “Fast Photomosaic,” in WSCG ’05: Poster Proceedings of the 13th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2005, pp.15–16, 2005.

전 영 재 (Chun, Young Jae)

2007 숭실대학교 미디어학부 학사

2007-현재 숭실대학교 미디어학부 석박사통합과정 관심분야 : 실시간 컴퓨터 그래픽스. 게임 프로그래밍

오 경 수 (Oh, Kyoung Su)

2001 서울대학교 전기 컴퓨터 공학부 박사 2001-2002 (주) 조이멘트 개발팀장 2003-현재 숭실대학교 미디어학부 부교수

관심분야 : 실시간 컴퓨터 그래픽스, 게임 프로그래밍

조 성 현 (Cho, Sung Hyun)

1978년 서울대학교 계산통계학과 이학사 1980년 서울대학교 계산통계학과 이학석사 1995년 UCLA 컴퓨터과학과 이학박사 1996년-현재 홍익대학교 게임학부 교수

관심분야 : 게임프로그래밍, 게임그래픽스, 게임인공지능