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