Слияние двух меток в соединяемых компонентах во время первого прохода

Question

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

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

Answer 1

Вы не исключили бы второй проход.Если вы изменили метки соседних пикселей, что насчет их соседних пикселей?По сути, если это событие происходит, вы обнаружили, что две метки находятся в одном классе эквивалентности;но вам все равно придется пройтись по всему, что вы исследовали до сих пор, чтобы переназначить эти ярлыки.Вы также можете просто сделать это на втором проходе и выполнить все переназначения за один раз.

Пример:

+-+-+-+
|?|?|A|
+-+-+-+
|B|B|x|
+-+-+-+

Вы изучаете пиксель x, он соответствует обоим пикселям на север и запад.Предположим, A является минимальной меткой.Таким образом, вы решите пометить три пикселя A, но это не пометит другой пиксель B.Вы все еще должны записать, что A == B, и вам все равно придется пролистать, чтобы перемаркировать любые B, которые остались.Кроме того, позже вы можете обнаружить, что само A эквивалентно некоторой другой метке меньшего размера, и вам придется поменять все эти пиксели позже.