江南大学学士毕业论文--基于指纹识别技术的学生身份认证系统

江南大学学士毕业论文--基于指纹识别技术的学生身份认证系统内容摘要：

系统采用 Sobel 梯度算子计算象素点在 x 和 y 方向上的梯度 Gx 和 Gy。 对所有非背静区域的象素计算梯度，并保存在数组 Gx (i,j) 和 Gy (i,j) 里。 x (i,j) = ),(),(22222vuGvuG yiiujjvx  , (35) y (i,j) = )),(),(( 222222 vuGvuGyiiujjvx   , (36) )),( ),((ta n21),( 1 ji jiji xy  (37) 并不在开始就计算出所有点或块的方向估计，只有当后续处理需要计算某个象素的方向信息时，才根据公式予以计算，从而省去了很多不必要的计算量。 特征抽取 指纹灰度图象经过增强处理，对于细化后的图象，经过一定的光滑处理后，进一步去噪（如去除孤立点、毛刺、跨接短桥、小环等）后，就可以初步提取指纹细节点。 假定 P为被检测的黑点， N 为 P 的 8邻域中黑像素的个数。 如果N=1，则 P是末梢点；如果 N=3,则 P是分支点。 由于干扰、噪声的影响，提取出的细节点中包含相当多的伪细节点，一般采用统计和结构信息相结合的方法删除 伪细节点。 信息的新颖算法，这里用到的算法是对上述算法的改进，算法的基本思想是沿纹线方向自适应地追踪指纹脊线，在追踪的过程中，局部增强指纹图象，最后江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 12 页 共 51 页 得到一幅细化后的指纹脊线骨架图和附加在其上的细节点信息。 由于该算法只在占全图比例很少的点上估算方向并滤波处理，计算量相对较少，所以在时间上明显优于传统的方法。  基于脊线跟踪的细节提取算法 从数学上看，可以将指纹图象视为一个定义在二维平面上的一个曲面，沿脊线方向，灰度、变换相对平缓， 沿垂直于脊线的法线方向，灰度呈现波峰波谷交替出现的分布，而在接近背景区域或脊线末梢处，沿脊线方向的灰度发生显著变化。 本算法的思想正是建立在上述假设的基础上。 图 33 脊线跟踪算法示意图 图 34 细节点的判定 算法步骤 在处理阶段得到了计算出方差并从大到小排序的图象块序列。 选择块方差最大的块中灰度值最大的点，以该点 (it ,jt ) 为起始点执行脊线跟踪算法。 主要步骤如下 ： 1． 首先，计算出该点 (it ,jt ) 的方向估计值  ，得到以 (it ,jt ) 为中心的方向与  正交的（即法线方向Φ）长度为 2 +1 的点集Ω((i,j) ,Φ , )。  是一个与脊线宽度相关的常数，通常取 35。 2． 然后对点集Ω做局部滤波增强处理。 (a)对Ω上每个点 (Xi ,Yi ),i= 0..2 得到点集Ω i =Ω ((Xi ,Yi ) ,θ ,h) ，计算Ω i 上的灰度均值，赋给 (Xi ,Yi ) ，得到一个相对光滑的点集Ω 39。 ；（通常取 h=1） (b)使用一个高斯低通滤波器 G与Ω 39。 做卷积运算。 Ω 39。 39。 =Ω 39。  G (38) G(j) = r21exp 2rj (39) 3． 下一步是定位Ω上的最可能是脊线骨架上的点，以灰度值为依据找到江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 13 页 共 51 页 局部最大处（ Xmax ,Ymax ）和最小处（ Xmin ,Ymin ），认为最大处是与脊线骨架接近的脊线点，也是 要找的点，最小处是离脊线边缘最近的非脊线点，并计算两处的灰度落差 d，以作为下一步自适应跟踪的判据。 4． 计算出（ Xmax ,Ymax ）处的方向估计值θ，已一定的步长 u，沿θ方向探测点 (Xi ,Yi ) ,i = 0..n 直至 (X 1n ,Y 1n ) 落在背景区域或者与（ Xmax ,Ymax ）的灰度值之差大于某个与 d 相关的值。 得到延伸的距离 step = n u。 u 一般取 1 或 2。 5． 对 (Xn ,Yn ,step) 检查终止条件，如果满足终止条件，则结束了沿一个方向的脊线跟踪，回到初始点，沿反方向继续跟踪，当另一个方向的探测也结束后，得到了一条脊线，对脊线上的所有点 (x,y) ，修改s[x,y]=m(m0,为脊线的序号 )。 定位到下一个起始点，回到步骤 1。 从下一个块中寻找灰度最值点，如果该点未被访问过，则以该点作为新的出发点。 6． 如果不满足终止条件，则令（ X,Y） =( Xn ,Yn ) 为新的起始点，回到步骤 1。 终止条件和细节点的判定如下： i. sm(x,y) = +。 表示已经接触到了背景区域； ii. sm(x,y) = l m。 表示已经接触到了一条 已经标记过的脊线，探测到了分支点与脊线 l和 m相关联； iii. step=0 或者小于某个很小的正整数；表示已经探测到脊线 m 的一个方向的末梢点。 伪码描述： int FollowRidge() { int m = 0。 //变量 M记录已找到 foreach Block B { x,y = B 中最值点 { if (sm(x,y) == 0) { θ = (x,y) 处的方向估计； Ω = GetSection(x,y,θ ,α )。 //得到领 域点集 Filter(Ω )。 //局部滤波增强 江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 14 页 共 51 页 x,y,xd = GetLocalMax(Ω )。 //定位局部最大值 If (sm(x,y) == 0) { m++。 TrackRidge(x,y,d,m0。 //以 (x,y)为起点跟踪 } } } } return m。 } void TracRidge(x,y,d,m) //以 (x,y)为起始 点执行跟踪算法 { θ = 处的方向估计； Trace(x,y,θ ,d,m)//沿当前方向跟踪 If (θ 0) θ =θ π。 Elseθ =θ + π。 //得到反方向 Trace(x,y,θ ,d,m)。 //沿反方向跟踪 S[x,y] = m。 } int Trace(Xstart, Ystart, θ start,dstart) //沿θ start方向跟踪 { end = false。 k = 0。 //变量 k记录跟踪步数 xcurr = xstart。 ycurr = ystart。 θ curr = θ start。 dcur =dstart。 While(!end) { x[k] = xcurr。 y[k] = ycurr。 θ [k] =θ curr。 (xnext, ynext, θ next,step)= GetNextPoint(xcurr, ycurr, θ curr ,σ )。 //定位下一点 Ω = GetSection(xnext, ynext, θ next, σ )。 //得到新的领域点集 Filter(Ω )。 //局部滤波增强 处理 Xmax, Ymax, θ max,dmax = GetLocalMax(Ω ) //找到新的最值点 end = check(x,y,step)。 江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 15 页 共 51 页 //终止条件判断 k++。 xcurr = xmax。 ycurr = ymax。 θ curr = θ max。 dcur =dmax。 } for ( I = 0。 I k1。 I ++) { Line((x[i],y[i],x[i+1],y[i+1]))。 Foreach point(x,y) on the line S[x,y] = m。 //更新 s[x,y] } return k。 } 当算法终止时，通过记录在中的数据，得到了一幅宽度为 1的脊线图，并且在执行脊线跟踪的过程中得到了指纹细节点的位置，类型和相关的脊线信息。 下面的图像是处理结果： 原图 过程 结果 江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 16 页 共 51 页 比对算法 指纹比对需要解决的问题是：给定二维平面中的两个点集 P 与 Q，其中的点包含有位置信息与方向信息。 假定二者之间存在某种全局的旋转与平移变换，同时有噪声与局部变形存在。 比对的目标是 找到 P 与 Q 中的共同点，并求出点与点的对应关系。 指纹细节比对有树状结构搜索的方法，近邻关系的结构化方法，无监督神经网络的方法等。 指纹细节比对的很多思想来自于一般点匹配问题，本系统中采用的是遗传算法求解指纹特征点匹配问题。 指纹比对分为两个步骤：首先利用遗传算法搜索所有可能将两幅指纹特征点集对齐的参数，然后再确定点的位置匹配关系。 以下从遗传算法的每一个环节详细介绍对齐参数搜索算法。 搜索空间： 考虑到指纹点匹配的具体情况，两幅指纹之间可能有平移、旋转及局部变形存在，算法在处理时，将变形所带来的误差作为噪声 处理，而遗传算法搜索两幅指纹在 x 方向的平移， y方向的平移及围绕原点的旋转角度。 适度函数： 假定某一个对应的参数为 dx， dy，θ。 将特征点集 P 做参数为θ的旋转与平移变换，得到点集 P39。 假如此参数恰是 P 与 Q 之间的变换参数，则对特征点集 Q中的每一点（除去 Q 中新增的点），在 P39。 中相应位置上都应有一个点与之对应，并且这两个点的特征方向也一致。 据此，目标函数如下设计：对点集 Q中每一点 qi ，寻找 P39。 中与之相近的点 pj ，假如 pj 与 qi 之间的距离为  d，特征方向之差为  ，当二者都在某一误差范围内时，定义 pj 对 qi 的支持度为 s(qi , pj )=1/(1+ d)+K/(1+  )，式中 K为比例系数，用于调整距离与角度影响搜索方向的比重。 考虑到可能有若干个 pj 与 qi 相近，而 qi 只能与一个点对应，于是取 qi 的匹 配度为 m(qi )=jmax(s(qi , pj ))。 值得注意的是，这种近似有可能得 江南大学毕业设计论文 —— 基于指纹识别技术的学生身份认证系统 第 17 页 共 51 页 P中有两个相近的点对应到 Q中同一个点。 对应点搜索算法步骤将会检测出这一问题并加以解决。 取 Q 中所有点匹配适度之和作为控制遗传算法的适度函数。 编码方案： 本方法中，有 3 个参数同时需要优化。 遗传算法的个体编码采用多参数编码。 每一个体由 3 段 0/1 编码组成。 第一段是 dx 的编码，第二段是 dy 的编码，第三段则表示θ。 考虑到通常指纹匹配的可能参数范围，设置每段代码为 8位。 对于参数 dx 与 dy，码值减去 127 得到参数值，故它们的搜索范围均为 [127， 128]，精确到 1 象素。 对于参数θ，码值减去 127 后除以 4 得到参数值，故它的搜索范围为 [， 32]，精确到。 为了克服普通二进编码的 Hamming 悬崖缺陷，每一段参数采用 Gray 编码。 遗传操作：  遗传种群的产生：分别随机生成 dx， dy，θ，将它们转换成 Gray 码后串接在一起。 种群大小取 50。  选择策略：采用期 望值方法。 首先依据个体 x被选择的期望值 nPs (x,t)（ n为需要选出的个体总数）的整数部分安排个体被选中的次数。 期望值的小数部分重新由轮盘赌方法选择。 Ps (x,t)=f(x,t)/x txf ),(为每一个体被选择的概率，式中 f(x,t)为个体 x在第 t代的适度值。  交叉策略：采用修正的单点交叉策略。 首先根据预先设定的交叉概率决定用于交叉的个体。 每两个参与交叉的个体随机选定一个交叉位置，两个个体在该交叉点后的结构进行互换，并且生成两个新个体。 在修正中，所得的两个新个体只有在适度值高于父辈时没，才替换父辈进入种群。 这是由于在指纹点匹配问题中，有非常多的参数 dx， dy，θ组合将导致两幅特征点集没有特征点对应。 普通的后代直接替换父辈的交叉策略有较大可能破坏当前的搜索结果，而使种群重新回到一个较差的水平。 实验结果表明：修正的交叉策略在收敛速度、最优解的适度值等方面优于普通的交叉策略。  变异策略：引入两种变异操作： 1) 需要变异的个体以一定的概率。