हस्तलिखित गणित अभिव्यक्ति मान्यता

हेलो, हेब्र!

इस लेख में मैं हस्तलिखित गणितीय अभिव्यक्तियों को पहचानने का अनुभव साझा करना चाहता हूं। हालांकि विंडोज 7 में "मैथ इनपुट पैनल" mip.exe जैसे हैंड राइटिंग रिकग्निशन टूल्स पहले से मौजूद हैं, लेकिन इस समस्या को हल करने के लिए कई तरह के दृष्टिकोण प्रभावित नहीं कर सकते। मैं इनमें से एक दृष्टिकोण के बारे में बात करने जा रहा हूँ।

छोटा सा परिचय

गणितीय अभिव्यक्ति की मान्यता प्रतीकों की मान्यता की तुलना में अधिक जटिल प्रकार की मान्यता है, क्योंकि गणितीय प्रतीक को सीधे पहचानने के अलावा, गणितीय अभिव्यक्ति की संरचना को पहचानना भी आवश्यक है।

हस्तलिखित गणितीय अभिव्यक्तियों की ऑनलाइन मान्यता में, निम्नलिखित चरण आमतौर पर प्रतिष्ठित होते हैं:

1. डेटा संग्रह और पूर्व प्रसंस्करण:
   
2. एक अभिव्यक्ति को वर्णों में अलग करना (एक अभिव्यक्ति का विभाजन):
   
3. व्यक्तिगत पात्रों की मान्यता:
   
4. गणितीय अभिव्यक्ति की संरचना की मान्यता:
   

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

डेटा संग्रह और पूर्व-प्रसंस्करण

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

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

स्केलिंग, स्थानांतरण और नियंत्रण बिंदुओं की संख्या को बदलना
प्रत्येक स्ट्रोक के प्रत्येक बिंदु को स्थानांतरित किया जाता है ताकि शुरुआती बिंदु प्रतीक के बाउंडिंग बॉक्स के ऊपरी बाएं कोने हो। उसके बाद, चौड़ाई के अनुपात को बनाए रखते हुए सभी बिंदुओं को बढ़ाया जाता है ताकि प्रतीक को वर्ग के अंदर रखा जाए। इसके अलावा, प्रत्येक स्ट्रोक के बिंदुओं के सेट को बदल दिया जाता है ताकि अंक समतुल्य हों (रेखीय प्रक्षेप द्वारा चाप की लंबाई के साथ ओवरसम्पलिंग)। अंकों की संख्या निर्धारित है और 36 / एन के बराबर है, जहां एन प्रतीक में स्ट्रोक की संख्या है (36 को 1, 2, 3 और 4 से विभाजित किया गया है, जहां 4 एक प्रतीक में अधिकतम स्ट्रोक है)।
अंत में, बिंदुओं के निर्देशांक 72 तत्वों के एकल वेक्टर में एकत्र किए जाते हैं, जहां पहले 36 तत्व x में निर्देशांक का प्रतिनिधित्व करते हैं, और अंतिम - y में निर्देशांक।



हमें क्या मिला?
और हमें एक ही आयाम के वैक्टर का एक सेट मिला, जहां प्रत्येक वर्ग के वर्ण एक निश्चित संख्या में वैक्टर से मेल खाते हैं। इस जानकारी का उपयोग किया जा सकता है, उदाहरण के लिए, एक तंत्रिका नेटवर्क के प्रशिक्षण के लिए, या के-निकटतम पड़ोसी एल्गोरिथ्म का उपयोग करके चरित्र की पहचान के लिए।

वास्तव में, किसी भी जानकारी को खोए बिना, एक वेक्टर के आयाम को कई बार कम किया जा सकता है। इस एल्गोरिथ्म को "प्रधान घटक विधि" कहा जाता है।

परिणामस्वरूप, क्लासिफायर के प्रशिक्षण के लिए निम्नलिखित कुछ बनाया गया था:

अलग-अलग वर्णों का विभाजन और मान्यता

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

मान लीजिए कि दर्ज किए गए स्ट्रोक को समय के अनुसार आदेश दिया जाता है, अर्थात, जब आप तीन स्ट्रोक से मिलकर एक चरित्र दर्ज करते हैं, तो इस प्रतीक के स्ट्रोक क्रमिक रूप से दर्ज किए जाते हैं। उदाहरण के लिए, यह चरित्र पर एक डॉट लगाने की अनुमति नहीं है, जो कि मेरे बाद आने वाले पात्रों को लिखने के बाद। इस धारणा को देखते हुए, कई स्ट्रोक वाले पात्रों को निर्धारित करने के लिए, क्रमिक रूप से स्ट्रोक के समूहों पर विचार करना आवश्यक है, आकार में 1 से लेकर एन तक (एन हमारे मामले में 4 है)। यदि कई स्ट्रोक से एक प्रतीक को क्लासिफायर द्वारा एक निश्चित सीमा से कम त्रुटि के साथ पहचाना जाता है, तो यह प्रतीक पसंद किया जाता है। इस स्थिति में, माना गया संयोजनों की संख्या F (N) = O (kN) है । यदि कोई भी वर्गीकरण परिणाम थ्रेशोल्ड मान से अधिक नहीं है, तो थ्रेशोल्ड मान बढ़ता है और चरण दोहराया जाता है, या एक मान्यता त्रुटि होती है।

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

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



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

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

अब, अंत में, चलो एक अभिव्यक्ति की संरचना को पहचानने के लिए आगे बढ़ते हैं :-)

अभिव्यक्ति संरचना की मान्यता

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



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

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



प्रत्येक वर्ण वर्ग में अलग-अलग परिभाषित विशेषताएँ होती हैं। संरचनात्मक विश्लेषण में अस्पष्टताओं से बचने के लिए यह आवश्यक है:



अभिव्यक्ति बेसलाइन
एक आधार रेखा एक सूची है जो एक अभिव्यक्ति में वर्णों की क्षैतिज व्यवस्था का प्रतिनिधित्व करती है। प्रत्येक प्रतीक में अन्य आधार रेखाओं के लिंक होते हैं जो विभिन्न स्थानिक संबंधों को संतुष्ट करते हैं।



चरित्र प्रभुत्व और प्रमुख आधारभूत
वर्चस्व को इस प्रकार परिभाषित किया गया है: यदि क्षेत्र में झूठ है और क्षेत्र में झूठ नहीं है, तो प्रतीक एस प्रतीक पर हावी है। हालाँकि, दोनों पात्र एक दूसरे के क्षेत्रों में झूठ बोल सकते हैं। परिणामस्वरूप, फ़ंक्शन की गणना dominates(s,a) निम्नानुसार निष्पादित की जाती है (प्रत्येक बाद के चरण का प्रदर्शन किया जाता है यदि पिछले एक पर यह निर्धारित करना संभव नहीं था कि कौन सा प्रतीक हावी है):

1. वर्णों की ज्यामितीय व्यवस्था की जाँच करना।
2. चरित्र वर्ग की जाँच करें। उदाहरण के लिए, अंश वर्ण अंक वर्ण पर हावी होगा।
3. सापेक्ष चरित्र आकारों की जाँच करना

यदि एल वर्णों की एक आदेशित सूची है, तो आप निम्नलिखित पुनरावर्ती प्रक्रिया का प्रदर्शन करके सूची में सबसे बाईं ओर के चरित्र का निर्धारण कर सकते हैं:
getDominantSymbol(L): n = length(L) — . n==1, s(n) s(n) s(n-1) , s(n-1) L, s(n) getDominantSymbol(L).

1. getDominantSymbol(L): n = length(L) — . n==1, s(n) s(n) s(n-1) , s(n-1) L, s(n) getDominantSymbol(L).
2. getDominantSymbol(L): n = length(L) — . n==1, s(n) s(n) s(n-1) , s(n-1) L, s(n) getDominantSymbol(L).
3. getDominantSymbol(L): n = length(L) — . n==1, s(n) s(n) s(n-1) , s(n-1) L, s(n) getDominantSymbol(L).
4. getDominantSymbol(L): n = length(L) — . n==1, s(n) s(n) s(n-1) , s(n-1) L, s(n) getDominantSymbol(L).

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

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

तब इस अभिव्यक्ति का आधारभूत वृक्ष इस तरह दिखेगा:


प्रमुख आधार रेखा Db का निर्माण निम्न फ़ंक्शन के उपयोग से किया जाता है:
constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)


1. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

2. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

3. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

4. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

5. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

6. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

7. constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)


constructDominantBaseline(Db,L):
Db , Db = addSymbol(Db,getDomninantSymbol(L)) s = getLastSymbol(Db) Hs = getRightNeighbors(s,L) L, s Hs , Hs, sd = getDominantSymbol(Hs) Db = addSymbol(Db,sd) : constructDominantBaseline(Db,L)

बेसलाइन ट्री को एल की एक ऑर्डर की गई सूची द्वारा वर्णित अभिव्यक्ति में प्रमुख आधार रेखाओं को पुन: खोजकर बनाया गया है।
ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5


1. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

2. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

3. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

4. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

5. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

6. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

7. ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5


ConstructBaselineTree(L):
L , Db constructDominantBaseline(Db,L) Db, , s Db , , , L = Db , constructBaselineTree -, 5

परिणामी पेड़ एक गणितीय अभिव्यक्ति की एक संरचना है, और, पार्स होने के कारण, यह सूत्र संपादक के कोड में बदल सकता है। मेरे मामले में, यह OpenOffice संपादक है।

यह सब क्या हुआ

और यह GLDDOS निकला, इस एल्गोरिथम से एक एप्लिकेशन निकला, जो, हालांकि यह व्यक्तिगत पात्रों को पहचानने में गलती करने की क्षमता के बिना नहीं है, मक्खी पर काफी जटिल गणितीय अभिव्यक्तियों को पहचान सकता है। यह कैसा दिखता है:


और यह पहचान सकता है, हालांकि कभी-कभी त्रुटियों के बिना नहीं, ये सूत्र (और जो पहले एक चरित्र पहचान त्रुटि पाता है - अच्छी तरह से किया :-)

उपसंहार

तो मेरा Habré पर पहला लेख समाप्त हो गया। मुझे आशा है कि वह बहुत उबाऊ नहीं थी, और किसी के लिए उपयोगी होगी! आपका ध्यान के लिए धन्यवाद!

संदर्भ:

1. निकोलस मात्सकिस। हस्तलिखित गणितीय अभिव्यक्तियों की मान्यता। मास्टर की थीसिस, मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी, कैम्ब्रिज, एमए, मई 1999।
2. अर्नेस्टो तापिया: अंडरस्टैंडिंग मैथमेटिक्स: अ सिस्टम फॉर रिकग्निशन ऑफ ऑन-लाइन हैंड राइटिंग मैथमेटिकल एक्सप्रेशंस, बर्लिन, 2004
3. ईवा गैलार्डो पेरेज़: सीएमपी गणितीय फॉर्मूला ऑन-लाइन मान्यता प्रणाली के 2 डी व्याकरण विस्तार, सीएमपी की शोध रिपोर्ट, प्राग में चेक तकनीकी विश्वविद्यालय, नहीं। ३, २०० ९