हाथ से लिखे रूपों में नियमित रूप से ठेला मुद्दों

हाय, हैब्र)

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

पहले आपको यह निर्धारित करने की आवश्यकता है कि हम पहले से ज्ञात प्रपत्र के अनुसार निर्मित हस्तलिखित भरने के साथ दस्तावेजों के बारे में बात कर रहे हैं।


सेल ग्रिड

एकल कोशिकाएं

सीरीफ स्ट्रिंग
चित्रा 1. परिचित gratings के प्रकार

क)

ख)
चित्रा 2. सेरिफ़ (ए) की उपस्थिति में और नियमित हस्तक्षेप (बी) को हटाने के बाद भरे हुए क्षेत्र का एक उदाहरण

ऐसे मामलों में, दस्तावेज़ में डेटा प्रविष्टि फ़ील्ड का स्थान अग्रिम में जाना जाता है और इसमें वर्णित है
दस्तावेज़ का मॉडल, जिसमें स्थिर तत्वों (रेखाओं, रेखाओं, फ़ील्ड हेडिंग), तत्वों की संरचना, उनकी सापेक्ष स्थिति, आकार और अन्य विशेषताओं का विवरण शामिल है। हस्तलिखित भरने वाले दस्तावेजों के रिक्त रूपों के लिए, इनपुट फ़ील्ड एक विशेष प्रकार के ग्रिड के रूप में जारी किए जाते हैं, जिसमें प्रत्येक अक्षर (परिचित) के लिए एक अलग सेल आवंटित किया जाता है।
परिचित ग्रिड विभिन्न प्रकारों में आते हैं। व्यवहार में, तीन मुख्य प्रकार के लट्टे सबसे अधिक बार उपयोग किए जाते हैं: कोशिकाओं, व्यक्तिगत कोशिकाओं की एक ग्रिड के रूप में और सेरिफ़ (चित्रा 1) के साथ एक पंक्ति के रूप में। उन सभी में एक विशेषता आयताकार संरचना होती है (वे क्षैतिज और ऊर्ध्वाधर लाइनों से मिलकर होती हैं)।
चित्रा 2a एक पूर्ण हाथ से मुद्रित क्षेत्र का एक उदाहरण दिखाता है जैसे एक जाली के साथ "सेरिफ़ के साथ पंक्ति"। मान्यता प्रणाली के दृष्टिकोण से, परिचित झंझरी अनिवार्य रूप से एक संरचित शोर है जो पाठ डेटा पर आरोपित है, जिससे बड़ी संख्या में मान्यता त्रुटियां उत्पन्न होती हैं। विशेष रूप से, असंबंधित नमक / काली मिर्च के शोर के विपरीत, सुपरिम्पोज़ किए गए झंझरी टोपोलॉजिकल चरित्र मान्यता विधियों को पूरी तरह से अनुपयुक्त बनाते हैं। इस प्रकार, इन "कृत्रिम" हस्तक्षेप को हटाने का प्रयास मान्यता की गुणवत्ता में उल्लेखनीय वृद्धि कर सकता है।
समर्थन तत्वों के सटीक स्थान को जानने से आप उन्हें पाठ को विकृत किए बिना लगभग दबा सकते हैं। इस तथ्य के बावजूद कि सैद्धांतिक रूप से यह जानकारी ज्ञात है (दस्तावेज़ मॉडल में एम्बेडेड), व्यवहार में यह अक्सर अपूर्ण या गलत है। प्रपत्रों के मुद्रण, भरने और बाद के डिजिटलीकरण की प्रक्रिया में, विभिन्न प्रकार के विकृति (शिफ्ट, झुकाव, प्रिंटर और / या स्कैनर में दलाली से जुड़े मामूली खिंचाव) और शोर संकेतों (स्पॉटिंग, फोल्डिंग पेपर से छाया, और अन्य) को पेश किया जाता है। इसलिए, ग्रिड के संदर्भ विवरण अक्सर उनके कार्यान्वयन के अनुरूप नहीं होते हैं: आयताकार आकार की संपत्ति खो जाती है, सेरिफ़ और इतने पर आवृत्ति का उल्लंघन किया जाता है (चित्रा 3)।


आवधिकता का उल्लंघन


सीधे विकृति
चित्रा 3. परिचितता के अक्षांशों के विरूपण के उदाहरण

ऊपर से, निम्नलिखित समस्याएं समर्थन तत्वों के सटीक स्थानीयकरण से संबंधित हैं:

• • लाइनों की सीधेपन की विकृति।
• • अक्षांशों में आवधिकता का उल्लंघन परिचित है।
• • इनपुट फ़ील्ड (छवि 4) के करीब निकटस्थ स्थिर तत्वों की उपस्थिति।
• • तत्वों को लाइन सेगमेंट के समान रूप से भरने की उपस्थिति।

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

एक ज्ञात संयुक्त पैटर्न के साथ क्षैतिज रेखाएं खोजें

तो, बाहरी विपरीत लाइनों की पृष्ठभूमि के खिलाफ झंझरों के संदर्भ क्षैतिज रेखाओं को उजागर करने के लिए, झंझरी के ऊर्ध्वाधर तत्वों के साथ संदर्भ रेखा के संयुग्मन के बारे में जानकारी पर भरोसा करना प्रस्तावित है। हम सबसे सरल नियमित अभिव्यक्ति के साथ वांछित वस्तु का वर्णन करेंगे - एक स्ट्रिंग जिसमें सिमेंटिक प्रतीक और एक संभावित दोहराव प्रतीक ('*') होगा। इस विवरण को एक लाइन पैटर्न कहें।
सिमेंटिक पात्रों के रूप में, हम एक जंक्शन (उदाहरण के लिए, '' ',', ',' well ') जैसे वर्णों का उपयोग करेंगे, साथ ही जोड़ों के बिना एक रेखा की उपस्थिति (' a ') और एक रेखा (' ○ ') की अनुपस्थिति के प्रतीक भी होंगे। उदाहरण के लिए, अंजीर में दिखाए गए सभी क्षेत्रों की निचली संदर्भ लाइनें। 4, पैटर्न "└ are * ┘ ┘ *,", और "एकल कोशिकाओं" प्रकार के ग्रिड के साथ फ़ील्ड द्वारा वर्णित हैं, "the ┘ * ┘ └ * the * * the * └ * ┘ ..." हैं।
आइए अब हम एक छवि पिक्सेल को लाइन जंक्शन के केंद्रीय पिक्सेल के रूप में आंकने के लिए एक विधि पर विचार करते हैं। वास्तव में, हमें यह मूल्यांकन करने की आवश्यकता है कि केंद्रीय पिक्सेल कितना गहरा है, साथ ही उन दिशाओं में स्थित पिक्सेल भी हैं जिनमें हम लाइनों की उपस्थिति की अपेक्षा करते हैं। इसके अलावा, हमें यह जांचना होगा कि शेष दिशाओं में पिक्सेल पर्याप्त रूप से उज्ज्वल हैं (अन्यथा सभी डिटेक्टर क्रॉस-आकार के संयुक्त का जवाब देंगे), और, इसके अलावा, विकर्ण उज्ज्वल होना चाहिए (अन्यथा डिटेक्टर काली आयतों के कोनों का जवाब देगा)। हम नियमित लाइन के नोड्स में 9 पिक्सल के पैटर्न पर विचार करेंगे, जिसमें अपेक्षित लाइन मोटाई के साथ एक चरण L कमैंसुरेट होगा। अंजीर में। 5 जंक्शन "the" के लिए अपेक्षित कॉन्फ़िगरेशन दिखाता है। जिस पिक्सेल के लिए गणना की जाती है, वह दी गई योजना के केंद्र से मेल खाती है।



अब हम विचाराधीन विन्यास के अनुरूप रूपात्मक फिल्टर का निर्माण करते हैं। आरेख पर सफेद में चिह्नित पिक्सेल के लिए, हम एक न्यूनतम के लिए देखेंगे, और अश्वेतों के लिए - एक अधिकतम। तब हम प्राप्त मूल्यों का अंतर पाते हैं, और शून्य, यदि यह 0. से कम है, तो डब्ल्यू के परिणामस्वरूप मूल्य को इस पिक्सेल में वांछित संयुक्त की गुणवत्ता का अनुमान माना जाएगा:



अन्य सभी प्रकार के जोड़ों के डिटेक्टर उसी तरह से बनाए जाते हैं, साथ ही जोड़ों के बिना एक सीधी रेखा डिटेक्टर। लाइन डिटेक्टर की कमी के लिए, निर्माण विधि थोड़ा अलग है:


जहां Wbg का अर्थ पैटर्न के किसी भी पिक्सेल में संभावित दूषित पदार्थों की उपस्थिति में पृष्ठभूमि की चमक का आकलन करना है।

इसलिए, क्षेत्र की छवि के लिए उचित रूपात्मक फिल्टर लागू करते हुए, हम प्रत्येक पिक्सेल को रेटिंग के एक सेट में यह कहते हुए प्राप्त करते हैं कि यह पिक्सेल एक जंक्शन, लाइन या स्थान के केंद्रीय पिक्सेल की तरह दिखता है (छवि 5)।

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


तालिका 1. गतिशील प्रोग्रामिंग का उपयोग करके टेम्पलेट के अनुरूपता के मूल्यांकन के लिए खोज का एक उदाहरण।

ऊर्ध्वाधर लाइनों के लिए खोजें

क्षैतिज प्रक्षेपण की आवृत्ति विश्लेषण का उपयोग करके जाली की ऊर्ध्वाधर लाइनें मांगी जा सकती हैं। लेकिन झंझरी में प्रिंटर और ब्रोकिंग स्कैनर के अपूर्ण पेपर फीड सिस्टम के कारण, सेरिफ़ के बीच की आवृत्ति का अक्सर उल्लंघन होता है (चित्र 6)।

क) ख)

ग) छ)

चित्रा 6. क्षेत्र (ए) की छवि में जोड़ों के └ The, '' 'और' ('(बी, सी, डी) का पता लगाने का परिणाम।

इसके अलावा, जब फॉर्म डेवलपमेंट स्टेज (जब आपको "Gediminayte-Berzhanskayt-Klausutayt" नाम से अचानक पता चल जाता है) में फ़ील्ड सेल्स की संख्या में आपातकालीन वृद्धि होती है, तो ऐसा होता है कि जोड़े गए सेल में एक गैर-मानक आकार होता है। समस्या को इस तथ्य से जटिल किया जाता है कि यहां तक ​​कि सही जाली ज्यामिति के मामले में, प्रतीकों के कारण ऊर्ध्वाधर स्ट्रोक होते हैं, कई झूठी चोटियों को प्रक्षेपण पर प्रदर्शित किया जाता है।
हालांकि, पिछली समस्या को आंशिक रूप से कम किया जा सकता है: चूंकि झंझरी का पता लगाने के इस स्तर पर चूंकि हम पहले से ही क्षैतिज रेखाओं का स्थान जानते हैं, इसलिए हम क्षैतिज अक्ष पर पूरी छवि के प्रक्षेपण पर विचार नहीं कर सकते हैं, लेकिन केवल उस भाग का प्रक्षेपण जो झंझरी की निचली रेखा से ऊपर है, लेकिन शीर्ष रेखा के नीचे या ऊपर है। इसी प्रकार के झंझरी के मामले में सेरिफ़ हाइट्स। यह सुनिश्चित करता है कि बड़े अक्षरों द्वारा बनाई गई चोटियां जाली के तत्वों द्वारा बनाई गई चोटियों से अधिक नहीं होंगी। इसके अलावा, सही चोटियों को मजबूत करने के लिए हिस्टोग्राम के लिए "and" और "joints" जोड़ों का वजन जोड़ना उचित है।
ऊर्ध्वाधर सहायक तत्वों के बीच की दूरी में अनुमानित अवधि और संभावित त्रुटि को जानते हुए, आप किसी दिए गए साइट पर ऐसे तत्वों के स्थान के लिए सभी प्रकार के विकल्पों की जल्दी से गणना कर सकते हैं और सबसे अच्छा विकल्प चुन सकते हैं। इस समस्या को अच्छी तरह से गतिशील प्रोग्रामिंग की विधि द्वारा हल किया जाता है, और इस मामले में, तालिका को हल करने की आवश्यकता नहीं है।
हम बाएं से दाएं हिस्टोग्राम के साथ आगे बढ़ेंगे। प्रत्येक चरण पर, हम हिस्टोग्राम के एक खंड पर विचार करते हैं, जहां x हमारी वर्तमान स्थिति है, पी अपेक्षित अवधि है, और consider अधिकतम विचलन है। निर्दिष्ट सेगमेंट के लिए हिस्टोग्राम मूल्यों के बीच अधिकतम खोजें और वर्तमान सेल में जोड़ें, और एक समानांतर सरणी में अधिकतम इंडेक्स को स्टोर करें। तब प्राप्त हिस्टोग्राम का वैश्विक अधिकतम अंतिम ऊर्ध्वाधर रेखा की स्थिति के अनुरूप होगा, और संबंधित सूचकांक पाया लाइनों की सूची के पिछले तत्व को इंगित करेगा। सूची से गुजरने के बाद, हम सभी ऊर्ध्वाधर सहायक तत्वों की स्थिति को बहाल करेंगे।

क्षैतिज रेखाओं के स्थान को ठीक करना

ऊर्ध्वाधर और क्षैतिज रेखाओं को खोजने के बाद, परिचित जाली का गठन माना जाता है। हालांकि, ग्रिड हटाने के एल्गोरिथ्म को पिक्सेल सटीकता की आवश्यकता होती है, और जब मुद्रण और स्कैनिंग चरणों में कागज खींचते हैं, तो छवि को प्रशंसक विरूपण से गुजरना पड़ सकता है (यदि शीट घूमती है तो यह मार्ग के साथ गुजरती है)। इसके अलावा, फ़ील्ड छवि के कोण का निर्धारण करने के लिए एल्गोरिथ्म भी छोटी त्रुटियों का परिचय दे सकता है। हम समस्या को इस प्रकार से बताते हैं: हमें सेल से सेल (छवि 3) में क्षैतिज रेखा तत्वों के ऊर्ध्वाधर ऑफसेट का एक क्रम खोजने की आवश्यकता है, बशर्ते कि प्रत्येक व्यक्ति ऑफसेट k पिक्सल (आमतौर पर k = 1) से अधिक नहीं हो सकता है।
इस समस्या को डायनेमिक प्रोग्रामिंग की विधि द्वारा भी हल किया जाता है।
आइए हम जाली के प्रत्येक सेल के लिए क्षेत्र की ऊंचाई (जो जाली के आकार से अधिक है) के बराबर आकार का एक ऊर्ध्वाधर हिस्टोग्राम इकट्ठा करते हैं और इन हिस्टोग्राम को एक तालिका के साथ भरते हैं जिसमें कोशिकाओं की संख्या के बराबर चौड़ाई होती है। हम तालिका के बाईं ओर से दाईं ओर की सीमा तक, अधिकतम अनुमति देंगे, जब k के तत्वों से अधिक नहीं होने पर ऊपर या नीचे जाने के लिए, दाईं ओर स्थानांतरित हो। पाया अधिकतम पथ क्षैतिज संदर्भ रेखा के तत्वों के पदों का पालन करेगा।
इन दो उपकरणों की मदद से, परिचित अक्षांशों के सटीक स्थानीयकरण की समस्या हल हो गई थी। तुलनात्मक समस्या को हल करने के लिए विकसित दृष्टिकोण प्रोग्रामेटिक रूप से लागू किया गया था और वर्तमान में CTP बीमा प्रोफाइल, ऋण अनुप्रयोगों, साथ ही साथ नेटवर्क मार्केटिंग प्रोफाइल के स्ट्रीमिंग इनपुट के लिए औद्योगिक रूप से उपयोग किया जाता है।
एल्गोरिथ्म की गुणवत्ता का मूल्यांकन 12,245 फ़ील्ड (तालिका 2) वाले 395 CTP नीतियों के एक सेट पर किया गया था। इस सेट के लिए, सभी क्षेत्रों के सही मानों को मैन्युअल रूप से दर्ज किया गया था, फिर मान्यता प्रणाली को तीन मोडों में लॉन्च किया गया था: जाली हटाने वाला सबसिस्टम बंद हो गया, भोली एल्गोरिथ्म चालू (केवल हिस्टोग्राम के विश्लेषण पर आधारित) और प्रस्तावित एल्गोरिथ्म के साथ। मान्यता की गुणवत्ता को सही तरीके से (एक त्रुटि के बिना) मान्यता प्राप्त क्षेत्रों के प्रतिशत के रूप में मापा गया था। सिस्टम की दो गुना मंदी की कीमत पर, मान्यता की गुणवत्ता को 30% से 80% तक बढ़ाना संभव था। यह ध्यान दिया जाना चाहिए कि 70% से कम मान्यता गुणवत्ता वाले दस्तावेज़ मान्यता प्रणाली आमतौर पर लाभहीन हैं - ऑपरेटर द्वारा सभी क्षेत्रों को भरना त्रुटियों को ठीक करने की तुलना में तेज़ है।

जैसा कि संसाधित छवियों के एक विस्तृत दृश्य द्वारा दिखाया गया है, प्रस्तावित एल्गोरिथ्म प्रदान करता है:

• लेआउट के बाहरी विपरीत लाइनों पर कब्जा करने वाले क्षेत्रों के साथ सही काम।
• चर सेल चौड़ाई के साथ खेतों का सही प्रसंस्करण।
• झंझरी का सही प्रसंस्करण टूटी हुई ज्यामिति (प्रशंसक विरूपण सहित) से परिचित है।

तालिका 2

इस विषय पर अधिक जानकारी लेख में ए.वी. कुरोत्तेव, डी.पी. निकोलेव, वी.वी. Postnikov। "गतिशील प्रोग्रामिंग और रूपात्मक फ़िल्टरिंग विधियों द्वारा प्रश्नावली में फ़ील्ड भरने के समर्थन अक्षांशों का सटीक स्थानीयकरण", रूसी विज्ञान अकादमी (आईएसए आरएएस), 2013, वी। 63, नंबर 3, पी के इंस्टीट्यूट ऑफ सिस्टम एनालिसिस के प्रोसीडिंग्स में प्रकाशित किया गया है।