Способ сжатия изображения при фрактальном кодировании

Способ сжатия изображения при фрактальном кодировании

Иллюстрации

Показать все

Реферат

Изобретение относится к области обработки изображений для хранения и передачи цифровой информации и может применяться при фрактальном кодировании изображения.

Фрактальное кодирование изображения является одним из наиболее перспективных методов сжатия информации с потерями в настоящее время. Фрактальное кодирование отличается как высокой степенью сжатия, так и высокой скоростью восстановления изображения. Степень сжатия данного алгоритма можно сравнить с известными современными методами кодирования, например JPEG, а скорость восстановления изображения гораздо выше. Математическое описание изображения как результат фрактального кодирования позволяет восстановить изображение любого размера без каких-либо значительных масштабных искажений, которые свойственны другим методам кодирования. Фрактальное кодирование является очень перспективным для компьютерных мультимедиа приложений и цифрового видео. Основным недостатком метода является большая вычислительная сложность этапа кодирования изображения [1].

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

Рассмотрим базовый алгоритм фрактального кодирования изображения [2]. Изображение I разбивают на прямоугольные ранговые блоки R_i, причем ранговые блоки не перекрываются и покрывают все изображение. Далее покрывают изображение I множеством доменных блоков D_i. Доменные блоки могут перекрываться, иметь разный размер, и их количество может достигать сотни или тысячи единиц. Для каждого рангового блока R_i находят сжимающее аффинное преобразование w_i, которое наилучшим образом аппроксимирует данный ранговый блок в доменный блок D_i.

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

Наиболее близким по технической сущности к заявляемому способу сжатия изображения при фрактальном кодировании является способ обработки изображений с помощью метода LBP [3].

В данной процедуре предложено использовать известный метод двоичных локальных шаблонов LBP (Local Binary Patterns) [4]. Алгоритм метода LBP заключается в следующем. Выделяют окрестность размера 3x3 вокруг каждого пикселя. Соседним пикселям, которые имеют значение выше или равны значению центрального пикселя, присваивают значение 1, а тем пикселям, у которых значение меньше значения центрального пикселя, присваивают значение 0. Восемь двоичных чисел, связанных с восемью соседними пикселями, читают последовательно по часовой стрелке, чтобы сформировать двоичное число. Эти двоичные числа или их десятичный эквивалент могут быть ассоциированы с центральным числом и использованы как характеристики локальной текстуры.

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

Десятичная форма получающегося 8-битного слова - LBP кода для пикселя с координатами (x_c, y_c) выражена формулой:

где i_{n -} значение интенсивности соседнего пикселя с индексом n;

i_c - значение интенсивности центрального пикселя (x_c, y_c);

s(x) - пороговая функция, которая определена следующим образом:

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

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

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

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

Поставленная задача осуществляется путем применения модифицированного метода LBP, при котором пиксели выбирают на некотором расстоянии от центрального пикселя и их координаты P(x_p, y_p) определяют следующим образом:

где x_p, y_p - координаты выбранных пикселей;

x_c, y_c - координаты центрального пикселя;

R - радиус окружности, которую образуют выбранные пиксели;

Р - количество пикселей на окружности.

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

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

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

Заявленный способ поясняется чертежами:

фиг.1 - отображение ранговых областей в доменные области;

фиг.2 - вычисление LBP кода;

фиг.3 - модифицированный LBP код;

фиг.4 - варианты формирования LBP кода.

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

Источники информации

1. Barnsley М., Hurd L. Fractal Image Compression. - Wellesley, MA: A.K. Peters, Ltd, 1993.

2. С. Уэлстид. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособие. - М.: Издательство Триумф, 2003, 320 с;

3. Зыков А.Н., Карцов С.К., Куприянов Д.Ю. Обработка изображений с помощью метода LBP (Local Binary Patterns). Известия МГИУ №3 (27), 2012, с.42.

4. Ojala Т., Pietikainen М., Maenpaa Т. Multi resolution gray-scale and rotation invariant texture classification with local binary patterns. - IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol.24. N7. Jul 2002. P.971-987.

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