计算机拼图中形状识别算法研究
|
摘要
自动拼图(Automatic Puzzle Solver,APS)利用拼块的颜色、纹理和形状特征实现计算机对图像的自动拼接。拼图问题涉及到机器视觉、图像分析和模式识别等多个研究领域,需要形状描述、边界匹配、特征提取、相似性度量等很多机器视觉知识。此问题在考古学中的文物修复、公安机关的物证碎片复原以及生物研究等方面也有广泛的应用。本文在JPTV1.0(自动拼图软件1.0版本,拼图对象为计算机分割的拼块)的基础上,采用扫描仪摄入实际拼块进行研究。
自动拼图教育游戏软件采用了集教育性和娱乐性为一身的游戏形式,浅显易懂地介绍和展示了基本的机器视觉技术原理和方法。形状信息是拼图中利用的主要信息之一,对于拼图最终的匹配效果起着十分重要的作用。本文针对形状这一特征进行了大量的研究。
论文沿着拼图从实物扫描到最终的曲线匹配这一完整的流程一步步展开,研究内容主要体现在以下几个方面:
1.研究了拼块图像的噪声处理方法,并得出了良好的结果。
2.研究了图像轮廓的提取方法,并且将图像用链码及曲率两种方法进行表达。其中对于曲率的表达,比较了各种曲率计算方法,最后选定了一种简洁高效的闭合轮廓的曲率计算方法作为本文拼块形状表达所用。
3.为了找到拼图形状匹配需要的各条边界信息,本文研究了各种角点检测算法,最后经过改进,提出基于链码的拼块角点检测算法和基于曲率的拼块角点检测算法,并给出了详细的比较与评价。
4.分别就链码曲线和曲率曲线两种图像轮廓表达方式,结合动态规划的算法,提出基于链码的动态规划匹配算法和基于曲率的动态规划匹配算法对图像进行边界匹配。同时分别对不同的曲线表达方式给予了不同的相似性度量规则。最后通过实际的扫描拼图对以上算法进行测试,取得了90%以上的匹配正确率。结合颜色,纹理的参与,最终完成了拼图的正确拼接。
The aim of Automatic puzzles solver is to automatically assemble an image of the pieces of a jigsaw puzzle by the shape,color and texture features of the pieces,Jigsaw puzzle problem endemic to machine vision,image analysis and pattern recognition.It contains a number of issues about machine vision,like shape description,partial boundary matching,feature extraction,etc.It can be applied to diverse areas such as restoration of archaeological findings, repair of broken objects,biological research,etc.Based on the version 1.0 of the JPT,this paper makes use of the scanner to get the pictures as the object to research.
Automatic puzzles solver software integrates educational factor into a funny game and presents the basic principle of machine vision technology.It's easy to understand by students. The shape information is one of the most important information,which plays leading role in the Automatic Puzzles.This paper does a lot of research about the shape matching.
The research starts from image scanning and goes along the process of an image change into curves to finish this paper.The research contents of the paper include:
1.Discussing the methods reducing the noise caused by piece shadows,scanner noise, specks of color on the back sides of pieces,and so on.And a good result is gained.
2.Introducing the image contour extraction.We obtain the Freeman chain code representation and the curvature representation of the boundary firstly.In order to find the easiest algorithm to calculate the curvature,we compare several methods in this filed.In the end,a kind of way named closed contour calculation is selected to complete our work.
3.In order to find the boundary,this paper studies several conner detection algorithms and proposes two algorithms:conner detection based on chain code and conner detection based on curvature.Also detailed comparison and estimate about the two algorithms are discussed.
4.After the chain code and curvature of the boundary obtained,we combine the dynamic programming algorithm with them separately and propose a dynamic programming algorithms based on chain code and curvature.And different similar-measurements of the two algorithms are given respectively.The experiments results indicate that,without the participating of color and texture and only using the characteristic of shape,the correct rate approaches exceed 90%.If we combine the shape characters with color and texture,a whole image will be assembled correctly.
自动拼图教育游戏软件采用了集教育性和娱乐性为一身的游戏形式,浅显易懂地介绍和展示了基本的机器视觉技术原理和方法。形状信息是拼图中利用的主要信息之一,对于拼图最终的匹配效果起着十分重要的作用。本文针对形状这一特征进行了大量的研究。
论文沿着拼图从实物扫描到最终的曲线匹配这一完整的流程一步步展开,研究内容主要体现在以下几个方面:
1.研究了拼块图像的噪声处理方法,并得出了良好的结果。
2.研究了图像轮廓的提取方法,并且将图像用链码及曲率两种方法进行表达。其中对于曲率的表达,比较了各种曲率计算方法,最后选定了一种简洁高效的闭合轮廓的曲率计算方法作为本文拼块形状表达所用。
3.为了找到拼图形状匹配需要的各条边界信息,本文研究了各种角点检测算法,最后经过改进,提出基于链码的拼块角点检测算法和基于曲率的拼块角点检测算法,并给出了详细的比较与评价。
4.分别就链码曲线和曲率曲线两种图像轮廓表达方式,结合动态规划的算法,提出基于链码的动态规划匹配算法和基于曲率的动态规划匹配算法对图像进行边界匹配。同时分别对不同的曲线表达方式给予了不同的相似性度量规则。最后通过实际的扫描拼图对以上算法进行测试,取得了90%以上的匹配正确率。结合颜色,纹理的参与,最终完成了拼图的正确拼接。
The aim of Automatic puzzles solver is to automatically assemble an image of the pieces of a jigsaw puzzle by the shape,color and texture features of the pieces,Jigsaw puzzle problem endemic to machine vision,image analysis and pattern recognition.It contains a number of issues about machine vision,like shape description,partial boundary matching,feature extraction,etc.It can be applied to diverse areas such as restoration of archaeological findings, repair of broken objects,biological research,etc.Based on the version 1.0 of the JPT,this paper makes use of the scanner to get the pictures as the object to research.
Automatic puzzles solver software integrates educational factor into a funny game and presents the basic principle of machine vision technology.It's easy to understand by students. The shape information is one of the most important information,which plays leading role in the Automatic Puzzles.This paper does a lot of research about the shape matching.
The research starts from image scanning and goes along the process of an image change into curves to finish this paper.The research contents of the paper include:
1.Discussing the methods reducing the noise caused by piece shadows,scanner noise, specks of color on the back sides of pieces,and so on.And a good result is gained.
2.Introducing the image contour extraction.We obtain the Freeman chain code representation and the curvature representation of the boundary firstly.In order to find the easiest algorithm to calculate the curvature,we compare several methods in this filed.In the end,a kind of way named closed contour calculation is selected to complete our work.
3.In order to find the boundary,this paper studies several conner detection algorithms and proposes two algorithms:conner detection based on chain code and conner detection based on curvature.Also detailed comparison and estimate about the two algorithms are discussed.
4.After the chain code and curvature of the boundary obtained,we combine the dynamic programming algorithm with them separately and propose a dynamic programming algorithms based on chain code and curvature.And different similar-measurements of the two algorithms are given respectively.The experiments results indicate that,without the participating of color and texture and only using the characteristic of shape,the correct rate approaches exceed 90%.If we combine the shape characters with color and texture,a whole image will be assembled correctly.
引文
[1]葛庆平.北京市教育委员会科技发展计划面上项目申请书.2006.10.
[2]亦凡.用面向对象方法开发拼图处理和实现方法[J].电脑编程技巧与维护,2005(9):34-35
[3]张成海,唐双春.在AutoCAD下实现自动拼图[J].机械,第30卷增刊,2003:199-200.
[4]屠红蕾,黄静.基于K段主曲线算法的手绘形状识别[J].计算机应用,2009,29(2):456-458.
[5]吕玉增,彭启民,黎湘.基于极值特征的不变性形状识别[J].电子学报,2008,36(4):679-684.
[6]夏敏,刘宏申.基于小波描述子和神经网络的形状识别[J].计算机技术与发展,2007,17(3):106-108.
[7]周振环.基于角点特征的形状识别[J].计算机工程,2007,33(6):22-26.
[8]张波,邹建成,刘旭丽.一类新的V描述子在形状识别中的应用[J].计算机辅助设计与图形学学报,2007,19(7):920-926.
[9]Freeman,Garder.Apictorial Jigsaw Puzzles:The Computer Solution of a Problem in Pattem Recognition[J].IEEE Transactions on electronic computers,1964,118-127
[10]David A.Kosiba,Pierre M.Devaux,Sanjay Balasubramanian,etc.An Automatic Jigsaw Puzzle Solver[J].IEEE,1994,616-618
[11]M.G.Chung,M.Fleck,D.A.Forsyth.Jigsaw puzzle solver using shape and color[J],in:Proc.ICSP'98,1998,pp.877-880.
[12P N Suganthan.Solving jigsaw puzzles using Hopfield neural networks[J].IEEE(1999 ) 3745-3749.
[13]David Goldberg,Christopher Malon,Marshall Bern.A global approach to automatic solution of jigsaw puzzles[J].Computational Geometry 28,2004165-174..
[14]Min Gyp Chung,Margaret M.Fleck,David A.Forsyth.JIGSAW PUZZLE SOLVER USING SHAPE AND COLOR[J].Proc.ICSP'98,1998,pp.877-880.
[15]Roger W.Webster,Paul S.LaFollette,Robert L.Stafford.Isthmus Critical Points for Solving Jiagsw Puzzles in Computer Vision[J].IEEE,1991,1271-1278.
[16]陈希.基于内容的图像检索技术及其应用研究.武汉理工大学硕士学位论文.2008.04
[17]章毓晋.基于内容的视觉信息检索[M].北京,科学出版社,2003.5,62,94-95,118-123.
[18]李向阳,庄越挺,潘云鹤.基于内容的图像检索技术与系统[J].计算机研究与发展,2001.3,38(3):344-354.
[19]T.S.Huang,S.Mehrotra,and K.Ramchandran."Multimedia analysis and retrieval system(MARS)project"[C],in Proc of 33rd Annual Clinic on Library Application of Data Processing - Digital Image Access and Retrieval,1996.
[20]Wei-Ying Ma,B.S.Manjunath."NeTra:A toolbox for navigating large image databases"[J].Multimedia Systems 1999,7:154-198.
[21]Hongjiang Zhang."Relevance Feedback in Content-Based Image Retrieval".[EB/OL]http://research.microsoft.com/asia.
[22]郑南宁.计算机视觉与模式识别[M].北京,国防工业出版社,1998.80.
[23]井上诚喜等著,白玉林译.C语言使用数字图像处理[M].北京:科学出版社,2003.87-91.
[24]章毓晋.图像工程(中册)图像分析[M].北京,清华大学出版社,2005.10,369-377.
[25杨淑莹.VC++图像处理程序设计[M].北京,北方交通大学出版社,2003.79-80,148-149.
[26]崔凤魁,张丰收,白露,许荣海.二值图像目标领域点法边界跟踪算法[J].洛阳工学院学报,2001,22(1):28-34.
[27]高等数学上册.同济大学数学教研室编.1996年第四版:392-396.
[28]C.H.Teh,R.T.Chin.On the detection of dominant points on digital curves[J].IEEE Trans.Pattern Anal.Mach.lntell.1989,11(8)
[29]肖轶军,丁明跃,彭嘉雄.基于B样条模型的曲线特征点检测法.数据采集与处理,2000:15(4):421-425.
[30]张文景,许晓鸣,丁国骏,杨煜普.一种基于曲率提取轮廓特征点的方法[J].上海交通大学学报,1999,33(5):592-595.
[31]陈燕新,戚飞虎.一种新的提取轮廓特征点的方法.红外与毫米波学报,1998,17(3):171-176.
[32]孙兆林.MATLAB 6.x图像处理.清华大学出版社.2002
[33]Sven Loncaric."A Survey of Shape Analysis Techniques"[J].Pattern Recognition,1998,31(8):983-1001.
[34]Dengsheng Zhang,Guojun Lu."Review of Shape Representation and Description Techniques"[J].Pattern Recognition 2004,37:1-19.
[35]孙即祥.模式识别中的特征提取与计算机视觉不变量[M].北京,国防工业出版社,2001.9.
[36]Jukka livarinen,Markus Peura,Jaakko Srel,and Ari Visa."Comparison of Combined Shape Descriptors for Irregular Objects"[C].In Proceedings of the 8th British Machine Vision Conference,volume 2,pages 430-439,University of Essex,UK,Sept.8-11 1997.
[37]Milan Sonka,Vaclav Hlavac,and Roger Boyle.图像处理、分析与机器视觉(第二版)(影印版)[M].北京,人民邮电出版社,2002.1.
[38]S.Wang,P.Chen,and W.Lin."Invariant pattern recognition by moment Fourier descriptor"[J].Pattern Recognition,1994,27:1735-1742.
[39]姚文君.基于Freeman链码二维图像轮廓的提取与匹配[N],宁波职业技术学院学报,2006,10(5):24-26
[40]Miri Weiss-Cohen,Yoram Halevi,Knowledge Retrieval for Automatic Solving of Jigsaw Puzzles[J]IEEE,2005
[41]李庆扬,王能超,易大义.数值分析.清华大学出版社,施普林格出版社.2001:13-33.
[42]刘玉兰.光栅图像矢量化技术研究[D].首都师范大学硕士学位论文.2005年.
[2]亦凡.用面向对象方法开发拼图处理和实现方法[J].电脑编程技巧与维护,2005(9):34-35
[3]张成海,唐双春.在AutoCAD下实现自动拼图[J].机械,第30卷增刊,2003:199-200.
[4]屠红蕾,黄静.基于K段主曲线算法的手绘形状识别[J].计算机应用,2009,29(2):456-458.
[5]吕玉增,彭启民,黎湘.基于极值特征的不变性形状识别[J].电子学报,2008,36(4):679-684.
[6]夏敏,刘宏申.基于小波描述子和神经网络的形状识别[J].计算机技术与发展,2007,17(3):106-108.
[7]周振环.基于角点特征的形状识别[J].计算机工程,2007,33(6):22-26.
[8]张波,邹建成,刘旭丽.一类新的V描述子在形状识别中的应用[J].计算机辅助设计与图形学学报,2007,19(7):920-926.
[9]Freeman,Garder.Apictorial Jigsaw Puzzles:The Computer Solution of a Problem in Pattem Recognition[J].IEEE Transactions on electronic computers,1964,118-127
[10]David A.Kosiba,Pierre M.Devaux,Sanjay Balasubramanian,etc.An Automatic Jigsaw Puzzle Solver[J].IEEE,1994,616-618
[11]M.G.Chung,M.Fleck,D.A.Forsyth.Jigsaw puzzle solver using shape and color[J],in:Proc.ICSP'98,1998,pp.877-880.
[12P N Suganthan.Solving jigsaw puzzles using Hopfield neural networks[J].IEEE(1999 ) 3745-3749.
[13]David Goldberg,Christopher Malon,Marshall Bern.A global approach to automatic solution of jigsaw puzzles[J].Computational Geometry 28,2004165-174..
[14]Min Gyp Chung,Margaret M.Fleck,David A.Forsyth.JIGSAW PUZZLE SOLVER USING SHAPE AND COLOR[J].Proc.ICSP'98,1998,pp.877-880.
[15]Roger W.Webster,Paul S.LaFollette,Robert L.Stafford.Isthmus Critical Points for Solving Jiagsw Puzzles in Computer Vision[J].IEEE,1991,1271-1278.
[16]陈希.基于内容的图像检索技术及其应用研究.武汉理工大学硕士学位论文.2008.04
[17]章毓晋.基于内容的视觉信息检索[M].北京,科学出版社,2003.5,62,94-95,118-123.
[18]李向阳,庄越挺,潘云鹤.基于内容的图像检索技术与系统[J].计算机研究与发展,2001.3,38(3):344-354.
[19]T.S.Huang,S.Mehrotra,and K.Ramchandran."Multimedia analysis and retrieval system(MARS)project"[C],in Proc of 33rd Annual Clinic on Library Application of Data Processing - Digital Image Access and Retrieval,1996.
[20]Wei-Ying Ma,B.S.Manjunath."NeTra:A toolbox for navigating large image databases"[J].Multimedia Systems 1999,7:154-198.
[21]Hongjiang Zhang."Relevance Feedback in Content-Based Image Retrieval".[EB/OL]http://research.microsoft.com/asia.
[22]郑南宁.计算机视觉与模式识别[M].北京,国防工业出版社,1998.80.
[23]井上诚喜等著,白玉林译.C语言使用数字图像处理[M].北京:科学出版社,2003.87-91.
[24]章毓晋.图像工程(中册)图像分析[M].北京,清华大学出版社,2005.10,369-377.
[25杨淑莹.VC++图像处理程序设计[M].北京,北方交通大学出版社,2003.79-80,148-149.
[26]崔凤魁,张丰收,白露,许荣海.二值图像目标领域点法边界跟踪算法[J].洛阳工学院学报,2001,22(1):28-34.
[27]高等数学上册.同济大学数学教研室编.1996年第四版:392-396.
[28]C.H.Teh,R.T.Chin.On the detection of dominant points on digital curves[J].IEEE Trans.Pattern Anal.Mach.lntell.1989,11(8)
[29]肖轶军,丁明跃,彭嘉雄.基于B样条模型的曲线特征点检测法.数据采集与处理,2000:15(4):421-425.
[30]张文景,许晓鸣,丁国骏,杨煜普.一种基于曲率提取轮廓特征点的方法[J].上海交通大学学报,1999,33(5):592-595.
[31]陈燕新,戚飞虎.一种新的提取轮廓特征点的方法.红外与毫米波学报,1998,17(3):171-176.
[32]孙兆林.MATLAB 6.x图像处理.清华大学出版社.2002
[33]Sven Loncaric."A Survey of Shape Analysis Techniques"[J].Pattern Recognition,1998,31(8):983-1001.
[34]Dengsheng Zhang,Guojun Lu."Review of Shape Representation and Description Techniques"[J].Pattern Recognition 2004,37:1-19.
[35]孙即祥.模式识别中的特征提取与计算机视觉不变量[M].北京,国防工业出版社,2001.9.
[36]Jukka livarinen,Markus Peura,Jaakko Srel,and Ari Visa."Comparison of Combined Shape Descriptors for Irregular Objects"[C].In Proceedings of the 8th British Machine Vision Conference,volume 2,pages 430-439,University of Essex,UK,Sept.8-11 1997.
[37]Milan Sonka,Vaclav Hlavac,and Roger Boyle.图像处理、分析与机器视觉(第二版)(影印版)[M].北京,人民邮电出版社,2002.1.
[38]S.Wang,P.Chen,and W.Lin."Invariant pattern recognition by moment Fourier descriptor"[J].Pattern Recognition,1994,27:1735-1742.
[39]姚文君.基于Freeman链码二维图像轮廓的提取与匹配[N],宁波职业技术学院学报,2006,10(5):24-26
[40]Miri Weiss-Cohen,Yoram Halevi,Knowledge Retrieval for Automatic Solving of Jigsaw Puzzles[J]IEEE,2005
[41]李庆扬,王能超,易大义.数值分析.清华大学出版社,施普林格出版社.2001:13-33.
[42]刘玉兰.光栅图像矢量化技术研究[D].首都师范大学硕士学位论文.2005年.