Во второй половине XX вѣка (с появлением компьютеров и затѣмъ ещё с появлением у компьютеров цифровых растровых устройств вывода) человѣчество поставило перед собою интересную инженерную задачу: каким образом цифровое растровое устройство вывода должно располагать такие точки растра, каждой из которых можно придать лишь один из немногих цвѣтовъ, если конечною цѣлью является отображение изображения, имѣющаго нѣсколько большее количество цвѣтовъ?
Общеизвѣстны три примѣра этого:
① При чёрно-бѣлой печати выбирать можно только между чёрными точками (с краскою на бумаге) и бѣлыми (имѣющими цвѣтъ бумаги), а хочется передавать и сѣрые цвѣта.
② Ещё ≈35—40 лѣтъ тому назад видеокарты IBM могли выводить в графическом режиме пикселы только четырёх цвѣтовъ (таков был адаптер CGA в 1981 году, если не использовалися те трюки демосцены, о которых я бѣгло упоминал тут 10 ноября 2021 года въ предпослѣднемъ абзаце), или 16 цвѣтовъ (EGA, 1984 г.), или 256 цвѣтовъ (VGA, 1987 г.), а нѣкоторымъ хотелось показывать на экране если и не фотографии, то, по меньшей мѣрѣ, чуть болѣе полноцвѣтныя изображения.
③ Формат графических файлов GIF, до сих пор сохраняющий извѣстную долю прежней популярности как средство передачи анимаций по Интернету (в том числе и в Телеграме), ограничивает каждый кадр употреблением 256 цвѣтовъ.
На простые способы улучшения цвѣтопередачи набрели почти сразу (скажем, «располагая в шахматном порядке точки двух цвѣтовъ, получаем область промежуточного между ними цвѣта»), на болѣе сложные — попозже, и их оказалось довольно много («чѣмъ дальше въ лѣсъ, тѣмъ больше дров»): в вики проекта libcaca общее их перечисление занимает сразу нѣсколько страниц, раздѣлённыхъ по категориям: отсечение по пороговым значениям, формирование узоров, перераспредѣленіе ошибок и проч.
Третий подраздѣлъ на второй из этих страниц начинается упоминанием того приёма, которому посвящена и бóльшая часть страницы «Ordered dithering» в Википедии — рѣчь идёт о создании весьма регулярных узоров (по виду сѣтчатыхъ или крестообразных, отчасти напоминающих «вышивание крестиком») при математическом посредстве тѣхъ матрицъ, которыя Bryce Edward Bayer опубликовал в 1973 году в своей работе «An optimum method for two-level rendition of continuous-tone pictures». (Это был тот самый Байер, который чуть позже придумал и запатентовал матрицу пикселов RGGB, которая и доныне широчайше используется в цифровых фотоаппаратах и видеокамерах.)
Главнѣйшій недостаток байеровских узоров — их ясно видная искусственность, регулярность, лишённая какой-либо псевдослучайности. Однако при сохранении анимаций в формате GIF этот недостаток оборачивается двумя достоинствами:
⓵ Регулярные повторения пикселов обеспечивают неплохую сжимаемость байеровских узоров при посредстве алгоритма LZW, употребляемого при сжатии файлов GIF: суть этого алгоритма как раз и состоит в обнаружении и послѣдующемъ эффективном кодировании повторяющихся элементов картинки, экономящем объём файла.
⓶ Если в анимации возникает небольшая междукадровая разница, то она не усугубляется тѣмъ распространением на слишком многие сосѣдніе пикселы, которое непремѣнно произошло бы, если бы вмѣсто байеровских узоров использовалось перераспредѣленіе ошибок (совершаемое, скажем, по методу Флойда и Штейнберга 1976 г.), и поэтому не создаёт чрезмѣрнаго междукадрового поблёскивания или перескока (танца) пикселов, раздражающего взор зрителя. Притом, состоя из небольшого количества пикселов, такая междукадровая разница меньше отягощает собою и объём файла, а не только взгляд.
Сочетание этих двух достоинств оказывает такое благотворное влияние на сжатие GIF, что в марте 2015 года, когда в утилиту FFmpeg версии 2.6 был добавлен генератор палитры для анимаций GIF (создающий одну палитру на весь файл), автор обзора «High quality GIF with FFmpeg» сообщил, что отход от байеровских узоров к алгоритму перераспредѣленія ошибок, хотя совершается в пользу большего воспринимаемого качества (то есть, надо понимать, в пользу меньшей узорчатости), совершенно убивает собою сжимаемость файла GIF («it completely kills the compression of GIF»).
Общеизвѣстны три примѣра этого:
① При чёрно-бѣлой печати выбирать можно только между чёрными точками (с краскою на бумаге) и бѣлыми (имѣющими цвѣтъ бумаги), а хочется передавать и сѣрые цвѣта.
② Ещё ≈35—40 лѣтъ тому назад видеокарты IBM могли выводить в графическом режиме пикселы только четырёх цвѣтовъ (таков был адаптер CGA в 1981 году, если не использовалися те трюки демосцены, о которых я бѣгло упоминал тут 10 ноября 2021 года въ предпослѣднемъ абзаце), или 16 цвѣтовъ (EGA, 1984 г.), или 256 цвѣтовъ (VGA, 1987 г.), а нѣкоторымъ хотелось показывать на экране если и не фотографии, то, по меньшей мѣрѣ, чуть болѣе полноцвѣтныя изображения.
③ Формат графических файлов GIF, до сих пор сохраняющий извѣстную долю прежней популярности как средство передачи анимаций по Интернету (в том числе и в Телеграме), ограничивает каждый кадр употреблением 256 цвѣтовъ.
На простые способы улучшения цвѣтопередачи набрели почти сразу (скажем, «располагая в шахматном порядке точки двух цвѣтовъ, получаем область промежуточного между ними цвѣта»), на болѣе сложные — попозже, и их оказалось довольно много («чѣмъ дальше въ лѣсъ, тѣмъ больше дров»): в вики проекта libcaca общее их перечисление занимает сразу нѣсколько страниц, раздѣлённыхъ по категориям: отсечение по пороговым значениям, формирование узоров, перераспредѣленіе ошибок и проч.
Третий подраздѣлъ на второй из этих страниц начинается упоминанием того приёма, которому посвящена и бóльшая часть страницы «Ordered dithering» в Википедии — рѣчь идёт о создании весьма регулярных узоров (по виду сѣтчатыхъ или крестообразных, отчасти напоминающих «вышивание крестиком») при математическом посредстве тѣхъ матрицъ, которыя Bryce Edward Bayer опубликовал в 1973 году в своей работе «An optimum method for two-level rendition of continuous-tone pictures». (Это был тот самый Байер, который чуть позже придумал и запатентовал матрицу пикселов RGGB, которая и доныне широчайше используется в цифровых фотоаппаратах и видеокамерах.)
Главнѣйшій недостаток байеровских узоров — их ясно видная искусственность, регулярность, лишённая какой-либо псевдослучайности. Однако при сохранении анимаций в формате GIF этот недостаток оборачивается двумя достоинствами:
⓵ Регулярные повторения пикселов обеспечивают неплохую сжимаемость байеровских узоров при посредстве алгоритма LZW, употребляемого при сжатии файлов GIF: суть этого алгоритма как раз и состоит в обнаружении и послѣдующемъ эффективном кодировании повторяющихся элементов картинки, экономящем объём файла.
⓶ Если в анимации возникает небольшая междукадровая разница, то она не усугубляется тѣмъ распространением на слишком многие сосѣдніе пикселы, которое непремѣнно произошло бы, если бы вмѣсто байеровских узоров использовалось перераспредѣленіе ошибок (совершаемое, скажем, по методу Флойда и Штейнберга 1976 г.), и поэтому не создаёт чрезмѣрнаго междукадрового поблёскивания или перескока (танца) пикселов, раздражающего взор зрителя. Притом, состоя из небольшого количества пикселов, такая междукадровая разница меньше отягощает собою и объём файла, а не только взгляд.
Сочетание этих двух достоинств оказывает такое благотворное влияние на сжатие GIF, что в марте 2015 года, когда в утилиту FFmpeg версии 2.6 был добавлен генератор палитры для анимаций GIF (создающий одну палитру на весь файл), автор обзора «High quality GIF with FFmpeg» сообщил, что отход от байеровских узоров к алгоритму перераспредѣленія ошибок, хотя совершается в пользу большего воспринимаемого качества (то есть, надо понимать, в пользу меньшей узорчатости), совершенно убивает собою сжимаемость файла GIF («it completely kills the compression of GIF»).