Phân đoạn hình ảnh - Tách và Hợp nhất (Quadtrees)

Question

Có triển khai phương pháp tách và hợp nhất phân đoạn hình ảnh không? mọi lời khuyên sẽ được đánh giá cao.

Answer 1

Phân đoạn là gì?

Phân đoạn có nghĩa là phân chia hình ảnh của bạn thành một số vùng được kết nối. Về cơ bản, bạn có thể thực hiện phân đoạn với hai định nghĩa của vùng: bạn có thể xác định vùng là một nhóm các pixel tương tự được kết nối hoặc một tập hợp các điểm ảnh được kết nối được bao quanh bởi các điểm ngắt (cạnh). Split và merge sử dụng cách tiếp cận đầu tiên.

toán học nói: nếu toàn bộ hình ảnh của bạn được thể hiện bằng các thiết lập của pixel (gọi tắt là R), hơn bạn muốn để có được các tập con như

1. Phân đoạn hoàn tất, vì vậy tất cả các tiểu vùng tổng hợp cho toàn bộ R. Liên hiệp các tất cả các vùng là R UR U ... UR _n = R.
2. R _i được kết nối.
3. Khu vực riêng biệt. R _i ∩ R _j = ∅ cho rằng tôi ≠ j
4. vùng có tính chất tương tự. Điều này có thể được biểu diễn bằng một hàm gọi là tiêu chí đồng nhất (P). Nó sẽ cung cấp TRUE cho các thành viên của khu vực nhất định và FALSE cho tất cả các khu vực khác.
5. Không thể hợp nhất các vùng lân cận. Đối với tất cả các vùng P (R _i U R _j) = FALSE cho rằng i ≠ j.

Thuật toán phân tách và hợp nhất là gì?

Vì vậy, trước tiên, chúng tôi phải chọn một tiêu chí đồng nhất. Một tiêu chí đồng nhất có thể là toàn cầu (tùy thuộc vào toàn bộ khu vực) hoặc địa phương (tùy thuộc vào một cửa sổ nhỏ của khu vực, và nếu nó là đúng cho tất cả các cửa sổ, hơn là đúng cho khu vực). Một ví dụ đơn giản có thể là độ lệch trung bình nên nhỏ hơn ngưỡng. & forall; p _i ∈ R _i: | p _i - μ | ≤ f * σ.

Thuật toán tách và hợp nhất có hai giai đoạn: phân tách và pha hợp nhất. Trong giai đoạn tách chúng ta phân tách đệ quy các vùng thành bốn tiểu vùng (bắt đầu với toàn bộ hình ảnh là một vùng) cho đến khi tiêu chuẩn đồng nhất của chúng ta được đáp ứng trong tất cả các tiểu vùng. Thật dễ dàng để thấy rằng các điều kiện 1-4 của phân khúc được đáp ứng. Chúng tôi tiến hành hợp nhất bước để đáp ứng điều kiện thứ 1 ^thứ.

Trong bước merge chúng tôi kiểm tra xem P (R _i U R _j) = TRUE cho mỗi hai khu vực láng giềng, và hợp nhất hai khu vực. Chúng tôi lặp lại bước này cho đến khi không cần thay đổi nữa. Bây giờ chúng tôi đã đáp ứng tất cả các điều kiện, chúng tôi đã phân đoạn hình ảnh của chúng tôi thành các tiểu vùng.

Mã giả

Đây là một giả để tách và hợp nhất các thuật toán:

1. Init: chúng tôi chỉ có một khu vực lớn (toàn bộ hình ảnh).
2. Tách: Nếu P (R _i) = TRUE tiến hành bước tiếp theo. Nếu không chia nhỏ R _i thành bốn tiểu vùng và thực hiện bước 2 trên chúng.
3. Merge: Nếu R _i và R _j là các nước láng giềng và P (R _i UR _j) = TRUE, sáp nhập hai khu vực, hơn lặp lại bước 3. Nếu không có khu vực như chúng ta đã kết thúc.

Answer 2

một thuật toán phân chia hợp nhất được thực hiện ở đây: http://www.uni-koblenz.de/~lb/lb_downloads

Answer 3

Đây là thực hiện của tôi. Tôi không phải là một C++/opencv guru vì vậy nếu ai đó tìm ra một số cách để tối ưu hóa kịch bản này, thêm ý kiến ​​xin vui lòng!

#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; 
}