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

Изобретение относится к обработке, сжатию и передаче информации, в частности к способу сжатия графических файлов, и может быть использовано в системах передачи и приема сжатых графических файлов.
Из уровня техники известен способ (US 7020837, 28.03.2006) для эффективного сжатия графического содержания в сложных файлах PDF, содержащих комбинированные сложные графические страницы, каждая из которых составлена из базовой страницы и нуля или более наложений, а также страниц PDF. При этом страницы и графические элементы каждой страницы сохранены в статических файлах PDF.
Известен способ (CN 1595452, 16.03.2005) сжатия без потерь для графического файла, в котором сжимают графический файл согласно заданным параметрам длины регистра сжатия. Выбирают оптимальный параметр длины регистра сжатия. После этого сжимают графический файл согласно выбранному оптимальному параметру длины. Затем главная информация файла (графическая информация), информация сжатия и так далее вместе со сжатыми данными записываются в файле, тем самым формируя файл сжатия.
Недостатком известных способов является то, что после передачи сжатых файлов и их декомпрессии графическое изображение на выходе теряет четкость, притом что способы-аналоги обеспечивают относительно низкую степень сжатия, что не позволяет сжатые ими файлы передавать с большой скоростью по каналам передачи данных.
Наиболее близким по технической сущности к заявленному является контурный способ сжатия графических файлов (патент РФ №2339998, 06.03.2007 г.). В известном способе-прототипе исходный кадр графического изображения (ИКГИ) уменьшают при помощи специальной функции (ресайза), по меньшей мере, в 4 раза, сжимают и сохраняют его в сжатом файле, который декомпрессируют и увеличивают, по меньшей мере, в 4 раза. Затем ИКГИ накладывают на декомпрессионный увеличенный кадр, производят поиск разницы пиксельных значений между ИКГИ и декомпрессионным увеличенным кадром из заданного значения контраста по признаку контрастных элементов при помощи арифметического вычитания друг из друга. Затем полученный кадр со значениями контура контрастных элементов сжимают без потерь и сохраняют в сжатом файле.
Недостаток способа-прототипа состоит в том, что он обеспечивает относительно низкую степень сжатия, поскольку кадр со значениями контура контрастных элементов, содержащий большое число пикселей, значения которых близки к нулевой величине, невозможно сжать без потерь с высокой степенью сжатия. В результате кадры графического изображения, сжатые способом-прототипом, невозможно передавать с большой скоростью по каналам передачи данных.
Техническим результатом заявляемого способа является повышение степени сжатия графических файлов и скорости их передачи по каналам данных для заданной величины пикового отношения сигнал/шум.
Это достигается тем, что способ сжатия графических файлов, включающий операции изменения геометрических размеров исходного кадра графического изображения с последующей декомпрессией кадров графического изображения и качественной оценки параметров, отличается тем, что предварительно задают величину пикового отношения сигнал/шум, присваивают переменной iter значение, равное нулю, затем над исходным кадром графического изображения A(l,h) размером  элементов выполняют двумерное вейвлет-преобразование размером , из вейвлет-коэффициентов которого формируют матрицу Y(l, h), где ; , которую затем сжимают, а потом декомпрессируют, после чего формируют нулевую матрицу размером  элементов и вместо элементов с индексами ;  помещают соответствующие элементы декомпрессированной матрицы , затем формируют восстановленное изображение путем выполнения обратного двумерного вейвлет-преобразования над нулевой матрицей размером  с измененными элементами с индексами ; , после чего определяют величину пикового отношения сигнал/шум, характеризующую качество восстановленного кадра по сравнению с исходным кадром графического изображения, и если вычисленное отношение превышает заданную величину, то выполняют описанные выше действия, увеличив текущее значение переменной iter на единицу и заменив матрицу исходного кадра графического изображения A(l, h) на сформированную матрицу Y(l, h), причем указанные действия повторяют до тех пор, пока вычисленное пиковое отношение сигнал/шум не станет меньше или равным заданной величине.
Заявленный способ поясняется чертежами, на которых показаны:
фиг.1 - исходный кадр графического изображения A(l, h) размером L×H, здесь L - горизонтальный размер кадра, выраженный в пикселях; H - вертикальный размер кадра, выраженный в пикселях;
1
фиг.2 - матрица вейвлет-коэффициентов исходного кадра графического изображения после процедуры двумерного вейвлет-преобразования, в пределах которой выделена матрица вейвлет-коэффициентов  Y(l, h), здесь и далее нижний индекс у Y(l, h), O(l, h), , A(l, h) указывает на количество выполненных процедур двумерного вейвлет-преобразования, по результатам которого указанные матрицы формировались;
1
фиг.3 - нулевая матрица O(l, h), содержащая нулевые значения, в позиции которых, определенных координатами l=1, …, L/2; h=1, …, H/2, помещены вейвлет-коэффициенты декомпрессированной матрицы ;
1
фиг.4 - восстановленный процедурами двумерного вейвлет-преобразования до исходного размера L×H декомпрессированный кадр  после сжатия алгоритмом JPEG его матрицы вейвлет-коэффициентов Y(l, h) размером (L/2)×(H/2), сформированной в результате двумерного вейвлет-преобразования [JPEG (файл JPEG - сжатый файл с расширением *.jpg (англ. Joint Photographic Experts Group, no названию организации-разработчика))];
1
фиг.5 - матрица вейвлет-коэффициентов после процедуры двумерного вейвлет-преобразования над Y(l, h);
2
фиг.6 - восстановленный процедурами двумерного вейвлет-преобразования до исходного размера L×H декомпрессированный кадр  после сжатия алгоритмом JPEG его матрицы вейвлет-коэффициентов Y(l, h) размером (L/4)×(H/4).
Способ сжатия графических файлов реализуется следующим образом.
1. Задают величину пикового отношения сигнал/шум (PSNR). Качество восстановленного кадра графического изображения  оценивают величиной PSNR по отношению к исходному кадру A(l, h). С учетом того, что исходный кадр графического изображения A(l, h) представляет собой трехцветное изображение и имеет 3 компоненты - R, G, B [см. Телевидение (общий курс). Под ред. П.В.Шмакова, М.: «Связь», 1970, с.41]. Следовательно, итоговое выражение для вычисления PSNR будет иметь вид:
k
где L - горизонтальный размер кадра графического изображения в пикселях; H - вертикальный размер кадра графического изображения; (l, h)-l-е, h-е значение пикселя k-й компоненты исходного кадра графического изображения; -l-е, h-е значение пикселя k-й компоненты декомпрессированного после сжатия и восстановленного кадра; B - число битов, отводимых на точку (в зависимости от количества представляемых цветов, на каждую точку отводится от 1 до 48 битов); K=3 - число компонентов R, G, B.
Чем меньше различий в числовых значениях пикселей между исходным кадром графического изображения A(l, h) и восстановленным , тем выше значение показателя PSNR. Следовательно, тем меньше претерпевает изменений файл после процедур прямого и обратного двумерного вейвлет-преобразования, а также сжатия и декомпрессии с помощью алгоритма JPEG.
В исходном состоянии кадр графического изображения хранится в графическом файле BMP (от англ. Bitmap Picture - формат хранения растровых изображений, разработанный компанией Microsoft). После сжатия - в графическом файле JPEG.
доп
доп
Выбор заданного качества восстановленного кадра графического изображения PSNR определяется техническими возможностями системы передачи информации или свободным объемом носителя информации. Чем ниже пропускная способность и чем меньше свободного места на носителе информации, тем меньшее значение выбирают для показателя PSNR.
2. Для первой итерации выбирают значение переменной iter=0. Затем над исходным кадром графического изображения A(l, h) размером  (для первой итерации iter=0: L×H) элементов вычисляют двумерным вейвлет-преобразованием размером . На фиг.1 представлен исходный кадр графического изображения A(l, h) размером L×H. Операции реализации двумерным вейвлет-преобразованием в общем случае известны и описаны в [Мала С. Вейвлеты в обработке сигналов. Пер. с англ. - М.: Мир, 2005, стр.329-336].
1
3. Из вейвлет-коэффициентов двумерным вейвлет-преобразованием размером  формируют матрицу вейвлет-коэффициентов Y(l, h), где;  (для iter=0:Y(l,h), размером (L/2)×(H/2)). На фиг.2 представлена матрица вейвлет-коэффициентов исходного кадра графического изображения после процедуры двумерного вейвлет-преобразования (вейвлет-коэффициенты матрицы на позициях
;
имеют величину, равную нулю, или очень близкие к нулю значения, поэтому имеют низкую энергию и отображаются на изображениях темным цветом; с целью наглядности и пояснения физического смысла на всех представленных фигурах нулевые значения вейвлет-коэффициентов выделены белым цветом).
1
4. Матрицу вейвлет-коэффициентов Y(l,h) (для iter=0:Y(l,h)) сжимают алгоритмом JPEG, после чего декомпрессируют. Процедуры сжатия и декомпрессии исходного кадра графического изображения известны (см. С.Бернард. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр. Пер. с англ. - М.: Издательский дом «Вильямс», - 2003 г., стр.892-900; см. ссылку http://ru.wikipedia.org/wiki/JPEG).
1
1
1
5. Формируют нулевую матрицу O(l, h) размером  элементов (для iter=0:O(l,h) размером L×H) и вместо элементов с индексами ;  помещают соответствующие элементы декомпрессированной матрицы  (для
). Нулевая матрица O(l, h) представляет собой матрицу размером L×H, значения всех элементов которой равны нулю. Затем элементы, находящиеся на позициях ;  (для iter=0 это позиции l=1, …, L/2; h=1, …, H/2), заменяют вейвлет-коэффициентами декомпрессированной матрицы
. На фиг.3 показана нулевая матрица O(l, h), содержащая нулевые значения, в позиции которых, определенных координатами l=1, …, L/2; h=1, …, H/2, помещены вейвлет-коэффициенты декомпрессированной матрицы
.
1
1
6. Формируют восстановленное изображение
(для
) путем выполнения обратного двумерного вейвлет-преобразования над нулевой матрицей O(l, h) размером , в позициях индексов
;
которой помещены вейвлет-коэффициенты декомпрессированной матрицы
. Операции реализации обратного двумерного вейвлет-преобразования известны (см. Мала С. Вейвлеты в обработке сигналов. Пер. с англ. - М.: Мир, 2005, стр.329-336). На фиг.4 показан восстановленный процедурами двумерного вейвлет-преобразования до исходного размера L×H декомпрессированный кадр
после сжатия алгоритмом JPEG его матрицы ВК Y(l, h) размером (L/2)×(H/2), сформированной в результате двумерного вейвлет-преобразования.
доп
7. Определяют величину пикового отношения сигнал/шум, характеризующую качество восстановленного кадра
по сравнению с исходным кадром графического изображения A(l, h), и сравнивают ее с заданной величиной PSNR.
iter
0
доп
Оценивают величину PSNR (для iter=0:PSNR) по формуле (1) и сравнивают ее с предварительно заданной величиной PSNR.
0
доп
iter
доп
iter
доп
Если PSNR>PSNR, то значение переменной iter увеличивают на единицу и этапы 2-7 повторяют каждый раз, помещая вместо исходного кадра графического изображения A(l, h) матрицу Y(l, h), сформированную на предыдущем этапе выполнения итераций, до тех пор, пока не будет выполнено условие PSNR≤PSNR. При достижении условия PSNR≤PSNR сжатый файл исходного кадра графического изображения используют для хранения или передачи информации.
2
1
2
В качестве примера на фиг.5 показана матрица вейвлет-коэффициентов, сформированная на второй итерации для iter=1, когда в качестве исходного кадра графического изображения A(l, h) использовалась матрица Y(l, h) размером (L/2)×(H/2), сформированная на первой итерации iter=0. На фиг.5 матрица Y(l, h) выделена фрагментом (L/4)×(H/4). На фиг.6 показан восстановленный исходный кадр графического изображения
.
Таким образом, благодаря новой совокупности существенных признаков, заключающейся в том, что последовательно выполняют процедуры двумерного вейвлет-преобразования формирования матрицы вейвлет-коэффициентов, ее сжатия, декомпрессии, восстановления исходного кадра графического изображения путем формирования нулевой матрицы с декомпрессированными вейвлет-коэффициентами и выполнения обратного двумерного вейвлет-преобразования, обеспечивается максимально возможная степень сжатия для заданной величины пикового отношения сигнал/шум, что приводит к повышению скорости передачи сжатых исходных кадров графического изображения по каналам данных.