基于信息熵的自適應高斯金字塔的LSD算法改進

王冬梅, 謝 鑫

(東北石油大學 電氣信息工程學院, 黑龍江 大慶 163318)

0 引 言

線段作為圖像的低階特征, 常用于分析圖像。算法檢測出的線段需要保留原圖像中物體完整的輪廓信息, 又需要拋棄沒有利用價值的背景。圍繞該問題, 近年來人們提出了眾多線段檢測算法。主流線段檢測算法有基于像素梯度幅值的算法和基于像素梯度角度的算法。

Akinlar等[1]提出了EDLines(Real-time Line Segment Detector)算法, 這是一種基于像素梯度幅值的算法, 他能快速檢測一張圖像中的線段信息, 并能實現(xiàn)實時給出結(jié)果, 適合應用于實時系統(tǒng)。然而由于EDLines算法本身檢測線段的機制, 導致其在檢測較長的連續(xù)邊緣或交叉邊緣時容易出現(xiàn)不連續(xù)的問題。Gioi等[2]提出了LSD(Line Segment Detector)算法, 該算法在聚類類似梯度角度的像素點時, 由于僅通過一個像素點的八連通區(qū)域判斷周圍是否有類似梯度角度的像素點, 容易產(chǎn)生不連續(xù)的線段。這種線段不連續(xù)的問題在分辨率高的圖像或受到噪聲干擾的圖像中表現(xiàn)的更加明顯。為解決LSD算法在提取線段時容易產(chǎn)生線段不連續(xù)的問題, 郭克友等[3]提出了一種LSD改進算法, 該算法首先采用LDA(Linear Discriminant Analysis)對道路圖像進行有針對性的灰度化； 其次再用LSD算法檢測灰度圖像中的直線部分。劉璧鉞等[4]提出了一種LSD改進算法, 解決原LSD算法在檢測被遮擋或局部模糊的邊緣時, 將原本連續(xù)的邊緣分割成多條短線的問題, 但效果并不理想。

針對原LSD算法在對圖像提取線段時常常出現(xiàn)線段不連續(xù)的問題, 筆者提出一種LSD改進算法。該算法首先通過計算處理后的圖像與原圖之間的互信息熵, 確定高斯金字塔的層數(shù)與層內(nèi)圖像數(shù)量； 其次使用改進的大津閾值, 根據(jù)圖像的梯度峰值將圖像分割成不同區(qū)域并計算相應梯度閾值, 分離出圖像背景； 最后根據(jù)梯度角度尋找線段, 并通過赫爾姆霍茲準則驗證線段。

通過一組具有代表性的圖像, 與比較流行的Hough變換(Hough Transform)[5]、 PPHT(Progressive Probabilistic Hough Transform)[6]、 LSWMS(Line Segment detection using Weighted Mean Shift)[7]、 LSD、 EDLines算法進行了比較, 用結(jié)果圖像進行定性分析, 并且用線段數(shù)量、 總長度及平均長度定量分析各個算法的性能。最后進行抗噪聲實驗。

1 核心算法

1.1 LSD算法原理

LSD算法[1]是一種基于梯度角度的算法。該算法首先將輸入圖像轉(zhuǎn)換為灰度圖并求取像素的梯度幅值, 對像素梯度幅值進行從大到小排序； 其次由于梯度幅值相對較大的像素點周圍更可能出現(xiàn)邊緣, 因此以梯度幅值相對較大的像素點作為種子點, 聚類類似梯度角度的像素點形成線段區(qū)域； 再次通過計算能包括整個線段區(qū)域的最小矩形, 確定線段的位置、 長度和角度等信息； 最終該算法采用赫爾姆霍茲準則驗證線段是否存在于實際圖像中。

1.2 一種基于信息熵的自適應高斯金字塔算法

高斯金字塔實現(xiàn)在不同的尺度對同一個物體觀察, 挖掘同一物體在不同尺度下的圖像信息, 使算法提取出的信息更加完整[8-9]?，F(xiàn)有多數(shù)文章報道的高斯金字塔的層數(shù)與層內(nèi)圖像數(shù)量均是固定的。在構(gòu)建圖像金字塔過程中, 會對圖像進行降采樣和高斯模糊。若對圖像進行多次降采樣或高斯模糊, 圖像中原本獨立的物體可能會連在一起, 造成圖像失真。若算法對失真圖像進行線段檢測, 最終檢測結(jié)果中必然帶有不正確的線段信息, 已經(jīng)失真的圖像在高斯金字塔中是毫無作用的。高斯金字塔中圖像數(shù)量并不是越多越好, 但高斯金字塔中圖像過少時, 會導致高斯金字塔丟失某個尺度的信息, 最終檢測結(jié)果中可能會丟失重要線段信息。

因此高斯金字塔的組數(shù)與每組組內(nèi)圖像數(shù)量的確定方式顯得尤為重要, 筆者提出基于信息熵的自適應高斯金字塔。歸一化信息熵可以描述兩張圖像之間的相似程度[10], 借助這一特性, 將高斯模糊或降采樣后的圖像與原圖像進行計算歸一化信息熵, 算法將計算結(jié)果與閾值進行比較, 決定是否保留處理后的圖像, 從而構(gòu)建出自適應高斯金字塔。實現(xiàn)根據(jù)輸入圖像的不同而建立不同的高斯金字塔。使算法能適應各種各樣的圖像。

歸一化信息熵的計算公式如下

其中A,B為兩張圖像,H(A)、H(B)為圖像信息熵,H(A,B)為聯(lián)合信息熵,NNMI(A,B)為互信息熵。

算法將閾值ε0,ε1,…,εo和閾值α作為參數(shù)。閾值α決定了自適應高斯金字塔具體構(gòu)建多少組, 閾值ε0,ε1,…,εo分別決定了自適應高斯金字塔對應組組內(nèi)有多少張圖像, 參數(shù)具體設(shè)定方式在實驗中論述。算法對圖像構(gòu)建自適應高斯金字塔的具體步驟如下。

Step1 設(shè)定變量o為自適應高斯金字塔的組序號, 變量i為自適應高斯金字塔組內(nèi)圖像序號, 并初始化o、i為0。

Step2 將輸入圖像作為自適應高斯金字塔的第o組第i張圖像, 即金字塔最底層的圖像。

Step3 對自適應高斯金字塔的第o組第i張圖像進行高斯模糊, 并計算模糊后的圖像與輸入圖像之間的歸一化信息熵。判斷歸一化信息熵是否小于閾值εo。若小于閾值, 則i=i+1, 且將模糊后的圖像存入自適應高斯金字塔第o組第i張的位置; 若大于閾值, 則拋棄當前圖像, 并停止構(gòu)建當前組圖像。

Step4 對自適應高斯金字塔中第o組第i張圖像進行降采樣, 計算降采樣后的圖像與輸入圖像之間的歸一化信息熵。判斷歸一化信息熵是否小于閾值α。若小于閾值, 則o=o+1, 且將圖像存入自適應高斯金字塔第o組第i張的位置, 并重復Step3～Step4； 若大于閾值, 則拋棄當前圖像, 并停止構(gòu)建自適應高斯金字塔。

Step5 得到輸入圖像對應的金字塔。

通過計算圖像歸一化互信息熵的方式確定自適應高斯金字塔的組數(shù)以及每組組內(nèi)圖像數(shù)量。自適應高斯金字塔的結(jié)構(gòu)如圖1所示。對輸入圖像, 算法為其構(gòu)建的高斯金字塔中共有o+1組, 并且每組組內(nèi)圖像數(shù)量是不定的, 分別為i0+1,i1+1,i2+1,…,io+1張； 組內(nèi)的圖像是由當前組的前一張圖像高斯模糊得到的； 下一組的第1張圖像是前一組最后一張圖像降采樣得到的。

圖1 自適應高斯金字塔的結(jié)構(gòu)圖

1.3 大津閾值原理

大津閾值是一種圖像分割的算法。該算法首先將圖像灰度化并統(tǒng)計每個灰度級在圖像中出現(xiàn)的個數(shù)； 其次計算每個灰度級在圖像中所占比例； 最后遍歷所有灰度級, 找出能使前景和背景的類間方差最大的灰度級, 即得到該圖像前景和背景的分割閾值[11-15]

g=w0w1(u0-u1)2

(5)

其中w0為前景像素點數(shù)與圖像總像素點數(shù)的比例,u0為前景像素點平均灰度,w1為背景像素點數(shù)與圖像總像素點數(shù)的比例,u1為背景像素點平均灰度。

1.4 一種改進的大津閾值

每張圖像中都包括前景與背景, 背景對前景中物體的輪廓或邊緣并不重要, 并且在背景中可能包含一定的噪聲。因此在對圖像進行線段檢測前, 將前景與背景分離顯得尤為重要。這樣不僅可以避免算法對一些非邊緣像素點進行遍歷, 節(jié)省算法執(zhí)行時間； 也能減少噪聲干擾, 避免算法對線段的錯誤判斷。因為圖像的不同, 所以圖像對應的梯度閾值也應該是不同的。

原大津閾值算法是對整張圖像計算出一個閾值, 通過其值實現(xiàn)對圖像的分割。當圖像中的背景像素值類似時, 原大津閾值算法分割圖像能發(fā)揮出比較好的效果。然而并不是每張圖像的背景像素值都是類似的。大部分圖像中的背景像素值有幾類, 原大津閾值算法就不能很好地將前景與背景分離, 并且很可能將前景部分像素認作是背景像素。

因此筆者提出改進的大津閾值算法： 首先根據(jù)圖像像素梯度幅值, 將圖像分割成若干個局部； 其次計算出每個圖像局部的梯度閾值； 再次通過梯度閾值將前景與背景分離, 拋棄背景像素對應的梯度； 最終實現(xiàn)圖像的前景與背景實現(xiàn)精確分離, 從而抑制背景噪聲的影響。

改進的大津閾值算法的具體步驟如下。

Step1 讀取圖像金字塔中的一張圖像, 并對整張圖像像素求取梯度。

Step2 找出局部梯度峰值的像素點, 將這些像素點的笛卡爾坐標轉(zhuǎn)換為極坐標, 統(tǒng)計出共線的像素點, 通過最小二乘方法擬合線段； 計算出所得線段之間的交點, 通過線段交點即可將圖像分割成若干局部。

Step3 分別對圖像的每個局部計算出一個梯度閾值。

Step4 通過局部的梯度閾值將圖像局部的前景與背景分離, 拋棄背景像素對應的梯度。

Step5 判斷當前讀取的圖像是否為金字塔中的最后一張圖像, 若不是則重復Step1～Step5; 若是則結(jié)束算法。

Step6 得到金字塔中圖像前景像素對應的梯度。

流程圖如圖2所示。

圖2 改進的大津閾值算法的流程圖

2 仿真實驗

筆者實驗操作平臺電腦： 處理器為AMD Ryzen 5 2600X、 內(nèi)存為8 GByte、 操作系統(tǒng)為Windows 10。筆者所提算法(MultiscaleLSD)和做對比的算法均在Visual Studio平臺上用C++實現(xiàn)。

利用YorkUrbanDB(YorkUrban Dataset)數(shù)據(jù)庫[16]中的圖像對算法進行效果比較和抗噪聲實驗, 實驗涉及的算法有： Hough變換(Hough Transform)、 PPHT、 LSWMS、 LSD、 EDLines。其中Hough、 PPHT算法從Opencv 2.4.11軟件庫中調(diào)用, LSWMS、 LSD、 EDLines算法由筆者提供。

2.1 算法參數(shù)

該算法繼承了原LSD算法無參輸入的優(yōu)點, 因此閾值的設(shè)定應根據(jù)輸入圖像的不同而不同。參數(shù)的設(shè)定如下： 閾值α設(shè)定為自適應高斯金字塔第0組第0張圖像與第1組第0張圖像之間歸一化信息熵的x倍； 閾值ε0,ε1,…,εo分別設(shè)定為對應組的第0張圖像與高斯金字塔第0組第0張圖像之間歸一化信息熵的y倍, 具體x和y值的大小通過實驗確定。

實驗結(jié)果如圖3所示, 圖3a和圖3e分別用于確定y值和x值的實驗輸入圖像； 在還沒有確定x值的情況下, 暫且將x設(shè)定為0.8, 在同一輸入圖像的條件下, 將y值分別設(shè)定為0.5,0.7,0.9, 其檢測結(jié)果分別如圖3b、 圖3c、 圖3d所示, 3幅圖中差異較大的部分用圓角矩形圈出。圖3d相對于圖3c, 在墻壁邊緣處檢測出的細節(jié)更少。這是由于將y值設(shè)定過大后, 導致輸入圖像對應的高斯金字塔組內(nèi)圖像數(shù)量過少, 算法無法將圖像中的線段信息完整檢測出, 使檢測結(jié)果丟失部分線段信息。圖3b相對于圖3c, 雖然在墻壁邊緣處檢測出的細節(jié)差不多, 但在地面和樹木的位置中出現(xiàn)了更多的短線段, 這些短線段是多余的。這是由于將y值設(shè)定過小后, 導致輸入圖像對應的高斯金字塔組內(nèi)圖像數(shù)量過多, 算法將圖像中一些不重要的細節(jié)也檢測出來。根據(jù)以上分析, 為了使算法能盡可能地檢測出圖像中重要的線段信息, 并且忽略掉圖像中背景, 因此該算法將y值設(shè)定為0.7。

在確定y值后, 在同一輸入圖像的條件下, 將x值分別設(shè)定為0.4、0.6、0.8, 其檢測結(jié)果分別如圖3f、 圖3g、 圖3h所示, 3幅圖中差異較大的部分用圓角矩形圈出。圖3h相對于圖3g, 窗戶的輪廓細節(jié)更少, 這是由于在對輸入圖像建立的圖金字塔組數(shù)太少, 導致算法無法將圖像中物體的輪廓信息完整檢測出。圖3f相對于圖3g, 雖然窗戶的輪廓細節(jié)差不多, 但在建筑墻壁上檢測出了更多的短線段, 這些線段信息在實際利用中并不能發(fā)揮作用。這是由于在對輸入圖像建立的圖金字塔組數(shù)太多, 有些組內(nèi)圖像和輸入圖像相比出現(xiàn)失真, 導致檢測出較多短線段。根據(jù)以上分析, 因此該算法將x值設(shè)定為0.6。

圖3 參數(shù)選定實驗結(jié)果

綜上所述： 閾值α設(shè)定為自適應高斯金字塔第0組第0張圖像與第1組第0張圖像之間歸一化信息熵的0.6倍； 閾值ε0,ε1,…,εo分別設(shè)定為對應組的第0張圖像與高斯金字塔第0組第0張圖像之間歸一化信息熵的0.7倍。該參數(shù)設(shè)置能充分發(fā)揮高斯金字塔的優(yōu)點, 并且算法運行前所設(shè)定的參數(shù)對任何圖像都適用。

2.2 算法測評

為檢驗各算法線段檢測的效果, 將用各個算法的輸出圖像進行定性分析, 設(shè)定算法對輸入圖像檢測出的線段總數(shù)量為N、 總長度為L、 平均長度為L/N。用線段數(shù)量、 總長度及平均長度定量分析各個算法的性能。最后將筆者所提算法進行抗噪聲實驗。

教室線段檢測結(jié)果如圖4所示, 其中圖4a為輸入圖像, 圖4b是人工標定圖像。圖4c中邊緣不連續(xù), 算法效果差, 例如： 桌子、 椅子和窗戶。圖4d中丟失大量座椅邊緣信息。圖4e雖然比圖4c、 圖4d有進步, 但與圖4f相比, 還有很多細節(jié)描述不夠完整, 并帶有一些錯誤線段。圖4f相對于圖4e座椅細節(jié)信息更加完整, 但有些邊緣信息不夠完整, 例如： 黑板的下邊緣。圖4g中的物體輪廓大部分都有, 但少了很多物體細節(jié)信息, 例如： 椅子和天花板紋路。圖4h是筆者所提算法檢測結(jié)果, 將圖4h與圖4g比較, 不難發(fā)現(xiàn)圖4h檢測出的細節(jié)比較完整, 與其它算法檢測結(jié)果相比, 圖4h檢測出的線段更加連續(xù)。

圖4 教室線段檢測結(jié)果

表1為圖4所對應的表格。從表1可看出, Hough算法檢測出的線段數(shù)量最多, 線段總長度不大, 且平均長度最小。PPHT算法檢測出的線段數(shù)量最少, 并且其中一些線段為錯誤線段, 使線段平均長度最大。LSWMS算法檢測出的線段數(shù)量相對于Hough變換算法、 PPHT算法更多, 但相對于LSD、 EDLines、 MultiscaleLSD算法還是太少。LSD、 EDLines兩個算法的線段總長度和線段平均長度差不多, 但Edlines的線段數(shù)量更多一些, 這是因為EDLines算法在檢測時將一些在輸入圖像中連續(xù)邊緣當作不連續(xù)導致的。MultiscaleLSD算法檢測出的線段數(shù)量和線段總長度是所有算法結(jié)果最多的, 線段平均長度和LSD、 EDLines算法結(jié)果相差不多。

表1 教室線段信息

大廳線段檢測結(jié)果如圖5所示, 其中圖5a為輸入圖像, 圖5b是人工標定圖像。圖5c中有較多錯誤線段, 且很多邊緣檢測不完整, 例如： 玻璃護欄邊緣和窗戶。圖5d與圖5b對比, 有些線段位置有所偏離, 有些線段的長度長于人工標定圖像中線段的長度。圖5e雖然比圖5c、 圖5d有進步, 但有些線段沒有檢測出來, 例如： 圖像中的門框。圖5f中有很多物體的線段細節(jié), 但有些細節(jié)不夠完整、 連續(xù), 例如： 左側(cè)的柱子、 地板的紋路。圖5g中物體輪廓比較完整, 但少了很多物體細節(jié), 例如： 窗戶、 地板的紋路。圖5h是筆者所提算法檢測結(jié)果, 相對于其他算法, 細節(jié)都更加完整, 例如圖像左側(cè)的柱子、 門框。

表2為圖5所對應的表格。從表2可看出, Hough算法檢測出的線段數(shù)量最多, 但線段總長度不大, 且檢測結(jié)果中出現(xiàn)較多錯誤線段, 線段平均長度最小。PPHT算法檢測出的線段數(shù)量最少, 但線段平均長度最大, 這是因為有些線段的長度要長于標定圖像中線段的長度。LSWMS算法檢測出的線段數(shù)量相對于Hough變換算法、 PPHT算法更多, 但相對于LSD、 EDLines、 MultiscaleLSD還是太少。EDLines算法檢測出的線段數(shù)量、 總長度均要大于LSD算法的檢測結(jié)果, 但線段平均長度要略小于LSD的數(shù)值, 這是因為EDLines算法在檢測時將一些在輸入圖像中連續(xù)邊緣當作成不連續(xù)導致的。MultiscaleLSD算法檢測出的線段數(shù)量、 總長度和平均長度是所有算法中最好的。

圖5 大廳線段檢測結(jié)果

表2 大廳線段信息

2.3 抗噪聲實驗

在通常情況下圖像受到外界干擾或許會帶有一些噪聲, 算法在處理這種圖像時不能完整檢測出圖像中的線段信息。為對比不同算法的抗噪聲性能, 通過對圖像引入一定高斯噪聲, 測試在有噪聲干擾的情況下算法提取線段的效果。

走廊線段檢測結(jié)果如圖6所示, 圖6a為輸入圖像, 不帶有噪聲, 圖6b是人工標定圖像。圖6c和圖6d檢測出圖像部分線段, 但是不夠完整, 例如： 地板和部分墻體輪廓。圖6eLSWMS圖像檢測出部分地板邊緣, 但是帶有大量錯誤線段。圖6f和圖6g檢測出的線段數(shù)量差不多, 但是不夠完整, 例如： 地板和部分墻體輪廓。圖6h是筆者所提算法檢測結(jié)果, 相對于其他算法, 線段數(shù)量更多, 且更加連續(xù)。

圖6 走廊線段檢測結(jié)果

走廊線段檢測結(jié)果(帶噪聲)如圖7所示, 圖7a為輸入圖像, 帶有高斯噪聲(σ=10), 圖7b是人工標定圖像。圖7c在噪聲干擾情況下, 檢測出的線段是斷斷續(xù)續(xù)的, 且?guī)в休^多錯誤線段。圖7d檢測的有些線段位置有所偏離。圖7e幾乎沒有檢測出較完整的線段, 并帶有一些錯誤線段。圖7f和圖7g在噪聲的干擾下檢測出的線段更少。圖7h是筆者所提算法檢測結(jié)果, 相對于其他算法, 線段信息更加豐富。雖然有些線段是斷斷續(xù)續(xù)的, 但線段依舊描述出了原圖像的邊緣信息。

圖7 走廊線段檢測結(jié)果(帶噪聲)

3 結(jié) 語

針對LSD算法提取線段常常出現(xiàn)線段不連續(xù)的問題, 筆者提出了一種LSD改進算法。經(jīng)過圖像仿真實驗, 驗證了該算法能根據(jù)輸入圖像的不同, 建立不同的高斯金字塔, 能充分利用高斯金字塔攜帶多個尺度的信息； 通過改進的大津閾值算法, 將圖像分割成不同區(qū)域計算對應的梯度閾值, 將圖像的背景和前景進行精確地分離, 減少噪聲干擾, 避免算法對線段的錯誤判斷。該算法即解決了LSD原算法缺點又繼承了LSD原算法優(yōu)點, 使提取出的線段更加連續(xù)、 完整。通過對圖像引入一定噪聲, 與其他算法進行比較, 該算法能在噪聲干擾的情況下, 仍然能穩(wěn)定得到滿意的結(jié)果。