3.8.3. Кодер

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

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

Первый шаг при определении контекста заключается в вычислении значений градиентов

, , .

Если все эти величины равны нулю (или в моде почти без потерь их абсолютные значения не превосходят порога NEAR), то кодер переходит в серийную моду и ищет наибольшую длину серии пикселов, совпадающих с . На шаге 2 кодер сравнивает три градиента  с некоторыми параметрами и вычисляет зонные числа  по некоторым правилам (эти правила здесь не обсуждаются). Каждое зонное число  может принимать одно из 9 целых значений в интервале , поэтому имеется всего  троек зонных чисел. На третьем шаге используются абсолютные значения произведений зонных чисел  (всего разных троек будет 365, так как одна из 729 величин равна нулю) для вычисления числа  из интервала . Детали этих вычислений не предписываются стандартом JPEG-LS, и кодер может делать это по любому правилу. Число  становится контекстом текущего пиксела . Используются индексные массивы  и  из рис. 3.65.

После установления контекста , кодер прогнозирует пиксел  за два шага. На первом шаге вычисляется прогноз  с помощью правила края, как показано на рис. 3.62. На втором шаге производится корректировка прогноза (см. рис. 3.63) с помощью числа SIGN (зависящего от трех зонных чисел ), корректирующих величин  (выводимых из систематических смещений, и здесь не обсуждаемых) и параметра MAXVAL.

Рис. 3.62. Обнаружение угла.

Рис. 3.63. Корректировка прогноза.

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

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

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

.

При этом используется параметр NEAR, однако имеются некоторые детали, которые здесь не приводятся. Основной шаг реконструкции состоит в нахождении

.

Ошибка прогноза (после возможного квантования) претерпевает сокращение области (здесь эта процедура опущена). Теперь она готова для главного этапа кодирования.

Коды Голомба были введены в § 3.8.1, где основной параметр был обозначен через . В JPEG-LS этот параметр обозначается . Если число  уже выбрано, то код Голомба неотрицательного целого числа  состоит из двух частей: унарного кода целой части числа  и двоичного представления . Этот код является идеальным для целых чисел, имеющих геометрическое распределение (то есть, когда вероятность числа  равна , ). Для каждого геометрического распределения найдется такое число , что код Голомба, построенный по , имеет наименьшую возможную среднюю длину. Простейший случай, когда  равно степени 2 , приводит к простым операциям кодирования/декодирования. Код числа  состоит в этом случае из  младших разрядов числа , перед которыми стоит унарный код числа, составленного из остальных старших разрядов числа . Этот специальный код Голомба обозначается через .

Для примера вычислим код  числа . Поскольку  , то . Начнем с двух младших разрядов, , числа . Они равны 3, что то же самое, что  . Оставшиеся старшие разряды,  дадут число 4, которое равно целой части  . Унарный код 4 равен 00001, значит код  числа  равен 00001|11.

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

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

                   (3.18)

Это отображение перемежает отрицательные и положительные величины в виде последовательности

.

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

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

for (k=0; (N[Q]<<k)<A[Q]; k++),

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

Табл. 3.64. Ошибки прогнозов, отображения и коды .

После нахождения числа , ошибка прогноза Errval преобразуется с помощью уравнения (3.18) в число MErrval, которое кодируется с помощью кода . Число  является параметром. Обновление массивов  и  (вместе со вспомогательным массивом ) показано на рис. 3.65 (параметр RESET контролируется пользователем).

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

.

Серия не должна выходить за пределы текущей строки. Длина серии кодируется (сам пиксел кодировать не нужно, поскольку он равен ), и если конец серии находится раньше конца строки, то после ее закодированной длины будет сразу записан код следующего пиксела (который прерывает серию). Две основные задачи кодера в этой моде состоят (1) в отслеживании серии и кодировании ее длины; (2) в кодировании пиксела, прервавшего серию. Отслеживание серии показано на рис. 3.66. Кодирование серий приведено на рис. 3.67 (для сегментов серий длины ) и на рис. 3.68 (для сегментов серий длины меньше, чем ). Рассмотрим некоторые детали.

Рис. 3.65. Обновление массивов ,  и .

 Рис. 3.66. Отслеживание серий.

Кодер использует таблицу , состоящую из 32 записей, обозначаемых .  инициализируется величинами

0, 0, 0, 0, 1, 1, 1,1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15.

Для каждого значения  обозначим . Числа  (их всего 32) называются порядком кода. Первые 4 величины  имеют . Для второй четверки , а для следующей четверки . Для последнего числа . Кодер выполняет процедуру, указанную на рис. 3.66, для нахождения длины серии, которая сохраняется в переменной . Затем эта переменная кодируется разбиением на слагаемые, величины которых равны последовательным числам . Например, если , то его представляют в виде  с помощью первых пяти чисел . Оно кодируется с помощью 5 бит. Запись производится инструкцией AppendToBitfile(1,1) (рис. 3.67). Каждый раз, когда пишется 1, соответствующая величина  вычитается из . Если  было равно в начале 6, то она последовательно уменьшается до 5, 4, 3, 2 и 0.

Рис. 3.67. Кодирование серий (I).

Рис. 3.68. Кодирование серий (II).

Может конечно случиться, что длина серии не равна целой сумме чисел  . Например, . В этом случае в качестве кода записывается пять битов 1, за которыми следует префиксный бит и остаток от  (в нашем примере это 1), который запишется в файл в виде числа из  бит (текущее значение  из нашего примера равно 2). Эта последняя операция выполняется вызовом процедуры AppendToBitfile (RUNcnt, J[RUNindex] ) на рис. 3.68. Префиксным битом служит 0, если серия прерывается в строке другим пикселом. Если серия идет до конца строки, то префиксный бит равен 1.

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

Нет ничего хуже точного образа размытой концепции.
— Ансель Адамс