寻找角点

在视频跟踪中，有多种局部特征可以用来跟踪。我们可以想象，如果视频背景是一张白纸，此时我们很难在下一个视频帧中找到上个视频帧中的某一点。如果，此时的背景是一张有一个黑点的白纸，那么在下一个视频中，这个黑点很容易被找到。简而言之，角点就是这个黑点。当然在实际视频处理中，角点往往不是这么清晰的容易找到。一般来说，如果某个点在两个正交的方向上都有明显的导数，则认为该点是这张视频帧中独一无二的点，也即角点。

在OpenCV中，函数cvGoodFeaturesToTrack()采用了Shi和Tomasi提出的方法，先利用sobel算子计算二阶导数，再计算特征值，它返回满足易于跟踪的一系列角点。函数定义如下：

GoodFeaturesToTrack
确定图像的强角点
void cvGoodFeaturesToTrack( const CvArr* image, CvArr* eig_image, CvArr* temp_image,
                            CvPoint2D32f* corners, int* corner_count,
                            double quality_level, double min_distance,
                            const CvArr* mask=NULL );
image
输入图像，8-位或浮点32-比特，单通道
eig_image
临时浮点32-位图像，尺寸与输入图像一致
temp_image
另外一个临时图像，格式与尺寸与 eig_image 一致
corners
输出参数，检测到的角点
corner_count
输出参数，检测到的角点数目
quality_level
最大最小特征值的乘法因子。定义可接受图像角点的最小质量因子。
min_distance
限制因子。得到的角点的最小距离。使用 Euclidian 距离
mask
ROI:感兴趣区域。函数在ROI中计算角点，如果 mask 为 NULL，则选择整个图像。 必须为单通道的灰度图，大小与输入图像相同。mask对应的点不为0，表示计算该点。
函数 cvGoodFeaturesToTrack 在图像中寻找具有大特征值的角点。该函数，首先用cvCornerMinEigenVal 计算输入图像的每一个象素点的最小特征值，并将结果存储到变量 eig_image 中。然后进行非最大值抑制（仅保留3x3邻域中的局部最大值）。下一步将最小特征值小于 quality_level•max(eig_image(x,y)) 排除掉。最后，函数确保所有发现的角点之间具有足够的距离，（最强的角点第一个保留，然后检查新的角点与已有角点之间的距离大于 min_distance ）。

注意：函数cvGoodFeaturesToTrack()的输出结果为角点的位置数组。

如果在实际的操作中，需要精度更高的角点坐标，此时仅仅得到像素点位置就不够了，需要得到其物理位置。这个位置成为亚像素点（或精确角点），subPix。

得到该点的OpenCV函数为：FindCornerSubPix，具体定义如下：

FindCornerSubPix

精确角点位置

void cvFindCornerSubPix( const CvArr* image, CvPoint2D32f* corners,
                         int count, CvSize win, CvSize zero_zone,
                         CvTermCriteria criteria );

image

输入图像.

corners

输入角点的初始坐标，也存储精确的输出坐标

count

角点数目

win

搜索窗口的一半尺寸。如果 win=(5,5) 那么使用 5*2+1 × 5*2+1 = 11 × 11 大小的搜索窗口

zero_zone

死区的一半尺寸，死区为不对搜索区的中央位置做求和运算的区域。它是用来避免自相关矩阵出现的某些可能的奇异性。当值为 (-1,-1) 表示没有死区。

criteria

求角点的迭代过程的终止条件。即角点位置的确定，要么迭代数大于某个设定值，或者是精确度达到某个设定值。 criteria 可以是最大迭代数目，或者是设定的精确度，也可以是它们的组合。

函数 cvFindCornerSubPix 通过迭代来发现具有子象素精度的角点位置，或如图所示的放射鞍点（radial saddle points）。

子象素级角点定位的实现是基于对向量正交性的观测而实现的，即从中央点q到其邻域点p 的向量和p点处的图像梯度正交（服从图像和测量噪声）。考虑以下的表达式：

εi=DIpiT•(q-pi)

其中，DIpi表示在q的一个邻域点pi处的图像梯度，q的值通过最小化εi得到。通过将εi设为0，可以建立系统方程如下：

sumi(DIpi•DIpiT)•q - sumi(DIpi•DIpiT•pi) = 0

其中q的邻域（搜索窗）中的梯度被累加。调用第一个梯度参数G和第二个梯度参数b，得到：

q=G-1•b

该算法将搜索窗的中心设为新的中心q，然后迭代，直到找到低于某个阈值点的中心位置。

PS:

继Harris提出角点以及后来的Shi个Tomasi提出角点后，许多其他类型的角点和相关局部特征也被提出来。SIFI（Scale-invariant Feature Transform）是其中应用比较广泛的类型。SIFI具有缩放不变个旋转不变的特性。目前，OpenCV没有专门的实现该特征的函数。参考文献1指出，利用OpenCV现有函数，可以实现计算机视觉领域参考文献提出的绝大部分算法（特征）。

PS：

具体实现代码（转自文献3）：

#include "cv.h"
#include "highgui.h"
#include "stdio.h"
#include "iostream.h"

#define max_corners 80

int main( )
{
        IplImage *srcImage = 0, *grayImage = 0, *corners1 = 0, *corners2 = 0;


    int cornerCount=max_corners;
    CvPoint2D32f corners[max_corners];
    double qualityLevel;
    double minDistance;


     CvScalar color = CV_RGB(255,0,0);
    
    cvNamedWindow( "image", 0 ); 
   
    srcImage = cvLoadImage("Chess.bmp", 1);
    
    grayImage = cvCreateImage(cvGetSize(srcImage), IPL_DEPTH_8U, 1);
    
    cvCvtColor(srcImage, grayImage, CV_BGR2GRAY);
    
    corners1= cvCreateImage(cvGetSize(srcImage), IPL_DEPTH_32F, 1);
    corners2= cvCreateImage(cvGetSize(srcImage),IPL_DEPTH_32F, 1);
    
    cvGoodFeaturesToTrack (grayImage, corners1, corners2, corners,
        &cornerCount, 0.05, 5, 0);
    
    printf("num corners found: %d/n", cornerCount);
    
   
    if(cornerCount>0) 
    {
        for (int i=0; i<cornerCount; i++) 
        {
            cvCircle(srcImage, cvPoint((int)(corners[i].x), (int)(corners[i].y)), 6,
                color, 2, CV_AA, 0);
        }
    }
    
    cvShowImage( "image", srcImage );

 for (int j=0;j<cornerCount;j++)
 {
         cout<<corners[j].x;
     cout<<","<<corners[j].y<<endl;
 }
    
    cvReleaseImage(&srcImage);
    cvReleaseImage(&grayImage);
    cvReleaseImage(&corners1);
    cvReleaseImage(&corners2);
    
    cvWaitKey(0); 
    return 0;
}

==================================================================================

参考文献：

1.学习OpenCV（中文版） Gary Bradski & Adrian Kaebler著 于仕祺 刘瑞祯 译 清华大学出版社。 P351-356

2.OpenCV中文网站，http://www.opencv.org.cn/index.php/Cv%E5%9B%BE%E5%83%8F%E5%A4%84%E7%90%86

3.http://blog.csdn.net/sunyongbit/article/details/6335400