Priority levels and heuristic rules in the structural recognition of mathematical formulae

• Autorzy: Sroczyński S.

Warianty tytułu

PL

Rola priorytetów i reguł heurystycznych w rozpoznawaniu struktury wzorów matematycznych

• Języki publikacji: EN

Abstrakty

EN

In the paper an algorithm for an automatic recognition of the structure of mathematical formulae saved in a graphical form has been presented. The described method is based on 2D graph grammars, although the other approaches were mentioned. Moreover, the heuristic rules used during the simplification of the initial data structure, the example graph grammar rules, the priority system used within the production of the rules, and the test application that allows the step-by-step analysis of an entire recognition process, were discussed. The solution introduced in the paper allows to analyse web pages and the other documents containing a math notation saved in graphics formats. It will also help in the development of systems indexing, searching and translating such documents to formats used by visually impaired people.

PL

W pracy przedstawiono algorytm automatycznego rozpoznawania struktury wzorów matematycznych zapisanych w postaci graficznej, wykorzystujący gramatykę grafową. Opisane zostały reguły heurystyczne stosowane w celu uproszczenia inicjalnej struktury danych, przykładowe reguły gramatyki oraz aplikacja testowa, pozwalająca na analizę procesu rozpoznawania w trybie krokowym. Szczególną uwagę poświęcono zagadnieniom związanym z systemem priorytetów i reguł heurystycznych pozwalających na efektywne przetwarzanie grafu opisującego rozpoznawane wyrażenie za pomocą reguł zdefiniowanej gramatyki. Zastosowanie opisanego rozwiązania do przetwarzania stron internetowych oraz innych dokumentów zawierających wzory matematyczne osadzone w postaci graficznej pozwoli na indeksowanie, katalogowanie i wyszukiwanie ich treści, a także translację do formatów używanych przez osoby niepełnosprawne wzrokowo.

Słowa kluczowe

EN

structural recognition; mathematical notation; graph grammars

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2010
• Tom: Vol. 22, No. 4
• Strony: 273--289
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Sroczyński S.

• Institute of Mathematics, Silesian University of Technology

Bibliografia

• 1. P. Brzoza, P. Skurowski: Biblioteka internetowa dostępna dla osób niewidomych. Studia Informatica Vol. 24 No. 3 (55), Gliwice 2003.
• 2. Y. Eto, M. Suzuki: Mathematical Formula Recognition Using Virtual Link Network, Proceedings of the Sixth International Conference on Document Analysis and Recognition,Seattle, IEEE Computer Society Press (ICDAR ’01), pp: 762-768, ISBN:0-7695-1263-1 IEEE Computer Society, Washington, USA 2001.
• 3. A. Kosmala, G. Rigoll, S. Lavirotte, L. Pottier: On-Line Handwritten Formula Recognition using Hidden Markov Models and Context Dependent Graph Grammars, Proceedings of the Fifth International Conference on Document Analysis and Recognition (ICDAR’99), pp. 107-110, Bangalore, Indie, 1999.
• 4. S. Lavirotte, L. Pottier: Optical Formula Recognition in: Proceedings of the Fourth International Conference on Document Analysis and Recognition (ICDAR’97), I.C. Society,Proc. SPIE1, vol. 1, pp. 357-361, IEEE Computer Society Press 1997.
• 5. S. Lavirotte, L. Pottier: Mathematical Formula Recognition Using Graph Grammar, Electronic Imaging 1998. Document Recognition V, volume 3305, pages 44-52, SPIE – The International Society for Optical Engineering, San José, USA 1998.
• 6. S. Smithies, K. Novins, J. Arvo: Equation Entry and Editing via Handwriting and Gesture Recognition, Behaviour and Information Technology 20(1):53-67, January 2001.
• 7. A. Sroczyńska, Z. Sroczyński: Telepraca i zdalna edukacja osób niepełnosprawnych wzrokowo, Zeszyty Naukowe Politechniki Śląskiej w Gliwicach Seria Organizacja i Zarządzanie, z. 35, ISSN 1641-3466, pp. 183-192, Gliwice 2006.
• 8. Z. Sroczyński: Prezentacja dokumentów internetowych zawierających złożoną notację matematyczną dla potrzeb osób niewidomych, Studia Informatica Vol. 24, No3(55), s. 179-187, Gliwice 2003.
• 9. Z. Sroczyński: Automatyczne rozpoznawanie struktury dokumentów zawierających złożoną notację matematyczną. w: Węgrzyn S., Pochopień B., Czachórski T. (red.): Współczesne problemy sieci komputerowych. Nowe technologie. str. 341-348, ISBN 83-204-3010-0, Wydawnictwa Naukowo-Techniczne 2004.
• 10. Z. Sroczyński: Optymalizacja struktur danych opisujących dokumenty zawierające złożoną notację matematyczną. w: Internet w społeczeństwie informacyjnym. Techniczne i społeczne problemy zastosowania Internetu, pod red. A. Kwiecień, K. Wódz, pp. 225-238, ISBN 83-206-1590-9, Wydawnictwa Komunikacji i Łączności, Warszawa 2005.
• 11. Z. Sroczyński: Automatyczne rozpoznanie struktury złożonej notacji matematycznej osadzonej w postaci graficznej na stronach internetowych. w: Współczesna problematyka sieci komputerowych, pod red. Kwiecień A., Gaj P., Jestratjew A., pp. 185-198, ISBN 978-83-206-1778-8, Wydawnictwa Komunikacji i Łączności, Warszawa 2010.
• 12. P. Viola, E.G. Miller: Ambiguity and Constraint in Mathematical Expression Recognition, Proc. 15th National Conf. on Artificial Intelligence (AAAI 98), pp. 784-791, Madison, Wisconsin, July 1998.