(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 8. Другие методы кодирования изображений

Поиск осуществляется путем вычисления знаков скалярных произведений векторов-нормалей, опущенных из точки-блока на упомянутые выше гиперплоскости, и характеристических векторов этих гиперплоскостей [3.83]. При этом количество операций на блок снижается со значения порядка k до log2 k.

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

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

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

Еще одним специфическим вариантом блочного кодирования является использование неунитарного интерполяционного преобразования [3.17].

При этом изображение разбивается на блоки, скажем 4 × 4 пикселов X(i, j), i, j = 0, . . . , 3. Алгоритм передачи для каждого блока определяется, например, следующим образом:

–значение X(0, 0) передается непосредственно,

–величина X(3, 3) передается путем ее предсказания по переданному значе-

ˆ

нию X(0, 0),

– величины X(0, 3) и X(3, 0)	ˆ	ˆ
	предсказываются по значению [X(0, 0)+X(3, 3)]/2.

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

Несколько слов следует сказать об интерполяционном и экстраполяционном кодировании [3.17]. При этом в изображении выбирается набор базовых пикселов, для передачи которых используются различные варианты рассмотренных методов кодирования. Остальные пикселы восстанавливаются при помощи интерполяции/экстраполяции. В методах с фиксированными позициями базовых пикселов передаются всегда одни и те же значения пикселов.

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

8.2. Другие методы блочного и интерполяционного кодирования

Рис. 8.1. Разбиение пространственно-частотной области изображений

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

Особенно эффективной следует считать интерполяцию, адаптивную к движению объектов в изображении [3.17, 3.84]: интерполяции подвергается пиксел (k − 1)-го кадра с координатами (x + x/2, y + y/2) по значениям пикселов (k − 2)-го кадра с координатами (x,y) и k-го кадра с координатами (x + x, y + y).

При обзоре различных методов кодирования следует упомянуть также о методе, имеющем название «пирамида Лапласа» [3.17, 3.85–3.87].

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

fгр; fгр/k; fгр/k2; . . . .

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

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

Исследования показывают, что, если выбрать fx1 = 13 fx гр и fy1 = 13 fy гр и исключить область IV, как показано на рис. 8.1, справа, искажения телевизионных изображений малозаметны, в то время как эффективное напряжение помехи в изображении уменьшается почти в два раза.

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

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

Глава 8. Другие методы кодирования изображений

Рис. 8.2. Прореживание спектральной области I по горизонтали и вертикали

изображение «Залив» и прореженное изображение области I.

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

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

Дальнейшее уменьшение объема информации об областях II и III без устранения избыточности возможно путем свертки их спектров g2(x, y) и g3(x, y), приведенных на рис. 8.3, по высокочастотным направлениям с комплексными

величинами:			·		−			2
2	2
g (x, y) = g		(x, y)		exp	−	2π i	fx гр − fx1				x ;
3	3		·					2
g (x, y) = g		(x, y)		exp		2π i	fyгр − fy1			y .
При этом выделяются четыре изображения:
Re[g2(x, y)]; Im[g2(x, y)];					Re[g3(x, y)]			и	Im[g3(x, y)]

и прореживается каждое из них в три раза, как показано на рис. 8.4.

Каждое из этих изображений имеет объем информации в 9 раз меньший, чем исходное изображение.

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

8.3. Другие методы блочного и интерполяционного кодирования

Рис. 8.3. Прореживание спектральных областей II и III

Рис. 8.4. Преобразованные составляющие изображения, приведенные на рис. 8.3

Глава 8. Другие методы кодирования изображений

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

Фрактальные методы сжатия считаются одними из наиболее эффективных методов по степени сжатия изображения [3.88–3.97].

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

Рис. 8.5. Способ фрактального преобразования изображения

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

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

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

–во-вторых, оно определяется исключительно процедурой преобразования;

–в-третьих, дальнейшие преобразования будут преобразовывать его в самого себя;

–в-четвертых, оно может иметь сколь угодно мелкие детали.

Изображения такого типа называются аттракторами, а преобразования —

фрактальными.

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

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

ординат x и y:	2	y	3	=	2	ci	di	3	·	2	y	3	+	2	fi	3	,	(8.2)
Wi
		x				ai	bi				x				ei

где ai, bi, ci, di, ei, fi — параметры преобразования.

8.3. Фрактальные методы кодирования изображений

Рис. 8.6. Фрактальное преобразование различных изображений

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

На рис. 8.7 показано несколько процедур преобразования и их аттракторов:

–в верхнем ряду — описанное выше преобразование;

–в среднем ряду — аналогичное преобразование при дополнительном повороте верхней детали;

–в нижнем ряду — более сложное преобразование с поворотом деталей на разные углы и их масштабированием.

Последний случай наиболее интересен и имеет название «папоротник Барнсли» (Barnsley). Этот внешне сложный рисунок получен за счет четырех аффинных преобразований, каждое из которых имеет шесть параметров (см. приведенное матричное уравнение).

Такие самоподобные рисунки называются фракталами. Если перемножить число преобразований (4), число параметров (6) и число битовов под хранение каждого из параметров (например, 32) то получим 4 × 6 × 32 = 768 битов — столько битов необходимо для хранения способа получения этого изображения.

В то же время приведенное штриховое изображение (1 бит/пиксел) папоротника имеет разрешение 256 × 256 пикселов. Для прямого хранения такого изображения необходимо 65 536 битов. То есть рассматриваемая схема позволяет «сжать» изображение примерно в 85 раз. Обратим внимание на некоторую условность такого определения коэффициента сжатия. Дело в том, что для хранения алгоритма преобразования требуется определенное, заранее известное, количество битов, но этот алгоритм позволяет создать изображение любого размера с достаточно мелкими деталями, для хранения которого требуется другое (воз-

Глава 8. Другие методы кодирования изображений

Рис. 8.7. Различные фрактальные преобразования изображений

можно, существенно большее) количество битов. Соответственно размеру изображения будет меняться и коэффициент сжатия.

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

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

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

Пусть яркость пикселов изображения z задана некоторой функцией

z = f (x, y),

где x, y — координаты пикселов. Положим, z может иметь 256 фиксированных уровней. Само аффинное преобразование i-го блока полутонового изображения будет выглядеть следующим образом:

8.3. Фрактальные методы кодирования изображений

Рис. 8.8. Иллюстрация к подобию деталей в одном изображении

w	y		=	ci		di	0
	x				ai	bi	0
	z				0	0	si

xei

· y + fi

zoi

, (8.3)

где ai, bi, ci, di, ei, fi — параметры аффинного преобразования, si, oi — коэффициенты преобразования контраста и яркости блока.

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

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

Берется квадрат, например, в два раза большего размера 8 ×8, и путем усреднения по четырем соседним пикселам из него формируется квадрат 4 × 4.

Этот квадрат ориентируется в одном из восьми различных положений: четыре положения определяются его поворотом на 90 градусов и еще четыре – поворотом на 90 градусов его зеркального отражения.

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

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

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

Глава 8. Другие методы кодирования изображений

)

·

−

·

*%

−

2

n

n

n

n

n

n

n

si =

n

zpk zdk

zpk

zdk

n

zpk2

zpk

,

(8.4)

k=1

k=1

k=1

k=1

k=1

oi = )

zdk − si

zpk*% n;

(8.5)

k=1

k=1

k-х

!

!

2

!

n

n

n

если n k=1 zpk2 −

k=1 zpk = 0, то si = 0 и oi = k=1 zdk /n ; zpk, zdk — яркости

пикселов i-й ранговой области и домена, n - число пикселов в домене.

В этом случае среднеквадратичное отклонение яркостей домена и ранговой

области может быть определено формулой:

Ri = )

zdk2

+ si ·

si

n

zpk2 − 2

zpk · zdk

+

n

n

k=1

k=1

k=1

+ oi oi · n − 2

n zdk

*%n2.

(8.6)

+ 2oi n

zpk

k=1

k=1

Такие операции проводятся по всем восьми возможным ориентациям квадрата. Для определения истинной ранговой области данного домена необходимо перебрать все возможные квадраты 8 × 8 изображения.

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

	На рис. 8.9 представлено		исходное изоб-
	ражение, которое использовалось для сжатия.
	Рис. 8.10 иллюстрирует процесс восстановления
	изображения, сжатого фрактальным методом.
	В верхнем левом углу представлено исходное
	изображение (белое поле).
	Пять первых итераций процесса генерации
	изображения (аттрактора), близкого к исход-
	ному по установленным алгоритмам преобразо-
	вания координат ранговых областей, а также
	изменения коэффициентов их контраста и яр-
Рис. 8.9. Исходное изображение для	кости представлены далее	на	рис.	8.10 слева
фрактального сжатия	направо и сверху вниз.
	Исходное изображение	было		разбито на

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

8.3. Фрактальные методы кодирования изображений

Рис. 8.10. Восстановление из белого поля изображения (аттрактора), сжатого фрактальным методом

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

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

На рис. 8.11 представлено восстановленное изображение для разбиения на домены 4 × 4 пиксела. Следует заметить, что такой размер домена обеспечивает очень хорошее воспроизведение исходного изображения.

На рис. 8.12 представлено восстановленное изображение для разбиения на домены 8 × 8 пикселов. Видно, что такой размер домена обеспечивает более низкое качество воспроизведения исходного изображения на рисунке в областях с высокочастотными деталями (например, волосы и серьги девушки) виден характерный межблочный эффект.