A recognition problem of binary images by the methods of percolation theory.pdf В последнее время задача распознавания бинарных изображений приобрела особую значимость в связи с автоматизацией процессов сортировки железнодорожных вагонов и морских контейнеров. Основным направлением исследований является поиск и разработка методов удаления шумов из исходного изображения. В значительно меньшей степени исследовались задачи улучшения качества распознавания изображений с искажениями, вызванными движением и изменением угла зрения. Особенно большие проблемы возникают с изображениями, смазанными вдоль некоторого направления (рис. 1). Современные специализированные программы распознавания с большим трудом справляются с подобными задачами. На практике, как правило, особое внимание уделяется двум подходам к улучшению бинарных изображений: нейросетевому методу и методу клеточных автоматов. Метод клеточных автоматов заключается в следующем: при рассмотрении пикселя изображения учитываются цвета его соседей, и если его соседи имеют кардинально другой цвет, этот пиксель считают шумом. Недостатком данного метода является неправильная обработка небольших объектов. Так, например, линия будет полностью удалена, потому что ее толщина крайне мала. Также недостатком является невозможность обработки размытых изображений. При размытии изображения шум не является регулярным, и он не будет удален, так как шумовые пиксели будут окружены такими же темными пикселями. Нейросетевой метод улучшения изображений заключается в векторизации изображения, его аппроксимации и использовании некоторой функции T, которая обрабатывает изображение. Основные недостатки данного метода: крайняя степень неуниверсальности метода; при изменении конфигурации изображения нейронную сеть придется обучать заново. В задаче удаления шума нейронные сети эффективно справляются лишь с регулярными шумами. В настоящей работе на основе перколяционного подхода [1, 2] рассматривается задача предобработки бинарных изображений для улучшения эффективности их распознавания. Этот подход предлагает рассматривать зашумленное бинарное изображение как набор перколяционных кластеров. Математическая теория перколяции дает ряд результатов, касающихся поведения функции n(s) - плотности числа кластеров массы s. Наличие изображения в шуме, возможно, поменяет поведение этой функции. Если при этом знать a priory, какое изображение может появиться, то байесовский подход позволяет дать ответ, есть ли в данном зашумленном изображении такой объект или нет [3]. Рис. 1. Пример размытого изображения 1. Асимптотика функции распределения кластеров по их весу Вес кластера S - количество ячеек, которое кластер занимает на решетке. Функция n(s) дает зависимость процентного содержания кластеров веса s. Теорема [2]. Асимптотическое распределение веса кластеров на двумерной перколяционной решетке при p = р(крит) имеет вид n(S) «aS"x,S ^гс, (1) где n(S) - процентное содержание кластеров веса S. Значение константы т рекомендуется принять равным 187/91. Основная задача, решение которой необходимо для улучшения изображений в данном подходе, - это разделение кластеров решетки на предполагаемые кластеры оригинального изображения и так называемые шумовые кластеры. Найдя и удалив шумовые кластеры, мы улучшим изображение. Авторам известны два подхода к обработке изображений, использующих методы перколяционной теории. В первом подходе [1] было замечено, что график n(S) зашумленного изображения в двойном логарифмическом масштабе имеет в некоторых случаях характерный излом, соответствующий появлению оригинального изображения. Как видно из приведенного на рис. 2 графика, взятого из [1], при s > 50 наблюдается резкое различие (излом в оригинальном изложении) в поведении двух функций распределения для исходного изображения и цифрового шума. Ясно видно, что при s > 50 находятся в основном кластеры исходного изображения. В работе [1] предлагалось сохранять только эти кластеры, а остальные удалять. Рис. 2. График распределения кластеров в двойном логарифмическом масштабе [1] Во втором подходе [3] основной задачей ставилась проверка гипотезы наличия какого-либо известного заранее объекта в зашумленном изображении. Предложенный в [3] метод основан на вычислении вероятности появления кластера максимального размера в зашумленном изображении. Эти вычисления основаны на формуле (1). При этом предполагается, что шум в некотором смысле «не сильно портит» изображение. В настоящей статье предлагается новый подход к предобработке монохромных изображений. Он основан на анализе функции распределения веса кластера зашумленного изображения. Новизна предлагаемого подхода состоит в том, что решение о принадлежности данного кластера к исходному изображению принимается на основе вычисления расхождения графиков функций распределения весов кластера и носит вероятностный характер. Таким образом, алгоритм не является строго детерминированным и относится к семейству методов Монте-Карло. Формула (1) дает асимптотику распределения кластеров на пороге протекания. По этой причине ее использование не может быть достаточно эффективным при различных интенсивностях за-шумления. В [3] в результате компьютерных экспериментов напрямую вычисляли значение n(s) для шума разной интенсивности. Таким образом, еще раз нарушался детерминизм метода, что вообще связано со всеми алгоритмами типа Монте-Карло. Новизна данной статьи заключается также в попытке применения идей теории перколяции в задаче улучшения изображений. Основной целью являлись разработка метода, основанного на результатах перколяционной теории, написание и тестирование комплекса программ для улучшения изображений. 2. Алгоритм предобработки бинарных изображений Предлагается вместо интуитивного и трудно алгоритмизируемого понятия Саповала [1] «излома» функции распределения веса кластеров использовать разность функций распределения кластеров исходного изображения и такой же функции цифрового шума. Именно эта разность будет учитываться при принятии решения об удалении кластера для каждого значения s. Алгоритм удаления шума с изображения: суммируем значение двух распределений - исходного изображения A = r(s) и шумового B = n(s) (рис. 3) в некоторой точке s: r(S) + n(S) = MN . (2) Построим отрезок MN = MO + ON, где MO = AC, ON = BC. Возьмем значение некоторой случайной величины z, равномерно распределенной на отрезке MN. Возможны следующие два варианта расположения точки z: 1. Если z попадает на отрезок MO, то данный кластер является оригинальным и его необходимо оставить. Эта ситуация изображена на рис. 8. 2. Если z попадает на отрезок ON, то данный кластер является шумовым и его необходимо удалить. Рис. 3. Графики функций распределения A(s) и B(s) (светлая линия -график распределения кластеров размера n на исходном изображении; тёмная линия - на сгенерированном шуме) На начальном этапе исследования в качестве G(s) мы использовали точную аналитическую формулу (1), однако в дальнейшем от этого пришлось отказаться. Причина состоит в том, что формула (1) имеет асимптотический вид и характеризуется невысокой точностью при малых s. По этой причине величина G(s) вычислялась в результате компьютерного моделирования шумов различной интенсивности. После перехода к этому методу вычисления G(s) эффективность разрабатываемого алгоритма заметно увеличилась. 3. Результаты компьютерного моделирования Рассмотрим три рисунка: оригинальное изображение, образец шума и зашумленное изображение. Для эксперимента выберем решетку высотой в 29 и шириной в 14 ячеек. 1 Рис. 6. Зашумленное изображение, качество которого необходимо улучшить Рис. 4. Оригинальное изображение Рис. 5. Образец шума На рис. 5 представлена матрица с вероятностью зашумления p0 = 0,60. На рис. 6 изображена оригинальная единица, зашумленная с вероятностью p0 = 0,20. Был построен график зависимости числа кластеров от их веса для эталонного шума и для зашумленного изображения. Как видим на рис. 7, вероятность появления кластеров небольшого веса велика - от общего числа кластеров они составляют более половины. Теперь пронормируем оба графика и наложим их друг на друга. Далее для каждого значения s составим свой отрезок MN(s) и предложенным выше методом решим, удалять данный кластер из исходного изображения или нет. Результат применения данного метода приведен на рис. 7, 8. т- ■ п ■ I ■ Рис. 7. Изображение до обработки Рис. 8. Изображение после обработки 4. Применение метода для улучшения качества монохромных изображений Исследуем влияние степени зашумленности изображения p0 на качество восстановленных монохромных изображений. В данной ситуации используем регулярный шум. Для того чтобы обработать монохромное изображение, представим его как 255 (число оттенков черного цвета в палитре RGB) бинарных изображений и обработаем каждое из них по отдельности, после соединим обратно в монохромное. Для данного исследования возьмем нетривиальное искажение изображения, возникающее при съемке с большой выдержкой. Как известно, при данных условиях съемки за изображением возникает шумовой «хвост». На рис. 9 приведен пример изображения, снятого с большой выдержкой и естественным шумом, после чего нами подбирался параметр p, отвечающий за размеры удаляемых кластеров. Результат приведены на рис. 10. p = 0,60 p = 0,99 Рис. 10. Результат применения метода при обработке размытого изображения Как видно из рисунка, метод хорошо проявляет себя при обработке подобных изображений. При p = 0,20; 0,30 и 0,60 изображение восстановилось до контуров оригинальных букв. Лучше всего изображение выглядит при p = 0,30. Из вышеизложенного можно сделать вывод, что метод является универсальным и подходит для обработки изображений с шумами различных конфигураций. 5. Эксперименты с реальными данными Рис. 9. Искажение изображения при съемке с большой выдержкой Для анализа эффективности применения метода на практике использовалось стороннее ПО для распознавания изображения. Ниже приведены примеры работы программы - распознавателя текста «FineReader» для оригинального и обработанного изображения. Как вы видно из приведенной ниже таблицы, на необработанном изображении «FineReader» не смог выделить текстовую область, после обработки же изображение полностью распозналось. Исходное изображение Результат распознавания Невозможно распознать данную область. На ней отсутствует текст AO 165 Заключение Результат данной работы - реализация нового метода улучшения изображений, основанного на крайне специфичном способе применения перколяционной теории. Компьютерное моделирование на основе разработанного метода показало его высокую эффективность. При этом он является достаточно недорогим для аппаратной реализации.

Скачать электронную версию публикации