3.12. СИНТЕЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ АЛГОРИТМОВ ОБНАРУЖЕНИЯ ПРОСТРАНСТВЕННО-ПРОТЯЖЕННЫХ ОБЪЕКТОВ ПРИ ОПИСАНИИ БИНАРНОЙ СЦЕНЫ СЛОЖНЫМИ ЦЕПЯМИ МАРКОВА

Как показано в разделе 3.4, для автоматического обнаружения и выделения протяженных сигналов, местоположение которых на исходном изображении неизвестно, целесообразно применять алгоритмы Автоматическое обнаружение (и выделение) пространственно-протяженных объектов производится с помощью класса алгоритмов независимо по строкам и столбцам исходного изображения. В разделе 3.4 рассмотрены математические модели (цепи Маркова) и произведен расчет временной эффективности для случая, когда бинарные сигналы являются статистически независимыми. На практике бывают случаи, когда статистические свойства бинарных сигналов описываются простыми и сложными цепями Маркова. Рассмотрим описание вероятностных свойств исходных изображений простыми цепями Маркова. Имеем четыре условных вероятности Для критерия то в случае независимости бинарных сигналов имеем следующую матрицу вероятностей переходов (п. 3.4):

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

Сравнив (3.12.1) и (3.12.2), видим, что вероятности во второй строке матрицы (3.12.2) отличаются от вероятностей

в первой и третьей строках. Ниже представлены матрицы критерия для двух рассматриваемых случаев:

Матрицы (3.12.3) имеют одинаковую структуру, но в правой матрице вероятности в первой строке отличаются от вероятностей во второй и третьей строках. Нетрудно показать, что и в общем случае (для любого критерия ) структура матриц вероятностей переходов, когда вероятностные свойства исходных изображений описываются простыми цепями Маркова, не отличается от структуры матриц вероятностей переходов, когда бинарные сигналы статистически независимы, лишь в первом случае вероятности в некоторых строках будут отличаться от вероятностей в других. Таким образом, методика расчета временных характеристик алгоритмов класса не отличается от методики, рассмотренной ранее (см. 3.4).

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

Пусть исходное изображение характеризуется тем, что условные вероятности появления «нулей» и «единиц» зависят от двух предыдущих значений бинарного сигнала. Общая теория цепей Маркова [51] позволяет свести двухсвязную цепь Маркова в простую (односвязную), но для двухмерного вектора. При этом число состояний вновь образованной цепи Маркова рассчитывается по формуле , где число состояний исходной (простой) цепи Маркова.

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

Для отыскания искомой матрицы на основе (3.12.4) необходимо учесть, что событие «10» для критерия невозможно. Следовательно, в (3.12.4) необходимо вычеркнуть третью строку и третий столбец. Учитывая заданные вероятности , получим матрицу вероятностей переходов размерности 3X3:

Цепь (3.12.5) допускает укрупнение объединением двух последних состояний, после чего имеем искомую матрицу процедуры размерностью 2X2:

Перейдем к критерию Число возможных состояний соответствующей цепи Маркова равно . Для перечисления всех девяти состояний (событий) обозначим появление первой единицы появление второй единицы — Тогда все события могут быть представлены в виде: Для критерия события и являются невозможными. Учитывая заданные вероятности получим матрицу вероятностей переходов

Цепь (3.12.7) может быть укрупнена объединением двух последних состояний . В результате окончательная матрица размерностью 4X4 будет иметь вид

Перейдем к критерию Число всевозможных состояний соответствующей цепи Маркова Для перечисления всех шестнадцати состояний (событий) обозначим появление второго нуля 0, появление первой единицы , а появление второй единицы . Тогда все события можно представить в виде: , Для критерия (2/3) следующее событие невозможно: Учитывая заданные вероятности имеем матрицу вероятностей переходов размерностью

Возможно укрупнение цепи (3.12.9) объединением трех состояний . В результате получим окончательную матрицу размерностью

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

Для алгоритма

Для алгоритма

Для алгоритма

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

В табл. 3.28-3.30 представлены рассчитанные величины для следующих исходных данных: при справедливости гипотезы (нет полезного сигнала) при справедливости гипотезы полезный сигнал)

Таблица 3.28

Окончание табл. 3.28

Таблица 3.29

Таблица 3.30

Как видим, наибольшей эффективностью обладают алгоритмы

Пусть вероятностные закономерности исходной бинарной последовательности описываются -связной цепью Маркова, т. е. заданы условные вероятности Зададим также критерий обнаружения с помощью которого процесс принятия решения описывается соответствующей цепью Маркова [76] с числом состояний, рассчитываемым по формуле Тогда искомая цепь Маркова имеет число состояний Затем необходимо все М состояний перечислить. Для заданного критерия выявляются невозможные события, в дальнейшем они не учитываются. Для оставшихся возможных событий составляется матрица вероятностей переходов, которая подвергается укрупнению (возможно несколько Полученная укрупненная матрица и является искомой.

Приведем пример получения матрицы вероятностей переходов для критериев при Начнем с критерия Число возможных событий (состояний) . Все восемь событий представим в виде 000, 001, 010, 011, 100, 101, 110 и 111, из них только четыре события возможны: 000, 001, 011 и 111. Имеем матрицу

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

Сравнив (3.12.15) с (3.12.6), видим, что матрица критерия как для простой, так и для двух- и трехсвязной цепи Маркова имеет размерность 2X2 и одинаковую

структуру. Нетрудно показать, что это справедливо и в более общем случае

Получим матрицу переходных вероятностей критерия при Число возможных событий Представим все события в виде: (подчеркнутые события невозможны). Следовательно, имеем следующую матрицу вероятностей переходов размерностью 8X8:

Укрупнив цепь (3.12.16) объединением трех состояний получим искомую цепь Маркова размерностью 6X6:

Матрицы (3.12.15) и (3.12.17) позволяют синтезировать цепи Маркова алгоритмов

Приведем синтезированную цепь Маркова алгоритма

Расчет двух вариантов, дал следующие результаты:

вариант I: все

вариант II: все

В заключение заметим, что синтезированные матрицы вероятностей переходов при понижении порядка связности (числа ) укрупнением «переходят» в соответствующие цепи Маркова (но с меньшим числом ). Например, матрица (3.12.17) при переходит» в матрицу (3.12.8), которая в свою очередь при «переходит» в матрицу

а при в известную матрицу [83]