Сведения из теории дискретных цепей Маркова

Фурман Я. А., Юрьев А. Н., Яншин В. В.
фрагмент книги "Цифровые методы обработки и распознавания бинарных изображений", 1992 г.

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

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

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

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

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

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

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

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

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

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

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

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

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