СПОСОБ ПОМЕХОУСТОЙЧИВОГО ГРАДИЕНТНОГО ВЫДЕЛЕНИЯ КОНТУРОВ ОБЪЕКТОВ НА ЦИФРОВЫХ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЯХ
METHOD FOR NOISELESS GRADIENT SELECTION OF OBJECT CONTOURS ON DIGITAL HALFTONE IMAGES

Изобретение относится к области цифровой обработки изображений и может быть использовано в фото-, видео-, оптико-локационной и оптико-электронной технике при решении задач распознавания образов по их контурам на цифровых изображениях.
Необходимыми условиями того, что через некоторую точку цифрового полутонового изображения проходит контур, являются следующие:
1) резкое изменение яркости в данной точке по сравнению хотя бы с одной из соседних точек;
2) наличие хотя бы двух соседних точек, сопоставимых по яркости с рассматриваемой точкой.
В связи с этим большинство известных способов выделения контуров на цифровых полутоновых изображениях основаны на вычислении модуля градиента на всей площади цифрового изображения по приближениям первой производной - локальным конечным разностям яркости. При этом приближенные компоненты градиента вычисляют с использованием скользящего окна (маски), перемещающегося по всему изображению. При этом яркости пикселей изображения, попадающих в скользящее окно, перемножают на коэффициенты маски, а затем суммируют [1 - Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.: Техносфера, 2005, 1072 с.; 2 - Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. - М.: Техносфера, 2006, 616 с.; 3 - Прэтт У. Цифровая обработка изображений: Пер. с англ. - М.: Мир, 1982. Кн. 2. 480 с.; 4 - Гданский Н.И., Марченко Ю.А. Градиентный способ выделения контуров объектов на матрице полутонового растрового изображения. // Патент РФ №2325044 на изобретение. МПК H04N 1/409, G06K 9/46. Заявит. Гданский Н.И., Марченко Ю.А. Патентообл. МГУИЭ. - № 2007106412/09; заявл. 21.02.2007; опубл. 20.05.2008].
В настоящее время известно несколько типов масок: Робертса, Превитта, Собела, Щарра и др. Маска Робертса является наиболее простой, поскольку имеет размер 2×2 элемента. Маски Превитта, Собела и Щарра имеют размерность 3x3 пикселя и отличаются значениями коэффициентов. Недостатками способов выделения контуров изображений с помощью скользящих окон и определения компонент градиента яркости с помощью конечных разностей является их достаточно сильная чувствительность к помехам, относящимся к классу импульсных, возникающих вследствие многих явлений при цифровом преобразовании и передаче изображений (пораженные пиксели).
К другим способам выделения контуров объектов на изображениях относятся способы, основанные на вычислении приближений вторых производных - операторы типа «лапласиан», «гауссиан», или операторы, использующие разновидности масок Лапласа. Известна также корреляционная маска, коэффициенты которой пропорциональны соответствующим коэффициентам корреляции элементов изображения. В случае когда корреляция между элементами изображения отсутствует, маска не оказывает влияния на изображение, в противоположном случае коэффициент корреляции равен единице, данная маска сводится к маске Лапласа [3, С. 500-508]. Данные способы благодаря пересечению нулевого уровня прямой, соединяющей разнозначные вторые производные, позволяют получить более точное положение контура, но являются более чувствительными к различным помехам, в том числе и импульсным, чем градиентные, а также имеют недостаток, связанный с обнаружением многочисленных ложных замкнутых кривых.
Также известны способы выделения контуров объектов на изображениях, более далекие от заявляемого способа, которые основаны на аппроксимации перепадов яркости и статистические способы, например, метод на основе локально-полиномиальной аппроксимации [5 - Sherstobitov A.I., Marchuk V.I., Timofeev D.V., Voronin V.V., Egiazarian K.O. Local feature descriptor based on 2D local polynomial approximation kernel indices. Image Processing: Algorithms and Systems XII, edited by Karen O. Egiazarian, Sos S. Agaian, Atanas P. Gotchev, Proceedings of SPIE Vol. 9019 (SPIE, San Francisco, WA 2014) 901908, DOI: 10.1117/12.2041610]. Однако они также чувствительны к наличию на матрице цифрового изображения импульсных помех.
Следует отметить, что повышение устойчивости известных способов выделения контуров изображения возможно за счет предварительной коррекции изображения, связанной со сглаживанием яркости изображения. Однако такой подход может привести не только к устранению импульсных помех, но и к потере части полезной информации о контуре изображения.
Наиболее близким по технической сущности к заявляемому способу является способ помехоустойчивого градиентного выделения контуров объектов на цифровых изображениях [6 - Самойлин Е.А. Способ помехоустойчивого градиентного выделения контуров объектов на цифровых изображениях // Патент РФ № 2360289, МПК G06K 9/48. Заявит. Самойлин Е.А. Патентообл. Самойлин Е.А. - № 2008133097/09; заявл. 11.08.2008; опубл. 27.06.2009 Бюл. № 18], включающий операции оценивания локализации импульсных помех на цифровом полутоновом изображении, формирования четырех вспомогательных масок, а также четырех соответствующих управляющих векторов, операцию изменения коэффициентов соответствующих четырех разноориентированных масок Превитта, а также операции оценки приближенного значения модуля градиента яркости изображения, и получения контура изображения путем порогового преобразования матрицы модулей градиента яркости изображения.
Недостатком способа-прототипа является то, что вычисление значений коэффициентов откорректированной маски Превитта является дискретным и определяется на основе приближенного порогового формирования управляющего вектора. В результате в отличие от известных способов способ-прототип хотя и имеет пониженную чувствительность к импульсным помехам, однако позволяет определить только приближенные значения компонент градиента яркости изображения в точке, которые необходимы для вычисления контуров. Это может привести к снижению качества формируемых контуров в случае отсутствия или при слабых импульсных помехах.
Задачей, на решение которой направлено изобретение, является повышение качества формирования контуров полутоновых изображений в условиях помех.
x
y
Для решения указанной задачи предлагаемый способ помехоустойчивого градиентного выделения контуров объектов на цифровых полутоновых изображениях состоит в определении модуля градиента яркости в каждой точке изображения, пороговом преобразовании модуля градиента яркости, в ходе которого формируют контуры объектов путем выделения на новой белой матрице черным цветом элементов, модуль градиента которых в соответствующих координатах изображения превышает порог преобразования. В отличие от прототипа сначала вычисляют прямое вейвлет-преобразование строк и столбцов цифрового полутонового изображения, а затем формируют две матрицы g и g компонент градиента яркости в каждой точке изображения путем обратного вейвлет преобразования, в котором в качестве ядра преобразования используют аналитические функции, описывающие производные используемых вейвлетов обратного преобразования по соответствующим координатам. После этого модуль градиента яркости в точке изображения определяют путем вычисления квадратного корня из суммы квадратов найденных компонент градиента, а пороговое преобразование, приводящее к выделению контуров изображения, осуществляют, как и в прототипе.
Сравнительный анализ способа-прототипа и предлагаемого способа показывает, что в предлагаемом способе введены операции:
- прямое вейвлет-преобразование строк и столбцов цифрового полутонового изображения;
x
y
- формирование двух матриц g и g компонент градиента яркости в каждой точке изображения путем обратного вейвлет-преобразования, в котором в качестве ядра преобразования используют аналитические функции, описывающие производные используемых вейвлетов обратного преобразования по соответствующим координатам.
- изменен режим выполнения операции вычисления модуля градиента яркости изображения в каждой точке путем суммирования двух модулей найденных компонент.
Введение двух операций и изменение режима одной операции позволяет, по сравнению со способом-прототипом, обеспечить достижение технического результата, состоящего в повышении качества формирования контуров полутоновых изображений в условиях помех.
Предлагаемое изобретение не известно из анализа уровня техники, а также не известны источники информации, содержащие сведения об аналогичных технических решениях, имеющих признаки, сходные с признаками, отличающими заявляемое решение от прототипа, а также свойства, совпадающие со свойствами заявляемого решения, поэтому можно считать, что оно обладает существенными отличиями, вытекает из них неочевидным образом и, следовательно, соответствует критериям «новизна» и «изобретательский уровень».
Сущность предлагаемого способа раскрывается фигурами 1-6.
На фигуре 1 приведена структурная схема устройства, реализующего предлагаемый способ помехоустойчивого градиентного выделения контуров объектов на цифровых полутоновых изображениях.
На фигуре 2 показано исходное цифровое полутоновое изображение и результат выделения контуров данного изображения при отсутствии шумов.
На фигуре 3 показаны тестовые цифровые полутоновые изображения с наложенным на них шумом.
На фигуре 4 приведены изображения, иллюстрирующие результаты выделения контуров с использованием способа-прототипа для каждого из зашумленных изображений на фигуре 3.
На фигуре 5 отображены результаты выделения контуров предлагаемым способом.
На фигуре 6 представлены оценки эффективности, иллюстрирующие выигрыш в помехоустойчивости при использовании предлагаемого способа по сравнению с прототипом.
При реализации предлагаемого способа помехоустойчивого градиентного выделения контуров объектов на цифровых полутоновых изображениях выполняется следующая последовательность операций:
- вычисляют прямое вейвлет-преобразование строк и столбцов цифрового полутонового изображения;
x
y
- формируют две матрицы g и g компонент градиента яркости в каждой точке изображения путем обратного вейвлет-преобразования, в котором в качестве ядра преобразования используют аналитические функции, описывающие производные используемых вейвлетов обратного преобразования по соответствующим координатам;
x
y
- определяют модуль градиента яркости в каждой точке изображения путем вычисления квадратного корня из суммы квадратов g и g компонент градиента яркости изображения;
- выполняют пороговое преобразование модуля градиента яркости, в ходе которого формируют контуры объектов путем выделения на новой белой матрице черным цветом элементов, модуль градиента которых в соответствующих координатах изображения превышает порог преобразования.
Прежде чем рассмотреть работу устройства выделения контуров, для обоснования способа изложим следующее.
Пусть имеется некоторая функция В(x), описывающая распределение яркости изображения вдоль одной строки или столбца цифрового полутонового изображения.
Представим данную функцию в виде разложения в конечный ряд по базисным функциям ϕ(n,x):
n
где A - постоянные коэффициенты разложения.
N
Тогда ее производная может быть также представлена в виде ряда с этими же коэффициентами: d  d
i
Отсюда следует, что для расчета градиента яркости изображения в строке достаточно найти коэффициенты разложения функции B(x) в выбранном базисе и найти производные используемых базисных функций.
Однако при использовании обычных базисных функций для описания распределения яркости изображения возникают проблемы, обусловленные тем, что яркость в двух соседних точках может изменяться скачком, т.е. распределение яркости необходимо описывать с помощью функций, имеющих разрывы. В настоящее время описание сигналов с локальными особенностями наиболее удобно осуществлять с помощью вейвлетов [7 - Смоленцев Н.К. Введение в теорию вейвлетов. - Ижевск: РХД, 2010. - 292 с.; 8 - Дьяконов В.П. Вейвлеты. От теории к практике. - М.: СОЛОН-Р, 2002, 448 с.]. При этом дополнительным преимуществом вейвлет-преобразования является возможность сокращения избыточности информации и в очистке сигналов от шума, например, за счет ограничения уровня детализирующих коэффициентов [8, с. 4, с. 89-90].
m,n
В результате дискретного вейвлет-преобразования исходной функции В(x) будет получена двумерная матрица коэффициентов W, с помощью которой производная функции будет строиться по аналогии с (1) в виде двумерного ряда:
где N - длина строки (столбца) изображения;
М - количество уровней разбиений изображения.
Поскольку в настоящее время для обработки изображений используются различные вейвлеты, приведем несколько классических вейвлетов DOG, Mhat, Wave и их производные.
Рассмотрим конкретизирующие выражения для вейвлета DOG:
Тогда выражение для вейвлета DOG в дискретной форме будет иметь следующий вид:
Производная данного вейвлета может быть записана в виде:
Аналогично для вейвлета МНАТ получим:
Применительно к вейвлету WAVE аналогичные соотношения имеют вид
С учетом сделанных замечаний перейдем к процессу выделения контуров с помощью вейвлет преобразований.
Пусть распределение яркости изображения задает матрица S(i,j).
При этом прямое дискретное вейвлет преобразование для строк и столбцов осуществляется по формулам:
соответственно.
Если выбранному виду вейвлета соответствует его производная, то обратное преобразование, позволяющее получить компоненты градиента яркости исходного изображения, можно найти по формулам:
ψ
где C - коэффициент нормировки для обратного вейвлет-преобразования. Для приведенных соотношений данный коэффициент равен единице.
Модуль градиента яркости изображения будем определять по формуле
В результате пороговое преобразование описывается соотношением:
где P - значение порога.
Рассмотрим функционирование устройства выделения контуров.
В состав устройства выделения контуров на фиг. 1 входят блоки 1 и 2 вейвлет-преобразования исходного изображения (БВП), блоки 3 и 4 вычисления матриц x- и y-компонент градиента яркости изображения (БВКГ), блок 5 определения модуля градиента яркости изображения (БОМГ), блок 6 порогового преобразования (БПП).
Общим входом устройства являются входы БВП 1 и БВП 2, выход БВП 1 подключен ко входу БВКГ 3, выход которого соединен с первым входом БВМГ 5, выход БВП 2 связан со входом БВКГ 4, выход которого подключен ко второму входу БВМГ 5, выход БВМГ 5 связан со входом БПП 6, выход которого является выходом устройства.
Устройство работает следующим образом.
x
y
На входы БВП 1 и БВП 2 поступает двумерное распределение яркости сигнала, задаваемое матрицей яркости S(i,j) цифрового полутонового изображения (i=1,2,…,I; j=1,2,…,J). В БВП 1 осуществляется вейвлет-преобразование матрицы яркости S(i,j) по формуле (13). Полученные вейвлет-спектрограммы с выхода БВП 1 поступают на вход БВКГ 3, в котором преобразование сигналов осуществляется по формуле (15). На выходе БВКГ 3 формируется двумерная матрица g, элементы которой содержат значения производных яркости в каждой точке изображения вдоль строки. Данные сигналы поступают на первый вход БОМГ 5. Двумерное распределение яркости сигнала, описываемое матрицей S(i,j) и поступающее на вход БВП 3 преобразуется в нем по формуле (14). Результат вейвлет-преобразования передается на вход БВКГ 4, в котором рассчитывается матрица g, элементы которой содержат значения производных яркости в каждой точке изображения вдоль столбца. Данная матрица поступает на второй вход БОМГ 5. В БОМГ 5 осуществляется процедура расчета модуля градиента яркости по формуле (18), приводящая к построению двумерной матрицы, описывающей распределение модуля градиента яркости изображения, соответствующее каждой точке исходного изображения. Эта матрица поступает на вход БПП 6, в котором осуществляется формирование двумерной матрицы контуров Q(i,j) по формуле (19). Полученная матрица поступает на выход устройства, где может быть визуализирована или сохранена в памяти ЭВМ.
В качестве примера рассмотрим задачу выделения контуров на цифровом полутоновом изображении.
0
0
0
Для формирования тестовых изображений использовался следующий алгоритм. Матрица яркости S(i,j) исходного полутонового изображения, в котором отсутствовали шумы, обрабатывалась детектором границ «Canny». В результате было получено изображение контуров Qo{i,j), соответствующее матрице яркости S(i,j) при отсутствии шумов. Изображения, соответствующие матрицам S(i,j) и Qo(i,j) приведены на фиг. 2 (левое и правое поле соответственно).
0
0
Далее в исходное цифровое полутоновое изображение был добавлен шум (матрица n(i,j)). В качестве модели шума использовался белый гауссовский шум. В качестве математического ожидания при формировании зашумленного изображения использовалось значение яркости матрицы S(i,j) в данной точке, СКО шума составляло для тестовых примеров 10, 20 и 30 (в исходном изображении использовалось 256 градаций яркости). В результате были получены изображения, которым соответствуют матрицы яркости S(i,j) = S(i,j)+n(i,j), представленные на фиг. 3 (слева направо изменяется величина СКО шума: 10, 20 и 30 соответственно).
На фиг. 4 приведены матрицы Q(i,j) контуров, выделенных в цифровом полутоновом изображении S(i,j) с использованием способа-прототипа при различном уровне шумов.
Анализ полученных изображений позволяет заключить, что способ-прототип не позволяет качественно выделить контура изображения уже при величине СКО шума, равном 20, а при СКО шума, равном 30 является неработоспособным.
На фиг. 5 приведены изображения матриц Q(i,j) контуров, полученные предлагаемым способом с использованием рассмотренных выше вейвлетов при различном уровне шумов. Результатам использования трех видов вейвлетов соответствуют поля фиг. 5 сверху вниз, а уровню шумов - поля слева направо.
Сопоставление результатов на фиг. 5 показывает, что качество выделения конутуров остается стабильным при СКО шума, достигающем 30. При этом выбор типа вейвлета оказывается не принципиальным.
С целью количественной оценки эффективности предлагаемого способа по сравнению с прототипом использовалось три подхода.
0
Первый состоял в том, что определялась величина СКО между изображениями контуров Q(i,j), полученными предлагаемым способом, а также способом прототипа и изображением контура Q{i,j), полученным при отсутствии шумов.
Оценка СКО осуществлялась по формуле:
Здесь i=0,1,…, N-1, j=0,1,…, M-1.
Результаты данного сопоставления приведены на фиг. 6 (верхнее поле) из рисунка следует, что снижение СКО изображений контуров при использовании предлагаемого способа по отношению к способу прототипу составило около 25% при СКО шума, равном 10 и 72% при СКО шума 20 и 30.
Второй подход состоял в оценке SNRi отношения сигнал/шум (ОСШ) по формулам:
Результаты оценки эффективности применения способа-прототипа показаны на среднем поле фиг. 6. Из анализа рисунка следует, что выигрыш в ОСШ при различном уровне шумов колеблется в интервале 5…6 дБ.
Третий подход к оценке эффективности предлагаемого способа по сравнению со способом-прототипом основан на соотношении:
фон
где: σ - СКО фона;
- среднее значение фона;
1
1
фон
фон
n, m - координаты выбранной площадки фона размером N× N на исследуемом изображении Q(i, j),
Результаты оценок эффективности способа представлены на нижнем поле фиг. 6. В соответствии с данной методикой оценки выигрыш в ОСШ колеблется в интервале от 8 до 10 дБ.
Проведенные численные исследования подтверждают, что с использованием известных авторам методик оценки эффективности выделения контуров на цифровых полутоновых изображениях предлагаемый способ выделения контуров обладает заметным преимуществом по отношению к способу прототипу при различных уровнях шумов и реализациях предлагаемого способа.
В качестве блоков 1-6 рассмотренного устройства обработки изображений могут быть использованы описанные в [8; 9 - Айфичер Э.С, Джервис Б.У. Цифровая обработка сигналов: практический подход. 2-е издание. - М.: Вильямс, 2004. 992 с.; 10 - Куприянов М.С., Матюшкин Б.Л. Техническое обеспечение цифровой обработки сигналов. Справочник. - М.: Наука и техника, 2000. 752 с.], а также любые аналогичные известные из уровня техники технические устройства (программируемые и непрограммируемые процессоры цифровой обработки сигналов и изображений), реализующие соответствующие математические функции (13)-(15), (18), (19).
Например, в [8, с. 410] описывается аппаратная реализация вейвлет-кодека на микросхеме ADV601, которая может быть использована для реализации блоков БВП 1, БВП 2, а также БВКГ 3 и БВКГ 4.
Блоки БВМГ 5 и БПП 6 могут быть реализованы аналогично способу-прототипу в соответствии с описанием в источниках [9, 10].
Приведенные выше материалы подтверждает соответствие критерию "промышленная применимость" предложенного технического решения.
Это означает, что техническим результатом изобретения является повышение качества формирования контуров полутоновых изображений в условиях помех.
Источники информации
1. Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.: Техносфера, 2005. 1072 с.
2. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. - M.: Техносфера, 2006. 616 с.
3. Прэтт У. Цифровая обработка изображений: Пер. с англ. - М.: Мир, 1982. Кн. 2, 480 с.
4. Гданский Н.И., Марченко Ю.А. Градиентный способ выделения контуров объектов на матрице полутонового растрового изображения // Патент РФ №2325044 на изобретение. МПК H04N 1/409, G06K 9/46. 3аявит. Гданский Н.И., Марченко Ю.А. Патентообл. МГУИЭ. - №2007106412/09; заявл. 21.02.2007; опубл. 20.05.2008.
5. Sherstobitov A.I., Marchuk V.I., Timofeev D.V., Voronin V.V., Egiazarian K.О. Local feature descriptor based on 2D local polynomial approximation kernel indices. Image Processing: Algorithms and Systems XII, edited by Karen O. Egiazarian, Sos S. Agaian, Atanas P. Gotchev, Proceedings of SPIE Vol. 9019 (SPIE, San Francisco, WA 2014) 901908, DOI: 10.1117/12.2041610.
6. Самойлин Евгений Александрович. Способ помехоустойчивого градиентного выделения контуров объектов на цифровых изображениях. // Патент РФ № 2360289,, МПК G06K 9/48. Заявит. Самойлин Е.А. Патентообл. Самойлин Е.А. - № 2008133097/09; заявл. 11.08.2008; опубл. 27.06.2009 Бюл. № 18.
7. Смоленцев Н.К. Введение в теорию вейвлетов. - Ижевск: РХД, 2010. - 292 с.
8. Дьяконов В.П. Вейвлеты. От теории к практике. - М.: СОЛОН-Р, 2002, 448 с.
9. Айфичер Э.С., Джервис Б.У. Цифровая обработка сигналов: практический подход. 2-е издание. - М.: Вильямс, 2004. 992 с.
10. Куприянов М.С., Матюшкин Б.Л. Техническое обеспечение цифровой обработки сигналов. Справочник. - М.: Наука и техника, 2000. 752 с.