Пример внедрения инноваций

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

Год назад мы с моим другом Алексеем были в финале командного шахматного турнира. Когда на часах оставалось пять минут, вокруг меня заполнили огромные камеры местного телевидения. После блицкрига ходов он у меня был! Шах и мат?

Оказывается, я зря пожертвовал ладью, и матч был проигран. Алекс сказал: «Похоже, еще одна ночь в темной комнате со Stockfish». (Обычный шахматный движок). У меня не было желания открыть свой ноутбук, ввести эти движения и заново пережить самые мрачные моменты. Но мои опущенные глаза внезапно вспыхнули: почему бы не сделать систему, которая сканирует ведомости и оцифровывает их? Алекс был так же взволнован, и квест начался.

Представляем Рейне

Сегодня мы представляем Reine: сканер шахматных таблиц с открытым исходным кодом, который можно легко адаптировать для других целей сканирования почерка. В настоящее время у шахматистов есть два варианта: один - записывать ходы во время игры, а затем вручную вводить их в компьютер. Этот ввод вручную может занять до 30 минут для всего турнира или 4–5 часов, чтобы директор турнира начал все игры. Другой вариант - приобрести цифровой шахматный рекордер за 500 долларов, одобренный Шахматной федерацией США (MonRoi или Plycounter). Теперь Reine позволяет сканировать одну игру менее чем за 10 секунд.

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

Предварительное планирование

Вначале мы задали себе несколько ключевых вопросов: почему наша идея не была реализована раньше? Что в этом сложного? Что мы можем сделать, чтобы смягчить эти проблемы?

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

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

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

Построение модели

Если вы еще не догадались, мы будем использовать CNN, обученную EMNIST, для распознавания символов. Но как добиться максимальной точности? При 62 классах очень сложно добиться высокой точности!

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

Как мы решили, что пяти символов на слой * будет достаточно? База данных из 20 000 игр Lichess была проанализирована на предмет количества персонажей на ход, и мы пришли к следующему распределению:

* Фрагмент - это один ход для одной стороны или половина хода (например, «d4»).

Мы можем выполнить 99,9% ходов с максимум пятью персонажами. Мы не хотим игнорировать более длинные ходы, но это можно решить, посмотрев на общие возможные форматы ходов для каждого количества символов:

Возникает один очень полезный паттерн: если мы игнорируем проверки, последние два символа любого хода ДОЛЖНЫ обозначать квадрат на шахматной доске - строчную букву, за которой следует число. Кроме того, ходы длиной 6 символов становятся длиной всего 5 символов. Таким образом, мы решили: не ставьте «+» за чеки на бланке Рейне!

Кроме того, 99% пешек превращаются в ферзей, поэтому мы предполагаем, что любая пешка, достигшая любого конца доски, превращается в ферзя. Таким образом, 7 ходов персонажа уменьшаются до 4 ходов персонажа - и ни один ход не требует более 5 символов, чтобы отметить его в протоколе Рейна. Благодаря этим настройкам более длинные ходы не будут игнорироваться.

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

Давайте сначала перейдем от картинки смартфона к списку предсказанных персонажей - это важная часть.

Шаг 1. Выровняйте изображение

Мы хотим использовать маркеры «ArUco» в четырех углах здесь, чтобы выровнять это изображение, так что все, что мы видим, - это ходы. Импортируем все, что нам понадобится для всего проекта:

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

  1. Найдите маркеры ArUco со встроенной функцией, в данном случае маркеры 4x4. Эта функция возвращает несколько значений для каждого маркера (координаты и идентификатор маркера), поэтому функция get_data() дает нам только координаты.
  2. В документации OpenCV описывается функция get_transform(): «Для преобразования перспективы вам понадобится матрица преобразования 3x3…. Чтобы найти эту матрицу преобразования, вам понадобятся 4 точки на входном изображении и соответствующие точки на выходном изображении ». Функция cv.getPerspectiveTransform() находит матрицу, а cv.warpPerspective() использует ее для настройки перспективы изображения.

Шаг 2. Удалите тени

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

  1. Расширьте и размывайте изображение по центру, чтобы избавиться от тонких линий (текст, почерк, линии сетки).
  2. Вычтите это новое изображение из исходного изображения, существенно вычтя тени.
  3. Шаг 1 не идеален, поэтому все будет светлее исходного изображения. Нормализуйте, чтобы увеличить контраст.

Вот - код, который мы использовали.

Вот что у нас есть сейчас:

Шаг 3. Разрезайте коробки

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

1. Определите горизонтальные и вертикальные ядра, которые вы по существу проведете по всему изображению, ища горизонтальные и вертикальные линии.

2. Создайте новый образ из этих ядер вместе.

3. Расширьте и затем удалите (то есть закройте) все линии. В противном случае findContours() функция не сможет правильно определить контуры с неровными краями или отсутствующими пикселями. Это наше дополнение - поскольку мы не можем прочитать то, что не можем видеть, обязательно, чтобы были учтены ВСЕ 500 ящиков (количество возможных символов в нашей таблице). Мы добавляем эти строки к нашему изображению перед использованием функции findContours().

4. Наконец, отсортируйте поля слева направо, сверху вниз. Разумеется, мы сортируем левую и правую половины протокола отдельно. Это замена данной функции get_contour_precedence() в статье Medium, которая выполняет сортировку только сверху вниз.

5. Сортировка: сортировка сверху вниз выполняется с помощью функции, показанной непосредственно ниже. Переменная row_y имеет 25 значений y (для 25 ходов / строк) - значения y контуров будут близки ровно к одному из этих значений. Отсюда сортировка выполняется слева направо с использованием границ, заданных cv.boundingRect(), и отдельно для каждой половины листа.

И вот мы здесь:

А вот ЭМНИСТ выглядит так!

Шаг 4. Предварительная обработка наших данных

Нам повезло - в документе, который резюмирует создание набора данных EMNIST из правительственного набора данных NIST (который содержит естественные символы, подобные тем, которые мы разрезали), объясняется, как предварительно обработать каждый символ:

Мы делаем следующее:

  1. Измените размер символов до 138x138. Поскольку прямоугольники больше в высоту, чем в ширину, мы добавляем горизонтальные пробелы, чтобы сохранить пропорции символов.
  2. Инвертируйте изображение.
  3. Пороговое значение входного изображения, сделав его только черно-белым.
  4. Примените размытие по Гауссу, чтобы уменьшить неровность и шум.
  5. Отрежьте несколько линий снаружи так, чтобы ни одна из линий сетки не входила в исходные данные модели. Теперь у нас есть изображение 128х128.
  6. Центрируйте изображение по массе.
  7. Несколько раз удалите по одному пикселю с каждой стороны, пока все пиксели границы будут черными. Примечание: поскольку для более крупных символов удаляется меньше пробелов, они будут иметь более тонкие штрихи после изменения размера до 28x28 и наоборот. Это причина для шага 8.
  8. Мы добавляем один шаг, которого не было в документе EMNIST: после удаления черных пограничных пикселей мы стираем меньшие изображения и расширяем большие изображения так, чтобы ширина штриха была пропорциональна размеру изображения. (Это значительно улучшило результаты.)
  9. Добавьте отступы 2 пикселей, как указано в документе EMNIST.
  10. Измените размер изображения до 28x28. Используйте метод «бикубической интерполяции» для создания дисперсии в белых тонах (т.е. край штриха светлее его центра). Это важно при распознавании символов, потому что информация о краю штриха сообщает модели, где заканчивается символ.

Этот фрагмент кода содержит всю предварительную обработку вместе с комментариями:



Шаг 5. Распознавание

С 62 классами лучшая точность EMNIST, которую мы обнаружили, была ниже 90%, даже для набора для валидации. Настоящий почерк будет хуже. Рассматривая обобщенные возможности игнорирования проверок, мы можем решить эту проблему, ограничив классы только теми персонажами, которые действительно могут появляться в каждой позиции шахматного хода:

Вот модели, которые нам нужны, и улучшения по сравнению с исходной точностью случайной классификации 4%, которая была бы у вас с 25 классами:

Каждая модель теперь имеет значительно уменьшенное количество классов - и, следовательно, более высокую точность. (Примечание: модель «Letter» не включает «x», а модель «number» включает «O» для учета рокировки.)

Теперь у нас есть символы, похожие на набор данных EMNIST, и мы точно знаем, какие классы использовать для нашей CNN. Нам просто нужно их обучить. Вы можете использовать любую модель, какую захотите: ансамбль, одну CNN или поэкспериментировать с разным количеством эпох.

Однако для нас были особенно важны два аспекта: выбор только необходимых персонажей EMNIST для обучения и увеличение данных. Мы использовали это ядро ​​Kaggle, но со следующими необходимыми настройками:

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

2. Пополнение данных. Поскольку во время игры в шахматы люди будут писать беспорядочно, мы не знаем, что постобработка даст нам идеальное соответствие типа EMNIST. Это особенно верно, если люди пишут под углом или сильно утяжеляют символ в одну сторону (вмешиваясь в центрирование масс при предварительной обработке). Итак, мы хотим, чтобы аугментация выглядела примерно так:

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

Наш код с частыми комментариями можно найти здесь, но, за исключением вышеуказанных изменений, он не сильно отличается от стандартной процедуры EMNIST + CNN.



Шаг 6. Постобработка (последний!)

Нашу постобработку лучше всего пояснить на примере:

Модель дает нам уверенность в каждом возможном символе в каждой коробке. Он мог бы сказать, N-90%, K-10%, B/R/Q-0% для одной из коробок с «штуками». Мы проверяем каждый возможный ход, составленный персонажами, которым наша модель приписывает достаточно высокую степень достоверности. (Проверяем как минимум 2 верхних символа, независимо от уверенности). Например, рассмотрим последовательность ходов 1. d4 d2. Черные не могут сыграть d2 на первом ходу! Но мы смотрим на следующие наиболее вероятные прогнозы, возможно, d3 для белых и d5 для черных. Правильный ход должен быть одним из следующих:

1.d4 d2

1.d4 d5

1.d3 d2

1.d3 d5

Действительны только 1.d4 d5 и 1.d3 d5, поэтому мы игнорируем два других и переходим к следующему ходу.

Теперь рассмотрим код, который можно найти здесь:



Постобработка состоит из двух основных этапов:

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

Шаг 1 довольно интуитивно понятен. Мы начинаем с фильтрации маловероятных символов для каждого поля (как объяснялось ранее). Затем мы используем функцию itertools.product(), чтобы найти все возможные комбинации этих символов (то есть ходов).

Прежде чем мы начнем проверять, действительны ли эти ходы, мы дополнительно уменьшаем количество ходов, которые мы должны проверить: мы использовали пять различных моделей из-за ограничений на то, какие персонажи могут находиться в данной позиции для хода, и есть дополнительные ограничения, основанные на другие персонажи в движении. (В то время как «Bbc5» и «bxc5» - допустимые ходы, «bbc5» - нет!) Следующая функция исключает такие недопустимые ходы:

Далее идет шаг 2: поиск всех возможных легальных игр. Библиотека Python Chess [LINK] здесь полезна, и мы используем ее объекты Board, которые представляют одну шахматную позицию (шахматисты знают их как FEN). Мы сжалились над нашей оперативной памятью (но немного пожертвовали скоростью), неоднократно вызывая функцию для обновления глобальных переменных на пошаговой основе.

В следующем коде доски содержат списки «ходов», которые представляют собой списки всех досок, которые действительны для этого номера хода (boards[0][0] был инициализирован в начальную позицию). Глобальный pgn структурирован аналогично, но содержит списки ходов, сделанных для достижения этих досок (объекты Board хранят только данные о положении).

Выполните check_iterative() один раз для каждого слоя, и в результате вы получите PGN. Все, что осталось, - это формальность переформатирования ходов в красивую строку PGN и, наконец, файл .pgn, который выглядит так:

Оказалось, что в этой таблице было две ошибки, что дало нам точность более 96%. Исправьте несколько ходов, откройте в графическом интерфейсе шахматного движка и…

Ta-da!

Спасибо за прочтение! Напишите нам по адресу [email protected] или [email protected], если вы хотите принять участие или у вас есть какие-либо вопросы. Электронная почта нашей компании - [email protected], если у вас есть деловые вопросы. Удачи в реализации вашей следующей революционной идеи!

Вот веб-сайт проекта:



Здесь вы можете найти открытый исходный код:



Сообщение в блоге Chess.com: chess.com/blog/ReineChess/scannable-scoresheets-free



Сообщение Hacker News (# 1 на Show HN!):



~ Ритвик Судхарсан и Алекс Фунг

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

Независимая редакция, Heartbeat спонсируется и публикуется Comet, платформой MLOps, которая позволяет специалистам по обработке данных и группам машинного обучения отслеживать, сравнивать, объяснять и оптимизировать свои эксперименты. Мы платим участникам и не продаем рекламу.

Если вы хотите внести свой вклад, отправляйтесь на наш призыв к участникам. Вы также можете подписаться на наши еженедельные информационные бюллетени (Deep Learning Weekly и Comet Newsletter), присоединиться к нам в » «Slack и подписаться на Comet в Twitter и LinkedIn для получения ресурсов, событий и гораздо больше, что поможет вам быстрее и лучше строить модели машинного обучения.