REP - CP - 009, April Graph Clique 를이용한사진클러스터링과시각화인터페이스의구성 Photo Clustering using Clique and Its Visualized Interface Ryu Dong-Sung 류동성부산대학교컴퓨터

Size: px

Start display at page:

Download "REP - CP - 009, April Graph Clique 를이용한사진클러스터링과시각화인터페이스의구성 Photo Clustering using Clique and Its Visualized Interface Ryu Dong-Sung 류동성부산대학교컴퓨터"

지석 소
5 years ago
Views:

1 REP - CP - 009, April Graph Clique 를이용한사진클러스터링과시각화인터페이스의구성 Photo Clustering using Clique and Its Visualized Interface Ryu Dong-Sung 류동성부산대학교컴퓨터공학과 dsryu99@pusan.ac.kr ABSTRACT 최근디지털사진의보급으로인해, 많은수의사진이촬영됨에따라서, 사진관리에관한많은연구가진행되고있다. 그러나대부분의사진관리에사용되는썸네일기반의순차적인격자인터페이스는한가지사진의특성에따라각사진을정렬하는방식을사용게되는데, 사용자가많은수의사진을관리하기에는많은스크롤링과집중력을요구한다. 본논문에서는, 색상유사도와촬영시각을이용하여, 각사진을클러스터링하고시간의흐름에따라배열하는인터페이스를제안한다. 이를위해서, 사진의촬영시각에따라먼저각사진들을클러스터링하고한번분류된클러스터들을대상으로서로유사한색상의사진들끼리세부적인클러스터링을수행하였다. 이때, 세부적인클러스터링은구간그래프의 Maximal Clique 를이용하였며, 분류된사진들은클러스터의순서에따라연속적으로각클러스터들을배치한다. 마지막으로, 제안한클러스터링기능과사진배치인터페이스를평가하기위해서, 설문조사기반의사용자평가를수행하였다. Keywords Photo clustering, Interval graph, Clique, Photo visualization 1 Introduction 현재디지털카메라의확산과메모리기술의발전으로많은수의사진을촬영하는사람들이많아졌다. 예를들어, 3박 4일정도의여행으로도수백장의사진을촬영하며, 일주일일정의외국여행의경우 1,000장정도의사진을촬영하는일도종종발생한다 (PHOTOLAND 논문의데이터셋참조 ) [7]. 이렇게촬영된많은수의사진들을관리하기위한작업들은크게사진을선별하는작업과각사진들을시간이나이벤트에따라분류하는두가지작업으로구성된다. 그러나이와같은사진관리작업들은많은수의사진들을일일이살펴보고사진의종류를판별해야하기때문에, 많은시간이소모되고작업상의불편함이존재한다. 사진관리의수작업을자동화하기위해많은수의상용화된프로그램의개발과연구가진행되고있으며, 대부분의프로그램들은사진의촬영시각과내용그리고촬영장소를기준으로각사진들을관리하고분류하는방법을사용한다 [7]. 현재개발되고구현된사진관리프로그램은

2 REP - CP - 009, April 썸네일기반의격자인터페이스를사용한다. 이인터페이스는순차적인격자기반의레이아웃에각사진들의썸네일을배치한후, 사용자의스크롤링에따라사진을보여주는시각화방법을채택한다 [9]. 그러나이러한순차적인격자기반의레이아웃은사진들을시간순서에따라일렬로배치하기때문에, 공간적인정보와시간적인정보를동시에고려할수없는단점이있다. 그러므로사용자가각사진집합들의시간적인흐름파악이없거나그흐름이희미한경우, 사진관리에있어서많은시간과비용을소모하게된다. 사진의배치및시각화와관련된대표적인연구로써, Andreas가제안한 MediaGLOW [4] 는위에서언급한순차적인그리드레이아웃의단점을해소하기위해서, 시간과공간정보에따라 Force-Directed 레이아웃을이용하여, 2차원공간상에각클러스터링된사진들을배치하였다. 그러나이와같은방법또한각사진들이화면공간상에서로중첩되게배치됨으로써, 사진들의사용자접근성과식별성이저하되는단점을가지고있다. 그러므로본보고서에서는다음과같은사진관리프로그램의개선점과이를해결하기위한연구문제들은다음과같다. 1. 색상정보와사진의촬영시각정보둘다를고려한클러스터링방법 2. 사진촬영시각의흐름파악이가능한사진배치방법 3. 화면공간의효율적인사용방법. 2 문제제기 그림 1은사진시각화와관련된순차적인격자인터페이스와 2차원의기하공간을이용한대표적인 2가지연구를보여준다. 그림 1 (a) 의 PhotoTOC 는책의목차인터페이스를응용하여, 각사진들을클러스터링한후, 각클러스터의대표사진을목차형태로시각화하고 [5], 그림 1 (b) 의 MediaGLOW 는 Force-Directed 스프링모델기반의레이아웃을사용하여각사진들을배치하는인터페이스를사용한다 [4]. 2.1 두가지사진특성을고려한클러스터링기법각사진의촬영시각과색상정보를동시에고려하기위한문제에대해많은연구가이루어졌다. PHO- TOLAND [7] 는두사진의비교를위해서 Cooper [3] 의이벤트기반의촬영시각유사도와 25 가지색상의영상유사도 [6] 를선형보간한유사도를사용하여 2차원의격자공간에각사진들을배치하였다. 즉, 두사진의유사도 S(P i, P j ) 는촬영시각유사도 [3] 와 25가지색상에의한유사도 [6] 로측정된다. 그러므로두사진의유사도평가시, 극단적으로색상유사도나촬영시각을각각따로고려할수는있지만, 두유사도전부를동시에고려할수는없다. 다시말해두유사도값을각각 0.5 비율만큼고려한다면, 이것은각시간유사도및색상유사도를각각반씩고려하는것이지실제촬영시각순서가유지되는것을보장하는것은아니다. 이를해결하기위해서, MediaGLOW [4] 는각사진들을촬영시각과영상유사도에따라각사진들을 Force-Directed 연산으로배치하였다. 그러나 MediaGLOW 의경우, Tempooral Sequence의유지문제와각사진들이많을경우중첩문제에따른접근성문제가발생하는단점이있다.

REP - CP - 009, April 2010 3 (a) PhotoTOC [5] (b) MediaGLOW [4] 그림 1. 사진시각화와관련된대표적인 2가지연구 ( 썸네일기반의순차적인격자레이아웃과 2차원의기하공간을이용한인터페이스 ). (a) PhotoTOC 는책의목차인터페이스를응용하여, 각사진들을클러스터링한후, 각클러스터의대표사진을목차형태로시각화한다.

즉, Temporal Seqeunce는사용자가촬영된사진들이전체적으로어느시점에촬영을했는지를파악하기위한청사진을제공하는중요한정보이다.

3 REP - CP - 009, April (a) PhotoTOC [5] (b) MediaGLOW [4] 그림 1. 사진시각화와관련된대표적인 2가지연구 ( 썸네일기반의순차적인격자레이아웃과 2차원의기하공간을이용한인터페이스 ). (a) PhotoTOC 는책의목차인터페이스를응용하여, 각사진들을클러스터링한후, 각클러스터의대표사진을목차형태로시각화한다. (b) MediaGLOW 는 Force-Directed 스프링모델기반의레이아웃을사용하여각사진들을배치한다. 2.2 시간적순서의유지본논문에서는각사진클러스터들사이의 Temporal Sequence는전체적으로사진의촬영과정이시간흐름에맞게순차적으로배치되는것을의미한다. 즉, Temporal Seqeunce는사용자가촬영된사진들이전체적으로어느시점에촬영을했는지를파악하기위한청사진을제공하는중요한정보이다. MediaGLOW는각사진들이색상정보와촬영시각정보를고려하여 2차원공간에배치하는알고리즘을사용하게되는데, 만약 MediaGLOW가촬영시각정보만을고려하여각사진들을배치한다면, 전체사진들의 Temporal Sequence를유지할수있지만, 만약각클러스터사진들사이의색상정보에따른응집성과같은것들은포기해야하는단점이있다. 전체적인사진의촬영흐름정보를최대한유지하기위해서, PHOTOLAND는각사진촬영시각의응집성 (Temporal Coherence) 을고려하여사진을배치하였다. 그러나각사진들중, 사진의촬영시각차이와사진의색상유사도가큰경우, PHOTOLAND는각사진클러스터간의 Temporal Sequence 를보장하지못한다. 본논문에서는이러한문제를해결하기위해서, 각사진들의시각화과정에서순차적인격자인터페이스와는달리, 각사진클러스터들사이의 Temporal Sequence를유지한격자인터페이스를제안하였다. 2.3 화면공간사용의효율성각사진들의시각화과정에서화면에렌더링되는공간을효율적으로사용하기위한연구또한많이진행되었다. 순차적인그리드레이아웃을사용하는상용화된프로그램과연구들중, 그림 1 (a) 의 PhotoTOC [5] 와 PhotoMESA[2] 가화면을효율적으로사용하기위한대표적인연구이다. PhotoMESA는각사진들의썸네일을작게만들어서클러스터별로나열한다음사용자가원하는사진을고성능으로확대하여시각화하는방법을제공한다. PhotoTOC [5] 는왼쪽편의인덱스뷰와

REP - CP - 009, April 2010 4 (a) Temporal event

.., } 0, 1 2 3 P n C { P P, P P } i = t, t+ 1 t+ 2,.

sequence by temporal order (b) More detailed

t ) t ) t ) ( t ( P t+ 2 ( P t+ 3 ( P t+ 4 ( P t+ 5 P

(a) 시간순서에따라정렬된각사진들을 Cooper의방법에따라클러스터링을수행한다.

4 REP - CP - 009, April (a) Temporal event clustering Photo list P = { P P, P, P,..., } 0, P n C { P P, P P } i = t, t+ 1 t+ 2,... t+ n 1 P P t t+ 1 Pt+ 2 P P t+ 3 t+ 4 P t+ 5 Photo sequence by temporal order (b) More detailed clustering with interval graph t P ) t ( P t+ 1) t ) t ) t ) t ) ( t ( P t+ 2 ( P t+ 3 ( P t+ 4 ( P t+ 5 P t (0) C i (1) C i P t+1 P t+1 P t+4 P t+2 P t P t+3 P t+3 P t+2 P t+5 P t+4 P t+5 그림 2. Cooper의촬영시각에따른클러스터링과구간그래프를이용한세부클러스터링과정. (a) 시간순서에따라정렬된각사진들을 Cooper의방법에따라클러스터링을수행한다. (b) 구간그래프에서 Clique 구성을위해요구되는각구간간격 (Interval Span) 은사진유사도의평가정도에따라따라달라지게되며, 본논문에서는 25가지색상유사도를사용자가지정한임계값을기준으로설정하였다. 오른쪽의내용뷰를화면을제공함으로써, 사용자가각클러스터의요약화된대표사진을선택하고각클러스터의세부사진들을볼수있는인터페이스를구현하였다. 그러나이방법은전체적인사진의흐름을각클러스터의대표사진들로만파악해야하는단점이있으며전체사진들을시각화하기에는문제점이존재한다. 3 Maximal Clique 를이용한클러스터링 사진의촬영시각과색상정보를최대한활용하기위해서, 본논문에서는먼저 Cooper의클러스터링방법 [3] 으로각사진들을클러스터링한다. 각사진들의촬영시각차이가작다면그사진들은동일한장소에서유사한모델을촬영할가능성이많기때문에, 촬영시각으로나누어진각클러스터사진들은서로유사한사진들이많이존재하게된다. 만약나누어진클러스터의세부사진들중서로색상이

REP - CP - 009, April 2010 5 (a) (b) (c) 그림 3. 논문에서사용한사진배치순서. (a) 기존의사진관리시스템의보편적인레이아웃. 시간적인순서가썸네일들의행이변경될때마다연결되지못한다. (b) 각사진클러스터의시간일관성을유지하기위해, 붉은색화살표방향의순서대로사진을배치하여, 사용자가촬영시각에대한시간일관성을유지하게변경하였다.

먼저, Cooper 의방법으로클러스 터링된각사진집합을구간그래프 G 를이용하여, 그래프 G 의 Clique 를찾아서각 Clique 를세부 클러스터로분류한다. 구간그래프를구성하기위해서는각노드사이의간격을결정해야하는데, 논 문에서는 Prasad 가제안한 25 가지색상의색상유사도가연속적으로사용자가지정한유사도임계값 γ 이상인사진들을구간그래프 G 의간격으로설정하였다.

5 REP - CP - 009, April (a) (b) (c) 그림 3. 논문에서사용한사진배치순서. (a) 기존의사진관리시스템의보편적인레이아웃. 시간적인순서가썸네일들의행이변경될때마다연결되지못한다. (b) 각사진클러스터의시간일관성을유지하기위해, 붉은색화살표방향의순서대로사진을배치하여, 사용자가촬영시각에대한시간일관성을유지하게변경하였다. (c) 논문에서제안한사진배치결과. 색상유사도를위한클러스터링임계값 γ = 0.7 유사한사진들의쌍을찾아다시세부적인클러스터로분류한다면, 촬영시각과색상정보를둘다 고려할수있다. 그림 2 는본논문에서제안한사진클러스터링방법을보여준다. 먼저, Cooper 의방법으로클러스 터링된각사진집합을구간그래프 G 를이용하여, 그래프 G 의 Clique 를찾아서각 Clique 를세부 클러스터로분류한다. 구간그래프를구성하기위해서는각노드사이의간격을결정해야하는데, 논 문에서는 Prasad 가제안한 25 가지색상의색상유사도가연속적으로사용자가지정한유사도임계값 γ 이상인사진들을구간그래프 G 의간격으로설정하였다. 이때, 2Mb 가넘는원본사진들을 25 가지 색상으로양자화하기에는많은시간비용이소모되기때문에, 본논문에서는 GPU 를이용한 CUDA 의병렬처리기능을사용하여, 각사진들의양자화모듈변환에대한시간비용을개선하였다 [8]. 그림 2 에서시간순서에따라정렬된각사진들을그림 (a) 와같이 Cooper 의방법에따라클러 스터링된사진들을보여주며, 촬영시각에의해클러스터링된각사진들을그림 (b) 와같이 Maximal Clique 찾기알고리즘에따라구간그래프를구성하는과정을보여준다. 그림 (b) 의구간그래프는 25 가지색상이사용자가지정한임계값보다연속적으로높을경우간격이설정되게되며, 그 Maximal Clique 찾기알고리즘결과 C i 클러스터는 C (0) i 와 C (1) i 의두 Clique ( 두개의세부적인클러스터 ) 로분류된다. 그림 4은 134 장의사진을썸네일기반의순차적인인터페이스를사용하여, 배치한결과와

REP - CP - 009, April 2010 6 본논문에서제안한인터페이스로배치한결과를비교한그림이다. (a) (b) 그림 4. 134 장의사진을제안한인터페이스로배치한결과. (a) 썸네일기반의순차적 인인터페이스를사용할경우. (b) 제안한인터페이스에의해각사진들을배치한결과. 색상유사도를위한클러스터링임계값 γ = 0.

그리고구간그래프의 Maximal Clique 알고리즘에의해클러스터링된세분화된사진집합들은그림 (b) 와같이이벤트클러스터안에그림 (a) 와같은형태로각사진들을배치한다. 본논문에서는서로유사한사진들을구간그래프로모델링하여중첩된형태로배치하였는데, 제안한인터페이스가얼마나효율적으로화면공간을활용하였는지를다음과같이평가하였다.

6 REP - CP - 009, April 본논문에서제안한인터페이스로배치한결과를비교한그림이다. (a) (b) 그림 장의사진을제안한인터페이스로배치한결과. (a) 썸네일기반의순차적 인인터페이스를사용할경우. (b) 제안한인터페이스에의해각사진들을배치한결과. 색상유사도를위한클러스터링임계값 γ = 0.6 본논문에서구현한각클러스터의사진배치알고리즘을설명한다. 격자공간의사진배치에서각행이변경될때마다사람의시선이연결되도록지그재그형태로그림 3의 (a) 와같이배치한다. 각사진의클러스터들을이와같이배치함으로써, 사용자가다음행을탐색할때사용자의시선에서시간일관성을유지할수있다. 그리고구간그래프의 Maximal Clique 알고리즘에의해클러스터링된세분화된사진집합들은그림 (b) 와같이이벤트클러스터안에그림 (a) 와같은형태로각사진들을배치한다. 본논문에서는서로유사한사진들을구간그래프로모델링하여중첩된형태로배치하였는데, 제안한인터페이스가얼마나효율적으로화면공간을활용하였는지를다음과같이평가하였다. 실제공간의사용성을비교하기위해, 적용한벤치마킹프로그래은보편적인사진관리인터페이스인 ACDSee [1] 이며, 같은크기의썸네일을이용하여한화면에차지하는면적의비율을측정한다. 실제로 ACDSee 가차지하는면적을 1.0으로잡았을때, 제안한인터페이스가차지하는면적을계산하였는데, 실제평가결과는표 1와같으며, 제안한인터페이스가 ACDSee 보다대략 20% 정도의사용효율을보이는것으로평가되었다. 물론이실험결과는촬영자의사진찍는습성에따라달라지며, 논문에서사용한사진집합들은특별한의도없이일반인이촬영한사진을사용하였다. 논문에서제안한사진클러스터링및시각화결과를평가하기위해서, 기존의순차적인격자레이아웃을사용하고자동클러스터링기능을제공하지않는 ACDSee Photo Manager[1] 와논문에서제안한인터페이스를비교하는사용자평가를수행하였다. 설문조사에참여한평가자의수는 8명이며, 각자자신이촬영한사진집합에서랜덤으로선택된사진을찾고분류하는과정을수행한후, 각설문조사의항목들의점수를결정하였다. 각설문조사항목과그결과는표 2과같으며, 사진관리에있어서, 사진탐색과전체사진의흐름파악그리고사진분류기능면에서제안한시스템이우수한것으로평가되었다.

7 REP - CP - 009, April 표 1. 제안한인터페이스의공간효율성. 유사사진의세부클러스터링을의해사용자가 지정한색상유사도 γ 는 0.65 를사용하였다. 사진집합 개수 제안한인터페이스 A B C D 표 2. 설문조사와사용자평가결과 (0 점 - 최저점수, 5 점 - 최고점수 ). 질문 ACDSee 제안한인터페이스 사진분류를위한편의성 사진탐색을위한효율성 전체사진집합의흐름파악 결론및향후연구과제 본논문에서는사진의촬영시각정보와색상정보를동시에활용하기위한클러스터링방법을제안하였다. 제안한클러스터링방법은 Cooper의촬영시각에근거한이벤트클러스터링을수행하고, 클러스터링된각사진들의구간그래프의클리크를이용하여, 서로색상이유사한사진들을분류하는방법을제안하였다. 또한기존의사진관리시스템에서사용하던순차적인격자인터페이스를변형하여, 사용자의사진탐색시선이연결되도록시간일관성을유지하는사진배치방법을적용하였다. 사진관리에있어서, 본논문의기여는다음과같다. 1. 사진집합을촬영시각기반의이벤트클러스터링을수행하고, 클러스터링된사진집합을색상정보에따라세분화함으로써, 촬영시각정보와색상정보를활용한클러스터링을수행한다. 2. 각사진집합의시간일관성을유지하기위한사진배치방법을제안하였고, 색상정보가서로유사한사진집합들을중첩되게배치함으로써, 사용자에게할당된화면공간을효율적으로사용한다. 3. 두사진의색상을비교할때, 25가지색상으로양자화를수행하였는데, 이양자화과정을 GPU 를이용한 CUDA 연산으로구현함으로써, 클러스터링수행시소모되는시간비용을절약하였다. 클러스터사진들을배치할때, 각클러스터가화면공간에차지하는면적을고려하지않았다. 그 결과많은수의사진이짧은시간에촬영되어, 클러스터링된사진의수가많을경우, 화면공간에사용

8 REP - CP - 009, April 하지않는비어있는공간이생성된다. 본논문에서는클러스터의사진배치시, 에너지함수와같은 목적함수를이용하여, 여백을최소화하기위한방법을향후연구과제로제시한다. 참고문헌 1. ACDSystems, ACDSee photomanager B. B. Bederson, PhotoMesa: a zoomable image browser using quantum treemaps and bubblemaps, in Proc. of ACM Symposium on User Interface Software and Technology. ACM Press, 2001, pp 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 , A. Girgensohn, F. Shipman, L. Wilcox, T. Turner, and M. Cooper, MediaGLOW: organizing photos in a graph-based workspace, in Proc. of Intelligent User Interfaces. ACM, 2009, pp J. C. Platt, M. Czerwinski, and B. A. Field, PhotoTOC: automatic clustering for browsing personal photos, in Proc. of Pacific Rim Conference on Multimedia, Dec. 2003, pp B. G. Prasad, K. K. Biswas, and S. K. Gupta, Region-based image retrieval using integrated color, shape, and location index, Computer Vision and Image Understanding, vol. 94, no. 1-3, pp , 2004, special Issue: Colour for Image Indexing and Retrieval. 7. D.-S. Ryu, W.-K. Chung, and H.-G. Cho, PHOTOLAND: a new image layout system using spatiotemporal information in digital photos, in Proc. of the 25th ACM Symposium on Applied Computing. ACM, 2010, pp Wiki, Cuda, query1=10xx 류동성, 정우근, 조환규, 격자기반의디지털사진시각화와계층적인클러스터링방법, in 제 36 한국정보과학 컴퓨터종합학술대, , pp

REP - CP - 015, January 사진들의시간적순서를고려한이미지시각화방법 An Image Visualization Method to Keep Temporal Ordering for photo sets Ryu Dong-Sung 류동성부산대학교컴퓨터공

REP - CP - 015, January 사진들의시간적순서를고려한이미지시각화방법 An Image Visualization Method to Keep Temporal Ordering for photo sets Ryu Dong-Sung 류동성부산대학교컴퓨터공 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 일반적으로대부분의사람들은많은수의디지털사진을관리하기위해서,