基于CBIR的計(jì)算機(jī)拼圖系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

本文重點(diǎn)對(duì) CBIR軟件的系統(tǒng)框架和所用機(jī)器視覺技術(shù)進(jìn)行了闡述。該軟件經(jīng)過系統(tǒng)測(cè)試，能完成手工拼圖和12、48塊拼塊的自動(dòng)拼接。本文中介紹的技術(shù)方案，有可能應(yīng)用于破碎物品修復(fù)、考古瓷器碎片復(fù)原、碎紙屑拼接等領(lǐng)域。

1 引言

CBIR(Content Based Image Retieval)即基于內(nèi)容的圖像檢索是指直接根據(jù)圖像媒體對(duì)象內(nèi)容進(jìn)行的各種特征檢索，它能從圖像庫中直接找到具有指定特征或含有特定內(nèi)容的圖像[1]。

計(jì)算機(jī)自動(dòng)拼圖所涉及到的技術(shù)不僅可用于簡單的拼圖游戲，而且從深遠(yuǎn)層次講，還可以應(yīng)用到破碎物品的修復(fù)，考古瓷器碎片的復(fù)原，甚至在刑事破案中的碎紙屑拼接來提供有力證據(jù)等等。自上世紀(jì)60年代初，國外學(xué)術(shù)界對(duì)拼圖自動(dòng)拼接問題開展了大量科學(xué)研究[2 - 6]，然而先前的做法，主要是考慮到幾何形狀信息，沒有考慮到其它有用的信息，如顏色、紋理作為額外線索。鑒于這個(gè)事實(shí)，本文提出了一種新的拼圖求解器，其中用到顏色、紋理以及部分邊界信息。把CBIR的理論直接應(yīng)用到計(jì)算機(jī)拼圖系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)中，可以在無人工參與的條件下完成各小圖塊的拼接。重點(diǎn)闡述了計(jì)算機(jī)拼圖游戲系統(tǒng)的架構(gòu)和如何應(yīng)用具體的機(jī)器視覺技術(shù)，并詳細(xì)介紹了作者開發(fā)的計(jì)算機(jī)拼圖游戲系統(tǒng)應(yīng)用軟件。

2 CBIR系統(tǒng)簡介

典型的CBIR系統(tǒng)的框架如圖1所示，用戶通過人機(jī)交互界面選擇某幅圖像，然后提出感興趣目標(biāo)的幾何形狀或所需圖像背景顏色等發(fā)出查詢請(qǐng)求，系統(tǒng)將查詢要求提取輸入圖像的特征向量，再借助這些特征向量與特征庫中信息進(jìn)行匹配，提取出相似度高的圖像數(shù)據(jù)顯示給用戶，用戶對(duì)此驗(yàn)證后可直接使用或借以改進(jìn)查詢條件并開始新一輪檢索。

3 計(jì)算機(jī)拼圖游戲系統(tǒng)設(shè)計(jì)

計(jì)算機(jī)拼圖游戲系統(tǒng)是基于CBIR系統(tǒng)框架的，但鑒于系統(tǒng)處理對(duì)象即拼塊數(shù)量有限，并不存在特征庫，故不預(yù)先計(jì)算圖像庫中圖像的某種特征存入庫中，并且把特征提取模塊與檢索匹配模塊集成到統(tǒng)一檢索算法模塊DLL中，可以稱之為簡化的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)過面向?qū)ο蠓治雠c設(shè)計(jì)階段形成的主要實(shí)體類、邊界類和控制類表示。系統(tǒng)的關(guān)鍵為游戲控制類CJigsawGameControl，它一對(duì)多組合了拼塊CPiece類，并且一對(duì)一關(guān)聯(lián)了算法決策類CDecisionMaker、計(jì)時(shí)器類CTimer、封裝DirectSound的聲效播放器類CSpeaker。CPiece拼塊類的圖像顯示旋轉(zhuǎn)等操作是由其內(nèi)部關(guān)聯(lián)的CJigsawBitmap類完成的，CJigsawBitmap是基于GDI+ Bitmap的適配器。用于自動(dòng)拼接的CDecisionMaker算法決策類關(guān)聯(lián)了分別用于顏色、紋理和形狀算法接口類，封裝了初始化算法庫、算法權(quán)重設(shè)置、核心控制各算法搜索策略等方法。以顏色算法類CColorArthmetic類為例，由它派生出基于顏色直方圖相交法的CCHistorimArthmetic類和基于顏色累積直方圖相交法的CAgrHistorimArthmetic類，而它們的具體實(shí)現(xiàn)在相應(yīng)的動(dòng)態(tài)鏈接庫中，由動(dòng)態(tài)鏈接庫加載器類CDllLoader類完成動(dòng)態(tài)加載。

3.2.1 所用設(shè)計(jì)模式

模式，即在某一個(gè)情景下的問題解決方案。軟件設(shè)計(jì)模式，那些經(jīng)過前人總結(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è)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。使原本由于接口不兼容而不能一起工作的那些類可以一起工作[7]。對(duì)于拼塊CPiece類要求的拼塊圖像操作已經(jīng)被GDI+ Bitmap類完全實(shí)現(xiàn)，但CPiece類需要不同的方法名稱和參數(shù)列表，并且也不需要GDI+ Bitmap類的全部功能。故我們加入了CJigsawBitmap適配器類，CJigsawBitmap類包含GDI+ Bitmap類，并且把收到的請(qǐng)求轉(zhuǎn)發(fā)給內(nèi)部的GDI+ Bitmap類對(duì)象。

2)Singleton模式在系統(tǒng)中的應(yīng)用

在本系統(tǒng)中有且僅有一個(gè)游戲控制類CJigsawGame Control實(shí)例，并且為了滿足面向?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è)封裝起來，并且使它們可相互替換[7]。這點(diǎn)正好符合我們系統(tǒng)的定位，即為教育演示系統(tǒng)，針對(duì)每一種特征提取匹配會(huì)有多種的算法方案。我們?cè)贑DecisionMaker中包含顏色算法抽象基類CColorArthmetic、紋理算法抽象基類CTextureArthmetic和形狀算法抽象基類CShapeArthmetic。每個(gè)抽象類中都有一個(gè)抽象方法指定如何調(diào)用算法。每個(gè)派生類根據(jù)自身算法特點(diǎn)來實(shí)現(xiàn)這個(gè)抽象方法。

如CCHistorimArthmetic類使用基于顏色直方圖相交法實(shí)現(xiàn)MatchbyColor，而MatchbyColor在CAgrHistorimArthmetic類中使用基于顏色累積直方圖相交法。

3.2.2 各主要模塊設(shè)計(jì)

1)手工拼接

跟傳統(tǒng)電子拼圖游戲類似我們把每一個(gè)拼塊實(shí)現(xiàn)編號(hào)，從1，2，3，… …到N記數(shù)。對(duì)每一個(gè)拼塊CPiece類除了記錄本身ID，還記錄上、下、左、右四方向鄰居拼塊的編號(hào)，如果沒有鄰居拼塊簡單賦值為0即可。用于判斷在游戲中兩拼塊是否鄰接來觸發(fā)自動(dòng)磁性粘貼功能。手工拼接模塊主要涉及人機(jī)交互方面，即玩家可以通過系統(tǒng)標(biāo)準(zhǔn)輸入設(shè)備鼠標(biāo)來實(shí)現(xiàn)拼塊的拖拽移動(dòng)和放下來完成拼圖。其中最重要的是文檔視圖結(jié)構(gòu)中視圖類的用于鼠標(biāo)消息響應(yīng)的OnLButtonDown、OnLButtonUp和OnMouseMove三個(gè)方法。

OnLButtonDown方法中遍歷各個(gè)拼塊，如果鼠標(biāo)指針位置在某個(gè)拼塊外圍盒中，則說明玩家選中該拼塊，記錄拼塊編號(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)拼接

通過UI由用戶根據(jù)待拼接圖像特點(diǎn)來選擇使用單一顏色、單一紋理或單一形狀算法以及它們的組合。例如對(duì)于一張灰度圖像，用戶會(huì)選擇基于紋理和形狀特征，而不會(huì)采用顏色特征來完成拼塊自動(dòng)匹配拼接。更進(jìn)一步來講，用戶還可以具體到選擇使用何種顏色、形狀、紋理算法來比較和評(píng)價(jià)檢索算法。

系統(tǒng)所用的每種算法都被包裝成一個(gè)動(dòng)態(tài)鏈接庫(DLL)，平臺(tái)對(duì)這些DLL是采用動(dòng)態(tài)載入的方式調(diào)用的。這些DLL要求有統(tǒng)一的導(dǎo)出函數(shù)聲明，即名稱和參數(shù)列表。這樣，我們調(diào)用每種算法時(shí)只需要提供通用的一些參數(shù)，如圖像位圖文件全路徑，而算法程序也就是根據(jù)這些位圖數(shù)據(jù)計(jì)算出檢索所需要的特征和特征間相似距離再予以返回。在本系統(tǒng)中正是由CDllLoader的LoadLibraryAPI(LPCTSTR lpszDllName，LPCTSTR lpszModuleName，F(xiàn)ARPROC *exportedfunc)來加載名為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是一種符合人的視覺習(xí)慣的一種彩色模型。

首先從RGB到HSV的轉(zhuǎn)化公式[8]。

然后，將HSV三個(gè)分量進(jìn)行量化用于對(duì)直方圖的匹配。在匹配方法上采用了直方圖相交距離的方法進(jìn)行了圖像的匹配。設(shè)HQ和HD分別為選中拼塊圖像Q和其它拼塊圖像D的HSV統(tǒng)計(jì)直方圖，則兩圖之間的匹配值可以借助直方圖相交法來計(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)為教育演示軟件，故用戶可以自由選擇采用何種特征進(jìn)行自動(dòng)拼接，以及各特征權(quán)重的設(shè)定，來觀察不同特征分析匹配針對(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ī)器視覺原理，利用功能強(qiáng)大的軟件開發(fā)環(huán)境Visual C++6.0和GDI+/DirectX庫開發(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é)束語

以上闡述了計(jì)算機(jī)拼圖游戲系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。該系統(tǒng)作為一款計(jì)算機(jī)游戲，其采用媒體渲染效果強(qiáng)大的DirectX庫和MFC類庫，具有界面美觀，人機(jī)交互性強(qiáng)的特點(diǎn)。同時(shí)其本質(zhì)又是基于內(nèi)容的圖像檢索系統(tǒng)，該系統(tǒng)采用顏色、紋理以及部分邊界信息成功完成了12、48塊拼塊的自動(dòng)拼接。該系統(tǒng)不僅可以使游戲者帶來成功的喜悅，而且還可以向游戲者演示人工智能中計(jì)算機(jī)視覺的基本原理和操作過程，為啟發(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)容的視覺信息檢索[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è)頻道