Сжатие изображений. 32208-Текст статті-60612-1-10-20141207 (1). Исследование вейвлетного метода сжатия изображений для повышения быстродействия веб приложений аннотация
 Скачать 137.57 Kb.
|
|
Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) УДК 004.627 Е.В. Крылов, В.К. Аникин, Е.В. Аникина ИССЛЕДОВАНИЕ ВЕЙВЛЕТНОГО МЕТОДА СЖАТИЯ ИЗОБРАЖЕНИЙ ДЛЯ ПОВЫШЕНИЯ БЫСТРОДЕЙСТВИЯ ВЕБ ПРИЛОЖЕНИЙ Аннотация: Рассматривается методика повышения быстродействия веб- приложений путем уменьшения размеров загружаемых файлов, а именно сжа- тие изображений. При использовании изображений в цветном спектре с про- зрачностью был применен модифицированный метод вейвлетного сжатия, в частности с сохранением пяти, десяти и пятидесяти процентов коэффициен- тов для уменьшения размера сжатого файла изображения при условии сохра- нения его качества. Ключевые слова: сжатие изображений, быстродействия веб-приложений, вейвлетное сжатие, разностные коэффициенты. Введение На сегодняшний день повышение скорости работы сайтов явля- ется актуальной задачей. Методы повышения быстродействия мо- жно условно разделить на методы серверной и клиентской части сайта. Серверные методы используются в тех случаях, когда сер- вер, на котором расположен сайт, не выдерживает нагрузку и ско- рость работы сокращается для каждого пользователя. Клиентские методы направлены на ускорение загрузки информации в браузе- ре пользователя. Такие методы можно условно разделить на сле- дующие группы: • Уменьшение количества http запросов • Уменьшение размера загружаемых файлов • Повышение быстродействия стилей CSS • Повышение быстродействия скриптов javascript Уменьшение количества запросов необходимо для освобожде- ния соединения клиента с сервером и как следствие более быстрой загрузки общего контента. Для этого, например, используются ме- тоды объединения таблиц стилей и использование спрайтов. Повышение быстродействия таблиц стилей и скриптов заклю- чается в оптимизации этих файлов с целью их более быстрой ин- терпретации и выполнения. Например, для скриптов, необходимо уменьшать количество используемых внешних библиотек. Уменьшение размера загружаемых файлов является наиболее приоритетной задачей. Для этого используется очень большое ко- личество методов. Основными являются: архивация и сжатие c Е.В. Крылов, В.К. Аникин, Е.В. Аникина, 2013 ISSN 1560-8956 35 Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) HTML, CSS и javascript; минимизация стилей и скриптов; и мето- ды оптимизации и сжатия изображений. В этой статье уделено внимание последним из этих методов, а в частности, методам вейвлетного сжатия изображений [1]. Вейвлетное преобразование Предположим, что мы имеем последовательность, состоящую из 2 n точек [x 1 , x 2 , . . . , x 2 n ] для некоторого целого n > 0. Мы можем со- поставить эту последовательность со следующей функцией из ве- кторного пространства функций V n [2]: f (t) = x 1 ϕ n,0 (t) + . . . + x 1 ϕ n,2 n − 1 (t) (1) Первым шагом вычисления вейвлет-преобразования последова- тельности [x 1 , x 2 , . . . , x 2 n ] будет разложение f (t) по альтернативно- му базису пространства V n , половину которого составляют вейвле- ты: f (t) = a n−1,0 ϕ n−1,0 +. . .+a n−1,2 n−1 − 1 ϕ n−1,2 n−1 − 1 (t)+d n−1,0 ψ n−1,0 + + . . . + d n−1,2 n−1 − 1 ψ n−1,2 n−1 − 1 (t) (2) Коэффициенты d n−1,0 , . . . , d n−1,2 n−1 − 1 при базисных вейвлет- функциях составляют половину коефициентов вейвлет- преобразования, поэтому их значения сохраняются. Следующим шагом процесса преобразования является применение такого же базисного преобразования к остальным членам равенства: g n−1 (t) = a n−1,0 ϕ n−1,0 + . . . + a n−1,2 n−1 − 1 ϕ n−1,2 n−1 − 1 (t) (3) Таким образом g n−1 это элемент V n−1 и поэтому может быть ра- зложен по альтернативному базису состоящему из масштабирую- щих функций ϕ n−2,j и вейвлетов ψ n−2,j Для получения коэффициентов равенства используется ортого- нальность. Каждая ϕ n−1,j ортогональна каждой ϕ n−1,k так же как и всем ψ n−1,j и анагично каждый вейвлет ψ n−1,j ортогонален дру- гим вейвлетам ψ n−1,k и всем масштабирующим функциям ϕ n−1,j Так же, каждая ϕ n−1,j и каждый ψ n−1,j являются нормирован- ными [2]. Следуя, из выше изложенного получим: 1 ∫ 0 f (t) ϕ n−1,j (t) dt = a n−1,j (4) В силу ортогональности правой части остается только один член, а нормирование приводит к отсутствию коэффициента при a n−1,j . Теперь, подставив правую часть равенства, получим: a n−1,0 = x 1 + x 2 √ 2 (5) 36 ISSN 1560-8956 Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) Квадратный корень в коэффициенте появляется за счет нор- мирования. В случае использования ненормированных бази- сных функции результатом будет двухточечное среднее значение. Остальные коэффициенты a n−1,j j = 1, . . . , 2 n − 1 вычисляются аналогично. Таким образом: x 2j+1 + x 2j+2 √ 2 , ; j = 1, . . . , 2 n−1 − 1 (6) Аналогично, используя свойства ортогональности и нормирован- ности функций ψ n−1,j можно вычислить коэффициенты d n−1,j по следующей формуле: d n−1,j = x 2j+1 − x 2j+2 √ 2 , j = 1, . . . , 2 n−1 − 1 (7) Уравнения можно представить в виде одного матричного урав- нения. Введем векторную запись x, a и d. Тогда можно представить это как выражение A n D n x = a n−1 d n−1 (8) Матрица в левой части – это единая матрица 2 n × 2 n , а вектор в правой части – единый вектор-столбец 2 n ×1. На каждом шаге про- цесса вейвлет-преобразования сохраняются детализирующие ко- эффициенты и обрабатываются коэффициенты усреднения. В рас- сматриваемом случае вейвлет преобразование будет иметь 2 n ком- понентов. Половину из них мы получаем из уравнения в каче- стве детализирующих коэффициентов в d n−1 . Сохраняем эти ко- эффициенты как половину вейвлет-преобразования. Следующий шаг вейвлет-преобразования состоит в применении к a n−1 опера- ций усреднения и вычитания на следующем, более низком, уровне разрешения: A n−1 D n−1 a n−1 = a n−2 d n−2 (9) Здесь A n−1 и D n−1 – это 2 n−1 × 2 n матрицы, а a n−2 и d n−2 – это векторы-столбцы размерности 2 n−2 . Чтобы построить часть вейвлет-преобразования, мы сохраним d n−2 вместе с d n−1 . Далее процесс стоит в последующем применении операций усреднения и вычитания к a k сохраняя полученные детализирующие коэффи- циенты как часть вейвлет-преобразования. На заключительном шаге сохраняется среднее значение a 0 , которое является одноком- понентным вектором с единственным элементом a 0,0 . Результи- рующее вейвлет-преобразование, которое можно представить как единый вектор-столбец с 1 + 1 + 2 + . . . + 2 n−1 = 2 n элементами, будет иметь вид: ISSN 1560-8956 37 Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) a 0 d 0 d 1 d n−1 (10) Постановка задачи Форматы изображений, которые сжатые вейвлетным методом занимают меньшей объем физической памяти на диске, что позво- ляет снизить время их загрузки. Однако, в большинстве случаев, они не поддерживаются современными браузерами. Чтобы исполь- зовать такие изображения в веб-приложениях мы можем восполь- зоваться специализированным для графики тегом canvas. Так же, для сжатия изображения и для его обратного преобразования мо- дифицируем метод вейвлетного сжатия. Для сжатия изображения для веб-приложений коэффициенты преобразования будут иметь вид: a i,j = x 8j+i + x 8j+(i+4) √ 2 , j = 1, . . . , 2 n−1 − 1, i = 0..3 (11) d i,j = x 8j+1 − x 8j+(i+4) √ 2 , j = 1, . . . , 2 n−1 − 1, i − 0..3 (12) Сохранение только одного среднего значения a 0 позволило бы нам преобразовывать только изображения с градацией серого, представляя его в виде средней яркости каждого пикселя. В дан- ной модификации сохраняются значения пикселя в системе RGBA, что позволит нам использовать не только полную цветность изо- бражения, но так же, и прозрачность его пикселей. Так же, исходя из формата хранимых в теге canvas данных, мы можем упростить метод до одномерного случая, в результате чего мы должны получить матрицу следующего вида: a 0 a 1 a 2 a 3 d 0,0 d 1.0 d 2,0 d 3,0 d 0,n−1 d 1,n−1 d 2,n−1 d 3,n−1 (13) Применение модифицированного метода сжатия На последнем шаге вейвлет преобразования можно провести процедуру выбора значимых коэффициентов разности. Значение отличия цветности некоторых соседних пикселей настолько мало, что его можно приравнять к 0. Определяя процент запоминания 38 ISSN 1560-8956 Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) наибольших коэффициентов разности, можно существенно умень- шить размер файла, но так же уменьшив его качество. На рисунке 1 приведены изображения с 5%, 10% и 50% сохранением коэффи- циентов. Рис. 1 – Изображения сжатые вейвлетным методом с сохранением коэффициентов 5%, 10% и 50% Как видим, изображение с сохранением 5% коэффициентов отличается от 10% существенной нечеткостью. Однако 10% мало чем отличается от 50%, что доказывает то, что мы можем отбра- сывать большое количество несущественных данных не теряя при это качество изображения. На таблице 1 приведены размеры одинакового изображения ра- зных форматов распространенных форматов. Таблица 1 Сравнение размера разных форматов изображений Формат изобра- жения bmp jpeg png 5% 10% 50% Размер файла 387Kb 121Kb 233Kb 2 Kb 7,4 Kb 63,6 Kb ISSN 1560-8956 39 Мiжвiдомчий науково-технiчний збiрник «Адаптивнi системи автоматичного управлiння», 2013, № 2(23) Исходным форматом для конвертирования был выбран фор- мат bmp, так как он хранит информацию о пикселях изображе- ния в виде простого двухмерного массива и поэтому занимает боль- ше всего памяти на диске. Как видно из таблицы, формат png плохо подходит для выбранного типа изображения. Наилучшим решением помимо вейвлет преобразования является формат jpeg, с относительно небольшим размером файла и отсутствием иска- жений и потери качества. Вейвлет преобразование с сохранением 50% коэффициентов для выбранного типа изображения позволя- ет уменьшить его размер по сравнению с форматом jpeg на 47% при относительно небольшой потере качества. Что позволяет уве- личить скорость его загрузки в веб-приложение вдвое. Выводы Была рассмотрена методика повышения быстродействия веб- приложений путем сжатия файлов изображений. Задача сжатия решена с помощью модификации метода вейвлет-преобразования изображений в системе RGBA с сохранением 50% разностных ко- эффициентов. В результате экспериментального исследования по- казано, что применение данного метода позволяет уменьшить ра- змер файла изображения минимум на 47% в сравнении с осталь- ными распространенными форматами изображений и увеличить скорость его загрузки в веб-приложениях. Библиографический список 1. Яковлев А.Н. Введение в вейвлет-преобразовани. / А.Н. Яков- лев. — Новосибирск: НГТУ, 2003. – 104 с. 2. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии: пер. с англ. / С. Уэлстид.— М.:Триумф, 2003. —319 с. Отримано 15.10.2013 р. 40 ISSN 1560-8956 |