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

>Г6 од

САНКТ- ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ " О ¡'Г1\ , . -._

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

Фахми Шакиб

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

Специальность: 05.13.13 - Вычислительные машины,

комплексы, системы и сети

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

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

Работа выполнена в Санкт-Петербургском Государственном электротехническом университете.

Научный руководитель -кандидат технических наук, профессор ШМИДТ Е К.

Официальные оппоненты: доктор технических наук, профессор ЫЕТЛИЦКШ Е. А. кандидат технических наук, доцент ЛУЦИВ Е Р.

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

Защит.а диссертации состоится " /У " декабря 1ддз т. в {0— часов на заседании специализированного совета К 063. 36.12 Санкт-Петербургского Государственного электротехнического университета по адресу: 197376, Ранкт-Петербург, ул. Проф.Попова, 5.

С диссертацией можно ознакомиться в библиотеке университет Автореферат разослан " ^ " ОеХСьбрЯ }ддз

Ученый секретарь специализированного совета

БАЛАКИН ЕЕ

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

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

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

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

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

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

- разработка метода сжатия и восстановления изображений. 1иентированного на создание высокоэффективной систем^;

- разработка аналитической модели для опенки степени слога информации об ОТ;

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

- разработка функциональной структуры пистоли.

Штоды исследования. В диссертационной работе иепольаова-[сь рекурсивные методы программирования, теории вероятностей, методы моделирования на ЭШ

Научная новизна. ' Основными результатами диссертационно: работы являются:

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

2. Предложена аналитическая модель для оценки степен] сжатия информации при представлении и кодировании ОТ.

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

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

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

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

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

4. Даны рекомендации по выбору параметров алгоритмов сжатия информации об ОТ в процессе деления исходного изображен«! на полигоны.

Внедрение результатов работы. Основные теоретические i практические результаты использованы при выполнении следующих научно-исследовательских работ :

- "Исследование и разработка вычислительных комплексо! для цифровой обработки сигналов", ГБ-2/ВТ9,

- "Разработка комплекса технических средств и программного обеспечения класса основ ВТ", ГБ-2 АСОИУ-З/ВТ,

- "Радиоэлектронные системы прогнозирования чрезвычайны? ситуаций", ЧС 0.20.93.

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

/

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

Апробация работы: Основные результаты диссертационной ра-оты докладывались на:

- научно-технической конференции " Актуальные проблемы азвития радиотехники, электроники и связи" (г. Ленинград, анкт-Петербург, 1991 и 1992 гг.);

- на 48-ой научно-технической конференции, посвященной НЮ РАДИО (г. Санкт-Петербург, апрель 1993 г.).

Публикации по теме диссертации: опубликовано 4 статьи и 3 езиса на областных конференциях.

Структура и обьем работы. Диссертационная работа состоит :з введения, пяти глав, заключения, списка литературы, вклю-:ающего 60 наименований. Основной текст работы изложен на 175" траницах машинного текста. Работа содержит гг рисушсов, г таблиц.

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

Во-введэнии обоснована актуальность теш, сформулировала 1ель и основные задачи исследования.

В первой главе проведен обзор существующего положения в бласти пространственного сжатия изображений. Основное внимание ■делено следующим методам:

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

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

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

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

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

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

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

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

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

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

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

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

- моделирование алгоритмов и проведение сравнительно: анализа результатов для оценки эффективности сжатия и восст; вовлэния изображений;

- разработку эскизного проекта системы на базе ТМЗ 320: с полной загрузкой всех процессоров в системе.

Вторая глава посвящена разработке алгоритмов сжатия восстановления по ОТ. Особое внимание уделено регулярным алп ритмам сжатия и восстановления на основе пирамидально-реку] сивного разбиения исходного изображения ча полигоны. Рассма' ривашея алгоритмы двух типов:

- алгоритмы с фиксированным расположением ОТ в предел; полигона;

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

Алгоритмы с фиксированным расположением ОТ рассмотре! подробно и проведено моделирование их на ЭВМ. Исходное ква, ратное изображение делится на два прямоугольных треугольник Далее оценивается точность аппроксимации зтими треугольника!

ри условии, что плоскость треугольника определяется по коор-инатам и яркостям вершин треугольников, а яркости внутренних эчек линейно интерполируются. Те треугольники, точность

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

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

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

Предложены четыре новых алгоритма поиска ОТ:

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

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

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

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

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

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

- 6 - "

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

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

Характерной особенностью модели является введение пусты полигонов под которыми понимаются полигоны, не содержащие ОТ, при этом степень сжатия определяется соотношением:

k = ( £*v + £*logN)/( £*v + b) , где e - доля ОТ на исходном изображении, £ = n/N, где п - число ОТ,

N - общее количество точек исходного изображения, V - разрядность яркости ОТ,

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

Найдены рекурентные соотношения для определения функции b - f( £,d,m), где d - число полигонов после разбиения, m - максимальное число разбиений, N = ûm .

На рис. 1 показано местоположение данного способа кодирования ( кривая 1) по сравнению с теоретическим количеством информации (кривая 2), что соответствует теореме Шеннона об энтропии источника, и непосредственным способом кодирования 01 (кривая 3).

Под непосредственным способом кодирования подразумеваете? простой алгоритм: при малом числе ОТ кодируются и передаются координаты- При большом числе ОТ осуществляется сканирование изображений, каждая точка изображения кодируется одним битом, указывающим является данная точка опорной или нет:

bm/n- '¿loge'" (1 -£)10Sf(l -£),.

ΣlogM, при 0 N< £ v< 1/logN

1, при 1/logN s< £ 0.5.

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

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

100 00 80 70 60 50 40 30 20 10

А)

ю

20

Рис. 1 Количество информации при: 1. Ь=Г( £ ),

2. Ь,

МП'

3. ьн.

0.8 •• 0.7 -0.6 -0.5 -0.4 -0.3 -0.2 • 0.1 -

Б," бит/пиксёл ^ Л

к* 4

* \ * \ * \ А ^

■4 5"

У

(IV, дискреты яркости 7.

1.6

3.1

4.7

6.2

7.8

Рис. 2 Зависимость степени сжатия от заданных отклонений * Оценка субъективного качества результирующего изображения по пятибалльной шкале;

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

результаты алгоритма разбиения на треугольники.

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

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

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

Получено допустимое искажение сГху=2 пиксела (приблизительно один процент от размера изображения), обеспечивающее высокую степень сжатия (рис. 2), где в качестве исходного изображения взято изображение размером 256x256 типа "Портрет".

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

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

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

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

- объем рабочей памяти.

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

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

- разработку параллельных алгоритмов;

- выбор элементной базы и разработку функциональной схемы;

- оценку производительности системы.

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

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

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

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

При анализе треугольника выполняются: чтение N1 точек из памяти изображения и запись N2 точек. Таким, образом, время, затраченное на анализ треугольника в среднем будет Ы - Nl.il + N2.12, где Т1, Т2 - средние интервалы медду обращениями к памяти при чтении и записи, соответственно. Тогда общее усредненное время обращения в память при чтении и записи будет

Тс<0 = (N1.11 + N2. Т2)/(N1 + N2).

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

п = Тер /1ап , где Тол - время обращения в память изображения.

По результатам моделирования в третьей главе было найдено количество треугольников N3 после обработки изображения, следовательно, время обработки одного кадра изображения t будет: Ьв = Т^*

Время Ь выражается следующим образом: ^ = Т„„*( N1 + N2^3 . Определяя значения N1, N2 и N3 получим окончательный вариант времени обработки одного кадра:

** = ^«»^Ш!)^), где

- 10 -

число обращений в память, иаобраявний при анализе, MIR(О - количество треугольников размера i, P¿ - периметр треугольников размера i.

Как было отмечено ранее, время t справедливо при соблюдении баланса в системе.

Следует отметить, что, если ^реальное количество процессоров r\p > ns, то t не увеличивается иа-аа ограниченности скорости памяти. Если n р < n g, то время обработки уменьшится согласно формуле

t р - t£*n¿yn^ .

При использовании элементной базы семейства TMS 32010 и времени обращения в память изображений Т - 200 не производительность системы достигает 20 кадр/сек размером 256x256 трчек.

Анализ параллельного алгоритма показал, что число операций для закраски одной точки при восстановлении изображения равно 26. Тогда можно оценить время восстановления одного кадра- -г =26*N*T

Для изображения размером 255x256, t -0.3 сек/кадр, чему , соответствует производительность 3 кадр/сек.

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

Результатами данной главы являются :

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

- разработан эскизный проект системы на базе TMS 32010,

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

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

- 11 -

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

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

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

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

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

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

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

Выявлены возможности существования новых.методов сжатия и восстановления изображений по ОТ. '

5.'Предложены сравнительные результаты расчета степени сжатия изображения по алгоритмам с.фиксированным расположением ОТ в пределах полигона. При субъективном качестве результирующего ■изображения (типа "Портрет") достигнута степень сжатия 0. 42 бит/пиксел.

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

7. Разработан эсгаганый проект многопроцессорной системы на базе ТМЗ 32010. Определены количественные оценки аппаратных затрат и производительность системы в целом: 20 кадр/сек размером 256x256 точек.

- 12 -

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

1. Фахми Ш., Шах ЕЕ, Шмидт ЕК. Алгоритм слития иаобра-каэний с предсказанием по ОТ / JBT1L - JL , Деп. в ВИНИТИ 04.02.91, N 523-В91. - 30 С.

2- Фахш DL , Шах Е Е , Пкидт Е К Алгоритм сжатия и восстановления изображений с пирамидально-рекурсивной структурой данных // СП5ГТУ. - СШ., Дэп.,в ВИНИТИ 11.02.93, N 350-В9& '

- 10 с.

3. Фахми Ш-, Шах. Е Е , Шидт Е К. Аналитическая модель для оценки степени сжатия информации об опорных точках/Лйтоды и аппаратно-программные средства цифвовой обработки сигналов.

- СШ., 1993. - N 1. - С. 40-45.

4. Фахми HL, Шах Е Е. Алгоритм сжатия изображений с предсказанием по ОТ // Материалы 46-ой научно-технической конференции. - JL , 1991. - С. 60-61.

5. Фахми UL, Шах Е Е Сжатие изображений по опорным точкам // Материалы 47-ой научно-технической конференции. - JL ч 1992. - С. 59.

6. СЕахми Е Кодирование и декодирование полутоновых изображений методом разбиения на треугольники // Материалы 48-ой научно-технической конференции. - С-Пб. t 1993. - С. 91-92.

7. Фахми Ш., Шах Е Е , Шидт Е К. Алгоритмы сжатия и восстановления изображений методом деления на треугольники // Изв. СПб. электротехн. ун-та, 1993. - Вып. 448. - С. 5-15.