1.3. СВЕДЕНИЯ ИЗ ТЕОРИИ ДИСКРЕТНЫХ ЦЕПЕЙ МАРКОВА

Дискретные цепи Маркова — удобная и эффективная математическая модель бинарных изображений. Это объясняется тем, что уровни яркости бинарного изображения имеют всего лишь два значения, изображение дискретизировано при занесении его в запоминающее устройство изображений в ЭВМ, а механизм формирования изображений обычно обеспечивает определенную степень статистической зависимости между соседними отсчетами. Марковские модели достаточно часто применяются при обработке изображений, в том числе и бинарных (например, в [44]).

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

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

Основной характеристикой цепи Маркова является условная вероятность перехода вида означающая вероятность попадания процесса в состояние а, в момент времени при условий, что в момент времени процесс находился в состоянии При независимости указанных условных вероятностей от времени имеем однородные цепи Маркова. Вероятности образуют квадратную матрицу вероятностей переходов размерности

Вероятность перехода за шагов вычисляется через n-й степень матрицы Р, т. е.

где

— соответственно, вероятностные векторы состояний марковской цепи на нулевом и шагах.

Состояние называется поглощающим, если

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

При имеющейся матрице вероятностей переходов Р указанную матрицу удобно представить в следующем блочном виде:

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

где Q — квадратная подматрица матрицы Р, получающаяся вычеркиванием строк и столбцов, соответствующих поглощающим состояниям.

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

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

При наличии нескольких, поглощающих состояний возникает вопрос: какова вероятность того, что процесс попадает в конкретное поглощающее состояние? Ответ на него позволяет дать фундаментальная матрица, с помощью которой вычисляется матрица В [см. формулу (1.3.2)]:

При наличии двух поглощающих состояний имеются уже не только безусловные значения EV и DV, но и условные Пусть вектор математического ожидания времени до принятия решения «нет» («да»): вектор дисперсии математического ожидания времени до принятия решения «нет» («да»).

Для вычисления и необходима фундаментальная матрица

где вычисляется по формуле (1.3.3)] Матрица является диагональной с элементами формулу (1.3.5)].

Обращенные цепи Маркова позволяют производить прогнозирование процесса в прошлом времени, если известно состояние процесса в настоящем.

Матрицу вероятностей переходов обращенной цепи Маркова Р вычисляют по формуле

где транспонированная матрица эргодической цепи Маркова, получающаяся из исходной поглощающей цепи D — диагональная матрица с элементами, равными где координата вектора предельных вероятностей , вычисляемого по формуле дополненной условием нормировки

Перейдем к рассмотрению методов определения векторов вероятностей состояния дискретной цепи Маркова.

Исходным выражением для нахождения является формула (1.3.1), в которой основными действиями служат умножение вектора на матрицу и возведение матрицы в целую степень. Данный подход, с вычислительной точки

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

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

Независимые методы базируются на методах производящих функций, z — преобразованиях и расчетах по формуле Перрона [51]. Общий механизм вычисления вектора вероятностей состояний цепи поясним на примере цепей с регулярной матрицей вероятностей переходов Р [76]. Степень матрицы Р может быть представлена в виде

где характеристические числа матрицы Р, причем

где и — матрицы, составленные соответственно из семейств правых и левых собственных векторов матрицы Р.

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

Метод вычисления компоненты вероятностного вектора цепи с развязкой по состояниям получается на основе тождества Гамильтона-Кели. Как для вероятностного вектора, так и для его отдельной компоненты существуют рекуррентные соотношения вида [69, 76]:

где коэффициенты характеристического полинома матрицы Р, взятые с обратным знаком.

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

где F — матрица Р, приведенная к нормальному виду Фробениуса, матрица порядка , строками которой являются компоненты векторов

Основные преимущества представления марковской цепи в виде (1.3.10) основаны на том, что матрица F по сравнению с матрицей Р имеет очень простую структуру. Использование рекуррентных методов, обладающих свойством развязки по состояниям, обеспечивает значительный выигрыш в объеме вычислений для задач, в которых необходимо определение одной или нескольких компонент вектора вероятностей состояний марковской цепи с большим числом состояний. Примером таких задач является задача срыва слежения конечного автомата, возникающая, например, при прослеживании контура изображения.