Содержание к диссертации
Введение
Глава 1. Аналитический обзор методов, алгоритмов и аппаратных средств 10
1.1 Введение 10
1.2 Обзор методов распознавания образов 11
1.3 Области применения и особенности задач визуализации объектов п-мерного пространства 25
1.4 Основные методы визуализации многомерных данных 27
1.5 Сущность предлагаемого подхода к визуализации пространственно распределенных образов, имеющих сложный топологический портрет 30
1.6 Выводы по главе 32
Глава 2. Разработка математических методов распознавания образов 33
2.1 Введение 33
2.2 Существующие методы отображения многомерных объектов 34
2.2.1 Линейное отображение 34
2.2.2 Нелинейное отображение 35
2.2.3 Ортогональная проекция 36
2.2.4 Геометрический смысл нелинейного R-отображения точки it-мерного пространства на плоскость 45
2.2.5 Перепое начала координат n-мерного пространства и биплоскостные сечения 47
2.3 Метод секущих гиперплоскостей 48
2.4 Алгоритм секущих гиперплоскостей 51
2.5 Выводы по главе 54
Глава 3. Разработка устройства нелинейного отображения с секущими гиперплоскостями 55
3.1 Введение 55
3.2 Общее описание устройства 56
3.3 Синтез операционного автомата 58
3.4 Синтез управляющего автомата 82
3.5 Временные характеристики операционного устройства 86
3.6 Выводы по главе 92
Глава 4. Сравнительный анализ устройства нелинейного отображения с аналогами 93
4.1 Введение 93
4.2 Аналог 1 94
4.3 Аналог 2 102
4.4 Сравнение временных характеристик синтезированного устройства с аналогами 105
4.5 Выводы по главе 109
Заключение 110
Обзор литературных источников 113
- Области применения и особенности задач визуализации объектов п-мерного пространства
- Существующие методы отображения многомерных объектов
- Синтез операционного автомата
- Сравнение временных характеристик синтезированного устройства с аналогами
Введение к работе
Актуальность работы. Задачи визуализации объектов n-мерного пространства находят применение в системах управления технологическими процессами, в системах диагностики и распознавания обазов, экспертных системах и системах принятия решений в технике, экономике и медицине, в лингвистике и психологии. В последнее время широкое распространение получили интерактивные системы принятия решений, в которых ответственное лицо принимает решение и оценивает их последствия на основе визуализированных данных.
Для визуализации объектов, имеющих большое число признаков в виде совокупности параметров, на плоскости существует множество методов. Широкое распространение получили методы, относящиеся к линейным и нелинейным преобразованиям.
Решению проблем визуализации объектов многомерного пространства посвятили свои работы А.И Галушкин, К. Фу, К. Пирсон, К Фукунага, Н.Г. Загоруйко, Р.С. Лбов и другие отечественные и зарубежные авторы.
К наиболее распространенным методам визуализации объектов многомерного пространства в интерактивных системах принятия решений относятся нелинейные R-отображения (р: Rn—»R2. При визуализации объектов многомерного пространства рассматриваемые образы могут быть вытянуты вдоль одного или нескольких параметров или иметь сложный топологический портрет. Такие образы называются пространственно распределенными. Между тем в результате использования нелинейных R-отображений для визуализации пространственно распределенных образов часто возникают ситуации их ложного пересечения, в результате чего может произойти ошибочное принятие решения. Это обстоятельство определяет основную проблемную ситуацию данного диссертационного исследования. В системах принятия решений обрабатываемые данные носят преимущественно многомерный характер с большим числом признаков, что требует для визуализации значительных временных затраты. Для сокращения времени визуализации, требу- ются аппаратао-технические средства акселерации. Сущность основной решаемой задачи заключается в развитии существующих методов и разработке аппаратно-технических средств для визуализации точечных многомерных объектов в пространственно распределенных образах со сложными топологическими портретами на основе нелинейных отображений. На основании изложенного тема диссертационной работы является перспективной и актуальной. Работа выполнялась в рамках НИР по гранту Г02-4.2-5 (2002-2005 г.г.) «Разработка методов, алгоритмов, программных и технических средств быстрых символьных вычислений» при непосредственном участии автора.
Объектом исследования являются многомерные пространства, включающие в себя объекты с большим числом признаков.
Предметом исследования являются инструментально технические средства визуализации пространственно распределенных образов, имеющих сложный топологический портрет.
Цель работы: разработка методов и алгоритмов визуализации пространственно распределенных образов и построение на их основе устройства визуализации объектов многомерного пространства.
В соответствие с этим в работе решаются следующие задачи: анализ существующих методов визуализации объектов многомерного пространства и обоснование необходимости развития существующих методов для визуализации пространственно распределенных образов со сложными топологическими портретами; разработка метода и алгоритма секущих гиперплоскостей как развитие метода нелинейного отображения объектов многомерного пространства; разработка устройства визуализации пространственно распределенных образов со сложными топологическими портретами, реализующего метод секущих гиперплоскостей;
4) моделирование устройства визуализации, получение его временных характеристик и сравнение с аналогичными устройствами визуализации. Методы исследования. Для решения поставленных в работе задач используется теория распознавания образов, математический анализ, теория вычислительных процессов, теоретическое программирование и теория алгоритмов, а также теория автоматов.
Научная новизна работы заключается в следующем: разработан метод секущих гиперплоскостей как развитие метода нелинейного отображения объектов многомерного пространства, открывающий возможность корректной визуализации невыпуклых и пространственно распределенных образов, имеющих сложный топологический портрет; разработан алгоритм секущих гиперплоскостей, который за счет сокращения количества циклов вычислений позволяет сократить время визуализации объектов n-мерного пространства; разработано операционное устройство визуализации объектов многомерного пространства с операционным автоматом в виде I-автомата, что создает предпосылки к сокращению аппаратных затрат.
Практическая ценность работы состоит в следующем: построенный новый алгоритм метода секущих гиперплоскостей реализован виде программных продуктов «Навигатор» и «Навигатор-2» для решения практически важных задач в различных областях принятия решений; разработанное операционное устройство визуализации в виде I-автомата позволяет визуализировать объекты большой размерности с приемлемым временем визуализации, что открывает возможности к использованию в различных системах управления технологиче- б скими процессами, в системах диагностики, экспертных и других системах, использующих визуализацию многомерных объектов. На защиту выносятся:
Метод и алгоритм секущих гиперплоскостей, реализующий нелинейное отображение и позволяющий определить факт отсечения точки параллельными гиперплоскостями.
Операционное устройство визуализации объектов многомерного пространства в пространственно распределенных образах со сложными топологическими портретами, имеющее возможность параллельной организации п операционных автоматов с единым управляющим автоматом.
Результаты моделирования работы операционного устройства и сопоставительного анализа с аналогичными устройствами визуализации, показывающие, что синтезированное устройство по сравнению с аналогами затрачивает меньше времени на визуализацию объектов большой размерности.
Апробация работы. Основные положения диссертационной работы докладывались на международных и российских конференциях: "Распознавание - 2003" (г. Курск, 2003 г.), "Медико-экологические информационные технологии - 2003, 2004 (г. Курск, 2003, 2004 гг.), "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (г. Курск, 2003 г.), а также в научно-практическом вестнике «Человек и его здоровье» (г. Курск, 2005 г.).
Результаты работы внедрены на кафедрах дерматовенерологии и гистологии Курского государственного медицинского университета, в НПО «Экран» Минздрава РФ. Акты внедрения прилагаются к материалам диссертации.
Публикации. Результаты, полученные в диссертационной работе, нашли отражение в семи печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 99 наименований и одного приложения. Диссертация изложена на 186 страницах и содержит 34 рисунка и 16 таблиц. Основной текст работы содержит 109 страниц.
Во введении обоснована актуальность темы, сформулированы цель и задачи исследования, научная новизна, практическая ценность работы, основные положения, выносимые на защиту и др.
Первая глава носит обзорно-аналитический характер и раскрывает существующие методы классификации и распознавания образов.
В обзорной части главы приведены общие понятия теории распознавания образов, сформулирована проблема обучения распознающих систем, приведен круг задач решаемых с помощью распознавания образов, приведены несколько классификаций методов распознавания образов. Сформулированы два подхода к обучению распознающих систем: структурный и геометрический подходы. По способу представления знаний методы распознавания образов делятся на интенсиональные и экстенсиональные.
Задачи визуализации объектов n-мерного пространства находят применение в системах управления технологическими процессами, в системах диагностики и распознавания образов, экспертных системах и системах принятия решений в технике, экономике и медицине, в лингвистике и психологии.
Для задач визуализации характерно, что большие объемы обрабатываемых данных имеют высокую размерность п » 3, а результирующие данные должны иметь размерность от 1 до 3.
Основой визуализации является отображение, которой каждой точке п-мерного пространства ставит в соответствие точку двухмерного пространства. По виду отображение методы, использующие визуализацию при решении задач классификации, разделяются на линейные и нелинейные.
К основным линейным методам визуализации данных относятся: метод главных компонент (МГК), факторный анализ, линейный дискриминантный анализ, разложение Корунена-Лоева.
К основным нелинейным методам, использующим визуализацию в задачах классификации, можно отнести: методы многомерного шкалирования, методе Патрика, нелинейное R-отображение в двумерное пространство.
Сущность предлагаемого подхода заключается в отсечении части пространства двумя параллельными гиперплоскостями в местах n-мерного пространства, имеющего сложный топологических портрет, для визуального выявления ложных пересечений, путем исследования той части пространства, которая расположена между гиперплоскостями.
Во второй главе рассматриваются математические аспекты методов отображения многомерных объектов, таких как линейное и нелинейное отображения.
Нелинейное R-отображение включает в себя 2 последовательно выполняемых для каждой точки исследуемой совокупности преобразования: L-отображение точки z n-мерного пространства Р11 на плоскость R-отображения. S-отображение полученной точки двумерного пространства Р .
В основе S-отображения лежит преобразование, позволяющее при переходе из пространства Рл в пространство Р2 оставить неизменным расстояние от определенной фиксированной точки до всех остальных точек исследуемого множества. Направление для осуществления S-отображения в двумерном пространстве Р2 задается прямой, проходящей через начало координат и точку q = {q}, q2).
Сущность метода секущих гиперплоскостей заключается в отображении части пространства между двумя параллельными гиперплоскостями. Угол наклона или коэффициенты уравнения гиперплоскостей, а также расстояние между ними могут варьироваться. Это позволяет исследовать пространство в непосредственной близости от границ образов и выявить пересечения. Коэффициенты необходимо установить такие, чтобы гиперплоскости были перпендикулярны параметру, вдоль которого происходит пространственно распределение (вдоль которого вытянут образ).
В третьей главе описывается синтез операционного устройства для реализации нелинейного отображения и метода секущих гиперплоскостей.
Устройство, реализующее нелинейное отображение и метод секущих гиперплоскостей представляет собой операционное устройство, работающее под управлением хост-машины.
Операционный автомат синтезируется в виде I-автомата, состоящего из блока регистров, шины результата Z, шин операндов SI, S2, комбинационной схемы Ф.
Управляющий автомат представляет собой автомат Мура с жесткой логикой.
В четвертой главе сравниваются временные характеристики разработанного устройства и аналогов, разработанных на кафедре в рамках проводимых исследований. В качестве первого аналога был взят процессор визуализации объектов n-мерного пространства. В качестве второго аналога взят мультипроцессор распознавания образов.
В заключении приводятся основные результаты и выводы диссертационного исследования.
В приложении размещен листинг программных средств для моделирования работы алгоритмов и устройств.
Области применения и особенности задач визуализации объектов п-мерного пространства
Задачи визуализации объектов n-мерного пространства находят применение в системах управления технологическими процессами, в системах диагностики и распознавания образов, экспертных системах и системах принятия решений в технике, экономике и медицине, в лингвистике и психологии [52 - 62].
Основными целями визуализации в подобных задачах являются:1) визуальное исследование структуры, образованной объектами п-мерного пространства;2) визуальное исследование динамики изменения положения объектов п-мерного пространства;3) отнесение нового объекта к необходимому образу, путем визуального выбора.
Визуализация является наиболее наглядным способом описания структуры многомерных данных: лицо принимающее решение (ЛПР) имеет возможность путем непосредственного визуального анализа полученного изображения определить, как распределены точки в исходном пространстве признаков, распадаются ли исследуемые совокупности точек на четко выраженные образы (таксоны) в этом пространстве, определить число этих образов и осуществить выбор модели данных исследуемой предметной области. Иногда определение структуры образов с помощью визуализации может оказаться завершающим этапом исследования [55, 56].
Визуализация является наиболее наглядным способом оценки изменения расположения объектов n-мерного пространства, т.е. дает возможность наглядно увидеть процесс изменений, происходящих в наблюдаемой или управляемой системе [52].
Для задач визуализации характерно, что большие объемы обрабатываемых данных имеют высокую размерность п » 3, а результирующие данные должны иметь размерность от 1 до 3.
Получаемое при визуализации графическое изображение п-мерных объектов в одно-, двух- или трехмерном пространстве должно сохранить интересующие ЛПР специфические особенности исследуемой совокупности ri-мерных объектов [54 - 56]. Поскольку эти особенности сохраняются при отображении, они являются инвариантами этого отображения. Известно большое количество методов анализа многомерных данных: метод главных компонент, анализ соответствий, целенаправленное проецирование и т.д. [55, 63-67].
Во многих методах отображений каждая точка обрабатывается независимо от других точек, а иногда обрабатывается по одной и той же программе [63, 68, 69]. Таким образом, имеются необходимые предпосылки для распараллеливания.множество X, содержащее М эмпирических объектов (Х={х.},і=0,М), гдекаждый объект измеряется по п признакам. Такие объекты представляются в виде точек векторов (х-,...,х ) n-мерного линейного пространства Rn. Такаямодель представления широко используется в задачах классификации состояний различных систем [54, 55, 70 - 72].
Основой визуализации при такой постановке задачи является отображение, которой каждой точке n-мерного пространства ставит в соответствие точку двухмерного пространства. По виду отображение методы, использующие визуализацию при решении задач классификации, разделяются на линейные и нелинейные.
К основным линейным методам можно отнести: метод главных компонент (МГК) [63, 64, 73], факторный анализ [74 - 76], линейный дискрими-нантный анализ [54, 55, 73, 77], разложение Корунена-Лоева [68].
Все приведенные методы относятся к методам целенаправленных процедур (ЦП) [55, 66, 67, 78]. Сущность методов ЦП заключается в определении положения плоскости, на которую осуществляется отображение совокупности объектов n-мерного пространства, при котором максимально сохраняются те или иные наперед заданные свойства этой совокупности, задаваемые статистическими критериями.
Так в МГК в качестве базисных векторов плоскости отображения выбирают собственные вектора ковариационной матрицы всей совокупности объектов, имеющих наибольшие собственные значения.
В факторном анализе базисными векторами являются общие факторы. При этом выбор общих факторов дополняется еще процедурой ортогональных преобразований, т.е. таким поворотом плоскости отображения, при котором общие факторы получают наиболее естественную и убедительную содержательную интерпретацию.
В линейном дискриминантом анализе базисные вектора определяются в результате решения обобщенного характеристического уравнения, в которое входят ковариационная матрица точек одного и того же образа.
В качестве критериев в этих методах применяются различные среднеквадратичные критерии, используются в виде исходных данных значения расстояний между исходными точками совокупности и точками, рассчитанными на основании этой совокупности, например, геометрическими центрами одного образа.Основными методами отображения являются методы ортогональной и центральной проекции.
К основным нелинейным методам, использующим визуализацию в задачах классификации, можно отнести: методы многомерного шкалирования [59, 79 - 83], нелинейные отображение в двумерное пространство, увеличивающие разделимость образов [68, 84].
Особенностью большинства из подобных нелинейных методов, в отличие от линейных, является то, что само отображение определяется в процессе итерационной процедуры минимизации некоторого статистического критерия, зависящего от исходного множества отображаемых точек [59, 85, 86].
Критерии обладают различными свойствами передачи структуры исходной конфигурации точек: в среднем сохраняются все расстояния, более точно передаются небольшие и менее точно большие, более точно передаются большие расстояния, чем небольшие, большие расстояния несколько увеличиваются, а малые несколько уменьшаются.С другой стороны имеются нелинейные методы, в которых отображение
Существующие методы отображения многомерных объектов
Отображение видасопоставляющее каждому вектору z пространства Рп некоторый векторпространства Рт, называется оператором (преобразованием) С, действующим из Р" в Рт. Оператор С называется линейным, если для любых двух векторов Z] и z2 из Рп и произвольного числа \х выполняются соотношения: С Каждому линейному оператору С в n-мерном векторном пространстве Р" соответствует матрицакоторая называется матрицей оператора С. Элементы Су матрицы С представляют собой коэффициенты разложениякоординат вектора q по координатам вектора z.
Пусть q = Cz - линейный оператор, действующий из n-мерного пространства Рп в двумерное пространство Р2, где С = [(] - матрица данного линейного оператора. В качестве линейного преобразования для визуализации, в данной диссертационной работе используется отображение вида:
Линейное преобразование (2.7) ставит в соответствие каждому вектору z = (z}, z2,,..,zn) из n-мерного пространства P" вектор q = {цьЦІ) двумерного про-странства Р и называется L-отображением.
Для визуализации данных в данной диссертационной работе используется нелинейное R-отображение, включающее в себя 2 последовательно выполняемых для каждой точки исследуемой совокупности преобразования:3. L-отображение (2.7) точки z n-мерного пространства Р" на плоскость R-отображения.4. S-отображение полученной точки двумерного пространства Р2.
В основе S-отображения лежит преобразование, позволяющее при пере-ходе из пространства Р в пространство Р оставить неизменным расстояние от определенной фиксированной точки до всех остальных точек исследуемого множества. Направление для осуществления S-отображения в двумерном пространстве Р2 задается прямой, проходящей через начало координат и точку q = (qi, q2\ полученную в результате преобразования (2.7).
Произвольную точку h = (х,у) на прямой, проходящей через две точки ht = (хі,Уі) и h2 = (х2,у2) можно представить в виде вектора, зависящего от некоторого действительного числа Xт.е. ад = ((1-Я,) X! + X х2, (1-А.) л + Ху2) (2.9)Переменная X задается отношениемгде р(а,Ь) - расстояние между точками а и Ь.
Если точка h лежит на прямой между точками Гц и h2, то значения переменной X находятся в интервале 0 X 1. При этом точка h совпадает с точкой hi или с точкой h2 при X соответственно равной X = О и X = 1.
Пусть p(n)(zi, Zj) - расстояние между точками ZjH ZJ В n-мерном про странстве Р" (i, j - 1, М ), р(2)(Чі, qj) - расстояние между точками qs и ( в 2 мерном пространстве Р (i J = 1, М). Тогда X будет определяться отношениемгде Z[) = (0,... , 0) - начало координат в Рп; Чо = (qoi) Чек)- начало координат в Р2. В качестве меры близости объектов в исходном признаковом пространстве Р" и в 2-мерном пространстве Р2 при R-отображении используется евклидово расстояние, вычисляемое по формуле
Таким образом, смысл S-отображения точки qf = (qIt q2) заключается в вычислении экранных координат (qpi, qp2) в соответствии с формулой
Если экранные координаты ( 7оь Чъг) начала координат равны нулю, т.е. qo (0,0), то формула (2.13) запишется в видеS-отображение (2.13) или (2.14) выполняется для всех точек исследуемой совокупности, вследствие чего получается отображение двумерного пространства Р2 в двумерное пространство Р (S), которое является результирующим для R-отображения.
Пусть Pi - подпространство n-мерного евклидова пространства Р. Вектор рєР ортогонален подпространству Pi тогда, когда он ортогонален любому вектору VH3 Pt.
Рассмотрим в пространстве Р некоторое m-мерное подпространство Р] и точку z, не принадлежащую Рь Опустим перпендикуляр из точки z на Рь т.е. найдем вектор zo из Р[ такой, что вектор р = z - z0 ортогонален Pi- Вектор z0 называется при этом ортогональной проекцией точки (вектора) z на подпространство Рь
Пусть базис подпространства Р\ состоит из векторов оь о2,... ,от. Вектор zo представляется в видегде коэффициенты ак находятся из условия ортогональности вектора р = z - zo кРь
В случае, когда базис О], о2, ... ,от - ортогональный и нормированный коэффициенты а вычисляются по формулам
Если базис только ортогональный, то коэффициенты ак вычисляются по формуламРассмотрим в исходном пространстве Р некоторое двумерное подпространство Р] и вектор z, не принадлежащий Pi. Пусть Pi - плоскость экрана. Опустим перпендикуляр из точки z на Рь т.е. найдем ортогональную проекцию zo вектора z на подпространство Рь
Пусть базис подпространства Р] состоит из векторов о{, о2 и пусть вектора oj и о2 имеют следующие координаты в n-мерном пространстве
Возьмем в качестве координат векторов Oj и о2 значения коэффициентов линейного преобразования (2.7), используемого при визуализации в методах L-и R-отображений. Вектора о\ и о2 линейно независимы, т.к. нельзя получить Oi из о2 умножением на константу ц, потому что
Синтез операционного автомата
Входным, выходным и внутренним переменным ставятся в соответствие регистры операционного автомата. Разрядность всех регистров - 32 бит.
Для ускорения арифметических операций сложения, вычитания и умножения применяется целочисленная арифметика. Данные с плавающей точкой представляются в виде двух 16-ти битных слов. Первое слово содержит целую часть исходного числа, второе - дробную часть исходного числа. Для получения такого представления целая часть исходного числа сдвигается влево на 16 бит, а дробная часть умножается на 65536 и прибавляется к результату. Получившиеся 32-х битные числа складываются и вычитаются обычным способом. После умножения таких чисел необходимо результат умножения (64-х битный) сдвинуть вправо на 16 бит. После деления необходимо результат сдвинуть влево на 16 бит.
Операции sin, cos целесообразно рассчитывать табличным методом, сохраняя данные в ПЗУ. При этом можно подготовить таблицы специально для целочисленной арифметики 32-х битных вещественных чисел, представленных в виде двух 16-ти битных целых чисел. Углы из градусной меры переводятся в 32-х битные целые числа. Получаем следующие константы:
В ПЗУ хранится таблица синусов для диапазона углов от 0 до 90 градусов. Значения для других углов вычисляются, используя 2 старших бита угла. Значения косинуса вычисляются по формуле:cos (angle) = sin (angle + 90).Таким образом, алгоритм работы устройства принимает следующий вид:
Определяем микрооперации, учитывая вырожденные микрооперации: установка 0, установка константы. Операционный автомат синтезируется в виде I-автомата, состоящего из блока регистров, шины результата Z, шин операндов SI, S2, комбинационной схемы 68
Управляющие сигналы у будут состоять из нескольких сигналов: as, bs, dz и f. Исключение составляют сигналы вырожденных микроопераций: уО,
Здесь обозначено: DIV - схема деления, MUL - умножитель, ADD - сумматор, SIN - схема синуса, SQRT - схема извлечения квадратного корня. Каждое арифметическое устройство имеет 2 выхода: RES - выход на шину результата Z, FIN - сигнал окончания работы операции. Общий выход FIN по 74ступает в управляющий автомат для разрешения перехода в следующее состояние. Управляющие сигналы f предназначены для запуска соответствующих арифметических блоков и для разрешения выхода арифметического устройства на шину результата.
Схема умножения представляет собой модифицированную схему параллельного синхронного умножителя, основанного на продукционном символьном умножении [97]. Структурная схема умножителя показана на рис. 3.9.
Рис, 3.9 Параллельный синхронный умножитель На рисунке обозначено: Rg X - регистр множимого, Rg Y - регистр множителя, ВМ - вычислительная матрица элементов, ФС - блок формирования сигнала остановки, СД - схема сдвига вправо на 16 бит, yl - сигнал загрузки регистров, у2 - сигнал формирования частичных произведений, уЗ -синхросигнал, у4 - сигнал остановки.
В начале работы умножителя подается сигнал yl, происходит загрузка регистров множимого и множителя. После подачи сигнала у2 в ячейках вычислительной матрицы элементов происходит формирование частичных произведений. В течение последующих тактов формируется результат произведения. Сдвиг результата вправо на 16 разрядов необходим вследствие целочисленного представления чисел с плавающей точкой. В конце блок остановки выдает сигнал окончания произведения. Всего требуется от 2 до 64 тактов для произведения.
Блок формирования сигнала остановки показан на рисунке ЗЛО. Рис. ЗЛО Блок формирования сигнала остановки
Схема ячейки вычислительной матрицы элементов основана на следующей системе подстановок для формирования произведения:хронный RS триггер, вследствие чего ячейка вычислительной матрицы эле Здесь обозначены: і - номер столбца, j - номер строки, Xj - і-й бит множимого, Yj - j-й бит множителя, Фд - бит опроса состояния ячейки (i, j), Sy - значение данных в ячейке (i, j).
Для хранения значения синуса используется ПЗУ размером 32 килобайт. Достаточно хранить только значения от 0 до ANG90. 32-й бит угла определяет знак синуса. 31-й бит определяет четверть координатной плоскости. Всего хранится 8129 значения угла (213). Для получения 13-ти битного адреса ПЗУ первые 30 бит угла сдвигаются вправо на 17 бит в блоке СД. Сигнал f4 является сигналом чтения из ПЗУ и одновременно является сигналом окончания. Первые 30 бит результата из ПЗУ инвертируются в блоке совокупности схем XOR (исключающее ИЛИ), если 31-й бит угла равен 1. Всего требуется 1 такт для получения значения синуса.
Схема извлечения квадратного корня из целого числа представляет собой операционный автомат, основанный на итерационной формуле Ньютона: Для целочисленного извлечения квадратного корня достаточно, чтобы x/y[i] было больше или равно у [і]. Число итераций определяется количеством значащих бит в двоичном представлении исходного числа. Для 32-х разрядного числа максимальное число итераций равно 31, так как 32-й знаковый бит можно не учитывать: извлечение корня ведется всегда из положительного числа.хема операционной части автомата извлечения квадратного корня представлена на рисунке 3.14.Рис. 3.14 Операционная часть схемы извлечения квадратного корня
На рисунке обозначены: DIV - схема деления, СМР - схема сравнения =, SUM - сумматор, MUX - мультиплексор, SHR - схема сдвига вправо на 1 бит, SHL - схема сдвига влево на 4 бита.Управляющая часть автомата извлечения квадратного корня представляет собой автомат Мура. Диаграмма состояний управляющего автомата представлена на рисунке 3.15
Сравнение временных характеристик синтезированного устройства с аналогами
Для сравнения временных характеристик устройства аналогами используются следующие параметры: п - мерность пространства, m - число точек n-мерного пространства.
Все устройства представляют собой масштабируемые архитектуры с несколькими процессорами или операционными блоками, поэтому время работы этих устройств линейно зависят от числа точек, и в ходе испытаний можно зафиксировать число точек.
С другой стороны каждое устройство имеет собственную реализацию алгоритма нелинейного отображения, в результате чего будут наблюдаться различные зависимости от мерности пространства. Алгоритм, применяемый в синтезируемом устройстве, выполняется быстрее алгоритмов, используемых у аналогов, вследствие расчета евклидового расстояния в одном цикле с линейным отображением.
Явным отличием синтезированного устройства является наличие функции отсечения гиперплоскостями для реализации нового метода секущих гиперплоскостей при анализе и распознавании протяженно распределенных классов.
Мультипроцессор распознавания образов [99] имеет средства для распознавания, основанные на расстояниях от начала координат до точки объекта распознавания и расстоянии от начала координат до границы класса.
Достоинством синтезированного устройства является потоковая загрузка входных данных вследствие применения итерационного алгоритма линейного преобразования. Это позволяет убрать ограничение на мерность пространства, т.е. используемая мерность пространства не ограничена памятью устройства.
В отличие от аналогов в синтезированном устройстве используется целочисленная арифметика (представление вещественных чисел в виде двух 16-ти битных слов), что позволяет сократить время выполнения арифметических операций, особенно операции вычисления квадратного корня.
Еще одним преимуществом синтезированного устройства является 32-х битное представление значения угла, которое сохраняет арифметические свойства углов и позволяет выполнить простую реализацию операции синус с использованием таблицы значений, хранящейся в ПЗУ, простым механизмом формирования адреса ПЗУ и прямое формирование знака синуса, что позволяет получать значение синуса за один такт и использовать ПЗУ малого объема.
Используемый в синтезированном устройстве параллельный синхронный умножитель, разработанный на основе умножителя [97], позволяет быстро выполнять произведения 32-х битных чисел.
Устройство извлечения квадратного корня, применяемое в синтезированном устройстве, основано на итерационной формуле Ньютона и, вследствие применения целочисленной арифметики, имеет небольшое число итераций до останова (равное количеству значащих бит в двоичном представлении числа, из которого извлекается корень), что обеспечивает меньшее время вычисления квадратного корня по сравнению с извлечением квадратного корня из вещественного числа.
В таблице 4.1 представлены времена работы синтезированного устройства и аналогов. Для синтезированного устройства представлены предельные (максимально возможные) времена работы. При испытаниях использовалось число точек n-мерного пространства m равное 28000.
Из таблицы и графика видно, что синтезированное устройство имеет превосходство над аналогами. При увеличении мерности пространства разность между временами работы синтезированного устройства и аналогов также увеличивается. Это происходит вследствие оптимизации алгоритма нелинейного отображения и сокращение итерационной части алгоритма, которая непосредственно зависит от мерности пространства.
На значениях п, меньших 40, синтезированное устройство проигрывает мультипроцессору.1. Рассмотрены устройства аналогичные синтезируемому устройству: устройство визуализации объектов n-мерного пространства и мультипроцессор распознавания образов.2. Измерены времена работы устройств при фиксированном числе объектов n-мерного пространства.3. Синтезируемое устройство имеет преимущество во времени работы, особенно проявляющееся на высоких значениях мерности пространства (п 40). 1. Для визуализации пространственно распределенных образов со сложными топологическими портретами разработан метод секущих гиперплоскостей как развитие существующего метода нелинейного отображения точек n-мерного пространства, заключающийся в отсечении части пространства двумя параллельными гиперплоскостями в местах n-мерного пространства, имеющего сложный топологических портрет.2. Исследованы особенности метода нелинейного отображения точки n-мерного пространства и получены аналитические выражения определения факта отсечения точки n-мерного пространства параллельными гиперплоскостями.3. Синтезирован алгоритм нелинейного отображения точек п-мерного пространства, который дополнен функциями отсечения точек n-мерного пространства для реализации метода секущих гиперплоскостей, что позволило сократить время визуализации объектов n-мерного пространства за счет уменьшения количества циклов вычислений.4. Разработано операционное устройство визуализации в виде I-автомата, реализующее алгоритм метода секущих гиперплоскостей, для визуализации пространственно распределенных образов со сложными топологическими портретами, создающее основу для организации параллельных вычислений с однородными операционными автоматами.5. В результате моделирования и сравнения с аналогичными устройствами визуализации разработанное операционное устройство имеет преимущество во времени работы, которое проявляется на значениях размерностипространства больших 40.
