Выравнивание искажений в графических образах

[Kultura]

Помогите решить задачу:

Известно:
1) Имелся некий случайный набор точек, фигур или символов, основной характеристикой которого являлось горизонтальное расположение на плоскости в ряд. Самое простое - горизонтальная полоса.
2) Вносится искривление: каждая точка смещается в новую позицию действием искажающей функции.
3) Параметры искажающей функции не известны, их как раз и необходимо оценить. Впрочем, известно, что искажающая функция является гармонической.
4) Исходные данные - выборка из координат всех точек кривой картинки. (Т.е. для примера с горизонтальной полосой, имеем развивающийся флаг )

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

[Kultura]

Я недавно на форуме, возможно, не в ту тему отправил сообщение: т.к. задача не из стандартного курса. Может быть стоит переоформить в другом разделе?
Все ж таки речь идет о, на мой взгляд, чистой математике, неужели никто не встречался с подобным?

Математики, где вы, помогите решить!

[PAV]

Перемещено из "Помогите решить" в корневой раздел

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

[Kultura]

Да, линейный регрессионный анализ, когда-то проходили. Объясните , пожалуйста, подробнее, что бы понять, вспоминать его или нет:

"смещение каждой точки от "истинной" прямой случайно"

Здесь подразумевается изначальная прямая, или результат искажения? Мне предлагали использовать МНК для оценки параметров искажающей функции. Но пока что эта идея заглохла, т.к. этот метод требует знать вид функции, а в общем случае он не известен. Хотя и можно делать предположения, что ф-ия гармоническая, грубое приближение может и получиться.

[PAV]

Почитайте здесь

http://www.stat-msu.narod.ru/Tasks/task_6.pdf

Вообще же модель предполагает, что имеется некоторая "истинная" прямая $y(x) = ax+b$, а каждая реально наблюдаемая пара $(x_i,y_i)$ получена так $y_i=ax_i+b+\xi_i$, где $\xi_i$ - случайная величина, определяющая смещение данной точки от "истинной" прямой. Простейшая модель предполагает, что все смещения $\xi_i$ имеют нормальные распределения с нумевым средним и некоторой одинаковой сигмой. Есть и другие модели. Но я бы посоветовал попробовать, что дает МНК, даже не сильно глядя на модель, так как он хорошо работает при широких предположениях, а формулы там очень простые и реализовать их не составит труда.

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

[Kultura]

Не совсем понимаю основную идею. "Истинную" прямую мы знаем - это y = a, т.е. символы имеют горизонтальное расположение на плоскости в ряд. Или речь идет о линейной аппроксимации МНК?

Подготовил пример:

Ровное изображение

Искаженное


Если возможно, поясните на этом примере.

[PAV]

Нет, здесь регрессионный анализ не поможет.

Тут вообще все не так уж просто. Во-первых, здесь изображение смещается не только по вертикали, но и по горизонтали. Это видно по тому, что вертикальная палочка буквы q стала наклонной. Также похоже на то, что некоторые линии стали неодинаково толстыми. Так что преобразование для восстановления исходного написания должно быть более сложным. Возникает впечатление, что искажение осуществляется натягиванием картинки, нарисованной на резиновой пленке, на некоторую трехмерную поверхность.

Допустим, что мы пока забьем на горизонтальные искажения и попробуем восстановить только вертикальные, скажем, найдя нижние точки всех связных компонент и расположив их на одной линии. Но та же буква q тогда окажется поднятой. Таким образом, мы должны априорно знать, что у разных объектов точки, по которым их следует выравнивать, могут быть разными и не обязательно нижними.

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

Добавлено спустя 1 минуту 33 секунды:

А в чем состоит содержательная часть задачи, зачем нужно проводить такое восстановление. Обходить системы защиты от автоматической регистрации на интернет-ресурсах или еще что-то?

[Kultura]

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

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

О содержательной части. Вот здесь описание алгоритма, которым вносится искажение multiwave. Алгоритм этот используется на многих сетевых ресурсах. Очевидно, что обойдя его можно автоматизировать те действия, которые и были им защищены.
Надо сказать, с тех пор как я поставил перед собой такую задачу, уже успел почувствовать, что дело это какое-то тесное. Не важно, что именно нужно мне, но, например, материала в интернете почти нету, да и на форумах не спешат помогать.

[PAV]

Kultura в сообщении #171048 писал(а):

Хотя на глаз искажение четко просматривается, и все еще не хочется расставаться с мыслью, что есть некий хитрый ход.

На самом деле "на глаз" Вы производите следующие действия. Прежде всего, Вы распознаете написанный текст, искажение не мешает это сделать. Далее Вы используете имеющиеся у Вас априорные знания о том, как должна выглядеть каждая буква, для восстановления исходного изображения.

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

Если решать задачу обхода подобной защиты, то правильнее будет, ИМХО, сразу учить распознаватель читать искаженные символы, чем пытаться их восстановить.

Добавлено спустя 3 минуты 59 секунд:

А если бы это было так просто, то роботов уже давно научили бы подобные защиты обходить.

Я убежден, что сделать это вполне можно, но это хорошая и немаленькая исследовательская задача.

[worm2]

PAV писал(а):

Я убежден, что сделать это вполне можно...

...но не нужно
И так спасу никакого нет от спама. Слава богу, хоть не все капчи ещё поддаются взлому.
Я бы не стал помогать Kultura в таком "благородном" деле