[알고리즘][유전자알고리즘][뼈나이측정알고리즘][동기알고리즘][에지디텍션알고리즘]알고리즘의 자료구조, 알고리즘의 성능, 유전자알고리즘, 뼈나이측정알고리즘, 동기알고리즘, 에지디텍션알고리즘에 관한 분석

소개글

[알고리즘][유전자알고리즘][뼈나이측정알고리즘][동기알고리즘][에지디텍션알고리즘]알고리즘의 자료구조, 알고리즘의 성능, 유전자알고리즘, 뼈나이측정알고리즘, 동기알고리즘, 에지디텍션알고리즘에 관한 분석에 대한 보고서 자료입니다.

목차

Ⅰ. 알고리즘의 자료구조
1. 자료 객체(Data object)
2. 자료구조(Data structure)
3. 자료 객체란
4. Data Abstraction
5. ADT에 대하여

Ⅱ. 알고리즘의 성능
1. 공간 복잡도(Space complexity)
1) 고정 공간 요구
2) 가변 공간 요구
2. 시간 복잡도(Time complexity)
3. 설명

Ⅲ. 유전자 알고리즘
1. 유전자 알고리즘의 특징
2. 유전자 알고리즘의 수행절차
1) 개체집단 초기화
2) 개체선택
3) 교배연산(crossover)
4) 돌연변이(mutation)
5) 새로운 세대로 진화
3. 제약조건처리방법
1) 벌점함수(Penalty Function)
2) 복구알고리즘(Repair Algorithm)
3) GENOCOP 시스템(Genetic Algorithm for Numerical Optimization for Constrained Problems)

Ⅳ. 뼈나이측정 알고리즘
1. 설계 알고리즘
2. 최적 분할 탐색 알고리즘
1) 전체 탐색(exhaustive search)
2) 순차 탐색 알고리즘
3) 유전 알고리즘(genetic algorithm)
3. 인식 알고리즘
4. 계산 시간

Ⅴ. 동기 알고리즘
1. 송수신 클럭 동기
2. 망의 실제 지연 측정
3. 송수신 타이머 초기화
4. 재동기 알고리즘

Ⅵ. 에지디텍션 알고리즘

참고문헌

본문내용

l을 완성시키고 이것을 L이라 한다.
(3) edge pixel들은 L에서 zero-crossing인 pixel들이다.
Gaussian의 convolution된 결과는 edge image를 형성하기 위해 결합 된다. 두 개의 dimention의 convolution은 다음과 같이 표현될수 있다.
G(i,j)= I(n,m)G(i-n,j-m)
image와 convolution되는 함수 G는 다음과 같이 주어지는 2-D Gaussian이다.
(x,y)=exp( )
digital image상에서 convolution을 실행 하려면 Gaussian은 작은 2-D image를 만들기 위해 sampling되어야 한다. convolution후에 Laplacian operator가 적용될수 있다.
이것은
= +
이고 Gaussian의 Laplacian을 분석적으로 계산할수 있고 같은 결과를 내기위해 image상에 적용될수 있는 convolution mask를 만드는 함수를 sampling할 수 있다.
이 알고리즘은 먼저 Laplacian of Gaussian 의 2-D sampling을 만들고 입력 image와 convolution시킨다. 그리고 나서 zero-crossing pixel들은 구별한다. zero-crossing이 일어났다는 것은 어떤 방향의 반대쪽 두 이웃 pixel의 값이 다른 부호를 가졌다는 것을 의미하며 이 pixel이 edge이다.
Canny 알고리즘은 error rate와 localization, response 에 주안점을 두고 있다. 이 알고리즘은 step edge를 White Gaussial noise로, edge detector는 noise를 제거하고 edge를 위치시키는 convolution filter로 가정한다.
1-D에서 edge G에 대한 filter f의 응답은 다음과 같이 주어지는 convolution intergral에 의해 나타내어진다.
H=
filter는 [-W,W]범위 외에서는 0이라고 가정된다.
수학적으로 세가지 주안점의 기준은 다음과 같이 표현된다.
SNR =
Localization =
= π
SNR값은 error rate이고 가능한한 커야하며 Localization값은 실제 edge와 located edge 와의 거리의 역수를 나타내는데 역시 가능한 커야한다. 값은 제한이다. 그것은 의 zero crossing과 들 사이의 평균 거리를 나타내며 edge detector f가 작은 지역에서 같은 edge에 많은 응답을 않는다는 것을 나타낸다.
multiple-response constraint에 대해서 가장 큰 SNR × Localization을 가지는 filter f를 찾을려고 시도했다. 그 결과는 분석하기에 너무 복잡하지만 근사화를 통해 Gaussian 함수의 1차 도함수를 만들어 냈다. Gaussian 함수를 다시 써보자면
G(x) =
x에 대한 도함수는
(x) =
Gaussian 함수는 다음과 같다.
G(x,y) =
G는 x와 y 둘 다의 도함수를 가진다.
Canny의 edge detection에서 최적화된 필터의 근사화는 이며 와 입력 image 와 convolution시킴으로써 noise가 있는 경우에도 강조된 edge를 가지는 image E를 얻을 수 있다.
convolution 은 간단하게 실행할 수 있지만 2-D convolution에서는 계산하기 힘들다.
Canny 알고리즘은
image I를 읽는다. I와 convolution시키기 위해 1D Gaussian mask G를 만든다.Gaussian의 표준편차 s는 edge detecter의 parameter이다. x와 y방향에서 Gaussian의 1차 도함수에 대한 1D mask를 만단다. 이것들을 와 라 부르자. 같은 s 값이 위의 step2에서 사용된다. x 성분 image 와 y 성분 image 를 얻기 위해 image I와 G를 convolution시킨다. 를 얻기 위해 와를 convolution시킨다. 이것은 I의 x 성분과 Gaussian의 도함수와의 convolution이다. 그리고 를 얻기 위해 와 를 convolution시킨다.
결과를 보기를 원한다면 x와 y성분들이 결합되어야 한다. 결과값의 크기는 각각의 pixel(x,y)에 대해서 다음과 같이 계산된다.
M(x,y) =
Shen-Castan(ISEF)알고리즘은 canny edge detector의 일반적인 형태 edge pixel의 탐색에 따르는 smoothing kernal과의 convolution에 대해서 동의했다. 그러나 최고의 성능을 내기 위해 다른 함수를 만들었다. 그것은 다음과 같이 주어지는 을 최소로 만드는 function이 edge detector에서 최고의 smoothing filter 라는 것이다.
=
성능이 좋은 filter function은 infinite symmetric exponential filter(ISEF)로서 다음과 같은 funtion을 갖는다.
f(x) = in one dimension
Shen과 Castan은 이 필터가 canny의 필터보다 더 나은 signal-to-noise ratio를 가지고 있으며 더 나은 localization을 제공한다고 주장했다. 이 알고리즘에서 우선 개선 된 것이 false zero crossing suppression의 사용이다. edge 픽셀에서는 filtered image의 2차 도함수에서 zero crossing이 발생한다. 이것은 그 점에서의 gradient가 가장 큰 값이거나 가장 작은 값이라는 것을 의미한다. 원래 image가 noise가 아주 많이 끼었을 때 일반적인 thresholding방법이 충분하지 않을 수도 있다. Shen과 Castan은 adaptive gradient mathod를 제안했다.
참고문헌
○ 공성곤 외, 유전자 알고리즘, 그린, 1996
○ 박재우, 측정 활동을 통한 분수 계산 알고리즘의 이해에 관한 연구, 한국교원대학교 대학원 석사학위 논문, 2004
○ 이재규, C로 배우는 알고리즘, 2003
○ 알고리즘, Richard E Neapolitan 외 지음, 2004

키워드

알고리즘,   유전자알고리즘,   뼈나이측정알고리즘,   동기알고리즘,   에지디텍션알고리즘