ВВЕДЕНИЕ 5
1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 7
1.1. Предметная область 7
1.2. Обзор алгоритмов для решения задачи подсчета компонент связности9
1.3. Технологии реализации параллельности 11
2. ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ 14
2.1. Проектирование последовательного алгоритма 14
2.2. Реализация последовательного алгоритма 18
2.3. Проектирование параллельного алгоритма 20
2.2. Реализация параллельного алгоритма 21
3. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 24
3.1. Исходные данные для тестирования 24
3.2. Сравнение работы алгоритмов 25
ЗАКЛЮЧЕНИЕ 31
ЛИТЕРАТУРА
За последние десятки лет компьютерное зрение развилось из узкоспециализированного направления исследований, сфокусированных на решении прикладных задач, в независимый раздел в области искусственного интеллекта . На сегодняшний день компьютерное зрение сочетает в себе большое количество различных подходов к машинному обучению, линейные алгоритмы и нейросетевые технологии.
Стремительное развитие данной отрасли связано с технологическим прогрессом и широким распространением цифровых камер, способных снимать изображение в достаточном для большинства систем компьютерного зрения качестве.
Помимо этого, на развитие систем компьютерного зрения также повлияло повсеместное повышение мощностей персональных компьютеров, сделав более доступными для конечных пользователей технически требовательные программные продукты, в том числе, использующие параллельную реализацию .
В современных реалиях, когда количество ядер в процессорах персональных компьютеров, все большее число программных продуктов ориентируется на распараллеливание с целью оптимизации времени работы программ, а параллельные алгоритмы показывают себя лучше, чем более эффективные последовательные аналоги.
За последние годы, в связи с применимостью в различных прикладных областях, в области компьютерного зрения становится более востребованной задача подсчета количества схожих предметов на изображении, одним из решений которой является подсчет компонент связности в графе, представляющем изображение, или так называемая задача вычисления линейной вариации.
В данной работе предлагается параллельный метод решения задачи линейной вариации, не имеющий узкой специализации и применимый для решения широкого круга прикладных задач.
ЦЕЛЬ И ЗАДАЧИ РАБОТЫ
Целью данной работы является разработка и реализация параллельного алгоритма для вычисления линейной вариации.
Для достижения поставленной цели были вынесены следующие задачи:
1) осуществить обзор литературы и существующих решений;
2) реализовать последовательную версию алгоритма для вычисления линейной вариации;
3) реализовать параллельную версию алгоритма для вычисления линейной вариации;
4) провести численные эксперименты и оценку результатов.
СТРУКТУРА И ОБЪЕМ РАБОТЫ
Данная работа состоит из введения, четырех глав, заключения и библиографии. Объем работы составляет 33 страницы, объем библиографии - 20 источников.
СОДЕРЖАНИЕ РАБОТЫ
В первой главе рассматривается предметная область, в рамках которой выполняется данная работа. Помимо этого, глава содержит обзор существующих алгоритмов, предназначенных для достижения целей, схожих с целью данной работы.
Во второй главе приведены теоретические основы данной работы, а также описаны технологии, использованные для реализации параллельных вычислений.
Третья глава содержит полное описание проделанной работы по реализации параллельного алгоритма для вычисления линейной вариации.
Четвертая глава представляет собой описание проведенных вычислительных экспериментов, а также их результаты и оценку.
В заключении подытожены результаты работы и приводятся возможные направления ее дальнейшего развития.
В рамках данной работы был осуществлен обзор литературы и существующих решений, реализованы последовательная и параллельная версии алгоритма для вычисления линейной вариации, проведены численные эксперименты и оценены их результаты.
По итогам выполнения данных задач, поставленных ранее, можно сказать о выполнении и цели данной работы - разработки и реализации параллельного алгоритма для вычисления линейной вариации.
Дальнейшим направлением доработки должно стать улучшение масштабируемости, повышение эффективности и ускорения в работе реализованного алгоритма, создание специализированных программных инструментов, основанных на результатах данной работы.
