автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод декомпозиции алгоритмов систем технического зрения на параллельно-конвейерное программно-аппаратное исполнение в архитектуре ПЛИС-ЦСП

□03169111

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

К/л

Краснобаев Антон Александрович

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

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертация на соискание ученой степени кандидата физико-математических наук

1-4 * * * Г»

Э 14Ми ¿иНи

Москва 2008

003169111

Работа выполнена в Институте прикладной математики им. М В.Келдыша РАН

Научный руководитель - доктор физико-математических наук, профессор Платонов Александр Константинович

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

- доктор физико-математических наук Лацис Алексей Оггович

-кандидат физико-математических наук Андреев Виктор Павлович

Ведущая организация

Государственный научно-исследовательский институт авиационных систем (ГосНИИАС)

Защита состоится « » ¡Л'Уй^иА._2008 г. в // часов

на заседании Диссертационного совета Д 002 024 01 в Институте прикладной математики им. М.В.Келдыша РАН по адресу 125047, Москва, Миусская пл 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им М В Келдыша РАН

Автореферат разослан « » й/уи^Х_2008 г.

Учёный секретарь совета

доктор физико-математических наук

Т А Полилова

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

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

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

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

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

3

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

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

Цель работы

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

Научная новизна

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

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

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

• Построен формальный метод отображения алгоритмов обработки видеоданных на архитектуру вычислительных средств

Практическая значимость и реализация

Полученные методы и правила позволяют формализовать процесс построения СТЗ, минимальной по цене при заданной производительности, с эффективной реализацией требуемых алгоритмов первичной обработки видеоизображений В работе показано, что большое многообразие алгоритмов первичной обработки изображений может быть эффективно реализовано на однотипной аппаратной части в виде "рефлексного" видеодатчика, позволяющего совместить процессы получения видеоданных и их предобработки Результаты диссертационного исследования были использованы при разработке камеры с ее программируемыми откликами, на основе которой реализован сканер линейных и двухмерных штриховых кодов с разрешением 1280x1024 при частоте 30 кадров в секунду По функциональным характеристикам сканер существенно превосходит известные аналоги при вдвое меньшей себестоимости Имеются 2 патента на особенности разработанных алгоритмов и архитектуру сканера

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

Основные результаты работы докладывались и обсуждались на

• Конференция "Мобильные роботы 2003", Россия, Москва, ИМЕХ МГУ (XI/03)

• Конференция "Мобильные роботы 2005", Россия, Москва, ИМЕХ МГУ (111/05)

• Объединенном семинаре по робототехническим системам ИПМ им MB Келдыша РАН, МГУ им MB Ломоносова, МГТУ им НЭ Баумана и ИНОТиИ РГГУ, Москва, ИПМ им М В Келдыша РАН (11/05 и Х/06)

• XVII Международной конференции "Экстремальная робототехника", Санкт-Петербург, ЦНИИ РТК (IV/06)

• Семинаре по компьютерной графике и машинному зрению 10 М Баяковского Россия, Москва, МГУ, факультет ВМиК (Х/07)

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

Диссертация состоит из Введения, пяти глав, Заключения, Списка литературы и Приложения Содержание работы изложено на 160 страницах (включая 18 страниц приложения) Список литературы включает 59 наименований В работе содержится 75 рисунков и 15 таблиц

Содержание работы

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

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

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

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

= ,-',"2-7]. (!)

1=0 ;=0

где *[л,,л2] - входное изображение, ,«2] - выходное изображение, а^- весовые коэффициенты фильтра Из этой формулы следует важность аппаратной реализации операций суммирования с накоплением (см ниже)

4#И

ПЧО 1Н1Ч В( IV» 1Н 1Я II *Ог">|-ПЖ«. Н1К \П|рИЦ )

Ряс 1 "Оконность" адресации обращений к входным и выходным данным Черным цветом показаны центральные пиксели окон, серым - остальные пиксели, входящие в

окна

Детекторы простых элементов на изображении

Детекторы типа ДГ (7)

{использующие градиент яркости) Детекторы контуров 1 Робертса, 2 Собеля, 3 Превита, 4 Канни, Детекторы углов

5 Бедета,

6 Форстнера,

7 Харриса

Детекторы типа

ДСШ(З) (использующие коэффициент совпадения с шаблоном) Маски

8 Превита,

9 Киршча, 10 Робертсона

Детекторы типа ДПП(З)

{использующие преобразования пространства яркости) Детекторы

11 Хюккеля,

12 Бэккера Преобразование

13 Хака

Детекторы типа ДС(2)

{использующие статисты ческие

методы) Детектор контуров 14 Кониши Детектор углов 15 Сойка

Рис 2 Группы анализируемых детекторов простых элементов изображения с числом детекторов в группе (в скобках) Значительная часть главы посвящена анализу основного класса алгоритмов обработки изображения в СТЗ - алгоритмов детекторов простых элементов

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

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

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

Рис 3 Элементы ПСПД

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

Независимые части алгоритма

Хараг входн1

\ / Коммуникационные каналы

выполняемые ПЛИС и ДСП Каждый из алгоритмов представлен в виде ПСПД1 (см рис 3), учитывающей в себе коммуникационные расходы на передачу данных и параметры, характеризующие эффективность использования различных аппаратных архитектур для реализации каждой независимой части алгоритма При построении ПСПД в ней не должно быть циклов, и притом независимые части должны содержать минимально возможный набор операций над изображением Чем меньше будет гранулярность независимых частей, тем точнее можно выбрать место разбиения алгоритма между вычислителями (ПЛИС и ДСП) Так как ПСПД не содержит циклов, то всегда возможно конвейерное исполнение независимых частей Для возможности параллельного исполнения части алгоритмов не должны быть зависимыми друг от друга по данным, что с точки зрения ПСПД означает, что ни одна из этих частей не является предшествующей для любой другой

Алгоритм, каждого из рассмотренных детекторов элементов изображения, можно разложить на операторы преобразования параметров цветовой яркости (Вь В2, В3) и положения (1, _)) пикселов изображения в параметры выходных данных детектора С точки зрения задачи отображения алгоритма на архитектуру аппаратных средств в его составе следует выделить

• операторы преобразования адресов обращений к памяти,

• сами операторы обращения к памяти и

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

С целью описания свойств независимых частей алгоритмов в главе введено понятие графа зависимости алгоритмических параметров (называемого ниже -"ЗАП-граф") На рис 4 представлено графическое изображение операторов ЗАП-графа

Рис 4 Элементы ЗАП-графа В диссертации построены ЗАП-графы для всех независимых частей ПСПД алгоритмов детекторов простых элементов изображения приведенных на рис 2

1 В диссертации приводятся ПСПД для алгоритмов детекторов

8

ЗАП-граф для наиболее распространенных "оконных" операций показан на рис 5 Оператор АВ1 определяет адреса пикселей, входящих в последовательно перемещаемое по всему изображению окно, получает значения их яркостей, Р выполняет операцию над значениями яркостей нескольких пикселей в окне, и оператор \УВ1,„ записывает результат по адресу, определяемому оператором АВЫ1 и зависящему только от адреса центрального пикселя окна

Иначе обстоит дело с алгоритмом прослеживания контуров (см рис 6),

являющегося частью детектора Канни Здесь происходит выбор пикселей вдоль контура, определяемого яркостями соседних пикселей Следовательно, в операторе А„ определяется адрес очередного входного пикселя по результату работы оператора Р и адресу предыдущего входного пикселя Затем оператор 11В1 осуществляет доступ к элементу памяти по этому адресу и считывает значение яркости очередного пикселя входного изображения Алгоритм оператора Р отвечает на вопрос, является ли данный пиксель частью контура, и, если ответ

положительный, результат записывается оператором WBЬIX по адресу, определяемому оператором Авых, с учётом адреса входного пикселя.

ЗАП-граф преобразования Хака на рис.7 отличается от описанных детекторов свойством более сложной адресации к входным и выходным данным. В наиболее принятой реализации этого алгоритма выполняется суммирование значений яркостей пикселей, попавших на последовательно генерируемые линии, заданной формы. Алгоритмом оператора Авь„ перебираются все возможные значения параметров линий, т.е. осуществляется последовательная адресация ко всем элементам выходной матрицы, описывающей пространство параметров линий. Для очередного вектора параметров оператор Авх осуществляет вычисление адресов пикселей, по которым проходит линия внутри кадра изображения. При помощи оператора 11вх реализуется чтение в этих пикселях значений яркостей, и выполняется их суммирование оператором Р. Используя осуществляется запись полученного значения суммарной яркости линии по адресу выходной памяти, определяемому оператором Авьк. Очевидно, что, несмотря на сложность вычислений, этот алгоритм допускает конвейерное исполнение его частей.

алгоритма поступает бинарное изображение.

Анализ содержания ЗАП-графов показал, что важными параметрами алгоритмов для их отображения на архитектуру ПЛИС-ЦСП с учётом условий быстродействия и эффективности использования АЛУ являются:

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

2. Содержательная зависимость входных-выходных адресов (СЗА) алгоритма.

3. "Оконность" алгоритмических операций.

4. Отсутствие-присутствие циклов ЗАП - графа.

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

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

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

Значения объемов внутренней памяти для буферизирующего метода "оконных" преобразований вычисляются по формуле (2), для накапливающего -по формуле (3)

Мвир=(С + 1) (IVВра, (2)

= се,КВю) = се,^ се,1(2\о%гШ + Врх+Вли) (3)

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

Для более полной параметризации ПСПД необходимо было охарактеризовать и свойства коммуникационных каналов Здесь было желательным найти характеристику, независящую от пространственного разрешения кадра и частоты смены кадров Было принято, что каждая независимая часть алгоритма характеризуется ее коэффициентом КО изменения объемов данных в процессе их преобразования Например, для алгоритма бинаризации монохромного 256-градационного (8-ми битного) изображения КБ=1/8

Полученный набор схемных параметров (см рис 8), характеризующий независимые части алгоритмов с точки зрения их аппаратной реализации, включает

1) свойства, выделенные наЗАП-графах

a) "оконность" алгоритмических операций,

b) СЗА входных-выходных адресов алгоритма,

c) отсутствие-присутствие циклов,

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

3) необходимый объем внутренней памяти,

4) коэффициент изменения объема выходных данных по отношению к входным

СоХ^

1 {свойства ЗАП - графа]

2 ОР0 [операции/точку]

3 М„ [бит]

4 КЦ, [объём выхода/входу]

1 [свойства ЗАП - графа]

2 ОР. [операций/точку]

3 М, [бит]

4 КО, [объём выхода/входу]

КО0=С,Р,В,/С^0В0

Рис 8 Параметры ПСПД.

Здесь ОР - количество операций на один элемент входных данных, М -требуемый объем внутренней памяти, С, Я - количество столбцов и строк входных данных, В - разрядность данных

Третья глава содержит описание архитектур микросхем, применяемых для построения СТЗ Анализируются и оцениваются параметры приспособленности ПЛИС, ДСП и различных видов памяти к алгоритмическим требованиям реализации первичных алгоритмов обработки зрительных данных Определена наиболее эффективная (в вычислительном плане) роль каждой микросхемы в обработке потока данных изображения

Как известно, микросхемы внешней памяти (МВП), в зависимости от интерфейса, бывают синхронными и асинхронными, а в зависимости от их физического устройства - статическими и динамическими Заметными недостатками динамической памяти являются значения длительности времени доступа к ней, наличие циклов регенерации содержимого (1 раз в 64 гш, занимает около 0 3% от общего времени доступа) и переключение страниц памяти (на что требуются затраты времени не менее 7-ми тактов работы шины этой памяти) Опыт использования динамической памяти показывает, что циклы регенерации могут вызвать сбой при сохранении в памяти изображения, поступающего в систему в реальном времени А переключение ее страниц существенно тормозит процесс обращения к данным, расположенным на разных строках изображения В то же время память статического типа, несмотря на отсутствие в ней всех описанных недостатков, является более дорогостоящей и более энергопотребляющей Общим недостатком для всех типов памяти (в отличие, например, от регистрового файла процессора) является наличие задержки Тщ, момента времени чтения данных (времени между выставлением адреса и получением результата) Это свойство существенно для оценки реализуемости

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

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

Далее в главе рассмотрены свойства микросхем ЦСП Основное достоинство ЦСП связано с его универсальностью и логическими возможностями смены программ Это делает удобным его использование на верхних уровнях распознавания изображений (позволяя строить гибкую модель содержания наблюдаемой сцены) Вместе с тем наличие достаточного количества внутренней памяти делает удобным использование ЦСП и на нижнем уровне обработки видеоданных (позволяя быстро реализовывать "оконные" операции) Наличие в системе команд ЦСП операции умножения с накоплением позволяет заметно оптимизировать производительность вычислений при реализации КИХ-фильтров К преимуществам ЦСП следует отнести и наличие средств аппаратной поддержки работы с памятью (от реализации интерфейсов с внешней памятью до механизмов кэширования) Недостатком ЦСП является низкий уровень возможного параллелизма реализации алгоритмов преобразования видеоданных (не более 8-ми одновременных 16x16 битных умножений за один такт ЦСП)1

Затем в главе рассмотрены свойства микросхем ПЛИС Так как частота работы ПЛИС не является высокой, в сравнении с частотой сигнальных процессоров, то основное преимущество использования ПЛИС заключается в возможности программирования структуры соединения их внутренних элементов Учитывая это, наиболее эффективно использовать ресурсы ПЛИС для обработки изображений, реализуя на них ZIMD архитектуры (zero instructions multiple data/ ноль инструкций множество данных) ПЛИС является идеальной базой для мелко-гранулярных параллельных вычислений, благодаря возможностям одновременного использования большого количества конфигурируемых и независимых вычислительных элементов Кроме того, эти микросхемы позволяют организовывать конвейерные вычисления с большой длиной конвейера Архитектура ПЛИС дает возможность распределить требуемые процедуры вычислений между независимыми частями АЛУ ПЛИС и блоками внутренней памяти (каждый блок памяти ПЛИС фирмы Altera составляет 4608 бит), позволяя избежать простоев АЛУ в ожидании данных Возникает возможность работать с видеоканальными данными, обрабатывая их еще до момента времени сохранения изображения в МВП, что позволяет уменьшить трафик через шину памяти Через ПЛИС, образно говоря, "прокачивается" поток видеоданных с прогрессивной разверткой Очевидными преимуществами такого подхода является малая задержка между моментами

1 Данные на январь 2008 г

получения видеоданных и получением результатов обработки (данные одного кадра изображения обрабатываются по мере их поступления с датчика изображения) Преимущество ПЛИС, связанное с наличием большого количества конфигурируемых портов ввода/вывода, позволяет использовать ПЛИС как коммутатор потоков данных шин нескольких МВП, способствуя этим разделению трафика через различные шины памяти (архитектура с распределенной памятью) С помощью ПЛИС можно организовать подключение различных потребителей к различным МВП (архитектура с обобщенной памятью) Накладными расходами при этом является удлинение конвейера доступа к внешней памяти, что увеличивает задержку обращения к ней TRL Невысокая тактовая частота ПЛИС (-250 МГц) накладывает большие ограничения (по сравнению с ЦСП) при выполнении алгоритмов с СЗА или с циклами на ЗАП-графе Это связанно с отсутствием возможности одновременного выполнения операторов графа, входящих в цикл

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

1 Количество элементарных операций, приходящихся на один пиксель входного изображения, определяет необходимую суммарную производительность АЛУ Эти значения для детекторов показаны внутри операторов их ЗАП-графов

2 СЗА входных-выходных адресов алгоритма При СЗА снижается скорость выполнения оператора R как минимум на время TRL по причине большой длины конвейера доступа к памяти Здесь TRL время работы конвейера обращения к памяти (время на выставление адреса и получение данных) Алгоритмы, ЗАП-графы которых имеют СЗА, эффективнее исполняются при использовании памяти с меньшей задержкой чтения

Особенности свойств генерации адресов видеоданных._Табл. 1.

СЗА нет СЗА

входных данных выходных данных последовательный доступ к памяти непоследовательный доступ к памяти

• работа только с буферизированными в МВП данными, • накладные расходы на работу с памятью Тщ, И Т[\ЯА • возможна работа с видеоканальными данными, следующими с прогрессивной разверткой • возможна работа с видеоканальными данными, следующими с прогрессивной развёрткой • работа с буферизированными в МВП данными, • накладные расходы на работу с памятью Тг^д

Примеры

прослеживание контуров детектора Канни Формирование гистограммы яркостей ДСШ преобразование Хака

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

свойства СЗА, в главе вводится дополнительная характеристика их ЗАП-графа последовательный (или непоследовательный) доступ к памяти Описанные особенности генерации адресов видеоданных сведены в табл 1

3 "Оконность" алгоритмических операций Наличие описанного во второй главе свойства "оконности" позволяет, используя внутреннюю память, увеличить скорость доступа к видеоданным Для наиболее распространенных алгоритмов, у которых нет СЗА и при этом реализуемо последовательное перемещение окна, требуемый объем внутренней памяти может быть вычислен по формулам (2) или (3) Если свойства "оконности" нет, то нет и необходимости последовательного использования одних и тех же данных Это снижает потребность использования внутренней памяти микросхемы

4 Отсутствие-присутствие циклов ЗАП-грасЬа Наличие цикла исключает возможность параллельного или конвейерного выполнения его операторов (т к над очередной порцией данных необходимо выполнение всех операторов цикла до поступления новой порции данных) Для работы в темпе поступления видеоданных суммарное время работы всех операторов, входящих в цикл, должно быть не больше периода этого темпа. На рис 9-а показан пример цикла ЗАП-графа, образованного операторами А, И и Р Этот цикл исполняется над одной порцией данных в течение времени Тд+Тя+Тр Ни один из операторов цикла не начинает работу до окончания работы предыдущего, что резко сокращает производительность, в частности, -оператора К (ТК=Т|^) На рис 9-6 операторы Я и XV - оба работают с одним и тем же элементом памяти, в результате образуется цикл из операторов Л, Р и

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

МПЛИСi»^ПЛ31С-ДСПI) Мцсп, < X ^лтс-цсп, У)' (4)

- ¡¡I til

здесь к, - переменная, определяющая место разбиения /-ого алгоритма, priceO -таблично заданная функция цены микросхемы от параметров, ОР - требуемый в алгоритмах параметр производительности (количества операций в секунду), М -

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

ПЛИС и ЦСП частей алгоритмов тех детекторов, которые нужны для создания конкретной СТЗ, можно определить необходимые параметры ПЛИС и ЦСП Прежде всего, необходимо исключить повторяющиеся в разных алгоритмах независимые части, работающие с одними и теми же данными (независимые части С и Б на рис 10) Затем для независимых частей, использующих буферизирующий способ работы с внутренней памятью и обрабатывающих одни и те же данные, обнуляются требуемые объемы внутренней памяти, за исключением части, требующей наибольший объем Необходимые производительность и объем внутренней памяти ПЛИС определяются суммированием К, независимых частей алгоритма каждого детектора I, которые должны или могут выполняться на ПЛИС (5, 6) Для ЦСП требуемые характеристики определяются суммированием параметров ¿,-К частей (7, 8)

О^ПЛИС ~

1=1 *=1 III М

(6) мцс„=£|х (8)

'=1 А=1 111 '=1

Здесь Ркадр - частота кадров обрабатываемого изображения, Ск, Кк - количество столбцов и строк обрабатываемых данных на входе к-ой части алгоритма, ОРь -количество операций на один пиксел в к-ой части алгоритма каждого детектора

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

Пплис-цсп = Т<Сотк,+1, (9)

где Сотк,+1 - поток данных между частями алгоритма К, и К,+1

Сотк>х=Ск^ (Ю)

где В д +, - разрядность выходных данных А",-ой части алгоритма

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

Сош^, = (П)

/ЫРг е(К)

Рис 11 Архитектуры СТЗ, состоящих из ПЛИС, ЦСП и МВП Здесь О - объем передаваемой информации между микросхемами в секунду, ПИ-иериферийный интерфейс, ПДП- канал прямого доступа к памяти Таким образом, задача параллельно-последовательного распределения частей алгоритмов детекторов сводится к определению таких значений к=К„ которые в совокупности минимизируют критерий (4) с учетом условия выполнимости алгоритмических частей с индексами меньшими к, определяемого ограничениями возможностей ПЛИС

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

17

недостатком этого варианта является высокая цена на двухпортовые модули памяти, превосходящая цену однопортовых динамических модулей памяти такого же объема почти в 100 раз Этот вариант архитектуры (рис 11-а) целесообразен при высоких частотах видеоданных

В ряде случаев (см табл 1) возможна детекторная обработка непосредственно видеоканальных данных без предварительной буферизации всего кадра в МВП Данный способ, во-первых, позволяет уменьшить трафик данных через шину присоединения МВП для сохранения изображения, во-вторых, он позволяет уменьшить задержку в обработке очередного кадра и, в третьих, - не использовать адресные линии (это упрощает разводку проводников печатной платы и уменьшает количество занятых ножек ввода/вывода в ПЛИС) Поэтому в пределах, определяемых допустимыми нагрузками трафика через шину данных, эффективно использовать наиболее дешевый вариант архитектуры, показанный на рис 11-6 Здесь трафик данных является однонаправленным от ПЛИС к ДСП В этом варианте достаточно просто можно динамически задавать адреса памяти для хранения данных, выходящих из ПЛИС Эта информация через элементы ЦСП (ПИ и канал ПДП) попадает на шину ЦСП-МВП Кроме того, через эту шину осуществляется кэширование программного кода и работа с хранимыми в МВП данными

В общем случае, ПЛИС позволяет довольно гибко синтезировать архитектуры с различными встроенными в ПЛИС коммутаторами шин Ценой такой гибкой коммутации является увеличение задержки начала процесса передачи данных Тщ, (пропускная способность при этом остается той же) С использованием "ПЛИС-коммутаторов" можно сократить потери эффективности исполнения алгоритма, связанные с большими объемами передачи видеоданных В этом случае существует возможность выполнить требования трафика через шину МВП, при работе в темпе реального времени, и, в то же время, обеспечить передачу данных из ПЛИС в ЦСП Вариант такой реализации показан на рис 11в В этой архитектуре, поступающие кадры поочередно занимают одну из двух МВП, присоединенных к ПЛИС, в то время как с другой МВП через контроллер, реализованный на ПЛИС, работает ЦСП В главе показано, что этот вариант не эффективен в случае необходимости использования СЗА обращения к памяти при выполнении алгоритма на ЦСП Показано также, что снижение трафика через общую шину данной архитектуры можно достичь, используя ПИ ЦСП и канал ПДП В таком варианте ЦСП заказывает копирование блоков изображения из МВП1, или - МВП2 ПЛИС осуществляет посылку заказанных данных в ЦСП через ПИ и канал ПДП Это исключает операции чтения больших объемов данных из МВП1 и МВП2 по общей шине, где остаются только операции записи вМВПЗ

Каждая из приведенных архитектур соединения микросхем ПЛИС, ЦСП и МВП по-своему хороша (или плоха) для реализации алгоритмов обработки

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

№ детектора (рис 1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

№ архитектуры 2 2 2 1 2 2 2 2 2 2 2 2 3 2 2

Из таблицы видно, что для большинства детекторов наиболее подходит архитектура, показанная на рис 10-6 Исключения составляют лишь детектор контуров Канни и детектор Хака для поиска прямых линий, присутствующих в кадре изображения В главе содержится анализ причин целесообразности выбора другой архитектуры для реализации этих детекторов и приводятся рекомендации по выбору архитектуры, наиболее подходящей для реализации заданного множества детекторов, содержащих в своем составе детекторы Канни и Хака

Таким образом, формальное описание метода синтеза специализированной архитектуры для реализации заданного алгоритма обработки видеоданных на ПЛИС и ДСП состоит из последовательности следующих действий

1 Алгоритмы разбиваются на независимые части

2 Строятся ЗАП-графы независимых частей алгоритмов

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

4 Строится ПСПД

5 Выделяется подмножество совпадающих независимых частей разных детекторов, работающих с одинаковыми данными Они исключаются из всех детекторов кроме одного

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

7 Выбирается одна из трех архитектур их соединения, исходя из выработанных рекомендаций главы 4

8 Оцениваются трафики через шины и вычисляются значение критериев к,, используя зависимости (4 - 11)

9 Проверяется выполнимость циклов ЗАП-графа в выбранных микросхемах и архитектуре Если цикл не выполняется, то следует видоизменить алгоритм или выбрать более удачные микросхемы, минимизируя время выполнения операторов цикла

10 Оцениваются необходимые объемы внутренние памяти ПЛИС для группировки обработанных данных в блоки и передачи по интерфейсу

11 Окончательно выбираются микросхемы

В пятой главе, описанный метод синтеза специализированных архитектур, демонстрируется на примере выбора элементной базы и архитектуры СТЗ для распознавания штриховых кодов (ШК)_

плис исп

______ Передачу

необработанного изображения

Гистограмма 2Я ПЛИС ЦСП к

2 + 1 16 ьп

V

ЙХ 2 + 3 М^'20496 1280x1024 9ЬП ) / 280x1024 II 2 || 1 3 М-0 1280x1024 8ЬД 1280x1024

ау 1 поел окон 2 ♦ 3 3 М^-20496 II 2 |Г 1 3 М-0

9Ь« 6Ы1 ;

1280x1024 9ЬК ) 1280x1024 8Ы1 ,

с!46 1 поел окон 2+3 3 Мвуф»204Э6 II 2 || 1 3 М-0

280x10^4 1280x1024

<1136 2 + -3 3 Мвгф"20496 II 2 | | 1 3 М-0

9ЬЛ вьк ;

Оср«д_ 40x40 в

2 * 16 3 М «9728

Осрвд. 40x40 Л-10

1 поел окон 2*16 3 М '9728

28x1^2 8ЬЛЧ

128» 1(^2 8ЬЛ ^

128x102

N

28x^2

аьа N

Осрзд. 40хМ й-« 12811 поел окон ——-\

2 ♦ 16 8ЬИ

3 М -9728

128x102 8Ьл\

128x102 8ЬЛ N

Рис 12 ПСПД алгоритма локализации штрихового кода Задача распознавания и алгоритм ее решения описываются в начале главы Особенности оптической части делают критичным ко времени исполнения алгоритм локализации ШК, который должен производить обработку изображения разрешением БХвА (1280x1024) с частотой 30 кадров/сек После обнаружения ШК происходит его декодирование, в течение этого периода времени локализация ШК на вновь поступающих кадрах изображения продолжается, в МВП сохраняются только те кадры, на которых найдены ШК Отсутствие требований к высокому быстродействию алгоритмов декодирования ШК позволяет реализовать их на ЦСП Таким образом, производится разложение между ПЛИС и ЦСП алгоритма локализации ШК, ПСПД которого показана на рис 12 На этой схеме показаны также параметры задачи передачи необработанного изображения в МВП и формирования гистограммы яркостей элементов изображения

Рис 13 Требуемые от ПЛИС в задаче локализации IIIK ресурсы производительности -ОР, объем внутренней памяти - М, объём потока данных между ПЛИС и ЦСП - D, в зависимости от места разбиения алгоритма между ПЛИС и ЦСП - к.

Независимые части 1 7 алгоритма локализации ШК имеют характеристику последовательного доступа к памяти, следовательно, они могут работать непосредственно с видеоканальными данными Независимая часть 1 имеет признак "оконности", и при этом шаг окна d=l составляет один пиксель, что означает высокую эффективность буферизирующего метода использования внутренней памяти (,1/^=20496 бит или 5 блоков памяти ПЛИС, т е 23040 бит) Независимая часть 3 также имеет признак "оконности", но шаг окна d=10, следовательно, более эффективен накапливающий метод использования внутренней памяти (Мт*=4*9728 бит или 4*3 блока памяти ПЛИС, те 4*13842 бит) На рис 13 показаны требуемые ресурсы ПЛИС, в зависимости от места разбиения к алгоритма между ПЛИС и ЦСП

Часть 8 имеет СЗА входных данных, что делает невозможным работу с видеоканальными данными и требует сохранения изображения в МВП (нужно отметить, что СЗА можно избежать за счет изменения алгоритма, предусматривающего несколько проходов по изображению и генерацию большого блока вспомогательных данных) Поскольку эта часть алгоритма не использует преимуществ ПЛИС и сложна в аппаратной реализации, то она реализована в ЦСП

Задача вычисления гистограммы распределения яркостей пикселей изображения имеет ЗАП-граф, показанный на рис 14 Важно отметить наличие цикла из операторов Г(„Ы1, Р и WBbII Для работы в темпе поступления видеоданных необходимо выполнение условия не превышения времени работы

этих операторов периода поступления очередной яркости ТКвь|Х+ТР+Т\увых<Тр|х По условиям задачи Тр,х=20,8п8 Минимально возможная задержка чтения составляет 2 такта работы памяти, записи - 1 такт, и 1 такт будет потрачен на выполнение оператора Р Следовательно, 1 такт примерно равен 5,2 пЯ, а частота работы памяти и вычислителя должна быть не менее 192 МГц Что удовлетворяет параметрам АЛУ и внутренней памяти предположительных ПЛИС и ЦСП При этом объем необходимой внутренней памяти - 256*16=4096 бит Вычисление гистограммы, непосредственно используя видеоканальные данные, не требует использование операторов Авх, и Авых

Рис 14 ЗАП-граф алгоритма вычисления гистограммы распределения яркостей пикселей изображепия

Характеристики и цена ПЛИС фирмы Altera семейства Cyclone Табл 3

ЕР1СЗ ЕР1С4 ЕР1С6 ЕР1С12

Количество ЛЭ 2910 4000 5680 12060

Частота работы ЛЭ (градация скорости микросхемы - С8), МГц 275 275 275 275

Общее количество Кбит блоков памяти ОЗУ 60 78 92 239

Частота работы блоков памяти (градация скорости микросхемы - С8), МГц 197 01 197 01 197 01 197 01

Макс возможное количество 8-битных сумматоров 363 500 710 1507

Макс возможное количество миллионов 8-битных сложений в секунду, МАСб 99 825 137 500 195 250 414 425

Цена1 при градации скорости микросхемы -С8 264 руб 474 руб 533 руб 965 руб

Микросхемы ПЛИС выбирались из семейства Cyclone фирмы Altera, как наиболее новых и дешевых микросхем на момент разработки устройства. Изменение параметра разбиения к охватывало ПЛИС этого семейства в диапазоне ЕР1СЗ, ЕР1С4, ЕР1С6 и ЕР1С12 (см табл 3) Со стороны ЦСП были представлены процессоры семейства BlackFin фирмы Analog Devices

1 По данным сайта www digikev com на январь 2008 года

22

Выбор был сделан в пользу ЕР1С6 и BF-533. Полученное разбиение алгоритмов показано на рис. 12. Архитектура выбрана по типу изображённой на рис. 11-6, так как большая часть обработки сосредоточена на видеоканальных данных, и трафик, дополнительно создаваемый информацией от ПЛИС, составляет 39 Мбайт/сек, что примерно соответствует 15% максимально возможного трафика через шину ЦСП-МВП. В качестве МВП использован SDRAM 16MB с 16-ти разрядной шиной, работающей на частоте 133 МГц.

Разработанная по этому методу рефлексная видеокамера и её электронная часть показаны на рис. 15 и 16.

Рис. 15. Видеокамера, обеспечивающая программную реализацию на ПЛИС и ДСП

Рис. 16. Реализация 2-го варианта архитектуры соединения ПЛИС, ЦСП и МВП.

В Приложении приводятся список сокращений и тексты упомянутых

патентов.

Основные результаты диссертационной работы

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

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

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

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

Публикации по теме диссертации

1 Краснобаев А А Выделение трёхмерных объектов на сцене методом их моделирования Сборник трудов конференции Мобильные роботы 2003 -М, МГУ, 2003 С 309-317

2 Краснобаев А А Алгоритм локализации линейного штрихового кода в изображении сцены Сборник трудов молодых ученых, аспирантов и студентов "Информатика и системы управления в XXI веке" -М, МГТУ, 2004 С 228-234

3. Краснобаев А А Алгоритмы распознавания штриховых кодов, Препринт Института прикладной математики им М В Келдыша РАН, 2004, №84, 29 с

4. Краснобаев А А Алгоритмы работы системы технического зрения для распознавания штриховых кодов Сборник трудов конференции "Мобильные роботы 2005" -М , МГУ, 2005 С 22-32

5. Краснобаев А А Обзор алгоритмов детектирования простых элементов изображения и анализ возможности их аппаратной реализации, Препринт Института прикладной математики им М В Келдыша РАН, 2005, №114, 20 с

6 Краснобаев А А, Платонов А К Классификация алгоритмов детектирования простых элементов изображения и анализ возможности их аппаратной реализации 9-ая Всероссийская научн -практич конференция "Экстремальная робототехника", Том 5, СПб НПО Спец материалов, 2006г

7 Краснобаев А А, Платонов А К Метод параллельно-последовательного детектирования элементов изображения в системах технического зрения // Теория и системы управления, 2007, №4, С 96-109

8 Видеосканер штриховых кодов и расчетно-кассовый узел с его использованием пат 65267 Рос Федерация №2007111328/22, ; заявл 28 03 07; опубл 27 07 07, Бюл № 21

9 Способ нахождения штриховых кодов в кадре видеоизображения пат 2314564 Рос Федерация № 2006123894, заявл 05 07 06;опуб 10 01 08, Бюл №1

Введение.

ГЛАВА 1. Алгоритмы и аппаратные средства обработки изображений.

1.1. Этапы работы системы технического зрения.

1.1.1. Получение изображения.

1.1.2. Обработка и анализ видеоданных.

1.1.3: Передача получаемых данных в удалённый компьютер.

1.2. Задачи обработки изображений.

1.3. Организация вычислений.

1.3.1. Представление алгоритмов.

1.3.2. Методы'разложения задачи на аппаратуру.

1.3.3. Параллелизм и конвейерность.

1.4. Свойства вычислительных средств.

1.4.1. Процессоры.

1.4.2. Программируемая логика ПЛИС.

1.4.3. Характеристики производительности.

1.4.4. Сравнения.

Выводы главы 1.

ГЛАВА 2. Анализ алгоритмов первичной обработки изображений.

2.1. Параметры вычислительных ресурсов алгоритмов обработки изображений.

2.1.1. Параметризованная схема потоков данных.

2.1.2. Граф зависимости алгоритмических параметров'.

2.1.3. Параметры ПСПД.

2.1.4. Требуемый объём внутренней памяти микросхемы для оконных операций.

2.2. Анализ задач низко- и среднеуровневой обработки изображений.

2.2.1. Низкоуровневая обработка.

2.2.2. Среднеуровневая обработка.

2.2.3. Детекторы простых элементов изображения.

2.2.4. Морфологическая обработка изображений.

Выводы главы 2.

ГЛАВА 3. Элементная база электроники для реализации первичной обработки цифровых изображений.

3.1. Параметры архитектуры видеосистем.

3.2. Датчики изображения.

3.3. Память в составе видеоустройства.

3.3.1. Роль внутренней памяти в составе видеоустройства.

3.3.2. Внешняя память в составе видеоустройства.

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

3.4. Процессор в составе видеоустройства.

3.4.1. Роль механизмов работы с памятью процессора в видеосистеме.

3.4.2. Ввод/вывод видеоинформации в процессоре.

3.4.3. Анализ возможностей ЦСП в задаче обработки видеоданных.

3.5. ПЛИС в составе видеоустройства.98'

3.5.1. Свойства и характеристики ПЛИС.

3.5.2. Анализ возможностей ПЛИС в задаче обработки изображений.

3.6. Сравнение параметров ПЛИС и ЦСП.

3.7. Влияние свойств ЗАП-графа на архитектуру.

Выводы главы 3.

ГЛАВА 4. Программно-аппаратная система ПЛИС-ЦСП.

4.1. Разбиение алгоритмов обработки изображения между ПЛИС и ЦСП.

4.2. Архитектура системы, состоящей из МВП, ПЛИС и ЦСП.

4.3. Формат передачи данных между ПЛИС и ЦСП.

4.5. Формализм построения архитектурного решения для заданного алгоритма обработки видеоданных.

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

ГЛАВА 5. Пример использования метода разложения задач обработки изображений нижнего и среднего уровня на архитектуру ПЛИС-ЦСП.

5.1. Разработка сканера штриховых кодов.

5.1.1. Алгоритм работы сканера штриховых кодов.

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

Выводы главы 5.

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

Для решения этой, задачи желательно найти формальные методы

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

Хорошо известно, что на рынке интегральных микросхем существуют выпускаемые массово по сравнительно низкой цене цифровые процессоры, приспособленные к использованию всего богатства возможностей программных алгоритмов, и логические интегральные схемы, позволяющие достигнуть высокой степени параллельности преобразования данных. Среди этих микросхем для обработки видеоданных наилучшими качествами универсальности и возможностей специализации обладают цифровые сигнальные процессоры (ЦСП) и программируемые логические интегральные схемы (ПЛИС). Предполагается, что в архитектуре их совместного использования плохо параллелизуемые, логически ветвящиеся программные части. алгоритмов должны выполняться на ЦСП, а ПЛИС должна использоваться для выполнения- хорошо параллелизуемых и логически жёстко фиксированных частей алгоритма. В этом случае актуальна задача наилучшего разделения алгоритмов обработки изображений на части, выполняемые ЦСП, и на части, выполняемые ПЛИС. С другой стороны, опыт разработки видеосистем показал, что в таких системах возникает противоречие между алгоритмическими требованиями процессов доступа к большим объёмам памяти видеоданных, ограничениями объёмов внутренней памяти микросхем и быстродействием процессов обмена информацией с модулями внешней памяти: Это приводит в процессе анализа способа программирования СТЗ к необходимости учёта особенностей памяти аппаратных модулей, влияющих на процесс программной* реализации алгоритмов работы с видеоданными.

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

Существующие алгоритмы разложения конкретной задачи на разнородные вычислительные элементы базируются на описании раскладываемого алгоритма с помощью dataflow-wiQTOjsp., предложенного Д. Эдэмсом (D. Adams) [2]. Такое представление позволяет на верхнем уровне описания потока данных выявить требуемую последовательность преобразования данных и структуру задачи. Существует несколько широко используемых моделей параметризации dataflow-описания таких, как synchronous dataflow (SDF) [3], cyclo-static dataflow (CSDF) [4] и сравнительно недавно появившаяся модель windowed synchronous dataflow (WSDF) [5], больше подходящая для спецификации алгоритмов преобразования двумерных данных. С использованием этих спецификаций осуществляется статическое планирование выполнения задачи, анализ требуемых объёмов памяти и т.п. Подробный обзор наиболее распространённых методов разбиения задачи на аппаратную и программную части можно найти в [6]. В алгоритме global criticality, local phase (GGLP) [7] кроме параметризованного описания потока данных дополнительными входными данными являются оценки времени выполнения для каждого отдельного элемента фактора") алгоритма в их аппаратных и программных способах реализации, а также - оценки занимаемой площади микросхемы и объёма кода. Аналогичные оценки предполагает и COSYN алгоритм [8].

В данной работе рассматривается проблема разложения на аппаратную и программную части существующих алгоритмов первичной обработки изображений. Особое внимание уделено детекторам простых элементов изображения [9], далее называемых детекторами. Описаны методы выбора наиболее подходящего вычислительного элемента, основанные на предлагаемых оценках алгоритмических свойств частей детектора. Дана характеристика роли ПЛИС и ЦСП в процессе первичной обработки изображений. Рассматривается^ проблема построения архитектуры СТЗ, состоящей из ПЛИС, ЦСП и модулей внешней памяти (МВП).

Выраяфю огромную благодарность и признательность своему научному руководителю Александру- ^Константиновичу ¡Платонову за ценные' идеи, советы, наставления и всестороннюю поддержу. 'Большое значение для работы оказали пожелания и хритищ высказанные сотрудниками ЛСШМ. им. %рлдыша. Очень признателен за практическую апробацию разработанного метода сотрудникам Крмпании ИТтриз^М. ¡Неоценимый вклад в диссертационную работу внесли мои близкие родственники

Большое всем спасибоI

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

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

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

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

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

Заключение

1. Р.Гонсалез, Р. Вудс. Цифровая обработка изображений. Москва. Техносфера. 2005.

2. D.A. Adams. A computation model with dataflow sequencing. Technical Report CS 117, Computer Science Department, Stanford University, 1968.

3. E. A. Lee and D. G. Messerschmitt, "Synchronous Dataflow," Proceedings of the IEEE, vol. 75, pp. 1235-1245, 1987.

4. G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete, "Cyclo-Static Dataflow," IEEE Transactions on Signal Processing, vol. 44, pp. 397-408, 1996.

5. Joachim Keinert, Christian Haubelt, and Jurgen Teich, "Windowed Synchronous Data Flow (WSDF)," Tech. Rep. 02-2005, University of Erlangen-Nuremberg, Institut for Hardware-Software-Co-Design, 2005.

6. Shuvra S. Bhattacharyya, "Hardware/Software Co-synthesis of DSP Systems," in Y. H. Hu, editor, Programmable Digital Signal Processors: Architecture, Programming, and Applications, pages 333-378. Marcel Dekker, Inc., 2002.

7. A. Kalavade and E. A. Lee, "A Global Critically/Local Phase Driven Algorithm for the Constrained Hardware/Software Partitioning Problem," in Proceedings of the International Workshop on Hardware/Software Co-Design, 1994, pp. 42—48.

8. B. P. Dave, G. Lakshminarayana, and N. K. Jha, "COSYN: Hardware-Software Co-Synthesis of Embedded Systems," in Proceedings of the Design Automation Conference, 1997.

9. Dave Litwiller. CCD vs. CMOS: Facts and Fiction. http://www.dalsa.com/shared/content/PhotonicsSpectraCCDvsCMOSLitwiller.pd f

10. E.R. Fossum, "CMOS Image Sensors: Electronic Camera on a Chip," Proceedings of the IEEE International Electron Devices Meeting (IEDM), plenary paper, December 1995, Washington D.C.

11. E. Davis. Machine Vision : Theory, Algorithms, Practicalities. (2nd Edition), Academic Press (1996).

12. Андреев В.П., Вайнштейн Г.Г., Москвина Е.А. Экспериментальное исследование некоторых элементов процесса анализа трёхмерной сцены. 4-ая Международная объединённая конференция по искусственному интеллекту, Том 8, ВИНИТИ, М., 1975.

13. Тсудзи С., Накамура А. Распознавание объекта в наборе промышленных деталей. 4-ая Международная объединённая конференция по искусственному интеллекту, Том 8, ВИНИТИ, М., 1975.

14. P. Meer and I. Weiss. Smoothed differentiation filters for images. Journal of Visual Communication and Image Representation, 3(l):58-72, March 1992.22. http://en.wikipedia.org/wiki/Controlflow

15. JI. Рабинер, Б. Гоулд. Теория и применение цифровой обработки сигналов. Москва. Мир. 1978.

16. С. Northcote Parkinson, Parkinson's Law: The Pursuit of Progress, London: John Murray, 1958.

17. A. Epstein: "Parallel Hardware Architectures for the Life Sciences for the Life Sciences", Ph.d Thesis, Delft University of Technology, 2004.

18. A.J. Bernstein. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers, 15:757-762, October 1966.

19. C. Soviany: "Embedding Data and Task Parallelism in Image Processing Applications", Ph.d Thesis, Delft University of Technology, 2003.28. www.bdti.com

20. Von Neumann, J. 1945. "First Draft of a Report on the ED VAC," 30 June; reprinted in Stern,From ENIAC to UNIVAC: A Case Study in the History of Technology, Digital Press, Bedford, Massachusetts, 1981.30. www.analog.com31. www.ti.com

21. Kyo, S., Koga, Т., Okazaki S. IMAP-CE: a 51.2 GOPS video rate image processor with 128 VLIWprocessing elements. Proceedings. 2001 International Conference on Volume 3, Issue , 2001 Page(s):294 297 vol.3

22. B. Bayer, U. S. Patent No. 3,971,065.

23. А.И. Белоусов, С.Б. Ткачёв. Дискретная математика. Москва. МГТУ им. Н.Э. Баумана. 2002.

24. А.А. Краснобаев, Обзор алгоритмов детектирования простых элементов изображения и анализ возможности их аппаратной реализации, Препринт Института прикладной математики им. М.В. Келдыша РАН, 2005, №114, 20 с.

25. Weiss. High-order differential filters that work. IEEE Transaction on Pattern Analysis an Machine Intelligence, 16(7):734-739, July 1994.

26. P. Meer and I. Weiss. Smoothed differentiation filters for images. Journal of Visual Communication and Image Representation, 3(l):58-72, March 1992.

27. V. Torre and T. A. Poggio. On edge detection. IEEE Transaction on Pattern Analysis and Machine Intelligence, 8(2): 147-163, March 1986.

28. J. Canny. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679{698, November 1986.

29. P. Beaudet. "Rationally Invariant Image Operations," in International Joint Conference on Pattern Recognition, pp. 579-583, Kyoto, Japan, 1978.

30. W. Forstner. A feature based correspondence algorithm for image matching. Intl. Arch. Photogramm. Reemote Sensing, 26:150-166, 1986.

31. M. Trajkovic and M. Handley. Fast corner detection. Image and Vision Computing, 16:75-87,1998.

32. Hueckel M. H., «An operator which Locates Edges in Digitized Pictures», JACM, 18, №1, 113-125 (1971).

33. S. K. Nayar, S. Baker, and H. Murase, "Parametric feature detection," In Proceeding of IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, June 1996.

34. Illingworth, J., and Kittler, J., "A Survey of the Hough Transform," CVGIP, vol. 44, pp. 87-116, 1988.

35. D.J. Field, "Relations between the Statistics and Natural Images and the Responses Properties of Cortical Cells" J. Optical Soc. Am., vol. A, no. 4, pp. 2379-2394, 1987.

36. S. Konishi, A.L. Yuille, and J.M. Coughlan, "A Statistical Approach to MultiScale Edge Detection," Proc. Workshop Generative-Model-Based Vision: GMBV '02, 2002.

37. Andreas Farid Pour and Mark D. Hill, Performance Implications of Tolerating Cache Faults, IEEE Transactions on Computers (TOC), March 1993.

38. ADSP-BF531/ADSP-BF532/ADSP-BF533: Blackfin Embedded Processor Data Sheet (Rev. E,7/2007), http://www.analog.com/UploadedFiles/Data Sheets/ADSP-BF531 BF532 BF533.pdf

39. LVDS Application and Data Book, Texas Instruments, SLLD009, November 2002.

40. Cyclone III Device Handbook (ver 1.2, Sep 2007), http://www.altera.com/literature/hb/cyc3/cyc3ciii5vl.pdf

41. W. Zhao, R. Chellappa, A. Rosenfeld, P.J. Phillips, Face Recognition: A Literature Survey, ACM Computing Surveys, 2003, pp. 399-458.

42. Roger C. Palmer, The bar code book. Helmers Publishing, Inc. Formerly North American Technology, Inc., 1995.

43. Краснобаев A.A., Алгоритмы распознавания штриховых кодов, Препринт Института прикладной математики им. М.В. Келдыша РАН, 2004, №84, 29 с.

44. Краснобаев А.А. Алгоритмы работы системы технического зрения для распознавания штриховых кодов. Сборник трудов конференции "Мобильные роботы 2005". -М., МГУ, 2005. С. 22-32.

45. Способ нахождения штриховых кодов в кадре видеоизображения : Патент 2314564 РФ № 2006123894; заявл. 05.07.06 ; опубл. 10.01.08, Бюл. № 1

46. А.А. Краснобаев, Алгоритм локализации линейного штрихового кода в изображении сцены. Сборник трудов №2. Информатика и системы управления в XXI веке. -М., МГТУ, 2004. сс. 228-234.

47. Haralick, Robert М., and Linda G. Shapiro, Computer and Robot Vision, Volume I, Addison-Wesley, 1992, pp. 28-48.

48. Видеосканер штриховых кодов и расчетно-кассовый узел с его использованием : Патент 65267 РФ № 2007111328/22; заявл. 28.03.07; опубл. 27.07.07, Бюл. № 21