Fast segmentation of images

Systems, apparatuses, and methods are described for performing fast segmentation of an image. In embodiments, an image may be segmented by generating a background mask, generating an edge mask, dilating the edge mask, and refining that edge mask by applying refinement operations that remove edge pixels from the edge mask. In embodiments, the refined edge mask may be used to generate a foreground mask.

BACKGROUND

A. Technical Field

The present invention pertains generally to digital image processing, and relates more particularly to image processing that enables fast segmentation of an image.

B. Background of the Invention

A digital image typically comprises an array of picture elements. Each picture element, also known as a “pixel,” has a value and a location within the array. The value represents either the intensity of the pixel (if in grayscale) or the color of the pixel. At a higher level, pixels may be segmented into two or more groups. For example, pixels of an image may be classified into foreground and background layers or segments.

When processing a digital image, it can be beneficial to differentiate the pixels into different segments. Certain segments of the image may be of more interest than other segments, may be beneficially affected by image processing procedures, or may be adversely affected by image processing procedures. By dividing an image into different segments, one segment may be processed differently than another segment. Different methods for segmenting an image exist. Depending upon the application, it is generally preferred to have a good segmentation process that is efficient and not computationally expensive. The output of post-processing may also be affected by the method of segmentation that is used.

For example, one application of segmentation is document compression. Although compression methods help reduce file sizes, the compressed files are typically not without problems. Conventional image compression approaches that compress an entire image generally lead to unsatisfactory results in reconstructed image quality and compressed file size. When a high compression ratio is used, the compressed images may show disturbing artifacts, such as blurred text and blurred color boundaries. To obtain a high-quality compressed image, the compression ratio may need to be set very low, but the resulting file size will therefore not be substantially reduced. Thus, neither approach is particularly satisfactory. By segmenting an image into foreground and background regions, the foreground may be compressed at a different level than the background.

SUMMARY OF THE INVENTION

Systems, apparatuses, and methods are described for performing fast segmentation of an image. Depending upon the application, it is generally preferred to have a good segmentation process that is efficient and not computationally expensive.

In embodiments, an image may be segmented by generating an edge mask, dilating the edge mask, and refining that edge mask by applying refinement operations that remove edge pixels from the edge mask. Refinement operations may include removing edge pixels that do not satisfy a set of darkness criteria, removing edge pixels that also are labeled background, and removing bright-side edge pixels. In embodiments, the refined edge mask may be used to generate a foreground mask.

In embodiments, the set of darkness criteria comprises an average color value for image pixels within a first neighborhood of a dilated edge pixel being less than a first threshold value; and a difference between the first average color value and a second average color value from a second neighborhood of the dilated edge pixel, which may be smaller than the first neighborhood, being greater than a second threshold value.

In embodiments, a bright-side edge pixel has a color value that is brighter by at least a threshold value than the color value of at least one edge pixel from a neighborhood of the bright-side edge pixel. In embodiments, being brighter by at least a threshold value means that a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a first neighborhood of the bright-side edge pixel is greater than a first threshold; or a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a second neighborhood of the bright-side edge pixel is greater than a second threshold.

In embodiments, generating a background mask comprises the steps of converting the image into grayscale, generating a histogram of grayscale intensity for the image, identifying a dominant background color in a region of the histogram, calculating a background color threshold value using the dominant background color, and assigning a background label to the pixels that have a grayscale intensity value greater than the background color threshold value.

In embodiments, generating the foreground mask comprises using line scans to identify a non-edge pixel segment bounded by a first edge pixel segment and by a second edge pixel segment; and computing a first color value for the first edge pixel segment, a second color value for the second edge pixel segment, and a non-edge-pixel segment color value for the non-edge-pixel segment. If the difference between the non-edge-pixel segment color value and the average of the first and second color values is below a threshold value, and, in embodiments, if a threshold size limit is satisfied, the pixels in the combined first edge pixel segment, second edge pixel segment, and non-edge-pixel segment may be identified as solid region pixels.

In embodiments, the generated foreground mask, refined edge mask, and/or background mask may be used or undergo one or more post-processing operations. For example, in an embodiment, post processing may include compressing the image. In embodiments, the compressed image is a portable document format (“PDF”) image.

In embodiments, a median filter may be applied to non-edge areas of the image.

In embodiments, a system for segmenting an image may comprise a background mask generator, an edge detector, an edge mask dilator, an edge mask refiner, and a foreground mask generator. In embodiments, an edge mask refiner may apply refinement operations that remove edge pixels from the edge mask. Refinement operations may include removing edge pixels that do not satisfy a set of darkness criteria, removing edge pixels that also are labeled background, and removing bright-side edge pixels.

In embodiments, the set of darkness criteria comprises an average color value for image pixels within a first neighborhood of a dilated edge pixel being less than a first threshold value; and a difference between the first average color value and a second average color value from a second neighborhood of the dilated edge pixel, which may be smaller than the first neighborhood, being greater than a second threshold value.

In embodiments, a bright-side edge pixel has a color value that is brighter by at least a threshold value than the color value of at least one edge pixel from a neighborhood of the bright-side edge pixel. In embodiments, being brighter by at least a threshold value means that a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a first neighborhood of the bright-side edge pixel is greater than a first threshold; or a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a second neighborhood of the bright-side edge pixel is greater than a second threshold.

In embodiments, the foreground mask generator may generate a foreground mask using line scans.

In embodiments, the system may also comprise a color matcher, a refiner, and/or post processor. Image enhancement, image compression, watermarking, special effects, and video editing are examples of post-processing operations that may be alternatively performed or alternatively included within embodiments of a system.

In embodiments, an apparatus for refining an edge mask may comprise a dark edge pixel retainer that may remove edge pixels that do not satisfy a set of darkness criteria, a background excluder that may remove edge pixels that also are labeled background, and a bright-side edge pixel remover that may remove bright-side edge pixels.

In embodiments, the set of darkness criteria comprises an average color value for image pixels within a first neighborhood of a dilated edge pixel being less than a first threshold value; and a difference between the first average color value and a second average color value from a second neighborhood of the dilated edge pixel, which may be smaller than the first neighborhood, being greater than a second threshold value.

In embodiments, a bright-side edge pixel has a color value that is brighter by at least a threshold value than the color value of at least one edge pixel from a neighborhood of the bright-side edge pixel. In embodiments, being brighter by at least a threshold value means that a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a first neighborhood of the bright-side edge pixel is greater than a first threshold; or a difference between the color value of the bright-side edge pixel and a color value of at least one edge pixel in a second neighborhood of the bright-side edge pixel is greater than a second threshold.

Some features and advantages of the invention have been generally described in this summary section; however, additional features, advantages, and embodiments are presented herein or will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof. Accordingly, it should be understood that the scope of the invention shall not be limited by the particular embodiments disclosed in this summary section.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Systems, apparatuses, and methods are described for performing fast segmentation of an image. In embodiments, an image may be segmented by generating a background mask, generating an edge mask, dilating the edge mask, and refining that edge mask by applying refinement operations that remove edge pixels from the edge mask. Refinement operations may include removing edge pixels that do not satisfy a set of darkness criteria, removing edge pixels that also are labeled background, and removing bright-side edge pixels. In embodiments, the refined edge mask may be used to generate a foreground mask.

In the following description, for purpose of explanation, specific details are set forth in order to provide an understanding of the invention. It will be apparent, however, to one skilled in the art that the invention may be practiced without these details. One skilled in the art will recognize that embodiments of the present invention, some of which are described below, may be incorporated into a number of different systems and devices including camera, scanners, printers, computers, facsimile machine, mobile devices, including those devices with a display or camera capabilities, multimedia devices, multifunction devices, and the like. The embodiments of the present invention may be implemented in software, hardware, firmware, or combinations thereof.

Components, or modules, shown in block diagrams are illustrative of exemplary embodiments of the invention and are meant to avoid obscuring the invention. It shall also be understood that throughout this discussion that components may be described as separate functional units, which may comprise sub-units, but those skilled in the art will recognize that the various components, or portions thereof, may be divided into separate components or may be integrated together, including integrating within a single system or component.

Furthermore, connections between components/modules within the figures are not intended to be limited to direct connections. Rather, data between these components may be modified, re-formatted, or otherwise changed by intermediary components. Also, additional or fewer connections may be used. It shall also be noted that the terms “coupled” or “communicatively coupled” shall be understood to include direct connections, indirect connections through one or more intermediary devices, and wireless connections.

Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, characteristic, or function described in connection with the embodiment is included in at least one embodiment of the invention and may be in more than one embodiment. The appearances of the phrase “in one embodiment” or “in an embodiment” in various places in the specification are not necessarily all referring to the same embodiment.

It should be noted that the examples illustrated herein deal with images with light background and darker foreground. The examples are provided by way of explanation and not limitation. One skilled in the art shall recognize that the systems and methods discussed herein may be applied to or adapted for images with dark background and lighter foreground. For example, in an embodiment, the present system and methods may negate the color of the image and process the image using the same or similar methods as disclosed herein. In an embodiment, the present systems and methods may determine, for an image or a section of an image, whether it is a light background/darker foreground or dark background/lighter foreground image.

A. System Implementations

FIG. 1depicts a system100for fast segmentation of an image105according to embodiments of the invention. System100comprises a color matcher110, an edge detector115, a background mask generator120, a median filter125, an edge mask dilator130, an edge mask refiner135, a foreground mask generator140, and an image post processor145.

In embodiments, color matcher110receives an input image105and adjusts its color to be closer to the color of its corresponding original image. In embodiments, color matching involves enhancing the image colors and suppressing the background. For example, the input image may be a “scanned image” produced from its corresponding original image by a scanner device. A scanned image usually is darker than its corresponding original image, so the colors in the scanned image may be corrected to more closely represent the colors in the original image. The background of the scanned image may have a color other than white and that background color may be suppressed in order to improve contrast. For example, the paper on which a page is printed may have a color other than true white, which may be the desired background color of the scanned image.

In embodiments, one or more types of color adjustment may be used in performing color matching. One type of adjustment may be a “white point” adjustment, which may be used to adjust a color range supported by a device, such as a scanner. In one example, an original image may cover a grayscale range from 0 to 255, but a scanner may only support a grayscale range from 15 to 200. In an embodiment, a white point adjustment may map the darkest color produced by a scanner to black (0), and the lightest color produced by a scanner to white (255). Using the white point adjustment, a scanned image may be corrected to be a more accurate representation of the range of colors in the original image. Another type of color adjustment may be a color matching table/transform that maps a spectrum of colors produced by a device, such as a scanner, to a spectrum of true colors that may be present in an original image. In embodiments, device dependent color calibration tables/transforms may be provided by device manufacturers. In alternative embodiments, one or more default color calibration tables/transforms may be used. In other alternative embodiments, no color matching table may be available, but methods known to those skilled in the art may be used to dynamically construct a color matching table such as, for example, using a white point adjustment. It should be noted that color matching may be beneficial when the image information is being communicated between devices, such as, for example from one copier to another copier or to a computer screen. Accordingly, the color matcher may provide adjustments given the intended output display. In embodiments, the labeled image may be used to perform differential enhancement for viewing or printing of the compressed image. For example, printing often requires higher levels of sharpening for high-quality text than what would be required for viewing on a computer screen. The label information may also be used to switch between printer/screen color tables to improve the rendering of the image or portions thereof, such as non-halftone edges that typically correspond to text on background regions. For example, lower frequency screens may be used over pixels labeled halftone edge or halftone to improve tone stability in devices such as color laser printers and may also provide a greater number of tones.

In embodiments, an edge detector115receives a color adjusted image and produces an edge mask in which the edge pixels are identified or labeled. In embodiments, a pixel may be labeled an “edge pixel” if it is located in a boundary region between two regions of an image such as, for example, foreground and background regions. The foreground region of an image typically contains the most important information in an image. For example, the text and graphics of an image of a document page are typically considered to be in the foreground region of the image, while the paper and associated watermarks are typically considered to be in the background region of the image. Identification of the boundary between the foreground and background regions of an image facilitates identification of the regions.

Those skilled in the art will recognize that numerous edge detection methods may be used to identify edge pixels within an image and to generate an edge mask. One example edge detection method is Sobel edge detection. In embodiments, edge detector115may use two convolution masks to detect both horizontal and vertical edges. In embodiments, Sobel edge detection may be applied to a grayscale version of the image to compute an approximate gradient magnitude for each pixel. Pixels with a gradient magnitude larger than a predefined grayscale threshold may be classified as edge pixels.

In alternative embodiments in which there may be some foreground regions with similar intensity to the background (for example, an image of a page containing yellow text on a bright background), edge detection may additionally include an application of edge detector115in a color channel, such as, using the color values in the blue (B) channel of pixel red-green-blue (RGB) color values. For the example of yellow text on a bright background, the intensity gradient magnitude in the B channel calculated for a pixel may be compared to a predefined yellow-scale threshold value instead of to a predefined grayscale threshold value in order to identify edge pixels.

In embodiments, background mask generator120receives a color adjusted image and performs an analysis of the image pixels in order to identify (label) the pixels in the background region. In embodiments, the image pixel colors are converted to grayscale, and a histogram of the pixels' grayscale values is plotted. In embodiments, an analysis of the histogram determines a “dominant background color.” In embodiments, the dominant background color may be set as the brightest color shared by the largest group of pixels; alternatively, the dominant background color may be the average color (mean, median, or mode) of pixels in a region of the histogram. In embodiments, the dominant background color is used to compute a background color threshold value. All pixels with a color value greater than (brighter than) the background color threshold may be identified (labeled) as background pixels. A background mask may be generated from the set of labeled background pixels in the image.

In embodiments, median filter125receives a color adjusted image with labeled edge pixels. Median filtering may be used to remove artifacts, such as Moire patterns, from non-edge areas of the image.

In embodiments, edge mask dilator130receives an edge mask and applies a dilation operation to the edge pixels in the edge mask in order to generate a dilated edge mask. In embodiments, a one pixel dilation may be applied to each edge pixel in the edge mask. In embodiments, a 3×3 square dilation object may be applied to the edge pixels. Those skilled in the art will recognize that various types and sizes of dilation objects may be used in a dilation operation. The dilated edge mask will have enhanced, or thicker, edges than the received edge mask. An edge pixel that was not assigned an edge label by an edge detector but was assigned an edge label as a result of edge pixel dilation may be referred to as a “dilated edge pixel.”

In embodiments, edge mask refiner135receives a dilated edge mask and applies at least one refinement operation to the edge pixels in the dilated edge mask to more precisely define the edges in the image. A refinement operation applies additional classification criteria to an edge pixel that may result in removing an edge pixel from the edge mask. In embodiments, the refinement operation may result in re-labeling the edge pixel as a background pixel. A refined thin edge mask is generated from the dilated edge mask after application of at least one refinement operation.

In embodiments, foreground mask generator140receives a refined thin edge mask, which may be used to generate a foreground mask. In embodiments, horizontal and/or vertical line scans may be used to identify a non-edge-pixel segment bounded by a first edge pixel segment and a second edge pixel segment. A first color value may be computed for the first edge pixel segment. A second color value may be computed for the second edge pixel segment, and a non-edge-pixel segment color value may be computed for the non-edge-pixel segment. In embodiments, a segment may be one or more pixels, and the color values may be the mean, median, or mode of a segment. In embodiments, responsive to the difference between the non-edge-pixel segment color value and the average of the first and second color values being below a threshold value, the combined first edge pixel segment, second edge pixel segment, and non-edge-pixel segment may be identified as solid color region pixels and included in the image foreground mask. One skilled in the art will recognize that the larger the threshold value, the more variance in color the segments may have and still be classified as a solid color region.

In embodiments, the selection of a solid color region may include a size constraint. One or more of the lengths of the combined length of the first edge pixel segment, second edge pixel segment, and non-edge-pixel segment; the combined length of the first edge pixel segment and non-edge-pixel segment; the combined length of the second edge pixel segment and non-edge-pixel segment; and the length of the non-edge-pixel segment, may be required to be below a threshold length or lengths. If the size constraint is met, the combined first edge pixel segment, second edge pixel segment, and non-edge-pixel segment may be identified as solid color region pixels and included in the image foreground mask. In embodiments, additional or alternative constraints may be imposed upon a line scan in order for it to be classified as solid color pixels. An additional or alternative constraint may be that at least a portion of the preceding line scan be identified as edge pixels or solid color pixels.

In embodiments, image post processor145receives the segmentation information and the color adjusted image. One skilled in the art shall recognize that, having obtained image layers or segments, any of a number of post-processing operations may be performed in order to generate output150. Image enhancement, image compression, watermarking, special effects, and video editing are examples of post-processing operations that may be alternatively performed or alternatively included within a system, such as system100.

One example of a post-processing operation is document compression. Because the background layer typically does not contain important information, as part of post processing, the background layer may undergo more aggressive compression than the foreground layer. In embodiments, a high-quality, compact PDF document may be generated from an image created by a scanner device.

Turning now toFIG. 2, depicted in the figure is an edge mask refiner apparatus135that receives an edge mask and applies at least one refinement operation to the edge pixels in the edge mask in order to more precisely define the edges in the image according to embodiments of the invention. The edge mask refiner135comprises a dark edge pixel retainer205, a background excluder215, and a bright-side edge pixel remover220.

In embodiments, dark edge pixel retainer205receives an edge mask and re-labels as background any edge pixel that was not labeled as a result of edge detection or does not satisfy at least one of a set of darkness criteria. In embodiments, darkness criteria may be examined by computing the average color of image pixels within a defined neighborhood of the edge pixel and then comparing that average to a threshold value. In embodiments described herein, “average” may refer to the mean, median, or mode.

In embodiments, background excluder215receives an edge mask and applies a “conflict test” to the edge pixels. Any edge pixel that has been labeled a background pixel in the image background mask has its edge label removed and therefore it is removed from the edge mask.

In various embodiments, bright-side edge pixel remover220receives an edge mask and removes from the edge mask any edge pixel that does not satisfy at least one of a set of edge darkness criteria. In embodiments, the edge pixel may be re-labeled as background. In embodiments, edge darkness criteria are examined by computing the differences between the color of the edge pixel and the colors of edge pixels within a neighborhood of the edge pixel and then comparing the differences to a threshold value.

FIG. 3depicts a system300for fast segmentation of an image305according to embodiments of the invention. System300comprises an edge detector310, a background mask generator315, an edge mask dilator320, an edge mask refiner325, and a foreground mask generator330. In system300, some of the optional components of system100have been removed.

A color matcher110is not comprised within embodiments of system300because color correction may be applied to an input image305while it is being generated. For example, a scanned image may have color correction applied by the scanner as part of the scanning operation.

Furthermore, filtering may be considered an optional process. Accordingly, a median filter125may not be within various embodiments of system300.

B. Methods for Fast Image Segmentation

FIG. 4depicts a method400for fast segmentation of an image according to embodiments of the invention. Method400may be implemented in embodiments of system100.

1. Color Matching

In step405, the color of an input image is adjusted to be closer to its corresponding original image by applying color matching to the input image. Step405may be implemented by embodiments of color matcher110. In embodiments, color matching involves enhancing the image colors and suppressing the background. For example, the input image may be a “scanned image” produced from its corresponding original image by a scanner device. A scanned image usually is darker than its corresponding original image, so the colors in the scanned image may be corrected to more closely represent the colors in the original image. The background of the scanned image may have a color other than white and that background color may be suppressed in order to improve contrast. For example, the paper on which a text page is printed may have a color other than true white, which may be the desired background color of the scanned image.

In embodiments, one or more types of color adjustment may be used in performing color matching. One type of adjustment may be a “white point” adjustment, which may be used to adjust a color range supported by a device, such as a scanner. In one example, an original image may cover a grayscale range from 0 to 255, but a scanner may only support a grayscale range from 15 to 200. In an embodiment, a white point adjustment may map the darkest color produced by a scanner to black (0), and the lightest color produced by a scanner to white (255). Using the white point adjustment, a scanned image may be corrected to be a more accurate representation of the range of colors in the original image. Another type of color adjustment may be a color matching table/transform that maps a spectrum of colors produced by a device, such as a scanner, to a spectrum of true colors that may be present in an original image. In embodiments, device dependent color calibration tables/transforms may be provided by device manufacturers. In alternative embodiments, one or more default color calibration tables/transforms may be used. In other alternative embodiments, no color matching table may be available, but methods known to those skilled in the art may be used to dynamically construct a color matching table such as, for example, using a white point adjustment. It should be noted that color matching may be beneficial when the image information is being communicated between devices, such as, for example from one copier to another copier or to a computer screen. Accordingly, the color matcher may provide adjustments given the intended output display. In embodiments, the labeled image may be used to perform differential enhancement for viewing or printing of the compressed image. For example, printing often requires higher levels of sharpening for high-quality text than what would be required for viewing on a computer screen. The label information may also be used to switch between printer/screen color tables to improve the rendering of the image or portions thereof, such as non-halftone edges that typically correspond to text on background regions. For example, lower frequency screens may be used over pixels labeled halftone edge or halftone to improve tone stability in devices such as color laser printers and may also provide a greater number of tones.

2. Edge Pixel Detection

Step410employs edge detection to label (identify) edge pixels in the color adjusted image and generate an edge mask. Step410may be implemented by embodiments of edge detector115,310.

Those skilled in the art will recognize that numerous edge detection methods may be used to identify edge pixels within an image and to generate an edge mask. One example edge detection method is Sobel edge detection. In embodiments, edge detection may involve using two convolution masks to detect both horizontal and vertical edges. In embodiments, Sobel edge detection may be applied to a grayscale version of the image to compute an approximate gradient magnitude for each pixel.FIG. 5illustrates two 3×3 masks that are convolved with the grayscale intensity image to compute the gradient values in both horizontal (Gx)500-A and vertical (Gy)500-B directions for each pixel. A pixel's absolute gradient magnitude may be computed as |G|=|Gx|+|Gy|. Pixels with a gradient magnitude larger than a predefined grayscale threshold may be classified as edge pixels.

In alternative embodiments, edge detection may additionally include an application of edge detector115in a color channel, such as, using the color values in the blue (B) channel of pixel red-green-blue (RGB) color values. For the example of yellow text on a bright background, the intensity gradient magnitude |G|=|Gx|+|Gy| calculated for each pixel in the B channel may be compared to a predefined yellow scale threshold value instead of to a predefined grayscale threshold value in order to identify edge pixels.

3. Background Pixel and Color Estimate

In step415, an analysis of the image pixels may be performed to identify (label) the pixels in the background region.FIG. 6depicts a method600to perform this analysis according to various embodiments. Method600may be implemented by embodiments of background mask generator120,315. In embodiments, the image pixel color values are converted to grayscale values (step605), and a histogram of the pixels' grayscale values is generated (step610).FIG. 7illustrates an example of a histogram700of the grayscale intensity values710of the pixels705in an image according to various embodiments. In embodiments, an analysis of the histogram determines (step615) a background intensity μ (715) as a “dominant background color.” In this case, the dominant background color is the brightest color shared by the largest group of pixels. In an embodiment, the dominant background color may be the average (mean, median, or mode) of pixel values in a region of the histogram. In embodiments, the dominant background color may be used to compute a “background color threshold” value, for example, μ−σ (720) where σ is a predefined threshold. In various embodiments, σ may function like or be related to the variance of background intensity. A pixel may be labeled (step620) as a background pixel725if its intensity is greater than the background color threshold value. A background mask may be generated from the set of labeled background pixels in the image.

In embodiments, median filtering (step425) may be applied to non-edge areas of the image to mitigate artifacts, such as Moire patterns that may have been introduced as the image was generated by a scanner device. Median filtering may be implemented by embodiments of median filter125. In step420, a decision is made to determine if the input image was generated by a scanner device. Filtering may be considered an optional process.

In step430, a dilation operation is applied to the edge pixels in the edge mask in order to generate a dilated edge mask. Step430may be implemented by embodiments of edge mask dilator130,320. In embodiments, a one-pixel dilation may be applied to the edge pixels in the edge mask. In embodiments, this entails applying a 3×3 square dilation object to the edge pixels. Those skilled in the art will recognize that various types and sizes of dilation objects may be used in a dilation operation. The dilated edge mask will have enhanced, or thicker, edges than the received edge mask. An edge pixel that was not assigned an edge label by an edge detector but was assigned an edge label as a result of edge pixel dilation may be referred to as a “dilated edge pixel.”

6. Methods for Edge Mask Refinement

In step435, at least one refinement operation is applied to the edge pixels in the dilated edge mask in order to refine the edges. A refinement operation applies additional classification criteria to an edge pixel that may result in removing that pixel as an edge pixel. In embodiments, the edge pixel may be re-labeled as background.

A refined thin edge mask is generated from the dilated edge mask after application of at least one refinement operation. In alternative embodiments, step435may be applied to or adapted for an edge mask in which dilation has not been applied to the edge pixels. Step435may be implemented by embodiments of edge mask refiner135,325. In alternative embodiments, edge mask refinement may be applied to an edge mask that was generated using any method known to those skilled in the art provided information about the background regions also is known or may be obtained.

FIG. 8depicts a method800for edge mask refinement according to various embodiments. Method800comprises the steps of retaining dark edge pixels (805), excluding background pixels (810), and removing bright-side edge pixels (815). In alternative embodiments, the order of the steps may affect the refinement. The ordering of steps depicted inFIG. 8may bias the edge mask refinement towards the foreground region. This bias may be desirable for text preservation in a document compressing application, for example. In alternative embodiments in which step805is executed last, the edge mask refinement may be biased towards the background regions. This bias may be desirable for processing of a photo image containing scenes of people or landscapes, for example. In alternative embodiments, all steps may not be performed. Method800may be implemented by embodiments of edge mask refiner135,325.

a) Methods for Retaining Dark Edge Pixels

FIG. 9depicts a method900for retaining edge pixels in an edge mask that satisfy at least one of a set of darkness criteria according to embodiments of the invention. Method900may be implemented as step805of embodiments of method800, and by embodiments of dark edge pixel retainer205. A darkness criterion is examined by determining the average color value of image pixels within a defined neighborhood around an edge pixel, and comparing that average color value to a predefined threshold value.

In step905, an edge pixel in an edge mask is identified. In step910, an average color value C1of image pixels within a first neighborhood, such as a 9-by-9 (9×9) neighborhood, of the edge pixel is calculated. In step915, an average color value C2of image pixels within a second neighborhood, such as a 3×3 neighborhood, of the edge pixel is calculated. Darker colors have smaller values. A first image region darkness threshold TD1and a second image region darkness threshold TD2are defined. For example, in an embodiment TD1may be defined to be 32 and TD2may be defined to be 4.

In a decision analysis (step920), the edge pixel's label is retained (step925) if at least one of the following criteria are met:

1. The edge pixel's edge label was assigned by an edge detector;

2. The edge pixel is part of a dark region (C1<TD1); or

3. The edge pixel's neighboring image pixels are dark ((C1−C2)>TD2).

In alternative embodiments, for example, cases in which the edge mask is not a dilated edge mask, the first criterion may not be applied. If none of the criteria are met, the edge pixel may be removed from the edge mask (step930). One skilled in the art shall recognize that each criterion may be determined or evaluated separately and that if one criterion has been met that the remaining criteria need not be examined.

b) Methods for Excluding Background Pixels

FIG. 10depicts a method1000for excluding background pixels from an edge mask according to various embodiments of the invention. Method1000may be implemented as step810of embodiments of method800, and by embodiments of background excluder215. In step1005, an edge pixel within the edge mask is identified. A “conflict test” decision analysis (step1010) is applied to the edge pixel. If that pixel also was labeled a background pixel (e.g., during method600), the label conflict may be resolved by removing edge label from the pixel and removing the pixel from the edge mask (step1015). Alternatively, any edge pixel with a color the same or lighter than a background region color or colors may be removed from the edge mask.

c) Methods for Bright-Side Edge Pixel Removal

FIG. 11depicts a method1100for removing bright-side edge pixels from an edge mask according to various embodiments of the invention. Method1100may be implemented as step815of embodiments of method800, and by embodiments of bright-side edge pixel remover220. In embodiments, a “bright-side edge pixel” is an edge pixel that is brighter by at least a threshold amount than its neighboring edge pixels within a region or regions.

In the depicted embodiment ofFIG. 11, the color CPof an edge pixel in the edge mask is identified (step1105), and the difference between the color CPof the identified edge pixel and the color values of the edge pixels contained within one or more neighborhoods is determined.

FIG. 12illustrates examples of how neighboring regions1200,1210may be defined according to various embodiments. Those skilled in the art will recognize that the illustrated regions are examples and that other sized and configured neighborhoods may be used. Neighborhood1200is a partial 5×5 neighborhood that includes neighboring pixels within a distance less than 2.5 pixels from the edge pixel1205. Neighborhood1200is a partial 5×5 neighborhood that includes neighboring pixels within a distance less than 2.5 pixels from the edge pixel1205. Neighborhood1210is a 3×3 neighborhood. In embodiments, a subset neighborhood may be used; for example, neighborhood1215, which represents the partial 5×5 neighborhood minus the 3×3 neighborhood, may be used in determining whether a pixel located at location1205is a bright-side edge pixel.

In step1110, a difference is calculated between the color CPand the color Cfof edge pixels within a first neighborhood (such as, for example, within the 3×3 neighborhood1210) of an edge pixel1205. In step1115, if the difference between the colors of the edge pixels is greater than a first bright-side threshold, T1, the edge pixel at location1205may be removed (step1145) from the edge mask. In an embodiment, that edge pixel may be labeled as a background pixel. If the difference between the colors of the edge pixels is not greater than a first bright-side threshold, T1, the process may be repeated (step1120) for another neighboring edge pixel.

In embodiments, if no other edge pixels exist within the first neighborhood, the process may stop. Alternatively, as depicted inFIG. 11, one or more additional regions may be examined. In step1125, a difference is calculated between the color CPand the color Csof edge pixels within a second neighborhood (such as, for example, within the partial 5×5 neighborhood1200) of an edge pixel1205. In step1130, if the difference between the colors of the edge pixels is greater than a second bright-side threshold, T2, the edge pixel at location1205may be removed (step1145) from the edge mask. In an embodiment, that edge pixel may be labeled as a background pixel. If the difference between the colors of the edge pixels is not greater than a first bright-side threshold, T1, the process may be repeated (step1135) for another neighboring edge pixel. One skilled in the art shall recognize that in embodiments where T1is less than T2, the second neighborhood may be limited to1215. In embodiments, T2may be defined to be greater than T1based on an assumption that more distant neighboring edge pixels may be brighter. For example, in an embodiment T2may be defined to be 112 and T1may be defined to be 96.

In alternative embodiments, Cfmay be the average color of edge pixels within a first neighborhood and Csmay be the average color of edge pixels within a second neighborhood.

Returning toFIG. 11, if the edge pixel of interest (e.g., the edge pixel at location1205) is not brighter by a threshold amount than its neighboring edge pixels, the edge pixel's edge label is retained (step1140).

One skilled in the art shall recognize that other methods or ordering may be used to achieve the same or similar result as the methods depicted inFIG. 11and that such other methods are within the scope of the present invention.

7. Method for Generating an Image Foreground Mask

In step440, the refined thin edge mask generated from the refined dilated edge mask may be used to generate a foreground mask for the image. Step440may be implemented within embodiments of foreground mask generator140.

FIG. 13depicts a method1300for performing a color consistency analysis to extract regions, such as text items lying on image regions, in an image according to various embodiments of the invention. Method1300may be implemented within embodiments of step440, and within embodiments of foreground mask generator140. Horizontal and/or vertical line-by-line scans may be performed (step1305) using the edge information, or a portion thereof. For each line scan, the line segments or regions, if any, are identified (step1310) by pixel label type. It shall be noted that a line segment or region may be one or many pixels in size.

Illustrated inFIG. 14are two horizontal line scans1420,1425of a portion of a document containing the letter “A.” The border1405of the letter “A”1400represents the edge pixels obtained from the edge mask. The interior pixels1410represent halftone or non-halftone pixels. The letter A1400resides on an image region1415that may be background, halftone, or non-halftone pixels. Because line scan1420does not intersect any of letter A1400, it is a single line segment. Note, however, that line scan1425intersects letter A1400at several places. The first segment, a, comprises the pixels from the start of the line scan until the start of the edge pixels1405of the letter A1400. Segments b and d comprise edge pixels of the edge of the letter A1400; segment c comprises interior pixels of the letter A1400between the two edge pixel boundary segments, b and d; and so forth. A comparison is made (step1315) of the segments to identify regions, such as text regions. In various embodiments, the color of segment c may be compared (step1315) against the color of segment b with the color of segment d. If the difference in color between segment c and the edge segments b and d is below some threshold level, then the segments may be considered as part of a single solid region and may be classified (step1330) as such. If the difference in color between segment c and the edge segments b and d exceeds the threshold level, then the segments may not be classified (step1325) as a solid color region. In an embodiment, the color of the segment bounded by edge pixels, in this case segment c, may be compared against an average of the colors of the two bounding edge pixels segments, segments b and d. If the difference between the values is below a solid color region threshold level Tscr, as shown in the following formula:

the segments may be classified as a solid color region (step1330). In an embodiment, the average (mean, median, or mode) color of the segments may be used in the comparison process. In embodiments, any background pixels that reside along a line segment that has been classified as a solid region may not be classified as solid region but may remain as background pixels. One skilled in the art will recognize that the larger the threshold value (Tscr), the more variance in color the segments may have and still be classified as a solid color region.

In embodiments, the edge labels may be added to all or a portion of the image to avoid artifacts when items, such as text, appears at the image border. Consider, by way of illustration, the region1430appearing inFIG. 14, wherein edge pixels1435along the image border have been added. In the depiction, the darker exterior indicates pixels labeled as edge pixels and the lighter interior pixels represent non-edge pixels. When performing the color consistency analysis, a line scan will identify a line segment through region1430as being a solid region, assuming the other conditions are met, because it will be bounded by two edge pixels1435and1440.

In embodiments, additional conditions may be applied (step1320) as part of the color consistency analysis. An additional condition may include examining the neighboring pixels of the immediately preceding line segment. If the neighboring pixels are not substantially edge pixels or are not substantially identified as a solid region during its color consistency analysis, then the line segment may not be identified (step1325) as a solid region.

Consider, for purposes of illustration, the following example. Assuming that the segments b, c, and d met the conditions that the difference in color between segment c and the edge segments b and d was below a threshold level, the neighboring pixels to combined line segment b+c+d that were previously examined may be checked to determine if a number exceeding a threshold value of those pixels were also identified as a solid region. For example, assuming the line-by-line scan proceeded from top to bottom, the line segment of pixel neighboring line segment b+c+d would be the pixels directly above, as identified by line1445inFIG. 12. In an embodiment, if a threshold number of pixels on line1445had been identified as a solid region, line segment b+c+d would also be identified as a solid region; otherwise, line segment b+c+d would not be identified as a solid region.

In embodiments, the color consistency analysis may also include one or more threshold size restrictions or limitations. For example, if combined line segment b+c+d exceeds a threshold number of pixels, it may also be excluded from being classed as a solid color region. One skilled in the art shall recognize that a threshold size limit may be placed on any combination of the segments or any portion thereof.

In embodiments, a restriction may be placed on the brightness of pixels that may be classified as a solid region. For example, a set range of light colors may be excluded from being classified as a solid region.

One skilled in the art will recognize that the threshold levels and restrictions, including but not limited to, the maximum color variation, the maximum width, and the brightness of colors of such regions may be configured differently according to a number of factors, including but not limited to the operation mode (text, magazine, or photo) and the type of desired text (background or halftone).

8. Image Post Processing

One skilled in the art shall recognize that, having obtained image layers, any of a number of post-processing operations may be optionally performed (step445). Image enhancement, image compression, watermarking, special effects, and video editing are examples of post-processing operations that may be alternatively performed or alternatively included within a system, such as system100,300.

a) Layer-Based Compression and Composite Generator

In embodiments, system100, or portions thereof, may be used to help generate compressed documents. The compressed document may represent a composite of compressed segmented image layers and may have enhanced visual quality and much smaller file size. In an embodiment, the resulting compression document may be in a portable document format (“PDF”), but one skilled in the art shall recognize that other viewers and formats may be employed.

In embodiments, the background and foreground image layers may be compressed using one or more compression algorithms. In an embodiment, a JPEG compression with the same or different compression ratios may be used to compress the background and foreground image layers.

In an embodiment, the composite of two compressed image layers (foreground and background) may be achieved by maintaining an image mask that identifies foreground pixels. In one embodiment, this mask may be kept intact with lossless compression, such as JBIG2, to minimize file size. In an embodiment, the foreground and background image layers may be downsampled, such as, for example, by a ratio of 3:1, and the mask may be maintained at a ratio of 1:1. In embodiments, system100may include a downsampler (not shown) to downsample the foreground and/or background image layers.

It shall be noted that the present invention may be implemented in any instruction-execution/computing device or system capable of processing the image data, including without limitation, a general-purpose computer and a specific computer, such as one intended for graphics processing. The present invention may also be implemented into other computing devices and systems, including without limitation, a digital camera, a printer, a scanner, a multiple function printer/scanner, a facsimile machine, a multimedia device, and any other device that processes, captures, transmits, or stores an image. Furthermore, within any of the devices, aspects of the present invention may be implemented in a wide variety of ways including software, hardware, firmware, or combinations thereof. For example, the functions to practice various aspects of the present invention may be performed by components that are implemented in a wide variety of ways including discrete logic components, one or more application specific integrated circuits (ASICs), and/or program-controlled processors. It shall be noted that the manner in which these items are implemented is not critical to the present invention.

FIG. 15depicts a functional block diagram of an embodiment of an instruction-execution/computing device1500that may implement or embody embodiments of the present invention. As illustrated inFIG. 15, a processor1502executes software instructions and interacts with other system components. In an embodiment, processor1502may be a general purpose processor such as an AMD processor, an INTEL x86 processor, a SUN MICROSYSTEMS SPARC, or a POWERPC compatible-CPU, or the processor may be an application specific processor or processors. A storage device1504, coupled to processor1502, provides long-term storage of data and software programs. Storage device1504may be a hard disk drive and/or another device capable of storing data, such as a computer-readable media (e.g., diskettes, tapes, compact disk, DVD, and the like) drive or a solid-state memory device. Storage device1504may hold programs, instructions, and/or data for use with processor1502. In an embodiment, programs or instructions stored on or loaded from storage device1504may be loaded into memory1506and executed by processor1502. In an embodiment, storage device1504holds programs or instructions for implementing an operating system on processor1502. In one embodiment, possible operating systems include, but are not limited to, UNIX, AIX, LINUX, Microsoft Windows, and the Apple MAC OS. In embodiments, the operating system executes on, and controls the operation of, the computing system1500.

An addressable memory1506, coupled to processor1502, may be used to store data and software instructions to be executed by processor1502. Memory1506may be, for example, firmware, read only memory (ROM), flash memory, non-volatile random access memory (NVRAM), random access memory (RAM), or any combination thereof In one embodiment, memory1506stores a number of software objects, otherwise known as services, utilities, or modules. One skilled in the art will also recognize that storage1504and memory1506may be the same items and function in both capacities. In an embodiment, one or more of the components ofFIG. 1,2, or3may be modules stored in memory1504,1506and executed by processor1502.

In an embodiment, computing system1500provides the ability to communicate with other devices, other networks, or both. Computing system1500may include one or more network interfaces or adapters1512,1514to communicatively couple computing system1500to other networks and devices. For example, computing system1500may include a network interface1512, a communications port1514, or both, each of which are communicatively coupled to processor1502, and which may be used to couple computing system1500to other computer systems, networks, and devices.

In an embodiment, computing system1500may include one or more output devices1508, coupled to processor1502, to facilitate displaying graphics and text. Output devices1508may include, but are not limited to, a display, LCD screen, CRT monitor, printer, touch screen, or other device for displaying information. Computing system1500may also include a graphics adapter (not shown) to assist in displaying information or images on output device1508.

One or more input devices1510, coupled to processor1502, may be used to facilitate user input. Input device1510may include, but are not limited to, a pointing device, such as a mouse, trackball, or touchpad, and may also include a keyboard or keypad to input data or instructions into computing system1500.

In an embodiment, computing system1500may receive input, whether through communications port1514, network interface1516, stored data in memory1504/1506, or through an input device1510, from a scanner, copier, facsimile machine, or other computing device.

One skilled in the art will recognize no computing system is critical to the practice of the present invention. One skilled in the art will also recognize that a number of the elements described above may be physically and/or functionally separated into sub-modules or combined together.

While the invention is susceptible to various modifications and alternative forms, specific examples thereof have been shown in the drawings and are herein described in detail. It should be understood, however, that the invention is not to be limited to the particular forms disclosed, but to the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the scope of the appended claims.