ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



˳ͼƵͷ֯*
ѩvʷԪ
ժҪڶƵлݼʱ,ɷָõľͷЧ֯߼ЧʵһҪֶ.ھ,ͳԶܸ֯Ľ,Ҫͨ˻֯.˳ͼĸ,Ծͷ֡ʹøйĴ֡λ,ԱûĽ֯.»ƾĸΪ֡ԵĶ,˸ĽŴ㷨.²˳ͼƾõĸĽŴ㷨Ļ˼,ʵͷ.
ؼʡƵ,ƾ,˳,˳ͼ,Ŵ㷨.
ͼšTP311
Using Similarity Sequence for Shot Organization in Video Retrieval
BAI Xue-sheng,XU Guang-you,SHI Yuan-chun
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
(National Key Laboratory of Intelligent Technology and Systems Tsinghua University Beijing 100084)
AbstractShot organization is very important in content-based video retrieval, but in most cases automatic shot organization methods fail to give satisfactory results, thus human-involved interactive organization is required. In this paper, a new shot organization method called similarity sequence is proposed, which reorders the r-frames of shot and makes similar r-frame appear near each other in the generated sequence, thus provides an effective interactive organizing interface. To compare the performance of different sequences, a distance measure called similarity distance is proposed, upon which a gene algorithm calculating similarity sequence is developed and applied to r-frame sequence reordering in shot organization. Basic ideas and algorithm modules are given in detail, also with experimental results and analysis.
Key wordsVideo retrieval, similarity distance, similarity order, similarity sequence, gene algorithm.
ֻʱĵͶý弼ķչ,ƵϢҲģźʽڴԽ(¼)Ͻд洢ʱ,֮ڼֻ洢ʽ.Ϣ,ÿ춼дƵźŲ,ЩźŵĴ洢ͼҲͳΪҪ.
ƵźŵļҪбڴͳݿ,ڶ£ϣܹźм.ڼƵźʱ,Ƶ,ҪָΪжϢƬΡͷΪĻԪ1.źкдͷʱ,ֱӶԾͷΪ,ҪԾͷ߲֯ṹ.Ŀǰõķ,Щͷռ࣬ʱϾ2.Ŀǰͼ⼼ˮƽ,Զ֯Ľ.֮,ṩһּķʹûͨɾͷ֯,Ҳ;иΪҪ.
ڱ,һµľͷ֯˳ͼ.ھԶ֯ͬ,÷ݾͷ֯󲢲,ǸһͷԶڹϵһάС˳ͼ.,ľͷλ,ϴľͷλԶ.,ûͨ򵥵ĽͿȷľͷ֯.
Ϊ˶Բͬ֡ԽбȽ,ƾĸ,Ӷ˳ͼתΪһŻ.ڴ˻,ǲŴ㷨˳ͼ.Ŵ㷨,ǳ˲ôͳͱ֮,֪ʶȾɫƬǨ¸㷨,Լӿ㷨.
ĵ1ڶƵͷ֯ҪĽ.2ϸ˵˳ͼĺ塢ƾĶԼ˳ͼŴ㷨Ļ˼.3ڸ˳ͼģͶʵƵͷ֯ʵ.
1Ƶͷ֯
1.1Ƶķָ뾵ͷ
ƵźŵĲԭͱ༭Կ֪һƵźűɶΣRECORDSTOPڼõģƵźͨƴӱ༭.ھͷת,֡Իᷢı.ͨԴԶƵļ㷨,ɽƵָһ龵ͷ.
ɷָ,ҪÿͷԱڼ.һЧķǣһͼ񡪡֡ͷ,Ӷûһֱ۵ġӻ.֡һַܳӳͷݵͼ,һͨѡͷƵеͼƵƴӣmosaicõ3.
1.2Ƶͷ֯
ֱӶԾͷھͷٵ,ڽϳݷḻƵź,ָƵܻľͷ.,ԶԾͷ,Դ֡,,Ծͷ߲֯ṹԵʮֱҪ.
ͷ֯ĳ÷,ÿͷݽռоࣨԴ֡Ĳֵ,ͨʱϵľγɸ߲֯ṹ.һͨͼ⼼õ,Ŀǰļˮƽ,ľͷеطӳ,Զõ֯Ҳ˵ҪԶ.ʵԳ,ͷ֯ɱҪ˹Ա֤֯ȷ.,ṩһַԱûɾͷ֯ʮҪ.
㷨ȱڷɼ,׼Ƕ˵ĸ֪һ.һ,˼룺Ծͷ֡γһ,ʹøйĴ֡λϽ,϶Ĵ֡λԶ.γɵоṩûһӻġ׵֯,ûֻ򵥵ĽͿɾͷ֯.
2˳ͼⷽ
2.1ƾ˳ͼ
 ӵ1ڵķ֪,ʵǶԾͷţʹľͷλ.Ϊڶ֡ԽжȽ,µƾ.
1ƾ룩. ֪ռ㼯{Pi,i=0,1,...,N},ݸ붨,һǷ·Pi0,Pi1,...,PiN,·L1=|Pil-1Pil|Ϊ·һƾ.Ȼ,һƾڵ㣨1򣩵ľ.һ,nĶΪ·nƾ,Wmm=1,2,...,nֱΪӦλmĵȨ.
ƾ붨,ǿһӦ·nƾΪڴ֡Ƴ̶ȵĶ.,Ϳʽ.
2˳,˳ͼ. ֪ռеĵ㼯{Pi,i=0,1,...,N},ݸƾ붨,һǷ·Pi0Pi1...Pin,ʹӦnƾ.˳i0i1...inΪ˵㼯ڴƾ붨µ˳,ӦĴ֡ͼΪ˳ͼ.
˳ļһȽϸӵ.ھͷ֯Ŀṩһû֯Ľ,Ҫõı˳,˳򣨴ζ·Ӧ˳򣩾Ѹ൱õ֯.ԭ,ǽ˳˳ͼͳسƺõ˳ʹ֡ͼ.
2.2ȡ˳ͼŴ㷨Ļ˼
ͨ,תΪһŻ.ǲŴ㷨,ÿֱ·Ӧʾ.Ⱥ¸Ĳ,ǳ˲ôͳӽ֮,˸֪ʶȾɫƬǨƵķ.ǽ3ַϸ˵.
1 
㷨鷽ʽ.
(a) λ Ⱦɫ1ѡһЩƬΣλ,ƵȾɫĶӦλ.Ⱦɫ2ȥѡеĵ,ʣ㰴Ⱦɫ2е˳Ⱦɫ.ͼ1Ƭа3㣨B,E,FĶλʾͼ.

ͼ1λʾͼ
(b) λ顡Ⱦɫ1ѡһƬΣȺʼλ,ƵȾɫĶӦλ.Ⱦɫ2ȥѡеĵ,ʣ㰴Ⱦɫ2е˳Ⱦɫ.ͼ2ʾƬDEFGĶλ.

ͼ2λʾͼ
2 
ַʽ.
(a) Ƭξ񡡴ȾɫѡһƬΣȺʼλ,ƵȾɫӦλ.򲻱,ƵȾɫ.ͼ3ʾƬDEFľ.

ͼ3Ƭξʾͼ
(b) ȾɫλȾɫѭλһ,ӶõȾɫ.ͼ4˳Ϊ2Ⱦɫλ.

ͼ4Ⱦɫλʾͼ
3 ֪ʶȾɫƬǨ
ͱ,¸Ĳ,ܽŵƬҲȺǨƵ.Ϊ˼ӿ㷨ٶ,˸֪ʶȾɫƬǨƵ¸.˼,ѡPͳn,Pn-1㰴㷨1γһƬ.ĳһȾɫ,ѡһʼλ,ƬθƵȾɫ,ȾɫвڴƬڵĵ㰴ԭ˳Ⱦɫ.ͼ5ʾȾɫƬǨƵ,ƬADGΪ㷨1õܽţ໥СǨƬ.

ͼ5֪ʶȾɫƬǨƱʾͼ
Pͳn,Ƭε㷨.
㷨1ȡָָȵǨƬΣ.
룺ռ㼯{Pi,i=0,1,...,N},ָPm,ָL
PmĳΪlƬ
㷨
1 һ2*L-1СĻ,PmL,ʼspos=L,epos=L+1.
2 ڵ㼯ʣѡPmĵ,ΪQ.ֱQ뻺sposepos-1ľ,Ϊdist1dist2.
3 dist1dist2,Qspos-1,ͬʱ,spos1.ת5.
4 Qepos,ͬʱ,epos1.
5 epos-sposСָl,ת(2).,sposʼeposƬη.
2.3ȡ˳ͼŴ㷨
Ͻ¸ʽ,ʵȡ˳ͼŴ㷨.㷨,ÿֵȺƾ֮.ѡ,ǲѡ(roulette wheel selection scheme).Ⱥĸ²ȶ£steady deleteʽ.㷨.
㷨2ȡСnƾ·Ŵ㷨.
룺ռ㼯{Pi,i=0,1,...,n},ƾ붨,ȺСsѭ
ССnƾ·
㷨
1 ͨʼȺ,ÿ.
2 ѡ,ȺλöȺжλ.
3 ѡ,ȺʼλöȺжλ˳.
4 ѡƬγȺʼλ,ȺилƬξ.
5 ѡλ,ȺиȾɫλ.
6 ѡͳ,㷨1ǨƬ.ݴƬκʼλ,ȺиƬǨ.
7 ɵӸ,Ⱥ.
8 ƾСȺи,ȥظ,ǰs.
9 δﵽѭ,ת2.,СƳȵĸ巵,Ϊ·.
3㷨ʵ
ñ˳㷽,Ƕ㼯˷.ͼ6˶Զά3㼯õСƾ·.ƾΪ׾,ȨؾΪ1.㼯30,ȾɫȺСѡΪ20,ѭ2 000ȡСƾ·Ϊ.

ͼ63ά㼯ȡС·ķ
ô㷨,ǶʵƵźŷָõľͷн֯.ʵͼ7ʾ.

a ԭʼ֡

b õ˳ͼ
ͼ7Ƶͷ֯
ͼ7(a)ΪƵָ㷨õľͷ֡,ֵ֡Ⱥ.ڱ㷨,Ƕ.,ǲöֱDCͼز֡ӦRGB֮ͣΪ֡Ķ,ƾΪ,׶ӦȨؾΪ1.0ȺСΪ20,ѭ1 000.ͼ7(b)Ϊźõ˳ͼ.ɼ,ڴУйƵĴ֡ŵһ,ӶΪûṩһõĽ֯.Ψһ֪ͼ7(a)е24֡δͼ7(b)λ,ں̶ܴڲزΪԵ.֡˶Ĵ,֡нϴز,нϴľ.ö˶³ĶɫֱͼԱ.֮,˳ͼĽ.
*оõ863߿ƼĿ͹ҡ211ѧƽĿ.
ͨѶϵˣѩ 100084,廪ѧѧ뼼ϵϢ
߼飺ѩ,1972,ʿ,ҪоΪݼ,Ӿ.
v,1940,,ʿʦ,ҪоΪӾ,ý弼.
ʷԪ,Ů,1967,ְʿ,ڣҪоΪֵ֧Эͬ,ý弼.
ߵλѩvʷԪ廪ѧѧ뼼ϵ 100084)
ѩvʷԪ(廪ѧܼϵͳصʵҡ 100084
οף
1Zhang H J, Kankanhalli A, Smoliar S W. Automatic partitioning of animate video. Technical Report, Institute of Systems Science, National University of Singapore, 1992
2Yeung M M, Yeo B L, Liu B. Extracting story units from long programs for video browsing and navigation. In:IEEE Computer Society ed. Proceedings of the International Conference on Multimedia Computing and Systems. Los Alamitos:IEEE Computer Society Press, 1996. 291305
3Irani M, Anandan P, Hsu S. Mosaic based representations of video sequences and their applications. In:IEEE Computer Society ed. Proceedings of the 5th International Conference on Computer Vision. Los Alamitos:IEEE Computer Society Press, 1995. 605611
ոڣ1998-06-16޸ڣ1998-09-17
