Підвищення ефективності стиснення кольорових зображень у форматі PNG
Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Підвищення ефективності стиснення кольорових зображень у форматі PNG
Rise of efficiency of compression of coloured images in the PNG format Повышение эффективности сжатия цветных изображений в формате PNG. |
|
| Creator |
Шпортько, О.В.
|
|
| Subject |
кольорове зображення
стиснення без втрат графічний формат PNG методи попередньої обробки зображень цветное изображение сжатие без потерь графический формат PNG методы предварительной обработки изображений color image compression without losses graphic PNG format methods of the previous processing of images |
|
| Description |
The thesis is to devoted the question of rising the efficiency of compression without losses in the graphic formats (the PNG format as an example) of rasters, which use predictors, dictionary algorithm LZ77, context-independent coding and their combinations by means of improving and taking into consideration of the interaction of them and application of alternative or new methods and code algorithms. The method of searching of consilient sequences of the flow of data by choosing the shortest hash-chains and the method of exact computation of sizes of blocks of dynamic codes of HUFF has been improved for accelerating of coding in the PNG format. For diminishing of coefficient of compression in the ratified standard PNG format on the average of more than 3.9 % for the first time the postprocess method of reduction of size of the compressed block in the format of DEFLATE and method of previous analysis of images by breaking up into minimum and homogeneous blocks of lines have been realized. As for bringing of modifications in this format methods for the generation of the differential coloured models with the whole as well as real coefficients have been elaborated. The structure of curriculum of algorithm of LZ77 has been improved and a palette for group statistical coding which enabled to decrease coefficient of compression for more than 12 % in the case of compatible realization with the algorithm of correction of values of predictors.Диссертация посвящена вопросу повышения эффективности сжатия цветных изображений без потерь в растровых графических форматах (на примере формата PNG), использующих предикторы, словарный алгоритм LZ77, контекстно-независимое кодирование и их комбинации с помощью совершенствования и учета взаимодействия этих и применения альтернативных или новых методов и алгоритмов кодирования. В работе показано, что для повышения эффективности сжатия данных в форматах, последовательно использующих алгоритмы нескольких методов (как в формате PNG), целесообразно учитывать взаимовлияние этих алгоритмов, а во время предварительной обработки данных перед сжатием в таких форматах для расчета параметров компрессии рационально учесть все виды избыточностей, обрабатываемых их отдельными алгоритмами, а также разбивать данные на однородные блоки. Исследование проведено в трех направлениях: ускорение кодирования, уменьшения коэффициента сжатия (КС) в утвержденном стандарте формата PNG и внесение модификаций в этот формат. В направлении ускорения кодирования в формате PNG усовершенствованы метод поиска совпадающих последовательностей потока данных для формирования разложения алгоритма LZ77 путем выбора кратчайших хеш-цепей, что дало возможность, например, убыстрить формирование этого разложения для случая анализа всех элементов таких цепей в более чем 13 раз, и метод точного расчета размеров блоков динамических кодов HUFF без их предварительной генерации, ускоряющий выполнение этих вычислений более, чем на 80 %. Для уменьшения КС в утвержденном стандарте формата PNG, во-первых, предложен и реализован послепроцесный метод уменьшения размера сжатого блока в формате DEFLATE с помощью: расчета распределения частот для определения размеров альтернативных сжатых блоков без их предварительной генерации; выбора кратчайшего блока из альтернативных; итеративного отбрасывания неэффективных замен в кратчайшем сжатом блоке с последующим его формированием. Во-вторых, усовершенствован механизм формирования "ленивого" и почти оптимального разложения алгоритма LZ77 путем использования результатов предварительного анализа изображений. В-третьих, проведен анализ эффективности сжатия в случае применения разнообразных предикторов, существующих и разработанных энтропийных и эмпирических способов выбора предикторов для отдельных строк, различных способов кодирования для разнотипных изображений, по результатах которого выделено пять вариантов компрессии, каждый из которых может оказаться оптимальным для очередного блока строк: без использования предикторов, с применением LeftPredict, с использованием RightPredict, с применением непосредственного энтропийного способа выбора предикторов и с использованием энтропийного способа выбора предикторов после применения коротких замен алгоритма LZ77. В-четвертых, впервые разработан метод предварительного анализа изображений с разбиением на минимальные и однородные блоки строк с целью определения для каждого из них оптимального варианта компрессии (из пяти указанных выше) с помощью метода динамического программирования. Указанные методы и алгоритмы применены в разработанной утилите MinPNG, которая хотя и кодирует медленнее относительно быстрых вариантов сжатия в формате PNG в более чем 4.5 раза, но уменьшает КС в среднем на более чем 3.9 % и достигает по этому показателю наименьших значений среди программного обеспечения, сжимающего изображения в этом формате. В направлении внесения модификаций в формат PNG, во-первых, разработан ряд методов для генерирования разностных цветовых моделей как с целыми, так и с действительными коэффициентами, выполняющих замены максимум двух из трех компонентов цветовой модели разностями с другими компонентами так, чтобы максимально уменьшить энтропию после использования предикторов. Применение таких разностных цветовых моделей целесообразно в форматах без потерь, использующих предикторы и контекстно-независимое кодирование и не выполняющих межкомпонентную декорреляцию. Во-вторых, усовершенствована структура разложения алгоритма LZ77 для обеспечения возможности использования нескольких скользящих окон и формирования литералов с наименьшей энтропией. В процессе формирования разложения с усовершенствованной структурой кодирование выполняется по альтернативному словарю, содержащему самую длинную совпадающую последовательность, или по словарю с наименьшей энтропией, если совпадающие последовательности во всех альтернативных скользящих окнах отсутствуют. В-третьих, получил последующее развитие метод группового статистического кодирования с помощью использования палитры в процессе сжатия изображений без потерь, который представляет значение цвета каждого пиксела в виде индекса в палитре параллелепипеда, которому он принадлежит, и смещения по каждой координате в средине этого параллелепипеда. Групповое статистическое кодирование дает возможность достичь лучших КС по сравнению с результатами кодирования HUFF за счет уменьшения избыточной индексации цветов. Методы и алгоритмы этого направления исследования совместно с алгоритмом коррекции значений предиктора реализованы в комплексе программ ModifyPNG, применение которого в среднем уменьшает КС на более чем 12 % и достигает по этому показателю в среднем наименьших на сегодня значений в сравнении с другими подобными программами.Дисертація присвячена питанню підвищення ефективності стиснення без втрат у растрових графічних форматах (на прикладі формату PNG), що використовують предиктори, словниковий алгоритм LZ77, контекстно-незалежне кодування та їх комбінації за допомогою вдосконалення і врахування взаємодії цих та застосування альтернативних чи нових методів і алгоритмів кодування. У напрямку прискорення кодування у форматі PNG вдосконалено метод пошуку однакових послідовностей потоку даних шляхом вибору найкоротших хеш-ланцюгів та метод точного розрахунку розмірів блоків динамічних кодів HUFF. Для зменшення коефіцієнтів стиснення у затвердженому стандарті формату PNG у середньому на понад 3.9 % вперше реалізовано післяпроцесний метод скорочення розміру стиснутого блоку у форматі DEFLATE і метод попереднього аналізу зображень з розбиттям на мінімальні та однорідні блоки рядків. У напрямку внесення модифікацій у цей формат розроблено методи для генерування різницевих кольорових моделей як з цілими, так і з дійсними коефіцієнтами, вдосконалено структуру розкладу алгоритму LZ77 та використано палітру для групового статистичного кодування, що дало змогу у випадку їх сумісної реалізації з алгоритмом коригування значень предиктора в середньому зменшити коефіцієнт стиснення більше, ніж на 12 %. |
|
| Date |
2011-11-08T09:29:45Z
2011-11-08T09:29:45Z 2011 |
|
| Type |
Autoreferat
|
|
| Identifier |
Шпортько, О. В. Підвищення ефективності стиснення кольорових зображень у форматі PNG : автореферат дисертації кандидата технічних наук : 01.05.03 / О. В. Шпортько ; Національний університет "Львівівська політехніка". - Львів, 2011. - 20 с.
http://ena.lp.edu.ua:8080/handle/ntb/10509 |
|
| Language |
ua
|
|
| Publisher |
Національний університет "Львівська політехніка"
|
|