Шум для снижения ошибки квантования

Введение

Шум, снижающий ошибку квантования.

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

Этимология

Термин "дитер" был опубликован в книгах по аналоговым вычислениям и гидравлически управляемым орудиям вскоре после Второй мировой войны. Хотя он и не использовал термин "дитер", концепция дитеринга для уменьшения артефактов квантования была впервые применена Лоуренсом Г. Робертсом в его магистерской диссертации 1961 года и статье 1962 года. К 1964 году "дитер" использовался в современном смысле, описанном в этой статье. Эта техника применялась как минимум с 1915 года, хотя и не под названием "дитер".

В цифровой обработке и анализе формы волны

Дитер используется во многих различных областях, где применяется цифровая обработка и анализ. К этим областям относятся системы цифровой обработки сигналов, такие как цифровая аудио-, видео- и фототехника, сейсмология, радиолокация и системы прогнозирования погоды. Квантование неизбежно вносит ошибку. Если эта ошибка коррелирует с сигналом, результат может быть циклическим или предсказуемым. В некоторых областях, особенно там, где восприятие чувствительно к подобным артефактам, циклические ошибки приводят к нежелательным искажениям. В таких случаях добавление дитера преобразует ошибку в случайный шум. Область аудио является ярким примером этого. Человеческое ухо работает подобно преобразованию Фурье, выделяя отдельные частоты. Поэтому ухо очень чувствительно к искажениям или добавлению новых частот, но гораздо менее чувствительно к случайному шуму на всех частотах, как это происходит в дитерированном сигнале.

Цифровая аудио

В аналоговой системе сигнал непрерывен, но в цифровой системе PCM амплитуда сигнала на выходе из цифровой системы ограничена одним из набора фиксированных значений или чисел. Этот процесс называется квантованием. Каждое кодированное значение представляет собой дискретный шаг. Если сигнал квантуется без использования дитера, возникает искажение квантования, связанное с исходным входным сигналом. Чтобы предотвратить это, к сигналу добавляют дитер – процесс, который математически полностью устраняет гармоники или другие крайне нежелательные искажения, заменяя их постоянным, фиксированным уровнем шума. Окончательная версия аудио, записываемая на компакт-диск, содержит только 16 бит на сэмпл, но в процессе производства обычно используется большее количество бит для представления сэмпла, которое затем необходимо уменьшить до 16 бит для создания CD. Существует несколько способов это сделать. Например, можно просто отбросить лишние биты – это называется усечением. Также можно округлить лишние биты до ближайшего значения. Однако каждый из этих методов приводит к предсказуемым и определяемым ошибкам в результате. Использование дитера заменяет эти ошибки постоянным, фиксированным уровнем шума.

Использование

Дитер добавляется перед любым процессом квантования или переквантования, чтобы декоррелировать шум квантования от входного сигнала и предотвратить нелинейное поведение (искажения). Квантование с меньшей разрядностью требует большего количества дитера. Результат процесса всё равно содержит искажения, но эти искажения носят случайный характер, поэтому результирующий шум фактически некоррелирован с исходным сигналом. В основополагающей статье, опубликованной в журнале AES, Липшиц и Вандеркой указали, что различные типы шума с разными функциями плотности вероятности (PDF) по-разному ведут себя при использовании в качестве дитер-сигналов. Человеческий глаз воспринимает диффузию как смесь цветов, составляющих её (см. цветовое зрение). Дитерированные изображения, особенно использующие палитры с относительно небольшим количеством цветов, часто можно узнать по характерной зернистости или крапчатости. Дитеринг вносит в изображение шум или структуру, и часто эта структура заметна. В таких случаях было показано, что дитер, генерируемый синим шумом, наименее заметен и не отвлекает внимание. Методы диффузии ошибок были одними из первых способов генерации дитер-паттернов на основе синего шума. Однако другие методы, такие как упорядоченный дитеринг, также могут генерировать дитеринг синего шума, не склонный к вырождению в области с артефактами.

Примеры

Уменьшение цветовой глубины изображения может приводить к значительным визуальным побочным эффектам. Если исходное изображение – фотография, в нем, вероятно, содержатся тысячи или даже миллионы различных цветов. Процесс ограничения доступных цветов определенной цветовой палитрой фактически отбрасывает часть цветовой информации. На качество изображения с уменьшенной цветовой глубиной может влиять ряд факторов. Наиболее важным, пожалуй, является используемая цветовая палитра. Например, исходное изображение (рисунок 1) может быть сведено к 216-цветной веб-безопасной палитре. Если исходные цвета пикселей просто заменяются ближайшим доступным цветом из палитры, дитеринг не применяется (рисунок 2). Однако, как правило, такой подход приводит к появлению плоских областей (контуров) и потере деталей, а также может создавать цветовые пятна, значительно отличающиеся от оригинала. В областях с тенями или градиентами могут возникать цветовые полосы, которые могут отвлекать внимание. Применение дитеринга помогает минимизировать подобные визуальные артефакты и обычно обеспечивает более точное воспроизведение оригинала (рисунок 3). Дитеринг помогает уменьшить цветовые полосы и эффект плоскостности. Одна из проблем, связанных с использованием фиксированной цветовой палитры, заключается в том, что многие необходимые цвета могут отсутствовать в палитре, а многие доступные цвета могут оказаться ненужными; например, фиксированная палитра, состоящая в основном из оттенков зеленого, плохо подойдет для изображения пустыни. В таких случаях может быть полезно использовать оптимизированную цветовую палитру. Оптимизированная цветовая палитра – это палитра, в которой доступные цвета выбираются на основе частоты их использования в исходном изображении. Если изображение сведено с использованием оптимизированной палитры, результат часто намного ближе к оригиналу (рисунок 4). Количество цветов в палитре также является важным фактором. Например, если палитра ограничена всего 16 цветами, результирующее изображение может страдать от дополнительной потери деталей, что приведет к еще более заметным проблемам с плоскостностью и цветовыми полосами (рисунок 5). Вновь, дитеринг может помочь минимизировать подобные артефакты (рисунок 6).

Reducing the color depth of an image can have significant visual side effects. If the original image is a photograph, it is likely to have thousands or even millions of distinct colors. The process of constraining the available colors to a specific color palette effectively throws away a certain amount of color information. A number of factors can affect the resulting quality of a color reduced image. Perhaps most significant is the color palette that will be used in the reduced image. For example, an original image (Figure 1) may be reduced to the 216 color web safe palette. If the original pixel colors are simply translated into the closest available color from the palette, no dithering will occur (Figure 2). However, typically this approach will result in flat areas (contours) and a loss of detail and may produce patches of color that are significantly different from the original. Shaded or gradient areas may produce color banding which may be distracting. The application of dithering can help to minimize such visual artifacts and usually results in a better representation of the original (Figure 3). Dithering helps to reduce color banding and flatness. One of the problems associated with using a fixed color palette is that many of the needed colors may not be available in the palette, and many of the available colors may not be needed; a fixed palette containing mostly shades of green would not be well suited for an image of a desert, for instance. The use of an optimized color palette can be of benefit in such cases. An optimized color palette is one in which the available colors are chosen based on how frequently they are used in the original source image. If the image is reduced based on an optimized palette the result is often much closer to the original (Figure 4). The number of colors available in the palette is also a contributing factor. If, for example, the palette is limited to only 16 colors then the resulting image could suffer from additional loss of detail, resulting in even more pronounced problems with flatness and color banding (Figure 5). Once again, dithering can help to minimize such artifacts (Figure 6).

Приложения

Одно из распространенных применений дитеринга — более точное отображение графики, содержащей больший диапазон цветов, чем способен отобразить аппаратный модуль дисплея. Например, дитеринг может использоваться для отображения фотографического изображения, содержащего миллионы цветов, на видеооборудовании, которое способно отображать одновременно только 256 цветов. Для создания приближенного изображения оригинала будут использованы 256 доступных цветов. Без дитеринга цвета на исходном изображении будут квантованы до ближайшего доступного цвета, что приведет к отображению изображения, которое будет плохим представлением оригинала. Самые ранние примеры использования дитеринга были связаны с уменьшением изображений до 1 бита, черно-белого. Возможно, это делалось для печати даже раньше, чем для растровой видеографики. Это было распространено при создании изображений для отображения на 1-битных видеодисплеях систем X, Apollo и подобных Unix-рабочих станций. Дитеринг обычно предварительно вычислялся, и хранилось только дитерированное изображение, поскольку вычислительные ресурсы и объем памяти были слишком ограничены для вычисления его в реальном времени. Примером для пользователей домашних компьютеров может служить эмуляция графики CGA с 4 цветами низкого разрешения на монохромных графических картах Hercules с более высоким разрешением, где цвета преобразовывались в упорядоченные дитерные шаблоны. Некоторые жидкокристаллические дисплеи используют временный дитеринг для достижения аналогичного эффекта. Быстро чередуя цветовое значение каждого пикселя между двумя приблизительными цветами в цветовом пространстве панели, дисплей, поддерживающий только 18-битный цвет (6 бит на канал), может представлять 24-битное цветное изображение (8 бит на канал). Дитеринг, при котором аппаратное обеспечение дисплея является основным ограничением глубины цвета, обычно используется в программном обеспечении, таком как веб-браузеры. Поскольку веб-браузер может получать графические элементы из внешнего источника, ему может потребоваться выполнять дитеринг изображений, содержащих слишком много цветов для доступного дисплея. Проблемы с дитерингом привели к определению цветовой палитры, известной как «веб-безопасная палитра», для выбора цветов, которые не будут подвергаться дитерингу на системах, способных отображать одновременно только 256 цветов. Но даже когда общее количество доступных цветов в аппаратном обеспечении дисплея достаточно для правильной передачи полноцветных цифровых фотографий, полосатость все еще может быть заметна глазу, особенно на больших участках с плавными переходами оттенков. Умеренный дитеринг может решить эту проблему, не делая изображение зернистым. Профессиональное программное обеспечение для обработки изображений обычно использует эти методы для улучшения отображения. Другое полезное применение дитеринга — ситуации, в которых формат графического файла является ограничивающим фактором. В частности, широко используемый формат GIF ограничен использованием 256 или менее цветов. Такие изображения имеют определенную цветовую палитру, содержащую ограниченное количество цветов, которые могут быть использованы в изображении. В таких случаях графический редактор может отвечать за дитеринг изображений перед сохранением их в таких ограниченных форматах. Дитеринг аналогичен технике полутонов, используемой в печати. По этой причине термин «дитеринг» иногда используется как взаимозаменяемый с термином «полутонирование», особенно в контексте цифровой печати. Возможность струйных принтеров печатать отдельные точки увеличила использование дитеринга в печати. Типичный настольный струйный принтер может печатать максимум 16 цветов, поскольку это комбинация точки или отсутствия точки из сиановой, пурпурной, желтой и черной печатающих головок. Для воспроизведения широкого диапазона цветов используется дитеринг. В плотно запечатанных областях, где цвет темный, дитеринг не всегда виден, поскольку точки краски сливаются, создавая более однородный отпечаток. Однако при внимательном рассмотрении светлых участков отпечатка, где точки расположены дальше друг от друга, можно увидеть дитерные узоры.

One common application of dithering is to more accurately display graphics containing a greater range of colors than the display hardware is capable of showing. For example, dithering might be used in order to display a photographic image containing millions of colors on video hardware that is only capable of showing 256 colors at a time. The 256 available colors would be used to generate a dithered approximation of the original image. Without dithering, the colors in the original image would be quantized to the closest available color, resulting in a displayed image that is a poor representation of the original. The very earliest uses were to reduce images to 1 bit black and white. This may have been done for printing even earlier than for bit mapped video graphics. It was common for making images to display on 1 bit video displays for X and Apollo and similar Unix workstations. The dithering was usually pre computed and only the dithered image was stored; computation and memory were far too limited to compute it live. An example home computer users may have seen was emulation of lower resolution CGA 4 color graphics on higher resolution monochrome Hercules graphics cards, with the colors being translated to ordered dither patterns. Some liquid crystal displays use temporal dithering to achieve a similar effect. By alternating each pixel's color value rapidly between two approximate colors in the panel's color space, a display panel that natively supports only 18 bit color (6 bits per channel) can represent a 24 bit color image (8 bits per channel). Dithering such as this, in which the computer's display hardware is the primary limitation on color depth, is commonly employed in software such as web browsers. Since a web browser may be retrieving graphical elements from an external source, it may be necessary for the browser to perform dithering on images with too many colors for the available display. It was due to problems with dithering that a color palette known as the web safe color palette was identified, for use in choosing colors that would not be dithered on systems capable of displaying only 256 colors simultaneously. But even when the total number of available colors in the display hardware is high enough to properly render full color digital photographs, banding may still be evident to the eye, especially in large areas of smooth shade transitions. Modest dithering can resolve this without making the image appear grainy. High end still image processing software commonly uses these techniques for improved display. Another useful application of dithering is for situations in which the graphics file format is the limiting factor. In particular, the commonly used GIF format is restricted to the use of 256 or fewer colors. Images such as these have a defined color palette containing a limited number of colors that the image may use. For such situations, graphical editing software may be responsible for dithering images prior to saving them in such restrictive formats. Dithering is analogous to the halftone technique used in printing. For this reason, the term dithering is sometimes used interchangeably with the term halftoning, particularly in association with digital printing. The ability of inkjet printers to print isolated dots has increased the use of dithering in printing. A typical desktop inkjet printer can print, at most, just 16 colors as this is the combination of dot or no dot from cyan, magenta, yellow and black print heads. To reproduce a large range of colors, dithering is used. In densely printed areas, where the color is dark the dithering is not always visible because the dots of ink merge producing a more uniform print. However, a close inspection of the light areas of a print where dots are further apart reveals dithering patterns.

Другие применения

Стимулированное рассеяние Бриллуана (SBS) — это нелинейный оптический эффект, ограничивающий передаваемую оптическую мощность в волоконно-оптических системах. Этот предел мощности можно увеличить, используя дитеринг центральной частоты оптического сигнала, который обычно реализуется путем модуляции входного напряжения смещения лазера. См. также поляризационное перемешивание. Фазовый дитеринг может быть использован для повышения качества выходного сигнала в прямой цифровой синтезе. Другое распространенное применение — успешное прохождение тестов на электромагнитную совместимость (ЭМС) с помощью дитеринга частоты тактового сигнала с расширенным спектром, который размывает отдельные частотные пики. Недавно другой тип временного дитеринга был внедрен на финансовых рынках для снижения стимулов к высокочастотной торговле. ParFX, лондонский валютный рынок, начавший работу в 2013 году, вводит кратковременные случайные задержки на все входящие ордера; сообщается, что другие валютные биржи экспериментируют с этой технологией. Использование подобного временного буферирования или дитеринга было рекомендовано и в более широком контексте финансовой торговли акциями, сырьевыми товарами и производными финансовыми инструментами.