Разметка (labeling) изображения

Для обработки бинаризированного изображения и поиска на нем объектов необходимо выделить области (далее эти области будут называться «блобами»), образующие связанные участки на изображении. После разметки изображения каждому пикселу блоба будет присвоен один общий уникальный номер (label). В результате каждый блоб будет описан всеми пикселями, которым был присвоен номер данного блоба. Наглядно процесс разметки представлен на рисунке 4. На приведенном рисунке одному блобу принадлежат сразу несколько номеров. Это возникает из-за того, что описываемый далее алгоритм является однопроходным (один раз оценивает каждый пиксель), но в дальнейшем одному блобу присваивается только минимальный номер из тех, что попали в него.

Рисунок 5: Разметка изображения.

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

Рисунок 6. Маска для разметки (X — исходный пиксель; A, B, C, D — связанные пиксели) После того, как все пиксели были размечены, производится обработка блобов так, чтобы они содержали только один номер.