Обнаружение текста на изображениях Наталья Васильева HP Labs Russia 8 апреля 2012, Computer Science клуб

2 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice.

3 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Зачем? Необходимо для дальнейшего распознавания текста (OCR) Документы – page layout analysis Фотографии, чертежи, графики – text detection and localization Самостоятельные приложения Автоматическое построение коллажей Автоматическое изменение размера изображений

4 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Компоненты системы извлечения текста Fig. credit: J. Gllavata + Text Enhancement

5 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Приложения Оцифровка документов Индексирование и извлечение информации из графиков и чертежей Индексирование и поиск изображений, автоматическое построение аннотаций Переводчик в кармане пример: Word Lens ( Помощь слабовидящим Навигация роботов в помещениях, в городских условиях Fig. credit: N. Ezaki et al.

6 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice.

7 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice.

8 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice.

9 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение текста – газеты, журналы, книги обнаружение текстовых областей определение угла поворота текста (skew detection) определение порядка чтения

10 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение текста – произвольные изображения Исходное изображение Возможные результаты работы алгоритмов обнаружения текста

11 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение текста – чертежи и графики Обнаружение текстовых областей Определение угла поворота текстовых строк Короткие фрагменты текста Разнообразие шрифтов, текст под разными углами Однородный фон Высокая контрастность фотографии печатные документы

12 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. План лекции Зачем нужны алгоритмы обнаружения текста? Что такое цифровое изображение? –Представление цифровых изображений –Границы, компоненты связности, бинаризация, преобразование Хафа Печатные документы (document images) Фотографии (natural scenes) Чертежи, графики, обложки

13 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Представление цифровых изображений Растровое изображение

14 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Представление цифровых изображений RGB – распространенная модель цвета Каждый пиксель задается тремя значениями: red, green, blue Цветное растровое изображение:

15 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение границ

16 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Градиент изображения Градиент направлен в сторону наибольшего изменения интенсивности Направление градиента: Величина градиента:

17 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Вычисление градиента изображения Roberts:Prewitt:Sobel: Дискретный случай:

18 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Выделение границ: примеры Sobe l Canny Исходное

19 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Компоненты связности

20 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Компоненты связности

21 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Пороговая бинаризация Светлый объект на темном фоне Два светлых объекта на темном фоне Глобальная – порог единый для всех точек изображения Локальная или Динамическая – когда порог зависит от координат точки (x,y) Адаптивная – когда порог зависит от значения яркости в точке I(x,y)

22 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Бинаризация

23 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Преобразование Хафа (Hough transform) x y m b m0m0 b0b0 image spaceHough space Для данного набора точек (x, y) найти все точки (m, b), такие что y = mx+b

24 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Преобразование Хафа (Hough transform) x y m b image spaceHough space Точке (x 0, y 0 ) соответсвует прямая в пространстве Хафа: b = –x 0 m + y 0 x0x0 y0y0 Для данного набора точек (x, y) найти все точки (m, b), такие что y = mx+b Обычно, используют полярные координаты:

25 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. План лекции Зачем нужны алгоритмы обнаружения текста? Что такое цифровое изображение? –Представление цифровых изображений –Границы, компоненты связности, бинаризация, преобразование Хафа Печатные документы (document images) Фотографии (natural scenes) Графики, диаграммы, обложки

26 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Основные задачи Печатные документы Анализ структуры страницы (layout analysis, geometric structure analysis, page segmentation, region classification) Fig. credit: Y.Y. Tang et al.

27 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Основные задачи Печатные документы Анализ структуры страницы (layout analysis, geometric structure analysis, page segmentation, region classification) Fig. credit: Y.Y. Tang et al. Методы «Сверху-вниз» (top-down) XY-cuts, whitespace segmentation «Снизу-вверх» (bottom-up) группировка ближайших соседей, диаграммы Вороного

28 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Projection profiles and XY-cuts Вертикальна я проекция Горизонтальна я проекция Fig. credit: Y.Y. Tang et al.

29 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Результат алгоритма Docstrum Методы «снизу-вверх» Fig. credit: A. Namboodiri et al.

30 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Использование диаграмм Вороного Методы «снизу-вверх» Fig. credit: A. Namboodiri et al.

31 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Основные задачи Печатные документы Определение поворота текста (page rotation, skew detection) Обнаружение текстовых строк (text line finding, baseline finding) Projection profiles (для исходного изображения или компонент связности) Использование преобразования Хафа Определение угла наклона тектовых строк

32 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. План лекции Зачем нужны алгоритмы обнаружения текста? Что такое цифровое изображение? –Представление цифровых изображений –Границы, компоненты связности, бинаризация, преобразование Хафа Печатные документы (document images) Фотографии (natural scenes) Графики, диаграммы, обложки

33 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Почему не работают традиционные методы? Фотографии Большое разнообразие шрифтов Разнообразие расположений и направлений текстовых строк Короткие текстовые строки Разнообразие условий съемки (освещение, фокусное расстояние) Сложный фон Нет определенной структуры страницы Наложение объектов (occlusions)

34 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Классификация подходов Фотографии Text detection and localization Texture-based Region-based CC-based Edge-based K. Jung et al.

35 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Методы, основанные на анализе текстуры Фотографии Построение пирамиды изображений Извлечение текстурных признаков (Gabor, Wevelets, DCT) Классификация регионов (SVM) Text NoText Объединение результатов

36 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Методы, основанные на анализе текстуры Фотографии Сложный фон Вычислительно сложные (обработка нескольких масштабов, операции свертки) Произвольная направленность текста (негоризонтальный текст) Произвольный размер шрифта + –

37 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Region-based methods (bottom-up) Фотографии Выделение компонент связности на основе локальных признаков (близкий цвет или принадлежность границе) Объединение выделенных компонент связности в группы по признакам близкого расположения и схожих локальных признаков (размер, цвет)

38 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Region-based methods Фотографии Произвольный размер шрифта Произвольная направленность текста Просты в реализации Сложный фон Шум и нерезкость изображения Используют большое количество эвристик + –

39 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Stroke Width Transform (SWT) B. Epshtein et al. Исходное изображение Результат SWT После фильтрации по признаку постоянства ширины штриха Найденный текст

40 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение текста при помощи SWT B. Epshtein et al.

41 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Вычисление SWT (a)Фрагмент штриха (b)p – пиксель на границе штриха, q – пиксель на противоположной стороне штриха (градиенты в p и q направлены друг на друга) (c)Всем пикселям вдоль луча pq присваивается значение ширины штриха B. Epshtein et al.

42 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Обнаружение текста с помощью SWT Границы для нерезких изображений, низкого разрешения – Погрешность SWT на стыках штрихов – Эвристики для фильтрации компонент – Двойной проход и интеграция результатов –

43 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Комбинированные методы Y.-F. Pan et al.

44 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Шаг 1 – анализ текстуры Комбинированные методы Y.-F. Pan et al.

45 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Шаг 2 – анализ компонент связности Комбинированные методы Y.-F. Pan et al.

46 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Шаг 3 – выделение текстовых строк и слов Комбинированные методы Y.-F. Pan et al. построение минимального остовного дерева решение оптимизационной задачи

47 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Robust Reading Competitions ICDAR (2003, 2005, 2009, 2011) Распознавание символов Распознавание слов Локализация текста Распознавание текста

48 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. План лекции Зачем нужны алгоритмы обнаружения текста? Что такое цифровое изображение? –Представление цифровых изображений –Границы, компоненты связности, бинаризация, преобразование Хафа Печатные документы (document images) Фотографии (natural scenes) Графики, диаграммы, обложки

49 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Графики и диаграммы Анализ компонент связности по цвету

50 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Экспериментальная оценка LRRLPRTRRTPR Preprocess79.0%88.7%44.7%44.6% NoPreprocess33.7%84.2%2.5%2.9% LocationRecognitionRate = N Loc /N G LocationPrecisionRate = N Loc /N F TextPrecisionRate = N Txt /N F TextRecognitionRate = N Txt /N G N Loc – the number of correctly localized text blocks N Txt – the number of correctly recognized text blocks N G – the total number of text blocks N F – the total number of detected text blocks Тестовое множество: 1000 диаграмм, сгенерированных SWF/XML tool

51 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Screenshots (+) Быстрая бинаризация Время обработки изображения1600x1008 Tesseract OCR: ~6.56 секунд Данный алгоритм: ~0.45 seconds (–) Требует фильтрации компонент Naïve Bayes –Выделение границ и пороговая бинаризация –Удаление длинных горизонтальных и вертикальных границ –Выделение компонент связности –Классификация компонент связности и адаптивная бинаризация

52 © Copyright 2012 Hewlett-Packard Development Company, L.P. The information contained herein is subject to change without notice. Заключение Зачем нужны алгоритмы обнаружения текста? –Распознавание текста: оцифровка, индексирование, извлечение информации, автоматический перевод, text to speech, навигация Печатные документы (document images) –Анализ структуры документа, определение поворота, выделение текстовых строк Фотографии (natural scenes) –Texture-based & region-based –Stroke Width Transform, Hybrid approach Графики, диаграммы, обложки