Подпись теплового ядра

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

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

Обзор [ править ]

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

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

Технические детали [ править ]

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

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

где - оператор Лапласа – Бельтрами, а - распределение тепла в момент времени . Решение этого уравнения может быть выражено как, ^[1]${\ displaystyle \ Delta}$${\ Displaystyle и (х, т)}$${\ 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-подмногообразие) и определения граничного условия Неймана над границей 2-многообразия формы. Объемный HKS характеризует преобразования вплоть до объемной изометрии, которые представляют преобразование для реальных трехмерных объектов более точно, чем изометрия границ. ^[9]

Поиск формы [ править ]

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

Ссылки [ править ]