A First Order Predicate Logic Formulation of the 3D Reconstruction Problem and its Solution Space

Robinson, M., Kubik, K. and Lovell, B. (2005) A First Order Predicate Logic Formulation of the 3D Reconstruction Problem and its Solution Space. International Journal of Pattern Recognition and Artificial Intelligence, 19 1: 45-62. doi:10.1142/S0218001405003910

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
ijprai2003.pdf ijprai2003.pdf application/pdf 558.36KB 55

Author Robinson, M.
Kubik, K.
Lovell, B.
Title A First Order Predicate Logic Formulation of the 3D Reconstruction Problem and its Solution Space
Journal name International Journal of Pattern Recognition and Artificial Intelligence   Check publisher's open access policy
ISSN 0218-0014
Publication date 2005-01-01
Sub-type Article (original research)
DOI 10.1142/S0218001405003910
Open Access Status File (Author Post-print)
Volume 19
Issue 1
Start page 45
End page 62
Total pages 18
Editor P. Shen Pei Wang
X. Jiang
Place of publication Singapore
Publisher World Scientific Publishing Co. PTE LTD
Collection year 2005
Language eng
Subject C1
280207 Pattern Recognition
280208 Computer Vision
700199 Computer software and services not elsewhere classified
Abstract This paper defines the 3D reconstruction problem as the process of reconstructing a 3D scene from numerous 2D visual images of that scene. It is well known that this problem is ill-posed, and numerous constraints and assumptions are used in 3D reconstruction algorithms in order to reduce the solution space. Unfortunately, most constraints only work in a certain range of situations and often constraints are built into the most fundamental methods (e.g. Area Based Matching assumes that all the pixels in the window belong to the same object). This paper presents a novel formulation of the 3D reconstruction problem, using a voxel framework and first order logic equations, which does not contain any additional constraints or assumptions. Solving this formulation for a set of input images gives all the possible solutions for that set, rather than picking a solution that is deemed most likely. Using this formulation, this paper studies the problem of uniqueness in 3D reconstruction and how the solution space changes for different configurations of input images. It is found that it is not possible to guarantee a unique solution, no matter how many images are taken of the scene, their orientation or even how much color variation is in the scene itself. Results of using the formulation to reconstruct a few small voxel spaces are also presented. They show that the number of solutions is extremely large for even very small voxel spaces (5 x 5 voxel space gives 10 to 10(7) solutions). This shows the need for constraints to reduce the solution space to a reasonable size. Finally, it is noted that because of the discrete nature of the formulation, the solution space size can be easily calculated, making the formulation a useful tool to numerically evaluate the usefulness of any constraints that are added.
Keyword Computer Science, Artificial Intelligence
3d Reconstruction
Solution Space
reconstruction algorithms
References 1. Simon Baker, Terence Sim, and Takeo Kanade. When is the shape of a scene unique given its light-field: a fundamental theorem of 3d vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(1), January 2003. 2. A.F. Bobick and S.S. Intille. Large occlusion stereo. IJCV, 33(3):1-20, September 1999. 3. J. De Bonet and P. Viola. Roxels: Responsibility weighted 3D volume reconstruction. In Proceedings of the 7th IEEE International Conference on Computer Vision (ICCV-99), volume I, pages 418-425, Los Alamitos, CA, September 20-27 1999. IEEE. 4. W. Bruce Culbertson, Thomas Malzbender, and Gregory G. Slabaugh. Generalized voxel coloring. In Workshop on Vision Algorithms, pages 161-169, 1999. 5. C. R. Dyer. Volumetric scene reconstruction from multiple views. In L. S. Davis, editor, Foundations of Image Analysis. Kluwer, 2001. 6. Oliver Grau and Ralf Tnjes. Knowledge Based Modelling of Natural Scenes. In European Workshop on Conbined Real and Synthetic Image Processing for Broadcast and Video Production, November 1994. 7. J. Hsu, Z. Pizlo, C. Babbs, D. Chelberg, and E. Delp. Design of studies to test the effectiveness of stereo imaging, truth or dare: is stereo viewing really better. In Proc. SPIE 1994, vol. 2177, pages 211-220, 1994. 8. S.S. Intille and A.F. Bobick. Disparity-space images and large occlusion stereo. In ECCV94, pages 179-186, 1994. 9. S.S. Intille and A.F. Bobick. Incorporating intensity edges in the recovery of occlusion regions. In ICPR94, pages A:674-677, 1994. 10. Kiriakos Kutulakos and Steven Seitz. A theory of shape by space carving. International Journal of Computer Vision, 38(3):199-218, 2000. 11. Claus-E. Liedtke, O. Grau, and Stefan Growe. Use of explicit knowledge for the reconstruction of 3-d object geometry. In Computer Analysis of Images and Patterns, pages 580-587, 1995. 12. D. Marr and T.A. Poggio. Cooperative computation of stereo disparity. Science, 194(4262):283-287, October 15, 1976, October 1976. 13. Wojciech Matusik, Chis Buehler, Ramesh Raskar, Steven J. Gortler, and Leonard McMillan. Image-based visual hulls. SIGGRAPH, pages 369-374, 2000. 14. H. Saito and T. Kanade. Shape reconstruction in projective grid space from large number of images. In Proceedings of the IEEE Computer Science Conference on Computer Vision and Pattern Recognition (CVPR-99), pages 49-54, Los Alamitos, June 23-25 1999. IEEE. 15. S.M. Seitz and C.R. Dyer. Photorealistic scene reconstruction by voxel coloring. In CVPR97, pages 1067-1073, 1997. 16. Greg Slabaugh, Bruce Culbertson, Tom Malzbender, and Ron Schafer. A survey of methods for volumetric scene reconstruction from photographs. In VG2001, 2001. 17. Gregory G. Slabaugh, Tom Malzbender, and Bruce Culbertson. Volumetric warping for voxel coloring on an infinite domain. In SMILE2000, pages 109-123, 2000. 18. Ramin Zabih and John Woodfill. Non-parametric local transforms for computing visual correspondence. In ECCV (2), pages 151-158, 1994.
Q-Index Code C1

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Access Statistics: 247 Abstract Views, 55 File Downloads  -  Detailed Statistics
Created: Wed, 15 Aug 2007, 07:24:25 EST