【文献翻译】LSD: A Fast Line Segment Detector with a False Detection Control
前言
博主譯文水平不好，為了學習，所以進行論文翻譯和研究，博文以譯文為主。如果有翻譯不對之處，還請各位指出，便于我修改。文獻信息
引用格式：Gioi R G V, Jakubowicz J, Morel J M, et al. LSD: A Fast Line Segment Detector with a False Detection Control[J]. IEEE Trans Pattern Anal Mach Intell, 2010, 32(4):722-732.所屬級別：CCF A類
發表期刊：TPAMI
發表年份：2010
原文鏈接： LSD: A Fast Line Segment Detector with a False Detection Control
LSD：具有假檢測控制的快速線段檢測器
摘要: 我們提出了一種線性時間線段檢測器，可提供準確的結果，可控數量的錯誤檢測，并且不需要參數調整。 該算法經過測試并與大量自然圖像中的最新算法進行比較。關鍵字： 線段檢測，NFA，亥姆霍茲原理，反向檢測。
引言
?? 線段提供有關圖像幾何內容的重要信息。 首先，因為大多數人造物體都是由平面構成的; 其次，因為許多形狀接受直線方面的經濟描述。 線段可以用作低級特征以從圖像中提取信息，或者可以作為分析和檢測更復雜的形狀的基本工具。 作為特征，它們可以幫助解決立體分析[14]，材料裂縫檢測[17]，圖像壓縮[11]和衛星圖像索引[19]等幾個問題。
?? 理想情況下，人們希望有一種算法能夠精確檢測圖像中存在的線段，而不會發生錯誤檢測，也無需手動調整每個圖像或每組圖像的參數。 為了評估本文提出的線段檢測器（LSD）在這個方向上的趨勢，所有的實驗將使用相同的參數進行，無論圖像來源，場景和分辨率如何。
?? 線段檢測是計算機視覺中的一個老舊且經常出現的問題。 標準方法首先應用Canny邊緣檢測器[4]，接著進行Hough變換[1]，提取所有包含多個邊界點的線條，這些線條超過閾值。 這些線條之后通過使用間隙和長度閾值切割成線段。 霍夫變換方法具有嚴重的缺陷。 具有高邊緣密度的紋理區域會導致許多錯誤檢測（參見圖1樹上的斜線）。 忽略邊緣點的方向，這種算法獲得具有異常方向的線段。 而且，設定閾值是所有檢測方法的基本問題。 使用固定的閾值會導致大量的誤報或漏報（見圖1）。 圖 1
圖1.各種線段檢測方法的比較。 指示Apple PowerBook G4 1.5 GHz的處理時間。 Hough變換，Etemadi和Burns等人。 方法檢測樹上許多不相關的小線段。 PPHT不會產生錯誤檢測，但無法檢測到小線段。 Desolneux等人 控制錯誤的檢測，但在對齊的線段出現時給出不準確的解釋。 Multisegments檢測器給出了一個好的結果，但是時間過長。 LSD在線性時間中給出了類似的結果。
?? 另一種經典方法是從邊緣點開始，將它們鏈接成曲線，然后用直線標準將鏈條切割成線段[10]。 一個標準的鏈接方法是由于Etemadi [9]。 這種方法是無參數的，通常會給出準確的結果。 此外，它是同時檢測線段和弧線的少數幾種算法之一[1]。然而，結果并不完全令人滿意，如圖1所示。許多檢測到的直線和小邊緣曲線都是誤報： 再次出現基本的閾值問題。
?? Burns等人 [3]引入了一個關鍵新思想的線性時間線段檢測方法。 他們的算法不是從邊緣點開始的，實際上只使用梯度方向來忽略梯度幅度。 Kahn等人對這種算法進行了改進 [15]，[16]。 這個算法給出的線段很好的定位，但是閾值問題仍然存在。 圖1中的樹葉可以被描述為一個紋理，作為一個對象，但肯定不是一組線段。 對這些方法的檢查表明，應該添加一個選擇標準作為最后一步。
?? 這些經典方法有一些這樣的標準規則。一個很好的例子是由Matas等人提出的漸進概率霍夫變換（PPHT）[18]，[12]。像許多類似的方法一樣，它通過隨機選擇邊緣點來加速計算時間。但是改進來自于使用圖像梯度信息和錯誤檢測控制。圖1顯示了對標準霍夫變換方法的明顯改進。盡管如此，所使用的錯誤檢測控制并不完全令人滿意。首先，該機制適用于整條線，而不適用于線段檢測。長線段（與圖像中線的長度相似）會產生檢測結果，但小線段不會。結果，許多短線段缺失，如圖1所示。其次，該方法的檢測參數是每次分析邊緣點時獲得錯誤檢測的概率。但是，分析的邊緣點數量取決于圖像大小以及錯誤檢測的預期數量。該參數的默認值被設置為控制圖像大小約為256×256256×256的錯誤檢測.對于較大的圖像，錯誤檢測不再被控制，如圖 10和11顯示。任何固定值都會在大圖像上產生錯誤的檢測結果，在小圖像上漏掉。
?? 這個閾值問題由Desolneux，Moisan和Morel [6]徹底分析。他們的線段檢測方法成功地控制了誤報的數量。該方法計算對齊點的數量（梯度方向與線段大致正交的點），并在非結構化，反向（contrario）模型中找到線段為異常值。這種方法是基于一般感知原理，亥姆霍茲原理[8]，據此觀測到的幾何結構在噪聲期望值小于1時具有感知上的意義。應用亥姆霍茲原理可以保證弱感知中沒有誤報，意味著平均而言，在與分析圖像大小相同的白噪聲圖像中只能進行一次錯誤檢測。它也保證不會出現假陰性，因為噪聲中可能出現的線段必須被視為真陰性。用亥姆霍茲原理檢測線段受到與人類感知的受控心理視覺比較[7]，[8]。該比較使用合成圖像。地面真實是由確定性對齊組成的。它疊加到由小隨機線段組成的背景雜波上。通過改變背景和地面實況的參數，該設置提供了實驗檢測 - 拒絕曲線，可以與亥姆霍茲原理預測的理論曲線進行比較。 [7]，[8]中的結果顯示了20個主題的預測曲線和觀察曲線之間的令人信服的定性和定量的一致性。
?? Desolneux等人方法已經過廣泛的測試。實驗證據（包括此處顯示的所有圖像）證實，它確實找到圖像中直觀存在的線段（無假陰性）。由于該方法的保證，它幾乎沒有誤報。不幸的是，它往往會曲解對齊線段的數組（參見例如圖1中的窗口）。對這種缺陷進行了詳細的分析，并在[21]，[22]中找到了令人滿意的解決方案。該解決方案涉及更復雜的亥姆霍茲原理計算，并比較每條線上所有可能的線段（多段）數組的意義。對Desolneux等人的誤解方法進行了校正，得到了更準確的線段檢測器（見圖1）。不幸的是，Desolneux 等人而多分段檢測器是窮舉的算法。 Desolneux等人方法測試圖像中所有可能的線段，并具有O(N4)O(N4)復雜度，其中NN是圖像周長。多段式具有O(N5)O(N5)復雜性。因此，這些檢測器注定只能用于離線應用。
?? 本文的目的是提出一種線性時間算法，該算法可以累積以前算法的大部分優點而不存在缺點。 Burns等人 在線段提取方面取得突破的線段查找器將得到改進，并與來自Desolneux等人的驗證標準相結合。 其結果是LSD，線性時間線段檢測器，不需要參數調整，并提供準確的結果（見圖1）。
?? 第2節和第3節介紹了Burns等人的改進版本。 提供線段候選的算法。 第4節描述了驗證標準。 第5節給出了該算法的全局圖，并討論了其最重要的屬性。 第6節評論實驗結果，第7節結束本文。
2、線支撐區域（LINE-SUPPORT REGIONS）
?? 與經典的邊緣檢測器相比，Burns等人 方法將線段定義為圖像區域，即線支撐區域，即其點共享大致相同的圖像梯度角的直線區域。 這樣的線段大致沿平均水平線方向取向。 Burns等人算法分三步提取線段：
?? 考慮到這種方法是一個真正的突破，所提出的算法共享步驟1和2的核心思想，并進行了一些改進。 然而，步驟3是完全不同的，并且基于Desolneux 等人相反的方法。 本節介紹步驟1的新版本。 步驟2和3將在以下兩節中進行介紹。
??我們的步驟1的版本是一個區域增長算法。 圖2說明了該過程。 每個區域僅僅是以一個像素開始，并且該區域角度（region angle）設置為該像素處的水平線角度（與梯度角正交）。 然后，測試與該區域相鄰1的像素; 水平線方向等于區域角度達到一定精度2的區域被添加到該區域。 在每次迭代中，區域角度更新為區域像素的偽平均水平線方向，由此定義
圖2.對齊點區域的生長過程。 水平線方向場（與梯度方向場正交）用虛線表示。 標記像素是形成該區域的像素。 從左到右：第一次，第二次和第三次迭代，以及最終結果。
??重復該過程直到不能添加新點。 偽碼算法1給出了更多細節。 首先測試 3， 具有較大梯度幅度的種子像素，因為它們更可能屬于直線邊緣。 當一個像素被添加到一個區域時，它會被標記并且再也不會被訪問。 這個關鍵屬性使算法變得貪婪和因此線性。
算法1??無論何時在圖像中存在大且對比度良好的直邊，該算法通常會找到相同的線支撐區域，無論起點如何。 相反，結果可能取決于非線性曲線通過線段進行近似時的起始點（例如，當圖像中出現圓時）。 在這種情況下，將圓分解成線段的分解將與從不同種子點獲得的任何其他分段一樣好。 由于Burns等人的觀點，具有共同方向的連接區域幾乎總是與直線邊緣重合的事實是令人驚訝的經驗發現。 我們提到曲線的情況是一個無害的第一反例。 自古以來，光滑的曲線已經作為（小）直段的連接處理。
3、區域的矩形逼近
??在驗證步驟之前，線支撐區域（一組像素）必須與一個線段（實際上是一個矩形）相關聯。 線段由其端點及其寬度或等效的中心，角度，長度和寬度決定。 其如圖3所示的矩形近似包括所有這些參數。
圖3圖3.線段的特點是由其中心點，角度，長度和寬度決定的矩形。
??想到的第一個想法是使用平均平行線角度作為線段的主要方向。 當背景顯示出緩慢的強度變化時，這個過程可能導致錯誤的線角度估計，參見[20]。 在LSD中（這個想法最初由Kahn等人在[15]，[16]中提出），質心用于選擇矩形的中心，第一個慣性軸用于選擇矩形的方向。 梯度大小被用作像素的質量（mass）。 具有較大梯度范數的點與觀察邊緣（edges）更好地對應。 然后，以覆蓋線支撐區域的方式選擇長度和寬度。 圖4顯示了結果的一個例子。
圖4圖4.線支撐區域的矩形近似示例。 左圖：圖像。 中：線支撐區域之一。 右：矩形近似重疊到線支撐區域。
4、線段驗證
??Desolneux等人方法的兩個關鍵點 [6]是使用梯度方向和一個新的框架來處理參數設置。 他們的方法如圖5所示。計算輸入圖像的梯度，只保留水平線方向。 在圖5中，這些信息被編成了破折號的角度。 給定一條線段，該算法計算對齊點（aligned point)的數量，即具有等于線段角度的水平線方向的點，計算該數量直至某個公差ττ。 必須測試圖像上所有可能的線段; 滿足基于長度ll 和它們的對齊點kk的數量的閾值標準的那些線段被認為為有效檢測。
圖5圖5.左：水平線方向場上方顯示的一條線段（與梯度方向場正交）。 右：計算每個線段達到角度公差ττ的對齊點的數量。 顯示的線段有七個中的四個對準點。
??在自然圖像上，對應于邊緣的灰度級過渡可以是許多密集像素。 例如，這發生在焦點對象的直線邊界上。 在那種情況下，Desolneux 等人的算法給出了許多并行檢測，并且需要很大的努力才能回到正確的解釋[8]。 為了解決這個問題，將使用矩形（rectangles，具有一定寬度的線段）而不是線段。 圖6說明了這個概念。
圖6圖6.在水平線方向場上顯示的一個矩形（與梯度方向場正交）。 該矩形有20個中有9個對齊的點。
??在Desolneux et al等人的一個相反（contrario）的方法，檢測被視為一個簡化的假設檢驗問題。 事實上，在經典決策框架中，需要兩個概率模型：一個用于背景，另一個用于要檢測的對象。 在相反（contrario）的方法中，對象直接被檢測為背景模型的異常值。 另外，背景模型被簡化為最簡單的，即白噪聲。 正如Desolneux等人表明，合適的背景模型只是其中所有梯度角度是獨立且均勻分布的模型。 他們表明這是高斯白噪聲圖像的情況。 更正式地說，在背景模型H0H0下的圖像XX是隨機圖像（在網格上定義為Γ=[1,N]×[1,M]?Z2Γ=[1,N]×[1,M]?Z2）
??對于通常由于采集過程而呈現的平坦圖像區域來說，這確實是一個很好的模型，它具有白噪聲分布。 但是，更重要的是，這個模型代表了很好的等向性（isotropic）區域，而直邊則完全相反：高度各向異性(anisotropic)的區域。 因此，實際上，如果一組像素可能已經由等向性過程形成，則其不被接受為線段。 一個很好的例子如圖1所示。樹的葉子遠非白色噪音過程，而是等向性的結構; 因此，在那里沒有檢測到線段。
??有多少個統計測試TrTr要在圖像中作為潛在的矩形rr執行。 每個測試都依賴于統計數據k(r,x)k(r,x),，其是矩形rr和圖像xx中的對齊點的數量。 檢測步驟如下：如果k(r,x)≥krk(r,x)≥kr則拒絕H0H0，否則接受H0H0。 對于這個測試，非H0H0也將用HrHr表示，即矩形檢測。 因此，我們導致了為每個矩形rr確定閾值krkr的問題。 在Desolneux等人之后，krkr必須以確保在H0H0下預期的誤報數量的控制的方式被固定。 我們定義了一個矩形r∈Rr∈R 和一個圖像xx的誤報警數量，如
NFA(r,x)=#R?IPH0[k(r,X)≥k(r,x)]NFA(r,x)=#R?IPH0[k(r,X)≥k(r,x)]
??其中xx是觀察圖像，XX是H0H0下的隨機圖像,#R#R是圖像中潛在矩形的數量。 NFA(r,x)NFA(r,x)越小，rr越有意義，即在H0H0模型下繪制的圖像中出現的可能性越小。 拒絕H0H0當且僅當NFA(r,x)≤εNFA(r,x)≤ε。 我們把 εε 稱為有意義的矩形（meaningful rectangles）。
??該方法通過以下命題是合理的：
命題.
??換句話說，背景模型下的預期檢測次數少于 εε ，因此，根據亥姆霍茲原理，只有偶然發生的極少數檢測（ εε ）。
??在實踐中，只有算法步驟1中找到的線支撐區域被測試為線段檢測的候選。 但是，這并不意味著可以將#R#R設置為等于有效測試的線支撐區域的數量。 這些線支撐區域具有復雜的統計數據，與白噪聲統計數據不同。 實際上，它們中的每一個都被選為共享相同方向的像素的連接分量的邊界框。 讓我們稱B(r)B(r)為r是這樣一個邊界框的事件。 只有當我們知道如何計算條件概率IPH0[k(r,X)≥k(r,x)|B(r)]IPH0[k(r,X)≥k(r,x)|B(r)]時，計算適用于有效測試包圍框的NFA才是可能的。這個概率在直觀上遠高于IPH0[k(r,X)≥k(r,x)]IPH0[k(r,X)≥k(r,x)] 。在沒有這個復合概率的閉合公式的情況下，我們必須滿足上述命題給出的估計值，計算圖像中潛在矩形的數量。
??考慮到一個像素的精度，在N×NN×N圖像 （在網格ΓΓ的一個點上開始和結束）中有N4N4個潛在導向線段。 如果我們將矩形的可能寬度值的數量設置為N（過高估計），則潛在測試的數量將上升到#R=N5#R=N5。 這個估計很粗糙，確切的數字取決于所考慮的確切精度。 這里重要的是數量級，它允許閾值適應不同的圖像大小。 見[8]進一步討論測試次數。
??如果角度公差ττ 被設定為 τ=πpτ=πp，給定點的水平線與矩形對齊的概率（在H0H0下）為pp。 由于梯度在H0H0下的不同圖像點處是獨立的，因此k(r)k(r)遵循具有參數n(r)n(r)和pp的二項定律（binomial law），其中n(r)n(r)是矩形中的點的總數。 使用之前估計的測試數量，我們可以記為
NFA(r)=N5?b(n(r),k(r),p)NFA(r)=N5?b(n(r),k(r),p) ??其中b(n,k,p)=∑ni=k(nr)pi(1?p)n?ib(n,k,p)=∑i=kn(nr)pi(1?p)n?i代表二項式尾項。??該方法對εε 的依賴性非常弱（實際上是對數），見[6]。因此，正如Desolneux等人所建議的那樣，可以僅限一次去固定ε=1ε=1。 這通常對應于在非結構化模型上接受每個圖像的一個假陽性(false positive)檢測。 它還保證所有丟棄的線段確實可能出現在噪聲中（在這個意義上沒有誤報(false negatives)）。
5、完整的LSD算法
5.1、算法的細節
??算法2顯示了完整算法的偽代碼。 子程序GradGrad計算圖像梯度并給出三個輸出：水平線角度，梯度幅度和像素的有序列表。 參數ρρ是一個閾值：梯度幅度小于ρρ的點被丟棄(為了驗證，這些點被認為不是邊緣的一部分，因此是非對齊的。)。這個參數將在5.2節中討論。 為了構造該列表，按照它們的梯度幅度將像素分類為箱（bins); 該列表以屬于高梯度箱的像素開始，并以屬于低梯度箱的像素結束。 該列表大致按遞減的大小順序排序。 算法2??像素列表用于在搜索線支撐區域時優先考慮像素作為種子。 列表中的第一個像素是具有較高梯度大小的像素，因為它們更可能屬于邊緣。 從該像素開始，第2部分RegionGrowRegionGrow中描述的算法用于獲取線支撐區域。 然后，第3節RectApproxRectApprox中描述的算法給出該區域的矩形近似值，第4節中描述的方法計算線段的NFA。
??在我們的上下文中，線支撐區域的最佳矩形近似值是給出較小NFA值的矩形近似值。 程序ImproveRectImproveRect嘗試對最初的近似進行幾次擾動以獲得更好的近似值。 這個步驟對于大型且對比度良好的線段并不重要，但它擴展了對小型和嘈雜型線段的檢測限制。 被測試的擾動是寬度和橫向位置的變化4。理由是線段的寬度是第一個矩形近似中最差的估計參數，但也是一個非常有影響的參數。 使矩形變大一個像素的錯誤會增加大量的非對齊點，與線段的長度一樣多。 這可以增加NFA的價值，增加非檢測風險。
??NFA值的第一次計算使用概率pp（即一個點偶然對齊）完成，等于p=τπp=τπ ，其中ττ是用于獲得線支撐區域的公差。 但是，觀察到的水平線角度可能更精確，導致更好的NFA值。 從p=τπp=τπ開始，ImproveRectImproveRect也會嘗試二元精度級別（dyadic precision levels），覆蓋pp值的實際范圍5。精度越高，某些點可能會停止對齊，所以k(r)k(r)可能會減小; 根據情況，較小的pp和較小的k(r)k(r)之間的平衡可以增加或減少NFA值。 保留最好的一個。 請注意，此循環消除了pp作為方法參數。
??StatusStatus用于跟蹤由線支撐區域使用或測試的像素，如第2節中所述。但是，添加了第三種可能的狀態：NotIniNotIni，它被分配給沒有被認定為檢測的線支撐區域中的像素。 這將防止它們被用作新地區的種子點，但是如果鄰居地區增長起來，就可以使用它們。 在某些情況下，這有助于改進搜索，參見[20]。
5.2、內部參數
??LSD涉及三個參數:ρρ,ττ和 εε 。
??ρρ是梯度大小的閾值：不考慮具有小梯度的像素。 原因是要處理圖像強度值的量化。Desolneux等人 [5]表明，灰度量化會產生梯度方向角的誤差。 當梯度幅度很大時，這個誤差可以忽略不計，但對于小梯度幅度可以占主導地位。 它可以創建模式(patterns)并因此產生虛假檢測。 閾值ρρ的副作用是通過減少所考慮像素的數量來提高速度。
??我們用來設定ρρ的標準是在角度誤差大于角度公差的情況下省略掉點。 讓uu表示圖像和u~u~ 量化的圖像。 然后，u~=u+nu~=u+n,而且
??其中nn是量化噪聲。 在[5]中，顯示了圖像梯度角度的誤差可以被約束。|angleerror|≤arcsin(q|?u|)|angleerror|≤arcsin(q|?u|) ??其中qq是|?u||?u|的邊界，參見圖7。 圖7
圖7.圖像噪聲和梯度角度誤差之間的關系。
??要使|angleerror|≤τ|angleerror|≤τ ，則可得
??例如，在量化圖像灰度值為0,1,2,...,2550,1,2,...,255; |?u||?u|可以有確界q=2q=2（最壞的情況是當相鄰點得到+ 1和-1的誤差時）。 如果ττ 設置為22.5度（對應于八個不同的角度箱），梯度幅度的閾值是ρ=5.2ρ=5.2。
??ττ 是用于搜索線支撐區域的角度公差。 小值更具限制性，導致線段過度分割。 大值會導致大的地區和無關聯的地區的融合。 當圖像中存在一個對比度足夠好且足夠大的線段時，線支撐區域在這個參數上很少取決于這個參數（并且由于使用了梯度量值加權，矩形近似甚至更少）。 在臨界尺寸區域或存在較多噪聲時，此參數更重要。
??Burns等人 [3]建議使用對應于八個不同角度箱的22.5度角。 獨立地，我們達到了與提供最佳結果的值相同值。 這個參數值背后沒有任何理論，但它在成千上萬的圖像上得到了支持。
??注意 ττ 也用于設置在NFA計算中使用的第一個角度公差。 但是，pp的所有實際值的范圍也被測試。 結果是， ττ在驗證步驟和線段的理論定義中都沒有影響。
??最后，如第4節所述，檢測參數εε 不是一個關鍵因素;可以安全地將其值設置為1，這意味著平均而言，每個圖像的一次偶然檢測是可以接受的。
??總而言之，LSD可以在沒有參數調整的情況下使用，并且所有上述參數都可以被視為內部參數。 這一事實得到了成千上萬種不同種類和來源圖像的測試的支持。
5.3、算法的復雜性
??梯度大小和角度的計算與像素的數量成正比。像素通過分類可以偽分類成箱，操作可以在線性時間完成。線支撐區域查找算法的計算時間與訪問像素的數量成正比。如果區域之間沒有重疊，則該數字將等于區域中的像素總數加上每個區域的邊界像素。 NotIniNotIni條件允許區域之間的某些重疊。這種重疊等同于區域之間具有較厚的(thicker)邊界。因此，訪問像素的數量與圖像的總像素數成比例。其余的處理可以分為兩類任務。第一種，例如，對區域質量進行求和或計數對齊點，與所有區域中涉及的像素總數成比例。第二種，例如計算慣性矩或從對齊點的數量計算NFA值，與區域的數量成比例。涉及的像素總數和區域數最多等于像素數。總而言之，LSD的執行時間與圖像中像素的數量成正比。
6、實驗
??對512×512512×512大小的圖像的處理時間是一秒鐘的一小部分。 這允許在數千個圖像，不同種類的圖像，來源，尺寸和噪聲水平上測試算法; 還對視頻進行了一些測試。 應該強調的是，所有的實驗都是在不調整任何參數的情況下完成的。 參見[20]對實驗進行更深入的分析。 可以在http://iie.fing.edu.uy/~jirafa/lsd找到更多結果，包括一些視頻，演示版本和算法的源代碼。 本文中顯示的結果是在一些最具挑戰性的圖像上獲得的。
??圖8顯示了Apple PowerBook G4 1.5 GHz上的計算時間（以秒為單位）與圖像大小的關系圖。 對于大多數圖像來說，計算時間比相同大小的白噪聲圖像（圖上斜線性的一系列點）短。 主要原因是，在自然圖像中，許多像素被梯度閾值丟棄。 然而，一些圖像比白噪聲圖像需要更長的處理時間，如圖中所示。 在噪聲類結構（如草地背景）和長距離結構（如前景物體）的圖像中通常會出現這種情況。
圖8圖8. LSD處理1,297個圖像所需的計算時間（以秒為單位）作為圖像大小（像素總數）的函數。 計算是在Megawave2版本2.31a上執行的LSD完成的，運行在Apple PowerBook G4 1.5 GHz上,。 斜線性系列對應于高斯白噪聲圖像。 垂直線性系列對應于大小為3的圖像3,072×2,3043,072×2,304，今天流行的相機分辨率。
??圖9顯示了一系列關于自然圖像的實驗。請注意，檢測到的線段很好地代表了這些不同圖像的結構。左欄中的圖像包含高度幾何內容。幾乎所有預期的線段都被找到了，感知的例外就是超出意義限制的小線段。按照這個理論，很少有錯誤的檢測。右側欄中的圖像顯示了一些非幾何圖像的結果。這第二組圖像中的大多數檢測結果不對應于真正的直的或平坦的物體;它們對應于局部筆直的邊緣。在像手臂輪廓那樣的情況下，從手臂不直的意義上講，線段解釋并不嚴格正確，但是對于給定分辨率的圖像呈現的二維結構而言，這是一個合理的解釋。對于彎曲的邊緣，就像中右圖像中的輪子，線段解釋只是對曲線的經濟近似。這樣的結果是可以接受的，即每個檢測對應于圖像中的局部直線結構，并且每個局部直線結構具有相關聯的線段。
圖9圖9.自然圖像LSD的結果。
??噪音的存在會降低LSD的性能。 亥姆霍茲原理規定，不應對白噪聲圖像進行檢測。 結果，當增加方差增加的噪聲時，有意義的線段的NFA值增加。 最終，噪聲在圖像中占主導地位，NFA變得大于1，并且線段不再被檢測到。 參見[20]了解更多細節。
??噪聲也會影響區域增長算法，并且這種影響對于LSD至關重要。 噪音會產生水平線角度的變化。 低功耗噪聲產生的微小變化并且結果不受影響。 噪聲功率適中時，水平線角度的變化會變大，角度差可以達到角度公差值ττ。 然后，區域增長算法不再能夠跟隨邊緣，并且線支撐區域變得碎片化。 在存在強噪聲的情況下，僅形成小的線支撐區域并且不進行檢測。 圖10（上）顯示了一個合成噪聲圖像的例子; LSD只能檢測到邊緣的兩個小部分。 然而，沒有發現錯誤的檢測結果，與現有技術的方法形成鮮明對比，參見圖10.同樣的效果發生在真實圖像上，見圖11。
圖10圖10.用五個線段檢測算法分析兩個不同尺度的噪聲邊緣圖像。 當存在很多噪聲時（這里的高斯噪聲為σ=50σ=50），LSD不會檢測到我們可以看到的一些線段; 它也不會產生錯誤的檢測結果。 沒有錯誤檢測控制的方法會產生很多錯誤的檢測結果，導致結果無用。 在這種情況下，PPHT錯誤檢測控制失敗。 PPHT和Etemadi的方法的確在全分辨率下檢測邊緣; 這是因為檢測依賴于Canny邊緣點，其涉及高斯濾波。 處理噪聲的標準方法是高斯子采樣。 當LSD處理半分辨率圖像（第二行）時，它成功檢測邊緣; 霍夫變換方法，Etemadi方法和Burns等人 方法仍會產生錯誤的檢測結果。
圖11圖11.在嘈雜的自然圖像上可以看到圖10所示的相同效果。 三行分別對應全尺寸，1/2分辨率和1/4分辨率的高斯濾波分析。 在全分辨率下，LSD無法檢測圖像的結構，但不會產生錯誤檢測。 沒有錯誤檢測控制的算法，如霍夫變換方法，Etemadi方法和Burns等人的方法會產生無用的結果。 PPHT錯誤檢測控制在此圖像中失敗并產生許多錯誤檢測。 當噪聲占主導地位時，無法以全分辨率獲得圖像結構。 但是圖像可以用不同的尺度進行分析（可能是人類視覺）。 LSD在半分辨率下檢測到大部分結構。 請注意，PPHT方法和Etemadi方法以全分辨率檢測圖像的部分結構; 原因是兩種方法都使用Canny點，這涉及到高斯濾波。
??可以對這個理論提出批評：在 10和11的全分辨率圖像中幾乎沒有檢測到線段,即使它們對我們來說完全可見。答案是人類視覺系統使用多尺度分析。為了公平比較，我們必須授權線段檢測理論也在不同尺度上來分析圖像。 （霍夫變換方法，Etemadi方法和PPHT包括這樣一個步驟，因為它們依賴于Canny點，其處理意味著高斯濾波。）。圖10（底部）和11（中間和底部）顯示被噪聲遮蔽的線段可以通過在較粗尺度上的相同算法來檢測。以較粗糙的比例進行分析也可能有助于在全尺度上通過圖像細節檢測全局結構。見[20]。然而，用強烈的人造噪聲進行的這個實驗并不意味著線段檢測的多尺度理論是必要的。它只指出應該檢測噪聲，并且當噪聲異常強烈時執行去噪步驟或放大。
??圖12顯示了在自然圖像上的七個線段檢測算法的比較。 顯示了Apple PowerBook G4 1.5 GHz的所有計算時間以及找到的線段數量。 所使用的算法是：在免費提供的Xhoughtool軟件包[13]中實現的Hough變換方法; Etemadi的算法在其原始實現ORT-2.3中; Burns等人的算法，使用Ross Beveridge [2]（個人通信）的實現; 在免費提供的RAVL庫中實施PPHT; Desolneux等人的算法，在免費提供的圖像處理框架MegaWave2中包含的模塊align_mdl中實現; http://gawave.cmla.ens-cachan.fr; multisegment檢測器; 最后是LSD的實施，可在http://iie.fing.edu.uy/~jirafa/lsd上找到。
圖12圖12.各種線段檢測方法的比較。 指示Apple PowerBook G4 1.5 GHz的處理時間。 Etemadi的方法同時檢測線段和弧線; 這里只顯示線段。 霍夫和埃特馬迪有很多錯誤的檢測。Burns等人的方法是準確的，但有大量的錯誤檢測。 PPHT不會產生錯誤檢測，但無法檢測到多條線段。 Desolneux等人的方法沒有錯誤檢測，但是太全局化了。 Multisegments和LSD在非常不同的時間給出類似的結果。
??如上所示，霍夫變換方法通常會產生錯誤檢測，因為它不考慮邊緣方向：查看人的頭發上的水平方向。 Etemadi和Burns等人的方法存在閾值問題：需要一個決策規則來選擇好的線段;否則，檢測無效（分別檢測到1,517和3,677個線段）。由于檢測閾值過于嚴格，PPHT無法檢測到許多小線段，非常適合線檢測，但不適用于線段檢測。 Desolneux等人的方法沒有產生錯誤的檢測，但是當存在對齊的線段時沒有得到正確的解釋，如在圖12的背景中的欄桿處。而且，當緩慢梯度出現時，如在在圖像左側的表格中，這會產生多個平行檢測，而不是一個更寬的線段。Multisegment檢測可以產生良好的結果（即使并行檢測問題仍然存在，并且在某些情況下幻覺全局對齊結構（hallucinates global aligned structures）不存在，參見[20]）。然而它的計算時間是過高。目的LSD在0.7秒內對716條線段的圖像結構進行了很好的描述。
??multisegment檢測器和LSD的結果在大多數情況下是相似的。讓我們簡要地評論一下主要的區別。multisegment檢測器處理穿過圖像的每條線，為每一條線生成全局解釋。這個過程偶爾會導致圖像中不存在的全局結構的幻覺（hallucination of a global structure）。圖1顯示了一個例子：葉子中水平或垂直的小線段，并與圖像上存在的一些真實對齊線保持一致。這種明顯的隨意對齊加強了該線的意義。因此，小的線段本身無意義，被解釋為更大的多段的一部分。由于局部更多，LSD不會出現這個問題。但是，multisegment探測器的全局分析需要掌握對其他案例的正確解釋，如圖13所示。在此圖像中，LSD無法檢測到太短的小線段，而multisegment算法成功地重構了全局結構。
圖13圖13.multisegment檢測器比LSD產生更好結果的情況。 有些線段太小而不適合LSD。 這意味著他們的線路支持區域可能會產生噪音。 在每條線上進行的全局分析允許multisegment檢測器獲得正確的線解釋。
7、結論
??對實驗結果（以及讀者可能希望在線執行的許多其他實驗結果）的檢查表明，線段檢測可以是準確的并且具有少量的誤報（false positive）和漏報（false negative）檢測。這一有希望的結果可以主要歸因于Burns等人，他們將右邊緣表示作為對齊的定位像素的區域，并且Desolneux等人提出了一種消除誤報（false positives）的通用方法。實驗結果證實了可靠的原始的最初的草圖（raw
primal sketch）在數字圖像中可行的想法。然而，實驗也表明，這個理論并不完整，而是剛剛開始。圓板被檢測為直線段的串聯。這種表示必須引出曲線的概念。更準確的表示應該區分真實的多邊形和曲線。它還應該允許構建更精細的格式，例如條形，規則多邊形，周期性網格或條紋等，這些只是本文提供的測試圖像中可見的幾個。
總結
以上是生活随笔為你收集整理的【文献翻译】LSD: A Fast Line Segment Detector with a False Detection Control的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 关于论文的修改--对小修的respons
- 下一篇： 摸鱼神器——python命令行小说阅读器