Offline Handwritten Arabic Segmentation Algorithm And Multi-queue Grapheme Merging Model

Optical Character Recognition (OCR) has been investigated for decades. It's goal is to turn the character image into the inner code, saving large amount of labor work, time and money, and expediting the process of digitization. With the increasing need of digitization of Arabic documents, the subject of offline handwritten Arabic script recognition is gaining more and more attention in recent years. As Arabic is a cursive script, the system designed for Arabic language meets many challenges, mainly on the step of"character segmentation". Our main work is the successful designing of the two steps"over-segmentation"and"grapheme merging"."Over-segmentation"is a step that segment the word image into graphemes (parts of character). The main challenge is the connectivity between characters in an Arabic word. The over-segmentation method is based on the contour feature, obtaining candidate segmentation points."Grapheme merging"is the step that merges the graphemes into integral characters. We introduce a"multi-queue grapheme merging model"to describe and tackle the complex two-dimensional layout of graphemes. First, we sort the graphemes into three queues, according to their horizontal position. Then a three dimensional segmentation state space is constructed, through which the state trajectory representing the candidate merging scheme. The confidence of a character is calculated by calculation multiple source of information for decision. The optimal merging scheme is obtained through Dynamic Programming. The performance of our system is improved considerably. Experiments prove that the main contribution of the improvement is from the"multi-queue merging model"and the syndication of multiple source of information for decision. Our system runs at a high speed, proving the high efficiency of Dynamic Programming.Also, after the practical work of offline handwritten Arabic script segmentation, we derive the"multi-queue grapheme merging model"theoretically. For any complex two-dimensional layout of graphemes, the position constraints among graphemes can be described by"Positional Relationship Graph"(PRG). Based on PRG, the multi-queue structure can be generated, and then the optimization can be conducted to find optimal state trajectory, which represents the result of merging. The theoretical analysis of"multi-queue model"can help to guide the practice of segmentation in complex cases.