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

Краткая история

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

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

Описание

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

Как правило, в целях генерирования пирамиды для удобства её представления изначальное изображение пересчитывается в размерности, кратные степени числа 2 . Если исходные данные имели вид массива пикселов ${\displaystyle N\times N}$ , то эта запись эквивалентна ${\displaystyle 2^{n}\times 2^{n}}$ , где ${\displaystyle n=\log _{2}N}$ . В таком виде параметр ${\displaystyle n}$ играет роль высоты пирамиды, выраженной в количестве представлений исходного изображения (слоёв) .

Первый слой (приближение) пирамиды можно получить последовательным усреднением соседних пикселей, результатом которого станет массив ${\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}}$ . Применяя эту процедуру рекурсивно получается набор изображений с экспоненциально уменьшающимися размерами. При этом, пикселы промежуточных изображений содержат в себе информацию о квадратных блоках пикселов нижележащих слоёв с более высоким разрешением . Тогда произвольно выбранный промежуточный слой будет содержать в себе ${\displaystyle 2^{j}\times 2^{j}}$ пикселов, где 0 ≤ j < n , а полное количество пикселов в пирамиде, содержащей ${\displaystyle k}$ слоёв :

${\displaystyle 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}.}$

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

Применение пирамид

Наиболее очевидным полезным свойством кратномасштабных пирамид является возможность снижения вычислительных затрат различных алгоритмов за счёт применения принципа « разделяй и властвуй » ^{[ уточнить ]} . Также к преимуществам представления двумерного изображения в виде пирамиды считается соотнесение его локальных элементов и свойств с глобальными. Это позволяет конструировать древовидные структуры данных для многофакторного анализа , включающего в себя локальную и глобальную информацию. Например, связывая значения отдельных пикселов со свойствами окружающих их регионов .

Разновидности

Классическими видами пирамидальных иерархий считаются гауссовы пирамиды и пирамиды лапласианов . Благодаря своим хорошо изученным свойствам они получили широкое распространение в целом ряде практических приложений .

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

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

Примечания

Источники

• Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. — М. : «Техносфера», 2005. — 1072 с. — ISBN 5-94836-028-8 .
• Форсайт, Д. Компьютерное зрение. Современный подход / Д. Форсайт, Ж. Понс. — М. : «Вильямс», 2004. — 928 с. — ББК 32.973.26-018.2.75 . — УДК . — ISBN 5-8459-0542-7 .
• Jähne, B. Digital Image processing : [ англ. ] . — 5th ed. — Springer-Verlag, 2002. — ISBN 3-540-67754-2 .
• Jayaraman, S. Digital Image Processing. — Tata McGraw Hill, 2009. — ISBN 978-0-07-014479-8 .
• Montanvert, A. Hierarchical Image Analysis Using Irregular Tesselations : [ англ. ] / G. Goos, J. Hartmanis. — Computer Vision - ECCV 90. — Springer-Verlag, 1990. — ISBN 3-540-52522-X .
• Szeliski, R. Computer Vision Algorithms and Applications : [ англ. ] . — Springer, 2011. — ISBN 978-1-84882-934-3 . — doi : .
• Dictionary of Computer Vision and Image Processing : [ англ. ] . — 2th ed. — John Wiley & Sons Ltd, 2014. — ISBN 978-1-119-94186-6 .
• Multiresolution Image Processing and Analysis : [ англ. ] / A. Rosenfeld. — Springer-Verlag, 1984. — ISBN 978-3-642-51592-7 . — doi : .