Кривизна кривой шириной в один пиксель

Известный способ сделать это — подогнать параметрическую кривую низкого порядка к каждой из скелетонизированных точек, используя две или более соседних точек. Затем вы вычисляете кривизну в точке, используя подобранные параметры кривой с помощью аналитической формулы. Можно использовать несколько моделей кривых. Две основные модели:

1. Окружность. Радиус кривизны – величина, обратная кривизне. Для кривой он равен радиусу дуги окружности, которая наилучшим образом соответствует кривой в этой точке. Вы можете подогнать круг к набору точек данных 2D, используя различные методы. Библиотека Python, которая реализовала несколько, находится здесь.
2. Квадратичный. Это можно подогнать к точке и ее соседям, затем можно оценить кривизну путем дифференцирования кривой второго порядка здесь. Вы можете использовать numpy.polyfit, чтобы соответствовать этой модели. Простая стратегия состоит в том, чтобы сначала оценить касательный вектор в точке, подбирая локальную линию (например, с помощью полифита с использованием кривой 1-го порядка). Вы вращаете точки, чтобы выровнять касательный вектор с осью x. Наконец, вы подгоняете одномерную квадратичную функцию f(x) к повернутым точкам, используя полифит.

Сложность создания любого оценщика кривизны заключается в том, что кривизну можно оценивать в разных масштабах. Например, хочу ли я, чтобы мой оценщик был чувствителен к высокочастотным деталям, или это на самом деле шум? Это решение проявляется в выборе размера окрестности. Слишком маленькие, а ошибки из-за шума и дискретизации приводят к неустойчивым оценкам. Однако слишком большой может быть большая ошибка моделирования (ошибка аппроксимации кривой как параметрической функции). Как правило, вы должны выбрать лучший размер окрестности самостоятельно.

У вас также будут плохие оценки кривизны в точках соединения, но это в значительной степени неизбежно, поскольку кривизна там не определена. Наивным решением может быть сегментация всех путей в точках пересечения, а затем оценка кривизны каждого пути в отдельности.

Тоби дал отличное предложение относительно точек соединения: определить точки соединения и взять каждую линию между ними независимо.

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

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

3. Отслеживание каждой строки. В приведенном выше шаге необходимо отследить каждую строку. Посмотрим, сможешь ли ты это понять, это весело! Вот описание алгоритма, который отслеживает очертания объектов, вы можете используйте это как вдохновение, так как эта проблема очень похожа. Сохраните вектор с координатами x и один с координатами y для каждой строки.

4. Сглаживание линий. Как вы заметили, последовательные шаги выполняются в одном из 8 направлений, поэтому углы сильно дискретизированы. Этого можно избежать, сгладив векторы координат. Это быстрый и грязный трюк, но он работает. Думайте об этих векторах как об одномерных изображениях и применяйте фильтр сглаживания (я предпочитаю фильтр Гаусса для много причин). Здесь вы фильтруете вектор с координатами x отдельно от вектора с координатами y.

5. Вычисление кривизны. Наконец, вы можете вычислить кривизну кривой, как норма производной единичной нормали к кривой. Не забывайте учитывать расстояние между точками при вычислении производных!