Development of Applied Computer Vision Systems Using Projective Morphologies and Evidence-Based Image Analysis

Evidence-Based Image Analysis
Yury V. Vizilter viz@gosniias.ru
FGUP “State Research Institute of Aviation

in the field of avionics for flight vehicles of civil

“Technical Vision” laboratories:

Computer and Machine Vision Laboratory
Laboratory for Close-range Digital Photogrammetry
Laboratory for Long-range Digital Photogrammetry
Laboratory for Optic and Electronic Systems

About 60 developers (engineers and software engineers)
4 Doctors of Science, 8 Candidates of Sciences
More than 300 scientific publications in related area

More information about commercial products and projects: www.iitvision.ru

JSC “Institute of Information Technologies”:

www.gosniias.ru

design of vision algorithms. It’s a special way for thinking

деталей




MIN
эрозия
MAX
дилатация
MIN
эрозия
MAX
дилатация
реконструкция A
A
Serra J. Image Analysis and Mathematical

Исходный образ

B

A

BT

T

Трансляция

A

A

AB

Открытие: X○B = (XB)⊕B

Закрытие: X●B = (X⊕B)B

Сжатие AB

Расширение A⊕B

Базовые операции ММ

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

Исходное изображение

Трансляция

Opening

Closing

XoB = ∪{BT | BT⊆ X}

Форма = Комбинация “Struxels”

Морфологические фильтры как комбинация структурирующих элементов

Открытие

Закрытие

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





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

Комбинация Дисков
A = ∪p∈S(A) D(p, rA(p))
где
D(p,r) –

S(A)

Форма 2 = Комбинация “Aнкселей” (ANalitcal piCTure ELements)

L. Mestetskiy, A. Semenov. Binary image skeleton – continuous approach. Proceedings of the Third International conference on computer vision theory and applications (VISAPP 2008), V.1: 251-258, 2008.

сравнения изображений по форме:
Выделить связные области на изображении A.
Вычислить среднюю

A

B

B

C

форма A и С

форма

яркость

(реконструкция B)

пикселя с координатами (x, y) (функция изображения)
с1,…, с4 – яркости

X

X – поле зрения

Форма = Комбинация элементов-областей

Yu. Pyt’ev. Morphological Image Analysis. Pattern Recognition and Image Analysis. V.3. No1: 19-28, 1993.

Х
Форма изображения V(f) в виде множества
- интеграл яркостей по области

Проекция вектора g на плоскость V(f)

Определение коэффициентов ci*

Дифференцируя по ci, получим решение задачи в виде

- площадь области Ai

Проекция на Форму

= arccos km
Нормированный
коэфициент корреляции
Морфологический
коэффициент корреляции:
0 ≤ km ≤ 1
Km не зависит

>

Shape-Tessellation

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

with Projectors
- Projection to the Shape
- Projection = Segmentation +

Common Instruments

Common Aspects

соответствующему заданному классу форм.
Алгебраический проектор:
F(X)=F(F(X))
Геометрическая интерпретация:
Два способа описания класса:

Проектор –

M. Pavel, Fundamentals of Pattern Recognition. Marcel Dekker. Inc, New York, 1989.

сложность:
Если одно модельное множество целиком принадлежит другому,
то соответствующая форма

>

>

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

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

∪

>

>

∪

∪

Структурная сложность:
Чем больше элементов в модели, тем сложнее описание.

на размер объекта
X
rB
X◦rB
XrB

S(X◦B) – площадь открытия образа Х элементом B
Формальное определение морфологического

Maragos P. Pattern Spectrum, Multiscale Shape Representation. IEEE Trans.on pattern analysis, machine intelligence, Vol, II, No 7, July 1989.

и пиковые составляющие формы фигуры (Визильтер, Сидякин, 2010)

2010)

«кубиков»)

ε: ϑ → Λ
Морфологическая реконструкция

71


f(x)


a4 x4+a3 x3+a2 x2+a1 x+a0
Естественный
изоморфизм
Позиционные системы счисления
Разложение на простые

Аппроксимация полиномами

Methods, Means for Recognizing Complex Patterns. − U.S., Patent 3069654,

точке
Радиус-вектор в точке
Угол между градиентом
и радиус-вектором
ϕ



ϕ
ϕ
LUT: R(ϕ)
Ballard D. H. Generalizing

изображения A(p) на отдельные прямые линии: Pr(A(p),t) = MAXq∈Q(A(q,t)∙Pr(A(p),ϕ(p,q))) = MAXq∈Q(A(q,t)∙A(p)∙ϕ(p,q)),
где

путем комбинирования разных операторов сегментации с разными операторами реконструкции.

Пример: селективные

(a)
Object’⊆Object, if E(Object)=∅ (b)
Object, if ∃Im:O(Im)=Object

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

Object, if E(Object) ≠ ∅ (b)

SO(Object)=

Стандартная ММ

Селективная ММ

Открытие SM

Эрозия MM

ε

δ

δ′

точек)

1, если B⊆A
r(A,B) =

Pr(A,B)=∅

Например, для ММ Серра

B

A

Pr(A,B)=B

B

A

Projective space of patterns (images) is an algebraic system <Ψ, Ω, ∙, V, μ, Pr, E>, where Ψ is a set of scalars including 0 and 1; Ω is the set of patterns with “zero pattern” ∅; ‘∙’ is the multiplicative group operation of multiplication of scalars Ψ × Ψ → Ψ and a scalar by pattern multiplication Ψ × Ω → Ω; ‘V’ ∈ {‘+’, ‘×’, ‘∪’, ‘∩’, ‘∨’, ‘∧’, ‘min’, ‘max’, …} is the additive Abel semi-group of scalars fusion Ψ × Ψ → Ψ and patterns fusion Ω×Ω→Ω; μ is the norm of the pattern Ω → R (μ(A) = ||A||, ||∅|| = 0); set of basic patterns (primitives) E = {E1, …, En} is the basis of the morphological pattern decomposition. Let E will denote the corresponding morphological subspace E ⊆ Ω generated by the algebraic closing of basis E relative to‘∙,V’-combination. The operator of linear projection of pattern onto the pattern has a form
Pr(A,B) = r(A,B)∙B: Ω → B ⊆ Ω,
where r(A,B) ∈ Ψ is the coefficient of linear connection of A relative to pattern B.

признаковых описаний этих образов является обоснованным.
Отсюда и все полезные

= Vk=1..n(r(A,Ek)∙Ek)

фильтры НЧ, ВЧ
Вейвлет-преобразование и фильтры

(двумерным функциям):
Введем пространства параметров изображения P и разложения Q:
A→A(p); Ek→Ek(p)→ϕ(p,q);

Ю.П. Пытьева)
Структурный проектор = Морфологический фильтр, применяемый к образу A,

разложений:

на базе проективных разложений

Пытьева
Морфология Серра морфологический скелет


















Минимальное число областей
Минимальное число дисков
Полное писксельное

Полное дисковое представление

сегментация с потерями

и α=2000.
Морфологическая сегментация в 1D

DP-Close(α=200).
Примеры применения операторов DP-Open (α=1000) и DP-Close(α=1000).
Морфологическая сегментация в 1D

DP-Open (α=1000), DP-Open (α=50000)
Примеры применения операторов DP-Close: Исходная функция, DP-Close

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

кусочно-линейной сегментации типа «закрытие».








Морфологическая сегментация в 1,5D

кусочно-линейной сегментации типа «открытие».








Морфологическая сегментация в 1,5D

изображений)








Морфологическая сегментация в 1,5D
Ф(f,L) = -J(L) + α×Q(L) →

|A-B|2
L1-открытие: |A-B|, B≤A
L1-закрытие: |A-B|, A≤B
N –

TV - Суммарная длина контуров

D - Размер дескриптора

…

Q

J

Конкретный тип задачи

Exact maximum a posteriori estimation for binary images // Journal

1 (геометрическое)
Граф с циклическими связями
1D-Развертка по кривой Гильберта-Пеано
2D-Пиксельная решетка

Ациклический граф типа «цепь»

Срез – комбинация срезовых сегментов (областей)

Стековое отношение – отношение включения вышележащих сегментов в нижележащие сегменты

Стековое дерево – ациклический граф стековых отношений

Операция реконструкции функции:

сегмента

сегмента

сегмента

сегмента

сегмента

сегмента

сегментов
21 сегмент

сегментов
106 сегмента

и распознавание объектов, основанное на их структурированных яркостно-геометрических моделях.
Составление яркостно-геометрической

Схема модельного подхода к обнаружению объектов

робастные алгоритмы
голосования или
сопоставления (matching)

сцена

сенсоры

изображения

сегментация (выделение)
характерных черт

Неформальная
структурированная
яркостно-геометрическая
модель объекта

МОДЕЛЬНЫЙ ПОДХОД к построению эффективных процедур обнаружения объектов

образа
P(M): Ω→[0,1],
Вероятностная модель регистрации изображения
P(L/M): M→[0,1],
Вероятностная модель искажений
P(A/L): M×Ω→[0,1]
Критерий максимальной вероятности
P(A,L)=P(A/L)×P(L/M)×P(M)→max(L).
Оператор максимально вероятной

P(e(p),h(q))→max(h(q)),
где E(A) – совокупность морфологических событий или точнее совокупное морфологическое

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

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

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

строится экспертная вероятностная модель, описывающая связь между особенностями изображения (характерными чертами) и гипотезой о принадлежности объекта заданной яркостно-геометрической модели
вероятностная модель используется непосредственно в ходе низкоуровневого анализа изображения
каждая обнаруженная особенность изображения (ХЧ) рассматривается как событие, свидетельствующее в пользу гипотезы (ряда гипотез) о наличии и характеристиках искомого объекта (голосование в специальном аккумуляторном пространстве).

S(θ)=S'(θ')∙S"(θ")
•  редукция вектора параметров S(θ)→S'(θ')
•  загрубление модели объекта M → M'⊇M
•  иерархический

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

и искажений
2.  определить степень загрубления модели объекта
3.  осуществить

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

изображениях

изображениях
Обнаружение штриховых кодов. Постановка задачи
Модель объекта. Прямоугольная область плоскости, заполненная

Обнаружение штриховых кодов. Разработка алгоритма

1. Загрубление модели. Прямоугольная область плоскости (x1,у1, x2,у2, x3,у3, x4,у4) с высокой колинеарностью градиентов.
2. Загрубление и декомпозиция вектора параметров. Модель "четыре угла" преобразуется к модели "четыре прямые" (ρ1,θ,ρ2,θ+90°,ρ3,θ,ρ4,θ+90°). Отсюда декомпозиция модели на кодосодержащую полосу (ρ1,ρ2,θ) и положение в полосе (ρ3, ρ4).
3. Аккумулирование свидетельств. Голоса пикселей с высоким градиентом аккумулируются в двухпараметрическом пространстве Hough (ρ,θ) с учетом направления градиента.

пространстве Хафа
Исходное изображение и голосование с учетом направления градиента
Область с

Соответствующий аккумулятор пространства Хафа

MHT для обнаружения штриховых кодов и текстовых строк

1

2

3

4

1

2

3

4

Обрабатывается полутоновое изображение
2. Объекты поиска – полосы (группы прямых)
3. Голосуют точки с высоким модулем градиента яркости
4. Голосование с учетом направления градиента в точке
5. Анализ аккумулятора – поиск сигнала заданной формы

Особенности метода

x

y

ϴ

ρ

x

y

ϴ

ρ

based on marking line recognition
Own lane detection, car auto-orientation on

of horizontal segments
- Natural parametrisation (xTop,xBottom)
- Bundle of parallel 3D-lines,

marking lines are shown.

objects on the curved road surface

Recognition of possible situation:

1) Object

various distances (10-40m)
Determining 2-6 reference distances with high precision
Automated relative orientation

machine vision procedure
reconstruction of 3D coordinates of road points

estimation (m)
Object height (cm)
Method for 3D obstacle detection in stereo
Detection

P2(R,A) ≤ P2max, T(R,A) ≤ Tmax
P1 – вероятность необнаружения объекта;
P2

объектов, основанный на преобразованиях модельных описаний
Метод преобразования модельных описаний
Рекурсивные модели

описание моделей объектов.
Преобразование моделей объектов.
Перевод декларативного описания в процедурное (сопоставление

на две части и редукция (отсечение) одной из них.
Obj = {

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

одной прямой. (М1) Штриховая линия = прямая, состоящая из отдельных штрихов.

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

индексации целевого предиката на изображении.
2.  Удалить все голосующие элементы, не участвующие

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

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

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

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

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

Хромосома = последовательность генов ограниченной длины.
3.     Функция качества хромосомы:

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

один из возможных структурных примитивов, характеризуемый набором {Mk(u,qk),tk,qk}.
2.     Хромосома =

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

заданного объекта.
2.     Модельная интерпретация = Набор элементов структурной модели объекта,

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

are presented.
It is important that they provide both theoretical basis