Распознавание образов методом декомпозиции форм (1187425), страница 2

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

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

Определение M_ε(O) и C(O) основано на теории Морса. Она имеет 2 основные операции. Первая – построение функция Морса f : M → R, которая может рассматриваться как проекция на выбранное направление. Вторая – п остроение графа Риба.

Рис.3 Рис.4

Граф Риба подковы Измерение вогнутости двух точек

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

Осталось разобраться с понятием вогнутости и дать формальное определение «приблизительности» выпуклой декомпозиции.

Определение 6. Для двух точек p₁ и p₂ формы O кривую их соединяющую и лежащую внутри O назовем путем между p₁ и p₂. Все пути соединяющие p₁ и p₂ обозначим C(p₁, p₂).

Очевидно, что количество путей в C(p₁, p₂) может быть бесконечным. Для каждого пути вводится понятие вогнутости. Пусть точка p принадлежит пути С, соединяющем p₁ и p₂ и пусть f(p₁) ≥ f(p₂), тогда:

На рисунке 4 С₁, С₂ и С₃ – пути между точками p₁ и p₂, при этом .

Вогнутость для 2 точек p₁ и p₂ – минимум меры вогнутости среди всех путей соединяющих p₁ и p₂:

Вогнутость же части P – максимум вогнутости случайных двух точек из P:

M_ε(O) – слишком большое, поэтому чтоб уменьшить сложность, будем рассматривать M_ε(O) ни как множество пар мьютексных множеств точек.

Определение 7. Если для двух непересекающихся множеств A и B существует мьютексная пара точек, состоящая из точки из A и точки из B, то множества A и B называются мьютексным: A ≈ B.

Теперь можно дать определение максимальной и минимальной вогнутости для двух мьютексных множеств.

Е сли , то мьютексная пара множеств может быть проигнорирована. Если же , то каждая пара точек из A и B формируют мьютексную пару, вес которой не меньше . Теперь нашей задачей является нахождение множеств точек A и B: , и также найти разрезы которые их разделят. Зная граф Риба это очень легко сделать. Так как он показывает изменения количества связных компонент, то два соседних множества и являются мьютексной парой. Разрезы же, которые их разделяют, и есть разрезы-кандидаты.

Рис. 5.

На рисунке 5 два множества A и B – мьютексная пара. В то же время два кандидатныых разреза – оба разделяют A и B. Очевидно, что .

Таким образом, мы нашли M_ε(O) и C(O).

Кратко алгоритм приблизительной декомпозиции можно записать следующим образом:

1. Выбираем множество направлений, считаем функцию Морса.

2. for каждой функции Морса do

   1. строим граф Риба

   2. считаем мьютексные пары и добавляем их в мьютексное множество

   3. считаем кандидатные разрезы и добавляем их в множество кандидатных разрезов

end

1. for каждого разреза в множестве кандидатных разрезов do

for каждой пары в мьютексном множестве do

Проверяем удовлетворяет ли разрез мьютексной паре

end

end

1. Решаем задачу линейного программирования (3)

2. Выбираем решающие разрезы, основываясь на их стоимости.

П римеры декомпозиции:

В столбце A показаны входные формы; в столбце B – графы Риба, построенные по высотной функции вдоль вертикали; С – результат декомпозиции; D – граф выпуклости формы.

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

Данный метод основан на анализе поведения границы формы, а точнее на особенностях её изменения при переходе между частями. Важным аспектом является то, что выделенные части последовательно удаляются и дальнейшая декомпозиция идет без их участия. Выделают 3 типа частей: «шея», «конечность» и «отрез».

Рис.6.

Анализ проходит на основании скелета сглаженной локальной симметрии (Smoothed Local Symmetries - SLS). Представим головку машины, которая последовательно скользит по осям такого скелета. Таким образом, форма – это объединение ребер, соединяющих симметричные точки границы формы, с центром на оси.

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

Рис.7

Будем рассматривать отрезок с концами и , где и –параметрические положения кривой. Длина отрезка , а его направление . Касательные в этих точках соответственно обозначим и . Обозначим угол между и p как , а угол между p и как , где . Тогда полный угол поворота это .

Рис.8

Ниже будет показано, что величина связности равна . На рисунке 8 показано изменение связности при последовательном движении по оси симметрии формы. Также показано, что по характеру изменения R можно судить о виде части (Рис.6).

Частично касательной назовем окружность , которая касательна к границе формы в точке и проходит через точку . Её радиус (см. Рис.7). Теперь мы можем определить частные производные по и :

	(6)
	(7)

– кривизна кривой . Далее нам будут важны следующие величины:

(8)

Также необходимо формализировать понятие асимметрии . – разница между углами . А точнее: .

Определение 8. Две точки и асимметричны, если .

Из определения следует, что движение симметричной пары точек по скелету сглаженной локальной симметрии перпендикулярно градиенту асимметрии . Рассмотрим малый шаг вдоль оси. При этом смещение симметричной пары будет и соответственно. Поэтому . Для симметричной пары , : две частично касательные окружности совпадают друг с другом (бикасательная окружность) и мы можем связать и :

(9)

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

Шаг можно разбить на две составляющие: перпендикулярную и параллельную :

(10)

Обычно не равен нулю, а и в большой степени компенсируют друг друга, поэтому . Следовательно, параллельной составляющей можно пренебречь. Поэтому с учетом (6): и:

(10)

П ерейдем теперь к понятию связности границ поверхности:

Определение 9. Пусть и – две границы поверхности, и – их продолжения. Тогда две границы называются связными, если и пересекаются и их смежный угол пересечения острый.

В [3] вводится мера связности, как , где – это любая сглаживающая кривая, соединяющая и . В нашем варианте параметризации прямой .

Мы можем найти изменение связности при движении вдоль SLS на малый шаг . С учетом (8) и того что мы получаем и

(11)

где и .

Можно сделать вывод, что изменение связности определяется средней нормированной величиной кривизны в симметричных точках. Также заметим, что знак не зависит от направления . Далее видим, что вторая производная пропорциональна связности:

(12)

Резкое изменение является индикатором переходной области. Однако эта величина зависит от масштаба изображения, поэтому определим величину силы перехода:

Определение 10. Локальной силой перехода симметричной пары назовем величину .

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

Определение 11. Полной силой перехода между частями называется величина изменения связности в переходной области:

,

где – отрезок оси с .

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

На рисунке ниже можно видеть эксперименты с варьированием пороговых величин и (под каждым изображением записана величина ).

На следующем рисунке показаны изменения связности и силы перехода для элемента формы.

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

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

В этом разделе рассмотрим предложенный мною метод декомпозиции.

Как известно, скелетом фигуры называется множество центров всех её максимальных пустых кругов. В [1] рассматривается ещё одно определение скелета, основанное на понятии дистанционной функции формы. Дистанционная функция для каждой внутренней точки формы задает «глубину» ее расположения относительно границы, равную расстоянию от этой точки до границы фигуры. Дистанционная функция строится последовательным обходом всех внутренних точек формы, начиная со «слоя» точек максимально близких к границе. Пройдя один слой полностью, мы переходим на следующий слой внутрь формы. Визуализация результата представлена на рисунке ниже:

Рис.9. Начальная форма и её глубинная функция

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

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

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

Рис.10. Исходное растровое изображение (а), минимальный разделяющий многоугольник и его скелет (б), последовательная стрижка ребер (в)-(д).

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

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