Обзор правил сжатия изображений

Размещено на http://www.allbest.ru/

1. Общие положения алгоритмов сжатия изображений

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

Изображения - это своеобразный тип данных, характеризуемый тремя особенностями:

1) Изображения занимают намного больше места в памяти компьютера, чем текст;

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

3) Изображение в отличие от текста обладает избыточностью в двух измерениях. То есть, как правило, соседние точки, как по горизонтали, так и по вертикали в изображении близки по цвету. Кроме того, мы можем использовать подобие между цветовыми плоскостями R, G и B, что дает возможность создавать более эффективные алгоритмы.

Чтобы говорить об алгоритмах сжатия изображений, мы должны определиться с несколькими важными вопросами:

1) Каковы критерии сравнения различных алгоритмов?

2) Какие классы изображений существуют?

3) Какие классы приложений, использующие алгоритмы сжатия изображений существуют, и какие требования они предъявляют к алгоритмам?



2. Классы изображений

Статические растровые изображения, представляют собой двумерный массив чисел. Элементы этого массива называют пикселями. Если рассматривать так называемые изображения без палитры, то значения каждого пикселя интерпретируются как яркость соответствующей точки. Это называется изображения в градациях серого. Встречаются изображения с 2, 16, 256 уровнями градации серого цвета. При использовании некоторой системы представления цвета каждый пиксель представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет представлен значениями интенсивности красной (R), зеленой (G) и синей (B) компонент.

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

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

1) Класс 1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Примеры: деловая графика - диаграммы, гистограммы, графики и т.п.

2) Класс 2. Изображения с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели САПР.

3) Класс 3. Фотореалистичные изображения. Примеры: отсканированные фотографии, цифровые фотографии.

4) Класс 4. Фотореалистичные изображения с наложением деловой графики. Пример: реклама.

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



3. Классы приложений

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

1) Класс 1. Характеризуются высокими требованиями к архивации и разархивации. Нередко требуется просмотр уменьшенной копии изображения и поиск в базе данных изображений. Примеры: издательские системы в широком смысле этого слова. Имеются в виду, как журналы, так и информационные узлы WWW. Проблема хранения файлов стоит очень остро. алгоритм сжатие файл кодирование

2) Класс 2. Характеризуется высокими требованиями к степени архивации и времени разархивации. Время архивации роли не играет. Иногда подобные приложения также требуют от алгоритма компрессии легкости масштабирования изображения под конкретное разрешение монитора у пользователя. Пример: справочники и энциклопедии на DVD-ROM.

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

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

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

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

4. Требования приложений к алгоритмам сжатия

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

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

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

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

4. Высокая скорость декомпрессии. Это достаточно универсальное требование.

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

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

7. Устойчивость к ошибкам. Данное требование означает локальность нарушений в изображении при порче или потере фрагмента передаваемого файла.

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

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

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

9. Редактируемость. Под редактируемостью понимается минимальная степень ухудшения качества изображения при его повторном сохранении после редактирования.

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

5. Критерии сравнения алгоритмов

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

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

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

2. Класс изображений, на который ориентирован алгоритм.

3. Симметричность. Отношение характеристики алгоритма компрессии к аналогичной характеристике при декомпрессии.

4. Есть потери качества?



6. Алгоритмы архивации без потерь

Алгоритм RLE

Алгоритм прост в реализации. Русское название - групповое кодирование - расшифровка RLE - Run Length Encoding - это один самых старых и самых простых алгоритмов архивации графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного байта:

ХХ значение

11 6 бит Что повторять

Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов превращаем в два байта, то есть сжимаем в 32 раза.

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

Характеристики алгоритма RLE:

Коэффициенты сжатия: (лучший -32, худший - 0.5).

Класс изображений: изображения с небольшим количеством цветов: деловая и научная графика.

Симметричность: примерно единица.

Особенность: не требует дополнительной памяти, быстро работает.



7. Словарные методы. Алгоритм LZW

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

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

В результате выходной файл состоит из индексов и рядов слов, поэтому необходимо делать различие между ними. Один возможный способ - это добавление к записываемому в файл образчику еще один дополнительный бит. В принципе, 19-битовый индекс будет достаточен для точного указания слов в словаре объема 2¹⁹=524299 элементов. Поэтому, если прочитанное слово найдено в словаре, то можно записать 20-битную ссылку, состоящую из флагового бита, (возможно, нулевого), за которым следует 19 битов индекса. Если данное слово не обнаружено в словаре, записывается флаг 1, затем длина слова и, наконец, само слово.

При этом возникает вопрос: "Сколько совпадений нужно обнаруживать в словаре, чтобы иметь общее сжатие?"

Если считать, что средний размер слова - 5 букв, а на сообщение о размере слова отведем 7 бит+1 бит на флаг, то среднее слово будет занимать 6 байт=48 бит в выходном файле. Напомним, что ссылка на место в словаре имеет длину 20 бит.

Пусть вероятность обнаружения слова в словаре равна P. После чтения и сжатия N слов размер выходного файла будет равен N(20P+48(1-P))=N(48-28P). Размер входного файла будет равен (при условии, что слово имеет 5 букв) 40N. Тогда сжатие будет достигаться, если N(48-28P)<40N, т.е. при P>. Следовательно, нужно иметь 29% и больше успешных нахождений слов в словаре для успешного сжатия.

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

Первые методы для словарного сжатия данных были разработаны Якобом Зивом (Jacob Ziv) и Абрахамом Лемпелом (Abraham Lempel). Здесь изложена модификация, принадлежащая Терри Уэлчу (Terry Welch).

Алгоритм LZW

Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя.

Метод LZW накапливает поступающие на вход символы в стоке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, процесс удлинения продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер

(1) Записывает в выходной файл указатель в словаре на строку I;

(2) Сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции;

(3) Инициализирует (присваивает) строке I новое значение х.

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

Проиллюстрируем работу кодера таблицей

I	Есть в словаре?	Новая запись	В выходном файле
а	Да
аб	Нет	3 - аб	1
б	да
ба	нет	4 - ба	2
а	да
аб	Да
аба	нет	5 - аба	3
а	Да
аб	Да
аб(eof)	нет		3

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

Чтобы понять, как работает декодер метода LZW, нужно помнить, как работает кодер. Кодер, делая очередную запись в выходной файл: (1) заносит словарный указатель на строку I, (2) сохраняет строку Iх в следующей свободной позиции словаря и инициализирует строку I символом х.

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

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

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

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

I	J	В словаре?	Новая запись	Выход
1				а
	2			б
12		нет	3 - аб
2
	3			аб
21		нет	4 - ба
3
	3			аб
31		нет	5 - аба

Замечание по структуре словаря в методе LZW

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

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

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

8. Сжатие изображений: стандарт JPEG

Рассмотрим теоретические основы алгоритма JPEG. Цель этих лекций - рассмотрение обычно используемого алгоритма сжатия изображений (имеются в виду статичные изображения, то есть фотографии, а не видеоклипы). Метод сжатия изображений широко известен как JPEG, аббревиатура Joint Photographic Experts Group, консорциум компаний и специалистов, которые разработали и популяризировали этот метод. Группа начала работу в июне 1987г, и первая версия стандарта была опубликована в 1991г. Метод сжатия JPEG широко используется для сжатия изображений в цифровых фотокамерах.

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

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

1500х2х100х70=21 000 000 знаков

1 знак=1 байт =8 бит

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

Простой подход к такому алгоритму сжатия назначает коды различной длины каждой букве алфавита. Частота использования букв, вообще говоря, зависит от автора и от содержания текста. Естественно назначить более короткие коды часто используемым буквам, а более длинные - используемым реже. В этом случае символы кодируются различным числом бит, а не одним байтом. При восстановлении информации закодированный таким образом текст будет восстановлен корректно. Но файл, содержащий необычно высокий процент редко используемых букв, может, в принципе, быть длиннее, чем исходный файл. Идея назначения кодов различной длины отдельным символам лежит в основе алгоритма сжатия Хаффмана (Huffman).

Следующий пример. Все экраны компьютеров (мониторы) имеют конечное разрешение. Обычно известно число пикселей, которые монитор может воспроизвести. Каждый пиксель может быть иллюминирован, чтобы иметь определенные яркость и цвет. Ранние мониторы имели разрешение 640х480=307200 пикселей (число пикселей в строке и число строк). Предположим, что крупный художественный музей решил оцифровать свою коллекцию живописных полотен. Музей хочет сделать это на таком уровне, чтобы удовлетворить вкусы экспертов. С другой стороны, музей хочет, кроме этого, иметь файлы небольшого размера для передачи через сеть Интернет и демонстрации изображений на экранах компьютеров. Эти файлы, для экспертов и для Интернет, будут существенно отличаться по разрешению и по размерам. Те, что будут предназначены для передачи через Интернет, будут содержать меньше деталей, но будут достаточного размера, чтобы демонстрироваться на мониторе. Размер изображения в пикселях должен соответствовать размеру строки и числу строк типичного монитора. Но как быть, если хочется еще уменьшить размер передаваемых по сети файлов?

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

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

Фотография может быть оцифрована разными способами. В методе JPEG изображение, прежде всего, разбивается на элементы малого размера, называемые пикселями. Каждый пиксель связывается с равномерным цветом или серым тоном. Допустим, черно-белая фотография квадратного формата имеет размеры 640х640 пикселей. Каждый из этих 640х640=409600 пикселей связан с равномерным серым тоном между белым и черным цветами. Предполагаемая фотография оцифровывается с использованием шкалы из 256 градаций из серого тона, где 0 представляет черный, а 255 представляет белый цвета. Так как 256=2⁸, каждый такой элемент (информация о каждом пикселе) может храниться в 8 битах (одном байте). Без сжатия нам потребуется 409600 байтов, чтобы хранить информацию о такой гипотетической фотографии. Чтобы закодировать информацию о цвете, потребуется сопоставить каждому пикселю еще три значения (красный, зеленый, синий) также по 8 бит на каждый цвет. Таким образом, ?410 Кбайт на яркость и ?3х410 Кбайт на цвет соответствует более 1 Мбайт информации. Однако, те, кто посещает Интернет, знают, что файл, содержащий фото такого размера, сжатое по стандарту JPEG, редко превышает размер 100 Кбайт. JPEG не имеет привязки только к Интернет, этот стандарт используется цифровыми фотокамерами. Алгоритм использует сжатие с потерями, поэтому часть информации при сжатии исчезает навсегда.

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

9. Случай 2х2 блока

Рассмотреть случай, когда блок представляет собой квадрат 2х2 пикселя, проще, чем случай с блоком 8х8, поэтому начнем с этого более простого случая.

Мы видели, что серые тона обычно представляют с использованием шкалы из 256 градаций. Мы рассмотрим, следуя экспертам из группы JPEG, шкалу с непрерывным изменением градаций, которая покрывает отрезок или некоторый интервал на действительной оси . В этом случае мы можем связать отрицательные значения с темными серыми тонами, стремящимися к черному цвету, а положительные значения с светлыми серыми тонами, стремящимися к белому цвету. Точка "0" будет соответствовать серому между 127 и 128 на шкале из 256 уровней. Мы будем игнорировать тот факт, что наши градации серого тона являются целыми числами между 0 и 255 и вместо этого полагать их действительными числами в указанном диапазоне. Таким образом, тон каждого пикселя может быть представлен действительным числом, и блок 2х2 будет требовать 4 таких значения или, что эквивалентно, четырехмерного вектора, или точки в четырехмерном пространстве . (При рассмотрении блока NxN потребуется вектор из пространства ).

Допустим, что мы нумеруем пиксели в двух измерениях, используя два индекса i и j для блока 2х2 , а для блока NxN .Индекс i соответствует строке, индекс j - столбцу, как в линейной алгебре. То есть для случая 2х2 имеем

Многие функции принимают значения в интервале [-1,1]. Чтобы представить их как значения серых тонов, мы будем использовать очевидные преобразования, отображающие отрезок [-1,1] в диапазон [0,255]. Эти преобразования могут быть следующими

Или

,

Где [x] означает взятие целой части числа x. Это потребуется, когда значения будут ограничены целыми числами в диапазоне [0,255]. Мы будем использовать f, чтобы обозначать функцию, определенную в диапазоне [0,255], и g, чтобы обозначать функцию, определенную в диапазоне [-1,1].

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

Пример. Пусть

Представим стандартный базис в аналитически

и графически. Как мы уже говорили, 0 соответствует среднесерому тону, а 1 - белому. Тогда



Пусть этот базис обозначается B.

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

Обратим внимание, что векторы ортогональны друг другу, то есть , в смысле скалярного произведения векторов ((i,j)?(k,l)). Элементы нового базиса могут быть представлены графически.

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

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

Матрица перехода S невырождена, при этом ее k-тый столбец состоит из коодинат "нового" k-того вектора в старом базисе. Следовательно, в нашем случае4-хмерного векторного пространства матрица S имеет вид

Очевидно, что обратное преобразование имеет вид

Обратим внимание, что в нашем случае матрица S симметрична, то есть , кроме того, она ортогональна, так как ее столбцы ортогональны, то есть , где I - единичная матрица. Таким образом, координаты вектора

,



заданные в стандартном базисе, в базисе вычисляются так:

Мы получили разложение

В этом базисе наибольший элемент среди координат вектора g равен 1. Это вес элемента , который дает одинаковую важность каждому из 4-х пикселей. Другими словами, этот элемент нового базиса назначает всем пикселям одинаковый серый тон. Два других ненулевых коэффициента гораздо меньше по модулю и содержат информацию о небольшой величине контраста между правым и левым столбцом и между двумя пикселями правого столбца. Аккуратный выбор базиса выделяет объемный контраст информации по сравнению с индивидуальной информацией о каждом пикселе. Это основа стандарта JPEG. Чтобы сделать этот метод методом сжатия с потерями, кто-либо должен решить какой из коэффициентов соответствует видимым контрастам каждого элемента в базисе. Остальные коэффициенты могут быть просто отброшены.



10. Случай блока NxN

Стандарт JPEG делит изображение на блоки по 8х8 пикселей. Определение базиса, который фокусирует больше внимания на информацию о контрасте, по сравнению с информацией об индивидуальных пикселях может быть также определен для произвольных NxN блоков. Базис, который был определен ранее для случая N=2 и используемый в стандарте JPEG для N=8, являются частными случаями. Дискретное преобразование заменяет функцию , определенную на квадрате NxN сетки, набором коэффициентов

Коэффициенты определяются следующим образом:

.

Фактически можно переписать в виде:

,

где коэффициенты определяются так

,

при этом

Для случая N=2 коэффициенты вычисляются следующим образом:



Преобразования элементов в элементы , очевидно, линейны, а матрица C выглядит так

.

Мы видим, что преобразование является матричным преобразованием , где C^T - матрица, транспонированная к матрице C.

Каждое линейное преобразование можно представить в соответствующем пространстве как умножение матрицы на вектор. Размеры матриц ? и f равны NxN. Соответственно, каждой из них можно сопоставить вектор длиной N². Таким образом, соответствующая матрица линейного преобразования (линейно преобразующая векторы, соответствующие матрицам ? и f) будет иметь размер N²х N².

Поясним сказанное, используя уже разобранный случай N=2. Для этого случая матрица имела размер 4х4 и преобразовывала вектор, соответствующий матрице в вектор . Преобразуем вектор g, используя формулу . Получим



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

Если матрица C невырожденная, что мы примем без доказательства, можно записать выражение для матрицы g через матрицу ?

,

где, как обычно, С^-1 обозначает матрицу, обратную к матрице C.

Примем без доказательства еще один факт. А именно: Матрица C является ортогональной, то есть С^-1=C^T. Это упрощает преобразования, так как в этом случае g= C^T?C.

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

Из соотношения, связывающего ? и g, мы видим, что g является линейной комбинацией некоторых величин с коэффициентами ?_kl. Множители при этих коэффициентах являются матрицами, формирующими базис. Эти базисные матрицы представляют собой в случае блока 8х8 набор из 64 матриц размера 8х8. Если каждому элементу из этого набора сопоставить картинку, то первой матрице будет соответствовать картинка, имеющая однородный серый тон, а последней матрице будет соответствовать картинка из 64 квадратов, каждый из которых отличается по тону от соседнего (шахматная доска). Таким образом, при изменении номера матрицы в наборе от первого к последнему частота смены тона в соседних квадратах, соответствующих этим матрицам картинок, возрастает.

Что можно сказать о коэффициентах разложения ?_kl матрицы f по базису из матриц? Коэффициенты ?_kl, связанные с f, будут иметь существенную величину, если тональная величина, соответствующая базисной матрице с номером kl, подобна тональной величине f. Отрицательные значения ?_kl указывают, что пятна яркости f совпадают с темными пятнами элементов базиса и наоборот. Так, близкие к постоянным базисные матрицы A₀₀, A₀₁ и A₁₀ должны иметь соответствующие им большие коэффициенты ?_kl для почти постоянных функций f. В случае быстро меняющихся яркостей изображения большие значения будут иметь коэффициенты при матрицах A₆₇, A₇₆ и A₇₇,. Отвечающих за большой контраст соседних областей, по аналогии с блоком 2х2: контраст правого и левого, верхнего и нижнего, а также их сумма.

11. Стандарт JPEG

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

С теми фактами, которые мы узнали о дискретном преобразовании и коэффициентах ?_kl, выглядит разумным позволить низкочастотным компонентам (с малыми значениями l и k) играть бoльшую роль, в то время как высокочастотным компонентам (с l и k, близкими к N) играть меньшую роль. Следующее правило является руководством: всякая потеря информации, которая незаметна для человеческого зрения, является допустимой.

Алгоритм сжатия может быть разделен на следующие главные шаги:

· преобразование функции изображения;

· применение дискретного преобразования к каждому блоку 8х8;

· квантизация преобразованных коэффициентов;

· зигзагообразное упорядочивание и кодирование преобразованных коэффициентов.

Опишем каждый из этих шагов подробнее.

Преобразование функции изображения. Первый шаг представляет собой преобразование значений f значением 2^b-1, где b - число битов, для представления каждого пикселя. Мы рассматриваем случай b=8, поэтому 2^b-1 =2⁷ =128 мы вычитаем из каждого пикселя. Этот первый шаг дает нам функцию , значения которой лежат в интервале [-2^b-1, 2^b-1-1], что является почти симметричным относительно нуля, как диапазон функции и формы базисных матриц A_kl. Напомним, что мы раньше предположили о кодировании тональности изображения каждого пикселя в диапазоне целых чисел [0,255].

Значения преобразованной функции, таким образом, равны .

12. Дискретное преобразование каждого блока 8х8 пикселей

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

13. Квантизация преобразованных коэффициентов

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

,

где [x] - целая часть числа x.

Поясним источник этой формулы. Так как множество чисел, представимых в компьютере, конечно, то математическая концепция непрерывной действительной оси неестественна для компьютера. Числа должны подвергнуться дискретизации, но должны ли мы при этом использовать максимально достижимую степень точности? Можем ли мы провести их дискретизацию по более грубой шкале? Стандарт JPEG допускает большую гибкость в этом шаге: каждый коэффициент ?_kl заменяется приближенно дискретной величиной со своим шагом квантизации. Размер шага кодируется в таблице квантизации, которая используется в дальнейшем во всех 8х8 блоках данного изображения.

Поясним использование величин q_kl на примере. Пусть q₀₀=10, тогда все ?₀₀, например, от 5 до 15, не включая правую границу, то есть [5,15) будут соответствовать L₀₀=1:



и

для произвольного малого положительного числа ?.

После восстановления сжатого изображения (декомпрессии) величина L_kl ?q_kl будут соответствовать коэффициенту до сжатия изображения. Дробь ? в формуле обеспечивает попадание числа в середину диапазона. Если величина q_kl выбрана сравнительно большой, например, q_kl=90, то числа ?_kl, лежащие в диапазоне [-45,45) будут все отображаться в нуль. Точное значение коэффициента внутри этого интервала будет при сжатии безвозвратно утеряно. Таблицы для квантизации подбираются так, чтобы большим ?_kl соответствовали меньшие диапазоны, а малым ?_kl - большие, так как малые значения играют малую роль и потеря точности в этом случае считается допустимой.

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

14. Зигзагообразное упорядочение и кодирование

Последним шагом алгоритма сжатия является кодирование таблицы квантизованных коэффициентов L_kl. Стандарт JPEG предпочитает коэффициенты с малыми абсолютными величинами: чем меньше | L_kl |, тем меньше длина кода для записи этой величины. Не является удивительным, что большинство коэффициентов L_kl равны нулю, так как ?_kl и, соответственно, L_kl обычно соответствуют изменениям, которые относительно малы в тональных яркостях фотореалистичных изображений).

Благодаря шагу квантизации, многие величины L_kl с большими номерами k и l равны нулю. Кодирование использует этот факт, упорядочивая коэффициенты так, чтобы длинные строки нулевых коэффициентов были близки. Точное упорядочивание, принятое в стандарте JPEG, таково:

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

15. Восстановление

Компьютер может быстро восстановить (распаковать) фото по информации в JPEG файле. Таблица квантизации считывается из заголовка файла. Затем следующие шаги выполняются для каждого блока 8х8 пикселей: информация считывается, пока не будет найден адрес "конец блока". Компьютер умножает каждый коэффициент L_kl на соответствующую величину q_kl. Коэффициент в этом случае оказывается в середине диапазона, в котором находился ?_kl. Обратное дискретное преобразование применяется к величинам ?, чтобы получить новые серые тона :

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

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

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

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



16. Поисковые системы

Инструменты для автоматического поиска появились в последние несколько десятилетий. Можно перечислить различные области деятельности, в которых люди имеют дело с большими объемами информации: библиотечные каталоги, государственные реестры, отраслевые базы данных. Эти объемы информации имеют некоторые общие черты. Прежде всего, они содержат информацию, которая собрана с точно определенной целью. Например, все книги в библиотеке содержат название, имеют одного или нескольких авторов, название издательства и т.д. Однородность данных, согласно которым организована соответствующая база, облегчает поиск. Качество информации также очень высоко. Например, записи о книгах в библиотечный каталог обычно вносятся профессионалами, поэтому уровень ошибок обычно невысок. Если же ошибки случаются, то простота устройства каталога облегчает процесс устранения ошибки. Одинаковость потребностей пользователей также является преимуществом, которое используется при организации подобных систем. Цель каталога - создание списка книг, которые доступны в данный момент. Даже если используются специальные термины, что случается в медицинских или юридических базах данных, пользователи, которые являются профессионалами в своих областях, обычно знакомы с ними. Поэтому поиск в этих базах данных легко осуществляется всеми пользователями.

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

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

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

Однако большинство страниц написаны на языке HTML или его диалектах, кроме того, метод кодировки ссылок на страницы в сети более или менее одинаков. Эти URL используются путешественниками по сети при переходе с одной страницы на другую. Компьютер может выделить URL среди текста изображений и других элементов веб-страницы. В 1998 г. 4 исследователя из Стэнфордского университета L.Page, S.Brin, R.Motwani, I.Winograd предложили алгоритм для ранжирования страниц сети. Этот алгоритм,PageRank, этот алгоритм использует только структуру связи между страницами.

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

17. Сеть Интернет и цепи Маркова

Сеть Интернет состоит из миллиардов отдельных страниц и гораздо большего числа связей между этими страницами. В связи с этим, сеть может быть смоделирована как ориентированный граф, где страницам соответствуют вершины, а ссылкам ориентированные дуги между ними. Например, на рисунке представлена маленькая сеть, состоящая из 5 страниц (A,B,C,D и E).

Ориентированные дуги между вершинами указывают, что

· единственная ссылка со страницы A ведет к странице B;

· страница B ссылается на страницы A и C;

· единственная ссылка со страницы D ведет к странице A;

· со страницы C ссылки идут к страницам A, B и E;

· страница E ссылается на страницы

Чтобы определить ранжирование этой небольшой сети из пяти вершин, рассмотрим упрощенную версию PageRank-алгоритма. Предположим, что гипотетический путешественник по этой сети случайным образом выбирает ссылки для перехода от одной страницы к другой. Если он имеет лишь один вариант передвижения (например, если он находится на странице D), то он переходит по единственной ссылке (на страницу A в данном случае). Если он находится на странице C, он перейдет с вероятностью ? на страницу A и точно также на страницы B и E. Другими словами, он, находясь на некоторой странице, выбирает с равной вероятностью исходящие из этой страницы ссылки. Если такой гипотетический путешественник ползал по этой сети указанным образом, выбирая по одной ссылке каждую минуту, где он будет находиться через час, через два дня, или через некоторое число переходов? Более точно, так как его путь задан вероятностным способом, с какой вероятностью он будет находиться на заданной странице после заданного промежутка времени?

Рисунок демонстрирует ответ на этот вопрос для первых двух шагов гипотетического путешественника, стартующего со страницы C. Эта страница содержит три исходящие ссылки; поэтому путешественник может перейти только на одну из следующих страниц: A, B и E. Так после первого шага он может попасть на страницу A с вероятностью ?, на страницу B с вероятностью ? и на страницу E с вероятностью ?. Это указано в средней колонке рисунка с тремя уравнениями

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

.

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

Третья колонка на рисунке демонстрирует возможные пути на втором шаге. Если путешественник был на странице A после первого шага, он будет гарантированно на странице B после второго шага. Так как он был на странице A с вероятностью , этот путь вносит в вероятность оказаться на B после второго шага. Однако, p(B) не равно после второго шага, поскольку имеется другой независимый путь, который приводит туда: C E B. Если путешественник окажется после первого перемещения на странице E, он с равной вероятностью может перейти по трем ссылкам на страницы B, C и D. Каждый из этих путей вносит к вероятностям p(B), p(C), p(D) после второго шага. После двух шагов путешественник находится на данной странице со следующими вероятностями:

.

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

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

Пусть случайный процесс, то есть семейство случайных величин, перенумерованных целыми значениями величины n. Мы предположим, что каждая из этих случайных величин принимает значения из конечного множества S. В примере путешествия по заданной сети, S - набор web-страниц . Для каждого шага положение путешественника есть . Придерживаясь языка теории случайных процессов, мы определили ранее вероятности возможных исходов для и , предполагая, что прогулка начинается с вершины . Это может быть выражено как условная вероятность события P(I|J), вычисленной при условии, что событие J произошло. Например, дает вероятность того, что путешественник оказался на странице А на шаге 1, после того, что он был на странице С в начале своего путешествия.