728x90 Quality control (Univ. Study)197 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 22 다음 728x90
