유전자로의 코드화

영상 복원에서 찾고자 하는 해는 원래 영상이 아닌 가장 근사하다고 판 단되는 추정 영상이다. 본 연구에서는 하나의 영상을 하나의 개체로 보았 다. 유전 알고리즘은 보통 개체의 표현을 1차원 배열을 사용한다. 그러 나, 영상은 2차원의 화소로 표현된다. 본 연구에서는 각 화소를 유전자로 간주하고 하나의 영상을 2차원 염색체로 간주하였다. 본 연구에서는 원래 영상을 그레이 영상에 한정하고, 염색체는 2차원의 비트 배열로 하였다.

Fig. 7은 Fig. 6의 영상을 유전자로 표본화한 것을 보여준다.

Fig. 6 Original Image

Fig. 7 Image Encoding

Fig. 8 3×3 adjacency pixel

3. 유전자 조작

각 개체의 적합도가 구한 다음에는 개체 집단에 대한 유전자 조작을 가 하였다. 본 연구에서는 선택, 교차, 돌연변이등을 순차적으로 수행하였 다. 선택 방법은 적합도가 낮은 개체를 도태시키고, 적합도가 높은 개체 를 복제하여 개체의 수를 유지 하였다.

Fig. 10 Crossover

Fig. 10 Mutation

교차는 일반적인 유전 알고리즘과 달리 2차원 배열인 염색체 개체를 가 로 또는 세로로 교차하는 방법을 사용하였다. 돌연변이는 난수에 의해서 선택된 화소의 주위 화소의 정보를 이용하였다. 돌연변이 비율이 너무 높 으면 부분 해에 빠지거나 우수한 유전자를 가진 해 집단이 파괴되는 경우

가 생긴다. 돌연변이에 의해 반전될 확률을 그 주위 화소의 평균값에 의

Procedure: Image Restoration Unsing Genetic Algorithms Begin

t ← 0;

population P(t);

fitness P(t);

While (not termination condition) do selection P(t+1);

본 연구에서 제시하는 기법은 열화된 영상을 가지고 추정 영상 그룹을 생성하고 그 추정 화상들에 대하여 유전형질의 적합도를 구하여 그 적합 도를 평가하고 높은 적합도를 갖는 우수한 형질의 개체만을 선택하고 교 차하여 새로운 집단을 생성하고 부분 해에 빠지는 경우를 위해 주위의 화 소를 이용한 돌연변이 연산을 수행하고 원 영상에 가까운 추정 영상을 얻 을 때까지 반복 수행하는 기법이다.

제시하는 알고리즘은 대수적인 기법을 사용하지 않고도 열화된 영상에 서 원 영상에 가까운 영상을 구하는 방법을 제시하고 있다.

유전 알고리즘에서는 먼저 문제의 해 후보로부터 형성된 초기 집단을 생성한다. 이 초기 집단에 대하여 평가함수를 환경으로 한 자연도태의 원 리를 적용시키고, 유전자 조작을 반복하여 집단에 추가해 가는 것에 의해 집단이 진화하여 최적 해를 얻게된다.

IV. 설계 및 구현

여 계산하였으며, 이 적합도에 따라 선택 연산에서 도태시킬 개체를 선 택하게 된다.

3) 선택 연산 함수

선택 연산은 각 개체의 적합도를 기반으로 이루어진다. 적합도가 다 른 개체에 비하여 떨어지는 개체는 도태시키고, 도태된 개체의 수 만큼 을 적합도가 우수한 개체로부터 생성하여 집단의 개체수를 유지한다.

4) 교차 연산 함수

교차 연산은 가로 교차와 세로 교차를 같이 사용하였다. 이 교차 연 산을 통하여 생성되는 자식 개체는 양쪽 부모 개체의 유전자를 모두 가 지게된다.

5) 돌연변이 연산 함수

돌연변이 연산은 임의의 개체를 선택하고 임의의 유전자를 변경하는 연 산이다. 랜덤 변수와 주위 화소의 정보를 이용하여 돌연변이 연산을 구현 하였다.

Fig. 12 Image restoration algorithms

V. 결과 및 고찰

지금까지 설명한 기법을 이용하여 영상 복원을 수행하였다. 실험에 사 용된 영상은 256×256 크기의 영상을 사용하였으며, 노이즈로 10%와 20%

의 가우시안 노이즈를 흑백 영상과 그레이 영상에 첨가하여 열화 시키고 이를 복원하였다. 초기 모집단의 수는 4개 이상으로 하였으며 3세대 이상 진화한 후의 영상 중에서 복원된 영상을 구하였다.

(a) (b)

(c)

Fig. 13 (a) Original image; (b) Image including 10% gaussian noise;

(d) Restoration image

Fig. 13은 흑백의 원래 영상에 10%의 가우시안 노이즈를 첨가한 열화 영상을 가지고 4개의 모집단과 3세대의 진화 연산을 거쳐 복원한 것이다.

(a) (b)

(c)

Fig. 14 (a) Original image; (b) Image including 20% gaussian noise;

(d) Restoration image

Fig. 14는 흑백의 원래 영상에 20%의 가우시안 노이즈를 첨가한 열화 영상을 가지고 4개의 모집단과 3세대의 진화 연산을 거쳐 복원한 것이다.

(a) (b)

(c)

Fig. 15 (a) Original image; (b) Image including 10% gaussian noise;

(d) Restoration image

Fig. 15는 그레이 영상에 10%의 가우시안 노이즈를 첨가한 열화 영상을 가지고 6개의 모집단과 5세대의 진화 연산을 거쳐 복원한 것이다.

(a) (b)

(c)

Fig. 16 (a) Original image; (b) Image including 20% gaussian noise;

(d) Restoration image

Fig. 16은 그레이 영상에 20%의 가우시안 노이즈를 첨가한 열화 영상을 가지고 6개의 모집단과 5세대의 진화 연산을 거쳐 복원한 것이다.

Fig. 17 Number of maximum fitness

Fig. 17은 각 세대에 따라 최고의 적합도 평가치를 나타내는 개체의 변 화 추이를 나타낸다. 또한 각 세대에 따라 나타나는 최고의 적합도 평가 치의 변화 추이는 Fig.18과 같다.

Fig. 18 Fitness transition

Fig. 17과 Fig. 18를 보면 세대가 지날수록 적합도 평가치는 한곳으로 수렴하고 최고의 평가치를 가지는 개체의 수는 증가함을 알 수 있다. 이 러한 현상은 열화된 영상에서 원래의 영상으로의 수렴을 나타낸다.

이상의 결과에서와 같이 유전 알고리즘이 영상 복원에 효과적으로 응용 될 수 있다는 것을 보여주고 있다. 또한 영상의 색상이 많아지면 모집단 의 크기와 진화 연산의 세대수가 증가하여야 원래의 영상과 근접한 복원 영상을 얻을 수 있음을 알 수 있다.

VI. 결론

열화된 영상은 필터를 사용하거나 대수학적인 방법을 사용하여 원래의 영상에 근접한 추정 영상을 얻는 것이 현재 사용되고 있는 기법이다. 그 러나 유전 알고리즘을 영상 복원 적용하면 필터나 대수학적 방법을 사용 하지 않고도 원 영상에 가까운 영상을 쉽게 얻을 수 있다.

유전 알고리즘의 선택, 교배, 돌연변이 등의 유전자 연산에 의하여 열 화된 영상으로부터 생성된 추정화상의 집단은 세대가 지날수록 원래의 영 상에 근접한 영상의 집단으로 수렴을 하게된다.

유전 알고리즘에 의한 영상 복원에서 앞으로 연구되어야 할 방향으로는 자연 영상으로의 확장과 실시간 영상 복원을 들 수 있다. 자연 영상을 복 원하기 위해서는 파라미터의 값을 실수 범위에서 다루어야 하므로 계산량 이 증가하게 된다. 또한 실시간 영상 복원을 위해서는 고속의 영상 복원 시스템이 필요하게 된다. 이러한 처리를 위해서는 시스템의 병렬화를 포 함한 고속화 기법의 개발이 필요하다.

참고문헌

Resonfeld A. & Kak A.C.,Digital Picture processing, 1978

W.K.Pratt, 1978, Digital Image Processing, New York,Wiley

I.daubechies,1988,"Orthonormal bases of compactly supported wavelets" , commun, pure Appl, Math, Vol.XLT, no.7,pp.909∼996

M.Vetterli & C.Herly, 1992, "Wavelets and filter banks: Theory and design", IEEE Trans.signal Processing, Vol.40, no.9, pp.2207∼2232

M.Antonini, M.Barlaurd, P.Mathieu and I.Daubechies, 1992, "Image coding using wavelet transform", IEEE Trans. Image Processing, Vol.1 ,no.2, pp.205∼220

D.t.kuan, A.A. Sawchuck, T.C.Strand and P.chavel,1985,"Adaptive noise smoothing filter images with signal dependent noise", IEEE Trans. Patt.Anal.Machine Intell, Vol.PAMI-7, no.2, pp.165∼177

Rafael C.Gonzalez and Richard E.Woods,1998, Digital Image Processing

Rechenberg I., 1973, Evolutionsstrategie:Optimierung technischer System nach Prinzipiender biologischen Evolution, Fromman-Holzboog verlag, Stuttgart

Schwefel H.P., 1981, Numerical Optimization for Computer Models, John Wiley, Chichester, UK

Through Simulated Evolutionm John Wiley, chichester, UK

Goldberg D.E., 1989, Genetic Algorithms in Search,Optimization and Machine Learning, Addison-Wesley ,Reading

Holland J.H.,1975, Adaptation in Natual and Artificial Systems, University of Micigan Press, Ann Arbor

Melanie Mitchell, 1998, Introduction Genetic Algorithms

Takatsu K., Watanabe S., Sawai H. and Yoneyama M., No 1992, A Propsal of Image Restoration Using Genetic Algorithms, Proceedings of Int. joint Conf. On Neural Networks, Beijing,IEEE & INNS, Vol.1, pp 642∼647

Geman S. and Geman D., 1984.11, Stochastic Relaxations, Gibbs distributions and the Bayesian restoration of images, IEEE Trans., PAMI-6

Koch C., Marroquin J. and Yuille A., 1986, Analog 'Neuronal' Networks in Early Vision, Proc.Natl.Acad.Sci.USA,83

Stark H.(Ed.):Rhodes W.T.,1982, Space-Variant Optical Systems and Processing, In Applications of Optical fourier Transforms, Academic Press

Ackely D.H., Hinton G.E. and Sejnowski T.J., 1985, A Learning Algorithm for Boltzmann Machines, Cognitive Science Vol.9, no.1, pp.147∼169

Kirkpatrick S.,Gelatt Jr., C.D. andVecchi M.P., 1983, Optimization

by Simulated Annealing, Science vol.220, pp.671∼680

Davis T.E. and Pricipe J.C., 1991, A Simulated Annealing like Convergence Theory for the Simple Genetic Algorithm, in proc.4th Int.Conf. on genetic Algorithms

Syswerda G. , 1989, Uniform Crowwover in Genetinc Algorithms, Proc.

of ICGA-89

八木伸行․井上誠喜․林 正樹,奧正誠人,合志淸一, 1998, C언어에 의한 디 지털 영상처리

임영도, 이상부, 1998, 퍼지․신경망․유전진화

이문호, 염재훈, 1998, C언어를 이용한 영상신호처리

손동일, 1993, Windows 이미지 그래픽 프로그래밍

감사의 글