Раздел: Документация
0 ... 68 69 70 71 72 73 74 ... 78 Обучающие поел вдова- с тельное та Генератор матрацы рассеяния Л Вычитатель векторов Сеть умножителей матриц Х2 Сеть умножителей матриц 1 Векторы с образов блок обращения матриць?
1
Генератор признаков й) блок обращения треугольной матрицы блок обращения треугольной матрицы Обучающие векторы 1 признаков Г- Генератор ковариационных матриц Сеть умножителей матриц N Вычитатель И векторов 1 № Сеть умножителей матриц
Векторы. признаков 1 Фишеровский линейный классификатор блок решения линейной системы  блокрешения треугольных систем J Отметки классов б) • Рис. 25.4. СБИС для анализа (распознавания) образов: а - экстрактор признаков; б - классификатор образов матриц рассеяния выполняется с применением сети LU-разложения, двух устройств обращения треугольных матриц и сети умножителей для выполнения вычислений А-1 = (L U) 1 =U~1 • L"1. Генератор признаков может быть реализован на модулях типа V с модифицированными входами констант. Наконец, матрично-векторный умножитель также строится на модулях типа V.У СБИС и классификация образов. Примерная функциональная схема классификатора образов приведена на рис. 25А,б. Схемотехническое решение генератора ковариационных матриц такое же, как у генератора матриц рассеяния на рис. 25.4,а. Блок линейной системы состоит из сети для LU-разложения и блока решения треугольной системы. Этот матричный решающий блок необходим для приведения запомненной системы к треугольному виду. Фишеровский классификатор реализуется на небольшом числе комбинационных логических схем и модифицированных модулях типа V. Распознавание контекстно-свободных языков. В синтаксическом анализе образов форма образа часто представляется строкой контекстно-свободного языка. Распознавание формы образа выполняется с помощью грамматического разбора строки по правилам заданной грамматики образов [14]. Систолическая структура СБИС для высокоскоростного распознавания контекстно-свободных языков показана на рис. 25.5. Процесс распознавания основан на алгоритме Кока-Казами-Янгера (Cocke-Kasami-Younger). Эта конвейерная треугольная матрица, построенная из п(п+ 1)/2 процессорных ячеек, может быть использована в синтаксическом распознавании образов. Каждая ячейка имеет два однонаправленных канала данных и одну линию управления по каждому из направлений. Данные, поступающие в виде строк символов, проходят через распознающую матрицу слева направо и снизу вверх, как показано на рис. 25.5. Эта двумерная матрица может распознать любую входную строку длиной п за 2п тактов. Такой языковой анализатор и его расширение для распознавания конечных языков более детально описаны в работе [3]. Недавно была предложена архитектура СБИС распознавания языков [21]. СБИС в сейсмической классификации. Здесь представлен специализированный СБИС-процессор для быстрой классификации сейсмических волн [20]. Этот специализированный процессор, содержащий три систолические матрицы, может быть подключен к универсальной ЭВМ. Каждая систолическая матрица имеет такую временную характеристику 0(1), чтобы входные данные могли подаваться соответствующим образом. Систолическая матрица для выделения признаков содержит линейно соединенные процессорные элементы, как показано на рис. 25.6. Входные данные, которыми являются дискретизированные и квантованные сейсмические волны, кодированные в двоичном коде, запоминаются в отдельных модулях памяти. Вычисляются два признака: число переходов через нуль i-I \W0)\ ! j (01) щ i-• i.7/; I i i (02) (OS) (12) (04) 11 > i---1 I (22}\ i -i * (14) (23) Рис. 25.5. Архитектура СБИС для распознавания контекстно-свободных языков для п =4: сплошной квадрат - ячейка; штриховой квадрат - граничная ячейка Iff г-1 10X4 I I (24) (34) i---1 \(44)\ I j Рис. 25.6. Процессорная матрица, схема перемещения данных и операции каждого процессора по выделению признаков
а 123 13 44 1 х~*-а и сумма абсолютных значений. Переход через нуль определяется проверкой знаков в каждой паре последовательных точек. Для определения изменения знака используются схемы "Исключающее ИЛИ". Все п процессорных элементов вычисляют оба признака одновременно и передают частичные результаты следующим процессорным элементам. Для простейшего распознавания вычисляется расстояние между вектором неизвестных признаков и каждым из опорных векторов, например вектором средних, каждой из групп (примитивов), а затем вектор неизвестных признаков приписывается ближайшей группе. Эта процедура может быть разделена на два этапа: вычисление расстояния между вектором неизвестных признаков и опорными векторами и далее выбор одного из них - ближайшего. В системе используется процессорная матрица, содержащая процессоры-вычислители для вычисления расстояния, и процессорная матрица, содержащая процессоры-компараторы для сравнения расстояний. Предположим, что имеется / примитивов; каждый примитив / имеет опорный вектор признаков [m\ , т\ , . .., mlk ], где к - общее число признаков. Процессорная матрица размера 1Хк, которая выполняет вычисление расстояний, показана на рис. 25.7. Опорные векторы примитивов вводятся снизу и продвигаются вверх, в то время как векторы неизвестных признаков вводятся сверху и продвигаются вниз. Хорошо известно, что расстояние Левенштейна (Levenshtein) между двумя строками может быть вычислено с помощью процедуры динамического программирования. Следовательно, оно может быть реализовано параллельной обработкой в СБИС. В определении расстояния Левенштейна каждая вставка, удаление и замена подсчитываются как одно ошибочное преобразование. Для таких вычислений со строками построена процессорная мат-   4* U [xjt х • • • > xjj] [х}, х2,..., х£] ----t-Izi riiri £Т TT TT TT FT TT il Al   JT rj lITj ? Примитив [/77?,/77f,...,/77j*] [/77;г,/77,. [777/,/77/,. ..,/77] ..,/77/] Рис. 25.7. Процессорные матрицы и схема перемещения данных при распознавании примитивов рица, изображенная на рис. 25.8. Предлагаемый компаратор строк может использоваться в любой задаче, где требуется вычислять расстояние Левенштейна. С его помощью можно осуществить анализ строк при распознавании сейсмических волн, распознавании строк символов при приеме информации или сравнение образов при анализе графических очертаний, если объект может быть представлен строкой, например цепным кодом. Данный простейший анализатор может быть также применен в любых задачах распознавания по наименьшему кодовому расстоянию и векторного сравнения образов. Было проведено имитационное моделирование трех описанных систолических матриц: матрицы выделения признаков, матрицы простейшего распознавания и матрицы анализа строк. Доказана корректность проекта сис-  Рис. 25.8. Процессорная матрица и схема перемещения данных при вычислении расстояний Левенштейна топических матриц и правильность их функционирования. Детальные сведения о систолических матрицах и результаты моделирования приведены в работе [20]. 25.4. МАШИНЫ БАЗ ДАННЫХ ИЗОБРАЖЕНИЯ Система управления базой данных изображения предоставляет простой доступ большого числа пользователей к широкому набору структурированных графических данных (цифровых образов). Она обеспечивает как высокоуровневый, так и низкоуровневый доступ к изображениям. Большинство существующих систем баз данных изображения применяются со специально разработанными пакетами математического обеспечения и для специализированных систем анализа образов. Было бы весьма желательно разработать специализированную машину баз данных для управления базой данных изображения. Пока было предпринято несколько попыток создания аппаратуры [4, 16, 22], но ни одна из них на самом деле не была применена для управления базой данных изображения. Функции по управлению базой данных изображения и их периферийная поддержка изображены на рис. 25.9. Во-первых, необходимы быстродействующие и интеллектуальные входные графические устройства. Признаки и структура изображения (очертания, тестура и пространственные связи), выделяемые главным графическим процессором, должны быть преобразованы в символьные эксизы (sketches) изображения, запоминаемые в логической базе данных изображения. Эти непреобразованные "сырые" образы система должна преобразовать в эффективные коды, запоминаемые в физи-434\ Система управления базой данных изображения Сырые образы Входное устройство т i i i 1 т Реляционное структурирование эскизов изображения  i ± Сжатие изображения Символические эскизы изображения база данных изображений  Т 1 Восстановление изображений L ± Декомпрессия изображений Выходное устройство Рис. 25.9. Функции управления базой данных изображения ческой базе данных изображения. За счет использования высокоуровневых языков управления изображением должна быть обеспечена гибкая манипуляция и образом, и функцией доступа. Для восстановления изображения из реляционных эскизов используется логическая база данных. Для отображения на дисплее с высоким разрешением сжатые изображения должны быть подвергнуты декомпрессии1. Функции передачи выделенных результатов в главную ЭВС выполняет выходное устройство. Рассмотренные функции управления базой данных изображения должны быть поддержаны специально спроектированными аппаратными устройствами, которые и составляют машину базы данных. Машина баз данных для обработки изображений может быть определена следующими функциональными характеристиками. Реализуются такие высокоуровневые функции баз данных, как выбор, проекция и соединение. Эти функции предназначены для манипуляции базой данных изображения. С другой стороны, реализуются и такие низкоуровневые операции обработки, как построение гистограмм и выделение контура. Таким образом, машина баз данных изображений - это обычная машина баз данных, дополненная низкоуровневым оборудованием для обработки изображений. Обычно считают, что СБИС дешевы. В действительности для сложных операций это не так, поскольку необходимо обеспечить внешнее управление, синхронизацию, память и программирование. Кроме того, по мере роста числа типов кристаллов система становится дорогостоящей. Решением этой проблемы является общее использование ресурсов сети и соединений. Такой путь решения проблемы иллюстрируется рис. 25.10. Кристаллы СБИС распределены по всем модулям памяти. Они могут использоваться разными трактами в реальном масштабе времени. Пул общих ресурсов Операция, обратная по отношению к операции сжатия. - Прим. ред. 0 ... 68 69 70 71 72 73 74 ... 78
|
|||||||||||||||||||||||||||||||
