System and method for color characterization using fuzzy pixel classification with application in color matching and color match location

• US 20040228526A9
• Filed: 12/13/2000
• Published: 11/18/2004
• Est. Priority Date: 08/17/1999
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Lin, Siming, Schmidt, Darren
• Granted Patent: US 7,046,842 B2
• Time in Patent Office: Days
• US Class Current: 382/165
• CPC Class Codes: G06F 18/256 of results relating to different input data, e.g. multimodal recognition
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 20/66 Trinkets, e.g. shirt buttons or jewellery items recognising microscopic objects G06V20/69

Abstract

A system and method for measuring the similarity of multiple-color images and for locating regions of a target image having color information that matches, at least to a degree, the color information of a template image. A color characterization method operates to characterize the colors of an image and to measure the similarity between multiple-color images. For each image pixel, the method determines a color category or bin for the respective pixel based on HSI values of the respective pixel, wherein the color category is one of a plurality of possible color categories in HSI color space. In various embodiments, the weight of the pixel may be fractionally distributed across a plurality of color categories, e.g., as determined by applying fuzzy pixel classification with a fuzzy membership function. The percentage of pixels assigned to each category is then determined. The percentage of pixels in each color category is then used as a color feature vector to represent the color information of the color image. A quantitative measurement of the color similarity between color images is then computed based on the distance between their color feature vectors. Once the color information of a template image has been characterized, a target image may be searched in order to locate regions within the target image having matching color information. In one embodiment, a coarse-to-fine heuristic may be utilized, in which multiple search stages of decreasing granularity are performed. A first-stage search may operate to identify a list of candidate match regions based on the city-block distance of the color feature vector computed using a sub-sampling scheme. These candidate match regions may then be examined in further detail in order to determine final matches.

Claims

1. A computer-implemented method for characterizing colors of an image, wherein the image comprises a plurality of pixels, the method comprising:

for each respective pixel of at least a subset of pixels of the image, assigning values to one or more color categories based on color information of the pixel;

wherein, for each of one or more first pixels, said assigning comprises assigning values to a plurality of the color categories based on color information of the pixel; and

determining information regarding the total values of pixels assigned to each of the color categories, wherein said information characterizes colors of the image;

2. The method of claim 1,

wherein, for each of the one or more first pixels, said assigning comprises assigning a percentage of the pixel to each of the plurality of color categories.

3. The method of claim 2,

wherein, for each of the one or more first pixels, the sum of the percentages assigned to each of the plurality of color categories is 100 percent.

4. The method of claim 1,

wherein each of the one or more color categories corresponds to a portion of a color space.

5. The method of claim 4,

wherein, for each respective pixel of the at least a subset of pixels, said assigning values to the one or more color categories based on color information of the pixel comprises:

determining a location of the pixel within the color space;

applying a function based on the location of the pixel within the color space to determine the values assigned to the one or more color categories.

6. The method of claim 5,

wherein said determining the location of the pixel within the color space comprises examining color information of the pixel.

7. The method of claim 6,

wherein the color space is the Hue, Saturation, Intensity (HSI) color space;

wherein said examining color information of the pixel comprises examining HSI information of the pixel.

8. The method of claim 5,

wherein the function is a fuzzy membership function.

9. The method of claim 8,

wherein the fuzzy membership function is one of:

a triangle fuzzy membership function;

a trapezoidal fuzzy membership function; and

a step fuzzy membership function.

10. The method of claim 1, further comprising:

selecting the subset of pixels of the image, wherein the subset of pixels characterize the image, wherein the subset is selected using one or more of a random selection, a grid-based selection, or a Low Discrepancy sequence selection.

11. The method of claim 1,

wherein said assigning values to one or more color categories based on color information of each pixel comprises creating a data structure having values representing the total values of pixels assigned to each of the color categories;

wherein said determining information regarding the total values of pixels assigned to each of the color categories comprises determining the values of the data structure.

12. A computer-implemented method for characterizing colors of an image, wherein the image comprises a plurality of pixels, the method comprising:

for each respective pixel of at least a subset of pixels of the image, determining contributions of the pixel to one or more color categories;

wherein, for each of one or more first pixels, said determining comprises determining contributions of the pixel to a plurality of the color categories; and

determining information regarding the total contributions of pixels to each of the color categories, wherein said information characterizes colors of the image.

13. The method of claim 12,

wherein, for each of the one or more first pixels, said determining comprises determining a percentage of the pixel that is contributed to each of the plurality of color categories.

14. The method of claim 13,

wherein, for each of the one or more first pixels, the sum of the percentages contributed to each of the plurality of color categories is 100 percent.

15. The method of claim 12,

wherein each of the one or more color categories corresponds to a portion of a color space.

16. The method of claim 15,

wherein, for each respective pixel of the at least a subset of pixels, said determining the contributions of the pixel to the one or more color categories comprises:

determining a location of the pixel within the color space;

applying a function based on the location of the pixel within the color space to determine the contributions of the pixel to the one or more color categories.

17. The method of claim 16,

wherein said determining the location of the pixel within the color space comprises examining color information of the pixel.

18. The method of claim 17,

wherein the color space is the Hue, Saturation, Intensity (HSI) color space;

wherein said examining color information of the pixel comprises examining HSI information of the pixel.

19. The method of claim 16,

wherein the function is a fuzzy membership function.

20. The method of claim 19,

wherein the fuzzy membership function is one of:

a triangle fuzzy membership function;

a trapezoidal fuzzy membership function; and

a step fuzzy membership function.

21. The method of claim 12, further comprising:

selecting the subset of pixels of the image, wherein the subset of pixels characterize the image, wherein the subset is selected using one or more of a random selection, a grid-based selection, or a Low Discrepancy sequence selection.

22. The method of claim 12,

wherein said determining contributions of each pixel to one or more color categories comprises creating a data structure having values representing the total contributions of pixels to each of the color categories;

wherein said determining information regarding the total contributions of pixels to each of the color categories comprises determining the values of the data structure.

23. A computer-implemented method for characterizing the color information of an image, wherein the image comprises a plurality of pixels, wherein a color space representing possible colors of the pixels is divided into a plurality of bins, the method comprising:

for each of at least a subset of pixels of the image;

examining color information of the pixel to determine a bin corresponding to the color information of the pixel;

applying a function based on a location of the pixel within the bin to determine a contribution of the pixel to one or more neighboring bins;

assigning values to the bin and the one or more neighboring bins based on the determined contributions of the pixel to the one or more neighboring bins;

wherein the total assigned values across the bins of the color space characterize the color information of the image.

24. The method of claim 23,

wherein the color space is the Hue, Saturation, Intensity (HSI) color space;

wherein said examining color information of the pixel comprises examining HSI color information of the pixel.

25. The method of claim 23,

wherein the function is a fuzzy membership function.

26. The method of claim 23,

wherein a first pixel falls within a first bin;

wherein the location of the first pixel within the first bin is a first distance away from a second bin, with respect to color space difference, wherein the second bin neighbors the first bin, with respect to the portion of color space to which the first and second bins correspond;

wherein a second pixel falls within the first bin;

wherein the location of the second pixel within the first bin is a second distance away from the second bin, with respect to color space difference;

wherein the second distance is less than the first distance;

wherein applying the function based on the location of the first pixel within the first bin results in determining a contribution of the first pixel to the second bin;

wherein applying the function based on the location of the second pixel within the first bin results in determining a contribution of the second pixel to the second bin;

wherein the contribution of the second pixel to the second bin is greater than the contribution of the first pixel to the second bin.

27. A computer-implemented method for determining a similarity of colors between a template image and a target image, wherein the template image and the target image each comprise a plurality of pixels, the method comprising:

determining color information of the template image, wherein said color information comprises information regarding assigned values of at least a subset of template image pixels to each of a plurality of color categories;

determining color information of the target image, wherein said color information comprises information regarding assigned values of at least a subset of target image pixels to each of the plurality of color categories;

determining a similarity of colors between the template image and the target image, based on the color information of the template image and the color information of the target image;

wherein, for one or more template image pixels or one or more target image pixels, a value is assigned to more than one color category.

28. The method of claim 27,

wherein for each of the one or more template image pixels or one or more target image pixels for which a value is assigned to more than one color category, a percentage of the pixel is assigned to each of the more than one color categories, wherein the sum of the percentages is 100 percent.

29. The method of claim 27,

wherein each of the color categories corresponds to a portion of a color space.

30. The method of claim 29, further comprising:

for each of the at least a subset of template image pixels, determining a location of the pixel within the color space, based on color information of the pixel; and

for each of the at least a subset of target image pixels, determining a location of the pixel within the color space, based on color information of the pixel;

wherein said determining color information of the template image comprises;

for each of the at least a subset of template image pixels, assigning values to one or more color categories based on the location of the pixel within the color space;

wherein said determining color information of the target image comprises;

for each of the at least a subset of target image pixels, assigning values to one or more color categories based on the location of the pixel within the color space.

31. A computer-implemented method for characterizing colors in an image, wherein the image comprises a plurality of pixels, the method comprising:

for each respective pixel of at least a subset of the pixels, assigning the respective pixel to one or more color categories from a plurality of possible color categories, based on color information of the respective pixel;

determining information regarding the distribution of pixels across each of the color categories;

determining information regarding one or more dominant color categories, based on the information regarding the distribution of pixels across each of the color categories, wherein the one or more dominant color categories are assigned a relatively larger proportion of pixels, with respect to other color categories;

wherein the information regarding the distribution of pixels across each of the color categories and the information regarding the one or more dominant color categories characterizes colors in the image.

32. A system for characterizing colors of an image, wherein the image comprises a plurality of pixels, the system comprising:

a processor;

a memory medium coupled to the processor, wherein the memory medium stores color characterization software;

wherein the processor is operable to execute the color characterization software to;

for each respective pixel of at least a subset of pixels of the image, assign values to one or more color categories based on color information of the pixel;

wherein, for each of one or more first pixels, said assigning comprises assigning values to a plurality of the color categories based on color information of the pixel;

wherein the processor is operable to determine information regarding the total values of pixels assigned to each of the color categories, wherein said information characterizes colors of the image.

33. The system of claim 32,

wherein, for each of the one or more first pixels, said assigning comprises assigning a percentage of the pixel to each of the plurality of color categories.

34. The system of claim 32,

wherein each of the one or more color categories corresponds to a portion of a color space.

35. The system of claim 34,

wherein, for each respective pixel of the at least a subset of pixels, in assigning values to the one or more color categories based on color information of the pixel, the processor is operable to:

determine a location of the pixel within the color space;

apply a function based on the location of the pixel within the color space to determine the values assigned to the one or more color categories.

36. The system of claim 35,

wherein the function is a fuzzy membership function.

37. The system of claim 32, wherein the processor is further operable to:

select the subset of pixels of the image, wherein the subset of pixels characterize the image, wherein the processor is operable to select the subset using one or more of a random selection, a grid-based selection, or a Low Discrepancy sequence selection.

38. The system of claim 32,

wherein, in performing said assigning values to one or more color categories based on color information of each pixel, the processor is operable to create a data structure having values representing the total values of pixels assigned to each of the color categories;

wherein said determining information regarding the total values of pixels assigned to each of the color categories comprises determining the values of the data structure.

39. A memory medium comprising program instructions operable to:

for each respective pixel of at least a subset of pixels of an image, assign values to one or more color categories based on color information of the pixel;

wherein, for each of one or more first pixels, said assigning comprises assigning values to a plurality of the color categories based on color information of the pixel; and

determine information regarding the total values of pixels assigned to each of the color categories, wherein said information characterizes colors of the image.

40. The memory medium of claim 39,

wherein, for each of the one or more first pixels, said assigning comprises assigning a percentage of the pixel to each of the plurality of color categories.

41. The memory medium of claim 39,

wherein each of the one or more color categories corresponds to a portion of a color space.

42. The memory medium of claim 41,

wherein, for each respective pixel of the at least a subset of pixels, said assigning values to the one or more color categories based on color information of the pixel comprises:

determining a location of the pixel within the color space;

applying a function based on the location of the pixel within the color space to determine the values assigned to the one or more color categories.

43. The memory medium of claim 42,

wherein the function is a fuzzy membership function.

44. The memory medium of claim 39, further comprising program instructions operable to:

select the subset of pixels of the image, wherein the subset of pixels characterize the image, wherein the subset is selected using one or more of a random selection, a grid-based selection, or a Low Discrepancy sequence selection.

45. The memory medium of claim 39,

wherein said assigning values to one or more color categories based on color information of each pixel comprises creating a data structure having values representing the total values of pixels assigned to each of the color categories;

wherein said determining information regarding the total values of pixels assigned to each of the color categories comprises determining the values of the data structure.