Can you summarize the following document?
        
  這個變換為了解析氣泡室 (bubble chamber)的圖片才誕生的(Hough, 1959)。  霍夫變換在1962年申請為專利U.S. Patent 3,069,654,其專利名為"辨識複雜圖案的方法及手段"(Method and Means for Recognizing Complex Patterns)。 任一條直線可以由斜率和截距來表示,在該專利中,利用斜率和截距來將一條直線引數化,然而這會導致無界的轉換空間(unbounded transform space),因為斜率有可能是無限大。  而現在被廣泛使用的formula_1表示式,第一次出現在 雖然這早已經雷登變換的<unk>準。  O'Gorman and Clowes' variation 是在這篇 而現代的霍夫變換的發明故事紀載於

  在自動化分析數碼圖片的問題裡,其中一個常有的子問題是偵測某些簡單的直線、圓形、橢圓形。在多數情況下,邊緣偵測器(edge detector)會先用來做圖片前處理,將原本的圖片變成只含有邊緣的圖片。 因為圖片的不完美或是邊緣偵測的不完美,導致有些點(point)或畫素(pixel)缺漏,或是有噪聲使得邊緣偵測器所得的邊界偏離了實際的邊界。所以無法直觀的將檢測出的邊緣分成直線、圓形、橢圓形的集合, 而霍夫變換解決上述問題,藉由霍夫變換演算法中的投票步驟,在複雜的引數空間中找到圖形的引數,電腦可以由引數得知該邊緣(edge)是哪種形狀。  最簡單的霍夫變換是在影象中識別直線。在平面直角座標系(x-y)中,一條直線可以用方程式 表示,formula_3是直線的截距,formula_4是直線的斜率。 而formula_5可以視為引數空間formula_6中的一點。當直線垂直於formula_7軸時,斜率為無限大, 若用電腦數值計算時會很不方便,因此Duda 和 Hart  提出使用Hesse normal form來表示直線的引數 formula_9是從原點到直線的距離,formula_10是formula_11和formula_7軸的夾角。利用引數空間formula_13解決了原本引數空間formula_6發散的問題, 進而能夠比較每一個線段的引數,有人將formula_13平面稱為二維直線的霍夫空間(Hough space)。這個表示方法讓霍夫變換跟二維的雷登變換非常相似,可以說是一體兩面  給定一個點formula_16,通過該點的所有直線的引數formula_13的集合,會在formula_13平面上形成一個三角函式,可由下方程式證明 因此,給定很多點,判斷這些點是否共線(concurrent lines)的問題,經由霍夫變換之後,變成判斷一堆曲線(每一個點在formula_13平面上代表一條曲線)是否 在formula_13平面上相交於同一點的問題(concurrent curves)。

  偵測直線的霍夫變換演算法使用一個稱作累加器(accumulator)二維的矩陣,來偵測圖片中是否有直線可以用方程式formula_8來描述。 Accumulator矩陣的維度等於未知的引數的總數,舉例來說,要尋找是否有一條直線,他的引數空間的變數總共有兩個formula_9和formula_10,因此Accumulator矩陣的維度是2。 而這個二維的accumulator矩陣,一個維度代表經過量化(quantized)的formula_9,另一個維度則是代表量化的formula_10,因此每一個矩陣的元素(element)的值,是可以用該元素表示的直線 的數量總和,因此矩陣元素的最大值的意義是,該張圖片裡出現該元素代表的直線的信心最大。  對於每一個畫素(pixel) formula_28與其鄰近的點,演算法會依據一些證據來判斷是否有一條直線通過該畫素formula_28與其鄰近的點,如果有,演算法就會把該條直線的引數 formula_13所對應到的Accumulator矩陣裡的元素增加1,最後在選出Accumulator矩陣裡,大於閾值(threshold)的一些區域性最大值(local maximum),就可能找到真地存在於圖片上的直線, 在其他狀況下,不使用threshold改用其他的技巧可以讓演算法的表現(performance)更好。然而,霍夫變換隻能求得線的引數,無法求得該條線的長度,所以,必須在霍夫變換完的下一步,將線條配對到 圖上的線條。而霍夫變換的誤差來源,可能是圖片的不完美(噪聲、遺漏畫素),使得邊緣偵測器(edge detector)的偵測出錯誤的邊界。

  輸入的圖片中有兩條粗直線,經過霍夫變換後的結果得到accumaltor矩陣,右圖就是把accumaltor矩陣畫出來,越亮值越大,越黑值越小。在右圖中,有兩個很明顯的亮點, 這兩個亮點分別代表兩條不同引數的直線,與輸入的圖片(左圖)吻合。然後讀取矩陣的兩個最大值就可以得出這兩條線距畫面中心距離以及角度。

  利用梯度的方向(gradient direction)減少投票數  Kernel-based Hough transform (KHT)

  霍夫變換透過由投票機制(accumaltor矩陣的極大值)來找出線條的引數,這種機制讓霍夫變換能夠在有噪聲的圖片中找出線段。在有噪聲的情況下,如果量化(quantization)的間距(step)太細, 會讓票數分散,換句話說使得應該集中的值分散到極大值附近的矩陣元素。  當引數空間的變數變多,每個矩陣元素的平均大小也會下降,使得正確的引數跟其他引數之間的差變小。另外,每增加一個引數,霍夫變換的複雜度就會增加一個formula_31, formula_32是引數的總數、formula_33是圖片的大小。因此使用霍夫變換偵測直線和圓以外的形狀時,必須要非常小心上述的問題。  最後,霍夫變換的效率取決於輸入圖片的品質,邊緣必須要正確呈現才能讓霍夫變換有效率,當圖片有噪聲的時候,在霍夫變換的前一級要做抑制噪聲的動作。
霍夫變換是一種特徵提取,被廣泛應用在影象分析、電腦視覺以及數碼影像處理。 霍夫變換是用來辨別找出物件中的特徵,例如:線條。他的演算法流程大致如下,給定一個物件、要辨別的形狀的種類,演算法會在引數空間中執行投票來決定物體的形狀,而這是由累加空間(accumulator space)裡的區域性最大值來決定。