가우스와 등차수열

수학 이야기 2013. 1. 28. 15:35

학생시절 수학 문제집 간지에서 읽었던 독일 수학자 가우스에 대한 일화가 아직도 기억에 남는다.


벽동공장에서 일하는 아버지를 둔 가우스는 바닥에 쪼그리고 앉아서 조약돌을 가지고 노는게 일상이었다고 한다. 가우스가 초등학교 시절에 하루는 선생님이 학생들에게 벌로 1에서 100까지 더하라는 문제를 내 놓고는 쉬고 있었다고 한다. 내심 그거 다 더할라면 한참 걸리겠지 하고 있었는데 문제를 내자마자 잠시후 한 학생이 벌떡 일어나서는 바로 정답을 말했다고 한다. '어떻게 벌써 다 풀었니' 하고 물으니 가우스가 대답하기를 돌을 1개, 2개, 3개, ..., 100개 이렇게 순서대로 한줄로 놓고 이것들을 다 더하면 되는데, 이번에는 먼저 놓아진 돌들의 밑에다가 반대로 100개, 99개, ..., 1개 순으로 돌들을 놓고 위아래 순서대로 더하면 항상 101개가 되기 때문에 윗줄과 아랫줄 돌들을 다 합치면 총 101 x 100 = 10100개가 되며 이것의 절반인 10100/2 = 5050개가 답이라고 했다 한다. 




위 일화는 문제집의 단원 중 등차수열 부분의 뒷 부분에 있었던 것으로 기억되는데 당시 이걸 읽으면서 참으로 대단하구나 하고 감탄을 했던 것 같다. 위 문제를 일반화하면 '1에서 n까지 더하면 n(n+1)/2 이다'라는 잘 알려진 수학 공식이 된다. 이걸 그냥 공식으로 암기해서 문제를 풀 수도 있고 아니면 가우스처럼 풀 수도 있을 것이다. 하지만, 공식으로만 암기해서 문제를 풀었던 사람은 1 + 3 + 5 + 7 + ... + 101과 같이 조금만 문제가 변해도 당황해 버리고 만다. 그 차이는 생각보다 크며 수학이 지긋지긋한 과목이 될지 아니면 정말 흥미롭고 성취감을 느낄 수 있는 재미있는 학문이 될지는 여기서 갈린다. 보다 중요한 사실은 이러한 올바른 수학적 마인드 및 접근방식을 통해 머리는 끊임없이 훈련이 되고 성장해 간다는 것이다.


☞ 조카에게 들으니 너무 유명한 얘기라서 요즘 학생들은 대부분 다 알고 있다고 하네요 :)


by 다크 프로그래머

'수학 이야기' 카테고리의 다른 글

축구경기와 수학  (9) 2013.01.28
수학은 정의에서 출발한다  (2) 2013.01.28
수학공식(참고용)  (0) 2013.01.28

FFT와 모아레 제거 프로그램

개발한 것들 2013. 1. 28. 13:24

글 말미에 첨부된 프로그램은 FFT(Fast Fourier Transform)을 이용해서 이미지의 스펙트럼(spectrum)을 확인하고 수정하면서 영상의 다양한 주파수 특성을 테스트할 수 있는 프로그램입니다. 또한 이미지에 나타난 모아레(moire) 패턴을 제거할 수 있는 기능을 포함하고 있습니다.



 

예전에 FFT를 이용해서 모아레를 제거하기 위해 구현해 보았던 것인데, 이번에 포스팅을 하면서 FFT의 개념을 익히고 FFT의 효과를 직접 테스트해 볼 수 있는 일종의 교육용 소프트웨어 형태로 수정해 보았습니다. 자동 모아레 제거 기능은 단순한 방법만 포함시켜서 잘 안되는 경우도 있을 것입니다. 나중에 시간이 되면 밝기보정, 저주파 영역 처리 등 모아레 제거 기능을 보완한 버전을 올려보도록 하겠습니다.

 

푸리에 변환이란?

 

먼저, 푸리에 변환(Fourier Transform, FT)에 대해 간단히 설명을 드리겠습니다. 참고로, FFT는 푸리에 변환을 빠르게 계산할 수 있는 알고리즘을 지칭합니다. 푸리에 변환이란 어떤 시간 도메인(time domain)에서 표현된 신호(signal)를 주파수 도메인(frequency domain)에서의 표현으로 변환해주는 것을 말합니다. 예를 들어, 음파를 생각하면 시간축에 따라서 위아래로 요동치는 파형이 상상될 것입니다. 우리가 흔히 생각하는 방식은 이와같이 time domain에서 표현하는 방식입니다. 이를 frequency domain에서는 신호가 어떤 주파수 성분으로 구성되어 있는지로 표현합니다.

 

아래 그림은 3Hz로 진동하는 신호의 파형(왼쪽 그림) 및 이를 FT를 통해 주파수 도메인으로 변환한 예(오른쪽 그림)를 보여줍니다. 오른쪽 그림에 보면 주파수 3에 해당하는 지점에서 그래프가높은 값을 나타냄을 볼 수 있고 역으로 이를 통해 원래 신호가 3Hz의 강한 주기성을 가짐을 파악할 수 있습니다.

 

그림 출처: http://en.wikipedia.org/wiki/Fourier_transform

 

영상처리에서는 2차원 푸리에 변환을 사용합니다. 이는 영상을 x축 또는 y축 방향으로 따라가면서 픽셀의 밝기 변화를 파형 또는 신호로 보고 주파수 분석을 적용하는 것입니다. 푸리에 변환을 통해 얻은 각 주파수 성분의 강도를 스펙트럼(spectrum)이라고 부르는데 스펙트럼도 이미지처럼 표현이 가능합니다.

 

모아레(Moire)란

 

두 개의 격자 패턴을 서로 겹쳐놓으면 물결 모양의 어떤 새로운 주기성을 가진 패턴이 생성되는데 이를 모아레 패턴이라고 부릅니다. 가장 손쉽게 모아레 패턴을 확인할 수 있는 방법은 여러분이 가진 휴대폰 카메라로 모니터 화면을 찍어보면 됩니다. 아래 그림은 모아래가 포함된 사진(왼쪽)과 이를 첨부한 프로그램을 이용하여 모아레 제거한 사진(오른쪽)을 보여줍니다.

 


 

프로그램 사용법

 

먼저, 첨부된 프로그램을 실행시키면 다음과 같은 GUI 화면이 나옵니다.

 

 

처음의 "Load Image" 버튼을 이용하여 이미지 파일을 선택하면 아래 그림과 같이 입력 영상(왼쪽)과 이를 푸리에 변환한 스펙트럼 영상(오른쪽)을 같이 보여줍니다. 

 


스펙트럼 영상에서 중심 부분은 저주파 영역, 테두리 부분은 고주파 영역을 나타냅니다. 모아레 제거를 위해서는 모아레 패턴에 해당하는 주파수 대역을 스펙트럼에서 제거해야 합니다. 스펙터럼 영상에 마우스를 가져다 대고 드래그(drag)를 하면 아래 그림과 같이 원하는 사각형 영역을 제거할 수 있습니다.

 

 

모아레 제거를 할때 스펙트럼 영상의 중심에 있는 밝은 부분은 건드리면 안됩니다. 이 부분은 영상의 전체적인 밝기 및 원본 영상의 주요 패턴을 나타내는 부분입니다. 모아레 패턴은 비교적 고주파 반복 패턴이기 때문에 위 그림과 같이 테두리 부근에서 밝게 빛나는 부분을 제거해 주면 됩니다. 이와 같이 원하는 주파수 대역을 제거한 후에  "Inverse FFT" 버튼을 눌러서 푸리에 역변환을 하면 아래 그림과 같이 특정 주파수 패턴이 제거된 영상을 얻을 수 있습니다.

 

 

마지막으로, 세번째 "Remove Moire" 버튼을 누르면 위의 모아레 제거 과정을 자동으로 처리하여 복원된 영상을 보여줍니다. 자동 복원이 잘 되지 않을 경우에는 'radius' 파리미터와, 'threshold' 파라미터를 적절히 조절해 보시기 바랍니다. 'radius'를 줄일수록 모아레 제거가 잘되지만 원본 이미지 손상이 큽니다. 'threshold'는 작은 값을 줄수록 모아레 제거는 잘 됩니다 (대신 원본 손상도 큽니다). 


프로그램 다운로드:


fft_tool.zip


by 다크 프로그래머

'개발한 것들' 카테고리의 다른 글

걷는 속도와 비를 맞는 양 - 컴퓨터 시뮬레이션  (54) 2013.06.05
라이브 왜곡 보정 프로그램  (86) 2013.02.13
오목  (52) 2013.01.28

오목

개발한 것들 2013. 1. 28. 12:30

프로그래밍을 배우고 제가 최초로 구현했던 프로그램이 테트리스라면 두번째로 구현한 것이 오목입니다.

 

컴퓨터로 무언가 지능을 가진 프로그램을 만들면 재미있지 않을까 하는 생각에 시작하게 되었고 당시 다른 시험 준비를 하면서 틈틈히 구현을 했습니다. 무슨 책을 보거나 한 것이 아니고 그냥 무턱대고 구현을 시작한 것이라서 처음에는 컴퓨터의 실력이 형편없었습니다. 그래도 프로그램이랑 오목을 두어 보면서 조금씩 조금씩 보완해 나가다 보니 어느 순간에 저를 뛰어넘더군요.

 

이제 됐다 싶어서 같이 시험 준비를 하던 친구를 집으로 불러다 밥을 해 먹이면서 제가 만든 프로그램이랑 오목을 두게 했습니다. 결과는 거의 프로그램의 압승 ㅎㅎㅎ. 그때 속으로 느꼈던 희열이 아직도 기억에 남는군요. 그 친구는 지금은 대학 교수로 있는데 우연히라도 이 글을 보게 되면 아마도 기억이 나겠죠 ^^.

 

아쉽게도 당시 도스 환경에서 터보 C로 구현했던 오목 프로그램의 원본 소스는 지금은 사라지고 없습니다. 다만 그 뒤 인공지능 기법중 알파베타(alpha-beta) 기법이란 것을 배우고 나서 이를 적용해서 수정했던 윈도우 버전의 오목 프로그램만이 남아있습니다. 윈도우 버전의 프로그램은 첨부로 올립니다.

 

당시 알파베타 기법을 적용하면 성능이 훨씬 좋아질 것이라고 기대하면서 수정을 했었는데, 결론적으로 왠지 모르게 실망스러웠습니다. 그건 아마도 휴리스틱과 이론의 차이라 생각됩니다. 처음 도스 버전이 온갖 휴리스틱의 집합체였다면 두번째 윈도우 버전은 잘 정립된 이론에 기반한 방법입니다. 두 번째 애도 나름 잘 두긴 하는데 정형화된 틀 속에 있다는 느낌입니다. 반면 첫번째 버전은 가끔 엉뚱한 수를 두기도 하지만 종종 기발한 수를 두어서 놀래키기도 했던 것 같습니다. 그러고 보니 두 프로그램을 같이 올렸다면 흥미로운 비교가 되었을 텐데 아쉽네요.

 


omok.exe


(2016.03.14 추가)

요즘 이세돌과 알파고의 바둑 대결이 세간의 화제를 모으고 있습니다. 1국과 2국의 패배에 이어서 3국에서의 패배를 지켜보면서 저렇게까지 해야 하나.. 알파고에게 물이라도 한바가지 찌끄려야 하나 하는 생각이 들었습니다. 하지만 어제 이세돌이 알파고를 누르고 1승을 거두었을 때의 감정은 말로 표현하기 힘듭니다. 원래 블로그에 올렸던 위 오목 프로그램에 탐색 수만 늘려서 4수까지 탐색하도록 프로그램을 수정해 보았습니다. 당연히 속도는 많이 느려졌는데 성능은 그렇게 좋아진지는 잘 모르겠네요..


omok2.exe



(2016.07.02 추가)

요즘 마나님이 오목에 푹 빠져서 심심하면 오목을 둡니다. 그래서 이왕이면 내가 짠 걸로 둬 보라고 추천을 했습니다. 처음에는 컴터한테 거진 지더니 요즘에는 자꾸 이깁니다. 그러면서 프로그램에 자꾸 오류가 뜬다고 불평을 합니다. 오류가 뜨는 것은 아래 댓글에서도 몇번 지적되었던 사항인대 사실 그동안 귀찮아서 손을 대지는 않았습니다. 하지만 마나님이 두시는데 이럴 순 없다 싶어서 거의 15년만에 코드를 다시 봤습니다. 그랬더니 버그도 많이 발견되었고 논리적 오류도 발견되었습니다. 전반적으로 코드를 다시 수정하고 버그 및 성능을 보완한 버전을 다시 올립니다. 난이도(앞으로 몇 수를 볼 것인지)를 조정하는 기능을 추가했고 앞서의 두 버전에 비해 성능도 일부 개선이 되었습니다.


omok_advanced.exe


☞ 구현된 3x3 금지 기능은 오목의 공식적인 3x3 규칙과는 다릅니다. 여기서는 연속해서 붙어있는 돌 3개와 3개가 만나는 경우만을 금하는 것으로 구현되어 있습니다.


by 다크 프로그래머