Navigation – Plan du site

AccueilTroisième série22A new strategy for Arabic OCR bas...

A new strategy for Arabic OCR based on script analysis and synthesis

Une nouvelle stratégie pour la reconnaissance optique de caractères arabes basée sur l'analyse et la synthèse de l'écriture
إستراتيجية جديدة للتعرُّف الضوئي على الحروف العربية استناداً إلى تحليل وتوليف خطوط الكتابة
Alicia González Martínez et Thomas Milo
p. 21-30

Résumés

La reconnaissance automatique de caractères (OCR) a connu d’importantes améliorations ces dernières années, même si les stratégies OCR conventionnelles n'exploitent pas encore les concepts linguistiques sur l'analyse de l'écriture arabe. Nous présentons une stratégie supplémentaire, nouvelle, qui vise à améliorer l'OCR en arabe. Dans cette approche, les points de désambiguïsation sont temporairement éliminés, ce qui réduit les classes de graphèmes partageant le même élément de base à des archigraphèmes uniques. En outre, le comportement contextuel des archigraphèmes arabes est redéfini comme une fusion : les archigraphèmes fusionnent de manière méconnaissable en blocs de lettres selon un système basé sur des règles appelées grammaire de script. Le bloc de lettres est défini comme l'unité minimale de formation de l'écriture arabe. Par exemple, le mot بحوث se compose de deux blocs de lettres, des groupes d'allographes fusionnés entourés d'un espace graphique, ٮحو et ٮ (BGW B). D'un corpus arabe d'environ 85 millions de mots, nous avons extrait une liste d'environ 47 000 blocs de lettres archigraphèmiques uniques, ce qui implique que nous avons réduit le système d'écriture arabe dynamique et génératif aux proportions d'une écriture statique comme le chinois. Nous montrons ensuite comment synthétiser toutes les formes théoriques pour chaque bloc de lettres à partir de modèles informatiques de styles d'écriture islamiques spécifiques (ruqʿä, naskh, nastaʿlīq). Ce n'est que dans la dernière étape que nous devrons désambiguïser les archigraphèmes en graphèmes réels en utilisant des informations linguistiques, dont une partie a déjà été recueillie dans le corpus de 85 millions de mots. Cette approche rend également possible une formation initiale à l'OCR sur des textes rendus avec les mêmes modèles d'écriture islamiques.

Haut de page

Texte intégral

Introduction

1Conventional Arabic OCR systems are based on a typographic perception of script, assuming that glyphs, the units of mechanical reproduction of script, have a logical relation with graphemes, the units of script itself. Current methods try to recognise script by splitting chunks of text into paragraphs, paragraphs into lines, lines into words, and words into characters or sub-characters (Srihari and Ball 2014: 7-8). This approach follows the traditional mechanics of the 15th century printing press, where actual shapes of letters or groups of letters are represented in types or sorts, i.e., in physical boxes: the glyphs of today's font technology. It inadvertently treats the glyph as the smallest unit of Arabic script, whereas in reality, glyphs are not. For example, it is quite usual in manuscripts to find a grapheme compound ب, there the base grapheme ٮ B and the dot grapheme are not in the same physical space, but the dot grapheme may appear in a nearby area. An example of this reality can be seen in figure 1. As a result, an algorithm for an OCR system that takes the glyph as a basic unit for recognition won’t be able to provide high rates of success. The typographic bias of the printing press tradition as the base of OCR systems has already been described by Milo and González Martínez (2019). Figure 1 describes a typical example of writing found in manuscripts where conventional recognition algorithms for OCR methods would fail.

Figure 1a

Figure 1a

A LFW BH A LY BKW N BHA A LFKR W A LFW H A LY BHA, manuscript scan

Figure 1b

Figure 1b

[…] l-qawiyyätu llatī yakūnu bihā l-fikru wa l-quwwätu llatī bihā […], orthographic and typographic normalisation

Figure 1c

Figure 1c
  • 1 The document clearly displays we l-qiwweh in spite of the fact that normalized classical Arabic pr (...)

[…] l-qawiyyeh lletī yekūn behā l-fikru we l-qiwweh lletī behā […], digital approximation of fig 1, with matching transcription of missing vowels as [e]1

Figure 1d

Figure 1d

A LFW BH A LY BKW BHA A LFKR W A LFW H A LY BHA, archigraphemic reduction of fig. 1

Interference of typographic legacy in OCR systems

2Conventional Optical Character Recognition systems are based on a mechanical breakdown of Arabic script: Arabic letters have two or four contextual shapes and any exception to this definition is considered to be a ligature. Until well into the 1980s, metal and photo typesetting were the only means to produce professional Arabic typography. Typeset Arabic was usually set with many ligatures, i.e., exceptions to the two-shape and four-shape breakdown, which justifies the question: what drives type-makers to implement so many exceptions to a practical two-shape and four-shape breakdown? To us this is an academically justified question. However, authoritative scholars like W. Wright dismissed ligatures as inconvenient to printers without even attempting to find a plausible explanation for their existence in the first place (Wright 1859: paragraph 1, remark C). In this spirit, scholars have made no effort since, to address this aspect of Arabic studies (see Mitchell 1953: 2). The only systematic description of an Arabic writing system is made by T.F. Mitchell, a linguist with a background in Romance languages (Michell 1953). We propose to take this subject seriously and acknowledge that ligatures are an integral part of the type-makers effort to mechanise Arabic script as accurately as possible (Milo 2011). This implies that the four-shape breakdown fails to cover the reality of Arabic manuscript practice, which, after all, was the model for Arabic typography. From this it follows, that the first step in the academic approach of both Arabic script mechanisation and script recognition has to be a comprehensive analysis and description of the contextual shaping rules that are shared between all instances of writing in a given Islamic script style. Since this results in a description of a rule-based communication system, we propose to call such a system a script grammar of a given style.

Figure 2

Figure 2

State-of-the-art approach to Arabic OCR

Computer analysis and synthesis of Islamic script

3We propose to exploit the existing results of script grammar research in the form of operational computer typefaces that reproduce with great precision the average naskh style, ruqʿä style, and both the Persian and Indian Subcontinental flavours of the nastaʿlīq style [8]. Script grammar covers the rules for basic shaping inside a group of connected letters (letter block), including various dissimilation conventions that enhance legibility (Milo 2002: 120). The simplified two/four-shape model lost this latter characteristic feature of Islamic script (Nemeth 2017: 109-114).

4In addition to basic shaping, script grammar also observes and describes extended shaping. Extended shaping is ruled by several factors, such as elongation, alternative shaping and swashing (Nemeth 2017: 433). These computer models of Islamic scripts are presently available as typefaces in various typesetting systems (Nemeth 2017: 428-433), but we propose to use them in a totally different manner: for generating exhaustive lists of all theoretically possible results of basic and extended shaping combined. In the design process of these computer models this was already done: before a computer model of an Islamic script is released as a typeface, a simple program is used to test the logic of all theoretical letter permutations of up to 8 letters in the process, its basic shaping alone generates billions of results (source: DecoType, designers of computer typography, Amsterdam).

Figure 3

Figure 3

Repetitions of the denticle: B BB BBB BBBB BBBBB BBBBBB (transliterated as archigrapheme B) exposes the absence of script grammatical basic shaping of denticles in typographical simplifications of Arabic.

Figure 4

Figure 4

Basic script grammatical shaping of denticles according to the rules of naskh: 1. no more than two consecutive low denticles are allowed. 2. raised denticles must be separated by two low denticles (note: this rule does not apply in nastaʿlīq).

Figure 5

Figure 5

Extended shaping, illustrated with elongating of letters. BB-BBBB (with elongation of the second denticle), contrasted with basic shaping. 3. from a group of consecutive denticles in letter block initial position the first one cannot be stretched. 4. three consecutives low denticles are only allowed, when the first or the second one is stretched (in this example, stretching the first one is blocked by rule 3).

Figure 6

Figure 6

Extended shaping with elongation of the third denticle: BBB-BBB, which maintains with rule 1: two groups of three denticles that need the middle one to be raised. Again, contrasted with basic shaping.

Figure 7

Figure 7

Extended shaping with elongation of the fourth denticle: BBBB-BB, the combination of rule 4 and rule 1 causes the third denticle to raise into dissimilation mode. The combination of rule 5 and 6 blocks the elongation of the fifth denticle. This leaves the fourth denticle as the only remaining candidate for lengthening. 5. a final denticle counts as an elongated denticle; 6. consecutive elongated characters are not allowed; 7. a raised denticle cannot be stretched.

Reducing Arabic script to its essence

5The possibility to synthesise exhaustive lists of correctly and realistically shaped traditional letter groups, opens the perspective to use this computer synthesis as a technique to train OCR to deal with it. A proof-of-concept could be accomplished by teaching an OCR system to recognise existing computer-generated grammatically formed script, for instance, as employed in the typographically dynamic Omani web Qur’ân: www.mushafmuscat.om, released in 2017.

6However, given the massive numbers of shapes that would have to be synthesised and analysed, a drastic reduction is mandatory to create an example of any possible letter group of a given Islamic script. A first step to obviate this obstacle is to reduce the theoretical repertoire of shapes by removing all diacritics: what remains are archigraphemes as nominal text in Unicode format, i.e., irrespective of any contextual shaping.

Generating the list of archigraphemic letter blocks encountered in the Arabic language

7We created a utility that automatically converts any Arabic text to archigraphemes. With this archigraphemic reduction it becomes possible to collect from huge corpora of Arabic-scripted text all instances of connected letter groups or letter blocks that are in actual use. In this manner many billions of theoretical letter permutations are reduced to a list of less than sixty thousand actually attested archigraphemic letter blocks. To verify this assumption, we extracted from two large representative Arabic corpora all actually used archigrapemic letter blocks:

  • The first corpus is the COBHUNI corpus (González Martínez, Feige 2017), which consists of hadith literature and tafsir, i.e., Quranic exegesis. The hadith material has been extracted from a website2 and contains both original hadiths and commentaries.3
  • The second corpus is a subset from the OpenITI (Miller, Romanov, Bowen Savant 2018), a corpus of pre-modern texts in Arabic. This subset contains 85.4 million words, extracted randomly from historical texts in Arabic script, and constitutes a representative sample of the Arabic language. The OpenITI is an effort to create the largest scholarly corpus of premodern Arabic texts to this day. Thus, it is the most suitable dataset to extract a representative list of letterblocks that exist in Arabic.

8We tokenised both corpora and then performed the archigrahemic reduction on all words, keeping a mapping between each archigraphemic letter block and the actual word form it occurs in. The size of both subsets and the lists of archigraphemes can be seen in Table 1. This same procedure would work for any other language written in Arabic script.

Figure 8

Figure 8

Generation of a corpus of archigraphemes mapped to the actual word forms they appear in.

Table 1

Corpora Number of tokens Number of letter blocks
Complete Cobhuni Corpus 21,026,587 35,509
Subcorpus taken from OpenITI 64,373,842 46,731
Total 85,400,429 53,217

Size of corpora used to extract the list of unique archigraphemic letter blocks and number of letter blocks in resulting list.

Samples of authentic shape generation

9With the availability of a limited list of attested instances of Arabic letter blocks, applying script synthesis in the development of OCR for script grammatically formatted texts becomes a realistic and practicable proposition.

Figure 9

Figure 9

Extended shaping of the letter block FLKL, generated by one of two parameters or combinations of them: 1. elongation, 2. alternative shaping

10There is now the prospect of building an OCR system based on a representative repertoire of a few hundred thousand of Unicode-indexed computer-synthesised theoretical forms. Finally, this approach also opens the perspective of training intelligent shape recognition software to recognize any product of a given script grammar.

Present state of the research and first results

  1. Islamic script synthesis: we have existing script grammatical typefaces at our disposal;
  2. We implemented an algorithm for conversion from plene orthography to archigraphemic transliteration in Unicode format;
  3. We implemented real-time conversion of step 2 in a search algorithm;
  4. Steps 2 and 3 resulted in the creation of the list of unique archigraphemic letter blocks;
  5. We are able to generate Unicode-indexed exhaustive lists of theoretical shapes of any of the listed letter blocks.

Conclusion

11With this research we lay the basis for OCR technology that exploits available typographic technology based on deep analysis of Arabic script structures. The next steps are:

  • to locate or create matching Artificial Intelligence software to teach OCR to recognize any unmapped letter blocks in order to make the OCR dynamic;
  • to identify the language;
  • to apply linguistic parsing to infer and verify the dot and vowel diacritics.
Haut de page

Bibliographie

González Martínez A., Feige T., 2017, “Herausforderungen in der Nutzung vorhandener Tools für arabische Daten”, Conference abstracts DHd 2017 Digitale Nachhaltigkeit, Bern, Switzerland, p. 67-70.

Miller M.T., Romanov M.G., Bowen Savant S. 2018, “Digitizing the Textual Heritage of the Premodern Islamicate World: Principles and Plans”, International Journal of Middle East Studies 50, 1 (February 2018), p. 103-109.

Milo T., 2011, “Arabic Typography”, in Lutz Edzard, Rudolf de Jong (eds Online Edition), Encyclopedia of Arabic Language and Linguistics, URL: https://referenceworks.brillonline.com/entries/encyclopedia-of-arabic-language-and-linguistics/arabic-typography-EALL_SIM_000043?s.num=10.

Milo T., González Martínez A., 2019, “A new strategy for Arabic OCR: Archigraphemes, Letter Blocks, Script Grammar and shape synthesis”, Datech 2019, p. 93-96.

Milo T., 2002, “Arabic script and typography, a brief historical overview”, in Berry, J.D. (ed.), Language Culture Type, International type design in the age of Unicode, New York: ATypI and Graphis, p. 112-127.

Mitchell T.F., 1953, Writing Arabic: A Practical Introduction to Ruqah Script, Oxford: Oxford University Press.

Nemeth T., 2017, Arabic Type-Making in the Machine Age. The Influence of Technology on the Form of Arabic Type, 1908–1993, Series: Islamic Manuscripts and Books, vol. 14, p. 109-114.

Srihari S.N., Ball G. 2014, “An Assessment of Arabic Handwriting Recognition Technology”, in Volker Märgner and Haikal El Abed, Guide to OCR for Arabic Scripts, London: Springer, p. 3-34.

Wright W., 1859, A grammar of the Arabic language: translated from the German of Caspari, and edited with numerous additions and corrections, London: Williams and Norgate.

Haut de page

Notes

1 The document clearly displays we l-qiwweh in spite of the fact that normalized classical Arabic prescribes wa l-quwwätu. Text editions routinely correct “errors” when the observed text does not match the norm. See for example Akkach S. 2010 (Letters of a Sufi Scholar) p. XXI: […] “ʾ is generally used instead of the hamza […]. Except when it was necessary to keep yāʾ for rhyming purposes, hamza is used throughout, as required in formal Arabic.” Another representative example is M. Kozah 2020 (The Yoga Sutras of Patañjali) p. XXV: “hamzahs […] have been added or changed (e.g., changing جزوية to جزئية.” This is a subjective or text editing aspect that is not covered by this article, which concentrates on strictly objective recognition.

2 URL: http://hadith.al-islam.com, consulted on 01/11/2016.

3 The tafsir material has been extracted from www.altafsir.com.

Haut de page

Table des illustrations

Titre Figure 1a
Légende A LFW BH A LY BKW N BHA A LFKR W A LFW H A LY BHA, manuscript scan
URL http://journals.openedition.org/ema/docannexe/image/13146/img-1.jpg
Fichier image/jpeg, 393k
Titre Figure 1b
Légende […] l-qawiyyätu llatī yakūnu bihā l-fikru wa l-quwwätu llatī bihā […], orthographic and typographic normalisation
URL http://journals.openedition.org/ema/docannexe/image/13146/img-2.jpg
Fichier image/jpeg, 333k
Titre Figure 1c
Légende […] l-qawiyyeh lletī yekūn behā l-fikru we l-qiwweh lletī behā […], digital approximation of fig 1, with matching transcription of missing vowels as [e]1
URL http://journals.openedition.org/ema/docannexe/image/13146/img-3.jpg
Fichier image/jpeg, 303k
Titre Figure 1d
Légende A LFW BH A LY BKW BHA A LFKR W A LFW H A LY BHA, archigraphemic reduction of fig. 1
URL http://journals.openedition.org/ema/docannexe/image/13146/img-4.jpg
Fichier image/jpeg, 261k
Titre Figure 2
Légende State-of-the-art approach to Arabic OCR
URL http://journals.openedition.org/ema/docannexe/image/13146/img-5.jpg
Fichier image/jpeg, 254k
Titre Figure 3
Légende Repetitions of the denticle: B BB BBB BBBB BBBBB BBBBBB (transliterated as archigrapheme B) exposes the absence of script grammatical basic shaping of denticles in typographical simplifications of Arabic.
URL http://journals.openedition.org/ema/docannexe/image/13146/img-6.jpg
Fichier image/jpeg, 26k
Titre Figure 4
Légende Basic script grammatical shaping of denticles according to the rules of naskh: 1. no more than two consecutive low denticles are allowed. 2. raised denticles must be separated by two low denticles (note: this rule does not apply in nastaʿlīq).
URL http://journals.openedition.org/ema/docannexe/image/13146/img-7.jpg
Fichier image/jpeg, 30k
Titre Figure 5
Légende Extended shaping, illustrated with elongating of letters. BB-BBBB (with elongation of the second denticle), contrasted with basic shaping. 3. from a group of consecutive denticles in letter block initial position the first one cannot be stretched. 4. three consecutives low denticles are only allowed, when the first or the second one is stretched (in this example, stretching the first one is blocked by rule 3).
URL http://journals.openedition.org/ema/docannexe/image/13146/img-8.jpg
Fichier image/jpeg, 21k
Titre Figure 6
Légende Extended shaping with elongation of the third denticle: BBB-BBB, which maintains with rule 1: two groups of three denticles that need the middle one to be raised. Again, contrasted with basic shaping.
URL http://journals.openedition.org/ema/docannexe/image/13146/img-9.jpg
Fichier image/jpeg, 21k
Titre Figure 7
Légende Extended shaping with elongation of the fourth denticle: BBBB-BB, the combination of rule 4 and rule 1 causes the third denticle to raise into dissimilation mode. The combination of rule 5 and 6 blocks the elongation of the fifth denticle. This leaves the fourth denticle as the only remaining candidate for lengthening. 5. a final denticle counts as an elongated denticle; 6. consecutive elongated characters are not allowed; 7. a raised denticle cannot be stretched.
URL http://journals.openedition.org/ema/docannexe/image/13146/img-10.jpg
Fichier image/jpeg, 21k
Titre Figure 8
Légende Generation of a corpus of archigraphemes mapped to the actual word forms they appear in.
URL http://journals.openedition.org/ema/docannexe/image/13146/img-11.jpg
Fichier image/jpeg, 115k
Titre Figure 9
Légende Extended shaping of the letter block FLKL, generated by one of two parameters or combinations of them: 1. elongation, 2. alternative shaping
URL http://journals.openedition.org/ema/docannexe/image/13146/img-12.jpg
Fichier image/jpeg, 419k
Haut de page

Pour citer cet article

Référence papier

Alicia González Martínez et Thomas Milo, « A new strategy for Arabic OCR based on script analysis and synthesis »Égypte/Monde arabe, 22 | 2020, 21-30.

Référence électronique

Alicia González Martínez et Thomas Milo, « A new strategy for Arabic OCR based on script analysis and synthesis »Égypte/Monde arabe [En ligne], 22 | 2020, mis en ligne le 03 janvier 2022, consulté le 23 septembre 2023. URL : http://journals.openedition.org/ema/13146 ; DOI : https://doi.org/10.4000/ema.13146

Haut de page

Auteurs

Alicia González Martínez

Alicia González Martínez (Universität Hamburg), is a research associate on computational linguistics at the Asien-Afrika-Institut, Universität Hamburg. She has a multidisciplinary profile covering Arabic linguistics, Oriental studies and software development, with a special focus on Arabic Natural language processing. She completed her PhD in 2013 on Arabic computational morphology and is the developer of YaKabikaj, a search utility for Arabic-scripted texts.

Thomas Milo

Thomas Milo (DecoType), linguist and computer typography pioneer specialized in writing systems and Arabic-scripted typography from Amsterdam, the Netherlands. He published many articles on the structure and history of Arabic script, notably on the scientific analysis of classical Arabic scripts which led to the introduction of the concept of script grammar. Distinctions: Unicode Bulldog Award 2000 for fundamental contributions to digital text encoding – Dr Peter Karow Award 2003 for exceptional and innovative contributions to the development of digital type and typography related technology. www.decotype.com.

Haut de page

Droits d’auteur

CC-BY-NC-SA-4.0

Creative Commons - Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International - CC BY-NC-SA 4.0

https://creativecommons.org/licenses/by-nc-sa/4.0/

Haut de page
Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search