Systems and methods for identifying regions within an image having similar continuity values

• US 7,379,587 B2
• Filed: 02/12/2004
• Issued: 05/27/2008
• Est. Priority Date: 02/12/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kletter, Doron, Nafarieh, Asghar, Curry, Donald J.
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): Shikhman; Max
• Application Number:
  US10/776,515
• Publication Number:
  US 20050180628A1
• Time in Patent Office: 1,566 Days
• Field of Search: 382/165, 382/164
• US Class Current: 382/164
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

A blob identifier uses edge continuity signal to analyze how to combine the current pixel into an existing blob or into the background image, or start a new blob. The blob identifier outputs a list of blob identifiers on a line-by-line basis.

Claims

1. An apparatus, comprising:

a first comparator that compares an edge continuity value of a current pixel of each line of pixels to edge continuity values of pixels within a first neighborhood of the current pixel, wherein the first neighborhood comprises at least 3 adjacent pixels to generate compare results;

a blob identifier; and

an assigner that assigns a blob identification of a blob to the current pixel based on the compare results to associate the current pixel with the blob;

wherein the blob identifier includes a top-to-bottom module for analyzing each pixel in turn in raster scan order;

a gradient parameter generator that generates a gradient parameter value for the current pixel based on luminance and chroma values of a second neighborhood of the current pixel;

a quantizer that quantizes the gradient parameter value to set an edge continuity value of the pixel;

the gradient parameter generator is a grayscale selector generator that includes a second comparator that compares luminance values of pixels within the second neighborhood of the current pixel to output a maximum luminance value and a minimum luminance value of the second neighborhood,

the second comparator further outputs first chroma values and second chroma values that correspond to a location of the respective maximum luminance and minimum luminance values, wherein a dependent maximum value is a combination of the first chroma values and the maximum luminance value, and a dependent minimum value is a combination of the second chroma values and the minimum luminance value;

the grayscale selector generator generating a grayscale selector value based on the dependent maximum value and the dependent minimum value; and

the quantizer quantizing the grayscale selector value by comparing the grayscale selector value with one or more threshold values and assigning the grayscale selector value to a finite set of values.

2. The apparatus of claim 1, wherein the first neighborhood of the current pixel includes pixels within a line of pixels including the current pixel and a top line of pixels previous to the line of pixels including the current pixel, the top line including pixels having positions that are aligned to positions of pixels of the line of pixels including the current pixel, a pixel in the top line having a corresponding position of the current pixel being a top-adjacent pixel, a pixel to a left side of the top adjacent pixel being a top-left adjacent pixel, and a pixel to a left side of the current pixel in the line of pixels being a left-adjacent pixel.

3. The apparatus of claim 1, wherein the second neighborhood of the current pixel includes a window of pixels surrounding the current pixel.

4. The apparatus of claim 2, wherein

the first comparator compares the edge continuity value of the current pixel with the edge continuity value of a top-adjacent pixel and/or a left-adjacent pixel and/or a top-left adjacent pixel;

and

the assigner assigns the current pixel a blob identification associated with the top-adjacent pixel or a blob identification associated with the top-left adjacent pixel or a blob identification associated with the left-adjacent pixel or a new blob identification or to a background plane based on the comparison of the edge continuity values.

5. The apparatus of claim 4, wherein

the assigner uses an action table to determine whether to assign the current pixel the blob identification associated with the top-adjacent pixel or the blob identification associated with the top-left adjacent pixel or the blob identification associated with the left-adjacent pixel or the new blob identification or to the background plane, based on a pattern of the edge continuation values of the top-adjacent pixel, the top left adjacent pixel and the left adjacent pixel.

6. The apparatus of claim 1, wherein

the apparatus outputs a table that contains a list of blob identifications associated with pixels of the line of pixels including the current pixel.

7. A xerographic marking device incorporating the apparatus of claim 1.

8. A marking device incorporating the apparatus of claim 1.

9. A digital photocopier incorporating the apparatus of claim 1.

10. A method, comprising:

analyzing each pixel in turn in raster scan order;

comparing an edge continuity value of a current pixel of each line of pixels to edge continuity values of pixels within a first neighborhood of the current pixel wherein the first neighborhood comprises at least 3 adjacent pixels, to generate compare results;

identifying a blob; and

assigning the identification of the blob to the current pixel based on the compare results to associate the current pixel with the blob;

generating a gradient parameter value for the current pixel based on luminance and chroma values of a second neighborhood of the current pixel; and

quantizing the gradient parameter value to set an edge continuity value of the current pixel;

comparing luminance values of pixels within the second neighborhood of the current pixel to output a maximum luminance value and a minimum luminance value of the second neighborhood;

further outputting first chroma values and second chroma values that correspond to a location of the respective maximum luminance value and the minimum luminance value, wherein a dependent maximum value is a combination of the first chroma values and the maximum luminance value and a dependent minimum value is a combination of the second chroma values and the minimum luminance value;

generating a grayscale selector value based on the dependent maximum value and the dependent minimum value; and

quantizing the grayscale selector value by comparing the grayscale selector value with one or more threshold values and assigning the grayscale selector value to one of a finite set of values.

11. The method of claim 10, wherein the first neighborhood of the current pixel includes pixels within a line of pixels including the current pixel and a top line of pixels previous to the line of the pixels including the current pixel, the top line including pixels having positions that are aligned to positions of pixels of the line of pixels including the current pixel, a pixel in the top line having a corresponding position of the current pixel being a top-adjacent pixel, a pixel to a left side of the top adjacent pixel being a top-left adjacent pixel, and a pixel to a left side of the current pixel in the line of pixels being a left-adjacent pixel, the method further comprising:

comparing the edge continuity value of the current pixel with the edge continuity value of a top-adjacent pixel and/or a left-adjacent pixel and/or a top-left adjacent pixel;

assigning the current pixel to a blob identification associated with the top-adjacent pixel or to a blob identification associated with the top-left adjacent pixel or a blob identification associated with the left-adjacent pixel or a new blob identification or to a background plane based on the comparison of the edge continuity values.

12. The method of claim 11, further comprising:

using an action table to determine whether to assign the current pixel the blob identification associated with the top-adjacent pixel or the blob identification associated with the top-left adjacent pixel or the blob identification associated with the left-adjacent pixel or the new blob identification or to the background plane based on a pattern of the edge continuation values of the top-adjacent pixel, the top-left adjacent pixel and the left-adjacent pixel.

13. The method of claim 10, further comprising:

outputting a table that contains a list of blob identifications associated with pixels of the line of pixels including the current pixel.

14. A blob identifier, comprising:

a top-to-bottom module for analyzing each pixel in turn in raster scan order

means for comparing an edge continuity value of a current pixel of each line of pixels to edge continuity values of pixels within a first neighborhood of the current pixel comprising at least three adjacent pixels to generate compare results,

wherein the first neighborhood of the current pixel includes pixels within a line of pixels including the current pixel and a top line of pixels previous to the line of the current pixel, the top line including pixels having positions that are aligned to positions of pixels of the line of pixels including the current pixel, a pixel in the top line having a corresponding position of the current pixel being a top-adjacent pixel, a pixel to a left side of the top adjacent pixel being a top-left adjacent pixel, and a pixel to a left side of the current pixel in the line of pixels being a left-adjacent pixel; and

means for assigning a blob identification of a blob to the current pixel based on the compare results to associate the current pixel with the blob;

means for generating a gradient parameter value for the current pixel based on luminance and chroma values of a second neighborhood of the current pixel; and

means for quantizing the gradient parameter value to set an edge continuity value of the current pixel;

means for comparing luminance values of pixels within the second neighborhood of the current pixel to output a maximum luminance value and a minimum luminance value of the second neighborhood;

means for further outputting first chroma values and second chroma values that correspond to a location of the respective maximum luminance value and the minimum luminance value, wherein a dependent maximum value is a combination of the first chroma values and the maximum luminance value and a dependent minimum value is a combination of the second chroma values and the minimum luminance value;

means for generating a grayscale selector value based on the dependent maximum value and the dependent minimum value; and

means for quantizing the grayscale selector value by comparing the grayscale selector value with one or more threshold values and assigning the grayscale selector value to one of a finite set of values.

15. The blob identifier of claim 14, wherein the means for assigning further comprises:

table means for determining whether to assign the current pixel to the blob identification associated with the top-adjacent pixel or the blob identification associated with the top-left adjacent pixel or the blob identification associated with the left-adjacent pixel or the new blob identification or to a background plane based on the pattern of the edge continuation values of the top-adjacent pixel, the top-left adjacent pixel and the left-adjacent pixel.

16. A computer readable storage medium storing a set of program instruction executable on a data processing device, the set of program instructions comprising:

instructions for analyzing each pixel in turn in raster scan order to identify a blob;

instructions for comparing an edge continuity value of a current pixel of each line of pixels to edge continuity values of pixels within a first neighborhood of the current pixel, wherein the first neighborhood comprises at least 3 adjacent pixels, to generate compare results; and

instructions for assigning the blob identification of the blob to the current pixel based on the compare results to associate the current pixel with the blob;

instructions for generating a gradient parameter value for the current pixel based on luminance and chroma values of a second neighborhood of the current pixel; and

instructions for quantizing the gradient parameter value to set an edge continuity value of the current pixel;

instructions for comparing luminance values of pixels within the second neighborhood of the current pixel to output a maximum luminance value and a minimum luminance value of the second neighborhood;

instructions for further outputting first chroma values and second chroma values that correspond to a location of the respective maximum luminance value and the minimum luminance value, wherein a dependent maximum value is a combination of the first chroma values and the maximum luminance value and a dependent minimum value is a combination of the second chroma values and the minimum luminance value;

instructions for generating a grayscale selector value based on the dependent maximum value and the dependent minimum value; and

instructions for quantizing the grayscale selector value by comparing the grayscale selector value with one or more threshold values and assigning the grayscale selector value to one of a finite set of values.