基于聚类优化模型的碎纸自动拼接方法研究 - 计算机应用与软件.pdf

第３２卷第１２期　　　 计算机应用与软件 Ｖｏｌ３２Ｎｏ．１２ ２０１５年１２月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｄｅｃ．２０１５ 基于聚类优化模型的碎纸自动拼接方法研究 张　亮 （浙江工业大学经贸管理学院　浙江杭州３１００２３） 摘　要　　碎纸自动拼接算法是计算机图形图像应用的一个热点领域。对于碎纸拼接主要由计算机图像预处理、图形图像特征提 取和图像匹配三个过程组成。针对中文内容碎纸和英文内容碎纸的区别，给出了两种不同的图像特征提取方法。首先建立聚类模 型对碎纸图像中提取的图像特征值进行Ｋｍｅａｎ聚类得到属于同一行的碎片集合；然后建立旅行商优化数学模型，以拼接方案特征 值误差平方和最小为目标函数，实现同一行碎片集合的排序，形成完整一行的图像；最后利用优化数学模型实现不同行图像的排序。 实验结果显示：该拼接算法可以给出准确的拼接方案，且求解迅速，无需进行人工干预，实现真正的全自动拼接。 关键词　　图像拼接　系统聚类　旅行商最优化 中图分类号　ＴＰ３　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１５．１２．０５１ ＲＥＳＥＡＲＣＨＯＮＡＵＴＯＭＡＴＩＣＲＥＣＯＮＳＴＲＵＣＴＩＯＮＯＦＲＩＰＰＥＤＵＰＤＯＣＵＭＥＮＴＳＢＡＳＥＤ ＯＮＣＬＵＳＴＥＲＩＮＧＯＰＴＩＭＩＳＡＴＩＯＮＭＯＤＥＬ ＺｈａｎｇＬｉａｎｇ （ＳｃｈｏｏｌｏｆＢｕｓｉｎｅｓｓＡｄｍｉｎｉｓｔｒａｔｉｏｎ，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ３１００２３，Ｚｈｅｊｉａｎｇ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ａｕｔｏｍａｔｉｃｒｉｐｐｅｄｕｐｄｏｃｕｍｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎｉｓａｈｏｔｆｉｅｌｄｉｎｃｏｍｐｕｔｅｒｇｒａｐｈｉｃｓｉｍａｇｅａｐｐｌｉｃａｔｉｏｎｓ．Ｆｏｒｒｉｐｐｅｄｕｐｄｏｃｕｍｅｎｔｓ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，ｉｔｍａｉｎｌｙｃｏｎｓｉｓｔｓｏｆｔｈｒｅｅｐｒｏｃｅｓｓｅｓｉｎｃｌｕｄｉｎｇｃｏｍｐｕｔｅｒｉｍａｇｅｐｒｅｐｒｏｃｅｓｓｉｎｇ，ｇｒａｐｈｉｃｓｉｍａｇｅｆｅａｔｕｒｅｅｘｔｒａｃｔｉｏｎａｎｄｉｍａｇｅ ｍａｔｃｈｉｎｇ．ＡｉｍｉｎｇａｔｔｈｅｄｉｆｆｅｒｅｎｃｅｂｅｔｗｅｅｎｒｉｐｐｅｄｕｐｄｏｃｕｍｅｎｔｓｗｉｔｈＣｈｉｎｅｓｅａｎｄＥｎｇｌｉｓｈｃｏｎｔｅｎｔｓ，ｗｅｐｒｅｓｅｎｔｉｎｔｈｅｐａｐｅｒｔｗｏｄｉｆｆｅｒｅｎｔ ｉｍａｇｅｆｅａｔｕｒｅｅｘｔｒａｃｔｉｏｎｍｅｔｈｏｄｓ．Ｆｉｒｓｔｗｅｂｕｉｌｄｃｌｕｓｔｅｒｉｎｇｍｏｄｅｌ，ｉｔｉｓｆｏｒａｐｐｌｙｉｎｇｋｍｅａｎｓｃｌｕｓｔｅｒｉｎｇｔｏｉｍａｇｅｆｅａｔｕｒｅｖａｌｕｅｅｘｔｒａｃｔｅｄｆｒｏｍ ｒｉｐｐｅｄｕｐｄｏｃｕｍｅｎｔｉｍａｇｅｔｏｏｂｔａｉｎｔｈｅｓｅｔｏｆｆｒａｇｍｅｎｔｓｂｅｌｏｎｇｉｎｇｔｏｓａｍｅｒｏｗ；Ｔｈｅｎｗｅｂｕｉｌｄｔｈｅｏｐｔｉｍｉｓｅｄｔｒａｖｅｌｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ （ＴＳＰ）ｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌ，ｔａｋｉｎｇｉｔａｓｔｈｅｔａｒｇｅｔｆｕｎｃｔｉｏｎｔｈａｔｔｏｍｉｎｉｍｉｓｅｔｈｅｅｒｒｏｒｓｑｕａｒｅｓｕｍｏｆｆｅａｔｕｒｅｖａｌｕｅｏｆｓｐｌｉｃｉｎｇｓｃｈｅｍｅｔｏ ａｃｈｉｅｖｅｔｈｅｓｏｒｔｉｎｇｏｆｔｈｅｆｒａｇｍｅｎｔｓｅｔｉｎｓａｍｅｒｏｗａｎｄｔｏｆｏｒｍｔｈｅｉｍａｇｅｏｆａｃｏｍｐｌｅｔｅｒｏｗ；Ｆｉｎａｌｌｙ，ｗｅｅｍｐｌｏｙｔｈｅｏｐｔｉｍｉｓｅｄｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌｔｏｉｍｐｌｅｍｅｎｔｓｏｒｔｉｎｇｔｈｅｉｍａｇｅｓｏｆｄｉｆｆｅｒｅｎｔｒｏｗｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｌｌｕｓｔｒａｔｅｔｈａｔｔｈｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｐｒｏｐｏｓｅｄｉｎｔｈｅｐａｐｅｒ ｃａｎｐｒｏｖｉｄｅａｃｃｕｒａｔｅｓｐｌｉｃｉｎｇｓｃｈｅｍｅｗｉｔｈｒａｐｉｄｓｏｌｕｔｉｏｎａｎｄｗｉｔｈｏｕ