LSH (Locality-Sensitive Hashing)

지역성 민감 해싱(Locality-Sensitive Hashing, LSH)은 단순한 아이디어에 기반한 근사 최근접 이웃 검색 기법입니다: **비슷한 디스크립터가 충돌(같은 버킷에 들어감)**할 확률이 높고, 다른 디스크립터가 충돌할 확률은 낮도록 디스크립터를 해시합니다. 그러면 질의는 전체 데이터베이스가 아니라 자신의 버킷 안에 있는 몇 개의 후보와만 비교하면 됩니다.

지역성 민감 속성

거리 함수 $d(\cdot,\cdot)$ 에 대해, 해시 함수 집합 $\mathcal{H}$ 가 $(r, cr, p_1, p_2)$ -민감(sensitive)하다는 것은 임의의 두 점 $\mathbf{p}, \mathbf{q}$ 에 대해:

$d(\mathbf{p}, \mathbf{q}) \leq r$ 이면 $\Pr[h(\mathbf{p}) = h(\mathbf{q})] \geq p_1$ ,
$d(\mathbf{p}, \mathbf{q}) \geq cr$ 이면 $\Pr[h(\mathbf{p}) = h(\mathbf{q})] \leq p_2$ ,

가 $p_1 > p_2$ 이고 $c > 1$ 일 때 성립함을 의미합니다. 즉, 가까운 점은 충돌할 가능성이 높고, 먼 점은 충돌할 가능성이 낮습니다.

해밍 거리를 사용하는 이진 디스크립터(ORB, BRIEF, AKAZE의 MLDB)의 경우, 자연스러운 함수 집합은 **비트 샘플링(bit sampling)**입니다: 무작위로 선택한 비트 위치 $i$ 에 대해 $h(\mathbf{x}) = x_i$ 입니다. 길이 $n$ 인 두 디스크립터가 $d_H$ 개의 비트에서 다를 때 충돌 확률은

\Pr[h(\mathbf{p}) = h(\mathbf{q})] = 1 - \frac{d_H(\mathbf{p}, \mathbf{q})}{n}

이며, 거리에 정확히 반비례하여 감소합니다 — 지역성 민감 속성이 공짜로 얻어집니다.

증폭: k비트, L테이블

단일 무작위 비트는 매우 약한 해시이므로, LSH는 두 방향으로 이를 증폭합니다:

결합(AND): $k$ 개의 해시 함수로 각 테이블의 키를 구성합니다, $g(\mathbf{x}) = (h_1(\mathbf{x}), \dots, h_k(\mathbf{x}))$ . 한 테이블의 충돌 확률은 $(1 - d_H/n)^k$ 가 됩니다 — $k$ 가 커지면 버킷이 더 작아지고 더 선택적이 되어 거짓 양성(false positive)이 줄어듭니다.
다중 테이블(OR): $L$ 개의 독립적인 테이블을 만들고 모두를 조회합니다. 참 이웃이 적어도 하나의 테이블에서 충돌할 확률은

P = 1 - \left(1 - \left(1 - \frac{d_H}{n}\right)^{k}\right)^{L}

$k$ 와 $L$ 을 조율하면 정확도와 속도/메모리 사이의 트레이드오프가 만들어집니다: 선택적인 키(큰 $k$ )는 재현율(recall)을 유지하기 위해 많은 테이블(큰 $L$ )이 필요합니다.

Multi-probe LSH

표준 LSH는 좋은 재현율을 얻기 위해 많은 해시 테이블이 필요한데, 이는 메모리를 많이 소모합니다. Multi-probe LSH는 참 이웃이 질의의 버킷을 놓쳤다면, 대개 키가 몇 개의 위치에서만 다른 근처 버킷에 들어갔을 것이라는 점에 주목합니다. 테이블을 더 추가하는 대신, multi-probe 질의는 (키의 비트 하나를 뒤집고, 그다음 두 개를 뒤집는 등) 이웃을 포함할 가능성 순으로 정렬된 *탐색 시퀀스(probing sequence)*의 섭동된 키들을 생성하고, 동일한 테이블 내에서 그 추가 버킷들을 검사합니다. 이는 쿼리당 더 많은 탐색이 필요한 대신, 몇 배 더 적은 테이블로 비슷한 재현율을 달성합니다. OpenCV의 FLANN 기반 LSH 인덱스는 정확히 이러한 조절 항목들을 제공합니다: 테이블 수, 키 크기 $k$ , multi-probe 레벨입니다.

SLAM에서의 의미

특징점 기반 SLAM 시스템은 프레임당 수천 개의 이진 디스크립터를 생성하고, 이를 수백만 개를 담고 있는 맵이나 키프레임 데이터베이스와 매칭해야 합니다. 브루트 포스 매칭은 정확하지만 $O(nm)$ 으로 확장되며, kd-트리는 고차원 이진 데이터에 대해 심각하게 성능이 저하됩니다. LSH는 이진 디스크립터에 대한 표준적인 해답이며 — FLANN이 ORB/BRIEF 데이터에 대해 선택하는 방식이며 — 질의 디스크립터 집합이 밀리초 단위로 큰 맵과 매칭되어야 하는 빠른 재위치추정과 루프 클로저 후보 검색을 지원합니다. $k$ / $L$ /multi-probe 트레이드오프를 이해하면 플랫폼에 맞게 재현율 대 지연 시간을 조율할 수 있습니다.

LSH (Locality-Sensitive Hashing)

지역성 민감 속성

증폭: k비트, L테이블

Multi-probe LSH

SLAM에서의 의미

관련 문서