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

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

Краткая историяПравить

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

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

ОписаниеПравить

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

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

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

\text{[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}

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

Применение пирамидПравить

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

РазновидностиПравить

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

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

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

ПримечанияПравить

↑ ¹ ² Dictionary of Computer Vision and Image Processing, 2014, Image pyramid, p. 132.
↑ ¹ ² 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.
↑ ¹ ² ³ Гонсалес, Вудс, 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.

[_017625c718c00490-1] ¹ ² Dictionary of Computer Vision and Image Processing, 2014, Image pyramid, p. 132.

[_d0a9360910fbc456-2] ¹ ² Szeliski, 2011, Pyramids and wavelets, p. 127.

[_08b4041dc0aa89b7-3] Szeliski, 2011, A rough timeline of some of the most active topics of research in computer vision, p. 10.

[_3229d9525dbaa881-4] Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 240.

[_0766ca093ae14b71-5] Szeliski, 2011, A brief history, p. 10.

[_0efa67d4892d1d4a-6] ¹ ² ³ Гонсалес, Вудс, 2005, Пирамиды изображений, с. 514.

[_46e8a977a912f0a4-7] Jayaraman, 2009, Image Pyramid, p. 650.

[_2449e99700782ba0-8] Montanvert, 1990, Introduction, p. 28.

[_0bbb90c523b75ee8-9] Rosenfeld, 1984, Some Varieties of Pyramids, p. 2—3.

[_6bd12ab2a322a2dc-10] Rosenfeld, 1984, Some Varieties of Pyramids, p. 3.

[_f77fa1ae9ca8a600-11] Rosenfeld, 1984, Some Useful Properties of Pyramids, p. 2.

[_037455623558c8c4-12] Szeliski, 2011, Multi-resolution representations, p. 135.

[_c724ac68cc7d818e-13] Форсайт, Понс, 2004, Метод: масштаб и пирамиды изображений, с. 241—242.

[_b072213deb43f076-14] Jayaraman, 2009, Gaussian Pyramid, p. 650.

[_19f000e3ccd866fc-15] Jayaraman, 2009, Laplacian Pyramid, p. 650.

[_0efa67d4892d1d49-16] Гонсалес, Вудс, 2005, Пирамиды изображений, с. 517.

[_83b87a4c33f888d5-17] Jähne, 2002, Laplacian pyramid, p. 140.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]