автореферат диссертации по приборостроению, метрологии и информационно-измерительным приборам и системам, 05.11.16, диссертация на тему:Методы и средства компактного табличного представления и воспроизведения функций в информационно-измерительных системах

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

МЕТОДЫ И СРЕДСТВА КОМПАКТНОГО ТАБЛИЧНОГО ПРЕДСТАВЛЕНИЯ И ВОСПРОИЗВЕДЕНИЯ

ФУНКЦИЙ В ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ

05.11.16 - информационно-измерительные системы (в промышленности)

Автореферат диссертации на соискание ученой степени доктора технических наук

Рабинович Евгений Владимирович

На правах рукописи

УДК 681.3.014

Новосибирск - 1998

Работа выполнена в Новосибирском государственном техническом университете.

Научный консультант - Заслуженный деятель науки и техники РСФСР, действительный член Международной академии информатизации, почетный академик Метрологической академии, доктор технических наук, профессор М. П. Цапен-ко.

Официальные оппоненты: - д.т.н.. профессор Губарев В. В.

- д.ф.-м.н. Трофимов О. Е.

- д.т.н., профессор Хорошевский В. Г.

Ведущая организация - Институт вычислительной математики и математической геофизики СО РАН. (г. Новосибирск)

Защита состоится 16 июня 1998 г. в 10.00 часов на заседании диссертационного совета Д.063.34.08 при Новосибирском государственном техническом университете (630092, г. Новосибирск-92, пр. К. Маркса, 20).

С диссертацией можно ознакомиться в библиотеке НГТУ.

Автореферат разослан 15 апреля 1998 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент В. Л. Полубинскип

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

Термин "компактный"(плотный, сжатый), по-видимому, ясно отражает стремление к устранению всех форм избыточности, выбору оптимальных алгоритмов, рациональному использованию ресурсов технических средств, сжатому представлению данных, экономному построению программного обеспечения.

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

В измерительной технике применение табличного представления функций известно около 40 лет. Однако, широкого применения табличные методы не получили из-за трудности практической реализации таблиц большой емкости. Здесь можно назвать исследования М. П. Цапенко и О. В. Улина, работы В. И. Рабиновича по функциональным аналого-цифровым-преобразователям и др.

Исследования по применению табличных методов в вычислительной технике связаны с В. Б. Смоловым, Б. Н. Малиновским, И. Ф. Образцовым, руководимыми ими коллективами и др.

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

практическую реализацию устройств для воспроизведения функций самого широкого класса.

Уменьшение емкости памяти связано с устранением избыточности представления измерительных данных. Сюда можно отнести исследования, проводившиеся под руководством М. П. Цапенко (Ю. В. Носков, Н. В. Третьякова, Е. П. Дьяков и др.) в области построения аппроксимирующих измерительных систем и устройств.

Отечественные исследования по сжатию изображений представлены работами И. И. Цукермана, Л. П. Ярославского, В. М. Ефимова, 10. Н. Золотухина, А. Н. Колесникова, М. А. Старкова и др.

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

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

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

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

• разработка и исследование методов компактного представления таблиц функций самого широкого класса;

• разработка и исследование методов компактного представления двумерных массивов данных, сохраняющих с контролируемой точностью структуру и основные свойства исходных данных;

• создание принципов построения и структур таблично-опера-

ционных спецпроцессоров воспроизведения функций нескольких переменных и функций одной высокоразрядной переменной;

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

• разработка методик оценки быстр оде й ст в ия, точности и сложности табличных измерительно-вычислительных средств и алгоритмов;

• расчетная и экспериментальная проверка конкретных методов, алгоритмов и структур, предназначенных для построения информационно-измерительных систем.

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

Достоверность полученных теоретических результатов подтверждается математическим моделированием на ЭВМ и экспериментальной проверкой макетных образцов разработанных устройств.

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

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

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

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

описания изображений позволяют снижать сложность алгоритмов их обработки.

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

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

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

На защиту выносятся:

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

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

3. Принципы построения и структуры таблично-операционных спецпроцессоров.

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

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

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

мой "Микропроцессоры и михроЭВМ" (приказ Минвуза СССР N455 от 18.06.86, пункт 2.2), комплексной программой МАП и Минвуза РСФСР "Полет"и Всероссийской программой "Технические университеты", раздел 2.5. Связь. Проблемы информационного обмена.

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

Апробация работы. Основные положения диссертационной работы обсуждались в ряде организаций страны и докладывались на 12 международных, всесоюзных, и российских научно-технических конференциях и симпозиумах. На VI Всесоюзном симпозиуме "Проблемы автоматизации в прочностном эксперименте" (Новосибирск, 1986 г.), на Всесоюзной конференции "Методы и микроэлектронные средства цифрового преобразования и обработки сигналов" (Рига, 1986 г.), на Всесоюзной научно-технической конференции "Микропроцессорные системы автоматизации технологических процессов" (Новосибирск, 1987 г.), на VIII Всесоюзной научно-технической конференции "Измерительные информационные системы "ИИС-87"" (Ташкент, 1987 г.), на VI Всесоюзном симпозиуме "Проблемы создания преобразователей формы информации" (Киев, 1988 г.), на Региональной научно-технической конференции "Измерение характеристик случайных сигналов с применением микромашинных средств" (Новосибирск, 1988 г.), на IX Всесоюзной научно-технической конференции "Измерительные информационные системы "ИИС-89""(Ульяновск, 1989 г.), на Всесоюзной научно-технической конференции "Микропроцессорные системы автоматики" (Новосибирск, 1990 г.), на Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" (Новосибирск, 1994 г.), на Международной научно-технической конференции "Измерительные информационные системы"(Москва, 1994 г.), на Всероссийской научно-технической конференции "Электроника и информатика" (Москва, 1995 г.), на III Международной научно-технической конференции "Микропроцессорные системы автоматики" (Новосибирск, 1996 г.), на II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996 г.), на 4th UK/Australian International Symposium on DSP for Communication Systems (Perth, Australia, 1996), на 30th Annual Conference on Information Science and Systems (Princeton, USA, 1996), на Международной научно-технической конференции "Научные основы высоких технологий"(Новосибирск, 1997 г.).

Публикации. По теме диссертации опубликовано 31 работа, 8 отчетов по НИР и принята к опубликованию монография.

Объем и структура диссертации. Диссертационная работа состоит из' введения, 5 глав, заключения, двух приложений и содержит 212 страниц основного текста, 49 рисунков, 5 таблиц и список литературы из 120 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ ВВЕДЕНИЕ

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

ГЛАВА 1. ОСНОВЫ ТАБЛИЧНОГО ПРЕДСТАВЛЕНИЯ

ФУНКЦИЙ

В главе даны основные определения и сделан краткий очерк современного состояния табличного представления данных и методов сокращения емкости табличных устройств памяти. Рассмотрены достоинства и перспективы использования табличного представления информации для достижения заданных характеристик информационно-измерительных систем [1,2,3,15,21].

Набор (таблица) цифровых отсчетов непрерывного сигнала, распределенного во времени или в пространстве, полученный в результате дискретизации, квантования и кодирования измеряемой величины, является формой цифрового описания аналогового сигнала.

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

S(t)

t е JR5 = {f G R : |i| - £ utj 6 {0,1}}, j=i

где S(t) ~ количество разрядов в двоичном представлении числа t, R - множество действительных чисел.

Табличным представлением вещественной функции /(.-г), х 6 [я, Ь] будем называть конечное упорядоченное множество Г(/; е) вещественных чисел /; (t = 0,..., N), при помощи которого воспроизводящий алгоритм R(f) формирует с погрешностью, не превышающей е > 0, приближенное значение функции f(x) на отрезке [а, Ъ].

Информационной емкостью С(/) таблицы функции будем называть количество двоичных разрядов, необходимое для записи всех элементов множества 71(/;г). Информационная емкость таблицы определяется выражением С(/) = Л(/)5'(/), где А(/) - мощность множества 71(/;е) - адресное пространство (количество ячеек) таблицы; 5(/) - разрядность элементов /; 6 Т(/;е), выбираемая исходя из заданной точности воспроизведения функции.

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

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

ГЛАВА 2. КОМПАКТНОЕ ТАБЛИЧНОЕ ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПРОЦЕССЕ ИЗМЕРЕНИЯ

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

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

Функциональные аналого-цифровые преобразователи. Заслуживают серьезного внимания функциональные аналого-цифровые преобразователи, получающие цифровые значения функции у = *р{Х) при уравновешивании непрерывной переменной X образцовой величиной, формируемой с помощью таблицы функции х — <р~1(у), обратной функции у. Применение таблиц обратных функ-

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

V

Рис. 1

Разработаны и исследованы принципы построения и структуры аналого-цифровых преобразователей, обеспечивающих реализацию функциональной композиции вида [13,17]

у = <Рз(Ь(*я) 0 ЫЪ)), (1)

где - аналоговая переменная, - цифровая, а символ 0 обозначает бинарную операцию. Функция Л - произвольная, а щ и

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

Структура, отвечающая (1), показана на Рис. 1, ее особенность

— двукратное использование таблиц обратных функций <р\1(у) и УгЧ^Г'Су) ® /¡(хг)). Здесь символ ® обозначает бинарную опера-

цию, обратную 0, блок F - устройство, ее реализующее, а - г-й разрядный коэффициент у.

В каждом такте уравновешивания в регистре последовательных приближений SAR формируется текущее значение у, код которого поступает на ПЗУ ROM в качестве адреса. Хранящееся в ПЗУ соответствующее значение функции <Р\1(у) и значение функции h(x2) цифровой переменной извлеченное из собственной таблицы, поступают в блок F, где вычисляется адрес в таблице функции

l{iPi1{y) ® h(xi))- Величина X] уравновешивается аналоговым эквивалентом функции <р% 1(у), что фиксируется компаратором СМР. По окончании всех тактов уравновешивания в SAR хранится значение у.

Отметим, что имеется возможность в (1) использовать функции вида у = <р( 1/Х) и у = <p(Xi¡Х2).

Аналого-цифровые препроцессоры. Приводятся результаты разработки и исследования принципов построения и структур аналого-цифровых препроцессоров, осуществляющих основные процедуры цифровой обработки сигналов (дискретное ортогональное преобразование, нерекурсивную фильтрацию, свертку) во время аналого-цифрового преобразования [10,17].

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

Математической основой для реализации алгоритмов дискретной обработки'в процессе поразрядного уравновешивания аналогового сигнала является выражение для "текущего"произведения т-го отсчета сигнала Х\ на табличную константу hn — h(x2)

у(т)к - y(m)k-i + КиХк2~к, к = 1,... ,S(x), (2)

которое при к = S(x) дает требуемый результат. Выражение (2) показывает, что искомое произведение у{т) — hnx(m), являющееся результатом соответствующих подстановок в (1), формируется

потактно в темпе поразрядного уравновешивания. Если в текущем такте разрядный коэффициент иХк = 1, то выполняются операции сдвига табличной константы 1гп и сложения.

Аппаратурная основа воплощения структуры Рис. 1 для реализации (2) состоит из регистра сдвига и накапливающего сумматора.

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

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

ГЛАВА 3. КОМПАКТНОЕ ТАБЛИЧНОЕ ПРЕДСТАВЛЕНИЕ СЛОЖНЫХ ФУНКЦИЙ

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

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

Основы метода представления таблицы функции нескольких переменных в виде совокупности таблиц функций одной переменной. Для табличного представления функции /(х\,х2, • ■ •, хп) необходима таблица, адресное пространство которой равно

Л(/) =

Очевидно, что информационная емкость таблицы С(/), пропорциональная А(/), растет с увеличением числа переменных п, как показательная функция с натуральным показателем. Кроме того, С(/) зависит от разрядности Э{х{) входных переменных ж,-, увеличение которой на один бит удваивает А{}). Отсюда можно заключить, что

наибольшую трудность для табулирования представляют функции нескольких высокоразрядных: аргументов.

Автором предложен метод расщепления функций [5,6,16,18], обеспечивающий возможность применения ПЗУ для табулирования функций, непосредственное табулирование которых практически невозможно (из-за чрезмерной потребности в емкости памяти). При помощи метода расщепления эти функции представляются в виде вспомогательных функций, имеющих таблицы доступной суммарной емкости.

Суть метода' расщепления функций заключается в представлении частичной суммы кратного степенного ряда, аппроксимирующего функцию нескольких переменных, в виде суммы вспомогательных полиномов одной переменной. Возможность такого компактного представления следует из известной теоремы, доказанной А. Н. Колмогоровым и В. И. Арнольдом, которая утверждает, что всякая непрерывная функция п переменных (а следовательно, и всякая аналитическая функция) может быть представлена в виде суперпозиции непрерывных функций одного переменного и операции сложения.

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

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

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

Рассматриваемый метод является конструктивным в силу того,

что для всех функций, определенного выше класса, дает конкретный алгоритм расщепления.

Расщепление функций двух переменных. Обратимся к математическим аспектам метода расщепления функций двух переменных f(xи Xi) [6].

Пусть (Ь,М)-я частичная сумма степенного ряда

L М

f(x1,x2)~ £ £ ainxix?. (3)

1=0 m=0

аппроксимирует с заданной точностью е функцию f(x 1,12). Адресное пространство таблицы T(f\e) равно Ar(f) = 22SÍ1'.

Представление суммы (3) в виде суммы вспомогательных полиномов Pj(zj), j = 0,..., N, каждый из которых образован собственной переменной zj, обеспечивает сокращение адресного пространства. Получено соотношение

L м N

f{xux2) ~ £ £ аыхр? = Т,рЛъ)> (4)

/=0 т=0 j=0

где N — L + М, а полиномы Pj(zj) имеют вид N

Pjizi) = И Ckj((XjiXi + <Xj2X2) , j = o,..., N, (5)

fc=j

где c¿j\, Qy2 - константы, удовлетворяющие условию

сXjl<Xm2 ф 3 ф j,m = 0,...,k, (6)

а коэффициенты су являются решением систем уравнений, связывающих коэффициенты при степенях мономов х\х™ и биномов (аяХ1 + aj2x2)k.

Суммарное адресное пространство таблиц многочленов pj, необходимых для расщепления функции f(xi,xz) согласно (4), определяется равенством

A(f) = í 2S{X)+&S>,

где ASj — f|log2(o;j-i +0^2)!], a fí] обозначает целое, большее или равное действительного числа t.

Очевидно, что выбор констант ад и а^ влияет на размер A(f). Выбирая, с учетом условия (6), значения aj 1 и aj2 из ряда наименьших положительных целых чисел удается минимизировать ASj. Для N = 6 эти значения приведены в Таблице.

j 0 1 2 3 4 5 6

ад 0 1 1 1 1 2 3

<*j2 1 0 1 2 3 1 1

Выигрыш п адресном пространстве таблиц при табулировании расщепленной функции /(жь^г), по сравнению с непосредственным табулированием этой функции, равен

' 3=0

Например, при N = б, S(x) = 12, выигрыш ¿?(12,6) = 205.

Таким образом, применение расщепления функции j(xi,xi) позволяет значительно (так как обычно S(x) ASj) сократить адресное пространство таблиц для воспроизведения данной функции и, тем самым, уменьшить емкость запоминающего устройства C(f).

Рассмотрены варианты метода расщепления и его обобщение для функций п переменных.

Расщепление функций высокоразрядных аргументов. Сегментация высокоразрядного аргумента х функции f(x) позволяет применить метод расщепления для сокращения адресного пространства таблиц, необходимых для таблично-операционного воспроизведения данной функции [5].

Представим высокоразрядный аргумент х € Rs в виде

® = «1 + хи xi € R5/2, (7)

где ï\ и %2 - сегменты.

Пусть функция f(x) аппроксимируется с точностью s N-и частичной суммой степенного ряда

f(x) = •£ скхк, (8)

4=0

тогда при подстановке (7) в (8) и ряде преобразований, аналогичных примененным в случае функций двух переменных, можно получить.

/(*) = (9)

1=0

где полиномы определяются формулой (5) при замене Х\ и Х2 на XI и %2-

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

Пусть х £ тогда

Х^ЕЗ«^, (10)

¿=1

Подставляя (10) в выражение (9) для /(х), получим функцию тг переменных, расщепление которой можно использовать для дальнейшего сокращения адресного пространства таблиц функции /(ж). В этом случае выигрыш в адресном пространстве становится весьма значительным. Например, при N = б, 3(х) — 12 и числе сегментов п = 3, выигрыш <3(12,6,3) = 138654,6.

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

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

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

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

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

пения [8,9].

Блок-схема алгоритма воспроизведения функции /(хх, х?) изображена на Рис. 2. Переменные и х2 подаются на блок ЕА, форми-

XI

Х2

FA

2

i=l

¿0

ZN

ROM

Pj(zi) j = 0~N

Po

Pi

■Pn

SM

N , \/(яъ*2)

J=0

Рис. 2

рующий адреса Zj. По этим адресам из соответствующих таблиц N -f 1 блоков ROM извлекаются N +1 кодов, которые суммируются в блоке SM. Результат округляется согласно заданным требованиям к точности воспроизведения функции f{x\,xj).

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

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

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

п Si = (n!2"_I)_1

i=l j-о 1=1

где £ {0,1} - инверсное значение г-го разрядного коэффициента в двоичном представлении индекса j. Дана методика расчета основных параметров схемы умножителя п чисел.

Рассматривается применение таблично-операционного воспроизведения функций в измерительно-вычислительных системах с универсальными ЭВМ. Такое применение связано с выполнением в реальном времени заранее известных алгоритмов управления, входными параметрами которых являются результаты измерений.

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

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

ГЛАВА 4. КОМПАКТНОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЙ

Компактное представление изображений имеет огромное значение, как средство повышения эффективности систем обработки, хранения и передачи видеоинформации.

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

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

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

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

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

жен и исследован ряд алгоритмов, основанный на методе адаптивной кусочно-полиномиальной аппроксимации (АКА). Необходимость адаптивного подхода диктуется наличием нестационарности, пространственной и частотной анизотропии, отсутствием гладкости и разрывностью данных натурных экспериментов, полевых измерений, цифровых изображений [19,20]. Такой подход обладает значительно меньшей вычислительной сложностью, по сравнению с методами аппроксимации на больших отрезках приближения, исследованными Ю. В. Носковым.

Предлагаемые алгоритмы АКА основаны на следующих видах адаптации - по длине отрезка приближения, по степени полинома и по применяемой системе'базисных функций (используются ортогональные квадратические полиномы Чебышева для равноотстоящих точек либо дельта-функции Кронекера). Суть сжатия заключается в поиске аппроксимирующих полиномов минимальной степени, заданных на отрезках приближения максимальной длины и хранении параметров аппроксимации вместо значений пикселов изображения на данном отрезке. Чем больше пикселов содержится на отрезке аппроксимации, тем выше степень сжатия. Если приближение с заданной точностью невозможно, то значения выделяющихся пикселов сохраняется при помощи дельта-функций Кронекера [22 - 27].

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

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

Рекурсивный алгоритм построения кривой Гильберта заключается в непрерывном обходе всех смежных точек дискретного квадрата,

о--о

6 о

охватывающего изображение, начиная с квадрата 2x2 пикселов и завершая квадратом максимального размера. Кривые Гильберта 1, 2 и 6-го порядков изображены на Рис. 3. Стрелками указано направление обхода пикселов изображения. В результате обхода изображения по траектории, заданной кривой Гильберта, локальные пространственные однородности сигнала интенсивности "разматываются"в протяженные гладкие отрезки приближения. Следовательно, одним полиномом может быть аппроксимировано большее количество отсчетов сигнала интенсивности.

На первом этапе сжатия компактное описание изображения обеспечивается заменой функции /(х) кусочной функцией д(х), которая задается на отрезке, состоящем из N + 1 точек, с помощью М (М < Ы) независимых числовых параметров и приближает }{х) с наперед заданной среднеквадратической погрешностью а > 0. Функция д{х) состоит из последовательно расположенных на отрезке [О, /V] "кусков"^(г), j = 0,..., /. Используются "куски"двух типов. Первый тип представляют полиномы степеней не выше второй, заданные в к+ 1 (к И) точках и приближающие "кусок"функции /(я) с погрешностью а. Второй тип представляют отсчеты функции }(х) в точках, где ее не удалось приблизить полиномами.

Сегментом приближения будем называть набор параметров, описывающий сигнал на отрезке приближения. Сегмент состоит из значений аппроксимирующего полинома, число которых определяется степенью полинома, индекса сегмента (степени полинома) и длины отрезка. Одноточечные сегменты состоят только из значения пиксела и индекса (3).

Алгоритм адаптивной аппроксимации ортогональными полиномами Чебышева для равноотстоящих точек и дельта-функциями

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

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

Выделенная из последовательности сегментов приближения подпоследовательность одноточечных сегментов состоит из пикселов двух типов. Это либо отдельные пикселы, разделенные гладкими участками изображения, либо смежные пикселы, но тогда их интенсивности значительно различаются, так как не удалось произвести их сглаживание на отрезке из четырех точек. Данная подпоследовательность фактически описывает модель контурных элементов изображения. Расположение этих элементов определяется естественным порядком следования сегментов приближения, поэтому не требуется затрат на локализацию контуров.

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

На втором этапе сжатия осуществляется снижение психофизиологической избыточности за счет использования различного числа

бит для описания хорошо и плохо воспринимаемых глазом изменений интенсивности изображения. Это достигается переквантованием (уменьшением разрядности) последовательности контурных элементов изображения. Для формирования малоразрядной последовательности, близкой к оптимальной по качеству приближения к контурной последовательности применен прием, основанный на кодировании контурной последовательности решетчатым кодом Унгербоеха и декодировании по алгоритму Витерби.

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

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

Предлагаемое компактное представление изображения содержит раздельное описание контуров и текстуры изображения, что позволяет использовать его для прогрессивной передачи и векторного квантования изображений.

Полученное при помощи алгоритма АКА компактное представление изображения состоит из отсчетов полиномов, приближающих сигнал интенсивности, и его истинных отсчетов (одноточечных сегментов). Поэтому оно сохраняет практически все характерные свойства исходного представления изображения, отличаясь от него только тем, что избыточные, в рамках заданной точности, отсчеты сигнала интенсивности оказываются опущенными.

В результате сжатия и воспроизведения изображения мелкие шумовые колебания исходного сигнала интенсивности оказываются сглаженными на воспроизведенном изображении, в то время как и высокочастотные, и низкочастотные колебания, характеризующие неслучайную составляющую сигнала, описываются с заданной точностью. Это хорошо видно на Рис. 4, где изображены одномерный 160-ти пикселный фрагмент сигнала интенсивности популярного тестового изображения "Ьеппа"и наложенный на него фрагмент воспроизведенного сигнала. Воспроизведение выполнялось после сжатия изображения с коэффициентом сжатия 12.

Для изображения "Ьеппа"на Рис. 5 приводится сводный график зависимостей пикового отношения сигнала к шуму (Р8К11) от отношения бит на пиксел (ВРР) для нескольких алгоритмов сжатия. Эти зависимости отражают общепризнанный (но далекий от идеала) критерий качества алгоритмов сжатия, заключающийся в оценке среднего уровня искажений воспроизведенного изображения при одинаковой степени сжатия. Зависимости а) и б) относятся к алгоритму полосового кодирования, в) - алгоритму дифференциального векторного квантования, г) и д) - к алгоритму "приоритетного"дискретного косинусного преобразования (ДКП). Описания алгоритмов и ссылки на соответствующие источники имеются в Приложении А. Зависимость ж) получена в результате тестирования алгоритма АКА.

Анализ зависимостей показывает, что при равном качестве воспроизведения расход бит на представление пиксела у алгоритма АКА ниже, чем у некоторых других алгоритмов. В области сильного сжатия (ВРР ~ 0.5) он практически не уступает и более мощным, но

РЭШ

т 35

30

г

д

ж

а

б Б

О.З

1.5

ВРР Рис. 5

необладающим перечисленными выше свойствами методам.

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

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

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

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

ГЛАВА 5. ПРИМЕНЕНИЕ ПРЕДЛОЖЕННЫХ МЕТОДОВ И СРЕДСТВ ТАБЛИЧНОГО ПРЕДСТАВЛЕНИЯ ФУНКЦИЙ

Методы компактного табличного представления и воспроизведения функций ни в коей мере не призваны заменить собой операционные методы и средства вычислительной техники. Они используются как дополнение, снижающее нагрузку или ускоряющее традиционную обработку, в тех сложных ситуациях, когда требуются высокие точность и скорость процедур измерения и обработки, когда преобразуются сверхбольшие объемы данных. Такие ситуации связаны, как правило, с невозможностью использования в натурном эксперименте дорогих высокопроизводительных универсальных ЭВМ, с необходимостью многократного повторного решения однотипных специальных задач в автоматических системах управления и массового медицинского обследования, с использованием возможности предварительной обработки за рамками реального времени, с устранением различных форм избыточности.

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

Табличная аппроксимирующая измерительная система реального времени. Создана многоканальная система, предназначенная для аппроксимации 32-мя ортогональными полиномами Че-бышева для равноотстоящих узлов телеметрических сигналов, заданных на 512-ти точечных интервалах [4,11,12].

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

Система построена по модульному принципу, при этом каждый модуль обслуживает 8 каналов и содержит 8-ми разрядный аналого-цифровой преобразователь с коммутатором, табличный блок, хранящий значения полиномов Чебышева для всех точек интервала, и накапливающий сумматор с аккумулятором в виде ОЗУ. Обработка одного отсчета входного сигнала осуществляется за 250 - 300 не, при верхней частоте сигнала 4 кГц. Среднеквадратическая погрешность аппроксимации не превышает 1%.

Таблично-операционное преобразование систем координат в контуре управления. Описана реализация таблично-операционного воспроизведения функций в системе числового программного управления металлорежущим станком нетрадиционной компоновки [7,14]. Воспроизведение функций г/1 = у/х, У2 = я2, уг = агс^х применяется для преобразования координатных систем станка, которое необходимо выполнить с высокой точностью в реальном режиме времени. В рамках заданных условий по точности и быстродействию микропрограммная реализация указанных функций является весьма проблематичной, в то время как предложенное устройство с запасом, позволяющим оптимизировать структурные решения, дает необходимый результат.

Упрощенно конструкцию станка можно представить в виде платформы, шарнирно укрепленной на шести "ногах", длина которых может изменяться. На платформе установлен режущий инструмент, а обрабатываемая деталь располагается в пространстве между "ногами" станка. Зона действия инструмента ограничена сферой с радиусом 0,5 м. Так как в системе числового программного управления станком погрешность линейных перемещений равна 1мкм, то преобразование координат необходимо выполнять при использовании 20-ти разрядных двоичных чисел с фиксированной запятой.

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

натных систем станка выполняет таблично-операционный конвейерный микропрограммный спецпроцессор.

Выбор конвейерной структуры обусловлен запасом времени, предоставляемым таблично-операционным алгоритмом, и требованием к минимизации аппаратурных затрат. В условиях применения микросхем ТТЛ-серий время воспроизведения функций у\, т/3 занимает от 2,4 до 8,8мкс.

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

Сейсмограмма имеет вид двумерного числового массива, описывающегося моделью, напоминающей модель изображения. Здесь отсчеты трассы сейсмограммы, также как и отсчеты сигнала интенсивности изображения, составляют строки двумерного массива. Такое представление сейсмограмм-изображений позволяет применить к ним алгоритм АКА сжатия изображений.

Фрагмент реальной сейсмограммы был представлен в виде изображения, в котором вместо строк сигнала интенсивности использованы трассы сейсмограммы. В правой части Рис. 6 для иллюстрации приведено это "изображение". Оно было сжато в 10 раз и воспроизведено. Слева на Рис. 6 традиционным образом, в масштабе, изображен исходный фрагмент сейсмограммы, содержащей 48 трасс (отображена каждая вторая) по 1250 отсчетов и наложенный на него воспроизведенный фрагмент.

Расстояние между сейсмоприемниками, откладываемое по горизонтали, называется выносом (offset) и измеряется в метрах. По вертикали откладывается время регистрации колебаний (time), измеряемое в секундах. На временах около 1.2 сек. и выносах 30, 50 м. в отмеченных, а также в некоторых других частях сейсмограммы можно заметить различие в исходной и воспроизведенной трассах.

о Г Р я в ± Сл_> в 5В 100 150 280

Рис. 6

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

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

Самостоятельное значение для сеймических и сейсмологических исследований имеет эффективное сжатие результатов полевых наблюдений.

Обработка медицинских рентгеновских изображений.

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

Для медицинского исследования рентгеновских изображений интерес представляют отдельные фрагменты и детали рентгенограм-

мы, характеризующие состояние здоровья пациента. Типичная ситуация заключается в выявлении наличия, анализе интенсивности, размеров и расположения таких деталей относительно других менее важных или несущественных деталей. Рентгенолог может задать области, в которых располагаются важные детали изображения, и с помощью алгоритма АКА обработать и сжать данные, относящиеся к этим областям, с невысоким коэффициентом сжатия или вообще не сжимать, а остальное пространство изображения сжать сильно.

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

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

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

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

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

нат. В результате такой предварительной обработки отпадает необходимость выполнения ряда процедур в реальном масштабе времени, экономится время дизайнера.

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

Следует отметить, что процедуры преобразования систем цветовых координат эффективно выполняются таблично-операционным алгоритмом, реализованным в специальной СБИС.

Моделирование методов проводилось на 9 тестовых изображениях фирмы БСГГЕХ (Израиль), одного из лидеров в производстве полиграфических компьютерных систем. Размеры тестовых изображений составляют от 37 до 73 мегабайт. Результаты моделирования подтвердили возможность применения предложенных методов, все необходимые для внедрения материалы переданы фирме БСГГЕХ.

ПРИЛОЖЕНИЯ

В Приложении А дается обзор методов сжатия изображений. Приложение Б содержит сведения о внедрении результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

Диссертация содержит следующие основные результаты исследований, проведенных в 1984 - 1997 годах.

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

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

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

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

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

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

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

• На основе применения табличного представления и воспроизведения функций разработаны и внедрены:

— Табличная аппроксимирующая система реального времени, обеспечивающая приближение сигналов, заданных на 512-ти точечных отрезках, при помощи 32-х ортогональных полиномов Чебышева для равноотстоящих узлов. Среднеквадратическая погрешность аппроксимации не превышает 1%.

— Таблично-операционный спецпроцессор преобразования координат для управления работой металлорежущего станка нетрадиционной компоновки. В условиях применения микросхем ТТЛ-серий выполняется воспроизведение нескольких функций 20-ти разрядных аргументов за время меньшее 2 - 8,8 мкс.

- Метод компактного представления сейсмических данных, позволяющий с допустимой погрешностью производить обработку сжатых данных вместо исходных, что снижает сложность алгоритмов обработки. Уменьшение объема вычислений пропорционально степени сжатия сейсмограммы (8 - 16 раз).

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Основное содержание диссертации опубликовано в следующих работах:

1. Рабинович Е. В. Применение таблично-операционных устройств в ИВС // Измерительно-вычислительные системы. Теория и реализация: Межвуз. сб. научн. трудов / Новосиб. электротехн. йн-т; - Новосибирск. - 1986. - С. 152 - 160.

2. Рабинович В. И., Рабинович Е. В., Цапенко М. П. "Развитие табличных методов, применяемых в измерительно-вычислительных системах прочностного эксперимента // Проблемы автоматизации в прочностном эксперименте: Труды VI Всесоюзн. симпозиума - Новосибирск. - 1986. - С. 252 - 255.

3. Рабинович В. И., Рабинович Е. В., Худомясов А. В., Цапенко М. П. Применение табличных методов для реализации алгоритмов преобразования и обработки информации // Методы и микроэлектронные средства цифрового преобразования и обработки сигналов: Тез. докл. Всесоюзн. научн.-техн. конф. - Рига. -1986. - Т.1. - С. 213 - 216.

4. Носков Ю. В., Рабинович Е. В., Худомясов А. В. Исследование и разработка алгоритма аппроксимации для быстроменяющихся процессов, основанного на таблично-операционных методах // ЦНТИ "Поиск". - Сер. XII. - Вып. 2. М., - 1986. - С. 31 - 43.

5. Рабинович Е. В. Применение метода расщепления для высокоточного таблично-операционного воспроизведения функций. -Новосибирск. - 1987. - 11с. - Деп. в ВИНИТИ 03.03.87, N1544-В87 Деп.

6. Рабинович Е. В. Применение метода расщепления для таблично-операционного воспроизведения функций нескольких переменных. - Новосибирск. - 1987. - 13с. - Деп. в ВИНИТИ 02.04.87, Ш390-В87 Деп.

7. Рабинович Е. В., Ухин Н. И., Хомяков В. В., Цабель Г. Э. Таблично-операционное микропроцессорное устройство преобразования координат для нетрадиционного станка с ЧПУ // Микропроцессорные системы автоматизации технологических процессов: Тез. докл. Всесоюзн. научн.-техн. конф. - Новосибирск. - 1987. - С. 165 - 166.

8. Рабинович Е. В., Худомясов А. В., Цапенко М. П. Таблично-операционное преобразование функций в измерительно-вычислительных системах // Измерительные информационные системы "ИВС-87": Тез. докл. Всесоюзн. научн.-техн. конф. -Ташкент. - 1987. Т.2. С.5.

9. Рабинович Е. В., Худомясов А. В. Таблично-операционное умножение синусоидальных функций // Измерительно-информационные системы и их элементы. Алгоритмы и структуры: Межвуз.' сб. научн. трудов / Новосиб. электротехн. ин-т. -Новосибирск. - 1987. - С. 86 - 91.

10. Рабинович Е. В., Фихман М. И., Цапенко М. П. Аналого-цифровые процессоры, использующие табличное представление образцовой величины // Проблемы создания преобразователей формы информации: Труды VI Всесоюзн. симпозиума - Киев. - 1988. - С. 202 - 203.

И. Долгов А. В., Кот М. Г., Рабинович Е. В., Худомясов А. В.,

Цапенко М. П. Таблично-операционная микропроцессорная аппроксимирующая система (ТОМАС) // Измерение характеристик случайных сигналов с применением микромашинных средств: Тез. докл. Регионал. научн.-техн. конф. - Новосибирск. - 1988. - С. 168.

12. Кот М. Г., Носков Ю, Л., Рабинович Е. В., Худомясов А. В., Цапенко М. П. Методы адаптивной аппроксимации в измерительных системах // Измерительные информационные системы: Тез. докл. Всесоюз. научн.-техн. конф. - Ульяновск: НПК УЦМ, - 1989. - Ч. 1. - С. 27 - 28.

13. Рабинович Е. В. Использование табличного представления функций для аналого-цифрового преобразования // Цифровая информационно-измерительная техника: Межвуз. сб. научн. трудов /Пензенский политехи, ин-т. - Пенза. - 1989. - С. 21 -26.

14. Рабинович Е. В. Применение табличного представления функций для преобразования координат в системе ЧПУ станка нетрадиционной компоновки // Измерительно-вычислительные системы и их элементы: Межвуз. сб. научн. трудов / Но-восиб. электротехн. ин-т. - Новосибирск. - 1989. - С. 106 -112.

15. Рабинович Е. В. Проблемы табличной обработки сигналов // Микропроцессорные системы автоматики: Тез. докл. Всесоюз. научн.-техн. конф. - Новосибирск. - 1990. - С. 168.

16. Рабинович Е. В. Сокращение емкости таблиц функций двух высокоразрядных аргументов //Измерительно-вычислительные системы и их элементы: Межвуз. сб. научн. трудов / Но-восиб. электротехн. ин-т. - Новосибирск. - 1990. - С. 61 -66.

17. Рабинович Е. В., Цапенко М. П. Табличные аналого-цифровые преобразователи и процессоры // Автометрия. - 1992.- N6.-С.31 - 37.

18. Рабинович Е. В. Компактное представление сложных для табулирования функций (Метод расщепления функций) // Автометрия. - 1992,- N6.- С.38-44.

19. Рабинович Е. В., Рубан А. А., Цапенко М. П., Шефель Г. С. Адаптивная кусочно-линейная аппроксимация // Автометрия. - 1993.- N1,- С.26 - 29.

20. Рабинович Ё. В., Рубан А. А., Цапенко М. П., Шефель Г. С. Алгоритмы адаптивной кусочно-полиномиальной аппроксимации

и Автометрия. - 1993.- N1. - С.ЗО - 34.

21. Рабинович Е. В., Цапенко М. П. Табличные преобразователи при контроле и диагностировании //Приборы и системы управления. - 1993. - N5. - С. 19 - 20.

22. Рабинович Е. В. Компактное представление изображений при помощи адаптивной аппроксимации // Информатика и проблемы телекоммуникаций: Тез. докл. Российск. научн.-техн. конф. - Новосибирск. - 1994. - С. 117.

23. Рабинович Е. В. Применение адаптивной аппроксимации для компактного представления изображений // Измерительные информационные системы: Тез. докл. Междукародк. каучп.-техн. конф. - Москва. - 1994. - С. 31.

24. Рабинович Е. В. Адаптивный алгоритм сжатия изображений // Электроника и информатика - 95: Тез. докл. Всероссийск. научн.-техн. конф. - Москва. - 1995. - С. 326,

25. Рабинович Е. В. Адаптивный алгоритм сжатия изображений // Микропроцессорные системы автоматики: Матер. III между и. научн.-техн. конф. - Новосибирск. НГТУ. - 1996. - С. F20 -F21.

26. Рабинович Е. В. Компактное описание изображений // Инженерная математика: Тез. докл. II Сибирский Конгресс по прикладной и индустриальной математике. - Новосибирск. - 1996. - С. 230.

27. Рабинович Е. В. Использование кусочно-полиномиальной аппроксимации для сжатия изображений // Автометрия. - 1996.-N2,- С.64-70.

28. Rabinovich Е. V. Compact image representation based on adaptive polynomial approximation //in Proc. 4th. UK/Australian Internat. Symp. DSP Communie. Systems, Perth, Sep. 1996.

29. Rabinovich E. V. Adaptive polynomial approximation for image compression // in Proc. Conf. Inform. Sciences and Systems, Princeton, NJ, Mar. 1996.

30. Рабинович E. В. Компактное описание одномерного представления изображений // Автометрия. - 1997.- N2,- С. 87 - 93.

31. Рабинович Е. В., Кузюрин Д. В. Одномерное представление для сжатия изображений // Научные основы высоких технологий: Труды междун. научн.-техн. конф. - Новосибирск. НГТУ. -1997. - Т.2. - С. 173 - 176.



Шу

НОВОСИБИРСКИМ

«с я

',М А ¡1л

<Х0 Н

ОКТОРА

наук

И ТЕХНИЧЕСКИЙ

На правах рукописи

Ч ;-,1яВАКг ССИИ

__«Л :

Рабинович. Евгений Владимирович

МЕТОДЫ И СРЕДСТВА КОМПАКТНОГО ТАБЛИЧНОГО ПРЕДСТАВЛЕНИЯ И ВОСПРОИЗВЕДЕНИЯ

ФУНКЦИЙ В ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ

СИСТЕМАХ

05.11.16 - информационно-измерительные системы (в промышленности)

Диссертация на соискание ученой степени доктора технических наук

Новосибирск - 1998

Оглавление

Обозначения 4

Введение 7

Глава 1 Основы табличного представления функций 23

1.1. Основные понятия и определения........................25

1.2. Современное состояние табличных средств преобразования информации..........................................29

1.2.1. Табличное представление функций в информационно-измерительных системах......... 29

1.2.2. Обзор методов построения табличных устройств и сокращения емкости памяти .... 35

1.3. Оценка сложности и погрешностей табличного представления функций .................... 52

1.3.1. Оценка сложности табличного представления функций....................... 53

1.3.2. Расчет погрешностей табличных преобразователей ........................ 57

Глава 2 Компактное табличное представление данных в процессе измерения 63 2.1. Совмещение процедур аналого-цифрового преобразования и обработки данных ................. 65

2.1.1. Применение таблиц обратных функций..... 66

2.1.2. Арифметические операции в процессе поразрядного уравновешивания .............. 70

2.2. Табличные средства измерения и первичной обработки

данных........................... 73

2.2.1. Функциональные аналого-цифровые преобразователи ........................ 73

2.2.2. Аналого-цифровые препроцессоры........ 77

Глава 3 Компактное табличное представление сложных функций 83

3.1. Метод расщепления функций............... 84

3.1.1. Расщепление функций нескольких переменных 84

3.1.2. Расщепление функции одной высокоразрядной переменной..................... 91

3.2. Таблично-операционные алгоритмы и структуры устройств, основанных на методе расщепления функций 95

3.2.1. Воспроизведение функций двух переменных . . 95

3.2.2. Воспроизведение функций одной высокоразрядной переменной...................103

3.3. Таблично-операционные средства обработки измерительных данных......................105

3.3.1. Таблично-операционный умножитель нескольких сомножителей.................107

3.3.2. Таблично-операционные специализированные процессоры.....................114

3.3.3. Таблично-операционное преобразование на ЭВМ 123

Глава 4 Компактное представление изображений 127

4.1. Адаптивная кусочная аппроксимация функций.....129

4.1.1. Адаптивная кусочно-линейная аппроксимация . 130

4.1.2. Алгоритмы адаптивной кусочно-полиномиальной аппроксимации................135

4.2. Средства получения компактного представления изображений ..........................143

4.2.1. Адаптивный кусочно-аппроксимационный алгоритм сжатия изображений............147

4.2.2. Сочетание алгоритма адаптивной кусочной аппроксимации с другими методами сжатия изображений ......................166

Глава 5 Применение предложенных методов и средств

табличного представления функций 177

5.1. Полиномиальная аппроксимация сигналов в измерительно-вычислительной системе реального времени . . 178

5.2. Преобразование координат для системы числового программного управления металлорежущего станка нетрадиционной компоновки...............183

5.3. Сжатие сейсмических данных..............197

5.4. Сжатие медицинских рентгеновских изображений . . . 203

5.5. Сжатие цветных изображений..............210

Заключение 218

Список литературы 221

Приложение А Краткий обзор методов сжатия изображений 235

А.1. Обзор методов кодирования первого поколения.....236

А.2. Обзор методов кодирования второго поколения .... 240 А.З. Обзор методов кодирования третьего поколения .... 245

А.3.1. Многоразрешающее представление.......245

А.3.2. Краткий обзор методов векторного квантования 248

Приложение Б Акты использования результатов диссертации 259

Обозначения

В приведенных определениях первая цифра указывает номер главы, в которых появляется обозначение, а вторая - параграф в этой главе.

' к

^ т

Ы|

а

а(к)

а,-

^УтЦ —>

а

ахЬ

т

5(х)

х

биномиальный коэффициент; 3.1

норма (в соответствующей метрике) элемента а; 4.1

А В отображение множества А в множество В] 4.2

приближение элемента а; 1.1 дискретное преобразование а{т)\ 2.2 г-ж сегмент числа а; 1.2

обратная конечная разность г'-го порядка отсчета у(т); 2.3

вектор; 5.1

векторное произведение векторов; 5.1

скалярное произведение функий / и д; А.З

целое число, большее или равное действительного числа 2.2

дельта функция в точке ж; 1.1 цифровая переменная; 1.1 аналоговая переменная; 2.2

Ах абсолютная погрешность, интервал дискретизации х; 1.1

М[Ах] математическое ожидание Ах; 1.3 <т[Дж] стандартное среднеквадратическое отклонение Ах; 1.3 т£(Л) нижняя грань множества А; 4.1 Х(т) т-й отсчет аналоговой переменной X; 2.2

цифровое значение отсчета Х(т); 2.2 г-й разряд в двоичнопозиционном представлении числа

Х- 2.2

Л(/) адресное пространство (количество ячеек) таблицы

функции /; 1.1

С(/) информационная емкость таблицы функции /; 1.1

!)(/) область определения функции /; 1.1

С(а, 6, с) выигрыш в адресном пространстве таблиц, необходимом для табличного представления заданной функции, а, 6, с - параметры; 3.1

Н(/) энтропия нулевого порядка функции /; 1.1

/(/) сложность элементарных операций, необходимых для

восстановления значений /(х); 2.1

Д(/) воспроизводящий алгоритм для таблицы Г(/;е)

функции /; 1.1

5 (ж) разрядность (количество бит) числа х; 1.1

Т(/;е) таблица функции /; 1.1

С [а, 6] множество непрерывных функций, заданных на отрезке [а,Ь]; 2.2

7г,7г] множество периодических функций непрерывных на от-

резке [—7г, 7г] вместе со своими производными до т-го порядка включительно; 4.2

Ь2 гильбертово пространство функций двух переменных;

А.З

№ множество целых чисел > 0; 2.1

Н множество действительных чисел; 1.1

множество действительных 5-разрядных двоичных чисел; 1.1

Ж множество целых чисел; А.З

факториальный многочлен. № = — 1)... (£ — п + 1); 5.2

ВРР отношение "число бит - пиксел"; 1.1

МвЕ среднеквадратическая ошибка; 1.1

пиковое отношение "сигнал - шум"; 1.1

Введение

АКТУАЛЬНОСТЬ ТЕМЫ. Современное общество переживает период бурного и постоянно увеличивающегося роста потока информации, перерабатываемого во всех сферах жизни человечества. Процессы получения и преобразования информации занимают все большее место в повседневной жизни людей, производстве, науке, культуре и других областях.

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

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

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

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

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

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

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

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

тельных средств системы.

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

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

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

В то же время повышение производительности информационно-измерительных систем встречает принципиальные трудности. Очевидные ограничения накладывает достигнутый уровень быстродействия элементной базы. Не менее важен тот факт, что совершенствование информационно-измерительных систем практически в любом направлении (от увеличения емкости памяти до использования алгоритмических языков высокого уровня) обычно связано с дополнительными временными затратами и, следовательно, сдерживает рост производительности. Такие затраты необходимы при ужесточении требований к частоте и точности получения результатов измерений, объему вычислительных процедур обработки этих результатов, качеству и объему предоставляемых оператору данных.

Рассматривая производительность систем, следует отметить, что

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

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

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

СОСТОЯНИЕ ПРОБЛЕМЫ. Табличная форма представления функций является естественной для аналого-цифровой и цифровой частей современных информационно-измерительных систем. Это касается как входной информации, полученной в результате дискретизации, квантования и кодирования измеряемых аналоговых величин, распределенных во времени или пространстве, так и системных функций, необходимых для обработки, передачи и хранения преобразованной системой информации. Многомерные табличные функции (различного рода изображения) составляют основу видеоинформационных систем и технологий.

Под табличным представлением функции далее понимается набор (таблица) заранее вычисленных с определенной точностью параметров, характеризующих функцию, хранимый на различных носителях информации, в первую очередь, в запоминающих устройствах. Цифровые изображения далее рассматриваются как таблицы двухмерных пространственных функций, определяющих интенсивность изображения в каждом из своих отсчетов (элементов изображения или пикселов изображения или пикселов - сокращение от pixel -picture element).

Табличным воспроизведением функции будем называть выбор-

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

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

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

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

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

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

ния табличные методы не получили из-за трудности практической реализации таблиц большой емкости. Здесь можно назвать исследования М. П. Цапенко и О. В. Улина, работы В. И. Рабиновича по функциональным аналого-цифровым преобразователям и др.

Исследования по применению табличных методов в измерительно-вычислительной технике связаны так же с В. Б. Смоловым, Б. Н. Малиновским, И. Ф. Образцовым и руководимыми ими коллективами и др.

Появление запоминающих устройств (ОЗУ, ПЗУ, ППЗУ, ПЛМ), обеспечивающих практическую возможность реализации таблиц большой емкости, привело к распространению работ в области вычислительной техники, посвященных табличному и таблично-алгоритмическому воспроизведению функций. Табличное воспроизведение применяется для относительно простых функций. Таблицы таких функций, как правило, не требует особенно большой емкости запоминающего устройства. Таблично-алгоритмическое воспроизведение применяется для более сложных функций. В этом случае получение значений воспроизводимой функции осуществляется на ЭВМ по алгоритмам, высокая эффективность которых основана на применении таблиц специально подобранных функций. При доступной емкости используемых запоминающих устройств, таблично-алгоритмические средства воспроизведения функций уступают табличным в быстродействии.

Поиск компромисса между быстродействием и емкостью па