Содержание к диссертации
Введение
ГЛАВА 1- Фрактальное сжатие изображений, его особенности и обсласти применения 10
Введение 10
1.1, Математические основы фрактального сжатия изображений 11
1.2, Фрактальное сжатие изображений в градациях серого 20
13, Методы повышения временной эффективности фрактального алгоритма 27
1.4, Фрактальное сжатие цветных изображений 51
1.5. Особенности и области применения фрактального сжатая 52
Заключение 56
ГЛАВА 2. Фрактальное сжатие изображений с применением поиска ближайшего соседнео элемента 57
Введение 57
2.1. Математические основы фрактального сжатия с использованием ближайшего соседнего элемента 57
2.2. Современные методы поиска ближайшего соседнего элемента в многомерном метрическом пространстве 61
Заключение 71
ГЛАВА 3. Адаптация пространственно-чувствительного хеширования для создания эффективных методов фрактального сжатия изображений 72
Введение 72
3.1. Понятие пространственно-чувствительного хеширования 72
3.2. Применение пространственно-чувствительного хеширования для решения задачи фрактального сжатая изображений 73
3.3. Адаптация пространственно-чувствительных хеш-функций к фрактальному сжатию изображений на основе р-устойчивых распределений 75
3.4, Преимущества использования метода пространственно-чувствительного хеширования при фрактальном сжатии
изображений 78
Заключение 83
ГЛАВА 4, Программная реализация применение и эксплуатация эффективного алгоритма фрактального сжатия изображений 84
введение 84
4.1. Описание алгоритма фрактального сжатия при помощи прост ранственно чувствительного хеширования (FracLSH) 84
4.2, Оценка временной эффективности алгоритма FracLSH 91
4.3, Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок 92
4.4. Сравнение FracLSH с другими современными алгоритмами сжатия изображений 102
Заключение 106
Заключение 107
Библиографический список
- Фрактальное сжатие изображений в градациях серого
- Современные методы поиска ближайшего соседнего элемента в многомерном метрическом пространстве
- Применение пространственно-чувствительного хеширования для решения задачи фрактального сжатая изображений
- Оценка временной эффективности алгоритма FracLSH
Введение к работе
Актуальность темы
Актуальность исследований в области повышения временной эффективности алгоритмов фрактального сжатия изображений определяется существующими в настоящее время тенденциями к применению таких алгоритмов дая сжатия статических изображений и динамической видеоинформации. Именно фрактальные алгоритмы потенциально способны обеспечить наилучшее соотношение степени сжатия и качества восстановленного изображения, что важно в системах подготовки мультимедиа информации к тиражированию. Однако, существующие реализации таких алгоритмов весьма требовательны к ресурсам вычислительной системы, что несколько сужает область их применения» К алгоритмам и системам сжатия видеоинформации предъявляется ряд достаточно жестких требований по временной эффективности, обусловленных комфортностью работы с программными системами, в которых применяются данные алгоритмы, а также необходимостью использования сжатия. Решение этой задачи не может опираться только на возрастающие мощностью современных компьютеров и связано с разработкой эффективных алгоритмов сжатая.
В связи с этим разработка эффективных алгоритмов фрактального сжатия изображений представляет собой актуатьную задачу в области создания эффективного математического и программного обеспечения вычислительных машин, комплексов и компьютерных сетей.
Состояние проблемы
При разработке, исследовании и развитии методов фрактального сжатия изображений охватывается широкий круг проблем связанных с повышением временной эффективности методов фрактального сжатия изображений, их алгоритмического обеспечения, оценки качества алгоритмов
сжатия и восстановления растровых изображений, в исследование и развитие которых внесли значительных вклад российские и зарубежные ученые: Н. А. Ваганова, Д. С. Ватолин, Н.Б. Новинский, В.В. Нечепаев, М Barnsley, Т. Bedford, J. Bentley, A. Bogdan, L. Chen, R Dekking, Y. Fisher, J. R. Finkel, Friedman, M, Gharavi-Alkhansari, R, Hamzaoui, J. Hutchinson, A. Jacquin, W. Kinser, C. Lee, S, Leps0y, H. Lin, B. Mandelbrot, H. Meadows, G. 0Іеп, D. Saupe, A, Venetsanopoulos, L. Wall, и др.
Большинство современных публикаций по тематике исследования алгоритмов фрактального сжатия посвящены повышению временной эффективности фрактального кодирования. Несмотря на интенсивные исследования в области классической теории алгоритмов фрактального сжатия растровых изображений некоторые вопросы остаются нерешенными, В первую очередь это касается вопроса поиска эффективных методов построения систем итерируемых функций для заданного входного изображения. Отметим в данном контексте работы Д. С Ватолина (Московский государственный университет) по методам оптимизации алгоритмов фрактального сжатия статических растровых изображений и Н. А, Вагановой (Институт вычислительной математики и математической геофизики) по методам фрактального сжатия динамических изображений. Большой вклад в разработку методов обработки растровых изображений внесли работы, выполненные в институте систем обработки изображений РАН, в частности работы В. В. Сергеева и В, А. Сойфера.
Тем не менее, большинство публикаций по тематике исследования методов фрактального сжатия изображений свидетельствуют о том, что в настоящее время задача построения эффективних по времени алгоритмов фрактального сжатия растрового изображения остается актуальной с точки зрения практических характеристик их программных реализаций.
Объект исследования
Объектами исследования диссертационной работы являются вычислительные (компьютерные) алгоритмы фрактального сжатия изображений в аспекте их временной эффективности при ограничениях, налагаемых особенностями и спецификой их применения в разрабатываемых программных средствах и системах.
Целью работы является повышение временной эффективности компонентов алгоритмического обеспечения программных средств фрактального сжатия изображений за счет разработки эффективных методов сопоставления доменпо-ранговых областей па основе метода пространственно чувствительного хеширования.
Научная новизна диссертации заключается в:
Обосновано применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение (V,c,)-NN задачи) в применении к фрактальному сжатию изображений.
Предложен способ построения семейства хеш-функций, адаптированных к особенностям задачи фрактального сжатия изображений.
Разработан ресурсно-эффективный комбинированный алгоритм фрактального сжатия статических изображений.
Практическая ценность результатов работы заключается в возможности решения:
— задачи повышения временной эффективности алгоритмического обеспечения фрактального сжатия изображений с использованием разработанного метода фрактального сжатия изображений на основе применения модифицированного метода приближенного решения задачи поиска
ближайшего соседнего элемента при помощи пространственно-чувствительного хеширования;
задачи разработки комбинированных алгоритмов фрактального сжатия изображений, включающих в себя алгоритмы, рациональные по различным требованиям к качеству декодированного изображения и времени сжатия;
задачи экспериментального исследования временной эффективности алгоритмов фрактатьного сжатия изображений с использованием разработанных программных средств.
Основные результаты, выносимые на защиту:
1 - Применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение (v,c)-NN задачи) в применении к фрактальному сжатию изображений»
2. Способ построения семейства хеш-функций, адаптированных к
фрактальному сжатия изображений.
Асимптотические оценки временной эффективности разработан^ ного алгоритма фрактального сжатия изображений.
Ресурсно-эффективный комбинированный алгоритм фрактального сжатия статических изображений, разработанный на основе предложенных методов.
Апробация работы
Основные положения и результаты диссертационной работы докладывались на всероссийских конференциях и семинарах: I Всероссийский семинар аспирантов, 2006 г,; Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2005 г.; VIII Всероссийской научно-технической конференции «Новые информационные технологии», Москва,
2005 г,; VIII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2005 г.;
УСЛОВНЫЕ ОБОЗНАЧЕНИЯ
Rm — ранговый блок с номером т, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 9Г,
Dk — ранговый блок с номером к, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 9Г.
d(y) — функция, вычисляющая расстояние между своими операндами представляющими точки в полном метрическом пространстве.
s — коэффициент масштабирования (scaling).
о —смещение (offset).
w(') — сжимающее (как правило афинное) преобразование.
/(хзУ) —изображение, рассматриваемое как вещественная функция,
Щп>Ц) — функция, вычисляющая ошибку приближения (расстояние, между ранговым и доменным блоками.
Фрактальное сжатие изображений в градациях серого
Изображение, такое как известный фрактальный папоротник, может быть воспроизведено с помощью относительно прострой системы итерируемых функций, так как этот вид обладает свойством глобального самоподобия. Это значит, что целое изображение состоит из уменьшенных копий его самого или его частей. Увеличивая такое изображение можно наблюдать одну и ту же степень детализации независимо от разрешения. Кроме того, изображение такого типа — это двоичное изображение, то есть каждый его пиксел может быть представлен единицей или нулем. Реальные изображения не обладают свойством глобального самоподобия. Кроме того, реальные изображения не являются двоичными, каждый пиксел принадлежит диапазону значений (в градациях серого) или вектору значений (в цвете). Дня того, чтобы представить такое изображение как аттрактор итерационной очевидне, ігам необходим способ построит такую систему функций в автоматическом рижіше,
В этом ртдшж рзсшїїтрйвдш ся шктротаїш и реализация тагах систш, шшръа: могут быть исполь ювшы во фрактальном кодировании произвольных изображнш в градщях серого»
Определим пространство F вещественных функций интегрируемых с квадратом на I2 с введенной метрикой. Тогда пространство F - полное, и в нем выполняется теорема о сжимающих отображениях. Изображения, рассматриваемые в данной диссертации - это цифровые изображения, то есть пхт матрица значений \ffJ\9i = \9...9nt / = 1,..., , где /и= f{xi y3) Таким образом, это матрица фиксированных значений функции f(x y)f взятых в точках (хпУі) В этом случае говорят о среднеквадратическойметрике (от rms - root mean square):
Во фрактальном сжатии изображений используются IFS специального вида, а именно системы итерируемых кусочно-определенных функций (partitioned iterated function system - PIFS). PIFS состоит из полного метрического пространства X, набора подобластей Д сХ, = 1,„.,я и набора сжимающих отображений wt Пусть wt(x,y) это афинное преобразование, переводящее в себя единичный квадрат: I2 - I2, или, другими словами
Для некоторой матрицы Aj размером 2x2 и вектора Ь. размером 2x1. Пусть Dk сі2 - некоторая подобласть единичного квадрата I2 и пусть Rm— область значений преобразования wJ9 действующего на множестве Dk+ так что щ(Ок)- Rm. Теперь можно определить отображение w,: F -» Fs действующее на изображение f{xty)t в виде -i при условии, что Щ обратимо и (x,y)eRm. Константа st расширяет или сужает диапазон значений функции Л или, для изображений в градациях серого, управляет контрастностью. Аналогично, константа о( увеличивает или уменьшает значения градаций серого, или управляет яркостью. Преобразование wr называется пространственной составляющей преобразования wr Преобразование (1.2.2) - это базовое афинное преобразование изображений в градациях серого, которое наиболее часто используется для фрактального сжатия, Для того, чтобы отображение и; :F- F являлось сжатием требуется выполнение условия для некоторого s, 0 s 1, где d{w) - это метрика, заданная выражением (1.2.1). Используя формулу замены переменной в кратном интеграле, получим йгШх) Ш H(fd y)-4fi){ y)t &dy = = .J detAjJy; );) /2(x,7)f 5j jdetA]l (y;,/2) где Aj — матрица преобразования wf detА — определитель А( и s{ — коэффициент сжатия. Чтобы преобразование было сжатием, достаточно выполнения условия 5/j- detAJ l (1.2-3)
В частности, коэффициент сжатия должен быть по модулю больше единицы: к, 1. Тогда пространственная составляющая wi будет являться сжатием с коэффициентом сжатия, достаточно маленьким для того, чтобы выполнялось (1.2.3).
Разобьем единичный квадрат I2 на множество ранговых блоков {Rm} которые образуют покрытие Iі: Пусть #,— PIFS вида Дня некоторого множества доменных блоков (доменов — domains) Dk с I2 (блоки Dk могут перекрываться и могут не полностью перекрывать I2).
Для каждого iv, определим соответствующее сжатие Щ на пространстве изображений F: выбирая sf так чтобы Щ было сжатием. Теперь определим W :F- F следующим образом W{f)(x,y) = wAf)(x,y) доя (x9y)sRM
В силу того, что ранговые блоки Rm покрывают I2, W определено для всех (х,у) из I2 и, следовательно, (/) является изображением. Так как каждое отображение щ является сжатием, то W является сжатием на F Поэтому, согласно теореме о сжимающих отображениях, W имеет единственную неподвижную точку Л є Р, удовлетворяющую
Современные методы поиска ближайшего соседнего элемента в многомерном метрическом пространстве
Проблема поиска ближайшего соседнего элемента заключается в том, чтобы для данного набора доменных блоков построить такуго структуру данных, чтобы для данного рангового блока Rm можно было быстро найти ближайший к Rm доменный блок.
Данная проблема хорошо изучена в течение длительного времени, и имеет множество названий в разнообразной специальной литературе. В одной из самых ранних попыток предложить решение для данной проблемы (как описано Д. Кнутом в [81]} она называлась задача почтового агентства. В другой работе задача называлась поиск файла по ближайшему совпадению [52]. В литературе по разработке баз данных данная задача может называться проблема построения индекса для поиска похожих элементов [72], В теории информации задача известна как проблема векторного квантовангт [86,70], В теории распознавания паттернов (или статистике), она может называться проблема построения быстрого классификатора ближайшего соседа [65, 60].
Результаты, описанные в данной главе, были предложены для решения пробелмы поиска ближайшего соседнего элемента в контексте большого количества различных алгоритмов и структур данных. Стоит заметить, что существует большое количество таких алгоритмов, поэтому в рамках данной работы рассмотрены основные методы поиска ближайшего соседнего элемента, на которых строятся уже конкретные реализации. Термин «временно-эффективный» метод в данный главе не очень конкретен, но в основном касается не очень больших структур данных, но позволяющих быстро обрабатывать запросы, где «не очень большие» означает 0{п) и «быстро» означает о(п) в то время как число доменных блоков п -» х.
Свойства метрических пространств позволяют сделать некоторые базовые наблюдения, которые могут привести к существенному повышению временной эффективности алгоритмов поиска ближайшего соседнего элемента. Эти наблюдения следуют из аксиомы треугольника, которая позволяет определить границы расстояния, которое мы еще не вычислили, скажем d(Rm9Dk)9 из двух расстояний которые мы уже знаем, скажем d(Rm,DkX) и d(DkiDk}). Имеют место следующие простые свойства: Для Rm,DktDkl є X, любого значения г,илюбого РаХ, 3. Если d(DklfDk) d(Dkl9Rm) + r или d(DkUDk) d(DkURJ-r, то d(Rm,Dk) r; 4.Если d(DkX,Dk) 2d{DkURm), то d(Rn9Dk) d{RnfDkl). Доказательство: Применим неравенство треугольника тремя возможными способами, d(Rm,Dk)ud(RmiDk{) + d{DkX,Dk) d{Dkl,D&) d(Dkt,Rm) + d(Rm,Dk) d{Rm,Dkx)ud{Rm,Dk) + d{Dk,DH)
Первое из этих неравенств является верхней границей для d(Rm,Dk) в утверждении (1), и остальные два дают нижнюю границу в (1). Утверждение (2) следует из (1), две части утверждения (3) следуют из последних двух неравенств, соответственно, и утверждение (4) следует из утверждения (3) с r = d(DtvRm).
Значение d {RmtDk)9 которое является нижней границей для d(RmtD&), используется в методе AESA, как описано ниже.
Вышеописанные краницы из аксиомы треугольника дают способ избежать вычисления расстояния от рангового блока Rm до многих доменных блоков, рассмотрев границы на их расстояния, которые позволяют отбросить доменные блоки как не являющиеся ближайшими.
Например, рассмотрим следующую простую схему. Дня каждого доменного блока Dk создадим список доменных блоков в порядке возрастания расстояния к Dk,
Для того, чтобы найти ближайший доменных блок к данному ранговому блок Rm, выберем некоторый доменный блок Dc как начальный кандидат в ближайшие соседы. Вычислим d(Dc,Rm) и пройдем по списку для Dci вычисляя расстояния до доменных блоков в списке. Если какой-нибудь доменный блок Ds ближе к Rm чем Dc, установим с \=s. Теперь повторим всю процедуру, используя новый Ц, и его список, и так далее. Предположим, что мы прошли по данному списку до доменного блока Ds такого, что d{Dc Ds) 2d{Dc,Rm),
Применение пространственно-чувствительного хеширования для решения задачи фрактального сжатая изображений
Для того, чтобы пространственно-чувствительная функция хеширования была полезной с точки зрения применимости к фрактальному сжатию изображений, она должна удовлетворять неравенствам р\ р2 и
В специальной литературе принято обозначать задачу приближенного поиска соседнего элемента как f cJ-NN задачу, при этом гг=т и г2=с-т. Покажем, как пространственно-чувствительные функции могут быть использованы для решения fr,cJ-NN задачи при фрактальном сжатии: для данного семейства Я хэш-функций, обладающих параметрами (г\ гг РиРг) увеличим разрыв между «высокой» вероятностью Р\ и «низкой» вероятностью Рг путем соединения нескольких функций. В частности, для параметра К, значение которого будет установлено ниже, определим семейство функций F = {g: S - U } так что g(Db) = ( (0 ),,.., (0 % где fyetf- Для целого числа L выберем L функций givigL из , независимо и равномерно, случайным образом. Во время шага предварительных вычислений, сохраним каждую проекцию доменного блока D eS в наборе gj(Dk\ для каждого / = 1,...,. Так как общее число таких множеств может быть велико, оставим только непустые наборы путем возврата к классическому хешированию. Дпя того чтобы обработать ранговый блок Rmj производим поиск среди всех множеств gx(R \, gL(R ). Так как возможно (хотя и маловероятно) что общее количество доменов, сохраненных в этих множествах велико, то поиск домена прерывается после нахождения 3L элементов (включая дубликаты). Пусть Ц1,..,,!)/" — найденные элементы.
Для каждого домена 0} t возвращаем ответ «ДА» (т.е. данный домен является потенциальным кандидатом построения преобразования в ранговый блок Rm), если Д t є B(R ,r2), иначе возвращаем ответ «НЕТ».
Параметры К и L выбираются так, чтобы гарантировать, что следующие два свойства выполняются с заданной вероятностью: І.Если существует DlsB(R 9rt), то gj(Dl) = gj(R ) для некоторого У = 1..Х. 2. Общее количество коллизий Rm с точками из S — B(Dk ,г2) меньше чем Зі (параметр определен эмпирическим путем в [89]) то есть: i\(S-B(Ditr2))ngf(gi{D )\ 3L
Если выполняются оба свойства, то алгоритм является корректным. Отсюда следует ([76] теорема 5), что если установить К \о {\! р2\ и = , где fi=mtr (3-2Л) то свойства (1) и (2) выполняются с постоянной вероятностью. Таким образом, получаем следующую теорему [89], которая касается зависимости эффективности решения (т, cJ-NN задачи при фрактальном сжатии изображений от параметров LSH:
Предположим, существует (г, т,р!,/?2)-чувствительное семейство функций хеширования Я дая меры расстояния d(y)a Тогда существует алгоритм для решения (г ,c)-NN задачи для меры (v), который использует 0{dnd+nd p) памяти, с временем обработки одного запроса определяемым 0{п/) вычислений расстояния и 0{n/\og([lp2)-nd) вычислений хеш-функций из Я, где Р определен как (3.2.1),
Устойчивые распределения [117] определяются как пределы нормализованных сумм независимых равномерно распределенных случайных переменных (ниже дано альтернативное определение). Наиболее известный пример устойчивого распределения — это нормальное (гауссово) распределение. Однако, класс таких распределений является значительно более широким. Распределение № над 9? называется -устойчивым, если существует Р 0 такое, что для любых d действительных чисел v]5,..,v и переменных Xu.4fXd с распределением М, случайная переменная Х Л имеет такое же распределение, как и переменная (Е,&\Р)х,рХ, где X— случайная переменная с распределением №. Известно [117], что устойчивые распределения существуют для любого рє(0,2]. В частности гауссово (нормальное) распределение №а определенное как функция плотности вероятности VZTT является 2-устойчивым. Заметим, что с практической точки зрения, несмотря на недостаток закрытых форм функций распределения плотности, известно [54], что можно создать /т-устойчивую случайную переменную из двух независимых случайных переменных, равномерно распределенных на интервале [0,1].
Используя jT-устойчивые распределения, построим семейство хэш-функций Я, адаптированное к фрактальному сжатию изображений. Интуитивно, семейство хеш-функций должно быть пространственно-чувствительным, т.е. если два вектора R ,D близки друг к другу (значение Rm -&к относительно невелико), то они должны с большой вероятностью вызывать коллизию (иметь одно и то же значение хеш-функции) и, если они расположены далеко друг от друга, то вероятность коллизии должна быть мала. Пусть а — вектор размерности d, элементы которого выбираются независимо из / -устойчивого распределения.
Скалярное произведение (а #и) проецирует каждый вектор на множество действительных чисел. Из / -устойчивости следует, что для двух векторов R Db расстояние между их проекциями \U,R j-U9Dk распределено К-ії как - , где X — это случайная переменная, выбранная из р р устойчивого распределения. Если «разделить» множество действительных чисел на подмножества равного размера У И определить значение хеш-функции для вектора в зависимости от того, на какое подмножество он проецируется, то интуитивно ясно, что такая хеш-функция будет пространственно чувствительна в описанном выше смысле.
Оценка временной эффективности алгоритма FracLSH
Рассмотрим формальный подход к миогофакторной оценке алгоритмов сжатия/восстановления растровых изображений. Пусть D — исходное изображение, состоящее из пхп = н2 пикселей, при этом если один пиксель кодируется пр битами, то изображение D занимает объем 0 = пэ пр бит. Обозначим через Д. алгоритм сжатия изображения, переводящий исходное изображение в сжатое: где Dc — сжатое изображение, причем Dr = ffi бит. Стандартно степень сжатия изображения 5" определяется при фиксированном значении яр следующим образом S(n,m) = - . (4.3.1.1) т Обозначим через Аг парный с Д. алгоритм восстановления изображения: к где D — восстановленное изображение, возможно с потерей качества. Введем в рассмотрение функцию ошибки восстановления, и обозначим ее через E(D,D ). (4.3.1.2) Потребуем выполнение следующих очевидных условий; E(D,D) = 0; E(D,M!Dn:d2) = \, (4.3.1.3) где Dtiiii — изображение, в котором значение каждого пикселя задано случайно из допустимого диапазона равномерным генератором псевдослучай-пых чисел. Конкретные варианты задания функции E(D,Dr) будут рассмотрены ниже.
Пусть так же известны функции трудоемкости алгоритмов Лс и Аг в базовых операциях приятой модели вычислений — Д (-О) и Д (АО соответственно. В классе изображений реальной области применения мы можем рассматривать средние трудоемкости этих алгоритмов DeG„ / („) = ЕВД-Д( Д D De9De D\ (4315) где Grt — класс изображений области применения с размером л х и пикселей, С(М — класс сжатых изображений, соответствующих классу Gn со средним объемом tfi, a P\D) — вероятность поступления изображения D на вход алгоритма сжатия. Мы считаем, что средняя трудоемкость восстановления есть функция линейного размера восстановленного изображения, поскольку алгоритм Лґ имеет на входе образы изображений из Gn.
Отметим, что реально средние трудоемкости могут быть определены экспериментальным путем, на основе результатов исследования алгоритмов по выборке изображений, характерной для данной области применения. Поскольку нас интересует поведение пары алгоритмов сжатия/восстановления не на конкретном изображении , а на классе изображений GH? то целесообразно рассматривать среднюю оценку качества восстановления изображения Е{п) и среднюю степень сжатия изображения S(n), Эти оценки определяются соответствующим усреднением по изображениям класса GH значений, определяемых по формулам (4.3.1.1) и (4.3Л.2). Отметим, что средняя оценка качества восстановленного изображения Е(п) не зависит от среднего размера сжатого изображения в силу формулы (4.3Л.2), а оценка S(n) не зависит от значения w в силу усреднения по изображениям класса GH й
Обозначим через A = (AciAr) упорядоченную пару алгоритмов сжатия/восстановления изображений. Тогда, с учетом введенных обозначений, формальная оценка качества парно-связанных алгоритмов сжатия/восстановления изображения — Ас и Д. в общем виде есть функция от степени сжатия, качества восстановленного изображения и трудоемкостей этих алгоритмов QAn) = QA (n)Mn\JA{n)JA{n)). (4.3.1.6)
Мы предлагаем использовать именно трудоемкости алгоритмов, а не временные оценки программных реализаций, поскольку речь идет об оценке качества алгоритмов, а не программных средств, функционирующих на определенных компьютерах. Отметим, что представляющие практический интерес временные оценки программных реализаций алгоритмов могут быть прогнозированы на основе функции трудоемкости по известным методикам (см., например, [89]).
Очевидно, что проблемная область применения алгоритмов сжатия/восстановления растровых изображений может быть ограничена некоторым сегментом размерностей — ие[«д,л]э где Щ9пЕ — граничные значения размера изображений, определенных на области применения G. При этом сама область применения G есть объединение классов изображений (J„, где п = пВ9...9пЕ .
Формально оценка качества парно связанных алгоритмов сжатия/восстановления должна быть построена таким образом, чтобы лучшие парно связанные алгоритмы имели бы большую количественную оценку по нормированным показателям. С этой целью введем в рассмотрение следующие нормированные показатели:
Похожие диссертации на Математическое и программное обеспечение методов повышения временной эффективности фрактального сжатия изображений
