МОРФОЛОГИЧЕСКИЕ СИСТЕМЫ и АНАЛИЗ ИЗОБРАЖЕНИЙ

Что такое морфология?

СПОСОБЫ - эвристики, эксперименты
НАУКА
МЕТОДЫ - математические

Что такое морфология?

Термин: Морфология – (1) «наука о форме»;
(2) методы анализа

Формальная морфология

ϑ

Λ

M ⊆ ϑ

ε

δ

ϕεδ = δε

множество образов

множество описаний

модельное
множество

Морфологическая сегментация ε:

Сегментация + Реконструкция

множество образов

множество описаний

<5,6,8>
<1,0,1,0,0>
<2,0,0,1,0,…>

Искусственный
изоморфизм

Естественный
гомоморфизм

568=5×102+6×101+8×10
40=1×25+1×23
28=22 × 71
f(x)

Пример 1. Морфологический анализ Пытьева Сравнение по форме, выделение отличий

─

=

─

=

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

Морфологический анализ Пытьева

A1

A2

A3

A4

Индикаторная функция множества Ai

Значение яркости(интенсивности) пикселя с координатами

Морфологический анализ Пытьева

Проекция изображения на форму

Изображение , определенное на поле

Морфологический анализ Пытьева

α = arccos ku, β = arccos km

Нормированный
коэфициент корреляции
Морфологический
коэффициент корреляции:
0

Морфологический анализ Пытьева

Пример 2. Математическая морфология Серра Обработка с учетом формы, выделение деталей

Математическая морфология Серра

B

BT

T

Структурирующий элемент Исходный образ

Трансляция

Opening (открытие)

Closing (закрытие)

XoB =

Математическая морфология Серра

Трансляция A по z:
Az = {y| a∈A, y=a=z}.
Сложение

Математическая морфология Серра

ММ-операторы:

ММ-проекторы:

Эрозия (сжатие)

Дилатация (расширение)

ММ-открытие

ММ-закрытие

ММ-фильтрация

Учет формы путем выбора структурирующих элементов:

Математическая морфология Серра

Пример 3. Бинарная морфология на базе скелетов

A

Фигурой называется связная замкнутая

Бинарная морфология на базе скелетов

ПРОЕКТИВНОСТЬ

Проекторы как распознающие операторы (М. Павель)

Структурный фильтр: процедура преобразования образа к виду,

Сравнение форм по сложности (Пытьев)

M1

M2

M3

M3 ⊆ M2 ⊆ M1

Морфологическая сложность:

Морфологический спектр (Maragos)

r

∂ || A o D(r) || / ∂r

монотонное

АЛГЕБРА ИЗОБРАЖЕНИЙ

Морфологические алгебры

Общие особенности рассмотренных методов

Проектор в алгебраическом смысле
Проекция образа

Морфологические алгебры

Пример. Проективные морфологии на базе методов интерполяции

Интерполяционные многочлены
Пусть на отрезке

Пример. Проективные морфологии на базе методов интерполяции

Проективная морфология на базе

Пример. Проективные морфологии на базе методов интерполяции

Кусочно-линейная интерполяция функции на

Пример. Проективные морфологии на базе методов интерполяции

Морфология на базе кусочно-линейной

Пример. Проективные морфологии на базе методов интерполяции

Вид опорной функции L(xi,yi,x,y) =

Пример. Проективные морфологии на базе методов интерполяции

Проективная морфология на базе

Пример. Проективные морфологии на базе методов интерполяции

Морфологический коэффициент корреляции:
K(g,f) =

Пример. Проективные морфологии на базе методов интерполяции

Сравнение по форме: Проекция

Пример. Проективные морфологии на базе методов интерполяции

Сравнение по форме: Проекция

Пример. Проективные морфологии на базе методов интерполяции

Форма двумерной функции

Вычисление интерполяционной проекции

Пример. Проективные морфологии на базе методов интерполяции

Сравнение по форме двумерных функций

Примеры

ПРОСТРАНСТВО РАЗЛОЖЕНИЙ

Проективные морфологические разложения

Проективные морфологические разложения
Использование морфологических разложений образов в качестве признаковых

Проективные морфологические разложения

Типы морфологических разложений
Условие разложимости:
∃ E⊆Ω: Pr(A,E) = Vk=1..n(Pr(A,Ek)) =

Проективные морфологические разложения

Ортогональные морфологии на базе БПФ и т.п.

БПФ, ДКП, фильтры

Проективные морфологические разложения

Проективные морфологические разложения Морфологический анализ изображений

Переход от образов к изображениям (двумерным

Проективные морфологические разложения Морфологический анализ изображений

Фильтрация изображений с использованием разложений:

Проективные морфологические разложения Морфологический анализ изображений

Структурное сравнение изображений (обобщение методики Ю.П.

Проективные морфологические разложения Конструирование алгоритмов обнаружения объектов

Обнаружение объектов с использованием разложений:

Проективные морфологические разложения Морфологические операторы сегментации и сжатия данных

Морфологическая сегментация на

Проективные морфологические разложения Проективная сегментация без потерь

Морфология Пытьева «форма» Пытьева

Морфология Серра

МОДУЛЬНОСТЬ (в поисках нетривиального описания)

Формальная морфология

ϑ

Λ

M ⊆ ϑ

ε

δ

ϕεδ = δε

множество образов

множество описаний

модельное
множество

Морфологическая сегментация ε:

Способ описания: Преобразование Хафа и GHT

Голосование точек в аккумулятор

Анализ аккумулятора

Параметризация:

Обобщение:

НТ

GНТ

Пространство параметров

Модульные проективные морфологии

Монотонные проективные морфологии на базе преобразования Хафа и GHT

H-открытие - объединение

Морфологическая фильтрация на базе рекуррентного преобразования Хафа в скользящем окне
Вычислительно-эффективная реализация алгоритма.
(a) (b)

МОДУЛЬНОСТЬ (комбинирование процедур)

Альтернативные модульные морфологии

Идея: Построение различных модульных морфологических операторов путем комбинирования

Селективные морфологии

(a)

(b)

(c)

(a)

(b)

(a)

(a)

Открытие MM

(a)

(a)

O(Object)=

∅, if E(Object) = ∅ (a)

Object’⊆Object, if E(Object)=∅

Селективные морфологии

Im

E(Im)

O(Im)

Im-O(Im)

Полутоновое
MM-открытие

Селективные морфологии

Полутоновое
SM-открытие

Im

E(Im)

SO(Im)

Im-SO(Im)

Селективные морфологии

Im

D(Im)

C(Im)

Im-C(Im)

Полутоновое
MM-закрытие

Селективные морфологии

Im

D(Im)

SC(Im)

Im-SC(Im)

Полутоновое
SM-закрытие

Селективные морфологии

Полутоновое
MM-открытие

Im

E(Im)

O(Im)

Im-O(Im)

Селективные морфологии

Полутоновое
SM-открытие

Im

E(Im)

SO(Im)

Im-SO(Im)

Селективные морфологии

Полутоновое
MM-закрытие

Im

D(Im)

C(Im)

Im-C(Im)

Селективные морфологии

Полутоновое
SM-закрытие

Im

D(Im)

SC(Im)

Im-SC(Im)

Селективные морфологии

Im

E1D(Im)

SO1D(Im)

Im-SO1D(Im)

Контурная селективная морфология
(на базе оператора удаления заданного числа концевых точек)

МОРФОЛОГИЧЕСКИЙ АНАЛИЗ НА БАЗЕ КРИТЕРИЕВ (сегментация с регуляризацией)

Критерии в классических морфологиях
Морфология Пытьева:
Pr(A,M(B)) = argminC∈M(B) || A -

Критериальная морфология:
Модель: M(λ): Λ→[0,1] ⇔ M(L):ϑ→[0,1]
Критерий соответствия:
K(E,λ): ϑ×Λ→[0,1] ⇔ K(E,L): ϑ×ϑ→[0,1]
Критериальный

Морфологическое решение задач анализа данных:
1. Фильтрация ϕФ(E)=δ(λ):
2. Сегментация εФ(E)=λ:
Ф(E,λ)=K(E,δ(λ))×M(λ)→max(λ∈Λ)
3. Распознавание cФ(E)=H:
Ф(E,λ,H)=K(E,δ(λ))×M(λ,H)×M(H)→max(λ∈Λ,H∈Θ)
4.

Нечеткие модели: [0,1]
Максимум достоверности:
Ф(A,L)=K(A,L)×M(L)→max(L∈Ω)
Вероятностные модели: [0,1]
Максимум апостериорной вероятности
ψ(A)=L: P(A,L)=P(A/L)×P(L)→max(L∈Ω).
Четкие или логические

Регуляризация

Ф(A,L) = J(A,L) → min(L∈F(x))

x

f(x)

Регуляризация

Ф(A,L) = J(A,L) → min(L∈F(x))

x

f(x)

Регуляризация

Ф(A,L)=J(A,L)+α×Q(L)→min(L∈F(x))

x

f(x)

Регуляризация ⇒ сегментация с потерями

Ф(A,L)=J(A,L)+α×Q(L)→min(L∈F(x))

x

f(x)

Критериальные проективные морфологии

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

Стандартный критерий штрафа
Ф(A,B)= J(A,B) + χ(A,B) + α×Q(B)
где J(A,B) – критерий

Морфологический спектр по параметру

r

∂ || A o D(r) || / ∂r

монотонное

Морфологический спектр по сложности

α

Sp(A,α) = ∂ || Pr(A,J,Q) || / ∂α

монотонное

Достаточные условия построения проективных операторов
Ф(A,B)= J(A,B) + χ(A,B) + α×Q(B)

Критериальные проективные

Алгоритмические аспекты морфологии (от математического зрения к компьютерному)

Среднеквадратичная проективная сегментация одномерных функций

Пример СКО-фильтрации. Исходная функция, результаты сегментации для α=500 и

Монотонная проективная фильтрация одномерных функций

Примеры применения операторов DP-Open (α=200) и DP-Close(α=200).

Примеры

Монотонная проективная сегментация одномерных функций

Примеры применения операторов DP-Open: Исходная функция, DP-Open

Монотонная фильтрация и сегментация двумерных кривых (контуров бинарных изображений)

Пример кусочно-линейной

Монотонная фильтрация и сегментация двумерных кривых (контуров бинарных изображений)

Пример кусочно-линейной

Морфологии на базе сопоставления функций
1D-Matching:
g(x) = f(x+v(x)) + ξ
J(f(x),g(x),L(x))=J(f(x),g(x+L(x))).
2D-Matching:
g(x,y) = f(x+vx(x,y),y+vy(x,y))

Морфология на базе оптимальной кусочно-линейной интерполяции
Ф(f,L) = -J(L) + χ(f,L)

Морфология на базе оптимальной кусочно-линейной интерполяции
a) b) c)
a – исходная

Морфология на базе оптимальной кусочно-линейной интерполяции двумерных кривых (контуров бинарных изображений)

д) α=1000

г) α=100

в) α=10

б) α=5

а) α=0

Морфология на базе оптимальной кусочно-постоянной сегментации

д) α=1000

г) α=100

в) α=10

б) α=5

а) α=0

Морфология на базе оптимальной кусочно-постоянной сегментации

Срезовый стек:

Оператор реконструкции срезового стека δ:

Морфологическая фильтрация с использованием стековых

г)

в)

б)

а)

з)

ж)

е)

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

д)

Стековое свойство элементов срезовой цепи изображения:
а)

Оператор уменьшающей срезовой фильтрации:

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

Дерево срезовых сегментов:

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

1. Морфологический фильтр, сохраняющий структуру стекового дерева

2. Морфологический фильтр с

з) α=10000000, n=1.

ж) α=1000000, n=2;

е) α=100000, n=4;

д) α=10000, n=12;

Морфологическая фильтрация с

з) α=10000000, n=1.

ж) α=1000000, n=1;

е) α=100000, n=4;

д) α=10000, n=12;

г) α=1000, n=32;

в)

з) α=10000000, n=1.

ж) α=1000000, n=3;

е) α=100000, n=8;

д) α=10000, n=24;

г) α=1000, n=120;

в)

з) α=10000000, n=1.

ж) α=1000000, n=2;

е) α=100000, n=12;

д) α=10000, n=38;

г) α=1000, n=156;

в)

НЕПРОЕКТИВНЫЕ МОРФОЛОГИИ МОРФОЛОГИЧЕСКИЙ АНАЛИЗ СВИДЕТЕЛЬСТВ (от математического зрения к компьютерному)

Основной современный подход к задаче обнаружения и распознавания – обнаружение и

ХЧ

Точки

Углы, соединения линий, точки высокой кривизны градиента яркости, центр тяжести области,

Характерные черты на изображении имеют следующие виды атрибутов:
Положение: Концы отрезка, центр

Примеры атрибутов характерных черт

‘.’ - близость;
‘!’ - коллинеарность;
‘=‘ - параллельность;
‘L’- перпендикулярность;

Присутствие/плотность: наличие данных ХЧ на всех используемых изображениях, достаточная плотность ХЧ

Пример автоматического обнаружения зданий с летательного аппарата
исходное изображение

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

Контурный препарат

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

Выделение характерных черт - областей

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

Выделение первичных линеаментов

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

Выделение крупных и/или параллельных линеаментов

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

Фильтрация по размеру

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

Поиск П-образности

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

Окончательная 2D-модель

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

Межкадровое соответствие

Окончательная модель

Морфологический анализ свидетельств

Вероятностная интерпретация методов морфологического анализа изображений
Вероятностная модель формирования образа
P(M): Ω→[0,1],
Вероятностная

Морфологический анализ свидетельств

Вероятностное обобщение понятия проективности
При вторичном применении оператора максимально вероятной

Морфологический анализ свидетельств

Признаки как достаточные статистики. Независимые признаки
 Набор признаков: f(A)=∈Ψn,
Критерий

Морфологический анализ свидетельств

Анализ морфологических свидетельств
Морфологическое событие:
e(p)={f(A,p)=e∈X}.
Морфологическая гипотеза:
h(q)={ψ(A) = L(q)}.
Модель голосования:
P(E(A),h(q))=Πp∈X, P(e(p),h(q))→max(h(q)),
где

Морфологический анализ свидетельств

Анализ морфологических свидетельств
Под анализом морфологических свидетельств понимается
следующая процедура:
Морфологические события

РАЗРАБОТКА ВЫЧИСЛИТЕЛЬНО ЭФФЕКТИВНЫХ АЛГОРИТМОВ АНАЛИЗА МОРФОЛОГИЧЕСКИХ СВИДЕТЕЛЬСТВ (от математического зрения к

Способы повышения вычислительной эффективности:
•  независимое аккумулирование свидетельств
•  декомпозиция вектора параметров S(θ)=S'(θ')∙S"(θ")

Иерархический анализ свидетельств. Теорема разделения

Морфологический анализ свидетельств

Последовательность шагов разработки алгоритма
обнаружения и идентификации объектов
1.  описать модели объекта, регистрации и

Пример. Метод обнаружения штриховых кодов и текстовых областей на изображениях

Пример. Метод обнаружения штриховых кодов и текстовых областей на изображениях

Обнаружение штриховых

ρ

Параметризация:

Голосование точек в аккумулятор

Параметризация

x cosθ + y sinθ = ρ

ПРЕОБРАЗОВАНИЕ ХАФА

x

y

x

y

ϴ

ρ

ϴ

ρ

ϴ0

ρ0

.

Достоинства:

Идея модифицированного преобразования Хафа

Метод выделения штриховых и текстовых строк в пространстве

АВТОМАТИЗИРОВАННОЕ КОНСТРУИРОВАНИЕ МОРФОЛОГИЧЕСКИХ АЛГОРИТМОВ (от математического зрения к компьютерному)

Автоматизированное конструирование алгоритмов обнаружения объектов Постановка задачи

P1(R,A) → min(R,A) | P2(R,A)

Автоматизированное конструирование алгоритмов обнаружения объектов

1. Метод автоматизированного конструирования алгоритмов обнаружения объектов,

Автоматизированное конструирование алгоритмов обнаружения объектов Конструирование детекторов по модельным описаниям

Формальное описание

Метод преобразования модельных описаний
Модель объекта:
Преобразования моделей:
перестановка порядка предикатов; ,
декомпозиция (разбиение)

Пример преобразования модельных описаний
Модели: Штриховая линия = набор штрихов, лежащих на одной

Пример преобразования модельных описаний Рекурсивная модель (M2):
Штрих_линия(X)=лежать_на_прямой(х) рядом(х,у)Штрих_линия(Х\х);
Штрих_линия({х})=лежать_на_прямой(х). После перестановки предикатов:
Штрих_линия(X)=лежать_на_прямой(х) Штрих_линия(Х\х) рядом(х,у);
Штрих_линия({х})=лежать_на_прямой(х). После

Алгоритм применения построенной модели процедуры голосования:
1.  Осуществить все возможные успешные индексации

Проективные морфологии на базе неоднородных структурных моделей, описываемых логическими предикатами
Утверждение

Принцип конструирования процедуры идентификации
Множество процедур обнаружения:
, где - процедура обнаружения фрагмента,

Задача условной оптимизации:
,
где: - время работы процедуры на изображениях из

Схема применения генетического алгоритма:
1.     Ген = одна из элементарных процедур.
2.     Хромосома

Схема применения генетического алгоритма для формирования морфологических детекторов:
1.     Ген = один

Интерпретация результата:
1.     Процедурная интерпретация = Близкая к оптимальной процедура обнаружения заданного

РАЗНООБРАЗИЕ МОРФОЛОГИЧЕСКИХ СИСТЕМ

- Проективные / непроективные
- Модульные / унитарные
- Алгебраические / критериальные
- Монотонные

Типы описаний, используемых в анализе изображений

Ф(A,λ)=K(e(A),δ(λ))×M(λ)→max(λ∈Λ).

Выбор ℑ(ℜ)={ϑ,Λ,δ,K,M} определяет конкретную морфологическую систему.
Возникает нечто вроде систематической таблицы методов

ПРИМЕР ИСПОЛЬЗОВАНИЯ ТАБЛИЦЫ
Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Основная

Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Пусть дан образ B

Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Примеры проекции фигуры

Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Проекция на класс

Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Проекция на класс

Морфологическое сравнение бинарных изображений на базе их скелетных представлений

Инвариантные проекции на

Спасибо за внимание!