Reconstructing Convex Sets from Support Line Measurements
April 1990 (vol. 12 no. 4)
pp. 377-389
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/34.50623
Algorithms are proposed for reconstructing convex sets given noisy support line measurements. It is observed that a set of measured support lines may not be consistent with any set in the plane. A theory of consistent support lines which serves as a basis for reconstruction algorithms that take the form of constrained optimization algorithms is developed. The formal statement of the problem and constraints reveals a rich geometry that makes it possible to include prior information about object position and boundary smoothness. The algorithms, which use explicit noise models and prior knowledge, are based on maximum-likelihood and maximum a posteriori estimation principles and are implemented using efficient linear and quadratic programming codes. Experimental results are presented. This research sets the stage for a more general approach to the incorporation of prior information concerning the estimation of object shape. [1] G. T. Herman,Image Reconstruction from Projections. New York: Academic, 1980.[2] P. L. Van Hove and J. G. Verly, "A silhouette-slice theorem for opaque 3-d objects," inProc. IEEE Int. Conf. Acoustics, Speech, Signal Processing, Mar. 26-29, 1985, pp. 933-936.[3] P. L. Van Hove, "Silhouette slice theorems," Ph.D. dissertation, Dep. Elec. Eng., Massachusetts Inst. Technol., Cambridge, MA, 1986.[4] J. L. Prince, "Geometric model-based Bayesian estimation from projections," proposal for Ph.D. research, Dep. Elec. Eng., Massachusetts Inst. Technol., Cambridge, MA, Apr. 1986.[5] D. J. Rossi and A. S. Willsky, "Reconstruction from projections based on detection and estimation of objects,"IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-32, pp. 886-906, 1984.[6] Y. Bresler and A. Macovski, "Estimation of 3-d shape of blood vessels from x-ray images," inProc. IEEE Comput. Soc. Int. Symp. Medical Images and Icons, 1984.[7] J. S. Schneiter, "Automated tactile sensing for object recognition and localization," Ph.D. dissertation, Dep. Mech. Eng., Massachusetts Inst. Technol., Cambridge, MA, 1985.[8] B. K. P. Horn,Robot Vision. Cambridge, MA: M.I.T. Press, 1986.[9] J. M. Humel, "Resolving bilinear data arrays," Master's thesis, Dep. Elec. Eng., Massachusetts Inst. Technol., Cambridge, MA, 1986.[10] F. P. Preparata and M. I. Shamos,Computational Geometry, an Introduction. New York: Springer-Verlag, 1985.[11] J. Greshak, "Reconstructing convex sets," Ph.D. dissertation, Dep. Elec. Eng., Massachusetts Inst. Technol., Cambridge, MA, 1985.[12] R. Cole and C. K. Yap, "Shape from probing,"J. Algorithms, vol. 8, no. 1, pp. 19-38, Mar. 1987.[13] S. S. Skiena, "Geometric probing," Ph.D. thesis, Dept. of Comput. Sci., Univ. of Illinois, Urbana-Champaign, Rep. no. UIUCDCS-R-88-1425, Apr. 1988.[14] H. Edelsbrunner and S. S. Skiena, "Probing convex polygon with X-rays,"SIAM J. Comput., vol. 17, no. 5, pp. 870-882, Oct. 1988.[15] L. A. Santalo,Integral Geometry and Geometric Probability. Vol. 1 of Encyclopedia of Mathematics and Its Applications. Reading, MA: Addison-Wesley, 1976.[16] P. J. Kelly and M. Weiss,Geometry and Convexity--A Study in Mathematical Methods. New York: Wiley, 1979.[17] M. Spivak,A Comprehensive Introduction to Differential Geometry, vol. 2. Berkeley, CA: Publish or Perish, 1979.[18] J. L. Prince and A. S. Willsky, "Estimation algorithms for reconstructing a convex set given noisy measurements of its support lines," M.I.T. Lab. Inform. Decision Syst., Cambridge, MA, Tech. Rep. LIDS-P-1638, Jan. 1987.[19] W. C. Karl, "Reconstructing dynamically evolving shapes from partial information," Ph.D. dissertation, Dep. Elec. Eng., Massachusetts Inst. Technol., Cambridge, MA, 1989.[20] H. Rademacher, "Uber eine funktionale ungleichung in der theorie der konvexen korper," inMathematische Zeitschrift. Berlin: Springer-Verlag, 1922.[21] R. Bellman,Introduction to Matrix Analysis. New York: McGraw-Hill, 1960, p. 56.[22] H. L. Van Trees,Detection, Estimation, and Modulation Theory, Vol. I. New York: Wiley, 1968.[23] A. H. Land and S. Powell,Fortran Codes for Mathematical Programming. London: Wiley-Interscience, 1973.[24] D. Goldfarb and A. Idnani, "A numerically stable dual method for solving strictly convex quadratic programs,"Math. Program., vol. 27, pp. 1-33, 1983.[25] D. G. Luenberger,Linear and Nonlinear Programming. Reading, MA: Addison-Wesley, 1984.
Index Terms:
fast Fourier transforms; computerised picture processing; multiframe estimation; trajectories estimation; frequency domain algorithm; multiframe detection; dim targets; moving targets; imaging sensors; directional filtering; detection probabilities; computerised picture processing; fast Fourier transforms; filtering and prediction theory; tracking systems
Citation:
J.L. Prince, A.S. Willsky, "Reconstructing Convex Sets from Support Line Measurements," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 4, pp. 377-389, Apr. 1990, doi:10.1109/34.50623
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb