Three dimensional vision device and method, and structured light bar-code patterns for use in the same
The present invention is a system and method for three dimensional machine vision including a projector and camera. The projector casts a structured light Quadratic Residue Bar Code on the surface to be mapped. The camera then images the surface. The projected image is shifted, and the process is repeated a number of times, according to the particular arrangement selected for the structured light Quadratic Residue Bar Code. The image data collected from this series of images is then processed by relatively simple matrix operations to determine the location of each camera pixel in three dimensional space.
1. A system for mapping a surface comprising:
a projection device operative to project a sequence of parallel bars, each of said bars having one of a first and second light values, wherein a vector representation of the order of said bars, supplemented by a value representing an additional bar, is mutually orthogonal to any circular shift of said order supplemented by a value representing an additional bar;
means for generating an image of the surface; and
means for processing the resulting image to map the surface.
2. The system according to claim 1 , wherein each of said bars has substantially the same width.
3. The system according to claim 1 , wherein said bars whose order in said sequence is equal to the remainder of a perfect square number divided by the number of said bars in each period have said first light value, and all other said bars have said second light value.
4. The system according to claim 1 , wherein said sequence comprises a prime number p of bars according to the formula [p=4m−1], where m is a positive integer.
5. The system according to claim 4 wherein said prime number p is 19.
6. The system according to claim 1 , wherein each of said bars has one of a first and second light value, according to the sequence:
++++−+−++−−+−−−
where “+” represents the first light value and “−” represents the second light value, or any circular shift of said sequence.
7. A method of mapping a surface comprising the steps of:
(a) projecting a bar code onto the surface to be mapped;
(b) incrementally shifting said bar code over the surface a number of times equal to one less than the number of bars comprising said bar code;
(c) imaging the surface for each position of said bar code, to collect data as to the light intensity of each of a plurality of pixels comprising said image; and
(d) processing said collected data to determine the location in three dimensional space of the portion of the surface corresponding to each pixel.
8. The method according to claim 7 , wherein the processing of the collected data includes the addition of data representing an image of the surface without said projected bar code.
9. The method according to claim 8 further comprising the step of imaging the surface to be mapped absent said projected bar code to form said additional data.
10. The method according to claim 8 further comprising the step of simulating a dark image to form said additional data.
11. The method according to claim 7 wherein the step of processing said collected data to determine the location in three dimensional space of the portion of the surface corresponding to each pixel further comprises:
(a) calculating the correspondence of each pixel to a respective one of said bars which comprise the bar code.
12. The method according to claim 7 wherein the step of processing said collected data to determine the location in three dimensional space of the portion of the surface corresponding to each pixel further comprises:
(a) processing said collected data to determine the proportion of each of a plurality of said bars which comprise the image within each pixel.
13. A bar code pattern for mapping a surface, said bar code comprising a sequence of parallel bars, each of said bars having one of a first and second light values, wherein a vector representation of the order of said bars, supplemented by a value representing an additional bar, is mutually orthogonal to any circular shift of said order supplemented by a value representing an additional bar.
14. The bar code pattern according to claim 13 wherein said bars whose order in said sequence is equal to the remainder of a perfect square number divided by the number of said bars in each period have said first light value, and all other said bars have said second light value.
15. The bar code pattern according to claim 13 wherein each of said bars has a substantially the same width.
16. The bar code pattern according to claim 13 wherein said sequence of bars comprises a prime number p of bars according to the formula [p=4m−1], where m is a positive integer.
17. The bar code pattern according to claim 16 wherein said prime number p is 19.
18. The bar code pattern according to claim 13 , said structured light comprising 15 bars, wherein each of said bars is has one of a first and second light value, according to the sequence
++++−+−++−−+−−−
where “+” represents the first light value and “−” represents the second light value, or any circular shift of said sequence.
19. An apparatus displaying the bar code pattern according to claim 13 .
20. An apparatus for mapping a surface comprising:
an input for receiving image data representing a plurality of images of the surface, at least one of said images comprising said surface illuminated by a predetermined structured light;
means for determining the correspondence between each pixel of said image data and one or more portions of said predetermined structured light;
means for calculating a position of the portion of said surface corresponding to each pixel, from the determined correspondence, a predetermined position of a source of the predetermined structured light, and a predetermined position of the source of the images,
said determining and said calculating being carried out as a function of a stored sequence of parallel bars, each of said bars having one of a first and second light values, wherein a vector representation of the order of said bars, supplemented by a value representing an additional bar, is mutually orthogonal to any circular shift of said order supplemented by a value representing an additional bar.
21. The apparatus according to claim 20 , wherein said means for determining the correspondence comprises means for calculating the inner product of a time series vector for each pixel of the image data and a time series fingerprint of each portion of the predetermined structured light.
22. A method of mapping a surface comprising:
collecting image data representing a plurality of images of the surface, at least one of said images comprising said surface illuminated by a predetermined structured light;
determining the correspondence between each pixel of said image data and one or more portions of said predetermined structured light;
calculating a position of a portion of said surface corresponding to each pixel from the determined correspondence, a predetermined position of a source of the predetermined structured light, and a predetermined position of the source of the images,
said determining and said calculating being carried out as a function of a stored sequence of parallel bars, each of said bars having one of a first and second light values, wherein a vector representation of the order of said bars, supplemented by a value representing an additional bar, is mutually orthogonal to any circular shift of said order supplemented by a value representing an additional bar.
23. The method according to claim 22 , wherein determining the correspondence comprises calculating the inner product of a time series vector for each pixel of the image data and a time series fingerprint of each portion of the predetermined structured light.
24. An apparatus for generating a bar code pattern for mapping a surface, said apparatus comprising a projection device operative to project a bar code comprising a sequence of parallel bars, each of said bars being one of either light and dark, wherein a vector representation of the order of light and dark bars, supplemented by a value representing a dark bar, is mutually orthogonal to any circular shift of said order supplemented by a value representing a dark bar.
25. The apparatus according to claim 24 , wherein said projection device comprises a laser emitter and a rotating reflective surface.
26. The apparatus according to claim 24 , wherein said projection device comprises a mask for forming said bar code.
27. The apparatus according to claim 24 , wherein said projection device comprises means for generating a video signal, and means for actively projecting said video signal.
28. A processor for mapping a surface comprising:
means for determining correspondence between each pixel of image data representing a plurality of images and one or more portions of a predetermined structured light, wherein at least one image among said plurality of images depicts said surface illuminated by said predetermined structured light, said means for determining comprising means for calculating the inner product of a time series vector for each pixel of the image data and a time series fingerprint of each portion of the predetermined structured light;
means for calculating a position of a portion of said surface which corresponds to each pixel from said determined correspondence, a predetermined position of a source of said predetermined structured light, and a predetermined position of a source of said series of images.