Измерение прямолинейности сегмента кривой (представленного в виде ломаной линии)

Я работаю над автоматическим алгоритмом маркировки контура возвышения, и один из факторов, который я хочу принять во внимание при определении положения меток, - насколько «прямолинейен» конкретный сегмент контура. Чем оно прямее, тем больше вероятность, что оно будет использовано для размещения метки на этом сегменте.

Каждый контур представлен полилинией (но точки расположены близко друг к другу, чтобы выглядеть как кривая невооруженным глазом). У меня тогда есть фиксированная длина (ширина метки), скажем, 100 пикселей. Если я случайно (или иным образом) выбираю сегмент контура с шириной 100 пикселей, я хочу получить количественное количественное значение его прямолинейности (скажем, ноль для полностью прямого контура сегмента, некоторое значение больше нуля для не такой прямой сегмент, и это значение увеличивается по мере того, как увеличивается кривизна).

Я искал ответы, но не мог найти ничего действительно полезного. Буду благодарен за любые указатели.

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

Например, предположим , что вы собираетесь проводить систематический поискчерез всю связную компоненту контура, представленную как последовательность точек P (0), P (1), ..., P (n). Это было бы сделано путем инициализации одного указателя (индекса в последовательности) s = 0 («s» для «начала») и другого указателя f (для «конца»), чтобы быть наименьшим индексом, для которого расстояние (P (f), P (s))> = 100, а затем продвижение s на расстояние, равное расстоянию (P (f), P (s + 1))> = 100. В результате получается кандидатная ломаная (P (s), P (s +) 1) ..., P (f-1), P (f)) для оценки. Оценив его «пригодность» для поддержки метки, вы затем увеличиваете s на 1 (s = s + 1) и переходите к увеличению f до (скажем) f 'и s до s' до тех пор, пока еще раз кандидатная ломаная линия не превысит минимальное значение. образуется диапазон 100, представленный как (P (s '), ... P (f), P (f + 1), ..., P (f')). При этом вершины P (s) ... P (s ') Очень желательно, чтобы пригодность могла быть быстро обновлена ​​на основе знания только удаленных и добавленных вершин. (Эта процедура сканирования будет продолжаться до тех пор, пока s = n; как обычно, f должно быть разрешено «оборачиваться» от n до 0 в процессе.)

Это соображение исключает множество возможных мер пригодности ( извилистость , извилистость и т. Д.), Которые в противном случае могли бы быть привлекательными. Это побуждает нас отдавать предпочтение мерам на основе L2 , потому что они, как правило, могут быстро обновляться, когда базовые данные изменяются незначительно. Принимая аналогию с анализом главными компонент предполагает , мы принимаем следующие меры (где маленьким лучше, по запросу): используйте меньшее из двух собственных в ковариационной матрицекоординат точки. Геометрически это является одной мерой «типичного» бокового отклонения вершин в пределах потенциального участка ломаной линии. (Одна интерпретация состоит в том, что его квадратный корень является меньшей полуосью эллипса, представляющего вторые моменты инерции вершин полилинии.) Он будет равен нулю только для наборов коллинеарных вершин; в противном случае он превышает ноль. Он измеряет среднее боковое отклонение относительно базовой линии в 100 пикселей, созданной началом и концом полилинии, и, таким образом, имеет простую интерпретацию.

Поскольку ковариационная матрица составляет только 2 на 2, собственные значения быстро находят путем решения одного квадратного уравнения. Кроме того, ковариационная матрица представляет собой сумму вкладов от каждой из вершин полилинии. Таким образом, он быстро обновляется при удалении или добавлении точек, что приводит к алгоритму O (n) для контура с n точками: это хорошо масштабируется до очень подробных контуров, предусмотренных в приложении.

Вот пример результата этого алгоритма. Черные точки - вершины контура. Сплошная красная линия является лучшим кандидатом в полилинии, длина конца в конец больше 100 в пределах этого контура. (Визуально очевидный кандидат в правом верхнем углу не достаточно длинный.)

В сообществе компьютерной графики часто бывает необходимо найти ограничивающую рамку вокруг объекта. Следовательно, это хорошо изученная проблема с быстрыми алгоритмами. Например, см. Статью « Минимальные ограничивающие рамки» в Википедии . Вы можете найти прямоугольник минимальной площади, окружающий вашу полилинию, а затем использовать соотношение сторон прямоугольника, высоту / длину. Чтобы получить более точную меру, вы можете посмотреть на отклонение полилинии от центральной линии этого ограничивающего прямоугольника.

Я не знаю, помогает ли это, или даже если это считается ответом, но когда я сидел здесь и размышлял над вопросом, который только что написал, у меня возникла мысль:

Что, если вы поместите круг определенного радиуса на линию контура. Этот круг будет пересекать контурную линию как минимум в двух местах. Чем прямее линия, тем короче расстояние вдоль линии контура между двумя точками пересечения. Чем больше расстояние вдоль линии контура между точками пересечения, тем более изогнута линия. Если имеется более двух точек пересечения, контурная линия слишком изогнута.

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

Я уверен, что это не очень помогает, и то, что я говорю по-английски, намного сложнее на любом языке программирования, который вы используете, но это может быть началом?

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

Это должно быть действительно простым в реализации решением.

Обновление: Как правильно заметил Майк, это будет равно Sinuosity .

Поиск "кривизна" и "полилиния", я получил эту информацию Как я могу найти кривизну полилинии? , Там он предложил использовать возврат к определению кривизны - K= DF/Ds. Здесь Fон имеет в виду phi, или Tв примечаниях Википедии здесь ( http://en.wikipedia.org/wiki/Curvature ).

Скажем, у вас есть последовательность трех точек, p0, p1 и p2. вычислите расстояние sмежду p0 и p1, которое является дельтой s ( Ds), предполагая, что точки находятся близко друг к другу. Тогда вам нужна дельта T ( DT), которая представляет собой изменение единичного тангенциального вектора между p0 и p1. это может быть сложный способ, но грубый метод, который я могу придумать, состоит в том, чтобы взять два вектора p0-> p1, p1-> p2, нормализовать каждый, чтобы иметь длину один, затем взять векторное вычитание этих двух, а затем определить величину. То есть DT. Деление дает кривизну K0_1. возьмите p1, p2 и p3 для вычисления K1_2и так далее.

Мне интересно, если вы получите контур как ломаную линию, а не как визуализированные пиксели. Вы сказали 100px, так что я немного волнуюсь.