REP - CP - 015, January 2010 1 사진들의시간적순서를고려한이미지시각화방법 An Image Visualization Method to Keep Temporal Ordering for photo sets Ryu Dong-Sung 류동성부산대학교컴퓨터공학과 dsryu99@pusan.ac.kr ABSTRACT 일반적으로대부분의사람들은많은수의디지털사진을관리하기위해서, 이벤트혹은날짜에따라각사진들을폴더별로분류하는방법을사용한다. 그러나관리해야할사진의개수가수백에서수천장으로증가함에따라, 사진관리에많은시간과비용이소모된다. 본논문에서는짧은촬영시각사이에있는사진들중, 각사진들의색상이서로유사한사진들을분류하고동시에, 분류된사진들의시간일관성이유지되는사진시각화방법을제안한다. 이를위해, 본보고서에서는시간순서대로나열되어있는각사진들을 25가지색상유사도를고려한색상유사도에따라 Interval graph를구성하였으며, 각 Interval Graph 에서 Clique를찾아각자유사한색상의사진들을클러스터링한후, 이를중요영역만렌더링하는중첩된시각화방법을제안한다. 본보고서에서제안한방법을통해, 많은수의사진들을제한된화면에효율적으로렌더링할수있으며, 각클러스터의시간순서를유지할수있다. Keywords Photo Clustering, Overlapped Layout, Interval Graph 1 Introduction 최근들어보급형디지털카메라의확산과메모리기술의발전으로인한사진저장용량의확대는일반카메라사용자들이손쉽게수백장혹은수천장의사진을촬영할수있게하였다 [4]. 그러므로이전의필름카메라를사용하였던시절과는달리일반사람들이일상생활에서수백에서수천장의사진을관리해야하는일이많아졌다 [6, 10]. 그러나이작업은많은수의사진들을일일이살펴보고사진의종류를판별해야하기때문에, 많은시간이소모되고작업상의불편함이존재한다 [10]. 대부분의사진관리프로그램은썸네일기반의격자기반의인터페이스를사용한다. 이인터페이스는순차적인격자기반의레이아웃에각사진들의썸네일을배치한후, 사용자의스크롤링에따라사진을보여주는기능을수행한다. 그러나이러한순차적인격자기반의레이아웃은사진들을시간순서에따라일렬로배치하기때문에, 공간적인정보와시간적인정보를동시에고려할수없다. 그러므로사용자가각사진집합들의시간적인흐름파악이없거나시간흐름이희미한경우, 사진관리에있어서
REP - CP - 015, January 2010 2 많은시간과비용을소모하게된다. 본보고서에서는다음과같은사진관리프로그램의개선점과이를해결하기위한방법에대해논의한다. 1. Utilization of screen space : 제한된화면공간에배치하기에너무많은사진을관리해야한다. 2. Summarization of photo clusters : 촬영시각과색상이서로유사한사진들의집합은대표사진만배치한다. 3. Discontinuity of temporal sequence : 사진탐색과정에있어서, 일관된시간순서를유지하는사진배치방법이필요하다. 2 관련연구많은수의디지털사진들을관리하기위해, 최근까지많은연구가이루어졌다. 먼저, Bederson은영상줌인브라우저인 PhotoMesa를개발하였다 [4]. PhotoMesa는 Quantum Treemap과 Bubble map을사용하여, 사용자가지정한특성 ( 년도, 달, 서람 ) 에따라그룹별시각화기능과설정한각그룹을폴더로나누어정리해주는기능을제공한다. 표 1. Result of space efficiency using the proposed method compared to ACDSee. 연구 레이아웃 특징 PhotoMesa [4] 썸네일기반의격자공간 Quantum Treemap과 Bubble map을사용한확장가능인터페이스 PhotoTOC [11] 썸네일기반의격자공간 Kullback-Leibier 척도사용 Graham [10] 썸네일기반의격자공간 계층적브라우저와달력인터페이스 MediaGLOW [8] 최소에너지기반의스프링시간및공간문맥을동시에모델고려한사진배치방법 Girgensohn에의해제안된 MediaGLOW는스프링레이아웃을사용하여, 클러스터링된사진들의대표사진을배치한다. 그리고각노드사이의거리는사진의촬영시각에기반을둔최소에너지의스프링레이아웃에의해결정된다 [8]. 각사진의 GPS 정보 ( 위도와경도 ) 와촬영시각을이용하여, 스토리텔링보드를작성할수있는연구또한진행되었다. Jim에의해개발된 MyLifeBits는각디지털매체와자료를이용한스토리저작도구이며, 사용자는지도에서 GPS 정보를기반으로트랙포인트를지정하고각사진을링크하는형태로스토리텔링을구성할수있으며, 구성한스토리는슬라이드쇼와타임시트등으로시각화한다 [7]. 상업적인툴로써, 최근까지꾸준히개발되고있는 ACDSee Photo Manager [1] 와 Picasa Web Album [9] 은사진관리에있어서편리한기능들을사용자에게제공한다. 그유용한기능들은얼굴찾기및적목현상수정그리고색상보정등과같은사용보정기능들유용한기능들이대부분이며, 사용자가지정한태그정보를이용하여, 각사진들을클러스터링하는기능또한제공한다. 본논문에서는사진관리시스템에대한관련연구로써, 표 1 과같이정리하였다.
REP - CP - 015, January 2010 3 Photo set ordered by temporal information, P= { P, P, P, P, P P} 0 1 2 3 4, 5 P0 P P P 1 2 3 P P 4 5 t ( P 0 ) t P ) t P ) t P ) t P ) t P ) ( 1 ( 2 ( 3 ( 4 ( 5 P 1 P 4 P 0 P 3 P 0 P 1 P 2 P 2 Interval graph of photo set P with their clique covering P 5 P 3 P 4 P 5 C = { P, P, P P} C = { P } 0 0 1 2, 3 1 4, P 5 Intervals of spatial similarity Overlapping photo placement divided by greedy clique covering. 그림 1. Interval Graph 를이용한사진클러스터링및시각화기법. 각사진들의시간 순서를유지하고동시에 Spatial Similarity (Similarity of 25 colors) 를고려한사진클 러스터링방법. 3 Interval Graph 를이용한사진클러스터링 Interval Graph는 Graph Theory에서주로사용하며, 각노드가양끝단인간격들의교차그래프이며, 각간격이교차하는노드들에게에지를할당한다. 각 i-번째노드의각시점이 I i 이고 P R 을각시점의집합이라고한다면, Interval Graph G = (V, E) 에서 V = {I 1, I 2,..., I n } 이며각시점의연속된쌍인에지는 {I α, I β } E I α I β 0 로정의할수있다. 본보고서에서는그림 1과같이 Interval Graph를이용하여, 시간순서를유지한상태에서, 색상이유사한각사진들을서로중첩되게배치하는사진시각화방법을제안한다. 먼저, 그림 (a) 와같이시간순서로나열되어있는각사진집합 P 를그림 (b) 와같이각사진들의색상이유사한정도를 Interval 로지정한다. 여기서각사진쌍의색상유사도는 Prasad가제안한 25가지생상표에따라각유사도가계산된다. 예를들어, 사진 P 3 의경우나머지모든사진들과의색상이유사하기때문에, P 3 사진은모든노드에걸쳐지는간격으로설정된다. 그후, 그림 (c) 와같이 Interval Graph를구성한후, 각노드들이완전부그래프 (complete sub graph) 를구성하는 Clique (C 0 과 C 1 ) 를찾아서, 서로유사한사진들의쌍을분류한다. 이렇게분류된각 Clique의구성사진들은각사진들마다서로유사한정도가아주높기때문에, 이들중하나의사진만으로각자의사진들을그림 (d) 와같이표현할수있다. 또한각 Clique 사이의시간일관성이유지되기때문에, 제안한방법은사용자의사진정보를시간순서에
REP - CP - 015, January 2010 4 맞게효율적으로표현할수있는장점이있다. 보고서에서제안한방법을정리하면다음과같다. 1. 25가지색상유사도가일정값이상인사진쌍들이촬영시각기준으로연속적인경우, 이간격들을 Interval로설정한다 ( 그림 b). 2. 각사진을노드로하고간격에따라설정되는 Interval Graph를구성한후, 완전부그래프인 clique를탐욕알고리즘으로반복찾기한다 ( 그림 c). 3. Clique로구성된각사진들의대표사진 ( 각 Clique를구성하는사진들중가장공통된색상의사진 ) 을선택하고, 나머지사진들은대표사진의뒷편에중요부분만렌더링되게배치한다 ( 그림 d). 그림 1의 (c) 에서각 Clique 의중첩된노드의경우 (P 3 ), 양쪽 Clique C 0 와 C 1 사이에서어떤쪽에포함될지애매한경우가발생한다. 많은해결책이있겠지만, 이러한경우양쪽 Clique 중색상유사도가더높은쪽으로포함시키는것도한가지방법이다. 본보고서에서는알고리즘의간단명료함을위해반복적인 Clique 찾기중탐욕알고리즘을적용한선택방법을적용하였다. 즉, 두 Clique의공통사진이되는 P 3 를먼저 Coverging되는 Clique 쪽으로분할하였다. 4 결론 본보고서에서는각사진의시간순서를유지하면서, 서로가유사한색상의사진집합을찾기위한사진클러스터링및시각화방법을제안하였다. 이를위해서, 촬영시각에따라정렬된각사진집합들을색상이유사한정도에따라연속된구간을 Interval Graph의 Interval로계산하였다. 그리고이 Interval Graph에서유사한사진쌍들의집합인 Clique를찾아각사진들의촬영시각순서가보존되는유사사진집합들을분류할수있을것이다. 이를요약하면다음과같다. 1. Interval Graph를이용하여시간순서가유지되는사진분류알고리즘을제안한다. 2. 25가지색상을이용하여, 유사한색상의사진집합을평가하였으며, 이와동시에분류된사진들의촬영시각순서를보존할수있다. 그러나제안한방법은아직구현되지않았으며, 구현및실험상으로해결해야할문제점들이존재한다. 예를들어서, 각사진들의색상유사도에대한임계값지정과 Interval Graph를구성할때, 고려해야하는연속된사진들의후보개수와같은문제이다. 색상유사도에대한임계값은사진을분류하고자하는사용자에의해결정되게된다. 그러나각간격지정에있어서고려해야하는연속된사진들의후보개수는사진의개수가 n 일경우, 색상유사도를비교해야하는쌍은 n (n 1) 로계산상많은비용이소모된다. 이러한경우, 실험을통하여적절한연속된사진들의후보개수 n을파악하는것이요구된다. 참고문헌 1. ACDSystems, ACDSee photomanager. http://store.acdsee.com/.
REP - CP - 015, January 2010 5 2. S. Battiato, G. Ciocca, F. Gasparini, G. Puglisi, and R. Schettini, Smart photo sticking, Adaptive Multimedial Retrieval: Retrieval, User, and Semantics, pp. 211 223, 2008. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-79860-6_17 3. H. Bay, T. Tuytelaars, and L. V. Gool, SURF: Speeded up robust features, in Proc. of the 9th ECCV 06, pp. 404 417. 4. B. B. Bederson, PhotoMesa: a zoomable image browser using quantum treemaps and bubblemaps, in Proc. of the 14th ACM UIST 01. New York, NY, USA: ACM Press, pp. 71 80. 5. W.-T. Chu and C.-H. Lin, Automatic summarization of travel photos using near-duplication detection and feature filtering, in Proc. of the 17th ACM MM 09. New York, NY, USA: ACM, pp. 1129 1130. 6. M. Cooper, J. Foote, A. Girgensohn, and L. Wilcox, Temporal event clustering for digital photo collections, ACM Transactions on Multimedia Computing, Communications and Applications, vol. 1, no. 3, pp. 269 288, 2005. 7. J. Gemmell, G. Bell, and R. Lueder, Mylifebits: a personal database for everything, Commun. ACM, vol. 49, no. 1, pp. 88 95, January 2006. [Online]. Available: http://dx.doi.org/10.1145/1107458.1107460 8. A. Girgensohn, F. Shipman, L. Wilcox, T. Turner, and M. Cooper, MediaGLOW: organizing photos in a graph-based workspace, in Proc. of IUI 09. New York, NY, USA: ACM, 2009, pp. 419 424. [Online]. Available: http://dx.doi.org/10.1145/1502650.1502711 9. Google, Picasa Web Albums, http://picasa.google.com/features.html, September 2006. 10. A. Graham, H. Garcia-Molina, A. Paepcke, and T. Winograd, Time as essence for photo browsing through personal digital libraries, in Proc. of the 2nd ACM/IEEE-CS JCDL 02. New York, NY, USA: ACM, 2002, pp. 326 335. 11. J. Platt, M. Czerwinski, and B. Field, PhotoTOC: automatic clustering for browsing personal photographs, in Proc. of the 4-th ICICS-PCM 03, vol. 1, Dec., pp. 6 10 Vol.1. 12. B. G. Prasad, K. K. Biswas, and S. K. Gupta, Region-based image retrieval using integrated color, shape and location index, in Proc. of CVIU 03, vol. 94, no. 1-3, pp. 193 233.