기하학적 해싱

컴퓨터 과학에서 기하학적 해싱은 다른 물체 표현과 변환에 대한 확장이 존재하지만, 아핀 변환을 거친 이산 점으로 대표되는 2차원 물체를 효율적으로 찾는 방법이다.오프라인 단계에서는 각 점 쌍을 기하학적 기준으로 처리하여 사물을 암호화한다.나머지 포인트는 두 파라미터를 사용하여 이 기준에 관하여 불변적인 방식으로 나타낼 수 있다.각 점에 대해 정량화된 변환 좌표는 해시 표에 키로 저장되며, 기본 점의 지수는 값으로 저장된다.그런 다음 새 기준점 쌍을 선택하고 프로세스를 반복한다.온라인(인식) 단계에서는 무작위로 선택한 데이터 포인트 쌍을 후보 기반으로 간주한다.각 후보별로, 나머지 데이터 포인트는 근거에 따라 인코딩되며, 오브젝트로부터의 가능한 서신은 이전에 구성된 표에서 찾을 수 있다.충분한 수의 데이터 포인트가 일관된 객체 베이스를 인덱싱할 경우 후보 기준이 허용된다.

기하학적 해싱은 원래 2D와 3D의 물체 인식을 위한 컴퓨터 시야에서 제시되었으나,^[1] 이후 단백질의 구조적 정렬 등 다른 문제에 적용되었다.^[2][3]

컴퓨터 시력의 기하학적 해싱

기하학적 해싱은 물체 인식에 사용되는 방법이다.모델 이미지가 입력 이미지에서 보여질 수 있는지 확인하고 싶다고 합시다.이것은 기하학적 해싱으로 이루어질 수 있다.이 방법은 베이스에 있는 여러 개체 중 하나를 인식하는 데 사용될 수 있는데, 이 경우 해시 테이블은 포즈 정보뿐만 아니라 베이스에 객체 모델의 인덱스도 저장해야 한다.

예

단순성을 위해, 이 예는 너무 많은 포인트 기능을 사용하지 않을 것이며, 그들의 설명자가 좌표에 의해서만 주어진다고 가정한다(실제로 SIFT와 같은 로컬 설명자는 인덱싱에 사용될 수 있다).

교육 단계

1. 모델의 피쳐 포인트를 찾으십시오.Assume that 5 feature points are found in the model image with the coordinates ${\displaystyle (12,17);}$${\displaystyle (45,13);}$${\displaystyle (40,46);}$${\displaystyle (20,35);}$${\displaystyle (35,25)}$, see the picture.
2. 피쳐 포인트의 위치를 설명하는 근거를 소개하십시오.2D 공간 및 유사성 변환의 경우 기본은 점 쌍으로 정의된다.출발점은 두 점(P2, 본 예에서는 P4)을 연결하는 세그먼트 중간에 위치하며, $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$축은$$ 그 중 하나를 향하며, $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은 직교하여$$ 원점을 통과한다.척도는 두 기준점에 $대한{\displaystyle {}^{}}$ x$$ ${\displaystyle {\prime }^{}}${\$displaystyle$x'}의 절대값이 1이 되도록 선택된다.
3. 해당 기준에 대한 형상 위치를 설명하십시오. 즉, 새 좌표 축에 대한 투영을 계산하십시오.좌표는 노이즈에 따라 견고하게 인식될 수 있도록 식별되어야 하며, 빈 사이즈는 0.25이다.We thus get the coordinates ${\displaystyle (-0.75,-1.25);}$${\displaystyle (1.00,0.00);}$${\displaystyle (-0.50,1.25);}$${\displaystyle (-1.00,0.00);}$${\displaystyle (0.00,0.25)}$
4. 형상에 의해 인덱싱된 해시 테이블에 기초를 저장한다(이 경우 변환된 좌표만).일치시킬 개체가 더 많았다면 기본 쌍과 함께 개체 번호도 함께 저장해야 한다.
5. 다른 기본 쌍(2단계)에 대해 프로세스를 반복하십시오.혼선을 처리할 필요가 있다.이상적으로는 모든 비색인 쌍을 열거해야 한다.우리는 두 번 반복한 후에 해시 테이블을 제공하며, 두 번째 해시 테이블은 쌍(P1, P3)이 선택된다.

해시 테이블:

벡터(${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$	기본
${\디스플레이 스타일(-0.75,-1.25);}$	(P2,P4)
$(\displaystyle(1.00,0.00);}$	(P2,P4)
${\디스플레이 스타일(-0.50,1.25);}$	(P2,P4)
$(\디스플레이 스타일(-1.00,0.00);}$	(P2,P4)
${\displaystyle(0.00,0.25)}$	(P2,P4)
$(\displaystyle(1.00,0.00);}$	(P1,P3)
${\displaystyle(0.00,1.25);}$	(P1,P3)
$(\디스플레이 스타일(-1.00,0.00);}$	(P1,P3)
$(0.00,-0.25);}$	(P1,P3)
${\displaystyle(0.00,0.50)}$	(P1,P3)

대부분의 해시 테이블은 다른 값에 매핑된 동일한 키를 가질 수 없다.그래서 실제 생활에서는 기본 키(1.0, 0.0)와 (-1.0, 0.0)를 해시 테이블에 인코딩하지 않는다.

인식 단계

1. 입력 이미지에서 흥미로운 피쳐 포인트를 찾으십시오.
2. 임의의 기준을 선택하십시오.적절한 임의의 기준이 없는 경우 입력 이미지에 대상 개체가 포함되지 않을 가능성이 높다.
3. 형상점의 좌표를 새로운 기준으로 설명하십시오.이전과 같이 얻은 좌표를 정량화한다.
4. 입력 이미지의 변환된 모든 포인트 피쳐를 해시 테이블과 비교하십시오.점 형상이 동일하거나 유사한 경우 해당 기준(그리고 개체 유형(있는 경우)에 대한 카운트를 늘리십시오.
5. 카운트가 특정 임계값을 초과하도록 각 기준에 대해 2단계에서 선택한 영상 기준에 해당한다는 가설을 확인하십시오.영상 좌표계를 모델 1(예상된 객체에 대해)로 전송하고 일치시키십시오.성공하면 객체가 발견된다.그렇지 않으면 2단계로 돌아가십시오.

미러링된 패턴 찾기

이 방법은 스케일링과 번역, 회전만 할 수 있는 것으로 보인다.그러나 입력 이미지는 미러 변환의 개체를 포함할 수 있다.그러므로 기하학적 해싱도 그 물체를 찾을 수 있어야 한다.거울에 비친 물체를 감지하는 방법에는 두 가지가 있다.

1. 벡터 그래프의 경우 왼쪽을 양으로, 오른쪽을 음으로 만든다.x 위치에 -1을 곱하면 같은 결과가 나온다.
2. 기본은 3점을 사용한다.이를 통해 미러 이미지(또는 개체)를 탐지할 수 있다.사실, 3개의 점을 기본으로 사용하는 것은 기하학적 해싱에 대한 또 다른 접근법이다.

고차원 기하학적 해싱

위의 예와 유사하게 해싱은 고차원 데이터에 적용된다.3차원 데이터 점의 경우, 기초에 대해서도 3개의 점이 필요하다.처음 두 점은 X축을 정의하고, 세 번째 점은 Y축을 정의한다(첫 번째 점으로).z축은 오른쪽 규칙을 사용하여 생성된 축과 수직이다.점의 순서가 결과 기준에 영향을 미친다는 점에 유의하십시오.

참고 항목

• 지각 해싱

참조

• 울프슨, H.J. & 리구토스, I (1997년)기하학적 해싱: 개요.IEEE 계산 과학 및 엔지니어링, 4(4), 10-21.