Image analysis – Histogram processing – With pattern recognition or classification
Reexamination Certificate
1999-06-18
2003-03-11
Tran, Phuoc (Department: 2621)
Image analysis
Histogram processing
With pattern recognition or classification
C382S165000, C382S305000
Reexamination Certificate
active
06532301
ABSTRACT:
BACKGROUND
1. Technical Field
The invention is related to a computer-implemented object recognition system and process, and more particularly, to such a system and process employing co-occurrence histograms (CH) for finding an object in a search image.
2. Background Art
Object recognition in images is typically based on a model of the object at some level of abstraction. This model is matched to an input image which has been abstracted to the same level as the model. At the lowest level of abstraction (no abstraction at all), an object can be modeled as a whole image and compared, pixel by pixel, against a raw input image. However, more often unimportant details are abstracted away, such as by using sub-templates (ignoring background and image position), normalized correlation (ignoring illumination brightness), or edge features (ignoring low spatial frequencies). The abstraction itself is embodied in both the representation of the object and in the way it is matched to the abstracted image. For instance, Huttenlocher et al. [1] represent objects as simple edge points and then match with the Hausdorff distance. While the edge points form a completely rigid representation, the matching allows the points to move nonrigidly.
One interesting dimension of the aforementioned abstraction is rigidity. Near one end of this dimension are the several object recognition algorithms that abstract objects into a rigid or semi-rigid geometric juxtaposition of image features. These include Hausdorff distance [1], geometric hashing [2], active blobs [3], and eigenimages [4, 5]. In contrast, some histogram-based approaches abstract away (nearly) all geometric relationships between pixels. In pure histogram matching, e.g. Swain & Ballard [6], there is no preservation of geometry, just an accounting of the number of pixels of given colors. The technique of Funt & Finlayson [7] uses a histogram of the ratios of neighboring pixels, which introduces a slight amount of geometry into the representation.
Abstracting away rigidity is attractive, because it allows the algorithm to work on non-rigid objects and because it reduces the number of model images necessary to account for appearance changes due to scaling and viewpoint change. One can start with a geometrically rigid approach and abstract away some rigidity by using geometric invariants [8], loosening the matching criteria [1], or explicitly introducing flexibility into the model [3]. On the other hand, one can start with a method like Swain & Ballard's color indexing [6], which ignores all geometry, and add some geometric constraints. For example, some histogram-based approaches, most of which are used to find images in a database rather than to find an object in an image, have employed attempts to add spatial information to a regular color histogram. Included among these are Huang et al. [9] where a “color correlogram” is used to search a database for similar images, or Pass and Zabih [10] where “color coherence vectors” are employed that represent which image colors are part of relatively large regions of similar color.
The dilemma comes in deciding how much to abstract away. The goal is to ignore just enough details of the object's appearance to match all anticipated images of the object, but not so many details that the algorithm generates false matches. The present invention addresses this issue.
It is noted that in the preceding paragraphs, as well as in the remainder of this specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, “reference [1]” or simply “[1]”. Multiple references will be identified by a pair of brackets containing more than one designator, for example, [4, 5]. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.
SUMMARY
This invention is directed toward an object recognition system and process that identifies the location of a modeled object in an image. Essentially, this involves first creating model images of the object whose location is to be identified in the search image. As the object may be depicted in the search image in any orientation, it is preferred that a number of model images be captured, of which each shows the object from a different viewpoint. Ideally, these model images would be taken from viewpoints spaced at roughly equal angles from each other around the object. In addition, multiple images could be taken at each angular viewpoint where each is captured at a different distance away from the object being modeled. This latter method would better model an object whose distance from the camera capturing the search image is unknown. One way of determining how far apart each angular viewpoint should be to ensure a good degree of match between the object in the search image and one of the model images is to require a high degree of matching between each model image. Similarly, it is desirable that a good degree of match exist between adjacent model images taken at the same angular viewpoint, but at different distances from the object, for the same reasons.
Each model image is processed to compute a color co-occurrence histogram (CH). This unique histogram keeps track of the number of pairs of certain “colored” pixels that occur at particular separation distances in the model image. In this way, geometric information is added to the histogram to make it more selective of the object in the search image, than would a simple color histogram. In generating the CH there are two parameters that are selected ahead of time. These parameters are the color ranges and the distance ranges. Choosing the color ranges involves dividing the total possible color values associated with the pixels of the model images into a series of preferably equal sized color ranges. Choosing the distance ranges involves selecting a set of distance ranges, for example (1-2 pixels), (2-3 pixels), (3-4 pixels) . . . , up to a prescribed maximum separation distance between pairs of pixels that will be checked. The size of each color and distance range (& so ultimately the total number of different ranges) is preferably selected to optimize the search process as will be discussed later. Essentially, these ranges should be made small enough to ensure a high selectivity in finding the object in the search image and to minimize false matches. On the other hand, the ranges should be large enough to reduce the amount of processing and to allow enough flexibility in the match that small changes in the shape of the object in the search image (e.g. due to flexure, a slight change in viewpoint, or a different zoom level or scale) do not prevent an object from being recognized.
Once the color and distance ranges are established, each pixel in the model image is quantized in regards to its color by associating it to the color range which includes the actual color value of the pixel. The model images are quantized in regards to distance by associating each possible unique, non-ordered, pair of pixels in a model image to one of the distance ranges based on the actual distance separating the pixel pair. The CH is then generated by establishing a count of the number of pixel pairs in a model image which exhibit the same “mix” of color ranges and the same distance range.
The search image (i.e., the image to be searched for the modeled object) is first cordoned into a series of preferably equal sized sub-images or search windows. These search windows preferably overlap both side-to-side and up-and-down. In the tested embodiment of the present invention, the overlap was set to one-half the width and height of the search window. The size of the search window is preferably as large as possible so as to minimize the search process. However, it is also desired that the search wind
Chang Peng
Krumm John
Lyon Richard T.
Lyon & Harr LLP
Microsoft Corporation
Sherali Ishrat
Tran Phuoc
LandOfFree
Object recognition with occurrence histograms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Object recognition with occurrence histograms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object recognition with occurrence histograms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065600