Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании
Пропонується новий метод стиснення, що полягає в багатомасштабному поділі зображення на контур і фон. Виділення контуру здійснюється в кожному масштабі на основі симетричного низькочастотного фільтру, а фон представлено вейвлеткоефіцієнтами. Показано, що даний метод порівняно з вейвлетпере- творенн...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2006 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/206814 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2006. — № 3. — С. 89-101. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860257899530420224 |
|---|---|
| author | Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. |
| author_facet | Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. |
| citation_txt | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2006. — № 3. — С. 89-101. — Бібліогр.: 16 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Пропонується новий метод стиснення, що полягає в багатомасштабному поділі зображення на контур і фон. Виділення контуру здійснюється в кожному масштабі на основі симетричного низькочастотного фільтру, а фон представлено вейвлеткоефіцієнтами. Показано, що даний метод порівняно з вейвлетпере- творенням є більш швидким і дозволяє одержати більш високий коефіцієнт стиснення зображення.
The new method of compression consisting in multiscale separation of the map on a loop and a hum noise is offered. Selection of a loop is carried out in each scale on the basis of a symmetric lowfrequency filter, and the hum noise is represented by wavelet-factors. It is shown, that the given method, in comparison with wavelet conversion is faster and allows to receive higher aspect ratio of the map.
|
| first_indexed | 2025-12-07T18:51:04Z |
| format | Article |
| fulltext |
© В.Г. ИВАНОВ, М.Г. ЛЮБАРСКИЙ, Ю.В. ЛОМОНОСОВ, 2006
Проблемы управления и информатики, 2006, № 3 89
УДК 621.391
В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов
СЖАТИЕ ИЗОБРАЖЕНИЙ НА ОСНОВЕ
КОМПЕНСАЦИИ КОНТУРОВ
ПРИ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИИ
Введение. Технологии хранения и доставки информации в виде изображений
стали нормой нашей повседневной жизни.
Колоссальная избыточность такого рода информации давно уже сделала ее
традиционным объектом научного штурма, цель которого — найти пути к осво-
бождению от этой избыточности [1–6]. Особенно быстрый период развития этих
технологий наблюдается в последнее десятилетие, когда были созданы новые
высокоэффективные форматы хранения графических данных, основанные на
методах вейвлет-преобразований и автоматической сегментации [7–12]. Приме-
ром такого подхода является формат DjVu компрессии, в котором изображение
разделяется на контур (передний план) и фон (задний план), которые кодируются
соответственно JB2 и IW44 методами. JB2 — модификация факсимильного стан-
дарта JBIG2, а IW44 использует вейвлет-прогрессивные методы, равнозначные
JPEG-2000 в отношении шумового коэффициента, но декодер которого более эф-
фективен, занимает меньше памяти и оптимизирован для более быстрой работы.
Однако этот формат сложен в реализации и ему присущи недостатки парамет-
рических моделей кластер-анализа. Также очевидно, что исследователи при-
ближаются к пределу эффективности сжатия изображений и в теории и на прак-
тике остается все меньше потенциала, содержащегося в этой области. Поэтому
весьма актуальна задача исследования новых схем сжатия, которые сегодня или
в ближайшем будущем позволят получить весомые результаты в кодировании
изображений.
В данной работе авторы развивают и модифицируют метод сжатия изобра-
жений с помощью многомасштабной компенсации контуров (Multi Scale Edge
Compensation — MSEC) или, другими словами, на основе компенсации контуров
при вейвлет-преобразовании. Этот метод является существенной модернизацией
вейвлет-сжатия, основанного на быстром алгоритме Малла [13, 14]. MSEC-метод
можно отнести к технике кодирования изображений второго поколения, которая
основывается на интеллектуальных методах сегментации и автоматической клас-
сификации изображений [8, 15, 16].
Вейвлет-преобразование дискретных сигналов. Алгоритм Малла.
Вейвлет-преобразование дискретных сигналов основано на многомасштабном
анализе — разложении сигналов конечной энергии, определенных на числовой
оси, по ортонормированному (или биортогональному) очень специальному бази-
су в пространстве ).(2 ℜL Этот базис, элементы которого называются вейвлетами,
обладает следующими замечательными свойствами.
1. Каждый вейвлет-базис порождается всего одной функцией )(tψ и состоит
из ее масштабных преобразований, кратных числу 2, и целочисленных сдвигов по
координатам:
.,2,1,0,,
2
2)( 2/ ±±=
−ψ=ψ − jiitt
j
j
ij
90 ISSN 0572-2691
Здесь индекс j определяет масштаб вейвлета, i — его расположение, а мно-
житель 2/2 j− нужен для нормировки.
2. Порождающая функция ),(tψ а значит, и каждый вейвлет )(tijψ локализо-
ваны в пространстве, в отличие, например, от экспонент, используемых в рядах
Фурье. Это свойство объясняет название: «вейвлет» переводится как «маленькая
волна».
3. Возможность конструировать порождающую функцию, а это основная за-
дача математической теории вейвлетов, позволяет получить симметричные глад-
кие вейвлеты с большим числом нулевых моментов: ∫
∞
ψ= ,)( dtttM n
n .,1,0 =n
Масштабируемость и пространственная однородность вейвлет-базиса позво-
лили Малла определить преобразование дискретных сигналов, тесно связанное с
вейвлет-базисом, а также указать для этого простую и эффективную в вычисли-
тельном смысле рекуррентную процедуру [14].
Пусть задан дискретный сигнал },{ ix определенный на множестве целых чи-
сел i. Малла исходит из так называемой масштабной функции ),(tϕ которая зада-
ет порождающую вейвлет-базис функцию ).(tψ В простейшем случае масштаб-
ная функция — это «ступенька», равная единице на интервале )1,0[ и нулю во
всех остальных точках числовой оси. Такой масштабной функции соответствует
вейвлет Хаара. По сути алгоритм Малла дает разложение по вейвлет-базису
функции ,
2
)( 0
0
0
−ϕ= ∑ itctx i
i
где .0
ii xc = Считается, что эта функция имеет
(относительно ))(tϕ масштаб 0.
На первом шаге алгоритма вычисляются коэффициенты }{ 0
id разложения
функции )(0 tx по вейвлетам масштаба .0=j Остаток ),()()( 001 tytxtx −= где
),()( 0
0
0 tdty ii
i
ψ= ∑ уже не содержит вейвлеты масштаба 0, т.е. является функци-
ей масштаба 1 и, следовательно, представим в виде .
2
)( 1
1
1
−ϕ= ∑ itctx i
i
Второй шаг алгоритма отличается от первого только тем, что роль исходного
сигнала )(0 tx играет остаток )(1 tx масштаба 1. Далее находят коэффициенты
}{ 1
id разложения функции )(1 tx по вейвлетам масштаба ,1=j функцию =)(1 ty
)(1
1 td ii
i
ψ= ∑ и остаток ),()()( 112 tytxtx −= имеющий масштаб 2, и т.д.
Переход от коэффициентов }{ n
ic к коэффициентам }{ 1+n
ic и }{ 1+n
id на n-м
шаге алгоритма осуществляется по формулам
n
kik
k
n
i cgd +
+ ∑= 2
1 и ,2
1 n
kik
k
n
i chc +
+ ∑= (1)
где конечные наборы чисел }{ khh = и },{ kgg = связанные соотношением =ig
,)1( i
i h−−= взаимно-однозначно определяются масштабной функцией и называ-
ются соответствующими ей квадратурными зеркальными фильтрами.
Отметим, что применение фильтра h к функции )(txn дает функцию )(1 txn+
с характерным масштабом изменения, вдвое большим, чем у ).(txn Таким обра-
Проблемы управления и информатики, 2006, № 3 91
зом, фильтр h выделяет из сигнала )(txn низкочастотную составляющую ),(1 txn+
а фильтр g — высокочастотную: ).(1 tyn+ Из приведенных формул следует, что
в соответствии с разделением частотного диапазона на две равные части коли-
чество коэффициентов для каждого диапазона уменьшается вдвое. Так что на
каждом шаге алгоритма Малла суммарное количество коэффициентов }{ 1+n
ic и
}{ 1+n
id совпадает с количеством коэффициентов }.{ n
ic
Зная коэффициенты разложения исходной функции )(0 tx по вейвлет-базису
до масштаба m и остаток ),(1 txm+ можно восстановить ).(0 tx Это делается поша-
гово с помощью рекуррентной формулы
.1
2
1
2∑ ∑ +
−
+
− +=
k k
n
kki
n
kki
n
i dgchc (2)
Формулы (1), (2) определяют прямое и обратное вейвлет-преобразование по
алгоритму Малла.
Cказанное относится и к ортогональному вейвлет-базису. Но в целях увели-
чения количества нулевых моментов на практике чаще используется биортого-
нальный вейвлет-базис.
В терминах алгоритма Малла это означает, что имеется две пары квадратурных
зеркальных фильтров },{ khh = },{ kgg = и },
~
{
~
khh = },~{~
kgg = первая исполь-
зуется в формулах разложения (1), вторая — в формуле восстановления, анало-
гичной (2),
.~~ 1
2
1
2∑ ∑ +
−
+
− +=
k k
n
kki
n
kki
n
i dgchc (3)
Фильтры h и h
~ имеют сравнительно простую аналитическую форму в тер-
минах их преобразований Фурье )(ωh и ).(
~
ωh Коэффициенты этих фильтров
(см. ниже) находятся численным образом с помощью обратного преобразования
Фурье. Обычно используется следующее семейство фильтров:
,
2
sin
2
12)(;
2
12)(
~ 2
2
,,
ω−
−ωω
ω
+
=ω
+
=ω im
m
nmi
mn
ni
mn ePeheh (4)
где ss
sm
m
s
m xCxP +−
−
=
∑= 1
1
0
)( — многочлен Дебеши.
Эти фильтры симметричны, а соответствующие им разлагающие вейвлеты
имеют достаточно нулевых моментов, число которых увеличивается с ростом па-
раметра n. Гладкость восстанавливающих вейвлетов повышается при увеличении
параметра m. Увеличение параметров сопровождается усложнением поведения
вейвлета и соответственно ростом длины фильтра.
Для вейвлет-преобразования изображений, когда входной сигнал имеет два
индекса, т.е. представляет собой матрицу, одномерное вейвлет-преобразование
применяется сначала к каждой строке, а затем — к полученным столбцам. Это
показано на рис. 1.
Изображение h g
hh hg
gh gg
Рис. 1
92 ISSN 0572-2691
Первый прямоугольник представляет собой исходное изображение, вто-
рой — два прямоугольника, вдвое меньшей ширины, полученные применением
фильтров h и g к каждой строке изображения. И наконец, третий квадрат состоит
из четырех равных прямоугольников, полученных из прямоугольников h и g при-
менением этих фильтров к каждому столбцу. Это первый шаг алгоритма Малла
для изображений. Прямоугольники hg, gh и gg, содержащие высокочастотную
часть изображения, запоминаются, а к прямоугольнику hh, содержащему низкоча-
стотную часть изображения, применяются фильтры так же, как к исходному изоб-
ражению, и т.д.
Метод многомасштабной компенсации контуров (Multi-Scale Edge Com-
pensation — MSEC). Сжатие изображения при вейвлет-преобразовании в основ-
ном осуществляется за счет исключения избыточной информации, связанной с
гладкостью изображения. В общем случае, по крайней мере, на первом-втором
шагах алгоритма Малла, высокочастотные прямоугольники hg, gh и gg содержат
много малых значений, их можно при восстановлении без ущерба для качества
изображения заменить нулями или записать более короткими словами. Чем глаже
изображение, тем меньше информации содержится в высокочастотных прямо-
угольниках и тем лучше сжатие. По этой же причине сжатие улучшается, если ис-
пользовать вейвлет с бóльшим числом нулевых моментов. Однако фильтры, отве-
чающие таким вейвлетам, очень длинные, что резко увеличивает необходимое ко-
личество арифметических операций. Поэтому совершенно естественна идея, из
которой, по-видимому, исходили авторы метода MSEC. Если заранее из изобра-
жения удалить резкие перепады яркости и сохранить их отдельно, то оставшаяся
часть изображения будет сжиматься очень хорошо.
Совокупность точек, в которых имеются большие перепады яркости, принято
называть эскизом, или контуром изображения. Это наиболее информативная для
глаза человека часть изображения. Оставшуюся после выделения контура часть
изображения называют фоном. При этом совершенно ясно, что если контур удален
из изображения, то высокочастотные прямоугольники почти не содержат инфор-
мации, поэтому и нет необходимости вычислять входящие в них коэффициенты.
Алгоритм MSEC-разложения строится таким образом.
1. Разделить изображение на фон и контур и сохранить последний.
2. Провести вейвлет-преобразование фона, используя только вторую из фор-
мул (1). В результате останется только низкочастотный прямоугольник hh.
Эта процедура рекуррентно применяется теперь к прямоугольнику hh как
к исходному изображению. Результат одного шага разложения показан на рис 2.
Изображение Контур hh фона +
Рис. 2
При восстановлении на каждом шаге нужно:
1) провести обратное вейвлет-преобразование фона с помощью формулы
,
~ 1
2
+
−∑= n
kki
k
n
i chc (5)
которая совпадает с формулой восстановления (3) при нулевых высокочастотных
коэффициентах;
2) добавить соответствующий сохраненный контур.
Выделение контура. Из описания алгоритма MSEC следует, что при разло-
жении фона и его восстановлении выполняется значительно меньше арифметиче-
Проблемы управления и информатики, 2006, № 3 93
ских операций, чем при стандартных прямом и обратном вейвлет-преобразо-
ваниях. Остается главный вопрос: «как разделить изображение на контур и фон?».
В [13] авторы MSEC описывают (но не приводят) весьма сложный алгоритм
выделения контура, который, по-видимому, является их «ноу-хау». Например,
они делят контуры на два типа — импульсные и ступенчатые — и по-разному их
обрабатывают. В настоящей работе предлагается очень простой, быстрый и до-
статочно эффективный способ выделения контуров.
Пусть задано изображение }.{ ijx Рассмотрим преобразование H типа гауссиана,
действующее по правилу: },{}{ ijijxH ξ= где 4/)( 1,1,,1,1 +−+− +++=ξ jijijijiij xxxx
(рис. 3).
jix ,
jix ,1−
1, −jix 1, +jix
jix ,1+
Рис. 3
Преобразование H — симметричный (по координатам i и j) низкочастотный
фильтр, так как сглаживает перепады яркости в изображении. Точнее если точки,
приведенные на рис. 3, лежат примерно в одной плоскости, то яркости ijx и ijξ
мало отличаются. Если же поверхность, проходящая через эти точки, сильно изо-
гнута, что является признаком контура, то различие в яркости ijx и ijξ может
быть значительным. В первом случае высокочастотный фильтр g, соответствую-
щий вейвлету, у которого равны нулю хотя бы первые два момента, не даст зна-
чимого вклада в высокочастотные компоненты изображения. Во втором — вклад
может быть бóльшим. Поэтому во втором случае точку ),( ji нужно считать при-
надлежащей контуру и для получения фона изменить значение ijx яркости в ней.
Соответствующее изменение нужно запомнить. Таким образом, после обработки
всех точек изображения получим контур. Опишем это более формально.
Пусть ∆ — задаваемое положительное число, о величине которого сказано
ниже. Положим
.если,,
,если,0,
∆≥ξ−ξ−=ξ=
∆<ξ−==
ijijijijijijij
ijijijijij
xxzy
xzxy
(6)
Исходное изображение }{ ijx представлено теперь в виде суммы двух изоб-
ражений: }{ ijy и },{ ijz в том смысле, что
.ijijij zyx += (7)
Изображение }{ ijy более гладкое, чем исходное, и его естественно назвать
фоном. Изображение }{ ijz соответственно содержит контур.
Формулы (6) конкретизируют п. 1 алгоритма MSEC-разложения, а форму-
ла (7) — п. 2 алгоритма MSEC-восстановления.
В указанной простой схеме есть два момента, требующие обсуждения — вы-
бор параметра ∆ и выбор гауссиана. Начнем с первого.
Чем меньше величина параметра ∆, тем глаже получается фон, но больше
ненулевых значений в контуре. Для лучшего сжатия недопустимы обе крайности:
94 ISSN 0572-2691
при большом ∆ фон не отличается от исходного изображения, а при малом —
контур содержит слишком много деталей. Оптимум находится посредине и зави-
сит как от сжимаемого изображения, так и от количества нулевых моментов у ис-
пользуемого вейвлета. Можно рекомендовать следующее эвристическое правило.
Число ненулевых значений в контуре должно составлять 3–5 % от числа пик-
селов в изображении.
Ясно, что это правило легко включить в алгоритм так, чтобы параметр ∆ ав-
томатически определялся в зависимости от изображения, причем отдельно на каж-
дом шаге MSEC-разложения.
С помощью выбора гауссиана, содержащего больше точек, чем приведенный
выше, или расположенных по-другому, можно отслеживать границы различных
типов и обрабатывать их в отдельности. Такое усовершенствование алгоритма
приведет к его значительному усложнению, но, возможно, даст преимущества
в сжатии.
Для сжатия изображений, по-видимому, бессмысленно использовать больше
трех шагов алгоритма MSEC, так как на третьем шаге фон становится в 64 раза
меньше исходного изображения, и дальнейшая его обработка слабо влияет на об-
щий результат сжатия. Кроме фона после третьего шага сохранены три контура:
первый контур того же размера, что и исходное отображение, второй — в четыре
раза меньше, и третий — меньше в 16 раз. Фактически имеется три изображения с
суммарным количеством пикселов, превосходящим по этому параметру исходное
изображение. Однако в них находится только около 3–5 % ненулевых значений,
поэтому контуры, считанные, например, построчно в одномерный массив, очень
хорошо сжимаются энтропийными методами кодирования.
Практическая реализация алгоритма. Для получения количественных и
качественных показателей эффективности обработки (кодирования) изображений
рассмотрим две схемы, использующие вейвлет-преобразование исходных данных
парой биортогональных фильтров — алгоритм Малла (рис. 4) и одним фильтром с
многомасштабной компенсацией контуров — MSEC (рис. 5). Необходимо отме-
тить, что вычисление вейвлет-коэффициентов в обоих случаях проводилось одной
парой фильтров, полученной согласно выражению (4) при заданных параметрах
3=n и .9=m
1. Вейвлет-
преобразование
с использованием
h и h
~ фильтров
2. Формирование
векторов вейвлет-
коэффициентов
(Z-сканирование)
3. Пороговая
обработка
вектора вейвлет-
коэффициентов
4. Кодирование
RLE + Хаффман
5. Архив
или передача
6. Декодирование
(RLE + Хаффман)
7. Формирование матрицы
вейвлет-коэффициентов
(обратное Z-сканирование)
8. Обратное
вейвлет-
преобразование
(h и h
~ фильтрами)
Рис. 4
Кратко рассмотрим алгоритмы работы предлагаемых методов кодирования
изображения. Так после первого шага работы схемы, представленной на рис. 4,
получим плоскость вейвлет-коэффициентов, с размещением, представленным на
рис. 1. Необходимо заметить, что при данном подходе к кодированию изображе-
ний размерность исходного изображения полностью совпадает с размерностью
плоскости вейвлет-коэффициентов.
Проблемы управления и информатики, 2006, № 3 95
1. Разделение
изображения
на контур и фон
3. Вейвлет-
преобразование
фона (h-фильтр)
4. CCITT-
модифицированный
алгоритм Хаффмана
2. RLE-
кодирование
контура
6. Декодирование
CCITT
(модифицированный
алгоритм Хаффмана)
7. RLE-декодирование
контура
8. Обратное вейвлет-
преобразование фона
-
~
h фильтром
Контур
9. Синтез изображения,
вейвлет-коэффициентов
(контур + фон)
Контур
Фон
Фон
5. Архив
или передача
Рис. 5
После нахождения вейвлет-коэффициентов при заданной «глубине погруже-
ния» (D) целесообразно перейти от матричной формы представления данных
к векторной (блок 2 в схеме кодирования изображен парой ортогональных филь-
тров (h и ),
~
h см. рис. 4).
В силу того, что после каждого шага преобразования качественный состав
коэффициентов остаточного члена меняется, возникает необходимость учета рас-
положения коэффициентов, полученных на предшествующих шагах преобразова-
ния (погружения). Для последовательного расположения коэффициентов, полу-
ченных на различных этапах погружения, целесообразно использовать методику
считывания вейвлет-коэффициентов в вектор с помощью Z-сканирования [12].
После Z-считывания коэффициентов (блок 2 схемы на рис. 4) получим после-
довательность отсчетов следующего вида (рис. 6)
0
20
40
60
80
100
120
140
160
180
200
220
240
0 4830 10787 17841 24914 31988 39081 48135 53209 60282
Рис. 6
Как видно, из рис. 6, такой подход полностью оправдан с точки зрения полу-
чения более равномерного распределения коэффициентов. Это обстоятельство
позволяет в дальнейшем эффективнее использовать методы компрессии данных
без потерь после пороговой обработки вектора вейвлет-коэффициентов. Порого-
вая обработка, реализованная в блоке 3 схемы кодирования изображений парой
биортогональных фильтров (h и )
~
h (см. рис. 4) при формировании вейвлет-коэф-
фициентов, предназначена для получения более равномерного распределения зна-
96 ISSN 0572-2691
чений отсчетов после Z-сканирования. Данная операция обеспечивает получение
заданного коэффициента сжатия. После пороговой обработки последовательность
вейвлет-коэффициентов поступает на вход блока 4 в схеме на рис. 4, где реализо-
ваны энтропийные методы кодирования, основанные на алгоритме группового
кодирования (RLE) и модифицированном алгоритме Хаффмана (CCITT). Восста-
новление изображений проводится в обратном порядке (см. рис. 4).
Алгоритм разложения изображений, реализованный в схеме кодирования
изображений одним фильтром (h) и компенсацией контуров в плоскости вейвлет-
коэффициентов (MSEC) рис. 5, схематично представлен на рис. 7, 8.
Контур 1
HH HG
GH GG
Контур 2
HH HG
GH GG
Контур 3
Фон
Рис. 7
Рис. 8
Проблемы управления и информатики, 2006, № 3 97
Сравнительная оценка вычислительных затрат алгоритмов Малла и
MSEC. Для сравнительного анализа и расчета объема вычислений в схеме коди-
рования MSEC (см. рис. 5) и схеме обработки изображений алгоритмом Малла
(см. рис. 4) приведем некоторые допущения.
1. Найдем относительный показатель вычислительных затрат в виде коэффи-
циента, который определяет, во сколько раз сократилось количество операций при
выполнении процедуры свертки изображения с одним фильтром h (MSEC) и дву-
мя ортогональными фильтрами h и g (Малла);
2. Для простоты сначала найдем относительный коэффициент эффективности
вычислений для равных и симметричных фильтров с параметрами ,1=N .1=M
В этом случае согласно выражению (4) получим пару биортогональных фильтров
для вычисления вейвлетов Хаара;
3. Далее определим, каким образом влияет длина разлагающих и восстанав-
ливающих фильтров на объем вычислений при сравнении схем кодирования
изображений с одним фильтром h или парой биортогональных фильтров h и g.
Структура размещения вейвлет-коэффициентов на плоскости изображения
после кодирования алгоритмом Малла при одном шаге разложения представлена
на рис. 1. Также оговорим размер исходного изображения: будем считать, что ко-
личество строк соответствует количеству столбцов в матрице изображения и рав-
но N. Сначала определим выигрыш в объеме вычислений при использовании биор-
тогональных фильтров для получения вейвлетов Хаара, которые в данном случае
равны между собой, т.е. .gh =
Для вычисления области вейвлет-коэффициентов НН фильтру h требуется
выполнить операцию свертки на N строках исходного изображения и на )2/(N
столбцах (см. рис. 1). Аналогичным образом запишем количество строк и столб-
цов, необходимых для построения остальных областей вейвлет-коэффициентов
при разложении изображения согласно алгоритму Маала:
.)2/(;)2/(
;)2/(;)2/(
columncolumnrow
columncolumnrow
NGHNNGG
NHGNNHH
=+=
=+=
(8)
Разложение и восстановление изображений методом MSEC проводится со-
гласно второму выражению в формуле (1) и выражению (5) при условии, что
.
~
hg = Для вычисления относительного коэффициента количества операций алго-
ритма Малла и алгоритма MSEC необходимо использовать следующие отношения:
.яизображениениивосстановлпри/)()
я,изображениразложениипри/)()
−
−
+++=
+++=
GGGHGGHGHHKб
HHGHGGHGHHKа
(9)
Заменим соответствующие члены этого выражения значениями, полученны-
ми в (8). В силу того, что изображение имеет равное количество строк и столбцов,
можно сократить соответствующие члены:
).6(6,2
5,1
4
)2/(
)2/(2))2/((2
==
+
++
=
N
N
NN
NNNK (10)
Поскольку фильтры h и g равны, следует, что обе схемы (см. рис. 4 и рис. 5)
при вычислении вейвлет-коэффициентов Хаара симметричны. По вычислитель-
ным затратам алгоритм MSEC имеет преимущество в 2,6 раза, перед схемой ко-
дирования алгоритмом Маала, как при разложении, так и при восстановлении
изображений.
98 ISSN 0572-2691
Количество операций при вычислении вейвлет-коэффициентов с использова-
нием пары биортогональных фильтров h и g будет определяться длиной фильтра h
и длиной фильтра g ).
~
( hg = При заданных параметрах 3( =N и )9=M длина
фильтра h равна 4, а длина фильтра g — 32 отсчета. Поэтому в выражении (8), где
вычисляются области вейвлет-коэффициентов с применением фильтра g, необхо-
димо поставить дополнительный множитель, равный отношению длины фильтра
g к длине фильтра h (в данном случае этот множитель равен 8 = 32 : 4). Таким об-
разом, выражение (8) и выражение (10) соответственно приобретают вид
;4);)2/((8
;4;)2/(
columncolumnrow
columncolumnrow
NGHNNGG
NHGNNHH
=+=
=+=
(11)
).3(3,14
5,1
5,21
)2/(
8))2/((9
==
+
++
=
N
N
NN
NNNK (12)
При восстановлении изображения используется выражение (9, б):
.79,1
12
5,21
))2/((8
8))2/((9
==
+
++
=
N
N
NN
NNNK (13)
По результатам расчетов можно сделать вывод, что количество операций при
использовании схемы с многомасштабной компенсацией контуров (см. рис. 5) при
вычислении вейвлетов Хаара меньше, чем при использовании алгоритма Малла
(см. рис. 4) в 2,6 раза, как при восстановлении, так и при разложении исследуе-
мых изображений. При использовании пары биортогональных фильтров h и g вы-
игрыш в количестве операций, согласно выражениям (12) и (13), составит:
— при разложении изображения 14,3;
— при восстановлении изображения 1,79.
Таким образом, очевидно, что алгоритм с многомасштабной компенсацией
контуров MSEC асимметричен, а коэффициент асимметрии приблизительно ра-
вен отношению длины фильтра g к длине фильтра h. Это свойство можно использо-
вать для предварительной оценки асимметричности работы алгоритма MSEC при
формировании определенной пары биортогональных фильтров по выражению 4.
Качественная и количественная оценка степени сжатия изображений. Для
оценки эффективности алгоритмов и расчета показателей качества различных пре-
образований из библиотеки стандартных изображений (http://www.icsl.ucla.edu) вы-
брано изображение в формате ∗.bmp, представленное файлом Zelda.bmp с пара-
метрами: размер 256 × 256 точек, глубина цвета 8 бит в градации серого, исход-
ный объем файла 65536 Б. Изменение коэффициента сжатия )( comprK —
отношение количества двоичных знаков на входе технологической цепочки коди-
рования к количеству этих знаков, полученных на выходе этой цепочки, оценива-
лось в зависимости от среднеквадратической ошибки (СКО) восстановленного
изображения после соответствующего преобразования. Причем соответствующим
интервалам значений СКО субъективно присвоены значения: отлично, хорошо,
удовлетворительно и плохо. Эти оценки позволяют с достаточной точностью гово-
рить о качестве визуального восприятия изображения после его восстановления.
На рис. 9 представлена зависимость коэффициента сжатия comprK от СКО (Е)
изображения Zelda.bmp при использовании алгоритма Малла (см. рис. 4), алго-
ритма MSEC (см. рис. 5) и алгоритма JPEG 2000, реализованного в коммерческом
формате компанией производителем. При расчетах коэффициента сжатия алго-
ритмами Малла и MSEC использовалась одна пара биортогональных фильтров.
http://www.icsl.ucla.edu/
Проблемы управления и информатики, 2006, № 3 99
0,05 0,06 0,07
Отлично
0,08 0,09 0,1
Хорошо
0,11 0,12 0,13
Удовлетворительно
0,14 0,15
Плохо
Малла MSEC JPEG 2000 DjVu
0
5
10
15
20
25
30
35
40
Зависимость коэффициента сжатия от СКО
К
оэ
фф
иц
ие
нт
с
ж
ат
ия
(р
аз
)
E (%)
Рис. 9
Из рис. 9 следует, что на исследуемом отрезке значений ошибок, алгоритм
многомасштабной компенсации контуров (MSEC) имеет преимущество перед ал-
горитмом Малла, который использует два фильтра при разложении и при восста-
новлении изображения. Так, при хорошем качестве (Е = 8–10 %) коэффициент
сжатия ,comprK полученный с использованием алгоритма MSEC, превосходит
аналогичный показатель для алгоритма Малла в среднем на 15 %.
Однако на интервале СКО (Е) — «отлично», когда ошибка имеет малые зна-
чения, коэффициент сжатия для всех алгоритмов практически одинаков, что еще в
бóльшей степени свидетельствует о преимуществах рассмотренного в работе ал-
горитма. Высокая эффективность формата JPEG 2000, в котором также использу-
ется вейвлет-преобразование изображений, объясняется более совершенными ме-
тодами энтропийного кодирования и инженерными составляющими формата.
На рис. 10 представлены изображения, полученные при использовании алго-
ритмов MSEC и Малла для СКО = 11 % и коэффициентах сжатия MSEC 24 раза
и Малла 22,5 раза соответственно, где а — оригинал изображения Zelda.bmp;
б — результат кодирования MSEC; в — кодирование MSEC без контуров; г — кон-
тура MSEC при трех уровнях разложения; д — остаточный фон; е — кодирование
алгоритмом Малла.
а б в
г д е
Рис. 10
100 ISSN 0572-2691
Выводы. В результате проведенных исследований получены качественные
и количественные оценки эффективности алгоритма сжатия изображений на
основе MSEC, из которых следует, что использование алгоритма MSEC приво-
дит к уменьшению количества операций при разложении и при восстановлении
изображений по сравнению с алгоритмом вейвлет-анализа Малла, а также име-
ет некоторое преимущество в качестве кодирования. Особенно сказываются
преимущества рассмотренного метода при малых ошибках (0,05 %) восстанов-
ления исходного изображения, даже по сравнению с коммерческими формата-
ми. К ограничениям данного метода можно отнести тот факт, что MSEC не
позволяет осуществить кодирование изображения без потерь, так как вейвлет-
преобразованию подвергается только остаточный член, а не вся плоскость
изображения.
В.Г. Іванов, М.Г. Любарський, Ю.В. Ломоносов
СТИСНЕННЯ ЗОБРАЖЕНЬ
НА ОСНОВІ КОМПЕНСАЦІЇ КОНТУРІВ
ПРИ ВЕЙВЛЕТ-ПЕРЕТВОРЕННІ
Пропонується новий метод стиснення, що полягає в багатомасштабному поділі
зображення на контур і фон. Виділення контуру здійснюється в кожному масш-
табі на основі симетричного низькочастотного фільтру, а фон представлено
вейвлет-коефіцієнтами. Показано, що даний метод порівняно з вейвлет-пере-
творенням є більш швидким і дозволяє одержати більш високий коефіцієнт
стиснення зображення.
V.G. Ivanov, M.G. Lubarskiy, Yu.V. Lomonosov
COMPRESSION OF THE IMAGES ON THE BASIS
OF COMPENSATION OF CONTOURS
AT WAVELET TRANSFORMATION
The new method of compression consisting in multiscale separation of the map on a
loop and a hum noise is offered. Selection of a loop is carried out in each scale on the
basis of a symmetric low-frequency filter, and the hum noise is represented by wave-
let-factors. It is shown, that the given method, in comparison with wavelet conver-
sion is faster and allows to receive higher aspect ratio of the map.
1. Харкевич А.А. Сравнение некоторых возможностей передачи простых рисунков // Электро-
связь. — 1958. — № 44. — С. 44–47.
2. Лебедев Д.С., Цуккерман И.И. Телевидение и теория информации. — М. : Энергия,
1965. — 219 с.
3. Сокращение избыточности // Тр. ИИЭР. Тематический вып. — 1967. — 55, № 3. — C. 173.
4. Цифровое кодирование телевизионных изображений / И.И. Цуккерман, Б.М. Кац,
Д.С. Лебедев, В.Г. Маковеев, С.В. Сардыка, Е.З. Сорока, В.А. Хлебородов,
Н.Н. Шостацкий / Под ред. И.И. Цуккермана. — М. : Радио и связь, 1981. — 240 с.
5. Прэтт У. Цифровая обработка изображений. — М. : Мир, 1982. – Кн. 2. — 480 с.
6. Методы передачи изображений. Сокращение убыточности / У.К. Прэтт, Д.Д. Сакри-
сон, Х.Г. Мусман и др. / Под ред. У.К. Прэтта: Пер. с англ. — М. : Радио и связь, 1983. —
264 с.
7. Х.Г. Мусман, П. Пирш, Х. Граллерт. Достижения в области кодирования изображений //
ТИИЭР. — 1985. — 73, № 4. — С. 31–58.
Проблемы управления и информатики, 2006, № 3 101
8. Kunt M., Ikonomopoulos A., Kocher M., Second-Generation Image Coding Techniques // Proc.
IEEE, Apr. 1985. — 73, N 4. — P. 549–574.
9. Миано Дж. Форматы и алгоритмы сжатия изображений в действии: Уч. пособ. — М. : Три-
умф, 2003. — 336 с.
10. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии: Уч. пособ. — М. :
Триумф, 2003. — 320 с.
11. Сэломон Д. Сжатие данных, изображений и звука. — М. : Техносфера, 2004. — 368 с.
12. Иванов В.Г., Любарский М.Г., Ломоносов Ю.В. Фурье- и вейвлет-анализ изображений в
плоскости JPEG-технологий // Проблемы управления и информатики. — 2004. — № 5. —
C. 111–124.
13. Xue X., Wu X. Image representation based on multi-scale edge compensation // IEEE Intern. Conf.
on Image Proc. — 1999. — http://citeseer.ist.psu.edu/xue99image.html.
14. Mallat S. Multiresolution approximation and Wavelet orthonormal bases L2(R) // Trans. of the
American Mathematical Society, June 1989. — 315, N 1. — P. 68–87.
15. Иванов В.Г., Ломоносов Ю.В., Шишков К.С. Сжатие изображений на основе выращивания
и кодирования областей // Вісн. Нац. техн. ун-ту «Харківський політехнічний інститут».
Зб. наук. праць. Тем. випуск: «Системний аналіз, управління та інформаційні технології». —
Харків : НТУ «ХПІ». — 2005. — № 18 (19). — 8 с.
16. Иванов В.Г. Кодирование изображений на основе автоматической классификации и пози-
ционирования фрагментов // Матеріали 12-ї Міжнар. конф. з автоматичного управління
(Автоматика – 2005), м. Харків, 30 травня–3 червня 2005 р.: В 3-х т. — Харків : Вид-во
НТУ «ХПІ», 2005. — 3. — С. 80–81.
Получено 16.11.2005
После доработки 24.02.2006
http://citeseer.ist.psu.edu/xue99image.html
|
| id | nasplib_isofts_kiev_ua-123456789-206814 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:51:04Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. 2025-09-22T16:20:51Z 2006 Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании / В.Г. Иванов, М.Г. Любарский, Ю.В. Ломоносов // Проблемы управления и информатики. — 2006. — № 3. — С. 89-101. — Бібліогр.: 16 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206814 621.391 Пропонується новий метод стиснення, що полягає в багатомасштабному поділі зображення на контур і фон. Виділення контуру здійснюється в кожному масштабі на основі симетричного низькочастотного фільтру, а фон представлено вейвлеткоефіцієнтами. Показано, що даний метод порівняно з вейвлетпере- творенням є більш швидким і дозволяє одержати більш високий коефіцієнт стиснення зображення. The new method of compression consisting in multiscale separation of the map on a loop and a hum noise is offered. Selection of a loop is carried out in each scale on the basis of a symmetric lowfrequency filter, and the hum noise is represented by wavelet-factors. It is shown, that the given method, in comparison with wavelet conversion is faster and allows to receive higher aspect ratio of the map. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки и защиты информации Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании Стиснення зображень на основі компенсації контурів при вейвлет-перетворенні Image Compression Based on Contour Compensation in Wavelet Transformations Article published earlier |
| spellingShingle | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании Иванов, В.Г. Любарский, М.Г. Ломоносов, Ю.В. Методы обработки и защиты информации |
| title | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| title_alt | Стиснення зображень на основі компенсації контурів при вейвлет-перетворенні Image Compression Based on Contour Compensation in Wavelet Transformations |
| title_full | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| title_fullStr | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| title_full_unstemmed | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| title_short | Сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| title_sort | сжатие изображений на основе компенсации контуров при вейвлет-преобразовании |
| topic | Методы обработки и защиты информации |
| topic_facet | Методы обработки и защиты информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/206814 |
| work_keys_str_mv | AT ivanovvg sžatieizobraženiinaosnovekompensaciikonturovpriveivletpreobrazovanii AT lûbarskiimg sžatieizobraženiinaosnovekompensaciikonturovpriveivletpreobrazovanii AT lomonosovûv sžatieizobraženiinaosnovekompensaciikonturovpriveivletpreobrazovanii AT ivanovvg stisnennâzobraženʹnaosnovíkompensacííkonturívpriveivletperetvorenní AT lûbarskiimg stisnennâzobraženʹnaosnovíkompensacííkonturívpriveivletperetvorenní AT lomonosovûv stisnennâzobraženʹnaosnovíkompensacííkonturívpriveivletperetvorenní AT ivanovvg imagecompressionbasedoncontourcompensationinwavelettransformations AT lûbarskiimg imagecompressionbasedoncontourcompensationinwavelettransformations AT lomonosovûv imagecompressionbasedoncontourcompensationinwavelettransformations |