꿈꾸는 개발자

Visual SLAM을 공부하다 보면 리 군과 리 대수에 대한 개념을 접하게 된다. 이는 매우 어려운 개념 중 하나인데, 최근 AI Robotics KR 스터디에 참여하게 되면서 자율주행을 위한 Visual SLAM 책을 토대로 4장 리 군과 리 대수에 대한 내용을 발표하게 되어 공부한 내용을 정리해보려고 한다. 본 포스팅은 Visual SLAM에서 다루는 내용만을 가지고 공부를 했기 때문에 보다 더 넓은 군론에 대한 개념을 보고 싶다면 BC Hall 저자의 Lie Groups, Lie Algebras, and Representations를 참조하기 바란다. 목차는 다음과 같다. 선행 지식 리 군과 리 대수는 무엇일까? SO(3), so(3) SE(3), se(3) 지수 매핑과 로그 매핑 리 대수 유도 ..

논문 제목 : KPConv : Flexible and Deformable Convolution for Point Clouds Introduction Kernel Point Convolution(KPConv)라는 point convolution 연산을 제안 KPConv는 3D filter로 이루어져있고, 이전 point convolution들의 한계점(네트워크 수렴의 어려움, 복잡성)을 극복 Euclidean space 상에서 kernel point와 가장 가까운 입력 포인트와 연산을 통해 특징을 추출함으로써 grid convolution보다 뛰어난 유연성을 갖고 있음 rigid KPConv와 rigid KPConv에 deformable을 추가한 deformable KPConv를 제안 rigid KPCon..

논문 제목 : Dynamic Graph CNN for Learning on Point Clouds Introduction point clouds의 high-level task를 CNN 기반의 EdgeConv라는 neural network module로 classification과 segmentation을 수행하는 DGCNN 모델을 제안 EdgeConv는 포인트와 그 포인트의 이웃간 관계를 설명하는 edge feature를 생성하는 모듈로 미분 가능하고 기존에 존재하는 아키텍쳐에 추가할 수 있음 OUR APPROACH DGCNN은 Edge 정보를 활용한 CNN과 비슷한 연산으로 특징을 추출하는 방식 DGCNN에서 주요 모듈로 EdgeConv가 존재하고, 이는 포인트와 인접한 포인트 간의 관계를 Edge로 ..

PointNet++ : Deep Hierarchical Feature Learning on Point Sets in a Metric Space Introduction PointNet은 각 포인트에 대해 특징을 추출하고 특징들을 모아 global feature를 생성하는데 이는 metric으로부터 유도된 local feature는 얻지 못한다는 한계점이 있어 이를 해결하기 위해 CNN과 비슷한 컨셉의 local feature를 학습할 수 있는 hierarchical neural network를 제안 PointNet++에서 두 가지 이슈를 다룸 어떻게 Point Cloud를 local region으로 나눌 것인가 Euclidean space 에서 Neighborhood ball 구조로 local region..

PointNet : Deep Learning on Point Sets for 3D Classification and Segmentation 논문을 보기 앞서 Point Cloud 데이터에 대한 특성을 알 필요가 있다. Point Cloud 데이터는 unordered(순서가 정해져있지 않음)하고 강체 운동에 불변하다. 이는 각 점들의 입력 순서를 변경하더라도 3D 객체나 형태가 변하지 않고 Point Cloud에 Transformation을 적용해도 3D 객체나 형태가 변하지 않는다는 것을 의미한다. 이러한 Point Cloud 특성을 반영해 논문에서는 permutation invariance 라는 단어를 사용하는데, 이는 Point Cloud의 점들이 어떤 순서로 입력되든지 간에 일관된 결과를 도출한다는..

시간 복잡도 - $ O(n\log(n)) $ 퀵 정렬 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미칠 수 있음.(최악의 경우 $ O(n^{2}) $) 피벗(pivot)을 설정해 부분 배열로 나누고 재귀적으로 정렬해가는 과정 #include using namespace std; void quick_sort(vector &A, int S, int E, int K); int partition(vector &A, int S, int E); void swap(vector &A, int S, int E); void quick_sort(vector &A, int start, int end, int K) { i..

버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 장점 : 구현이 쉽다. 단점 : 상대적으로 다른 정렬 알고리즘보다 시간이 오래 걸린다. 시간 복잡도 - $ O(n^{2}) $ 버블 정렬 코드 스니펫 #include #include using namespace std; int main() { int N = 1000; vector A(N, 0); bool change = false; for (int i = 1; i > N; vector A(N, {0, 0}); // 데이터 값, 각 배열의 인덱스를 저장 for (int i = 0; i > A.at(i).first; // 값 저장 A.at(i).second = i; // 값에 해당하는 인덱스..

시간 제한 : 2초 메모리 제한 : 256MB 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 문제 해설 두 개의 합 혹은 다른 두 수라는 내용이 문제에서 나올 경우 2 포인터 알고리즘이라고 생각하는 것이 중요! 해당 문제에서 시간 복잡도의 경우 최소 $ O(n\log(n)) $ 이어야 하기 때문에 정..

코딩 테스트를 공부할 때 미리 자신만의 스니펫을 구성해두는 것을 추천한다. 간단한 코딩테스트의 경우 쉽게 문제를 풀 수 있지만, 난이도가 높은 문제일수록 쉬운 알고리즘들을 미리 스니펫을 구성해둔 상태로 진행하는 것이 시간을 단축 시킬 수 있다. 이번 포스팅에는 특정 구간에 대한 값의 합을 구하고 싶을 때, 사용되는 구간 합 스니펫을 구현해보았다. 시간 복잡도는 $ O(n) $ 이다. 배열 A 가 존재할 때, 배열 A의 인덱스까지의 누적 합을 배열 S 로 표현한 것은 다음과 같다. S[i] = S[i-1] + A[i] #include #include int main() { vector A; vector S; A.push_back(1); A.push_back(2); A.push_back(3); A.push_..

C++ 기준에서 1억번의 연산 = 약 1초로 볼 수 있다. 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것 코딩 테스트에서는 빅-오 표기법($ O(n) $)을 기준으로 수행 시간을 계산하는 것이 좋다. 예를 들어보자. #include #include #include using namespace std; int main() { int findNumber; int N = 1000000; srand(time(NULL)); findNumber = rand() % 1000000; for (int i = 0; i < N; i++) { if (i == findNumber) { cout