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