【正文】 弦箭算法的提出是在對(duì)橢圓曲線 特性 分析的基礎(chǔ) 上， 根據(jù)人臉邊緣中的橢圓曲線，來(lái) 快速準(zhǔn)確 地 確定人臉 大概區(qū)域 位置。其原理主要是根據(jù)橢圓曲線的法線簇交點(diǎn)的包絡(luò)線位于橢圓內(nèi)部，從而確定橢圓大概區(qū)域，即人臉 大概 區(qū)域位置 。弦箭算法可以有效提高 當(dāng)前人臉檢測(cè)算法的檢測(cè)速度和檢測(cè)正確率 ，在人臉識(shí)別與跟蹤等領(lǐng)域有著重要的應(yīng)用 。 從橢圓曲線的一般性來(lái)看，弦箭算法還有更加廣泛的應(yīng)用。 弦箭算法主要是利用圖像中人臉的邊緣曲線，快速確定搜索空間。實(shí)際上，任意一幅圖像，其確定的是圖像中類橢圓型形狀 物體的大概區(qū)域位置 。 所以 根據(jù)具體 實(shí)際應(yīng)用 ，通過(guò)對(duì)算法進(jìn)行改進(jìn)，在 此 基礎(chǔ)上結(jié)合其他算法，可 以 有效實(shí)現(xiàn)對(duì)各種橢圓形物體的檢測(cè)。因此橢圓弦箭算法 在計(jì)算機(jī)視覺(jué)技術(shù)，模式識(shí)別等領(lǐng)域 可以 實(shí)現(xiàn)更 加 廣泛的應(yīng)用。 4 本文研究的主要 內(nèi)容和成果 本文的主要 內(nèi)容 是 對(duì) 弦箭算法 的原理 進(jìn)行分析與介紹，并用 C語(yǔ)言進(jìn)行 編程 ， 實(shí)現(xiàn) 應(yīng)用弦箭算法快速估計(jì)出人臉大概區(qū)域位置，以提高后序 人臉 算法的效率 。 弦箭算法是 研究在二維圖像中檢測(cè)正面人臉的快速算法 。 通過(guò)對(duì)橢圓曲線特性的分析，可以知道， 在橢圓上等間隔做法線 ， 當(dāng)橢圓長(zhǎng)短軸長(zhǎng)度相差不大時(shí)， 橢圓法線簇 包絡(luò)線的交點(diǎn)必在橢圓內(nèi)部 ，接近于橢圓中心 。 人臉含有眾多的橢圓邊緣曲線，其凹向大都指向人臉內(nèi)部， 如果對(duì)這些邊緣曲線做法線，進(jìn)行累加投票，其 累加和最大峰值的位置必接近于人臉內(nèi)部 ，而 圖像 背景中邊緣曲線的凹向隨機(jī)性很大， 累加和最大峰值 出現(xiàn)的概率就非常小，從而 可以 確定人臉大概區(qū)域位置。 本文編程所使用的環(huán)境是 Microsoft Visual C++ ，用 C 語(yǔ)言編程實(shí)現(xiàn)弦箭算法。 對(duì)于 讀入的 圖像， 首先進(jìn)行 間隔采樣和 高斯濾波 ， 利用 Canny 算子 對(duì)濾波后的圖像 進(jìn)行 邊緣檢測(cè) ， 得到圖像中的邊緣曲線 。 再通過(guò)相應(yīng)的算法對(duì)圖像進(jìn)行預(yù)處理：割斷分叉的邊緣點(diǎn)，去除邊緣曲線中大于某一閾值的直線和長(zhǎng)度過(guò)短的曲線。進(jìn)而對(duì) 剩下各條曲線依次應(yīng)用弦箭算法，在各點(diǎn)進(jìn)行累加 投票 ，并記錄最大箭長(zhǎng)，根據(jù)累 加和峰值和最大箭長(zhǎng)來(lái)確 定人臉大概區(qū)域位置。 本文 研究弦箭算法的主要目的是快速估計(jì) 出 人臉大概位置區(qū)域，提高當(dāng)前人臉檢測(cè)算法的效率。 本文在一個(gè)現(xiàn)有程序中編程嵌入弦箭算法，實(shí)現(xiàn)了對(duì)于給定一張 256 色的二值灰度圖像，快速估計(jì)出人臉大概位置區(qū)域， 估計(jì)出人臉圖像中眼睛 或 嘴巴所在的區(qū)域。 第二章 弦箭算法的原理 人臉的邊緣可以近似為一些橢圓曲線，如圖 21 所示 的人臉邊緣模型。通過(guò)觀察，人臉邊緣線的共同特點(diǎn)就是：無(wú)論頭發(fā)的邊緣、臉頰的邊緣以及下巴的邊緣 ，其凹向總是指向人臉的內(nèi)部。 通過(guò)對(duì)人臉邊緣曲線及橢圓 特性 的分析，我們提出了橢圓弦箭累加算法，可以快速確定人臉主要特征（人眼和嘴）所在的大致位置和區(qū)域。 圖 21 1 橢圓特性分析 如果在橢圓上等間隔做法線可得圖 22 所示的星形包絡(luò)線?？梢宰C明，當(dāng)橢圓長(zhǎng)短軸長(zhǎng)度相差不大時(shí)，包絡(luò)線的交點(diǎn)必在橢圓內(nèi)部 ，接近于橢圓中心 。 圖 22 分析如下：設(shè)橢圓中心點(diǎn)在原點(diǎn)， a、 b 分別為橢圓長(zhǎng)短軸長(zhǎng)度，則 橢圓參數(shù)方程 可表示 為： ）（為參數(shù) 12s i nc os ???? ?? ???by ax 則橢圓上任意點(diǎn) ( acosθ ,bsinθ )的法線的斜率為 tanθ ，法線簇的方程為： 2)(2 a c o stanb s i ny ）（ ??? ?? x 化簡(jiǎn)得： )32(02s i n2c oss i n ????? ??? bayx 上式左邊對(duì) θ 求導(dǎo)（把 x 和 y看作常數(shù)）可得： )42(0b ) c o s 2(ay s i nc o s ??? ???x 根據(jù)微分幾何原理， 包絡(luò)線的方程應(yīng)同時(shí)滿足式（ 23）和式（ 24），從式（ 23）和式（ 24）中可得包絡(luò)線方程為： )52()2/0(c os2s i n2s i n2c os)(s i n2s i n2c os2c os)(????????????????????????????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ī)性很大，形成累加和最大峰值的概率就很低。橢圓弦箭累加算法 就是 利用這種特性， 來(lái)實(shí)現(xiàn)人臉區(qū)域位置的 估計(jì) 。 通過(guò) 弦箭算法 計(jì)算人臉大概位置區(qū)域主要分為 三步：圖像預(yù)處理、弦箭算 法 、確定人臉區(qū)域大概位置 。 一、圖像預(yù)處理 為減少運(yùn)算量，對(duì)較大的源圖像可進(jìn)行間隔采樣 ， 并對(duì) 采樣后的圖像進(jìn)行高斯濾波。 （ 1） 采用 canny 算子提取濾波后的邊緣。 （ 2） 割斷分叉邊緣點(diǎn)，使所有邊緣線都不分叉。 （ 3） 過(guò)濾掉邊緣中長(zhǎng)度大于某一閾值的直線，一般使用簡(jiǎn)單的鏈碼過(guò)濾方法。 （ 4） 去除長(zhǎng)度過(guò)小的邊 緣線。 （ 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)單，用橢圓弦線的垂直中分線來(lái)近似代替橢圓的法線。垂直中分線以弦線中點(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)過(guò)程： ① 正向過(guò)程：假設(shè)如圖 23 所示的任意一橢圓曲線 AB，先任意固定弦的一端如 A 點(diǎn)，弦的另一端隨曲線移動(dòng)，每移動(dòng)一次稱為一次“跨步”?！?跨步”的長(zhǎng)度以弧長(zhǎng)計(jì)算（像素點(diǎn)個(gè)數(shù)近似代替），箭長(zhǎng)為每次弦所跨過(guò)的曲線弧長(zhǎng)的 τ 倍。如圖 23 所示，每個(gè)過(guò)程包含若干“跨步”： 第 1 跨步：設(shè)最小跨步弧長(zhǎng)為 Δ S，如果 Δ S 小于曲線弧長(zhǎng) L，則“跨步”到弧長(zhǎng)為 Δ S 的點(diǎn) t1，否則算法中止。在 A（ i， j， k）的對(duì)應(yīng)坐標(biāo)位置上“繪制”長(zhǎng)度為 τ Δ 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弧長(zhǎng)的點(diǎn)t2，“繪制”箭 a2，箭長(zhǎng) 2τ Δ S。否則，結(jié)束正向過(guò)程。 第 3 跨步：如果 3Δ SL，且 |At3||At2|， 則跨到 3Δ S 弧長(zhǎng)的點(diǎn) t3，“繪制”箭 ，箭長(zhǎng) 3τ Δ S。否則，結(jié)束正向過(guò)程。 第 n跨步：如果 nΔ SL，且 |Atn||At(n1)|， 則跨到弧長(zhǎng)為 nΔ S的 tn 的位置，“繪制”箭，箭長(zhǎng) nτ Δ S。否則，結(jié)束正向過(guò)程。圖 23中由于 |Atn||At(n1)|，所以不“繪制” an，結(jié)束正向過(guò)程。 ② 反向過(guò)程：固定 B點(diǎn)，向 A點(diǎn)的方向“跨步”，方法同正向過(guò)程。當(dāng)反向過(guò)程停止時(shí)，則該曲線的弦箭算法結(jié)束，進(jìn)入下一條曲線。當(dāng)所有的曲線的弦箭算法結(jié)束后則開(kāi)始確定 人臉區(qū)域大概位置 。 在上述弦箭法的正反過(guò)程 中，有如下特殊情況需要處理： （ 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è)方向的過(guò)程進(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ū)域中的最長(zhǎng)的箭，其所屬曲線也必 然最長(zhǎng)，最靠近外部，接近于頭像外部輪廓的可能性也最大。所以采 上述矩形框?qū)⑷搜?、嘴覆蓋在內(nèi)的可能性也最大，同時(shí)也可最大程度地縮小搜索空間。 其中α可根據(jù)圖像大小和精度要求來(lái)確定；當(dāng)圖像較小定位精度要求高時(shí)，取α =0。 第三章 弦箭算法的 編程 實(shí)現(xiàn) 1 BMP 圖像文件格式 數(shù)字圖像有多種存儲(chǔ)格式，本文編程主要針對(duì)復(fù)雜背景下的二值灰度圖像，對(duì)于其他格式的圖像文件，可以通過(guò)多種工具很方便的 轉(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)的長(zhǎng)度是固定的，為 14 個(gè)字節(jié)（ WORD為無(wú)符號(hào) 16位二進(jìn)制整數(shù)， DWORD為無(wú)符號(hào) 32位二進(jìn)制整數(shù)）。 第二部分為位圖信息頭 BITMAPINFOHEADER，也是一個(gè)結(jié)構(gòu) 體 ，其定義如下： typedef struct tagBITMAPINFOHEADER{ DWORD biSize。 //該結(jié)構(gòu)的長(zhǎng)度，為 40 LONG biWidth。 //圖像的寬度，單位是像素 LON