【正文】 嘴巴所在的區(qū)域。 第二章 弦箭算法的原理 人臉的邊緣可以近似為一些橢圓曲線，如圖 21 所示的人臉邊緣模型。通過觀察，人臉邊緣線的共同特點就是：無論頭發(fā)的邊緣、臉頰的邊緣以及下巴的邊緣，其凹向總是指向人臉的內(nèi)部。 通過對人臉邊緣曲線及橢圓 特性 的分析，我們提出了橢圓弦箭累加算法，可以快速確定人臉主要特征（人眼和嘴）所在的大致位置和區(qū)域。 圖 21 1 橢圓特性分析 如果在橢圓上等間隔做法線可得圖 22 所示的星形包絡(luò)線。可以證明，當(dāng)橢圓長短軸長度相差不大時，包絡(luò)線的交點必在橢圓內(nèi)部 ，接近于橢圓中心 。 圖 22 分析如下：設(shè)橢圓中心點在原點， a、 b 分別為橢圓長短軸長度，則 橢圓參數(shù)方程 可表示 為： ）（為參數(shù) 12s i nc os ???? ?? ???by ax 則橢圓上任意點 ( acosθ ,bsinθ )的法線的斜率為 tanθ，法線簇的方程為： 2)(2 a c ost a nb s i ny ）（ ??? ?? x 化簡得： )32(02s i n2c o ss i n ????? ??? bayx 上式左邊對θ求導(dǎo)（把 x 和 y 看作常數(shù)）可得： )42(0b ) c os 2(ay s i nc os ??? ???x 根據(jù)微分幾何原理， 包絡(luò)線的方程應(yīng)同時滿足式（ 23）和式（ 24），從式（ 23）和式（ 24）中可得包絡(luò)線方程為： )52()2/0(c o s2s i n2s i n2c o s)(s i n2s i n2c o s2c o s)(????????????????????????????babaybabax 由此可得，包絡(luò)線與坐標軸的四個交點位置分別為：（ ab， 0）， （ 0， （ ab）），（ （ ab）， 0），（ 0， ab），分別對應(yīng)θ =0,π /2,π , 3π /2。當(dāng) a≠ b 時，按參數(shù)方程繪制，可得星形包絡(luò)線；當(dāng) a=b 時，法線相交于中心點；當(dāng) a、 b 相差不大時，四個交點必接近于橢圓中心，位置在橢圓內(nèi)部。 2 弦箭累加算法的原理 從對橢圓特性的分析可以看出，如果將橢圓法線在二維累加平面上做累加的話，那么累加 和 峰值必然集中于上述包絡(luò)線的四個交點或中心點的位置。人臉含有眾多的橢圓曲線邊緣，如外層、內(nèi)層頭發(fā)邊緣、嘴眼邊緣、耳朵邊緣、下顎邊緣等，且曲線凹向均指向人臉內(nèi)部，如果也做累加投票的話，累加和最大峰值的位置必接近于人臉內(nèi)部。相反，背景圖像邊緣的凹向隨機性很大，形 成累加和最大峰值的概率就很低。橢圓弦箭累加算法就是利用這種特性，來實現(xiàn)人臉區(qū)域位置的 估計 。 通過 弦箭算法 計算人臉大概位置區(qū)域主要分為 三步：圖像預(yù)處理、弦箭算 法 、確定人臉區(qū)域大概位置 。 一、圖像預(yù)處理 為減少運算量，對較大的源圖像可進行間隔采樣， 并對 采樣后的圖像進行高斯濾波。 （ 1） 采用 canny 算子提取濾波后的邊緣。 （ 2） 割斷分叉邊緣點，使所有邊緣線都不分叉。 （ 3） 過濾掉邊緣中長度大于某一閾值的直線，一般使用簡單的鏈碼過濾方法。 （ 4） 去除長度過小的邊緣線。 （ 5）對邊緣線進行編號并獲得坐標點序列 X（ k， num）， Y（ k，num)， k=1， 2， 3?， L（ num），其中 num 為曲線編號， k 為像素序列號， L（ num）為標號為 num 的曲線上的像素點個數(shù)。 二、弦箭算法 邊緣圖在去除直線之后，較大的人臉的邊緣曲線就較難連續(xù)，如果是較小的人臉，則邊緣線就更接近于圓。所以，邊緣上的兩點 連線的垂直中分線就和與垂直中分線相交的邊緣上的點的法線很接近。為了運算簡單，用橢圓弦線的垂直中分線來近似代替橢圓的法線。垂直中分線以弦線中點為起始點，方向指向曲線內(nèi)部延伸，如圖 23 所示，形同弓箭。下文稱垂直中分線為箭，弦線中心點為箭尾 ，另一端為箭頭，算法簡稱弦箭法。以圖 23 為例弦箭算法描述如下： 圖 23弦箭算法舉例（ A向 B） （ 1）建立三維數(shù)組表 A（ i， j， k）， i=1～ m， j=1～ n， k=1， 2；并 初 始化為零。其中 A（ i， j， 1） 中保存累加和， A（ i， j， 2） 中保存最大 距離 。 （ 2）對各邊緣曲線依次使用弦箭法，每個曲線包括正反 ①和②兩個移動過程： ① 正向過程：假設(shè)如圖 23 所示的任意一橢圓曲線 AB，先任意固定弦的一端如 A 點，弦的另一端隨曲線移動，每移動一次稱為一次“跨步”?！翱绮健钡拈L度以弧長計算（像素點個數(shù)近似代替），箭長為 每次弦所跨過的曲線弧長的 τ 倍。如圖 23 所示，每個過程包含若干“跨步”： 第 1 跨步：設(shè)最小跨步弧長為 Δ S，如果 Δ S 小于曲線弧長 L，則“跨步”到弧長為 Δ S 的點 t1，否則算法中止。在 A（ i， j， k）的對應(yīng)坐標位置上“繪制”長度為 τ Δ S 個像素的垂直中分線，此即箭 a1。圖 23 中的箭頭只是為了表示垂直中心線“繪制”方向，方向指向曲線的內(nèi)部，方向判斷 在此 不做詳述?！袄L制”的含義包含（ a）、（ b）兩個方面： （ a）在箭 a1，即在垂直中分線對應(yīng) 的 累加數(shù)組 A（ i， j， k）的位置上如式（ 26）做累加： )62(1)1,()1,( ??? jiAjiA （ b）累加的同時，做如下作，其中 Dis 為當(dāng)前位置到箭尾的距離： If DisA(i,j,2) then 將此距離填入距離表中： A（ i， j， 2） =Dis。 else 進入箭的下一個點； end 以下各跨步和第 1 跨步相似，為敘述方便，設(shè) |Ati|為 A 到 ti的距離。 第 2 跨步：如果 2Δ SL,且 |At2||At1|，則跨到 2Δ S 弧長的點t2，“繪制”箭 a2，箭長 2τ Δ S。否則，結(jié)束正向過程。 第 3 跨步：如果 3Δ SL，且 |At3||At2|， 則跨到 3Δ S 弧長的點 t3，“繪制” 箭 ，箭長 3τ Δ S。否則，結(jié)束正向過程。 第 n 跨步：如果 nΔ SL，且 |Atn||At(n1)|， 則跨到弧長為 nΔ S 的 tn 的位置，“繪制”箭，箭長 nτ Δ S。否則，結(jié)束正向過程。圖 23 中由于 |Atn||At(n1)|，所以不“繪制” an，結(jié)束正向過程。 ② 反向過程：固定 B 點，向 A 點的方向“跨步”，方法同正向過程。當(dāng)反向過程停止時，則該曲線的弦箭算法結(jié)束，進入下一條曲線。當(dāng)所有的曲線的弦箭算法結(jié)束后則開始確定 人臉區(qū)域大概位置 。 在上述弦箭法的正反過程中，有如下特殊情況需要處理： （ 1）當(dāng)弦與所跨曲線近 似重合，相差小于某個閾值時，該箭不做累加，如圖 24 中的 a1。 （ 2）從 A 向 B“跨步”，當(dāng)弦與邊緣曲線有交點時，如圖 24(a)，則將固定點移到交點 c 處，重新向 B 點方向進行“跨步”，直到剩下的曲線 CB 的弦箭算法結(jié)束為止。從 B 向 A 時方法相同。直到曲線 AB的兩個方向的過程進行完為止。 （ 3）當(dāng)箭的角度較大，近似 90 度時；或較小，近似 0 度時，由于累加數(shù)組的分辨率，導(dǎo)致出現(xiàn)類似圖 24(b)左邊直線累加位置的間斷。如圖 24(b)箭頭右邊所示將直線填滿，保證所有箭在累加數(shù)組中的連續(xù)性。 圖 24弦箭法特殊情況處 理 三、確定人臉區(qū)域大概位置 首先，求 A（ i， j， 1）數(shù)組中的最大值所在的位置（ Xmax， Ymax）。然后在數(shù)組 A（ i， j， 2）內(nèi)以 （ Xmax， Ymax） 坐標為中心，寬度為2a 的正方形區(qū)域內(nèi)求 A（ i， j， 2）的最大值 Dmax。確定以 （ Xmax，Ymax） 為中心以寬度為 2Dmax 的正方形區(qū)域作為 人臉位置的大概區(qū)域 ： =∪ {A(i,j,1)= α ,|iXmax|Dmax,|jYmax|Dmax}。根據(jù)能夠射向累加和最大值區(qū)域中的最長的箭，其所屬曲線也必然最長，最靠近外部，接近于頭像外部輪廓的可能性也最大 。所以采上述矩形框?qū)⑷搜?、嘴覆蓋在內(nèi)的可能性也最大，同時也可最大程度地縮小搜索空間。 其中α可根據(jù)圖像大小和精度要求來確定；當(dāng)圖像較小定位精度要求高時，取α =0。 第三章 弦箭算法的 編程 實現(xiàn) 1 BMP 圖像文件格式 數(shù)字圖像有多種存儲格式，本文編程主要針對復(fù)雜背景下的二值灰度圖像，對于其他格式的圖像文件，可以通過多種工具很方便的 轉(zhuǎn)化為灰度圖像 ， 下面首先介紹 BMP 圖像文件格式。 BMP（ BitMap Picture）文件格式是 Windows 系統(tǒng)交換圖形、圖像數(shù)據(jù)的一種標準格式。 BMP 圖像的數(shù)據(jù)由四部分組成： 位圖文件頭、位圖信息頭、調(diào)色板、位圖數(shù)據(jù)。 第一部分為位圖文件頭 BITMAPFILEHEADER，它是一個結(jié)構(gòu)體，其定義如下： typedef struct tagBITMAPFILEHEADER{ WORD bfType。//文件類型，必須是 0x424D，即字符串“ BM” DWORD bfSize。 //指定文件大小，包括這 14 個字節(jié) WORD bfReserved1。 //保留字 WORD bfReserved2。 //保留字 DWORD bfOffbits。 //從文件頭到實 際位圖數(shù)據(jù) 的 偏移字節(jié)數(shù) }BITMAPFILEHEADER； 這個結(jié)構(gòu)的長度是固定的，為 14 個字節(jié)（ WORD 為無符號 16 位二進制整數(shù)， DWORD 為無符號 32 位二進制整數(shù)）。 第二部分為位圖信息頭 BITMAPINFOHEADER，也是一個結(jié)構(gòu) 體 ，其定義如下： typedef struct tagBITMAPINFOHEADER{ DWORD biSize。 //該結(jié)構(gòu)的長度，為 40 LONG biWidth。 //圖像的寬度，單位是像素 LONG biHeight。 //圖像的高度，單位 是像素 WORD biPlanes。 //位平面數(shù)，必須是 1 WORD biBitCount。 //指定顏色位數(shù)， 1 為二值， 4 為 16 色//8 為 256 色， 1 2 32 位真彩色 DWORD biCompression。 //指定是否壓縮 DWORD biSizeImage。 //實際的位圖數(shù)據(jù)占用的字節(jié)數(shù) LONG biXPelsPerMeter。 //目標設(shè)備水平分辨率 LONG biYPelsPerMeter。 //目標設(shè)備垂直分辨率 DWORD biClrUsed。 //實際實用的顏色數(shù)，若該值為 0，則使//用的顏色數(shù)為 2 的 biBitCount 次方種 DWORD biClrImportant。 //圖像中重要的顏色數(shù)，若該值 //為 0 則所有顏色都是重要的 }BITMAPINFOHEADER； 這個結(jié)構(gòu)的長度是固定的，為 40 個字節(jié)（ LONG 為 32 為二進制整數(shù)）。其中， biCompression 的有效值為 BI_RGB、 BI_RLE BI_RLEBI_BITFIELDS,這都是一些 Windows定義好的常量。由于 RLE4和 RLE8的壓縮格式用的不多 ，一般 biCompression 的有效值為 BI_RGB，幾步壓縮的情況。 第三部分為調(diào)色板（ Palette），這里是對那些需要調(diào)色板的位 圖文件而言的。真彩色圖像是不需要調(diào)色板的， BITMAPINFOHEADER后直接是位圖數(shù)據(jù)。調(diào)色板實際上是一個數(shù)組，共有 biClrUsed 個元素（若該值為零，則有 2 的 biBitCount 次方個元素）。數(shù)組中每個元素類型是一個 RGBQUAD 結(jié)構(gòu)，占 4 個字節(jié)，其定義如下： typedef struct tagRGBQUAD{ BYTE rgbBlue； //該顏色的藍色分量 BYTE rgbGreen//該顏色的綠色分量 BYTE rgbRed； //該顏色的紅色分量 BYTE rgbReserved； //保留值 }RGBQUAD； 第四部分就是實際的圖像數(shù)據(jù)。對于用到調(diào)色板的位圖，圖像數(shù)據(jù)就是該像素顏色在調(diào)色板中的索引值，對于真彩色圖像，圖像數(shù)據(jù)就是實際的 R、 G、 B 值。下面就 2 色、 16 色、 256 色和真彩色位圖分別介紹。 對于 2 色位圖，用 1 位就可以表示該像素的顏色（一般 0 表示黑， 1 表示白），所以一個字節(jié)可以表示 8 個像素。 對于 16 色位圖，用 4 位就可以表示該像素