СИНТЕЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И АЛГОРИТМОВ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА ОСНОВЕ СЛОЖНЫХ ЦЕПЕЙ МАРКОВА

Петров Е.П., Харина Н.Л., Ржаникова Е.Д.

Введение

Случайные процессы, у которых каждая выборка процесса зависит от определенного числа выборок расположенных в ближайшей окрестности от нее могут быть представлены сложной цепью Маркова со связностью между исследуемой выборкой и выборками окрестности [1-3].

Выбор размера сложной цепи Маркова аппроксимирующей реальный процесс зависит от скорости убывания автокорреляционной функции (АКФ), имеющей экспоненциальный или близкий к нему характер. Чем быстрее убывает АКФ с удалением от исследуемой выборки, тем меньше размер . При сложная цепь Маркова переходит в простую цепь Маркова, хорошо изученную в радиотехнических и других приложениях [2-6].

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

Постановка задачи

Для оценки потерь информации при выборе связности сложной цепи Маркова необходимо разработать математическую модель (ММ), адекватную реальному случайному процессу и на ее основе, используя теорию фильтрации условных марковских процессов, синтезировать алгоритмы фильтрации в условиях действия белого гауссовского шума (БГШ).

Математическая модель сложной цепи Маркова

Пусть последовательность бинарных импульсных сигналов сложная цепь Маркова с двумя равновероятными состояниями и , в которой каждое последующее состояние зависит от предыдущих с матрицей вероятностей переходов (МВП) вида:

,

(1)

где .

Нормированная АКФ случайного процесса, представленного сложной m-связной цепью Маркова имеет вид (рис. 1).

Представим сложную цепь Маркова суперпозицией из одномерных простых цепей Маркова [7,8]. В этом случае элементы МВП могут быть вычислены из аргумента логарифма в формуле (2) взаимной информации между состояниями -связной сложной цепи Маркова.

,

(2)

где - нечетное, - четное число; . Знак в (2) означает последовательность произведений для сомножителей с несовпадающими индексами в аргументах.

МВП -связной сложной цепи Маркова с двумя состояниями имеет вид:

,

(3)

где - знак транспонирования.

Потери информации за счет неадекватной аппроксимации случайного процесса простой цепью Маркова можно вычислить по формуле (2) при различных . На практике удобнее оперировать с оценками потерь в отношении сигнал/шум по мощности сигнала. Для этой цели необходимо, используя теорию фильтрации условных марковских процессов и разработанную ММ сложной цепи Маркова, синтезировать алгоритмы фильтрации случайных бинарных коррелированных сигналов при аппроксимации их сложными цепями Маркова с различной связностью [7,8].

Выполнение заданных ограничений на потери в отношении сигнал/шум по мощности гарантирует адекватность реального случайного процесса алгоритму фильтрации наименьшими вычислительными ресурсами.

	Рис.1. Нормированная АКФ случайного процесса	Рис. 2. 8-разрядное ЦПИ (473990)
Рис. 3(а). АКФ старшего РДИ по горизонтали			Рис. 3(б). АКФ старшего РДИ по вертикали

Оценим потери за счет упрощения аппроксимации реального случайного процесса простой цепью Маркова с двумя равновероятными состояниями. Для этого возьмем в качестве реального случайного процесса последовательность бинарных импульсных сигналов старшего разряда первой строки цифрового полутонового изображения (ЦПИ) (рис. 2) представленного 8-разрядными двоичными числами. Длина последовательности (строки) состоит из 938 импульсов. Автокорреляционная функция (АКФ) последовательности, представленная на рис. 3, имеет заметную корреляцию на интервале трех соседних импульсов по горизонтали и вертикали разрядного двоичного изображения (РДИ). Данный бинарный случайный процесс аппроксимируем одно-, двух- и трехсвязной цепью Маркова.

Алгоритмы одномерной фильтрации РДИ

На основе ММ (3) и теории фильтрации условных марковских процессов синтезированы алгоритмы фильтрации реального случайного процесса при трех аппроксимациях.

1. Односвязная цепь Маркова :

,

(4)

где

;

(5)

- оценки элементов МВП ; - логарифм отношения апостериорных вероятностей состояний дискретного параметра импульсных сигналов; - разность логарифмов функций правдоподобия дискретного параметра бинарных сигналов; - порог вычисленный по критерию идеального наблюдателя [9].

2. Двусвязная сложная цепь Маркова:

,

(6)

где в функции (6) и .

3. Трехсвязная сложная цепь Маркова:

,

(7)

где в функции (7) и , , , .

В таблице 1 приведены результаты фильтрации реального случайного процесса из которого следует, что при неудачном выборе аппроксимации реального процесса, потери в отношении сигнал/шум по мощности сигнала могут достигать значительной величины и тем большей, чем меньше отношение сигнал/шум на входе приемного устройства.

Таблица 1 – Выигрыш при фильтрации ЦПИ на основе одномерной сложной цепи Маркова различной связности .

Зашумленный реальный процесс
	7,47 дБ	8,55 дБ	8,81 дБ
	9,31 дБ	11,07 дБ	11,85 дБ
	10,84 дБ	13,63 дБ	14,85 дБ

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

ММ РДИ на основе простой двумерной цепи Маркова

Представим статическое ЦПИ набором РДИ, каждое из которых является двумерной цепью Маркова с двумя состояниями. Будем считать, что каждый элемент РДИ (рис.4) принадлежит двум независимым цепям Маркова с двумя равновероятными состояниями , и матрицами вероятностей переходов (МВП) из состояния к соседнему состоянию по горизонтали и вертикали БСП, соответственно:

(8)

Рис. 4. Фрагмент ММ РДИ

Рис. 5. Фрагмент области РДИ, где приняты обозначения

Если известны коэффициенты корреляции по строкам и столбцам РДИ, то элементы МВП (8) можно определить по формулам:

.

(9)

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

(10)

Для односвязной двумерной цепи Маркова окрестность примет вид (рис. 5):

(11)

Вероятности перехода состояний элементов окрестности относительно элемента образуют МВП вида:

.

(12)

Элементы матрицы (12) связаны с элементами матриц (8) следующими соотношениями:

, ,

(13)

где - элемент дополнительной матрицы

.

(14)

Элементы строк матрицы удовлетворяют условию нормировки:

.

(15)

ММ РДИ на основе сложной двумерной цепи Маркова

Рис. 6. Фрагмент двумерной ММ РДИ со связностью = 2

Для сложной двусвязной двумерной цепи Маркова окрестность, предшествующих формируемому состоянию , примет вид (рис. 7):

.

(16)

Рис. 7. Фрагмент области (рис. 6) с МВП

В этом случае корреляция ограничивается коэффициентом (рис. 1) по горизонтали и по вертикали.

Представим двусвязную двумерную цепь Маркова как суперпозицию двух двусвязных сложных цепей Маркова с МВП:

	(17)
.	(18)

Тогда МВП двусвязной двумерной цепи Маркова примет вид:

(19)

Элементы матрицы (19) связаны с элементами матриц (18) следующими соотношениями:

(20)

где

(21)

Остальные элементы матрицы (19) вычисляются аналогично в соответствии с состояниями четырех бинарных импульсов в точках окрестности (16).

Для оценки потерь вызванных аппроксимацией возьмем РДИ старшего разряда реального 8-разрядного ЦПИ (рис. 2). АКФ по горизонтали (рис. 3а) и вертикали (рис. 3б) РДИ имеют заметные значения на интервале , что позволяет аппроксимировать РДИ сложной цепью Маркова со связностью .

Рис. 8. Фрагмент области (рис. 6) со связностью и МВП (19)

Для сложной трехсвязной двумерной цепи Маркова окрестность, предшествующих формируемому состоянию , примет вид (рис. 8):

.

(22)

Алгоритмы нелинейной фильтрации РДИ и ЦПИ

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

1. Аппроксимация простой двумерной цепью Маркова . Алгоритм фильтрации бинарных импульсных сигналов синтезирован в [7] и имеет вид:

,

(23)

где

;

(24)

- оценки элементов МВП ; - логарифм отношения апостериорных вероятностей состояний дискретного параметра импульсных сигналов; - разность логарифмов функций правдоподобия дискретного параметра бинарных сигналов; - порог вычисленный по критерию идеального наблюдателя [9].

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

,

(25)

где в функции (25) и

Алгоритм нелинейной фильтрации РДИ (25) можно упростить, сократив одинаковые слагаемые, а функции объединить под одним логарифмом.

3. Аппроксимация двумерной трехсвязной цепью Маркова синтезируется аналогично алгоритму (25), но из-за громоздкости записи не приводится. Алгоритм содержит 32 слагаемых со знаком «плюс» и 31 слагаемое со знаком «минус».

Учитывая, представление ЦПИ набором 8-и РДИ, было проведено моделирование реального ЦПИ при трех аппроксимациях сложной цепью Маркова со связностью . Результаты фильтрации реального ЦПИ искаженного БГШ с нулевым средним и дисперсией при отношении сигнал/шум по мощности приведены в таблице 3. Выигрыш вычислялся суммированием выигрышей, полученных для каждого РДИ:

,

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

Таблица 2 – Выигрыш при фильтрации ЦПИ на основе двумерной сложной цепи Маркова различной связности .

	10,91 дБ	11,39 дБ	11,44 дБ
	14,60 дБ	15,64 дБ	15,72 дБ
	18,23 дБ	20,30 дБ	20,39 дБ

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

Литература

1. Марков А.А. Избранные труды: Теория чисел. Теория вероятностей/ Под ред. проф. Ю.В.Линника.- М.: Изд-во академии наук, 1951. – 465 с.

2. Ching Wai-Ki, Michael K. Ng. Markov Chains: Models, Algorithms and Applications.- Springer Science+Business Media, Inc., 2006. – 211p.

3. Королюк В.С., Турбин А.Ф. Полумарковские процессы и их приложения. – Киев: Изд. Наукова думка», 1986. – 182 с.

4. Амиантов И.Н. Избранные вопросы статистической теории связи. - М.: Сов. радио, 1971, - 416 с.

5. Петров Е.П., Харина Н.Л., Кононова В.Ю. Нелинейная фильтрация нестационарных цифровых случайных полей. T-Comm. Телекоммуникации и транспорт. № 5, 2011. ‑ С. 18-22.

6. Петров Е.П., Медведева Е.В., Харина Н.Л. Модели и алгоритмы цифровой обработки изображений: учебное пособие. – Киров: О-Краткое, 2008. – 88 с.

7. Петров Е.П., Харина Н.Л. Математическая модель последовательностей бинарных импульсных сигналов на основе сложных цепей Маркова// Сб. докл. XVIII МНТК «Радиолокация, навигация, связь»: - Воронеж, т.1, 2012.- С.1-8.

8. Харина Н.Л. Математическая модель двоичных изображений на основе сложных цепей Маркова// Сб. докл. XVIII МНТК «Радиолокация, навигация, связь»: - Воронеж, т.1, 2012.- С.147-154.

9. Тихонов В.И. Статистическая радиотехника. - М.: Сов.радио, 1966, 679 с.