छवि अपलोड एल्गोरिदम, वीडियो के साथ लोकप्रिय है

अमूर्त

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

पृष्ठभूमि और पूर्वापेक्षाएँ

एक सरल तरीके से, हम संयोजक जोड़े के एक निर्धारित सेट पर जुड़ाव या पड़ोस के संबंध का परिचय देते हैं। हम उन मामलों के बीच अंतर करेंगे जहां एक बिंदु में चार पड़ोसी (छवि 1 ए) हैं और जिस मामले में एक बिंदु में आठ पड़ोसी हैं (छवि 1 ए)।

ऐसा क्यों करें और क्या चुनना है यह चित्र 2 में दिखाया गया है।

चित्रा 2 में, छोटे वर्ग डिजिटल छवि के सशर्त पिक्सेल का प्रतिनिधित्व करते हैं, जबकि काले पिक्सेल दो क्षेत्रों के बीच की सीमा का वर्णन करते हैं - ऊपरी और निचले। हम ऊपरी सफेद क्षेत्र को नीले पेंट से भर देंगे। यदि हम एक बिंदु के लिए केवल 4 पड़ोसियों में प्रवेश करते हैं , तो नीली पेंट काली सीमा (Fig.2b) से नहीं गुजरेगी और निचला क्षेत्र सफेद रहेगा, और यदि हम आठ पड़ोसियों का उपयोग करते हैं, तो काली सीमा सीमा नहीं है, और छलनी - जिसके माध्यम से और पेंट निचले क्षेत्र में फैल गया।

किस तरह की कनेक्टिविटी चुनें? विमान पर, विकल्प छोटा है - या तो 4 या 8 पड़ोसी, और विकल्प मूल समस्या के निर्माण पर निर्भर करता है, लेकिन बहुआयामी अंतरिक्ष में सब कुछ अधिक कठिन है, यह कल्पना करना भी असंभव है, और लेख में हम केवल सपाट मामले पर विचार करेंगे। इस मामले में, हम चार पड़ोसियों के मामले पर विचार करते हैं, जिसे आसानी से आठ के मामले में बढ़ाया जा सकता है।

सभी ने देखा कि कार्लसन की तस्वीर, पेंट में मेरे स्वाद और प्रतिनिधित्व को चित्रित करते हुए, लेख के उद्घोषणा में, किसी तरह से टेढ़ा-मेढ़ा भर गया था, सीमा पर एक काली रूपरेखा है - एक रंगीन क्षेत्र - क्या मेरी आँखें सफेद और ग्रे डॉट्स हैं? यह इस कारण से हुआ कि हमारा कार्लसन बाइनरी कलर में नहीं है, बल्कि ग्रे रंग में है। पहली चीज़ जो हम करते हैं वह इस प्रमुख दोष को दूर करती है और चित्र को बायनेरिज़ करती है, और यह हमारे लिए केवल एक चैनल के साथ काम करने के लिए पर्याप्त है - पहले को लाल होने दें।
तो:

% //
source_image = imread( 'karlson.bmp' );
% //
gray_image = source_image(:,:,1);
% // 0.5
bim=double(im2bw(gray_image, 0.5));
% //
imagesc(bim);

* This source code was highlighted with Source Code Highlighter .

% //
source_image = imread( 'karlson.bmp' );
% //
gray_image = source_image(:,:,1);
% // 0.5
bim=double(im2bw(gray_image, 0.5));
% //
imagesc(bim);

* This source code was highlighted with Source Code Highlighter .
चित्र 3 में हमारे स्लॉपर के पैर को उसके मूल रूप (Fig.3a) और बाइनराइजेशन (Fig.3b) के रूप में दर्शाया गया है, क्योंकि हम देखते हैं कि समोच्च उम्मीद के मुताबिक पतला हो गया है और अब इसमें केवल काले डॉट्स हैं, जिनमें से कुछ गायब हैं।
अगला, हम दो भरने वाले एल्गोरिदम पर विचार करेंगे, लेकिन हम उन्हें पुनरावर्ती रूप से प्रोग्राम नहीं करेंगे (ताकि अतिरिक्त हॉलीवर को नस्ल न करें और ओवरफ्लो से बचें), लेकिन स्टैक पर पुनरावृत्ति का विस्तार करें।
चलो शब्दावली को परिभाषित करते हैं:

• प्रारंभिक बिंदु - एक पिक्सेल जिसमें उपयोगकर्ता पेंट की तरह क्लिक कर सकता है
• पुराना रंग - भरे हुए क्षेत्र का रंग
• नया रंग भरने के बाद क्षेत्र का रंग है।

सरल और धीमी गति से भरने एल्गोरिथ्म

छवि के किनारों को छवि की सीमा भी माना जाएगा।
एल्गोरिथ्म का सार सरल है: वर्तमान बिंदु पर हम जांचते हैं: यदि पुराना रंग - इसे एक नए के साथ बदलें, यदि नया है, तो हम कुछ भी नहीं करते हैं। फिर हम चार पड़ोसियों के लिए एक ही ऑपरेशन करते हैं, जिसका रंग पुराने रंग के बराबर है।
मुझे एक बार पुनरावर्ती कार्यान्वयन के साथ स्रोत कोड चोरी करना है, बस सार प्रदर्शित करने के लिए:

//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4( int x, int y, int newColor, int oldColor)
{
if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion

floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
* This source code was highlighted with Source Code Highlighter .

//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4( int x, int y, int newColor, int oldColor)
{
if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion

floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
* This source code was highlighted with Source Code Highlighter .
मतलाब पर भी और नकली स्टैक के साथ यह कैसा दिखेगा? और यहाँ है कैसे:

%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 48; point.y = 234;
stack = [point];
[wh] = size(bim);
stack_size = [];
mov = avifile( 'karlson_fill2.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
bim(point.x,point.y) = newColor; %

if (point.x+1 <= w && bim(point.x+1,point.y) == oldColor)
newpoint.x = point.x+1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.x-1 > 0 && bim(point.x-1,point.y) == oldColor)
newpoint.x = point.x-1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.y+1 <= h && bim(point.x,point.y+1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y+1;
stack = [stack newpoint];
end;
if (point.y-1 > 0 && bim(point.x,point.y-1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y-1;
stack = [stack newpoint];
end;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
mov = close(mov);
figure; imagesc(bim);
figure; plot(stack_size);

* This source code was highlighted with Source Code Highlighter .

%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 48; point.y = 234;
stack = [point];
[wh] = size(bim);
stack_size = [];
mov = avifile( 'karlson_fill2.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
bim(point.x,point.y) = newColor; %

if (point.x+1 <= w && bim(point.x+1,point.y) == oldColor)
newpoint.x = point.x+1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.x-1 > 0 && bim(point.x-1,point.y) == oldColor)
newpoint.x = point.x-1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.y+1 <= h && bim(point.x,point.y+1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y+1;
stack = [stack newpoint];
end;
if (point.y-1 > 0 && bim(point.x,point.y-1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y-1;
stack = [stack newpoint];
end;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
mov = close(mov);
figure; imagesc(bim);
figure; plot(stack_size);

* This source code was highlighted with Source Code Highlighter .
आप चाय का एक कप ले सकते हैं, जबकि हमारे भौंह की भौं सलेटी रंग की होती है। इसी समय, प्रस्तावित कोड प्रत्येक पुनरावृत्ति पर स्टैक अधिभोग का एक ग्राफ भी खींचेगा, और हम इस पर चर्चा करेंगे। और एक अच्छा बोनस कोड के रूप में - आउटपुट फिलिंग को दर्शाती एक वीडियो क्लिप भी है। मैंने एक भौं के रूप में इतना छोटा विवरण क्यों चुना - क्योंकि कुछ और डालना, उदाहरण के लिए, एक पेट, मटैलब निष्पादन योग्य भाषा की विशेषताएं, समय की एक निश्चित राशि में संभव नहीं है।


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

अल्‍गोरिदम भरें - तेज, पंक्तिबद्ध

पुनरावर्ती एल्गोरिथ्म का सार:
हम एक किनारे से दूसरे किनारे तक वर्तमान लाइन को भरना शुरू करते हैं।
पहले शुरुआती बिंदु से ऊपर और फिर नीचे।
हम प्रारंभिक बिंदु पर लौटते हैं। हम देखते हैं - यदि प्रारंभिक बिंदु के बाईं ओर पुराना रंग है और कोई सीमा नहीं है, तो एक नई लाइन भरें।
हम प्रारंभिक बिंदु पर लौटते हैं। हम देखते हैं - यदि शुरुआती बिंदु के दाईं ओर पुराना रंग है और कोई सीमा नहीं है, तो हम एक नई पंक्ति में भरते हैं।

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

clear all;
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 17; point.y = 143;
stack = [point];
[wh] = size(bim);
stack_size = []; spanLeft = 0; spanRight = 0;

mov = avifile( 'karlson_fill3.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
y1 = point.y;

%
while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
y1 = y1 + 1;
spanLeft = 0; spanRight = 0;
%
while (y1 < h && bim(point.x,y1) == oldColor)
bim(point.x,y1) = newColor; %
if (spanLeft == 0 && point.x > 0 && bim(point.x-1,y1) == oldColor)
newpoint.x = point.x-1; newpoint.y = y1; stack = [stack newpoint];
spanLeft = 1;
elseif (spanLeft == 1 && point.x > 0 && bim(point.x-1,y1) ~= oldColor)
spanLeft = 0;
end;

if (spanRight == 0 && point.x < w && bim(point.x+1,y1) == oldColor)
newpoint.x = point.x+1; newpoint.y = y1; stack = [stack newpoint];
spanRight= 1;
elseif (spanRight == 1 && point.x < w && bim(point.x+1,y1) ~= oldColor)
spanRight = 0;
end;

y1 = y1 + 1;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
end;
mov = close(mov);

* This source code was highlighted with Source Code Highlighter .

clear all;
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 17; point.y = 143;
stack = [point];
[wh] = size(bim);
stack_size = []; spanLeft = 0; spanRight = 0;

mov = avifile( 'karlson_fill3.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
y1 = point.y;

%
while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
y1 = y1 + 1;
spanLeft = 0; spanRight = 0;
%
while (y1 < h && bim(point.x,y1) == oldColor)
bim(point.x,y1) = newColor; %
if (spanLeft == 0 && point.x > 0 && bim(point.x-1,y1) == oldColor)
newpoint.x = point.x-1; newpoint.y = y1; stack = [stack newpoint];
spanLeft = 1;
elseif (spanLeft == 1 && point.x > 0 && bim(point.x-1,y1) ~= oldColor)
spanLeft = 0;
end;

if (spanRight == 0 && point.x < w && bim(point.x+1,y1) == oldColor)
newpoint.x = point.x+1; newpoint.y = y1; stack = [stack newpoint];
spanRight= 1;
elseif (spanRight == 1 && point.x < w && bim(point.x+1,y1) ~= oldColor)
spanRight = 0;
end;

y1 = y1 + 1;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
end;
mov = close(mov);

* This source code was highlighted with Source Code Highlighter .


चित्र 7 में हमारे पास स्टैक ऑक्यूपेंसी का ग्राफ है, लेकिन पहले से ही सामान्य निर्देशांक में। एक नए रंग के साथ पंजे को भरने वाला एक चित्र नीचे प्रस्तावित है। यह उसी तरह से किया जाता है - प्रति सेकंड 50 फ्रेम।

जैसा कि हम इस मामले में देखते हैं, हमारा स्टैक (चित्र 7) भर में भरने के लिए नगण्य है, और हमने कम गहराई से खोज कर एक गति से जीता है।

निष्कर्ष

अंत में, मैं कहना चाहता हूं - सब कुछ, यहां तक ​​कि इस तरह के सरल एल्गोरिदम को स्पष्ट करें, क्योंकि सुंदरता शक्ति है ।
मैं लंबे लेख के लिए और शायद अगले के लिए एक बीज के रूप में माफी मांगता हूं
मैं लेख का लिंक दूंगा। यह मेरे सामने अपरिचित एक और बहुत ही रोचक और बहुत तेजी से भरने वाले एल्गोरिदम का वर्णन करता है। शायद खाली समय के साथ एक नायक है जो इस एल्गोरिदम का विस्तार से और चित्रण के साथ विश्लेषण भी करेगा।
और अगर किसी के पास अधिक शक्तिशाली संसाधन हैं, तो मेरा सुझाव है कि आप कार्लाइंस के पेट को भरें और यहां वीडियो अपलोड करें, अन्यथा मेरे पास धैर्य नहीं है जबकि वीडियो लिखा जा रहा है। इसके लिए लाभ सभी कोड है।

सूत्रों का उपयोग किया

1. Lode Vandevenne, Lode का कंप्यूटर ग्राफिक्स ट्यूटोरियल - लिंक
2. कार्लसन के बारे में रंग पृष्ठ, जो छत पर रहता है, यहां से लिया गया है - लिंक