弦箭算法的C语言实现本科毕业论文.doc

毕业设计论文题目： 弦箭算法的C语言实现内容摘要：静态复杂背景灰度图像的人脸快速精确定位问题，是近年来迫切需要解决和完善的问题。王洪群等教师提出了一种椭圆弦箭算法，利用图像中的边缘曲线快速确定人脸位置区域，缩小人脸检测算法的搜索空间，以提高人脸检测算法的速度与效率。本文主要通过对椭圆特性的分析，说明弦箭算法的原理，并在Microsoft Visual C+ 6.0环境下利用C语言进行编程实现。 索引关键词人脸检测 边缘 弦箭算法Abstract: Locating human face in a single and gray level image with cluttered background remains a difficult problem and needs to be completed or perfected in recent year. A novel ellipse arrow method using edge information of the image to location the area of face fast has put forward by Mr. wang and others. The method contract the space of the manhunt of the face detection, raise the speed and the efficiency of the face detection. The article introduce the theories of the ellipse arrow method through the analysis to the oval characteristic, and programme the method making use of the language of C under the Microsoft Visual C+6.0 environments.Keywords: Face Detection Edge Ellipse The ellipse arrow method目录第一章 绪论- 2 -1、1引言- 2 -1、2 弦箭算法地提出- 2 -1、3 弦箭算法的应用- 4 -1、4 本文研究的主要内容和成果- 4 -第二章 弦箭算法的原理- 5 -2、1 椭圆特性分析- 6 -2、2 弦箭累加算法的原理- 7 -第三章 弦箭算法的编程实现- 10 -3、1 BMP图像文件格式- 10 -3、2 本文编程环境- 12 -3、3 弦箭累加的编程实现- 13 -第四章 实验检测与分析- 25 -4、1 图像测试集- 25 -4、3 评估准则- 25 -4、4 不同参数下的实验结果- 26 -4、5 算法中间结果示例- 28 -4、6 算法最终人脸区域估计结果示例- 28 -4、7对算法及实验结果的分析总结- 30 -后记32致谢32参考文献32弦箭算法的C语言实现第一章 绪论1、1引言人脸识别技术起源于上个世纪六十年代，发展到现在已经有了四十多年的历史，是当前模式识别和人工智能等领域的一个重要的研究课题。人脸识别作为一种重要的个人身份鉴别方法，其研究前景十分广阔，无论是在商业还是法律仲裁领域等都拥有巨大的应用空间。例如静态领域中的医学、档案管理、刑侦破案、证件验证、入口控制；动态领域中的人群监控、视频会议、人机交互系统等。人脸识别 (Face Recognition)是指对一个输入的图像或视频图形，判断其是否含有人脸图像，如果存在人脸图像,再进一步判断图像中人脸的大小，位置，以及面部各个主要器官的位置。再从这些信息中提取人主要的身份信息，将这些信息与数据库中的信息相比较,从而得到人的一些授权信息。人脸识别技术的主要内容可分为为：输入图像-人脸检测-人脸跟踪-人脸比对-输出结果。人脸识别首先要对输入的图像进行人脸检测。人脸检测(Face Detection)，是指在既有的图像中判断是否存在人脸并确定人脸的位置、大小等相关信息，进一步提供人脸的主要特征。人脸检测作为人脸信息识别处理中的一项关键技术，其检测效率的高低将直接影响到后续模块的执行效果。1、2 弦箭算法地提出人脸检测是一个复杂的具有挑战性的模式检测问题。图像中的人脸往往随光线的改变、位置的移动、倾斜、旋转和缩放等外部变化而变化，而且人脸内部也具有复杂的变化，如表情、长相、胡须、眼睛闭合、眼镜等。人脸的不确定性，对人脸检测算法的稳定性和鲁棒性提出了更高的要求。目前，研究人脸检测的方法有很多，定位算法的精度在不断提高，也更加复杂。各种人脸检测算法中，精度及鲁棒性好的算法，运算量都比较大，直接对图像进行计算，在时间上让人难以忍受。Adaboost学习算法是目前最快的人脸检测算法之一。Boosting 是一种分类器融合算法。Adaboost学习算法通过对一些弱的分类器的组合来形成一个强的分类器。在Adaboost算法中，简单的分类算法被称为弱学习算法。Adaboost算法通过一个迭代的训练过程来得到一个强的分类器。在第一次训练出一个弱分类器后，训练样本的权重得到调整，从而使没有被第一次训练出的弱分类器正确分类的样本的权重增加。如此迭代下去，最终得到的分类器是对每次训练得到的弱分类器的一个线性组合。由于Adaboost算法，要通过迭代训练将弱的分类器组合成强的分类器，其运算很耗资源。在实际应用中往往都是结合其他算法来提高运算效率。人脸的边缘图富含大量的人脸特征信息，许多学者利用这些边缘信息来确定人脸的区域。大多数学者使用Hough变换来检测人脸外边缘，但如果用标准的Hough变换检测人脸椭圆边缘需要在一个5维的参数空间做投票累加，这样的计算量是难以忍受和不切实际的。Wang 和Tan利用输入图像边缘梯度向量和椭圆模型的边缘梯度方向向量内积的大小来衡量匹配程度；Li和Roeder在预先确定的人脸区域内使用简化的自适应Hough变换，检测垂直的脸颊直线边缘和下颚抛物线边缘；Yuen分成两步检测椭圆：利用椭圆边缘上任意两点的切线的交点和这两点的连线的中点的连线必然经过椭圆中心，首先确定椭圆的中心坐标，再确定剩下的三个参数，虽然比标准Hough变换运算量减少了不少，但运算量仍很大。人脸含有众多的椭圆曲线边缘，如外层、内层头发边缘、嘴眼边缘、耳朵边缘、下颚边缘等，且曲线凹向均指向人脸内部。王洪群等人通过对椭圆曲线的分析，提出的了一种特殊的椭圆弦箭累加算法。该算法避免使用Hough变换等一些耗时的算法，具有大面积快速搜索的能力，确定的搜索范围较小，可以快速确定人脸主要特征（人眼和嘴）所在的大致位置和区域。该算法利用图像的边缘快速确定搜索空间，并在搜索空间内使用虹膜网格采样矩阵进行纹理分析，采用在频域中按指数增长的分布方式设计Cabor滤波器，进一步提高了Cabor滤波器纹理分析效率，从而精确定位人眼和嘴。该算法复杂度适中，运算量较小，定位精度较高，鲁棒性好，有很大的实用价值。1、3 弦箭算法的应用弦箭算法的提出是在对椭圆曲线特性分析的基础上，根据人脸边缘中的椭圆曲线，来快速准确地确定人脸大概区域位置。其原理主要是根据椭圆曲线的法线簇交点的包络线位于椭圆内部，从而确定椭圆大概区域，即人脸大概区域位置。弦箭算法可以有效提高当前人脸检测算法的检测速度和检测正确率，在人脸识别与跟踪等领域有着重要的应用。从椭圆曲线的一般性来看，弦箭算法还有更加广泛的应用。弦箭算法主要是利用图像中人脸的边缘曲线，快速确定搜索空间。实际上，任意一幅图像，其确定的是图像中类椭圆型形状物体的大概区域位置。所以根据具体实际应用，通过对算法进行改进，在此基础上结合其他算法，可以有效实现对各种椭圆形物体的检测。因此椭圆弦箭算法在计算机视觉技术，模式识别等领域可以实现更加广泛的应用。1、4 本文研究的主要内容和成果本文的主要内容是对弦箭算法的原理进行分析与介绍，并用C语言进行编程，实现应用弦箭算法快速估计出人脸大概区域位置，以提高后序人脸算法的效率。弦箭算法是研究在二维图像中检测正面人脸的快速算法。通过对椭圆曲线特性的分析，可以知道，在椭圆上等间隔做法线，当椭圆长短轴长度相差不大时，椭圆法线簇包络线的交点必在椭圆内部，接近于椭圆中心。人脸含有众多的椭圆边缘曲线，其凹向大都指向人脸内部，如果对这些边缘曲线做法线，进行累加投票，其累加和最大峰值的位置必接近于人脸内部，而图像背景中边缘曲线的凹向随机性很大，累加和最大峰值出现的概率就非常小，从而可以确定人脸大概区域位置。本文编程所使用的环境是Microsoft Visual C+ 6.0，用C语言编程实现弦箭算法。对于读入的图像，首先进行间隔采样和高斯滤波，利用Canny算子对滤波后的图像进行边缘检测，得到图像中的边缘曲线。再通过相应的算法对图像进行预处理：割断分叉的边缘点，去除边缘曲线中大于某一阈值的直线和长度过短的曲线。进而对剩下各条曲线依次应用弦箭算法，在各点进行累加投票，并记录最大箭长，根据累加和峰值和最大箭长来确定人脸大概区域位置。本文研究弦箭算法的主要目的是快速估计出人脸大概位置区域，提高当前人脸检测算法的效率。本文在一个现有程序中编程嵌入弦箭算法，实现了对于给定一张256色的二值灰度图像，快速估计出人脸大概位置区域，估计出人脸图像中眼睛或嘴巴所在的区域。第二章 弦箭算法的原理人脸的边缘可以近似为一些椭圆曲线，如图2-1所示的人脸边缘模型。通过观察，人脸边缘线的共同特点就是：无论头发的边缘、脸颊的边缘以及下巴的边缘，其凹向总是指向人脸的内部。通过对人脸边缘曲线及椭圆特性的分析，我们提出了椭圆弦箭累加算法，可以快速确定人脸主要特征（人眼和嘴）所在的大致位置和区域。图2-12、1 椭圆特性分析如果在椭圆上等间隔做法线可得图2-2所示的星形包络线。可以证明，当椭圆长短轴长度相差不大时，包络线的交点必在椭圆内部，接近于椭圆中心。图2-2分析如下：设椭圆中心点在原点，a、b分别为椭圆长短轴长度，则椭圆参数方程可表示为：则椭圆上任意点( acos,bsin )的法线的斜率为tan，法线簇的方程为：化简得：上式左边对求导（把x和y看作常数）可得：根据微分几何原理，包络线的方程应同时满足式（2-3）和式（2-4），从式（2-3）和式（2-4）中可得包络线方程为：由此可得，包络线与坐标轴的四个交点位置分别为：（a-b，0），（0，-（a-b），（-（a-b），0），（0，a-b），分别对应=0,/2, 3/2。当ab时，按参数方程绘制，可得星形包络线；当a=b时，法线相交于中心点；当a、b相差不大时，四个交点必接近于椭圆中心，位置在椭圆内部。2、2 弦箭累加算法的原理从对椭圆特性的分析可以看出，如果将椭圆法线在二维累加平面上做累加的话，那么累加和峰值必然集中于上述包络线的四个交点或中心点的位置。人脸含有众多的椭圆曲线边缘，如外层、内层头发边缘、嘴眼边缘、耳朵边缘、下颚边缘等，且曲线凹向均指向人脸内部，如果也做累加投票的话，累加和最大峰值的位置必接近于人脸内部。相反，背景图像边缘的凹向随机性很大，形成累加和最大峰值的概率就很低。椭圆弦箭累加算法就是利用这种特性，来实现人脸区域位置的估计。通过弦箭算法计算人脸大概位置区域主要分为三步：图像预处理、弦箭算法、确定人脸区域大概位置。一、图像预处理为减少运算量，对较大的源图像可进行间隔采样，并对采样后的图像进行高斯滤波。（1）采用canny算子提取滤波后的边缘。（2）割断分叉边缘点，使所有边缘线都不分叉。（3）过滤掉边缘中长度大于某一阈值的直线，一般使用简单的链码过滤方法。（4）去除长度过小的边缘线。（5）对边缘线进行编号并获得坐标点序列X（k，num），Y（k，num)，k=1，2，3，L（num），其中num为曲线编号，k为像素序列号，L（num）为标号为num的曲线上的像素点个数。二、弦箭算法边缘图在去除直线之后，较大的人脸的边缘曲线就较难连续，如果是较小的人脸，则边缘线就更接近于圆。所以，边缘上的两点连线的垂直中分线就和与垂直中分线相交的边缘上的点的法线很接近。为了运算简单，用椭圆弦线的垂直中分线来近似代替椭圆的法线。垂直中分线以弦线中点为起始点，方向指向曲线内部延伸，如图2-3所示，形同弓箭。下文称垂直中分线为箭，弦线中心点为箭尾，另一端为箭头，算法简称弦箭法。以图2-3为例弦箭算法描述如下：图2-3弦箭算法举例（A向B）（1）建立三维数组表A（i，j，k），i=1m，j=1n，k=1，2；并初始化为零。其中A（i，j，1）中保存累加和，A（i，j，2）中保存最大距离。（2）对各边缘曲线依次使用弦箭法，每个曲线包括正反和两个移动过程：正向过程：假设如图2-3所示的任意一椭圆曲线AB，先任意固定弦的一端如A点，弦的另一端随曲线移动，每移动一次称为一次“跨步”。“跨步”的长度以弧长计算（像素点个数近似代替），箭长为每次弦所跨过的曲线弧长的倍。如图2-3所示，每个过程包含若干“跨步”：第1 跨步：设最小跨步弧长为S，如果S小于曲线弧长L，则“跨步”到弧长为S的点t1，否则算法中止。在A（i，j，k）的对应坐标位置上“绘制”长度为S个像素的垂直中分线，此即箭a1。图2-3中的箭头只是为了表示垂直中心线“绘制”方向，方向指向曲线的内部，方向判断在此不做详述。“绘制”的含义包含（a）、（b）两个方面：（a）在箭a1，即在垂直中分线对应的累加数组A（i，j，k）的位置上如式（2-6）做累加：（b）累加的同时，做如下作，其中Dis为当前位置到箭尾的距离：If Dis>A(i,j,2) then将此距离填入距离表中：A（i，j，2）=Dis;else 进入箭的下一个点；end以下各跨步和第1跨步相似，为叙述方便，设|Ati|为A到ti的距离。第2跨步：如果2S<L,且|At2|>|At1|，则跨到2S弧长的点t2，“绘制”箭a2，箭长2S。否则，结束正向过程。第3跨步：如果3S<L，且|At3|>|At2|，则跨到3S弧长的点t3，“绘制”箭 ，箭长3S。否则，结束正向过程。第n跨步：如果nS<L，且|Atn|>|At(n-1)|，则跨到弧长为nS的tn的位置，“绘制”箭，箭长nS。否则，结束正向过程。图2-3中由于|Atn|<|At(n-1)|，所以不“绘制”an，结束正向过程。反向过程：固定B点，向A点的方向“跨步”，方法同正向过程。当反向过程停止时，则该曲线的弦箭算法结束，进入下一条曲线。当所有的曲线的弦箭算法结束后则开始确定人脸区域大概位置。在上述弦箭法的正反过程中，有如下特殊情况需要处理：（1）当弦与所跨曲线近似重合，相差小于某个阈值时，该箭不做累加，如图2-4中的a1。（2）从A向B“跨步”，当弦与边缘曲线有交点时，如图2-4(a)，则将固定点移到交点c处，重新向B点方向进行“跨步”，直到剩下的曲线CB的弦箭算法结束为止。从B向A时方法相同。直到曲线AB的两个方向的过程进行完为止。（3）当箭的角度较大，近似90度时；或较小，近似0度时，由于累加数组的分辨率，导致出现类似图2-4(b)左边直线累加位置的间断。如图2-4(b)箭头右边所示将直线填满，保证所有箭在累加数组中的连续性。图2-4弦箭法特殊情况处理三、确定人脸区域大概位置首先，求A（i，j，1）数组中的最大值所在的位置（Xmax，Ymax）。然后在数组A（i，j，2）内以（Xmax，Ymax）坐标为中心，宽度为2a的正方形区域内求A（i，j，2）的最大值Dmax。确定以（Xmax，Ymax）为中心以宽度为2Dmax的正方形区域作为人脸位置的大概区域：=A(i,j,1)>= ,|i-Xmax|<Dmax,|j-Ymax|<Dmax。根据能够射向累加和最大值区域中的最长的箭，其所属曲线也必然最长，最靠近外部，接近于头像外部轮廓的可能性也最大。所以采上述矩形框将人眼、嘴覆盖在内的可能性也最大，同时也可最大程度地缩小搜索空间。其中可根据图像大小和精度要求来确定；当图像较小定位精度要求高时，取=0。第三章 弦箭算法的编程实现3、1 BMP图像文件格式数字图像有多种存储格式，本文编程主要针对复杂背景下的二值灰度图像，对于其他格式的图像文件，可以通过多种工具很方便的转化为灰度图像，下面首先介绍BMP图像文件格式。BMP（BitMap Picture）文件格式是Windows系统交换图形、图像数据的一种标准格式。BMP图像的数据由四部分组成：位图文件头、位图信息头、调色板、位图数据。第一部分为位图文件头BITMAPFILEHEADER，它是一个结构体，其定义如下：typedef struct tagBITMAPFILEHEADERWORD bfType;/文件类型，必须是0x424D，即字符串“BM”DWORD bfSize; /指定文件大小，包括这14个字节WORD bfReserved1; /保留字WORD bfReserved2; /保留字DWORD bfOffbits; /从文件头到实际位图数据的偏移字节数BITMAPFILEHEADER；这个结构的长度是固定的，为14个字节（WORD为无符号16位二进制整数，DWORD为无符号32位二进制整数）。第二部分为位图信息头BITMAPINFOHEADER，也是一个结构体，其定义如下：typedef struct tagBITMAPINFOHEADERDWORD biSize; /该结构的长度，为40LONG biWidth; /图像的宽度，单位是像素LONG biHeight; /图像的高度，单位是像素WORD biPlanes; /位平面数，必须是1WORD biBitCount; /指定颜色位数，1为二值，4为16色/8为256色，16、24、32位真彩色DWORD biCompression; /指定是否压缩DWORD biSizeImage; /实际的位图数据占用的字节数LONG biXPelsPerMeter; /目标设备水平分辨率LONG biYPelsPerMeter; /目标设备垂直分辨率DWORD biClrUsed; /实际实用的颜色数，若该值为0，则使/用的颜色数为2的biBitCount次方种DWORD biClrImportant; /图像中重要的颜色数，若该值/为0则所有颜色都是重要的BITMAPINFOHEADER；这个结构的长度是固定的，为40个字节（LONG为32为二进制整数）。其中，biCompression的有效值为BI_RGB、BI_RLE8、BI_RLE4、BI_BITFIELDS,这都是一些Windows定义好的常量。由于RLE4和RLE8的压缩格式用的不多，一般biCompression的有效值为BI_RGB，几步压缩的情况。第三部分为调色板（Palette），这里是对那些需要调色板的位图文件而言的。真彩色图像是不需要调色板的，BITMAPINFOHEADER后直接是位图数据。调色板实际上是一个数组，共有biClrUsed个元素（若该值为零，则有2的biBitCount次方个元素）。数组中每个元素类型是一个RGBQUAD结构，占4个字节，其定义如下：typedef struct tagRGBQUADBYTE rgbBlue；/该颜色的蓝色分量BYTE rgbGreen/该颜色的绿色分量BYTE rgbRed；/该颜色的红色分量BYTE rgbReserved；/保留值RGBQUAD；第四部分就是实际的图像数据。对于用到调色板的位图，图像数据就是该像素颜色在调色板中的索引值，对于真彩色图像，图像数据就是实际的R、G、B值。下面就2色、16色、256色和真彩色位图分别介绍。对于2色位图，用1位就可以表示该像素的颜色（一般0表示黑，1表示白），所以一个字节可以表示8个像素。对于16色位图，用4位就可以表示该像素的颜色，所以一个字节可以表示2个像素。对于256色位图，用8位就可以表示该像素的颜色，所以一个字节刚好可以表示1个像素。下面有两点需要注意：（1）每一行的字节数必须是4的整数倍，如果不是，则需补齐。（2）BMP文件的数据存放是从下到上，从左到右的。也就是说，从文件中最先读到的是图像最下面一行的左边第一个像素，然后是第二个像素，接下来是倒数第二行左边第一个像素，左边第二个像素。以此类推，最后得到的是最上面一行的最右边的一个像素。3、2 本文编程环境本文编程所使用的环境是Microsoft Visual C+ 6.0。Visual C+提供了一个支持可视化编程的集成开发环境，采用标准的多窗口Windows用户界面，易于使用，可以很方便的生成人机界面。通过C+编程，弦箭算法可以方便地嵌入实际应用，其代码也可应用于诸多领域。由于MFC没有封装处理与DIB位图相关的Windows API函数的类，使得利用C语言实现对图像的处理相对复杂。本文利用一个现有的图像处理程序ImageProcessing，在此基础上，嵌入弦箭算法。利用该程序，可以很方便地读取图像的各种信息，以及对图像数据进行计算。3、3 弦箭累加的编程实现一、类Cdib 及canny算子程序ImageProcessing是在VC+环境下编写的对BMP图像进行处理的MFC AppWizard程序，可以对BMP图像进行变换、特征提取、图像分割等多种处理。程序通过类Cdib来实现对BMP图像文件的读取、显示、保存以及获取图像文件信息等， 在程序ImageProcessing中，类Cdib共设计了13个属性（成员变量）和30个成员函数，通过它们来完成对图像的一些处理。这里对类Cdib中的13种属性进行简要说明如下：LPVOID m_lpvColorTable：调色板指针；HBITMAP m_hBitmap：BITMAP结构指针；LPBYTE m_lpImage：DIB位图数据块地址；LPBITMAPINFOHEADER m_lpBMIH：DIB信息头指针；HGLOBAL m_hGlobal：全局的句柄，用于内存映射文件中； Alloc m_nBmihAlloc：表示信息头内存分配的状况；Alloc m_nImageAlloc：表示位图数据分配的状况；DWORD m_dwSizeImage：DIB位图中的字节数（信息头和调色板数据除外）；int m_nColorTableEntries：调色板表项数；HANDLE m_hFile：文件句柄；HANDLE m_hMap：内存映射文件句柄；LPVOID m_lpvFile：文件句柄；HPALETTE m_hPalette：调色板句柄；对于Cdib类的构造函数、文件读写成员函数以及大多数Get成员函数等意义都是暗含的，程序中也都有详细的注解，在此不再详细讨论。canny算子是对图像进行边缘检测的一种算法，其主要通过以下几个函数来实现：函数GaussianSmooth对原图象进行高斯滤波；函数DirGrad来计算x、y方向上的导数；函数GradMagnitude计算梯度的幅度；通过函数NonmaxSuppress应用non-maximum 抑制；应用Hysteresis，找到找到所有的边界。canny函数输入参数说明如下:unsigned char *pUnchImage- 图象数据int nWidth - 图象数据宽度int nHeight - 图象数据高度double sigma - 高斯滤波的标准方差double dRatioLow - 低阈值和高阈值之间的比例double dRatioHigh - 高阈值占图象象素总数的比例unsigned char *pUnchEdge - canny算子计算后的分割图canny分割算子，计算的结果保存在pUnchEdge中，逻辑1(255)表示该点为边界点，逻辑0(0)表示该点为非边界点。该函数的参数sigma，dRatioLow，dRatioHigh，是需要指定的。这些参数会影响分割后边界点数目的多少，程序中这些参数取值为0.4, 0.4, 0.79。经过canny算子计算后的结果如下图3-1所示。（a）原图 （b）canny算子计算后的图像图3-1二、割断图像中分叉的边缘点经过canny算子的图像曲线，会有很多分叉的曲线，我们通过将曲线交叉点置为0来将其断开。首先按从上到下的、从左到右的顺序扫描图像，寻找数值不为0的点，定义整形变量count来记录该点四邻域中不为0的点的个数，count初始化为0。若count值大于2，则表示曲线在该点处分叉， count值小于1（即为0），表示该点为孤立点，count值为1表示该点为其所在曲线的一个端点，count值为2表示该点为曲线的一个中间点。我们只要要将count值大于2的点置为0，就可以将分叉的曲线断开，但是这样做会将分叉的曲线断成三条曲线，如图3-2（b）所示。通过分析发现，如果将该点四邻域中不为0的一个点置为0，最多只会将曲线断成两条曲线，如图3-2（c）所示。这样不仅减少了曲线条数，也是曲线尽可能不被断成短线，提高算法准确率。该段程序流程如图3-3所示。abcd0bcdab0d（a） a点四邻域有b、c、d三个点，曲线在a点处分叉（b） 若将a点置为0后，b、c、d点分别位于三条曲线（c） 若将a点邻域中c点置为0后，曲线最多被分割成为两条： c点引出的曲线和a、b、d点所在曲线图3-2三、删除图像中长度大于某一阈值的直线过滤掉边缘曲线中的长度大于某一阈值的直线，对直线的判断采用爬行算法，删除图像中长度大于某一阈值的直线，主要通过Del_line 和Del_l两个函数来实现。函数Del_l（）实现的功能是删除从点（x，y）开始的dir_long个值为255的点，其输入参数说明如下： unsigned char *pUnchEdge - 经过边缘检测后的图象数据； int nWidth - 图象数据宽度； int x，int y - 图象数据中的点（x，y）；int dir_long - 要删除的点的个数； 在函数中定义了变量x1、y1来对各点进行判断，其初始化为x、y，通过变量i控制循环。算法流程图如图3-4所示。图3-3 割断分叉点 图3-3Del_l函数流程图 函数Del_line()实现的功能是删除图像中长度小于某一阈值p的直线，其输入参数说明如下: unsigned char *pUnchEdge - 经过边缘检测后的图象数据 int nWidth - 图象数据宽度int nHeight - 图像数据高度 int x，int y - 图象边缘曲线中的一个点在函数中定义变量x1、y1来依次对各点进行判断，其值初始化图3-4 Del_line函数流程图为x、y；变量p为长度阈值；变量dir为方向向量，记录曲线中点的走向，初始化为0；变量dir_long为直线长度，初始化为0；通过new函数开辟一段大小为nWidth*nHeight的数据单元unsigned char * pUnchEdge1，其数据初始化为图像数据，通过其来控制我完成对曲线的搜索计算。该函数算法流程图如图3-4所示,函数在完成对变量的初始化后，从点（x，y）判断曲线的下一个点在其四邻域中的位置方向，dir记录了上一次判断的方向。如果dir与本次判断一致，则变量dir_long加一。如果不一致，且dir_long的值是小于阈值p，只需更改dir的值，继续判断下一个点；如果dir_long的值大于阈值p，则先改变曲线下一个点的值（将其赋值254），调用del_l函数删除从（x1，y1）开始的曲线上的dir_long个值为255的点。再递归调用dir_long函数从这下一个点开始判断，直至该条曲线所有点判断完毕后，算法结束。四、搜索并标记曲线算法该算法主要是依次搜索图像中各条曲线，在数组pUnchImage记录图像中各点所在曲线的序号，并删除图像中过短的曲线。算法通过函数Del_cur和函数Serch_cur来实现，算法流程图如下图3-5所示。函数Del_cur用于删除图像中以点（x，y）为起始点的曲线。曲线中所有的点在pUnchImage中标记了对应曲线序号，图像数据pUnchEdge中标记了曲线端点，曲线中其余点均为0，曲线端点在pUnchEdge中以值不为0。删除曲线后，图像数据pUnchEdge、曲线编号数据pUnchImage中各点对应值均置为0。函数的输入参数说明如下：unsigned char *pUnchEdge 对图像中曲线进行搜索处理过的图象数据 unsigned char *pUnchImage- 记录图像中各点所在曲线编号的数据 int nWidth - 图象数据宽度int x，int y - 图象中所要要删除曲线的一个端点坐标 函数中定义（x1,y1）来对曲线上个点进行删除处理，算法流程图如图3-6所示。图3-5 搜索标记曲线算法流程图 图3-6 Del_cur函数流程图函数Serch_cur用以找出以点（x，y）为起始点的曲线中所有的点（曲线中的点值为255），在pUnchImage中标记点所在曲线的序号，将曲线中各点（不包括起始点（x，y），点（x，y）在pUnchEdge值为253进行了标记）对应在pUnchEdge中的值置为0。曲线搜索完毕，判断曲线长度size是否小于阈值min_size，若size小于阈值 min_size，则调用del_cur函数将该条曲线删除，删除后，曲线长度size为0。函数返回size，可根据size值是否为0判断曲线是否被删除，再进行其他处理。函数的输入参数说明如下：unsigned char *pUnchEdge - 经过边缘检测后的图象数据unsigned char *pUnchImage- 该数组用于记录图像中各点所在曲线序号int nWidth - 图象数据宽度int x，int y - 要搜索曲线的起始点坐标int cur_num - 该条曲线序号int min_size - 曲线长度阈值,默认值取20Serch_cur函数数据类型定义为整形，返回值为曲线长度size。函数中定义x1,y1来对曲线中各点进行搜索处理。函数算法流程图如下页图3-7所示。图3-7 Serch_cur函数流程图五、弦箭算法去除了图像边缘曲线中的直线段和过短的曲线，图像中的曲线就较多为人脸边缘曲线（也包含去除不了的噪声曲线）。弦箭算法就是利用弦两点间的垂直平分线近似代替弦所跨曲线的法线，依次对各条曲线进行投票累加，算法主要通过xj函数来实现。算法首先根据pUnchEdge和pUnchImage中的值依次查找各条曲线，并将曲线上各点坐标值存入数组cur，定义两个数组a1和a2，来代替弦箭算法原理中的三维数组，分别记录各点弦箭累加值和最大箭长，通过调用xj函数来来完成箭的“绘制”。数组cur中依次记录了曲线各点坐标值，我们只需要将cur中的数据按坐标点进行反向存取，调用xj函数，即可实现反向跨步。该段算法流程图如图3-8所示。图3-8 弦箭算法流程图图3-9 xj函数流程图 xj函数主要实现对曲线进行弦箭累加计算，完成跨步和箭的“绘制”。函数的输入参数说明如下:int cur_num - 曲线长度Point *cur - 曲线数组地址指针int nWidth - 图象数据宽度unsigned char *a1 - 记录各点弦箭累加值unsigned char *a2 - 记录各点最大箭长int x - 图像宽度int y - 图像高度弦箭累加计算的结果保存在数组a1和a2中，数组a1记录累加值，数组a2记录箭长。在进行跨步射箭累加时，首先对第二章原理中提到的前两种特殊情况进行处理，判断弦与曲线有无交点。如果当弦与所跨曲线近似重合，不做操作继续跨步。对于第二种特殊情况，在判断弦与曲线有无交点时，我们从曲线上固定点开始，依次将所跨曲线上的点代入弦所在直线方程，如果某点C满足方程，C即弦与曲线的交点，就将固定点移到C点继续跨步。对于第一种特殊情况，我们从固定点开始计算，相同横坐标下，曲线和弦的纵坐标差值之和e， e为0表示弦与曲线近似重合，不作操作。同时，根据e和弦的垂直中分线的斜率k0，可以判断射箭方向：如果e>0&&k0<0|e<0&&k0>0则向右射箭，如果e<0&&k0<0|e>0&&k0>0则向左射箭。在绘制箭的过程中，对于第三种特殊情况，如果箭的下一个点与上一个点不相连，则补充相应的点使箭