SIFT特徵

在不同影像上進行特徵匹配時,常會遇到尺度變化的問題,也就是要分析的物體,可能在不同張影像的大小是不同的,當我們實際上要進行匹配時,由於尺度的差異,同個物體的特徵並不會匹配。

為了解決這個問題,有些算法用來尋找尺度不變的特徵,主要是基於每個檢測到的特徵點都伴隨著對應的尺寸,這邊介紹一種尺度不變的特徵,SIFT(Scale-Invariant Feature Transform)特徵,和另一個著名的尺度不變特徵檢測器SURF(Speeded Up Robust Features)相比,SURF速度較快,SIFT搜尋的特徵較準確。


以下使用程式碼使用SiftFeatureDetector找到影像的SURF特徵,接著用drawKeyPoints()劃出特徵點,旗標使用DRAW_RICH_KEYPOINTS,可看出圓圈的尺寸與特徵的尺度成正比,同時由於SURF算法將方向與每個特徵作關聯,使得特徵具有旋轉無關性:


影像匹配除了需要檢測圖像的特徵點,還需要向量來描述特徵才能進行比較,OpenCV裡使用SiftDescriptorExtractor來得到特徵點的SIFT描述子,描述子是一個Mat,行數與特徵點個數相同,每行都是一個N維的特徵向量,SIFT的描述子維度為128,特徵向量描述特徵點周圍的強度樣式,兩個特徵點越類似,特徵向量的距離越近。

假使我們想匹配在不同圖像的兩個相同物體,首先取得每個圖像的特徵,然後提取他們的描述子,將第一幅圖像和第二幅圖像中的每個特徵向量做比較,距離最近的特徵向量即為那個特徵的最佳匹配,對第一幅圖像的所有特徵都進行此處理,這也是BruteForceMatcher所採用的方法。

以下範例使用SIFT演算法檢測特徵點,並呼叫drawMatches()看特徵點的匹配情形:

SURF特徵

在不同影像上進行特徵匹配時,常會遇到尺度變化的問題,也就是要分析的物體,可能在不同張影像的大小是不同的,當我們實際上要進行匹配時,由於尺度的差異,同個物體的特徵並不會匹配。

為了解決這個問題,有些算法用來尋找尺度不變的特徵,主要是基於每個檢測到的特徵點都伴隨著對應的尺寸,這邊介紹一種尺度不變的特徵,SURF(Speeded Up Robust Features)特徵,不僅具有尺度和旋轉的不變性,而且非常高效,和另一個著名的尺度不變特徵檢測器SIFT(Scale-Invariant Feature Transform))相比,SURF速度較快,SIFT搜尋的特徵較準確。


以下使用程式碼使用SurfFeatureDetector找到影像的SURF特徵,接著用drawKeyPoints()劃出特徵點,旗標使用DRAW_RICH_KEYPOINTS,可看出圓圈的尺寸與特徵的尺度成正比,同時由於SURF算法將方向與每個特徵作關聯,使得特徵具有旋轉無關性:


影像匹配除了需要檢測圖像的特徵點,還需要向量來描述特徵才能進行比較,OpenCV裡使用SurfDescriptorExtractor來得到特徵點的SURF描述子,描述子是一個Mat,行數與特徵點個數相同,每行都是一個N維的特徵向量,SURF的默認維度為64,特徵向量描述特徵點周圍的強度樣式,兩個特徵點越類似,特徵向量的距離越近。

假使我們想匹配在不同圖像的兩個相同物體,首先取得每個圖像的特徵,然後提取他們的描述子,將第一幅圖像和第二幅圖像中的每個特徵向量做比較,距離最近的特徵向量即為那個特徵的最佳匹配,對第一幅圖像的所有特徵都進行此處理,這也是BruteForceMatcher所採用的方法。

以下範例使用SURF演算法檢測特徵點,並呼叫drawMatches()看特徵點的匹配情形:

FAST特徵

Harris算法提出了搜尋角點(或者說是特徵點)的方式,基於兩個正交方向上的強度變化率,能夠得到不錯的結果,但由於需要耗時的計算影像的一階微分,而特徵點檢測通常只是整個複雜算法的第一步,所以這邊另外介紹FAST檢測器,正如名字所示,此算法能快速進行檢測,依賴較少像素來確定是否為特徵點。

FAST(Features from Accelerated Segment Test)算法,和Harris算法同樣要定義甚麼是角點,FAST的角點定義基於和周圍像素的強度關係,檢查候選像素周圍一圈的像素,與中心點差異較大的像素如果組成連續的圓弧,並且弧長大於圓周長的3/4,那麼就把這個點視為特徵點。

FAST算法使用額外的技巧進行加速,一開始先測試周圍圓上被90分割的四個點,比如說測試點的上、下、左、右四個像素,因為滿足FAST對角點的定義,則這四個點至少有三個和中心點的強度差異須大於閾值,實務上大部分的像素都可用這方法進行移除,因此使用上非常高效,原則上測試上的半徑應該是一個參數,實際上半徑為3可以兼顧結果及效率。

和Harris找角點相同,可以在找到的角點上執行非極大值抑制,而由於FAST算法能快速的檢測特徵點,在對執行速度要求的環境下,比如在高FPS的影片上進行視覺跟蹤時,此時可以考慮用FAST來搜尋特徵點。

Harris 角點

在影像中檢測特徵點時,角點可以做為一個重要的參考,因為角點是兩條邊緣的交點處,可以被精確定位,這和位於相同強度的區域不同,與物體輪廓的點也不同,輪廓點難以在其他影像的相同物體進行精確定位。

Harris特徵檢測器是一個經典的角點檢測方法,OpenCV使用cornerHarris()實現Harris角點偵測演算法,輸出結果為浮點數類型的影像,每個像素值為相對位置的角點強度,之後再用閾值進行二值化即可得到角點。


OpenCV Harris角點檢測

void cornerHarris(InputArray src, OutputArray dst, int blockSize, int ksize, double k, int borderType=BORDER_DEFAULT)

  • src:輸入圖,8位元或浮點數單通道圖。
  • dst:輸出圖,儲存Harris檢測結果,型態為CV_32FC1,尺寸和輸入圖相同。
  • blockSize:相鄰像素的尺寸。
  • ksize:Sobel算子的濾波器模板大小。
  • k:Harris參數,即為下面方程式的k值。
  • borderType:邊緣擴充方式。

為了偵測影像中的角點,Harris觀察一個假定點周圍小窗口內強度差的平方和,窗口大小為cornerHarris()的第三個參數blockSize,因為無法確定高強度變化的方向,因此在所有可能的方向計算,過程首先獲得強度變化最大的方向,接著檢查它垂直方向的變化是否也很強烈,同時滿足的話便是一個角點。

小窗口強度差平方和:

Harris

用泰勒展開式對算式進行近似:

Harris

對算式化簡:

eHarris

轉換成矩陣型式:

Harris

矩陣M是一個斜方差(Covariance)矩陣,代表所有方向上的強度變化率,矩陣內的一階微分通常是Sobel算子計算結果,cornerHarris()的第四個參數ksize為Sobel的模板尺寸,斜方差矩陣的特徵值,代表最大強度變化以及和它垂直的方向,如果這兩個特徵值都低,代表此點位於變化不大的區域,要是其中一個較高另一個較低,代表此點位於邊上,如果兩個特徵值都較高,代表此點位於角點上。所以我們尋找角點的方式就是擁有超過閾值的斜方差矩陣特徵值:

Harris Harris

用下式驗證兩個特徵值是否足夠高,當兩個特徵值都高時,此計算結果也高,這也是cornerHarris()在每個位置得到的分數,k的值為cornerHarris()的第五個參數,實務上通常在0.05~0.5之間能得到滿意的結果: Harris

以下我們用cornerHarris()得到harris的分數,接著自定義閾值求出原始圖的角點:

#include <cstdio>
#include <opencv2/opencv.hpp>
using namespace cv;

int main(){
    Mat src = imread("church.jpg",CV_LOAD_IMAGE_GRAYSCALE);
    Mat harrisStrength;
    cornerHarris(src, harrisStrength, 3, 3, 0.01);
    Mat corners;
    double thres = 0.0001;
    threshold(harrisStrength, corners, thres, 255, THRESH_BINARY);

    imshow("原始圖", src);
    imshow("角點圖", corners);
    waitKey(0);
    return 0;
}

由上面結果可看出,實際呼叫cornerHarris()找角點時,偵測的結果可能在鄰近區域內有許多角點,而不容易進行精確定位,以下程式碼對Harris結果進行改進,角點不只需要結果高於閾值,還必須為局部最大值。所以對Harris結果圖進行膨脹,膨脹運算只有在局部最大值的地方維持原值,之後輸出結果為維持原值的位置才是角點,以下為詳細的程式碼:


關於特徵點聚集的問題,除了用局部極大值的方式,也可以指定兩個特徵點的最小距離,OpenCV另外有goodFeaturesToTrack(),從Harris得分最高的點開始,僅接受距離大於最小允許距離的特徵點,檢測的結果可用於視覺跟蹤的特徵集合。

支撐向量機(SVM)

機器學習(Machine Learning)主要是設計算法,讓電腦能透過資料而有像人類的學習行為,算法通常是自動分析數據,獲得規律,並利用規律對未知數據進行預測,進而達到分類、回歸分析等目的,在影像處理上則可能是影像辨識。

依據輸入資料是否有標籤,我們分監督式學習和非監督式學習,資料有標籤的為監督式學習,沒有標籤的為非監督式學習,舉例來說,假如輸入臉的輪廓,輪廓本身沒有標籤,但加入每個輪廓年齡多少這個資料就是標籤。

這邊介紹支撐向量機SVM(Support Vector Machine),這是一種監督式的機器學習算法,原先用於二元分類,比如說這封郵件是否為垃圾郵件,或是這個人是男是女,這種二個類別的問題,但現在已擴展且廣泛應用於統計分類和回歸分析。

SVM建構多維的超平面來分類資料點,這個超平面即為分類邊界,直觀來說,好的分類邊界要距離最近的訓練資料點越遠越好,因為這樣可以減低判斷錯誤的機率,而SVM的目標即為找出間隔最大的超平面來作為分類邊界,下面為SVM的示意圖,綠線為分類邊界,分類邊界與最近的訓練資料點之間的距離稱為間隔(margin)。

SVM


以下我們示範OpenCV SVM的使用方式,大概可分以下幾個步驟:

  1. 在空間中選擇六個點作為輸入資料。
  2. 給這些點相對的標籤,對輸入資料進行分類。
  3. 設置CvSVMParams作為SVM的參數。
  4. 將資料和參數輸入SVM::train(),進行訓練後即可求得分類邊界。
  5. 之後可輸入新的資料,由SVM::predict()看此筆資料屬於哪一類。

以下為實際程式碼:

# include <cstdio>
# include <opencv2/opencv.hpp>   
# include <vector> 
using namespace cv;

int main(){ 
    int width = 300; 
    int height = 300; 
    Mat image = Mat::zeros(height, width, CV_8UC3); 

    float trainingData[6][2] = {{250,250},{200,100},{260,180},{140,10},{30,70},{50,50}};
    Mat trainingDataMat(6, 2, CV_32FC1, trainingData);

    float labels[6] = {1.0, 1.0, 1.0, -1.0, -1.0, -1.0}; 
    Mat labelsMat(6, 1, CV_32FC1, labels);

    CvSVMParams params;
    params.svm_type    = CvSVM::C_SVC;
    params.kernel_type = CvSVM::LINEAR;
    params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);

    CvSVM SVM;
    SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);
    Vec3b green(0,255,0), red (0,0,255);
    for (int i=0; i<image.rows; ++i){
        for (int j=0; j<image.cols; ++j){
            Mat sampleMat = (Mat_<float>(1,2) << j,i);
            float response = SVM.predict(sampleMat);

            if(response == 1){
                image.at<Vec3b>(i,j)=green;
            }
            else if(response == -1){
                image.at<Vec3b>(i,j)=red;
            }
        }
    }
    circle(image, Point(250, 250), 3, Scalar(0, 0, 0));
    circle(image, Point(200, 100), 3, Scalar(0, 0, 0));
    circle(image, Point(260, 180), 3, Scalar(0, 0, 0));
    circle(image, Point(140, 10), 3, Scalar(255, 255, 255));
    circle(image, Point(30, 70), 3, Scalar(255, 255, 255));
    circle(image, Point(50, 50), 3, Scalar(255, 255, 255));

    imshow("SVM示範", image); 
    waitKey(0);

    return 0;
}

SVM


有時因為資料的關係,無法取得完美的分類邊界,以下示範如何用SVM取得相對好的分類邊界,使用方式和上述例子差不多:

#include <cstdio>
#include <opencv2/opencv.hpp>
#include <vector>
using namespace cv;

int main(){ 
    int width = 300; 
    int height = 300; 
    Mat I = Mat::zeros(height, width, CV_8UC3); 
    Mat trainData(100, 2, CV_32FC1); 
    Mat labels (100, 1, CV_32FC1);

    //設100個隨機點
    RNG rng;
    for(int i=0; i<50; i++){
        labels.at<float>(i,0) = 1.0;
        int tempY = rng.uniform(0,299);
        int tempX = rng.uniform(0,170);
        trainData.at<float>(i,0) = tempX;
        trainData.at<float>(i,1) = tempY;
    }
    for(int i=50; i<99; i++){
        labels.at<float>(i,0) = -1.0;
        int tempY = rng.uniform(0,299);
        int tempX = rng.uniform(130,299);
        trainData.at<float>(i,0) = tempX;
        trainData.at<float>(i,1) = tempY;
    }

    CvSVMParams params;
    params.svm_type    = SVM::C_SVC;
    params.C           = 0.1;
    params.kernel_type = SVM::LINEAR;
    params.term_crit   = TermCriteria(CV_TERMCRIT_ITER, (int)1e7, 1e-6);
    CvSVM svm;
    svm.train(trainData, labels, Mat(), Mat(), params);

    Vec3b green(0,100,0), blue (100,0,0);
    for (int i = 0; i < I.rows; ++i){
        for (int j = 0; j < I.cols; ++j){
            Mat sampleMat = (Mat_<float>(1,2) << i, j);
            float response = svm.predict(sampleMat);
            if(response == 1){
                I.at<Vec3b>(j, i)=green;
            }
            else if (response == 2){
                I.at<Vec3b>(j, i)=blue;
            }
        }
    }

    float px, py;
    for (int i=0; i<50; ++i){
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point((int)px, (int)py), 3, Scalar(0, 0, 255));
    }
    for (int i=50; i<100; ++i){
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point((int)px, (int)py), 3, Scalar(255, 255,0));
    }

    imshow("SVM示範", I); 
    waitKey(0);
    return 0;
}

SVM

繼續閱讀 支撐向量機(SVM)

特徵

特徵提取

電腦不認識圖像,只知道數值,為了使電腦能夠像人類的視覺一樣,透過觀察理解圖像,我們研究如何從圖像的像素值,抽取有用的數據或訊息,來描述這個圖像或物體,這個過程就是特徵提取,這些描述就是所謂的特徵,我們可以透過這些特徵,通過訓練來讓電腦如何懂得這些特徵。


特徵

特徵是某個物體或圖像,能夠和其他物體或圖像區分的特點或特性,或是這些特點或特性的集合,有一些是透過像素值,很直接就能得到的,比如說強度、邊緣、顏色等,有些是要透過變換或計算才能得到的,比如說矩(moment)、直方圖、主成分等,這概念用於物體識別、影像匹配、視覺跟蹤等。


特徵向量

我們常將一類對象的單個或多種特性結合起來,形成一個特徵向量來表示這個對象,如果只有一個特徵,則特徵向量為一維向量,如果是n個特性的組合,則為n維向量,我們可把特徵向量想成是空間中的一個點,n個特徵就是在n維空間的一個點,而分類的行為就是對這個空間的一種劃分。


描述方式

經過圖像分割得到感興趣的區域之後,以下為一些常用來描述的特徵,通常會將這些組合成特徵向量以供分類使用:

  1. 周長:區域邊界上的像素數目。
  2. 面積:區域的像素總數。
  3. 質心位置。
  4. 平均強度:區域所有像素的平均值。
  5. 包含區域的最小矩形。
  6. 最大強度。
  7. 最小強度。
  8. 大於或小於平均強度的個數。