Поиск линии корешка на фотографиях книжных разворотов

  • Tutorial
При съемке книжного разворота с помощью камеры мобильного устройства неизбежно возникают некоторые из нижеперечисленных дефектов (а возможно, что и все сразу):

• цифровой шум,
• тени и блики,
• расфокусировка и смаз,
• перекос,
• перспективные искажения,
• кривые строки,
• лишние объекты в кадре.

Обработка таких фотографий для последующего OCR – довольно трудоемкая задача даже для человека, хорошо владеющего навыками работы в Photoshop. Как быть, если мы хотим это сделать автоматически, с помощью программы? Сразу оговоримся, что подробное описание всех этапов алгоритма сделало бы публикацию чересчур объемной, поэтому мы сейчас расскажем только о том, как решать одну из подзадач – найти линию корешка на таких фотографиях. О том, как устранять тени и блики на фотографиях мы уже рассказывали. Про устранение цифрового шума написано много статей. А про автоматическое исправление перспективы и кривых строк мы расскажем в следующий раз.

На первый взгляд, задача не представляет никакой сложности: выделяем все контуры на изображении с помощью одного из операторов градиента (например, Sobel) и ищем наиболее сильный и протяженный из них с помощью преобразования Хафа:





Нам нужно найти самый яркий пиксель на картинке справа и получить уравнение линии из его координат. И это все? Кто-то, возможно, решит, что можно еще сначала уменьшить картинку, чтобы не заниматься всем этим на изображении размером 5-10 мегапикселей. Но что-то подсказывает, что так просто это будет работать далеко не всегда. Рассмотрим возможные ситуации:

У корешка нет тени:



На странице есть фотография с темной рамкой:



Или просто большая темная фотография:



Таблица:



Многоколоночный текст с сепараторами:



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

Предобработка для подчеркивания слабой тени у корешка


Конвертируем изображение в полутоновое (серое) и применяем фильтр UnsharpMask со следующими параметрами: radius = 41, strength = 300.



Быстрое определение ориентации строк текста


Чтобы определить, в каком направлении нам следует разрезать изображение, мы ищем направление строчек текста. Это можно сделать на бинаризованном изображении по гистограммам длин белых RLE-штрихов. Известно, что расстояние между строк как правило превосходит интервал между букв в многострочном тексте (иначе его было бы трудно читать). Гистограмму длин штрихов следует собирать по области изображения, содержащей текст. Можно использовать простейший классификатор текстовых блоков или просто отступить от краев изображения 10-15%, чтобы поля и фон не «затеняли» собираемую статистику. Обозначим сумму площадей горизонтальных белых штрихов, имеющих длину, не превосходящую некоторый порог L, как Sh, а сумму площадей вертикальных штрихов как Sv. Тогда, меняя порог L, можно следить за соотношением max(Sh, Sv) / min(Sh, Sv), и как только оно станет больше 2, мы можем с уверенностью сказать, что обнаружили межбуквенный интервал. А заодно и определили направление строк: если max(Sh, Sv) = Sh – оно горизонтальное, иначе – вертикальное. Мы взяли соотношение равным 2, чтобы не делать слишком много пропусков в определении ориентации и в то же время, не ошибаться слишком часто. Меняя эту величину можно получать разные точки на графике precision/recall. Можно использовать дополнительные признаки из тех же гистограмм. В тех случаях, когда нам не удается определить ориентацию однозначно простым способом, мы запускаем поиск сильной гипотезы корешка (тени) в обоих направлениях (горизонтальном и вертикальном) и оцениваем направление строк текста как перпендикулярное к направлению корешка, которое имеет более сильный отклик.



Сильная гипотеза (тень)


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

a) уменьшим изображение до заданного размера, например, до 800 пикселей по длинной стороне;
b) избавляемся от больших теней с помощью морфологической операции TopHat: вычитаем из исходного изображения его размыкание, т.е. наращивание от эрозии (r=5), под сигналом = 1 понимаем черное, а белый фон = 0;
c) убираем строчки (короткие вертикальные черные штрихи) с помощью эрозии по вертикали (r=3);
d) получив изображение строк как разницу между двумя предыдущими результатами, используем его как штраф, прибавив к текущему.

a)

b)

c)

d)

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



Можно учесть при этом статистическое распределение по углу от вертикали и смещению по горизонтали линии корешка. Как правило, в 99.9% случаев угол не превосходит по модулю 20-25 градусов, а середина линии корешка имеет координату от w/3 до 2w/3 (w – ширина изображения). При этом крайние значения углов и координат имеют гораздо меньшую вероятность, чем средние. Можно учесть это распределение в значениях точек в пространстве Хафа, накладывая штраф за отклонение от наиболее вероятного положения по углу и координате (0, w/2).

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

Слабая гипотеза (просвет)


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

Вычисляем модуль градиента (b) на уменьшенном полутоновом изображении (a) (оператор Sobel):

a)

b)

Здесь специально выбран другой пример, т.к. наличие сильной тени будет мешать этому алгоритму.

На бинаризованном изображении c) склеим текст в блоки с помощью морфологической операции дилатации (d, r=6 для изображения размером 800 пикселей). Применим полученную маску текстовых областей к изображению модуля градиента (e, сигнал был усилен в 4 раза).

c)

d)

e)

А теперь сгладим маску текстовых областей (d) гауссовым размытием (f) (r=8) и добавим к ней полученный усиленный градиент нетекстовых областей (g).

f)

g)

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

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



Координаты максимума преобразуем в уравнение линии корешка. Готово!

Приведенный несложный алгоритм на имеющейся в нашем распоряжении базе в >1800 фотографий книжных разворотов дает менее 1,5% ошибок.

Разумеется, есть много возможностей для его улучшения: можно выделять дополнительные признаки на изображении, вычислять не две гипотезы последовательно, а несколько и сразу, оценивать их взаимное расположение, выделять объекты на изображении (строки, сепараторы) и заниматься их анализом… В какой-то момент возникнет потребность в очередной раз расширить обучающую (и тестовую!) выборку, чтобы избежать возможного переобучения. Все это – бесконечная борьба за качество алгоритма.

Решая задачу поиска линии корешка, мы забыли сказать, а зачем вообще нам было это нужно? Зачем нужно на фотографии искать эту линию? Очень просто: линия корешка позволяет устранить перекос, т.е. повернуть изображение так, чтобы эта линия стала вертикальной, она разделяет изображение на две страницы для последующего применения алгоритма разгибания строк, помогает определить перспективные искажения (правда, для этого нужно будет найти еще точки схода перспективы). В общем, не решив эту задачу, подготовить подобные фотографии для последующего OCR едва ли возможно. Эти алгоритмы уже нашли свое применение в технологии BookScan, которая является частью нашего мобильного приложения ABBYY FineScanner.
ABBYY
Решения для интеллектуальной обработки информации

Comments 20

    +8
    А какой смысл постить мегабайтные .BMP-хи? Думаете какие-то детали потеряются при конвертации их в чёрно-белый JPEG?
      0
      Виноват, как обычно, редактор. Сейчас исправим.
        –5
        Картинки вполне сжатые (6.2Mb для сжатых BMP vs 4.7Mb при конвертации в PNG vs 5Mb 100% quality JPEG) и весят не так много.
        Зачем тут использовать формат сжатия с ошибками?
        +9
        А как были выбраны конкретные значения radius = 41, strength = 300? Почему не, скажем, 42 и 333?
          0
          Да все ж элементарно по-моему. Любые фильтры всегда призваны выделять контраст одного перед другим. Разработчик визуально подбирает коэффициенты фильтра усиливающие контраст границ. Причём судя по опыту работы с этим фильтром и ваши коэффициенты прекрасно подойдут.

          Там разброс практически не зависит от технических характеристик входного кадра. Подгонять радиус размытия можно легко через разрешение кадра. Все цветные фотографии с мобил имеют максимально возможный для них динамический диапазон и контраст максимально близкий к тому что можно назвать фотографическим качеством. Соответственно шапрятся они примерно одинаково.
            +2
            Помимо визуального контроля за результатом работы фильтра, его параметры подбирались так, чтобы минимизировать количество ошибочных разрезов на обучающей выборке.
              0
              Спасибо за пояснения. Но один нюанс: для Вас это может быть элементарно, но для тех, кто не занимался разработкой подобного кода — напоминает картинку «как нарисовать сову» :-)
                0
                я не занимался конкретно кодом) просто знаю этот фильтр по фотошопу, так как с ним я давно работаю и уже в голове знаю как будет выглядеть изображение при таком то или таком то фильтре, ну и да чутка про OCR изучаю.
            0
            А чем вариант с просветом так уж плох? Вроде бы он есть как раз чаще чем тень. Не претендую на глобальность, но последний раз, решая эту задачу (для частного случая нужно было быстро), я просто накидал выделение двух блоков текста и где-то посередине поискал просвет между ними. А вот тень- (глянул на свои сканы)- где там тень…
              0
              Предлагаемый метод предназначается для фотографий с мобильных устройств, а не сканов. В этом случае тень — более частое явление. По нашей базе получается, что в 85-90% случаев тень есть.
                0
                ух ты. 90%. не спорю, ваша база, наверно, порепрезентативней будет, но это как же надо снимать-то… (мой случай был тоже для телефонофото)
              0
              Расскажите, пожалуйста, как восстанавливать (реконструировать) параграфы из отдельных слов.
                +3
                А если тупо нарисовать линию по середие с надписью, «кто не навел линию на середину книги тот фигу получит а не OCR» и все, и не надо напрягать процессоры мобильные
                  0
                  Задача мобильного приложения сделать все необходимые подсказки пользователю и облегчить работу используемым алгоритмам. Линия с надписью есть, но это уже не алгоритм, а часть продукта.
                    0
                    все правильно, ( линия тоже алгоритм!) ) но если приложение будет отрабатывать на 2 секунды быстрее благодаря этой линии… (две ли?) продукт будет восприниматься как более шустрый. Ну и черт с этой линией, для блондинок по дефолту пусть автомат, а для дартаньянов — в опциях галочка.
                      0
                      Весь этот алгоритм обрабатывает 1 фотографию в среднем за 70 миллисекунд.
                  0
                  А как быть, если направление строк меняется? В последнем примере первая картинка: неаккуратное перелистывание, в итоге
                  — наклон строк на левой странице не постоянен из-за «загиба вверх» (как будто немног оприсобрали в гармошку)
                  — отличается от направления строк правой странице
                  Ну и для старых книг, когда разваливается на отдельные тетради, там вообще чудеса в решете могут быть
                    0
                    Борьбой с наклоном строк, в том числе переменным, занимается алгоритм разгибания строк. О нем мы расскажем в одной из следующих публикаций. Определение направления — это всего лишь попытка ответить на вопрос, какое оно: преимущественно горизонтальное или преимущественно вертикальное?
                    +1
                    Алгоритм немного расстроил. А нельзя бинаризировать, построить дерево вложенных контуров и по их максимальному числу и максимальному периметру определить корешок? Зачем танцы с фильтрами и размытиями?
                      0
                      фильтры можно очень быстро применять: это один проход по массиву. Фактически, это O(n) (или даже O(log(n))). Деревья обычно имеют сложность O(n^2)… O (nlog(n)).

                      Меня вот другое волнует: в 50% реально можно взять линию примерно посередине изображения, выровненного по горизонтали — это и будет разворот. Вся математика применима даже не в 80% случаев. А вот ошибка 1,5% при такой математике кажется странной (большой). Либо сама задача сформулирована слишком строго, а на практике все несколько более приземленно.

                    Only users with full accounts can post comments. Log in, please.