图像匹配之最小面积矩形

图像匹配，设计到旋转平移及缩放，在目标轮廓清晰的情况下，可通过连通域的方法分割出每一个目标，然后可以依据pattern的几何特征过滤掉一大部分不满足要求的连通域，将满足要求的再旋转到一个特定的方向，即可解决旋转问题，继而采用多尺度方法就可解决最终的图像匹配问题，本节介绍的就是利用最小面积外接矩形的方法来解决旋转问题。
最小面积外接矩形，其原理是首先提取图像的有效像素的凸包，求点云凸包算法可以参考我之间的博客-凸包求取算法，然后再求凸包的相邻点的梯度方向，将图像旋转对应方向，求旋转后有效像素的外接矩形的面积，在所有的凸包角度中，求最小面积对应的角度，既是旋转角度，但是这个算法也有不足，对图像的外部轮廓噪声十分敏感，当轮廓不够光滑时误差较大；无法正确区别0°、90°、180°、270°，之后需要添加另外的相关函数区分；精度不是很高，这也源于其对轮廓的高灵敏性，需要添加细分算法。

###代码

bool MinAreaRect(GCLPOINT *pointsIn, int num, double *rectX, double *rectY, double &convexHullArea)
{
    vector<int> index;
    ConvexHull(pointsIn, num, index);
    int nptNum = index.size();
    double *x = new double[nptNum];
    double *y = new double[nptNum];
    memset(x, 0, sizeof(double) * nptNum);
    memset(y, 0, sizeof(double) * nptNum);
    //gcloutput(_T("\n\n**************************\n\n"));
    GCLPOINT *pt = new GCLPOINT[nptNum];
    memset(pt, 0, sizeof(GCLPOINT) * nptNum);
    for (int i = 0; i < index.size(); i++)
    {
        x[i] = pointsIn[index[i]].x;
        y[i] = pointsIn[index[i]].y;
        pt[i].x = x[i];
        pt[i].y = y[i];
        //gcloutput(_T("%f %f\n"), x[i], y[i]);
    }
    convexHullArea = PolygonArea(pt, nptNum);
    delete[] pt;

    /*map<double, int> mapEigen;
    int dex = 0;
    for (int i = 0; i < nptNum - 2; i++)
    {
        for (int j = i + 1; j < nptNum; j++)
        {
            double theta = atan2(y[j] - y[i], x[j] - x[i]);
            if (theta >= PI / 2)
            {
                theta -= PI / 2;
            }
            else if (theta < 0)
            {
                if (theta >= - PI / 2)
                {
                    theta += PI / 2;
                }
                else
                {
                    theta += PI;
                }
            }
            mapEigen.insert(make_pair(theta,dex++));
        }
    }
    int nsize = mapEigen.size();*/
    // theta 去重
    //double *temp = new double[nsize];
    //double *gama = new double[nsize];
    //memset(gama, 0, sizeof(double) * nsize);
    //memset(temp, 0, sizeof(double) * nsize);
    //map<double, int>::iterator iter = mapEigen.begin();
    //int findex = 0;
    //for (;iter != mapEigen.end(); iter++)
    //{
    //    temp[findex++] = iter->first; // key value
    //    printf("%f\n",iter->first);
    //}
    //int *nindex = new int[nsize];
    //memset(nindex, 0, sizeof(int) * nsize);
    //for (int i = 0; i < nsize - 1; i++)
    //{
    //    for (int j = i + 1; j < nsize; j++)
    //    {
    //        if (abs(temp[i] - temp[j]) < 0.5 * PI / 180)
    //        {
    //            nindex[j] = 1;
    //        }
    //    }
    //}
    //int sumD = 0;
    //for (int i = 0; i < nsize; i++)
    //{
    //    if(nindex[i] != 1)
    //    {
    //        gama[sumD++] = temp[i];
    //    }
    //}
    //for (int i = 0; i < sumD; i++)
    //{
    //    printf("%f ",gama[i]);
    //}

    map<double, int> mapEignen;
    for (int i = 0; i < nptNum - 1; i++)
    {
        double temp = atan2(y[i + 1] - y[i], x[i + 1] - x[i]);
        temp = temp - floor(temp / (PI / 2)) * PI / 2;
        mapEignen.insert(make_pair(temp, i));
    }

    map<double, int>::iterator iter = mapEignen.begin();

    // 计算最小面积矩形
    double minArea = DBL_MAX;
    for (; iter != mapEignen.end(); iter++)
    {
        double gama = iter->first;
        double *xx = new double[nptNum];
        double *yy = new double[nptNum];
        memcpy(xx, x, sizeof(double) * nptNum);
        memcpy(yy, y, sizeof(double) * nptNum);
        Rmat(xx, yy, nptNum, -gama);
        double minX = DBL_MAX;
        double maxX = -DBL_MAX;
        double minY = DBL_MAX;
        double maxY = -DBL_MAX;
        for (int j = 0; j < nptNum; j++)
        {
            if (xx[j] > maxX)
            {
                maxX = xx[j];
            }
            if (xx[j] < minX)
            {
                minX = xx[j];
            }
            if (yy[j] > maxY)
            {
                maxY = yy[j];
            }
            if (yy[j] < minY)
            {
                minY = yy[j];
            }
        }
        double area = (maxY - minY) * (maxX - minX);
        if (area < minArea)
        {
            minArea = area;
            rectX[0] = minX;
            rectX[1] = maxX;
            rectX[2] = maxX;
            rectX[3] = minX;

            rectY[0] = minY;
            rectY[1] = minY;
            rectY[2] = maxY;
            rectY[3] = maxY;
            Rmat(rectX, rectY, 4, gama);
        }
        delete[] xx;
        delete[] yy;
    }

    delete[] x;
    delete[] y;

    return true;
}