맥도날드(페스트푸드) 자동화 주문 관리시스템

- 김 동 현 -

맥도날드(페스트푸드) 자동화 주문 관리시스템

김동현

대구대학교 전산통계학과 4년

요약문

데이터베이스의 서버와 클라이언트 형식으로 상호간의 주문과 관리하는 시스템으로 페스트푸드 점들 중에 맥도날드를 선택하여 음식을 주문하고 그 주문을 매니저가 받음으로 프로그램이 진행된다. 전산으로의 주문으로 시간 단축과 마일리지 적립 그리고 인건비의 절약을 기반으로 연구와 프로그램을 만들게 되었고 보다 편리하고 간단하게 시스템을 구축하였다. visual c++6.0과 콘솔프로그래밍으로 MySQL 데이터베이스 시스템을 사용하여 처리가 빠르다.

Ⅰ. 서 론

1. 연구의 배경 및 목적

요즘 많은 페스트푸드 점들이 있다. 그 중에서도 맥도날드로 정했고 여러 종류의 주문방법이 있다. 그 중에서도 흔히 사람들은 페스트푸드 점에 직접 가서 주문을 하고 거기서 만들어 져서 나올 때까지를 기다린 후에 음식을 먹거나 포장해 간다. 우선 페스트푸드 점을 방문해야 한다는 번거로움이 제일 큰 과제이다. 요즘 맥도날드에서는 전화로 주문을 하고 일정 비용을 더 추가하면 집까지 배달해 주는 시스템을 도입해서 배달업도 하고 있다. 여기에서 만약 전화비도 들지 않고 추가 비용 없이 모든 것을 전산화 시키면 편리하고 데이터베이스를 이용하면 충분한 시간 절약을 할 수 있겠다는 생각이 이 프로그램 개발하게 만들었다. 측면별 장점은 사용자적인 측면으로는 페스트푸드 맥도날드에서 점원이 아닌 컴퓨터를 통해 자동으로 음식을 주문할 수 있고 자신의 마일리지를 카드휴대가 아닌 전산처리로 인한 편리함과 주문 대기자에 대한 전광판 확인으로 자신의 순서를 명확화 시킬 수 있다. 또 자신의 취향에 따른 품목을 통한 즐겨하는 음식을 조회가능 하다. 관리자적인 측면으로는 해당 품목에 대한 등록, 수정, 조회, 삭제가 가능하며 점원에 대한 인건비 감소(전산화 처리)가 가능하다 또 판매 매출에 대한 관리도 가능하다.

2. 개발환경 및 수행환경

visual c++6.0을 기반으로 비쥬얼을 보여주기 위한 콘솔프로그래밍에 대해 처리가 빠르며 동일한 프레임워크로 인해 모듈개발이 용이하며 데이터베이스는 MySQL을 사용함으로써 데이타베이스 접근 라이브러리가 강하며 쿼리의 응답에 쉽게 대응할 수 있고 데이타베이스의 안정성이 뛰어남을 보여주는 프로그램이다.

3. 개발 알고리즘

1) 전체 알고리즘 구도

<그림 Ⅰ-1> 알고리즘 구도

2) menu테이블(주문리스트)

<표 Ⅰ-1> menu테이블

3) taste테이블(자신의 음식 취향리스트)

<표 Ⅰ-2> taste테이블

4) user테이블(회원정보)

<표 Ⅰ-3> user테이블

5) manager테이블(관리자정보)

<표 Ⅰ-4> manager테이블

6) pop테이블(인기음료테이블)

<표 Ⅰ-5> pop테이블

7) sell테이블(판매정보)

<표 Ⅰ-6> sell테이블

8) 네트워크 패킷 설계

<표 Ⅰ-6> 네트워크 패킷 설계 테이블

Ⅱ. 본  론

1. 알고리즘 및 프로그램 소스

1) 서버(Server)

(1) CoffeManagerDlg (서버 메인 소스)

(2) data (네트워크 송수신 소스)

(3) dataSocket (네트워크 소켓 지정 소스)

(4) DelDlg (삭제목록 소스)

(5) KbcBmp (그림파일목록 소스)

(6) KbcButton (버튼 생성 소스)

(7) ListTable (리트스 테이블 소스)

(8) ManagerTable (매니저 테이블 소스)

(9) MemTable (메모리 테이블 소스)

(10) PopTable (팝 테이블 소스)

(11) SellTable (셀 테이블 소스)

(12) ServerSocket (서버에 소켓 연결 소스)

(13) ShowDlg (메인화면을 보여주는 소스)

(14) ShowMemverDlg (회원목록을 보여주는 소스)

2) 클라이언트

(1) CoffeDlg (클라이언트 메인 소스)

(2) data (네트워크 송수신 소스)

(3) DataSocket (네트워크 소켓 지정 소스)

(4) FindDlg (찾기 메인 소스)

(5) JoinDlg (접속 메인 소스)

(6) KbcBmp (그림 파일 목록 소스)

(7) KbcButton (버튼 생성 소스)

(8) ListTable (목록 테이블 소스)

(9) LoginDlg (로그인 메인 소스)

(10) MenuDlg (메뉴 메인 소스)

(11) MilDlg (마일리지 메인 소스)

(12) OrderDlg (주문 메인 소스)

(13) ReviseDlg (정보수정 메인 소스)

(14) TasteDlg (인기메뉴 메인 소스)

Ⅲ. 결 론

1. 기능 분해 결과 및 각 모듈 설명

[그림 Ⅲ-1] 맥도날드 클라이언트 메인화면

아이디 : 사용자 아이디를 입력한다.

암호 : 사용자 패스워드를 입력한다.

가입 : 회원가입을 할수 있다.

서버접속 : 서버의 아이피를 입력 한다.

접속 : 해당 아이디와 패스워드로 로그인을 한다.

[그림 Ⅲ-2] 회원 가입 화면

아이디 : 아이디를 입력한다.

암호 : 패스워드를 입력한다.

연락처 : 회원 연락처를 입력한다.

이메일 : 회원이메일을 입력한다.

중복체크 : 등록하려는 아이디가 중복인지 확인한다.

JOIN : 해당 사항을 기입하면 가입한다.

확인 : 조인 후 가입절차를 마친다.

[그림 Ⅲ-3] 클라이언트의 메인화면 모습

상단아이디 : 로그인한 회원의 아이디를 출력한다.

대기리스트 : 현재 주문한 음식의 목록을 확인한다.

대기시간 : 자신의 음식의 대기시간을 조회한다.

메뉴리스트 : 현 지점의 메뉴 리스트를 본다.

취득시간 : 자신의 음식을 take하는데의 시간을 조회한다.

주문 : 해당음료를 주문하기 위한 기능이다.

내정보조회 : 자신의 대한 각종 정보 출력 및 수정한다.

나가기 : 로그아웃을 한다.

이달의 HOT FOOD : 현 지점에 가장 많이 팔린 음식를 출력한다.

내가 주문한 음식리스트 : 자신의 주문한 음식에 대해서 다시 한번 confirm한다.

결재 : 해당음식에 대해 결재를 하여 완료를 한다.

선택된 음식제거 : 주문한 음식리스트에서 선택된 음식리스트를 제거한다.

[그림 Ⅲ-4] 메뉴 리스트 화면

현재 지점에서의 메뉴리스트를 출력

[그림 Ⅲ-5] 대기 시간 조회 화면

[그림 Ⅲ-6] 주문하기 화면

왼쪽 리스트 컨트롤 : 자신의 주문목록을 보여준다.

오른쪽 리스트 컨트롤 : 현 지점의 선택한 메뉴를 보여준다.

주문이동: 주문하기.

주문취소: 제거하기.

주문하기 : 해당 메뉴를 주문한다.

[그림 Ⅲ-7] 마이페이지

자신에 대한 각종 정보 출력 및 수정이 가능하다

[그림 Ⅲ-8] 나의 취향리스트

총 소비금액 : 본 지점에 소비한 총금액을 보여준다.

나의 취향 : 자신이 섭취한 음식 목록을 보여준다.

좋아하는 음식 : 시식한 음식의 총수량을 보여준다.

[그림 Ⅲ-9] 마일리지 화면

마일리지 점수 : 자신의 총 마일리지를 보여준다. 10회시 쿠폰을 지급한다.

[그림 Ⅲ-10] 자신의 정보 수정

자신의 회원 정보를 수정한다.

[그림 Ⅲ-11] 결재 방식 선택

자신의 결재에 대한 방법을 선택한다.

[그림 Ⅲ-12] 마일리지 부족시 에러창

마일리지에 대한 결재금액이 부족시에 마일리지 부족이라는 메시지창이 뜬다.

[그림 Ⅲ-13] 서버에서 주문 수락을 대기하는 화면

서버의 주문대기에 해당 음료에 대한 목록이 생성이 되면 해당음료에 대해서 선택후 요리수락을 누르면 해당 음료가 클라아언트의 대기 목록으로 전송이 된다.

[그림 Ⅲ-14] 클라이언트에서 해당 음료에 대한 대기 시간을 출력하는 화면

고객아이디 : 자신의 아이디

품명 : 해당 음식명 출력

대기시간 : 해당 음료가 완료되기 전까자의 대기 시간

[그림 Ⅲ-15] 서버가동시 확인 알림

서버가동을 통해 자신의 아이피와 포트번호로 리스닝상태.

[그림 Ⅲ-16] 클라이언트로부터 접속 요청시

클라이언트의 connect요청을 처리한다.

[그림 Ⅲ-17] 서버에서 상품 등록 화면

서버에서 상품등록을 눌르면 해당상품에 대해서 등록을 한다.

[그림 Ⅲ-18] 상품 수정시 화면

해당 상품명으로 검색을 하면 해당상품명이 출력.

수정하려는 데이터로 수정 후 수정 버튼을 눌르면 완료.

[그림 Ⅲ-19] 상품 삭제 화면

해당되는 상품명을 입력 후 삭제를 누르면 해당음료 삭제가 된다.

[그림 Ⅲ-20] 회원보기 화면

현재 가입되어 있는 회원의 정보를 볼 수가 있다.

[그림 Ⅲ-21] 매출보기 화면

현재 판매된 매출 목록을 조회한다.

[그림 Ⅲ-22] 물품보기화면

현재 등록되어 있는 물품을 조회한다.

[그림 Ⅲ-23] 관리자 화면 수정 화면

현재 관리자의 아이디와 패스워드를 수정한다.

Ⅳ. 논문을 마감하며

학교를 다니면서 복수전공을 하다 보니 C언어에 대한 기초가 많이 부족했다. 그래서 논문을 마감하기까지 어려움도 많았고 뒤처지기 싫어서 매번 반복하고 노력하면서 1년의 준비기간을 두고 한 보람이 있는 것 같다. 처음에는 처음 이 프로그램의 구상을 하고 설계를 하는 동안 과연 이걸 해낼까 하는 걱정이 많았지만 이렇게 완성을 하니까 뿌듯하고 졸업을 앞둔 4학년으로써 감회가 새롭다. 항상 전산공학 복수전공을 많이 응원해준 교수님들과 친구들 그리고 선배님들께 감사하며 앞으로도 컴퓨터 분야로 나아가기 위해 많은 프로그램을 만들어 볼 예정이고 열심히 공부하고 노력하겠다.

Ⅴ. 참고문헌

[1] 서현우 저, (2007), 뇌를자극하는 C프로그래밍, 한빛미디어

[2] Richard Neapolitan/Kumarss Naimipour 저, (2004), FOUNDATIONS of ALGORITHMS USING C++ PSEUDOCODE 3th, 사이텍미디어

[3] 윤성우 저, (2004), 熱血講義 C프로그래밍, FREELEC

군집분석을 이용한 위성영상의 패턴분류

- 김 미 란 -

김미란

대구대학교 전산통계학과 4년

요약문

영상분류는 대상영상을 자동으로 감지하거나 분류하는 기술이며, 최근에는 의학, 인공위성 영상 분석, 전자회로 분석 등의 다양한 분야에서 사용되어지고 있다. 최근의 위성영상은 높은 해상도를 가지고 있으며, 매우 다양한 지구표면의 정보를 포함하고 있어 위성영상으로부터 유용한 정보를 경제적이고, 빠르게 검출하는 것이 매우 중요하다. 지금까지 연구되어 왔던 위성영상분류를 위한 기법에는 평행육면체 기법(Parallel-Piped Classification), 최소거리기법(Minimum Distance Classification), MLC(Maximum Likelihood Classification) 등의 감독분류 기법과 순차군집분류 기법, K-Means군집분류 기법, ISODATA 기법, Fuzzy C-Means군집분류 기법 등의 무감독분류 기법이 있다. 본 논문에서는 감독분류 기법의 MLC와 무감독분류 기법의 K-Means 군집분류 기법을 Microsoft Visual C++ 를 이용해 시스템을 구현하고 실제 위성영상의 분류 결과를 분석하며 두 방법의 장단점을 살펴본다. 시스템에 관련된 사항은 부록에 정리되어있다.

Ⅰ. 서 론

군집분석을 이용한 위성영상의 패턴분류

영상분류는 대상영상을 자동으로 감지하거나 분류하는 기술이며, 최근에는 의학, 인공위성 영상분석, 전자회로 분석 등의 다양한 분야에서 사용되어지고 있다. 원격탐사는 주로 항공기나 인공위성에 탑재된 분광감지기를 이용하여 지표면의 대상물에서 반사 또는 복사되는 전자파를 측정하여 분석함으로서 대상물이나 현상에 대한 해석 및 감시를 하는 기술을 말한다. 항공기나 인공위성으로부터 얻어진 화상으로부터 지표면의 특징을 분류하여 피복도를 작성하는 것은 원격탐사 분야에사용자의 경험에 의존적이라는 문제점이 있다. 그에 반해 무감독분류 기법은 영상에 대한 사전지식을 가지지 못한 경우 적용이 가능한 분류기법이다. 일반적으로 사전지식을 획득하기 위해서는 현지답사, 실측 등의 많은 부과적인 작업이 필요하다. 그러나 요즈음 인공위성 영상은 넓은 지역의 고해상도 영상을 사용하기 때문에 사전지식을 획득하기 위해 시간과 비용이 많이 요구되고, 빠른 분류 결과를 요구한다.

1. 위성영상

1) 위성원격탐사의 개념

지구상에 존재하는 다양한 문제를 해결하기 위하여 연구가들은 자료를 취득하며, 취득된 자료는 그 자체가 해결책이 되기도 하고 다른 분석을 위한 도구로 사용되기도 한다. 환경, 지리, 산림, 농업 등 여러 분야에서 데이터는 현장에서 가각의 도구나 기기를 이용하여 정확하게 측정하는 것이 분석을 위한 가장 좋은 자료 취득방식이지만, 때때로 대규모 지역(산림, 평야, 침수지역)을 대상지역으로 하는 경우 또는 직접 접근하기 어려운 경우 원거리에서 대상지역의 자료를 취득할 수밖에 없다. 이렇게 원격탐사는 직접 접촉하지 않고 얻어진 다수의 자료를 이용하여 다양한 목적에 사용되고 있으며, 그 활용범위는 점점증가하고 있다. 즉 원격탐사(Remote Sensing)는 멀리 떨어져 있는 대상물을 관측하는 기술로서 측정하고자 하는 목표물에 직접 접촉하지 않고 목표물에서 복사되어 나오는 전자파를 감지하여 그 물리적 성질을 측정하는 기술이다. 대상물로부터 반사 또는 복사되는 전자파 등을 수신하는 장치를 리모트 센서(Remote Sensor)라고 하고 카메라와 스캐너 등이 여기에 속한다. 그리고 이러한 센서를 탑재하는 이동체를 플랫폼(Platform)이라고 하고 항공기와 인공위성 등이 여기에 속한다. 원격탐사라는 사진측량, 사진판독, 사진지질 등을 종합하는 의미로 사용되기 시작하였고 1972년 최초의 지구관측위성인 Landsat이 발사되고 나서 급속도로 보급되었다. 원격탐사에 의해 지표의 대상물과 현상을 판독/해석할 수 있는 것은 ‘종류와 환경조건이 다르면 모든 물체는 서로 다른 전자파를 반사 혹은 복사하는 특성을 가지고 있다’라는 물체의 전자파 특성에 기초하고 있다. 원격탐사는 물체에서 반사 혹은 복사되는 전자파의 고유성에 착안해서 전자파로 관측된 물체를 식별하거나 그것이 놓여진 환경조건을 파악하는 기술이라고도 할 수 있다.  원격탐사의 응용분야는 실내의 공업계측에서 넓은 대륙, 해양의 정보수집, 지구규모의 환경변동 감시 등에 이르기까지 매우 다양하다. 도시와 같은 지역규모에서는 토지개발계획과 녹지/식생의 변화 감시등에 이용되며, 사막화 등과 같은 지구규모의 자연환경을 파악하는데도 중요한 수단으로 이용되고 있다. 해양 분야에서는 해면수위, 오염상황, 식물플랑크톤분포, 해면온도 등 여러 가지 정보를 획득할 수 있으며 또한 원격탐사에서 얻어진 파도정보로부터 해상풍의 풍향/풍속을 추정할 수 있다. 대기에서는 이산화탄소와 오존 등 미량성분 조성조사, 구름영상으로부터 기상현상 해석 등에 이용되고 있다.

[그림 .1] 원격탐사의 기본원리

[그림 1.]

<그림 1.1>과 <그림 1.2>에서와 같이 인공위성에서의 원격탐사 자료의 획득은 전적으로 관측 센서에 입사하는 전자기파의 세기에 의존한다. 센서에 지표면의 물체에 반사된 태양광선이 입사함으로서 그 빛의 세기가 영상 자료의 형태로 저장되어진다. 일반적으로 모든 물질은 전자기파 중 특정한 파장의 전자를 흡수하거나 반사하는 고유한 특징을 가지는데, 이러한 성질을 그 물체의 분광 특성이라고 한다. 이 분광 특성에 의해 표적물로부터 반사되거나 복사되는 에너지의 세기는 물체의 특성에 따라 달라지며, 같은 대상물이라도 파장대에 따라 반사 또는 복사되는 에너지의 비율이 달라지기 때문에 물체의 판별이 가능하게 된다. 원격탐사에서는 지상 물체에 대한 다양한 정보를 얻어내기 위하여 여러 가지 파장대에서 획득한 영상 자료를 사용한다. 인공위성으로부터 얻어진 원격탐사 영상은 다양한 보정 작업을 거친 후 분류를 위한 자료로 사용되어진다.

2)Landsat 위성의 특징

Landsat Program은 1972년 미국의 USGS(United State Geological Survey), NOAA(National Oceanic and Atmospheric Administration), Space Imaging 등과 공동으로 NASA(National Aeronautics and Space Administration )에서 개발하여 ERTS-1(Earth Resources Technology Satellite)이란 이름으로 발사되기 시작한 지구최초의 탐사위성 발사 계획으로서 놀라운 탐사능력을 지님으로서 우주공간으로부터의 원격탐사 기술의 커다란 진보를 이루는데 지대한 공헌을 하였다.

이후 Landsat(Land Satellite)이라는 이름으로 개명되어 현재 7호까지 발사되었으며, 기본적으로 30m의 공간해상도를 가지는 radiometric sensor 인 TM(Thematic Mapper)이 탑재되어 있다. 또한 가장 최근의 Landsat series인 Landsat-7은 1999년 4월에 발사되었으며, 공간해상도 30m를 지원하는 Multispectral mode와 공간해상도 15m를 지원하는 Panchromatic Mode가 포함된 ETM+(Enhanced Thematic Mapper+) sensor가 추가적으로 탑재되어 있다.

Landsat은 약 705Km 의 고도에서 26,000km/h의 속도로 궤도를 돌고 있다. 또한 이 위성은 99분마다 한 번씩 궤도를 돌면서 정교한 센서로 수 백만개의 데이터를 기록한다. 이 센서는 RGB (적, 녹, 청) 채널을 사용하여 가시광선 영역의 칼라 사진을 촬영하며, 네 개의 적외선 채널도 갖고 있다. 이 위성이 촬영한 한 scene의 사진은 각각 가로 185 km 세로 170 km의 지역을 나타내며, 판매단위인 한 scene당 면적은 가로, 세로 공히 180km로 resampling되어 표현된다.

또한 이 위성은 적도기점에서 약간 우측각으로 북극점과 남극점을 통과하는 자전동기 궤도(Sun Synchronous Orbit)를 따라 움직이고 있다. Landsat은 하루에 15회씩 지구를 회전하며, 동일지점을 통과하는데 16일의 시간이 소요된다.

<표 1.1> Landsat위성의 해상도

	분광해상도 센서가 감지하는 파장대의 수와 파장대의 크기	공간해상도 센서에 의해 한 개의 화소에 표현할 수 있는 지상면적, 또는 물체의 크기	시간해상도 선세가 특정 지역의 영상을 기록하는 주기	복사해상도 지표에서 반사 또는 방출된 복사에너지가 센서에 기록될 때 식별 가능한 신호레벨의 수
Landsat MSS	0.6 ~ 0.7 0.7 ~ 0.8 0.8 ~ 1.1 10.4 ~ 12.6	80m	16일	6bit
Landsat TM	0.45 ~ 0.52 0.52 ~ 0.60 0.63 ~ 0.69 0.76 ~ 0.90 1.55 ~ 1.75 2.08 ~ 2.35	28.5m	16일	8bit

<표 1.> Landsat 위성의 밴드별 특징

MSS	TM	파장([eqn: mum])	영역	주요응용분야
	1	0.45 ~ 0.52	Blue	물을 투과하도록 디자인, 해안선 Mapping, 토양 및 식생 구분, 산림도의 Mapping, 지표면의 관측
1	2	0.52 ~ 0.60	Green	식생 반사의 녹색 피크를 통해 식생 구분
2	3	0.63 ~ 0.69	Red	클로로필A 흡수 영역을 관측함으로써 식생구분
3	4	0.76 ~ 0.90	Near-IR	식생, Biomass 양, 물의 구별, 토양의 수분 구별
4	5	1.55 ~ 1.75	Mid-IR	식생과 토양의 수분 구별, 구름과 눈의 구별
	6	10.4 ~ 12.5	Thermal-IR	온도의 Mapping
	7	2.08 ~ 2.35	Mid-IR	식생의 수분 정도 구별, 광물과 광석 종류 구별

2. 위성영상 포맷

다중분광 인공위성영상은 공간적 위치와 분광정보를 포함하고 있다. 다중 분광영상의 자료포멧은 화소 배치 속에 밴드별 정보를 어떻게 포함하고 있느냐에 따라 BSQ(Band Sequential), BIL(Band Interleaved by Line), BIP(Band InterLeaved By Pixel)등 3종류로 나누어진다. BSQ형

식은 각 밴드의 2차원 영상자료를 밴드 순으로 정렬하고, BIL형식은 한 라인 속에 한 밴드의 분광값을 나열한 것을 밴드 순으로 정렬하고, 그것을 전체 라인에 대해 반복한다. 그리고 BIP형식은 한 라인 중의 하나의 화소 분광값을 나열한 것을 그 라인의 전체 화소에 대해 정렬하고, 그것을 전체 라인에 대해 반복한다. 본 논문에서 구현한 군집분류 시스템에서는 ERDAS사의 LAN포멧과 GeoTIFF형식으로 저장되어 있는 인공위성영상을 BIP포멧으로 변환하여 작업한다. 각 포맷의 형태는 [그림 1.3]과 같다.

(1,1)	(1,2)					밴드1
(1,1)	(1,2)					밴드2
(1,1)	(1,2)					밴드3
(2,1)	(2,2)
(2,1)	(2,2)
(2,1)	(2,2)

(a) BIL

(1,1)	(1,2)	(1,3)				밴드1
(2,1)	(2,2)
(3,1)
(1,1)	(1,2)	(1,3)				밴드2
(2,1)	(2,2)
(3,1)
(1,1)	(1,2)	(1,3)				밴드3
(2,1)	(2,2)
(3,1)

(b) BSQ

(1,1)	(1,1)	(1,1)	(1,1)	(1,2)	(1,2)	(1,3)	(1,3)	(1,3)
(2,1)	(2,1)	(2,1)	(2,2)	(2,2)	(2,2)
(3,1)	(3,1)	(3,1)
															(i, j)	(i, j)	(i, j)
밴드1	밴드2	밴드3

(c) BIP

[그림 1.3] 영상자료 포맷(3밴드의 경우)

우리가 컴퓨터에서 흔히 쓰는 BMP, JPG 등 이미지 파일들도 영상에 대한 데이터를 [그림 1.3]의 형태로 저장하고 있다. 우리가 눈으로 보는 모니터는 빛의 삼원색인 Red, Green, Blue의 조합으로 표시되기 때문에 이미지파일을 위성영상에 대응시켜보면 밴드가 3개인 영상데이터라고 할 수 있다. 이러한 영상 데이터는 우리가 실습해봤던 통계자료와는 다른 형태이며, 어떻게 처리 할 것인가 하는 고민을 할 수도 있다. 하지만 영상데이터의 좌표를 무시하고 행, 열의 순서로 순차적으로 나열되어있고 각 밴드는 각각의 변수라고 생각하면 이해하는데 도움이 될 것이다.

3. 분류 기법

1) 감독분류 기법

감독분류 기법은 영상에서 분류하고자 하는 정보 집단의 위치나 분광 특성을 사용자가 정확히 알고 있을 때 사용하는 방법이다. 일단 영상자료로부터 집단의 각 밴드별 화소 값을 추출해야 한다. 이렇게 추출된 영상의 일부분을 표본 집단이라고 하며, 분류작업 시 표본 집단의 통계적 수치를 계산하여 입력 자료로 사용한다. 분류하고자 하는 자료의 표본 집단이 완성되면, 이들과 비슷한 통계 값을 갖는 화소들을 계속 수집하여 집단의 크기를 확장해 감으로써 전체 영상에 대한 분류 작업을 완성하게 된다. 감독분류 기법은 사용자의 판단이 전체 결과에 매우 중요한 요소로 대두하기 때문에 많은 경험과 정확한 사전 지식이 요구된다. 이와 같은 감독분류 기법에는 평행육면체 기법, 최소거리 기법, MLC등이 있다. [그림 1.4]는 원 영상데이터에서 훈련영역 즉, 표본 집단을 추출한 후 전체영상에 대한 분류과정을 나타내고 있다.

[그림 1.4] 위성영상 데이터의 군집분류

2) 무감독분류 기법

무감독분류 기법은 표본 집단과 같은 사전정보 없이 영상을 구성하는 화소 값의 공간적, 분광적 특성만을 이용하여 분류 작업을 수행하는 기법이다. 이 방법은 순수한 통계처리 기법에 의해 수행된다는 점에서 군집화(Clustering)라고 불리우며, 분류할 군집의 개수와 각 분광 군집 사이의 한계 거리만을 지정해 줌으로써 작업이 가능하다. 이와 같은 무감독분류 기법에는 순차군집분류 기법, K-Means군집분류 기법, ISODATA 기법 , Fuzzy C-Means군집분류 기법 등이 있다.

Ⅱ. 본 론

무감독분류 기법은 분류할 군집의 개수와 각 분광 군집 사이의 한계 거리만을 지정해 줌으로써 작업이 가능하다. 일단 사용자가 초기 입력 값을 지정 해 주면, 컴퓨터가 분류할 군집 개수만큼의 초기 군집중심을 자동으로 생성하여 통계 평면상에 임의로 위치시키게 되는데, 이 화소가 군집을 구성하는 군집중심으로 작용한다. 분류가 시작되면 컴퓨터는 영상 내 각각의 화소들을 그 화소와 가장 비슷한 분광특성을 갖는 초기 군집중심과 같은 군집으로 분류를 수행한다. 분류 작업이 끝난 후에는 군집에 소속된 화소들을 사용하여 새로운 군집중심을 선택하게 되고, 위와 같은 작업을 사용자가 입력한 반복횟수 또는 더 이상 군집중심의 변화가 없을 때까지 계속하게 된다. 무감독 분류는 사용자의 사전지식 없이도 분류가 가능하다는 장점이 있지만, 분류된 항목이 정확히 어떤 항목인지는 알 수 없고 단지 대상 영상의 분포나 구성요소들만을 확인할 수 있다. 본 논문에서는 여러 무감독분류 기법 중 K-Means 군집분류 기법을 구현해 보았다.

1. 군집분류

1) K-Means 군집분류

K-Means 군집분류 기법은 영상을 통해 얻고자 하는 군집의 개수를 사용자가 지정하도록 되어있고, 사용자가 지정한 개수만큼의 군집 중심을 다차원 측정공간상에 위치시킨다. 영상의 각 화소들은 군집들의 임시 평균벡터들 중에서 가장 가까운 군집에 할당된다. 모든 화소들이 이러한

방법으로 분류된 후, 군집은 새로운 군집중심이 계산된다. 이렇게 수정된 군집중심은 영상 재분류의 근거로 사용된다. 군집중심의 위치가 더 이상 변하지 않을 때 까지 알고리즘의 반복이 지속된다. K-Means군집분류 기법은 영상을 반복적으로 분석하기 때문에 매우 많은 계산 량이 요구된다. 그래서 이 기법은 전체 영상보다 부분영상에 적용되곤 한다.

n개 개체가 p차원 다변량 개체라고 했을 때 각 개체는 초기에 설정된 k개의 군집 중 어느 군집에 할당된다고 가정하자. 이때 i번째 개체의 j번째 변수를 X(i, j)로 표시하고, c번째 군집에 속한 [eqn: n_c] 개 개체들의 j번째 변수에 대한 평균을 [eqn: bar {X~}(c,~j)]로 표시했을 때 i번째 개체와 c번째 군집 사이의 유클리드 거리는 다음과 같이 표시할 수 있다.

[eqn: D(i,~c)~=` LEFT ( ` sum _{j=1} ^{p} [X(i,~j)~-~ bar{X~} (c,~j)] ^{2} RIGHT ) ^{{1} over {2}}]

<수식 2.1>

또한 각 개체를 c번째 군집에 재 할당할 때 오차자승합 E는 다음과 같다.

[eqn: E~=~ sum _{i=1} ^{n} [D(i,~c(i))] ^{2}]

<수식 2.2>

<수식 2.2> 에서 c(i)는 i번째 개체를 포함하고 있는 군집을 뜻하고, D(i, c(i))는 i번째 개체와

그 개체를 포함하고 있는 군집 사이의 유클리드거리를 표시한다. 따라서 분리군집방법은 각 개체를 어느 한 군집으로부터 다른 군집으로 움직일 때 오차자승합을 계산하여 비교하면서 더 이상 움직일 개체가 없을 때(오차자승합이 최소화)까지 반복하게 된다.

2) MLC(Maximum Likelihood Classifier)

최대우도비를 이용한 분류법은 픽셀이 최대우도비에 대응되는 군집으로 분류되는 위성영상의 군집화에 가장 대중적으로 사용되는 기법중 하나이다. 우도비는 하나의 픽셀이 소속되는 군집 k의 사전 확률이다.

[그림 2.1] 최대우도법의 개념

[그림 2.1]는 밴드가 밴드1, 밴드2 두개 이고 군집이 군집A, 군집B의 경우에 임의의 좌표 X([eqn: band_{i}~,~band_{j}])의 군집을 결정하는 최대우도비분류의 개념을 나탄 낸 그림이다. 첫 번째 그래프는 밴드1에 대한 군집A와 군집B의 분포이고 두 번째 그림은 밴드1과 밴드2의 산접도이며 군집A와 군집B의 분포도 함께 나타낸 것이다. 밴드1과 밴드2의 산점도에서 임의의 좌표 X([eqn: band_{i}~,~band_{j}])의 군집을 결정하고자할 때 각 군집의 우도비를 보면 군집B의 우도비가 군집A의 우도비보다 크므로 X([eqn: band_{i}~,~band_{j}])는 군집B로 분류할 수 있다.

[그림 2.2] 원 영상에서의 훈련영역 추출과 군집화

최대우도비를 이용한 군집분석을 하기 위해서는 우선 원 위성영상 데이터에서 훈련영역을 선택해야 하는데 그 방법은 [그림 2.2]와 같이 분석자가 직접 영역을 선택할 수도 있고 임의로 픽셀들을 선택하고 선택된 밴드를 몇 개의 집단으로 나눈 후 그 집단의 정보로 전체 데이터에 대해 군집화를 수행한다.

[그림 2.3]	[그림 2.4]

훈련영역을 선택할 때 고려해야 될 사항이 있는데 [그림 2.3]과 같이 우도비가 같은 경우 어느 군집으로 분류해야 할지 고민 해 볼 필요가 있다. 물론 위성영상의 밴드는 3~7개 정도 되므로 [그림 2.3]과 같은 경우가 거의 발생하지 않겠지만 각 군집의 분산이 커 분포의 겹치는 부분이 많다면 분류가 잘못 되는 케이스의 수가 많아 질것이다. 특히 사전확률 계산 시 유클리디언 거리를 이용하면 밴드 수가 많더라도 유클리디언 거리는 같게 나오는 경우가 종종 발생한다.

[그림 2.3]과 같은 경우를 최소한으로 하기 위해 본 논문에서는 사전확률 계산 시 유클리디언 거리가 아닌 Mahalobis거리를 이용하며 각 훈련영역의 분포를 작게 하기 위해 k개의 훈련영역 각각에 대해 중심을 구하고 훈련영역[eqn: i] 전체픽셀에 대해 중심[eqn: i]와의 유클리디언 거리를 구하고 유클리디언 거리의 평균을 계산한다. 그리고 훈련영역[eqn: i]의 전체픽셀 중 유클리디언 평균거리 내의 픽셀들만 모아 훈련영역[eqn: i]로 대체한다. 대체된 훈련영역들의 중심을 새로 구하고 그 새로운 중심으로 전체 픽셀에 대한 분류작업을 한다.

[그림 2.4]는 프로그램 수행 중 훈련영역을 선택하면 보여지는 밴드별 산점도와 히스토그램이다. 산점도는 두 종류로 나타나는데 붉은색으로 표시된 부분이 유클리디언 거리의 평균거리 내부의 픽셀에 대한 산점도이고 붉은색을 포함한 회색 산점도가 원래의 훈련영역에 대한 산점도다.

사전확률은 n차원 다변량 정규확률밀도함수를 이용해 계산한다.

[eqn: P(X~| w_{ i}) = 1over{(2pi)^{N/2}| sum _{ } ^{ }i |^{1/2}}exp[-{1}over{2}({X-U_{i})}^{T}sumi^{-1}(X-U_{i})]]
	[eqn: | sum _{} ^{} i|] = 공분산행렬 [eqn: sum _{} ^{} i]의 행렬식 [eqn: sum _{} ^{} i ^{-1}] = [eqn: sum _{} ^{} i]의 역행렬 [eqn: (X-U _{i} ) ^{T}] = 벡터 [eqn: (X-U _{i} )]의 전치행렬

위의 식을 계산하기 위한 부수적인 수식을 보면 다음과 같다.

□ 하나의 픽셀에 대한 관측벡터

[eqn: X`~=left[~pile{ x_{1} #{ x_{2} }#{ . } #{ . }#{ x_{k} }}~right]],     k = 1, 2, … , n밴드

□ N개의 픽셀에 대한 관측벡터

[eqn: X_{1}`~=left[~pile{ x_{11} #{ x_{21} }#{ . } #{ . }#{ x_{N1} }}~right]~,~~X_{2}`~=left[~pile{ x_{12} #{ x_{22} }#{ . } #{ . }#{ x_{N2} }}~right]~,~ ……~,~~X_{N}`~=left[~pile{ x_{1k} #{ x_{2k} }#{ . } #{ . }#{ x_{Nk} }}~right]]

□ 두 개의 밴드([eqn: k, ~l])간의 공분산

[eqn: C_{kl}~=~{sum _{j=1 } ^{n }(x_{kj}- mu_{k} ) (x_{lj}- mu_{l} )}over{n - 1}]

밴드 수 : [eqn: k = 1,~2,~…~,N]

밴드 수 : [eqn: l = 1,~2,~…~,N]

□ 분류항목 i에 대한 밴드 k의 평균

[eqn: mu_{ik}~=~{ LEFT ( sum_{j=1}^{n}x_{ikj} RIGHT ) }over{n}],	k = 1, 2, … , N밴드 j = 1 , 2, … , n화소 [eqn: i] = 분류항목

□ 분류항목 i에 대한 N개 밴드의 평균 벡터

[eqn: U_{i}`~=left[~pile{ mu_{i1} #{ mu_{i2} }#{ . } #{ . }#{ mu_{iN} }}~right]]

□ 분류항목 i에 대한 N개 밴드의 공분산 행렬

[eqn: C_i ~=~left[ pile{c_{i11}~~c_{i12}~~…~~c_{i1N}#c_{i21}~~c_{i22}~~…~~c_{i2N}#⋮~~⋮~~…~~~⋮#c_{iN1}~~c_{iN2}~~…~~c_{iNN}}Right]] = [eqn: sumi ~=~left[ pile{ sigma _{i11}~~sigma_{i12}~~…~~sigma_{i1N}#sigma_{i21}~~sigma_{i22}~~…~~sigma_{i2N}#⋮~~⋮~~…~~~⋮#sigma_{iN1}~~sigma_{iN2}~~…~~sigma_{iNN}}Right]]

□ Mahalanobis 거리

[eqn: d ~=~ LEFT ( LEFT( pile{x_{1k}#x_{2k}#⋮#x_{Nk}}RIGHT)~-LEFT( pile{u_{1i}#u_{2i}#⋮#u_{N i}}RIGHT)right)^{T}BULLET left(pile{c_{i11}~~c_{i12}~~…~~c_{i1N}#c_{i21}~~c_{i22}~~…~~c_{i2N}#⋮~~⋮~~…~~~⋮#c_{iN1}~~c_{iN2}~~…~~c_{iNN}}right)^{-1}bullet LEFT ( LEFT( pile{x_{1k}#x_{2k}#⋮#x_{Nk}}RIGHT)~-LEFT( pile{u_{1i}#u_{2i}#⋮#u_{N i}}RIGHT)right)]

□ 군집 [eqn: i]에 대한 화소 1의 사전 확률 [eqn: P(X_{1}~|w_{i})~=]

[eqn: {{1}over{(2pi)^{N/2} LEFT |~{pile{c_{i11}~~c_{i12}~~…~~c_{i1N}#c_{i21}~~c_{i22}~~…~~c_{i2N}#⋮~~⋮~~…~~~⋮#c_{iN1}~~c_{iN2}~~…~~c_{iNN}} ~RIGHT | }^{1/2}}exp LEFT [ -{1}over{2} LEFT ( LEFT( pile{x_{1k}#x_{2k}#⋮#x_{Nk}}RIGHT)~-LEFT( pile{u_{1i}#u_{2i}#⋮#u_{N i}}RIGHT)right)^{T} left(pile{c_{i11}~~c_{i12}~~…~~c_{i1N}#c_{i21}~~c_{i22}~~…~~c_{i2N}#⋮~~⋮~~…~~~⋮#c_{iN1}~~c_{iN2}~~…~~c_{iNN}}right)^{-1} LEFT ( LEFT( pile{x_{1k}#x_{2k}#⋮#x_{Nk}}RIGHT)~-LEFT( pile{u_{1i}#u_{2i}#⋮#u_{N i}}RIGHT)right)RIGHT ]]

□사전확률에 의한 가중치의 적용

[eqn: D_{i}(X)~=~lnP(w_{i})-{1}over{2}~ln2pi~-{1}over{2}~ln|sumi|-{1}over{2}{(X-U_{i})}^{T}{sumi}^{-1}(X-U_{i})]

[eqn: P(w_{i})]는 k개의 군집 중 [eqn: i]군집으로 배정될 사전확률

[eqn: D_{i}(X)~=~ln LEFT | sumi RIGHT |+{(X-U_{i})}^{T}{sumi}^{-1}(X-U_{i})]

[eqn: =~ln LEFT | ` pile{{c _{i11} ~~c _{i12} ~~…~~c _{i1N}}#{c _{i21} ~~c _{i22} ~~…~~c _{i2N}}#{VDOTS ~~ VDOTS ~~…~~` VDOTS }#{c _{iN1} ~~c _{iN2} ~~…~~c _{iNN}}} ` RIGHT | + LEFT ( LEFT ( pile{{x _{1k}}#{x _{2k}}#{VDOTS }#{x _{Nk}}} RIGHT ) `- LEFT ( pile{{u _{1i}}#{u _{2i}}#{VDOTS }#{u _{Ni}}} RIGHT ) RIGHT ) ^{T} LEFT ( pile{{c _{i11} ~~c _{i12} ~~…~~c _{i1N}}#{c _{i21} ~~c _{i22} ~~…~~c _{i2N}}#{VDOTS ~~ VDOTS ~~…~~` VDOTS }#{c _{iN1} ~~c _{iN2} ~~…~~c _{iNN}}} RIGHT ) ^{-1} LEFT ( LEFT ( pile{{x _{1k}}#{x _{2k}}#{VDOTS }#{x _{Nk}}} RIGHT ) `- LEFT ( pile{{u _{1i}}#{u _{2i}}#{VDOTS }#{u _{Ni}}} RIGHT ) RIGHT )]

[eqn: X_1]에 대해 [eqn: P(X_{1}~|w_{i})]가 최대가 되는 군집으로 분류를 하던지 [eqn: D_{i}(X)]가 최소가 되는 군집으로 분류하면 된다.

2. 시스템 구현을 통한 실험 및 분석

[그림 2.5]	[그림 2.5]는 실험에 사용할 위성영상이다. Landsat TM 영상이며 가로 169픽셀, 세로 169픽셀, 밴드 7개를 가지고 있다. [그림 2.5]는 7개의 밴드 중 Red영역인 Band3, Green 영역인 Band2, Blue 영역인 Band1만으로 출력한 영상이고 원래의 영상으로는 식별이 힘들어 전처리로 평활화를 수행한 이미지이다. 분포가 특정부분으로 치우친 것을 전체영역으로 고르게 분포하도록 균일화 처리

[그림 2.6]

[그림 2.6]은 개발한 군집분류 시스템의 실행 모습이다. 시스템은 최소한의 기능만 구현되어 있으며 군집분류 후 ‘다른 이름으로 저장’을 하면 분류 결과를 텍스트 파일로 저장할 수 있다.

1) K-Means 군집분류의 수행결과

K-Means 군집분류 기법은 생성군집의 개수와 반복횟수를 입력변수로 받고, 위성영상데이터 전체 분포에서 임의의 값을 초기 군집 중심으로 선택하여 모든 화소를 군집에 분배한 후 군집중심을 갱신한다. 이와 같은 과정을 오차자승의 합이 최소이거나 입력받은 반복횟수 만큼 반복했다면 종료한다.

[그림 2.7]

[그림 2.7]은 중심 값을 계산 하는 법을 간략히 표현한 그림이다. 분포의 최대 값과 최소 값의 차를 (생성 군집의 수 / 2) 로 나누고 평균을 중심으로 최소 값 보다 크고 평균보다 작은 쪽을 (생성군집의 수 / 2)로 나눈 수만큼 Min에서 더해서 중심으로 선택하고, 평균보다 크고 최대값 보다 작은 쪽을 (생성군집의 수 / 2)로 나눈 수만큼 평균에서 더해서 중심으로 선택한다.

[그림 2.8]

1) 실험1)

[그림 2.8]은 입력변수들을 지정하는 창으로 반복횟수를 20회, 4개의 군집을 생성하고 1, 3, 5, 7밴드만으로 분류하라고 지정했다. 영상의 분류를 직접 확인 하기위해 각 군집에 대응되는 대응색도 지정되어 있다.

[그림 2.9]

[그림 2.9]는 [그림 2.8]과 같은 입력변수로 K-Means 군집분류 수행 후 원 영상과 대응색으로 표시된 이미지를 보여주고 있다. 다음은 분류 후 산출되는 결과 들이다.

===============================================================================

입력영상 정보

===============================================================================

Width : 169

Height : 169

밴드 수 : 7

픽셀 수 : 28561

<표 2.1>입력영상에 대한 각 밴드별 기초 통계량

	Mean	Variance	Stdev	Max	Min	Q1	Median	Q3	Mode
Band1	89	50.755	7.124	175	70	84	43	92	85
Band2	35	25.171	5.017	81	26	32	17	34	34
Band3	33	76.2	8.729	102	20	28	15	38	28
Band4	115	409.251	20.230	185	36	102	59	129	122
Band5	103	673.352	25.949	231	52	79	52	122	74
Band6	38	314.409	17.732	158	10	23	17	48	20
Band7	149	10.612	3.258	168	144	147	74	152	147

===============================================================================

무감독분류 K-Means 분류 결과

===============================================================================

최대 반복횟수 : 20회

실제 반복횟수 : 4회

군집 수 : 4

분류 대상 밴드 : Band1, Band3, Band5, Band7

- 분류결과 반복횟수를 20회로 입력했지만 오차자승의 합이 최소가 되는 4회까지만 반복을 하고 종료되었음을 알 수 있다.

<표 2.2> 초기 군집중심

	군집 1	군집 2	군집 3	군집 4
Band1	74.75	84.25	93.75	132.00
Band3	23.25	29.75	36.25	67.50
Band5	64.75	90.25	115.75	167.00
Band7	145.25	147.75	150.25	158.50

<표 2.3> 최종 군집중심

	군집 1	군집 2	군집 3	군집 4
Band1	84.55	88.45	89.48	101.80
Band3	28.09	32.75	34.38	50.08
Band5	75.58	95.96	119.66	147.13
Band7	147.64	149.84	150.23	154.22

<표 2.4> 최종 군집중심간 거리(유클리디언 거리)

	군집 1	군집 2	군집 3	군집 4
군집 1		21.374	49.698	91.725
군집 2	94.182		97.138	112.038
군집 3	120.687	123.008		127.672
군집 4	149.143	159.250	162.879

<표 2.5> 각 군집의 픽셀 수

군집 1	9714
군집 2	5422
군집 3	9666
군집 4	3759

[그림 2.10]

대상밴드로 선택했었던 3, 5밴드의 산점도이다. 왼쪽이 분류 전의 산점도 이고 오른쪽이 분류 후의 산점도 이다.

[그림 2.11]

1) 실험2) 1, 3, 5, 7밴드를 선택했던 앞의 실험과 다르게 2, 4, 6 밴드만으로 실험 하고자 한다.

[그림 2.12]

우선 결과 이미지만 봐도 밴드의 상관관계에 따라 완전히 다른 분류결과를 보이게 된다. 저장한 결과를 좀 더 살펴보기로 한다.

===============================================================================

무감독분류 K-Means 분류 결과

===============================================================================

최대 반복횟수 : 20회

실제 반복횟수 : 2회

군집 수 : 4

분류 대상 밴드 : Band2, Band4, Band6

- 분류 횟수부터 앞 실험의 4회보다 2회가 줄어든 2회에서 분류가 종료되었음을 알 수 있다.

<표 2.6> 최종 군집중심간 거리(유클리디언 거리)

	군집 1	군집 2	군집 3	군집 4
군집 1		31.955	69.112	75.428
군집 2	81.918		87.033	94.142
군집 3	112.330	116.112		130.509
군집 4	133.961	138.685	150.944

<표 2.7> 각 군집의 픽셀 수

군집 1	2160
군집 2	8670
군집 3	15299
군집 4	2432

[그림 2.13]

[그림 2.13]은 4, 6밴드의 산점도이다. 4, 6밴드의 산점도로는 굉장히 잘 분류가 된 듯하지만 3, 5밴드의 산점도 [그림 2.14]를 보면 군집의 대응색이 서로 섞여있는 것을 볼 수 있다. 앞의 실험과는 전혀 다른 결과이다.

[그림 2.14]

2) MLC(Maximum Likelihood Classifier) 수행결과

2) 실험1)

[그림 2.15]

위성영상에서 [그림 2.15]와 같이 훈련영역 aaa, bbb, ccc, ddd를 선택하고 군집분류를 수행한다.

[그림 2.16]

[그림 2.16]은 훈련영역 선택 시 통계치와 밴드별 히스토그램, 산점도 등 훈련영역에 대한 정보를 표시하고 중심을 설정하기 위한 창이다. 훈련영역을 위성영상에서 마우스로 드래그 하여 선택하면 [그림 2.16]에서처럼 Sampling 창에 정보들이 표시된다. 산점도의 붉은 점은 2) MLC(Maximum Likelihood Classifier)에서 설명했듯이 유클리디언 거리의 평균거리 내부의 픽셀에 대한 산점도이고 붉은색을 포함한 회색 산점도가 원래의 훈련영역에 대한 산점도다. 아래 [그림 2.12]는 선택된 훈련영역에서 모든 밴드를 분류대상으로 선택하고 최대우도비로 분류한 결과이다.

[그림 2.12]

===============================================================================감독분류 최대우도비분류(MLC) 결과

===============================================================================

군집 수 : 4

분류 대상 밴드 : Band1, Band2, Band3, Band4, Band5, Band6, Band7

<표 2.8> 초기 군집중심

	군집 1 (aaa)	군집 2 (bbb)	군집 3 (ccc)	군집 4 (ddd)
Band1	84.90	84.45	99.72	91.77
Band2	34.21	31.64	43.47	39.33
Band3	28.40	27.62	49.40	36.28
Band4	141.83	122.26	90.32	123.61
Band5	119.31	75.91	137.75	136.81
Band6	37.24	20.89	63.09	56.23
Band7	147.38	147.18	155.13	151.85

<표 2.9> 최종 군집중심간 거리(유클리디언 거리)

	군집 1 (aaa)	군집 2 (bbb)	군집 3 (ccc)	군집 4 (ddd)
군집 1 (aaa)		227.387	348.073	438.929
군집 2 (bbb)	509.218		573.370	632.659
군집 3 (ccc)	683.302	720.144		768.187
군집 4 (ddd)	810.405	841.701	881.992

<표 2.10> 각 군집의 픽셀 수

군집 1 : aaa	6197
군집 2 : bbb	11734
군집 3 : ccc	9649
군집 4 : ddd	981

<표 2.11> 분류결과 성능평가

분류항목	예측 소속집단				Total
	aaa	bbb	ccc	ddd
aaa	896	9	1	4	910
bbb	8	875	12	0	895
ccc	30	12	770	7	819
ddd	16	0	0	367	383
Total	950	896	783	378	3007

OVERALL CLASS PERFORMANCE( 2908 / 3007 ) = 96.71%

위의 분류 결과 성능평가는 훈련영역으로 선택된 픽셀들이 실제 군집분류 후에 얼마나 제대로 분류 되었는지 보여주는 표다. 선택한 훈련영역(aaa, bbb, ccc, ddd)의 총 픽셀 수가 3007개 이고 훈련영역 aaa는 950개 픽셀 중 896개의 픽셀만 정확히 aaa군집으로 분류되고 bbb군집에 8개, ccc군집에 30개, ddd군집에 16개의 픽셀이 분류 되었다. 훈련영역 bbb도 전체 896개의 픽셀중 875개의 픽셀이 bbb군집으로 분류되었고 aaa군집에 9개, ccc군집에 12개가 분류되었다. 훈련영역 ccc도 총 783개의 픽셀에서 770개 픽셀만이 ccc군집으로 분류 되었다. 훈련영역 ddd도 378개중 367개가 ddd군집으로 분류되었음을 알 수 있다. 따라서 전체 3007개의 픽셀 중 2908개의 픽셀이 예측소속 집단으로 제대로 분류되었으므로 96.71%가 옳게 분류 되었다.

2) 실험2)

[그림 2.13]

[그림 2.14]

[그림 2.15]

[그림 2.14]는 [그림 2.13]과 같이 훈련영역을 선택하고 실험1)과 마찬가지로 1~7밴드를 모두 분류대상 밴드로 선택하고 MLC를 수행한 결과이다. 실험1)의 결과인 [그림 2.15]와 비교해보면 크게 차이는 없지만 군집 대응색이 섞여있는 것을 볼 수 있다.

===============================================================================감독분류 최대우도비분류(MLC) 결과

===============================================================================

군집 수 : 4

분류 대상 밴드 : Band1, Band2, Band3, Band4, Band5, Band6, Band7

<표 2.12> 초기 군집중심

	군집 1 (abc)	군집 2 (def)	군집 3 (ghi)	군집 4 (jkl)
Band1	86.67	84.91	94.54	92.86
Band2	35.45	32.21	39.89	38.40
Band3	31.02	28.28	41.41	37.40
Band4	128.88	121.31	99.78	103.31
Band5	118.36	79.74	120.97	114.03
Band6	39.84	23.19	51.16	47.61
Band7	148.43	147.68	153.66	153.35

<표 2.13> 최종 군집중심간 거리(유클리디언 거리)

	군집 1 (abc)	군집 2 (def)	군집 3 (ghi)	군집 4 (jkl)
군집 1 (abc)		229.056	339.894	420.098
군집 2 (def)	490.357		550.918	603.710
군집 3 (ghi)	654.547	693.469		736.107
군집 4 (jkl)	778.345	811.350	849.323

<표 2.14> 각 군집의 픽셀 수

군집 1 : abc	7399
군집 2 : def	12441
군집 3 : ghi	3585
군집 4 : jkl	5136

<표 2.15> 분류결과 성능평가

분류항목	예측 소속군집				Total
	abc	def	ghi	jkl
abc	1704	350	156	82	2292
def	497	1822	647	326	3292
ghi	157	107	865	139	1268
jkl	192	220	611	693	1716
Total	2550	2499	2279	1240	8568

OVERALL CLASS PERFORMANCE( 5084 / 8568 ) = 59.34%

성능평가를 보면 실험1)과는 다르게 59.34%만 옳게 분류된 것을 볼 수 있다. 훈련영역이 다를 뿐 모든 조건이 동일한 가운데 이러한 결과를 낸다는 것은 결국 훈련영역이 분류 결과에 영향을 심하게 미침을 알 수 있다.

Ⅲ. 결 론

본 논문에서는 다양한 군집분류 기법 중 무감독분류의 K-Means군집분류 기법과 감독분류의 MLC(Maximum Likelihood Classifier)를 구현하고, Landsat위성의 영상에 적용한 실험을 통하여 두 군집분류 기법의 특성을 파악하고, 각 군집분류 기법의 입력변수의 변화에 의한 실행결과를 비교하였다. K-Means군집분류 기법은 군집중심의 값이 거의 변하지 않을 때까지 반복적으로 화소를 분석 하기 때문에 데이터의 특성을 알지 못하는 상태에서도 분류 결과에 어느 정도의 정확도를 기대할 수 있는 장점이 있는 반면 반복적이라는 요소 때문에 분류하는데 걸리는 시간이 길어지는 단점이 있다. 이는 실험에서 보듯이 같은 반복횟수, 같은 생성군집 수를 입력변수로 하더라도 어떤 변수(밴드)를 선택하느냐에 따라 분류횟수와 결과가 달라지기 때문에 수차례 반복실험을 해서 얻는 경험적인 밴드 선택이 필요하다. 최대우도비를 이용한 군집분류 기법은 우선 감독분류이므로 영상에 대한 사전지식을 통해 훈련영역을 지정할 수 있고 확률에 근거한 분류 기법이므로 무감독분류보다는 정확한 결과를 얻을 수 있다. K-Means군집분류기법과 같은 반복이 없으므로 수행속도 면에서도 빠르다고 할 수 있지만 실험1)과 실험2)의 분류 결과를 보면 훈련영역에 치명적인 영향을 받는 것으로 나타났다. 조사한 바에 의하면 영상을 K-Means등의 무감독분류기법으로 한번 군집분류를 하고 그 결과 이미지를 훈련영역으로 삼고 감독분류기법으로 다시 분류하는 등 정확도를 높이기 위한 방법들이 있다고 한다.

Ⅳ. 논문을 마감하며

우연히 영상처리라는 분야에 통계가 쓰인다는 사실에 호기심으로 시작한 개인적인 공부였지만, 4년 동안 배운 통계만으로는 단지 여론조사나 품질관리, 금융계통의 예측 등의 분야로만 국한시켜 생각한 나와 비슷한 생각을 가진 동기나 후배들이 있을법하여 통계가 응용되는 무궁무진한 여러 분야 중 하나일 뿐이지만 이러한 분야에도 통계가 쓰인다는 사실을 전해주고 싶은 생각에 이렇게 논문으로도 작성하게 되었다. 좀 더 일찍 접하고 좀 더 일찍 시작했더라면 더 많은 분류 기법의 구현과 안정적인 프로그램으로 구현했을 텐데 어느덧 제출 기한이 다되어 이쯤에서 논문은 마감해야하는 것이 아쉽지만 논문 제출 후에도 개인적으로는 좀 더 구현 해 볼 생각이다.

통계가 이러한 위성영상처리뿐만 아니라 동일한 분류 기법으로 해저 지형도를 작성한다거나 GIS, 지문인식, 얼굴인식, 과속단속카메라의 차량 번호판 식별, 컴퓨터의 프로세스 처리과정에서 성능향상을 위한 알고리즘 등 적용되고 있는 분야가 무궁무진 하다는 것을 알고 나서는 통계가 정말 재미있는 분야라는 것을 깨닫게 되었고 좀 더 열심히 공부하지 않은 것에 대한 늦은 후회가 든다.

Ⅴ. 참 고 문 헌

[1] 국토지리정보원, http://simc.ngii.go.kr, 2006/9/10 18:24

[2] 김용성 (2005). Visual C++ 완벽가이드 2nd Edition, 22-764, Youngjin.com

[3] 대한원격탐사학회, http://www.ksrs.or.kr/library/rsnote/contents.htm, 2006/10/28 18:24

[4] 박성현⋅조신섭⋅김성수(2004). 한글 SPSS Ver.SPSS 12k, 296-330, SPSS 아카데미

[5] 성웅현 (1997). 응용 다변량분석, ,탐진

[6] 안승철⋅이재원⋅최원(2005). 수리통계학의 이해, 309-313, 교우사

[7] 이문호 (2001). Visual C++ 실용 영상 신호처리, 7-103, 大英社

[8] 정성태 (2005). Visual C++을 이용한 실용 영상처리, 12-146, 생능출판사

[9] 차영준 (2002). 통계소프트웨어 개발, , 자유아카데미

Ⅵ. 부 록

1. 프로그램 사용법

[그림 6.1]

메뉴에서 “파일->열기“를 클릭하고 ”위성영상“ 폴더안의 ”tip.lan“파일을 불러온다.

[그림 6.2]

위성영상이 불려진 상태

[그림 6.3]

메뉴의 “보기->평활화“를 클릭

[그림 6.4]

메뉴의 “보기->밴드 합성”을 클릭

[그림 6.4]와 같이 RED에는 Band3, GREEN에는 Band2, BLUE에는 Band3을 선택하고 OK버튼을 클릭 (본인이 원하는 밴드대로 합성을해도 무방함)

1) K-Means 분류기법 실험

메뉴 “무감독분류->K-Means” 클릭

[그림 6.5]

Clustering 창에서 반복횟수와 군집 수를 입력하고 분류 대상 밴드를 선택

각 군집마다 대응색 열의 빈칸을 클릭하면 대응색 지정가능

(군집과 대응될 색을 선택한 후 확인버튼 클릭)

[그림 6.6]

모든 군집에 대응색을 지정했다면 OK버튼 클릭

결과이미지가 오른쪽 View에 나타나면 메뉴의 “파일->다른 이름으로 저장“ 클릭

[그림 6.7]

원하는 폴더와 파일명으로 저장

프로그램 종료

2) MLC분류 기법 실험

위성영상을 부르고 밴드 합성하는 과정까지는 K-Means와 동일함

메뉴의 “감독분류 -> 최대우도비 분류”클릭

[그림 6.8]

[그림 6.9]

[그림 6.10]

[그림 6.9]와 같이 원하는 훈련영역을 선택하고 [그림 6.10]의 군집 레이블을 입력

[그림 6.11]

군집 대응색의 ▼버튼을 클릭해서 대응색을 선택 후 “확인“버튼을 클릭하고 “추가“버튼 클릭

원하는 만큼의 훈련영역을 선택/추가 한 후 “최대우도비 분류” 버튼 클릭

분류 종료 K-Means와 같이 “파일->다름 이름으로 저장“으로 결과 저장

프로그램 종료

최적의 게임을 위한 게임AI프로그래밍( Settlers of Catan )

- 게임 AI 프로그래밍 -

- 구 본 철 -

구본철

대구대학교 전산통계학과 4년

요 약 문

컴퓨터의 발전과 함께 끊임없이 발전해나가는 그래픽, 효과와 다르게 발전이 정체하여 있는 게임AI에 대하여 분석하고, 그 과정에서 얻어진 아이디어를 실제로 구현하였으며, 그 구성과 알고리즘에 대한 내용을 논문의 주로 삼는다. 또한 결과적으로 그 AI를 이용하여 인하여 얻을 수 있는 효과에 대해서도 분석하였다.

Ⅰ.개발배경 및 필요성

게임에서의 인공지능. 그것은 30년의 짧은 역사를 가진 게임에 있어서, 더욱 더 인간적으로, 더욱 더 사실적으로 움직이는 적을, 또는 동료를 만들어내기 위하여 수없이 많은 시도가 행해졌다. 그리고 그에 따라 더 사실적인 그래픽, 사실에 가까운 묘사 등, 게임은 비약적인 발전을 이루어 현재에 이르렀다. 하지만 보이는 곳에서 적을 사실적으로 만들어주는 그래픽과는 달리 보이지 않는 곳에서 사실적으로 움직이는 적을 만들기 위해 필요한 인공지능. 그것은 얼마나 발전을 이루고 있을까? 그것을 알기 위해 여러 가지 조사를 해보았다.

그렇다면 과연 그 조사의 결과는 어찌 되었을까? 인공지능의 발전, 그것은 물리적인 시스템의 발전에 따라서 같이 상승하게 되는 그래픽과는 달리, 10년전이나 현재나, 아니, 20년전과도 크게 다르지 않았다. 현재에도 인공지능이란 단순히 for문을 반복하거나, 분기 문에 따라서 조건을 만족하면 단순히 정해진 행동을 하는, 말 그대로 인공지능이라고 할 수 없는 인공지능이 대부분이었다. 그 어느 곳을 찾아도, 단순한 길 찾기 알고리즘, 위치 찾기 알고리즘 등의 단순히 행동적으로 사실에 가까울 뿐, 인간에 가까운 ‘사고’라는 내용을 가진 Ai는 그 어느 곳에도 존재하지 않았다. 그렇다면 내가 사고를 가진 AI까지는 아니더라도, 그에 준하는, 인간의 사고와 같은 모양을 보여주는 그러한 AI를 만들 수 없을까? 라고 궁리한 결과, 인간의 행동과 더욱 가까운 AI를 고안해보기로 하였다.

Ⅱ.최종목표 및 사양

1. 최종목표

이 인공지능 연구의 최종목표는 위에서 말했듯이, 더욱 나은 알고리즘, 더욱 훌륭한 인공지능이 아닌, 게이머의 입장에서 느끼는 보다 인간적인 인공지능을 목표로 하였다. 그렇다면, 인간의 입장에서 느끼는 인간적인 인공지능이란 어떤 느낌일까? 그것은 바로, 감정을 가지고(또는 가진 듯 보이고) 자기의 행동에 맞춰 움직여주는, 능동적인 인공지능. 그것이 게이머가 바라는 인공지능이자, 이 연구에서 추구하는 목표이다.

게임 AI 프로그래밍

2. 사양

1) 하드웨어 사양

위 알고리즘의 구현은 AVD(안드로이드 버츄얼 디바이스)상에서 구현되었고, WVGA800의 480*800의 해상도 기준으로 제작되었으며, 그 WVGA 및 HVGA이외의 환경에서 정상적인 작동을 보장할 수 없다.

2) 소프트웨어 사양

위 알고리즘의 구현은 어플리케이션 Settlers of Catan 상에서 구현되었고, 위 어플리케이션은 Android SDK 2.1 상에서 구현되었다. 그렇기에 위의 어플리케이션의 구동에는 Android SDK 2.1이상의 업데이트를 필요로 한다. 또한 이 어플리케이션의 구동을 위한 ADV의 구동에는 1.6버전이상의 JAVA를 필요로 한다.

Ⅲ. 관련개발/연구동향

이 분야의 관련개발은 게임업계의 거장 피터 몰리뉴에 의해 진행되고 있다. 그의 연구 성과는 그의 게임 블랙 앤 화이트2에서 가장 강하게 드러났으며, 그 구현방식은 일반적인 게임에서의 인공지능구현과는 사뭇 다르다. 그가 구현한 인공지능은 언제나 능동적이다. 그것을 표현하기 위해 한가지 예를 들어보겠다. 어떠한 맵에 두 종류의 크리쳐가 있다. 그 둘은 각각 포만감, 따분함, 공포라는 스테이터스를 가지고 있다. 그를 통해 그들은 스크립트와는 달리, 자신의 현재 상태에 따라 현재의 행동을 결정짓는 것이다. 첫 번째 크리쳐인 피터는 놀이를 좋아하는 크리쳐이다. 그는 언제나 집안의 공을 가지고 놀고, 잠이 오면 잠들고, 배가 고프면 사냥을 하는 반복적인 행동을 반복하는 크리쳐이다. 두 번째 크리쳐인 몰리는 언제나 배고픈 크리쳐이다. 그는 끊임없이 사냥을 반복하고, 배를 채우기 위해 움직여나간다. 이 두 크리쳐는 서로가 만나기전까지는 끊임없이 자신의 정해진 행동을 반복해나가고 있었다. 그러다가 피터의 공이 몰리의 영역으로 가게 되었다. 놀기 좋아하는 피터는 당연히 공을 찾으러 몰리의 영역으로 이동하였으나, 배고픈 몰리는 피터를 공격하였다. 그러자 겁에 질린 피터는 자기가 좋아하는 공을 버려두고 도망가기 시작했다. 즉, 행동의 우선순위에 따라, 또한 자신의 현재 상태에 따라 행동하는 좀 더 능동적인 인공지능을 꾸며냈다고 할 수 있다. 실제 이 기능은 알고리즘적면에서 볼 때는 별 다를 것 없는 간단한 내용에 지나지 않을지도 모른다. 하지만 여러 가지 기능의 연쇄, 또한 그것을 통한 능동적인 상황에 대한 대처는 게임AI중의 새로운 축을 지탱하고 있다고 불리고 있다.

Ⅳ. 상세개발내용

1. 설계

위 프로그램의 구현은 일반적인 게임프로그래밍과 동일한 단일 쓰레드 위에서의 자바프로그래밍으로 구현되었다. 또한 외부 리소스를 모두 내부가 아닌, 외부 객체화를 통하여 언제든지 변경할 수 있는 형태로 하여, 재사용성을 향상시켰다. 또한 내부에 구현된 맵은 Node인터페이스를 상속받은 각각의 클래스를 구현하여, 코드의 간결성을 높였다.

2. 구현

1) 구성

실제 구현에 있어서는 대표적으로 다음과 같은 클래스를 가진다.

(1) Map클래스 -

실질적인 맵의 구성요소를 담고 있는 클래스이다. 이 클래스는 Node인터페이스를 상속받은 Road, Tile, Cell, EmptyCell 클래스를 각각 구현하여, 다형성을 이용한 구현으로 전체적으로 커맨드의 실행에 있어, for문을 이용한 일률적으로 행해지기 때문에 전체적인 코드의 간결성을 향상함과 동시에 제어의 편의성을 높였다.

(2) Character클래스

Character클래스는 각각의 AI플레이어의 행동지침을 결정한다. 각각의 AI플레이어는 탐색, 결정 등의 과정에 있어서 각각의 행동지침에 따라서 결정이 능동적으로 바뀌게 된다. 그 행동지침을 위하여, Character클래스는 무모함, 감정적 이라는 두 가지 행동지침을 지니게 되고, 이 행동지침에 따라서 이동 중 적과 조우했을 때의 대처법, 선택의 지침 등을 결정하게 된다.

(3) Search클래스

AI클래스는 각각의 AI플레이어의 성향을 입력받아, 그 AI와 현재 맵 상태를 고려하여, 링크드 리스트 형태의 행동지침을 생성한다. 행동된 생성지침은 모든 과정을 처리하는 Catan_Play클래스로 반환되며, 반환된 행동지침은 Catan_Play클래스의 내부 메소드 process에서 처리된다.

(4) Catan_Play클래스

Catan_Play클래스는 위의 외부 클래스를 참조하여, 각각의 상황에 필요한 처리를 행하며, 최종적으로 실제 유저가 눈으로 보는 대부분의 내용을 담당한다. 이에 따라서, 위의 클래스는 터치이벤트, 화면출력 등을 행하여, 유저가 게임을 진행하는 데에 어려움이 없도록 그에 관련된 모든 내용을 처리한다. 또한, 현재 AI플레이어의 턴일 경우에는, 생성된 행동지침을 process메소드 내부에서 처리한다.

2) AI

이 어플리케이션의 실질적인 구성은 Settlers of Catan이라는 게임의 구성을 재현하다기보다는, AI의 능동적 제어라는 내용을 기준으로 잡고 구성되었다. 그렇기에, 따로 AI의 구성을 설명하기 위해 그에 대한 부분을 따로 기술하기로 한다.

일단 이 설명을 위해서는 알아야할 부분은 바로 Settlers of Catan의 기본적인 진행방식이다. 일반적으로 알려진 보드게임은 맵이라 하면 많아야 3가지의 스테이터스를 가진다. 예를 들어 바둑이라면 빈칸, 흰 돌, 검은 돌과 같이 확연히 구분되는 한가지의 스테이터스 즉 보드상의 스테이터스의 유무 또는 종류를 판단할 뿐이다. 또한, 자신이 취할 수 있는 모든 수에 대한 이동비용이 동일하다. 즉, 일반적인 보드게임은 이동경로 대비 얻을 수 있는 자원의 양만이 경로의 결정의 기준이 될 뿐, 이동경로의 가치비용이 상대적으로 낮다. 그렇기에 A*알고리즘 등의 길 찾기 알고리즘으로 최적의 수를 찾을 수 있다. 하지만 Settlers of Catan은 형태는 보드게임의 형태를 지니고 있지만, 그 구성은 보드게임보다는, 오히려 PC상에서 즐기는 전략시뮬레이션과 닮아있다고 할 수 있다. 간단히 예를 들어 설명해보자. Settlers of Catan은 최초 시작 시 각각 2개의 Settler와 Road를 가지게 된다. 그리고 그 위치를 임의의 위치에 배정하는 동작이후 매 턴 주사위의 값과 일치하는 타일의 주변에 Settler가 존재할 때 자원을 얻을 수 있다. 또한 그 이동도 매우 한정적이다. 4개의 타일이 존재하는 나무와 3개의 타일이 존재하는 벽돌을 각각 1개씩 이용하여 도로를 짓고, 마찬가지로 나무, 벽돌, 양, 곡물을 1개씩 소비하여 마을을 지어나간다. 즉 이동에 소모되는 이동비용의 획득이 랜덤으로 이루어지고, 이동에 소모되는 비용이 매우 높다는 것이다.  그렇다면 이 게임 상에서 승리하는 방법은 무엇일까? 그것은 이동비용의 획득이 랜덤으로 이루어진다는 것을 생각해보면, 이동비용의 획득확률을 높이는 방법. 즉, 자원을 얻을 확률이 높은 Settler를 최대한 빨리 차지하는 것이다. 또한 자원에는 중요도라는 것이 있다. 사용률이 낮은 양을 얻을 확률을 아무리 높여도 상대적으로 승리에는 큰 영향을 미치지 않는 반면, 사용률이 매우 높은 철이나 곡식을 많이 얻게 되면 적은 자원으로도 상대적으로 빠른 승리를 얻을 수 있다. 즉 자신의 빌드에 따른 자원의 선택과 상대방보다 우수한 Settler를 선점하는 것이 플레이어를 승리로 이끄는 가장 중요한 요소인 것이다.

이해를 돕기 위해 예를 들어 설명해보겠다. 한국에서 많이 알려진 스타크래프트. 한국인이라면 많은 사람들이 알고 있을 전략 시뮬레이션이다. 이 게임의 승패를 좌우하는 요소는 자원의 획득과 컨트롤이라고 흔히들 알고 있다. 그렇다면 보드게임인 이 게임에선 이 요소가 배제된다. 그렇다면 남은 자원의 획득. 그것이 이 게임에서의 승리요건인 것이다. 그렇다면 이 승리조건을 달성하기 위해서 생성되는 확장기지. 확장기지의 생산 순위는 어떻게 결정되는가? 가까운 곳에서 최대한의 비용을 얻어낼 수 있는 곳(앞마당), 공격의 우선순위에서 제외되는 곳(섬), 위험을 감수하더라도, 최대한의 비용을 얻어낼 수 있는 곳. 이것이 일반적으로 생각되는 자원의 획득을 위한 확장기지의 조건일 것이다. 즉, 확장에 상대적으로 큰 비용을 소모하기에, 미래에 우수한 위치보다, 현재의 최적의 위치에 기지를 생산하여, 얻어진 많은 자원으로 또 한 번 확장을 해나가는, 방식을 택하고 있는 것이다. 상대적으로 이동에 많은 비용을 소모하는 방식 상에서, 가깝고 빠르게 자원을 얻을 수 있는 위치를 선점하여, 다음 확장까지의 상대적 소모비용을 줄여나가는 것이다. 이를 통해 안정적인 생산, 안정적인 확장을 통하여 최적의 상태를 유지해나갈 수 있는 것이다.

그리고 이를 Settlers of Catan에 동일하게 적용하여 보았다. 빌드에 따른 상대적 비용. 즉, 자신의 빌드에 소모되는 총 비용을 100으로 잡고, 그에 대한 상대적 비용을 낮춰감에 따라서, 자신에게 필요한 자원의 가치를 결정짓게 하는 것이다. 즉, 상대적비용에 따라, 가장 가까운 위치에서 최대한의 자원을 얻을 수 있는 위치를 결정하여 그 위치에 Settler를 건설함으로서 다음 이동에의 상대적비용을 점점 낮춰가는 것이다. 이를 통해 AI는 더 빠르게 더 많은 자원을 선점할 확률이 높아진다.

또한 현재 자신이 선택할 최적의 위치를 선택하는데에 위에서 명시한 Character클래스의 행동지침이 사용된다. 즉, 무모함이 높은 케릭터의 경우에는 적에 둘러 쌓여 있어 상대적으로 확장의 가능성이 낮은 지형일지라도 자원의 획득률이 높을 경우에는 전진해 나가지만, 반대로 낮은 케릭터의 경우는 그 곳으로 발을 향할 확률이 낮아져 가는 것이다. 이처럼 자원의 가치와 행동지침, 이 두 가지의 복합적인 요소로 다음의 수를 선택하게 되는 것이다.

이처럼 다중의 복합적 요소와 현재의 상태를 고려해 기존의 AI와는 다르게, 현재 취할 수 있는 최선의 행동을 행하는 것이 이 AI의 행동방식이다.

Ⅴ.	기능 및 성능평가

사실 이 AI의 성능은 기대 이하였다. 능력치에 따라 적은 이기지도 못할 위치로 돌진해오기도 하였고, 일정이상 게임에 대한 경험을 가지고 있는 게이머에게 있어서는 큰 메리트를 느끼지 못하는 그저 약하기만 한 AI에 지나지 않았다. 하지만 이와는 반대로 , 게임에 있어서 좀 더 새로운 경험을 제공하기도 하였다. 그저 최적의 수만을 찾아내는 일반의 AI와는 달리, 행동지침에 따라서 능동적으로 움직이는 AI는 늦지만, 어떤 상황에도 대처할 수 있었고, 또한 정해진 능력에 따라 자신만의 행동양식도 가지고 있었다.

Ⅵ.	활용방안 및 파급효과

위에서 얻은 AI는 발전형태에 따라 다양한 형태로 변형될 수 있다.  바로 이 AI의 기본은 바로 범용성인 것이다. 인간은, 아니 생물은, 자신의 현재 상태를 자각하고, 그에 따른 행동을 한다. 그것을 최적은 자신의 최적의 선택이 아닐지라도, 더욱 자연스러운 형태로 드러나는 것이다. 그것은 AI도 마찬가지라고 생각한다. 굳이 최적의 값을 얻을 필요는 없다. 실수를 하기에 그것이 더욱 자연스러운 것이고 생명체에 가까운 형태이기 때문이다. 즐거운 게임에는 강한 적도 필요로 하지만, 그 이상으로 약한 적도 필요로 한다. 그렇기에 최적의 값을 찾을 순 없지만, 언제나 자연스러운 선택을 할 수 있을 이 AI의 유용성이 대두되는 것이다. 그렇기에 이러한 형태의 AI를 통해, 지금까지와는 다른 양상으로 행동하는 인공지능 플레이어를 만들어낼 필요가 있는 것이다. 하지만 그러기 위해선, 인공지능에는 경험이란 요소를 필요로 한다. 인간도 처음엔, 누구나 실수하고, 누구나 잘못된 선택을 한다. 그렇지만 그 잘못된 선택을 메꾸어 나가는 것은 바로 AI이다. 그렇기에 향후, 경험이란 요소를 넣어서 자신의 행동지침을 변경해나가는, 학습해나가는 형태로의 발전도 기대할 수 있다.

Ⅶ.	개발추진체계 및 개발일정

이 어플리케이션의 개발은 단독으로 이루어졌으나, 東京電気大学, Chen교수님과의 많은 자문으로 이루어졌다. 개발기간은 2009년 10월에서 2010년 5월 사이에 이루어졌다.

Ⅷ.	결론 및 향후연구방향

현대의 게임은 끝없이 발전한다. 또한 디지털 스페이스의 주민들은 끝없이 그들이 소비해야할 컨텐츠를 원하고, 소비해 나가고 있으며, 만들어내고 있다. 그렇기에 그 소비를 선도해나가는 게임은 그들에게 끝없는 경험을 제공할 의무가 있다. 그 의무는 물리적 기술의 발전과 인간의 생활영역의 확장에 따라 물리적인 형태로 무한히 발전해나가고 있다. 하지만 실질적으로 AI부문에서는 그 경험의 폭을 막아둔 채 단지 겉모습만 발전해나가고 있다. 그렇기에 이러한 연구가 활발히 행해져서 보다 인간적인, 보다 자연스러운 형태의 AI을 만날 수 있을 날이 오기를 기대한다.

Ⅸ.	참고문헌

[1] 셰인 론더 - 로렌 다시 . 시작하세요! 안드로이드 프로그래밍 , 위키북스.

[2] 이재영 외 공역. 실용적 예제로 본 게임인공지능 프로그램하기 , (주)사이텍미디어.

[3] Alex J. Champandard. 인공지능 게임 프로그래밍 실전 가이드 , 에이콘출판(주).

Ⅹ.	부록

위의 프로그램은 실행에 AVD와 최신버전의 Java를 필요로 하므로, 실행환경의 구축에 어려움이 있을 경우를 대비하여 AI의 구성도, 실기 스크린 샷 일부의 소스코드를 첨부한다.

그림  - AI 구성도

그림  - 실기 스크린 샷 (오프닝)

그림  - 실기 스크린 샷 ( 플레이 화면 )

소스코드-

public class Catan_Play extends Activity {

@Override

public void onCreate(Bundle savedInstanceState) {

super.onCreate(savedInstanceState);

setContentView(new CatanView(this));

}

private class CatanView extends SurfaceView implements Runnable, Callback {

private SurfaceHolder holder;

private Thread gameLoop_;

private Context mContext;

private Node map[][];

Map tmpMap;

private Canvas canvas;

private Status bank_[];

private CharacterInfo character[];

private Random random_;

private int touchX_;

private int touchY_;

private int mode_;

private Command header_;

private int turn_[];

private Queue<Command> excuteCmd_;

public CatanView(Context context) {

super(context);

prov = new int[NUM_RES];

holder = getHolder();

holder.addCallback(this);

mContext = context;

setFocusable(true);

tmpMap = new Map();

map = tmpMap.map;

canvas = null

bank_ = new Status[NUM_PLAYER + 1];

character = new CharacterInfo[NUM_AI];

random_ = new Random();

excuteCmd_ = new LinkedList<Command>();

bank_ = new Status[NUM_PLAYER + 1];

}

public void surfaceChanged(SurfaceHolder holder, int format, intwidth,

int height) {

}

public void surfaceCreated(SurfaceHolder holder) {

setClickable(true);

gameLoop_ = new Thread(this);

gameLoop_.start();

}

public void surfaceDestroyed(SurfaceHolder holder) {

gameLoop_ = null

}

public void run() {

startGame();

while (gameLoop_ != null) {

drawCanvas();

try {

Thread.sleep(2000);

} catch (Exception e) {

}

if (!excuteCmd_.isEmpty()) {

//..

}

}

}

private void drawCanvas() {

canvas = null

try {

canvas = holder.lockCanvas(null);

//..

}

} catch (Exception e) {

} finally {

if (canvas != null) {

holder.unlockCanvasAndPost(canvas);

}

}

}

private void process(int player) {

//..

}

private void updateImportance(int player) {

//..

}

private void search(int player) {

//..

}

private int computeDepth(int player, int x, int y, String direct) {

int depth = 0

int tmp = 0

if (map[x][y].getType() == TYPE_ROAD)

//..

return depth + 1

} else {

return 0

}

else

return 0

}

private void startGame() {

//..

}

private void endGame() {

//..

}

private void startTurn() {

//..

}

private void endTurn() {

//..

}

private void throwDice() {

int tmp = 0

for (int i = 0 i < NUM_DICE; i++) {

tmp += (random_.nextInt(6) + 1);

}

Toast

.makeText(Catan_Play.this, "Dice - " + tmp,

Toast.LENGTH_SHORT).show();

updateResource(tmp);

}

private void updateResource(int dice) {

if (dice == 7) {

burst();

} else {

//..

}

}

private void burst() {

//..

}

private int getCellImportance(int player, int x, int y) {

int avr = 0

//..

return avr;

}

private int getCellImp2(int player, int x, int y) {

//..

return 0

}

private boolean canBuildRoad(int player, int x, int y) {

//..

return false

}

private boolean canBuildSettler(int player, int x, int y) {

//..

}

return false

}

private boolean canBuildCity(int player, int x, int y) {

//..

return true

}

private void buildSettler(int player, int x, int y) {

//..

bank_[getiFromPlayer(player)].vp += 1

map[x][y].build(player);

drawCanvas();

}

private void buildCity(int player, int x, int y) {

//..

map[x][y].build(player);

drawCanvas();

}

private void buildRoad(int player, int x, int y) {

//..

map[x][y].build(player);

drawCanvas();

}

private void commandDialog() {

new AlertDialog.Builder(super.getContext()).setTitle(

R.string.command_label).setItems(R.array.commandList,

new DialogInterface.OnClickListener() {

public void onClick(DialogInterface dialoginterface,

int i) {

switch (i) {

//...

}

}

}).show();

}

private void buildDialog() {

//..

}

private void useDialog() {

//..

}

private void tradeDialog() {

AlertDialog.Builder builder;

AlertDialog dialog;

LayoutInflater inflater = (LayoutInflater) mContext

.getSystemService(LAYOUT_INFLATER_SERVICE);

View layout = inflater.inflate(R.layout.trade_dialog,

(ViewGroup) findViewById(R.layout.main));

Spinner spin[] = new Spinner[10];

int res[] = new int[10];

ArrayAdapter aa[] = new ArrayAdapter[10];

//...

for (int i = 0 i < spin.length; i++) {

res[i] = 0

aa[i] = ArrayAdapter.createFromResource(super.getContext(),

R.array.ResNum, android.R.layout.simple_spinner_item);

aa[i]

.setDropDownViewResource(android.R.layout.simple_spinner_dropdown_item);

spin[i].setAdapter(aa[i]);

spin[i].setOnItemSelectedListener(new OnItemSelectedListener() {

@Override

public void onItemSelected(AdapterView parent, View view,

int position, long id) {

switch (position) {

//...

}

}

@Override

public void onNothingSelected(AdapterView arg0) {

//...

}

});

}

builder = new AlertDialog.Builder(mContext);

builder.setView(layout);

builder.setPositiveButton("Yes",

new DialogInterface.OnClickListener() {

public void onClick(DialogInterface dialoginterface,

int i) {

//...

}

}).setNegativeButton("No",

new DialogInterface.OnClickListener() {

public void onClick(DialogInterface dialoginterface,

int i) {

dialoginterface.cancel();

commandDialog();

}

});

dialog = builder.create();

dialog.show();

}

private void bankDialog() {

//..

}

private void endDialog() {

new AlertDialog.Builder(super.getContext()).setMessage(

R.string.end_label).setCancelable(false).setPositiveButton(

"Yes", new DialogInterface.OnClickListener() {

public void onClick(DialogInterface dialoginterface,

int i) {

//...

}

}).setNegativeButton("No",

new DialogInterface.OnClickListener() {

public void onClick(DialogInterface dialoginterface,

int i) {

dialoginterface.cancel();

commandDialog();

}

}).show();

}

@Override

public boolean onTouchEvent(MotionEvent event) {

touchX_ = (int) event.getX();

touchY_ = (int) event.getY();

if (event.getAction() == MotionEvent.ACTION_DOWN) {

if (mode_ == STATE_SETTLER) {

//...

mode_ = STATE_DEFAULT;

} else if (mode_ == STATE_CITY) {

//...

mode_ = STATE_DEFAULT;

} else if (mode_ == STATE_ROAD) {

//...

mode_ = STATE_DEFAULT;

} else if (mode_ == STATE_TILE) {

//...

mode_ = STATE_DEFAULT;

} else

commandDialog();

}

return super.onTouchEvent(event);

}

}

}