Введение к работе
Актуальность темы. Аналого-цифровое преобразование применяется практически при переводе любых одномерных и многомерных сигналов в цифровую форму и включает в себя два этапа: дискретизацию сигнала по времени и квантование сигнала по уровню. Моделирование первого этапа предполагает прежде всего оценку потерь информации, возникающих при переходе от непрерывного сигнала к дискретному. В 1948 году в качестве теоретической модели процесса дискретизации Шенноном была предложена квантизационная модель, которая позволяет произвести оценивание потерь дискретизации и свести эти потери к минимуму выбором соответствующих узлов дискретизации.
Общая задача квантизации в Rn формулируется следующим образом. Пусть Т - некоторое связное подмножество FP1. Пусть (fjt/^Li - набор N точек из Т. Каждая точка множества Т кодируется какой-нибудь одной точкой из этого набора. Ошибка кодирования точки t Є Т точкой tk измеряется некоторой неотрицательной функцией p(t,tk), действующей из ТХ Т в R .
Пусть Ajfc - множество точек из Т, которые кодируются ТОЧКОЙ tk, к = \,...,N. Так как кодируются все точки Т, набор множеств {Ajt}j^_[ образует разбиение Т. Ошибка кодирования точкой t/t измеряется интегралом / /)(i,f,fe)df, к = 1,. .. ,N. Общая ошибка кодирования множества Г точками
{(/t}jj._l измеряется суммой
eN\T}=t [p(t,tk)dt. (1)
Первоначально задача квантизации рассматривалась для одномерного случая с функцией ошибки, являющейся евклидовой метрикой (соответствующей однородным изотропным данным). Далее было сделано обобщение на неоднородный случай (с функцией ошибки локально приближаемой евклидовой метрикой). Также рассматривался случай, когда функция ошибки может быть локально приближена степенью метрики L\.
В данной работе рассматривается случай, когда функция ошибкир(^,-?) может быть локально приближена степенью метрики, порожденной выпуклым множествам. Этот случай позволяет моделировать процессы дискретизации неизотропных данных с оцениванием возникающих при этом потерь информации и с возможностью минимизации этих потерь.
Цель работы. Целью настоящей работы является обобщение основных результатов асимптотической теории квантизации на случай неизотропного источника и последующего применения этого
C&fSkM AIM* WWfifcWftR і SNMNOTEft J
о» mp*? .J
^ii і *—
модели-
рования процессов адаптивной дискретизации основных типов непрерывных данных.
Задачи.
1) Построить квантизационную модель с функцией ошибки, локально
приближаемой степенью выпуклой метрики, позволяющую учитывать неизо
тропность данных и оценивать возникающие при этом потери информации.
2) Разработать методы моделирования адаптивной дискретизации
неизотропных данных в различных условиях. Свести общую задачу кван
тизации к более простым частным задачам вычислительной геометрии.
-
Вычислить асимптотические оценки потерь информации, возникающих при дискретизации неизотропных данных в различных условиях.
-
Построить иерархию моделей для различных частных случаев многомерных неизотропных данных.
-
Провести численные эксперименты моделирования показательных частных видов двумерных неизотропных данных, сравнить полученные результаты с результатами кластеризационного алгоритма Маккуина.
Методы исследования. В работе используются следующие известные методы и конструкции. Модель Шеннона моделирования процессов дискретизации непрерывных данных и оценивания потерь информации при этой дискретизации. Метрика, порожденная выпуклым множеством и теория множеств Вороного относительно этой метрики. Методы классической теории квантизации, в частности, простейшие утверждения, что оптимальным разбиением квантизации будет разбиение на множества Вороного относительно точек дискретизации, а также, что минимум погрешности по множеству фиксированной площади достигается, когда это множество есть шар в метрике ошибки. Метод построения асимптотически оптимальной квантизации и асимптотического оценивания потерь дискретизации в случае неоднородных данных, состоящий в разбиении области Т на бесконечно малые подмножества, на которых данные считаются однородными (все методы классической теории квантизации были адаптированы к случаю неизотропных данных). Методы сведения задачи адаптивной дискретизации случайных данных и классов неслучайных данных к задаче оптимальной квантизации.
Научная новизна работы. Принципиально новым в работе является обобщение квантизационной модели Шеннона на случай неоднородных данных при помощи выбора в качестве ошибки квантизации метрики, порожденной выпуклым множеством. Впервые была построена иерархия моделей дискретизации различных типов случайных и неслучайных неизотропных данных. Впервые для случая неоднородных данных в различных условиях были доказаны теоремы существования и построения адаптивной дискретизации с оценкой возникающих при этом потерь информации. При помощи доказан-
ных теорем впервые численно промоделированы процессы адаптивной дискретизации нескольких типов двумерных неизотропных данных. Приведено сравнение полученных результатов с результатами применения кластериза-ционного алгоритма Маккуина адаптивной дискретизации, который показал более слабые результаты.
Теоретическая и практическая значимость. Моделирование процессов адаптивной дискретизации неизотропных данных (с оценкой потерь) имеет существенное значение для теории информации. Полученные результаты в частности могут быть применены для оптимизации аналого-цифрового преобразования многомерного неизотропного сигнала, оптимизации фото-приемных матриц приборов с зарядовой связью, а также для оптимизации геофизических съемок. Также работа может оказаться полезной при моделировании случайных и неслучайных полей ступенчатыми полями.
На защиту выносятся:
квантизационная модель с функцией ошибки, локально приближаемой степенью выпуклой метрики, описывающая процесс дискретизации неизотропных данных с оценкой потерь информации;
методы моделирования адаптивной дискретизации неизотропных данных в различных условиях:
оценки потерь информации при дискретизации неизотропных данных в различных условиях;
- иерархия моделей для различных частных случаев многомерных
неизотропных данных;
- результаты численных экспериментов моделирования частных видов
двумерных неизотропных данных.
Апробация работы. Результаты неоднократно докладывались на научных семинарах г.Уфы, а также на международных конференциях, соответствующих профилю диссертации. В частности, были сделаны доклады
-
На международном конгрессе по кубатурным формулам (Уфа. 2001).
-
На международной конференции по кубатурным формулам (Красноярск, 2003).
-
На семинаре по теории вероятностей и математической статистике кафедры математики УГАТУ, руководитель проф.Ф.С.Насыров.
-
На городском семинаре по кубатурным формулам, руководители проф.М Д.Рамазанов, проф.Р.Р.Асадуллин.
-
На методическом семинаре Института математики с вычислительным центром УНЦ РАН, руководитель проф.Н.К.Бакиров.
Публикации. Основные результаты диссертации изложены в шести публикациях, среди которых одна монография ([1]) и пять статей ([2]-[6]). Работа [4] выполнена совместно с К.В.Симоновым и САПеретокиным. Из
результатов этой работы в диссертацию автором включены только результаты, полученные им лично.
Структура и объем диссертации. Диссертация включает в себя список основных обозначений, введение, пять глав, содержащих в совокупности 22 параграфа, заключение, список литературы, содержащий 147 наименований, в том числе ссылки на работы автора, помещенные в конце списка, а также два приложения. Общий объем диссертации 137 страниц.
