Классификация двумерных фигур с использованием скелетно-геодезических гистограмм толщин-расстояний
Ломов Н.А., Сидякин С.В., Визильтер Ю.В.

 

Московский государственный университет имени М. В. Ломоносова,
ФГУП «Государственный научно-исследовательский институт авиационных систем»

Аннотация:
В работе рассматривается задача классификации бинарных изображений двумерных фигур. При этом в качестве дескриптора формы фигуры предлагается использовать скелетно-геодезическую гистограмму толщин-расстояний. Дескрипторы формы, основанные на статистиках парных расстояний между точками фигуры, хорошо известны. Известно также, что гистограммы парных геодезических расстояний между точками фигуры обладают устойчивостью к гибким деформациям частей фигуры, при которых не нарушается топология фигуры и мало изменяется её локальная толщина. Предложенный новый дескриптор представляет собой совместную гистограмму скелетно-геодезических расстояний и разностей локальных толщин между точками фигуры. Такая статистика является более информативной за счёт использования дополнительной информации о локальной толщине фигуры. Кроме того, предложенный подход к её вычислению на основе анализа рёбер непрерывного скелета и областей их притяжения позволяет значительно ускорить время расчёта по сравнению с гистограммами геодезических расстояний. Приведены результаты экспериментов, подтверждающих эффективность применения предложенного дескриптора в задачах классификации двумерных фигур.

Ключевые слова:
анализ бинарных фигур, классификация, непрерывные скелеты, скелетно-геодезические расстояния, гистограммы.

Цитирование:
Ломов, Н.А. Классификация двумерных фигур с использованием скелетно-геодезических гистограмм толщин-расстояний / Н.А. Ломов, С.В. Сидякин, Ю.В. Визильтер // Компьютерная оптика. – 2017. – Т. 41, № 2. – С. 227-236. – DOI: 10.18287/2412-6179-2017-41-2-227-236.

Литература:

  1. Местецкий, Л.М. Непрерывная морфология бинарных изображений. Фигуры, скелеты, циркуляры / Л.М. Местецкий. – М.: Физматлит, 2009. – 288 с. – ISBN: 978-5-922110-50-1.
  2. Chui, H. A new point matching algorithm for non-rigid registration / H. Chui, A. Rangarajan // Computer Vision and Image Understanding. – 2003. – Vol. 89, Issue 2-3. – P. 114-141. – DOI: 10.1016/S1077-3142(03)00009-2.
  3. Aslan, C. Disconnected skeleton: shape at its absolute scale / C. Aslan, A. Erdem, E. Erdem, S. Tari // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2008. – Vol. 30, Issue 12. – P. 2188-2203. – DOI: 10.1109/TPAMI.2007.70842.
  4. Bai, X. Path similarity skeleton graph matching / X. Bai, L. Latecki // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2008. – Vol. 30, Issue 7. – P. 1282-1292. – DOI: 10.1109/TPAMI.2007.70769.
  5. Belongie, S. Shape matching and object recognition using shape contexts / S. Belongie, J. Malik, J. Puzicha // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2002. – Vol. 24, Issue 4. – P. 509-522. – DOI: 10.1109/34.993558.
  6. Latecki, L. Shape similarity measure based on correspondence of visual parts / L. Latecki, R. Lakamper // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2000. – Vol. 22, Issue 10. – P. 1185-1190. – DOI: 10.1109/34.879802.
  7. Ling, H. Shape classification using the inner-distance / H. Ling, D. Jacobs // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2007. – Vol. 29, Issue 2. – P. 286-299. - DOI: 10.1109/TPAMI.2007.41.
  8. Felzenszwalb, P.F. Hierarchical matching of deformable shapes / P.F. Felzenszwalb, J.D. Schwartz // CVPR '07. IEEE Conference on Computer Vision and Pattern Recognition. –2007. – P. 1-8. – DOI: 10.1109/CVPR.2007.383018.
  9. Bronstein, A.M. Analysis of two-dimensional non-rigid shapes / M.M. Bronstein, A.M. Bruckstein, R. Kimmel // International Journal of Computer Vision. –2008. – Vol. 78, Issue 1. – P. 67-88. - DOI: 10.1007/s11263-007-0078-4.
  10. Sebastian, T.B. Recognition of shapes by editing their shock graphs / T.B. Sebastian, P.N. Klein, B.B. Kimia // IEEE Transactions on Pattern Analysis and Machine Intelligence. –2004. – Vol. 26, Issue 5. – P. 550-571. – DOI: 10.1109/TPAMI.2004.1273924.
  11. Siddiqi, K. Shock graphs and shape matching / K. Siddiqi, A. Shokoufandeh, S. Dickinson, S. Zucker // International Journal of Computer Vision. –1999. – Vol. 35, Issue 1. – P. 13-32. – DOI: 10.1023/A:1008102926703.
  12. Домахина, Л.Г. Скелетная сегментация и циркулярная морфология многоугольников: дис. … канд. физ.-мат. наук: 01.01.09 : защищена 16.05.2014 / Домахина Людмила Григорьевна. – М.: МГУ, 2013. – 149 с.
  13. Местецкий, Л.М. Медиальная ширина фигуры - дескриптор формы изображений / Л.М. Местецкий // Машинное обучение и анализ данных. – 2014. – Т. 1, № 9. – С. 1291-1318.
  14. Bai, X. Integrating contour and skeleton for shape classification / X. Bai, W. Liu, Z. Tu // IEEE 12th International Conference on Computer Vision Workshops (ICCV Workshops). –2009. – P. 360-367. – DOI: 10.1109/ICCVW.2009.5457679.
  15. Shen, W. Shape recognition by combining contour and skeleton into a mid-level representation / W. Shen, X. Wang, C. Yao, X. Bai // Proceedings of the 6-th China Conference on Pattern Recognition (CCPR). – 2014. – P. 391-400. – DOI: 10.1007/978-3-662-45646-0_40.
  16. Sun, K.B. Classification of contour shapes using class segment sets / K.B. Sun, B.J. Super // CVPR '05 Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition. – 2005. – Vol. 2. – P. 727-733. – DOI: 10.1109/CVPR.2005.98.
  17. Lafon, S. Diffusion maps and geometric harmonics / S. Lafon // PhD thesis. – Yale University, Dept. of Mathematics & Applied Mathematics, 2004.
  18. Coifman, R. Diffusion maps / R. Coifman, S. Lafon // Applied and Computational Harmonic Analysis. – 2006. – Vol. 21(1). – P. 5-30. – DOI: 10.1016/j.acha.2006.04.006.
  19. Osada, R. Matching 3D models with shape distributions / R. Osada, T. Funkhouser, B. Chazelle, D. Dobkin // SMI '01 Proceedings of the International Conference on Shape Modeling & Applications. – 2001. – P. 154-166. – DOI: 10.1109/SMA.2001.923386.
  20. Hamza, A.B. Probabilistic shape descriptor for triangulated surfaces / A.B. Hamza, H. Krim // IEEE International Conference on Image Processing. – 2005. – Vol. 1. – P. 1041-1044. – DOI: 10.1109/ICIP.2005.1529932.
  21. Wang, X. Bag of Contour Fragments for Robust Shape Classification / X. Wang, B. Feng, X. Bai, W. Liu, L.J. Latecki // Pattern Recognition. – 2014. – Vol. 47, Issue 6. – P. 2116-2125. – DOI: 10.1016/j.patcog.2013.12.008.
  22. Bai, X. Shape vocabulary: A robust and efficient shape representation for shape matching / X. Bai, C. Rao, X. Wang // IEEE Transactions on Image Processing. – 2014. – Vol. 23, Issue 9. – P. 3935-3949. – DOI: 10.1109/TIP.2014.2336542.
  23. Ломов, Н.А. Площадь дискового покрытия – дескриптор формы изображения / Н.А. Ломов, Л.М. Местецкий // Компьютерная оптика. 2016. – Т. 40, № 4. – С. 516-525. – DOI: 10.18287/2412-6179-2016-40-4-516-525.
  24. Sivic, J. Video google: A text retrieval approach to object matching in videos / J. Sivic, A. Zisserman // Proceedings of the 9-th International Conference on Computer Vision. – 2003. – Vol. 2. – P. 1470-1477. – DOI: 10.1109/ICCV.2003.1238663.
  25. Wang, J. Locality-constrained linear coding for image classification / J. Wang, J. Yang, K. Yu, F. Lu, T. Huang, Y. Gong // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). – 2010. – P. 3360-3367. – DOI: 10.1109/CVPR.2010.5540018.
  26. Сидякин, С.В. Разработка алгоритмов построения морфологических спектров для анализа цифровых изображений и видеопоследовательностей: дис. … канд. физ.-мат. наук: 05.13.17 / Сидякин Сергей Владимирович. – Москва: ВЦ РАН, 2013. – 163 с.
  27. Li, Y. A hierarchical shape tree for shape classification / Y. Li, J. Zhu, F. Li // 25th International Conference of Image and Vision Computing New Zealand. – 2010. – P. 1-6. – DOI: 10.1109/IVCNZ.2010.6148820.
  28. Lim, K.-L. Shape classification using local and global features / K.-L. Lim, H.K. Galoogahi // Fourth Pacific-Rim Symposium on Image and Video Technology (PSIVT). – 2010. – P. 115-120. – DOI: 10.1109/PSIVT.2010.26.
  29. Ozay, M. Compositional hierarchical representation of shape manifolds for classification of non-manifold shapes / M. Ozay, U.R. Aktas, J.L. Wyatt, A. Leonardis // IEEE International Conference on Computer Vision (ICCV). – 2015. – P. 1662-1670. – DOI: 10.1109/ICCV.2015.194.
  30. Johnson, D.B. Efficient algorithms for shortest paths in sparse networks / D.B. Johnson // Journal of the ACM. – 1977. – Vol. 24, Issue 1. – P. 1-13. – DOI: 10.1145/321992.321993.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20