Введение
Актуальность
Многие отрасли техники, имеющие отношение к получению, обработке, хранению и передаче информации, в значительной степени ориентируются в настоящее время на развитие систем, в которых информация имеет характер изображений. Решение научных и инженерных задач при работе с визуальными данными требует особых усилий, опирающихся на знание специфических методов.
Выбор метода - это первая задача, которую должен решить разработчик программных средств сжатия данных. Выбор зависит от типа данных, которые предстоит обрабатывать, аппаратных ресурсов, требований к степени сжатия и ограничений на время работы программы.
Существует множество программных продуктов, позволяющих сжимать графические изображения. Но все они сжимают изображения в заданном пользователем формате, запрашивая у него необходимые параметры сжатия. Т.о. пользователь сам принимает решение о том, как сжимать изображение или ряд изображений, зачастую по незнанию выбирая не самый подходящий формат или параметры.
Одна из серьезных проблем машинной графики заключается в том, что до сих пор не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати.
Необходимо отметить, что среди существующих методов нет универсального, который был бы эффективен для всех видов растровых изображений. Для изображений с небольшим количеством цветов 4-6 эффективными, как правило, оказываются методы сжатия без потерь, тогда как применением методов сжатия с потерями таких же результатов можно добиться ценой существенных потерь. Но количество цветов не является достаточным признаком для выбора того или иного метода для сжатия конкретного изображения. Для методов сжатия с потерями не существует адекватной оценки потерь. Наилучшим методом является визуальная оценка. При использовании количественных оценок для одних изображений хорошее качество восстановленного изображения характеризуется меньшими их показателями, чем для других. В связи со всем выше перечисленным, встает задача определения для каждого конкретного изображения метода и параметров сжатия, обеспечивающие оптимальное соотношение между степенью сжатия и качеством.
Можно привести пример простого критерия оценки потерь качества изображения: среднеквадратичное отклонение значений пикселов (L2 мера, или root mean square - RMS):
d(x,y)=SQRT( SUMi,j=1 to n(xi,j-yi,j)2 / n2 ) (1)
По нему изображение будет сильно испорчено при понижении яркости всего на 5% (глаз этого не заметит - у разных мониторов настройка яркости варьируется гораздо сильнее). В то же время изображения "со снегом" - резким изменением цвета отдельных точек, слабыми полосами или "муаром" - будут признаны "почти не изменившимися".
Свои неприятные стороны есть и у других критериев. Рассмотрим, например, максимальное отклонение:
d(x,y)= MAXi,j ABS(xi,j-yi,j) (2)
Эта мера, как можно догадаться, крайне чувствительна к биению отдельных пикселов. То есть во всем изображении может существенно измениться только значение 1 пиксела (что практически незаметно для глаза), однако согласно этой мере изображение будет сильно испорчено.
Мера, которую сейчас используют на практике, называется мерой отношения сигнала к шуму (peak-to-peak signal-to-noise ratio - PSNR):
d(x,y)= 10*lg(2552*n2 / [SUMi,j=1 to n(xi,j-yi,j)2] (3)
Данная мера, по сути, аналогична среднеквадратичному отклонению, однако пользоваться ей несколько удобнее за счет логарифмического масштаба шкалы. Ей присущи те же недостатки, что и среднеквадратичному отклонению.
Лучше всего потери качества изображений оценивают наши глаза. Отличным считается сжатие, при котором невозможно на глаз различить первоначальное и распакованное изображения. Хорошим - когда сказать, какое из изображений подвергалось сжатию, можно только сравнивая две находящиеся рядом картинки. При дальнейшем увеличении степени сжатия, как правило, становятся заметны побочные эффекты, характерные для данного алгоритма. На практике, даже при отличном сохранении качества, в изображение могут быть внесены регулярные специфические изменения. Поэтому алгоритмы сжатия с потерями не рекомендуется использовать при сжатии изображений, которые в дальнейшем собираются либо печатать с высоким качеством, либо обрабатывать программами распознавания образов. Неприятные эффекты с такими изображениями могут возникнуть даже при простом масштабировании изображения.
Цель и задачи работы
Целью магистерской работы является разработка компьютерной подсистемы выбора оптимального алгоритма сжатия растровых статичных изображений.
Для достижения данной цели необходимо решить следующие задачи:
" рассмотреть существующие алгоритмы сжатия изображений;
" проанализировать характер растровых статичных изображений, специфику их использования, и с учетом этого выбрать наиболее эффективные алгоритмы сжатия;
" определить критерий оптимальности алгоритмов с учетом специфики задачи;
" проанализировать возможные методы поиска оптимального алгоритма и выбрать наиболее подходящий из них;
" на основе выбранного метода создать программный продукт.
Предполагается применение следующих методов исследования: обзор литературных источников и патентный поиск по данной теме, в том числе поиск в Internet; инженерный анализ эффективности применения существующих алгоритмов и методов; сравнение фактических результатов работы различных алгоритмов.
Обзор по теме
Вопросами сжатия и оптимизации изображений занимаются различные компании. Компания Adobe Systems, основанная в 1982, является одним из ведущих производителей программного обеспечения для графического дизайна, публикации, Web и продукции печати. Канадская компания Corel завоевала известность благодаря своему флагманскому пакету CorelDRAW. Многочисленные продукты этой компании включают инструменты оптимизации графических изображений для размещения в Internet и полиграфии. Компания ACD Systems была основана в 1993 г в Британской Колумбии. Занимается разработкой и распространением широкого спектра продуктов и для профессионального, и домашнего использования. В большинство продуктов ACD Systems (ACDSee, RealOptimizer) также включена возможность оптимизации изображений в различных форматах.
 |
|
Анимированный gif
5 кадров с задержкой 1,5 секунды
320х240
Глубина цветности 128 бит
Размер 86,6 КБайт
5 повторов |
Сравнение алгоритмов по степени сжатия
Решение задачи сравнения алгоритмов по достигаемой ими степени сжатия требует введения некоторого критерия, так как нельзя сравнивать производительность реализаций на каком-то абстрактном файле. Следует осторожно относиться к теоретическим оценкам, так как они вычисляются с точностью до констант. Величины этих констант на практике могут колебаться в очень больших пределах, особенно при сжатии небольших файлов.
В 1989 г. группа исследователей предложила оценивать коэффициент сжатия с помощью набора файлов, получившего название Calgary Compression Corpus [2] (CalgCC). Набор состоит из 14 файлов, большая часть которых представляет собой тексты на английском языке или языках программирования. Позже к этим 14 файлам были добавлены еще 4 текста на английском языке.
Следует заметить, что на данный момент набор серьезно устарел. Среди стандартных наборов тестовых изображений наиболее известны четыре: JPEG Set, PNG Set, Waterloo Images и Kodak True Color Images.
Заключение
В данной работе
" Приведена классификация (условная) изображений, а также приложений, использующих алгоритмы компрессии графики и предъявляемые к ним требования.
" Определены их особенности как типа данных: большой объем, характерное восприятие человеком, избыточность данных в двух измерениях.
" Обзорно перечислены используемые в настоящий момент форматы хранения изображений. Выделены их особенности, отличия от алгоритмов архивации, а также отличия алгоритмов от применяемых методов сжатия изображений.
" Приведены примеры сравнения алгоритмов. Необходимо отметить, что среди существующих методов нет универсального, который был бы эффективен для всех видов растровых изображений.
" Проанализировано современное состояние разработок в области сжатия изображений.
" Выделены основные проблемы, существующие в данной области и нерешенные задачи. Одной из серьезных проблем машинной графики является то, что до сих пор не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати. Данная задача в полной мере еще не решена, поскольку для этого потребуется создание системы, столь же сложной что и мозг человека. Т.о. наилучшим методом является визуальная оценка качества изображения.
Из поставленных задач на данный момент не все решены. В связи с этим планируется выполнить следующее:
" проанализировать возможные методы поиска оптимального алгоритма и выбрать наиболее подходящий из них;
" обосновать выбор наиболее эффективного алгоритма сжатия для данных конкретных условий;
" создать программный продукт.
Изображения - своеобразный тип данных, характеризуемый тремя особенностями.
1. Изображение (как и видео) обычно требует для хранения гораздо большего объема памяти, чем текст.
2. Человеческое зрение при анализе изображения оперирует контурами, общим переходом цветов и сравнительно нечувствительно к малым изменениям в изображении. Данная особенность человеческого зрения позволила создать специальные алгоритмы сжатия, ориентированные только на изображения. Эти алгоритмы позволяют сжимать изображения с высокой степенью сжатия и незначительными с точки зрения человека потерями.
3. Изображение обладает избыточностью в двух измерениях. То есть, как правило, соседние точки, как по горизонтали, так и по вертикали, в изображении близки по цвету.
Требования приложений к алгоритмам компрессии:
" Высокая степень компрессии
" Высокое качество изображений
" Высокая скорость компрессии
" Высокая скорость декомпрессии
" Устойчивость к ошибкам
" Масштабирование изображений
" Учет специфики изображения
" Редактируемость
" Возможность показать огрубленное изображение
Нет смысла говорить о том, что какой-то алгоритм сжатия лучше другого, если мы не обозначили классы изображений, на которых сравниваются алгоритмы, равно как и о том, что какой-то конкретный алгоритм компрессии лучше другого, если мы не обозначили класс приложений, относительно которого мы эти алгоритмы собираемся сравнивать. На практике для каждой задачи мы можем сформулировать набор приоритетов из требований, изложенных выше, который и определит наиболее подходящий в наших условиях алгоритм (либо набор алгоритмов) для ее решения.
Литература
1. Грузман И.С., Киричук В.С., Косых В.П., Перетягин Г.И., Спектор А.А. ЦИФРОВАЯ ОБРАБОТКА ИЗОБРАЖЕНИЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ: Учебное пособие. - Новосибирск: Изд-во НГТУ, 2000. - 168.
2. Bell Т. С, Witten I. H. Cleary, J. G. Modeling for text compression //ACM Computer Survey. 1989. Vol. 24, № 4. P. 555-591.
3. http://www.gurovdima.narod.ru/Soft.htm - домашняя страница Дмитрия Гурова, создателя программы ImageAnalysis.
4. http://compression.ca/act-executable.html - сводные таблицы сравнения различных архиваторов и алгоритмов сжатия.
5. http://www.compression.ru - все о методах сжатия.
6. http://dushkin.boom.ru/resource/gl6.zip - генетические алгоритмы и нейросети.
7. Назаров Л.Е., Назарова З.Т. Нейросетевой, фрактальный и JPEG алгоритмы сжатия изображений. // Информационные технологии. - 2001. - №1. - с.3-10.
8. http://www.tiflocomp.ru/docs/fr80/fr80_1_6.php - обзор программ оптимизации графики.
9. http://fotoleto.ru/screenshot-optimization/index.html - Владимир Жуйков - Оптимизация изображений в различных программах.
10. http://photosoft.ru?ks_cat=23.htm - обзор программ оптимизации графики
11. http://archives.maillist.ru/35219/471376.html- обзор программ оптимизации графики.
12. Мастрюков Д. Алгоритмы сжатия информации. // Монитор. - 1994. - №1. - с.15-20.
13. Мастрюков Д. Алгоритмы сжатия информации. // Монитор. - 1994. - №3. - с.5-19.
14. Ватолин Д.С. Алгоритмы сжатия изображений. Методическое пособие. -М: Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В.Ломоносова (лицензия ЛР № 040777 от 23.07.96), 1999. - 76 с.
15. Ватолин Д.С. Сжатие статических изображений. // Открытые системы сегодня. - 1995.- № 8 (29). - с. 25-30.
16. Ватолин. Д.С. Тенденции развития алгоритмов архивации графики. // Открытые системы. - 1995. - №4. - с.10-13.
17. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. - СПб: ВУС, 1999. - 203 с.
18. Ефимов В.М., Колесников А.Н. Сжатие изображений с предварительной интерполяцией сигналов // 2-я Всероссийская с участием стран СНГ конф. "Распознавание образов и анализ изображений: новые информационные технологии" (Ульяновск, 28 августа - 1 сентября 1995): Тезисы докладов. ч.1. - Ульяновск: УГТУ, 1995. - с. 122-125.
19. Орловский Е.Л. Передача факсимильных изображений. - М.: Связь, 1980. - 125с.
20. Поспелов В.В., Кислицина М.А. Использование преобразования Хаара для модификации алгоритма JPEG - сжатия изображений. Тезисы доклада III конференции "Распознавание образов и анализ изображений".ч.I. - Н.Новгород: РОАИ, 1997. с. 210 - 212.
21. Просис Д. Файлы растровой графики: взгляд внутрь. // PC Magazine. - 1996. - December 3. - с. 3 - 21.
22. Прэтт У. Цифровая обработка изображений: Пер. с англ. - М.: Мир, 1982.-Кн. 2 - 480 с.
23. Уинтц П.А. Кодирование изображений посредством преобразований.-ТИИЭР. - тематический вып. "Обработка изображений при помощи цифровых вычислительных машин.". - 1972. - т. 60. - №7. - с. 69-48.
24. Яншин В.В. Анализ и обработка изображений: Принципы и алгоритмы: Учебное пособие для студентов вузов - М.: Машиностроение, 1995. - 111 c.
Литература по форматам графических файлов.
25. Климов А.С. Форматы графических файлов. - С.-Петербург: ДиаСофт, 1995.- 480с.
26. Матвеев С. Форматы графических файлов. // Открытые системы. - 1997.- №4. - с.12-15.
27. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC . - Москва: Унитех, 1992. - 320с.
28. Мюррей Д.Д. , Райнер У. Ван. Энциклопедия форматов графических файлов. Пер. с англ. - Киев: BHV, 1997, - 535с.
Литература по обработке и анализу изображений.
29. Александров В.В., Горский Н. Д. Алгоритмы и программы структурного метода обработки данных. - Л.: Наука, 1983. - 205с.
Литература по оценке эффективности методов сжатия.
30. Ефимов В.М., Золотухин Ю.Н., Колесников А.Н. Оценка эффективности некоторых алгоритмов сокращения избыточности информации при абсолютной точности воспроизведения. // Автометрия. - 1991. - № 6. - с. 50-55.
31. http://emanual.ru/download/www.eManual.ru_3962.html
32. http://home.uic.tula.ru/~s950417/sc_work1.htm
|
