基于積分圖像的灰度分布標準化快速算法

摘要：在積分圖像基礎上提出和應用平方積分圖像，實現了一種計算速度與圖像窗口大小無關的快速灰度均值和方差算法。應用該算法，結合對灰度分布標準化近似計算公式的變換，實現了圖像窗口灰度分布標準化的快速計算。實驗證明，當需要對一幅圖像的大量圖像窗口進行灰度分布標準化時，這種算法對提高計算速度十分有效。

關鍵詞：積分圖像；灰度分布標準化；方差；快速算法

中圖分類號：TP391文獻標志碼：A

文章編號：1001—3695(2007)03—0277—03

在Crow提出Summed-AreaTables算法[1]后，Viola首次將其用于人臉圖像分析，并稱之為積分圖像(IntegralImage)[2]。積分圖像作為圖像的一種中間表示，Viola在Adaboost和Cascade算法實現的實時人臉檢測系統中用它來計算圖像窗口的灰度值總和[2]。此外，也有人用積分圖像計算圖像窗口的灰度均值[3，4]。

在人臉檢測中，對圖像窗口灰度分布標準化的計算量大，因為一方面圖像窗口的數量很多;另一方面灰度分布標準化之前還必須計算這些窗口的灰度均值及方差。利用積分圖像，雖然可以快速計算出圖像窗口的灰度均值，但仍不能直接用來快速計算圖像窗口的灰度方差。在積分圖像基礎上，提出和應用平方積分圖像，能實現一種計算速度與圖像窗口大小無關的快速灰度均值和方差算法，從而大大提高灰度分布標準化的處理速度，再結合對灰度分布標準化公式的變換，則可進一步加快灰度分布標準化。

1積分圖像及平方積分圖像

1.1積分圖像

積分圖像的任意一點(x，y)表示圖1所示的原圖像斜線區域的灰度值總和，即

其中，s(x，y)表示一列的積分，且s(x，-1)=0，ii(-1，y)=0。求積分圖像，只需遍歷一次原圖像，計算開銷很小。圖2所示窗口D的灰度值總和，不管窗口D的大小如何，均可以用積分圖像的相應點1，2，3，4快速計算出來，即窗口D的灰度值總和為4+1-（2+3）。

1.2平方積分圖像

為快速計算圖像窗口的方差，在積分圖像的基礎上提出平方積分圖像的概念。設sii(x，y)為平方積分圖像，i(x′，y′)為原圖像，則

式(4)說明平方積分圖像的任意一點(x，y)代表圖1所示的原圖像中斜線區域的灰度值平方總和，sii(x，y)可用式(5)、(6)迭代計算得到:

其中，ss(x，y)表示一列的平方積分，且ss(x，-1)=0，sii(-1，y)=0。平方積分圖像可與積分圖像在對原圖像的同一次遍歷中算出，計算開銷很小。參照圖2所示的計算方法，運用平方積分圖像可快速算出窗口D的灰度值平方總和，且計算速度與窗口D的大小無關。

2圖像窗口快速灰度分布標準化算法

2.1灰度均值及方差快速計算

式(7)表明，直接計算窗口的灰度均值將需對窗口遍歷一次。因其中項∑y+M-1j=y∑x+N-1i=xR[i][j]表示窗口灰度值的總和，若用積分圖像來計算，將能避免對窗口遍歷，從而提高窗口的灰度均值計算速度。

式(8)則表明，直接求窗口的灰度方差需先計算窗口的灰度均值μR，然后再對窗口遍歷一次才能完成。為避免對窗口遍歷，且使計算窗口的灰度方差不必先計算窗口的灰度均值，式(8)作如下變換:

2.2快速灰度分布標準化

灰度分布標準化是指將圖像窗口的灰度均值和方差變換為事先設定的標準值μ₀和σ²₀。在基于模板的人臉檢測中，灰度分布標準化作為模板匹配前對圖像窗口的預處理步驟，可采用式(10)計算[5—7]，即對圖像窗口中每一個像素的灰度值進行如下變換:

預先計算出a和b，再利用式(11)來對圖像窗口中每一個像素進行灰度分布標準化變換，將可進一步提高灰度分布標準化處理的速度。

以利用“雙眼—人臉模板對”進行正面端正的人臉檢測為例，一般先對圖像窗口使用雙眼模板進行粗篩選，然后用各種寬長比的人臉模板作進一步匹配[5—9]，每個可能是雙眼(或人臉)的窗口在模板匹配前均需進行灰度分布標準化處理，窗口灰度分布標準化處理的快速算法如下:

(1)計算圖像的積分圖像ii(x，y)和平方積分圖像sii(x，y)。

(2)對圖像中可能是雙眼(或人臉)的圖像窗口用ii(x，y)和sii(x，y)計算其灰度均值μ_R和均方差σ_R。

(3)若σ_R=0，則認為圖像窗口不是雙眼(或人臉)，并結束對該窗口的操作；否則從原圖像中剪切該圖像窗口至內存作為雙眼(或人臉)子圖像。

(4)計算式(11)中的變量a和b，然后利用式(11)對剪切得到的雙眼(或人臉)子圖像進行灰度分布標準化。

(5)若圖像中還有可能是雙眼(或人臉)的圖像窗口，則轉（2）；否則結束。

用固定比率不斷重采樣以壓縮原圖像的方法來解決多尺度的人臉檢測問題時，上述算法需要在各壓縮后的圖像中重復進行。

3實驗結果與分析

以文獻[7]正面端正人臉檢測為例，雙眼模板的尺度為24×9，各種人臉模板的寬長比分別為24×21，24×24，24×26，24×28，24×31。模板匹配前的灰度分布標準化將針對這些尺度的圖像窗口來進行。本文的灰度分布標準化快速算法不改變原來直接用公式計算的精度，所以實驗結果只包含計算速度的對比。實驗中使用的計算機為Pentium700MHzCPU，256MB內存，實驗圖像來自CMU人臉檢測庫。

3.1圖像窗口的灰度均值及方差計算速度對比

灰度均值及方差(GrayscaleAverageandVariance，GAV)的計算實驗將三種算法進行對比（表1）。算法GAV1為文獻[7]的直接公式算法，使用式(7)和(8)計算窗口的灰度均值及方差;算法GAV2僅使用積分圖像快速計算窗口的灰度均值，灰度方差計算仍使用式(8);算法GAV3則同時使用積分圖像和平方積分圖像快速計算窗口的灰度均值及方差。

表1灰度均值及方差算法比較

從圖3可知，算法GAV2比算法GAV1的計算速度有較大提高，但兩者的計算速度均與圖像窗口的大小有關，圖像窗口越大，計算速度越慢;算法GAV3則不但計算速度比算法GAV1和算法GAV2快得多，而且與圖像窗口的大小無關。由此可見，當需要對一幅圖像的大量窗口進行灰度均值及方差計算時，采用積分圖像和平方積分圖像對提高計算速度十分有效。

3.2圖像窗口的灰度分布標準化計算速度對比

灰度分布標準化(GrayscaleDistributionNormalization，GDN)的計算需先計算圖像窗口的灰度均值及方差，然后從原圖像中剪切該窗口至內存，并逐個對像素進行灰度分布標準化變換。實驗對三種算法進行了對比(表2)。算法GDN1為文獻[7]的直接公式算法，先使用式(7)和(8)計算窗口的灰度均值及方差，再使用式(10)進行灰度分布標準化;算法GDN2使用算法GAV3快速計算窗口的灰度均值及方差，但灰度分布標準化時使用式(10);算法GDN3則使用算法GAV3快速計算窗口的灰度均值及方差，然后先計算式(11)中的變量a和b，再使用式(11)進行灰度分布標準化。

從圖4可知，算法GDN2比算法GDN1的計算速度有較大提高，這是因為采用積分圖像和平方積分圖像計算窗口的灰度均值及方差，減少了計算開銷;算法GDN3則比算法GDN2的計算速度有進一步的提高，這是因為通過預先計算式(11)中的變量a和b，使計算量減少。但因這三種算法均不可避免地要對子圖像的每一個像素進行灰度值變換，所以它們的計算速度均與圖像窗口的大小有關。圖4表明，圖像窗口越大，計算速度越慢。

4結束語

本文提出了一種基于積分圖像的快速灰度分布標準化算法。首先在積分圖像的基礎上，提出和應用平方積分圖像，實現了一種計算速度與圖像窗口大小無關的快速灰度均值和方差算法。用這種快速算法，結合對灰度分布標準化計算公式的適當變換，最終實現了圖像窗口的快速灰度分布標準化。實驗表明，當需要對一幅圖像的大量圖像窗口進行灰度分布標準化時，這種基于積分圖像的灰度分布標準化快速算法對提高計算速度十分有效，可在人臉檢測、人臉識別及相關領域中廣泛應用。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。