1. 首頁
  2. 問答
  3. 圖像分割 - 拆分和合並（四叉樹）

圖像分割 - 拆分和合並（四叉樹）

2011-08-13 268 views

回答

12

細分是關於什麼？

分割是指將圖像分割爲多個連接區域。基本上，您可以使用區域的兩個定義進行分割：您可以將區域定義爲一組連接的相似像素，或者由不連續性（邊緣）包圍的一組連接像素。拆分和合並使用第一種方法。

從數學上說：如果你的整個圖像是由一組像素（稱爲R）的代表，比你想獲得的子集，如

  1. 分割完成，所以所有次區域總結整個所有區域的R.聯盟爲R UR ù... 我連接UR ñ = R.
  2. R上。
  3. 區域不同。 ř我 ∩řĴ = ∅鑑於本人≠Ĵ
  4. 區域具有相似的性質。這可以用稱爲均勻性標準（P）的函數來表示。它應該爲給定地區的成員提供TRUE，而爲所有其他地區提供FALSE。
  5. 不能合併鄰居區域。對於所有地區P（R i U R j）= FALSE給定i ≠ j。

什麼拆分和合並算法是關於什麼的？

首先，我們必須選擇均勻性標準。均勻性標準可以是全球性的（取決於整個地區）還是局部性的（取決於該地區的一個小窗口，如果對於所有窗口來說都是如此，則對於該地區而言是如此）。一個簡單的例子可能是平均數的偏差應該小於一個閾值。 ＆forall; p i ∈ R i：| p i - μ | ≤ f * σ。

拆分和合並算法有兩個階段：拆分和合並階段。 在分裂階段，我們遞歸地將區域分割成四個子區域（以整個圖像作爲一個區域開始），直到我們的所有子區域均勻標準得到滿足。很容易看到分割的1-4個條件得到滿足。我們繼續合併以便滿足條件。

在合併步驟中，我們檢查P（R＆我üřĴ）= TRUE對於每兩個相鄰的區域，這兩個區域合併。我們重複這一步驟，直到沒有必要進行更改。現在我們滿足了所有的條件，我們將我們的圖像分割成分區域。

僞

這裏是拆分和合並算法的僞代碼：

  1. 初始化：我們只有一個大的區域（整個圖像）。
  2. 拆分：如果P（R i）= TRUE繼續下一步。否則，將R i細分爲四個子區域並對它們執行步驟2。
  3. 合併：若R 我和R Ĵ是鄰居和P（R 我 UR Ĵ）= TRUE，合併的兩個區域，比重複步驟3。如果沒有這樣的區域，我們完了。

來源

2011-08-18 10:22:36 WebMonster

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-06 13:38:20 nkint

+0

如果我正確理解合併的實現不符合圖像空間中相鄰區域可能具有不同父級或在[在此描述]的金字塔結構中處於不同級別（即大小不同）的要求， （http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARBLE/medium/segment/split.htm）。但是，這很重要，我們應該意識到這一點。 –

相關問題

 相關問題