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