Нагревание подписи ядра

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

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

Обзор

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

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

Технические детали

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

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

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

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

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

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

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

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

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

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

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

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

$L=A^{-1}W$

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

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

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

Ограничения

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

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

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

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

Временная сложность

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

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

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

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

Источник:

Кривизна

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

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

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

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

ВКС следует той же идее, что и HKS, заменяя уравнение теплопроводности волновым уравнением Шредингера ,

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

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

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

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

Глобальная подпись точки (GPS)

Как и в HKS, GPS основан на операторе Лапласа-Бельтрами. GPS в точке $x$ представляет собой вектор масштабированных собственных функций оператора Лапласа – Бельтрами, вычисленный при $x$. GPS является глобальной функцией, тогда как масштаб HKS можно изменять, изменяя временной параметр диффузии тепла. Следовательно, HKS можно использовать в приложениях частичного сопоставления форм, тогда как GPS — нет.

Вейвлет-подпись спектрального графа (SGWS)

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

Расширения

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

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

${\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 также может быть создана путем создания представления масштабного пространства . В масштабном пространстве HKS масштабированной формы соответствует сдвигу с точностью до мультипликативного коэффициента. Преобразование Фурье этого HKS изменяет перевод времени в комплексную плоскость, и зависимость от перевода можно устранить, рассмотрев модуль преобразования. Демонстрация масштабно-инвариантного HKS на YouTube . Альтернативный масштабно-инвариантный HKS может быть установлен путем разработки его конструкции с помощью масштабно-инвариантной метрики, как определено в .

Объемный ХКС

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

Поиск формы

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