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

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

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

Разработка и исследование алгоритмов обработки изображений базируются на математических моделях (ММ), адекватных реальным изображениям. К настоящему времени разработано большое число различных ММ двумерных изображений, на базе которых создан целый ряд алгоритмов обработки [10, 11]. Набольшее количество ММ разработано для полутоновых изображений, аппроксимируемых марковскими процессами. Значительный вклад в разработку двумерных математических моделей марковского типа внесли российские ученые В. В. Быков [5], К. К. Васильев [13],.

В.Р.Крашенинников [12], Б. Г. Бондур [6], А. А. Спектор, [13], В. Н. Васюков [16], Я. А. Фурман [17], Е. П. Петров [18] а также зарубежные ученые А. К. Джайн [10], К. Абенд [19], Дж. Вудс [20], Дж. Безаг [21,22], Р. Кашьяп [23], Г. Винклер [24] и др. [25−28]. Наибольший практический интерес предсталяют ММ видеопоследовательностей изображений. Работ, посвященных ММ видеопоследовательностей полутоновых изображений, представляющих собой случайные марковские процессы размерностью, превышающей 2, из-за большой вычислительной сложности значительно меньше. Среди них следует отметить работы [1, 3, 9−11, 14,15, 26, 31−34].

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

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

Трудности создания ММ цифровых полутоновых изображений и их видеопоследовательностей, представленных g-разрядными двоичными числами и удовлетворяющих требованию высокой вычислительной эффективности, значительно возрастают, если учесть, что они являются случайными процессами, принимающими q = 2g дискретных значений.

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

Обоснованность выбора в качестве ММ цифровых полутоновых изображений и их видеопоследовательностей многомерного дискретнозначного марковского процесса базируется на близости их статистических характеристик и опыта использования в работах [37, 38] моделей двумерного и трехмерного многозначных марковских процессов, для разработки и исследования алгоритмов нелинейной фильтрации видеопоследовательности цифровых полутоновых изображений, искаженных аддитивным белым гауссовским шумом. Результаты исследований, приведенные в [37, 38], показали адекватность указанных ММ реальным процессам.

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

Математическая модель двух статистически связанных видеопоследовательностей цифровых полутоновых изображений, представляющих собой многомерный (четырехмерный) многозначный марковский процесс исследовалась в работах [31−34], где многомерный многозначный марковский процесс представляется набором простых в реализации двумерных марковских процессов с вычислительными ресурсами, не зависящими от размера изображения [31−34]. При этом предполагалось, что статистические связи между двумерными процессами, являющимися составными частями четырехмерного процесса, несущественна. Исследования, проведенные в [34] показали, что при размерности моделируемого процесса больше трех такое представление многомерного процесса приводит к нарушению адекватности ММ реальному процессу и тем больше, чем больше размерность моделируемого процесса. Метод построения многомерной каузальной ММ цифровых полутоновых изображений и их статистически связанных видеопоследовательностей, предложенный в [28, 34, 35], основанный на использовании многомерных многозначных марковских процессов и энтропийном подходе к вычислению матриц вероятностей перехода в многомерных цепях Маркова, лишен недостатков, присущих ММ в [32], что позволяет успешно использовать разработанные модели для синтеза алгоритмов фильтрации цифровых полутоновых изображений в их различных статистически связанных комбинациях.

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

2. Разработка ММ цифрового марковского полутонового изображения на основе казуального двумерного многозначного марковского процесса.

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

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

5. Исследование разработанных ММ на адекватность статистических характеристик реальным цифровым полутоновым изображениям и их видеопоследовательностям.

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

На защиту выносятся следующие научные результаты, развитые или впервые полученные в настоящей работе:

1. Математическая модель цифрового полутонового марковского изображения на основе каузального одномерного многозначного марковского процесса.

2. Математическая модель цифрового полутонового марковского изображения на основе каузального двумерного многозначного марковского процесса.

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

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

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

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

7. Расчет объема вычислительных операций и памяти ЭВМ при реализации разработанных математических моделей.

Новизна научных результатов заключается в следующем'.

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

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

По теме диссертации опубликовано 18 работ. Из них — 2 статьи в журналах, рекомендуемых ВАК, 11 статей в научно-технических журналах и сборниках. Основные положения и результаты диссертационной работы отражены в депонированной рукописи-монографии (№ 275-В2006). Материалы диссертационной работы докладывались и обсуждались на VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004): Российской научно-технической конЛепениии (НТЮ «Ппибогюстпое / ш> 1 1 1 V /1 11 ние в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2004) — V Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2004) — Всероссийской НТК «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, 2005) — VIII Международной НТК «Цифровая обработка сигналов и ее применения» (Москва — 2005 г.) — XII Международной НТК «Радиолокация, навигация, связь RNLC» (Воронеж — 2006 г.) — 61-й научной сессии, посвященной Дню радио (Москва — 2006 г.) — Всероссийской НТК «Наука-производство-технология-экология» (Киров — 2006 г.) — 14 межрегиональной НТК «Обработка сигналов в системах телефонной связи и вещания» (Н.Новгород — 2006 г.). Опубликованы статьи в сборнике «Проблемы обработки информации: Вестник ВНЦ Верхне-Волжского отделения АТН РФ» (Н.Новгород — 2006 г.). Получено свидетельство об официальной регистрации программы для ЭВМ «Математическая модель многомерных марковских цифровых полутоновых изображений», per. № 2 006 613 667 от 20.10.2006. Материалы диссертационной работы были использованы при подготовке учебного пособия «Моделирование цифровых полутоновых изображений марковского типа с дискретными аргументами» (Изд-во ВятГУ, 2006 г.).

Диссертационная работа состоит из четырех глав.

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

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

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

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

Выводы по главе 4.

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

2. Дана методика построения многомерной (/г-мерной) ММ статистически связанных цифровых полутоновых изображений, которая строится для каждого конкретного случая по формальным процедурам. При реализации ММ отсутствуют вычислительные операции, а объем памяти при моделировании h-мерного процесса не превышает размера (h-2)-g двоичных изображений.

3. Проведен анализ разработанной четырехмерной ММ на соответствие статистических характеристик искусственных изображений, заданным в модели. Для 50-го кадра видеопоследовательности позиции d искусственных полутоновых изображений оценки вероятностей перехода, вычисленные для двоичного разрядного изображения 171^=0,922, 27г|р = 0,924 на статистике 256×256, отличаются от заданных 0,92 не более чем на 0,5%, для 50-го кадра видеопоследовательности позиции d-1 оценки вероятностей перехода составляют =0,918, 27г£} = 0,922 при заданных ^^nf = 0,92.

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

ЗАКЛЮЧЕНИЕ

.

В работе предложены научно-обоснованные решения задач построения математических моделей цифровых полутоновых изображений и их статистически связанных видеопоследовательностей, являющиеся случайными многозначными марковскими процессами различной размерности. Разработанные ММ были успешно использованы при синтезе и исследовании алгоритмов нелинейной фильтрации реальных цифровых полутоновых изображений и их видеопоследовательностей в работах [37, 38], подтвердив их адекватность реальным процессам.

Среди результатов, полученных в работе, к наиболее значимым следует отнести следующие.

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

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

3. На основе разделения цифровых полутоновых изображений марковского типа на разрядные двоичные сечения и использования энтропийного подхода к вычислению элементов переходных матриц для каждого разрядного сечения, разработаны двумерные ММ стационарных и нестационарных марковских цифровых полутоновых изображений, представляющих собой набор разрядных двоичных марковских изображений. Адекватность ММ реальным изображениями подтверждена совпадением оценок элементов матриц переходных вероятностей, для искусственных и реальных изображений и синтезированным на основе ММ в [36] алгоритмом нелинейной фильтрации цифровых полутоновых изображений марковского типа. Оценки вероятностей перехода, вычисленные для искусственного изображения 1%и =0,8983 2%и =0,8989 на статистике 512×512, отличается от заданных 17t/V=2 тсг (=0,9 на 0,5%, на статистике 1024×1024 оценки.

1%и = 0,8995 2%и = 0,899, отличается от заданных 1пи=2%. = 0,9 на 0,2%.

4. Разработана трехмерная ММ видеопоследовательности цифровых полутоновых изображений, являющаяся трёхмерным многозначным марковским процессом с разделимой экспоненциальной корреляционный функцией, допускающей представление трёхмерного многозначного марковского процесса как суперпозицию трёх одномерных многозначных марковских процессов. Адекватность статистических характеристик искусственных изображений реальным цифровым полутоновым изображениям видеопоследовательности доказана оценками вероятностей перехода в различных кадрах, вычисленные для одной из разрядных видеопоследовательностей искусственных изображений 1 я^ = 0,6936, 2nf = 0,6984 в первом кадре, а в 20-м кадре '4/) = 0,6979, 2 7^ = 0,6987 отличаются от заданных 'л= 0,7 не более чем на 0,3%.

5. Разработана четырёхмерная ММ двух статических связных видеопоследовательностей цифровых полутоновых изображений, на основе четырёхмерного многозначного марковского процесса с разделённой экспоненциальной автокорреляционной функцией, позволяющей представить четырёхмерный многозначный марковский процесс, как суперпозицию четырёх одномерных многозначных марковских процессов. Проведен анализ разработанной четырехмерной ММ на соответствие статистических характеристик искусственных изображений, заданным в модели. Для 50-го кадра видеопоследовательности позиции d искусственных полутоновых изображений оценки вероятностей перехода, вычисленные для двоичного разрядного изображения 'тг^ =0,922, = 0,924 на статистике 256×256, отличаются от заданных = 0,92 не более чем на 0,5%, для 50-го кадра видеопоследовательности позиции d-1 оценки вероятностей перехода составляют =0,918, = 0,922при заданных 2Tif=nf = 0,92.

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

7. Показано, что статистически связанные видеопоследовательности обладают большой статистической избыточностью, которую целесообразно использовать при обработке цифровых полутоновых изображений. Так в одномерном случае вероятность появления одного и того же значения элемента изображения равна пf = 0,9, то в двухмерном njp = 0,987 в трехмерном — = 0,998 629, в четырехмерном т^}л =0,9 998 478.

7 15.

8. Показано, что при реализации разработанных ММ отсутствуют вычислительные операции, а объем памяти при моделировании^{-мерного} процесса не превышает размера (h-2)-g двоичных изображений.

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