Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fast Method for Performing Cellular Logic Operations on Binary Images

IP.com Disclosure Number: IPCOM000111881D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 6 page(s) / 206K

Publishing Venue

IBM

Related People

Billings, DW: AUTHOR

Abstract

Fig. 1 shows a field box surrounding a field on a form. The form has been scanned with a scanner to generate a digital image of Fig. 1. As can be seen in Fig. 1, there is a misregistration in the location of the numeral 6 in the field box.

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

Fast Method for Performing Cellular Logic Operations on Binary Images

      Fig. 1 shows a field box surrounding a field on a form.  The
form has been scanned with a scanner to generate a digital image of
Fig. 1.  As can be seen in Fig. 1, there is a misregistration in the
location of the numeral 6 in the field box.

      In Fig. 2, field extraction has been performed dropping out the
field box.  The result of field extraction leaves a gap in the number
6, as can be seen in in Fig. 2.

      Fig. 3 is a magnified view of the encircled portion of Fig. 2,
showing the top portion and bottom portion of the body of Fig. 6 of
Fig. 2.

      A significant problem is encountered in character recognition
of numerals which have been fragmented, as is shown in Fig. 2.  A
technique to rejoin segments of numerals and characters is shown in
the sequence of Figs. 4-9.

      A technique, known in the prior art as dilation and erosion, is
known in the area of cellular logical operation on binary images.
The technique is performed as is seen in the sequence of Figs.  4-9.

      Figs. 4-6 show the dilation sequence.  The lower portion L and
the upper portion U of the 6 shown in Fig. 4 are really collections
of pixels, each of which has a binary value of one, for example.  In
accordance with the dilation operation, wherever there is a value of
one, a value of one is turned on in an adjacent pixel.  Thus, as can
be seen in the transition from Fig. 4 to Fig. 5, the body of the
lower segment L grows by a layer of ones surrounding the lower
segment L.  Similarly, a body of ones grows around the upper segment
U.

      The transition from Fig. 5 to Fig. 6 shows a second dilation
step which repeats the growth of another coating of ones around each
one for both the lower segment L and upper segment U.

      As can be seen in Fig. 6, by performing two dilation steps, the
gap between the lower segment L and the upper segment U has been
closed.  In this example, the width of the field box was two pixels
wide in Fig. 1.

      The next sequence of steps, the erosion steps, is shown in
Figs. 7-9.  In an erosion step in the cellular logic operations on
binary images, where a pixel having a value one does not have a
neighboring pixel with a value of one, then that pixel is removed.
Thus, the outer layers of the combined image of Fig. 6 are removed in
making the transition from Fig. 7 to Fig. 8.  Note here that the
lower segment L and the upper segment U still remain joined, since
the pixels between the lower segment L and upper segment U had
contiguous pixels with values of one.  Similarly, the transition from
Fig. 8 to Fig. 9 is a second erosion step where the outer layer of
ones is removed from the lower segment L and the upper segment U.
Once again, note that because the region between the lower segment L
and the upper segment U does have pixels whose contiguous cells
contain the value one, they are not removed.

    ...