company_banner

Конкурс World & AI Data Challenge: начинаем решать задачу распознавания шрифта Брайля

    Технологии искусственного интеллекта и анализа данных всё стремительнее входят в нашу жизнь, они могут дать еще один шанс решению действительно важных для людей социальных задач, которые ранее не были реализованы. С этой целью центр цифрового развития АСИ организовал конкурс World AI & Data Challenge, цель которого — структурировать процесс поиска социальных задач и их решений. В феврале 2020 года команда центра цифрового развития АСИ позвала меня войти в состав экспертов этого конкурса. В этой заметке я немного расскажу о самом конкурсе, а также о том, как можно начать решать одну из интересных задач этого конкурса — распознавание шрифта Брайля. Поучаствовать в решении этой и других задач конкурса вы можете до 31 августа 2020 г.



    О конкурсе


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


    На первом этапе представители региональных органов власти и сообществ ставят наиболее актуальные для них задачи и, по возможности, находят соответствующие датасеты. После сбора всех задач подключаются эксперты конкурса, чтобы провести акселерацию задач, а также оценить их на соответствие требованиям конкурса и наличие данных для перехода лучших на следующий этап. Всего поступило 147 задач от 43 регионов России, а также из Сингапура, Казахстана, Узбекистана и Монголии. По итогам голосования осталось 30 задач из 30 регионов, в том числе 8 из них — задачи международного уровня.


    Сейчас идет второй этап конкурса, где разработчики со всего мира находят решения отобранных задач. На сегодняшний день к проекту подключилось уже более 2 тысяч ребят. Каждый участник берет наиболее близкую ему тему: кто-то хочет спрогнозировать потребность медицинских организаций в лекарствах, кто-то разрабатывает сервис по выявлению факта развития сердечно-сосудистых заболеваний, а некоторые берутся решать более глобальную задачу по снижению бедности в мире. Полный список задач для решений можете посмотреть здесь. Главное — успеть загрузить свои проекты на платформу http://git.asi.ru до 31 августа 2020 г..


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


    Призовой фонд проекта будет пополняться, на данный момент он составляет 1,5 млн рублей. Помимо этого, победителям предусмотрены гранты на вычислительные мощности от 1 млн и курсы по Data Science от лучших мировых онлайн-школ.


    Распознавание шрифта Брайля


    Одна из наиболее интересных мне задач в этом конкурсе — это распознавание шрифта Брайля. В идеале в результате решения должен быть создан продукт, который преобразует документ на языке Брайля, снятый на камеру смартфона или отсканированный на сканере, в текст.


    Несмотря на кажущуюся простоту задачи, она осложняется рядом моментов:


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

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


    Смотрим на существующие решения


    Для начала, немного поизучаем, что уже сделано в направлении распознавание Брайля. Например, в 2017 году был вот такой пост, анонсировавший проект распознавателя на GitHub, но при внимательном изучении оказывается, что сам проект — это несколько скриптов на Python (из которых, тем не менее, можно будет взять какой-то код для вдохновения). При внимательном поиске находится ещё пара проектов, которые примерно в таком же состоянии, например вот такой. Явно есть над чем поработать!


    Также имеет смысл поискать научные статьи на тему, например к упомянутому выше проекту есть вот такая статья. Ещё пара интересных статей: Smart Braille System Recognizer (2013), или совсем современная статья этого года Optical Braille Recognition Based on Semantic Segmentation Network.


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


    Изучаем датасет и ищем дополнительные данные


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


    Braille Cyryllic Letters


    Там же есть ещё датасет для двухсторонней печати, но на китайском языке.


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


    • Разумный датасет для распознавание отдельных символов [находится на Kaggle][KaggleData], он содержит фотографии отдельный символов Брайля, к которым применены различные трансформации, вроде поворота или изменения яркости. На таком датасете в принципе можно обучить распознаватель отдельных символов.
    • В упомянутом выше проекте на GitHub находится неплохой датасет символов, полученных фотографированием реальных книг, с последующим применением преобразований для data augmentation.
    • Поскольку алфавит азбуки Брайля известен, теоретически возможно попытаться сгенерировать искусственный датасет на основе произвольных текстов. При этом важно научиться делать это так, чтобы изображения выглядели достаточно реалистично, т.е. предусмотреть различные варианты освещения, поворота, диаметров точек и т.д.

    Braille Cyrillic Letters


    Общая архитектура решения


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


    1. Предварительная обработка фотографии с целью нормализации яркости/контраста
    2. Выделение границ текста, вырезание области с символами и (в идеале) исправление геометрических перспективных искажений
    3. Разбиение текста на отдельные символы
    4. Распознавание отдельных символов, с помощью нейросети или алгоритмически
    5. Коррекция полученного текста с целью исправления единичных ошибок. Для этого, в простейшем случае, может использоваться обычный spell checker, например, имеющийся к наборе когнитивных сервисов Microsoft.

    Давайте кратко рассмотрим эти пункты. Код, который я буду здесь демонстрировать, есть на GitHub в репозитории https://github.com/shwars/braillehack. Если вы будете использовать его на хакатоне — делайте fork! Запустить и посмотреть работу кода вы можете с помощью Visual Studio Codespaces


    Предобработка изображений


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


    im = cv2.imread('../data/Photo_Turlom_C1_2.jpeg')
    im = cv2.cvtColor(im,cv2.COLOR_BGR2GRAY)


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


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


    im = cv2.blur(im,(3,3))
    im = cv2.adaptiveThreshold(im, 255, cv2.ADAPTIVE_THRESH_MEAN_C,
                               cv2.THRESH_BINARY_INV, 5, 4)
    im = cv2.medianBlur(im, 3)
    _,im = cv2.threshold(im, 0, 255, cv2.THRESH_OTSU)
    im = cv2.GaussianBlur(im, (3,3), 0)
    _,im = cv2.threshold(im, 0, 255, cv2.THRESH_OTSU)
    plt.imshow(im)

    В результате из нашего исходного изображения получаем следующее:



    Получаем координаты точек


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


    Для нахождения крайних точек текста для начала выделим из картинки ключевые точки. Для этого используются так называемые feature detectors, и в составе OpenCV реализован детектор ORB, который может быть реализован парой строк кода:


    orb = cv2.ORB_create(5000)
    f,d = orb.detectAndCompute(im,None)

    5000 — это максимальное число ключевых точек, которые мы хотим искать. Если мы теперь построим эти точки на пустом изображении то увидим, что все наши точки из символов алфавита были обнаружены:


    def plot_dots(im,dots):
        img = np.zeros_like(im)
        for x in dots:
            cv2.circle(img,(int(x[0]),int(x[1])),1,(255,0,0))
        plt.imshow(img)
    
    pts = [x.pt for x in f]
    plot_dots(cim,pts)  


    Два подхода к решению задачи


    Получив множество точек Брайля на исходном изображении, мы можем идти двумя путями:


    • Рассматривать задачу распознавания шрифта Брайля как классическую задачу классификации для компьютерного зрения. В этом случае нам предстоит разбить текст на символы, и потом применить свёрточную нейросеть для решения задачи классификации. Полученные координаты точек мы будет использовать лишь для выделения фрагмента изображения, содержащего символы, для последующего разбиения текста на символы.
    • Использовать полученные координаты точек для решения задачи алгоритмически.

    Использование feature detector позволило нам свести задачу работы с изображением к множеству точек, с которыми мы можем работать алгоритмически.

    Здесь важно отметить один момент: одной точке на изображении возможно соответствует несколько обнаруженных ORВ-алгоритмом ключевых точек, о чем свидетельствует разная яркость точек на полученном изображении. Если мы хотим использовать алгоритмическое распознавание, нам скорее всего понадобится отсеять близко лежащие точки — вот тут обсуждают, как это можно сделать более менее эффективно.


    Мы не будем рассматривать алгоритмический способ решения, но он кажется достаточно привлекательной альтернативой! Надеюсь, какая-то из работающих над этой задачей команд пойдёт по этому пути!


    Вырезание области с символами


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


    min_x, min_y, max_x, max_y = \
       [int(f([z[i] for z in pts])) 
           for f in (min,max) for i in (0,1)]

    Далее приведём построенный нами прямоугольник к прямоугольнику с заданной длиной сторон (например, 500):


    off = 5
    src_pts = np.array([(min_x-off,min_y-off),(min_x-off,max_y+off),
                        (max_x+off,min_y-off),(max_x+off,max_y+off)])
    dim = 500
    dst_pts = np.array([(0,0),(0,dim),(dim,0),(dim,dim)])
    h,m = cv2.findHomography(src_pts,dst_pts)
    trim = cv2.warpPerspective(cim,h,(dim,dim))
    plt.imshow(trim)


    Мы получили практически идеальный прямоугольник с текстом.


    Разбиваем текст на символы


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


    char_h = 32
    char_w = 22
    def slice(img):
        dy,dx = img.shape
        y = 0
        while y+char_h<dy:
            x=0
            while x+char_w<dx:
                # Корректируем сдвиг по x
                while np.max(img[y:y+char_h,x])!=0:
                    x+=1
                while np.max(img[y:y+char_h,x+char_w])!=0:
                    x-=1
                # Пропускаем полностью пустые символы
                if np.max(img[y:y+char_h,x:x+char_w])>0:
                    yield img[y:y+char_h,x:x+char_w]
                x+=char_w
            y+=char_h
    
    sliced = list(slice(trim))

    Здесь мы используем одну хитрость. Из-за неточностей арифметики возможны смещения, которые могут накапливаться и привести к тому, что разрез "заедет" на границу символа. Поэтому в том случае, если граница символа содержит какие-то точки, мы слегка корректируем координату x. Аналогичный приём можно попытаться применить для вертикального разбиения на строки.


    В результате применения процедуры разрезания к нашему набору, получаем следующий результат:



    Свёрточная сеть для распознавания символов


    Я не буду подробно останавливаться на том, как происходит процесс обучения свёрточной сети для распознавания символов, поскольку этот процесс очень похож на распознавание рукописных цифр в датасете MNIST, про который написано множество обучающих текстов, например:



    Финальная коррекция текста


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


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


    Создание приложения


    К этому моменту мы получили модель (в виде некоторого кода или функции на языке Python), способную по входной фотографии вернуть распознанный текст. Однако в задании сказано, что в результате конкурса ожидается приложение, а не только работающая модель. Поэтому будет правильным потратить немного времени и оформить всё в виде конечного работоспособного продукта (MVP), благо облачные технологии Microsoft Azure позволяют сделать это весьма безболезненно.


    В качестве клиенской части приложения можно использовать:


    • Чат-бот в Telegram или Skype, который будет получать на вход фотографию. Реализация чат-ботов максимально просто делается с помощью Microsoft Bot Framework.
    • Мобильное приложение, по возможности кросс-платформенное, для создания которого можно использовать Xamarin или React Native
    • Веб-сайт

    Основную процедуру распознавания в виде кода на Python удобнее всего выполнять на сервере, в виде облачного REST-сервиса. По сути речь идёт про создание веб-API, которым будет пользоваться ваше клиентское приложение. Такое API лучше всего оформить в виде Azure Function с HTTP-триггером.


    Azure Function — это по сути фрагмент кода на каком-то языке программирования (в нашем случае на Python), который срабатывает при наступлении какого-то события (в нашем случае — при вызове REST-запроса). Подбробнее о том, как создать такую функцию с использованием Python — читайте в этом руководстве.


    Очень похожий по архитектуре клиент-серверный проект виртуального музейного экспоната я описал в своей статье. Фрагментами кода оттуда тоже можно вдохновляться!


    Выводы


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


    Работоспособный пример кода, описанного в данной статье, вы можете найти на http://github.com/shwars/braillehack. Он, в некотором смысле, "обрывается на полуслове" — в основном для того, чтобы вы могли оттолкнуться от него и доработать своё решение. Если у вас будут возникать вопросы, или если получится сделать что-то работающее на основе этого кода — пишите мне, координаты есть на сайте http://soshnikov.com.


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

    Microsoft
    Microsoft — мировой лидер в области ПО и ИТ-услуг

    Комментарии 5

      +2
      Уточните дату, пожалуйста,… до 31 августа может быть? (в шапке)
        +1
        Да, до 31 августа. Опечатались. Спасибо за комментарий.
        +1

        Стоит упомянуть, что призовых мест будет 10. Посчитаем:
        1500000/10 = 150 000 рублей составит средний приз. При этом некоторые участники уже работают полтора месяца над этими задачами совместно с экспертами. Задач всего 30, получается, что денег не хватило даже на каждую задачу. Получается, что экспертам придется искать не только лучший проект в рамках одной задачи, но и сравнивать несколько разноплановых проектов. Об уровне же самого мероприятия можно судить даже по организации процесса сабмита решений (через гит, и никаких вам лидербордов).
        Завтраками о том, что будет расширение призового фонда кормят уже сначала июля, а воз и ныне там.
        Чуть не забыл:


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

        По словам представителя АСИ внедрение это будет в общем случае неоплачиваемым.

          0

          Спасибо за взгляд со стороны! Поскольку решения очень разноплановые, а уровень формализации совсем не такой, как на kaggle, то кажется git является неплохим вариантом подачи решений. Я не представитель АСИ, но мне кажется это мероприятие не про "заработать денег на решении", а про "сделать мир лучше". АСИ умеет помогать налаживать контакты, а уж дальше каким будет внедрение — зависит от вас.

          +1
          Спасибо за статью. Это было интересно, правда в основном в первой половине.
          Однако у меня есть два серьёзных дополнения:

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

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

          Прежде всего, Брайль — это система, в которой знаки составляются из ячеек по 6 (в особых случаях по 8) точек).
          На листе будет фиксированное количество строк и фиксированное количество столбцов, а само шеститочие/восьмиточие даже при разных форматах листов плюс-минус одного размера, комфортного для тактильного восприятия.
          То есть логично сначала определить условную сетку ячеек на листе, а потом анализировать каждую получившуюся ячейку. Думаю, это повысит устойчивость к ошибкам из-за шума: если какой-то артефакт на изображении есть не в сетке, то его в принципе можно игнорировать.
          Ну и, как я уже написал, размер ячейки и точек сильно не различается, так что там должны быть плюс-минус одни и те же пропорции. В частности, в России есть вообще конкретный стандарт по параметрам брайлевской печати — ГОСТ Р 56832-2015 Шрифт Брайля. Требования и размеры

          На этом этапе я бы советовал результаты распознавания сохранить как есть, то есть в виде комбинаций точек. В частности, существует две распространённые системы кодирования: Braille ASCII и Braille Patterns.
          На Braille ASCII базируется такой формат документов, как BRF. То есть фактически мы сможем легко отправить отсканированный текст снова на печать. Это полезно, когда, например, мы сканируем старую книгу с целью подготовки её переиздания. Вышеупомянутый продукт Braille Reader VDL как раз решал эту задачу, которая была сильно востребована в библиотеках, желавших спасти старые брайлевские издания нот.
          Зато нотация Braille Patterns кодирует не 6, а 8 точек брайлевского знака, да и может быть легко сконвертирована в Braille ASCII. Правда восьмиточечный Брайль не используется в бумажной форме, так что вряд ли это актуально для задачи сканирования.

          Ну и вот что касается уже получения текста из комбинаций брайлевских точек, то сложность этой части, как мне показалось, вы как раз сильно недооцениваете.
          Дело в том, что одна брайлевская ячейка совсем не соответствует какому-то символу. У шеститочия всего 64 варианта (считая пробел), поэтому там просто не хватает вариативности.
          В итоге, вбрайлевском письме целый ряд символов кодируется одинаковым набором точек и их трактовка зависит либо от контекста, задаваемого окружением, либо вообще от чисто смыслового контекста. Причём, контекст окружающих символов может задаваться не только в соседних ячейках, но и существенно дальше. Например, строки
          • 1234567890
          • abcdefghij
          • абцдефгхиж
          • αβφδεφγθιη

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

          В индустрии вспомогательных технологий в основном решается задача трансляции обычного текста в брайлевский, потому что именно она наиболее востребована (брайлевские дисплеи, подготовка текстов к печати и т.д.). Но есть open source библиотека Liblouis*, которая является наиболее распространённым решением и теоретически обеспечивающем трансляцию в обе стороны.
          Однако трансляция брайлевского текста в обычный в любом случае сложнее и менее надёжна, чем обычного в брайлевский, да к тому же уровень поддержки языков в брайлевских трансляторах сильно разнится. В частности, поддержка русского оставляет желать много лучшего даже при трансляции обычного текста в брайлевский.
          Я сомневаюсь, что эту задачу даже на минимальном уровне смогут решить случайные люди, толком не знающие Брайля, да к тому же с наскока за несколько недель. Мне кажется, что вся сложность этой задачи вами сильно недооценивается.

          Думаю, полезнее сосредоточиться на решении чисто задачи сканирования брайлевского текста с последующим распознаванием в нотацию Braille ASCII или Braille Patterns. Это абсолютно реально для современных систем компьютерного зрения и относительно несложно, так что вполне можно собрать рабочий прототип за пару недель. Это будет полезно как раз для сохранения старых брайлевских изданий, для которых уже не осталось цифровых исходников или типографских матриц для нового тиража.
          Ну а задачу трансляции брайлевского текста в обычный стоит решать уже в рамках отдельной исследовательской работы, где на вход сразу принимать эти строго формализованные нотации описания брайлевских символов, или же сразу приходить в проект Liblouis* и делать вклад в него.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое