五、模型的建立与求解
5.1问题一的模型建立与求解 5.1.1 中文碎纸片的拼接复原
根据4.1.1中的分析，做出19?19的矩阵D、矩阵D’、矩阵D’’、矩阵D’’’（这里仅做出D’与D’’，其他两个矩阵仅在下面的说明中会提及，但不会使用），元素Dij为碎纸片图像未倒置时矩阵i的第二列与矩阵j第一列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第二列与矩阵j的第二列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第一列与矩阵j第一列的边缘匹配度，元素Dij’’为碎纸片图像未倒置时矩阵i的第一列与矩阵j第二列的边缘匹配度。
? 0 0.6990 0.7485 0.6955 0.7621 0.7247 0.9621 0.7409 0.7687 0.7515 0.7692 0.7263 0.7843 0.7313 0.7202 0.7556 0.7369 0.7667 0.7778????0.7116 0 0.6995 0.7333 0.9212 0.7545 0.7606 0.7000 0.7318 0.7348 0.7677 0.7116 0.7576 0.7237 0.7237 0.7369 0.7626 0.7338 0.7258??0.7076 0.7490 0 0.7758 0.7636 0.7646 0.7343 0.7960 0.7934 0.7702 0.7596 0.7692 0.7657 0.7530 0.7258 0.8005 0.9717 0.7480 0.7227????0.7465 0.7061 0.7919 0 0.7520 0.7379 0.7581 0.7571 0.7828 0.7434 0.9359 0.7293 0.8056 0.7455 0.7495 0.7475 0.7510 0.7798 0.7141??0.7293 0.7384 0.7505 0.7348 0 0.9429 0.7379 0.7359 0.8434 0.7434 0.7470 0.7970 0.7652 0.7273 0.8192 0.7919 0.7530 0.7061 0.7798????0.7126 0.7460 0.7601 0.7111 0.7313 0 0.7141 0.7899 0.7722 0.9419 0.7283 0.7187 0.7758 0.7490 0.7318 0.7662 0.7616 0.7318 0.7439??0.7768 0.7313 0.8172 0.7106 0.7753 0.8510 0 0.8268 1.0000 0.7919 0.7561 0.8394 0.8581 0.7737 0.8374 0.9071 0.7955 0.7586 0.8192????0.7530 0.7369 0.7530 0.6919 0.7707 0.7253 0.7848 0 0.7712 0.7328 0.7465 0.7237 0.7788 0.7399 0.7369 0.7652 0.7646 0.9470 0.7338??0.7616 0.7455 0.7121 0.7045 0.7369 0.7985 0.7268 0.7500 0 0.7182 0.7348 0.7667 0.7449 0.7000 0.9232 0.7667 0.7227 0.7253 0.7919???D??0.7571 0.7328 0.7631 0.7566 0.7394 0.7343 0.7303 0.7707 0.7692 0 0.7253 0.7813 0.7424 0.9682 0.7015 0.7702 0.7485 0.7419 0.7288????0.7076 0.7288 0.9672 0.7303 0.7101 0.7606 0.7364 0.7778 0.7934 0.7793 0 0.7540 0.7879 0.7631 0.7227 0.7480 0.7394 0.7298 0.7288??0.7606 0.7525 0.7576 0.7146 0.7318 0.7540 0.7369 0.9480 0.8212 0.7768 0.7268 0 0.7722 0.7626 0.7515 0.7949 0.7823 0.7646 0.7288???? 0.7934 0.7076 0.7561 0.7131 0.7525 0.7869 0.7333 0.7869 0.8955 0.8015 0.7566 0.8096 0 0.7631 0.7874 0.9621 0.7778 0.7682 0.7707?? 0.7697 0.7384 0.7253 0.7217 0.7136 0.7611 0.7591 0.7631 0.8192 0.7434 0.7025 0.7939 0.7278 0 0.7626 0.8061 0.7379 0.7242 0.7793???? 0.7581 0.7086 0.8258 0.6939 0.7949 0.7859 0.7727 0.7828 0.8864 0.7490 0.7919 0.7672 0.9545 0.7641 0 0.8035 0.7646 0.7793 0.9535?? 0.7237 0.7328 0.7490 0.9354 0.7101 0.7263 0.6818 0.7111 0.6884 0.7005 0.7152 0.7379 0.7040 0.7460 0.6823 0 0.7455 0.6934 0.7409????0.7051 0.9525 0.7111 0.7348 0.7056 0.7419 0.6854 0.7611 0.7152 0.7455 0.7015 0.7202 0.6985 0.7232 0.7354 0.7040 0 0.7162 0.7066????0.9444 0.7253 0.7394 0.7025 0.7116 0.7409 0.7177 0.7742 0.7727 0.7293 0.7207 0.7727 0.7500 0.7717 0.7727 0.7818 0.7056 0 0.7384??0.7621 0.7298 0.7500 0.7242 0.7263 0.7606 0.7475 0.7414 0.7783 0.7480 0.7273 0.9187 0.7293 0.7611 0.7348 0.7965 0.7616 0.7217 0 ???? 0 0.6146 0.6298 0.6384 0.6879 0.6419 0.7687 0.6268 0.6737 0.6157 0.6399 0.6525 0.6884 0.6636 0.7177 0.5682 0.5828 0.6333 0.6197??? 0.6146 0 0.6061 0.6328 0.6662 0.6242 0.7318 0.6232 0.6551 0.6071 0.6424 0.6157 0.6707 0.6278 0.6788 0.5596 0.5793 0.6096 0.6111??? 0.6298 0.6061 0 0.6449 0.7066 0.6313 0.7934 0.6242 0.6722 0.6212 0.6596 0.6601 0.7232 0.6641 0.7162 0.5808 0.5904 0.6278 0.6455???? 0.6384 0.6328 0.6449 0 0.7071 0.6318 0.7828 0.6490 0.6636 0.6308 0.6561 0.6586 0.7136 0.6515 0.7217 0.5813 0.6030 0.6303 0.6389?? 0.6879 0.6662 0.7066 0.7071 0 0.6843 0.8434 0.6742 0.7182 0.6672 0.7146 0.7030 0.7652 0.7131 0.7561 0.6288 0.6455 0.6646 0.6864???? 0.6419 0.6242 0.6313 0.6318 0.6843 0 0.7722 0.6343 0.6712 0.6283 0.6535 0.6581 0.7404 0.6692 0.7071 0.5838 0.5753 0.6237 0.6545?? 0.7687 0.7318 0.7934 0.7828 0.8434 0.7722 0 0.7712 0.8273 0.7692 0.7934 0.8212 0.8955 0.8192 0.8864 0.6884 0.7152 0.7727 0.7783???? 0.6268 0.6232 0.6242 0.6490 0.6742 0.6343 0.7712 0 0.6753 0.6273 0.6586 0.6652 0.7152 0.6500 0.7323 0.5737 0.5965 0.6601 0.6273?? 0.6737 0.6551 0.6722 0.6636 0.7182 0.6712 0.8273 0.6753 0 0.6712 0.6823 0.6990 0.7561 0.6939 0.7439 0.6025 0.6121 0.6556 0.6601???Di? 0.6157 0.6071 0.6212 0.6308 0.6672 0.6283 0.7692 0.6273 0.6712 0 0.6576 0.6490 0.7141 0.6561 0.7020 0.5576 0.5702 0.6217 0.6253???? 0.6399 0.6424 0.6596 0.6561 0.7146 0.6535 0.7934 0.6586 0.6823 0.6576 0 0.6732 0.7303 0.6702 0.7354 0.5869 0.6268 0.6530 0.6677?? 0.6525 0.6157 0.6601 0.6586 0.7030 0.6581 0.8212 0.6652 0.6990 0.6490 0.6732 0 0.7591 0.6859 0.7490 0.5843 0.6172 0.6667 0.6712???? 0.6884 0.6707 0.7232 0.7136 0.7652 0.7404 0.8955 0.7152 0.7561 0.7141 0.7303 0.7591 0 0.7379 0.8000 0.6333 0.6662 0.7096 0.7081?? 0.6636 0.6278 0.6641 0.6515 0.7131 0.6692 0.8192 0.6500 0.6939 0.6561 0.6702 0.6859 0.7379 0 0.7429 0.6167 0.6131 0.6667 0.6561???? 0.7177 0.6788 0.7162 0.7217 0.7561 0.7071 0.8864 0.7323 0.7439 0.7020 0.7354 0.7490 0.8000 0.7429 0 0.6283 0.6561 0.7005 0.7081?? 0.5682 0.5596 0.5808 0.5813 0.6288 0.5838 0.6884 0.5737 0.6025 0.5576 0.5869 0.5843 0.6333 0.6167 0.6283 0 0.5682 0.5652 0.5909???? 0.5828 0.5793 0.5904 0.6030 0.6455 0.5753 0.7152 0.5965 0.6121 0.5702 0.6268 0.6172 0.6662 0.6131 0.6561 0.5682 0 0.5798 0.6015 ???? 0.6333 0.6096 0.6278 0.6303 0.6646 0.6237 0.7727 0.6601 0.6556 0.6217 0.6530 0.6667 0.7096 0.6667 0.7005 0.5652 0.5798 0 0?? 0.6197 0.6111 0.6455 0.6389 0.6864 0.6545 0.7783 0.6273 0.6601 0.6253 0.6677 0.6712 0.7081 0.6561 0.7081 0.5909 0.6015 0.6399???
对于得到的两个矩阵D、D'，从i=0即第0行（为方便说明）开始，找到这一行
'中最大的匹配度maxD0、，两者进行大小比较： maxD0'1） 若maxD0大于等于maxD0，把maxD0所处列数赋值为新的i，找到这一行中的最大
9
匹配度maxDi、maxDi'，两者进行大小比较，重复上述过程直到i重新变为0。若i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
''2） 若maxD0小于maxD0，把maxD0所处的列数赋值为新的i，找到矩阵D''、Dij'''这一
行中的最大匹配度maxD''i、maxDi'''，两者进行大小比较，其他过程与上述分析类似，不再进行说明，重复上述过程直到i重新变为0。若i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
'根据所得两个矩阵D、D'的情况，发现任意一行的maxD0大于maxD0，可以一定'程度说明碎纸片中不存在倒置的情况，仅按上述maxD0大于等于maxD0的情况做分析
即可。
该方法可以用图7的matlab软件编程流程图来表示。可以看出由于问题一中的数据量较小，为了方便我们仅对计算机的编程结果进行人工干预，而不对过程做人工干预。
10
i=0 否 maxDi>=maxDi’? 记录i并重新赋值i 是 maxDi’’>=maxDi’’’? 记录i并重新赋值i …… i=0? 是 本次搜索结束，记录i并记录搜索次数n并重新赋值i开始新的搜索 否 …… i经过19次变化（若重新进行了搜索，此处为19-n次） 是 结束并输出结果 人工处理
图7.流程图
得到的结果见表1：
表1.计算机拼图位置表格1 000 006 008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 001 根据表种情况可已发现碎纸片006和碎纸片008连接在一起，发生这种情况的原因
是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片008为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片008作为纸片的开端，表格见表2，在使用matlab中的imshow（）函数，得到人机结合后的复原图片。
11
表2.修改后的拼图位置表格2 008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 001 000 006
5.1.2 英文碎纸片的拼接复原
根据4.1.1与4.1.2的分析，模型建立求解同5.1.1。使用计算求解的结果见表3。 表3.计算机拼图位置表格3 000 005 001 009 013 010 008 012 014 017 016 004 003 006 002 007 015 018 011 根据表种情况可已发现碎纸片003和碎纸片004连接在一起，发生这种情况的原因
是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片003为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片003作为纸片的开端，表格见表3，在使用matlab中的imshow（）函数，人机结合后的复原图片见图片5。
表4.修改后的拼图位置表格4 003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004
5.2 问题二模型的建立与求解
5.2．1 中文碎纸片复原的模型建立与求解
搜索每一张碎纸片转化后二值化矩阵Ci的每一行，若存在黑色即矩阵该行中存在数
值1，则将该行全部赋值为1，若这一行不存在黑即此行元素全为0，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵Ei，之后同5.1的求解过程做边缘匹配，做出矩阵大小为209?209边缘匹配度矩阵D（由于矩阵太大，在论文中不作出），元素
Dij为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。在矩阵D中每一行选取匹配度大于0.9的元素，进行统计分组，可得结果如下表表5.
表5.分组情况 序碎纸片编号 号 1 0 7 45 53 68 126 137 138 158 174 175 208 2 1 18 23 26 30 41 50 62 76 86 87 100 120 142 147 168 179 191 195 3 2 11 22 28 49 54 57 65 91 95 118 129 141 143 178 186 188 190 192 4 3 12 31 39 51 73 82 107 115 128 134 135 159 160 169 176 199 203 12
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 4 40 101 108 113 114 117 119 123 140 146 151 154 155 185 194 207 5 10 29 37 44 48 55 59 64 75 92 98 104 111 171 172 180 201 206 6 19 20 36 52 61 63 67 69 72 78 79 96 99 116 131 162 163 177 8 9 25 74 105 182 13 15 17 33 80 83 132 133 156 198 200 202 16 21 66 106 109 110 139 145 150 157 173 181 184 187 197 204 24 35 38 46 81 88 103 122 130 148 161 167 189 193 27 60 85 152 165 170 205 32 56 70 93 153 166 196 34 42 43 47 58 77 84 90 94 97 112 121 124 127 136 144 149 164 183 14 71 89 102 125 可以看出在取匹配度为0.9及以上时，分出了20个组，其中组内元素最多的为19，
组内元素最少的为1。而最后的结果应该为11行，我们需要对这些组中的元素进行合并后得到11行，所以我们要先考虑元素数量为19的组，再考虑其他元素数多的组，对组内图片进行5.1中的边缘匹配，匹配后的结果在与元素数少的组做匹配与人工处理。
以序号2的组为例，该组包含19个元素，对于组内的19个元素的原始二值化矩阵进行上述中的边缘匹配，通过结果观察本题模型第一步确定模型的的可行性，其他的组的处理情况相同，不再重述。结果如下，见表6。
序号 2 168-100-076 分别复原得到图片，观察下面的图8、图9。 表6.内部分组 分组 062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018 13