基于慢特征分析的智能拼图算法
|
摘要
现有拼图算法对背景单一、存在大量相似物的图片进行组合拼接时,不能精确分辨拼图块间的微小差异,还原的图片存在偏差。为此,提出一种智能拼图算法,通过计算相邻拼图块边缘的慢特征值选择正确的拼图块,利用贪婪算法根据拼图块的邻近关系实现图片智能拼接。实验结果表明,与MGC算法相比,该算法具有更高的拼图准确率及稳定性。
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.
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.
引文
[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.Determining 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.Asystem for high-volume acquisition and matching of fresco fragments:reassembling Theran wall paintings[J].ACMTransactions 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:ACMPress,2007:171-176.
[6]CAO S,LIU H,YAN S.Automated assembly of shredded pieces from multiple photos[C]//Proceedings of IEEEInternational Conference on Multimedia and Expo.Washington D.C.,USA:IEEE Press,2010:358-363.
[7]MARQUES M A O,FREITAS C O A.Reconstructing stripshredded 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:IEEEPress,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].SIAMJournal 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.
[2]WANG C S.Determining molecular conformation from distance or density data[M]//Dissertation D.Determining 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.Asystem for high-volume acquisition and matching of fresco fragments:reassembling Theran wall paintings[J].ACMTransactions 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:ACMPress,2007:171-176.
[6]CAO S,LIU H,YAN S.Automated assembly of shredded pieces from multiple photos[C]//Proceedings of IEEEInternational Conference on Multimedia and Expo.Washington D.C.,USA:IEEE Press,2010:358-363.
[7]MARQUES M A O,FREITAS C O A.Reconstructing stripshredded 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:IEEEPress,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].SIAMJournal 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.