Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Однако регуляризованный скелет не дает нужных нам точек максимума, а вернее дает целую их последовательность, среди которой нужно выделить «центры» будущих частей. Поэтому предлагается сгруппировать найденные максимумы дистанционной функции следующим образом.

1. Каждой точке присваиваем метку группы. Если точка не входит ни в какую группу ставим метку (-1).

2. Инициализируем текущий номер группы: group = 1.

3. for каждой точки do

if точке не присвоена метка группы then

1. присваиваем точке текущую метку группы

2. ищем другие точки, которые находятся на расстоянии меньшем, чем глубина рассматриваемой точки

3. присваиваем найденным точкам текущую метку

4. переходим в начало шага 3, но цикл осуществляется по найденным точкам

1. Для каждой группы ищем их геометрические центры

Найденные центры и будут центрами формирования частей. На рисунке ниже показан результат работы описанных шагов.

Следующим шагом является применение алгоритма водораздела с пиками в найденных нами точках.

Приоритет (высота) точек – это их глубина в нашей форме. Начиная с самых приоритетных точек, мы последовательно ставим самым близким к ним пикселям метку группы этой точки. Продолжаем это делать, удаляясь от самой приоритетной точки, и запоминаем, на какой глубине мы сейчас находимся. После проставления меток на очередном круге, мы пробегаем по всем остальным центрам, и если их глубина равна текущей, запускаем такую же операцию (водопоток) с этого центра. Для наглядности представлен рисунок с порядком выставления меток. Цветом обозначен индикатор группы.

В результате, всем пикселям формы присвоено какое-то цветовое значение, которое и является индикатором принадлежности к какой-либо части.

Примеры результатов декомпозиции:

Алгоритм хеширования

В данном разделе предлагается алгоритм хеширования, который в результате помог осуществлять быстрый поиск похожих декомпозированных частей. В следующем же разделе, опираясь на описанные особенности хеширования, мы выберем алгоритм декомопозиции.

Алгоритм хеширования декомпозированных частей должен удовлетворять следующим свойствам:

1. Хеш должен быть сравниваемым. То есть, зная хеши 2 форм, мы можем сказать, не только схожи ли эти формы, но и степень их близости.

2. Хеш не должен зависеть от масштаба формы

3. Хеш не должен зависеть от поворота формы.

В этом разделе под формой мы будем понимать простую форму, как одну из частей сложной декомпозированной формы. Первым шагом алгоритма является поиск центра масс формы. К примеру, для изображения размера N × N его можно найти по следующей формуле:

где

В [5] рассматриваются этот и другие методы поиска центроида в двухбитном изображении.

Далее для каждой точки границы формы считается расстояние до центра масс:

На рисунке изображен график расстояний до границы пятиугольника. Можно видеть на нем пять максимумов и пять минимумов, которые соответствуют вершинам и серединам сторон пятиугольника соответственно. Из этого замечания и следует основная идея алгоритма: следующим шагом считаем, сколько раз встречаются одни и те же расстояния от центра масс до границы. Иначе можно сформулировать вопрос, опираясь на график: сколько раз прямая, параллельная оси X пересекает график.

Однако для того, чтобы ответить на него, необходима предварительная обработка графика. Причиной снова являются «шумы» изображения и неровность границы, в том числе и из-за «растровости» изображения. Для устранения таких эффектов предлагается применить Рамера — Дугласа — Пекера к графику расстояний. Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, соединяющего первую и последнюю. Если точка находится на расстоянии, меньшем чем ε, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора, и получившаяся прямая сглаживает кривую с точностью не ниже ε. Если же расстояние больше ε, то алгоритм рекурсивно вызывает себя на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению). По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.

Чтобы результат хеширования не зависел от масштаба, отнормируем все расстояния, разделив на максимальное.

На рисунке изображена кривая расстояний после применения алгоритма Рамера — Дугласа — Пекера, а также график частоты пересечений прямой параллельной оси X. Для сравнения, ниже представлен график другого пятиугольника – большего по размеру, повернутого и немного видоизмененного. И сравним их с графиками других простых форм:

График зависимости частоты встречаемости расстояния от самого расстояния и предлагается взять за хеш. Свойства 2 и 3 мы выполнили при построении алгоритма. Осталось определить правила сравнения хешей. Предлагается мерой близости считать разницу площадей под графиками. Чем она меньше, тем более схожи фигуры.

Выбор алгоритма декомпозиции

К алгоритмам декомпозиции предъявлялись следующие требования в порядке убывания приоритета:

1. Декомпозиция должна совпадать с интуитивным восприятием формы человеком.

2. Части – результаты декомпозиции – должны легко хешироваться предложенным алгоритмом.

3. Скорость работы алгоритма должна быть высокой.

4. Простота реализации.

Глубинный метод.

Данный метод с уверенностью удовлетворяет 2-4 требованиям. При этом центр масс можно заменить уже найденными локальными максимумами удаленности от границы, а во многих случаях эти точки совпадут. Однако возникают проблемы с первым требованиям. Достаточно несложно придумать пример формы, при котором алгоритм не выделит части, которые интуитивно предполагаются. Для этого надо придумать форму, у которой будет один локальный максимум удаленности от границы, при этом были ответвления без подобных локальных максимумов. Примером может служить следующая форма звезды:

У неё один локальной максимум удаленности и следовательно один центр декомпозиции. При этом человек, скорее всего, интуитивно выделит части у этой формы – центр и конечности звезды.

Метод связности.

Этот алгоритм декомпозиции лучше других удовлетворяет первому требованию. При этом благодаря «эллиптичности» декомпозированных частей в них легко выделить центр масс и посчитать хеш. Однако алгоритм оказался очень сложен в реализации. Одна из основных проблем заключается в том, что форма представляется непрерывной в кривой, что сложно гарантировать.

Приблизительно выпуклая декомпозиция

Эксперименты показали, что данный алгоритм чаще всего декомпозирует форму на интуитивно понятные части. Второе требованием выполняется автоматически за счет выпуклости частей (или их приблизительной выпуклости, что легко настраивается варьированием параметра ε метода). То есть из любой точки (в том числе из центра масс формы) мы можем провести отрезок до другой точки формы (в нашем случае до её границы), и он будет лежать внутри формы. Также проводились эксперименты с производительностью данного алгоритма, при которых он хорошо себя показал, за счет возможности варьировать параметра декомпозиции, такие как ε «приблизтельность» декомпозиции.

Таким образом, выбор был сделан в пользу алгоритма приблизительно выпуклой декомпозиции.

Особенности реализации

Описанные алгоритмы были реализованы на языках Python и C++. Для демонстрации алгоритма глубинной декомпозиции и алгоритма хеширования был создан веб-сайт. На нем пользователь может загрузить черно-белое изображение и увидеть результат декомпозиции и распознавание декомпозированных частей с помощью сравнения их хешей.

Веб-сайт был написан с использованием фреймворка Django. Он позволяет удобно выделить все алгоритмы анализа изображений в отдельное приложение, что позволяет на ранних этапах работать с ними напрямую и быстро, и одновременно в нужный момент легко встроить их в MVC структуру фреймворка.

В качестве СУБД используется MySQL. Управлением запросов занимается Apache HTTP-сервер. В качестве посредника между сервером и Django выступает модуль mod_wsgi, который предоставляет WSGI-совместимый интерфейс для работы с web-приложениями, написанными на языке программирования Python. В роли серверной машины выступает облачный виртуальный сервер от провайдера DigitalOcean.

Для обработки изображений использовался пакет scikit-image. Реализация алгоритма приблизительно выпуклой декомпозиции была подготовлена при взаимодействии с Khaled Mamou, чья реализация алгоритма декомпозиции используется в таких крупных проектах 3D визуализации, как Unreal Engine 4.

Заключение

В данной работе были рассмотрены алгоритмы декомпозиции форм. Также был предложен новый метод декомпозиции. Проведено сравнение этих методов. Предложен способ хеширования простых 2-битных изображений для их быстрого сравнения. Реализованы все описанные алгоритмы, и представлен веб-интерфейс для их тестирования.

Следующим шагом является исследование способа хранения и быстрого поиска сложной формы целиком на основе хешей декомпозированных частей. Здесь наиболее сложной является задача сравнения графов декомпозиции с вершинами, имеющими характеристики в виде хешей.

Также планируется усовершенствовать веб-сайт. Будут добавлены новые методы декомпозиции форм и анализа изображений вообще.

Список литературы

[1] Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. – М.:ФИЗМАТЛИТ, 2009. – 288 с. – ISBN 978-5-9221-1050-1.

[2] Hairong Liu, Wenyu Liu, Longin Jan Latecki. Convex Shape Decomposition. IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2010.

[3] Manish Singh, Donald D. Hoffman. Completing visual contours: The relationship between relatability and minimizing inflections. Perception & Psychophysics 1999, 61 (5), 943-951

[4] Xiaofeng Mi, Doug DeCarlo. Separating Parts from 2D Shapes using Relatability. ICCV 2007: 1-8

[5] Zhang Hai-yan, Wang Dong-mu, Song Ke—ou. An improved fast algorithm for searching centroid of object in binary image. Proc. SPIE 5286, Third International Symposium on Multispectral Image Processing and Pattern Recognition, 859 (September 29, 2003); doi:10.1117/12.538711; http://dx.doi.org/10.1117/12.538711

Характеристики

Список файлов ВКР