Global mapper

1. 여러가지 global map 형태(representation 방식)의 특징과 장단점

1.1. Point Clouds

• 3D 공간에서의 점들의 집합으로, 각 점은 XYZ 좌표와 추가적인 정보(RGB 값, 정규벡터 등)를 포함할 수 있음
• 장점:
  • 직관적이고 간단한 데이터 구조.
  • 고해상도의 환경 세부 정보 표현 가능.
  • 데이터 처리 및 시각화 도구가 다양함.
• 단점:
  • 데이터 양이 매우 방대함.
  • 공간적 효율성이 낮아 대규모 환경에서 메모리 요구량이 큼.
  • 점군 간의 상호작용이나 관계를 직접 표현하기 어려움.

---

1.2. Map Grids / Occupancy Grids / Voxel

• 
• Map Grids 또는 Occupancy Grids는 환경을 일정한 크기의 격자로 나누고, 각 격자 셀이 점유되었는지 또는 빈 공간인지를 표시
• 이 방식은 2D 또는 3D로 구현될 수 있으며, 3D 점유 격자는 종종 복셀(Voxels)이라고 함
• 장점:
  • 공간을 균일하게 표현하여 계산 및 검색이 용이.
  • 크기와 점유 여부 정보로 간단한 내비게이션과 충돌 회피에 유용.
  • 메모리 사용량을 조절하기 위해 멀티 해상도 접근법을 적용할 수 있음.
• 단점:
  • 세부 정보 표현에 한계가 있음.
  • 공간 해상도에 따라 성능이 크게 달라짐.
  • 빈 공간과 점유 공간의 이진 구분으로 인해 정보 손실 가능성이 있음.

1.3. 쿼드 트리(Quadtree)

• 쿼드 트리는 2차원 공간을 재귀적으로 네 개의 동등한 사분면으로 분할하여 관리하는 자료 구조
• 구조:
  • 쿼드 트리의 노드는 최대 네 개의 자식 노드를 가질 수 있으며, 각 자식 노드는 부모 노드의 공간을 네 개의 구역(사분면)으로 나눕니다.
  • 이 과정은 더 이상 분할할 수 없거나, 노드가 설정한 임계값(예: 요소의 수, 깊이)에 도달할 때까지 반복

1.4.2. 최적화 및 효율성

• 최적화:
  • 쿼드 트리와 옥트리 모두 공간 분할의 깊이와 분할 기준을 조정함으로써 최적화할 수 있습니다.
  • 이는 특정 응용 프로그램의 요구 사항과 데이터의 특성에 따라 달라질 수 있으며, 메모리 사용량과 검색 속도 사이의 균형을 맞추는 데 중요

---

---

쿼드 트리 VS grid map

쿼드 트리 장점

• 공간 효율성: 쿼드 트리는 비어 있는 공간을 효율적으로 압축하여 저장할 수 있기 때문에, 특히 대규모 또는 희소한 환경에서 메모리 사용량을 크게 줄임
• 적응적 해상도: 이는 로컬 영역의 세부 정보를 유지하면서도 전체 맵의 크기를 효율적으로 관리할 수 있게

단점

• 검색 성능: 특정 조건에 맞는 데이터를 검색하는 경우, 그리드 기반 맵에 비해 상대적으로 검색 성능이 떨어질 수 있습니다. 모든 노드를 순회하거나 깊이를 따라 내려가야 하는 경우가 발생할 수 있기 때문입니다.
• 구현 복잡성: max_depth와 max_points 값에 대한 세심한 튜닝이 중요하다.
• 분할 기준의 한계: 실세계의 복잡한 환경을 표현할 때, 균등하게 공간을 4분할하는 쿼드 트리의 접근 방식이 항상 최적의 해를 제공하지는 않습니다. (사각형이므로)

그리드 글로벌 맵의 장점

• 단순성과 일관성: 그리드 맵은 구현이 단순하고, 모든 그리드 셀이 동일한 크기와 모양을 가지므로 처리 로직이 일관됩니다. 이는 맵의 해석과 사용을 용이
• 빠른 접근성: 특정 위치의 데이터에 대한 접근이 O(1) 시간 복잡도로 이루어질 수 있음. 이는 실시간 시스템에서 매우 중요한 이점입니다.
• 검색 및 업데이트 효율성: 고정된 셀 구조 덕분에 특정 영역 내 데이터를 검색하거나 업데이트하는 과정이 매우 빠르고 효율적입니다.

그리드 글로벌 맵의 단점

• 메모리 사용량:
  • 모든 셀이 무조건적으로 메모리를 차지하기 때문에, 그리드 기반 맵은 큰 환경을 모델링할 때 상당한 양의 메모리를 소비할 수 있습니다.
  • 특히 환경의 대부분이 빈 공간이라면, 이러한 메모리 사용은 매우 비효율적일 수 있음
• 해상도 고정:
  • 그리드 맵에서는 모든 셀이 동일한 크기를 가집니다.
  • 이는 세밀한 해상도가 필요한 지역과 그렇지 않은 지역이 동일하게 처리되어, 해상도가 전체적으로 제한되거나, 불필요하게 높은 해상도로 인해 메모리 낭비가 발생할 수 있습니다.

쿼드 트리 대 그리드 맵: 선택 기준

• 환경의 복잡성과 동적 변화:
  • 환경이 복잡하고 동적으로 변화한다면, 쿼드 트리가 더 적합할 수 있습니다.
  • 쿼드 트리는 필요에 따라 해상도를 조정할 수 있고, 특정 부분만을 대상으로 빠르게 업데이트할 수 있기 때문
• 메모리 사용과 성능 요구 사항:
  • 메모리 사용이 큰 걱정거리이고, 불규칙적인 데이터 분포를 가지는 대규모 환경을 다룬다면, 쿼드 트리가 더 효율적
  • 반면, 작업이 간단한 데이터 접근과 빠른 업데이트에 중점을 둔다면, 그리드 맵이 더 나을 수 있습니다.
• 구현의 복잡성과 유지보수:
  • 구현의 단순성과 유지보수가 중요한 요소라면, 그리드 기반 맵이 더 매력적일 수 있습니다.
  • 쿼드 트리는 고급 기능과 효율성을 제공하지만, 그만큼 구현과 관리가 더 복잡합니다.

---

---

2. global map에 RGB 이미지까지 함께 저장하기

2.1. 3D 포인트 클라우드와 연계된 RGB 이미지 데이터

• 이 방법은 3D 공간의 각 점에 대한 RGB 정보를 포인트 클라우드 데이터에 직접 연결하는 것입니다. 포인트 클라우드 각 점에는 3차원 공간의 위치(X, Y, Z)와 해당 점의 색상 정보(R, G, B)가 포함됩니다.

• 장점:
  • 공간의 정밀한 구조와 시각적 정보를 동시에 제공합니다.
  • 시각적 정보를 활용한 객체 인식 및 분류 작업에 유용합니다.
• 단점:
  • 높은 데이터 양으로 인한 저장 공간 및 처리 능력의 부담이 증가합니다.
  • 동적 환경 변화에 대한 실시간 업데이트가 요구될 경우, 처리 복잡성이 증가합니다.

2.2. 시맨틱 맵핑과 RGB 이미지의 연계 (좋은듯)

• 시맨틱 맵핑은 환경 내의 객체나 공간을 의미론적으로 분류하고, 이러한 정보를 RGB 이미지와 연계하는 방식
• 각 객체 또는 공간에 대한 시맨틱 태그와 함께 해당하는 RGB 이미지를 저장하여, 공간에 대한 더 풍부한 정보를 제공합니다.

• 장점:
  • 공간에 대한 깊은 이해와 분석이 가능합니다.
  • 다양한 응용 프로그램에서 공간 정보와 시각적 정보의 통합적 활용이 용이
• 단점:
  • 시맨틱 분류 및 태깅은 고도의 인공지능 알고리즘을 요구
  • 실시간 환경 변화에 대응하기 위해서는 지속적인 데이터 업데이트가 필요

---

3. global map에 temporal 정보까지 같이 저장하기

3.1. 3D 포인트 클라우드와 타임스탬프 통합

• 타임스탬프 정보 통합:
  • 각 포인트 클라우드 데이터 세트에 타임스탬프를 추가하여, 데이터가 언제 취득되었는지에 대한 시간적 정보를 기록
  • 이는 변화하는 환경을 기록하고, 시간에 따른 변화를 분석하는 데 유용

3.2. 데이터 저장 및 검색 구조

3.2.1. 4D space time cube 모델:

• 
• 공간적 및 시간적 데이터를 통합하여 저장하는 효율적인 방법
• 이 모델은 X, Y, Z 좌표와 시간(T)을 축으로 하는 4차원 데이터 구조로, 특정 시간에 특정 위치의 환경 정보를 검색하는 데 유용

3.2.2. 데이터베이스 및 인덱싱:

• 시간적 정보와 함께 3D 데이터를 관리하기 위해, 고성능 데이터베이스 시스템을 사용하며, 공간적 정보를 효과적으로 검색할 수 있도록 고급 인덱싱 기술을 적용
• 예를 들어, R-트리, k-d 트리 또는 공간-시간 인덱스는 공간적 및 시간적 차원에서 빠른 검색을 지원
• 이러한 인덱싱 방법은 복잡한 쿼리를 실행할 때 데이터 접근 시간을 대폭 줄여주며,
• 특정 시간 범위 내에서의 공간적 조회나, 특정 지역에서의 시간적 변화 추적 같은 복잡한 질의를 신속하게 처리할 수 있음

3.3. 변화 감지 및 시간적 변화 추적

• 변화 감지 알고리즘:
  • 환경의 변화를 탐지하고 기록하기 위해, 변화 감지 알고리즘을 적용할 수 있음
  • 이러한 알고리즘은 연속적인 시간대의 데이터를 비교하여 변화된 부분을 식별
• 시간적 변화 데이터 모델링:
  • 변화 감지 결과를 기반으로, 환경의 시간적 변화를 모델링하고 저장하는 방법을 개발
  • 이는 변화의 유형, 범위, 시간 등을 포함할 수 있으며, 시간에 따른 환경 변화의 기록을 제공
  • 이러한 정보는 환경의 역사적 변화를 분석하거나 미래의 변화를 예측하는 데 사용될 수 있음

---

4. global map에 decaying factor 까지 함께 고려하기

4.1. 데이터 저장 구조

4.1.1. 4D 스페이스-타임 큐브 모델 확장:

• 공간(X, Y, Z)과 시간(T)을 기반으로 하는 4D 큐브 모델에, 물체 클래스 정보와 각 클래스별 감쇠 인자를 포함시키는 추가 차원을 도입
• 이는 공간-시간 데이터 구조에 객체 인식 및 감쇠 정보를 통합하여, 특정 시간 및 위치에서의 객체 상태와 그 변화를 정밀하게 모델링할 수 있도록 합니다.

4.1.2. 옥트리(Octree)와 시멘틱 분할:

• 공간적 데이터를 효율적으로 저장하고 검색할 수 있는 옥트리 구조에, 객체 인식 정보(시멘틱 라벨)와 decaying factor를 추가
• 각 노드는 특정 물체 클래스에 속하는 포인트들과 해당 클래스의 감쇠 인자 값을 저장할 수 있으며, 시간이 지남에 따라 이 정보를 업데이트합니다.

4.2. 감쇠 인자(decaying factor)의 적용

• 감쇠 모델 정의:
  • 물체 클래스별로 다른 감쇠 인자를 정의합니다.
  • 예를 들어, 변화가 빈번한 객체(사람, 자동차 등)는 높은 감쇠 인자를, 상대적으로 정적인 객체(건물, 나무 등)는 낮은 감쇠 인자를 할당합니다.
  • 이러한 인자는 시간에 따라 객체의 관련성이나 신뢰도를 감소시키는 데 사용
• 시간적 감쇠 처리:
  • 시스템은 각 데이터 포인트의 타임스탬프와 현재 시간을 비교하여, 설정된 감쇠 인자에 따라 객체의 가중치나 신뢰도를 조정
  • 이는 객체의 현재 상태를 더 정확하게 반영하며, 오래된 정보에 대한 의존도를 감소시킴

4.3. 데이터 관리 및 검색

• 시간적 및 공간적 쿼리 지원:
  • 개발된 데이터 저장 구조는 시간적 및 공간적 쿼리를 모두 지원해야 함
  • 예를 들어, 특정 시간 범위 내에서 특정 위치의 특정 물체 클래스에 대한 정보를 검색할 수 있어야 함
• 고성능 데이터베이스 사용:
  • 대량의 3D 포인트 클라우드 데이터와 시간적, 감쇠 인자 정보를 효과적으로 관리하기 위해, 고성능 데이터베이스 시스템을 사용
  • 데이터베이스는 고급 인덱싱 메커니즘을 제공하여, 빠른 데이터 검색과 업데이트를 지원해야 합니다.

---