岳英杰 劉 盼 徐榮青

(南京郵電大學(xué)電子與光學(xué)工程學(xué)院 江蘇 南京 210046)

0 引 言

隨著信息服務(wù)的蓬勃發(fā)展，商標(biāo)識別的應(yīng)用越來越廣泛，例如在電子商務(wù)平臺監(jiān)測用戶參與度[1-2]，在日常生活中特定領(lǐng)域的標(biāo)志物識別(例如車輛標(biāo)志[3]和交通標(biāo)志識別[4])。在體育領(lǐng)域，贊助商每年在體育營銷上花費(fèi)數(shù)百萬歐元，俱樂部贊助球隊(duì)，每年要在球隊(duì)上投入一大筆金額。因此贊助商和俱樂部希望以更有效的途徑讓更多的觀眾直接、方便地獲取贊助商和俱樂部的宣傳信息，通過運(yùn)動員商標(biāo)識別來連接到主頁URL是一種新的推介方式，所以從運(yùn)動員穿著的衣物上進(jìn)行商標(biāo)識別是非常有必要的。早些年間，Chattopadhyay等[5]在體育比賽中，實(shí)時(shí)將場地旁邊的廣告牌識別，以完成宣傳贊助商的目標(biāo)。Kim等[6]提出了一種基于文字的實(shí)時(shí)監(jiān)測與識別運(yùn)動場地廣告牌的算法。

進(jìn)行商標(biāo)識別的前提是對商標(biāo)進(jìn)行分割。將商標(biāo)分割的目的是為了分割出無關(guān)背景[7]，只將商標(biāo)作為分類器的訓(xùn)練內(nèi)容，有效地減少了背景等無關(guān)項(xiàng)的干擾，有利于訓(xùn)練準(zhǔn)確性的提升。但是由于運(yùn)動員在球場上劇烈運(yùn)動，這就導(dǎo)致衣服上的商標(biāo)具有旋轉(zhuǎn)、平移、縮放的特性，并且受環(huán)境的影響，例如光照不均勻、圖像背景復(fù)雜、圖片模糊情況的影響，所以傳統(tǒng)圖像分割算法易造成欠分割或者過分割的情況。本文針對上述復(fù)雜情況下的圖片，提出一種Graph Cut與Grab Cut相結(jié)合的改進(jìn)算法，為后續(xù)商標(biāo)識別提供了技術(shù)支持。

1 相關(guān)算法

1.1 Graph Cut

Graph Cut現(xiàn)在已經(jīng)成為解決一類能量最小化問題(例如計(jì)算機(jī)視覺中的圖像分割)的主要選擇方法之一。Graph Cut最初是由Boykov等[8]在解決馬爾可夫隨機(jī)場的能量最小化問題時(shí)提出來的，并且他們還得出了如何使用Graph Cut得到近似最優(yōu)解的方法。

Graph Cut是基于圖論的分割，如圖1所示，黑色的點(diǎn)代表像素點(diǎn)，整幅圖像被重構(gòu)為圖1所示的結(jié)構(gòu)，第一類邊為相鄰像素之間的邊，稱為“n-links”，第二類邊為每個(gè)像素與s和t連成的邊，稱為“t-links”。圖像分割的結(jié)果就是將s與t分開，其中與s相連的為前景像素，與t相連的為背景像素。Graph Cut使能量函數(shù)E(A)最小完成分割。

E(A)=λR(A)+R(B)

(1)

式中：A={A1,A2,…,AP}為每個(gè)像素的標(biāo)簽label，Ai為0(背景)或1(前景)；λ是區(qū)域項(xiàng)和邊界項(xiàng)之間的重要因子，決定它們對能量的影響大??；R(A)為區(qū)域項(xiàng)；R(B)為邊界項(xiàng)。

(2)

(3)

(4)

r,g,b∈[0,255]

圖1 Graph Cut連接圖

圖片重構(gòu)的結(jié)果如圖2所示，可以看出，圖片依照輪廓被分為了很多不同的區(qū)域，其中分割區(qū)域的多少受設(shè)為相似區(qū)域的像素距離閾值影響。

圖2 Graph Cut圖片區(qū)域重構(gòu)

1.2 Grab Cut

Rother等[9]在SIGGRAP 2004中通過將Graph Cut算法迭代，提出了一個(gè)基于Graph Cut迭代的Grab Cut算法。通過構(gòu)造前景中和背景中的兩個(gè)標(biāo)記的能量函數(shù)，將分割問題轉(zhuǎn)化為兩個(gè)標(biāo)記問題。該算法最終可以確定每個(gè)像素是屬于背景還是前景，以便它可以使能量最小化。

Grab Cut算法的步驟如圖3所示。首先，用戶選擇一個(gè)感興趣矩形(ROI)。然后與原始圖像具有相同像素的掩膜圖像被初始化，用來記錄圖像分割的結(jié)果。掩膜圖像的每個(gè)像素點(diǎn)只有四種取值，分別為0(表示明確屬于背景的像素)、1(表示明確屬于前景的像素)、2(表示可能屬于背景的像素)、3(表示可能屬于前景的像素)。然后，利用式(5)-式(7)計(jì)算被稱為邊界能量項(xiàng)像素的n-links，并根據(jù)用戶選擇的感興趣區(qū)域矩形，建立前景和背景的GMM模型。

圖3 Grab Cut算法流程

(5)

(6)

(7)

式中：μ為三通道的高斯分量的均值向量；Σ為3×3的協(xié)方差矩陣。

在算法繼續(xù)往下進(jìn)行之前，緊接著利用K-means聚類算法[10]將組成GMM模型的所有像素點(diǎn)分為k類?；诖司垲惖慕Y(jié)果，GMM模型的參數(shù)θ和t-links也可以被計(jì)算出來。值得注意的是，在使區(qū)域能量也就是t-links最小化過程中，應(yīng)該多次迭代k和θ以滿足最小化。因此，s-t網(wǎng)絡(luò)被建立，并且通過最小割/最大流算法將圖像分割。

在圖4中，(a)是原始圖像，(b)是Grab Cut分割的結(jié)果(GMM模型中的參數(shù)K=500)?？梢钥闯?，Grab Cut的一個(gè)缺點(diǎn)是當(dāng)商標(biāo)與背景顏色相似時(shí)，分割后會出現(xiàn)一些圖像碎片噪聲，也就是我們所說的欠分割情況。這種情況會導(dǎo)致前景提取的不精確，為接下來的商標(biāo)識別增加很多干擾和影響。因此，改進(jìn)此分割算法顯得尤為重要。

(a) 原始圖像(b) Grab Cut分割結(jié)果圖4 Grab Cut分割結(jié)果

2 改進(jìn)的商標(biāo)分割算法

根據(jù)前文的分析，Graph Cut算法在分割圖像時(shí)，算法利用了物體位置和邊緣的信息，當(dāng)一幅圖像中存在很多噪聲時(shí)這種方法是十分有效的。從圖4(b)中我們可以看出，Grab Cut算法存在很多不足，當(dāng)圖片的背景與前景顏色相近時(shí)，這幅圖片很可能被欠分割。并且受到環(huán)境因素、光照等情況的影響，盡管某些部分與目標(biāo)前景明顯不同，但是Grab Cut算法不能很好地分開與前景無關(guān)的背景干擾像素。

所以在進(jìn)行圖像分割之前，有效地進(jìn)行預(yù)處理是接下來工作的根本。因?yàn)镚raph Cut利用了圖片的邊緣信息，所以本文考慮使用銳化處理。銳化處理的目的是為了增強(qiáng)圖片的邊緣，使得目標(biāo)物體的邊緣鮮明，以便于提取目標(biāo)的邊緣，對圖像進(jìn)行分割。本文采用拉普拉斯算子進(jìn)行圖像銳化，它是根據(jù)相鄰像素之間的變化程度來計(jì)算的。一階函數(shù)微分描述的是函數(shù)變化的方向，二階函數(shù)微分描述的是函數(shù)變化的速度，用圖像來解釋就是一階函數(shù)微分能確定圖片的邊緣是否存在，而二階函數(shù)微分能確定圖片邊緣的位置。

考慮到銳化是在Graph Cut算法之前進(jìn)行的，而前文描述的Graph Cut算法在計(jì)算相鄰像素的連通值時(shí)采用的是8連通法。如圖5所示，所謂的八連通法就是在計(jì)算周圍像素到中心像素的影響時(shí)，考慮上、下、左、右、左上、右上、左下、右下一共8個(gè)像素。

圖5 圖片中像素的8連通示意圖

來計(jì)算，得到的銳化圖像g(x)為：

(8)

本文考慮了銳化步驟在增強(qiáng)圖像邊緣的同時(shí)，也會將噪音增強(qiáng)，所以在進(jìn)行銳化處理之前將圖片先進(jìn)行高斯濾波。

另外針對分割不精確，Grab Cut還提供人工修改掩膜的權(quán)利，又多了一次交互過程，本文將修改掩膜的步驟提前進(jìn)行，因?yàn)閳D像分割的實(shí)質(zhì)是迭代使得圖像每個(gè)部分的能量函數(shù)最小化，此時(shí)輸出的最優(yōu)結(jié)果為最佳分割。而在Graph Cut算法中，僅涉及兩類能量，第一類是像素點(diǎn)與圖像區(qū)域不同的能量，稱為點(diǎn)與類的能量；第二類是像素點(diǎn)與像素點(diǎn)之間不同的能量，稱為點(diǎn)與點(diǎn)的能量。兩個(gè)能量之間所占的比例關(guān)系使用Potts模型參數(shù)K來控制比例，當(dāng)點(diǎn)與點(diǎn)的能量所占比例高時(shí)，像素局部平滑約束就越高，圖像就越平滑，圖像分割保留的細(xì)節(jié)就越少。所以利用雙閾值首先將圖片進(jìn)行初步過濾，直接將圖片的某些部分視為前景或背景的部分，再送入Grab Cut進(jìn)行迭代。

根據(jù)上述情況，本文提出的改進(jìn)算法步驟如下：

(2) 對高斯濾波之后的圖像進(jìn)行拉普拉斯算子銳化處理，增強(qiáng)圖像邊緣。

(3) 對整幅圖像使用Graph Cut算法，統(tǒng)計(jì)出每個(gè)像素的標(biāo)簽值。

(4) 用戶進(jìn)行交互，將目標(biāo)前景用矩形框圈出，并統(tǒng)計(jì)矩形框中有多少種標(biāo)簽和屬于該標(biāo)簽有多少數(shù)量的像素。

(5) 計(jì)算矩形框中每種標(biāo)簽的像素占整幅圖像屬于該種標(biāo)簽的像素比例。

(6) 設(shè)置閾值H1和H2，兩個(gè)閾值的設(shè)定根據(jù)特定的圖片應(yīng)用場景，根據(jù)圖片分割的平滑約束度，利用K值來設(shè)定閾值H1和H2：

(9)

(10)

式中：K代表Graph Cut算法設(shè)定的Potts模型參數(shù)；P代表用戶交互后得出的矩形框中像素點(diǎn)的總數(shù)；Connectsize代表像素點(diǎn)與其相鄰8鄰域像素點(diǎn)的連通平均值。

即H1為低閾值，H2為高閾值，比例小于H1，則將矩形框中的屬于該標(biāo)簽的像素視為背景的一部分，若比例大于H1小于H2視為可能的背景，若比例大于H2視為可能的前景。

(7) 根據(jù)判決比例和矩形框中的標(biāo)簽值，生成掩膜圖像。

本研究嚴(yán)格按照Delphi專家咨詢法,構(gòu)建了一套科學(xué)、合理的康復(fù)專科護(hù)士核心能力評價(jià)指標(biāo)體系，包括8個(gè)一級指標(biāo)、21個(gè)二級指標(biāo)和66個(gè)三級指標(biāo)。專家對各個(gè)指標(biāo)的意見具有高度的一致性，可信度高，同時(shí)具有一定的科學(xué)性和權(quán)威性，并且各指標(biāo)的權(quán)重設(shè)置合理，為康復(fù)?？谱o(hù)士培養(yǎng)、資質(zhì)認(rèn)證和能力評價(jià)提供參考依據(jù)。本研究并未對指標(biāo)內(nèi)在品質(zhì)進(jìn)行研究，因此，對康復(fù)?？谱o(hù)士核心能力評價(jià)指標(biāo)的信效度檢驗(yàn)，將是下一步研究的重點(diǎn)內(nèi)容。

(8) 利用生成的掩膜圖像去初始化Grab Cut算法，完成圖像分割。

假設(shè)矩形圖像中N個(gè)標(biāo)簽，每個(gè)標(biāo)簽k=1,2,…,N,每個(gè)標(biāo)簽中像素的數(shù)量是Sk。用戶交互完成后，在矩形框中有i個(gè)標(biāo)簽，屬于這i個(gè)標(biāo)簽的像素為Ri(i=1,2,…,N,i∈K)。通常，用戶交互后的矩形中像素所占所有像素標(biāo)簽的比例定義為：

(11)

Lk的含義是矩形框中的一個(gè)像素屬于背景的可能性。若Lk=1的含義就是屬于該標(biāo)簽的所有像素都處于矩形框中。Lk的值越接近于0，越能說明該像素屬于背景。所以，當(dāng)計(jì)算出的Lk低于設(shè)定的閾值H1和H2，在掩膜中該點(diǎn)的取值由可能的前景變?yōu)榭赡艿谋尘盎虮尘?，從而減少背景像素的干擾。

3 實(shí)驗(yàn)結(jié)果分析

通過實(shí)驗(yàn)我們發(fā)現(xiàn)，閾值的大小會嚴(yán)重影響分割的結(jié)果，不同應(yīng)用場景下閾值不同。針對此應(yīng)用場景，通過式(9)和式(10)計(jì)算得出H1=0.3、H2=0.8。圖6是使用改進(jìn)后的算法分割的結(jié)果?？梢钥闯?，改進(jìn)之后的算法相比較于傳統(tǒng)Grab Cut算法在精度上具有明顯的提升，有效地滿足了欠分割的問題。另外我們從實(shí)驗(yàn)得出，當(dāng)閾值設(shè)置過低時(shí)，改進(jìn)的算法不是很有效。若將閾值H1和H2設(shè)為0，那么改進(jìn)后算法的結(jié)果將與傳統(tǒng)Grab Cut一致，算法改進(jìn)將變得沒有意義。

圖6 改進(jìn)算法分割結(jié)果

另外，Graph Cut初始化設(shè)置分割區(qū)域數(shù)量的多少也會對分割結(jié)果產(chǎn)生重要的影響。而分割區(qū)域的數(shù)量與K值的大小有關(guān)。K值越大，則兩個(gè)像素相隔的距離越近，一幅圖像被分成的區(qū)域越多；反之K值越小，兩個(gè)像素相隔的距離就遠(yuǎn)，一幅圖像被分成的區(qū)域越少。圖7(b)展示了設(shè)置過多的分割區(qū)域數(shù)量，算法的精度將會下降。圖8展示了不同的K值對分割精度的影響，可以看出，K值在一定范圍內(nèi)不會對分割精度產(chǎn)生很大的影響，但是將圖片分割成更細(xì)小的區(qū)域意味著需要更多的時(shí)間，所以在保證大概分割區(qū)域數(shù)量對精度影響很小的情況下，盡量減小K值，使分割區(qū)域盡可能少，這樣分割的速度會有一定程度上的提升。

(a) 原始圖像

(b) K=800

(c) K=600圖7 不同K值對圖像的影響

圖8 K值對算法精度的影響

4 算法評價(jià)

本文從BelgaLogos公開數(shù)據(jù)集中選擇了100幅圖片，并用Photoshop圖像抓取工具分割它們的背景作為完美分割的參考圖像。評價(jià)分割算法最重要的指標(biāo)是精確度，本文使用標(biāo)準(zhǔn)的Jaccard相似度指數(shù)對改進(jìn)算法的精確度進(jìn)行驗(yàn)證。Jaccard相似性指數(shù)是衡量兩個(gè)集合的相似性的指標(biāo)，利用式(12)計(jì)算出每幅圖片的Jaccard相似指數(shù)，再取平均，得到算法的精確度結(jié)果。

(12)

式中：S1和S2指的是兩個(gè)集合，在本文中，S1為改進(jìn)算法的分割結(jié)果圖像，S2為參考圖像。

(13)

式中：i=0,1，…，99代表每幅圖片；Ji(S1,S2)代表每幅圖片的Jaccard指數(shù)。

改進(jìn)算法的分割結(jié)果展示在表1中?？梢钥闯龈倪M(jìn)后的算法對分割精度有了很高的提升，但是精度的提升受到了特定圖片的限制。另外，本文將算法改進(jìn)結(jié)果與Wicaksono等[11]提出的K-means改進(jìn)算法相比較，在精度方面有相對程度上的提高。

表1 算法結(jié)果

同時(shí)，從不同的性能指標(biāo)驗(yàn)證分割方法是非常必要的，本文使用峰值信噪比(PSNR)指標(biāo)來評判分割的性能，一定程度上驗(yàn)證了改進(jìn)算法的說服力。利用式(14)計(jì)算得出的均方誤差MSE，是反映估計(jì)量與被估計(jì)量之間差異程度的一種度量。

(14)

式中：m代表圖像的寬度像素?cái)?shù)量；n代表圖像的長度像素?cái)?shù)量；I代表算法分割之后的圖像；K代表完美分割的參考圖像。PSNR用來檢測圖像的質(zhì)量，利用式(15)計(jì)算得出PSNR值。

(15)

式中：MAXI是表示圖像點(diǎn)顏色的最大數(shù)值。PSNR數(shù)值越大，代表圖像的質(zhì)量越好。如圖9所示，本文分別求得Graph Cut、Grab Cut、k-means分割算法和改進(jìn)的Grab Cut算法的PSNR值，并以柱狀圖的形式展示。

圖9 不同算法的PSNR比較

由圖9可得，本文的改進(jìn)Grab Cut算法具有最大的PSNR值，一定程度上驗(yàn)證了本文算法有一定程度上的性能提升，但是當(dāng)目標(biāo)物體比背景更大的時(shí)候，分割精度更高，因此，不是所有的圖片都能體現(xiàn)出改進(jìn)算法的優(yōu)點(diǎn)。

5 結(jié) 語

本文提出一種基于體育商標(biāo)的改進(jìn)圖像分割算法。實(shí)驗(yàn)結(jié)果展示了該算法的精確度，使用改進(jìn)后的算法能使得商標(biāo)分割準(zhǔn)確率為94%，基本上滿足準(zhǔn)確分割體育商標(biāo)的需要。但是，算法的缺點(diǎn)是增加了運(yùn)行時(shí)間。本文的研究意義在于，發(fā)現(xiàn)了可以利用像素與像素之間的關(guān)系來改進(jìn)Grab Cut的不足之處。

毫無疑義，當(dāng)商標(biāo)圖片背景特別復(fù)雜時(shí)，對分割的精度會造成重大的影響，但是本文通過改進(jìn)Grab Cut算法，使得在復(fù)雜背景下使Grab Cut分割精度有了一定的提升，有效解決欠分割和過分割的問題。