Bangor University

DOCTOR OF PHILOSOPHY
A Novel Approach to Printed Arabic Optical Character Recognition

Alghamdi, Mansoor
Award date:2019
Awarding institution:
Bangor University
Link to publication

General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.
• Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal ?
Take down policy
If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately
and investigate your claim.
Download date: 29. Sept. 2024

Bangor University

DOCTOR OF PHILOSOPHY
A Novel Approach to Printed Arabic Optical Character Recognition

Alghamdi, Mansoor
Award date:2019

Link to publication

General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.
• Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal ?
Take down policy
If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately
and investigate your claim.
Download date: 23. Sep. 2019

School of Computer Science

A Novel Approach to Printed Arabic
Optical Character Recognition
Mansoor Ali Alghamdi

Submitted in partial satisfaction of the requirements for the
degree of Doctor of Philosophy
in Computer Science

Supervisor: Dr William J. Teahan

Abstract
Optical character recognition (OCR) is essential in various real-world applications,such as digitizing learning resources to assist visually impaired people andtransforming printed resources into electronic media. Considering the Arabic
language, the need to extend digital Arabic content on the Internet has motivated more
research on Arabic text recognition. However, Arabic OCR still poses significant
challenges, owing to the special characteristics of Arabic script. This research aims todevelop an effective printed Arabic OCR system.
Performance evaluation of OCR systems is an essential task for OCR systems
development. However, studies in Arabic OCR suffer from the lack of proper
performance evaluation metrics, the availability of evaluation tools and effective
performance evaluation of current OCR systems. Thus, this work proposes a standard
protocol with an automated evaluation tool, which has a new set of metrics, formeasuring the effectiveness of Arabic OCR systems. In addition, the effectiveness ofthe state-of-the-art printed Arabic text recognition systems have been experimentally
evaluated.
In this work, we describe the implementation of a printed Arabic OCR system. The
implantation of this system is divided into five stages: pre-processing, feature
extraction, character segmentation, classification and post-processing. Unlike othertypical Arabic OCR systems, the developed system performs the feature extraction
stage prior to the character segmentation stage.
In the pre-processing stage, a novel thinning algorithm is developed in order to produce
skeletons for Arabic text images. An evaluation experiment is conducted to evaluate
the performance of the new algorithm against other well established thinningalgorithms with respect to several new performance metrics. In all performance tests,
the new algorithm produces the best results. In the second stage, a new chain-code
representation technique using an agent-based model for extracting features from nondotted Arabic text images has been proposed. The feature extraction method achieved
an accuracy of 98.1%. Based on the extracted features, a character segmentation
technique for segmenting connected Arabic words into characters was developed. Thev

character segmentation technique produced a recall of 84.2% and a precision of 77.3%.
In the classification stage, the Prediction by Partial Matching (PPM) compression
based method is applied as a classifier to recognise Arabic text. Experimental
evaluation on a public dataset reveals that the system has an accuracy of 77.3% forparagraph-based text images. In the final stage, a post-processing technique based on
a PPM model is applied for correcting the OCR output. By applying the postprocessing method, the recognition accuracy improves to 86.9%. The experimental
results show that the system substantially improves upon the state-of-the-art whencompared with four well-known Arabic OCR systems using the automated evaluation
tool.

vi

Acknowledgments
First, I would like to express my deep gratitude to my supervisor Dr. William J. Teahan
who was abundantly helpful and offered invaluable assistance, support and guidance.
I could not have imagined having a better supervisor for my PhD study.
Many thanks to my beloved wife Maryam for her understanding and endless love,throughout the duration of my studies.
Special thanks to my son Meshari, who is the pride and joy of my life, for putting up
with me when I was busy working on my thesis instead of playing with him.
Last but not the least, I would like to thank my parents, brothers and sisters who
deserve special mention for their support. Especially my mother is the one who
truthfully raised me with her caring and gently love and her every day prayers. I would
not be in this position without her.

vii

Table of Contents
Abstract .................................................................................................................................... ii
Acknowledgments.................................................................................................................. vii
Table of Contents .................................................................................................................. viii
List of Figures ......................................................................................................................... xi
List of Tables ........................................................................................................................ xiv
List of Abbreviations ............................................................................................................. xv
Chapter 1: Introduction ............................................................................................................ 1
1.1 Background and Motivation........................................................................................... 1
1.2 Research Questions ........................................................................................................ 2
1.3 Aims and Objectives ...................................................................................................... 3
1.4 Contributions.................................................................................................................. 4
1.5 Thesis Outline ................................................................................................................ 6
Chapter 2: Literature Review ................................................................................................... 8
2.1 Introduction .................................................................................................................... 8
2.2 Arabic script characteristics and challenges .................................................................. 9
2.3 General Arabic OCR methodology (model) ................................................................ 11
2.3.1 Preprocessing phase .............................................................................................. 122.3.2 Segmentation phase .............................................................................................. 18
2.3.3 Feature extraction phase........................................................................................ 23
2.3.4 Classification phase .............................................................................................. 27
2.3.5 Post-processing phase ........................................................................................... 34
2.4 Performance evaluation ............................................................................................... 35
2.5 Challenges and open problems .................................................................................... 37
2.6 Summary ...................................................................................................................... 41
Chapter 3: Experimental Evaluation of Arabic OCR Systems .............................................. 43
3.1 Introduction .................................................................................................................. 43
3.2 Metrics for Arabic OCR system performance evaluation ............................................ 44
3.3 An Automated Arabic OCR Evaluation Tool .............................................................. 48
3.4 Arabic OCR Systems ................................................................................................... 50
3.5 Experimental Protocol ................................................................................................. 52
3.6 Experimental Results and Discussion .......................................................................... 54
3.7 Summary and Conclusion ............................................................................................ 61
Chapter 4: Thinning ............................................................................................................... 62
4.1 Introduction .................................................................................................................. 62
4.2 An Efficient Thinning Algorithm for Arabic Text ....................................................... 64
4.3 Evaluating Thinning Algorithms for Arabic Text ........................................................ 66
4.3.1 Connectivity preservation metric .......................................................................... 67
4.3.2 Dot preservation metric......................................................................................... 69viii

4.3.3 Topology preservation metric ............................................................................... 69
4.3.4 Thinning rate (unit pixel width) ............................................................................ 70
4.4 Experimental Results and Discussion .......................................................................... 70
4.5 Summary and Conclusion ............................................................................................ 83
Chapter 5: Feature Extraction ................................................................................................ 84
5.1 Introduction .................................................................................................................. 84
5.2 Why This Approach? ................................................................................................... 85
5.3 New Feature Extraction Method .................................................................................. 87
5.3.3 Baseline determination.......................................................................................... 90
5.3.4 Word segmentation ............................................................................................... 92
5.3.5 Extraction of features ............................................................................................ 92
5.4 Experimental Evaluation .............................................................................................. 96
5.4.1 Baseline determination method evaluation experiment ........................................ 96
5.4.2 Word segmentation method evaluation experiment .............................................. 98
5.4.3 Feature extraction method evaluation experiment ................................................ 98
5.5 Summary and Discussion ........................................................................................... 102
Chapter 6: Character Segmentation ..................................................................................... 103
6.1 Introduction ................................................................................................................ 103
6.2 Arabic script features used for designing the character segmentation technique ...... 104
6.3 New character segmentation approach ...................................................................... 106
6.4 Experimental Results and Discussion ........................................................................ 107
6.5 Summary and Discussion ........................................................................................... 110
Chapter 7: Classification Using PPM .................................................................................. 112
7.1 Chapter Introduction .................................................................................................. 112
7.2 Implementation of PPM Classifier ............................................................................. 113
7.2.1 Stage I: Training stage ........................................................................................ 114
7.2.2 Stage II: Testing/recognition stage ..................................................................... 119
7.3 Experimental Evaluation Results ............................................................................... 119
7.3.1 Pre-segmented character images evaluation experiment .................................... 120
7.3.2 Paragraph-based text images evaluation experiment ......................................... 129
7.4 Discussion and Summary ........................................................................................... 133
Chapter 8: Post-processing .................................................................................................. 134
8.1 Chapter Introduction .................................................................................................. 134
8.2 Applying a PPM Language Model for Arabic Text Correction ................................. 135
8.3 Experimental Evaluation of PPM Correction Method ............................................... 136
8.3.1 PATRION OCR output correction experiment ................................................... 137
8.3.2 Commercial Arabic OCR output correction experiment .................................... 142
8.4 Overall Experimental Evaluation of the PATRION OCR System............................. 145
8.5 Discussion and Summary ........................................................................................... 149
Chapter 9: Conclusion and Future Work ............................................................................. 151
9.1 Chapter Introduction .................................................................................................. 151
9.2 Summary .................................................................................................................... 151
ix

9.3 Review of Aims and Objectives................................................................................. 154
9.4 Review of Research Questions .................................................................................. 155
9.5 Limitations of the Work ............................................................................................. 158
9.6 Future Work ............................................................................................................... 159
References ............................................................................................................................ 161
Appendices........................................................................................................................... 178

xList of Figures
Figure 1.1: Categories of OCR systems ................................................................................... 2
Figure 1.2: Thesis structure...................................................................................................... 7
Figure 2.1: Arabic script characteristics ................................................................................ 11
Figure 2.2: Two characters (Ba and Ya) with an identical shape and a different number ofdots ......................................................................................................................................... 11
Figure 2.3: General printed Arabic OCR methodology ......................................................... 12
Figure 2.4. An example of Arabic text skew ......................................................................... 14
Figure 2.5: Baseline detection of a printed Arabic text image ............................................... 16
Figure 2.6: An example of line segmentation ........................................................................ 20
Figure 2.7: Segmenting Arabic words into their characters ................................................... 22
Figure 2.8: Present status of printed Arabic OCR based on the number of publications fordifferent OCR elements ......................................................................................................... 40
Figure 2.9: Number of papers per 5-year period in the top 100 results returned by Google
Scholar for different Arabic OCR related search phrases ...................................................... 40
Figure 3.1. Loop characters ................................................................................................... 46
Figure 3.2. Diacritic marks .................................................................................................... 47
Figure 3.3. GUI of the Arabic OCR evaluation tool .............................................................. 48
Figure 3.4. A sample Arabic text image ............................................................................... 49
Figure 3.5. OCR output text for image in Fig. 3.4 ................................................................. 49
Figure 3.6. (a) A text image from the KAFD dataset; (b) output of the Sakhr OCR system;(c) output of the ABBYY OCR system; (d) output of the RDI OCR system; and (e) output of
the Tesseract OCR system ..................................................................................................... 55
Figure 3.7. Overall accuracy vs. resolution results from the OCR system evaluation ........... 55
Figure 3.8. Character accuracy in terms of character position results from the OCR systemevaluation ............................................................................................................................... 56
Figure 3.9. Dot character accuracy vs. no-dot character accuracy results from the OCR
system evaluation ................................................................................................................... 57
Figure 3.10. Dot character accuracy based on baseline results from the OCR systemevaluation ............................................................................................................................... 57
Figure 3.11. Character accuracy based on shaped character results from the OCR systemevaluation ............................................................................................................................... 58
Figure 3.12. Digit, punctuation and diacritics accuracy results from the OCR systemevaluation ............................................................................................................................... 58
Figure 3.13. Arabic OCR accuracy vs. font pitch size results from the OCR systemevaluation. .............................................................................................................................. 59
Figure 3.14. Italic and non-italic font accuracy comparison results from the OCR systemevaluation ............................................................................................................................... 59
Figure 4.1: Block diagram of the PATRION system ............................................................. 63
Figure 4.2: Examples of pixels (a), (b), (c) with an encasement and (d), (e), (f) without anencasement ............................................................................................................................. 64
Figure 4.3: Flowchart of Kocyigit algorithm ......................................................................... 65xi

Figure 4.4: Example of the problem of the connectivity metric: (a) an Arabic letter with four
components and (b) a skeleton for (a) with four components ................................................ 67
Figure 4.5. Using a graph to represent a text image: (a) text image and (b) graph for (a) ..... 68
Figure 4.6. One thinning example for text image in Figure 4.5(a): (a) its skeleton and (b) agraph for (a). .......................................................................................................................... 68
Figure 4.7. Another thinning example for text in Figure 4.5 (a): (a) its skeleton and (b) agraph for (a). .......................................................................................................................... 69
Figure 4.8. Example of dot perservation for thinning. (a) a skeleton and (b) a graph for (a) 69
Figure 5.1: Block diagram of the PATRION OCR system .................................................... 85
Figure 5.2: An Arabic text example that has identical characters but different pronunciation............................................................................................................................................... 86
Figure 5.3: An example of a worksheet that adopts the tracing handwriting strategy, from
(Garcia, 2005). ....................................................................................................................... 87
Figure 5.4. An example of how an Arabic letter “Laam” is traced ........................................ 88
Figure 5.5. An example of an Arabic text image conveyed into NetLogo ............................ 89
Figure 5.6. Block diagram of feature extraction method ....................................................... 90
Figure 5.7: Flowchart of the feature baseline determination algorithm ................................. 91
Figure 5.8. Screenshot from the NetLogo model that was developed for baseline
determination ......................................................................................................................... 91
Figure 5.9: Flowchart of feature extraction algorithm ........................................................... 93
Figure 5.10: Example of three branch points that occur in the Arabic word (“‫)”الكل‬............. 94
Figure 5.11: Tracing example for an Arabic word with features extracted in NetLogo ........ 95
Figure 5.12: Screenshot of the NetLogo model extracting features from an Arabic text image............................................................................................................................................... 96
Figure 5.14: Screenshot from NetLogo model showing example of incorrect baseline
determination using 3 as a threshold value ............................................................................ 97
Figure 5.13: Screenshot from NetLogo model showing example of correct baseline
determination using 7 as a threshold value ............................................................................ 97
Figure 5.15: An example of edit distance between two feature strings ................................. 99
Figure 5.17. Example of the effect of loss of visual information (caused by thinningalgorithm) on the feature extraction algorithm .................................................................... 101
Figure 5.16. Example of the effect of disconnection errors (produced by thinning algorithm)
on the feature extraction algorithm ...................................................................................... 101
Figure 6.1. Block diagram of the PATRION OCR system .................................................. 103
Figure 6.2: Examples of overlapping characters highlighted in Arabic words in different
fonts ..................................................................................................................................... 104
Figure 6.3: Junction line and branch point features of an Arabic word ............................... 106
Figure 6.4. A sample of applying character segmentation on an Arabic word .................... 107
Figure 6.5. Sample of segmenting overlapping characters .................................................. 109
Figure 7.1: Block diagram of the PATRION OCR system .................................................. 113
Figure 7.2: Text image example used in the recognition/testing stage ................................ 131
Figure 7.3: PATRION OCR output text produced for image in Figure 7.2 ......................... 131
Figure 8.1: Block diagram of the PATRION OCR system .................................................. 135
Figure 8.2: PPM correction of the PATRION OCR output text .......................................... 139
xii

Figure 8.3: PPM correction of the PATRION OCR output text .......................................... 140
Figure 8.4: PPM correction of the PATRION OCR output text .......................................... 141
Figure 8.5: PPM correction of the PATRION OCR output text .......................................... 142
Figure 8.6: Example of unreadable Sakhr OCR output text ................................................ 143
Figure 8.7: PPM correction of the ABBYY OCR output text ............................................. 144
Figure 8.8: Character position class accuracy comparison on KAFD dataset ..................... 147
Figure 8.9: Dot character class accuracy comparison on KAFD dataset ............................. 147
Figure 8.10: Baseline dot character class accuracy comparison on KAFD dataset ............. 148
Figure 8.11: Shape character class accuracy comparison on KAFD dataset ....................... 148
Figure 8.12: Overall Arabic OCR performance accuracy comparison on KAFD dataset ... 149

xiii

List of Tables
Table 2.1: Arabic characters with different positions and shapes .......................................... 10
Table 2.2: Processing the string ‘tobeornottobe’ using PPM ................................................ 33
Table 2.3: Google Scholar search results for Arabic OCR-related phrases ........................... 39
Table 3.1. An Arabic character with dissimilar shapes .......................................................... 45
Table 3.2. Examples of dot characters and no-dot characters ................................................ 45
Table 3.3. Examples of dot characters based on the baseline ................................................ 45
Table 3.4. Arabic OCR performance accuracy according to 10 different font types ............. 61
Table 4.1: Visual samples used in the evaluation .................................................................. 73
Table 4.2: comparing the three thinning algorithms on the samples ..................................... 83
Table 4.3: summary of results comparing the thinning algorithms ....................................... 83
Table 5.1: Results of baseline determination algorithm on sample test text images on
different Arabic fonts using threshold values between 5 and 7 based on text images ........... 98
Table 5.2: Error analysis according to different fonts and error types ................................. 102
Table 6.1: Testing dataset statistics...................................................................................... 108
Table 6.2. Segmentation Error Rate Percentage .................................................................. 109
Table 7.1: Combining Arabic characters in character classes, grouped according to theirmain type of shape ............................................................................................................... 115
Table 7.2: Training data for Stage I ..................................................................................... 116
Table 7.4: Examples of feature strings for character classes in Tables 7.2 and 7.3 ............. 117
Table 7.5: Confusion matrix using edit-distance for Arabic character of Simplified font-type.
............................................................................................................................................. 118
Table 7.6: Recognising the feature strings for five Arabic characters ................................. 119
Table 7.7: Confusion matrix for Traditional font-type classification using the 20 classes .. 122
Table 7.8: PPM classification results for the Traditional Arabic font type.......................... 123
Table 7.9: Confusion matrix for the Transparent font-type classification using the 20 classes............................................................................................................................................. 124
Table 7.10: PPM classification results for the Transparent Arabic font type ...................... 125
Table 7.11: Confusion matrix for the Simplified Arabic font-type classification using the 20classes .................................................................................................................................. 126
Table 7.12: PPM classification results for the Simplified Arabic font type ........................ 127
Table 7.13: Confusion matrix for the AdvertisingBold font type classification using the 20classes .................................................................................................................................. 128
Table 7.15 Recognition accuracy results on different Arabic fonts ..................................... 132
Table 7.16: Italic and normal font recognition accuracy results .......................................... 132
Table 7.17: Recognition accuracy results based on font pitch size ...................................... 132
Table 8.1: Set of confusions used for correcting the PATRION OCR output ..................... 136
Table 8.2: Sample of the confusions used that were generated from ABBYY OCR output 144
Table 8.3: Arabic OCR performance accuracy according to four font types ....................... 149

xiv

List of Abbreviations
BACC

Bangor Arabic Compression Corpus

GED

Graph Edit Distance

HHM

Hidden Markov Models

NLP

Natural Language Processing

NNs

Neural Networks

OCR

Optical Character Recognition

PATRION

Printed Arabic Optical Character Recognition

PPM

Prediction by Partial Matching

SVM

Support Vector Machines

xv

Chapter 1: Introduction
1.1 Background and Motivation
Optical character recognition (OCR) is a technique that transforms a printed or
handwritten text image into an electronic textual format. OCR development is
considered as a challenging task in the field of pattern recognition. Many OCR
approaches have been proposed for Latin and non-Latin scripts. Previous research on
text recognition has focused primarily on Latin scripts, such as English, and it has notbeen until the last two decades that recognition of non-Latin scripts, such as Arabic,
has been researched (Alginahi, 2013). Furthermore, owing to the special
characteristics of Arabic script, OCR for Arabic text still poses significant challenges(Slimane et al., 2013).
OCR applications can be categorized into two types, namely online text recognitionand offline text recognition (Ahmad, 2016). Figure 1.1 illustrates the different types oftext recognition systems. Offline text recognition systems perform on text that has
been previously written or printed on a page. Online text recognition systems, bycontrast, recognise text captured in real-time. Offline text recognition is further
classified into two types: handwritten text recognition and printed text recognition. In
contrast, online text recognitions systems are limited to recognising handwritten text.
Although handwritten script is significantly more challenging than printed Arabic text
for OCR, Arabic printed text OCR still poses significant challenges (Slimane et al.,2013). Therefore, this study will deal only with the printed text recognition type.
Generally, the process for developing a typical OCR system involves five stages: preprocessing, segmentation, feature extraction, classification and post-processing,(Khorsheed, 2002). A text image may need to go through the pre-processing stage forenhancing the readability of the image. During the segmentation stage, the text image
is segmented into small patterns, like segmenting words into characters. Then, features
are extracted from the segmented patterns to be utilized by the next stage which isclassification. The classification stage is responsible for assigning a pattern into a preclassified class based on the extracted features of the pattern. The final stage is thepost-processing stage which improves the recognition accuracy by detecting and1

correcting linguistic misspellings in the produced OCR text without humanintervention.
Arabic OCR is highly desirable in various real-world applications, such as digitisinglearning resources to assist visually impaired people, bank cheque processing and mailsorting (Al-Badr and Mahmoud, 1995; Alginahi, 2013). Furthermore, there are many
initiatives for Arabic digital content enrichment (Saad and Ashour, 2010). One of these
initiatives is King Abdullah’s Initiative for Arabic Content (Jambi, 2014). Recently,
Crown Prince Mohammed Bin Salman has established the global center for combating
extremist ideology. One of its objectives is to analyse online Arabic text, such as text
from Twitter that may have extremist content (Etidal, 2018). Twitter has a character
limit of 280 characters, so users are not able to add long tweets. However, users publish
their tweets on text images in order to avoid cramming their text into 280 characters.
Therefore, robust and efficient Arabic OCR is required to support the initiative by
increasing Arabic content on the Internet and to analyse online text images.

Figure 1.1: Categories of OCR systems
Note: The shaded text box is the scope of this research.

1.2 Research Questions
The following are the specific research questions being investigated in this study inorder to help achieve the primary aim of the project:Is the current OCR methodology which involves the five sequential stages (preprocessing; feature extraction; segmentation; classification and postprocessing) the most effective for designing Arabic OCR?

Are there alternative methodologies that might yield better results for Arabic
OCR?
2



Are the general standard performance measurements of character accuracy
sufficient to assess how Arabic OCR systems are coping with the challengesof Arabic script?



Are the available OCR systems sufficient to recognise printed Arabic text
images?



Can Arabic text be effectively recognised by considering Arabic text as nondotted text and then corrected later on in order to recover the dotted from?



Can a compression based method be effectively applied as a classifier for therecognition of the text features?

Can a compression based method be applied to Arabic OCR output that
contributes to significant improvement in Arabic text recognition accuracy?

1.3 Aims and Objectives
The primary aim of this study is to develop a novel OCR system for printed Arabic
script that substantially improves upon the state-of-the-art when compared withpresently available systems. A further aim is to develop new approaches that make useof compression-based language modelling as these have proven to be very effective
for many natural language processing (NLP) applications in the past but they have notyet been applied to the specific problem of Arabic OCR.
In order to fulfill these aims, the following objectives for this work are to:perform a comprehensive review of printed Arabic text recognition (seeChapter 2);develop an automated tool for evaluating the performance of Arabic OCR
systems (see Chapter 3);

evaluate the effectiveness of the state-of-the-art printed Arabic text recognition
systems (see Chapter 3);

design and implement a new thinning algorithm for Arabic text and evaluate
the effectiveness of the new algorithm by comparing it with well-known
thinning algorithms (see Chapter 4);3

develop a new chain-code representation technique using an agent-based modelfor extracting features from non-dotted Arabic text images prior to the character
segmentation phase (see Chapter 5);develop a new character segmentation technique for segmenting connectedArabic words into characters based on the extracted features (see Chapter 6);develop a new compression-based method for classifying the segmented
Arabic characters (see Chapter 7);use compression-based post-processing techniques (e.g., adding dots to Arabic
text and correcting the OCR output) (see Chapter 8);

1.4 Contributions
The main contribution of this study is the development of a novel OCR system forprinted Arabic script that substantially improves upon the state-of-the-art. In thefollowing are the further contributions of this work to the field of printed Arabic text
recognition:
1. A novel printed Arabic OCR application to recognise multi-font types,
multi-size and multi-styles Arabic text images has been developed. The
effectiveness of this system was evaluated by comparing the output
produced with ground truth and by comparing it with other Arabic OCR
systems.
2. A comprehensive review of printed Arabic text recognition has been
performed. This review analyzed the challenges and open problems in thefield of printed Arabic OCR. This work resulted in the following
publication:
Alghamdi, M. and Teahan, W., 2018. Printed Arabic Script Recognition: A
Survey. International Journal of Advanced Computer Science andApplications (IJACSA), 9(9).

3. An automated evaluation tool with new objective metrics for the evaluationof Arabic OCR performance has been developed. Also, a standard protocol
for measuring the effectiveness of Arabic OCR systems with acomprehensive automated evaluation of the current Arabic OCR systems
has been provided. This work resulted in the following publications:4

Alghamdi, M.A., Alkhazi, I.S. and Teahan, W.J., 2016. Arabic OCR
evaluation tool. In Computer Science and Information Technology (CSIT),
2016 7th International Conference on (pp. 1-6). IEEE.



Alghamdi, M. and Teahan, W., 2017. Experimental evaluation of Arabic
OCR systems. PSU Research Review, 1(3), pp.229-241.

4. A novel thinning algorithm for Arabic text has been developed andevaluated by comparing it with alternative thinning algorithms. Also, a new
set of performance metrics for the evaluation of thinning algorithm is
proposed. This work resulted in the following publication:
Alghamdi, M.A. and Teahan, W.J., 2017. A new thinning algorithm for
Arabic script. International Journal of Computer Science and Information
Security, 15(1), p.204-211.

5. A new technique based on a cognitive insight used for extracting featuresfrom non-dotted Arabic text images has been developed and evaluated. The
method has been tested on a sample of 100 Arabic words images and has
produced an average edit distance accuracy of 98.07%.
6. A new character segmentation technique based on the features extracted
from Arabic text has been developed and evaluated. The method has beentested on a sample of 100 Arabic words images and has produced a recall of
84.21% and a precision of 77.25%.
7. A novel compression-based method has been applied as a classifier for the
first time to Arabic textual feature recognition and has been evaluated. The
method has produced an average edit distance accuracy of 77.31%.
8. A post-processing technique based on the PPM compression scheme has
been applied to two problems: adding dots to Arabic text and correcting the
OCR output. The post-processing technique improves the edit distanceaccuracy of the printed Arabic OCR system from 77.3% to 86.9% which isa significant improvement.
9. A new methodology for implementing printed Arabic OCR has beendeveloped. This methodology performs the feature extraction stage prior tothe character segmentation stage in order to overcome the challenges of
Arabic character segmentation.

5

1.5 Thesis Outline
The organisation of the thesis is illustrated in Figure 1.2. This thesis is divided into nine
chapters as follows.
Chapter 1, entitled “Introduction”, presents the background and motivation of this workand highlights the aim and objectives of this work along with the research questions.
Also, it reviews the contribution of this work.
Chapter 2, entitled “Literature Review”, reviews the literature related to printed Arabic
text recognition research. It discusses techniques that have been utilized for developing
printed Arabic OCR with emphasis on the issues related to Arabic script. It also
addresses the challenges and open problems in printed Arabic text recognition.
Chapter 3, entitled “Experimental Evaluation of Arabic OCR systems”, introduces anautomated evaluation tool with new objective metrics for the evaluation of Arabic OCR
performance. Also, it describes an experiment to automatically evaluate four wellknown Arabic OCR systems using a set of performance metrics. The evaluation
experiment is conducted on a publicly available printed Arabic dataset comprising 240
text images with a variety of resolution levels, font types, font styles and font sizes.
Chapter 4, entitled “Thinning”, proposes a new thinning algorithm for Arabic script.
The chapter also addresses several objective performance metrics for assessing
statistically the effectiveness of thinning algorithms. An experiment is conducted toevaluate the new thinning algorithm against two well established thinning algorithms
with respect to the proposed objective performance metrics.
Chapter 5, entitled “Feature Extraction”, proposes a new approach based on a cognitive
insight for extracting features from non-dotted Arabic text images. It describes therationale behind using this approach and explains how the feature of Arabic text
images are extracted.
Chapter 6, entitled “Character segmentation”, presents a new character segmentation
technique for segmenting connected Arabic words into characters.
Chapter 7, entitled “PPM Classification”, describes the use of the Prediction by Partial
Matching (PPM) compression based method for textual feature recognition. The
chapter implements the PPM model to recognise isolated Arabic character images andArabic text images.
6Chapter 8, entitled “PPM Post-processing”, introduces a post-processing method basedon a PPM model for correcting Arabic OCR output. It also investigates theeffectiveness of using the PPM based correction method for correcting the Arabic OCR
output.
Chapter 9, entitled “Conclusion and Future Work”, summarises the main conclusionsof this study and provides several directions for future research.

Figure 1.2: Thesis structure

7Chapter 2: Literature Review
2.1 Introduction
OCR is a technique that transforms a printed or handwritten text image into anelectronic format. OCR development is considered a challenging task in the field ofpattern recognition. Many OCR approaches have been proposed for Latin and nonLatin scripts. However, printed Arabic OCR still poses great challenges because of thespecial characteristics of Arabic script (Slimane et al., 2013; Ahmed et al., 2019)
Arabic OCR is highly desirable in various real-world applications, such as digitisinglearning resources to assist visually impaired people, bank cheque processing and mailsorting (Alginahi, 2013; Al-Badr and Mahmoud, 1995). Furthermore, there are many
initiatives for Arabic digital content enrichment (Saad and Ashour, 2010). One of these
initiatives is King Abdullah’s Initiative for Arabic Content. Therefore, a robust andefficient Arabic OCR is required to support this initiative by increasing Arabic content
on the Internet.
Numerous methods have been proposed for recognising printed Arabic script from animage, yet we are unaware of comprehensive surveys of printed Arabic OCR during
the last fifteen years. Two surveys have been conducted on printed Arabic OCR (AlBadr and Mahmoud, 1995; Khorsheed, 2002). However, these reviews do not reflect
the current progress in printed Arabic OCR. Therefore, establishing a guide andbaseline for future directions remains important for Arabic OCR researchers.
This work will establish this guide and baseline for Arabic OCR researchers byproviding a comprehensive literature review of printed Arabic text recognition
research. It reviews techniques that have been utilized for developing printed Arabic
OCR with emphasis on the issues related to Arabic script. It also addresses thechallenges and open problems in printed Arabic text recognition.
Part of this work in this chapter has been published in the following paper:
Alghamdi, M. and Teahan, W., 2018. Printed Arabic Script Recognition: A
Survey. International Journal of Advanced Computer Science andApplications (IJACSA), 9(9).

This chapter is organised as follows. In Section 2.2, Arabic script characteristics andchallenges are discussed. Section 2.3 presents the methodologies of printed Arabic
8

OCR, with subsections that review the five stages of the development of printed Arabic
OCR: preprocessing, segmentation, feature extraction, classification and postprocessing. Section 2.4 discusses performance evaluation issues of printed Arabic
OCR. Section 2.5 concludes with a discussion about challenges and open problems. A
summary is provided in the last section.
2.2 Arabic script characteristics and challenges
There is no doubt that printed Arabic OCR faces a number of challenges and there is
still an intensive need for more research (Al-Helali and Mahmoud, 2017). However,most challenges facing the development of Arabic OCR are due to the characteristics
of Arabic script. Arabic script has some features that distinguish it from otherlanguages. Compared to English, the most obvious feature of Arabic script is that it is
written cursively from right to left in both printed and handwritten. The greatest
challenges are due to the more complex characteristics of Arabic script. In thefollowing section, the characteristics of Arabic script that may complicate recognition
will be discussed:

Shapes and positions

The Arabic alphabet has 28 basic letters (see Table 2.1). However, an Arabic lettermay contain four dissimilar shapes in relation to its location inside a word: whether it
is an isolated letter, an initial letter (in which a letter is inked from the right side, an
ending letter (in which a letter is linked form the left side) or a middle letter (in which
a letter is linked from the right and left sides). Thus, the number of letters to berecognized will increase from 28 letters to 125 letters. Also, Arabic script contains
loop shaped letters.
Overlapping characters and Ligatures

Characters in an Arabic word might be overlapped vertically with or without touchingeach other (see Figure 2.1). In particular, some characters are combined and written as
a ligature such as )‫ (ال‬which is a combination of two letters Lam (‫ )ل‬and Alf (‫)ا‬.
However, ligatures occur in Arabic script depending on the type of fonts being used
(AlSalamah and King, 2018). For instance, in Traditional Arabic font, there are about
220 ligatures whereas Simplified Arabic incorporates about 150 ligatures (ElMahallawy, 2008).
9

Diacritics

Characters in an Arabic word can exist with diacritics or short vowels such as Fat-hah,
Dhammah, Mada’ah, Kasrah and Sukkun, as illustrated in Figure 2.1. These can beplaced either over or below the letters as strokes. In addition, Tanwen is considered asa diacritic which is indicated by double Fat-hah, double Dhammah and double Kasrah.
One more diacritic that Arabic script has is Shaddah which is similar to the number 3
as it is rotated 90° clockwise.

Isolated

InitialMiddleEnd

Isolated

InitialMiddle

End

‫ا‬
‫ب‬
‫ت‬
‫ث‬
‫ج‬
‫ح‬
‫خ‬
‫د‬
‫ذ‬
‫ر‬
‫ز‬
‫س‬
‫ش‬
‫ص‬

‫ا‬
‫بـ‬
‫تـ‬
‫ثـ‬
‫جـ‬
‫حـ‬
‫خـ‬
‫د‬
‫ذ‬
‫ر‬
‫ز‬
‫سـ‬
‫شـ‬
‫صـ‬

‫ـا‬
‫ـبـ‬
‫ـتـ‬
‫ـثـ‬
‫ـجـ‬
‫ـحـ‬
‫ـخـ‬
‫ـد‬
‫ـذ‬
‫ـر‬
‫ـز‬
‫ـسـ‬
‫ـشـ‬
‫ـصـ‬

‫ـا‬
‫ـب‬
‫ـت‬
‫ـث‬
‫ـج‬
‫ـح‬
‫ـخ‬
‫ـد‬
‫ـذ‬
‫ـر‬
‫ـز‬
‫ـس‬
‫ـش‬
‫ـص‬

‫ض‬
‫ط‬
‫ظ‬
‫ع‬
‫غ‬
‫ف‬
‫ق‬
‫ك‬
‫ل‬
‫م‬
‫ن‬
‫ه‬
‫و‬
‫ي‬

‫ضـ‬
‫ط‬
‫ظ‬
‫عـ‬
‫غـ‬
‫فـ‬
‫قـ‬
‫كـ‬
‫لـ‬
‫مـ‬
‫نـ‬
‫هـ‬
‫و‬
‫يـ‬

‫ـضـ‬
‫ـطـ‬
‫ـظـ‬
‫ـعـ‬
‫ـغـ‬
‫ـفـ‬
‫ـقـ‬
‫ـكـ‬
‫ـلـ‬
‫ـمـ‬
‫ـنـ‬
‫ـهـ‬
‫ـو‬
‫ـيـ‬

‫ـض‬
‫ـط‬
‫ـظ‬
‫ـع‬
‫ـغ‬
‫ـف‬
‫ـق‬
‫ـك‬
‫ـل‬
‫ـم‬
‫ـن‬
‫ـه‬
‫ـو‬
‫ـي‬

Table 2.1: Arabic characters with different positions and shapes

10Figure 2.1: Arabic script characteristics

Figure 2.2: Two characters (Ba and Ya) with an identical shape and a different numberof dotsCursive

As mentioned above, Arabic script is a cursive script which means that a word iscomposed of connected characters using a horizontal line called the baseline.
However, six characters (‫ و‬,‫ ز‬,‫ ر‬,‫ ذ‬,‫ د‬,‫ ( ا‬of the Arabic alphabet are not linked withsucceeding letters. This can present a challenge because these characters can divide aword into one or more units as sub-words (see Figure 2.1).
Presence of dots

In old Arabic script, the characters were not originally dotted. However, due to thedifficulty of recognising Arabic characters by non-native Arabic learners, thecharacters of Arabic script have become dotted (Baik, 1992). The Arabic alphabet
relies on number and position of dots in order to differentiate between similar letters(see Figure 2.2). Fifteen characters in the Arabic alphabet have dots. They can beplaced below the character, above it or in the middle. Ten of these characters have one
dot, three have two dots and two have three dots, as shown in Table 2.1.
2.3 General Arabic OCR methodology (model)This section will focus on the methodologies used by printed Arabic OCR systems.
Published approaches and systems for Arabic OCR indicate that the process of11

implementing Arabic OCR consists of five phases: (1) pre-processing; (2) feature
extraction; (3) segmentation; (4) classification and (5) post-processing, see Figure 2.3.

Figure 2.3: General printed Arabic OCR methodology

2.3.1 Preprocessing phase

This is the first phase of OCR methodology which is responsible for enhancing thereadability of the input image. Preprocessing is a combination of algorithms that are
applied to the input image in order to reduce noise and alterations, thus simplifying thesubsequent phases of OCR methodology (Abu-Ain et al., 2018; Al-Badr andMahmoud, 1995). There are various factors that affect the quality of the input image.
Al-Badr and Mahmoud (1995) list the history of image, the printing process, the kindof font, the quality of paper, the condition of the image and the image acquisition as
the vital factors that influence the input image quality.
Khorsheed and Clocksin (2000) emphasize that the downstream OCR accuracy relieson the quality of the input image. Furthermore, Al-Badr (1995) states that OCR
systems, which report high recognition accuracy on some input images, will reportless recognition accuracy on input images that are poor in quality. Thus, thepreprocessing phase is a critical stage in OCR development that simplifies the data forthe subsequent phases to operate accurately. Generally, several preprocessing
operations are employed on the input image: binarization, layout analysis, thinning,smoothing and filtering, size and slant normalization, slant detection, skew detection
and baseline detection. The selection of these operations to be applied in the
preprocessing relies upon the conditions of the input image, such as the amount ofnoise and skew in the input image (Kannan and Subramanian, 2015). In the following
section, the preprocessing techniques which are applied in Arabic OCR will beclarified.
12

Binarisation

For character recognition, the binarisation process involves converting an input grayscale image into a binary image, in which a pixel has only two values 0 and 1. The
binary image has the critical information, such as the shape of characters. It has beenfound that increasing processing speed and reducing storage capacity are the key
benefits of binarisation technique (El-Mahallawy, 2008; Lawgali, 2015). Al-Badr andHaralick (1998) suggest selecting the most appropriate method for binarisation might
separate connected objects or joining isolated objects. A number of studies haveconfirmed the efficiency of computing the histogram of the gray scale of an image andthen detecting a cut-off point as the binarisation method (Al-Badr and Haralick, 1998;
Jumari and Ali, 2012). However, some researchers work on recognition without
applying binarisation methods, such as AbdelRaouf (2012) and Pavlidis (1993).
Size normalization

Since Arabic characters differ in size, as described earlier, size normalization iscommonly applied to characters or words by scaling the characters or the words to an
adjusted size. This process is crucial for the recognition or classification phase, sincesome recognition methods are sensitive to dissimilarity in size and position, such as
template matching and correlation approaches (Al-Badr and Haralick, 1998).
AbdelRaouf (2012) classified normalization methods into two approaches: momentbased normalization; and nonlinear normalization. It is argued that normally acharacter is normalized to a standard size for classification (Cheriet et al., 2007).
However, in terms of word normalization, applying normalization to a word instead ofa character will result in losing critical information (Cheriet et al., 2007; Cho et al.,1995).
De-noising

Noise may be presented during the acquisition process via scanners which results indistortions and variations in the input text image. Besides this, very small items in the
text image can be reflected as noise (Lawgali, 2015), which are byproducts of image
scanning or binarisation and which are not parts of the text. Such noise may have amajor impact on the performance of OCR systems (Drira and Lebourgeois, 2012).

13

Noise removal is an operation for enhancing the visual quality of the input image (Shiet al., 2012).
As a solution, several techniques have been introduced that are considered as noise
removal methods (Buades et al., 2005). These methods like dilation algorithms, which
are applied to broken letters, and erosion algorithms, which are applied to text images
with touching letters (AbdelRaouf, 2012), are conditioning processes in terms of OCR
development (Al-Badr and Mahmoud, 1995; Gonzalez and Woods, 2002). In addition,
the median filter approach is commonly used in both printed text images andhandwritten text images. For example, Al-ani et al. (2014) apply this approach forremoving noise in printed Arabic text images. Another example of a study that applies
a median filter algorithm in handwritten Arabic text images is a study by Al-Shatnawi
et al. (2011). Ahmed et al. (2012) applied a morphological noise removal method for
Arabic printed OCR proposed by Mahmoud (1994). However, Ahmed et al. (2012)
discovered that letter holes could be filled while applying this method, with lower
thresholds, to Arabic text images.
Figure 2.4. An example of Arabic text skew

In fact, the review suffers from the fact that some printed Arabic OCR studies applied
noise removal algorithms without providing information of the applied algorithm, forinstance, in Taha et al. (2012). Such approaches, however, should be selected carefully
when considering OCR systems. That is, because of the similarity between Arabic
letters, any alteration of a letter might change it to another letter. Thus, a perfect noise
removal method is the method that is able to eliminate noise while preserving the shapeof the character (Drira and Lebourgeois, 2012).
Skew detection and correction

Initially, a text image has zero rotation, yet when physically scanning the image
manually, rotation of images up to 20ᵒ might occur (Khorsheed, 2002). This rotation
is called skew which results in non-zero skew text images (see Figure 2.4). The skew
can lead to incorrect recognition and baseline detection (Al-Shatnawi and Omar,
14

2009). According to Abuhaiba (2003), it is impossible to segment a text if the text is
rotated. As a result, detecting and correcting the skew is critical to OCR applications
that rely on segmentation approaches to recognize characters.
The process of estimating the skew angle is known as skew detection, whereas theprocess of rotating the image with the purpose of correcting the skew is called skew
correction. A wide variety of skew detection and correction methods have been
proposed. Sun and Si (1997) group these methods into five groups: projection profile,
Hough transform, Fourier transform, nearest neighbor clustering and correlation. The
Hough transform is the standard approach for detecting the skew (Parker, 2011). A
method based on the projection profile was introduced by Baird (1995). Hull (1998)
has provided a comprehensive review of twenty–five skew detection and correction
approaches. The author concludes that further work on more sophisticated methods isstill required. The Radon transform method has shown its efficiency for skew
correction (Dong et al., 2005). Some methods are designed for specific applications
and image type. For example, a new method has emerged for Arabic text images from
Al-Shatnawi and Omar (2009). Alginahi (2010) concludes that selecting a skew
detection and correction method relies on the image type.
Baseline detection

As described in the previous section, Arabic characters are joined through a horizontal
line called the baseline (see Figure 2.5). Graphically, the baseline can be described as
the line which has the maximal amount of black pixels (Shafait et al., 2006). This line
contains critical information about the text, such as text orientation and position ofconnection points between Arabic letters (Al-Badr and Mahmoud, 1995). Thus,
detecting the baseline is beneficial for many OCR stages, for instance, skew
normalization (Omar et al., 2000), segmentation (Amin, 1998; Arica and YarmanVural, 2002) and structural features extraction such as the character’s dots (El-Hajj etal., 2005).
It has been reported that most Arabic OCR has applied baseline detection methods asa preprocessing step (Al-Shatnawi et al., 2011) .The baseline detection techniques for
Arabic script have been classified into four groups by Al-Shatnawi and Omar (2008);
namely, horizontal projection methods, the word skeleton method, contour tracing andprinciple component analysis. Among these, the horizontal projection technique is15

widely implemented for determining the baseline in Arabic OCR, such as in Pechwitz
and Margner (2002) and Al-Badr and Mahmoud (1995). Several studies implement a
horizontal projection approach in OCR systems for detecting the baseline, such as inZidouri et al. (2003), El-Hajj et al. (2005), Ahmed et al. (2012) and Al-rashaideh,(2006). It has been emphasized that the horizontal projection method is simple andefficient for Arabic printed text (Pechwitz and Margner, 2002; Zeki, 2005). However,this method is applicable only for noise-free images, as it fails for unclean images(Bukhari et al., 2011).

Figure 2.5: Baseline detection of a printed Arabic text image

Another baseline detection approach is the x-y cut proposed by Nagy et al. (1992)
which is based on a horizontal projection method. This method works well for Arabic
noisy images, though it fails in the presence of large amounts of noise and skew
(Bukhari et al., 2011). Consequently, Bukhari et al. (2011) proposed using a ridgebased text line detecting approach for Arabic text. The former method’s efficiency has
been tested and recommended for different types of Arabic text images, since it was
found to achieve above 96% text line detection accuracy (Bukhari et al., 2011).
Al-Shatnawi and Omar (2008) summarize the state-of-the-art of baseline detection
methods in Arabic script. In summary, for printed Arabic text, the standard horizontal
projection method is sufficient for detecting the baseline, since the baseline in printed
text is straight whereas for handwriting, the baseline is not straight, thus moresophisticated approaches should be considered (Parvez and Mahmoud, 2013).
Thinning and skeletonization

Producing skeletons is a critical pre-processing operation for OCR in which extracting
features from the skeleton of a character is essential (Parker, 2011). The method for
producing the skeleton of a pattern image is called thinning. Thinning“skeletonization” can be defined as the process of unpeeling as many pixels as possible
without distorting the general shape of the character (Cheriet et al., 2007). In otherwords, it involves operations that can be implemented in order to produce the skeleton16

of object images. Thinning techniques are classified into iterative approaches and noniterative approaches (Abu-Ain et al., 2013). The former can be either sequential
methods, which perform by peeling the counter pixels individually, or parallel methods
which perform simultaneously on all the counter pixels until obtaining a skeleton(Saeed et al., 2010). The latter utilize other techniques, such as distance transforms, toproduce a skeleton without examining all pixels (Saeed et al., 2010).
In general, thinning is usually applied in OCR systems as a method for reducing theamount of data of a pattern that needs to be considered for next processing stage,
thereby saving storage space for the structural information of the pattern (Naccacheand Shinghal, 1984; Al-Shatnawi et al., 2011). Furthermore, thinning algorithms havecontributed to facilitate feature extraction of a pattern which is the core task in OCR
to identify the pattern from another, since the relevant information of a pattern is not
related to the thickness of the pattern (Devi, 2006; Alginahi, 2010). Therefore, it isclaimed that the effectiveness of an OCR performance is heavily reliant on how
effective the thinning algorithm is (Ali, 2012). The authors in (Cheriet et al., 2007) and(Chatbri and Kameyama, 2014) agree that the main features of a desirable thinningalgorithm are: ensuring the peeling is as thin as possible, connected and preserving the
topology of a pattern.
A number of thinning algorithms have been proposed, such as in (Guo and Hall, 1992),(Hilditch, 1983), (Wang and Zhang, 1989); for a comprehensive survey refer to (Lamand Lee, 1992). However, these algorithms have not been proposed specifically for
Arabic script; rather they are proposed for general purposes. Additionally, direct
adoption of such thinning algorithms, which are developed for other languages, may
be not applicable to Arabic because of its characteristics (Al-shatnawi and Omar, 2014;
Cowell and Hussain, 2001; Hosseini, 1997).
According to Cowell and Hussain (2001), various problems have arisen when applying
thinning algorithms to Arabic characters. One of the main obstacles with applying
thinning algorithms to Arabic text is reducing the number of dots for similar characters,
where the number of dots can differentiate between them (Al-Badr and Mahmoud,
1995; Al-shatnawi and Omar, 2014). It is believed that any deletion of character dots
will result in misrepresenting these characters (Hosseini, 1997). Therefore, someresearchers extract dots of Arabic characters before applying thinning algorithms, inorder to overcome this problem (Melhi et al., 2001; Al-Badr and Haralick, 1998).
17

Another problem of thinning algorithms when considering Arabic script concernspreserving the connectedness of Arabic text. Some thinning approaches may fail inpreserving the Arabic text connectivity which will lead to challenges in text
recognition (Al-shatnawi and Omar, 2014). Owing to these reasons, it is claimed thatthinning is responsible for many recognition errors in OCR systems (Al-Badr andMahmoud, 1995; Al-shatnawi and Omar, 2014). Therefore, thinning algorithms must
be capable of both preserving dots and the connectedness of Arabic script.
As stated, there has been relatively few publications on developing thinning algorithms
for Arabic (Ali, 2012; A. M. Al-Shatnawi et al., 2011; Al-ani et al., 2014). For instance,(Cowell and Hussain, 2001; Altuwaijri and Bayoumi, 1995) introduce thinningalgorithms for Arabic script. However, the proposed algorithms can only deal withisolated Arabic characters. Furthermore, one study by Ali (Ali, 2012) provides athinning algorithm for Arabic handwritten script. Unfortunately, none of previous
studies have considered the challenge of Arabic script discussed above, such as dots
and connectivity preservation, when developing the thinning algorithm.

2.3.2 Segmentation phase

After the preprocessing phase, an enhanced text image in the sense of low noise andvariation, and a necessary amount of character information (Al-Badr and Mahmoud,1995), has been produced. During the segmentation phase, the text image is segmented
into small components, with a page being segmented into lines, a line into words anda word into letters (Lorigo and Govindaraju, 2006; Naz et al., 2014; Plamondon and
Srihari, 2000). Segmentation is a crucial step in Arabic OCR system development
because of the fact that it plays a vital role in ensuring the success of the subsequentfeature extraction and classification stages (Alginahi, 2013; Zeki, 2005; Stolyarenko
and Dershowitz, 2011). However, Zeki (2005) stresses that misrecognition can arise
by applying a poor segmentation method. As a result, this stage will have a critical
impact on the recognition rate of the text (El-Mahallawy, 2008).
As explained previously, one of the main challenges facing Arabic OCR development
is the cursiveness of Arabic script. Segmentation of Arabic text thus can be moredifficult and time consuming for the development of Arabic OCR systems (Alginahi,2013). Correspondingly, segmentation has been considered as the main contribution
18

for increasing the recognition error rate in Arabic OCR systems (Amara et al., 2016;
Nawaz et al., 2003; Zeki, 2005).
Generally, segmenting a text image can be graded into two types: externalsegmentation; and internal segmentation (Arica and Yarman-Vural, 2001). While theformer type deals with the isolation of different writing objects such as, paragraphs,
sentences and words, the latter deals with the isolation of characters (Alkhateeb, 2010;
Arica and Yarman-Vural, 2001).
2.3.2.1 External segmentation

External segmentation refers to the document layout analysis, in particular page
decomposition. Document layout analysis is accomplished in order to identify thephysical structure of a page (O’Gorman, 1993). As far as offline OCR development
is concerned, page analysis is a basic step which segments the image into its different
logical parts with the identical type of information, such as graphs, text and tables.
Page layout analysis is performed in two approaches: structural analysis by which a
page is decomposed into blocks of the page elements, such as paragraphs and words;
and functional analysis by which a page is decomposed into functional elements suchas title and abstract (Alkhateeb, 2010; Arica and Yarman-Vural, 2002; O’Gorman,
1993).
With respect to Arabic document processing, page decomposition refers to theisolation of text lines of a texture region and the segmentation of words and sub-words(El-Mahallawy, 2008; Khorsheed, 2002; Srihari and Ball, 2012), since it is restricted
to text images (Khorsheed, 2002). According to Khorsheed (2002), Amin and Masini(1986) and Mari (1989), applying a fixed threshold to Arabic text documents todetermine text lines is the standard method. However, this method fails with a skewed
text image (Amin, 1998).
Methods based on histogram projection are considered as conventional approaches for
isolating lines and words in Arabic text documents (Amin and Masini, 1986; Ymin
and Aoki, 1996). Several studies have relied on horizontal projection techniques forsegmenting Arabic text images into lines, such as Cheung et al. (2001), Khorsheed(2007), Amin and Masini (1986), Al-Yousefi and Udpa (1992), Abuhaiba et al. (1994),
Taha et al. (2012) and Supriana and Nasution (2013). It is recommended horizontal
projection be applied for text images because of its advantages in reducing
19

computational load and its simplicity of implementation (Cheung et al., 2001).
Moreover, horizontal projection is an appropriate method for locating text lines in
Arabic printed text, since the text lines in printed text are straight (Parvez and
Mahmoud, 2013).
For line segmentation, researchers in Arabic OCR determine words in a line of text byinspecting the vertical projection (Sarfraz et al., 2003; Taha et al., 2012). (See Figure2.6). This method depends on the estimation of the minimum space between words.
However, it was pointed out in the Arabic script characteristics section above that someArabic characters are not linked with succeeding letters, thus this results in a word
having with one or more connected components (sub-words), as shown in Figure 2.6.
To overcome this issue, methods based on vertical projection consider that the widthof spaces between sub words is smaller than the width of the spaces between words(Sarfraz et al., 2003).

Figure 2.6: An example of line segmentation

Generally, it is relatively easy to segment a text line into words in printed text images,
compared to handwritten text images which involve overlapping and touching
characters by using vertical projection histogram profiles (Alginahi, 2010; Lawgali,
2015; Al-Shatnawi et al., 2011) . However, some Arabic fonts contain characters thatvertically overlap, such as the Traditional font type. Thus, Arabic script even in printed
form can contain touching and overlapping characters, so algorithms that have been
designed to overcome this challenge for handwritten script may be utilized for printed
Arabic. For example, AlKhateeb et al. (2009) have developed a method based on theconnected components that analyses the distance between connected components inorder to segment handwritten words.
2.3.2.2 Internal segmentation

Internal segmentation deals with segmenting a word into characters. When reviewing
segmentation methods in the literature, a major complication arises concerning theclassification of word segmentation approaches. For instance, Khorsheed (2002)
classifies Arabic OCR systems based on word segmentation into ‘segmentation based
20systems’, which is based on analytical techniques where a word is segmented into
characters, and ‘segmentation–free systems’, which is based on recognizing a word asa unit without segmentation. Amin (1998) and Xiu et al. (2006) discuss word
segmentation in terms of implicit and explicit segmentation. Others classify word
segmentation in terms of techniques which have been applied to segmenting a word,such as Lawgali (2015), Zeki et al. (2011) and Alginahi (2013). Al-Shatnawi et al.
(2011) organize segmentation methods for Arabic script into holistic approaches andanalytical approaches.
Mostly, Arabic OCR systems have been developed by two main paradigms: holistic
approaches (segmentation–free) which require a large lexicon of Arabic words, andanalytical approaches (segmentation based) where a word is segmented into units andeach unit is recognized separately.
a- Holistic approach
Segmentation-free or holistic Arabic OCR systems perform the recognition on theentire word as a unit without segmenting the word or recognizing characters separately(Al-Badr and Mahmoud, 1995). Several studies have investigated the holistic approachfor printed Arabic script OCR such as Erlandson et al. (1996), Al-Badr and Haralick(1998) and Khorsheed and Clocksin (2000). OCR systems based on a holistic approachrequire tracing the feature of the entire word and dealing with words instead ofcharacters. As a result, this approach is restricted to recognizing a word against alexicon (Al-Badr and Mahmoud, 1995; Jain et al., 2018). Moreover, this approach has
the challenge of how to deal with the large lexicon size of Arabic words (Nashwan etal., 2017). It is claimed that systems based on this type of segmentation are not usefulfor general text recognition. Choudhary (2014) suggests this approach for systems inwhich a lexicon is statically defined, such as bank cheque recognition where
vocabulary is limited.
b- Analytical approach
For the analytical or segmentation-based approach, Arabic OCR systems segment
words into smaller units like characters (see Figure 2.7). In the typical Arabic OCR
system, the analytical approach is divided into two approaches: explicit segmentationand implicit segmentation.

21

1. Explicit segmentation
The explicit segmentation approach, which is also called dissection segmentation,
attempts to segment a word into smaller units. These units could be characters, strokes
or loops. Naz et al. (2015) argue that there are two classes of explicit segmentation,
which are: direct segmentation and indirect segmentation. In the former, a word isdirectly segmented into characters exploiting a set of heuristics, while in the latter, aword is divided into smaller segments which can be characters or marks that oversegmented characters, such as strokes.

Figure 2.7: Segmenting Arabic words into their characters

Projection analysis is considered as one of the earliest applied dissection methods on
Arabic character segmentation (Amin and Masini, 1986; Ymin and Aoki, 1996; Zeki,2005). The projection method of the text image aims to reduce 2D information into 1D
in order to simplify the character segmentation process. A method based on a
modulated histogram of the image has been proposed by Najoua and Noureddine(1995). However, this method has been tested on specific Arabic fonts which do notcontain overlapping and ligatures. Consequently, this method would not be appropriate
for Arabic fonts that have ligatures, such as traditional Arabic font (Alginahi, 2013;
Amara et al., 2016).
Another histogram projection method is presented for printed Farsi word segmentation
by Parhami and Taraghi (1981) which is also applicable to Arabic script, as Arabic
script is similar to Farsi script (Alginahi, 2013). However, this method is fontdependent and ineffective in segmenting small font sizes. Although many of the othertechniques based on projection analysis have been devolved for Arabic script such as
by Zheng et al. (2004), Amara et al. (2016) and Lorigo and Govindaraju (2005), it
seems that no projection based segmentation algorithm is accurate in segmenting
Arabic text (Parvez and Mahmoud, 2013).
Instead of applying projection analysis methods, contour–based algorithms, which areused for dissection segmentation that rely on the skeleton or contour of Arabic words,
are used to simplify the Arabic word segmentation such as in Xiu et al. (2006). Other
22

methods rely on white space and pitch finding techniques for segmenting Arabic words(Al-Yousefi and Udpa, 1992; Zeki, 2005). However, a major criticism of the explicit
approach is that it is expensive because of the requirement of finding the optimum
word from the arrangement of segmented units (Naz et al., 2015). Cheung et al. (2001)
conclude that an accurate segmentation may not be acquired by relying on dissection
segmentation approaches.
2. Implicit segmentation
In OCR systems based on implicit segmentation, the segmentation phase andrecognition phase are performed simultaneously (Alginahi, 2013). In other words, aword is segmented into characters while being recognized without segmentation inadvance (Zeki, 2005). Straight segmentation and recognition based segmentation are
also referred to as implicit segmentation (Zeki, 2005). This segmentation approachsearches the text image for components that match predefined classes. The principleof implicit segmentation is to utilize a sliding widow to segment the word image intoframes of fixed width on which classification relies to make a decision (Koteswara
Rao and Negi, 2016). Owing to challenges in segmentation of cursive scripts such as
Arabic, researchers use the implicit segmentation approach in order to overcome theproblems of word segmentation (Choudhary, 2014). In principle, by applying this typeof segmentation, there is no need for a specific dissection algorithm for Arabic script
segmentation and the accuracy performance relates to the classification performance(Zeki et al., 2011). Thus, some researchers implement techniques based on implicit
segmentation in order to improve recognition accuracy of Arabic OCR, such as
Cheung et al. (2001), Al-Badr and Haralick (1995) and Chen and DeCurtins (1993).

2.3.3 Feature extraction phase

Once the text image is segmented into isolated regions (such as character, part ofcharacter), the next step is feature extraction which is the process of obtaining
distinguishing attributes of the segmented character to be utilized by the next phasewhich is classification (Srinivas et al., 2008). Feature extraction is the most significant
level that heavily influences overall OCR performance (Al-Shatnawi et al., 2011;
Lawgali, 2015; Naz et al., 2014). The feature extraction stage is correlated with other
OCR stages, such as preprocessing and classification stage. In other words, Due Trier23

(1996) points out that the selection of feature extraction methods depends on the outputof the preprocessing stage. For instance, some techniques for feature extraction workon skeletons, whereas others work on grayscale images. Moreover, the set of features
extracted must match the specification of the selected classifier (Al-Badr andMahmoud, 1995).
In terms of OCR performance, feature extraction plays a critical role in achieving highaccuracy performance (Lawgali, 2015), since the feature extraction stage contributes
to the success of the classification step (Naz et al., 2014). However, selection of feature
types is a major issue in OCR development (Moubtahij et al., 2014). Researchers
recommend that the feature extraction methods should be independent of scalable fontcharacteristics such as font styles, font types, font sizes and should be able to describe
and distinguish different patterns effectively (Moubtahij et al., 2014; Sharma et al.,2012). In other words, Al-Muhtaseb and Qahwaji (2011) emphasize that the key
purpose of selecting good features is to maximize the effectiveness and the efficiencyof the OCR system minimizing the complexity and processing time simultaneously.
Among OCR system development, researchers propose various types of features. Suchfeatures can be categorized into three groups: structural features; statistical features;and global transformation features (Khorsheed, 2002). In the following, these features
will be discussed in the context of recognizing Arabic script.
2.3.3.1 Structural features

Structural features illustrate a text image in terms of its topological and geometricalcharacteristics by using its local and global properties (Al-Badr and Mahmoud, 1995;
Moubtahij et al., 2014). In case of Arabic script, lines, dots, loops, holes, strokes andzigzags are some structural features (Moubtahij et al., 2014; Abd et al., 2012; Saabni,
2015; Elgammal and Ismail, 2001; Khorsheed and Clocksin, 1999; Ahmad et al.,2013). Considering Arabic script characteristics, some characters have common
primary shapes and they can only be differentiated by the number and location of theirdots. Thus, Lorigo and Govindaraju (2006) claim that structural features have beencommonly used for Arabic script in order to capture the dot information of characters
explicitly.
On the other hand, Ghosh et al. (2010) argue that structural feature methods are notcapable of discriminating between characters having similar shapes. Similarly, a study24

by Moubtahij et al. (2014) reports that relying on the structural features of Arabic script
may result in misrecognition, owing to the small difference between Arabic letters.
Khorsheed (2002) comments that extracting structural features of Arabic characters isa challenging task. Furthermore, it is claimed that Arabic OCR systems using structuralfeature methods suffer from exhaustive processing time (Almohri et al., 2007).
Likewise, various studies have reported that another complication of applying
structural features is that it involves expensive preprocessing techniques, such as
skeletonization which may result in character shape distortion and loss of structuralfeature data (Naz et al., 2014; Lorigo and Govindaraju, 2006; Hossain, 2012).
Therefore, research on Arabic OCR has been carried out on other feature extraction
approaches, as will be discussed below, that are effective in reducing process time andimproving performance accuracy (Almohri et al., 2007).
2.3.3.2 Statistical features

Statistical features are derived from statistical representation of patterns which provide
a measurable event of interested patterns. Researchers in Arabic OCR systems adopt
different approaches to produce statistical features. Some examples of the approaches,
which have been applied for representing Arabic characters, are zoning, moments,characteristic loci, histograms and crossing (Moubtahij et al., 2014; Khorsheed, 2002;
Al-Badr and Mahmoud, 1995; A. M. Al-Shatnawi et al., 2011).
The zoning method divides the character image into several overlapping and nonoverlapping regions. Then, the density of each region pixel is analysesd and used as afeature (Moubtahij et al., 2014; Kumar and Bhatia, 2014).
According to Ahmed et al. (2012), the moment method is a common statistical featureapproach that has been applied in patter recognition applications. Moments, including
Legendre moments, Zernike moments, central moments, pseudo-Zernike moments andHu moments, extract geometric features in an image, such as, the shape area of apattern and the center of the mass (AbdelRaouf, 2012; Aboaisha et al., 2012; Kef etal., 2012). Several studies in printed Arabic script, such as, Abd and Paschos (2007),
Oujaoura et al. (2012), Shaaban (2008) and Elrube et al. (2010), have applied moment
invariants as a feature vector.
In short, it is claimed that statistical features for pattern representation are easy to
extract (Moubtahij et al., 2014; Al-Badr and Mahmoud, 1995). Moreover, such25

features can be effective in recognition systems and providing high speed and low
complexity implementation (Naz et al., 2014; Pati and Ramakrishnan, 2005).
However, special attention to the prepossessing techniques should be given, sincemisrecognition may accrue due to poor prepossessing techniques (Khorsheed, 2002).
Nevertheless, the fundamental issue is to determine a set of statistical features, which
need to be the most representative data of a pattern, maximizing the performanceaccuracy and minimizing the processing time simultaneously.
As a result, researchers call for investigating other statistical features which maximize
the performance accuracy and minimize the processing time (Al-Badr and Mahmoud,
1995; Arica and Yarman-Vural, 2001).
2.3.3.4 Global transformation features

The global transformation method is applied to convert a skeleton or contour of apattern by a linear transform into a form that reflects the most relevant features of thetransformed

pattern(Aricaand

Yarman-Vural,2001).

Numerous

globaltransformation methods have been used in developing Arabic OCR systems. An
example of such methods is the Fourier descriptor which represents the characteristicof a pattern in a frequency domain (Zhang and Lu, 2001). The Fourier descriptor has
been applied to Arabic script, such as in Khorsheed and Clocksin (2000) and Mahmoud(1994). Another method is the Hough transform which detects lines in binary images
and then defines the parameters of the lines (Cheriet et al., 2007). Amor and Amara(2006) and Touj et al. (2005) utilized the Hough transform for extracting features from
Arabic script. Also, some other global transformation methods that have been applied
for Arabic OCR for feature extraction are the direction codes method such as
Freeman’s chain code in Taha et al. (2012), Wavelets in Amor and Amara (2012) andWalsh transformation in Oujaoura et al. (2012).
Overall, it is claimed that global transformation feature techniques have several
advantages over structural and statistical approaches. For example, they are applicablefor new fonts and easily implemented. Another advantage is that they are robust to
noise and variation. However, they might require the implementation of other featuresin order to obtain high accuracy performance.
In conclusion, the feature extraction stage plays a critical role in Arabic OCR
development in which distinguishing attributes are extracted and it is clear that each26

Arabic OCR developer needs to apply different feature extraction approaches. Still,good features are required, which assist in distinguishing a character from othercharacters and maximize the accuracy performance simultaneously. Furthermore,these features must be selected specifically for a selected classifier. Some researchers
apply different feature extraction methods in combination. However, this may cause
extra complications for the implementation (Khorsheed and Clocksin, 2000).

2.3.4 Classification phase

The classification phase has the responsibility for assigning a pattern into a preclassified class based on the features of the pattern which have been extracted in theprevious phase (Cheriet et al., 2007). The pre-classified classes can be words, subwords, characters or strokes, based on the OCR approach used (Al-Helali and
Mahmoud, 2017). Several different classification approaches have been used for many
applications, such as text classification, speech recognition and text recognition.
Different classifiers have been used for printed Arabic text recognition, such as Hidden
Markov Models (HMM), Support Vector Machines (SVM), K-nearest neighbour and
Neural Networks (NNs).
SVM, which is a binary classifier, has been used in the implementation of printed
Arabic OCR systems (Abd and Paschos, 2007; Abd et al., 2012; and Mehran et al.,2005). (For a comprehensive review of applying SVM to Arabic OCR, refer to Amara
et al. (2014)). However, classifiers based on SVM are mostly applied to a small set ofdata due to the high complexity of training and processing time (Shafii, 2014; Aroraet al., 2010). Another classification technique that has been applied to printed Arabic
OCR are HMM based techniques. HMMs are statistical models that are considered as
being one of the most efficient for recognition applications especially for speech
recognition (AbdelRaouf, 2012). Therefore, researchers in OCR have implemented
HMMs for OCR in order to obtain high performance OCR systems, such as in
Khorsheed (2007), Khorsheed (2015), Awaida and Khorsheed (2012), Slimane et al.
(2013), Shaker (2018), Rahal et al. (2018) and Al-Muhtaseb et al. (2008).
Neural Networks (NNs) based methods have been successfully applied in many NLP
applications, such as text recognition (Al-Ayyoub et al., 2018). NNs refer to the nonlinear system that may be constructed according to a specific network topology
27

(Khorsheed, 2002). There are different architectures of NNs which consist of an input
layer, an output layer and a single or multiple hidden layers (Hamza, 2008). According
to Alginahi (2004), NNs based methods can successfully improve computation timesince they consist of parallel processing consisting of several connections of the sameneural processes. Moreover, NNs have the capability to adhere to data changes as they
are adaptive (Alginahi, 2013). Extraction features from raw images can be done
automatically by using NN based methods (Sawy et al., 2017). However, NNs requirelarge training data (Nashwan et al., 2017).
Several NN methods, such as Deep Neural Networks (DNNs), Recurrent Neural
Networks (RNNs) and Convolutional Neural Networks (CNNs), have been used asclassifiers for Arabic text recognition and resulted in achieving promising accuracies.
Owing to the challenge of Arabic segmentation, researchers developed freesegmentation Arabic OCR systems that employ NN based methods (Nashwan et al.,2017). NN based methods such as RNNs have the ability to recognise unsegmented
characters as they work on the sequence of characters (Younis and Alkhateeb, 2017).
For example, Radwan et al. (2018) proposed an OCR system for Arabic text using
multichannel neural networks in order to overcome the challenge of character
segmentation of Arabic text. They implemented three neural networks. In the first
network, the font pitch of an Arabic word is predicted. In the second network, theArabic word is segmented into its characters. Then, the segmented characters are fed
as input to a CNN by which salient features are automatically extracted. The system
was evaluated on a word-level dataset and achieved an accuracy rate of 94.3% for an
Arabic transparent font of 18 font pitch.
Ko et al. (2018) proposed an OCR system for recognising printed Arabic text using a
deep-learning approach. They used the multi-dimensional bi-direction long short-term
memory (MD-LSTM) with the use of connectionist temporal classification. The
system was trained on one-million Arabic text line images. The system achieved an
accuracy rate of 99.9%. Similarly, Rashid et al. (2013) introduced a printed Arabic
OCR system based on the MD-LSTM approach. The system achieved an accuracy rateof 99.1% on a word-level dataset. In addition, multiple classifiers has been utilized inorder to improve the accuracy of classification; for review see (Rahman and Fairhurst,
2003).

28

There are a number of studies that compare the performance of different classifiers.
For instance, Amara, Ghedira, Zidi, & Zidi (2015) conduct a performance evaluation
experiment on multi-class support vector machines using an Arabic character dataset.
In addition, in (Pal et al., 2009), performance of different classifiers have been
evaluated on Devanagari characters. However, the performance of classification
methods on text recognition systems are affected by various factors, such as the preprocessing method, feature extraction techniques and training and testing datasets (Liuand Fujisawa, 2008). Therefore, it is challenging to assess the performance of aclassifier based on reported performance accuracies in different studies, since thestudies do not use standard pre-processing methods, feature extraction techniques anddatasets.
Interestingly, compression based methods (models) for classification have beensuccessfully applied in different text classification applications (Alkhazi et al., 2017).
For instance, model-based text classification using the PPM compression method,which will be discussed in the next sub-section, has been considered for a number ofdifferent classification applications. The PPM model has been found to be competitivein different classification tasks (Teahan, 2018). For example, Teahan & Harper (2003)
use PPM models for topic classification and report results that PPM outperforms otherclassification methods, such as SVM and Naïve Bayes classifiers. In addition, the PPM
based compression models have been used accurately for gender classification(Altamimi and Teahan, 2017), emotion classification (Almahdawi and Teahan, 2017),
and text classification (Teahan, 2018; Alkhazi and Teahan, 2017). Although manystudies consider the use of compression-based methods as classifiers, no prior study
exists on the use of compression-based models as a classifier in Arabic text
recognition. Although it has been shown in the literature above that Arabic OCR
systems that applied NNs produced competitive results, they require a large amount oftraining data. However, the compression based method used in this thesis can be used
as a classifier with comparatively smaller training data (as described in Chapter 7).
2.3.4.1 Prediction by Partial Matching (PPM)

PPM is an online adaptive text compression system that foretells the following
character or symbol by using the previous context with given fixed length. Models that
set their prediction probabilities on a few preceding characters are called order n29finite-context models, where n indicates the number of preceding characters used. The
model’s order represents the maximum length of context used to predict the next
character. To predict upcoming characters, PPM uses a set of fixed order context
models with different values of n.
For each model, a record is kept of the frequency counts all symbols that have followed
every subsequence observed in the input from 1 to length n with the number of times
that each has occurred. Prediction probabilities are estimated by using these frequency
counts. The probabilities associated with each symbol that has followed the precedingn symbols in the past are used to predict the forthcoming symbol. Therefore, a single
probability distribution is obtained from each model.
PPM combines these distributions into a single model and arithmetic coding is used
for encoding the symbol according to its associated probability. The combination ofdifferent probability distributions into one model is achieved through the insertion of
the escape symbol. PPM starts with the model’s maximum order first to encode theforthcoming symbol (Teahan et al., 2000). However, if a specific model does notcontain the input symbol, which means that the input symbol has not been seen
previously, an escape symbol is inserted at the transition from the current order modelto the lower order model (a model of order n -1). That is, if the model does not containthe symbol, then the encoder will back off to a default order of -1 (Teahan et al.,2000).This process of escaping will be repeated until the model finds that symbol or
prediction. If necessary, when completely unseen symbol is encountered, the encoder
will back off to the lowest order context of -1 in which all symbols are encoded with1

a probability of |𝐴|, where A is the size of the alphabet that is used.

PPM uses a Markov-based character n-gram procedure which applies a back-off
mechanism alike to that suggested by Katz (Katz, 1987). Nevertheless, PPM refers tothe backing-off as “escaping” and it was developed before Katz’s proposedmechanism. It was first proposed by Cleary and Witten (Cleary, John and Witten,
1984) in 1984 when they developed the character-based PPM variants, PPMA and
PPMB. Then came Moffat and Howard, in 1990 and 1993, who introduced two further
variants of PPM, PPMC and PPMD (Wu, 2007). The main distinction among thesevariants of PPM, is the estimation of the escape probability that the smoothing30

mechanism requires for backing off to a reduced model’s order. Experiments forcharacter streams have shown that PPMD usually delivers better compression results
when compared to other variants of PPM (Khmelev and Teahan, 2003).
The following equation is used to determine the probability p of the following
character φ using PPMD (Teahan, 2000):𝑝(𝜑) =

2𝑐𝑑 (𝜑)−1

(2.1)

2𝑇𝑑

where the coding order currently used is indicated by d, the number of times where
the current context has happened or occurred in total is represented by 𝑇𝑑 and thenumber of times that the context has followed by the symbol φ is represented by 𝑐𝑑(φ). The estimate of the escape probability e by PPMD is as follows:𝑡𝑒 = 2𝑇𝑑(2.2)

𝑑where 𝑡𝑑 represents the number of types of unique symbols that occur following thecurrent context.
For example, if a specific context has occurred three times before, with three charactersa, b and c following it once, according to equation 2.1 and 2.2, the probability for each13character will be 6 and the escape probability will be 6. In the escape probability, 3
represents the number of types as there are three types, a, b and c.
In most experiments, the use of 5 as a maximum order has proven to be efficient, as
PPMD starts with the model’s maximum order first to encode the forthcoming symbol(Teahan et al., 2000).
If the forthcoming symbol was predicted by the current model, then its probability inthe current maximum order, 5 in this case, will be used to transmit it. If the forthcoming
symbol was not found in the model, then the encoder will escape to the next lower
order model, 4 in this case. This process of escaping will be repeated until the model
finds that symbol or prediction. If the model does not contain the symbol, then theencoder will back off to a default order of -1 (Teahan et al., 2000).
To explain character-based encoding in more detail, Table 2.2 presents the way PPM
models a given string. The example in this case is using the PPMD prediction method
to model the string ‘tobeornottobe’. The model in this example uses a maximum modelorder of 2 for illustration purposes (although normally it would be order 5). The first31and the second columns contain nine and six different predictions, respectively. Eachcolumn contains an escape probability whose count c is equivalent to the number of
unique symbols that have been seen in the given string. Therefore, the escape symbol
the third column (order 0) has a count of 6 because six unique symbols have been seenin the given string. The final column at the bottom of the table that has the lowest ordercontext of -1 will be used when a symbol is completely unseen. In the table, c indicatesthe count, p symbolizes the probability and |A| is the size of the alphabet that is used
(Teahan et al., 2000).
Let the imminent character for this example be letter o. The letter has been seen once
before (‘be’ → o) for the order two context ‘be’ and therefore it has a probability of 12,
1

applying equation (2.1) since the count is 1, and as a result (− log 2 2 = 1). Therefore,
the letter o will be encoded using 1 bit. But if the upcoming letter in the order twocontext had not been seen before, (i.e. suppose the next letter was t rather o), then themodel would need to escape to a lower order, the escape probability will be 12, and themodel will back off to the order 1 context.
When the model backs off, the new order will be used to estimate the probability, andin this case, there is no letter t that comes after e. As a result, the model will encode1

another escape using a probability of 2, and the context will be reduced to the null(order 0) context. Letter t will be encoded using this order, where the probability will
5

5

1

1

be 26. The total cost of predicting the last letter will be 26 × 2 × 2, which in this casewill be over 4 bits. Moreover, if the following letter has not been seen before in thecontext, such as letter x, the escape probability will be encoded three times from the
1

1

3

1

maximum order of 2 to -1 with the following probabilities:2 × 2 × 13 × 256 since order-1 will be used to encode this letter since we are encoding English characters using
ASCII (with an alphabet size of 256), and this will require over 12 bits (Teahan et al.,2000).

32

Order 1

Order 2
Prediction cpOrder 0Prediction cpPrediction c

p

1 1/2

‘b’ → e2 3/4 → b

2 3/26→ esc 1 1/2→ esc

1 1/4 → e

2 3/26

1 1/2 ‘e’ → o

1 1/2 → n

1 1/26→esc

1 1/2 → o

4 7/26

1 1/2 ‘n’ → o

1 1/2 → r

1 1/26

1 1/2 → t

3 5/26

2 3/8 → esc

6 3/13‘be’ → o‘eo’ → r→ esc 1 1/2‘no’ → t→ esc 1 1/2‘ob’ → e

2 3/4 ‘o’ → b→ esc 1 1/4‘or’ → n

1 1/2→ esc 1 1/2‘ot’ → t

→ esc

1 1/2

→ esc 1 1/2

→r

1 1/8

→t

1 1/8 Order -1→ esc

3 3/8 Prediction c‘r’ → n→ esc

1 1/2 → A

‘t’ → o

2 1/2

1 1/2

→t

1 1/6

‘to’ → b

2 3/4

→ esc

2 1/3

→ esc

1 1/4

→ esc

‘tt’ → o→ esc

1 1/|A|

1 1/2

1 1/2

‘rn’ → o

p

1 1/2
1 1/2

Table 2.2: Processing the string ‘tobeornottobe’ using PPM(Teahan et al., 2000)

33

2.3.5 Post-processing phase

Post-processing is the final stage of the development of Arabic OCR. The objective of
this step is to enhance the recognition accuracy by detecting and correcting linguistic
misspellings in the produced OCR text without human intervention. Research studies
on Arabic OCR have implemented post-processing methods in order to improve theoutput, such as Doush and Trad (2016) and Magdy and Darwish (2008). It is worth
mentioning that three main elements should be considered in correcting OCR output:
non-word errors correction; isolated word errors correction; and context–based wordcorrection (Parvez and Mahmoud, 2013). Generally, post-processing methods can be
categorized into two main approaches: lexicon-based methods; and context-based(statistical) methods (Taghva and Stofsky, 2001).
The typical technique for correcting the mistakes of Arabic OCR outputs is thelexicon-based method which requires the utilization of an Arabic dictionary, such asin Hassin et al. (2004) and Aljarrah et al. (2012). This technique corrects errors without
considering any contextual information in which the errors appear. Therefore, aproblem might occur with using this approach when a word is misrecognized by an
OCR system and is also in the lexicon (these are called real-word errors) such as, Fearfor Tear. This occurs in many languages such as Arabic in which a large fraction of
three characters sequences are corrected words. Consequently, only non-word errors
can be corrected, since this method is comparing the recognized words with the words
that are in the dictionary. Also, this approach requires a wide-ranging lexicon thatconsists of all single words. However, the Arabic language has various dialects and it
is also a triglossic language with three forms – modern standard Arabic and classicalArabic (Damien et al., 2009) and mixtures of the two. Therefore, this approach is lessappropriate for Arabic language since building a single lexicon for Arabic language ismore complicated.
On the other hand, context-based (statistical) methods take into account the contextual
information in which the misrecognized words appear. A few studies have
implemented statistical language models for improving the recognition accuracy of
Arabic OCR systems, such as in Prasad et al. (2008), Doush et al. (2018) and Natarajan
et al. (2008). Using such methods will help overcome the problem of correcting realword errors. Moreover, they are also useful in correcting word errors that might have34

several potential corrections, since these techniques can correct word errors based ongrammatical concepts and semantic context (Bassil and Alwani, 2012). Teahan et al.
(1998) have applied a statistical approach by using the PPM compression-based
language model for correcting English text. The PPM algorithm predicts a probability
distribution for the upcoming characters by using the previous characters, as describedabove in Section 2.3.4.1. For Arabic text, a study by Alhawiti, (2014) investigated thepossibility of using the PPM language model for correcting Arabic OCR output text inorder to improve the overall accuracy of the OCR system. This study had shown asignificant improvement of the OCR system’s performance when only correcting
single-character errors.
Recently, there have been several attempts to provide systems for correcting Arabic
OCR output. For instance, Doush and Trad (2016) propose a system for Arabic OCR
output correction based on Google online suggestions within Microsoft Office Word.
Bassil and Alwani (2012) describe a context-based technique for detecting andcorrecting Arabic OCR errors. Although there are some studies on applying contextbased methods for correcting Arabic OCR output, more research is needed oninvestigating the use of Arabic contextual information for OCR output correction(Krayem, 2013).
2.4 Performance evaluation
OCR performance evaluation can be classified into two types: black-box evaluation
and white-box evaluation. In the former, an entire OCR engine is treated as anindivisible unit, so the submodules of the OCR system are not known to the evaluator,
whereas with the white-box evaluation, each submodule of the OCR system is
evaluated if the submodules are accessible (Rice, 1996). Performance evaluation of
OCR systems is essential for monitoring progress of OCR systems development,
assessing the effectiveness of OCR algorithms, identifying open areas for further
research and providing scientific explanation for the performance of OCR systems(Mihov et al., 2005; Kanungo et al., 1999a). Therefore, to produce an efficient Arabic
OCR system, effective performance evaluation of current OCR systems is essential.
Despite the significance of Arabic OCR system performance evaluation, relatively
little work has been published on empirical analysis of the effectiveness of Arabic
OCR systems. For instance, two studies provide an evaluation of two Arabic OCR
35

systems (Kanungo et al., 1999a; Kanungo et al., 1999b). However, as these studies
were conducted in 1999, over 17 years ago, they do not reflect current progress in thefield of Arabic OCR development (Alginahi, 2013). Some competitions have been
held by international conferences for printed Arabic text recognition in order toevaluate different OCR systems. For example, a competition was presented at the 11th
International Conference on Document Analysis and Recognition (ICDAR-2011)(Slimane et al., 2011). The main objective of this competition was to assess the impactof font pitch sizes on the performance of OCR systems. A recent competition wasorganized by the 14th International Conference on Document Analysis andRecognition (ICDAR-2017) (Slimane et al., 2018). In both competitions, only a wordlevel dataset, in which each text image contains one Arabic word, was used forevaluating printed OCR systems and technique. A more recent empirical study
provides a comparative evaluation of the most common Arabic OCR systems (Saber
et al., 2016). However, the study by these authors only investigated the effectivenessof input quality images on the performance of Arabic OCR systems. In addition,
exploring Arabic OCR systems in relation to their sensitivity to different levels of pagequality may not be adequate in fairly assessing their success, as some OCR systems
include a combination of image enhancement techniques. To the best of the author’s
knowledge, no established work has gaged the current progress in the enhancement of
Arabic OCR in terms of the challenges of Arabic script.
Moreover, the performance assessments of Arabic OCR systems are only reported bytheir developers: their results are derived from different datasets that might be smallor might be used in developing the systems (Al-Badr and Mahmoud, 1995; Alginahi,2013). Consequently, as these performance tests are statistically invalid, they cannot
be used to compare the performance between Arabic OCR systems (Margner and El
Abed, 2009; Alginahi, 2017). Evaluating the performance of Arabic OCR systems is
also challenging as no standard dataset is available nor is a set of performance metrics
freely available to the community of Arabic OCR developers (Al-Muhtaseb andQahwaji, 2011; Abdelraouf et al., 2008; Al-Badr and Mahmoud, 1995; Ahmad et al.,2016). In addition, most reports on the performance of Arabic OCR systems are interms of the general, standard performance measurement of character accuracy, suchas in Dahi et al. (2015) and Ahmad et al. (2016). However, this performance metric is36

insufficient to assess how Arabic OCR systems are coping with the challenges of
Arabic script.
On the other hand, to obtain statistically meaningful results when evaluating theperformance of OCR systems, a great number of text images are needed to be tested(Rice, 1996). Although tools exist for other languages (e.g. English (Carrasco, 2014),(Nartker et al., 2005)), none exists for Arabic. Therefore, a programmed test tool isneeded to automate the evaluation test. Additionally, conducting the performance
evaluation under an automated tool will result in eliminating human error, improve
speed, precision and reduce repetition (Saber et al., 2016). From the experimental
studies on Arabic OCR evaluation, only two studies—(Saber et al., 2016, 2014)—
indicate that an automated tool was utilised to evaluate the performance of Arabic
OCR systems. Unfortunately, the utilised tool is not available for researchers and islimited in accuracy metrics.
2.5 Challenges and open problems
This chapter has overviewed the main stages used in printed Arabic OCR. It main aim
is to reveal the current status of printed Arabic OCR. Although there are various
attempts to solve the problems of Arabic text recognition, there is still a crucial needfor more research.
In an attempt to evaluate the status of printed Arabic OCR and support the claim that
more research is needed in many areas, we used Google scholar to search for scientificresearch publications, in March 2018, using phrases that are related to Arabic text
recognition. The findings are summarized in Table 2.3. The table shows the searchphrases used and the search results returned by Google Scholar. It is apparent from thetable that there is a lack of Arabic OCR research as comparatively very little research
has focused on Arabic OCR compared to studies in OCR for other languages. For
example, there were 322,000 results returned for the more general search query ‘OCR’,
whereas there were only 956 results returned for the more specific search query‘Arabic OCR’.
In order to provide a measure of the coverage of research in a particular area, we canestimate the probability that a particular research paper will be in a more specific topic
area compared to the more general topic area. For example, we may be interested in
the general topic area “single font OCR” and wish to see how much research has been37

published in the more specific topic area “single font Arabic OCR” in comparison. We
can estimate the probability p that the more general topic will be concerned with themore specific topic as p = s / g where s is the count of the number of papers found forthe specific topic compared to the count g of the number of papers found for the moregeneral topic. Then we can define the ‘Information Coverage’ I associated with thespecific topic in relation to the more general topic as I = – log p. If this value is highcompared to other specific vs. general comparisons for the same overall topic (e.g. in
relation to Arabic OCR vs. OCR in general), then this reflects that research may beunder-represented in this area.
This analysis has been done using the values from Table 2.3 and graphed in Figure
2.8. In the Figure, we see that except for papers on Arabic OCR concerning easy fonts
and diacritics, the remaining topics have higher Information Coverage values meaningthat there have been less papers published in these areas proportionately compared topapers published in the more general (non-Arabic) areas. We can use Figure 2.8 tohelp gage the present status of printed Arabic OCR research as it highlights some open
areas which need more research. This is based on the number of publications for single,
omni and multi font OCR concerning various elements that are related to text
recognition concerning easy fonts, complicated fonts, diacritics, page layout, multilanguage and noisy documents. In particular, for Arabic text images which containcomplicated fonts, there are still many gaps in the research. Furthermore, for single,
omni and multi font Arabic OCR on multi-language text images, intensive further
research is needed.
Figure 2.9 plots the number of papers per 5-year period for the top 100 Google Scholar
searches using the Arabic OCR related phrases. A number of striking results areapparent in Figure 2.9. For example, publications for Arabic OCR peak after 2005.
Also, the numbers of papers for printed Arabic OCR decrease since 2005 (this could
be because researchers have focussed on handwritten Arabic OCR). Furthermore, it isapparent that the smallest numbers of papers in the period of Arabic OCR research are
papers related to noisy documents.
Note that the earliest research papers for the ‘Arabic OCR’ search query are from 1985,
which is a result of the top-100 ranking returned by Google Scholar. If, however, we
restrict the range of years for which we search, we find that the first papers returned
by Google Scholar appear in the 1970 to 1980 period. In contrast, Bader (1995) states
38that text recognition research first originated in 1940, and papers related to the ‘text
recognition’ query appear in Google Scholar from the 1960s.

Google Scholar search phrase
1
2
3
4
5
6
7
8
9
10

11

12

13

14

15

+"Arabic OCR"+"OCR"+"OCR" + "Arabic printed text"+"OCR" + "printed text"+"Arabic OCR" + "diacritics"+"OCR" + "diacritics"+"Arabic OCR" + "page layout"+"OCR" + "page layout"+"Arabic OCR" + "multi-language "+"OCR" + "multi-language"+"Arabic OCR" + "Omni font"+"OCR" + "Omni font"+"Arabic OCR" + "single font"+"OCR" + "single font"+"Arabic OCR" + "multi-font "+"OCR" + "multi-font"+"Arabic OCR" + "noisy document"+"OCR" + "noisy document"+"Arabic OCR" + " Simplified Arabic " + "single font"+"Arabic OCR" + " Simplified Arabic " + "Omni font"+"Arabic OCR" + " Simplified Arabic " + "multi font"+"Arabic OCR" + " Advertising Bold " + "single font"+"Arabic OCR" + " Advertising Bold " + "Omni font"+"Arabic OCR" + " Advertising Bold " + "multi font"+"Arabic OCR" + "diacritics" + "single font"+"Arabic OCR" + "diacritics" + "Omni font"+"Arabic OCR" + "diacritics" + "multi font"+"Arabic OCR" + " page layout " + "single font"+"Arabic OCR" + " page layout " + "Omni font"+"Arabic OCR" + " page layout " + "multi font"+"Arabic OCR" + " multi-language " + "single font"+"Arabic OCR" + " multi-language " + "Omni font"+"Arabic OCR" + " multi-language " + "multi font"+"Arabic OCR" + " noisy document " + "single font"+"Arabic OCR" + " noisy document " + "Omni font"+"Arabic OCR" + " noisy document " + "multi font"

Number of papers
956
322,000
247
7,190
302
1,800
54
3,360
20
866
60
380
61
717
149
1,270
12
515
20
22
48
5
5
15
30
36
62
8
9
11
17
9
29
1
2
3

Table 2.3: Google Scholar search results for Arabic OCR-related phrases

39

Information Coverage I

2
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0

Single Font
Omni Font
Multi-Font

Easy fontComplicatedfont

Diacritics

Page layout Multi-language

Noisy

OCR Elements

Number of Top 100 Papers

Figure 2.8: Present status of printed Arabic OCR based on the number of publications
for different OCR elements

50
40
30
20
10
0

Period
AC

PC

AD

PL

ML

OF

SF

ND

MF

Figure 2.9: Number of papers per 5-year period in the top 100 results returned by
Google Scholar for different Arabic OCR related search phrases
Notes: AC = ‘Arabic OCR’; PC = ‘Arabic printed text’; AD = ‘Arabic diacritics’; PL = ‘Arabic OCR+ page layout’; ML= ‘Arabic OCR + multi-language’; OF = ‘Arabic OCR + omni font’; SF = ‘Arabic
OCR + single font’; MF = ‘Arabic OCR + multi font’; ND = ‘Arabic OCR + noisy document’.

From the review of each stage used in Arabic OCR, the following observations havebeen noted:
1- All the reviewed research of printed Arabic OCR have used the general OCR
methodology which involves the five stages; pre-processing; feature
extraction; segmentation; classification and post-processing. However, thefollowing are still open questions: ‘Is the current OCR methodology the mosteffective for designing Arabic OCR?’ and ‘Are there alternative methodologies
40that might yield better results for Arabic OCR’?
2- From the review of each OCR stage, it is apparent that the most challenging
task in the development of Arabic OCR is the segmentation task. Althoughprevious studies have presented different segmentation techniques for Arabic
OCR, these studies have not provided the accuracy performance of thesetechniques. Since only the overall OCR performances have been reported, it isdifficult to gain an insight into which segmentation techniques perform betterfor printed Arabic OCR. A performance evaluation tool should be developed
to assess the different segmentation techniques.
3- The pre-processing stage review given in this study reached the conclusion that
direct adoption of pre-processing methods which are designed for general
purposes might be not applicable for Arabic script. Thus, developing preprocessing methods that consider the specific characteristics of Arabic script isneeded.
4- Most of the proposed methods for feature extraction in Arabic OCR have been
adopted from methods that have been developed for other languages without
considering the characteristics of Arabic script. Such methods may not be themost appropriate for accurate recognition. The characteristics of Arabic script
should be taken into consideration when selecting a feature extraction methodthat is able to distinguish between Arabic characters.
5- The studies on performance evaluation of printed Arabic OCR have used a
black-box evaluation method which can only provide the overall performanceof OCR systems. For more insight into which OCR stage is causing the mostproblems, a white-box evaluation, where each component of the system isaccessible, is required.
2.6 Summary
This thesis has provided a comprehensive literature review of printed Arabic text
recognition. At first, the specific characteristics of Arabic script that challenge therecognition process have been discussed. Then, the general methodology of printed
Arabic OCR has been presented. This methodology was divided into five stages:
preprocessing; segmentation; feature extraction; classification; and post-processing.
41

Techniques applied at each stage of Arabic OCR have been discussed. Also, the issues
related to the performance evaluation have been reviewed. Finally, we analyzed thechallenges and the remaining problems in the field of printed Arabic OCR.

42

Chapter 3: Experimental Evaluation of Arabic OCR
Systems
3.1 Introduction
Performance evaluation of OCR systems is an essential task for OCR systems
development. However, relatively little work has been published on empirical analysisof the effectiveness of Arabic OCR systems. Moreover, studies in Arabic OCR sufferfrom the lack of proper performance evaluation metrics and the availability of
automated evaluation tools. The review in chapter 2 showed that printed Arabic OCR
poses great challenges owing to the special characteristics of Arabic text. Although theliterature provides typical performance metrics, such as character accuracy and word
accuracy for OCR performance evaluation, these metrics are insufficient to assess
Arabic OCR systems in terms of the challenges of Arabic text.
Thus, this chapter first aims to propose an automated software tool with a new set ofobjective accuracy metrics for the evaluation of Arabic OCR systems with respect tothe challenges of Arabic text. It also proposes a standard protocol which we hope will
be used as a benchmark by researchers in comparing between OCR algorithms. It thenaims to experimentally evaluate the effectiveness of the state-of-the-art printed Arabic
text recognition systems to provide a better insight into their performances.
The work in this chapter has been published in the following papers:


Alghamdi, M.A., Alkhazi, I.S. and Teahan, W.J., 2016. Arabic OCR
evaluation tool. In Computer Science and Information Technology (CSIT),
2016 7th International Conference on (pp. 1-6). IEEE.



Alghamdi, M. and Teahan, W., 2017. Experimental evaluation of Arabic
OCR systems. PSU Research Review, 1(3), pp.229-241.

This chapter is organised as follows: in section 3.2, a new set of objective accuracy
metrics for Arabic OCR evaluation is discussed. The developed tool for the evaluationof Arabic OCR performance is described in section 3.3. The most common Arabic
OCR systems and an experimental protocol are presented in section 3.4 and 3.5
respectively. The experimental results are then presented and discussed in section 3.6.
In the final section, a summary and conclusion is provided.

43

3.2 Metrics for Arabic OCR system performance evaluation
Generally, Arabic OCR systems are evaluated in terms of character accuracy with thisobtained by identifying the differences between an observed variable, which is theoutput text of the OCR system, and a reference variable, which is the original text
called ‘ground-truth’ (Kanai et al., 1993; Teahan et al., 1998). These differences canbe determined by the edit distance which is the minimum number of edit operations
required to correct the OCR output text to be matched with the ground-truth text. These
edit operations are: character insertion, character deletion and character substitution;
for more details refer to Levenshtein (1966).
For example, the edit distance between the two strings, the ground truth string ( ‫جامعة‬‫ )بانجور‬and the OCR-generated string, (‫ )حامعة ببانجور‬is 2. The required operations totransform the OCR-generated string into the correct one are: (1) substitute theunderlined letter in the OCR output (‫ )حـ‬for (‫ ;)جـ‬and (2) delete the underlined letter(‫)بـ‬. This number, which is the minimum number of single character edit operations, isknown as the Levenshtein distance (Levenshtein, 1966). Regarding OCR evaluation
studies, it is common to determine the edit distance in different levels: word level andcharacter level. However, character level accuracy is useful for predicting
improvements in OCR systems in which OCR developers are interested, whereas wordlevel accuracy is useful for analysing the ease of human readability, as Kanungo et al.
(1999b) emphasise. Word accuracy is outside the scope of this of this study.
In the following sub-sections, we suggest various objective performance metrics withrespect of the characteristics of Arabic text for evaluating Arabic OCR systems which
can provide us with more insight into the effectiveness of Arabic OCR systems.
a.

Overall character accuracy

Accuracy in an OCR-generated text in respect to the ground truth text is computed byLevenshtein edit distance; that is, the minimum number of primitive operations thatare required to correct the OCR output text to be matched with the ground truth text.
These operations are substitution, deletion and insertion.
Overall character accuracy determines the accuracy of Arabic OCR over all of thetested text images. Character accuracy is the percentage of ground-truth characters thatare recognised correctly on an Arabic text image, by comparing the ground-truth text44

file with the OCR output text file. The character accuracy is determined by Equation(3.1):
me
 100
m

(3.1)

where m is the number of characters in the ground-truth text file and e is the edit
distance. The cost for each edit operation is defined as 1.
b.

Character accuracy based on character class

Considering Arabic script, some characters have features that allow them to beclassified into a particular class. Consequently, it will be valuable to analyse theaccuracy of each class. To determine the accuracy of this metric, Arabic charactershave been classified into various classes as below:
1.

Character accuracy based on character position

As mentioned in chapter 2, an Arabic character may have one to four shapes depending
on its position in a word; for example, see Table 3.1. The four possible shapes are
isolated, initial, middle and end. Thus, it is valuable to analyse the effectiveness of
Arabic OCR systems in recognising isolated, initial, middle and end characters. To
analyse the accuracy of this class, the ground truth Arabic characters are categorised
into four classes: isolated, initial, middle, and end, as shown in Table 3.1. The accuracyof each class by using Equation (3.1).
Isolated

InitialMiddle

End

‫ه‬

‫هـ‬

‫ـهـ‬

‫ـه‬

Table 3.1. An Arabic character with dissimilar shapes

One dot

Two dots

Three dots

No-dot‫بجخذزضظغفن‬‫تقية‬‫شث‬‫حدرسصطعلمهوكى‬

Table 3.2. Examples of dot characters and no-dot characters

Dot character above baseline

Dot character below baseline‫قنفغظضشزذخثت‬‫يجب‬

Table 3.3. Examples of dot characters based on the baseline

45

2.

Dot character class and no-dot character accuracy

One of the challenges of Arabic OCR is the presence of dots in Arabic script. Assessing
the impact of dot and no-dot characters on the performance of Arabic OCR systems istherefore of interest. To do so, Arabic characters are categorised into four classes: one
dot class, two dot character class, three dot character class and no-dot character class,as illustrated in Table 3.2. The accuracy of each class is determined by Equation (3.1).
3.

Dot character accuracy based on baseline

Dots of Arabic characters can be placed either above or below the baseline. Owing to
the significance of the baseline in Arabic OCR, it would be valuable to compute theaccuracy of characters that are most related to the baseline. Regarding the baseline,
Arabic dot characters will be divided into two groups: above baseline and below
baseline, as shown in Table 3.3. Each group accuracy is expressed by Equation (3.1).
4.

Zigzag-shaped character accuracy

One of the distinguishing characteristics of Arabic script is the presence of a zigzagshaped mark (‫)ء‬, called Hamza, with some Arabic characters. The aim of using thismetric is to expose the sensitivity of Arabic OCR systems to zigzag-shaped characters.
The zigzag-shaped character accuracy is computed by using Equation (3.1).

Figure 3.1. Loop characters46

Figure 3.2. Diacritic marks

5.

Loop-shaped character accuracy

When considering the characteristics of Arabic script, several letters consist of a loop
shape. Such a feature may be an obstacle in Arabic OCR development. Thus, it would
be desirable to assess the accuracy of characters that have this feature. In order toassess the accuracy of this class, loop characters are defined according to how they
are presented in Figure 3.1. The accuracy of loop-shaped characters is also determinedby Equation (3.1).
c.

Diacritics accuracy

A major feature of Arabic script is the appearance of diacritical marks, as shown in
Figure 3.2. Thus, it is essential to evaluate the performance of Arabic OCR systems
in recognising Arabic diacritical marks. As before, diacritical mark accuracy isdetermined by Equation (3.1).
d.

Digit accuracy

It is critical for developers to assess the recognition of numbers by Arabic OCR
applications. In respect to Arabic script, both Hindu–Arabic digits and English
numerals may appear in any Arabic text. Thus, the evaluation considers all numerals
in computing the accuracy of digits. Digit accuracy is determined by Equation (3.1).
e.

Punctuation accuracy

Several punctuation symbols resemble Arabic characters. For example, the full-stoppunctuation (.) is quite identical to the Arabic Zero number (٠). This illustration
confirms that the punctuation group has a vital effect on Arabic OCR accuracy.
Punctuation accuracy is determined by Equation (3.1).

47

3.3 An Automated Arabic OCR Evaluation Tool
The new Arabic OCR evaluation tool that was developed for this study, which is
programmed in Java, allows for comparison of an OCR-generated text file with aground truth text file. The difference between the two text files is computed in termsof the minimum cost of converting the OCR output text to the ground truth. For thispurpose, Levenshtein edit distance algorithm in (Levenshtein, 1966) has been adopted.
By using the software tool, an evaluator can quantitatively measure the performanceof Arabic OCR systems according to the proposed Arabic accuracy metrics, mentioned
in section 3.2. A Graphical User Interface (GUI) has been implemented to facilitate
evaluators to select the OCR output text file and the ground truth text file, as
demonstrated in Figure 3.3. Also, as can be seen in Figure 3.3, after clicking on the
Evaluate button, the GUI displays statistics of all the accuracy metrics discussed. The
Arabic OCR evaluation tool is provided freely as open-source software at thefollowing GitHub address: https://github.com/NLPBangor/OCREvaluationTool.
In order to illustrate how the tool works, an example is provided here. Figure 3.4 shows
the text image that contains Arabic text with digits, diacritics and punctuation marks.

Figure 3.3. GUI of the Arabic OCR evaluation tool48

The open source OCR Tesseract engine1, which supports Arabic, was run to convert
the Arabic text image to an editable text. Figure 3.5 displays the corresponding OCRgenerated text. To evaluate the accuracy of the utilised OCR application, the tool was
run on the OCR output text and the ground truth text. The result of the evaluation ispresented in Figure. 3.3.

Figure 3.4. A sample Arabic text image

Figure 3.5. OCR output text for image in Fig. 3.4

This example illustrates the idea that evaluation of Arabic OCR systems according todifferent accuracy measures is required. In other words, it can be seen from the resultsin Fig. 3.3 that the total character accuracy is about 78%. However, the accuracy resultsfor individual character classes are significantly different. In particular, the accuracyof the one dot characters group and the two dots characters group are around 67%,
whereas, the accuracy of the three dot character class is 100%. Moreover, the observed
difference between the accuracy of the zigzag characters group and the loop charactersgroup is significant, 50% and 80% respectively. Another important finding is that theaccuracy of the above baseline characters class (80%) is very different to the accuracyof below baseline characters (67%). Also, it can clearly be seen that the punctuation
class has the lowest accuracy rate.
Based on the findings above, it is possible to state that measuring Arabic OCR
performance in terms of the accuracy metrics, which are implemented in the Arabic
OCR evaluation tool, can help researchers to automatically assess how Arabic OCR
1 https://github.com/tesseract-ocr

49systems are overcoming the challenges of Arabic text and it contributes to eliminate
human error, improve speed and precision, and reduce repetition in evaluating Arabic
OCR systems.
3.4 Arabic OCR Systems
Some research efforts on printed Arabic text recognition have been reported in theliterature. A multi-font cursive Arabic OCR system is reported by Khorsheed andClocksin (2000). This system is a free-segmentation based approach in which eachword in a used lexicon was transformed into a normalised polar image. The system
extracts Fourier transform coefficients from a normalised polar image. Each word isrepresented by a template that contains a Fourier transform coefficient. The
recognition is performed using a normalized Euclidean distance that measures the
distance between the templates and tested word images. This system was evaluatedusing a sample of 1700 Arabic words and achieved an accuracy of 90%. To improve
the accuracy rate, Khorsheed (2004) presents a new system based on Hidden Markov
Models (HMM) in which each word is represented by a single HMM. The system hasachieved an accuracy rate of 97% which is a higher accuracy rate compared to thetemplate-based system.
A printed Arabic OCR system based on HMMs was developed by Al-Muhtaseb et al.
(2008). They used overlapping and non-overlapping hierarchical windows to extract
16 features. The system was tested on eight Arabic fonts and achieved accuracy rates
between 98.1% and 99.9%. In another effort, Khorsheed (2007) introduced a freesegmentation OCR system for recognising printed Arabic text. The system extracts
statistical features to be fed to the HMM. The system was tested on six different Arabic
fonts and the highest accuracy achieved was 92.4%. In a later work, Khorsheed (2015)
proposed another free-segmentation OCR system using HMMs with run-length
encoding as a feature extraction method. The system achieved a higher accuracy ratecompared to the pervious developed system. Recently, Ko et al. (2018) proposed an
OCR system for recognising printed Arabic text using a deep-learning approach. The
system achieved an accuracy rate of 99.9%.
However, it is a challenge to compare the performance accuracy that are obtained on
different datasets. Only a handful of accessible OCR systems claim that they arecapable of recognising Arabic script. Therefore, our evaluation study is limited to the50

four most well-known Arabic OCR systems, namely, Automatic Reader 11.2 producedby the Sakhr Software Company; FineReader 12 produced by the ABBYY Company;
Clever Page produced by RDI (Research & Development International); and Tesseract
produced originally by Hewlett Packard (HP). In the following subsections, the four
Arabic OCR engines are briefly discussed.
Automatic Reader 11.2 software
Automatic Reader is a commercial product first developed by the Sakhr Software
Company in 1982 for text recognition of Arabic script. It supports Arabic language
and several Arabic character-based languages, such as Arabic, Farsi and Urdu. Sakhr
claims that Automatic Reader has been ranked as the best existing Arabic OCR
software for high-quality text images by United States (US) government evaluators(Sakhr Software OCR, 2017). It supports multi-font type and multi-resolution images.
However, font size 8 is not supported by the Automatic Reader OCR software(henceforth, referred to as Sahkr OCR).
FineReader 12 software
FineReader is produced commercially by a global company, called ABBYY, asadvanced OCR software. The performance of FineReader has been enhanced by
ABBYY for many years. FineReader 12 supports 190 languages including Arabic
script using dictionary support (Abbyy OCR, 2017). It supports multi-font types,
multi-size and multi-resolution images. Henceforth, FineReader will be referred to as
ABBYY OCR.
Clever Page software
Clever Page originally began as a PhD research study by El-Mahallawy (2008). Since
2008, Clever Page has been designed and developed as an Omni font-written Arabic
OCR engine by Research & Development International (RDI). Clever Page is a HMM
based OCR system. El-Mahallawy (2008) designed a new feature extraction method
based on autonomously normalized horizontal differentials. These features are usedwith HMMs to model Arabic characters. He reported a word error rate of 0.77% whichis equivalent to an accuracy rate of 99.3%. This very high performance rate is due tothe use of a noise-free dataset and using high quality Arabic text images. It supports
multi-font types and multi-size text images. However, it is worth mentioning that the51

Clever Page OCR software only works on pages with 300 dots per inch (dpi).
Henceforth, Clever Page will be referred to as RDI OCR.
Tesseract software
Tesseract is an OCR engine designed at Hewlett Packard (HP) between 1984 and 1994.
Since late 2005, it has been maintained by Google and released as open source OCR
software. Tesseract OCR processes in different steps. In the first step, it converts animage to a binary image using the Otsu thresholding method (Otus, 1979). In the next
step, it uses a page layout analysis method that has been developed by HP in order toextract the text blocks from an image (Smith, 2007). Then, it segments a text block
into lines and words using definite spaces and fuzzy spaces (Smith, 2007). Tesseract
extracts the outlines of the segmented words to obtain the polygonal approximation asfeatures (Smith et al., 2009) . For the recognition task, it uses adaptive and staticclassifiers with the use of a dictionary lookup (Smith, 2007). It supports various
languages. However, Arabic support has only been added recently (Sabbour andShafait, 2013). Tesseract is the only Arabic OCR software that is freely available. It
supports multi-font types, and multi-size and multi-resolution images.
3.5 Experimental Protocol
Very few Arabic datasets are freely available to researchers. The most widely used
dataset for evaluating Arabic OCR approaches is the Arabic Printed Text Image(APTI). This public dataset was developed by Slimane et al. (2009). However, APTI
is a word-level dataset where each text image contains only one Arabic word. AnotherArabic dataset is ALPH-REGIM which is provided by Ben Moussa et al. (2010). Thisdataset contains about 5000 printed and handwritten Arabic text images. Compared to
the APTI dataset, ALPH-REGIM is a paragraph-based text image dataset. However,
the text images are only available in one font size and at one resolution level. A recent
printed Arabic dataset is created by Doush et al. (2018). However, this dataset
comprises text images of only two Arabic font types. Thus, the KAFD dataset,developed by Luqman et al. (2014), is used for evaluating the performance of the four
Arabic OCR systems.
The KAFD dataset is freely available and is a page-level dataset where each text image
consists of a text. It has Arabic printed text images and corresponding ground-truth
text files. These text images are available at 100 dpi, 200 dpi and 300 dpi. Furthermore,52

it comprises text images of 40 Arabic font types, 10 pitch sizes and four styles, withresolutions of 100 dpi, 200 dpi, 300 dpi and 600 dpi.
For the current work, 10 different font types of the text image, in which the forms ofthe characters are of various types, are selected, namely, Andalus, Arabic Transparent,
AdvertisingBold, Diwani Letter, DecoType Thuluth, Simplified Arabic, Tahoma,
Traditional Arabic, DecoType Naskh and M Unicode Sara. These font types are
selected based on the level of complexity of the writing style in printed Arabic script,
ranging from simple fonts with no overlaps and ligatures, such as AdvertisingBold, tomore complex fonts with overlaps, such as Diwani Letter. For each font type, 8, 12,18 and 24 pitch sizes have been used in order to highlight the effectiveness of Arabic
OCR systems on specific pitch sizes. Moreover, to enable the evaluation of theperformance of Arabic OCR systems in terms of font style, normal and italic font styles
are used. To study the influence of the page resolution level on Arabic OCR system
performance, all text images in the above set have been randomly selected at 100 dpi,
200 dpi and 300 dpi. This resulted in 80 text images for each resolution. Thus, thisexperiment is performed on 240 text images in TIFF format.
The experiment was conducted on the four Arabic OCR systems, as previously
discussed, namely, Sakhr, ABBYY, RDI and Tesseract OCR systems. Sakhr and
ABBYY OCR systems were kindly provided to the authors by their developers,
whereas the RDI OCR system output was obtained by sending the dataset to thesystem’s developer to apply the system to the test images.
To statistically assess the performance of each Arabic OCR system, the performance
metrics described in section 3.2 were used. In particular, the output text files of each
Arabic OCR system were utilised to compute the quantities of each performance
metric, corresponding to the ground-truth text files for the dataset. To eliminate humanerror, improve speed and precision, and reduce repetition, the automated open accesstool for evaluating Arabic OCR systems, descripted in section 3.3 was utilised toobtain the statistical data. A sample of a text image from the dataset and thecorresponding Arabic OCR output are visually illustrated in Figure 3.6.

53

3.6 Experimental Results and Discussion
The experimental results, obtained from the evaluation experiment discussed in theprevious section, are presented in this section to analyse the effectiveness of theevaluated Arabic OCR systems in printed Arabic text recognition.
The overall character accuracy scores for the four evaluated Arabic OCR systems overdifferent resolutions are presented in Figure 3.7. It is apparent that the Arabic OCR
systems are affected by the resolution of the text images. In particular, the resultsshows a gradual increase in the overall character accuracy of all Arabic OCR systems
when increasing the resolution of text images from 100 dpi to 300 dpi. In addition, aclear upward trend is apparent in the overall character accuracy of Sakhr OCR when
the resolution of text images increased from 100 dpi to 200 dpi. Interestingly, highscores of character accuracy at 100 dpi, 200 dpi and 300 dpi were obtained by the
ABBYY OCR system. Crucially, this system among the four Arabic OCR systems has
the highest character accuracy at 100 dpi, 200 dpi and 300 dpi of 46%, 60% and 62%,
respectively.

54

Figure 3.6. (a) A text image from the KAFD dataset; (b) output of the Sakhr OCR system;(c) output of the ABBYY OCR system; (d) output of the RDI OCR system; and (e) outputof the Tesseract OCR system

Figure 3.7. Overall accuracy vs. resolution results from the OCR system evaluation

55

The accuracy of Arabic OCR systems in recognising Arabic characters based on theirposition in a word are provided in Figure 3.8. As has been mentioned, the connectivity
feature of Arabic script is an obstacle to Arabic text recognition. This is supported by
the experiment data which indicate that all of the evaluated Arabic OCR systems havehigher accuracy in recognising isolated characters when they are not connected withother characters in a word. On the other hand, the performance of the Arabic OCR
systems decreased in recognising initial, middle and end characters, as shown in Figure
3.8. Compared to the Arabic OCR systems’ accuracy in recognising isolatedcharacters, the low recognition accuracy of initial, middle and end characters by theevaluated systems is possibly due to the segmentation algorithms implemented bythese systems, as the segmentation process is not required for recognising isolatedcharacters. However, a new methodology is needed to evaluate the segmentation stage
in Arabic OCR systems to gain a better understanding of these results.

Figure 3.8. Character accuracy in terms of character position results from the OCR
system evaluation

The results of the recognition accuracy performance of the Arabic OCR systems interms of one dot, two dot, three dot and no-dot characters are illustrated in Figure 3.9.
It is obvious that the recognition accuracy rates of no-dot characters are significantly
better for all evaluated Arabic OCR systems, compared to one, two and three dot
characters. This confirms that one of the challenges in Arabic OCR development is thepresence of dots in Arabic script, as discussed previously. It has been hypothesisedthat a thinning algorithm, as a pre-processing technique, has an influence on therecognition accuracy of dot characters (Hosseini, 1997). In particular, some thinningalgorithms may remove the dots of Arabic characters which results in misrecognising56

these characters. Therefore, these results are likely to be related to thinning algorithms
used in the pre-processing stage of the Arabic OCR system.

Figure 3.9. Dot character accuracy vs. no-dot character accuracy results from the OCR
system evaluation

Figure 3.10. Dot character accuracy based on baseline results from the OCR systemevaluation

The results of analysing the performance of the evaluated Arabic OCR systems on
characters that have a dot above or below the baseline are presented in Figure 3.10.
These results highlight that Arabic OCR systems perform much better in identifying
characters with a dot below the baseline than characters with a dot above the baseline.
The reasons for these results are not entirely clear. However, one technique used in the
pre-processing stage for developing Arabic OCR systems is page decomposition
which separates the lines of a text block in a text image. To be specific, someresearchers emphasise that considerable attention must be paid in the page57

decomposition of Arabic text images to ensure that dots placed above or below a lineof text are not separated (Al-Badr and Mahmoud, 1995; Sami El-Dabi et al., 1990).
Thus, a possible reason for this finding may be due to the page decomposition process.
Figure 3.11 compares the recognition accuracy for zigzag-shaped characters and loopshaped characters by the evaluated Arabic OCR systems. It is apparent from the resultsthat the performance rates of Arabic OCR systems in accurately recognising loopshaped characters are higher than in recognising zigzag-shaped characters. It can thus
be assumed that recognising characters with a zigzag shape is more challenging thanrecognising characters that have a loop shape.

Figure 3.11. Character accuracy based on shaped character results from the OCR
system evaluation

Figure 3.12. Digit, punctuation and diacritics accuracy results from the OCR systemevaluation

58

Figure 3.13. Arabic OCR accuracy vs. font pitch size results from the OCR systemevaluation.

Figure 3.14. Italic and non-italic font accuracy comparison results from the OCR
system evaluation

Figure 3.12 presents the recognition accuracy of the evaluated Arabic OCR systems interms of the digits, punctuation and diacritics groups. Surprisingly, Tesseract and RDI
OCR systems were not able to recognise any diacritical marks. However, one possible
reason is that these OCR systems were not trained to recognise diacritics. In addition,
Figure 3.12 indicates that the Sakhr OCR system was unable to recognise Arabic digits(Hindu digits). As this result was not expected, we undertook further investigation tofind an explanation. After manual inspection of the output of the Sakhr OCR system,
we discovered that the system recognises Arabic digits as English digits. In otherwords, the system replaced the Arabic digits with English digits when producing the59

output. Improved accuracy rates for the Sakhr OCR system could be achieved if thesystem were to overcome this problem.
The respective accuracy of the Arabic OCR systems in relation to different font pitch
sizes is plotted in Figure 3.13. It can be seen that a drop in character recognition
accuracy occurs when reducing the font pitch size. It can thus be concluded that theevaluated systems struggle when the font pitch size is too small, such as a font pitchof 8. Another important finding from this result is that the RDI OCR system performs
better for a font pitch of 12 than for a font pitch of 24. The reason for this finding is
unclear.
The recognition performance analysis of the evaluated Arabic OCR systems on fontswith an italic style compared to those with a non-italic font style is shown in Figure
3.14. Our experimental results show that, for all evaluated systems, the recognition
accuracy rates for a non-italic font style are higher than for an italic font style. The low
recognition accuracy percentages for an italic font style are likely to be related to thefact that the italic font style is a cursive font.
Table 3.4 reports on the accuracy of the evaluated Arabic OCR systems in terms offont types. As expected, the low accuracy rates for all evaluated systems in recognising
the Diwani Letter font are due to the complexity of this font which contains overlaps.
In summary, most of the performance accuracy rates of the evaluated Arabic OCR
systems are below 75%, indicating the continuing need for improvements in therecognition of printed Arabic script. Moreover, the correlation between theperformance accuracy of Arabic OCR systems and the features of Arabic script havebeen highlighted. In particular, the experimental analysis indicates that thecharacteristics of printed Arabic script, such as the connectivity, and the presence ofdots and zigzag shapes, all contribute to the challenge for Arabic OCR systems.
Overall, the results indicate that recognition of Arabic script remains an open research
problem.

60

Font Type
Traditional Arabic
TahomaSimplified Arabic
M Unicode Sara
Diwani Letter
DecoType Thuluth
DecoType Naskh
Arabic Transparent
Andalus
AdvertisingBold

OCR System
Sakhr

ABBYY

RDI

Tesseract

48.5%
40.5%
52.9%
36.1%
18.1%
36.1%
48.8%
51.5%
28.1%
57.3%

67.6%
69.9%
67.7%
59.4%
18.4%
37.7%
50.2%
75.1%
37.5%
70.2%

51.9%
26.4%
44.9%
25.9%
18.1%
24.2%
41.6%
46.1%
21.7%
27.2%

47.1%
38.4%
46.7%
33.7%
23.3%
32.5%
40.9%
48.6%
25.3%
39.4%

Table 3.4. Arabic OCR performance accuracy according to 10 different font types

3.7 Summary and Conclusion
This chapter describes an automated tool for performance evaluation based on
different objective accuracy metrics with respect to the challenges of Arabic text. This
tool has been specifically developed to assist Arabic OCR researchers to automaticallycalculate the accuracy of different Arabic OCR systems and to assess how Arabic OCR
systems are copying with the challenges of Arabic text. Furthermore, by using thisautomated tool, an OCR evaluator can quickly process an enormous number of testing
experiments. It also provides an experimental protocol that enables the effectivenessof different Arabic OCR systems to be compared.
In addition, this chapter describes an experiment to automatically evaluate four wellknown Arabic OCR systems: Sakhr, ABBYY, RDI and Tesseract. The evaluation
experiment is conducted on a publicly available printed Arabic dataset comprising 240
text images with a variety of resolution levels, font types, font styles and font sizes.
The experimental results show that all the evaluated Arabic OCR systems have low
performance accuracy rates, below 75%, which means that the time which it would
take to manually correct the OCR output would be a prohibitive.

61

Chapter 4: Thinning
4.1 Introduction
This work aims to develop a novel OCR for printed Arabic text. To achieve this aim,
we implement a new Printed Arabic Optical Character Recognition (PATRION)
system using five stages: thinning, feature extraction, character segmentation,
classification and post-processing, as illustrated in Figure 4.1. In this chapter, we
present the first stage for developing the PATRION system which is thinning as a preprocessing stage.
Thinning is one of the critical processes that can be applied to the input text images
for facilitating the subsequent stages of the PATRION OCR development process. In
particular, producing skeletons is required for the PATRION OCR development inwhich extracting features from the skeleton of Arabic text is essential. Thus, a new
thinning algorithm for Arabic script has been implemented in order to fulfil therequirements of the development of the PATRION OCR system. Furthermore, several
new performance metrics for evaluating thinning algorithms for Arabic text arepresented, since there is a lack of quantitative performance measures of thinningtechniques, as stated in the literature.
The work in this chapter has been published in the following paper:
Alghamdi, M.A. and Teahan, W.J., 2017. A new thinning algorithm for
Arabic script. International Journal of Computer Science and Information
Security, 15(1), p.204-211.

This chapter first describes an effective new thinning algorithm for printed Arabic
script. Then, evaluation of thinning algorithms for Arabic will be discussed withintroducing several new objective performance metrics for thinning algorithms. An
evaluation experiment is conducted on the proposed algorithm with providing acomparison with a number of most common thinning algorithms. In the last section, asummary and conclusions will be provided.

62

Figure 4.1: Block diagram of the PATRION system
Note: The shaded area shows the scope of the current chapter (the thinning stage).

63

4.2 An Effective Thinning Algorithm for Arabic Text
An effective thinning algorithm produced by Kocyigit (2012) has been used in thiswork. However, this algorithm was only investigated for English characters. The
method aims to produce a skeleton with one width pixel by detecting the neighborhood
connectivity of any given pixel. Each pixel is directly connected with eightneighboring pixels; the pixel is considered as “encased” if only all the black neighborpixels are interconnected with each other. In other words, if each black neighbour pixelof a considered pixel is connected vertically or diagonally to at least one other black
pixel, the given pixel will achieve a state of encasement. For example, if the center
pixel (P) is being processed pixel, it is considered as “encased” in Figure 4.2: (a), (b)and (c). In contrast, (b), (c) and (d), the pixel (P) is not considered as “encased”.

Figure 4.2: Examples of pixels (a), (b), (c) with an encasement and (d), (e), (f) without
an encasement

Kocyigit algorithm utilizes a 3x3, 2D array of pixels which is obtained by thresholding
the image. The descriptions of the rows and columns are equivalent to the pixel’s
coordinates and are set to either value “1” (black) or “0” (white) depending on thecharacter. Deletion of a pixel will change the value of the pixel from 1 to 0.
Whenever any pixel is encased, the algorithm cleans up the defined pixel. The
algorithm observes sequential and iterative principles in that whenever any pixel is64

removed, the entire algorithm restarts the iterative process, continues until a state ofconsistency is achieved where no further pixel is deleted.
A flowchart of Kocyigit algorithm is provided in Figure 4.3. Initially, the algorithm
finds a black pixel. Then, delete the black pixel if it has an encasement.

Figure 4.3: Flowchart of Kocyigit algorithm65

4.3 Evaluating Thinning Algorithms for Arabic Text
In respect to performance evaluation of thinning algorithms, most of studies evaluate
their proposed thinning algorithm in terms of execution time and compression ratio,such as in Naccache and Shinghal, (1984), Saudagar and Mohammed, (2016) andZhang and Wang, (1988). Furthermore, some researchers evaluate thinning algorithms
by only illustrating the output images of the algorithms, regardless of application
requirements, such as Ali and Jumari, (2003), Ali, (2012), Abu-Ain et al. (2013) and
Abu-Ain et al. (2014). However, from an OCR perspective, these metrics are notsufficient to provide us with insight into which algorithm performs better for OCR.
Zhou et al. (1995) provide other general metrics for assessing thinning algorithms,
such as the thinness metric, which assesses the level to which a patter image is thinned,
and the connectivity metric that measures the connectivity of the thinned patternimages.
As mentioned before Arabic script uses a cursive writing style and therefore, theconnectivity measure is considered as a critical metric in order to evaluate theconnectivity of the output skeleton of an Arabic text image. For instance, the study in
Al-Shatnawi et al. (2014) utilizes the connectivity measure to assess the performanceof different thinning algorithms for Arabic. The idea of this metric is to consider thenumber of connected components in the original image and in the output image of thethinning algorithm. Namely, if the number of components is equal in both images, thenthis is a sign that the thinning algorithm is preserving text connectivity. However, somethinning algorithms may remove some dots of Arabic characters and they may spilt
the body of a character into several parts. Consequently, an issue will arise when
adopting the connectivity metric to evaluate the connectivity of thinned Arabic text. In
particular, when thinning algorithms remove the characters dots or make a
disconnection through the letters forms, then a performance metric which is relying on
the number of connected components, will not be reliable.
To illustrate this problem, Figure 4.4 shows that the number of component of theoriginal image (a) is four and the number of components in the thinned image (b) isfour. Thus, according to the connectivity metric, the algorithm will be assessed aspreserving the text connectivity, where in fact it is not. This problem occurs owing to

66

(a)

(b)

Figure 4.4: Example of the problem of the connectivity metric: (a) an Arabic letter withfour components and (b) a skeleton for (a) with four components

the removing of one dot of the letter and making a gap of the letter’s shape. Therefore,
it is difficult to obtain statistical evaluation results of connectivity preservation by
relying on this measurement.
To overcome this problem, we propose new performance metrics for evaluating
thinning algorithms for Arabic text in terms of connectivity and dots persevering.
Moreover, other further objective performance metrics for evaluating thinningalgorithms will be discussed below.

4.3.1 Connectivity preservation metric

Typically, an image for a pattern is constructed from a set of vertices (nodes) and edges(links) some of which might be connected or disconnected (Gao et al., 2010), see
Figure 4.5 for illustration. For thinning algorithms to preserve text connectivity, theymust not divide a pattern in an image into incorrect pieces. A sophisticated thinningalgorithm therefore must not delete edges of an images in order to maintain theconnectivity characteristic of Arabic script.
Basically, there are two possible cases that will affect preserving the connectivity when
producing skeletons for Arabic script. The first case is deletion of edges. For example,
considering Figure 4.6 (a), it is clear that the word in the original image has fourteen(14) vertices and seven (7) edges. In contrast, in the thinned image, which has been
manually produced in order to illustrate the first case that affects preserving theconnectivity, in Figure 4.6 (b) there are fourteen (14) vertices and six (6) edges. The
lower number of edges is because of the deletion of one edge. The second case isinsertion of a gap which results further insertion of edges and vertices. This can beseen in the case shown in Figure 4.7 where the thinned image, which was manually
produced to illustrate the second case that affects preserving the connectivity, has

67sixteen (16) vertices and eight (8) edges, compared the original image in Figure 4.5 (a)which has fourteen (14) vertices and seven (7) edges.
Graph Edit Distance (GED) is a distortion measure on graphs that determines thedifferences between two pattern images (Neuhaus and Bunke, 2007). The differences
between the two images are obtained with a number of edit operations that are required
to convert one image into another image. The authors here will utilize the concept of
GED to assess the effectiveness of a thinning algorithm in preserving the connectivityof Arabic text.
The edit operations are: insertion of edges, insertion of vertices and deletion of edges.
In order to measure GED, the minimum number of edit operations (edit distance)needed to convert the thinned image into the original image will be considered. Then,
accuracy of thinning algorithms in preserving Arabic connectivity is determined by:

𝑔−𝑒

(4.1)

𝑔

where g is the number of edges and vertices in the original image, and e is the edit
distance. The cost of each edit operation will be defined as 1. For example, if a thinningalgorithm inserted a gap, it will result in adding two vertices and delete one edge. Thus,
the edit distance cost will be three, as three operations are required to transform thethinned image into the original – two deletions of vertices and one deletion of an edge,
each having a cost of 1.

Figure 4.5. Using a graph to represent a text image: (a) text image and (b) graph for (a)Figure 4.6. One thinning example for text image in Figure 4.5(a): (a) its skeleton and(b) a graph for (a).

68

Figure 4.7. Another thinning example for text in Figure 4.5 (a): (a) its skeleton and (b) agraph for (a).

Figure 4.8. Example of dot perservation for thinning. (a) a skeleton and (b) a graph for(a)4.3.2 Dot preservation metric

In order for thinning algorithms to preserve dots of Arabic script, they must not remove
isolated vertices which present the dots of Arabic text (see Figure 4.8 which was
manually produced for illustration). Thus, to statistically measure the effectiveness ofthinning algorithms in preserving Arabic dots, the following equation is utilized:

𝑣−𝑒𝑣

where v is the number of isolated vertices in the original image, and e is the edit
distance. The cost for each edit operation will be defined to be 1.

4.3.3 Topology preservation metric

The topology preservation metric is the performance measurement utilized to assessthe degree of thinning algorithm in preserving the visual information of the original
image (Chatbri and Kameyama, 2014; Jang and Chin, 1992; Huang et al., 2003; Goyal
and Dutta, 2016a; Goyal and Dutta, 2016b). As reported by the researchers in AlShatnawi et al. (2014) and Al-shatnawi and Omar, (2014), producing spurious tails is
considered a common problem of thinning algorithm for text images. Spurious tails
can change the shape of a pattern, thereby affecting the accuracy of OCR output.

69

Accordingly, it is essential to evaluate the effectiveness of thinning algorithms in terms
of producing spurious tails.
The accuracy of thinning algorithms in preserving topology is determined by Chatbri
and Kameyama, (2014) :1 o 1     
2 c 
where o is the number of object pixels in thinned image and c is the number of counter
pixels in the thinned image. Note that in order to state that a thinning algorithm
maintains visual information of the original image, the algorithm needs to have apreserving topology value close to 1.

4.3.4 Thinning rate (unit pixel width)

It is critical to evaluate the thinning algorithms in term of thinness of the skeleton,
since one of the main principles of thinning algorithms is to ensure the peeling is asthin as possible. The thinness of the skeleton can be determined by computing thethinning rate as the following (Tarábek, 2008):

 1 tc
tr

where tc and tr refer to the number of triangles in the thinned image and in the original
image, respectively. A thinning rate of 1 indicates that the skeleton is thinned to onepixel wide, whereas a 0 value indicates that the skeleton is not thinned.

4.4 Experimental Results and Discussion
We have used performance metrics described in the previous section for evaluating the
Kocyigit thinning algorithm. For comparison purposes, we also produce results for twoother commonly used thinning algorithms for Arabic script, namely the Zhan-Suen(Zhang and Suen, 1984) thinning algorithm and the Hilditch algorithm (Hilditch,1969). Note that all the three thinning algorithms were implemented in the Java
programing language. The performance evaluation will provide us with insight ofwhich algorithm performs better for Arabic script. In particular, a good thinningalgorithm for Arabic should have a high performance accuracy in preserving
70connectivity and dots with a value of preserving topology and thinning rate both close
to 1.
Three datasets were used in this experiment. Specifically, the first dataset (Luqman etal., 2014) is the printed Arabic word dataset, which consists of 50 word images,
differing in fonts, sizes and styles. Also, two further sets of images were created forthis evaluation experiment: images of Arabic characters and images of Arabic digits
images.
In this experiment, all images from the three datasets were sent to each thinningalgorithm to obtain thinned images. Then, the output images of each thinningalgorithm were utilized to compute the quantities of each performance metric,corresponding to the original images for the datasets. Note that the performance
metrics are implemented using the Matlab programming language. Samples of theevaluation experiment from the three datasets are visually illustrated in Table I. Table
II presents the experimental data on the visual samples shown in Table 4.1.
As discussed previously, connectivity preservation is one of the most essential features
expected of thinning algorithms. From the data presented in Table 4.1, it is apparent
that the connectivity characteristic of Arabic script is almost maintained by the
Kocyigit algorithm. In particular, the Zhan-Suen algorithm and the Hilditch algorithm
failed in preserving the connectivity of sample 1 and sample 5, whereas theconnectivity is preserved by the new algorithm in both samples.
There were major differences in the preservation of the dots of Arabic script between
the three thinning algorithms. However, the Kocyigit algorithm preserves the dots ofArabic script on all samples images that contain dots, as illustrated in Table 4.1.
Furthermore, it is instructive to note that the Zhan-Suen algorithm and the Hilditch
algorithm were not able to preserve the loop shape of the sample 5 image, as shown in
Table 4.1 and Table 4.2, whereas it has been preserved by the Kocyigit algorithm.
The average scores for each metric for the three thinning algorithms are presented inTable 4.3. The first column compares the three thinning algorithms in terms of theconnectivity preservation which shows that the Kocyigit algorithm obtained thehighest accuracy (94.6%) of connectivity preservation among the other twoalgorithms.
71

The second column of Table 4.3 compares the thinning algorithms in terms ofpreservation of the dots of Arabic. The results show that there are significant
differences between the performance accuracy for dot preservation by the Zhan-Suenalgorithm, the Hilditch algorithm and the Kocyigit algorithm, 78.2 %, 85.2 % and 99.4
% respectively. Thus, it can be stated that the Kocyigit algorithm is the most effectiveat preserving the dots.
The third column of Table 4.3 lists the values for topology preservation. As mentioned
previously, a value of topology preservation close to 1 indicates that the algorithm issuccessful in preserving the shape of the original images. The results in the thirdcolumn of Table 4.3 show that the value of topology preservation is significantly betterfor the Kocyigit algorithm (0.9599), compared to the Zhan-Suen algorithm (0.9398)
and the Hilditch algorithm (0.9411).
The results of the thinning rate analysis are presented in the fourth column in Table
4.3. From this column, it clear that the thinning rate value achieved by the Kocyigit
algorithm (0.9887) is superior to the other two algorithms. This indicates that theskeletons produced by the Kocyigit algorithm is thinner than skeletons produced by
the Zhan-Suen and the Hilditch algorithms.
In summary, the evaluation experiment results show that the Kocyigit algorithm ismore effective at dealing with the challenges of thinning for Arabic script, namely,
connectivity and dots preservation. Moreover, the experimental analysis indicates thatthe skeletons of Arabic text produced by the Kocyigit algorithm are better than those
produced by the two other algorithms in terms of topology preservation and thinning
rate. Also, the evaluation experiment of thinning algorithms by utilizing the proposed
performance metrics provides a more in-depth analysis of which algorithm will
perform better for Arabic OCR systems.

72

Sample No.

Original image

Zhan-Suen

Hilditch

Sample 1

Sample 2

Sample 3

Sample 4

Sample 5

Sample 6

Sample 7

Table 4.1: Visual samples used in the evaluation

73

KocyigitImageSample 1
Sample 2
Sample 3
Sample 4
Sample 5
Sample 6
Sample 7

Connectivity Preservation
ZhanHilditch
Kocyigit
Suen

ZhanSuen

Dots Preservation

Topology Preservation
ZhanHilditch
Kocyigit
Suen

ZhanSuen

Hilditch

Kocyigit

0.909

0.909

1

0.9

0.9

1

0.958

1

1

0.941

0.941

1

1

1

0.833

Thinning rate
Hilditch

Kocyigit

10.99550.92880.9511

0.94730.92590.97661

10.9751

0.97290.98750.87110.88130.97961

1

10.96300.99830.92440.96950.9390

1

1

0

1

1

0.92470.95130.95130.9716

0.88650.9929

0.833

1

N/A

NIA

N/A

0.86140.86140.90451

0.97520.9886

0.5

0.5

0.833

0

0.333

1

0.9695

0.94340.97820.93890.90610.9859

0.8

0.8

1

N/A

N/A

N/A

0.9426

0.95900.991810.9606

0.9859

Table 4.2: comparing the three thinning algorithms on the samples

83

Algorithms
Zhan-Suen
Hilditch
Kocyigit

Connectivity
Preservation

0.844
0.837
0.946

Dot
Preservation

0.782
0.852
0.994

Topology
Preservation

0.93980.94110.9599Thinning Rate

0.95520.9266
0.9887

Table 4.3: summary of results comparing the thinning algorithms

4.5 Summary and Conclusion
An effective thinning algorithm for Arabic script is described. Furthermore, thechapter describes several objective performance metrics for assessing statistically theeffectiveness of thinning algorithms including, two new metrics for assessing topology
preservation and dots preservation. By utilizing these metrics, a more robust evaluationof the effectiveness of different thinning algorithms can be carried out. Consequently,
these metric will simplify the choice of thinning algorithms for Arabic OCR
developers.
An evaluation experiment was conducted to evaluate the performance of the Kocyigit
algorithm against other two well established thinning algorithms. In all performance
tests, the Kocyigit algorithm obtains the best results.
In the next chapter, the output of the thinning algorithm will be used for the next stageof the PATRION OCR system.

83

Chapter 5: Feature Extraction
5.1 Introduction
In the previous chapter, the skeletons for Arabic text images have been produced
by using the new thinning algorithm. In the following stage of the developed
PATRION system, which is the feature extraction stage (as shown in Figure 5.1),
the features of the skeletons will be extracted. Feature extraction is the process bywhich certain attributes of interest within a text image are obtained to be utilized
for further processing of recognizing Arabic script. Feature extraction is the
crucial phase in the development of Arabic OCR, as a well-defined feature set canfacilitate recognition and increase accuracy performance (Lawgali, 2015).
In order to recognize Arabic script, our new approach develops a feature extraction
method that transforms the word into a set of features that are utilized to recognise
the Arabic word. Since the input for the PATRION OCR system is a text image ofa page of printed Arabic, several pre-processing steps are required to be appliedprior to or within feature extraction. These steps are baseline determination andword segmentation.
The remainder of this chapter describes our approach to the feature extraction
stage. It formally states the rationale behind using this approach. Then, it explainsin detail the feature extraction method that has been used in this work with therequired pre-processing steps, baseline determination and word segmentation.

84

Figure 5.1: Block diagram of the PATRION OCR system
Note: The shaded area shows the scope of the current chapter ‘Feature Extraction’.

5.2 Why This Approach?
The human reading task is a cognitive process nearly equivalent to OCR thatinvolves detecting characters and classifying them from among enormous
possibilities (Rashid, 2014). Humans can efficiently and accurately recognize text
in different fonts and sizes. The accuracy of human recognition of text can be
attributed to several cognitive processes, involving reading and writing strategies.
Generally, it is claimed that humans rely on their existing knowledge in order toaccomplish a reading task (Pi et al., 2008). For instance, people can recognise
identical words or characters based on the surrounding context. A good example
for native Arabic readers is the text illustrated in Figure 5.2 which has a numberof identical characters (non-dotted characters) that have different pronunciations
but can be identified based on the context. Another example from English is that85

Figure 5.2: An Arabic text example that has identical characters but different
pronunciation

people can readily recognize the correct form for the letter ‘1’ in the following
three strings based on the surrounding context: “l234”, “lntelligence” and “left”.
Therefore, humans’ existing knowledge is essential for the reading task.
Researchers in the field of cognitive psychology have presented several theories
to explain the principal cognitive processes in human recognition. For example,
several studies such as Bobik and Sayre, (1963) have shown that humanrecognition of a character is directly related to understanding the general idea ofthe character, the basic elements that define it, irrespective of color and size. Somecognitive scientists argue that the visual system is sensitive to the way thecharacters are physically produced; thus the rules that are followed in order to writea character affects the perception of it (Kandel et al., 2000; Tse and Cavanagh,2000). According to this viewpoint, humans extract writing information of thecharacters from an image by mentally tracing over them in their minds as if they
were writing them with a pen.
Also, the most used strategy for developing handwriting skills in primary schools
is the tracing handwriting strategy (Vinter and Chartrel, 2010). This is a practicethat comprises tracing characters or words, which have been printed using dots, bya pen, as shown in Figure 5.3. The worksheet in Figure 5.3 is an example ofhandwriting exercise that have been used in teaching children on handwriting bydemonstrating the action of tracing movements which the learners should follow
in order to produce a character or a word in Arabic and English.

86

Figure 5.3: An example of a worksheet that adopts the tracing handwriting strategy, from
(Garcia, 2005).

The proposed feature extraction method, to some extent, follows the above insightsfrom cognitive science in order to design a robust Arabic OCR system.
5.3 New Feature Extraction Method
The feature extraction phase processes the skeleton text images produced by thethinning algorithm that was described in the previous chapter. As mentioned inliterature review in section 2.2 Arabic scripts have some dotted characters which
could contain one, two or three dots. Moreover, these dots could be the only featurethat could be used to differentiate between dotted characters. Recall that Arabic
script was not originally dotted: referring to the literature review in Chapter 2,
some issues have been raised when recognizing dots in Arabic script. For example,
dots in Arabic text may characterised as noise. In order to help recognition, preprocessing techniques, such as a noise removal algorithm may remove the dots ofArabic text. Also, applying thinning algorithm on Arabic text images may affectthe preserving of the dots in Arabic text. Due to these issues, researchers in Arabic
OCR have extracted the dots information before applying pre-processing methods.
However, in some Arabic fonts, two dots are joined together and printed as one
stroke which is similar to the diacritical mark called Fat-hah. As a result, it isdifficult to isolate connected dots and to distinguish between the dots and the Fathah diacritical mark. Thus, the feature extraction process will only deal with themain part of Arabic script. That is, it will be assumed that all Arabic words in the87text images are non-dotted, as dots will be recovered in the post-processing stage.
Moreover, ignoring recognising dots in this stage will result in reducing thenumber of character models needed in the classification stage as will be discussed
in section 7.2.1.
Referring to the literature review, most studies in previously developing analyticalArabic OCR systems perform the character segmentation phase prior to the feature
extraction phase. However, in this work, the feature extraction stage does not
require performing character segmentation in advance.
The proposed method is based on feature extraction methods using direction codes,
such as the Freeman chain code (Freeman, 1961) which provides information
about the structure of an object based on its boundary. It follows the object’s
boundary from a fixed starting point and continues moving in a clockwise or
anticlockwise direction until it reaches the starting point. For more details of theFreeman chain code, refer to Nixon and Aguado, (2008).
A study by Kocyigit (2012) proposes a feature extraction method based on
direction codes for tracing English characters’ skeletons in order to extract thedirection movement features used to follow the character’s skeleton shape. Thismethod has been adopted here for extracting features from Arabic script with somemodifications (described below) that control the tracing movements in order toextract feature from cursive printed text, since the method was only investigatedfor English script.

Figure 5.4. An example of how an Arabic letter “Laam” is traced
Note: the black squares are the unprocessed pixels of the character image
and the gray squares are the pixels that have already been processed.

88

In this work, the proposed algorithm extracts the direction movements asfeatures from Arabic words by tracing their skeletons (thinned images). This
resembles the way a human might write a word or a character with a pen using thehandwriting development strategy, which is a tracing strategy as discussed
previously. When individuals trace a word or a character, they place the pen at a
certain point and move in different directions in order to produce the word or thecharacter. This can be illustrated by assuming the start point of the Arabic letter“Laam” )‫ )ل‬is the right top corner of the letter. In order to write the Arabic letter,
we begin from the start point and move forward in a south direction, then turn left
and move forward to the west. After that, we move forward in the north direction;
see Figure 5.4 for illustration.

Figure 5.5. An example of an Arabic text image conveyed into NetLogo
Note: (a) the original thinned text image, (b) the 2D array for a part of (a) and(c) the text image imported into NetLogo.

89

This can be reproduced by using an agent-based model implemented in NetLogo
that uses turtle movements controlled from a first-person perspective. To this aim,several pre-processing steps are applied to the text images in order to prepare themfor feature extraction. Firstly, the thinned text image to be recognised is imported
into the system as a 2D array of 1 (black patches) and 0 (white patches) values tobe read in NetLogo, as shown in Figure 5.5. Then, the feature extraction method
is broken into three sub-stages: baseline determination; word segmentation andextraction of features, as shown in Figure 5.6.

Figure 5.6. Block diagram of feature extraction method

5.3.3 Baseline determination

The proposed method relies on the baselines of Arabic text. Thus, the baseline of
Arabic text needs to be detected. The baseline of Arabic script is a horizontal line
through which Arabic characters are joined. It usually has the maximal amount of
black pixels, especially for printed Arabic text (although not for handwritten text
images in which the writer is moving the pen above and below the baseline). In
the literature, there a number of baseline determination algorithms (see Chapter 2,
section 2.3.1). For this work, the method proposed by Kocyigit (2012) has beenused due to its effectiveness in the feature extraction stage (as evidenced by theaccuracy performance evaluation detailed below). The baselines of text images are
extracted using a thresholding algorithm developed in the NetLogo
implementation. The steps of the baseline determination algorithm are as follows
in the flowchart provided in Figure 5.7. The threshold value 𝑇 used in thealgorithm is changeable (from 1 to 10) depending on the text density of the lines.
The algorithm calculates the ratio of the counts of black patches on adjacent rows
and determines that a new line of text starts when this ratio exceeds a selected
threshold value. To always ensure non-zero counts, a black border is placed aroundthe 2D array of the text image.
90

In this work, it is assumed that the input Arabic text images have 0˚ skew, as skew
correction is beyond the scope of this research. Figure 5.8 shows an example ofArabic text images after determining the baselines, which are green colored lines
shown through the text, by the baseline determination algorithm.

Figure 5.7: Flowchart of the feature baseline determination algorithm.

Figure 5.8. Screenshot from the NetLogo model that was developed for baseline determination

915.3.4 Word segmentation

Determining where each word is in a text image is required in order to segment aword into characters. In this work, the white space (white patches) between eachword is used for word segmentation. In particular, the tracing agent records thefinish point for each word (connected component) after completing the movement
over the word (see step 9 in Figure 5.9). When the tracing agent locates the finish
point and comes to the start point of the next word, the white space between thestart point and finish point is marked as sub-word space (segmenting each text line
into sub-words, since an Arabic word may have more than one connectedcomponents (sub-words) as mentioned in chapter 2).

5.3.5 Extraction of features

This section explains how the features of Arabic text images are extracted. Figure
5.9 states the algorithm’s flowchart for determining how the tracing agent moves
over the Arabic text. After determining the baselines in the text image, the tracing
agent in the NetLogo environment is placed at the right bottom of the lowest
baseline of the Arabic text images. It then visits each baseline from bottom to topof the image moving across the baseline from right to left (see steps 1, 2 and 3 inFigure 5.9). We choose the starting point at the right bottom on account of the factthat Arabic text is written from right to left and a pen is placed on the right bottomof a baseline when writing Arabic text.
While the tracing agent is moving over the selected row, the agent marks the first
black patch on the row as the start point of a word (refer to step 4). Then, thetracing agent moves onto the black neighbouring patches using four directions:south; north; west; and east, according to the direction of the patch (see steps 5 and
6). Due to the fact that Arabic script has some curved characters, the algorithm
will treat the curved characters as diagonally connected pixels. The agent checks
if the pixels of the curved parts of the characters create a corner and changes the
direction. If not, the agent accepts these pixels as the same direction which theagent is already moving in.

92

Figure 5.9: Flowchart of feature extraction algorithm
93

Figure 5.10: Example of three branch points that occur in the Arabic word(“‫)”الكل‬Note: When the agent finds the branch points (the first and the second green pixels), the agent
moves first to the north direction (the blue pixels), then to west direction (the red pixels).
While the agent finds the branch point (the third green pixel), the agent moves first to thenorth direction (the blue pixels), then to the south direction (the red pixels).

During the tracing process, the tracing agent may face a branch point which
presents more than one direction for the next step of the agent. If the agent faces abranch point, it records all options and the branch point. Then it follows all theoptions one by one in order with priority given to move first to the north, then to
the south, and finally to the west (refer to decision 2 and 3 and steps 7 to 12 in
Figure 5.9). For example if there are two directions on the next step of the agent
where one of them is to the north and the other is to the west, the agent first follows
the north direction. When it has completed the movement for this option, it returns
to the branch point and follows the west direction. We set these steps due to thefact that a branch point in an Arabic word has two or three directions – north, south
and west; see Figure 5.10 for illustration. Therefore, it was decided to control theorder the agent moves over the Arabic word, as this is a valuable step for the nextstage of the PATRION OCR which will be discussed in the next chapter.
Figure 5.11 displays the tracing process and the features extracted from an Arabic
word. The initials “N”, “S”, “E”, “W” in Figure 11 refer to the direction
movements which are north, south, east and west, respectively and the symbol “*”refers to the branch point. The red lines in the figure illustrate how the tracing
process proceeds. In Figure 5.12, a screenshot from the NetLogo model is shown
while feature extraction is being performed on an Arabic text image. It is obviousthat the feature string which is extracted by the feature extraction method isirreversible. Thus, it is not possible to recover the original text image by using the94

produced feature strings. However, this does not affect the performance of the
OCR system which will be discussed in section 7.2.1.

Text Image Tracing
Features Extracted
Feature extracted for the first sub-word

Feature extracted for the next sub-word

Figure 5.11: Tracing example for an Arabic word with features extracted in NetLogo
Note: The tracing is performed from right to left. The red lines illustrate the progress as the
tracing process proceeds.

95

Figure 5.12: Screenshot of the NetLogo model extracting features from an Arabic text
image
Note: the extracting features are shown in the output box below.

5.4 Experimental Evaluation
In this section, three experimental evaluations are conducted in order to assess thebaseline algorithm, word segmentation method and the feature extraction methods.
The KAFD dataset, which was mentioned in Chapter 3, has been used in theseexperimental evaluations.

5.4.1 Baseline determination method evaluation experiment

The baseline determination algorithm is evaluated on Arabic printed text images,
which were selected from KAFD dataset, at 300 dpi and with 24 pitch size multiple
font types, namely AdvertisingBold, Simplified Arabic and Traditional Arabic.
The text images contain 105 baselines. The accuracy of the algorithm relies on
the threshold value 𝑇. For the text image samples in this evaluation, we manually
adjusted the 𝑇 value for accurate baseline determination. We found that 𝑇 values
between 5 and 7 were the most accurate threshold values in the test samples. Figure5.13 shows how the algorithm has determined the baselines when the thresholdvalue was adjusted to 7 whereas, Figure 5.14 shows the output of the baseline
algorithm when selecting a threshold value of 3. The algorithm obtained 100%96

accuracy when selecting 7 as a threshold value. Table 5.1 shows the evaluation
results which were obtained through the evaluation experiment on the sample text
images.

Figure 5.13: Screenshot from NetLogo model showing example of correct baseline determination
using 7 as a threshold value

Figure 5.14: Screenshot from NetLogo model showing example of incorrect baseline
determination using 3 as a threshold value

97

TotalNumber of
Baselines

Font Type

AdvertisingBold
Simplified Arabic
Traditional Arabic
Total

39
34
32
105

Number of
Baselines
Correctly
Determined
39
34
32
105

Accuracy
100%
100%
100%
100%

Table 5.1: Results of baseline determination algorithm on sample test text images on different
Arabic fonts using threshold values between 5 and 7 based on text images

5.4.2 Word segmentation method evaluation experiment

In this work, the word segmentation method attempts to segment Arabic text in theimages into sub-words. Thus, to evaluate the word segmentation method, theground truth of the dataset has been modified by adding a space between each subword in the test sample as only word spaces (spaces between words) are available
in the ground truth of the dataset. The word segmentation method is evaluated by
the following two measures:
𝑅𝑒𝑐𝑎𝑙𝑙 = 100 × 𝑎/(𝑎 + 𝑐)

(5.1)

𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 100 × 𝑎/(𝑎 + 𝑏)

(5.2)

where 𝑎 is correct insertion of space, 𝑏 is spurious space insertion and 𝑐 is missed
space. A perfect word segmentation will have recall and precision of 100%. Using
text images that contain 100 Arabic words, the method produced a recall of 100%and a precision of 96.99%. It seems that the algorithm suffers from inserting
spurious spaces (over segmentation). This issue occurred as a result of the thinningalgorithm producing disconnections (not maintaining the connectivity) throughArabic words.

5.4.3 Feature extraction method evaluation experiment

To evaluate the feature extraction method, a ground truth of directional features of
the images has been generated in order to be able to make a comparison of thecorrect output string and the generated extracted features output string. The
evaluation in this experiment is based on the edit distance between the extracted98

features string and the ground truth string. The edit distance here is the minimumtransformation sequence that converts the extracted features string into the groundtruth string. The Accuracy A is defined as:
𝐴=

𝑓−𝑒
𝑓

× 100

(5.3)

where e is the edit distance, and f is the number of features in the ground truth
string. The cost for each edit operation is defined as 1. For example, Figure 5.15
illustrates the edit distance between the feature string (b), which was extracted
from the thinned image (a) and the ground truth string (c) is 3 because threeoperations are required to convert the feature string (b) to the ground truth string(c) which are adding one symbol “*” (branch point) and adding two direction
strings, “W”, and “S”, that are written in red colour.
The average accuracy of the feature extraction technique was found to be 98.07%.
It is critical to note that most of the errors produced by the method are related tothe thinning algorithm. That is, when the thinning algorithm failed in persevering
connectivity (disconnection), the feature extraction makes an error in extracting
the directional features; see Figure 5.16 for illustration. Another problem that arose
is due the loss of visual information of the original text images that have been
produced by the thinning algorithm. In fact this issue occurs mostly inAdvertisingBold font with loop characters, as shown in Figure 5.17.
(a)(b)
NWSN*WN* – NWN*WN* – N – ESWNWN*– N(C)
NWSN*WN* – NWN*WN* – N – WSESWN*WN*– N
Figure 5.15: An example of edit distance between two feature strings
Note: (a) A thinned Arabic word, (b) the extracted feature string from (a) and (c) the ground truth
string for (a) with the edit operations highlighted in red colour

99

Table 5.2 summarizes the errors that occurred in the feature extraction method
according to different error types which have been produced by the thinningalgorithm. The data in Table 5.2 shows that most of the errors in the test samples
occurred in text images that involved the AdvertisingBold font. The high numberof errors that occurred in text images of AdvertisingBold font is likely due to theinefficiency of the thinning algorithm (discussed in chapter 4) in thinning boldstyle text.

100

(a)

(b)

(c)

(d)
(e)
Figure 5.16. Example of the effect of disconnection errors (produced by thinning algorithm) on
the feature extraction algorithm
Note: (a) An original Arabic word image, (b) the thinned image of (a), (c) the sub-word in which the disconnection
occurred (highlighted in a circle), (d) the extracted feature string from (c) by the feature extraction algorithm and(e) the ground truth for (c).

Figure 5.17. Example of the effect of loss of visual information (caused by thinning algorithm) on
the feature extraction algorithm
Note: (a) An original Arabic text image (the patterns in which the error occurred are highlighted in squares), (b)the thinned image of (a), (c) the extracted feature string from the highlighted characters in (b), and (d) the groundtruth for the highlighted characters in (b).

101

Error Category

Disconnection

Loss of visual
Information

Total Errors (%)

AdvertisingBold5

10

15 (53.5%)

Simplified Arabic

2

4

6 (21.4%)

Traditional
Arabic437 (25%)

Total Errors (%)

11 (39.2%)

17 (60.7%)

28

Font

Table 5.2: Error analysis according to different fonts and error types

5.5 Summary and Discussion
In this chapter, a new technique, based on a cognitive insight, for extracting
features from non-dotted Arabic text images has been proposed and developed
using an agent-based NetLogo model. Some pre-processing steps are applied toprepare the text images for feature extraction, such as the baseline determinationand the word segmentation.
The feature extraction method transforms an Arabic word into a string of direction
movements, which are representative of how the agent in the model traces Arabic
words, combined with the branch points. The average performance accuracy of thefeature extraction algorithm on a sample of 100 images is 98.07%.
The following two chapters use these extracted features in order to design a system
for recognising Arabic text.

102Chapter 6: Character Segmentation
6.1 Introduction
Chapter 5 presents a method for extracting direction code features from Arabic
text images. The next stage in this work for the developed PATRION system isthe character segmentation which differs from a typical Arabic OCR system in that
here the character segmentation proceeds subsequently to the feature extraction
stage, as shown in Figure 6.1. Character segmentation is the process of segmenting
a word into its characters. Referring to the literature in chapter 2, it is stated thatcharacter segmentation is a critical step as most recognition errors are produced asa result of character segmentation (Al-Badr and Mahmoud, 1995; Tamen andDrias, 2010).
In the literature, there are a number of image-level algorithms for segmenting
Arabic words into characters; for a comprehensive survey in character
segmentation for Arabic script, refer to Zeki et al. (2011). Although many studies

Figure 6.1. Block diagram of the PATRION OCR system
Note: The shaded area shows the scope of the current chapter ‘Character Segmentation’.

103

have provided different character segmentation algorithms, there are no accuratecharacter segmentation algorithms (Gouda and Rashwan, 2004; Zeki et al., 2011).
A number of the algorithms face various segmentation problems, such as oversegmentation and under-segmentation. A major drawback of applying suchcharacter segmentation techniques for Arabic text is that they fail in segmenting
overlapping characters. Overlapping characters in Arabic script cause difficulties
for a number of existing character segmentation algorithms (see Figure 6.2).
Some studies overcome the challenges of character segmentation by developing
Arabic OCR systems based on a free-segmentation or holistic approach which
recognize words or sub-words as a whole unit with no segmentation. However,such systems can only recognize Arabic words that appear in the lexicon because
these systems are lexicon based systems. This provides the motivation fordeveloping a novel character segmentation method for the Arabic OCR system.
Doing this enables the delivery of a robust Arabic OCR system (as evidenced by
the results provided in Chapter 8).

Figure 6.2: Examples of overlapping characters highlighted in Arabic words in
different fontsThis chapter firstly discuss the features of Arabic script that are useful when
designing character segmentation methods. Then, section 6.3 presents a new
method for segmenting Arabic words into characters. In section 6.4, an evaluation
experiment is conducted on the proposed character segmentation method.
6.2 Arabic script features used for designing the character segmentation
technique
The challenge of character segmentation task is undoubtedly due to thecharacteristics of Arabic script, as discussed in chapter 2 and discussed again
104

above. As a result, the special characteristics of written Arabic script should not
be ignored in order to design a robust character segmentation method for Arabic
script.
One feature of Arabic script that can be exploited for designing a character
segmentation technique is the baseline. As already discussed in chapter 2, thebaseline is the horizontal line through which Arabic characters are joined together.
That is, when an Arabic word is written, the baseline is used to join the characters
together in order to produce the word. There is a part of the baseline which is
between each of the connected characters called the junction line. The junction
line is used by different image processing algorithms to segment Arabic words into
characters. However, this feature may not work well in image-level algorithms as
the length of the junction line varies in different fonts being often short in many
printed Arabic fonts. Also, character segmentation approaches based on thejunction line suffer in segmenting overlapping characters in Arabic text (Gouda
and Rashwan, 2004).
Another feature of Arabic script that can be utilized for character segmentation isthe branch point which occurs at the beginning of a connected Arabic character ina word and after a junction line. The branch point as described in chapter 5 is thepoint where there is more than one direction to follow in the process of executing
the tracing algorithm.
According to the two above characteristics which are the junction line and thebranch point, there is usually a character segmentation point in a word if there is abranch point after a junction line. Figure 6.3 illustrates the two selected features of
Arabic script for detecting the character segmentation point. Recall that the Arabic
language has some characters which divide one word into one or more pieces ofwords called sub-words. These characters are not connected with the succeeding
characters and they can be only linked from their right sides. Therefore, when theyoccur in the middle of an Arabic word, the word is divided into sub-words byadding a space. Figure 6.3 (a) shows an Arabic word comprising three sub-words;
two are isolated characters and the third is a connected sub-word of five characters.
Figure 6.3 (b) and (c) shows that the junction line and the branch point are appear
only in a connected sub-word, not in sub-words with isolated characters.
105

(a)

(b)

(c)

Figure 6.3: Junction line and branch point features of an Arabic word

6.3 New character segmentation approach
The new approach for character segmentation is applied in order to overcome theaforementioned problems. The extracted features string described in the previous
chapter is used for performing the character segmentation task. Recall that theextracted features from Arabic text is comprised of four directions represented as
symbols in a text string: south (‘S’); north (‘N’); west (‘W’); east (‘E’) and abranch point symbol (“*”).
The feature extraction algorithm in chapter 5 extracts the west direction as the last
direction feature after detecting a branch point, since this confirms that the tracing
agent does not move to a succeeding character until it extracts the whole featuresof the preceding character in a word. That is, it does not move to the next characterin the connected word until it finishes tracing the character being processed.
The aim of the character segmentation technique in this work is to identify thesegmentation point in the extracted features string in order to break the connectedcharacters in a connected word or a connected sub-word.
After investigation of the direction features extracted from printed Arabic script,
we noticed that the west ‘W’ direction feature symbol commonly represents thejunction line (and does not represent a part of a character) when it is followed bya branch point (the star ‘*’ in the extracted features string). Therefore, there should
be a character segmentation point between the ‘W’ and ‘*’ symbols.

106Figure 6.4. A sample of applying character segmentation on an Arabic word
Note: (a) An Arabic word with two sub-words, (b) the feature extraction string produced from (a),(c) segmentation points in the word and (d) the feature extraction string (b) after applying thecharacter segmentation technique.

Simply, in order to segment an Arabic word into characters, the new approach
inserts a slash sign ‘/’ (to indicate a segment break) between the ‘W’ and ‘*’
symbols into the output of the feature extraction algorithm that was discussed inchapter 5. Figure 6.4 shows a sample of extracted feature string (b) that was
produced, using the feature extraction method in chapter 5, from the Arabic word
shown in (a). The Arabic word has two sub-words: one consists of four connectedcharacters which should be represented as four symbols in the text string whensegmented; and one sub-word of an isolated character which should not be
segmented. Figure 6.4 (c) shows the positions (segmentation points) where thesub-word should be segmented. Figure 6.4 (c) shows the feature extraction string(b) after applying the character segmentation technique.
6.4 Experimental Results and Discussion
Comparing the performance of character segmentation methods is a challenging
task due to the different experimental protocols, different testing datasets anddifferent performance measures. Besides most studies in Arabic text recognition
have only provided the overall performance accuracy of their systems. In this107

work, an experiment was designed in order to evaluate the performance of thenovel character segmentation method.
The character segmentation method is evaluated on the dataset of 100 Arabic word
images which were used in chapter 5. The text in the testing dataset comprises
different features of Arabic script that may contribute to the challenges of Arabic
character segmentation. Table 6.1 shows basic statistics of the test images sample
in terms of Arabic script characteristics.
The character segmentation method is evaluated by the following two performancemeasures:
𝑅𝑒𝑐𝑎𝑙𝑙 = 100 × 𝑠/(𝑠 + 𝑚)

(6.1)

𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 100 × 𝑠/(𝑠 + 𝑏)

(6.2)

where 𝑠 is correct insertion of the slash symbol ‘/’, 𝑏 is spurious slash sign insertionand 𝑚 is missed slash sign. A perfect character segmentation will have recall andprecision of 100%. The method produced a recall of 84.2% and a precision of
77.2%. The prime causes of the segmentation errors are due to specific features of
Arabic script and the errors which have been delivered from the previous stages.
Table 6.2 shows the segmentation error rate percentage of the method in terms of
the features of Arabic script.
During the evaluation experiment, it was observed that there are a number of reoccurring situations where usually the character segmentation method did not
perform well or produced segmentation errors. For instance, an over segmentation
problem occurs on segmenting the Arabic character (Seen “‫)”س‬. The method oversegmented the (Seen) letter into three segments because it consists of two junctionlines and two branches.
FeaturesWord
Sub-word
Sub-word with isolated character
Overlapping character
Loop character
End-form character

Count of items
100
129
28
89
180
101

Table 6.1: Testing dataset statistics
108

Features

Error rate

Overlapping character segmentation
End-form character segmentation
Loop character segmentation

4.5%
14.8%
6.9%

Table 6.2. Segmentation Error Rate Percentage

Furthermore, as stated in Table 6.2, segmenting end-form characters has thehighest segmentation error rate which is 14.8%. This high error rate is related tothree Arabic characters if they are found at the end of words or sub-words (the end
form shape). These characters are Alef “‫”ـا‬, Haa “‫ ”ـه‬and Yaa “‫”ـى‬. The method
did not segment these characters (under-segmentation) as there is no branch point
after the junction line. Such characters will be dealt with at the post-processing
stage in Chapter 8 rather than be corrected at this stage.

Figure 6.5. Sample of segmenting overlapping characters
Note: (a) An Arabic word containing overlapping characters (Traditional Arabic Font); (b) the
sub-words of the word shown in (a); (c) the feature extraction string produced from each subword shown in (b); (d) the segmented feature extraction string after applying the character
segmentation technique which are coloured corresponding to the way characters are coloured in(a).

The error rate percentage of the character segmentation method in relation to loop
characters is about 7%, as shown in Table 6.2. The segmentation errors insegmenting loop characters are due to errors which have been produced in the two
previous stages. In particular, when the thinning algorithm (discussed in Chapter
1094) has produced a disconnection through a loop character’s form, a branch point
after a junction line existed in the main form of the character. The feature
extraction algorithm (discussed in Chapter 5) thus has extracted these features
which are the west ‘W’ direction feature and the branch point ‘*’. As a result, thecharacter segmentation method over segmented the character into more than one
segment.
On the other hand, the segmentation method succeeds in dealing with the problems
that arise when segmenting overlapping characters. For example, Figure 6.5 shows
how overlapping characters in an Arabic word have been segmented successfullyby the character segmentation method. The character segmentation produced only
an error rate of 4.5% for segmenting overlapping characters. In fact, this error rate
is related only with the Arabic ligature (‫ )ال‬which is a combination of two
overlapping characters: Lam (‫ )ل‬and Alef (‫)ا‬. The algorithm did not segment such
ligatures, as there were no identified segmentation points. We overcome this issue
by dealing with such ligatures as one character, so segmenting the ligature into
characters is not required.
6.5 Summary and Discussion
In this chapter, a new character segmentation technique for segmenting connectedArabic words into characters has been provided. The character segmentation
method uses the extracted features string, which have been obtained as a result of
the feature extraction process described in Chapter 5, for performing thesegmentation process.
The character segmentation method segments a connected word into characters byidentifying the segmentation point in the extracted feature string. The
segmentation point is determined based on two features of Arabic script: thejunction line and the branch point. The method has been tested on a sample of 100
Arabic words images and has produced a recall of 84.2% and a precision of 77.2%.
The character segmentation method leads to under-segmentation in some end-formcharacters. However, the method has successfully segmented overlapping
characters.

110

In the following chapter, the segmented feature strings will be used for recognising
Arabic text.

111

Chapter 7: Classification Using PPM
7.1 Chapter Introduction
Chapter 4 presents a method for extracting feature strings from printed Arabic text
images. Then, chapter 5 describes a method that uses the features in order tosegment Arabic words into characters. In this chapter, the segmented featurestrings will be used for recognising Arabic text. In other words, the following stageof the developed PATRION system, which is the classification stage (as shown in
Figure 7.1), is responsible for classifying the feature strings into the best characterclass in order to complete the recognition task.
In the literature, a number of classifiers have been used for Arabic OCR. However,no prior study exists on the use of compression based models as a classifier in
Arabic text recognition. Therefore, in this work a compression based method has
been applied for the first time as a classifier for the text recognition. Moreover,since the aim of the classification stage (implemented in the PATRION OCR
system) in this work is to distinguish (classify) the feature strings (extracted inchapter 5). PPM, which is discussed in the review chapter, was chosen to be
applied as a classifier.
The following sections of this chapter describe the use of the PPM compressionbased method for text recognition (classification). Also, constructing PPM
classifiers and experimental results for PPM model classification are reported. In
particular, section 7.2 discusses the implementation of the PPM classifier. We thendiscuss experimental results using the PPM classifier in section 7.3. A summaryand discussion of this chapter is presented in section 7.4.

112

Figure 7.1: Block diagram of the PATRION OCR system
Note: The shaded area shows the scope of the current chapter ‘Classification using PPM’.

7.2 Implementation of PPM Classifier
Our approach is to recognise Arabic characters by the use of the PPM method thatclassifies the feature strings obtained from the previous chapter. The PPM
classification approach in the PATRION OCR system consists of two stages: atraining stage and a testing/recognition stage. During the training stage, charactermodels are constructed using a pre-segmented character image dataset. Order 5
PPMD character models, which are implemented by the Tawa Toolkit, describedin (Teahan, 2018), have been used for constructing the character models. During
the testing stage, the recognition of both Arabic text and pre-segmented Arabic
character images were analysed by the text classification method which is also
provided by the toolkit. In the following sections, the two stages will be discussed
in detail.

113

7.2.1 Stage I: Training stage

For constructing a PPM classifier, a training dataset consisting of pre-segmented
printed Arabic characters is required as the main idea is to train PPM for isolated
Arabic characters. The literature suggests a comprehensive isolated printed Arabic
characters dataset named PAC-NFB which is provided by Alkholy (2016). The
dataset is freely available and comprises character images of 10 different font
types, 10 pitch sized and four styles (normal, italic, bold, bold italic), with 300 dot
per inch (dpi). The dataset contains 4080 character images for each font withdifferent variations. For this study, four various font types have been selected fromthe PAC-NFB dataset; namely, Arabic Transparent, AdvertisingBold, Simplified
Arabic and Traditional Arabic. For each font, 12 and 24 pitch sizes have been
selected. Additionally, normal and italic font styles for each font pitch size havebeen used.
Since this work only considers the main part of the Arabic text (non-dotted text),
Arabic characters that share an identical visual shape have been joined in one
group. This leads to a reduction of the number of character models as each PPM
model is formed from the grouped characters in each group.
Table 7.1 shows the joint group character classes which consist of the charactersin different forms (isolated, start, middle and end) that have identical shapes withthe only characteristic that can be used to differentiate between them being thenumber, location and appearance of dots. If we consider all characters in the Arabicalphabet and LAM ALEF and HAMZA in the four different forms which are
isolated, start, middle and end forms, we end up with 103 characters (as discussed
in chapter 2) that need to be used for training (AbdelRaouf, 2012). However, bygrouping the identical characters which differ in the number, location andappearance of dots into one class (such as characters like ‫ب‬, ‫ت‬, and ‫ ث‬which havebeen grouped into one class), we will have only 20 classes. Therefore, only 20classes of characters have to be considered for training. This means that the total
number of training models will be 20 instead of 103.

114

Table 7.1: Combining Arabic characters in character classes, grouped according to theirmain type of shape

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Character namein English
ALEF
BEH
HAH
DAL
REH
SEEN
SAD
TAH
AIN
FEH
QAF
KAF
LAM
MEEM

15

NOON

16
17
18
19
20

HEH
WAW
YEH
LAM ALEF
HAMZAClass number

Class
Character

Characters grouped together into the same
class

‫ا‬
‫ب‬
‫ح‬
‫د‬
‫ر‬
‫س‬
‫ص‬
‫ط‬
‫ع‬
‫ف‬
‫ق‬
‫ك‬
‫ل‬
‫م‬
‫ن‬
‫ه‬
‫و‬
‫ي‬
‫ال‬
‫ء‬

‫ا ـا‬‫ب بـ ـبـ ـب ت تـ ـتـ ـت ث ثـ ـثـ ـث ـب لـ ـلـ ـنـ نـ ـيـ يـ‬‫ح ـح ـحـ حـ خ ـخ ـخـ خـ ج ـج ـجـ جـ‬‫د ـد ذ ـذ‬‫ر ـر زـز‬‫س سـ ـسـ ـس ش ـش ـشـ شـ‬‫ص صـ ـصـ ـص ض ضـ ـضـ ـض‬‫ط طـ ـطـ ـط‬‫ع عـ ـعـ ـع‬‫ف فـ ـفـ ـف ـقـ قـ‬‫ق ـق‬‫ك كـ ـكـ ـك‬‫ل ـل‬‫م مـ ـمـ ـم‬‫ن ـن‬‫ه هـ ـهـ ـه‬‫و ـو‬‫ي ـي‬‫ال ـال‬‫ء‬Considering the table above, for each specific font, 60 character images of eachcharacter class have been selected from the PAC-NFB with the intention to cover
all font styles and sizes that are considered in this study. 70% of the selected
images were used as a training set for constructing the PPM model and 30% wereused for testing in stage II which will be discussed in section 7.4. Tables 7.2 and7.3 show an example of training data used for stage I using the character classesof the Traditional Arabic font.
The PATRION OCR system in this work uses characters (isolated characters) as
models. That is, each character model is constructed by passing the training set ofa specific class from a specific font through the thinning stage and feature
extraction stage, explained in Chapters 4 and 5 respectively, then the output of thefeature extraction which is the feature strings are used to train the corresponding
PPM model. For instance, the character model of the Traditional Arabic font forclass 1 is trained on all characters that appear in class 1 from different font styles
and pitch sizes. This results in having 20 character models for each font. For
115

illustration, Table 7.4 shows three examples of the feature strings for four different
character classes. In these examples, only ten character images have been used foreach of the four classes. The table shows that there are only three distinct featurestrings for each character class.
Class
Class
number nameCharacter image

Class
number

Class
name

1

ALEF

11

QAF

2

BEH

12

KAF

3

HAH

13

LAM

4

DAL

14

MEEM

5

REH

15

NOON

6

SEEN

16

HEH

7

SAD

17

WAW

8

TAH

18

YEH

Table 7.2: Training data for Stage I
Note: A single font (Traditional Arabic font) is shown.

Continued onto next page

116

Character image

9

AIN

19

LAM
ALEF

10

FEH

20

HAMZA

Table 7.3: Continued. Training data for stage I
Note: A single font (Traditional Arabic font) is shown.

Class nameFeature strings
SSENWWEN*
SSENW*WSN*SSENW*WEN*ESS*SN*NESEWNWN*NESEWNWN
WN*
NWN*
WEN*
NWSWN*
NWSN
NWN*

HAMZA

LAM ALEF

BEH

LAM

Table 7.4: Examples of feature strings for character classes in Tables 7.2 and 7.3
Note: The feature strings were extracted by running the algorithm discussed in chapter 5 on asample of the Traditional Arabic font dataset.

The feature string produced by the feature extraction method is irreversible, as
stated previously. Moreover, the feature algorithm uses only four directions: north;east; west; and south. Consequently, an issue might occur when there is a case ofan edge that goes roughly north-west, south-west, north-east and north-west or
even goes to secondary intermediate directions such as NNE, ENE, ESE, SSE,
SSW, WSW, WNW and NNW. In particular, the mapping from skeleton images
to feature strings can be at risk of labelling similar images as being different. In
order to show that these problems are not major issues for the proposed OCR
system, we compare the feature strings that have been extracted from twenty
character images from all the twenty character classes, mentioned above, using
117

edit distance which was discussed in section 5.4.3. Note that only Arabic
characters in an isolated form have been considered in this comparison. The
character images have been selected from the PAC-NFB dataset of Simplified
Arabic font. The high numbers of edit distance mean that the feature string is very
different. Table 7.5 shows the confusion matrix using edit distance. Table 7.5
shows that only some characters that are visually similar to each other having lessedit distance, such as the similarity between the two letters ‫ ل‬and ‫ ن‬and between
the letters ‫ك‬, ‫ د‬and ‫ب‬.
ActualShape 1
class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

‫ا‬
‫ب‬
‫ح‬
‫د‬
‫ر‬
‫س‬
‫ص‬
‫ط‬
‫ع‬
‫ف‬
‫ق‬
‫ك‬
‫ل‬
‫م‬
‫ن‬
‫ه‬
‫و‬
‫ي‬
‫ال‬
‫ء‬

Predicted Class
10 11 12 13 14 15 16 17 18 19 20

2

3

4

5

6

7

8

9

‫ا‬

‫ب‬

‫ح‬

‫د‬

‫ر‬

‫س‬

‫ص‬

‫ط‬

‫ع‬

‫ف‬

‫ق‬

‫ك‬

‫ل‬

‫م‬

‫ن‬

‫ه‬

‫و‬

‫ي‬

‫ال‬

‫ء‬

0
3
7
3
2
10
9
7
6
5
8
3
3
4
3
4
6
13
5
8

3
0
5
0
3
7
6
4
5
2
5
0
2
3
2
3
4
11
4
6

7
5
0
5
5
7
9
6
4
4
5
5
5
3
5
3
4
9
6
7

3
0
5
0
3
7
6
4
5
2
5
0
2
2
2
2
4
11
4
5

2
3
5
3
0
8
7
6
5
3
6
3
1
3
1
3
4
11
4
7

10
7
7
7
8
0
6
6
7
5
4
7
7
7
7
7
5
8
7
6

9
6
9
6
7
6
0
6
7
7
7
6
6
7
6
7
6
10
6
8

7
4
6
4
6
6
6
0
7
3
6
4
5
5
5
5
4
9
4
6

6
5
4
5
5
7
7
7
0
5
5
5
5
3
5
3
4
10
6
5

5
2
4
2
3
5
7
3
5
0
3
2
2
2
2
2
3
10
4
5

8
5
5
5
6
4
7
6
5
3
0
5
5
4
5
4
2
9
7
6

3
0
5
0
3
7
6
4
5
2
5
0
2
2
2
2
4
11
4
5

3
2
5
2
1
7
6
5
5
2
5
2
0
4
0
4
5
10
3
6

4
3
4
2
3
6
7
4
5
2
5
2
3
0
3
2
3
10
5
4

3
2
5
2
1
7
6
5
5
2
5
2
0
3
0
4
5
10
3
6

4
3
3
2
3
7
7
5
3
2
4
2
4
2
4
0
3
11
5
5

6
4
4
4
4
5
6
4
4
3
2
4
5
3
5
3
0
8
6
6

13
11
9
11
11
8
10
9
10
10
9
11
10
10
10
11
8
0
9
7

5
4
6
4
4
7
6
4
6
4
7
4
3
5
3
5
6
9
0
6

8
6
7
5
7
6
8
6
5
5
6
5
6
4
6
5
6
7
6
0

Table 7.5: Confusion matrix for Arabic character of Simplified font-type using edit-distance.

1187.2.2 Stage II: Testing/recognition stageDuring the recognition stage, thinning, feature extraction and segmentation
algorithms are applied to the input text images to obtain a character’s feature string(see Figure 7.1 at the beginning of the chapter). Then, the character’s feature string
being recognized is compressed using the PPM pre-trained models, and thecharacter class is chosen from the model used for training that compresses thefeature string best, as described in chapter 2, section 2.3.4.1. In particular, thecharacter’s feature string being recognized will obtain the lowest codelength when
it is compressed using the model that has been trained on the feature strings of thischaracter.
Table 7.6 shows how this works for a sample of feature strings taken from fivecharacters which are HEH, WAW, YEH, LAM ALEF and HAMZA. Twenty
character feature strings were obtain from each character. A tested feature stringof each character were compressed using order 5 PPM models trained on theremaining feature strings for the five selected character. The best performed modelfor each character’s feature strings are highlighted in bold. In all cases, the best
performed model is associated with the correct character of each feature string.
Testedfeaturestrings
HEH
WAW
YEH
LAM ALEF
HAMZA

Training feature strings
HEH

WAW

YEH

LAM ALEF

HAMZA

12.05214.95922.36212.76622.89622.562
16.33330.11721.67632.31553.76452.30215.31755.08441.76631.46631.21838.22412.06441.35133.51040.78235.04243.801
11.142

Table 7.6: Recognising the feature strings for five Arabic characters
Note: compression codelengths (in bits) for the character’s feature strings

7.3 Experimental Evaluation Results
In this section, two testing experiments have been conducted in order to recognize
Arabic text images and evaluate the performance of the PPM classifier. In the firstexperiment, the classifier was evaluated on a pre-segmented character images
119dataset. In the second experiment, the classifier was evaluated on a paragraphbased text images dataset. In the following sub-sections, the testing procedure will
be explained for both experiments.

7.3.1 Pre-segmented character images evaluation experiment

From the character dataset used in the training stage, 30% of the selected images
were selected as a testing set. For this experiment, the testing dataset follows thesame procedure used for the training stage. In particular, the two processing steps,
thinning and feature extraction, were applied to each image. This resulted infeature strings that were then passed to the PPM classifier. Note that thesegmentation method was not applied on this set, since the dataset consists of presegmented characters.
A number of performance metrics have been used to evaluate the accuracy ofclassification methods. In order to evaluate the PPM classifier, three of the mostcommon evaluation metrics have been used in this experiment: recall, precision
and F-measure (Witten et al., 2005). These metrics can be calculated using a
confusion matrix, which is used for visualizing the performance of theclassification techniques, as follows:
𝑇𝑃+𝑇𝑁

𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 = 𝑇𝑃+𝑇𝑁+𝐹𝑃+𝐹𝑁
𝑇𝑃

𝑅𝑒𝑐𝑎𝑙𝑙 = 𝑇𝑃+𝐹𝑁
𝑇𝑃𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 𝑇𝑃+𝐹𝑃
𝐹 − 𝑚𝑒𝑎𝑠𝑢𝑟𝑒 =2 ×𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛×𝑅𝑒𝑐𝑎𝑙𝑙
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛+𝑅𝑒𝑐𝑎𝑙𝑙

(7.1)
(7.2)
(7.3)
(7.4)

where 𝑇𝑃 (True Positives) is the number of cases where the prediction correctlyclassified and 𝑇𝑁 (True Negatives) is the number of cases where the prediction
correctly classified as negative. 𝐹𝑃 (False Positives) is the number of cases where
the prediction incorrectly classified as positive and 𝐹𝑁 (False Negatives) is thenumber of cases where the prediction is incorrectly classified as negative.
Confusion matrices that resulted from applying PPM to classify the pre-segmented
datasets for Traditional Arabic font, Arabic Transparent font, Simplified Arabic
120

font and AdvertisingBold font are shown in Table 7.7, Table 7.9, Table 7.11, andTable 7.13 respectively. The values in bold font represent the number of correctclassifications made by the PPM classifier.
It can be seen from Table 7.7 that a major confusion made by the PPM classifier
is between classes 2, 13 and 15, which are the BEH, LAAM and NOON characterclasses respectively. This misclassification seems a reasonable error to make, sincemost characters in class number 13 and class number 15 of the Traditional fontdataset have identical shapes which results in them sharing the same featurestrings. In addition, some characters from class number 13 have been misclassified
as characters from class number 2 by PPM. These misclassifications have occurredas the LAAM character in the middle form, which is a part of class number 13,
and the BEH characters in middle form have an identical feature. Table 7.8 shows
the accuracy, precision, recall and F-measure values that are achieved by the PPM
classifier when classifying the Traditional Arabic font dataset. The bottom row
displays an overall average for accuracy, precision, recall and F-measure. PPM
classified the Traditional Arabic font and AdvertisingBold font with an average
accuracy of 0.99, an average precision, recall and F-measure of 0.93, as shown in
Tables 7.8 and 7.14.
Remarkably, PPM performs better when classifying characters from the Simplified
Arabic font dataset in class 2 and 13, as shown in Table 7.11. The increase of thenumber of the corrected classifications made by the PPM for classifying
Simplified Arabic characters in class 13 is due to the LAAM characters in the
middle form having a dissimilar shape to the BEH character in the Simplified
Arabic font. Thus, the PPM classifier produced an average accuracy rate of 0.99
and average rates for all precision, recall and F-measure of 0.95, as shown in Table
7.12.

121

Actual
class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1
20
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0

Predicted Class2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0
17 0 0 0 0 0 0 0 1 0 0
0 20 0 0 0 0 0 0 0 0 0
0 0 18 0 0 0 0 0 0 0 2
0 0 0 17 0 0 0 0 0 0 0
0 0 0 0 20 0 0 0 0 0 0
0 0 0 0 0 20 0 0 0 0 0
0 0 0 0 0 0 20 0 0 0 0
0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 0 0 0 0 20 0 0
0 0 0 0 0 0 0 0 0 20 0
0 0 0 0 0 0 0 2 0 0 18
4 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

13
0
2
0
0
3
0
0
0
0
0
0
0
12
0
3
0
0
0
0
0

14
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0

15
0
0
0
0
0
0
0
0
0
0
0
0
1
0
15
0
0
0
0
0

16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0

17
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
18
0
0
0

18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0

Table 7.7: Confusion matrix for Traditional font-type classification using the 20 classes

122

19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0

20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20

ClassNumber
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AverageAccuracy

Precision

Recall

0.99
0.98
1.00
0.98
0.98
1.00
1.00
1.00
0.99
0.99
1.00
0.98
0.95
1.00
0.98
1.00
0.99
1.00
1.00
1.00
0.99

0.95
0.80
1.00
0.90
0.80
1.00
1.00
1.00
0.90
0.95
1.00
0.90
0.60
1.00
0.93
1.00
0.94
1.00
1.00
1.00
0.93

1.00
0.85
1.00
0.90
0.85
1.00
1.00
1.00
0.95
1.00
1.00
0.90
0.60
1.00
0.75
1.00
0.90
1.00
1.00
1.00
0.93

Fmeasure
0.97
0.82
1.00
0.90
0.82
1.00
1.00
1.00
0.92
0.97
1.00
0.90
0.60
1.00
0.83
1.00
0.92
1.00
1.00
1.00
0.93

Table 7.8: PPM classification results for the Traditional Arabic font type123

ActualPredicted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20

20
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
17
0
1
0
0
0
0
2
0
0
2
3
0
0
0
0
0
0
0

0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
18
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0

0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
17
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
20
0
0
1
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
17
1
0
0
0
0
0
0
0

0
2
0
0
1
0
0
0
0
0
0
1
14
0
2
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
19
0
1
0
0
0
0

0
0
0
0
1
0
0
0
0
0
0
0
2
0
17
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
0
0
0
0

0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
20
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0

Table 7.9: Confusion matrix for the Transparent font-type classification using the
20 classes

124

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20

ClassNumber
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AverageAccuracy Precision
0.99
0.97
1.00
0.99
0.99
1.00
1.00
1.00
0.99
1.00
0.99
0.98
0.96
0.99
0.98
0.99
0.99
1.00
1.00
1.00
0.99

0.95
0.68
1.00
1.00
0.94
1.00
1.00
1.00
1.00
1.00
0.95
0.94
0.70
0.95
0.94
1.00
0.95
1.00
1.00
1.00
0.95

Recall
1.00
0.85
1.00
0.95
0.90
1.00
1.00
1.00
0.85
1.00
1.00
0.85
0.70
0.95
0.85
0.95
1.00
1.00
1.00
1.00
0.94

Fmeasure
0.97
0.75
1.00
0.97
0.92
1.00
1.00
1.00
0.91
1.00
0.97
0.89
0.70
0.95
0.89
0.97
0.97
1.00
1.00
1.00
0.94

Table 7.10: PPM classification results for the Transparent Arabic font type125

Actualpredicted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20

20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
18
0
1
0
0
0
0
1
0
0
0
3
0
0
0
0
0
0
0

0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
1
0
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0

0
0
0
0
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
1
20
0
0
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
18
1
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
1
19
0
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0

0
0
0
2
0
0
0
0
0
0
0
18
0
0
0
0
0
0
0
0

0
1
0
0
0
0
0
0
0
0
0
2
16
0
1
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0
0
0

0
0
0
0
0
1
0
0
0
0
0
0
3
0
19
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0
0

0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
19
0
0
0

Table 7.11: Confusion matrix for the Simplified Arabic font-type classification
using the 20 classes

126

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20

ClassNumber
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AverageAccuracy Precision
1.00
0.98
1.00
0.98
0.99
0.99
0.99
0.99
0.99
0.99
1.00
0.98
0.97
1.00
0.98
1.00
0.99
1.00
1.00
1.00
0.99

1.00
0.78
1.00
0.94
0.95
1.00
1.00
0.95
0.94
1.00
1.00
0.90
0.80
1.00
0.82
1.00
0.95
1.00
1.00
1.00
0.95

Recall
1.00
0.90
1.00
0.85
1.00
0.95
0.95
1.00
0.90
0.95
1.00
0.90
0.80
1.00
0.95
1.00
0.95
1.00
1.00
1.00
0.95

Fmeasure
1.00
0.83
1.00
0.89
0.97
0.97
0.97
0.97
0.92
0.97
1.00
0.90
0.80
1.00
0.88
1.00
0.95
1.00
1.00
1.00
0.95

Table 7.12: PPM classification results for the Simplified Arabic font type127

Actual
class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

2
0
16
0
1
0
0
0
0
1
2
0
0
6
0
0
0
0
0
0
0

3
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

4
0
1
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

5
0
0
0
0
19
0
0
0
0
0
0
0
1
0
2
0
0
0
0
0

6
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0

7
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0

8
0
0
0
0
0
0
1
20
0
0
0
0
0
0
0
0
0
0
0
0

Predicted Class
9 10 11 12
0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0
20 0 0 0
0 18 0 0
0 0 19 0
0 0 0 180 0 0 00 0 2 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0

13
0
3
0
0
1
0
0
0
0
0
0
1
10
0
0
0
0
0
0
0

14
0
0
0
0
0
0
0
0
0
0
0
0
0
18
0
1
0
0
0
0

15
0
0
0
0
0
1
0
0
0
0
0
1
3
0
18
0
0
1
0
0

16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
0
0
0
0

17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0
0
0

18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
0
0

Table 7.13: Confusion matrix for the AdvertisingBold font type classification using
the 20 classes

128

19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
0

20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20

ClassNumber
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AverageAccuracy Precision
1.00
0.96
1.00
0.99
0.98
1.00
1.00
0.99
1.00
0.99
0.99
0.99
0.96
0.99
0.97
0.99
1.00
0.99
1.00
1.00
0.99

1.00
0.61
1.00
0.95
0.86
1.00
1.00
0.95
1.00
1.00
0.90
1.00
0.66
0.94
0.75
1.00
1.00
1.00
1.00
1.00
0.93

Recall
1.00
0.80
1.00
0.95
0.95
1.00
1.00
1.00
1.00
0.90
0.95
0.90
0.50
0.90
0.90
0.95
1.00
0.95
1.00
1.00
0.93

Fmeasure
1.00
0.69
1.00
0.95
0.90
1.00
1.00
0.97
1.00
0.94
0.92
0.94
0.57
0.92
0.81
0.97
1.00
0.97
1.00
1.00
0.93

Table 7.14: PPM classification results for the AdvertisingBold font type

7.3.2 Paragraph-based text images evaluation experiment
The objective of this experiment described in this section is to assess recognition
performance (combining thinning, feature extraction, segmentation andclassification stages) of the PATRION OCR system using the PPM as a classifier
on real text images. Thus, the edit distance evaluation metric has been used in thisexperiment (see chapter 3, section 3.2). The dataset which was used for thisevaluation is the same dataset used for the evaluation study in chapter 3. However,Arabic Transparent, AdvertisingBold, Simplified Arabic and Traditional Arabic
are the font types which have been investigated in this recognition study with text
images at 300dpi. Recall that the text images have been selected from a publicly
available dataset (KAFD dataset). The test set contains 16 text images from thefour font types (Arabic Transparent, AdvertisingBold, Simplified Arabic andTraditional Arabic) at 300dpi. For each font, 12 and 24 pitch sizes have been
selected. Additionally, normal and italic font styles for each font pitch size have129

been used. Note that as recognition of numbers and punctuation marks is out of
the scope of this study, numbers or punctuation marks have been ignored in theclassification stage.
The test text images were passed through the thinning, feature extraction andsegmentation stages. Then, the output of the segmentation stage which is thefeature string for each character has been passed to the PPM classifier to performthe recognition task using the twenty character models.
Figure 7.7 (a) shows a sample of the text image test set. The corresponding groundtruth which is available with the dataset (see Figure 7.2 (b)) has been modified inorder that they can be matched with the output of the classifier. In particular, allcharacters have been replaced by their corresponding class characters as shown in
Table 7.1. For example, characters like ‫ ج‬and ‫ خ‬in the ground-truth have been
replaced by their class character which is the character (‫)ح‬. Running this image
through the PATRION Arabic OCR system produced the text shown in Figure 7.3.

130

(a)

(b)

Figure 7.2: Text image example used in the recognition/testing stage
Note: (a) An Arabic text image from the KFAD dataset and (b) the modified corresponding ground truth

Figure 7.3: PATRION OCR output text produced for image in Figure 7.2

131Table 7.15 shows the recognition accuracy for each font. As can be seen from thetable, the PATRION OCR system achieves an average accuracy rate of 77.3%.
The recognition results indicate that the system has a higher accuracy inrecognising Simplified Arabic font with 81.5% accuracy. In terms of font style,our experiment finds that the PATRION OCR system obtains an accuracy rate of
78.5% and 76.1% for recognizing a normal font style and an italic font stylerespectively, as Table 7.16 shows. In addition, the respective recognition accuracyof the proposed system in relation to different font pitches sizes is presented inTable 7.17.
The possible explanation for the lower accuracy in this experiment is as follows.
Recall that the connectivity of Arabic text is an obstacle of Arabic text recognition.
Also, as has been mentioned in Chapter 5 that character segmentation in Arabic
text recognition is a critical step as most of the recognition errors are produced byerrors in character segmentation. This is supported by the experiment results,
obtained from both evaluation experiments, which indicate that the accuracy
performance rates of the PPM classifier are higher in classifying pre-segmented
Arabic characters than in classifying characters from paragraph-based text images.
Font type
Arabic Transparent
Traditional Arabic
Simplified Arabic
AdvertisingBold
AverageAccuracy
74.7%
77.5%
81.5%
75.5%
77.3%

Table 7.15 Recognition accuracy results on different Arabic fonts
Font style
NormalItalicAccuracy
78.5%
76.1%

Table 7.16: Italic and normal font recognition accuracy results

Font pitch size
24
12

Accuracy
79.7%
74.9%

Table 7.17: Recognition accuracy results based on font pitch size132

7.4 Discussion and Summary
In this chapter, a compression-based model has been applied for the first time to
Arabic text recognition. The implementation of a compression based model has
been explained. Two classification experiments were conducted in order toclassify and recognise isolated Arabic character images and Arabic text images
using the PPM models.
The experimental evaluation study in this chapter has analysesd the performanceof the PPM classifier and underlined the major misclassifications that were
produced, such as the misclassification between the LAAM character, the BEH
character and the NOON character. These major misclassification errors that weremade by the PPM classifier will be examined when improving the overall accuracyof the PATRION OCR system in the next chapter.

133

Chapter 8: Post-processing
8.1 Chapter Introduction
In the previous chapter, the new PATRION system, which was developed for thisresearch, recognised non-dotted Arabic text images. The PATRION system misrecognised some Arabic characters. In this chapter a post-processing stage, whichis the final stage in the PATRION OCR system (see Figure 8.1), has been
implemented for improving the OCR output by correcting the mis-recognition
errors. Recognizing dots in Arabic text has been ignored in all the previous stages
due to its challenge. However, this chapter aims to overcome the challenge ofrecognizing dotted characters in Arabic text by using a post-processing method torecover unrecognised dots.
In this chapter, a post-processing technique based on the PPM compression
scheme, which is discussed in the review chapter, has been applied to two specificproblems: adding dots to Arabic text and correcting the OCR output. Section 8.2
shows how the PPM language model can be used as a post-processing stage for
the Arabic OCR system. Then, section 8.3 discusses experimental results using the
PPM based correction method. Section 8.4 compares the performance of the
PATRION system with others reported in chapter 3. A summary and discussion ofthis chapter is presented in section 8.5.

134

Figure 8.1: Block diagram of the PATRION OCR system
Note: The shaded area shows the scope of the current chapter ‘Post-processing’.

8.2 Applying a PPM Language Model for Arabic Text Correction
The PPM correction method uses a language model to determine the likelihood ofa possible correct character using the Viterbi algorithm (Viterbi, 1967). For
constructing a language model, a training corpus of Arabic text is required. Due tothe limited availability and accessibility of Arabic corpora, the Bangor Arabic
Compression Corpus (BACC) published by Alhawiti (2014), which contains about
31-millon Arabic words collected from several sources, has been selected. The
PPM model was applied to the problem of OCR text correction using the approach
used by Teahan et al. (1998) for correcting English OCR texts and by Alhawiti(2014) for correcting Arabic OCR texts. However, the main limitation of
Alhawiti’s Arabic correction study is that the PPM method was only able to correct
one-to one Arabic character errors. To overcome this problem, the Buckwalter text
processing technique, as used by Alkhazi & Teahan (2017), has been first applied
to convert Arabic characters to equivalent Latin ASCII characters. Then, an order
5 PPMD model implemented by the Tawa Toolkit described by Teahan (2018)trained on the BACC Corpus has been used for constructing the language model.
Teahan et al. (1998) define ‘confusion’ as a transformation that is used to correctcharacters in the text. They use 𝑜𝑏𝑠𝑒𝑟𝑣𝑒𝑑 → 𝑐𝑜𝑟𝑟𝑒𝑐𝑡 to denote a confusion
135

transformation from the observed text to the correct text. For the PATRION
system, the mis-recognitions produced in the previous chapter have been used as
the confusions. Table 8.1 shows a set of confusions that have been mostly
generated by the PATRION OCR. Also, Table 8.1 contains a set of confusions thatis used for adding dots to Arabic characters (correcting dots characters). For
example to correct the dot character ‫ج‬, ‫ ج →ح‬denotes the character ‫ ح‬corrected tothe character ‫ج‬. On the other hand, Arabic script has some letters that contains
Hamza which is placed above or below the letter, such as the ALEF character.
Hamza that is placed above or below the ALEF has been ignored in the previous
stages as it is not a part of the main body of the character. Thus, we also include a
confusion for correcting Hamza in the ALEF character.

Arabic Character‫ل →ب‬‫ن →ل‬‫ل →ن‬‫ا →ب‬‫ت →ب‬‫ج →ح‬‫ز →ر‬‫ظ →ط‬‫ي →ى‬‫ث →ب‬‫خ →ح‬‫ش →س‬‫و →ر‬

Confusion
Equivalent
Arabic Character
Buckwalteri→T‫س →ب ل‬T→U
‫ي →ب‬
U→T‫م →ف‬i→u‫أ →ا‬i→p‫ي →ب‬d→s‫ذ →د‬j→ k‫ض →ص‬v →b‫ق →ف‬
P→A‫س →ب ن‬i→a
‫غ →ع‬d→f‫ى →م‬l→z‫إ →ا‬j→ O‫ة →ه‬

Equivalent
Buckwalter
iT→l
i→A
W→ Y
u→e
i→A
g→h
x→c
W→ E
Ui→l
n→m
Y→P
u→t
I→o

Table 8.5: Set of confusions used for correcting the PATRION OCR output

8.3 Experimental Evaluation of PPM Correction Method
In this section, two experiments have been conducted for an investigation into theeffectiveness of using the PPM based correction method for correcting the Arabic
OCR output. In the first experiment, the PPM language model was applied to the
PATRION OCR system in order to correct and add dots to the output text producedby the system. In the second experiment, we applied the PPM correction method136to a commercial Arabic OCR system, in an attempt to improve OCR output to see
if the correction method also applies to other Arabic OCR systems.
The image dataset used in both experiments is the KAFD dataset used in theprevious chapter which contains 16 text images from the four font types (Arabic
Transparent, AdvertisingBold, Simplified Arabic and Traditional Arabic) at
300dpi. The PPM based correction method has been evaluated by comparing theprocessed text with the original text (ground-truth). The difference between the
two texts was obtained by using the edit distance implemented in the automatedevaluation tool described in chapter 3. In the following sub-sections, the evaluation
procedure will be explained for both experiments.

8.3.1 PATRION OCR output correction experiment

In this experiment, the PPM correction method was applied to the PATRION OCR
system at the post-processing stage. A sample of the output text produced by the
PATRION OCR system for an Arabic text image is shown in Figure 8.2. As canbe seen from the output text, some characters are required to be dotted. For
instance, ‫ د‬in the word ‫ هدا‬and ‫ ح‬in the word ‫ ( برحع‬line 1 in Figure 8.2 (b)) are notdotted. These should be dotted as ‫ذ‬, and ‫ ج‬respectively. Also, the OCR systemproduces some recognition errors, such as ‫ الم‬and ‫ احساببهما‬which should be written
as ‫ إلى‬and ‫إحساسهما‬.
Sample texts after applying the correction method for the OCR output texts ofdifferent font types of text images are shown in Figures 8.2, 8.3, 8.4 and 8.5.
Considering the corrected output texts, the text has been correctly dotted by the
PPM correction method. For example, the dot corrections of ‫ فد‬to ‫ قد‬, ‫ هدا‬to ‫( هذا‬line
1 in Figure 8.2), ‫ فرب‬to ‫ ( قرب‬line 1 in Figure 8.3), ‫ فى‬to ‫ ( في‬line 3 in Figure 8.3),‫ بعسره‬to ‫( بعشرة‬line 1 in Figure 8.4), and ‫ بسكل‬to ‫ ( بشكل‬line 1 in Figure 8.5) stemfrom single character confusions, whereas the correction of ‫ بلبب‬to ‫( سبب‬line 1 inFigure 8.2), ‫ البلفن‬to ‫( السفن‬line 3 in Figure 8.3) derives from double character
confusions which is ‫س → ب ل‬. Also, the PPM correction method successfully
corrected multiple errors that occur in some words. For example, thecorrections ‫ برحع‬to ‫( يرجع‬line 1 in Figure 8.2), ‫ حرب‬to ‫( جرت‬line 3 in Figure 8.3)
and ‫ الرعابه‬to ‫( الرعاية‬line 3 in Figure 8.5) are multiple character corrections in one
137

word. Interestingly, Hamza errors have been successfully corrected by the PPM
method, such as and ‫ إ → ا‬in the word ‫( إلى‬line 2 in Figure 8.2) and ‫ أ → ا‬in the word‫( أجزاء‬line 2 in Figure 8.4).
In the previous chapter, it is stated that the overall accuracy of the PATRION OCR
system so far is 77.3%. However, by applying the post-processing method on the
16 text images used for testing mentioned in section 8.3, the recognition accuracy
improves to 86.9%.

138

(a)

(b)

(c)

Figure 8.2: PPM correction of the PATRION OCR output text
Note: (a) An Arabic text image of the Arabic Transparent font from the KFAD dataset, (b) The output text from the
proposed OCR system that was produced for the image in (a) and (c) the corrected OCR output text after applying the
PPM correction method.

139

(a)

(b)

(c)

Figure 8.3: PPM correction of the PATRION OCR output text
Note: (a) An Arabic text image of the Simplified Arabic font from the KFAD dataset, (b) The output text from the
proposed OCR system that was produced for the image in (a) and (c) the corrected OCR output text after applying
the PPM correction method.

140

(a)

(b)

(c)

Figure 8.4: PPM correction of the PATRION OCR output text
Note: (a) An Arabic text image of the AdvertisingBold font from the KFAD dataset, (b) the output text from the
proposed OCR system that was produced for the image in (a) and (c) the corrected OCR output text after applying
the PPM correction method.

141

(a)

(b)

(c)

Figure 8.5: PPM correction of the PATRION OCR output text
Note: (a) An Arabic text image of the Traditional Arabic font from the KFAD dataset, (b) The output text from the
proposed OCR system that was produced for the image in (a) and (c) the corrected OCR output text after applying the
PPM correction method.

8.3.2 Commercial Arabic OCR output correction experiment

In an attempt to evaluate the impact of using the PPM model-based text correction
method on the four Arabic OCR systems (Sakhr, ABBYY, RDI and Tesseract)
studied in Chapter 3, the method was applied only to the output of the ABBYY
commercial OCR system. This choice has been made as other OCR systems
produced unreadable output text due to their poor performance. See figure 8.6 asan example of an output text produced by Sakhr OCR which is extremely hard atbest and impossible at worst for a human to read.

142

(a)

(b)

Figure 8.6: Example of unreadable Sakhr OCR output text
Note: (a) An Arabic text image from the KFAD dataset, and (b) the Sakhr OCR output text that was produced for theimage in (a).

Table 8.2 lists a sample of the confusions that were generated when the ABBAYY
OCR system was applied to the text images. It is worth mentioning that the mosterrors made by the ABBYY OCR system are related to the dot characters andHamza characters. Examples for dot character errors are: the letter ‫ ف‬wasincorrectly replaced by ‫ق‬, the letter ‫ ب‬was incorrectly replaced by ‫ ي‬and the letter‫ ص‬was replaced by the letter ‫ض‬. The incorrect transformation of the letter ‫ أ‬to ‫ ا‬isan example of Hamza character error. A sample of ABBYY OCR output for a text
image and the correction OCR text is shown in Figure 8.7. The correction of ‫نكروا‬to ‫ذكروا‬, ‫ ان‬to ‫ أن‬and ‫ المفرب‬to ‫( المغرب‬line 1 in the text) all stem from one character
confusions which are ‫ذ →ن‬, ‫ أ →ا‬and ‫غ →ف‬, while the corrections of ‫ خوها‬to ‫نحوها‬derives from multiple character confusions. The correction of ‫ المفري‬to ‫( المغرب‬lastline in the text) requires multiple corrections in one word (‫ غ →ف‬and ‫)ب →ي‬. After
applying the PPM correction method to the output of the ABBYY OCR system,
the recognition accuracy increases from 70.2% to 77.1%.

143

Confusion
ArabicEquivalent
ArabicEquivalentCharacter Buckwalter Character Buckwalteru→tf→Ud‫إ →ا‬‫ن ح →خ‬ArabicCharacter‫أ →ا‬

Equivalent
Buckwalteru→e‫ذ →ن‬

U→h‫ر →ى‬

P→j‫ض →ص‬x→ c‫غ →ف‬W →m‫و →ه‬

I→O‫ت →ث‬a→p‫أن →ت‬p→eU‫ف →ق‬E→ W‫ر →م‬

Y→ j‫ع →غ‬

m→n‫ظ →ط‬v→b‫ب →ي‬

A→i

Table 8.6: Sample of the confusions used that were generated from ABBYY OCR
output

(a)

(b)

(c)

Figure 8.7: PPM correction of the ABBYY OCR output text
Note: (a) An Arabic text image from the KFAD dataset, (b) the proposed OCR output text that was produced for theimage in (a) and (c) the corrected OCR output text after applying the PPM correction method.

144

8.4 Overall Experimental Evaluation of the PATRION OCR System
In this section, we compare the PATRION OCR with results obtained using thefour Arabic OCR systems studied in Chapter 3, which are Sakhr OCR, ABBYY
OCR, RDI OCR and Tesseract OCR. The comparative evaluation results wereobtained by running Arabic OCR systems on the same dataset mentioned in
Section 8.3. For a fair comparison, the recognition accuracy of numbers andpunctuations of Arabic OCR systems have been excluded from the overall
accuracy, since the recognition of numbers and punctuations are out of the scopeof the PATRION OCR system. The automated tool described in chapter 3 has beenused in order to provide performance accuracy rates using various metrics thatprovide a better insight into the effectiveness of the Arabic OCR systems withrespect to the challenges of Arabic script.
The accuracy of Arabic OCR systems in recognising Arabic characters based on
their position in a word are provided in Figure 8.8. The results show that all of the
Arabic OCR systems have higher accuracy in recognising isolated characters when
they are not connected with other characters in a word. This supports the idea thatthe connectivity feature of Arabic script is still an obstacle to Arabic text
recognition. However, high scores of character accuracy for the four character
positions were obtained by the PATRION OCR system. From figure 8.8, it can beseen that a drop in character recognition accuracy occurs when recognising end
characters by the PATRION OCR system. The low recognition accuracy of end
characters by the PATRION OCR system is due to segmentation errors whensegmenting the end form shape of the Alef “‫”ـا‬, Haa “‫ ”ـه‬and Yaa “‫ ”ـى‬characters
discussed in chapter 6.
The results of the recognition accuracy performance of the Arabic OCR systems
in terms of one dot, two dot, three dot and no-dot characters are illustrated in figure
8.9. These results shows that the recognition accuracy rates of no-dot characters
are significantly better for Sakhr, ABBYY, RDI and Tesseract OCR system,compared to one, two and three dot characters. However, among the evaluatedArabic OCR systems, only the PATRION OCR system’s recognition accuracy
rates of two and three dot characters are similar to the recognition accuracy rate of145

no-dot characters. This confirms that the PATRION OCR system overcomes thechallenge of the presence of dots in Arabic script by using the PPM correction
method for adding dots to Arabic texts.
The results of analysing the performance of the Arabic OCR systems on charactersthat have a dot above or below the baseline are presented in figure 8.10. It is
obvious that all of the evaluated Arabic OCR systems and the PATRION OCR
system perform much better in identifying characters with a dot below the baseline
than characters with a dot above the baseline. The reasons for these results are notentirely clear. It could be due to baseline determination algorithms implemented
by these systems.
Figure 8.11 compares the recognition accuracy for zigzag-shaped characters andloop-shaped characters by the Arabic OCR systems. It is apparent from the resultsthat the performance rates of Sakhr, ABBYY, RDI and Tesseract OCR system inrecognising loop-shaped characters are higher than in recognising zigzag-shaped
characters, whereas the PATRION OCR system performs better in recognisingzigzag-shaped characters than loop-shaped characters. However, the PATRION
OCR system has the highest performance accuracy rates for both character shapes,
compared to the other four Arabic OCR systems. Moreover, the results indicatethat the PATRION OCR system is more robust in recognising zigzag-shaped
characters which is a challenge for the four other Arabic OCR systems.
Figure 8.12 and Table 8.3 summarize the overall accuracy scores for thecomparison of the Arabic OCR systems. The evaluation results when comparing
the PATRION OCR system against the other four Arabic OCR systems show that
the PATRION OCR system achieved the highest accuracy of 86.9%. In summary,the results shows that the PATRION OCR system is very effective when compared
the other four Arabic OCR systems.

146

100.00
90.00
80.00

Accuracy

70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00
Isolated

InitialTesseract

Sakhr

ABBYY

RDI

PATRION

MiddleEnd

Character position classes

Figure 8.8: Character position class accuracy comparison on KAFD dataset

100.0090.00

Accuracy

80.00
70.00
60.00
50.00
40.00
30.00
20.00
10.00
One Dot

Two Dots

Tesseract

Sakhr

RDI

PATRION

Three Dots

ABBYY

No-Dots

Dot character classes

Figure 8.9: Dot character class accuracy comparison on KAFD dataset147

Accuracy

100.00
90.00
80.00
70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00

Tesseract

Sakhr

RDI

PATRION

Above

Baseline dot character classes

ABBYY

Below

Accuracy

Figure 8.10: Baseline dot character class accuracy comparison on KAFD dataset

100.00
90.00
80.00
70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00
ZigzagShaped character classes

Tesseract

Sakhr

RDI

PATRION
Loop

Figure 8.11: Shape character class accuracy comparison on KAFD dataset

148

ABBYY

100.00
90.00
80.00

Accuracy

70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00
Sakhr

ABBYY

RDI

Tesseract

PATRION

OCR systems

Figure 8.12: Overall Arabic OCR performance accuracy comparison on KAFD
datasetOCR System

Font Type

Sakhr

ABBYY

RDI

Tesseract

PATRION

Traditional Arabic
Simplified Arabic
Arabic Transparent
AdvertisingBold

48.5%
52.9%
51.5%
57.3%

67.7%
67.7%
75.2%
70.3%

51.9%
44.9%
46.1%
27.2%

47.1%
46.7%
48.6%
39.4%

Average

52.6%

70.2%

42.5%

45.4%

87.9%
91.8%
83.1%
84.7%
86.9%

Table 8.7: Arabic OCR performance accuracy according to four font types

8.5 Discussion and Summary
In this chapter, a post-processing method based on a PPM model was introduced
for correcting Arabic OCR output. This method has been applied to two problemsof Arabic OCR systems: adding dots to Arabic text and correcting the OCR output.
The method has successfully corrected mis-recognition errors and dottedcharacters in Arabic OCR output. By applying the PPM model to the new
PATRION OCR system, the edit distance accuracy improved from 77.3% to86.9%. Also, the implementation of the PPM correction method in the PATRION
OCR system has helped to overcome the challenges of the presence of dots andzigzag-shaped characters in Arabic script, since the experimental results show that
the PATRION OCR system is robust in recognising dotted characters and zigzagshaped characters.
149

Moreover, experimental results on a commercial Arabic OCR system show thatthe post-processing method was also able to increase the edit distance accuracy forthat system from 70.2% to 77.1%.

150

Chapter 9: Conclusion and Future Work
9.1 Chapter Introduction
The need to extend digital Arabic content on the Internet and to analyse online text
motivated the development of an accurate OCR system for Arabic text. However,the development of an OCR system for printed Arabic is a challenging task. These
challenges are due to the specific characteristics of Arabic script. Previous research
adopted different methods that were developed for other languages without
considering the specific characteristics of Arabic script. Moreover, there is a lackof objective performance metrics for assessing how Arabic OCR systems arecoping with the challenges of Arabic text.
In this study, we proposed several related methods that take into consideration thecharacteristics of Arabic text for the implementation of a robust printed Arabic
OCR system. In addition, a novel automated evaluation tool was developed withnew objective performance metrics.
Compression based language modelling has proven to be very effective for many
NLP applications. However, no prior study has exploited the effectiveness ofcompression based models for the problems of Arabic OCR. In this work, wedeveloped new approaches that make use of a compression-based model.
This chapter first provides the summary of this dissertation. Then, it reviews theaims and objectives of this work followed by reviewing the research questions. It
also highlights the limitations of this work. Finally, it provides several directions
for future work.
9.2 Summary
This work firstly provided a comprehensive literature review of printed Arabic text
recognition. It reviewed different methods that have been used for developing
Arabic OCR systems. In addition, it reviewed relevant issues of printed Arabic
OCR including the challenges of printed Arabic script and performance evaluation
issues. Also, it discussed the current status of printed Arabic OCR as well as thechallenges and open problems in printed Arabic text recognition. It concluded that151

there is still a crucial need for more research, although there are various attempts tosolve the problems of Arabic text recognition.
In chapter 3, we firstly developed a novel automated Arabic OCR evaluation tool.
This tool has been developed based on a new set of objective performance metrics
with respect to the challenges of Arabic text which are character accuracy based on
character position, dot character accuracy, zigzag-shaped character accuracy, loopshaped character accuracy, diacritics accuracy, digit accuracy and punctuation
accuracy. We then proposed a standard protocol for measuring the effectiveness of
Arabic optical character recognition. An automated evaluation experiment has been
conducted, using the developed evaluation tool, to evaluate the performance of fourwell-known Arabic OCR systems: Sakhr, ABBYY, RDI and Tesseract. The
experimental results showed that all the evaluated Arabic OCR systems have low
performance accuracy rates, below 75%, which means that the field of character
recognition for printed Arabic still requires further research to reach an efficient
text recognition method for Arabic script. Chapter 3 also concluded that the newly
developed automated evaluation tool is able to automatically assess how Arabic
OCR systems are overcoming the challenges of Arabic text and it contributes toeliminate human error, improve speed and precision, and reduce repetition in
evaluating Arabic OCR systems.
Our study mainly aimed at developing a novel OCR for printed Arabic text that
substantially improves upon the state-of-the-art. To achieve this aim, a new
PATRION OCR system has been implemented in this work using five stages: (1)thinning; (2) feature extraction; (3) character segmentation; (4) classification; (5)post-processing.
In chapter 4, a new thinning algorithm for Arabic text has been developed. Also,
we proposed an experimental framework with new objective performance metrics
for evaluating thinning algorithms for Arabic text in terms of connectivity and dots
persevering. An experimental evaluation was conducted to evaluate the new
thinning algorithm against two well-known thinning algorithms, Zhan-Suen and
Hilditch, with respect to the new proposed performance metrics and other different
adopted metrics. The experimental results showed that the new algorithm has thebetter performance than the other two thinning algorithms. Chapter 4 also152

concluded that the new objective performance metrics are sufficient to provide us
with insight of which thinning algorithm performs better for Arabic OCR.
In chapter 5, a new technique based on a cognitive insight used for extracting
features from the skeleton of non-dotted Arabic text images has been developed
using an agent-based NetLogo model. This method has been applied prior to thecharacter segmentation phase in order to overcome the challenges of Arabic
character segmentation. The method has been tested on a sample of 100 Arabic
words images and has produced an average edit distance accuracy of 98.07%.
Chapter 5 also concluded that most of the produced errors by the feature extraction
method are related to the thinning algorithm.
Chapter 6 presented a new character segmentation technique for segmenting
connected Arabic words into characters based on the extracted feature. The
character segmentation method identified the segmentation point in the extracted
feature string based on two features of Arabic script: the junction line and thebranch point. The method has been tested on a sample of 100 Arabic words images
and has produced a recall of 84.2% and a precision of 77.2%. Chapter 6 also
concluded that the segmentation method has effectively segmented overlapping
characters which is one of the main characteristics of Arabic text that causes
difficulties to the development of character segmentation methods.
In Chapter 7, a compression based model has been applied for the first time to
Arabic textual feature recognition. Two classification experiments were conductedin order to classify and recognise isolated Arabic character images and Arabic text
images using PPM models. The method has produced an average edit distanceaccuracy of 77.3%. Chapter 7 also concluded that due to the challenge of theconnectivity characteristic of Arabic script, the PPM classifier performs better inclassifying pre-segmented Arabic characters than in classifying characters fromparagraph-based text images.
In the final stage of the development of the PATRION system, a post-processing
technique based on a PPM correction method was applied for correcting Arabic
OCR texts, in an attempt to improve the recognition accuracy, as explained inchapter 8. This method has improved the edit distance accuracy of the PATRION
system from 77.3% to 86.9%. The PPM correction method was also applied to a153

commercial Arabic OCR system and it was able to improve the edit distanceaccuracy for that system from 70.2% to 77.1%. Also, the PATRION system wasevaluated against the four well-known Arabic OCR systems (mentioned above).
The results show that the PATRION OCR system is very effective compared to theother four Arabic OCR systems, as it achieved the highest accuracy of 86.9%.
Chapter 8 also concluded that the implementation of the PPM correction method in
the PATRION OCR system has helped to overcome the challenges of the presenceof dots and zigzag-shaped characters in Arabic text.
9.3 Review of Aims and Objectives
The aims and objectives of this work listed in Section 1.2 have all been successfully
achieved. A novel OCR system (PATRION) for printed Arabic script has beendeveloped. The PATRION OCR system has been evaluated and compared withfour well-known Arabic OCR systems and the experimental results showed that thesystem substantially improves upon the other OCR systems.
The specific objectives addressed in Section 1.2 were achieved as follows: perform a comprehensive review of printed Arabic text recognition.
A comprehensive review of printed Arabic text recognition has been performed.
This objective was achieved in chapter 2.
 develop an automated tool for evaluating the performance of Arabic OCR
systems.
An automated evaluation tool with new objective metrics for the evaluation of
Arabic OCR performance has been developed. This objective was achieved inchapter 3.
 evaluate the effectiveness of the state-of-the-art printed Arabic text recognition
systems.
The state-of-the-art printed Arabic text recognition systems have been evaluatedin chapter 3.
 design and implement a new thinning algorithm for Arabic text and evaluate
the effectiveness of the new algorithm by comparing it with well-known thinningalgorithms.
154

A novel thinning algorithm for Arabic text has been developed and evaluated bycomparing it with well-known thinning algorithms. This objective was achievedin chapter 4.
 develop a new chain-code representation technique using an agent-basedmodel for extracting features from non-dotted Arabic text images prior to thecharacter segmentation phase.
A new technique based on chain-code representation used for extracting featuresfrom non-dotted Arabic text images prior to the character segmentation phasehas been developed. This objective was achieved in chapter 5.
 develop a new character segmentation technique for segmenting connectedArabic words into characters based on the extracted features.
A new character segmentation technique based on the features extracted from
Arabic text has been developed. This objective was achieved in chapter 6.
 develop a new compression-based method for classifying the segmented Arabic
characters.
A novel compression based method has been applied as a classifier to Arabic
textual feature recognition. This objective was achieved in chapter 7.
 use compression-based post-processing techniques (for example, adding dots
to Arabic text and correcting the OCR output).
Finally, a compression based post-processing technique has been applied to two
problems: adding dots to Arabic text and correcting the OCR output. Thisobjective was achieved in chapter 8.
9.4 Review of Research Questions
This section reviews the specific research questions of this work that were listed in
Section 1.3.
 Is the current OCR methodology which involves the five sequential stages (preprocessing; feature extraction; segmentation; classification and postprocessing) the most effective for designing Arabic OCR?

155

The literature review noted that most of the current studies in Arabic OCR used
the general methodology that involves the five sequential stages. Some studies
ignored the segmentation stage by developing Arabic OCR systems based on afree-segmentation or holistic approach which recognize words or sub-words asa whole unit with no segmentation in order to overcome the challenges ofcharacter segmentation. However, such systems are lexicon based systems.
From reviewing the work on the five stages of printed Arabic OCR, we reached
the conclusion that there is less opportunity for improvement for Arabic OCR
by using the general OCR methodology, since most approaches used in eachstage have been adopted from approaches that have been developed for otherlanguages without considering the characteristics of Arabic script.
 Are there alternative methodologies that might yield better results for Arabic
OCR?
This study developed a new methodology for implementing printed Arabic OCR
system. In particular, the developed system performs the feature extraction stageprior to the character segmentation stage, unlike the general methodology, inorder to overcome the challenges of Arabic character segmentation. As indicatedin the comparative evaluation results of the developed OCR (PATRION) and
four other OCR systems (shown in chapter 9), the approach which was used indeveloping the PATRION OCR system seems to be promising as it achieves
better recognition performance.
 Are the general standard performance measurements of character accuracy
sufficient to assess how Arabic OCR systems are coping with the challenges of
Arabic script?
The literature showed that printed Arabic OCR poses great challenges due to thespecial characteristics of Arabic text. Therefore, different methods have been
proposed for developing printed Arabic OCR systems. Most of the proposed
methods have been evaluated in terms of a general metric which is character
accuracy. By relying on such a metric, we cannot fully assess how Arabic OCR
systems are overcoming the challenges of Arabic text. Therefore, we havesuggested a new set of objective performance metrics for the evaluation of
Arabic OCR systems with respect to the challenges of Arabic script. These are156

character accuracy based on character position, dot character accuracy, zigzagshaped character accuracy, loop-shaped character accuracy and diacritics
accuracy, as described in chapter 3, section 3.2.
 Are the available OCR systems sufficient to recognise printed Arabic text
images?
The experimental results, obtained from evaluating the four well-known Arabic
OCR systems discussed in chapter 3 (section 3.6), showed that all the evaluatedArabic OCR systems have low performance accuracy rates, below 75%, whichmeans that the OCR systems are insufficient to recognise printed Arabic text
images.
 Can Arabic text be effectively recognised by considering Arabic text as nondotted text and then corrected later on in order to recover the dotted from?
In this work, the PATRION OCR system was designed to recognise non-dotted
Arabic text images. In particular, the new feature extraction method,
implemented in the PATRION system (see chapter 5), has been developed forextracting features from non-dotted text, as it was assumed that all Arabic words
in the text images are non-dotted. The feature extraction method was effectively
able to extract features from non-dotted Arabic text. Then the recognition of dots
has been considered in the final stage of the development of the system byapplying a post-processing method to recover unrecognised dots. The postprocessing method was effectively able to recover the dotted form, as shown inchapter 9.
 Can a compression based method be effectively applied as a classifier for therecognition of the text features?
Our approach in this work was effectively able to recognise Arabic charactersby applying the PPM compression method as a classifier in the PATRION OCR
system in order to classify the feature strings obtained from the feature extraction
stage. The explanation of the implementation of the PPM compression method
as a classifier is shown in chapter 7, section 7.2.
 Can a compression based method be applied to Arabic OCR output that
contributes to significant improvement in Arabic text recognition accuracy?
157

A compression based correction method was applied as a post-processing
method to correct Arabic OCR output. This method has been applied to two
problems of Arabic OCR systems: adding dots to Arabic text and correcting the
OCR output. The method has successfully corrected OCR errors and dottedcharacters in Arabic OCR output. The post-processing method was able toincrease the edit distance accuracy for the PATRION OCR system from 77.3%
to 86.9%, and for a commercial Arabic OCR system from 70.2% to 77.1%,
which are significant improvements. The explanation of the implementation of
the compression method as a post-processing method is provided in chapter 8,
section 8.2.
9.5 Limitations of the Work
Various limitations of this work have occurred for various reasons. Firstly, theexperimental evaluation (presented in chapter 3) was limited to four Arabic OCR
systems, since we were not be able to obtain other Arabic OCR systems. Also, theevaluation study was only concerned with the output of the Arabic OCR systems
rather than how the output is produced, since accessing the submodules of the
Arabic OCR systems studied in chapter 3 was not possible.
Another limitation is that due to the limited availability and accessibility of Arabic
corpora, this work used a training corpus of only 31-millon Arabic words, which is
the BACC Corpus, for constructing the language model used in the post-processing
method. Using a larger Arabic corpus might result in better performance.
Finally, the performance of the PATRION OCR system was evaluated using only
two pitch sizes (12 and 24 ) in two styles (normal and italic) for four font types(Arabic Transparent, AdvertisingBold, Simplified Arabic and Traditional Arabic)
at 300 dots per inch (dpi). The OCR system can be evaluated using more font types
and pitch sizes by training various character models of different font types and pitch
sizes, as explained in chapter 7 (section 7.2.1). However, extracting feature strings
from pre-segmented character images for training purposes would be a time
consuming task.

158

9.6 Future WorkIn this work, various achievements have been made in the area of Arabic text
recognition. However, several observations have been noted for possible future
directions. The following areas should be considered for future work:Creating a noisy page-level text image dataset.

This study used the KFAD dataset for evaluating printed Arabic OCR systems as it
is freely available, paragraph-based, and comprises text images of different font
types, pitch sizes, and resolutions. However, the KFAD dataset is made up of noisefree text images. Thus, a noisy Arabic text image dataset is required to assess theeffectiveness of Arabic OCR systems on poor quality text images.
Implementing the thinning algorithm for different OCR systems.

This study has proposed an efficient thinning algorithm. It will be interesting tomeasure the impact of the proposed thinning algorithm on the performanceaccuracy of different Arabic OCR systems.
Including more objective performance metrics into the proposed evaluation
tool.

This study provided an evaluation tool with a new set of objective performance
metrics for assessing the performance of Arabic OCR with respect to the challengesof Arabic script. This tool can be enhanced by including different performance
metrics that can provide a better insight into the effectiveness of Arabic OCR
systems regarding the challenges of Arabic text. Since Arabic script has somecharacters that share an identical visual shape, performance metrics related to visualshape can be a further possible performance metric.
Applying the feature extraction method to handwritten text recognition.

The feature extraction method, which is presented in chapter 5, resembles the way
a human might write a word or a character with a pen. Therefore, this method could
be applied to handwritten text images and it may contribute significantly to theenhancement of the field of handwritten text recognition.
Using the PPM based method for diacritising OCR output text.

The experimental results presented in chapter 3 (section 3.6) concluded thatrecognising Arabic text with diacritics is still an open research problem. To solve
159this problem, the PPM compression based method could be used for diacritising
Arabic text in the same way it is used for adding dots to non-dotted Arabic text, as
described in chapter 8 (section 8.2). However, an Arabic corpus with diacritised
text is required for training.


Evaluating Arabic OCR approaches in terms of execution time.

This research focused on improving and evaluating the recognition accuracy of
printed Arabic OCR. However, it will be interesting to study the effectiveness of
OCR approaches in terms of both the execution time and recognition accuracy.

160

References
ABBYY OCR [WWW document], n.d. URL https://www.abbyy.com/en-gb/(accessed 4.15.17).
Abd, M., Paschos, G., 2007. Effective Arabic character recognition using
support vector machines. In Innovations and Advvanced Techniques in
Computer and Information Sciences and Engineering. Springer, pp. 7–11.
Abd, M., Al Rubeaai, S., Paschos, G., 2012. Hybrid features for an Arabic word
recognition system. Computer Technology and Application. David
publishing, 3(10), pp. 685–691.
AbdelRaouf, A.M., 2012. Offline printed Arabic character recognition. PhD
thesis, University of Nottingham.
Abdelraouf, A., Higgins, C.A., Khalil, M., 2008. A database for Arabic printed
character recognition. In International Conference Image Analysis andRecognition. Springer, pp. 567–578. DOI:10.1007/978-3-540-69812-8_56
Aboaisha, H., Xu, Z., El-Feghi, I., 2012. An investigation on efficient feature
extraction approaches for Arabic letter recognition. In: Proceedings of the
Queen’s Diamond Jubilee Computing and Engineering Annual Researchers’
Conference, pp. 80-85.
Abu-Ain, W., Abdullah, S.N.H.S., Bataineh, B., Abu-Ain, T., Omar, K., 2013.
Skeletonization algorithm for binary images. Procedia Technol, 11, 704–
709. DOI:10.1016/j.protcy.2013.12.248
Abu-Ain, W., Abdullah, S.N.H.S, Omar, K., 2014. A simple iterative thinningalgorithm for text and shape binary images. Journal of Theoretical &Applied Information Technology, 63(2), pp. 274–281.
Abu-Ain, W.A.K., Abdullah, S.N.H.S., Omar, K., Rahman, S.Z.A., 2018.
Automatic multi-lingual script recognition application. GEMA
Online®Journal of Language Studies, 18(3), pp. 203–221.
Abuhaiba, I.S.I., 2003. Skew correction of textural documents. Journal of King
Saud University-Computer and Information Sciences. Elsevier, 15, pp. 73–
93. DOI:10.1016/S1319-1578(03)80003-4
Abuhaiba, I.S.I., Mahmoud, S.A., Green, R.J., 1994. Recognition of handwritten
cursive Arabic characters. IEEE Transactions on Pattern Analysis andMachine Intelligence. IEEE, 16(6), pp. 664–672. DOI:10.1109/34.295912
Ahmad, I., 2016. Modeling and training options for handwritten Arabic text
recognition. PhD thesis, Technische Universität Dortmund.
Ahmad, I., Mahmoud, S.A., Fink, G.A., 2016. Open-vocabulary recognition ofmachine-printed Arabic text using hidden Markov models. Pattern
Recognition. Elsevier, 51, pp. 97–111. DOI:10.1016/j.patcog.2015.09.011
Ahmad, I., Rothacker, L., Fink, G.A., Mahmoud, S.A., 2013. Novel subcharacter HMM models for Arabic text recognition. In International
161

Conference on Document Analysis and Recognition. IEEE, pp. 658–662.
DOI:10.1109/ICDAR.2013.135
Ahmed, S. Bin, Naz, S., Razzak, M.I., Yusof, R., 2019. Arabic Cursive Text
Recognition from Natural Scene Images. Applied Sciences, 9(2), p. 236.
Ahmed, I., Mahmoud, S.A., Parvez, M.T., 2012. Printed Arabic text recognition.
In: Märgner, V., El Abed, H. (Eds.), Guide to OCR for Arabic Scripts.
Springer London, London, pp. 147–168. DOI:10.1007/978-1-4471-40726_7
Al-ani, H., Ban, N., Abass, H.M., 2014. Printed Arabic character recognition
using neural network. Journal of Emerging Trends in Computing andInformation Sciences. 5, pp. 64–66.
Al-Ayyoub, M., Nuseir, A., Alsmearat, K., Jararweh, Y., Gupta, B., 2018. Deeplearning for Arabic NLP: A survey. Journal of Computer Science, 26, pp.
522–531.
Al-Badr, B.H., 1995. A segmentation-free approach to text recognition withapplication to Arabic text. PhD thesis, University of Washington, Seattle,
WA, USA.
Al-Badr, B., Haralick, R.M., 1995. Segmentation-free word recognition withapplication to Arabic. In: Proceedings of 3rd International Conference on
Document Analysis and Recognition. IEEE, 1, pp. 355–359.
DOI:10.1109/ICDAR.1995.599012
Al-Badr, B., Haralick, R.M., 1998. A segmentation-free approach to text
recognition with application to Arabic text. International Journal on
Document Analysis and Recognition, 1, pp. 147–166.
Al-Badr, B., Mahmoud, S.A., 1995. Survey and bibliography of Arabic opticaltext recognition. Signal Processing, 41(1), 49–77. DOI:10.1016/01651684(94)00090-M
Al-Helali, B.M., Mahmoud, S.A., 2017. Arabic Online Handwriting Recognition(AOHR): A survey. ACM Computing Surveys, 50(3), p. 33.
Al-Muhtaseb, H., Mahmoud, S.A., Qahwaji, R.S., 2008. Recognition of off-line
printed Arabic text using hidden Markov models. Signal Processing, 88(12),pp. 2902–2912.
Al-Muhtaseb, H., Qahwaji, R., 2011. Arabic Optical Character Recognition:
Recent trends and future directions. In: Applied Signal and Image
Processing: Multidisciplinary Advancements. IGI Global, pp. 324–346.
Al-Rashaideh, H., 2006. Preprocessing phase for Arabic Word Handwritten
Recognition. Information Process, 6, pp. 11–19.
Al-Shatnawi, A.M., Al-Zawaideh, F.H., Al-Salameh, S., Omar, K., 2011. Offline
Arabic Text Recognition: An overview. World Computing Science andInformation Technology, 1, pp. 184–192.
Al-Shatnawi, A.M., Alfawwaz, B.M., Omar, K., Zeki, A.M., 2014. Skeleton
extraction: Comparison of five methods on the Arabic IFN/ENIT database.
In: 6th International Conference on Computer Science and Information
162

Technology (CSIT). IEEE, pp. 50–59.
Al-Shatnawi, A., Omar, K., 2008. Methods of Arabic language baseline
detection: The state of art. In International Journal of Computer Science andNetwork Security, 8, pp. 137–143.
Al-Shatnawi, A.M., Omar, K., 2009. Skew detection and correction technique for
Arabic document images based on centre of gravity. Department of System
Science and Management, Faculty of Information Science and Technology,
Universiti Kebangsaan Malaysia. Journal of Computer Science, 5(5), pp.
363–368. DOI:10.3844/jcssp.2009.363.368
Al-Shatnawi, A.M., Omar, K., 2014. The thinning problem in Arabic text
recognition: A comprehensive review. International Journal of Computer
Applications, 103(3), pp. 35–42.
Al-Yousefi, H., Udpa, S.S., 1992. Recognition of Arabic characters. IEEE
Transactions on Pattern Analysis & Machine Intelligence, 14, pp. 853–857.
DOI:10.1109/34.149585
Alginahi, Y., 2004. Computer analysis of composite documents with nonuniform background. PhD thesis, University of Windsor, Ontario, Canada.
Alginahi, Y., 2010. Preprocessing techniques in character recognition. In
Character Recognition. InTech, pp. 1–20.
Alginahi, Y.M., 2013. A survey on Arabic character segmentation. International
Journal on Document Analysis and Recognition (IJDAR), 16(2), pp. 105–
26. DOI:10.1007/s10032-012-0188-6
Alginahi, Y., 2017. Document processing and Arabic optical character
recognition: A user perspective. International Journal of Computer Scienceand Information Security, 15(12), pp. 86–97.
Alhawiti, K.M., 2014. Adaptive models of Arabic text. Phd thesis, Prifysgol
Bangor University, Bangor, UK.
Ali, M.A., 2012. An efficient thinning algorithm for Arabic OCR systems. Signal
Image Processing, 3(3), pp. 31–38.
Ali, M., bin Jumari, K., 2003. Skeletonization algorithm for an Arabic
handwriting. WSEAS Transactions on Computers, 2(3), pp. 662–667.
Aljarrah, I., Al-Khaleel, O., Mhaidat, K., Alrefai, M., Alzu’Bi, A., Rabab’Ah,
M., 2012. Automated system for Arabic optical character recognition withlookup dictionary. Journal of Emerging Technologies in Web Intelligence,
4(4), pp. 362–370. DOI:10.4304/jetwi.4.4.362-370
AlKhateeb, J., 2010. Word based off-line handwritten Arabic classification andrecognition. PhD thesis, School of Computing, Informatics and Media,
University of Bradford.
AlKhateeb, J.H., Jiang, J., Ren, J., Ipson, S., 2009. Component-based
segmentation of words from handwritten Arabic text. International Journalof Computer Systems Science and Engineering, 5(1), pp. 54–58.

163

Alkhazi, I.S., Alghamdi, M., Teahan, W.J., 2017. Tag based models for Arabic
text compression. In Intelligent Systems Conference (IntelliSys). IEEE, pp.
697–705.
Alkhazi, I.S., Teahan, W.J., 2017. Classifying and segmenting Classical andModern Standard Arabic using minimum cross-entropy. In International
Journal of Advanced Computer Science and Applications (IJACSA), 8(4),pp. 421–430. DOI:10.14569/IJACSA.2017.080456
Alkholy, M.D.A.-Z., 2016. Arabic optical character recognition using local
invariant features. PhD thesis, Faculty of Computers and Information,
Menoufia University.
Almahdawi, A., Teahan, W.J., 2017. Emotion recognition in text using PPM. In:
International Conference on Innovative Techniques and Applications ofArtificial Intelligence. Springer, pp. 149–155. DOI:10.1007/978-3-31971078-5_13
Almohri, H., Gray, J.S., Alnajjar, H., 2007. A real-time DSP-based opticalcharacter recognition system for isolated Arabic characters using the TI
TMS320C6416T. PhD thesis, University of Hartford.
AlSalamah, S., King, R., 2018. Towards the Machine Reading of Arabic
Calligraphy: A Letters Dataset and Corresponding Corpus of Text. In: IEEE
2nd International Workshop on Arabic and Derived Script Analysis andRecognition (ASAR). IEEE, pp. 19–23. DOI:10.1109/ASAR.2018.8480228
Altamimi, M.J., Teahan, W., 2017. Gender and authorship categorisation of
Arabic text from Twitter using PPM. In International Journal of Computer
Science & Information Technology (IJCSIT), 9, pp. 131–140.
DOI:10.5121/ijcsit.2017.9212
Altuwaijri, M., Bayoumi, M., 1995. A new thinning algorithm for Arabic
characters using self-organizing neural network. In: IEEE International
Symposium on Circuits and Systems (ISCAS ’95). IEEE, 3, pp. 1824–1827.
Amara, M., Ghedira, K., Zidi, K., Zidi, S., 2015. A comparative study of multiclass support vector machine methods for Arabic characters recognition. In:
IEEE/ACS 12th International Conference of Computer Systems andApplications (AICCSA). IEEE, pp. 1–6.
Amara, M., Zidi, K., Ghedira, K., Zidi, S., 2016. New rules to enhance theperformances of histogram projection for segmenting small-sized Arabic
words. In: Hybrid Intelligent Systems. Springer, pp. 167–176.
Amara, M., Zidi, K., Zidi, S., Ghedira, K., 2014. Arabic character recognition
based M-SVM. In: International Conference on Advanced Machine
Learning Technologies and Applications. Springer, pp. 18–25.
Amin, A., 1998. Off-line Arabic character recognition. Pattern Recognition,
31(5), pp. 517–530. DOI:10.1016/S0031-3203(97)00084-8
Amin, A., Masini, G., 1986. Machine recognition of multi font printed {Arabic}
texts. In: Eighth International Conference on Pattern Recognition. Paris,
France, pp. 392–395.
164

Arica, N., Yarman-Vural, F.T., 2002. Optical character recognition for cursive
handwriting. IEEE Transactions on Pattern Analysis and MachineIntelligence. IEEE, 24(6), pp. 801–813.
DOI:10.1109/TPAMI.2002.1008386
Arica, N., Yarman-Vural, F.T., 2001. An overview of character recognition
focused on off-line handwriting. IEEE Transactions on Systems, Man, andCybernetics, Part C Applications and Reviews, 31(2), pp. 216–233.
DOI:10.1109/5326.941845
Arora, S., Bhattacharjee, D., Nasipuri, M., Malik, L., Kundu, M., Basu, D.K.,
2010. Performance comparison of SVM and ANN for handwritten
Devnagari character recognition. International Journal of Computer Science,
7, pp. 1–10.
Awaida, S.M., Khorsheed, M.S., 2012. Developing discrete density: Hidden
Markov models for Arabic printed text recognition. Proc. 2012 IEEE
International Conference on Computational Intelligence and Cybernetics(CyberneticsCom). IEEE, pp. 35–39.
DOI:10.1109/CyberneticsCom.2012.6381612
Baik, M.K., 1992. History of Arabic Language. Dar Sa’ad Aldin, Damascus 1.
Baird, H.S., 1995. The skew angle of printed documents. In: Document Image
Analysis. pp. 204–208.
Bassil, Y., Alwani, M., 2012. OCR Post-processing error correction algorithm
using Google’s online spelling suggestion. Journal of Emerging Trends in
Computing and Information Sciences, 3(1), pp. 90–99.
Ben Amor, N., Ben Amara, N.E. 2006. Multifont Arabic characters recognition
using HoughTransform and HMM/ANN Classification. Journal ofMultimedia, 1(2), pp. 50–54.
Ben Amor, N., Ben Amara, N.E. 2012. A novel method for multifont Arabic
characters features extraction. INTECH Open Access Publisher.
Ben Moussa, S., Zahour, A., Benabdelhafid, A., Alimi, A.M., 2010. Newfeatures using fractal multi-dimensions for generalized Arabic fontrecognition. Pattern Recognition Letters. Elsevier, 31(5), pp. 361–371.
DOI:10.1016/j.patrec.2009.10.015
Bobik, J., Sayre, K.M., 1963. Pattern recognition mechanisms and St. Thomas’
theory of abstraction. Revue philosophique de Louvain, 61(69), pp. 24–43.
Buades, A., Coll, B., Morel, J., 2005. A review of image denoising algorithms,
with a new one. Multiscale Modeling & Simulation, 4(2), pp. 490–530.
DOI:10.1137/040616024
Bukhari, S.S., Shafait, F., Breuel, T.M., 2011. High performance layout analysis
of Arabic and Urdu document images. In: International Conference on
Document Analysis and Recognition (ICDAR). IEEE, pp. 1275–1279.
DOI:10.1109/ICDAR.2011.257
Carrasco, R.C., 2014. An open-source OCR evaluation tool. In: FirstInternational Conference on Digital Access to Textual Cultural Heritage
165

(DATeCH ’14). ACM, New York, NY, USA, pp. 179–184.
DOI:10.1145/2595188.2595221
Chatbri, H., Kameyama, K., 2014. Using scale space filtering to make thinningalgorithms robust against noise in sketch images. Pattern Recognition
Letters. Elsevier, 42, pp. 1–10. DOI:10.1016/j.patrec.2014.01.011
Chen, C.H., DeCurtins, J.L., 1993. Word recognition in a segmentation-free
approach to OCR. In: Proceedings of 2nd International Conference on
Document Analysis and Recognition (ICDAR'93). IEEE, pp. 573–576.
DOI:10.1109/ICDAR.1993.395670
Cheriet, M., Kharma, N., Liu, C., Suen, C., 2007. Character recognition systems:
A guide for students and practitioners. John Wiley & Sons.
DOI:10.1002/9780470176535
Cheung, A., Bennamoun, M., Bergmann, N.W., 2001. Arabic optical character
recognition system using recognition-based segmentation. Pattern
Recognition. Elsevier, 34(2), pp. 215–233. DOI:10.1016/S00313203(99)00227-7
Cho, W., Lee, S.W., Kim, J.H., 1995. Modeling and recognition of cursive words
with hidden Markov models. Pattern Recognition. Elsevier, 28(12), pp.
1941–1953. DOI:10.1016/0031-3203(95)00041-0
Choudhary, A., 2014. A review of various character segmentation techniques forcursive handwritten words recognition. International Journal of Information& Computation Technology, 4(6), 559–564.
Cleary, J., Witten, I., 1984. Data compression using adaptive coding and partial
string matching. IEEE Transactions on Communications, 32(4), 396-402.
Cowell, J., Hussain, F., 2001. Thinning Arabic characters for feature extraction.
In: Proceedings of the International Conference on Information
Visualisation. IEEE, pp. 181–185. DOI:10.1109/IV.2001.942056
Dahi, M., Semary, N.A., Hadhoud, M.M., 2015. Primitive printed Arabic Optical
Character Recognition using statistical features. In: IEEE SeventhInternational Conference on Intelligent Computing and Information Systems(ICICIS). IEEE, pp. 567–571. DOI:10.1109/IntelCIS.2015.7397278
Damien, P., Wakim, N., Egea, M. 2009. Phoneme-viseme mapping for Modern,
Classical Arabic language. In: International Conference on Advances in
Computational Tools for Engineering Applications (ACTEA). IEEE, pp.
547–552. DOI:10.1109/ACTEA.2009.5227875
Devi, H., 2006. Thinning: A preprocessing technique for an OCR system for the
Brahmi script. Ancient Asia, 1, pp. 167–172.
Dong, J.X., Dominique, P., Krzyzak, A., Suen, C.Y., 2005. Cursive word
skew/slant corrections based on Radon transform. In Eighth International
Conference on Document Analysis and Recognition (ICDAR'05). IEEE, pp.
478–483. DOI:10.1109/ICDAR.2005.83
Doush, I.A., Al-Trad, A.M., 2016. Improving post-processing optical character
recognition documents with Arabic language using spelling error detection
166

and correction. International Journal of Reasoning-based Intelligent
Systems, 8(4), pp. 91–103. DOI:10.1504/IJRIS.2016.082957
Doush, I.A., AlKhateeb, F., Gharaibeh, A.H., 2018a. A novel Arabic OCR postprocessing using rule-based and word context techniques. International
Journal on Document Analysis and Recognition, 21(2), pp. 77–89.
DOI:10.1007/s10032-018-0297-y
Doush, I.A., AIKhateeb, F., Gharibeh, A.H., 2018b. Yarmouk Arabic OCR
dataset. In: 8th International Conference on Computer Science andInformation Technology (CSIT). IEEE, pp. 150–154.
Drira, F., Lebourgeois, F., 2012. Denoising textual images using local/non-local
smoothing filters: A comparative study. In International Conference on
Frontiers in Handwriting Recognition. IEEE, pp. 521–526.
DOI:10.1109/ICFHR.2012.198
Due Trier, Ø., Jain, A.K., Taxt, T., 1996. Feature extraction methods forcharacter recognition: A survey. Pattern Recognition, 29(4), pp. 641–662.
DOI:10.1016/0031-3203(95)00118-2
El-Dabi, S.S., Ramsis, R., Kamel, A., 1990. Arabic character recognition system:
A statistical approach for recognizing cursive typewritten text. Pattern
Recognition, 23(5), pp. 485–495. DOI:10.1016/0031-3203(90)90069-W
El-Hajj, R., Likforman-Sulem, L., Mokbel, C., 2005. Arabic handwriting
recognition using baseline dependant features and hidden Markov modeling.
In International Conference on Document Analysis and Recognition(ICDAR). IEEE, pp. 893–897. DOI:10.1109/ICDAR.2005.53
El-Mahallawy, M.S.M., 2008. A large scale HMM-based Omni font-written
OCR system for cursive scripts. PhD thesis, Faculty of Engineering, Cairo
University, Giza, Egypt.
Elgammal, A.M., Ismail, M.A. 2001. A graph-based segmentation and feature
extraction framework for Arabic text recognition. In: Proceedings of the
Sixth International Conference on Document Analysis and Recognition.
IEEE, pp. 622–626. DOI:10.1109/ICDAR.2001.953864
Elrube, I.A., El Sonni, M.T., Saleh, S.S., 2010. Printed Arabic sub-wordrecognition using moments. World Academy of Science, Engineering andTechnology, International Journal of Electrical, Computer, Energetic,
Electronic and Communication Engineering, 4(6), pp. 959–963.
Erlandson, E.J., Trenkle, J.M., Vogt, R.C., 1996. Word-level recognition ofmultifont Arabic text using a feature vector matching approach. In:
Document Recognition III. International Society for Optics and Photonics,
pp. 63–71.
Etidal, 2018. Etidal – Global center for combating extremist ideology [WWW
document]. URL https://etidal.org/en/home/ (accessed 3.6.19).
Freeman, H., 1961. On the encoding of arbitrary geometric configurations. IRE
Transactions on Electronic Computers, pp. 260–268.
DOI:10.1109/TEC.1961.5219197
167

Gao, X., Xiao, B., Tao, D., Li, X., 2010. A survey of graph edit distance. PatternAnalysis and Applications, 13(1), pp. 113–129. DOI:10.1007/s10044-0080141-y
Garcia, A.L., 2005. Arabic Learning Materials [WWW Document]. URL
https://www.scribd.com/document/294105424/Arabic-Writing-SheetRevised (accessed 3.2.18).
Ghosh, D., Dube, T., Shivaprasad, A., 2010. Script recognition: A review. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 32(2), pp.
2142–2161. DOI:10.1109/TPAMI.2010.30
Gonzalez, R., Woods, R., 2002. Digital image processing. Prentice Hall.
DOI:10.1016/0734-189X(90)90171-Q
Gouda, A.M., Rashwan, M.A., 2004. Segmentation of connected Arabic
characters using hidden Markov models. In: 2004 IEEE International
Conference on Computational Intelligence for Measurement Systems andApplications (CIMSA). IEEE, pp. 115–119.
Goyal, G., Dutta, M., 2016a. Design of Pixel neighborhood based Offline
Handwritten Thinning Framework for Devnagri Numeral Script using
Elman Neural Network. International Journal of Computer Science andInformation Security, 14(7), p. 369.
Goyal, G., Dutta, M., 2016b. Experimental approach for performance analysis ofthinning algorithms for Offline Handwritten Devnagri Numerals. Indian
Journal of Science and Technology, 9(30) pp. 1–10.
Guo, Z., Hall, R.W., 1992. Fast fully parallel thinning algorithms. CVGIP Image
Understanding, 55(3), pp. 317–328. DOI:10.1016/1049-9660(92)90029-3
Hamza, A.A., 2008. Back propagation neural network Arabic charactersclassification module utilizing Microsoft word. Journal of Computer
Science, 4(9), p. 744.
Hassin, A.H., Tang, X.-L., Liu, J.-F., Zhao, W., 2004. Printed Arabic character
recognition using HMM. Journal of Computer Science and Technology,
19(4), pp. 538–543. DOI:10.1007/BF02944755
Hilditch, C., 1969. Linear skeletons from square cupboards. In: Meltzer, B.,
Michie, D. (Eds.), Machine Intelligence 4. Edinburgh University Press, p.
403.
Hilditch, C., 1983. Comparison of thinning algorithms on a parallel processor.
Image and Vision Computing, 1(3), pp. 115–132. DOI:10.1016/02628856(83)90063-X
Hossain, M.Z., 2012. Rapid feature extraction for Optical Character Recognition.
arXiv preprint, pp. 1–5.
Hosseini, H.M.M., 1997. Analysis and recognition of Persian and Arabic
handwritten characters. PhD thesis, Department of Electrical and Electronic
Engineering, University of Adelaide.
Huang, L., Wan, G., Liu, C., 2003. An improved parallel thinning algorithm.
Proc. Int. Conference on Document Analysis and Recognition (ICDAR), pp.
168

780–783. DOI:10.1109/ICDAR.2003.1227768
Hull, J., 1998. Document image skew detection: Survey and annotatedbibliography. Ser. Mach. Perception and Artificial Intelligence. Document
Analysis Systems II, pp. 40–64.
Jain, M., Mathew, M., Jawahar, C. V., 2018. Unconstrained OCR for Urdu using
deep CNN-RNN hybrid networks, in: Proceedings of the 4th Asian
Conference on Pattern Recognition (ACPR 2017). IEEE, pp. 747–752.
DOI:10.1109/ACPR.2017.5
Jambi, H., 2014. King Abdullah Bin Abdulaziz AL-Saud Initiative for Arabic
Content [WWW document]. URL
https://archive.org/details/KingAbdullahBinAbdulazizAlsaudInitiativeForArabicContent (accessed 2.10.19).
Jang, B.K., Chin, R.T., 1992. One-pass parallel thinning: Analysis, properties,
and quantitative evaluation. IEEE Transactions on Pattern Analysis &Machine Intelligence, 14, pp. 1129–1140. DOI:10.1109/34.166630
Jumari, K., Ali, M., 2012. A survey and comparative evaluation of selected offline Arabic handwritten character recognition systems. Jurnal Teknologi,
36(1), pp. 1–18.
Kandel, S., Orliaguet, J.P., Viviani, P., 2000. Perceptual anticipation in
handwriting: The role of implicit motor competence. Perception &Psychophysics, 62(4), pp. 706–716. DOI:10.3758/BF03206917
Kannan, R.J., Subramanian, S., 2015. An adaptive approach of Tamil character
recognition using deep learning with big data: A survey. In Emerging ICT
for Bridging the Future-Proceedings of the 49th Annual Convention of theComputer Society of India (CSI). Springer, 1, pp. 557–567.
DOI:10.1007/978-3-319-13728-5_63
Kanungo, T., Marton, G.A., Bulbul, O. 1999a. Performance evaluation of two
Arabic OCR products. In 27th AIPR Workshop: Advances in ComputerAssisted Recognition. International Society for Optics and Photonics, pp.
76–83. DOI:10.1117/12.339809
Kanungo, T., Marton, G.A., Bulbul, O. 1999b. OmniPage vs. Sakhr: Paired
model evaluation of two Arabic OCR products. In Document Recognition
and Retrieval. International Society for Optics and Photonics, pp. 109–120.
Katz, S.M., 1987. Estimation of probabilities from sparse data for the language
model component of a speech recognizer. IEEE Transactions on Acoustics,
Speech, and Signal Processing, 35(3), pp. 400–401.
DOI:10.1109/TASSP.1987.1165125
Kef, M., Chergui, L., Chikhi, S., 2012. Comparative study of the use ofgeometrical moments for Arabic handwriting recognition. In: 6thInternational Conference on Sciences of Electronics, Technologies ofInformation and Telecommunications (SETIT). IEEE, pp. 303–308.
Khmelev, D.V, Teahan, W.J., 2003. A repetition based measure for verificationof text collections and for text categorization. In: Proceeding of the 26th169

Annual International ACM SIGIR Conference on Research andDevelopment in Information Retrieval. ACM, pp. 104–110.
Khorsheed, M.S., 2004. A lexicon based system with multiple HMMs torecognise typewritten and handwritten Arabic words. The 17th National
Computer Conference, Madinah, Saudi Arabia. pp. 5–8.
Khorsheed, M.S., 2002. Off-line Arabic character recognition: A review. PatternAnalysis & Applications, 5(1), pp. 31-45. DOI:10.1007/s100440200004
Khorsheed, M.S., 2007. Offline recognition of omnifont Arabic text using the
HMM ToolKit (HTK). Pattern Recognition Letters, 28(12), pp. 1563–1571.
DOI:10.1016/j.patrec.2007.03.014
Khorsheed, M.S., 2015. Recognizing cursive typewritten text using
segmentation-free system. The Scientific World Journal, 1, pp. 7–14.
Khorsheed, M.S., Clocksin, W.F., 1999. Structural features of cursive Arabic
script. In: British Machine Vision Conference (BMVC). pp. 1–10.
Khorsheed, M., Clocksin, W., 2000. Multi-font Arabic word recognition using
spectral features. In: 15th International Conference on Pattern Recognition.
IEEE, 4, pp. 543–546.
Ko, D., Lee, C., Han, D., Ohk, H., Kang, K., Han, S., 2018. Approach formachine-printed Arabic character recognition: The-state-of-the-art deeplearning method. Electronic Imaging, pp. 1–8.
Kocyigit, P., 2012. Agent based optical character recognition, Master’s
dissertation. Prifysgol Bangor University, Bangor, UK.
Koteswara Rao, D., Negi, A., 2016. Advances in signal processing andintelligent recognition systems: Proceedings Second International
Symposium on Signal Processing and Intelligent Recognition Systems(SIRS-2015) December 16-19, 2015, Trivandrum, India. In: Thampi, M.S.,
Bandyopadhyay, S., Krishnan, S., Li, K.-C., Mosin, S., Ma, M. (Eds.).
Springer International Publishing, Cham, pp. 633–644. DOI:10.1007/978-3319-28658-7_54
Krayem, A.G., 2013. A high level approach to Arabic sentence recognition. PhD
thesis, Nottingham Trent University.
Kumar, G., Bhatia, P.K., 2014. A detailed review of feature extraction in image
processing systems. In: International Conference on Advanced Computing
and Communication Technologies (ACCT). IEEE, pp. 5–12.
DOI:10.1109/ACCT.2014.74
Lam, L., Lee, S.W., 1992. Thinning methodologies—a comprehensive survey.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(9), pp.
869–885. DOI:10.1109/34.161346
Lawgali, A., 2015. A survey on Arabic character recognition. International
Journal of Signal Processing, Image Processing and Pattern Recognition,
8(2), pp. 401–426.
Levenshtein, V.I., 1966. Binary codes capable of correcting deletions, insertions,and reversals. In Soviet physics doklady, 10(8), pp. 707–710. DOI:citeulike170

article-id:311174
Liu, C.L., Fujisawa, H., 2008. Classification and learning methods for character
recognition: Advances and remaining problems. In Machine Learning inDocument Analysis and Recognition. Springer, pp. 139–161.
DOI:10.1007/978-3-540-76280-5_6
Lorigo, L., Govindaraju, V., 2005. Segmentation and pre-recognition of Arabic
handwriting. In: Proceedings of the International Conference on Document
Analysis and Recognition (ICDAR). IEEE, pp. 605–609.
DOI:10.1109/ICDAR.2005.207
Lorigo, L.M., Govindaraju, V., 2006. Offline Arabic handwriting recognition: A
survey. IEEE Transactions on Pattern Analysis and Machine Intelligence,
28(5), pp. 712–724. DOI:10.1109/TPAMI.2006.102
Luqman, H., Mahmoud, S.A., Awaida, S., 2014. KAFD Arabic font database.
Pattern Recognition, 47, pp. 2231–2240. DOI:10.1016/j.patcog.2013.12.012
Magdy, W., Darwish, K., 2008. Effect of OCR error correction on Arabic
retrieval. Information Retrieval, Boston, 11(5), pp. 405–425.
Mahmoud, S.A., 1994. Arabic character recognition using Fourier descriptors
and character contour encoding. Pattern Recognition, 27(6), pp. 815–824.
DOI:10.1016/0031-3203(94)90166-X
Mahmoudb, S.A., 1995. Survey and bibliography of Arabic optical text
recognition Signal processing, 41(1), pp. 49-77.
Margner, V., El Abed, H., 2009. Arabic word and text recognition: Current
developments. In: Proceedings of the Second International Conference on
Arabic Language Resources and Tools, Cairo, Egypt, MEDAR Consortium.
Mari, J.F., 1989. Machine recognition and correction of printed Arabic text.
IEEE Transactions on systems, man, and cybernetics, 19(5), pp. 1300–1306.
DOI:10.1109/21.44052
Mehran, R., Pirsiavash, H., Razzazi, F., 2005. A front-end OCR for omni-font
Persian/Arabic cursive printed documents. In Digital Image Computing:Techniques and Applications (DICTA’05). IEEE, p. 56.
Melhi, M., Ipson, S.S., Booth, W., 2001. A novel triangulation procedure forthinning hand-written text. Pattern Recognition Letters, 22(10), pp. 1059–
1071. DOI:10.1016/S0167-8655(01)00038-1
Mihov, S., Schulz, K.U., Ringlstetter, C., Dojchinova, V., Nakova, V.,
Kalpakchieva, K., Gerasimov, O., Gotscharek, A., Gercke, C., 2005. A
corpus for comparative evaluation of OCR software and postcorrection
techniques. In the International Conference on Document Analysis andRecognition (ICDAR2005). IEEE, pp. 162–166.
DOI:10.1109/ICDAR.2005.6
Moubtahij, E., Hicham, A.H., Satori, K., 2014. Review of feature extraction
techniques for offline handwriting Arabic text recognition. International
Journal of Advances in Engineering & Technology, 7(1), pp. 50–58.
171

Naccache, N.J., Shinghal, R., 1984. SPTA: A proposed algorithm for thinningbinary patterns. IEEE ransactions on Systems, Man, and Cybernetics. SMC,
3, pp. 409–418. DOI:10.1109/TSMC.1984.6313233
Nagy, G., Seth, S., Viswanathan, M., 1992. A prototype document image
analysis system for technical journals. Computer (Long Beach, CA), 25(7),pp. 10–22. DOI:10.1109/2.144436
Najoua, B.A., Noureddine, E., 1995. A robust approach for Arabic printed
character segmentation. In: Proceedings of the Third International
Conference on Document Analysis and Recognition. IEEE, 2, pp. 865–868.
Nartker, T.A., Rice, S.V, Lumos, S.E., 2005. Software tools and test data forresearch and testing of page-reading OCR systems. In: International
Symposium on Electronic Imaging Science and Technology, pp. 37–48.
Nashwan, F., Rashwan, M., Al-Barhamtoshy, H., Abdou, S., Moussa, A., 2017.
A holistic technique for an Arabic OCR system. Journal of Imaging, 4(1),pp. 6–17.
Natarajan, P., Saleem, S., Prasad, R., MacRostie, E., Subramanian, K., 2008.
Multi-lingual offline handwriting recognition using hidden Markov models:A script-independent approach. In: Arabic and Chinese Handwriting
Recognition. Springer, pp. 231–250. DOI:10.1007/978-3-540-78199-8_14
Nawaz, S.N., Sarfraz, M., Zidouri, A., Al-Khatib, W.G., 2003. An approach tooffline Arabic character recognition using neural networks. In: Proceedingsof the 10th IEEE International Conference on Electronics, Circuits andSystems (ICECS). IEEE, 3. pp. 1328–1331.
DOI:10.1109/ICECS.2003.1301760
Naz, S., Hayat, K., Imran Razzak, M., Waqas Anwar, M., Madani, S.A., Khan,
S.U., 2014. The optical character recognition of Urdu-like cursive scripts.
In: Pattern Recognition, 47(3), pp. 1229–1248.
DOI:10.1016/j.patcog.2013.09.037
Naz, S., Umar, A.I., Shirazi, S.H., Ahmed, S.B., Razzak, M.I., Siddiqi, I., 2015.
Segmentation techniques for recognition of Arabic-like scripts: A
comprehensive survey. Education and Information Technologies, 21 (5), pp.
1–17.
Neuhaus, M., Bunke, H., 2007. A quadratic programming approach to the graphedit distance problem. Graph-Based Represent. Pattern Recognition.
Springer, pp. 92–102. DOI:10.1007/978-3-540-72903-7_9
Nixon, M.S., Aguado, A.S., 2008. Feature extraction and image processing.
Academic Press. DOI:10.1016/B978-0-12-396549-3.00001-X
O’Gorman, L., 1993. The document spectrum for page layout analysis. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 15(11), 1162–
1173. DOI:10.1109/34.244677
Omar, K., Mahmod, R. bin Sulaiman, M. N., bin Ramli, A. R., 2000. The
removal of secondaries of Jawi characters. 2000 TENCON Proceedings.
Intelligent Systems and Technologies for the New Millennium (Cat.
172

No.00CH37119). IEEE, 2, pp. 149–152.
DOI:10.1109/TENCON.2000.888408
Optical Character Recognition (OCR) [WWW document], n.d. URL
http://www.sakhr.com/index.php/en/solutions/ocr (accessed 4.15.17).
Otus, N., 1979. A threshold selection method from gray-level histograms. IEEE
Transactions on Systems, 9(1), pp. 62–66.
Oujaoura, M., El Ayachi, R., Fakir, M., Bouikhalene, B., Minaoui, B., 2012.
Zernike moments and neural networks for recognition of isolated Arabic
characters. International Journal of Computer Engineering Science, 2(3), pp.
17–25.
Pal, U., Wakabayashi, T., Kimura, F., 2009. Comparative study of Devnagari
handwritten character recognition using different features and classifiers. In:
10th International Conference on Document Analysis and Recognition.
IEEE, pp. 1111–1115. DOI:10.1109/ICDAR.2009.244
Parhami, B., Taraghi, M., 1981. Automatic recognition of printed Farsi texts.
Pattern Recognition, 14, pp. 395–403.
Parker, J.R., 2011. Algorithms for image processing and computer vision. John
Wiley & Sons. DOI:10.1002/1521-3773(20010316)40:6<9823::AIDANIE9823>3.3.CO;2-C
Parvez, M.T., Mahmoud, S.A., 2013. Offline Arabic handwritten text
recognition: A survey. ACM Computing Surveys, 45(2), pp. 23:1–23:35.
DOI:10.1145/2431211.2431222
Pati, P.B., Ramakrishnan, A.G., 2005. OCR in Indian scripts: A survey. IETE
Technical Review, 22(3), pp. 217–227.
Pavlidis, T., 1993. Recognition of printed text under realistic conditions. Pattern
Recognition Letters, 14(4), pp. 317–326. DOI:10.1016/01678655(93)90097-W
Pechwitz, M., Margner, V., 2002. Baseline estimation for Arabic handwritten
words. In: Proceedings of the Eighth International Workshop on Frontiers in
Handwriting Recognition (IWFHR). IEEE, pp. 479–484.
DOI:10.1109/IWFHR.2002.1030956
Pi, Y., Liao, W., Liu, M., Lu, J., 2008. Theory of cognitive pattern recognition.
In Pattern Recognition Techniques, Technology and Applications. InTech.
DOI:10.5772/6251
Plamondon, R., Srihari, S.N., 2000. On-line and off-line handwriting recognition:
A comprehensive survey. IEEE Transactions on Pattern Analysis andMachine Intelligence, 22(1), pp. 63–84. DOI:10.1109/34.824821
Prasad, R., Saleem, S., Kamali, M., Meermeier, R., Natarajan, P., 2008.
Improvements in hidden Markov model based Arabic OCR. In: Proceedingsof the19th International Conference on Pattern Recognition. IEEE, pp. 1–4.
DOI:10.1109/ICPR.2008.4761446

173

Radwan, M.A., Khalil, M.I., Abbas, H.M., 2018. Neural networks pipeline foroffline machine printed Arabic OCR. Neural Processing Letters, 48(2), pp.
769–787. DOI:10.1007/s11063-017-9727-y
Rahal, N., Tounsi, M., Alimi, A.M., 2018. Auto-Encoder-BoF/HMM System for
Arabic Text Recognition. arXiv Preprint.
Rahman, A.F.R., Fairhurst, M.C., 2003. Multiple classifier decision combination
strategies for character recognition: A review. Document Analysis andRecognition. Springer, 5(4), pp. 166–194. DOI:10.1007/s10032-002-0090-8
Rashid, S.F., 2014. Optical character recognition: A combined ANN/HMM
approach. PhD thesis, Technische Universität Kaiserslautern.
Rashid, S.F., Schambach, M.-P., Rottland, J., von der Nüll, S., 2013. Low
resolution Arabic recognition with multidimensional recurrent neuralnetworks. In: Proceedings of the 4th International Workshop on
Multilingual OCR. ACM.
Rice, S.V., 1996. Measuring the accuracy of page-reading systems. University of
Nevada, Las Vegas.
Saabni, R., 2015. Efficient recognition of machine printed Arabic text using
partial segmentation and Hausdorff distance. In: the 6th International
Conference of Soft Computing and Pattern Recognition (SoCPaR). IEEE,
pp.284–289. DOI:10.1109/SOCPAR.2014.7008020
Saad, M., Ashour, W., 2010. OSAC: Open Source Arabic Corpora. In: the 6thInternational Symposium on Electrical and Electronics Engineering andComputer Science (EECS’10), Lefke, Cyprus. pp. 118–123.
DOI:10.13140/2.1.4664.9288
Sabbour, N., Shafait, F., 2013. A segmentation-free approach to Arabic and Urdu
OCR. In Document Recognition and Retrieval. International Society for
Optics and Photonics, pp. 86580N–86580N-12.
Saber, S., Ahmed, A., Elsisi, A., Hadhoud, M., 2016. Performance evaluation of
Arabic optical character recognition engines for noisy inputs. In: 1stInternational Conference on Advanced Intelligent System and Informatics(AISI2015). Springer, Beni Suef, Egypt, pp. 449–459.
Saber, S., Ahmed, A., Hadhoud, M., 2014. Robust metrics for evaluating Arabic
OCR systems. In: First International Image Processing, Applications andSystems Conference (IPAS). IEEE, pp. 1–6.
DOI:10.1109/IPAS.2014.7043272
Saeed, K., Tabędzki, M., Rybnik, M., Adamski, M., 2010. K3M: A universal
algorithm for image skeletonization and a review of thinning techniques.
International Journal of Applied Mathematics and Computer Science, 20(2),317–335. DOI:10.2478/v10006-010-0024-4
Sarfraz, M., Nawaz, S.N., Al-Khuraidly, A., 2003. Offline Arabic text
recognition system. In: Proceedings International Conference on Geometric
Modeling and Graphics. IEEE, pp. 30–35.
DOI:10.1109/GMAG.2003.1219662
174

Saudagar, A.K.J., Mohammed, H.V., 2016. Open CV based implementation of
Zhang-Suen thinning algorithm using Java for Arabic text recognition. In:
Information Systems Design and Intelligent Applications. Springer, pp.
265–271.
Sawy, A. El, El-Bakry, H., Loey, M., 2017. CNN for handwritten Arabic digits
recognition based on LeNet-5. In: International Conference on AdvancesIntelligent Systems and Informatics. Springer.
Shaaban, Z., 2008. A new recognition scheme for machine-printed Arabic texts
based on neural networks. In: Proceedings of World Academy of Science,
Engineering and Technology, pp. 25–27.
Shafait, F., Adnan-ul-Hasan, Keysers, D., Breuel, T.M., 2006. Layout analysis of
Urdu document images. In: 10th IEEE International Multitopic Conference(INMIC). IEEE, pp. 293–298. DOI:10.1109/INMIC.2006.358180
Shafii, M., 2014. Optical character recognition of printed Persian/Arabic
documents. PhD thesis, University of Windsor.
Shaker, A.S., 2018. Recognition of Off-line Printed Arabic Text Using Hidden
Markov Models. Ibn AL-Haitham Journal for Pure and Applied Science,31(2), 230–238.
Sharma, D.V., Saini, G., Joshi, M., 2012. Statistical feature extraction methods
for isolated handwritten Gurumukhi script. International Journal ofEngineering Research and Application, 2, 380–384.
Shi, Z., Setlur, S., Govindaraju, V., 2012. Guide to OCR for Arabic scripts. In:
Märgner, V., El Abed, H. (Eds.), Springer London, London, pp. 79–102.
DOI:10.1007/978-1-4471-4072-6_4
Slimane, F., Ingold, R., Hennebert, J., 2018. ICDAR 2017 competition on multifont and multi-size digitally represented Arabic text. In: Proceedings of theInternational Conference on Document Analysis and Recognition (ICDAR).
IEEE, 1, pp. 1466–1472. DOI:10.1109/ICDAR.2017.239
Slimane, F., Ingold, R., Kanoun, S., Alimi, A.M., Hennebert, J., 2009. A new
Arabic printed text image database and evaluation protocols. In:
Proceedings of the International Conference on Document Analysis andRecognition (ICDAR). IEEE, pp. 946–950. DOI:10.1109/ICDAR.2009.155
Slimane, F., Kanoun, S., El-Abed, H., Alimi, A.M., Ingold, R., Hennebert, J.,
2011. ICDAR 2011: Arabic recognition competition: Multi-font multi-size
digitally represented text. In: Proceedings of the International Conference
on Document Analysis and Recognition (ICDAR). IEEE, pp. 1449-1453.
DOI:10.1109/ICDAR.2011.288
Slimane, F., Kanoun, S., Hennebert, J., Alimi, A.M., Ingold, R., 2013. A study
on font-family and font-size recognition applied to Arabic word images at
ultra-low resolution. Pattern Recognition Letters, 34(2), pp. 209–218.
DOI:10.1016/j.patrec.2012.09.012
Smith, R., 2007. An overview of the Tesseract OCR engine. In: Proceedings ofthe International Conference on Document Analysis and Recognition, IEEE.
175

Smith, R., Antonova, D., Lee, D.-S., 2009. Adapting the Tesseract open source
OCR engine for multilingual OCR. In: Proceedings of the International
Workshop on Multilingual OCR. ACM.
Srihari, S.N., Ball, G., 2012. An assessment of Arabic handwriting recognition
technology. In: Guide to OCR for Arabic Scripts. Springer, pp. 3–34.
Srinivas, B.A., Agarwal, A., Rao, C.R., 2008. An overview of OCR research inIndian scripts. International Journal of Computer Sciences and Engineering
Systems (IJCSES), 2(2), pp. 141–153.
Stolyarenko, A. V, Dershowitz, N., 2018. OCR for arabic using SIFT descriptors
with online failure prediction. Tel Aviv University.
Sun, C., Si, D., 1997. Skew and slant correction for document images using
gradient direction. In: Proceedings of the Fourth International Conference
on Document Analysis and Recognition. IEEE, 1, pp. 142–146.
DOI:10.1109/ICDAR.1997.619830
Supriana, I., Nasution, A., 2013. Arabic character recognition systemdevelopment. Procedia Technology, 11, pp. 334–341.
DOI:10.1016/j.protcy.2013.12.199
Taghva, K., Stofsky, E., 2001. OCRSpell: An interactive spelling correction
system for OCR errors in text. International Journal on Document Analysis
and Recognition, 3, pp. 125–137. DOI:10.1007/PL00013558
Taha, S., Babiker, Y., Abbas, M., 2012. Optical character recognition of Arabic
printed text. In: IEEE Student Conference on Research andDevelopment (SCOReD). IEEE, pp. 235–240.
DOI:10.1109/SCOReD.2012.6518645
Tamen, Z., Drias, H., 2010. How to overcome some segmentation problems in aconstrained handwritten Arabic character recognition system. In: 10th
International Conference on Information Sciences, Signal Processing and
Their Applications, (ISSPA 2010). IEEE, pp. 634–637.
DOI:10.1109/ISSPA.2010.5605419
Tarábek, P., 2008. Performance measurements of thinning algorithms. Journal of
Information, Control and Management, 6(2), pp. 125–132.
Teahan, W.J., 2000. Text classification and segmentation using minimum crossentropy. In: Content-Based Multimedia Information Access, 2, pp. 943-961.
Teahan, W., 2018. A compression-based toolkit for modelling and processing
natural language text. Information, 9(12), pp.294-323.
DOI:10.3390/info9120294
Teahan, W.J., Harper, D.J., 2003. Using compression-based language models fortext categorization. Language Modeling for Information Retrieval. Springer,
pp. 141-165. DOI:10.1007/s10639-015-9377-5
Teahan, W.J., Inglis, S., Cleary, J.G., Holmes, G., 1998. Correcting English text
using PPM models. In: Proceedings Data Compression Conference. IEEE,
pp. 289-298.
176

Teahan, W.J., Wen, Y., McNab, R., Witten, I.H., 2000. A compression-basedalgorithm for Chinese word segmentation. Computational Linguistic, 26(3),375–393.
Touj, S., ben Amara, N.E., Amiri, H., 2005. Generalized Hough transform for
Arabic printed optical character recognition. International Arab Journal of
Information Technology, 2(4), pp. 326–333.
Tse, P.U., Cavanagh, P., 2000. Chinese and Americans see opposite apparent
motions in a Chinese character. Cognition, 74(3), pp. 27–32.
DOI:10.1016/S0010-0277(99)00065-7
Viterbi, A., 1967. Error bounds for convolutional codes and an asymptotically
optimum decoding algorithm. IEEE Transactions on Information
Theory, 13(2), pp.260-269.
Vinter, A., Chartrel, E., 2010. Effects of different types of learning on
handwriting movements in young children. Learning and Instruction, 20(6),pp. 476–486.
Wang, P.S.P., Zhang, Y.Y., 1989. A fast and flexible thinning algorithm. IEEE
Transactions on Computers, 38(5), pp. 741–745. DOI:10.1109/12.24276
Witten, I. H., Frank, E., Hall, M. A., 2005. Data mining: Practical machinelearning tools and techniques. In: Data mining, Morgan Kaufmann
Publishers Inc., San Francisco, CA, USA.
Wu, P., 2007. Adaptive models of Chinese text. Prifysgol Bangor University ofWales.
Xiu, P., Peng, L., Ding, X., Wang, H., 2006. Offline handwritten Arabic
character segmentation with probabilistic model. In: Lecture Notes in
Computer Science (including Subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics). Springer, pp. 402–412.
DOI:10.1007/11669487_36
Ymin, A., Aoki, Y., 1996. On the segmentation of multi-font printed Uygur
scripts. In: Proceedings of the 13th International Conference on Pattern
Recognition. IEEE, 3, pp. 215–219.
Younis, K.S., Alkhateeb, A.A., 2017. A new implementation of deep neuralnetworks for optical character recognition and face recognition. In:
Proceedings of the New Trends in Information Technology. Jordan, 157–
162.
Zeki, A.M., 2005. The segmentation problem in Arabic character recognition:
The state of the art. In: Proceedings of the 1st International Conference on
Information and Communication Technology (ICICT). IEEE, pp. 11–26.
DOI:10.1109/ICICT.2005.1598538
Zeki, A.M., Zakaria, M.S., Liong, C.-Y., 2011. Segmentation of Arabic
characters: A comprehensive survey. International Journal of Technology
Diffusion, 2(4), pp. 48–82. DOI:http://dx.doi.org/10.4018/jtd.2011100104

177

Zhang, D., Lu, G., 2001. A comparative study on shape retrieval using Fourier
descriptors with different shape signatures. In: Proceedings of International
Conference on Intelligent Multimedia and Distance Education, 1, pp. 1–9.
Zhang, T.Y., Suen, C.Y., 1984. A fast parallel algorithm for thinning digitalpatterns. Communications of the ACM, 27(3), pp. 236–239.
Zhang, Y.Y., Wang, P.S.P., 1988. A modified parallel thinning algorithm. In:
Proceedings of the 9th international Conference on Pattern Recognition.
IEEE, pp. 1023–1025. DOI:10.1109/ICPR.1988.28429
Zheng, L., Hassin, A.H., Tang, X., 2004. A new algorithm for machine printed
Arabic character segmentation. Pattern Recognition Letters, 25(15), pp.
1723–1729. DOI:10.1016/j.patrec.2004.06.015
Zhou, R.W., Quek, C., Ng, G.S., 1995. A novel single-pass thinning algorithm
and an effective set of performance criteria. Pattern Recognition Letters,
16(12), pp. 1267–1275.
Zidouri, A., Sarfraz, M., Nawaz, S.N., Ahmad, M.J., 2003. PC based offline
Arabic text recognition system. In: Proceedings of the Seventh International
Symposium on Signal Processing and Its Applications. IEEE, pp. 431–43
DOI:10.1109/ISSPA.2003.1224906

Appendices

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220