WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |

Алгоритм, каждого из рассмотренных детекторов элементов изображения, можно разложить на операторы преобразования параметров цветовой яркости (B1, B2, B3) и положения (i, j) пикселов изображения в параметры выходных данных детектора. С точки зрения задачи отображения алгоритма на архитектуру аппаратных средств в его составе следует выделить:

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

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

Адрес - оператор Данные - оператор записи вычисления в память адресов W A Адрес - оператор Адрес Данные Данные Данные вычисления - оператор чтения из значений памяти R P выходных данных - дуга направления передачи - дуга показывающая место текущего результатов чтения или записи в память работы операторов - двумерная матрица изображения с выделенным пикселем, к которому производится обращение в конкретный момент времени Рис. 4. Элементы ЗАП-графа.

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

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

ЗАП-граф для наиболее распространённых “оконных” операций показан на рис. 5. Оператор Авх определяет адреса пикселей, входящих в последовательно перемещаемое по всему изображению окно, Rвх получает значения их яркостей, P выполняет операцию над значениями яркостей нескольких пикселей в окне, и оператор Wвых записывает результат по адресу, определяемому оператором Авых и зависящему только от адреса центрального пикселя окна.

i, j p, q i = 1.. I, di=1.. Wi j = 1.. J, dj = 1.. Wj Авых i + di, j + dj Rвх Wвых Авх P i = p = j = q = p, q i, j i = I p = P j = J q = Q Рис. 5. ЗАП-граф для “оконных” операций.

i = 1.. I, di=1.. Wi i, j p, q j = 1.. J, dj = 1.. Wj Авых i + di, j + dj Rвх Wвых Авх P i = 1 p = j = 1 q = p, q i, j i = I p = P j = J q = Q Рис. 6. ЗАП-граф алгоритма прослеживания контуров в детекторе Канни.

Иначе обстоит дело с алгоритмом прослеживания контуров (см. рис. 6), являющегося частью детектора Канни. Здесь происходит выбор пикселей вдоль контура, определяемого яркостями соседних пикселей. Следовательно, в операторе Авх определяется адрес очередного входного пикселя по результату работы оператора P и адресу предыдущего входного пикселя. Затем оператор Rвх осуществляет доступ к элементу памяти по этому адресу и считывает значение яркости очередного пикселя входного изображения. Алгоритм оператора P отвечает на вопрос, является ли данный пиксель частью контура, и, если ответ положительный, результат записывается оператором Wвых по адресу, определяемому оператором Авых, с учётом адреса входного пикселя.

ЗАП-граф преобразования Хака на рис.7 отличается от описанных детекторов свойством более сложной адресации к входным и выходным данным.

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

p = 1.. P p -1 P2 + Qq = 1.. Q = p, q P -1 q - = 2 2 2 Авых Q -I + J I + J t = t -...

2, i, j i = - sin( )t + cos( ) t Rвх Wвых j = cos( )t + sin( ) Авх P i = p = j = q = p, q i = I p = P j = J q = Q Рис. 7. ЗАП-граф алгоритма преобразования Хака (Hough) для прямых линий. На вход алгоритма поступает бинарное изображение.

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

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

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

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

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

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

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

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

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

M = (C +1) (W -1) Bpix, (2) BUF C W M = Nacc ceil(Bacc ) = ceil ceil ceil(2log2 W + Bpix + Bfilt ). (3) acc d d Здесь С – длина строки изображения, d – шаг окна, W – размер окна, ceil() – функция округления до большего среднего, Bpix – количество бит для представления яркости пикселей изображения, Bfilt – количество бит для представления весовых коэффициентов фильтра.

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

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

1) свойства, выделенные на ЗАП–графах a) “оконность” алгоритмических операций, b) СЗА входных-выходных адресов алгоритма, c) отсутствие-присутствие циклов, 2) количество элементарных операций, приходящихся на один пиксель входного изображения, 3) необходимый объём внутренней памяти, 4) коэффициент изменения объёма выходных данных по отношению к входным.

0 i C0xR0 1. [свойства ЗАП - графа] C1xR1 CixRi Ci+1xRi+1. [свойства ЗАП - графа] 2.OPi,[операций/точку] B0 2.OP0, [операций/точку] B1 Bi 3. Mi, [бит] Bi+...

3. M0, [бит] 4. KD0, [объём выхода/входу] 4. KDi, [объём выхода/входу] KD0=C1R1B1/C0R0B0 KDi=Ci+1Ri+1Bi+1/CiRiBi Рис. 8. Параметры ПСПД.

Здесь OP – количество операций на один элемент входных данных, M – требуемый объём внутренней памяти, C, R - количество столбцов и строк входных данных, B – разрядность данных.

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

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

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

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

Далее в главе рассмотрены свойства микросхем ЦСП. Основное достоинство ЦСП связано с его универсальностью и логическими возможностями смены программ. Это делает удобным его использование на верхних уровнях распознавания изображений (позволяя строить гибкую модель содержания наблюдаемой сцены). Вместе с тем наличие достаточного количества внутренней памяти делает удобным использование ЦСП и на нижнем уровне обработки видеоданных (позволяя быстро реализовывать “оконные” операции). Наличие в системе команд ЦСП операции умножения с накоплением позволяет заметно оптимизировать производительность вычислений при реализации КИХ-фильтров.

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

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

Возникает возможность работать с видеоканальными данными, обрабатывая их ещё до момента времени сохранения изображения в МВП, что позволяет уменьшить трафик через шину памяти. Через ПЛИС, образно говоря, "прокачивается" поток видеоданных с прогрессивной развёрткой. Очевидными преимуществами такого подхода является малая задержка между моментами Данные на январь 2008 г.

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

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

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

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

Эти значения для детекторов показаны внутри операторов их ЗАП–графов.

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

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

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

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»