Медведев Г.А., Морозов В.А. Практикум на ЭВМ по анализу временных рядов

Подождите немного. Документ загружается.

Определение порогового уровня. Рассмотрим гистограмму изображе-

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

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

ем p(z) = P

(z) + P

(z), где интенсивность z — случайная величина; P

и P

— априорные вероятности появления двух видов уравнения интенсивности на

изображении (светлого и темного); p

(z) и p

(z) — плотности вероятностей. Для

определения оптимального значения порога по интенсивности используется то

значение z = T , при котором P

(T ) = P

(T ). Если в качестве распределения

(z), p

(z) применяются гауссовские с математическими ожиданиями µ

, µ

дисперсиями σ

, σ

соответственно, то оптимальный порог T находится из урав-

нения

+ BT + C = 0, (7.24)

где

A = σ

− σ

; (7.25)

B = 2(µ

− µ

); (7.26)

C = σ

− σ

+ 2σ

. (7.27)

Определение оптимального порога можно осущест вит ь аналогичным образом в

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

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

Если изоб ражение имеет многомодальную гистограмму, представляемую в

виде суммы n функц ий плотности вероятности p(z) = P

p(z) + . . . + P

(z),

то задача оптимизации порогового уровня сводится к опред елению принадлеж-

ности данного пиксела к одному из n классов. Данный пиксел интенсивности z

принадлежит k-му классу, если P

(z) > P

(z), j = 1, . . . , n; j 6= k. Оптималь-

ный порог T

определяется из уравнения P

) = P

Возможность выбора “хорошего” порогового уровня существенно увеличи-

вается, если пики гистограмм являются высокими, узкими, симметричными и

разделены глубокими провалами. Одним из подходов к улучшению вида гисто-

грамм может быть рассмотрение только тех пикселов, которые лежат на границе

(или около нее) между объектами и фоном. Для этого можно использовать гра-

диент (

7.12) и лапласиан L[f (x, y)] =

∂

∂x

∂

∂y

. Для дискретных изображений

оператор Лапласа определяется следующим образом:

L[f(x, y)] = [f(x + 1, y) + f(x − 1, y) + f(x, y + 1) + f(x, y − 1)] − 4f (x, y).

Эти два оператор а можно использо ват ь для формирования трехуровневого об-

раза

s(x, y) =











0, G[f(x, y)] < T,

+, G[f(x, y)] ≥ T, L[f(x, y)] ≥ 0,

−, G[f(x, y)] ≥ T, L[f(x, y)] < 0,

180

где символы 0, “+”, “−” представляют три различных уровня освещенности, а T

— пороговый уровень. Предположим, что темный объект располагается на свет-

лом фоне, тогда применение данного преобразования дает образ S(x, y), в кото-

ром все пикселы, не лежащие на контуре, помечены 0, все пикселы на темной

стороне контура помечены “+”, на светлой — “−”. Таким образом, гистограмма

строится по значениям пикселов, помеченных “+” и “−”. Данная процедура мо-

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

1 соответствует искомым объектам, а 0 — фону.

Областно-ориентированная сегментация. Пусть R — область изобра-

жения. Рассмотрим сегментацию как процесс разбиен ия R на n подобластей

, R

, . . . , R

, так, что выполняются следующие условия:

i=1

= R;

2) R

— связная область, i = 1, 2, . . . , n;

3) R

∩ R

= ∅ для всех i и j, i 6= j;

4) P (R

) есть истина для i = 1, 2, . . . , n;

5) P (R

∪ R

) есть ложь для i 6= j,

где P (R

) — логический предикат, определенный на точках из множества

; ∅ — пустое множество. Четвертое условие оп ред еляе т свойства, кото-

рым должны удовлетворять пикселы в сегментированной области. Например,

P (R

) =ИСТИНА, если все пикселы в R

имеют одинаковую интенсивность.

Рассмотрим два алгоритма областно-ориентированной сегме нтации: расши-

рение области за счет объединения пикселов; разбиение и объединение области.

Алгоритм 1. Расширение области сводится к процедуре группиро ван ия пик-

селов или подобластей в большие объединения. Простейшей из них является аг-

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

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

точкам соседних пикселов с похожими характеристиками (интенсивность, цве т).

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

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

в различные области в процессе расширения. Выбор множества, состоящего из

одной или н ескольких начальных точек, следует из постановки задачи. Напри-

мер, выбор наиболее ярких пикселов является естествен ным начальным шагом

в алгоритме процесса расширения области.

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

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

ряд произвольных непересекающихся облас тей и затем объединять и (или) раз-

бивать эти области с целью удовлетворения условий, сформулированных в на-

чале данной главы. Итеративный алгоритм может быть изложен следую щим

образом.

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

P . Один из способов сост оит в успешном разбиении площади образа на все мень-

шие квадратные области, так, что для каждой области R

, P (R

) =ИСТИНА.

181

Процедура начинается с рассмотрения всей области R. Если P (R) =ЛОЖЬ, об-

ласть разбивается на квадранты. Есл и для какого-либо квадранта P принимает

значение ЛОЖЬ, этот квадрант разбивает ся на подквадранты и т.д. После опе-

рации разбиения производится операция объединения областей, имеющих оди-

наковые свойства по предикату P .

Таким образом, процедура разбиения и объединения имеет следующий вид:

1) разбиение области R

, для которой P (R

) =ЛОЖЬ, на четыре непер е-

секающихся квадранта;

2) объедин ени е соседних обла стей R

и R

, для которых P(R

∪

∪R

) =ИСТИНА;

3) выход на останов, когда дальней шее объединение или разбиение невоз-

можно.

Лабораторная работа 29. Сегментация изображений

Цель работы. Выделить объекты на изображении, используя алгор итмы сег-

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

Порядок выполнения работы

Использовать все шесть цифровых изображений из лабораторной работы 25.

Задание 1. Отделить объект от фона на изображениях №1, 2, используя

для этого пороговое решающее правило. В качестве порога T выбрать порог,

вычисленный по уравнению (7.24). Предполагается, что изображения искаже-

ны гауссовским шумом с нулевым средним и ди спе рси ей σ

= 0,25. Поэтому

в формулах (7.25)—(7.27) следует положить µ

= 0, µ

= 1, σ

= σ

= 0,25,

= P

= 0,5.

Задание 2. Отделить объект от фона на изображениях №1, 2, используя

пороговое решающее правило. Порог находится по гистограмме (значение T ,

разделяющее пики гистограмм), которая строиться по пикселам, расположен-

ным на границе между объектом и фоном (пикселы, принимающие значения

“+” или “−” на трехуровневом образе s(x, y)).

Задание 3. Произвести сегментацию изображений №1, 2 с помощью а л-

горитма разбиения и объединения области. Присвоить значению предиката

P (R

) =ИСТИНА, если средний уровень яркости в этой области больше порога

T . В качестве порога T использовать порог из задания 2.

7.6. Специальные модели изображений

Пространственную статистическую зависимость между пикселами в двух-

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

Эти модели подразделяются на глобальные по признаку соотве тст вия множе-

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

признаку соответствия его ограниченной (локальной) части.

182

Локальные МСП характеризуют статистическую зависимость интенсивно-

сти изображения в точке (m, n) от значений интенсивности в с осед ни х точ-

ках, представляя интенсивност ь x(m, n) как линейную комбинацию значений

{x(m + k, n + l), (k, l) ∈ S} и аддитивного шума, где S — множество соседей, не

включающее точку (m, n). Два неэквивалентных способа взаимодействия между

отсчетами изображения приводят к двум классам локальных МСП : одновремен-

ных и условных АР моделей.

Одновременная АР модел ь является фундаментальной моделью класса ло-

кальных МСП. Если стационарное изображение {x(m, n), (m, n) ∈ Ω} определе-

но на бесконечной решетке Ω = {(m, n), −∞ ≤ m, n ≤ ∞}, то его одновременное

АР (ОАР) представление имеет вид

x(m, n) =

(k,l)∈S

x(m + k, n + l) + ξ(m, n), (7.28)

где ξ(m, n) — двухмерная последовательность независимых и одинаково рас-

пределенных значений шума с нулевым средним и дисперсией σ

; A = {a

k,l

;

(k, l) ∈ S} — вектор неизвестных коэффициентов модели. Множество соседей S

должно быть симметричным.

При выборке модели из класса локальных МСП, соответствующей некото-

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

из них связана с оценкой параметров модели при заданном множестве соседей,

а вторая — с определением типа модели, наил учши м способом согласующейся с

реальным изображением.

Реальное изображение можно рассматривать как конечный блок бесконечно-

го изображения, заданного на бесконечной решетке Ω. Параметры ОАР модели

на бесконечной решетке могут быть найдены с помощью МНК:

A =





(m,n)

Y (m, n)Y

∗

(m, n)





−1

(m,n)

Y (m, n)x(m, n); (7.29)

(m,n)

[x(m, n) −

∗

Y (m, n)]

Y (m, n) = col [x(m + k, n + l); (k, l) ∈ S], (7.30)

операция col (·) — операция развертки двухмерного множества (матрицы) в

вектор-столбец; M — размер квадрата и зоб ражения, заданного на решетке Ω.

Оценки, полученные с помощью МНК, в обще м случае являются асимптотиче-

ски со стоятельными и несмещенными для ОАР модели только с односторонним

множеством соседей S.

Разрешение проблемы сложности при рассмотрении вопроса о ценки па ра-

метров ОАР моделей осуществляется переходом к подклассу моделей на ко-

нечных решетках. Для таких моделей конечная решетка Ω

делится на два

183

подмножества: внутреннее Ω

и внешнее Ω

, так, что Ω

= {(m, n) |(m, n) ∈

∈ Ω

, (m + k, n + l) ∈ Ω

для (k, l) ∈ S}, Ω

= Ω

− Ω

. Тогда для конечного

изображения {x(m, n), (m, n) ∈ Ω

} вводится тороидальная ОАР модель:

x(m, n) =

(k,l)∈S

k,l

x(m + k, n + l) + ξ(m, n), (m, n) ∈ Ω

; (7.31)

x(m, n) =

(k,l)∈S

k,l

(m + k, n + l) + ξ(m, n), (m, n) ∈ Ω

, (7.32)

где

(m + k, n + l) =

x(m + k, n + l), если (m + k, n + l) ∈ Ω

x[(k ⊕ m − 1), (l ⊕ n − 1)], если (m + k, n + l) ∈ Ω

;

знак ⊕ означает суммирование по модул ю M + 1. Для гауссовского распределе-

ния отсчетов изображения оценки параметров ОАР модели на конечной решет -

ке определяются с помощью итерационной процедуры метода максимального

правдоподобия:

t+1

R −

ˆσ

−1

V −

ˆσ

, t = 0, 1, 2, . . . ; (7.33)

ˆσ

(m,n)∈Ω

[x(m, n) −

∗

Y (m, n)]

, t = 0, 1, 2, . . . , (7.34)

где

T =

(m,n)∈Ω

Y (m, n)Y

∗

(m, n);

U =

(m,n)∈Ω

Y (m, n)x(m, n);

R =

(m,n)∈Ω

∗

− C

∗

);

V =

(m,n)∈Ω

;

= col

cos

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

;

= col

sin

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

Начальное значение A

выбирается равным T

−1

U, суммирование проводится по

всем (m, n) ∈ Ω

184

Оценить коэффициенты ОАР модели можно также с использованием спек-

трального представления случайного поля

X(λ

, λ

) =

(m,n)∈Ω

x(m, n)

−i(mλ

+ nλ

)

. (7.35)

Данный спектр определяется на области

Ω

(λ

, λ

) |λ

= 2π

, 0 ≤ m

≤ M, j = 1, 2

Если Ω

распространить на всю численную решетку, то спектральная плотность

случайного поля задается соотношением

g(λ

, λ

) = M{

X(λ

, λ

) X(λ

, λ

)}, (7.36)

где черта сверху — символ комплексной сопряженности. Для спектральной плот-

ности ОАР модели получаем формулу

(λ

, λ

) =

1 −

(k,l)∈S

k,l

i(λ

k + λ

. (7.37)

Спектральное представление распределено по нормальному закону в каждой

точке (λ

, λ

), имеет нулевое математическое ожидание, и д ля различных то-

чек (λ

, λ

) спектральные представления статистически независимы. При этом,

как следует из (

7.36), дисперсией такого спектрального представления я вляе т-

ся спектральная плотность g(λ

, λ

). Таким образом, плотность в ероятностей

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

p(X(λ) |λ ∈

Ω) = (2π)

−M

λ∈

Ω

g(λ)

−1/2

exp

−

λ∈

Ω

|X(λ)|

/g(λ)

где λ = (λ

, λ

). Пусть z(λ) = |X(λ)|

p(z |g

) = (2π)

−M

λ∈

Ω

(λ) exp

−

λ∈

Ω

(Z(λ)/g

(λ))

. (7.38)

Функция Z(λ) = Z(λ

, λ

) может быть вычислена по реализации случайного

поля с п омощь ю формулы (7.35) для каждой пары (λ

, λ

) ∈

Ω. Параметры

ОАР модели могут быть оценены с помощью ММП:

ˆa

k,l

= arg max

k,l

p(Z |g

где p(Z |g

) определяются формулой (

7.38). Введем для удобства функцию

F (λ, A) соотношением g

(λ) = σ

/(1 − F (λ, A)). Упоряд оч им элементы множе-

ства S, присво ив им номера S = {s

(1)

, s

(2)

, . . . , s

(N)

}, s

(j)

= (k, l), и введем в

185

рассмотрение векторы A = (a

(1)

, . . . , a

(N)

)

∗

, B(λ) = (cos λ

∗

(1)

, . . . , cos λ

∗

(N)

)

∗

C(λ) = (sin λ

∗

(1)

, . . . , sin λ

∗

(N)

)

∗

, где λ

∗

s = λ

k + λ

l. Тогда функцию F(λ, A)

можно записать в форме F (λ, A) = 2A

∗

B(λ) − A

∗

(B(λ)B

∗

(λ) + C(λ)C

∗

(λ))A.

Логарифм функции правдоподобия принимает вид

ln p(Z |A) = −

ln 2π −

λ∈

Ω

(ln g(λ) + Z(λ)/g(λ)) =

= −

ln 2π −

λ∈

Ω

[ln σ

− ln (1 − F (λ, A)) +

Z(λ)

(1 − F (λ, A))].

Таким образом, неизвестные па рамет ры σ

и A спектральной плотности g(λ) по

ММП должны находиться как решение уравнения

ln σ

λ∈

Ω

Z(λ)

(1 − F (λ, A)) − ln (1 − F (λ, A))

→ min

, A

. (7.39)

По переменной σ

функция, стоящая в левой части (

7.39), являе тся гладкой и

выпуклой книзу, поэтому оценка σ

вычисляется следующим образом:

ˆσ

λ∈

Ω

Z(λ)(1 − F (λ, A)). (7.40)

Учитывая (

7.40) в (7.39), приходим к уравнению относительно вектора A

λ∈

Ω

ν∈

Ω

Z(ν)(1 − F (ν, A))

− ln (1 − F (λ, A))

= M

λ∈

Ω

ν∈

Ω

Z(ν)(1 − F (ν, A))

(1 − F (λ, A))

→ min

. (7.41)

Функция в левой части (7.41) является в общем случае многоэкстремальной,

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

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

локальные алгоритмы. Экстремальные значения па рамет ров A находятся из

уравнения

λ∈

Ω

1 − F (λ, A)

−

Z(λ)

ν∈

Ω

Z(ν)(1 − F (ν, A))

∂F (λ, A)

∂A

= 0. (7.42)

Обозначим B(λ)B

∗

(λ) + C(λ)C

∗

(λ) = H(λ), тогда (

7.42) записывается в виде

λ∈

Ω

1 − F (λ, A)

−

Z(λ)

ν∈

Ω

Z(ν)(1 − F (ν, A))

|B(λ) + H(λ)A|

= 0. (7.43)

186

Приведем простую итерационную процедуру поиска параметра A. Пусть

A(k) — оценка параметра A на k-м шаге, тогда

A(k + 1) =

λ∈

Ω

h³

− B(λ) +

Z(λ)

ν∈

Ω

Z(ν)(1 − F (ν, A(k)))

−

F (λ, A(k))

1 − F (λ, A(k))

(B(λ) + H(λ)A(k))

, k = 0, 1, . . . ,

где в качестве A(0) берется любая точка, обеспечивающая стационарность ОАР

модели, т.е. выполнение неравенства

(k,l)∈S

k,l

(0)| < 1.

При использовании подкласса условных АР моделей предполагается, что по-

рождающий их шум является коррелированным. Условно-марковская модель

(УМ) является одной из моделей данно го подкласса. Изображе ние , удовлетво-

ряющее УМ на бесконечной решетке, задается уравнением

x(m, n) =

(k,l)∈S

k,l

x(m + k, n + l) + ν(m, n), (7.44)

где множество соседей симметрично, т.е. a

k,l

= a

−k,−l

, (k, l) ∈ S; ν(m, n) — стаци-

онарная гауссовская шумовая последовательность, удовлетворяющая условиям

M{ν(m, n)} = 0,

M{ν(m, n), ν(k, l)} =







ρ, (m, n) = (k, l),

−a

m−k,n−l

ρ, (m − k, n − l) ∈ S,

0, в ос тальных случаях.

При задании УМ на конечной решетке используется, как для ОАР модели,

тороидальное пр едставление решетки. Для обеспечения стационарности моде-

ли должно выполняться условие 1 − 2A

∗

> 0, (m, n) ∈ Ω

, где A =

= col [a

k,l

, (k, l) ∈ S

]; Φ

= col {cos

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

}; мно-

жество S

является такой половиной множества соседей S, что S = S

∪

∩

= ∅,

= {(k, l) |(−k, −l) ∈ S

Оценка параметров УМ находится следующим образом:





Ω

Q(m, n)Q

∗

(m, n)





−1

Ω

Q(m, n)x(m, n), (7.45)

где Q(m, n) = col [x(m+k, n +l) +x(m−k, n−l), (k, l) ∈ S

]; Ω

— подмножество

множества Ω

. Данная оценка не является единственной, п оскольку суммирова-

ние по д руго му подмножеству Ω

= Ω

−Ω

дает другую оценку, которая может

отличаться от A

. МНК-оценка

МНК

модели (

7.6) аналогична оценке (7.45), но

суммирование производится по множеству Ω

187

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

на критерии Байеса. Использование байесовского подхода приводит к следую-

щему решению. Выбирается множество соседей S

∗

, если

∗

= arg min{J

}, (7.46)

где

−

(m,n)∈Ω

ln [1 − 2

∗

(r) +

∗

(r)

+ M

ln ˆσ

+ m

ln (M

)

; (7.47)

Q(m, n) = S

(r)S

∗

(r) + C

(r)C

∗

(r),

m,n

(r) = col

cos

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

m,n

(r) = col

sin

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

— количество точек на множестве соседей S

Для УМ реша ющее правило выбора множества соседей также имеет вид

(7.46), где

= −

(m,n)∈Ω

ln [1 − 2

∗

(r)] + M

ln ρ

+ m

ln (M

); (7.48)

m,n

(r) = col

cos

2π

[(m − 1)k + (n − 1)l], (k, l) ∈ S

— такая половина множества соседей S

, что S

= S

∪

, S

∩

= ∅,

= {(k, l) |(−k, −l)∈ S

Выбор модели из класса локальных МСП, наилучшим образом соотв етст ву-

ющих данному изображению, проводится на основе рассмотренных выше кри-

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

модели состоит в вычислении конкретного значения J

для различных моделей,

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

соответствует наименьшее значение J

Лабораторная работа 30. Оценивание параметров МСП,

порождаемых уравнениями АР

Цель работы. Смоделировать изображения, удовлетворяющие уравнениям

АР, оценить параметры авторегрессионного уравнения.

Порядок выполнения работы

188

Получить модель изображения №1, имеющего ОАР представление (7.28).

Множество S = {(−1, 0), (0, −1), (1, 0), (0, 1)}. Числовые значения для коэффи-

циентов a

могут быть взяты следующими:

1) a

= 0,12, a

−10

= 0,12, a

= −0,14, a

0 −1

= −0,14;

2) a

= 0,24, a

−10

= 0,24, a

= 0,1, a

0 −1

= 0,1,

где ξ(m, n) — множество независимых гауссовских случайных величин с

нулевым средним и дисперсией σ

. Дисперсия может принимать значения

= 0,5; 1,0. Значения для множества узлов решетки (m, n) ∈ Ω

находят-

ся по формуле

(m, n) =

(k,l)∈S

t−1

(m + k, n + l) + ξ

(m, n), t = 1, . . . , t

(m, n) = ξ

(m, n), (m, n) ∈ Ω.

Параметр t

может принимать значения t

= 5; 10. Изображен ие x

(m, n),

где (m, n) ∈ Ω

— искомое изображение.

Получить модель изображения №2, имеющего ОАР представление (7.31),

(7.32). Параметры a

, S, σ

аналогичны параметрам модели №1.

Алгоритм получения модели №2

Ш а г 1. Смоделировать поле независимых гауссовских случайных величин

ξ(m, n), (m, n) ∈ Ω с нулевым средним и дисперсией σ

Ш а г 2. Произвести БПФ поля ξ(m, n), котор ое заключается в последова-

тельном применении одномерного БПФ для стр ок и столбцов (и ли наоборот)

исходного поля.

Ш а г 3. Разделить каждый элемент преобразованного изображения

ξ(m, n)

на λ(m, n):

ξ(m, n) =

ξ(m, n)/λ(m, n), λ(m, n) = 1 − 2A

∗

Ш а г 4. Произвести обратное БПФ для изображения

ξ(m, n), (m, n) ∈ Ω.

Получить модель изображения №3, имеющего условно-марковское представ-

ление (7.44) на тороидальной решетке. Алгоритм аналогичен алгори тму №2,

только в качестве значения λ(m, n) принимается

λ(m, n) = (λ(m, n))

1/2

Задание 1. Оценить множество соседей S для моделей №1—3. Для нахожде-

ния множества S моделей №1, 2 использовать ( 7.4 6 ), (7.47), а для модели №3 —

(7.46), (7.48). Искать множество S среди множеств S

, . . . , S

, гд е S

= {(1, 0),

(−1, 0), (0, 1), (0, −1)}; S

= {(2, 0), (1, 0), (−1, 0), (0, 2), (0, 1), (0, −1), (0, −2)};

= {(1, 0), (1, 1), (−1, 0), (−1, 1), (0, 1), (0, −1), (1, −1), (−1, −1)} = N

(p);

= {(1, 1), (1, −1), (−1, 1), (−1, −1)} = N

(p).

Задание 2. Оценить параметры изображения из модели №1 по формулам

(7.29), (7.30), из модели №2 — по формулам (7.33), (7.34), из модели №3 — по

формулам (7.30), (7.45). Сравнить качество получаемых оценок и сделать выво-

ды о применимости алгоритмов для оценивания параметров.

189