पिक्सल के साथ काम करने के उदाहरण का उपयोग करते हुए k- साधन (k- साधन) एल्गोरिथ्म का कार्यान्वयन

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

तो हमारी धारणाओं के संदर्भ में क्या है? मैं आपको एक उदाहरण देता हूं, मान लीजिए कि आपकी दादी की कुटिया के फूलों के साथ एक अच्छी तस्वीर है।



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

कई क्लस्टरिंग एल्गोरिदम हैं, लेकिन उनमें से सबसे सरल है k - माध्यम, जिस पर बाद में चर्चा की जाएगी। K- साधन एक सरल और कुशल एल्गोरिथ्म है जो एक सॉफ्टवेयर पद्धति का उपयोग करके लागू करना आसान है। डेटा जो हम क्लस्टर में वितरित करेंगे, वह पिक्सेल है। जैसा कि आप जानते हैं, एक रंगीन पिक्सेल में तीन घटक होते हैं - लाल, हरा और नीला। इन घटकों को थोपना और मौजूदा रंगों का एक पैलेट बनाता है।



कंप्यूटर की मेमोरी में, प्रत्येक रंग घटक को 0 से 255 तक की संख्या की विशेषता है। अर्थात, लाल, हरे और नीले रंग के विभिन्न मूल्यों के संयोजन से, हमें स्क्रीन पर एक रंग पैलेट मिलता है।

एक उदाहरण के रूप में पिक्सेल का उपयोग करना, हम अपने एल्गोरिथ्म को लागू करते हैं। K- साधन एक पुनरावृत्ति एल्गोरिथ्म है, अर्थात्, यह कुछ गणितीय परिवर्तनों की पुनरावृत्ति की एक निश्चित संख्या के बाद, सही परिणाम देगा।

एल्गोरिथ्म

1. आपको पहले से पता होना चाहिए कि डेटा को वितरित करने के लिए आपको कितने क्लस्टर की आवश्यकता है। यह इस पद्धति का एक महत्वपूर्ण नुकसान है, लेकिन एल्गोरिथ्म के बेहतर कार्यान्वयन द्वारा इस समस्या को हल किया जाता है, लेकिन इसे पूरी तरह से एक महत्वपूर्ण कहानी कहा जाता है।
2. हमें अपने समूहों के प्रारंभिक केंद्रों को चुनने की आवश्यकता है। कैसे? रैंडम पर हाँ। क्यों? ताकि आप प्रत्येक पिक्सेल को क्लस्टर के केंद्र में स्नैप कर सकें। केंद्र राजा की तरह होता है, जिसके चारों ओर उसके विषय इकट्ठे होते हैं - पिक्सल। यह केंद्र से पिक्सेल के लिए "दूरी" है जो निर्धारित करता है कि प्रत्येक पिक्सेल किसका पालन करेगा।
3. हम प्रत्येक पिक्सेल से प्रत्येक केंद्र से दूरी की गणना करते हैं। इस दूरी को अंतरिक्ष में बिंदुओं के बीच यूक्लिडियन दूरी के रूप में माना जाता है, और हमारे मामले में, तीन रंग घटकों के बीच की दूरी के रूप में:

   $$$$ प्रदर्शन $ $ \ sqrt {(R_ {2} -R_ {1}) ^ 2 + (G_ {2} -G_ {1}) ^ 2 + (B_ {2} -B_ {1}) ^ 2} । $ $ प्रदर्शन $ $

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

कार्यान्वयन

मैं इस प्रोजेक्ट को C ++ में लागू करूंगा। पहली फ़ाइल "k_means.h" है, इसमें मैंने मुख्य डेटा प्रकार, स्थिरांक, और काम करने के लिए मुख्य वर्ग - "K_means" को परिभाषित किया है।
प्रत्येक पिक्सेल को चिह्नित करने के लिए, एक संरचना बनाएं जिसमें तीन पिक्सेल घटक होते हैं, जिसके लिए मैंने अधिक सटीक गणना के लिए डबल प्रकार चुना, और कार्यक्रम के लिए कुछ स्थिरांक भी निर्धारित किए हैं:

const int KK = 10; //  const int max_iterations = 100; //   typedef struct { double r; double g; double b; } rgb; 

K_means वर्ग ही:

 class K_means { private: std::vector<rgb> pixcel; int q_klaster; int k_pixcel; std::vector<rgb> centr; void identify_centers(); inline double compute(rgb k1, rgb k2) { return sqrt(pow((k1.r - k2.r),2) + pow((k1.g - k2.g), 2) + pow((k1.b - k2.b), 2)); } inline double compute_s(double a, double b) { return (a + b) / 2; }; public: K_means() : q_klaster(0), k_pixcel(0) {}; K_means(int n, rgb *mas, int n_klaster); K_means(int n_klaster, std::istream & os); void clustering(std::ostream & os); void print()const; ~K_means(); friend std::ostream & operator<<(std::ostream & os, const K_means & k); }; 

कक्षा के घटकों पर चलते हैं:

वेक्टरपिक्ससेल - पिक्सल के लिए एक वेक्टर;
q_klaster - समूहों की संख्या;
k_pixcel - पिक्सेल की संख्या;
वेक्टरेंट - क्लस्टरिंग केंद्रों के लिए एक वेक्टर, इसमें तत्वों की संख्या q_klaster द्वारा निर्धारित की जाती है;
Ident_centers () - इनपुट पिक्सल के बीच प्रारंभिक केंद्रों को बेतरतीब ढंग से चुनने के लिए एक विधि;
गणना () और कंप्यूट_ () क्रमशः पिक्सेल और पुनर्गणना केंद्रों के बीच की दूरी की गणना करने के लिए अंतर्निहित तरीके हैं;
तीन कंस्ट्रक्टर: पहला डिफ़ॉल्ट रूप से है, दूसरा एक सरणी से पिक्सेल को इनिशियलाइज़ करने के लिए है, तीसरा एक टेक्स्ट फ़ाइल से पिक्सल को इनिशियलाइज़ करने के लिए है (मेरे कार्यान्वयन में, फ़ाइल गलती से पहली बार डेटा से भर जाती है, और फिर प्रोग्राम को काम करने के लिए इस फ़ाइल से पिक्सेल पढ़े जाते हैं, सीधे वेक्टर में क्यों नहीं - बस मेरे मामले में);
क्लस्टरिंग (std :: ostream & os) - क्लस्टरिंग विधि;
परिणामों को प्रकाशित करने के लिए आउटपुट स्टेटमेंट की विधि और अधिभार।

विधि कार्यान्वयन:

 void K_means::identify_centers() { srand((unsigned)time(NULL)); rgb temp; rgb *mas = new rgb[q_klaster]; for (int i = 0; i < q_klaster; i++) { temp = pixcel[0 + rand() % k_pixcel]; for (int j = i; j < q_klaster; j++) { if (temp.r != mas[j].r && temp.g != mas[j].g && temp.b != mas[j].b) { mas[j] = temp; } else { i--; break; } } } for (int i = 0; i < q_klaster; i++) { centr.push_back(mas[i]); } delete []mas; } 

यह प्रारंभिक क्लस्टरिंग केंद्रों का चयन करने और उन्हें केंद्र वेक्टर में जोड़ने के लिए एक विधि है। इन मामलों में केंद्रों को दोहराने और उन्हें बदलने के लिए एक जांच की जाती है।

 K_means::K_means(int n, rgb * mas, int n_klaster) { for (int i = 0; i < n; i++) { pixcel.push_back(*(mas + i)); } q_klaster = n_klaster; k_pixcel = n; identify_centers(); } 

एक सरणी से पिक्सेल को इनिशियलाइज़ करने के लिए एक कंस्ट्रक्टर कार्यान्वयन।

 K_means::K_means(int n_klaster, std::istream & os) : q_klaster(n_klaster) { rgb temp; while (os >> temp.r && os >> temp.g && os >> temp.b) { pixcel.push_back(temp); } k_pixcel = pixcel.size(); identify_centers(); } 

हम इस निर्माता के लिए एक इनपुट ऑब्जेक्ट पास करते हैं जो फ़ाइल और कंसोल दोनों से डेटा दर्ज करने में सक्षम हो।

 void K_means::clustering(std::ostream & os) { os << "\n\n :" << std::endl; /*             :        ,    -  ,    ,   ,        .*/ std::vector<int> check_1(k_pixcel, -1); std::vector<int> check_2(k_pixcel, -2); int iter = 0; /* .*/ while(true) { os << "\n\n----------------  №" << iter << " ----------------\n\n"; { for (int j = 0; j < k_pixcel; j++) { double *mas = new double[q_klaster]; /*  :          .      ,   .*/ for (int i = 0; i < q_klaster; i++) { *(mas + i) = compute(pixcel[j], centr[i]); os << "   " << j << "   #" << i << ": " << *(mas + i) << std::endl; } /*     m_k      .*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) { if (min_dist > *(mas + i)) { min_dist = *(mas + i); m_k = i; } } os << "    #" << m_k << std::endl; os << "  #" << m_k << ": "; centr[m_k].r = compute_s(pixcel[j].r, centr[m_k].r); centr[m_k].g = compute_s(pixcel[j].g, centr[m_k].g); centr[m_k].b = compute_s(pixcel[j].b, centr[m_k].b); os << centr[m_k].r << " " << centr[m_k].g << " " << centr[m_k].b << std::endl; delete[] mas; } /*   .*/ int *mass = new int[k_pixcel]; os << "\n  : "<< std::endl; for (int k = 0; k < k_pixcel; k++) { double *mas = new double[q_klaster]; /*    .*/ for (int i = 0; i < q_klaster; i++) { *(mas + i) = compute(pixcel[k], centr[i]); os << "   №" << k << "   #" << i << ": " << *(mas + i) << std::endl; } /*  .*/ double min_dist = *mas; int m_k = 0; for (int i = 0; i < q_klaster; i++) { if (min_dist > *(mas + i)) { min_dist = *(mas + i); m_k = i; } } mass[k] = m_k; os << " №" << k << "     #" << m_k << std::endl; } /*            .*/ os << "\n    : \n"; for (int i = 0; i < k_pixcel; i++) { os << mass[i] << " "; check_1[i] = *(mass + i); } os << std::endl << std::endl; os << " : " << std::endl; int itr = KK + 1; for (int i = 0; i < q_klaster; i++) { os << " #" << i << std::endl; for (int j = 0; j < k_pixcel; j++) { if (mass[j] == i) { os << pixcel[j].r << " " << pixcel[j].g << " " << pixcel[j].b << std::endl; mass[j] = ++itr; } } } delete[] mass; /*    .*/ os << " : \n" ; for (int i = 0; i < q_klaster; i++) { os << centr[i].r << " " << centr[i].g << " " << centr[i].b << " - #" << i << std::endl; } } /*         –  .*/ iter++; if (check_1 == check_2 || iter >= max_iterations) { break; } check_2 = check_1; } os << "\n\n ." << std::endl; } 

क्लस्टरिंग की मुख्य विधि।

 std::ostream & operator<<(std::ostream & os, const K_means & k) { os << " : " << std::endl; for (int i = 0; i < k.k_pixcel; i++) { os << k.pixcel[i].r << " " << k.pixcel[i].g << " " << k.pixcel[i].b << " - №" << i << std::endl; } os << std::endl << "   : " << std::endl; for (int i = 0; i < k.q_klaster; i++) { os << k.centr[i].r << " " << k.centr[i].g << " " << k.centr[i].b << " - #" << i << std::endl; } os << "\n : " << k.q_klaster << std::endl; os << " : " << k.k_pixcel << std::endl; return os; } 

प्रारंभिक डेटा का आउटपुट।

आउटपुट उदाहरण

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

अधिक दिलचस्प यादृच्छिक रूप से उत्पन्न पिक्सेल के मामले हैं। 50 बिंदुओं को उत्पन्न करने के लिए जिन्हें 10 समूहों में विभाजित करने की आवश्यकता होती है, मुझे 5 पुनरावृत्तियों मिले। 50 बिंदुओं को उत्पन्न करने के लिए जिन्हें 3 समूहों में विभाजित करने की आवश्यकता है, मुझे सभी 100 अधिकतम अनुमत पुनरावृत्तियां मिलीं। आप देख सकते हैं कि अधिक क्लस्टर्स, प्रोग्राम के लिए सबसे समान पिक्सों को ढूंढना और उन्हें छोटे समूहों में संयोजित करना आसान है, और इसके विपरीत - यदि कुछ क्लस्टर्स हैं और कई बिंदु हैं, तो एल्गोरिथ्म अक्सर केवल तभी समाप्त होता है जब अधिकतम संख्या में पुनरावृत्तियों को पार कर जाता है, क्योंकि कुछ पिक्सेल लगातार कूदते हैं। एक क्लस्टर से दूसरे क्लस्टर में। हालाँकि, थोक अभी भी उनके समूहों में पूरी तरह से निर्धारित हैं।

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



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

मान लीजिए कि हमारे पास ऐसी फोटो है। हम एक द्वीप को एक क्लस्टर के रूप में परिभाषित कर सकते हैं, लेकिन वृद्धि के साथ हम देखते हैं कि इसमें हरे रंग के विभिन्न रंग शामिल हैं।



और यह क्लस्टर 8 है, लेकिन एक छोटे संस्करण में, परिणाम समान है:



कार्यक्रम का पूरा संस्करण मेरे गिटहब पर देखा जा सकता है ।