पाठ में चित्रों को पार्स करना: एक सरल एल्गोरिथ्म

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



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

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







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

मैंने यह सब पहले पर्ल में और फिर पीएचपी में लिखा, लेकिन यह किसी के लिए लिस्टिंग के साथ बोर करने के लायक नहीं है, है ना?

चरण 1. मैट्रिक्स के लिए छवि।
हम छवि को _xy , या [x] [y] रूप के दो-आयामी मैट्रिक्स में पार्स करते हैं, यदि आप इसे अधिक पसंद करते हैं।
हम मैट्रिक्स के प्रत्येक तत्व के लिए एक मूल्य प्रदान करते हैं - पिक्सेल का रंग।
हम विभिन्न रंगों के पिक्सेल की संख्या की गणना करते हैं, इस बारे में जानकारी एक नियमित सरणी में दर्ज की जाती है।

चरण 2. हम अतिरिक्त से छुटकारा पा लेते हैं।
एक छवि, भले ही GIF से ली गई हो, जिसमें 256 से अधिक रंग न हों, फिर भी जानकारी की मात्रा में कमी की आवश्यकता होती है। रंगों की संख्या कम करें: हम उन सभी मूल्यों को त्याग देते हैं जो हमारे सरणी में सबसे अधिक संदर्भ वाले रंग के कम से कम 50% से कम हैं। एक प्रतीत होता है मोनोक्रोम छवि से, आमतौर पर चार रंग रहते हैं। यह प्राथमिक रंगों की एक सूची है।

चरण 3. अगला सबसे मजेदार है: कुल पैनापन और ग्रेस्केल बनाएं। अपने हाथ देखो:

एक नया द्वि-आयामी मैट्रिक्स बनाएँ [x] [y]। हम इसमें परिणाम लिखेंगे।
चार आसन्न पिक्सेल लें - एक वर्ग।
यदि इन पिक्सेल का कम से कम एक रंग प्राथमिक रंगों की सूची में रहता है, तो हम नए मैट्रिक्स में b [0] [0] = X लिखते हैं। यदि कोई नहीं है, तो b [0] [0] = 0 लिखें।
निम्नलिखित 4 पिक्सेल लें। मैट्रिक्स के अंत तक दोहराएं, और बड़ी छवियों के मामले में, ऑपरेशन को दो बार भी चलाया जा सकता है। बस दूर नहीं किया जाता है - छवि जितनी अधिक जटिल होगी, आगे की तुलना करना उतना ही कठिन होगा।

परिणाम एक ऐसी सुंदरता है:


इसमें कुछ बचपन से है, जब स्कूल में उन्होंने ज़िप कोड लिखना सिखाया, है ना?

सबसे सरल बात बनी हुई है: कंप्यूटर को यह समझाने के लिए कि ग्राफिक छवि, जिसमें क्रॉस और शून्य शामिल हैं, अच्छी तरह से एक दशमलव अंक हो सकता है। ऐसा करने के लिए, प्रतीकों द्वारा मैट्रिक्स को टुकड़ों-submatrices में विभाजित करें, और मानक के साथ उनकी तुलना करें। दुर्भाग्य से, प्रत्येक कैप्चा के लिए मानक अलग है, और हर बार आपको इसे समायोजित करना होगा, भले ही थोड़ा सा।

बहुत ही अंत में, हम इसी तरह के तार की तुलना करने के लिए ओलिवियर एल्गोरिथ्म द्वारा सहेजे जाते हैं, जिसका उपयोग समाप्त PHP फ़ंक्शन int समान_टेक्स्ट (str, str) में किया जाता है । बेशक, लाइनों की लंबाई जितनी छोटी होती है, उतनी ही तेज़ी से उनकी जाँच की जाती है, इसलिए मैंने मानक की पहली पंक्ति के साथ "मान्यता प्राप्त" चरित्र में पहली पंक्ति की तुलना की, दूसरी के साथ दूसरी, और इसी तरह अंत तक।

1 टुकड़े की त्रुटि के साथ चालीस हजार फोन नंबरों को मान्यता दी गई थी। अब एल्गोरिथ्म को अधिक सार्वभौमिक बनाने के लिए - और हमारी जेब में एक मिलियन, है ना?