## Factor graph methods for three-dimensional shape reconstruction as applied to LIDAR imaging

JOSA A, Vol. 21, Issue 10, pp. 1855-1868 (2004)

http://dx.doi.org/10.1364/JOSAA.21.001855

Enhanced HTML Acrobat PDF (595 KB)

### Abstract

Two methods based on factor graphs for reconstructing the three-dimensional (3D) shape of an object from a series of two-dimensional images are presented. First, a factor graph model is developed for image segmentation to obtain silhouettes from raw images; the shape-from-silhouette technique is then applied to yield the 3D reconstruction of the object. The second method presented is a direct 3D reconstruction of the object using a factor graph model for the voxels of the reconstruction. While both methods should be applicable to a variety of input data types, they will be developed and demonstrated for a particular application involving the LIDAR imaging of a submerged target. Results from simulations and from real LIDAR data are shown that detail the performance of the methods.

© 2004 Optical Society of America

**OCIS Codes**

(100.2000) Image processing : Digital image processing

(100.3010) Image processing : Image reconstruction techniques

(100.6890) Image processing : Three-dimensional image processing

**History**

Original Manuscript: December 22, 2003

Revised Manuscript: May 19, 2004

Manuscript Accepted: May 19, 2004

Published: October 1, 2004

**Citation**

Robert J. Drost and Andrew C. Singer, "Factor graph methods for three-dimensional shape reconstruction as applied to LIDAR imaging," J. Opt. Soc. Am. A **21**, 1855-1868 (2004)

http://www.opticsinfobase.org/josaa/abstract.cfm?URI=josaa-21-10-1855

Sort: Year | Journal | Reset

### References

- I. Quidu, J. Ph. Malkasse, G. Burel, P. Vilbé, “Mine classification based on raw sonar data: an approach combining Fourier descriptors, statistical models, and genetic algorithms,” in Proceedings of Oceans 2000 MTS/IEEE Conf. and Exhibition (IEEE Press, Piscataway, N.J., 2000), Vol. 1, pp. 285–290.
- Q. Zheng, S. Z. Der, H. I. Mahmoud, “Model-based target recognition in pulsed ladar imagery,” IEEE Trans. Image Process. 10, 565–572 (2001). [CrossRef]
- P. J. Shargo, N. Çadalli, A. C. Singer, D. C. Munson, “A tomographic framework for LIDAR imaging,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE Press, Piscataway, N.J., 2001), Vol. 3, pp. 1893–1896.
- W. N. Martin, J. K. Aggarwal, “Volumetric descriptions of objects from multiple views,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 150–158 (1983). [CrossRef]
- A. Laurentini, “How far 3D shapes can be understood from 2D silhouettes,” IEEE Trans. Pattern Anal. Mach. Intell. 17, 188–195 (1995). [CrossRef]
- A. Laurentini, “The visual hull concept for silhouette-based image understanding,” IEEE Trans. Pattern Anal. Mach. Intell. 16, 150–162 (1994). [CrossRef]
- Lavakusha, A. K. Pujari, P. G. Reddy, “Linear octrees by volume intersection,” Comput. Vision Graph. Image Process. 45, 371–379 (1989). [CrossRef]
- M. Potemsil, “Generating octree models of 3D objects from their silhouettes in a sequence of images,” Comput. Vis. Graph. Image Process. 40, 1–29 (1987). [CrossRef]
- N. Ahuja, J. Veenstra, “Efficient octree generation from silhouettes,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (IEEE Press, Piscataway, N.J., 1986), pp. 537–542.
- M. Jones, J. P. Oakley, “Efficient representation of object shape for silhouette intersection,” IEE Proc. Vision Image Signal Process. 142, 359–365 (1995). [CrossRef]
- J. C. Carr, W. R. Fright, A. H. Gee, R. W. Prager, K. J. Dalton, “3D shape reconstruction using volume intersection techniques,” in Proceedings of the IEEE International Conference on Computer Vision (IEEE Press, Piscataway, N.J., 1998), pp. 1095–1100.
- Lavakusha, A. K. Pujari, P. G. Reddy, “Volume intersection algorithm with changing directions of view,” in Proceedings of the International Workshop on Industrial Applications of Machine Intelligence and Vision (IEEE Press, Piscataway, N.J., 1989), pp. 309–314.
- M. Kass, A. Witkin, D. Terzopoulos, “Snakes: active contour models,” Int. J. Comput. Vision 1, 321–331 (1988). [CrossRef]
- C. Xu, J. L. Prince, “Snakes, shapes, and gradient vector flow,” IEEE Trans. Image Process. 7, 959–969 (1998).
- A. K. Jain, Y. Zhong, S. Lakshmanan, “Object matching using deformable templates,” IEEE Trans. Pattern Anal. Mach. Intell. 18, 267–278 (1996). [CrossRef]
- G. Poggi, A. R. P. Ragozini, “Image segmentation by tree-structured Markov random fields,” IEEE Signal Process. Lett. 6, 155–157 (1999). [CrossRef]
- R. A. Weisenseel, W. C. Karl, D. A. Casañon, R. C. Brower, “MRF-based algorithms for segmentation of SAR images,” in Proceedings of the International Conference on Image Processing (IEEE Computer Society Press, Los Alamitos, Calif., 1998), Vol. 3, pp. 770–774.
- M. Mignotte, C. Collet, P. Perez, P. Bouthemy, “Unsupervised Markovian segmentation of sonar images,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE Press, Piscataway, N.J., 1997), Vol. 4, pp. 2781–2784.
- D. Snow, P. Viola, R. Zabih, “Exact voxel occupancy with graph cuts,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 2000), Vol. 1, pp. 345–352.
- R. E. Walker, J. W. McLean, “LIDAR equations for turbid media with pulse stretching,” Appl. Opt. 38, 2384–2397 (1999). [CrossRef]
- J. W. McLean, J. D. Freeman, R. E. Walker, “Beam spread function with time dispersion,” Appl. Opt. 37, 4701–4711 (1998). [CrossRef]
- N. Çadalli, D. C. Munson, A. C. Singer, “Bistatic receiver model for airborne LIDAR returns incident on an imaging array from underwater objects,” Appl. Opt. 41, 3638–3649 (2002). [CrossRef] [PubMed]
- R. E. Walker, Marine Light Field Statistics (Wiley, New York, 1994).
- F. R. Kschischang, B. J. Frey, H.-A. Loeliger, “Factor graphs and the sum–product algorithm,” IEEE Trans. Inf. Theory 47, 498–519 (2001). [CrossRef]
- F. R. Kschischang, B. J. Frey, “Iterative decoding of compound codes by probability propagation in graphical models,” IEEE J. Sel. Areas Commun. 16, 219–230 (1998). [CrossRef]
- B. J. Frey, R. Koetter, N. Petrovic, “Codes on images and iterative phase unwrapping,” in Proceedings of the IEEE Information Theory Workshop (IEEE Press, Piscataway, N.J., 2001), pp. 9–11.
- S. M. Aji, G. B. Horn, R. J. McEliece, “Iterative decoding on graphs with a single cycle,” in Proceedings of the IEEE International Symposium on Information Theory (IEEE Press, Piscataway, N.J.), p. 276.
- G. Winkler, Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction (Springer, New York, 2003).
- H. Elliot, H. Derin, R. Cristi, D. Geman, “Application of the Gibbs distribution to image segmentation,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE Press, Piscataway, N.J., 1984), Vol. 9, pp. 678–681.
- A. Minagawa, K. Uda, N. Tagawa, “Region extraction based on belief propagation for Gaussian model,” in Proceedings of the International Conference on Pattern Recognition (IEEE Computer Society Press, Los Alamitos, Calif., 2002), Vol. 2, pp. 507–510.
- J. S. Lim, Two-Dimensional Signal and Image Processing (Prentice Hall, Englewood Cliffs, N.J., 1990).
- M. Wainwright, T. Jaakola, A. Willsky, “Tree-based reparameterization framework for approximate estimation of stochastic processes on graphs with cycles,” (Laboratory for Information and Decision Systems, MIT, Cambridge, Mass., 2001).

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

### Figures

Fig. 1 |
Fig. 2 |
Fig. 3 |

Fig. 4 |
Fig. 5 |
Fig. 6 |

Fig. 7 |
Fig. 8 |
Fig. 9 |

Fig. 10 |
Fig. 11 |
Fig. 12 |

Fig. 13 |
Fig. 14 |
Fig. 15 |

Fig. 16 |
Fig. 17 |
Fig. 18 |

« Previous Article | Next Article »

OSA is a member of CrossRef.