4.1.3. Последовательный алгоритм разметки
Теперь мы подготовлены к описанию алгоритма разметки, который лучше приспособлен к последовательному сканированию изображения и не нуждается в рекурсивных вызовах. Допустим, что сканирование ведется строка за строкой, сверху вниз и слева направо (рис. 4.3). Тогда при обработке элемента А мы знаем, что левый элемент В, так же как и верхний С, уже помечен. Далее, элемент 
расположенный над В, считается связанным с А и потому также должен быть принят во внимание.
Для простоты предположим на время, что мы размечаем лишь компоненты объекта. Тогда если А содержит нуль, то можно идти дальше. Если А содержит единицу, a D уже помечен, то достаточно просто скопировать эту метку и продолжить работу. То же самое необходимо сделать, если помечен один из элементов В или С. Если же ни В, ни С не помечены, то мы должны выбрать новую метку для А. Тем самым здесь мы впервые вводим в рассмотрение новую
Рис. 4.3. Решения, принимаемые при разметке. Они основываются на метках, уже присвоенных четырем элементам изображения, попавшим в окно, которое перемещается по изображению и последовательно сканирует его.
компоненту. Оставшаяся возможность: как В, так и С имеют метки. Проблем не возникает, когда эти метки одинаковые; но поскольку по нашей схеме они не являются соседями, их метки могут быть различными. В этом случае мы как раз обнаружили, что две различные метки использовались для различных частей одной компоненты изображения (рис. 4.4). Они соединяются через точку А. В этот момент необходимо указать, что две метки эквивалентны, и использовать одну из них для А. Такова цена, которую приходится платить за последовательный характер алгоритма.
Рис. 4.4. Последовательная разметка.
Может так случиться, что две области, считавшиеся ранее различными, на самом деле оказываются связанными. Необходимо указать на эквивалентность соответствующих меток. (Воспроизводится с разрешения из работы [115].)
В конце просмотра данные, относящиеся ко всем частям с эквивалентными метками, необходимо объединить. Если же мы лишь накапливаем суммы для расчета нулевого, первого и второго моментов, можно избежать и этого шага. Достаточно сложить суммы, до сих пор относившиеся к двум различным компонентам, и продолжать накопления в этих объединенных суммах.
Если мы хотим обозначить области едиными метками, необходимо сделать второй просмотр изображения, присваивая каждой области метку — представителя того класса эквивалентности, которому принадлежит ее исходная метка.
