기하학적 해싱: 이미지 인식 및 매칭을 위한 효율적인 알고리즘

By Fouad Sabry

기하학적 해싱이란

컴퓨터 과학에서 기하학적 해싱은 확장을 통해 아핀 변환을 거친 개별 점으로 표현된 2차원 개체를 효율적으로 찾는 방법입니다. 다른 객체 표현 및 변환에도 존재합니다. 오프라인 단계에서 객체는 각 점 쌍을 기하학적 기반으로 처리하여 인코딩됩니다. 나머지 점은 두 개의 매개변수를 사용하여 이 기준에 대해 불변 방식으로 표현될 수 있습니다. 각 포인트에 대해 양자화 변환된 좌표는 해시 테이블에 키로 저장되고 기본 포인트의 인덱스는 값으로 저장됩니다. 그런 다음 새로운 기준점 쌍이 선택되고 프로세스가 반복됩니다. 온라인(인식) 단계에서는 무작위로 선택된 데이터 포인트 쌍이 후보 베이스로 간주됩니다. 각 후보 베이시스에 대해 나머지 데이터 포인트는 베이시스에 따라 인코딩되며 개체의 가능한 대응 관계는 이전에 구성된 테이블에서 찾습니다. 충분히 많은 수의 데이터 포인트가 일관된 개체 기반을 색인화하는 경우 후보 기반이 허용됩니다.

혜택을 받는 방법

(I) 통찰력, 및 다음 주제에 대한 검증:

1장: 기하학적 해싱

2장: 분석 기하학

3장: 직교 좌표계

4장: 2D 컴퓨터 그래픽

5장: 좌표계

6장: 변환(기하학)

7장: 허프 변환

8장: 척도 불변 특성 변환

9장: 호모그래피

10장: 기하학적 특성 학습

(II) 다음에 대한 대중의 주요 질문에 답하기 기하학적 해싱.

(III) 다양한 분야에서 기하학적 해싱을 사용하는 실제 사례.

이 책의 대상 독자

전문가, 학부생 및 대학원생, 열정가, 취미생활자 및 모든 종류의 기하학적 해싱에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

 

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 11, 2024

Book preview

1 장 : 기하학적 해싱

다양한 객체 표현 및 변환에 대한 확장이 있지만 컴퓨터 과학에서는 아핀 변환을 거친 이산 점으로 표현되는 2차원에서 객체를 효율적으로 배치하는 데 기하학적 해싱이 사용됩니다. 오프라인에서 각 점 쌍은 개체를 인코딩하기 위한 기하학적 기준으로 사용됩니다. 두 개의 매개변수는 나머지 점의 기저 불변 표현을 허용합니다. 해시 테이블은 각 키에 대한 베이시스 포인트의 인덱스와 각 값에 대한 양자화된 변환 좌표와 같은 한 쌍의 값을 유지합니다. 그런 다음 이번에는 다른 베이시스 포인트 세트를 사용하여 절차를 반복합니다. 온라인(인식) 단계에서는 데이터 포인트의 임의 쌍이 잠재적 기반으로 평가됩니다. 객체와 각 후보 기저 사이의 실현 가능한 대응을 찾기 위해, 나머지 데이터 포인트들은 기저에 따라 인코딩된다. 데이터 포인트의 충분히 큰 부분이 상수 객체 기준을 가리키면 후보 기준이 허용됩니다.

컴퓨터 비전에서 기하학적 해싱은 2D 및 3D 객체 인식, 기하학적 해싱을 사용한 객체 인식을 위해 처음 제안되었습니다.

입력 이미지에서 모델 이미지를 볼 수 있는지 확인하고 싶다고 가정해 보겠습니다.

기하학적 해싱은 이를 달성하는 데 사용할 수 있는 방법입니다.

이 기술은 데이터베이스의 여러 개체 중에서 단일 개체를 식별하는 데 사용할 수 있으며, 이 시나리오에서 해시 테이블은 개체 모델의 포즈 데이터와 기본 인덱스를 모두 추적해야 합니다.

예제를 간단하게 유지하기 위해 몇 가지 포인트 특성을 사용하고 설명이 좌표에서만 온다고 가정합니다 (실제로 SIFT와 같은 로컬 디스크립터를 인덱싱에 사용할 수 있음).

모델의 정의 특성을 학습합니다.

좌표가 있는 모델 이미지에 5개의 특징점이 있다고 가정 (12,17); (45,13); (40,46); (20,35); (35,25) 하고 사진을 봅니다.

특징점의 좌표를 설명하기 위한 기초를 제공합니다.

2차원 공간에서 유사성 변환의 기초를 제공하는 두 점입니다.

시작점은 두 점(P1, P2)을 연결하는 선의 중간에 위치하며, 사례 연구의 P4, x' 축은 그 중 하나를 향하고 직 y' 교하며 원점을 통과합니다.

척도는 두 기준점의 절대값이 x' 1이 되도록 선택됩니다.

그 기초와 관련하여 사물이 어디에 있는지 설명하십시오.

새 좌표축에 대한 변환을 계산합니다.

노이즈에 대한 인식의 복원력을 높이려면 좌표를 이산화해야 하며 0.25 단위 빈이 사용됩니다.

따라서 좌표를 얻습니다. (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

피처가 있는 해시 테이블을 인덱스로 사용하여 기초를 저장합니다(이 경우 변환된 좌표만). 일치시킬 항목이 두 개 이상인 경우 기본 쌍과 함께 저장할 항목 수입니다.

새 베이시스 쌍으로 전환하고 거기에서 계속하십시오(2단계). 오클루전을 처리하려면 이것이 필수적입니다. 선형이 아닌 모든 쌍이 이상적으로 나열되어야 합니다. 쌍 (P1, P3)이 선택된 두 번의 반복 후에 해시 테이블을 제공합니다.

해시 테이블:

대부분의 해시 테이블에서는 중복 키를 별도의 값과 연결할 수 없습니다.

따라서 실생활에서는 기본 키 (1.0, 0.0) 및 (-1.0, (해시 테이블, 값 0)을 인코딩하지 않습니다.

주어진 이미지에서 시각적 매력의 지점을 찾습니다.

임의의 시작점을 선택합니다. 입력 이미지는 대상 항목이 있는지 여부를 결정하기 위한 적절한 임의의 기반이 없는 경우 대상 항목을 포함하지 않을 수 있습니다.

새 좌표계의 피처 포인트 위치를 자세히 설명합니다. 결과 좌표의 기존 양자화를 수행합니다.

해시 테이블에 대해 입력 이미지의 변환된 포인트 기능을 확인합니다. 포인트 피처가 동일하거나 매우 유사한 경우 관련 기준에 대한 개수(및 개체 유형(있는 경우))를 올려야 합니다.

특정 기준의 카운트가 일부 임계값보다 크면 이 기준이 2단계에서 선택한 이미지 기준에 해당할 가능성이 높습니다. 이를 위해 먼저 이미지의 좌표계를 모델의 좌표계(가상의 개체용)로 변환합니다. 작동하면 항목을 찾을 수 있습니다. 그렇지 않은 경우 이전 단계로 돌아갑니다.

이 접근 방식이 처리할 수 있는 유일한 변환은 크기, 위치 및 방향의 변환인 것으로 보입니다. 그러나 항목이 미러 이미지 형식으로 제공된 이미지에 이미 존재할 수 있습니다. 따라서 객체는 기하학적 해싱을 통해서도 검색할 수 있어야 합니다. 미러링된 오브젝트는 두 가지 방법으로 식별할 수 있습니다.

벡터 그래프의 왼쪽을 양수로, 오른쪽을 음수로 만듭니다. x를 곱할 때 동일한 결과를 얻으려면 -1을 더하면 됩니다.

트라이어드를 시작점으로 사용합니다. 이를 통해 반사(또는 물체)를 식별할 수 있습니다. 기하학적 해싱의 또 다른 방법은 세 개의 점 집합을 기초로 사용합니다.

해싱은 위와 같이 고차원 데이터에 대해 유사하게 작동합니다. 3차원 데이터의 기초에는 세 개의 점이 필요합니다. x축은 처음 두 점으로 정의되고 y축은 세 번째(첫 번째 점 포함)로 정의됩니다. 오른손 법칙을 사용하여 축을 구성할 수 있으며 z축은 이에 수직입니다. 결과 기준은 점이 입력되는 순서에 따라 달라집니다.

{챕터 1 종료}

제 2 장: 해석 기하학

좌표 기하학 또는 데카르트 기하학이라고도 하는 해석 기하학은 데카르트 관점에서 기하학 연구와 관련된 수학의 한 분야입니다. 합성 기하학은 이것의 반대입니다.

물리학, 공학, 항공, 로켓, 우주 과학 및 우주 여행은 모두 해석 기하학을 사용합니다. 그것은 대수기하학, 미분기하학, 이산기하학, 계산기하학과 같은 현대 기하학의 여러 분야의 기초입니다.

평면, 직선 및 원과 관련된 방정식으로 작업할 때는 일반적으로 데카르트 좌표계가 사용됩니다. 기하학에서는 2차원 유클리드 평면과 3차원 유클리드 공간을 연구합니다. 일반적으로 교과서에서 정의되고 가르치는 해석 기하학은 수치적 의미에서 기하학적 모양을 생성 및 표현하고 이러한 표현에서 수치 정보를 추출하는 것과 관련이 있습니다. 칸토어-데데킨트 공리는 선형 연속체의 기하학적 계산이 실수의 대수만을 사용하여 수행될 수 있음을 보장합니다.

그리스 수학자 메나에크무스가 문제를 풀고 정리를 증명할 때 좌표를 사용하는 것과 유사한 기술을 사용했기 때문에 해석 기하학을 개발했다는 주장이 있습니다.

11세기 페르시아의 수학자 오마르 카이얌(Omar Khayyam)은 기하학과 대수학 사이의 밀접한 관계를 보았고, 수치 대수학과 기하학적 대수학 사이의 격차를 좁히는 데 도움을 주면서 올바른 방향으로 나아가고 있었다.248

해석 기하학은 르네 데카르트와 피에르 드 페르마에 의해 독립적으로 발명되었으며, 데카르트 기하학의 대명사인 데카르트 기하학은 데카르트의 이름을 딴 것입니다.

데카르트는 1637 년에 출판 된 자신의 이성을 올바르게 지시하고 과학에서 진리를 찾는 방법에 대한 담론의 부록 인 La Géométrie (기하학)라는 제목의 에세이에서 방법에 대해 상당한 진전을 이루 었으며, 방법에 대한 담론은이 작업의 대중적인 이름입니다.

그의 모국어인 프랑스어, 이론적 기초 등으로 완전히 구성된 La Geometrie는 유럽에서 미적분학 발전의 토대를 마련했습니다.

이 작품은 처음에는 회의론에 부딪혔는데, 부분적으로는 논쟁의 수많은 구멍과 얽힌 수학 때문이었습니다.

데카르트의 걸작은 1649년 반 슈텐이 라틴어로 번역하고 주석을 추가할 때까지(그리고 그가 작업을 계속한 후에도) 그 자체로 인정받지 못했습니다.

이 방법을 취한 결과, 데카르트는 더 복잡한 방정식을 푸는 임무를 맡았고, 더 큰 정도의 다항식 방정식을 다루기 위한 기술의 개선이 필요했습니다.

레온하르트 오일러(Leonhard Euler)는 좌표법을 사용하여 공간의 곡선과 표면을 체계적으로 조사한 최초의 사람입니다.

해석 기하학에서는 평면에 좌표계가 도입되고 각 점에 두 개의 실수가 할당됩니다. 유클리드 공간의 각 점에도 세 개의 좌표가 할당됩니다. 좌표의 중요도는 선택한 기준점에 의해 결정됩니다. 다양한 좌표계가 존재하지만 가장 일반적인 좌표계는 다음과 같습니다.

각 점의 수평 위치를 나타내는 x 좌표와 수직 위치를 나타내는 y 좌표가 있는 데카르트 좌표는 가장 널리 사용되는 좌표계입니다. 이들은 일반적으로 쌍을 이루는 표현식 (x, y)로 표시됩니다. 3차원 유클리드 공간의 모든 점은 이 방법(x, y, z)을 사용하여 정렬된 좌표의 삼중으로 나타낼 수 있습니다.

극좌표 표기법에서 평면의 모든 점은 원점으로부터 의 거리 r  과 각도 θ 로 표시되며 θ  는 일반적으로 양의 x축에서 시계 반대 방향으로 측정됩니다.

이 표기법은 다음과 같은