Как оцифровать бумажный сканворд по фото и настроить к нему совместный доступ для друзей

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

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

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

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

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

→ Мультиплеер

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

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

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

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

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

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

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

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

<i>Задача полегче: судоку. <a href="https://api.vc.ru/v2.8/redirect?to=https%3A%2F%2Fstackoverflow.com%2Fquestions%2F48954246%2Ffind-sudoku-grid-using-opencv-and-python&postId=1492558" rel="nofollow noreferrer noopener" target="_blank">Источник</a>.</i>

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

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

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

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

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

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

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

Уменьшить входящую картинку (desampling) — в нашем случае до 1024 пикселей по большей грани. Перевести в оттенки серого и размыть по Гауссу с ядром 3х3.
Применить оператор Кэнни для определения краев (Canny Edge Detector).
Применить операцию dilate, чтобы расширить распознанные грани.
Применить операцию erode для сужения граней. В результате получаются более тонкие грани с меньшим количеством шума.
Вызвать функцию 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] для каждого контура.

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

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

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

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

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

Значения в 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 — он удовлетворял мои базовые запросы. Относительно просто обрабатывал «перетягивание» объектов и увеличение-уменьшение по колесику мыши.

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

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

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

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

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

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

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

Чтобы организовать мультиплеер, необходимо организовать обмен информацией между всеми подключенными клиентами. Проще всего — сделать из сервера репитер. Клиент будет отправлять сообщение серверу, а сервер — посылать его всем остальным с тем же идентификатором игры. Для организации связи клиент-сервер ничего выдумывать не надо, используем 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. Одного процесса достаточно для небольшого проекта, поэтому оставлю как есть.

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

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

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

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

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

→ Аппетиты ИИ меняют экологию. Разбираемся, как снизить ущерб уже сейчас

→ Чат-боты под ключ: 6 простых «рецептов» для создания мини-приложений в Telegram

→ Вспоминаем, что сделало ICQ таким классным: фичи, которые стали стандартом в мессенджерах

#selectel #python #online #кроссворд #хобби #технологии #программирование

5 комментариев

Aleksandr Shilov

20 сент

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

Ответить

Alexander Zorin

Это настолько круто, что надо выпить чаю, чтобы оправиться от шока!

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

Сценарий использования выглядит так: открыл кроссворд, навел на него смартфон ‑ на экране живая схема того, какие слова куда вписывать.

Это же готовый онлайн-сервис! Остается только сообразить, как подключить подписку. Но с этой задачей автор справится за полминуты, просто помешивая ложечкой кофе.

Анастасия

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

Милена Комягина

24 окт

Как оцифровать бумажный сканворд по фото и настроить к нему совместный доступ для друзей

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

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

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

Мультиплеер

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

Заключение

Читайте также: