【導(dǎo)讀】基本的hough變換方法是將圖像中的。每一邊緣點(diǎn)映射到參數(shù)空間的一個(gè)區(qū)域，選取累積最多的參數(shù)。中，由于噪音、數(shù)字化錯(cuò)誤和圖形變異等因素真實(shí)的圖形經(jīng)常被曲解，因此，圖像在應(yīng)用hough變換后，很難找到單一的峰值，這也就造成了檢測的難度。換的原理基礎(chǔ)上利用圓的幾何特征提出了改進(jìn)算法。重點(diǎn)介紹隨機(jī)hough變。換原理，將傳統(tǒng)hough變換圓檢測時(shí)的二維參量統(tǒng)計(jì)變成一維參量統(tǒng)計(jì)。

　　

【正文】 的邊緣總有一些模糊，所以這里洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 22 垂直上下的邊緣剖面都表示成有一定坡度。 圖 31(a)中，對灰度值剖面的一階導(dǎo)數(shù)在圖像由暗變明的位置處有一個(gè)向上的階躍，而在其他位置都為零 [12]。對灰度值剖面的二階導(dǎo)數(shù)在一階導(dǎo)數(shù)的階躍上升區(qū)有一個(gè)向上的脈沖，而在一階導(dǎo)數(shù)的階躍下降區(qū)有一個(gè)向下的脈沖。在這兩個(gè)階躍之間有一個(gè)過零點(diǎn)，他的位置正對應(yīng)原圖像中邊緣的位置。所以可用二階導(dǎo)數(shù)的過零點(diǎn)檢測邊緣位置，而用二階導(dǎo)數(shù)在過零點(diǎn)附近的符號確定邊緣像素在圖像邊緣的暗區(qū)或明區(qū)。分析圖 31(b)可以得到相似的結(jié)論。這里圖像是由明變暗，所 以與圖 31(a)相比，剖面左右對換，一階導(dǎo)數(shù)上下對換，二階導(dǎo)數(shù)左右對換。 圖 31(c)中，脈沖狀的剖面邊緣與圖 31(a)的一階導(dǎo)數(shù)形狀相同，所以31(c)圖的一階導(dǎo)數(shù)形狀與 31(a)圖的二階導(dǎo)數(shù)形狀相同，而它的二階導(dǎo)數(shù)的兩個(gè)過零點(diǎn)正好分別對應(yīng)脈沖的上升沿和下降沿。通過檢測脈沖剖面的二階導(dǎo)數(shù)的兩個(gè)過零點(diǎn)就可以確定脈沖的范圍。 圖 31(d)中，屋頂狀邊緣的剖面可看作是將脈沖邊緣底部展開得到的，所以它的一階異數(shù)是將圖 31(c)脈沖剖面的一階異數(shù)的上升沿和下降沿展開得到的。通過檢測屋頂狀邊緣剖面的一階 導(dǎo)數(shù)過零點(diǎn)可以確定屋頂位置。 真實(shí)圖像中 (灰度 )邊緣是比較復(fù)雜的，由于采樣的原因，實(shí)際圖像中的邊緣是有坡度的，所以一般需要用 5 個(gè)參數(shù)來描述它 ： (1) 位置：邊緣 (等效的 )最大灰度不連續(xù)處。 (2) 朝向：跨越灰度最大不連續(xù)的方向。 (3) 幅度：灰度不連續(xù)方向上的灰度差。 (4) 均值：屬于邊緣的像素的灰度均值。 (5) 斜率：邊緣在其朝向上的傾斜程度。 對邊緣的檢測常借助邊緣在上述 5 個(gè)方面的特點(diǎn)來進(jìn)行。所謂邊緣檢測也常指通過計(jì)算獲得了邊緣的 5 個(gè)參數(shù)中的若干個(gè)。 基于以上的討論和檢測原理，可采用許多不同的 方式來檢測邊緣。在空域?qū)吘壍臋z測常采用局部算子進(jìn)行。下面分別對幾種經(jīng)典的邊緣檢測算子 (包括一階和二階 )進(jìn)行介紹。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 23 傳統(tǒng)的邊緣檢測算法 現(xiàn)有的方法主要以各種微分算子為基礎(chǔ)，結(jié)合用范本及門限、平滑等手段提取邊緣。如 Robert 算子、 Sobel 算子、 Prewitt 算子等，其都是一階微分算子，二階微分算子有拉普拉斯算子、 M 一 H 算子等。一階微分是圖像邊緣和線條檢測的最基本方法。常用的算子有： (1)Roberts 算子 (2)Sobel 算子 (3)Prewitt 算子 由于一階微分算子通常在邊緣附近的區(qū)域 內(nèi)產(chǎn)生較寬的響應(yīng)，所得的結(jié)果常需加以細(xì)化處理，影響了邊緣定位的精度。而利用二階導(dǎo)數(shù)零交叉所提取的邊緣寬度為一個(gè)像素，所得結(jié)果無需細(xì)化，有利于邊緣的精確定位。二階微分算子主要有： (1)Laplace 邊緣檢測算子 (2)LOG 算子 通過研究與比較，發(fā)現(xiàn)用不同的邊緣檢測算子對同一幅具有不同灰度類型、不同邊緣類型的原始圖像進(jìn)行檢測，其檢測效果的差異是很明顯的。 Roberts 算子對灰度呈階梯狀的邊緣檢測效果較佳，且所得邊緣細(xì)小，對邊緣的朝向及噪聲不敏感，運(yùn)算量小，但部分邊緣出現(xiàn)不連續(xù)的情況Sobel 算子和 Prewitt算子檢測的信息比較豐富，但同時(shí)也帶來了許多的偽緣點(diǎn)，放大了噪聲，而且兩種算法檢測到的邊緣線比較粗，邊緣定位精度不高。在一般的情況下，需要在這兩種算法的基礎(chǔ)上細(xì)化等算法，提高邊緣定位精度，或者結(jié)合亞像素定位技術(shù)，以達(dá)到準(zhǔn)確的邊緣檢測定位的目的；對于 Laplace 算子，其具有旋轉(zhuǎn)不變性的特點(diǎn)，所以其定位精度高偽邊緣比較少，但它信息丟失比較嚴(yán)重，有些邊緣也出現(xiàn)了不連續(xù)的情況，而且易受噪聲干擾。 LOG 算子把高斯平滑濾波器和拉普拉斯銳化濾波器結(jié)合了起來，先平滑掉噪聲，再進(jìn)行邊緣檢測，但是平滑和銳化的結(jié)合，會使檢測后 的圖像細(xì)節(jié)比較模糊，邊緣粗大，嚴(yán)重的影響了邊緣的定位，給后續(xù)的檢測帶來不便。 眾所周知：每種邊緣檢測算子都存在著這樣或那樣不完善的問題，即沒有一種邊緣檢測算法適用于所有圖像。因此，在對具體圖像進(jìn)行邊緣檢測時(shí)，需要根據(jù)圖像的特點(diǎn)選用適當(dāng)?shù)乃惴āＲ话銇碇v，一個(gè)好的邊緣檢測算法應(yīng)滿足如下要求： (1) 檢測精度高。 (2) 抗噪聲能力強(qiáng)。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 24 (3) 計(jì)算簡單。 (4) 易于并行實(shí)現(xiàn)。 基于邊緣檢測的分割物體的邊緣是圖像局部變化的重要特性，以不連續(xù)性的形式出現(xiàn)，通常用方向和幅度來描述圖像的邊緣特性。一般來講，邊緣走向 的像素變化平緩，而垂直于邊緣走向的像素變化劇烈。基于邊緣檢測的基本思想是先檢測圖像中的邊緣點(diǎn)，再按一定的方法連接成輪廓，從而構(gòu)成分割區(qū)域。邊緣檢測有模板匹配、微分法、統(tǒng)計(jì)方法和輪廓線擬合等方法。邊緣檢測的基本算法，如 Sobel 算子、梯度算子、 Marr 算子、 Robert 算子、Prewitt 算子、拉普拉斯算子，高斯濾波器和 Canny 算子等。 1. 經(jīng)典算法 傳統(tǒng)的邊緣檢測算法通過梯度算子來實(shí)現(xiàn)，在求邊緣的梯度時(shí)，需要對每個(gè)象素位置計(jì)算。在實(shí)際中常用社區(qū)域模板卷積來近似計(jì)算，模板是 N*N的權(quán)值方陣，經(jīng)典的梯度算子 模板： Sobel 模板、 Kirsch 模板、 Prewitt 模板、Roberts 模板、 Laplace 模板等。 Kirsch 算子的運(yùn)算量比較大。其次在邊緣檢測中邊緣定位能力和噪聲抑制能力方面，有的算子邊緣定位能力強(qiáng)，有的抗噪聲能力比較好： Roberts算子利用局部差分算子尋找邊緣，邊緣定位精度較高，但容易丟失一部分邊緣，同時(shí)由于沒經(jīng)過圖像平滑計(jì)算，不能抑制噪聲。該算子對具有陡峭的低噪聲圖像回應(yīng)最好； Sobel 算子和 Prewitt 算子都是對圖像進(jìn)行差分和濾波運(yùn)算，差別只是平滑部分的權(quán)值有些差異，對噪聲具有一定的抑制能 力，不能完全排除檢測結(jié)果中出現(xiàn)偽邊緣。這兩個(gè)算子的邊緣定位比較準(zhǔn)確和完整，但容易出現(xiàn)邊緣多像素寬。對灰度漸變和具有噪聲的圖像處理的較好； Kirsch算子對 8 個(gè)方向邊緣信息進(jìn)行檢測，因此有較好的邊緣定位能力，并且對噪聲有一定的抑制作用，該算子的邊緣定位能力和抗噪聲能力比較理想；Laplace 算子是二階微分算子，對圖像中的階躍型邊緣點(diǎn)定位準(zhǔn)確且具有旋轉(zhuǎn)不變性即無方向性。但該算子容易丟失一部分邊緣的方向信息，造成不連續(xù)的檢測邊緣，同時(shí)抗噪聲能力比較差，比較適用于屋脊型邊緣檢測。 2. 最優(yōu)算子 最優(yōu)算子又可以分為 馬爾算子 (LOG 濾波算子 )、坎尼 (Canny)邊緣檢測、曲面擬合法。 Torre 和 Pgogio 提出高斯函數(shù)是接近最優(yōu)的平滑函數(shù)， Marr洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 25 和 Hildreth 應(yīng)用 Gaussian 函數(shù)先對圖像進(jìn)行平滑，然后采用拉氏算子根據(jù)二階導(dǎo)數(shù)過零點(diǎn)來檢測圖像邊緣，稱為 LOG 算子。對于 LOG 算子數(shù)學(xué)上已經(jīng)證明，它是按照零交叉檢測階躍邊緣的最佳算子。但在實(shí)際圖像當(dāng)中，高斯濾波的零交叉點(diǎn)不一定全部是邊緣點(diǎn)，還需要進(jìn)一步確定真?zhèn)?；坎尼把邊緣檢測問題轉(zhuǎn)換為檢測單位函數(shù)極大值問題，根據(jù)邊緣檢測的有效性和定位的可靠性，研究了最優(yōu)邊緣檢測器所 需的特性，推導(dǎo)出最優(yōu)邊緣檢測器的數(shù)學(xué)表達(dá)式。與坎尼密切相關(guān)的還有 Deriche 算子和沈俊算子，它們在廣泛的意義下是統(tǒng)一的；曲面擬合的基本思想是用一個(gè)平滑的曲面與待測點(diǎn)周圍某鄰域內(nèi)像素的灰度值進(jìn)行擬合，然后計(jì)算此曲面的一階或二階導(dǎo)數(shù)。該方法依賴于基函數(shù)的選擇，實(shí)際應(yīng)用中往往采用低階多項(xiàng)式。 3. 多尺度方法 早期邊緣檢測的主要目的是為了處理好尺度上的檢測和定位之間的矛盾，忽略了在實(shí)際圖像中存在的多種干擾邊緣，往往影響到邊緣的正確檢測和定位。 Rosenfeld 等首先提出要把多個(gè)尺寸的算子檢測到的邊緣加以組合；Marr 倡導(dǎo)同時(shí)使用多個(gè)尺度不同的算子，并提出了一些啟發(fā)性的組合規(guī)則。這一思想后來經(jīng) Witkin 等發(fā)展成了尺度空間濾波理論，說明了不同尺度上的零交叉的因果性； Lu Jain 對二維信號進(jìn)行了類似的研究； Yuille 和 Pgogio證明了對于任意維信號，當(dāng)用高斯函數(shù)濾波時(shí)，尺度圖中包含了數(shù)目最小的零交叉，并且可以由粗到細(xì)地跟蹤這些零交叉。 多尺度信號處理不僅可以辨識出信號中的重要特征，而且能以不同細(xì)節(jié)程度來構(gòu)造信號的描述，在高層視覺處理中有重要的作用 [18]。其中小波變換是近年得到廣泛應(yīng)用的數(shù)學(xué)工具。與傅立葉變換 和窗口傅立葉變換相比，小波變換是時(shí)間和頻率的局域變換，因而能有效地從信號中提取信息，它通過伸縮和平移等運(yùn)算功能對函數(shù)或信號進(jìn)行多尺度細(xì)化分析，解決了傅立葉變換不能解決的很多困難問題，因而被譽(yù)為“數(shù)學(xué)顯微鏡”。信號突變點(diǎn)檢測及由邊緣點(diǎn)重建原始信號或圖像是小波變換應(yīng)用的一個(gè)很重要的方面。 從邊緣檢測的角度看，小波變換有以下幾個(gè)優(yōu)點(diǎn)： (1) 小波分解提供了一個(gè)數(shù)學(xué)上完備的描述。 (2) 小波變換通過選取合適的濾波器，可以極大地減小或去除所提取的洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 26 不同特征之間的相關(guān)性。 (3) 具有“變焦”特性：在低頻段可用高頻分 辨率和低時(shí)間分辨率；在高頻段可用低頻分辨率和高時(shí)間分辨率。 (4) 小波變換可通過快速算法來實(shí)現(xiàn)。 小波邊緣檢測算法，依據(jù)的是信號主要分布在低頻部分或低尺度部分，而噪聲分布于高頻部分或高尺度部分的特點(diǎn)。另外小波變換具有較強(qiáng)的去相關(guān)性，變換后的小波系數(shù)之間仍然存在大量的相關(guān)性質(zhì)，即小波系數(shù)在不同分辨率下的對應(yīng)系數(shù)之間具有較強(qiáng)的相關(guān)性或稱層間的相關(guān)性。通過對比該方法能夠較好多的防止噪聲干擾，又能有效地保留圖像邊緣。 4. 自適應(yīng)平滑濾波方法 該方法是邊緣檢測的一個(gè)重要方法，無論是對于灰度圖象處理還是距離圖像和 平面曲線處理都是非常有效的。它的優(yōu)點(diǎn)是： (1) 平滑濾波的迭代運(yùn)算使信號的邊緣得到銳化，此時(shí)再進(jìn)行邊緣檢測，可以得到很高的邊緣定位精度。 (2) 通過自適應(yīng)迭代平滑，實(shí)現(xiàn)了將高斯平滑之后的階躍邊緣、屋頂狀邊緣和斜坡邊緣都轉(zhuǎn)化為理想的階躍邊緣，提高了圖像的信噪比。 (3) 經(jīng)過多次迭代運(yùn)算，圖像按邊緣分塊實(shí)現(xiàn)自適應(yīng)平滑，但不會使邊緣模糊。 (4) 應(yīng)用自適應(yīng)平滑濾波得到一種新的圖像尺度空間描述。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 27 第 4 章 Hough 變換 Hough 變換的原理 Hough 變換是圖像處理中從圖像中識別幾何形狀的基 本方法之一。Hough 變換的基本原理在于利用點(diǎn)與線的對偶性，將原始圖像空間的給定的曲線通過曲線表達(dá)形式變?yōu)閰?shù)空間的一個(gè)點(diǎn)。這樣就把原始圖像中給定曲線的檢測問題轉(zhuǎn)化為將圖像空間內(nèi)具有一定關(guān)系的像元進(jìn)行聚類，尋找能把這些像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應(yīng)點(diǎn)，換句話說，也就是尋找參數(shù)空間中的峰值問題。 平面中任意一條直線可以用極坐標(biāo)方程方程來表示，即可以用 ? 和 ? 兩個(gè)參數(shù)確定下來，對于圖像空間任意點(diǎn) ),( yx ，其函數(shù)關(guān)系為： ??? sinco s yx ?? () 其中 ? 為原點(diǎn)到直線的距離 (即原點(diǎn)到直線的垂直線的長度 )， ? 確定了直線的方向 (即原點(diǎn)到直線的垂直線與 x 軸方向的夾角 )。數(shù)字圖像處理中我們在圖像空間 ),( yx 和 Hough 空間 ),( ??H 面對的都是離散量。因此，每個(gè)像素點(diǎn)都能投影到參數(shù)空間中的一些點(diǎn)上。如果對于同一直線 l 上的 n 個(gè)點(diǎn)進(jìn)行上述變換，則原圖像空間 n 個(gè)點(diǎn)在參數(shù)空間中對應(yīng)地得到 n 條正弦曲線，并且這些曲線相交于同一點(diǎn)，它同樣具有以上的兩個(gè)性質(zhì)。因此圖像空間中共線的點(diǎn)與參數(shù)空間中共點(diǎn)的線存在對應(yīng)關(guān)系，只要找 出參數(shù)空間中共點(diǎn)的曲線，就能確定圖像空間中的曲線。 Hough 變換的圓檢測 Hough 變換最早應(yīng)用在直線檢測上，大量試驗(yàn)表明其對各種噪聲、形變、邊緣斷續(xù)甚至區(qū)域殘缺都具有很好的魯棒性和適應(yīng)性。直線的 Hough 變換是一個(gè)兩參數(shù)的參數(shù)空間，推而廣之，其它常見曲線也存在對應(yīng)的參數(shù)空間。在坐標(biāo)平面上確定一個(gè)圓需要三個(gè)參數(shù) —— 圓的半徑、圓心的 x 軸坐標(biāo)和 y軸坐標(biāo)，因此圓的 Hough 變換是一個(gè)以圓的半徑和圓心坐標(biāo)為參數(shù)的三維空間。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì) (論文 ) 28 經(jīng)典的 Hough 圓檢測 已知圓的一般方程為： ? ? ? ?22 2x a y b r? ? ? ? () 式中： ? ?,ab 圓心， r — 圓的半徑。 如果我們將式 ()的未知數(shù)反轉(zhuǎn)， yx? 是常量，而 a b r?? 變作未知數(shù)，那么顯然式 ()就是一個(gè)圓錐的方程。換句話說，過 yx? 平面上固定點(diǎn)的所有圓的 a b r?? 對應(yīng)于參數(shù)空間中的一個(gè)三維錐面。這樣，檢測 yx? 平面上的圓的問題就轉(zhuǎn)換到檢測 a b r?? 參數(shù)空間上三維錐面的交點(diǎn)。圖像平面的方程轉(zhuǎn)化為參數(shù)平面上的示意圖如圖 41 所示。 圖 41 圓的參數(shù)空間表示 但是上述方法的算法復(fù)雜度太高，假設(shè)要檢測 100 100 分辨率的小圖像，我們就至少需要 100 100 100 大小的參數(shù)空間。直接用參數(shù)空間投票的 方法計(jì)算復(fù)雜、資源需求大，處理時(shí)間長。在大噪聲和具有復(fù)雜圖像背