Surf算法

前期看了許久的sift算法，總算是有些了解了過程。對于具體算法的一些實現，仍舊是不太明白。對于kd樹的建立，和匹配依舊是自己不想寫算法，而是利用已經寫好的算法做個小實驗。vlfeat算法，有實現好的帶有匹配的sift算法嗎？有知道的童鞋們嗎？告知~

正文開始：

surf借鑒了sift中簡化近似的思想，將DOH中的高斯二階微分模板進行了近似簡化，使得模板對圖像的濾波只需要進行幾個簡單的加減法運算，并且，這種運算與濾波模板的尺寸有關。實驗證明surf算法較sift算法在運算速度上要快3倍左右。

1 積分圖像

surf算法中要用到積分圖像的概念。借助積分圖像，圖像與高斯二階微分模板的濾波轉化為對積分圖像的加減運算。積分圖像（Integral Image）的概念是由viola和Jones提出來的，而將類似積分圖像用于盒子濾波是由Simard等人提出。

積分圖像中任意一點（i,j）的值為ii(i,j)為原圖像左上角到任意點（i,j）相應的對角線區域灰度值的總和即：

公式中，I(x`,y`)表示原圖像中點（i`,j`）的灰度值，ii（x,y）可以由下面兩公式迭代計算得到：

公式中，S（x,y）表示一列的積分，且S（i,-1）=0,ii(-1,j)=0.求積分圖像，只需對原圖像的所有像素素進行一遍掃描。下面的代碼為c++語言的實現

pOutImage[0][0] = pInImage[0][0];

for(int x = 1, x < nWidth; i++)
{
  pOutImage[x][0] = pInImage[x-1][0] + pInImage[x][0];

}

for(int y=1; y< nHeight ;y++)
{
  int nSum = 0;

  for(int x=0; x < nWidth;x++)
  {
    nSum = pInImage[x][y];

    pOutImage[x][y]= pInImage[x][y-1]+nSum;
  }

}

如圖表示，在求取窗口w內的像元灰度和時，不管窗口W的大小如何，均可利用積分圖像的4個對應點（i1,j1）（i2,j2）（i3,j3）（i4,j4）的值計算的到。也就是說，求取窗口W內的像元灰度和與窗口的尺寸是無關的。窗口W內的像元的灰度和為

Sum（W）= ii(i4,j4) -ii(i2,j2) - ii(i3,j3) + ii(i1,j1)

下面看以截圖，相信都可以看懂

關于矩形區域內像素點的求和應該是一種簡單重復性運算，采用這種思路總體上提高了效率。為什么這么說呢？假設一幅圖片共有n個像素點，則計算n個位置的積分圖總共的加法運算有n-1次（注意：可不是次哦，要充分利用遞推思想），將這些結果保存在一個跟原圖對應的矩陣M中。當需要計算圖像中某個矩形區域內的所有像素之和是直接像查表一樣，調出A,B,C,D四點的積分圖值，簡單的加減法（注意只需要三次哦）即可得到結果。反之，如果采用naive的方式直接在原圖像中的某個矩形區域內求和，你想想，總共可能的矩形組合有多少？ ！！且對于一幅圖像n那是相當大啊，所以2^n

 那可是天文數字，而且這里面絕大部分的矩形有重疊，重疊意味著什么？在算求和的時候有重復性的工作，其實我們是可以有效的利用已經計算過的信息的。這就是積分圖法的內在思想：它實際上是先計算n個互不重疊（專業點說是不相交）的矩形區域內的像素點求和，充分利用這些值（已有值）計算未知值，有點類似遞推的味道...這就完全避免了重復求和運算。

 這樣就可以進行2種運算：

    （1）任意矩形區域內像素積分。由圖像的積分圖可方便快速地計算圖像中任意矩形內所有像素灰度積分。如下圖2.3所示，點1的積分圖像ii1的值為(其中Sum為求和) :

    ii1=Sum（A）

    同理，點2、點3、點4的積分圖像分別為：

    ii2=Sum(A)+Sum(B);      ii3=Sum(A)+Sum(C);    ii4=Sum(A)+Sum(B)+Sum(C)+Sum(D);

    矩形區域D內的所有像素灰度積分可由矩形端點的積分圖像值得到:

                   Sum(D)=ii1+ii4-(ii2+ii3)            (1)

(2) 特征值計算
    矩形特征的特征值是兩個不同的矩形區域像素和之差，由(1)式可以計算任意矩形特征的特征值，下面以圖2.1中特征原型A為例說明特征值的計算。

   
    如圖2.4 所示，該特征原型的特征值定義為:

    Sum（A）-Sum（B）

    根據（1）式則有：Sum(A)=ii4+ii1-(ii2+ii3);    Sum(B)=ii6+ii3-(ii4+ii5);

   所以此類特征原型的特征值為:

                (ii4-ii3)-(ii2-ii1)+(ii4-ii3)-(ii6-ii5)

   另示：運用積分圖可以快速計算給定的矩形之所有象素值之和Sum(r)。假設r=(x,y,w,h),那么此矩形內部所有元素之和等價于下面積分圖中下面這個式子:

                 Sum(r) = ii(x+w,y+h)+ii(x-1,y-1)-ii(x+w,y-1)-ii(x-1,y+h)

   由此可見，矩形特征特征值計算只與此特征端點的積分圖有關，而與圖像坐標值無關。對于同一類型的矩形特征，不管特征的尺度和位置如何，特征值的計算所耗費的時間都是常量，而且都只是簡單的加減運算。其它類型的特征值計算方法類似