close

Вход

Забыли?

вход по аккаунту

?

Эффективный алгоритм фрактального сжатия изображений с использованием пространственно-чувствительного хеширования.

код для вставкиСкачать
Новые технологии
точников и описанные на уровне метаданных языка XML.
Рис.5
В работе предлагается новая концеп-
ставлены в виде точки трехмерного пространства, измерениями которого выступают: поведение пользователя (предпочтения и
навигация), технология (организация сети и
пользовательский терминал), внешнее окружение (время, местоположение, язык и т.п.).
Представление предметной области соответствует каждой возможной позиции пользователя в «пространстве адаптации».
Подготовка специализированных учебных пособий в соответствии с предлагаемым
подходом требует большей проработки и
унификации всех процедур, а также используемого инструментария. Однако, индивидуализация и предоставление студенту только необходимого объема информации на
каждом этапе обучения даже при отсутствии
непосредственного контакта с преподавателем, приведет к увеличению эффективности
процесса обучения.
ция описания адаптации гипермедиа системы. Состояния системы могут быть предЛитература
1. Ковалев И.В., Кустов Д.В. PLSA-адаптация модели пользователя в открытой информационнообразовательной среде // Телекоммуникации и информатизация образования. –2004. . – №6 (25).
2. Кустов Д.В. XML-ориентированная модель гипермедиа. // Вестник университетского комплекса:
Сб. научн. тр./Под общей ред. проф.Н.В. Василенко; Красноярск: ВСФ РГУИТП, НИИ СУВПТ. –2005. –
Вып. 3 (17). – С. 16-36.
3. Захарушкин В.Ф. Особенности создания информационного обеспечения корпорации // Электронный журнал «Исследовано в России», 2003.
4. Brusilovsky. P. Methods and techniques of adaptive hypermedia.// User Modeling and User Adapted Interaction, 1996. Vol. 6. – P. 87-129.
5. Cannataro M., Cuzzocrea A., Pugliese A. A probabilistic approach to model adaptive hypermedia systems. Proceedings of the International Workshop on Web Dynamics, 2001.
6. De Bra P., Aerts A., Houben G.J., Wu H. Making General-Purpose Adaptive Hypermedia Work. Proceedings of the WebNet Conference, 2000.
7. SaltonG., McGrill M.J. Introduction to Modern Information Retrieval. McGraw-Hill, New York, 1993.
ЭФФЕКТИВНЫЙ АЛГОРИТМ ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ
С ИСПОЛЬЗОВАНИЕМ ПРОСТРАНСТВЕННО-ЧУВСТВИТЕЛЬНОГО
ХЕШИРОВАНИЯ
С.В. Винокуров, инженер-программист, асп.
Тел.: 8-916-555-18-62 E-mail: sten@smartline.ru
Научный руководитель Ульянов М.В., проф., д.т.н., доц.
Московский государственный университет приборостроения и информатики
http://mgapi.ru/modules/news/article.php?storyid=25
In given article is result of the new approach of efficiency of algorithm of fractal compression which is based on a combination of ideas D. Saupe about data of a problem fractal compression to a problem of search of the nearest next element in multivariate interaction space, and modified method of the approached decision of a problem of search of the
nearest next element by means of spatially-sensitive hash.
Введение. Одной из проблем, возникающих при создании компакт-дисков, содержащих мультимедийные обучающие
62
программы и энциклопедии, является проблема размещения значительного объема
аудио- и видеоинформации. Обычный ком-
Открытое образование • 4/2006
Новые технологии
пакт-диск в 650 Мбайт без использования
компрессии может содержать либо 56 минут
качественного звука, либо 700 полноцветных изображений размером 640х480 пикселей, что явно не достаточно при современных требованиях к составу и объему мультимедийных обучающих программ.
Использование специальных методов
сжатия изображений и звука позволяет существенно увеличить объем хранимой информации. Так, например, известная мультимедиа энциклопедия компании Microsoft
— Microsoft Encarta много лет занимает лидирующие позиции среди аналогичных продуктов.
Причина подобной
популярности состоит не только в
удобстве использования и высоком
качестве статей но
и в большом количестве материалов,
размещенных на
диске. На диск записано примерно 7 часов
звука, 100 анимационных роликов, 850 масштабируемых карт, а также 7500 качественных фотографий.
Применяемые в данной области алгоритмы восстановления изображений должны
обладать, очевидно, хорошей временной
эффективностью, а соответствующие алгоритмы сжатия должны обеспечивать высокую степень сжатия без существенной потери качества изображения. Такими характеристиками обладают фрактальные алгоритмы, которые позволяют, затратив определенное время на подготовку диска и сжатие
информации, достичь высокого соотношения качества восстановленного изображения
к степени сжатия. При этом скорость восстановления изображения, в сравнении с
другими подходами, очень высока, а требования, предъявляемые к аппаратным ресурсам, значительно ниже, чем, например, в
традиционном алгоритме сжатия JPEG. Известным недостатком алгоритмов фрактального сжатия являются значительные временные затраты, в связи с чем разработка
новых фрактальных алгоритмов сжатия, обладающих лучшей временной эффективностью, является актуальной задачей.
Основная идея алгоритма. Фрактальное сжатие изображений основано на предположении, согласно которому в большинстве изображений можно обнаружить ло-
Открытое образование • 4/2006
кальное самоподобие различных его частей.
Устранение этой формы избыточности позволяет достичь высоких степеней компрессии. Изображение разбивается на множество
непересекающихся квадратных областей
определенного размера, называемых ранговыми блоками, и множество пересекающихся областей большего размера, называемых
доменными блоками. Далее производится
поиск аффинных преобразований, переводящих доменные блоки в ранговые. Коэффициенты этих преобразований и составляют фрактальный код изображения.
Этап поиска доменно-ранговых соответствий является наиболее трудоемким
этапом алгоритма фрактального сжатия изображений. При классическом подходе для
всех возможных комбинаций пар доменных
и ранговых блоков требуется решить задачу
поиска оптимальных коэффициентов аффинных преобразований (при этом критерием оптимальности коэффициентов является
минимум значения функции ошибки) и выбрать лучший вариант. И, хотя такой метод
дает наилучшее решение, его временная эффективность является неприемлемой с практической точки зрения. Однако задачу фрактального сжатия изображений можно свести
к задаче поиска ближайшего соседнего элемента в многомерном пространстве. В свою
очередь, приближенное решение задачи поиска ближайшего соседнего элемента может
быть эффективно найдено с использованием
специальной модификации алгоритма пространственно-чувствительного
хеширования. Комбинация этих двух идей и составляет основу для построения предлагаемого в
статье эффективного алгоритма, реализующего фрактальное сжатие изображений.
Сведение задачи фрактального сжатия изображений к задаче поиска ближайшего соседнего элемента в многомерном пространстве. Изложим кратко идею
D.Saupe [1], которая позволяет отойти от
полного перебора всех комбинаций пар доменных и ранговых блоков и, путем относительно эффективной предобработки, свести
эту задачу к задаче поиска ближайшего соседнего элемента в многомерном метрическом пространстве.
Предположим, что растровое изображение разделено на не перекрывающиеся ранговые блоки размером N × N (обычно 4 × 4
или 8 × 8 пикселей), и доменные блоки вдвое
большего размера. При этом над каждым доменным блоком выполняются операции усреднения и фильтрации так, чтобы его резуль-
63
Новые технологии
тирующий размер был равен размеру рангового блока N × N . Будем рассматривать каждый ранговый блок с номером m как вектор
Rm в линейном векторном пространстве
ℜn ,
где n = N × N , m = 1, K , nr , nr —
общее число ранговых блоков. Преобразование растрового квадратного изображения со
стороной квадрата длиной N в вектор дли2
ной N можно выполнить, например, построчным сканированием. Работа с векторами
вместо двумерных массивов значительно упрощает запись, без потери общности рассмотрения.
Обозначим через Dk вектор, представляющий доменный блок, где
nd
k = 1, K, nd , а
— общее число доменных блоков. Введем
в рассмотрение множество B , состоящее из
p независимых от изображения блоков, причем p < n . Представим их векторами
B1 , B2 ,..., B p ∈ ℜ n ,
которые выбираются
таким образом, чтобы они образовывали ортонормированный базис p -мерного подпроn
странства в ℜ . Их называют фиксированными базисными блоками. В процессе сжатия
изображения для каждого рангового блока
необходимо выполнить поиск по всем доменным блокам. При этом задача кодирования
рангового блока Rm формулируется как задача нахождения аффинных коэффициентов,
минимизирующих ошибку E ( Dk , Rm ) [1]:
E ( Dk , Rm ) =
p
min
a ,b1 ,...,b p ∈R
R m − ( a ⋅ D k + ∑ bk B k ) =
k =1
= min
Rm − Ax .
p +1
x∈ℜ
где А ― это
столбцы
которой
Dk , B1 , B2 ,..., B p , а
n × ( p + 1)
есть
x = (a, b1 , b2 ,..., b p ) ∈ ℜ p +1
(1)
матрица,
векторы
Rm a Dl : l = arg min {E ( Dk , Rm )}, a < 1.
Dk , k =1,...,nd
Введем в рассмотрение ортогональный
n
оператор P , который проецирует ℜ в подпространство ℑ с базисом B1 , B2 ,..., B p .
Rm имеет уникальное разлоRm = ORm + PRm , где оператор O
Ранговый блок
жение
проецирует свой операнд на ортодополнение
ℑ⊥ .
Для Z = ( z1 ,..., z n ) ∈ ℜ
делим оператор
φ (Z ) =
— вектор ко-
n
\ ℑ,
опре-
OZ
.
OZ
(2)
В данных обозначениях базовый результат, полученный Saupe в [3], имеет вид:
2
E ( Dk , Rm ) = Rm ,φ ( Rm ) 1 − φ ( Dk ),φ ( Rm ) ,
где
⋅,⋅
— скалярное произведение двух век-
торов. Таким образом, задача о минимизации
ошибки E ( Dk , Rm ) для фиксированного
Rm
и всех доменных блоков Dk может рассматриваться с точки зрения углового критерия. Минимум E ( Dk , Rm ) достигается тогда, когда скалярное произведение векторов
φ ( Dk ),φ ( Rm )
2
максимально, так как:
φ ( Dk ), φ ( Rm )
2
=
= cos 2 ∠(φ ( Dk ), φ ( Rm )).
Это означает необходимость минимизации угла ∠(φ ( Dk ),φ ( Rm )) , или, что экви-
валентно, ∠(ODk , ORm ). Таким образом,
задача фрактального сжатия изображения (в
смысле поиска Dk для Rm ) сводится к задаче о поиске ближайшего соседнего к данному
ранговому блоку — вектору Rm доменного
блока — вектора
эффициентов. Данная задача должна быть решена для всех доменных блоков Dk , и блок,
который дает наименьшее значение ошибки
E ( Dk , Rm ) , выбирается при условии, что
значение a для данного блока обеспечивает
сходимость процесса декодирования (т.е.
64
a < 1)
ве
Dk
в линейном пространст-
ℜ n \ ℑ.
Понятие
пространственно-чувствительного хеширования. В работе [3] P.Indyk
и R.Motwani представлен метод решения задачи приближенного поиска ближайшего
элемента, основанный на пространственно
чувствительном хешировании (метод LSH —
locality sensitive hashing). Авторы LSH предлагают использовать пространственное хе-
Открытое образование • 4/2006
Новые технологии
ширование для организации поиска в приложениях баз данных, распознавании образов,
поиска в архивах документов. В данной статье предлагается модифицировать метод пространственно чувствительного хеширования
для организации поиска ближайшего соседнего элемента при фрактальном сжатии изображений.
Вначале рассмотрим кратко основную
идею
метода
пространственночувствительного хеширования применительно к поиску ближайших доменных блоков. Для множества точек S , содержащего
Dk⊥ = φ ( Dk )
проекции доменных блоков
и
ранговых
блоков
Rm⊥ = φ ( Rm )
на
ℜn \ ℑ ,
с мерой расстояния ∆ (в нашем
случае Евклидовой), семейство LSH функций определено в [3] следующим образом:
Множество хеш функций
H = {h : S → U }
называется
для ∆ ,
если для любой проекции рангового и домен-
(r1 , r2 , p1 , p2 ) -чувствительными
ного блока
няется
если
Rm⊥ , Dk⊥ ∈ S
на
Dk⊥ ∈ B( Rm⊥ , r1 ),
ℜn \ ℑ
выпол-
то
PrH [h( Rm⊥ ) = h( Dk⊥ )] ≥ p1 ,
⊥
⊥
если Dk ∉ B ( Rm , r2 ), то
PrH [h( Rm⊥ ) = h( Dk⊥ )] ≤ p2 .
где
r
B ( x, r )
— гиперсфера радиусом
∆ с центром
⊥
PrH [h( Rm ) = h( Dk⊥ )] —
в смысле меры расстояния
в точке x , а
вероятность того, что хеш функция образует
коллизию для данных проекций рангового и
⊥
⊥
доменного блока Rm и Dk .
Применение
пространственночувствительного хеширования для решения задачи фрактального сжатия изображений. Для того, чтобы пространственночувствительная функция хеширования была
полезной с точки зрения применимости к
фрактальному сжатию изображений, она
должна
удовлетворять
неравенствам
p1 > p2 и r1 < r2 .
В специальной литературе принято
обозначать задачу приближенного поиска
соседнего элемента как ( τ ,c)-NN задачу,
при этом r1 = τ и r2 = c ⋅ τ . Покажем, как
Открытое образование • 4/2006
пространственно-чувствительные функции
могут быть использованы для решения
( τ ,c)-NN задачи при фрактальном сжатии:
для данного семейства H хэш-функций,
обладающих параметрами ( r1 , r2 , p1 , p 2 ) ,
увеличим разрыв между «высокой» вероятностью p1 и «низкой» вероятностью p2
путем соединения нескольких функций. В
частности, для параметра K , значение которого будет установлено ниже, определим
Ψ = {g : S → U K }
семейство функций
g ( Dk⊥ ) = (h1 ( Dk⊥ ),..., hK ( Dk⊥ )),
где hi ∈ H . Для целого числа L выберем
L функций g1 ,..., g L из Ψ , независимо и
так, что
равномерно, случайным образом. Во время
шага предварительных вычислений сохраним каждую проекцию доменного блока
Dk⊥ ∈ S в наборе g j ( Dk⊥ ),
j = 1,..., L. Так как общее
для каждого
число таких
множеств может быть велико, оставим только непустые наборы путем возврата к классическому хешированию. Для того чтобы
обработать ранговый блок Rm , производим
поиск
среди
всех
множеств
g1 ( Rm⊥ ),..., g L ( Rm⊥ ) .
Так как возможно
(хотя и маловероятно) что общее количество
доменов, сохраненных в этих множествах
велико, то поиск домена прерывается после
нахождения 3L элементов (включая дубликаты). Пусть
D1⊥ ,..., Dt⊥
— найденные эле-
менты. Для каждого домена D1Kt возвращаем ответ «ДА» (т.е. данный домен является потенциальным кандидатом построения
преобразования в ранговый блок Rm ), если
D1Kt ∈ B( Rm⊥ , r2 ),
иначе возвращаем от-
вет «НЕТ». Параметры K и L выбираются
так, чтобы гарантировать, что следующие
два свойства выполняются с заданной вероятностью:
1.Если существует
g j ( Dk* ) = g j ( Rm⊥ )
j = 1...L.
то
Dk* ∈ B( Rm⊥ , r1 ) ,
для некоторого
2.Общее количество коллизий
точками из
S
—
B( Dk⊥ , r2 )
Rm⊥
с
меньше чем
65
Новые технологии
3L
(параметр определен эмпирическим путем в [4]) то есть:
L
∑ (S − B( D
⊥
k
j =1
, r2 )) ∩ g −j 1 ( g i ( Dk⊥ )) < 3L.
Если выполняются оба свойства, то алгоритм является корректным. Отсюда следует ([3] теорема 5), что если установить
K = log(1 / p 2 ), и L = n ρ , где
ln(1 / p1 )
,
ρ=
ln(1 / p2 )
(3)
то свойства (1) и (2) выполняются с постоянной вероятностью. Таким образом, получаем следующую теорему [ 4 ] , которая
касается зависимости эффективности решения ( τ , c)-NN задачи при фрактальном сжатии изображений от параметров LSH:
Предположим, существует
(τ , c ⋅ τ , p1 , p2 ) -чувствительное семейство функций хеширования H для меры расстояния ∆ . Тогда существует алгоритм для решения ( τ ,c)-NN задачи для ме∆,
ры
который
использует
O(dnd + nd
ботки
ρ
1+ ρ
)
одного
O ( nd )
памяти, с временем образапроса, определяемым
вычислений
расстояния
и
ρ
O(nd log(1 / p2 ) ⋅ nd ) вычислений хешфункций из H , где ρ определен как (3).
Адаптация
пространственночувствительных хеш-функций к фрактальному сжатию изображений на основе
p-устойчивых распределений. Устойчивые
распределения [5] определяются как пределы нормализованных сумм независимых
равномерно распределенных случайных переменных (ниже дано альтернативное определение). Наиболее известный пример устойчивого распределения — это нормальное
(гауссово) распределение. Однако, класс таких распределений является значительно
более широким. Распределение µ над ℜ
называется p-устойчивым, если существует
p ≥ 0 такое, что для любых d действи-
тельных чисел
X 1 ,..., X d
v1 ,..., vd
с распределением
переменная
∑ivi X i
пределение,
как
p 1/ p
(∑i vi )
и переменных
X,
где
имеет такое же раси
X
переменная
— случайная пе-
ременная с распределением
66
µ , случайная
µ.
Известно [5], что устойчивые распределения существуют для любого p ∈ (0,2]. В
частности гауссово (нормальное) распределение µ G , определенное как функция
плотности вероятности
g ( x) =
1 − x2 / 2
e
,
2π
является 2-устойчивым.
Заметим, что с практической точки зрения, несмотря на недостаток закрытых форм
функций распределения плотности, известно
[6], что можно создать p-устойчивую случайную переменную из двух независимых
случайных переменных, равномерно распределенных на интервале [0,1].
Используя p-устойчивые распределения, построим семейство хэш-функций H ,
адаптированное к фрактальному сжатию
изображений. Интуитивно, семейство хешфункций должно быть пространственночувствительным, т.е. если два вектора
Rm⊥ , Dk⊥
близки друг к другу (значение
Rm⊥ − Dk⊥
p
относительно невелико), то
они должны с большой вероятностью вызывать коллизию (иметь одно и то же значение
хеш-функции) и, если они расположены далеко друг от друга, то вероятность коллизии
должна быть мала. Пусть a — вектор размерности d , элементы которого выбираются независимо из p-устойчивого распределения. Скалярное произведение
a, Rm⊥
про-
ецирует каждый вектор на множество действительных чисел. Из p-устойчивости следует, что для двух векторов
ние
между
их
a, Rm⊥ − a, Dk⊥
Rm⊥ − Dk⊥
p
X,
где
Rm⊥ , Dk⊥
расстояпроекциями
распределено
X
как
— это случайная
переменная, выбранная из p-устойчивого
распределения. Если «разделить» множество
действительных чисел на подмножества
равного размера r и определить значение
хеш-функции для вектора в зависимости от
того, на какое подмножество он проецируется, то интуитивно ясно, что такая хешфункция будет пространственно чувствительна в описанном выше смысле.
Формально,
каждая
хеш-функция
Открытое образование • 4/2006
Новые технологии
ha ,b ( v ) : ℜ d → Ν
размерности
d
отображает вектор
v
Rm⊥
(проекция рангового
⊥
или доменного Dk блока) на множество
целых чисел. Каждая хеш-функция в семействе однозначно определяется выбором случайного вектора a , определенного выше, и
действительного числа b , выбранного случайным образом из диапазона [0, r ] . Для
a, b
данных
определим хеш-функцию
ha,b
следующим образом [7]:
(4)
Теперь вычислим вероятность коллизии
хеш-функции, выбранной случайно согласно
описанным выше соображениям, для двух
векторов
Пусть
f p (t )
обозначает
плотность вероятности абсолютного значения p-устойчивого распределения. Для двух
векторов
Rm⊥ , Dk⊥
пусть
c = Rm⊥ − Dk⊥
p
.
Для случайно выбранного вектора a , элементы которого взяты из p-устойчивого распределения,
a, Rm⊥ − a, Dk⊥
распреде-
лено как cX , где X — случайная переменная, выбранная из p-устойчивого распределения. Так как b выбрано случайно из
диапазона [0, r ] , легко увидеть [4], что
p (c) = Pra ,b [ha ,b ( Rm⊥ ) = ha ,b ( Dk⊥ )] =
=∫
r
0
.
t
t
1
f p ( )(1 − )dt.
c
r
c
Для фиксированного параметра r вероятность коллизии монотонно уменьшается
с ростом
c = Rm⊥ − Dk⊥
p
. Согласно опре-
делению, данному в начале параграфа, семейство хеш-функций ha ,b ( v ) является
(r1 , r2 , p1 , p2 ) -чувствительным для
p1 = p (1) и p2 = p (c) при r2 / r1 = c.
Параметр r не был четко определен, так как
он зависит от значений c и p . Для каждого
данного c задача заключается в выборе такого конечного значения r , которое минимизирует значение
ция
Dk⊥ = φ ( Dk )
на ортодополнение
ℑ⊥ .
Определение оператора φ ( x) было дано выше (2). Далее, для полученных точек
Dk⊥ ∈ ℜ n \ ℑ
вычисляются и сохраняются
⊥
⎢ a, v + b ⎥
ha ,b ( v ) = ⎢
⎥.
r
⎣
⎦
Rm⊥ , Dk⊥ .
Алгоритм фрактального сжатия при
помощи пространственно чувствительного хеширования (FracLSH). Предложенный алгоритм состоит из двух этапов: на
этапе предварительных вычислений для всех
векторов, представляющих доменные блоки,
вычисляется их ортонормированная проек-
ρ.
Открытое образование • 4/2006
значения хеш-функций g i ( Dk ) по формуле (4).
На этапе поиска доменно-ранговых соответствий для данного рангового блока вычисляется ортонормированная проекция
Rm⊥ = φ ( Rm )
на ортодополнение
ℑ⊥ .
Вы⊥
числяется значение хеш-функций g i ( Rm ) и
производится линейный поиск в таблицах
хеш-функций доменных блоков, вычисленных ранее.
Благодаря свойствам пространственночувствительных хеш-функций, при совпадении хеш-значений для рангового и доменного вектора, существует очень высокая вероятность того, что данные вектора лежат
близко друг другу в заданном (в нашем случае в Евклидовом) метрическом пространстве. Для M найденных доменных блоков
кандидатов производится вычисление ошибки E ( Dl , Rm ) , l = 1,..., M по формуле (1)
и выбирается наиболее подходящий блок. Таким образом, мы избегаем необходимости решать задачу для каждой пары доменноранговых блоков, а отбираем лишь несколько
кандидатов, которые с большой вероятностью
дадут решение, близкое к оптимальному.
Этим и достигается существенное повышение
временной эффективности предлагаемого алгоритма.
Оценка временной эффективности алгоритма FracLSH. Оценка временной эффективности фрактального сжатия с использованием пространственно-чувствительного
хеширования основывается на существующих оценках алгоритма поиска ближайшего
соседнего элемента в многомерном метрическом пространстве. Время обработки одного запроса на поиск подходящего доменного блока для данного рангового блока оп-
67
Новые технологии
ределяется количеством операций вычисле-
∆( Rm⊥ , Dk⊥ )
межния функции расстояния
ду проекциями рангового и доменным блоков, и количеством операций вычисления
⊥
хеш-функции g i ( Dk ) . Общее число запросов равно количеству ранговых блоков.
В работе [8] показано, что при соответствующем выборе параметров алгоритма LSH
для одного запроса количество операций
вычисления функции расстояния определяρ
ется как O ( nd ) , а количество операций
вычисления хеш-функции, соответственно,
как
ρ
O(nd log1/ p2 nd ) ,
количество
ρ=
ln(1 / p1 )
ln(1 / p2 )
где
доменных
для
nd
— общее
блоков,
(r1 , r2 , p1 , p2 ) -
чувствительной хеш-функции, p1 определена
как вероятность того, что расстояние между
двумя точками в заданном метрическом пространстве не более r1 при условии, что хешфункция дает коллизию, p2 — это вероятность того, что расстояние между двумя точками больше r2 при условии, что коллизии не
происходит
(строгое
определение
(r1 , r2 , p1 , p2 ) -чувствительности дано в [4]).
68
Алгоритм LSH для построения промежуточных
структур
данных
требует
O(dnd + nd
1+ ρ
)
слов памяти, где d — это
размерность ортонормированной проекции
D ⊥j
доменного блока на ортодополнение
ℑ⊥ .
Таким образом, достигается сублинейное время обработки одного рангового блока, что является большим шагом
вперед по сравнению с классическими
алгоритмами фрактального сжатия.
Реализация и результаты. Реализация описанного выше метода показала
свою эффективность на большом наборе
тестовых данных. По сравнению с полным перебором достигнуто увеличение
времени работы алгоритма в несколько
сотен раз. Для реального сравнения с
предложенным алгоритмом был выбран
один из наиболее эффективных, из известных в настоящее время, алгоритм
FracANN, основанный на использовании
kd-деревьев для решения задачи поиска
ближайшего соседнего элемента. Алгоритм FracANN создает промежуточную
структуру данных — kd-дерево, размером O ( nd ) и глубиной O (log(nd )) .
Общее время конструирования такого
Открытое образование • 4/2006
Новые технологии
дерева
асимптотически
составляет
O(log(nd ) ⋅ nd ) [9].
На рис. 1 приведена диаграмма зависимости качества восстановленного
изображения (PSNR, dB), определяемого
в соответствии с [10], от времени сжатия
изображения lena.jpg размером 256x256
пикселей предложенным алгоритмом и
алгоритмом FracANN. Второй алгоритм
является адаптацией известной библиотеки ANN [11], которая реализует поиск
ближайшего соседнего элемента, используя один из вариантов реализации kdдерева.
Рис. 1. Сравнение алгоритмов FracLSH
и FracANN
Изображение разбивалось на ранговые
блоки размером 4x4 пикселя. В обоих случаях испытания проходили на компьютере с
процессором Pentium-4 2,4 GHz без поддержки технологии HyperThreading. Изменение соотношения «время сжатия — качество» достигалось варьированием параметров K, L, M предложенного алгоритма и параметров M, ε алгоритма FracANN. Как
видно из рис. 1, при малом времени сжатия
алгоритм FracLSH опережает алгоритм FracANN по качеству восстановленного изображения. При одинаковом качестве восста-
новленного изображения (PSNR=31dB) время работы предложенного алгоритма в 3
раза меньше времени работы алгоритма FracANN. При дальнейшем увеличении времени сжатия графики сливаются в одну линию,
обеспечивая одинаковое соотношение для
восстановленного изображения.
Заключение. В данной работе представлен эффективный алгоритм фрактального сжатия, позволяющий значительно улучшить временные характеристики процесса
сжатия изображений при приемлемом качестве восстановления. Эксперименты показывают, что предложенная схема – поиск
ближайшего соседнего элемента с использованием
пространственно-чувствительного
хеширования – обладает более высокими
характеристиками по сравнению с традиционными схемами фрактального сжатия и
может успешно конкурировать с лучшими
современными алгоритмами в данной области. Очевидно, что предложенный алгоритм
может применяться и в комбинации с квадродеревом и другими схемами разбиения
изображения, что открывает пути дальнейшего увеличения производительности и
улучшения качества восстановленного изображения.
Одной из областей использования алгоритма FracLSH может быть подготовка компакт-дисков, содержащих мультимедийные
обучающие программы. Алгоритм обеспечивает хорошее соотношение качества восстановленного изображения к степени сжатия и высокую скорость декомпрессии, что
особенно актуально для данной области
применения.
Литература
1. Saupe, D., Accelerating fractal image compression by multi-dimensional nearest neighbor search, in:
Proceedings DCC’95 Data Compression Conference, J. A. Storer and M. Cohn (eds.), IEEE Comp. Soc. Press,
March 1995.
2. Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni. Locality-Sensitive Hashing Scheme
Based on p-Stable Distributions. Symposium on Computational Geometry 2004: 253-262.
3. P. Indyk and R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality.
Proceedings of the Symposium on Theory of Computing, 1998.
4. Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni. Locality-Sensitive Hashing Scheme
Based on p-Stable Distributions. Symposium on Computational Geometry 2004: 253-262.
5. V.M. Zolotarev. One-Dimensional Stable Distributions. Vol. 65 of Translations of Mathematical Monographs, American Mathematical Society, 1986.
6. J.M. Chambers, C.L. Mallows, and B. W. Stuck. A method for simulating stable random variables. J.
Amer. Statist. Assoc., 71:340-344, 1976.
7.Винокуров С. В. Построение пространственно-чувствительных хеш-функций, адаптированных к
задаче фрактального кодирования изображений. Методы и модели автоматизации управления, Сборник
научных трудов МАДИ – ГТУ, 2006.
8. Rajeev Motwani, Assaf Naor, Rina Panigrahy. Lower bounds on Locality Sensitive Hashing.
http://research.microsoft.com/research/theory/naor/home page%20files/lsh-new.pdf
Открытое образование • 4/2006
69
Новые технологии
9. S. Arya and H. Y. Fu. Expected-case complexity of approximate nearest neighbor searching. In Proc.
11th ACM-SIAM Sympos. Discrete Algorithms, pages 379--388, 2000. Extended version appears as HKUST
Technical Report HKUST-TCSC2000 -03, URL: http://www.cs.ust.hk/tcsc/RR.
10. Saupe, D., Hamzaoui, R., Hartenstein, H., Fractal image compression - An introductory overview, in:
Fractal Models for Image Synthesis, Compression, and Analysis, ACM~SIGGRAPH'96 Course Notes, 66 p.
11. ANN: Approximate Nearest Neighbors, http://www.cs.umd.edu/~mount/ANN.
ВОПРОСЫ АВТОМАТИЗАЦИИ КОНТРОЛЯ ЗНАНИЙ
ПРИ ПОДГОТОВКЕ СОВРЕМЕННЫХ ИТ-СПЕЦИАЛИСТОВ
С.В. Синицын, к.т.н., доц., зав. каф. Кибернетики,
Тел.:(495)3242885,E-mail: sintzyn@cyber.mephi.ru
Н.Ю.Налютин, асс. каф. Кибернетики,
Тел.: (495)3242885, E-mail: nalutin@cyber.mephi.ru
Е.А.Петухова, ст. преп., зам. декана фак. Кибернетики,
Тел.: (495)3242885, E-mail: helene@cyber.mephi.ru
С.М.Садчиков, ст. преп., зам. зав. каф. Кибернетики
Тел.: (495)3239326, E-mail: sadchikov@cyber.mephi.ru
Московский инженерно-физический институт (государственный университет),
http://www.mephi.ru
The question of education quality IT-students is considered. Article describes models
and methods of development and operational experience of systems of the interactive solving for multistage educational tasks.
Анализ
дипломных работ и
распределения
выпускников кафедры Кибернетики МИФИ показывает, что в последние годы им все
чаще приходится
участвовать в коллективных разработках программного обеспечения, осуществлять сопровождение и модернизацию больших программных комплексов самого различного назначения.
Можно назвать широкий диапазон направлений: от банкоматов, микропроцессорных систем и бортового ПО до документооборота предприятий и обучения. В связи с
этим для кафедры Кибернетики особое значение приобретает аспект технологической
подготовки будущих инженеров-математиков. Под технологической подготовкой
понимается процесс получения студентами
знаний и навыков в области создания программного продукта. В технологической
подготовке мы видим совокупность приемов, подходов и методов к решению задач,
вне зависимости от дальнейшей специализации студента.
70
Контроль усвоения студентами знаний
и умений решать классические учебные задачи или выполнять практические учебные
задания является неотъемлемой частью процесса обучения. И при таком контроле часто
оказывается необходимой проверка, следует
ли студент при решении требуемому методу
или технологии. Как правило, невозможно
узнать, как выполнялось задание, сверяя только конечный результат. А на этапе
начальной
подготовки специалиста важно
выработать у него
навыки применения верных технологий при выполнении заданий при изучении, как фундаментальных дисциплин, так и специальных,
прикладных.
В области программных разработок
редко существуют такие практические задачи, которые можно выполнять единственно
допустимым способом, без вариаций. Большинство задач допускают решение несколькими методами полностью или с помощью
вариации на некоторых этапах. Разрабатывая схему контроля выполнения задания,
Открытое образование • 4/2006
1/--страниц
Пожаловаться на содержимое документа