비전과 패턴인식 : Herbert Schildt

컴퓨터가 인간세계와 완전히 상호작용 (interface) 하려면, 분명히 어떤 종류의 비전 능력이 요구된다. 자동 로봇의 경우에 비전은 필수 불가결하다. 텔레비전 카메라의 신호를 디지털화 하는 과정이 비록 AI 의 일부는 아니지만, 그 신호를 해석하는 과정은 AI 의 일부이다. 이 장에서 보여줄 것처럼, 컴퓨터가 그런 신호들을 해석할 수 있는 방법이 여러 가지 있다.

컴퓨터에 비전 시스템이 연결되어 있지 않더라도 관계없다. 이 장에 있는 어떤 예를 위해서도 필요치 않을 것이다. 이 장은 텔레비전 신호를 실제로 잡는 것을 다루는 것이 아니라 여러 가지 패턴의 인식을 다루기 때문에, 예로써 디지털화된 신호를 시뮬레이트 할 것이다.

종종, 영상처리 (image processing) 라는 용어는 비전, 패턴인식, 영상강화 (image enhancement) 라는 꽤 넓은 분야를 뜻한다. 그 분야가 그렇게 큰 이유는 두가지 주요 부분을 망라하기 때문인데, 첫 번째 부분은 2 차원 처리이고 두 번째 부분은 흔히 실세계 처리로 불리우는 3 차원 처리이다. 여러 가지 물체를 인식할 C 프로그램을 개발하기 전에 몇가지 주요한 주제와, 영상처리와 패턴인식의 문제에 대한 개요를 알아야 한다.

1. 필터링, 대비, 명암 (FILTERING, CONTRAST, AND SHADING)

일반적으로 비전 시스템을 구현하는 데는 두가지 방법이 있다. 첫 번째 방법은 영상을 각 물체의 외형을 이루는 선에서 도출해 내려고 한다. 이 방법은 영상으로부터 정보를 제거하기 위해 여러 가지 필터와, 영상의 모든 부분을 검거나 희게 만들기 위하여 대비 강화기 (contrast enhancer) 를 사용한다. 이것은 회색 지역이 없기 때문에 - 영상의 모든 점이 검거나 희다 - 때때로 이진영상 (binary image) 이라고 부른다.

이진 영상의 실제 생성은 일반적으로 영상의 어떤 해석에도 관계치 않는 선행처리기 (preprocessor) 에 맡겨진다. 그러한 필터링이 비록 디지털형으로 행해질 수 있지만, 텔레비전 수상기에서 광도조절 (brightness control) 을 줄이는 동안 내내 대비 조절을 높일 때 보는 것과 유사한 고대비 (high-contrast) 영상을 생성하는 아날로그 회로를 사용하여 간단한 시스템으로 실행한다. 그러나, 이 장에서는 영상강화에 대해서는 설명하지 않을 것이다.

이진영상의 장점은, 매우 간단한 알고리즘을 사용하여 컴퓨터가 쉽게 인식할 수 있는, 엄밀히 정의된 경계를 제공하는 점이다. 다시 말해서, 각 물체가 어디서 시작하고 끝나는지 명확하다. 고대비 영상은, 단 몇 개의 선택된 물체들만 관찰될 것이라고 미리 알려진 조절된 환경에서 흔히 사용된다. 대부분, 이것은 이차원 영상처리 시스템이 사용하는 구현 유형이다.

비전 시스템을 구현하는 두 번째 방법은 컴퓨터에게 사람이 보는 것과 좀 더 비슷한 영상의 모습을 주려고 시도한다. 이 방법은 영상 일부의 광도 (brightness) 에 대한 정보를 컴퓨터에 준다. 이것은 컴퓨터로 하여금 고대비 영상에서 가능하지 않은 영상으로부터 두 가지 중요한 특징 - 표면(surface) 과 그림자(shadow) - 을 도출해 낼 수 있게 한다. 컴퓨터는 영상에 대한 3 차원 정보를 제공하기 위해서, 그리고 한 물체가 부분적으로 다른 물체를 가릴 때 충돌 (conflict) 를 해결하기 위해서 이런 것들을 사용한다. 이런 유형의 영상화 (imaging) 는 보통 3 차원 비전 시스템에서 사용한다.

(1) 컬러와 흑백 (Color Versus Black-and-White)

실제로 모든 비전 시스템은 두 가지 이유 때문에 컬러 대신 흑백 영상을 사용한다 : 첫째, 컬러는 일반적으로 필요하지 않고, 둘째, 컬러 정보를 첨가하는 것은 영상을 처리하고 있는 컴퓨터와 소프트웨어에 훨씬 더 큰 요구를 한다. 비전 기술의 현재 상태 (current) 와 기대 상태 (expect) 가 주어졌을 때, 이 상황은 쉽게 바뀔 것 같지 않다. 그러므로 이 장에서는 모든 영상이 흑백이라고 가정한다.

2. 2 차원 시스템 (TWO-DIMENSIONAL SYSTEMS)

2 차원 비전 시스템은 모든 영상이 편평한 것처럼 처리하기 때문에 엄밀히 조절되고 제한된 환경을 요구한다. 사실상, 2 차원 영상처리는 이 이유 때문에 때때로 편평한 영상 (flat image) 처리라고 부른다. 단 2 차원만이 표현되기 때문에, 고대비 이진 영상이 일반적으로 사용되는데, 이것은 물체의 외형만을 이끌어 낸다. 2 차원 시스템은 어떤 특정한 2 차원 모양의 방향 (orientation), 위치 (location) 또는 인식이 중요한 자동화된 작업 라인과 같은 환경에서 아주 흔히 쓰인다.

그림 1 2 차원 비전 제어 정렬 라인

관찰되는 실제 물체는 편평할 필요가 없고 보통 3 차원이라는 것을 명심해야 한다. 시스템의 유일한 요구사항은 3 차원 영상이 그 주체 (identity) 를 잃지 않고 2 차원 영상으로 변형 (reduce) 될 수 있다는 것이다. 예를들어, 단 네가지 유형의 블록들만 제조하는 장난감 공장을 상상해 보자 - 정사각형, 직사각형, 삼각형과 원기둥, 블록이 만들어 질 때, 자동 정렬 (automated sorting) 을 위한 컨베이어 벨트위에 놓여진다. 컨베이어 벨트위에 장치된 (mounted) 텔레비전 카메라는 각 블록의 2 차원적, 위에서 본 영상을 컴퓨터에 공급한다. 각 블록이 어떤 유형이고, 각 블록이 현재의 틀속에 어떤 순서로 놓여 있는지를 결정한다. 그림 1 이 이 상황을 설명한다.

각 블록이 지나감에 따라, 카메라는 블록의 3 차원 모습을 윗부분의 모양을 형성하는 2 차원으로 변형시킨다. 그림 2 는 컴퓨터가 보는 영상을 보여준다. 비록 한 차원 전체가 제거 되었지만, 컴퓨터는 각 블록을 올바로 인식하기 위해서 여전히 충분한 정보를 갖는다.

그림 2 컴퓨터가 본 블록

관찰된 물체는 엄격히 통제 (control) 되고 그들의 변형은 발생하지 않는다는 것이 간단한 2 차원 영상처리기의 성공에 기본이 됨을 명심해야 한다. 예를들어, 만약 블록 분류기 (sorter) 에 정사각형 바닥을 가진 피라밋을 넣었다면, 2 차원 영상은 정사각형으로 나타나고, 컴퓨터는 그것을 정사각형 블록의 통 속에 놓을 것이다. 그러한 피라밋을 인식하는 것이 필요해지면, 카메라의 위치를 바꾸거나 측면 관찰을 위해서 두 번째의 2 차원 시스템을 첨가해야 할 것이다.

2 차원 시스템이 갖는 공통된 문제점은 물체가 다른 물체에 의해 부분적으로 가려지거나 덮여져 있을 때 시스템은 그 물체를 인식하는 데에 어려움을 갖는다는 것이다. 유용한 3 차원 정보가 없기 때문에 카메라는 충돌되거나 잘못된 정보를 컴퓨터에 넣는다. 그러한 충돌을 올바로 해결하는 것이 항상 가능한 것은 아니다. 나중에 제시된 프로그램에서 보겠지만, 인식 루틴이 구현되는 방법은 컴퓨터가 어떤 유형의 상황을 다룰 수 있을지를 제어한다. 이 문제를 이해하기 위해서, 삼각 모양의 블록이 우연히도 정사각형 블록의 위에 놓였다고 생각해 보자. 컴퓨터는 다음 모양을 보게된다.

컴퓨터는 이 영상이 사각 모양을 형성하는, 서로 이웃하는 두 개의 삼각형으로 이루어진 것인지 또는 사각형의 위에 놓인 삼각형인지 구별할 수가 없다. 그러한 문제 때문에 3 차원 영상화를 사용하게 된다.

3. 3 차원 시스템 (THREE-DIMENSIONAL SYSTEMS)

기본적으로, 3 차원 비전 시스템은 다른 물체의 정면이나 윗부분에서 방해하는 물체들에 의해 생성되는 모든 관찰 문제를 다루려고 한다. 3 차원 시스템을 또한 컴퓨터 프로그램이 국가의 지구물리학적 지도를 생성하는 것을 돕는 일과 같은, 한 영상으로부터 지형학적 정보를 추출해 내려고 한다. 3 차원 영상처리는 프로그래머가 3 차원 비전 시스템을 구현할 수 있기 전에 극복되어야 할 실질적인 문제들이 있기 때문에 AI 기술의 최전선에 있다.

하나의 카메라를 갖는 비전 시스템이 3 차원 정보를 요구하는 많은 응용에 충분하다는 것을 알면 놀랄지도 모른다. 그 이유를 이해하기 위해서, 잠시 한 눈을 감고 둘러보라. 주위의 물체들을 여전히 쉽게 인식할 수 있다. 이 이유는 설명하기에는 간단하지만 컴퓨터에서 구현하기는 어렵다. 시력 (vision) 은 단순히 물체의 경계선보다 훨씬 더 많은 정보를 포함하기 때문에 여전히 한 눈만으로 볼 수 있다. 색, 명암 (shading), 광도 (brightness) 그리고 거리에 대한 정보를 갖는다. 두 눈을 사용한 시력의 손실을 보상하기 위해서 (최소한 부분적으로) 다른 정보에 의존할 수 있기 때문에 한 눈만으로 세계에 대한 3 차원 관점을 여전히 갖게 된다. 이 설명의 나머지 부분에서 단 하나의 카메라만 사용된다고 가정한다.

3 차원 시스템은 제한된 2 차원 방식에서 존재하지 않았던 여러 가지 문제를 극복해야 한다. 먼저, 컴퓨터가 처리하는 영상은 훨씬 더 많은 정보를 갖는다. 이것은 단순한 말처럼 들리지만, 잠시 그것에 대하여 생각해 보자 : 고대비 이진 영상에서, 컴퓨터는 각 픽셀 (pixel) 이 검은 색이거나 흰색이기 때문에 그것을 한 비트에 저장할 수 있다 (픽셀은 비디오 영상의 한 점이다). 그러나 3 차원 정보를 얻는 것은 각 픽셀의 상대적인 광도에 대한 정보를 요구한다. 여러 제약조건에 따라서, 몇 개의 강도에서 수백 개의 광도까지 있을 수 있다. 256 가지 회색의 명암이 있고 각 픽셀을 저장하기 위해 1 바이트를 요구한다고 가정하자. 이 숫자는 고대비 방법에 의해 요구되는 것보다 8 배 많다. 얼마나 많은 기억장소가 요구되는지 알기 위해, 다음을 생각해 보자 : 보통의 미국 텔레비전 카메라는 525 개의 스캔라인을 사용하고, 동일한 수평 해상도를 가정하면, 흑백 사진을 저장하는 데에 275,625 바이트가 필요할 것이다 (만약 컬러 영상을 저장하기 원한다면 요구된 기억장소의 양은 거의 두 배가 될 것이다 !). 대부분의 개인용 컴퓨터가 이만큼의 메모리를 쉽게 가질 수 있지만, 컴퓨터가 소화할 많은 정보를 표현하고, 고대비 모드에서의 영상과 반대되게 이런 형태로 영상을 분석하는 데에는 더 많은 시간이 걸릴수 있다. 실시간 응용에서, 이것은 문제가 될 수 있다.

더 중요한 문제는 영상이 갖는 모든 정보를 컴퓨터로 하여금 사용하게 하려고 할 때 발생한다. 본능적으로 또는 아주 어린 나이에 배워서 볼 수 있기 때문에, 어떻게 보는지에 대하여 많은 생각을 하지 않는다. 결국 눈은 텔레비전 카메라와 크게 다르지 않다. 그러므로, 두뇌는 매일 보는 모든 영상을 해석하기 위하여 많은 양의 처리를 해야 한다. 사람이 영상을 처리하는 방법을 컴퓨터에 복사하는 것이 AI 의 일이다. 실세계의 영상을 해석하는 어려움을 이해하기 위하여 다음의 여러 문제와 그 해결 방안을 공부하자.

(1) 표면 방향 찾기 (Detecting Surface Direction)

인공위성이 찍은 로키 산맥 사진을 그림 3 에 주어진 스케치와 비슷하다. 이 사진을 분석하기 위하여 컴퓨터를 사용한다면, 컴퓨터가 산을 보고 있고 계곡은 보고 있지 않다는 것을 어떻게 컴퓨터가 아는가? 다시 말해서, 사진은 산맥에 관한 것이지, 그랜드 캐년과 같은 골짜기에 관한 것이 아니라는 것을 컴퓨터는 어떻게 결정할 수 있을까? 산맥의 영상을 올바로 해석하기 위해, 컴퓨터는 영상에서 표면의 방향을 알아야 한다.

그림 3 인공위성에서 본 로키 산맥

그림 4 산과 계곡에서의 빛의 반사

표면이 빛을 반사하는 방법을 공부함으로써 그 방향을 결정할 수 있다. 그림 4 는 산과 계곡의 측면을 보여주고 각각은 태양이 바로 위에 있다. 그림에서 보여주듯이, 산의 측면을 비추는 빛은 측면으로 반사된다. 반면에 계곡을 비추는 빛은 먼저 반대편 벽에 반사되고 그리고 나서 하늘로 다시 반사된다. 영상을 분석하는 프로그램은 컴퓨터가 산을 보고 있는지 계곡을 보고 있는지 결정하기 위해서 표면의 상대적 밝기 (brightness) 를 사용할 수 있다. 이 분석은 간단한 영상에서 조차도 매우 복잡한 일이고, 복잡한 영상에서는 거의 압도적이다.

(2) 표면의 결 결정 (Determining Surface Texture)

비록 속임을 당할 수는 있지만, 일반적으로 어떤 물체를 보아서 부드러운지 거친지를 결정할 수 있다. 예를들어, 털이 있는 공은 부드러워 보이고 유리대리석은 딱딱해 보인다. 먼 거리에서도 더욱이, 매우 광택있는 금속과 유리는 천연목재와 달라 보인다. 그러므로, 외양을 보고 물체의 결을 결정할 수 있다.

부드러운 물체를 거친 물체와 구별하는 열쇠는 다시, 각각이 빛을 반사하는 방법을 해석하는데에 있다. 그림 5 가 보여주는 것처럼, 딱딱한 물체의 특성인 부드러운 표면은 그것을 비추는 빛을 균일한 방법으로 반사한다. 그러나, 부드러운 물체의 특징인 거친 표면은 빛을 흩뜨린다. 그러므로, 부드러운 결의 물체의 상대적 밝기는 딱딱한 결의 물체보다 더 작다.

그림 5 부드러운 면과 딱딱한 표면에서의 반사

통제된 환경에서, 컴퓨터는 표면이 부드러운지 거친지 결정하기 위해서 단순히 각 물체의 상대적인 밝기를 사용할 수 있다. 이런 유형의 영상처리는, 용접과 페인트 같은 특징이 균일한지 체크되는 자동차 조립 라인에서 흔히 사용한다.

그러나, 컴퓨터로 하여금 실세계 상황에서 결이 거친 물체와 결이 부드러운 물체를 구별할 수 있게 하는 것은 단순히 물체의 상대적인 밝기를 비교하는 것보다 더 많은 것을 요구한다. 이유는 물체의 상대적 밝기를 색과, 그 물체를 만드는데 사용된 재료의 반사 질에 의해서도 영향 받기 때문이다. 그러므로 결을 결정하는 것은 빛의 근원에 관하여 다른 관점에서의 물체에 대한 둘 이상의 영상을 요구한다. 그림 6 을 공부해보자 : 점 A 에서 관찰할 때, 딱딱한 결의 물체는 관찰자에게 비추는 거의 모든 빛을 직접 반사하기 때문에 밝아보인다. 부드러운 결의 물체는 빛의 일부만 관찰자에게 반사한다. 그러나, 점 B 에서 보면, 딱딱한 결의 물체는 아주 적은 양의 빛만 반사하고, 반면 부드러운 결의 물체는 거의 같은 양의 빛을 반사한다. 그러므로, 컴퓨터는 밝기의 변화를 비교함으로써 결을 구별할 수 있다. 큰 변화는 부드러운 결을 나타내고 작은 변화는 거친 결을 나타낸다.

그림 6 관점 A 와 B 에서 본 부드러운 물체와 딱딱한 물체

4. 공통된 인식 문제 (COMMON RECOGNITION PROBLEMS)

2 차원이나 3 차원 시스템을 사용하여, 영상을 올바로 해석하는 모든 문제를 해결할 수 있다고 가정하면 영상을 구성하는 물체나 특징들을 올바로 알아내는 문제가 여전히 남아있다. 이 문제는 다음 설명에 나올 것 처럼 해결하기가 아마 더 어려울 것이다.

(1) 겹치는 물체 (Overlapping Objects)

비전 시스템을 만들려고 할 때 봉착하는 가장 힘든 문제 중의 하나는 겹치는 물체의 인식이다. 문제는 한 물체가 다른 물체의 앞에 있다는 것을 컴퓨터가 구별할 수 없다는 것이 아니다 : 일반적으로 그림자와 명암의 차이가 충분한 실마리를 제공한다. 실제로 어려운 점은 부분적인 물체가 무엇인지에 대해서 그것을 인식하도록 컴퓨터를 프로그램하는 것이다. 예를들어, 컴퓨터에게 삼각형은 세 변과 세 정점을 갖는다고 알리면, 그리고 컴퓨터가 다른 물체에 의해 흐려진 (또는 아마도 카메라의 시계밖에 있는) 정점을 하나 갖는 삼각형을 보면, 컴퓨터는 비록 세 번째 정점이 없지만 여전히 삼각형을 보고 있다는 것을 어떻게 알겠는가?

이 문제에 대한 많은 접근 방법이 있다. 그러나 아마 가장 재미있는 해결 - 그리고 사람의 눈이 하는 것과 가장 가까운 방법 - 은 통제된 환각 (controlled hallucination) 이다. 이 방법에서 초기 정보에 의해 지시받은 컴퓨터는, 삼각형이며, 두 선이 가려진 부분 어딘가에서 교차할 것이라는 것을 계산하는 것과 같은 어떤 방법에 의해 이를 확인하려하고 있다는 것을 주장한다. 생각할 수 있듯이, 이것은 아주 통제된 환경을 제외한 모든 환경에서 다루기 힘든 과정이다.

(2) 분류에 의한 물체인식 (Recognition of Objects by Classification)

또다른 어려운 문제는 물체들의 분류 - 나무는 나무다, 집은 집이다 - 을 인식하도록 컴퓨터를 프로그램하는 것이다. 컴퓨터로 하여금 어떤 분류에 있는 물체들을 인식하게 하기보다는 특정 물체를 인식하게 하는 것이 훨씬 더 쉽다. 이 이유는, 특정 물체에는, 따라야 할 엄밀한 제한을 줄 수 있지만, 약간의 변형을 모두 다루기 위하여 분류 정의 (class definition) 를 아주 일반적이고 느슨하게 유지해야 하기 때문이다.

이 글을 쓰는 현재 이 문제가 일반적인 경우에 대하여 어떻게 해결될 것인가는 분명하지 않다. 나중에, 패턴인식을 수행하는 어떤 프로그램을 이 장에서 개발함에 따라 컴퓨터는 분류 정의에 바탕을 둔 간단한 기하학적 모양을 결정할 수 있지만, 이런 유형의 물체에 적용될 수 있는 기법들은 아주 복잡한 물체로 변형되지 않는다는 것을 알게 될 것이다.

(3) 눈의 착각 (Optical Illusions)

눈의 착각과, 컴퓨터화된 비전 시스템에서의 영향에 대한 짧은 언급없이 영상처리에 대한 개관은 완성될 수 없다. 이상하게도, 인간을 속이는 많은 눈의 착각은 같은 형상의 컴퓨터 분석에 영향을 주지 않는다. 예들들어, 그림 6 의 A 와 B 는 정확히 같은 길이이지만, A 가 더 길어보인다. 그러나 컴퓨터는 같은 실수를 하지 않는다.

그림 7 간단한 눈의 착각 예

그러나, 반대 상황이 일어날 수 있다 : 컴퓨터는 인간이 해석하는 영상으로 혼동을 일으킬 수 있다. 예를들어, 길고 곧은 길을 내려다 볼 때, 좁아보이고 마침내 "소멸점 (vanishing point)" 에서 사라지는 것처럼 보인다 : 즉, 물체는 더 멀리 있을수록 더 작아 보인다. 이 효과에 익숙해 있고 그것에 대하여 거의 생각하지 않는다. 그러나 덜 완벽한 비전 시스템에서, 컴퓨터는 멀리있는 물체는 단순히 작다고 생각하기 쉽다.

그러므로, 인간에게 존재하는 것과 다른 종류의 착시가 컴퓨터에 존재한다는 것을 알아야 한다. 더우기, 당연히 여기는 많은 특징들이 컴퓨터가 영상을 올바로 해석할 수 있기전에 명확히 프로그램되어야 한다.

이제 지능적인 비전 시스템과 관련된 주요 주제와 문제들의 개관을 완성했으므로, 이런 몇몇 문제에 부딪치기 위하여 C 를 사용할 수 있는 방법을 공부할 준비가 되어있다.

5. 2 차원 패턴인식 (TWO-DIMENSIONAL PATTERN RECOGNITION)

3 차원 영상과, 그것을 인식하는 데에 필요한 기법들의 복잡성 때문에, 그것들은 이 책의 범위를 넘어선다. 그러므로, 패턴인식에 대한 이 설명은 2 차원 영상으로 제한한다. 방금 주어진 개관에서 지적했듯이, 영상처리를 요구하는 대부분의 실용적인 문제들을 고대비, 편평한 영상을 사용하여 해결할 수 있다. 예에서 사용될 것이 바로 이런 유형의 영상이다 (여기서 설명된 몇가지 기법들을 3 차원 패턴인식의 더 복잡한 분야에도 적용할 수 있다).

컴퓨터가 물체를 인식할 수 있는 많은 방법이 있다. 어떤 방법은 특정한 물체들에 대해서만 작동하는 반면 다른 방법은 일반적인 경우에 대해서 작동할 수 있다. 그러므로, 한가지 방법이 다른 것보다 나은지 결정하는 객관적인 기준을 만드는 것은 어렵다. 그러나 다음 문제들에 대한 답은 특정한 인식 기법을 어떤 상황에 적용할 수 있고, 그 제한은 무엇인지 알도록 돕는다.

1. 인식 기법은 다른 물체의 위에 놓인 물체들을 옳게 결정하는가?
2. 물체의 방향이 인식에 영향을 주는가?
3. 물체의 정확한 크기가 인식에 영향을 주는가?
4. 그 기법이 얼마나 효율적인가?
5. 그 기법은 혼동되거나 실수를 하지 않는가?

이러한 질문을 배경으로, 세 개의 서로 다른 패턴인식 방법 개발에 대하여 볼 준비가 되어있다.

(1) 상황 (The Situation)

삼각형과 사각형을 옳게 인식할 패턴인식 루틴을 디자인해야 한다고 생각해보자. 처음에, 단 한가지 유형의 삼각형 - 2 등변 삼각형 - 만 있을 것이다. 나중에 직각 삼각형을 추가할 것이다. 항상 한가지 유형의 사각형만 있다. 이 일은 너무 간단해 보이지만, 곧 알게 되겠지만, 패턴인식 루틴을 만드는 데에는 많은 어려움이 있다.

(2) 비디오 영상 시뮬레이트 (Simulation a Video Image)

이 장의 처음에서 언급했듯이, 컴퓨터에는 아마 비전 시스템이 부착되어 있지 않기 때문에, 그리고 여러 가지 비전 하드웨어가 다르게 작동하기 때문에, 시각 영상을 시뮬레이트할 것이다. 컴퓨터의 스크린 디스플레이 정보를 가지고 있는 메모리를 사용하여 이를 할 수 있다. IBM PC 와 호환 기종은 메모리 맵 비디오를 사용한다.

이 방법에서, 스크린의 각 문자 위치는 RAM 의 예약 위치에서 한 바이트에 대응한다. 이 메모리 영역에 무엇이 있건 스크린에 디스플레이 된다. 반대 상황이 또한 발생할 수 있다 : 스크린에 디스플레이 되는 것은 메모리에도 있다. 비전 영상을 시뮬레이트 하기 위해, 먼저 스크린을 클리어하고 그리고 나서 간단한 물체의 외형을 디스플레이 한다. 이것은 고대비인 편평한 영상을 표현한다. 그리고 나서 각 프로그램의 인식 부분은 비디오 메모리를 스캔하고, 물체들을 알아내려고 시도한다. 알 수 있듯이, 프로그램의 인식부분을 스크린에 무엇이 놓였는지에 대한 직접적인 지식을 갖지 않는다.

모든 C 컴파일러가 그래픽 라이브러리를 갖는 것은 아니므로, 비디오 영상은 텍스트 모드에서 시뮬레이트 하기로 한다. 이것은 영상을 구성하는 24 x 80 개의 픽셀이 있을 것이라는 것을 의미한다. 컴퓨터는 별표 (asterisks) 와 빈칸을 사용하여 스크린에 각 물체를 그릴 것이다. 픽셀이 별표를 포함하면, 컴퓨터는 온 (on) 상태에 있다고 가정한다 : 픽셀이 빈 칸을 포함하면, 컴퓨터는 오프 (off) 상태에 있다고 가정한다. 이 기법은 고대비 흑백 영상을 만든다. 프로그램은 현재 위치의 문자를 리턴하는 BIOS 인터럽트 10H, 기능번호 8 을 이용하여 영상을 스캔할 수 있다. 텍스트 모드 사용으로, 그래픽 기능을 갖지 않은 사용자는 뒤에 제시된 패턴인식 프로그램을 사용할 수 있다.

이 프로그램들을 검토하기 전에, 필요로 하는 세 개의 지원할 수가 있다. 마이크로소프트 C 버전 4.0 과 같은 어떤 C 컴파일러는 커서 (cursor) 주소 지정, 스크린 클리어, 여러 가지 BIOS 호출을 위한 라이브러리 루틴을 제공하지 않기 때문에, 이 함수들을 구현할 필요가 있다. 이 함수들을 직접 지원하지 않는 컴파일러을 사용하는 독자들을 위하여, 그것들을 다음에 준비했다 : 함수들은 마이크로소프트 C 버전 4 컴파일러의 int86() 이라는 포괄적인 인터럽트 루틴을 사용한다.

/* checks to see if the point is an '*' by using BOIS int 10h, #8 */

check_point(a, b)

int a, b;

{

union REGS regs;

gotoxy(a, b);

regs.h.ah=8;

regs.h.bh=0;

int86(16, &regs, &regs);

if (regs.h.al=='*') return 1;

return 0;

}

/* put cursor at x, y */

gotoxy(x, y)

int x, y;

{

union REGS regs;

regs.h.ah=2;

regs.h.dh=y;

regs.h.dl=x;

regs.h.bh=0;

int86(16, &regs, &regs);

}

/* clear the screen */

cls()

{

union REGS resg;

regs.h.ah=6;

regs.h.al=0;

regs.h.ch=0;

regs.h.cl=0;

regs.h.dh=24;

regs.h.dl=79;

regs.h.bh=7;

int68(16, &regs, &regs);

}

다음 루틴은 검은 스크린에, 주어진 x, y 좌표에 삼각형과 사각형을 그린다.

/* draw a triangle at x, y */

make_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<5 ; t++) {

gotoxy(x-t, y+t);

printf("*");

}

for(t=0; t<5; t++) {

gotoxy(x+t, y+t);

printf("*");

}

gotoxy(x-5, y+5);

printf("*****************");

}

/* draw a square at x, y */

make_square(x, y)

int x, y;

{

int t;

for (t=0; t<5; t++) {

gotoxy(x, y+t);

printf("*");

}

for (t=0; t<5; t++) {

gotoxy(x+10, y+t);

printf("*");

}

gotoxy(x, y);

printf("****************")

gotoxy(x, y+5);

printf("****************");

}

이 장에서 개발된 모든 패턴인식 프로그램들은 온 상태의 픽셀들을 찾기 위하여 영상을 봐야한다. 프로그램은 물체가 스크린의 어디에 있는지 모르기 때문에, 별표를 포함하는 픽셀들을 찾아내기 위하여, 다음에 있는 find_point() 함수를 사용한다.

/* returns the cursor loc of an '*' with the search beginning with startx and starty */

find_point(startx, starty, x, y)

int startx, starty, *x, *y;

{

int a, b;

a=startx; b=starty;

do {

if (check_point(a, b) {

*x=a;

*y=b;

returns 1;

}

a++;

} while (a<79);

a=0;

b++;

} while (b<24);

return 0;

}

find_point() 함수가 호출될 때마다, 좌표 startx, starty 에서 시작하여, 왼쪽에서 오른쪽 그리고 위에서 아래로 진행하면서 별표를 찾기 시작한다. 별표를 발견하면 그 위치를 x 와 y 에 리턴한다. 이제 비디오 영상을 시뮬레이트 하고 각 픽셀을 엑세스하는 방법이 있으므로 패턴인식으로 진행할 준비가 되었다.

(3) 각에 의한 인식 프로그램 (The Recognition-by-Angle Program)

매우 통제된 환경에서, 정점의 각을 측정함으로써 삼각형이나 사각형을 옳게 알아내는 것이 가능하다. 삼각형의 유형을 이등변으로 제한하는 것은 삼각형을 사각형과 구별하는 것을 간단하게 한다 : 어떤 정점에서도 두 점만 체크하면 된다. 점들이 직각이면, 그 물체는 사각형임에 틀림없다. 점들이 60 도 각도에 있으면 그 물체는 삼각형임에 틀림없다.

각도에 의한 인식을 구현하는 가장 쉬운 방법중의 하나는, 옳은 위치에 있는지 알기 위하여 정점에 이웃한 점들을 체크하는 것이다. 예를들어, 어떤 삼각형의 정점에도, 대각선에 이웃하는 별표가 있을 것이다. 사각형을 발견하기 위해서는, 프로그램이 별표를 찾을 때마다, 그것의 직각에 또 다른 별표가 있는지 알기 위하여 체크한다는 것만 제외하고는, 삼각형을 발견하기 위하여 사용한 것과 같은 과정을 따른다.

다음에 있는 istriangle() 과 issquare() 함수는, 스크린 위치가 주어졌을 때 각각 삼각형과 사각형을 테스트한다.

/* check for a triangle */

istriangle(x, y)

int x, y;

{

if (check_point(x+1, y+1) && check_point(x-1, y+1))

return 1;

return 0;

}

/* check for a square */

issquare(x, y)

int x, y;

{

if (check_point(x+1, y) && check_point(x, y+1))

return 1;

return 0;

}

주된 함수 recognize() 는 issquare() 와 istriangle() 을 다룬다.

/* search for a triangle and a square */

recognize()

{

int x, y;

x=y=0;

while (find_point(x, y, &x, &y)) {

if (istriangle(x, y)) {

gotoxy(0, 0);

printf("triangle at %d %d", x, y);

break;

}

x++;

}

x=y=0;

while (find_point(x, y, &x, &y)) {

if (issquare(x, y) {

gotoxy(0, 1);

printf("square at %d %d", x, y);

break;

}

x++;

}

삼각형을 발견하기 위해, 프로그램은 find_point 가 별표의 위치를 리턴할 때마다 istriangle() 을 호출한다. 프로그램이 삼각형을 발견하면, 루프는 끝난다 ; 만약 프로그램이 삼각형을 발견하지 못하면, 다른 위치를 시도한다. 결국, 삼각형은 발견된다.

각에 의한 인식 프로그램 전체가 다음에 있다. 이제 그것을 컴퓨터에 넣어야 한다.

#include "dos.h"

/* Recognition-by-Angles */

main()

{

position();

recognize();

getche();

}

/* read the positions for the objects */

position()

{

int x, y, a, b;

do {

printf("x y position of isosceles triangle : ");

scanf("%d%d", &x, &y);

} while (outrange(x, y));

do {

printf("＼nx y position of square : ");

scanf("%d%d", &a, &b);

} while (outrange(a, b));

cls();

make_triangle(x, y);

make_square(a, b);

}

/* return true if out-of-range coordinates */

outrange(x, y)

int x, y;

{

if (x<0 || x>79) return 1;

if (y<0 || y>24) return 1;

return 0;

}

/* draw a triangle at x, y */

make_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<5 ; t++) {

gotoxy(x-t, y+t);

printf("*");

}

for(t=0; t<5; t++) {

gotoxy(x+t, y+t);

printf("*");

}

gotoxy(x-5, y+5);

printf("*****************");

}

/* draw a square at x, y */

make_square(x, y)

int x, y;

{

int t;

for (t=0; t<5; t++) {

gotoxy(x, y+t);

printf("*");

}

for (t=0; t<5; t++) {

gotoxy(x+10, y+t);

printf("*");

}

gotoxy(x, y);

printf("****************")

gotoxy(x, y+5);

printf("****************");

}

/* search for a triangle and a square */

recognize()

{

int x, y;

x=y=0;

while (find_point(x, y, &x, &y)) {

if (istriangle(x, y)) {

gotoxy(0, 0);

printf("triangle at %d %d", x, y);

break;

}

x++;

}

x=y=0;

while (find_point(x, y, &x, &y)) {

if (issquare(x, y) {

gotoxy(0, 1);

printf("square at %d %d", x, y);

break;

}

x++;

}

/* check for a triangle */

istriangle(x, y)

int x, y;

{

if (check_point(x+1, y+1) && check_point(x-1, y+1))

return 1;

return 0;

}

/* check for a square */

issquare(x, y)

int x, y;

{

if (check_point(x+1, y) && check_point(x, y+1))

return 1;

return 0;

}

/* returns the cursor loc of an '*' with the search beginning with startx and starty */

find_point(startx, starty, x, y)

int startx, starty, *x, *y;

{

int a, b;

a=startx; b=starty;

do {

if (check_point(a, b) {

*x=a;

*y=b;

returns 1;

}

a++;

} while (a<79);

a=0;

b++;

} while (b<24);

return 0;

}

/* checks to see if the point is an '*' by using BOIS int 10h, #8 */

check_point(a, b)

int a, b;

{

union REGS regs;

gotoxy(a, b);

regs.h.ah=8;

regs.h.bh=0;

int86(16, &regs, &regs);

if (regs.h.al=='*') return 1;

return 0;

}

/* put cursor at x, y */

gotoxy(x, y)

int x, y;

{

union REGS regs;

regs.h.ah=2;

regs.h.dh=y;

regs.h.dl=x;

regs.h.bh=0;

int86(16, &regs, &regs);

}

/* clear the screen */

cls()

{

union REGS resg;

regs.h.ah=6;

regs.h.al=0;

regs.h.ch=0;

regs.h.cl=0;

regs.h.dh=24;

regs.h.dl=79;

regs.h.bh=7;

int68(16, &regs, &regs);

}

<각에 의한 인식 프로그램 분석 (Analysis of the Recognition-by-Angles Program) >

프로그램을 실행시키고 삼각형을 위해서는 좌표 10, 10 을, 그리고 사각형을 위해서는 55, 12 를 넣어보자. 그러면 그림 8 에 있는 것과 비슷한 디스플레이를 보게 될 것이다. 그림이 보여주듯이, 인식 루틴은 삼각형과 사각형을 올바로 알아냈다.

그림 8 각에 의한 인식 프로그램의 디스플레이

프로그램의 성능을 분석하기 위해서 앞에 주어진 질문을 사용해야 한다. 이 접근방식은 다른 물체 위에 놓여진 물체를 옳게 인식하는가 알아내기 위해, 프로그램을 다시 실행시키고 두 물체의 좌표로 10, 10 을 넣어본다. 디스플레이는 그림 9 에 있는 것과 비슷할 것이다. 루틴은 다시 삼각형과 사각형을 옳게 발견했다.

그림 9 삼각형과 사각형이 겹치게 한 디스플레이

방향이 인식에 영향을 주는가? 불행히도, 프로그램이 구현되는 방법은 물체들이 몇 개의 위치 중 한 군데에 있을 것을 요구한다 - 물체들은 임의의 위치에 있을 수 없다. 그러나 주어진 예에서, 회전 가능성이 없으므로, 이 요구사항은 의미있는 제한이 아니고, 루틴을 여러 변형된 문제에 적용될 수 없게 한다. 그러나, 물체가 회전되게 하는, 각에 의한 인식 프로그램의 버전을 설계하는 것은 가능하다.

물체의 정확한 크기가 인식에 영향을 주는가? 대답은 "아니다" 이다. 왜냐하면 루틴이 하는 모든 것이 두 변 사이의 교차각을 확인하는 것이기 때문이다. 따라서 각에 의한 인식을 크기가 다른 물체에 적용할 수 있다.

프로그램은 얼마나 효율적인가? 단순성과 방향 제한 때문에 프로그램은 매우 효율적이다.

프로그램은 혼동될 수 있는가? 방금 주어진 예의 제한 내에서, 프로그램은 실수하지 않을 것이다. 그러나 만약 다른 유형의 모양이 허용되면, 프로그램은 실수를 할 수 있다. 예를들어, 프로그램이 첫 위치로서 직각삼각형의 빗변 반대 위치의 정점을 테스트하도록 삼각형의 방향이 되어 있으면 프로그램은 직각 삼각형을 사각형으로 잘못 알기가 쉽다.

이 분석에서 보여주듯이 각에 의한 인식이 프로그램을, 변형된 물체의 수가 최소인 아주 통제된 상황에만 적용할 수 있다.

(4) 주요 점들에 의한 인식 프로그램 (The Recognition-by-key-Points Program)

직각 삼각형은 각에 의한 프로그램을 혼동시킬 수 있기 때문에, 이 절에서는 방금 테스트된 이등변 삼각형과 사각형에 직각 삼각형을 추가하고, 이 세 물체 모두를 알아내는 프로그램을 만든다 (이 프로그램의 완전한 리스팅에 주어진 부가적인 디스플레이 코드를 발견할 것이다).

그림 10 삼각형과 사각형의 주요 점

프로그램이 항상 같은 크기를 갖는 물체를 알아내는 한가지 방법은 몇가지 주요 점들만 조사하는 것이다. 주요 점들은 단 한가지 물체만 조건을 만족하는 그런 방법으로 선택된다. 그림 10 은 프로그램이 알아내야 하는 세 물체와 주요 점들을 보여준다.

두 개의 다른 삼각형 - 다른 주요점을 갖는 - 이 있기 때문에 가장 쉬운 해결은 각 유형을 인식하기 위하여 개별 루틴을 만드는 것이다. 그러므로, 사각형을 발견하기 위하여 issquare() 를 사용하는 것 외에, isright() 함수는 직각삼각형을 발견하고 istriangle() 은 이등변삼각형을 발견한다. istriangle() 과 issquare() 의 새 버전과 새 함수 isright() 가 다음에 있다.

/* check for an isosceles triangle by key points */

istriangle(x, y)

int x, y;

{

if (check_point(x+5, Y+5))

return 1;

return 0;

}

/* check for a right triangle by key points */

isright(x, y)

int x, y;

{

if (check_point(x+9, y) && check_point(x, y+9))

return 1;

return 0;

}

/* check for a square by key points */

issquare(x, y)

int x, y;

{

if (check_point(x+10, y) && check_point(x, y+5) && !check_point(x, y+6) return 1;

return 0;

}

주요 점들에 의한 인식 프로그램 전체가 다음에 있다.

#include "dos.h"

/* Recognition-by-key-points */

main()

{

position();

recognze();

getche();

}

/* read the positions for the objects */

position()

{

int x, y, a, b, i, j;

do {

printf("x y position of isosceles triangle : ");

scanf("%d%d", &x, &y);

} while (outrange(x, y));

do {

printf("x y position of right triangle : ");

scanf("%d%d", &i, &j);

} while (outrange(x, y));

do {

printf("＼nx y position of square : ");

scanf("%d%d", &a, &b);

} while (outrange(a, b));

cls();

make_triangle(x, y);

make_square(a, b);

make_right_triangle(i, j);

}

/* return true if out-of-range coordinates */

outrange(x, y)

int x, y;

{

if (x<0 || x>79) return 1;

if (y<0 || y>24) return 1;

return 0;

}

/* draw an isosceles triangle at x, y */

make_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<5 ; t++) {

gotoxy(x-t, y+t);

printf("*");

}

for(t=0; t<5; t++) {

gotoxy(x+t, y+t);

printf("*");

}

gotoxy(x-5, y+5);

printf("*****************");

}

/* draw a right triangle at x, y */

make_right_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<10 ; t++) {

gotoxy(x, y+t);

printf("*");

}

for(t=0; t<9; t++) {

gotoxy(x-t+9, y+t);

printf("*");

}

gotoxy(x, y);

printf("*****************");

}

/* draw a square at x, y */

make_square(x, y)

int x, y;

{

int t;

for (t=0; t<5; t++) {

gotoxy(x, y+t);

printf("*");

}

for (t=0; t<5; t++) {

gotoxy(x+10, y+t);

printf("*");

}

gotoxy(x, y);

printf("****************")

gotoxy(x, y+5);

printf("****************");

}

/* search for a triangle and a square */

recognize()

{

int x, y;

x=y=0;

while (find_point(x, y, &x, &y)) {

if (istriangle(x, y)) {

gotoxy(0, 0);

printf("isosceles triangle at %d %d", x, y);

break;

}

x++;

}

x=y=0;

while (find_point(x, y, &x, &y)) {

if (isright(x, y)) {

gotoxy(40, 0);

printf("right triangle at %d %d", x, y);

break;

}

x++;

}

x=y=0;

while (find_point(x, y, &x, &y)) {

if (issquare(x, y) {

gotoxy(0, 1);

printf("square at %d %d", x, y);

break;

}

x++;

}

/* check for an isosceles triangle by key points */

istriangle(x, y)

int x, y;

{

if (check_point(x+5, Y+5))

return 1;

return 0;

}

/* check for a right triangle by key points */

isright(x, y)

int x, y;

{

if (check_point(x+9, y) && check_point(x, y+9))

return 1;

return 0;

}

/* check for a square by key points */

issquare(x, y)

int x, y;

{

if (check_point(x+10, y) && check_point(x, y+5) && !check_point(x, y+6) return 1;

return 0;

}

/* returns the cursor loc of an '*' with the search beginning with startx and starty */

find_point(startx, starty, x, y)

int startx, starty, *x, *y;

{

int a, b;

a=startx; b=starty;

do {

if (check_point(a, b) {

*x=a;

*y=b;

returns 1;

}

a++;

} while (a<79);

a=0;

b++;

} while (b<24);

return 0;

}

/* checks to see if the point is an '*' */

check_point(a, b)

int a, b;

{

union REGS regs;

gotoxy(a, b);

regs.h.ah=8;

regs.h.bh=0;

int86(16, &regs, &regs);

if (regs.h.al=='*') return 1;

return 0;

}

/* put cursor at x, y */

gotoxy(x, y)

int x, y;

{

union REGS regs;

regs.h.ah=2;

regs.h.dh=y;

regs.h.dl=x;

regs.h.bh=0;

int86(16, &regs, &regs);

}

/* clear the screen */

cls()

{

union REGS resg;

regs.h.ah=6;

regs.h.al=0;

regs.h.ch=0;

regs.h.cl=0;

regs.h.dh=24;

regs.h.dl=79;

regs.h.bh=7;

int68(16, &regs, &regs);

}

<주요 점들에 의한 인식 프로그램 분석>

프로그램을 실행시키고 다음 좌표를 넣어보자.

이등변삼각형 10, 4

직각삼각형 55, 11

사각형 30, 12

그림 11 과 유사한 디스플레이를 볼 것이다. 분명히, 인식의 주요점 방식은 이 제한된 상황에서 작동한다.

그림 11 점에 의한 인식 프로그램에 의한 디스플레이

프로그램의 제한을 이해하기 위해, 다섯가지 기준 질문에 대답해야 한다. 프로그램은 다른 물체 위에 놓인 물체를 올바로 해결하는가? 알아내기 위해, 모든 물체를 10, 10 에 놓고 프로그램을 실행시켜 보라. 대답은 '아니다' 이다 : 그림 12 에 있는 것처럼, 프로그램은 이제 단 하나의 사각형과 하나의 삼각형만 있다고 생각한다.

그림 12 10, 10 에서의 세 물체 디스플레이

물체의 방향이 인식에 영향을 주는가? 그림 12 는 프로그램은 여전히 모든 물체를 발견하지만 사각형이 10, 10 이 아닌 10, 14 위치에 있다고 생각한다. 이 결과는 인식기법을 혼란시키는 겹치는 물체 때문이다.

물체의 정확한 크기가 인식에 영향을 주는가? 대답은 '그렇다' 이다. 각 물체는 주요점들에 의한 인식 프로그램에 대하여 정확히 같은 크기여야 하는데 주요점들은 고정된 거리에 있기 때문이다.

프로그램은 얼마나 효율적인가? 물체의 정체 (identity) 를 결정하기 위해서 단 몇 개의 점만 조사하기 때문에, 아주 효율적이다. 거의 각에 의한 인식 프로그램만큼 효율적이다.

프로그램은 쉽게 혼동되는가? 프로그램을 실험해보면 세 개의 삼각형이 있다고 생각하게 할 수 있다는 것을 알게 될 것이다. 삼각형과 사각형의 위치를, 프로그램에 삼각형을 형성하도록 나타나는 고립된 점이 있는 그런 방식으로 배열하면 이런 일이 생길 수 있다.

더 다양한 삼각형을 인식할 수 있는 것과는 별개로, 이 프로그램에서 얻은 것보다 잃은 것이 더 많았던 것같다. 각에 의한 인식 프로그램보다 훨씬 더 제한적인 환경을 요구하고 혼동되기 쉽다.

(5) 델타-D 인식기 (The Delta-D Recognizer)

이 장에서 개발할 마지막 인식 방법은 방향의 변화에 기초를 둔다. 예를들어, 삼각형의 어떤 점에서 시작하든, 시작점으로 돌아갈 때까지 선들을 쫒아가면 방향을 세 번 바꾸게 될 것이다. 만약 사각형의 선들을 따라가면 방향을 네 번 바꿀 것이다. 방향이 바뀌는 횟수는 모양의 정점의 수와 같다 (원은 적분에서 처럼, 무한 번의 방향 변화를 갖거나 변화를 갖지 않는 것으로 생각된다). 정점을 만날 때마다, 방향 변화가 있다. 이 변화는 수학과 컴퓨터과학 에서 종종 델타값이라고 부른다. 여기 제시된 프로그램은 방향 변화에 기초하기 때문에 이 방법은 때로 델타-D 인식기라고 부른다. 여기서 D 는 방향 (direction) 을 의미한다.

델타-D 인식기가 작동하기 위해서는 물체의 모양을 따라가야 한다. 앞에 주어진 예에서, 프로그램은 다른 선과 교차할 때까지 직선을 따라갈 수 있어야 한다. 교차점에서, 프로그램은 다음 직선을 정확히 찾아서 그것을 따라가야 한다. 이것은 어려운 프로그래밍 문제가 아니지만, 그 해결은 쓸데없는 백트랙킹의 문제 때문에 직관적이지 않다. 델타-D 인식기를 구현할 방법이 많지만, 여기에 주어진 해는 두 가지 목적을 위하여 방문한 모든 점을 유지하는 oldp 라고하는 데이터베이스의 사용을 요구한다 : 먼저 루틴들은 시작점에 언제 되돌아가는지 알 수 있는 것이 필요하다 - 이것은 프로그램이 물체의 전체 외형을 따라갔다는 것을 나타내준다. 두 번째, 루틴이 자신의 꼬리를 따라가지 않게 해야 한다. oldp 데이터베이스의 정의와 위치를 저장하는데 필요한 assert_oldp() 함수, 그리고 위치가 데이터베이스에 있는지를 결정하는데 필요한 find() 함수가 다음에 있다.

#define MAX 200

struct oldpoints {

int x, y;

} oldp[MAX];

int pos=0; /* indexes into oldp database */

assert_oldp(x, y)

int x, y;

{

if (pos==MAX) {

printf("point database full ＼n");

return;

}

if (find(x, y)) return; /* already in db */

oldp[pos].x=x;

oldp[pos].y=y;

pos++;

}

find(x, y)

int x, y;

{

register int t;

for (t=0; t<pos; t++)

if (oldp[t].x==x && oldp[t].y==y) return 1;

return 0;

}

델타-D 인식기 작동의 핵심이 되는 follow() 와 find_direction() 함수가 아래에 있다.

/* follow a shape and return number of turns */

follow(x, y)

int x, y;

{

int incx, incy, startx, starty, count;

startx=x; starty=y;

count=0;

assert_oldp(x, y);

if (!find_direction(x, y, &incx, &inxy)) return 0;

do {

while (check_point(x+incx, y+incy)) {

x=incx+x;

y=incy+y;

assert_oldp(x, y);

}

if (x==startx && y=starty) return count;

count++;

if (!find_direction(x, y, &incx, incy)) return 0;

} while(1);

}

/* find a new line to follow */

find_direction(x, y, incx, incy)

int x, y, *incx, *incy;

{

register int a, b;

for (a=-1; a<2; a++)

for (b=-1; b<2; b++)

if (check_point(x, a, y+b) && !find(x+a, y+b)) {

*incx=a;

*incy=b;

return 1;

}

return 0;

}

시작점이 주어져 있을 때, follow() 함수는 증가치 incx 와 incy 의 값을 결정하기 위해서 find_direction() 을 호출하고, 그 값들이 정의하는 선을 따라 간다. 다음 위치에서, 차례를 알려주는 별표가 없으면 새로운 증가치를 결정하기 위하여 follow() 는 다시 find_direction() 을 호출한다 ; follow() 는, 다음으로 count 를 증가시킨다. 프로그램이 다시 원점 (the point of origin) 을 만날 때 과정은 결론을 내린다.

함수 find_direction() 은 다른 별표를 찾기 위하여 이웃 위치를 모두 시도함으로써 작동한다. find() 루틴은 점이 이미 oldp 데이터베이스에 있으면 참을 리턴하고 아니면 거짓을 리턴한다.그러므로, 이미 방문한 점들로는 받아들일 만한 선택이 이루어지지 않는다. 이 단계는 루틴으로 하여금 온 길을 되돌아 가지 못하게 한다.

다시 작성된 istriangle() 과 issquare() 함수가 다음에 있다. 주요점들에 의한 인식 프로그램과는 달리, 델타-D 인식기는 모든 삼각형이 세 변을 갖기 때문에 삼각형을 발견하기 위하여 하나의 루틴만을 필요로 한다는 것을 주목해야 한다 - 정확한 크기와 위치는 중요하지 않다.

/* check for an triangle by key points */

istriangle(x, y)

int x, y;

{

if (follow(x, y)==2) return 1;

return 0;

}

/* check for a square by key points */

issquare(x, y)

int x, y;

{

if (follow(x, y)==3) return 1;

return 0;

}

물체가 삼각형이면 방향이 두 번 바뀔 것이다. (istriangle() 의 이 버전은 원래 방향을 변화로 생각하지 않기 때문에 세 번이 아니다). 그러므로 만약 follow() 가 2 를 리턴하면, 이것은 삼각형을 발견했음을 나타낸다. 비슷하게, follow() 가 3 을 리턴하면, 이것은 사각형을 인식했음을 알려준다.

델타-D 프로그램 전체가 다음에 있다. 이제 컴퓨터에 넣어야 할 때다.

#include "dos.h"

#define MAX 200

struct oldpoints {

int x, y;

} oldp[MAX];

int pos=0; /* indexes into oldp database */

/* delta-D Recognizer */

main()

{

clear_db(); /* init the point database */

position();

recognze();

getche();

}

/* read the positions for the objects */

position()

{

int x, y, a, b, i, j;

do {

printf("x y position of isosceles triangle : ");

scanf("%d%d", &x, &y);

} while (outrange(x, y));

do {

printf("x y position of right triangle : ");

scanf("%d%d", &i, &j);

} while (outrange(x, y));

do {

printf("x y position of square : ");

scanf("%d%d", &a, &b);

} while (outrange(a, b));

cls();

make_triangle(x, y);

make_square(a, b);

make_right_triangle(i, j);

}

/* return true if out-of-range coordinates */

outrange(x, y)

int x, y;

{

if (x<0 || x>79) return 1;

if (y<0 || y>24) return 1;

return 0;

}

/* draw an isosceles triangle at x, y */

make_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<5 ; t++) {

gotoxy(x-t, y+t);

printf("*");

}

for(t=0; t<5; t++) {

gotoxy(x+t, y+t);

printf("*");

}

gotoxy(x-5, y+5);

printf("*****************");

}

/* draw a right triangle at x, y */

make_right_triangle(x, y)

int x, y;

{

int t;

for (t=0; t<10 ; t++) {

gotoxy(x, y+t);

printf("*");

}

for(t=0; t<9; t++) {

gotoxy(x-t+9, y+t);

printf("*");

}

gotoxy(x, y);

printf("*****************");

}

/* draw a square at x, y */

make_square(x, y)

int x, y;

{

int t;

for (t=0; t<5; t++) {

gotoxy(x, y+t);

printf("*");

}

for (t=0; t<5; t++) {

gotoxy(x+10, y+t);

printf("*");

}

gotoxy(x, y);

printf("****************")

gotoxy(x, y+5);

printf("****************");

}

/* search for a triangle and a square */

recognize()

{

int x, y, t;

t=0;

x=y=0;

while (find_point(x, y, &x, &y)) {

if (istriangle(x, y)) {

gotoxy(t*40, 0); t++;

printf("triangle at %d %d", x, y);

}

x++;

}

clear_db();

x=y=0;

while (find_point(x, y, &x, &y)) {

if (issquare(x, y)) {

gotoxy(0, 1);

printf("square at %d %d", x, y);

break;

}

x++;

}

/* check for an triangle by key points */

istriangle(x, y)

int x, y;

{

if (follow(x, y)==2) return 1;

return 0;

}

/* check for a square by key points */

issquare(x, y)

int x, y;

{

if (follow(x, y)==3) return 1;

return 0;

}

/* follow a shape and return number of turns */

follow(x, y)

int x, y;

{

int incx, incy, startx, starty, count;

startx=x; starty=y;

count=0;

assert_oldp(x, y);

if (!find_direction(x, y, &incx, &incy)) return 0;

do {

while (check_point(x+incx, y+incy)) {

x=incx+x;

y=incy+y;

assert_oldp(x, y);

}

if (x==startx && y=starty) return count;

count++;

if (!find_direction(x, y, &incx, &incy)) return 0;

} while(1);

}

/* find a new line to follow */

find_direction(x, y, incx, incy)

int x, y, *incx, *incy;

{

register int a, b;

for (a=-1; a<2; a++)

for (b=-1; b<2; b++)

if (check_point(x+a, y+b) && !find(x+a, y+b)) {

*incx=a;

*incy=b;

return 1;

}

return 0;

}

assert_oldp(x, y)

int x, y;

{

if (pos==MAX) {

printf("point database full ＼n");

return;

}

if (find(x, y)) return; /* already in db */

oldp[pos].x=x;

oldp[pos].y=y;

pos++;

}

find(x, y)

int x, y;

{

register int t;

for (t=0; t<pos; t++) {

if (oldp[t].x==x && oldp[t].y==y) return 1;

}

return 0;

}

/* returns the cursor loc of an '*' with the search beginning with startx and starty */

find_point(startx, starty, x, y)

int startx, starty, *x, *y;

{

int a, b;

a=startx; b=starty;

do {

if (check_point(a, b) {

*x=a;

*y=b;

returns 1;

}

a++;

} while (a<79);

a=0;

b++;

} while (b<24);

return 0;

}

/* checks to see if the point is an '*' */

check_point(a, b)

int a, b;

{

union REGS regs;

gotoxy(a, b);

regs.h.ah=8;

regs.h.bh=0;

int86(16, &regs, &regs);

if (regs.h.al=='*') return 1;

return 0;

}

/* put cursor at x, y */

gotoxy(x, y)

int x, y;

{

union REGS regs;

regs.h.ah=2;

regs.h.dh=y;

regs.h.dl=x;

regs.h.bh=0;

int86(16, &regs, &regs);

}

/* clear the screen */

cls()

{

union REGS resg;

regs.h.ah=6;

regs.h.al=0;

regs.h.ch=0;

regs.h.cl=0;

regs.h.dh=24;

regs.h.dl=79;

regs.h.bh=7;

int68(16, &regs, &regs);

}

clear_db()

{

register int t;

for (t=0; t<MAX; t++) oldp[t].x=oldp[t].y=0;

}

<델타-D 인식기 분석>

프로그램을 실행시키고 다음 좌표들을 넣어보자.

이등변 삼각형 10.4

직각 삼각형 55.11

사각형 30.12

그림 13 에 있는 것과 비슷한 디스플레이를 보게 될 것이다. 분명히, 델타-D 인식 방법은 예의 제한된 상황에 대하여 작동한다.

그림 13 델타-D 프로그램의 디스플레이

프로그램의 취약성을 이해하기 위해서, 다섯가지 기준 질문에 답해야 한다. 프로그램은 다른 물체 위에 놓인 물체를 올바로 인식하는가? 이 질문은 델타-D 인식기의 최악의 특징을 지적해 낸다 ; 한 물체가 다른 물체 위에 있을 때 완전히 실패한다. 이를 보기위해, 모든 물체를 10,10 에 놓고 프로그램을 다시 실행시켜 보자. 결과가 그림 14 에 있다 ; 프로그램은 어떤 삼각형도 발견해 내지 못하고, 사각형을 알아내는 것은 단지 우연에 불과하다. 너무 많은 방향 변화 때문에, 많은 선들을 따라가는 결과가 되어, 삼각형들을 구별할 수 없다.

그림 14 10, 10 에서의 세 물체 디스플레이

물체의 방향이 인식기에 영향을 주는가? 프로그램의 가장 훌륭한 특징 중의 하나는 물체가 어느 위치에 있건 상관없이 옳게 작동할 것이라는 것이다. 이 특징은 델타-D 인식기를 많은 실세계 상황에서 매력적이게 한다.

물체의 정확한 크기가 인식에 영향을 주는가? 델타-D 방식의 다른 좋은 점은 물체가 어떤 크기이건 상관하지 않는다는 것이다. 이것은 일단의 물체들을 인식하기 위하여 그것을 사용할 수 있다는 것을 의미한다.

프로그램은 얼마나 효율적인가? 델타-D 인식기는 앞에 주어진 두 프로그램보다 훨씬 더 일반적이기 때문에 그것들만큼 효율적으로 작동하지 않는다. 그러나 신뢰성을 위한 효율의 트레이드 오프 (trade-off) 는 일반적으로 가치가 있다.

프로그램은 쉽게 혼동되는가? 구현된 것처럼, 델타-D 인식기는 겹치는 물체에 의해 쉽게 혼동될 수 있지만, 특별한 상황의 제한 내에서 한가지 유형의 물체를 다른 것으로 잘못 알지는 않을 것이다.

최종 분석에서, 델타-D 방법은 적용되는 환경이 아주 통제되는 한 이 장에 제시된 세가지 프로그램들 중 가장 큰 일반성을 제공한다.

6. 일반화된 시스템 (GENERALIZED SYSTEMS)

이 장에 제시된 설명과 예가 보여 주었듯이, 영상을 해석하는 어떤 방법도 모든 상황에 적절하지는 않을 것이다. 영리한 (smart) 프로그램에 의해 선택적으로 적용되는 많은 서로 다른 방법을 결합하여 마침내 공통된 실세계 상황에서 사용될 수 있는 시스템이 나올 것이다.