Содержание к диссертации
Введение
1. Анализ широко используемых методов сжатия цифровых изображений, подходов к оценке их эффективности и программных средств ее повышения . 14
1.1. Способы представления цифровых растровых изображений. 14
1.2. Классификация методов сжатия цифровых изображении. 17
1.3. Анализ подходов к оценке потерь качества 21
1.4. Описание и анализ основных широко используемых методов сжатия 24
1.4.1. Статистическое (энтропийное) кодирование. 24
1.4.21 Групповое кодирование, или кодирование серий (RLE). 25
1.4.3. Кодирование одинаковых последовательностей (LZ-подобные алгоритмы, LZW). 27
1.4.4. Кодирование на основе преобразования: алгоритмы JPEGirJPEG2000;; 28
1.5. Изображения 35
1.6. Анализ подходов к оценке эффективности методов сжатия. 37
1.7. Анализ программных средств повышения эффективности применения методов сжатия цифровых изображений 39
1.8 Постановка задач на исследование. 42
1.9. Выводы. 43
2. Самоорганизация моделей для оценки коэффициента и параметров сжатия для различных методов компрессии : 46
2.1. Определение набора признаков изображений; оказывающих влияние на коэффициент и параметры сжатия. 46
2.1.1. Анализ влияния гистограммных признаков первого и второго порядка на сжимаемость изображения различными методами, 47
2.1.2. Методика оценки неоднородности изображения с помощью квадродерева. 53
2.1.3; Прочие признаки, оказывающие влияние на сжимаемость изображений; 63
2.2. Применение метода группового учета аргументов (МГУА). 64
2.3; Построение моделей для оценки максимально возможного коэффициента сжатия и параметров для различных классов методов компрессии. 72
2.4: Выводы. 74
3; Разработка математического и программного обеспечения эффективного сжатия изображений . 77
3.1. Математическое описание системы эффективного сжатия? изображений; 77
3.2. Разработка алгоритма комплексного определения признаков изображения с наименьшей вычислительной сложностью 80
3.2.1. Оценка вычислительной сложности алгоритмов сжатия. 81
3;2.2. Синтез алгоритмов определения признаков изображения' оценка и их вычислительной сложности 87
3.2.3. Сравнение суммарной вычислительной сложности алгоритмов сжатия и определения признаков изображения 97
3:3. Алгоритм многорядного МГУА с исключением незначимых элементов. 99
3.4. Алгоритм выбора метода и параметров сжатия с использованием моделей изображений- 101
3;5; Выводы 103
4. Экспериментальное исследование программного обеспечения эффективного сжатия растровых изображений . 105
4.1. Программное обеспечение для получения и использования* многорядных моделей оценок коэффициентов и параметров сжатия различными методами. 105
4.1.1. Структура программного обеспечения: 105
4.1.2. Разработка подсистемы сбора экспериментальных данных 107
4.1.3; Разработка подсистемы моделирования 111
4.2. Исследование эффекта применения процедуры исключения, незначимых элементов на основе анализа коэффициента множественной детерминации в многорядном МГУА 116
4.3; Анализ многорядных моделей; получаемых на различных наборах данных 117
4.4. Формирование архивов медицинских диагностических изображений с использованием разработанного ПО. 124
4.5; Применение разработанного ПО в системах видеонаблюдения. 131
4.6. Выводы 134
Заключение; 136
Литература 139
- Описание и анализ основных широко используемых методов сжатия
- Применение метода группового учета аргументов (МГУА).
- Разработка алгоритма комплексного определения признаков изображения с наименьшей вычислительной сложностью
- Исследование эффекта применения процедуры исключения, незначимых элементов на основе анализа коэффициента множественной детерминации в многорядном МГУА
Введение к работе
В диссертации разработано математическое: и программное обеспечение для; построения подсистемы, позволяющей повысить эффективность применения методов сжатия изображений в различных системах обработки, хранения и передачи цифровых изображений.
Актуальность темы. С развитием ш разработкой новых технических средств получения растровых цифровых изображений в различных отраслях науки и промышленности, они все чаще используются в качестве данных об обрабатываемых и исследуемых объектах в системах, создаваемых на базе вычислительных машин; комплексов и компьютерных сетей. Представление цифровых изображений в виде; двумерных матриц требует больших объемов данных и предъявляет высокие требования к сетевому оборудованию при передаче их по каналам связи и к емкости внешних носителей при хранении. Так скромная, не очень качественная иллюстрация на обложке книги размером 500 х 800 точек занимает 1.2 Мб— столько же, сколько художественная книга из 400 страниц (60 знаков в строке, 42 строки на странице) [5]. Этим объясняется актуальность задачи создания, сопровождения и эксплуатации программных средств эффективного сжатия изображений. Особенно остро эта задача стоит перед системами, в которых необходимо обеспечить хранение большого количества изображений в автономном режиме: бортовые системы фотографирования поверхности Земли, спутниковые системы получения метеоснимков, медицинские базы данных, хранящие диагностические снимки, фотографии, результаты томографических исследований, охранные системы видеонаблюдения' с возможностью видеорегистрации.
В последние годы решению проблемы эффективного кодирования цифровых изображений уделяется серьезное внимание как у нас в стране, так и за-
рубежом [8]. Разработано большое количество различных методов сжатия цифровых изображений. Среди них есть как видоизмененныеуниверсальные, так и абсолютно новые методы, ориентированные исключительно на сжатие изображений! Более того, разрабатываются методы, ориентированные на конкретный класс изображений, например отпечатки пальцев, медицинские снимки; Практика использования различных методов кодирования, изображений; реализованных в существующих программных средствах, показывает, что нет универсального метода, который был бы одинаково эффективен для; всех видов изображений. Как правило, любой. из существующих методов обеспечивает высокий коэффициент сжатия при сохранении хорошего качества для одного вида изображений; а для других высокий коэффициент сжатия достигается ценой значительных потерь, заметных при визуальной оценке, а в худшем случае метод не применим [54]. Кроме того, методы сжатия с потерями, как правило, имеют параметры, позволяющие управлять соотношением между объемом и качеством: чем меньше объем, тем ниже качество и наоборот. Для-одних изображений допускаются значительные потери, которые не заметны при визуальной оценке, и за счет этого максимально возможный коэффициент сжатия для них высок. Длядругих же изображений даже небольшие потери приводят к заметным искажениям, и как следствие, максимально допустимый коэффициент сжатия-для них небольшой.Пользователь, который имеет опыт использования? методов сжатия цифровых изображений; может по виду изображения определить, какой;метод их какими параметрами является наиболее подходящим или подобрать их экспериментально.. Но часто необходимо обеспечить. эффективную компрессию '> изображений»в автономном режиме ив масштабе реального времени. Это делает актуальной задачу разработки методики создания программных средств, осуществляющих для конкретного изображения выбор подходящего метода кодирования и определение его параметров, которая, и решается в данной работе.
Указанные обстоятельства определили направление исследований диссертационной работы.
Объектом исследования являются программные средства повышения эффективности применения методов сжатия цифровых изображений.
Предметом исследования являются методы определения; максимально возможного коэффициента и параметров сжатия; для - различных методов компрессии цифровых изображений по его признакам.
Цель и задачи диссертации. Целью является уменьшение объема данных для хранения цифровых изображений и передачи их по каналам связи за счет повышения эффективности применения существующих методов сжатия; и использования для кодирования подходов, обеспечивающих минимальный объем данных при сохранении приемлемого качества.
В соответствии с указанной целью были; поставлены и решены следующие задачи:
Анализ существующих методов сжатия и подходов к оценке их эффективности с целью выделения признаков, оказывающих влияние на максимально возможный коэффициент сжатия.
Анализ существующих программных инструментальных средств, позволяющих сократить объемы данных для хранения * цифровых изображений и передачи их по каналам связи.
Разработка методики построения? моделей изображений, дающих оценки максимально возможного коэффициента и параметров сжатия, для различных методов кодирования.
Разработка программного инструментального средства "Моделирование изображений" для построения на основе экспериментальных данных моделей; позволяющих по вектору признаков изображения вычислить оценки максимально возможного коэффициента сжатия и параметров для различных методов сжатия. Разработка динамически загружаемой библиотеки для интеграции полученных с помощью инструментального средства оценивающих моделей в системы обработки, хранения и передачи цифровых изображений для повышения эффективности применения методов сжатия.
Методы исследования: В качестве основного инструмента теоретического исследования использовались методы функционального анализа, линейной алгебры, теории вероятностей и математической статистики; теории случайных процессов, теории информации, методы самоорганизации моделей сложных систем.
Научная новизна: В диссертационной: работе получены следующие новые научные результаты:
11 Выделены признаки цифровых растровых изображений; от которых зависит его > сжимаемость, для* построения моделей оценкш максимально возможного коэффициента сжатия для различных методов компрессии.
2. Разработана методика анализа неоднородности поля изображения с использованием квадродерева с черно-белыми- вершинами, позволяющего выделить однородные и неоднородные области; и описать их с помощью геометрических и топологических признаков.
3: Для самоорганизации математических моделей' оценки максимально возможного коэффициента сжатия и соответствующих параметров;применен метод группового учета аргументов (МГУА), который позволяет получить достаточно адекватные модели на выборках малого размера. Использование предложенной процедуры исключения незначимых элементов частных моделей на основе анализа коэффициента множественной детерминации, позволяет улучшить качество синтезируемых моделей и уменьшить их сложность, определяемую как наивысшая степень полинома.
4. Разработана методика построения многорядных моделей изображения, дающих оценку максимально возможного коэффициента1 сжатия»и соответствующих параметров для различных классов методов сжатия.
На защиту выносятся следующие основные результаты:
- форма представления изображения в виде набора характеристик, включающего наряду со статистическими (гистограммными) предложенные признаки, характеризующие неоднородность изображения, что позволяет про-
граммно построить более точные модели для оценки максимально возможного коэффициента и параметров сжатия для различных методов кодирования;
методика и программное обеспечение оценки степени неоднородности поля изображения на основе квадродерева; позволяющего обозначить однородные (с плавным изменением характеристик пикселей) и неоднородные (содержащие резкие переходы, детали) области, и описать их с помощью геометрических и топологических признаков;
методика ^программное обеспечение построения моделей для оценки максимально возможного коэффициента и параметров сжатия для различных методов кодирования на основе МГУ А; который позволяет получить их на экспериментальной выборке малого размера;
методика создания* программного обеспечения эффективного применения имеющегося набора методов компрессии изображений за счет выбора; на основе оценок, даваемых полученными моделями изображения, такого метода и таких его параметров, которые обеспечивают минимальный объем данных при сохранении приемлемого качества.
Практическая ценность Разработанные: методики и алгоритмы позволяют создавать программные средства эффективного» применения имеющихся методов сжатия в системах обработки, хранения и передачи изображений, работающих с большим количеством цифровых изображений в автономном режиме.. Их использование целесообразно в томі случае, если вычислительная сложность оценки максимально возможного коэффициента- сжатия; не превышает оценки сложности используемых алгоритмов сжатия. Полученные программные средства эффективного применения имеющихся і методов сжатия позволяют:
сократить время разработки систем обработки, хранения и передачи цифровых изображений, за счет эффективного использования существующих методов сжатия, вместо разработки специализированного метода сжатия;
в системах передачи цифровых изображений за счет эффективного применения методов сжатия разгрузить более чем на 10...20% канал связи, и,
следовательно, повысить достоверность полученной информации, сократить время и/или снизить мощность и вес передающей аппаратуры;
- в системах регистрации и хранения цифровых* изображений за счет эффективного применения методов сжатия снизить количество и объем і внешних накопителей более чем на 10...20%, благодаря чему сократить расходы на хранение и поиск информации в архиве.
Реализация и внедрение результатов работы: Предложенные алгоритмы ш методы реализованы в виде пакета программ на языке: C++ для» машин IBM1 PC AT. Пакет программ.включает в себя программное обеспечение "Моделирование изображений" и динамически загружаемую- библиотеку для операционной системы MS Windows 9x/Me/NT2000/XP.
Программное обеспечение "Моделирование изображений" позволяет собирать экспериментальные данные, включающие характеристики изображений и максимально возможные коэффициенты сжатия отдельно по каждому методу, и строить по ним многорядные полиномиальные модели, дающие оценку максимального коэффициента сжатия.и; параметров:изображения;. На данный момент включены и исследованы методы JPEG, LZW, RLE (групповое кодирование) и JPEG2000, но набор методов может быть легко расширен.
Динамически загружаемая библиотека включает в себя функции, которые позволяют по многорядным, моделям, полученным шсохраненным в файле с помощью ПО "Моделирование изображений", для конкретного изображения' определить метод, обеспечивающий максимально возможный коэффициент сжатия^ и его параметры.
Разработанное программное обеспечение было использовано при построении ! системы обработки, передачи и хранения медицинских цифровых диагностических изображений в ТУП "НИИ новых медицинских технологий" (г. Тула). В результате внедрения разработанного программного обеспечения і удалось снизить объем архивов диагностических изображений на 20%. Также оно было использовано в системах видеонаблюдения с возможностью ведения видеорегистрации в НЛП "Альфа-прибор" (г. Тула), что привело к сокращению
объема видеоинформации и соответственно?количества внешних носителей на 10%.
Разработанные методики; и« алгоритмы: используются- в учебных курсах "Теория сигналов" и "Программирование на языке высокого уровня" на кафедре ЭВМ Тульского государственного университета.
Внедрение результатов диссертационной работы и достигнутый при этом эффект подтверждены соответствующими актами.
Апробация работы. Основные положения и результаты диссертационной; работы докладывались XV Международной научной конференции "Математические методы в технике и технологиях" в 2002 г. (г. Тамбов), 5-й\ Международной конференции "Распознавание-200 1" и 6-й Международной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2003" соответственно в 2001, 2003 гг. (г.Курск), XXVI, XXVIII Молодежных Международных научно-технических конференциях "Гагаринские чтения" в 2000 2002 гг. (г.Москва), XVII;XVIII научной сессии РНТОРЭС им. А.С.Попова в 2000,2001 гг. (г.Тула), 7-й Всероссийской НТК студентов, молодых ученых и специалистов, посвященная; 50-летию РГРТА "Новые информационные технологии» в научных исследованиях ив образовании" в 2002 г. (г. Рязань), 4-й Международной НТК; "Космонавтика. Радиоэлектронника. Геоинформатика." в 2003 г. (г.Рязань), Межрегиональных научно-технических конференциях "Интеллектуальные и информационные системы" в 2000, 2003 гг. (г. Тула); XL Всероссийской конференции по проблемам математики, информатики, физики и химии. Секция «Оптические, математические и электронные методы обработки изображений и сигналов» в 2004 г. (г. Москва, РУДН).
По результатам исследований опубликовано 17 работ [24-33,,37-43], втом числе 7 статей [25-31] и 10 тезисов докладов.
Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и четырех приложений.
В первом разделе проанализированы детерминированный и статистический подходы к формальному описанию цифровых изображений, и сделан вывод о необходимости использования формального описания в виде набора признаков, учитывающих как статистические свойства изображения, так и особенности его содержимого. Также в разделе приведены классификация, краткое описание основ ї и характеристика существующих методов сжатия. Наиболее широко используемые методы RLE, LZW, JPEG и новый метод JPEG2000 рассмотрены более подробно. Проанализированы подходы к оценке коэффициента сжатиями эффективности методов сжатия, сделан вывод о необходимости разработки подхода, учитывающего характерные особенности; конкретного изображения. Дан анализ существующих программных средств оптимизации объемов цифровых изображения за счет выбора метода кодирования и параметров.
Во втором разделе приводятся теоретические положения, являющиеся основой для разработки методики построения моделей для оценки максимально возможного коэффициента и параметров сжатия. Выделены признаки, определяющие коэффициент и параметры сжатия. Приведена новая методика численного описания неоднородности изображения с использованием квадродере-ва. Разработана методика построения моделей изображения для оценки максимально возможного коэффициента и параметров сжатия для* различных классов методов сжатия. Описана предлагаемая процедура исключения статистически незначимых элементов частных квадратичных моделей на основе анализа коэффициента множественной '< детерминации в многорядном * МГУА с квадратичными частными описаниями, которая; позволяет повысить точность. и снизить сложность синтезируемых моделей.
В третьем разделе дано математическое описание системы эффективного сжатия цифровых изображений. Приведены алгоритмы определения признаков изображения с минимальной вычислительной сложностью.. Оценена сложность . наиболее широко используемых методов сжатия. и разработанного алгоритма вычисления признаков. Сформулирован критерий рациональности использования моделей для получения оценки максимально возможного коэффи-
циента сжатия вместо непосредственного его измерения; Приведены алгоритмы МЕУА с процедурой исключения статистически : незначимых элементов на каждом ряду селекции и выбора для і конкретного изображения метода и параметров сжатия с помощью получаемых моделей изображений:
В > четвертом разделе освещены. вопросы реализации> программного < инструментального средства."Моделирование изображений!' и; динамической библиотеки; позволяющей для конкретного-изображения по многорядным моделям получить оценку максимально возможного коэффициента и параметров сжатия, и интеграции их в систему получения, обработки, хранения и передачи цифровых изображений. Описаны структуры данных и форматы файлов для хранения экспериментальных данных и; многорядных моделей. Рассмотрены результаты внедрения; разработанного программного обеспечения в- систему получения, обработки, хранения и передачи медицинских изображений- и в систему видеонаблюдения с возможностью видеорегистрации ш необходимостью долговременного хранения записанных видеофрагментов.
В заключении перечисляются основные результаты диссертационной работы и формулируются выводы.
В приложении 1' приведены данные по длительности выполнения арифметических операций* процессором Celeron-1200, которые используются при определения вычислительной сложности алгоритмов.
В приложении 2 приведена блок-схема алгоритма работы и схема.ресурсов программного инструментального средства "Моделирование изображений".
В приложении і приведены оценки коэффициентов сжатия, данные многорядными моделями, построенными с помощью программного' инструментального средства "Моделирование изображений" для. различных методов, и измеренные непосредственно для оценки точности и адекватности моделей.
В приложении 4 помещены акты внедрения результатов диссертационной работы.
1. АНАЛИЗ ШИРОКО ИСПОЛЬЗУЕМЫХ МЕТОДОВ СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ, ПОДХОДОВ К ОЦЕНКЕ ИХ ЭФФЕКТИВНОСТИ И ПРОГРАММНЫХ СРЕДСТВ ЕЕ ПОВЫШЕНИЯ
Описание и анализ основных широко используемых методов сжатия
Сущность метода статистического кодирования заключается в том, что уровням с большей вероятностью появления ставятся в соответствие короткие кодовые слова, и наоборот, элементам с реже встречающимися уровнями ста вятся в соответствие более длинные кодовые слова. В начале при составлении кода необходимо произвести моделирование, оценку или измерение вероятностей появления элементов с различными уровнями для изображения определенного типа. Существует ряд высокоэффективных кодов, подходящих для поэлементного статистического кодирования изображений. Самыми известными из них являются коды Шеннона-Фано [52, 70] и Хаффмэна [83]. Последний всегда реализует наивысшую достижимую для данного источника сообщений эффективность.
Коэффициент сжатия оценивается по следующей формуле где «о - длина исходного кода, (/) - средняя длина кода, которая определяется по следующей формуле: где 1(ак) — длина кода элемента я , Рг{ } - вероятность появления, или частота, символа я . Согласно теореме Шеннона [69] где Н(а) — энтропия случайной величины. Методы Хаффмена и Шеннона-Фано дают Н(а) (/) Н(а) + 1. Они кодируют символы целым числом бит, поэтому нижняя граница Ща), если она представляет собой дробное число, не достигается. С этой точки зрения, более эффективными являются арифметическое и блочное кодирование [67]. Как показали исследования Назарова Л.Е. и Назаровой 3.Т. [49], применение статистического кодирования непосредственно к элементам изображения малоэффективно. Например, применение статистического кодирования для изображений РСА (космические изображения земной поверхности) позволяет достичь коэффициента сжатия уц є(1,2 -г-2,0)..
Энтропийное кодирование применяется как дополнительный этап в схемах кодирования с преобразованиями. Метод кодирования серий основан на сравнении уровней соседних элементов вдоль строки развертки. Серией называют последовательность элементов, уровни которых не отличаются или мало отличаются друг от друга. Соседняя серия отделятся большим скачком і уровня: — контуром;
При таком способе кодирования передается либо уровень последнего элемента серии, либо функция значения разностного сигнала на границе серий- Позиция последнего эле-ментаданной серии определяется числом элементов от начала строки — кодирование концов серий, либо относительно последнего элемента \ предыдущей серии - кодирование длин серий. Кодирование длин серий эффективнее, так как средняя длина кодовых комбинаций, определяющих положение границ серий, сравнительно невелика. При реализации , этого метода назначается максимально возможнаядлина серии, для того чтобы упростить декодирование;информации. Здесь важен выбор максимально возможною длины серии с целью сокращения количества серий; для которых число разрядов, отводимых на кодирование длины, избыточно, и для уменьшения необходимости дробить длинные серии на ряд коротких. Эта проблема была изучена У.Прэттом [53]. Им были исследованы зависимости коэффициента сжатия от предела длины серии М и от вероятности появления контура р. Рассматривались М, равные 8; 16, 32,.64,..128:.. В,табл. 1.2. приведены оптимальные значения пределов серии М для различных интервалов изменения; вероятностей появления контуров р, полученные в результате этих исследований
Применение метода группового учета аргументов (МГУА).
МГУА позволяет решать задачу идентификации структуры и параметров сложных объектов по результатам наблюдений [19-23;.34]." Этот метод удовлетворяет двум принципам: 1) принципу Геделя (принцип внешнего дополнения) - только внешние критерии, основанные на новой информации, позволяют найти истинную модель объекта, скрытую в зашумленных данных; 2) принципу Д.Табора - всякая однорядная процедура структурной идентификации может быть заменена многорядной (обладающей меньшей трудоемкостью) только при условии сохранения "свободы выбора" нескольких лучших решений каждого предыдущего ряда. Алгоритмы, реализующие МГУА, воспроизводят схему массовой селекции. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Полное описание объекта Ф = f(x\ x2 x3.-)) заменяется рядами частных описаний, как показано на рис. 2.6. Различные алгоритмы МГУА отличаются друг от друга по виду функции / Известны алгоритмы с квадратичным и линейным полиномами, вероятностные алгоритмы МГУА, использующие формулы Байеса или теории статистических решений, и многие другие. В основном алгоритме МГУА используются квадратичные полиномы [20] вида: На следующий ряд селекции выбираются только наилучшие по некоторому внешнему критерию модели. В качестве внешнего критерия для задачи открытия функциональной зависимости лучше всего подходит критерий минимума смещения [34]. Для вычисления любого внешнего критерия выборка делится на две подвыборки обучающую (ХА, YA)n проверочную (Хв, YB) объемом NA и NB соответственно.
Очевидно, что NA+NB = N Перед разбиением, согласно третьему способу регуляризации [21], точки располагаются в ряд по величине их дисперсии от среднего значения, и этот ряд делится на две указанные подвыборки. Обучающую подвыборку составляют точки с четными номерами, а проверочную — с нечетными. Критерий минимума смещения вычисляется по следующей формуле: где УАІ значение, рассчитанное по модели, построенной на основе данных обучающей подвыборки (ХА, YA); УВС значение, рассчитанное по модели, построенной на основе данных проверочной подвыборки (Хв, YB); Утабл. табличные значения выходной переменной. Дополнительно необходимо обеспечить, чтобы, получаемые модели обладали хорошим качеством прогноза. Внешним критерием оценки качества прогноза является критерий регулярности: Для оценки и отбора моделей целесообразно использовать комбинированный критерий: Полученные на одном ряду модели упорядочиваются по данному критерию, и выбирается т моделей, где т — число входных переменных. Для того чтобы в результате такого отбора не потерять переменную, которая оказывает существенное влияние на поведение объекта только совместно с другими переменными, используется протекция переменных. Для этого анализируются отобранные модели, и составляется список использованных в них входных переменных. В том случае, если не все входные переменные задействованы в отобранных моделях, то среди оставшихся ищутся наилучшие, включающие эти переменные. Найденные модели также участвуют в формировании моделей для следующего ряда селекции. Селекция продолжается до тех пор, пока наименьшее значение комбинированного внешнего критерия р уменьшается. Характер изменения внешнего критерия в зависимости от ряда селекции, или от сложности модели, показан на рис. 2.7.
Разработка алгоритма комплексного определения признаков изображения с наименьшей вычислительной сложностью
Вычислительная: сложность определения признаков изображения не должна превышать вычислительной сложности алгоритмов сжатия, в противном случае использование моделей для получения оценок коэффициентов сжатия теряет смысл. Для алгоритмов сжатия изображений и определения признаков, чтобы иметь возможность более точно описать их сложность и сопоставить между собой; необходимо учитывать затраты, не только! связанные с вычислением преобразованиям квантования, но и на такие операции как упаковка данных, формирование групп, сбор статистики, генерация кодов, формирование потока, переход к палитре;
Обзор; рассматриваемых алгоритмов- сжатия и операций; необходимых для вычисления признаков изображения, позволил выделить следующие базовые операции: сложение (вычитание):: а/.— с фиксированной точкой, а/— с плавающей точкой; умножение: mt — с фиксированной точкой, ntf- с плавающей точкой; деление::dj — с фиксированной точкой, df- с плавающей точкой; извлечение квадратного корня q; вычисление log log; сравнение с, реализуется как вычитание и анализа регистра флагов; сдвигs;; упаковка л, включает в себя сдвиги и-логические операций; которые выполняются при формировании выходного байта в схемах компрессии; использующих коды переменной длины. Сложность алгоритма предлагается описывать выражением вида:
Подставив f в такое выражение вместо обозначений соответствующие затраты, необходимые для ее выполнения І в некоторых единицах, мы получим численную оценку сложности; Как правило, в качестве:единицы сложности принимают затраты на выполнение операции сложения, тогда все остальные операции заменяются эквивалентным числом операций сложения; и оценка вычислительной і сложности получается в операциях сложения. Форма представления сложности (3.2) выбрана для того, чтобы обеспечить возможность получения численной г оценки сложности для различных типов АЛУ, так как соотношения между приведенными операциями для них могут сильно различаться.
Оценим вычислительную сложность алгоритмов сжатия: группового кодирования LZW, JPEG и JPEG2000.
И в алгоритме группового кодирования, ив алгоритме LZ W необходимо составить палитру (таблицу цветов) изображения и перейти от трехкомпонент-ного описания пикселей к индексам палитры. При переходе вектор компонент пикселя сравнивается с входом в палитре ив случае совпадения записывается индекс найденного входа. Максимальное количество входов в таблицу цветов 256. Для некоторых пикселей индекс будет определен по первым сравнениям, для других необходимо проверить все входы, поэтому будем считать, что в среднем необходимо 256/2=128 сравнений для каждого пикселя. Операция замены пикселя на индекс по затратам незначительна и поэтому ее можно не у читывать. Таким образом, сложность перехода к палитре для изображения размером; x-Ny составляет \2SNxNyc.
В алгоритме группового кодирования выделяются; цепочки одинаковых байт, для чего рассматривается каждый пиксель и либо присоединяется к группе, либо предыдущая группа; записывается; в файл ш организуется новая. Для принятия решения о присоединении; пикселя к группе или образования новой для каждого пикселя необходимо выполнить сравнение с, а запись группы в поток соответствует операции п. Тогда, исходя из наихудшего предположения о том; что не удается выделить цепочки одинаковых байт, и учитывая затраты на переход к палитре, сложность алгоритма группового кодирования будет l2SNxNyc + NxNyc + NxNyn = (129с + n)NxNy.
В; алгоритме LZW при кодировании динамически создается словарь. Ка-ждый.новый пиксель добавляется в,цепочку, осуществляется! поиск новой цепочки по словарю, если еенет,.то она добавляется в словарь, в поток заносится код предыдущей цепочки,, и- построение цепочки начинается заново. Максимальный размер словаря 212 = 4096 входов, минимальный равен количеству цветов в палитре. При таком большом размере словаря целесообразно использоватьч алгоритмы быстрого поиска. Цепочка состоит из кода предыдущей выделенной цепочки (до г 12 бит) и символа (8 бит), поэтому размер ключа 20 бит. Приї использовании двоичного поиска в; словаре цепочка І находится за 20 операций І сравнения с, выполняемых для? каждого пикселя; Количество операций записи кода пикселя в поток, упаковки, в худшем случае, когда- не удается выделить одинаковых цепочек, будет равно количеству пикселей. Таким образом; с учетом затрат на переход к палитре сложность алгоритма LZW может быть оценена сверху как \2SN-xNyc + 20NxNyc + NxNyn = (148с + n)NxNy.
Исследование эффекта применения процедуры исключения, незначимых элементов на основе анализа коэффициента множественной детерминации в многорядном МГУА
Для подтверждения того, что введение предложенной процедуры исключения незначимых элементов позволяет получать более простые и точные модели, был поведен ряд экспериментов, данные для которых генерировались случайным образом. Затем по сгенерированным данным вычислялась выходная величина по полиномиальной функциональной зависимости. Полученные данные и значения выходной переменной- передавались алгоритмам МГУА и МГУ Ас исключением незначимых элементов. На рис., 4.6 приведен типичный пример их работы. Общий объем экспериментальной выборки N = 30, объем обучающей выборки Л = 20, объем проверочной выборки іУд = 10. Число фак-торов т = 5. Заданная;функциональной; зависимости имеет вид: = 50хз + 5Ахз2Х2 — Эх/ . В результате использования предложенной процедуры исключения незначимых элементов модель получилась проще, ее сложность, оцениваемая как наивысшая степень полинома; которая равна 4, меньше, чем у модели, полученной в результате работы алгоритма, наивысшая степень полинома которой ; равна 8. Модель, полученная в результате работы алгоритма с исключением незначимых элементов, получилась также качественнее по комбинированному критерию. Кроме этого, на приведенном примере продемонстрировано правило останова при использовании предложенной процедуры.,
С помощью разработанного программного обеспечения были получены многорядные модели; для оценки коэффициентов сжатия, достигаемых при применении исследуемых форматов для хранения растровой- графической информации, и параметров кодирования. Целью проводимых экспериментов было показать возможность получения на основе выделенных в разделе 2.1 признаков изображения оценок,, достаточно близких к реальным значениям. Другая цель заключалась в том, чтобы, показать, что качество моделей улучшается при введениш в рассмотрении признаков, характеризующих отклонение растрового изображения» от нормального? изотропного стационарного поля и изменение цвета в плоскости изображения (неоднородность). Поэтому для каждой оценки были получены две модели: при построении первой1 использовались все введенные признаки, при построении второй только гистограммные признаки, которые, как уже говорилось, рассчитываются из предположения, что изображение представляет собой нормальное изотропное стационарное поле.. Полученные модели приведены ниже.
Модель для достигаемого при использовании формата GIF коэффициента сжатия, полученная на основе всех признаков, приведена на рис. 4.7. В ней оказались задействованы число различных цветов, доля черных вершин, средняя площадь, число Эйлера. Из гистограммных признаков - коэффициент эксцесса, и энергии, рассчитанные по гистограмме первого порядка и гистограмме второго порядка, как и предполагалось, с параметрами (Г, 0).
Модель для оценки достигаемого при использовании формата GIF коэффициента сжатия, построенная только по гистограммным признакам; приведена на рис. 4.8 Качество полученной модели хуже, чем качество предыдущей, нов нее также вошел коэффициент эксцесса, а из признаков, гистограммы второго порядка, рассчитанные только по гистограмме с параметрами (1, 0).
