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

ОБРАБОТКА ИЗОБРАЖЕНИЙ, РАСПОЗНАВАНИЕ ОБРАЗОВ

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

при известных границах областей

Сергеев В.В., Денисова А.Ю.

Институт систем обработки изображений РАН

Аннотация

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

Ключевые слова: кусочно-постоянные изображения, ряд Неймана, итерационное восстановление, среднеквадратичное отклонение, дискретизация, интерполяция.

Введение

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

LANDSAT

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

На рис. 1 задача восстановления иллюстрируется на примере изображений участка земной поверхности, полученных со спутников Landsat (разрешение 32 метра) и Terra (разрешение 250 метров), с наложенными на них векторными границами.

Постановка задачи

Используемая в постановке задачи модель наблюдения показана на рис. 2. Пусть исходное изображение x(tbt2), заданное в непрерывных координатах tbt2, является кусочно-постоянным:

x (t1, t2) = a,,

i = 0..I -1, i * j

(tj,t2) e Di, Dt П Dj = 0,

U D, = D,

TERRA

Рис. 1. Схема задачи восстановления кусочно-постоянных изображений для спутниковых изображений: а) изображение среднего (32 м) разрешения, б) обрисовка векторных границ, в) сохранение векторных границ в ГИС, г) изображение низкого разрешения (250 м), д) интерполяция изображения г) до наземного шага дискретизации 32 м, е) наложение векторных границ на результаты интерполяции, ж) усреднение яркости внутри векторных границ

1=0

X Линейное XI Дискретизация Х2 Интерполяция Хз Усреднение по областям А4 X

Аг Аг Ч±/ А3

Рис. 2. Модель наблюдения

где а1 - значение яркости изображения в области D¡, I - число областей разбиения, D - область определения изображения.

Наблюдаемое дискретное изображение ха («1, п2) формируется под действием искажающей линейной инвариантной к сдвигу системы с импульсной характеристикой (ИХ) h (т1, т2) [2]

X t2) = 11 h(х,т2)х(t1 -х,^ -т2)dт1dт2

пространственной дискретизации искаженного изображения с шагом Т по координатам

,(«1, « ) = х1 t2 )|^ =„1Т

и добавления шума

хЛ

где Т - шаг дискретизации по координатам, («1,«2) -целочисленные индексы, V(«1,«2) - случайные искажения пикселов.

Процесс восстановления в самом очевидном варианте выражается в интерполировании искажённого изображения:

хз

« «2

где I t2) - интерполирующая функция, и приведении его к кусочно-постоянному виду путём усреднения по областям:

У (tl, t2 ) = а< =-(tl, t2 )е П

Л Х3

Л dTldT2

I = 0..1 -1.

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

Задача состоит в получении более точной оценки исходного изображения (1) при известном разбиении на области и наблюдаемом изображении (4).

Алгоритм

Если пренебречь шумовыми искажениями (4), то связь исходного изображения (1) и его оценки (6) можно представить в виде действия некоторого линейного оператора А (здесь и ниже запись аргументов для краткости опускаем):

у = Ах .

Известно, что если оператор А имеет обратный оператор А-1, линейный оператор J - А (где 3 - то-

ждественный оператор) является ограниченным и выполняется условие

то существует единственное разложение обратного оператора А-1 в ряд Неймана [3]:

А-1 = 3 +Х

На этом факте основана итерационная схема восстановления Ван-Циттерта. Применяя вместо обратного оператора разложение (9) и выполняя последовательное суммирование, получаем приближения ис-

М .

комого решения х

(0) = У, х(и) = у + (3 - А)х(и-1), « > 1.

В рассматриваемой нами задаче оператор искажений представляет собой композицию операторов сглаживания А1 (формула (2)) , дискретизации А2 (формула (3)), интерполяции А3 (формула (5)) и усреднения внутри границ областей А4 (формула (6)):

А = А4 А3 А2 А1.

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

Для сходимости ряда (9) необходимо, чтобы выполнялось условие (8). Условие (8) легко проверяется (а при необходимости и обеспечивается путём несложной модификации итерационной процедуры, см., например [3]) только для А1. Однако несложно доказать, что операторы А2, А3, А4 являются положительными и нерасширяющими:

1< 1, I = 2,3,4

и что этого достаточно, чтобы при выполнении условия (8) отдельно для сжимающего оператора А1 это условие выполнялось и для всей композиции (11).

Правило остановки итераций

Поскольку знания об идеальном сигнале отсутствуют, то недоступна для непосредственного измерения и погрешность приближенного решения

8 = х-х

Однако можно вычислить погрешность аппроксимации в пространстве образов оператора искажений:

у - Ах

«=1

22

п

П

так как нам известен оператор искажений. Рис. 3 демонстрирует связь этих величин. Если бы х(и) являлось точным решением, то выполнялось бы равенство е = Е = 0 . Иными словами, погрешности в пространстве образов и в пространстве прообразов оператора искажений имеют общий ноль.

Рис. 3. Погрешность решения в пространстве сигнала и пространстве искажений

Из погрешности (14) и итерационной формулы (10) вытекает:

Е = у - Ах(и) = х(и+1) - х

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

е2 и ЕИ.

В качестве критерия остановки итерационного процесса можно использовать:

Е2 <Д,

где Д - некоторый назначаемый порог.

Экспериментальное исследование

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

На рис. 4а - пример неискажённого изображения, на рис. 4б - результат восстановления предлагаемым методом. На рис. 4в приведено отконтрастированное изображение погрешности восстановления. Рис. 4г демонстрирует начальное приближение, которое значительно меньше соответствует исходному изображению, чем результат процедуры восстановления. Величина ошибки зависит от уровня коррелированно-сти изображения: чем меньше корреляция, т.е. меньше расстояние между объектами, тем ошибка выше.

При компьютерном моделировании оператора сглаживания использовалась дискретная свёртка. Пусть х (ть т2) - исходное квазинепрерывное изображение, h (к1, к2), - К < к1, k2 < К - ИХ сглаживающего фильтра, тогда оператор А1 примет вид:

х1 (т1, т2) =

К К

= Ё Ё h(к1,к2)х(т1 -к1,т2 -к2).

к1 =-К к2 =-К

Рис. 4. Примеры изображений: а) квазинепрерывное мозаичное поле (коэффициент корреляции 0,95), б)результат восстановления, в) погрешность восстановления (после контрастирования), г) начальное приближение

В экспериментах применялись фильтры с гауссовой импульсной характеристикой:

Ь (^ к2 ) = йехР I-

-К < к1, к2 < К,

(к2 + к22 )2 2 R2

где Q1 - константа, обеспечивающая выполнение условия нормировки

К, К,

X Ё Ь

к1 =-К к2 =-К

и прямоугольной импульсной характеристикой Ь2

(к, к2) —

1

, -К < к1, к2 < К

( 2 К +1)2 0, иначе

В качестве пространственной дискретизации искажённого изображения х1(т1, т2) использовалось равномерное прореживание в Т раз. В качестве оператора А3 использовалась интерполяция по ближайшему соседу до уровня детализации исходного квазинепрерывного изображения.

В экспериментах с шумом использовался гауссов белый шум отношением шум/сигнал d — DV / DX , где DX - дисперсия изображения, DV - дисперсия шума.

Размер исходных неискажённых квазинепрерывных изображений составлял 1024x1024 точки, параметр частоты прореживания составлял Т — 8 , параметры гауссовой и прямоугольной импульсных харак-

теристик определялись величинами К = 24, R = 8 и К = 8 соответственно. Эксперимент проводился на наборах по 10 изображений для трёх коэффициентов корреляции между соседними пикселами 0,9, 0,95 и 0,99.

Рис. 5а и рис. 56 демонстрируют зависимость величины е2 / DX от номера итерации для случаев с гауссовой и прямоугольной импульсными характеристиками в отсутствие шума.

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

a)

II II II а. а. а. i ! 1 0,90 0,95 0,99

1 V.

L4----

50 100 150 200

250

0,3

0,2

0,1

•s2/Dx 1

р-0,90

\ — - р=0,95 - р=0,99

*

1

\

С"--

б)

0

10 20 30 40

Рис. 5. Зависимость е2„^х от номера итерации п

для случая с: а) гауссовой ИХ, б) прямоугольной ИХ, - при различных коэффициентах корреляции изображений

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

Исследования метода при наличии шумов проводились для значений d = 0,001; 0,01; 0,1 для всех изображений. На рис. 6а изображены зависимости дисперсии погрешности восстановления от номера итерации для изображений с коэффициентом корреляции 0,95 и гауссовой искажающей импульсной характеристикой. При наличии шума погрешность восстановления имеет минимум, который хорошо прослеживается на графиках, что говорит об улучшении качества изображения.

Несмотря на отсутствие сходимости к точному решению при наличии шумов, итерационная процедура уменьшает погрешность восстанавливаемого изображения от 1,25 до 5 раз для изображений с корреляцией 0,9, от 2 до 15 раз при корреляции 0,95 и в 10 и более раз для корреляции 0,99.

Как видно из рис. 6а, оптимальное (в смысле погрешности) восстановление достигается относитель-

но быстро, как правило, в течение первых двух десятков итераций. Поведение величины ^ / Dх при этих же условиях эксперимента представлено на рис. 6б.

- d=0,001 - d=0,01  d=0,l

n

а) 0 0,05 0,04 0,03 0,02 0,01

е/А

50

100

150

200

-d=0,001 d-0,01 ...... d=0,l

б) 0 50 100 150 200

Рис. 6. Зависимость от номера итерации n для случая гауссовой ИХ, при значении коэффициента корреляции 0,95 и при отношении шум/сигнал d, равном 0,001, 0,01 и 0,1

Выводы

Описанная итерационная процедура повышает качество оценок изображений, близких к кусочно-постоянным, в широком диапазоне значений отношения сигнал-шум. Точность решения задачи восстановления ограничивается, во-первых, необходимой остановкой итерационного процесса, во-вторых, что более принципиально, наличием на изображении локальных «вставок» (объектов малой площади) среди протяжённых областей постоянной яркости.

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

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

Работа выполнена при финансовой поддержке РФФИ (гранты 13-01-12080-офи и 13-07-97006-р_поволжье_а), программы фундаментальных исследований Президиума РАН «Фундаментальные проблемы информатики и информационных технологий» (проект 2.12), а также Минобрнауки РФ (госконтракт № 02.G36.31.0001 от 12.02.2013 г. в рамках Постановления Правительства РФ от 09.04.2010 г. № 218).

Литература

1. Лупян, Е.А. Технологии спутникового мониторинга в сельском хозяйстве России / Е.А.Лупян, С.А.Барталёв , И.Ю.Савин // Аэрокосмический курьер. - 2009. - № 6. - С.47-49.

2. Методы компьютерной обработки изображений / под ред. В.А. Сойфера. - М.: Физматлит, 2003. - 784 с.

3. Василенко, Г.И. Восстановление изображений / Г.И. Василенко, А.М. Тараторин. - М.: Радио и связь, 1986. - 304 с.

4. Modestino, J. W., Stochastic image models generated by random tessellations of the plane / J.W. Modestino, R.W. Fries, A.L. Vickers //Computer graphics and image processing. - 1980. - Vol. 12(1). - P. 74-98.

References

1. Loupian, E.A. The remote sensing technologies for agricultural monitoring of Russia / Loupian E.A., Bartalev S.A., Savin I.U. // Aerospace Courier. - 2009. - №6. -P.47-49.

2. Methods of computer image processing / edited by V.A. Soifer. - Moscow: "Fizmatlit" Publisher, 2003. -748 p. - (In Russian).

3. Vasilenko, G.I. Image reconstruction / G.I. Vasilenko, A.M. Taratorin. - Moscow: "Radio i svyaz'" Publisher, 1986. - 304 p. - (In Russian).

4. Modestino, J. W., Stochastic image models generated by random tessellations of the plane / J.W. Modestino, R.W. Fries, A.L. Vickers //Computer graphics and image processing. - 1980. - Vol. 12(1). - P. 74-98.

ITERATIONAL METHOD FOR PIECEWISE CONSTANT IMAGES RESTORATION WITH AN A PRIORI KNOWLEDGES OF IMAGE OBJECTS BOUNDARIES

V.V. Sergeyev, A.Yu. Denisova Image Processing Systems Institute of the RAS

Abstract

This article observes restoration method for piecewise constant images with predefined areas' borders based on Van Cittert filtration. As a distortion Gaussian and rectangle impulse response are considered. Image to be reconstructed is the result of sampling and noise addition. The results of experimental research of dependency of accuracy and stop-criterion from iteration number are demonstrated. Also potential application for remote sensing image analysis such as quality enhancement of average assessments is described.

Key words: piecewise constant images, Van Cittert filtration, root mean square error, sampling, interpolation, Neumann series.

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

Сергеев Владислав Викторович родился в 1951 году. В 1974 году окончил Куйбышевский авиационный институт (ныне Самарский государственный аэрокосмический университет (национальный исследовательский университет), СГАУ). В 1993 году защитил диссертацию на соискание степени доктора технических наук. В настоящее время работает заведующим лабораторией математических методов обработки изображений в Институте систем обработки изображений РАН. Круг научных интересов: цифровая обработка сигналов, анализ изображений, распознавание образов, геоинформатика. Имеет около 270 публикаций, в том числе 56 статей, четыре монографии (в соавторстве). Председатель Поволжского отделения Национального комитета РАН по распознаванию образов и анализу изображений. Член-корреспондент Российской экологической академии и Академии инженерных наук РФ, член SPIE (The International Society for Optical Engineering), лауреат Самарской губернской премии в области науки и техники.

E-mail: vserg@smr.ru .

Vladislav Victorovich Sergeyev (1951 b.), graduated (1974) from the S.P. Korolyov Samara State Aerospace University (SSAU). He received his PhD in Technical sciences (1978) and DrSc degree in Physics & Maths (1993). At present he is a head of laboratory at the Image Processing Systems Institute of the Russian Academy of Sciences, and, holding a part-time position as the head of the Geoinformatics and Information Security sub-department at SSAU. The area of interests includes digital signals and image processing, geoinformatics and pattern recognition. He's list of publications contains about 270 scientific papers, including 4 monographs. He is a member of Russian Association of Pattern Recognition and Image Analysis and The International Society for Optical Engineering.

Денисова Анна Юрьевна родилась в 1988 году. В 2011 году защитила диплом магистра прикладной математики и информатики в Самарском государственном аэрокосмическом университете (СГАУ) (национальный исследовательский университет). В настоящее время работает стажёром-исследователем в Институте систем обработки изображений РАН в ЛММОИ и обучается в аспирантуре СГАУ. Круг научных интересов включает обработку изображений, геоинформационные системы.

E-mail: anna3138@yandex.ru .

Anna Yurievna Denisova was born at 1988. At 2011 graduated from Samara State Aerospace University as master of mathematics and computer science. Now works at the Image Processing Systems Institute of the RAS and studies at Samara State Aerospace University. The area of research interest includes image processing and geoinformational systems.

Получена 20 апреля 2013г.