4-соединенный против 8-подключенный в маркировке подключенных компонентов. Каковы / являются заслугами одного над другим?

Question

Я хочу реализовать Маркировка подключенных компонентов , но я не уверен, должен ли я делать это 4-контактным способом или 8-контактным. Я прочитал о 3 материалах, но ни один из них не объясняет их выбор графической связности. Один из них выбрал 8, два других 4 и один из этих двух сказали, что он выбрал 4 для более короткой трассировки программы (отметив, что расширение его псевдокода до 8 должно быть тривиальным). Итак, каковы достоинства одного над другим?

Answer 1

Единственная реальная разница заключается в том, как алгоритмы обрабатывают диагональные конфигурации.С алмазной окрестностью диагональные элементы «in» не будут связаны.С квадратным соседством они будут.

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

Answer 2

Ну, исходя из моего скромного опыта, я бы сказал, что нет никакого «достоинства» в использовании 4 или 8 подключенных.

Что произойдет, если использовать 4 для маркировки, вы, вероятно, получите больше объектов.

Это как остров пикселей. Некоторые «острова» связаны с другими островами только одним пикселем, и, если этот пиксель имеет диагональ, использование 4 подключенных пометит оба острова как два отдельных объекта, а 8 подключенных будет предполагать, что они являются только одним объектом.

Answer 3

С сожалением выражаю несогласие с комментариями этой страницы, по крайней мере, в том, что касается алгоритмов поиска в двоичных изображениях. Там могут быть явные преимущества при использовании 4-по сравнению с 8-подключения. То есть в геометрии решения. Очевидно, что недостатки заключаются в сложности времени (теоретически работа в «4-режиме» имеет временную сложность вдвое больше, чем в другом режиме).