7

有没有实现图像分割的拆分和合并方法？任何建议将不胜感激。

4

3 回答 3

14

细分是关于什么的？

分割意味着将您的图像划分为几个连接的区域。基本上，您可以使用两种区域定义进行分割：您可以将区域定义为一组连接的相似像素，或一组被不连续性（边缘）包围的连接像素。拆分和合并使用第一种方法。

从数学上讲：如果您的整个图像由一组像素（称为 R）表示，那么您希望获得子集，例如

  1. 分割完成，所以所有子区域加起来就是整个R。所有区域的并集是R 1 UR 2 U ... UR n = R。
  2. R i是连通的。
  3. 地区是不同的。R i ∩R j =∅ 假设 i≠j
  4. 区域具有相似的属性。这可以通过称为同质性标准 (P) 的函数来表示。它应该为给定区域的成员提供 TRUE，为所有其他区域提供 FALSE。
  5. 无法合并相邻区域。对于所有区域 P(R i UR j )=FALSE，因为 i≠j。

什么是拆分和合并算法？

所以首先，我们必须选择一个同质性标准。同质性标准可以是全局的（取决于整个区域）或局部的（取决于该区域的一个小窗口，如果所有窗口都为真，则该区域为真）。一个简单的例子可能是与平均值的偏差应小于阈值。∀p i ∈R i : |p i -μ|≤f*σ。

拆分和合并算法有两个阶段：拆分和合并阶段。在分割阶段，我们递归地将区域分割成四个子区域（从整个图像作为一个区域开始），直到所有子区域都满足我们的同质性标准。不难看出，切分的1-4个条件都满足了。我们继续进行合并步骤以满足第 5个条件。

在合并步骤中，我们检查每两个相邻区域的 P(R i UR j )=TRUE，然后合并这两个区域。我们重复此步骤，直到不再需要更改。现在我们满足了所有条件，我们将图像分割成子区域。

伪代码

这是拆分和合并算法的伪代码：

  1. Init：我们只有一个大区域（整个图像）。
  2. 拆分：如果 P(R i )=TRUE 继续下一步。否则将 R i细分为四个子区域并对其执行步骤 2。
  3. 合并：如果 R i和 R j是邻居并且 P(R i UR j ) = TRUE，则合并两个区域，然后重复步骤 3。如果没有这样的区域，我们就完成了。
于 2011-08-18T10:22:36.793 回答
9

这是我的实现。我不是 c++/opencv 大师，所以如果有人找到优化此脚本的方法，请添加评论！

#include <opencv2/highgui/highgui.hpp>
#include <opencv2/core/core.hpp>
#include <iostream>

using namespace cv;
using namespace std;

Mat img;
Size size;

struct region {
    // tree data structure
    vector<region> childs;
    bool validity; // TODO: have a method for clear the data structure and remove regions with false validity

    // tree for split&merge procedure
    Rect roi;
    Mat m;
    Scalar label;
    Mat mask; // for debug. don't use in real cases because it is computationally too heavy.
};

//----------------------------------------------------------------------------------------------------------------------- merging
bool mergeTwoRegion(region& parent, const Mat& src, region& r1, region& r2,  bool (*predicate)(const Mat&)) {
    if(r1.childs.size()==0 && r2.childs.size()==0) {

        Rect roi1 = r1.roi;
        Rect roi2 = r2.roi;
        Rect roi12 = roi1 | roi2;
        if(predicate( src(roi12) )) {
            r1.roi = roi12;

            // recompute mask
            r1.mask = Mat::zeros(size, CV_8U);
            rectangle(r1.mask, r1.roi, 1, CV_FILLED);

            r2.validity = false;
            return true;
        }
    }
    return false;
}

void merge(const Mat& src, region& r, bool (*predicate)(const Mat&)) {
    // check for adjiacent regions. if predicate is true, then  merge.
    // the problem is to check for adjiacent regions.. one way can be:
    // check merging for rows. if neither rows can be merged.. check for cols.

    bool row1=false, row2=false, col1=false, col2=false;

    if(r.childs.size()<1) return;

    // try with the row
    row1 = mergeTwoRegion(r, src, r.childs[0], r.childs[1], predicate);
    row2 = mergeTwoRegion(r, src, r.childs[2], r.childs[3], predicate);

    if( !(row1 | row2) ) {
        // try with column
        col1 = mergeTwoRegion(r, src, r.childs[0], r.childs[2], predicate);
        col2 = mergeTwoRegion(r, src, r.childs[1], r.childs[3], predicate);
    } 

    for(int i=0; i<r.childs.size(); i++) {
        if(r.childs[i].childs.size()>0) 
            merge(src, r.childs[i], predicate);
    }
}

//----------------------------------------------------------------------------------------------------------------------- quadtree splitting
region split(const Mat& src, Rect roi, bool (*predicate)(const Mat&)) {
    vector<region> childs;
    region r;

    r.roi = roi;
    r.m = src;
    r.mask = Mat::zeros(size, CV_8U);
    rectangle(r.mask, r.roi, 1, CV_FILLED);
    r.validity = true;

    bool b = predicate(src);
    if(b) {
        Scalar mean, s;
        meanStdDev(src, mean, s);
        r.label = mean;
    } else {
        int w = src.cols/2;
        int h = src.rows/2;
        region r1 = split(src(Rect(0,0, w,h)), Rect(roi.x, roi.y, w,h), predicate);
        region r2 = split(src(Rect(w,0, w,h)), Rect(roi.x+w, roi.y, w,h), predicate);
        region r3 = split(src(Rect(0,h, w,h)), Rect(roi.x, roi.y+h, w,h), predicate);
        region r4 = split(src(Rect(w,h, w,h)), Rect(roi.x+w, roi.y+h, w,h), predicate);
        r.childs.push_back( r1 );
        r.childs.push_back( r2 );
        r.childs.push_back( r3 );
        r.childs.push_back( r4 );
    }
    //merge(img, r, predicate);
    return r;
}

//----------------------------------------------------------------------------------------------------------------------- tree traversing utility
void print_region(region r) {
    if(r.validity==true && r.childs.size()==0) {
        cout << r.mask << " at " << r.roi.x << "-" << r.roi.y << endl;
        cout << r.childs.size() << endl;
        cout << "---" << endl;
    }
    for(int i=0; i<r.childs.size(); i++) {
        print_region(r.childs[i]);
    }
}

void draw_rect(Mat& imgRect, region r) {
    if(r.validity==true && r.childs.size()==0) 
        rectangle(imgRect, r.roi, 50, .1);
    for(int i=0; i<r.childs.size(); i++) {
        draw_rect(imgRect, r.childs[i]);
    }
}

void draw_region(Mat& img, region r) {
    if(r.validity==true && r.childs.size()==0) 
        rectangle(img, r.roi, r.label, CV_FILLED);
    for(int i=0; i<r.childs.size(); i++) {
        draw_region(img, r.childs[i]);
    }
}

//----------------------------------------------------------------------------------------------------------------------- split&merge test predicates
bool predicateStdZero(const Mat& src) {
    Scalar stddev, mean;
    meanStdDev(src, mean, stddev);
    return stddev[0]==0;
}
bool predicateStd5(const Mat& src) {
    Scalar stddev, mean;
    meanStdDev(src, mean, stddev);
    return (stddev[0]<=5.8) || (src.rows*src.cols<=25);
}

//----------------------------------------------------------------------------------------------------------------------- main
int main( int /*argc*/, char** /*argv*/ )
{
    img = (Mat_<uchar>(4,4) << 0,0,1,1,
                               1,1,1,1, 
                               3,3,3,3,
                               3,4,4,3);

    cout << img << endl;
    size = img.size();

    region r;
    r = split(img, Rect(0,0,img.cols,img.rows), &predicateStdZero);
    merge(img, r, &predicateStdZero);
    cout << "------- print" << endl;
    print_region(r);

    cout << "-----------------------" << endl;

    img = imread("lena.jpg", 0);

    // round (down) to the nearest power of 2 .. quadtree dimension is a pow of 2.
    int exponent = log(min(img.cols, img.rows)) / log (2);
    int s = pow(2.0, (double)exponent);
    Rect square = Rect(0,0, s,s);
    img = img(square).clone();

    namedWindow("original", CV_WINDOW_AUTOSIZE);
    imshow( "original", img );

    cout << "now try to split.." << endl;
    r = split(img, Rect(0,0,img.cols,img.rows), predicateStd5);

    cout << "splitted" << endl;
    Mat imgRect = img.clone();
    draw_rect(imgRect, r);
    namedWindow("split", CV_WINDOW_AUTOSIZE);
    imshow( "split", imgRect );
    imwrite("split.jpg", imgRect);

    merge(img, r, &predicateStd5);
    Mat imgMerge = img.clone();
    draw_rect(imgMerge, r);
    namedWindow("merge", CV_WINDOW_AUTOSIZE);
    imshow( "merge", imgMerge );
    imwrite( "merge.jpg", imgMerge );

    Mat imgSegmented = img.clone();
    draw_region(imgSegmented, r);
    namedWindow("segmented", CV_WINDOW_AUTOSIZE);
    imshow( "segmented", imgSegmented );
    imwrite( "segmented.jpg", imgSegmented );

    while( true )
    {
        char c = (char)waitKey(10);
        if( c == 27 ) { break; }
    }

    return 0;
}
于 2013-02-06T13:38:20.677 回答
3

这里实现了一个 split-merge 分割算法：http://www.uni-koblenz.de/~lb/lb_downloads

于 2011-11-20T09:24:22.967 回答