Алгоритм Адам7
Adam7 — это чересстрочной развертки алгоритм для растровых изображений , наиболее известный как схема чересстрочной развертки, опционально используемая в PNG изображениях . Чересстрочное изображение Adam7 разбито на семь частей изображения, которые определяются путем репликации этого шаблона 8×8 по всему изображению.
1 6 4 6 2 6 4 67 7 7 7 7 7 7 75 6 5 6 5 6 5 67 7 7 7 7 7 7 73 6 4 6 3 6 4 67 7 7 7 7 7 7 75 6 5 6 5 6 5 67 7 7 7 7 7 7 7 |
Части изображений затем сохраняются в файле изображения в числовом порядке.
Adam7 использует семь проходов и работает в обоих измерениях, по сравнению с четырьмя проходами в вертикальном измерении, используемыми GIF . Это означает, что аппроксимация всего изображения может быть воспринята гораздо быстрее на первых проходах, особенно если такие алгоритмы интерполяции, как бикубическая интерполяция . используются [1]
История
[ редактировать ]Adam7 назван в честь Адама М. Костелло, который предложил этот метод 2 февраля 1995 года, и в честь семи включенных в него шагов.
Это перестановка [2] этой пятипроходной схемы [3] это ранее было предложено Ли Дэниелом Крокером :
1 5 3 55 4 5 43 5 2 55 4 5 4 |
Альтернативные спекулятивные предложения в то время включали переплетение квадратных спиралей и использование кривых Пеано , но они были отвергнуты как слишком сложные.
Проходит
[ редактировать ]Пиксели, включенные в каждый проход, и общее количество пикселей, закодированных в этот момент, следующие:
Пройден 1, 1/64 = 1,5625%
Пройден 2, 1/32 = 3,125%
Пройден 3, 1/16 = 6,25%
Пройден 4, 1/8 = 12,5%
Пройден 5, 1/4 = 25%
Пройден 6, 1/2 = 50%
Пройден 7, 1/1 = 100%
При рендеринге изображение обычно интерполируется на более ранних этапах, а не рендерятся только эти пиксели.
Связанные алгоритмы
[ редактировать ]Adam7 — это многомасштабная модель данных, похожая на дискретное вейвлет-преобразование с вейвлетами Хаара , хотя она начинается с блока 8×8 и понижает дискретизацию изображения, а не децимирует ( низкочастотная фильтрация , затем понижающая дискретизация). Таким образом, он предлагает худшее частотное поведение, демонстрируя артефакты ( пикселизацию ) на ранних стадиях, в обмен на более простую реализацию.
Итерация
[ редактировать ]Adam7 возникает в результате повторения следующего шаблона:
1233 |
что можно интерпретировать как «складывание» в вертикальном и горизонтальном измерениях. Аналогично, переплетение GIF 1324 можно рассматривать как итерацию 12 шаблон, но только в вертикальном направлении ( 12 расширяется до 1.2. который заполняется как 1324 ).
Использование этого трехпроходного шаблона означает, что первый проход равен (1/2). 2 = 1/4 (25%) изображения.
Повторение этого шаблона один раз дает схему с 5 проходами; после 3 проходов это дает
1 . 2 .. . . .3 . 3 .. . . . |
который затем заполняется до:
1 4 2 45 5 5 53 4 3 45 5 5 5 |
В схеме из 5 проходов первый проход (1/4) 2 = 1/16 (6,25%) изображения.
Повторная итерация дает 7-проходную схему Adam7, где первый проход (1/8) 2 = 1/64 (1,5625%) изображения.
В принципе, это можно повторять, получая схему из 9 проходов, схему из 11 проходов и т. д., или, альтернативно, можно использовать адаптивное количество проходов, столько, сколько позволяет размер изображения (поэтому первый проход состоит из один пиксель), как обычно в безмасштабном многомасштабном моделировании. В контексте разработки PNG (т.е. для рассматриваемых размеров изображения и скорости соединения) 7-проходная схема считалась достаточной. [ почему? ] и предпочтительнее простой 5-проходной схемы.
Ссылки
[ редактировать ]- ^ Введение в PNG - nuwen.net
- ^ Костелло, Адам М. (2 февраля 1995 г.). «Возврат к чересстрочной развертке: схема Adam7» . png-список (список рассылки) . Проверено 18 апреля 2016 г.
Я немного переработал схему Lee7 (Lee7 является очевидным расширением пятипроходной схемы Ли), получив схему Adam7.
- ^ Лейн, Том (1 февраля 1995 г.). «Методы чересстрочной развертки: визуальное тестирование» . png-список (список рассылки) . Проверено 18 апреля 2016 г.
Предложение Ли Крокера о 5-проходном двумерном чересстрочном соединении