Способ сжатия изображения

Способ сжатия изображения

Иллюстрации

Показать все

Реферат

Изобретение относится к области обработки данных изображения, а именно к способам сжатия изображения, и может быть применено в любой области науки и техники, в которой используются цифровые изображения, в частности для сохранения и архивирования фото- и видеоданных. В аппаратной реализации заявленное изобретение может использоваться в видеокамерах, фотокамерах и других устройствах, использующих цифровые изображения. Возможно также применение заявленного способа в военных и картографических целях, благодаря его высокой помехозащищенности, обеспечивающей гарантированную распознаваемость изображения даже в случае значительных искажений в переданных данных.

Цифровые изображения являются существенной частью современного мира. Сжатие изображения так же важно, как передача и хранение данных. Существует постоянно растущий интерес к улучшению способов сжатия изображений.

Для решения проблемы сжатия изображения (кодирования изображения в широком понимании) используют достижения различных областей науки.

Необходимость эволюции способов сжатия изображения обусловлена природой изображения. Она может характеризоваться тремя особыми свойствами.

Первое - это то, что цифровое изображение (и цифровое видео) занимает намного больший объем памяти по сравнению с обычным текстом. Например, маленькое изображение с низким разрешением 500×800 и низким качеством имеет размер примерно 1.2 Мб. Этот размер эквивалентен книге, которая имеет 400 страниц (60 знаков в строке, 42 строки на странице). Это свойство цифрового изображения определяет актуальность проблемы сжатия изображения.

Второе свойство цифрового изображения заключается в том, что человеческий глаз оперирует контурами и оценивает лишь общее изменение цвета при анализе изображения. Кроме того, человеческий глаз не ощущает малые изменения в изображении. Это означает, что можно создать эффективные способы сжатия изображения. После восстановления (из сжатого состояния) обработанные таким способом изображения не будут эквивалентны оригиналу (несжатом состоянии), но человеческий глаз не заметит отличий. Данная особенность человеческого глаза позволяет создавать особые способы, которые могут быть применены только для сжатия цифрового изображения и не могут применяться, в частности, для сжатия данных. Основанные на этом свойстве способы сжатия отличаются очень высокой эффективностью.

Третье свойство, характеризующее цифровое изображение по сравнению с обычным текстом, состоит в избыточности информации в двух измерениях (тогда как текст имеет одномерную структуру). Это означает, что пиксели (точки), находящиеся в локальной области, имеют почти одинаковый цвет. Поэтому в способах сжатия изображения всегда учитывают внутреннюю структуру изображения.

В настоящее время существуют два основных направления в разработке способов сжатия изображения. Первое направление обеспечивает эффективное сжатие изображений без потерь. Второе направление оперирует свойством контурного восприятия изображения глазом человека и сжимает изображение с потерями (декомпрессированное изображение не эквивалентно оригиналу), но отличие не заметно для глаза. Эти основные направления относятся только к процессам сжатия изображения, и технологии, примененные в указанных разработках, не могут быть применены для сжатия других объектов (например, для сжатия текста).

Раскрытие структуры данных является ключевым аспектом для эффективного представления и хранения данных. Майкл Барнсли и Алан Слоан (см. патенты США №4941193 [1] и №5065447 [2]) были первыми исследователями, которые обнаружили возможность применения систем итерируемых функций (ITS - Iterated Function Systems) в области сжатия цифровых изображений. А.Джеквин (см. монографию Уэлстид С.Фракталы и вейвлеты для сжатия изображений в действии. - М.: Издательство Триумф, 2003 [3]) представил способ, в котором системы доменов и ранговых блоков изображения используются для сжатия. Доменный блок - часть изображения, входящая в перекрывающееся покрытие изображения и имеющая произвольную форму. Ранговый блок - это часть изображения, входящая в неперекрывающееся покрытие изображения и имеющая произвольную форму. В соответствии с данным способом все изображение разделяется на неперекрывающиеся ранговые подызображения, которые определяются набором перекрывающихся доменных подызображений. Для каждого рангового блока в способе ищут наиболее подходящий доменный блок и, применяя аффинное преобразование, преобразуют доменный блок в найденный ранговый блок. Внутреннее представление изображения преобразовывают из двумерного массива пикселей в систему ранговых блоков, доменных блоков и их преобразований между ними.

Прежде всего необходимо уточнить термин сжатие. Сжатие означает преобразование данных, описываемое следующим выражением:

V_SD>V_CD,

где V - функция объема, SD - исходные данные (start data), CD - сжатые данные (compressed data).

Для корректной оценки коэффициента сжатия необходимо ввести понятие класса изображения. Под термином класс изображения понимают всю совокупность изображений, которые будут иметь качественно одинаковые результаты после применения способа сжатия.

Необходимо ввести набор характеристик:

- высокий коэффициент сжатия;

- высокое качество распакованного изображения;

- высокая скорость сжатия;

- высокая скорость распаковывания;

- возможность быстрого предварительного просмотра изображения;

- высокая степень защиты от ошибок;

- эффективность программной реализации;

- невысокая цена аппаратной реализации.

В настоящее время фрактальное сжатие целесообразно использовать в случае, когда необходимо обеспечить следующие характеристики: высокую степень сжатия, высокое качество распакованного изображения, высокую скорость распаковки, возможность быстрого предварительного просмотра изображения, высокая защита от ошибок передачи в канале данных и эффективность программной и аппаратной реализации.

Приведенный выше набор характеристик способа сжатия изображения в соответствии с требованиями приложений зависит от реальных условий, в которых способ будет использоваться. Невозможно произвести универсальное сравнительное описание хорошо известных способов, поэтому необходимо отметить наиболее важные критерии сравнения способов сжатия:

- степень сжатия;

- класс изображений, на который ориентирован способ;

- время, необходимое для сжатия и распаковывания (обычно обозначаемое термином - симметрия);

- специфические особенности способа, которые используются для эффективного сжатия.

При фрактальном сжатии цифровых изображений определяют достаточное покрытие для множества сжимающих преобразований, которые преобразуют доменные блоки в ранговые блоки (Фиг.1). Ранговые блоки могут быть фиксированного размера, но обычно используют адаптивную грануляцию (разбиение) с изменяемым размером ранговых блоков. Ранговые блоки, которые показаны на Фиг.1 (правая часть фигуры), сформированы путем применения метода квадродерева (каждый блок, если он не покрывается требуемой ошибкой, должен быть разделен на 4 равных подблока).

Рассмотрим основной (базовый) способ фрактального сжатия (Фиг.2):

- Изображение F разделяют на множество неперекрывающихся ранговых блоков {R}. В базовом способе используют прямоугольные ранговые блоки, но можно использовать ранговые блоки другой формы (например, треугольные). Применяют адаптивное разбиение ранговых блоков для улучшения качества изображения в случае большого количества деталей. Это позволяет более эффективно заполнить ранговыми блоками части изображения с мелкими деталями.

- Покрывают изображение множеством доменов (возможно, что число доменов превысит 10000).

- Для каждого рангового блока определяют доменный блок и преобразование (при этом чаще всего используют аффинное преобразование), которое удовлетворяет требованиям по разнице между оригинальным и распакованным изображениями, и сохраняют контраст и среднюю яркость изображения для найденного лучшего соответствия.

- Если ранговый блок не покрыт после сравнения всех доменов, его разделяют на меньшие ранговые блоки (метод квадродерева) и опять выполняют предыдущий шаг. Если достигают минимального размера рангового блока и не покрывают с допустимой ошибкой, тогда сохраняют преобразование и доменный блок с минимальным уровнем ошибки.

На Фиг.2 представлена схема основного способа фрактального кодирования. В данном способе существует специальная опция, которая позволяет определить лучший домен, даже если найден домен с допустимой ошибкой. Если выбрана такая опция, то поиск продолжают до того, как закончатся все домены, в противном случае ищут первый подходящий домен (с ошибкой меньше заданной). Без данной опции сжатие можно выполнить гораздо быстрее, но с худшим качеством.

Детали фрактальной компрессии могут сильно различаться для разных вариантов выполнения. В некоторых из них для сжатия изображения используют непрямоугольную форму ранговых и доменных блоков. В наиболее популярном способе для сжатия используют треугольные блоки. Триангуляция позволяет избежать блочного эффекта в распакованном изображении, который возникает в результате разбиения прямоугольных блоков. Иногда применяют неафинное преобразование. Пространственная часть аффинного преобразования для изображения в оттенках серого Wi обеспечивает пространственное сжатие, когда выполнено условие: |det A|<1 (где Wi - трехмерное аффинное преобразование, А - матрица поворота и масштабирования). Чтобы получить пространственное сжатие, необходимо ограничить преобразование Wi параллельным сдвигом и одним из девяти основных поворотов (0, 90, 180, 270 градусов) и отражений (относительно вертикальной и горизонтальной осей).

Шаг 3 описанного выше основного способа предъявляет наиболее высокие требования к вычислительной системе, выполняющей алгоритм. Для каждого рангового блока Ri в способе находят домен Di, пространственное преобразование Wi, контраст Si и яркость Oi, которые удовлетворяют следующему требованию: Wi(F) должно быть близко к начальному изображению F. Это означает, что ищут Wi, для которого величина выражения минимальна:

Данный интеграл заменяют операцией попиксельного суммирования. В случае если ошибка превышает определенный уровень, адаптивная схема разбивает ранговый блок на меньшие ранговые блоки. Этот процесс продолжается до возникновения двух возможных ситуаций: первой, когда достигают определенного уровня ошибки, или второй, когда достигают наименьшего размера рангового блока.

Для увеличения скорости фрактального сжатия изображения часто применяют способ определения характеристик доменного и рангового блока.

В качестве характеристик обычно используют набор из пяти различных измерений (вектор характеристик). Этот набор был определен как оптимальный набор для определения признаков (оптимальный набор характеристик может быть дополнен):

- стандартное отклонение σ:

,

где µ - средняя попиксельная величина прямоугольной области размером nr, nc и ρ_ij - величина пикселя в ряде i, столбце j.

- асимметрия:

- соседний контраст. Он может быть вычислен путем измерения усредненной разницы между соседними пикселями;

- бета. Данная характеристика показывает, насколько велика разница между пикселями в блоке и в центре блока;

- максимальный градиент. Это максимальный горизонтальный и вертикальный градиенты, которые показывают изменение цвета пикселей в горизонтальном и вертикальном направлениях.

Каждый блок (как ранговый, так и доменный) в методе с выделением особенностей имеет собственный вектор характеристик Ф, по которому кодер принимает решение, похожи ли блоки или нет и стоит ли производить попиксельное сравнение.

Далее приведены шаги выполнения способа с определением характеристик (Фиг.3):

- Вычисляют и сохраняют характеристики для всех доменных блоков. Определяют максимальную и минимальную величины характеристик во всем списке доменов для нормализации. Выполняют нормализацию всех характеристик для всех доменов. Величина характеристики Ф может быть сдвинута к нормализованной величине n_Ф, которая находится между 0 и 1 за счет использования следующей формулы:

,

где f - значение компоненты вектора характеристик.

- При проведении сравнения между доменными и ранговыми блоками вычисляют вектор характеристик для рангового блока. При этом учитывают, что после нормализации могут получить Ф_r, которые не находятся в промежутке (0, 1), поскольку максимальная и минимальная величины были вычислены только для списка доменов. Если используют большой список доменных блоков, величины нормализованных ранговых характеристик не могут быть намного больше. После этого вычисляют расстояние между двумя векторами (ранговым и доменным):

,

где f_r - вектор характеристик для рангового блока, f_d - вектор характеристик для доменного блока.

Кодировщик контролирует минимальную величину расстояния, и если величина меньше, чем на предыдущей итерации (для первой итерации расстояния выставляют бесконечными), необходимо контролировать максимальную допустимую величину каждой характеристики (толерантность). Если расстояние меньше, чем толерантность, то производят сравнение домена и рангового блоков. Если в результате сравнения получена ошибка, меньшая, чем допустимая, тогда принимают ранговый блок в качестве покрытого (обработанного), если нет, то продолжают проверку доменов. Ранговый блок, как и раньше, может быть разбит на меньшие подблоки.

«Код» изображения, сжатого фрактальным способом, будет представлен в виде списка. Каждый элемент данного списка будет содержать информацию о каждом ранговом блоке. Это означает, что этот элемент будет содержать информацию о месте рангового блока в изображении, соответствующем домене (обычно в виде его индекса) и всех параметрах преобразования. Это означает, что индекс сжатия зависит от числа ранговых блоков и эффективности представления данных в устройстве хранения (стандартные способы позволяют уменьшить размер уже сжатых данных более чем в четыре раза).

Известен способ сжатия цифрового изображения с использованием итерационных преобразований изображения, описанный в патенте США №5416856 [4], в котором изображение, представленное массивом пикселей, разбивают на ранги и домены.

Преобразования генерируют для каждого домена таким образом, что ни одно из них не является сжимающим. Каждое преобразование домена оптимизировано в единицах шкалы интенсивности и коэффициентов смещения. Выбирают домен и соответствующее оптимизированное преобразование, что минимизирует данные ошибки преобразования. Эти шаги повторяют для выбранного множества рангов, при этом формируют неперекрывающуюся ячеистую структуру изображения, таким образом, соответствующие оптимизированные преобразования, связанные с выбранным множеством, формируют итоговую сжатую карту. Информацию, которая идентифицирует каждое из выбранных множеств рангов и выбранных доменов и соответствующих оптимизированных преобразований, затем сохраняют в адресной памяти в качестве кодированного изображения.

Недостатком данного способа является низкая производительность кодирующего устройства, построенного на базе данного подхода.

Наиболее близким к заявленному изобретению является сжимающее устройство на основе фрактального преобразования (см. патент США №5430812) [5], которое содержит контролирующий контур для получения данных цифрового изображения и для преобразования данных изображения в блоки. Контролирующий контур передает обработанные данные изображения множеству преобразующих контуров и питающему контуру и выполняют параллельную обработку, чтобы сравнить блоки данных изображения и сгенерировать величины, представляющие данные изображения в сжатой форме. Данное устройство выбрано в качестве прототипа заявленного изобретения.

Способы и устройства фрактального сжатия изображения позволяют обеспечить следующие характеристики: высокую степень сжатия, высокое качество распакованного изображения, высокую скорость распаковывания, возможность быстрого предварительного просмотра изображения, высокую защиту от ошибок, эффективность программной и аппаратной реализации.

Основной недостаток описанных выше способов фрактального кодирования, в том числе прототипа, заключается в том, что в них необходимо сравнить большое число доменов и ранговых блоков, что уменьшает их скорость работы и производительность.

Задачей заявленного изобретения является создание способа сжатия изображения на основе фрактального преобразования с увеличенной скоростью работы, производительностью и помехозащищенностью без ущерба качеству.

Поставленная задача решена путем создания способа сжатия изображения, заключающегося в выполнении следующих операций:

- получают данные изображения на входе оптимального кодировщика;

- производят посредством кодировщика оценку изображения и определяют класс изображения на основе набора фильтров сжатия;

- разделяют (разбивают) изображение F на множество неперекрывающихся ранговых блоков {R}, применяют адаптивное разбиение ранговых блоков;

- посредством кодировщика предварительно вычисляют преобразования для всех доменов на основе набора фильтров для ранее определенного класса и создают набор доменов;

- вычисляют посредством кодировщика векторы характеристик для всех доменов;

- для каждого рангового блока ищут среди ранее рассчитанных блоков доменный блок и преобразование в виде поворота/отражения, отвечающее требованиям по ошибке;

- если ранговый блок не подвергся обработке (т.е. не покрыт) после сравнения всех доменов, его разбивают на меньшие ранговые блоки и опять выполняют предыдущий шаг, если достигают минимального размера рангового блока и не подвергают его обработке с допустимой ошибкой, тогда сохраняют преобразование и доменный блок с минимальным уровнем ошибки.

В представленном изобретении решена проблема низкой производительности кодировщика и предложен метод сжатия, реализующий скорость компрессии, близкую к реальному времени (25 кадров в секунду при разрешении 512 на 512 точек при глубине цвета 16 бит). Этот результат получен за счет выделения самодостаточного набора классов изображений и предположения о достаточном наборе доменных блоков (доменной достаточности). В заявленном изобретении достигается баланс соотношения времени сжатия (близкого к реальному), качества распакованного изображения и коэффициента сжатия (превышающего существующие аналоги, за исключением прототипа).

Для лучшего понимания заявленного изобретения далее приводится его подробное описание с соответствующими чертежами.

Фиг.1. Схема преобразования из доменных в ранговые блоки, известная из уровня техники.

101 - Преобразование из доменных блоков в ранговые блоки (аффинное масштабирование, поворот, отражение по вертикали/горизонтали)

102 - Доменные блоки

103 - Ранговые блоки

Фиг.2. Схема основного способа фрактального сжатия, известного из уровня техники.

201. Начало

202. Конец

203. Остались непокрытые ранговые блоки?

204. Разделяют (разбивают) ранговый блок

205. Выбирают ранговый блок из списка

206. Преобразуют доменный блок для сравнения с ранговым

207. Ошибка покрытия меньше допустимой?

208. Выбрана опция поиска лучшего домена?

209. Ранговый блок покрывается с допустимой ошибкой

210. Выбирают доменный блок из списка

211. Достигнут конец списка доменов?

212. Достигнут минимальный размер рангового блока?

213. Достигнут конец списка доменов?

214. Ранговый блок обработан, но не отвечает требованиям о допустимой ошибке. Используют домен с наименьшей величиной ошибки.

Фиг.3. Схема способа фрактального сжатия с определением характеристик, известного из уровня техники.

1. Начало

2. Вычисляют вектора характеристик для всех доменов

3. Конец

4. Есть непокрытые ранговые блоки?

5. Измеряют расстояние между векторами характеристик (ранг - домен)

6. Преобразовывают доменный блок для сравнения с ранговым

7. Разделяют (разбивают) ранговый блок

8. Выбирают ранговый блок из списка

9. Расстояние между векторами характеристик меньше, чем сохраненное минимальное расстояние?

10. Ошибка меньше допустимой?

11. Выбрана опция поиска лучшего домена?

12. Ранговый блок покрыт с допустимой ошибкой?

13. Выбирают вектор характеристик для данного домена из списка

14. Достигнут конец списка доменов?

15. Расстояние между векторами меньше допустимого?

16. Достигнут минимальный размер рангового блока?

17. Достигнут конец списка доменов?

18. Ранговый блок обработан, но отвечает требованию о допустимой ошибке. Используют домен с наименьшей величиной ошибки.

Фиг.4. Схема способа сжатия согласно изобретению.

401. Начало

402. Дополнительные подшаги:

- 402.1. Производят оценку цифрового изображения и определяют класс.

- 402.2. Вычисляют преобразования для доменов на основе набора фильтров для определенного класса и формируют набор доменов

- 402.3. Вычисляют векторы характеристик для всех доменов

403. Конец

404. Существуют непокрытые ранговые блоки?

405. Измеряют расстояние между векторами характеристик (ранг - домен)

406. Используют предварительно вычисленный доменный блок для сравнения с ранговым

407. Разделяют (разбивают) ранговый блок

408. Выбирают ранговый блок из списка

409. Расстояние между векторами характеристик меньше, чем сохраненное минимальное расстояние?

410. Ошибка покрытия меньше допустимой?

411. Выбрана опция поиска лучшего домена?

412. Ранговый блок покрыт с допустимой ошибкой

413. Выбирают вектор характеристик для данного домена из списка

414. Достигнут конец списка доменов?

415. Расстояние между векторами меньше допустимого?

16. Достигнут минимальный размер рангового блока?

417. Достигнут конец списка доменов?

418. Ранговый блок обработан, но не отвечает требованию о допустимой ошибке. Используют домен с наименьшей величиной ошибки.

Для описания заявленного способа сжатия необходимо ввести следующие понятия: класс изображения, набор фильтров, доменная достаточность, скорость компрессии.

Фрактальный способ сжатия в базовом представлении оперирует блоками изображений и аффинными преобразованиями над ними, как инструментом сжатия. Для начала нужно пояснить, что собой представляет понятие доменной достаточности.

Под термином доменной достаточности понимают необходимый и достаточный набор доменов для сжатия того или иного класса изображений, при этом понятие доменной достаточности жестко связано с набором фильтров, формирующих набор доменов.

Термин класс изображений (см. определение выше) используется для выделения и группировки оптимального набора фильтров, который бы обеспечивал построение наиболее похожего набора доменов для последующего доменно-рангового сравнения.

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

Скорость компрессии жестко связана с термином доменной достаточности, так как доменная достаточность определяет конечный и сравнительно небольшой (по сравнению с базовым набором, в котором обычно присутствует порядка 10000 доменных блоков) набор доменных блоков для базового алгоритма компрессии, притом алгоритм обеспечивает работу компрессора в масштабе реального времени как с единичными кадрами, так и с видеопотоками.

Под термином фильтр будем понимать линейное и нелинейное маскирование.

Термин доменной достаточности базируется на понятии фрактал, которое подразумевает самоподобие фрактальных объектов и применяется в данном случае к изображению целиком и к его частям (рангам) в частности. В базовом методе понятие фрактал используется при сравнении покрывающих изображение доменных и ранговых блоков, в отличие от предложенного метода, в котором все доменные блоки предвычисляют из целого изображения.

Заявленный способ сжатия изображения на основе фрактального преобразования может быть представлен в виде следующей последовательности операций (Фиг.4):

- получают данные изображения на входе оптимального кодировщика;

- кодировщик производит оценку изображения и определяет класс изображения;

- кодировщик предварительно вычисляет преобразования для всех доменов на основе набора фильтров для определенного класса и создает множество доменов;

- кодировщик предварительно вычисляет векторы характеристик для всех доменов;

- затем начинают основные операции по сжатию, которые сходны с немодифицированным способом.

В целом способ реализован следующим набором шагов:

Оценивают изображение и выбирают класс изображения (набор фильтров сжатия).

Разделяют изображение F на множество неперекрывающихся ранговых блоков {R}. Применяют адаптивное разбиение ранговых блоков.

Строят и предвычисляют доменное покрытие для всего изображения и всех допустимых размеров ранговых блоков.

Для каждого рангового блока ищут доменный блок и преобразование, которое удовлетворяет требованиям по ошибке декодирования.

Если ранговый блок не покрыт после сравнения всех доменов, его разделяют на меньшие ранговые блоки и опять выполняют предыдущий шаг. Если достигают минимального размера рангового блока и не покрывают его с допустимой ошибкой, тогда сохраняют преобразование и доменный блок с минимальным уровнем ошибки.

Основными характерными особенностями заявленного способа сжатия изображения являются:

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

- Предварительное выполнение аффинного преобразования доменных блоков на стадии построения набора доменов, а не на стадии сравнения доменов и ранговых блоков. Это главное условие оптимизации. Оно означает, что на шаге 401 уменьшают размер доменов, а на шаге 402 уменьшают число вычислений на стадии доменно-рангового сравнения.

- Использование большого набора фильтров (линейных/нелинейных) для формирования доменного покрытия.

- Применение классификации изображений для выбора оптимального набора фильтров для сжатия того или иного изображения.

- Значительное увеличение устойчивости к потере информации о доменно-ранговых преобразованиях в процессе передачи и хранения сжатых данных, так как при формировании всех без исключения доменов используется все изображение, а не его часть.

Хотя указанный выше вариант выполнения изобретения был изложен с целью иллюстрации настоящего изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла настоящего изобретения, раскрытого в прилагаемой формуле изобретения.

Способ сжатия изображения, заключающийся в выполнении следующих операций:получают данные изображения на входе оптимального кодировщика;производят посредством кодировщика оценку изображения и определяют класс изображения на основе набора фильтров сжатия;разделяют изображение F на множество неперекрывающихся ранговых блоков {R}, применяют адаптивное разбиение ранговых блоков;посредством кодировщика предварительно вычисляют преобразования для всех доменов на основе набора фильтров для ранее определенного класса и создают набор доменов;вычисляют посредством кодировщика векторы характеристик для всех доменов;для каждого рангового блока ищут среди ранее рассчитанных блоков доменный блок и преобразование в виде поворота/отражения, отвечающее требованиям по ошибке;если ранговый блок не покрыт после сравнения всех доменов, его разделяют на меньшие ранговые блоки и опять выполняют предыдущий шаг, если достигают минимального размера рангового блока и не покрывают ранговый блок с допустимой ошибкой, тогда сохраняют преобразование и доменный блок с минимальным уровнем ошибки.