Содержание к диссертации
Введение
1 Анализ способов и подходов к сжатию цифровых изображений 11
1.1. Способы представления цифровых изображений 11
1.2. Классификация методов сжатия цифровых изображений. Описание и анализ основных широко используемых методов сжатия 14
1.2.1 .Статистическое (энтропийное) кодирование 16
1.2.2. Кодирование одинаковых последовательностей (LZ-подобные алгоритмы, LZW) 19
1.2.3.Кодирование на основе преобразования: алгоритмы JPEG и JPEG2000 20
1.3. Анализ подходов к оценке потерь качества при восстановлении изображе
ний 27
1 ААнализ подходов к оценке эффективности методов сжатия " 29
1.5.Анализ программных средств повышения эффективности применения методов сжатия цифровых изображений 32
1.6.Постановка задач на исследование 35
Выводы 38
2. Разработка математических моделей растровых изображений 40
2.1. Разработка алгебраической модели оценки растровых изображений .40
2.2.Разработка математической модели многорядной селекции и оценки рас
тровых изображений 47
Выводы 65
3 Разработка методики оценки эффективности и выбора метода сжатия 67
3.1 . Разработка алгоритма комплексного анализа признаков изображения 67
3.2.Алгоритм моделирования изображений на основе многорядной селекции с исключением незначимых элементов 89
3.3.Алгоритм оценки эффективности и выбора метода сжатия 94
ЗАВыводы 97
4. Экспериментальное исследование моделей и алгоритмов эффективного сжатия растровых изображений 99
4.1. Автоматизированная система исследования методов и параметров сжатия 99
4.1.1 .Структура автоматизированной системы 99
4.1.2.Разработка подсистемы сбора экспериментальных данных 103
4.1.3.Разработка подсистемы моделирования 105
4.2.Исследование эффекта от применения процедуры исключения незначимых элементов в математической модели многорядной селекции 107 4.3.Анализ многорядных моделей, получаемых на различных
наборах данных 108
4.4. Автоматизация формирования электронных архивов в автоматизирован ной системе технологической подготовки производства 119
Выводы 125
Заключение 127
Литература
- Способы представления цифровых изображений
- Кодирование одинаковых последовательностей (LZ-подобные алгоритмы, LZW)
- Разработка алгебраической модели оценки растровых изображений
- Разработка алгоритма комплексного анализа признаков изображения
Введение к работе
Актуальность темы. Выпуск новой техники и освоение новых технологий, расширение и обновление ассортимента изделий, автоматизация проектно-конструкторских работ требует обработки значительного объема изображений в различных автоматизированных системах предприятий.
Наличие многочисленных методов и способов сжатия, необходимость передачи изображений в корпоративных сетях и их хранение в электронных архивах предприятий приводит к необходимости рационального использования ресурсов. Очевиден тот факт, что эффективность методов и способов сжатия в значительной степени зависит от структуры самого изображения. Сейчас эту проблему решают интуитивно, что не всегда является эффективным, как с точки зрения хранимых в архивах объёмов информации, так и объёмов информации, передаваемых по корпоративным сетям предприятий.
Таким образом, задача выбора эффективного метода сжатия на основе проведения научных исследований в автоматизированных системах предприятий различного типа (САПР, АСТПП, АСУП, АСУ I'll) в зависимости от параметров хранимой и передаваемой информации, а также эффективности 'метода для конкретного изображения является актуальной.
Анализ ретроспективы предметной области показывает, что исследованию вопросов эффективного сжатия изображений посвящено большое количество работ. Теоретические основы методов сжатия исследовались зарубежными учёными Барнсли М., Макхоулом Дж., Прэттом У. Проблемы применения высокоэффективных методов сжатия в телекоммуникационных системах решались Ланнэ А.А., Дворковичем В. П., Зубаревым Ю.Б., Харатишвили Н.Г., Устиновым А.А.
Оценки коэффициента сжатия для некоторых методов сжатия цифровых изображений были ранее получены В.М. Ефимовым, А.Н. Колесниковым, Ю.Н. Золотухиным, Н.П. Коршуновой.
Исследованию сжатия изображений посвящены работы Л.Е. Назаро-
5 ва и З.Т. Назаровой, в которых были рассмотрены нейросетевые методы сжатия. В основу их оценок было положено приближенное вычисление объема сжатых данных, при этом в оценках фигурируют параметры методов и не учитываются характеристики изображения.
В существующих академических изданиях и специальных трудах имеются достаточные научные предпосылки для решения поставленной задачи. Между тем до настоящего времени существующие подходы к решению задачи выбора метода и параметров сжатия носят, как правило, локальный по областям и разрозненный по методам характер.
В различных автоматизированных системах предприятий наибольшее применение при цифровом- отображении чертежей, графиков, схем нашли растровые изображения, что обусловило выбор объекта, предмета и цели исследования.
Объектом исследования являются автоматизированные системы научных исследований методов сжатия цифровых изображений.
Предметом исследования являются методы и алгоритмы сжатия растровых изображений.
Цель исследования. Увеличение коэффициента сжатия для растровых изображений.
Для достижения сформулированной цели были поставлены и решены следующие задачи:
1.Анализ существующих подходов к сокращению объема данных при хранении цифровых изображений.
2.Анализ существующих моделей изображения и методов сжатия, а также подходов к оценке их эффективности.
3.Анализ гистограммных характеристик изображения первого и второго порядка, и оценка их влияния на коэффициент сжатия.
4.Разработка способов и приёмов выбора метода и параметров сжатия изображения.
Методы исследования. В качестве основного инструмента теоретического исследования использовались методы системного анализа, линейной алгебры, теории вероятностей и математической статистики, теории информации, методы самоорганизации моделей сложных систем.
Научная новизна диссертационного исследования заключается в том, что получены новые научные результаты:
Алгебраическая модель оценки растровых изображений, базирующаяся на теории стационарного поля, отличающаяся комплексным использованием гистограммных признаков первого и второго порядка.
Математическая модель многорядной селекции и оценки растровых изображений, базирующаяся на методе группового учёта аргументов, отличающемся процедурой исключения незначимых элементов и позволяющей' снизить их влияние.
3.Методика оценки эффективности и выбора метода сжатия изображений, включающая разработанные модели и позволяющая оценить качество сжатия на основе измеренных признаков и самого декодированного изображения.
4. Автоматизированная система исследования методов и параметров сжатия, обеспечивающая моделирование, визуальную оценку качества изображения и научно обоснованный выбор метода сжатия.
Практическая значимость заключается в применении математических моделей и методики выбора метода и параметров сжатия в автоматизированной системе.
В частности, полученные результаты использованы:
для определения направления конструктивного решения по построению специализированного аппаратно-программного комплекса в ОКР «ГИАЦ-3 комплекс» ФГУ НИИ «Энергия» (г. Ступино);
при проведении исследований модульных систем сбора и обработки информации в НИОКР «Комплекс-МК» ОАО «ЭЛВИС-ПЛЮС»;
в ОКР «Oca-DECT» Краснодарского филиала ФГУП НТЦ «Атлас»
7 при разработке математического и программного обеспечения модульных структур систем сбора и обработки данных в специализированных автоматизированных системах управления (АСУ).
Результаты внедрения подтверждены соответствующими актами.
Достоверность и обоснованность научных положений, результатов, выводов и рекомендаций, приведенных в диссертационной работе, достигнута: за счет корректного применения методов математического и функционального анализа, теории вероятностей и математической статистики, теории случайных процессов; непротиворечивости и воспроизводимости результатов, полученных теоретическим путем; сочетания формальных и неформальных методов исследования; использования методов, адекватных природе изучавшихся процессов и явлений; верификации отдельных результатов в рамках известных теоретических конструкций, широко используемых в теории сложных технических систем.
Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях:
Ш-й Всероссийской научно-технической конференции «Информационные системы и модели в научных исследованиях, промышленности и, экологии» (г. Тула, 2005);
V-ой региональной научно-практической конференции «Современные проблемы экологии и рационального природопользования в Тульской области» (г. Тула, 2006);
Х1-ой конференции преподавателей и аспирантов ОрелГТУ «Неделя науки» (г. Орел, 2006);
II Международной научно-практической конференции «Информационные технологии в науке, образовании и производстве (ИТНОП)» (г. Орел, 2006).
Публикации. По результатам исследований опубликовано- 10 работ, в том числе, 3 статьи в журналах, входящих в перечень ВАК РФ, 7 статей в< журналах и материалах конференций.
8 Положения, выносимые на защиту:
Алгебраическая модель оценки растровых изображений.
Математическая модель многорядной селекции и оценки растровых изображений на основе метода группового учёта аргументов.
Методика выбора метода и параметров сжатия изображений.
Автоматизированная система исследования методов и параметров сжатия изображений.
Структура и объем работы. Диссертационная работа изложена на 144 страницах и состоит из введения, четырех глав, заключения и 1 приложения. Библиографический список включает в себя 105 наименований. Работа содержит 26 рисунков и 14 таблиц.
В первой главе проведён анализ методов сжатия цифровых изображений, представлена их классификация, способы и подходы к оценке эффективности методов кодирования растровой графики.
Программные средства для оптимизации графических файлов* позволяют выбрать для конкретного изображения метод сжатия для- получения минимального объёма данных при сохранении приемлемого качества. Данные инструментальные средства чаще всего используют форматы JPEG, GIF и PNG. Большинство инструментальных средств данного класса позволяют организовать пакетное кодирование цифровых изображений.
При использовании алгоритма JPEG возможно выделение областей, не содержащих деталей, что обеспечивает дополнительные возможности по сжатию изображений. При этом целесообразна качественная оценка восстановленных изображений со стороны пользователя.
Указанные особенности определяют необходимость гибких подходов к оценке параметров сжатия.
В главе рассмотрены способы преобразования цифровых изображений и сделан вывод о целесообразности комплексного использования признаков изображения.
Во второй главе приводятся разработанные теоретические положения
моделирования изображений.
Выделены признаки, определяющие коэффициент и параметры сжатия. Разработана алгебраическая модель на основании гистограммных признаков первого и второго порядка. Приведена математическая модель многорядной селекции и оценки растровых изображений для описания неодно-родностей изображения. Описана предлагаемая процедура исключения статистически незначимых элементов частных квадратичных моделей на основе анализа коэффициента множественной детерминации при использовании метода группового учета аргументов.
В третьей главе представлено описание методики оценки эффективности и выбора метода сжатия. Для каждого этапа методики разра-ботаны алгоритмы.
В исследовании для каждой конкретной модели определены вычислительные затраты при ее применении и, произведено сопоставление их с вычислительными затратами на сжатие изображений.
Это позволяет оценить целесообразность использования оценивающих моделей изображения для повышения эффективности применения методов сжатия.
В четвертой главе представлено экспериментальное исследование предложенных моделей изображения и алгоритмов, и основные результаты их внедрения.
Разработана автоматизированная система исследования методов и параметров сжатия, позволяющая осуществлять синтез многорядных моделей и интегрировать ее в различные системы обработки, хранения и передачи цифровых изображений.
Разработанная автоматизированная система обеспечивает свободный доступ к созданной информации и возможность организации взаимодействия с другими функционирующими на предприятии системами (например, с автоматизированной системой технологической подготовки производства).
Экспериментальные исследования показали, что использование разра-
10 ботанных алгоритмов позволило увеличить коэффициент сжатия для 16-битных растровых изображений на 10-15 %, для 32-битных - на 20-22%.
Сокращение объема хранимой и передаваемой информации является исключительно актуальным при ведении состава изделия, получении полного комплекта конструкторской документации, управлении процессом конструкторской подготовки производства и защищенном хранении конструкторско-технологической документации.
В заключении перечисляются основные результаты диссертационной работы и формулируются выводы.
В приложении 1 помещены акты внедрения результатов диссертационной работы.
Способы представления цифровых изображений
При формальном описании растрового изображения используют два представления [47, 70]: детерминированное и статистическое. При детерминированном представлении растровое изображение есть двумерный массив отсчетов А размерами N pcNy, Отсчет а(х, у), где 0 x Nx,0 y Ny, - называют также пикселем. Для анализа часто переходят к вектору А, выстраивая в цепочку строки или, реже, колонки массива. Достоинства вектора: компактность обозначений и возможность использования методов, применяемых для обработки одномерных сигналов. Значением отсчета при описании черно-белого изображения будет либо 0 (черный цвет), либо 1 (белый цвет), при описании полутонового монохромного (в градациях серого) - значение яркости, при описании цветного изображения - вектор значений компонент в,используемой системе представления цветности. Наиболее распространенными системами представления цветности являются красно-сине-зеленая координатная система (RGB), где компоненты соответствуют основным хроматическим составляющим красной (R), зеленой (G) и синей (В), и координатная система YCrCb, где Y - соответствует яркости, Сг - хроматическому красному, СЪ - хроматическому синему.
Если количество цветов не превышает 256, при сохранении данных используют цветовую таблицу, или палитру, содержащую используемые в изображении цвета. Тогда значением пикселя является индекс в палитре, для хранения которого достаточно одного байта. Такой переход позволяет без применения методов сжатия сократить объем хранимых в- файле данных в 3 раза без учета затрат на хранение палитры. Коэффициент сжатия определяется следующим выражением у- 3N N (1.1) NSNV+C 3 где С - количество цветов в палитре.
Использование палитры размером больше 256 становится просто не выгодно, так как на кодирование индекса потребуется уже два байта.
Детерминированное представление изображений используется для их обработки как дискретного двумерного сигнала. Использование детерминированного представления изображения при его моделировании с целью получения оценок максимально возможных коэффициентов и параметров сжатия делает эту задачу астрономически сложной.
При статистическом представлении изображение считают реализацией случайного процесса. Случайный процесс описывается моментами и совместной плотностью вероятности [58]. Используются моменты первого и второго порядка.
Совместные плотности вероятности высокого порядка для изображений обычно неизвестны, и их в общем случае трудно моделировать. Для плотности вероятности первого порядка удается удачно подобрать модель из физических соображений или на основе измеренных гистограмм. Распределение относительных частот используется как оценка одномерного распределения вероятностей, т.е. P(A)=N(A)/N, (1.13) где N(A) - количество изображений A, N- количество изображений в ансамбле.
Усредненные значения по ансамблю равны усредненным по пространственным координатам для эргодичных источников. В качестве оценки распределения также используются относительные частоты: Р(Ъ) = Fr{a{x,y) = b}=N(b)/N, (1.14) где N(b) - количество пикселей, для которых а(х, у) = b; N-— общее количе 14 ство пикселей.
Статистическое представление используется для моделирования коэффициентов преобразования, яркости и разностных сигналов в задачах определения параметров фильтрации. Оно может быть использовано и для оценки максимально возможного коэффициента сжатия для конкретного метода, но из-за большого количества допущений дает лишь общее представление об изображении, которого недостаточно, так как именно те особенности изображения, которые оно не учитывает, оказывают существенное влияние на максимально возможный коэффициент сжатия и параметры.
Классификацию методов сжатия растровых изображений обычно осуществляют по двум признакам: способ обработки элементов изображения при кодировании [53, 67] и точность восстановления информации [10, 6].
По способу обработки элементов растрового изображения выделяют методы кодирования с поэлементной обработкой и методы кодирования с пространственной обработкой. К методам кодирования с поэлементной обработкой относятся: импульсно-кодовая модуляция (ИКМ) [55, 68], кодирование серий [50, 67], статистическое кодирование [45, 69, 83], кодирование с предсказанием [74, 90, 82], кодирование последовательности одинаковых символов (LZ-подобные алгоритмы) [42, 94, 98, 99]. В этих методах каждый пиксель кодируется отдельно. К методам кодирования с пространственной обработкой относятся: интерполяционное кодирование [16, 56], кодирование с преобразованием [51, 61, 62, 63, 66, 73, 92, 97, 98], векторное кодирование (квантование)[12,77, 79, 80, 89], итеративное фрактальное кодирование [4, 7, 9, 84, 94]. В этих методах кодируется группа пикселей.
Кодирование одинаковых последовательностей (LZ-подобные алгоритмы, LZW)
Сжатие во всех LZ-подобных алгоритмах осуществляется на основе кодирования одинаковых цепочек байт. Они различаются методом поиска повторяющихся цепочек, способом их представления, способом построения-словаря цепочек. Лучшим из всех LZ-подобных алгоритмов признан алгоритм LZW с динамически создающимся во время кодирования и декодирования словарем и переменным числом битов в кодах цепочек. Эти методы.были разработан Лемпелем А., Зивом Дж. и Уэлчом Т. А. [96, 100, 101], по первым буквам фамилий которых они и получили свое название. Описание и анализ этих алгоритмов даны в статьях [44, 45]. Для представления и хранения цепочек метод LZW использует дерево. Это накладывает сильное ограничение на вид цепочек, и далее не все одинаковые подцепочки в изображении будут использованы при сжатии. Однако в этом алгоритме выгодно сжимать даже цепочки, состоящие из двух байт. Преимуществом LZW является также и то, что для декомпрессии не нужно сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что сам восстанавливает таблицу строк, пользуясь только потоком кодов. Степень компрессии дополнительно увеличивается за счет упаковки кодов переменной длины. LZW реализован в форматах GIF и TIFF [33, 46]. Для дальнейших исследований целесообразно взять GIF, так как он имеет более простую структуру файла и содержит меньшее количество дополнительных данных. Максимальный- коэффициент сжатия достигается на картинках с однородным фоном размером около 7Мб и составляет 1000. Средний коэффициент сжатия -15, худший 5/7. Ориентирован алгоритм LZW на 8-битные изображения, полученные на компьютере. Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко.
Кодирование, на основе преобразования является косвенным методом: Изображение подвергается математическому преобразованию с целью декор-релировать отсчеты изображения и получить как можно большее количество незначимых (равных нулю) коэффициентов. Полученные в результате коэффициенты преобразования квантуются и кодируются. Общая схема кодирования на основе преобразования приведена на рис. 1.1.
Анализ кодирования изображений посредством унитарного преобразования дан в [61]. При использовании унитарных преобразований изображение разбивается на небольшие блоки, к которым применяется преобразование, полученные коэффициенты преобразования (трансформанты) квантуются и кодируются. Эффект сжатия заключается в том, что в результате таких унитарных преобразований, как Фурье, Адамара, Карунена-Лоэва, Хаара, значения многих коэффициентов преобразования сравнительно,малы. Незначимые коэффициенты можно отбросить или отвести на их кодирование малое число двоичных разрядов без риска сколько-нибудь значительных искажений. Существует два способа отбора коэффициентов [62]: зональный и пороговый.
При зональном отборе выбирается зона в матрице спектральных коэффициентов, в которой концентрируется максимальная энергия. Коэффициенты, входящие в эту зону кодируются, а остальные просто отбрасываются. Или же каждый блок разделяется на ряд областей. Для каждой области устанавливается отбор уровней квантования, число которых выбирается пропорционально средней дисперсии спектральных коэффициентов, принадлежащих данной области.
При пороговом кодировании для всех спектральных коэффициентов, превышающих по величине заданный порог, устанавливается единая шкала-квантования. Остальные коэффициенты просто исключается. Позиция коэффициентов, прошедших пороговый отбор, указывается числом исключенных коэффициентов, разделяющих соседние значащие коэффициенты.
Под кодированием энтропии понимается статистическое кодирование коэффициентов преобразования.
Минимальную среднеквадратическую ошибку кодирования обеспечивает преобразование Карунена-Лоэва (Хотеллинга), но оно требует знания статистических характеристик ансамбля кодируемых изображений,.и для этого метода нет быстрого вычислительного алгоритма. По эффективности к преобразованию Карунена-Лоэва самым близким является косинусное преобразование, которое и получило широкое распространение. Используется также преобразование Хаара [51]
При использовании кодирования на основе преобразования для цветных изображений осуществляется переход от координат цвета источника R, G, В, определяющую красную, зеленую и синюю составляющие для каждого элемента изображения, к трехмерной системе координат Y, I, Q , определяющих координаты яркости и цветности.
Гибридный метод кодирования с использованием преобразований и ДИКМ сохраняет основные теоретические преимущества двумерных преобразований, но приводит к более простым в практическом осуществлении системам. Вначале производится двумерное преобразование блока из NxN элементов в спектральные коэффициенты, которые затем подвергаются обработке с помощью ДИКМ. Эта обработка ведется в направлении столбцов исходного изображения и сводится к кодированию с предсказанием по предшествующему элементу.
В качестве преобразований в настоящее время в форматах файлов растровой графической информации используются дискретное косинусное преобразование и дискретное вейвлет-преобразование [11]. Квантование производится учетом восприятия человеческим глазом различных частот. Те частоты, которые плохо воспринимаются глазом, квантуются более грубо, меньшим числом разрядов. На шаге квантования и происходят потери информации. При требовании точного воспроизведения этот шаг может быть опущен.
На основе дискретного косинусного преобразования построен стандарт сжатия JPEG, разработанный в 1991 году группой экспертов в области фотографии специально для сжатия 24-битных изображений [85-87]. Алгоритм JPEG подробно рассмотрен в [91, 97].
Разработка алгебраической модели оценки растровых изображений
Определение набора признаков изображения для моделирования является одной из основополагающих задач, от успеха решения которой-зависит возможность получения достоверных моделей. В области распознавания образов, где наиболее часто решается эта задача, она не имеет формального метода, позволяющего быстро, без глубоких исследований, требующих много времени и ресурсов, получить точное решение. Объяснением служит многообразие признаков, способов их представления и оценки и многообразие решаемых задач. Как правило, эвристические подходы, основанные на знаниях о предметнойобласти и опыте специалистов, приводят к более быстрым и качественным результатам. В данной работе для выделения признаков использовался эвристический подход.
Признаком изображения является его простейшая отличительная характеристика или свойство. Признаки можно разделить на естественные, уста-наливаемые визуальным анализом изображения, и искусственные, получаемые в результате его специальной обработки или измерений. К естественным признакам относятся светлота (яркость) и текстура различных областей изображения, форма контуров объектов. Гистограммы распределения яркости и спектры протранственных частот дают примеры искусственных признаков. Для-решения поставленных задач интерес представляют искусственные признаки, так как они позволяют получить компактное представление о разных изображениях с помощью небольшого унифицированного набора количественных характеристик. Как уже отмечалось в первом разделе, для моделирования коэффициентов преобразования, яркости и разностных сигналов в задачах определения параметров фильтрации используются различные статистические характеристики изображения, которые оцениваются при допущении, что изображение является стационарным изотропным полем. Ряд этапов методов сжатия с потерями можно представить как фильтрацию, поэтому в набор признаков целесообразно включить статистические признаки. Методы без потерь, так же зависят от статистических свойств конкретного изображения. Для оценки вероятности появления конкретного значения пикселя или пары значений используется гистограмма изображения, поэтому эти признаки обозначены далее, как гистограммные признаки соответственно первого и второго порядка. Так как реальные изображения не являются изотропными стационарными полями, из-за наличия деталей, контуров, границ, несущих основную информацию и являющихся основным препятствием для достижения высоких коэффициентов сжатия, в набор должны быть включены также признаки, характеризующие перечисленные неоднородности изображениям Для этого предлагается методика выделения неоднородностей и стационарных областей с помощью квадродерева, позволяющая енить их топологические и геометрические характеристики. Также были введены дополнительные признаки, которые оказывают влияние на коэффициент сжатия изображения. Итак, предлагаемый набор признаков подразделяется на три группы: гистограммные признаки первого и второго порядка, признаки, оценивающие стационарность и неоднородность поля изображения, прочие признаки.
При рассмотрении растрового изображения как однородного изотропного стационарного поля и из предположения об эргодичности случайного процесса его породившего распределение вероятностей значений яркости первого порядка определяется как P(b) = Pr{a(iJ) = b}, (2.1) где О Ъ L-1 - уровни квантования. Распределение частот первого порядка, оценивающее Р(Ь), описывается простым выражением: P(b) N(b)/N, (2.2) где N — полное число элементов изображения, a N(b) — число элементов изображения, имеющих уровень Ь.
Используют следующие характеристики, описывающие форму гистограмм первого и второго порядка: M = (b,o- ,bs,bK,bN,bE,BA,Bc,Bj,Bv,BN) Средняя яркость: Ь = ЬР(Ь) (2.3) 6=0
Средняя яркость изображения влияет на коэффициент сжатия при использовании методов сжатия с потерями JPEG и JPEG2000. Чем темнее изображение, тем меньше, как правило, заметны искажения, вносимые алгоритмами сжатия с потерями, и тем сильнее их можно сжать. Кроме того, ожидаются меньшие значения коэффициентов преобразования, что при упаковке дает более высокий коэффициент сжатия.
Дисперсия: У2Ь= {Ь-Ъ)2Р{Ъ). (2.4) 6=0 Этот признак должен оказывать существенное влияние на коэффициент сжатия, достигаемого любым из методов сжатия, который построен из расчета того, что соседние пиксели имеют близкие значения, т.е. для изображений с большими гладкими областями.
Разработка алгоритма комплексного анализа признаков изображения
На первом этапе методики необходимо определение признаков изображения, что накладывает условие на значение вычислительной сложности алгоритма, которая не должна превышать вычислительной сложности методов сжатия, в противном случае использование моделей для получения оценок коэффициентов сжатия теряет смысл. Для алгорит мов сжатия изображений и определения признаков, чтобы иметь возмож ность более точно описать их сложность и сопоставить между собой;,;.необ ходимо учитывать затраты, не только связанные с вычислением преобра зования и; квантования, но и на такие операции как упаковка данных, фор мирование групп, сбор статистики генерация кодов, формирование потока переход кпалитре. - ". Обзор рассматриваемых алгоритмов сжатия и операций, необходимых для вычисления признаков, изображения, позволил выделить слег дующие базовые операции: - сложение (вычитание): at - с фиксированной точкой, ау- с плавающей точкой; - умножение: ти - с фиксированной точкой, mj с плавающей точкой; - деление: d{ - с фиксированной точкой, df с плавающей точкой; - извлечение квадратного корня q; - вычисление log log; - сравнение с, реализуется как вычитание и анализа регистра флагов; - сдвиг s; -упаковка п, включает в себя сдвиги и логические операций, которые выполняются при формировании выходного байта в схемах компрессии; использующих коды переменной длины. Сложность алгоритма предлагается описывать выражением вида: а/а,- + aimi+a di+a +ass+a i+a-aj+asmf+agdj+aioq+ajjlog (3.1)
Подставив в такое выражение вместо обозначений соответствующие затраты, необходимые для ее выполнения в некоторых единицах, мы получим численную оценку сложности. Как правило, в качестве единицы сложности принимают затраты на выполнение операции сложения, тогда все остальные операции заменяются эквивалентным числом операций сложения, и оценка вычислительной сложности получается в операциях сложения. Форма представления сложности (3.1) выбрана для того, чтобы обеспечить возможность получения численной оценки сложности для различных типов АЛУ, так как соотношения между приведенными операциями для них могут сильно различаться.
Оценим вычислительную сложность алгоритмов сжатия- группового кодирования LZW, JPEG и JPEG2000.
И в алгоритме группового кодирования, и в алгоритме LZW необходимо составить палитру (таблицу цветов) изображения и перейти" от трех-компонентного описания пикселей к индексам палитры. При переходе вектор компонент пикселя сравнивается с входом в палитре и в случае совпадения записывается индекс найденного входа. Максимальное количество входов в таблицу цветов 256. Для некоторых пикселей индекс будет определен по первым сравнениям. Для других необходимо проверить все входы, поэтому будем считать, что в среднем необходимо 256/2=128 сравнений для каждого пикселя. Операция замены пикселя на индекс по затратам незначительна и поэтому ее можно не учитывать. Таким образом, сложность перехода к палитре для изображения размерами Nx х Ny составляет 128NxNyc.
В алгоритме группового кодирования выделяются цепочки одинаковых байт, для чего рассматривается каждый пиксель и либо присоединяется к группе, либо предыдущая группа записывается в файл и организуется новая. Для принятия решения о присоединении пикселя к груп пе или образования новой для каждого пикселя необходимо выполнить сравнение с, а запись группы в поток соответствует операции п. Тогда, исходя из наихудшего предположения о том, что не удается выделить цепочки одинаковых байт, и учитывая затраты на переход к палитре, сложность алгоритма группового кодирования будет 128NxNyc + NxNyjc + NxNfi = (129с + n)NxNy
В алгоритме LZW при кодировании динамически создается словарь. Каждый новый пиксель добавляется в цепочку, осуществляется поиск новой цепочки по словарю, если ее нет, то она добавляется в словарь, в поток заносится код предыдущей цепочки, и построение цепочки начинается заново. Максимальный размер словаря 212 - 4096 входов, минимальный равен количеству цветов в палитре. При таком большом размере словаря целесообразно использовать алгоритмы быстрого поиска. Цепочка состоит из кода предыдущей выделенной цепочки (до 12 бит) и символа (8 бит), поэтому размер ключа 20 бит. При использовании двоичного поиска в словаре цепочка находится за 20 операций сравнения с, выполняемых для каждого пикселя. Количество операций записи кода пикселя в поток, упаковки, в худшем случае, когда не удается выделить одинаковых цепочек, будет равно количеству пикселей. Таким образом, с учетом затрат на переход к палитре сложность алгоритма LZW может быть оценена сверху как 128NxNyc + 20NxNyc + NxNyn = (148с + n)NxNy.
Сжатие изображения с помощью алгоритма JPEG состоит из четырех этапов: - вычисление дискретного косинусного преобразования (ДКП); - квантование; - обработка коэффициентов; - статистическое кодирование Хаффмана.
