Этот пост — погружение в кроличью нору. Разработчик Монсеф Аббад задумался о изображениях — вероятно, после недавнего изучения им некоторых схем компрессии. Общеизвестно, что изображения бывают либо полутоновыми, либо RGB, когда новые цвета создаются на основе смешения красного, зелёного и синего. Но для хранения изображения требуется нечто большее, чем просто выравнивание трехбайтовых значений RGB.
Что-то в этой идее пробудило любопытство автора, поэтому в статье он попытался удовлетворить его и ответить на вопрос: как на самом деле хранятся изображения?
Основы
Изображение — это набор пикселей. Пиксель — наименьшая единица цвета в изображении. Рассмотрим следующее изображение из известного датасета MNIST:
Это изображение состоит из 28x28 пикселей (или квадратов). Оно выполнено в градациях серого, то есть каждый пиксель имеет значение от 0 до 255, где 0 — чёрный, а 255 — белый.
А как насчет цветных изображений? В них также используются пиксели, но каждый пиксель хранится в виде RGB-триплета. Для каждого пикселя 3 байта представляют его цвет: красный, зеленый и синий. (0, 0, 0) — это чёрный цвет, а (255, 255, 255) — белый. Суть в том, что при отсутствии светлого (0, 0, 0), цвет — чёрный, а смешивая максимальное количество каждого цвета, вы получаете белый. Красный — это (255, 0, 0), зеленый — (0, 255, 0), а синий — (0, 0, 255).
RGB может иметь четвёртый компонент, называемый альфа, что делает его RGBA. Альфа указывает на непрозрачность или прозрачность пикселя. Он полезен при создании изображений, поскольку определяет, как обрабатывается прозрачность. Чем прозрачнее пиксель, тем меньше он скрывает фон за ним. При наложении двух изображений альфа-значение каждого пикселя определяет видимость фонового изображения через соответствующий пиксель изображения переднего плана.
Рассмотрим знаменитый клетчатый узор, который часто используется для обозначения прозрачности. В левой части изображения непрозрачность высокая (альфа-значение высокое), что делает фон невидимым. Напротив, в правой части, где непрозрачность ниже (альфа низкая), клетчатый фон становится видимым.
Если мы храним цветное изображение (3 байта на пиксель) размером 1920x1080 без сжатия, то только для одного изображения нам потребуется 1920x1080x3 = 6 220 800 байт (около 6 МБ)!
1080p — обычное дело для видео, в то время как 240p (разрешение VHS) считается низким качеством. 480p — это нормально и соответствует качеству DVD.
Если бы мы передавали несжатое видео 1080p с частотой 24 кадра в секунду, это потребовало бы более 1 гигабита в секунду, что просто колоссально! Поэтому, если не использовать сжатие и другие ухищрения, потоковая передача высококачественного видео будет невозможна.
Алгоритмы сжатия без потерь обычно достигают коэффициента сжатия в лучшем случае 3:4. Алгоритмы, которые достигают таких высоких коэффициентов, часто требуют больших вычислительных затрат и работают медленно, что делает их непригодными для потоковой передачи в реальном времени. Даже коэффициента 3:4 недостаточно для передачи видео высокого разрешения с высокой частотой кадров.
Именно здесь на помощь приходит сжатие с потерями. Отбрасывая часть данных, мы можем добиться гораздо лучшего коэффициента сжатия. Схемы сжатия с потерями часто включают параметр качества, указывающий, в какой степени мы готовы пожертвовать качеством в обмен на лучший коэффициент сжатия.
Форматы без потерь
GIF
Graphical Interchange Format, GIF (произносится как «gif» от «gift») — это формат сжатия изображений без потерь. В нем используется фиксированная палитра из 256 цветов, каждый из которых задается 3 байтами для RGB. И вместо того, чтобы использовать 3 байта для кодирования каждого пикселя, мы используем индекс, указывающий на один из цветов в палитре. Идея здесь в том, что палитра содержит достаточно оттенков для передачи изображения. Таким образом, при 256 цветах нам нужен всего 1 байт для хранения индекса и коэффициент сжатия составляет 3:1. Хотя маловероятно, что изображение в реальном мире имеет только 256 цветов, некоторая форма сжатия должна была произойти раньше. Однако сам GIF не отвечает за это сжатие.
Изображения хранятся в виде массива w × h 8-битных индексов палитры, которые затем кодируются с помощью техники LZ (повторяющиеся последовательности с обратной ссылкой).
Разумеется, GIF известен тем, что может хранить несколько изображений в одном файле, что позволяет создавать анимированные изображения.
Давайте посмотрим на реализацию GIF в стандартной библиотеке Go. Полагаю, изучение того, как список изображений и задержки между ними используются для создания правильного GIF, поможет лучше понять этот формат:
images := []*image.Paletted{...}
// The successive delay times, one per frame, in 100ths of a second
// In this example, we have three images with 0.5 second delay between each
delays := []int{50,50,50}
f, _ := os.OpenFile("amazing.gif", os.O_WRONLY|os.O_CREATE, 0600)
defer f.Close()
gif.EncodeAll(f, &gif.GIF{
Image: images,
Delay: delays,
})API для создания GIF в Go достаточно прост: нужно передать список изображений с палитрой и задержки между ними и сохранить результат в нужный нам файл.
Взглянем на структуру Paletted:
package image
// Paletted is an in-memory image of uint8 indices into a given palette.
type Paletted struct {
// Pix holds the image's pixels, as palette indices. The pixel at
// (x, y) starts at Pix[(y-Rect.Min.Y)*Stride + (x-Rect.Min.X)*1].
Pix []uint8
// Stride is the Pix stride (in bytes) between vertically adjacent pixels.
Stride int
// Rect is the image's bounds.
Rect Rectangle
// Palette is the image's palette.
Palette color.Palette
}
type Palette []Color
// Color can convert itself to alpha-premultiplied 16-bits per channel RGBA.
// The conversion may be lossy.
type Color interface {
// RGBA returns the alpha-premultiplied red, green, blue and alpha values
// for the color. Each value ranges within [0, 0xffff], but is represented
// by a uint32 so that multiplying by a blend factor up to 0xffff will not
// overflow.
//
// An alpha-premultiplied color component c has been scaled by alpha (a),
// so has valid values 0 <= c <= a.
RGBA() (r, g, b, a uint32)
}
// A Rectangle contains the points with Min.X <= X < Max.X, Min.Y <= Y < Max.Y.
// It is well-formed if Min.X <= Max.X and likewise for Y. Points are always
// well-formed. A rectangle's methods always return well-formed outputs for
// well-formed inputs.
type Rectangle struct {
Min, Max Point
}
// A Point is an X, Y coordinate pair. The axes increase right and down.
type Point struct {
X, Y int
}Палитра определяется следующими полями:
Rectangle, который определяется верхней левой точкой (min) и нижней правой точкой (max). Просто и эффективно! Чтобы упростить задачу, предположим, что
Min = (0, 0).color.Palette — массив интерфейсов
Color, служащий, по сути, хранилищем для используемых RGB-цветов.Stride — расстояние между двумя вертикально соседними пикселями; часто это длина строки, т. е.
Max.X - Min.X.Pix — фактические данные изображения в виде индексов цветовой палитры. Массив одномерный, но представляет собой двумерное изображение. Допустим,
Min = (0, 0). Эффективная прогрессия выглядит так:
(0, 0),(1, 0), …,(Max.X-1, 0),(0, 1),(1, 1), …,(Max.X-1, 1),…,
(0, Max.Y-1),(1, Max.Y-1), …,(Max.X-1, Max.Y-1).
Проще говоря, image.Paletted — это список цветов и список пикселей, ссылающихся на эти цвета.
Палитризованные изображения и задержки используются для инициализации GIF-структуры. Взглянем на неё:
// GIF represents the possibly multiple images stored in a GIF file.
type GIF struct {
Image []*image.Paletted // The successive images.
Delay []int // The successive delay times, one per frame, in 100ths of a second.
// LoopCount controls the number of times an animation will be
// restarted during display.
// A LoopCount of 0 means to loop forever.
// A LoopCount of -1 means to show each frame only once.
// Otherwise, the animation is looped LoopCount+1 times.
LoopCount int
// Disposal is the successive disposal methods, one per frame. For
// backwards compatibility, a nil Disposal is valid to pass to EncodeAll,
// and implies that each frame's disposal method is 0 (no disposal
// specified).
Disposal []byte
// Config is the global color table (palette), width and height. A nil or
// empty-color.Palette Config.ColorModel means that each frame has its own
// color table and there is no global color table. Each frame's bounds must
// be within the rectangle defined by the two points (0, 0) and
// (Config.Width, Config.Height).
//
// For backwards compatibility, a zero-valued Config is valid to pass to
// EncodeAll, and implies that the overall GIF's width and height equals
// the first frame's bounds' Rectangle.Max point.
Config image.Config
// BackgroundIndex is the background index in the global color table, for
// use with the DisposalBackground disposal method.
BackgroundIndex byte
}Отметим, что количество повторов (циклов) настраивается и по умолчанию равно бесконечности, если LoopCount == -1. Также мы видим, что ширина и высота GIF либо задаются явно, либо определяются из размеров первого изображения. Это означает, что изображения внутри GIF могут иметь разные размеры, и здесь становятся важными значения Min и Max в прямоугольнике каждого изображения: они не обязательно должны быть равны глобальным Min и Max.
Disposal указывает, как следует обрабатывать предыдущий кадр. Этот параметр напрямую связан с альфа-каналом RGBA, то есть с параметром прозрачности. Основные методы удаления предыдущего кадра такие:
Unspecified (Ничего). Полностью заменить одно полноразмерное непрозрачное изображение другим.
Do Not Dispose (Оставить как есть). Все пиксели, не покрытые следующим кадром, продолжают отображаться.
Restore to Background (Восстановить фон). Показать изображение, указанное в
BackgroundIndex, через прозрачные пиксели нового кадра.
Config также может содержать color.Palette, которая является глобальной палитрой, общей для всех изображений. У каждого изображения может быть своя палитра, или они могут использовать одну для экономии места, если они достаточно похожи.
Итак. Теперь, когда мы знаем, как выглядят наши структуры, перейдем к самому процессу кодинга:
// EncodeAll writes the images in g to w in GIF format with the
// given loop count and delay between frames.
func EncodeAll(w io.Writer, g *GIF) error {
if len(g.Image) == 0 {
return errors.New("gif: must provide at least one image")
}
if len(g.Image) != len(g.Delay) {
return errors.New("gif: mismatched image and delay lengths")
}
e := encoder{g: *g}
// ...
if e.g.Config == (image.Config{}) {
// If the image has no Config, we use the first image dimensions.
p := g.Image[0].Bounds().Max
e.g.Config.Width = p.X
e.g.Config.Height = p.Y
} else if e.g.Config.ColorModel != nil {
if _, ok := e.g.Config.ColorModel.(color.Palette); !ok {
return errors.New("gif: GIF color model must be a color.Palette")
}
}
// ensure we have a proper write to send our data to
if ww, ok := w.(writer); ok {
e.w = ww
} else {
e.w = bufio.NewWriter(w)
}
e.writeHeader()
for i, pm := range g.Image {
disposal := uint8(0)
if g.Disposal != nil {
disposal = g.Disposal[i]
}
e.writeImageBlock(pm, g.Delay[i], disposal)
}
e.writeByte(sTrailer) // sTrailer = 0x3B => ascii semi-colon to signify EOF
e.flush()
return e.err
}Мне нравится такой код! Читается как обычный абзац. Проверка на ошибки, установка конфига, запись заголовка, затем запись каждого блока изображения и, наконец, запись символа EOF и сброс буфера.
Вот writeHeader с некоторыми дополнительными комментариями от меня:
func (e *encoder) writeHeader() {
if e.err != nil {
return
}
_, e.err = io.WriteString(e.w, "GIF89a") // Magic byte
if e.err != nil {
return
}
// Logical screen width and height.
// written in Little Endian
byteorder.LEPutUint16(e.buf[0:2], uint16(e.g.Config.Width))
byteorder.LEPutUint16(e.buf[2:4], uint16(e.g.Config.Height))
e.write(e.buf[:4])
if p, ok := e.g.Config.ColorModel.(color.Palette); ok && len(p) > 0 {
// write the global palette if we have it
paddedSize := log2(len(p)) // Size of Global Color Table: 2^(1+n).
e.buf[0] = fColorTable | uint8(paddedSize)
e.buf[1] = e.g.BackgroundIndex
e.buf[2] = 0x00 // Pixel Aspect Ratio.
e.write(e.buf[:3])
var err error
e.globalCT, err = encodeColorTable(e.globalColorTable[:], p, paddedSize)
if err != nil && e.err == nil {
e.err = err
return
}
e.write(e.globalColorTable[:e.globalCT])
} else {
// All frames have a local color table, so a global color table
// is not needed.
e.buf[0] = 0x00
e.buf[1] = 0x00 // Background Color Index.
e.buf[2] = 0x00 // Pixel Aspect Ratio.
e.write(e.buf[:3])
}
// Add animation info if necessary.
if len(e.g.Image) > 1 && e.g.LoopCount >= 0 {
e.buf[0] = 0x21 // Extension Introducer.
e.buf[1] = 0xff // Application Label.
e.buf[2] = 0x0b // Block Size.
e.write(e.buf[:3])
_, err := io.WriteString(e.w, "NETSCAPE2.0") // Application Identifier.
if err != nil && e.err == nil {
e.err = err
return
}
e.buf[0] = 0x03 // Block Size.
e.buf[1] = 0x01 // Sub-block Index.
byteorder.LEPutUint16(e.buf[2:4], uint16(e.g.LoopCount))
e.buf[4] = 0x00 // Block Terminator.
e.write(e.buf[:5])
}
}Вот цикл, который кодирует таблицу Palette:
for i, c := range p {
if c == nil {
return 0, errors.New("gif: cannot encode color table with nil entries")
}
var r, g, b uint8
// It is most likely that the palette is full of color.RGBAs, so they
// get a fast path.
if rgba, ok := c.(color.RGBA); ok {
r, g, b = rgba.R, rgba.G, rgba.B
} else {
rr, gg, bb, _ := c.RGBA()
r, g, b = uint8(rr>>8), uint8(gg>>8), uint8(bb>>8)
}
dst[3*i+0] = r
dst[3*i+1] = g
dst[3*i+2] = b
}Ничего сложного. Мы проходим по цветам и последовательно кодируем красные, синие и зелёные байты в целевой буфер.
Собственно данные изображения записываются в writeImageBlock. Он немного длинноват, но самый интересный, на мой взгляд, фрагмент:
for i, c := range p {
if c == nil {
return 0, errors.New("gif: cannot encode color table with nil entries")
}
var r, g, b uint8
// It is most likely that the palette is full of color.RGBAs, so they
// get a fast path.
if rgba, ok := c.(color.RGBA); ok {
r, g, b = rgba.R, rgba.G, rgba.B
} else {
rr, gg, bb, _ := c.RGBA()
r, g, b = uint8(rr>>8), uint8(gg>>8), uint8(bb>>8)
}
dst[3*i+0] = r
dst[3*i+1] = g
dst[3*i+2] = b
}В оригинальном коде rect имеет имя b. Я переименовал его для наглядности.
Мы берем массив Pix из нашей палитры изображения, где каждое значение представляет собой индекс в массиве цветов, затем сжимаем его по схеме lzww и записываем.
Вуаля! В этом и заключается магия кодирования GIF.
Я считаю, что декодер, который отображает GIF-изображение, — то, в чём кроется истинная магия формата. Но это небольшое исследование должно дать нам представление о том, как устроены под капотом все эти реакционные мемы, которые лично я использую слишком часто.
Напоследок в этом разделе сделаем до смешного простой GIF: 3 кадра синего, зелёного и красного цвета с 1-секундной задержкой. Запустив go run main.go, мы создадим файл rgb.gif, который будет зацикливать эти цвета.
package main
import (
"fmt"
"image"
"image/color"
"image/gif"
"os"
)
func main() {
var w, h int = 240, 240
fileName := "rgb.gif"
var palette = []color.Color{
color.RGBA{0x00, 0x00, 0xff, 0xff}, // Blue
color.RGBA{0x00, 0xff, 0x00, 0xff}, // Green
color.RGBA{0xff, 0x00, 0x00, 0xff}, // Red
}
var images []*image.Paletted
var delays []int
for frame := 0; frame < len(palette); frame++ {
img := image.NewPaletted(image.Rect(0, 0, w, h), palette)
paletteIndex := uint8(frame) // paletteIndex 0 is blue, 1 is green and 2 is red
for p := 0; p < 240*240; p++ {
img.Pix[p] = paletteIndex
}
images = append(images, img)
delays = append(delays, 100) // 1 second delay between frames
}
f, _ := os.OpenFile(fileName, os.O_WRONLY|os.O_CREATE, 0600)
defer f.Close()
gif.EncodeAll(f, &gif.GIF{
Image: images,
Delay: delays,
})
fmt.Printf("Created '%v'.\n", fileName)
}
PNG
Portable Network Graphic (PNG) был разработан как преемник GIF. В отличие от своего предшественника, PNG поддерживает цвета без палитры, то есть фактически хранит RGB или RGBA для каждого цвета. Но он также поддерживает оттенки серого и палитры размером 3 байта RGB или 4 байта RGBA.
Каждый файл PNG начинается с сигнатуры:
89 50 4E 47 0D 0A 1A 0AЗатем следует список чанков. Существуют различные типы чанков:
IHDR (заголовок изображения). Этот чанк должен идти первым и содержит важные метаданные изображения, такие как ширина, высота, битовая глубина, тип цвета и т. д.
IDAT (данные изображения): В этом чанке хранятся данные изображения, сжатые с помощью алгоритма Deflate (GZIP). Данные изображения могут быть разделены на несколько IDAT-чанков, особенно для больших изображений.
IEND (End Chunk). Этот чанк отмечает конец файла PNG.
Я не большой поклонник этих аббревиатур (IHDR, IDAT), для меня они звучат излишне вычурно.
Так или иначе, PNG использует известный алгоритм DEFLATE, применяемый в GZIP для сжатия данных изображения.
Фильтрация
Пиксели не всегда охотно поддаются сжатию. Они могут проявлять некоторое упрямство. Например, значения пикселей могут следовать определённому шаблону (2,4,6,8 и т. д.). Этот шаблон, к сожалению, не поддаётся сжатию LZ. Хоть мы и знаем, что существует повторяющееся поведение, которое управляет значениями пикселей, мы не можем просто использовать ссылки на предыдущие данные.
Решение? Преобразовать данные. Скажем, мы будем вычитать из каждого пикселя значение его соседа слева. В нашем примере мы получим (2,2,2,2,2 и т. д.). Это легко сжимается. Такая техника называется Sub Filter. Иногда закономерность проявляется по вертикали, а не по горизонтали. Например, пиксели в строке N - (12,18,44,89), а чуть ниже, в строке N+1, - (13,19,45,90). Это не так уж и маловероятно, потому что часто мы имеем градиент или плавные переходы цветов. Если мы применим фильтр Up Filter, то есть вычтем из каждого пикселя значение пикселя сверху, то получим аккуратный (1,1,1,1), что отлично поддаётся сжатию.
PNG применяет фильтры по строкам. Как выбрать фильтр? Идеального способа не существует, но используется такой эвристический подход: минимизируем сумму абсолютных разностей между пикселями оригинала и пикселями фильтра (вверх, до и т. д.). Почему? Если сумма абсолютных разностей минимальна, то вполне вероятно, что у нас много близких или одинаковых значений, которые, скорее всего, более сжимаемы, чем «разрозненные» значения. Я понимаю, что можно придумать контрпример: например, массив (100, 100, 100, 100, 100, 100, 100), сумма которого равна 600, более сжимаем, чем (1,2,3,4,5,6), сумма которого намного меньше. Но это эвристика, и, судя по всему, она показала хорошие эмпирические результаты. Существуют и другие методы. В libpng (канонической реализации PNG) есть следующий комментарий:
* The prediction method we use is to find which method provides the
* smallest value when summing the absolute values of the distances
* from zero, using anything >= 128 as negative numbers. This is known
* as the "minimum sum of absolute differences" heuristic. Other
* heuristics are the "weighted minimum sum of absolute differences"
* (experimental and can in theory improve compression), and the "zlib
* predictive" method (not implemented yet), which does test compressions
* of lines using different filter methods, and then chooses the
* (series of) filter(s) that give minimum compressed data size (VERY
* computationally expensive).
*
* GRR 980525: consider also
*
* (1) minimum sum of absolute differences from running average (i.e.,
* keep running sum of non-absolute differences & count of bytes)
* [track dispersion, too? restart average if dispersion too large?]
*
* (1b) minimum sum of absolute differences from sliding average, probably
* with window size <= deflate window (usually 32K)
*
* (2) minimum sum of squared differences from zero or running average
* (i.e., ~ root-mean-square approach)
*/Реализация в Golang также использует ту же эвристику, как мы увидим ниже.
Вот список всех фильтров, которые использует PNG:
None. Ничего не делает.
Sub. Каждый байт заменяется разницей между текущим и предыдущим пикселем (в той же строке).
Up. Каждый байт заменяется разницей между текущим пикселем и пикселем, расположенным непосредственно над ним.
Average. Каждый байт заменяется средним значением пикселя слева и пикселя сверху.
Paeth. Каждый байт заменяется разницей между текущим пикселем и лучшим значением из трех: слева, сверху или по диагонали вверх-влево.
Операции фильтрации выполняются на уровне байтов, и в результате на изображениях с малой глубиной (менее 8 бит на пиксель) по умолчанию используется фильтр NONE.
Перейдем к делу и рассмотрим реализацию фильтров в Go.
// Chooses the filter to use for encoding the current row, and applies it.
// The return value is the index of the filter and also of the row in cr that has had it applied.
func filter(cr *[nFilter][]byte, pr []byte, bpp int) int {
// We try all five filter types, and pick the one that minimizes the sum of absolute differences.
// This is the same heuristic that libpng uses, although the filters are attempted in order of
// estimated most likely to be minimal (ftUp, ftPaeth, ftNone, ftSub, ftAverage), rather than
// in their enumeration order (ftNone, ftSub, ftUp, ftAverage, ftPaeth).
cdat0 := cr[0][1:]
cdat1 := cr[1][1:]
cdat2 := cr[2][1:]
cdat3 := cr[3][1:]
cdat4 := cr[4][1:]
pdat := pr[1:]
n := len(cdat0)
// The up filter.
sum := 0
for i := 0; i < n; i++ {
cdat2[i] = cdat0[i] - pdat[i]
sum += abs8(cdat2[i])
}
best := sum
filter := ftUp
// The Paeth filter.
sum = 0
for i := 0; i < bpp; i++ {
cdat4[i] = cdat0[i] - pdat[i]
sum += abs8(cdat4[i])
}
for i := bpp; i < n; i++ {
cdat4[i] = cdat0[i] - paeth(cdat0[i-bpp], pdat[i], pdat[i-bpp])
sum += abs8(cdat4[i])
if sum >= best {
break
}
}
if sum < best {
best = sum
filter = ftPaeth
}
// The none filter.
sum = 0
for i := 0; i < n; i++ {
sum += abs8(cdat0[i])
if sum >= best {
break
}
}
if sum < best {
best = sum
filter = ftNone
}
// The sub filter.
sum = 0
for i := 0; i < bpp; i++ {
cdat1[i] = cdat0[i]
sum += abs8(cdat1[i])
}
for i := bpp; i < n; i++ {
cdat1[i] = cdat0[i] - cdat0[i-bpp]
sum += abs8(cdat1[i])
if sum >= best {
break
}
}
if sum < best {
best = sum
filter = ftSub
}
// The average filter.
sum = 0
for i := 0; i < bpp; i++ {
cdat3[i] = cdat0[i] - pdat[i]/2
sum += abs8(cdat3[i])
}
for i := bpp; i < n; i++ {
cdat3[i] = cdat0[i] - uint8((int(cdat0[i-bpp])+int(pdat[i]))/2)
sum += abs8(cdat3[i])
if sum >= best {
break
}
}
if sum < best {
filter = ftAverage
}
return filter
}Функция принимает аргументы cr *[nFilter][]byte, pr []byte, bpp int. cr — это массив массивов (я буду использовать массив и срез как взаимозаменяемые), он представляет текущий ряд, для которого мы хотим выбрать фильтр (возвращаемое значение — это индекс/тип фильтра).
Каждый результат фильтрации записывается внутри массива cr[filterNb]. Как сказано в комментарии, фильтры тестируются в порядке наиболее вероятных кандидатов на минимальную сумму разностей, это делается для того, чтобы иметь возможность прервать работу последующего фильтра, как только сумма превысит текущее лучшее значение. pr — предыдущий ряд. Первый байт массива байтов каждой строки содержит тип фильтра, поэтому pdat = pr[1:] — это данные предыдущей строки без типа фильтра. Давайте разберем фильтр up.
// The up filter.
sum := 0
for i := 0; i < n; i++ { // loop over the row pixels
cdat2[i] = cdat0[i] - pdat[i] // subsctract the previous row's pixel at the same position i.e. the pixel above
sum += abs8(cdat2[i]) // add the absolute difference to our sum which we are trying to minimize
}Как насчет субфильтра?
// The sub filter.
// bpp is bytes per pixel. For RGB, it's 3. For gray scale, it's 1.
sum = 0
for i := 0; i < bpp; i++ {
cdat1[i] = cdat0[i]
sum += abs8(cdat1[i])
}
for i := bpp; i < n; i++ {
cdat1[i] = cdat0[i] - cdat0[i-bpp] // subtract each byte within a pixel from corresponding byte in previous pixel
sum += abs8(cdat1[i])
if sum >= best { // break early if this is worse than previous filter
break
}
}bpp играет здесь решающую роль. Обратите внимание, что при вычитании cdat1[i] = cdat0[i] - cdat0[i - bpp] мы вычитаем пиксель на bpp позиций раньше текущего пикселя. В случае RGB это означает, что из текущего значения красного цвета вычитается красный предыдущего пикселя, из текущего зелёного — зелёный предыдущего и так далее.
Мы вычисляем сумму для каждого фильтра и берем min — это и будет наш выбранный фильтр, который, предположительно, обеспечит максимальное сжатие алгоритмом DEFLATE. Результат применения выбранного фильтра будет находиться в массиве cr[chosenFilter].
Кодирование
Рассмотрим метод Encode, используемый для кодирования изображений PNG.
// Encode writes the Image m to w in PNG format.
func (enc *Encoder) Encode(w io.Writer, m image.Image) error {
// Obviously, negative widths and heights are invalid. Furthermore, the PNG
// spec section 11.2.2 says that zero is invalid. Excessively large images are
// also rejected.
mw, mh := int64(m.Bounds().Dx()), int64(m.Bounds().Dy())
if mw <= 0 || mh <= 0 || mw >= 1<<32 || mh >= 1<<32 {
return FormatError("invalid image size: " + strconv.FormatInt(mw, 10) + "x" + strconv.FormatInt(mh, 10))
}
e := &encoder{}
//....
e.enc = enc
e.w = w
e.m = m
var pal color.Palette
// cbP8 encoding needs PalettedImage's ColorIndexAt method.
if _, ok := m.(image.PalettedImage); ok {
pal, _ = m.ColorModel().(color.Palette)
}
if pal != nil {
if len(pal) <= 2 {
e.cb = cbP1
} else if len(pal) <= 4 {
e.cb = cbP2
} else if len(pal) <= 16 {
e.cb = cbP4
} else {
e.cb = cbP8
}
} else {
switch m.ColorModel() {
case color.GrayModel:
e.cb = cbG8
case color.Gray16Model:
e.cb = cbG16
case color.RGBAModel, color.NRGBAModel, color.AlphaModel:
if opaque(m) {
e.cb = cbTC8
} else {
e.cb = cbTCA8
}
default:
if opaque(m) {
e.cb = cbTC16
} else {
e.cb = cbTCA16
}
}
}
_, e.err = io.WriteString(w, pngHeader)
e.writeIHDR()
if pal != nil {
e.writePLTEAndTRNS(pal)
}
e.writeIDATs()
e.writeIEND()
return e.err
}Многое предстоит распаковать. Весело! Одна из причин, по которой я люблю читать код, это комментарии вроде «Очевидно, что отрицательные значения ширины и высоты недействительны». Он просто красиво звучит.
Мы начинаем с проверки размеров наших изображений, затем инициализируем наш энкодер, который определяется как:
type encoder struct {
enc *Encoder
w io.Writer
m image.Image
cb int // a combination of color type and bit depth.
err error
header [8]byte
footer [4]byte
tmp [4 * 256]byte
cr [nFilter][]uint8 // stores the current row and possible filter
pr []uint8 // previous row
zw *zlib.Writer // used of compression
zwLevel int // compression level
bw *bufio.Writer
}Затем пытаемся преобразовать наше изображение в image.PalettedImage и извлечь из него Palette (которая является псевдонимом для []Color). Если это удаётся, значит, изображение палитровое, и мы определяем глубину цвета (количество бит) в зависимости от количества цветов в палитре. Если нет, то, основываясь на возвращаемом типе ColorModel, присваиваем наш cb. GrayModel, Gray16Model, RGBAModel, AlphaModel — всё это именно то, о чем говорят их названия.
Как только мы узнаем тип и глубину цвета, оставшийся код становится практически простым текстом.
_, e.err = io.WriteString(w, pngHeader) // write magic "\x89PNG\r\n\x1a\n"
e.writeIHDR() // write the actual header
if pal != nil {
e.writePLTEAndTRNS(pal) // write the palette, if there is one
}
e.writeIDATs() // the image data
e.writeIEND() // write the footer: `IEND`Вот функция writeIHDR, перед которой идут определения типов цвета:
// Color type, as per the PNG spec.
const (
ctGrayscale = 0
ctTrueColor = 2
ctPaletted = 3
ctGrayscaleAlpha = 4
ctTrueColorAlpha = 6
)
func (e *encoder) writeIHDR() {
b := e.m.Bounds()
// Write image dimensions in BigEndian (most significant byte at the smallest memory address)
binary.BigEndian.PutUint32(e.tmp[0:4], uint32(b.Dx())) // image width
binary.BigEndian.PutUint32(e.tmp[4:8], uint32(b.Dy())) // image height
// Set bit depth and color type.
switch e.cb {
case cbG8:
e.tmp[8] = 8
e.tmp[9] = ctGrayscale
case cbTC8:
e.tmp[8] = 8
e.tmp[9] = ctTrueColor
case cbP8:
e.tmp[8] = 8
e.tmp[9] = ctPaletted
case cbP4:
e.tmp[8] = 4
e.tmp[9] = ctPaletted
case cbP2:
e.tmp[8] = 2
e.tmp[9] = ctPaletted
case cbP1:
e.tmp[8] = 1 // 1 bit per Pixel !!!!
e.tmp[9] = ctPaletted
case cbTCA8:
e.tmp[8] = 8
e.tmp[9] = ctTrueColorAlpha
case cbG16:
e.tmp[8] = 16
e.tmp[9] = ctGrayscale
case cbTC16:
e.tmp[8] = 16
e.tmp[9] = ctTrueColor
case cbTCA16:
e.tmp[8] = 16
e.tmp[9] = ctTrueColorAlpha
}
e.tmp[10] = 0 // default compression method
e.tmp[11] = 0 // default filter method
e.tmp[12] = 0 // non-interlaced
e.writeChunk(e.tmp[:13], "IHDR")
}
Мы подготавливаем массив заголовка размером 13 байт и записываем его как блок IHDR с помощью функции writeChunk:
func (e *encoder) writeChunk(b []byte, name string) {
if e.err != nil {
return
}
// 4 Gib max chunk size
n := uint32(len(b))
if int(n) != len(b) {
e.err = UnsupportedError(name + " chunk is too large: " + strconv.Itoa(len(b)))
return
}
// add the chunk length
binary.BigEndian.PutUint32(e.header[:4], n)
// chunk name
e.header[4] = name[0]
e.header[5] = name[1]
e.header[6] = name[2]
e.header[7] = name[3]
crc := crc32.NewIEEE()
// CRC check for the name + actual chunk data
crc.Write(e.header[4:8])
crc.Write(b)
binary.BigEndian.PutUint32(e.footer[:4], crc.Sum32())
// write header (length + name)
_, e.err = e.w.Write(e.header[:8])
if e.err != nil {
return
}
// actual data
_, e.err = e.w.Write(b)
if e.err != nil {
return
}
// CRC
_, e.err = e.w.Write(e.footer[:4])
}Я добавил комментарии, но код довольно прост. Он записывает длину и имя чанка, затем сами данные, а в конце добавляет контрольную сумму (CRC).
Если в нашей цветовой схеме есть палитра, мы пишем чанк PLTE, используя:
func (e *encoder) writePLTEAndTRNS(p color.Palette) {
if len(p) < 1 || len(p) > 256 {
e.err = FormatError("bad palette length: " + strconv.Itoa(len(p)))
return
}
last := -1
for i, c := range p {
c1 := color.NRGBAModel.Convert(c).(color.NRGBA)
e.tmp[3*i+0] = c1.R
e.tmp[3*i+1] = c1.G
e.tmp[3*i+2] = c1.B
if c1.A != 0xff {
last = i
}
e.tmp[3*256+i] = c1.A
}
e.writeChunk(e.tmp[:3*len(p)], "PLTE")
if last != -1 {
e.writeChunk(e.tmp[3*256:3*256+1+last], "tRNS")
}
}Чанк PLTE всегда хранит цвета палитры с использованием 3 байтов, независимо от типа цвета, то есть даже цвета в градациях серого (1 байт) используют 3 байта. Чанк tRNS хранит информацию о прозрачности, причем альфа-байт для каждой цветовой палитры располагается после байтов цвета палитры.
И наконец, собственно данные изображения, записанные с помощью writeIDATs:
// Write the actual image data to one or more IDAT chunks.
func (e *encoder) writeIDATs() {
if e.err != nil {
return
}
if e.bw == nil {
e.bw = bufio.NewWriterSize(e, 1<<15)
} else {
e.bw.Reset(e)
}
e.err = e.writeImage(e.bw, e.m, e.cb, levelToZlib(e.enc.CompressionLevel))
if e.err != nil {
return
}
e.err = e.bw.Flush()
}Его суть заключается в цикле внутри writeImage:
for y := b.Min.Y; y < b.Max.Y; y++ {
// Convert from colors to bytes.
i := 1
switch cb {
case cbG8:
if gray != nil {
offset := (y - b.Min.Y) * gray.Stride
copy(cr[0][1:], gray.Pix[offset:offset+b.Dx()])
} else {
for x := b.Min.X; x < b.Max.X; x++ {
c := color.GrayModel.Convert(m.At(x, y)).(color.Gray)
cr[0][i] = c.Y
i++
}
}
// omitted ...
case cbTC8:
// We have previously verified that the alpha value is fully opaque.
// omitted ...
for x := b.Min.X; x < b.Max.X; x++ {
r, g, b, _ := m.At(x, y).RGBA()
cr0[i+0] = uint8(r >> 8)
cr0[i+1] = uint8(g >> 8)
cr0[i+2] = uint8(b >> 8)
i += 3
}
case cbP8:
// omitted ...
pi := m.(image.PalettedImage)
for x := b.Min.X; x < b.Max.X; x++ {
cr[0][i] = pi.ColorIndexAt(x, y)
i += 1
}
// omitted ...
}
// Apply the filter.
// Skip filter for NoCompression and paletted images (cbP8) as
// "filters are rarely useful on palette images" and will result
// in larger files (see http://www.libpng.org/pub/png/book/chapter09.html).
f := ftNone
if level != zlib.NoCompression && cb != cbP8 && cb != cbP4 && cb != cbP2 && cb != cbP1 {
// Since we skip paletted images we don't have to worry about
// bitsPerPixel not being a multiple of 8
bpp := bitsPerPixel / 8
f = filter(&cr, pr, bpp)
}
// Write the compressed bytes.
if _, err := e.zw.Write(cr[f]); err != nil {
return err
}
// The current row for y is the previous row for y+1.
pr, cr[0] = cr[0], pr
}Я оставил только случаи для оттенков серого, RGB (истинного цвета) и 256-цветной палитры cbP8. Как вы можете видеть, мы перебираем строки изображения: y := b.Min.Y; y < b.Max.Y; y++. Для каждой строки, если это градации серого (cbG8), мы копируем по 1 байту для каждого цвета. Если это RGB, то копируем 3 байта. Для палитры мы просто записываем индекс палитры.
Затем, если сжатие включено (level != zlib.NoCompression) — нет необходимости фильтровать, если мы не будем сжимать, — и мы не используем палитры, мы выбираем фильтр для данных изображения с помощью функции filter , которую изучили ранее. Затем передаем отфильтрованные (или неотфильтрованные) байты в LZ-writer, и наши сжатые данные изображения готовы к записи.
Наконец, добавляем последний чанк с помощью функции writeIEND, короткой и приятной:
func (e *encoder) writeIEND() { e.writeChunk(nil, "IEND") }
И в этом вся суть PNG!
Изображения с потерями
JPEG
JPEG, Joint Photographic Experts Group (что за название!), чрезвычайно распространён в Интернете. Каждый, кто работал с изображениями на компьютере, наверняка сталкивался с PNG либо с JPEG. Этот формат позволяет достичь высокой степени сжатия, уменьшая исходное изображение до +90% от его размера при сохранении приемлемого качества. Степень сжатия варьируется от 5:1 до 50:1. Качество настраивается, и мы можем выбрать компромисс между коэффициентом сжатия и качеством изображения.
JPEG — это волшебный инженерный подвиг, состоящий из множества аспектов. Попробуем исследовать некоторые из его основных идей и посмотреть на код. Далее поговорим о цветовой субдискретизации, DCT (дискретное косинусное преобразование) и квантовании.
YCbCr и цветовая субдискретизация
Этот шаг основан на следующей идее: человеческий глаз более чувствителен к яркости (luma) и зелёному цвету, чем к красному и синему (chroma).
Если мы преобразуем наш цвет RGB в эквивалент, который изолирует яркость от красных и синих компонентов, мы сможем сохранить биты luma (к которым наш глаз более чувствителен), одновременно сжимая (субдискретизируя) chroma (красный и синий), к которому мы менее чувствительны.
Такое преобразование называется YCbCr (Y: Luma, Cb: Chroma Blue, Cr: Chroma Red); оно отделяет яркость (Y) от цветовой информации (Cb и Cr).
Учитывая, что наши глаза более чувствительны к яркости, чем к цветам, мы можем сжать исходное изображение, выбрав меньше компонентов CbCr и оставив все компоненты яркости. Это называется цветовой субдискретизацией, т. е. мы берем меньше информации о цветах. Для каждого набора из 4 пикселей мы делаем субдискретизацию, заменяя их одним пикселем (например, усредняя или беря левый верхний пиксель). Заменяя 4 пикселя на 1 для Cb и Cr, мы уменьшаем исходный размер на 50 %.
JPEG работает с блоками 8x8 пикселей. Вот функция, которую использует стандартная библиотека Go для преобразования в YCbCr:
const blockSize = 64
type block [blockSize]int32 // block holds 64 (8x8) pixels
// toYCbCr converts the 8x8 region of m whose top-left corner is p to its
// YCbCr values.
func toYCbCr(m image.Image, p image.Point, yBlock, cbBlock, crBlock *block) {
b := m.Bounds()
xmax := b.Max.X - 1
ymax := b.Max.Y - 1
for j := 0; j < 8; j++ { // 8x8 pixel blocks
for i := 0; i < 8; i++ {
r, g, b, _ := m.At(min(p.X+i, xmax), min(p.Y+j, ymax)).RGBA()
yy, cb, cr := color.RGBToYCbCr(uint8(r>>8), uint8(g>>8), uint8(b>>8))
yBlock[8*j+i] = int32(yy)
cbBlock[8*j+i] = int32(cb)
crBlock[8*j+i] = int32(cr)
}
}
}Волшебное преобразование происходит внутри RGBToYCbCr:
// RGBToYCbCr converts an RGB triple to a Y'CbCr triple.
func RGBToYCbCr(r, g, b uint8) (uint8, uint8, uint8) {
// The JFIF specification says:
// Y' = 0.2990*R + 0.5870*G + 0.1140*B
// Cb = -0.1687*R - 0.3313*G + 0.5000*B + 128
// Cr = 0.5000*R - 0.4187*G - 0.0813*B + 128
// https://www.w3.org/Graphics/JPEG/jfif3.pdf says Y but means Y'.
yy := (19595*r1 + 38470*g1 + 7471*b1 + 1<<15) >> 16
// omitted ...
cb := -11056*r1 - 21712*g1 + 32768*b1 + 257<<15
// omitted ...
cr := 32768*r1 - 27440*g1 - 5328*b1 + 257<<15
// omitted ...
return uint8(yy), uint8(cb), uint8(cr)
}Это просто линейное преобразование. Мы замечаем, что Y в основном зелёный, но в нём также есть немного красного и синего. Как мы уже говорили, это luma, и наш глаз наиболее чувствителен к ней; она представляет собой яркость изображения. Cb и Cr можно интерпретировать как цветовые отличия синего и красного относительно яркости.
В этой потрясающей лекции (я обожаю весь цикл лекций, а профессор просто восхитителен) показано множество примеров и того, как изменение различных значений RGB и YCbCr может повлиять на итоговое изображение. Удивительно, как уменьшение глубины (меньшее количество битов/информации) для Cb и Cr имеет гораздо меньший эффект, чем уменьшение синего или красного в пространстве RGB.
Это пересечение нейробиологии и инженерии.
Один из интересных выводов из этого — насколько мир оптимизирован под биологию человека. Это похоже на то, как очки создаются для человеческого лица, ушей и глаз. Это также заставляет меня думать, что роботов лучше всего делать гуманоидными, чтобы они были наиболее эффективными, поскольку наш мир спроектирован для нас.
Ладно, хватит философствовать, как на самом деле происходит цветовая субдискретизация?
Вот цикл, который записывает данные изображения в JPEG:
cb, cr [4]block
// omitted
for y := bounds.Min.Y; y < bounds.Max.Y; y += 16 {
for x := bounds.Min.X; x < bounds.Max.X; x += 16 {
for i := 0; i < 4; i++ {
xOff := (i & 1) * 8
yOff := (i & 2) * 4
p := image.Pt(x+xOff, y+yOff)
// omitted ..
toYCbCr(m, p, &b, &cb[i], &cr[i])
prevDCY = e.writeBlock(&b, 0, prevDCY)
}
scale(&b, &cb)
prevDCCb = e.writeBlock(&b, 1, prevDCCb)
scale(&b, &cr)
prevDCCr = e.writeBlock(&b, 1, prevDCCr)
}
}cb и cr содержат по 4 блока пикселей Cb и Cr размером 8x8. Мы проходим по области 16x16 из исходного изображения, которая состоит из 4 блоков 8x8. Эти блоки размещаются в переменных cb и cr.
В самом внутреннем цикле есть довольно интересный трюк. Обратите внимание на xOff := (i & 1) * 8 и yOff := (i & 2) * 4. Их значения для i = [0,1,2,3] будут: (xOff, yOff) = [(0,0), (8,0), (0,8), (8,8)]. Это позволяет двигаться по блоку 16x16: сначала сдвигаемся слева направо по верхнему ряду, затем смещаемся на 8 (переход к следующему блоку 8x8 вправо), а затем переходим к следующей строке и выполняем то же самое.
Таким образом, мы имеем значения Cb и Cr в 4 блоках 8x8. Субдискретизация происходит в функции scale:
// scale scales the 16x16 region represented by the 4 src blocks to the 8x8
// dst block.
func scale(dst *block, src *[4]block) {
for i := 0; i < 4; i++ {
dstOff := (i&2)<<4 | (i&1)<<2
for y := 0; y < 4; y++ {
for x := 0; x < 4; x++ {
j := 16*y + 2*x
sum := src[i][j] + src[i][j+1] + src[i][j+8] + src[i][j+9]
dst[8*y+x+dstOff] = (sum + 2) >> 2
}
}
}
}Это нечто! Во-первых, обратите внимание, что мы берем исходный block размером [4] и преобразуем его в block dst. Напоминаю, что block — это просто массив размером 64 (8x8).
i представляет собой верхний левый, верхний правый, нижний левый и нижний правый блоки 8x8 в области 16x16 входных данных. Каждый из блоков 8x8 будет отображаться в блок 4x4 (уменьшение на 1/4). Каждый пиксель блока 4x4 обозначается x и y. Как вычисляется значение каждого пикселя?
j := 16*y + 2*x // top left point of the 4 pixel square
sum := src[i][j] + src[i][j+1] + src[i][j+8] + src[i][j+9] // sum of pixel square values starting at j
dst[8*y+x+dstOff] = (sum + 2) >> 2 // divide by 4 (>>2) to get the average but add 2 before to round up instead of downЭто просто усреднение значений 4 пикселей с помощью 2-битного сдвига вправо и округления в большую сторону путем добавления 2 перед сдвигом.
Значение dstOff интригует. Для i=[0,1,2,3] мы получаем dstOff=[0,4,32,36]. Что они означают?
Давайте вспомним, что каждый i представляет собой 4x4 блок внутри нашей целевой 8x8 области, которая представляет собой уменьшенную версию 16x16. Если представить матрицу 8x8, то левый верхний блок начинается в точке (0,0). Правый верхний блок начинается в точке (4,0). Левый нижний блок начинается в точке (4,0), а правый нижний — в точке (4,4). Если мы переведем их в одномерное представление с помощью x + 8y, то получим:
0 + 0 * 8 = 0
4 + 0 * 8 = 4
0 + 4 * 8 = 32
4 + 4 * 8 = 36Который представляет собой начало каждого блока 4x4. Это вычисление причудливым образом производится с помощью dstOff := (i&2)<<4 | (i&1)<<2.
(i&2)<<4 даст 32 для значений, у которых второй бит равен единице, то есть для 2 (10) и 3 (11) (вторая строка), а (i&1)<<2 даст 4 для значений 1 (01) и 3 (11). Настоящая бинарная магия!
Если вы задаётесь вопросом, зачем делать всё это и получать 4 блока из области 16x16 вместо того, чтобы обрабатывать их по отдельности, то причина в том, что в итоге мы хотим получить блок 8x8, аналогичный компоненту Y (luma). Это гарантирует, что следующий шаг JPEG, а именно дискретное косинусное преобразование (DCT), будет работать с теми же размерами.
В общем, функция scale — это просто усреднение 4 пикселей в 1, что позволяет уменьшить 4 блока 8x8 до одного.
Прямое косинусное преобразование
Итак, мы достигли приличного 50-процентного сжатия, используя YCbCr. Однако всё ещё далеки от раскрытия всего потенциала JPEG.
Следующий шаг в процессе — дискретное косинусное преобразование (DCT). Вкратце, DCT выделяет и идентифицирует части изображения, которые можно обрезать или отбросить без существенного ухудшения качества.
Мы можем представить себе изображение как функцию. Каждый пиксель на изображении соответствует позиции (x, y) со значением, указывающим на интенсивность его цвета. Мы можем представить это как F(x, y) = pixelValue. Если мы хотим обходить изображение слева направо и сверху вниз, мы можем упростить задачу, используя одну переменную x', где x' = x + len(row) * y (по сути, это то, что делает реализация Golang со своими 64-битными блоками беззнаковых целых чисел).
Другими словами, изображение — это функция. И что с того? — спросите вы. А что, если есть способ аппроксимировать эту функцию с помощью набора компонентов разной важности и сэкономить место, отбросив наименее важные из них?
Представьте, что у нас есть набор кортежей типа (1, 2), (2, 4), ..., (10, 20), (1000, 2000). Мы можем хранить 2 * 1000 чисел, а можем понять, что эти отношения следуют простой схеме: f(x) = 2x. Вместо того чтобы хранить все точки, мы могли бы хранить только формулу, что дало бы значительную экономию места.
DCT позволяет представить функцию изображения в виде суммы известных косинусных функций возрастающей частоты. Математически доказано, что это возможно.
Что действительно поразительно в этом представлении, так это то, что человеческий глаз (биология снова наносит удар) менее чувствителен к высокочастотным деталям, чем к низкочастотным. Еще интереснее то, что высокочастотные компоненты соответствуют резким изменениям на изображении, а на практике изображения в основном состоят из низкочастотных компонентов. Другими словами, цвета в изображениях обычно не меняются резко.
Говоря иначе, любой блок размером 8x8 пикселей можно выразить как взвешенную сумму следующих 64 блоков:
Давайте подумаем об этом ещё раз. Любой блок 8x8 может быть выражен как комбинация этих 64 блоков. И чем больше мы приближаемся к правому нижнему углу, тем выше частота соответствующего компонента — и тем менее различим он для человеческого глаза.
Поэтому, если мы представим наш блок 8x8 только несколькими весами этих низкочастотных блоков DCT — скажем, сохраним всего 16 или 32 (вместо 64 пикселей), мы добьемся большой экономии места без заметной потери качества.
Чтобы мой плагин Mathjax не пылился без дела а мои рассуждения были подкреплены наукой, давайте посмотрим на фактическую формулу:
![X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(n+{\tfrac {1}{2}}\right)k\,\right]\qquad {\text{ for }}~k=0,\ \dots \ N-1~](https://habrastorage.org/getpro/habr/formulas/b/bf/bf3/bf38f5a536aeb76b2b417069a2a8d9ba.svg)
Так мы вычисляем коэффициент K-й косинусной функции.
Будет удобно представить себе это уравнение как скалярное произведение между нашими N значениями пикселей и N выборками косинусной функции:
![\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(n+{\tfrac {1}{2}}\right)k\,\right]](https://habrastorage.org/getpro/habr/upload_files/ec5/c0e/eeb/ec5c0eeebf57605c976be679d83baf05.svg)
частота которых увеличивается с ростом k.
Коэффициент представляет собой степень сходства (т. е. скалярное произведение) между нашими значениями пикселей и соответствующей косинусной функцией.
Для наших целей мы работаем с одним из 64 блоков (обратите внимание, что приведённая выше косинусная функция является одномерной, а блок — двумерным, поэтому данное объяснение применимо только к одному из измерений).
Например, если у нас есть сетка входных пикселей 8x8, которая идеально совпадает с одним из косинусных шаблонов, то соответствующий коэффициент будет равен 1, а коэффициенты для других блоков будут равны 0. Это происходит потому, что только этого блока достаточно для представления входных данных.
Еще раз: взвешенная комбинация низкочастотных блоков (ближе к левому верхнему углу) с большей вероятностью сможет хорошо представить исходный блок 8x8 пикселей. Поэтому, когда мы представляем наше изображение в виде 64 коэффициентов, мы можем отбросить высокочастотные не сильно теряя в качестве.
Итак, теперь мы готовы к двумерной формуле:
![X_{k,l} = \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x_{n,m} \cos\left[\frac{\pi}{N} \left(n + \frac{1}{2}\right) k \right] \cos\left[\frac{\pi}{N} \left(m + \frac{1}{2}\right) l \right]](https://habrastorage.org/getpro/habr/formulas/e/e4/e45/e459c803c13c363f7bd03e9d332e9119.svg)
Переведя в код, получим следующее:
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
temp := 0.0
for x := 0; x < N; x++ {
for y := 0; y < N; y++ {
temp += Cosines[x][i] * Cosines[y][j] * Pixel[x][y]
}
}
temp *= math.Sqrt(2 * float64(N)) * Coefficient[i][j]
DCT[i][j] = int(math.Round(temp))
}
}Массив cosines уже содержит предварительно вычисленные значения. Мы просто итерируемся по пикселям и вычисляем выходные коэффициенты, которые зависят от значений пикселей и косинусов.
Однако, как видно, уровень вложенности 4 для циклов не так уж хорош для производительности. В практических реализациях используется оптимизированная версия, известная как Fast DCT, которая более эффективна с вычислительной точки зрения.
Квантование
Вместо того чтобы сразу удалять высокочастотные коэффициенты, мы уменьшаем их точность, используя меньшее количество бит для их хранения. Этот процесс называется квантованием. В результате важные низкочастотные коэффициенты сохраняются с большей точностью, а высокочастотные коэффициенты квантуются для экономии места.
Как это происходит на практике?
Результаты DCT делятся на Q таблицу, уменьшая количество необходимых бит. Например, если результат DCT равен 31, а значение Q - 2, Round(31/Q) дает 16. Если Q равно 4, Round(31/Q) дает 8. Чтобы восстановить исходные значения, мы умножаем квантованный результат на Q, хотя восстановленное значение будет приблизительным.
Стандарт JPEG определяет таблицу для квантования каждого из 64 коэффициентов, полученных после применения DCT к блоку 8x8 пикселей.
Поскольку компоненты цветности (Yb и Yr) оказывают меньшее влияние на наше восприятие, их таблицы квантования более агрессивны, чем таблицы, используемые для яркости (Y). Вот эти таблицы:
var unscaledQuant = [nQuantIndex][blockSize]byte{
// Luminance.
{
16, 11, 12, 14, 12, 10, 16, 14,
13, 14, 18, 17, 16, 19, 24, 40,
26, 24, 22, 22, 24, 49, 35, 37,
29, 40, 58, 51, 61, 60, 57, 51,
56, 55, 64, 72, 92, 78, 64, 68,
87, 69, 55, 56, 80, 109, 81, 87,
95, 98, 103, 104, 103, 62, 77, 113,
121, 112, 100, 120, 92, 101, 103, 99,
},
// Chrominance.
{
17, 18, 18, 24, 21, 24, 47, 26,
26, 47, 99, 66, 56, 66, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
},
}Можно заметить, что низкие частоты (вверху слева) делятся на меньшие значения, чтобы сохранить более высокую точность, в то время как высокие частоты (внизу справа) делятся на большие значения из таблицы Q, что приводит к очень маленьким результатам (близким к 0 или 1). Эти малые значения являются идеальными кандидатами для методов сжатия без потерь, таких как LZ77 или кодирование длин серий.
Чтобы добиться максимальной эффективности сжатия, блок обходится в зигзагообразном порядке. Как видно из таблицы квантования, увеличение значений Q (и, соответственно, результата квантования) не происходит по типичной схеме слева направо, сверху вниз. Напротив, оно происходит от левого верхнего края к правому нижнему.
Это означает, что значения, которые, скорее всего, похожи и, следовательно, более сжимаемы, следуют друг за другом по диагонали. Зигзагообразный обход эффективно группирует эти похожие значения, оптимизируя сжатие.
Зигзагообразный обход выполняется довольно хитро: используется массив из 64 элементов, который сопоставляет каждый обычный индекс с его зигзагообразным порядком.
// unzig maps from the zig-zag ordering to the natural ordering. For example,
// unzig[3] is the column and row of the fourth element in zig-zag order. The
// value is 16, which means first column (16%8 == 0) and third row (16/8 == 2).
var unzig = [blockSize]int{
0, 1, 8, 16, 9, 2, 3, 10,
17, 24, 32, 25, 18, 11, 4, 5,
12, 19, 26, 33, 40, 48, 41, 34,
27, 20, 13, 6, 7, 14, 21, 28,
35, 42, 49, 56, 57, 50, 43, 36,
29, 22, 15, 23, 30, 37, 44, 51,
58, 59, 52, 45, 38, 31, 39, 46,
53, 60, 61, 54, 47, 55, 62, 63,
}
Если собрать все части вместе, получится, что основной цикл JPEG — это:
// writeBlock writes a block of pixel data using the given quantization table,
// returning the post-quantized DC value of the DCT-transformed block. b is in
// natural (not zig-zag) order.
func (e *encoder) writeBlock(b *block, q quantIndex, prevDC int32) int32 {
fdct(b) // apply DCT
// ...
for zig := 1; zig < blockSize; zig++ {
ac := div(b[unzig[zig]], 8*int32(e.quant[q][zig])) // divide zigzag DCT result by quantization number
if ac == 0 {
// quantization result is 0, increase RLE
runLength++
} else {
// ...
// write the current RLE sequence
e.emitHuffRLE(h, runLength, ac)
runLength = 0
}
}
//...
}
Мы опустили довольно много деталей, но всё же можем видеть, как применяются различные идеи, которые мы рассмотрели.
JPEG — настоящая сокровищница восхитительных инженерных решений, и то, что мы здесь обсудили, — лишь верхушка айсберга. Но я надеюсь, что это было познавательно и увлекательно.
На этом пока все. Ценю, что вы присоединились ко мне в этом путешествии.
Спасибо!
