Coded objects and methods for detecting such coded objects

• US 6,108,612 A
• Filed: 06/23/1998
• Issued: 08/22/2000
• Est. Priority Date: 06/23/1998
• Status: Expired due to Term

• Current Assignee: Vulcan Patents LLC
• Original Assignee: Interval Research Corporation
• Inventors: Covell, Michele M., Piernot, Philippe P., Slaney, Malcolm G., Saunders, Steven E., Vescovi, Marcos R.
• Primary Examiner(s): SHAH, KAMINI S
• Application Number:
  US09/103,265
• Time in Patent Office: 791 Days
• Field of Search: 702/150, 348/813, 235/494, 235/469, 283/114, 283/93, 315/383, 315/382
• US Class Current: 702/150
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1443 locating of the code in an image

Abstract

Disclosed is a method of finding a reference object within a coded object having a plurality of regions. Each region has a plurality of subregions, and at least a majority of a first one of the subregions has a different color from a second one of the subregions. The reference object has a known relative position to other objects within the coded object so that the reference object is utilizable to locate the other objects within the coded object. A first one of the subregions within a selected one of the regions within the coded object is selected. A first region and a second region within the coded object are also selected. The selected first and second region form a plurality of subregion pairs. Each subregion pair includes a subregion from the seleced first region and a subregion from the selected second region. Luminosity values of the subregions within each subregion pair are compared. It is determined whether the selected subregion is the reference object based on the comparisons of the luminosity values for each subregion pair.

Claims

1. A method of locating a correct reference pixel within an image, the correct reference pixel representing a reference object within a coded object that has a known code pattern, the method comprising:

receiving an image having a plurality of coded object pixels that include a first expected reference pixel and a plurality of first pixels and second pixels, wherein each first pixel is expected to have a different color from an associated second pixel; and

step for determining whether the first expected reference pixel is a correct reference pixel that represents the reference object of the coded object by comparing luminosity values of the first pixel and the second pixel to determine if the expected reference pixel and first and second pixels substantially match the known code pattern.

2. A method of tracking a position of a movable object with respect to a reference object, the method comprising:

receiving an image having a plurality of coded object pixels that include a first pixel and second pixel, wherein the first pixel has an opposite color than the second pixel; and

step of determining a position of the movable object pixel with respect to the reference object by comparing luminosity values of the first and second pixel.

3. The method recited in claim 2 wherein the position of the movable object indicates whether the movable object is positioned within a particular range of angles with respect to the reference object.

4. The method recited in claim 3, wherein the position of the movable object indicates whether a center of the movable object is to the left or to the right of the reference object.

5. A physical system having a movable object and a reference object that are configured to be scanned by a camera and represented in an image that is received as input to a computer implemented coded object recognition program, the physical system comprising:

a first region having a plurality of first subregions that include a first portion of the movable object, wherein the first subregions are mostly a first color that is different from the first portion of the movable object; and

a second region having a plurality of second subregions that include a second portion of the movable object, wherein the second subregions are mostly a second color that is significantly different from the second portion of the movable object and most of the first subregions

whereby a position of the movable object may be determined by comparing luminosity values for selected pairs of the first and second subregions.

6. The coded object recited in claim 5, wherein the movable object is configured to be rotatable.

7. The coded object recited in claim 5, wherein the position of the movable object is determined with respect to a reference object.

8. A method of finding a reference object within a coded object having a plurality of regions with each region having a plurality of subregions, at least a majority of a first one of the subregions having a different color from a second one of the subregions, the reference object having a known relative position to other objects within the coded object so that the reference object is utilizable to locate the other objects within the coded object, the method comprising:

(a) selecting a first one of the subregions within a selected one of the regions within the coded object;

(b) selecting a first region and a second region within the coded object, the selected first and second region forming a plurality of subregion pairs, each subregion pair including a subregion from the seleced first region and a subregion from the selected second region;

(c) comparing luminosity values of the subregions within each subregion pair; and

(d) determining whether the selected subregion is the reference object based on the comparisons of the luminosity values for each subregion pair.

9. A method as recited in claim 8 wherein the selected subregion is determined to be the reference object when more than a first predetermined number of the selected first region'"'"'s subregions from each subregion pair differ from the selected second region'"'"'s subregions from such each subregion pair by more than a second predetermined number.

10. A method as recited in claim 8 further comprising comparing the luminosity value of the selected subregion and each subregion pair, wherein the determination of whether the selected subregion is the reference object is further based on the comparison of the luminosity value of the selected subregion and each subregion pair.

11. A method as recited in claim 10 wherein

a maximum luminosity value from each of the subregion pairs is known to be greater than the reference object'"'"'s luminosity value, and

the selected subregion is determined to be the reference object when more than a first predefined number of maximum luminosity values of the subregion pairs are greater than the selected subregion'"'"'s luminosity value.

12. A method as recited in claim 10 wherein

a minimum luminosity value from each of the subregion pairs is known to be lower than the reference object'"'"'s luminosity value, and

the selected subregion is determined to be the reference object when more than a first predefined number of minimum luminosity values of the subregion pairs are lower than the selected subregion'"'"'s luminosity value.

13. A method as recited in claim 8, wherein the selected subregion is determined to be the reference object when the sum of luminosity differences between each first subregion and second subregion within each subregion pair is greater than a predefined number.

14. A method as recited in claim 10 wherein

each subregion pair, along with the selected subregion, are expected to have luminosity values wherein a first luminosity value is at least greater than a second and third luminosity value by a second predefined number and the second and third luminosity values have a difference that is not greater than a third predefined number, and

the selected subregion is determined to be the reference object when more than a first predefined number of subregion pairs, along with the selected subregion, have luminosity values wherein the first luminosity value is at least greater than the second and third luminosity value by the second predefined number and the second and third luminosity values have a difference that is not greater than the third predefined number.

15. The method recited in claim 8, wherein the coded object further includes an angle object, wherein the method further comprising:

locating the angle object; and

determining the coded object'"'"'s orientation based on a location of the angle object and the reference object.

16. A coded object comprising:

a reference object;

a first region having a plurality of first subregion pairs, wherein each first subregion pair includes two opposite colored subregions; and

a second region having a plurality of second subregion pairs, wherein each second subregion pair includes two opposite colored subregions,

wherein the first subregion pairs form a plurality of first identifiers for the coded object and the second subregion pairs form a plurality of second identifiers for the coded object.

17. The coded object recited in claim 16, wherein each identifier has an associated value based on a relative placement of a black and white portion within each identifier.

18. The coded object recited in claim 16, wherein one subregion pair selected from the group consisting of the first subregion pairs and second subregion pairs form a angle object, wherein the selected subregion pair has substantially equal color subregions.

19. The coded object recited in claim 16, wherein a first boundary between two of the first identifiers substantially aligns with a second boundary between two of the second identifiers such that a position of the alignment of first and second boundaries may be defined as a position of an angle object.

20. The coded object recited in claim 19, wherein both the first and second boundaries have a color change between the two first identifiers and the two second identifiers.

21. The coded object recited in claim 19, wherein there is at least a color change between two of the first identifiers and between two of the second identifiers.

22. The coded object recited in claim 16, wherein the reference object is white and the coded object further includes a black isolation object that is adjacent to the reference object such as to enhance detection of the reference object and reduce anti-aliasing.

23. A computer readable medium containing instructions for finding a reference object within a coded object having a plurality of regions with each region having a plurality of subregions, at least a majority of a first one of the subregions having a different color from a second one of the subregions, the reference object having a known relative position to other objects within the coded object so that the reference object is utilizable to locate the other objects within the coded object, the computer readable medium comprising computer code for:

(a) selecting a first one of the subregions within a selected one of the regions within the coded object;

(b) selecting a first region and a second region within the coded object, the selected first and second region forming a plurality of subregion pairs, each subregion pair including a subregion from the seleced first region and a subregion from the selected second region;

(c) comparing luminosity values of the subregions within each subregion pair; and

(d) determining whether the selected subregion is the reference object based on the comparisons of the luminosity values for each subregion pair.

24. A computer readable medium as recited in claim 23 wherein the selected subregion is contained within the selected first region.

25. A computer readable medium as recited in claim 23 wherein the selected subregion is determined to be the reference object when more than a first predetermined number of the selected first region'"'"'s subregions from each subregion pair differ from the selected second region'"'"'s subregions from such each subregion pair by more than a second predetermined number.

26. A computer readable medium as recited in claim 23 further comprising code for:

selecting a next selected subregion, a next first region, and a next second region, the next selected first and second regions forming a plurality of next subregion pairs, each next subregion pair including a subregion from the next seleced first region and a subregion from the next selected second region, and

repeating acts (c) and (d) for the next selected subregion, the next first regions the next second region, and the next subregion pair.

27. A computer readable medium as recited in claim 26 wherein the next selected subregion is contained within the next selected first region.

28. A computer readable medium as recited in claim 26 wherein only one of the previous selected subregion and the next selected subregion are determined to be the reference object.

29. A computer readable medium as recited in claim 26 wherein

the previous selected subregion is determined to be the reference object when the previous selected subregion has a number of first subregions from each previous subregion pair that differ from the second subregions from such previous subregion pair by more than the second predetermined number is greater than a number of first subregions from each next subregion pair that differ from the second subregions from such next subregion pair by more than the second predetermined number and is greater than the first predetermined number, and

the next selected subregion is determined to be the reference object when the next selected subregion has a number of first subregions from each next subregion pair that differ from the second subregions from such next subregion pair by more than the second predetermined number is greater than a number of first subregions from each previous subregion pair that differ from the second subregions from such previous subregion pair by more than the second predetermined number and is greater than the first predetermined number.

30. A computer readable medium as recited in claim 23 further comprising computer code for comparing the luminosity value of the selected subregion and each subregion pair, wherein the determination of whether the selected subregion is the reference object is further based on the comparison of the luminosity value of the selected subregion and each subregion pair.

31. A computer readable medium as recited in claim 30 wherein

a maximum luminosity value from each of the subregion pairs is known to be greater than the reference object'"'"'s luminosity value, and

the selected subregion is determined to be the reference object when more than a first predefined number of maximum luminosity values of the subregion pairs are greater than the selected subregion'"'"'s luminosity value.

32. A computer readable medium as recited in claim 30 wherein

a minimum luminosity value from each of the subregion pairs is known to be lower than the reference object'"'"'s luminosity value, and

the selected subregion is determined to be the reference object when more than a first predefined number of minimum luminosity values of the subregion pairs are lower than the selected subregion'"'"'s luminosity value.

33. A computer readable medium as recited in claim 30 further comprising computer code for:

selecting a next selected subregion, a next first region, and a next second region, the next selected first and second regions forming a plurality of next subregion pairs, each next subregion pair including a subregion from the next seleced first region and a subregion from the next selected second region, and

repeating acts (c) and (d) for the next selected subregion, the next first regions the next second region, and the next subregion pair.

34. A computer readable medium as recited in claim 33 wherein

a maximum luminosity value from each of the subregion pairs is expected to be greater than the reference object'"'"'s luminosity value,

the previous selected subregion is determined to be the reference object when the previous selected subregion has a highest number of maximum luminosity values of the subregion pairs that are greater than the selected subregion as compared to the next selected subregion, and

the next selected subregion is defined as the reference object when the next selected subregion has a highest number of maximum luminosity values of the next subregion pairs that are greater than the next selected subregion as compared to the previous selected subregion.

35. A computer readable medium as recited in claim 23 wherein the selected subregion is determined to be the reference object when the sum of luminosity differences between each first subregion and second subregion within each subregion pair is greater than a predefined number.

36. A computer readable medium as recited in claim 35 further comprising computer code for:

selecting a next selected subregion, a next first region, and a next second region, the next selected first and second regions forming a plurality of next subregion pairs, each next subregion pair including a subregion from the next seleced first region and a subregion from the next selected second region, and

repeating acts (c) and (d) for the next selected subregion, the next first region, the next second region, and the next subregion pair.

37. A computer readable medium as recited in claim 36 wherein

the previous selected subregion is determined to be the reference object when a sum of luminosity differences between each first subregion and second subregion within each previous subregion pair is greater than a predefined number and is greater than the predefined number, and

the next selected subregion is determined to be the reference object when a sum of luminosity differences between each first subregion and second subregion within each next subregion pair is greater than a predefined number and is greater than the predefined number.

38. A computer readable medium as recited in claim 30 wherein

each subregion pair, along with the selected subregion, are expected to have luminosity values wherein a first luminosity value is at least greater than a second and third luminosity value by a second predefined number and the second and third luminosity values have a difference that is not greater than a third predefined number, and

the selected subregion is determined to be the reference object when more than a first predefined number of subregion pairs, along with the selected subregion, have luminosity values wherein the first luminosity value is at least greater than the second and third luminosity value by the second predefined number and the second and third luminosity values have a difference that is not greater than the third predefined number.

39. A computer readable medium as recited in claim 38 further comprising computer code for:

selecting a next selected subregion, a next first region, and a next second region, the next selected first and second regions forming a plurality of next subregion pairs, each next subregion pair including a subregion from the next seleced first region and a subregion from the next selected second region, and

repeating acts (c) and (d) for the next selected subregion, the next first region, the next second region, and the next subregion pair.

40. A computer readable medium as recited in claim 39 wherein

the previous selected subregion is defined as the reference object when the previous selected subregion has a highest number of previous subregion pairs, along with the previous selected subregion, that have luminosity values wherein a first luminosity value is at least higher than a second and third luminosity value by a second predefined number and the second and third luminosity values have a difference that is not greater than a third predefined number, as compared to the next selected subregion, and

the next selected subregion is defined as the reference object when the next selected subregion has a highest number of next subregion pairs, along with the next selected subregion, that have luminosity values wherein a first luminosity value is at least higher than a second and third luminosity value by a second predefined number and the second and third luminosity values have a difference that is not greater than a third predefined number, as compared to the previous selected subregion.

41. The computer readable medium recited in claim 23, wherein the coded object further includes an angle object, the computer readable medium further comprising computer code for:

locating the angle object; and

determining the coded object'"'"'s orientation based on a location of the angle object and the reference object.