OpenCV源码解析之在图片中找四边形－FindSquares

Myth丶恋晨 2022-04-11 03:50 630阅读 0赞

这个FindSquares算是比较典型的综合技能项目吧，用到的小技巧还不少，我们先看一下几个函数吧，

## 函数static double angle的作用是求角度 ##

根据余弦定理：![a^2 + b^2 - 2ab\\cos\{\\theta\} = c^2][a_2 _ b_2 - 2ab_cos_theta_ _ c_2]  
在平面座标中  
![\\begin\{align\*\} a &= (x\_1 - x\_0)^2 + (y\_1 - y\_0)^2 \\\\ b &= (x\_2 - x\_0)^2 + (y\_2 - y\_0)^2\\\\ c &= (x\_2 - x\_1)^2 + (y\_2 - y\_1)^2\\\\ \\end\{align\*\}][begin_align_ a _ _x_1 - x_0_2 _ _y_1 - y_0_2 _ b _ _x_2 - x_0_2 _ _y_2 - y_0_2_ c _ _x_2 - x_1_2 _ _y_2 - y_1_2_ _end_align]

![\\begin\{array\}\{lc\} a^2 + b^2 - c^2 \\\\ = (x\_1 - x\_0)^2 + (y\_1 - y\_0)^2 + (x\_2 - x\_0)^2 + (y\_2 - y\_0)^2 -(x\_2 - x\_1)^2 + (y\_2 - y\_1)^2 \\\\ = 2\\left\[ (x\_1 - x\_0)(x\_2 - x\_0)+(y\_1 - y\_0)(y\_2 - y\_0) \\right\] \\end\{array\}][begin_array_lc_ a_2 _ b_2 - c_2 _ _ _x_1 - x_0_2 _ _y_1 - y_0_2 _ _x_2 - x_0_2 _ _y_2 - y_0_2 -_x_2 - x_1_2 _ _y_2 - y_1_2 _ _ 2_left_ _x_1 - x_0_x_2 - x_0_y_1 - y_0_y_2 - y_0_ _right_ _end_array]  
通过计算变换，最后可以得到：

![\\begin\{array\}\{lc\} \\cos\{\\theta\} = \\frac\{ (x\_1 - x\_0)(x\_2 - x\_0)+(y\_1 - y\_0)(y\_2 - y\_0) \}\{ab\} \\end\{array\}][begin_array_lc_ _cos_theta_ _ _frac_ _x_1 - x_0_x_2 - x_0_y_1 - y_0_y_2 - y_0_ _ab_ _end_array]  
嗯，函数中直接用了这个结果。

## 其余函数的说明 ##

1.函数Canny进行边缘检测，和Sobel原理差不多，不过相对加了些料，稍有点复杂，以后有时间再说吧。

2.函数dilate是对白色高亮部分的扩张，目的是消除噪音点，（这个可以忽略，不影响对源代码的理解）。

3.函数findContours用来寻找闭合的边缘(函数本身会找到所有的边，这里我们只用闭合的边，而且是４边形)。

4.函数approxPolyDP采用Ramer–Douglas–Peucker 计算方法来对边缘进行多边形拟合，具体原理可参考

[https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker\_algorithm][https_en.wikipedia.org_wiki_Ramer_E2_80_93Douglas_E2_80_93Peucker_algorithm]

![20181204173626475.gif][]

就是先找最远的点连成一直线，然后发现有距离该直线比较大的点可能是角点，那就把原来的线去掉，以原来的２个端点和这个刚找到的最远的点一起，再连成两条新生成的线，依次循环！

5. 函数isContourConvex用来判断多边形是否是凸多形，判断方法如下图所示

(注意图中是假设以顺时针方向遍历多边形的边，逆时针遍历的话判断时符号要反过来)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70][]

嗯，理解起来貌似都不太难！

## 源码 ##

最后判断４个角度这句， if( maxCosine < 0.3 )，0.3大约相当于72度，也就是说72~108度的角都可以认为是９０度的近似而被接收为４边形。

#include "opencv2/core.hpp"
    #include "opencv2/core/ocl.hpp"
    #include "opencv2/core/utility.hpp"
    #include "opencv2/imgproc.hpp"
    #include "opencv2/imgcodecs.hpp"
    #include "opencv2/highgui.hpp"
    #include <iostream>
    
    using namespace cv;
    using namespace std;
    
    int thresh = 50, N = 11;
    const char* wndname = "Square Detection Demo";
    
    // helper function:
    // finds a cosine of angle between vectors
    // from pt0->pt1 and from pt0->pt2
    static double angle( Point pt1, Point pt2, Point pt0 )
    {
        double dx1 = pt1.x - pt0.x;
        double dy1 = pt1.y - pt0.y;
        double dx2 = pt2.x - pt0.x;
        double dy2 = pt2.y - pt0.y;
        return (dx1*dx2 + dy1*dy2)/sqrt((dx1*dx1 + dy1*dy1)*(dx2*dx2 + dy2*dy2) + 1e-10);
    }
    
    
    // returns sequence of squares detected on the image.
    static void findSquares( const UMat& image, vector<vector<Point> >& squares )
    {
        squares.clear();
        UMat pyr, timg, gray0(image.size(), CV_8U), gray;
    
        // down-scale and upscale the image to filter out the noise
        // 先down到1/4大小（长宽各取一半），然后再up到原图大小，中间有两次Guassian卷积去噪音
        pyrDown(image, pyr, Size(image.cols/2, image.rows/2));
        pyrUp(pyr, timg, image.size());
        vector<vector<Point> > contours;
    
        // find squares in every color plane of the image
        for( int c = 0; c < 3; c++ )
        {
            int ch[] = {c, 0};
            mixChannels(timg, gray0, ch, 1);　// 把c=0,1,2这3个channel分别copy到gray0中
    
            // try several threshold levels
            for( int l = 0; l < N; l++ )
            {
                // hack: use Canny instead of zero threshold level.
                // Canny helps to catch squares with gradient shading
                if( l == 0 )
                {
                    // apply Canny. Take the upper threshold from slider
                    // and set the lower to 0 (which forces edges merging)
                    Canny(gray0, gray, 0, thresh, 5);
                    // dilate canny output to remove potential
                    // holes between edge segments
                    dilate(gray, gray, UMat(), Point(-1,-1));
                }
                else
                {
                    // apply threshold if l!=0:
                    //     tgray(x,y) = gray(x,y) < (l+1)*255/N ? 255 : 0
                    threshold(gray0, gray, (l+1)*255/N, 255, THRESH_BINARY);
                }
    
                // find contours and store them all as a list
                findContours(gray, contours, RETR_LIST, CHAIN_APPROX_SIMPLE);
    
                vector<Point> approx;
    
                // test each contour
                for( size_t i = 0; i < contours.size(); i++ )
                {
                    // approximate contour with accuracy proportional
                    // to the contour perimeter
    
                    approxPolyDP(contours[i], approx, arcLength(contours[i], true)*0.02, true);
    
                    // square contours should have 4 vertices after approximation
                    // relatively large area (to filter out noisy contours)
                    // and be convex.
                    // Note: absolute value of an area is used because
                    // area may be positive or negative - in accordance with the
                    // contour orientation
                    if( approx.size() == 4 &&
                            fabs(contourArea(approx)) > 1000 &&
                            isContourConvex(approx) )
                    {
                        double maxCosine = 0;
    
                        for( int j = 2; j < 5; j++ )
                        {
                            // find the maximum cosine of the angle between joint edges
                            double cosine = fabs(angle(approx[j%4], approx[j-2], approx[j-1]));
                            maxCosine = MAX(maxCosine, cosine);
                        }
    
                        // if cosines of all angles are small
                        // (all angles are ~90 degree) then write quandrange
                        // vertices to resultant sequence
                        // 0.3 means 72degree, so if 90+/-8degee will be regarded as 90degree
                        if( maxCosine < 0.3 )
                            squares.push_back(approx);
                    }
                }
            }
        }
    }
    
    // the function draws all the squares in the image
    static void drawSquares( UMat& _image, const vector<vector<Point> >& squares )
    {
        Mat image = _image.getMat(ACCESS_WRITE);
        for( size_t i = 0; i < squares.size(); i++ )
        {
            const Point* p = &squares[i][0];
            int n = (int)squares[i].size();
            polylines(image, &p, &n, 1, true, Scalar(0,255,0), 3, LINE_AA);
        }
    }
    
    
    // draw both pure-C++ and ocl square results onto a single image
    static UMat drawSquaresBoth( const UMat& image,
                                const vector<vector<Point> >& sqs)
    {
        UMat imgToShow(Size(image.cols, image.rows), image.type());
        image.copyTo(imgToShow);
    
        drawSquares(imgToShow, sqs);
    
        return imgToShow;
    }
    
    
    int main(int argc, char** argv)
    {
        const char* keys =
            "{ i input    | ../data/pic1.png   | specify input image }"
            "{ o output   | squares_output.jpg | specify output save path}"
            "{ h help     |                    | print help message }"
            "{ m cpu_mode |                    | run without OpenCL }";
    
        CommandLineParser cmd(argc, argv, keys);
    
        if(cmd.has("help"))
        {
            cout << "Usage : " << argv[0] << " [options]" << endl;
            cout << "Available options:" << endl;
            cmd.printMessage();
            return EXIT_SUCCESS;
        }
        if (cmd.has("cpu_mode"))
        {
            ocl::setUseOpenCL(false);
            cout << "OpenCL was disabled" << endl;
        }
    
        string inputName = cmd.get<string>("i");
        string outfile = cmd.get<string>("o");
    
        int iterations = 10;
        namedWindow( wndname, WINDOW_AUTOSIZE );
        vector<vector<Point> > squares;
    
        UMat image;
        imread(inputName, 1).copyTo(image);
        if( image.empty() )
        {
            cout << "Couldn't load " << inputName << endl;
            cmd.printMessage();
            return EXIT_FAILURE;
        }
    
        int j = iterations;
        int64 t_cpp = 0;
        //warm-ups
        cout << "warming up ..." << endl;
        findSquares(image, squares);
    
        do
        {
            int64 t_start = getTickCount();
            findSquares(image, squares);
            t_cpp += cv::getTickCount() - t_start;
    
            t_start  = getTickCount();
    
            cout << "run loop: " << j << endl;
        }
        while(--j);
        cout << "average time: " << 1000.0f * (double)t_cpp / getTickFrequency() / iterations << "ms" << endl;
    
        UMat result = drawSquaresBoth(image, squares);
        imshow(wndname, result);
        imwrite(outfile, result);
        waitKey(0);
    
        return EXIT_SUCCESS;
    }

[a_2 _ b_2 - 2ab_cos_theta_ _ c_2]: https://private.codecogs.com/gif.latex?a%5E2%20&plus;%20b%5E2%20-%202ab%5Ccos%7B%5Ctheta%7D%20%3D%20c%5E2
[begin_align_ a _ _x_1 - x_0_2 _ _y_1 - y_0_2 _ b _ _x_2 - x_0_2 _ _y_2 - y_0_2_ c _ _x_2 - x_1_2 _ _y_2 - y_1_2_ _end_align]: https://private.codecogs.com/gif.latex?%5Cbegin%7Balign*%7D%20a%20%26%3D%20%28x_1%20-%20x_0%29%5E2%20&plus;%20%28y_1%20-%20y_0%29%5E2%20%5C%5C%20b%20%26%3D%20%28x_2%20-%20x_0%29%5E2%20&plus;%20%28y_2%20-%20y_0%29%5E2%5C%5C%20c%20%26%3D%20%28x_2%20-%20x_1%29%5E2%20&plus;%20%28y_2%20-%20y_1%29%5E2%5C%5C%20%5Cend%7Balign*%7D
[begin_array_lc_ a_2 _ b_2 - c_2 _ _ _x_1 - x_0_2 _ _y_1 - y_0_2 _ _x_2 - x_0_2 _ _y_2 - y_0_2 -_x_2 - x_1_2 _ _y_2 - y_1_2 _ _ 2_left_ _x_1 - x_0_x_2 - x_0_y_1 - y_0_y_2 - y_0_ _right_ _end_array]: https://private.codecogs.com/gif.latex?%5Cbegin%7Barray%7D%7Blc%7D%20a%5E2%20&plus;%20b%5E2%20-%20c%5E2%20%5C%5C%20%3D%20%28x_1%20-%20x_0%29%5E2%20&plus;%20%28y_1%20-%20y_0%29%5E2%20&plus;%20%28x_2%20-%20x_0%29%5E2%20&plus;%20%28y_2%20-%20y_0%29%5E2%20-%28x_2%20-%20x_1%29%5E2%20&plus;%20%28y_2%20-%20y_1%29%5E2%20%5C%5C%20%3D%202%5Cleft%5B%20%28x_1%20-%20x_0%29%28x_2%20-%20x_0%29&plus;%28y_1%20-%20y_0%29%28y_2%20-%20y_0%29%20%5Cright%5D%20%5Cend%7Barray%7D
[begin_array_lc_ _cos_theta_ _ _frac_ _x_1 - x_0_x_2 - x_0_y_1 - y_0_y_2 - y_0_ _ab_ _end_array]: https://private.codecogs.com/gif.latex?%5Cbegin%7Barray%7D%7Blc%7D%20%5Ccos%7B%5Ctheta%7D%20%3D%20%5Cfrac%7B%20%28x_1%20-%20x_0%29%28x_2%20-%20x_0%29&plus;%28y_1%20-%20y_0%29%28y_2%20-%20y_0%29%20%7D%7Bab%7D%20%5Cend%7Barray%7D
[https_en.wikipedia.org_wiki_Ramer_E2_80_93Douglas_E2_80_93Peucker_algorithm]: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
[20181204173626475.gif]: /images/20220411/f1c4eeb28b674185b61c10b14dfdbede.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70]: /images/20220411/a24c4aac7ca843e9806ba7f8b397f1ec.png