Алгоритм разрастания регионов (“region growing”) является методом автоматической сегментации и учитывает пространственное расположение точек напрямую.
Метод разрастания регионов основан на следующей идее. Сначала по некоторому правилу выбираются центры регионов (seeds), к которым поэтапно присоединяются соседние точки, удовлетворяющих некоторому критерию. Процесс разрастания регионов останавливается, когда ни одна точка изображения не может быть присоединена ни к одному региону.
Применяются разные критерии, на основании которых точка присоединяется или не присоединяется к региону: близость (в некотором смысле) точки к центру региона; близость к соседней точке, присоединенной к региону на предыдущем шаге; близость по некоторой статистике региона; стоимость кратчайшего пути от точки до центра региона, и т. п.
В основном процедура разрастания регионов используется для получения отдельных регионов, однако, применяя эту процедуру последовательно или одновременно для нескольких регионов, можно получить разбиение всего изображения. Существуют различные стратегии выбора зерен (seeds) и выращивания регионов.
Простейшая стратегия заключается в сканировании изображения сверху вниз, слева направо. На i-м шаге этого алгоритма рассматривается точка A, и сформированы регионы B и C слева и выше от пикселя A (рис. 5.11).
Рис. 5.11. i шаг алгоритма разрастания регионов
Определим I(A) как яркость пикселя A, а Clavg(B) и Clavg(C) как средние яркости областей, которым принадлежат точки B и C соответственно. Обозначим через δ пороговое значение, которое задает чувствительность метода при создании нового сегмента.
На i-м шаге алгоритма проверяются следующие условия и выполняются соответствующие действия:
1. Если |I(A) – Clavg(B)| > δ & |I(A) – Clavg(C)| > δ, то создаем новую область и присоединяем к ней пиксель A.
2. Если |I(A) – Clavg(B)| ≤ δ xor[4] |I(A) – Clavg(C)| ≤ δ, то создаем новую область и присоединяем к ней пиксель A.
3. Если |I(A) – Clavg(B)| ≤ δ & |I(A) – Clavg(C)| ≤ δ, то проверяем:
1. Если | Clavg(B) – Clavg(C)| ≤ δ, то сливаем области B и C.
2. Если | Clavg(B) – Clavg(C)| > δ, то добавляем пиксель A к тому классу, отклонение от которого минимально.
Недостатком описанного алгоритма является высокие вычислительные затраты.