기하학적 해싱(Geometric hashing)은 컴퓨터 비전과 패턴 인식에서 사용되는 방법으로, 장면 내 객체를 식별하기 위해 기하학적 특징을 사전 계산된 데이터베이스와 대조하는 기법이다. 이 방법은 1980년대 후반 예헤즈켈 람단(Yehezkel Lamdan)과 하임 J. 울프슨(Haim J. Wolfson)에 의해 개발되었으며, 모델 기반 객체 인식 분야에서 영향력을 발휘했다. 이 기법은 부분적인 폐색을 처리하는 능력과 일반적인 기하학적 변환에 대한 불변성으로 주목받았으며, 초기 템플릿 매칭 접근법에 비해 강건한 대안을 제공했다.
기하학적 해싱의 핵심 아이디어는 각 객체 모델을 특징점(모서리, 가장자리, 관심점 등)의 집합으로 표현하고, 이들의 공간적 관계를 해시 테이블에 인코딩하는 것이다. 인식 단계에서는 쿼리 장면에서 특징점을 추출하고, 해시 테이블을 사용하여 후보 모델에 투표한다. 이 투표 과정을 통해 시스템은 객체의 특징 중 일부만 보이는 경우에도 어떤 모델이 존재할 수 있는지 빠르게 가설을 세울 수 있다.
역사적 발전
기하학적 해싱은 1980년대 계산 기하학과 컴퓨터 비전 연구에서 등장했다. 람단과 울프슨은 1988년 IEEE 국제 컴퓨터 비전 회의에서 발표된 "기하학적 해싱: 일반적이고 효율적인 모델 기반 인식 기법"이라는 논문에서 이 개념을 소개했다. 이 접근법은 해싱과 기하학적 매칭에 대한 초기 연구를 기반으로 했지만, 모델 특징을 인덱싱하는 새로운 방식을 도입하여 인식을 빠르고 노이즈에 강건하게 만들었다.
이 기법은 1990년대에 산업용 부품 검사, 로봇 공학, 의료 영상과 같은 응용 분야에서 주목을 받았다. 또한 분자 생물학에서 단백질 구조 비교를 위해 적응되었으며, 여기서 원자나 잔기의 기하학적 배열을 서로 다른 분자 간에 대조할 수 있었다. 2020년대 초반 기준으로 기하학적 해싱은 컴퓨터 비전의 기초 개념으로 남아 있지만, 많은 실제 응용 분야에서 딥러닝 기반 방법으로 대체되었다.
알고리즘 개요
기하학적 해싱 알고리즘은 전처리와 인식의 두 단계로 작동한다. 전처리 단계에서는 데이터베이스의 각 모델에 대해 특징점 집합을 추출한다. 각 점의 순서쌍(또는 기준점, 일반적으로 좌표 프레임을 정의하는 두 점)에 대해 알고리즘은 해당 기준점을 기준으로 한 다른 모든 점의 좌표를 계산한다. 이러한 상대 좌표는 해시 테이블에 저장되며, 기준점과 모델 식별자가 연관 값으로 사용된다.
인식 단계에서는 장면의 특징점을 추출하고, 알고리즘은 무작위 점 쌍을 후보 기준점으로 선택한다. 이 기준점을 사용하여 나머지 장면 점의 상대 좌표를 계산하고 해시 테이블에서 조회한다. 각 일치는 해당 모델과 기준점에 대한 투표를 증가시킨다. 모든 가능한 기준점(또는 샘플링된 하위 집합)을 처리한 후, 가장 높은 투표 수를 가진 모델이 최적의 일치로 선택된다. 그런 다음 알고리즘은 모델을 장면에 정렬하고 일관성을 확인하여 일치를 검증한다.
이 접근법은 상대 좌표가 정규화된 프레임에서 계산되므로 이동, 회전, 균일 스케일링에 불변하다. 또한 모델의 특징 중 일부만 장면에 존재해도 충분한 투표가 누적될 수 있으므로 부분적인 폐색을 처리한다.
컴퓨터 비전에서의 응용
기하학적 해싱은 강건한 객체 인식이 필요한 여러 분야에 적용되었다. 산업 자동화에서는 기준 참조에 대해 회전하거나 스케일링된 부품을 컨베이어 벨트에서 찾는 데 사용되었다. 로봇 공학에서는 로봇이 복잡한 환경에서 객체를 식별하고 파악하는 데 도움을 주었다. 폐색에 대한 내성 덕분에 더미 속에 부분적으로 숨겨진 객체를 인식하는 작업에 적합했다.
의료 영상에서는 X-ray나 MRI 이미지에서 해부학적 구조를 정렬하는 데 사용되어 이미지 등록과 수술 계획과 같은 작업을 지원했다. 분자 생물학에서는 단백질 3D 구조 비교를 용이하게 했으며, 아미노산 서열의 차이에도 불구하고 유사한 접힘 패턴을 찾는 것이 목표였다. 이러한 응용 분야는 개별 점 간의 명시적 대응 없이 기하학적 구성을 매칭하는 기법의 능력을 활용했다.
현대 접근법과의 비교
2010년대 Machine learning과 Deep learning의 부상으로 기하학적 해싱은 주류 컴퓨터 비전에서 덜 두드러지게 되었다. Neural network 아키텍처, 특히 Convolutional neural network와 Transformer (architecture) 모델 기반 방법은 대규모 인식 작업에서 더 높은 정확도를 달성했다. 이러한 현대적 접근법은 데이터에서 직접 특징 표현을 학습하는 반면, 기하학적 해싱은 수작업으로 설계된 기하학적 특징과 명시적 공간 인덱싱에 의존한다.
그러나 기하학적 해싱은 특정 시나리오에서 여전히 장점을 제공한다. 광범위한 훈련 데이터가 필요하지 않아 객체의 예시가 몇 개뿐인 경우 유용하다. 또한 투표 과정이 인식에 기여한 특징을 드러내므로 해석 가능한 매칭 결과를 제공한다. 반면 딥러닝 모델은 종종 블랙박스로 작동한다. 2020년대 중반 기준으로 특징 추출을 위해 기하학적 해싱과 Machine learning을 결합한 하이브리드 접근법이 탐구되었지만, 여전히 틈새 시장에 머물러 있다.
한계와 확장
기하학적 해싱의 한계 중 하나는 특징점 추출 품질에 대한 민감성이다. 특징 검출기가 노이즈가 많거나 불일치하는 점을 생성하면 해시 테이블 조회가 신뢰할 수 없게 된다. 또한 알고리즘은 모델 수가 증가함에 따라 확장성이 떨어지며, 해시 테이블이 커지고 메모리 집약적이 될 수 있다. 이를 해결하기 위해 무작위 기준점이나 계층적 해싱을 사용하여 탐색 공간을 줄이는 확장이 제안되었다.
또 다른 확장은 유사 변환 대신 아핀 또는 투영 변환을 사용하는 것으로, 적용 가능한 시나리오의 범위를 넓힌다. 일부 변형은 기하학적 특징과 함께 색상이나 질감 정보를 통합하여 판별력을 향상시킨다. 이러한 개선에도 불구하고 속도와 강건성 사이의 근본적인 균형은 여전히 과제로 남아 있으며, 이 기법은 현대 시스템에서 Data Augmentation 기반 훈련과 같은 다른 방법과 결합하여 사용되는 경우가 많다.
유산과 영향
기하학적 해싱은 대규모 이미지 검색에서 해싱의 사용과 SIFT(Scale-Invariant Feature Transform)와 같은 로컬 특징 기술자의 설계를 포함한 컴퓨터 비전의 후속 발전에 영향을 미쳤다. 기하학적 불변량을 해시 테이블에 인덱싱하는 아이디어는 이후 많은 알고리즘에서 볼 수 있다. 또한 기하학적 추론이 계산 시스템에서 효율적으로 구현될 수 있음을 보여줌으로써 Artificial intelligence의 더 넓은 분야에 기여했다.
오늘날 기하학적 해싱은 컴퓨터 비전 과정에서 모델 기반 인식의 고전적인 예로 가르쳐진다. 그 원리는 포인트 클라우드의 3D 객체 인식과 컴퓨터 지원 설계의 형상 매칭과 같은 특수 응용 분야에서 여전히 관련이 있다. 더 이상 이 분야를 지배하지는 않지만, 그 개념적 기여는 Artificial intelligence와 패턴 인식 역사의 중요한 부분으로 남아 있다.