![](https://habrastorage.org/webt/gt/dx/oz/gtdxoz9_vhsmup35o6ri0eqrjbg.png)
Несмотря на развитие технологий, журналы с кроссвордами, сканвордами и судоку до сих пор актуальны. Бумажную версию удобно разгадывать или в одиночку, или с людьми, которые непосредственно рядом. Но что делать, если хочется разделить процесс с друзьями, которые находятся далеко? Обратиться к технологиям, конечно.
Как оцифровать сканворд по фотографии? Насколько сложно сделать систему общего доступа? Действительно ли интересно разгадывать бумажные сканворды на электронном устройстве? Ответы на эти и другие вопросы — под катом.
Приглашаем 10 октября на Selectel Tech Day
Расскажем о новинках на рынке и обновлениях в наших продуктах. Вас ждут доклады, нетворкинг, мастер-классы и вечерняя программа. Участие бесплатное, но нужно зарегистрироваться.
Используйте навигацию, если не хотите читать текст полностью:
→ Мотивация проекта
→ Распознавание игрового поля
→ Веб-интерфейс
→ Мультиплеер
→ Демонстрация
Мотивация проекта
![](https://habrastorage.org/webt/xd/ne/m_/xdnem_fiybhu2thyvcetwk_sidc.png)
«Дедовские» технологии.
Это началось спонтанно. Друзья переслали в чат мем про старость и бумажные кроссворды, а потом… начали его разгадывать. Сначала Настя решала все, что могла. Если не знала ответа, то запрашивала нашу помощь. Гораздо интереснее подкидывать загадки другим людям, а не искать ответ в бездушном поисковике. Вскоре мы начали решать сканворды полностью коллективным разумом.
К сожалению, «бумажный» формат накладывал некоторые ограничения.
- Владелец оригинала должен следить за нашими сообщениями и вписывать варианты ответов.
- Бумага не прощает ошибок. Можно, конечно, использовать карандаш, но все равно останется грязь.
- «Удаленщики» не получают обновлений в режиме реального времени. Владелец должен каждый раз делать новую фотографию игрового поля.
В общем, за социальное взаимодействие и мозговую разминку — определенно «пятерка», а вот удобство нужно доработать.
В своем Telegram-канале я проводил опрос по популярности сканвордов. 44% интересуются разгадыванием кроссвордов и только четверть из них предпочитают бумажные версии. Подписывайтесь, там можно увидеть заметки по темам статей, над которыми я работаю, и небольшие познавательные посты.
Чтобы участникам было удобно, я продумал последовательность действий для игры в идеальных условиях.
- Автор фотографирует страницу.
- Система распознает игровое поле и строит его электронную версию.
- Автор делится ссылкой на электронное игровое поле.
- Каждый игрок заполняет свои ответы и видит, что и как заполняют другие.
Основополагающий момент — распознавание игрового поля по фотографии. Без «контента» кооперативный кроссворд будет просто «технодемкой», а составители кроссвордов вряд ли поделятся машиночитаемыми исходниками.
![](https://habrastorage.org/webt/wl/aa/dj/wlaadjlloqq7yzpxdqmwqg4bcxq.png)
Распознавание игрового поля
До начала проекта мои знания о компьютерном зрении были равны практически нулю. Когда-то давно я слышал, что есть мощный проект OpenCV, но взаимодействовать с ним не приходилось.
![](https://habrastorage.org/webt/ig/-n/q8/ig-nq8p4akkbmn97vmwje0wc9dk.png)
Задача полегче: судоку. Источник.
Сперва я решил ознакомиться с существующими предложениями и узнать, кто уже решил задачу за меня. Оказалось, что проблема беспокоила нескольких людей, но никто не поделился итоговым решением. Чисто человеческим взглядом мне показалось, что будет хорошо научиться определять вертикальные и горизонтальные линии, из которых состоит любой кроссворд или сканворд. Я начал поиск и нашел несколько полезных материалов.
- Вопрос на StackOverflow по определению разделительных линий в судоку.
- Потенциальный решатель судоку по фотографии с использованием распознавания цифр.
- Распознаватель кроссвордов, который не полностью справляется со своей задачей. Вопрос не решен.
- Магистерская ВКР из университета Коломбо (Шри-Ланка): End-End Automated Crossword Puzzle solver using image processing, NLP and neural network.
К сожалению для меня, в магистерской работе автор уделяет внимание обработке естественного языка (NLP), а распознаванию поля кроссворда — менее страницы. К тому же технология распознает кроссворд не с фотографии, а со скриншота, который сразу содержит игровое поле.
![](https://habrastorage.org/webt/k5/5t/ds/k55tdsax-ol0cxf5os0cbpc6sok.png)
Определение линий.
Я зацепился за идею обнаружения линий и приступил к копированию кусочков кода со StackOverflow. Однако система прерывала линии, а в качественных фотографиях создавала их даже из части букв. Полученные результаты совершенно не вдохновляли: у меня не было понимания как отсеять лишнее. В отличие от судоку, линии в сканвордах не обязательно проходят от одного конца игрового поля до другого.
В общем, идея не сработала и пришлось перечитывать источники в поисках упущенных знаний. Так и оказалось. В магистерской диссертации и нерабочем распознавателе кроссвордов использовалась функция поиска контуров findContours. Гениально! Вместо непонятных линий можно искать ячейки «изнутри».
![](https://habrastorage.org/webt/ty/cz/fn/tyczfnxyy7nswqmmz8twtgjzmdq.png)
Преобразования до обнаружения контуров.
Для успешного распознавания нужно выполнить несколько шагов.
- Уменьшить входящую картинку (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] для каждого контура.
![](https://habrastorage.org/webt/jo/p2/ps/jop2psmpuz8a9nzioocyyo8j9mu.png)
Распознавание основного контура.
Спустя некоторое время наблюдений я обнаружил стабильную закономерность. Можно найти контур, внутри которого больше всего дочерних контуров. Это позволяет смело отбросить контуры за пределами игрового поля.
![](https://habrastorage.org/webt/zq/qy/wy/zqqywytojkhh7unjrw_6clxcbmo.png)
Крайние случаи.
Если в кадре несколько игровых полей, побеждает то, которое содержит больше внутренних контуров и полностью находится в кадре. Вот и нашлось первое ограничение: фотографировать нужно только одну страницу.
![](https://habrastorage.org/webt/gy/h7/oj/gyh7ojp-6igwu63oohrovxvvccq.png)
![](https://habrastorage.org/webt/y7/xp/m2/y7xpm22ukadwl4issjxuwh6r7pi.png)
Шаги исключения лишних внутренних контуров. Слева — без обработки, середина — удаление контуров малой площади, справа — исключение не квадратов
Следующий этап — оставить на игровом поле только те контуры, которые определяют ячейки. В ходе экспериментов я выработал алгоритм.
- Вместо контуров стоит работать с прямоугольником, в который вписан контур. Его можно получить с помощью функции boundingRect.
- Контрастные фрагменты изображений и буквы условия определяются как контуры малой площади. Если фрагменты меньше, их нужно отсечь. Далее выбрал условие: площадь, то есть произведение длины и ширины описанного вокруг контура прямоугольника, должна быть больше 1000 пикселей.
- Ячейка сканворда квадратная, поэтому исключаем остальные фигуры. Поскольку фотография может быть под углом, считаем квадратом все, у чего разность ширины и длины не превышает десяти пикселей.
Значения в 10 и 1000
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 — он удовлетворял мои базовые запросы. Относительно просто обрабатывал «перетягивание» объектов и увеличение-уменьшение по колесику мыши.
![](https://habrastorage.org/webt/wl/ll/ih/wlllih6memsreihofrdoc_zw85s.png)
Страница редактирования. Ожидание.
Сперва я добавил возможность удаления клеток, которые были распознаны неверно. Для этого поместил на сцену оригинальное изображение, а потом нанес на него полупрозрачные зеленые прямоугольники в соответствии с координатами распознавателя. При нажатии на прямоугольник квадрат окрашивается в красный — значит, это кандидат на удаление. Кнопка «Сохранить», в свою очередь, отправляет запрос об удалении выделенных прямоугольников.
![](https://habrastorage.org/webt/aa/cj/ep/aacjepm4k2x4xgssl9-q7kv84gu.png)
Страница редактирования. Реальность.
Внимательный читатель может заметить, что технология обнаруживает контуры на уменьшенной версии изображения, а для читаемости условий сохраняет в базу данных оригинальное изображение. Контуры, обнаруженные на маленьком изображении, никак не могут «подойти» к оригинальному изображению.
Проблема, в общем-то, незначительная. При уменьшении изображения сохраняем коэффициент уменьшения, поделив высоту изображения до уменьшения на высоту изображения после уменьшения. После обнаружения контуров умножаем каждую компоненту контура на этот коэффициент.
![](https://habrastorage.org/webt/qj/uz/eq/qjuzeq7mwshwmyihyofll0oirb8.png)
Игровое поле в браузере.
Игровое поле — это модификация поля редактирования. Акцент (выделение клетки) можно сделать только один. При наличии выделенной клетки события с клавиатуры изменяют текст с пробела на выбранную букву.
С веб-интерфейсом разобрались. Осталось подключить мультиплеер.
Мультиплеер
Чтобы организовать мультиплеер, необходимо организовать обмен информацией между всеми подключенными клиентами. Проще всего — сделать из сервера репитер. Клиент будет отправлять сообщение серверу, а сервер — посылать его всем остальным с тем же идентификатором игры. Для организации связи клиент-сервер ничего выдумывать не надо, используем 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. Одного процесса достаточно для небольшого проекта, поэтому оставлю как есть.
Демонстрация
Чтобы улучшить пользовательский опыт на фронтенде, я сделал определение вертикалей и горизонталей, а также автоматический переход к следующей клетке. Ну и для красоты добавил цветные «курсоры» и ники пользователей. По ссылке — видео с решением кроссворда.
![](https://habrastorage.org/webt/di/3q/rz/di3qrz35wcc__r90re1kbqfrnfk.png)
Хотел как лучше, а получилось как всегда?
Заключение
Сначала проект казался мне неприступным: нужно было использовать компьютерное зрение, в котором у меня совершенно не было опыта. Но если подробнее изучить технологию, то создать онлайн-кроссворд не составит труда.
Сейчас работа над проектом не закончена. Есть несколько типов кроссвордов, которые не подходят под алгоритм. В планах настроить его так, чтобы он распознавал разные форматы кроссвордов. А также добавить соревновательную часть для друзей.
Разгадываете ли вы сканворды в свободное время? Пишите в комментариях свои ответы и делитесь вариантами любимых журналов.
Комментарии (9)
gudvinr
22.08.2024 09:59А вы не выравниваете поля?
Раз границы определены, то можно скорректировать перспективу, чтобы границы поля были параллельны сторонам экрана.Firemoon Автор
22.08.2024 09:59Нет, поля не выравниваю. Была идея извлекать ячейки с условием, а весь остальной сканворд нарисовать на «конве», но тогда нужно извлекать ещё и стрелочки. В общем, решил максимально не усложнять в первой итерации.
s60
22.08.2024 09:59+2До начала проекта мои знания о компьютерном зрении были равны практически нулю. Когда-то давно я слышал, что есть мощный проект OpenCV, но взаимодействовать с ним не приходилось.
это ж как надо любить сканворды чтобы войти в IT через OpenCV ..... :)
а за материал однозначно лайк
задумывал о реализации подобной задачи, когда увидел Android игру, в которой все слова по 5 букв в клетчатом поле , например, 10х10 клеток, но могут изгибаться по всякому (-, I, Г, L, ¬), но так и не придумал как можно генерить такое поле из словаря (хз как подобрать варианты изгибов, чтобы все поле заполнить + каждый раз по-разному)
alcotel
22.08.2024 09:59Супер! Тоже игры на бумаге люблю.
Оффтопик, наверное:
Был тут недавно на экскурсии в крепости-тюрьме Орешек. Кто там только не сидел, но 200 лет назад там сидели декабристы перед отправкой в Сибирь. Некоторые там и насовсем остались. Так вот. Легенда гласит, что эти товарищи с помощью перестукивания умудрялись играть в шахматы. Похоже, это была самая ранняя сетевая игра, что я теперь знаю.
ALapinskas
Делал подобную игру "крестики-нолики", но там для мультиплеера нужно распределять пользователей по комнатам, ведь игра на 2-х, сделал небольшой проект на nodejs для этого https://github.com/ALapinskas/gameserver