Пирамида изображений
Пирами́да изображе́ний — класс кратномасштабных иерархических структур данных, разработанных для применения в прикладных задачах машинного зрения, сжатия информации, анализа текстур растровых изображений и т. п. Такие структуры содержат на каждом своём уровне иерархии уменьшенную версию предыдущего изображения, каждая из которых рекурсивно вычисляется на базе предыдущих слоёв посредством применения однотипной операции (например — сглаживания)[1]. При этом всякому уровню иерархии ставится в соответствие актуальный для решаемой задачи параметр масштаба, который описывает интересующие свойства изображения[2].
Краткая история
Возникновение интереса специалистов по математической обработке изображений к иерархическим пирамидам связано с необходимостью решать некоторые прикладные задачи в условиях априори неизвестного масштаба искомых свойств или признаков. Так как этот характерный размер не определён, то возможным путём к решению является декомпозиция исходного изображения на иерархическую систему в которой каждый слой представлен своим собственным масштабом, артикулирующим отдельный диапазон признаков. Аналогичным образом устроена система обработки видеоинформации у биологических объектов[2].
Появление первых иерархических пирамид датируется концом 1970-х годов[3], выбор их названия был продиктован чисто внешней зрительной ассоциацией[4]. В 1980-х началось активное использование иерархических пирамид в задачах смешивания изображений и поиска на них соответствия между разномасштабными элементами и структурами. В это же самое время завершилось создание непрерывных версий пирамидальных структур для пространственно-масштабной обработки. Однако в конце 1980-х годов традиционным пирамидам пришлось потесниться из-за активного внедрения вейвлет-преобразований[5].
Описание
По своей сути пирамида изображений может рассматриваться как набор представлений, упорядоченный в форме вертикальной иерархии по мере уменьшения некоего масштаба. Обычно в основании пирамиды располагается оригинальное изображение высокого разрешения, а по мере движения вверх масштаб и разрешение уменьшаются. В результате, на вершине оказывается самое грубое приближение с низким качеством и информативностью[6][7].
Как правило, в целях генерирования пирамиды для удобства её представления изначальное изображение пересчитывается в размерности, кратные степени числа 2[1]. Если исходные данные имели вид массива пикселов , то эта запись эквивалентна , где [6]. В таком виде параметр играет роль высоты пирамиды, выраженной в количестве представлений исходного изображения (слоёв)[8].
Первый слой (приближение) пирамиды можно получить последовательным усреднением соседних пикселей, результатом которого станет массив . Применяя эту процедуру рекурсивно получается набор изображений с экспоненциально уменьшающимися размерами. При этом, пикселы промежуточных изображений содержат в себе информацию о квадратных блоках пикселов нижележащих слоёв с более высоким разрешением[9]. Тогда произвольно выбранный промежуточный слой будет содержать в себе пикселов, где 0 ≤ j < n, а полное количество пикселов в пирамиде, содержащей слоёв[6]:
Промежуточные узлы пирамиды не обязательно должны представлять собой взвешенное среднее по интенсивности из нижних слоёв. Вместо интенсивности в них могут храниться другие виды информации, например — дескрипторы текстур или параметры геометрических элементов (линий, кривых и т. п.)[10]
Применение пирамид
Наиболее очевидным полезным свойством кратномасштабных пирамид является возможность снижения вычислительных затрат различных алгоритмов за счёт применения принципа «разделяй и властвуй» []. Также к преимуществам представления двумерного изображения в виде пирамиды считается соотнесение его локальных элементов и свойств с глобальными. Это позволяет конструировать древовидные структуры данных для многофакторного анализа, включающего в себя локальную и глобальную информацию. Например, связывая значения отдельных пикселов со свойствами окружающих их регионов[11].
Разновидности
Классическими видами пирамидальных иерархий считаются гауссовы пирамиды и пирамиды лапласианов. Благодаря своим хорошо изученным свойствам они получили широкое распространение в целом ряде практических приложений[12].
Гауссова пирамида состоит из слоёв, каждый из которой получается из предыдущего с помощью сглаживания симметричной гауссоидой (низкочастотная фильтрация) и последующей за этим дискретизацией (см. Фильтр Гаусса). Совокупность этих слоёв называется грубой шкалой изображения. Областью применения гауссовых пирамид обычно являются задачи поиска изображений по масштабу и пространственного сопоставления различных изображений[13][14].
Пирамиды лапласианов вычисляются последовательным сглаживанием и децимацией начальных данных. При этом, каждый уровень пирамиды является уточнением предыдущих и соответствует отдельной полосе частот (полосовая фильтрация). В отличие от гауссовых пирамид, этот тип данных допускает более высокую степень сжатия информации[15][16]. В дополнение к этому исходное изображение может быть легко восстановлено на основе суперпозиции промежуточных слоёв, что позволяет не хранить его в памяти[17].
Примечания
- ↑ 1 2 Dictionary of Computer Vision and Image Processing, 2014, Image pyramid, p. 132.
- ↑ 1 2 Szeliski, 2011, Pyramids and wavelets, p. 127.
- ↑ Szeliski, 2011, A rough timeline of some of the most active topics of research in computer vision, p. 10.
- ↑ Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 240.
- ↑ Szeliski, 2011, A brief history, p. 10.
- ↑ 1 2 3 Гонсалес, Вудс, 2005, Пирамиды изображений, с. 514.
- ↑ Jayaraman, 2009, Image Pyramid, p. 650.
- ↑ Montanvert, 1990, Introduction, p. 28.
- ↑ Rosenfeld, 1984, Some Varieties of Pyramids, p. 2—3.
- ↑ Rosenfeld, 1984, Some Varieties of Pyramids, p. 3.
- ↑ Rosenfeld, 1984, Some Useful Properties of Pyramids, p. 2.
- ↑ Szeliski, 2011, Multi-resolution representations, p. 135.
- ↑ Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 241—242.
- ↑ Jayaraman, 2009, Gaussian Pyramid, p. 650.
- ↑ Jayaraman, 2009, Laplacian Pyramid, p. 650.
- ↑ Гонсалес, Вудс, 2005, Пирамиды изображений, с. 517.
- ↑ 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.