Несмотря на развитие технологий, журналы с кроссвордами, сканвордами и судоку до сих пор актуальны. Бумажную версию удобно разгадывать или в одиночку, или с людьми, которые непосредственно рядом. Но что делать, если хочется разделить процесс с друзьями, которые находятся далеко? Обратиться к технологиям, конечно.
Как оцифровать сканворд по фотографии? Насколько сложно сделать систему общего доступа? Действительно ли интересно разгадывать бумажные сканворды на электронном устройстве? Ответы на эти и другие вопросы — под катом.
Хочешь выиграть мерч? Попробуй решить IT-кроссворд! Более 256 вопросов, 7 кроссвордов на разные темы из мира IT — ежедневно с 23 по 29 сентября. Достаточно зарегистрироваться по ссылке.
Используйте навигацию, если не хотите читать текст полностью:
→ Мотивация проекта
→ Распознавание игрового поля
→ Веб-интерфейс
→ Мультиплеер
→ Демонстрация
Мотивация проекта
«Дедовские» технологии.
Это началось спонтанно. Друзья переслали в чат мем про старость и бумажные кроссворды, а потом… начали его разгадывать. Сначала Настя решала все, что могла. Если не знала ответа, то запрашивала нашу помощь. Гораздо интереснее подкидывать загадки другим людям, а не искать ответ в бездушном поисковике. Вскоре мы начали решать сканворды полностью коллективным разумом.
К сожалению, «бумажный» формат накладывал некоторые ограничения.
- Владелец оригинала должен следить за нашими сообщениями и вписывать варианты ответов.
- Бумага не прощает ошибок. Можно, конечно, использовать карандаш, но все равно останется грязь.
- «Удаленщики» не получают обновлений в режиме реального времени. Владелец должен каждый раз делать новую фотографию игрового поля.
В общем, за социальное взаимодействие и мозговую разминку — определенно «пятерка», а вот удобство нужно доработать.
В своем Telegram-канале я проводил опрос по популярности сканвордов. 44% интересуются разгадыванием кроссвордов и только четверть из них предпочитают бумажные версии. Подписывайтесь, там можно увидеть заметки по темам статей, над которыми я работаю, и небольшие познавательные посты.
Чтобы участникам было удобно, я продумал последовательность действий для игры в идеальных условиях.
- Автор фотографирует страницу.
- Система распознает игровое поле и строит его электронную версию.
- Автор делится ссылкой на электронное игровое поле.
- Каждый игрок заполняет свои ответы и видит, что и как заполняют другие.
Основополагающий момент — распознавание игрового поля по фотографии. Без «контента» кооперативный кроссворд будет просто «технодемкой», а составители кроссвордов вряд ли поделятся машиночитаемыми исходниками.
Распознавание игрового поля
До начала проекта мои знания о компьютерном зрении были равны практически нулю. Когда-то давно я слышал, что есть мощный проект OpenCV, но взаимодействовать с ним не приходилось.
Задача полегче: судоку. Источник.
Сперва я решил ознакомиться с существующими предложениями и узнать, кто уже решил задачу за меня. Оказалось, что проблема беспокоила нескольких людей, но никто не поделился итоговым решением. Чисто человеческим взглядом мне показалось, что будет хорошо научиться определять вертикальные и горизонтальные линии, из которых состоит любой кроссворд или сканворд. Я начал поиск и нашел несколько полезных материалов.
- Вопрос на StackOverflow по определению разделительных линий в судоку.
- Потенциальный решатель судоку по фотографии с использованием распознавания цифр.
- Распознаватель кроссвордов, который не полностью справляется со своей задачей. Вопрос не решен.
- Магистерская ВКР из университета Коломбо (Шри-Ланка): End-End Automated Crossword Puzzle solver using image processing, NLP and neural network.
К сожалению для меня, в магистерской работе автор уделяет внимание обработке естественного языка (NLP), а распознаванию поля кроссворда — менее страницы. К тому же технология распознает кроссворд не с фотографии, а со скриншота, который сразу содержит игровое поле.
Определение линий.
Я зацепился за идею обнаружения линий и приступил к копированию кусочков кода со StackOverflow. Однако система прерывала линии, а в качественных фотографиях создавала их даже из части букв. Полученные результаты совершенно не вдохновляли: у меня не было понимания как отсеять лишнее. В отличие от судоку, линии в сканвордах не обязательно проходят от одного конца игрового поля до другого.
В общем, идея не сработала и пришлось перечитывать источники в поисках упущенных знаний. Так и оказалось. В магистерской диссертации и нерабочем распознавателе кроссвордов использовалась функция поиска контуров findContours. Гениально! Вместо непонятных линий можно искать ячейки «изнутри».
Преобразования до обнаружения контуров.
Для успешного распознавания нужно выполнить несколько шагов.
- Уменьшить входящую картинку (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] для каждого контура.
Распознавание основного контура.
Спустя некоторое время наблюдений я обнаружил стабильную закономерность. Можно найти контур, внутри которого больше всего дочерних контуров. Это позволяет смело отбросить контуры за пределами игрового поля.
Крайние случаи.
Если в кадре несколько игровых полей, побеждает то, которое содержит больше внутренних контуров и полностью находится в кадре. Вот и нашлось первое ограничение: фотографировать нужно только одну страницу.
Шаги исключения лишних внутренних контуров. Слева — без обработки, середина — удаление контуров малой площади, справа — исключение не квадратов
Следующий этап — оставить на игровом поле только те контуры, которые определяют ячейки. В ходе экспериментов я выработал алгоритм.
- Вместо контуров стоит работать с прямоугольником, в который вписан контур. Его можно получить с помощью функции 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 — он удовлетворял мои базовые запросы. Относительно просто обрабатывал «перетягивание» объектов и увеличение-уменьшение по колесику мыши.
Страница редактирования. Ожидание.
Сперва я добавил возможность удаления клеток, которые были распознаны неверно. Для этого поместил на сцену оригинальное изображение, а потом нанес на него полупрозрачные зеленые прямоугольники в соответствии с координатами распознавателя. При нажатии на прямоугольник квадрат окрашивается в красный — значит, это кандидат на удаление. Кнопка «Сохранить», в свою очередь, отправляет запрос об удалении выделенных прямоугольников.
Страница редактирования. Реальность.
Внимательный читатель может заметить, что технология обнаруживает контуры на уменьшенной версии изображения, а для читаемости условий сохраняет в базу данных оригинальное изображение. Контуры, обнаруженные на маленьком изображении, никак не могут «подойти» к оригинальному изображению.
Проблема, в общем-то, незначительная. При уменьшении изображения сохраняем коэффициент уменьшения, поделив высоту изображения до уменьшения на высоту изображения после уменьшения. После обнаружения контуров умножаем каждую компоненту контура на этот коэффициент.
Игровое поле в браузере.
Игровое поле — это модификация поля редактирования. Акцент (выделение клетки) можно сделать только один. При наличии выделенной клетки события с клавиатуры изменяют текст с пробела на выбранную букву.
С веб-интерфейсом разобрались. Осталось подключить мультиплеер.
Мультиплеер
Чтобы организовать мультиплеер, необходимо организовать обмен информацией между всеми подключенными клиентами. Проще всего — сделать из сервера репитер. Клиент будет отправлять сообщение серверу, а сервер — посылать его всем остальным с тем же идентификатором игры. Для организации связи клиент-сервер ничего выдумывать не надо, используем 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. Одного процесса достаточно для небольшого проекта, поэтому оставлю как есть.
Демонстрация
Чтобы улучшить пользовательский опыт на фронтенде, я сделал определение вертикалей и горизонталей, а также автоматический переход к следующей клетке. Ну и для красоты добавил цветные «курсоры» и ники пользователей. По ссылке — видео с решением кроссворда.
Хотел как лучше, а получилось как всегда?
Заключение
Сначала проект казался мне неприступным: нужно было использовать компьютерное зрение, в котором у меня совершенно не было опыта. Но если подробнее изучить технологию, то создать онлайн-кроссворд не составит труда.
Сейчас работа над проектом не закончена. Есть несколько типов кроссвордов, которые не подходят под алгоритм. В планах настроить его так, чтобы он распознавал разные форматы кроссвордов. А также добавить соревновательную часть для друзей.
Разгадываете ли вы сканворды в свободное время? Пишите в комментариях свои ответы и делитесь вариантами любимых журналов.
