Исследование метода разреженных представлений для подавления эффекта ложного оконтуривания

ИССЛЕДОВАНИЕ МЕТОДА РАЗРЕЖЕННЫХ ПРЕДСТАВЛЕНИЙ ДЛЯ ПОДАВЛЕНИЯ ЭФФЕКТА ЛОЖНОГО ОКОНТУРИВАНИЯ

А.В. Умнов 1, А.С. Крылов 2 1 Национальный исследовательский университет «Высшая школа экономики», Москва, Россия,

2Московский государственный университет имени М.В. Ломоносова, Москва, Россия

Аннотация

В статье предложен алгоритм решения задачи подавления эффекта ложного оконтуривания на изображениях на основе метода разреженных представлений. Предложенный метод включает в себя в качестве одного из этапов повышение резкости изображений методом де-конволюции Винера-Ханта. Алгоритм подавления эффекта ложного оконтуривания построен на основе результатов анализа взаимной согласованности сигналов и разреженности представлений при работе с эффектом ложного оконтуривания в методе разреженных представлений. Проведен также анализ взаимной согласованности сигналов и разреженности представлений для размытых изображений и изображений с белым гауссовским шумом.

Ключевые слова: эффект ложного оконтуривания, разреженные представления, взаимная согласованность.

Цитирование: Умнов, А.В. Исследование метода разреженных представлений для подавления эффекта ложного оконтуривания / А.В. Умнов, А.С. Крылов // Компьютерная оптика. - 2016. - Т. 40, № 6. - С. 895-903. - Б01: 10.18287/2412-6179-2016-40-6-895-903.

Введение

Эффект ложного оконтуривания - это артефакт, который выражается в осцилляциях вблизи резких контуров на изображениях. Этот эффект возникает при искажении или потере высокочастотной информации на изображении и может появляться в результате работы алгоритмов обработки изображений, на изображениях магнитно-резонансной томографии, на изображениях, подвергнутых передаче через аналоговые каналы связи [1]. В основе этого эффекта лежит эффект Гиббса.

Алгоритмами, в результате которых может появиться эффект ложного оконтуривания, являются увеличение резкости изображения, подавление шума на изображении, повышение разрешения изображения. Наиболее часто встречающимся источником эффекта ложного оконтуривания является сжатие изображений и видео [2]. Пример изображения с эффектом ложного оконтуривания показан на рис. 1.

Рис. 1. Пример изображения с эффектом ложного оконтуривания

Существует множество различных методов обнаружения и подавления эффекта ложного оконтурива-

ния для алгоритмов сжатия JPEG и JPEG 2000 [3 - 6]. С другой стороны, существует не так много алгоритмов, которые рассматривают задачи обнаружения и подавления чистого эффекта ложного оконтуривания с различными параметрами [7 - 11]. Эти алгоритмы подавления основаны на связи эффекта ложного оконтуривания и полной вариации [12, 13], и их основная проблема заключается в том, что они, как правило, не отличают эффект ложного оконтуривания от мелких деталей на изображении, поэтому при обработке детали искажаются. Один из возможных алгоритмов, обходящих эту проблему, представлен в статье [14]. В данной работе мы представляем новый алгоритм подавления эффекта ложного оконтуривания, показывающий более качественные результаты при эффекте ложного оконтуривания высокой силы.

В работе для подавления эффекта ложного окон-туривания используется метод разреженных представлений, который в последнее время широко применяется как в задачах обработки сигналов [12, 15], так и в задачах обработки изображений [16]. Основная идея этого подхода заключается в построении представления исходных данных (в данном случае блоков изображения) в виде линейной комбинации небольшого числа сигналов из заранее выбранного избыточного словаря элементарных сигналов. В результате представление получается одновременно простым и информативным. Более подробно этот подход описан в параграфе 1.

В параграфе 2 проводится анализ взаимной согласованности сигналов и разреженности представлений для изображений с эффектом ложного оконтурива-ния, изображений с белым гауссовским шумом, а также размытых изображений [17]. По результатам этого анализа был разработан новый метод подавления эффекта ложного оконтуривания на изображениях, основанный на разреженных представлениях, который описывается в параграфе 3. Для улучшения ка-

чества работы алгоритма на этапе обучения используется повышение резкости изображений алгоритмом деконволюции Винера-Ханта [18].

1. Разреженные представления

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

Входной сигнал обозначим как вектор у, а словарь элементарных сигналов представим как матрицу Б (записав элементарные сигналы по столбцам), тогда вектор представления с можно искать исходя из следующей задачи:

где ||c||0 - количество ненулевых координат в векторе, £ - порог ошибки представления. В общем случае эта задача является NP-полной, но существуют алгоритмы приближенного решения этой задачи, на практике дающие хорошие результаты [15].

Один из таких алгоритмов - это алгоритм Orthogonal Matching Pursuit (OMP). Его идея заключается в последовательном жадном добавлении элементов к носителю решения. На каждом шаге выбирается такой элемент, чтобы приближение текущим набором элементов было наилучшим. В данной работе нами были также опробованы и другие алгоритмы решения задачи разреженных представлений, но алгоритм OMP дал наилучшие результаты. Поэтому везде далее при построении разреженных представлений используется этот метод.

Словарь задачи (1) может либо выбираться как заранее зафиксированный набор сигналов (например, базис дискретного косинусного преобразования) или же при помощи предварительного обучения на наборе сигналов, аналогичных входному. Второй способ обычно дает более качественные результаты, рассмотрим его подробнее.

Пусть матрица Y - набор сигналов для обучения, записанных в виде столбцов матрицы; матрица C -неизвестные представления этих сигналов (где i-й столбец этой матрицы равен с) и матрица D - искомый словарь. Тогда задача обучения словаря может формулироваться так:

min XIN|0 при условии

IIY - DC\\2 < е.

i

Для этой задачи также существуют приближенные алгоритмы решения, один из которых - алгоритм K-SVD [15]. Этот алгоритм использует идею альтернативной итерации: задача поочередно решается относительно представлений C с фиксированным словарем D и относительно словаря D с фиксированным представлением C. В данной работе нами были также опробованы и другие алгоритмы решения задачи обучения словарей, но алгоритм K-SVD дал наилучшие результаты. Поэтому везде далее при построении словарей используется этот метод.

Алгоритмы вычисления представлений и построения словарей имеют высокую ресурсоемкость, кроме того, построение словарей также требует наличия

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

2. Влияние искажений изображений на метод разреженных представлений

В методе разреженных представлений важную роль играет количество ненулевых коэффициентов в используемых представлениях [15]. Исследуем, как эффект ложного оконтуривания и другие искажения влияют на этот параметр. Помимо эффекта ложного оконтуривания, рассмотрим также размытие изображения и белый гауссовский шум. Дополнительно исследуем влияние повышения резкости методом Вине-ра-Ханта, которое понадобится в параграфе 3 для улучшения предложенного метода.

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

, ч 1(X У)1 т(х у) = | и и •

И Л у12

Пусть Б - словарь со столбцами d1, ..., йт (они же элементарные сигналы), тогда взаимная согласованность словаря определяется так [19]:

т(Б) = тах m(d¡, d ).

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

Н <1 (1 + —

111,0 2 ^ т

Таким образом, мы в дальнейшем будем считать эти параметры обратными (и это будет подтверждено экспериментами). Далее мы приводим соображения, исходя из которых то или иное искажение должно увеличивать или уменьшать взаимную согласованность, и экспериментально подтверждаем предсказанное влияние искажений на взаимную согласованность и разреженность.

Пусть X, У - независимые гауссовские вектора размерности п с независимыми компонентами. Тогда можно показать [20], что

E (m( X, Y) ) =

1

Г

VPr

Эта функция является убывающей, а значит, при увеличении количества независимых компонент уменьшается взаимная согласованность и, следователь-

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

Рассмотрим эффект ложного оконтуривания. Моделирование эффекта ложного оконтуривания происходит следующим образом. Введем параметр ё и обозначим за ¡а маску, удаляющую все частоты вне круга радиуса wа = 1 / (2ё):

¡а(^, wy) =

11, если Л ¡w1x + w2 < wd,

10, если Л/W2 + wy > wd.

Тогда с увеличением параметра а увеличивается и доля удаляемых частот, таким образом этот параметр отвечает за силу эффекта ложного оконтуривания.

Пусть 1(х,у) - некоторое изображение. Тогда, обозначив операторы косинусного преобразования Фурье и обратного к нему как Р и соответственно, введем оператор добавления эффекта ложного окон-туривания силы а:

*а(I) = Р-'(¡а  Р(I)).

Это преобразование является ортогональным, поэтому сохраняет скалярное произведение, нормы и независимость векторов. В частотной области эффект ложного оконтуривания удаляет некоторое количество компонент, поэтому, по утверждению выше, взаимная согласованность должна увеличиваться и, следовательно, должна увеличиваться и разреженность [20].

Эффект размытия также может быть представлен как умножение преобразования Фурье изображения на некоторую маску. Например, в случае гауссовско-го размытия это будет функция Гаусса с центром в точке, соответствующей нулевой частоте. Эта функция значительно уменьшает коэффициенты для одной части частот и полностью обнуляет коэффициенты для другой части частот (с учетом квантования). То есть количество компонент уменьшается и, следовательно, взаимная согласованность и разреженность должны увеличиваться. В результате повышения резкости изображения взаимная согласованность и разреженность должны наоборот уменьшаться.

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

Продемонстрируем теперь приведенные выше соображения с помощью численных экспериментов. Эксперименты производились на изображениях из базы [21].

Для демонстрации влияния различных искажений на взаимную согласованность изображений мы рассмотрели наборы случайных блоков изображений и посчитали среднюю взаимную согласованность для пар блоков из этого набора. Для каждого искажения мы рассмотрели различные значения силы искажения и построили график зависимости средней взаимной согласованности от силы искажения. Эти графики изображены на рис. 2 - 4 для эффекта ложного оконтурива-ния, размытия и шума соответственно. Видно, что для эффекта ложного оконтуривания и размытия взаимная согласованность растет с ростом силы искажения, а для шума наоборот убывает, что соответствует соображениям, описанным выше. Под силой искажения подразумевается доля удаляемых частот в случае эффекта ложного оконтуривания, степень размытия в случае размытия и сила шума в случае белого шума. Средняя согласованность 0,7

1,5 2,0 2,5 3,0

Сила эффекта ложного оконтуривания с1

Рис. 2. Изменение взаимной согласованности

при добавлении эффекта ложного оконтуривания;

пунктиром обозначено значение взаимной согласованности

для обычных изображений, а сплошной линией -

для изображений с различной силой а эффекта

ложного оконтуривания

Средняя согласованность 0,8 I

. . 1,5 2,0

а ядра размытия

Рис. 3. Изменение взаимной согласованности

при добавлении размытия; пунктиром обозначено значение

взаимной согласованности для обычных изображений,

а сплошной линией - для изображений

с различной силой размытия

Средняя согласованность 0,6 —I— -1—

0,5 -0,4 -0,3 -

0,1 - -

О-1-1-1-1-

0,01 0,04 0,07 0,1

Дисперсия шума

Рис. 4. Изменение взаимной согласованности при добавлении шума; пунктиром обозначено значение взаимной согласованности для обычных изображений,

а сплошной линией - для изображений с различной

дисперсией шума

Для оценки подходящей степени разреженности для естественных изображений или изображений с одним из рассматриваемых искажений мы используем обучение словарей на выборке блоков изображений рассматриваемого типа и вычисляем среднюю разреженность по всем представлениям блоков обучающей выборки. Полученная величина зависит не только от типа сигнала, но и от ошибки е, поэтому мы проводим обучение при различных значениях ошибки и строим зависимость разреженности от ошибки. Таким образом, характеристикой разреженности для данного типа и силы искажения является график зависимости разреженности от ошибки е. Ошибка е приводится в терминах метрики PSNR, которая вычисляется по формуле:

PSNR = 10log10 (MAX, MSE),

где MAXi - максимальное значение, принимаемое пикселями на изображении, и MSE - среднеквадратичная ошибка.

Графики зависимости ошибки от разреженности изображены на рис. 5 - 7. Видно, что для эффекта ложного оконтуривания и размытия количество коэффициентов растет с ростом силы искажения, а для шума наоборот убывает, что соответствует соображениям, описанным выше.

На рис. 8 изображены графики разреженности представлений для блоков обычных изображений, изображений с эффектом ложного оконтуривания, а также изображений с эффектом ложного оконтурива-ния после повышения резкости методом деконволю-ции Винера-Ханта. Видно, что повышение резкости повышает количество необходимых коэффициентов.

3. Подавление эффекта ложного оконтуривания

В работе [14] был предложен метод подавления эффекта ложного оконтуривания на основе разреженных представлений, и в этом методе на этапе обучения строился словарь одновременно для изображений

с эффектом ложного оконтуривания и изображений без него (далее будем обозначать этот метод как JC -joint coding).

Рис. 5. Изменение разреженности при добавлении эффекта ложного оконтуривания; сплошная линия соответствует изображениям без искажения, штриховая, штрихпунктирная и точечная соответствуют изображениям с эффектом ложного оконтуривания

с силой искажения d = 1,5; 2; 3 соответственно Количество коэффициентов

_I_I_I_

30 35 40 45 PSNR

Рис. 6. Изменение разреженности при добавлении размытия; сплошная линия соответствует изображениям без искажения, штриховая, штрихпунктирная и точечная соответствуют изображениям с размытием с ядром с а = 0,5; 1; 2 соответственно

На этапе применения алгоритма он работал только с изображениями с эффектом ложного оконтурива-ния, и было обнаружено, что оптимальные параметры разреженности при обучении и применении метода сильно отличались.

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

Далее представлен новый алгоритм подавления эффекта ложного оконтуривания, основанный на ме-

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

30 35 40 45 РБШ

Рис. 7. Изменение разреженности при добавлении шума;

сплошная линия соответствует изображениям без искажения, штриховая, штрихпунктирная и точечная соответствуют изображениям с шумом дисперсией 0,02; 0,05; 0,1 соответственно Количество коэффициентов

30 35 40 45 РБЖ

Рис. 8. Изменение разреженности при повышении резкости; сплошная линия соответствует изображениям без искажения, штриховая соответствует изображению с эффектом ложного оконтуривания с силой искажения, равной 2, штрихпунктирная и точечная соответствуют

предыдущим изображениям с дополнительным повышением резкости с гауссовским ядром с а, равным 1 и 1,5 соответственно

Опишем алгоритм более детально. Для обработки каждого блока алгоритм использует два заранее обученных словаря.

Первый словарь Б1 моделирует изображения без эффекта ложного оконтуривания и обучается на любом наборе блоков естественных изображений.

Второй словарь Б2 моделирует чистый эффект ложного оконтуривания. Для его обучения мы используем разницу между изображением с искус-

ственно созданным эффектом ложного оконтуривания и соответствующим исходным изображением.

Эффект ложного оконтуривания наиболее выражен вблизи резких контуров на изображении. Введем обозначения областей Basic Edge Neighborhood (BEN) и Basic Edge Points (BEP) [1, 9]. Для построения этих областей на изображении находятся ярко выраженные контуры, отстоящие достаточно далеко от других контуров (во избежание интерференции эффекта ложного оконтуривания). Области, соответствующие точкам контура, обозначаются BEP, а области на небольшом расстоянии от них обозначаются BEN. На рис. 9 схематически изображены эти области.

BEN

ВЕР

Рис. 9. Области BEN и BEP

Для улучшения качества обучения словаря D2 мы обучаем его только на блоках, взятых из областей BEN, так как в этих областях находятся наиболее выраженные осцилляции. Такое ограничение значительно уменьшает размер обучающий выборки. Однако эффект ложного оконтуривания инвариантен к поворотам, поэтому вместе с каждым изображением в выборке можно рассматривать и его повернутые версии. Это позволяет искусственно расширять размер обучающей выборки. Нами рассматривались повороты на 90°, 180° и 270° во избежание ошибок интерполяции.

Из двух описанных выше словарей D1 и D2 составляется словарь D = [D1; D2], получаемый объединением множества элементарных сигналов этих словарей (столбцы соответствуют сигналам). Далее для входного изображения y строится разреженное представление c = [c1; c2] по объединенному словарю:

Тогда

Dc = D1c1 + D2c2.

Обозначим yi - искомое изображение без эффекта ложного оконтуривания, тогда y = y1 + y2, где y2 -изображение с чистым эффектом ложного оконтури-вания. При построении представления c алгоритм использует элементарные сигналы из обоих словарей, причем требование на минимальность количества использованных сигналов приводит к тому, что эти сигналы используются наиболее эффективно. Поэтому для восстановления yi, как правило, используются элементарные сигналы словаря Di, а для восстанов-

ления y2 - элементарные сигналы словаря D2. Исходя из этого положим y1 ~ D1c1.

Мы также обнаружили, что повышение резкости изображений с эффектом ложного оконтуривания при обучении словаря D2 позволяет увеличить эффективность метода. Для повышения резкости используется алгоритм деконволюции Винера-Ханта. Мы полагаем, что это связано с тем, что повышение резкости позволяет увеличить количество коэффициентов в представлениях для этого словаря и таким образом сбалансировать количество коэффициентов на этапе тестирования (это приводит к тому, что для словарей D1 и D2 нужна примерно одинаковая разреженность). Кроме этого, такой эффект может также достигаться за счет того, что повышение резкости усиливает эффект ложного оконтуривания на изображении, и на этапе обучения это позволяет алгоритму лучше настроиться на отделение эффекта ложного оконту-ривания от элементов обычных изображений.

Для тестирования эффективности метода мы использовали базу изображений [21]. На этих изображениях был смоделирован эффект ложного оконтуривания в соответствии с описанием в параграфе 2, также для соответствия реальному эффекту ложного оконтурива-ния на них был добавлен небольшой шум. Изображения были поделены на две группы - для обучения и для тестирования. Оценка эффективности метода производилась по трем различным метрикам (в сравнении изображений после восстановления и исходного изображения): PSNR, вычисленный глобально по всему изображению, PSNR в области BEP и PSNR в области BEN.

Тестирование проводилось при различных значениях d. Для сравнения использовались результаты метода JC и метода, основанного на полной вариации [9] (далее обозначим его TV - total variation). При сравнении глобального значения PSNR было обнаружено, при низких значениях d = 1,5, 2 метод JC дает наилучшее качество, а при более высоких значениях d = 2,5, 3 качество метода JC и предложенного метода близки (результаты в сравнении с методом TV аналогичны [14]). В табл. 1 приведено сравнение значений PSNR в области BEN, а в табл. 2 - сравнение значений PSNR в области BEP.

Табл. 1. Сравнение метода TV, метода JC и предложенного

метода в терминах метрики PSNR в области BEN, жирным выделен наилучший результат в строке

d TV JC Предложенный

1,5 35,79 36,16 35,62

2 34,5 34,24 34,61

2,5 33,62 33,05 33,65

3 32,64 31,36 32,78

Исходя из полученных результатов можно сделать следующие выводы. Метод JC показывает хорошие результаты по глобальному значению PSNR для всех значений d. Однако в областях BEN и BEP его результаты хуже, чем результаты метода TV и предложенного метода. Это связано с тем, что метод TV в основном ориентирован на работу с текстурами, ко-

торые не обязательно расположены вблизи контуров. Предложенный метод показывает хорошие результаты по глобальному значению PSNR для высоких значений d, а также превосходит методы TV и JC по значению PSNR в областях BEN и BEP.

Табл. 2. Сравнение метода TV, метода JC и предложенного метода в терминах метрики PSNR в области BEP, жирным выделен наилучший результат в строке

d TV JC Предложенный

1,5 32,29 32,27 31,45

2 29,12 29,04 29,26

2,5 26,92 26,85 27,06

3 25,36 25,2 25,43

Мы полагаем, тот факт, что предложенный метод хорошо работает при больших значениях d, связан с тем, что, во-первых, он работает с блоками изображений большего размера (для метода 1С это было невозможно из-за высокой вычислительной сложности), а ширина осцилляций и области, где эффект ложного оконтуривания заметен, растет с увеличением значения d. Во-вторых, эффект, описанный в параграфе 2, также сильнее выражен при более высоких значениях d.

На рис. 10 приведен фрагмент изображения с эффектом ложного оконтуривания для d = 2,5. На рис. 11 приведен аналогичный фрагмент изображения после подавления эффекта ложного оконтуривания методом 1С, а на рис. 12 - с использованием предложенного метода. Видно, что в некоторых областях вблизи границ новый метод лучше устраняет арте-фактные осцилляции.

Рис. 10. Изображение с эффектом ложного оконтуривания ^ = 2,5) для применения алгоритма подавления

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

V.

•II *

1

Рис. 11. Изображение после подавления эффекта ложного оконтуривания методом ЗС

Щ

г.

ем

JHLanIIM1

Рис. 12. Изображение после подавления эффекта ложного оконтуривания предложенным методом

Для входного изображения сначала определяется степень размытия контуров а на изображении [1]. В работе [8] было показано, что степень размытия контуров а линейно зависит от силы ложного оконтури-вания а. Для этого для набора контуров с различными значениями а находилось приближение этого контура размытым контуром, дающее наименьшую ошибку, и было показано, что зависимость силы размытия о от силы эффекта ложного оконтуривания а хорошо приближается формулой о = 0,336ё. Таким образом, после получения силы размытия а можно вычислить силу эффекта ложного оконтуривания как ё = о / 0,336. С помощью оцененных параметров далее выбирается наиболее подходящий словарь, и с его помощью производится подавление эффекта ложного оконтуривания.

Заключение

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

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

Благодарности

Работа выполнена при поддержке гранта Российского научного фонда, проект № 14-11-00308.

Для выполнения численных экспериментов в работе использовались библиотеки SciPy [22], Mat-plotlib [23] и Scikit-learn [24] для языка Python.

Литература

1. Nasonov, A.V. Edge quality metrics for image enhancement / A.V. Nasonov, A.S. Krylov // Pattern Recognition and Image Analysis - 2012. - Vol. 22(2). - P. 346-353. -DOI: 10.1134/S1054661812020113.

2. Koh, C.C. Annoyance of individual artifacts in MPEG-2 compressed video and their relation to overall annoyance / C.C. Koh, S.K. Mitra, J.M. Foley, I. Heynderickx // Proceedings of SPIE. - 2005. - Vol. 5666. - P. 595-606. -DOI: 10.1117/12.587423.

3. Liu, H. A perceptually relevant approach to ringing region detection / H. Liu, N. Klomp, I. Heynderickx // IEEE Transactions on Image Processing. - 2010. - Vol. 19(6). -P. 1414-1426. - DOI: 10.1109/TIP.2010.2041406.

4. Marziliano, P. Perceptual blur and ringing metrics: application to JPEG2000 / P. Marziliano, F. Dufaux, S. Winkler, T. Ebrahimi // Signal Processing: Image Communication. - 2005. - Vol. 19. - P. 163-172. - DOI: 10.1016/j.image.2003.08.003.

5. Ghang, H. Reducing artifacts in JPEG decompression via a learned dictionary / H. Chang, M.K. Ng, T. Zeng // IEEE Transactions on Signal Processing. - 2014. - Vol. 62(3). -P. 718-728. - DOI: 10.1109/TSP.2013.2290508.

6. Shen, M.-Y. Review of postprocessing techniques for compression artifact removal / M.-Y. Shen, C.-C. Jay Kuo // Journal of Visual Communication and Image Representation. -1998. - Vol. 9(1). - P. 2-14. - DOI: 10.1006/jvci.1997.0378.

7. Mosleh, A. Image deconvolution ringing artifact detection and removal via psf frequency analysis / А. Mosleh, J.M.P. Langlois, P. Green // Computer Vision - ECCV 2014, Series: Lecture Notes in Computer Science. - 2014.

Vol. 8692. - P. 247-262. 10593-2 17.

DOI: 10.1007/978-3-319-

8. Umnov, A. Sparse method for ringing artifact detection / A. Umnov, A. Nasonov, A. Krylov, D. Yong // Proceedings of 12th International Conference on Signal Processing. -2014. - P. 662-667. - DOI: 10.1109/ICOSP.2014.7015086.

9. Nasonov, A. Adaptive image deringing / A. Nasonov, A. Krylov // Proceedings of GraphiCon 2009. - 2009. -P. 151-154.

10. Krylov, A. Variational image deringing using varying reg-ularization parameter / A. Krylov, I. Sitdikov // Pattern Recognition and Image Analysis. - 2015. - Vol. 25(1). -P. 96-100. - DOI: 10.1134/S1054661815010186.

11. Kellner, E. Gibbs-ringing artifact removal based on local subvoxel-shifts / E. Kellner, B. Dhital, V. Kiselev, M. Reisert // Magnetic Resonance in Medicine. - 2016. -Vol. 76(5). - P. 1574-1581. - DOI: 10.1002/mrm.26054.

12. Mallat, S. A wavelet tour of signal processing: the sparse way / S. Mallat. - Philadelphia: Elseveir, 2009. - 805 p. -ISBN: 978-0-12-374370-1.

13. Rudin, L. Nonlinear total variation based noise removal algorithms / L. Rudin, S. Osher, E. Fatemi // Physica D: Nonlinear Phenomena. - 1992. - Vol. 60(1-4). - P. 259268. - DOI: 0.1016/0167-2789(92)90242-F.

14. Umnov, A. Ringing artifact suppression using sparse representation / A. Umnov, A. Krylov, A. Nasonov // Proceedings of the 16th International Conference on Advanced Concepts for Intelligent Vision Systems. - 2015. - P. 3545. - DOI: 10.1007/978-3-319-25903-1_4.

15. Elad, M. Sparse and redundant representations / M. Elad. - New York: Springer, 2010. - 376 p. - ISBN: 9781441970107.

16. Elad, M. On the role of the sparse and redundant representations in image processing / M. Elad, M.A.T. Figueiredo,

Y. Ma // Proceedings of the IEEE. - 2010. - Vol. 98(6). -P. 972-982. - DOI: 10.1109/JPROC.2009.2037655.

17. Кольцов, П.П. Оценка размытия изображения / П.П. Кольцов // Компьютерная оптика. - 2011. - Т. 35, № 1. - С. 95-102.

18. Orieux, F. Bayesian estimation of regularization and point spread function parameters for Wiener-Hunt deconvolution / F. Orieux, J.F. Giovannelli, T. Rodet // Journal of the Optical Society of America A. - 2010. - Vol. 27(7). -P. 1593-1607. - DOI: 10.1364/J0SAA.27.001593.

19. Donoho, D.L. Stable recovery of sparse overcomplete representations in the presence of noise / D.L. Donoho, M. Elad, V.N. Temlyakov // IEEE Transactions on Information Theory. - 2006. - Vol. 52(1). - P. 6-18. - DOI: 10.1109/TIT.2005.860430.

20. Крылов, А. С. Влияние эффекта Гиббса на взаимную согласованность в методе разреженных представлений для изображений / А.С. Крылов, А.В. Умнов // Вестник МГУ. Серия 15: Вычислительная математика и кибернетика. - 2016. - Т. 4. - С. 12-17.

21. База данных изображений с эффектом Гиббса и ложным оконтуриванием [Электронный ресурс]. - URL: http://imaging.cs.msu.ru/research/ringing/database (дата обращения 21.09.2016).

22. SciPy: Open Source scientific tools for Python [Electronical Resource] / E. Jones, E. Oliphant, P. Peterson [et al.]. -URL: http://scipy.org/ (дата обращения 21.09.2016).

23. Hunter, J. Matplotlib: A 2D graphics environment / J. Hunter // Computing in Science and Engineering. - 2007. - Vol. 9(3). - P. 90-95. - DOI: 10.1109/MCSE.2007.55.

24. Pedregosa, F. Scikit-learn: Machine learning in Python / F. Pedregosa [et al.] // Journal of Machine Learning Research. - 2011. - Vol. 12. - P. 2825-2830.

Сведения об авторах

Умнов Алексей Витальевич, 1990 года рождения, окончил Московский государственный университет имени М.В. Ломоносова по специальности «Математика». Работает младшим научным сотрудником в Национальном исследовательском университете «Высшая школа экономики». Область научных интересов: обработка изображений, разреженные представления, обучение представлений. E-mail: aumnov@hse.ru .

Крылов Андрей Серджевич, 1956 года рождения, доктор физико-математических наук, профессор, заведующий лабораторией математических методов обработки изображений кафедры математической физики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова. Область научных интересов: прикладная математика, математические методы обработки изображений. E-mail: kryl@cs.msu.ru .

ГРНТИ: 28.23.15

Поступила в редакцию 29 июня 2016 г. Окончательный вариант - 30 октября 2016 г.

RESEARCH OF SPARSE REPRESENTATION METHOD FOR RINGING SUPPRESSION

A. V. Umnov 1, A.S. Krylov 2

1 National Research University Higher School of Economics, Moscow, Russia,

2 Lomonosov Moscow State University, Moscow, Russia

Abstract

In this paper we suggest an algorithm for ringing suppression based on a sparse representation method. As one of its steps, the suggested method includes image deblurring based on the Wiener-Hunt deconvolution algorithm. The ringing suppression algorithm uses the signals' mutual coherence and sparsities analysis when dealing with the ringing effect based on the sparse representation method. We also analyze the mutual coherence and sparsities for blurred images and images with white Gaussian noise.

Keywords: ringing effect, sparse representations, mutual coherence.

Citation'. Umnov AV, Krylov AS. Research of sparse representation method for ringing suppression. Computer Optics 2016; 40(6). 895-903. DOI. 10.18287/2412-6179-2016-40-6-895-903.

Acknowledgements: The work was partially funded by the Russian Science Foundation (RSF), grant No. 14-11-00308. For numerical experiments, the Python libraries SciPy [22], Matplotlib [23] and Scikit-learn [24] were used.

References

[1] Nasonov AV, Krylov AS. Edge quality metrics for image enhancement. Pattern Recognition and Image Analysis 2012; 22(2): 346-353. DOI: 10.1134/S1054661812020113.

[2] Koh CC, Mitra SK, Foley JM, Heynderickx I. Annoyance of individual artifacts in MPEG-2 compressed video and their relation to overall annoyance. Proc SPIE 2005; 5666: 595606. DOI: 10.1117/12.587423.

[3] Liu H, Klomp N, Heynderickx I. A perceptually relevant approach to ringing region detection. IEEE Transactions on Image Processing 2010; 19(6): 1414-1426. DOI: 10.1109/TIP.2010.2041406.

[4] Marziliano P, Dufaux S, Winkler T, Ebrahimi T. Perceptual blur and ringing metrics: application to JPEG2000. Signal Processing: Image Communication 2005; 19: 163-172. DOI: 10.1016/j.image.2003.08.003.

[5] Chang H, Ng MK, Zeng T. Reducing artifacts in JPEG decompression via a learned dictionary. IEEE Transactions on Signal Processing 2014; 62(3): 718-728. DOI: 10.1109/TSP.2013.2290508.

[6] Shen M-Y, Jay Kuo CC. Review of Postprocessing Techniques for Compression Artifact Removal. Journal of Visual Communication and Image Representation 1998; 9(1): 2-14. DOI: 10.1006/jvci.1997.0378.

[7] Mosleh A, Langlois JMP, Green P. Image deconvolution ringing artifact detection and removal via psf frequency analysis. ECCV 2014: Lecture Notes in Computer Science 2014; 8692: 247-262. DOI: 10.1007/978-3-319-10593-2_17.

[8] Umnov A, Nasonov A, Krylov A, Yong D. Sparse method for ringing artifact detection. ICOSP 2014: 662-667. DOI: 10.1109/ICOSP.2014.7015086.

[9] Nasonov A, Krylov A. Adaptive image deringing. Proceedings of GraphiCon 2009: 151-154.

[10] Krylov A, Sitdikov I. Variational image deringing using varying regularization parameter. Pattern Recognition and Image Analysis 2015; 25(1): 96-100. DOI: 10.1134/S1054661815010186.

[11] Kellner E, Dhital B, Kiselev V, Reisert M. Gibbs-ringing artifact removal based on local subvoxel-shifts. Magnetic

resonance in medicine 2016; 76(5): 1574-1581. DOI: 10.1002/mrm.26054.

[12] Mallat S. A wavelet tour of signal processing: the sparse way. Philadelphia: Elseveir; 2009. ISBN: 978-0-12374370-1.

[13] Rudin L, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena 1992; 60(1-4): 259-268. DOI: 0.1016/0167-2789(92)90242-F.

[14] Umnov A, Krylov A, Nasonov A. Ringing artifact suppression using sparse representation. ACIVS 2015: 35-45. DOI: 10.1007/978-3-319-25903-1_4.

[15] Elad M. Sparse and redundant representations. New York: Springer; 2010. ISBN: 978-1441970107.

[16] Elad M, Figueiredo MAT, Ma Y. On the role of the sparse and redundant representations in image processing. Proc IEEE 2010; 98(6): 972-982. DOI: 10.1109/JPROC.2009.2037655.

[17] Koltsov PP. Image blur estimation. Computer Optics 2011; 35(1): 95-102.

[18] Orieux F, Giovannelli JF, Rodet T. Bayesian estimation of regularization and point spread function parameters for Wiener-Hunt deconvolution. JOSA A 2010; 27(7): 15931607. DOI: 10.1364/JOSAA.27.001593.

[19] Donoho DL, Elad M, Temlyakov VN. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory 2006; 52(1): 6-18. DOI: 10.1109/TIT.2005.860430.

[20] Krylov AS, Umnov AV. Influence of Gibbs phenomenon on the mutual coherence in sparse representations [In Russian]. Moscow University Bulletin. Series 15: Computational Mathematics and Cybernetics 2016; 4: 12-17.

[21] Ringing analysis database. Source: (http://ima-ging.cs.msu.ru/research/ringing/database).

[22] Jones E, Oliphant E, Peterson P, et al. SciPy: Open Source scientific tools for Python. Source: (http://scipy.org).

[23] Hunter J. Matplotlib: A 2D graphics environment. Computing in Science and Engineering 2007; 9(3): 90-95. DOI: 10.1109/MCSE.2007.55.

[24] Pedregosa F, et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 2011; 12: 2825-2830.

Authors' information

Alexey Vitalievich Umnov (b. 1990), received a specialist degree in mathematics in Lomonosov Moscow State University. Currently he works as a junior research fellow in National Research University Higher School of Economics. Research interests: image processing, sparse representations, representation learning. E-mail: aumnov@hse.ru .

Andrey Serdjevich Krylov (b. 1956) doctor of sciences, professor, head of Mathematical Methods of Image Processing laboratory, chair of Mathematical Physics Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University. Research interests: applied mathematics, mathematical methods of image processing. E-mail: kryl@cs.msu.ru .

Received June 29, 2016. The final version - October 30, 2016.