Содержание к диссертации
Введение
2 Фракталы 23
2.1 Основные понятия и определения 23
2.2 Аппроксимация множеств 24
2.3 Фрактальное представление монохромных изображений 27
2.4 Численный алгоритм фрактального сжатия монохромного изображения 29
3 Методы повышения быстродействия фрактального сжатия 34
3.1 Предварительная классификация фрагментов изображения 34
3.2 Использование преобразования Мерсенна 39
3.3 Использование многопроцессорной вычислительной техники 44
4 Применение всплесков в задаче фрактального сжатия 53
4.1 Кратномасштабный анализ 53
4.2 Всплеск-фрактальное преобразование 56
4.3 Модифицированный метод всплеск-фрактального сжатия 57
5 Поиск параметров IFS для бинарных изображений 63
Заключение 69
Список литературы 70
- Фрактальное представление монохромных изображений
- Использование преобразования Мерсенна
- Использование многопроцессорной вычислительной техники
- Всплеск-фрактальное преобразование
Введение к работе
Актуальность темы
Современные информационные технологии предполагают передачу и хранение больших объемов данных. Значительную часть передаваемых данных составляют графические изображения и видеоинформация. В связи с этим важную роль играют методы сжатия (т.е. компактного описания) графических изображений. Под монохромным графическим изображением будем понимать матрицу целых чисел X = {^tj}"7=om~ » xij — 0,...,26 — 1. Каждый элемент матрицы X определяет интенсивность свечения графического элемента (пиксела). Нулевое значение элемента соответствует чёрному цвету, а значение (2Ь — 1) — белому. Параметр Ь называется глубиной цвета и определяет количество информации, необходимое для хранения значения одного элемента. Таким образом, для хранения всего изображения X необходимо т-П'Ь бит памяти.
Если Ь = 1, такое изображение называется бинарным, т.е. в нём могут быть графические элементы только чёрного и белого цвета. Бинарное изображение также можно представить как характеристическую функцию компактного множества из R2.
В цветном (многоканальном) изображении каждый графический элемент представляется в виде трех- или четырехмерного вектора. В этом случае каждая цветовая составляющая эквивалентна отдельному монохромному изображению и обрабатывается независимо.
Коэффициентом сжатия называется отношение количества информации, необходимой для хранения исходного (несжатого) изображения к количеству информации, требуемого для представления того лее изображения в компактной форме. Различают два вида сжатия: сжатие без потерь и сжатие с потерями.
Сжатие без потерь также называется архивированием или упаковкой и используется не только при хранении изображений (форматы GIF, PCX), но и вообще произвольных данных (например текста или программных кодов). Восстановленная информация абсолютно идентична сжимаемой. Коэффициент такого сжатия обычно не превышает 2.5 - 3.
Как видно из названия, сжатие с потерями предполагает потерю части информации при сжатии и последующем восстановлении. Использование методов сжатия с потерями ограничивается объекта-
ми, где такие потери допустимы (обработка графической, звуковой информации и т.д.). Для оценки качества восстановления используют величину PSNR (peak signal-to-noise ratio, предельное отношение сигнал-шум), измеряемую в дБ:
n— 1,т—1
KPSNR(X,Y) = -WlS ;'Г^. (2ь _ 1)2 [ДВ], (1-1)
где X и Y - соответственно исходное и восстановленное изображения. Качество восстановления, как правило, находится в обратной зависимости от коэффициента сжатия. Т.е. коэффициент сжатия ограничен требуемым качеством восстановления, и его значение может достигать сотни и более. В данной работе рассматриваются лишь методы сжатия с потерями.
В настоящее время для сжатия численной информации используют методы аппроксимации функций полиномами [37], рациональными дробями [5], экспонентами [32], сплайнами [26], всплесками. Одним из самых распространенных алгоритмов сжатия с потерями фотогорафических изображений является JPEG (Joint Photographic Expert Group - объединенная группа экспертов по фотографии). Этот алгоритм [31] основан на разбиении исходного изображения на фрагменты размером 8x8 пикселов. Для каждого фрагмента выполняется двумерное дискретное косинус-преобразование (ДКП) [1]. Далее происходит квантование по уровню спектра ДКП, что и определяет потери при сжатии. Коэффициенты квантования определяют, какое количество данных теряется и, следовательно, коэффициент сжатия и качество восстановленного изображения. Для получения окончательного результата выходные данные квантования без потерь упаковываются с использованием какого-либо статистического метода кодирования. Таким методом может быть арифметическое кодирования, либо кодирования по методу Хаффмана [8], [20].
Фрактальные методы сжатия изображений позволяют не только компактно хранить данные, но и воспроизводить данное изображение практически при любом увеличении. Возможность фрактального увеличения обеспечивается тем, что в таких алгоритмах запоминаются не отдельные элементы изображения, а соотношения между различными фрагментами.
Самое общее понятие фрактала можно дать следующим образом: это такой объект, который при сколь угодно большом увеличении (рассмотрении все меньших фрагментов) сохраняет неизменной степень своей детализации (визуальной сложности). Классический пример фрактала — береговая линия. Если выбрать некоторый участок берегового контура, например, на карте с мелким масштабом, а затем увеличивать этот участок (использовать карты со все более крупным масштабом), то можно увидеть, как появляются все новые и новые детали. При больших увеличениях географических карт будет недостаточно, и придется воспользоваться фотографиями. Камни и песок, составляющие береговую линию, издали кажутся гладкими, но пр дальнейшем увеличении и они будут состоять из различных "шероховатостей". Ни при каком увеличении не будет наблюдаться тенденции к сглаживанию береговой линии. Фрактальные методы сжатия основаны на предположении Б. Мандельброта о глобальной "самопохожести" (масштабной инвариантности) многих естественных объектов [17]. Это означает, что различные части объекта оказываются похожими друг на друга или на весь объект в целом.
Цель работы
Целью представленной диссертационной работы является:
Оценить существующие алгоритмы сжатия графических изображений, в том числе, алгоритмы фрактального сжатия.
Разработать методы ускорения процедур фрактального сжатия монохромных изображений.
Улучшить аппроксимативные свойства алгоритма фрактального сжатия монохромных и бинарных изображений
Создать комплекс программ, в том числе и для многопроцессорной техники, для обработки графических изображений в соответствии с разработанными алгоритмами фрактального сжатия.
Научная новизна работы
В данной работе впервые предложено использовать:
параметр нормализованной размерности для предварительной классификации фрагментов изображения; это позволяет ускорить процесс нахождения параметров фрактального сжатия.
преобразование Мерсенна для ускорения процесса фрактального сжатия.
процедуру адаптивного разбиения на регионы дерева всплеск-коэффициентов для улучшения аппроксимационных свойств фрактального сжатия изображений.
Апробация работы Основные результаты диссертации докладывались на:
Молодежной конференции "Проблемы теоретической и прикладной математики". Екатеринбург: УрО РАН, 1997, 1999, 2000г.
Школе-конференции им. С.Б.Стечкина по теории приближения функции, Миасс, 1998, 1999, 2000, 2003г.
Сессиях молодых ученых ИММ УрО РАН.
Расширенном семинаре "Параллельные вычисления"ИММ УрО РАН.
Исследования, проведенные по теме диссертации, поддержаны грантами РФФИ №96-01-00121, №99-01-00460 и №02-01-00782, а также грантом "Ведущие научные школы РФФИ" №00-15-96035.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав основного текста и заключения, в котором перечислены основные полученные результаты. Объем диссертации составляет 73 страницы. Библиография включает 38 наименований. Диссертация содержит 23 рисунка и 3 таблицы.
Краткое содержание работы
Во введении дается понятие сжатия информации, обзор основных методов сжатия графических изображений и параметры оценки этих методов. Сформулированы цель работы, краткое содержание диссертации по главам и научная новизна.
Во второй главе изложены основные сведения о фрактальном методе сжатия изображений.
В разделе 2.1 приведены основные понятия и определения. Пусть (Z,р) - полное метрическое пространство, где р{х,у) - расстояние между элементами х, у Є Z. Отображение Т : Z —> Z называется сжимающим, если величина
def (р(Т(х),Т(у))\
ГТ = SUp ( г I
x,yeZ,x?y \ Р\?уу) )
удовлетворяет неравенству тт < 1. В этом случае число г? называют коэффициентом сжатия оператора Т. Точка гт Є Z называется
неподвижной точкой оператора Т, если T(zt) = zt-
В соответствии с теоремой Банаха о неподвижном элементе сжимающего оператора в полном метрическом пространстве, если для элемента гт удастся найти сжимающий оператор Г такой, что T(zt) = zt, то zt может быть восстановлен с произвольной наперед заданной точностью. Восстановление осуществляется с помощью итерационной последовательности {Tn(x)}%L0, гДе х ~ произвольно выбранный начальный элемент. Погрешность восстановления определяется как:
p(ZT,Tn(x))
1 — Гт
Задача фрактального сжатия сводится к задаче оптимизации: на некотором заданном множестве Т сжимающих операторов найти оператор Т : Z —> Z, неподвижная точка zt которого аппроксимировала бы заданный элемент z Є Z. Ошибку аппроксимации обозначим
как Е-:
Ej= ini' p(z,zT). тєт
Задача нахождения такой точной нижней грани очень сложна, и для
ее упрощения используют неравенство Барнсли [2]:
P\z,zT) < ——-—,
1 — Гт
которое непосредственно следует из теоремы Банаха. Благодаря этому, указанную выше задачу оптимизации можно заменить на поиск сжимающего отображения Т, под действием которого исходный элемент z не слишком бы изменялся. В этом случае аппроксимация заключается в решении следующей задачи минимизации:
Ez=mmp(z,T(z)).
В разделе 2.2 изложены основные принципы аппроксимации множеств.
Пусть пространство Z = {М С Е2,М — компакт}. Идея фрактальной аппроксимации множества М (Дж. Хатчинсон, [9]) заключается в использовании оператора Т, который действует на Z и задается соотношением:
Т(М) = (J Г«(М), »=1
Г-
где Ті — аффинный сжимающий оператор, Z -\ Z.
В качестве расстояния между множествами из Ж2 используется расстояние по Хаусдорфу. Пусть
p{x,Y)d= гтпр(х,у)
- расстояние от элемента х Є R2 до множества Y С К2. Обозначим V(XyY) = sup/0(2:,У), Х,У С R2.
Тогда расстояние Хаусдорфа между множествами X, Y С М2 записывается как
h(X,Y) d=f max(V(X,r),F(y,X)).
Пространство Z с метрикой h является полным метрическим пространством. Оператор Т является сжимающим с коэфициентом сжатия гт < max г ті. Обозначим Мт - инвариант для оператора Г,
i=l,...N
т.е. Мт = Т(Мт). Набор {Ti}fL1 называют системой итерируемых функций (IFS) [2].
Задача аппроксимации инвариантом Мт бинарного изображения, заданного множеством М, состоит в нахождении оператора Т, т.е. параметров соответствующей IFS {Т*}^, гарантирующего заданную погрешность є: h(M,T(M)) < є.
В разделе 2.3 рассмотрено фрактальное представление монохромных изображений.
На основе понятия IFS A. Jacquin предложил метод фрактального сжатия монохромных изображений [11]. Под монохромным изображением в данном случае понимается ограниченная функция яркости /(ж), которая задана на компактном множестве X С R2 с мерой /і, X Л Е, /GL2 = L2(X,M).
Для построения оператора Т, действующего в Ьг(Х, д) требуются следующие составляющие:
1. Набор компактных множеств {R^Iq > - С Х> такой, что:
&)n\jRi = X;
*=о
2. Набор компактных множеств {Dj}l-_}Q1Di С Ху такой что для
любых Ri и Dj существует сжимающий оператор Wij : X -f X, имеющий обратное отображение fcfy1, причем Wij(Dj) = ..
3. Набор сжимающих операторов {&}=о,№ ^ ^- Обычно пола
гают, что
ipi(t) = dit + bi.
Множества Ri называются регионами (regions), a Dj — доменами (domains).
Функции tpi будут согласовывать значения яркости фрагментов изображения, соответствующих конкретному региону и домену, т.е. выбор (рі вида (2.10) определяется условием:
min {||/№) - <йМЫ(Ъ))\\ьЛ, і = 0,...,n - 1.
Произвольной функции / = /(я), (х ЄХ) оператор X сопоставляет функцию Г/, задаваемую на каждом Я», г = 0, ...,тг — 1 соотношением:
Номер г определяется по ж, так как # Є Ri, и для преобразования Г используются ірі и u>i с соответствующим индексом г.
Заранее выбранные наборы {-К^^Гд1, {A7"}j=o> а также ВИД опе~ раторов {(pi}^Q и определяют множество поиска параметров фрактального сжатия.
В большинстве алгоритмов конструирования (нахождения) оператора Т среди заданных множеств домен и регионов путем перебора выявляют оптимальные пары, вычисляя погрешность Є{ :
Si = minmin{||/(iu) - ^(/(а^СВДЦ^}, і = 0,...,n
-1 .
Таким образом, задачу фрактального сжатия разбивают на п локальных (взаимно независимых) задач.
В разделе 2.4 рассмотрен пример численного алгоритма фрактального сжатия монохромного изображения.
Для приложений, связанных с вычислительной техникой, удобно представлять графические изображения в виде матрицы X — іх- Л^т1'"1-1 ж =0 2Ь —1
Глубину цвета 6 обычно берут равной б, 8 или 16. Бинарному изображению соответствует 6=1.
Из матрицы X перестановкой четных и нечетных элементов построим матрицу У(X) = ( ,.00 -?1 J, т.е.
*00 — \х2г,2з U=o,k=o *
101 — \x2i,2j+lJi=0,k=0 »
Ут - -Гго^-, „лК"-1)/2)'!/2)
*10 — іж2ї+1,2^іі=о,А;=0 »
Til — \x2i+l,2j+lSi=otk=0 »
где [...] — целая часть.
Для построения набора IFS определим множество допустимых домен и регионов следующим образом. В качестве регионов выбираем квадратные фрагменты одинакового размера:
Rk = {Гу}^1о, »у = Xi+bVJ+kaV, ГДЄ fc = (fci,fc2),
У - размер регионов. Таким образом, данные регионы без пересечений покрывают все изображение X. На У строим набор домен, которые также являются квадратными фрагментами:
Di = {4/'}*\Й)> 4/ = УЖі,і+'2і гДе і = {luh)-
Фрактальное сжатие состоит в нахождении для каждого региона Rk наиболее подходящего домена Di в смысле
V-1
е\ = minmin{ Т Н- - *Л\з - о)2,|5| < 1, о = 0,..., 2Ъ - 1} t,j=o
Здесь s — контрастность, о — яркость. Оба эти параметра согласуют значения яркости различных фрагментов изображения. Вместо описания графического изображения как матрицы X надо запомнить для каждого региона Д& номер наиболее подходящего для него домена I и параметры такой похожести (коэффициенты s и о). Методом
наименьших квадратов для фиксированных I и к можно найти параметры 5 и о, при которых величина
i.= EH-4-»)!
*,j'=o
достигает минимума.
Восстановление изображения происходит следующим образом:
Берём произвольное начальное изображение Xq\.
Строим У(Х0);
Строим регионы Rk : r- = «*djj + о&;
Построенные регионы образуют новую итерацию восстановленного изображения Х\ На ее основе строим Y(Xi) и повторяем п.З.
Поиск коэффициентов фрактального сжатия требует значительных вычислительных затрат и, соответственно, времени счёта. Предлагаемые методы повышения быстродействия фрактального сжатия рассматриваются в третьей главе.
В разделе 3.1 описан метод повышения быстродействия на основе предварительной классификации фрагментов изображения. Это позволяет для каждого региона проводить поиск, т.е. решать задачу оптимизации только среди домен, близких в смысле этой классификации к региону Rk. Удачно подобранный признак классификации позволяет значительно сократить объем требуемых вычислений, почти не увеличивая погрешность. Таким критерием может быть, например, пространственная близость региона и домена [3]: поиск осуществляется лишь среди тех домен, которые расположены недалеко от данного региона.
Другой критерий, основанный на разделении всех фрагментов изображения на "гладкие", "шероховатые" и с "выраженной границей перепада значений", используется в работах Фишера, Якобса и Босса [б], [10].
Предлагаемый алгоритм также основан на интуитивно понятном стремлении проводить поиск оптимального фрагмента для некоторого Ri с "шероховатой" (сильно изломанной) поверхностью среди таких домен, у которых поверхность также является "шероховатой". В качестве "меры шероховатости" поверхности можно принять фрактальную размерность h фрагмента, которая определяется как предел
(если этот предел существует) [22]:
logN
h = lim
є-ю log І/є '
где Ne — наименьшее число шаров радиуса е, необходимых для покрытия поверхности. Чем больше h , тем "шероховатость" выше.
Недостаток такого способа классификации заключается в том, что при воздействии на регион коэффициентами яркости и контрастности изменится и фрактальная размерность этого региона. Это значит, что при решении задачи поиска нельзя предварительно (т.е. до определения s и о) провести классификацию фрагментов Di. Выходом из этой ситуации может быть использование следующей нормализации фрагментов функции:
G{d»' - m»dL-mJndL'
D, %3 Di %3
где Di — средняя величина функции на фрагменте Di , Такая процедура нормализации гарантирует выполнение равенства
G^) = G(s dlij + о) Vs,o.
Чтобы исключить неопределенность в случае, когда
тахс^ — minc^.- = 0, уточним формулу для G{d\A следующим обра
зом:
G(d\j) = ^^-, где
_ J тахс^ - mindlj, maxd^- - mind^ > 1 1 ~~ \ 1, maxd^ — mmd\j < 1
В качестве признака классификации фрагментов выберем такую "нормализованную" размерность g{D{) = h(G(dlij))i d\j Є D{, которая также не будет зависеть от коэффициентов s, о.
Таким образом, поиск пар регион-домен будет проводится в два этапа:
1. Нахождение и запоминание "нормализованных" размерностей д для всех рассматриваемых регионов {Rk} и домен {Di};
2. Для каждого региона Rk определяется множество домен ED* С {D/}, на котором будет осуществляться поиск наилучшего Di в смысле (2.15).
При достаточно низком качестве аппроксимации, т.е. при большом Єк нельзя утверждать, что у оптимальной пары регион-домен "мера шероховатости" будет совпадать или хотя бы достаточно близка. Иными словами, возможна ситуация, когда, например, сильно "изломанный" регион наиболее удачно (из всех рассматриваемых вариантов) аппроксимируется "гладким" доменом. При этом, неизбежное отбрасывание потенциально оптимальных кандидатур на предварительном этапе приведет к ухудшению качества аппроксимации (т.е. качества решения задачи фрактального сжатия в целом). Естественно, чем больше домен исключено из процедуры поиска, тем хуже будет это качество.
В таблице приведены результаты работы данного алгоритма на изображении Lenna.
В разделе 3.2 предложен метод повышения быстродействия с использованием преобразования Мерсенна (см. [35]). Попарное сравнение К регионов и L домен заключается в вычислении параметров s и о и погрешности єік- При этом основная вычислительная слоясность приходится на вычисление L К выражений типа
K-1.L-1
V
Выражение вида
^2rijdlij = ^2xi+kip,j+k2pywi,j+h
*]
называется корреляцией. Для его быстрого вычисления можно использовать N-точечное дискретное преобразование Фурье. Одна-
ко использование преобразования Фурье для подобных вычислений оказывается неэффективным по следующим причинам:
вычисления приходится проводить в области комплексных значений, тогда как исходное оцифрованное изображение задано, массивом целых чисел ;
использование величин типа sin (jf-ik) и cos (jf-ik) приводит к ошибкам округления, и конечный результат получается неточным.
Имеет смысл заменить преобразование Фурье неким другим преобразованием, которое было бы пригодно для аналогичного вычисления корреляций и, одновременно, лишено перечисленных недостатков, т.е. чтобы вычисления проводились в целых числах. Такими свойствами обладает, например, преобразование Мерсенна, особенностью которого является работа в модулярной арифметике. Одномерное р-точечное преобразование Мерсенна записывается в виде (см. [35]):
(р-1 л Р-1
{ЗДЙ = М ({хі}^) = х&к mod (2Р - Ц \ > (L2)
где р — простое число. Числа вида 2Р — 1 ,(р - простое), называются числами Мерсенна.
Сравнивая дискретное преобразование Фурье и преобразование
(
\ N ei%rlkj = 1 и (2гк)р = 1 mod (2Р — 1) ,
т.е. в обоих преобразованиях разложение происходит по базису, составленному из корней iV-й и р-й степени из 1, соответственно.
р-1
р-1
Циклическая корреляция [35] представляется следующим образом
X^(fc+i) (mod p)Xi > = М.1 (М г ({уі}) М ({х{})) -р 1 ,
. *=0 ) к=о
при условии, что значения получаемых отсчетов не превосходят величины 2Р — 1.
Преобразования М({хі}) и М({у»}) надо выполнять один раз для каждого фрагмента функции (домена или региона). Почленное произведение M(f)'M~1(g) (р2 умножений по модулю 2Р—1) и обратное преобразование надо выполнять L К раз. Для более точного сравнения объема требуемых вычислений непосредственным счетом и с
помощью преобразования Мерсенна автором настоящей работы были составлены соответствующие программы на ассемблере (TASM с опцией р48б) и определено количество тактов процессора i486 (справочные данные, см.,например, [27]), требуемых для вычисления двумерной циклической корреляции обоими способами.
Метод с использованием преобразования Мерсенна требует ^mersenn R* 44р3 + 107р2 тактов для вычисления, а прямой счет ^direct w (407712 + 10m) р2 тактов, где т — линейный размер фрагмента изображения. Линейный размер га, длина преобразования р и глубина цвета Ь связаны между собой соотношением: log2 т < р/2—6, полученным из условия
2_^ 2_^ У(кі+іі) (mod p)(k2+i2) (mod p)xiii2 < 2P — 1,
»1=0І2=0
#1, A?2 == 0,...,p — 1, Хіхі2, Уігі2 = 0,..., 2 — 1 ,
Для типовых значений b — 8, p = 23 ига = 8 преобразование Мерсенна дает выигрыш примерно в 2.36 раза при получении точно таких же результатов, что и непосредственным вычислением [16].
В разделе 3.3 дается описание алгоритма вычисления параметров фрактального сжатия для многопроцессорной вычислительной техники. Многопроцессорный вычислительный комплекс представляет собой множество связанных между собой процессоров (устройств обработки информации). Схему аппаратной связи узлов друг с другом удобно представить в виде неориентированного графа, в котором вычислительные узлы Vi представляются в виде вершин, а связи между ними — в виде дуг. Если узлы не являются ближайшими соседями, то они все равно могут обмениваться сообщениями, передавая их "по цепочке" из непосредственно связанных между собой вычислительных узлов. Передача данных между узлами — относительно медленный процесс, по сравнению с самими вычислениями. Этот процесс протекает быстрее, если информацией обмениваются узлы, являющиеся непосредственными соседями.
Задача, которая выполняется на многопроцессорном вычислительном комплексе, считается завершенной, когда все узлы, участвующие в её решении, закончат свою работу. Для эффективного переноса алгоритма на многопроцессорный комплекс (т.е. "распараллеливание алгоритма") необходимо:
Свести к минимуму время простоя отдельных узлов;
Уменьшить количество обменов между узлами, особенно между теми, которые не являются ближайшими соседями;
Обеспечить возможность назначать для решения задачи произвольное количество процессов.
Для оценки эффективности работы алгоритма на многопроцессорном комплексе используется коэффициент распараллеливания
Кп(п) = п- -Р-,
где ti — время счёта задачи на одном узле (т.е. без распараллеливания), п — количество узлов, tn — время счёта задачи на п узлах.
Распараллеливание считается идеальным, если Кц{п) гИ 1 при достаточно большом п.
Поиск наилучшего домена для каждого региона выполняется независимо, что упрощает распараллеливание алгоритма: один регион (или набор регионов) обрабатывется на отдельном узле вычислительного комплекса. Один из узлов назначим ведущим: он будет распределять работу (т.е. номера регионов) между остальными узлами (ведомыми), а также собирать результаты вычислений с этих узлов. Как только ведомый узел передал ведущему очередной результат, так сразу получает новое задание. При этом время простоя и количество обменов между узлами минимально, и коэффициент распараллеливания близок к 1. К недостаткам данного способа распараллеливания можно отнести то, что все исходные данные необходимо хранить целиком на каждом узле, что не всегда применимо при обработке изображений большого размера. Предлагается изменить алгоритм так, что каждый узел будет хранить лишь фрагмент матрицы Ти выполнять поиск для всех регионов по доменам из этого своего фрагмента.
Ведущий узел передает остальным узлам данные об очередном регионе. Для этого региона ведомые ищут наилучший домен на своем фрагменте матрицы У, после чего передают результат обратно ведущему. Из всех переданных ему результатов ведущий выбирает наилучший домен, т.е. с наименьшей погрешностью е^, а также назначает ведомым новое задание по следующему региону.
Такой алгоритм требует большего количества обменов между узлами, что снижает производительность.
Для повышения эффективности вычислений необходимо по мере возможности выполнить следующие требования:
Уменьшить общее количество обменов между узлами, особенно если эти узлы не являются непосредственными соседями;
Разбить матрицу Y на N8 равновеликих прямоугольных фрагментов (т.е. содержащих примерно одинаковое количество отсчётов), где N8 — количество ведомых узлов, выделенных для решения задачи фрактального сжатия. Это требование обеспечивает примерно одинаковый объем вычислений для каждого узла и, соответственно, уменьшает общее время простоя вычислительного комплекса;
Соотношение сторон прямоугольных фрагментов должно быть как можно ближе к 1.
Для уменьшения количества обменов между узлами, не являющимися непосредственными соседями, предлагается учесть в алгоритме схему аппаратной связи узлов друг с другом. Эту схему в вычислительном комплексе MVS-100 молено определить программно, например в самом начале работы программы.
Через Cij обозначим расстояние между узлами Vi и Vj.
Назовем вершину Vk центром графа, если тахсы = minmaxcf/.
з і з
"Развернем" данный граф в дерево, отбросив все дуги, кроме тех,
которые образуют кратчайшие пути от центра графа до остальных
вершин. Центр графа назначим ведущим узлом.
Схема передачи данных в алгоритме будет определяться таким деревом. Ведущий узел передает информацию о регионе Rk своим непосредственным соседям. Эти узлы, после вычисления наилучших для них домен на своих фрагментах, передают данные о регионе Rk вместе с информацией о результате поиска дальше по дереву. Таким образом, информация о наилучшем по всей ветке домене накапливается в каждом из оконечных узлов ("листьях"). Эту информацию оконечные узлы передают ведущему, который и осуществляет окончательный выбор наилучшего домена для данного региона.
Передача этой (и только этой) информации будет происходить неоптимальным образом (т.е. между узлами, не являющимися непосредственными соседями). Как только узел заканчивает процедуру поиска для одного региона, он обращается к вьппестоящему узлу за новой порцией данных (по следующему региону). Таким образом, основной поток данных последовательно распространяется от веду-
щего узла к оконечным, и в обмене информацией при этом участвуют лишь непосредственные соседи.
В соответствии с данным параллельным алгоритмом фрактального сжатия изображений была разработана программа для многопроцессорного вычислительного комплекса MVS-100. На рис. 1.1 изображена зависимость скорости решения задачи фрактального слсатия по параллельному алгоритму от количества процессоров. Размер обрабатываемого изображения 1600 х 960 пикселов.
1.4-1.2-
t 0.8--
S о.б--
0.4--
0.2--
количество процессоров
Рис. 1.1. Зависимость скорости вычисления от количества процессоров
В четвертой главе обсуждается применение всплесков в задаче фрактального сжатия. Теория всплесков родилась в середине 1980-х годов. Её возникновение и развитие связано с именем Ж.Морлета, Я.Мейера, С.Малла, И.Добеши и др. [38], [30], [14]. Всплески находят применение в обработке сигналов с меняющимися частотами для одновременно анализа частотных и временных характеристик. При дискретном всплеск-преобразовании функция / представляется в виде
/ ~ ^2 o>ij^{otit - Pj), otuPj Є R
Это представление основано на понятии "кратномасштабная аппроксимация " (" multiresolution approximation ").
В разделе 4.1 дается понятие кратномасштабной аппроксимации. Обычно коэффициенты всплеск-преобразования изображаются в виде бинарного дерева.
Коэффициенты группируются по блокам (поддеревьям) Bij. Т.е. можно определить блок коэффициентов
Bkj = {{h+pj^p+itflo1 \ .
і. і р=0
р= Определим расстояние между блоками всплеск-коэффициентов:
р 2р-1
P2{Bkx,ji,Bk2,j2) = 2~к'2 22 2~Р'2 22 (&fei+P,Ji-2P+i - bk2+p,j2.2P+l)2,
р=0 1=0
(1.3) где к = max(A;i, /).
В разделе 4.2 дается описание всплеск-фрактального преобразования.
Будем обозначать поэлементное умножение на А Є R всех коэффициентов блока Bkj как Л Bkj.
Зафиксируем некоторый уровень бинарного дерева к. Назовём блоки Вы, і = 0,2к — 1 регионами, а блоки Bk-i,%, г = 0,2к~х — 1 — доменами.
Каждому региону Вк% некоторым образом сопоставим домен Bk-iji и множитель ;|А$|. На основе дерева коэффициентов исходного всплеск-преобразования построим новое следующим образом: верхние коэффициенты до уровня к оставим без изменения, а блоки Bku і = 0,2Ї_1 заменим на XiBk-i^.
Построенное таким образом новое дерево коэффициентов обозначим как F\. На основе описанной процедуры из F\ построим i*2, затем из i*2 —> Fz и т.д. Таким образом, мы определили оператор
Т 1
Т : Fi -> Fi+i. В [24] показано, что при | А» |< -т- оператор Т будет сжимающим.
Для минимизации величины p(Fo,F*) где F* = T(F*) будем минимизировать p(Fo,T(Fo)). Для каждого региона Вы, г = 0,2* — 1 будем искать наилучший домен Вк-\^'
ji = arg min min р{Вкі, A B( ft_i)Z).
Величина mmp(Bki,\ -B(jk-i)z) находится при помощи метода
наименьших квадратов. Для такого всплеск-фрактального представления достаточно запомнить "верхние этажи" пирамиды до уровня к — 1 и 2к пар коэффициентов (jj, А»). При восстановлении дерево коэффициентов F* будет достраиваться сверху вниз, начиная с уровня к.
В разделе 4.3 рассматривается предлагаемая модификация всплеск-фрактального метода сжатия изображений. Для улучшения аппрок-симационных свойств метода предлагается проводить разбиение оставшейся части дерева всплеск-коэффициентов (с уровня к' + 1) на регионы в зависимости от конкретного изображения. Такое разбиение будем проводить последовательно по следующему алгоритму:
Для всех регионов найти наилучшие домены и величины ошибок е%.
Найти регион с самой большой ошибкой * = тахе*.
Заполнить корневой элемент найденного региона, а оставшуюся часть разбить на два (в одномерном случае) или четыре (в двумерном) новых региона.
Для этих новых регионов найти наиболее подходящие домены и вычислить погрешности. Поиск осуществляется среди тех домен (блоков), уровни которых на единицу меньше (выше), чем уровень соответствующих регионов.
Если достигнут заданный коэффициент сжатия или заданная погрешность, то процесс фрактального сжатия завершен. Иначе перейти на п.2.
Как видно из описания, данный алгоритм позволяет осуществлять компрессию данных с произвольным, заранее заданным коэффициентом сжатия. В соответствии с этим алгоритмом кроме дополнительных коэффициентов (у "разбиваемых" регионов) необходимо также запоминать и саму схему разбиения.
В пятой главе предлагается метод нахождения параметров IFS. Данный метод состоит из двух этапов: предварительного и уточняющего. На предварительном этапе необходимо найти "не самые плохие" начальные коэффициенты IFS, которые можно было бы уточнить на следующем этапе. Основной целью предварительного этапа является выделение на исходном множестве М областей, за аппроксимацию которых будет "отвечать"соответствующий оператор Т$.
Для этого предлагается следующий алгоритм:
1. На М построим последовательность итерационно наиболее уда
ленных друг от друга точек (ИУТ) {#г}=і следующим образом:
хі,Х2 Є М і p(xi,X2) = max р(х,у)
х,уЄМ
Хі = argmax.mmp(xj,x),i = 3,..., n,
хЄМ j
т.е. две первые точки наиболее удалены друг от друга, а остальные строятся последовательно как наиболее удаленные от уже найденных.
2. Произведем разбиение Вороного [36] множества М на под
множества Pi С М,г = 1,...,ЛГ, т.е. Pi = {х Є М : р{хі,х) <
min p(xj, х)}. Эти подмножества и будут являться искомыми обла-
стями разбиения.
3. Для того, чтобы аффинное преобразование Т» соответствовало
конкретному подмножеству Pi, определим коэффициенты этого пре
образования так, чтобы расстояние Хаусдорфа между множествами
Ті(М) и Pi было не очень большим. С этой целью для каждого Pi на
ходим три итерационно удаленные точки {г/!}^=1. Коэффициенты Ті
выбираем так, чтобы {yj}?=1 являлись образами первых трех ИУТ
{хі}і=і всего множества М. Из возможных б вариантов наложения
одной тройки точек на другую выбираем тот, при котором ошибка
h(Ti(M),Pi)) наименьшая.
Для простого множества М, вроде треугольника Серпинского, найденная таким образом первоначальная IFS уже будет неплохой аппроксимцией. Но для большинства других М это будет не так. Поэтому найденные коэффициенты нуждаются в уточнении.
4. Из найденного набора IFS {Ti}^L1 выберем самое "плохое"пре
образование Ті* , т.е. если
max р(у,М) > тахр(ж, І I ТАМ)),
N хЄМ ^
y\jTi(M) t=l
то і* := arg max p(y,M) = arg max p(y,M),
уєи Ti(M) У г К J
в противним случае, обозначив
(я*,у*) =argmax min p(x,y),i* : у* Є Ті*{М),
х.М N
і/є U Ті(м)
«=1
построим новое Pi* ={xeM: р(х,Ті.(М)) < і(є) Лр(х, (J Tj(M)) > 2(е),
где є = h{M,T{M)). Величина 5\{s) определяет насколько сильно
будет отклоняться новое Рі* от старого Ті» (М), а $2 (є) регулирует
^ вхождение в новое Pi* тех точек, которые будут аппроксимироваться
за счет остальных Tj. Эти величины выбираются экспериментально.
Этап уточнения подробно описан в [25]. Обозначим F(T) = h(M,T(M)). Будем говорить, что ЛТ задает направление спуска, если при всех достаточно малых Л > 0 выполняется неравенство F(T + ДАТ) < F{T). Для компактов G,Q С М? обозначим через Gq = {д Є G : p(g,Q) = h(G,Q)} множество точек из G максимального уклонения до Q. Проекцию точки х на Q будем обозначать как Pq(х) = {q Є Q : /э(ж,Т задает направление спуска.
Будем искать точку z* Є М6, которая удовлетворяет всем этим
. условиям. После нахождения нового оператора Tj повторяем этап
» уточнения.
По всем предлагаемым алгоритмам были составлены программы компактного описания графических изображений.
Список работ по теме диссертации
V.I. Berdyshev, S.V. Berdyshev, V.P. Kondrat'ev, V.B. Kostousov, Ya V. Malygin. On compression and modelling of images // Russian Journal of Numerical Analysis and Mathematical Modelling. Vol. 11, № 4, 1996, p. 275-285.
Ya. V. Malygin. Two Methods for Fast Fractal Compression of Images II Pattern recognition and Image Analysis. Vol. 9, № 3, 1999, p. 448-452.
3. Малыгин Я.В. Всплеск-фрактальное сжатие с адаптивными
размерами регионов // Проблемы теоретической и прикладной ма-
jf тематики: Труды 32-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2001, С. 37-39.
Малыгин Я.В. Поиск параметров IFS для бинарного изображения // Проблемы теоретической и прикладной математики: Труды 33-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2002, С. 71-73.
Малыгин Я.В. Параллельный алгоритм фрактального сжатия графических изображений большого размера // Проблемы теоретической и прикладной математики: Труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 276-278.
Результаты автора по этой теме также были использованы в монографии Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297 с.
2 Фракталы
Фрактальное представление монохромных изображений
На основе понятия IFS A. Jacquin предложил метод фрактального сжатия монохромных изображений [11]. Под монохромным изображением будем понимать ограниченную функцию яркости f(x), которая задана на компактном множестве 1сМ2с мерой fi, X -» R, feL2 = L2(X,fi). Для построения оператора Г, действующего в L2 (X, у) требуются следующие составляющие: 1. Набор компактных множеств {Ri ojRi С X, такой, что: 2. Набор компактных множеств {-D/}i-=o -CVC X, такой что для любых Ri и Dj существует сжимающий оператор ufy- : X —f X, имеющий обратное отображение wjl1, причем Uij(Dj) = R . 3. Набор сжимающих операторов { PiYiZo№ -4 К,. Обычно пола гают, что Множества Ri называются регионами (regions), a Dj — доменами (domains). Функции (pi будут согласовывать значения яркости фрагментов изображения, соответствующих конкретному региону и домену, т.е. вы бор ірі вида (2.10) определяется условием: где - норма в Z/2. Произвольной функции / = f(x), (х Є X) оператор Т сопоставляет функцию Т/, задаваемую на каждом Щ, г = 0, ...,п — 1 соотношением: Заранее выбранные наборы {Ri}?=Q, {Dj}l3Z}01 а также вид операторов { г} )1 и определяют множество поиска параметров фрактального сжатия. Возможность аппроксимации одного фрагмента изображения другим обусловлена избыточностью, содержащейся в самом изображении [17]. Задача фрактального сжатия сводится к поиску похожих фрагментов внутри самого изображения. В большинстве алгоритмов конструирования (нахождения) оператора Т среди заданных множеств домен и регионов путем перебора выявляют оптимальные пары, вычисляя погрешность є» : Таким образом, задачу (2.5) разбивают на п локальных (взаимно независимых) задач. Сжатие графической информации обеспечивается небольшим числом параметров оператора Т, необходимых для описания исходного изображения /. Для приложений, связанных с вычислительной техникой, удобно представлять графические изображения в виде матрицы Глубину цвета b обычно берут равной 6, 8 или 16. Бинарному изображению соответствует 6=1. Из матрицы X перестановкой четных и нечетных элементов по строим матрицу Y(X) = I где [...] — целая часть. Для построения набора IFS определим множество допустимых домен и регионов следующим образом. В качестве регионов выбираем квадратные фрагменты одинакового размера: V — размер регионов. Таким образом, данные регионы без пересечений покрывают все изображение X. На Y строим набор домен, которые также являются квадратными фрагментами: Фрактальное сжатие состоит в нахождении для каждого региона Rk наиболее подходящего домена D\ в смысле . Оба эти параметра согласуют значения яркости различных фрагментов изображения.
Вместо описания графического изображения как матрицы X надо запомнить для каждого региона Rk номер наиболее подходящего для него домена I и параметры такой похожести (коэффициенты s и о). Хорошо известным способом для фиксированных І я к можно найти параметры s и о, при которых величина достигает минимума. Для этого приравниваем к нулю ее производные по s и о: : 1. Берём произвольное начальное изображение Хо; 2. Строим Y(X0); 3. Строим регионы Rk : r- = 5 d{} + о ; 4. Построенные регионы образуют новую итерацию восстановленного изображения Xi На ее основе строим Y{X\) и повторяем п.З. Для фрактального увеличения линейных размеров восстанавливаемого изображения в q N раз данный алгоритм следует немного изменить: 1. Берём произвольное начальное изображение например "черное поле": а& = 0.; 2. Перестановкой четных и нечетных элементов получаем Y(Xo); 3. Элементы каждого региона строим по правилу : r = Skd1 + о , где домен 4. Как и в предыдущем случае, построенные регионы образуют новую итерацию восстановленного изображения Х\, на основе кото рой строим Y{X\) и повторяем п.З. Пример. Пусть изображение имеет размеры т = п = 256, глубина цвета 6 = 8. Для хранения такого изображения необходимо 64 Кб памяти. Если разбить данное изображение на регионы Rk размером 8x8 пикселов, то количество регионов будет равно 1024. При фрактальном описании этого изображения для каждого региона необходимо запомнить: — номер наиболее подходящего домена / (16 бит), — коэффициент контрастности s (6 бит), — коэффициент яркости о (8 бит). Таким образом, фрактальное представление данного изображения занимает 1024 (16 + 6 + 8) = 30720 бит, и коэффициент сжатия составляет « 17,07. Результат работы данного алгоритма приведен на рис. 2.3. Здесь и далее в качестве примера используется стандартное тестовое изображение "Lena". Если требуется более высокое качество восстанавливаемого изображения, то можно уменьшить коэффициент сжатия, например, путем увеличения количества регионов Rk Рис. 2.3. Изображение Lena. Размер 256x256 пикселов, глубина цвета 8 бит на пиксел. Слева оригинал. Справа - восстановленное изображение. Качество 27.14 дБ, коэффициент сжатия 17.07, время счета 605 сек. На рис. 2.4 приведен результат фрактального увеличения этого изображения. Заметим, что коэффициент сжатия для изображения,
Использование преобразования Мерсенна
Другим способом уменьшения времени поиска может быть модификация механизма вычислений без изменения самой идеи полного перебора. Попарное сравнение К регионов и L домен заключается в вычислении параметров з и о (2.16) и погрешности єік (2.15). Для этих вычислений необходимо использовать следующие множества величин: Первые четыре множества содержат относительно немного элементов (L или К), что позволяет вычислить их и запомнить для дальнейшего многократного использования в процедуре поиска. Последнее множество состоит из L К элементов, и их вычисление является основной вычислительной сложностью в алгоритме фрактального сжатия. Выражение вида (см. 2.13, 2.14) называется корреляцией (см. [35]). Для его быстрого вычисления можно использовать N-точечное дискретное преобразование Фурье, которое в одномерном случае записывается как: (здесь и до конца раздела j обозначает мнимую единицу). Однако использование преобразования Фурье для подобных вычислений оказывается неэффективным по следующим причинам: - вычисления приходится проводить в области комплексных значений, тогда как исходное оцифрованное изображение задано массивом целых чисел ; - использование величин типа sin (77 ) и cos (jj-ik) приводит к ошибкам округления, и конечный результат получается неточным. Имеет смысл заменить преобразование Фурье неким другим преобразованием, которое было бы пригодно для аналогичного вычисления корреляций и, одновременно, лишено перечисленных недостатков, т.е. чтобы вычисления проводились в целых числах. Такими свойствами обладает, например, преобразование Мерсенна [35], особенностью которого является работа в модулярной арифметике.
Одномерное р-точечное преобразование Мерсенна записывается в виде: где р — простое число. Числа вида 2Р — 1 ,(р - простое), называются числами Мерсенна. Сравнивая дискретное преобразование Фурье и преобразование т.е. в обоих преобразованиях разложение происходит по базису, составленному из корней N-и и р-й степени из 1, соответственно. Рассмотрим действия над числами в модулярной арифметике. Число хп можно представить в следующем виде: где xnj Є {0,1} - двоичный разряд. Сложение двух целых чисел длиной р бит в общем случае занимает р +1 бит: т.к. 2Р = 1 mod (2Р — 1). Таким образом, при сложении двух целых чисел самый старший разряд добавляется к самому младшему. Определим инверсию числа хп : хп — Yl, Яп,і2% где ХПІІ - инверсия разряда: Тогда сумма Отсюда следует, что Рассмотрим умножение числа хп на величину 2d : Таким образом, умножение на 2d эквивалентно циклическому сдвигу р-битового слова на d двоичных разрядов влево. Умножение общего вида сводится к умножениям на степени 2 и сложениям. Обратное преобразование Мерсенна записывается в виде: т.е. нулевой элемент обратного преобразования XQ совпадает с нулевым элементом прямого преобразования хо : хо = XQ = # . Для остальных элементов Хк = #p-fc mod (2Р — 1), /г = 1,... ,р — 1. А в соответствии с теоремой Ферма (2Р — 2) делится на р. Циклическая корреляция [35] представляется следующим образом: 4f» (3.8) при условии, что значения получаемых отсчетов не превосходят величины 2Р — 1. Преобразования М.{{х%}) и Лі({уі}) надо выполнять один раз для каждого фрагмента функции (домена или региона). Почленное произведение Л1({а;»}) Л _1({у»}) (р2 умножений по модулю 2Р —1) и обратное преобразование надо выполнять L K раз. Для более точного сравнения объема требуемых вычислений непосредственным счетом (по левой части (3.8) ) и с помощью преобразования Мерсенна (по правой части (3.8) ) автором данной работы были составлены соответствующие программы на ассемблере (TASM с опцией р486) и определено количество тактов процессора i486 (справочные данные, см.,например, [27]), требуемых для вычисления двумерной циклической корреляции обоими способами. Метод с использованием преобразования Мерсенна требует imersenn « 44р3 + 107р2 тактов для вычисления, а прямой счет direct w (40m2 + Ют) p2 тактов, где га — линейный размер фрагмента изображения. Линейный размер га, длина преобразования р и глубина цвета Ъ связаны между собой соотношением: log2 га р/2—Ь, полученным из условия: р
Для типовых значений 6 = 8, p = 23 и m = 8 преобразование Мерсенна дает выигрыш примерно в 2.36 раза при получении точно таких же результатов, что и непосредственным вычислением [16]. Так, время фрактального сжатия с использованием преобразования Мерсенна изображения Lenna (см. рис 2.3) уменьшилось с 605 до 383 сек. Для уменьшение времени фрактального сжатия изображений предлагается использовать многопроцессорную вычислительную технику, которая получает все большее распространение [29]. Многопроцессорный вычислительный комплекс представляет собой множество связанных между собой процессоров (устройств обработки информации). С помощью этих связей процессоры (их называют узлами) могут обмениваться между собой информацией (например, результатами вычислений). Как правило, узел вычислительного комплекса непосредственно связан не со всеми остальными узлами, а лишь с несколькими, называемыми ближайшими соседями. Например, у каждого узла вычислительного комплекса MVS-100 (ИММ УрО РАН) не более четырех таких связей. Схему аппаратной связи узлов друг с другом удобно представить в виде неориентированного графа, в котором вычислительные узлы и представляются в виде вершин, а связи между ними — в виде дуг. Если узлы не являются ближайшими соседями, то они все равно могут обмениваться сообщениями, передавая их "по цепочке" из непосредственно связанных между собой вычислительных узлов. Передача данных между узлами — относительно медленный процесс, по сравнению с самими вычислениями. Этот процесс протекает быстрее, если информацией обмениваются узлы, являющиеся непосредственными соседями.
Использование многопроцессорной вычислительной техники
Для типовых значений 6 = 8, p = 23 и m = 8 преобразование Мерсенна дает выигрыш примерно в 2.36 раза при получении точно таких же результатов, что и непосредственным вычислением [16]. Так, время фрактального сжатия с использованием преобразования Мерсенна изображения Lenna (см. рис 2.3) уменьшилось с 605 до 383 сек. Для уменьшение времени фрактального сжатия изображений предлагается использовать многопроцессорную вычислительную технику, которая получает все большее распространение [29]. Многопроцессорный вычислительный комплекс представляет собой множество связанных между собой процессоров (устройств обработки информации). С помощью этих связей процессоры (их называют узлами) могут обмениваться между собой информацией (например, результатами вычислений). Как правило, узел вычислительного комплекса непосредственно связан не со всеми остальными узлами, а лишь с несколькими, называемыми ближайшими соседями. Например, у каждого узла вычислительного комплекса MVS-100 (ИММ УрО РАН) не более четырех таких связей. Схему аппаратной связи узлов друг с другом удобно представить в виде неориентированного графа, в котором вычислительные узлы и представляются в виде вершин, а связи между ними — в виде дуг. Если узлы не являются ближайшими соседями, то они все равно могут обмениваться сообщениями, передавая их "по цепочке" из непосредственно связанных между собой вычислительных узлов. Передача данных между узлами — относительно медленный процесс, по сравнению с самими вычислениями. Этот процесс протекает быстрее, если информацией обмениваются узлы, являющиеся непосредственными соседями. Задача, которая выполняется на многопроцессорном вычислительном комплексе, считается завершенной, когда все узлы, участвующие в её решении, закончат свою работу.
Для эффективного переноса алгоритма на многопроцессорный комплекс (т.е. "распараллеливание алгоритма") необходимо: 1. Свести к минимуму время простоя отдельных узлов; 2. Уменьшить количество обменов между узлами, особенно между теми, которые не являются ближайшими соседями; 3. Обеспечить возможность назначать для решения задачи произвольное количество процессоров. Для оценки эффективности работы алгоритма на многопроцессорном комплексе используется коэффициент распараллеливания где t\ — время счёта задачи на одном узле (т.е. без распараллеливания), п — количество узлов, tn — время счёта задачи на п узлах. Распараллеливание считается идеальным, если Кц {ті) 1 при достаточно большом п. Поиск наилучшего домена для каждого региона выполняется независимо, что упрощает распараллеливание алгоритма: один регион (или набор регионов) обрабатывется на отдельном узле вычислительного комплекса. Один из узлов назначим ведущим: он будет распределять работу (т.е. номера регионов) между остальными узлами (ведомыми), а также собирать результаты вычислений с этих узлов. Как только ведомый узел передал ведущему очередной результат, так сразу получает новое задание. При этом время простоя и количество обменов между узлами минимально, и коэффициент распараллеливания близок к 1. К недостаткам данного способа распараллеливания можно отнести то, что все исходные данные необходимо хранить целиком на каждом узле, что не всегда применимо при обработке изображекний большого размера. Предлагается изменить алгоритм так, что каждый узел будет хранить лишь фрагмент матрицы У и выполнять поиск для всех регионов по доменам из этого своего фрагмента. Ведущий узел передает остальным узлам данные об очередном регионе. Для этого региона ведомые ищут наилучший домен на своем фрагменте матрицы У, после чего передают результат обратно ведущему. Из всех переданных ему результатов ведущий выбирает наилучший домен, т.е. с наименьше погрешностью еы см.(2.15), а также назначает ведомым новое задание по следующему региону. Такой алгоритм требует большего количества обменов между узлами, что снижает производительность. Для повышения эффективности вычислений необходимо по мере возможности выполнить следующие требования: 1. Уменьшить общее количество обменов между узлами, особенно если эти узлы не являются непосредственными соседями; 2. Разбить матрицу Y на N8 равновеликих прямоугольных фрагментов (т.е. содержащих примерно одинаковое количество отсчётов), где Ns — количество ведомых узлов, выделенных для решения задачи фрактального сжатия. Это требование обеспечивает примерно одинаковый объем вычислений для каждого узла и, соответственно, уменьшает общее время простоя вычислительного комплекса; 3. Соотношение сторон прямоугольных фрагментов должно быть как молено ближе к 1. Рис. 3.2. Пример разбиения прямоугольника на 10 равновеликих фрагментов Для пояснения последнего требования рассмотрим пример разбиения прямоугольника на 10 равновеликих частей (рис. 3.2).
Домены, целиком принадлежащие одному фрагменту, обрабатываются на одном ведомом узле. Возникает вопрос, как обрабатывать домены, отсчеты которых принадлежат разным фрагментам (т.е. пересекающие границу фрагментов). Для решения этого вопроса предлагается разбивать на фрагменты не всю матрицу У, а её часть У = {yijYi=o,jLdm (см СТР 29), т.е. усечённую справа и снизу на линейный размер домена V. После разбиения матрицы Y каждый фрагмент увеличим на величину V справа и снизу (рис. 3.3). На этом рисунке верхняя и левая границы новых фрагментов изображены сплошной линией, а правая и нижняя граница - пунктиром. При этом фрагменты будут перекрываться на величину V (линейный размер домена), и каждый домен всегда будет принадлежать какому-то одному фрагменту.
Всплеск-фрактальное преобразование
Будем обозначать поэлементное умножение на А Є R всех коэффи циентов блока Bkj как Л Bkj. Ч Зафиксируем некоторый уровень бинарного дерева к. По анало гии с (п. 2.2) назовём блоки Вии і = 0,2 — 1 регионами, а блоки верхнего уровня Вк-\,і, і = 0,2А-1 — 1 — доменами. Каждому региону Вкі некоторым образом сопоставим домен Bk-iji и множитель А 1. На основе дерева коэффициентов исходного всплеск-преобразования построим новое следующим обра -зом: верхние коэффициенты до уровня к оставим без изменения, а блоки Вы, г = 0,2Ї_1 заменим на XiBk-iji Построенное таким образом новое дерево коэффициентов обозна чим как F\. На основе описанной процедуры из F\ построим i , за тем из / — F3 и т.д. Заметим, что наборы коэффициентов Fi и д.. Fi+i различаются лишь начиная с уровня k + i (и ниже), а их верх ние части будут совпадать. Таким образом, мы определили оператор Т: Fi Fi+L В [24] показано, что при А 4= оператор Т будет сжимающим. По аналогии с (п. 2.1) для минимизации величины P(FQ,F ) где F = T(F ) минимизируем p(Fo1T(Fo)). С этой целью для каждого региона Вкі-, і = 0,2 — 1 будем искать наилучший домен Вк-г, : Применив метод наименьших квадратов (аналогично п. 2.3) можно определить: 2P Для такого всплеск-фрактального представления достаточно запомнить "верхние этажи" пирамиды до уровня к — 1 и 2к пар коэффициентов (ji, At). При восстановлении дерево коэффициентов F будет достраиваться последовательно сверху вниз, начиная с уровня к (рис. 4.2). Рис. 4.2. Принцип построения всплеск-фрактального преобразования Заметим, что при восстановлении дерева коэффициентов можно не останавливаться на заданном уровне, а строить новые слои, осуществляя тем самым фрактальную детализацию изображения. Для некоторых регионов можно найти удачные домены, т.е. величина Є{ = p{Bki, А Bk-i,ji) будет небольшой. Другие регионы не удастся хорошо аппроксимировать. Именно они и будут вносить основной вклад в общую ошибку аппрксимации.
Для уменьшения этой ошибки можно увеличить уровень к, с которого начинается разбиение дерева всплеск-коэффициентов на домены и регионы. Наряду с уменьшением ошибки при этом возрастает количество коэффициентов, которые надо запоминать, а значит коэффициент сжатия уменьшается. Для улучшения аппроксимационных свойств метода без уменьшения коэффициента сжатия предлагается проводить разбиение оставшейся части дерева всплеск-коэффициентов (с уровня к -+- 1) на регионы в зависимости от конкретного изображения. Такое разбиение будем проводить последовательно по следующему алгоритму: 1. Для всех регионов найти наилучшие домены и величины ошибок 6j. 2. Найти регион с самой большой ошибкой е3 = maxj. з запомнить "верхние этажи" пирамиды до уровня к — 1 и 2к пар коэффициентов (ji, At). При восстановлении дерево коэффициентов F будет достраиваться последовательно сверху вниз, начиная с уровня к (рис. 4.2). Рис. 4.2. Принцип построения всплеск-фрактального преобразования Заметим, что при восстановлении дерева коэффициентов можно не останавливаться на заданном уровне, а строить новые слои, осуществляя тем самым фрактальную детализацию изображения. Для некоторых регионов можно найти удачные домены, т.е. величина Є{ = p{Bki, А Bk-i,ji) будет небольшой. Другие регионы не удастся хорошо аппроксимировать. Именно они и будут вносить основной вклад в общую ошибку аппрксимации. Для уменьшения этой ошибки можно увеличить уровень к, с которого начинается разбиение дерева всплеск-коэффициентов на домены и регионы. Наряду с уменьшением ошибки при этом возрастает количество коэффициентов, которые надо запоминать, а значит коэффициент сжатия уменьшается. Для улучшения аппроксимационных свойств метода без уменьшения коэффициента сжатия предлагается проводить разбиение оставшейся части дерева всплеск-коэффициентов (с уровня к -+- 1) на регионы в зависимости от конкретного изображения. Такое разбиение будем проводить последовательно по следующему алгоритму: 1. Для всех регионов найти наилучшие домены и величины ошибок 6j. 2. Найти регион с самой большой ошибкой е3 = maxj. з 3. Запомнить корневой элемент найденного региона, а оставшуюся часть разбить на два (в одномерном случае) или четыре (в двумерном) новых региона. 4. Для этих новых регионов найти наиболее подходящие домены и вычислить погрешности. Поиск осуществляется среди тех домен (блоков), уровни которых на единицу меньше (выше), чем уровень соответствующих регионов. Т.е. для региона Вц множество домен определяется как {5і_і 7}.. 5. Если достигнут заданный коэффициент сжатия или заданная погрешность, то процесс фрактального сжатия завершен. Иначе перейти на п.2. Как видно из описания, данный алгоритм позволяет осуществлять компрессию данных с произвольным, заранее заданным, коэффициентом сжатия. Пример разбиения дерева всплеск коэффициентов (в одномерном случае) представлен на 3. Запомнить корневой элемент найденного региона, а оставшуюся часть разбить на два (в одномерном случае) или четыре (в двумерном) новых региона. 4. Для этих новых регионов найти наиболее подходящие домены и вычислить погрешности. Поиск осуществляется среди тех домен (блоков), уровни которых на единицу меньше (выше), чем уровень соответствующих регионов. Т.е. для региона Вц множество домен определяется как {5і_і 7}.. 5. Если достигнут заданный коэффициент сжатия или заданная погрешность, то процесс фрактального сжатия завершен. Иначе перейти на п.2. Как видно из описания, данный алгоритм позволяет осуществлять компрессию данных с произвольным, заранее заданным, коэффициентом сжатия. Пример разбиения дерева всплеск коэффициентов (в одномерном случае) представлен на рис. 4.3. В соответствии с этим алгоритмом кроме дополнительных коэффициентов (у "разбиваемых" регионов) необходимо также запоминать и саму схему разбиения. Кодирование двумерной схемы разбиения осуществляется относительно базового уровня к на основе рис. 4.4. Например, число 1 определяет, что исходный регион необходимо
