13.02.2017 ura

ОБЗОР ФОРМАТА JPG (JPEG)




ГОНСАЛЕС-ВУДС | ЦВЕТНОЙ JPG | СЖАТИЕ | INKSCAPE
ЛАБОРАТОРНЫЕ ОПЫТЫ | HABRAHABR


Тракт обработки данных с помощью ортогональных матриц в общих его чертах сходен с одним из самых первых алгоритмов сжатия изображений, который мы подробно рассмотрим с численными примерами. Аббревиатура JPEG расшифровывается как Join Photographic Experts Group (объединенная группа экспертов-фотографов) – организация, которая создала этот формат. Степень сжатия задается условным числом q, которое изменяется от 1 до 100 (или от 1 до 10). Основным этапом работы алгоритма является нахождение матрицы дискретного косинусного преобразования Фурье (ДКП)

Dij=(1/n)1/2, если j=0, Dij=(2/n)1/2cos((2i+1)jπ/(2n)), если j>0


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



Рисунок 1. Матрица дискретного косинусного преобразования


Мы предпочитаем использовать столбцовую форму ортогональной матрицы D (базисные векторы – столбцы), поэтому знак транспонирования ставится у первой матрицы при нахождении спектра S=D'(P–128J)D, где P – фото, J – матрица всех единиц, D – ортогональная матрица. На рисунке – тракт сжатия с транспонированием при второй матрице D (если базис составляют строки матрицы).

Первый столбец матрицы D имеет, как видно, самую низкую "частоту" (нулевую), следующие столбцы содержат чаще осциллирующие последовательности, управляемые множителем jπ/(2n).

Типичный тракт обработки изображений предполагает вычисление спектра выделенного фрагмента P в результате подобного преобразования, которое в случае ортогональных матриц, обозначаемых D (D–1=DT), принимает вид

S=D–1PD=DTPD, обратно: P=DSDT


Существует спектральное разложение симметричных матриц P=PT=VSVT – собственные числа (элементы диагонали диагональной матрицы S) вещественны и совпадают по модулю с сингулярными числами P, а собственные вектора (столбцы V) ортогональны, их называют еще сингулярными векторами. Спектр S является диагональной матрицей, если матрица D совпадает с матрицей V сингулярного разложения P.

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

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

Так зачем же она, эта матрица S?

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

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

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

Следует отчетливо понимать, что и фильтрация сама по себе тоже не приводит к сжатию. Замена одних значений спектра изображения на другие, приглаженные, ничего формально не меняет. В самом деле, нет разницы, хранить в файле число 125 или, скажем, 110. Откуда сжатие? Дело все в том, что при понижении амплитуд значения некоторых пикселей сливаются, в спектре появляются цепочки одинаковых элементов. Примитивное сжатие реализуется так, например, что вместо хранения всех элементов цепочки мы можем хранить одно значение. Указав дополнительно, сколько таких элементов в цепи.

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

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

Не путайте механизмы нахождения спектра и фильтрации с самим сжатием, они лишь создают почву для него, поджимая спектры по амплитуде. Если нет алгоритма Хаффмана, под рукой, сжимайте методом PNG. Это сжатие примерно так и устроено. Кстати, парадоксально, но факт. Ортогональное преобразование с фильтрацией могут рассматриваться как лишние, ненужные и вредные операции, которые только портят картинку и создают ненужные всем хорошо известные проблемы разводов и ореолов. Именно поэтому и появился PNG без них, и этот алгоритм получил широкое распространение.

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

Например, нужно сжать следующий фрагмент изображения со значениями элементов от 0 до 255

P=
 95 
  88 
  88 
  87 
  95 
  88 
  95 
  95 
 143 
 144 
 151 
 151 
 153 
 170 
 183 
 181 
 153 
 151 
 162 
 166 
 162 
 151 
 126 
 117 
 143 
 144 
 133 
 130 
 143 
 153 
 159 
 175 
 123 
 112 
 116 
 130 
 143 
 147 
 162 
 189 
 133 
 151 
 162 
 166 
 170 
 188 
 166 
 128 
 160 
 168 
 166 
 159 
 135 
 101 
  93 
  98 
 154 
 155 
 153 
 144 
 126 
 106 
 118 
 133 


Рисунок 2. Матрица изображения P для пробы дискретного косинусного преобразования


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

Note. Квазиортогональная матрица перед умножением обязательно нормируется до просто ортогональной делением каждого столбца на число, равное его норме (длине)). Непосредственно нормируется, или делитель (длина) "держится в уме". Операция умножения вектора сигнала на ортогональную матрицу – это операция поворота вектора без изменения его длины.

Если брать координатами вектора только положительные числа диапазона [0,255], то поворот выведет вектор из этого диапазона, мы покинем диапазон разрешенных чисел. Появятся отрицательные координаты, не укладывающиеся в разрешенные значения. Для ряда микропроцессоров это критично важно.

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

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

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

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

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


Затем происходит переход к спектральной матрице S=D'(P–128*J)D, J – матрица единичных элементов, см. рис. 3



Рисунок 3. Изображение P и двухмерный спектр изображения S=D'(P–128*J)D

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

S=
 92.25 
  2.3946 
  –7.8856 
  –7.4139 
  3.7504 
  –1.2731 
  0.5609 
  1.4337 
  –38.7254 
  –57.2544 
  11.4181 
  17.4934 
  –2.4737 
  2.1859 
  4.0216 
  2.31 
  –85.2144 
  63.5258 
  –0.3419 
  –16.9772 
  2.5046 
  4.6248 
  –5.5371 
  4.9267 
  –51.8996 
  –36.9947 
  –9.6905 
  13.089 
  –9.2524 
  3.0976 
  –1.7001 
  0.2885 
  –85.7501 
  –41.2717 
  50.1194 
  –8.2787 
  18.2506 
  –6.6955 
  –1.8177 
  4.5015 
  –63.2377 
  66.1383 
  –13.0008 
  –0.5269 
  2.3776 
  –7.536 
  –2.3394 
  0.6346 
  –16.9282 
  14.6428 
  –36.536 
  17.6617 
  –11.5911 
  3.2022 
  2.8403 
  –1.0386 
  –52.8234 
  30.6848 
  –7.2563 
  –9.8128 
  23.3477 
  –0.9328 
  1.4353 
  2.7026 



Теперь пора применить фильтр низкой частоты (ФНЧ), использовав в качестве матрицы пропусных коэффициентов гиперболическую зависимость

Fij=1/(1+(1+i+j)*q),


где q – коэффициент подавления, рассматриваемый в диапазоне от 0 до 100. Числитель этой зависимости называется матрицей квантования Q.



Рисунок 4. Матрица фильтра F матрица квантования Q




Рисунок 5. Частотная характеристика фильтра нижних частот (ФНЧ)




В результате фильтрации спектра S=F.*S=S./Q (поточечные умножение или деление) получим много нулевых элементов на канве (после округления).



Рисунок 5. Спектр изображения до и после фильтрации



Для подсчета последовательностей нулей развернем отфильтрованную матрицу спектра в последовательности змейкой: номерами показана последовательность Z перебора элементов.

Z=
1
2
6
7
 15 
 16 
 28 
 29 
3
5
8
 14 
 17 
 27 
 30 
 43 
4
9
 13 
 18 
 26 
 31 
 42 
 44 
 10 
 12 
 19 
 25 
 32 
 41 
 45 
 54 
 11 
 20 
 24 
 33 
 40 
 46 
 53 
 55 
 21 
 23 
 34 
 39 
 47 
 52 
 56 
 61 
 22 
 35 
 38 
 48 
 51 
 57 
 60 
 62 
 36 
 37 
 49 
 50 
 58 
 59 
 63 
 64 


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

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

Восстановим изображение обратными операциями P=D*S.*Q*D'+128*J и отметим, что при коэффициенте фильтрации (регулятора степени сжатия) q=2 амплитуда искажения восстановленного изображения достигает 10, при q=2 это значение удваивается, но в дальнейшем растет не столь быстро. .



ВИКИУЧЕБНИК | ДЕМО | ПРИМЕР | АЛГОРИТМ ХАФФМАНА НА JAVASCRIPT


Днем рождения PNG можно считать 4 января 1995 года, когда Т. Боутелл предложил в ряде конференций Usenet создать свободный формат, который был бы не хуже GIF. И уже через три недели после публикации идеи были разработаны четыре версии нового формата. Уже в декабре того же года спецификация PNG версии 0.92 была рассмотрена консорциумом W3C, а с выходом 1 октября 1996 года версии 1.0 PNG был рекомендован в качестве полноправного сетевого формата.

Формат PNG спроектирован для замены устаревшего и более простого формата GIF, а также, в некоторой степени, для замены значительно более сложного формата TIFF. PNG с самого начала использует открытый, непатентованный алгоритм сжатия Deflate, бесплатные реализации которого доступны в Интернете. Этот же алгоритм используют многие программы компрессии данных, в том числе PKZIP и gzip (GNU zip).

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

Особенность вайвелет-преобразований состоит в том, что при одинаковой частоте "волны-всплеска" в базисе появляются функции, зависящие от пространственной координаты x. Таким образом, если менять еще и частоту w, спектр сигнала стоновится трехмерным в том смысле, что амплитудная характеристика здесь – функция двух параметров A=A(w,x). От плоского спектра мы переходим к трехмерному. Это достоинство и недостаток, одновременно (избыток информации).

WIKI | ОБЗОР МЕТОДОВ | ПРИМЕР (С ОШИБКОЙ) | RGB-РАСКЛАДКА | ЕЩЕ

Hide

Rambler's Top100