Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6




Скачать 312.68 Kb.
НазваниеЛитература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6
страница2/4
Дата конвертации17.02.2013
Размер312.68 Kb.
ТипЛитература
1   2   3   4

БЫСТРЫЙ АЛГОРИТМ ГЛОБАЛЬНОЙ КОМПЕНСАЦИИ ДВИЖЕНИЯ основанный на бинаризации кадров

Мочалов И.С., Жуков А.А., Новожилова Т.В.

Ярославский Государственный Университет им. П.Г. Демидова

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

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

    Рассмотрим случай, когда макроблоки (блоки пикселей N*N) одного видеообъекта испытывают однородное перемещение. Такое движение возникает при панорамной видеосъёмке, приближение камеры к сцене, различных поворотах. В таких случаях, возникает возможность передавать относительно малое число параметров движения (деформации), которое описывает глобальное изменение всей плоскости видеообъекта. Инструмент, использующий описанный выше подход называется GMC (Global Motion Compensation) глобальная компенсация движения. Механизм GMC позволяет существенно увеличить сжатие, когда большая часть макроблоков из плоскости видеообъекта имеют одинаковые характеристики движения. Для каждого пиксела индивидуальный вектор движения вычисляется с помощью интерполяции векторов GMV (Global Motion Vectors). Такой механизм позволяет строить компенсацию для широкого типа движений: различные вращения, наплывы, деформации, сдвиги и линейные перемещения.

    Предлагаемый алгоритм быстрой глобальной компенсации движения позволяет вычислять GMV при аффинных преобразованиях масштабирования и сдвига. На первом этапе исходное изображение , обрабатывается фильтром Лапласа с целью выделения контуров объектов. Полученное высокочастотное изображение бинаризуется с помощью пороговой обработки. Результатом бинаризации являются два бинарных изображения и . Выбор порога зависит от уровня высокочастотного шума, который может быть оценен [2], как .

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

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

    или .

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







    а)

    б)

    Рис 1. Бинарные изображения а) «+» б) «-»

На втором этапе происходит определение параметров глобального движения и . Параметр масштабирования ищется на основе информации о числе ненулевых элементов в и . . После того, как найден параметр (если ) оба изображения разбиваются на блоки. Размер блоков может быть различным, но для получения существенного выигрыша (более 25 раз) в быстродействии необходимо, чтобы число пикселей в блоке было больше 100. Каждый блок представляет собой бинарное изображение размером L*L. Обозначим – множество пикселей, принадлежащих –му блоку.

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

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

. (1).

Как видно из (1) второй элемент зависит только от выбора общей области и практически не изменяется. Для вычисления первого элемента требуется 4 действия сложения/вычитания для каждого блока и каждого смещения. Пример функции , для области поиска 129*129, приведен на рис. 2. Стоит отметить, что, как и более сложные алгоритмы, данный алгоритм может быть ускорен, на основе применения алгоритма иерархического поиска.

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

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

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





Рис 2. Минимизируемая функция

Рис 3. Минимизируемая функция

Литература

1. Ричардсон Я. Видеокодирование. H.264 и MPEG-4 – стандарты нового поколения. ─ Москва: Техносфера, 2005.

2. Taswell C. The what, how and why of wavelet shrinkage denoising // Computing in Science and Engneering, pp. 12–19, 2000.


NEW FAST GLOBAL MOTION COMPENSATION ALGORITHM based on frame binaryzation

Mochalov I., Ghukov A., Novoghilova T.

Yaroslavl State University

Global motion compensation (GMC) is an important step in video coding and pattern recognition in video. It is needed in automatic video object segmentation for content-based video coding and useful in motion compensation.

Global motion refers to the motion which brings the background from previous frame to current frame. It can be represented in different models such as the simple 2-parameter translation, 6-parameter affine motion, etc.

The estimation of global motion parameters (GMP) can be achieved in many different ways. A common approach focuses on minimizing the squared intensity differences between the current and prediction frames. Optimization is performed to find the GMP which gives the minimum intensity difference. The high computation is due to the need of computing many sets of GMPs for each consecutive two frames. In this paper, we propose a new fast GMC method based on binarization of frame.

    This method allows compute global motion parameters if referred image was translate or scale. Firstly current image, for edges detection processes by Laplace filter. Then output image transformed into binary and. This operation also employed to refer image and.

    To find scaling parameter and translation parameter next maximization tasks mast be solved

    or .

For fast definition we purpose to use integral image, that allow to fast getting sum of elements belong to square region of image.

Due to integral image this task can be writing ,

where is common region of current and scaled refer image.

    On last stage translate parameter precise to achieve half-sample or quarter-sample precision. For this task cumulative sum interpolates. Purposed algorithm allows decry low complexity.






АЛГОРИТМ СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ДИСКРЕТНОГО ПСЕВДОКОСИНУСНОГО ПРЕОБРАЗОВАНИЯ

Курина В.В., Умняшкин С.В.

Московский государственный институт электронной техники (технический университет)

В настоящее время известно множество быстрых алгоритмов вычисления дискретного косинусного преобразования (ДКП), разработанных для различных задач сжатия изображений и видео. Они дают возможность сократить количество операций умножения, необходимых для выполнения преобразований, но, тем не менее, не позволяют полностью исключить эту операцию. В данной работе предлагается использовать для сжатия изображений с потерями дискретное псевдокосинусное преобразование (ДПКП) [1] – простую в вычислении аппроксимацию ДКП, сохраняющую свойство ортогональности. Матрица преобразования W получается с помощью замены значений тригонометрических функций в матрице ДКП их приближенными значениями, что позволяет представить её в виде произведения двух матриц специального вида: . Матрица состоит только из чисел {-2, -1, 1, 2}, а, следовательно, при умножении на эту матрицу можно использовать только операции сложения. Умножение вектора на нормирующую диагональную матрицу можно объединить с процедурой скалярного квантования. Алгоритм сжатия изображений на основе такого преобразования будет востребован в устройствах с ограниченными аппаратными ресурсами, например, карманных компьютерах или мобильных телефонах, а также при реализации в СБИС.

Базовая «JPEG-подобная» схема сжатия включает стандартные этапы: выполнение преобразования, квантование и арифметическое кодирование. Обработка изображения производится по блокам размера . На этапе вычисления двумерного ДПКП сначала строки каждого блока изображения, затем столбцы полученной матрицы умножаются на матрицу . Скалярное квантование объединяется с умножением на матрицу благодаря введению специального шага квантования .

Арифметическое кодирование выполняется с адаптивными статистическими моделями [2]. Для сокращения объема алфавита арифметического кодирования модули коэффициентов кодируются отдельно от их знаков, кроме того, каждый блок разделяется на 8 зон, кодируемых независимо друг от друга. Зоны выбирались таким образом, чтобы дисперсии коэффициентов были близки, и наиболее коррелированные коэффициенты входили в одну зону.

Пусть – проквантованный коэффициент ДПКП с номером в блоке с координатами (начало координат – блок в левом верхнем углу), нумерация внутри блока – от левого верхнего угла по строкам. Зону, в которой все коэффициенты равны нулю, будем называть нулевой. Для описания нулевых зон каждому блоку поставим в соответствие 8-ми битовый ключ. Если все коэффициенты -ой зоны равны нулю, то -ый бит ключа для этого блока равен 0, если хотя бы один коэффициент отличен от нуля, то -ый бит равен 1. Для арифметического кодирования ключей формируется отдельный поток данных.

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

  1. Арифметическое кодирование постоянной составляющей. Вычисление разности для двумерной дифференциальной импульсно-кодовой модуляции (ДИКМ): . Абсолютное значение разности кодируется в отдельном потоке. Если , то знак (1 бит) записывается в поток знаков.

  2. Формирование ключа блока и его арифметическое кодирование.

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

К приведенному базовому алгоритму можно применить ряд модификаций, что позволит повысить эффективность сжатия, но в той или иной степени увеличит вычислительную сложность. Так, можно использовать квантование с нулевой зоной (dead zone quantization). В этом случае пороги квантования имеют вид: {..., –3kq, –2kq, –kq, kq, 2kq, 3kq,…}, а уровни квантования вычисляются как среднее арифметическое соседних порогов. Такое квантование при k = 1 используется, например, в стандартах JPEG2000, MPEG-2, H.263. Результаты обработки нескольких изображений показали, что оптимальным также является значение k = 1.

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

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

Возможности повышения эффективности алгоритма сжатия исследуется с помощью теории «битовые затраты-искажение» (rate-distortion theory, R-D theory). Этот подход описан для алгоритмов сжатия изображений, основанных на ДКП [3] и вейвлет-преобразовании [4]. Задача RD-оптимизации заключается в следующем: необходимо найти такой набор ключей блоков и такую величину шага квантования , которые бы обеспечивали минимум функции Лагранжа:

. (3). Здесь – всевозможные наборы ключей блоков; – заданный неотрицательный параметр, определяющий соотношение ошибки восстановления изображения и битовых затрат на его кодирование: чем больше значение , тем хуже качество изображения, и тем меньше битовые затраты; D – ошибка квантования (в силу ортогональности ДПКП равная ошибке восстановления изображения), , R – битовые затраты на арифметическое кодирование.

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

Пусть () – значение (минимальное) функции Лагранжа для блока с координатами ; () – значение (минимальное) функции Лагранжа для всего спектра, ; и – ошибка квантования и битовые затраты на кодирование блока с координатами соответственно. Функция возвращает оценку вероятности символа w в соответствии с текущим состоянием модели кодирования с номером r. Поиск набора ключей блоков , минимизирующего функцию L при заданных значениях q и , выполняется по следующему алгоритму (последовательно для каждого блока):

    Определить базовый ключ блока .

  1. Определить значение разности для двумерной ДИКМ.

  2. Вычислить – функцию Лагранжа для данного блока: , .

  3. Выполнить перебор всевозможных ключей. С текущим значением ключа k вычислить . Если , то , .

  4. При l = 1,…, 63, если и , то положить .

  5. Выполнить виртуальное кодирование блока с ключом .

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

Количество итераций в процедуре RD-оптимизации можно уменьшить за счет сокращения вариантов поиска оптимальных значений шага квантования и ключей. Так, например, эксперименты показали, что перебор всевозможных ключей на шаге (5) не требуется. Достаточно рассмотреть ключи, получаемые из базового заменой на каждой итерации одного бита, равного 1, на 0. Также выяснилось, что связь между значением шага квантования q и параметра может быть приближенно описана соотношением: , где С – некоторая общая для различных изображений константа, что позволяет сузить интервал поиска оптимального шага квантования.

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

На графике (Рисунок 1) приведены результаты, полученные при сжатии изображений «Barbara» и «Lena» модифицированным вариантом предлагаемого алгоритма и алгоритмом JPEG на основе ДКП. Сжатие по стандарту JPEG выполнялось с помощью программы Advanced Batch Converter 3.9.24. При анализе экспериментальных результатов из размера полученного файла JPEG вычиталась длина его заголовка.




Рис. 1. График зависимости величины PSNR от количества бит на пиксель изображения


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

Предложенный алгоритм по характеристикам PSNR и степени сжатия не уступает JPEG на базе ДКП, более того, на мелко-детальных «высокочастотных» изображениях (типа «Barbara») показывает преимущества, а значит в приложениях, имеющих ограничения на аппаратные ресурсы, может успешно его заменить.

Работа выполнена при поддержке гранта Президента Российской Федерации МД-6172.2008.9.
1   2   3   4

Похожие:

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАдаптивная обработка сигналов
Обработки сигналов» и «Радиотехнические цепи и сигналы». Знания и навыки, полученные при изучении дисциплины «Адаптивные системы»,...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЛитература. Обработка изображений
Ярославский Л. П. Цифровая обработка сигналов в оптике и голографии. М.: Радио и связь, 1987. 296 с

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЦифровая обработка сигналов
...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconУчебно-методический комплекс (умк) дисциплины «Цифровая и аналоговая обработка сигналов» для специальности кафедры ту
Курячий М. И. Цифровая обработка сигналов: Учебное пособие для вузов с грифом умо. – Томск: Томск гос ун-т систем упр и радиоэлектроники,...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconНовые книги, поступившие в библиотеку с 16-29 февраля 2012 г. Автоматизация сельского хозяйства
Радченко Г. Е. Автоматизация сельскохозяйственной техники : учебно-методическое пособие / Г. Е. Радченко. Минск : ивц минфина, 2011....

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАлгоритм вейвлет-сжатия неподвижных цифровых изображений с использованием оптимального базиса на соответствующих уровнях разложения
Овых изображений с использованием оптимального базиса класса Добеши на каждом уровне разложения Показано, что предложенный алгоритм...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЦифровая обработка многомерных сигналов модифицированный билатеральный фильтр для улучшения качества jpeg-изображений
Для удаления блочного эффекта в сжатых изображениях можно использовать билатеральный фильтр (БФ) [4, 5]. Однако прямое его применение...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconСжатие изображений на основе их сегментного представления
Рассматривается алгоритм восстановления изображения из кода и приводится оценка коэффициента сжатия, полученная на разработанной...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАлгоритм сжатия неподвижных цифровых изображений с использованием оптимального базиса класса Добеши на каждом уровне вейвлет разложения
Добеши на каждом уровне разложения Показано, что предложенный алгоритм при обработке 8-ми битных монохромных изображений превосходит...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconВ. В. Сюзев цифровая обработка сигналов: методы и алгоритмы
Включен так же ряд оригинальных результатов в области разработки быстрых алгоритмов обработки на скользящих интервалах времени и...


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница