Способ повышения скорости кодирования при совместном использовании векторного квантования и фрактального кодирования изображений
Владельцы патента RU 2321184:
Государственное образовательное учреждение высшего профессионального образования Академия Федеральной службы охраны Российской Федерации (Академия ФСО России) (RU)
Изобретение относится к области цифровой обработки изображений и может быть использовано при передаче изображений по низкоскоростным каналам связи. Техническим результатом является повышение скорости кодирования при сохранении скорости передачи и длине формата кадра, достигаемое тем, что изображение разбивают на ранговые блоки, для каждого рангового блока исходного изображения находят домен или блок из кодовой книги и соответствующее преобразование, которое наилучшим образом покрывает данный ранговый блок, если достаточно точного соответствия не получилось, то разбивают ранговые блоки на меньшие по размеру, продолжая этот процесс, пока не добьются приемлемого соответствия, или пока размер ранговых блоков не достигнет некоторого заранее определенного предела, причем после разбивания изображения на ранговые блоки осуществляют их классификацию, согласно которой каждый домен относится к одному из трех классов, причем кроме доменных блоков исходного изображения также осуществляется классификация блоков из кодовой книги, далее доменно-ранговые сопоставления выполняются только для тех доменов, которые принадлежат классу подобия данной ранговой области. В результате при кодировании поиск области, подобной ранговому блоку, осуществляется не только среди доменов - блоков кодируемого изображения, но и среди блоков из кодовой книги соответствующих классу ранговой области. 3 ил.
Изобретение относится к области цифровой обработки изображений и может быть использовано при передаче изображений по низкоскоростным каналам связи. Техническим результатом изобретения является разработка способа повышающего скорость кодирования при совместном использовании векторного квантования и фрактального кодирования изображений.
Наиболее близким по своей технической сущности к заявленному способу повышения скорости при совместном использовании векторного квантования и фрактального кодирования изображений является патент США №4941193, 1990 [1]. Авторы патента М.Барнсли и А.Слоун впервые увидели возможность применения теории систем итерируемых функций к проблеме сжатия изображений.
Сжатие изображений в указанном прототипе осуществляется следующим образом [2]. Для каждого рангового блока исходного изображения находят домен и соответствующее преобразование, которое наилучшим образом покрывает данный ранговый блок. Обычно это аффинное преобразование. Аффинное преобразование состоит из трех этапов. Во-первых, к выбранному домену применяется один из восьми базовых поворотов/отражений (четыре поворота на 90 градусов и зеркальное отражение в каждой ориентации). Во-вторых, вращаемая доменная область сжимается, чтобы соответствовать размеру ранговой области. И, наконец, методом наименьших квадратов вычисляются параметры контрастности α и яркости β соответствующие оптимальным значениям, при которых минимизируется выражение (1):
где: E(R, D) - метрика между ранговым блоком R и приведенным к нему по размеру доменным блоком D;
n - число строк в обрабатываемом ранговом блоке;
m - число столбцов в обрабатываемом ранговом блоке.
Если достаточно точного соответствия не получилось, то разбивают ранговые блоки на меньшие по размеру. Продолжают этот процесс до тех пор, пока не добьются приемлемого соответствия, или размер ранговых блоков не достигнет некоторого заранее определенного предела.
Недостатками прототипа является то, что при кодировании ранговых областей с большим динамическим диапазоном сложно подобрать домен с еще большим динамическим диапазоном, что приводит к снижению качества восстановления изображения. Кроме того, фрактальное кодирование требует большого объема вычислений, так как, во-первых, для каждого рангового блока необходимо вести поиск среди большого количества доменов и, во-вторых, в связи с теми вычислениями, которые требуются для каждого сравнения домена с ранговым блоком.
Целью данного изобретения является разработка способа повышения скорости кодирования при совместном использовании векторного квантования и фрактального кодирования изображений, обеспечивающего повышение скорости кодирования по сравнению с фрактальным методом сжатия для любого типа изображений при сохранении скорости передачи и длине формата кадра.
Одним из способов увеличения скорости при совместном использовании векторного квантования и фрактального кодирования изображений является классификация доменов и блоков, составляющих кодовую книгу. Большое время кодирования - это результат того, что приходится производить большое количество сравнений ранговых областей с доменами и блоками из кодовой книги. Общее время кодирования является произведением количества сопоставлений и времени, требуемого на выполнение каждого сопоставления. Каждое сопоставление - это требующая больших вычислений попиксельная обработка, включающая поворот, сжатие и подгонку доменного блока или блока из кодовой книги к ранговому блоку.
В данном изобретении используется классификация, предложенная Фишером в [3], согласно которой каждый домен относится к одному из трех классов. Далее доменно-ранговые сопоставления выполняются только для тех доменов, которые принадлежат классу подобия данной ранговой области.
1 класс A1≥А2≥А3≥А4
2 класс А1≥А2≥А4≥А3
3 класс A1≥А4≥А2≥А3
где А1, А2, А3, А4 - сумма значений пикселов классифицируемого доменного блока в верхнем левом, верхнем правом, нижнем левом и нижнем правом квадрантах соответственно.
Указанная классификация может быть использована при совместном использовании векторного квантования и фрактального кодирования изображений. В этом случае, кроме доменных блоков исходного изображения, также осуществляется классификация блоков из кодовой книги. В результате при кодировании поиск области, подобной ранговому блоку, осуществляется не только среди доменов - блоков кодируемого изображения, но и среди блоков из кодовой книги соответствующих классу ранговой области.
Заявленный способ поясняется чертежами:
- Фиг.1 - алгоритм кодирования изображения при совместном использовании векторного квантования и фрактального кодирования изображений с учетом классификации доменов и блоков из кодовой книги;
- Фиг.2 - схема разбиения на классы доменов и блоков из кодовой книги;
- Фиг.3 - соотношение времени кодирования и пикового соотношения сигнал/шум (PSNR) при кодировании изображения с помощью совместного использования фрактального кодирования и векторного квантования без классификации и с классификацией.
Алгоритм кодирования изображения при совместном использовании векторного квантования и фрактального кодирования изображений с учетом классификации доменов и блоков из кодовой книги показан на Фиг.1. Исходное изображение разбивается на неперекрывающиеся ранговые и доменные блоки, которые классифицируются. После этого для каждого рангового блока находят домен, который принадлежит классу подобия данной ранговой области, и соответствующее преобразование, которое наилучшим образом покрывает ранговый блок. Обычно это аффинное преобразование. В качестве доменов могут выступать доменные области исходного изображения или блоки кодовой книги, также соответствующие классу кодируемой ранговой области. Кодирование завершается при покрытии каждого рангового блока доменной областью с заданной погрешностью.
На Фиг.2 представлена схема разбиения на классы доменов и блоков из кодовой книги. Каждый домен или блок из кодовой книги разбивается на четыре квадранта и в каждом квадранте вычисляется сумма значений пикселов.
где: k - число строк (столбцов) в квадранте;
rj - значение j-го пиксела квадранта.
Уровнями яркости каждого квадранта показаны соответствующие классы разбиения.
На Фиг.3 представлено соотношение времени кодирования и пикового соотношения сигнал/шум (PSNR) при кодировании изображения с помощью совместного использования фрактального кодирования и векторного квантования без классификации и с классификацией. Проведенные исследования при кодировании тестового изображения "Лена" на компьютере с процессором AMD Athlon 1900 показали, что время кодирования изображения при использовании классификации доменных блоков и блоков из кодовой книги уменьшается в 2 раза (с 8-и минут до 4-х минут) при снижении качества восстановленного изображения на 0.2 дБ, что является незначительным.
Предлагаемый способ может быть реализован на современных цифровых процессорах обработки сигналов и может найти свое применение при передаче изображений по низкоскоростным каналам связи
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Barnsley M., Sloan A., Methods and apparatus for image compression by iterated function system. Патент США №4941193, 1990.
2. С.Уэлстид, Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособие - M.: Издательство Триумф, 2003.
3. Y.Fisher, Fractal image compression with quadtrees. Fractal Image Compression - Theory and Application, Springer-Verlag, New York, 1994.
Способ повышения скорости кодирования при совместном использовании векторного квантования и фрактального кодирования изображений, заключающийся в том, что изображение разбивают на ранговые блоки, для каждого рангового блока исходного изображения находят домен или блок из кодовой книги и соответствующее преобразование, которое наилучшим образом покрывает данный ранговый блок, если достаточно точного соответствия не получилось, то разбивают ранговые блоки на меньшие по размеру, продолжая этот процесс, пока не добьются приемлемого соответствия или размер ранговых блоков не достигнет некоторого заранее определенного предела, причем после разбивания изображения на ранговые блоки их классифицируют, после чего для каждого рангового блока исходного изображения находят домен или блок из кодовой книги, из блоков изображений из класса, соответствующего классу кодируемого рангового блока и преобразование, которое наилучшим образом покрывает данный ранговый блок, если достаточно точного соответствия не получилось, то разбивают ранговые блоки на меньшие по размеру, продолжая этот процесс, пока не добьются приемлемого соответствия или размер ранговых блоков не достигнет некоторого заранее определенного предела.
