Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Пирамида изображений

Пирами́да изображе́ний — класс кратномасштабных иерархических структур данных, разработанных для применения в прикладных задачах машинного зрения, сжатия информации, анализа текстур растровых изображений и т. п. Такие структуры содержат на каждом своём уровне иерархии уменьшенную версию предыдущего изображения, каждая из которых рекурсивно вычисляется на базе предыдущих слоёв посредством применения однотипной операции (например — сглаживания)[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. 1 2 Dictionary of Computer Vision and Image Processing, 2014, Image pyramid, p. 132.
  2. 1 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. 1 2 3 Гонсалес, Вудс, 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.