本发明涉及计算机图象处理技术领域，更具体的是涉及一种彩色图案的计算机辅助拼接方法。

在生产和生活中，人们需要将一些碎片拼接复原为完整的图形，例如金属板材、因误操作而被碎纸处理的重要纸质文件以及纸币等平面材料的拼接复原。但是拼接工作比较繁琐，其劳动量随着碎片数量的增加成指数增长。人工拼接费时费力。而实际上，拼接的绝大部分时间是花费在比较、试拼接和调整等重复性的工作上。而由于人为参与的成分较多，往往出现因为人为因素（例如人的疲劳）等原因导致的拼接错误。

碎片拼接问题具有几个特点。首先，在大多数情况下无法预知最后拼接结果的全貌，而作为拼接依据的重要信息主要位于碎片边缘；其次，在无碎片丢失的情况下，拼接时碎片既不重叠，也不存在间隙；再次，对于实物物体，拼接时一般不能对碎片模块进行形态上的几何扭曲变形。对于常见的具有彩色图案和直线棱边特点的碎片模块，拼接工作实际上可以由计算机辅助完成。利用计算机信息采集和处理技术，结合拼接算法可以获得优化的拼接策略，从而避免了重复的比较、试拼接和调整等繁琐工作，大大节省拼接时间，提高拼接效率和准确度。

专利（申请号200910073179.2）提出了一种基于碎片断面的高度图的三维物体碎片的数字拼接方法，这种方法采用碎片断面高度匹配作为拼接依据，因此适用于三维物体碎片，但是对于具有彩色图案和直线棱边特点的碎片模块该方法并不适用。

本发明的目的是提供一种用于拼接具有彩色图案和直线棱边的模块的计算机辅助拼接方法。

本发明的技术方案是：包括以下步骤

1）扫描；将n块彩色拼图模块在相同条件下进行扫描，对彩色拼图模块和扫描的彩色图像相对应的从1到n依次编号；

2）编码；对彩色拼图模块和扫描的彩色图像中所有棱边从1到mi依次编号，其中i=1,2,3, …, n；然后在每个棱边按等间隔d取点，取点规则是第一点是每个棱边的中点，然后依次对称向第一点两边取点，提取每个点的颜色编码，为这                                                条棱边进行编码，并建立数据库，所述数据库包括棱边编号、棱边所在彩色拼图模块编号、拼接配对成功标志、棱边上各点颜色编码；

3）配对；首先对所有棱边按照取点数目进行分组，相同取点数目的棱边分在同一组；然后按照取点数目由多到少分别对各组中的棱边进行拼接配对；所述拼接配对是评判两棱边上相对的所取点的颜色编码是否一致，并对配对成功的棱边进行标记；

4）模拟拼图；按照步骤3）中配对标记进行模拟拼图并检查，如未达要求，调整d值后返回步骤2）；

5）实物拼图；步骤4）的结果拼接彩色拼图模块；

进一步，所述步骤2）中对颜色编码的提取方法是，以所取点为中心、R值为半径划定一个区域，对该区域内的所有象素点的颜色值取均值，获得均值颜色编码。

本发明的有益效果是：

1）本方法除了采用边缘特征点的颜色信息作为拼接依据外，同时以边缘长度作为拼接依据，按照边缘长度获得不同长度的碎片边缘信息，以边缘信息长度匹配作为拼接的首要条件进行初次筛选，从而节省拼接计算的时间。

2）极大地提高了拼接效率。采用该方法，拼接过程由预先设定好拼接算法的计算机来完成，免除了人为的比较、试拼接和调整等费时费力的过程。使人摆脱了繁琐的拼接劳动，大大降低了因为人为因素（例如人的疲劳）等原因导致的拼接错误，提高了拼接的准确程度。

表1 棱边取点编号顺序示意图

表2 拼接计算前的棱边数据库表

表3 拼接计算后的棱边数据库表

图1 操作流程图；

图2 棱边取点编号顺序示意图；

图3 拼图模块（其中Ⅰ、Ⅱ、Ⅲ三个模块的编号分别为1、2、3）；

图4 模块拼接完成图；

图中英文字母表示不同颜色，B：蓝色；G：绿色；K ：黑色；R：红色；Y：黄色。

其操作流程图如图1。具体实施过程可分为5大步骤：

1、扫描。假设需要拼接的彩色拼图模块有n块，每块拼图模块有mi条棱边（i=1,2,3, …, n）。首先将这n块拼图模块在相同扫描条件下依次扫描，转换成为数码格式的彩色图像，并在实物和计算机中同时对这些彩色拼图模块和彩色图像依次标记相同的序号。特别注意拼图模块的棱边边缘颜色和长度信息采集的准确性。

2、编码。对采集的n块拼图模块的每条棱边（共条棱边）从1开始依次编号，然后进行等距间隔（例如间隔距离d取为1 mm）取点，第一个点为每条棱边的中点，其余依次向两边取点。为这条棱边进行编码，并建立数据库。数据库包括以下信息：该棱边的编号i、该棱边所在拼图模块的编号j、拼接配对成功与否的标志flag（初始取值都设置为0）、棱边上依次各点的红绿蓝颜色编码[a,b,c]（以棱边中点为第一点），并在数据库中存储成为一串颜色编码序列。

表1 编码数据存储格式

其存储顺序参照表1所示，第一个存储位置保存了棱边的编号信息；第二个存储位置保存了该棱边所在拼图模块的编号信息；第三个存储位置保存了拼接配对成功与否的标志信息；第四及其后的存储位置保存了棱边上各点的红绿蓝颜色编码信息。图2展示了棱边上各点的编号顺序，第一个点位于棱边中点，第二个点位于第一个点左下侧，第三个点位于第一个点右上侧，第四个点位于第一个点左下侧，第五个点位于第一个点右上侧，依次类推。并且，相邻两点间距相等。棱边的编号i同时标记在被扫描的拼图模块上，以便按照计算机拼图结果拼接实物模块。

为了提高拼接配对的效率和准确性，还可以采用改进的方法，即在棱边上各点的位置确定好后，以各点为中心、R值为半径划定一个区域（棱边边缘为直线的情况下为一个半圆区域），并对该区域内的所有象素点的颜色编码后取均值，获得均值颜色编码[A,B,C]。其中，，。这里p为该区域内的所有象素点的个数，ai、bi、ci分别为区域内每个像素点的红绿蓝颜色编码。

3、配对。首先对所有的棱边按照取点数目进行分组，相同取点数目的棱边分在同一组。然后按照取点数目由多到少分别对各组中的棱边进行拼接配对，即先拼接取点数目多的组，后拼接取点数目少的组。对于任意一组中的一条棱边，假如数据库中的flag信息为0，则依次与同组中flag信息为0的棱边进行比较，比较是否具有相同颜色编码序列，从而判断是否和该棱边相匹配。每次比较过程中，假如判定不匹配，则将进行比较的其中一条棱边的颜色编码序列的顺序重新调整，即保持中点颜色编码仍然在第1个位置，第2、第3个颜色编码顺序互换，第3、第4个颜色编码顺序互换，第5、第6个颜色编码顺序互换，…。以此避免因为棱边上中点的两侧的颜色编码序列的顺序被颠倒记录而不能顺利拼接的情况。拼接成功后的棱边在数据库中的flag存储位置标记为与之配对的棱边编号，否则仍然置为0。采用相同方法对依次对其它组中的棱边进行拼接。

    4、模拟成图。按照配对结果所显示的标记，采用计算机进行模拟拼图，检查实际拼图效果，判断拼图效果是否满意。不满意则回到步骤2，需要则进行新一轮的操作循环，即调整d值和R值，重新进行下一轮编码、配对、拼接成图步骤；满意则终止，完成拼接成图工作。

    5、实物拼图。按照模拟拼图的结果对进行彩色拼图模块拼接。

实施例1   

本发明彩色图案的计算机辅助拼接方法，用于拼接具有彩色图案和直线棱边的模块。以下结合实施例，具体说明其操作步骤：

1、扫描。如图3中，总共有3块需要拼接的彩色拼图模块。对其进行编号，图中Ⅰ、Ⅱ、Ⅲ三个模块的编号分别为1、2、3。拼图模块形状都为等腰直角三角形，其中模块1的直角边长13.8 cm，模块2的斜边长27.6 cm，模块3的直角边长13.8 cm。依次对每个拼图模块的棱边进行编号，具体编号如图3所示。将这3块拼图模块在相同扫描条件下依次扫描，转换成为数码格式的彩色图形。特别注意拼图模块的边缘颜色和长度信息采集的准确性。

2、编码。对采集的3块拼图模块的每条棱边（共9条棱边）进行从1开始依次编号，然后进行等距间隔取点，间隔距离为d=2 cm。第一个点为每条棱边的中点，其余依次向两边取点，获得这9条棱边的颜色编码序列，并建立数据库，如表2所示。另外，棱边的编号1～9同时标记在被扫描的拼图模块上，以便按照计算机拼图结果拼接实物模块。

表2 拼接计算前的棱边数据库表

为了提高拼接配对的效率和准确性，采用改进的方法，即在棱边上各点的位置确定好后，以各点为中心、R=1 mm值为半径划定一个区域（棱边边缘为直线的情况下为一个半圆区域），并对该区域内的所有象素点的颜色编码后取均值，获得均值颜色编码[A,B,C]。其中，，。这里p为该区域内的所有象素点的个数，ai、bi、ci分别为区域内每个像素点的红绿蓝颜色编码。

3、配对。首先对所有的棱边按照取点数目进行分组，相同取点数目的棱边分在同一组。这样，9条棱边可以分为3组，第一组：棱边5；第二组：棱边3、4、6、7；第三组：棱边1、2、8、9。然后按照取点数目由多到少分别对各组中的棱边进行拼接配对。先配对第一组中的棱边，配对结果：没有配对成功的棱边；再配对第二组，配对结果：棱边3和4可以配对，而棱边6和7在其中一条棱边改变颜色编码序列的顺序后也可以配对成功。更改配对成功的棱边中的flag信息；最后对第三组中的棱边进行配对，配对结果：没有可以配对的棱边。最终配对结果如表3所示。

表3拼接计算后的棱边数据库表

4、模拟成图。按照计算机拼图结果（表3）以及拼图模块的棱边编号，模拟拼接各个拼图模块，即棱边3和4拼接，棱边6和7拼接，形成如图4所示的图像，经检查该拼图符合要求。

5、实物拼图。按照模拟拼图的结果，最终进行实物拼图。