基于慢特征分析的智能拼图算法

doi:10.19678/j.issn.1000-3428.0049206

摘要/Abstract

摘要：

现有拼图算法对背景单一、存在大量相似物的图片进行组合拼接时,不能精确分辨拼图块间的微小差异,还原的图片存在偏差。为此,提出一种智能拼图算法,通过计算相邻拼图块边缘的慢特征值选择正确的拼图块,利用贪婪算法根据拼图块的邻近关系实现图片智能拼接。实验结果表明,与MGC算法相比,该算法具有更高的拼图准确率及稳定性。

关键词: 智能拼图, 慢特征分析, MGC算法, 贪婪算法, 最小生成树

Abstract:

Existing intelligence puzzle algorithms can not restore the image well when they have a single background and a large number of similar things.Because they can not distiguish the tiny difference between puzzle block.Aiming at these problem,this paper proposes a intelligence puzzle algorithm.It selects the correct puzzle pieces by calculating the slow eigenvaluess of the edges of adjacent puzzle pieces,and then uses the greedy algorithm to realize intelligence puzzle according to the neighbor relationship of puzzle pieces.Experimental results show that the algorithm has a higher puzzle accuracy stability than the MGC algorithm.

Key words: intelligence puzzle, Slow Feature Analysis(SFA), MGC algorithm, greedy algorithm, minimal spanning tree

中图分类号:

TP751.1

吴娟,陈丽芳. 基于慢特征分析的智能拼图算法[J]. 计算机工程, 2019, 45(2): 207-212.

WU Juan,CHEN Lifang. Intelligence Puzzle Algorithm Based on Slow Feature Analysis[J]. Computer Engineering, 2019, 45(2): 207-212.

https://www.ecice06.com/CN/Y2019/V45/I2/207

参考文献

［1］MARANDE W,BURGER G.Mitochondrial DNA as a genomic jigsaw puzzle［J］.Science,2007,318(5849):415-420.
［2］WANG C S.Determining molecular conformation from distance or density data［M］//Dissertation D.Deter-mining molecular conformation from distance or density data.Cambridge,USA:Massachusetts Institute of Technology,2000:1-7.
［3］MORTON A Q,LEVISON M.The computer in literary studies［C］//Proceedings of World Computer Congress.Poznan,Poland:［s.n.］,1968:1072-1081.
［4］BROWN B J,TOLERFRANKLIN C,NEHAB D,et al.A system for high-volume acquisition and matching of fresco fragments:reassembling Theran wall paintings［J］.ACM Transactions on Graphics,2008,27(3):1-9.
［5］ZHAO Y X,SU M C,CHOU Z L,et al.A puzzle solver and its application in speech descrambling［C］//Proceedings of 2007 Annual Conference on Computer Engineering and Applications.New York,USA:ACM Press,2007:171-176.
［6］CAO S,LIU H,YAN S.Automated assembly of shredded pieces from multiple photos［C］//Proceedings of IEEE International Conference on Multimedia and Expo.Washington D.C.,USA:IEEE Press,2010:358-363.
［7］MARQUES M A O,FREITAS C O A.Reconstructing strip-shredded documents using color as feature matching［C］//Proceedings of ACM Symposium on Applied Computing.New York,USA:ACM Press,2009:893-894.
［8］NIELSEN T R,DREWSEN P,HANSEN K.Solving jigsaw puzzles using image features［J］.Pattern Recognition Letters,2008,29(14):1924-1933.
［9］DEEVER A,GALLAGHER A.Semi-automatic assembly of real cross-cut shredded documents［C］//Proceedings of IEEE International Conference on Image Processing.Washington D.C.,USA:IEEE Press,2013:233-236.
［10］HERNANDEZ-CASTRO C J,R-MORENO M D.Using JPEG to measure image continuity and break capy and other puzzle CAPTCHAs［J］.IEEE Internet Computing,2015,19(6):46-53.
［11］FREEMAN H,GARDER L.Apictorial jigsaw puzzles:the computer solution of a problem in pattern recognition［J］.IEEE Transactions on Electronic Computers,1964,EC-13(2):118-127.
［12］WOLFSON H,SCHONBERG E,KALVIN A,et al.Solving jigsaw puzzles by computer［J］.Annals of Operations Research,1988,12(1):51-64.
［13］KOSIBA D A,DEVAUX P M,BALASUBRAMANIAN S,et al.An automatic jigsaw puzzle solver［C］//Proceedings of the 12th International Conference on Pattern Recognition.Washington D.C.,USA:IEEE Press,2013:9-13.
［14］WEBSTER R W,LAFOLLETTE P S,STAFFORD R L.Isthmus critical points for solving jigsaw puzzles in computer vision［J］.IEEE Transactions on Systems Man and Cybernetics,1991,21(5):1271-1278.
［15］YAO F H,SHAO G F.A shape and image merging technique to solve jigsaw puzzles［J］.Pattern Recognition Letters,2003,24(12):1819-1835.
［16］NIELSEN T R,DREWSEN P,HANSEN K.Solving jigsaw puzzles using image features［J］.Pattern Recognition Letters,2008,29(14):1924-1933.
［17］YANG X,ADLURU N,LATECKI L J.Particle filter with state permutations for solving image jigsaw puzzles［C］//Proceedings of CVPR’11.Washington D.C.,USA:IEEE Press,2011:2873-2886.
［18］POMERANZ D,SHEMESH M,BENSHAHAR O.A fully automated greedy square jigsaw puzzle solver［C］//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2011:9-16.
［19］GALLAGHER A C.Jigsaw puzzles with pieces of unknown orientation［C］//Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Computer Society,2012:382-389.
［20］MOSSEL E,ROSS N.Shotgun assembly of labeled graphs［EB/OL］.［2017-10-05］.http://arxiv.org/abs/1504.07682.
［21］BORDENAVE C,FEIGE U,MOSSEL E.Shotgun assembly of random jigsaw puzzles［EB/OL］.［2017-10-05］.https://arxiv.org/abs/1605.03086.
［22］MARTINSSON A.A linear threshold for uniqueness of solutions to random jigsaw puzzles［EB/OL］.［2017-10-05］.http://arxiv.org/abs/1701.04813.
［23］ZIELOSKO B,PILISZCZUK M.Greedy algorithm for attribute reduction［J］.Fundamenta Informaticae,2008,85(1-4):579-561.
［24］HASSIN R,LEVIN A.A better-than-greedy approximation algorithm for the minimum set cover problem［J］.SIAM Journal on Computing,2005,35(1):189-200.
［25］GU X,LIU C,WANG S.Supervised slow feature analysis for face recognition［C］//Proceedings of Chinese Conference on Biometric Recognition.Berlin,Germany:Springer,2013:178-184.
［26］WISKOTT L,SEJNOWSKI T.Slow feature analysis:unsupervised learning of invariances［J］.Neural Computation,2002,14(4):715.
［27］马奎俊.时序数据的慢特征分析及其若干应用［D］.北京:中国科学院大学,2011.

[1]	傅伟, 周新力. 无人机网络中基于博弈模型的数据转发优化算法[J]. 计算机工程, 2019, 45(8): 146-151.
[2]	杨罡, 晋涛, 王大伟, 曹京津, 张娜, 严碧武, 李涛, 程远. 改进的代价聚集快速立体匹配算法[J]. 计算机工程, 2019, 45(7): 268-272,281.
[3]	倪国英,覃锡忠,贾振红,牛红梅,王哲辉. 基于认知MIMO网络的资源分配方法[J]. 计算机工程, 2018, 44(8): 86-92,99.
[4]	李明,胡江平. 基于学习自动机的异构有向传感器节点调度算法[J]. 计算机工程, 2018, 44(8): 199-203.
[5]	李玉龙,刘任任,赵津锋,臧浪,曹斌. 分簇感知网络中基于压缩感知的数据收集方法[J]. 计算机工程, 2018, 44(10): 129-135.
[6]	韩毅,赵凯,周晏. 基于分数阶变换和改进最小生成树的图像配准算法[J]. 计算机工程, 2017, 43(9): 263-269.
[7]	曾千千,曾安,潘丹,杨海东,邓杰航. 基于最大信息系数的贝叶斯网络结构学习算法[J]. 计算机工程, 2017, 43(8): 225-230.
[8]	刘海客,李集林,尤启迪,张华健. 一种OpenFlow网络的动态负载均衡方法[J]. 计算机工程, 2016, 42(8): 85-90.
[9]	邢亚虹,杜欣慧. 基于贪婪算法的配电网网格负荷预测与规划方法[J]. 计算机工程, 2016, 42(11): 316-321.
[10]	林雅文,孔繁锵,沈秋,郭文骏. 基于自适应回溯联合正交匹配追踪的高光谱图像解混[J]. 计算机工程, 2015, 41(12): 188-193.
[11]	任亮,徐志刚,赵祥模,周经美. 基于Prim最小生成树的路面裂缝连接算法[J]. 计算机工程, 2015, 41(1): 31-36.
[12]	肖婧, 郑更生, 方勇, 陈蒂. 基于自组织神经网络的分簇成链协议[J]. 计算机工程, 2013, 39(7): 148-151.
[13]	汤进, 陈影, 江波, 罗斌. 基于复杂网络的图像建模与特征提取方法[J]. 计算机工程, 2013, 39(5): 243-247,252.
[14]	赵知劲, 赖海超, 尚俊娜. 基于QoS需求的认知无线电资源分配算法[J]. 计算机工程, 2013, 39(2): 85-89.
[15]	徐沁，罗斌. 结合mean-shift与MST的K-means聚类算法[J]. 计算机工程, 2013, 39(12): 204-210.

选择文件类型/文献管理软件名称

选择包含的内容