छवि वर्गीकरण

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

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

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

मुख्य विचार

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

पीढ़ी

जनरेटर को न केवल चित्र बनाना चाहिए, बल्कि उनके साथ हस्तक्षेप करने में भी सक्षम होना चाहिए। उत्पन्न करते समय, हमें एक निश्चित आकार (उदाहरण के लिए, 15 पिक्सेल) से कम और मोटे कोण (150 डिग्री से अधिक) के साथ पक्षों को आकृतियों को छोड़ना चाहिए - यहां तक ​​कि किसी व्यक्ति के लिए उन्हें वर्गीकृत करना मुश्किल है।
स्क्रिप्ट को विक्टर एवरस्टैटोव द्वारा सावधानीपूर्वक प्रदान किया गया था।
bitbucket.org/rampeer/image-classifier/src/HEAD/picture_generator.py

फिल्टर

सहकर्मियों के साथ चर्चा के दौरान, हमने फ़िल्टर के लिए अच्छे विचार पाए। हम हस्तक्षेप के लिए विपरीत रंग के पिक्सेल से घिरे काले पिक्सेल लेते हैं (यह विचार मंझला फिल्टर का आधार बनता है), और वांछित पथ के लिए हम काले पिक्सेल का एक बड़ा संचय लेते हैं, अर्थात, हम एक bicomponent फ़िल्टर का उपयोग करते हैं।

माध्यियन फ़िल्टर : प्रत्येक ब्लैक पिक्सेल के लिए हम त्रिज्या R के पड़ोस में "ब्लैक" पड़ोसियों की संख्या निर्धारित करते हैं। यदि यह संख्या एक निश्चित टी से कम है, तो हम इस पिक्सेल को त्याग देते हैं, अर्थात इसे सफेद रंग में पेंट करते हैं। "मूल" माध्यिका फ़िल्टर में, हम पिक्सेल को त्याग देते हैं यदि उसके पास आधे से कम काले पड़ोसी हैं, और हमने अपनी सीमा टी निर्धारित की है, इसलिए, वास्तव में, यह एक मात्रात्मक फ़िल्टर है।



मैंने माध्य फ़िल्टर को ईमानदारी से और "हेड-ऑन" लिखा है, इसलिए यह O(WHR2) लिए काम करता है, जहां डब्ल्यू और एच चित्र आकार हैं। शिक्षक ने कहा कि आप फूरियर रूपांतरण का उपयोग करके एल्गोरिथ्म को गति दे सकते हैं। वास्तव में, मंझला फ़िल्टर को कनवल्शन के माध्यम से व्यक्त किया जा सकता है, और तेजी से फूरियर ट्रांसफॉर्म का उपयोग करके कन्वेंशन की गणना जल्दी से की जा सकती है।
यह पता चला है कि आप पड़ोसियों की संख्या के साथ एक मैट्रिक्स की गणना कर सकते हैं
result = FFT-1 (FFT(data) FFT(window))
यह एल्गोरिथ्म O(WHlog(W+H)) लिए काम करता है, O(WHlog(W+H)) , एक भोली कार्यान्वयन की तुलना में बहुत तेज़ है, और यह खिड़की के आकार पर निर्भर नहीं करता है। सजा चक्र के कारण, सीमाओं पर एक विरूपण साक्ष्य उत्पन्न होता है: जब बाईं ओर के पिक्सल को संसाधित करते हैं, तो सबसे दाहिने पिक्सेल को पड़ोसी माना जाएगा। छवि के किनारों के साथ शुद्ध पिक्सेल का एक फ्रेम जोड़कर इसे ठीक किया जा सकता है, या आप इसे छोड़ सकते हैं जैसा मैंने किया था - वैसे भी यह प्रभाव प्रदर्शन को प्रभावित नहीं करता है।
bitbucket.org/rampeer/image-classifier/src/HEAD/filter_median.py
हालांकि, मुझे इस फिल्टर के साथ एक खराब संपत्ति मिली: यह त्रिकोण के तेज कोनों से गोल है। इस वजह से, आपको खिड़की आर की त्रिज्या को छोटा नहीं लेना होगा और केवल कुछ (एन) बार फिल्टर के साथ छवि के माध्यम से जाना होगा। हालाँकि पहले ऐसा लगता था कि आप एक माध्यिका फ़िल्टर लागू कर सकते हैं जब तक कि यह कुछ पिक्सेल निकालता है।

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


<Filter_bicomp.py>
पिछले एक के विपरीत, यह फ़िल्टर छवि को खराब नहीं करता है। यह केवल तभी नुकसान पहुंचा सकता है जब आंकड़ा टी की तुलना में हस्तक्षेप की चौड़ाई की रेखा को पार कर जाता है, जो कि संभावना नहीं है।
माध्यिका फ़िल्टर में, मुझे एक और संपत्ति मिली, इस बार सकारात्मक। वह हस्तक्षेप से भरे स्थान को "द्वीपों" में विभाजित करता है। तो, फिर एक bicomponent फ़िल्टर लागू करना, हम चिपके हुए शोर के साथ एक समोच्च प्राप्त करते हैं। एक bicomponent फिल्टर के साथ प्रसंस्करण के बाद, शेष धक्कों को हटाने के लिए फिर से माध्यिका से गुजरने के लायक है। फिर आपको शेष बिंदुओं के चारों ओर एक उत्तल समोच्च बनाने की आवश्यकता है, इसे भरें और नई छवि के लिए पहले से ही मैट्रिक्स की गणना करें।
bitbucket.org/rampeer/image-classifier/src/HEAD/process.py
फिल्टर का काम:

स्रोत छवि	मेडियन फिल्टर	मेडियन, बायोमेकनोपेंट	मेडियन, बायोमकॉपेंट, माध्य भर

फ़िल्टर मापदंडों को नमूने में छवियों के आकार और उनके शोर के आधार पर चुना जाता है। ऊपर दिखाए गए मुश्किल चतुर्भुज के लिए:

  median.filter(img, 2, 6, 1) bicomp.filter(img, 2) median.filter(img, 2, 5, 2) 

हमारे नमूने में, चित्र कम शोर वाले होंगे और सेटिंग्स अधिक बख्शने वाली होंगी।

मैट्रिक्स

सहकर्मियों के साथ एक ही चर्चा के दौरान, हम कई अलग-अलग दिलचस्प मैट्रिक्स के साथ आए।

गिनती के कोण । यह पहली चीज है जो कार्य को पढ़ने के बाद दिमाग में आती है। लेकिन हस्तक्षेप के कारण, 0 डिग्री के करीब अतिरिक्त कोण दिखाई दे सकते हैं। मैंने इससे निपटने के लिए असफल कोशिश की, "एक साथ gluing" लगभग कोलिनियर वैक्टर और थ्रेसहोल्ड सेट करना। इस तरह के तरीकों को कॉन्फ़िगर करना मुश्किल है, और वे अभी भी एक गलत परिणाम दे सकते हैं, क्योंकि फ़िल्टर किए जाने पर यह आंकड़ा चिकना हो जाता है। कोणों के साइन के वर्गों को योग करना बेहतर है, और यदि कोण एक निश्चित सीमा टी से अधिक है, तो वर्ग को एकता तक गोल करें। यह काफी अच्छा परिणाम देता है: तेज कोण काउंटर में एक जोड़ते हैं, और 0 के करीब कोण लगभग कुछ भी नहीं जोड़ते हैं। वैसे, यह मुझे मजाकिया लग रहा था कि इस मामले में एक त्रिकोण के कोणों की संख्या 2.5 से 4 तक भिन्न हो सकती है।

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_edges.py

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

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_mirror.py

परिधि के वर्ग के क्षेत्रफल का अनुपात । परिधि को चुकाना होगा ताकि मीट्रिक में एक आयाम न हो और छवि के आकार पर निर्भर न हो। परिधि और क्षेत्र को उत्तल समोच्च से लिया जाएगा। सर्कल में आंकड़ों के बीच सबसे बड़ा मीट्रिक मूल्य है: s/p^2 =(πr^2)/(4π^2 r^2 )=1/4π । एक समभुज त्रिभुज के लिए (इसमें त्रिभुजों में सबसे बड़ा अनुपात है): s/p^2 =(4√3 a^2)/(3*9a^2 )=(4√3)/27 । वर्ग के लिए: s/p^2 =(a^2)/(16*a^2 )=1/16 ।

bitbucket.org/rampeer/image-classifier/src/HEAD/feature_perimeter.py

विवरण आयत पर मेट्रिक्स । पिछले मेट्रिक्स ने चार और त्रिकोण को बहुत अच्छी तरह से अलग नहीं किया, और मैंने एक नई मीट्रिक के साथ आने का फैसला किया। आकृति के चारों ओर एक बाउंडिंग बॉक्स बनाएं। आयत के प्रत्येक पक्ष के लिए, हम आकृति के साथ पहला ("न्यूनतम") और अंतिम ("अधिकतम") चौराहा पाते हैं। हमें एक "अष्टकोना" मिलता है जिसके लिए हम विभिन्न मैट्रिक्स की गणना कर सकते हैं।

उदाहरण के लिए, एक विवरण वर्ग के क्षेत्रफल के क्षेत्रफल का अनुपात (सॉबर)।
bitbucket.org/rampeer/image-classifier/src/HEAD/feature_sbound.py
इसके अलावा, इस अष्टकोण (s2) के क्षेत्र के आंकड़े के क्षेत्र का अनुपात एक आशाजनक मीट्रिक लगता है:
bitbucket.org/rampeer/image-classifier/src/HEAD/feature_sbound2.py

डेटा संग्रह

अर्जित ज्ञान को लागू करते हुए, मैंने चित्र बनाए और आंकड़े एकत्र किए। इस छवि सेट में, मैंने ऐसे आकार जोड़े हैं जो मैट्रिक्स के लिए संभावित "बुरे मामलों" का प्रतिनिधित्व करते हैं:

• समबाहु त्रिभुज
• अक्षों के समानांतर दो भुजाओं वाला समकोण त्रिभुज
• कुल्हाड़ियों के समानांतर पक्षों वाला एक वर्ग।

मैंने पेड़ बनाते समय इन मामलों को बहुत अधिक वजन दिया। तथ्य यह है कि ऐसी तस्वीरों की यादृच्छिक पीढ़ी की संभावना छोटी है, और ये मामले कुछ मैट्रिक्स के लिए सीमा हैं। इसलिए, सही वर्गीकरण के लिए, उन्हें एक बड़े वजन के साथ नमूना में जोड़ा जाना चाहिए।
मैंने छवि को फ़िल्टर करने और मैट्रिक्स को एक अलग फ़ाइल में इकट्ठा करने के लिए प्रक्रिया रखी, यह विश्लेषण के लिए आवश्यक होगा। वैसे, निर्णय वृक्ष में हमारे मैट्रिक्स को "इनपुट पैरामीटर" या "सुविधाएँ" (सुविधा) कहा जाता है।
bitbucket.org/rampeer/image-classifier/src/HEAD/process.py
bitbucket.org/rampeer/image-classifier/src/HEAD/stats.py
फिर मैंने यह सुनिश्चित करने की साजिश रची कि मेट्रिक्स आंकड़े को अच्छी तरह से अलग करते हैं। इसके लिए, "ऐन्टेना वाले बक्से" जैसा एक शेड्यूल उपयुक्त है:

"एंटीना" प्रतिच्छेद, जिसका अर्थ है कि विश्लेषण में गलतियां संभव हैं। जैसा कि ऊपर लिखा गया था, सटीकता के लिए हमें कई मीट्रिक चाहिए, और एक नहीं। फिर मैंने यह सुनिश्चित करने की कोशिश की कि मेट्रिक्स के "खराब मामले" प्रतिच्छेद नहीं करते हैं। ऐसा करने के लिए, मैंने एक मीट्रिक की दूसरे पर निर्भरता का निर्माण किया। अगर यह पता चलता है कि वे एक-दूसरे पर एक-दूसरे पर निर्भर हैं, तो उनके "बुरे मामले" भी मेल खाएंगे।

* जैसा कि हम ग्राफ से देख सकते हैं, "बादलों" के अंक दृढ़ता से प्रतिच्छेद करते हैं। नतीजतन, वर्गीकरण में एक बड़ी गलती संभव है। इसके अलावा, मैट्रिक्स एक दूसरे पर एक दूसरे पर निर्भर नहीं हैं।

के विश्लेषण

एकत्रित आंकड़ों के आधार पर, आप एक निर्णय ट्री बना सकते हैं:
bitbucket.org/rampeer/image-classifier/src/HEAD/analyze.py
मैंने पेड़ की कल्पना करने की कोशिश की। यह इस तरह की एक योजना है:

यह इस प्रकार है कि कुछ मैट्रिक्स अप्रयुक्त रह गए हैं। शुरुआत से ही, हम यह अनुमान नहीं लगा सकते थे कि कौन से मैट्रिक्स दूसरों की तुलना में "बेहतर" होंगे।
भविष्यवाणी की सटीकता लगभग 91 प्रतिशत है, जो वर्गों के विरूपण और नमूने में हस्तक्षेप को देखते हुए बुरा नहीं है:



आइए छवियों को स्वयं खींचने का प्रयास करें और उनका विश्लेषण करें:

वृत्त

आयत

त्रिभुज

चलो वोल्टेज बढ़ाने की कोशिश करते हैं।
हम आंकड़ों को विकृत करेंगे जब तक कि वे गलत तरीके से निर्धारित नहीं हो जाते।

आयत

आयत

त्रिभुज

आयत

वह सब है।
अंतिम छवि में, त्रिकोण के कोण बहुत गोल हैं, किनारों को सही ढंग से काम नहीं कर सकता है, और परिधि बहुत अधिक त्रुटि देता है। त्रिकोण असफल रूप से घुमाया जाता है: जब बाउंडिंग आयत का निर्माण होता है, तो केवल दो कोने इसे स्पर्श करेंगे, और sbound और sbound2 कुछ भी उचित उत्पादन नहीं करेंगे। केवल एक दर्पण ही सही परिणाम दे सकता है, लेकिन यह पेड़ में शामिल नहीं है। और यदि 5 मीट्रिक में से केवल एक त्रिभुज की ओर इंगित करता है, तो इस निष्कर्ष को गलत माना जा सकता है।

निष्कर्ष

मशीन सीखने के तरीकों ने हमें एक ऐसी प्रणाली बनाने की अनुमति दी जो कार्य के साथ अच्छी तरह से मेल खाती है - यह छवि में आंकड़ों को अच्छी तरह से पहचानती है।
आर में चार्ट बनाए गए:
bitbucket.org/rampeer/image-classifier/src/HEAD/charts.R