（计算机应用技术专业论文）足迹比对算法的研究与实现.pdf

摘要 由于足迹具有相对稳定、可认定人身份、现场提取率高等特点，因此足迹识别技术在公安 及安全等相关部门的工作中有着重要的作用。传统的足迹识别更多的依赖于人的经验，存在着 明显的判断不稳定性，使其难以发挥真正有效的作用因此利用图像处理与识别等相关技术进 行足迹自动识别具有重要的意义足迹比对算法作为足迹自动识别系统中的关键部分，成为研 究的重点。 本课题在对足迹自动识别系统中的图像预处理，边缘检测及轮廓跟踪研究的基础上，重点 对特征提取和比对检索算法进行了研究，提出了一种基于方向熵索引的比对检索算法。由于该 方法与直接基于几何特征值的图像检索方法相比能够快速确定和缩小检索范围，因此大大提高 了足迹比对检索算法的效率。经大量实例验证，结果表明本文提出的算法具有较高的查准率和 查全率。 在足迹和鞋底图像预处理方面，通过灰度修正和灰度去噪增强图像的清晰度；针对鞋底图 像和足迹图像不同的特点，采用了不同灰度修正方法。 对于足迹和鞋底图像边缘检测和轮廓跟踪，通过对大量图像进行研究，发现采用c a n n y 算 子对足迹图像和鞋底图像进行边缘检测。效果优于其他边缘检测算子；针对轮廓跟踪记录的 f r e e m a n 链码在图像几何变换时会发生变化的缺点，利用最小和方向统计码( m s s d c ) 的几何 变换不变性和尺度变换成比例等特点，将其应用于足迹花纹轮廓描述中，并以此构造与m s s d c 相应的方向熵。根据方向熵对四种花纹类型进行识别。本文还对波折型花纹的特征提取进行了 研究，其中包括波长、振幅、间距等特征值的提取。 在上述研究的基础上，初步实现了足迹自动识别系统的部分功能，构建了相应的数据库。 关键词：足迹比对，边缘检测，特征提取，方向熵索 l l a b s t r a c t f o o t p r i n ti sr e l a t i v e l ys t a b l e ，p e r s o ni d e n t i f i a b l ea n dh a st h eh i g hs p o te x t r a c t i o nr a t e ，t h e r e f o r e ， f o o t p r i n ti d e n t i f i c a t i o ni nt h ew o r ko f t h er e l e v a n td e p a r t m e n t sh a sa l li m p o r t a n te f f e c t b u tt r a d i t i o n a l f o o t p r i n ti d e n t i f i c a t i o ni sm o r ed e p e n d e n to nt h eh u m a ne x p e r i e n c e ，a n de x i s t sas e r i o u sa m b i g u i t y , w h i c hm a k ei td i f f i c u l tt ob r i n gi n t oe f f e c t t h eu o fi m a g ep r o c e s s i n ga n di m a g ei d e n t i f i c a t i o n a n d o t h e rr e l a t e dt e c h n o l o g i e st og a r r yt h r o u g ht h ea u t o m a t i cf o o t p r i n ti d e n t i f i c a t i o nh a sa l li m p o r t a n t r e s e a r c hm e a n i n g a st h ek e yc o m p o n e n to ft h ea u t o m a t i cf o o t p r i n ti d e n t i f i c a t i o ns y s t e m ，t h e a l g o r i t h mo f f o o t p r i n tc o m p a r i n gh a sb e c o m et h ef o c u so f t h es t l l d y o nt h eb a s i so f t h ei m a g ep r e p r o e e s s i n g , e d g ed e t e c t i o na n dc o n t o u r st r a c k i n gi nt h ea u t o m a t i c f o o t p r i n ti d e n t i f i c a t i o ns y s t e m ，t h es u b j e c tt a k e st h e f e a t u r ee x t r a c t i o n ，c o m p a r i n ga n dr e t r i e v a l a l g o r i t h ma st h ee m p h a s e st od i s c u s s t h e d i s s e r t a t i o np r o p o s e sa na l g o r i t h mo ff o o t p r i n tc o m p a r i n g a n dr e t r i e v a l l i n gb a s e do nt h ed i r e c t i o ne n t r o p yi n d e x ( d ei n d e x ) c o m p a r e dw i t ht h em e t h o do f i m a g er e t r i e v a lb a s e do ng e o m e t r i c a lf e a t u r e ，t h em e t h o dc a l li d e n t i 母a n dr e d u c et h er e t r i e v a lr a n g e r a p i d l y t h e r e f o r e ，i th a sg r e a t l yi m p r o v e dt h ee f f i c i e n c yo ff o o t p r i n tc o m p a r i n gr e t r i e v a la l g o r i t h m ，i t i s p r o v e dt h a tt h ea l g o r i t h mh a sh i g h r e c a l lr a t ea n dp r e c i s i o nr a t et h r o u g hal a r g en u m b e ro f e x a m p l e s t h es t u d yo ff o o t p r i n t sa n ds o l e si m a g ep r e p r o c e s s i n gi st oe n h a n c et h ei m a g ec l a r i t ym a i n l y t h r o u g ht h eg r a ya m e n d i n ga n dg r a yd e n o i s i n g t ot h ed i f f e r e n tc h a r a c t e r i s t i c so f t h ef a yl e v e lo f t h e s o l e si m a g e sa n df o o t p r i n ti m a g e sa c q u i s i t i o n , w et a k ed i f f e r e n tm e t h o d so ng r a ya m e n d i n g t h es t u d yo ff o o t p r i n ta n ds o l ei m a g ee d g ed e t e c t i o na n dc o n t o u rt r a c k i n gi sb a s e do nal a r g e n u m b e ro fi m a g e st e s t s u s i n gc a n n yo p e r a t o rt ot a k ef o o t p r i n t si m a g e sa n ds o l e si m a g e so ne d g e d e t e c t i o ni sb e t t e rt h a no t h e re d g ed e t e c t i o no p e r a t o r a c c o r d i n gt ot h ef r e e m a nc h a i nc o d e s h o r t c o m i n g sb yt h ec o n t o u rt r a c k i n gr e c o r d , an e ws h a p ed e s c f i p t i o nc o d i n gi sb e i n gs t u d i e d ：t h e s m a l l e s ta n dd i r e c t i o ns t a t i s t i c sc o d e ( m s s d c ) t h e n , w ec o n s t r u c tt h ec o r r e s p o n d i n gd i r e c t i o n e n t r o p y , a n dc a r r yo nt h ei n i t i a lc l a s s i f i c a t i o no ft h ef o u rt y p e sf l o w e rp a t t e r nu n d e rt h ed i r e c t i o n e n t r o p y t h ef o o t p r i n to fa u t o m a t i ci d e n t i f i c a t i o ns y s t e mi s p r i m a r i l yr e a l i z e da n dt h ed a t a b a s ei s s t r u c t u r e d k e yw o r d s ：f o o t p r i n tc o m p a r a t i o n ，e d g ed e t e c t i o n ，f e a t u r ee x t r a c t i o n ，d i r e c t i o ne n t r o p yi n d e x i l l 中国农业大学颈十学位论文第一章绪论 1 1 课题背景及研究意义 第一章绪论 足迹具有易留性、多发性、特定性、相对稳定性、反映性和连续性等特点，而且具有现场 提取率高等优点，一般为现场指纹提取率的5 7 倍，有着较高的应用价值。这些都使得足迹识 别在公安机关等相关部门工作中作用日益突出，但传统的人工识别操作更多的依赖于人的经验， 存在着严重的二义性，使其难以真正发挥其重要作用。利用图像处理及图像识别等相关技术进 行足迹自动识别，为足迹在相关部门工作中发挥其作用提供了更经济、更有效的途径，且充分 利用了计算机快速、高效的特点，解决了由人工识别带来的二义性等问题。 因此研究足迹自动识别具有重要的实际意义。而足迹比对作为足迹自动识别系统中的重要 内容，其比对检索算法具有重要的研究意义。 1 2 足迹识别系统国内外研究现状 1 2 1 国外研究现状 国外在足迹信息计算机管理方面研究工作开展得比较早，典型的产品有英国f r e e m a n 公司 的s i c a r ( s h o e p r i n ti m a g ec a p t u r ea n dr e t r i e v a l ) ，目前最新的版本s i c a r 4 1 1j ，该系统采用文本， 商标图形，花纹三种信息对鞋底花纹进行建库，功能较全，可以将现场鞋印在嫌疑人库，罪犯 库和鞋样库中查询并进行串并案，但录入过程对录入人员要求过高，分类过细，花纹信息及结 构安排共分为l o 类：有圆形、多边形、规则形、不规则形、锯齿形、网状、结构形、边缘形和 一般形等，而仅圆形又分为4 0 余种子类，不仅要求录入花纹，还要对它们之间的组合及结构信 息进行人工判断，对录入人员要求极高，易造成录入错误。 英m k 9 刑侦设备公司( k 9f o r e n s i cs e r v i c e sl t d ) 的t h et r e a d l m a r ks y s t e m o f a n a l y s i sa n df o o t w e a ri d e n t i f i c a t i o n ，能够实现人工干预条件下的自动花纹查询， 可用于嫌疑人鞋印在犯罪现场库中的比对，但对现场条件要求较高，同时识别率也偏低j 。 英国贝尔法斯特市皇后大学的计算机专家埃威安亚列格山德研制出的一种称为弗列克特尔 ( f t a d 的数据库系统【3 1 ，其总体工作程序是：将鞋印的压模通过扫描器或数字照相机输入计算机， 该系统就会自动在成千上万个储存的鞋印压模中进行搜索，系统会得出一个与你刚输进去的鞋印 最接近的模型。该系统是通过每个进入f r a c t a l 系统菜单的图像来进行搜索的，该系统由一系列复 杂的几何形状组成，这些几何形状在很大范围看上去一模一样，亚列格山德采用的数学方法，就 是根据其形状来描绘鞋印。在反复运用这种方法的过程中，复杂的f r a c t a l 系统即被简单的方程式 描绘下来，于是一种描绘鞋印的数学式即可从一个图像中产生出来。该系统的主要优点在于，不 需要把鞋子分为不同的类型，在一定程度上排除了人的主观性，不至于产生误导，可以少走许多 中国农业大学硕+ 学位论文 第一章绪论 弯路。但该系统是利用数学模型建构的，且是基于鞋印的压模的，对输入的图像有特定的要求， 在实际应用中较难得到推广 1 2 2 国内研究现状 解放军信息工程学院信息科学系田越、平西建教授等针对刑侦工作中立体足迹识别的要求 提出了三维表面的等值线特征提取。曲线形状的空间结构及自回归谱( a r 谱) 分析，以及基于曲 线形状分析的模糊模式识别方法，试验表明该方法用于三维表面识别效果明显hj 。这方面的研 究是综合了计算机视觉及人工智能理论的一个对于立体足迹的课题。 中国刑警学院史力民教授主持的课题足迹检验科学性的研究，是公安部资助项目，其 足 迹档案计算机管理系统i l l 尸, 于0 4 年5 月通过公安部鉴定，该系统中足迹信息查询采用文本查 询、花纹查询和两者结合查询功能，并对不同查询项目设置权值，给出它们的重要性指标和逻 辑关系，并提供了辅助分析，统计、报表等功能。该系统在信息录入过程中虽然通过鞋底花纹 在鞋底所处的部位和花纹的几何特征对鞋底花纹进行分类的方法解决了鞋底花纹分布随意性的 问题，但在具体部位的花纹特征还是通过人工录入，没有实现真正意义上的自动提取花纹特征， 没有真正意义上排除人工干预带来的录入信息不准确，存在主观性等问题。 大连海事大学信号与图像处理研究所采用概率统计技术、多尺度小波边缘检测技术、基于 纹理等特征1 5 1 的方法、基于模式识别【6 1 等技术对鞋底花纹分类的自动识别和分类算法进行了研 究，同时对足迹图像的增强和分割技术初步有所研究j 。 大连恒锐图像技术有限公司开发的“恒锐足迹分析与比对系统”是基于刑事侦察工作实际， 充分利用公安内部网络资源，发挥足迹在刑事侦察和串并案件的突出作用而研制开发的产品。 在公安系统中已经得到了较好的应用p j 。但随着科学技术的发展，结合用户的反馈信息，目前 该系统存在着这样一些技术问题：( 1 ) 该系统在各种足迹图像的录入过程中，需要人机交互地 形式来录入花纹形状，需要比较大的工作量；( 2 ) 人工录入过程中识别花纹类型容易产生二义 性，对查询效果有一定的影响。而且对于操作人员的专业要求也较高，不利于系统的充分利用； ( 3 ) 相似匹配时间效率不高。 1 3 足迹比对的基础 1 3 1 鞋底花纹分类 鞋底花纹分类方法不是着眼于足迹和鞋底的精确匹配，而是为了减少足迹在一对多模式下 匹配时的搜索量，尤其是在大型数据库中。这种分类是很必要的。由于鞋底花纹种类繁多，如 果将鞋底花纹类型分的过多过细，会浪费系统资源，不利于信息的检索，如果花纹类型分得过 少过粗，足迹图像在鞋库图像中比对检索的时候，会增加检索子范围的图像数目，耗时增加。 本文对鞋底花纹类型分类的采用下列标准： 1 波折型 由波峰、波谷相连的曲线或折线围成的花纹。波折型花纹至少由一个波峰一个波谷，花纹 2 中国农业大学硕士学位论文 第一章绪论 i 整体均匀。见图卜1 。 图1 1 波折型花纹 2 类圆型 由圆型、椭圆型或圆环型构成的花纹，花纹面积大于0 5 c m x o 5 c a 。见图l - 2 。 图1 2 类圆型花纹 3 边块型 由多条直线或曲线构成边块型花纹，花纹面积大于0 5 c m x o 5 c m ，图形宽度大于0 5 c m 。 见图卜3 。 图卜一3 边块型花纹 3 中国农业大学硕士学位论文第一章绪论 4 图文型 由具有标识性质的图案( 或文字) 组成的花纹见图1 - 4 。 图1 - - 4 图文型花纹 5 线条型 由直线或曲线组成的花纹，线条互不相交。线条的宽度小于0 5 0 n 。见图l _ 5 图1 5 线条型花纹 6 交织型 由数根线条构成的相交或经纬相互沉浮穿插组成的花纹见图l - 6 。 图1 - - 6 交织型花纹 4 中国农业大学硕士学位论文 第一章绪论 7 点状型 由多个细小点块状凸起组成的花纹，花纹面积小于0 5 e r a 0 5 c m 。见图卜7 8 其它型 除上述1 7 类之外的花纹。 1 3 2 鞋底花纹分区 图1 - 7 点状型花纹 柯少卿等人在对鞋印分块分类研究中 9 1 ，在对鞋底花纹进行纹理分类的前期图像预处理过 程中，将图像分块，每块大小为6 4 x 6 个像素，整幅鞋底分为1 3 x 5 块，鞋印图的标准大小为 8 3 2 3 2 0 ，对分好块的区域进行标号，在此基础上进行纹理分块分类。这种处理方法一方面加 大了工作量，降低了效率；另一方面，由于分块过多，必然会导致有些方块得到的信息不完整。 课题采集了4 0 0 多幅左右的鞋底图像，采集了1 0 0 幅左右的足迹图像，其中大概1 5 0 幅左 右的带有波折型花纹的鞋底图像，其中鞋的生产厂家包括：n i k e ，a d d i d a s ，锐步，安踏，欢腾， k a p p a , e l l e 等。对于波折型花纹的鞋的类型大多为运动、休闲类的图l 一8 和图l 一9 是采集 的一些鞋底图像和足迹图像的样本 图1 - 8 采集足迹图像样本 5 中国农业大学硕士学位论文第一帝绪论 图1 - 9 采集鞋底图像样本 通过观察鞋底图像和包含较为完整信息的足迹图像，结合文献【9 】关于鞋印库鞋印长宽比， 将图像分为下列6 个区，区域划分如图卜1 0 。其中，0 区是脚尖，l 区是脚掌中部，2 区是脚跟， 3 区是脚弓处，4 ，5 区分别为脚掌左、右围边。对于足迹比对来说，考虑到实际过程中采集到 足迹的信息，可知道l 区脚掌中部和2 区脚跟处为比对时重要区域处对于3 区脚弓处，对于 一些鞋，由于设计的时候这部分是呈弓形的，所以存在对应足迹图像在这个区域是没有信息的， 而对于像运动鞋、休闲鞋等，所对应的图像在这个区域有诸如商标等重要信息，是不可忽略的 区域。采集到的足迹图像在这六个区域都有可能会出现信息不全的情况，但通过对采集的人量 图像进行观察，脚掌区域和和脚跟区域应该作为重点处理，在比对时所占的权值比重也应较大。 图卜1 0 分区域示例圈 图1 - 1 0 中比例，整个区域的长宽比是( 1 5 + 4 5 + 3 + 4 ) ：5 - - 2 6 ，4 区域、l 区域和5 区域的 宽度比是1 ：3 ：1 。 6 中国农业大学硕十学位论文 第一章绪论 1 4 本课题研究内容 本课题主要对足迹识别系统中足迹比对算法进行研究，并对足迹图像和鞋底图像预处理、 边缘检测及轮廓跟踪、特征提取进行研究。具体工作主要有： ( i ) 对足迹图像和鞋底图像进行预处理。针对采集到的足迹图像和鞋底图像不同特点，研 究采用不同方法对图像灰度进行修正，改善图像质量。 ( 2 ) 采用合适的边缘算子对足迹图像和鞋底图像进行边缘检测。在边缘检测基础上，对轮 廓进行跟踪，记录链码值。并针对f r e e m a n 链码描述轮廓的缺点，研究改进方法。 ( 3 ) 对足迹图像和鞋底图像进行特征提取。特征提取从统计特征和精确特征两方面探讨研 究。 ( 4 ) 在对图像特征提取的基础上，对足迹比对算法进行研究，提出一种算法，能实现足迹 图像和鞋底图像库中鞋底图像高效检索比对。 ( 5 ) 在算法研究的基础上，开发足迹识别系统的初始版本，搭建数据库，对算法进行验证。 7 中国农业大学硕士学位论文 第二章鞋底和足迹图像预处理 第二章鞋底和足迹图像预处理 足迹识别是基于足迹和鞋底图像特征的，无论采用何种特征表示，其特征提取的方法都在 不同程度上依赖于图像质量。因此鞋底和足迹图像预处理是足迹识别中非常重要的一步，它的 好坏直接影响特征提取和比对效果，针对不同的图像特征有不同的预处理方法，所采取的步骤 和处理量也不同。 本文采用的预处理过程分为三个步骤进行：彩色图像的灰度化处理、图像的灰度修正、灰 度图像的去噪处理。其中彩色图像处理是将读入的彩色鞋底图像和足迹图像根据公式转换为灰 度图像。图像的灰度修正和平滑操作均属于图像的增强技术。图像增强技术是数字图像处理过 程中经常采用的一种方法。为了改善视觉效果或者便于人和机器对图像的理解和分析，根据图 像的特点或存在的问题采取的简单改善或者加强特征的措施称为图像增( i m a g ee n h a n c e m e n t ) 。 图像增强技术通常有两类方法：空间域法和频率域法。空间域法主要是在空间域中对图像像素 灰度值直接进行运算处理。频率域法是在图像的某种变换域中( 通常是频率域中) 对图像的变 换值进行某种运算处理，然后变换回空间域。本文经过研究探讨，针对采集的足迹图像和鞋底 图像的特点，采用了不同的灰度修正方法。在灰度修正的基础上，运用中值滤波技术对灰度图 像进行平滑处理，将背景噪声干扰减少到最小程度，同时增加了图像的对比度。 整个预处理过程是为了使鞋底和足迹图像画面清晰，边缘明显，突出图像中的某些信息， 削弱或除去某些不需要的信息，使它的结果对后面的识别来说比原始图像更合适，以便后期准 确提取特征进行比对。下面对预处理中的每一步分别进行介绍。 2 1 彩色图像的灰度化处理 由于鞋底和足迹图像比对所关心的主要是图像花纹的形状信息，与颜色关系不久，而灰度 图像使用起来比彩色图像简单，因此本文主要对灰度图像进行处理。但是，足迹识别中的原始 采集的鞋底图片和足迹图片，均是彩色图像，所以预处理中首先需要将采集到的彩色图像转换 成灰度图像。 1 彩色图像 在数字图像处理中，实际中最通用的彩色模式就是r g b ( g e 、绿、蓝) 模型。在r g b 彩色 模式中，所表示的图像由3 个图像分量组成，每一个分量图像都是其原色图像。在r g b 空间， 用以表示每个像素的比特数叫做像素深度。考虑r g b 图像，其中每一幅红、绿，蓝图像都是 一幅8 比特图像，在这种条件下，每一个r g b 彩色像素( r 、g 、1 3 ) 值3 个一组称为2 4 比特深 度0 i 。 2 灰度图像 灰度图是指只含亮度信息，不含色彩信息的图像，就像平时看到亮度由暗到明的黑白照片， 8 中国农业大学硕十学位论文第二章鞋底和足逊嘲像颅处理 亮度变化是连续的。因此，要表示灰度图，就需要把亮度值进行量化。通常划分为0 2 5 5 共 2 5 6 个级别，0 最暗( 全黑) ，2 5 5 最亮( 全白) ，是一幅8 比特图像。 b m p 格式的文件中并没有灰度图这一个概念，但是可以很容易的用b m p 文件来表示灰度 图。方法是用2 5 6 色的调色板，只不过这个调色板有点特殊，每一项的r g b 值都是相同的， 也就是说r g b 从( 0 ，0 ，o ) ，( 1 ，1 ，1 ) 一直至j ( 2 5 5 ，2 5 5 ，2 5 5 ) 。( o ，0 ，0 ) 表示全黑色，( 2 5 5 ， 2 5 5 。2 5 5 ) 表示全白色，中间的是灰色这样，灰度图就可以用2 5 6 色图来表示了 灰度图像使用比较方便。首先，r 、g ，b 分量的值都一样；其次，图像数据即调色板索引 值，也就是实际的r g b 的亮度值；另外，因为是2 5 6 色的调色板，所以图像数据中一个字节 代表一个像素j 。 3 彩色图像到灰度图像的转换 由彩色转换为灰度的过程叫做灰度化处理。一般情况下彩色图像每个像素用三个字节表示， 每个字节对应着r ，g ，b 分量的亮度( 红、绿、蓝) ，转换后的灰度图像的一个像素用一个字 节表示该点的灰度值，它的值在0 2 5 5 之间，数值越大，该点越白，即越亮，越小则越黑。转 换公式为 g r a y ( i ，) = o 2 9 9 r ( i ，) + o 5 8 7 x g ( ，) + o 1 1 4 x b ( i ，_ ，) ( 2 - - 1 ) 其中g r a y ( i ，j ) 为转换后的灰度图像在( f ，j ) ) 点处的灰度值1 ”。 2 2 图像的灰度修正 灰度修正是图像在空间域中增强的简单而有效的方法。通常根据图像不同的降质现象而采 用不同的修正方法。它能使图像具有期望的灰度分布，从而有选择的突出所需要的图像特征。 1 灰度直方圈 在数字图像处理中，一种简单且有用的工具是灰度直方图。它概括了一幅图像的灰度级内 容。灰度直方图是灰度级的函数，描述的是图像中具有该灰度级的像素的个数，其横坐标是灰 度级，纵坐标是该灰度出现的频率( 像素个数) 。其表达公式如2 - - 2 ，其中n 为图像中总的像 素个数： p a r , ) = 生 玎 ( 2 2 ) 任何一幅图像的灰度直方图都包括了可观的信息。如图2 - 1 和图2 2 分别是鞋底图像和足 迹图像及其他们所对应的灰度直方图。 9 中国农业大学硕十学位论文第二章鞋底和足迹图像预处理 2 灰度直方图修正 图2 - 1鞋底图像及其灰度直方围 图2 - 2 足迹图像殛灰度直方国 灰度直方图修正是图像点运算的应用。在图像处理中，点运算是简单却很重要的一类技术， 它们能让用户改变图像数据占据的灰度范围。对于一幅输入图像，经过点运算( p o i n t o p e r a t i o n ) 将产生一幅输出图像，后者的每个像素点的灰度值仅由相应输入像素的值决定( 这种方法与局 部运算的差别在于，后者每个输出像素的灰度值由对应输入像素的一个邻域内几个像素的灰度 值决定) 。因此，点运算并不改变图像内的空间关系 为方便起见，本文明确在下面的讨论中，以r ，s 分别表示原图像和经直方图修正后的图像 灰度值。即：0 r 。j 1 在 0 。1 区间内的任何一个r 值，都可以产生一个s 值，且 1 0 中国农业大学硕七学位论文 第二章鞋底和足迹图像预处理 j = 丁( ，1 ( 2 3 ) t 为变换函数。r p ) 满足下列条件： ( 1 ) 在0 ，1 区间内是单调递增函数； ( 2 ) 在0 ，1 区间内，有0 t ( r ) 1 。 条件( 1 ) 保证灰度级从黑到白的次序不变，条件( 2 ) 确保映射后的像素灰度在允许的范围内。 反变换为： ，= t 1 ( s 1 ( 2 4 ) 丁- 1 ( j ) 对s 同样满足上述条件。 由概率论知，若且( ，) 和变换函数s = t ( r ) 已知，t 1 ( j ) 是单调增长函数，则变换后的图 像的概率密度函数p a s ) 如下式所示： 见( s ) 2 n ( ，) 鱼丁一= 【p ，( ，) d 出r a s 脚- l ( ，) ( 2 - 5 ) 5 口j 7 ( 一1 通过变换函数t ( r ) 可以控制图像灰度级的概率密度函数，从而改变图像的灰度层次。这就 是直方图修正技术的基础。 2 2 1 灰度直方图均衡化 灰度直方图均衡化，是把给定图像的直方图分布改造成均匀灰度直方图分布。直观的讲， 灰度直方图均衡化导致图像的对比度增加，在一些图像中，感兴趣的特征仅占整个灰度级相当 窄的一个范围。直方图均衡化可以扩展感兴趣特征的对比度使之占据可显示灰度级的更大部分。 灰度直方图均衡化是以累积分布函数变换法为基础的灰度直方图修正法 1 3 1 。假定变换函数 为： 0 j = r ( ，) = i p ，( v m ；(2-6) 其中国是积分变量，而s p ，( 矽国就是r 的累积分布函数( c d f ) 。这里，累积分布函数就 o 是r 的函数，并且单调地从0 增加到1 ，所以这个变换函数满足关于r o ) 在0 ，1 内单调增 加，在0 墨，l 内有0 s r ( r ) 1 的两个条件。 对式( 2 6 ) 的r 求导，则 再把结果代入式( 2 5 ) ，则 _ d s ：p x ，) a r ( 2 7 ) 中国农业大学硕十学位论文 第二帝鞋底和足迹嘲像预处理 k ( 珍。d r l ： l c l sj r 。r 1 ( ，) 晰歪1l = 而1 “ q - s ， d rj ，。r ( ， 由上面的推导可以看出，在变换后的变量s 的定义域内的概率密度是均匀的由此可见， 用r 的累积分布函数作为变换函数可以产生一幅灰度级分布具有均匀概率密度的函数。其结果 扩展了像素取值的动态范围 前面叙述的修正法是以连续随机变量为基础进行讨论的。正如前面谈到的那样，为了对图 像进行数字处理，必须引进离散形式的公式。当灰度级是离散值的时侯，可以用频数近似代替 概率值，即： p a r d = 旦0 - 5 - 1k = o ，1 ，2 ，一l ( 2 9 ) 式中，是灰度级的总数目，p , ( r k ) 是取第k 级灰度值的概率，是在图像中出现第k 级灰 度的次数，n 是图像中像素总数。 式( 2 6 ) 的所对应的离散形式可由下式表示： s = r ( ) = 詈= 只( ) o o lk = 0 ，1 ，2 ，z 一1 p 0 ” j 2 0 ( 2 - - 1 0 ) 其反变换式为r k = t - 1 ( & ) 。 图2 _ 3 鞋底图像直方图均衡化图像及灰度直方图 1 2 中国农业大学硕+ 学位论文第二章鞋底和足迹嘲像预处理 围2 - 4 足迹图像直方图均衡化图像及灰度直方图 图2 3 、2 - 4 分别为图2 - 1 中鞋底图像和图2 2 中足迹图像进行灰度直方图均衡处理后图 像及其灰度直方图。分别与原灰度图像比较，可以看出，经过直方图均衡后，鞋底图像的对比 度大大提高，处理后的鞋底图像对应的灰度分布也趋于均匀，效果较好。但对于足迹图像来说， 在增大图像对比度的同时，对部分区域灰度加重，导致该部分区域图像形状不清晰，效果较差。 分析原因，主要是因为足迹图像相比鞋底图像采集条件比较复杂，故需要进行灰度拉伸对足迹 图像进行分区域调整。 2 2 2 灰度拉伸 灰度拉伸的基础是灰度的线形变换。灰度的线性变换就是将图像中所有的点的灰度按照线 性灰度变换函数进行变换。图像的线性变化是这样定义的： 假定原图像，( x ，y ) 的灰度范围为【a , b 】，变换后的图像g ( x ，y ) 的灰度范围线性的扩展至 【c ，d 】则对于图像中的任一点的灰度值，o ，y ) ，变换后为g ( x ，y ) 。数学表达式如公式( 2 1 1 ) 所示。 g ( w ) ：孚兰i f ( x , y ) - a + c 灰度拉伸是分段进行的线性变换，它的灰度变换函数如图2 - - 5 所示，函数表达式如下： g ( x ，y ) = c x f ( x ，y ) ，0 f ( x ，y ) 口 _ d 一- c ( x ，y ) 一口】+ c ，口厂( x ，y ) - b ( 2 1 2 ) d 一口 丽2 5 5 i - d 【m ，y ) 一小d ，6 1 ) 物体灰度区间以改善图像：同样如果图像灰度集中在较亮的区域而导致图像偏亮，也可 以用灰度拉伸功能来压缩( 斜率 0 ，判为b 类 ( 2 ) t t 时，就认为存在一条直线：其起点可根据链码起点 ( ，y ) 与口在，中的位置得到；其方向与链码方向口一致：长度为e 。这是存在理想直线的 情况。 判据2 。对，中的链码段口到d ，若满足以下条件，也认为存在一条直线l ； ( 1 ) 这段链码中只有两个方向皿，d ，交替出现； ( 2 ) d l ，d ，为最相邻的两个链码方向； ( 3 ) p 到2 的统计数据之和c t tc = q ，k = f ，j 这是两个跟踪方向交替出现的情况。 因此，对直线段而言，它在链码上表现为一定范围内只出现个方向，或两个方向交替出 现，最多有两个码值组成并且两个码值间差。如果检测到满足以上特征的目标边缘，则判断为 直线型。 根据直线段的判据，可以进一步得到弧线边缘的判据。弧线型可以在大的范围里看成由三 个方向相邻的直线段组成，因此弧线型的链码数目等于3 ，弧线型链码特征是去掉水平或垂直 方向的指向符后只剩下两个方向的指示符，每个指示符连续有一定的数目，此两个方向的指示 符不交替出现，并且水平或垂直指向符连续出现的次数多于8 ，符合以上条件，则可判断为弧 线型| 5 】 在对直线和弧线判断依据的讨论基础上可以进一步得到折波和弧波的判断依据。此外，波 折型花纹根据花纹走向，有纵向波和横向波之分。 通过大量的试验观察得出波折型花纹的识别方法：对于波折类型的曲线链码首先除去水平 或垂直方向的指示符( 这两个方向表示的是线条的前进方向) ，剩下的应该只有两种指示符，每 种指示符连续应有一定的数目，这种指示符结束是另一指示符，并且指示符的变化次数至少为 2 ( 满足此条件说明曲线至少含有一个波峰和一个波谷) ，则据此判断为波折类型：进一步观察 原链码，根据原链码中包含的是表示水平还是垂直方向走向的指示符，来判断波折是横向波还 是纵向波；最后判断是弧波型还是折波型，如果原链码中水平或垂直的指示符连续出现的次数 大于某一数目( 根据试验本文此数目取为4 ，满足此条件的趋向波峰或者波谷过渡平滑) ，则判 断为弧波型，不满足则判断为折波型。 如图4 - - 7 所示，以鞋底图像为例详细说明波折型花纹的识别过程。 中国农业大学硕+ 学位论文 第叨章鞋底与足迹图像之间特秆匹配 图4 - 7 边缘提取过程图 试验中采用的原始灰度图像如图4 - 7 ( a ) ，c a n n y 算子检测后的图像如图4 - 7 ( b ) ，边界跟踪后 的图像如图4 - 7 ( c ) ，提取出最长的一条边缘如图4 - 7 ( d ) 来分析。 图4 - 7 ( d ) 边界跟踪后得到的链码是： 1 7 7 0 7 0 0 7 7 0 7 0 0 7 7 0 7 0 7 7 0 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 0 7 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 7 0 0 7 7 0 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 0 7 0 7 7 0 7 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 7 0 7 0 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 7 0 7 0 7 7 0 7 去掉原链码中存在的水平方向的指示符后得到链码： 1 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 1 1 1 l l l l l l l l l l l l l l 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 得到的链码就变成了由多个同向链码的组合，同向链码就表示直线段，而且得到的同向链 码只有两种指示符，指示符的变化是7 一 l 一 7 一 l - - 7 ，变化次数为4 ，原链码中存在的是 表示水平方向的指示符0 ，且0 连续出现的次数没有超过设定阂值4 ，根据上述分析的这些特征， 原图选定的区域可以判定为波折型花纹中的折波型，波纹走向为横向。 2 波折型花纹的特征提取 一般意义上的机械波如图4 - 8 所示，波长定义为两个相邻波峰( 或波谷) 间的距离。振幅 为图中a 。 l 4 广 d 6 v ； 口 图4 8 机械波 本课题中，考虑到大多数鞋底图像的具体情况，取图4 9 中用红线标明的为一个完整波 4 0 中国农业大学硕士学位论文第四章鞋底与足迹图像之间特征匹配 折形： 图4 - 9 鞋底图像的完整波折定义 如图4 _ 9 所示，a 点处为波峰，b 点处为波谷，点a 和点b 之间的水平距离( 即在x 方向 上的投影距离) 为波长的一半，点a 和点b 之问的垂直距离( 即在y 方向上的垂直距离) 为 振幅的两倍，所以在具体过程中，根据前面的边界跟踪后得到的链码值，求得a b 点之间的水 平距离和垂直距离，进而求得这个波折的波长和振幅，对于鞋底和足迹图像的特征提取区域来 说，通过求取多条波折的波长和振幅，求其均值，作为该区域波折型花纹的波长和振幅特征值 标识。 波长和振幅标识的单条波折线的特征，而具体的鞋底图像区域中还存在着一个重要的几何 特征值，即上下( 对应于横向波折) 或者左右( 对应于纵向波折) 波折的间距。如图4 - - 1 0 所 示，点c 和点d 之间的距离即为上下波的间距。 图4 - 1 0 鞋底图像波间距定义 在具体求取过程中，只需要根据已经记录的两条波折的链码，来求得波折上的点的坐标， 进而求取上波折，和下波折m 横坐标相同( 对于横向波折) 或纵坐标相同( 对于纵向波折) 点 的纵坐标或者横坐标差值。对于鞋底和足迹图像的特征提取区域来说，通过求取多个波折的间 距，求其均值，作为该区域的间距特征值标识。 上述过程求得的特征值都以像素为单位，通过读取图像文件的分辨率属性，来转换为实际 的长度度量单位。 3 特征提取的计算基础 从链码可以得出边界的许多形状特征嘲： ( 1 ) 链的长度 工= 吃+ n o 互( 4 8 ) 其中，表示方向链中偶数码的数目，表示奇数码的个数。奇数码用互的权重修正后， 边界的长度检测时可以弥补图像离散化的误差。 ( 2 ) 边界所表示区域的宽度和高度 4 l 中国农业大学硕士学位论文 第四蕈鞋厩与足迹图像之同行衍匹雕 设方向链为 q 呸吗吒 ，定义q 在x 轴上的分量为，在y 轴上的分量为，则： q = 0 时，= l ，= o q = l 时，= l ，= l q - - 2 时，= 0 ，= l q = 3 时，= 一l ，= l a j = 4 时，= 一l ，= 0 q = 5 时，= 一l ，勺= 一l a j = 6 时，= o ，= 一l q = 7 时，= l ，= 一l 设而和是起始点的坐标，则： ，= m 警( + 而) 一叩( + 而) t = i k = 1 i = m ( + ) 一中( + ) ( 4 9 ) k = l k = l ( 其中，表示宽度，矗表示高度) ( 3 ) 假如两个像素点可由方向链码连接 q 啦吩a 3 ，则这两点的距离为： 4 特征提取实例分析 d = 图4 - 1 1 特征提取示意图 ( 4 1 0 ) 由图4 - 7 提取的链码得到，图4 - 1 1 波折a b e 之间的链码表示为： 1 0 1 0 0 1 0 1 0 0 l o l 0 0 1 0 l o l 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 7 7 7 0 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 0 7 7 0 7 0 7 0 7 0 7 0 7 7 0 中国农业大学硕+ 学位论文第四章鞋底与足迹图像之间特钉f 匹配 7