Méthodologie de conception de motifs dirigée par la distance de Hamming et la géométrie épipolaire en lumière structurée

Méthodologie de conception de motifs dirigée par la distance de Hamming et la géométrie épipolaire en lumière structurée

Xavier Maurice Christophe Doignon 

Laboratoire des Sciences de l’Image, de l’Informatique et de la Télédétection (UMR CNRS 7005) Université de Strasbourg Bd Sébastien Brant, BP 10413 F-67412 Illkirch cedex

Corresponding Author Email: 
xavyeah.maurice@gmail.com
Page: 
229-254
|
DOI: 
https://doi.org/10.3166/TS.29.229-254
Received: 
N/A
|
Accepted: 
N/A
|
Published: 
31 August 2012
| Citation

OPEN ACCESS

Abstract: 

Structured light-based patterns provide a way to capture the state of an object shape. However it may be inefficient when the object is freely moving or when its surface contains highly curved parts. To deal with unstructured and dynamical environments, only one shot is required for capturing the shape of a moving region-of-interest. Then robust patterns and real-time capabilities must be targeted. In this paper we present a new matching technique for the pattern visual features, through the numerical coding of the associated symbols. The novelty of the proposed method is to use both the epipolar geometry and a desired Hamming distance of this stereovision-like system, the latter criterion can be specified by its minimal value for the pattern design. This ensures a high degree of redundancy within the overall pattern to project. The counterpart is the big amount of codes the coding/decoding algorithms have to face with a high desired Hamming distance. In the first part, we show that the mean Hamming distance is a useful criterion for characterizing the future pattern and we give a way to predict its value. Furthermore, to ensure the local uniqueness of every code with consideration of many incomplete ones, the Perfect Map theory is involved. Then, we describe a pseudorandom/exhaustive algorithm to build very large patterns in a very short time, thanks to a splitting strategy which performs the Hamming tests in the 1-D code address space instead of the 2-D pattern array. This leads to a significant reduction of the computational complexity and it may be applied to other purposes. Second, the conjunction of features conformation and epipolar geometry simplifies the segmentation as it provides a better understanding of the projected features in the image.The results show that epipolar-aligned patterns can be quickly produced thanks to this coding scheme which yields far more redundant and/or bigger coding maps than what have been achieved in the literature. Finally, real-time surface reconstructions from single images are reported and results are compared to the best known ones which are outperformed in many cases.

RÉSUMÉ

En vision artificielle par lumière structurée, la projection d’un motif sur un objet permet de capturer la forme de sa surface à un instant donné, en effectuant généralement plusieurs acquisitions. Cette technique peut cependant s’avérer inefficace lorsque l’objet est en mouvement. Il devient alors nécessaire de ne faire appel qu’à une seule prise d’images pour analyser la forme d’une région d’intérêt en mouvement, et des motifs intégrant des propriétés intrinsèques de corrections doivent alors être envisagés. Dans cet article nous présentons une nouvelle méthode d’appariement d’indices visuels composant des motifs de lumière structurée codée. L’originalité de la méthode consiste, à travers un codage spatial, à exploiter conjointement la géométrie épipolaire et une distance de Hamming désirée, critère dont la valeur minimale peut être spécifiée dès la conception, assurant un niveau minimal de redondance des informations au sein du motif à projeter. En contrepartie, quand la valeur de celle-ci est élevée, les algorithmes de codage/décodage ont à faire face à un nombre considérable de codes candidats. Dans un premier temps, nous montrons que la distance de Hamming moyenne est un critère statistique pertinent pour prédire les propriétés globales du futur motif, et nous fournissons un moyen de la calculer. Nous présentons un algorithme de codage basé sur la théorie des matrices parfaites, la distance de Hamming et le paradigme exploration/exploitation, où l’unicité des codes est examinée dans l’espace monodimensionnel des adresses des codes au lieu de celui du motif matriciel, comme c’est le cas dans la littérature. Dans un second temps, mettant en synergie la conformation des indices visuels et la géométrie épipolaire, nous montrons qu’il est possible de prédire la façon dont ces indices vont se projeter sur le plan image, permettant ainsi de simplifier la segmentation, le codage et le décodage. Les résultats montrent une réduction significative de la complexité algorithmique et la possibilité de fournir des motifs en temps réel, ou bien d’une taille bien supérieure à ce qui existe à ce jour. Finalement, des reconstructions de scènes diverses et effectuées aussi en temps réel, à partir d’une seule image des motifs projetés, sont reportées, pour illustrer le potentiel applicatif de notre approche.

Keywords: 

coded structured light, perfect maps, epipolar geometry, surfaces reconstruction, minimum Hamming distance

MOTS-CLÉS

lumière structurée codée, matrices parfaites, géométrie épipolaire, reconstruction de surfaces, distance de Hamming minimum

Extended Abstract
1. Introduction
2. Statistiques Pour La Conception De Motifs
3. Génération De Motifs Matriciels
4. Conception De Motifs Basée Sur La Géométrie Épipolaire
5. Reconstruction De Surfaces À Partir D’une Image
6. Conclusion
  References

Adan A., Vàsquez A., Cerrada C., Salamanca S. (2009). Moving surface extraction based on unordered hexagonal perfect submaps projection: Applications to 3D feature tracking. Image and Vision Computing, vol. 27, n° 8, p 1083-1096.

Albitar C., Graebling P., Doignon C. (2007). Robust structured light coding for 3D reconstruction. IEEE Int’l Conference on Computer Vision, Rio de Janeiro, Brésil.

Batlle J., Mouaddib E.M., Salvi J. (1998). Recent progress in coded structured light as a technique to solve the correspondence problem: a survey. Pattern Recognition, vol. 31, n° 7, p. 963-982.

Chan S.Y., Li Y.F., Zhang J. (2007). Real-time Structured Light Vision with the Principle of Unique Color Codes. IEEE Int’l Conf. on Robotics and Automation, p. 429-434.

Claes K. (2008). Structured Light Adapted to Control a Robot Arm. Thèse de Doctorat, Katholik Univ. Louvain, Belgique.

De Bruijn N. G. (1946). A combinatorial problem. Nederlanske Akad. van Wetenschappen, p. 758-764.

Etzion T. (1988). Constructions for perfect maps and pseudorandom arrays, IEEE Transactions on Information Theory, vol. 34, n° 5/1, p. 1308-1316.

Griffin P.M., Narasimhan L.S., Yee S.R. (1992). Generation of uniquely encoded light patterns for range data acquisition, Pattern Recognition, vol. 25, n° 6, p. 609-616.

Gühring J. (2001). Dense 3-D surface acquisition by structured light using off-the-shelf components. Videometrics and Optical Methods for 3D Shape Measurement, vol. 4309, p. 220-231.

Hartley R., Zisserman A. (2000). Multiple view geometry in computer vision. Cambridge Univ. Press.

Hulbert G., Garth I. (1993). On the de Bruijn torus problem. Journal of Combinatorial Theory Ser. A, vol. 64, p. 50-62.

Hung D. (1993). 3D scene modeling by sinusoid encoded illumination. Image and Vision Computing, vol. 11, p. 251-256.

Ishii I., Yamamoto K., Doi K. and Tsuji T. (2007). High-speed 3D image acquisition using coded structured light projection. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 925-930, St Louis, USA.

Kawasaki H. Furukawa R., Sagawa R., Yagi Y. (2008). Dynamic scene shape reconstruction using a single structured light pattern. IEEE Int’l Conf. on Computer Vision and Pattern Recognition, Anchorage, Alaska, USA.

Koninckx T.P., Van Gool L. (2006). Real-Time Range Acquisition by Adaptive Structured Light. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, n° 3, p. 432-445.

Longuet-Higgins C. (1981). A computer algorithm for reconstructing a scene from two projections, Nature, vol. 293, p. 61-62.

Maurice X., C. Doignon (2012). Méthodologie de conception dirigée par la distance de Hamming : application à la reconstruction de surfaces à partir d’une seule image, Actes de la conférence RFIA, Lyon.

Maurice X., Graebling P., Doignon C. (2011). A pattern framework driven by the Hamming distance for structured light-based reconstruction with a single image. IEEE Int’l Conference on Computer Vision and Pattern Recognition, Colorado Springs, USA.

Maurice X., Graebling P., Doignon C. (2010). Conception et appariement de motifs géométriques pour une projection de lumière structurée. Actes de la conférence RFIA, Caen, France.

Mitchell C.J. (1995). Aperiodic and semi-periodic perfect maps. IEEE Transactions on Information Theory, vol. 41, n° 1, p. 88-95.

Morano A., Ozturk C., Conn R., Dubin S., Zietz S., Nissanov J. (1998). Structured Light Using Pseudo-random Codes. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, n° 3, p. 322-327.

Morita, H., Yajima, K., Sakata, S. (1988). Reconstruction of surfaces of 3-D objects by MArray pattern projection method. IEEE Int’l. Conference on Computer Vision, vol. 88, p. 468-473.

Pagès J., Salvi J. Collewet C., Forest J. (2005). Optimised De Bruijn patterns for one-shot acquisition. Image and Vision Computing, vol. 23, p. 707-720.

Patterson K.G. (1994). Perfect Maps. IEEE Transactions on Information Theory, vol. 40, n° 3, p. 743-753.

Peterson W.W., Weldon E.J. Jr. (1972). Error-Correcting Codes, 2nd edition, Cambridge MIT Press.

Pribanic T., Dapo H., Salvi J. (2009). Efficient and Low-Cost 3D Structured light system based on a modified number-theoretic approach. EURASIP Journal on Advances in Signal Processing, vol. 2010.

Sagawa R., Ota Y., Yagi Y., Furukawa R., Asada N. (2009). Dense 3-D reconstruction method using a single pattern for fast moving object. IEEE Int’l Conf. Computer Vision, Kyoto, Japon.

Salvi J., Pagès J., Batlle J. (2004). Pattern codification strategies in structured light systems. Pattern Recognition, vol. 37, p. 827-849.

Salvi J., Batlle J., Mouaddib E.M. (1998). A robust-coded pattern projection for dynamic 3d scene measurement. Pattern Recognition Letters, vol. 19, p. 1055-1065.

Singleton R.C. (1964). Maximum distance q-nary codes. IEEE Transactions on Information Theory, vol. 10, p. 116-118.

Weise T., Leibe B., Van Gool L. (2007). Fast 3-D scanning with automatic motion compensation. IEEE Int’l Conf. on Computer Vision and Pattern Recognition, Minneapolis, MN, USA.

Young M., Beeson E., Davis J., Rusinkiewicz S., Ramamoorthi R. (2007). View-point coded structured light. IEEE Int’l Conf. on Computer Vision and Pattern Recognition, Minneapolis, MN, USA.

Zhang L., Curless B., Seitz S. (2002). Rapid shape acquisition using structured light and multi-pass dynamic programming, Int’l Symp. on 3D Data Processing, Visualization and Transmission, p. 24-36.