John Petry
Color Vision ____________ This is a very good background paper explaining the mechanics of color representation and analysis. Starting with the imaging properties of CCD sensors, it then describes the 3-dimensional color space and various representations of it, such as hue, saturation and intensity; Red, Green, Blue; or variations on RGB which more closely correspond to human perception, such as the Munsell system. It describes the usual method of comparing colors by measuring the Euclidean distance between two points in 3-D color space, and explains that this approach has problems due to singularities in the color space and uneven color distributions in real images. [This comparison issue is addressed by the other two papers.] The paper then lists the most common ways of segmenting images by color: spectral signature analysis (if a priori color information exists); clustering and variations on it when advance knowledge on color distributions does not exists; and color edge detection. Color Indexing by Swain and Ballard ______________ This paper suggests that color is a reasonable method for identifying objects of known location, and locating objects of known appearance. According to the others, color has previously been discounted in these tasks relative to geometric approaches. Swain and Ballard suggest that it is practical to use color for high-speed image location and identification. For identification, they propose a method called Histogram Intersection, which matches 3D color image histograms (eg. Red-Green-Blue). Histogram Intersection is a bin-wise comparison between two histograms which returns a relative match score based on the portion of pixels which are found in the same color bin of each image. While a complete comparison is dependent on matching N^^3 bins, a much faster match can be computed by only comparing the most densely populated bins of the image and model histograms. This Incremental Intersection technique takes advantage of the fact that many bins will be unpopulated or very sparsely populated, while most of the unique aspects of an image will be contained in the few (<10 out of 256) bins with the highest populations. Incremental Intersection thus has the properties of producing a match score almost identical to that from a full matching of all bins, while needed to compare only a few of the bins, and being easily interruptable. The authors claim that the matching technique itself is essentially independent of background, viewpoint, moderate occlusion, and limited resolution differences. They also assert that it works under varying lighting conditions given suitable controls. I am not sure about their background claim; note that all samples in their database were colorful objects on a black background, which makes segmentation inherent in the measurement. This is especially important if the object is not scale-invariant, because a scaling operation must be performed, and this is much less feasible if the object cannot be segmented from its background (unless the scale factor itself is known a priori). Nonetheless, the algorithm appears to provide a good method for distinguishing objects by color in a moderately controlled database, assuming that images can be histogrammed in advance, so that only comparisons (or better yet, Histogram Intersections) are computed at runtime. Their method of object location does relative matching within regions of approximately the same area as the model, and builds up a match image on which peak detection can be done to find the likeliest location of an object. This approach has essentially the same properties as Histogram Intersection. [I have some questions regarding the underlying approach, but these will probably come out in class.] Efficient Color Histogram Indexing for Quadratic Form Distance Functions ________________________________________________________________________ by Hafner, Sawhney, Equitz, Flickner, and Niblack. N-dimensional Histograms (eg. 64 or 256 bins), such as those used by Swain and Ballard above, can be compactly represented by a 3-dimensional "average color" vector. Such vectors have several useful properties: They can be precomputed for image databases; The databases can be arranged for easy indexing according to the vectors; It is possible to simulate full N-dimensional histogram comparisons between images and a model with comparisons between their average color vectors. While the comparison between average color vectors is not as accurate as that between full N-dimensional histograms, it is *much* faster, running in constant time per image, rather than O(N) or O(N^^2). In addition, a search for all images whose color vector is within an arbitrary difference from the model image will produce a set of images which is guaranteed to include all images whose N-dimensional histograms differ from the model by less than the arbitrary difference. This means that not only does this approach act as a good preprocessing step, by returning images with properties similar to those desired in the final processing step, it guarantees that all "matching" final images that would be found by an exhaustive search will be returned. "False negatives" are thereby eliminated, though "false positives" must still be winnowed by the final computation-intensive step. As an interesting side effect, while this approach was implemented for the purpose of high-speed color comparisons, the underlying math extends directly to other multidimensional comparisons with similar attributes.
Shren Daftary
Synopsis for Color Indexing by Swain and Ballard This paper discusses methods to cope with the need of real time analysis of objects for robots. The two likely methods that a robot will deal with its surroundings are to find a single object among many objects, or to determine the object at a particular location. The use of color identifiers and histograms has been neglected, in spite of its utility. This is because color is not related to the class of the object, as opposed to shape or texture identifiers. According to the paper, however when many objects need to be compared the latter identifiers involve complex routines that are computationally expensive, while color comparisons can be analyzed by simply comparing histograms - and then performing more extensive tests on the smaller set of objects. Color histograms are not responsive to changes in orientation, or distance of object, so they will narrow down the set of potential matches. The comparison of histograms is performed by first reducing the amount of colors that need to be stored for each object to about 200 with the use of a color-constancy algorithm. To determine the intersection of two histograms requires at most small variations in lighting, resolution, and viewpoints and minimal occlusion, and background noise. One technique which can deal with of the above except for lighting variations is histogram intersection. This system simply adds all of the matches in the histogram scheme, and will work well with a color constancy scheme that gets rid of variations in lighting. Without color constancy, The accuracy of Histogram Intersection falls dramatically when lighting effects are not compensated for. The calculations involved for this method are O(n). A separate algorithm Incremental Intersection is suited for use in real time situations where the computer has time constraints. This technique is computationally quicker and provides better matching then Histogram Intersection. A final technique presented in the paper is Histogram Backprojection. This technique involves the creation of a ratio histogram that is min (Mi/Ii,1) where M and I are color histograms. This histogram R is backprojected onto the image. After backprojecting R "the new image is convolved by a mask, which are about the same area as the object, and the peak is the location of the object" - ie a correlation function. This technique can be performed on reduced resolution images. Some areas that remain to be solved are lighting issues, Synopsis of Efficient Color Histogram Indexing for Quadratic Form Distance Functions by Hafner, Sawhney et al. This paper presents the QBIC technique of image retrieval. This technique works by retrieving images that are similar to each other based on shape, color, texture, and possibly user sketches. Part of this technique is the analysis of histogram distance - an O(N^2) operation dependent on the number of bins/image or at best O(N). Since this is computationally expensive the authors suggest the use of a low-dimensional computation to reduce the amount of intensive calculations that need to be performed to determine the best matches. The metric that is used to determine the distance between two histograms in this techniques is different than the standard Euclidian distance, since it accounts for perceptual similarities between two different colors, for instance yellow and orange. In the simplest case this technique calculates a simple distane which provides a quick calculation at the cost of higher false hits. This is accomplished by simply making a three dimensional matrix C that represents the magnitude of an image in three different directions. By storing this matrix, the average color distance can be determined by performing only 3 multiplications and subtractions, and two additions as opposed to N operations. After this operation is performed over the entire set, more complex comparisons can be performed to get closer matches. The use of the C matrix is generalizable to the use of any k dimensional index or feature to reduce the search time for the larger database. Color Vision by Shafer and Kanade This paper begins by discussing the importance of color in our identification of objects. They then define methods of quantifying color by the creation of color space with three axes. For computers to filter out colors properly then 3 types of filters are needed. The normal method to distinguish different colors is by comparing Red, Green, and Blue intensities. Other methods are available to describe a color such as saturation, hue, intensity method. (HSI) Both of these metrics provide Euclidean distances that do not correspond well with human perception. A few techniques have been developed to provide for better correlation between perception and distance. One such techniques, the YIQ, is the linear transformation of the RGB, which is an adjustment for human perception. The paper then introduces histograms, and the concept of region splitting, into areas or a single color, and region growing, into areas of similar colors. Summary of papers These papers provided an introduction into computer vision, and some methods to compare and find similar objects or images. They discussed techniques to quantify images, and to use the quantifications to find similar images through histogram analysis or by use of lower dimensional searches. Finally the papers presented additional techniques to increase computational efficiency to make it more practical to calculate image similarities in real time.
Paul Dell
Synopsis for Color Indexing by Swain and Ballard This paper discusses methods to cope with the need of real time analysis of objects for robots. The two likely methods that a robot will deal with its surroundings are to find a single object among many objects, or to determine the object at a particular location. The use of color identifiers and histograms has been neglected, in spite of its utility. This is because color is not related to the class of the object, as opposed to shape or texture identifiers. According to the paper, however when many objects need to be compared the latter identifiers involve complex routines that are computationally expensive, while color comparisons can be analyzed by simply comparing histograms - and then performing more extensive tests on the smaller set of objects. Color histograms are not responsive to changes in orientation, or distance of object, so they will narrow down the set of potential matches. The comparison of histograms is performed by first reducing the amount of colors that need to be stored for each object to about 200 with the use of a color-constancy algorithm. To determine the intersection of two histograms requires at most small variations in lighting, resolution, and viewpoints and minimal occlusion, and background noise. One technique which can deal with of the above except for lighting variations is histogram intersection. This system simply adds all of the matches in the histogram scheme, and will work well with a color constancy scheme that gets rid of variations in lighting. Without color constancy, The accuracy of Histogram Intersection falls dramatically when lighting effects are not compensated for. The calculations involved for this method are O(n). A separate algorithm Incremental Intersection is suited for use in real time situations where the computer has time constraints. This technique is computationally quicker and provides better matching then Histogram Intersection. A final technique presented in the paper is Histogram Backprojection. This technique involves the creation of a ratio histogram that is min (Mi/Ii,1) where M and I are color histograms. This histogram R is backprojected onto the image. After backprojecting R "the new image is convolved by a mask, which are about the same area as the object, and the peak is the location of the object" - ie a correlation function. This technique can be performed on reduced resolution images. Some areas that remain to be solved are lighting issues, Synopsis of Efficient Color Histogram Indexing for Quadratic Form Distance Functions by Hafner, Sawhney et al. This paper presents the QBIC technique of image retrieval. This technique works by retrieving images that are similar to each other based on shape, color, texture, and possibly user sketches. Part of this technique is the analysis of histogram distance - an O(N^2) operation dependent on the number of bins/image or at best O(N). Since this is computationally expensive the authors suggest the use of a low-dimensional computation to reduce the amount of intensive calculations that need to be performed to determine the best matches. The metric that is used to determine the distance between two histograms in this techniques is different than the standard Euclidian distance, since it accounts for perceptual similarities between two different colors, for instance yellow and orange. In the simplest case this technique calculates a simple distane which provides a quick calculation at the cost of higher false hits. This is accomplished by simply making a three dimensional matrix C that represents the magnitude of an image in three different directions. By storing this matrix, the average color distance can be determined by performing only 3 multiplications and subtractions, and two additions as opposed to N operations. After this operation is performed over the entire set, more complex comparisons can be performed to get closer matches. The use of the C matrix is generalizable to the use of any k dimensional index or feature to reduce the search time for the larger database. Color Vision by Shafer and Kanade This paper begins by discussing the importance of color in our identification of objects. They then define methods of quantifying color by the creation of color space with three axes. For computers to filter out colors properly then 3 types of filters are needed. The normal method to distinguish different colors is by comparing Red, Green, and Blue intensities. Other methods are available to describe a color such as saturation, hue, intensity method. (HSI) Both of these metrics provide Euclidean distances that do not correspond well with human perception. A few techniques have been developed to provide for better correlation between perception and distance. One such techniques, the YIQ, is the linear transformation of the RGB, which is an adjustment for human perception. The paper then introduces histograms, and the concept of region splitting, into areas or a single color, and region growing, into areas of similar colors. Summary of papers These papers provided an introduction into computer vision, and some methods to compare and find similar objects or images. They discussed techniques to quantify images, and to use the quantifications to find similar images through histogram analysis or by use of lower dimensional searches. Finally the papers presented additional techniques to increase computational efficiency to make it more practical to calculate image similarities in real time.
John Isidoro
The three articles we read were about color indexing and some of the techniques used to search an image database by color histograms. The Swain and Ballard paper served as an introduction to these topics describing both color histogram intersection and incremental intersection. These techniques serve as ways to enumerate the similarity between two images. Also explained was the concept of histogram back projection which is a form of image reconstruction when the model color histogram is known. The color vision paper explianed the various color spaces used in computer graphics and their various advantages and disadvantages. Also discussed were some of the benefits of using color as a statistical property, and how this concept can be utilized to split an image up into regions of resonably constant color. The third paper "Efficient Color ..." discussed a more efficient way to perform color histogrram intersection by storing something called a k-dimensional index which can be used as a smaller index for an image. Overall I enjoyed the Swain and Ballard paper most of all, it was a great introduction to computer vision using color properties. It was smooth reading because it relied more on concepts and intuition rather than just heavy math. The color vision paper was useful in bringing up the considerations of using various color spaces to build color histograms. The third paper seemed to be based on performance optimizations and really didn't relate to any work I have done yet..
Lars Liden
"Color Vision" Shafer & Kanade This article introduced some of the issues involved in the representation of color information as a color space, and with transformations such as the CIE-XYZ system and the Munsell color order system. Several methods for image segmentation using color were discussed. One of the most common is `spectral signature analysis' in which prior knowledge of an objects characteristic color is used to classify and segment an object. Several clustering methods were also mentioned using techniques such as `relaxation' to prevent clusters from overlapping in color space, `region splitting' which breaks the image into successively smaller pieces and `region growing' in which smaller regions are successively merged to form larger regions based on their similarity. The use of color for edge detection was also introduced. Finally, the use of heuristics for such jobs as shadow detection was briefly discussed. It occurred to me reading this article that there may be many good alternatives to the clustering techniques discussed in the article. In particular, it seems that this problem is particularly suited to various neural network techniques. Unsupervised learning algorithms would probably be the most appropriate, but perhaps even a supervised model learning from pre-segmented images would work. "Color Indexing" Swain & Ballard This article discusses the merits of using color to determine the identity of object with a known location and to determine the location of known objects. A color histogram is used to compare images to model histograms. This method has the advantage that it is relatively invariant to translation, rotation and performs well even at lower resolution and with occlusion. A method called incremental intersection is presented which improves the efficiency of the algorithm for on-line searching. `Histogram Backprojection' is used to find a known object in an image by searching for matching colors. The use of other similar techniques for features such as texture is suggested. In relation to the other (later) articles, the algorithms presented in this particular one seemed to be throwing away a lot of information about the structure and segmentation of objects. Although color does seem to posses an abundance of information about an image, it seems that segmentation of the image into objects/background is still a key component to object recognition and localization. "Efficient Color Histogram Indexing for Quadratic Form and Distance Functions" Hafner, Sawhney, Equitz, Flicknet & Niblack This article also examined how one could create an efficient indexing and retrieval system for images from a large database using color information. Instead of a simple histogram comparison, a filtering method was presented. Some of the key ideas were the use of a weighted similarity matrix to encode the perceptual similarity between colors, and the use of average color distance. As the previous article, this one also seems to discount the utility of attempting to segment objects as part of the classification/search process.
Stan Sclaroff
Created: Sept 18, 1995
Last Modified: