Содержание к диссертации
Введение
Глава 1. Методы сжатия цифровых изображений 13
1.1. Основные классы изображений 14
1.2. Основные подходы к сжатию изображений 15
1.2.1. Сжатие без потерь 16
1.2.2. Сжатие с потерями 23
1.2.3. Стандарты сжатия цифровых изображений 28
1.3. Основные показатели эффективности методов сжатия и качества восстановленных изображений 34
1.4. Постановка задач на исследование 38
Выводы 41
Глава 2. Построение и исследование свойств разностно- упорядоченных систем дискретных функций Уолша 42
2.1. Краткий обзор дискретных функций Уолша и их упорядочений 42
2.2. Синтез разностно-упорядоченной системы дискретных функций Уолша 46
2.3. Свойства разностно-упорядоченных систем дискретных функций Уолша 52
2.4. Построение быстрых алгоритмов преобразований в разностно-упорядоченных системах дискретных функций Уолша 58
Выводы 66
Глава 3. Разработка двухэтапных алгоритмов сжатия изображений на основе дискретных преобразований Уолша 67
3.1. Двухэтапный метод сжатия изображений с использованием дискретных преобразований Уолша 67
3.2. Двухэтапный JPEG — подобный алгоритм сжатия изображений на основе дискретных преобразований Уолша 71
3.3. Комбинированный алгоритм сжатия изображений на основе дискретных преобразований Уолша 77
3.4. Двухэтапный алгоритм сжатия изображений с многопотоковым кодированием 79
3.5. Прогрессивная передача изображений с использованием двухэтапных алгоритмов сжатия изображений 86
3.6. Оценка вычислительной сложности двухэтапных алгоритмов сжатия изображений 88
Выводы 95
Глава 4. Исследование эффективности двухэтапных алгоритмов сжатия и их практического применения 97
4.1. Исследование эффективности методов сжатия и качества восстановленных изображений 97
4.1.1. Анализ эффективности двухэтапных алгоритмов сжатия изображений по коэффициенту сжатия по числу координат разложения 97
4.1.2. Результаты исследования эффективности алгоритмов на тестовых изображениях 105
4.2. Программная реализация кодер-декодера сжатия цифровых изображений 115
4.2.1. Назначение и структура кодер-декодера 115
4.2.2. Интерфейс программы 120
4.3. Решение практических задач сжатия изображений 123
Выводы 132
Заключение 134
Список литературы 136
- Основные показатели эффективности методов сжатия и качества восстановленных изображений
- Синтез разностно-упорядоченной системы дискретных функций Уолша
- Двухэтапный JPEG — подобный алгоритм сжатия изображений на основе дискретных преобразований Уолша
- Программная реализация кодер-декодера сжатия цифровых изображений
Введение к работе
Актуальность темы. Широкая информатизация является одной из наиболее актуальных проблем современного общественного прогресса. Развитие современных информационных систем и сетей привело к широкому использованию цифровых изображений. В настоящее время многие отрасли техники, имеющие отношение к получению, обработке, хранению и передаче информации, в значительной степени ориентируются на развитие систем, в которых информация представлена в виде изображений. При решении задач цифровой обработки изображений особое внимание уделяется использованию цветных изображений. В связи с этим вопросы сжатия цифровых изображений сегодня приобретают особую актуальность. Сжатие изображений (СИ) важно для повышения эффективности использования коммуникационных и информационно-вычислительных ресурсов указанных систем.
СИ из чисто теоретической задачи стало повседневной практикой, что требует при его осуществлении постоянного внимания к экономическим характеристикам и возможностям реальной аппаратуры. Существующие проблемы передачи изображений по низкоскоростным каналам связи, в частности по сети Интернет, а также проблемы просмотра видео или больших по размеру изображений на маломощных рабочих станциях также ужесточают требования к алгоритмам СИ. Поэтому актуальной является задача разработки новых эффективных методов и соответствующих алгоритмов сжатия, пригодных для практической реализации на современной элементной базе вычислительной техники.
К настоящему времени предложено и исследовано множество алгоритмов СИ. Весьма популярны в практике СИ алгоритмы поблочного кодирования с преобразованием, основанные на дискретных ортогональных преобразованиях. Новые перспективные методы, появившиеся на базе векторного квантования, субполосного кодирования, фрактальных преобразований, преобразований на основе всплесков, потенциально могут обеспечить существенно более высокое СИ, однако их внедрение пока во многих случаях упирается в проблему вычислительной сложности их реализации, которая часто объясняется отсутствием быстрых алгоритмов.
Значительный вклад в решение проблем обработки изображений с использованием дискретных ортогональных преобразований внесли как отечественные, так и зарубежные ученые: Л.П. Ярославский, Н.Н. Красильников, А.М. Трахтман, С.В. Умняшкин, Д.С. Ватолин, В.В. Сергеев, У. Прэтт, Н. Ахмед, К.Р. Рао, Д. Селомон, Р.С. Гонсалес, Д.А. Хаффман и др. Интерес исследователей к дискретным ортогональным преобразованиям связан со следующими причинами: большой набор систем базисных функций позволяет выбрать наиболее рациональную систему для решения конкретной задачи; появление задач цифровой обработки сигналов, решаемых наиболее эффективно с использованием новых дискретных базисов; успехи в области создания средств вычислительной техники на многозначной элементной базе и использованием нетрадиционных арифметик.
Среди алгоритмов с преобразованием фактическим стандартом является алгоритм JPEG (Joint Photographic Experts Group), поддерживаемый многочисленными программными и аппаратными системами цифровой обработки, хранения и передачи изображений. Однако этот алгоритм имеет низкую скорость работы и сложен в аппаратной реализации.
С точки зрения практической реализации наиболее простыми являются дискретные преобразования Уолша (ДПУ), которые, уступая используемому в алгоритме JPEG дискретному косинусному преобразованию (ДКП) в способности локализации энергии изображения в спектре, требуют для своей реализации значительно меньших вычислительных затрат. Вопросам СИ с использованием ДПУ посвящены работы как в России, так и за рубежом. Таким образом, актуальной задачей является разработка алгоритмов на основе дискретных преобразований Уолша, обеспечивающих возможность более эффективного сжатия изображений.
Следует отметить, что при СИ с помощью ДПУ существует возможность повышения эффективности сжатия посредством экстраполяции спектра и кодирования полученных трансформант и ошибок предсказания. Такой подход в ряде случаев может дать эффект, близкий к эффекту от использования оптимальных базисов для определенных классов изображений.
Представляет интерес также исследование существующих и построение новых упорядочений систем базисных функций Уолша. На практике для известных дискретных систем используется лишь незначительное количество фиксированных способов упорядочения базисных векторов, хотя известно, что эффективность решения отдельных задач цифровой обработки сигналов зависит от упорядочения функций в системе.
Цель работы. Цель диссертационной работы - повышение эффективности поблочного кодирования цифровых изображений с использованием дискретных преобразований Уолша.
Научная задача. Диссертационная работа посвящена решению следующей научной задаче: разработка двухэтапных методов, алгоритмов и программных средств сжатия изображений, обеспечивающих возможность эффективного кодирования изображений с использованием дискретных преобразований Уолша.
Достижение поставленной цели и решение научной задачи потребовало:
анализа известных методов сжатия цифровых изображений и подходов к оценке их эффективности;
построения новых фиксированных способов упорядочения дискретных функций Уолша (ДФУ) и быстрых алгоритмов преобразований по ним;
разработки двухэтапного метода к СИ, обеспечивающего возможность эффективного кодирования изображений с использованием ДПУ;
разработки алгоритмов СИ на основе ДПУ, реализующих двухэтапный метод;
оценки эффективности предложенных методов и алгоритмов СИ;
программной реализации предложенных алгоритмов СИ и выработки рекомендаций по их применению для решения различных практических задач.
Методы исследования. Для решения поставленных в диссертационной работе задач применены теория ортогональных преобразований, методы сжатия изображений, теории информации и статического анализа данных, использованы прикладные математические программы.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:
-
Предложены метод построения фиксированных упорядочений дискретных функций Уолша с использованием их конечно-разностных свойств и быстрые алгоритмы преобразований по ним.
-
Предложен двухэтапный метод к СИ на основе ДПУ, в котором предусматривается дополнительная обработка элементов двумерного спектра экстраполяционными методами.
-
Разработаны двухэтапные алгоритмы СИ, обеспечивающие возможность более эффективного кодирования изображений за счет частичной и полной экстраполяции трансформант Уолша.
-
Обоснована возможность использования двухэтапных алгоритмов СИ для прогрессивного сжатия изображений и предложен метод прогрессивной передачи трансформант Уолша.
Достоверность результатов работы. Положения диссертационной работы получены при использовании строгого математического аппарата, а также согласованности полученных новых результатов с известными. Достоверность научных результатов подтверждена данными компьютерного экспериментального исследования в программной среде Matlab 6.5 и разработанной в интегрированной среде Borland C++ 2005 программы кодирования/декодирования «Image Compressor JPGW».
Практическая ценность работы. Разработанные методы и алгоритмы СИ, использующие как разностно-упорядоченную систему ДФУ, так и системы ДФУ в известных упорядочениях, позволяют создавать программные средства пригодные для эффективного применения в системах обработки, хранения и передачи изображений. Их использование целесообразно в том случае, когда критична скорость обработки и передачи данных, например в системах с низкой вычислительной мощностью приемника и передатчика информации, а также при передаче по телефонному каналу или по низкоскоростным каналам связи.
Реализация и внедрение результатов работы. Основные положения работы использованы при выполнении прикладной научно-исследовательской работы АН РТ «Разработка методов решения задач управления развитием систем цифровой обработки информации и совершенствование их алгоритмических средств» (Институт проблем информатики АН РТ, 2006-2008 гг.).
Теоретические и практические результаты диссертационной работы используются в научных исследованиях и разработках ООО «КЭР-Инжиниринг», а также внедрены в учебный процесс по дисциплине «Цифровые методы анализа» на кафедре систем автоматизации и управления технологическими процессами Казанского государственного технологического университета.
На основании результатов диссертационной работы разработана программа по кодированию/декодированию изображений «Image Compressor JPGW», защищенная авторским свидетельством о государственной регистрации программы для ЭВМ № 2009615236.
Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на следующих научных конференциях и семинарах: международная научно-практическая конференция “Инфокоммуникационные технологии глобального информационного общества” (Казань, 2004, 2005, 2007-2009 гг.); межвузовская научно-практическая конференция “Современная торговля: теория, методология и практика” (Казань, 2005-2007 гг.); III-я республиканская научно-техническая конференция “Автоматика и приборостроение” (Казань, 2006 г.); 5-я международная конференция «Авиация и космонавтика-2006» (Москва, 2006 г.); всероссийская научно-техническая конференция “Современные инновационные технологии и оборудование” (Тула, 2006 г.); II-я международная научно-техническая конференция “Тинчуринские чтения” (Казань, 2007 г.); всероссийская научная конференция “Информационные технологии в науке, образовании и производстве” (Казань, 2007 г.); международная конференция студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2008 г.); международная молодежная научная конференция “Туполевские чтения” (Казань, 2008 г.); международная научно-практическая конференция “Радиолокация, навигация и связь”, (Воронеж, 2009 г.); (Ульяновск, 2009 г.); республиканский научный семинар «Методы моделирования» при КГТУ им. А.Н. Туполева, (Казань, 2009 г.).
Публикации. По теме диссертации опубликовано 21 научная работа, включая 4 статьи и 17 тезисов докладов, в том числе 1 статья в журнале, рекомендованном ВАК. Получено 1 авторское свидетельство на программу для ЭВМ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка (157 наименований). Работа содержит 153 страницы машинописного текста, 40 рисунков и 19 таблиц.
Основные показатели эффективности методов сжатия и качества восстановленных изображений
Можно выделить два основных подхода к оценке эффективности методов сжатия. Первый заключается в непосредственном подсчете объема сжатых растровых данных. Примеры таких оценок КС даны в [34,68,83,87] и основаны на таком понятии цифрового сжатия данных, как избыточность.
Пусть Щ и п2 означают число элементов — носителей информации в двух наборах данных, представляющих одну и ту же информацию. Тогда относительная избыточность первого набора данных RD (характеризуемая значением Щ) по отношению ко второму набору может быть определена как где величина CR, обычно называемая КС, есть
В практике СИ в формуле (1.2) определим Щ как размер входного файла и Щ как размер выходного файла. Значения больше 1 означает сжатие, а меньше 1 — расширение. В [34] Щ, Щ определяют как количество бит (или количество координат разложения) исходного и восстановленного изображения.
Другой подход, разработанный и развитый в работах [42,60,97,101], применяется, например для методов с предсказанием и преобразованием. При этом для оценки количества бит, необходимых для кодирования трансформант, используется оценка энтропии. Приведенный подход учитывает особенности алгоритмов, но не учитывает особенности конкретного изображения.
В работе мы в основном используем подход, основанный на непосредственном подсчете объема сжатых растровых данных (1.2).
В настоящее время не найден адекватный критерий оценки потерь качества изображения, а теряется оно постоянно — при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати и, что для нас особенно важно, при архивации с потерями. Широко используются как объективные, так и субъективные критерии оценки потерь качества [28,34,87].
Если степень потери информации может быть выражена как функция исходного и сжатого, а затем восстановленного изображения, то такой подход называют объективным критерием качества изображения.
Пусть X(i,j) — исходное изображение, a X{i,j) - его приближенное, получаемое в результате операций сжатия и последующего восстановления. Тогда среднеквадратичная ошибка определяется как где
Основным недостатком мер является то, что если в результате кодирования произошло несущественное равномерно распределенное по всей области изображения понижение яркости, то они покажут существенное снижение качества, а на практике такое искажение легко компенсируется за счет регулирования яркости устройства отображения. С другой стороны, изображения со «снегом», муаром по этому критерию будут считаться практически не изменившимися. Критерий максимального отклонения от оригинала вычисляется по формуле
Данная мера крайне чувствительна к «биению» отдельных пикселей, то есть во всем изображении может существенно измениться только значение одного пикселя (что практически незаметно для глаза), однако изображение будет сильно испорчено.
Широко используемой величиной считается пиковое отношение сигнал/шум (PSNR). Высокое значение PSNR означает определенную схожесть восстановленного и исходного изображения. где S — количество значимых бит (как правило, 8). В [87] представлена шкала оценивания качества по PSNR (табл. 1.13).
Эта мера аналогична среднеквадратичному отклонению, но пользоваться ей удобнее из-за логарифмического масштаба, что соответствует модели зрения человека.
Лучшей оценкой качества воспроизведения остается визуальная (субъективная) оценка потерь качества. Отличным считается сжатие, при котором невозможно на глаз различить первоначальное и распакованное изображения. Часто дополнительно проводят построение разностного изображения и оценивают его качество визуальным наблюдением. В табл. 1.4 приведен один из вариантов абсолютной шкалы оценивания качества изображений [34].
Синтез разностно-упорядоченной системы дискретных функций Уолша
Предлагаемый метод упорядочения систем ДФУ размерности N = 2n заключается в следующем [47]. Строится разбиение множества порядковых номеров функций Уолша исходной системы I = {0,1,...,JV-1} (2.12) на (я + 1) подмножеств, каждое из которых включает номера функций с одинаковыми дифференциальными порядками. Затем сформированные подмножества располагают в порядке увеличения дифференциальных порядков соответствующих функций, т.е. в итоге получаем множество 3 = {30,3v...J3n}, для которого справедливы следующие соотношения: Очевидно, что множество ./ определяет перестановку функций Уолша в системе Полученная в результате этой перестановки система ДФУ будет характеризоваться тем, что функции в ней располагаются группами в порядке возрастания их дифференциальных порядков.
По этой причине назовем эту систему ДФУ разностно-упорядоченной. Для вектора перестановочной последовательности будем придерживаться обозначения Pn=(pQ,p1,..., pN_x), где pt = j}, і = 0, N -1. Перестановку с использованием этого вектора назовем перестановкой по дифференциальным порядкам базисных функций (кратко D-перестановкой). Рассмотрим упорядочение системы Уолша-Пэли с использованием предложенного метода [48]. Анализ дифференциальных порядков функций Уолша-Пэли показал, что вектор Рп может быть представлен в виде объединения ряда подвекторов: где Р,(0) =(0),P,w =(2 -1),і = й; PJ,k\k = l,n-\, - подвекторы, определяемые рекуррентными соотношениями: Векторы Рп размерности N = 2n,n-l,5, соответствующие перестановочным последовательностям, представлены в табл. 2.1. Здесь сверху подчеркнуты группы коэффициентов четных, а снизу -нечетных дифференциальных порядков. С учетом введенного вектора значений перестановочной последовательности разностно-упорядоченную систему ДФУ {ріад,0 )} оІМОЖНО описать так: где paljyO) - і-я функция Уолша-Пэли. Матричная запись для введенной системы ДФУ имеет следующий вид: где S = [.їу I = =i — матрица -перестановок, элементы которой формируются так: Следует отметить, что представленное выше упорядочение системы ДФУ получено на основе системы Уолша-Пэли. Выбор в качестве базисной системы Уолша-Пэли обусловлен легкостью получения аналитического описания для перестановочной последовательности и матричного соотношения, формирующего предложенное упорядочение системы ДФУ. Различные варианты разностно-упорядоченных систем могут быть получены при выборе в качестве базисной других систем Уолша.
Анализ дифференциальных порядков функций Уолша-Адамара и Уолша-Пэли показал, что вектор значений перестановочной последовательности Рп при выборе в качестве опорных матриц Уолша-Адамара также может быть представлен в виде объединения ряда подвекторов (2.14—2.15) — см. табл. 2.2. На основе полученного вектора значений перестановочной последовательности разностно-упорядоченные системы ДФУ \hddN(i) ) 1 можно описать так
Двухэтапный JPEG — подобный алгоритм сжатия изображений на основе дискретных преобразований Уолша
В работе предлагается алгоритм СИ, основанный на тех же принципах что и JPEG, однако вместо ДКП для обработки компонент цветности в нем используется ДПУ. Отметим, что на сегодняшний день существуют разработки JPEG-подобных алгоритмов на основе ДПУ с КС, превышающим стандартный алгоритм JPEG при высоком качестве изображения [54]. В отличие от алгоритма [54], реализующего традиционный подход к СИ с отбрасыванием нулевых трансформант, в предлагаемом алгоритме используется двухэтапныи подход к СИ, в котором предусматривается дополнительная обработка элементов двумерного спектра Уолша экстраполяционными методами [18,50]. Алгоритм включает в себя следующие шаги: 1. Преобразование цифрового изображения из цветовой системы RGB в цветовую систему YCbCr. Это прямое преобразование можно представить с помощью следующего векторно-матричного соотношения Y 2. Субдискретизация цветовых компонент изображения Cb, Сг. Укрупнение пикселов делается в соотношении [2:1] по горизонтали и вертикали - так называемое укрупнение 2h2v (рис. 3.3). Эта операции не применяется для компоненты яркости 7. 3. Вычисление двумерного прямого ДОП компонент изображения, разбитых на блоки размером 8x8 пикселей. Для компоненты яркости Y выполняется ДКП. Отметим, что ДКП обеспечивает упаковку наибольшего количества информации в наименьшее количество коэффициентов. В упрощенном виде прямое и обратное ДКП блока f[i,j] при /Y = 8 можно представить следующим образом: Для компонент цветности СЬ, Сг выполняется ДПУ. Формулы прямого и обратного ДПУ при N = 8 записываются в виде где H{i,j,u,v) - матрица ДПУ в используемом упорядочении ДФУ (2.1, 2.2, 2.3,2.12).
Для вычисления ДПУ в различных упорядочениях [79] и ДКП используем алгоритмы быстрых преобразований [66,107], а также алгоритмы, предложенные в п. 2.5. 4. Экстраполяция трансформант Уолша и вычисление ошибок предсказания трансформант, охваченных парциальными процедурами экстраполяции. Выполняется для компонент цветности. На рис. 3.4 показаны схемы формирования групп трансформант Уолша-Качмажа, охваченных процедурами экстраполяции. Процедуры частичной экстраполяции проводим в пределах групп дифференциальных порядков /=1,2. Восстановление спектральных коэффициентов ДПУ из значащих трансформант и ошибок предсказания трансформант Уолша (охваченных процедурами экстраполяции) для элементов подгрупп дифференциального порядка d=\ выполняется по формулам: а) подгруппа 1: b) подгруппа 2: 5. Квантование спектра ДКП и полученных значащих трансформант и ошибок предсказания трансформант Уолша, охваченных экстраполяционными процедурами [16].
Каждый элемент спектра равномерно квантуется независимо от других с округлением до целого. В стандарт JPEG включены рекомендованные матрицы квантования, построенные на основе опытных данных, которые дают очень хорошее качество на любых изображениях. Для преобразования ДКП матрица квантования рассчитывается по следующей формуле: где q - коэффициент задаваемый пользователем. При преобразовании ДПУ потребовалось применить матрицу JPEG, поэлементно деленную на определенный коэффициент [31]: Это обусловлено тем, что данное преобразование имеет меньшую точность по сравнению с преобразованием ДКП. На этом шаге происходит потеря информация. Матрицы для большего или меньшего КС получают путем умножения матриц квантования на коэффициент q, подбираемый пользователем экспериментально. 6. Переводим матрицу размерности 8x8 в 64-элементный вектор при помощи «зигзаг»-сканирования (рис. 3.5). Таким образом, основная часть нулевых элементов спектра, оказывается сосредоточенной в конце 64-элементного вектора. 7. Обратимая упаковка векторов с помощью алгоритма группового кодирования RLE64 [129]. Сжатие сводится к тому, что на каждой итерации алгоритма определяется длина максимальной последовательности ненулевых байт (не больше 15) и длина следующей за ней последовательности нулевых байт (не больше 15). В выходной поток выдается контрольный байт, в четырех младших битах содержащий длину первой последовательности, а в старших — длину второй.
После этого в выходной поток выдается обнаруженная последовательность ненулевых байт. Если до конца блока остались одни нули, алгоритм выдает в выходной поток нуль и для данного блока завершает выполнение. 8. Сжатие полученных векторов методом Хаффмана с фиксированной таблицей [87]. Вместо того чтобы кодировать все символы одинаковым числом бит, будем кодировать символы, которые встречаются чаще, меньшим числом бит, чем те, которые встречаются реже. Таблицы кодов Хаффмана должен строить сам разработчик системы сжатия, поэтому эти таблицы кодов Хаффмана необходимо помещать в заголовок выходных данных системы сжатия. В стандарт JPEG включены рекомендованные таблицы кодов Хаффмана [66,87]. Представленный алгоритм является симметричным. Каждому шагу сжатия соответствует шаг при декомпрессии, при которой выполняются обратные операции. За исключением пятого шага сжатия все операции являются обратимыми. При этом алгоритм будет обладать достаточно хорошими скоростными свойствами, так как дополнительные шаги можно реализовать в целочисленной арифметике с использованием лишь операций двоичного сдвига и вычитания.
Программная реализация кодер-декодера сжатия цифровых изображений
Проведем анализ эффективности двухэтапных алгоритмов СИ с экстраполяцией трансформант Уолша с использованием КС по числу координат разложения в сравнении с традиционным алгоритмом СИ, основанном на отбрасывании незначащих трансформант Уолша [50]. Анализ эффективности алгоритма СИ проводится в два этапа. На первом этапе изображение делится на блоки размерности 8x8 и определяются относительные частоты pt, / = 0,7 появления блоков, описываемых двумерными дискретными степенными полиномами. При этом величины рп і-0,6, определяются как относительные частоты появления блоков, описываемых полиномами /-го (/=0,6) порядка, а р1 - как относительная частота появления блоков, описываемых полиномами порядков от 7 до 14. На втором этапе рассчитывается коэффициент выигрыша в сжатии (KB) по числу координат разложения. Отметим, что максимальный порядок двумерного степенного полинома, описывающего блок изображения размерности 8x8, равен 14, а максимальный дифференциальный порядок двумерных ДФУ d=6. В дальнейшем блок изображения, включенный в группу с относительной частотой появления ph будем называть блоком изображения /-го вида. Для определения относительных частот р,, / = 0,7, целесообразно использовать разложение изображения в двумерном базисе дискретных полиномов Чебышева [71].
В этом случае легко определяется максимальная степень полинома, описывающего блок изображения. Его величина определяется как максимальный номер ряда элементов матрицы трансформант /тах, расположенных на позициях, параллельных обратной диагонали матрицы, содержащего хотя бы один ненулевой элемент: где F(i,j) - трансформанта с индексом (i,j) в двумерном базисе дискретных полиномов Чебышева.
Представим выражения для вычисления КС анализируемых алгоритмов СИ, основанных на ДПУ, при нулевой погрешности восстановления изображений. 1. Традиционный алгоритм СИ с отбрасыванием нулевых трансформант Уолша (алгоритм А1): где С6 - биноминальный коэффициент (число сочетаний из 6 по j); Sj - число ненулевых трансформант блоков изображения і-го вида. 2. Алгоритм СИ с полной экстраполяцией трансформант Уолша (алгоритм А2): где ki - количество значащих трансформант Уолша для блоков z-го вида: где S_2 = S_, = 0; д — символ Кронекера; Lt - количество трансформант-представителей /-го дифференциального порядка: 3. Алгоритм СИ с частичной экстраполяцией трансформант Уолша не выше второго дифференциального порядка (алгоритм A3): Здесь величина 12J,, определяет число обнуленных трансформант Уолша второго дифференциального порядка за счет экстраполяции по соответствующим транс формантам-представителям. KB по сжатию по числу координат разложения можно записать в виде соотношения КС традиционного и предложенного алгоритмов: С точки зрения практической реализации наибольший интерес представляет алгоритм A3, поэтому проведем более детальный анализ эффективности традиционного алгоритма А1 СИ и алгоритма A3, при котором процедурами экстраполяции охвачены лишь трансформанты Уолша первого и второго дифференциальных порядков. Запишем выражение для расчета KB по сжатию по числу координат разложения в следующем виде:
