在 feature detection 的部分,FAST (Features from Accelerated Segment Test) 可以說是目前速度最快的,以下簡單說明該演算法。

之前的幾個 feature detector 其實都算不錯,唯一的缺點是不夠快,FAST 在 2006 年被提出,於 2010 年改版。

FAST 的演算法,其實並不複雜,也就是不複雜,所以快:
  1. 要判斷在影像中的某個像素 P 是否為 feature,假定其灰階值為 Ip
  2. 選取適當的 threshold 值 - t
  3. 取該像素周圍的 16 個像素值來作比較,如下圖。
  4. 如果該像素 P 為 corner,則在這 16 個像素中,必有連續的 n 個像素其灰階值都大於 (Ip + t) 或都小於 (Ip - t) ,在論文中 n 為 12
  5. High-speed Test: 用來加速剔除非 corner 的像素。
    這個方法會先檢查位於 1, 9, 5, 13 的像素值 (先是 1, 9,如果都大於或都小於,才會繼續檢查位於 5, 13),如果 P 是 corner,則這四個像素中,至少會有三個的像素值為都大於 (Ip + t) 或都小於 (Ip - t) ,否則 P 不為 corner,判斷可能是 corner 之後,才會對周圍的 16 個像素作完整的判斷。
    雖然 High-speed Test 提高了效率,不過還是有一些缺點:
    1, 如果 n < 12,則效率會變差。
    2, 關於所拿來測試的 4 個像素的位置選擇,並沒有作最佳化。
    3, High-speed Test 的結果,在判斷完是否可能為 corner 之後,即沒再作利用。
    4, 對同一個區域,可能會偵測到多個重疊的 feature。

對於上述的前三項缺點,可以用 machine learning 的方式來作最佳化,第四項則可以採用 non-maximal suppression。



non-maximal suppression 的作法為:
  1. 對所有已經判斷為 feature 的像素打分數,分數為該像素的像素值與鄰近 16 個像素的像素值之差的總和。
  2. 如果有兩個為相鄰的 feature,則比較他們的分數。
  3. 捨棄分數較低的 feature。




Reference

FAST Algorithm for Corner Detection

文字內容 或 影像內容 部份參考、引用自網路,如有侵權,請告知,謝謝。
創作者介紹

拾人牙慧點滴

silverwind1982 發表在 痞客邦 PIXNET 留言(0) 人氣()