角檢測

角檢測或興趣點檢測，是計算機視覺系統中用來提取特徵以及推測影象內容的一種方法。角檢測的應用很廣，經常用在運動檢測、跟蹤、馬賽克、三維建模以及物體識別中。問題定義.兩條邊的交點形成一個角。所以，如果我們只想檢測角的話，還需要對檢測出的要點進一步分析。例如也可以先經過邊檢測，之後在做一些後處理來檢測角，像是Kirsch operator和Frei-Chen masking set兩種方法。為了分辨區辨識時影象含有一部分目標影象的資訊是否正確，角檢測通常不是一個非常確定且同時需要很多額外的確認才可以確定，角檢測在影象上最簡單的做法是利用相關性，但這樣的作法需要耗費大量的運算資源以及得到的結果可能只是區域性最大值，因此有另一個常見的作法是使用Harris和Stephens所提出的經由改善Moravec方法的結果。Moravec 角檢測演演算法.這是最早使用來做角檢測的做法，他首先定義所謂的「角」就是那些自我相似程度低的點。這個演演算法檢查所有影象中的畫素，並考慮以該畫素為中心點的一片範圍，該範圍與他周圍覆蓋最大的另一個範圍的相似度做為參考，而相似度通常是將兩個範圍的對應點計算誤差的平方和(SSD: Sum of Squared differences) ，越小代表相似度越高。舉例來說，如果一個畫素是位於一片均勻強度的區塊時，這時每個畫素周圍與其附近的畫素的周圍都是相當類似的，因此相似度也高，不會被認為是角。而在圖形的邊界處的畫素，若是與邊垂直方向處附近的畫素，兩者的周圍影象相似度就會比較低，然而若是與邊平行附近的畫素，兩者的周圍影象相似度就會比較高(看到的都是一條在同樣位置的邊)，因此也不會被認為是角。只有在那些與附近畫素的周圍影象都很不相似的畫素，才會被認為是「角」。如果我們將這種與周圍的相似程度量化(使用誤差平方和)，並且找出整個影象的區域性最大值(區域性最不相似的點)，這些區域性最大值就很有可能是我們想要偵測到的「角」。Harris &amp; Stephens / Plessey / Shi–Tomasi 角檢測演演算法.Harris &amp; Stephens改善了Moravec的方法，他們直接考慮每個畫素沿著特定方向處的畫素的SSD，而不是使用與周圍畫素範圍的SSD。不失一般性，我們假設現在是對一個灰階的2維影象來做偵測。令這個圖為 formula_1 ，考慮 formula_2 位置的畫素與周圍的區塊，並選取一個固定向量 formula_3 作為該畫素的參考畫素，因此固定的這個向量 formula_3 所算出的所有差平方和的總和記做為 formula_5 ，而對於每個 formula_6 做不同加權，就可以得到formula_7如果使用泰勒展開式將 formula_8 展開，假設formula_9 和 formula_10是 formula_1 的偏微分，可以得到formula_12並將原式改寫成formula_13或是使用矩陣來簡化算式formula_14其中矩陣 formula_15 為formula_16式子中的矩陣是Harris矩陣，而括號代表對所有的 formula_6 取加權平均，一個角(或者說是要點)可以被刻劃成該點 formula_6 使得 formula_19 在不同的方向 formula_20 之間有很大的變異數的點。根據分析 formula_15 的特徵值，以上的特性可以用下面的方式闡述：在角的點上，formula_15應該要有兩個"大"的特徵值。根據特徵值的大小，我們會有以下的推論：Harris 和 Stephens 注意到計算特徵值在運算量上面相當大，計算中需要使用到取平方根的操作，因此給出了另一個近似值 formula_32 ，其中 formula_33 是需要調整的重要引數。formula_34因此該演演算法不需要真正的去做 formula_15 的特徵分解，而只需要去估計 formula_15 的行列式和跡。Shi–Tomasi 角檢測在假設一般影象每個畫素所給出的函式值通常是光滑(smooth)且穩定的(stable)，他直接去計算 formula_37 ，有時又稱該方法為 Kanade-Tomasi 角檢測。而 formula_33 的值通常是由經驗決定，而通常在 0.04–0.15 的範圍裡是可解的。另一種方法可以避開選擇 formula_33 的困擾，這個方法是使用 Noble's 角測度 formula_40 ，而角測度是計算所有特徵值的調和平均數formula_41其中 formula_42 是一個小的正常數。而角的位置的共變異數矩陣即為formula_43，可以寫成formula_44Förstner 角檢測.在某些情況，會希望更精確地去計算角的位置，為了得到近似值，Förstner 演演算法可以解出閉集上的角附近範圍中的所有切線與最接近這些切線的點，該演演算法依賴於在一個理想的角附近。一個畫素 formula_45 的切線 formula_46 可以由數學式給出formula_47其中 formula_48 是影象 formula_1 在 formula_45 點的梯度向量。而最靠近長方形範圍 formula_51 中所有切線的點 formula_52 為formula_53formula_52 到切線 formula_55 的距離依照梯度向量的大小來加權，因此若經過該點的切線有較大的梯度的話，在加權上就會佔較高的比重。嘗試著解 formula_52 ：formula_57formula_58 分別為formula_59要找出最小值可以經由計算式子對 formula_60 的微分，並讓微分後的式子等於0來解formula_60formula_62注意到如果要能夠解上述等式， formula_63 必須要是可逆的，或是說 formula_63 必須要是滿秩的，而解可以寫成formula_65只有在範圍 formula_51 之中有角時才存在。此外 Lindeberg 給出一個方法去評估角的確定性，經由最小化誤差formula_67而這對所有尺度都適用，因此這方法可以自動去適應圖片中不同梯度大小所造成的影響與誤差。此外多尺度 Harris 運算元.Harris 運算元中的微分矩陣 formula_15 會牽涉到要計算影象中的偏微分(Image derivatives) formula_71，而這可以用附近點的線性組合來做逼近，而計算線性組合時通常也會需要根據附近影象值的大小來做縮放，因此需要兩個額外的縮放引數：(i)一個區域性縮放引數主要用來讓影象平滑一點 (ii)一個積分引數用來累積在微分操作中的非線性運算元，作為影象的修正項。若以 formula_1 代表原本圖形中的亮度，formula_73 為一個將影象 formula_1 透過一個高斯濾波器讓影象變模糊的結果。formula_75而引數 formula_76 用來控制高斯濾波器的變異數formula_77令 formula_78 和 formula_79 為 formula_73 的偏導數，此外用一個高斯濾波器作為縮放大小，引數 formula_81 可供調整。則"multi-scale second-moment matrix" 可以被定義為formula_82則我們也可以用前面類似的方法來計算 formula_83 的特徵值，並且定義多尺度 Harris corner 測度為formula_84注意到區域性尺度引數 t 和積分尺度引數 s ，這兩個引數通常會有相對關係 formula_85，其中 formula_86 為一個引數通常介於 formula_87 之間。因此我們可以計算多尺度 Harris corner 測度 formula_88 ，在給定的任何區域性尺度 t 去做到多尺度角偵測。一般實際應用上，多尺度角偵測通常會先做尺度選擇的步驟，可以參考正規化尺度拉普拉斯運算元 。formula_89常常在尺度選擇的部分用到，並且用來同時調整尺度以適應該角點。formula_91formula_94