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

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

1 引言

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

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

2 CBIR系統(tǒng)簡介

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

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

計算機拼圖游戲系統(tǒng)是基于CBIR系統(tǒng)框架的，但鑒于系統(tǒng)處理對象即拼塊數(shù)量有限，并不存在特征庫，故不預(yù)先計算圖像庫中圖像的某種特征存入庫中，并且把特征提取模塊與檢索匹配模塊集成到統(tǒng)一檢索算法模塊DLL中，可以稱之為簡化的CBIR系統(tǒng)。其系統(tǒng)結(jié)構(gòu)圖如圖2所示。

3.1 功能

計算機拼圖游戲系統(tǒng)主要由手工拼圖、自動拼圖和項目選擇三大功能。3.2 整體設(shè)計

本系統(tǒng)采用面向?qū)ο蠹夹g(shù)實現(xiàn)上圖的三大功能。經(jīng)過面向?qū)ο蠓治雠c設(shè)計階段形成的主要實體類、邊界類和控制類表示。系統(tǒng)的關(guān)鍵為游戲控制類CJigsawGameControl，它一對多組合了拼塊CPiece類，并且一對一關(guān)聯(lián)了算法決策類CDecisionMaker、計時器類CTimer、封裝DirectSound的聲效播放器類CSpeaker。CPiece拼塊類的圖像顯示旋轉(zhuǎn)等操作是由其內(nèi)部關(guān)聯(lián)的CJigsawBitmap類完成的，CJigsawBitmap是基于GDI+ Bitmap的適配器。用于自動拼接的CDecisionMaker算法決策類關(guān)聯(lián)了分別用于顏色、紋理和形狀算法接口類，封裝了初始化算法庫、算法權(quán)重設(shè)置、核心控制各算法搜索策略等方法。以顏色算法類CColorArthmetic類為例，由它派生出基于顏色直方圖相交法的CCHistorimArthmetic類和基于顏色累積直方圖相交法的CAgrHistorimArthmetic類，而它們的具體實現(xiàn)在相應(yīng)的動態(tài)鏈接庫中，由動態(tài)鏈接庫加載器類CDllLoader類完成動態(tài)加載。

3.2.1 所用設(shè)計模式

模式，即在某一個情景下的問題解決方案。軟件設(shè)計模式，那些經(jīng)過前人總結(jié)和時間考驗的解決方案為我們創(chuàng)建可復(fù)用的、高質(zhì)量的軟件和改善代碼的可修改性使之更容易處理變化奠定了堅實的基礎(chǔ)。針對本系統(tǒng)的不同應(yīng)用場景和意圖，我們主要采用了Adapter、Singleton、Stragy三種模式。

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

Adapter模式的意圖是：將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口。使原本由于接口不兼容而不能一起工作的那些類可以一起工作[7]。對于拼塊CPiece類要求的拼塊圖像操作已經(jīng)被GDI+ Bitmap類完全實現(xiàn)，但CPiece類需要不同的方法名稱和參數(shù)列表，并且也不需要GDI+ Bitmap類的全部功能。故我們加入了CJigsawBitmap適配器類，CJigsawBitmap類包含GDI+ Bitmap類，并且把收到的請求轉(zhuǎn)發(fā)給內(nèi)部的GDI+ Bitmap類對象。

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

在本系統(tǒng)中有且僅有一個游戲控制類CJigsawGame Control實例，并且為了滿足面向?qū)ο蠹夹g(shù)要求消除全局變量的準(zhǔn)則，我們選用了單件模式。CJigsawGameControl的公有靜態(tài)方法GetGameControl會檢查對象是否已經(jīng)被實例化。如果對象已經(jīng)被實例化，僅僅返回一個指向這個對象的指針，否則先對象實例化再返回新對象的地址。

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

Strategy模式的意圖是：定義一系列的算法，把它們一個個封裝起來，并且使它們可相互替換[7]。這點正好符合我們系統(tǒng)的定位，即為教育演示系統(tǒng)，針對每一種特征提取匹配會有多種的算法方案。我們在CDecisionMaker中包含顏色算法抽象基類CColorArthmetic、紋理算法抽象基類CTextureArthmetic和形狀算法抽象基類CShapeArthmetic。每個抽象類中都有一個抽象方法指定如何調(diào)用算法。每個派生類根據(jù)自身算法特點來實現(xiàn)這個抽象方法。

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

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

1)手工拼接

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

OnLButtonDown方法中遍歷各個拼塊，如果鼠標(biāo)指針位置在某個拼塊外圍盒中，則說明玩家選中該拼塊，記錄拼塊編號和鼠標(biāo)指針位置(X1，Y1)與拼塊外圍盒左上角坐標(biāo)(X2，Y2)之差，用于移動拼塊。

OnMouseMove方法中實時更新選中拼塊外圍盒左上角坐標(biāo)。

OnLButtonUp方法中遍歷除已選拼塊外其余拼塊，分別判斷是否是已選拼塊的頂端、左端、底端和右端拼塊，如果是調(diào)整選中拼塊外圍盒左上角坐標(biāo)。最后根據(jù)各拼塊外圍盒左上角坐標(biāo)和寬高信息重新繪制視圖中所有拼塊。

2)自動拼接

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

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

4 關(guān)鍵技術(shù)與實現(xiàn) 4.1 顏色、紋理、紋理特征分析算法

1)顏色特征分析算法

本系統(tǒng)使用了顏色直方圖的方法進行了顏色的提取，首先得到圖像的RGB三個通道的直方圖，然后將其轉(zhuǎn)換為HSV分量，因為HSV是一種符合人的視覺習(xí)慣的一種彩色模型。

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

然后，將HSV三個分量進行量化用于對直方圖的匹配。在匹配方法上采用了直方圖相交距離的方法進行了圖像的匹配。設(shè)HQ和HD分別為選中拼塊圖像Q和其它拼塊圖像D的HSV統(tǒng)計直方圖，則兩圖之間的匹配值可以借助直方圖相交法來計算。

2)紋理特征分析算法

本系統(tǒng)首先利用二維傅里葉變換F(u，v) 將圖像變換到頻域。二維傅里葉變換后的頻譜能描述紋理的粗糙度和方向性[9]。

然后將(u，v ) 直角坐標(biāo)系轉(zhuǎn)換成(r，φ)極坐標(biāo)系，其中r是以原點為中心的圓周半徑，φ是極位角，這時計算各圖塊的粗糙度。取r=0，4，8，12，16...24共七個半徑值，計算各幅圖七個圓環(huán)的功率譜。在內(nèi)徑為r1，外徑為r2的圓環(huán)上的功率譜為：

P(r1，r2)揭示了不同頻率分量的能量分布信息，在紋理較粗的情況下，若r較小，P(r)很大，r很大時，P(r)反而較??；而在紋理較細(xì)的情況下，r變化對P(r)的影響不是很大。

再計算各圖塊紋理的分布方向性。取6個角度，計算各幅圖的6個扇形的功率譜。計算扇形區(qū)域內(nèi)的功率譜P (φ1，φ2):

其中φ1和φ2是規(guī)定扇形區(qū)范圍的兩個角度。

在匹配方法上采用歐式距離的方法進行匹配。則兩圖之間的匹配值可以計算圖像間對應(yīng)的圓環(huán)功率譜的歐式距離，計算圖像間對應(yīng)扇形功率譜的歐式距離，再進行相加，計算公式如下。

3)形狀特征分析算法

由于系統(tǒng)中采用標(biāo)準(zhǔn)拼塊形狀，如圖4所示，左上、左下、右上、右下四角點均成九十度，故采用空間模板匹配的方法即可獲得角點坐標(biāo)位置。

首先將拼圖圖像進行二值化處理，然后從左上角點作為跟蹤的起始點，采用8鄰域搜索的邊緣跟蹤算法[10]，得到上下左右四邊的鏈碼序列。而兩拼塊在位置上相鄰的原則就是其相鄰邊的鏈碼匹配相等，但實際由于誤差的引入，即使兩邊相鄰，也不可能兩邊鏈碼完全相等，但至少在與其它拼塊邊鏈碼差異上達到最小。這里需要注意的是，假定有兩個邊鏈碼A和B，需要先對A和B進行反方向編碼，即一個按順時針編碼，一個按逆時針編碼，但8鄰域搜索的準(zhǔn)則是按逆時針編碼。需要我們對A或B中的某一邊鏈碼取逆后再匹配，即對于鏈碼的每一個碼值加4后除以8的余數(shù)賦給原碼值。

4.2　核心控制

由于本系統(tǒng)為教育演示軟件，故用戶可以自由選擇采用何種特征進行自動拼接，以及各特征權(quán)重的設(shè)定，來觀察不同特征分析匹配針對不同特點的拼塊圖像的結(jié)果。如果采用顏色、紋理、形狀特征分析進行自動拼接，其流程圖如圖5所示，其中diff表示兩邊鏈碼差異，min記錄兩邊鏈碼差異的最小值。

5 系統(tǒng)測試

在Windows XP系統(tǒng)下，采用面向?qū)ο蟮募夹g(shù)和相關(guān)機器視覺原理，利用功能強大的軟件開發(fā)環(huán)境Visual C++6.0和GDI+/DirectX庫開發(fā)了計算機拼圖游戲系統(tǒng)。該軟件經(jīng)測試，系統(tǒng)已完成圖3所示的各項功能性需求。系統(tǒng)可根據(jù)顏色和形狀分析算法，成功地完成了12塊拼塊的拼接。另外，系統(tǒng)由于采用了算法Dll動態(tài)載入的方式，達到了系統(tǒng)平臺代碼和算法實現(xiàn)的獨立性，為日后維護和升級平臺系統(tǒng)和添加驗證新的算法提供了方便。

6 結(jié)束語

以上闡述了計算機拼圖游戲系統(tǒng)的設(shè)計與實現(xiàn)。該系統(tǒng)作為一款計算機游戲，其采用媒體渲染效果強大的DirectX庫和MFC類庫，具有界面美觀，人機交互性強的特點。同時其本質(zhì)又是基于內(nèi)容的圖像檢索系統(tǒng)，該系統(tǒng)采用顏色、紋理以及部分邊界信息成功完成了12、48塊拼塊的自動拼接。該系統(tǒng)不僅可以使游戲者帶來成功的喜悅，而且還可以向游戲者演示人工智能中計算機視覺的基本原理和操作過程，為啟發(fā)中學(xué)生的科研意識和創(chuàng)新意識起到積極作用。從深遠層次角度考慮，如果系統(tǒng)處理對象的不同，本文介紹的技術(shù)方案，有可能應(yīng)用于破碎物品修復(fù)、考古瓷器碎片復(fù)原、碎紙屑拼接等領(lǐng)域，具有廣泛的市場前景。但由于采用算法的精確度所至，對于處理大規(guī)模數(shù)量的拼塊或者更為復(fù)雜的拼塊形狀，系統(tǒng)還將在系統(tǒng)的精確性、靈活性方面加以改進，以提高其運行性能。

參考文獻

[1] 王海龍，王佩雪.基于內(nèi)容的圖像檢索探討[J].中原工學(xué)院學(xué)報，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è)計模式:可復(fù)用面向?qū)ο筌浖幕A(chǔ)[M].李英軍譯.北京: 機械工業(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

更多計算機與外設(shè)信息請關(guān)注：21ic計算機與外設(shè)頻道