분할 및 정복의 개념 적군의 대병력을 격파하기 쉬운 소병력으로 분할(divide)하고, 분할된 소병력들을 쉽게 정복(conquer)하는 원리 적용 예 이진 탐색(binary search) Max_Min 알고리즘 Merge Sort(합병 정렬) Quick Sort(퀵 정렬)
whan0623
메인 함수
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main(int argc, char** argv) { int A[8] = {36, 2, 3, 15, 32, 4, 10, 30}; int n = sizeof(A) / sizeof(A[0]); quick_sort(A, 0, n-1); for(int i=0; i<n; i++){ printf("%d ", A[i]); } printf("\n"); return 0; } |
Swap 함수
|
1 2 3 4 5 6 |
void swap(int A[], int a, int b) { int t = A[a]; A[a] = A[b]; A[b] = t; } |
Quick 정렬
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void quick_sort(int A[], int s, int e) { if(s<e){ int p = s, l = s+1, r = e; while(l<=r){ while(l<= e && A[l]<=A[p]) l++; while(r>=s+1 && A[r]>=A[p]) r--; if(l<r) swap(A, l, r); } swap(A, p, r); quick_sort(A, s, r-1); quick_sort(A, r+1, e); } } |
whan0623
메인 함수
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int main(int argc, char** argv) { int A[8] = {36, 2, 3, 15, 32, 4, 10, 30}; int n = sizeof(A) / sizeof(A[0]); MergeSort(A, n, 0, 7); for(int i=0; i<n; i++){ printf("%d ", A[i]); } printf("\n"); return 0; } |
합병 정렬
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
void Merge(int A[], int n, int first, int mid, int last){ int tmp[n]; int first1 = first; int last1 = mid; int first2 = mid + 1; int last2 = last; int i; while( first1 <= last1 && first2 <= last2 ){ if(A[first1] < A[first2]){ tmp[i++] = A[first1++]; } else{ tmp[i++] = A[first2++]; } } while(first1 <= last1){ tmp[i++] = A[first1++]; } while(first2 <= last2){ tmp[i++] = A[first2++]; } for(int i=first; i<=last; i++){ A[i] = tmp[i]; } } |
|
1 2 3 4 5 6 7 8 |
void MergeSort(int A[], int n, int first, int last){ if(first < last){ int mid = (first + last) / 2; MergeSort(A, n, first, mid); MergeSort(A, n, mid+1, last); Merge(A, n, first, mid, last); } } |
whan0623
메인 함수 : 1,2,3,4,7,8,11,15에서 11을 찾는 과정을 3가지 방법으로 구함 순차 탐색 이진 탐색(반복문 사용) 이진 탐색(재귀호출 사용)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int main(int argc, char** argv) { int A[8] = {1,2,3,5,7,9,11,15}; int n = sizeof(A) / sizeof(A[0]); sequential_search(A, n, 11); binary_search_while(A, n, 11); int idx = binary_search_recursive(A, 11, 0, 7); printf("Search Index : %d\n", idx); return 0; } |
순차 탐색
|
1 2 3 4 5 6 7 8 9 10 11 |
void sequential_search(int A[], int n, int k){ //sequential serach int idx=-1; for(int i=0; i<n; i++){ if(k == A[i]){ idx = i; } } printf("Search Index : %d\n", idx); } |
이진 탐색(반복문 사용)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void binary_search_while(int A[], int n, int k){ //binary search int s = 0, e = n-1, m; //s : start, e : end, m : mid int idx=-1; while(e-s >= 0){ m=(s + e) / 2; if(k == A[m]) { idx = m; break; } if(k > A[m]) s = m + 1; else e = m - 1; } printf("Search Index : %d\n", idx); } |
이진 탐색(재귀 호출 Recursive 사용)
|
1 2 3 4 5 6 7 8 9 |
int binary_search_recursive(int A[], int k, int s, int e){ if(s > e) return -1; int m = (s + e)/2; if(k == A[m]) return m; if(k > A[m]) return binary_search_recursive(A, k, m+1, e); else return binary_search_recursive(A, k, s, m-1); } |
whan0623
최대값과 최소값을 구하는 알고리즘 1. 메인 함수
|
1 2 3 4 5 6 7 8 9 10 |
int main(int argc, char** argv) { int A[9] = {9, 3, 2, 0, 5, 18, 8, 11, 16}; int n = sizeof(A) / sizeof(A[0]); int tmax=-999, tmin=999; seq_max_min(A, n); max_min(A, 0, 8, &tmax, &tmin); printf("Divide Conquor Method Max : %d, Min : %d\n", tmax, tmin); return 0; } |
2. 순차 알고리즘
|
1 2 3 4 5 6 7 8 9 |
void seq_max_min(int A[], int n){ int tmax=-999, tmin=999; for(int i=0; i<n; i++){ if(tmax < A[i]) tmax = A[i]; if(tmin > A[i]) tmin = A[i]; } printf("Sequence Method Max : %d, Min : %d\n", tmax, tmin); } |
3. 분할 정복 방법 사용
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void max_min(int A, int i, int j, int *tmax, int *tmin){ if(i == j){ *tmax = A[i]; *tmin = A[i]; } else if(i == j-1){ if(A[i] < A[j]){ *tmax = A[j]; *tmin = A[i]; } else{ *tmax = A[i]; *tmin = A[j]; } } else{ int gmax, gmin, hmax, hmin, middle; middle = (i+j)/2; max_min(A, i, middle, &gmax, &gmin); max_min(A, middle+1, j, &hmax, &hmin); *tmax = (gmax > hmax)? gmax : hmax; *tmin = (gmin < hmin)? gmin : hmin; } } |
whan0623
형태학적 처리 부분 소스 코드 0. 메뉴를 다음과 같이 추가한다. 1. 형태_침식연산 메뉴를 더블클릭한 후 private void 형태침식연산ToolStripMenuItem_Click() 함수 위쪽에 침식(f_Errosion) 함수와 팽창(f_Dilation)를 추가한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
private byte[] f_Errosion(int width, int height, byte[] data) { int x, y; byte min; byte[] newdata = new byte[data.Length]; for (y = 1; y < height - 1; y++) { for (x = 1; x < width - 1; x++) { min = 255; if (data[(y - 1) * height + x - 1] < min) min = data[(y - 1) * height + x - 1]; if (data[(y - 1) * height + x] < min) min = data[(y - 1) * height + x]; if (data[(y - 1) * height + x + 1] < min) min = data[(y - 1) * height + x + 1]; if (data[(y) * height + x - 1] < min) min = data[y * height + x - 1]; if (data[(y) * height + x] < min) min = data[y * height + x]; if (data[(y) * height + x + 1] < min) min = data[y * height + x + 1]; if (data[(y + 1) * height + x - 1] < min) min = data[(y + 1) * height + x - 1]; if (data[(y + 1) * height + x] < min) min = data[(y + 1) * height + x]; if (data[(y + 1) * height + x + 1] < min) min = data[(y + 1) * height + x + 1]; newdata[y * width + x] = min; // 최소값을 결과 영상에 저장 } } return newdata; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
private byte[] f_Dilation(int width, int height, byte[] data) { int x, y; byte max; byte[] newdata = new byte[data.Length]; for (y = 1; y < height - 1; y++) { for (x = 1; x < width - 1; x++) { max = 0; if (data[(y - 1) * height + x - 1] > max) max = data[(y - 1) * height + x - 1]; if (data[(y - 1) * height + x] > max) max = data[(y - 1) * height + x]; if (data[(y - 1) * height + x + 1] > max) max = data[(y - 1) * height + x + 1]; if (data[(y) * height + x - 1] > max) max = data[y * height + x - 1]; if (data[(y) * height + x] > max) max = data[y * height + x]; if (data[(y) * height + x + 1] > max) max = data[y * height + x + 1]; if (data[(y + 1) * height + x - 1] > max) max = data[(y + 1) * height + x - 1]; if (data[(y + 1) * height + x] > max) max = data[(y + 1) * height + x]; if (data[(y + 1) * height + x + 1] > max) max = data[(y + 1) * height + x + 1]; newdata[y * width + x] = max; // 최대값을 결과 영상에 저장 } } return newdata; } |
2. [형태_침식연산(배경=0)] 메뉴를 더블클릭한 후 다음코드를 완성한다.
|
1 2 3 |
///////// Start Image Processing //////////////// data = f_Errosion(bmp.Width, bmp.Height, data); ///////// End Image Processing //////////////// |
3. [형태_팽창연산(배경=0)] 메뉴를 더블클릭한 후 다음코드를 완성한다.
|
1 2 3 |
///////// Start Image Processing //////////////// data = f_Dilation(bmp.Width, bmp.Height, data); ///////// End Image Processing //////////////// |
4. [형태_열림연산(배경=0)] 메뉴를 더블클릭한 후 다음코드를 완성한다.
|
1 2 3 4 5 6 7 8 |
///////// Start Image Processing //////////////// data = f_Errosion(bmp.Width, bmp.Height, data); data = f_Errosion(bmp.Width, bmp.Height, data); data = f_Errosion(bmp.Width, bmp.Height, data); data = f_Dilation(bmp.Width, bmp.Height, data); data = f_Dilation(bmp.Width, bmp.Height, data); data = f_Dilation(bmp.Width, bmp.Height, data); ///////// End Image Processing //////////////// |
5. [형태_닫힘연산(배경=0)]… Continue Reading 형태학적 처리 C# 소스 코드
whan0623
영역 기반 처리 부분 소스 코드 용어 : 회선(convolution) : 디지털 영상에서 각각의 픽셀을 본래 픽셀과 그 주변 픽셀의 조합으로 대체하는 동작, 0. 메뉴를 다음과 같이 추가한다. 1. 영역_선명화 메뉴를 더블클릭한 후 private void 영역선명화ToolStripMenuItem_Click() 함수 위쪽에 회선(convolution) 함수를 추가한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
private byte[] f_Convolve(int width, int height, int bias, byte[] data, double[] mask) { int depth = data.Length / width / height; byte[] newdata = new byte[data.Length]; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { double sum = 0; for (int yy = 0; yy < 3; yy++) { for (int xx = 0; xx < 3; xx++) { if (y + yy - 1 < 0 || y + yy - 1 >= height || x + xx - 1 < 0 || x + xx - 1 >= width) { sum += 0; } else { sum += data[(y + yy - 1) * width + (x + xx - 1)] * mask[yy * 3 + xx]; } } } sum += bias; if (sum > 255) sum = 255; if (sum < 0) sum = 0; newdata[y * width + x] = (byte)sum; } } return newdata; } |
2. [영역_선명화] 메뉴를 더블클릭한 후 다음코드를 완성한다.
|
1 2 3 4 5 6 7 8 9 |
///////// Start Image Processing //////////////// double[] mask = new double[9]{ 0, -1, 0, -1, 5, -1, 0, -1, 0 }; data = f_Convolve(bmp.Width, bmp.Height, 0, data, mask); ///////// End Image Processing //////////////// |
3. [영역_흐리게하기] 메뉴를… Continue Reading 영역 기반 영상 처리 C# 소스 코드
whan0623
Visual Studio 2010에서 C#으로 영상처리 프로그램 시작 글의 마지막 부분에 추가했던 [픽셀_산술덧셈]과 [픽셀_산술뺄셈] 코드부터 다시 시작한다. 픽셀 기반 처리 부분 소스 코드 1. [픽셀_산술덧셈]을 클릭했을 때 추가되었던 함수를 다음과 같이 완성한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
private void 픽셀산술덧셈ToolStripMenuItem_Click(object sender, EventArgs e) { Bitmap bmp = f_OpenBitmapFile(); //그림파일 불러오기 if (bmp == null) return; byte[] data = f_getDataFromImage(bmp); //Bitmap 형식에서 byte 데이터만 가져오기 ///////// Start Image Processing //////////////// //영상처리 시작(산술덧셈) int addValue = 50; for (int i = 0; i < data.Length; i++) { if (data[i] + addValue > 255) { data[i] = 255; } else { data[i] = (byte)(data[i] + addValue); } } ///////// End Image Processing //////////////// //영상처리 끝(산술덧셈) Bitmap bmp2 = f_makeImageFromData(256, 256, data); //byte형 데이터를 Bitmap 형식으로 변환하기 f_drawImage(bmp, bmp2); //Form에 Bitmap 그림 출력하기 } |
2. 계속해서 [픽셀_산술뺄셈] 메뉴를 더블클릭한 후 다음코드를 완성한다. 산술 덧셈과 산술 뺄셈 코드는 대부분이 똑같고 약간의… Continue Reading 픽셀 기반 영상 처리 C# 소스 코드
whan0623
이 장에서 배우는 기능 변수의 개념 알기 : 변수란 프로젝트가 실행되는 동안 값을 저장하는 공간 변수 만들기 : 생명, 점수, 물고기속도, 번개속도 메시지 보내고 받기 : 스크립트간의 동기화를 위한 수단 실전4-1과 실전4-2를 먼저 공부해보자. 블록 익히기 실전 4-1(p51) : 스크립트의 실행 결과 예상해보자 교재 내용(p52) : Alex가… Continue Reading 하늘에서 떨어지는 물고기(변수)
whan0623
블록 익히기 반복구조 조건구조 배경(Underwater2), 상어(Shark), 크랩(Crab), 물고기(Fish1)를 이용하여 프로젝트 만들기 기능 상어가 불규칙적으로 움직이는 기능 물고기가 방향키에 의해 움직이는 기능 물고기가 상어에 닿으면 사라지는 기능 스크립트 Shark : 1초마다 다음 모양으로 바꾸기, 5만큼 이동, 벽에 닿으면 튕기기, -60 ~ 60도 만큼 돌고, 2~5초 사이 기다리기 Crab… Continue Reading 상어 피하는 물고기(선택 블록)
whan0623