Тепловая сигнатура ядра

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

HKS был представлен в 2009 году Цзянь Саном, Максом Овсяниковым и Леонидасом Гибасом . ^[1] Он основан на ядре тепла , которое является фундаментальным решением уравнения теплопроводности . HKS является одним из многих недавно введенных дескрипторов формы, которые основаны на операторе Лапласа-Бельтрами, связанном с формой. ^[2]

Обзор

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

HKS основан на концепции диффузии тепла по поверхности. При заданном начальном распределении тепла по поверхности тепловое ядро ​​связывает количество тепла, переданного от к по истечении времени . Тепловое ядро ​​инвариантно относительно изометрических преобразований и устойчиво при малых возмущениях относительно изометрии. ^[1] Кроме того, тепловое ядро ​​полностью характеризует формы вплоть до изометрии и представляет все более глобальные свойства формы с увеличением времени. ^[3] Поскольку определено для пары точек во временной области, использование тепловых ядер напрямую в качестве признаков привело бы к высокой сложности. Вместо этого HKS ограничивает себя только временной областью, рассматривая только . HKS наследует большинство свойств тепловых ядер при определенных условиях. ^[1] ${\displaystyle u_{0}(x)}$ ${\displaystyle h_{t}(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle t}$ ${\displaystyle h_{t}(x,y)}$ ${\displaystyle h_{t}(x,x)}$

Технические подробности

Уравнение диффузии тепла над компактным римановым многообразием (возможно, с границей) задается выражением: ${\displaystyle M}$

${\displaystyle \left(\Delta -{\frac {\partial }{\partial t}}\right)u(x,t)=0}$

где — оператор Лапласа–Бельтрами , а — распределение тепла в точке времени . Решение этого уравнения можно выразить как, ^[1] ${\displaystyle \Delta }$ ${\displaystyle u(x,t)}$ ${\displaystyle x}$ ${\displaystyle t}$

${\displaystyle u(x,t)=\int h_{t}(x,y)u_{0}(y)dy.}$

Собственное разложение теплового ядра выражается как:

${\displaystyle h_{t}(x,y)=\sum _{i=0}^{\infty }\exp(-\lambda _{i}t)\phi _{i}(x)\phi _{i}(y)}$

где и являются собственным значением и собственной функцией . Тепловое ядро ​​полностью характеризует поверхность с точностью до изометрии: Для любого сюръективного отображения между двумя римановыми многообразиями и , если то является изометрией, и наоборот. ^[1] Для краткого описания признаков HKS ограничивает тепловое ядро ​​только временной областью, ${\displaystyle \lambda _{i}}$ ${\displaystyle \phi _{i}}$ ${\displaystyle i^{th}}$ ${\displaystyle \Delta }$ ${\displaystyle T:M\rightarrow N}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle h_{t}(x,y)=h_{t}(T(x),T(y))}$ ${\displaystyle T}$

${\displaystyle h_{t}(x,x)=\sum _{i=0}^{\infty }\exp(-\lambda _{i}t)\phi _{i}^{2}(x).}$

HKS, подобно тепловому ядру, характеризует поверхности при условии, что собственные значения для и неповторяющиеся . Термины можно представить как банк фильтров нижних частот с определением частот среза. ^[2] ${\displaystyle \Delta }$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle \exp(-\lambda _{i}t)}$ ${\displaystyle \lambda _{i}}$

Практические соображения

Поскольку , в общем случае, HKS является непараметрической непрерывной функцией, на практике ее представляют как дискретную последовательность значений, выбираемых в моменты времени . ${\displaystyle h_{t}(x,x)}$ ${\displaystyle \{h_{t_{1}}(x,x),\ldots ,h_{t_{n}}(x,x)\}}$ ${\displaystyle t_{1},\ldots ,t_{n}}$

В большинстве приложений базовое многообразие для объекта неизвестно. HKS можно вычислить, если доступно сеточное представление многообразия, используя дискретное приближение и дискретный аналог уравнения теплопроводности. В дискретном случае оператор Лапласа–Бельтрами является разреженной матрицей и может быть записан как, ^[1] ${\displaystyle \Delta }$

${\displaystyle L=A^{-1}W}$

где — положительная диагональная матрица с элементами, соответствующими площади треугольников в сетке, разделяющих вершину , и — симметричная полуопределенная весовая матрица. может быть разложена на , где — диагональная матрица собственных значений , расположенных в порядке возрастания, и — матрица с соответствующими ортонормированными собственными векторами. Дискретное тепловое ядро ​​— это матрица, заданная как, ${\displaystyle A}$ ${\displaystyle A(i,i)}$ ${\displaystyle i}$ ${\displaystyle W}$ ${\displaystyle L}$ ${\displaystyle L=\Phi \Lambda \Phi ^{T}A}$ ${\displaystyle \Lambda }$ ${\displaystyle L}$ ${\displaystyle \Phi }$

${\displaystyle K_{t}=\Phi \exp(-t\Lambda )\Phi ^{T}.}$

Элементы представляют диффузию тепла между вершинами и после времени . Затем HKS задается диагональными элементами этой матрицы, выбранными через дискретные интервалы времени. Подобно непрерывному случаю, дискретный HKS устойчив к шуму. ^[1] ${\displaystyle k_{t}(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle t}$

Ограничения

Неповторяющиеся собственные значения

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

Выбор параметра времени

Параметр времени в HKS тесно связан с масштабом глобальной информации. Однако прямого способа выбора дискретизации времени не существует. Существующий метод выбирает выборки времени логарифмически, что является эвристикой без гарантий ^[4]

Сложность времени

Дискретное тепловое ядро ​​требует собственного разложения матрицы размером , где — число вершин в сеточном представлении многообразия. Вычисление собственного разложения — дорогостоящая операция, особенно по мере увеличения. Однако следует отметить, что из-за обратной экспоненциальной зависимости от собственного значения обычно достаточно лишь небольшого (менее 100) собственного вектора для получения хорошего приближения HKS. ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle n}$

Неизометрические преобразования

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

Связь с другими методами

Источник: ^[2]

Кривизна

(Непрерывная) HKS в точке на римановом многообразии связана со скалярной кривизной соотношением: ${\displaystyle x}$ ${\displaystyle h_{t}(x,x)}$ ${\displaystyle s(x)}$

${\displaystyle h_{t}(x,x)={\frac {1}{4\pi t}}+{\frac {s(x)}{12\pi }}+O(t).}$

Следовательно, HKS можно интерпретировать как кривизну в масштабе . ${\displaystyle x}$ ${\displaystyle t}$

Подпись волнового ядра (WKS)

WKS ^[4] следует идее, схожей с HKS, заменяя уравнение теплопроводности волновым уравнением Шредингера ,

${\displaystyle \left(i\Delta +{\frac {\partial }{\partial t}}\right)\psi (x,t)=0}$

где - комплексная волновая функция. Средняя вероятность измерения частицы в точке определяется как, ${\displaystyle \psi (x,t)}$ ${\displaystyle x}$

${\displaystyle p(x)=\sum _{i=0}^{\infty }f^{2}(\lambda _{i})\phi _{i}^{2}(x)}$

где — начальное распределение энергии. Зафиксировав семейство этих распределений энергии , можно получить WKS как дискретную последовательность . В отличие от HKS, WKS можно представить как набор полосовых фильтров, что приводит к лучшей локализации признаков. Однако WKS не очень хорошо представляет крупномасштабные признаки (поскольку они отфильтровываются ), что приводит к низкой производительности в приложениях сопоставления форм. ${\displaystyle f}$ ${\displaystyle f_{i}(x)}$ ${\displaystyle \{p_{f_{1}}(x),\ldots ,p_{f_{n}}(x)\}}$

Глобальная точечная сигнатура (GPS)

Подобно HKS, GPS ^[5] основан на операторе Лапласа-Бельтрами. GPS в точке представляет собой вектор масштабированных собственных функций оператора Лапласа-Бельтрами, вычисленных в . GPS является глобальной функцией, тогда как масштаб HKS может изменяться путем изменения параметра времени для диффузии тепла. Следовательно, HKS может использоваться в приложениях частичного сопоставления форм, тогда как GPS не может. ${\displaystyle x}$ ${\displaystyle x}$

Спектральный граф вейвлет-сигнатура (SGWS)

SGWS ^[6] предоставляет общую форму для спектральных дескрипторов , где можно получить HKS, указав функцию фильтра. SGWS — это многомасштабный локальный дескриптор, который не только изометрически инвариантен, но и компактен, прост в вычислении и сочетает в себе преимущества как полосовых, так и низкочастотных фильтров.

Расширения

Масштабная инвариантность

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

${\displaystyle {\begin{aligned}s&=\sum _{j}A_{j}\\A&=A/s\\\lambda _{i}&=s\lambda _{i}{\text{ for each }}i\\\phi _{i}&={\sqrt {s}}\phi _{i}{\text{ for each }}i\\\end{aligned}}}$

В качестве альтернативы, масштабно-инвариантная версия HKS также может быть построена путем генерации представления масштабного пространства . ^[7] В масштабном пространстве HKS масштабированной формы соответствует переносу с точностью до мультипликативного множителя. Преобразование Фурье этого HKS изменяет временной перенос в комплексную плоскость, и зависимость от переноса может быть устранена путем рассмотрения модуля преобразования. Демонстрация масштабно-инвариантного HKS на YouTube . Альтернативный масштабно-инвариантный HKS может быть установлен путем разработки его конструкции с помощью масштабно-инвариантной метрики, как определено в. ^[8]

Объемный HKS

HKS определяется для граничной поверхности трехмерной формы, представленной как двумерное риманово многообразие. Вместо того, чтобы рассматривать только границу, можно рассматривать весь объем трехмерной формы для определения объемной версии HKS. ^[9] Объемный HKS определяется аналогично обычному HKS путем рассмотрения уравнения теплопроводности по всему объему (как 3-подмногообразия) и определения граничного условия Неймана по границе двумерного многообразия формы. Объемный HKS характеризует преобразования вплоть до объемной изометрии, которая представляет преобразование для реальных трехмерных объектов более точно, чем граничная изометрия. ^[9]

Поиск по форме

Масштабно-инвариантные признаки HKS могут использоваться в модели мешка признаков для приложений поиска форм. ^[10] Признаки используются для построения геометрических слов с учетом их пространственных отношений, из которых могут быть построены формы (аналогично использованию признаков как слов и форм как предложений). Сами формы представлены с помощью компактных двоичных кодов для формирования индексированной коллекции. При наличии формы запроса, похожие формы в индексе с возможными изометрическими преобразованиями могут быть извлечены с использованием расстояния Хэмминга кода в качестве меры близости.

Ссылки

1. Sun, J. и Ovsjanikov, M. и Guibas, L. (2009). «Краткая и доказуемо информативная многомасштабная подпись на основе диффузии тепла». Computer Graphics Forum . Том 28. С. 1383–1392.{{cite conference}}: CS1 maint: multiple names: authors list (link)
2. Александр М. Бронштейн (2011). "Спектральные дескрипторы деформируемых форм". arXiv : 1110.5015 . Bibcode :2011arXiv1110.5015B. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
3. Григорян, Александр (2006). «Heat kernels on weighted multiples and applications». Вездесущее тепловое ядро . Contemporary Mathematics. Vol. 398. Providence, RI: American Mathematical Society. pp. 93–191. doi :10.1090/conm/398/07486. MR  2218016.
4. Aubry, M. и Schlickewei, U. и Cremers, D. (2011). «Сигнатура волнового ядра — квантово-механический подход к анализу формы». Международная конференция IEEE по компьютерному зрению (ICCV) — семинар по динамическому захвату и анализу формы (4DMOD) .{{cite conference}}: CS1 maint: multiple names: authors list (link)
5. Рустамов, Р. М. (2007). «Собственные функции Лапласа–Бельтрами для представления инвариантной формы деформации». Труды пятого симпозиума Eurographics по обработке геометрии . Ассоциация Eurographics. С. 225–233.
6. C. Li; A. Ben Hamza (2013). «Многоуровневый дескриптор для поиска деформируемых трехмерных форм». The Visual Computer . 29 (6–8): 513–524. doi :10.1007/s00371-013-0815-3. S2CID  10125228.
7. Бронштейн, ММ; Коккинос, И. (2010). «Масштабно-инвариантные сигнатуры теплового ядра для распознавания нежесткой формы». Компьютерное зрение и распознавание образов (CVPR), 2010. IEEE. С. 1704–1711.
8. Афлало, Йонатан; Киммел, Рон; Равив, Дэн (2013). «Масштабно-инвариантная геометрия для нежестких форм». Журнал SIAM по визуальным наукам . 6 (3): 1579–1597. CiteSeerX 10.1.1.406.3701 . doi :10.1137/120888107. 
9. Равив, Д. и Бронштейн, М. М. и Бронштейн, А. М. и Киммел, Р. (2010). «Объемные сигнатуры теплового ядра». Труды семинара ACM по поиску трехмерных объектов . ACM. С. 30–44.{{cite conference}}: CS1 maint: multiple names: authors list (link)
10. Бронштейн, AM и Бронштейн, MM и Гибас, LJ и Овсяников, M. (2011). "Shape google: геометрические слова и выражения для поиска инвариантной формы". ACM Transactions on Graphics . 30 (1). doi :10.1145/1899404.1899405. S2CID  7964594.{{cite journal}}: CS1 maint: multiple names: authors list (link)