凸包とOpenCV - Kazzz's diary

昨日までの件に関して、もう一度困っている事とやりたい事とを整理しておこう。

困っている事

findContourとapproxPolyDPで抽出した輪郭の頂点座標の出現順が一定しない。
座標原点の右上から出現したり、左下から出現したりするため、他の座標系(例:UIView)に変換することができない

やりたい事

findContourとapproxPolyDPで抽出した輪郭の頂点座標の列挙に一貫性を持たせ、他の座標系への変換を容易にする。

昨日までの私の足りない考えでの単純な方法では失敗したが、昨日コメントでアドバイス頂いたように、色々調べてみるとこのアルゴリズムは計算幾何学で言う所の"凸包"を算出する事に等しいのではないかということが判った。

凸包とは?

「点の集合があったとき、その点を全て含んで且つ凹んでいる部分が無い(凸)多角形を形成する点の集合。」
とでも言えば良いだろうか。詳しくは、Wiki等を参照されたい。凸包 - Wikipedia

ということで方法としては点集合の凸包を元にその頂点を抽出していけば良い訳だが、幸いなことにOpenCVにはこの凸包を取得するためのメソッドが既に用意されている。 (ラッキー!!!)

cv::convexHull

Structural Analysis and Shape Descriptors - convexHull ― OpenCV 2.4.3 documentation

OpenCVのサイトにはサンプルコードも用意されているので、これを見ながらやれば完璧だ。

疑似コード(C++)

    //srcは入力画像をMatに変換したものを渡すこととする
    cv::vector<cv::vector<cv::Point>> squares;
    cv::vector<cv::vector<cv::Point> > contours;// 輪郭情報
    cv::vector<cv::vector<cv::Point> > poly;// ボリゴン情報

    // 輪郭抽出
    cv::findContours(src, contours ,CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE);

    for (size_t i = 0; i < contours.size(); i++)
    {
        cv::Mat contour = cv::Mat(contours[i]);

        //凸包取得
        cv::vector<cv::Point> approx;
        cv::convexHull(contour, approx);

        // 輪郭・ポリライン近似 epsilonはarcLengthに対する割合で指定する
        cv::approxPolyDP(approx, approx, epsilon * cv::arcLength(contour, true), true);

        if (approx.size() == 4 )　//ここでは頂点数4、つまり四辺形の頂点集合だけを対象にしている
        {
　　　　　　　　　　　//destは出力先のMat
            cv::drawContours(dest, contours, i, CV_RGB(0, 0, 255), 4);
            //ベクタに格納
            squares.push_back(approx);
        }
    }

findContours〜approxPolyDPに至る間にconvexHullを介することによりベクタには凸包頂点座標が格納される。
convexHullの第3パラメタは頂点を抽出する際の向きとして時計回り/反時計回りを指定できるが、今回はデフォルトでに設定することでSW(右下)→NW(左下)→NE(左上)→SE(右上)と時計回りで座標が格納されるので、あとはUIViewの座標系原点に対して単純に変換すれば良い。