TL;DR
This paper presents the first HMM-based system for online Arabic handwriting recognition, tackling the script's inherent complexities like cursive writing, position-dependent letter shapes, and crucial "delayed strokes" (dots and small marks). The system achieves strong writer-independent word recognition rates, demonstrating the effectiveness of their novel delayed-stroke handling and feature extraction methods.
What Problem Does This Paper Address?
The paper tackles the challenging problem of recognizing Arabic handwriting in real-time (online). Unlike static, scanned images (offline recognition), online recognition captures the dynamic stroke information as a user writes. Arabic script presents unique difficulties:
- Cursive Nature: Letters connect fluidly, making segmentation into individual characters difficult.
- Position-Dependent Shaping: Most Arabic letters have different visual forms depending on whether they appear at the beginning, middle, or end of a word.
- Obligatory Dots and Strokes: Arabic script relies heavily on dots and small strokes placed above or below letter bodies to distinguish between letters that otherwise look similar. These are often written after the main letter body, hence "delayed strokes." Their presence, absence, or position can drastically change a letter's identity and, consequently, the word's meaning.
- Top-Down Writing Style: In some Arabic writing, letters can be written above their preceding ones, further complicating positional analysis.
Existing approaches struggled with these issues, particularly the delayed strokes, often discarding them or creating overly complex models.
Methods
The authors propose a novel system built upon Hidden Markov Models (HMMs), a standard technique in sequence recognition. Their key contributions lie in:
- Novel Delayed-Stroke Handling: They introduce a "delayed-stroke projection algorithm." This method detects delayed strokes based on their location, size, and temporal order relative to the main letter body. Crucially, it then "projects" these strokes onto the letter body by inserting virtual points, effectively integrating them into the stroke sequence for recognition. This is a significant departure from methods that simply discard or treat them as separate entities.
- Feature Extraction: They extract three types of features for each point in the digitized stroke sequence:
- Local Angle: The angle of the current stroke segment relative to the X-axis.
- Super-Segment Angle: A novel feature that captures geometric information by relating a segment to its "group" within a larger stroke sequence, computed after initial simplification.
- Loop Presence: A global feature indicating if a point is part of a loop, which is common and important in Arabic script.
- Geometric Preprocessing: Standard techniques like low-pass filtering for noise reduction and the Douglas-Peucker algorithm for line simplification are used. Writing speed normalization is also applied.
- HMM-Based Recognition Framework: Each Arabic letter shape (considering its positional variations) is modeled by a discrete HMM. These letter-shape models are then embedded into a "word-part network," which represents a dictionary of possible word parts. The recognition process involves simultaneously segmenting word parts and recognizing letter shapes within an integrated HMM framework.
Datasets
The paper describes the creation of custom datasets for training and evaluation:
- Training Data: Created by asking four Arabic-literate trainers to handwrite 800 selected words. They were also instructed to manually mark letter shape boundaries and ensure delayed strokes were within these boundaries.
- Testing Data: Ten testers (the four trainers plus six new volunteers) wrote 280 words not present in the training data. This set comprised 2,358 total words. The overlap in trainers between training and testing was intentional to evaluate writer-dependence versus writer-independence.
The authors note that no standard reference datasets for Arabic online handwriting recognition were available at the time.
Key Insights and Ideas
- Delayed Strokes are Crucial: The paper strongly emphasizes that delayed strokes are not mere embellishments but essential discriminators in Arabic script. Their novel projection method successfully integrates this information, leading to improved recognition.
- Writer-Independence is Achievable: The system demonstrates a small difference (less than 2%) between writer-dependent and writer-independent recognition rates across various dictionary sizes. This suggests the chosen features and the delayed-stroke handling are robust to individual writing styles.
- Word-Part Networks Improve Efficiency: By leveraging the structure of Arabic words (composed of word parts), the system optimizes the search space and recognition process.
- Global Features Matter: While local features are standard, the inclusion of a global "loop presence" feature proved beneficial, especially given the prevalence of loops in Arabic letters.
Key Results
The system achieved good results, particularly for writer-independent recognition:
- Word Recognition Rate: For a 5K word dictionary, the writer-independent (WI) average word recognition rate was 96.28%, only slightly lower than the writer-dependent (WD) rate of 96.47%. This gap widened with larger dictionaries, reaching 88.01% (WI) vs. 89.75% (WD) for a 40K dictionary.
- Word-Part Recognition Rate: This metric was even higher, with WI rates around 98.49% for a 5K dictionary and 94.40% for a 40K dictionary.
- Degradation with Ambiguity: As expected, performance degraded with increasing dictionary size (ambiguity), but the degradation in word-part recognition was slower than word recognition, indicating that errors are often tied to specific word parts.
- Qualitative Findings: The authors note that recognition errors often occur for very similar-looking word parts (e.g., ب/با, ر/د), suggesting that current features might not be sufficient to distinguish these subtle differences.
Limitations and Future Work
- Limitations:
- The system currently focuses on undiacritized (unvocalized) Arabic.
- The performance degradation with larger dictionaries highlights the ongoing challenge of ambiguity.
- Distinguishing very similar word parts remains an area for improvement.
- Future Work:
- Handling delayed strokes written before a word part is completed.
- Incorporating geometric computation techniques in a postprocessing phase to further reduce errors.
- Exploring sentence-level language modeling to leverage contextual information.
- Developing morphologically driven models to enhance dictionary efficiency and coverage.
Summary updated