이미지 분할 - 분할 및 병합 (Quadtrees)

Question

이미지 분할의 분할 및 병합 방법에 대한 구현이 있습니까? 조언을 주시면 감사하겠습니다.

Answer 1

세분화는 무엇입니까?

분할이란 이미지를 여러 연결된 지역으로 나누는 것을 의미합니다. 기본적으로 영역의 두 가지 정의로 세그먼트 화를 수행 할 수 있습니다. 영역을 연결된 유사한 픽셀 그룹 또는 불연속 (가장자리)으로 둘러싸인 연결된 픽셀 세트로 정의 할 수 있습니다. 분할 및 병합은 첫 번째 방법을 사용합니다.

수학적으로 말하기 :

1. 분할이 완료 등이 하위 집합을 좀하고 싶습니다보다 전체 이미지가, (R라고도 함) 픽셀의 집합으로 표현되는 경우, 그래서 모든 하위 영역 전체를 요약 모든 지역의 R. 연합 R 1 _{UR 2} ... U _I 연결되어 UR _{N =} R.
2. R이다.
3. 지역이 다릅니다. R _난 ∩ _{R j는} = ∅ I ≠ J
4. 영역이 유사한 특성을 갖는 것으로 주어진다. 이것은 균질성 표준 (homogenity criterion, P)이라 불리는 함수로 표현 될 수있다. 주어진 지역의 멤버에게는 TRUE를, 다른 모든 지역에는 FALSE를 주어야합니다.
5. 인접 영역을 병합 할 수 없습니다. 모든 지역에 대해 P (R _i U R _j) = FALSE이면 i ≠j가됩니다.

어떤 분할 및 병합 알고리즘이 사용됩니까?

먼저 균등성 기준을 선택해야합니다. 동질성 기준은 전역 (전체 지역에 따라 다름) 또는 지역 (작은 지역의 창에 따라 다르며 모든 창에 대해 사실이라면 지역에 해당)에 따라 달라질 수 있습니다. 간단한 예가 평균으로부터의 편차가 임계 값보다 작아야합니다. & ltall; p _{i ∈ R i : | p i - μ | ≤ f * σ.}

분할 및 병합 알고리즘에는 분할과 병합 단계의 두 단계가 있습니다. 분할 단계에서 우리는 균일 한 기준이 모든 하위 영역에서 충족 될 때까지 반복적으로 영역을 네 개의 하위 영역으로 분할합니다 (이미지 전체를 하나의 영역으로 시작). 세분화의 1-4 조건이 충족되는 것을 쉽게 알 수 있습니다. 우리는 5 ^th 조건을 만족하기 위해 단계를 병합합니다. 병합 단계

우리는 확인이 P (R I _{U R J}) = 각각의 두 인접 영역에 대한 TRUE, 두 영역을 병합. 더 이상 변경이 필요하지 않을 때까지이 단계를 반복합니다. 이제 우리는 모든 조건을 충족 시켰고 이미지를 부분 영역으로 세분화했습니다.

1. 초기화 :

   의사 코드 여기

   은 분할 알고리즘을 병합하는 의사입니다 우리는 단지 하나의 큰 지역 (전체 이미지)을 가지고있다.

2. 스플릿 : P (R _i) = TRUE이면 다음 단계로 진행합니다. 그렇지 않은 경우 R _i을 4 개의 하위 영역으로 세분화하고 2 단계를 수행하십시오.
3. 병합 R _I 및 R _J는 이웃 P 인 경우 (R _I UR _J) = TRUE, 우리는 이러한 영역이 없으면 3 단계를 반복하지 않고, 두 영역을 병합 끝마친.

Answer 2

분할 병합 분할 알고리즘은 여기에 구현 : http://www.uni-koblenz.de/~lb/lb_downloads

Answer 3

이 내 구현입니다. 나는 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; 
}