
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fast Algorithms for Minimum Covering Run Expression
Supoj CHINVEERAPHAN AbdelMalek B.C. ZIDOURI Makoto SATO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E77D
No.3
pp.317325 Publication Date: 1994/03/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Image Processing, Computer Graphics and Pattern Recognition Keyword: Minimum Covering Run (MCR) expression, bipartite graph, minimum covering, maximum matching, HopcroftKarp's algorithm,
Full Text: PDF>>
Summary:
The Minimum Covering Run (MCR) expression used for representing binary images has been proposed [1][3]. The MCR expression is an adaptation from horizontal and vertical run expression. In the expression, some horizontal and vertical runs are used together for representing binary images in which total number of them is minimized. It was shown that, sets of horizontal and vertical runs representing any binary image could be viewed as partite sets of a bipartite graph, then the MCR expression of binary images was found analogously by constructing a maximum matching as well as a minimum covering in the corresponding graph. In the original algorithm, the most efficient algorithm, proposed by Hopcroft, solving the graphtheoretical problems mentioned above, associated with the Rectangular Segment Analysis (RSA) was used for finding the MCR expression. However, the original algorithm still suffers from a long processing time. In this paper, we propose two new efficient MCR algorithms that are beneficial to a practical implementation. The new algorithms are composed of two main procedures; i.e., Partial Segment Analysis (PSA) and construction of a maximum matching. It is shown in this paper that the first procedure which is directly an improvement to the RSA, appoints well a lot of representative runs of the MCR expression in regions of text and line drawing. Due to the PSA, the new algorithms reduce the number of runs used in the technique of solving the matching problem in corresponding graphs so that satisfactory processing time can be obtained. To clarify the validity of new algorithms proposed in this paper, the experimental results show the comparative performance of the original and new algorithms in terms of processing time.

