Тема: поделки

CHICA

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

Вот, например, намедни ломали мы китайскую капчу.

Предвосхищая вопросы, сразу отмечу три факта:
- на всё про всё было потрачено 3 или 4 вечера, не считая разметки капч, которая занимала по 5 минут в день в течение 2-3 недель,
- нет, я не ломаю капчу на заказ и не планирую этим заниматься в будущем ;)
- целей никаких не преследовалось, это было for fun.

А дело было так:

Пришел ко мне как-то товарищ s0me0ne (с которым мы как-то раз делали 3d-ландшафты соли под микроскопом) и жалуется: я, говорит, постоянно что-то у наших заморских братьев с доставкой заказываю, всё время несколько заказов висят в процессинге. Ну и написал скрипт для мониторинга статусов заказов, делов то. Но с одной китайской службой промашка вышла — там, чтобы узнать статус, надо капчу решить. И непростую, а настолько суровую, что я даже глазами её не всегда разбираю:

Мне любопытно стало, и решил я её поломать.

О том и рассказ.

0. Дискляймер

Я, натурально, ненастоящий сварщик. Раньше капч я не ломал, да и в будущем не планирую. Некоторые навыки в ML и ImageProcessing, вообще говоря, у меня имеются, но скорее теоретический багаж, нежели жизненный опыт. Посему, я явно прошелся по нескольким классическим граблям, и результат вышел не слишком оптимальным, но зато вполне рабочим, чего мне в данном проекте вполне достаточно. В конце поста, однако, я постараюсь какие-то мысли в формате работы над ошибками написать, на тот случай, если кому-то понадобится.

И, да, кода я не выложу. Не потому, что жадный, а потому что код так себе по качеству, а алгоритмы я всё равно все опишу словами.

1. Знакомство с ChiCa

После первого приступа естественного изумления удалось сформулировать следующие впечатления.

Плюсы:
- Число символов постоянно.
- Фоновый градиент фиксирован.
- Положение букв по вертикали более-менее стабильно.
- Шрифт один и тот же.
Минусы:
- Добавлен мелкий шум (вроде, не страшный)
- Букв в алфавите около сорока (английские буквы + цифры + символы доллара, собачки и т.п.)
- Положение букв по горизонтали колбасит страшно. В частности, нередки случаи когда буквы сильно перекрываются.
- Буквам рэндомно меняется кегль, болд, италик.

2. Базовая чистка

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


дальше картинки буду зумить

Имея такую радость, несложно её вычесть, дабы получить что-то вроде:

Ну и цвет нам совершенно не нужен больше. А кроме того, для дальнейших плясок нам пригодится две картинки — контрастная ч/б-версия и серая с полутонами (не важно, черным по белому, или наоборот):


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

3. Вертикальная сегментация

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


я буду менять картинки периодически, чтобы не скучно было

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

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

4. Горизонтальная сегментация

Тут начинаются песни и пляски с бубном, ибо китайцам всё равно, налезли буквы друг на друга, или нет; и даже в случаях, когда просвет между буквами имеется, он не обязательно строго вертикальный (т.к. буквы бывают написаны италиком), например:

Поэтому, пришлось вспомнить дедушку Брезенхэма и пробивать каждую вертикаль несколькими линиями под разными углами (я проверял 4 угла с шагом dx в 1 пиксель, исходя из максимального наклона италика). Опять-таки, считаем плотность, но на самом деле нам интересно только, нулевая она или нет. Ну и, конечно, плотность мы смотрим по вертикали уже только в пределах зоны, ограниченной желтыми линиями, т.е. там где буквы живут.

Получаем местами вполне неплохой себе результат:

Но бывают и упячки разного рода:



Визуальный анализ упячек позволил придумать следующий набор правил:
- одиночные (изолированные с обоих сторон) красные точки — убираем, т.к. это скорее-всего шум,
- скользящим окном в 5 точек ищем случаи вида Х0ХХ00, доставляем точку, преобразуя их в ХХХХ00
- и, симметрично, 00ХХ0Х в 00ХХХХ.

В результате выходит значительно лучше:


Если же всё-таки сегментов оказалось более 4, то сортируем их по размеру и берем 4 самых больших.
Что же, однако, делать, если сегментов оказалось меньше 4? Есть некоторые шансы, что сегменты у нас склеились или сразу, или в процессе работы предыдущей эвристики:

Этому горю несложно помочь, если внимательно рассмотреть возможные случаи:
- У нас на выходе 3 сегмента — значит, слиплись какие-то 2 буквы. Режем самый большой из имеющихся сегмент пополам.
- У нас на выходе 2 сегмента — если один из них сильно (более чем в 2 раза) второго, значит, считаем, что в него слиплись 3 буквы и пилим его на 3 части. Иначе — каждый из 2 сегментов пилим пополам.
- У нас на выходе 1 сегмент — значит, нам повезло, и все 4 буквы склеились в 1. Делим наш сегмент на 4 равные части, т.к. больше нам тут поделать нечего.

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

5. Обучающая выборка

По причине того, что каждая буква в данной капче имеет больше десятка различных возможных написаний (с учётом болда, италика и кегля) решено было стрелять из перспетрона. Благо у меня как раз осталась его реализация под Octave после прохождения стенфордского ML-курса. Но персептрону нужно обучаться, и тут пришлось поработать неграм (в лице меня и s0me0ne).

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

Мы решали капчи (по паре-тройке десятков в день каждый) недели три. С учётом разнообразия символов было решено набрать 1000 размеченных капч (т.е. 4000 сэмплов), попробовать на них обучиться, а дальше действовать по обстоятельствам.

И тут… по всем законам жанра, в тот день, когда мы набрали 1000 сэмплов, КИТАЙЦЫ ПОМЕНЯЛИ КАПЧУ.

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

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

6. Персептрон

Дальше всё было несложно. Я порезал сэмплы описанным выше алгоритмом на “буквы”, снабдил их метками, которые мы расставили вручную, когда решали капчи, и выгрузил всю эту радость в Octave. Там я обучил стандартный персептрон с одним скрытым слоем — на входном слое было 195 нейронов (по числу пикселей в окне буквы 13х15). На скрытом я от балды поставил 30 нейронов, на выходном вышло 26, по числу распозноваемых букв. Обучение заняло минут 10.

Точность определения 1 символа на тестовой выборке получилась чуть больше 90% — т.е. если считать что точность определения 4 букв в капче независима (что не совсем правда, т.к. иногда гадит сегментация, а значит, портятся сразу несколько соседних букв), то вероятность корректного решения целой капчи вышла около 70%. На практике оценка подтвердилась.

Из обученного персептрона я выгрузил две матрицы параметров и зашил их в php-код. Кодить матричную арифметику с нуля самому было лень, PEAR я не люблю, в итоге я дернул пару полезных функций, кажется, отсюда. Собрал всё в кучку и наваял несложный единый скрипт. Работает он примерно так:

7. Мысли напоследок

Тут я хочу просто перечислить тонкие места и очевидные допущенные промашки:
* Начать сбор обучающей выборки можно было еще до того, как садиться за сегментацию — это хорошо распараллеливаемые процессы.
* После смены китайцами капчи нейросеть для распознавания символов в данном случае явно была оверкиллом. По идее, поиска по маске со словарём из двух масок (обычная и италик) на каждую букву должно было хватить. Просто я уже как-то настроился из персептрона пошмалять ;)
* По результатам кажется, что сегментация на символы, может быть гораздо более эффективно и универсально решена той же нейросетью. А так, это, конечно, заход солнца вручную получился :)
* Для того, чтобы не решать тысячи капч руками, по уму надо было подобрать шрифт (скажем, с помощью этого или этого сервисов), потом воспроизвести генератор и нагенерировать нужное количество сэмплов.

Вот такая история.

Tags: , , , , | 1 comment

ЗАКОЛДОВКА

Может, никто и не помнит, но года три назад я травил байку о совершенно обкуренной умозрительной игре, в которую мы с друзьями рубились в детстве, без преувеличения, годами. Забава эта называлась у нас “Заколдовкой” и, хотя и была почти полностью нашей выдумкой, изначально питала свои корни в детской настолькой игре “Заколдованная страна“.

А “Заколдованная страна” была первой настольной игрой где-то около ADnD-шного жанра, официально выпущеной в нашей стране. Она была издана ныне, кажется, почившим питерским кооперативом “Осень” в 1990 году и представляла собой довольно кривой перевод польской настольной игры (название утеряно), которая, в свою очередь была слизана поляками с системы ADnD.

Так вот, несколько лет назад я наткнулся на пост в журнале товарища Enjoy, где он выложил все отфотографированные материалы игры (а это игровое поле, три книжки правил и сто карточек существ). Качество снимков было никакое, но благодоря упорству и помощи таких доблестных соратниц как Marmil, Nightiny и Dalena, мне удалось практически польностью восстановить бумажный комплект игры в 2 (двух) экземплярах. Один из них я подарил на позапрошлый день рождения товарищу sirNik-у (с которым в детстве мы наиграли в неё несметное число часов, дорисовывали замки и карточки, дописывали правила и уровни заклинаний и т.п.), а второй положил к себе на полку.

Забрать архив всех восстановленых материалов, готовый к распечатке, можно тут (осторожно, 35 мб), или с зеркала.

Основные отличия восстановленой версии:

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


Tags: , , , | Make a comment

BULLSHIT BINGO: ПРОШЛОГОДНИЕ НОВОСТИ

Лучше поздно, чем никогда. Рассказываю.

В прошлом году мы с соратником Neyro сделали локализацию замечательной игры Bullshit Bingo. Русская версия носит название Ерунда-ЛОТО и доступна по адресу http://e-loto.altsoph.ru/

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

Tags: , | Make a comment

ГУГЛ СЧЁТЫ / ЯНДЕКС СЧЁТЫ

Меж делом обнаружен и заполнен значимый пробел в широком спектре современных WEB2.0 сервисов.

Вашему вниманию представляется:






Tags: , , | Make a comment

MIMIC GOES TO JABBER

TWIMC.

Намедни общался с Мимиком, он просил передать всем знакомым, что его так долго не видно в асе, потому что он давным-давно перешел на jabber и доступен по адресу mimicq эт jabber дот ру.

Tags: , , , | Make a comment

MICROSALT

А на минувших выходных мы поехали к товарищу s0me0ne-у, ибо у него недавно был день варенья.

В числе прочего s0me0ne получил в подарок от жены настоящий мелкоскоп. s0me0ne микроскопу зело обрадовался и купил к нему вебкамеру, которая крепится на видоискатель. Правда, дров на неё под линукс не нашлось, поэтому s0me0ne написал свои, добавив заодно билинейную интерполяцию цвета из Байеса, выдаваемого камерой.

Так, как к нашему приезду s0me0ne мелкоскопом баловался уже недели две, то нам сразу же была продемонстрирована стандартная программа: свежевырванный волос, капля крови, лист растения и прочая мура.

Тогда я сказал «к чёрту органику! Даешь фракталы!» и потащил s0me0ne-а на кухню, где мы стали выращивать кристаллы соли из насыщенного раствора. Растили мы их часа три, используя при этом микроволновку, гитару, стопку и очередной свежевырванный волос. Потом мы эти кристаллы долго скриншотили с бреккетингом по фокусу, так как ГРИП на таком зуме – ни к чёрту.

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

Итак, кристаллы соли с 400-кратным увеличением:

микросоль

…далее еще 5 фото и 2 видео…

Continue reading

Tags: , , , , | Make a comment

Луч-ВТ + uniboard + Touch Diamond

Приобрел себе на прошлой неделе bluetooth-клавиатуру (Луч-ВТ компакт) для КПК (Touch Diamond aka HTC P3700). На многочисленных сайтах магазинов была заявлена совместимость, так что я смело заказал данную приблуду (на условиях недельной возможности возврата).

И привезли. И началось.

Дальше идут жёсткие описания технических извращений, так что дальше лучше и не читать, вот.

Continue reading

Tags: , , , | 4 comments

ЧЕТЫРЬМЬЮСТАМИ СОРОКОМ ЧЕТЫРЬМЯМИ

Для одного из проектов пришлось написать библиотеку для формирования “прописи” числа в заданном падеже.

Полная документация, исходники и примеры в архиве (15кб) здесь:
http://altsoph.ru/stuff/prjs/php/numsamp_v1.4b.zip
Поиграться можно здесь:
http://altsoph.ru/stuff/prjs/php/ns_test/numbersampling.php

Continue reading

Tags: , , , | 6 comments