Распознавание отрезков по последовательности точек

Question

Учитывая ввод 2D точек, я хотел бы сегментировать их по линиям. Поэтому, если вы рисуете линию зигзагообразного стиля, каждый из сегментов должен распознаваться как линия. Обычно я бы использовал OpenCV cvHoughLines или аналогичный подход (PCA с удалением выбросов), но в этом случае программе не разрешается делать «ложноположительные» ошибки. Если пользователь рисует линию, и она не распознается - это нормально, но если пользователь рисует кривую, и она получается в виде квадрата - это не нормально. Итак, у меня есть верхняя граница ошибки - но если это длинная линия, а некоторые точки имеют большее расстояние от аппроксимированной линии, это снова нормально. Подведены итоги:

линия обнаружения - нет ложных срабатываний динамически корректируемая ошибка

О, и точки нарисованы в последовательности, как рисование рук.

По крайней мере, это не должно быть быстрым. Это для инструмента рисования. У кого-нибудь есть идея?

Answer 1

Это имеет ту же сложность, что и распознавание голоса и жеста.Другими словами, вы никогда не можете быть на 100% уверены, что нашли все углы / соединения, и среди тех, кого вы нашли, вы никогда не сможете быть на 100% уверены, что они верны.Причина, по которой вы не можете быть абсолютно уверены, заключается в двусмысленности.Пользователь мог сделать один штрих, намереваясь создать две линии, которые встречаются под прямым углом.Но если бы они сделали это быстро, «угол» мог бы быть довольно круглым, поэтому он не был бы обнаружен.

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

Существует множество работ по сегментации эскизов каждый год.Это кажется очень простой проблемой, но это все еще открытая тема.Тот, который я использую, находится вне Техаса A & M, называется MergeCF.В этой статье хорошо изложено следующее: http://srlweb.cs.tamu.edu/srlng_media/content/objects/object-1246390659-1e1d2af6b25a2ba175670f9cb2e989fe/mergeCF-sbim09-fin.pdf.

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

Прошло много времени с тех пор, как я смотрел на новые сегментаторы, но я не думаю, что были какие-то прорывы.

ВВ моей реализации я использую кривизну медиана вместо означает в моем начальном пороге, что, кажется, дает мне лучшие результаты.Моя сильно измененная реализация здесь, которая, безусловно, не является чем-то отдельным, но она может дать вам некоторое представление.http://code.google.com/p/pen-ui/source/browse/trunk/thesis-code/src/org/six11/sf/CornerFinder.java