Hough Transform

IPhOCC

物理實驗的進展所帶給我們的,很多時候不只是讓我們對於世界有更多的認識,也包括了在 科技上的各種創新,像是大家所熟悉的全球資訊網(WWW, World Wide Web),最初發明時只是為了解決歐洲核子研究組織(CERN)的資訊交換需求,沒有人預期到 WWW 會如此蓬勃發展,到今日已經融入了我們的日常生活之中。今天要介紹的 Hough transform 或許不像 WWW 這麼的知名,但其在影像處理的領域有的極為重要的應用。

WWW 的誕生地(筆者攝)

在數位的偵測器發明以前,雲霧室和氣泡室一直是粒子物理學家極為重要的工具,這類偵測器通常由一個充滿不穩定液體或氣體的腔室和長時間曝光的底片所構成,當帶電粒子通過腔室時,由於粒子所帶來的擾動會在腔室內留下稍縱即逝的軌跡,這些軌跡會被底片捕捉下來,而物理學家就可以從洗出來的相片中的軌跡來回推當初發生在腔室中的物理究竟為何。

雲霧室示意圖,注意到左下角有高能 α 粒子通過,60Co。(筆者攝)

以往,我們可以依靠肉眼和直尺等作圖工具直接在相片上工作,直接以量測的方式決定出軌跡的方程式為何。但隨著實驗數據量快速的增加,依靠肉眼來分析漸漸變得不可行,而電腦的加入,更是讓人們必須尋找快速且可以機械化重複的步驟來找出軌跡,而不再需要人們感官的介入和判斷。

Hough transform 就是在這樣的情境下被提出來的,其核心在於真實圖片空間的直線到參 數空間的點的轉換,這聽起來有點複雜,我們可以用一些簡單的例子來看。在國中我們都已經 學到,一條xy 平面上的直線可以寫成 y = m x + b 我們不需要列出直線上無窮多個點的值,而只需要知道斜率 m 和截距 b 就可以完整描述這一條直線,這就代表說,在 xy 的真實空間裡的一條直線,在 mb 的參數空間裡只是一個點。我們可以利用參數空間中的一個點,來代表真實空間的一條直線,並進行相關操作。

但這樣的轉換有幾個小問題,首先垂直線不能表示成 y = mx + b 的形式。 而且這樣的 轉換並不是均勻的,讓我們考慮固定截距 b 的情形,斜率 m 從 0 到 1 和從 1 到 2 在參數空間所佔的面積相同,但是兩者在真實空間分佈並不一致,並且當斜率越大時,差距會更明顯。這樣不均勻參數分佈,會影響到之後我們在參數空間的辨別能力。

紅線 = 0 ,綠線 m = 1,藍線 m = 2。(筆者繪)

為了避開上述的問題,我們考慮另外一種形式的直線方程式,如圖, 我們可以利用直線到原 點的鉛垂線,來唯一的決定出兩個參數到原點的距離 r 以及角度 θ ,並且我們可以把直線寫成 r = xcos θ + ysin θ 這樣的參數分佈 會相對的均勻,並且不會有垂直線無法表示的問題。

r θ 參數示意圖。(筆者繪)

有了參數空間轉換的知識之後,讓我們回到真實的問題,電腦在處理圖片時必須線經過離散化的步驟,圖片轉成由一格一格的像素所構成,利用圖片本身的對比度和一些適當的處理,我們可以決定出每一個像素有或是沒有軌跡通過。接著,我們要決定某一個有軌跡通過的格子,通過他的究竟是哪條直線。但事實上,單看這一個點我們是不能決定出是哪一條直線的,我們只能知道可能的直線有哪些,這聽起來有點抽象。回到式 [rrr] ,當我們固定 x0y0 時,滿足式子的 rθ 其實就是通過 (x0, y0) 的所有可能直線。我們可以看出,等號的左邊其實是三角函數的疊合,可以整理得到得到 r = A(x0, y0)c os(θ + θ0(x 0, y0)) 這代表在真實空間的每一個點,通 過他的直線族在參數空間會是一個正弦曲線。

真實空間中的同條直線上的相異兩點,雖然通過的直線族不完全相同,但我們可以預期,至少有一條直線是相同的,這表示在參數空間代表兩個點的正弦曲線至少會有一個交點。

從以上的分析,我們最終可以把在真實空間尋找直線的問題,轉化成在參數空間尋找許多正弦波交點的問題,我們可以在參數空間中統計每一個像素被正弦曲線通過的次數,如此就可以找出交點的位置。最後在利用該點的參數,就可以唯一的確定出在真實空間中的曲線究竟為何。

真實空間中的直線 y = x + 1。(筆者繪)
變換到參數空間的結果,可以注意到各個正弦曲線都交在 r2 = 2 θ = π/4,即 y = x + 1 的參數上。(筆者繪)

如今,Hough transform 的應用並不只粒子物理資料的分析,而是廣泛的被應用在影像處理的各個領域。而其推廣的形式,也讓他所能識別的圖形不侷限在直線,而可以應用到任意的 形狀識別。

作者介紹

呂佳軒 
曾經拿過物奧最佳實驗。雖然大學讀的是物理系,但還雙/輔了資工系和生科系,物理系只修了剛好可以畢業的學分而已。