Region segmentation and characterization systems and methods for augmented reality

• US 20040258314A1
• Filed: 06/23/2003
• Published: 12/23/2004
• Est. Priority Date: 06/23/2003
• Status: Active Grant

• Current Assignee: Shoestring Research LLC
• Original Assignee: Shoestring Research LLC
• Inventors: Hashimoto, Roy T.
• Granted Patent: US 7,515,756 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 3/012 Head tracking input arrangements
• CPC Class Codes: G06F 3/0325 using a plurality of light emitters or reflectors or a plurality of detectors forming a reference frame from which to derive the orientation of the object, e.g. by triangulation or on the basis of reference deformation in the picked up image
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/74 involving reference images or patches

Abstract

A novel method of region segmentation for an image is disclosed. Specifically, region segmentation is accomplished by dividing the image into a plurality of sticks of pixels and determining whether each stick belongs to any region from a set of region. Each stick that belongs to any region is classified as belonging to a specific region.

Claims

1. A method of segmenting an image having a plurality of pixels, the method comprising:

dividing the image into a plurality of sticks of pixels, wherein each stick contains at least two pixels;

determining whether each stick belongs to any region from a set of region; and

classifying each stick that belongs to any region as belonging to a specific region of the set of regions.

2. The method of claim 1, wherein each pixel of each stick are from a single raster line.

3. The method of claim 2, wherein each pixel of each stick are consecutive pixels of the single raster line.

4. The method of claim 2, wherein a size of each stick is a multiple of a word size of a SIMD processor.

5. The method of claim 1, wherein determining whether each stick belongs to any region from a set of region comprises:

determining whether any pixel of a current stick belongs to any region; and

classifying the current stick as belonging to any region when any pixel of the current stick belongs to any region.

6. The method of claim 5, wherein the determining whether any pixel of a current stick belongs to any region comprises comparing a binary classifier input value with a threshold level.

7. The method of claim 6, wherein the binary classifier input value is a color component.

8. The method of claim 6, wherein the binary classifier input value is a luminance value.

9. The method of claim 6, wherein the binary classifier is a chrominance value.

10. The method of claim 5, wherein the determining whether any pixel of a current stick belongs to any region comprises:

comparing a first binary classifier input value with a first threshold level;

comparing a second binary classifier input value with a second threshold level.

11. The method of claim 1, wherein the classifying each stick that belongs to any region as belonging to a specific region of the set of regions comprises:

determining whether any member of a set of previously processed sticks belong to any region;

assigning an earliest region identifier of a set of previously processed sticks to the current stick when a member of the set of previously processed sticks belongs to any region and the current stick belongs to any region; and

assigning a new region identifier to the current stick when the current stick belongs to any region and no member of the set of previously processed sticks belongs to any region.

12. The method of claim 11, wherein the set of previously processed sticks comprises:

a preceding stick on the same raster row as the current stick;

a first stick on a preceding raster row; and

a second stick on the preceding raster row.

13. The method of claim 12, wherein the first stick is in a same row position as the current stick and the second stick is in a following row position of the current stick.

14. The method of claim 1, further comprising characterizing each region of the set of regions.

15. The method of claim 14, wherein the characterizing each region of the set of regions comprises computing rectified moments for each region using a weighting table and unrectified image data.

16. The method of claim 15, wherein the weighted lookup table comprises pre-computed coefficient vectors.

17. The method of claim 16, wherein the pre-computed coefficient vectors are a product of a weight factor, a first pixel coordinate raised to a non-negative power, and a second pixel coordinate raised to a non-negative power.

18. A method of segmenting an image having a plurality of pixels, the method comprising:

dividing the image into a plurality of sticks of pixels, wherein each stick contains at least two pixels;

determining whether each stick belongs to any region from a set of region; and

classifying each stick that belongs to any region as belonging to a specific region of the set of regions.

19. The method of claim 18, wherein each pixel of each stick are from a single raster line.

20. The method of claim 19, wherein each pixel of each stick are consecutive pixels of the single raster line.

21. The method of claim 19, wherein a size of each stick is a multiple of a word size of a SIMD processor.

22. The method of claim 18, wherein determining whether each stick belongs to any region from a set of region comprises:

determining whether any pixel of a current stick belongs to any region; and

classifying the current stick as belonging to any region when any pixel of the current stick belongs to any region.

23. The method of claim 22, wherein the determining whether any pixel of a current stick belongs to any region comprises comparing a binary classifier input value with a threshold level.

24. The method of claim 23, wherein the binary classifier input value is a color component.

25. The method of claim 23, wherein the binary classifier input value is a luminance value.

26. The method of claim 23, wherein the binary classifier is a chrominance value.

27. The method of claim 22, wherein the determining whether any pixel of a current stick belongs to any region comprises:

comparing a first binary classifier input value with a first threshold level;

comparing a second binary classifier input value with a second threshold level.

28. The method of claim 18, wherein the classifying each stick that belongs to any region as belonging to a specific region of the set of regions comprises:

determining whether any member of a set of previously processed sticks belong to any region;

assigning an earliest region identifier of a set of previously processed sticks to the current stick when a member of the set of previously processed sticks belongs to any region and the current stick belongs to any region; and

assigning a new region identifier to the current stick when the current stick belongs to any region-and no member of the set of previously processed sticks belongs to any region.

29. The method of claim 28, wherein the set of previously processed sticks comprises:

a preceding stick on the same raster row as the current stick;

a first stick on a preceding raster row; and

a second stick on the preceding raster row.

30. The method of claim 29, wherein the first stick is in a same row position as the current stick and the second stick is in a following row position of the current stick.

31. The method of claim 18, further comprising characterizing each region of the set of regions.

32. The method of claim 31, wherein the characterizing each region of the set of regions comprises computing rectified moments for each region using a weighting table and unrectified image data.

33. The method of claim 32, wherein the weighted lookup table comprises pre-computed coefficient vectors.

34. The method of claim 33, wherein the pre-computed coefficient vectors are a product of a weight factor, a first pixel coordinate raised to a non-negative power, and a second pixel coordinate raised to a non-negative power.

35. A system of segmenting an image having a plurality of pixels, the system comprising:

means for dividing the image into a plurality of sticks of pixels, wherein each stick contains at least two pixels;

means for determining whether each stick belongs to any region from a set of region; and

means for classifying each stick that belongs to any region as belonging to a specific region of the set of regions.

36. The system of claim 35, wherein each pixel of each stick are from a single raster line.

37. The system of claim 36, wherein each pixel of each stick are consecutive pixels of the single raster line.

38. The system of claim 36, wherein a size of each stick is a multiple of a word size of a SIMD processor.

39. The system of claim 35, wherein the means for determining whether each stick belongs to any region from a set of region comprises:

means for determining whether any pixel of a current stick belongs to any region; and

means for classifying the current stick as belonging to any region when any pixel of the current stick belongs to any region.

40. The system of claim 39, wherein the means for determining whether any pixel of a current stick belongs to any region comprises means for comparing a binary classifier input value with a threshold level.

41. The system of claim 40, wherein the binary classifier input value is a color component.

42. The system of claim 40, wherein the binary classifier input value is a luminance value.

43. The system of claim 40, wherein the binary classifier is a chrominance value.

44. The system of claim 39, wherein the means for determining whether any pixel of a current stick belongs to any region comprises:

means for comparing a first binary classifier input value with a first threshold level;

means for comparing a second binary classifier input value with a second threshold level.

45. The system of claim 35, wherein the means for classifying each stick that belongs to any region as belonging to a specific region of the set of regions comprises:

determining whether any member of a set of previously processed sticks belong to any region;

assigning an earliest region identifier of a set of previously processed sticks to the current stick when a member of the set of previously processed sticks belongs to any region and the current stick belongs to any region; and

assigning a new region identifier to the current stick when the current stick belongs to any region and no member of the set of previously processed sticks belongs to any region.

46. The system of claim 45, wherein the set of previously processed sticks comprises:

a preceding stick on the same raster row as the current stick;

a first stick on a preceding raster row; and

a second stick on the preceding raster row.

47. The system of claim 46, wherein the first stick is in a same row position as the current stick and the second stick is in a following row position of the current stick.

48. The system of claim 35, further comprising characterizing each region of the set of regions.

49. The system of claim 44, wherein the characterizing each region of the set of regions comprises computing rectified moments for each region using a weighting table and unrectified image data.

50. The system of claim 49, wherein the weighted lookup table comprises pre-computed coefficient vectors.

51. The system of claim 50, wherein the pre-computed coefficient vectors are a product of a weight factor, a first pixel coordinate raised to a non-negative power, and a second pixel coordinate raised to a non-negative power.

56. The system of claim 51, wherein the means for determining whether each stick belongs to any region from a set of region comprises:

means for determining whether any pixel of a current stick belongs to any region; and

means for classifying the current stick as belonging to any region when any pixel of the current stick belongs to any region.

57. The system of claim 56, wherein the means for determining whether any pixel of a current stick belongs to any region comprises means for comparing a binary classifier input value with a threshold level.

58. The system of claim 57, wherein the binary classifier input value is a color component.

59. The system of claim 57, wherein the binary classifier input value is a luminance value.

60. The system of claim 57, wherein the binary classifier is a chrominance value.

61. The system of claim 56, wherein the means for determining whether any pixel of a current stick belongs to any region comprises:

means for comparing a first binary classifier input value with a first threshold level;

means for comparing a second binary classifier input value with a second threshold level.

52. A system of segmenting an image having a plurality of pixels, the system comprising:

dividing the image into a plurality of sticks of pixels, wherein each stick contains at least two pixels;

determining whether each stick belongs to any region from a set of region; and

classifying each stick that belongs to any region as belonging to a specific region of the set of regions.

53. The system of claim 52, wherein each pixel of each stick are from a single raster line.

54. The system of claim 53, wherein each pixel of each stick are consecutive pixels of the single raster line.

55. The system of claim 53, wherein a size of each stick is a multiple of a word size of a SIMD processor.

62. The system of claim 52, wherein the means for classifying each stick that belongs to any region as belonging to a specific region of the set of regions comprises:

means for determining whether any member of a set of previously processed sticks belong to any region;

means for assigning an earliest region identifier of a set of previously processed sticks to the current stick when a member of the set of previously processed sticks belongs to any region and the current stick belongs to any region; and

means for assigning a new region identifier to the current stick when the current stick belongs to any region and no member of the set of previously processed sticks belongs to any region.

63. The system of claim 62, wherein the set of previously processed sticks comprises:

a preceding stick on the same raster row as the current stick;

a first stick on a preceding raster row; and

a second stick on the preceding raster row.

64. The system of claim 63, wherein the first stick is in a same row position as the current stick and the second stick is in a following row position of the current stick.

65. The system of claim 52, further comprising means for characterizing each region of the set of regions.

66. The system of claim 65, wherein the means for characterizing each region of the set of regions comprises means for computing rectified moments for each region using a weighting table and unrectified image data.

67. The system of claim 66, wherein the weighted lookup table comprises pre-computed coefficient vectors.

68. The system of claim 67, wherein the pre-computed coefficient vectors are a product of a weight factor, a first pixel coordinate raised to a non-negative power, and a second pixel coordinate raised to a non-negative power.