СПОСОБ СЖАТИЯ ГРАФИЧЕСКИХ ФАЙЛОВ
METHOD OF COMPRESSING GRAPHICS FILES

Изобретение относится к обработке, сжатию и передаче информации, в частности к способу сжатия графических файлов, и может быть использовано в системах передачи и приема сжатых графических файлов.
Из уровня техники известен способ (US 7020837, 28.03.2006) сжатия графического содержания в сложных файлах PDF, содержащих комбинированные сложные графические страницы, каждая из которых составлена из базовой страницы и нескольких наложений, а также страниц PDF. При этом страницы и графические элементы каждой страницы сохраняют в статических файлах PDF.
Известен способ (CN 1595452, 16.03.2005) сжатия без потерь для графического файла, в котором сжимают графический файл согласно заданным параметрам длины регистра сжатия, для чего выбирают оптимальный параметр длины регистра сжатия. После этого сжимают графический файл согласно выбранному оптимальному параметру длины. Затем формируют файл сжатия, в который помещают сжатую информацию и сжатые о ней данные.
Недостатками указанных способов-аналогов является то, что после передачи сжатых файлов и их декомпрессии графическое изображение на выходе теряет четкость при том, что способы-аналоги обеспечивают относительно низкую степень сжатия, что не позволяет сжатые ими файлы передавать с большой скоростью по каналам передачи данных.
Наиболее близким аналогом по технической сущности к заявленному является контурный способ сжатия графических файлов (патент RU 2339998 по заявке 2007108339/09, 06.03.2007 г.).
В наиболее близком способе-аналоге исходный кадр графического изображения (ИКГИ) уменьшают при помощи специальной функции (ресайза, описанной в патенте RU 2339998 по заявке 2007108339/09, 06.03.2007 г., или посредством программы «Microsoft office picture manager», которая входит в состав пакета программ «Средства Microsoft Office»), по меньшей мере, в 4 раза. Сжимают и сохраняют его в сжатом файле, который декомпрессируют и увеличивают, по меньшей мере, в 4 раза. Затем ИКГИ накладывают на декомпрессионный увеличенный кадр, производят поиск разницы пиксельных значений между ИКГИ и декомпрессионным увеличенным кадром из заданного значения контраста по признаку контрастных элементов при помощи арифметического вычитания друг из друга. После полученный кадр со значениями контура контрастных элементов (ККЭ) сжимают без потерь и сохраняют в сжатом файле.
Недостаток наиболее близкого способа-аналога состоит в том, что для сжатых с его применением файлов ИКГИ с достаточно низким показателем контрастности обеспечивается относительно невысокая скорость передачи данных. Это обусловлено относительно низкой степенью сжатия соответствующих указанным ИКГИ кадрам со значениями ККЭ, так как те содержат относительно малое число нулевых коэффициентов.
Целью заявленного технического решения является разработка такого способа сжатия графических файлов, который обеспечивает более высокую скорость передачи данных, за счет максимально возможной степени сжатия ИКГИ и его кадра со значениями ККЭ для предварительно заданного числа N градаций уменьшения геометрических размеров ИКГИ.
Поставленная цель достигается тем, что в способе сжатия графических файлов, заключающемся в том, что уменьшают геометрические размеры ИКГИ, сжимают его и сохраняют в сжатом файле, который затем декомпрессируют и декомпрессированный кадр увеличивают до геометрических размеров ИКГИ, после чего вычисляют кадр со значениями ККЭ путем алгебраического вычитания пиксельных значений ИКГИ и увеличенного декомпрессированного кадра, затем полученный в результате вычитания кадр в виде ККЭ сжимают и сохраняют в сжатом файле. Предварительно задают число N градаций уменьшения геометрических размеров ИКГИ, причем для каждой n-й градации, где n=1, 2,…, N , последовательно выполняют действия по уменьшению геометрических размеров ИКГИ, его сжатию, сохранению в сжатом файле, декомпрессированию, увеличению декомпрессированного кадра до первоначального геометрического размера ИКГИ, вычитанию из пиксельных значений ИКГИ пиксельных значений увеличенного декомпрессированного кадра, сжатию полученного в результате вычитания кадра в виде ККЭ и его сохранению, затем суммируют n-е значение уменьшенного сжатого кадра и его сжатого ККЭ, запоминают вычисленную сумму, после чего из всех N значений запомненных сумм выделяют наименьшую, причем дополнительно сохраняют сжатый файл ККЭ и сжатый файл с уменьшенными геометрическими размерами ИКГИ, принадлежащих n-й градации, при которой сумма сжатого файла ККЭ и сжатого файла с уменьшенными геометрическими размерами ИКГИ наименьшая.
Уменьшают геометрические размеры ИКГИ с использованием процедуры бикубической интерполяции. Сжимают ИКГИ с использованием алгоритма дискретного косинус-преобразования. Декомпрессируют ИКГИ с использованием алгоритма дискретного косинус-преобразования. Увеличивают геометрические размеры декомпрессированного уменьшенного ИКГИ с использованием процедуры бикубической интерполяции. Сжимают кадр со значениями ККЭ с использованием алгоритма сжатия без потерь.
Благодаря новой совокупности существенных признаков обеспечивается более высокая скорость передачи данных для предварительно заданного числа N градаций уменьшения геометрических размеров ИКГИ за счет достижения минимального размера (в байтах) суммарного значения файла уменьшенного сжатого ИКГИ и его сжатого ККЭ.
Заявленный способ поясняется чертежами, на которых показаны:
фиг.1. Принцип уменьшения геометрических размеров ИКГИ для числа градаций N=5. Здесь L - горизонтальный размер ИКГИ, выраженный в пикселях; Н - вертикальный размер ИКГИ, выраженный в пикселях;
фиг. 2. Сжатые формы ИКГИ (H×L) и его уменьшенных копий: в два раза (H/2)×(L/2); в три раза (H/3)×(L/3); в четыре раза (H/4)×(L/4); в пять раз (H/5)×(L/5), с помощью алгоритма дискретного косинус-преобразования, реализованного в стандарте JPEG (способ сжатия графических файлов JPEG (англ. Joint Photographic Experts Group, по названию организации-разработчика));
фиг. 3. Кадры копий, ранее уменьшенных в один раз H×L и в два раза (H/2)×(L/2), после операций их декомпрессии и увеличения до геометрических размеров ИКГИ (копия H×L была только декомпрессирована, ее геометрические размеры не изменялись);
фиг. 4. Кадры копий, ранее уменьшенных в три раза (H/3)×(L/3) и в четыре раза (H/4)×(L/4), после операций их декомпрессии и увеличения до геометрических размеров ИКГИ;
фиг. 5. Кадр копии, ранее уменьшенной в пять раз (H/5)×(L/5), после операции декомпрессии и увеличения до геометрических размеров ИКГИ и кадр со значениями ККЭ, полученный в результате разности значений пикселей ИКГИ и декомпрессированной увеличенной до геометрических размеров ИКГИ копии, ранее уменьшенной в пять раз (H/5)×(L/5).
Способ сжатия графических файлов JPEG (файл JPEG - сжатый файл с расширением *.jpg (англ. Joint Photographic Experts Group, по названию организации-разработчика)) содержит следующие этапы.
1. Предварительно задают число N градаций уменьшения геометрических размеров ИКГИ. В общем случае рассматриваемое число градаций может быть произвольным. Однако целесообразен выбор такого числа N, при котором деление геометрической высоты Н и длины L ИКГИ будет осуществляться без остатка, т.е. Н/N - целое число и L/N - целое число.
В качестве примера на фиг. 1 представлен ИКГИ и его копии: уменьшенные в два раза (H/2)×(L/2); в три раза (H/3)×(L/3); в четыре раза (H/4)×(L/4); в пять раз (H/5)×(L/5) и в один раз, т.е. без изменений (H×L).
2. Для каждой n-й градации, где n=1, 2,…, N, последовательно выполняют действия по уменьшению геометрических размеров ИКГИ, его сжатию, сохранению в сжатом файле. Уменьшить геометрические размеры ИКГИ можно на основе бикубической интерполяции (см. Г.Корн, Т.Корн. Справочник по математике (для научных работников и инженеров). М.: Наука. - 1974 г., стр. 675-683; см. ссылку http://ru.wikipedia.org/wiki/ Бикубическая_интерполяция). Сжать ИКГИ и сохранить его в сжатом файле можно на основе алгоритмов, реализующих дискретное косинус-преобразование (см. С.Бернард. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. - М.: Издательский дом «Вильямс». - 2003 г., стр. 892 - 900; см. ссылку http://ru.wikipedia.org/wiki/JPEG). Хранить файл можно на жестком диске или в оперативной памяти ЭВМ.
В качестве примера на фиг. 2 представлены сжатые формы ИКГИ и его уменьшенных копий. Файл JPEG - сжатый файл с расширением *.jpg (см. ссылку http://ru.wikipedia.org/wiki/JPEG).
3. Декомпрессируют, увеличивают декомпрессированный кадр до первоначального геометрического размера ИКГИ. Декомпрессия - это операция, обратная сжатию. Ее реализация известна (см. С.Бернард. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. - М.: Издательский дом «Вильямс». - 2003 г., стр. 892-900; см. ссылку http://ru.wikipedia.org/wiki/JPEG). Увеличить геометрические размеры декомпрессированного файла до размеров ИКГИ можно на основе бикубической интерполяции (см. Г.Корн, Т.Корн. Справочник по математике (для научных работников и инженеров). М.: Наука. - 1974 г., стр. 675-683; см. ссылку http://ru.wikipedia.org/wiki/Бикубическая_интерполяция).
В качестве примера на фиг. 3, фиг. 4 и фиг. 5 представлены кадры копий, ранее уменьшенных в два раза (H/2)×(L/2), в три раза (H/3)×(L/3), в четыре раза (H/4)×(L/4), в пять раз (H/5)×(L/5) и в один раз, т.е. без изменений (H×L) после операций их декомпрессии и увеличения до геометрических размеров ИКГИ.
4. Вычитают из пиксельных значений ИКГИ пиксельные значения увеличенного декомпрессированного кадра. В результате вычитания получают кадр в виде ККЭ. Указанную процедуру можно реализовать посредством вычитания из пиксельных значений матрицы ИКГИ пиксельных значений матрицы увеличенного декомпрессированного кадра. Операция вычисления разности двух матриц известна (см. Справочник по высшей математике / А.А.Гусак, Г.М.Гусак, Е.А.Бричикова. - 2-е изд., стереотип. Мн.: ТетраСистем, 2000. С.102).
В качестве примера на фиг. 5 представлены кадр копии, ранее уменьшенной в пять раз (H/5)×(L/5), после операций ее декомпрессии и увеличения до геометрических размеров ИКГИ и кадр ККЭ, полученный в результате вычитания из пиксельных значений ИКГИ пиксельных значений увеличенного декомпрессированного кадра (H/5)×(L/5). Кадр в виде ККЭ представляет собой графический файл BMP (от англ. Bitmap Picture - формат хранения растровых изображений, разработанный компанией Microsoft). В данном графическом формате BMP сохраняют в файл (* .bmp) и ИКГИ.
5. Сжимают полученный в результате вычитания кадр в виде ККЭ и сохраняют его в виде файла. Сжимают кадр со значениями ККЭ на основе алгоритмов сжатия без потерь (см. Сжатие и шифрование при обработке, хранении и передаче информации. Григорьев В.А., Григорьев С.В. Под ред. Григорьева В.А. СПб.: ВУС. 2000. С.74-97; см. ссылку http://ru.wikipedia.org/wiki/Cжaтиe_дaнных_без_потерь). Примером формата, реализующего алгоритм сжатия данных без потерь, является формат ARJ, который формирует файлы сжатых данных с расширением (*.arj). Хранить файл можно на жестком диске или в оперативной памяти ЭВМ.
6. Суммируют n-е значение уменьшенного сжатого кадра и его сжатого ККЭ, запоминают вычисленную сумму. Значение файла уменьшенного сжатого кадра и его сжатого ККЭ определяют в байтах, поэтому вычисленная сумма для каждого n-го значения уменьшенного сжатого кадра и его сжатого ККЭ также будет выражаться в байтах.
Например, объем ИКГИ в формате BMP составляет 921654 байта (см. фиг. 1). После его сжатия без потерь алгоритмом ARJ итоговый объем файла составил 343302 байта. Объем файлов сжатых копий ИКГИ алгоритмом с потерями JPEG для градаций уменьшения геометрических размеров n=1, 2, 3, 4, 5 соответственно составил: 43943; 13071; 7026; 4589; 3331 байтов. Объем сжатых ККЭ алгоритмом ARJ для градаций n=1, 2, 3, 4, 5 соответственно составляет: 304870; 285057; 287018; 293179; 288255 байтов. Следовательно, сумма для каждого n-го значения уменьшенного сжатого кадра с градациями n=1, 2, 3, 4, 5 и его сжатого ККЭ соответственно составляет: 348813; 298128; 294044; 297768; 291556 байтов.
Операции сложения известны (см. Г.Корн, Т.Корн. Справочник по математике (для научных работников и инженеров). М.: Наука. - 1974 г., стр.27).
7. Выделяют наименьшую из всех N значений запомненных сумм, причем дополнительно сохраняют сжатый файл ККЭ и сжатый файл с уменьшенными геометрическими размерами ИКГИ, принадлежащих n-й градации, при которой сумма сжатого файла ККЭ и сжатого файла с уменьшенными геометрическими размерами НЕСТИ наименьшая. Наименьшее из значений запомненных сумм можно выбрать в результате их сравнения между собой, а хранить файлы можно путем их записи на жесткий диск или в оперативную память ЭВМ.
Для рассмотренного в п.6 примера наименьшая из запомненных сумм соответствует градации уменьшения геометрического размера n=5. Указанная сумма меньше объема ИКГИ после его сжатия без потерь алгоритмом ARJ.
Таким образом, благодаря новой совокупности существенных признаков обеспечивается наибольшая скорость передачи данных для предварительно заданного числа N градаций уменьшения геометрических размеров ИКГИ за счет достижения минимального размера (в байтах) суммарного значения файла уменьшенного сжатого ИКГИ и его сжатого ККЭ.
Следует заметить, что непосредственное применение способа-прототипа для рассмотренного примера позволяет получить суммарное значение размера файла уменьшенного сжатого ИКГИ и его сжатого ККЭ файла уменьшенного сжатого ИКГИ и его сжатого ККЭ, равное 297768 байтов, которое на 6212 байтов превышает значение суммы, обеспечиваемой предложенным способом.