Method of and apparatus for segmenting foreground and background information for optical character recognition of labels employing single layer recurrent neural network

• US 5,710,830 A
• Filed: 11/30/1995
• Issued: 01/20/1998
• Est. Priority Date: 10/05/1994
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Incorporated
• Inventors: Holeva, Lee F.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/574,254
• Time in Patent Office: 782 Days
• Field of Search: 382/173, 382/282, 358/464
• US Class Current: 382/173
• CPC Class Codes: F24C 7/06 Arrangement or mounting of electric heating elements
• CPC Class Codes: F24C 7/087 of electric circuits regulating heat
• CPC Class Codes: G01L 1/144 with associated circuitry G01L1/146 and G01L1/148 take precedence
• CPC Class Codes: G05D 1/0816 to ensure stability
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: H05B 3/0076 for cooking, e.g. in ovens lamps specially adapted for non-metallic cooking plates H05B3/742, H05B3/744

Abstract

A method and apparatus for processing a greyscale input of an image, particularly of a shipping label, into a binary output image in which foreground information is segmented from the background information and contrasts between adjacent regions having different background densities are obliterated is described. A neuron employing a 5×5 input neighborhood having a unique neuron activation function is shown. No explicit line process is employed. Output is biased toward a particular one of the output values by employing non-linear feedback as a function of both the grey scale value for the pixel corresponding to the label site being updated and the most recent value of the label site. The otherwise strong contribution from a gradient term in the energy function is suppressed by a shunting inhibition when the shunting inhibition function detects that the pixel lies on or near a boundary between adjacent regions of differing background intensities.

Claims

1. A method of segmenting foreground areas from background areas of an input image including input pixels having grey scale input pixel values, comprising the steps of:

defining an output image comprising output pixels having binary output pixel values;

assigning each input pixel and each output pixel a position in a coordinate system so that the input image and the output image correspond to the physical configuration of the substrate;

assigning a scaling factor to each input pixel so that a scaling factor assigned to an input pixel represents an estimate of the background input pixel values in a neighborhood about the input pixel;

defining an energy function that varies as a function of the input pixels values, the output pixels values, and the scaling factors comprising

a first component expressing a cost associated with an output pixel value not being in agreement with the value of a corresponding input pixel taking into account the value of the scaling factor assigned to the corresponding input pixel,

a second component expressing a cost associated with the value of an output pixel not being in agreement with the values of pixels in a neighborhood around the output pixel, and

a third component expressing a cost associated with the gradient of the input pixel values so as to define boundaries between regions of the input image having contrasting input pixel values; and

segmenting foreground areas of the output image from background areas of the output image by iteratively varying the output pixel values so that the energy function converges toward a minimum value.

2. The method of claim 1, wherein the step of segmenting foreground areas of the output image from background areas of the output image comprises the step of growing foreground areas of the output image.

3. The method of claim 2, wherein the step of growing foreground areas of the output image comprises the steps of:

growing the foreground areas of the output image until the foreground areas intersect the boundaries; and

shunting boundaries associated with changes in the scaling factors so that changes in the scaling factors do not prevent the growth of the foreground areas.

4. The method of claim 3, wherein the step of growing the foreground areas of the output image until the foreground areas intersect the boundaries comprises the step of assigning the energy function an energy penalty for foreground areas crossing boundaries.

5. The method of claim 4, wherein the step of assigning the energy function an energy penalty for foreground areas crossing boundaries comprises the step of assigning the energy function an energy penalty based on directional derivatives taken from the input image.

6. The method of claim 5, wherein the energy function further comprises:

a shunt inhibitor that counteracts the energy penalty for foreground areas of the output image crossing boundaries associated with changes in the scaling factors so that changes in the scaling factors do not prevent the growth of the foreground areas.

7. The method of claim 1, wherein the third component includes directional derivatives taken in directions relative to the coordinate system comprising:

a vertical direction;

a horizontal direction;

a plus forty-five degrees direction; and

a minus forty-five degrees direction.

8. The method of claim 1, wherein the input pixels are in a one-to-one correspondence with the output pixels so that each output pixel has an associated input pixel.

9. An apparatus for segmenting foreground areas from background areas of an input image including input pixels having grey scale input pixel values, comprising:

a computer storage medium for defining an output image comprising output pixels having binary output pixel values;

means for assigning each input pixel and each output pixel a position in a coordinate system so that the input image and the output image correspond to the physical configuration of the substrate;

means for assigning a scaling factor to each input pixel so that a scaling factor assigned to an input pixel represents an estimate of the background input pixel values in a neighborhood about the input pixel;

means for defining an energy function that varies as a function of the input pixels values, the output pixels values, and the scaling factors comprising,

a first component expressing a cost associated with an output pixel value not being in agreement the value of a corresponding input pixel taking into account the value of the scaling factor assigned to the corresponding input pixel,

a second component expressing a cost associated with the value of an output pixel not being in agreement with the values of its neighboring output pixels, and

a third component expressing a cost associated with the gradient of the input pixel values so as to define boundaries between regions of the input image having contrasting input pixel values; and

means for segmenting foreground areas of the output image from background areas of the output image by iteratively varying the output pixel values so that the energy function converges toward a minimum value.

10. The apparatus of claim 9, wherein:

the means for assigning a scaling factor to each input pixel comprises a competitive learning network for assigning a scaling factor to each input pixel so that a scaling factor assigned to an input pixel represents an estimate of the background input pixel values in a neighborhood about the input pixel.

11. The apparatus of claim 9, wherein the means for segmenting foreground areas of the output image from background areas of the output image comprises:

means for growing foreground areas of the output image until the foreground areas intersect the boundaries; and

means for shunting boundaries associated with changes in the scaling factors so that changes in the scaling factors do not prevent the growth of the foreground areas.

12. The apparatus of claim 11, wherein:

the means for segmenting foreground areas of the output image from background areas of the output image comprises a recurrent neural network for segmenting foreground areas of the output image from background areas of the output image by iteratively varying the output pixel values so that the energy function converges toward a minimum value.