（计算机应用技术专业论文）基于形状特征的平面鞋印图像检索的研究.pdf

摘要 摘要 鞋印图像是一类具有特殊意义的计算机图像，它能够反映出鞋底外表的结构 特征。如何快速、准确地进行鞋印图像检验是刑事技术理论与实践的重要课题。 基于内容的平面鞋印检索利用图像处理、模式识别等技术实现快速、准确认定给 定鞋印与鞋印库中特定鞋印样本间的相似关系，这一研究对刑侦技术发展具有重 大意义。 本文通过深入研究鞋印图像的特征，设计开发“平面鞋印检索系统 。该系统 突破常规以经验为主的专家主观判断的局限，用量化的方法，提取鞋印轮廓特征， 根据轮廓特征进行鞋印图像检索，使鞋印检验理论和技术更加系统和客观。 本文主要围绕鞋印形状特征提取这一关键技术展开，提出基于外轮廓、内部 花纹形状特征的鞋印图像检索方法。所做工作主要包括以下四个方面： ( 1 ) 为了提高检索精确度，简化特征提取过程，给出了一种新的鞋印图像倾斜 校正方法，该方法根据鞋印图像最长轴和水平方向的夹角，将鞋印图像倾斜校正， 然后将鞋印进行分区以及建立坐标轴。 ( 2 ) 提出了基于各分区纵横比、特征点的外轮廓描述法。分区纵横比刻画了鞋 印的鞋尖区、鞋掌区、鞋弓区、鞋跟宽度与最长轴之间的比值；外轮廓特征点包 含拐点、切点，其中拐点是凹圆弧与凸圆弧的平滑过渡点，切点是凸凹圆弧与直 线之间的过渡点。 ( 3 ) 在已有轮廓特征提取算法的基础上，提出了基于距离、角度直方图的花纹 形状表示方法。该方法不仅能提取花纹的形状特征，而且也考虑了各花纹间的空 间位置关系，从而更准确地进行鞋印图像检索。 ( 4 ) 为了提高检索算法时间和空间效率，采用矢量量化方法，建立鞋印花纹特 征与码字的对应关系。每个不连通花纹特征可用与其对应码字的索引值和质心坐 标来表示。 本文提出的倾斜校正算法、轮廓特征提取等方法在平面鞋印图像检索系统中 得到运用，所开发的原型系统在实验中取得了很好的效果。 关键词：形状特征；轮廓特征；倾斜校正；花纹特征；图像检索 a b s 撕蕾c t i i l a b s t r a c t s 魏鼢si 麟l g e s 氇怼ac 董a s so fs 辨e 滋e o m 辨缸趣a 鲈s ，氇锣e 鑫n 托羹tm e s 协l c t u 蒯c h a r a c t e r i s t i c so fs o l e s a 1 ) p e a 啪c e h o wt oi i l s p i e c ts o l e sq u i c 姒y 砒l de x a c u y i s 鑫i 燃筘r 魄哦l a s k 南r 壤e o g 躲d 掰戚c eo ff l o r e 翦s i e 钕h l 玲l o g y t h ef e 菌e v 破o f c o m e n t 山嬲e dp l a n es o l e sm a l 【e su s eo f 油a g ep r c h c e s s i i l ga n dp a 吮mr e c o 鲥t i o n t e c l l l l i q u e st oi d e n t i 每w h e t l l e rt 董l es o l e sa r el e rb yc e r t a i ns h o e s ，w i l i c hi so fg 鹕a t s i 弘i 蠡c 铺c e | o 氆ed e v c l 卵麟雌o ff o l 优s i ct e c h n o l o 科 t h ep a p e rf o c u s e so nd e s i g l l i n ga n dd e v e l o p i n gt l l ep l a n es h o es o l e sr e t r i e v a l s y s e 撤臻r o 珏g hd e e p l y 瓣s e 鑫糙越魏g 睡ef e 氇纨羚so f 攮e l e s 妇a g e s 飘糖s o 是黼 d e v e l o p e db r e a k sm el i i i l i t o fp a y i n ga n e n t i o nt o c x p e r t s e x p e r i e n c e s na p p l i e s q 珏a n t i 缄i v cm e m o d s ，e 蹒l 甜e si n d i v i d u a ls u 酾e c t i v e 敝；t o r s 褫ds c a l e s s 商o l l s l y f 研o b t 蕊1 1 i n gm er e s u l t t h em e o 拶a 1 1 dt c c h n o l o g yo fs h o es l o e sr e c o g l l i t i o n a r e b e c o m i l l g m o r ea n dm o r es y s t e m a t i c 甜l do b j e c t i v e k 越sp a p e r ，w ea i 辙雒e x t 麟；t i n g 幽婶e 凳翻鹏s 硒mp l a l l es h o es l o e sa n d p r o p o s eas 耐e so fp r a c t i c a lm e t l l o d sb a s e do ns h a p ef c a t u r e so fo u t s i d ec o n t o u ra n d 趣i d ep 批弧em 越n 啪恕瓣猫岛l l o 弼 ( 1 ) w ep u tf o r w a 们an e wm e m o df o rs l a n tc o r r e c t i o no fs l o e s ，w 1 1 i c hi sb a s e do n t 量l ea n g l e 她e db y 也eb 稳g e s ta n dh o r i z r o n t 越a x i s a l l dt h e ns e g 秘e 越t h es h o es o l e s a n dc o n 8 仃i l c tc o o r d i n a t e sf o r 缸胁e r 纯a t u r e se x t f a c t i n g ( 2 ) e x p a t i a 把ad e p i c t i n gm e m o d f o ro u t s i d ec o n t o u rb a s e do n 私p e c tr 蕊oa l l d 凳撒p o 主n 童so f e a c 量ls e 蹦e n t 髓ea s p e 戍r a t i o 愆f e r s 专。越碰ob e t w e e n 镪ew i 融o f t o p ，p a l m ，b o w ，h c e lo fs h o es l o e s 弧l dt 1 1 el o n g e s ta x i s a n dm ef e a t u r e sp o i n t so f o 昭i 氐e o 越o l 瑶i 热鑫i e a 耄e 趣爨e x i o 嚣嚣毂莲纨g e 纛筘迹菱髓羚。攘s i 氐e o 登籽暇o fs h o es l o e s m a i l l l yc o i l s i s t so fc o n v e xa r c ，c o n c a v ea r c 柚d1 i n e t h ei n n e x i o nr e f e r st om es m o o m 姻n s i t i o 稳p o i n to fe o n v e xa r ca n dc o n c a v e 魏，a l l dt h e 识趣s i t i o 娃p o i i l 埝o fe o n 袱， c o n c a v ea l l dl i n ea c a l l e dt a 芏l g e n tp o i n t ( 3 ) 1 1 1 ei l l s i d ep a l t e mi sa l s od e p i c t e dt l l i _ 0 u 曲k i n d so f8 h a p e s w - ep r o p o s ea l n e 氇o d 毫0 乏i e s e f i b | e 氇ep 馈专l e ms 魏a 薹e sb a s e d 戎s l a 翱c e 强d 雏g l e ，w h i c hl 约to 越y e x 仃a c t st h es i i a p ef e a t l l r e so fp a t t e mb u ta l s oc o n s i i i e r s 廿l er c l a t i o n s h i po fs p a t i a l p o s i t i o n ( 4 ) i no r d e rt oi m p r o v es p a c ee m c i e n c ya i l dt h es p e e do fr e t r i e v a l ，t r a i nm e d i s c o 肋e c t e dt e x t i l r aif e a t i 埘e so fa l ls l o e sa i l dt h e ng e t sc o d e b o o k u s ei n d e xv a l u eo f c o d e b o o ka n dc e m r o i dc o o r d i n a t et od e s c r i b ee a c hd i s c o m l e c t e dt e x t u i 谢f e a t l l r e t 雠sp 印e rm i n e st l l ef e a t u r e so fs h o es o l e si m a g e so nm eb 嬲i so fm ee x i s t i n g s i l 乏畔- b a s e di m a g e 砌e v a l ，p r o p o s e st h em e m o do fe x t i 徼t i l l go u t s i d ec o n t o u ra 1 1 d i n s i d ep a t t e mo fs h o es o l e s ，锄dr e t r i e v e st l l es h o es o l e si m a g e su s i n gs h 印ef e a t u r e s t h ee x p e r i m e n t 觚p r o t o t y p es y s t e m 时l o w st l l em e t h o dp r o p o s e dw o r k sw e l l k 哪7 0 r d s ：s h a p ef e a n l r e s ；o u t l i n ef e a ：t u r e s ；s l a n tc o r r e c t i o n ；t e x m 蹦f e a ：t u r e s ；i m a g e f 州e v a l 管燕：基于形状特征的平面鞋印图像检索的研究 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名：学燕 签字日期：加暑年6 月2 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借 阅。本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国 科学技术信息研究所将本学位论文收录到 o ，雕v ( x ) ( 胛) = c 口耐 办g 掣( z ) ( p ) = 万 其 中c a r d 表示求集合的势。 基于傅立叶变换的轮廓描述 假设在数字图像的边界上有个点，它从任意一个起点( 而，) 开始，以逆时 针方向沿着边界移动，这样可以得到一系列坐标点( 而，) ，( 五，少1 ) ，( h 小蜘一。) ，通 过这些坐标点可以得到一个复数z ( 拧) ，它的表达式如下所示： z ( 刀) = 戈( 万) + j 少( 刀) ， 胛= l ，2 ，一l ( 2 5 ) 在图像边界的描述过程中，因为受到边界曲线形状和初始点的影响，数字图像的 边界坐标通常不是连续的，而是离散的。z ( 厅) 的离散傅立叶变换如下所示： ，一l 口( 七) = z ( 即) e x p 一_ ，2 翮七】，o 七一l ( 2 6 ) = 0 复系数口( 七) 叫做边界的傅立叶描述子。利用傅立叶描述子提取出图像特征后，必 须对图像特征进行归一化，因为进行图像检索时候，所需要的特征有着不同的取 值范围。图像特征归一化过程建立在特征均值和方差的基础上，它把所有数据都 映射到【0 ，1 】区间上。 链码 图2 1 f 舱锄a n 链码 f r e e m 锄出于模式识别的目的，提出了用图2 1 所示的不同斜率方向的8 个 小直线段作为基元，通过这8 个方向的编码来描述线条图，即为f r e e m a l l 链码。 它实质上是串指向符的序列，以8 方向链码为例，方向定义见图2 1 。对任一 管燕：基于形状特征的平面鞋印图像检索的研究望 像素点p ，考虑它的8 个邻近像素，指向符共有8 个方向，分别用0 、l 、2 、3 、 4 、5 、6 、7 表示。链码表示就是从某一起点开始沿曲线观察每一线段的走向并用 相应的指向符来表示，结果形成一个数列。因此可以用链码来描述任意曲线或闭 合的边界。 基于小波变换的轮廓描述在相同长度下，它比傅立叶轮廓描述符有着更高的 描述精度，同时描述结果也更加直观，小波轮廓描述符在轮廓中的局部变化只会 影响对应局部系数，对其它系数的影响不明显，用比较少的系数就可以实现比较 高的轮廓描述精度问题。虽然在大尺度下不容易对边界进行定位，但是它的误差 比较小。在比较小的尺度下定位比较精确，但是误差比较大。数学形态学的粒度 测定可以在不进行图像分割的情况下，利用开运算族来提取形状信息，但是它的 计算效率很低，实现起来比较难。基于傅立叶变换的轮廓描述符具有良好的平移、 旋转、伸缩等几何不变性，非常适合于构造形状的边界信息。它的缺点是：轮廓 的空间变化会带来傅立叶描述数值的无规律的变化，并且很难从直观上对变化进 行预测，局部变动会造成对应轮廓不规则的畸变，在提高精度的时候需要大量地 增加系数量，同时它对噪声比较敏感。 ( 2 ) 基于区域的形状特征描述方法 在实际应用中，出于对算法时间和空间复杂性的考虑，形状的表达和匹配往 往采用更为简单的区域特征描述方法。譬如，采用有关形状定量测度( 如矩、而积、 周长等) 的形状参数法( s h a p ef a c t o r ) 。在q b i c 系统中，便是利用圆度、偏心率、 主轴方向和代数小变矩等几何参数，进行基于形状特征的图像检索。 在基于区域的物体形状表示的矩描述方法中，一种有效、经典的矩描述方法 是由h u 提出的形状不变矩方法。在该方法中，假设r 是用二值图像表示的物体， 则r 形状的第p + g 阶中心矩为： 脚= o t ) 9 ( 少一y 。) 4 ( 2 7 ) ，y c 月 式中，( x c ，y c ) 是物体的中心。为获得缩放不变的性质，可对该中心矩进行标准化 操作： ，7 w ：箪7 = 掣 ( 2 8 ) z 基于这些矩，h u 提出了如下一系列分别具有变换、旋转、缩放不变性的7 个矩： 仍= 玎2 0 + 刁0 2( 2 9 ) 1 2 扬州大学硕士学位论文 缈2 = ( ，7 2 0 + 材0 2 ) 2 + 4 ，7 矗 仍= ( 玎3 0 一3 ，7 1 2 ) 2 + ( 玎0 3 3 印2 1 ) 2 纨= ( ，7 3 0 + 玎1 2 ) 2 + ( 玎0 3 + ，7 2 1 ) 2 缈5 = ( ，7 3 0 一3 刁1 2 ) ( 町3 0 + 3 玎1 2 ) 【( 印3 0 + 咿1 2 ) 2 3 ( 玎2 l + 刁0 3 ) 2 】 + ( 3 刁2 l 一刁0 3 ) ( 玎2 l + ，7 0 3 ) 【3 ( ，7 1 2 + 刁3 0 ) 2 一( 玎2 l + 印0 3 ) 2 】 = ( ，7 2 0 一，7 0 2 ) 【( 玎3 0 + 卵1 2 ) 2 一( ，7 0 3 + ，7 2 1 ) 2 】 + 4 j 7 j l ( 叩3 0 + j 7 1 2 ) ( 矽0 3 + 玎2 1 ) 仍= ( 3 玎2 1 一，7 0 3 ) ( ，7 3 0 + ，7 1 2 ) 【( ，7 3 0 + 刁1 2 ) 2 3 ( 玎0 3 + 刁2 1 ) 2 】 + ( 刁3 0 一3 刁2 1 ) ( 刁0 3 + 刁2 i ) 【( 叩0 3 + 刁2 i ) 2 3 ( 节3 0 + 刁1 2 ) 2 】 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 除了上述7 种不变矩之外，还有许多计算小变矩的方法。譬如，在g h e n 定 理的基础上，g 和a 】b r e 垂s c n 等人提出了在二值图像中快速计算矩的方法。 由于许多有效的小变量都是从反复实验中得到的，k a p u r 等人开发了一系列算法， 用来系统地寻找特定的几何不变性【4 2 】。另外，文献【4 3 】还提出了一种代数曲线和小 变量的框架，用来在混杂的场景中表示复杂物体。它用多项式拟合来表示局部几 何信息，用几何不变量进行对象的匹配与识别。此外，c h e n 也提出了一种改进的 不变矩方法l 4 4 j 。 2 1 4 空间关系特征 目前人们对空间关系的研究主要集中在拓扑、顺序和度量关系这三大类【4 5 】。 由于空间关系问题固有的复杂性和不确定性，空间关系的描述和推理普遍采用定 性的方法，这符合人们对于空间的认知规律。拓扑关系是空间关系中最基本、最 重要、同时也是被研究得最多的一类空间关系。拓扑关系是指在拓扑变换旋转、 缩放等下的拓扑不变性，如空间对象包含、相离和相邻等关系。由于空间对象间 的拓扑关系在空间数据组织、空间数据分析和查询等方面起着非常重要的作用， 近二十年来人们对空间拓扑关系进行了大量深入的研究，并取得了很大的进展， 已经有一些成熟的拓扑关系模型在很多实际应用中发挥了作用。顺序关系用来描 述空间对象在空间中整体和局部的某种排序，常用方向性名词描述空间实体间的 顺序关系，如前后、左右、上下关系等。顺序关系中研究得最多的重要关系是方 管燕：基于形状特征的平面鞋印图像检索的研究坚 位和方向关系。方位关系是指相对于地理空间的方位概念如东、西、南、北等， 而方向关系是指人类认知中的方向概念如前后、左右等要说明方向或方位关系， 至少需要三个元素主对象、参考对象和参考框架，在高于二维的空间中需要给出 的说明可能更多。描述一个方向或方位关系的参考框架主要有三种内部参考框架， 即按照参考对象的内部方向确定的参考框架，如建筑物或车都有其内部方向、外 部参考框架，与地理空间中的方向一致直接参考框架，加入了视点这一元素，用 视点与参考对象的连线确定方向。 与拓扑关系相比，对于方向和方位关系的理论研究还不够完善，尤其是其中 一些基本的概念性问题还未形成统一认识。 度量关系是用某种度量空间中的度量来描述空间对象间的关系，如对象间的 距离、大小等。度量关系本身是一种定量空间关系，其依赖于某种具体的空间度 量，度量关系中的距离和大小通常用线性尺度来衡量，用数学公式进行计算。例 如两个点对象的距离有欧氏距离、曼哈顿距离和广义距离等多种定义。 2 2 鞋印图像预处理 由于从现场得到的足迹图像存在着模糊，干扰成分太多等特点，因而要想自 动的进行入库和检索，就必须进行预处理。预处理主要包括灰度化、二值化、图 像增强、图像滤噪等，这些预处理操作和一般图像的预处理操作很类似，这里就 不再叙述了。下面主要介绍本文提出的鞋印图像倾斜校正算法、分区和建坐标轴 操作。 2 2 1 鞋印图像倾斜校正 ( 1 ) 鞋印图像倾斜校正的意义 鞋印实地拍摄过程中考虑光线的问题，技术人员为了获取比较清晰的鞋印纹 理，需要调整拍摄的角度。这样拍摄下来的照片中鞋印会出现各种角度。在鞋印 预处理时已将图像转动，使鞋尖朝上，但不能保证所有的鞋印图像的倾斜程度一 致，这将直接影响浏览效果。另外，本文对于鞋印特征的提取采取自动法，即自 动提取鞋印外轮廓特征和内部各花纹的形状特征。对于外轮廓的提取采用各分区 纵横比法和特征点法，而对于鞋印内部花纹形状特征的提取采用基于距离、角度 直方图花纹形状表示法，同时用各花纹的质心坐标来描述各花纹形状的空间位置 竺扬州大学硕士学位论文 关系。这些特征提取的前提就是所有鞋印图像必须以相同角度存放。本文给出了 一种鞋印图像倾斜校正方法，该方法根据鞋印图像最长轴和水平方向的夹角，将 鞋印图像倾斜校正。 ( 2 ) 鞋印图像倾斜校正 鞋印倾斜校j 下的思路是计算鞋印轮廓上最长两点组成的直线和水平方向的夹 角，根据这个夹角来校正。具体方法如下： s t e p l ：将轮廓上所有轮廓点的坐标记下。 对于二值化后的图像，即鞋底图像是黑色，背景是白色。本文采用逐行扫描 的算法，将每行的左起第一个黑像素点和右起第一个黑像素点的坐标记录下来， 具体实现的代码如下： v o i dl u i l l ( u o t i q u o 将鞋印的轮廓点的坐标记录下来，其中a i 】【0 】存放第i 行左 起第一个黑像素点的纵坐标，a 嘲【1 】存放第i 行右起第一个黑像素点的纵坐标 fh = 0 ；他用来标示逐行扫描出现的第一个黑像素点所在的行标 k = o ；用来标示逐行扫描出现的最后一个黑像素点所在的行标 f l a g l = 1 ：用来标示逐行扫描到的黑像素点是否第一个黑像素点 f l a 9 2 = l ；用来标示逐行扫描到的黑像素点是否最后一个黑像素点 f o “i n ti - o ；i b i h e i g h t ；i + + ) n a 9 3 = l ；n a 9 3 用来标示从左扫描有无黑像素点出现，如果没有就没有必要 再从右边扫描 f o “i n tj = o ；j 邮b i h 一 b i w i d t h ；j 抖) 逐行从左扫描，找到左起第一个 黑像素点 p = p 、v + ( s r c b u f s i z e l i n e b y t e s i l i l l e b y t e s ) 斗j ； i f 【奎p 一0 ) f l a 9 3 = 0 ； i f ( n a 9 1 = = 1 ) h _ i ；n a 9 1 - 0 ；) a 嘲【o 】= j ；b r e a k ； ) i 坟n a 9 3 = = 0 ) f o r ( 硫k = 瑚p b i h 一 b i w i d 廿1 - 1 ；k = o ；k 一) 逐行从右扫描，找到右起第 一个黑像素点 管燕：基于形状特征的平面鞋印图像检索的研究 p = p w + ( s r c b u f s i z e l i n e b y t e s i 宰l m b y t e s ) + k ； 圾宰p = = 电) a 【i 】【l 】- k ；b r e a l ( ； i f ( f l a 9 3 0 ) & & ( h 0 ) k _ i ；n a 9 2 = 0 ； i f ( n a 9 2 0 ) b r e a l ( ； ) 通过该算法使鞋印的轮廓存储在一个二维矩阵中a 中， 么= ，o ，l 口 + l ，0 ，口 + l ，l q 。o ，吼，l ( 2 1 6 ) 其中a 蛐存放第x 行左起第一个黑像素点的纵坐标，q t 存放右起第一个黑像素点 的纵坐标，j l ，x 七，办用来标示逐行扫描出现的第一个黑像素点所在的行标，七 用来标示逐行扫描出现的最后一个黑像素点所在的行标。 s t e p 2 ：求出鞋长( 最长轴) 思路：将鞋印轮廓上最长两点的距离作为鞋长。 本文采用如下的计算公式， 。 ，= m a x ( d 跆t 锄( ( 口，。) ，( ，口j 1 ) ) i 办f 七，f ，七 ( 2 1 7 ) 其中如t 觚c p ( ( f ，) ，( ，口) ) 为坐标为( z ，) 的轮廓点与坐标为( 歹，口) 的轮廓点的 距离，h 为轮廓中最上面黑像素点所在的行标，k 为轮廓中最下面黑像素点所在的 行标，口，。为行标为i 的左轮廓点的列标，口为行标为j 的右轮廓点的列标。为了 提高执行效率，避免求过的两轮廓点距离重复求，最长轴左边的轮廓点分别和最 长轴右边所有行标大于等于左轮廓点行标的所有右轮廓点求距离。具体代码如下： v o i ds l 锄tc o 仃e c t i o n ( ) 求出鞋长，同时记下鞋印最长两点的坐标 l - 0 ；i l = 0 ，j1 = o ，i 2 = 0 ，j 2 = o ； f o r ( i n tm = h ；m k ；m + + ) i f ( a b s ( a 【m 】【1 】a 【m 】 0 】) 1 ) l = a b s ( a 【m 】 1 】a m 】 0 】) ；i 1 = i 2 = m ；j1 2 a 【m 0 】；j 2 = a m 】 1 】； f 0 “i n t 卿；y q ；y + + ) f o r ( i n ti f m + 1 ；n b i h e i g m ；r 1 + + ) f o “i n tz = o ；z 1 ) l = s q r t ( ( a m 】 y 】- a 【n 】 z 】) 宰( a m 】【y 】- a 【n 】【z 】) + ( m n ) 幸( m n ) ； i 1 = m ；j 1 = a m 】【y 】；i 2 = n ；j 2 2 a 【n 】【z 】； ) ) ) s t 印3 ：算出方位角q ，即最长轴与与水平方向x 轴的夹角； s t e p 4 ：如果q 9 0 。，则 图像顺时针转动q 9 0 0 。 2 2 2 鞋印分区以及坐标轴的建立 鞋印一般分为鞋尖、鞋掌、鞋弓、鞋跟四个区，每个区占整个鞋印一定的比 例【蛔，鞋跟长度一般占整个鞋长的2 5 ，鞋弓占2 9 ，鞋掌占2 8 ，鞋尖占1 8 。 本文根据以上鞋印分区的数据对鞋印进行自动分区，分区的方法是：对校正后的 鞋印图像建立坐标轴，如图2 2 所示，以b 点为原点，以鞋印最长轴a b 为y 轴， 以垂直a b 、过b 点的直线为x 轴，建立的二维坐标，从原点开始沿x 轴正方向 根据一定的比例将鞋印自动划分成四个区。建立坐标轴的目的是将鞋印进行自动 分区，同时也便于标示鞋印内部各花纹的坐标，达到描述鞋印内部各花纹的空间 位置关系。 二4 p j 土 ”*r 图2 2 鞋印各分区比例图 管燕：基于形状特征的平面鞋印图像检索的研究 2 3 图像中常用的相似性度量方法 2 3 1 概述 在基于内容的图像检索中，两幅图像是否相似是指图像的特征向量是否相 似。常用的图像相似性测度通常采用几何模型，将图像特征看作是向量空间中的 点，通过计算两个点之间的接近程度来衡量图像特征之间的相似度【2 8 】【4 7 1 。基于内 容的图像检索算法主要有最邻近查询算法和区间查询算法，它们都依赖于距离函 数或者相似性度量。 在基于内容的图像检索中，例子图像查询是主要的查询方式。图像或者图像 片段可以用一系列含有d 个特征( x 【1 】，x 【2 】，x 【d 】) 的集合来表示，这些特征包 括纹理、形状、颜色以及它们之间的组合。在d 维特征空间中，把特征聚合成为 一个特征向量，可以根据不同坐标轴来标记相应的特征。为了支持最邻近查询和 区间查询，特征空间必须与一个度量或者相似性测度相匹配。在图像相似性测度 中，可以采用各种距离函数或者距离度量、统计学方法和非几何相似性测度方法 【2 8 】【2 9 】。 2 3 2 相似性测度 假设在图像数据库中，用特征向量来表示任何一个图像特征，其中x 和y 分 别是任意两个特征向量，它们满足图像相似性度量中的自相似性、最小性、对称 性和三角不等性度量公理，它们之间的接近程度可以采用距离度量或者统计学方 法来进行图像相似性判断。常见的距离度量有欧几里德距离、m a i l l l a t t 锄距离、 m i 炯s 1 ( v 距离、m a l l a l a n o b i 距离等【2 8 】【4 8 5 2 1 。 ( 1 ) 欧几罩德距离 欧几里德距离是一个应用非常普遍的距离度量。它的计算简单，并且与参考 系统的旋转不变量相关。它的定义如下： r r 一 d ( x ，】，) = 、( x 【f 】一l ，【f 】) 2 ( 2 1 8 ) y ，= l 当发生数据丢失或者当所有特征向量不具备相同的权重时，那么就不能使欧几里 德距离来进行相似性测度。为了避免这种情况，在实际的应用过程中可以对欧几 坚 扬州大学硕士学位论文 里德距离进行归一化。归一化欧几里德距离的定义如下所示： d ( x ，】，) = ( 2 1 9 ) ( 2 ) m a n h a t t a n 距离 m a n h a t a n 距离又叫街区距离，它与欧几里德距离具有相同的计算复杂度， 它的定义如下： 厂7 一 d ( x ，】，) = 、l x 【f 】一】，【圳p ( 2 2 0 ) y= i ( 3 ) m i n k o ，s k y 距离 m i n k o 、s k y 距离是一个距离函数系列，它的参数为p 。在个别维数中，利用 非负权重哆可以进行不同的加权计算。它的数学表达式如下： ( 2 2 1 ) ( 4 ) m a h a l a i l o b i s 距离 它是一个计算复杂的权重欧几里德距离。它根据一个协方差矩阵c 来定义， 它的定义如下所示： 烈墨y ) = ( 研司一y 【习) 1c q 何f 】一h 司) ( 2 2 2 ) c 一是c 的协方差逆矩阵，如果c 是恒等矩阵，那么m a h a l a l l o b i s 距离就变成欧几 里德距离。当特征向量的分向量之间没有相关性，可以对m a l l a l a l l o b i s 距离进行 简化。 ( 5 ) 相关系数 它的定义如下： 舭肛焉坠竺塑粤查坚 ( 2 2 3 ) ：。( x 【力一石 m 2 ：( 刀一x 【m 2 其中i = 【_ 【l 】，_ 【2 】，_ 【d 】是数据库中所有向量的均值。如果把点x 和y 投影到 单位半径为x 的球面上，量化为2 2 p ( x ，l ，) ，它就是投影区间的欧几里德距离。 在投影区间中，对应于搜索空间的尺度和旋转不变量就是相关系数。它可以用于 统计任意变量的偶合行为属性。 ( 6 ) 相对熵( k l 分裂) 管燕：基于形状特征的平面鞋印图像检索的研究 它仅仅应用于随机分布，它的定义如下所示： 驯n = 枷】1 0 9 篇 仅仅当元素x 和y 非负并且：。x 【f 】= ：。刁= l 时它才具有实际意义。因为它不 具备对称性，也不满足三角形不等式，所以它不是距离度量。当它应用于图像检 索的时候，可以把第一个独立变量作为查询向量，第二个独立变量作为数据库向 量。 ( 7 ) z 2 距离 它仅仅应用于随机分布，它的定义如下： 。础) = 喜等 当且仅当元素x 和y 非负并且：。x 【f 】= ：。司= l 时候，它才具有实际意义。它 在计算量和分裂上的耗费很大。 在上述的相似性度量方法中没有任何一种方法可以适用于所有特征向量间的 相似性度量，其主要原因是上述度量方法具有特征依赖的特点，不同的特征应该 应用不同的度量方法。例如，直方图相交法不适合于非直方图的特征，虽然二次 式距离可以有效的度量颜色直方图的距离，但在对其它特征向量的距离度量效果 却没有采用欧氏距离度量的效果好【5 3 】。因此在进行图像检索时，显然难以证明上 述相似性度量方法谁更具优势，在具体的应用过程中只有根据实际需要进行灵活 选择。需要指出的是在相似性度量的能力上，某些已知工作给出了一些结果，如 文献【5 3 ，5 4 】指出，除了颜色的直方图特征外，在进行特征向量间的相似性度量时， 欧氏距离和城区距离相对于其它相似性度量方法具有更好的检索性能。 2 4 图像检索算法的评价准则 在进行图像检索时往往需要选择一种或多种最有效的特征描述方法和相似 性度量方法，这就需要对不同的图像特征或特征组合以及不同的相似性度量方法 的检索效果进行全面的评价，比较不同方法的性能，找出最好的方法。但是，由 于图像检索具有很强的主观性，因此，评价一个图像检索算法性能的优劣并不容 易。下面列举的是几个公认的图像检索算法的评价准则【5 5 - 5 9 1 。 扬州大学硕士学位论文 2 4 1 查准率和查全率 查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 仍是目前在c b i r 中应用最为广泛的一种 评价准则。查准率的含义是在次查询过程中，系统返回的相关图像数目占所有 返回图像数目的比例，如果在检索结果集合中，正确相关图像数目多，则查准率 就高。查全率则指系统返回的查询结果中相关图像数目占图像库中所有相关图像 数目( 包括返回的和没有返回的) 的比例。 设s 为图像库中所有和查询图像相关的图像集，r 为所有检索到的图像集合， s 为一次查询中检索到的所有相关图像数目，u 为一次检索过程中检索到的不相关 的图像数目，v 为图像库中和检索图像相关但在检索中未被检索到的图像的数目。 这样查准率和查全率可表示为： 删：尸川s ) ：璺：业! ：( 2 2 6 ) 尸( s ) 5 + 1 ， 、。 p 陀c 括如疗= 尸( sr ) = ! 垡! 塑= 上 ( 2 2 7 ) 尸( 尺) s + 甜 、 查准率和查全率越高，表明该检索系统的效果越好。一般地，查全率和查准 率是一对矛盾，当要求精度较高时，查全率较低，反之亦然。因此，一般的检索 系统只要求在这两者之间达到一个最优的平衡点，就认为达到了较好的检索性能。 2 4 2 命中准确率 查准率和查全率需要用户在图像库中人工找出与查询图像相似的图像集，这 将耗费大量的人工劳动，因此这种度量准则对于较小型的图像数据库比较合适。 如果图像库测试集已经提前进行了分类，如c o r e l i m a g eg a l l e 巧等类型的数据库， 就可以简单的将每一个图像类别作为其中每一幅图像的相关图像，由此来度量算 法的检索准确率。设图像q 所在的相关图像集为g ，图像检索算法自动输出了t 个相似图像，其中命中g 的有n 幅图像，此次检索的准确率定义为：。一f 。 由此，平均多个查询的检索准确率就可以度量算法的检索性能。 2 4 3 排序值评测法 设g 是一幅查询图像，g ，g ：，晶为图像检索算法检索到的与g 相关的且从 管燕：基于形状特征的平面鞋印图像检索的研究型 主观上认为相似的图像，设翮七( g ，) ，j = 1 ，2 ，行为图像g ，在检索结果图像序列中对 应的排序值，则下述两个指标可以有效的衡量算法的检索性能， ，一朋螂讹= 去翮七( g ，) ( 2 2 8 ) p 一肌鲫“陀= 二去_ ( 2 2 9 ) 刀t 彳，口玎七( g ，) 、7 其中，第一个指标定义了所有相关图像在检索结果中的平均排序，显然，此指标 越小，检索算法的准确率越高。第二个指标定义了所有相关图像在靠前排列的紧 密程度，因此该值越大表明检索结果越好，如果所有的相关图像都排在最前面， 则此指标取值为l 。 a n m i u r ( a v e r a g en o 咖a l i z e dm o d i f i e dr c t r i e v a l 舢k ) 是m p e g 7 推荐的一种性 能评价方法，设( g ，) ( f = 1 ，2 ，9 表示图像库中与图像g 。相似的所有图像数目， m = m a x ( 吼) ，( g ：) ，( ) ，足= m i l l 4 ( 吼) ，2 m ，设与例子图像相似的图像在 检索结果序列中所处的位置为： 降鲋 朋刀故d2 ( 2 3 0 ) l “l 螂 从而，a n m i 汛定义如下： ，等笔婴乩5 _ o 5 ( g ，) 一= 拯竺篇矗茅 由上式可知a n m i 汛取值越小表明该算法的检索性能越好。 应当指出，除了主观因素，图像检索的准确率与图像数据库有很大的关系， 即使同一算法根据相同的评价方法在不同的数据库中计算出的检索准确率都可能 会存在较大的差异。 2 2 扬州大学硕士学位论文 2 5 本章小结 基于内容的图像检索研究是一个综合的研究领域，该技术的研究把计算机视 觉( c o m p u t e rv i s i o n ) 、图像处理( i i l l a g ep r o c e s s i n g ) 、图像理解( i m a g eu i l d e r s t a n d i n 曲 和数据库( d a t a b a s e ) 等多个领域的技术成果结合起来，因此仅靠短短的一章不可能 将图像检索的关键技术介绍清楚。本章仅仅对c b i r 研究中常用的图像低层特征 的描述方法、图像特征间的相似性度量方法、图像检索性能评价则进行了介绍， 在图像预处理中提出了倾斜校正算法，通过这些预备知识的介绍，使我们能够从 整体上了解该领域研究的主要问题和己有的工作基础，同时也为后续章节的展开 。作了铺垫。 管燕：基于形状特征的平面鞋印图像检索的研究 3 基于外轮廓特征鞋印图像检索 鞋印的外轮廓的形状都很类似，呈长腰型，如采用上述一般图像轮廓特征描 述方法并不能很好的区分各鞋印外轮廓。在鞋印检验过程中，鞋印外轮廓一般通 过各部分的长、宽以及特征点间的距离来描述，而鞋印各部分的长、宽及特征点 间的距离都是通过大分规和尺测量得到的。在要求精度不高时，有时就是靠检验 人员目测得到的。实际操作中，正是因为测量不方便以及测量值不可靠，使足迹 各部分的长、宽特征不受重视，通常只测量鞋印长度。单个长宽特征属于质量不 很高的种类特征，贾转玲唧】用整个鞋印的长和宽、鞋印的重心位置等来描述鞋印 的几何特征，即鞋印的外轮廓特征。该方法是提取图像轮廓特征的通用手段，用 在鞋印轮廓特征提取上并不是很好，描述的也不是很准确，因为鞋印外轮廓有自 身的特点，这个特点主要包括两方面：一是鞋印可以分为4 个区( 鞋尖、鞋掌、 鞋弓、鞋跟) ，可用各分区的宽度和鞋印最长轴之间的比值参数来描述鞋印外轮廓 特征；二是鞋印的外轮廓主要由凸凹圆弧、直线组成，凸凹圆弧的平滑过渡点称 为拐点，凸凹圆弧与直线之间的过渡点称为切点，这些轮廓特征点( 拐点、切点) 可用来描述鞋印外轮廓。本文根据这些特点，提出了基于各分区纵横比、特征点 的外轮廓描述法。 3 1 基于各分区纵横比的外轮廓描述 3 1 1 鞋印外轮廓特征提取的一般方法 在实际运用中刘珍【6 l 】利用计算机辅助测量技术提取鞋印掌宽、弓宽、跟宽、 全长，如图3 1 所示，用其描述鞋印外轮廓特征，其步骤如下： 确定中心线，在鞋印的内侧和外侧各做一条切线，使两切线与前掌内、外 两侧最突出部分，后跟内、外侧最突出部分分别相切，作足迹的内侧切线和外侧 切线交角的角平分作为鞋印中心线。 中心线确定后，再于鞋尖前缘和跟后缘两处，各作一条与中心线垂直的切 线，两切线之间的垂直距离，就是鞋印全长。 在掌的内侧突点和外侧突点分别作两条与中心线平行的切线，两切线的垂 扬州大学硕士学位论文 直距离即为掌宽。 与中心线平行在弓部内外缘分别作两条切线，两切线的垂直距离为弓宽。 在跟的内缘和外缘分别作两条切线，且两切线平行，两切线间的垂直距离 即为跟宽。 该方法虽然考虑到将鞋印分为3 个区：鞋掌、鞋弓、鞋跟，用各分区的宽和 鞋长来描述鞋印外轮廓，但存在两个弊端：用计算机测量掌宽、弓宽、跟宽、 全长，这里计算机还只是个辅助工具，每次测量之前都必须由人利用计算机作切 线等，由于人为影响，所测量的结果不一定准确，效率也比较低；当图像进行 缩放时，这些指标都将发生变化，描述图像的特征最好是不受图像缩放、平移、 旋转的影响。 “ a l? ) 一 厂 二一7 ； l 一二 0 1 4 (罗。 i j 图3 1 鞋印轮廓计算 3 1 2 基于各分区纵横比的外轮廓描述 c h 图3 2 两只鞋底轮廓图 本文提出的基于各分区纵横比来描述鞋印的外轮廓克服了以上缺点，充分利 用了鞋印外轮廓形状特点的第一方面，即鞋印可以分为4 个区( 鞋尖、鞋掌、鞋 弓、鞋跟) ，可用各分区的宽度和鞋印最长轴之间的比值参数来描述鞋印外轮廓特 征。在图3 1 描述的各分区的范围基础上上下各扩大5 求其宽度。分别采用公 式3 1 、3 2 、3 3 计算掌宽、弓宽、跟宽。 茄篡蕊篇璧盘m 胁5 。j b ， 其中l ( 七一j l l + 1 ) 1 3 j 工l ( 七一办+ 1 ) 5 1 j 、7 凳蒜：袋蕊曼m 聃8 叫 2 ， 其 f 机七一 + 1 ) 4 1 j x k 七一j i l + 1 ) 8 0 l j 、7 鼎竺鼍c 繁2 世口：，? ( 3 3 ) 其中j ( 七一 + 1 ) 7 0 j x i ”一7 足霉中心蝇 管燕：基于形状特征的平面鞋印图像检索的研究堑 h 为轮廓中最上面黑像素点所在的行标，