एफ #, जुड़े छवि घटकों के लिए एल्गोरिथ्म को चिह्नित करना

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

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

परिचय

V के मान के साथ एक जुड़ा हुआ घटक C ऐसे पिक्सेल का एक सेट है जिसमें v का मान होता है और इन पिक्सेल का प्रत्येक जोड़ा v के मान से जुड़ा होता है।

यह लाजिमी लग रहा है, तो चलो बस तस्वीर देखते हैं। हम मानते हैं कि द्विआधारी छवि के अग्रभूमि पिक्सल 1 के रूप में चिह्नित हैं , और पृष्ठभूमि पिक्सेल 0 के रूप में चिह्नित हैं ।

जुड़े हुए घटकों के अंकन एल्गोरिदम के साथ छवि को संसाधित करने के बाद, हमें निम्न चित्र मिलता है। यहां, पिक्सेल के बजाय, जुड़े हुए घटक बनते हैं, जो संख्या में एक दूसरे से भिन्न होते हैं। इस उदाहरण में, 5 घटक पाए गए थे और उनके साथ अलग-अलग संस्थाओं के साथ काम करना संभव होगा।

चित्रा 1: लेबल कनेक्टेड घटक

$$

$$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 2 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 2 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 3 & 3 & 3 & 3 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 3 & 0 & 4 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 0 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 2 & 2 & 2 \end{matrix}$$

ऐसी समस्या को हल करने के लिए इस्तेमाल किए जा सकने वाले दो एल्गोरिदम को नीचे माना जाएगा।

पुनरावर्ती लेबलिंग एल्गोरिथ्म

हम सबसे स्पष्ट के रूप में पुनरावृत्ति-आधारित एल्गोरिथ्म को देखकर शुरू करेंगे। इस तरह के एक एल्गोरिथ्म के संचालन का सिद्धांत निम्नानुसार होगा।

एक लेबल असाइन करें, जिसे हम संबंधित घटकों को चिह्नित करेंगे, प्रारंभिक मूल्य।

1. हम तालिका में सभी बिंदुओं के माध्यम से सॉर्ट करते हैं, समन्वय 0x0 (ऊपरी बाएं कोने) से शुरू होता है। अगले बिंदु को संसाधित करने के बाद, लेबल को एक से बढ़ाएं
2. यदि वर्तमान समन्वय पर पिक्सेल 1 है , तो हम इस बिंदु के सभी चार पड़ोसियों को स्कैन करते हैं (ऊपर, नीचे, दाएं, बाएं)
3. यदि पड़ोसी बिंदु भी 1 है , तो फ़ंक्शन पुनरावर्ती रूप से पड़ोसी को संसाधित करने के लिए खुद को कॉल करता है जब तक कि वह सरणी या 0 की सीमा को हिट नहीं करता है
4. पड़ोसी के पुनरावर्ती प्रसंस्करण के दौरान, एक चेक बनाया जाना चाहिए कि बिंदु पहले से ही संसाधित नहीं हुआ है और वर्तमान मार्कर के साथ चिह्नित है।

इस प्रकार, सरणी में सभी बिंदुओं के माध्यम से छंटनी और प्रत्येक के लिए एक पुनरावर्ती एल्गोरिदम को लागू करना, फिर खोज के अंत में हमें पूरी तरह से चिह्नित तालिका मिलती है। चूँकि इस बात की जाँच है कि क्या किसी दिए गए बिंदु को पहले ही चिह्नित किया जा चुका है, इसलिए प्रत्येक बिंदु पर केवल एक बार कार्रवाई की जाएगी। पुनरावृत्ति की गहराई वर्तमान बिंदु से जुड़े पड़ोसियों की संख्या पर निर्भर करेगी। यह एल्गोरिथ्म उन छवियों के लिए अच्छी तरह से अनुकूल है जिनमें बड़ी छवि नहीं है। यही है, ऐसी छवियां जिनमें पतली और छोटी लाइनें हैं, और बाकी सब एक पृष्ठभूमि छवि है जो संसाधित नहीं होती है। इसके अलावा, इस तरह के एल्गोरिथ्म की गति लाइन-बाय-लाइन एल्गोरिथ्म से अधिक हो सकती है (हम इस लेख में बाद में चर्चा करेंगे)।

चूंकि द्विआयामी द्विआधारी छवियां दो आयामी मैट्रिक्स हैं, एल्गोरिथ्म लिखते समय, मैं मैट्रिसेस की अवधारणाओं के साथ काम करूंगा, जिसके बारे में मैंने एक अलग लेख बनाया है, जिसे यहां पढ़ा जा सकता है।

रैखिक बीजगणित के सिद्धांत से मैट्रिस के साथ काम करने के उदाहरण का उपयोग करके कार्यात्मक प्रोग्रामिंग

आइए हम एफ # -फंक्शन पर विस्तार से विचार करें और विश्लेषण करें । जुड़ा द्विआधारी छवि घटकों के लिए पुनरावर्ती लेबलिंग एल्गोरिथ्म

let recMarkingOfConnectedComponents matrix =

        let copy = Matrix.clone matrix

        let (|Value|Zero|Out|) (x, y) = 
            if x < 0 || y < 0
                || x > (copy.values.[0, *].Length - 1)
                || y > (copy.values.[*, 0].Length - 1) then
                Out
            else
                let row = copy.values.[y, *]
                match row.[x] with
                    | 0 -> Zero
                    | v -> Value(v)

        let rec markBits x y value =
            match (x, y) with
            | Value(v) ->
                if value > v then
                    copy.values.[y, x] <- value
                    markBits (x + 1) y value
                    markBits (x - 1) y value
                    markBits x (y + 1) value
                    markBits x (y - 1) value
            | Zero | Out -> ()

        let mutable value = 2
        copy.values
        |> Array2D.iteri (fun y x v -> if v = 1 then
                                            markBits x y value
                                            value <- value + 1)

        copy 

हम recMarkingOfConnectedCompords फ़ंक्शन की घोषणा करते हैं , जो मैट्रिक्स के एक रिकॉर्ड में पैक मैट्रिक्स के दो-आयामी सरणी लेता है। फ़ंक्शन मूल सरणी को नहीं बदलेगा, इसलिए पहले इसकी एक प्रति बनाएं, जिसे एल्गोरिथ्म द्वारा संसाधित किया जाएगा और वापस आ जाएगा।

let copy = Matrix.clone matrix

सरणी के बाहर अनुरोधित बिंदुओं के सूचकांकों के चेक को सरल बनाने के लिए, एक सक्रिय टेम्पलेट बनाएं जो तीन में से एक मान लौटाता है।

आउट - अनुरोधित सूचकांक द्वि-आयामी सरणी से परे चला गया -
शून्य में पृष्ठभूमि पिक्सेल (शून्य के बराबर)
मान शामिल है - अनुरोधित सूचकांक सरणी के भीतर है।

यह टेम्पलेट अगले पुनरावर्तन फ्रेम में छवि बिंदु के निर्देशांक की जांच को सरल करेगा:

let (|Value|Zero|Out|) (x, y) = 
    if x < 0 || y < 0
        || x > (copy.values.[0, *].Length - 1)
        || y > (copy.values.[*, 0].Length - 1) then
        Out
    else
        let row = copy.values.[y, *]
        match row.[x] with
            | 0 -> Zero
            | v -> Value(v)

MarkBits फ़ंक्शन को पुनरावर्ती घोषित किया गया है और वर्तमान पिक्सेल और उसके सभी पड़ोसियों (ऊपर, नीचे, बाएं, दाएं) को संसाधित करने का कार्य करता है:

let rec markBits x y value =
    match (x, y) with
    | Value(v) ->
        if value > v then
            copy.values.[y, x] <- value
            markBits (x + 1) y value
            markBits (x - 1) y value
            markBits x (y + 1) value
            markBits x (y - 1) value
    | Zero | Out -> ()

फ़ंक्शन निम्न मापदंडों को एक इनपुट के रूप में स्वीकार करता है:

x - पंक्ति संख्या
y - स्तंभ संख्या
मान - पिक्सेल

का मिलान करने के लिए वर्तमान लेबल मान / निर्माण और सक्रिय टेम्पलेट (ऊपर) का उपयोग करके , पिक्सेल निर्देशांक की जाँच की जाती है ताकि यह द्वि-आयामी से आगे न जाए। सरणी। यदि बिंदु दो-आयामी सरणी के अंदर है, तो हम प्रारंभिक जांच करते हैं ताकि उस बिंदु को संसाधित न करें जो पहले से ही संसाधित हो चुका है।

if value > v then

अन्यथा, अनंत पुनरावृत्ति होगी और एल्गोरिथ्म काम नहीं करेगा।

अगला, वर्तमान मार्कर मान के साथ बिंदु को चिह्नित करें:

copy.values.[y, x] <- value

और हम अपने सभी पड़ोसियों की प्रक्रिया करते हैं, उसी फ़ंक्शन को पुन: कॉल कर रहे हैं:

markBits (x + 1) y value
markBits (x - 1) y value
markBits x (y + 1) value
markBits x (y - 1) value

एल्गोरिथ्म को लागू करने के बाद, इसका उपयोग किया जाना चाहिए। अधिक विस्तार से कोड पर विचार करें।

let mutable value = 2
copy.values
|> Array2D.iteri (fun y x v -> if v = 1 then
                                    markBits x y value
                                    value <- value + 1) 

छवि को संसाधित करने से पहले, लेबल का प्रारंभिक मान सेट करें, जो पिक्सेल के जुड़े समूहों को चिह्नित करेगा।

let mutable value = 2

तथ्य यह है कि द्विआधारी छवि में सामने के पिक्सल पहले से ही 1 पर सेट हैं , इसलिए यदि लेबल का प्रारंभिक मूल्य भी 1 है , तो एल्गोरिथ्म काम नहीं करेगा। इसलिए, लेबल का प्रारंभिक मूल्य 1 से अधिक होना चाहिए । समस्या को हल करने का एक और तरीका है। एल्गोरिथ्म शुरू करने से पहले, -1 के शुरुआती मूल्य के साथ सभी पिक्सल को 1 पर सेट करें । तब हम मान को 1 पर सेट कर सकते हैं । यदि आप चाहते हैं तो आप इसे स्वयं कर सकते हैं। अगला निर्माण, Array2D.iteri फ़ंक्शन का उपयोग करके, सरणी में सभी बिंदुओं पर पुनरावृत्त करता है , और यदि खोज के दौरान एक बिंदु 1 पर सेट है

, तो इसका मतलब है कि यह संसाधित नहीं है और इसके लिए आपको पुनरावर्ती फ़ंक्शन चिह्न को कॉल करने की आवश्यकता है वर्तमान लेबल मान के साथ। एल्गोरिथ्म द्वारा 0 पर सेट सभी पिक्सेल को अनदेखा किया जाता है।

बिंदु को पुन: संसाधित करने के बाद, हम यह मान सकते हैं कि यह जुड़ा हुआ समूचा समूह चिह्नित होने की गारंटी है और आप इसे अगले जुड़े बिंदु पर लागू करने के लिए लेबल मान को 1 से बढ़ा सकते हैं ।

इस तरह के एक एल्गोरिथ्म के आवेदन के एक उदाहरण पर विचार करें।

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t = System.Diagnostics.Stopwatch.StartNew()
let R = Algorithms.recMarkingOfConnectedComponents A
t.Stop()

printfn "origin =\n %A" A.values
printfn "rec markers =\n %A" R.values
printfn "elapsed recurcive = %O" t.Elapsed 

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]

rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]

elapsed recurcive = 00:00:00.0037342

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

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

दुर्भाग्य से, टेल रिकर्सन के सिद्धांत को इस एल्गोरिथम में लागू नहीं किया जा सकता है, क्योंकि टेल रिकर्सन की दो आवश्यकताएं हैं:

1. प्रत्येक पुनरावर्तन फ़्रेम को परिकलन करना होगा और परिणाम को संचायक में जोड़ना होगा, जो स्टैक के नीचे प्रेषित होगा।
2. एक पुनरावर्ती फ़्रेम में एक से अधिक पुनरावर्ती फ़ंक्शन कॉल नहीं होना चाहिए।

हमारे मामले में, पुनरावर्तन कोई अंतिम गणना नहीं करता है, जिसे पुनरावृत्ति के अगले फ्रेम में पारित किया जा सकता है, लेकिन बस एक द्वि-आयामी सरणी को संशोधित करता है। सिद्धांत रूप में, इसे केवल एक ही संख्या को वापस करके परिवृत्त किया जा सकता है, जिसका अपने आप में कोई मतलब नहीं है। हम 4 पुनरावर्ती कॉल भी करते हैं, क्योंकि हमें बिंदु के सभी चार पड़ोसियों को संसाधित करने की आवश्यकता है।

खोजों को संयोजित करने के लिए डेटा संरचना के आधार पर जुड़े घटकों को चिह्नित करने के लिए शास्त्रीय एल्गोरिदम

एल्गोरिथ्म का एक अन्य नाम भी है, "प्रगतिशील अंकन का एल्गोरिदम" और यहां हम इसे पार्स करने का प्रयास करेंगे।

. . . , , .

ऊपर दी गई परिभाषा और भी अधिक भ्रामक है, इसलिए हम एल्गोरिथ्म के सिद्धांत से एक अलग तरीके से निपटने और दूर से शुरू करने की कोशिश करेंगे।

सबसे पहले, हम वर्तमान बिंदु के चार - जुड़े और आठ-जुड़े पड़ोस की परिभाषा से निपटेंगे । नीचे दिए गए चित्रों को देखें कि यह क्या है और क्या अंतर है।

चित्रा 2: चार जुड़े घटक
\ शुरू {मैट्रिक्स} चित्रा 2: आठ से जुड़े घटक \ शुरू {मैट्रिक्स} पहली तस्वीर चार-जुड़े घटक दिखाती है $$\begin{matrix} & 1 & \\ 2 & * & 3 \\ & 4 & \end{matrix}$$


$$\begin{matrix} 1 & 2 & 3 \\ 4 & * & 5 \\ 6 & 7 & 8 \end{matrix}$$
अंक, इसका मतलब है कि एल्गोरिथ्म वर्तमान बिंदु (बाएं, दाएं, ऊपर और नीचे) के 4 पड़ोसियों को संसाधित करता है। तदनुसार, एक बिंदु के आठ-जुड़े घटक का मतलब है कि इसमें 8 पड़ोसी हैं। इस लेख में, हम चार-जुड़े घटकों के साथ काम करेंगे।

अब आपको यह पता लगाने की आवश्यकता है कि कुछ सेटों पर निर्मित खोज के संयोजन के लिए डेटा संरचना क्या है ?

उदाहरण के लिए, मान लें कि हमारे पास दो सेट हैं

$$

$$(1, 2, 3, 4, 8) (5, 6, 7)$$

ये सेट निम्नलिखित पेड़ों के रूप में आयोजित किए जाते हैं:





ध्यान दें कि पहले सेट में नोड्स 3 मूल है, और दूसरे नोड्स में 6.

अब हम खोज-संघ के लिए डेटा संरचना पर विचार करते हैं, जिसमें ये दोनों सेट होते हैं, और उनके पेड़ की संरचना भी व्यवस्थित करते हैं। ।

चित्र 4: खोज-संघ
\ _ {मैट्रिक्स} के लिए डेटा संरचना ऊपर दी गई तालिका को ध्यान से देखें और ऊपर दिखाए गए सेट पेड़ों के साथ एक संबंध खोजने की कोशिश करें। तालिका को ऊर्ध्वाधर स्तंभों में देखा जाना चाहिए। यह देखा गया है,पहली पंक्ति में संख्या 3 , संख्या 0 से मेल खाती है $$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 0 & 3 & 7 & 7 & 0 & 3 \end{matrix}$$

दूसरी पंक्ति में। और पहले पेड़ में, संख्या 3 पहले सेट की जड़ है। सादृश्य से, आप पा सकते हैं कि पहली पंक्ति से संख्या 7 दूसरी पंक्ति से संख्या 0 से मेल खाती है । 7 नंबर दूसरे सेट के पेड़ की जड़ भी है।

इस प्रकार, हम निष्कर्ष निकालते हैं कि ऊपरी पंक्ति से संख्याएँ सेट की बेटी नोड्स हैं, और निचली पंक्ति से संबंधित संख्या उनके मूल नोड हैं। इस नियम से निर्देशित, आप उपरोक्त तालिका से दोनों पेड़ों को आसानी से बहाल कर सकते हैं।

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

आगे बढ़ने से पहले, एल्गोरिथ्म द्वारा उपयोग किए जाने वाले कुछ कार्यों के छद्म कोड पर विचार करें।

हम तालिका को PARENT के रूप में शामिल-खोज के लिए डेटा संरचना का प्रतिनिधित्व करते हैं । अगले फ़ंक्शन को खोज कहा जाता है और वर्तमान लेबल एक्स को मापदंडों के रूप में ले जाएगाऔर की एक सरणी PARENT । यह प्रक्रिया पेड़ की जड़ तक मूल बिंदुओं का पता लगाती है और पेड़ के मूल नोड के लेबल का पता लगाती है कि X किससे संबंधित है ।

 ̆   ̆  .
X —  
PARENT — , ̆    -

procedure find(X, PARENT);
{
j := X;
while PARENT[j] <> 0
    j := PARENT[j]; return(j);
}

विचार करें कि F # पर ऐसा फ़ंक्शन कैसे लागू किया जा सकता है

let rec find x =
    let index = Array.tryFindIndex ((=)x) parents.[0, *]
    match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x 

यहां हम खोज के एक पुनरावर्ती कार्य की घोषणा करते हैं , जो वर्तमान लेबल एक्स को लेता है । PARRENT सरणी यहां से पारित नहीं हुई है, क्योंकि हमारे पास पहले से ही वैश्विक नाम स्थान में है और फ़ंक्शन पहले से ही इसे देखता है और इसके साथ काम कर सकता है।

सबसे पहले, फ़ंक्शन शीर्ष रेखा पर लेबल के सूचकांक को खोजने की कोशिश करता है (क्योंकि आपको इसके मूल को खोजने की आवश्यकता है, जो नीचे की रेखा पर स्थित है।

let index = Array.tryFindIndex ((=)x) parents.[0, *]

यदि खोज सफल होती है, तो हम इसके अभिभावक से मिलते हैं और 0 से तुलना करते हैं । यदि माता-पिता 0 के बराबर नहीं है , तो इस नोड में भी माता-पिता होते हैं, और फ़ंक्शन पुनरावर्ती रूप से तब तक कॉल करता है जब तक कि पैरेंट 0 के बराबर न हो । इसका मतलब यह होगा कि हमें सेट का रूट नोड मिल गया है।

match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x 

अगले फ़ंक्शन को हमें यूनियन कहा जाता है । यह दो लेबल X और Y लेता है , साथ ही PARENT की एक सरणी भी । यह संरचना संशोधित करता है (यदि आवश्यक हो) एक लेबल X युक्त PAR फ्यूजन सब्मिट , जिसमें लेबल Y शामिल है । प्रक्रिया दोनों लेबल के रूट नोड्स के लिए खोज करती है और यदि वे मेल नहीं खाते हैं, तो एक लेबल के नोड को दूसरे लेबल के मूल नोड के रूप में नामित किया गया है। तो दो सेटों का एक संघ है।

   .
X — ,   .
Y — ,   .
PARENT — , ̆    -.

procedure union(X, Y, PARENT);
{
j := X;
k := Y;
while PARENT[j] <> 0
    j := PARENT[j];
while PARENT[k]] <> 0
    k := PARENT[k];

if j <> k then PARENT[k] := j;
} 

एफ # कार्यान्वयन इस तरह दिखता है

let union x y =
    let j = find x
    let k = find y
    if j <> k then parents.[1, k-1] <- j 

ध्यान दें कि हमारे द्वारा पहले से लागू किया गया खोज फ़ंक्शन यहां पहले से ही उपयोग किया गया है ।

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

let neighbors_labels x y =
    match (x, y) with
    | (0, 0) -> []
    | (0, _) -> [step1.[0, y-1]]
    | (_, 0) -> [step1.[x-1, 0]]
    | _ -> [step1.[x, y-1]; step1.[x-1, y]]
    |> List.filter ((<>)0) 

आगे देखते हुए, मैं तुरंत कहता हूं कि सरणी चरण 1 जो फ़ंक्शन का उपयोग करता है वह पहले से ही वैश्विक स्थान में मौजूद है और इसमें पहले पास पर एल्गोरिदम को संसाधित करने का परिणाम है। मैं अतिरिक्त फिल्टर पर विशेष ध्यान देना चाहता हूं।

|> List.filter ((<>)0)

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

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

चित्र 5: मूल द्विआधारी छवि
संसाधन से पहले, एक खाली सारिणी निर्मितचरण 1, जिसमें पहली पास का परिणाम सहेजा जाएगा। चित्र 6: प्राथमिक प्रसंस्करण परिणामों को संग्रहीत करने के लिए चरण 1 को रोकें $$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix}$$




$$\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$

प्राथमिक डेटा प्रोसेसिंग के पहले कुछ चरणों पर विचार करें (मूल द्विआधारी छवि की केवल पहली तीन पंक्तियाँ)।

इससे पहले कि हम एल्गोरिथ्म पर एक कदम-दर-चरण नज़र डालें, चलो छद्म-कोड को देखें जो ऑपरेशन के सामान्य सिद्धांत की व्याख्या करता है।

     .
B —   .
LB —   .

procedure classical_with_union-find(B, LB);
{
“  .” initialize();
“  1 ̆  L     .”
for L := 0 to MaxRow
{
“     L  ”
for P := 0 to MaxCol
    LB[L,P] := 0;
“  L.”
for P := 0 to MaxCol
    if B[L,P] == 1 then
    {
        A := prior_neighbors(L,P);
        if isempty(A)
        then {M := label; label := label + 1;};
        else M := min(labels(A));
        LB[L,P] := M;
        for X in labels(A) and X <> M
           union(M, X, PARENT);
    }
}
“  2 ,    1,     .”
for L := 0 to MaxRow
    for P := 0 to MaxCol
        if B[L, P] == 1
        then LB[L,P] := find(LB[L,P], PARENT);
};
      LB ( step1)     ( ).

चित्र 7: चरण 1. बिंदु (0,0), लेबल = 1
$$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
चित्र 8: चरण 2. बिंदु (1,0), लेबल = 1
$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
चित्रा 9: चरण 2. बिंदु (2.0), लेबल = 1
$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
चित्रा 10: चरण 4. बिंदु (3.0), लेबल = 2
$$\begin{matrix} 1 & 1 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
चित्र 11: अंतिम चरण, प्रथम उत्तीर्ण का अंतिम परिणाम
$$\begin{matrix} 1 & 1 & 0 & 2 & 2 & 2 & 0 & 3 \\ 1 & 1 & 0 & 2 & 0 & 2 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 7 & 7 & 3 \end{matrix}$$
कृपया ध्यान दें कि मूल छवि के प्रारंभिक प्रसंस्करण के परिणामस्वरूप, हमें दो सेट मिले

$$

$$(1,2) - (3,7)$$

दृष्टिगत रूप से, इसे अंक 1 और 2 (अंकों के निर्देशांक (1,3) और (2,3) ) और अंक 3 और 7 (अंकों के निर्देशांक (7,7) और (7,6) ) के संपर्क के रूप में देखा जा सकता है । खोज-संघ के लिए डेटा संरचना के दृष्टिकोण से, यह परिणाम प्राप्त होता है।

चित्र 12: खोज एकत्रीकरण के लिए कम्प्यूटेड डेटा संरचना
$$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 3 \end{matrix}$$
अंत में प्राप्त डेटा संरचना का उपयोग करके छवि को संसाधित करने के बाद, हमें निम्नलिखित परिणाम मिलते हैं।

चित्र 13: अंतिम परिणाम
$$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 3 & 3 & 3 \end{matrix}$$
अब सभी जुड़े घटकों में हमारे पास अद्वितीय लेबल हैं और प्रसंस्करण के लिए बाद के एल्गोरिदम में उपयोग किया जा सकता है।

एफ # कोड कार्यान्वयन निम्नानुसार है

let markingOfConnectedComponents matrix =

    // up to 10 markers
    let parents = Array2D.init 2 10 (fun x y -> if x = 0 then y+1 else 0)

    // create a zero initialized copy
    let step1 = (Matrix.cloneO matrix).values

    let rec find x =
        let index = Array.tryFindIndex ((=)x) parents.[0, *]
        match index with
        | Some(i) -> 
            match parents.[1, i] with
            | p when p <> 0 -> find p
            | _ -> x
        | None -> x

    let union x y =
        let j = find x
        let k = find y
        if j <> k then parents.[1, k-1] <- j

    // returns up and left neighbors of pixel
    let neighbors_labels x y =
        match (x, y) with
        | (0, 0) -> []
        | (0, _) -> [step1.[0, y-1]]
        | (_, 0) -> [step1.[x-1, 0]]
        | _ -> [step1.[x, y-1]; step1.[x-1, y]]
        |> List.filter ((<>)0)

    let mutable label = 0
    matrix.values
    |> Array2D.iteri (fun x y v ->
                        if v = 1 then
                            let n = neighbors_labels x y
                            let m = if n.IsEmpty then
                                        label <- label + 1
                                        label
                                    else
                                        n |> List.min
                            n |> List.iter (fun v -> if v <> m then union m v)
                            step1.[x, y] <- m)

    let step2 = matrix.values
                |> Array2D.mapi (fun x y v ->
                        if v = 1 then step1.[x, y] <- find step1.[x, y]
                        step1.[x, y])

    { values = step2 } 

कोड का एक लाइन-बाय-लाइन स्पष्टीकरण अब कोई मतलब नहीं है, जैसा कि सब कुछ ऊपर वर्णित किया गया था। यहां आप बस # कोड को छद्म कोड में मैप कर सकते हैं ताकि यह स्पष्ट हो सके कि यह कैसे काम करता है।

बेंचमार्किंग एल्गोरिदम

आइए दोनों एल्गोरिदम (पुनरावर्ती और पंक्ति-वार) के साथ डेटा प्रोसेसिंग गति की तुलना करें।

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()

printfn "origin =\n %A" A.values
printfn "markers =\n %A" R1.values
printfn "rec markers =\n %A" R2.values

printfn "elapsed lines = %O" t1.Elapsed
printfn "elapsed recurcive = %O" t2.Elapsed 

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]
markers =
 [[1; 1; 0; 1; 1; 1; 0; 3]
 [1; 1; 0; 1; 0; 1; 0; 3]
 [1; 1; 1; 1; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
elapsed lines = 00:00:00.0081837
elapsed recurcive = 00:00:00.0038338

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

let a = Array2D.create 100 100 1
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()
printfn "elapsed lines = %O" t1.Elapsed

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()
printfn "elapsed recurcive = %O" t2.Elapsed 

elapsed lines = 00:00:00.0131790
elapsed recurcive = 00:00:00.2632489

जैसा कि आप देख सकते हैं, पुनरावर्ती एल्गोरिदम पहले से ही रैखिक से 25 गुना धीमा है। आइए तस्वीर के आकार को 200x200 पिक्सेल तक बढ़ाएं।

elapsed lines = 00:00:00.0269896
elapsed recurcive = 00:00:06.1033132

अंतर पहले से ही कई सौ बार है। मैं ध्यान देता हूं कि पहले से ही 300x300 पिक्सल के आकार पर, पुनरावर्ती एल्गोरिदम एक स्टैक अतिप्रवाह और प्रोग्राम क्रैश का कारण बनता है।

सारांश

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

यहाँ चर्चा की गई स्रोत कोड को मैट्रिक्स मैट्रिक्स एल्गोरिथ्म जीथब पर भी देखा जा सकता है
।

मुझे उम्मीद है कि यह लेख विशेष रूप से एफ # और छवि प्रसंस्करण एल्गोरिदम में रुचि रखने वालों के लिए दिलचस्प था।