论文部分内容阅读
摘 要 本文深入研究遺传算法及其在指纹识别匹配中的应用。传统的遗传算法容易陷入局部最优而导致过早收敛，为解决这个问题，本文在遗传算法的编码、选择、交叉、变异操作上进行了一定的改进，以适应指纹识别的匹配应用。用matlab对本文算法进行仿真，实验结果表明，本文算法的匹配效果较好。
关键词 指纹识别；遗传算法；特征匹配
中图分类号 TP 文献标识码 A 文章编号 1673-9671-(2011)081-0215-02
生物识别是指利用人体的生理或行为特征进行个人身份鉴定的技术，包括有人脸识别、指纹识别、手型识别、虹膜识别、声音识别等，而指纹识别相对其他的识别技术，具有高稳定性和可靠性，是目前最成熟和最有前景的生物识别技术之一。
为了得到清晰的指纹及可靠的特征点，在匹配前要进行一系列的处理，过程如图1所示。通过读取设备得到图像后，首先要进行预处理，通过背景分割、滤波增强、细化等操作，使之更清晰，为下一步的特征点匹配作准备。最后采取某些方法对两个指纹的特征点进行比较，计算出它们的相似度，得出匹配结果。
指纹识别的最终目的匹配，所以匹配算法是指纹识别的关键步骤。匹配算法包括有点模式匹配、近邻结构匹配、基于结构特征的匹配、BP神经网络匹配算法等。这些算法存在计算量过高、效率低、寻优能力差等问题。遗传算法仿效生物的进化与遗传，根据生存竞争和优胜劣汰的法则，借助于遗传操作，使所求解的问题逐步逼近最优解。与其它方法相比，遗传算法通用性高、鲁棒性强、全局搜索能力强，适合全局优化问题的求解。
基本遗传算法有它的固有缺陷，容易陷入局部最优且收敛缓慢，本文对基本遗传算法进行一定的改进，并应用在指纹匹配算法中。实验结果表明，该方法具有较高的可靠性和有效性。
1指纹识别匹配
指纹匹配是指通过对两枚指纹的比较来确定它们是否同源的过程，实质就是把一幅指纹图像通过某种平移、旋转后变成另一幅图像，再与模板指纹图像进行比较，计算匹配的程度。指纹匹配的输入是两个关键点的点集P与Q。其中一个点集P是从输入的指纹图中提取出来的，另一个点集Q则是预先从标准的指纹图中提取出来，存储在模板库中。把这两个点集分别表示为：
其中，（xiP，yiP，αiP，）表示点集P中第i个关键点的信息：x坐标、y坐标和方向。假设两幅指纹图可以完全匹配起来，则可通过对输入的指纹图作某些变换（旋转、平移与伸缩）得到模板中的指纹图。因此点集P可以通过旋转、平移与伸缩等变换近似成点集Q。变换后试图寻找使两个点集尽可能多的匹配的变换。如果两个点不仅距离相近而且方向基本一致，则认为这两个点匹配。
设点集P中某点的坐标为（xiP，yiP），经过变换后为（xiT，yiT），公式如下：
其中，Δx与Δy是平移因子，θ是旋转角度。
根据上式，匹配的任务就是找出一组最佳的（Δx，Δy，θ），使一幅指纹变换后能跟另一幅指纹更好的匹配，也即存在最多的匹配点。遗传算法具有搜索全局最优解的能力，因此我们能够通过遗传算法，设置合适的编码方式、适应度函数和遗传操作，求解最优的一组（Δx，Δy，θ），找出尽可能多的匹配点，以判断两幅指纹图像是否来自同一个手指。
2基于遗传算法的指纹匹配
2.1基本遗传算法
遗传算法（Genetic Algorithm， GA）是借鉴生物界的选择淘汰、基因突变、基因遗传进化规律演变而来的一种随机搜索算法，其基本思想是基于Darwin的进化论和Mendel的遗传学说。
染色体是遗传物质的主要载体，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，遗传算法在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出新的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。这就是遗传算法的基本思想。
2.2基于改进的遗传算法的指纹匹配
1）编码。为了降低复杂度，本文采用文献[3]的方法确定两幅待匹配图的旋转因子θ，然后在旋转因子θ确定的情况下仅对dx和dy编码，这样遗传算法的搜索空间降为28×28。
本文中，遗传算法的个体编码采用多参数编码，即两个参数dx和dy结合在一起进行编码，每一个体由2段二进制编码组成，第一段是dx的编码，第二段是dy的编码，分别为9位，其中一位表示正负号。
2）适应度函数。适应度函数设置为：P按旋转因子变换成P*后，P*与Q之间的匹配程度。匹配程度则用两个匹配点集的距离和方向差来衡量。具体做法是，对点集Q中的每一点qj，寻找P*中与之相近的点pi，pi与qj之间的距离为Δd：
细节点的方向差为Δθ，当Δd和Δθ都在某一误差范围内时，则认为这两个点是匹配的。由于同一幅指纹的任意两个特征点的距离一般不超过纹线间隔λ，本文中λ为10，设Δd＝8，Δθ=0.2＝（0.2/3.14）*π＝0.064π。
当认为两个点匹配时，定义pi对qj的支持度为：f（qj，pi）=
（1/Δd）+（1/Δθ）。若有2个以上的特征点与其相近，就取其中最大的一个支持度。最后取Q中所有匹配点的支持度之和作为个体的适应度函数：
3）遗传操作。①选择操作。采用轮盘赌选择法，计算每个个体的适应度后，根据各个体的适应度大小按比例选择个体，适应度越大，被选择的机会越大。但轮盘赌选择法有一个缺陷，虽然最佳个体被选中的概率最大，但仍会有被排除的机会考虑到以上情况，本文对轮盘赌选择法稍作改动，令每代种群中适应度最高的个体自动进化下一代，其余的个体则按轮盘赌选择法进化选择，这样可以保证下一代的最高适应度一定不小于上一代的最高适应度。②交叉操作。本文采用修正的单点交叉法。在普通单点交叉的基础上作一个小改动，两个交叉后的新子代只有适应度高于父代才替代父代进入种群，否则父代不参与交叉而直接进入种群。这样能保证新种群的适应度普遍比旧种群的高。③变异操作变异操作是为了提高当前个体在附近搜索的能力，而基本的变异操作选择在个体的随机位上取反。本文中个体的编码表示的是dx和dy，若基本变异操作应用在本文中，则使变异结果完全远离当前个体，可能使种群脱离最优解，达不到应有的效果。本文在基本变异操作的基础上作点改动，为了使变异后的个体限定在当前个体的附近，把变异的随机位限定在dx和dy权重的第1、第2和第3位上。④搜索中止条件。点集Q和P的匹配程度达到阈值要求，即证明两个点集是匹配的；或超过进化代数，即证明两个点集不匹配。达到这两个条件之一可中止搜索。
3仿真实例
采用matlab7.0平台实现本文算法。通过大量的实验操作，本文设定种群大小为80；最大进化代数为80；编码长度为18位，dx和dy各占9位，其中一位表示正负，则dx和dy的搜索范围为-（28-1）~28-1，即[-255~255]；交叉概率为0.8，变异概率为0.2。
图2为本文算法的匹配试验结果，a和b是两个来自同一手指的未匹配前的指纹图像，而且a图指纹只采集到b图指纹的一部分，c和d是基于遗传算法的匹配结果（c和d的图像中，圆点表示匹配点，叉点表示非匹配点）。结果表明，本文的算法能较精确的计算出匹配的旋转因子，平移后应用遗传算法基本上能搜索出大部分的匹配点，匹配效果好。
4结束语
利用遗传算法对指纹识别的匹配问题进行了讨论，针对基本遗传算法存在的早熟、局部最优等问题，提出了一种改进遗传算法，并用matlab进行仿真。仿真结果表明，改进的遗传算法有效解决基本遗传算法局部最优等缺点。
参考文献
[1]王小平.遗传算法·遗传算法:理论、应用及软件实现[M].西安:西安交通大学出版社,2002.
[2]杜鸿飞.基于PCNN及遗传算法的指纹识别算法研究[D].兰州:兰州大学,2006.
关键词 指纹识别；遗传算法；特征匹配
中图分类号 TP 文献标识码 A 文章编号 1673-9671-(2011)081-0215-02
生物识别是指利用人体的生理或行为特征进行个人身份鉴定的技术，包括有人脸识别、指纹识别、手型识别、虹膜识别、声音识别等，而指纹识别相对其他的识别技术，具有高稳定性和可靠性，是目前最成熟和最有前景的生物识别技术之一。
为了得到清晰的指纹及可靠的特征点，在匹配前要进行一系列的处理，过程如图1所示。通过读取设备得到图像后，首先要进行预处理，通过背景分割、滤波增强、细化等操作，使之更清晰，为下一步的特征点匹配作准备。最后采取某些方法对两个指纹的特征点进行比较，计算出它们的相似度，得出匹配结果。
指纹识别的最终目的匹配，所以匹配算法是指纹识别的关键步骤。匹配算法包括有点模式匹配、近邻结构匹配、基于结构特征的匹配、BP神经网络匹配算法等。这些算法存在计算量过高、效率低、寻优能力差等问题。遗传算法仿效生物的进化与遗传，根据生存竞争和优胜劣汰的法则，借助于遗传操作，使所求解的问题逐步逼近最优解。与其它方法相比，遗传算法通用性高、鲁棒性强、全局搜索能力强，适合全局优化问题的求解。
基本遗传算法有它的固有缺陷，容易陷入局部最优且收敛缓慢，本文对基本遗传算法进行一定的改进，并应用在指纹匹配算法中。实验结果表明，该方法具有较高的可靠性和有效性。
1指纹识别匹配
指纹匹配是指通过对两枚指纹的比较来确定它们是否同源的过程，实质就是把一幅指纹图像通过某种平移、旋转后变成另一幅图像，再与模板指纹图像进行比较，计算匹配的程度。指纹匹配的输入是两个关键点的点集P与Q。其中一个点集P是从输入的指纹图中提取出来的，另一个点集Q则是预先从标准的指纹图中提取出来，存储在模板库中。把这两个点集分别表示为：
其中，（xiP，yiP，αiP，）表示点集P中第i个关键点的信息：x坐标、y坐标和方向。假设两幅指纹图可以完全匹配起来，则可通过对输入的指纹图作某些变换（旋转、平移与伸缩）得到模板中的指纹图。因此点集P可以通过旋转、平移与伸缩等变换近似成点集Q。变换后试图寻找使两个点集尽可能多的匹配的变换。如果两个点不仅距离相近而且方向基本一致，则认为这两个点匹配。
设点集P中某点的坐标为（xiP，yiP），经过变换后为（xiT，yiT），公式如下：
其中，Δx与Δy是平移因子，θ是旋转角度。
根据上式，匹配的任务就是找出一组最佳的（Δx，Δy，θ），使一幅指纹变换后能跟另一幅指纹更好的匹配，也即存在最多的匹配点。遗传算法具有搜索全局最优解的能力，因此我们能够通过遗传算法，设置合适的编码方式、适应度函数和遗传操作，求解最优的一组（Δx，Δy，θ），找出尽可能多的匹配点，以判断两幅指纹图像是否来自同一个手指。
2基于遗传算法的指纹匹配
2.1基本遗传算法
遗传算法（Genetic Algorithm， GA）是借鉴生物界的选择淘汰、基因突变、基因遗传进化规律演变而来的一种随机搜索算法，其基本思想是基于Darwin的进化论和Mendel的遗传学说。
染色体是遗传物质的主要载体，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，遗传算法在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出新的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。这就是遗传算法的基本思想。
2.2基于改进的遗传算法的指纹匹配
1）编码。为了降低复杂度，本文采用文献[3]的方法确定两幅待匹配图的旋转因子θ，然后在旋转因子θ确定的情况下仅对dx和dy编码，这样遗传算法的搜索空间降为28×28。
本文中，遗传算法的个体编码采用多参数编码，即两个参数dx和dy结合在一起进行编码，每一个体由2段二进制编码组成，第一段是dx的编码，第二段是dy的编码，分别为9位，其中一位表示正负号。
2）适应度函数。适应度函数设置为：P按旋转因子变换成P*后，P*与Q之间的匹配程度。匹配程度则用两个匹配点集的距离和方向差来衡量。具体做法是，对点集Q中的每一点qj，寻找P*中与之相近的点pi，pi与qj之间的距离为Δd：
细节点的方向差为Δθ，当Δd和Δθ都在某一误差范围内时，则认为这两个点是匹配的。由于同一幅指纹的任意两个特征点的距离一般不超过纹线间隔λ，本文中λ为10，设Δd＝8，Δθ=0.2＝（0.2/3.14）*π＝0.064π。
当认为两个点匹配时，定义pi对qj的支持度为：f（qj，pi）=
（1/Δd）+（1/Δθ）。若有2个以上的特征点与其相近，就取其中最大的一个支持度。最后取Q中所有匹配点的支持度之和作为个体的适应度函数：
3）遗传操作。①选择操作。采用轮盘赌选择法，计算每个个体的适应度后，根据各个体的适应度大小按比例选择个体，适应度越大，被选择的机会越大。但轮盘赌选择法有一个缺陷，虽然最佳个体被选中的概率最大，但仍会有被排除的机会考虑到以上情况，本文对轮盘赌选择法稍作改动，令每代种群中适应度最高的个体自动进化下一代，其余的个体则按轮盘赌选择法进化选择，这样可以保证下一代的最高适应度一定不小于上一代的最高适应度。②交叉操作。本文采用修正的单点交叉法。在普通单点交叉的基础上作一个小改动，两个交叉后的新子代只有适应度高于父代才替代父代进入种群，否则父代不参与交叉而直接进入种群。这样能保证新种群的适应度普遍比旧种群的高。③变异操作变异操作是为了提高当前个体在附近搜索的能力，而基本的变异操作选择在个体的随机位上取反。本文中个体的编码表示的是dx和dy，若基本变异操作应用在本文中，则使变异结果完全远离当前个体，可能使种群脱离最优解，达不到应有的效果。本文在基本变异操作的基础上作点改动，为了使变异后的个体限定在当前个体的附近，把变异的随机位限定在dx和dy权重的第1、第2和第3位上。④搜索中止条件。点集Q和P的匹配程度达到阈值要求，即证明两个点集是匹配的；或超过进化代数，即证明两个点集不匹配。达到这两个条件之一可中止搜索。
3仿真实例
采用matlab7.0平台实现本文算法。通过大量的实验操作，本文设定种群大小为80；最大进化代数为80；编码长度为18位，dx和dy各占9位，其中一位表示正负，则dx和dy的搜索范围为-（28-1）~28-1，即[-255~255]；交叉概率为0.8，变异概率为0.2。
图2为本文算法的匹配试验结果，a和b是两个来自同一手指的未匹配前的指纹图像，而且a图指纹只采集到b图指纹的一部分，c和d是基于遗传算法的匹配结果（c和d的图像中，圆点表示匹配点，叉点表示非匹配点）。结果表明，本文的算法能较精确的计算出匹配的旋转因子，平移后应用遗传算法基本上能搜索出大部分的匹配点，匹配效果好。
4结束语
利用遗传算法对指纹识别的匹配问题进行了讨论，针对基本遗传算法存在的早熟、局部最优等问题，提出了一种改进遗传算法，并用matlab进行仿真。仿真结果表明，改进的遗传算法有效解决基本遗传算法局部最优等缺点。
参考文献
[1]王小平.遗传算法·遗传算法:理论、应用及软件实现[M].西安:西安交通大学出版社,2002.
[2]杜鸿飞.基于PCNN及遗传算法的指纹识别算法研究[D].兰州:兰州大学,2006.