Русская Википедия:Пирамида изображений
Пирами́да изображе́ний — класс кратномасштабных иерархических структур данных, разработанных для применения в прикладных задачах машинного зрения, сжатия информации, анализа текстур растровых изображений и т. п. Такие структуры содержат на каждом своём уровне иерархии уменьшенную версию предыдущего изображения, каждая из которых рекурсивно вычисляется на базе предыдущих слоёв посредством применения однотипной операции (например — сглаживания)Шаблон:Sfn. При этом всякому уровню иерархии ставится в соответствие актуальный для решаемой задачи параметр масштаба, который описывает интересующие свойства изображенияШаблон:Sfn.
Краткая история
Возникновение интереса специалистов по математической обработке изображений к иерархическим пирамидам связано с необходимостью решать некоторые прикладные задачи в условиях априори неизвестного масштаба искомых свойств или признаков. Так как этот характерный размер не определён, то возможным путём к решению является декомпозиция исходного изображения на иерархическую систему в которой каждый слой представлен своим собственным масштабом, артикулирующим отдельный диапазон признаков. Аналогичным образом устроена система обработки видеоинформации у биологических объектовШаблон:Sfn.
Появление первых иерархических пирамид датируется концом 1970-х годовШаблон:Sfn, выбор их названия был продиктован чисто внешней зрительной ассоциациейШаблон:Sfn. В 1980-х началось активное использование иерархических пирамид в задачах смешивания изображений и поиска на них соответствия между разномасштабными элементами и структурами. В это же самое время завершилось создание непрерывных версий пирамидальных структур для пространственно-масштабной обработки. Однако в конце 1980-х годов традиционным пирамидам пришлось потесниться из-за активного внедрения вейвлет-преобразованийШаблон:Sfn.
Описание
По своей сути пирамида изображений может рассматриваться как набор представлений, упорядоченный в форме вертикальной иерархии по мере уменьшения некоего масштаба. Обычно в основании пирамиды располагается оригинальное изображение высокого разрешения, а по мере движения вверх масштаб и разрешение уменьшаются. В результате, на вершине оказывается самое грубое приближение с низким качеством и информативностьюШаблон:SfnШаблон:Sfn.
Как правило, в целях генерирования пирамиды для удобства её представления изначальное изображение пересчитывается в размерности, кратные степени числа 2Шаблон:Sfn. Если исходные данные имели вид массива пикселов <math>N \times N</math>, то эта запись эквивалентна <math>2^n \times 2^n</math>, где <math>n = \log_2 N</math>Шаблон:Sfn. В таком виде параметр <math>n</math> играет роль высоты пирамиды, выраженной в количестве представлений исходного изображения (слоёв)Шаблон:Sfn.
Первый слой (приближение) пирамиды можно получить последовательным усреднением соседних пикселей, результатом которого станет массив <math>\frac{N}{2} \times \frac{N}{2}</math>. Применяя эту процедуру рекурсивно получается набор изображений с экспоненциально уменьшающимися размерами. При этом, пикселы промежуточных изображений содержат в себе информацию о квадратных блоках пикселов нижележащих слоёв с более высоким разрешениемШаблон:Sfn. Тогда произвольно выбранный промежуточный слой будет содержать в себе <math>2^j \times 2^j</math> пикселов, где Шаблон:Math, а полное количество пикселов в пирамиде, содержащей <math>k</math> слоёвШаблон:Sfn:
- <math> N^2 \left ( 1 + \frac{1}{4^1} + \frac{1}{4^2} + \frac{1}{4^3} + ... + \frac{1}{4^k} \right ) \leq \frac{4}{3} N^2. </math>
Промежуточные узлы пирамиды не обязательно должны представлять собой взвешенное среднее по интенсивности из нижних слоёв. Вместо интенсивности в них могут храниться другие виды информации, например — дескрипторы текстур или параметры геометрических элементов (линий, кривых и т. п.)Шаблон:Sfn
Применение пирамид
Наиболее очевидным полезным свойством кратномасштабных пирамид является возможность снижения вычислительных затрат различных алгоритмов за счёт применения принципа «разделяй и властвуй» Шаблон:Уточнить. Также к преимуществам представления двумерного изображения в виде пирамиды считается соотнесение его локальных элементов и свойств с глобальными. Это позволяет конструировать древовидные структуры данных для многофакторного анализа, включающего в себя локальную и глобальную информацию. Например, связывая значения отдельных пикселов со свойствами окружающих их регионовШаблон:Sfn.
Разновидности
Классическими видами пирамидальных иерархий считаются гауссовы пирамиды и пирамиды лапласианов. Благодаря своим хорошо изученным свойствам они получили широкое распространение в целом ряде практических приложенийШаблон:Sfn.
Гауссова пирамида состоит из слоёв, каждый из которой получается из предыдущего с помощью сглаживания симметричной гауссоидой (низкочастотная фильтрация) и последующей за этим дискретизацией (см. Фильтр Гаусса). Совокупность этих слоёв называется грубой шкалой изображения. Областью применения гауссовых пирамид обычно являются задачи поиска изображений по масштабу и пространственного сопоставления различных изображенийШаблон:SfnШаблон:Sfn.
Пирамиды лапласианов вычисляются последовательным сглаживанием и децимацией начальных данных. При этом, каждый уровень пирамиды является уточнением предыдущих и соответствует отдельной полосе частот (полосовая фильтрация). В отличие от гауссовых пирамид, этот тип данных допускает более высокую степень сжатия информацииШаблон:SfnШаблон:Sfn. В дополнение к этому исходное изображение может быть легко восстановлено на основе суперпозиции промежуточных слоёв, что позволяет не хранить его в памятиШаблон:Sfn.
Примечания
Источники
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Публикация
