Комментарии 9
Так и знал, что что-нибудь да забуду. После обхода по контуру точки контура желательно отсортировать по X, затем по Y, тогда в алгоритме получения начальных точек можно будет пропускать не отдельные точки, а целые группы точек, принадлежащие уже обсчитанному контуру. Найти соответствующий Y и пропустить до максимального X.
Насколько многогранная и интересная тема оказалась, у меня тогда будет видимо еще один вариант с трассировкой контуров. Потому что вы предложили то что я совсем не ожидал и никогда не видел.
Спасибо.
Спасибо.
Спасибо за статью. По моему, в OpenCV применяется похожий алгоритм.
>Сложность такого алгоритма пропорциональна количеству точек внешних контуров для объектов изображения.
По факту, это означает сложность O(n^2). Такая сложность практически у всех алгоритмов (в т.ч. и у простейших рекурсивных). Я конечно понимаю, что ваш алгоритм быстрее, но это достигается уменьшением константы вычислений, а не снижением сложности алгоритма.
>Сложность такого алгоритма пропорциональна количеству точек внешних контуров для объектов изображения.
По факту, это означает сложность O(n^2). Такая сложность практически у всех алгоритмов (в т.ч. и у простейших рекурсивных). Я конечно понимаю, что ваш алгоритм быстрее, но это достигается уменьшением константы вычислений, а не снижением сложности алгоритма.
все-таки внешних точек существенно меньше, чем размер изображения. но в целом, да, сложность O(n^2), но даже в худшем случае на фильтрованном изображении константа будет порядка 0.25.
и кстати это не совсем правда, т.к. даже у считывания изображения из файла в «плоском формате» сложность width*height, просто можно замаскировать предварительные действия за считывание в нужный формат в памяти. действительно — для того чтобы обработать изображение, нужно просмотреть каждый его пиксель. вопрос в том, чтобы этих просмотров (а тем более измнений) было не более 1 за работу алгоритма — и здесь почти так.
А как определяется что точка принадлежит контуру? Не будет ли подвоха что в соседних сегментах к контуру отнесутся разные точки, например в одном внутренние в другом внешние.
Еще, по моему в переходе по диагоналям кроется проблема.
Еще, по моему в переходе по диагоналям кроется проблема.
мне несколько не понятно, что значит «сегмент» в вашем вопросе. по сути мы помним все внешние точки для всех контуров, и попадая на внешнюю — пропускаем до внешней точки того же контура, лежащей правее остальных для заданного Y, то есть во внутренние точки у нас никаких шансов попасть нет.
в диагоналях проблем нет, это, вовсе не очевидно из кода обхода, согласен, но все учтено :)
в диагоналях проблем нет, это, вовсе не очевидно из кода обхода, согласен, но все учтено :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрая маркировка изображений с использованием внешних контуров