• Reviewing what I studied, how this work will be explained as well.

Quick Sort is an efficient, comparison-based sorting algorithm that employs the divide and conquer strategy. Unlike Merge Sort which divides arrays into equal halves, Quick Sort creates unbalanced partitions based on a pivot element. This characteristic gives Quick Sort its name - it’s particularly “quick” for many real-world scenarios.

The Divide and Conquer Strategy in Quick Sort

1. Divide: Select a pivot element and partition the array into two sub-arrays - elements less than the pivot and elements greater than the pivot.
2. Conquer: Recursively sort the sub-arrays.
3. Combine: Since the partitions are already sorted in place, no explicit combination step is needed. Let’s actually see how this works.

Partitioning

Partitioning is a crucial step in the Quick Sort algorithm where elements are rearranged around a pivot value. There are two main partitioning schemes: Lomuto and Hoare.

Lomuto Partition Scheme The Lomuto partition scheme typically selects the last element as the pivot. It uses a one-directional scanning technique that maintains three distinct partitions: elements less than the pivot, elements greater than the pivot, and the unknown section.

pair<int, int> lomutoPartition(int data[], int lo, int hi) {
    int pivot = data[hi]; // alternatively you can select the pivot in the middle of the array.

    int i = lo - 1; // int i = 0
    for (int j = lo; j < hi; j++) {
        if(data[j] <= pivot)
            swap(data[++i], data[j]);  // data[i++]
    }

    swap(data[++i], data[hi]);   // data[i]
    return make_pair(i - 1, i + 1);
}

Hoare Partition Scheme The Hoare partition scheme, developed by Sir Charles Antony Richard Hoare (the creator of Quick Sort), typically selects the first element as the pivot. It uses a two-directional scanning technique with two pointers moving in opposite directions.

pair<int, int> hoarePartition(int data[], int lo, int hi) {
    int pivot = data[(lo + hi) / 2];
    int i = lo - 1;
    int j = hi + 1;

    while(true){
        do i++; while(data[i] < pivot);
        do j--; while(data[j] > pivot);

        if (i < j)
            swap(data[i], data[j])
        else 
            break;
    }

    return make_pair(j, j+1);
}

version 2:

pair<int, int> hoarePartition2(int data[], int lo, int hi) {
    int pivot = data[(lo + hi) / 2];

    int i = lo;
    int j = hi;
    while( i <= j ){
        while(data[i] < pivot)
            i++;
        while(data[j] > pivot)
            j--;

        if (i < j)
            swap(data[i++], data[j--]);
        else
            i++;
    }
    return make_pair(j, j+1);
}

version 3: when pivot was selected in the first element

pair<int, int> hoarePartition3(int data[], int lo, int hi) {
    int pivot = data[lo];

    int i = lo;
    int j = hi+1;
    while(true) {  
        do i++; while( i <= hi && data[i] < pivot);
        do j--; while( j > lo && data[i] > pivot);

        if(i < j)
            swap(data[i], data[j]);
        else
            break;
    }
    swap(data[lo], data[hi]);
    return make_pair(j -1, j+1);
}

3-way Partitioning

This is very specific cases, where there are multiple or repetitive numbers:

Then we use 3-way partitioning. There are two 3-way partitioning; hoare partition and Bentley-Macllroy.

pair<int, int> partition3wayHoare(int data[], int lo, int hi) {
    int pivot = data[(lo + hi)/2];

    int lt = lo;
    int gt = hi;
    for (int i = lo; i <= gt;) {
        if(data[i] < pivot)
            swap(data[lt++], data[i++])
        else if (data[i] > pivot)
            swap(data[i], data[gt--])
        else
            i++;
    }
    return make_pair(lt - 1, gt + 1);
}

pair<int, int> partitionBently3way(int data[], int lo, int hi) {
    int pivot = data[(lo + hi) /2];
    int i = lo - 1, j = hi + 1;
    int p = lo - 1, q = hi + 1;

    while(true) {
        while(data[++i] < pivot);
        while(data[--j] > pivot);
    

        if (i < j) {
            swap(data[i], data[j]);
            if (data[i] == pivot)
                swap(data[++p], data[i]);
            if (data[j] == pivot)
                swap(data[--q], data[j]);
        } else {
            if (i == j)
                swap(data[++p], data[i]);
            break;
        }
    }

    i = j +1;
    for (int k = lo; k <= p; k++)
        swap(data[k], data[j--]);
    for (int k = hi; k >= q; k--)
        swap(data[k], data[i++]);
    return make_pair(j, i);
}

So using one of those partition mechanism, we can use one of those above.

How to select right pivot value?

1. first or last:
2. random: int pivot = data[rand() % (hi - lo + 1) + lo];
3. middle
4. MED3 (Median of Median)

Standard C++ Library: Select Pivot

int choosePivot(int data[], int lo, int hi)
{
    int n = hi - lo + 1;
    int mid = (lo + hi) / 2;
    if (n > 7) {
        if (n > 40) {
            lo = MED3(data, lo, lo + d, lo + 2*d);
            mid = MED3(data, mid - d, mid, mid + d);
            hi = MED3(data, hi - 2*d, hi - d, hi);
        }
        mid = MED3(data, lo, mid, hi);
    }
    return mid;
}

int pivot = data[choosePivot(data, lo, hi)];

Algorithm Walkthrough

Let’s trace through the Quick Sort algorithm with a concrete example:

Initial Array: {5, 3, 8, 4, 9, 1, 6, 2, 7}

First Partition:

1. Select pivot: Let’s choose the first element, 5
2. Initialize pointers:
   • Left pointer starts at index 1 (value 3)
   • Right pointer starts at the last index (value 7)
3. Partitioning process:
   • Move left pointer rightward until finding an element ≥ pivot
   • Move right pointer leftward until finding an element ≤ pivot
   • Swap these elements if pointers haven’t crossed
   • Continue until pointers cross
4. Final swap: Place pivot at its correct position by swapping with the right pointer
5. Result: {2, 3, 1, 4, 5, 9, 6, 8, 7}

Now we have two sub-arrays: {2, 3, 1, 4} (elements < 5) and {9, 6, 8, 7} (elements > 5).

Second Partition (Left Sub-array):

1. Select pivot: 2
2. Partitioning process: Similar to above
3. Result: {1, 2, 3, 4} with sub-arrays {1} and {3, 4}

Third Partition (Right Sub-array):

1. Select pivot: 9
2. Partitioning process: Similar to above
3. Result: {7, 6, 8, 9} with sub-arrays {7, 6, 8} and {}

The process continues recursively until all sub-arrays are sorted.

This can be done recursively. Let’s look at the code.

void quickSortRect(int data[], int lo, int hi) {
    if (lo >= hi) return;

    int leftLast, rightFirst;
    auto [leftLast, rightFirst] = partition(data, lo, hi);

    quickSortRec(data, lo, leftLast);
    quickSortRec(data, rightFirst, hi);
}

void quickSort(int data[], int n) {
    quickSortRec(data, 0, n -1)
}

Time Complexity

The time complexity is based on the pivot value, because this will make array to be unbalanced. The worst case would be O(n^2), but the best case would be O(nlogn)

• Reviewing what I studied, how this work will be explained as well.

Quick Selection Sort

Quick Selection, also known as Quickselect or Hoare’s Selection Algorithm, is an efficient algorithm designed to find the kth smallest element in an unordered list. Developed by Tony Hoare (the same computer scientist who created Quicksort), this algorithm shares the same partitioning strategy as Quicksort but with a crucial difference in its recursive approach.

Algorithm Overview

Quickselect uses a divide-and-conquer approach similar to Quicksort:

1. Choose a Pivot: Select an element from the array as the pivot
2. Partition: Rearrange the array so elements less than the pivot are on the left, and elements greater are on the right
3. Selective Recursion: Unlike Quicksort which recurses on both partitions, Quickselect only recurses on the partition that contains the kth element we’re looking for

This selective recursion is what gives Quickselect its efficiency advantage over a full sorting algorithm when we only need to find a specific element.

Implementation

int partition(int data[], int lo, int hi) {
    int pivot = data[hi];

    int i = lo -1;
    for(int j = lo; j < hi; j++) {
        if (data[j] <= pivot)
            swap(data[++i], data[j];)
    }
    swap(data[++j], data[hi]);
    return i;
}

void quickSelectRec(int data[], int lo, in hi, int k) 
{
    if (lo == hi) return;

    int pivotIndex = partition(data, lo, hi);

    if (k == pivotIndex)
        return;
    else if (k < pivotIndex) 
        quickSelectRec(data, lo, pivotIndex - 1, k);
    else
        quickSelectRec(data, pivotIndex + 1, hi, k);
}


void quickSelect(int data[], int n, int k) {
    quickSelectRec(data, 0, n - 1, k);
}

Time Complexity

The time complexity of Quickselect varies depending on the scenario:

1. Best Case: O(n) - This occurs when each partition divides the array into roughly equal halves.
2. Average Case: O(n) - Even with random pivot selection, the algorithm performs linearly on average.
3. Worst Case: O(n²) - This happens when the partitioning is maximally unbalanced (e.g., when the array is already sorted and we choose the first or last element as pivot).

The linear average-case time complexity makes Quickselect significantly more efficient than sorting algorithms (which require at least O(n log n) time) when we only need to find a specific element.

• Reviewing what I studied, how this work will be explained as well.

Selection Sort is a simple and intuitive comparison-based sorting algorithm. The core idea behind this algorithm is to divide the array into a sorted portion and an unsorted portion, then repeatedly find the smallest (or largest) element from the unsorted portion and place it at the end of the sorted portion.

Algorithm Steps

Selection Sort operates through the following steps:

1. Initialization: Conceptually divide the array into a sorted portion (initially empty) and an unsorted portion (initially the entire array).
2. Find Minimum: Find the smallest element in the unsorted portion.
3. Swap: Exchange the found minimum with the first element of the unsorted portion.
4. Boundary Shift: Move the boundary between sorted and unsorted portions one position to the right.
5. Repeat: Continue this process until the entire array is sorted.

You may find this algorithm to be too easy!

Implementation

void SelectionSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;

        for (int j = i + 1; j <= n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }

        swap(arr[i], arr[minIdx]);
    }
}

void printArray(vector<int>& arr) {
    for (int& val : arr) {
        cout << val << " ";
    }
    cout << endl;
}


int main()
{
    vector<int> arr = { 64, 25, 12, 22, 11 };
    cout << "Original array: ";
    printArray(arr);

    SelectionSort(arr);

    cout << "Sorted array: ";
    printArray(arr);
}

The time complexity would be in for-loop (inner loop and outer loop) => O(n²) for all cases.

Kth Selection Sort

Problem Statement: The selection problem is defined as: Given an array of n elements and an integer k (1 ≤ k ≤ n), find the kth smallest (or largest) element in the array.

Implementation

void SelectionSort(vector<int> vec, int lo, int hi)
{
    int minIdx = lo;
    for (int i = lo + 1; i <= hi; i++)
    {
        if(vec[i] < vec[minIdx])
            minIdx = j;
    }
    swap(vec[lo], vec[minIdx]);
}

void PartialSelectionSort(vector<int> vec, int k) 
{
    for (int i = 0; i < k; i++) 
    {
        SelectionSort(vec, i, k)
    }
}

int main() {
    vector<int> vec = { 7, 10, 4, 3, 7, 20, 15 };
    int k = 4;
    PartialSelectionSort(vec, k);
}

The time complexity for this O(kn), but if k is smaller value, it can be interpreted as O(n), but if k is large enough, it is considered to be O(n²)

• Reviewing what I studied, how this work will be explained as well.

This sorting algorithm is based on the devide and conquer strategy. The steps in simple array are as follows:

1. Divide the input array into two halves. (Divide)
2. Sort each half. (Conquer)
3. Merge the two halves. (Combine)

Basically, we’re breaking the problem of sorting the array into two smaller problems. (sub-problems), then we merge the two halves, which are sorted.

The problem state: Given some array, and sort it in increasing order. There are two solution can exist: bottom up (for loop), and top down (recursive). Let’s explore what are the code looks like, and the logic behind. If the size of the array or the vector is 0 or 1, it is already sorted. The sort doesn’t happen when it’s divided, it happens when it’s combining(merging).

Let’s look at the recursive way to solve this first (top-down merge sort)

void Merge(vector<int>& a, int lo, int mid, int hi)
{
    aux.resize(a.size())
    int i = lo; j = mid + 1;
    for (int k = lo; k <= hi, k++)
    {
        aux[k] = a[k];
    }

    // you can do while in the similar way, which can be way easier than this
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid) a[k] = aux[j++];                // left array is already sorted, now look at right array
        else if (j > hi) a[k] = aux[i++];            // right array is already sorted, now look at left array
        else if (aux[i] < aux[j]) a[k] = aux[i];     // compare the value, get the min value
        else a[k] = aux[i++];                        // just copy the value
    }
}

void SortHelper(vector<int>& a, int lo, int hi)
{
    if(hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    SortHelper(a, lo, mid);
    SortHelper(a, mid+1, hi);
    Merge(a, lo, mid, hi);
}

int main() 
{
    std::vector<int> vec = {3, 5, 8, 9, 6, 2};
    SortHelper(vec, 0, vec.size() - 1);
}

Let’s look at the bottom-up approach

void Sort(vector<int>& a)
{
	aux.resize(a.size());

	int N = a.size();

	for (int sz = 1; sz < N; sz = sz + sz) {
		for (int lo = 0; lo < N - sz; lo += sz + sz)
			Merge(a, lo, lo + sz - 1, std::min(lo + sz + sz - 1, N - 1));
	}
}

void Merge(vector<int>& a, int lo, int mid, int hi)
{
	int i = lo, j = mid + 1;
	if (a[mid] <= a[j]) return;
	for (int k = lo; k <= hi; k++)
		aux[k] = a[k];
	for (int k = lo; k <= hi; k++)
	{
		if (i > mid) a[k] = aux[j++];
		else if (j > hi) a[k] = aux[i++];
		else if (aux[j] < aux[i]) a[k] = aux[j++];
		else a[k] = aux[i++];
	}
}


int main() 
{
    std::vector<int> vec = {3, 5, 8, 9, 6, 2};
    Sort(vec, 0, vec.size() - 1);
}

Time Complexity & Accuracy

• this is definitive way to sort array or vector. If we have a n problem, we divided into n/2 and so on, then level is created is log(N), so this becomes O(n * log n)

• Reviewing what I studied, how this work will be explained as well.

Given this array / vector that has {2, 8, 5, 3, 9, 4}. We want to sort this increasing order.

1. Work left to right
2. Examine each item and compare it to items on its left.
3. Insert the item in the corect position in the array.

We sure that first element is sorted out, that’s why we loop from 1 to vector size. Since we partition the first group (element), then we compare the next value and the far right of the partioned group. (ex: if i index = 2, then j = 2, compare 8 and 5, 5 is smaller than 8, so we swap them.) Also, another case would be if i index = 3, we compare 8, and 3, then swap. Then we compare 3 and 5, and swap. Basically we’re inserting every time if next value and the partioned array’s of last index by comparing. Basically, that’s what inserting happend!

#include <iostream>
#include <vector>

void Print(const std::vector<int>& vec)
{
	for (auto& v : vec) {
		std::cout << v << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::vector<int> vec = { 2, 8, 5, 3, 9, 4 };
	Print(vec);

	// Logic:
	// first element is always sorted.
	for (int i = 1; i < vec.size(); i++)
		for (int j = i; j > 0 && vec[j-1] > vec[j]; j--)
			std::swap(vec[j - 1], vec[j]);
	
	Print(vec);
}

But we can also simplify, and a bit optimize version by not using std::swap

for (int i = 1; i < vec.size(); i++)
{
	int key = a[i];
	int j = i;
	for(; j >0 && a[j -1] > key; j--)
		a[j] = a[j-1];
	a[j] = key
}

Time Complexity && Worst Case

We know that two for loop, which means it will compare the new value and the partitioned elements. So, it will be O(n^2). Best Case is O(n) when the array is already sorted. But Worst Case is O(n^2) when the array is sorted in decreasing order.

Resource

• Insertion Sort

회사에서, UNDO / REDO 설계를 맡게 되었는데.. 여러의 source 들을 찾아보려고 하니 @abstractstaticmethod 라는 녀석을 보게 되었다. 과연 abstract 는 왜 사용 되는지, static method, class method, 그리고 instance method 를 알아보겠다.

일단 아래의 그림을 보면, 대충 추상클래스가 왜 필요한지 볼 수 있다.

정의는 이러하다 Weapon Class(추상 클래스)가 생성이 되면, 무기마다 다른 특성들을 가지고 있기 때문에 Gun Class 와 Sword Class 가 가지는 action method 들도 다를것이고, 역활? 도 나름 다를 것이다. 사실 무기 클래스는 attack() 이라는 method 를 가질수 있다, 하지만 내부에서 구현하는 방식이, 어떤 종류의 무기에 따라서 내용이 달라진다.

즉 여러 종류의 무기 class (e.g sword, gun, etc..) 들은 무기(Weapon)이라는 Class로 부터 상속을 받게 하므로, 세세한 구현은 상속받은 자식 클래스로부터 세부 구현해야한다. 이렇다고 한다면, 이론적으로 overriding 하고 똑같은 의미이지 않느냐? 라고 물어볼수 있다.

일단, 추상 클래스는 실제로 추상적인 또는 대체적인 그림의 틀을 가지고 있다고 생각하면 된다. 실체 클래스들은 자식들의 클래스이다. 즉 실체 클래스의 멤버(필드, 메소드)를 잘 잡아주는 틀이라고 생각하면 될것 같다.

즉 메소드 선언만 통일화 [링크 참조]를 할수 있게 만들며, 각각의 기능은 달라지는거라고 생각하면 편하다.또 Method 선언만 통일화 하고 각각의 기능이 달라져야 되는 케이스가 필요하기 때문에, 추상 메소드 오버라이딩이 필요하다.

python 에서의 추상 클래스를 만들기 위해서, abc 모듈을 가지고 와야한다.

-코드-

from abc import *
class MyAbstractClass(metaclass=ABCMeta):

  @abstractmethod
  def MyabstractMethod(self):
    pass

예제 코드

from abc import *

class Weapon(metaclass=ABCMeta):
  name = "weapon name"
  att_dmg = 0
  durability = 100

  @abstractmethod
  def attack(self):
    pass


# Gun
class Gun(Weapon):
  def __init__(self, name, att_dmg):
    self.name = name
    self.att_dmg = att_dmg

  def attack(self):
    self.durability -= 2
    print("%s %d %d" %(self.name, self.att_dmg, self.durability))


# Sword
class Sword(Weapon):
  def __init__(self, name, att_dmg):
    self.name = name
    self.att_dmg = att_dmg

  def attack(self):
    self.durability -= 5
    print("%s %d %d" %(self.name, self.att_dmg, self.durability))


# Bow
class Bow(Weapon):
  def __init__(self, name, att_dmg):
    self.name = name
    self.att_dmg = att_dmg

  def attack(self):
    self.durability -= 1
    print("%s %d %d" %(self.name, self.att_dmg, self.durability))

위의 코드와 같이 weapon 이라는 클래스는 맞지만, 클래스가 아닌? 추상적인 클래스가 있고, 세부적인 무기들은 weapon 이라는 클래스를 상속 받는다. 파이썬에서 각각의 weapon 들을 instance 화 시키면, 결과 값은 다 다르다. 결국, 억지인 예일수 있지만, 달고나 만드는것 처럼, 달고나를 만드는 행위는 어떤 모양이든 다 같지만, 하지만 어떤한 모양으로 낼지는 다른거다 라고 말을 할수 있을것 같다.

Resouce

1. Python Basic - Abstract & Class Variable
2. Abstract Method and Overriding
3. Why do we need to use the Abstract Method
4. Virtual Function

ROS2 책을 사서, 보고 있는데… 사실상 ROS1 과 ROS2 의 차이를 어느정도 느끼고 있으면서도, 확실히 많은 것 같은 느낌이 든다.

Definition of DDS

DDS 의 정의란 이런다. DDS 는 데이터 분산 시스템의 줄임말로 OMG Object Management Group 에서 표준을 정하고자 만든 트레이드 마크이다. 형식상 어려운 말이기도 하다.. 뭔 Oh My God 도 아니고.. 규정을 하는 OMG 가 있다니.. 하지만 책에서 보기에는 이게 데이터 통신을 위한 Middleware 이다.

우선 정의는 이렇다 DDS 는 Data Distribution Servce, 의 약자이며, 데이터 분산 서비스의 약자이다.

OMG 에서 정의 한 DDS 란, 더욱더 명확한것 같다..

The Data Distribution Service(DDS) is a middleware protocol and API standard for data-centric connectivity from the OMG> it integrates the components of a system together, proviiding low-latency data connectivity, extreme reliability, and a scalable architecture that business and mission-critical IOT applications need.

In a distributed system, middleware is the sfotware layer that lies between the operating system and data. It simplifies the development of distributed systems by letting software developers focus on the specific purpose of therir applications rather than the mechanics of passing information between applications and systems.

이걸 보면, 대학원 수업시간에 distributed system 을 듣긴한것 같은데, 그래서 middleware 가 좀 더 친숙한 단어이긴하다.

책에서는 이렇게 말한다. “실제로는 데이터를 중심으로 결성을 갖는 미들웨어의 프로토콜(DDSI-RTPS) 와 간이 DDS 사양을 만족하는 middleware api 가 그 실체 이다.” 즉 APP 과 OS 를 중간에서 연결해주는 다리 역활은 하는데. 여기서는 API 들이 주로 programming language 와 ROS 에 Topics, data, types, filtering, cache 등 있고, protocol 에는 Session, reliability, QoS 등 있다. 즉 ROS 는 또 다른 OS 라고 생각하면, OS 와 우리가 사용하는 Application 사이에 통신을 이어주며, Programming Language 의 호환 등… 있는것 같다.

Feature of DDS

• Industry Standards
• OS Independent
• Language Independent
• Transport on UDP / IP
• Data Centricity
• Dynamic Discovery
• Scalable Architecture
• Interoperability
• Quality of Service(QoS)
• Security

여기서 잠깐? Middleware 란?

Resource (발췌)

ROS2 (Robot Operating System), ROS2 로 시작하는 로봇 프로그래밍 - 표윤석, 임태운 지음

요즘 Facebook 에 Robotics KR 또는 SLAM KR 에서, 열심히 눈팅하다가 보았던 Magazine 을 회사에서 프린트를 하고 보려던 참에 눈에 들어와서 읽어보았다.

일단 SLAM 이라는 기술은 현재 autonomous vehicles and robot 에 사용되었다. 어제만해도, 로봇 청소기가 어떻게 Mapping 을 할 수 있을지가 궁금했었는지 말이다. SLAM (Simultaneous localization and Mapping) 또는 SfM(Structure from Motion) 이라는 기술은 지금 계속 연구되고 있다고 한다.

3 차원 환경 지도를 만들고 위치 추정을 하려면, 여러가지의 sensor device 가 필요한데. 예를 들어서, 카메라(monocular and stereo camera), 레이저 센서, RGB-D 카메라가 있다. RGB-D 카메라 같은 경우, 내가 유튜브로 보다가 Amazon? 에서 나온 카메라를 본적은 있엇던것 같다. 레이저 센서는 너무 유명 하고도 유명한 LiDAR 이 있다. 2D LiDAR 와 3D LiDAR 가 있는데 이게 수직 해상도(vertical resolution)에 따라서 분류가 된다고 한다.

여기서 정리 할 필요가 있는데, 한번 표로 정리를 해봐야겠다.

사실 Stereo 와 Monocular Camera 를 이용한 딥러닝 Paper 를 읽어본 적 있으며, Unsupervised Way 나 ConvLSTM 을 사용해서 문제를 풀었던 문제를 읽곤 했었다. Depth Estimation 에 “거리” 라는건 굉장히 중요하고 카메라가 가격의 장점을 이용해서, 이 문제를 푸는건 아직도 큰 문제 인거 같긴하다.

사실 새롭게 알았던건, 카메라를 이용해서, SLAM 기법을 사용하면, 오차가 누적되기 때문에, 최종 생성된 지도와 위치 추정의 오차가 매우 커진다라는것과 이러한 오차를 해결한 방법은 Visual-SLAM 을 사용해서 문제를 풀어간다라는것이다. 그렇다면 왜 오차가 누적되는냐 ? 라는 대답은 주변환경과 조도의 변화(Changes in illumination)에 따라서 센서 관측치(Observation)에 대한 Noise 또는 Ambiguity 가 존재 한다라는것이다. 사실 이거의 예가 올바를지 모르지만, 일단 클래식한 컴퓨터 비전 알고리즘을 사용한 예를 들자면, 사진과 영상은 빛에 너무 영향을 받기 때문에 Edge Detection 과 Face Recognition 이 Fail 할 가능성이 높다.

그렇다면, Visual-SLAM의 기법은 3가지로 나누어진다고 한다. 기하학적인 기법(Geometry), 학습을 이용한 기법, 두가지를 사용한 하이브리드 기법이 있다고 한다.

기하학적인 방법

이 Paper 에서 말한 기하학적인 방법의 배경설명은 이렇다. “임의의 환경에서 획득한 영상 Sequence 로 부터 기하학적 계산을 통해 카메라의 위치 및 3차원지도를 생성하면서 발생하는 오차 누적을 줄이기 위한 방법” 일단 기하학적으로 계산을 한다는 거 자체가 Overhead 가 있지 않을까라는 생각과도 잠시 Optimization 기법이 있다고 해서 안심했엇다. 이 오차 누적을 줄이기 위해서는 크게 Filtering 과 Optimization 기법이 있다고 한다.

Filtering Method

Filtering Method 의 방식은 카메라 자세와 3차원 지도에 대한 확률분포를 영상 데이터를 획득할 때마다 새롭게 갱신하는 방법으로 확률분포의 정의에 따라서 Kalman Filter 와 Particle Filter 의 기법으로 나누어진다고 한다. 여기서의 카메라의 위치는 로봇의 그 자체가 될수 있다라는것도 주의해볼만 하다. 여기서 내리는 Kalman Filter 의 정의는, 카메라의 자세와 지도를 구성하는 3차원 Landmark 의 위치를 가우시안 분포로 가정하고 영상 데이터를 획득할 때마다 가우시안 분포를 표현하는 평균 벡터와 공분산을 새롭게 갱신하면서 SLAM을 수행한다고 한다. 사실 Kalman Filter 의 정의와 Method 는 잘 알고 있었다. u 값과 sigma 값을 로봇의 위치가 update 할때마다, 두개의 Gaussian Distribution 을 보며, 평균을 구하는 정도의 Background 는 얼추 알고 있었다.

여기서 새롭게 나온 Method 를 인용했었는데, 꼭 읽업봐야겠다 라는 생각이 들었다. Unscented Kalman Filter[Robust Real-Time Visual SLAM using Scale Prediction and Exemplar Based Feature Description] 또 Particle Filtering 의 예시로 보여준 Rao-Blackwellized Particle Filtering 과 Key Frame Method 를 사용해서 성능과 처리 속도를 개선했다고 하는 [Bayesian Filtering for Keyframe-based visual SLAM] 이라는 Paper 를 꼭 읽어봐야겠다.

Optimization Method

Optimization method 는 크게 두가지로 표현된다고 하였다.

1. 영상으로부터 특징점을 추출하고 이를 영상 Sequence 에서 추적하여 초기 카메라의 위치를 계산하고, 3차원 지도를 생성한다. 그리고 3차원 지도를 구성하는 Landmark의 위치들은 카메라의 추정된 자세로 투영(Reprojection)시켜서 영상으로부터 추적된 특징점의 좌표와의 거리를 최소화 하도록 update 한다라는 것이다. [A Versatile and Accurate Monocular SLAM System]
2. 두 장의 영상으로부터 카메라의 움직임과 환경에 대한 3차원 정보를 획득하기 위해서 첫 번째 영상을 두 번째 위치에서의 영상으로 변환하였을대 실제 획득한 두 번째 영상과의 밝기 차이를 최소화하도록 최적화를 수행하여 개선하는 Direct SLAM 기법이 있다고 한다. [Direct Space Odometry]

사실 Optimization Method 란, 내 생각에는 어느 한 domain 을 기준으로 해서, 문제를 Optimization 하는것 같다. 생각을 해보면 첫번째 방법은 특징점을 추출하고 3D Map 을 만들어서, 다시 재투영한 결과의 Map 과의 차이점을 최소화하는 기법인것 같고, 두번째는 두개의 카메라를 사용해서, 실제 Pixel Intensity 의 차이를 가지고 최소화 하는것 같아 보였다.

특징점 기반 즉 첫번째 기반 같은 경우 영상에서 특정 화소들을 이용하여 카메라 위치를 추정하고 3차원 지도를 생성함으로써 빠르다는 장점이 있다고 한다. 그리고 특징점의 False Matching 으로 발생되는 문제들을 RANSAC(Random Sample Consensus) 기반의 방법을 활용하여 제거 하는 것이 가능하다고 한다. RANSAC 같은 경우는 내가 급히 SLAM 이 쪽으로 취직방향을 잡기 위해서, 잠깐 공부했었는데 역시 쉽게 얻어가는건 쉽게 잊혀진다고 하지 않았나 싶다.

두번째 기법인 Direct SLAM 기법은 처리속도가 느리나 환경을 조밀하게 모델링하는게 가능해서, 특징점이 없는 균질한(Homogeneous) 한 환경에서 성능이 우수하다고 하였다.

Deep Learning Based Visual SLAM

사실, 여기에도 굉장히 관심이 많다. Computer Vision 을 공부하면서, 여기에 답이 있다고 생각을 많이 했었다. 하지만, 딥러닝이 풀수 없는 문제도 정말 많다. 앞서 말했다 싶이 illumination 문제는 너무나도 사진이나 영상에 치명적인 오차를 준다고 개인적으로 생각하기 때문에, 어떻게 문제를 풀어갈지도 너무 궁금하다.

여기서 말하는 딥러닝 기반의 알고리즘은 이렇게 표현했다. “딥러닝 기반 알고리즘의 경우 학습된 지식을 통해 응용 분야에 맞게끔 모델을 자동으로 설계한다.” 이러면서 딥러닝의 강점인 특징을 이야기했는데, “학습 기반 방법의 장점은 복잡한 모델과 고차원의 특징 정보들을 사람의 정의 없이 학습 데이터로부터 자동으로 계산할 수 있으므로 다양한 환경 변화 및 특징 정보가 부족한 환경에서도 강인성 을 확보 할수 있다.” 최근들어서 머신러닝, 딥러닝 분야가 확실히 뜨고 있는건 사실이다. 하지만, 불확정한 학습데이터와 모델을 설명할수 없는(unexplained 된 Deep Learning Model) 이 정말 많고, 배우는데 많이 기초가 잡혀지지 않을수 있다.

딥러닝 기반의 SLAM 기술들은 크게 Odometry 추정과 Mapping 으로 분류 된다고 한다. Odometry 추정은 두 영상 사이의 상대적인 자세 변화를 추정하는 기술이고, Mapping 은 주변 환경에 대한 공간 모델을 생성하는 것을 의미한다고 말한다. [A Sruvey on Deep Learning for Localization and Mapping: Towards the Age of Spatial Machine Intelligence]

난 처음에 Odometry 라는 영단어가 쉽게 들리면서, SLAM 의 개념적으로 어떻게 적용(Apply)이 되는지 몰랐었다. 그래서 여기서 한번 정의를 내리자.

What is the Odometry ?

앞서 말했다싶이 Odometry 는 예를 들어서, 우리가 자동차를 타다 보면, 앞에 속도와 주행거리를 나타내주는 계기판이 있다. 여기서 주행거리를 보여주는 작은 장치를 Odometry 라고 한다. 또한 이걸 주행 기록계 라고 한다. 그렇다면 어떻게 이게 Robotics 와 SLAM 에 연관된다라는게 나의 큰 질문이다.

왜 Odometry 와 SLAM 이 연관 되느냐. 일단 Odometry 를 로보틱스에 관점을 들자면, 일단 차의 바퀴가 회전할 것이다. 그렇다면, 바퀴의 회전수에 따른 주행거리를 구할 수 있는 Parameter 가 생긴다. 이 후 주행거리를 구하기 위해서 이 값에 바퀴의 둘레를 곱하여 측정하는 것이다. 그리고 단순히 주행거리만 측정하는 것 뿐만 아니라, 로봇 또는 자동차가 갔었던? 주행했었던? 전체적인 궤적을 구할수 있다. 그렇다면, 로봇의 위치는 어떻게 구할수 있는건가? 로봇의 완전한 위치를 알려주는 벡터값 [x^t, y^t, z^t, a^t, b^t, r^t] 가 있다고 한다. 여기서 a(alpha), b(beta), r(gamma) 는 오일러 각이라고 알려져 있고, x, y, z 는 Cartesian Coordinate 정보라고 한다. 즉 Odometry 추정이라는 건, 로봇이 주행한거리를 추정 하는거 뿐만아니라 로봇이 움직였던 궤적을 추정할수 있다는 것이다.

Odometry 추정

딥러닝 기반의 Odometry 추정 기술은 지도 학습과 비지도 학습으로 분류 된다고 한다. 지도 학습은 연속적인 영상과 그에 대응하는 카메라 자세 변화에 대한 학습데이터가 존재하는 경우, 입력 영상에 대한 자세 변화의 출력을 제공하는 end-to-end 딥러닝 기술이라고 한다 지도 학습 기반의 방법으로 영상에서 특징 정보를 추출하기 위한 CNN(Convolutional Neural Network)와 순차적 자세 변화 추정을 위한 RCNN(Recurrent Convolutional Neural Network) 를 이용하여 입력 영상 sequence 에 대한 카메라 자세를 출력하는 기술이 제안되었다고 한다. 역시 영상 sequence 라는 건 시간(t) 가 하나의 Parameter 또는 dependent 한거니까, RCNN 을 써야 한다는 생각이들었다. [Towards End-to-End visual Odometry with Deep Recurrent Convolutional Neural Network]

비지도 학습 기반의 방법은 주어진 영상 sequence 에 대한 자세 학습데이터가 없는 경우 depth 정보를 추출하고 자세 변화를 추정하기 위한 딥러닝 기술로서 계산된 자세 변화와 depth 로 부터 다른 시점의 영상을 합성하여 그 시점의 실영상과 비교를 통해 손실함수를 정의하고 학습한다.[Unsupervised Learning of Depth and Ego-Motion from Video]. 사실 이 Paper 는 굉장히 유명하다. 특히나 Unsupervised Learning 을 사용해서, Depth 를 추정하는것도 굉장히 흥미로웠던 논문이다.

Mapping

Mapping 이란 센서 데이터를 이용하여 주변 환경에 대한 3차원 형상 또는 구조를 표현하는 기술로서 지도를 구성하는 기본 요소에 따라서 depth, point, mesh, voxel 로 표현 한다고 한다. 사실 Point Cloud 라는 말은 흔히 들어봤다. 그리고 이게 실제 Mapping 하는 기술에도 많이 쓰인다고 종종 들었다. 영상 정보로부터 커리를 획득하는 방법은 Streo Camera 를 사용하거나 Video Sequence 를 사용하는 게 일반적이었으나 최근 Monocular Camera 로부터 depth information 를 추출할 수 있는 딥러닝 기술들이 활발히 연구되고 있다고 한다. Depth 생성 기술은 지도학습 또는 비지도학습으로 나누어진다고 한다. 대표적인 Paper 는 [Depth map prediction from a single image using a multi-scale deep network] and [Unsupervised monocular depth estimation with left-right consistency]. 사실 첫번째 Paper 같은 경우, 되게 많이 사용된다. 내가 첫 Conference 를 갔었을때 Human Right 에 관했던 Conference 였는데, Human Trafficking 을 방지하고자 이 비슷한 Architecture 을 통해서 인권매매를 하는 호텔들이 어디에 있는지 추측하는 그런 interesting 한 발표가 있었었다. The second paper is also very popular when it comes to depth estimation by using the monocular camera.

지도 학습 방법은 방대한 양의 영상과 해당 depth information 를 학습하여 입력영상으로 부터 바로 depth 를 예측하는 기술로 전역과 지역적으로 depth 를 예측하는 두개의 Network 를 사용하여 정확도를 개선하는 기술이 제안되었다고 한다. [Depth map prediction from a single image using a multi-scale deep network]. 하지만, 늘 말하지만 딥러닝은 도깨비 방망이가 아니듯이, accurate depth video sequence 를 확보하는게 어렵다. 이 문제를 해결하기 위해 비지도 학습 방법에서는 depth sequence 대신에, stereo camera 로 부터 획득한 영상을 학습 데이터로 활용한다. 구체적으로는 왼쪽 영상을 오른쪽 영상으로 변환하기 위해서 disparity와 오른쪽 영상을 왼쪽 영상으로 변환하는 시차를 계산하고 이른 왼쪽-오른쪽 일관성(left-right consistency) 제약조건을 이용하여 네트워크를 구성함으로써 향상된 Depth Map 을 생성했다. 사실 disparity 를 이용해서 딥러닝 문제를 푸는건 굉장히 많은데에서 사용된다. 내가 처음에 일했었던 교수는 protein depth map 를 deep learning 을 사용해서 만들었었는데, 이때 disparity map 을 사용하면서, protein contact map 을 만드는데 성공했었던게 기억이 난다.

Hybrid Visual SLAM Method

여기서 말하는 하이브리드 방식은 Visual SLAM 을 구성하고 있는 여러 단계 중 일부를 딥러닝 방법으로 계산하고 다른일부는 고전적인 기하학적 방법을 활용한다. 딥러닝 기반의 방법은 영상에서 특징 정보를 추출하기 어려운 환경에서 더 나은 결과를 제공하지만, 특징 정보가 풍부한 환경에서는 고전적인 방법의 성능이 우수하다. 사실, 이거에 대한 합리적인 의심이 들지만, 꼭 기하학적인 방법으로 한번 구현해봐야겠다라는 생각이들었다. 이 Paper [Scale recovery for monocular visual odometry using depth estimated with deep convolutional neural fields] 에서는 monocular visual odometry 를 deep learning based method 로 풀어 냈었고, 입력 영상으로부터 자세 변화를 추정하는 부분을 기하학적 Odometry 추정방법을 채택하였다고 한다. 생성된 초기 depth 와 Camera Pose 는 CRF(Conditional Random Field)를 이용해서 정확도를 향상시켰다고 한다.

또 다른 Paper [Visual Odometry revisited: What should be learnt?] 에서는 depth 와 optical flow 를 딥러닝 기반의 학습으로 부터 계산을 하고, 이 결과물을 기하학적 odometry 알고리즘에 적용하여 카메라의 자세 변화를 추정하였다. 또 다른 방법으로는 딥러닝 기술로 부터 움직이거나 또는 변화가 있는 부분을 검출하여 기존 특징점 기반과 Direct. SLAM 의 성능을 개선하는 방법도 제안되었다고 한다. [Driven to distraction: self-supervised distractor learning for robust monocular visual odometry in urban environments].

최근에는 딥러닝 기술과 기존 필터링 기반의 방법이 융합된 SLAM 기술로서 칼만 필터와 입자 필터를 딥러닝으로 학습하는 기술이 개발됬다고 한다. [Backprop kf: Learning discriminative deterministic state estimators] and [Differentiable SLAM-net: Learning Particle SLAM for Visual Navigation]

사실 이 Paper 를 읽고 많은 흥미로운 사실과 더 공부해야할 이유 또는 motivation 이 생겼다. SLAM 이 어려운 학문이고, 정말 Fusion 음식같이 어렵고, 복잡한것 같다. 풀기 위한 방법은 여러가지 일것 같으며, 어떤 problem domain 인가에 따라서 새로운 문제를 풀수 있다라는 걸 느끼게 되었다.

Reference :

1. Visual SLAM 기술개발 동향 - 김정호(한국전자기술연구원)
2. 초보자를 위한 Visual Odometry - 시작부터 튜토리얼 까지

벌써 이 블로그에 글을 쓰는게 Log 를 쓰는게 한달이 훌떡 지나버렸다. 정말로 한국으로 오면서 많은 일들이 있었고, 적응하기도 너무 애매해서 힘들었었다. 그리운 사람도 있고 정말 보고싶은 사람도 있다. 이 감정때문에 우울감에 살짝 빠져있었지만, 주변에 탄천에 걸어가면서 Spotify 에 마음에 드는 노래를 Playlist 에 넣는것도 나의 행복의 일부분이 되어버렸다. 그리고 최근에 직장인 밴드부 단체 톡방에도 가입을 했다. 아직 사람을 만나는 건 불편하지만, 점점 내 스스로가 낳아지길 기다리고 기대한다.

일은 참 여러가지로 지금 정말 좋다. 모르는걸 배우고, 다른 사람의 생각들을 배우고, 듣고, 이야기하는게 즐겁다. 또 프로젝트 진행도 가끔씩 멈출때가 많지만? 그래도 해결해 나가는 나의 모습을 보면 자랑스럽기도 하면서도, 회사가 너무 좋아졌다. 물론 나의 한계? 인내심? 이런걸 마주보게 되지만. 이게 사실은 맞는길로 가고 있다라는 생각이든다. 책상에 적어 놓은 노트에도 “좋은 Researcher 그리고 Programmer 가 되려면, 꾸준히 오래, 열정히 식지 않게 달려가자” 라는 문구를 써놓았지만, 아직 해놓지 못한 일들이 많다. 하지만 열심히 해야겠다라는 나의 마음은 아직도 있으며, 이게 쫓기고 가는 길이 아니였으면 하는 바램이 든다.

오늘, 나는 월급을 받고 순천 집에 내려가고 있다. 노래를 들으면서, 많은 여러 생각이 든다. 슬프지만 웃어야 된다 라는 느낌이 정말 크다. 하지만 어쩔수 없지 않겠는가? 지금부터 시작이고, 천천히 만들어나가는게 맞지 않을까? 처음부터 잘하는 사람없고, 실수 안하는 사람 아무도 없을 것이다. 그러기 때문에 포기라는 단어는 아쉬운것이고, 도전이라는 생각밖에 안든다. 항상 내 주변에 또는 내 바운더리에 있는 사람을 사랑하고 아끼고, 이쁜 말 해주고, 들어주고, 그런 삶을 살아야겠다. 돈은 차츰차츰 천천히 벌고, 구지 내 욕심 부리지말고 천천히 배타는 듯 그렇게 시간이 갔으면 좋겠다. 아직 3 개월 차 한국, 모든게 새롭고 어렵지만, 천천히 좋은 날로만 가득하길 바란다.

If you want to listen to my playlist on Spotify, This is my spotify link : Nick J’s Playlist

오늘은 조금 다르게 빵에다가 Bluberry Jam 을 발라서 먹었다 (아침은 먹는게 좋다는게 사실이다.) 여전히 오늘도 똑같은 거리를 걸으면서, 회사에 도착했다. 나름 오늘은 어제와는 다르게, 조금 열심히 더 해야겠다 라는 마음을 가지게 되었다. 하지만 아침에 먹은게 너무 배불러서 뭔가 배운다는 느낌이 안들고 졸렸다. 한참을 VirtualBox로 Ubuntu 로 끄적끄적 만지고, 어떻게 내 자기 소개를 할까 고민하다가 벌써 점심시간이 다가왔었다. 오늘은 나와 같은 전문연구요원으로 일하고 계신분에게 점심을 먹자고 이야기를 하려고 했지만, 팀장님과 열심히 이야기하길래. 그냥 혼자 집에서 밥을 먹어야겠다며, 집에서 볶음밥과 계란에 밥을 먹었다. 밥을 먹는 시간이 생각보다 짧다라는 생각이 들을 때쯤 나는 이미 밖에 나와있었고, 회사를 가고 있었다.

오후에도 열심히 다짐하며 회사 내에 있는 커피를 먹었음에도 불구하고 이놈의 밥먹고 졸린 현상은 나를 미치도록 했다. 분명 회사가 개발중인 정밀지도를 만드는 software 에 대한 어느정도 이해가 필요 했었고, 그거에 대한 세미나를 찾아서 들었었다. 웬지 모르게 느낌이, 아 여기는 혼자서 다 해야겠구나 따른 train 을 결정하는건 나의 자유구나 라는 느낌을 받았었다. 장점과 단점이 많은 혼자 배우는게 아직은 낯설었지만 그래도 세미나를 듣고, 노트에다가 개념을 써내려갔다. 실질적으로 아직은 적응을 잘못했지만, 실무적으로 뭔가를 해봐야겠다는 느낌이 많이 들었고, 지금 개발중인 코드를 보니 너무 어렵게 다가왔었다. 수많은 코드와 oop 를 사용한것들이 보이니까 어디서 어디까지가 definition 인지 모든걸 이해하지 못했지만, function name 들을 대충보니 약간 짐작같는게 맞는지도 하는 확신이 들긴들었다.

아직은 나에게 그런 큰 개발은 너무 어렵게 다가와서, 휴대폰으로 facebook 을 하다가 이러한 글을 보았다. “어떻게 좋은 개발자가 될까?” 라는 글을 읽게되었는데, 다읽지는 못하고 이런 문구만 머리쏙에 떠올리게 된다. “Make it work, Make it right, Make it fast” 이 문구에 동기부여를 해서, 일단 OpenCV 를 회사 컴퓨터에 설치하고, 나는 퇴근을 하였다.

오늘도 피곤한 하루 였고, 뭔가 한거 없었지만, productive 하려고 노력한 모습에 나를 칭찬하며, 내일도 또 행복하고 알찬 하루를 보내야겠다.