728x90 전체 글423 Digital Image Processing - Fourier transform / Frequency domain 푸리에 변환 푸리에 변환은 Fourier가 제시한 아이디어인 Fourier series라는 모든 주기함수는 각기 다른 주파수의 사인과 코사인 함수의 가중합으로 표현될 수 있다는 아이디어로부터 확장된 개념이다. 아래 그림은 다양한 주파수의 사인함수를 더해서 unit function에 수렴하게 만드는 대표적인 Fourier series의 예시이다. 푸리에 변환은 어떤 함수를 주기함수(주파수를 갖는 함수)의 합으로 표현할 수 있다는 개념을 차용하여 아래와 같이 변환하는 방법이다. 물론 그 역과정을 통해 원시함수를 찾아내는 푸리에 역변환 과정도 가능하다. 이때 F(w)는 Magnitude가 A이고 Phase가 Ø인 주기함수이고 각각은 아래와 같이 실수부 R(w)과 허수부 I(w)로 표현된다. Continuous.. 2024. 4. 18. Optimizer Optimizer 모델이 학습한다는 것은 loss를 최소화하는 최적화과정을 거치는 것이다. 이전에도 optimizer를 직접 구현하며 optimizer의 종류를 알아보고 성능을 비교해봤지만 너무 중요한 내용이고 수업에 나왔기에 다시 한번 수식과 그 의미를 간단히 정리해보고자 한다. 딥러닝 직접 구현하기 - (Optimizer) SGD 확률적 경사 하강법(stochastic gradient descent)의 줄임말인 SGD는 현재 상태에서 학습률과 미분값에 비례한 값을 빼서 갱신하는 방식을 이용한다. 위 식을 기반으로 파이썬 클래스로 구현하면 아래 canvas4sh.tistory.com SGD Stochastic Gradient Descent는 확률적 경사 하강법으로 이름 그대로 모든 데이터에 대해서 그래.. 2024. 4. 17. 알고리즘 설계 실습 - KMP 문제 KMP 알고리즘을 구현하세요. 구현한 KMP 알고리즘으로 문자열 T에서 문자 열 P를 모두 찾고, 찾은 개수와 위치를 출력하세요. 첫째 줄에는 문자열 T가 주어집니다. 문자열 T의 길이 n은 1이상 100만 이하입니다. 둘째 줄에는 문자열 P가 주어집니다. 문자열 P의 길이 m은 1 이상 26 이하입니다. 문자열은 모두 알파벳 대문 자로만 이루어져 있습니다. (줄 바꿈 문자 \n을 포함하면 최대 문자열 길이가 2 추가됩니다.) 첫째 줄에는 문자열 T에서 문자열 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력하세요. 둘째 줄에는 문자열 T에서 문자열 P가 나타나는 위치를 차례대로 공백으로 구분하여 출력하세요. 예를 들면, 문자열 T의 i～i+m-1번째 문자와 P의 1～m번째 문자가 차례로 일.. 2024. 4. 17. Algorithm Design - 라빈-카프 / 패턴 매칭 Rabin-Karp 라빈-카프 알고리즘은 스트링을 숫자값으로 바꾼 다음 해시 값을 계산하여 매칭하는 알고리즘이다. 최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘이다. 첫 번째 M 자리의 나머지를 구한 다음부터는 한 자리씩만 추가하면서 간단한 계산으로 나머지를 구할 수 있으므로 빠른 시간에 스트링 탐색을 수행한다. 해시 값이 다르다면 두 문자열이 다르다는 것이 보장된다. 그러나 해시 값이 같다고 해서 두 문자열이 같다는 것이 보장되지는 않기 때문에 해시값이 같은 경우 문자열을 비교하는 과정을 거친다. 찾고자하는 패턴은 한번 연산을 해두면 해시값이 정해져있지만 한칸씩 넘어가며 텍스트와 비교를 할때 텍스트에서 비교하고자 하는 부분의 해시값을 매번 다시 연산하는 것.. 2024. 4. 17. Digital Image Processing - Warping Image warping 이미지 워핑은 이미지의 형태를 변형하는 과정으로, 특정 알고리즘에 따라 이미지의 픽셀을 새로운 위치로 매핑함으로써 이미지의 모양을 변형시키는 과정이다. 아래와 같이 다양한 워핑 기법이 존재한다. 이미지 필터링이 아래와 같이 화소의 range를 바꾸는 기법이라면 이미지 와핑은 아래와 같이 spatial domain 자체를 바꾸는 기법이다. Forwad Warping Source image(f(x))의 픽셀들을 h(x)함수에 따라 Target(g(x))의 지정된 위치에 옮기는 방식이다. 그러나 새롭게 옮긴 값들이 아래 그림과 같이 픽셀들의 사이에 위치하게 되는 문제가 있다. 이를 해결하기 위해 고안된 방법이 splatting이다. Splatting이란 본래 액체가 팍 튄다는 뜻인데 .. 2024. 4. 15. DIP 실습 - Median / Bilateral / Canny edge detection Median filter 과제: salt_pepper2.png에 대해서 3x3, 5x5의 Median 필터를 적용해보고 결과를 분석할 것 #include #include #include using namespace cv; using namespace std; // 중간값 필터 함수 Mat MedianFilter(const Mat& src, int kernelSize) { Mat dst = src.clone(); // 출력 이미지 초기화 int pad = kernelSize / 2; // 패딩 크기 계산 // 이미지의 각 픽셀에 대해 중간값 필터 적용 for (int i = pad; i < src.rows - pad; i++) { for (int j = pad; j < src.cols - pad; j++).. 2024. 4. 12. Algorithm Design - 스트링 탐색 알고리즘(Naïve/KMP/BM) 스트링 탐색 문서에서 스트링을 탐색할 때 쓰이는 용어를 살펴보면 다음과 같다. - 텍스트(text) : 문서 - 패턴(pattern) : 탐색할 스트링 - 스트링(string): 문자가 연속적으로 나열된 것, 텍스트(text) 스트링, 이진(binary) 스트링 스트링 탐색 알고리즘의 설계는 필연적으로 false start가 발생하는데 이 false start의 횟수와 길이를 줄여가는 것이다. 우선 가장 단순한 알고리즘부터 살펴보자. Naïve Algorithm Brute force 알고리즘이라고도 불리고 직선적 알고리즘이라고도 불리는 특별한 알고리즘이 없는(?) 알고리즘이다. 한 글자 또는 한 비트씩 오른쪽으로 진행하면서 텍스트의 처음부터 끝까지 모두 비교하며 탐색하는 방식을 이용한다. BruteFor.. 2024. 4. 12. Digital Image Processing - Subsampling Sub-Sampling 이미지 Sub-sampling은 downsampling이라고도 불리는데 아래와 같이 원본의 사진의 픽셀의 일부를 제거하여 이미지의 크기를 줄이는 것이다. 이를 확대하면 일상에 자주 볼 수 있는 이미지가 깨지는 현상을 볼 수 있다. 이러한 문제를 해결하기 위해 미리 가우시안 필터링을 하고 downsampling을 하면 아래와 같이 개선된 결과를 얻을 수 있다. 이를 확대해보면 아래와 같이 나타난다. Sub-sampling과정에서 문제가 발생하는 원인이 Nyquist Sampling theorem을 지키지 못하게 되어 고주파 부분의 값을 잃었기 때문이므로 고주파 부분을 Gaussian filter를 이용하여 평탄화를 시켜서 왜곡을 방지하는 방식을 이용하는 것이다. Gaussian an.. 2024. 4. 10. Algorithm Design - B-Tree / B+Tree B-Tree Bayer & McCreight가 1970년에 제안한 구조이다. 차수 m인 B-트리의 특성은 아래와 같다. 1. B-트리는 공백이거나 높이가 1 이상인 m-원 탐색 트리이다. 2. 루트와 리프를 제외한 내부 노드는 아래와 같이 최소 e[m/2u] , 최대 m개의 서브트리를 갖고 있고 적어도 [m/2] - 1개의 키 값(노드의 반 이상 채워짐)을 갖고 있다. 3. 루트 : 리프가 아니면 적어도 두 개의 서브트리를 가진다. 4. 모든 리프는 같은 레벨이다. 또한 B-트리의 장점은 삽입,삭제 뒤에도 균형 상태 유지가 되고 저장 장치의 효율성이 좋다. 각 노드의 반 이상 키 값 저장을 저장하고 최악의 경우에도 O(log_n (N+1))의 시간복잡도를 보장한다. 아래는 이러한 특징이 반영된 3차 B-.. 2024. 4. 5. Digital Image Processing - Smoothing / Edging Noise Signal에서 변화를 감지하려면 미분을 해서 찾아내야 하는데 미분은 noise에 굉장히 취약하다. 미분을 하면 기울기가 나오는데 아무리 작은 noise라도 위아래로 피크가 생기면 그 기울기값은 매우 커지기 때문이다. 따라서 미분을 하기 전에 gaussian filter를 통과시켜서 noise를 제거한다. gaussian filtering으로 denoise를 해주고 미분을 하니 원하는대로 signal이 변하는 부분을 쉽게 캐치할 수 있는 것을 볼 수 있다. 이때 convolution 미분 연산을 아래와 같이 바꿀 수 있는 성질이 있는데 이를 이용하면 DoG(Derivative of Gaussian)을 만들어서 사용할 수 있다. x방향이느냐 y방향이느냐에 따라 DoG는 아래와 같이 나타난다. S.. 2024. 4. 5. Algorithm Design - Tree Tree 우선 트리구조를 가볍게 살펴보자. 이미 자료구조론 수업에서 다뤘던 내용이기 때문에 간단하게만 살펴보려한다. Tree terminology 1. 루트(Root): 부모가 없는 노드 (A) 2. 자식(Child): 노드 u가 노드 v의 부모라면, v는 u의 자식입니다. 3. Siblings: 같은 부모를 가진 노드들 4. Internal node: 적어도 하나의 자식을 가진 노드 (A, B, C, F) 5. Leaf node: 자식이 없는 노드 (E, I, J, K, G, H, D) 6. 노드의 깊이(Depth of a node): ancestor의 수 7. Height of a tree: 어떤 노드의 최대 깊이 8. 차수(Degree): 노드의 자식 수 Traversal 종류 Preorder (.. 2024. 4. 4. [논문 리뷰] YOLO-World: Real-Time Open-Vocabulary Object Detection 리뷰 Intro 우선 YOLO는 You Only Look Once의 약자이다. YOLO이전의 R-CNN은 이미지 안에서 bounding box를 생성하기 위해 sliding window를 사용하여 region proposal 방식으로 사진의 부분부분을 확인한다. bounding box에 classifier를 적용하여 분류한 뒤 bounding box를 조정하고, 중복된 검출을 제거하고, 객체에 따라 box의 점수를 재산정하기 위해 후처리를 한다. 반면 YOLO는 이미지 전체를 한눈에 보고 regression으로 multi task를 한번에 처리한다. 이렇게 간단히만 알아봐도 처리속도가 훨씬 빠르고 실시간 처리에 적합할 것이 쉽게 파악된다. Background Object Detection에는 두 가지 방식이 .. 2024. 4. 4. 이전 1 ··· 5 6 7 8 9 10 11 ··· 36 다음 728x90
