基于CBIR的計(jì)算機(jī)拼圖系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
本文重點(diǎn)對(duì) CBIR軟件的系統(tǒng)框架和所用機(jī)器視覺(jué)技術(shù)進(jìn)行了闡述。該軟件經(jīng)過(guò)系統(tǒng)測(cè)試,能完成手工拼圖和12、48塊拼塊的自動(dòng)拼接。本文中介紹的技術(shù)方案,有可能應(yīng)用于破碎物品修復(fù)、考古瓷器碎片復(fù)原、碎紙屑拼接等領(lǐng)域。
本文引用地址:http://m.butianyuan.cn/article/202326.htm1 引言
CBIR(Content Based Image Retieval)即基于內(nèi)容的圖像檢索是指直接根據(jù)圖像媒體對(duì)象內(nèi)容進(jìn)行的各種特征檢索,它能從圖像庫(kù)中直接找到具有指定特征或含有特定內(nèi)容的圖像[1]。
計(jì)算機(jī)自動(dòng)拼圖所涉及到的技術(shù)不僅可用于簡(jiǎn)單的拼圖游戲,而且從深遠(yuǎn)層次講,還可以應(yīng)用到破碎物品的修復(fù),考古瓷器碎片的復(fù)原,甚至在刑事破案中的碎紙屑拼接來(lái)提供有力證據(jù)等等。自上世紀(jì)60年代初,國(guó)外學(xué)術(shù)界對(duì)拼圖自動(dòng)拼接問(wèn)題開(kāi)展了大量科學(xué)研究[2 - 6],然而先前的做法,主要是考慮到幾何形狀信息,沒(méi)有考慮到其它有用的信息,如顏色、紋理作為額外線索。鑒于這個(gè)事實(shí),本文提出了一種新的拼圖求解器,其中用到顏色、紋理以及部分邊界信息。把CBIR的理論直接應(yīng)用到計(jì)算機(jī)拼圖系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)中,可以在無(wú)人工參與的條件下完成各小圖塊的拼接。重點(diǎn)闡述了計(jì)算機(jī)拼圖游戲系統(tǒng)的架構(gòu)和如何應(yīng)用具體的機(jī)器視覺(jué)技術(shù),并詳細(xì)介紹了作者開(kāi)發(fā)的計(jì)算機(jī)拼圖游戲系統(tǒng)應(yīng)用軟件。
2 CBIR系統(tǒng)簡(jiǎn)介
典型的CBIR系統(tǒng)的框架如圖1所示,用戶(hù)通過(guò)人機(jī)交互界面選擇某幅圖像,然后提出感興趣目標(biāo)的幾何形狀或所需圖像背景顏色等發(fā)出查詢(xún)請(qǐng)求,系統(tǒng)將查詢(xún)要求提取輸入圖像的特征向量,再借助這些特征向量與特征庫(kù)中信息進(jìn)行匹配,提取出相似度高的圖像數(shù)據(jù)顯示給用戶(hù),用戶(hù)對(duì)此驗(yàn)證后可直接使用或借以改進(jìn)查詢(xún)條件并開(kāi)始新一輪檢索。
3 計(jì)算機(jī)拼圖游戲系統(tǒng)設(shè)計(jì)
計(jì)算機(jī)拼圖游戲系統(tǒng)是基于CBIR系統(tǒng)框架的,但鑒于系統(tǒng)處理對(duì)象即拼塊數(shù)量有限,并不存在特征庫(kù),故不預(yù)先計(jì)算圖像庫(kù)中圖像的某種特征存入庫(kù)中,并且把特征提取模塊與檢索匹配模塊集成到統(tǒng)一檢索算法模塊DLL中,可以稱(chēng)之為簡(jiǎn)化的CBIR系統(tǒng)。其系統(tǒng)結(jié)構(gòu)圖如圖2所示。
3.1 功能
計(jì)算機(jī)拼圖游戲系統(tǒng)主要由手工拼圖、自動(dòng)拼圖和項(xiàng)目選擇三大功能。3.2 整體設(shè)計(jì)
本系統(tǒng)采用面向?qū)ο蠹夹g(shù)實(shí)現(xiàn)上圖的三大功能。經(jīng)過(guò)面向?qū)ο蠓治雠c設(shè)計(jì)階段形成的主要實(shí)體類(lèi)、邊界類(lèi)和控制類(lèi)表示。系統(tǒng)的關(guān)鍵為游戲控制類(lèi)CJigsawGameControl,它一對(duì)多組合了拼塊CPiece類(lèi),并且一對(duì)一關(guān)聯(lián)了算法決策類(lèi)CDecisionMaker、計(jì)時(shí)器類(lèi)CTimer、封裝DirectSound的聲效播放器類(lèi)CSpeaker。CPiece拼塊類(lèi)的圖像顯示旋轉(zhuǎn)等操作是由其內(nèi)部關(guān)聯(lián)的CJigsawBitmap類(lèi)完成的,CJigsawBitmap是基于GDI+ Bitmap的適配器。用于自動(dòng)拼接的CDecisionMaker算法決策類(lèi)關(guān)聯(lián)了分別用于顏色、紋理和形狀算法接口類(lèi),封裝了初始化算法庫(kù)、算法權(quán)重設(shè)置、核心控制各算法搜索策略等方法。以顏色算法類(lèi)CColorArthmetic類(lèi)為例,由它派生出基于顏色直方圖相交法的CCHistorimArthmetic類(lèi)和基于顏色累積直方圖相交法的CAgrHistorimArthmetic類(lèi),而它們的具體實(shí)現(xiàn)在相應(yīng)的動(dòng)態(tài)鏈接庫(kù)中,由動(dòng)態(tài)鏈接庫(kù)加載器類(lèi)CDllLoader類(lèi)完成動(dòng)態(tài)加載。
3.2.1 所用設(shè)計(jì)模式
模式,即在某一個(gè)情景下的問(wèn)題解決方案。軟件設(shè)計(jì)模式,那些經(jīng)過(guò)前人總結(jié)和時(shí)間考驗(yàn)的解決方案為我們創(chuàng)建可復(fù)用的、高質(zhì)量的軟件和改善代碼的可修改性使之更容易處理變化奠定了堅(jiān)實(shí)的基礎(chǔ)。針對(duì)本系統(tǒng)的不同應(yīng)用場(chǎng)景和意圖,我們主要采用了Adapter、Singleton、Stragy三種模式。
1)Adapter模式在系統(tǒng)中的應(yīng)用
Adapter模式的意圖是:將一個(gè)類(lèi)的接口轉(zhuǎn)換成客戶(hù)希望的另外一個(gè)接口。使原本由于接口不兼容而不能一起工作的那些類(lèi)可以一起工作[7]。對(duì)于拼塊CPiece類(lèi)要求的拼塊圖像操作已經(jīng)被GDI+ Bitmap類(lèi)完全實(shí)現(xiàn),但CPiece類(lèi)需要不同的方法名稱(chēng)和參數(shù)列表,并且也不需要GDI+ Bitmap類(lèi)的全部功能。故我們加入了CJigsawBitmap適配器類(lèi),CJigsawBitmap類(lèi)包含GDI+ Bitmap類(lèi),并且把收到的請(qǐng)求轉(zhuǎn)發(fā)給內(nèi)部的GDI+ Bitmap類(lèi)對(duì)象。
2)Singleton模式在系統(tǒng)中的應(yīng)用
在本系統(tǒng)中有且僅有一個(gè)游戲控制類(lèi)CJigsawGame Control實(shí)例,并且為了滿(mǎn)足面向?qū)ο蠹夹g(shù)要求消除全局變量的準(zhǔn)則,我們選用了單件模式。CJigsawGameControl的公有靜態(tài)方法GetGameControl會(huì)檢查對(duì)象是否已經(jīng)被實(shí)例化。如果對(duì)象已經(jīng)被實(shí)例化,僅僅返回一個(gè)指向這個(gè)對(duì)象的指針,否則先對(duì)象實(shí)例化再返回新對(duì)象的地址。
3)Strategy模式在系統(tǒng)中的應(yīng)用
Strategy模式的意圖是:定義一系列的算法,把它們一個(gè)個(gè)封裝起來(lái),并且使它們可相互替換[7]。這點(diǎn)正好符合我們系統(tǒng)的定位,即為教育演示系統(tǒng),針對(duì)每一種特征提取匹配會(huì)有多種的算法方案。我們?cè)贑DecisionMaker中包含顏色算法抽象基類(lèi)CColorArthmetic、紋理算法抽象基類(lèi)CTextureArthmetic和形狀算法抽象基類(lèi)CShapeArthmetic。每個(gè)抽象類(lèi)中都有一個(gè)抽象方法指定如何調(diào)用算法。每個(gè)派生類(lèi)根據(jù)自身算法特點(diǎn)來(lái)實(shí)現(xiàn)這個(gè)抽象方法。
如CCHistorimArthmetic類(lèi)使用基于顏色直方圖相交法實(shí)現(xiàn)MatchbyColor,而MatchbyColor在CAgrHistorimArthmetic類(lèi)中使用基于顏色累積直方圖相交法。
3.2.2 各主要模塊設(shè)計(jì)
1)手工拼接
跟傳統(tǒng)電子拼圖游戲類(lèi)似我們把每一個(gè)拼塊實(shí)現(xiàn)編號(hào),從1,2,3,… …到N記數(shù)。對(duì)每一個(gè)拼塊CPiece類(lèi)除了記錄本身ID,還記錄上、下、左、右四方向鄰居拼塊的編號(hào),如果沒(méi)有鄰居拼塊簡(jiǎn)單賦值為0即可。用于判斷在游戲中兩拼塊是否鄰接來(lái)觸發(fā)自動(dòng)磁性粘貼功能。手工拼接模塊主要涉及人機(jī)交互方面,即玩家可以通過(guò)系統(tǒng)標(biāo)準(zhǔn)輸入設(shè)備鼠標(biāo)來(lái)實(shí)現(xiàn)拼塊的拖拽移動(dòng)和放下來(lái)完成拼圖。其中最重要的是文檔視圖結(jié)構(gòu)中視圖類(lèi)的用于鼠標(biāo)消息響應(yīng)的OnLButtonDown、OnLButtonUp和OnMouseMove三個(gè)方法。
OnLButtonDown方法中遍歷各個(gè)拼塊,如果鼠標(biāo)指針位置在某個(gè)拼塊外圍盒中,則說(shuō)明玩家選中該拼塊,記錄拼塊編號(hào)和鼠標(biāo)指針位置(X1,Y1)與拼塊外圍盒左上角坐標(biāo)(X2,Y2)之差,用于移動(dòng)拼塊。
OnMouseMove方法中實(shí)時(shí)更新選中拼塊外圍盒左上角坐標(biāo)。
OnLButtonUp方法中遍歷除已選拼塊外其余拼塊,分別判斷是否是已選拼塊的頂端、左端、底端和右端拼塊,如果是調(diào)整選中拼塊外圍盒左上角坐標(biāo)。最后根據(jù)各拼塊外圍盒左上角坐標(biāo)和寬高信息重新繪制視圖中所有拼塊。
2)自動(dòng)拼接
通過(guò)UI由用戶(hù)根據(jù)待拼接圖像特點(diǎn)來(lái)選擇使用單一顏色、單一紋理或單一形狀算法以及它們的組合。例如對(duì)于一張灰度圖像,用戶(hù)會(huì)選擇基于紋理和形狀特征,而不會(huì)采用顏色特征來(lái)完成拼塊自動(dòng)匹配拼接。更進(jìn)一步來(lái)講,用戶(hù)還可以具體到選擇使用何種顏色、形狀、紋理算法來(lái)比較和評(píng)價(jià)檢索算法。
系統(tǒng)所用的每種算法都被包裝成一個(gè)動(dòng)態(tài)鏈接庫(kù)(DLL),平臺(tái)對(duì)這些DLL是采用動(dòng)態(tài)載入的方式調(diào)用的。這些DLL要求有統(tǒng)一的導(dǎo)出函數(shù)聲明,即名稱(chēng)和參數(shù)列表。這樣,我們調(diào)用每種算法時(shí)只需要提供通用的一些參數(shù),如圖像位圖文件全路徑,而算法程序也就是根據(jù)這些位圖數(shù)據(jù)計(jì)算出檢索所需要的特征和特征間相似距離再予以返回。在本系統(tǒng)中正是由CDllLoader的LoadLibraryAPI(LPCTSTR lpszDllName,LPCTSTR lpszModuleName,F(xiàn)ARPROC *exportedfunc)來(lái)加載名為lpszDllNameDLL文件中名為lpszModuleName的算法函數(shù)。
4 關(guān)鍵技術(shù)與實(shí)現(xiàn) 4.1 顏色、紋理、紋理特征分析算法
1)顏色特征分析算法
本系統(tǒng)使用了顏色直方圖的方法進(jìn)行了顏色的提取,首先得到圖像的RGB三個(gè)通道的直方圖,然后將其轉(zhuǎn)換為HSV分量,因?yàn)镠SV是一種符合人的視覺(jué)習(xí)慣的一種彩色模型。
首先從RGB到HSV的轉(zhuǎn)化公式[8]。
然后,將HSV三個(gè)分量進(jìn)行量化用于對(duì)直方圖的匹配。在匹配方法上采用了直方圖相交距離的方法進(jìn)行了圖像的匹配。設(shè)HQ和HD分別為選中拼塊圖像Q和其它拼塊圖像D的HSV統(tǒng)計(jì)直方圖,則兩圖之間的匹配值可以借助直方圖相交法來(lái)計(jì)算。
2)紋理特征分析算法
本系統(tǒng)首先利用二維傅里葉變換F(u,v) 將圖像變換到頻域。二維傅里葉變換后的頻譜能描述紋理的粗糙度和方向性[9]。
然后將(u,v ) 直角坐標(biāo)系轉(zhuǎn)換成(r,φ)極坐標(biāo)系,其中r是以原點(diǎn)為中心的圓周半徑,φ是極位角,這時(shí)計(jì)算各圖塊的粗糙度。取r=0,4,8,12,16...24共七個(gè)半徑值,計(jì)算各幅圖七個(gè)圓環(huán)的功率譜。在內(nèi)徑為r1,外徑為r2的圓環(huán)上的功率譜為:
P(r1,r2)揭示了不同頻率分量的能量分布信息,在紋理較粗的情況下,若r較小,P(r)很大,r很大時(shí),P(r)反而較??;而在紋理較細(xì)的情況下,r變化對(duì)P(r)的影響不是很大。
再計(jì)算各圖塊紋理的分布方向性。取6個(gè)角度,計(jì)算各幅圖的6個(gè)扇形的功率譜。計(jì)算扇形區(qū)域內(nèi)的功率譜P (φ1,φ2):
其中φ1和φ2是規(guī)定扇形區(qū)范圍的兩個(gè)角度。
在匹配方法上采用歐式距離的方法進(jìn)行匹配。則兩圖之間的匹配值可以計(jì)算圖像間對(duì)應(yīng)的圓環(huán)功率譜的歐式距離,計(jì)算圖像間對(duì)應(yīng)扇形功率譜的歐式距離,再進(jìn)行相加,計(jì)算公式如下。
3)形狀特征分析算法
由于系統(tǒng)中采用標(biāo)準(zhǔn)拼塊形狀,如圖4所示,左上、左下、右上、右下四角點(diǎn)均成九十度,故采用空間模板匹配的方法即可獲得角點(diǎn)坐標(biāo)位置。
首先將拼圖圖像進(jìn)行二值化處理,然后從左上角點(diǎn)作為跟蹤的起始點(diǎn),采用8鄰域搜索的邊緣跟蹤算法[10],得到上下左右四邊的鏈碼序列。而兩拼塊在位置上相鄰的原則就是其相鄰邊的鏈碼匹配相等,但實(shí)際由于誤差的引入,即使兩邊相鄰,也不可能兩邊鏈碼完全相等,但至少在與其它拼塊邊鏈碼差異上達(dá)到最小。這里需要注意的是,假定有兩個(gè)邊鏈碼A和B,需要先對(duì)A和B進(jìn)行反方向編碼,即一個(gè)按順時(shí)針編碼,一個(gè)按逆時(shí)針編碼,但8鄰域搜索的準(zhǔn)則是按逆時(shí)針編碼。需要我們對(duì)A或B中的某一邊鏈碼取逆后再匹配,即對(duì)于鏈碼的每一個(gè)碼值加4后除以8的余數(shù)賦給原碼值。
4.2 核心控制
由于本系統(tǒng)為教育演示軟件,故用戶(hù)可以自由選擇采用何種特征進(jìn)行自動(dòng)拼接,以及各特征權(quán)重的設(shè)定,來(lái)觀察不同特征分析匹配針對(duì)不同特點(diǎn)的拼塊圖像的結(jié)果。如果采用顏色、紋理、形狀特征分析進(jìn)行自動(dòng)拼接,其流程圖如圖5所示,其中diff表示兩邊鏈碼差異,min記錄兩邊鏈碼差異的最小值。
5 系統(tǒng)測(cè)試
在Windows XP系統(tǒng)下,采用面向?qū)ο蟮募夹g(shù)和相關(guān)機(jī)器視覺(jué)原理,利用功能強(qiáng)大的軟件開(kāi)發(fā)環(huán)境Visual C++6.0和GDI+/DirectX庫(kù)開(kāi)發(fā)了計(jì)算機(jī)拼圖游戲系統(tǒng)。該軟件經(jīng)測(cè)試,系統(tǒng)已完成圖3所示的各項(xiàng)功能性需求。系統(tǒng)可根據(jù)顏色和形狀分析算法,成功地完成了12塊拼塊的拼接。另外,系統(tǒng)由于采用了算法Dll動(dòng)態(tài)載入的方式,達(dá)到了系統(tǒng)平臺(tái)代碼和算法實(shí)現(xiàn)的獨(dú)立性,為日后維護(hù)和升級(jí)平臺(tái)系統(tǒng)和添加驗(yàn)證新的算法提供了方便。
6 結(jié)束語(yǔ)
以上闡述了計(jì)算機(jī)拼圖游戲系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。該系統(tǒng)作為一款計(jì)算機(jī)游戲,其采用媒體渲染效果強(qiáng)大的DirectX庫(kù)和MFC類(lèi)庫(kù),具有界面美觀,人機(jī)交互性強(qiáng)的特點(diǎn)。同時(shí)其本質(zhì)又是基于內(nèi)容的圖像檢索系統(tǒng),該系統(tǒng)采用顏色、紋理以及部分邊界信息成功完成了12、48塊拼塊的自動(dòng)拼接。該系統(tǒng)不僅可以使游戲者帶來(lái)成功的喜悅,而且還可以向游戲者演示人工智能中計(jì)算機(jī)視覺(jué)的基本原理和操作過(guò)程,為啟發(fā)中學(xué)生的科研意識(shí)和創(chuàng)新意識(shí)起到積極作用。從深遠(yuǎn)層次角度考慮,如果系統(tǒng)處理對(duì)象的不同,本文介紹的技術(shù)方案,有可能應(yīng)用于破碎物品修復(fù)、考古瓷器碎片復(fù)原、碎紙屑拼接等領(lǐng)域,具有廣泛的市場(chǎng)前景。但由于采用算法的精確度所至,對(duì)于處理大規(guī)模數(shù)量的拼塊或者更為復(fù)雜的拼塊形狀,系統(tǒng)還將在系統(tǒng)的精確性、靈活性方面加以改進(jìn),以提高其運(yùn)行性能。
參考文獻(xiàn)
[1] 王海龍,王佩雪.基于內(nèi)容的圖像檢索探討[J].中原工學(xué)院學(xué)報(bào),2005,16(2):1
[2] Altman,Tom.Solving the jigsaw puzzle problem inlinear time[J]. Applied Artificial Intelligence,1989,3:453-462
[3] Freeman,Herbert and L. Gardner.Apictorial jigsaw puzzles: the computer solution of a problem in pattern recognition[J].IEEE Transactions on Electronic Computers,1964,13:118-127
[4] Radack,Gerald M. and Norman I. Badler.Jigsaw puzzle matching using a boundary-centered polar encoding[J].Computer Graphics and Image Processing,1982,19:1-17
[5] Webster,Roger W,Paul S. LaFollette and Robert L. Stafford.Isthmus critical points for solving jigsaw puzzles in computer vision[J]. IEEE Transactions on Systems,Man and Cybernetics,1991,21:1271-1278
[6] Wolfson,H.,E. Schonberg,A. Kalvin and Y. Lamdan.Solving jigsaw puzzles by computer[J],Annals of O perations Research,1988,12:51-64
[7] Gamma,E.,Heml,R.,Johnson,R.,Vlissides,j.,著. 設(shè)計(jì)模式:可復(fù)用面向?qū)ο筌浖幕A(chǔ)[M].李英軍譯.北京: 機(jī)械工業(yè)出版社,2000:12-92
[8] 章毓晉.基于內(nèi)容的視覺(jué)信息檢索[M]. 第一版,北京:科學(xué)出版社,2003:62
[9] Haralick.R.M.statistical and structural approaches to texture[J].IEEE.2000,67(5):786-804
更多計(jì)算機(jī)與外設(shè)信息請(qǐng)關(guān)注:21ic計(jì)算機(jī)與外設(shè)頻道
評(píng)論