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

Как оцифровать сканворд по фотографии? Насколько сложно сделать систему общего доступа? Действительно ли интересно разгадывать бумажные сканворды на электронном устройстве? Ответы на эти и другие вопросы — под катом.

Приглашаем 10 октября на Selectel Tech Day
Расскажем о новинках на рынке и обновлениях в наших продуктах. Вас ждут доклады, нетворкинг, мастер-классы и вечерняя программа. Участие бесплатное, но нужно зарегистрироваться.

Используйте навигацию, если не хотите читать текст полностью:

→ Мотивация проекта
→ Распознавание игрового поля
→ Веб-интерфейс
→ Мультиплеер
→ Демонстрация

Мотивация проекта

«Дедовские» технологии.

Это началось спонтанно. Друзья переслали в чат мем про старость и бумажные кроссворды, а потом… начали его разгадывать. Сначала Настя решала все, что могла. Если не знала ответа, то запрашивала нашу помощь. Гораздо интереснее подкидывать загадки другим людям, а не искать ответ в бездушном поисковике. Вскоре мы начали решать сканворды полностью коллективным разумом.

К сожалению, «бумажный» формат накладывал некоторые ограничения.

• Владелец оригинала должен следить за нашими сообщениями и вписывать варианты ответов.
• Бумага не прощает ошибок. Можно, конечно, использовать карандаш, но все равно останется грязь.
• «Удаленщики» не получают обновлений в режиме реального времени. Владелец должен каждый раз делать новую фотографию игрового поля.

В общем, за социальное взаимодействие и мозговую разминку — определенно «пятерка», а вот удобство нужно доработать.

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

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

1. Автор фотографирует страницу.
2. Система распознает игровое поле и строит его электронную версию.
3. Автор делится ссылкой на электронное игровое поле.
4. Каждый игрок заполняет свои ответы и видит, что и как заполняют другие.

Основополагающий момент — распознавание игрового поля по фотографии. Без «контента» кооперативный кроссворд будет просто «технодемкой», а составители кроссвордов вряд ли поделятся машиночитаемыми исходниками.

Распознавание игрового поля

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


Задача полегче: судоку. Источник.

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

• Вопрос на StackOverflow по определению разделительных линий в судоку.
• Потенциальный решатель судоку по фотографии с использованием распознавания цифр.
• Распознаватель кроссвордов, который не полностью справляется со своей задачей. Вопрос не решен.
• Магистерская ВКР из университета Коломбо (Шри-Ланка): End-End Automated Crossword Puzzle solver using image processing, NLP and neural network.

К сожалению для меня, в магистерской работе автор уделяет внимание обработке естественного языка (NLP), а распознаванию поля кроссворда — менее страницы. К тому же технология распознает кроссворд не с фотографии, а со скриншота, который сразу содержит игровое поле.


Определение линий.

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

В общем, идея не сработала и пришлось перечитывать источники в поисках упущенных знаний. Так и оказалось. В магистерской диссертации и нерабочем распознавателе кроссвордов использовалась функция поиска контуров findContours. Гениально! Вместо непонятных линий можно искать ячейки «изнутри».


Преобразования до обнаружения контуров.

Для успешного распознавания нужно выполнить несколько шагов.

1. Уменьшить входящую картинку (desampling) — в нашем случае до 1024 пикселей по большей грани. Перевести в оттенки серого и размыть по Гауссу с ядром 3х3.
2. Применить оператор Кэнни для определения краев (Canny Edge Detector).
3. Применить операцию dilate, чтобы расширить распознанные грани.
4. Применить операцию erode для сужения граней. В результате получаются более тонкие грани с меньшим количеством шума.
5. Вызвать функцию findContours на изображении после всех преобразований. На примере выше контуры находятся поверх оригинальной фотографии.

Преобразуем шаги в код на Python:

import cv2

def resize(img, size=1024):
    x = img.shape[0]
    y = img.shape[1]
    factor = max(x / size, y / size)
    if factor <= 1:
        return img
    return cv2.resize(img, (int(y // factor), int(x // factor)))

file_path = 'data/photo_2024-07-25_13-13-16.jpg'
img = cv2.imread(file_path)
img = resize(img, size=1024)

gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

gray = cv2.GaussianBlur(gray, (5, 5), 0)
show('0-Blur', gray)

edges = cv2.Canny(gray, 30, 200, apertureSize=3)
show('1-Canny', edges)
kernel = np.ones((3, 3), np.uint8)
edges = cv2.dilate(edges, kernel, iterations=1)
show('2-dilate', edges)
kernel = np.ones((3, 3), np.uint8)
edges = cv2.erode(edges, kernel, iterations=1)
show('3-erode', edges)

contours, hierarchy = cv2.findContours(edges, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

c = cv2.drawContours(img, contours, -1, (0,255,0), 3)
show('4-contours', c)

Когда на изображение наносят сразу все контуры, то разобрать что-либо затруднительно. Однако чтение документации творит чудеса. Функция findContours не только находит контуры объектов, но и структурирует их в иерархию, если передать флаг RETR_TREE. При этом массив hierarchy содержит кортеж [Next, Previous, First_Child, Parent] для каждого контура.


Распознавание основного контура.

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


Крайние случаи.

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



Шаги исключения лишних внутренних контуров. Слева — без обработки, середина — удаление контуров малой площади, справа — исключение не квадратов

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

1. Вместо контуров стоит работать с прямоугольником, в который вписан контур. Его можно получить с помощью функции boundingRect.
2. Контрастные фрагменты изображений и буквы условия определяются как контуры малой площади. Если фрагменты меньше, их нужно отсечь. Далее выбрал условие: площадь, то есть произведение длины и ширины описанного вокруг контура прямоугольника, должна быть больше 1000 пикселей.
3. Ячейка сканворда квадратная, поэтому исключаем остальные фигуры. Поскольку фотография может быть под углом, считаем квадратом все, у чего разность ширины и длины не превышает десяти пикселей.

Значения в 10 и 1000 квадратных пикселей — это эмпирические данные, которые сработали на тестах. При этом они задают ограничение: система, скорее всего, не сможет корректно распознать фотографию размером А1 — будут «ложные клетки». Но в А4-А5 покажет достойный результат. В коде это выглядит так:

children = dict()

# Делаем словарь из списка
for i, (next_, prev, first_child, parent) in enumerate(hierarchy[0]):
    if parent not in children:
        children[parent] = list()

    children[parent].append(i)

    print(f"{i} -> {next_}, {prev}, {first_child}, {parent}")

max_i = -1
max_value = 0

# Находим самого большого родителя
for key, value in children.items():
    if len(value) > max_value:
        max_i = key
        max_value = len(value)

print(f"Biggest part: {max_i} ({max_value})")

# Выбирает только детей этого родителя
out = []
for i, (next_, prev, first_child, parent) in enumerate(hierarchy[0]):
    if parent == max_i:
        out.append(contours[i])

# Дебаг-вывод родительского контура
c = cv2.drawContours(img, [contours[max_i]], -1, (0,255,0), 3)
show('5-contours', c)

# Фильтрация дочерних контуров
c_s = list()
for c in out:
    x,y,w,h = cv2.boundingRect(c)
    if abs(w - h) > 10:
        continue
    if w*h < 1000:
        continue
    c_s.append((x, y, w, h, c))

# Дебаг-вывод оставшихся дочерних контуров
for x, y, w, h, c in c_s:
    cv2.rectangle(img,(x,y),(x+w,y+h),(255,255,0),2)
show("6-all", img)

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

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

Веб-интерфейс

Для основной части бэкэнда я использовал FastAPI. В его основе нет особенностей, которые требуют подробных разъяснений. Для фронтенда использовал шаблон Jinja2.

Все файлы отправляются с клиента на бэкэнд через форму с типом multipart/form-data. При загрузке фотография разбирается на контуры, а их координаты и размеры сохраняются в базу данных вместе с оригинальным файлом.

Чтобы отобразить игровое поле в браузере, использовал Konva.js — он удовлетворял мои базовые запросы. Относительно просто обрабатывал «перетягивание» объектов и увеличение-уменьшение по колесику мыши.


Страница редактирования. Ожидание.

Сперва я добавил возможность удаления клеток, которые были распознаны неверно. Для этого поместил на сцену оригинальное изображение, а потом нанес на него полупрозрачные зеленые прямоугольники в соответствии с координатами распознавателя. При нажатии на прямоугольник квадрат окрашивается в красный — значит, это кандидат на удаление. Кнопка «Сохранить», в свою очередь, отправляет запрос об удалении выделенных прямоугольников.


Страница редактирования. Реальность.

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

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


Игровое поле в браузере.

Игровое поле — это модификация поля редактирования. Акцент (выделение клетки) можно сделать только один. При наличии выделенной клетки события с клавиатуры изменяют текст с пробела на выбранную букву.

С веб-интерфейсом разобрались. Осталось подключить мультиплеер.

Мультиплеер

Чтобы организовать мультиплеер, необходимо организовать обмен информацией между всеми подключенными клиентами. Проще всего — сделать из сервера репитер. Клиент будет отправлять сообщение серверу, а сервер — посылать его всем остальным с тем же идентификатором игры. Для организации связи клиент-сервер ничего выдумывать не надо, используем WebSocket. В сокет передаем словарь в виде JSON-строки.

/* URL подставляется через шаблоны FastAPI */
let socket = new WebSocket("wss://{{ host }}/live/{{ game_id }}")

/* При открытии соединения запрашиваем начальное состояние */
socket.onopen = function (event) {
    socket.send(JSON.stringify({init: true}))
}

/* Обрабатываем сообщения */
socket.onmessage = function (event) {
    let data = JSON.parse(event.data)

    if(data.hasOwnProperty("init")) {
        /* Если есть init, то заполняем */
    }

    if(data.hasOwnProperty("letter") && data.hasOwnProperty("pos")) {
        /* Кто-то заполнил букву letter в клетку с индексом pos */
    }

    if(data.hasOwnProperty("unset")) {
        /* Кто-то “отпустил” клетку с индексом unset */
    }

    if(data.hasOwnProperty("set")) {
        /* Кто-то “залочил” клетку с индексом set */
    }
}

socket.onclose = function (event) {
    alert("Соединение потеряно! Перезагрузите страницу")
}

На сервере создаем ответную часть через FastAPI WebSockets. Есть два пути: быстрый и правильный. Использую быстрый и объявляю глобальную переменную, которая хранит список всех подключенных веб-сокетов.

live_router = APIRouter(prefix="/live", tags=["live"])


games: Dict[str, List[WebSocket]] = dict()


@live_router.websocket("/{game_id}")
async def game_websocket(game_id: str, ws: WebSocket):
    # Сохраняем вебсокет в глобальной переменной
    if game_id not in games:
        games[game_id] = list()
    games[game_id].append(ws)
    await ws.accept()

    try:
        while True:
            # receive text from the user
            data = await ws.receive_json()

            if data.get("init"):
                # Считываем из БД и отправляем
                …
                await ws.send_json({"init": result})
            if data.get("letter") and data.get("pos") is not None:
                # Записываем, что кто-то заполнил клетку
                …

            # Пересылаем это сообщение другим клиентам
            for client in games[game_id]:
                if client != ws:
                    await client.send(data)

    except WebSocketDisconnect:
        games[game_id].remove(ws)

Глобальная переменная доступна только в рамках одного worker’а, поэтому он будет работать в dev-версии бэкэнда с параметром reload=True, либо при одном процессе FastAPI. Одного процесса достаточно для небольшого проекта, поэтому оставлю как есть.

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

Чтобы улучшить пользовательский опыт на фронтенде, я сделал определение вертикалей и горизонталей, а также автоматический переход к следующей клетке. Ну и для красоты добавил цветные «курсоры» и ники пользователей. По ссылке — видео с решением кроссворда.


Хотел как лучше, а получилось как всегда?

Заключение

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

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

Разгадываете ли вы сканворды в свободное время? Пишите в комментариях свои ответы и делитесь вариантами любимых журналов.