基于CBIR的计算机拼图系统的设计与实现

本文重点对 CBIR软件的系统框架和所用机器视觉技术进行了阐述。该软件经过系统测试，能完成手工拼图和12、48块拼块的自动拼接。本文中介绍的技术方案，有可能应用于破碎物品修复、考古瓷器碎片复原、碎纸屑拼接等领域。

1 引言

CBIR(Content Based Image Retieval)即基于内容的图像检索是指直接根据图像媒体对象内容进行的各种特征检索，它能从图像库中直接找到具有指定特征或含有特定内容的图像[1]。

计算机自动拼图所涉及到的技术不仅可用于简单的拼图游戏，而且从深远层次讲，还可以应用到破碎物品的修复，考古瓷器碎片的复原，甚至在刑事破案中的碎纸屑拼接来提供有力证据等等。自上世纪60年代初，国外学术界对拼图自动拼接问题开展了大量科学研究[2 - 6]，然而先前的做法，主要是考虑到几何形状信息，没有考虑到其它有用的信息，如颜色、纹理作为额外线索。鉴于这个事实，本文提出了一种新的拼图求解器，其中用到颜色、纹理以及部分边界信息。把CBIR的理论直接应用到计算机拼图系统的设计和实现中，可以在无人工参与的条件下完成各小图块的拼接。重点阐述了计算机拼图游戏系统的架构和如何应用具体的机器视觉技术，并详细介绍了作者开发的计算机拼图游戏系统应用软件。

2 CBIR系统简介

典型的CBIR系统的框架如图1所示，用户通过人机交互界面选择某幅图像，然后提出感兴趣目标的几何形状或所需图像背景颜色等发出查询请求，系统将查询要求提取输入图像的特征向量，再借助这些特征向量与特征库中信息进行匹配，提取出相似度高的图像数据显示给用户，用户对此验证后可直接使用或借以改进查询条件并开始新一轮检索。

3 计算机拼图游戏系统设计

计算机拼图游戏系统是基于CBIR系统框架的，但鉴于系统处理对象即拼块数量有限，并不存在特征库，故不预先计算图像库中图像的某种特征存入库中，并且把特征提取模块与检索匹配模块集成到统一检索算法模块DLL中，可以称之为简化的CBIR系统。其系统结构图如图2所示。

3.1 功能

计算机拼图游戏系统主要由手工拼图、自动拼图和项目选择三大功能。3.2 整体设计

本系统采用面向对象技术实现上图的三大功能。经过面向对象分析与设计阶段形成的主要实体类、边界类和控制类表示。系统的关键为游戏控制类CJigsawGameControl，它一对多组合了拼块CPiece类，并且一对一关联了算法决策类CDecisionMaker、计时器类CTimer、封装DirectSound的声效播放器类CSpeaker。CPiece拼块类的图像显示旋转等操作是由其内部关联的CJigsawBitmap类完成的，CJigsawBitmap是基于GDI+ Bitmap的适配器。用于自动拼接的CDecisionMaker算法决策类关联了分别用于颜色、纹理和形状算法接口类，封装了初始化算法库、算法权重设置、核心控制各算法搜索策略等方法。以颜色算法类CColorArthmetic类为例，由它派生出基于颜色直方图相交法的CCHistorimArthmetic类和基于颜色累积直方图相交法的CAgrHistorimArthmetic类，而它们的具体实现在相应的动态链接库中，由动态链接库加载器类CDllLoader类完成动态加载。

3.2.1 所用设计模式

模式，即在某一个情景下的问题解决方案。软件设计模式，那些经过前人总结和时间考验的解决方案为我们创建可复用的、高质量的软件和改善代码的可修改性使之更容易处理变化奠定了坚实的基础。针对本系统的不同应用场景和意图，我们主要采用了Adapter、Singleton、Stragy三种模式。

1)Adapter模式在系统中的应用

Adapter模式的意图是：将一个类的接口转换成客户希望的另外一个接口。使原本由于接口不兼容而不能一起工作的那些类可以一起工作[7]。对于拼块CPiece类要求的拼块图像操作已经被GDI+ Bitmap类完全实现，但CPiece类需要不同的方法名称和参数列表，并且也不需要GDI+ Bitmap类的全部功能。故我们加入了CJigsawBitmap适配器类，CJigsawBitmap类包含GDI+ Bitmap类，并且把收到的请求转发给内部的GDI+ Bitmap类对象。

2)Singleton模式在系统中的应用

在本系统中有且仅有一个游戏控制类CJigsawGame Control实例，并且为了满足面向对象技术要求消除全局变量的准则，我们选用了单件模式。CJigsawGameControl的公有静态方法GetGameControl会检查对象是否已经被实例化。如果对象已经被实例化，仅仅返回一个指向这个对象的指针，否则先对象实例化再返回新对象的地址。

3)Strategy模式在系统中的应用

Strategy模式的意图是：定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换[7]。这点正好符合我们系统的定位，即为教育演示系统，针对每一种特征提取匹配会有多种的算法方案。我们在CDecisionMaker中包含颜色算法抽象基类CColorArthmetic、纹理算法抽象基类CTextureArthmetic和形状算法抽象基类CShapeArthmetic。每个抽象类中都有一个抽象方法指定如何调用算法。每个派生类根据自身算法特点来实现这个抽象方法。

如CCHistorimArthmetic类使用基于颜色直方图相交法实现MatchbyColor，而MatchbyColor在CAgrHistorimArthmetic类中使用基于颜色累积直方图相交法。

3.2.2 各主要模块设计

1)手工拼接

跟传统电子拼图游戏类似我们把每一个拼块实现编号，从1，2，3，… …到N记数。对每一个拼块CPiece类除了记录本身ID，还记录上、下、左、右四方向邻居拼块的编号，如果没有邻居拼块简单赋值为0即可。用于判断在游戏中两拼块是否邻接来触发自动磁性粘贴功能。手工拼接模块主要涉及人机交互方面，即玩家可以通过系统标准输入设备鼠标来实现拼块的拖拽移动和放下来完成拼图。其中最重要的是文档视图结构中视图类的用于鼠标消息响应的OnLButtonDown、OnLButtonUp和OnMouseMove三个方法。

OnLButtonDown方法中遍历各个拼块，如果鼠标指针位置在某个拼块外围盒中，则说明玩家选中该拼块，记录拼块编号和鼠标指针位置(X1，Y1)与拼块外围盒左上角坐标(X2，Y2)之差，用于移动拼块。

OnMouseMove方法中实时更新选中拼块外围盒左上角坐标。

OnLButtonUp方法中遍历除已选拼块外其余拼块，分别判断是否是已选拼块的顶端、左端、底端和右端拼块，如果是调整选中拼块外围盒左上角坐标。最后根据各拼块外围盒左上角坐标和宽高信息重新绘制视图中所有拼块。

2)自动拼接

通过UI由用户根据待拼接图像特点来选择使用单一颜色、单一纹理或单一形状算法以及它们的组合。例如对于一张灰度图像，用户会选择基于纹理和形状特征，而不会采用颜色特征来完成拼块自动匹配拼接。更进一步来讲，用户还可以具体到选择使用何种颜色、形状、纹理算法来比较和评价检索算法。

系统所用的每种算法都被包装成一个动态链接库(DLL)，平台对这些DLL是采用动态载入的方式调用的。这些DLL要求有统一的导出函数声明，即名称和参数列表。这样，我们调用每种算法时只需要提供通用的一些参数，如图像位图文件全路径，而算法程序也就是根据这些位图数据计算出检索所需要的特征和特征间相似距离再予以返回。在本系统中正是由CDllLoader的LoadLibraryAPI(LPCTSTR lpszDllName，LPCTSTR lpszModuleName，FARPROC *exportedfunc)来加载名为lpszDllNameDLL文件中名为lpszModuleName的算法函数。

4 关键技术与实现 4.1 颜色、纹理、纹理特征分析算法

1)颜色特征分析算法

本系统使用了颜色直方图的方法进行了颜色的提取，首先得到图像的RGB三个通道的直方图，然后将其转换为HSV分量，因为HSV是一种符合人的视觉习惯的一种彩色模型。

首先从RGB到HSV的转化公式[8]。

然后，将HSV三个分量进行量化用于对直方图的匹配。在匹配方法上采用了直方图相交距离的方法进行了图像的匹配。设HQ和HD分别为选中拼块图像Q和其它拼块图像D的HSV统计直方图，则两图之间的匹配值可以借助直方图相交法来计算。

2)纹理特征分析算法

本系统首先利用二维傅里叶变换F(u，v) 将图像变换到频域。二维傅里叶变换后的频谱能描述纹理的粗糙度和方向性[9]。

然后将(u，v ) 直角坐标系转换成(r，φ)极坐标系，其中r是以原点为中心的圆周半径，φ是极位角，这时计算各图块的粗糙度。取r=0，4，8，12，16...24共七个半径值，计算各幅图七个圆环的功率谱。在内径为r1，外径为r2的圆环上的功率谱为：

P(r1，r2)揭示了不同频率分量的能量分布信息，在纹理较粗的情况下，若r较小，P(r)很大，r很大时，P(r)反而较小；而在纹理较细的情况下，r变化对P(r)的影响不是很大。

再计算各图块纹理的分布方向性。取6个角度，计算各幅图的6个扇形的功率谱。计算扇形区域内的功率谱P (φ1，φ2):

其中φ1和φ2是规定扇形区范围的两个角度。

在匹配方法上采用欧式距离的方法进行匹配。则两图之间的匹配值可以计算图像间对应的圆环功率谱的欧式距离，计算图像间对应扇形功率谱的欧式距离，再进行相加，计算公式如下。

3)形状特征分析算法

由于系统中采用标准拼块形状，如图4所示，左上、左下、右上、右下四角点均成九十度，故采用空间模板匹配的方法即可获得角点坐标位置。

首先将拼图图像进行二值化处理，然后从左上角点作为跟踪的起始点，采用8邻域搜索的边缘跟踪算法[10]，得到上下左右四边的链码序列。而两拼块在位置上相邻的原则就是其相邻边的链码匹配相等，但实际由于误差的引入，即使两边相邻，也不可能两边链码完全相等，但至少在与其它拼块边链码差异上达到最小。这里需要注意的是，假定有两个边链码A和B，需要先对A和B进行反方向编码，即一个按顺时针编码，一个按逆时针编码，但8邻域搜索的准则是按逆时针编码。需要我们对A或B中的某一边链码取逆后再匹配，即对于链码的每一个码值加4后除以8的余数赋给原码值。

4.2　核心控制

由于本系统为教育演示软件，故用户可以自由选择采用何种特征进行自动拼接，以及各特征权重的设定，来观察不同特征分析匹配针对不同特点的拼块图像的结果。如果采用颜色、纹理、形状特征分析进行自动拼接，其流程图如图5所示，其中diff表示两边链码差异，min记录两边链码差异的最小值。

5 系统测试

在Windows XP系统下，采用面向对象的技术和相关机器视觉原理，利用功能强大的软件开发环境Visual C++6.0和GDI+/DirectX库开发了计算机拼图游戏系统。该软件经测试，系统已完成图3所示的各项功能性需求。系统可根据颜色和形状分析算法，成功地完成了12块拼块的拼接。另外，系统由于采用了算法Dll动态载入的方式，达到了系统平台代码和算法实现的独立性，为日后维护和升级平台系统和添加验证新的算法提供了方便。

6 结束语

以上阐述了计算机拼图游戏系统的设计与实现。该系统作为一款计算机游戏，其采用媒体渲染效果强大的DirectX库和MFC类库，具有界面美观，人机交互性强的特点。同时其本质又是基于内容的图像检索系统，该系统采用颜色、纹理以及部分边界信息成功完成了12、48块拼块的自动拼接。该系统不仅可以使游戏者带来成功的喜悦，而且还可以向游戏者演示人工智能中计算机视觉的基本原理和操作过程，为启发中学生的科研意识和创新意识起到积极作用。从深远层次角度考虑，如果系统处理对象的不同，本文介绍的技术方案，有可能应用于破碎物品修复、考古瓷器碎片复原、碎纸屑拼接等领域，具有广泛的市场前景。但由于采用算法的精确度所至，对于处理大规模数量的拼块或者更为复杂的拼块形状，系统还将在系统的精确性、灵活性方面加以改进，以提高其运行性能。

参考文献

[1] 王海龙，王佩雪.基于内容的图像检索探讨[J].中原工学院学报，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.，着. 设计模式:可复用面向对象软件的基础[M].李英军译.北京: 机械工业出版社，2000:12-92

[8] 章毓晋.基于内容的视觉信息检索[M]. 第一版，北京:科学出版社，2003:62

[9] Haralick.R.M.statistical and structural approaches to texture[J].IEEE.2000，67(5):786-804

更多计算机与外设信息请关注：21ic计算机与外设频道