7.3.2. Байесовская сегментация изображения на основе стохастической релаксации

Оптимальная сегментация, основанная на байесовском принципе, должна вырабатывать такой результат , которому соответствует максимум апостериорного распределения вероятностей (АРВ):

                           (7.26)

где  - результат оптимальной сегментации. Располагая совместным распределением(7.25), можно найти и АРВ, поскольку

                       (7.27)

Однако вычисления (7.27) можно избежать. В самом деле, АРВ  и совместное распределение  различаются лишь множителем , который не зависит от . Поэтому характер зависимости от  этих двух распределений одинаков, следовательно, вектор , максимизирующий АРВ, доставляет максимум совместному распределению и, наоборот, если  максимизирует , то при этом максимизируется и . Эти соображения позволяют вместо требования (7.26) для отыскания оптимального результата  использовать требование

                             (7.28)

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

Какальтернатива данному традиционному методу получения байесовских оценок развивается теория, получившая название стохастической релаксации. Вместо полного перебора вариантов, описанного выше, в этом случае осуществляют целенаправленное вероятностное моделирование случайного поля с использованием итерационной процедуры. На -м шаге итерационного процесса формируется поле , а основой его генерирования являются результат предыдущего шага  и распределение . При рационально организованном итерационном процессе имеет место сходимость  к , причем, хотя количество итераций оказывается достаточно большим, общее число вычислений получается вполне приемлемым. Существует несколько методов стохастической релаксации, реализующих эту идею. Рассмотрим один из них, так называемый метод Метрополиса[7.3, 7.4], более подробно.

На первом шаге итерационного процесса  случайное поле  формируют при помощи датчика случайных чисел с равномерным распределением вероятностей на интервале [0, 1]. Для этого данный интервал разбивают на два подынтервала, а в качестве граничной точки используют значение вероятности  того, что . При неизвестном значении  его принимают равным 0,5. При помощи датчика формируют число , которое затем путем сравнения с порогом  преобразуют в  в соответствии с правилом:

Отметим, что получаемое в результате первого шага случайное поле состоит из независимых значений в силу независимости чисел, генерируемых датчиком.

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

На каждом микрошаге решается вопрос о возможном изменении только того отсчета , который является текущим. Для этого сначала, как и на первом шаге, при помощи датчика случайных чисел вырабатывается число  (которое может совпадать с прежним значением поля  в этой точке или отличаться от него). В результате формируется промежуточный вектор, который, возможно, отличается от  только в одной текущей точке с координатами . Затем по формуле (7.25) подсчитываются вероятности  и , сравнение которых позволяет определить, какой из векторов  и  является более вероятным. Если  (это может быть лишь при различных значениях  и ), то за результат этого шага принимается вектор . Следовательно, при таком развитии процесса на данном микрошаге происходит изменение одного (текущего) элемента поля.

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

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

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

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

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

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

где

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

На рис. 7.6 показаны результаты эксперимента по бинарной сегментации реального изображения участка земной поверхности, выполненного на базе описанного метода. На рис. 7.6, апоказано исходное изображение, а на рис. 7.6, б и 7.6, в – результаты его бинарной сегментации на основе порогового (порог равен 180) и гиббсовского методов соответственно. Очевидно, что гиббсовская сегментация субъективно воспринимается как болеесовершенная.

а

б

в

Рис.7.6. Гиббсовская сегментация изображения

Критерий прекращения итерационного процесса основывается на анализе степени обновления результата данного макрошага  по сравнению с предыдущим макрошагом . На первых макрошагах количество отсчетов поля, изменяющих свое значение, велико. Постепенно это число уменьшается, стремясь в пределе к нулю, что и означает сходимость итерационного процесса. Поэтому можно использовать правило, при котором процедура прекращается после очередного макрошага, если процент обновившихся точек не превысил заданной величины . Понятно, что продолжительность процедуры является случайной величиной. В проведенном эксперименте величина была выбрана равной 0,01, а продолжительность процедуры составила 235 макрошагов.

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