गंदे आयताकारों का इष्टतम सेट

Question

मैं विशिष्ट प्रोग्रामिंग भाषा से स्वतंत्र, यहां एक एल्गोरिदम खोज रहा हूं।

समस्या:

हम एक 2-आयामी प्रदर्शन क्षेत्र (लगता है पिक्सल के सरल बफर) है। समय-समय पर, कुछ पिक्सल बदल गए हैं। हमें आयतों का एक सेट ढूंढना होगा जो सभी परिवर्तित पिक्सल को समाहित करता है।

यह तुच्छ होगा, लेकिन अवांछनीय, एक एकल, संभवतः बड़े, आयत है कि सभी बदली हुई पिक्सल समाहित गणना करने के लिए। हमारे पास एकाधिक, छोटे, तंग-फिटिंग आयताकार निर्दिष्ट न्यूनतम आकार (जो एक चर है जो बदल सकता है) के बजाय होगा।

उदाहरण के लिए, मान लीजिए कि पूरे प्रदर्शन क्षेत्र के भीतर, में कुछ पिक्सल ऊपरी बाएँ कोने बदल गया है और निचले दाएं कोने में एक कुछ पिक्सल बदल दिया है। हम पूरे क्षेत्र के एकल गंदे आयत की गणना नहीं करना चाहते हैं - हम इसके बजाय दो गंदे आयत चाहते हैं: ऊपरी में एक छोटा सा छोड़ दिया गया है और निचले में एक छोटा सा दाएं है।

प्रदर्शन महत्वपूर्ण है, इसलिए यह सवाल है।

यह समस्या हर समय फसल होती है, निश्चित रूप से वीडियो कोडेक्स और दूरस्थ डेस्कटॉप संपीड़न क्षेत्रों में, मुझे लगता है। मेरे मामले में, यह ग्राफिकल छवि मैनिप्लेशंस के दौरान आवर्ती समस्या है जिसमें एक साथ साझा क्षेत्र में एक साथ कई उपयोगकर्ता शामिल होते हैं।

क्या किसी को इसके लिए प्रकाशित एल्गोरिदम पता है या अतीत में उपयोग किए गए समाधान के बारे में पता है?

धन्यवाद!

Answer 1

मेरा विचार, दो निर्णय विकल्पों के साथ:

मैं स्यूडोकोड किसी तरह का में लिखा था ..

पहला विकल्प आप एक प्रतिशत है कि अपने क्षेत्र के कम से कम गंदा पिक्सल पूरा करने के लिए पालन करना चाहिए पर फैसला के लिए

मूल रूप से गिनती।

और दूसरे विकल्प के लिए, आप तय करते हैं कि इस क्षेत्र में इस कारक या गंदे पिक्सल में अंतर बहुत अधिक बदल जाता है यदि आप इस पिक्सेल को शामिल करने के लिए विस्तार करते हैं।

struct DirtyPixelArea 
{ 
    Vec2 topLeft; 
    Vec2 size; 
    list<Vec2> dirtyPixels; 

    void AddPixelToArea(); 

    int Area(); 
    int DirtyPixelsArea(); // sums all dirty pixels in area 
}; 

list<DirtyPixelArea> dirtyPixelsAreaList 

void add_dirty_pixel(Vec2 dirtyPixel) 
{ 
    closest_area = find_closest_area_to_pixel(dirtyPixel).copy(); 

    //option 1 - begin 

    closest_area.add_dirty_pixel(dirtyPixel); 

    if (closest_area.DirtyPixelsArea() > (closest_area.Area() * 0.25)) // you can experiment on choosing your own dirty pixel factor 
    { 
     update_area_in_list(closest_area); 
    } 
    else 
    { 
     new_area = new DirtyPixelArea(); 
     new_area.AddPixelToArea(dirtyPixel); 
     add_area_in_list(new_area); 
    } 

    //option 1 - end 

    // option 2 - begin 
    original_area = find_closest_area_to_pixel(dirtyPixel); 
    closest_area.add_dirty_pixel(dirtyPixel) 

    original_area_factor = original_area.DirtyPixelsArea()/original_area.Area(); 
    closest_area_factor = closest_area.DirtyPixelArea()/closest_area.Area(); 

    if (closest_area_factor/original_area_factor > 0.5) 
    { 
     update_area_in_list(closest_area); 
    } 
    else 
    { 
     new_area = new DirtyPixelArea(); 
     new_area.AddPixelToArea(dirtyPixel); 
     add_area_in_list(new_area); 
    } 

    // option 2 - end 

} 

Answer 2

R-tree और quadtree डेटा संरचनाओं में देखो।

Answer 3

स्क्रीन वीडियो/रिमोट डेस्कटॉप कोडेक्स आम तौर पर स्क्रीन को टाइल्स में विभाजित करते हैं और फिर बदले गए टाइल्स के लिए बिटमैप्स ट्रांसमिट करते हैं। टाइल छवियां आमतौर पर तब ZLIB- संपीड़ित होती हैं।

इस पर सुधार करने के कई तरीके हैं, उदा।

• प्रत्येक टाइल अपने स्वयं के सीमांकन आयत के पिछले सामग्री के साथ
• प्रधानमंत्री कंप्रेसर दें, उस टाइल में बदली हुई पिक्सल को कवर (पूरे टाइल फिर से संचारण करता है, तो केवल कुछ ही पिक्सल बदल दिया है से बचने के लिए।) टाइल (यह बहुत आप रिकॉर्डिंग कर रहे एक खिड़की घसीटा जा रहा है या स्प्राइट एक 2D खेल में आगे बढ़ अगर संपीड़न दक्षता में सुधार।)

उदाहरण के लिए एडोब फ्लैश अपने "स्क्रीन वीडियो 2" कोडेक में तीनों तकनीकों का एक संयोजन का उपयोग करता ।

यदि आप संपीड़न का उपयोग नहीं करना चाहते हैं, तो टाइल्स & बाध्यकारी बक्से का संयोजन एक अच्छा समझौता है। जैसे यदि आपके पास विपरीत कोनों पर केवल दो बदलते पिक्सेल हैं, तो केवल दो पिक्सेल अपडेट किए जाएंगे, लेकिन यदि आपके पास बिखरे हुए परिवर्तन वाले क्षेत्र हैं (उदाहरण के लिए टेक्स्ट एडिटर में टाइप करना) परिवर्तन कुछ बड़े आयतों में संयुक्त होते हैं जो शायद अधिक कुशल होते हैं इसे सैकड़ों छोटे आयतों में तोड़ना।)