Взлом капчи

0xFF) - (($color2 >> 8) & 0xFF), 2) +
pow(($color1 & 0xFF)

- ($color2 & 0xFF), 2));
}

// Создание маски изображения, выделяющей пиксели, отстающие от белого фона
// больше чем на 200 единиц
protected function update_mask()
{
$this->mask = array();
for ($i = 0; $i < $this->width; $i++)
for ($j = 0; $j < $this->height; $j++)
$this->mask[$i][$j] = $this->colordist(imagecolorat($this->image, $i, $j), $this->bg_color) > 200 ? 1 : 0;
}
…
}

Маска, во-первых, выполняет роль упомянутого выше фильтра по яркости, а, во-вторых, увеличивает

скорость работы с изображением — нет необходимости каждый раз выполнять преобразования при сравнении цветов пикселей.

Поиск надписи

Основной принцип, на котором основаны надежные капчи, — затруднение выделения отдельных символов в надписи. Это достигается путем смещения символов относительно их первоначальных позиций и искажений надписи в целом. В капче сайта xakep.ru расстояния между центрами цифр (~19 пикселов) и размеры самих цифр (16x24 пискселов) практически не меняются. Из всех искажений, применяемых к надписи, значительный эффект оказывает только наклон шрифта — им нам пренебречь не удастся. Если бы не шумовые линии, мы бы смогли сразу точно определить расположение цифр на изображении путем отсечения светлых участков со всех четырех сторон — наши цифры были бы единственным темным пятном. Но придется решить небольшую оптимизационную задачу.

Задача оптимизации в общем виде состоит в поиске оптимального значения параметров некоторой целевой функции, значение которой необходимо максимизировать или минимизировать. В нашем случае целевой функцией будет суммарная яркость (точнее её обратное значение) области предполагаемого расположения надписи. Другими словами мы будем стараться найти на изображении темное пятно, по форме напоминающее нашу надпись (нам известны размеры цифр и расстояния между ними). Итак, у нас есть 4 прямоугольника, которые при наличии наклона шрифта превращаются в параллелограммы, необходимо найти такое расположение этой группы параллелограммов и такой наклон, чтобы минимизировать суммарную яркость внутри этих параллелограммов. В итоге у нас есть три параметра: x, y (левый верхний угол первого параллелограмма) и d — сдвиг нижнего основания относительно верхнего. Такой метод поиска надписи будет эффективен для не слишком зашумленных линиями изображений, о которых мы и говорили выше.

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

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

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

параметрами второго). Отбор особей для создания нового поколения осуществляется по принципу естественного отбора — чем выше значение целевой функции (приспособленность) особи, тем выше вероятность её перехода в новую популяцию. После создания нового поколения вновь проводится оценка каждой особи, выявляется лучшая и проверяется условие остановки. Если цель всё ещё не достигнута, создается очередная популяция и т.д. В нашем случае решением является вектор из трех переменных x, y и d, а целевая функция — суммарная яркость пикселов внутри параллелограммов.