В статье предложен метод анализа изображений с помощью графового представления. Вершинами графа служат пиксели изображения. Ребрами соединены только ближайшие соседи на изображении. Вес ребра определяется цветом, соединяемых вершин. Для полученного графа осуществляется поиск сообществ, позволяющий выявить фрагменты изображения, схожие по цвету. Предложенный подход применяется для подавления импульсного шума на изображении. Проведен компьютерный эксперимент. Показано, что предложенный метод более эффективен, чем традиционные фильтры.
Будем применять алгоритм фильтрации к зашумленному изображению размерами × пикселей. Положение каждого пикселя на изображении может быть задано парой целых чисел (, ), которые можно считать геометрическими координатами. Число лежит на отрезке [0, − 1], а число y – на отрезке [0, − 1]. Будем использовать цветовую модель RGB. В этом случае для каждого пикселя с координатами (, ) определены три цветовые функции: (, ) – интенсивность красного цвета, (, ) – интенсивность зеленого цвета, (, ) – интенсивность синего цвета.
Для каждого изображения однозначным образом может быть построен неориентированный взвешенный граф , показывающий изменения цвета при переходе от одного пикселя к другому. Множество вершины графа совпадает с множеством пикселей изображения. Ребрами будем соединять только ближайшие соседние пиксели. Вес ребра будем вычислять на основе цветовых компонент пикселей, соединенных этим ребром. Для двух соседних вершин = (, ) и = (, ) вес ребра будет равен:
1 √︁ (, ) = exp(− ℎ
( − )2 + ( − )2 + ( − )2). Здесь = (, ), = (, ), = (, ).
Параметр ℎ определяет значение разности цвета между соседними пикселями, соответствующее
переходу через границу двух сегментов. Данный параметр определяется пользователем и является общим
для всего изображения. Как показано в работах [
Определим матрицу весов для графа . Значения диагональных элементов равно весу вершин. В
начале работы алгоритма вес всех вершин нулевой. Остальные элементы матрицы весов ( ̸= ) равны
весу соответствующего ребра. Следует отметить, что в матрице будет много нулевых элементов, так как
в графе ребрами соединены только вершины, соответствующие ближайшим соседям на изображении.
Матрица будет симметричной относительно главной диагонали, так как граф неориентированный.
Перейдём к приведенному виду матрицы весов = /, где
Элемент равен доле веса заданного ребра в общем весе графа. В дальнейшем под матрицей весов будет
пониматься именно приведенный вид. Легко видеть, что
Величина модульности определяется выражением [
,=1 ∑︁ = 1. ,=1 Для поиска сообществ на графе используем процедуру образования стяжек. Под стяжкой понимается преобразование, при котором некоторый подграф графа заменяется одной вершиной . Если какаято из вершин подграфа была связана ребром с вершиной из подграфа ∖, то вершина также будет связана ребром того же веса с вершиной . Вес новой вершины будет равен сумме весов ребер и вершин, входящих в подграф . Новый граф обозначим . Подграф будем считать сообществом, если ( ) > (). Следует отметить, что при образовании стяжки уменьшается число вершин графа . Нашей задачей стоит поиск вершин графа, не входящих ни в одно более крупное сообщество. Выявление таких вершин будем осуществлять с помощью следующего алгоритма.
1. Осуществляем последовательный проход по всем пикселям изображения.
2. Для каждого пикселя поочередно рассматриваем ближайшие соседние пиксели () ( = 1, ..., 8). Рассматриваем подграфы, состоящие из двух вершин и () ( = 1, ..., 8) и пытаемся объединить их в сообщество. При каждом объединении вычисляем изменение функции модульности ( = 1, ..., 8).
3. Если при объединении данной вершины в сообщества со всеми ближайшими соседями изменение функции модульности отрицательно ( < 0, = 1, ..., 8), то соответствующий пиксель считаем поврежденным.
Изменение функции модульности достаточно быстро вычисляется из текущих характеристик графа, соответствующего изображению. При объединении вершин и изменение модульности будет иметь вид:
= 2( − ). Очевидно, что предложенный алгоритм имеет линейную трудоемкость от числа пикселей.
После выявления поврежденных пикселей необходимо выбрать для них цвет из анализа окружающих пикселей. Для этого проанализируем ближайших соседей. Пусть минимальное значение цветовой компоненты пикселей соседних с поврежденным пикселем равно 1, а максимальное – 2. Проведем последовательный перебор всех значений цвета поврежденного пикселя от 1 до 2. Для каждого значения будем вычислять значение изменения функции модульности при объединении данной вершины в сообщество с одним из ближайших соседей. В качестве окончательного цвета оставим тот, который позволяет получить максимальное значение изменения функции модульности. 2
Компьютерный эксперимент Компьютерный эксперимент проводился как на искусственных изображениях геометрических объектов, так и на цветных фотографиях. Уровень импульсного шума характеризовался величиной , показывающей процент поврежденных пикселей по отношению к общему количеству пикселей изображения. Импульсный шум моделировался с помощью линейного конгруэнтного генератора псевдослучайных чисел, с помощью которого определялись как координаты поврежденных пикселей, так и их цвет. При проведении компьютерного эксперимента процент испорченных пикселей варьировался от 10% до 70%. Улучшение изображения производилось с помощью предложенного фильтра, а также, для сравнения, с помощью широко распространенного медианного фильтра.
Для сравнения близости изображений использовалась метрика Минковского [
(, ) = max ∑=︁1 1 |() − ()|. где и – значения цветов пикселей изображения A и С, – количество пикселей.
Относительное улучшение изображения вычислялось на основе расстояния (, ) от восстановленного изображения до исходного и расстояния (, ) от испорченного изображения до исходного изображения : = (, ) − (, ) (, ) · 100%.
Эксперимент для прямоугольной области с равномерной заливкой показал, что предложенный фильтр позволяет значительно улучшить изображение. Зависимость относительного улучшения от процента испорченных пикселей для предложенного фильтра и медианного фильтра представлены на рисунке 1. Рис. 1: Зависимость относительного улучшения изображения от процента зашумления для предложенного фильтра (сплошная линия) и медианного фильтра (пунктирная линия)
Результаты применения предложенного фильтра и медианного фильтра для улучшения искусственного изображения с наличием сплошной и градиентной заливки представлены на рисунке 2. Рис. 2: Результаты применения фильтра к искусственному изображению с уровнем шума p=20%: а) исходное изображение, б) зашумленное изображение, в) изображение восстановленное предложенным фильтром, г) изображение восстановленное медианным фильтром
Как хорошо видно из рисунка 2 результаты предложенного фильтра более выигрышно выглядят для темных участков изображения, тогда как медианный фильтр дает лучший визуальный результат для светлой части изображения. Этот эффект связан с выбором нового цвета испорченного пикселя. При использовании медианного фильтра цвета восстановленных пикселей смещены в область белого цвета. При этом цвета окружающих его пикселей также изменяют свой цвет. Численное сравнение результатов работы показывает значительное преимущество предложенного алгоритма перед медианным фильтром.
Зависимость относительного улучшения от процента зашумления искусственного изображения представлена на рисунке 3.
Также данный фильтр позволяет получить значительно лучшие результаты и для фотографических изображений. Результаты для хорошо известного изображения «Lena» при уровне зашумления = 20% представлены на рисунке 4. Рис. 3: Зависимость относительного улучшения от процента зашумления искусственного изображения для предложенного фильтра (сплошная линия) и медианного фильтра (пунктирная линия) Рис. 4: Результаты применения фильтра к изображению «Lena» с уровнем шума = 20%: а) исходное изображение, б) зашумленное изображение, в) изображение, восстановленное предложенным фильтром, г) изображение, восстановленное медианным фильтром
Хорошо известно, что изображение «Lena» характеризуется большим количеством мелких деталей, которые создают сложности для всех фильтров. Как видно из рисунка 4 предложенный фильтр дает значительно лучшие результаты даже при визуальном сравнении. Зависимость относительного улучшения от процента зашумления представлена на рисунке 5. 3
Выводы Таким образом, предложенный фильтр обладает хорошими характеристиками при линейной трудоемкости. Как видно из графиков, представленных на рисунках 1, 3 и 5 эффективность данного фильтра примерно на 20% выше, чем медианного при любом проценте испорченных пикселей. Такое заметное преимущество объясняется тем, что обычные фильтры изменяют все пиксели изображения. Исправление испорченных пикселей приближает изображение к оригиналу, но при этом изменение неиспорченных пикселей увеличивает расстояние до оригинала. Данное свойство присуще не только медианному фильтру, но и всем традиционным фильтрам.
Предложенный в данной статье фильтр действует избирательно и изменяет только те пиксели, которые значительно отличаются от окружающих. С высокой вероятностью такие пиксели окажутся поврежденными импульсным шумом. Выбор нового цвета на основе присоединения к одному из соседних сообществ пикселей позволяет формировать группы близких по характеристикам точек. Список литературы [1] I. Pitas, A. Venetsanopoulos. Nonlinear Digital Filters: Principles and Applications. Boston, MA: Kluwer, 1990, 392 p. Рис. 5: Зависимость относительного улучшения от процента зашумления изображения «Lena» с помощью предложенного фильтра (сплошная линия) и медианного фильтра (пунктирная линия)
Sergey V. Belim, Stanislav B. Larionov
In article the images analysis method by means of graph representation is suggested. Image pixels are compared to graph vertex. By edges only the closest neighbors on the image are connected. Weight of an edge is defined by color, the connected vertex. For the received graph search of communities is carried out, allowing to reveal the image fragments similar in color. The suggested approach is applied to impulse noise suppression on the image. The computer experiment is made. It is shown that the suggested method is more efective, than traditional iflters.