열 커널 시그니처

열 커널 시그니처(HKS)는 변형 형상 분석에 사용하기 위한 형상 설명자로 스펙트럼 형상 분석 방법 그룹에 속한다.형상의 각 점에 대해 HKS는 점의 로컬 및 글로벌 기하학적 특성을 나타내는 형상 벡터를 정의한다.응용 프로그램에는 분할, 분류, 구조 탐색, 형상 일치 및 형상 검색이 포함된다.

HKS는 2009년 지안 선, 막스 오브자니코프, 레오니다스 기바스가 도입했다.^[1]그것은 열 방정식의 근본적인 해결책인 열 커널을 기반으로 한다.HKS는 모양과 관련된 라플라스-벨트라미 연산자를 기반으로 최근에 소개된 모양 설명자 중 하나이다.^[2]

개요

형상 분석은 형상 자동 디지털 분석 분야(예: 3D 객체)이다.많은 형상 분석 작업(예: 형상 일치/반복)의 경우 형상의 전체 3D 모델을 사용하는 대신 특정 키 포인트에 대한 형상 벡터를 사용한다.그러한 특징 설명자의 중요한 요구사항은 특정 변환에서 불변성이라는 것이다.경직된 변환의 경우 일반적으로 사용되는 형상 설명자에는 형상 컨텍스트, 스핀 이미지, 통합 볼륨 설명자 및 멀티스케일 로컬 기능이 포함된다.^[2]HKS는 경직된 변환을 일반화하는 등축 변환을 허용한다.

HKS는 표면에 열 확산의 개념을 기반으로 한다.표면에서$$ 초기 열 분포 ${\displaystyle u}$ 0${\displaystyle {}_{}}$( x${\displaystyle }$) ${\displaystyle u_{0}(x)}$이(가) 있을 경우, 열 커널 h ${\displaystyle t_{}x}$, y${\displaystyle }$) ${\$$displaystyle h_$${t}(x,y)}}$은 시간 $t{\displaystyle }$ ${\displaystyt}$ 이후$$ $x$에서 $}($으$)$로 전달된 열량을 연관시킨다$.$열 알맹이는 등축변환 하에서 불변하며 등축에 대한 작은 동요에서도 안정적이다.^[1]또한, 열 알맹이는 형상을 등각계까지 완전히 특성화하고 시간이 지날수록 형상의 전지구적 특성을 나타낸다.^[3]$h{\displaystyle {}_{}}$ ${\displaystyle t_{}}$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle h_{t}(x,y)}$이(가) 임시 영역을 넘는 점 쌍에 대해 정의되므로$$ 열 커널을 특징으로 직접 사용하면 복잡성이 높아진다.HKS는 대신 h ${\displaystyle t_{}}$( ${\displaystyle x}$, ${\displaystyle x}$) ${\displaystyle h_{t}(x,x)}$만을 고려하여 시간적 영역에만 국한된다$.$ HKS는 특정 조건에서 열 커널의 대부분의 속성을 상속한다.^[1]

기술적 세부사항

콤팩트한 리만 $다지관{\displaystyle }$ M ${\displaystyle M}($경계가 있을 가능성이 있음)에 대한 열 확산 방정식은 다음과 같다.

${\displaystyle \왼쪽(\Delta -{\frac {\partial }{\partial t}\오른쪽)u(x,t)=0}$

여기서 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta}$은(는) Laplace-Beltami 연산자이고 $u{\displaystyle (x}$ ,$$t${\displaystyle }$) {\$displaystyle u(x,$t$$)}은$$ 시간$$t {\$displaystyty$ t$}$의 점 $x{\displaystyle }$ ${\displaystystyle x}$에서의 열 분포이다$.$이 방정식의 해법은 다음과 같이 표현할 수 있다.^[1]

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

열 낟알의 고유 분해는 다음과 같이 표현된다.

${\displaystyle h_{t}(x,y)=\sum _{i=0}^{\inful }\expenda _{i}t)\phi _{i}\phi _{i}(y)}$

${\displaystyle {\mathrm{여기}}^{}}$서 $\lambda {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ $\$$lambda$ $_{i}$ 및$$ $\varphi {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$}}$$$\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta}$의 $고유값$ 및 고유함수인$$ heat it h {\displaystyle \Delta}. 열 커널은 표면의 특성을 등계까지 완전하게 나타낸다$.$모든 돌출 지도 ${\displaystyle T}$: ${\displaystyle M}$→ N ${\displaystyle T:$$M\rightarrow N}$ between two Riemannian manifolds ${\displaystyle M}$ and ${\displaystyle N}$, if ${\displaystyle h_{t}(x,y)=h_{t}(T(x),T(y))}$ then ${\displaystyle T}$ is an isometry, and vice versa.^[1]간결한 피쳐 설명자의 경우 HKS는 열 커널을 임시 도메인으로만 제한한다.

${\displaystyle h_{t}(x,x)=\sum _{i=0}^{\inful }\exput\da _{i}t)\phi _{i}^{2}(x).}$

HKS는 열 커널과 유사하게 $M{\displaystyle }$ ${\displaystyle M}$ 및$$ $N{\displaystyle }$ ${\displaystyle N}$에 대한 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$의 고유값이 비반복적이라는$$ 조건에서 표면을 특성화한다.${\displaystyle \exp }$ (${\displaystyle }$- ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle \exp(-\lambda _{i})$용어는 컷오프 주파수를 결정하는$$ $\lambda {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 로패스 필터 뱅크로서 직관할 수 있다$$.^[2]

현실적 고려

Since ${\displaystyle h_{t}(x,x)}$ is, in general, a non-parametric continuous function, HKS is in practice represented as a discrete sequence of ${\displaystyle \{h_{t_{1}}(x,x),\ldots ,h_{t_{n}}(x,x)\}}$ values sampled at times ${\di$$splaystyle t_{1},\ldots,t_{n$

대부분의 용도에서, 물체의 기저 다지관은 알려져 있지 않다.HKS는 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$에 대한 이산 근사치 및 열$$ 방정식의 이산 아날로그를 사용하여 다지관의 망사 표현을 사용할 수 있는지 계산할 수 있다.이산형 사례에서 라플라스-벨트라미 연산자는 희박한 행렬이며 다음과 같이 쓸 수 있다.^[1]

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

여기서 ${\displaystyle A}$은(는${\displaystyle )}$ 정점 $i{\displaystyle }$ ${\displaystyle i}$및 $W{\displaystyle }$ ${\displaystyle$W}을(를) 공유하는 메쉬의 삼각형 영역에 해당하는$$ $항목{\displaystyle }$ A$($를 포함하는 양의 대각 행렬이며, W {\displaystyle W$}$은 대칭 반정확한 가중 행렬이다.${\displaystyle L}$ can be decomposed into ${\displaystyle L=\Phi \Lambda \Phi ^{T}A}$, where ${\displaystyle \Lambda }$ is a diagonal matrix of the eigenvalues of ${\displaystyle L}$ arranged in the ascending order, and ${\displaystyle \Phi }$ is the matrix with the corresponding orthonormal고유 벡터이산 열 낟알은 매트릭스에 의해 주어진다.

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

요소 k $t{\displaystyle {}_{}}$ (${\displaystyle {}_{}{i}_{}}$ ,${\displaystyle j}$ )${\displaystyle k_{t}(i,j)$는 시간$$ $t{\displaystyle }$ ${\displaystyle$ $i}$과 j ${\displaystyle$ $j}$ 사이의 열 확산 시간을 나타낸다$.$HKS는 이 행렬의 대각선 항목으로 제공되며, 별도의 시간 간격으로 샘플링된다.연속 케이스와 유사하게 이산 HKS는 노이즈에 강하다.^[1]

제한 사항

비반복 고유값

HKS를 사용하여 최대 이등계까지 표면을 특징짓는 주요 특성은 표면의 고유값이 반복되지 않을 때만 유지된다.이 조건을 위반하는 특정 표면(특히 대칭이 있는 표면)이 있다.구체는 그러한 표면의 단순한 예다.

시간 매개변수 선택

HKS의 시간 매개변수는 글로벌 정보의 규모와 밀접한 관련이 있다.다만 시간 탈피 방식을 직접 선택할 수 있는 방법은 없다.기존 방법은 시간표본을 로그로 선택하는데, 이는 보증이^[4] 없는 경험적 휴리스틱이다.

시간 복잡성

이산형 열 커널은 $크기{\displaystyle }$ n${\displaystyle }$× ${\displaystyle n}$ ${\displaystyle n\times n}$의 매트릭스 구성을 필요로 하며$,$ $여기$서 n ${\displaystyle n}$은 다지관의 망사 표현에 있는 정점의 수입니다.특히 $n{\displaystyle }$ ${\displaystyle n}$이(가) 증가함에 따라 eigende composition을 계산하는 것은 비용이 많이 드는 작업이다.그러나 고유값에 대한 역 지수적 의존성 때문에 일반적으로 작은(100 미만) 고유 벡터만 HKS의 좋은 근사치를 얻기에 충분하다는 점에 유의하십시오.

비 등축 변환

HKS에 대한 성능 보증은 진정한 등축 변환에 대해서만 유효하다.그러나 실제 형상의 변형은 등축이 아닌 경우가 많다.그러한 변형의 간단한 예는 두 손가락 사이의 지오데틱 거리가 변하는 사람에 의한 주먹의 닫힘이다.

다른 방법과의^[2] 관계

곡률

리만 매니폴드의 점 $x{\displaystyle }$$$$${\$displaystyle x$ $h{\displaystyle {}_{}}$ ${\displaystyle t_{}x}$, ${\displaystyle x}$) ${\displaystyle h_{t}(x,x)}$에 있는 (연속) HKS는 스칼라 $곡률{\displaystyle }$ s${\displaystyle }$(${\displaystyle x}$) ${\displaystyle$ s$(x)}$ by$$,

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

따라서 HKS는 척도 $t{\displaystyle }$ ${\displaystyle t}$에서 x ${\displaystyle x}$의 곡률로 해석할 수 있다$.$

WKS(Wave 커널 서명)

WKS는^[4] 열 방정식을 슈뢰딩거 파동 방정식으로 대체하면서 HKS와 유사한 아이디어를 따른다.

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

여기서 $\psi {\displaystyle }$( ${\displaystyle x}$, t${\displaystyle }$) ${\displaystyle \psi (x,t)}$은 복잡한 파형 함수다.점$$ $x{\displaystyle }$ ${\displaystyle x}$에서 입자를 측정할 평균 확률은 다음과 같다.

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

여기서 $f{\displaystyle }$ ${\displaystyle f}$은(는) 초기 에너지 분배다.By fixing a family of these energy distributions ${\displaystyle f_{i}(x)}$, the WKS can be obtained as a discrete sequence ${\displaystyle \{p_{f_{1}}(x),\ldots ,p_{f_{n}}(x)\}}$. Unlike HKS, the WKS can be intuited as a set of band-pass filters leading to better feature국산화그러나 WKS는 형상 일치 애플리케이션에서 저조한 성능을 내는 대규모 형상을 잘 나타내지 않는다.

글로벌 포인트 시그니처(GPS)

HKS와 유사하게^[5] GPS는 라플라스-벨트라미 운영자를 기반으로 한다.지점 $x{\displaystyle }$ ${\displaystyle x}$의 GPS는 $x{\displaystyle }$ ${\displaystyle$ x$}$에서 계산된 라플라스-벨트라미 연산자의 스케일 조정 고유 기능의 벡터다$.$GPS는 전지구적 특징인 반면에 HKS의 척도는 열 확산에 대한 시간 매개변수를 변화시킴으로써 변화될 수 있다.따라서, HKS는 GPS는 사용할 수 없는 반면 부분적인 형태 일치 어플리케이션에 사용될 수 있다.

스펙트럼 그래프 파장 시그니처(SGWS)

SGWS는^[6] 필터 기능을 지정해 HKS를 얻을 수 있는 스펙트럼 설명자의 일반적인 형태를 제공한다.SGWS는 등축 불변성뿐만 아니라 컴팩트하고 계산하기 쉬운 멀티솔루션 로컬 설명자로 대역 통과 필터와 로우패스 필터 모두의 장점을 결합한 것이다.

확장

척도 불변도

HKS는 여러 척도로 모양을 나타내지만 본질적으로 척도가 불변하는 것은 아니다.예를 들어 형상 모형의 HKS와 형상 모형의 축척 버전은 사전 정규화 없이는 동일하지 않다.척도 불변성을 보장하는 간단한 방법은 동일한 표면적(예: 1)을 갖도록 각 형상을 사전 스케일링하는 것이다.위의 표기법을 사용하여, 이는 다음을 의미한다.

${\displaystyle}s&=\sum _{j}A_{j}\\\A&\s\\lambda _{i}\\lambda _{i}{{i}\\\phi _{s}}\sqrt{s}}}{i}{i\\ended}}}}}}}}별 {i}$

또는, HKS의 스케일 인바리어트 버전도 스케일 공간 표현을 생성하여 구성할 수 있다.^[7]축척 공간에서 축척 모양의 HKS는 최대 곱셈 인자에 해당하는 번역에 해당한다.이 HKS의 푸리에 변환은 시간 변환을 복잡한 평면으로 변화시키며, 변환의 계수를 고려하여 번역에 대한 의존성을 제거할 수 있다.YouTube에서 Scale invariant HKS 데모.대체 척도 불변 HKS는 정의한 척도 불변계측정을 통해 구성을 수행함으로써 확립될 수 있다.^[8]

부피 HKS

HKS는 2D 리만 다지관으로 표현되는 3D 형태의 경계면에 대해 정의된다.경계만 고려하는 것이 아니라 3D 형상의 전체 볼륨이 HKS의 부피 버전을 정의하는 것을 고려할 수 있다.^[9]Volumetric HKS는 전체 부피에 대한 열 방정식(3-submanifold)을 고려하고 형상의 2-manifold 경계 위에 Neumann 경계 조건을 정의함으로써 일반 HKS와 유사하게 정의된다.부피 측정 HKS는 볼륨 등각도까지 변형을 특징으로 하며, 이는 경계 등각보다 실제 3D 물체의 변형을 더 충실히 표현한다.^[9]

모양 검색

스케일 인바리어트 HKS 기능은 형상 검색 응용을 위한 백 오브 피쳐 모델에서 사용할 수 있다.^[10]형상은 형상을 구성할 수 있는 공간적 관계(형상을 문장으로 사용하는 것과 유사함)를 고려하여 기하학적 단어를 구성하는 데 사용된다.도형 자체는 인덱싱된 컬렉션을 형성하기 위해 콤팩트한 이진 코드를 사용하여 표현된다.쿼리 모양이 지정되면 코드의 해밍 거리를 근거리 측정으로 사용하여 등축 변환 가능성이 있는 인덱스의 유사한 형상을 검색할 수 있다.

참조