弦箭算法的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 DisA(i,j,2) then将此距离填入距离表中：A（i，j，2）=Dis;else 进入箭的下一个点；end以下各跨步和第1跨步相似，为叙述方便，设|Ati|为A到ti的距离。第2跨步：如果2S|At1|，则跨到2S弧长的点t2，“绘制”箭a2，箭长2S。否则，结束正向过程。第3跨步：如果3S|At2|，则跨到3S弧长的点t3，“绘制”箭 ，箭长3S。否则，结束正向过程。第n跨步：如果nS|At(n-1)|，则跨到弧长为nS的tn的位置，“绘制”箭，箭长nS。否则，结束正向过程。图2-3中由于|Atn|= ,|i-Xmax|Dmax,|j-Ymax|0&k00|e0则向右射箭，如果e0&k00&k00则向左射箭。在绘制箭的过程中，对于第三种特殊情况，如果箭的下一个点与上一个点不相连，则补充相应的点使箭连续，