计算机拼图中形状识别算法研究

【作者】 史晶晶；

【导师】 葛庆平；

【作者基本信息】 首都师范大学 ， 计算机应用技术， 2009， 硕士

【摘要】 自动拼图(Automatic Puzzle Solver,APS)利用拼块的颜色、纹理和形状特征实现计算机对图像的自动拼接。拼图问题涉及到机器视觉、图像分析和模式识别等多个研究领域,需要形状描述、边界匹配、特征提取、相似性度量等很多机器视觉知识。此问题在考古学中的文物修复、公安机关的物证碎片复原以及生物研究等方面也有广泛的应用。本文在JPTV1.0(自动拼图软件1.0版本,拼图对象为计算机分割的拼块)的基础上,采用扫描仪摄入实际拼块进行研究。自动拼图教育游戏软件采用了集教育性和娱乐性为一身的游戏形式,浅显易懂地介绍和展示了基本的机器视觉技术原理和方法。形状信息是拼图中利用的主要信息之一,对于拼图最终的匹配效果起着十分重要的作用。本文针对形状这一特征进行了大量的研究。论文沿着拼图从实物扫描到最终的曲线匹配这一完整的流程一步步展开,研究内容主要体现在以下几个方面:1.研究了拼块图像的噪声处理方法,并得出了良好的结果。2.研究了图像轮廓的提取方法,并且将图像用链码及曲率两种方法进行表达。其中对于曲率的表达,比较了各种曲率计算方法,最后选定了一种简洁高效的闭合轮廓的曲率计算方法作为本文拼块形状表达所用。3.为了找到拼图形状匹配需要的各条边界信息,本文研究了各种角点检测算法,最后经过改进,提出基于链码的拼块角点检测算法和基于曲率的拼块角点检测算法,并给出了详细的比较与评价。4.分别就链码曲线和曲率曲线两种图像轮廓表达方式,结合动态规划的算法,提出基于链码的动态规划匹配算法和基于曲率的动态规划匹配算法对图像进行边界匹配。同时分别对不同的曲线表达方式给予了不同的相似性度量规则。最后通过实际的扫描拼图对以上算法进行测试,取得了90%以上的匹配正确率。结合颜色,纹理的参与,最终完成了拼图的正确拼接。更多还原

【Abstract】 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.更多还原