Параллельные реализации алгоритмов нахождения зеркальной симметрии бинарных растровых изображений

Abstract

Оценка симметричности фигур является важным этапом анализа бинарных изображений и может применяться для решения многих прикладных задач компьютерного зрения, таких, например, как анализ условий произрастания растений, билатеральной симметрии насекомых. Известные алгоритмы поиска оси зеркальной симметрии позволяют найти лишь приближенное решение данной задачи, как правило, не предоставляя возможности оценить качество полученного решения. Естественным способом оценки качества в данном случае является сравнение с точным решением - эталонной осью симметрии, мера симметричности изображения относительно которой имеет максимальное значение. В данной работе исследуется точный метод поиска такой эталонной оси симметрии, основанный на полном переборе всех потенциально возможных осей и оценке симметричности фигуры с использованием теоретико-множественного подобия Жаккарда, применяемого к подмножествам пикселей фигуры при делении ее осью. Алгоритм полного перебора гарантированно находит эталонную ось симметрии, но требует весьма значительного времени на обработку каждого изображения. Для достижения скорости, позволяющей работать с большими базами изображений, была разработана параллельная версия данного алгоритма, которая была реализована на языке C++ с применением технологии параллельного программирования MPI и протестирована с использованием ресурсов суперкомпьютерного комплекса МГУ имени М.В. Ломоносова. Экспериментальные исследования на базе изображений «Бабочки» показали, что предложенный алгоритм позволяет найти эталонную ось симметрии за время, приемлемое для обработки баз, состоящих из сотен и тысяч изображений, что сделало возможным его применение для автоматической разметки баз изображений, а также отладки и тестирования на них предложенных ранее авторами приближенных процедур поиска оси симметрии. Разработанная параллельная версия одного из приближенных алгоритмов обеспечивает возможность решения прикладных задач анализа изображений в условиях, близких к режиму реального времени, позволяя достичь времени обработки, исчисляемого в долях секунды даже на обычных многоядерных персональных компьютерах, сохраняя при этом максимальное, либо близкое к максимальному качество решения.