Captcha - как искажать картинку?

Captcha - как искажать картинку?

от edren-baton автор: Lexa

Капчу видели все. В интернете тут и там предлагают ввести “буквы, изображенные на картинке”. В данной статье под капчей будут пониматься именно искаженные буковки. Хотя на самом деле за аббревиатурой скрывается куда более жестокий смысл: полностью автоматизированный публичный тест Тьюринга для различия компьютеров и людей (ПАПТТРКЛ, короче говоря).

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

Итак, я надел очки и принял умный вид.

Искажение изображения - это применение к нему преобразования. Наиболее естественными выглядят преобразование типа масшабирования и сдвига:

x' = a1x + b1
y’ = a2y + b2


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

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

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

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

Почти хороший вариант - это синус. Он и гладкий, и ограниченный. Но вместе с тем он еще такой банальный, что тошнит.

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

1. На интересующем нас отрезке выбираются случайно N точек, в которых значение функции генерируется случайно в допустимом диапазоне
2. В промежуточных точках интервала [xi, xi+1] функция будет полиномом 3 степени Si(x) = aix3 + bix2 + cix + di
3. Условия непрерывности запишутся как Si(xi+1) = Si+1(xi+1) = yi+1
4. Условия гладкости и ограниченности я выбрал очень хитро: S'(xi) = S’(xi+1) = 0

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

А еще, простота этих условий дает возможность вычислить 4 коэффициента полинома для каждого интервала независимо! Четыре уравнения для определения 4 неизвестных:

S(xi) = yi
S(xi+1) = yi+1
S’(xi) = 0
S’(xi+1) = 0


Maple дает решение:

Теперь можно поглядеть, как будут выглядеть такие функции. Построим кривую по 4 точкам [2, 4], [6, 6], [8, 1], [12, -1]:

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

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

Получилось вот это:

Тот самый эффект развивающегося флага, к которому все привыкли!

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

P.S. Иногда картинка получается не очень искаженной. Происходит это из-за того, что иногда кривые получаются не очень кривыми. То есть опорные точки надо выбирать все-таки не совсем случайно, а из каких-то условий, обеспечивающих нужную кривизну… Но искать эти условия мне уже лень.