Детальная информация

Название: Разработка алгоритма сборки пазла: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_04 «Биоинформатика»
Авторы: Гумерова Альбина Дмитриевна
Научный руководитель: Козлов Константин Николаевич
Другие авторы: Арефьева Людмила Анатольевна
Организация: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Выходные сведения: Санкт-Петербург, 2020
Коллекция: Выпускные квалификационные работы; Общая коллекция
Тематика: минимальное остовное дерево; генетический алгоритм; расстояние махаланобиса; сумма квадратов разностей; minimal spanning tree; genetic algorithm; mahalanobis distance; sum of squared differences
Тип документа: Выпускная квалификационная работа бакалавра
Тип файла: PDF
Язык: Русский
Уровень высшего образования: Бакалавриат
Код специальности ФГОС: 01.03.02
Группа специальностей ФГОС: 010000 - Математика и механика
Ссылки: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2020/vr/vr20-1389
Права доступа: Доступ по паролю из сети Интернет (чтение, печать, копирование)
Ключ записи: ru\spstu\vkr\8284

Разрешенные действия:

Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети Действие 'Загрузить' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети

Группа: Анонимные пользователи

Сеть: Интернет

Аннотация

Данная работа посвящена рассмотрению двух алгоритмов сборки пазлов с квадратными фрагментами без перекрытий, использующих только значения цветов пикселей на краях фрагментов: жадный алгоритм, основанный на нахождении минимального остовного дерева, и генетический алгоритм, вдохновленный механизмами естественного отбора. Задачи, которые решались в ходе исследования: 1. Изучение и реализация жадного алгоритма сборки пазлов, основанного на поиске минимального остовного дерева. 2. Изучение и реализация генетического алгоритма для сборки пазлов. 3. Рассмотрение каждого подхода с двумя функциями сравнения различности фрагментов пазла: сумма квадратов разностей и функция, основанная на расстоянии Махаланобиса. 4. Сравнение двух рассматриваемых подходов. Для работы с первым алгоритмом пазл интерпретируется как граф, в котором необходимо найти минимальное остовное дерево, используя алгоритм Краскала. Генетический же алгоритм находит оптимальное расположение фрагментов пазлов среди пространства всех возможных решений путем случайного подбора, комбинирования и перестановок искомых параметров. Каждый алгоритм был запрограммирован на языке С++ и проведен их сравнительный анализ. Сравнение проводилось по точности на наборе данных из 1800 пазлов с различным числом фрагментов трех размеров и временной сложности алгоритмов. В результате был определен выбор подхода для решения различных пазлов. При необходимости решения пазлов, состоящих из небольшого количества фрагментов, оба рассмотренных подхода дают хороший результат, достигнутая точность составила 89%. При решении пазлов из большого количества фрагментов маленького размера стоит остановить свой выбор на генетическом алгоритме с функцией, основанной на расстоянии Махаланобиса.

This paper is devoted to the development of a genetic algorithm with optimization and comparison with greedy algorithm. This work introduces two algorithms for square-piece image jigsaw puzzles without overlapping that only using information of the pixel value on the border line of the pieces: the first is greedy algorithm based on finding minimum spanning tree and the second one uses genetic algorithm which was inspired by natural selection mechanisms. In this paper were solving the following tasks: 1. Studying and implementing a greedy puzzle assembly algorithm based on finding the minimum spanning tree. 2. Studying and implementing a genetic algorithm. 3. Consideration of each approach with two functions for comparing the differences of puzzle pieces: the sum of the squared differences and a function based on the Mahalanobis distance. 4. Comparing two algorithms. In In the first approach we interpret the puzzle as a graph in which we need to find for a minimum spanning tree. The genetic algorithm searches the optimum piece arrangement in large optimization space by random search, combination and rearrangement of the desired parametres. Other contributions of the paper include two pieces dissimularity measure functions: sum of squared differences and the function based on Mahalanobis distance. Each of approaches was programmed in C++ and analyzed. A comparison for accuracy was made on 1800 pictures dataset with different number of pieces of three sizes. Also, a time complexity comparison was made. As a result, we determine the way to choose algorithm in different cases. If it is necessary to solve puzzles consisting of a small number of fragments, both approaches considered give a good result, the achieved accuracy was 89%. When solving puzzles from a large number of small fragments, it is worth choosing a genetic algorithm with a function based on the distance of the Mahalanobis.

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Интернет Авторизованные пользователи СПбПУ Прочитать Печать Загрузить
-> Интернет Анонимные пользователи

Оглавление

  • Тема выпускной квалификационной работы
    • 1. Постановка задачи
    • 2. Описание методов
    • 3. Программная реализация
    • 4. Результаты
    • Список использованных источников

Статистика использования

stat Количество обращений: 11
За последние 30 дней: 0
Подробная статистика