9. Шпортько О. В. Оптимізація блоків стиснутих даних у графічному форматі PNG / О. В. Шпортько // Вісник Національного університету "Львівська політехніка" : Інформаційні системи та мережі. - 2009. - № 653. - С. 223-231.

10. Шпортько О. В. Стиснення RGB-зображень без втрат із використанням палітри / О. В. Шпортько // Системні дослідження та інформаційні технології. - 2010. - № 2. - С. 26-36.

11. Бомба А. Я. Алгоритм оптимізації вибору фільтра для попереднього опрацювання зображень перед стисненням на основі методу "предиктор - коректор" / А. Я. Бомба, О. В. Шпортько // Вісник Національного університету "Львівська політехніка" : Інформаційні системи та мережі. - 2008. - № 621. - С. 46-54.

12. Шпортько О. В. Алгоритми оптимізації розкладу LZ77 та вибору розмірів блоків динамічних кодів Хафмана для стиснення даних у форматі DEFLATE / О. В. Шпортько // Волинський математичний вісник. Зб. наукових праць. Рівне : РДГУ, 2008. - № 5 (14). - С. 297-311. - (Серія: Прикладна математика).

13. Рішення про реєстрацію авторського права на твір "Комп'ютерна програма "AnalisysForPNG" / О. В. Шпортько. - № 35819; заявл. 13.09.2010.

14. Рішення про реєстрацію авторського права на твір "Комп'ютерна програма "UsingDCM" / О. В. Шпортько. - № 35820; заявл. 13.09.2010.

15. Бомба А. Я. Комплексне застосування модифікацій формату PNG / А. Я. Бомба, О. В. Шпортько // Обчислювальні методи і системи перетворення інформації : Зб. праць наук.-техн. конф. - Львів : ФМІ НАН України, 2010. - С. 151-154.

16. Шпортько О. В. Використання альтернативних блоків стиснутих даних у форматі PNG / О. В. Шпортько // Комп'ютерні науки та інформаційні технології : Матеріали Третьої міжнародної конференції CSIT'2008. - Львів : Видавництво ПП "Вежа і Ко", 2008. - С. 149-153.

17. Шпортько О. В. Вибір найкоротших хеш-ланцюгів в процесі пошуку співпадаючих послідовностей у декількох словниках / О. В. Шпортько // Комп'ютерні науки та інформаційні технології : Матеріали 4-ї Міжнародної конференції CSIT'2009. - Львів : Видавництво ПП "Вежа і Ко", 2009. - С. 220-224.

18. Шпортько О. В. Стиснення RGB-зображень без втрат з використанням палітри : Тези доп. / О. В. Шпортько // Системний аналіз та інформаційні технології : Матеріали X Міжнародної науково-технічної конференції. - К. : НТУУ "КПІ", 2008. - С. 424.

19. Шпортько О. В. Застосування різницевих кольорових моделей та корегувань значень предикторів в процесі стиснення RGB-зображень без втрат : Тези доп. / О. В. Шпортько // Системний аналіз та інформаційні технології : Матеріали XII Міжнародної науково-технічної конференції. - К. : УНК "ІПСА" НТУУ "КПІ", 2010. - С. 506.

20. Шпортько О. В. Використання арифметичного кодування у форматі PNG : Тези доп. / О. В. Шпортько // Системний аналіз та інформаційні технології : Матеріали XI Міжнародної науково-технічної конференції. - К. : УНК "ІПСА" НТУУ "КПІ", 2009. - С. 598.

Анотації

Шпортько О. В. Підвищення ефективності стиснення кольорових зображень у форматі PNG. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 математичне та програмне забезпечення обчислювальних машин і систем. - Національний університет “Львівська політехніка”, Львів, 2011.

Дисертація присвячена питанню підвищення ефективності стиснення без втрат у растрових графічних форматах (на прикладі формату PNG), що використовують предиктори, словниковий алгоритм LZ77, контекстно-незалежне кодування та їх комбінації за допомогою вдосконалення і врахування взаємодії цих та застосування альтернативних чи нових методів і алгоритмів кодування. У напрямку прискорення кодування у форматі PNG вдосконалено метод пошуку однакових послідовностей потоку даних шляхом вибору найкоротших хеш-ланцюгів та метод точного розрахунку розмірів блоків динамічних кодів HUFF. Для зменшення коефіцієнтів стиснення у затвердженому стандарті формату PNG у середньому на понад 3.9 % вперше реалізовано післяпроцесний метод скорочення розміру стиснутого блоку у форматі DEFLATE і метод попереднього аналізу зображень з розбиттям на мінімальні та однорідні блоки рядків. У напрямку внесення модифікацій у цей формат розроблено методи для генерування різницевих кольорових моделей як з цілими, так і з дійсними коефіцієнтами, вдосконалено структуру розкладу алгоритму LZ77 та використано палітру для групового статистичного кодування, що дало змогу у випадку їх сумісної реалізації з алгоритмом коригування значень предиктора в середньому зменшити коефіцієнт стиснення більше, ніж на 12 %.

Ключові слова: кольорове зображення, стиснення без втрат, графічний формат PNG, методи попередньої обробки зображень.

Шпортько А. В. Повышение эффективности сжатия цветных изображений в формате PNG. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 математическое и программное обеспечение вычислительных машин и систем. - Национальный университет “Львовская политехника”, Львов, 2011.

Диссертация посвящена вопросу повышения эффективности сжатия цветных изображений без потерь в растровых графических форматах (на примере формата 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, методы предварительной обработки изображений.

Shportko A. V. Rise of efficiency of compression of coloured images in the PNG format. Manuscript.

Thesis for a candidate's degree in technical sciences by speciality 01.05.03 mathematical and software support of computer machines and systems. - Lviv Politechnic National University, Lviv, 2011.

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.

Keywords: color image, compression without losses, graphic PNG format, methods of the previous processing of images.

Размещено на Allbest.ru