基于凸壳的指纹轮廓线快速计算

6.1　基于凸壳的指纹轮廓线快速计算

指纹边界轮廓线通常都是凸壳，但由于指纹采集与指纹本身的噪声影响，使得分割后的指纹边界往往并不是一个凸壳。根据指纹的这一实际情况，可采用格雷汉姆（Graham）方法来求指纹边界点的凸壳，并将所得凸壳作为指纹图像的轮廓线。国内外不少研究者（例如：杨德英等）研究了基于凸壳的指纹轮廓线。

格雷汉姆方法的依据，是凸多边形的各顶点必在该凸多边形的任意一条边的同一侧。其指纹轮廓应用原理可简述如下：

输入：“前景为黑，背景为白”的二值化指纹图像点集S。

输出：分割指纹前景与后景的凸壳点。

第1步：求S中前景点的X坐标最大、最小值所对应的点，设为P_xmax与P_xmin。

第1-1步：r =（P_xmax−P_xmin）/k，k为适当正整数；划分图像点集S所在域为k个其宽度为r的长条域；计算图像点集S中各点所在长条域的编码，使位于第i个长条域的点构成条域点集S_i，使图像点集S满足

第1-2步：计算条域点集S_i中点的y坐标最大、最小值所对应的点，记设为Pⁱ_ymax与Pⁱ_ymin，并记凸集S′_i={P_xmax，P_xmin，Pⁱ_ymax，Pⁱ_ymin}，其中i=1，…，k。比较相邻条域点集S_i−2，S_i−1，S_i，S_i+1，S_i+2各点中的Y坐标值最大者：若两侧大于中间者，则删去位于中间的其Y坐标值较小的点。同理，对Y坐标最小者，也作类同处理。

第1-3步：设凸集S′_i中的Y坐标最小点为P₁，把P₁同凸集S′_i中其他各点P_i用线段连接，并计算这些线段与水平线的夹角。然后，按夹角的大小和到P₁的距离，对各点P_i进行词典式分类排序。P₁点是凸壳的起点，P₂ 及P₃点也是凸壳边界的起点。

第1-4步：按如下方法，删去P₃，P₄，…，P_n-1中不是凸壳的点。

如果　P₁和P_k分别在线段P_k-j+1P_k−j两侧，则：删去P_k−1，后继顶点编号减1，k=k−1，j=j−1否则：让P_k−1暂为凸壳顶点，并标记之；

第1-5步：顺序输出指纹轮廓凸壳顶点（注：该算法的时间复杂度为O（n+k），偏差距离不大于1，适用于指纹轮廓点集的修正计算）。

第2步：对步骤1所得指纹轮廓凸壳各顶点，再施行双三次B样条变换平滑化处理（其平滑化处理详细过程，从略）。

结束步：输出所形成的由光滑曲线描述的指纹。

据此指纹轮廓凸壳算法结论，就可利用凸壳来较高程度地提升指纹识别的正确性与精确度。