Как решатель Meowdoku читает поле со скриншота
Решатель Meowdoku получает не саму головоломку, а её изображение. До решения ему нужно найти поле, определить число клеток и понять, какие из них имеют общий цвет. Здесь разобраны все решения этого конвейера и его ограничения.
Сложнее всего не распознать цвета
На скриншоте Meowdoku виден не только квадрат: там есть заголовок, подсказки правил, таймер и системная строка телефона. Поле — лишь квадратный блок в середине, положение и размер которого зависят от устройства, а подписей на изображении нет.
До чтения первого цвета нужно определить три неизвестных. Ошибка в любом из них даст не слегка неточный ответ, а уверенно решённую другую головоломку.
Всё выполняется в браузере
Скриншот никуда не загружается. Изображение рисуется на canvas, пиксели считываются, и все следующие шаги работают с этим массивом чисел в вашей вкладке. Сервер не видит и не хранит картинку.
Если изображение не отправляется, его не нужно хранить и потом удалять. Без сетевого запроса поле возвращается заметно быстрее секунды.
Сначала длинная сторона уменьшается максимум до 900 пикселей. Дальше нужен один характерный цвет клетки, а не резкая фотография; объём попиксельной работы падает пропорционально квадрату масштаба.
Шаг 1: найти поле
Сначала решатель оценивает фон. Он берёт полосу шириной 7% по четырём краям и вычисляет медиану каждого канала, заранее отбрасывая яркие пиксели, чтобы цветной баннер в углу не исказил оценку.
Затем пиксели делятся на фон и не-фон, а вторые считаются построчно. Получается профиль плотности: почти ноль на полях, высокий уровень на доске и средний в заголовке. Плотные последовательности становятся кандидатами. Узкие провалы от линий сетки соединяются, потому что линия в один пиксель не является разрывом; настоящее пространство над полем остаётся и исключает подсказки правил.
Главная проверка — квадратность. Каждый кандидат сканируется по другой оси и остаётся, только если ширина и высота различаются примерно не более чем на треть и занимают хотя бы 3% кадра. Баннеры и панели широкие и низкие; квадратным на скриншоте Meowdoku является поле.
Если квадрат не найден, решатель считает, что изображение уже обрезано до поля, и использует весь кадр. Это разумный отказ: картинку, которую нельзя локализовать, обычно и не требовалось локализовать.
Шаг 2: посчитать сетку
Положение поля не говорит, 7×7 оно или 9×9. Решатель проходит его за 400 шагов и измеряет изменение цвета, усредняя 48 параллельных линий по другой оси, чтобы один тёмный кот не выглядел границей. Края клеток проявляются регулярными пиками.
Вместо расстояния между пиками проверяются гипотезы. Для каждого N от 4 до 12 вычисляются позиции N−1 внутренних границ, ищутся близкие пики и оценивается совпадение. Побеждает N, лучше всего объясняющее профиль.
Оси измеряются отдельно и затем согласуются, ведь поле квадратное. Если по горизонтали вышло 8, а по вертикали 7, одна слабая линия пропущена и выбирается большее число.
Шаг 3: брать цвет по кольцу, а не в центре
После определения поля и сетки нужен цвет каждой клетки. Естественно было бы взять центральный пиксель.
Но именно в центре стоят кот и знак ✕. На частично решённом поле центральная выборка примет цвет символа за цвет клетки и создаст несуществующие регионы.
Поэтому берутся три кольца на расстоянии 28%, 36% и 43% от центра, по шестнадцать углов на каждом: 48 образцов. Кольцо лежит внутри границы, но снаружи значка. Медиана каналов отбрасывает редкие образцы на сглаженном крае или блике.
Шаг 4: разделить цвета ровно на N регионов
Теперь N×N цветов нужно собрать в регионы. Обычная сложность кластеризации — неизвестное число групп: неверная догадка незаметно ломает ответ.
В Meowdoku число задано правилами. Поле N×N содержит ровно N связных регионов; у 9×9 их девять, не восемь и не десять. Получается k-means с известным k, поэтому этот этап надёжнее двух предыдущих.
Начальные центры выбираются по принципу максимальной удалённости и распределяются по реальным оттенкам. Выбор детерминирован, поэтому один скриншот всегда даёт одно поле.
Затем регионы перенумеровываются в порядке чтения, начиная с содержащего левую верхнюю клетку. Решение от этого не зависит; данные лишь выглядят привычно.
Шаг 5: решить и проверить второе решение
Когда известны размер и регионы, используется тот же решатель ограничений, что и при создании полей. Важная деталь: он ищет два решения, а не одно.
У правильно прочитанного поля решение единственное. Два означают, что клетка попала не в тот регион; ни одного — что другое неверное чтение создало противоречие. Поиск второго ответа проверяет качество распознавания.
Где распознавание ошибается и зачем нужна кисть
Всё до шага 4 — наилучшая оценка, которая иногда ошибается. Типичные случаи:
- Два близких оттенка в сжатом скриншоте. Артефакты JPEG могут объединить два региона и разделить третий, чтобы сохранить N групп.
- Фотография экрана вместо скриншота. Съёмка под углом нарушает равный шаг клеток, подсчёт сетки и выборку по кольцу.
- Обрезка с частью интерфейса. Даже половина подсказки сдвигает рамку на несколько пикселей и переносит кольца в соседнюю клетку.
- Почти завершённое поле. Чем больше котов и ✕, тем больше закрыто. Кольца помогают, но не всесильны.
Кисть — часть решения, а не запасной выход
Поэтому любую распознанную клетку можно перекрасить перетаскиванием, а решатель не запускается, пока не будет ровно N разных регионов, и показывает текущее число. Этот барьер ловит ошибочное объединение или разделение до появления уверенного неверного ответа.
Поле рисуется цветами из вашего скриншота, а не стандартной палитрой, чтобы результат можно было проверить взглядом. Если клетка выглядит неверно, она неверна, и одно движение исправляет её. Распознавание делает скучные девяносто с лишним процентов; вы добавляете окончательное суждение.
Попробуйте на своём поле
Сделайте скриншот поля, на котором застряли, загрузите его и проверьте неверно прочитанные клетки. Ошибки почти всегда возникают в описанных здесь местах.
Решатель полностью работает в браузере. Скриншоты читаются на устройстве и никогда не загружаются.