1.1.3 Оценка качества восстановления

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

Логичный способ оценки качества алгоритма – сравнение числа бит, требуемых для передачи оригинала и числа бит, требуемых для передачи данных после обработки, т.е. оценка качества алгоритма по коэффициенту сжатия. Предположим, что мы обрабатываем изображение размером 256 на 256 пикселов. Объем, требуемый для передачи такого количества информации – 65536 байт. Допустим, что после сжатия данных, они занимают всего 16384 байта, т.е. коэффициент сжатия 4 к 1.

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

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

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

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

2. Математические основы кодирования с потерями информации

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

2.1 Введение

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

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

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

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

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

Xc