Automatic image segmentation using local area maximum and minimum image signals

• US 5,293,430 A
• Filed: 01/12/1993
• Issued: 03/08/1994
• Est. Priority Date: 06/27/1991
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Shiau, Jeng-Nan, Farrell, Barbara L.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/004,479
• Time in Patent Office: 420 Days
• Field of Search: 382/9, 382/42, 382/52, 382/53, 358/455, 358/456, 358/458, 358/462, 358/464
• US Class Current: 382/173
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

Method and apparatus for processing image pixels to determine the presence of high frequency halftone images. Prior to auto correlation, each pixel in the image is examined to determine whether it is a local area maximum or minimum. A binary image function composed of the image local area maximum or minimums is made available for auto correlation. The presence of peaks at shifts indicative of predetermined halftone image frequencies is detected, and an output signal indicative of the presence or absence of peaks at the predetermined halftone image frequencies is provided. The arrangement is combined with a run length encoder to reduce false microdetection results.

Claims

1. A method of processing image pixels in an electronic document image to determine the presence of halftone images, for optimum image processing thereof preparatory to printing the document, the steps comprising:

at an document image data buffer, receiving a document image defined by a plurality of pixels, each pixel a signal representing an optical density of the document at a discrete location therewithin and storing it in said document image data buffer;

with a comparison circuit operatively connected to said document image data buffer and having as inputs each pixel in a predetermined neighborhood thereof comparing said pixel to a group of neighboring pixels to determine whether it is a local area minimum or maximum and producing a local area minimum or maximum signal indicative thereof;

with a signal generator circuit responsive to said minimum or maximum signal, generating two image signals, a first image signal representing local area maximums of the image, and a second image signal representing local area minimums of the image;

with an averaging circuit having as input the image defined by a plurality of pixels, measuring optical density of the image over a block of T pixels with respect to a reference, and producing an average optical density signal indicative of the measured optical density;

with an auto correlation circuit having as inputs the first and second image signal, and operating on in response to the average optical density signal, auto correlating the first image signal if the average optical density signal is relatively high with respect to the reference, or auto correlating the second image signal if the average optical density signal is relatively low with respect to the reference, the auto correlation function evaluated over the block of T pixels, and for each of a plurality of offset values selected as corresponding to probable halftone frequencies;

from the auto correlated function, detecting for each offset value for which the auto correlation function was evaluated, whether the result of the evaluation is a zero or non-zero value, the presence of a non-zero value indicating the presence of halftone images at the frequency corresponding to the offset value; and

with an output signal generator, directing an output signal indicative of the presences of halftone images at the frequency corresponding to the offset value to an image processing control, to control the manner in which image pixels are processed when halftone images are detected.

2. The method as defined in claim 1, wherein the auto correlation function A(n) is given by:

##EQU5## where n is a selected offset of the auto correlation function;

p is the pixel value; and

t=a pixel position in the block of T pixels selected.

3. The method as defined in claim 1, wherein the auto correlation function Φ

(h) is given by;

##EQU6## where k is a selected offset value at which the function is evaluated;

f(l) is the pixel value; and

ti is a selected pixel position in the block of T pixels.

4. The method as defined in claim 1, where each pixel in the first image signal representing local area maximums of the image, and a second image signal representing local area minimums of the image are each represented by a one bit per pixel function.

5. The method as defined in claim 4, wherein, the auto correlation function is given by:

##EQU7## where n is selected offset of the auto correlation function;

p is the pixel value;

t is a pixel position in the block of T pixels selected; and

Λ

is a logical AND function.

6. The method as defined in claim 1, wherein in the determination of local area minimum, to be determined a minimum, a pixel must be at less than other pixels in the local area by a preselected amount.

7. The method as defined in claim 1, wherein the determination of local area maximum, to be determined a maximum, a pixel must be at greater than other pixels in the local area by a preselected amount.

8. The method as defined in claim 1, wherein in the determination of local area, the local area includes the closest eight neighboring pixels.

9. The method as defined in claim 1, wherein the determination of image density over the block of pixels is made by keeping a running average of pixel values in the block, and for each pixel determining whether the the running average is greater than or less than a density reference.

10. A method of processing image pixels in an electronic document image to determine the presence of halftone images therein, for optimum image processing preparatory to printing the document, the steps comprising:

at a document image data buffer, receiving an image defined by a plurality of pixels, each pixel representing an optical density of the document at a discrete location therewithin and storing it is said document image data buffer;

with a comparison circuit operatively connected to said document image data buffer and having as inputs each pixel in a predetermined neighborhood thereof comparing said pixel to a preselected group of neighbors to determine whether it is a local area minimum or maximum, and producing a local area minimum or maximum signal indicative thereof;

with a signal generator circuit responsive to said minimum or maximum signal, generating two image signals, a first image signal representing local area maximums of the image, and a second image signal representing local area minimums of the image;

with an auto correlation circuit having as inputs the first and second image signal, for each pixel in a block of T pixels, evaluating auto correlation function A(n) at a plurality of offset values n, given by;

##EQU8## where n is a selected offset of the auto correlation function,

p is the pixel value, and

t=a pixel position in the block of T pixels selected; and

with a zero detecting circuit operatively connected to said auto correlation circuit, from signal A(n), detecting for each offset value whether the result of the auto correlation function evaluation is a zero or non-zero value, the presence of a non-zero value indicating the presence of halftone images at the frequency corresponding to the offset value; and

with an output signal generator, directing an output signal indicative of the presences of halftone images at the frequency corresponding to the offset value to an image processing control, to control the manner in which image pixels are processed when halftone images are detected.

11. A method of processing image pixels in an electronic document image represented by a plurality of scan lines of pixels, to determine the presence of color halftones or rotated halftones in the image, for optimum image processing of colored halftones preparatory to printing the document, the steps comprising:

at an document image data buffer, receiving an image defined by a plurality of pixels, each pixel representing the optical density of a document image at a discrete location therewithin and storing it in said document image data buffer;

with a comparison circuit operatively connected to said document image data buffer and having as inputs each pixel in a predetermined neighborhood thereof comparing said pixel to a group of neighboring pixels to determine whether it is a local area minimum or maximum, and producing a local area minimum or maximum signal indicative thereof;

with a signal generator circuit responsive to said minimum or maximum signal, generating two image signals, a first image signal representing local area maximums of the image, and a second image signal representing local area minimums of the image;

with an averaging circuit having as an input the image defined by a plurality of pixels, measuring optical density over a block of T pixels with respect to a reference density;

with an auto correlation circuit having as inputs the first and second image signal, and operating on in response to the average optical density signal, for each block of T pixels, auto correlating the first image signal if the average optical density signal is relatively high with respect to the reference density, or auto correlating the second image signal if the average optical density signal is relatively low with respect to the reference density, the auto correlation function evaluated over the block of T pixels, and for each of a plurality of offset values including n=0 selected as corresponding to probable halftone frequencies, the determination of image density with respect to a reference made over the block of pixels;

with a zero detector circuit, from the auto correlated image signal, detecting for the offset value n=0 whether the result of the auto correlation evaluation is a zero or non-zero value;

with a counter circuit, counting the number of non-zero values for each block of T pixels over a group of scan lines, and upon exceeding a predetermined threshold indicative of the presence of color halftones or rotated halftones in the image, producing a color halftone presence signal thereof; and

with an output signal generator and responsive to the color halftone presence signal, directing an output signal indicative of the presences of color halftones or rotated halftone images to an image processing control, controlling the manner in which image pixels are processed when halftone images are detected.

12. Apparatus for processing image pixels in an electronic document image represented by a plurality of scan lines of pixels, to determine the presence of halftones in the image, for optimum image processing preparatory to printing a document comprising:

a document image data buffer, suitable for storing an image defined by a plurality of pixels, each pixel a signal representing the optical density of a document image at a discrete location therewithin;

a comparison circuit operatively connected to said document image data buffer and having as inputs each pixel in a predetermined neighborhood thereof, said circuit comparing each pixel with a group of neighboring pixels to determine whether it is a local area minimum or maximum, and provide an output signal indicative thereof;

a signal forming circuit forming a minimum signal and maximum signal each representing the set of minimum pixels and the set of maximum pixels within the image;

an averaging circuit having as an input signal the image defined by a plurality of pixels, measuring average optical density of the image over a block of T pixels and producing an average optical density signal;

thresholding means operable on the average optical density signal of a block of T pixels in the image, for determining whether the image is relatively dark or light, and producing a dark signal if the average value is less than a threshold value and a light signal if the average value is greater than the threshold value;

an auto correlation circuit having as inputs the first and second image signal from said signal forming means, and operating on a selected one of said signal responsive to the dark and light signals for evaluating the auto correlation function for each block of T pixels, said auto correlation means operable on the maximum signal if the image has been determined to be dark, and operable on the second function if the image has been determined to be light, the auto correlation function evaluated over the block of T pixels, and for each of a plurality of offset values selected as corresponding to probable halftone frequencies;

an offset comparison means for determining from said auto correlation circuit whether the evaluation at each offset value is a non-zero value, and producing an offset comparison signal indicating the presences of halftone at the corresponding halftone frequency,

an output signal generator, responsive to said offset comparison signal and directing an output signal indicative of the presences of halftone images at the frequency corresponding to the offset value, to an image processing control, to control the manner in which image pixels are processed when halftone images are detected.

13. The apparatus as defined in claim 12, where the maximum signal and the minimum signal are each represented by a one bit per pixel function.

14. The apparatus as defined in claim 13, wherein, the auto correlation function is given by:

##EQU9## where n is a selected offset of the auto correlation function;

p is the pixel value, equal to 1 if the pixel is a minimum or maximum, else equal to 0;

t is a pixel position in the block of T pixels selected; and

Λ

is a logical AND function.

15. A method of controlling an image processing circuit by distinguishing in an image within an electronic document to be processed thereby, portions thereof classifiable as halftone image portions and background image portions for optimum image processing preparatory to printing the document, comprising the steps of:

at a document image data buffer, receiving an electronic document image defined by a plurality of pixels, each pixel an electronic signal representing an optical density of the document at a discrete location therewithin, and storing said electronic document image in said document image data buffer;

with an image processing circuit, operatively connected to said document image data buffer, receiving and processing an electronic document image with a plurality of image type specific processing circuits preparatory to printing, at least one of said image type specific processing circuits optimally processing continuous tone or line/text images, and producing processed image signals as an output;

directing the output of each image type specific processing circuit to a data bus;

operating an image averaging circuit having as an input the electronic document image stored in the document image data buffer, to generate an image average background signal for the image;

with a halftone detection circuit, connected to said document image data buffer and having as inputs each electronic signal in a portion of the stored electronic document image, determining portions of the image to be treated as including halftone images and producing a halftone presence signal indicative thereof;

operating a neighborhood averaging circuit, having as an input the electronic document image and determining for each pixel the average value of its neighboring pixels responsive to the halftone detection signal;

operating a Laplacian calculating circuit, having as a signal input said neighborhood average signal and a corresponding pixel and subtracting the value of the pixel electronic signal, from the neighborhood average signal, and producing a Laplacian signal as a circuit response, and for a negative value so determined, determining two'"'"'s complement of the negative value thereby determining the absolute value of the Laplacian of the pixel;

operating a summing circuit, having as signal inputs the absolute value of the Laplacian sum for each pixel, and its neighboring pixels, and comparing the absolute value signal produced at the summing circuit to a predetermined reference signal selected to discriminate between halftone image portions and text background image portions;

comparing the pixel to a predetermined fraction of the average background signal of the image;

with an output signal generator, producing an output signal indicative of background image portions in accordance with the comparison of the absolute value signal with the reference signal, and in accordance with the comparison of the pixel with the predetermined fraction of the background value to an image processing bus controller, to limit access to the data bus for image signals from image type image processing circuits optimally processing for printing.

16. A method of controlling an image processing circuit by determining the presence within an electronic document image to be processed thereby of portions thereof classifiable as continuous tone or line/text images, for optimum image processing preparatory to printing the document, comprising the steps of:

at a document image data buffer, receiving an electronic document image defined by a plurality of pixels, each pixel an electronic signal representing an optical density of the document at a discrete location therewithin and storing it in said document image data buffer;

with an image processing circuit, operatively connected to said document image data buffer, receiving and processing electronic document image with a plurality of image type specific processing circuits preparatory to printing, at least one of said image type specific processing circuits optimally processing continuous tone or line/text images, and producing processed image signals as an output;

directing the output of each image type specific processing circuit to a data bus in accordance with an image type signal received at a bus controller;

with a halftone detection circuit, operatively connected to said document image data buffer and having as inputs each electronic signal in a predetermined neighborhood of pixels, determining that an image portion does not include halftones, and producing a halftone absence signal indicative thereof;

operating an averaging circuit having as signal inputs the image portion and responsive to the halftone absence signals, generating a neighborhood average signal for each pixel in the image portion;

operating a Laplacian calculating circuit, having as a signal input said neighborhood average signal and said pixel electronic signal and, subtracting the value of the pixel electronic signal, from the neighborhood average signal, and producing a Laplacian signal as a circuit response, and for a negative value so determined, determining two'"'"'s complement of the negative value thereby determining the absolute value of the Laplacian of the pixel;

operating a summing circuit having as signal inputs the signal from the Laplacian calculating circuit, summing the Laplacian signals generated for each pixel, and its neighboring pixels, and comparing said result to a predetermined reference signal selected to discriminate between continuous tone image portions and text/line image portions;

with an output signal generator, producing an output signal indicative of continuous tone image portions or text/line portions in accordance with the comparison of the Laplacian sum and the reference signal to an image processing bus controller, to limit access to the data bus for image signals from image type image processing circuits optimally processing continuous tone or line/text images when continuous tone image portions or text/line portions images are detected, for printing.

17. A method of controlling an image processor for optimum image processing preparatory to printing a document by determining the presence within an electronic document image of portions thereof classifiable as line/text, continuous tone, or background, wherein pixel values range from a minimum value representing a black pixel and a maximum value representing a white pixel, comprising the steps of:

at a document image data buffer, receiving an electronic document image defined by a plurality of pixels, each pixel representing an optical density of a document image at a discrete location therewithin and storing it in said document image data buffer;

with an image processing circuit, operatively connected to said document image data buffer, receiving and processing electronic document image with a plurality of image type specific processing circuits preparatory to printing, at least one of said image type specific processing circuits optimally processing continuous tone or line/text images, and producing processed image signals as an output;

directing the output of each image type specific processing circuit to a data bus;

with an averaging circuit having as an input the image, determining from the stored electronic document in the document image data buffer an average background value for the image, and producing an average background signal indicative thereof;

responsive to the average background signal, producing first and second fractional average background signals of the average background signal, with the first value being greater than the second one;

operating a halftone detection circuit to determine those portions of the image including halftones, and producing a halftone detection signal indicative thereof;

operating an absolute Laplacian summing circuit, receiving as inputs pixels in the image with a predetermined spatial relationship with a pixel to be processed, and producing an absolute Laplacian sum signal;

with an image run detector, receiving as inputs said halftone detection signal determining for each scanline in the image whether the scan line is in a portion of the image classifiable as an image run, and storing the location of each image runs in an image run location buffer, each image run including a continuous sequence of pixels, wherein each pixel in the image run may be classified into at least one of three classifications wherein pixels in the first class have a pixel value with a predetermined relationship with the average background value and absolute Laplacian sum, pixels in the second class includes pixels that are inside a portion of the image classified as including halftones and pixels of the third class include pixels that are located inside an image run of the preceding scanline;

at a background-continuous tone-line/text detection circuit, having as inputs the image run signal, the first and second fractional value background signals, a black reference signal and the absolute Laplacian sum signal, producing a control signal to the image processing circuit controlling the image processing of the electronic document image in accordance with a predetermined relationship of said background-continuous tone-line/text detection circuits inputs.

18. The method as defined in claim 17, wherein said predetermined relationship is defined as follows:

for each pixel, producing an indication of a line/text image portion, when the absolute Laplacian sum for the pixel is greater than the reference value and the pixel is not inside the image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is greater than the second fractional value and the pixel is not inside an image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is greater than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of continuous tone image portion when the pixel value is less than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of text/line image portion when the pixel value is less than a black reference value and the pixel is not inside an image run of the previous scanline; and

for each pixel, producing an indication of continuous tone image portion when the pixel value is less than the second fractional value of background value and the pixel is either inside an image run or with pixel value greater than the black reference value.

19. The method as defined in claim 17, wherein said predetermined relationship is defined as follows:

for each pixel, producing an indication of background image portion when the pixel value is less than the second fractional value and the pixel is not inside an image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is less than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of continuous tone image portion when the pixel value is greater than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of text/line image portion when the pixel value is greater than a black reference value and the pixel is not inside an image run of the previous scanline; and

for each pixel, producing an indication of continuous tone image portion when the pixel value is greater than the second fractional value of background value and the pixel is either inside an image run or with pixel value greater than the black reference value.

20. The method as defined in claim 17, wherein said predetermined relationship is defined as follows:

for each pixel, producing an indication of a line/text image portion, when the high frequency image filter output for the pixel is greater than the reference value and the pixel is not inside the image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is greater than the second fractional value and the pixel is not inside an image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is greater than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of continuous tone image portion when the pixel value is less than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of text/line image portion when the pixel value is less than a black reference value and the pixel is not inside an image run of the previous scanline; and

for each pixel, producing an indication of continuous tone image portion when the pixel value is less than the second fractional value of background value and the pixel is either inside an image run or with pixel value greater than the black reference value.

21. The method as defined in claim 17, wherein said predetermined relationship is defined as follows:

for each pixel, producing an indication of a line/text image portion, when the absolute value of a high frequency image filter output for the pixel is less than the reference value and the pixel is not inside the image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is less than the second fractional value and the pixel is not inside an image run of the previous scanline;

for each pixel, producing an indication of background image portion when the pixel value is less than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of continuous tone image portion when the pixel value is greater than the first fractional value and the pixel is inside an image run of the previous scanline;

for each pixel, producing an indication of text/line image portion when the pixel value is greater than a black reference value and the pixel is not inside an image run of the previous scanline; and

for each pixel, producing an indication of continuous tone image portion when the pixel value is greater than the second fractional value of background value and the pixel is either inside an image run or with pixel value greater than the black reference value.