Введение к работе
Актуальность проблемы. . В связи с-бурным развитием вычислительной техники точных технологии, необходимостью обработки -больших числовых массивов , .значительно возрос интерес к проблемам обработки цифровой информации. О этой целью создаются системы обработки - изображении,которые используют для решения -atiix задач ',как: распознавание образов, обнаружения «эли .медицинского, диагноза,анализа различных, бкомедицинских сигналов изображений,опознавание на расстоянии, идентификация человеческих лиц к отпечатков пальцев, обработка аэрофотоснимков и т.п. s Особый ''интерес к таким системам возник, в', связи с развитием персональны): ЭВМ, увеличения их быстродействия и сбьема 'Памяти и снижения стоимости' , что и послужило основной-причиной.создания на их базе систем обработки изображения. Для систем работающих в .'реальном '.масштабе времени особенно важны.такие хзракте-рис тика, как сбьем. памяти:'и быстродействие вычислительной среды. Термин "реальней масштаб времени" в зависимости от решаемых- задач обработки.изображений понимается по разному. Скажем, если.такая-система установлена на производственном тенвейере,то здесь реальный масштаб -времени ассоциируется ;о скоростью движения данного конвейера.Однако если -брать іеловеческіш глаз , то'реальный масштаб -времени будет равен М кадрам в секунду. Если задачи конвейера уже более/или <енее решаются в настоящий момент,то задачи человеческого лаза в основном рассматриваются в перспективе, так как для шх-необходим-качественный скачок в развитии -.технологий фонзводстБЭ'ЩС, что должно увеличить -быстродействие не на >диницы. ,а на-несколько'порядков. '. Поэтому, задачу'обработки ізображенпй в реальном масштабе.времени в.-настоящий момент [Ытаютоя решать в двух направлениях:'
аппаратная реализация, алгоритмов обработки изображений.
использование "параллельных -^-числительных процессоров.
Аппаратная реализация, алгоритмов обработки изображений страда** узкой направленностью, громоздкость» и ,' как пра-,е;іло , все же не обеспечивает необходимого быстродействия . Использование же параллельныхвычислительных сред , работающих в реальном масштабе времени ,как нельзя лучше подходит для создания интеллектуальных систем обработки изображений. Однако при этом возникает различные сложности в реализации алгоритмов обработки изображений в параллельной.среде процессора.
' Параллельный процессор '.если -рассматривать .. грубо, состоит .'иэ процессорных. элементов и блока управления. Лісбой из параллель-них. процессоров имеет как правило' некоторую архитектуру. Архитектура параллельного процессора..определяется праькла'.ш связи между соответствующими -процессорными элементами . і а также правилами поступления данных в процессорные элементы извне. Процессорные .'элементы с системой -коммуникаций' :. образуют параллельную среду вычислений .которая подразделяется на однородную и неоднородную. Если процессорные элементы .входящие в состав параллельного процессора, имеют одинаковую структуру и мощность , тосоот-ьестзуещая параллельная среда является однородной и неоднородной е противном случае. Обилие архитектур говорит само за сс-бя - о 'сложности программирования , а также об отсутствии универсальности.' :-Поэтому для . решения определении.", задач обработки иЕсбражеккд подбирается оптимальным, образом Определенная -архитектура. Следовательно , более универсальный вариант для систем обработки изображений будет находился в гибридных архитектура?.. Однако ввиду сложности и, соотБетсвенно,, больших материальных затратах , о такой архитектуре'.'.приходится липа мечтать.Данную же проблему' пытаются '.резіїть.. пока лутем.создания уникальных архитектур ,' таких как: ..-систолическая, матричная,, нейронная, гиперкуб и т'.'п;.:-. - ..'';-,.'... -',; ?.'-\'--;: .':: "у:''.' '' '-Л.
В данной диссертационной работе рассматривается система обработки изобрахеннй с архитектурой гиперкуба с однородней параллельной вычислительной среди": .Еыбср такой архитектуры был сделан исходя из следующих соображений: в отличие от матричной и систолической , архитектура гиперкуба имеет больше связей ,что позволяет перестраивать' архитектуру з процессе решения задач обработки пзебралений. Далее путем пересилю! данных мехно случить матричную, сферическую, то-рообразную иерархичную структуру. Однородная вычислительная среда была выбрана в силу специфики данных оцифрованных изображений, которые обрабатываются в системе. Кроме того, гиперкуб более изучен теорией графов ,что- позволяет использовать ее потенциальные возможности в программировании.Обрабатывая данные, : которыми в частности являются цифрс-вие изображения, на любом параллель ном процессоре приходится решать,по крайней мере дзе категории задач: так,это задачи "транспорта",т.е. пересылки данных ыелд'у процессорными зле-. ментзми, ' и задачи "распараллеливания алгоритмов обработки этих, данных.Обе зти задачи взаимосвязаны »:ехду собой , так как имеют общую цель: наиболее, эффективно использовать еы-" числительные ресурса , а следовательно , п увеличить быстродействие всей системы обработки изображений.
Цель работы. Настоящая робота посвящена вопроса1,' разработки.."-алгоритмов для 'программного обеспечения систем обработки цифровых изображении на базе вычислительной еноте:.»! параллельной-обработки (ЕСГО), параллельный процессор которой имеет архитектуру гиперкуба. . ' '.: ' . -. .
В связи с этим в работе проводятсяследукдпе - исследования:
.;'-. 1)Дается анализ и оценка систем обработки изображений.с точки зрения их программного: обеспечения. С атей целью рассмотрены аспекты, касапздеся выбора языков-лрогрк.жпро-вания, ; представления данных об пзеб-ражекш:, режимов работ, взаимодействия с-.аппаратными средствами,с пользователе:: и анализируются функций обработки цифровых изображений в существующих соответствующих ECHO . '
" -.5.-.,. .
2).'.классифицируются системы обработкиизображений на основе параллельныхвычислительных средств с SIMP, MIMD и конвейерными архитектурами,.
. 4} разрабатывайте* и вводятся определения идеального QJ* и реаліного QR„-.мерного пространства гиперкуба .учитывающее правіками соседства ПЭ в . параллельном процессоре. Используя 'определенную теорией графов вершинну» связность мы определяем связность изображении.
S разрабатывается и оптимизируется алгоритм для получения ллачарной карты загрузки элементов цифровых изображений . ь локальную память соответствующих ПЭ ЕСЛО "ПАРС", имеющей .. QR^-мерное пространство гиперкуба.
6) разрабатывается методика- распараллеливания алгоритмов обработки цифровых изображений, включ&кщаа обобщенную схему распараллеливания алгоритмов,опирающаяся на алгоритмы' создания карт загрузки.
Методы исследования. При выполнении работ ..использован математический аппарат теории множеств и теории графов, а также элементы теории алгоритмов.
Новые научные результаты-к- основные положения, выносимые ка заздту'.-
1). метод создания в QJ*-мерном пространстве гипер-.
куба'тривиальных плоскостей (тор, сфера, плоскость),необхо
димых при ревении задач при решении задач обработки изобра
жений -ь ECHO с архитектурой гиперкуба.' . .
'.) оригинальный метод создания,карт загрузки, позволяющий резать' задачи транспорта .для- алгоритмов, .обработки' изображений; .испс-льз-дапх . в- качестве -'данных некоторую окрестность. Проведена оптимизация данных карт загрузки ка предмет шішналь них временных затрат.;.
3}.разра0отана методика распараллеливания'алгоритмов обработки .: цифровых 'изображений, включаюдзя ' обобщенную схему распараллеливания, алгоритмов, -опирающаяся на алгоритмы создания. Карт загрузк!!,. ':.-
'Практическая ценность результатов проведенных .исследований заключается) в разработке; -.' алгоритмов создания опти-
мальнои карты эагрувки элементов цифровых изображений в реальное вычислительное пространство параллельного процессора ВСПО "ПАРС",предназначенного для быстрого решения гадач транспорта; методика распараллеливания некоторого'класса алгоритмов обработки цифровых ««ображений , с. учетом выбранной карты загруеки, в параллельном процессоре ECHO с архитектурой гиперкуба .'".
Реализация и шедре-'іе' результатов исследований. Теорії-тические и практические результаты диссертационной работы использованы при проведении двух хоздоговорных научно-исследовательских, работ ,( с номерами государственной' регистрации 01830030834,01840037373.)
Результаты опробованы на эммулягоре реального пространства гиперкуба на IB).! РС'\ХТ.
Апробацій работы. Основные положения обсуждались на следующих научно-технических конференциях: ,
-всесоюзная'конференция " Микропроцессоры-35 ", г.Москва 1985,
- научно-техническая конференция "Проблемы создания систем, анализа и понииаиия изображений ",Ташкент 19Э1.
Публикации. Материалы по теме диссертационной работы опубликованы в 4-х статьях, 2- отчетах по И!Р,
Структура диссертационной работы. 'Работа состоит из -введения; трех глав, заключения/содержит список литгратуры 113-22 наименований , 3-і. рисунков, 1 таблицы и приложения.
Похожие диссертации на Разработка алгоритмов цифровой обработки сигналов для программного обеспечения многопроцессорных систем
