А. Федоров

Бинаризация
черно-белых изображений:
состояние и перспективы развития

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

Извлечение информации из растровых документов и их редактирование является трудоемким процессом. Поэтому для редактирования и последующей обработки в системах автоматического проектирования (САПР) используются векторные форматы файлов. Полутоновое изображение содержит несколько слоев объектов. Каждый слой можно превратить в бинарный и затем его векторизовать с помощью программы - векторизатора. Получение нескольких бинарных слоев объектов из одного полутонового изображения называется расслоением.

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

Разрывы и потеря целостности объектов изображения возникают вследствие ряда причин, обусловленных структурой изображения: значительной зональной неравномерностью яркости объекта; касанием объектов изображения, когда часть контура объекта теряется при бинаризации, и объект сливается с соседним; наложением объектов изображения.

Большое значение имеет наложение объектов и их касание, как частный случай наложения. В результате бинаризации место наложения объектов может быть интерпретировано как продолжение одного или нескольких объектов. Алгоритмы бинаризации, проверяющие целостность геометрической формы объекта, в месте наложения формируют разрыв объектов. Причина в том, что точное теоретическое решение задачи интерпретации места наложения отсутствует из-за недостатка информации, и вследствие этого на практике используются тривиальные решения: интерпретировать место наложения как фон и как продолжение каждого из прилегающих объектов. Очевидно, что ни то, ни другое решение в общем случае не является удовлетворительным. Каждый тип изображений, подлежащих бинаризации или расслоению, содержит сотни наложений объектов, «разъединение» которых сегодня производится вручную. Это объясняет тот факт, что бинаризация чертежа среднего формата занимает порядка 70% времени подготовки документа.

При бинаризации изображения яркость каждого пикселя B(x,y) сравнивается с пороговым значением яркости B_T(x,y); если значение яркости пикселя выше значения яркости порога, то на бинарном изображении соответствующий пиксель будет «белым», или «черным» в противном случае. Необходимость устранения большого числа ошибок процесса бинаризации повлекла за собой появление большого числа методов бинаризации, которые делятся на две группы по принципу построения пороговой поверхности: методы глобальной и локальной бинаризации. Пороговой поверхностью является матрица размерностью M×N, соответствующей размерности исходного изображения, каждая ячейка матрицы задает порог яркости бинаризации для соответствующего пикселя на исходном изображении. В методах глобальной бинаризации пороговая поверхность является плоскостью с постоянным значением пороговой яркости, а в методах локальной бинаризации значение пороговой яркости меняется от точки к точке изображения, и рассчитывается на основе некоторых локальных признаков в окрестности пикселя.

Методики, получившие практическое применение, изложены в [Траер1, 1995; Траер2, 1995].

Метод Отса

Наиболее эффективным из методов глобальной бинаризации, как по качеству (ошибок до 30% и меньше), так и по скорости обработки является метод Отса (см. табл. 1) [Траер1, 1995; Траер2, 1995]. К его недостаткам относится размытие линий, «слипание» объектов, особенно в местах пересечений, потеря тонких линий (см. рис. 4г и 5г).

Метод использует гистограмму распределения значений яркости пикселей растрового изображения. Строится гистограмма по значениям p_i=n_i/N, где N – это общее кол-во пикселей на изображении, n_i – это кол-во пикселей с уровнем яркости i. Диапазон яркостей делится на два класса с помощью порогового значения уровня яркости k,k - целое значение от 0 до L. Каждому классу соответствуют относительные частоты: ω₀ω₁:

Средние уровни для каждого из двух классов изображения:

Далее вычисляется максимальное значение оценки качества разделения изображения на две части:

где (σ_кл)²₌ω₀ω₀₁(μ₁-μ₀)², – межклассовая дисперсия, а (σ_общ)² – это общая дисперсия для всего изображения целиком.

Метод Бернсена

Часто используется метод Бернсена. Для схематических и картографических изображений.

Для каждого пикселя (x;y) выбирается порог яркости B(x;y)=(B_мин-B_макс)/2, где B_минB_макс – соответственно, самый низкий и самый высокий уровень яркости пикселей из квадратной окрестности пикселя (x;y). Если уровень контраста (разность самого высокого уровня и самого низкого уровней) превышает некоторый порог, то пиксель считается либо белым, либо черным. Для всего изображения этот порог контраста является константой и должен подбираться интерактивно.

Имеет ряд недостатков: после обработки монотонных областей яркости формируются сильные паразитные помехи, в некоторых случаях приводит к появлению ложных черных пятен (см. рис. 3б, 4б, 6б). Недостатки могут быть компенсированы с помощью дополнительной обработки – постпроцессинга (см. рис. 3в, 4в, 6в). Метод является наиболее быстрым среди остальных (см. табл. 1), даже в совокупности с этапом постпроцессинга.

Метод Эйквеля

Одним из самых производительных методов является метод Эйквеля. Его часто применяют для обработки четких и контрастных изображений.

Согласно данному методу изображение обрабатывается с помощью двух концентрических окон: маленького – S, и большого L (см. рис. 1). Обычно форма окон принимается квадратной. Оба окна последовательно слева направо сверху вниз накладываются на изображение с шагом равным стороне маленького окна S. Для окна L рассчитывается порог B так, чтобы поделить пиксели на два кластера. Если математические ожидания уровня яркости в двух кластерах имеют разницу, превышающую некоторый заданный пользователем уровень /μ₁-μ₂/≥l, то все пиксели внутри окна S бинаризуются в соответствии с порогом T. В противном случае, яркость пикселей из окна S заменяется некоторым близким значением.

Рисунок 1. Перемещение окон в методе Эйквеля.

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

Метод Ниблэка

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

Идея данного метода состоит в варьировании порога яркости B бинаризации от точки к точке на основании локального значения стандартного отклонения. Порог яркости в точке (x, y) рассчитывается так:

B(x, y)=m(x, y)+k s(x, y),

где m(x, y)s(x, y) – среднее и стандартное отклонение выборки для некоторой окрестности точки. Размер окрестности должен быть минимальным, но таким, чтобы сохранить локальные детали изображения. В то же время размер должен быть достаточно большим, чтобы понизить влияние шума на результат (для изображений, приведенных здесь, радиус окрестности составляет 16 пикселей). Значение k определяет, какую часть границы объекта взять в качестве самого объекта. Значение k=-0.2 задает достаточно хорошее разделение объектов, если они представлены черным цветом, а значение k=+0.2, – если объекты представлены белым цветом.

В местах плавного перехода яркости метод дает ложные объекты с небольшим шумом (см. рис. 5б). Метод получил свое распространение на практике благодаря его интеграции с этапом постпроцессинга. При этом скорость обработки падает в 3 раза, и количество ошибок сокращается на 20% (см. табл. 1).

Метод Яновица и Брукштейна

Наиболее эффективным для обработки сканированных бумажных картографических изображений является метод Яновица и Брукштейна, Таким изображениям свойственна яркостная зональная неравномерность, при которой одни и те же объекты изображения в разных частях имеют значительные различия яркости (до 20-50%).

В качестве пороговой поверхности бинаризации используется поверхность потенциалов, строящаяся на основе локальной максимизации градиента яркости. Значение градиента яркости часто рассчитывается с помощью контурного оператора Собеля или Кэнни [Прэтт, 2000; Хемминг, 1990]. Изображение фильтруется с целью получения контурных линий толщины в 1 пиксель, а затем усредняющим фильтром 3×3 [Прэтт, 2000; Хемминг, 1990], и потенциальная поверхность, теперь, строится по итерационной интерполирующей схеме. Расчет поверхности идет в порядке, начиная от контурных пикселей. Для каждого не контурного пикселя рассчитывается интерполяционный остаток R(x, y) и новое значение пикселя P(x, y) на n+1-ом шаге должно рассчитываться в соответствии с формулами:

P_n+1(x, y)=P_n(x, y)+β R_n(x, y)/4,

R_n(x, y)=P_n(x-1,y)+P_n(x+1,y)+P_n(x,y-1)+P_n(x,y+1)-4 P_n(x,y)

Авторы метода предлагают использовать значение β в пределах 1≤β≤2 для быстрой сходимости.

Метод не дает паразитного шума на бинарном растре (см. рис. 4д, 5в, 6е). Ошибка разрыва линейных объектов низка (см. табл. 1). Но среди методов локальной бинаризации он наименее производительный (см. табл. 1).

Удаление ложных объектов

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

Рисунок 2. Возникновение ложных объектов при бинаризации.

Операции:

1. Сглаживается исходное изображение фильтром 3×3 для удаления шума [Прэтт, 2000; Хемминг, 1990].
2. Рассчитывается значение градиента для каждого пикселя сглаженного изображения с помощью контурного оператора Собеля [Прэтт, 2000; Хемминг, 1990].
3. Выбирается значение порога для градиента, который будет разделять объекты на значимые и ложные. Это значение указывается вручную.
4. Для всех контурных пикселей объекта рассчитывается средний градиент (по окрестности). Контурным пикселем объекта считается информационный пиксель, который присоединен к фоновому согласно условию 4-х связности [Прэтт, 2000]. Если среднее значение градиента окажется ниже порогового, то соответствующий информационный пиксель должен стать фоновым.

В таблице ниже приведены результаты бинаризации четырех изображений, отражающих особенности применения описанных алгоритмов. Для демонстрации взято 4 изображения, которые условно названы: «Негатив», «Кабели», «Карта 1», «Карта 2». Разнотипные изображения выбраны для демонстрации степени универсальности методик бинаризации. Для обработки выбраны наиболее эффективные их описанных методов. Критерий качества оценивался следующим образом: для каждого из пяти типов ошибок вводилась независимая оценка от 0 до 5 баллов. Далее оценки суммировались. Таким образом, для каждого изображения максимальная оценка качества составляет 25 баллов. Время обработки приведено для изображения «кабели». В приложении этой статьи можно найти исходные и обработанные изображения.

Табл. 1. Характеристика методов бинаризации

Заключение

Существующие алгоритмы бинаризации позволяют проводить обработку изображений со значительной зональной неравномерностью яркости, с монотонными областями яркости, с сильно зашумленными изображениями. Однако остаются нерешенным ряд проблем. К таким проблемам относится обнаружение зон наложения объектов изображения и необходимость автоматической интерпретации данных зон. Другими словами, процесс подготовки документа требует определения конфигурации объекта в местах его наложения с другими объектами. Не является удовлетворительным часто используемый вариант «обрывания» объекта в месте наложения, т. к. на реальных документах, соответствующих обрабатываемым изображениям, объекты образуют большое количество наложений, и «обрывание» приводит к появлению серьезной ошибки – потери целостности объектов. Неудовлетворительным является и вариант, в котором зона наложения считается частью каждого из прилегающих к ней объектов.

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

Литература

ПРИЛОЖЕНИЕ

а)	б)
в)	г)

Рисунок 3. а) исходное изображение «карта 1»;
б), в), г) бинаризованное изображение «карта 1» методами Бернсена (б),
Бернсена с постпроцессингом (в), Эйквеля с постпроцессингом (г).

а)	б)
в)	г)
д)	е)

Рисунок 4. а) исходное изображение «кабели»;
б), в), г), д), е) бинаризованное изображение «кабели» методами Бернсена (б),
Бернсена с постпроцессингом (в), Отса (г), Яновица и Брукштэйна (д),
Эйквеля с постпроцессингом (е).

а)	б)
в)	г)

Рисунок 5. а) исходное изображение «карта 2»;
б), в), г) бинаризованное изображение «карта 2» методами Ниблэка с постпроцессингом (б),
Яновица и Брукштэйна (в), Отса (г).

а)	б)
в)	г)
д)	е)

Рисунок 6. а) исходное изображение «негатив»;
б), в), г), д), е) бинаризованное изображение «негатив» методами Бернсена (б),
Бернсена с постпроцессингом (в), Эйквеля (г), Эйквеля с постпроцессингом (д),
Яновица и Брукштэйна (е).