छवि विभाजन - विभाजन और विलय (Quadtrees)

Question

क्या छवि विभाजन के विभाजन और विलय विधि के लिए कोई कार्यान्वयन है? किसी भी सलाह की सराहना की जाएगी।

Answer 1

किस विभाजन के बारे में है?

सेगमेंटेशन का मतलब है कि आपकी छवि का विभाजन कई जुड़े क्षेत्रों में है। असल में, आप क्षेत्र की दो परिभाषाओं के साथ विभाजन कर सकते हैं: आप एक क्षेत्र को समान पिक्सेल के समूह के रूप में परिभाषित कर सकते हैं, या विघटन (किनारों) से घिरे जुड़े पिक्सेल के सेट के रूप में परिभाषित कर सकते हैं। विभाजन और विलय पहले दृष्टिकोण का उपयोग करता है।

गणितीय बोल: यदि आपके सम्पूर्ण छवि पिक्सल (आर कहा जाता है) के सेट का प्रतिनिधित्व करती है की तुलना में आप इस तरह के रूप

1. विभाजन पूरा हो गया है सबसेट प्राप्त करना चाहते हैं, तो सभी उपक्षेत्रों पूरे करने के लिए योग सभी क्षेत्रों के आर संघ आर यू.आर. यू ... यू.आर. _n = आर
2. आर _मैं जुड़ा हुआ है है।
3. क्षेत्र अलग हैं। आर _मैं ∩ आर _जे = ∅ यह देखते हुए कि मैं ≠ जे
4. क्षेत्र समान गुण होते हैं। यह homogenity मानदंड (पी) नामक एक समारोह द्वारा व्यक्त किया जा सकता है। इसे दिए गए क्षेत्र के सदस्यों के लिए सत्य और अन्य सभी क्षेत्रों के लिए गलत देना चाहिए।
5. पड़ोसी क्षेत्रों को विलय नहीं किया जा सकता है। सभी क्षेत्रों के लिए पी (आर _i यू आर _जे) = गलत दिया गया है कि मैं ≠ जे।

एल्गोरिदम क्या विभाजन और विलय के बारे में है?

तो सबसे पहले, हमें एक होमोजेनिटी मानदंड चुनना होगा। एक होमोजेनिटी मानदंड वैश्विक हो सकता है (पूरे क्षेत्र के आधार पर) या स्थानीय (क्षेत्र की एक छोटी सी खिड़की के आधार पर, और यदि यह सभी खिड़कियों के लिए सच है, तो यह क्षेत्र के लिए सच है)। एक साधारण उदाहरण औसत से विचलन हो सकता है जो थ्रेसहोल्ड से छोटा होना चाहिए। और इसके लिए; पी _i ∈ आर _i: | पी _i - μ | ≤ एफ * σ।

विभाजित और मर्ज एल्गोरिदम में दो चरण हैं: विभाजन, और विलय चरण। विभाजित चरण में हम क्षेत्रों को चार subregions (पूरी छवि के साथ एक क्षेत्र के रूप में शुरू) में विभाजित करते हैं जब तक कि हमारे homogenity मानदंड सभी subregions में पूरा नहीं हो जाता है। यह देखना आसान है कि विभाजन की 1-4 स्थितियों को पूरा किया जाता है। हम 5 ^वें स्थिति को संतुष्ट करने के लिए चरण को मर्ज करने के लिए आगे बढ़ते हैं।

मर्ज चरण में हम जांच लेंगे कि पी (आर _मैं यू आर _जे) = प्रत्येक दो पड़ोसी क्षेत्रों के लिए सही है, और दोनों क्षेत्रों के विलय। हम इस कदम को दोहराते हैं जब तक कि कोई और बदलाव आवश्यक न हो। अब हम सभी शर्तों को पूरा करते हैं, हमने अपनी छवि को उप-वर्गों में विभाजित किया था।

1. Init:

   स्यूडोकोड

   यहाँ विभाजित है और एल्गोरिथ्म मर्ज करने के लिए एक स्यूडोकोड है हम केवल एक बड़ा क्षेत्र (संपूर्ण चित्र) है।

2. अलग करना: पी (आर _मैं) सही = तो अगले कदम के लिए आगे बढ़ें। अन्यथा आर _मैं से चार उपक्षेत्र का उप-विभाजन और उन पर चरण 2 प्रदर्शन करते हैं।
3. मर्ज: अगर आर _मैं और आर _जे पड़ोसियों और पी रहे हैं (आर _मैं यू.आर. _जे) = सही, दोनों क्षेत्रों के विलय, दोहराने कदम 3. से ऐसी कोई क्षेत्रों हम कर रहे हैं देखते हैं, तो ख़त्म होना।

Answer 2

एक विभाजित मर्ज विभाजन एल्गोरिथ्म यहां लागू किया गया था: http://www.uni-koblenz.de/~lb/lb_downloads

Answer 3

यह मेरा कार्यान्वयन है। मैं एक सी ++/ओपनसीवी गुरु नहीं हूं इसलिए अगर कोई इस स्क्रिप्ट को अनुकूलित करने के लिए कुछ रास्ता ढूंढता है तो कृपया टिप्पणी जोड़ें!

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