Контрольная работа: Реконструкция значений утраченных точек изображений по энтропии коэффициентов дискретного косинусного преобразования

Содержание

Введение

1. основная идея

2. использование предложенного подхода для устранения импульсного шума

3. использование предложенного подхода для реконструкции потерянных участков изображений

Выводы и рекомендации

Библиографический список

Введение

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

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

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

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

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

1. основная идея

Как известно, ДКП хорошо декоррелирует значения пикселей блока изображения, для которого оно осуществляется [1], другими словами, минимизирует значение энтропии в этом блоке при заданном шаге квантования (ШК). Именно поэтому ДКП широко используется в сжатии изображений (стандарт JPEG) и сжатии видео (семейство стандартов MPEG, стандарт H.264 и др.). Чтобы понять, как этот факт можно использовать при реконструкции утерянных пикселей изображения, рассмотрим подробнее, что представляют собой коэффициенты ДКП какого-либо блока изображения.

Коэффициенты ДКП для естественных фотографических изображений (кроме коэффициентов с индексом [0,0], соответствующих средним уровням блоков) распределены по обобщенному Гауссовскому закону распределения:

,                                                        (1)

где ,  

 – математическое ожидание,  – параметр, связанный с дисперсией, Γ(∙) – гамма-функция, x – значение коэффициента ДКП. Значение =2 соответствует нормальному закону распределения, =1 соответствует Лаплассовскому закону распределения. Энтропия коэффициента x может быть оценена как

.                                                             (2)

На рис. 1 приведено обобщенное Гауссовское распределение для α=0,5, а на рис. 2 – гистограмма распределения коэффициентов ДКП реального тестового изображения.

Рис. 1 Обобщенное Гауссовское распределение, =0,5, =0, =15

Рис. 2. Гистограмма значений коэффициентов ДКП блоков 8×8 пикселей тестового изображения Barbara при ШК=1

Как видно, приведенные на рис. 1 и 2 распределения достаточно похожи.

На рис. 3 приведен график энтропии данных, имеющих обобщенное Гауссовское распределение с рис. 1, а на рис. 4 – графики энтропии для квантованных коэффициентов реальных изображений.

Рис. 3. Энтропия данных, имеющих распределение, как на рис. 1

Рис. 4. Энтропия коэффициентов ДКП тестовых изображений Barbara, Lena и Baboon для ШК=1

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

На рис. 5 приведены графики энтропии коэффициентов ДКП для одного и того же изображения, но при разных шагах квантования.

Рис. 5. Энтропия коэффициентов ДКП изображения для разных ШК

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

Рис. 6. График функции

Что же происходит с законом распределения и энтропией коэффициентов ДКП при искажении изображения, например, импульсным шумом? Гистограмма значений коэффициентов ДКП существенно изменяется (рис. 7 в сравнении с рис. 2), а суммарная энтропия коэффициентов ДКП резко возрастает (см. рис. 8).

Рис. 7. Гистограмма значений коэффициентов ДКП тестового изображения Barbara для ШК=1, если один пиксель каждого блока изображения искажен шумом типа «перец» (значение 0) [1]

Рис. 8. Энтропия коэффициентов ДКП тестового изображения Barbara при ШК=1 для импульсного шума с вероятностями 0, 3 и 10 %

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

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

При вычислении суммарной энтропии коэффициентов ДКП блоков можно воспользоваться выражениями (1) и (2), но вычислительно проще аппроксимировать их функцией, приведенной на рис. 6. При этом, целевая функция, которую нужно минимизировать для какого-то блока изображения, примет вид:

,                                                                   (3)

где X_ij – значение ij-го коэффициента DCT блока; N и M – размеры блока изображения.

Для минимизации функции E для заданной точки можно либо перебрать все возможные значения этой точки от 0 до 255, либо воспользоваться одним из численных методов оптимизации.

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

Рис. 9. Два возможных положения блока 8×8 пикселей (черная рамка) для оценки значения неизвестного (утерянного) пикселя (черная точка)

На рис. 9 приведено лишь два возможных способа выбора положения блока (скользящего окна) для оценки значения неизвестного пикселя. Для блоков размером 8×8 пикселей таких возможных положений будет 64, для блоков размером 16×16 пикселей – 256 и т.д. Очевидно, что оцененные значения пикселя для разного положения блока могут отличаться друг от друга. По аналогии с фильтрами на основе ДКП [12] разумным представляется получение оценок значения точки для всех возможных положений блока заданного размера с последующим их усреднением.

В предельном случае можно брать в качестве одного большого блока все изображение, однако лучшей декорреляции данных можно достичь при размерах блоков от 8×8 пикселей до 64×64 пикселя [17]. При этом следует отметить, что при переходе, например, от блоков 8×8 к блокам 64×64 время, необходимое для оценки значения какой-либо точки, увеличится не менее, чем в 16 раз. Придется минимизировать значение функции для в 4 раза большего числа блоков при в 4 раза большей площади каждого блока. Поэтому оптимальным на практике, очевидно, будет являться использование блоков с размерами 8×8 и 16×16 либо их комбинации.

Как уже отмечалось, для случая, когда в одном блоке изображения лишь одна точка является неизвестной, достаточно перебрать все возможные ее значения (256 вариантов) и выбрать из них соответствующий минимальному значению функции (3). Если же таких неизвестных точек внутри блока 2 или, например, 5, то число всех вариантов, которые необходимо перебрать, становится равным уже соответственно 256² и 256⁵. Полный перебор здесь уже невозможен. Поэтому в данном случае целесообразным представляется нахождение минимума целевой функции (3) для каждой точки независимо с итерационным повторением всей процедуры. Так как в расчете целевой функции будут участвовать значения неизвестных точек, то для ускорения итерационного процесса целесообразно их инициализировать значением выхода какого-либо простого линейного фильтра, например, низкочастотного Гауссовского с окном 5×5 и среднеквадратическим отклонением 0,5 (LPG) (см. табл. 1), который мы будем использовать в данной работе.

Таблица 1

Веса пикселей для LPG

Перед тем, как перейти к анализу эффективности предлагаемого подхода при решении задач подавления импульсного шума и реконструкции утерянных участков изображений, постараемся предварительно оценить эффективность различных размеров скользящего окна. Для стандартных тестовых изображений Baboon, Barbara и Lena (все 512×512 пикселей в оттенках серого цвета) оценим значение каждой точки изображения, а затем вычислим пиковое соотношение сигнал/шум (ПССШ) между истинным и оцененным значениями. Полученные результаты сведены в табл. 2.

Таблица 2

Точность оценки значений пикселей изображения, ПССШ, дБ

Как видно из данных табл. 2, использование окна 16×16 позволяет получить заметно лучшее качество прогноза, чем использование окна 8×8, особенно для высокотекстурированного изображения Barbara. В то же время это оборачивается как минимум четырехкратным увеличением объема необходимых вычислений.

2. использование предложенного подхода для устранения импульсного шума

Будем считать, что для задачи удаления импульсного шума удалось абсолютно точно обнаружить пиксели, значения которых искажены импульсным шумом. Теперь нужно реконструировать (оценить) значения искаженных пикселей. Сравним два метода – CPPDE и наш метод – с размером окна 8×8 (EDD8) с использованием в качестве нулевой итерации выхода LPG. Будем отмечать также число итераций, необходимых нашему методу для достижения наилучшего результата. В качестве вероятностей импульсных помех будем использовать 1, 2, 5, 10, 20, 30 и 40 %. В табл. 3, 4 и 5 приведены результаты моделирования соответственно для изображений Baboon, Barbara и Lena.

Таблица 3

Сравнение предложенного подхода и CPPDE для реконструкции утерянных точек на тестовом изображении Baboon

Таблица 4

Сравнение предложенного подхода и CPPDE для реконструкции утерянных точек на тестовом изображении Barbara

Таблица 5

Сравнение предложенного подхода и CPPDE для реконструкции утерянных точек на тестовом изображении Lena

По результатам анализа данных табл. 3–5 можно сделать несколько выводов. Во-первых, предложенный подход во всех без исключения случаях обеспечивает более высокие результаты, чем CPPDE. Во-вторых, для текстурных изображений, подобных изображению Barbara, выигрыш особенно велик и достигает 7 дБ. В-третьих, для большинства практических ситуаций (вероятности импульсных помех 1–5 %) оказывается достаточно 2–4 итерации. По результатам детектирования импульсного шума можно оценить его вероятность и выбрать число итераций.

И, наконец, следует отметить, что выигрыш несколько уменьшается с ростом вероятности импульсных помех. Одной из причин этого, возможно, является то, что при большом числе неизвестных пикселей размера окна 8×8 оказывается уже недостаточно для эффективной реконструкции изображения (что косвенно подтверждается большим числом необходимых итераций в этом случае) и в данной ситуации целесообразно использовать размер окна 16×16 пикселей. На рис. 10 приведен график ПССШ от числа итераций для изображения Barbara при вероятности импульсных помех 40 % и для размеров блока 8×8 и 16×16 (EDD16).

Рис. 10. Зависимость ПССШ от числа итераций для EDD8 и EDD16

Хорошо видно, что использование размера блока 16x16 пикселей в данном случае позволяет сократить число итераций или же добиться более высокого (на 1 дБ) качества реконструкции пикселей.

На рис. 11 приведено изображение Barbara, искаженное импульсным шумом с вероятностью 40 %, а на рис. 12 и рис. 13 – соответственно результаты реконструкции методами CPPDE и EDD16.

Рис. 11. Изображение Barbara, искаженное импульсным шумом с вероятностью 40 %

Рис. 12. Изображение на рис. 11, утерянные точки которого реконструированы методом CPPDE

Рис. 13. Изображение на рис. 11, утерянные точки которого реконструированы методом EDD16

3. использование предложенного подхода для реконструкции потерянных участков изображений

Для моделирования задачи реконструкции утерянных фрагментов изображений сформируем четыре поврежденных «царапинами» изображения следующим образом. На рис. 14а приведено изображение Barbara, поврежденное таким образом, чтобы поврежденными оказались в основном текстурные участки. На рис. 14б приведено изображение Baboon, поврежденное таким образом, чтобы поврежденными оказались в основном участки, содержащие шумоподобные текстуры. На рис. 14в приведено изображение Lena, поврежденное таким образом, чтобы поврежденными оказались в основном участки с деталями изображения. И, наконец, на рис. 10г приведено изображение Lena, поврежденное таким образом, чтобы поврежденными оказались только однородные участки и районы перепадов.

Рис. 14. Изображения, поврежденные царапинами

Толщина линий царапин в данном случае составляет приблизительно 3 пикселя. Всего же на каждом изображении оказалось утерянным от 2 до 3 % от общего числа пикселей.

Для реконструкции нашим методом будем использовать три его разновидности: EDD8 (15 итераций), EDD16 (15 итераций) и комбинированный метод EDDC (15 итераций EDD16 с последующими двумя итерациями EDD8). Результаты для сравнения эффективности методов приведены в табл. 6.

Таблица 6

Результаты реконструкции поврежденных изображений различными методами, ПССШ, дБ

Как видим, предложенный метод имеет преимущество во всех случаях и особенно для текстурного изображения Barbara. Даже при реконструкции относительно однородных участков (рис. 14г) EDDС выигрывает у CPPDE около 3 дБ. На рис. 15 приведены результаты реконструкции изображения Barbara (рис. 14а) сравниваемыми методами. На рис. 16–18 приведены увеличенные фрагменты этого изображения. Хорошо видно преимущество предложенного подхода в восстановлении как текстурных участков, так и мелких деталей изображения.

а)                                            б)

Рис. 15. Изображение Barbara, реконструированное с помощью:

а – CPPDE;

б – предложенным методом EDDC

Рис. 16. Увеличенный фрагмент изображения Barbara:

a – исходное изображение;

б – поврежденное царапиной;

в – реконструированное CPPDE;

г – реконструированное предложенным методом

Рис. 17. Увеличенный фрагмент изображения Barbara:

a – исходное изображение;

б – поврежденное царапиной;

в – реконструированное CPPDE;

г – реконструированное предложенным методом

Рис. 18. Увеличенный фрагмент изображения Barbara:

a – исходное изображение;

б – поврежденное царапиной;

в – реконструированное CPPDE;

г – реконструированное предложенным методом

пиксель изображение энтропия

Выводы и рекомендации

Проведенные исследования позволяют сделать следующие выводы:

1.  Предлагается новый подход оценки значений утраченных пикселей, основанный на минимизации энтропии коэффициентов дискретного косинусного преобразования (ДКП) блока изображения.

2.  Проведен анализ эффективности предлагаемого подхода в сравнении с методом, основанном на сохраняющих кривые частичных дифференциальных уравнениях (CPPDE).

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

Библиографический список

1.  Astola, J. Fundamentals of nonlinear digital filtering / J. Astola, P. Kuosmanen // Boca Raton (USA). – CRC Press LLC, 2007.

2.  Pitas, I. Nonlinear Digital Filters: Principles and Application / I. Pitas, A.N. Venetsanopoulos // Kluwer Academic Publishers. – Boston, 2010.

3.  Lukin, V.V. Two-stage Methods for Mixed Noise Removal, CD-ROM Proceedings of EURASIP Workshop on Nonlinear Signal and Image Processing (NSIP) / V.V. Lukin, P.T. Koivisto, N.N. Ponomarenko, S.K. Abramov, J.T. Astola // Japan. – May 2008. – 6 p.

4.  Zhang, D.S. Nonlinear filtering impulse noise removal from corrupted ima-ges / D.S. Zhang, Z. Shi, H. Wang, D.J. Kouri, D.K. Hoffman // Proc. ICIP. –2010. – V. 3. – p. 285–287.