角點(diǎn)：最直觀的印象就是在水平、豎直兩個(gè)方向上變化均較大的點(diǎn)，即Ix、Iy都較大

　　邊緣：僅在水平、或者僅在豎直方向有較大的變化量，即Ix和Iy只有其一較大 平坦地區(qū)：在水平、豎直方向的變化量均較小，即Ix、Iy都較小

　　Harris角點(diǎn)檢測(cè)算子是于1988年由CHris Harris & Mike Stephens提出來的。在具體展開之前，不得不提一下Moravec早在1981就提出來的Moravec角點(diǎn)檢測(cè)算子。

　　1.Moravec角點(diǎn)檢測(cè)算子

　　Moravec角點(diǎn)檢測(cè)算子的思想其實(shí)特別簡(jiǎn)單，在圖像上取一個(gè)W*W的“滑動(dòng)窗口”，不斷的移動(dòng)這個(gè)窗口并檢測(cè)窗口中的像素變化情況E。像素變化情況E可簡(jiǎn)單分為以下三種：A 如果在窗口中的圖像是什么平坦的，那么E的變化不大。B 如果在窗口中的圖像是一條邊，那么在沿這條邊滑動(dòng)時(shí)E變化不大，而在沿垂直于這條邊的方向滑動(dòng)窗口時(shí)，E的變化會(huì)很大。 C 如果在窗口中的圖像是一個(gè)角點(diǎn)時(shí)，窗口沿任何方向移動(dòng)E的值都會(huì)發(fā)生很大變化。

　　上圖就是對(duì)Moravec算子的形象描述。用數(shù)學(xué)語(yǔ)言來表示的話就是：

　　其中（x，y）就表示四個(gè)移動(dòng)方向（1，0）（1，1）（0，1）（-1，1），E就是像素的變化值。Moravec算子對(duì)四個(gè)方向進(jìn)行加權(quán)求和來確定變化的大小，然和設(shè)定閾值，來確定到底是邊還是角點(diǎn)。

　　2.Harris角點(diǎn)檢測(cè)算子

　　Harris角點(diǎn)檢測(cè)算子實(shí)質(zhì)上就是對(duì)Moravec算子的改良和優(yōu)化。在原文中，作者提出了三點(diǎn)Moravec算子的缺陷并且給出了改良方法：

　　1. Moravec算子對(duì)方向的依賴性太強(qiáng)，在上文中我們可以看到，Moravec算子實(shí)際上只是移動(dòng)了四個(gè)45度角的離散方向，真正優(yōu)秀的檢測(cè)算子應(yīng)該能考慮到各個(gè)現(xiàn)象的移動(dòng)變化情況。為此，作者采用微分的思想（這里不清楚的話可以復(fù)習(xí)下高數(shù)中的全微分）：

　　其中：

　　所以E就可以表示為：

　　2.由于Moravec算子采用的是方形的windows，因此的E的響應(yīng)比較容易受到干擾，Harris采用了一個(gè)較為平滑的窗口——高斯函數(shù)：

　　3.Moravec算子對(duì)邊緣響應(yīng)過于靈敏。為此，Harris提出了對(duì)E進(jìn)行變形：

　　對(duì)，沒錯(cuò)，變成了二次型，果然是大牛，更牛的還在后面！其中，

　　用α，β表示矩陣M的特征值，這樣會(huì)產(chǎn)生三種情況：A 如果α，β都很小，說明高斯windows中的圖像接近平坦。 B 如果一個(gè)大一個(gè)小，則表示檢測(cè)到邊。 C 如果α，β都很大，那么表示檢測(cè)到了角點(diǎn)。

　　α，β表示矩陣M的特征值，這樣會(huì)產(chǎn)生三種情況：

　　A.α，β都很小，說明高斯Windows中的圖像接近平坦

　　B.如果一個(gè)大一個(gè)小，則表示檢測(cè)到邊

　　C.α，β都很大，那么表示檢測(cè)到角點(diǎn)。
?

　　角點(diǎn)響應(yīng)

　　R=det（M）-k*（trace（M）^2） （附錄資料給出k=0.04~0.06，opencv指出是0.05-0.5，浮動(dòng)較大）

　　det（M）=λ1*λ2 trace（M）=λ1+λ2

　　R取決于M的特征值，對(duì)于角點(diǎn)|R|很大，平坦的區(qū)域|R|很小，邊緣的R為負(fù)值。

　　算法步驟

　　其中，局部極大值可用先膨脹后與原圖比較的方法求得，具體見二中源碼。

　　opencv代碼實(shí)現(xiàn)

　　harris類

　　#ifndef HARRIS_H

　　#define HARRIS_H

　　#include “opencv2/opencv.hpp”

　　class harris

　　{

　　private：

　　cv：：Mat cornerStrength; //opencv harris函數(shù)檢測(cè)結(jié)果，也就是每個(gè)像素的角點(diǎn)響應(yīng)函數(shù)值

　　cv：：Mat cornerTh; //cornerStrength閾值化的結(jié)果

　　cv：：Mat localMax; //局部最大值結(jié)果

　　int neighbourhood; //鄰域窗口大小

　　int aperture;//sobel邊緣檢測(cè)窗口大?。╯obel獲取各像素點(diǎn)x，y方向的灰度導(dǎo)數(shù)）

　　double k;

　　double maxStrength;//角點(diǎn)響應(yīng)函數(shù)最大值

　　double threshold;//閾值除去響應(yīng)小的值

　　int nonMaxSize;//這里采用默認(rèn)的3，就是最大值抑制的鄰域窗口大小

　　cv：：Mat kernel;//最大值抑制的核，這里也就是膨脹用到的核

　　public：

　　harris（）：neighbourhood（3），aperture（3），k（0.01），maxStrength（0.0），threshold（0.01），nonMaxSize（3）{

　　};

　　void setLocalMaxWindowsize（int nonMaxSize）{

　　this-》nonMaxSize = nonMaxSize;

　　};

　　//計(jì)算角點(diǎn)響應(yīng)函數(shù)以及非最大值抑制

　　void detect（const cv：：Mat &image）{

　　//opencv自帶的角點(diǎn)響應(yīng)函數(shù)計(jì)算函數(shù)

　　cv：：cornerHarris （image，cornerStrength，neighbourhood，aperture，k）;

　　double minStrength;

　　//計(jì)算最大最小響應(yīng)值

　　cv：：minMaxLoc （cornerStrength，&minStrength，&maxStrength）;

　　cv：：Mat dilated;

　　//默認(rèn)3*3核膨脹，膨脹之后，除了局部最大值點(diǎn)和原來相同，其它非局部最大值點(diǎn)被

　　//3*3鄰域內(nèi)的最大值點(diǎn)取代

　　cv：：dilate （cornerStrength，dilated，cv：：Mat（））;

　　//與原圖相比，只剩下和原圖值相同的點(diǎn)，這些點(diǎn)都是局部最大值點(diǎn)，保存到localMax

　　cv：：compare（cornerStrength，dilated，localMax，cv：：CMP_EQ）;

　　}

　　//獲取角點(diǎn)圖

　　cv：：Mat getCornerMap（double qualityLevel） {

　　cv：：Mat cornerMap;

　　// 根據(jù)角點(diǎn)響應(yīng)最大值計(jì)算閾值

　　threshold= qualityLevel*maxStrength;

　　cv：：threshold（cornerStrength，cornerTh，

　　threshold，255，cv：：THRESH_BINARY）;

　　// 轉(zhuǎn)為8-bit圖

　　cornerTh.convertTo（cornerMap，CV_8U）;

　　// 和局部最大值圖與，剩下角點(diǎn)局部最大值圖，即：完成非最大值抑制

　　cv：：bitwise_and（cornerMap，localMax，cornerMap）;

　　return cornerMap;

　　}

　　void getCorners（std：：vector《cv：：Point》 &points，

　　double qualityLevel） {

　　//獲取角點(diǎn)圖

　　cv：：Mat cornerMap= getCornerMap（qualityLevel）;

　　// 獲取角點(diǎn)

　　getCorners（points， cornerMap）;

　　}

　　// 遍歷全圖，獲得角點(diǎn)

　　void getCorners（std：：vector《cv：：Point》 &points，

　　const cv：：Mat& cornerMap） {

　　for（ int y = 0; y 《 cornerMap.rows; y++ ） {

　　const uchar* rowPtr = cornerMap.ptr《uchar》（y）;

　　for（ int x = 0; x 《 cornerMap.cols; x++ ） {

　　// 非零點(diǎn)就是角點(diǎn)

　　if （rowPtr［x］） {

　　points.push_back（cv：：Point（x，y））;

　　}

　　}

　　}

　　}

　　//用圈圈標(biāo)記角點(diǎn)

　　void drawOnImage（cv：：Mat &image，

　　const std：：vector《cv：：Point》 &points，

　　cv：：Scalar color= cv：：Scalar（255，255，255），

　　int radius=3， int thickness=2） {

　　std：：vector《cv：：Point》：：const_iterator it=points.begin（）;

　　while （it！=points.end（）） {

　　// 角點(diǎn)處畫圈

　　cv：：circle（image，*it，radius，color，thickness）;

　　++it;

　　}

　　}

　　};

　　#endif // HARRIS_H

　　相關(guān)測(cè)試代碼：

　　cv：：Mat image， image1 = cv：：imread （“test.jpg”）;

　　//灰度變換

　　cv：：cvtColor （image1，image，CV_BGR2GRAY）;

　　// 經(jīng)典的harris角點(diǎn)方法

　　harris Harris;

　　// 計(jì)算角點(diǎn)

　　Harris.detect（image）;

　　//獲得角點(diǎn)

　　std：：vector《cv：：Point》 pts;

　　Harris.getCorners（pts，0.01）;

　　// 標(biāo)記角點(diǎn)

　　Harris.drawOnImage（image，pts）;

　　cv：：namedWindow （“harris”）;

　　cv：：imshow （“harris”，image）;

　　cv：：waitKey （0）;

　　return 0;

　　相關(guān)測(cè)試結(jié)果：

　　改進(jìn)的Harris角點(diǎn)檢測(cè)

　　從經(jīng)典的Harris角點(diǎn)檢測(cè)方法不難看出，該算法的穩(wěn)定性和k有關(guān)，而k是個(gè)經(jīng)驗(yàn)值，不好把握，浮動(dòng)也有可能較大。鑒于此，改進(jìn)的Harris方法（）直接計(jì)算出兩個(gè)特征值，通過比較兩個(gè)特征值直接分類，這樣就不用計(jì)算Harris響應(yīng)函數(shù)了。

　　另一方面，我們不再用非極大值抑制了，而選取容忍距離：容忍距離內(nèi)只有一個(gè)特征點(diǎn)。

　　該算法首先選取一個(gè)具有最大 最小特征值的點(diǎn)（即：max（min（e1，e2）），e1，e2是harris矩陣的特征值）作為角點(diǎn)，然后依次按照最大最小特征值順序?qū)ふ矣嘞碌慕屈c(diǎn)，當(dāng)然和前一角點(diǎn)距離在容忍距離內(nèi)的新角點(diǎn)唄忽略。

　　opencv測(cè)試該算法代碼如下：

　　cv：：Mat image， image1 = cv：：imread （“test.jpg”）;

　　//灰度變換

　　cv：：cvtColor （image1，image，CV_BGR2GRAY）;

　　// 改進(jìn)的harris角點(diǎn)檢測(cè)方法

　　std：：vector《cv：：Point》 corners;

　　cv：：goodFeaturesToTrack（image，corners，

　　200，

　　//角點(diǎn)最大數(shù)目

　　0.01，

　　// 質(zhì)量等級(jí)，這里是0.01*max（min（e1，e2）），e1，e2是harris矩陣的特征值

　　10）;

　　// 兩個(gè)角點(diǎn)之間的距離容忍度

　　harris（）.drawOnImage（image，corners）;//標(biāo)記角點(diǎn)

　　測(cè)試結(jié)果如下：

　　FAST角點(diǎn)檢測(cè)

　　算法原理比較簡(jiǎn)單，但實(shí)時(shí)性很強(qiáng)。

　　該算法的角點(diǎn)定義為：若某像素點(diǎn)圓形鄰域圓周上有3/4的點(diǎn)和該像素點(diǎn)不同（編程時(shí)不超過某閾值th），則認(rèn)為該點(diǎn)就是候選角點(diǎn)。opencv更極端，選用半徑為3的圓周上（上下左右）四個(gè)點(diǎn)，若超過三個(gè)點(diǎn)和該像素點(diǎn)不同，則該點(diǎn)為候選角點(diǎn)。

　　和Harris算法類似，該算法需要非極大值抑制。

　　opencv代碼：

　　cv：：Mat image， image1 = cv：：imread （“test.jpg”）;

　　cv：：cvtColor （image1，image，CV_BGR2GRAY）;

　　//快速角點(diǎn)檢測(cè)

　　std：：vector《cv：：KeyPoint》 keypoints;

　　cv：：FastFeatureDetector fast（40，true）;

　　fast .detect （image，keypoints）;

　　cv：：drawKeypoints （image，keypoints，image，cv：：Scalar：：all（255），cv：：DrawMatchesFlags：：DRAW_OVER_OUTIMG）;

　　測(cè)試結(jié)果如下：

　　關(guān)于矩陣知識(shí)的一點(diǎn)補(bǔ)充：好長(zhǎng)時(shí)間沒看過線性代數(shù)的話，這一段比較難理解?？梢钥吹組是實(shí)對(duì)稱矩陣，這里簡(jiǎn)單溫習(xí)一下實(shí)對(duì)稱矩陣和二次型的一些知識(shí)點(diǎn)吧。

　　1. 關(guān)于特征值和特征向量：

　　特征值的特征向量的概念忘了就自己查吧，這里只說關(guān)鍵的。對(duì)于實(shí)對(duì)稱矩陣M（設(shè)階數(shù)為n），則一定有n個(gè)實(shí)特征值，每個(gè)特征值對(duì)應(yīng)一組特征向量（這組向量中所有向量共線），不同特征值對(duì)應(yīng)的特征向量間相互正交；（注意這里說的是實(shí)對(duì)稱矩陣，不是所有的矩陣都滿足這些條件）

　　2. 關(guān)于對(duì)角化：

　　對(duì)角化是指存在一個(gè)正交矩陣Q，使得 Q’MQ 能成為一個(gè)對(duì)角陣（只有對(duì)角元素非0），其中Q’是Q的轉(zhuǎn)置（同時(shí)也是Q的逆，因?yàn)檎痪仃嚨霓D(zhuǎn)置就是其逆）。一個(gè)矩陣對(duì)角化后得到新矩陣的行列式和矩陣的跡（對(duì)角元素之和）均與原矩陣相同。如果M是n階實(shí)對(duì)稱矩陣，則Q中的第 j 列就是第 j 個(gè)特征值對(duì)應(yīng)的一個(gè)特征向量（不同列的特征向量?jī)蓛烧唬?/p>

　　3. 關(guān)于二次型：

　　對(duì)于一個(gè)n元二次多項(xiàng)式，f（x1，x2.。。.xn） = ∑ （ aij*xi*xj ） ，其中 i 和 j 的求和區(qū)間均為 ［1，n］ ，

　　可將其各次的系數(shù) aij 寫成一個(gè)n*n矩陣M，由于 aij 和 aji 的對(duì)稱等價(jià)關(guān)系，一般將 aij 和 aji 設(shè)為一樣的值，均為 xi*xj 的系數(shù)的二分之一。這樣，矩陣M就是實(shí)對(duì)稱矩陣了。即二次型的矩陣默認(rèn)都是實(shí)對(duì)稱矩陣

　　4. 關(guān)于二次型的標(biāo)準(zhǔn)化（正交變換法）：

　　二次型的標(biāo)準(zhǔn)化是指通過構(gòu)造一個(gè)n階可逆矩陣 C，使得向量 （ x1，x2.。.xn ） = C * （y1，y2.。.yn），把n維向量 x 變換成n維向量 y ，并代入f（x1，x2.。。.xn） 后得到 g（y1，y2.。.yn），而后者的表達(dá)式中的二次項(xiàng)中不包含任何交叉二次項(xiàng) yi*yj（全部都是平方項(xiàng) yi^2），也即表達(dá)式g的二次型矩陣N是對(duì)角陣。用公式表示一下 f 和 g ，（下面的表達(dá)式中 x 和 y都代表向量，x‘ 和 y’ 代表轉(zhuǎn)置）

　　f = x‘ * M * x ;

　　g = f = x’ * M * x = （Cy）‘ * M * （Cy） = y’ * （C‘MC） * y = y’ * N * y ;

　　因此 C‘MC = N。正交變換法，就是直接將M對(duì)角化得到N，而N中對(duì)角線的元素就是M的特征值。正交變換法中得到的 C 正好是一個(gè)正交矩陣，其每一列都是兩兩正交的單位向量，因此 C 的作用僅僅是將坐標(biāo)軸旋轉(zhuǎn)（不會(huì)有放縮）。

　　OK，基礎(chǔ)知識(shí)補(bǔ)充完了，再來說說Harris角點(diǎn)檢測(cè)中的特征值是怎么回事。這里的 M 是

　　將M對(duì)角化后得到矩陣N，他們都是2階矩陣，且N的對(duì)角線元素就是本文中提到的 α 和 β。

　　本來 E（x，y） = A*x^2 + 2*C*x*y + B*y^2 ，而將其標(biāo)準(zhǔn)后得到新的坐標(biāo) xp和yp，這時(shí)表達(dá)式中就不再含有交叉二次項(xiàng)，新表達(dá)式如下：

　　E（x，y） = Ep （xp，yp） = α*xp^2 + β*yp^2，

　　我們不妨畫出 Ep （xp，yp） = 1 的等高線L ，即

　　α*xp^2 + β*yp^2 = 1 ，

　　可見這正好是（xp，yp）空間的一個(gè)橢圓，而α 和 β則分別是該橢圓長(zhǎng)、短軸平方的倒數(shù)（或者反過來），且長(zhǎng)短軸的方向也正好是α 和 β對(duì)應(yīng)的特征向量的方向。由于（x，y）空間只是 （xp，yp）空間的旋轉(zhuǎn)，沒有放縮，因此等高線L在（x，y）空間也是一個(gè)全等的橢圓，只不過可能是傾斜的。

　　現(xiàn)在就能理解下面的圖片中出現(xiàn)的幾個(gè)橢圓是怎么回事了，圖（a）中畫的正是高度為 1 的等高線，（其他”高度“處的等高線也是橢圓，只不過長(zhǎng)短軸的長(zhǎng)度還要乘以一個(gè)系數(shù)）。其他的幾幅圖片中可以看到，“平坦”區(qū)域由于（高度）變化很慢，等高線（橢圓）就比較大；而”邊緣“區(qū)域則是在一個(gè)軸向上高度變化很快，另一個(gè)與之垂直的軸向上高度變化很慢，因此一個(gè)軸很長(zhǎng)一個(gè)軸很短；“角點(diǎn)”區(qū)域各個(gè)方向高度都變化劇烈，因此橢圓很小。我們?nèi)搜劭梢灾庇^地看到橢圓的大小胖瘦，但如何讓計(jì)算機(jī)識(shí)別這三種不同的幾何特征呢？為了能區(qū)分出角點(diǎn)、邊緣和平坦區(qū)域我們現(xiàn)在需要用α 和 β構(gòu)造一個(gè)特征表達(dá)式，使得這個(gè)特征式在三種不同的區(qū)域有明顯不同的值。一個(gè)表現(xiàn)還不錯(cuò)的特征表達(dá)式就是：

　　（αβ） - k（α+β）^2

　　表達(dá)式中的 k 的值怎么選取呢？它一般是一個(gè)遠(yuǎn)小于 1 的系數(shù)，opencv的默認(rèn)推薦值是 0.04（=0.2的平方），它近似地表達(dá)了一個(gè)閾值：當(dāng)橢圓短、長(zhǎng)軸的平方之比（亦即α 和 β兩個(gè)特征值之比）小于這個(gè)閾值時(shí)，認(rèn)為該橢圓屬于“一個(gè)軸很長(zhǎng)一個(gè)軸很短”，即對(duì)應(yīng)的點(diǎn)會(huì)被認(rèn)為是邊緣區(qū)域。

　　對(duì)于邊緣部分，（假設(shè)較大的特征值為β）由于 β》》α且α《kβ，因此特征式 ：

　　（αβ） - k（α+β）^2 ≈ αβ - kβ^2 《 （kβ）β - kβ^2 = 0

　　即邊緣部分的特征值小于0 ；

　　對(duì)于非邊緣部分，α 和 β相差不大，可認(rèn)為 （α+β）^2 ≈ 4αβ，因此特征式：

　?。é力拢?- k（α+β）^2 ≈ αβ - 4kαβ = （ 1 - 4k ） * αβ

　　由于 k 遠(yuǎn)小于1，因此 1 - 4k ≈ 1，這樣特征式進(jìn)一步近似為：

　?。é力拢?- k（α+β）^2 ≈ αβ

　　在角點(diǎn)區(qū)域，由于α 和 β都較大，對(duì)應(yīng)的特征式的值也就很大；而在平坦區(qū)域，特征式的值則很小。

　　因此，三種不同區(qū)域的判別依據(jù)就是： 如果特征表達(dá)式的值為負(fù)，則屬于邊緣區(qū)域；如果特征表達(dá)式的值較大，則屬于角點(diǎn)區(qū)域；如果特征表達(dá)式的值很小，則是平坦區(qū)域。

　　最后，由于αβ和（α+β）正好是M對(duì)角化后行列式和跡，再結(jié)合上面補(bǔ)充的基礎(chǔ)知識(shí)第2條中提到的行列式和跡在對(duì)角化前后不變，就可以得到 （αβ） - k（α+β）^2 = det（M） - k*Tr（M）^2，這就是Harris檢測(cè)的表達(dá)式。