Пирамида изображений

Пирамида изображений

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Dictionary of Computer Vision and Image Processing, 2014, Image pyramid, p. 132.
2. Szeliski, 2011, Pyramids and wavelets, p. 127.
3. Szeliski, 2011, A rough timeline of some of the most active topics of research in computer vision, p. 10.
4. Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 240.
5. Szeliski, 2011, A brief history, p. 10.
6. Гонсалес, Вудс, 2005, Пирамиды изображений, с. 514.
7. Jayaraman, 2009, Image Pyramid, p. 650.
8. Montanvert, 1990, Introduction, p. 28.
9. Rosenfeld, 1984, Some Varieties of Pyramids, p. 2—3.
10. Rosenfeld, 1984, Some Varieties of Pyramids, p. 3.
11. Rosenfeld, 1984, Some Useful Properties of Pyramids, p. 2.
12. Szeliski, 2011, Multi-resolution representations, p. 135.
13. Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 241—242.
14. Jayaraman, 2009, Gaussian Pyramid, p. 650.
15. Jayaraman, 2009, Laplacian Pyramid, p. 650.
16. Гонсалес, Вудс, 2005, Пирамиды изображений, с. 517.
17. Jähne, 2002, Laplacian pyramid, p. 140.

Источники

• Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. — М. : «Техносфера», 2005. — 1072 с. — ISBN 5-94836-028-8.
• Форсайт, Д. Компьютерное зрение. Современный подход / Д. Форсайт, Ж. Понс. — М. : «Вильямс», 2004. — 928 с. — ББК 32.973.26-018.2.75. — УДК 681.3.07^(G). — 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:10.1007/978-1-84882-935-0.
• 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:10.1007/978-3-642-51590-3.