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

• US 20050180628A1
• Filed: 02/12/2004
• Published: 08/18/2005
• 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.
• Granted Patent: US 7,379,587 B2
• Time in Patent Office: Days
• 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 to how to combine the current pixel into an existing or into the background image, or start a new blob. The blob identifier outputs a lists 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 pixel of each line to edge continuity values of pixels within a first neighborhood of the pixel to generate compare results; and

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

2. The apparatus of claim 1, further comprising:

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

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

3. The apparatus of claim 2, wherein

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 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.

4. The apparatus of claim 1, wherein the first neighborhood of the pixel includes pixels within a line of the pixel and a line previous to the line of the pixel named a top line, the top line including pixels having positions in the top line that are aligned to positions of pixels of the line, a pixel in the top line having a corresponding position of the 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 pixel in the line being a left-adjacent pixel.

5. The apparatus of claim 2, wherein the second neighborhood of the pixel includes a window of pixels surrounding the pixel.

6. The apparatus of claim 4, wherein

the first comparator compares the edge continuity value of the 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 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.

7. The apparatus of claim 6, wherein

the assigner uses an action table to determine whether to assign the 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.

8. The apparatus of claim 1, wherein

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

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

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

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

12. A method, comprising:

comparing an edge continuity value of a pixel of each line to edge continuity values of pixels within a first neighborhood of the pixel to generate compare results; and

assigning a blob identification of a blob to the pixel based on the compare results to associate the pixel with the blob.

13. The method of claim 12, further comprising:

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

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

14. The method of claim 13, further comprising:

comparing luminance values of pixels within the second neighborhood of the 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.

15. The method of claim 12, wherein the first neighborhood of the pixel includes pixels within a line of the pixel and a line previous to the line of the pixel named a top line, the top line including pixels having positions in the top line that are aligned to positions of pixels of the line, a pixel in the top line having a corresponding position of the 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 pixel in the line being a left-adjacent pixel, the method further comprising:

comparing the edge continuity value of the 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 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.

16. The method of claim 15, further comprising:

using an action table to determine whether to assign the 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.

17. The method of claim 12, further comprising:

outputting a table which contains a list of blob identifications associated with pixels of the current line.

18. A blob identifier, comprising:

means for comparing an edge continuity value of a pixel of each line to edge continuity values of pixels within a first neighborhood of the pixel to generate compare results; and

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

19. The blob identifier of claim 18, wherein the means for assigning further comprises:

table means for determining whether to assign the 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.

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

instructions for comparing an edge continuity value of a pixel of each line to edge continuity values of pixels within a first neighborhood of the pixel to generate compare results; and

instructions for assigning a blob identification of a blob to the pixel based on the compare results to associate the pixel with the blob.