ПОНЯТИЯ И ПРОБЛЕМЫ

1.1. Основные подходы к проблеме компрессии изображений

1.1.1. Математическая модель дискретного изображения

1.1.2. Мера ошибки восстановления изображений

1.1.3. Исходные идеи методов компрессии статических изображений

1.1.4. Вариант JPEG, основанный на применении ДКП

1.1.5. Проблема выбора базисов разложения

1.2. Использование вейвлет-преобразований для компрессии статических изображений

1.2.1. Основные понятия, определения, специфика вейвлет-преобразований

1.2.2. Двумерные вейвлет-преобразования

1.2.3. Основные идеи современных алгоритмов вейвлет-компрессии изображений

1.3. Особенности обработки видеопоследовательностей

1.4. Общая постановка задачи оптимизации кодирования с потерями

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

Заключение диссертации по теме "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", Умняшкин, Сергей Владимирович

Список литературы диссертационного исследования доктор физико-математических наук Умняшкин, Сергей Владимирович, 2001 год

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

Преобразования, которые используются для сжатия изображений должны быть быстрыми, и, по возможности, легко реализуемыми на компьютере. Это прежде всего предполагает, что такие преобразования должны быть линейными. То есть, преобразованные величины С{ являются линейными комбинациями (суммами с некоторыми множителями или весами) исходных величин (пикселов) dj, причем соответствующим множителем или весом служит некоторое число Wij (коэффициент преобразования). Значит, С{ - ]Г\- djWij, где г, j = 1,2,..., п. Например, при п = 4 это преобразование можно записать в матричной форме которая в общем случае примет следующий вид: С = W D. Каждый вектор-столбец матрицы W называется «базисным вектором».

Важной задачей является определение коэффициентов преобразования wij. Основное требование заключается в том, чтобы после преобразования величина с\ была бы большой, а все остальные величины С2,сз,... стали бы малыми. Основное соотношение С{ = Ylj djWij предполагает, что С{ будет большим, если веса Wij будут усиливать соответствующие величины dj. Это произойдет, например, если компоненты векторов wij и dj имеют близкие значения и одинаковые знаки. Наоборот, С{ будет малым, если веса избудут малыми, и половина из них будет иметь знак, противоположный знаку соответствующего числа dj. Поэтому, если получаются большие с*, то векторы W{j имеют сходство с исходным вектором dj, а малые С{ означают, что компоненты wij сильно отличаются от dj. Следовательно, базисные векторы wij можно интерпретировать как инструмент для извлечения некоторых характерных признаков исходного вектора.

На практике веса Wij не должны зависеть от исходных данных. В противном случае, их придется добавлять в сжатый файл для использования декодером. Это соображение, а также тот факт, что исходные данные являются пикселами, то есть, неотрицательными величинами, определяет способ выбора базисных векторов. Первый вектор, тот, который, порождает с\, должен состоять из близких, возможно, совпадающих чисел. Он будет усиливать неотрицательные величины пикселов. А все остальные векторы базиса должны наполовину состоять из положительных чисел, а на другую половину - из отрицательных. После умножения на положительные величины и их сложения, результат будет малым числом. (Это особенно верно, когда исходные данные близки, а мы знаем, что соседние пикселы имеют, обычно, близкие величины.) Напомним, что базисные векторы представляют собой некоторый инструмент для извлечения особенностей из исходных данных. Поэтому хорошим выбором будут базисные векторы, которые сильно различаются друг от друга и, поэтому, могут извлекать разные особенности. Это приводит к мысли, что базисные векторы должны быть взаимно ортогональными. Если матрица преобразования W состоит из ортогональных векторов, то преобразование называется ортогональным. Другое наблюдение, позволяющее правильно выбирать базисные векторы, состоит в том, что эти векторы должны иметь все большие частоты изменения знака, чтобы извлекать, так сказать, высокочастотные характеристики сжимаемых данных при вычислении преобразованных величин.

Первый базисный вектор (верхняя строка W) состоит из одних единиц, поэтому его частота равна нулю. Все остальные векторы имеют две +1 и две -1, поэтому они дадут маленькие преобразованные величины, а их частоты (измеренные количеством смен знаков в строке) возрастают. Эта матрица подобна матрице преобразования Адамара-Уолша (см. уравнение (3.11)). Для примера, преобразуем начальный вектор (4,6,5,2)

Результат вполне ободряющий, поскольку число с\ стало большим (по сравнению с исходными данными), а два других числа стали малыми. Вычислим энергии исходных и преобразованных данных. Начальная энергия равна 4 2 + б 2 + 5 2 + 2 2 = 81, а после преобразования энергия стала 17 2 + З 2 + (-5) 2 + I 2 - 324, что в четыре раза больше. Энергию можно сохранить, если умножить матрицу преобразования W на коэффициент 1/2. Новое произведение W-(4,6,5,2) т будет равно (17/2,3/2, -5/2,1/2). Итак, энергия сохраняется и концентрируется в первой компоненте, и она теперь составляет 8.5 2 /81 = 89% от общей энергии исходных данных, в которых на долю первой компоненты приходилось всего 20%.

Другое преимущество матрицы W состоит в том, что она же делает обратное преобразование. Исходные данные (4,6,5,2) восстанавливаются с помощью произведения W-(17/2,3/2, -5/2,1/2) т.

Теперь мы в состоянии оценить достоинства этого преобразования. Квантуем преобразованный вектор (8.5,1.5,-2.5,0.5) с помощью его округления до целого и получаем (9,1,-3,0). Делаем обратное преобразование и получаем вектор (3.5,6.5,5.5,2.5). В аналогичном эксперименте мы просто удалим два наименьших числа и получим (8. 5,0, -2.5,0), а потом сделаем обратное преобразование этого грубо квантованного вектора. Это приводит к восстановленным данным (3,5.5,5.5,3), которые также весьма близки к исходным. Итак, наш вывод: даже это простое и интуитивное преобразование является хорошим инструментом для «выжимания» избыточности из исходных данных. Более изощренные преобразования дают результаты, которые позволяют восстанавливать данные с высокой степенью схожести даже при весьма грубом квантовании.

Контрольная

Коммуникация, связь, радиоэлектроника и цифровые приборы

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

2.4. Алгоритмы трансформирования исходных изображений на основе ортогональных преобразований (С какой целью могут использоваться алгоритмы трансформирования исходных изображений на основе ортогональных преобразований? Что общего и в чём различия между дискретным преобразованием Фурье и другими видами ортогональных преобразований?).

В некоторых случаях, для сокращения объёма данных или облегчения процедуры выделения признаков объектов на последующих этапах распознавания, целесообразно предварительно преобразовывать исходный двумерный массив [ Е i , j ] в массив значений коэффициентов [ F u , v ], имеющий такой же формат MxN, как и исходное изображение.

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

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

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

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

Рис. 2. 3. Распределение энергии сигнала между отдельными элементами
в исходном массиве (а) и в трансформанте (б).

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

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

Здесь коэффициенты F u в общем случае являются комплексными числами

Дискретное преобразование Фурье

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

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

Преобразование Уолша (при M = N )

В свою очередь, коэффициенты b k (Z ) определяются следующим образом: b k (Z ) равен значению k -того разряда двоичного кода числа Z , состоящего из l двоичных разрядов. Если, например, Z = 10, т.е. 10 10 =1010 2 , то
b 0 = 0; b 1 = 1; b 2 = 0; b 3 = 1.

b k — определяются в соответствии с правилом их определения в преобразовании Уолша.

Преобразование Адамара (при M = N )

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

Пусть [Е i , j ] — массив исходного изображения форматом NxN , где j — номер строки, i — номер столбца элементов (номер элементов в строке); [ F u , v ] — трансформанта изображения, которая имеет тот же формат NxN , где u и v соответственно номер строки и номер столбца элементов трансформанты. Тогда, в общем случае, независимо от вида ортогонального преобразования, запишем

где a (i , j , u , v ) и b (i , j , u , v ) — базисные функции прямого и обратного преобразований соответственно.

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

Здесь а стр (i , u ), b (i , u ) и a (j , v ), b (j , v ) — базисные функции прямого и обратного преобразований, соответственно вдоль направления строк и столбцов.

Для удобства записи и вычислений целесообразно использовать матричный аппарат

Здесь [А э ] и [ А стр ] — матрицы прямого преобразования; [ В э ] и [ В стр ] — матрицы обратного преобразования; [А стр ] т и [В стр ] т — матрицы, полученные в результате транспонирования матриц [ А стр ] и [ В стр ].

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

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

Алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований

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

Умняшкин Сергей Владимирович

УДК 004.932: 004.421: 519.722

Математические методы и алгоритмы цифровой

компрессии изображений с использованием

ортогональных преобразований

Специальность 05.13.11 - “Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей”

Москва – 2001 2

Работа выполнена в Московском государственном институте электронной техники (техническом университете)

Научный консультант : доктор физико-математических наук, профессор Поспелов А.С.

Официальные оппоненты :

Доктор физико-математических наук, профессор Ососков Г.А.

Доктор физико-математических наук, профессор Селищев С.В.

Доктор технических наук профессор Коекин А.И.

Ведущая организация : ФГУП НИИ Радио (г.Москва)

Защита состоится 19 февраля 2002 года в 1430 на заседании диссертационного совета Д.212.134.02 в Московском государственном институте электронной техники по адресу: 103498, Москва, г. Зеленоград, МИЭТ (ТУ).

С диссертацией можно ознакомиться в библиотеке МИЭТ (ТУ).

Ученый секретарь диссертационного /Воробьев Н.В./ совета профессор

Общая характеристика работы

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

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

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

Направление исследований. Проведенные в диссертационной работе исследования включали в себя рассмотрение следующих вопросов:

1. Исследование и разработка методов теоретического анализа и синтеза дискретных преобразований для схем компрессии коррелированных данных;

2. Разработка новых быстрых алгоритмов вычисления дискретного преобразования Крестенсона-Леви (ДПКЛ) и алгоритма сжатия полутоновых изображений, основанного на статистическом кодировании спектров ДПКЛ;

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

4. Разработка алгоритмов вейвлет-компрессии изображений и изучение возможностей фрактального кодирования в области вейвлет-спектра;

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

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

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

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

На защиту диссертации выносятся следующие основные результаты:

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

Новый быстрый алгоритм ДПКЛ и его модификация – алгоритм с неполным вычислением; алгоритм совмещенных вычислений ДПКЛ для обработки вещественных массивов в базисе (1,exp(-2i/3));

Метод компрессии изображений, основанный на специальном способе арифметического кодирования спектров ДПКЛ блоков изображения;

Детерминированные и вероятностные оценки коэффициентов дискретного косинусного преобразования (ДКП);

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

Общая схема компрессии изображений на основе адаптивного векторного квантования в области ортогональных преобразований;

Алгоритмы вейвлет-компрессии статических изображений;

Алгоритм поиска перемещенных блоков изображения;

Экспериментальная методика построения разбиения спектров на области независимого кодирования;

Алгоритм видеокомпрессии.

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

Реализация результатов работы. Теоретические результаты работы и алгоритмы сжатия видеоизображений внедрены в ГУ НПК «Технологический Центр» МИЭТ (http://www.tcen.ru) и использованы в научно-производственной деятельности НПП «Технология» (Москва) .

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

1. VII саратовская зимняя школа по теории функций и приближений (СГУ, январь 1994 г.) .

2. Междунар. конференция по теории функций и приближений, посвященная 90-летию акад. С.М.Никольского (Москва, МИ РАН, май 1995 г.) .

3. Всероссийские научно-технические конференции “Электроника и информатика” (Москва, МИЭТ, 1995-2000 г.) .

4. Междунар. конференция по теории приближения функций, посвященная памяти проф. П.П.Коровкина (Калуга, КГПУ, 26-29 июня 1996 г.) .

5. Международные конференции «Методы оптимизации вычислений» (Киев, 1997, 2001 г.) .

6. Международная конференция «Проблемы математического образования», посв. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева (1998 г.) .

7. Международная конференция «Теория приближений и гармонический анализ» (Тула, 26-29 мая 1998 г.) .

8. Международная конференция «Информационные технологии в инновационных проектах» (Ижевск, 20-22 апреля 1999 г.) .

9. VII Международная конференция «Математика. Экономика. Экология. Образование» – Международный симпозиум «Ряды Фурье и их приложения»

(Новороссийск, 1999 г.) .

10. VII Международная конференция «Математика. Компьютер. Образование»

11. Международная конференция, посвященная 80-летию со дня рождения С.Б.Стечкина (Екатеринбург, 28 февраля – 3 марта 2000 г.) .

Публикации . Основное содержание диссертации отражено в 30 работах.

Структура и объем диссертации . Диссертационная работа содержит страницы (из которых 26 страниц – приложения) и состоит из введения, шести глав, заключения и 6 приложений. Библиографический список включает в себя 178 наименований. В приложениях приведены численные результаты ряда экспериментов по обработке изображений, а также справочная информация и копии документов об использовании результатов диссертационной работы.

Во введении (28 страниц) обосновываются актуальность, научная новизна, практическая ценность исследований. Кратко излагается содержание глав.

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

Использование алгоритмов сжатия с потерями данных для полутоновых изображений носит повсеместный характер: допустив наличие ошибки в восстановленном изображении, можно добиться намного более высокого уровня компрессии данных. Чаще всего качество обработки изображений оценивают X=(xi,j) – матрица исходного изображения, X = (xi, j) – матрица изображения, полученного после обработки (сжатия и восстановления данных). Для логарифмической величины СКО используется общепринятая мера PSNR (peak signal to noise ratio – отношение пикового значения сигнала к шуму), Методы сжатия изображений удобно рассматривать в виде общей схемы, состоящей из трех основных этапов: снижение межэлементной корреляции данных, квантование элементов данных, статистическое кодирование. Квантование является основным инструментом, используемым при сжатии с потерями данных. По сути дела, квантование есть выделение из входных данных некоторой основной части информации, когда ее менее значимая часть опускается.

Применяется как скалярное, так и векторное квантование.

Перевод изображения в обобщенную спектральную область при помощи линейного преобразования F может значительно снизить межэлементную корреляцию в матрице-трансформанте Y=F(X) по сравнению с корреляцией элементов в матрице дискретного изображения Тогда независимое покомпонентное кодирование матрицы Y, а не матрицы X, становится более эффективным. Можно также дать энергетическую трактовку цели использования преобразований, которая в таком понимании заключается в концентрации максимальной части энергии исходного дискретного сигнала (матрицы X) в минимальном количестве спектральных коэффициентов (элементов матрицы Y). Между распределением энергии в обобщенном спектре и декоррелирующими свойствами преобразований имеется определенная связь. Изучение эффективности декоррелирующих свойств, таким образом, является важной задачей при выборе преобразования для применения в схеме компрессии.

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

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

В первой главе отмечается, что для оптимизации алгоритмов сжатия данных с потерями часто используется подход, основанный на минимизации RDфункции Лагранжа. Пусть X – некоторый входной набор данных, которому в результате выполнения процедуры сжатия-восстановления ставится в соответствие выходной набор данных той же природы, Y=F(X,u), где u=(u1,…,un) – набор управляющих параметров алгоритма сжатия F. Считаем X, Y элементами некоторого пространства с метрикой D(X,Y), множество всех возможных значений управляющего вектора u обозначим U. Задача оптимизации кодирования состоит в том, чтобы для заданного набора входных данных X и максимально допустимых битовых затрат Rb найти такие параметры u* = u1,..., un алгоритма F, чтобы ошибка кодирования данных D(X,Y)=D(X,F(X,u)) принимала бы минимальное значение. То есть где R(X,u) – число бит, необходимое для кодирования набора данных X с параметрами u.

Поиск решения задачи (1) в большинстве случаев сводится к громоздким численным процедурам итерационного характера. Если не задаваться ограничением R(X,u)Rb, то для определения оптимальных параметров кодирования u*, соответствующих решению задачи (1) для некоторого (заранее неизвестного) значения Rb, используется упрощенный вариант минимизации RD-функции Лагранжа:

где – неотрицательный параметр, задаваемый внешне. Параметр в функции J(u) устанавливает баланс между качеством и уровнем сжатия данных. Значение =0 соответствует наименьшей ошибке кодирования, увеличивая значение, получаем при оптимизации параметров алгоритма F по (2) меньшую длину кода, но большую ошибку. Тем самым можно настраивать алгоритм кодирования F на необходимые характеристики. Для поиска решения задачи (1) минимизация (2) повторяется итерационно, с различными значениями – данная процедура носит название RD-оптимизации1.

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

Так же как и для статической компрессии, алгоритмы кодирования видео чаще всего являются более сложными по сравнению с алгоритмами декодирования.

Реализация программной компрессии видео в реальном масштабе времени, таBerger T. Rate Distortion Theory. – Endlewood Cliffs, NJ: Prentice Hall, 1971.

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

Вторая глава (52 страницы) посвящена изучению эффективности и синтезу ортогональных преобразований, предназначенных для использования в сжатии данных. Предложенный новый метод анализа эффективности основан на следующих рассуждениях. Пусть известна ковариационная матрица KX исходного вектора данных X = (x0, x1,…, x N 1)T, вектор-спектр Y получен в результате некоторого ортогонального преобразования с матрицей W: Y=WX.

Средняя безусловная энтропия коэффициента вектор-спектра может быть записана в виде :

где fk(mk,k,x) – функция плотности распределения вероятностей для спектральной характеристики yk (k-ой компоненты вектора Y), mk – математическое ожидание, k – среднеквадратичное отклонение, f k0 (x) = f k (0,1, x). Чем меньше средняя энтропия (3), тем эффективнее будет последующее независимое кодирование компонент спектра. Наложив ограничение, при котором для класса что для оптимального преобразования Карунена-Лоэва (когда матрица W=Wopt составлена из собственных векторов KX и матрица KY=WKXWT имеет диагоN 1 N нальный вид) декоррелирующей эффективности будем рассматривать величину средней избыточной энтропии H (W, K X) = H cp (W, K X) H cp (Wopt, K X), которая выражается через элементы матриц K X = (cov(xi, x j))i, j = 0 и W = (wi, j)i, j =0 следующим образом :

Чем больше значение H(W,KX), тем меньше эффективность декоррелирующего преобразования с матрицей W. Численные расчеты величины (4) для различных преобразований и видов ковариационных матриц показали результаты, полностью согласующиеся с известными данными, которые получены другими методами, например, по Пэрл (Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. - 1973. - Vol. ITP. 229-232.).

Большой интерес для анализа представляет модель дискретного сигнала (вектора X), имеющего статистику дискретного марковского процесса первого порядка, когда ковариационная матрица имеет следующий вид:

Данная модель часто используется для описания межстрочной и межстолбцовой корреляции в дискретных изображениях. При =1, когда все компоненты в исходном векторе X одинаковы (для любых двух отсчетов вектора коэффициент корреляции равен единице), расчет введенного критерия (4) для матрицы (5) невозможен, т.к. в этом случае имеем det K X = 0. Вместе с тем, на фоновых областях изображения 1. В главе 2 доказана следующая теорема.

Теорема 2.1. Для любой ортогональной матрицы W (NN) такой, что j = 0,1,… N 1: w0, j = (базисная функция с нулевым индексом есть нормиN рованная постоянная составляющая) и ковариационной матрицы (5) Различные исследования, в том числе проведенные в главе 2, показывают, что среди дискретных преобразований, имеющих быстрые алгоритмы вычислений (для размерности N реализуемых за ~NlogN арифметических операций) наиболее близкие к оптимальному преобразованию Карунена-Лоэва характеристики декорреляции для марковского процесса (5) дает использование ДКП.

Однако несмотря на наличие хорошо проработанных быстрых алгоритмов вычисления, ДКП принципиально требует для своей реализации выполнения операций умножения и по объему вычислений заметно уступает, например, преобразованиям Хаара, Уолша, Крестенсона-Леви. Отдельным вопросом, рассмотрению которого уделено значительное внимание в главе 2, является построение нового преобразования, имеющего как высокие характеристики декорреляции для модели (5), так и значительно более быстрые, чем для ДКП, алгоритмы вычисления. Полученное в результате дискретное псевдокосинусное преобразование определено для векторов размерности N, которая допускает разложение N=N1…Nn, причем k Nk{2,3,4}. Представление N=N1…Nn необходимо записать минимальным количеством множителей Nk, располагая их без убывания, т.е. k, m>k: NkNm. Например, для N=8 имеем N1=2, N2=4 (но не N1=4, N2=2 и не N1=N2=N2=2). Тогда матрица ДПКП WN (в данном случае нижний индекс указывает на размерность преобразования) строится как прямое произведение2 WN = WN 1 … WN n элементарных матриц ДПКП WN k {W2,W3,W4}, k=1,…,n, где элементарные матрицы ортогональны Под тензорным (прямым) произведением матриц D={dl,m} (l=0,…,-1; m=0,…,-1) и и получены в результате определенных модификаций из матриц ДКП соответствующей размерности. Элементарные матрицы представимы в виде произведения некоторой диагональной матрицы D на матрицу С, а структура С позволяет реализовать умножение на произвольный вектор U только при помощи операций сложения и вычитания чисел (умножение на 2 эквивалентно сложению, 2x=x+x). Именно:

Из свойств тензорного произведения следует представление WN = D N C N, C N = C N 1 … C N n. Матрицы C2, C3, C4, D2, D3, D4 приведены выше. Таким образом, реализация ДПКП Y = WN X = D N C N X заключается в реализации умножения матрицы CN на вектор, Y = C N X, и последующей нормировке полученного вектора Y, Y = D N Y. Для вычисления ДПКП удобно использовать быстрые алгоритмы, основанные на факторизованном представлении для матматриц3:

единичная матрица размерности N j N j. Поскольку матрицы TN j) состоят из определенным образом разреженных матриц-блоков C N j, умножение матрицы TN j) на вектор также сводится только к операциям сложения и вычитания чисел. Быстрые алгоритмы обратного ДПКП строятся аналогично, т.к. в силу орT) () Отметим, что необходимая при вычислении ДПКП и обратного ДПКП нормировка (умножение на матрицу DN) для схемы сжатия со скалярным квантованием коэффициентов преобразования не влечет усложнения вычислений.

Нормировка может быть объединена при сжатии данных с этапом скалярного зованного вектора Y индивидуального шага квантования qj=q/djj (где d jj – элемент диагональной нормировочной матрицы D N). При деквантовании y j = m~ j множитель для элемента y j следует выбирать в виде mj=qdjj.

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

Третья глава (48 стр.) посвящена изучению вопросов применения для сжатия изображений дискретного преобразования Крестенсона-Леви (ДПКЛ) и является развитием исследований кандидатской работы автора.

Для обоснования справедливости данного представления см. с.84-85 из монографии «Абстрактные алгебраические системы и цифровая обработка сигналов» / Вариченко Л.В., Лабунец В.Г., Раков М.А. - Киев: Наукова думка, 1986. – 248 с.

Идея предложенного в пятой главе алгоритма сжатия основана на работах Lewis-Knowles6 (LK) и Xiong-Ramchandran-Orchard7 (XRO). При кодиLewis A.S., Knowles G. Image Compression Using the 2-D Wavelet Transform // IEEE Trans.

Image Proc. – 1992. – Vol. 1. - №2. – P.244-250.

ровании топологии S в XRO для всех узлов дерева, кроме листьев, использовалась бинарная карта {ni}: если ni=0, то дерево в данном узле подрезается, а если ni=1, то по крайней мере непосредственные потомки сохраняются. Сказанное иллюстрируется рис. 2А. Статистическое кодирование признаков {ni} в алгоритме XRO не используется. Вместе с тем, признаки {ni} соседних (по положению внутри саббэнда) узлов являются коррелированными величинами. Чтобы учесть эту корреляцию, в разработанном алгоритме признаки для соседних узлов {ni }iC j предлагается группировать в единый элемент данных, так что карта подрезания ветвей (топология дерева) описывается новым алфавитом данных с символами Ni=(ni1,ni2,ni3,ni4)=ni1+2ni2+4ni3+8ni4, которые, кроме того, кодируются статистически. Новый расширенный признак Nj оказывается связанным уже с узлом j более высокого уровня, см. рис. 2Б.

Подрезание ветвей Рисунок 2. Способ подрезания ветвей при послойном просмотре узлов: А – алгоритм XRO, Б – предлагаемое кодирование топологии. Ci={i1,i2,i3,i4} Идея, которая восходит к работе LK и в том же виде используется в XRO, заключается в следующем: чем больше абсолютная величина вейвлеткоэффициента wi (или энергия, wi2) узла-родителя i, тем менее вероятно появление у данного узла нулевой (т.е. подрезанной) ветви. Более точное предсказание появления нулевой ветви можно составить, если использовать в качестве Xiong Z., Ramchandran K. and Orchard M.T. Space-frequency Quantization for Wavelet Image Coding // IEEE Trans. Image Proc. – V.6 – May 1997, P. 677-693.

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

где множества для индексов суммирования определяются среди соседей узла i в саббэнде в соответствии с рис. 3. Весовые коэффициенты, входящие в сумму, были получены в результате статистической обработки ряда тестовых изображений с целью выявления максимума выборочного значения для коэффициента корреляции между прогнозной величиной (10) и энергией проквантованных вейвлет-коэффициентов непосредственных потомков Сi: Pi, w2 max.

Предлагаемый алгоритм вейвлет-компрессии использует несколько статистических моделей. Функцию арифметического кодера, которая оценивает по внутренним статистическим моделям количество бит, необходимое для кодирования символа с в k-ом потоке, обозначим H(k,c). Обозначение Hspec относится к потокам, в которых кодируются проквантованные вейвлет-коэффициенты, Hmap – к потокам, в которых кодируются признаки начала нулевой ветви. Деревья спектра обрабатываются последовательно; после оптимизации топологии очередного дерева его необходимо закодировать, и тем самым произвести адаптацию статистических моделей арифметического кодера.

Шаг 0. /* инициализация */ i Ln1: /* просматриваются все узлы предпоследнего уровня */ /*корректировка проквантованных коэффициентов*/ /* расчет RD-функций сохранения и подрезания листьев */ Шаг 2. i Ll: /*просмотр текущего уровня с попыткой подрезания ветвей */ Если i0 то /* не достигли начала дерева */ /* определение оптимальной топологии ветвей */ /*корректировка проквантованных коэффициентов*/ /* подготовка для просмотра следующего уровня */ иначе /* i=0, достигли начала дерева */ /* определение оптимальной топологии дерева */ Шаг 3. /* формирование и выдача результата */ Конец Просмотр узлов дерева проводится от листьев к корню. На первом (подготовительном) шаге просматриваются те узлы i, которые имеют только непосредственных потомков (Ci=Ui), формируются массивы из значений RDфункций, соответствующих вариантам подрезания (J U i) и сохранения (J U i) листьев. Предварительно, на шаге 1.1, для каждого узла-листа анализируется возможность дополнительной минимизации Лагранжа, характеризующей скалярное квантование вейвлет-коэффициентов. Данная процедура основана на известных свойствах распределения вероятностей вейвлеткоэффициентов, в соответствии с которыми битовые затраты R на кодирование коэффициента априори тем меньше, чем меньше его абсолютное значение (по этой причине для случая w = 0 процедура дополнительной минимизации не применяется). На втором шаге, который выполняется для всех узлов i следующих уровней, iLl (l=n-2,…,0), производится выбор RD-оптимального способа подрезания ветвей (шаги 2.1-2.2), начинающихся из узлов jCi. Шаги 2.3 и 2. несут тот же смысл, что и шаги 1.1, 1.2. Отметим, что введение дополнительной оптимизации скалярного квантования (шаги 1.1 и 2.3) позволяет при том же уровне сжатия дополнительно повысить PSNR на 0,02-0,03 дБ.

Для всех узлов, за исключением корневого, выбор модели для кодирования признаков Ni (на шаге 2.1) производится с использованием правила, определяемого функцией IndMap(i). Для кодирования признака N0, связанного с корнем дерева, используется отдельный поток данных, которому условно присвоен номер 0 (см. шаг 2.6).

Как следует из приведенного описания алгоритма оптимизации, важнейшую роль в его работе играют функции IndMap(Pi) и IndSpec(i), которые задают правила выбора потоков для кодирования данных. Первая функция производит выбор модели кодирования признака Ni=(ni1,ni2,ni3,ni4) по среднему значению прогнозных величин Pi (10), i=i1,i2,i3,i4, и имеет следующий вид:

Пороги (t1,t2,t3)=(0.3;1.1;4.0) для выбора моделей находились в результате минимизации длины выходного битового кода R(t1,t2,t3) при обработке известных тестовых изображений Lena, Barbara, Goldhill. Эксперименты показали также, что введение большего числа моделей для признаков лишено смысла.

Вторая ключевая функция алгоритма вейвлет-сжатия, IndSpec(i), представляет собой правило выбора модели для кодирования не попавших в нулевые ветви вейвлет-коэффициентов. Для кодирования спектральных коэффициентов более эффективным оказывается использование прогнозной величины, полученной не только по родительскому узлу, но и по вейвлеткоэффициентам узлов, которые находятся в том же саббэнде, рядом с обрабатываемым8. В рассматриваемом алгоритме последовательность кодирования и декодирования узлов вейвлет-спектра определяется схемой рисунка 4 (цифры обозначают порядок обработки саббэндов). Для использования в функции IndSpec(j) прогнозная величина текущего узла j (помечен черным) формируется s j = 0.36 Pi + 1.06 w j y + w jx + 0.4 w jd, где jy – узел-сосед по вертикали, jx – Идея использования контекста соседних вейвлет-коэффициентов предложена в работе Chrysafis С., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression // Proc. Data Compression Conference. – Snowbird (Utah), 1997. – P. 241-250.

узел-сосед по горизонталии, jd – узел-сосед по диагонали (которые уже обработаны, см. рис. 4), Pi определяется для узла-родителя i (jCi) по (10). При этом результатам обработки тестовых изображений.

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

Характеристики, которые дает Таблица. 1. Величина PSNR (в дБ), попредложенный алгоритм компрессии лученная при сжатии тестовых изобрадля стандартных тестовых изображе- жений по предложенному алгоритму ний, приведены в табл. 1. В экспериLena Barbara Goldhill ментах применялись пятишаговые вейвлет-преобразования из работы Wei D., Pai H.-T., and Bovik A. C., Antisymmetric Biorthogonal Coiflets for Image Coding // Proc. IEEE International Conference on Image Processing. – Chicago, 1998. – V. 2. – P. 282-286. Сравнение достигнутых характеристик с результатами применения других известных алгоритмов показывает, что предложенный алгоритм имеет весьма высокие показатели.

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

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

Кадром видеопоследовательности назовем матрицу пикселей из M1 строк и M2 столбцов: B=(bk,l), k=0,1,…,M1-1, l=0,1,…,M2-1, а под видеопоследовательностью будем понимать упорядоченный набор кадров B0,B1,…,Bi,…. Назовем (y,x)-блоком кадра B (y, x – целочисленные координаты) некоторую подматрицу By,x=(bk,l), где k=y,y+1,…,y+N1-1, l=x,x+1,…,y+N2-1. В разработанном алгоритме каждый кадр видеопоследовательности разбивается при обработке на смежные матрицы-блоки {Bm,n} размером 88, m,n=0,8,16… Если какой-либо блок Biy,x видеопоследовательности оказался в определенном смысле «похож» на оригинальный блок Bim, n, считаем, что блок Bim,n – это перемещенный фрагмент Biy,x См., например, Davis G.M., A wavelet-based analysis of fractal image compression // IEEE Trans. Image Proc. – 1998. – V.7 – №2. – P.141-154.

предыдущего кадра, и для кодирования (m,n)-блока изображения достаточно задать координаты блока в предыдущем кадре, y и x, либо изменения координат y-m и x-n. Частным случаем перемещенного блока является неподвижный блок, когда m=y, n=x. Если блоку Bim, n нельзя найти похожий в предыдущем кадре, блок должен кодироваться как новый. Для выбора способа кодирования очередного обрабатываемого блока Bim, n вновь руководствуемся критерием минимума функции Лагранжа J(b)=D(b)+R(b). Положим, что аргумент b= соответствует кодированию перемещенного (неподвижного) блока, а b=1 – нового. Т.е. если J(1)>J(0), то блок кодируется как перемещенный, и как новый – в противном случае.

При использовании RD-оптимизации задача поиска перемещенных блоков формулируется следующим образом. Для заданного (m,n)-блока Bim, n i-ого кадра найти в предыдущем восстановленном кадре такой (y,x)-блок B iy,x, чтобы минимальное значение принимала RD-функция Лагранжа Здесь учтено, что координаты найденного блока будут кодироваться как относительные, т.е. вектором перемещений r=(y-m,x-n). Для того чтобы поиск можно было осуществить в реальном масштабе времени, в качестве области необходимо рассматривать лишь точки (v,u), достаточно близко расположенные к точке (m,n). Повышение эффективности поиска за счет расширения области достигается применением различных алгоритмов направленного поиска, ориентированных на минимизацию ошибки представления перемещенного блока Bim, n Biy,1, что соответствует частному случаю (11) при =0. Для того, чтобы учесть вклад битовых затрат в RD-функцию J*, будем проводить минимизацию (11) поэтапно, на каждом из этапов приближенно полагая, что рассматриваемые векторы перемещений влекут одинаковые затраты на статистическое кодирование. Кроме того, для повышения универсальности итерационных алгоритмов поиска малые перемещения будем искать более точно. Действительно, если некоторый блок изображения переместился на значительное расстояние по сравнению с предыдущим кадром, то соответствующий фрагмент изображения воспринимается человеческим глазом смазано, и в точном определении вектора перемещения нет необходимости. Малые же перемещения блоков не только являются преобладающими, но и должны точно отслеживаться в силу специфики визуального восприятия. Предлагаемый алгоритм RD-поиска имеет следующий вид.

Шаг 0. Вычисление значения RD-функции неподвижного блока, r=(0,0):

Шаг 1. Близкий к перебору точный поиск небольших перемещений.

1.1. Среди девяти (y,x)-блоков предыдущего кадра, 1.2. Среди девяти (y,x)-блоков предыдущего кадра, 1.3. Вычисление значения RD-функции Шаг 2. Грубый поиск больших перемещений.

2.1. Среди восьми (y,x)-блоков предыдущего кадра, 2.2. Среди девяти (y,x)-блоков предыдущего кадра, (y 4, x 4) {(0,0), (2,2), (2,2), (2,2), (2,2), (3,0), (0,3), (3,0), (0,3)} 2.3. Вычисление значения RD-функции Шаг 3. Выбор наилучшего варианта перемещения блока.

Конец Для вычисления значения функции J0 необходимо учесть битовые затраты на кодирование признака перемещенного блока: J 0 = J * log2 (mov), где mov – частота появления перемещенных блоков в уже обработанных данных.

Основной объем вычислений в приведенном алгоритме связан с подсчетом отклонений B im, n Biy,x. При вычислениях одна пробная точка переходит с шага 0 на шаг 1.1, одна – с шага 1.1 на 1.2, одна – с шага 2.1 на 2.2. В итоге вычисление отклонения требуется выполнить 33 раза.

Для повышения эффективности приведенного алгоритма поиска для вектора (y, x) обрабатываемого блока следует строить прогноз по векторам () и () двух уже обработанных соседних блоков (соответственно соседа по вертикали и соседа по горизонтали). Собственно прогноз – это относительные координаты y 0, x 0, которые определяют перенос центра области поиска: из точки (m,n) в точку (m, n) = m + y 0, n + x 0. Эксперименты показывают, что число новых блоков изображения сокращается на 5…25%, если принять следующее правило составления прогноза:

Следуя идеологии стандарта MPEG, обработку новых блоков также осуществляем при помощи квантования с последующим статистическим кодированием коэффициентов двумерного ДКП. Пусть S=F(Вm,n) – результат ДКП блока Вm,n. Обозначим SQ = {~k,l = round(sk,l / qk,l)}k,l =0, SQ = {sk,l = qk,l ~k,l }k,l =0, где Q = {qk,l }k,l =0 – одна из матриц квантования JPEG. Для статистического кодирования матрицы S применен алгоритм контекстного кодирования, рассмотренный в главе 4, в который введен дополнительный этап RD-оптимизации. Пусть вновь ZQ = (z0,…, z63) – вектор, полученный в результате зигзагообразного считывания данных из матрицы SQ по правилу, определяемому стандартом JPEG (SQ ZQ), G (ZQ) = {g k }C=1 {0,…,63} – множество индексов ненулевых элементов вектора ZQ, т.е. z g k 0, если gkG; gkG: z g k = 0. RD-оптимизация статистического кодирования возможна за счет удлинения нулевых серий путем сокращения количества элементов во множестве G (дополнительного обнуления компонент вектора ZQ). Для того, чтобы в результате не произошло заметного усложнения алгоритма кодирования, будем анализировать лишь возможность увеличения финальной нулевой серии, что дает наибольший вклад в минимизацию функции J(ZQ)=D(ZQ)+R(ZQ). Пусть ZQ – вектор, полученный из вектора ZQ в результате обнуления последних компонент {zk }k = g m +1, т.е.

G (ZQ) = {g k }m=1 G (ZQ), m=1,…,C. Тогда простейшая RD-оптимизация состоm ит в поиске такого индекса g m * G (ZQ), что Рассмотренная выше процедура кодирования нового блока изображения предполагает использование заданной матрицы квантования Q. Универсальный же алгоритм кодирования должен оперировать некоторым набором матриц квантования {Qj} с возможностью выбора требуемой для конкретных условий.

Если набор достаточно большой, то подбор матрицы квантования Q по принципу минимума функции JQ (12) превращается в громоздкую процедуру, нереализуемую в реальном масштабе времени стандартными средствами. Кроме того, при большом диапазоне возможных значений индекса j его кодирование для каждого нового блока по отдельности влечет недопустимо высокие дополнительные битовые затраты. Поэтому в качестве исходного набора были выбраны лишь несколько матриц из множества, рекомендуемого JPEG, которые соответствуют наилучшему, наихудшему и некоторым промежуточным уровням качества. В экспериментах выбиралось число матриц |{Qj}|=4. Для ускорения выполнения операций деления, которые необходимы при квантовании, элементы матриц {Qj} были округлены до ближайшего значения 2k, k=0,1,… Такой подход позволяет заменить операции целочисленного деления и умножения сдвигами разрядов двоичного представления чисел, которые обычно выполняются реальной аппаратурой намного быстрее.

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

J = min (J Q log 2 Q) log 2 new, где JQ находится в соответствии с (12), Q – частота появления матрицы Q, new – частота появления новых блоков в ходе предшествовавшей обработки.

При исследовании характеристик итогового алгоритма видеокомпрессии для оценки величины ошибки кодирования в восстановленной последовательности B0, B1,…, B K 1 использовалось отношение пикового значения сигнала к шуму, которое определялось следующим образом:

где M1 и M2 задают размер кадра в пикселях. Для экспериментов были выбраны широко известные тестовые последовательности News, Container ship, Hall monitor, Akiyo, Claire. Все они имеют размер кадра 144176 пикселей. Перед проведением экспериментов оригинальные последовательности были прорежены: только каждый третий кадр, B3k (k=0,…,24), использовался для формирования тех 25-кадровых видеопоследовательностей, которые затем и были подвергнуты обработке. Данное временное прореживание было призвано смоделировать скорость видеозахвата 10 кадров в секунду, вместо оригинальных (для всех вышеназванных последовательностей) 30 кадров в секунду. Обработке подвергалась только яркостная Y-составляющая, и только по яркостной составляющей анализировалась ошибка Программное сжатие видеопоследовательностей при этом удалось осуществить в реальном масштабе времени.

Результаты численных экспериментов, полученные аспирантом Ф.В.Стрелковым , отражены в таблице 2. В скобках приведено значение PSNR (13), достигнутое на тех же самых прореженных 25-кадровых тестовых видеопоследовательностях с использованием общедоступного кодера MPEG- http://www.mpeg.org/MSSG. Длина файла сжатых данных, полученного в каждом эксперименте, в точности равна произведению величины битового потока данных (приведена в таблице) на множитель 2.5. Во всех тестах предложенная схема компрессии дает высокие результаты, превосходя характеристики указанного кодера MPEG-2, несмотря на то, что кодек mpeg2encode использовал для поиска перемещенных блоков изображения полный перебор в области из 2323 пикселей.

Таблица 2. Характеристики сжатия предложенного алгоритма Описанный алгоритм видеокомпрессии был реализован программно в рамках работ, проводившихся в ГУ НПК «Технологический Центр» Московского государственного института электронной техники и в НПП «Технология»

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

http://www.tcen.ru/vs).

Итог исследованиям, проведенным в диссертационной работе, подводится в заключительном разделе – «Основные выводы и заключение» (3 стр.).

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

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

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

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

4. При использовании статистического кодирования коэффициентов ДКП по методу JPEG наличие «скачков» дискретного сигнала наименее желательно в центральной области фрагментов обработки.

5. Высокую эффективность применения в различных схемах и алгоритмах сжатия данных имеет метод многомодельного (многопотокового) арифметического кодирования, а одним из ключевых моментов в разработке схем компрессии является определение правил для выбора текущей модели кодирования по контексту уже обработанных данных. Так, применение в схеме JPEG предложенного в главе 4 алгоритма многомодельного контекстного арифметического кодирования коэффициентов ДКП повышает эффективность сжатия данных на 10%.

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

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

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

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

Список основных работ по теме диссертации 1. Ефимов А.В., Умняшкин С.В. Быстрые алгоритмы вычисления дискретного преобразования Крестенсона-Леви и оценки его спектральных характеристик // Теор. функций и прибл.: Тр. 7-й саратов. зим. шк. (1994 г.). Ч. 2.- Саратов: Изд.-во СГУ, 1995. - С. 9-20.

2. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Применение преобразования Крестенсона-Леви в задачах цифровой обработки информации // Междунар.

конф. "Функциональные пространства, теория приближений, нелинейный анализ", посв. 90-летию акад. С.М.Никольского (27 апр. - 3 мая 1995 г.): Тез.

докл. - М.: Изд-во МФТИ, 1995. - С.124-125.

3. Умняшкин С.В. Применение дискретного преобразования Крестенсона-Леви (ДПКЛ) для кодирования изображений: сравнение с дискретным преобразованием Фурье (ДПФ) // Всерос. науч.-тех. конф. “Электроника и информатика” 15-17 нояб. 1995 г.: Тез. докл. - М.: МГИЭТ (ТУ), 1995. - С. 265-266.

4. Умняшкин С.В. Оценка дисперсии элементов спектра дискретного косинусного преобразования стационарного марковского процесса первого порядка // Междун. конф. по теор. прибл. функ., посв. памяти проф. П.П.Коровкина (Калуга, 26-29 июня 1996 г.): Тез. докл. -Т.2.-Тверь: ТГУ, 1996. - С. 217-218.

5. Умняшкин С.В. Оценка эффективности использования унитарных преобразований для кодирования дискретных сигналов // Информатика и связь: Сб.

Научных трудов под ред. В.А.Бархоткина. М.: МИЭТ.- 1997. С.73-78.

6. Умняшкин С.В. Оценка эффективности применения дискретных преобразований для сжатия данных // «Электроника и информатика – 97». Вторая всероссийская научно-техническая конференция с международным участием (Зеленоград, 25-26 ноября 1997г.): Тез. док. Часть 2. - С.79.

7. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Теоретические основы и некоторые особенности применения дискретных мультипликативных преобразований в задачах сжатия цифровых изображений // Працi мiжнародноi коференцii “Питання оптимизацii обчислень” (6-8 жовтня 1997 р., м. Киiв) Киiв: Iнститут кiбернетики iменi В.М.Глушкова, 1997. - С. 108-112.

8. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Некоторые свойства мультипликативных ортонормированных систем, используемые в цифровой обработке сигналов // Труды математического института им. В.А.Стеклова РАН.

- Т.219. - 1997. - С 137-182.

9. Ефимов А.В., Умняшкин С.В. О некоторых свойствах обобщенной системы Хаара и оценке эффективности применения ортогональных преобразований для сжатия данных // Функциональные пространства. Дифференциальные операторы. Проблемы математического образования: Труды междун. конф., посв. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева. - Том 1. - М.: Рос. ун-т дружбы народов, 1998. - С. 70-73.

10. Умняшкин С.В. О модификации дискретного косинусного преобразования // Теория приближений и гармонический анализ: Тез. докл. междунар. конф.

11. Умняшкин С.В. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. Т. 4. Вып. 1. С. 143-147.

12. Умняшкин С.В., Кочетков М.Е. Анализ эффективности использования дискретных ортогональных преобразований для цифрового кодирования коррелированных данных // Известия вузов. Электроника. - №6. - 1998. - С. 79-84.

13. Умняшкин С.В. О кластеризации коррелированных данных. // Информационные технологии в инновационных проектах. Междунар. конф. (г.Ижевск, 20-22 апр. 1999г.): Материалы докладов. - Ижевск, ИжГТУ, 1999. - С. 59-65.

14. Умняшкин С.В. Алгоритм кластеризации коррелированных данных // VII Междунар. конф. Математика. Экономика. Экология. Образование. Междунар. симп. Ряды Фурье и их приложения: Тез. док. – Ростов: Рост. гос. эконом. акад., 1999. – С. 211-212.

15. Ефимов А.В., Поспелов А.С., Умняшкин С.В. Некоторые вопросы применения мультипликативных систем и преобразований в задачах цифровой обработки изображений // VII Междунар. конф. Математика. Экономика.

Экология. Образование. Междунар. симп. Ряды Фурье и их приложения: Тез.

док. – Ростов: Рост. гос. эконом. акад., 1999. – С. 154-155.

16. Умняшкин С.В. Псевдокосинусное преобразование для сжатия дискретных сигналов // Информационные технологии и проблемы микроэлектроники.

Сб. науч. тр. – М.: МИЭТ. – 1999. – С.158-170.

17. Умняшкин С.В. Алгоритм компрессии неподвижных изображений на основе дискретного вэйвлет-преобразования // VII международная конференция «Математика. Компьютер. Образование» (Дубна, ОИЯИ, 24-29 янв. 2000):

Тез. док. – Москва: Прогресс-Традиция, 2000. – С.327.

18. Ефимов А.В., Умняшкин С.В. О структуре некоторых прямых и обратных вэйвлет-преобразований // Теория приближений функций и операторов: Тез.

докл. Междунар. конф., посв. 80-лет. со дня рожд. С.Б.Стечкина (Екатеринбург, 28 фев. – 3 мар. 2000). -Екатеринб.: УрГУ, 2000. – С.74-75.

19. Умняшкин С.В., Стрелков Ф.В., Жуков В.Г. Трехшаговые алгоритмы поиска перемещенных блоков изображения // Информационные технологии и системы управления. Сб. научн. тр. под ред. В.А.Бархоткина. – М: МИЭТ, 2000.

– С. 47-55.

20. Умняшкин С.В. Цифровая компрессия изображений с использованием дискретного преобразования Крестенсона-Леви // Межотраслевой научнотехнический журнал «Оборонный комплекс – научно-техническому прогрессу России», №2, 2000. С.28-39.

21. Умняшкин С.В., Космач М.В. Оптимизация кодирования цифровых изображений по методу JPEG //Изв. вуз. Электроника. -№4-5. -2000. -С.139-141.

22. Умняшкин С.В. Компенсация перемещения объектов при сжатии видеоданных // «Электроника и информатика – XXI век» Третья международная научно-техническая конференция: Тез. док. – М.: МИЭТ, 2000. – С. 365-366.

23. Умняшкин С.В. Алгоритм поиска перемещенных блоков для кодирования цифровых видеоизображений // Межотрасл. н.-т. журнал «Оборонный комплекс – научно-техническому прогрессу России», №3, 2001. – C. 38-41.

24. Умняшкин С. В. Использование контекстного арифметического кодирования для повышения сжатия данных по схеме JPEG // Известия вузов. Электроника. - №3. - 2001. – С. 96-99.

25. Умняшкин С. В. Вейвлет-компрессия цифровых изображений с прогнозированием статистических моделей //Изв. вузов. Электроника. - №5. - 2001. С.86-94.

26. Умняшкин С. В. Алгоритм фрактального кодирования изображений в области вейвлет-преобразований // Комп`ютерна математика. Оптимiзацiя обчислень: Збiрник наукових праць. – Том 1. – Кив: Iнститут кiбернетики iм.

В.М.Глушкова, 2001. – С. 385-391.

27. Umnyashkin S.V. Image compression based on mixed predictive modeling of wavelet trees // Reports from Vxj University (Sweden) – Mathematics, natural sciences and technology. – Nr.11 (September), 2001. – 18 pages.

28. Umnyashkin S.V., Strelkov F.V. An RD-optimized scheme for real-time video compression // Reports from Vxj University (Sweden) – Mathematics, natural sciences and technology. – Nr.12 (September), 2001. – 15 pages.

29. Разработка алгоритмов и программного обеспечения для реализации цифрового анализа и компрессии видеоизображений в реальном масштабе времени на базе программно-аппаратного комплекса общего назначения: Отчет о НИР (закл.) / НПП «Технология»; рук. – Умняшкин С.В. – «Страж»; № гос.

рег. 01990011697; Инв. №01077. – Москва, 1999. – 74 с.

30. Исследование и разработка алгоритмов программного сжатия данных с потерями для цифровой обработки видеоизображений: Отчет о НИР (закл.) / НПП «Технология»; рук. – Умняшкин С.В. – «Дозор»; № гос. рег.

01200004624; Инв. №100704. – Москва, 2000. – 48 с.

Подписано в печать: 25 декабря 2001 года Заказ №332. Тираж 100 экз. Уч.-изд.л. 2,4. Формат 6084 1/
уравнения Автореферат диссертации на соискание ученой степени доктора физико-математических наук Москва 2007 Работа выполнена в Научно-исследовательском институте прикладной математики и автоматизации...»

«КОРНИЛОВ Дмитрий Александрович ИССЛЕДОВАНИЕ СВОЙСТВ ФУЛЛЕРЕНОВ И НАНОТРУБОК МЕТОДОМ МОЛЕКУЛЯРНОЙ ДИНАМИКИ Специальность 01.04.07 – Физика конденсированного состояния Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Санкт-Петербург 2003 г. Работа выполнена в государственном образовательном учреждение высшего профессионального образования Санкт-Петербургский государственный политехнический университет Научный руководитель: доктор...»

«ЧИРИКОВ АНТОН МИХАЙЛОВИЧ НОВЫЕ ТЕОРЕМЫ ЕДИНСТВЕННОСТИ ДЛЯ СТЕПЕННЫХ РЯДОВ 01.01.01 - вещественный, комплексный и функциональный анализ Автореферат диссертации на соискание учной степени е кандидата физико-математических наук САНКТ-ПЕТЕРБУРГ 2011 Работа выполнена на кафедре математического анализа математического факультета Российского Государственного Педагогического Университета им. Герцена Научный руководитель доктор физико-математических наук, профессор Широков Николай...»

«Сидоров Евгений Николаевич ОСОБЕННОСТИ ОПТИЧЕСКИХ СВОЙСТВ СИЛЬНО ЛЕГИРОВАННОГО GaAs:Te В УСЛОВИЯХ КОРРЕЛИРОВАННОГО РАСПРЕДЕЛЕНИЯ ПРИМЕСИ Специальность 01.04.10 – физика полупроводников АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико–математических наук Томск – 2010 Работа выполнена в Омском филиале Института физики полупроводников им. А.В. Ржанова СО РАН Научный руководитель: кандидат физико–математических наук Давлеткильдеев Надим Анварович Официальные...»

«ЛЯШЕДЬКО АНДРЕЙ ДМИТРИЕВИЧ Термооптические искажения в неодимовых лазерах на основе пластинчатых активных элементов с продольной диодной накачкой Специальность: 01.04.21 – лазерная физика АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте общей физики им. А.М. Прохорова РАН Научный руководитель: доктор физико-математических наук Цветков...»

«УДК: 535.326, 534.18 Пятакова Зоя Александровна АКУСТООПТИЧЕСКОЕ ВЗАИМОДЕЙСТВИЕ В ДВУМЕРНЫХ ФОТОННЫХ КРИСТАЛЛАХ Специальность 01.04.03 – радиофизика Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2011 Работа выполнена на физическом факультете Московского государственного университета им. М.В. Ломоносова Научный руководитель: кандидат...»

«КРУТИКОВА Алла Александровна СПЕКТРАЛЬНЫЙ АНАЛИЗ КОМПОЗИТНЫХ МАТЕРИАЛОВ НА ОСНОВЕ НАНОКРИСТАЛЛИЧЕСКОГО КРЕМНИЯ Специальность: 02.00.02 – Аналитическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Москва–2007 Работа выполнена на кафедре аналитической химии Московской Государственной академии тонкой химической технологии им. М.В. Ломоносова Научный руководитель: доктор химических наук, профессор Ищенко Анатолий Александрович Официальные...»

«МАТВЕЕНКО Сергей Иванович ПЕРИОДИЧЕСКИЕ СТРУКТУРЫ В НИЗКОРАЗМЕРНЫХ КОРРЕЛИРОВАННЫХ СИСТЕМАХ Специальность 01.04.02 - теоретическая физика АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук Черноголовка - 2012 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте теоретической физики им....»

«УДК 004.896 АКСЕНОВ Константин Александрович ТЕОРИЯ И ПРАКТИКА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ В ОБЛАСТИ ПРОЦЕССОВ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ Специальность 05.13.01 – Системный анализ, управление и обработка информации Автореферат диссертации на соискание ученой степени доктора технических наук Екатеринбург – 2011 Работа выполнена на кафедре автоматизированных систем управления ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б.Н.Ельцина. Научный...»

«Восков Алексей Леонидович РАСЧЕТ ФАЗОВЫХ РАВНОВЕСИЙ МЕТОДОМ ВЫПУКЛЫХ ОБОЛОЧЕК Специальность 02.00.04 – физическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Москва – 2010 Работа выполнена в лаборатории химической термодинамики на кафедре физической химии Химического факультета Московского государственного университета имени М. В. Ломоносова. Научный руководитель: доктор химических наук, профессор Воронин Геннадий Федорович Официальные...»

«Кравченко Игорь Витальевич ОСОБЕННОСТИ СТРУКТУРИРОВАНИЯ СЛОИСТЫХ И ДИСПЕРСНЫХ СИСТЕМ НЕСОВМЕСТИМЫХ ПОЛИМЕРОВ ПРИ СДВИГОВОМ ТЕЧЕНИИ. ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ 02.00.06 – Высокомолекулярные соединения Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва 2010 www.sp-department.ru Работа выполнена в Учреждении Российской академии наук Институт проблем химической физики РАН Научный руководитель: доктор физико-математических наук Патлажан...»

«Грибов Андрей Геннадьевич АНАЛИЗ ИНФОРМАЦИОННЫХ ОБМЕНОВ В СИСТЕМАХ УПРАВЛЕНИЯ Специальность 05.13.01 – Системный анализ, управление и обработка информации (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2011 Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН в Отделе прикладных проблем оптимизации. Научный руководитель: доктор физико-математических наук...»

«Джардималиева Гульжиан Искаковна (СО)ПОЛИМЕРИЗАЦИЯ И ТЕРМИЧЕСКИЕ ПРЕВРАЩЕНИЯ МЕТАЛЛОСОДЕРЖАЩИХ МОНОМЕРОВ КАК ПУТЬ СОЗДАНИЯ МЕТАЛЛОПОЛИМЕРОВ И НАНОКОМПОЗИТОВ 02.00.06 – высокомолекулярные соединения АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора химических наук Черноголовка – 2009 www.sp-department.ru Работа выполнена в Институте проблем химической физики РАН доктор химических наук, профессор Научный консультант: Помогайло Анатолий Дмитриевич доктор химических...»

«ГАВРИЛОВ Алексей Андреевич ИССЛЕДОВАНИЕ ЛИНЕЙНЫХ И СЕТЧАТЫХ СЛУЧАЙНЫХ ПОЛИМЕРНЫХ СИСТЕМ МЕТОДАМИ КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ Специальности 02.00.06 высокомолекулярные соединения, 01.04.07 – физика конденсированного состояния Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 Работа выполнена на кафедре физики полимеров и кристаллов физического факультета Московского Государственного Университета имени М. В. Ломоносова....»

«НГУЕН СУАН НГИА ДИЭЛЕКТРИЧЕСКАЯ РЕЛАКСАЦИЯ НАДМОЛЕКУЛЯРНЫХ СТРУКТУР В БИОЛОГИЧЕСКИХ ЖИДКОСТЯХ НА НИЗКИХ И ИНФРАНИЗКИХ ЧАСТОТАХ Специальность - 01.04.04. Физическая электроника АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Санкт-Петербург - 2011 Работа выполнена в государственном образовательном учреждении высшего профессионального образования Санкт-Петербургский государственный политехнический университет Научный руководитель:...»

«Наймушина Екатерина Александровна. УДК 538.945 ПРИМЕНЕНИЕ МЕТОДА РЕНТГЕНОЭЛЕКТРОННОЙ СПЕКТРОСКОПИИ ДЛЯ ИССЛЕДОВАНИЯ ХИМИЧЕСКОГО СТРОЕНИЯ СЛОЖНЫХ МЕДНЫХ ОКСИДОВ В СВЕРХПРОВОДЯЩЕМ СОСТОЯНИИ Специальность 01.04.01. – приборы и методы экспериментальной физики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ижевск – 2004 Работа выполнена в лаборатории электронной спектроскопии Института физики поверхности при Удмуртском государственном...»

«Дашков Евгений Владимирович О пропозициональных исчислениях, представляющих понятие доказуемости 01.01.06 – математическая логика, алгебра и теория чисел АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета имени М. В....»

«Русаков Дмитрий Михайлович СХЕМЫ ПРОГРАММ С КОНСТАНТАМИ Специальность 01.01.09 – дискретная математика и математическая кибернетика АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва – 2008 Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова. Научный...»

«РЕМЕЕВА АЛЬФИЯ НИЛОВНА МЕТОДИКА ОБУЧЕНИЯ ФИЗИКЕ В КЛАССАХ СОЦИАЛЬНОЭКОНОМИЧЕСКОГО ПРОФИЛЯ 13.00.02 – теория и методика обучения и воспитания (физика) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Челябинск - 2008 Работа выполнена на кафедре теории и методики обучения физике государственного образовательного учреждения высшего профессионального образования Стерлитамакская государственная педагогическая академия Научный руководитель: доктор...»

«Изображение в полиграфии» - Специфика изображения в полиграфии. Главное свойство полиграфического изображения. Книга. Отличительная черта большинства изобразительных полиграфических произведений. Множественность Массовость Общедоступность. Соединение изображения с текстом. Искусство книги. Шрифт.

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

«Компьютерная графика» - Основные проблемы при работе с растровой графикой. Виды компьютерной графики отличаются принципами формирования изображения. Компьютерная графика. Фрактальная графика. Виды компьютерной графики. Большие объемы данных. Пиксель. Сравнительная характеристика растровой и векторной графики. Каждая точка экрана может иметь лишь два состояния – «черная» или «белая».

«Создание графических изображений» - Границы полотна. Задание 4. Создать рисунок, состоящий из автофигур. Создание рисунка с помощью панели инструментов Рисование. Положение графического изображения в тексте. Вставить рисунок из коллекции в текст. Полотно. Сравнительная характеристика растровой и векторной графики. Особенности создания векторного изображения в среде Word 2003.

«Изображение головы человека» - Иные холодные, мертвые лица Закрыты решетками, словно темница. Другие - как башни, в которых давно Никто не живет и не смотрит в окно. Какие бывают портреты? Пропорции лица человека. Изображение черт лица. Лицо и эмоции человека. Н. Заболоцкий. Какие бывают лица? Рисунок головы человека. Поистине мир и велик и чудесен!

«Растровые изображения» - Выводы по эксперименту. Красный. Какие основные цвета использует ком-пьютер? Растровое кодирование графической информации. Растровое изображение. Пиксели разных цветов. Голубой (бирюзовый). Серый. Розовый. Палитра современных компьютеров. Все цвета можно пронумеровать, а каждый номер перевести в двоичный код.