Introduction

• Visual Slam은 모바일 로봇 혹은 Mobility 능력을 갖춘 기계 시스템이 Lidar, Ladar, Camera, Ultra sonic 등과 같은 센서들을 이용하여서 물체 인식 및 Robot Localization(현지화), Building a Map 등을 이루게 만드는 기술이다.

• 특히 모바일 로봇틱스에서 많이 이용이 되는데, 모바일 로보틱스가 자율 주행을 하기 위해서는 아래와 같은 2개가 중요하다.

  • Localization
  • Mapping

Simultaneous Localization and Mapping

• Visual Localization
  • 로봇에 장착된 센서만 이용(외부 장치 X)
  • GPS가 잘 작동하지 않는 환경

• Mapping
  • 사전에 주변 환경이 만들어지지 않은 상태에서 주변환경(mapping and Building a Map)
  • 경로 계획에 대한 정보를 제공

Various Localization methods

• 가이드 레일, QR코드 GPS 센서
  • 실제로는 가이드 레일, QR 코드를 놓을 수 없는 경우가 많음
  • GPS 전파가 잘 닿지 않는 곳이 있음(실내, 도심지역)
  • 신뢰할 수 있지만 범용적이지 못함
  • 환경적인 제약이 존재
• Wheel Encoder, 카메라, Lidar, Ladar, IMU센서
  • 환경에 대한 간접적인 물리량을 측정
  • 환경에 대해 추가적인 설치 없이 위치 추정 문제 해결
  • 환경적인 제약이 있음
• Visual Slam
  • 카메라 센서를 주로 이용한 위치 추정 및 지도 작성 방법
• 카메라의 동작 방식에 따른 분류
  • 단안 카메라, 양안 카메라, 깊이 카메라

단안 카메라(Monocular Camera)

• 한개의 카메라를 움직여 물체까지 거리 추정 (Frame 별로 depending on Time)
• 깊이 추정 알고리즘(PnP, 3D-2D, Fundemantal Matrix, Essential Matrix)를 이용하여 각 픽셀의 시차(dispartiy)를 계산

• 영상에서 Feature point를 추출하고 영상간의 Feature point 매칭을 통해 3차원 포인트를 계산(추정 알고리즘)

• 장점
  • 다른 방법들에 비해 간단
  • 계산량이 적고 실시간에 적합
• 단점
  • Dispartiy는 계산할 수 있지만 실제적인 Depth는 알 수 없음
    • Baseline 부재(RGB-D카메라에는 두개의 단안 카메라로 이루어져있어 기본적인 Baseline이 이있어 Feature Point를 이용한 더 정확한 3D point를 생성할 수 있다.)
  • 정확한 Scale 정보를 알 수 없음.

양안 카메라(Stereo Camera)

• 거리가 고정된 두 개의 단안 카메라를 이용하여 물체까지 거리 측정

• BaseLine: 두카메라 사이에 고정된 거리
  • 베이스 라인이 멀 수록 먼 거리를 측정 가능
  • 깊이 추정 알고리즘을 이용하여 3D point 구현 및 맵핑 가능
• 장점
  • 단안 카메라 경우 보다 정확한 위치 추정 능력
  • Dense한 맵 생성 가능
• 단점
  • 스테레오 매칭 알고리즘의 계산이 복잡
  • 조명 변화에 취약

깊이 카메라(RGB-D Camera)

• 적외선(IR) 구조광 방식 또는 레이저 광선의 비행 시간을 측정해 깊이를 예측
• 현재 일반적으로 사용되는 깊이 카메라
  • Kinect V1, Kinect V2
  • Xition Pro Live
  • Intel RealSense
  • Google Tango

• 장점
  • 비교적 정확한 깊이 값 예측이 가능
  • Dense한 맵 생성 가능
• 단점
  • 좁은 측정 범위
  • 작은 시야각
  • 반사, 투과성 재질의 물체 깊이 측정 불가
  • 주로 실내 으용에서 사용됨.

Lidar(센서)

• 레이저 광선의 비행시간을 측정해 깊이를 예측
• 측정 가능 거리 및 공간 분해능이 높음

• 종류
  • 2D lidar/ 3D lidar
  • Spinning/Solid-State
• 주요 회사
  • Velodyne
  • Robosense
  • Ouster
  • SOSlab

전통적인 Visual SLAM 프레임 워크

• Sensor Input(Lidar, Camera)
  • Depth 이미지나 RGB이미지를 이용하여, intensity나 feature based extraction feature 포인트의 기술을 사용하여, 추적알고리즘을 통해 Visual odometery 구함
• Visual odomtery
• Backend Optimization
  • Bundle adjustment(BA)를 사용하여서 Localization을 업데이트 한다.
  • Graph based slam Optimization
• Loop Clousure detection
• Mapping

Visual odometery

• Fronted 단계
• 인접한 이미지 사이의 카메라 움직임을 통하여 Camera pose 구함
• 카메라와 3차원 공간 점 사이의 기하학적 관계(multi-Geometry)를 이용
  • Feature Point(2D)를 3D 포인터로 생성
• Drift Error
  • Visual odometry만 이용하여 궤적을 추정하면 에러가 누적도미
• 해결책
  • Bacekend Optimization과 Loop Closure Detection 필요

  

Backend Optimization

• Sensor noise
  • 정밀한 센서라도 노이즈는 있기 마련
  • 저렴한 센서는 측정(Measurement) 오류가 큼
  • 일부 센서는 자기장과 온도에 영향을 받음
• Backend Optimization
  • 노이즈가 많은 데이터로부터 전체 시스템의 상태를 추정하는 방법(state estimation)
  • Fronted에서 발생한 Drift 에러를 제거
• Fronted에서는 backend에 최적화 할 데이터와 데이터의 초기 값을 제공
• Backend 최적화 종류
  • 필터 기반(Kalman filter, Particle Filter)
  • 비선형최적화 기반
    • Bundle Adjustment : 카메라 포즈와 3차원 포인트 재조정
    • Pose graph optimization 맵포인트를 고려하면 계산량이 커지므로 pose만 고려하는 방법

Loop Closure Detection

• 현재 위치가 이전에 방문한 곳인지를 판단
• QR 코드 활용
  • 환경적인 제약이 존재
• 카메라 영상을 활용
  • 이미지간의 유사성을 판단(BoW(Bag of words))
  • Backend에서는 루프 폐쇄에 대한 정보를 받아서 위치 추정과 지도 작성에 반영
  • Drift 에러를 제거하고 전역적으로 일관된 맵으 생성

Mapping

• 환경 맵을 만드는 과정(Building a MAP)
• 응용프로그램에 따라 다르게 구현
  • 무인 청소 로봇
    • 2차원 지도로 충분
  • 자율주행 드론
    • 6DOF 이므로 3차원 지도가 필요
• Map Representation
  • Pointcloud
  • Voxel(volume matrix)
  • Surfel
  • Occupancy grid map
• 맵 표현 밀도에 따른 종류
  • Sparse, Dense, Semi-dense Map

Modern State of the Art System

• Sparse SLAM
  • only use a small selected subset of the pixels(features) from a monocular color camera
  • Fast and Real time on CPU but it produces a sparse map(point clouds)
    • point clouds는 sparse information이다.
  • Landmark-based or feature-based representations
• ORB-SLAM
  • one of the SOTA frameworks in the sparse SLAM category
  • Complete SLAM system for monocular camera
  • Real-time on standard CPUs in a wide variety of environment.
    • small hand-held indoors
    • drones flying in industrial environments
    • cars driving around a city

• Dense SLAM
  • using RGB-D camera
  • Use most of all the pixels in each received frame
  • or use depth images from a depth camera
  • it produces a dense map but GPU acceleration is necessary for the real time operation
  • Volumetric model or surfel-based representation
• InfiniTam
  • one of the SOTA frameworks in the Dense SLAM category
  • Multi-platform frameworks for real-time, Large-Scale Depth fusion and tracking
  • Densely Reconstructed 3D scenes

• Direct Method(semi-Dense SLAM)
  • make use of pixel intensities directly
    • intensity 차이를 통해 Mapping
      • Warping을 통해 시점을 갖다 붙인다.(가장 작도록하여서 update)
  • Enable using all information in the image
  • it produces a semi-dense map
  • Higher accuracy and robustness in particular even in environments with little keypoints
• LSD SLAM
  • Highly cited SLAM framework in the direct method SLAM category
  • Large-scale, consistent maps of the environment
  • Accurate pose estimation based on direct image alignment.

• Lidar SLAM
  • Make use of the Lidar sensor input for the localization and mapping
  • Autonomous driving purpose-oriented in outdoor environment
    • Lidar odometery maaping
• LOAM
  • One of the SOTA frameworks in the lidar SLAM category
  • Very low drift error using the edge and planar features
  • Low computation complexity
• 두 SLAM 기술을 통틀어 VLOAM이라고도 불림

SLAM 문제의 수학적 표현

• Motion Model
  • Control input such as Velocity, IMU
  • 위와 같은 Velocity가 input으로 들어오고 hardware를 통해 출력이 될떄 로봇 위치가 어떻게 변하는지 표현 하는 것
  • Such as Wheel odometer encoded from wheel odometer encoder and predict a robot pose in an environment.
  • Velocity값을 이용하여 robot statement(x,y,z)값을 구하는것

• Sensor Model
  • 랜드마크가 로봇에서 어떻게 관찰되는지 표현
  • such as visual odometer from Tracking algorithm by Camera sensor.
  • Landmark를 통해 로봇 statement(x,y,z)를 구하는 것.

Motion Model

• 로봇이 현재 위치에서 컨트롤 입력(e.g velocity) 받았을때 새로운 로봇 위치 예측
• Motion model 수학적 정의
  • x_f = f(x_k-1, u_k-1, w_k)
  • f() : Motion Model을 나타내는 함수
  • u_k : 모션 센서 및 컨트롤 입력 받은 값
  • w_k : Motion model에 대한 노이즈
• Motion Model로 부터 구해지는 x,y,z 값은 Kinematic formular를 통해서 구해진다.

• Example
• 평면에서 움직이는 청소 로봇의 경우

Sensor Model

• 로봇이 위치에서 어떤 랜드마크(extracted feature point)를 볼때 관측 데이터(x,y,z of extracted feature point)가 생성되는 것을 표현
• Sensor Model의 수학적 정의
  • z_kj = h(y_j, x_k, v_k, j)
  • h() : Sensor Model을 나타내는 함수
  • y_j : 랜드 마크
  • x_k : 현재 로봇 위치
  • Z_kj : 랜드마크의 관찰 값(x,y,z of extracted feature point)
  • v_kj : Sensor model에 대한 노이즈
• Example
  • 평면에 움직이는 청소 로봇의 경우

SLAM의 상태 추정 문제(State estimation)

• 모션 모델과 센서 모델 필요
  • x_f = f(x_k-1, u_k-1, w_k)
  • z_kj = h(y_j, x_k, v_k, j)
• 선형인가 비선형인가?
• 초기 SLAM 문제는 Extended Kalman Filter를 이용
  • Talyor expantion으로 선형화 한다(근사화)
• EFK SLAM의 단점
  • 선형화 과정에서의 오차
• Particle Filter, 비선형 최적화 방법을 사용하기 시작
• Graph 기반의 SLAM 방법이 주류를 이룸
  • Large Scale에 적합

Reference

SLAM KR 视觉SLAM书

Generic Programming

• Generic programming: separate algorithms from the data type
• Cup holds any type T, e.g. Coffee or Tea

Template functions

• Generic programming uses keyword template

  template <typename T, typename S>
  T awesome_function (const T& var_t , const S& var_s) {
  // some dummy implementation
  T result = var_t;
  return result;
  }
  

• T and S can be any type that is:
  • Copy constructable
  • Assignable
  • Is defined (for custom classes)

Explicit type

• If the data type cannot be determined by the compiler, we must define it ourselves

template <typename T>
T DummyFuncion(){
  T result;
  return result;
}
int main()
{
  DummyFuncion <int>();
  DummyFuncion <double>();
  return 0;
}

Template Classes

• Similar syntax to template functions
• Use template type anywhere in class

  template <class T>
  class MyClass
  {
  public:
  Myclass(const T& smth) : smth_{smth}
  private:
  T smth_;
  }
  int main()
  {
  MyClass<int> my_object(10);
  MyClass <double> my_double_object(10.0);
  return 0;
  }
  

Template specialisation

• We can specialize for a type
• Works for functions and classes alike

// Function definition
template <typename T>
T DummyFuncion(){
  T result;
  return result;
}
template <> // all give what i want type
int DummyFuncion(){ return 42;}
int main()
{
  DummyFuncion <int>();
  DummyFuncion <double>();
  return 0;
}

Template meta programming

• Templates are used for Meta programming
• The compiler will generate concrete instances of generic classes based on the classes we want to use
• If we create MyClass and MyClass the compiler will generate two different classes with appropriate types instead of template parameter

Template classes headers/source

• Concrete template classes are generated instantiated at compile time
• Linker does not know about implementation
• There are three options for template classes:
  • Declare and define in header files
  • Declare in NAME.h file, implement in NAME.hpp file, add **#include ** in the end of **NAME.h**
  • Declare in * .h file, implement in * .cpp file, in the end of the * .cpp add explicit instantiation for types you expect to use
• Read More about it https://en.cppreference.com/w/cpp/language/class_template https://www.drdobbs.com/moving-templates-out-of-header-files/184403420

  Iterators

  STL uses iterators to access data in containers

• Iterators are similar to pointerss
• Allow quick navigation through containers
• Most algorithms in STL use iterators
• Access current element with * iter
• Accepts -> alike to pointers
• Move to next element in container iter++
• Prefer range-based for loops
• Compare iterators with ==, !=, <
• Pre-defined iterators: obj.begin(), obj.end()

  #include <iostream>
  #include <map>
  #include <vector>
  using namespace std;
  int main(){
    // Vector iterator.
    vector<double> x = {1, 2, 3};
    for (auto it = x.begin (); it != x.end (); ++it) {
      cout << * it << endl;
    }
    // Map Iterations
    map<int,string> m = {1,"hello"},{2,"world"}; // add {} cover the Rvalue. but somehow error in blog system, i just put that like this
    map<int,string>::iterator m_it = m.find(1);
    cout << m_it->first << ":" << m_it->second << endl;
    if (m.find (3) == m.end ()) {
      cout<<"Key 3 was not found \n"
    }
    return 0;
  }

Error handling with exceptions

• We can “throw” an exception if there is an error
• STL defines classes that represent exceptions. Base class: exception
• An exception can be ‘‘caught’’ at any point of the program (try - catch) and even ‘‘thrown’’ further (throw)
• The constructor of an exception receives a string error message as a parameter
• This string can be called through a member function what()

throw exceptions

Runtime Error:

// if there is an error
if (badEvent ) {
  string msg = "specific error string";
  // throw error
  throw runtime_error (msg);
}

Logic Error: an error in logic of the user

throw logic_error (msg);

catch exceptions

• If we expect an exception, we can ‘‘catch’’ it
• Use try - catch to catch exceptions

  try {
  // some code that can throw exceptions z.B.
  x = someUnsafeFunction (a, b, c);
  }
  // we can catch multiple types of exceptions
  catch ( runtime_error &ex ) {
  cerr << "Runtime error: " << ex.what () << endl;
  } catch ( logic_error &ex ) {
  cerr << "Logic error: " << ex.what () << endl;
  } catch ( exception &ex ) {
  cerr << "exception: " << ex.what () << endl;
  } catch ( ... ) {
  cerr << "Error: unknown exception" << endl;
  }
  

Intuition

• Only used for “exceptional behavior”
• Often misused: e.g. wrong parameter should not lead to an exception
• GOOGLE-STYLE Don’t use exceptions
• http://www.cplusplus.com/reference/exception/

Program input parameters

• Originate from the declaration of main function
• Allow passing arguments to the binary
• int main(int argc, char const * argv[]);
• argc defines number of input parameters
• argv is an array of string parameters
• By default:
  • argc == 1
  • argv == “"

#include <iostream>
#include <string>
using namespace std;
int main(int argc , char const *argv []) {
  cout << "Got " << argc << " params\n";
  string program_name = argv[0];
  cout << "Program: " << program_name << endl;
  for (int i = 1; i < argc; ++i) {
    cout << "Param: " << argv[i] << endl;
  }
  return 0;
}

Using for type aliasing

• Use word using to declare new types from existing and to create type aliases（别名）
• Basic syntax: using NewType = OldType;
• using is a versatile(通用的) word
• When used outside of functions declares a new type alias
• When used in function creates an alias of a type available in the current scope
• http://en.cppreference.com/w/cpp/language/type_alias

#include <array>
#include <memory>

template <class T, int SIZE >
struct Image{
  // Can be used in classes.
  using Ptr = std :: unique_ptr <Image <T, SIZE >>;
  std::array<T, SIZE> data;
}
// Can be combined with "template".
template <int SIZE >
using Imagef = Image<float,SIZE>;
int main(){
  // Can be used in a function for type aliasing.
  using Image3f = Imagef<3>;
  auto image_ptr = Image3f::Ptr(new Image3f);
  return 0;
}

OpenCV

• Popular library for Image Processing
• We will be using version 2 of OpenCV
• We will be using just a small part of it
• #include <opencv2/opencv.hpp> to use all functionality available in OpenCV
• Namespace cv::

Data types

• OpenCV uses own types
• OpenCV trusts you to pick the correct type
• Names of types follow pattern
  • **CV_**
• Example: RGB image is CV_8UC3: 8-bit unsigned char with 3 channels for RGB
• Example: Grayscale image is CV_8UC1: single 8-bit unsigned char for intensity
• Better to use DataType
• Example: DataType::type == CV_8UC1

Basic Matrix Type

• Every image is a cv::Mat, for ‘‘Matrix’
• Mat image(rows, cols, DataType, Value);
• **Mat_ image(rows, cols, Value);**
• Initialize with zeros:

  cv:: Mat image = cv:: Mat :: zeros (10, 10, CV_8UC3);
  using Matf = cv::Mat_ <float >;
  Matf image_float = Matf :: zeros (10, 10);
  

• Get type identifier with image.type();
• Get size with image.rows, image.cols
• I/O:
  • Read image with imread
  • Write image with imwrite
  • Show image with imshow
  • Detects I/O method from extension

cv::Mat is a shared pointer

• It does not use std::shared_ptr but follows the same principle of reference counting

  #include <opencv2/opencv.hpp>
  #include <iostream>
  int main () {
  using Matf = cv::Mat_ <float >;
  Matf image = Matf :: zeros (10, 10);
  Matf image_no_copy = image; // Does not copy!
  image_no_copy.at<float>(5, 5) = 42.42f;
  std::cout << image.at<float>(5, 5) << std :: endl;
  Matf image_copy = image.clone(); // Copies image
  image_copy.at<float >(1, 1) = 42.42f;
  std :: cout<<image.at<float>(1, 1) << std :: endl;
  return 0;
  }
  

• result

  c++ -std=c++11 -o copy copy.cpp \`pkg -config --libs --cflags opencv `
  

Imread

• Read image from file
• Mat imread(const string& file, int mode=1)
• Different modes:
  • unchanged: CV_LOAD_IMAGE_UNCHANGED < 0
  • 1 channel: CV_LOAD_IMAGE_GRAYSCALE == 0
  • 3 channels: CV_LOAD_IMAGE_COLOR > 0

#include <opencv2/opencv.hpp>
#include <iostream>
using namespace cv;
int main(){
  Mat i1 = imread("logo_opencv.png",CV_LOAD_IMAGE_GRAYSCALE );
  Mat_ <uint8_t > i2 = imread("logo_opencv.png", CV_LOAD_IMAGE_GRAYSCALE );
  std::cout << (i1.type () == i2.type ()) << std::endl;
  return 0;
}

imwrite

• Write the image to file
• Format is guessed from extension
• bool imwrite(const string& file, const Mat& img);

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
int main () {
  cv:: Mat image = cv:: imread("logo_opencv.png", CV_LOAD_IMAGE_COLOR );
  cv:: imwrite("copy.jpg", image);
  return 0;
}

Write float images to * .exr files

• When storing floating point images OpenCV expects the values to be in [0, 1] range
• When storing arbitrary values the values might be cut off
• Save to * .exr files to avoid this
• These files will store and read values as is without losing precision

  #include <iostream>
  #include <opencv2/opencv.hpp>
  #include <string>
  int main(){
  using Matf = cv::Mat_ <float>;
  Matf image = Matf:: zeros(10, 10);
  image.at<float>(5, 5) = 42.42f;
  std::string f = "test.exr";
  cv:: imwrite(f, image);
  Matf copy = cv:: imread(f, CV_LOAD_IMAGE_UNCHANGED );
  std::cout << copy.at <float >(5, 5) << std :: endl;
  return 0;
  }
  

imshow

• Display the image on screen
• Needs a window to display the image
• void imshow(const string& window_name, const Mat& mat)

  #include <opencv2/opencv.hpp>
  int main(){
  cv:: Mat image = cv:: imread("logo_opencv.png",CV_LOAD_IMAGE_COLOR );
  std :: string window_name = "Window name";
  // Create a window.
  cv::namedWindow(window_name , cv:: WINDOW_AUTOSIZE);
  cv:: imshow(window_name , image); // Show image.
  cv:: waitKey (); // Don't close window instantly.
  return 0;
  }
  

• OpenCV vector type: cv::Vec<Type, SIZE>
• Many typedefs available: Vec3f, Vec3b, etc.
• Used for pixels in multidimensional images: mat.at(row, col);
• 사진의 픽셀을 고르는데 사용된다.(single pixels)

#include <opencv2/opencv.hpp>
#include <iostream>
using namespace cv;
int main(){
  Mat mat = Mat::zeros (10, 10, CV_8UC3);
  std:: cout << mat.at <Vec3b>(5, 5) << std::endl;
  Mat_ <Vec3f> matf3 = Mat_ <Vec3f>::zeros(10, 10);
  std::cout << matf3.at <Vec3f >(5, 5) << std :: endl;
  return 0;
}

Mixing up types is painful!

• OpenCV trusts you to pick the type
• This can cause errors
• OpenCV interprets bytes stored in cv::Mat according to the type the user asks (similar to reinterpret_cast)
• Make sure you are using correct types!

#include <opencv2/opencv.hpp>
int main () {
  cv::Mat image = cv::Mat::zeros (800 , 600, CV_8UC3);
  std::string window_name = "Window name"
  cv::namedWindow(window_name , cv::WINDOW_AUTOSIZE );
  cv::imshow(window_name , image);
  cv:: waitKey();
  for (int r = 0; r < image.rows; ++r) {
    for (int c = 0; c < image.cols; ++c) {
      // WARNING! WRONG TYPE USED!
      image.at <float >(r, c) = 1.0f;
    }
  }
  cv:: imshow(window_name , image);
  cv:: waitKey ();
  return 0;
}

SIFT Descriptors

• SIFT: Scale Invariant Feature Transform
• Popular features: illumination, rotation and translation invariant (to some degree)

SIFT Extraction With OpenCV

• SiftFeatureDetector to detect the keypoints
• SiftDescriptorExtractor to compute descriptors in keypoints

// Detect key points
SiftFeatureDetector detector;
vector <KeyPoint> keypoints ; // 픽셀들을 모아놓는다 키포인트
detector.detect(input, keypoints);
// Show the keypoints on the image.
Mat image_with_keypoints ;
drawKeypoints (input , keypoints , image_with_keypoints );
// Extract the SIFT descriptors.
SiftDescriptorExtractor extractor ;
extractor .compute(input , keypoints , descriptors );

FLANN in OpenCV

• FLANN: Fast Library for Approximate Nearest Neighbors
• build K-d tree, search for neighbors there

// Create a kdtree for searching the data.
cv:: flann :: KDTreeIndexParams index_params ;
cv:: flann :: Index kdtree(data , index_params );
...
// Search the nearest vector to some query
Mat nearest_vector_idx (1, k, DataType <int >:: type);
Mat nearest_vector_dist (1, k, DataType <float >:: type);
kdtree. knnSearch (query , nearest_vector_idx , nearest_vector_dist , k);

OpenCV 2 with CMake

• Install OpenCV 2 in the system

  sudo add -apt - repository ppa:xqms/opencv -nonfree
  sudo apt update
  sudo apt install libopencv -dev libopencv -nonfree -dev
  

• Find using find_package(OpenCV 2 REQUIRED)

  find_package(OpenCV 2 REQUIRED )
  

• Include ${OpenCV_INCLUDE_DIRS}
• Link against ${OpenCV_LIBS}

  add_library(some_lib some_lib_file .cpp)
  target_link_libraries(some_lib ${OpenCV_LIBS})
  add_executable( some_program some_file .cpp)
  target_link_libraries( some_program ${OpenCV_LIBS})
  

  Additional OpenCV information

• Example project with additional information about using SIFT and FLANN can be found here:
  • https://gitlab.igg.uni-bonn.de/teaching/example_opencv
  • https://docs.opencv.org/2.4/modules/nonfree/doc/feature_detection.html

    Reference

    https://www.ipb.uni-bonn.de/teaching/modern-cpp/

Cpp Core Guidelines: https://github.com/isocpp/CppCoreGuidelines

Git guide: http://rogerdudler.github.io/git-guide/

C++ Tutorial: http://www.cplusplus.com/doc/tutorial/

Book: Code Complete 2 by Steve McConnell

Modern CMake Tutorial https://www.youtube.com/watch?v=eC9-iRN2b04

Compiler Explorer: https://godbolt.org/ Gdbgui: https://www.gdbgui.com/ CMake website: https://cmake.org/ Gdbgui tutorial: https://www.youtube.com/watch?v=em842geJhfk

Fluent C++: structs vs classes: https://google.github.io/styleguide/cppguide.html#Structs_vs._Classes

Array

int main()
{
  int A[5];
  int B[5] = {2,4,6,8,10};
  int i ;
  size_ = sizeof(B)/sizeof(B[0]);
  for (i=0; i<size_; i++)
  {
    std::cout<< i;
  }
}

Structure

• Defining Structure
• Size of structure
• Declaring a Structure
• Accessing Member.

struct Rectangle
{
  int length; // int is 4byte in c++
  int height;
};
int main()
{
  struct Rectangle r = {10, 5};
}

struct Rectangle
{
  int length; // int is 4byte in c++
  int height;
};
int main()
{
  struct Rectangle r; // Declare
  struct Rectangle r = {10, 5}; //ininitlaize
  r.length = 15;
}

Complex No

struct Complex
{
  int real; // 4byte
  int image; // 4byte
} // 8 bytes
struct student
{
  int age; // 4byte
  char name[25]; // char is 1 bytes , 25 bytes
  char dept[10]; // 10 bytes
  char address[50]; // 50 bytes
}// 89 bytes

Example

struct Card
{
  int face;
  int shape;
  int color;
}; // 12bytes
int main()
{
  struct Card c;
  c.face = 1;
  c.shape = 0;
  c.color = 0;
}

struct Card
{
  int face;
  int shape;
  int color;
}; // 12bytes
int main()
{
  struct Card deck[52] = {1,2,3}, {2,0,0}, ... ,{1,1,0},{2,1,0};
  std::cout << deck[0].face;
  std::cout << deck[0].shap;
  ...
}
// 원래는 deck Rvalue에다 {}를 더해야되는데 이상하게 blog에다 쓰면 오류 떠서 안됨..

pointers

• Declaration
• Initialisation
• Dereferencing
• Dynamic Allocation

• 포인터 특징
  • Accessing Heap
  • Accessing Resource (include extra program of extra device)
  • parameter passing

int main()
{
  int a = 10; // data variable
  int * p; // address variable, raw pointer
  p = &a;
  std::cout<< * p; // 10;
}

• Array using pointer

  int main()
  {
  int * a = new int[5]; // dynamic array
  }
  

Reference

int main()
{
  int a = 10;
  int &r = a;
}

• 레퍼런스 r은 stack에 카피되지 않고 a의 벨류를 받아쓴다. 즉 a = r이 된다.
  • Move 개념이다. 단 a=r는 똑같은 address 주소로 같은 밸류를 갖고 있다.
• 포인터는 오직 data type에 따른 메모리만 할당 된다. (bytes)

  int main()
  {
  int a = 10;
  int &r = a;
  cout<<a; //10;
  r++;
  cout<<r; //11;
  cout<<a; //11;
  }
  

pointer to structure

struct Rectangle
{
  int length; // 4bytes
  int height; // 4 bytes
}; // 8bytes
int main()
{
  struct Rectangle r={10,5};
  struct Rectangle* p = &r;

  r = length.15;
  p->length = 20;
  cout>>r.length<<endl; //20;
}

• when we create a pointer which is pointing to memory allocation of structure or class, we use “->” to pointing a data variable inside structure or class when we using a pointer.

• 포인팅하는 어드레스에다가 포인터에게 값을 넣어주면 그 address에있는 밸류값이 포인터에게 주어진 값으로 바뀐다.

• Modern C++(C++11부터)는 Smart pointer를 쓰인다, 왜냐하면 메모리 릭등 항상 dereferecing을 하기 귀찮고, 잘못되면 프로그램에 문제가 생기기 떄문이다.
  • #include
    • std::unique_ptr<>
      • 보통 Raw pointer로 많이 쓰인다.
    • std::share_ptr<>
      • 여러 포인터가 address를 공유할 수 있도록 한다.

Functions

• Parameter passing
  • pass by value
  • pass by Address
  • pass by reference.

Case 1(monolithic program)

  int main()
  {
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
    ---------------------
  }

Case 2 ( Modular Program, Procedeure program)

void func1()
{
  ---------------------
}
int func2()
{
  ---------------------
}
float func3()
{
  ---------------------
}
void func4()
{
  ---------------------
}
int main()
{
  fun1();
  fun2();
  fun3();
  fun4();
}

int add(int a, int b)
{
  int c;
  c= a+b;
  return(c);
}
int main()
{
  int x,y,z;
  x= 10;
  y= 5;
  z = add(x,y);
  cout<<z;
}

• int add는 proto type(즉 리턴값을 어떤 데이터 유형을 쓸것인지)
• int a, int b는 Funtion parameter
• add(x,y)는 Actual Parameter

int add(int* a, int* b)
{
  int c;
  c= a+b;
  return(c);
}
int main()
{
  int x,y,z;
  x= 10;
  y= 5;
  z = add(&x,&y);
  cout<<z;
}

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
using std::cout;
using std::endl;
int k;
int TwoSum(std::vector<int> M, int key)
{
    int size_ = M.size();
    std::unique_ptr<int[]> hash_table(new int[10]);
    for ( m : M)
    {
        hash_table[m] = 1;
    }
    for (int i =0; i<=size_;i++)
    {
        int diff = key - M[i];
        if (hash_table[diff] == 1)
        {
            k=i;
            return diff;
        }

    }
}
int main () {
    std::vector<int> A = {2,3,6,8};
    int sum =9;
    int result_index= TwoSum(A,sum);
    cout<<result_index<<" " <<k<<endl;

    return 0;
}

설명

• 벡터를 이용하여 Heap Memory 4개의 어레이에 value가 있다.
• 찾고자하는 합은 9이다.
• 인덱스들을 찾아라
• Hash Table을 이용하여 인덱스 구함

• A의 인덱스 벨류 값들을 Hash_table 행렬에다가 할당을 한다.(1로 표시한다.)
  • 즉 A[1] = 2이면, Hash_table[2] = 1로 업데이트 한다.

• 찾고자 하는 인덱스:
  • 우리가 찾고자 하는 값은 합이 9(sum)
  • 그렇다면 합-어레이[i] = 찾고자 하는 값
  • Hash_table[찾고자 하는 값]이 만약 ==1이라면, 즉 A어레이로부터 찾고자 하는 값이 존재한다면
  • 인덱스 값들을 return 한다.

Introduction to Algorithm

• Language
  • C
  • C++
  • Java
  • C#
  • python
  • Javascript
• Topics
  • Physical Data structure
    • Arrays
    • Matrics
    • Linked List
  • logical data structure
    • Stack
    • Queue
    • Trees
    • Graph
    • Hashing
  • Recursion
  • Sorting