harris邊角（興趣點）檢測演算法

08-26

harris邊角（興趣點）檢測演算法

來自專欄計算機視覺論文閱讀筆記

動機

如果在右圖幾個綠框尋找和左圖紅框相同的，我們很快就找到第二張子圖。因為豎起來的柱子是特徵。為什麼是柱子？應為有三條邊相交於兩個點，邊緣和角點都是底層重要特徵。它對目標追蹤/動作分割/三維重建都有重要的影響。

我們怎麼定義一個角點？兩條直線相交就是一個角點？

如果我們在平坦的地方移動窗口，圖像灰度值不會有太多變化，如果我們在邊緣移動窗口，沿著邊緣方向移動，灰度值變化不大；沿著垂直於邊緣方向移動，灰度值變化很大。如果我們在角落移動窗口，在任何方向移動灰度值變化都很大。那麼我們怎麼來找到這些角點呢？

數學知識

我們學到的知識都是有用的，我們站在巨人的肩膀上。

在講如何建模之前先講兩個知識點。

泰勒展開

泰勒展開公式是一種統一的形式，非常完美。

一維泰勒展開公式：

$f(x)=f(a)+f(a)(x-a)+...$

二維泰勒展開公式：

$f(x+u,y+v)=f(x,y)+uf_x(x,y)+vf_y(x,y)+...$

矩陣的特徵值和特徵向量

對於矩陣A，如果滿足 $Ax=lambda x$ ,則向量x稱為A的特徵向量， $lambda$ 是A的特徵值。

如果將A轉化為行列式，那麼有：

$det|A|=prod_{j=1}^{n}lambda_j$

$Tr(A)=sum_{j=1}^{n}{lambda_j}$

不懂的回去補高等數學無窮級數和線性代數知識！

建模過程

我怎麼去量化某個窗口移動的灰度值變化大小？

作者使用了自相關函數：

$E(u,v)=sum{(I(x+u,y+v)-I(x,y))^2}$

(u,v)是窗口移動的方向，I(x,y)是灰度值，那麼E（x，y）的意思是我沿（u,v）方向移動與原來窗口的灰度值之差的平方的總和。E（x,y）越大，說明（x,y）是邊角的可能性越大，如果我們對E（x,y）設置一個閥值，就可以檢測出角點（corner）。

但是我怎麼去選擇方向啊？如果所有都選不是很麻煩，計算量也大？

於是泰勒級數用上了。下面對E（x,y）進行變形： $sum{(I(x+u,y+v)-I(x,y))^2}=sum{(I(x,y)+uI_x+vI_y-I(x,y))^2}$

這是對I(x+u,y+v)的一階近似。

通過化簡再做平方展開我們得到：

$E(u,v)=sum(u^2I_x^2+2uvI_xI_y+v^2I_y^2)$

使用矩陣形式改寫得到：

把中間的矩陣看成M，則：

這個M是很重要的M，把它分解成特徵值和特徵向量的組合：

$M=ABA$

其中A是由特徵向量構成

而B則是一個2*2的對角矩陣，對角線為特徵值 $lambda_1,lambda_2$ 。

我們知道位移向量左乘以A得到一個方向向量，而這個方向向量再乘以B，將有以下情況：

（1）如果 $lambda_1,lambda_2$ 值很小，則是平坦的區域；

（2）如果 $lambda_1,lambda_2$ 一個大一個小，則是邊緣；

（3）如果 $lambda_1,lambda_2$ 兩個都很大，則判定為corner。

那麼我們可以得到一個反應（response function）函數來判斷邊角：

$R = min(lambda_1,lambda_2)$

這個公式說明如果我的較小特徵值都很大，說明兩個特徵值都很大，所以可以判定為corner。

但是計算特徵值是比較耗時的。

因此Harris使用了一點啟發式思維，將R定義成：

$R = det|M|-Kcdot Tr(M)=lambda_1lambda_2-k(lambda_1+lambda_2)^2$

通常k取0.04-0.06之間。

通過判斷R值，就可以判斷是不是corner。

演算法總結

自然而然地，我們得出了corner檢測演算法：

計算窗口在x和y方向的梯度Ix,Iy。
計算窗口在梯度之間的乘積： $I_x^2 = I_xcdot I_x$ $I_y^2 = I_y cdot I_y$ $I_xI_y = I_x cdot I_y$
計算每個像素點的梯度乘積之和.
定義矩陣M。
計算R值。
採用非最大值濾波，使用閥值檢測角點。

該演算法能夠適應圖片的旋轉，但不能適應縮放，應為放大圖片將會使角變成平滑的邊緣，縮小圖像使角變成一個點。

感想

總的來說，我認為這是一個非常經典的建模過程，值得學習。由於時間的關係我還沒有看源碼，只知道一個大概的思路。對於圖像而言，矩陣，梯度都是很基礎的知識點，經常會用到。

reference:

1.Interest point detection

2.lectrue 06:harris corner detection

3.A combined corner and edge detector

4.Harris 角點

harris邊角（興趣點）檢測演算法

目錄

動機

數學知識

建模過程

演算法總結