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

санкт-петербургский государственный институт точной механики и оптики (технический университет)

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

матвеев юрий николаевич

параллельно-конвейерные: процессоры

фильтрации изображений

зциальность 05.13.05 - Элементы и устройства вычислительной

техники и систем управления

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

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

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

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

Очин .Евгений Федорович

Официальные оппоненты: доктор технических наук профессор

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

Банков Владимир Дмитриевич Кокаев Олег Григорьевич Кухарев Георгий Александров

Ведущее предприятие: Санкт-Петербургский Институт Информатики и Автоматизации Российской ' АН (СПИИА РАН)

Защита диссертации состоится "12-" 1995 г

в часов на заседании специализированного совет

Д 053.26.02 при Санкт-Петербургском Государственном Институте Точной Механики и Оптики по адресу: 197101. Санкт-Петербург, ул. Саблинская 14.

С диссертацией можно ознакомиться в библиотеке институ

Автореферат разослан ^ШЛОО/уо^ 1994 р.

Ученый секретарь-специализированного совета Д 053.26.02 д.т.н.. профессор А.В.Ушако

общая характеристика работы

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

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

предъявляются к алгоритмам, "удобным" для реализации в СБИС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- разработан базовый набор параллельно-конвейерных алгоритмов цифровой фильтрации изображений:

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

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

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

На защиту выносятся :

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

2. Классификация параллельно-конвейерных алгоритмов 'цифровой фильтрации изображений.

3. Параллельно-конвейерные алгоритмы цифровой фильтрации изображений.

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

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

Апробация работа. Основные положения и результаты ис-

следований по теме диссертации докладывались, и обсуждались на Всесоюзной конференции "Обработка изображений и дистанционные исследования" (Новосибирск. 1984), • Всесоюзной конференции "Микропроцессорные системы" (Челябинск, 1984), II Всесоюзной конференции "Методы и средства; обработки сложной графической информации"(Горький; 1985). Всесоюзных конференциях "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов" (Рига. 1983. 1986 и 1989), IV и V Всесоюзных школах-семинарах "Распараллеливание обработки информации" (Львов, 1983 и 1985), VI Всесоюзной школе-семинаре по оптической обработке информации (Фрунзе, 1986), краткосрочном семинаре- ЛДНТП "Системы цифровой обработки' сигналов" (Ленинград. 1988), III Всесоюзной конференции "Автоматизированные системы обработки изображений "'(Ленинград,' 1989),'II Всесоюзной конференции по оптической обработке информации (Фрунзе, 1990), Latvian Signal Processing International Conference (Riga, 1990), Межрегиональной семинаре "Системы цифровой обработки и анализа изображений" (Рига, 1991), конференции "Проблемы создания систем обработки, анализа и понимания изображений" (Ташкент. 1991), Международной выставке - семинаре IMPROGRAPH'92 (Москва, 1992). а такж'е на предприятиях и учебных заведениях России и Болгарии.

рцедрение результатов. Результаты проведенных исследований нашли практическое внедрение в сдедуквдх разработках, выполненных при участии автора (ответственный исполнитель) в соответствии с тематическими планами работ кафедры вычислительной техники ГИТМО:

- конвейерная мультимикропроцессорная система обработки видеоинформации (1983-1986 г.г. - п/я Р-6681, Ленинград);

- процессор обработки изображений (1987 - 1991 г.г. -п/я Р-6681, Ленинград);

- система технического зрения робота - манипулятора (1989-1990 г. г. - ВМЭИ им. В.и.Ленина. Пловдив,. Болгария);

- макет аппаратуры ввода оптического изображения в ПЭВМ (ЛИТМО, 1991-1992 г.г.);

-' система обработки и анализа изображений (1993-1994 г.г. - ОКБ "Омега", Новгород).

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

бот, защищены авторскими свидетельствами. За разработку функционального модуля двумерной медианной фильтрации -и скользящей эквализации гистограмм в составе разработанной в ЛИТМО аппаратуры динамической регистрации и обработки изображения с фотоприемным модулем на базе ПЗС в 1986 г. получена бронзовая медаль ВДНХ.

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

рубликациц. Основное содержание диссертации изложено в 68 работах, включая 17 авторских свидетельств.

ртруктура и объем работы. Диссертация состоит из введения. шести глав, заключения, списка цитируемой литературы. Она содержит 288 страниц машинописного текста, 104 рисунка и 8 таблиц. Список литературы включает 192 наименования.

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

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

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

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

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

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

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

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

В диссертации предлагается обобщенный цифровой фильтр

вида

М N

У1.3 " (+)„ *1-.,1.В (X) . (1)

т—и п—я

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

В случае линейной фильтрации (ЦДС) имеем:

М N ММ а (х) Ь а а • Ь. (+) (+).«! I ш—М ш—М п—N

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

М И U N

а) дилатация а (х) b з а + Ь, (+) (+) = гсах шах

m=-H n=-fi га=—М п=-Н

М ' N М Н

б), эрозия а (х) Ь в а - Ь. (+) (+) з min min

го=-М n=-N т=-М n=-H

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

М N И Н

а) дилагация а (х) b » а П Ь, .(+) (+) * и и

ш=-М n=-N m=-M n=-N М N М N

б) эрозия а (х) b е а П Ь, (+) (+) в п П

m=-M п=-И т=-М n=-N

Другим примером нелинейного фильтра являются операции клеточн Я логики:

- _ _ М N ' М N а (х) b н а П Ь. (+) (■<•) = и U ш=-М n=-ii ш=-М n=-N широко используемые для обработки бинарных изображений.

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

R чисел n1.....пг.....nR . в качестве которых наиболее часто

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

- и -

анализатора~произвольна, а окрестность линейного фильтра состоит из одного элемента, то имеем: у1>3 - пг. т.е. линойный фильтр вырождается в тождественный преобразователь. Если в качестве пг выбрана г-я порядковая статистика (г-й наименьший, элемент, элемент с рангом г), то такой нелинейный Фильтр принято называть ранговым фильтром. В качестве пг Может быть выбран ранг центрального элемента в окне фильтрации. Нелинейный фильтр в этом случае выполняет операцию скользящей эквализации гистограмм, причем, если у,,3 - (пг), то такой фильтр выполняет операцию скользящей модификации гистограмм, где { - некоторое табличное преобразование.

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

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

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

М N

У!., - 2 2 Хю.лч.г'^.п. <2)

ш—М п—N

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

В линейном конвейере все величины, являющиеся входными для данной ступени конвейера, . являются выходными величинами предыдущей ступени конвейера. При реализации операции одно-или двумерной свертки в качестве линейного конвейера используется структура процессора скалярных произведений, где первую ступень конвейера образуют с=(2М+1)х(2Н+1) умножителей, с помощью которых вычисляются все произведения х^,З.п№т.п-Эти произведения суммируются в последующих 1оегС ступенях, образующих конвейерную древовидную сеть сумматоров. Основным недостатком такого подхода является необходимость включения в состав процессора ЦДС видеопамяти, обеспечивающей в каждом такте выборку фрагмента изображения размером (2М+1)х(2М+1) отсчетов, а также сложность наращивания конвейера (древовидной сети, сумматоров) при увеличении размеров ядра свертки.

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

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

Параллельно-конвейерные алгоритмы ЦДС. основанные на использовании группы линейных или ортогональных вычислительных конвейеров, обеспечивают:

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

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

- регулярность и наращиваемость структуры процессора. Преобразуем'(2). выделив основные этапы вычисления ЦДС:

умножение отсчетов на весовые коэффициенты

Рг.з.т.» - »«.в-Х1-.г . т " -и. м- 11 ■ -И. м: (3)

суммирование по индексу п

N ' _

31.3.ш " I ».П - Ш —«. М; (4)

П=—N

суммир'ование по индексу гп

М

У1.л - 2 и (5)

т=—М

Для получения различных алгоритмов вычисления свертки (2) один из индексов Г или 1" в (3)-(5) заменяется на 1-т, другой - на 1, а соответственно один из индексов или заменяется на ¿-п. другой - на В зависимости от того, как именно заменяются индексы, можно получить один из четырех алгоритмов■(алгоритмы 1-4 в табл. 1).

Изменив порядок суммирования в выражении (1), его можно переписать, аналогично-(4) и (5), в виде:

31,3.п - * „ Р1-.Л,.,. . П - ЧПГ: (6)

ГП—М

N

У1.3 " * 3[.г.„. (7)

п—N

Заменяя в (3), (6) и (7) индексы 1'. 1", Д*, 3" аналогично изложенному выше, можно получить еще четыре алгоритма вычисления ЦДС (алгоритмы 5-8 в табл. 1).

Анализ данных таблицы показывает, что алгоритмы 1 и 5, 2 и 7, 3 и 6, 4 и 8 попарно эквивалентны (отличаются только направлением сканирования изображения). В зависимости от

Таблица 1. Характеристики конвейерных алгоритмов цифровой двумерной свертки

N . п вид И размер Фрагмента изображения Б (Б*) ал-гориТМ V 3 ал-гориТМ

1 *» , «Л -[ «.З-П Матрица <2М+1)Х (211+1) 2, л N 2 С« п—N .3 т. 11 Лин м 2 в!. т—М 3 . т Лин

2 Строка 1Х(2М+1) з, 3 К п—N .л II. п Лин м X Б,. т—м т . 3. т Орт

3 Столбец (2М+1)х1 N. н1 П—М . з -п, п. п орт м I 84 ш—М . ш Лин

4 "Л . »1X1 . д Отсчет .1X1 3 И 2 5' п—N . 3 -п, к п орт н ш—М' № . 3 . т орт

5 ^т.пх1- в.л -п Матрица (2М+1)х (2Н+1)- 1 м »- 2 р, Ю—М . л т, п Лин N 2 Б; П—N 3 . т Лин

6 «е.«XI. 1-п Строка 1Х(2И+1) 81 1 м 2 с» ш—М Г ч 3 . II п Орт N I Б; п—N 3 . т Лин

7 Столбец (2М+1)х1 Б; 1 М п" * Р1 " т—М . л. и Лин К 2 Б; 11—N 3 -п. го орт

8 Отсчет 1 XI 3 ь »■2 С» т—м -и .3 . т п орт n £ б; п—N 3 -п, т Орт

значений Г. ;Г 6 (3) определяется способ комбинирования входных отсчетов 'и весовых коэффициентов при умножении, а следовательно, вид фрагмента входного изображения. Суммирование произведений .в соответствии с (4) или (6). т.е. вычисление результатов одномерной свертки, выполняется одновременно для Есех 2М+1 строк (4) или всех 2К+1 столбцов (6) ядра ЦДС. В зависимости от вида индексов в (4) и (6) суммируются произведения , Формируемые параллельно . в одном такте

при, например, 1 га= 2 Рх Л й п. или произведения, форми-

п=-Н ' N

руемые последовательно при, например. 3 го * I Рх }.п т „.

п=-Н

В первом случае естественной формой реализации вычислений •

будут линейные конвейеры, во втором - ортогональные. Вычисление У!,.) выполняется суммированием соответствующих результатов т или Б^.з.п одномерных сверток (5) или (7). Если Э^.п, О'!.;,.„) формируются одновременно, то для вычисления у1>3 можно использовать линейный конвейер, если же ^.¿.т Формируются в различные моменты времени, то

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

Таким образом, для реализации каждого из четырех сущест-ственно различных параллельно-конвейерных алгоритмов-ЦДС на первом этапе вычисления используются 2М+1 или £N+1 линейных или ортогональных конвейеров одномерной свертки, а на втором этапе - один линейный или ортогональный конвейер суммирования. Это позволяет получить 16 базовых реализаций параллельно-конвейерных алгоритмов, на основе которых, задавай конкретные алгоритмы, структуры линейных и ортогональных конвейеров свертки и суммирования, можно создать большое число различных структур процессоров цифровой Двумерной свертки.

Далее в главе разрабатываются Параллельно-конвейерные шгоритмы ЦЦС для метода распределенной арифметики, основан-

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

р.-1 М К У!,, - х2 2Г I ^.^-«^..гЛ,». (8)

г-1 т—М п—N

где ^-т.з-п.г е {0. 1) - г-й разряд элемента

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

Использование параллельно-конвейерных алгоритмов позволяет сократить объем памяти ЗУ таблиц и уменьшить объем выборки данных из видеопамяти. Запишем (8) следующим образом:

Рх-1 N ! М 1

У!., - "Г 2Г I I »..«•*!-».з-п.Г • (9)

г-1 П—N V ш=-М )

при этом значение суммы в скобках определим 'сТгемощыо таблиц сложения. Для этого сформируем 2Н+1 таблиц Тп. состоящих из 22Нстрок. ■ Тогда выражение (9) можно переписать следующим . образом:

Ри.г.л " Т?.3.г • (Ю)

N

5».л.г - 2 Р^-п.г.п . (11)

п—N

у1>3 = . (12)

Г-0

При параллельной вычислении ЦДС по выражениям (10)-(12) ис-

пользуется рх копий таблиц. Выражение (11) описывает алгоритм ортогонального конвейера, а (12) - линейного конвейера.

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

При реализации операции ЦДС по алгоритмам 1 или 5 (табл. -1) в качестве линейного конвейера используется структура процессора скалярных произведений (ПСП), где вычисляется скалярное произведение двух входных векторов Х0 *• [xg] и Щ - [wg]:

G-1

Р - I vxg. (13)

g=0

и могут использоваться для вычисления ЦДС (2), если один из входных векторов составить из весовых коэффициентов ядра свертки. упорядоченных, например по столбцам w<2mm )<m»M)*n.N = Vn • а Другой вектор - из соответственно упорядоченных отсчетов фрагмента изображения

Х(2М*1)(m+M )+n*N " х1-т.3-п-

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

Р - Ic Sc , (14)

где Sc » Хс■WB, ■ - поэлементное умножение. Xs - txe], Wc -Cwg], s0 - [se] - вектор-столбцы элементов изображения, весовых коэффициентов и результата поточечного умножения соответственно, а 15т единичная вектор-строка размерности Q. В свою очередь, выражение (15) переписывается в виде:

гт

где 1С)1- единичные вектора размерности С„, 11-1, Н, в - Снх С.н_,х.. .хй,; матрица Гс[снхсн. 1х...хС!] - многомерное представление столбца Бе[в]. Обозначим

Fh - I^Fj., . h - 1. H . (F0 - fB).

тогда Р ■= Рн и вычисление (15) можно ■ организовать в виде конвейера из Н+1 ступеней. На нулевой ступени конвейера вычисляются в произведений входных данных на весовые коэффициенты. На П-й ступени (11 - 1.....Н) вычисляются

малоточечных сверток Fh размерности Gn (RH = 1). Размерность входного массива данных для h-й ступени равна F.h-i.

Аппаратно О-ступекь 'конвейера можно реализовать в виде линейки из G/S0 умножителей, а h-ступень - в виде линейки из Rh Бц-входовых сумматоров, каждый из которых вычисляет свертку Fh. При параллельном вычислении значения S0=l и Sn = Gh, а при последовательном - S0 - и Sh = 2. В результате, время вычисления одного значения свертки (15) Тцдс » rr.ax{Th), h = 0,1.....H, где Т0 = S0tx - время умножения вх.дных данных на весовые коэффициенты, Th = S1tCJlh.- время вычисления свертки Fh , tCJlh - время сложения рЛ-разрядных чисел, где

Ph = Рл-i ♦ floggGnl - Ро + 2 FlogBG,l есть разрядность проме-

J-1

«уточных данных на h-й ступени конвейера. р0 = рх + р„.

Закаты операционных ресурсов при такой организации вычислений Qc - Qcx + Qc*. где Qcx = (G/S0).X0_-/есть затраты операционных ресурсов на реализацию умножителей. к0 - число рм-разрядных умножителей, реализующих умножение' рх- и р„-

разрядных чисел, а а,■■ I йцкц есть затраты операционных ре-

сурсов на реализацию Бц-входовых сумматоров, где к„=|р„/р^-

число р#-разрядных сумматоров, реализующих сложение рп-

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

На основе-представления (15) в главе предлагается алгоритм, синтеза структур линейных конвейеров, реализующих операций скалярного произведения (13) в зависимости от заданных

♦

Н

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

Алгоритмы вычисления ЦДС в ортогональном конвейере (алгоритмы 4 и. 8 в табл. 1) позволяют использовать каждый эле-:ент изображения для вычисления нескольких элементов свертки [, следовательно, значительно упростить (по сравнению с ли-[ейным конвейером) обмен данными между процессором свертки и !У изображения.

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

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

)

У1.3-Я

Ч З-Н )

той Ь

+ Б

<3-Н) тоа I.' 0;

це ли

>1 . 3*11. ( З+П)

1. 3 «II. ( 3 *п ) !ЛО(1 1«

М

1 = 1

ш—М

п ■» -н. N

1-п,з'мв1,(з»п) той 1.

(16)

- 0;

зе

н -1

^■а ~ г*., Ь.з-и '

.3 «Н . п

+ э

1 .;)♦« .1

-М, N

ип

и 2

п—М

X,-

1-ш,3 .п

журрентные соотношения (16) описывают движение в конвейере )тока весовых коэффициентов ядра свертки, а рекуррентные ¡отношения (17) - потока частичных результатов. Б приЕеден-к рекуррентных соотношениях индекс п является пространс-¡енным. а индексы 1 и J - временными (в общем случае их ро-[ могут поменяться). В зависимости от способа реализации

п

вычислений сумм З^.,,, индекс га может быть временным (при . последовательном вычислении) или пространственным (при параллельном вычислении). Кроме того, поскольку разность между пространственными индексами в соотношениях (16)-(17) меньше или равна 1. то эти алгоритмы имеют локальный тип.

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

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

В ортогонально-линейных конвейерах используются алгоритмы 3 и 6 (табл. 1) вычисления ЦДС. где одномерные свертки (4) или (6) вычисляется последовательно или параллельно в ортогональном конвейере, а суммирование частичных результатов (5) или (7) производится параллельно в линейном конвейере. В диссертации проведен анализ структур ортогонально-ли-кейных конвейеров ЦДС и предложена новая структура, где для . снижения затрат оборудования'используются особенности коэффициентов ядра свертки: кратность коэффициентов степени двойки, симметричность ядра свертки относительно одной или обоих осей. Кроме того, в диссертации предложена структура ортогонально-линейного процессора ЦЦС с обработкой по разрядным срезам столбцов данных, где в ортогональном конвейере вычисляется ЦДС разрядных срезов, а в линейном - суммирование полученных частичных результатов с учетом их весов..

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

Одноканалькые структуры обеспечивают Бремя преобразования, пропорциональное размеру окна фильтрации. В главе предложена одноканальная структура, удобная при реализации на стандартных микропроцессорных комплектах, например, МПК К1804, позволяющих легко реконфигурироввть параметры свертки (размеры окна фильтрации, разрядность элементов данных и весовых коэффициентов). В предложенной структуре используется набор регистров (РЗУ) для хранения промежуточных результатов гп. причем для вычисления ЦДС используются рекуррентные соотношения (16), поскольку, в отличие от рекуррентных соотношений (17), в этсм случае не требуется сдзига частичных результатов между регистрами РЗУ.

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

Реальный масштаб времени (т.е. время преобразования, пропорциональное периоду следования отсчетоЕ изображения) для большинства приложений обеспечивают только двумерные параллельно-конвейерные структуры процессоров ЦДС.

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

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

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

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

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

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

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

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

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

рь = б""1 +

Я-Ч

ь - 1

2Гь"гь-1

Нь1.3.„ >

Ь-1.....В.

(18)

де Р0=0. 3°=0. бь = Рь - Н"; Нь - мультигистограмма

формированная по Гь старшим разрядам.отсчетов фрагмента зображения, попавшего в окно фильтрации; В - число мульти-истограмм; = - результат фильтрации.

В диссертации разработаны рекуррентные соотношения для ультигйстограммного алгоритма СЭГ (по четным отсчета» муль-игистограммы):

Б0 - О;

-«ь

» X,

Ь-1

ь _

Б"

= Хц-2

2ь-1

- 0;

/ь-Рь-!. -Рх+^ь

X В-1 Б"" + Х«2

1.4'

если если чь

У1.1

К-(5В + П1-3,Хц) + с;

к Ц '

(19)

ТГв

[е Хц" - число, состоящее из Г„ старших разрядов централь-го элемента обрабатываемого фрагмента изображения. Анало-чным образом можно записать рекуррентные соотношения для льтигистограммного алгоритма СЭГ по нечетным отсчетам.

=1

Временная сложность мультипрограммных алгоритмов РФ и СЭГ равна

/В Fb-F„., ft> 2Б(2М+1) + <[ I (2 - 1)] + 1

операций типа сложения. Распараллеливание вычислений по алгоритмам (18)-(19) достигается за счет одновременного формирования и обработки В мультигистограмм.

Максимальное распараллеливание алгоритмов РФ и СЭГ возможно при отказе от последовательной по своей природе операций формирования гистограмм. Так как локальная гистограмма фрагмента и соответствующее локальное преобразование используется для преобразования только одной точки изображения, тс это позволяет отказаться от явного определения гистограммь фрагмента изображения. Математически процедуру формирование гистограммы фрагмента можно описать как усреднение б-функци» Кронекера:

hi.'i.i - "„ 2 a(l-x,_BiJ_B). 1 « 0.1.....R-l. (20)

m«—M n»-N

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

1 IHK

chi.i.i " JM.i.i - i 2 u 6(r - x,.Bi3.B) -

r="0 r-0 ю—M n—N

м К

-SS • (XJ...J-,, < 1) . (21) m~M n—N

1 i o, Xt.B j.B > l:

ГДе 4P(Xt-m.д-n < 1) -Дв(Г " xi-».3-n) " . v ' . ..

" r-U II, Xj.n.j.n s i,

и операцию формирования мультигистограмм

' М N.

пй«,.а.1 - Z l 5(1-2-4 _ х,.я. j-n '2"4) •• m—M n=-N

Кз определения операции ранговой фильтрации следует,

что результат фильтрации есть число у13 - удовлетво-

ряющее следующему неравенству:

кГ" ■ и М «in

Г Vs. Г " £„ < R? " ) > rank. (22)

г»0 ш—М n—N

В результате, параллельный алгоритм РФ описывается о помощью следующих рекуррентных соотношений: Рх-1

1=0; г - 2 ; если chtiJ<1»r., < rank, то 1-i+r:

г = г/2; '

Ух.з = chli3il;

-де рх - разрядность элементов изображения.

Параллельный алгоритм СЭГ получается следующим образом. )перация СЭГ выполняется по формуле;

y,.j - [(v-d/g vht.j.jj. (23)

Ру

1де V = 2 - число уровней яркости преобразованного изобра-<ения. Подставляя (20) в (23). получим

Vi.J-

I (V-D/G Z X < xli3)l

L m—M n=-!í J

(24)

ice известные ранее алгоритмы СЭГ реализуют преобразование 24), которое требует выполнения последовательной по своей [рироде операции формирования гистограмм фрагментов изобра-;ения. Преобразование (23) эквивалентно преобразованию (24), даако важной особенностью последнего является отсутствие :еобходимости построения гистограмм и, следовательно, воз-южность распараллеливания вычислений. На основе представлена (24) в главе разработаны алгоритмы СЭГ для реализации в атричных и. систолических структурах.

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

морфологической фильтрации можно использовать алгоритмы ранговой фильтраций при значениях рангов гапК=1 (эрозия) и гапк-й (дилатация).

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

а„ I ' 3'

(25)

1, если Х!,3»а и х^^.д-Ь. |1-т|<1. Н-п|<.1; О, в остальных случаях.

Из анализа выражений (22), (24) и (25) следует, что операции ранговой фильтрации, скользящей эквализащм гистограмм и Формирования гистограмм второго порядка (ФГВП) также можно свести к обобщенному виду (1) при замене двуместной (х) и многоместной (+) операций следующим образом:

МЫ м к

операций РФ и СЭГ: а (х) Ь » <р(а < Ь). (+) (+) = I 1

га=-М п—К т=-М

13 13

операция ФГВП: а (XI Ь > ^(а.Ъ), (+) (+) * I I

- ^ 1=-1 ^

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

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

Разрабатываются мультипрограммные процессоры РФ и СЭГ с распределенной памятью гистограмм, параллельно-последовательные и паралле..ьно-конвейерные. На основе проведенных, исследований делаются следующие выводы: при малоразрядных данных (р„ < 8) оптимальной с точки зрения аппаратно-временных затрат является двух-канальная параллельно-последовательная структура; при большой разрядности данных оптимальной с течки зрения аппаратно-временных затрат является рк-канальная

[араллельно-последовательная структура; при обработке изобретай в реальном масштабе времени основным вариантом являйся параллельно-конвейерная структура.

Используя представление (24). разрабатываются принципи-.льно новые параллельно-конвейерные структуры процессоров 'ЭГ. Основываясь на приведении операции СЭГ к обобщенному ¡иду. для разработки структур процессоров применяется тот же :одход. что к для операции ЦДС. Рекуррентные соотношения для :араллельного алгоритма СЭГ имеют тот же вид. что и рекур-ентные соотношения (16)-(17) для ЦДС с учетом замены опера-,ии умножения на операцию в (24) и замены движени.. потока есовых коэффициентов ядра свертки на движение потока цент-альных элементов фрагментов.

Разработаны одномерные (ортогональные) и двумерные (ли-ейные. ортогональные, линейно-ортогональные и ортогональ-о-линейные) структуры процессоров СЭГ. Из проведенного в лаве анализа следует, что среди одномерных конвейеров СЭГ ля размеров окна фильтрации < 32 наименьших затрат оборудо-ания требуют ортогональные конвейеры, а в остальных случаях мультипрограммные. Среди двумерных конвейеров СЭГ наи-учшим вариантом является линейно-ортогональная структура с вижениём потока частичных результатов. Параллельно-конве-ерный мультипрограммный процессор СЭГ зсегда требует наи-ольших затрат оборудования. Кроме того, ' такие недостатки той структуры, как довольно сложный алгоритм взаимодействия этоков данных и команд, большое время разгона конвейера, а акже большая номенклатура используемых операционных элемен-эв, делают предпочтительном выбор разработанных в данной паве линейно-ортогональных' и ортогональных конвейеров СЭГ.

Общность параллельно-конвейерных структур процессоров 1С, РФ, СЭГ позволяет синтезировать универсальные ПЭ и ис-зльзовать единые структуры связей .ПЭ в конвейерах. В ка-зстве примеров производится разработка обобщенных парал-зльно-конЕейерных процессоров фильтрации: процессоров РФ'и ЭГ (двумерный линейный конвейер), процессоров ЦДС, - СЭГ у. {Г (одномерные ортогональные конвейеры) и на их основе про-зссора выделения контурных признаков.

Далее в главе разрабатываются параллельно-конвейерные

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

Показывается, что среди параллельно-конвейерных процес соров' МФ и ОКЛ наилучшим с точки зрения аппаратных затрг является . линейно-ортогональный конвейер. Кроме наименыш-затрат оборудования при наименьшем периоде работы, эт структура удовлетворяет требованиям регулярности и модульнс наращиваемости. Отмечается, что для реализации процессоре МФ и ОКЛ с малыш размерами окна фильтрации (до 4x4), целе сообразно использовать стандартные БИС ЗУ, емкость которых этом случае достаточна для хранения таблицы преобразования.

Среди процессоров ФГВП наименьших затрат оборудовав требует одноканальная структура, удобная для построения а} селераторов на базе стандартных МПК. Для формирования гис тограмм . второго порядка в реальном масштабе времени опта мальной является параллельная ортогонально-линейная структ} ра, обеспечивающая наилучшее соотношение аппаратно-временнь затрат.

В шестой главе проводится экспериментальное исследовг ние разработанных алгоритмов и структур процессоров. Привс дится описание йакетов моделирования операций фильтрации, также экспериментальной вычислительной системы обработа изображений в состав которой входят процессоры ЦДС, РФ СЭГ. Показывается, что результаты макетирования подтверди полученные оценки затрат оборудования и быстродействия ра: . работанных процессоров.

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

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

Основные результаты работы можно разбить на три групш

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

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

локальности.

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

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

обобщенному Еиду.'

4. Выполнено приведение операций морфологической филь-рации и операций клеточной логики к обобщенному виду.

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

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

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

6. Разработан базовый набор параллельно-конвейерных ал->ритмов и структур процессоров реализации обобщенной опера-!И. цифровой фильтрации: линейные, орто. ональные, линей-|-ортогональные и ортогонально-линейные.-

7. Исследованы алгоритмы и структуры процессоров ЦДС и едлотеи ряд новых структур:' одноканальные и одномерные ор-гональнке конвейеры: двумерные линейно-ортотональные и ор-гонально-линейные конвейеры, в том числе использующие ойстза симметричности ядра свертки; разрядко-срезовые кон-йеры с ортогснально-линейкой структурой

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

9. Предложены и исследованы принципиально новые пара; лельно-конвейерные алгоритмы и структуры процессоров скол1 зящей эквализации и модификации гистограмм. На основе эта алгоритмов и структур разработаны обобщенные параллельнс конвейерные структуры процессоров ЦЦС, РФ. СЭГ и СМГ.

10. Проведено исследование и предложен ряд новых пара; лельно-конЕейерных алгоритмов и структур процессоров морфе логической фильтрации и операций клеточной логики.

' И. Предложены и исследованы принципиально новые пара; лелько-конвейерные алгоритмы и структуры процессоров форм} рования гистограмм второго порядка бинарных изображений.

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

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

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

14. Разработан алгоритм синтеза структур процессор! э зависимости от заданных ограничений на скорость обработга быстродействие элементной базы и размер окна фильтрации:

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

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

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

1. Майоров С.А., Матвеев Ю.Н., Очин Е.Ф. Анализ метода Винограда для вычисления дискретного преобразования Фурье 2П-точечных последовательностей // Автоматика и вычислитель-чая техника. - 1982. - N 2. - С. 77 - 80.

2. Майоров С. А.. Матвеев Ю.Н., Очин Е.Ф. Принципы построения реконфигурируемого клеточного автомата предваритель-10й обработки изображений // Тезисы докладов Всесоюзн. конф. 'Методы и микроэлектронные средства цифрового преобразования I обработки сигналов". - Рига:ИЭВТ ЛАН, 1983. -Т.2. -С. 189-193.

3. Денисов В.М., Матвеев Ю.Н., Очин Е.Ф. Принципы орга-шзации систем обработки изображений на базе клеточной логи-си // Зарубежная радиоэлектроника. - 1984. - ПЛ. - С. 3-25.

4. Денисов В.М.. Матвеев Ю.Н., Очин Е.Ф. Выполнение »пераций клеточной логики в реконфигурируемом клеточном ав-'оиате // Деп. в ЦНИИТЭИ приборостроения 03.04.84, N 2405пр.

■ 84 Деп. - 9с.

5. Матвеев Ю.Н.. Очин Е.Ф. Принципы построения конвейерного клеточного автомата с произвольной траекторией скани-ования изображения // Известия вузов СССР. Приборостроение.

1984. N 4. - С. 49 - 53.

•6. Матвеев Ю.Н.". Очин Е.Ф. Микропрограммирование сколь-ящей эквализации гистограмм в мультииикролроцессорной сис-еме на базе МПК серии 1804//Материалы Всесоюзн. конф. "Мйк-опроцессорные системы". - Челябинск: ЧПИ.1984. - С. 228-229.

7. Матвеев Ю.Н., Очин Е.Ф. Нелинейное преобразование идеосигнала на основе алгопитма скользящей эквализации гис-ограмм // Тезисы докладов Всесоюзной конференции "Обработка зображений и дистанционные исследования" - Новосибирск: ИАЭ О АН СССР, 1984. - Ч. 1. - С. 29 - 31.

8. Донченко С.Е.. Кучеренко K..:i., Матвеев D.H., ' Очин . Ф. Алгоритмы выполнения свертки и зквализации гистограммы зумерных сигналов в специализированных БИС // Тезисы дома-зв V Всесоюзной школы-семинара "Распараллеливание обработки формации". - Львов: ФМИ АН УССР. 1985. - Ч.З. - С. 27-28.

9. Матвеев Ю. Н.. Очин Е. Ф. Параллельный алгоритм еычис-;ния двумерной свертки на ссноЕе многоуровневой дельта-мо-

дуляции // Там же. - 4.4. - С. 66-67.

10. Матвеев Ю.Н., Очин Е.Ф. Нелинейное преобразоваш видеосигнала на основе алгоритма скользящей эквализации гис тограмм // Известия вузов СССР. Радиоэлектроника. - 1985. N 1. - С. 81 - 82.

11. Матвеев Ю.Н., Очин Е.Ф. Структура устройства мод1 фикации гистограмм изображений // Тезисы докладов II Всесс изной конференции "Методы и средства обработки сложной грг фической информации". - Горький: ГГУ, 1985. - С. 320.

12. Донченко С.Е.. Королев А.Н., Матвеев Ю.Н.. 041 Е.Ф. Проектирование процессоров свертки двумерных сигналов переменными и адаптивными ядрами преобразований // Деп. ЦКИИТЗИ приборостроения 22.07.85, N2994 пр. - 85 Деп. - 19с

13. Донченко С.Е., Королев А.Н., Кучеренко К.И., Матве ев .Ю.Н.. Очин Е.Ф. Расчет основных параметров цифрового ко* вейерного видеопроцессора // Деп. в ЦНИИТЭИ приборостроеш 22.07.85, N 2995 пр. - 85 Деп. - 13 с.

14. Донченко С.Е., Клочков B.C., Кучеренко К.И., Матв« ев Ю.Н. и др. Конвейерная мультимикропроцессорная систе» обработки видеоинформации : Под рук. Е.Ф.Очина // Отчет i НИР N Гос. реГ. У09794. - Л.': ЛИТМО, 1986. - 68 с.

15. A.c. 1188754 СССР. МКИ G 06 F 15/36 // Устройст! для построения гистограмм / Кучеренко К.И.. Матвеев Ю.Н. Очин Е.Ф. - Опубл. 30.10,85, Бюл. К 40.

16. A.c. 1196871 СССР, МКИ G 06 F 11/00 // Устройст! ДЛЯ цифровой двумерной свертки / Кучеренко К.И., Матве( Ю.Н. . ОЧИН Е.Ф. - Опубл. 07.12.85, Бюл. Н 45.

17. A.C. 1196898 СССР, ' МКИ G 06 F 15/36 // Устройст! для обработки данных гистограмм / Кучеренко К.И., Матве( Ю.Н.. ОЧИН Е.Ф. - .Опубл. 07.12.85, Бюл. К 45.

' 18. А. о. 1262527 СССР, МКИ G 06 F 15/66 // Устройст! пара."пельной обработки видеоинформации / 'Кучеренко К.И Матвеев Ю.Н., Очцл Е.Ф. - Опубл. 07.10.86. Бюл. К 37.

19. Клочков B.C. , Кучеренко К.И., Матвеев Ю.Н., Очз Е.Ф. Принципы организации параллельно-последовательного.ци-рового видеопроцессора //Ред. журн. "Электронное моделиров; ние". - Киев: 1986. - 16 с.: Деп. в ВИНИТИ 07.05.86, N3316-81

20. Кучеренко К. И., Матвеев Ю.Н., Очин Е.Ф. Систоличе!

:ий алгоритм скользящей эквализации гистограмм многоуровне-:ых изображений // Материалы VI Всесоюзной школы-семинара по штической обработке информации. - - Т>оунзе: "ИЛИМ", ^Эвб. -118 - 119.

21. Донченко С.Е., Матвеев Ю.Н.. Очин Е.Ф.. Романов I. Ф. Цифровая свертка на основе многоуровневой дельта-моду-¡яции с логарифмическим компандированием // Тезисы докладов ¡сесоюзной конференции "Методы и микроэлектронные средства ;ифрового преобразования и обработки сигналов". - Рига: ИЭВТ АН, 1986. - Т. 1. - С. 165 - 167.

2Л. Матвеев Ю. Н.. Очин Е.Ф. Выполнение операции сколь-ящего выравнивания гистограмм изображений в однородных труктурах и средах // Там же. - Т. 2. - С. 519 - 522.

23. A.c. 1264309 СССР.МКИ Н 03 Н 17/06, G 06 F 15/353 // стройство для цифровой двумерной сЕерткИ/Донченко С.Е., Ку-еренкоК.И., Матвеев Ю.Н. и др. - Опубл. 15.10.86, Бил.N38.

24. A.c. 1312614 СССР, МКИ G 06 F 15/36 // Устройство ля локального выравнивания гистограмм /Донченко С.Е., Куче-енко К.И.. Матвеев Ю.Н. и др. - Опубл. 23.05.87, Бюл. N 19.

25. Донченко С.Е., Матвеев Ю.Н.. Очин Е.Ф. Принципы ор-анизации параллельных процессоров цифровой свертки изобра-ений //Зарубежная радиоэлектроника. - 1987.- N7.- С. 84-102.

'26. Клочков B.C., Матвеев D.H., Очин Е.Ф., Романов Ю.Ф. пециализированные процессоры цифровой обработки изображена: алгоритмы и структуры // Известия вузов СССР. Приборо-троение. - 1987. - Т. 30. - N.9. - С. 57 - 64.

27. Королев А.Н.. Матвеев Ю. Н.. Очин Е.Ф. Параллельяо-энвейерные процессоры цифровой свертки ортических изображена // Труды ГОИ. - 1987. - Т. 64, Вып. 198. - С. 70 - 76.

28. Матвеев D.H., Очин Е.Ф. Выполнение операции сколь-здего выравнивания гистограммы в матричном процессоре // зтометрия. - 1988. - Ü.I. - С. 14 - 17."

29. Клочков B.C.. Матвеев Ю.Н.. Очин Е.Ф.. Романов Ю.Ф. эхитектура спецпроцессоров цифровой обработки изображений * Материалы краткосрочного семинара "Системы цифровой обра зтки сигналов" - Л.: ЛДНТП, 1988. - С. 63 - 74.

30. Донченко С.Е.. Матвеев D.H.. Очин Е.Ф. Параллельно-жвейерные алгоритмы цифровой двумерной свертки изображений

// Оптическая и цифровая обработка изображений.- Л. : Наука, 1988. - С. 95 - 101.

31. A.c. 1416976 СССР. МКИ G 06 F 15/66 // Устройство для параллельного вычисления цифровой двумерной свертки / Донченко С. Е., Кучеренко К. И.. Матвеев Ю. Н.. Очин Е.Ф. -Опубл. 15.08.88. БЮЛ. H 30.

32. A.c. 1451694 СССР. МКИ G 06 F 11/00. 15/332 //'Устройство для цифровой двумерной свертки / Кучеренко К. И.. Матвеев Ю.Н.. Очин Е.Ф. - опубл. 15.01.89, Бюл. N2.

33. А.с. 1474675 СССР. МКИ G 06 F 15/36, 15/62 // Устройство для скользящей эквализации гистограмм / Кучеренко К. И,, Матвеев Ю.Н., Очин Е.Ф. - Опубл. 23.04.89, Бюл. N 15.

34. A.c. 1517040 СССР, МКЙ G 06 F 15/36 // Устройство для _ анализа распределений случайных процессов / Кучеренко К. И.. Матвеев Ю.Н.. Очин Е.Ф. - Опубл. 23.10.89. Бюл. N 39.

35. A.c. 1515182 СССР, МКИ G 06 К 9/00.9/36 // Устройство дл~ логической обработки информации / Денисов В.М.. Матвеев D.H.. ОЧИН Е.Ф. - Опубл. 15.10.89, Бюл. N 38.

36. Гайшук 0. В.. Денисов В.М., Матвеев Ю. Н., Хаваев В. Т. Комплекс программ анализа изображений на основе двумерных гистограмм // Тезисы докладов III Всесоюзн. конф. "Автоматизированные системы обработки изображений". - Л.:1989.- С.52.

37. Денисов В.И., Матвеев Ю.Н. Анализ изображений с помощью двумерных гистограмм // Там же. - С. 56.

38. Клочков B.C., Матвеев D.H., Муратов C.B. и др. Комплекс цифровой обработки изображений // Там же. - С. 100.

39. Гайшук О.В.. Денисов В.М.. Матвеев Ю.Н. йспользова-■ ние двумерных гистограмм для 'анализа бинарных изображений // Тезисы докладов Всесоюзной конференции "Методы и микроэлектронике средства цифрового преобразования и обработки сигналов"! - Рига: ИЭВТ ЛАН, 1989. - Т. 2. - С. 25 - 27.

40. Денисов В.М., Матвеев Ю.Н..Выполнение операции Формирования двумерной гистограммы бинарного изображения i- однородных структурах и средах // Там же. - С. 37 - 39.

41. Dsnisov V.M., Matveyev Yu.N. Binary Image analysis uMng multidimensional histograms // Proc. Latvian Sign-;; F.ocssslng International Conference. - F;'ga: j. '.nr. ?A -Ъ'з. - А. Г. - F. :il~35.

42. Денисов В.М., Матвеев Ю.Н. Двумерные гистограммы бинарных изображений и их практические приложения // Тезисы докладов II Всесоюзной конференции по оптической обработке информации. - Фрунзе: "Илим", 1990. - С. 32 - 33.

43. Денисов В. М.. Матвеев Ю. Н.. ХаваевВ. Т. Формирование признаков, инвариантных к сдвигу, ориентации и масштабу бинарных изображений // Там же. - С. 30-31.

44. Матвеев Ю.Н. Алгоритм быстрой медианной фильтрации // Там же. - С. 31 - 32.

45. A.c. 1608692 СССР. МКИ G 06 F 15/36 // Устройство для скользящей модификации гистограмм / Матвеев Ю.Н. -Опубл. 23. 11.90, БЮЛ. N 43.

46. Денисов В.М., Матвеев Ю.Н. Формирование двумерных гистограмм изображений в матричном процессоре // Программирование. - 1990. - N. 4. - С. 87-91.

47. Денисов В.М., Матвеев Ю.Н., Очин Е.Ф. Гистограммы второго порядка бинарных изображений // Радиотехника и электроника. - 1991. - N. 1. - С. 85 - 96.

48. Денисов В.М.. Матвеев D.H., Хаваев В.Т. Классификация бинарных изображений плоских объектов с использованием гистограмм второго порядка // Известия вузов СССР. Приборостроение. - 1991. - М. 5. - С. 3-8.

49. Гайаук 0. В.. Денисов В. М.. Матвеев Ю. Н. Определение ориентации плоских объектов с использованием гистограмм второго порядка бинарных изображений // Известия вузов СССР. Приборостроение. - 1991. - N. 6. - С. ..3 - 7.

50. Возовой A.C., Гуревич O.E., Матвеев Ю. Н., Очин Е.Ф. Система ввода и обработки изображений на базе ЭВМ, совместимых с IBM PC ХТ/ AT // Труды Межрегионального семинара "Системы цифровой обработки и анализа изображений". - Рига: ИЭВТ ЛАН. 1991. - С. 23 - 24.

51. Денисов В.М., Матвеев ю.н.. Хаваев В.Т. Формирование инвариантных признаков изображений на основе гистограмм второго порядка и их применение в интеллектуальных системах // Там же. - С. 39 - 40.

52. Матвеев Ю.Н., Черемисина О.Н. Использование морфологических операций для обработки бинарных изображений // Там ге. - С. 41 - 42.

53. A.c. 1647585 СССР, МКИ G 06 F 15/36 // Устройство цифровой двумерной свертки / Донченко С.Е.. Матвеев Ю.Н., ОЧИН Е.Ф. И др. - Опубл. 07.05.91, БЮЛ. N 17.

54. A.c. 1651297 СССР. МКИ G 06 F 15/36 // Устройство для формирования гистограмм / Денисов В. М., Матвеев Ю.Н. -Опубл. 23.05.91. БЮЛ. N 19.

55. А. с. 1654848 СССР. МКИ G 06 К 9/00, 9/36 // Устройство для логической обработки информации / Денисов В.М., Матвеев Ю.Н. - Опубл. 07.06.91, Бюл. N 21.

56. A.c. 1656554 СССР, МКИ G Об F 15/36,15/66 /■/ Вычислительное устройство для ранговой фильтрации /Донченко С.Е., Матвеев Ю.Н.. Очин Е.Ф. и др. - Опубл. 15.06.91, Бюл. N 22.

57. Матвеев Ю. Н.. Черемисина 0. Н. Использование морфологических операций для определения траектории движения биологического объекта // Тезисы докладов Всесоюзной конференции "Ппоблемы создания систем обработки, анализа и понимания изображений". - Ташкент: 1991. - С. 109.

58. Кудрявцева О.Г., Матвеев Ю.Н. Алгоритм векторной медианной фильтрации // Известия вузов СССР. Приборостроение. - 1992. - N 3 - 4. - С. 37 - 43.

Подписано к печати' 29.II.S4 г. Ёаказ 177 Ткраж ИХ экз.

Объем 1,1 п Бесплатно

Ротапринт. 1Ш'Ш. I9ÜÜGI-, С.-Петербург, пер.Гривцова, 14

БАК