Segmentacja obrazu - Split and Merge (Quadtrees)

Question

Czy istnieje implementacja metody podziału i scalania segmentacji obrazu? każda rada byłaby mile widziana.

Answer 1

O czym jest segmentacja?

Segmentacja oznacza podział obrazu na kilka połączonych regionów. Zasadniczo można dokonać segmentacji z dwiema definicjami regionu: można zdefiniować region jako grupę połączonych podobnych pikseli lub zbiór połączonych pikseli otoczony nieciągłościami (krawędziami). Podziel i scalaj używa pierwszego podejścia.

Matematycznie rzecz biorąc: jeśli cały obraz jest reprezentowany przez zbiór pikseli (zwanych R), niż chcieliby Państwo uzyskać podzbiory takie jak

1. Segmentacja jest kompletna, więc wszystkie podregiony sumują się do całości R. Związek wszystkich regionów: R UR U ... n _{UR = R.}
2. R _i jest podłączony.
3. Regiony są różne. R _i ∩ R _j = ∅ podano, że ≠ j
4. Regiony mają podobne właściwości. Można to wyrazić za pomocą funkcji zwanej kryterium homogeniczności (P). Powinien dawać PRAWDZIWOŚĆ członkom danego regionu i FALSE dla wszystkich pozostałych regionów.
5. Nie można scalić regionów sąsiadujących. Dla wszystkich regionów P (R _i U R _j) = FALSE, biorąc pod uwagę, że i ≠ j.

Co to jest algorytm podziału i scalania?

Po pierwsze, musimy wybrać kryterium homogeniczności. Kryterium jednorodności może mieć charakter globalny (w zależności od regionu) lub lokalny (w zależności od niewielkiego okna regionu, a jeśli jest prawdziwe dla wszystkich okien, niż w przypadku regionu). Prostym przykładem może być odchylenie od średniej powinno być mniejsze niż próg. & all; p _i ∈ R _i: | p _i - μ | ≤ f * σ.

Algorytm podziału i scalania składa się z dwóch faz: podziału i fazy scalania. W fazie podziału rekursywnie dzielimy regiony na cztery podregiony (zaczynając od całego obrazu jako jednego regionu), dopóki nasze kryterium homogeniczności nie zostanie spełnione we wszystkich podregionach. Łatwo zauważyć, że warunki 1-4 segmentacji są spełnione. Przechodzimy do etapu scalania w celu spełnienia warunku 5^th.

W etapie łączenia się sprawdzić, że P (R _i U R _J) = TRUE każdych dwóch sąsiednich obszarów, i połączenie dwóch regionów. Powtarzamy ten krok, dopóki nie będą potrzebne żadne zmiany. Teraz spełniliśmy wszystkie warunki, nasz obraz został podzielony na podregiony.

Pseudokod

Oto pseudokod do dzielenia i łączenia algorytmu:

1. Init: mamy tylko jeden duży obszar (cały obraz).
2. Podział: Jeśli P (R _i) = PRAWDA przejdź do następnego kroku. W przeciwnym razie podziel część R _i na cztery podregiony i wykonaj na nich krok 2.
3. Scal, gdy: R _i R _J sąsiadują i P (R _i UR _J) = PRAWDA, połączenie dwóch regionów niż powtarzania etapu 3. Jeżeli nie ma takich regionów jesteśmy skończone.

Answer 2

algorytm segmentacji split-seryjnej został wdrożony tutaj: http://www.uni-koblenz.de/~lb/lb_downloads

Answer 3

To moja realizacja. Nie jestem guru C++/opencv, więc jeśli ktoś znajdzie jakiś sposób na zoptymalizowanie tego skryptu, dodaj komentarze!

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