Доббль: практичный подход с OpenCV и NumPy +8


AliExpress RU&CIS

О чём мы вспоминаем в первую очередь, когда слышим про распознавание образов? Сложные нейронные сети, мощные видеокарты, объёмные наборы данных. Всего этого не будет в моей истории - я расскажу, как с помощью OpenCV и NumPy можно за 1 вечер решить задачу классификации 57 символов из игры Доббль, используя менее 500 их изображений без дополнительной аугментации. Разный масштаб, произвольный угол поворота - всё это не имеет значения, когда для описания символа достаточно четырёх чисел.

Эта история произошла весной 2020 года, во время вынужденной самоизоляции. Я смотрел ролики на youtube и наткнулся на интересную игру - Доббль, или по-другому SpotIt. В местных магазинах я вряд ли смог бы её найти, а в условиях самоизоляции вариант с заказом тоже выглядел довольно призрачно. В результате нашёл в сети файл с изображениями карточек, распечатал на плотной фотобумаге и вырезал - получился довольно аккуратный набор. Сыну игра понравилась, стали играть.

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

И тут на Хабре обнаружилась статья "Как я научила свой компьютер играть в Доббль с помощью OpenCV и Deep Learning". Казалось бы, вот оно - решение, но… Проанализировав код, я понял, что у подобного решения есть два фатальных недостатка - нарезка и разметка такого количества картинок займет слишком много времени, а тренировка модели на машине с неподдерживаемой видеокартой продлится еще дольше. Стал думать.

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

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

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

Один из неудачных вариантов автоматической разметки
Один из неудачных вариантов автоматической разметки

Потом я обучил нейросеть - многослойный перцептрон (MLP). Сеть сделал на основе учебного примера из книги "Python Machine Learning" Себастьяна Рашки, для её реализации достаточно пакета NumPy.

В качестве входных данных использовал список файлов с символами - содержащейся в нём информации достаточно для обучения сети. Название папки с символами начинается с двузначного числа - номер символа, используем его как метку. Имя файла содержит 4 числа, соответствующие параметрам символа. Значение всех параметров оказалось в пределах 45..255, поэтому для полного использования диапазона 0..1 вычитаем из них 45 и делим на 210. Так как данных мало, в качестве тестового набора используем часть тренировочного. В списке 440 файлов, время обучения составило около 1 минуты.

И всё равно в результате проверки идеи выявились коллизии, не дающие правильно опознать символ. Пришлось добавить еще один параметр - отношение площади символа к площади описывающего его прямоугольника (я назвал его "плотность"). В результате этот параметр оказался очень полезным, от одного из цветовых каналов удалось избавиться. Единичные символы теперь распознавались устойчиво по четырём признакам.

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

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

Проверка работы нейросети
Проверка работы нейросети

Ради интереса проверил производительность - полный проход по колоде из 55 карточек (1485 комбинаций) занял 170 секунд, ошибок 0. Была идея сделать распознавание карточек по изображению с веб-камеры, но оказалось, что они сильно бликуют. Кроме того, у сети выявился недостаток - она сильно чувствительна к понижению разрешения картинки: мелкие детали (например, лучи снежинки) сливаются и это приводит к изменению параметров. Но сделать на ней игру с поиском совпадений по двум карточкам можно. Или использовать уже размеченные изображения символов для создания полноценного датасета и тренировки свёрточной нейронной сети.

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




Комментарии (2):

  1. LoadRunner
    /#22540976

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

  2. Dinxor
    /#22544160

    За это же время можно было глазами найти недостающую карточку, разве нет?

    Попробую посчитать. Допустим, я взял новую колоду из 55 карточек и последовательно сравниваю каждую карточку из нее с каждой карточкой из старой колоды (54 карточки). Если они одинаковые — откладываю обе в сторону и перехожу к следующей карточке из новой колоды.
    Очевидно, при полном проходе было бы те же 1485 сравнений. В среднем совпадение будет находиться в середине второй колоды — делим на 2, 742 сравнения. Допустим, в середине первой колоды нашлась карточка, у которой нет пары — я её нашёл! Делим ещё на 2, 371 сравнение. За час это 9,7 секунды на проверку каждой пары карточек. Да, думаю глазами бы нашёл, но это утомительная однообразная работа.
    С другой стороны, за тот же час я разметил датасет и вручную переименовал папки с файлами. Это позволило мне проверить идею с обучением нейросети на малом числе параметров, из имеющихся материалов можно сделать игру (начал, но пока не доделал). Может, мой опыт ещё кому-то пригодится.
    Да, по горячим следам возникла идея — неплохо было бы нарезку файлов совместить с сортировкой не по одному, а по всем четырём имеющимся параметрам — можно сделать полноценную кластеризацию, только пока не разобрался как.
    В общем, думаю, что я не зря потратил время.