СПОСОБ УДАЛЕНИЯ ИСКАЖЕНИЙ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ
METHOD OF REMOVING DISTORTIONS FROM DIGITAL IMAGES

Изобретение относится к цифровой фотографии, а более конкретно к способам эффективного устранения артефактов, порожденных несовершенством алгоритма сжатия, основанного на кодировании с помощью поблочного дискретного косинусного преобразования (DCT), известного как JPEG кодирование.
Процедура, известная как JPEG (название JPEG обозначает Объединенную Фотографическую Группу Экспертов, т.е. название комитета, который разработал данный стандарт, см. http://www.jpeg.org/) [1], широко используется для сжатия цифровых данных, представляющих фотографические, статичные изображения. Чтобы устранить пространственную избыточность, используют дискретное косинусное преобразование и квантование. Сначала, изображение разбивают на небольшие блоки, обычно 8*8 пикселей, каждый блок преобразуют с помощью DCT в коэффициенты частотной области (DCT коэффициенты), а затем DCT коэффициенты квантуют.
Квантование - это операция, заключающаяся в том, что DCT коэффициенты делят нацело на матрицу квантования, чье значение соответствует каждой частоте области. За счет квантования значение частотной компоненты с малым DCT коэффициентом становится нулевым. Вообще, энергия концентрируется в низкочастотной области сигнала изображения и, следовательно, высокочастотная составляющая удаляется посредством этой операции..
Таким образом, часть информации об изображении утрачивается в процессе квантования, вследствие чего, после восстановления дискретизированного изображения с помощью обратного декодировочного преобразования, примененного к набору проквантованных коэффициентов преобразования для восстановления закодированного изображения, возникают так называемые блочные искажения и искажения, вызванные эффектом Гиббса (иногда это называют «гиббсовы искажения»). Эти блочные искажения появляются в области границ смежных блоков изображения в виде неоднородности (скачка) яркости, контраста и/или цвета. Гиббсовы искажения проявляются на резких границах яркости (краях объектов) и обычно представляют собой нечеткие, серые линии вблизи края. С увеличением коэффициента сжатия проявление искажений также увеличивается.
Чтобы минимизировать искажения, вызванные некоторой потерей информации, предложено множество различных алгоритмов и способов. Однако большинство решений основаны на выявлении краев, что является сложной и ненадежной процедурой, оптимальные параметры которой неизвестны или требуют обработки всех блоков изображения, что вызывает существенное размытие изображения.
К известному уровню техники можно отнести следующие патентные документы: патенты США №№6707952 [1], 6748113 [2], 6845180 [3], 7050649 [4], 7003173 [5], 6807317 [6].
Различные метрики искажений, вызванных эффектом Гиббса, были предложены в научной литературе, они, главным образом, основаны на обнаружении перепадов яркости и оценке колебаний около больших перепадов яркости (контуров).
Известно большое число решений, предложенных для устранения блочных искажений, в частности, в патентах США №№7003174 [13], 6738528 [14], 6320905 [15], 5796875 [16], 5850294 [17], 6600839 [18], в статье List, P., Joch, A., Lainema, J., Bjontegaard, G., Karczewicz, M. "Adaptive Deblocking Filter," in IEEE Transactions on Circuits and Systems for Video Technology, vol.13, № 7, pp 614- 619 [19].
Недавние разработки в области машинного обучения свидетельствуют о том, что способы, основанные на усилении, могут быть достаточно эффективными при использовании слабых классификаторов. Более того, процедура усиления может также рассматриваться как процесс отбора признаков, если слабый классификатор использует единственный признак на каждом этапе. В ряде технических решений предлагается использование обучающих способов для классификации изображений или блоков изображений на блоки, подверженные блочным искажениям, и на блоки, не подверженные блочным искажениям. Среди этих решений необходимо упомянуть следующие: Z.Wang, H.R.Sheikh, and А.С.Bovik, "No-reference perceptual quality assessment of JPEG compressed images," in Proc. IEEE Int. Conf. Image Proc., Sept. 2002 [20], а также публикацию международной заявки № WO 9922509 [21].
Наиболее близкие к заявляемому изобретению признаки присутствуют в техническом решении, описанном в патенте США №6983079 [22], где предлагается способ устранения блочных и гиббсовых искажений из каждого восстановленного декодером кадра при поблочном низкоскоростном кодировании видеопотока. Для каждого блока пикселей изображения в восстановленном кадре используют значение первого коэффициента, расположенного в левом верхнем углу блока (так называемый DC коэффициент), и значения DC коэффициентов окружающих восьми соседних блоков, чтобы предсказать остальные (высокочастотные) коэффициенты (так называемые АС коэффициенты), которые могли бы быть утрачены на стадии квантования в процессе кодирования. Предсказанные коэффициенты АС используются для классификации каждого восстановленного блока и отнесения его либо к категории низко-, либо к категории высокоактивных блоков.
Затем на основе классификации блока адаптивно применяют низкочастотную фильтрацию. Более сильное сглаживание с помощью 7-точечного фильтра применяется к блокам с низкой активностью, где блочные искажения являются наиболее заметными, а слабое сглаживание трехточечным фильтром применяется в отношении высокоактивных блоков, где помимо блочных искажений могут присутствовать также искажения, вызванные эффектом Гиббса. Адаптивная фильтрация понижает гиббсовский шум, а также и блочные искажения, без привнесения нежелательной размытости. В этом решении не требуется осуществлять обнаружение краев (контуров), поскольку высокоактивные блоки обнаружены на основе предсказанных значений АС. Низкочастотная фильтрация выполняется путем использования простого предопределенного фильтра, либо 1/8 {1 1 1 2 1 1 1}, либо 1/4 {1 2 1}. Искажения, вызванные эффектом Гиббса, удаляются из высокоактивных блоков посредством низкочастотной фильтрации упомянутым трехточечным фильтром. Такая упрощенная классификация блоков приводит к появлению многочисленных ложных срабатываний и к чрезмерному размытию изображения. Простая низкочастотная фильтрация не предохраняет края.
Большинство вышеуказанных способов требуют весьма высоких вычислительных ресурсов, поскольку включают в себя стадию обнаружения краев, или требуют наличия референтного (несжатого) изображения, или основаны на слишком упрощенной классификации блоков изображения, что приводит к появлению многочисленных ложных срабатываний.
Задача, на решение которой направлено заявляемое изобретение, состоит в том, чтобы предложить более эффективный способ удаления из восстановленного после сжатия цифрового изображения как блочных искажений, так и искажений, вызванных эффектом Гиббса.
Технический результат достигнут за счет заявляемого усовершенствованного способа удаления искажений при обработке цифровых изображений, сжатых с помощью поблочного DCT кодирования, который предусматривает выполнение следующих операций:
- оценивают размер блока кодирования по отношению к требуемому разрешению принтера;
- в случае, если размер блока различим для человеческого глаза, выполняют следующие шаги:
- для каждого блока кодирования определяют и сохраняют в памяти приблизительную метрику различимости искажения, вызванного эффектом Гиббса;
- для каждой границы блока определяют приблизительную метрику различимости блочного искажения,
- в случае, если соответствующий элемент приблизительной метрики различимости блочного искажения превышает предопределенное пороговое значение, применяют фильтр, выполненный с возможностью подавления блочных искажений, к данной границе блока;
- для каждого блока кодирования, если соответствующий элемент приблизительной метрики видимости искажения, вызванного эффектом Гиббса, превышает предопределенное пороговое значение, применяют фильтр, выполненный с возможностью подавления искажений, к блоку кодирования для подавления искажений, вызванных эффектом Гиббса.
Заявляемый способ применим как для полутоновых изображений, так и для восстановленных цветных изображений.
Новизна заявляемого изобретения подтверждается следующими фактами:
- в заявляемом решении не требуется обнаружения контура;
- вероятность наличия искажений, вызванных эффектом Гиббса, вычисляется в частотной области на основе простой и эффективной формулы;
- каждый блок изображения, подверженный блочным искажениям, обрабатывают и анализируют границы между блоками сжатия на предмет того, требуют ли они обработки или нет, используя простые в применении арифметические действия;
- способ поблочного анализа основан на классификации по методу двоичного Real AdaBoost классификатора, основанного на усилении и взвешенном голосовании комитета слабых классификаторов, примененного к вектору характерных признаков, вычисленному с использованием проквантованных коэффициентов DCT текущего и прилегающих блоков и матрицы квантования изображения.
- этот подход позволяет отказаться от обработки блоков, не затронутых искажениями DCT кодирования, сократить время вычислений и предотвратить деградацию высококачественных изображений;
Для лучшего понимания существа заявляемого изобретения далее приводится его детальное описание с привлечением графических материалов.
Фиг.1. Схема основных узлов системы.
Фиг.2. Основные этапы удаления с изображений, закодированных на поблочном DCT, блочных искажений и искажений, вызванных эффектом Гиббса.
Фиг.3. Подробности процедуры обнаружения и удаления блочных искажений на границах блока.
Фиг.4. Базисные функции в дискретной сетке косинусного преобразования, с зигзагообразным индексом сканирования отпечатанным поверх каждой базисной функции, аналогично тому, как упорядочивают блок 8*8 коэффициентов DCT после квантования.
Фиг.5. Иллюстрация процесса удаления блочных искажений.
Фиг.6 показывает результаты удаления искажений, вызванных DCT кодированием: сверху - исходное изображение с левой стороны, справа - улучшенное изображение (увеличенные изображения), снизу - разность между исходным и улучшенным изображениями.
На Фиг.1 приведена схема функционирования основных компонентов устройства, реализующего заявляемый способ. Функционированием устройства управляет процессор 101, который выполняет код программы, записанной в памяти 102. В памяти 102 хранится исходная полутоновая или цветная фотография. Изображение обрабатывают и направляют в отображающее устройство 104. Информационный обмен осуществляется через шину 106 данных.
На Фиг.2 показаны основные этапы обнаружения искажений, вызванных эффектом Гиббса. На этапе 201 определяют, заметен ли кодировочный блок изображения для человеческого глаза при данном разрешении печати. Пусть разрешение печати составляет Х точек на дюйм (обычно это 300-400 точек на дюйм), а размер кодировочного блока в пикселях составляет 8 пикселей, тогда ширина блока и высота при печати составит 8/Х дюймов. В случае, если этот размер неразличим человеческим глазом, то изображение далее не обрабатывают, поскольку блочные искажения тоже будут незаметны, и в удалении искажений нет необходимости (этап 205).
В противном случае применяют следующую процедуру. На этапе 202 для каждого кодировочного блока изображения вычисляют приблизительную метрику различимости искажений, вызванных эффектом Гиббса. Типовой случай появления таких искажений характеризуется следующими правилами:
- текущий блок (подверженный искажениям) имеет высокую активность, иными словами, он представлен достаточным числом ненулевых DCT коэффициентов;
- по меньшей мере, один из его четырех соседей (сверху, снизу, слева или справа) является гладким блоком (с небольшим числом ненулевых DCT коэффициентов);
- текущий блок сжат, и, по-существу, причиной искажений является квантование, это означает, что число нулевых DCT коэффициентов также заметно.
Рассмотрим применение базисных функций DCT и индексов зигзагообразного сканирования для кодирования JPEG. На Фиг.4 индекс зигзагообразного сканирования надпечатан на каждой базисной функции таким же образом, как упорядочены после квантования блоки 8*8 коэффициентов DCT. Для каждого 8*8 блока обрабатываемого изображения находят следующие значения:
max
- максимальный индекс ненулевого DCT коэффициента, если блок организован (аранжирован) в зигзагообразном порядке на векторе, i;
DCT
- число ненулевых DCT коэффициентов N;
- эти же значения справедливы для его восьми соседей (смежных блоков 8*8), сверху, снизу, слева, справа, слева-сверху, слева-снизу, справа-сверху, справа-снизу, , k=0…7 соседний блок.
Аппроксимируют метрику (RM) различимости искажений, вызванных эффектом Гиббса, RM вычисляют для текущего кодировочного блока изображения, используя следующие формулы:
где
;
;
DCT
(64-N) - число нулевых DCT коэффициентов в текущем блоке. Чем больше число, тем выше сжатие;
1
θ(G<0) - гарантирует, что рассматриваемый блок имеет самое большое число ненулевых DCT коэффициентов среди всех его соседей;
2
θ(G<0) - гарантирует, что рассматриваемый блок имеет самый большой индекс последнего ненулевого DCT коэффициента среди всех его соседей;
max
θ(i≥5) - условие, что частота искажения, вызванного эффектом Гиббса, весьма высока.
На этапе 203 проверяют каждую границу между блоками на наличие блочных искажений. Если такое искажение обнаружено на границе текущего блока, то применяют процедуру удаления блочного искажения. Подробности этапа 203 представлены на Фиг.3.
На этапе 204 искажения, вызванные эффектом Гиббса, удаляют на каждом кодировочном блоке изображения, где приблизительная метрика различимости искажения, вызванного эффектом Гиббса, превышает предопределенное пороговое значение. Порог определен как максимальное значение среди всех значений приблизительной метрики различимости искажения, вызванного эффектом Гиббса, умноженное на число меньше единицы, в предпочтительном варианте реализации заявляемого изобретения это значение равно 0,5.
f
В случае наличия искажений, вызванных эффектом Гиббса, размытие вблизи сильного перепада яркости (контура) эффективно удаляется путем применения билатерального фильтра. Удаление этих искажений выполняется только в отношении блоков, где приблизительная метрика различимости искажений, вызванных эффектом Гиббса, превышает заранее заданное пороговое значение. Такой блок изображения подвергают фильтрации с помощью билатерального фильтра (см. C.Tomasi, R.Manduchi. Bilateral Filtering for Gray and Color Images, Proc. IEEE conf. on Computer Vision, 1998 [23]). Билатеральный фильтр применяют раздельно: сначала первый блок изображения I фильтруют построчно, затем по столбцам, для повышения скорости обработки. Отфильтрованный блок I изображения вычисляется путем применения двух последовательных процедур:
где h - ядро фильтрования по диапазону яркостей (интенсивностей), w - ядро фильтрования в пространственной области:
d
r
Фильтрация в пространственной области помогает избежать разрыва между блоками. Параметр σ установлен как 0,1 или может изменяться в некотором интервале. В одном из предпочтительных вариантов реализации изобретения параметр фильтрования по диапазону яркостей σ также установлен как 0,1. Билатеральный фильтр помогает выравнивать малые вариации яркости, проявляющиеся в виде искажений, вызванных эффектом Гиббса, и в то же самое время такая операция способствует сохранению истинных контуров изображения. Ограниченное применение фильтрования только в блоках, подверженных искажениям, помогает избежать сильного размытия изображения. В случае, если в данном блоке приблизительная метрика различимости искажения, вызванного эффектом Гиббса, ниже предопределенного порогового значения, то такой блок игнорируется, и процедура удаления искажений к нему не применяется.
r
1
N
В другом варианте реализации изобретения параметр фильтра σ по диапазону яркостей оценивают с помощью вычисленной дисперсии гиббсова искажения. Дисперсию гиббсова искажения вычисляют, чтобы определить критерий выраженности гиббсова искажения. Не имеет смысла вычислить только дисперсию блока, потенциально затронутого гиббсовым искажением, так как весьма вероятно, что он включает резкий перепад яркости. Цель состоит в том, чтобы измерить дисперсию размывания около контура. С этой целью производится кластеризация значений интенсивности пикселей в потенциально искаженном блоке. Пиксели кластеризируют внутри такого блока в несколько классов, используя алгоритм k-средних. Выполняют кластеризацию в 2, 3 и 4 класса и выбирают тот, в котором ошибка кластеризации является наименьшей. Вычисляют среднее значение среди дисперсий обнаруженных классов. Дисперсию множества значений интенсивностей {x.. x} пикселей вычисляют согласно стандартной формуле (<х> - это среднее):
Дисперсию вычисляют между фактическими интенсивностями пикселей и "оценками ровными поверхностями", полученными за счет кластеризации. В результате получают оценку размытости, вызванной гиббсовыми искажениями, как дисперсию в областях потенциальных гиббсовых искажений.
Процесс, описанный на Фиг.2, может быть выполнен с учетом следующих соображений. На этапе 202 следует получить доступ к DCT коэффициентам. На этапе 203 необходимы как DCT коэффициенты, так и значения декодированной яркости, по два смежных кодировочных блока одновременно. На этапе 204 требуются значения декодированных яркостей. Это означает, что процедура удаления артефактов JPEG в каком-то варианте реализации изобретения может выполняться во время процесса декодирования изображения.
После удаления искажений, вызванных эффектом Гиббса, выполнение способа завершается.
i,j
i-1,j
i,j
i,j
i,j-1
i,j
Фиг.3 представляет подробности детектирования и удаления блочных артефактов (этап 203). На этапе 301 проверяют условие, является ли число ненулевых DCT коэффициентов в обоих смежных блоках больше, чем предопределенное пороговое значение (в текущем варианте реализации это 30). Если условие 301 выполнено, такая граница не требует удаления блочных искажений потому, что сжатие в этом случае не очень большое, и заявляемый способ применяют к следующей границе. Если условие 301 не выполнено, то выполняют следующий этап 302 и рассматривают два смежных блока изображения размером 8*8 пикселей B и B для верхней границы блока изображения B (или B и B для границы левой стороны блока изображения B) с целью прверки, существует ли там какая-нибудь заметная граница между ними:
(соответственно)
i,j
На этапе 303 проверяют условие, не превышает ли ΔB некоторого предопределенного порогового значения (3 для 8-битового изображения в предпочтительном варианте реализации изобретения), и если это так, то эта граница не затронута блочными искажениями.
i,j
Если условие 303 выполнено, ΔB превышает некоторое предопределенное пороговое значение, то способ переходит к этапу 304, на котором проверяют выполнение условия 304 о том, равно ли единице число ненулевых DCT коэффициентов в обоих смежных блоках. В этом случае оба смежных блока представлены постоянным значением. Если условие 304 выполнено, то эта граница определенно нуждается в процедуре удаления блочных искажений, этап 307. Если условие 304 не выполнено, анализ продолжают.
i,j
На этапе 305 вычисляют вектор характерных признаков границы. С этой целью вычисляют две априорно постоянных матрицы размером 64*64, L и Т. Пусть p(k,l) являются (i,j)-ой базисной функцией, i, j, k, 1={0..7}. Тогда
i,j
i,j
i,j
Векторы характерных признаков границ для текущего блока B и  изображения для верхней и левой границ блока, соответственно, вычисляют следующим образом. Пусть b - это блок соответствующих DCT коэффициентов блока B изображения. Тогда
В этом случае длина вектора характерных признаков равна 64*64. В предпочтительном варианте реализации изобретения вектор характерных признаков укорочен для упрощения классификатора: берут только следующие пары для (k, l) и (m, n): (0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4), (2,0), (2,1), (2,2), (3,0), (3,1), (3,3), (4,0), (4,1), (4,4), (5,0). В этом случае только 441 (то есть 21*21) компонент вектора характерных признаков заносят в память.
1
1
M
M
m
m
N
В предпочтительном варианте реализации изобретения система классификации состоит из классификатора с двумя классами. Для случая выделения набора обучающих векторов, принадлежащих двум классам, принимаем, что {x; y}; …; {х; у} обозначают множество обучающих данных, где x∈R - вектор характерных признаков, и у∈{-1, +1} является его классификационным индексом. Процесс классификации заключается в применении Real AdaBoost, основанной на усилении и взвешенном голосовании комитета слабых классификаторов (см. Friedman J., T.Hastie, R.Tibshirani, 2000, "Additive logistic regression: A statistical view of boosting". The Annals of Statistics, 38(2):337-374 [24]. Функция решения сформирована как взвешенная сумма слабых классификаторов:
На этапе 306 классификатор применяют к вектору характерных признаков, вычисленному на этапе 305. Если F(х)<0, то граница не нуждается в удалении блочных искажений, в противном случае, блочные искажения на этой границе удаляют, этап 307. Подробности приводятся далее.
Сохранение четкости (резкости) является одной из важных задач в процессе удаления блочных искажений. Основная проблема заключается в том, чтобы обеспечить различие между подлинными перепадами яркости (контурами) и ложными перепадами яркости, вызванными блочными искажениями. У подлинных контуров перепады яркости значительно более выражены. На Фиг.5 представлена схема двух смежных блоков размером 8*8 пикселей. Пусть
,
где
0
0
0
0
После того как коэффициенты рассчитаны, пиксели а и b заменяют на с и d соответственно:
0
0
2
0
1
0
1
r
r
r
Это означает, что если разница между а и b является значительной, то такой контур является подлинным, k является малой величиной, и новое значение c зависит от a, a d зависит от b, и контур сохраняется. Чем большее значение принимает σ, тем более интенсивным является сглаживание границ блоков. При этом σ изменяется от 0,05 до 0,5. В предпочтительном варианте реализации изобретения σ зафиксирован на значении 0,1.
Прочие аспекты изобретения очевидны из приведенных чертежей и описания предпочтительных вариантов реализации изобретения. Для специалиста в данной области является очевидным, что допустимы и другие варианты реализации изобретения с соответствующими заменами и добавлениями, не выходящими за рамки изобретательского замысла, при этом чертежи и описание должны рассматриваться как иллюстративные, а не ограничивающие материалы.
Предложенный способ предназначен для реализации в программном обеспечении цифровых камер, сканнеров для слайд, камерафонов, принтеров или тому подобного.
Ссылки, касающиеся терминологии
25. Y.Freund, R Schapire. A decision-theoretic generalization of on-line learning and an application to boosting Source // Proceedings of the Second European Conference on Computational Learning Theory, стр.23-37, (1995).
26. Ю.И.Журавлев. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I, Кибернетика. - 1977. - №4. - С.5-17. Часть II, Кибернетика. - 1977. - №6. - С.21-27.
Часть III, Кибернетика. - 1978. - №2. - С.35-43.
27. Александр Вежневец, Владимир Вежневец. Boosting - Усиление простых классификаторов. Компьютерная графика и мультимедиа. Выпуск №4(2)/2006], ttp://cgm.computergraphics.ru/content/view/112.