Details

Title: Разработка алгоритма сборки пазла: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_04 «Биоинформатика»
Creators: Гумерова Альбина Дмитриевна
Scientific adviser: Козлов Константин Николаевич
Other creators: Арефьева Людмила Анатольевна
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Imprint: Санкт-Петербург, 2020
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: минимальное остовное дерево; генетический алгоритм; расстояние махаланобиса; сумма квадратов разностей; minimal spanning tree; genetic algorithm; mahalanobis distance; sum of squared differences
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Speciality code (FGOS): 01.03.02
Speciality group (FGOS): 010000 - Математика и механика
Links: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2020/vr/vr20-1389
Rights: Доступ по паролю из сети Интернет (чтение, печать, копирование)

Allowed Actions:

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Данная работа посвящена рассмотрению двух алгоритмов сборки пазлов с квадратными фрагментами без перекрытий, использующих только значения цветов пикселей на краях фрагментов: жадный алгоритм, основанный на нахождении минимального остовного дерева, и генетический алгоритм, вдохновленный механизмами естественного отбора. Задачи, которые решались в ходе исследования: 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.

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print Download
Internet Authorized users Read Print Download
-> Internet Anonymous

Table of Contents

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

Usage statistics

stat Access count: 3
Last 30 days: 1
Detailed usage statistics