視頻幀／圖像中圖標識別算法
2008-12-31 00:00:00郭戈平西建
計算機應用研究 2008年12期
(解放軍信息工程大學， 鄭州 450002)
摘 要：
針對圖像/視頻中提取的圖標圖像，提出一種基于距離變換的識別和檢索算法。為減少顏色畸變帶來的影響，先將圖像轉換為二值圖標圖像進行后續處理。二值圖像可以通過像素點的不同空間位置分布來表現，據此提出一種基于像素點位置信息的識別檢索算法，其基本思想是首先對灰度圖像進行大小歸一化，然后二值化得到二值圖標圖像；主軸旋轉后利用基于形態學極限腐蝕的距離變換將二值圖像中像素點的位置信息轉換為不同的灰度信息，通過比較其直方圖特征實現對圖標的識別。實驗結果表明該算法速度快、識別率高，并且具有很好的平移、尺度和旋轉不變性。
關鍵詞：數學形態學； 距離變換； 距離圖； 極限腐蝕； 圖標圖像識別
中圖分類號：TN919.8 文獻標志碼： A
文章編號：10013695(2008)12369202
Image/video logo recognition based on distance transform
GUO Ge， PING Xijian
(PLA Information Engineering University， Zhengzhou 450002， China)
Abstract:
This paper proposed a new recognition and retrieval algorithm based on distance transform for logo in image and video. In order to reduce the influence brought by color， the logo region firstly transformed into binary image. Then introduced an efficient logo image recognition method based on location information of pixel. Unitied the graylevel logo image， and followed binarization. Then rotated it on a main direction， applied distance transform to translate the location information into gray level information. By comparing the histogram feature， logos were coarsely recognized. The experiments halyd done in a database including 1 000 binary logo images. Experiment results show that the algorithm possesses high processing speed and recognition accuracy， and it has very excellent performance under translation， scale and rotation.
Key words：mathematic morphologic; distance transform; distance map; ultimate erosion; logo image recognition
圖像/視頻中的圖標具有重要的語義信息，圖標的正確識別對基于內容的圖像/視頻信息檢索技術有很大的幫助。因為一方面，圖標圖像能夠反映圖像/視頻數據的來源；另一方面圖標較大并且變形少，相對于文字信息數目較少。對圖標圖像的識別技術研究在許多應用領域得到了迅速發展，目前國內外已有不少關于圖像/視頻中圖標圖像識別的文章[1]。Jain等人[2]提出分別利用邊界方向與Hu不變矩組以及變形模板匹配的方法進行識別；郭麗等人[3]提出的區域方向直方圖方法則是通過統計圖標中像素點在距離區域的分布情況來獲得形狀特征進行識別；另外還有將傅里葉描述子、Zernike矩和偽Zernike矩等圖像特征應用于圖標圖像的識別和檢索。
縱觀現有的圖標圖像識別算法，難點主要在于兩個方面：
a) 現有的方法大都是基于圖像形狀特征的，不管是整體還是局部的，往往忽略了像素點的位置信息。但是圖標圖像屬于人工圖像， 很多圖標是由幾個邊界分明的幾何圖像組合而成，若組合部分出現在不同的位置上則其表現出來的圖標則完全不同。
b）從圖像或視頻中分割出來的圖標由于受光照、閃光燈等的影響，其顏色特征會有很大程度的畸變。若直接對灰度圖像進行處理會出現誤識別，而二值化后得到的二值圖像所包含的可用信息又很少。
針對上述問題，本算法首先將圖像/視頻中提取出的圖標圖像轉換為二值圖像以去除顏色畸變對識別精度的影響；然后對二值圖標提出一種基于圖像內部像素點位置信息的識別算法。該算法利用基于形態學極限腐蝕的距離變換將圖像中像素點的位置信息轉換為不同的灰度信息，從而使二值圖像具有了灰度特征，通過比較其直方圖特征實現對圖標的識別。
1 基于距離變換的圖標圖像檢測算法
11 灰度歸一化
假設提取出的圖標圖像已經轉換為灰度圖像，歸一化前本文采用反梯度平均濾波法[4]去除掃描或數字化過程中帶來的噪聲。該算法在有效去除噪聲的同時，目標邊緣信息也得到了很好的保持。
由于對二值圖像進行歸一化操作容易造成不平滑、不連貫現象，從而給后續的特征提取帶來不便。本文在灰度域而非二值域對圖標圖像進行歸一化，整個處理過程如下：首先用迭代法[5]進行二值化，將二值化后的圖標圖像分別在水平和垂直方向上投影，即可得到圖標在原圖像中對應的位置；根據該位置信息從原灰度圖像中提取去除背景后的灰度圖標圖像；然后對該灰度圖像進行大小歸一化。
本文采用一種四近鄰插值算法對圖標圖像進行歸一化，歸一化后的簽名圖像高度都為H，設歸一化前簽名圖像f(x，y)的大小為M×N，則歸一化后的點陣F(x′，y′)大小為(MH/N)×H。為了保證直方圖柄數足夠多，本文取H=200像素，映射公式為
x′=(H/N)x，y′=(H/N)y(1)
采用的插值算法如下：設歸一化后的圖像中點(x′，y′)在原圖中對應坐標為(x，y)，對應圖1中的G點；離G最近的四個整數點為A、B、C、D(x，y都不為整數的情況)，它們的灰度值分別為g(A)，g(B)，g(C)，g(D)；E點和F點的灰度值分別為
g(E)=(|BE|×g(A)+|AE|×g(B))/|AB|
g(F)=(|EC|×g(D)+|DF|×g(C))/|DC|
F(x′，y′)=(|EG|×g(F)+|GF|×g(E))/|EF|(2)
若x，y中有一個值為整數，即(x，y)在矩形ABCD的某一條邊上，則F(x′，y′)的值由(x，y)所在邊的兩個端點值決定；若x，y都為整數，則F(x′，y′)=F(x，y)。
12 主方向旋轉
對上述歸一化后的灰度圖像再二值化。設T(x，y)代表二值化后的圖標圖像，則
T(x，y)= 1 if (x，y)為目標像素
0 if (x，y)為背景像素 (3)
為了使提取的圖像特征具有旋轉不變性，可根據圖像的主方向對其進行旋轉。定義圖像相對于主方向的夾角[4]為
=[a tan 2（2μ11，μ20-μ02)]/ 2(4)
其中：μp，q=∑ x ∑ y (x-x0)p(y-y0)qT(x，y)表示圖標區域的p+q階中心矩；x0，y0為T(x，y)的重心坐標。將圖像按照主方向旋轉后，提取所有黑色點的最大外接矩形，稱矩形內的圖像為目標區域，后續的工作均是基于圖像目標區域的操作，從而使得所提取的各種特征具有良好的平移不變性。
圖2是一幅二值化圖標進行主方向旋轉前后的比較。
13 距離變換
數學形態學以圖像的形態特征為研究對象，它的主要內容是設計一整套概念、變換和算法，用來描述圖像的基本特征和基本結構，也就是描述圖像中元素與元素、部分與部分間的關系。對于大部分的二值圖標圖像，它們都是由一些互不連通的幾何形狀構成，因此可以將其看做是由一些具有一定形狀特征的幾何圖形組成的集合體，不同的幾何圖形組合或者相同幾何圖形的不同排列組合表現出來的是完全不同的圖像。對于一幅二值圖像而言，如果將各組成部分像素點不同的位置信息轉換為不同的灰度信息，那么利用個灰度信息就可以將不同的圖像區分開來。定義距離函數如下：
x∈A，dist(x)=min{n∈N:xAΘnB}(5)
由此可知距離圖反映各像素值與目標的接近程度，類似于地理學上的等高線圖。考慮一幅包含目標和背景的二值圖，如將較大的值賦予接近目標的像素(與距離成正比)就可得到一幅距離圖。形態學中，可迭代地腐蝕二值圖，每次操作后，將剩下的像素值加1，從而得到距離圖。極限腐蝕就是用結構元素B反復對圖像進行腐蝕運算，在不斷腐蝕的過程中，不連通的區域不斷產生，同時某些區域又會不斷消失。一個連通成分在消失前的最后一步稱為最終連通成分。跟蹤所有的最終連通成分，用每個最終連通成分的中心點來標志每個連通區域的位置，所有最終連通成分的并稱為相對半徑r的極限腐蝕。圖3是一個極限腐蝕的例子；圖4給出上述主方向旋轉后的圖像（圖2(b)）進行距離變化的結果，極限腐蝕算子結構為圓型，半徑為1。
14 相似性度量
由于圖標圖形作鏡面對稱變換后，投影直方圖會有較大的變化。這里采用求直方圖相關距離的方法來度量歸一化直方圖間的距離，從而判別出兩個圖形的整體相似性。直方圖的相似性是通過距離來度量的，距離越小，則相似度越大。定義投影直方圖的相關距離為
DH(T(o)，T(s))=min(∑ i |h(o)i-h(s)i|，∑ i |h(o)i-h(s)N-1-i|)(6)
其中：0≤i＜N;T(o)為待識別的圖標圖像；T(s)為圖標庫中的圖像；h代表概率直方圖。為了進一步消除尺寸的影響，這里的直方圖計算去除了灰度為0的背景區域。圖像用這種方法求得的距離對于鏡面變換不敏感，能較好地反映圖像之間的相似性。最后取距離最小的那幅圖像為最終識別結果。
2 實驗結果
圖5描述了識別算法的整個處理過程。其中，（a）是從網絡文本圖像中提取到的圖標圖像；（b）是將（a）歸一化到高度為200像素后的結果；再對（b）進行二值化，經主方向旋轉后(圖5c)就可以得到反映圖中像素點位置信息的灰度距離圖（圖5（d））。從距離圖中可以看出，距離邊緣越遠的點越亮，而距離邊緣越近的點則越暗，也就是說，距離圖中像素點的灰度值準確地反映了該像素點的位置信息。
本文中選擇了10個圖標圖像庫進行實驗，其中每個圖像庫包含了150幅圖標圖像作為測試集，在每個數據庫中取60幅作為待識別圖像。表1給出了該算法的識別準確度及識別速率。其中識別速率以s/幅為度量單位，識別準確度為
準確度=正確識別的圖像數/測試集中總的圖像數
從表中可以看出，上述算法具有較好的識別率，出現誤識別的情況主要是因為直方圖不能反映圖像的空間信息。也就是說，完全不同的圖像極有可能具有相同或相似的直方圖特征，在后續的研究中可以進一步選取更有效的相似度度量特征來提高識別準確度。此外，上述算法在識別速度上也基本上取得了令人滿意的效果。
3 結束語
本文針對圖像/視頻中的圖標識別技術進行研究，提出了一種根據像素點的空間位置分布情況實現圖標圖像識別和檢索的算法。該算法主要基于以下幾點考慮：a)用灰度圖標圖像歸一化代替二值圖標圖像歸一化，以改善二值歸一化時造成圖像不平滑、不連貫的現象。b)圖像或者視頻在掃描和數字化過程中因光照和閃光燈的影響，若直接對灰度圖像進行處理，如對灰度直方圖進行比較就會出現較大的誤差，所以算法中應對大小歸一化后的灰度圖像進行二值化后再進行識別。c)二值化后的圖標圖像包含較少的顏色、紋理等信息，黑白像素點不同的空間分布形成不同的圖像，因此本文通過分析像素點的空間分布來實現對圖像的分類和識別。實驗表明，該算法有較高的識別率，并且具有很高的分類識別效率。本算法的缺點是距離變換受所選擇的極限腐蝕結構算子形狀的影響較大。如何選擇受之影響較小的相似性度量標準是下一步需要進行深入研究的問題。
參考文獻：
[1]YAN Jikun， ZHENG Hui， XI Jianmin. Logo recognition in low quality document images[C]//Proc of International Conference on Intelligent Information Technique. Beijing: Posts Telecom Press， 2002:185189.
[2] JAIN A K， VAILAYA A.Shape based retrieval:a case study with trademark image databases[J].Pattern Recognition ， 1998， 31 (9):13601390.
[3] 郭麗，孫興華，黃元元，等.距離分布直方圖及其在商標圖案檢索中的應用[J].中國圖象圖形學報，2005， 7 A(10):10271031.
[4] WANG D C C， VAGNUCCI A H. Gradient inverse weighting smoothing schema and the evaluation of its performance[J].Computer Graphics and Image Processing ， 1981， 15 (2):10541065.
[5] RIDLER T W， CALVARD S. Picture thresholding using an iterative selection method[J].IEEE Trans on System， Man and Cybernetics ， 1978， 8 (8):630632.
