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

Метод исключения избыточных ограничений в задаче восстановления тела по измерениям его опорной функции

Авторы

  • И.А. Палачев

Ключевые слова:

опорная функция
восстановление геометрических тел
линейное программирование
квадратичное программирование
теневой контур
преобразование двойственности

Аннотация

Предложен новый алгоритм восстановления тел по измерениям их опорных функций, который представляет собой алгоритм квадратичного или линейного программирования в форме Гарднера-Кидерлена с меньшим числом ограничений. Уменьшение числа ограничений достигается за счет нового метода, который позволяет исключить из исходной системы ограничений часть ограничений как избыточные. Предложен новый подход, позволяющий применять методы восстановления тел по измерениям опорной функции к задаче восстановления тел по теневым контурам. Представлено описание реализации алгоритма, а также результаты его тестирования на реальных промышленных теневых контурах. Предложенный метод в рассмотренном примере позволил сократить число ограничений на 80% и ускорить исходный алгоритм Гарднера-Кидерлена на порядок.

Новые вычислительные технологии

Загрузки

Опубликован

2015-07-03

Выпуск

Том 16 (2015): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

И.А. Палачев

Московский государственный университет имени М.В. Ломоносова,
механико-математический факультет
Ленинские горы, 119899, Москва
• аспирант

Библиографические ссылки

  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.