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

кандидата технических наук
Костикова, Елена Валентиновна
город
Санкт-Петербург
год
2013
специальность ВАК РФ
05.25.05
цена
450 рублей
Диссертация по документальной информации на тему «Алгоритмы и архитектура видеоинформационной системы на основе пространственно-рекурсивного метода кодирования изображений»

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

На правах рукописи

КОСТИКОВА ЕЛЕНА ВАЛЕНТИНОВНА

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

Специальность: 05.25.05 - Информационные системы и процессы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

I 4 ОХТ 2013

Санкт-Петербург - 2013

005535944

Работа выполнена в ФГБОУ ВПО «Государственный университет морского и речного флота имени адмирала С. О. Макарова»

Научный руководитель: кандидат технических наук, профессор

Бабурин Валерий Александрович

Официальные оппоненты:

Устинов Андрей Александрович, доктор технических наук, профессор ФГКОУ ВПО «Военная академия связи имени Маршала Советского Союза С. М. Будённого» МО РФ, старший научный сотрудник НИЛ-6

Гласман Константин Францевич, кандидат технических наук, доцент ФГБОУ ВПО «Санкт-Петербургский государственный университет кино и телевидения», заведующий кафедрой видеотехники факультета технологий кино и телевидения

Ведущая организация: ОАО «Научно-исследовательский институт

телевидения», г. Санкт-Петербург

Защита состоится «14» ноября 2013 г. в /7" часов на заседании совета по защите докторских и кандидатских диссертаций Д 223.009.03 при ФГБОУ ВПО «Государственный университет морского и речного флага имени адмирала С. О. Макарова» по адресу: 198035, г. Санкт-Петербург, ул. Двинская, 5/7

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

Автореферат разослан « 3 » октября 2013 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцец

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

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

Технической основой информационной среды становятся видеоинформационные системы (Ю. Б. Зубарев, Ю. С. Сагдуллаев,

В. П. Дворкович). Разработка видеоинформационных систем (ВИС) приема, обработки, хранения и передачи сверхбольших потоков информации в реальном масштабе времени — это важная научно-техническая проблема.

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

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

Появление технологии «система на кристалле» и внедрение её в телевизионных системах (А. А. Умбиталиев, А. К. Цыцулин) позволили снять ограничения на сложность алгоритмов спектрального и пространственного методов кодирования и декодирования видеоинформации. При этом известно, что одним из перспективных направлений в области пространственного сжатия изображений для построения ВИС является применение пирамидально-рекурсивного (В. В. Александров, Н. Д. Горский) и триангуляционного методов.

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

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

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

качество видеоинформации и улучшить характеристики в структурной части, техническом и программном обеспечении ВИС.

Цель и задачи диссертации

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

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

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

2) разработка аналитической модели для оценки параметров ВИС на основе предложенного метода;

3) разработка параллельных алгоритмов сжатия и восстановления изображений;

4) разработка функциональной параллельной структуры видеоинформационной системы.

Область исследования

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

Объектом исследования являются полутоновые чёрно-белые изображения.

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

Методы исследования

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

Основные научные положения, выносимые на защиту:

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

2) математическая модель для случая равновероятного распределения особых точек на изображении позволяет определить оптимальные параметры (число полигонов при разбиении, число особых точек изображений и объём памяти) ВИС обработки, хранения и передачи видеоинформации;

3) предложенная архитектура видеоинформационной системы на основе технологии «система на кристалле» необходима для максимального распараллеливания предложенных алгоритмов сжатия и восстановления изображений;

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

Научная повизна работы:

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

2) разработана математическая модель для определения оптимальных параметров ВИС на основе предложенного метода (числа полигонов после разбиения, формы полигонов и числа ОТ), отличающаяся равновероятным распределением ОТ на изображении;

3) разработана архитектура ВИС, отличающаяся внедрением технологии «система на кристалле» и учётом максимального распараллеливания разработанных алгоритмов;

4) предложена систематизация алгоритмов сжатия и восстановления изображений, реализующих разработанный метод.

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

1. Разработаны алгоритмы, рабочие программы и подпрограммы на языке ООП С++ для сжатия и восстановления изображений по ОТ.

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

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

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

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

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

Впедрепне результатов работы

Основные теоретические и практические результаты нашли применение: в НИР «Разработка методологии построения наноэлектронных транспортных систем искусственного зрения на кристалле» ИПТ им. В. Н. Соломенко РАН; в ОКР «Цифра-ЗР-ЛЭТИ» СПбГЭТУ «ЛЭТИ»; в ОКР «Разработка ряда высокопроизводительных сложных функциональных блоков для специальных систем цифровой передачи данных», шифр «Цифра-СФ», выполненной ОАО «НИИТ». Также результаты работы, связанные с обработкой, хранением и передачей изображений, используются в учебном процессе кафедр САПР и ТВ СПбГЭТУ «ЛЭТИ». Имеются акты внедрения.

Апробация работы

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

1. На 13-ой Международной конференции «Цифровая обработка сигналов и ее применение», Москва, 2011 г.

2. На Международных конференциях «Транспорт России: проблемы и перспективы», Санкт-Петербург, 2011 и 2012 гг.

3. На ІП Международной научно-практической конференции «Перспективы развития информационных технологий», Новосибирск, 2011 г.

4. На Всероссийских научно-практических конференциях «Информационные технологии в профессиональной деятельности и научной работе», Йошкар-Ола, 2011 и 2012 гг.

5. На Международной научно-практической конференции ИТАП-2011 «Информационные технологии. Автоматизация. Актуализация и решение проблем подготовки высококвалифицированных кадров», Набережные Челны, 2011 г.

6. На 66-ой научно-технической конференции СПбНТОРЭС, посвященной Дню радио, Санкт-Петербург, 2011 г.

7. На 8 и 10-ой Международных научно-технических конференциях «Телевидение: передача и обработка изображений», Санкт-Петербург, 2011 и 2013 гг.

8. На XVII Международной научно-технической конференции «Современное образование: содержание, технологии, качество», Санкт-Петербург, 2011 г.

9. На Международной конференции «Научному прогрессу — творчество молодых», Йошкар-Ола, 2011 г.

Публикации

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

Структура и объем работы

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы, включающего 115 наименований. Основной текст работы изложен на 155 страницах машинного текста. Работа содержит 49 рисунков и две таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

- методы сжатия и восстановления изображений с использованием спектрального преобразования;

- пирамидально-рекурсивные методы;

- триангуляционные методы.

В результате предпочтение отдано комбинированному варианту обработки видеоданных с использованием триангуляционного и пирамидально-рекурсивного методов. Замечено, что триангуляционный метод не применялся до сих пор в сочетании с итерационным принципом поиска ОТ. Это объясняется следующими причинами:

-высокой степенью вычислительной сложности самого процесса триан1уляции;

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

Предложенный метод эффективен с точки зрения получения высокой степени сжатия и возможности построения высокопроизводительных параллельных ВИС.

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

Вторая глава посвящена разработке алгоритмов сжатия и восстановления изображений по ОТ и выбору оптимального

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

Алгоритмы поиска особых точек в пределах полигона имеют два основных направления: первое — с фиксированным расположением их в пределах полигона; а второе — с произвольным расположением.

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

Рассматриваются 4 варианта выбора ОТ с фиксированным расположением (рис. 1):

I) Центр каждого простого полигона с яркостью соответствующего пикселя (рис. 1).

ХиУ!^

ХиУЬ»!

Особые точки (х, у, V) Особые точки (х, у, V)

Рис. 1. Фиксированное расположение ОТ: а) в центре полигона, б) в вершииах

полигона.

Данный алгоритм позволяет определять центр полигона в зависимости от формы и размера полигона и записывать в массив связей координаты центра полигона по следующему алгоритму:

1. Определяются координаты вершин полигона и их яркости.

2. Вычисляются диагонали полигона, если полигон является прямоугольником или квадратом, определяется точка пересечения диагоналей; если полигон — треугольник, то определяется точка пересечения медиан.

3. Фиксируются координаты и яркость ОТ (рис. 1) в пределах полигона.

II) Вершины полигона с яркостями соответствующих пикселей.

Данный алгоритм позволяет вычислять координаты вершин полигона и записывать их в массив связей в зависимости от формы и размера полигона по следующему алгоритму (рис. 1):

1. Определяются координаты вершин полигона и их яркости.

2. Фиксируются координаты вершин полигона в массиве связей для хранения и передачи.

III) Центр каждого простого полигона с яркостью, равной значению моды в пределах полигона.

Данный алгоритм повторяет алгоритм первого варианта поиска ОТ за исключением п.З — определения яркости ОТ. В данном случае яркость определяется по значению моды в пределах исследуемого полигона.

Алгоритм нахождения моды:

1. Вычисляется гистограмма яркостей полигона.

2. Определяется яркость с максимальной частотой повторения и присваивается центру полигона.

IV) Центр каждого простого полигона с яркостью, равной значению средней взвешенной в пределах полигона.

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

Алгоритм нахождения средней взвешенной яркости:

1. Вычисляется гистограмма яркостей полигона.

2. Определяется частота повторения каждой яркости

3. Определяется средняя взвешенная яркость полигона по формуле: V =Еу/9/Е/?, где ^=0^255.

4. Присваивается средняя взвешенная яркость ОТ.

Особенность алгоритмов с фиксированным расположением

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

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

Во втором случае ОТ имеют произвольное расположение в пределах полигона. При этом координаты и яркость ОТ

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

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

Рассмотрены два варианта поиска ОТ с произвольным расположением:

I) ОТ является центром тяжести полигона в трехмерном пространстве.

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

II) ОТ имеет яркость, наиболее близкую к плоскости, построенной по методу наименьших квадратов в пределах полигона.

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

Характерной особенностью алгоритмов с произвольным расположением ОТ является наличие дополнительной процедуры поиска ОТ в каждом полигоне при разбиении изображения.

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

Предложена систематизация алгоритмов поиска ОТ, основанная, во-первых, на регулярном делении изображений на полигоны, во-вторых, на способе расположения ОТ в пределах полигона.

Предложено описание совокупности ОТ, ориентированное на решение задачи поиска ближайшей ОТ.

Третья глава посвящена математическому моделированию для оценки степени сжатия информации об ОТ на основе предложенного пространственно-рекурсивного метода поиска и

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

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

Требуется найти функции /ь.., /5 для нахождения оптимальных значений: п — числа особых точек, s — числа уровней разбиения, d — числа полигонов после разбиения, объема рабочей памяти и т.д. f\ = К] + К2, где Кх — информация, необходимая для кодирования и передачи информации о местоположении (координаты х и у) ОТ, К2 — информация, необходимая для кодирования и передачи значения яркости ОТ; /2 — суммарная площадь заполненных полигонов после появления особой точки; f$ — суммарная площадь пустых полигонов после появления особой точки; fu, — число пустых полигонов; /5 — число заполненных полигонов.

Информация о местоположении ОТ состоит из описания

последовательностей пространственно-рекурсивных разбиений,

что определяет нахождение ОТ с точностью до пикселя, при этом

степень сжатия определяется соотношением:

,, п т + п los, N i Е

а= --2— , или

п-т + b

k= П"°Рт + П"°Р

log N

п,юрт + Ъ

где

'нор

доля ОТ

на

исходном изображении, пнор= n/N; т — разрядность яркости ОТ; b — усредненное число бит информации, необходимое для кодирования

местоположения одной ОТ в пределах полигона, Е-доля пустых полигонов к заполненным.

Выполнено математическое

5 10

Рис. 2. Степени приближения к эпсилон-энтропии при различных значениях с1

моделирование и найдены рекуррентные соотношения (/!,.., /5) для определения функции

к=Лпнир., а, я, Е), где с! — число полигонов после разбиения, М— максимальное число разбиений, N=(1^.

Результаты моделирования (рис. 2) показали местоположение предложенных алгоритмов сжатия информации (кривые ¿/=2; 3; 4) по сравнению с теоретическим минимальным количеством

N1

информации (кривая ктш= -:-), которое

п!(Ы-п)!

соответствует теореме Шеннона об энтропии источника.

В результате математического моделирования получены следующие основные выводы:

- определено, что оптимальным при пространственно-рекурсивном разбиении изображения с равновероятным распределением ОТ является трихотомия исходного изображения;

- показана целесообразность предложенного метода кодирования при наличии на исходном изображении ОТ не более 20 % от общего числа точек изображения;

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

- показано, что оптимальное значение числа разрядов для кодирования ОТ является »2=6.

Четвертая глава посвящена сравнительному анализу результатов моделирования алгоритмов сжатия и восстановления изображений по ОТ для различных методов (рис. 3).

Рассматриваются и моделируются три алгоритма сжатия и восстановления по ОТ — пространственно-рекурсивные алгоритмы при разбиении на 2, 3 и 4 (ПРМ 2-4) полигона, где в качестве исходного изображения взято изображение размером 256x256 пикселей, а также известные алгоритмы сжатия на основе дискретного косинусного преобразования (ДКП), вейвлет преобразования (ДВП), алгоритм триангуляции Делоне (АТД).

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

Определены основные параметры для аппаратной реализации алгоритмов:

а) число обращений в память изображения;

б) среднее число операций, выполняемых на точку;

в) объем рабочей памяти;

г) число необходимых процессоров и др.

0,5 1,0 1,5 2,0 2,5 Рис. 3 ('равнение эффективности различных алгоритмов (а) кодирования исходного изображения (6) дня формирования измерительной ВИС

Пятая глава посвящена разработке архитектуры ВИС сжатия и восстановления изображений с максимально возможным распараллеливанием алюри і мок кодирования и декодирования но ОТ (рис. 4) с использованием технологии «система на кристалле».

Процесс разработки включает в себя три этапа:

1. разработку параллельных алгоритмов сжатия и восстановления изображений;

2. выбор элементной базы и разработку функциональной схемы на основе технологии «система на кристалле»;

3. оценку производительности ВИС.

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

Аппаратно-программной декомпозиции обеспечивают систематическую и оперативную оценку альтернатив реализации. Обмен между стоимостью и производительностью системы

Выходной бу фер массива ОТ и связей

Буфер хранения ОТ и обслуживания заявок

СФБ,

СФБ:

СФБ,

Бу фер межпроцессорной связи

I Кадровое ОЗУ Код Л Яркость ОТ «Л

Устройства ввода изображений Код Яркость ОТ ЯР2

Рис. 4. Функциональная схема взаимодействия аппаратно-программных средств ВИС кодирования изображений на основе пространственно-рекурсивного метода

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

Максимальная загрузка всех СФ-блоков обеспечивается наличием в составе ВИС двух взаимодействующих софт-процессоров (рис. 4):

1) СФБуп— сложно-функциональный блок для управления приёмом изображения, анализом полигонов где /-номер полигона, и формированием списка ОТ, подлежащего передаче по каналу;

2) СФБДП— сложно-функциональный блок для диспетчеризации и загрузки всех СФБТ с использованием следующих буферов:

межпроцессорных связей, обеспечивающих хранение информации о разбиении и ОТ;

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

- формирования заданий (РПЮг) для обслуживания бесперебойной работы всех СФБГ в составе ВИС.

Для вычисления производительности ВИС необходимо определить критический путь, определяющий быстродействие системы, требующий большого объема вычислений, и для процедуры сжатия включающий в себя анализ очередного полигона на разбиение (ЯР=0 — полигон не разбивается, ИР=\ -полигон разбивается) и поиск ОТ, а для процедуры восстановления — закраску полигона, на которую тратится больше всего времени.

При использовании технологии «система на кристалле» и оценке времени выполнения основных процедур критического

пути алгоритмов функционирования ВИС производительность системы достигает 20~25 кадров/сек. при обработке полутоновых черно-белых изображений.

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

В результате моделирования подсистемы сжатия и восстановления изображений в составе ВИС получены следующие результаты:

1) количество элементарных процессоров в подсистеме сжатия изображений при максимальной их загруженности и отсутствии конфликтов равно 26, а в подсистеме восстановления равно 3;

2) производительность подсистемы ВИС сжатия изображений составляет 35 кадров/сек., а для подсистемы восстановления составляет 25 кадров/сек.;

3) предложена функциональная схема ВИС с учётом максимальной возможности распараллеливания алгоритмов сжатия и восстановления изображений;

4) определены дополнительные параметры ВИС: объем оперативной памяти, число особых точек и т.д.;

5) разработана методика проектирования ВИС, которая заключается в определении критического пути максимально распараллеленного алгоритма, который для процесса сжатия связан с анализом полигона и поиском особых точек, а для процесса восстановления — с закраской полигона;

6) осуществлен расчет производительности системы.

Таким образом, экспериментальные исследования показали,

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложена аналитическая модель для расчета и оценки параметров ВИС при условии равновероятного распределения ОТ на исходном изображении, позволившая:

-определить зависимость количества пустых полигонов от количества ОТ;

-определить соотношение числа особых точек к общему числу точек исходного изображения (не более 25%);

-найти оптимальное число полигонов (равное 3) при разбиении.

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

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

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

6. Предложена архитектура видеоинформационной системы сжатия и восстановления изображений по особым точкам с учётом максимального распараллеливания алгоритмов, и разработан эскизный проект ВИС на базе технологии «система на кристалле». Определены количественные оценки аппаратных затрат и производительность системы в целом.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в изданиях, входящих в перечень ВАК РФ

1. Костикова, Е. В. Сопряженное проектирование на базе реконфигурируемых систем на кристалле [Текст] / Е. В. Костикова, Ш. С. Фахми // Информационно-управляющие системы,- 2010.-№3,- С. 38-43.

2. Костикова, Е. В. Пространственные алгоритмы кодирования изображений [Текст]/ Е. И. Колесников, Е. В. Костикова // Научно-технический вестник СПбГУ ИТМО.-2011,- № 3,- С. 88-92.

3. Костикова, Е. В. Исследование рекурсивных алгоритмов сжатия и восстановления изображений [Текст] / Е. И. Колесников, Е. В. Костикова, С. С. Шагаров // Известия СПбГЭТУ «ЛЭТИ»,-2011.- №4,- С. 36-40.

4. Костикова, Е. В. Разработка архитектуры видеоинформационной системы кодирования и декодирования на основе пространственно-рекурсивного метода [Текст] / В. А. Бабурин, Е. В. Костикова, Ш. С. Фахми // Журнал университета водных коммуникаций,- 2012,- Выпуск 1(13).- С. 89 - 97.

5. Костикова, Е. В. Математическое моделирование и оценка параметров видеоинформационной системы наблюдения на транспорте [Текст] / Е. В. Костикова // Журнал университета водных коммуникаций,- 2012,- Выпуск 3(15).- С. 113 - 119.

Свидетельства о государственной регистрация программ

6. Свидетельство о государственной регистрации программы для ЭВМ №2011613700. Полигональный рекурсивный кодер изображений / Е. И. Колесников, Е. В. Костикова №2011611142; заявл. 22.02.2011; зарег. в Реестре программ для ЭВМ 12.05.2011.

7. Свидетельство о государственной регистрации программы для ЭВМ №2011613077. Программный кодек изображений методом разбиения на два полигона / Е. И. Колесников, Е.В.Костикова - №2011611333; заявл. 28.02.2011; зарег. в Реестре программ для ЭВМ 18.04.2011.

Материалы конференций

8. Костикова, Е. В. Развитие триангуляционного подхода сжатия и восстановления изображений [Текст] / Е. И. Колесников, Е. В. Костикова // Б8РА — 2011 «Цифровая обработка сигналов и ее применение»: труды 13-ой Междунар. науч.-техн. конф. Москва: Российское научно-техническое общество радиотехники, электроники и связи имени А. С. Попова, 2011. С. 131 - 133.

9. Костикова, Е. В. Разработка полигонально-рекурсивных алгоритмов кодирования и декодирования полутоновых изображений [Текст] / Е. И. Колесников, Е. В. Костикова,

С. С. Шагаров // «Научному прогрессу — творчество молодых»: матер. Межд. науч. студ. конф. Йошкар-Ола: Изд-во Марийский государственный технический университет, 2011. С. 143 — 144.

10. Костикова, Е. В. Параллельные алгоритмы компрессии изображений с использованием рекурсивного метода [Текст] / Е. И. Колесников, Е. В. Костикова, С. С. Шагаров, Ш. С. Фахми // «Телевидение: передача и обработка изображений»: матер. 8-ой Междунар. науч.-техн. конф., посвященной 125-летию Санкт-Петербургского электротехнического университета «ЛЭТИ» и 50-летию первого пилотируемого космического полета Ю. А. Гагарина. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2011. С. 68 - 72.

П.Костикова, Е. В. Транспортные видеоинформационные системы: Методы, алгоритмы и технологии [Текст] / В. В. Березин, А. Ю. Ходарев, Е. В. Костикова, Ш. С. Фахми // «Телевидение: передача и обработка изображений»: матер. 10-ой Междунар. науч.-техн. конф. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2013. С. 23 - 29.

12. Костикова, Е. В. Проблемы обработки видеоинформации на транспорте [Текст] / В. В. Березин, А. Ю. Ходарев, Е. В. Костикова, Ш. С. Фахми, А. В. Зинкевич // «Телевидение: передача и обработка изображений»: матер. 10-ой Междунар. науч.-техн. конф. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2013. С. 62 - 63.

13. Костикова, Е. В. САПР видеоинформационных систем на основе технологии «система на кристалле» [Текст] / В. В. Березин, Е. В. Костикова, Ш. С. Фахми, А. В. Зинкевич // «Телевидение: передача и обработка изображений»: матер. 10-ой Междунар. науч.-техн. конф. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2013. С. 15 - 20.

14. Костикова, Е. В. Сравнение алгоритмов полигонально-рекурсивного метода кодирования нестационарных сигналов [Текст] / Е. И. Колесников, Е. В. Костикова // «Современное образование: содержание, технологии, качество»: матер. XVII Междунар. науч.-техн. конф. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2011. С. 270-271.

15. Костикова, Е. В. Трихотомический алгоритм кодирования и декодирования изображений [Текст] / И. А. Зубакин, Е. И. Колесников, Е. В. Костикова, С. С. Шагаров // Труды 66-ой науч.-техн. конф. СПбНТОРЭС, посвященной Дню радио. СПб: Изд-во СПбНТОРЭС, 2011. С. 283 - 285.

16. Костикова, Е. В. Разработка структур данных для кодирования особых точек в задачах сжатия и представления

изображений [Текст] / Е. И. Колесников, Е. В. Костикова // «Перспективы развития информационных технологий»: матер. III Межд. науч. пр. конф. Новосибирск: Изд-во НГТУ, 2011. С. 203-208.

17. Костикова, Е. В. Рекурсивные алгоритмы анализа и представления изображений для систем мониторинга на транспорте [Текст] / В. А. Бабурин, Ш. С. Фахми, Е. В. Костикова, // «Транспорт России: проблемы и перспективы — 2011»: труды Всероссийской науч.-практ. конф. СПб: Изд-во ИПТ РАН, 2011. С. 146- 151.

18. Костикова, Е. В. Рекурсивно-параллельный подход в задачах иерархического представления и обработки изображений [Текст] / Ш. С. Фахми, Е. В. Костикова, В. В. Козлов, Е. И. Колесников // Информационные технологии в профессиональной деятельности и научной работе: сборник трудов Всероссийской науч.-практич. конф. (Информационные технологии — 2012, том 2) Йошкар-Ола: Изд-во Марийский государственный технический университет, 2012. С. 178— 183.

19. Фахми Ш.С., Костикова Е.В., Бабурин В.А. Систематизация алгоритмов кодирования изображений в транспортных видеосистемах [Текст] / Ш. С. Фахми, Е. В. Костикова, В. А. Бабурин // «Транспорт России: проблемы и перспективы - 2012»: труды межд. науч.-практич. конф. СПб: Изд-во ИПТ РАН, 2012. С. 75 - 78.

20. Костикова, Е. В. Математическая модель для оценки параметров видеоинформационных систем распознавания на транспорте [Текст] / Е. В. Костикова // «Транспорт России: проблемы и перспективы — 2012»: труды межд. науч.-практич. конф. СПб: Изд-во ИПТ РАН, 2012. С. 79 - 84.

Соискатель Е. В. Костикова

Подписано в печать с оригинал-макета автора 07.10.13 Сдано в производство 07.10.13 Формат 60x84 1/16 Усл.-псч. л. 1,27. Уч.-изд. л. 1,1.

Тираж 70 экз. Заказ № 120

Государственный университет морского и речного флота имели адмирала С.О. Макарова 198035, Санкт-Петербург, ул. Двинская, 5/7

Отпечатано в типографии ФГБОУ ВПО ГУМРФ имени адмирала С. О. Макарова 198035, Санкт-Петербург, Межевой капал, 2

Текст работы Костикова, Елена Валентиновна, диссертация по теме Информационные системы и процессы, правовые аспекты информатики

Федеральное агентство морского и речного транспорта

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Государственный университет морского и речного флота имени адмирала С. О. Макарова»

«АЛГОРИТМЫ И АРХИТЕКТУРА ВИДЕОИНФОРМАЦИОННОЙ СИСТЕМЫ НА ОСНОВЕ ПРОСТРАНСТВЕННО-РЕКУРСИВНОГО МЕТОДА КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ »

Специальность: 05.25.05 - Информационные системы и процессы

04201365523

На прг

Костикова Елена Валентиновна

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель - к. т. н., профессор Бабурин В. А. Санкт-Петербург - 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...............................................................................................................4

1. ОБЗОР МЕТОДОВ И ТЕХНОЛОГИИ СЖАТИЯ ВИДЕОИНФОРМАЦИИ

В ПРИКЛАДНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ....................................12

1.1. Классификация видеоинформационных систем и технологий........................14

1.2. Методы сжатия и восстановления изображений с использованием разверток......................................................................................................................17

1.2.1. Методы кодирования изображений с преобразованием.........................18

1.2.2. Методы кодирования с предсказанием.............................................22

1.3. Пространственные методы сжатия и восстановления изображений..............23

1.3.1. Пирамидально-рекурсивные методы сжатия изображений.....................24

1.3.2. Триангуляционные методы сжатия и восстановления изображений.........26

1.4. Выводы по главе и постановка задач исследования.........................................31

2. РАЗРАБОТКА АЛГОРИТМОВ ВИДЕОИНФОРМАЦИОННОЙ ПОДСИСТЕМЫ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЙ..............35

2.1. Разработка алгоритмов сжатия и восстановления изображений на основе пространственно-рекурсивного метода.....................................................................38

2.1.1. Разработка алгоритмов с фиксированным и произвольным расположением опорных точек...............................................................43

2.1.1.1. Алгоритмы разбиения изображений с фиксированным расположением опорных точек в пределах полигона...................................46

2.1.1.2. Алгоритмы разбиения изображения с произвольным расположением опорных точек в пределах полигона........................................................48

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

2.2. Анализ и систематизация алгоритмов сжатия и восстановления изображений.................................................................................................................59

2.3. Выбор оптимального алгоритма сжатия и разработка структуры видеоданных................................................................................................................63

2.3.1. Пирамидально-рекурсивное представление изображений.....................70

2.3.2. Разработка и выбор оптимальной структуры видеоданных....................75

2.4. Выводы по второй главе......................................................................................78

3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНЫХ ПАРАМЕТРОВ ВИДЕОИНФОРМАЦИОННОЙ ПОДСИСТЕМЫ.......................79

3.1. Постановка задачи математического моделирования......................................79

3.2. Общий подход к кодированию информации об ОТ изображений...............80

3.3 Математическая модель оценки параметров ВИС.............................................82

3.4. Рекуррентные соотношения для вычисления числа пустых и заполненных полигонов.........................................................................................84

3.5. Результаты моделирования...............................................................89

3.6. Выводы по третьей главе.....................................................................................93

4. РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ АЛГОРИТМОВ ДЛЯ СОЗДАНИЯ

БАЗ ВИДЕОДАННЫХ ВИДЕОИНФОРМАЦИОННОЙ СИСТЕМЫ...................94

4.1. Основные задачи моделирования процессов сжатия и восстановления изображений.................................................................................................................96

4.2. Обобщенная модель видеоинформационной подсистемы сжатия и восстановления изображений..................................................................................98

4.3. Результаты сжатия изображений для создания баз видеоданных.................102

4.4. Сравнительный анализ результатов и область применения метода............117

4.5. Выводы по четвертой главе...............................................................................120

ЛИТЕРАТУРА.. ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

Опыт использования наноэлектронных средств передачи информации, изобретенных в конце XX века показал не только преимущества информационных систем, основанных на твердотельном телевидении, но и определил основные направления их совершенствования [1]. Исследования в области прикладного телевизионного вещания привели к появлению новых способов и методов передачи информации, и в частности видеоинформации. Результатом активной работы ученых в течение одного века стали новые широкополосные проводные и беспроводные системы, обеспечивающие возможность передачи (приема) больших объемов информации на значительные расстояния. Появились наряду с проводными кабельными и радиосредствами новые: радиорелейные, тропосферные, спутниковые и оптико-волоконные средства связи. Совершенствование вычислительной техники привело не только к изобретению компьютерной техники, но появлению нового принципа организации связи - Интернет и мобильной беспроводной телефонной связи. Все это позволило к концу XX века начать проектирование широкополосных мультисервисных сетей, главной задачей которых является обеспечение всеобщей доступности населения к мировым информационным ресурсам. Широкое распространение получает передача разнообразной мультимедийной информации в сетях связи. Здесь и различные системы мониторинга, наблюдения, технического зрения, видеотелефонии, регистрирующие и передающие огромные объемы видеоданных, и различные автономные системы-роботы, принимающие решение на основе анализа видеоинформации, и полиграфия с возросшим объемом иллюстраций в печатной продукции, и медицина, и другие направления. Разработка эффективных методов обработки видеоинформации по-прежнему остается актуальной задачей, так как они обеспечивают: улучшение изображений для их наилучшего визуального восприятия человеком; сжатие видеоданных для хранения и передачи по

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

В создаваемой глобальной информационной инфраструктуре особое место занимает многофункциональная интерактивная видеоинформационная система (ВИС) [2-11], которая по своей сути моделирует зрительную систему человека и обеспечивает доставку информации о событиях или иной информации с любой точки нашей планеты для ее зрительного восприятия на расстоянии [12-21]. И это не случайно - ведь свыше 80% информации человек получает через органы зрения. Предтечей видеоинформационной системы по праву можно считать телевизионные системы. Именно эволюция составных частей телевизионной системы сделала возможным выход телекоммуникаций на новый качественный уровень [7-12].

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

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

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

Цифровые методы преобразования статических и динамических изображений обеспечивают высокое качество изображения при воздействии помех, способствуют повышению пропускной способности каналов передачи информации, обеспечивают надежность хранения информации [41-50].

При цифровой обработке изображений применяются различные преобразования: Фурье, косинусное, синусное, наклонное, Адамара, Хаара, сингулярное и другие, позволяющие в той или иной степени сократить объем информации [26, 27]. Актуальность алгоритмов сжатия изображений (как и видео) определяется своеобразными особенностями типа данных. Во-первых, изображения (видео) обычно требуют для хранения гораздо большего объема памяти, чем текст. Во-вторых, человеческое зрение при анализе изображений сравнительно нечувствительно к малым изменениям в изображении, что позволяет создавать эффективные алгоритмы с высокой степенью сжатия изображений, в которых декомпрессированное изображение не будет совпадать с оригиналом. Третья особенность изображений - обладание значительной статистической избыточностью. То есть, как правило, большая часть площади изображения одного кадра приходится на области с постоянной или мало меняющейся в пространстве (как по горизонтали, так и по вертикали) яркостью, а резкие световые переходы и детали малых размеров занимают малую долю площади изображения. Коэффициент корреляции соседних элементов изображения близок к единице, поэтому, зная яркость одного элемента можно с высокой степенью вероятности предсказать значение соседнего. Такого рода статистическую избыточность называют пространственной избыточностью изображения. Она устраняется путем применения к блокам изображения определенного размера преобразования, позволяющего перейти от массива коррелированных элементов изображения к меньшему по размеру массиву коэффициентов преобразования, по которым возможно восстановить изображение. Такой способ кодирования сигнала при передаче изображений позволяет существенно сократить необходимый при этом цифровой поток, а, следовательно, и необходимую для его передачи полосу частот канала.

Изображения соседних кадров обычно очень похожи друг на друга. По распределению яркости в одном кадре можно с высокой степенью точности предсказать распределение яркости следующего кадра. Эта предсказуемость указывает на временную избыточность изображения, которая устраняется: а) путем межкадрового предсказания и формирования вектора движения, подвергающегося кодированию [15]; б) использованием нового метода,

основанного на поиске оптимального базиса преобразования во временной области [50] и в) применением трёхмерного косинусного преобразования [5270].

В настоящее время быстро развивается направление представления и обработки изображений с использованием рекурсивных (регулярно-иерархических, пирамидальных, конусных) структур [34, 42]. При представлении рекурсивной структурой изображение разбивается на полигоны, а затем процедура разбиения рекурсивно повторяется для каждого полигона до тех пор, пока его размер не станет равным размеру элемента исходного изображения. Такой процесс называется рекурсивной или регулярной декомпозицией. Каждому блоку приписывается значение, называемое «яркостью» или «цветом» и являющееся его интегральной характеристикой. По завершении процесса декомпозиции получается набор изображений, последовательно уточняющих друг друга и сходящихся к исходному; этот набор обычно называют пирамидой изображения. Такие методы появились несколько лет назад и получили название - представление на основе пирамидальных структур [34].

Наряду с этим развивается самостоятельное направление, связанное со сжатием изображений и основанное на применении триангуляционных методов аппроксимации, суть которых заключается в нерегулярном соединении множества особых точек плоскими треугольниками [43, 44]. Известно, что данный метод эффективен тем, что обеспечивает высокий коэффициент сжатия при нерегулярном расположении особых точек на исходном изображении. Однако с точки зрения аппаратной реализации данный метод исключает возможность параллельной обработки. Кроме того, следует отметить и отсутствие эффективных способов поиска особых точек.

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

пирамиды «сверху вниз») процессов человеческого восприятия. Синтетическое узнавание также может быть смоделировано при использовании пирамидальных структур. Действительно, если алгоритм представления видеоданных не зависит от их содержания и определен заранее, то имеется возможность быстрого параллельного ввода видеоданных в систему одновременно с получением обобщенного описания. Получение такого обобщения не требует выделения семантической структуры изображений, т.е. исключается долгий аналитический путь восприятия. Анализ методов сжатия на основе пирамидально-рекурсивного подхода показал, что все они так или иначе преследуют цель сокращения избыточности на изображении, где восстановление производится путем присвоения области одной яркости (например, средней) [45], но у них отсутствуют способы выделения существенных признаков на исходном изображении, что является актуальным для решения задач, связанных со сжатием и обработкой изображений при проектировании видеоинформационных систем [А 12, А16, А17].

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

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

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

2) разработка аналитической модели для оценки параметров ВИС на основе предложенного метода;

3) разработка параллельных алгоритмов сжатия и восстановления изображений;

4) разработка функциональной параллельной структуры видеоинформационной системы.

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

Объектом исследования являются полутоновые черно-белые изображения.

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

Методами исследования в диссертационной работе являются методы теории вероятностей и математической статистики, методы обработки изображений и математического моделирования на ЭВМ.

Основные научные положения, выносимые на защиту:

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

2) математическая модель для случая равновероятного распределения особых точек на изображении позволяет определить оптимальные параметры (число полигонов при разбиении, число особых точек изображений и объем памяти) ВИС обработки, хранения и передачи видеоинформации;

3) предложенная архитектура видеоинформационной системы на основе технологии «система на кристалле» необходима для максимального распараллеливания предложенных алгоритмов сжатия и восстановления изображений;

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

Научная новизна работы заключается в следующем:

1) ра�