Sudoku Hunter

В последнее время наш блог молчит и может показаться, что «Карандаш и Самоделкин» все, сдулись. На самом деле работа кипела, а отсутствие публикуемых материалов было связано с тем, что проекты раз за разом становятся все сложнее и требуют все больше времени на реализацию. Последние наши разработки были так или иначе связаны с нейросетями, поэтому логично было за это время подтянуть скиллы по этой теме, что и было сделано – был пройден ряд онлайн курсов по и даже пара оффлайновых, из которых особенно понравилась «Зимняя школа машинного обучения» (Machine Learning Winter School).

Проект, работа над которым шла больше 4 месяцев, мы назвали Sudoku Hunter. Изначально была идея собрать робота по мотивам NXTSudokuSolver, однако постепенно она трансформировалось в нечто иное, на наш взгляд не менее интересное.

Итак, Sudoku Hunter – это пистолет с EV3, веб-камерой и Raspberry Pi на борту, из которого можно «стрелять» по математическим головоломкам судоку, получая на экране EV3-блока их решение. В алгоритмической части используются технологии машинного зрения и машинного обучения, веб-технологии для создания отладочной видеоконсоли.

Если кто не помнит, судоку - головоломка на бумаге, игровое поле которой представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

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

• Блок Lego Mindstroms EV3 и строительные детали из этого набора
• Raspberry Pi
• Веб-камера Sony Playstation Eye
• Wi-fi адаптер для связи EV3 с RPi
• Powerbank для питания RPi

Программ, которые необходимы для работы робота - несколько, все они написаны на Python:

• Программа для EV3 - отвечает за вывод информации на экран блока, связь с Raspberry Pi, передачу на RPi состояния датчика-кнопки
• Программа для Raspberry Pi - отвечает за обработку кадров с камеры, распознаванием цифр с использованием обученной нейросети, последующим решением распознанного судоку, связь с EV3, вывод вспомогательной и отладочной информации на веб-консоль,
• Программа для Raspberry Pi, предназначенная для создания дата сета для обучения нейронной сети.
• Программа для ПК, используется для создания и обучения нейросети на основе подготовленного дата сета

Основная программа для Raspberry Pi работает по следующему алгоритму: 

• Подключение библиотеки машинного зрения OpenCV

• Подключение библиотек машинного обучения keras(tensorflow), sklearn

Процесс 1:

• Взятие кадра с камеры

• Преобразование изображения из BGR в HSV 

• Наложение маски для фокусировки на значимых элементах изображения

• Запись результирующего кадра в объект в памяти

• Соединение с EV3 с помощью протокола socket 

• Основной цикл:

• Чтение кадра из объекта в памяти

• Поиск в изображении с наложенной маской объектов, напоминающих квадрат 

• Передача данных о предполагаемом расположении квадрата на EV3, для вывода на экран блока

• Приём данных с EV3 о состоянии кнопки 

• Если кнопка нажата:

Процесс 3:

• Запуск веб-сервера (используется модуль Flask)

• Соединение с Raspberry Pi с помощью протокола socket

• Получение данных о предполагаемом расположении квадрата 

• Подключение библиотеки машинного зрения OpenCV

• Подключение библиотек машинного обучения keras(tensorflow), sklearn

Процесс 1:

• Взятие кадра с камеры

• Преобразование изображения из BGR в HSV 

• Наложение маски для фокусировки на значимых элементах изображения

• Запись результирующего кадра в объект в памяти

• Соединение с EV3 с помощью протокола socket

• Чтение кадра из объекта в памяти

• Поиск в изображении с наложенной маской объектов, напоминающих квадрат 

• Передача данных о предполагаемом расположении квадрата на EV3, для вывода на экран блока

• Приём данных с EV3 о состоянии кнопки 

• Если кнопка нажата:

• Запуск веб-сервера (используется модуль Flask)

• Вывод информации на веб-сервер - видеоконсоль для удобства отладки

• Подключение библиотек машинного обучения 

• Загрузка дата сета изображений 

• Разбиение дата сета на учебные и тренировочные данные

• Создание нейронной сети с заданными параметрами 

• Обучение нейронной сети

• Сохранение модели 

Процесс 2:

• Изображение обрабатывается и судоку «нарезается» на 81 квадрат в каждом из которых одна клетка головоломки 
• Каждый из фрагментов проверяется на наличие в нём цифры и если цифра обнаружена, то клетка подаётся на распознавание нейронной сети 
• Распознанная цифра заноситься в массив. Когда массив заполнен всеми цифрами, он подаётся в алгоритм, решающий судоку 
• Массив содержащий решённую головоломку передаётся на EV3 для вывода на экран блока 

• Вывод информации на веб-сервер - видеоконсоль для удобства отладки

Программа на EV3 работает по следующему алгоритму:

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

Программа создания дата сета для обучения нейронной сети на Raspberry Pi имеет следующий алгоритм:

Процесс 2: 

• Изображение обрабатывается и судоку «нарезается» на 81 квадрат в каждом из которых одна клетка головоломки 
• Каждый квадрат сохраняется в папку, формируя дата сет

Процесс 3:

Программа на ПК, предназначенная для создания и обучения нейросети на основе подготовленного дата сета работает так: 

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

Исходные коды всех программ проекта мы выложили здесь: https://github.com/darkavengersmr/Sudoku-Hunter

Демонстрация работы робота: