Image analysis – Image segmentation
Reexamination Certificate
1999-08-23
2003-11-18
Au, Amelia M. (Department: 2623)
Image analysis
Image segmentation
C382S174000, C382S104000
Reexamination Certificate
active
06650775
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method and apparatus for implementing a streaming two-dimensional digital image segmentation. More particularly, the invention is related to an image segmentation method that is compatible with architectures for scan-line processing and streaming image data. The method of the invention is accomplished by detecting horizontal runs of adjacent non-background image elements potentially having a particular property, calculating an average strength value of the property for each run and comparing it to a threshold. A separate strength value for the property and run start position are also kept for each vertical column of image elements. Thus, an average strength value of a vertical run can also be calculated for each image element in the horizontal run and compared with the average strength value for the horizontal run. If the results agree, the image elements are tagged accordingly (i.e. whether the property is present). However, a strategy for resolving the results is implemented when the horizontal and vertical analyses do not agree. Several predetermined schemes for doing so are contemplated.
While the invention is particularly directed to the art of image segmentation useful for implementation with digital image processing devices such as copiers, scanners, fax machines, etc. and will be thus described with specific reference thereto, it will be appreciated that the invention may have usefulness in other fields and applications. For example, the invention may be used in any application where there is a desire to perform analysis of the properties of a digital image but a lack of sufficient storage space and/or capability in a system to store and/or manipulate a complete image.
By way of background, in order to provide the optimal rendition of a rasterized image, it is useful to understand the characteristics of the image. Different rendering and/or compression techniques can be applied depending on factors such as whether the image is color or black-and-white, whether it is picture or text, or whether it is halftoned or continuous tone. It is therefore useful to determine whether properties such as color, half-tone, text, . . . etc. are present in particular regions of the image.
From a practical standpoint, a page may not have uniform characteristics, but rather may be composed of regions that have their own respective properties. For example, a page may contain a region with a colored picture and another region with black-and-white text. For optimal rendering, analyzing the page to discover these regions and to identify their characteristics is required. This constitutes one approach to image segmentation.
In addition, the page image sought to be segmented may be generated from the scan of a digital copier. In this situation, there may be no information about the page other than the scanned raster image, so the segmentation is based solely on the image data. These circumstances may also require that the image data stream from the scanner to the printer. Thus, the full image is not stored at any one time. This means that the segmentation processing is limited to one or, at most, a few scan lines of the image for analysis.
Accordingly, known region identification methods that operate under this streaming constraint are one dimensional. Such methods analyze the streaming data within the scan and segment the scan into regions. Each scan is essentially processed independently.
For example, U.S. Pat. No. 5,850,474 to Fan has taught that segmentation can be done by first performing a local micro-analysis to determine the properties of pixels or blocks of pixels, and then by conducting a macro-analysis to group those pixels or blocks into regions, and to identify the characteristic properties of the regions.
Because such known methods are one dimensional, information for implementing the segmentation is necessarily limited. It would be desirable to make available more information upon which to base decisions on the segmentation.
The present invention contemplates a new and improved digital image segmentation method that resolves the above-referenced difficulties and others. More particularly, this invention is directed to a two-dimensional image segmentation that can be accomplished even though the image data is limited to only a few scans at any time.
SUMMARY OF THE INVENTION
A method and apparatus for implementing a streaming two-dimensional digital image segmentation are provided. The digital image is comprised of a plurality of image elements disposed in an arrangement of horizontal rows and vertical columns. The image elements include a first type positioned in a background portion and a second type positioned in a non-background portion, the second type of the image elements each having a value defining a strength of a property, there being at least two classifications of the second type of image elements based on the property.
In one aspect of the invention, the method comprises steps of determining whether selected image elements positioned along a horizontal row are of the second type, calculating a first characteristic function value of the property values of the selected image elements if the selected image elements are of the second type, determining whether the first characteristic function value meets a predetermined threshold to obtain a first classification result, calculating a second characteristic function value for each of the selected elements—the second characteristic function value being based on a stored value calculated from the property values of the each selected element and adjacent image elements of the second type disposed along a vertical column in which the each selected element is positioned, determining whether each of the second characteristic function values meets the predetermined threshold to obtain respective second classification results and classifying each of the selected elements based on the first and second classification results.
In a more limited aspect of the invention, determining whether selected image elements positioned along a horizontal row are of the second type includes scanning the digital image on an image element by image element basis and detecting whether image elements being scanned are white.
In a more limited aspect of the invention, the method further comprises summing the values of a property of adjacent successive image elements of the second type disposed along the horizontal row.
In a more limited aspect of the invention, the method further comprises determining a number of the adjacent successive image elements of the second type.
In a more limited aspect of the invention, calculating of the first characteristic function value includes calculating an average based on the values summed and the number of determined adjacent successive image elements of the second type.
In a more limited aspect of the invention, the method further comprises determining a number of the image elements upon which the stored value is based.
In a more limited aspect of the invention, the value of a property of an image element is added to a stored value for the column of that image element to update that stored value.
In a more limited aspect of the invention, the second characteristic function value is further based on the number determined.
In a more limited aspect of the invention, the property is one of color, half-tone and text.
In a more limited aspect of the invention, classifying each of the selected elements includes resolving inconsistencies in the first and second classification results in a predetermined manner.
In another aspect of the invention, an apparatus is provided to implement the method according to the present invention.
In another aspect of the invention, the method comprises steps of obtaining the digital image, scanning the digital image on an image element by image element basis—the scanning being conducted in a background mode if an adjacent image element previously scanned is a background element and in a non-background mode if the adjacent image element
Au Amelia M.
Fay Sharpe Fagan Minnich & McKee LLP
Le Brian Q
Xerox Corporation
LandOfFree
Method and apparatus for implementing a streaming... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing a streaming..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a streaming... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3180846