浙江大學(xué)碩士學(xué)位論文 摘要 摘要 如何高效而且令人愉快的瀏覽大量圖片一直是計(jì)算機(jī)視覺和多媒體鄰域中 的一個(gè)重大挑戰(zhàn)。現(xiàn)有的瀏覽大規(guī)模圖片集的技術(shù)按照它們對(duì)圖片的排列方式可 以分為兩類：空間排列方法和時(shí)間排列方法。空間排列方法利用屏幕空間來生成 圖片集的一個(gè)二維表示形式。傳統(tǒng)的馬賽克方法將所有圖片在一個(gè)簡(jiǎn)單的網(wǎng)格上 以不重疊的的方式排列好，它的后續(xù)工作采用更好的算法來決定圖片布局和排列 方式，但是它們都不允許圖片之間有重疊。最近出現(xiàn)的圖片拼接技術(shù)允許圖片不 重要的區(qū)域可以被其他圖片覆蓋，因而提高了屏幕的利用率。時(shí)間排列方法大部 分采用順序播放的方式，一次顯示一幅圖片。最近出現(xiàn)的新算法可以實(shí)現(xiàn)無重疊 圖片馬賽克的順序播放，它同時(shí)考慮了圖片在時(shí)間和空間上的排列方式，但是喪 失了瀏覽過程中的連續(xù)性。 本文提出的動(dòng)態(tài)圖片拼接算法是一種將時(shí)間和空間排列方式相結(jié)合的高效 大規(guī)模圖片集瀏覽技術(shù)，在圖片瀏覽過程中同時(shí)實(shí)現(xiàn)了空間排列上的緊湊性和時(shí) 間上的連續(xù)性。不同于之前的僅關(guān)注如何生成一個(gè)圖片集的二維排列方式的靜態(tài) 空間排列方法( t h u m b n a i l s ，圖片拼接) ，動(dòng)態(tài)圖片拼接技術(shù)明確考慮了時(shí)間遷 移的因素，從大規(guī)模圖片集中動(dòng)態(tài)的產(chǎn)生隨時(shí)間變化的圖片拼接結(jié)果。為了達(dá)到 圖片瀏覽的連續(xù)性，動(dòng)態(tài)圖片拼接在更新圖片拼接結(jié)果時(shí)，并不像之前的時(shí)間排 列方法那樣替換屏幕中的所有圖片，而只是更新少數(shù)圖片。它采用一種高效漸增 式的基于局部調(diào)整的算法來更新圖片布局( 所有圖片的中心位置，傾角，層次數(shù)) ， 使得屏幕展現(xiàn)的圖片可視信息量總和達(dá)到最大，因而有效的實(shí)現(xiàn)了圖片瀏覽的連 續(xù)性。較之前的圖片瀏覽算法，動(dòng)態(tài)圖片拼接在保持高效的前提下顯著提高了瀏 覽圖片的數(shù)量，豐富了用戶的視覺感受，最大限度的利用了屏幕空間和用戶時(shí)間， 達(dá)到了理想的圖片瀏覽效果。 關(guān)鍵詞：動(dòng)態(tài)圖片拼接，可視信息量，時(shí)間遷移 浙江大學(xué)碩士學(xué)位論文 a b s t r a c t a b s tr a c t b r o w s i n gl a r g ep h o t oc o l l e c t i o ni n a ne f f i c i e n ta n dp l e a s i n gw a yi sag r e a t c h a l l e n g e e x i s t i n gt e c h n i q u ef o rb r o w s i n gl a r g ep h o t oc o l l e c t i o n sc a nb ec l a s s i f i e d i n t ot w od i f f e r e n ta p p r o a c h e so nt h ea r r a n g e m e n to fi m a g e s ：s p a t i a la r r a n g e m e n t m e t h o d sa n dt e m p o r a la r r a n g e m e n tm e t h o d s s p a t i a la r r a n g e m e n tm e t h o d sa i mt o c r e a t eas i n g l e2 dr e p r e s e n t a t i o nf o rap h o t oc o l l e c t i o nu t i l i z i n gt h es c r e e ns p a c e t r a d i t i o n a lm o s a i cm e t h o dl i n e su pp h o t o si nas i m p l eg r i di nan o n - o v e r l a p p i n g m a n n e r , l a t e rw o r k su 8 cb e t t e ra l g o r i t h mt od e t e r m i n eag o o dl a y o u ta n dp l a c e m e n to f i m a g e s ，b u ta l lt h e s ew o r k sd o n ta l l o wp h o t oo v e r l a p p i n g r e c e n tt e c h n i q u en a m e d c o l l a g ea l l o w su n i m p o r t a n ta r e ao fap h o t ot ob ec o v e r e db yo t h e rp h o t o s ，8 0i t i m p r o v e st h eu t i l i z a t i o no fs c r e e ns p a c e t e m p o r a la r r a n g e m e n tm e t h o d sm o s t l y d i s p l a yp h o t oc o l l e c t i o ni nas e q u e n t i a lm a n n e rw i t ho n ei m a g ed i s p l a y e da tat i m e s o m en e wt e c h n i q u ea l l o wi m a g em o s a i c st ob es e q u e n t i a l l yd i s p l a y e d ，i tc o n s i d e r a r r a n g e m e n ta n dt e m p o r a la r r a n g e m e n ts i m u l t a n e o u s l y b u tl o s et h e t e m p o r a l c o n t i n u i t yo ft h ep r e s e n t a t i o n d y n a m i cc o l l a g ep r o p o s e di nt h i sp a p e ri sa ne f f i c i e n tt e c h n i q u ef o rb r o w s i n g l a r g ep h o t oc o l l e c t i o nt h a tc o m b i n e ss p a t i a la r r a n g e m e n tm e t h o da n dt e m p o r a l a r r a n g e m e n tm e t h o d ，a c h i e v i n gs p a t i a lc o m p a c t n e s s a n d t e m p o r a lc o n t i n u i t y s i m u l t a n e o u s l y u n l i k ep r e v i o u st e c h n i q u e s t h a tf o c u so n g e n e r a t i n g as t a t i c t w o d i m e n s i o n a la r r a n g e m e n to fp h o t o s ( s u c ha st h u m b n a i l sa n dc o l l a g e ) ，d y n a m i c c o l l a g ee x p l i c i t l yc o n s i d e r st e m p o r a lt r a n s i t i o na n dd y n a m i c a l l yc r e a t eat i m e v a r y i n g c o l l a g ef r o mt h el a r g ep h o t oc o l l e c t i o n i no r d e rt or e t a i nt h et e m p o r a lc o n t i n u i t y , d y n a m i cc o l l a g eo n l yu p d a t e sal i t t l ef e wp h o t o si n s t e a do fu p d a t i n ga l lp h o t o si nt h e s c r e e nl i k ew h a tp r e v i o u st e m p o r a l a r r a n g e m e n tm e t h o d sd o ，u s i n ga ne f f i c i e n t i n c r e m e n t a lo p t i m i z a t i o na l g o r i t h mb a s e do nl o c a l l ya d j u s t m e n tt o u p d a t et h e p l a c e m e n to fa l lp h o t o s ( t h ec e n t e rp o s i t i o n ，t h ea n g l e ，a n dt h el a y e ro fa l lp h o t o s ) a i m i n gt om a x i m i z et h ev i s u a li n f o r m a t i o ns ot h a tt e m p o r a lc o n t i n u i t yo ft h eb r o w s i n g p r o c e s si sp r e s e r v e d c o m p a r e dt op r e v i o u sa l g o r i t h m sf o rb r o w s i n gp h o t oc o l l e c t i o n ， d y n a m i cc o l l a g ed r a m a t i c a l l yi n c r e a s e st h es i z eo ft h ep h o t oc o l l e c t i o n st ob eb r o w s e d , e n r i c h e su s e r s v i s u a le x p e r i e n c e ，b e s tu t i l i z e st h es c r e e ns p a c ea n du s e rt i m e ，a n d a c h i e v e san i c ee x p e r i e n c ef o rb r o w s i n gp h o t oc o l l e c t i o n k e y w o r d s ：d y n a m i cc o l l a g e ，v i s u a li n f o r m a t i o n ，t e m p o r a lt r a n s i t i o n i ! i 浙江大學(xué)碩士學(xué)位論文圖目錄 圖目錄 圖2 1 采用了雙層表示的家庭照片集6 圖2 2d i g i t a lt a p e s t r y 的結(jié)果。7 圖2 3 滾動(dòng)播放圖片馬賽克8 圖3 1 動(dòng)態(tài)圖片拼接系統(tǒng)流程圖1 2 圖3 2 單一r o i 模型圖片拼接結(jié)果1 4 圖3 3 信息圖模型動(dòng)態(tài)圖片拼接結(jié)果1 4 圖4 1 貝葉斯網(wǎng)絡(luò)示例2 1 圖4 2 雙馬爾可夫隨機(jī)場(chǎng)的圖模型2 3 圖4 3 貝葉斯置信度傳遞過程2 4 圖4 4 包圍盒信息圖。2 9 圖4 5 帶有傾角的圖片求交轉(zhuǎn)化為包圍盒信息圖求交。2 9 圖4 6 圖模型的建立3 0 圖4 7 貝葉斯傳遞算法消息傳遞偽代碼一3 2 圖4 8 畫布初始狀態(tài)3 5 圖4 9 由初始狀態(tài)建立圖模型3 6 圖4 1 0 移除舊圖加入新圖( 新圖用加粗黑框表示) 3 6 圖4 1 1 更新圖模型3 7 圖4 1 2 中心位置優(yōu)化結(jié)果3 7 圖4 1 3 采用基于權(quán)值的拓?fù)渑判騼?yōu)化層次數(shù)偽代碼4 0 圖5 1 幾種不同的圖片瀏覽技術(shù)比較。4 3 圖5 2 用戶研究的實(shí)驗(yàn)結(jié)果總結(jié)。4 5 圖5 3 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 。4 7 圖5 4 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 。4 7 圖5 5 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 4 8 圖5 6 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 。4 8 圖5 7 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 。4 9 圖5 8 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 個(gè)人圖片集) 4 9 圖5 9 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 0 圖5 1 0 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 0 圖5 1 1 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 1 圖5 1 2 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 1 圖5 1 3 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 2 圖5 1 4 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 中國(guó)油畫) 5 2 圖5 1 5 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 5 3 圖5 1 6 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 5 3 圖5 1 7 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 5 4 h i 浙江大學(xué)碩士學(xué)位論文 圖目錄 圖5 1 8 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 5 4 圖5 1 9 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 5 5 圖5 2 0 動(dòng)態(tài)圖片拼接系統(tǒng)瀏覽截圖( 蝴蝶) 。5 5 i v 浙江大學(xué)研究生學(xué)位論文獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的 研究成果。除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā) 表或撰寫過的研究成果，也不包含為獲得澎鎏盤鱟或其他教育機(jī)構(gòu)的學(xué)位或 證書而使用過的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文 中作了明確的說明并表示謝意。 學(xué)位論文作者簽名： 簽字日期：年月日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解逝姿盤堂有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu) 送交本論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)逝姿盤堂可 以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索和傳播，可以采用影 印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。 ( 保密的學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文作者簽名： 導(dǎo)師簽名： 簽字日期： 年月日簽字日期： 1， 月 審互 多甲陣 ，l|1， 骨夥加 浙江大學(xué)碩士學(xué)位論文第1 章緒論 1 1 研究背景 第1 章緒論 隨著數(shù)碼照相機(jī)和移動(dòng)電話攝像頭的可用性和普及率的提高，數(shù)碼照片的數(shù) 量呈現(xiàn)了爆炸性的增長(zhǎng)?，F(xiàn)在，在個(gè)人電腦上保存成千上萬張家庭，旅游照片已 經(jīng)是十分普遍了；同時(shí)具有海量圖庫的互聯(lián)網(wǎng)也成為圖片的主要來源之一，用戶 經(jīng)常需要瀏覽從互聯(lián)網(wǎng)上搜索到的大量圖片。因此，設(shè)計(jì)一種在有限的時(shí)間內(nèi)使 用戶能夠充分瀏覽大量圖片的技術(shù)成為了當(dāng)今的一個(gè)具有挑戰(zhàn)性的工作。圍繞著 這個(gè)問題主要有三個(gè)階段的研究工作：圖片管理( 包括標(biāo)記和分類) ，圖片獲取 和可視化。我們的工作主要關(guān)注第三階段，也就是大量圖片的可視化問題。這直 接關(guān)系到用戶對(duì)大量圖片集的直觀視覺感受，在很多場(chǎng)合中是最需要解決的問 題，例如瀏覽家庭照片集合，瀏覽圖片搜索的結(jié)果以便于定位需要的圖片，等等。 本文提到的圖片瀏覽問題就是圖片可視化問題。 設(shè)計(jì)合理的圖片集可視化技術(shù)，也就是本文所說的瀏覽技術(shù)，必須注重兩點(diǎn)， 即效率和表達(dá)的視覺愉悅性。面對(duì)成千上萬的圖片，圖片集瀏覽技術(shù)必須在有限 的時(shí)間之內(nèi)，充分利用屏幕空間，展現(xiàn)整個(gè)圖片集合的全貌。而現(xiàn)有的工作并不 能夠很好的處理圖片瀏覽的時(shí)空協(xié)調(diào)問題，在瀏覽大規(guī)模圖片集合時(shí)，或是關(guān)注 如何在有限空間內(nèi)如何展示圖片( 已有的圖片拼接工作) ；或是關(guān)注時(shí)問，讓用 戶能夠順序?yàn)g覽圖片( 如s 1 i d e s h o w ) ，喪失了圖片拼接的緊湊型，對(duì)屏幕空間的 高利用率和瀏覽的連續(xù)性。極少數(shù)的兼顧時(shí)間和空間的算法也存在著瀏覽連續(xù)性 的問題，它們把圖片分類之后，按照不同的格局順序播放圖片拼接的結(jié)果，并且 在很大程度上不允許圖片重疊，增大了有限屏幕空間上的信息冗余度。 綜上所述，針對(duì)大量圖片的瀏覽技術(shù)具有很強(qiáng)的實(shí)用性和廣闊的應(yīng)用前景， 并且是現(xiàn)今急需解決的一個(gè)問題。同時(shí)，大規(guī)模圖片集的瀏覽技術(shù)必須做到高效 和保證用戶的視覺愉悅性，如何合理的安排圖片播放形式，協(xié)調(diào)時(shí)間和空間之間 浙江大學(xué)碩士學(xué)位論文第1 章緒論 的關(guān)系，這也是一個(gè)不小的挑戰(zhàn)。就是在這個(gè)背景下，本文提出了一種動(dòng)態(tài)圖片 拼接算法，詳細(xì)闡述了它的目標(biāo)，運(yùn)行機(jī)制和實(shí)驗(yàn)結(jié)果。經(jīng)過實(shí)驗(yàn)和一定量的用 戶體驗(yàn)測(cè)試，較之前的圖片拼接和滾動(dòng)播放( s l i d e s h o w ) ，動(dòng)態(tài)圖片拼接能更有 效地瀏覽圖片集，在種高效的算法控制下兼顧了圖片瀏覽時(shí)的時(shí)空協(xié)調(diào)，保證 了瀏覽的連續(xù)性。 1 2 研究目標(biāo)和研究?jī)?nèi)容 我們研究工作的主要內(nèi)容是設(shè)計(jì)一種瀏覽大規(guī)模圖片集的技術(shù)，它必須高效 而且具備視覺愉悅性。本文在充分借鑒之前的圖片拼接算法( p h o t oc o l l a g e ) 工作的基礎(chǔ)上，提出了一種新的圖片瀏覽算法，即動(dòng)態(tài)圖片拼接( d y n a m i c c o l l a g e ) 。下面，根據(jù)高效和視覺愉悅性，我們分別詳細(xì)闡述相關(guān)的研究?jī)?nèi)容。 1 2 1 圖片瀏覽高效性 本文提出的動(dòng)態(tài)拼接算法的高效包含兩個(gè)方面的含義：算法效率高，對(duì)畫布 ( c a n v a s ，圖片拼接的載體) 的利用率高。動(dòng)態(tài)圖片拼接允許圖片之間的相對(duì)非 關(guān)鍵區(qū)域可以相互重疊，使得有限的畫布上盡量只呈現(xiàn)關(guān)鍵區(qū)域信息，提高了畫 布的利用率。之前的圖片拼接工作將所有圖片在畫布上的排列方式，即它們的中 心位置，角度，層次( 1 a y e r ，決定圖片之間遮擋的次序) ，做為一個(gè)全局優(yōu)化問 題來求解，這樣，如果把每一個(gè)圖片的位置( 包含上述三個(gè)分量) 作為變量，那 么它的解空間可以是整個(gè)畫布，這使得優(yōu)化算法的計(jì)算量非常大。而動(dòng)態(tài)圖片拼 接把該問題視為一個(gè)局部?jī)?yōu)化問題，每個(gè)圖片的中心位置的解空間只是初始位置 的一個(gè)鄰域。于是這個(gè)局部?jī)?yōu)化問題的解空間大大減少了，這就是動(dòng)態(tài)圖片拼接 算法高效的關(guān)鍵。對(duì)于畫布上的每一幅圖片來說，優(yōu)化之后的最終位置處于其初 始位置的某一鄰域以內(nèi)。我們的局部?jī)?yōu)化算法采用一種漸增( i n c r e m e n t a l ) 的 方式對(duì)畫布上所有的圖片的位置在局部區(qū)域內(nèi)進(jìn)行調(diào)整，在很大程度上保證了優(yōu) 化前后畫布上所有圖片布局的連續(xù)性。事實(shí)上，這也是整個(gè)圖片瀏覽過程的連續(xù) 性的一個(gè)重要保證。在后面章節(jié)我們會(huì)對(duì)算法進(jìn)行詳細(xì)闡述，解釋這種局部調(diào)整 2 浙江大學(xué)碩士學(xué)位論文第1 章緒論 算法對(duì)于瀏覽圖片集問題的合理性。 1 2 2 圖片瀏覽的視覺愉悅性 這是圖片瀏覽算法設(shè)計(jì)中最具有主觀性并且挑戰(zhàn)最大的一部分。不同的用戶 有不同的需求，所謂眾口難調(diào)，我們只能基于常識(shí)，滿足最基本的需求。 由于畫布的面積有限，我們無法將大量圖片集中顯示在畫布上，必須考慮在 時(shí)間維上的圖片分布，這樣必然就有一個(gè)新舊圖片替換的問題：新的圖片進(jìn)入兩 布，舊的圖片( 或者重要性不高的圖片) 離開畫布，使得畫布空間的利用率維持 在一個(gè)合理的水平。 我們結(jié)合了人腦認(rèn)知模型對(duì)此進(jìn)行了具體分析。人腦具有暫時(shí)記憶功能，在 瀏覽圖片數(shù)據(jù)時(shí)，先前所看到的在大腦中還能保持一定的印象。為了適應(yīng)這種記 憶暫存現(xiàn)象，我們希望在更新圖片數(shù)據(jù)時(shí)，原有圖片的變動(dòng)不要太大，盡量保持 瀏覽的過程的連續(xù)性。如上一節(jié)所述，我們的優(yōu)化算法是一種局部調(diào)整算法，對(duì) 于畫布內(nèi)的每一幅圖片來說，優(yōu)化之后的最終位置處于初始位置的某個(gè)事先指定 的鄰域之內(nèi)，這樣便有效的保證圖片布局變動(dòng)的連續(xù)性，而全局優(yōu)化算法必然會(huì) 使畫布內(nèi)圖片布局發(fā)生不連續(xù)的突變。由此可以看到，基于局部調(diào)整的動(dòng)態(tài)圖片 拼接算法符合人腦的記憶暫存現(xiàn)象，確保了圖片瀏覽的視覺愉悅性。在后面的系 統(tǒng)模塊分析中，我們將對(duì)圖片調(diào)度模塊進(jìn)行細(xì)致的分析，從而可以達(dá)到更好的瀏 覽效果和更佳的視覺愉悅性。 1 3 本文組織結(jié)構(gòu) 根據(jù)上述研究?jī)?nèi)容和研究目標(biāo)，文章其余部分內(nèi)容組織如下： 第二章： 本章介紹了已有的圖片瀏覽技術(shù)，并且把現(xiàn)有的瀏覽技術(shù)按照空間排列方法 和時(shí)間排列方法進(jìn)行了分類說明，介紹了它們的研究歷史和各自的特點(diǎn)。同時(shí)指 出圖片拼接算法在瀏覽大規(guī)模圖片集時(shí)的不足，由此說明了設(shè)計(jì)新算法來瀏覽大 量圖片的必要性。 3 浙江大學(xué)碩士學(xué)位論文第1 章緒論 第三章： 本章介紹了動(dòng)態(tài)圖片拼接系統(tǒng)的概貌，指出了系統(tǒng)運(yùn)作的流程。對(duì)于系統(tǒng)流 程中的四個(gè)主要模塊，即圖片關(guān)鍵區(qū)域計(jì)算模塊( s a l i e n c yc o m p u t a t i o n ) ，調(diào)度模 塊( s c h e d u l e ) ，優(yōu)化模塊( o p t i m i z a t i o n ) ，繪制模塊( r e n d e d n g ) 進(jìn)行了有針對(duì) 性的詳細(xì)說明，明確了各個(gè)模塊的任務(wù)職責(zé)和工作過程。最后指出了優(yōu)化模塊是 動(dòng)態(tài)圖片拼接的核心模塊。 第四章： 本章詳細(xì)介紹了動(dòng)態(tài)圖片拼接系統(tǒng)的優(yōu)化模塊，集中闡述了動(dòng)態(tài)圖片拼接的 優(yōu)化過程。本章提出了相應(yīng)于特定問題背景的優(yōu)化目標(biāo)函數(shù)，利用分離優(yōu)化方式， 分別對(duì)畫布上所有圖片的中心位置，傾角，層次數(shù)進(jìn)行了優(yōu)化。最后本章對(duì)整個(gè) 優(yōu)化過程做了總結(jié)并且進(jìn)行了效率分析。 第五章： 本章主要說明了動(dòng)態(tài)圖片拼接的實(shí)驗(yàn)結(jié)果，包括以用戶體驗(yàn)的方式對(duì)包括動(dòng) 態(tài)圖片拼接技術(shù)在內(nèi)的幾種圖片瀏覽技術(shù)做比較的結(jié)果，以及采用動(dòng)態(tài)圖片拼接 系統(tǒng)瀏覽了若干個(gè)圖片集的效果。本章也根據(jù)用戶反饋的結(jié)果總結(jié)了動(dòng)態(tài)圖片拼 接在瀏覽圖片時(shí)的不足之處并且做出了分析。 第六章： 本章對(duì)全文內(nèi)容進(jìn)行了總括，回顧了本文的主要研究?jī)?nèi)容，歸納了本文的主 要貢獻(xiàn)以及創(chuàng)新點(diǎn)，并指出進(jìn)一步可以進(jìn)行研究的內(nèi)容，作為下個(gè)階段研究的重 點(diǎn)。 1 4 本章小結(jié) 本章介紹了本文研究的主題，二種新的圖片瀏覽方式一動(dòng)態(tài)圖片拼接，詳細(xì) 說明了圖片瀏覽技術(shù)產(chǎn)生的背景和現(xiàn)狀，指出了現(xiàn)有圖片瀏覽技術(shù)的不足之處， 由此引出了本文研究工作的必要性。接著，本章詳細(xì)介紹了動(dòng)態(tài)圖片拼接算法的 研究目標(biāo)和主要研究?jī)?nèi)容，提綱挈領(lǐng)的展示了本文的主體內(nèi)容。 4 浙江大學(xué)碩士學(xué)位論文第2 章圖片瀏覽研究綜述 2 1 引言 第2 章圖片瀏覽研究綜述 在緒論的介紹中，我們已經(jīng)大概介紹了當(dāng)前圖片瀏覽技術(shù)研究的現(xiàn)狀。在本 章中，我們會(huì)對(duì)已有的圖片瀏覽技術(shù)做出綜述，并且分析它們的優(yōu)點(diǎn)及不足這 些工作對(duì)于本文的工作具有重大的借鑒意義。 前面已經(jīng)指出，圖片瀏覽技術(shù)必須做到高效和保證視覺愉悅性。為了達(dá)到高 效的目標(biāo)，也就是為了充分利用有限的時(shí)間和屏幕( 畫布) 空間來展示圖片，現(xiàn) 有的大規(guī)模圖片集合的瀏覽技術(shù)根據(jù)它們對(duì)圖片的排列方式可以分為兩類：空問 排列方法( s p a t i a la r r a n g e m e n tm e t h o d ) 和時(shí)間排列方法( t i m ea r r a n g e m e n t m e t h o d ) 。最近出現(xiàn)了一類新的方法同時(shí)考慮了時(shí)間和空間上的排列方式，我們 把它放在時(shí)間排列方法中加以說明。 2 2 空間排列方法 為了充分利用畫布空間，空間排列方法致力于創(chuàng)建一個(gè)能展現(xiàn)所有圖片的二 維表示。這方面的一個(gè)傳統(tǒng)方法就是圖片馬賽克( i m a g em o s a i c i n g ) ，它把所有 的圖片用一種不重疊的方式在一個(gè)簡(jiǎn)單的網(wǎng)格內(nèi)排列好。由于它的簡(jiǎn)單實(shí)用性， 它在很多商業(yè)軟件中得到了廣泛的應(yīng)用，例如a c d s e e 1 1 ，p i c a s a 1 5 1 ，p i c l e n s l l 6 1 。 如今的圖片馬賽克技術(shù)采用更加成熟的算法來決定畫布的版面安排和圖片的位 置。b e d e r s o n 等人【2 1 提出了一種使用有序定量樹狀圖的方法來決定畫布的布局， 并且成功的把其算法應(yīng)用到了圖片瀏覽器p h o t o m e s a 之上。k u s t a n o w i t z 和 s h n e i d e r m a n t l l 】把這個(gè)方法進(jìn)行了擴(kuò)展，他們采用了改進(jìn)的畫布格局算法生成了 一個(gè)更高效的兩級(jí)圖片表達(dá)形式。在這個(gè)新的形式中，最能反映主旨的圖片被放 置在畫布的中央位置，而畫布的其他區(qū)域則放置層次稍低的圖片。他們的一個(gè)效 果如圖2 1 所示。 5 浙江大學(xué)碩士學(xué)位論文 第2 章圖片測(cè)覽研究綜述 疊鑫翻茲囂稍，確蝴辮 ，霹 醐薅霪貉j 憋毪虛紈鲞茂嗡洶擒心 翟 讎?yán)Т?。憊“滾磊i 確 潮 避鬻躺您鎰緘緘 圈幽函滋豳斌 圜鰳翻圈琵戮 爹麓 圖2 1 采用了雙層表示的家庭照片集 為了達(dá)到更好的圖片排列效果，一些工作更關(guān)注于照片管理。例如，p l a t t 等 人【川提出了圖片自動(dòng)聚類的方法，而c u i 等人【5 l 則提出了一個(gè)有效的圖片標(biāo)柱 模式。但是，本小節(jié)提到的所有技術(shù)，都是使用圖片馬賽克的形式在畫布上展現(xiàn) 圖片，原則上不允許圖片重疊，因而在有限的畫布空間內(nèi)增大了信息冗余度，并 沒有達(dá)到高效利用有限空間的目的。 最近，一種稱之為圖片拼貼畫( c o l l a g e ，本文也稱之為圖片拼接) 的技術(shù) 引起了廣泛的注意并且變得流行起來【8 ，壩6 - 1 & 2 。圖片拼接技術(shù)可以產(chǎn)生一個(gè)緊 湊的并且令人賞心悅目的多圖片展現(xiàn)形式，它和圖片馬賽克技術(shù)最大的不同之處 在于允許圖片之間重疊，這樣，通過遮擋圖片的非重要區(qū)域，在有限的畫布空問 內(nèi)就可以表示更多圖片的有用信息，達(dá)到了高效利用畫布空間的目的。由于本文 提出的動(dòng)態(tài)圖片拼接技術(shù)是在已有圖片拼接技術(shù)的基礎(chǔ)上直接產(chǎn)生，因而我們將 在2 3 節(jié)詳細(xì)介紹這一種圖片拼接技術(shù)。 圖片拼接的初始工作由g e i g e l 和l o u i i s 完成。他們用一群圖片產(chǎn)生一個(gè)自 動(dòng)的圖片拼接的結(jié)果，但是他們的結(jié)果中包含了大量的空自區(qū)域，視覺效果不佳。 6 一蹦篇蠛淼嘲一飄a啊然戮強(qiáng)嘲鍶皖一潮1錫黔鼬 訝茂蕊曩門馘瞄圜鬣嬲霸裔藹螨捌娥 一豫驄一魄螄蹬 霾鹺零嘲鬟竣繳燃豳 啊懣鵬露隴攀強(qiáng)燃弘斌譽(yù)漲警斛舳鬻娃豳隗幽囊蜢熬盼蠢峨群鬈隴跚馘瞄 掣蕊隧舅輔t一 娥圈能幽隔一隧鹽稅獺巍娥磁 戳辮麟藏聰鰳 辮娥程熱聰鰳黎圈謎心隧糟秘滓娥燃激鑫 浙江大學(xué)碩士學(xué)位論文第2 章圖片瀏覽研究綜述 r o t h e r 等人【1 9 】提出了一種“數(shù)字織錦 ( d i g i t a lt a p e s t r y ) 的方法，從圖片集 中自動(dòng)產(chǎn)生一個(gè)稠密的無縫圖片拼接效果，可以認(rèn)為這是圖片拼接的真正開端， 如圖2 2 所示為一個(gè)效果圖。 圖2 2d i g i t a lt a p e s t r y 的結(jié)果 接下來，r o t h e r 等擴(kuò)展了自己的方法，提高了方法的可量度性和計(jì)算效率， 做出了一個(gè)a u t o c o l l a g e 的結(jié)果【”l 。但是在這個(gè)工作中，他們對(duì)圖片進(jìn)行了篩選， 并不是所有的圖片都能放進(jìn)拼接圖中，因而不能在圖片拼接中瀏覽全部圖片。 w a n g 等人1 2 1 】在圖片拼接時(shí)中不采用無縫連接的方式，而是像大部分商業(yè)軟件那 樣，保持了圖片的邊框。d i a k o p o u l o s 和e s s a l 6 】提出了一種交互的方法來生成 圖片拼接結(jié)果，用戶可以根據(jù)自己的需要來創(chuàng)建圖片拼接。 在這里我們需要特別提及視頻拼接技術(shù)( v i d e oc o l l a g e ) 【4 2 2 1 。c h r i s t e l 等 人【4 l 提出了一種方法可以從新聞視頻集合中生成一個(gè)視頻拼接的結(jié)果，在他們的 方法中，所有輸入視頻的每一幀都被用來產(chǎn)生一個(gè)二維圖片拼接，由此可以看到 二維圖片拼接技術(shù)在三維上的應(yīng)用。w a n g 等人【硐用類似的技術(shù)從一個(gè)內(nèi)容更加 7 浙江大學(xué)碩士學(xué)位論文 第2 章圖片瀏覽研究綜述 廣泛的視頻集中進(jìn)行視頻拼接，該方法采用了更多種類的排列策略。k a n g 等人1 1 0 l 采用了時(shí)空蒙太奇的方法從多個(gè)輸入視頻中產(chǎn)生一個(gè)視頻拼接的結(jié)果。 2 3 時(shí)間排列方法 除了前面提到的采用空間排列方法來瀏覽圖片之外，另一種方法是按時(shí)間排 列方式來瀏覽圖片。滾動(dòng)播放( s l i d e s h o w ) 是最常見的一種，大部分商業(yè)軟件1 1 1 5 1 6 l 采用這種方式。滾動(dòng)播放一次展示一副圖片，所有的圖片用一種令人愉悅的 方式順序展現(xiàn)。最近，c h e n 等人【3 】提出了一種滾動(dòng)播放圖片馬賽克的方法。這是 一種結(jié)合時(shí)空排列形式來瀏覽圖片的方法，每一幀圖片馬賽克中包含一幅反映主 旨的大圖片，在它的周圍排布著一些襯托主旨的小圖片，如圖2 3 所示。隨著音 樂節(jié)拍，不同的圖片馬賽克被順序展現(xiàn)出來。 一一 霉! ? 霪纛鬻鍪i 霪囂絮籬麓 。 奄i i 黧一一l 簪；i o 耄 骶孽 霞澎鬟辮瀨 ! 彗謄五越滋澎耄! 凌 ，i 疊緞舞鬟畿浚| | ；期 圖2 3 滾動(dòng)播放圖片馬賽克 這種方法需要事先對(duì)圖片集按照不同的主題進(jìn)行聚類，根據(jù)聚類的結(jié)果安排 畫布，并且由背景音樂的節(jié)拍來判斷是否需要播放下一個(gè)圖片馬賽克。這種方式 考慮了圖片瀏覽的時(shí)間和空間順序，但是在時(shí)間上僅考慮音樂節(jié)拍，在空間上不 允許圖片之間的重疊，并未達(dá)到對(duì)時(shí)間和空間的充分利用。本文提出的動(dòng)態(tài)圖片 拼接技術(shù)較此有兩個(gè)主要不同之處。一，動(dòng)態(tài)圖片拼接采用可重疊的拼接形式， 達(dá)到了對(duì)畫布空間的高效利用，可以展現(xiàn)更多的圖片信息。二，動(dòng)態(tài)圖片拼接 強(qiáng)調(diào)瀏覽的連續(xù)性。在更新畫布時(shí)，只是更新畫布上的少數(shù)圖片，大部分圖片仍 然保留，而滾動(dòng)播放圖片馬賽克則是對(duì)畫布的完全刷新，時(shí)間上相鄰的兩個(gè)畫布 之間內(nèi)容及圖片布局迥異。根據(jù)前面的分析，瀏覽的連續(xù)性更可以適應(yīng)人腦的記 憶暫存現(xiàn)象，因而動(dòng)態(tài)圖片拼接較之滾動(dòng)播放圖片馬賽克能更充分的利用空間和 時(shí)間，獲得理想的圖片瀏覽效果。 8 浙江大學(xué)碩士學(xué)位論文第2 章圖片瀏覽研究綜述 2 4 圖片拼接 前面已經(jīng)介紹過，本文的工作借鑒了圖片拼接技術(shù)的結(jié)果，因此，本小節(jié)專 門分析圖片拼接技術(shù)睜1 8 2 1 2 2 1 。，并且指出在瀏覽大規(guī)模圖片集時(shí)的不足。盡管 之前的工作使用了很多不同的術(shù)語，例如，照片拼接( p h o t oc o l l a g e ) i s ，圖 片拼接( p i c t u r ec o l l a g e ) 【2 1 1 ，自動(dòng)拼接( a u t o c o l l a g e ) 1 8 l ，視頻拼接l 翊， 它們需要解決的問題都是相似的，那就是它們都需求解在靜態(tài)的二維畫布上圖片 ( 關(guān)鍵幀) 的最優(yōu)排列方式。為了避免因不同術(shù)語引起歧義，我們統(tǒng)一使用“圖 片拼接”來描述這個(gè)問題。 給定一個(gè)圖片集合，圖片拼接的目的是在一個(gè)給定大小的畫布上求得這些圖 片( 或者它的一個(gè)子集) 的一個(gè)最優(yōu)排列方式( 這里畫布的面積往往比圖片的面 積總和要小很多) ，使得畫布上所有圖片展現(xiàn)的信息量之和達(dá)到最大。一般的來 說，這是一個(gè)組合優(yōu)化問題，但是實(shí)際的解決方法中大量采用了啟發(fā)式的方法來 縮小解空間。圖片拼接求解可以分為兩個(gè)階段，即預(yù)計(jì)算階段和優(yōu)化階段。 2 4 1 預(yù)計(jì)算階段 在這個(gè)階段，圖片拼接算法首先需做的是精簡(jiǎn)輸入圖片集合，若輸入圖片集 中含有大量的冗余重復(fù)信息( 例如視頻中的所有幀) ，則算法首先從輸入圖片集 中挑選出那些最具有代表性的圖片，只有這些經(jīng)過挑選的圖片才能放入最后的拼 接結(jié)果中。接下來，對(duì)于每一幅被選中的圖片，算法采用一個(gè)可視信息度量方法 來計(jì)算它的最感興趣區(qū)域，也就是視覺上包含信息量最多，最顯著的區(qū)域。目前 在計(jì)算機(jī)視覺和多媒體領(lǐng)域中已經(jīng)發(fā)展了多種可視信息度量方法1 9 1 2 3 1 4 1 ，利用 這些方法可以采用對(duì)象識(shí)別技術(shù)在圖片中找到重要的對(duì)象，例如人臉【2 0 。 2 4 2 優(yōu)化階段 在優(yōu)化階段，圖片拼接算法把經(jīng)過挑選后的圖片排列在畫布上，使得畫布上 展現(xiàn)的信息量最大。一些已有的工作會(huì)去掉圖片的邊框，實(shí)現(xiàn)圖片的無縫連接1 1 8 2 2 1 ，這主要是通過a l p h a 通道混合或者p o i s s o n 融合的方式來實(shí)現(xiàn)的，以期達(dá)到 9 浙江大學(xué)碩士學(xué)位論文第2 章圖片瀏覽研究綜述 更好的視覺效果。由于圖片的面積總和要比畫布面積大很多，因此只有圖片的重 要區(qū)域才能被顯示在畫布上，而不重要的區(qū)域則被裁剪【6 1 ，混合【1 8 2 2 1 ，覆蓋【2 1 l 。 這是一個(gè)組合優(yōu)化問題。設(shè)畫布的面積為a ，我們需要排列n 幅圖片，那么 就存在a 種可能的圖片排列方式。盡管有多種啟發(fā)式的方法能夠縮小解空間， 采用全局優(yōu)化方法仍然有著很大的計(jì)算量。已有的算法或是用簡(jiǎn)單的啟發(fā)式方法 來得到一個(gè)次優(yōu)解【2 2 1 ；或是采用固定格局的畫稚1 6 1 ，從而得到一個(gè)非常小的解 空間；或是并不考慮解空間中所有點(diǎn)，而是在解空間中做一個(gè)蒙特卡羅采樣l 殂1 。 2 4 3 已有圖片拼接算法的不足 由上面的介紹可以看到，盡管已有的圖片拼接算法能夠有效的從一個(gè)小規(guī)模 圖片集中產(chǎn)生良好的圖片拼接效果，然而它的可擴(kuò)展性受到了畫布大小的嚴(yán)重限 制，無法在有限的畫布上展示更多的圖片。實(shí)驗(yàn)表明，如果畫布的面積與所有圖 片的面積總和之比小于0 6 時(shí)，那么圖片的任何排列方式都會(huì)顯得非常擁擠以致 于影響視覺效果【2 。因此，如果想用已有的圖片拼接算法來瀏覽大規(guī)模圖片集， 只有以下兩種方法： 1 ) 創(chuàng)建一個(gè)面積足夠大的畫布，做成一個(gè)包含所有圖片的大型拼接圖。這 種方法的缺點(diǎn)非常明顯。首先，根據(jù)前面的分析，大的畫布會(huì)形成巨大的解空間， 導(dǎo)致這種方法計(jì)算量非常大，效率很低。其次，瀏覽畫布會(huì)變得非常不方便。為 了瀏覽大小超過用戶屏幕分辨率的畫布，用戶必須前后左右拖動(dòng)畫布，顯得非常 不方便。 2 ) 從輸入圖片集中創(chuàng)建一個(gè)小型拼接圖的序列，可以設(shè)想每一個(gè)小的拼接 圖包含1 0 到2 0 幅圖片，然后用滾動(dòng)播放的形式播放拼接圖序列。這種方法的缺 點(diǎn)在于破壞了圖片瀏覽的連續(xù)性，在時(shí)間上相鄰的兩個(gè)拼接圖之間有很大的區(qū) 別。 根據(jù)上面的分析可以看到，已有的圖片拼接算法尚不適合用于瀏覽大量圖 片，由此本文提出了不破壞瀏覽連續(xù)性的動(dòng)態(tài)圖片拼接算法來瀏覽大規(guī)模圖片 集。 1 0 浙江大學(xué)碩士學(xué)位論文第2 章圖片瀏覽研究綜述 2 5 本章小結(jié) 本章主要介紹了已有的圖片瀏覽技術(shù)，并且把現(xiàn)有的瀏覽技術(shù)按照空間排列 方法和時(shí)間排列方法進(jìn)行了分類說明，介紹了它們的研究歷史和各自的特點(diǎn)。由 于本文工作主要基于圖片拼接算法，因此本章專門介紹了圖片拼接算法的研究歷 史和現(xiàn)狀，它的優(yōu)化求解的兩步過程，以及圖片拼接算法在瀏覽大規(guī)模圖片集時(shí) 的不足，由此說明了設(shè)計(jì)新算法來瀏覽大量圖片的必要性。 浙江大學(xué)碩士學(xué)位論文第3 章動(dòng)態(tài)圖片拼接算法綜述 3 1 引言 第3 章動(dòng)態(tài)圖片拼接算法綜述 從本章開始我們系統(tǒng)介紹動(dòng)態(tài)圖片拼接算法。本章將主要介紹動(dòng)態(tài)圖片拼接 系統(tǒng)的概貌，圖3 1 是整個(gè)動(dòng)態(tài)圖片拼接系統(tǒng)的流程圖。 p h o t oc o l l e c t i o n s 圖3 1 動(dòng)態(tài)圖片拼接系統(tǒng)流程圖 從圖3 1 可以看到，動(dòng)態(tài)圖片拼接系統(tǒng)的輸入是一個(gè)圖片集，它的數(shù)據(jù)來源 可以是本地的圖片數(shù)據(jù)庫，也可以是互聯(lián)網(wǎng)上圖片搜索的結(jié)果，等等。在系統(tǒng)處 理之前并不需要一次性輸入全部圖片，因?yàn)槲覀兊南到y(tǒng)是按一定的順序處理所有 圖片。這樣系統(tǒng)在很多場(chǎng)合下就具有更強(qiáng)的可用性，例如，服務(wù)器給用戶發(fā)送圖 片查詢結(jié)果時(shí)，一般情況下所有的圖片都是依次傳送過來，用戶端一次只能接收 一幅圖片，非常適合動(dòng)態(tài)圖片拼接系統(tǒng)采用“去舊迎新 的方式產(chǎn)生動(dòng)態(tài)拼圖以 供用戶瀏覽所有的圖片。 我們的動(dòng)態(tài)圖片拼接系統(tǒng)包含四個(gè)模塊：圖片關(guān)鍵區(qū)域計(jì)算模塊( s a l i e n c y c o m p u t a t i o n ) ，調(diào)度模塊( s c h e d u l e ) ，優(yōu)化模塊( o p t i m i z a t i o n ) ，繪制模塊 浙江大學(xué)碩士學(xué)位論文第3 章動(dòng)態(tài)圖片拼接算法綜述 ( r e n d e r i n g ) 。下面四個(gè)小節(jié)分別介紹這四個(gè)模塊。 3 2 圖片關(guān)鍵區(qū)域計(jì)算模塊 該模塊負(fù)責(zé)計(jì)算所有輸入圖片的視覺關(guān)鍵區(qū)域。已有的圖片拼接工作往往采 用簡(jiǎn)單的基于r o i ( r e c t a n g l eo fi n t e r e s t ) 的視覺關(guān)注模型，這種模型把圖片 的視覺關(guān)鍵區(qū)域視為一個(gè)矩形，然后在該矩形賦予相同的重要值( i m p o r t a n c e v a l u e ) 。對(duì)于采用全局優(yōu)化方法的圖片拼接算法來說，這種簡(jiǎn)單的模型可以有效 的減少計(jì)算量，因而是必要的，但是這種方法的缺陷十分明顯。很多情況下圖片 往往具有多個(gè)r o i ，例如，家庭照片中經(jīng)?？梢钥吹絻蓚€(gè)或者更多的人臉，顯然 也就具有相應(yīng)數(shù)量的r o i ：而且不同的r o i 的重要值也不必相同。 我們提出了一種更具一般性的視覺關(guān)注模型來解決這個(gè)問題。首先，我們引 入了“信息圖”( i n f o r m a t i o ni m a g e ) 的概念。我們計(jì)算每一個(gè)輸入圖片的信息 圖，信息圖的大小和原圖片大小一致，它的每一個(gè)像素值就是對(duì)應(yīng)圖片在相應(yīng)像 素上的重要值( i m p o r t a n c ev a l u e ) 。這種一般性的模型不僅解決了多r o i 的問 題( 只需在信息圖上指定相應(yīng)的r o i 即可) ，由于信息圖定義在像素級(jí)別上，我 們可以在每一個(gè)r o i 內(nèi)部采用不同的重要值分布模型，而非之前的單一值。例如， 在本文的實(shí)現(xiàn)中，所有的r o i 內(nèi)部的重要值分布采用了高斯分布模型，取得了良 好的效果。同時(shí)，為了提高這種像素級(jí)信息圖的查詢效率( 計(jì)算重疊區(qū)域信息損 失時(shí)需要查詢信息圖，累計(jì)區(qū)域內(nèi)所有像素的信息值) ，我們引入了“信息積分 圖 。對(duì)于每一幅信息圖，我們可以在線性時(shí)間內(nèi)計(jì)算它的積分圖【2 0 】并且保存， 此后對(duì)信息圖的查詢可以轉(zhuǎn)移為對(duì)積分圖的查詢，并且時(shí)間復(fù)雜度僅為d ( 1 ) ，極 大提高了信息圖的使用效率。除此之外，我們采用了有效的人臉檢測(cè)算法【冽， 信息圖中對(duì)應(yīng)人臉的區(qū)域的重要值設(shè)為一個(gè)足夠大的值，保證人臉永遠(yuǎn)不被覆 蓋。為了說明信息圖模型較單一r o i 模型的優(yōu)勢(shì)，可以對(duì)比圖3 2 和圖3 3 。我 們用已有的圖片拼接算法和單一r o i 模型生成了拼接結(jié)果圖3 2 ，而采用動(dòng)態(tài)圖 片拼接算法和信息圖模型，生成的結(jié)果如圖3 3 所示。 1 3 浙江大學(xué)碩士學(xué)位論文 第3 章動(dòng)態(tài)圖片拼接算法綜述 圖3 2 單一r o i 模型圖片拼接結(jié)果 圖3 3 信息圖模型動(dòng)態(tài)圖片拼接結(jié)果 注意到標(biāo)記紅圈的圖片。圖3 2 僅僅標(biāo)記了圖片左部的r o i ，因而右邊的人 全被擋??；而圖3 3 采用了信息圖標(biāo)記了左右兩邊的r o i ，并且在兩個(gè)r o i 內(nèi)部 采用了高斯分布模型，于是圖片左右方的關(guān)鍵部分都不被遮擋，其他相對(duì)不重要 的部分可以被覆蓋以顯示其他圖片的重要信息，達(dá)到了一個(gè)合理的圖片拼接效 1 4 浙江大學(xué)碩士學(xué)位論文第3 章動(dòng)態(tài)圖片拼接算法綜述 果。 3 3 調(diào)度模塊 調(diào)度模塊負(fù)責(zé)從當(dāng)前的拼接圖中刪除圖片，或者插入新圖片到拼接圖中。它 直接影響瀏覽順序。系統(tǒng)允許用戶自定義調(diào)度策略，從而得到多樣化的圖片拼接 效果。下面我們將論述與調(diào)度相關(guān)的三個(gè)要素，即調(diào)度時(shí)間，調(diào)度順序，調(diào)度之 后的畫布布局更新。畫布布局更新并不直接影響調(diào)度的結(jié)果，但是新圖片加入畫 布后的初始位置對(duì)當(dāng)前動(dòng)態(tài)圖片拼接的結(jié)果有直接影響，這是因?yàn)樗惴ú捎靡粋€(gè) 局部調(diào)整的方式來優(yōu)化圖片在畫布上的排列方式。我們認(rèn)為新畫片加入畫布后， 它的初始位置的選擇也屬于調(diào)度的范圍。 3 3 1 調(diào)度時(shí)間 系統(tǒng)根據(jù)一定的準(zhǔn)則，為每一個(gè)圖片確定了它在畫布內(nèi)的最大停留時(shí)間，我 們稱之為生命時(shí)間( 1 i f et i m e ) 。一旦圖片被調(diào)度模塊選擇進(jìn)入了畫布，那么一 個(gè)相應(yīng)的計(jì)時(shí)器開始計(jì)時(shí)。當(dāng)某一圖片的生命時(shí)間結(jié)束時(shí)，那么一個(gè)“p h o t o r e m o v a l 事件會(huì)被觸發(fā)，系統(tǒng)從畫布中移除該圖片。當(dāng)移除若干幅圖片之后， 畫布面積和畫布內(nèi)所有圖片面積總和之比( a k 文之后把這個(gè)比值簡(jiǎn)稱為畫布稠密 系數(shù)) 會(huì)升高，當(dāng)這個(gè)比值超過一個(gè)給定的閾值時(shí)( 例如0 7 5 ) ，那么系統(tǒng)認(rèn)為 畫布容納的圖片數(shù)目偏少，于是一個(gè)“p h o t oi n s e r t i o n 事件被觸發(fā)，一張新 圖片被插入畫布。在所有圖片的大小相差不多的情況下，系統(tǒng)總是可以將畫布稠 密系數(shù)保持在一個(gè)適當(dāng)?shù)暮侠硭?。在我們的?shí)際實(shí)現(xiàn)中，畫布稠密系數(shù)的值穩(wěn) 定在o 6 5 左右。 這里需要特別關(guān)注的是系統(tǒng)指定圖片生命時(shí)間的準(zhǔn)則。一個(gè)最簡(jiǎn)單的方式就 是對(duì)所有圖片指定一個(gè)統(tǒng)一的生命時(shí)間，然而這種方法不能反映圖片重要性的差 異。在本文中，系統(tǒng)采用用戶自定義的生命時(shí)間準(zhǔn)則，例如圖片大小( 大圖片擁 有更長(zhǎng)的生命時(shí)間) ，圖片內(nèi)容的豐富程度( 內(nèi)容豐富的圖片擁有更長(zhǎng)的生命時(shí) 間) ，等等。 浙江大學(xué)碩士學(xué)位論文第3 章動(dòng)態(tài)圖片拼接算法綜述 3 3 2 調(diào)度順序 當(dāng)“p h o t oi n s e r t i o n 事件被觸發(fā)之后，調(diào)度順序決定了應(yīng)該選擇哪一幅 圖片加入畫布。例如，可