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

Текст из файла

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Московский физико-технический институт

(государственный университет)»

Факультет управления и прикладной математики

Кафедра информатики

Распознавание образов методом декомпозиции форм

Выпускная квалификационная работа

(магистерская диссертация)

Направление подготовки:

03.04.01-Прикладная математика и физика (магистратура)

Выполнил:

студент 973 группы Бочаров Дмитрий Сергеевич

Научный руководитель:

к.ф. - м.н. Скороваров Константин Владимирович

Москва 2015

Оглавление

Введение 2

Основные понятия и постановка задачи 4

Алгоритмы декомпозиции 6

ACD (Approximate Convex Decomposition) – приблизительно выпуклая декомпозиция 6

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

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

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

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

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

Заключение 27

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

Введение

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

Изображение в компьютерном представлении – это прямоугольная матрица точек, обладающих определенным цветом и яркостью. Поэтому перед создателями систем обработки изображений возникает проблема преобразований формы изображений, при которой «человеческие», интуитивно понятные геометрические способы анализа, сравнения, распознавания и преобразования формы можно было бы применить к изображениям, представляемым в компьютере в виде матриц. Существует два пути решения этой проблемы: «дискретный» и «непрерывный». В «дискретном» способе решения предпринимаются попытки представить человеческие понятия формы, как непрерывного «сплошного» объекта, в виде дискретного растрового изображения. В «непрерывном» же способе строятся непрерывные модели для объектов, выделенных в дискретной матрице изображений, и далее строятся алгоритмы в терминах непрерывных моделей, близких к человеческому восприятию понятия формы. На самом деле эти 2 способа являются крайними, и чаще всего используется их комбинация.

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

Во введении будет представлена постановка задачи и даны основные определения. Далее рассматриваются основные уже существующие алгоритмы декомпозиции и предложен свой новый. Приведено их сравнение и причина выбора ACD (Approximate Convex Decomposition) алгоритма. Далее предлагается метод хеширования простых декомпозированных частей для их быстрого сравнения друг с другом. В конце представлены особенности реализации Web-интерефейса для работы с данными алгоритма и примеры декомпозиции и хеширования.

Основные понятия и постановка задачи

Бинарное изображение — это двухцветная картинка, на которой представлены один или несколько объектов одного цвета на фоне, имеющем другой цвет. Такие изображения представляются в компьютере в виде матрицы точек, каждая из которых может иметь лишь одно из двух значений цвета, условно обозначаемых через 0 или 1. Точки также называются пикселями (pixel — picture's element). He нарушая общности, будем считать бинарное изображение «черно-белым»: точки объекта являются черными (значение цвета равно 1), а точки фона — белыми (значение цвета равно 0).

Теперь дадим понятие формы. Так как мы работаем с двухмерным изображением, то все определения дадим применительно к евклидовой плоскости R².

Определение 1. Жордановой кривой называется образ окружности при непрерывном инъективном ее отображении в евклидову плоскость. Отображение инъективно, если любые две различные точки прообраза отображаются в две различные точки образа.

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

Таким образом, фигура в нашем понимании — это связная часть плоскости, ограниченная одной или несколькими замкнутыми линиями. Под это определение подходят сплошные объекты с конечным числом дыр.

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

А льтернативная модель основана на наблюдении за художниками, которые все значимые части представляют в виде эллипсов, в то время как параболические связки этих эллипсов считаются незначительными частями.

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

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

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

Алгоритмы декомпозиции

В данном разделе рассмотрены существующие алгоритмы декомпозиции форм, а также предложен свой.

ACD (Approximate Convex Decomposition) – приблизительно выпуклая декомпозиция

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

Определение 3. Для объекта О размерности n разрез – это пересечение (n - 1) –мерной гиперплоскости с O.

Таким образом, разрез удовлетворяет 2 критериям: 1) он лежит внутри объекта; 2) концы разреза лежат на границе формы.

Введем характеристики разреза и части формы:

• Стоимость разреза C, Cost(C), – действительное положительное число. Для его определения могут вводиться различные метрики, однако мы рассмотрим простой и интуитивно понятный вариант Евклидовой метрики. Cost(C) – длина разреза.

• Вогнутость части P, Concavity(P), – действительное положительное число, которое характеризует величину вогнутости части. О её формальном определении будет рассказано ниже.

Используя введенные понятия, можно дать формальное определение декомпозиции: разделить форму O на q частей, используя m разрезов, так чтобы суммарная стоимость m разрезов была минимальна и одновременно вогнутость каждой части не должна быть больше порогового значения ε.

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

О пределение 4. Точки p₁ и p₂ , принадлежащие форме O, называются мьютексными (взаимоисключающими), если O не содержит отрезок соединяющий p₁ и p₂. Обозначается как p₁ ≈ p₂.

Рис. 2

На рисунке 2 p₁ ≈ p₂ и p₁ ≈ p₄. Очевидно, что после декомпозиции p₁ и p₂ не могут быть в одной части. Таким образом, мьютексные точки являются ограничением выпуклой декомпозиции. Обычно результатом выпуклой декомпозиции является огромное число частей, с которыми тяжело работать, поэтому будем искать декомпозицию на примерно выпуклые части. Очевидно, что для приблизительно выпуклой декомпозиции p₁ ≈ p₂ и p₁ ≈ p₄ – различны. Определим меру вогнутости для мьютексной пары точек a и b: Concavity(a,b). При этом если форма O содержит отрезок, соединяющий a и b, то Concavity(a,b) = 0. Из это следует, что на рисунке 2: Concavity(p₁, p₂) > Concavity(p₁, p₄) > Concavity(p₁, p₃) = 0.

Определение 5. Для формы O ε-мьютексным множеством, M_ε(O), называется множество всех мьютексных пар, чей вес не меньше ε.

Введенное определение позволяет исключить мьютексные пары с малым весом.

Множество всех возможных разрезов формы O назовем кандидатным, C(O). Каждый разрез из C(O) может удовлетворять мьютексной паре из M_ε(O). То есть, чтобы выполнить приблизительно выпуклую декомпозицию нам надо выбрать такие разрезы из кандидатного множества C(O), которые удовлетворяют всем мьютексным парам из M_ε(O).

Пусть кандидатное множество C(O) = {cut₁ … cut_n} включает n разрезов, M_ε(O) = {mp₁ … mp_m} – m ε-мьютексных пар. Результат декомпозиции – множество индексов I, означающее, что если , то cut_i – решающий разрез. То есть каждому разрезу cut_i ставится в соответствие бинарная переменная x_i : . Каждому соответствует подмножество мьютексных пар, которым удовлетворяет этот разрез. То есть в M_ε(O) можео выделить n подмножеств мьютексных пар для каждого разреза. Для мьютексной пары среди всех разрезов, который ей удовлетворяют, должен быть хотя бы один, индекс которого принадлежит результирующему множеству I. То есть:

Пусть x = (x₁, x₂, …x_n)^T, c = (cost(cut₁), cost(cut₂), …, cost(cut_n))^T, A = {a_ij | I = 1 ... m, j = 1 ... n}, 1 = (1, 1, …, 1)^T, тогда задача (2) перепишется в задачу целочисленного линейного программирования:

Это NP-полная задача, однако мы можем ослабить условие на x_i:

(3) – задача линейного программирования. Решив её, мы получим приближенное оптимальное решение задачи (2). x_i может рассматриваться как вероятность выбора cut_i. После решения (3) мы можем последовательно выбирать разрезы, имеющие наибольшую вероятность, пока не удовлетворим все мьютексные пары из M_ε(O).

Для формы O, M_ε(O) и C(O) – настолько большие, что с ними не имеет смысла работать напрямую. Но многие мьютексные пары избыточны, то есть когда некоторые мьютексные пары удовлетворены, другие также автоматически удовлетворены. Далее будут показано, как избавиться от избыточных мьютексных пар и получить достаточно малое M_ε(O), а как уменьшить множество кандидатных разрезов C(O).

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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