Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
2000-05-22
2003-01-28
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S286000, C382S291000, C382S101000
Reexamination Certificate
active
06512849
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to methods and apparatus for image processing, and specifically to fast methods for finding an object in an image.
BACKGROUND OF THE INVENTION
Many image processing applications involve finding whether a certain object or objects are present in a given image and, if so, at what location in the image. A dictionary is given of the objects to be found. The appearance of the objects in the image, however, may differ from their appearance in the dictionary. Reasons for variation in the appearance of the objects include rotation, scaling, noise, nonlinear distortions, contrast variations within the object and between the object and background, and slight topological variations. Practical image processing methods must be capable of finding the specified objects rapidly, even in the presence of such variations, over large images.
Most methods known in the art for finding objects in an image involve either pattern matching or topological search techniques. Typically, they require that the image first be preprocessed, or filtered, to emphasize desired features, such as gradients or edges. Pattern matching is sensitive to the types of variations mentioned above, particularly nonlinear variations. Topological search methods involve operations such as dilation and finding contours and skeletons, which are too time-consuming and computationally inefficient for rapid processing of large images.
Binarization of the image before searching for objects can decrease computation time, particularly if the image is also decimated. Methods based on binarization, however, are particularly sensitive to contrast variations. Depending on the choice of binarization method and threshold, important features of objects in the image or distinctions between the objects and background may vanish when the image is binarized. Due to brightness and contrast variations within the image, different thresholds are frequently required in different parts of the image.
One particularly challenging object-finding application is automated sorting of postal parcels. The parcel sorting equipment must be capable of recognizing and locating various marks and stickers that are pasted onto the parcels. Typically, only very limited processing time is allocated to scan a large overall image area. Because the images are captured by a camera above the parcel conveyer, there may be large variations in scale due to the different heights of the parcels. Physical distortions of the parcels themselves cause nonlinear distortions of the stickers that are pasted onto them. Furthermore, different editions of the same sticker may have different gray-scale contrasts, stroke widths, fonts and feature topologies.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide methods and apparatus for rapidly finding an object in an image.
It is a further object of some aspects of the present invention to provide methods for finding an object in a image that operate rapidly even on very large images.
It is yet a further object of some aspects of the present invention to provide methods for finding an object in an image that are robust and accurate even in the presence of variations in the appearance of the object.
It is still a further object of some aspects of the present invention to provide a method for finding objects in an image that is suited for use in automated parcel sorting applications.
In preferred embodiments of the present invention, an object of interest to be found in an image is defined in terms of the lines that make up the object, and in particular in terms of the stroke width of the lines. (In the context of the present patent application and in the claims, the term “line” is to be understood as meaning any long, thin feature, whether straight or curved.) When these lines appear in the image, they are expected to have a width within a predefined range. This range contains the known stroke width of the lines that belong to the object, but is expanded to account for any deviations that may occur in the width of the actual lines in the image due to distortion, scaling, contrast variations or other reasons. In order to find the object, the image is rapidly searched for all features having a width within this range. This method generally allows a small set of regions of interest to be located rapidly based on scanning only a small subset of the pixels in the image, with a high probability that the object of interest will be found in one of these regions.
In some preferred embodiments of the present invention, a gray-scale image is searched for the object of interest in a series of successive stages. Each stage narrows the field of search relative to the previous one, while closing in on the specific object being sought. In the first stage, the regions of interest are located by finding clusters of pixels that appear to reside on features having widths within the predefined range. Next, the regions of interest are scanned to find contrast peaks, i.e., sharp variations in gray-scale occurring along selected scan lines taken through the regions. When the magnitude of such a peak is above a given threshold, and its width is within the range, it is a candidate to be a part of one of the lines that make up the object of interest. The candidate peaks are morphologically expanded in a region-growing procedure to create “stains,” i.e., connected groups of pixels having approximately the same gray-scale values. Then, a high-level image recognition procedure, as is known in the art, is applied to each of the stains in order to determine which stain or stains correspond to the object of interest. This final stage is the only one that is dependent on the object itself, and it is performed only on the very small subset of all of the pixels that are contained in the stains.
The methods described herein are particularly suited for identifying labels, symbols and stickers on postal parcels, for use in rapid scanning and sorting applications. The principles of the present invention may also be applied, however, in a wide range of other contexts in which objects of interest must be located rapidly in a large image, while avoiding identification errors due to variations and distortions in the image.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for finding a predefined object in an image, including:
selecting a line belonging to the object, the line having a known stroke width;
defining a maximum width and a minimum width that together define a range of widths therebetween that contains the stroke width;
finding a feature in the image having a feature width within the range; and
processing the feature to determine whether it is a part of the object.
Preferably, defining the maximum and minimum widths includes determining variations that may occur in the width of the line in the object when it appears in the image.
In a preferred embodiment, finding the feature in the image includes:
finding a first locus of pixels in the image belonging to one or more elements of the image having a width less than the maximum width;
finding a second locus of pixels in the image belonging to one or more elements of the image having a width less than the minimum width; and
taking a disjunction of the first and second loci.
Preferably, finding the first locus includes finding a pixel having a gray-scale value that differs by at least a predetermined contrast threshold from the gray-scale values of other pixels at a distance therefrom that is equal to the maximum width. Alternatively or additionally, finding the feature in the image includes sub-sampling the image before finding the loci, so that only a subset of all of the pixels in the image are considered for inclusion in the loci. Further alternatively or additionally, finding the feature in the image includes identifying a cluster of the pixels in the disjunction of the first and second loci as a region of interest in the image, which region is a candidate to contain the object.
I
Barkan Ella
Navon Yaakov
Yair Eyal
LandOfFree
Finding objects in an image does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Finding objects in an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding objects in an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3012342