Привет, хабр! С 2015-го года мы публикуем в нашем блоге посты, в которых описываем различные аспекты распознавания документов, удостоверяющих личность, (и не только) на мобильных устройствах (и не только). В комментариях нас несколько раз просили рассказать в целом о том, как устроена наша система распознавания, но мы долго откладывали, т.к. описать это “в двух словах” достаточно сложно. 

В этой статье мы постарались кратко описать устройство нашей системы распознавания документов, удостоверяющих личность, и алгоритмов, которые применяются на различных этапах процесса. Если вы хотели узнать, как устроена система Smart IDReader, - добро пожаловать под кат!

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

Принципы

В первую очередь очертим требования, которые мы закладывали при проектировании системы. Четыре основных принципа, лежащих в основе Smart IDReader:

1. Точность (спасибо, кэп). Даже если документ будет распознаваться на фотографиях и видео кадрах, полученных при помощи малоформатной цифровой камеры, точность распознавания должна быть достаточно высокой, чтобы обеспечить автоматизацию ввода данных (а иначе, зачем распознавать).

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

3. Автономность. Безопасность данных - превыше всего. Самый безопасный способ хранения данных - не хранить данные, самый безопасный способ передачи данных - не передавать данные. По нашему мнению, мобильная система распознавания обязана быть построена так, чтобы при распознавании никакие данные за пределы оперативной памяти конечного устройства не уходили. Следовательно, вся обработка изображений и все распознавание должно происходить непосредственно на устройстве, что накладывает дополнительные ограничения (см. п. 2) на используемые алгоритмы. 

4. Масштабируемость. Наша первая система распознавания для мобильников (вот эта) поддерживала только внутренний паспорт РФ. При этом в мире существуют тысячи документов, удостоверяющих личность, и система должна быть устроена таким образом, чтобы добавить поддержку нового документа можно было быстро. Кроме того, добавление нового типа документа не должно требовать большого количества примеров, поскольку их неоткуда взять.

Трудности

При использовании мобильных устройств в качестве средств захвата изображений возникает ряд проблем, не присущих “традиционным” системам распознавания, рассчитанным на плоские сканы. Во-первых, у сканов, как правило, однотонный равномерный фон, тогда как фотография или кадр видеопотока может быть сделан (и делается) на произвольном фоне. Это может значительно осложнить задачу поиска документа и определения его типа. Во-вторых, при работе с фотографиями и видео приходится иметь дело с неконтролируемым освещением: света может быть недостаточно, может быть слишком много, на поверхности документа могут появляться блики и т.п. В-третьих, изображения, полученные при помощи мобильного устройства, могут страдать от дефокусировки и смазывания.

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

Одним из способов повышения качества распознавания документов на мобильниках (учитывая перечисленные выше проблемы) является использование не одной фотографии в качестве входа системы, а последовательности кадров: если мы обладаем достаточно быстрыми алгоритмами обработки одного кадра, то, аккумулируя информацию с множества кадров, можно не только отфильтровать некоторые “плохие” входные изображения, но и существенно повысить точность финального результата.

Итак, держим в уме: всё должно быть сделано точно и быстро, только средствами мобильного устройства, при этом надо учитывать неконтролируемые условия съемки, но можно использовать несколько кадров.

Поиск документа

Система Smart IDReader в её современном состоянии поддерживает большое количество разнообразных документов, но при её проектировании главным образом рассматривались документы, обладающие жесткой структурой. Грубо говоря, документом (точнее, страницей документа) с жёсткой структурой является документ, в котором все статические элементы совпадают “на просвет” - если стереть с двух разных экземпляров документа все реквизиты, то полученные бланки будут совпадать. 

На первом этапе обработки изображения системой Smart IDReader мы детектируем страницы документа (мы их условно называем “шаблонами”). Шаблоны документов, которые мы ищем, нам заранее известны, все они представляются как изначально плоские прямоугольники (с известными физическими размерами), однако на изображении они могут быть проективно искажены. Кроме того, у одного документа могут быть несколько шаблонов: к примеру, передняя и оборотная стороны ID-карточки, или две страницы паспорта.

Для поиска шаблонов на изображении мы используем (иногда совместно) три основных подхода:        

1. Быстрый поиск проективно искаженного прямоугольного объекта с известными соотношениями сторон. Метод основан на предварительном поиске прямых линий быстрым преобразованием Хафа и аккуратной переборной схеме. Про этот метод мы уже писали на Хабре, также про него можно почитать в этом докладе. 

2. Подход, основанный на методе Виолы и Джонса, а точнее, на его обобщении в виде решающего дерева классификаторов. Для исправления “проективности” предварительно также производится анализ прямолинейных объектов на сцене, вычисление точек схода, и корректировка перспективы. Именно этим методом мы детектируем страницы российского паспорта (“чистые” бланки которых достаточно бедны на статические элементы, к которым можно было бы “привязаться” методом, описанным в пункте 3 ниже). Подробнее про этот метод можно почитать в этой статье.

3. Наиболее общий подход, основанный на связке: особые точки + дескрипторы + RANSAC. Вначале на входном изображении производится поиск особых точек (мы используем модификацию особых точек YAPE для изображений с большим разбросом локального контраста, про эту модификацию можно почитать в этом докладе) и для каждой точки вычисляется локальный дескриптор (в нашем случае - методом RFD, модифицированным с целью ускорения). Далее в индексе “известных” дескрипторов запуском серии поисков ближайших соседей выявляются шаблоны-кандидаты. После этого кандидаты верифицируются при помощи метода RANSAC с учетом геометрического расположения особых точек. Этот метод используется в Smart IDReader для поиска и типизации подавляющего числа типов идентификационных документов. Подробнее про него можно почитать в этом докладе.

Поиск полей

Теперь, когда мы знаем координаты шаблона на изображении и точный тип этого шаблона (а следовательно, его соотношение сторон, настоящие физические размеры и т.п.), казалось бы, мы просто можем вырезать каждое нужное нам поле просто по его координатам? Так можно было бы делать, если бы на документах с жесткой структурой поля всегда находились в одних и тех же местах. Однако, к сожалению, из того, что на бланке документа напечатаны статические тексты (указывающие где должно быть какое-то поле) или даже пропечатаны линеечки, на которых эти поля должны находиться, еще не следует, что поля будут печататься одинаково. Как в России, так и за рубежом даже для жёстких документов качество печати документов оставляет желать лучшего, и текстовые поля могут быть под углом, поверх статических текстов, поверх направляющих линеек и даже не совсем в тех местах, где нужно. Это означает, что нужно прибегать к специальным алгоритмам, предназначенным для поиска полей на найденном документе.

На этапе поиска полей мы прибегаем к (слабо определенному) понятию “зоны документа” - региону шаблона, который содержит набор нужных нам полей, обладающих примерно одинаковой структурой. К примеру, если поля повернуты на какой-то угол из-за дефекта печати, но в рамках зоны все поля повернуты на один и тот же угол. Для того, чтобы найти поля, вначале изображение зоны проективно вырезается из исходного изображения документа, с минимальным разрешением, достаточным для работы дальнейших алгоритмов. 

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

После этого на изображение зоны динамическим программированием “натягивается” шаблон геометрического расположения текстовых полей (мы помним, что мы знаем на какой документ мы смотрим, а значит, и то, какие поля там должны быть и где они должны примерно находиться).  

Подробнее про метод локализации текстовых полей в зоне с приблизительно определенным шаблоном расположения полей можно прочитать в этом докладе.

Обработка и распознавание полей

Теперь, когда мы наконец нашли текстовые поля, пришло время их распознавать, верно? Не совсем. Сначала задачу для распознавателя текста можно несколько облегчить, предварительно обработав изображения текстовых полей, исходя из априорных знаний о документе и о структуре распознаваемых полей. К примеру, зная, что на этом типе документа вот это конкретное поле содержится в ячеистой разграфке, или, если оно подчеркнуто, - прямые линии можно предварительно снять, используя морфологические операции. Или если мы знаем, что текстовые поля напечатаны курсивом, или если они рукописные, то предварительно можно исправить их наклон, используя поиск угла наклона букв при помощи быстрого преобразования Хафа (про это можно почитать здесь). При предварительной обработке полей зачастую рассматривается не каждое поле в отдельности, а сразу группа полей, поскольку несколько полей в рамках одной зоны, как правило, “наклонены” на один и тот же угол, либо написаны от руки одним и тем же почерком.

К моменту распознавания текстого поля мы уже знаем, что это за поле, какого документа, какой у этого поля алфавит, а также можем знать некоторые характеристики его шрифта. Для распознавания текстовых строк мы используем “двухпроходную” схему, подробно описанную в этой статье. 

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

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

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

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

Использование нескольких кадров

При использовании последовательности кадров Smart IDReader предполагает, что в рамках одной сессии распознавания на разных кадрах видеопотока виден один и тот же документ (это не означает, однако, что один и тот же шаблон - к примеру, при съемке ID-карты в рамках одной сессии документ можно перевернуть, показав оборотную сторону). Аккумулирование информации с нескольких кадров может быть полезно почти на любом этапе процесса анализа документа - начиная с поиска документа (как для дополнительной фильтрации набора возможных кандидатов, так и для уточнения геометрического позиционирования), и заканчивая распознаванием конкретного поля.

В системе Smart IDReader используется подход комбинирования результатов распознавания текстовых полей с нескольких кадров, что позволяет значительно повысить точность распознавания в видеопотоке и использовать даже информацию о частичном распознавании поля (если, к примеру, на каком-то кадре поле было прикрыто бликом). О методах комбинирования результатов распознавания текстовых строк можно прочитать, например, в этой статье.

Другим важным аспектом анализа последовательности кадров является решение об остановке. Вообще говоря, естественного критерия, когда можно считать распознавание в видеопотоке законченным, нет, его еще нужно придумать. Про задачу определения момента остановки процесса распознавания текстового поля на последовательности кадров мы уже писали на хабре. Важно понимать, что остановка служит не только очевидной цели в какой-то момент таки закончить захват кадров и отдать пользователю окончательный результат. Она еще является важным механизмом уменьшения времени, необходимого для распознавания документа. Ведь если какое-то поле уже “остановилось”, на следующем кадре не нужно тратить время на его распознавание, а если “остановились” все поля одной и той же зоны, - то и всю зону можно не обрабатывать (не тратить время на поиск полей).

Последним по порядку, но не по значению, аспектом работы с видеопотоком является анализ голограмм и других OVD (Optical Variable Devices) - элементов защиты документов, которые меняют свой внешний вид при изменении освещения или угла обзора. Для того, чтобы их детектировать и верифицировать их наличие, последовательность кадров просто необходима по определению. Рассматривая только одно изображение, верифицировать наличие такого элемента защиты нельзя.

Детали, детали…

В этой статье мы постарались описать основные блоки нашей системы и ключевые принципы, на которые мы ориентировались при разработке. Разумеется, в таком формате невозможно охватить полный набор компонентов и нюансов системы распознавания документов. Поэтому в данную статью не вошли описания таких компонентов, как детектор рукописи, детектирование ключевых объектов (гербы, фотографии, подписи, печати), быстрое детектирование машиночитаемой зоны (MRZ) и её использование для уточнения позиционирования и типизации документов, форматирование полей до межкадрового комбинирования, определение степени уверенности распознавания и многое-многое другое. Даже грубое описание системы потребовало с десяток ссылок на научные тексты, и решение задачи, которая кому-то может показаться простой, достигается с помощью серьезных научных достижений большого коллектива. По теме распознавания документов мы публикуем порядка 40 научных текстов в год и регулярно подаем заявки на патенты.

Мы надеемся, что по предложенному описанию станут понятны причины, по которым мы выбирали подходы к распознаванию. Для того, чтобы достичь максимальной точности и скорости распознавания, мы применяем не только методы машинного обучения, но и методы классического компьютерного зрения, запускаем распознавание только тогда, когда уже обладаем максимальной информацией о распознаваемом объекте, и повсюду стараемся не распознавать “лишнего”. Мы не стоим на месте и постоянно совершенствуем наши алгоритмы и подходы, как увеличивая точность и скорость обработки документов, так и добавляя новые фичи для своих клиентов. 

Спасибо вам за внимание! Если вам интересно подробнее узнать о каких-то специфических компонентах нашей системы распознавания, пишите нам в комментариях!