बाहरी आकृति का उपयोग करके छवियों को तुरंत चिह्नित करें

लेख में मैं आपको बताऊंगा कि बाइनरी रास्टर पर कनेक्ट की गई वस्तुओं को कैसे जल्दी से सूचीबद्ध किया जाए। हमने छवियों और ग्रंथों की मान्यता के लिए इस एल्गोरिथ्म का उपयोग किया; यह उच्च प्रसंस्करण गति (3200x2400 तक की तस्वीरों में, कुछ आरक्षणों के साथ, मिलीसेकंड में बाहर काम करता है) और समझने में आसान (कुछ C ++ ज्ञान के साथ) में समान है। मैं ध्यान देता हूं कि मूल छवि को एल्गोरिथ्म द्वारा "रीड-ओनली" के रूप में व्याख्या की जाएगी (क्यों अन्य तरीकों से काम कर सकते हैं) को बिगाड़ें, और इस संबंध में, एल्गोरिथ्म को थोड़ी मात्रा में अतिरिक्त मेमोरी की आवश्यकता होगी। इसके अलावा, बाहरी आकृति छवियों के विश्लेषण और वैश्वीकरण के लिए एक उपयोगी वस्तु है।


तो, कार्य: मूल छवि (छवि बिंदुओं की एक सरणी) को रूपरेखा की सूची में बदलने के लिए। एक पथ एक छवि के जुड़े हिस्से के लिए बस बाहरी बिंदुओं का एक सेट है। उदाहरण के लिए, एक भरे हुए सर्कल के लिए एक समोच्च सभी बाहरी बिंदुओं से प्राप्त एक सर्कल है।

आठ-जुड़ाव का उपयोग किया जाता है, अर्थात, दो बिंदु जुड़े हुए हैं यदि वे दिशाओं के संबंध में पड़ोसी हैं, बाएं-दाएं-नीचे और तिरछे। इस प्रकार, प्रत्येक बिंदु में अधिकतम आठ पड़ोसी हो सकते हैं।

छोटी तैयारी

हम एक एल्गोरिथ्म का निर्माण शुरू करते हैं जो निम्न संरचना के साथ किसी वस्तु के दिए गए प्रारंभिक बाहरी बिंदु से काफी कुशलता से एक समोच्च प्राप्त करता है:

class Contour : public Points
{
// references to the constructor params
const Image& SourceImage;
ImageMap& CurrentImageMap;

public :
/* here we assume that image is coherent in any of 8 ways,
* so if the pixel will not have neighbor in any of 4 diagonal and 4 straight directions
* then it will be considered as separate image part */

// extract contour and mark all coherent points on image map
Contour( const Image& img, ImageMap& map, const Point& start);

private :
// private methods for contour pass implementation only
void passDownLeft(Point& p, bool InvertedAxis = false );
Point movePoint( const Point& src, int x, int y, bool InvertedAxis = false );
Point commitPoint( const Point& p);
};

यहां सभी आवश्यक वस्तुएं और विधियां हैं जिन पर हम विचार करेंगे। कंस्ट्रक्टर संदेह से परे है, SourceImage भी।

ImageMap क्या है? वास्तव में, समोच्च के निर्माण के लिए एल्गोरिदम को किसी भी तरह से बिंदुओं को चिह्नित करना चाहिए ताकि उनकी दोहराया यात्रा को रोका जा सके, इसलिए, विचार किए जाने वाले बिंदु उस वस्तु की संख्या के साथ चिह्नित होंगे, जिसके वे संबंधित हैं।

ऐसा लगता है कि इसके लिए उतनी ही स्मृति की आवश्यकता होगी जितनी मूल छवि में होती है, लेकिन हम एक अधिक कुशल संरचना का उपयोग करेंगे। यह उन बिंदुओं पर मेमोरी बर्बाद करने का कोई मतलब नहीं है जो समोच्च से संबंधित नहीं हैं या इसके अंदर झूठ नहीं है, इसलिए मैं केवल छोटे ओवरहेड के साथ सीमा बिंदुओं को संग्रहीत करना चाहता हूं और उन्हें जल्दी से संबोधित करने में सक्षम हूं।


संरचना एसटीईपी ² आकार के छवि ब्लॉकों के सूचकांक पर आधारित है। सूचकांक अपने आप में एक्स / एसटीईपी * वाई / एसटीईपी के ब्लॉक के लिंक की एक सरणी है, जहां एक्स और वाई मूल छवि का संकल्प हैं। लेखन के लिए एक ब्लॉक का उपयोग करते समय, इसे मेमोरी में आवंटित किया जाता है और संबंधित सूचकांक तत्व को इसके सूचक के साथ चिह्नित किया जाता है। सबसे खराब स्थिति में, यदि हम प्रत्येक (n * STEP, m * STEP) बिंदु को चिह्नित करते हैं, तो हमें चित्र के आकार के बराबर एक मेमोरी उपयोग मिलता है, लेकिन औसतन हम 50-90% मेमोरी बचाते हैं। इंडेक्सिंग, आपने अनुमान लगाया, यह एसटीईपी द्वारा निर्देशांक को विभाजित करके किया जाता है, और यदि एसटीईपी दो की शक्ति है, तो यह उल्लेखनीय रूप से जल्दी काम करता है।

वैसे, एल्गोरिथ्म को निष्पादित करने के बाद, छवि मानचित्र छवि पर वस्तुओं को सूचीबद्ध करने के कार्य का परिणाम है।

समोच्च विधि को समोच्च में जोड़ने के लिए और वर्तमान समोच्च के साथ ImageMap को जोड़ने के लिए उपयोग किया जाता है:

Point Contour::commitPoint( const Point& p)
{
if (!CurrentImageMap.isAssigned(p) && SourceImage.isFilled(p))
{
CurrentImageMap.assignSegment(p, this );
push_back(p);
}
return p;
}


बेशक, ये कार्यान्वयन विवरण हैं, लेकिन यहां सब कुछ सरल है और इसका पुन: उपयोग किया जा सकता है। MovePoint फ़ंक्शन भी काफी सरल है, यह बस निर्दिष्ट वेतन वृद्धि को बिंदु पर जोड़ता है:

Point Contour::movePoint( const Point& src, int x, int y, bool InvertedAxis)
{
Point p = src;
if (InvertedAxis)
{
x = -x;
y = -y;
}
pX += x;
pY += y;
return p;
}


InvertedAxis पैरामीटर, जैसा कि आप अनुमान लगा सकते हैं, बस वेतन वृद्धि को विपरीत में बदल देता है (यह बाद में काम आएगा)।

एल्गोरिथ्म कोर

खैर, अब दिलचस्प है। वास्तव में, बाईपास ही कार्य करता है: पासडाउन लॉफ्ट। दिए गए शुरुआती बिंदु के लिए, हम ऑब्जेक्ट के चारों ओर जाना चाहते हैं, नीचे जा रहे हैं, और यदि संभव हो तो बाईं ओर।

जबकि हम ऑब्जेक्ट के भीतर हैं (यानी वर्तमान बिंदु का रंग पृष्ठभूमि रंग के बराबर नहीं है):

• वर्तमान एक के सापेक्ष एक बिंदु नीचे चलते हैं।
• यदि बाईं ओर, नए वर्तमान के संबंध में, भरा हुआ है, तो हम भाग्यशाली हैं, बाईं ओर "स्टॉप" पर जाएं। यदि सबसे बाईं ओर का बिंदु भरा है, तो हमने एक आत्म-चौराहा ढूंढ लिया है और चक्कर से बाहर निकलें।
• यदि नहीं भरा है, तो दाईं ओर जाएं जब तक हम भरे हुए बिंदु तक नहीं पहुंचते।

यह काफी सरल लगता है, लेकिन सटीक कार्यान्वयन थोड़ा अधिक जटिल लगता है:

void Contour::passDownLeft(Point& p, bool InvertedAxis)
{
while (SourceImage.isInside(p))
{
commitPoint(p);

// step one point down
p = movePoint(p, 0,1, InvertedAxis);

// select one of neighbors which is filled, prefer left one...
Point left = movePoint(p, -1,0, InvertedAxis);
if (SourceImage.isFilled(left))
{
p = commitPoint(left);
// ...and shift left as many as possible
while (SourceImage.isInside(p))
{
Point left = movePoint(p, -1,0, InvertedAxis);
if (!SourceImage.isFilled(left))
break ; // no more left neighbors

p = commitPoint(left);

Point up = movePoint(p, 0,-1, InvertedAxis);
if (SourceImage.isFilled(up))
return ; // crossed inside area
}
}
else
{
// selection still unfilled...
while (SourceImage.isInside(p) && !SourceImage.isFilled(p))
{
// ...shift right by connected points and test again
Point right = movePoint(p, 1,0, InvertedAxis);
Point rightUp = movePoint(right, 0,-1, InvertedAxis);
if (!SourceImage.isFilled(rightUp))
return ; // no more bottom right neighbors
commitPoint(rightUp);
p = commitPoint(right);
}
}
}
}

यदि कोई बिंदु छवि के भीतर स्थित है तो इनसाइड फ़ंक्शन यह जांचता है कि कहीं उसकी सीमा से बाहर न जाए।

परीक्षण चित्र पर इस बाईपास को लॉन्च करने से (हरे रंग के बिंदु प्रत्येक वस्तु को बायपास करने के लिए शुरुआती बिंदु हैं), जैसा कि अपेक्षित था, हमें कोई भी अंतर्विरोध नहीं मिला, क्योंकि निर्माण प्रक्रिया प्रत्येक ऑब्जेक्ट के निम्नतम बिंदुओं के खिलाफ टिकी हुई है। इसलिए, ऐसा एक फ़ंक्शन पर्याप्त नहीं है। लेकिन, आप ऊपर और दाएं तरफ समोच्च को पूरक कर सकते हैं, जो इस मामले के लिए प्रदान किए गए InvertedAxis ध्वज द्वारा आसानी से प्राप्त किया जाता है! इस प्रकार, अंत में छोड़ दिया गया निर्माणकर्ता समोच्च निर्माण एल्गोरिथ्म में जोड़ देगा:

ontour::Contour( const Image& img, ImageMap& map, const Point& start)
: SourceImage(img), CurrentImageMap(map)
{
bool doneSomething = true ;
Point p = start;
for ( int iter = 0; doneSomething; iter++)
{
size_t count = size();
passDownLeft(p, iter % 2 == 1);
doneSomething = size() > count;
}
}


हम वैकल्पिक बाएँ-दाएँ और दाएँ-बाएँ, जब तक कि यह पथ में नए बिंदुओं को जोड़ता है।

तो, हमें इस समोच्च के बिंदुओं की संख्या के सापेक्ष, किसी दिए गए छवि ऑब्जेक्ट के लिए बाहरी समोच्च के सभी बिंदुओं को सूचीबद्ध करने की एक कार्य पद्धति मिली है।

आरंभिक अंकों की गणना

स्रोत छवि से आकृति के निर्माण के लिए सभी शुरुआती बिंदुओं को खोजने के लिए केवल एक चीज बची है:

void Vectorization::getContours()
{
Point p(0,0); // line-by-line scan to extract contours of objects
for (pY = 0; pY < SourceImage.getHeight(); p.Y++)
{
for (pX = 0; pX < SourceImage.getWidth(); p.X++)
{
if (SourceImage.isFilled(p) && !ImageMap.isAssigned(p))
{
// that pixel is unprocessed yet, so extract the contour starting from it
Contour* c = new Contour(SourceImage, ImageMap, p);
// add new contour
ContoursStorage.push_back( c );
}
}
}
}

अब तक यह एल्गोरिथम का सबसे धीमा हिस्सा है: आखिरकार, आपको छवि के प्रत्येक बिंदु पर जाने की आवश्यकता है।

लेकिन इसका अनुकूलन व्यावहारिक रूप से सतह पर भी है: हम उसी इंडेक्स संरचना का उपयोग करेंगे जब छवि मानचित्र को संग्रहीत करते हुए, छवि को आकार STEP ^{2 के} ब्लॉक में विभाजित किया जाएगा।

void Vectorization::getContoursOptimized()
{
Point pIndex(0,0); // step-by-step scan
for (pIndex.Y = 0; pIndex.Y < SourceImage.getHeight(); pIndex.Y += STEP)
{
for (pIndex.X = 0; pIndex.X < SourceImage.getWidth(); pIndex.X += STEP)
{
if (!SourceImage.isEmptyIndex(pIndex))
{
Point pLocal = pIndex;
for (pLocal.Y = pIndex.Y ; pLocal.Y < STEP; pLocal.Y++)
{
for (pLocal.X = pIndex.X ; pLocal.X < STEP; pLocal.X++)
{
if (SourceImage.isFilled(pLocal))
{
if (Map.isAssigned(pLocal))
{
pLocal.X = dynamic_cast<Contour*>(Map.getSegment(pLocal))->getMaxX(pLocal.Y);
break ; /* skip already processed points by getting the max contour X for the specified Y */
}
// that pixel is unprocessed yet, so extract the contour starting from it
Contour* cntr = new Contour(SourceImage, Map, pLocal);
// add new contour
ContoursStorage.push_back( cntr ) ;
}
}
}
}
}
}
}

इस एल्गोरिथ्म की जटिलता छवि वस्तुओं के लिए बाहरी आकृति के बिंदुओं की संख्या के लिए आनुपातिक है।

चाल

अंतिम तथ्य से यह इस प्रकार है कि यह विधि आम तौर पर उन छवियों पर बहुत अच्छी नहीं होती है जहां व्यावहारिक रूप से जुड़े बिंदुओं का कोई समूह नहीं होता है, जबकि बिंदुओं को भरना पूर्ण संभव के करीब है (25% - प्रत्येक समन्वय में प्रत्येक दूसरा बिंदु भरा जाता है, बाकी - कोई)।

लेकिन छवि प्रसंस्करण समस्याओं के दृष्टिकोण से, ऐसी तस्वीरें सिर्फ शोर हैं, जो प्रारंभिक फिल्टर द्वारा आसानी से कट जाती हैं। तो सब कुछ ठीक है :)