प्रस्तावना

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

कार्यक्रम को निम्न-स्तरीय भाषा C ++ का उपयोग करके लिखा गया है, क्योंकि मैं वास्तव में यह समझना चाहता था कि यह सब अंदर से कैसे काम करता है। अगर आप भी कंप्यूटर विजन की पढ़ाई शुरू करना चाहते हैं, तो इसके लिए OpenCV लाइब्रेरी उपयोगी है। CodeProject पर, आप इस पर कई पाठ पा सकते हैं। वेबकैम से छवि वादिम गोर्बात्तेंको के स्रोत कोड (AviCap CodeProject) का उपयोग करके प्राप्त की जाती है।

नीचे दी गई छवि बताती है कि कार्यक्रम कैसे काम करता है।



नीचे दिए गए समय अंतराल में मेरे 2.8 गीगाहर्ट्ज पीसी पर 640x480 वेबकेम रिज़ॉल्यूशन के साथ मिलीसेकंड में देरी होती है। हम एक दिलचस्प परिणाम देख रहे हैं। उदाहरण के लिए, सबसे धीमा कदम कैमरा से एक फ्रेम प्राप्त करना है। यह 100 एमएस लेता है, और इसका मतलब है कि आपको प्रति सेकंड केवल 10 फ्रेम प्राप्त होंगे। यह पर्याप्त नहीं है। वेबकैम आमतौर पर धीमा होता है। आप संकल्प बदलकर उनकी गति बढ़ा सकते हैं। इसे कम करके, आप शूटिंग को गति देते हैं, लेकिन गुणवत्ता का त्याग करते हैं, और यह विश्लेषण के लिए पूरी तरह से अनुपयुक्त हो सकता है। एक और आश्चर्य की बात है कि छवि को बाइनरी (केवल सफेद या काले) में परिवर्तित करने में भी लंबा समय लगता है, जितना कि 12 एमएस। दूसरी तरफ, मुझे उम्मीद थी कि ओसीआर सुधार और सुडोकु के समाधान में बहुत समय लगेगा, और जब यह कदम 8 एमएस में एक साथ किया जाता है, तो सुखद आश्चर्य हुआ। नीचे मैं प्रत्येक चरण के बारे में विस्तार से बताऊंगा और दिखाऊंगा कि क्या सुधार किया जा सकता है।

मोनोक्रोम में रूपांतरण कैसे काम करता है

थ्रेसहोल्ड चयन

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

छवि बदलने के लिए सबसे आसान तरीका एक सामान्य सीमा है। मान लीजिए कि आपके पास RGB रंग (200, 200, 200) वाला पिक्सेल है। चूंकि घटकों की तीव्रता 0 से 255 तक भिन्न होती है, पिक्सेल बहुत उज्ज्वल है। दहलीज को आधी तीव्रता के रूप में चुनना: 256/2 = 128, हमें लगता है कि हमारे पिक्सेल को सफेद होना चाहिए। लेकिन आम सीमा का उपयोग शायद ही कभी वास्तविक अनुप्रयोगों में किया जाता है, क्योंकि यह बहुत कम उपयोग होता है। स्थानीय सीमा एल्गोरिथ्म बहुत अधिक उपयोगी है।



छवि को मोनोक्रोम में सही रूप से परिवर्तित करने के लिए, हम अनुकूली दहलीज चयन का उपयोग करेंगे। यह 128 की निश्चित सीमा मूल्य का उपयोग नहीं करता है। इसके बजाय, यह प्रत्येक पिक्सेल के लिए अलग-अलग सीमा पर विचार करता है। यह 11 पिक्सल के साथ एक वर्ग लेता है और हमारे पिक्सेल में एक केंद्र के साथ और सभी बिंदुओं की तीव्रता को सारांशित करता है। तीव्रता का औसत मूल्य किसी दिए गए पिक्सेल के लिए सीमा होगा। वर्तमान पिक्सेल के लिए तीव्रता का सूत्र: दहलीज = योग / 121, जहाँ 121 = 11x11। यदि हमारे पिक्सेल की तीव्रता थ्रेशोल्ड मान से ऊपर है, तो इसे सफेद में बदल दिया जाता है, यदि नहीं, तो काले रंग में। नीचे दी गई छवि में, पिक्सेल जिसके लिए सीमा निर्धारित की गई है, लाल रंग में चिह्नित है। और ये गणना प्रत्येक पिक्सेल के लिए की जाती है। इसलिए, यह कदम इतना धीमा है, क्योंकि एल्गोरिथ्म को छवि पिक्सेल की चौड़ाई * ऊंचाई * 121 रीडिंग की आवश्यकता है।

पूर्ण रूप

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



निम्न छवि दिखाती है कि पूर्णांक छवि कैसे उपयोगी हो सकती है। लक्ष्य ग्रे आयत में पिक्सेल की राशि की गणना करना है।
सूत्र: सम = डीसी-बी + ए। हमारे मामले में: 110-44-40 + 16 = 42 (मैन्युअल गणना करने का प्रयास करें)।
ग्रे आयत से सभी पिक्सेल पढ़ने के बजाय (जो उदाहरण में बहुत बड़ा हो सकता है), हमें केवल एक मेमोरी रीडिंग की आवश्यकता है। यह एल्गोरिथम का एक महत्वपूर्ण अनुकूलन है। लेकिन इसके साथ भी, एक छवि को मोनोक्रोम में परिवर्तित करना बहुत मुश्किल है।

रोटेशन के कोण का निर्धारण कैसे करें

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

यह कैसे काम करता है? आपको स्कूल का फॉर्मूला याद रखना चाहिए y = (x * cos (थीटा) + rho) / sin (थीटा)।


जहां थीटा लाइन का कोण है, और आरएचओ लाइन से निर्देशांक के केंद्र (0, 0) की दूरी है।
यह महत्वपूर्ण है कि लाइन को केवल दो चर में वर्णित किया जा सकता है: झुकाव का कोण और निर्देशांक के केंद्र की दूरी।

एल्गोरिथ्म एक मोनोक्रोम छवि में सभी पिक्सल से गुजरता है, सफेद पिक्सल को छोड़ देता है। जब वह ब्लैक पिक्सेल से टकराता है, तो वह इस पिक्सेल से 1 डिग्री की वृद्धि में गुजरने वाली सभी प्रकार की लाइनों को "आकर्षित" करने की कोशिश कर रहा है। इसका मतलब है कि प्रत्येक पिक्सेल में 180 काल्पनिक रेखाएँ होती हैं। 360 क्यों नहीं? हां, क्योंकि कोण 180-360 कोणों की प्रतियां 0-180 डिग्री के साथ हैं।

काल्पनिक लाइनों के इस सेट को ड्राइव कहा जाता है, थीटा और आरएचओ आयामों के साथ एक दो-आयामी सरणी, जो ऊपर सूत्र में थे। प्रत्येक काल्पनिक रेखा को ड्राइव में एक मान द्वारा दर्शाया जाता है। वैसे, विधि को रूपांतरण कहा जाता है क्योंकि यह लाइनों को (x, y) से सरणी (थीटा, थओ) में परिवर्तित करता है। प्रत्येक काल्पनिक रेखा ड्राइव में मूल्य जोड़ती है, इस संभावना को बढ़ाती है कि काल्पनिक रेखा वास्तविक से मेल खाती है। यह वोट की तरह है। इन पंक्तियों में सबसे अधिक "वोट" हैं।

सभी पिक्सेल और उनकी 180 काल्पनिक रेखाओं "वोट" के बाद, हमें ड्राइव में अधिकतम मान ज्ञात करना होगा। (वैसे, इसे एक ड्राइव कहा जाता है क्योंकि यह वोट जमा करता है) वोट का विजेता सबसे अधिक अभिव्यंजक रेखा है। इसके पैरामीटर थीटा और आरएचओ का उपयोग इसे तैयार करने के लिए ऊपर दिए गए सूत्र के साथ किया जा सकता है।

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



इस छवि को देखते हुए, आप समझ सकते हैं कि लाइन डिटेक्शन कैसे काम करता है। Hough ट्रांसफॉर्म एल्गोरिथ्म सफेद पिक्सेल को छोड़ देता है। प्रत्येक काले पिक्सेल पर, वह चार काल्पनिक हरी रेखाएँ खींचता है (वास्तव में वहाँ 180 हैं, लेकिन सादगी के लिए हम चार लेंगे) वर्तमान पिक्सेल से गुजरते हुए। लाइनों A, B, C और D के लिए पहला पिक्सेल वोट, E, B, G, H के लिए दूसरा पिक्सेल वोट। I, B, K, L के लिए तीसरा। सभी तीन पिक्सेल ने रेखा B के लिए मतदान किया, और शेष लाइनों ने कुल मिलाकर प्राप्त किया। एक आवाज। इस प्रकार रेखा बी ने वोट जीता।

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



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

यदि आपको एक सर्कल खोजने की आवश्यकता है, तो आपको तीन आयामों के साथ ड्राइव की आवश्यकता है: x, y और r। जहां x और y हमारे सर्कल के केंद्र के निर्देशांक हैं, और आर त्रिज्या है।
मूल छवि के क्षेत्र और संभावित कोणों को सीमित करके Hough रूपांतरण को अनुकूलित किया जा सकता है। हमें सभी लाइनों का विश्लेषण करने की आवश्यकता नहीं है, केवल वे जो केंद्र के करीब हैं। हमारे मामले में, यह उनसे है कि हम निर्माण कर सकते हैं।

ग्रिड को कैसे परिभाषित करें

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



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



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

TODO : यह कदम अधिक शोर प्रतिरोधी हो सकता है। अगले संस्करण में, मैंने ग्रिड के कोणों को निर्धारित करने के लिए Haar जैसे एल्गोरिदम के साथ वर्तमान विधि को संयोजित करने की योजना बनाई है। मुझे उम्मीद है कि इससे गुणवत्ता बढ़ेगी। समस्या यह हो सकती है कि Haar जैसी पद्धति ठोस क्षेत्रों के साथ अच्छी तरह से काम करती है, न कि लाइनों के साथ। लाइनें एक छोटे से क्षेत्र पर कब्जा कर लेती हैं, इसलिए एक प्रकाश और एक अंधेरे आयत के बीच का अंतर इतना महान नहीं है।
यह दिलचस्प है कि 10x10 ग्रिड का पता लगाने की कोशिश करने पर क्या होगा ...

OCR कैसे काम करता है?

यह निर्धारित करने के बाद कि नंबर कहां होना चाहिए, हमें उन्हें पहचानने की आवश्यकता है। यह अपेक्षाकृत आसान है। वर्णमाला में केवल 1 से 9 तक संख्याएँ होती हैं।

सिद्धांत

प्रत्येक मान्यता एल्गोरिथ्म में तीन चरण होते हैं:

• आवश्यक विशेषताओं का निर्धारण
• ट्रेनिंग
• वर्गीकरण (रनटाइम में मान्यता)

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

क्षेत्र

हमारे आवेदन में, ज़ोन के घनत्व की विधि का उपयोग किया गया था। अगला चरण (यह अग्रिम में किया जाना चाहिए) 1 से 9 तक के नंबरों पर एप्लिकेशन को प्रशिक्षित करना है। आप इन छवियों को ./res निर्देशिका में पा सकते हैं। वे 5x5 आकार के लिए कम हो जाते हैं, सामान्यीकृत होते हैं और एक स्थिर सरणी में संग्रहीत होते हैं OCRDigit :: m_zon [10] [5] [5], जो कुछ इस तरह दिखता है:

5x5 आकार में कमी को ज़ोनिंग या ज़ोनिंग कहा जाता है। उपरोक्त सरणी को फ़ंक्शन घनत्व कहा जाता है।
सामान्यीकरण का अर्थ है कि घनत्व 0 से 1024 तक भिन्न होता है। ज़ोन को सामान्य किए बिना, आप सही तरीके से तुलना नहीं कर सकते।
कार्यक्रम निष्पादन के दौरान क्या होता है: जब कोई अंक मूल छवि से प्राप्त होता है, तो यह 5x5 के आकार तक कम हो जाता है। उसके बाद, इसके प्रत्येक पिक्सेल की तुलना प्रशिक्षित एरे से नौ अंकों के प्रत्येक पिक्सेल से की जाती है। लक्ष्य एक अंतर के साथ एक आंकड़ा खोजने के लिए है।

यह विधि छवि के आकार के लिए अपरिवर्तनीय है, क्योंकि किसी भी स्थिति में हम 5x5 क्षेत्रों का उपयोग करते हैं। वह मोड़ों के प्रति संवेदनशील है, लेकिन हम पहले भी इस बात का ध्यान रख चुके हैं। समस्या यह है कि यह स्थिति और पूर्वाग्रह के प्रति संवेदनशील है, और नकारात्मक (काले रंग पर सफेद) और संख्याओं के साथ काम नहीं करता है।

चौड़ाई / ऊंचाई अनुपात

नंबर एक विशेष मामला है। चूंकि यह 4 और 7 के समान है, इसलिए ऊपर दी गई निर्धारण विधि अविश्वसनीय हो सकती है। एक विशिष्ट इकाई पैरामीटर: हमारे मामले में, इसकी चौड़ाई इसकी ऊंचाई से 40% कम है। समान अनुपात के साथ ऐसा कोई अन्य आंकड़ा नहीं है। हमारे पास पहले से ही 25 जोन (संकेत) हैं, इसलिए यह 26 वां संकेत है।

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



आप कुछ और सुधार जोड़ सकते हैं। पेशेवर OCR इंजन कई विशेषताओं का उपयोग करते हैं। उनमें से कुछ बहुत ही विदेशी हैं।

OCR परिणाम समायोजित करें

ओसीआर पूरा होने के बाद, परिणाम सुडोकू नियमों के अनुसार समायोजित किए जाते हैं। एक पंक्ति, स्तंभ और 3x3 ब्लॉक में समान अंक नहीं हो सकते। यदि नियम का उल्लंघन किया जाता है, तो परिणामों के लिए समायोजन शुरू करना आवश्यक है। हम उस गलत अंक को प्रतिस्थापित करेंगे जो कि शेष लोगों से संभव है। उदाहरण के लिए, ऊपर की छवि 12 में, परिणाम 5 है क्योंकि diff = 5210, जो सबसे छोटा अंतर मान है। अगला संभावित परिणाम 6 है, क्योंकि इस मामले में अंतर = 5508 है। इस प्रकार, हम 5 को 6. के साथ बदल देंगे। यह तय करने के लिए कि दोनों में से कौन सा अंक गलत है, हम उनके अंतर के मूल्यों की तुलना उनके नमूनों से करेंगे, और कम मूल्य वाले को सही माना जाएगा। आप फ़ंक्शन के स्रोत कोड को खोज सकते हैं SudSolver :: Fixit ();

सुडोकू समाधान फ़ंक्शन कैसे काम करता है?

सुडोकू को हल करने के कई तरीके हैं। हम तीन सरल तरीकों का उपयोग करते हैं जो एक साथ काम करते हैं और एक दूसरे के पूरक हैं: खुली संख्या, छिपी संख्या, और ओवरकिल।

क्रूर बल

यह प्रोग्रामर द्वारा सबसे व्यापक रूप से उपयोग की जाने वाली विधि है जो कठिनाई स्तर की परवाह किए बिना सटीक रूप से एक समाधान देती है। लेकिन खोज बहुत लंबी हो सकती है, यह पुनरावृत्ति की गहराई पर निर्भर करता है। आपको कभी पता नहीं चलेगा कि आपको कितने पुनरावृत्तियों की आवश्यकता है। खोज के दौरान, 1 से 9 तक के संभावित मूल्यों को बदले में सेल में डाल दिया जाता है, और सेट संख्या के साथ सुडोकू का समाधान जारी रहता है। यदि हम एक ठहराव पर हैं (हमें एक पंक्ति / स्तंभ / ब्लॉक में समान संख्याएं मिलती हैं, तो हम संख्या को अगले में बदल देते हैं)। वास्तव में, एक से अधिक समाधान हो सकते हैं, लेकिन यह कम से कम एक मिलने पर ठंडा होगा। (अनुवादक के पास खोज में समाधान था और यह आश्चर्यजनक रूप से तेजी से काम किया)।

सबसे पहले, उम्मीदवारों की एक तालिका तैयार करना आवश्यक है - प्रत्येक खाली सेल के लिए संभावित मान। नीचे दी गई छवि बताती है कि वास्तव में उम्मीदवार क्या हैं। उन्हें नीला रंग दिया गया है। सुडोकू के नियमों के अनुसार, पहली कोशिका में केवल संख्या 1, 4, 8 हो सकती है। तीन नहीं हो सकते, क्योंकि यह पहले से ही दो कोशिकाएं कम है।



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



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

नंबर खोलें

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

छिपे हुए नंबर

पहले की तरह, नीचे दी गई छवि इस पद्धति की व्याख्या करती है। संख्या 7. देखो यदि आप सुडोकू हल कर रहे हैं, तो आप सबसे अधिक संभावना यह कहेंगे कि सात को संकेतित सेल में होना चाहिए।



भले ही इस सेल में चार उम्मीदवार हों: 4, 7, 8, 9 (चित्र 15 देखें), चाल यह है कि हम 3x3 ब्लॉक में, पंक्ति में और कॉलम में उम्मीदवारों से अद्वितीय संख्या की तलाश कर रहे हैं। विधि संपूर्ण पहेली को हल करने में सक्षम हो सकती है, लेकिन यह विधि 2 के साथ बेहतर काम करती है। जब एकल उम्मीदवार खुले अंक पद्धति में समाप्त होते हैं, तो छिपी हुई अंक पद्धति दृश्य में प्रवेश करती है।

सभी तरीकों को एक साथ मिलाकर

इसके लिए, प्रसंस्करण गति और समाधान महत्वपूर्ण हैं। गणना बहुत तेज नहीं है। इस प्रकार, हम तीनों विधियों के संयोजन का उपयोग करेंगे। तरीके 2 और 3 बहुत तेज हैं, लेकिन केवल तेज पहेली को हल कर सकते हैं। चूंकि हम एप्लिकेशन को हमारे लिए पहेली को हल करने के लिए कहते हैं, इसका मतलब है कि यह वास्तव में जटिल है। नीचे काम का एल्गोरिदम है। तेजी से तरीके 2 और 3 बाईं ओर स्थित हैं। और केवल अगर वे पहेली को हल करने में विफल होते हैं, तो नियंत्रण इस खोज एल्गोरिथ्म के लिए काम को कम करते हुए, खोज विधि के साथ दाईं ओर से गुजरता है।



केवल अगर तरीके 2 और 3 पहेली को हल नहीं कर सकते हैं, तो क्या प्रोग्राम मूल्यों को मोड़ना शुरू कर देता है। और फिर भी, जानवर बल एल्गोरिथ्म 600,000 पुनरावृत्तियों तक सीमित है। तीन प्रयास भी हैं, जिसके बाद यह कार्यक्रम समाप्त हो जाता है। प्रत्येक प्रयास के बीच, पुनरावर्ती अनुक्रम को इस उम्मीद के साथ यादृच्छिक रूप से पुनर्व्यवस्थित किया जाता है कि नया अनुक्रम पहेली को तेज़ी से हल करने में मदद करेगा। यदि हम सुडोकू को हल नहीं कर सकते हैं, तो शायद हम कैमरे के अगले फ्रेम में भाग्यशाली होंगे। प्रस्तुत फ्लोचार्ट का वर्णन फ़ंक्शन में किया गया है SudSolver :: SolveMe ()।

बफरिंग सॉल्यूशंस

जब एक समाधान मिल जाता है, तो हम इसे SudResultVoter प्रकार की एक सरणी में संग्रहीत करते हैं। बफरिंग आवश्यक है क्योंकि ओसीआर परिणाम की शुद्धता की 100% गारंटी नहीं देता है, और समय-समय पर हमें अलग-अलग समाधान मिलते हैं। अस्थिर समाधान से बचने के लिए, हम हमेशा सबसे मजबूत (पिछले 12 समाधानों की सटीकता के लिए) दिखाएंगे। समय-समय पर, सरणी को शून्य पर रीसेट किया जाता है, पुराने फैसलों को भुलाकर नए लोगों को मौका दिया जाता है।

वीडियो

कार्यसूची:

भविष्य के लिए कुछ विचार:

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

डाउनलोड डेमो - 170 KB
डाउनलोड स्रोत - 307 KB

GitHub पर स्रोत कोड का एक दर्पण भी है: github.com/NeonMercury/Realtime-Webcam-Sudoku-Solver