1

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

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

АЛГОРИТМЫ И АРХИТЕКТУРА

ВИДЕОИНФОРМАЦИОННОЙ СИСТЕМЫ НА ОСНОВЕ

ПРОСТРАНСТВЕННО-РЕКУРСИВНОГО МЕТОДА

КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

198035, г. Санкт-Петербург, ул. Двинская, 5/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

критерию поиска особых точек.

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

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

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

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

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

алгоритмической и программной реализации предложенного метода:

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

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

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

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

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

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

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

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

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

2. На Международных конференциях «Транспорт России:

проблемы и перспективы», Санкт-Петербург, 2011 и 2012 гг.

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

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

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

высококвалифицированных кадров», Набережные Челны, 2011 г.

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

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

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

прогрессу — творчество молодых», Йошкар-Ола, 2011 г.

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

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

Основной текст работы изложен на 155 страницах машинного текста. Работа содержит 49 рисунков и две таблицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x1,y1,v1 x2,y2,v Рис. 1. Фиксированное расположение ОТ: а) в центре полигона, б) в вершинах Данный алгоритм позволяет определять центр полигона в зависимости от формы и размера полигона и записывать в массив связей координаты центра полигона по следующему алгоритму:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Определяется средняя взвешенная яркость полигона по формуле: v =vqfq / fq, где q=0255.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть N – общее число пикселей исходного изображения.

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

Требуется найти функции f1,.., f5 для нахождения оптимальных значений: n – числа особых точек, s – числа уровней разбиения, d – числа полигонов после разбиения, объема рабочей памяти и т.д. f1 = К1 + К2, где К1 – информация, необходимая для кодирования и передачи информации о местоположении (координаты x и y) ОТ, К2 – информация, необходимая для кодирования и передачи значения яркости ОТ; f2 – суммарная площадь заполненных полигонов после появления особой точки; f – суммарная площадь пустых полигонов после появления особой точки; f4 – число пустых полигонов; f5 – число заполненных полигонов.

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

исходном изображении, nнор= n/N; m – разрядность усредненное число бит доля пустых полигонов к заполненным.

Выполнено математическое моделирование и найдены рекуррентные соотношения (f1,.., f5) для определения функции k=f(nнор., d, s, E), где d – число полигонов после разбиения, M – максимальное число разбиений, N=dM.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРM ДВП ПРМ20, ПРМ Рис. 3. Сравнение эффективности различных алгоритмов (а) кодирования исходного изображения (б) для формирования Пятая глава посвящена разработке архитектуры ВИС сжатия и восстановления изображений с максимально возможным распараллеливанием алгоритмов кодирования и декодирования по ОТ (рис. 4) с использованием технологии «система на кристалле».

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

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

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

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

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

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

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

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

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

диспетчеризации и загрузки всех СФБ с использованием следующих буферов:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определены количественные оценки аппаратных затрат и производительность системы в целом.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

28.02.2011; зарег. в Реестре программ для ЭВМ 18.04.2011.

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

Российское научно-техническое общество радиотехники, электроники и связи имени А. С. Попова, 2011. С. 131 - 133.

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

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

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

Гагарина. СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2011. С. 68 – 72.

11. Костикова, Е. В. Транспортные видеоинформационные системы: Методы, алгоритмы и технологии [Текст] / В. В. Березин, А. Ю. Ходарев, Е. В. Костикова, Ш. С. Фахми // «Телевидение:

передача и обработка изображений»: матер. 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.

Систематизация алгоритмов кодирования изображений в транспортных видеосистемах [Текст] / Ш. С. Фахми, Е. В.

Костикова, В. А. Бабурин // «Транспорт России: проблемы и перспективы – 2012»: труды межд. науч.-практич. конф. СПб: Издво ИПТ РАН, 2012. С. 75 – 78.

20. Костикова, Е. В. Математическая модель для оценки параметров видеоинформационных систем распознавания на транспорте [Текст] / Е. В. Костикова // «Транспорт России:

проблемы и перспективы – 2012»: труды межд. науч.-практич.

конф. СПб: Изд-во ИПТ РАН, 2012. С. 79 – 84.