Intelligence Puzzle Algorithm Based on Slow Feature Analysis

doi:10.19678/j.issn.1000-3428.0049206

Abstract

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

摘要：

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

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

CLC Number:

TP751.1

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

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0049206

http://www.ecice06.com/EN/Y2019/V45/I2/207

References

［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]	MIAO Xin, CHEN Xuan, BAO Hongying, ZHANG Jingxuan, YU Wei. Study on Path Sweep Coverage Problem in Mobile Sensor Networks [J]. Computer Engineering, 2022, 48(12): 150-155,164.
[2]	YANG Ben, WANG Weiye, ZHAO Wanting, XIE Jinkui. DQN-based Automatic Stowage Planning Algorithm Using Dynamic Depth Multi-branch Search [J]. Computer Engineering, 2020, 46(8): 313-320.
[3]	FU Wei, ZHOU Xinli. Data Forwarding Optimization Algorithm Based on Game Model in Unmanned Aerial Vehicle Network [J]. Computer Engineering, 2019, 45(8): 146-151.
[4]	NI Guoying,QIN Xizhong,JIA Zhenhong,NIU Hongmei,WANG Zhehui. Resource Allocation Method Based on Cognitive Multiple-Input Multiple-Output Networks [J]. Computer Engineering, 2018, 44(8): 86-92,99.
[5]	LI Ming,HU Jiangping. Scheduling Algorithm for Heterogeneous Directed Sensor Nodes Based on Learning Automata [J]. Computer Engineering, 2018, 44(8): 199-203.
[6]	WANG Suqin,ZHANG Yang,JIANG Hao,ZHU Dengming. Improved Epsilon-greedy Algorithm for Cold-start Problem of New Users [J]. Computer Engineering, 2018, 44(11): 172-177.
[7]	ZENG Qianqian,ZENG An,PAN Dan,YANG Haidong,DENG Jiehang. Bayesian Network Structure Learning Algorithm Based on Maximal Information Coefficient [J]. Computer Engineering, 2017, 43(8): 225-230.
[8]	ZHENG Jinjin,LUO Zhinian. Resource Management Based on Greedy Algorithm for Carrier Aggregation in LTE-A System [J]. Computer Engineering, 2017, 43(11): 50-54.
[9]	Lü Tianhang,LIU Qinrang,ZHAO Bo. Network on Chip Inter-layer Connection Structure for 3D-Mesh Based on Greedy Algorithm [J]. Computer Engineering, 2016, 42(9): 52-57.
[10]	WEI Hao,CHEN Huafeng,CHEN Jun. Optimal Placement Method of City Surveillance Camera Network Based on Road Coverage [J]. Computer Engineering, 2016, 42(5): 269-274.
[11]	XING Yahong,DU Xinhui. Grid Load Forecasting and Planning Method for Distribution Network Based on Greedy Algorithm [J]. Computer Engineering, 2016, 42(11): 316-321.
[12]	ZHANG Xiang,ZHU Ming,SUN Yinlong,FANG Xuefeng. Virtual Channel Generation Algorithm in Network Live Television [J]. Computer Engineering, 2015, 41(12): 236-240.
[13]	LIN Yawen,KONG Fanqiang,SHEN Qiu,GUO Wenjun. Hyperspectral Image Unmixing Based on Adaptive Backtracked Simultaneous Orthogonal Matching Pursuit [J]. Computer Engineering, 2015, 41(12): 188-193.
[14]	LING Quan,LI Meiyi. Research on Backbone Nodes Deployment Algorithm in Wireless Mesh Network [J]. Computer Engineering, 2015, 41(11): 147-152.
[15]	XIAO Jing, ZHENG Geng-Sheng, FANG Yong, CHEN Di. Clustering and Chaining Protocol Based on Self Organizing Neural Network [J]. Computer Engineering, 2013, 39(7): 148-151.

Please choose a citation manager

Content to export