A method of redundant constraint elimination in the problem of body recovery based on support function measurements

Authors

DOI:

https://doi.org/10.26089/NumMet.v16r334

Keywords:

support function, geometric bodies recovery, linear programming, quadratic programming, shadow contour, duality transformation

Abstract

A new body recovery algorithm based on support function measurements is proposed. The proposed algorithm represents a linear or quadratic programming problem in Gardner-Kiderlen form with smaller number of constraints. The reduction of constraint number is based on a new method that allows one to eliminate a part of initial constraints as redundant. A new approach of body recovery based on shadow contours is proposed. It allows one to reuse body recovery methods based on support function measurements. The implementation of the algorithm is described and some results of its testing on real industrial contours are discussed. The proposed method ensures the reduction of constraint number by 80% in the discussed example and also enables to speedup the initial Gardner-Kiderlen algorithm by an order of magnitude.

Author Biography

I.A. Palachev

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics
• PhD Student

References

  1. P. K. Ghosh and K.V. Kumar, “Support Function Representation of Convex Bodies, Its Application in Geometric Computing, and Some Related Representations,” Comput. Vis. Image Underst. 72 (3), 379-403 (1998).
  2. J. L. Prince and A. S. Willsky, “Reconstructing Convex Sets from Support Line Measurements,” IEEE Trans. Pattern Anal. Mach. Intell. 12 (4), 377-389 (1990).
  3. A. S. Lele, S. R. Kulkarni, and A. S. Willsky, “Convex-Polygon Estimation from Support-Line Measurements and Applications to Target Reconstruction from Laser-Radar Data,” J. Opt. Soc. Am. A 9 (10), 1693-1714 (1992).
  4. W. C. Karl, S. R. Kulkarni, G. V. Verghese, and A. S. Willsky, “Local Tests for Consistency of Support Hyperplane Data,” J. Math. Imaging Vis. 6 (2-3), 249-267 (1996).
  5. J. Gregor and F. Rannou, “Least-Squares Framework for Projection MRI Reconstruction,” Proc. SPIE, Vol. 4322 (2001).
    doi 10.1117/12.431168
  6. J. Gregor and F. R. Rannou, “Three-Dimensional Support Function Estimation and Application for Projection Magnetic Resonance Imaging,” Int. J. Imaging Syst. Technol. 12 (1), 43-50 (2002).
  7. R. J. Gardner and M. Kiderlen, “A New Algorithm for 3D Reconstruction from Support Functions,” IEEE Trans. Pattern Anal. Mach. Intell. 31 (3), 556-562 (2009).
  8. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Springer, New York, 1985).
  9. B. Chazelle, “An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra,” SIAM J. Comput. 21 (4), 671-696 (1992).
  10. R. J. Gardner, M. Kiderlen, and P. Milanfar, “Convergence of Algorithms for Reconstructing Convex Bodies and Directional Measures,” Ann. Statist. 34 (3), 1331-1374 (2006).
  11. A. Guntuboyina, “Optimal Rates of Convergence for Convex Set Estimation from Support Functions,” Ann. Statist. 40 (1), 385-411 (2012).
  12. The Computational Geometry Algorithms Library.
    http://www.cgal.org . Cited June 8, 2015.
  13. S. Hert and S. Schirra, “3D Convex Hulls,” CGAL User and Reference Manual.
    http://doc.cgal.org/4.5.2/Manual/packages.html . Cited June 8, 2015.
  14. P. Alliez, S. Tayeb, and C. Wormser, “3D Fast Intersection and Distance Computation (AABB Tree),” CGAL User and Reference Manual.
    http://doc.cgal.org/4.5.2/Manual/packages.html . Cited June 8, 2015.
  15. C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls,” ACM Trans. Math. Softw. 22 (4), 469-483 (1996).
  16. GLPK (GNU Linear Programming Kit).
    http://www.gnu.org/software/glpk/glpk.html . Cited June 8, 2015.
  17. CLP, COIN-OR Linear Programming Solver.
    https://projects.coin-or.org/Clp . Cited June 8, 2015.
  18. Ipopt, COIN-OR Interior Point OPTimizer.
    https://projects.coin-or.org/Ipopt . Cited June 8, 2015.
  19. IBM ILOG CPLEX Optimizer.
    http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/. Cited June 8, 2015.
  20. A. W{854chter and L. T. Biegler, “On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming,” Math. Program. 106 (1), 25-57 (2006).
  21. The HSL Mathematical Software Library.
    http://www.hsl.rl.ac.uk/. Cited June 8, 2015.
  22. OpenBLAS. An Optimized BLAS Library.
    http://xianyi.github.io/OpenBLAS . Cited June 8, 2015.
New computational technologies

Downloads

Published

03-07-2015

How to Cite

Палачев И. A Method of Redundant Constraint Elimination in the Problem of Body Recovery Based on Support Function Measurements // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2015. 16. 348-359. doi 10.26089/NumMet.v16r334

Issue

Vol. 16 (2015): Issue 3.

Section

Section 1. Numerical methods and applications