Browse Prior Art Database

Binary Tree Structure for Managing Optical Character Recognition Alternate Segmentation Paths Particularly in Courtesy Amount Fields

IP.com Disclosure Number: IPCOM000117019D
Original Publication Date: 1995-Dec-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 163K

Publishing Venue

IBM

Related People

Narasimha, MS: AUTHOR [+2]

Abstract

Segmentation is the process of identifying and extracting the pels making up each digit of a numeric field. One approach to the problem is to attempt to construct partitioning paths through the background pels that exist between the digits of a field. Partitioning is straightforward if a field is devoid of inadvertently connected characters, noise pels and dropouts. However, in practice, fields often contain some or all of these three complicating factors.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

Binary Tree Structure for Managing Optical Character Recognition
Alternate Segmentation Paths Particularly in Courtesy Amount Fields

      Segmentation is the process of identifying and extracting the
pels making up each digit of a numeric field.  One approach to the
problem is to attempt to construct partitioning paths through the
background pels that exist between the digits of a field.
Partitioning is straightforward if a field is devoid of inadvertently
connected characters, noise pels and dropouts.  However, in practice,
fields often contain some or all of these three complicating factors.

      Connected or touching numerals are often introduced by the
writer.  Noise elements include partially dropped out amount lines
and boxes as well as features such as fraction lines that are
introduced by the writer.  Dropouts are sometimes caused by the
capture/thresholding process and sometimes caused by the writer
(e.g., pen skips and detached tops on the digit 5).

      The coexistence of these three problems is particularly
difficult to deal with.  The segmentation process must combine the
elements of fragmented numerals correctly while simultaneously
partitioning ones that are inadvertently combined.  Therefore, as
segmentation proceeds, it is often desirable to be able to identify
and retain a number of possible segmentation paths for later
evaluation.  Binary path point trees have proven to be a useful
mechanism for performing this function.

      The use of a recursive depth first search is a standard
technique for finding a path through a network.  In the described
segmentation system, each image pel is considered a point in a
network and segmentation is implemented as a recursive depth first
search through the background pels.  Successive right-side numeral
boundaries are established by construction of bottom-to-top paths
that pass through  the background pels of the image.  Each search is
allowed to proceed upward, left, or right, but not downward.

      The presence of dropouts and touching characters makes
necessary the extension of the basic depth first search procedure.
This extended procedure must be able to identify and remember the
locations where the constructed path appears to pass through dropouts
and those where a path appears to have terminated because of the
touching of adjacent numerals.  The use of path point trees provides
a mechanism which retains the simplicity of the basic recursive
search while adding the capability of remembering possible alternate
paths.

      Segmentation begins at the established left side boundary of a
numeral and proceeds to track the numeral's  bottom contour.  When
the bottom contour is detected to have risen by a certain threshold
amount above lowest point, the recursive upward search is initiated.
Each path point tree is a binary tree rooted at the point at which
such a search is initiated.

      Each time the search makes an upward step it pu...