Есть какой-то известный алгоритм, который превращает рисунки пользователя в сглаженные формы?

Question

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

Для начала я хочу преобразовать рисунок в прямоугольник, которыймаксимально напоминает оригинал.(Естественно, это не сработает, если пользователь намеренно рисует что-то еще.) Сейчас я вычисляю среднюю позицию по осям x и y и различаю горизонтальные и вертикальные линии.Но это еще не прямоугольник, а какие-то ортогональные линии.

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

Обновление: Может быть, мне поможет алгоритм распознавания образов.Есть несколько телефонов, которые просят пользователя нарисовать шаблон для разблокировки его клавиш.

PS: я думаю, что этот вопрос не связан с конкретным языком программирования, но если вам интересно, я будусоздайте веб-приложение с помощью RaphaelGWT.

Answer 1

Алгоритм Дугласа-Пекера используется в географии (например, для упрощения GPS-трека). Я думаю, его можно использовать и здесь.

Answer 2

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

• http://en.wikipedia.org/wiki/Vectorization_(image_tracing)
• http://outliner.codeplex.com/ - векторизатор краев в растровых изображениях с открытым исходным кодом.
• http://code.google.com/p/shapelogic/wiki/vectorization - описывает различные реализации алгоритма векторизации
• http://cardhouse.com/computer/vector.htm

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