    
Раздел: Документация
0 ... 67 68 69 70 71 72 73 ... 78 водства аппаратуры делают возможным построение больших многопроцессорных сетей, должны решаться и проблемы, связанные с разработкой эффектных систем обработки и анализа изображений как на уровне элементов растра, так и на уровне регионов. СПИСОК ЛИТЕРАТУРЫ [1] Н. С. Andrews, Computer Techniques in Image Processing, Academic Press, New York, 1970. [2] D. Ballard and C. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, NJ., 1982. [3] K. R. Castleman, Digital Image Processing, Prentice-Hall, Englewood Cliffs, NJ., 1979. [4] R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis, Wiley, New York, 1973. [5] R. C. Gonzalez and P. Wintz, Digital Image Processing, Addison-Wesley, Reading, Mass., 1977. [6] E. L. Hall, Computer Image Processing and Recognition, Academic Press, New York, 1979. [7] T. Pavlidis, Structural Pattern Recognition, Springer-Verlag, New York, 1977. [8] T. Pavlidis, Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, Md., 1982. [9] W. K. Pratt, Digital Image Processing, Wiley, New York, 1978. [10] A. Rosenfeld, Picture Processing by Computer, Academic-Press, New York, 1969. [11] A. Rosenfeld and А. С. Как, Digital Picture Processing, Academic Press, New York, 1976; 2nd ed. (2 vols.), 1982. [12] J. Serra, Image Analysis and Mathematical Morphology, Academic Press, New York» 1982. [13] A. Rosenfeld, "Picture Processing: 1981,** Comput. Graphics Image Process., 79:35-75 (1982). [14] S. H. Unger, "A Computer Oriented toward Spatial Problems," Proc. IRE, 46:1144-1750(1958). [15] A. Rosenfeld, Picture Languages, Academic Press, New York, 1979. [16] C. R. Dyer and A. Rosenfeld, "Image Processing by Memory-Augmented Cellular Automata," IEEE Trans., РАМ I-3:29-41 (1981). [17] C. R. Dyer and A. Rosenfeld, "Triangle Cellular Automata," Inf. Control, 48:54-69 (1981). [18] A. Rosenfeld and A. Wu, "Parallel Computers for Region-Level Image Analysis," Pattern Recog., /5:41-50 (1982). [19] A..Rosenfeld and A. Wu, "Reconfigurable Cellular Computers," Inf. Control, 50:64-84 (1982). [20] T. Dubitzki, A. Wu, and A. Rosenfeld, "Parallel Computation of Contour Properties," IEEE Trans., РАМ1-3 331-331 (1981). [21] J. S. Todhunter and С. C. Li, "A New Model for Parallel Processing of Serial Images," Proc. 5th Int. Conf. Pattern Recog., 1980, pp. 493-496. [22] T. Dubitzki, A. Wu, and A. Rosenfeld, "Region Property Computation by Active Quadtree Networks," IEEE Trans., РАМ1-3:626-633 (1981). СБИС-АРХИТЕКТУРЫ ДЛЯ АНАЛИЗА ФОРМЫ И УПРАВЛЕНИЕ БАЗОЙ ДАННЫХ ИЗОБРАЖЕНИЯ К. Фу, К. Хуанг, Б. Ва1 25.1.ВВЕДЕНИЕ В этой главе рассматриваются структуры СБИС для анализа и управления графической информацией. Специалисты в области информатики давно признали, что лучше один раз увидеть, чем тысячу раз услышать. Интеллект ЭВМ будущего значительно возрастет по сравнению с современными, если будет разработано новое поколение машин для обработки многомерных графических данных в дополнение к построчной обработке алфавитно-цифровой информации. За последнее десятилетие интенсивные исследования и разработки позволили осуществить машинный анализ и распознавание образов. Практические приложения таких машин включают анализ биомедицинской информации, распознавание символов, отпечатков пальцев и движущихся объектов, дистанционное восприятие, промышленный контроль, системы зрения роботов, военную разведку и сжатие данных в системах связи [11, 12, 24]. Под анализом изображений понимается использование ЭВМ для распознавания образов и обработки изображений. Оперативные графические данные необходимо сохранять на диске и быстро вызывать с него для решения указанных задач. Машины анализа изображений, построенные на СБИС, должны объединять возможности анализа образов и управления базой данных изображения в рамках единой системы [1, 10]. 25.2.СБИС И МАШИННАЯ ГРАФИКА Мы вступили в эру сверхбольших интегральных схем (СБИС). Интегральные схемы проникли во все области человеческой цивилизации. Размер пластин ИС за 20 лет возрос с 25 до 150 мм. Фирма Bell Laboratories изготавливает пластины размером 200 мм и кристаллы памяти на 2 Мбит. Японская фирма Fujitsu объявила о создании нового некремниевого прибора, транзистора с высокой подвижностью электронов, имеющего время переключения 17 пс, т. е. в 30 раз меньше, чем у кремниевых аналогов. Проект по разработке сверхскоростных интегральных схем (ССИС) посягнул на выпуск приборов с временем переключения 4 пс. В кругах разработчиков усиленно обсуждаются возможности использования интеграции на уровне пластины в алгоритмически специализированных машинах. Достижения в технологии СБИС пробудили мысль о реализации многих алгоритмов обработки сигналов и изображений непосредственно в специализированных кристаллах. Для внедрения образного восприятия в ЭВМ буду- 1 Лафайеттский университет, Лафайетт, Индиана. щего было бы весьма желательно иметь поддерживающую машину баз данных. Новый подход вычисления с управлением от данных может быть применен для систем искусственного интеллекта. Новые направления СБИС -архитектура и многопроцессорные системы с асинхронными потоками данных - должны быть серьезно исследованы на предмет потенциального использования в обработке сигналов и распознавании образов. Реалистичным подходом является также расширение потока управления в архитектуре с двумерного в матричных машинах до трехмерного в пирамидальных. Хорошими кандидатами для параллельной обработки изображений будут и многоконвейерные машины при условии эффективного решения проблем распределения задач. Принципиальные ограничения сегодняшних ЭВМ заложены в их механизмах ввода-вывода. Компьютеры все еще не могут эффективно общаться с человеком в естественных формах, таких как устная или письменная речь, рисунки или образы, документы и иллюстрации. Существующие ЭВМ пока далеко не удовлетворительны из-за малой скорости ввода-вывода, отсутствия речи и зрения, возможностей перевода и обработки в реальном масштабе времени. Для построения "ориентированных на человека" интерактивных ЭВМ потребуется прежде всего повысить их возможности в понимании "естественных" форм представления информации, разумной и, возможно,  Логическая схема  Аэрофотоснимок   Анализ образов и обработка знаний Рентгеновский снимок База знаний  Эскиз изображения База данных изображения   оооооооооо ОООООООО о о О О О О О О О Человек-холера тор Рис. 25.1. Функции анализа (поиска) изображения Таблица 25.1. Графические алгоритмы для реализации на СБИС Название алгоритма Реализуемые функции Обработка изображений Распознавание образов Статистическая обработка изображений Обработка баз данных Коррекция, фильтрация, повышение четкости, выделение контура, сегментация, регистрация, восстановление, группировка, свертка, фурье-анализ и т.д. Выделение признаков, сравнение с эталоном, статистическая классификация, синтаксический анализ, регистрация изменений, восприятие языка, анализ и синтез сцен и т. д. Статистическая декомпозиция, манипуляция атрибутами, реконструкция изображений, алгоритмы поиска-сортировки, подбор по образцам и т. д. Реляционные операторы (объединение, пересечение, проекция, дополнение), реляционно-эскизное преобразование, выделение сходства, структурирование данных, очереди приоритетов, динамическое программирование, пространственные операторы и т. д. более надежной, чем у человека, реакции на них. Естественные языки и обработка речи выходят за пределы тематики данной главы. Далее остановимся на разработках интеллектуальных ЭВМ с возможностями распознавания образов. Для реализации этих функций необходимо разработать системы ввода, вывода и анализа графической информации, выбираемой из большой базы данных изображения. Графические функции такой интеллектуальной ЭВМ анализа изображений в общих чертах приведены на рис. 25.1. На вход могут поступать чертежи или тоновые изображения, такие как функциональные схемы, рентгеновские или аэрофотоснимки. Соответствующим выходом может быть классификация и (или) интерпретация входных данных, например: рисунок топологии СБИС, точное описание патологии в области легкого или карта поля боя в реальном масштабе времени. Машина базы данных изображения может быть частью большой системы баз знаний. Множество функций анализа изображений требуется встроить в обрабатывающую секцию средней производительности для коррекции и сегментации изображений, выделения характеристик, классификация образов и форм, структурного анализа, описания и интерпретации изображений, как показано в табл. 25.1. Некоторые из этих функций могут быть реализованы непосредственно аппаратурой СБИС, а другие - специальными программными пакетами. Для построения интегрированных систем анализа (поиска) изображений необходим прогресс в разработке устройств ввода-вывода изображений, графической обработке запросов и методах управления базами данных. 25.3. ПРОЦЕССОРЫ НА СБИС ДЛЯ ОБРАБОТКИ ИЗОБРАЖЕНИЙ В недавнее время предпринимались многочисленные попытки разработки СБИС-устройств для обработки сигналов (изображений) и анализа образов. Статистические подходы к этим задачам часто приводили к вычислениям 427 hi bi Модуль munaD =$>L
0 0 1 "n UI2 и 13 О "гг "гз О 0 "зз 
6) А Модуль шилом в=с+ 1 а,-в, где сди t=i 11 {Aj и Bj для t=/t...tp}-матрицы размера гхг в) =0 р и Модуль типа У d=c+ Z А.-bt,гдеc.d {b£ для Ыи...,р}-Векторы- столбцы, для i=f,...,p} матрицы размера гхг г) Рис. 25.2. Простейшие матричные арифметические модули на СБИС: а - модуль разложения подматриц; б - модуль обращения матриц; в матриц; г - векторный умножитель матриц умножитель с матрицами больших размеров. Структурные подходы требуют выполнения операций синтаксического анализа и грамматического разбора. Здесь приводится пример проекта конвейерной архитектуры на СБИС для статистического выделения и классификации признаков. Ступени конвейера спроектированы из модульных арифметических устройств в соответствии с рис. 25.2. Эти арифметические модули на СБИС будут использоваться итеративно при вычислении подматриц. Конвейерная архитектура основана на алгоритмах обработки блочных матриц, разработанных в [9] для LXJ-разложения, умножения матриц, обращения треугольных матриц и решения треугольных систем уравнений. На рис. 25.3 показана конвейерная структура для реализации алгоритма обращения блочных матриц, исполняемого за четыре шага. Каждая СБИС выполняет вычисления с подматрицами размера г Хг, порядок входной матрицы U равен п. На практике считается, что п-Цг и п. Случай, когда к = -njr =4, показан на рис. 25.3. При больших к эгот конвейер требует исполь-  U„ О о о Utz U22 о о U13 V* U23 U2i U33 % -1
Шаг!: V„=u;1; V22~u£;Vn=U&VU Модули! Шаг2: Vn= -Vi, • (U1Z • v22);VZ3-VZZ {U23- Ыззз) МодулиM ШагЗ: Vi3~~Vtt (Ц12 V23+ U13 V33> Vz*r - vtz (цгз Ы+U2k • *W Модули M ШагЬ: V1tir - V1t • (Uf2« V24+ UJ3 • V31+U1U • V„) Модули M Рис. 25.3. Конвейерный блок обращения матриц на СБИС, основанный на алгоритме Хуанга-Чена: / - модуль обращения; М - модуль умножителя; L - регистр-защелка; подматрицы размера m X m зования О (к) - О (njr ) модулей СБИС. Общая задержка при вычислении V=U"1 составит 0(п2/г). Аналогичный конвейер может быть построен для перемножения матриц, \Л1-разложения и решения треугольных систем. Подробные сведения можно найти в статье [8]. СБИС и выделение признаков. На рис. 25 А,а показана функциональная схема экстрактора признаков на СБИС. Этот экстрактор состоит из трех подсистем: генератора матрицы рассеяния, системы обращения матриц и генератора признаков, которые выделены штриховыми линиями. Вычита-тель векторов реализован на модифицированных модулях типа V для генерирования разностных матриц входных отсчетов и средней разности. Сеть из двух матричных умножителей используется для умножения на ортогональную матрицу. Каждая сеть содержит njr модулей умножителей. Весовой матричный сумматор может быть реализован на п/r модулях умножителей с несколькими дополнительными входами для констант. Обращение 0 ... 67 68 69 70 71 72 73 ... 78 |
