434 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 5 호 (2012.5) 드라마동영상의스토리분석을위한계층적은닉변수모델 (Hierarchical Latent Variable Models for Story Analysis of TV Dramas) 이바도 석호식 (Bado Lee) 장병탁 (Ho-Sik Seok) (Byoung-Tak Zhang) 요약통계기법을이용한기계학습연구가활발히진행되면서시간정보가포함된동적스트림 (stream) 분석에기계학습기법을적용하려는시도가주목받고있다. 그러나기존연구는동일이미지반복이라는사전지식을이용하여이미지구간을분리하였으며각스토리구간을특정짓는이미지 / 텍스트의분포가뚜렷하게구분되는데이터를대상으로하였기에, 다양한동영상데이터에적용하기에는적합하지않았다. 본논문에서는이미지반복등의사전지식을이용하지않고비디오스트림을설명할수있는생성모델 (Generative Model) 을구성한후구성된모델이관찰한장면 (frame) 을만들어낼수있는가능성 (Likelihood) 에기반하여주어진드라마의스토리구간을추정할수있는방법을소개한다. 본논문에서제안하는방법은각스토리구간의은닉구조설명모수비교가어렵다는난점해결을 이논문은교육과학기술부의재원으로국가연구재단의지원을받아수행된연구 (2011-0016483) 이며, 지식경제부산업원천기술개발사업 (10035348) 및교육과학기술부의 BK21-IT 사업에의해일부지원되었음 이논문은제38회추계학술발표회에서 드라마동영상의스토리분석을위한계층적은닉변수모델 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교컴퓨터공학부연구원 bdlee@bi.snu.ac.kr 학생회원 : 서울대학교컴퓨터공학부 hsseok@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 btzhang@bi.snu.ac.kr (Corresponding author 임 ) 논문접수 : 2011년 12월 28일심사완료 : 2012년 2월 16일 CopyrightC2012 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제18권제5호 (2012.5) 위해스토리구간의은닉구조가주어졌을때새로운데이터의설명가능성을계산하는방법을활용한다는특징이있다. 우리는 LDA(Latent Dirichlet Allocation) 방법론을이용하여스토리구간모델을생성하였으며, 드라마동영상에제안방법을적용하여추정한결과를인간실험자의스토리구분결과와비교하여제안방법의성능을실험적으로제시하였다. 키워드 : 스토리분절화, LDA(Latent Dirichlet Allocation), 생성모델 Abstract With the advancement of statistical machine learning, various machine learning methods have been applied to dynamic analysis of multimodal streams. However, previous studies have limitations for tackling various real-world streams because they focus on utilizing very limited characteristics of certain domains such as repetition of fixed frames. In this paper, we introduce a generative model-based segmenting method in which a story segment of a video stream is estimated through the likelihood of a given model to explain incoming data without requiring prior knowledge. There exists a profound question of how to compare each segment's latent structure parameters. In the proposed model, this difficulty is circumvented by computing likelihood of a new frame given a story model. We apply the proposed method to distinguishing several story segments in a TV drama episode. We employ LDA (Latent Dirichlet Allocation) framework for generating a story segment model. The proposed method is validated by comparing its results with those of human estimation. Key words : Story Segmentation, LDA(Latent Dirichlet Allocation), Generative Model 1. 서론 우리가접하는세상은시간성을띄고있는대규모데이터로이루어져있기때문에 [1] 실제발생하는데이터를이해할수있으려면시간성을띄고있는데이터를지능적으로처리할수있는방법이필요하다. 그러나기존연구자들 [2,3] 은사전에구성해놓은이미지인식을이용하거나, 동일한이미지가반복되고스토리에따라등장하는단어가확연히구분되는데이터를대상으로연구를진행했기때문에, 데이터에잠재된시간정보를감안하여동적으로데이터를분석하기에는한계가있었다. 데이터에대한사전지식을이용하지않고시간변화에따른데이터구조 ( 분포 ) 변화를추정할수있도록 X. Wang 등은 TOT(Topics over Time) 모델을소개하였으며 [4], X. Wei 등은데이터의시간정보를고려한동적혼합모델인 DMM(dynamic mixture model) 을소개하였다 [5]. 기존방법들은시간성을고려한동적혼합모델을생성할수있지만비디오스트림과같은데
드라마동영상의스토리분석을위한계층적은닉변수모델 435 이터적용에는아직어려움이많다. 예를들어현재활발히연구되고있는 HDP(Hierarchical Dirichlet Process)[6] 는많은가능성을내포하고있지만다양한특성의비디오스트림에대한적용가능성을아직확인하지못하였으며, DMM(Dynamic Mixture Model) 은각각의문서를개별화하지만토픽을고정하기때문에그표현력이현저히낮아진다. 본논문에서는순차데이터중에서도특히다양한모달리티로구성된동영상데이터를처리할수있는동적혼합모델을제안한다. 제안모델은 DTM(Dynamic Topic Model)[7] 에기반한것으로 Topic Mixture 모델은주어진데이터의은닉인자의형태를정확히알수없을때특히유용하다. 본논문에서제안하는모델은각시점에서관찰되는이미지정보의변화와현재스토리구간에대하여생성된스토리모델이현시점의데이터를생성할우도 (Likelihood) 를모두감안하여스토리변화를추정하는방법으로본논문에서는간략화된추론모델을이용하여스토리구간모델을생성하고우도를계산한다. 스토리구간을구분하기위해연속된구간의은닉구조를설명하는인자를직접비교하는방법은여러가지어려움이있다. 우리는이런어려움을해결하기위하여은닉구조설명인자를비교하지않고, 은닉구조가새로운데이터를생성할수있는가능성을계산하여스토리구간을추정하는방법을제안하였다. 제안방법론을미국드라마동영상파일에적용하여해당파일에존재하는스토리변환지점을추정하였으며, 인간실험자의스토리변환지점판단결과와비교하여제안방법의성능을확인하였다. 표 1 인간평가자가판단한스토리변환구간의특징 변환지점수 변환발생구간의평균길이변환발생구간길이의최소 54 개 3.87 초 1.0 초 변환발생구간길이의표준편차 변환발생구간길이의최대 표 2 인간평가자의스토리변환지점의특징 Episode 1 평균일치정도 7 100% 일치 5/54 = 9.3% 0% 일치 11/54 = 20.4% 2.94 초 11 초 그림 1 인간평가자에의한스토리지속구간추정결과. 19명의평가자에의한스토리변환점을평균한결과를도시한것임 2. 스토리변환시점추정 본논문에서는스토리에대한인간실험자의개념을제한하지않기위하여스토리의정의를사전에인간실험자에게제공하지않고주어진동영상 1) 에서한스토리가다른스토리로변환되는시점을판단하도록요청하였다. 인간실험자의판단결과는표 1과표 2 및그림 1과그림 2에정리되어있다. 그림 1은실험에사용한에피소드에대하여인간평가자가판단한변환발생지점을평균값을통해도시한것이며표 1은인간평가자의변환발생지점에기반하여생성한변환발생구간의통계적특징을설명하는자료이다. 표 1의스토리변환구간은그림 1의변환지점평균값계산에사용된평가자료들이속한구간을정리한것으로어느한스토리변환시점에대한인간평가자들의반응차이를나타내는자료이다. 1) 본논문에서는 20세기폭스텔레비전이 ABC를위해제작한미국의법률드라마인보스턴리걸 (Boston Legal) 의에피소드 1개를실험용동영상으로사용하였다. 그림 2 인간평가자들의평가일치도경향그래프. x축은어느한변환구간에서변환이발생했다고판단한평가자의수. y축은각구간의백분율의미그림 2와표 2에서알수있듯동일한동영상임에도불구하고스토리변환시점판단결과가매우다양하기때문에어느한시점에서스토리변환이발생했다고결정하기어렵다. 위와같은문제를해결하기위해우리는인간평가자의평가결과에기반하여스토리변환이발생하는구간을설정한후해당구간에스토리변환예측값이포함될경우정확한예측이라고간주하였다.
436 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 5 호 (2012.5) 3. 스토리지속구간추정방법및결과 표 3 스토리지속구간추정 표 3및그림 3에서제안방법론을설명한다. 제안방법에서는관찰데이터 의집합으로스토리를구성하고해당스토리구간을설명할수있는확률모델을토픽모델에기반하여추정한다. 추정된확률모델은현재시점 t에서관찰한데이터생성가능성 ( 우도 ) 계산에사용하는데, 제안방법에서는각특성그룹 ( 토픽 ) 이스토리의기저벡터를형성한다고가정하였다. 새로운데이터가들어왔을때이데이터가기존데이터의스토리의연장선상에있다고하면, 이데이터는기존의파라미터로써표현될수있어야한다. 각각의토픽의경우시간구간마다그형태가변하게되는데, 이의변화를감지하는것은두가지이유에서불가능하다. 첫째, 토픽모델은확률적인모델로써매번추정할때마다그형태가달라질가능성이있다. 둘째, 형태를고정하는것 이가능하다고하더라도각시간구간에서의토픽들을서로비교하는것이불가능하다. 이와같은난점을해결하기위해제안방법에서는이제까지학습한토픽모델에기반하여새로관측된장면 (frame) 의우도를계산함으로써스토리공간의변화를추정한다. 이때, 제안모델에서사용하는토픽은사전에정의한토픽이아니라특성의결합을통해실험과정에서추정되는특성집합을의미하며 LDA (Latent Dirichlet Allocation)[8] 모델에서의토픽과같다. 본논문에서는한개의에피소드에대하여수행한스토리구간변화추정결과를소개한다. 대상에피소드는총 42분의동영상으로써초당 10장의이미지를샘플링하여총 25443장의연속된이미지로변환하였다. SIFT (Scale Invariant Feature Transform)[9] 을이용하여각각의이미지에서시각특성을추출하였고, 추출된시각특성으로 1000개의시각단어를구성하여각각의이미지를시각단어의히스토그램으로변환하였다. 각각의이미지는토픽모델에서의문서 (Document) 에해당한다. 토픽모델기법을사용하려면문서를문서군으로다룰필요가있는데다음과같은가정을사용하여전체이미지를군집화하였다. 첫째, 연속된이미지의칼라히스토그램의거리값이적을경우연속된이미지로판단한다. 둘째, 첫째가정에의해군집화된이미지의경우한공간안에서카메라촬영때문에 ABA 와같이곧바로같은이미지로돌아오는상황이빈번히발생한다. 따라서 A의마지막이미지와 A 의시작이미지의칼라히스토그램의거리차가적을경우 ABA 를하나의새로운군집 A로재정의하였다. 첫번째가정으로 25443 개의후보구간을 518개로줄일수있고, 두번째가정으로다시 153개의후보구간으로축소할수있다. - 표기 : 시점 에서의데이터 의토큰혼합분포인자 : 은닉컴퍼넌트 에서관찰되는토큰 의수 : 의토큰중은닉컴퍼넌트 에속한토큰의수 : 토큰혼합분포인자의하이퍼인자 : 해당스토리구간의하이퍼인자로해당이미지에서의집중도결정 : 토픽의단어분포 : 토큰집합의크기 : 은닉컴퍼넌트집합의크기 그림 3 제안방법론의도시. : 각이미지에대한토픽혼합결정인자, ω: 시점 에서관찰한이미지 + 텍스트, : Dirichlet 분포초기화결정인자, φ: 각토픽의워드분포, K: 토픽의수, D: 이미지개수, N d: 각이미지안에포함된시각단어의개수, z: 토픽 현재관찰데이터 는이미지데이터와텍스트데이터로구성된복합데이터로이미지데이터는현재시점
드라마동영상의스토리분석을위한계층적은닉변수모델 437 에서동영상데이터의스크린샷 (Screen shot) 이며텍스트데이터는현재시점해당하는대사에해당한다. 우리는특히이미지데이터를이용하여해당모달리티가사용할토큰 (Token) 을구성하였으며인자 를이용하여현재시점 에해당하는복합데이터를구성하는토큰의구성을설명하였다. X. Wei 등은이런상황에서연속데이터의동적혼합모델 (Dynamic Mixture Model) 구성에사용할수있는 DMM(Dynamic Mixture Model) 을제안하였다 [5]. 그러나 DMM에서는 를 에기반하여추정하기때문에연속된스토리구간에대한생성모델을구성할수는있지만본논문에서의도하는스토리변환판단에는사용할수없다. 표 3에서스토리변환판단을위해제안된방법론을설명하였다. 식 (1) 에서 는토픽 z에할당된단어 w의수이다. 깁스샘플링을통하여반복적으로 값을갱신할수있다. 식 (2) 는각토픽에대한단어의분포확률로써, 는문서 t 내에서의토픽 z에할당된토큰의수이다. 이또한깁스샘플링을통하여추정될수있다. 본논문에서제안한방법은은닉컴포넌트에서관찰되는토큰의수와데이터 의토큰이속한은닉컴포넌트정보를이용하여획득된은닉컴포넌트들의혼합비를이용하여스토리구간을설명하는모델을생성한다. 제안모델의성능을측정할수있도록다음과같은측도를사용하였다. 모델적용후의후보군 선택된후보군의비율 모델적용전의후보군 인간실험자결과와일치하는후보군 정확도 모델적용후의후보군 - 우도기준값 (threshold) : 각군집이다음군집을생성할수있는지판단하는기준그림 4 및그림 5는제안모델의변환지점추정성능을도시한것이다. 그림 4는우도기준값에따른후보군선택비율 ( 녹색선 ) 과선택된후보군에서정확한추정결과가차지하는비율 ( 청색선 ) 로, 전처리를통하여뽑아낸 153개의후보군중에서우도의기준값을변화시키면서찾아진후보군이어떤비율로생성되는지를나타낸다. 기준값이작을때는각군집별로다음군집을생성할우도가매우작더라도무조건전군집으로부터다음군집이생성되었다고판단하기때문에후보군이잘생성되지않지만 ( 모든군집이하나로군집화되고, 스토리구간을나누지못하게된다 ) 기준값이커지면선택되는후보군의비율이높아진다. 우도기준이낮을때는선택된후보군의절대비율이낮기때문에정확도가높지만, 우도기준이높아지면서선택된후보군의규모가커지면예측정확도가낮아진다 ( 청색선 ). 그림 4 우도기준값에따른후보군선택비율과정확도. 이그래프에서 x축은우도기준, y축은퍼센트 (%) 의미그림 5 우도기준값의변화에따른스토리변환점의변화그래프 ( 청색선 : 인간실험자가찾은스토리변환구간, 색깔점 : 모델예측스토리변환지점, 가로축 : 시간, 세로축 : 우도기준값, 붉은실선 : 적절한우도기준값 ). 우도기준값을조절하면서제안모델의예측성능확인그림 5는우도기준값의변화가스토리변환점추정결과에미치는영향을도시한것이다. 청색세로실선은인간실험자가찾은스토리변환구간 ( 도시편의를위하여 1명의자료사용 ) 이고, 색깔점은모델이예측한스토리변환지점, 가로축은시간, 세로축은우도기준값, 붉은가로실선은적절한우도기준값이다. 높은우도는인접한스토리후보구간이같은스토리구간에속함을의미한다. 우도기준값조절을통해스토리변화감지의민감도를조절할수있다. 그림 5를통해제안모델이예측한변경점이높은우도기준에도살아남아있음을확인할수있다. 따라서적절한우도기준값을정하면제안모델이안정적으로스토리변화지점을감지할수있음을알수있다. 분석동영상에대한의미정보를사용하지않았음을
438 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 5 호 (2012.5) 감안하면제안방법은우수한예측성능을보였다. 그러나인간평가자의평가결과와예측결과를비교했을때몇가지주목할만한특징을발견하였다. 첫째, 제안방법은밝기변화에민감하다. 예를들어조명등의변화로인한색상변화에민감하며, 화면에고정된이미지 ( 타이틀롤 ) 가등장할경우새로운특징이라고인식한다. 둘째, 급격한변화에민감한데, 급격한줌인 / 줌아웃이발생하면변화라고인식한다. 본논문에서제안한모델은동영상이보유한정보중색상변화에주목한모델이므로밝기변화및급격한변화에제안모델이반응하는것은당연한결과이다. 그러나이런반응은스토리변화구간예측에도움이되지않는다. 따라서스토리측면에서는의미가없으나유의미한변화정도를갖는특성변화를견뎌낼수있는처리방법을추가해야할것이다. 4. 결론및토의본논문에서는동영상에피소드를구성하는각스토리구간을 Dirichlet 분포에기반하여모델링할수있다는가정하에스토리변환구간을추정하는방법론을제안하였다. 동영상데이터에대한사전지식 ( 토픽 ) 에기반하여연관된데이터가연속된경우만을가정했던기존방법론과달리, 제안방법은연관된데이터가일정시간지속된후새로운종류의데이터 ( 스토리 ) 가등장하는상황을처리할수있는방법이다. 제안방법의성능은인간평가자의스토리변환판단결과와비교하여확인하였다. 스토리변환이라는문제는인간실험자들조차공통된변환점을판단하지못하는어려운문제지만, 인간실험자의변환점판단결과를정답이라고간주하고비교한결과를측정할수있는새로운방법을정의하여추정결과를수치적으로분석한결과는다음과같다. 첫째, 생성모델에기반한우도계산으로실제스토리구분점을찾을수있음을확인하였다. 둘째, 스토리구분점후보군의규모를조절할수있는수단을확보하였다. 우리는 Dirichlet 분포를이용하여스토리구간을모델링할수있다고가정했을뿐아니라그외에도이미지토픽의존재를가정하여변환지점을판단하였다. 토픽개수는추정정확성에상당한영향을미칠수있는제약조건이될수있다. 추후연구에서는이런문제를해결할수있도록토픽의수를사전에한정하지않는모델링방법을제안하고자한다. 또한이미지정보만을사용할경우조명변화, 시점변화와같은사소하지만급격한변화에취약함을확인하였으므로이미지정보채널외에다른채널을추가하여제안방법의성능을개선하고자한다. 참고문헌 [1] G. Laurent, "Sequence Coding and Learning," Dynamic Coordination in the Brain, C. v. d. Malsburg, W. A. Phillips, and W. Singer (Eds), MIT Press, pp.35-42, 2010. [ 2 ] J.-P. Poli, "An Automatic Television Stream Structuring System for Television Archives Holders," Multimedia Systems, vol.14, pp.255-275, 2008. [3] G. Manson and S.-A. Berranim "Automatic TV Broadcast Structuring," International Journal of Digital Multimedia Broadcasting, vol.2010, Article ID 153160, 2010. [4] X. Wang and A. McCallum, "Topics over Time: A Non-Markov Continuous-Time Model of Topical Trends," 12th ACM SIGKDD, pp.424-433, 2006. [5] X. Wei, J. Sun, and X. Wang, "Dynamic Mixture Models for Multiple Time Series," 20th International Joint Conference on Artificial Intelligence, pp.2909-2914, 2007. [6] Y. W. Teh and M. I. Jordan, "Hierarchical Bayesian Nonparametric Models with Applications," Bayesian Nonparametrics: Principles and Practice, N. Hjort, C. Holmes, P. Mueller, and S. Walker (Eds.), Cambridge University Press, 2010. [7] D. M. Blei and J. D. Lafferty, "Dynamic Topic Models," 23rd International Conference on Machine Learning, 2006. [8] D. Blei, A. Ng, and J. Michael, Latent Dirichlet allocation, Journal of Machine Learning Research, vol.3, pp.993-1022, 2003. [9] D.G Lowe, Object recognition from scale-invariant features, Proceedings of the Seventh IEEE International Conference on Computer Vision, vol.2, p.1150, 1999.