Метод декомпозиции алгоритмов систем технического зрения на параллельно-конвейерное программно-аппаратное исполнение в архитектуре ПЛИС-ЦСП тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Краснобаев, Антон Александрович

• Краснобаев, Антон Александрович
• кандидат физико-математических наук
• 2008

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

Введение.

ГЛАВА 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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Краснобаев, Антон Александрович

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Краснобаев, Антон Александрович, 2008 год

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