Visual  Image Understanding

인공지능 개론 : Dan W. Patterson 저서, 김영렬.김우성.김정W규.박용법.정목동 옮김, 지성출판사, 1995  (원서 : Introduction to Artificial Intelligence and Expert Systems, 1990), Page 357~399

1. 서론

1) 시각처리 개요

2) 컴퓨터 비젼 시스템 (Computer Vision System) 의 목적

2. 화상변환과 낮은 단계 (low-level) 처리

1) 빛 에너지 (light energy) 의 숫자로의 변환

2) 양자화된 배열 (Quantized Arrays) 의 처리

3) 텍스쳐 (texture) 와 색상 (color)

3. 중간 단계 (intermediate level) 화상처리

1) 그래픽적 에지 탐색 (Graphical edge finding)

2) 동적 프로그래밍 (dynamic programming) 에 의한 에지 탐색

3) 분리 (Splitting) 와 합병 (Merging) 을 통한 영역분할 (Region Segmentation)

4. 대상물의 묘사와 레이블 부여 (Labeling)

1) 경계선 묘사 (Describing Boundaries)

2) 연쇄코드 (Chain Code)

3) 다른 묘사 특징

4) 3 차원 묘사

5) 제한조건의 만족 방법 (Constraint Satisfaction) 에 의한 필터링

6) 형판 비교일치 (Template Matching)

5. 높은 단계 처리 (High-Level Processing)

1) 비젼에 있어서 Marr 의 이론 (Marr's Theory of Vision)

2) 높은 단계 처리 (High-Level Processing)

6. 비젼 시스템 구조 (Vision System Architecture)

1) ACRONYM 시스템

2) Ohta 의 컬러 실상 분석기 (Color Scene Analyzer)

7. 요약

시각 (vision) 은 인간이 지니고 있는 지적 감각능력 중에서 아마도 가장 뛰어난 것이라고 할 수 있을 것이다. 인간은 사물과 직접 접촉하지 않고서도 시각시스템을 통하여 주변 환경에 대한 정보를 얻을 수 있다. 또한, 인간의 시각은 다른 어느 시스템보다도 경이적인 속도와 가장 높은 해상도 (resolution) 로서 정보를 얻을 수 있다. 그 차이를 알기 위해서는, TV 카메라와 인간의 해상도를 비교하는 것만으로도 충분하다. 대략적으로 TV 카메라는 1 ㎠ 당 500 점의 해상도를 지닌데 비하여, 인간의 눈은 1 ㎠ 당 거의 25 × 10⁶ 점의 해상도를 지니고 있다. 따라서, 인간의 눈은 TV 카메라보다 적어도 10,000 배 이상의 정밀한 시각 해상도를 지니고 있다. 더욱 주목할 만한 사실은, 인간은 힘들이지 않고 다양한 화상을 느끼고 인지할 수 있다는 점이다. 이러한 행동은 거의 노력을 기울이지 않고 이루어지기 때문에, 우리가 그것을 인식하는 일은 거의 없다.

이 장에서 컴퓨터 비젼시스템 (computer vision system) 을 구축하는데 있어서 제반처리과정과 문제점을 조사하고자 한다. 지금까지 채택되어온 몇가지의 접근방식과 현재까지 구축된 비젼시스템 중에서 몇몇의 성공적인 사례에 대해서 고찰하고자 한다.

1. 서론

컴퓨터 비전 (computer vision) 은 그 광범위한 이용 가능성 때문에 과거 수십년 동안 AI 와 공학 분야에서 가장 집중적으로 연구되어 온 분야 중의 하나이다. 몇몇 전형적인 응용분야는 다음과 같다.

제조 :

품질 관리를 위한 부품검사 부품의 조립, 분류, 분배, 배치, 포장

의학 :

X-선, 단층촬영 (tomographic), 초음파 등 의학용 화상처리

국방 :

사진 정찰, 분석, 화상 판독 목표물 탐지 식별, 추적 미생물 탐지 및 식별 미사일 유도 원격 또는 국지 (local site) 감시

사무 :

문서 자동 입력기 공학 및 건축가의 설계도구 식별을 위한 레이블의 검사 제품 내용물의 검사와 포장

로보트 :

용접 및 페인트 분사구 조절 부품 분류, 선택, 상자 포장 육지, 항공, 바다 운송물의 자동 항법 제어

우주탐사 :

천체 사진의 해석 인공위성 화상 지도작성, 식생의 병충해, 광물 퇴적, 곤충피해, 토양침식

등의 해석

유기조직체에 있어서 시각인식이란 빛 에너지 패턴을 감지하고, 이들 패턴에 대한 해석을 전개하는 과정이다. 처리의 감지부 (sensing part) 에서는 주위 환경의 일정 지역으로부터의 빛을 선택적으로 모아, 감광기능을 지닌 표면에 초점을 맞추어 투영하고, 빛을 전자 화학적인 자극 패턴으로 변환한다. 처리의 인지부 (perception part) 에서는 전달된 자극 패턴을 미리 저장되어 있는 패턴과 일정한 추론형식을 이용하여 변환하고 비교하는 처리를 포함한다. 인간에게 일어나는 기본적인 시각처리를 그림 1 에 나타내었다.

그림 1

조명된 물체로부터의 반사광이 눈의 수정체에 의하여 수집되고, 초점이 맞추어진 다음에 망막에 투영되면, 약 2 억 5 천만개의 시세포는 활동전위를 시신경을 통하여 후두부의 대퇴피질 시각정보처리역으로 전달하고 여기에서 화상이 해석되고 인식된다.

현재까지 우리가 알고 있는 바로는, 컴퓨터 시각시스템과 인간의 시각시스템은 몇 가지 유사점을 지니고 있다. 또한, 이들간에는 중요한 차이점도 있다. 비록 인공적인 시각시스템의 접근방식은 그 응용분야에 따라 크게 상이하지만, 여기서는 인간의 시각시스템과 동등한 능력으로 3 차원 실상 (scene) 의 높은 단계 묘사 (high-level description) 를 결정하는데 궁극적인 목적이 있는 일반적인 시스템을 상정하기로 한다. 진행하기에 앞서 실상 (scene) 과 화상 (image) 을 구분하기로 한다. 실상은 촬상 지역에 존재하는 물리적 대상물들의 집합이고, 반면에 화상은 2 차원 평면위에 실상을 투영한 것이다.

위에 기술한 목적을 염두에 두면, 전형적인 컴퓨터 시각시스템은 다음과 같은 조작을 수행할 수 있어야 한다.

1. 화상 형성, 감지 (sensing), 디지탈화

2. 국소처리와 화상 분할

3. 모양 (shape) 형성과 해석

4. 의미 분석 및 묘사

이들 조작의 처리순서를 그림 2 에 나타내었다.

그림 2

컴퓨터 비전의 각 처리단계를 진행시켜 나감에 따라 독자들은 시각처리와 자연어 처리 (natural language processing) 간의 유사성과 병행성을 인식하게 될 것이다. 비젼에 있어서의 화상 센서 (image-sensor) 단계는 언어이해의 음성인식에 해당하고, 비젼의 낮은 단계 (low-level) 및 중간 단계 (intermediate-level) 의 처리는 각각 언어처리의 구문과 의미 해석 처리에 해당하며, 각 경우의 높은 단계 (high-level) 처리는 고수준 지식 구조의 구축과 해석에 해당한다.

1) 시각처리 개요

비젼시스템의 입력은 임의 형식의 감광제 표면 위에 수집된 2 차원 화상이다. 이 표면은 일정 방식에 의하여 주사되어 화상 표면 위의 광도 (light intensity) 에 비례한 연속적인 전압의 출력을 만들어 낸다. 출력 전압 는 이산적인 점 또는 화소 (pixel, picture element) 들로 구분되어 표본화되어 숫자로 변환된다. 양자화된 숫자는 흑백화상에 있어서는 그 점의 농도에 일치한다. 컬러 (color) 화상의 농도치는 3 개의 분리된 배열로서 구성되며, 이들 각각은 3 원색 (red, green, blue) 에 대한 농도에 해당한다.

이러한 디지탈화 (digitization) 과정을 통하여 화상은 연속적인 광원 (light source) 으로부터 숫자의 배열로 변환되며, 이들 숫자는 감광제 표면위 해당 화소의 국소적인 화상 농도에 일치한다.

이 숫자배열을 이용하여 잡음 (noise) 을 제거하기 위한 근방점들간의 평활화처리 (smoothing), 대상물의 윤곽이나 에지 (edge) 요소의 추출, 임계치 처리 (thresholding, 일정 임계치에 의해서 최대치와 최소치 만으로 기록), 텍스쳐 (texture), 색상 또는 그밖의 대상물들에 관한 특징을 알아내는 것과 같은 낮은 단계 (low-level) 의 조작들이 행해진다. 이러한 초기의 처리단계들은 대상물의 경계선들과 화상중의 다른 구조들을 강조하거나 위치를 알아내는데 사용된다.

다음 처리인 중간단계 (intermediate level) 에는 경계선들을 연결, 보충, 결합하고, 영역을 결정하며, 이전 단계에서 강조된 대상물들에 대해 그 특징을 묘사하는 레이블 (label) 을 부여하는 처리가 포함된다. 이 단계에서는 처음 단계의 저차원적인 요소들로부터 보다 고차원의 구조를 만들어 낸다. 이 단계가 끝나면, 식별이 가능한 기하학적 물체와 같은 레이블이 부여된 표면들을 다음 단계로 전달한다.

높은 단계 (high-level) 에서의 화상처리는 화상에서 중요한 대상물들을 식별하고 이들간의 관계를 결정하는 처리들로 구성되며, 이들은 잘 정의된 지식 구조로 묘사되어 추론 요소로서 사용된다.

특수한 형태의 비젼시스템에는 운동 검출 (motion detection) 및 분석과 같은 3 차원 처리 및 분석이 필요한 경우도 있다.

2) 컴퓨터 비젼 시스템 (Computer Vision System) 의 목적

컴퓨터에 의한 화상이래의 궁극적인 목표는 인간의 시각시스템과 동등한 또는 더욱 우수한 능력을 지닌 시스템을 구축하는 것이다. 이상적으로는, 컴퓨터 비젼시스템은 아무리 복잡한 실상 (scene) 이라도 완전하고 상세하게 해석하고 묘사할 수 있는 능력을 지니고 있어야 할 것이다. 이는 시스템이 복잡한 대상물들을 모두 식별할 수 있어야 할 뿐만 아니라, 실상속에서 어떠한 일이 벌어졌는가, 왜 관측되는 또는 암시된 사건이 발생하였나, 무엇이 벌어질 것 같은가, 실상속의 대상물이 무엇을 할 수 있는가 등의 그들의 기능과 목적을 기술하기 위하여 대상물들에 대하여 추리할 수 있어야만 한다는 것을 의미한다.

그림 3

그림 3 에 인간이 그다지 노력을 기울이지 않고도 쉽게 해석이 가능한 복잡한 실상의 예를 나타내었다. 컴퓨터 비젼 분야의 많은 연구자들의 목적은 실시간에 이러한 유형의 실상을 해석하고, 묘사하고, 추리할 수 있는 능력을 지닌 시스템을 구축하는 것이다. 그러나 불행하게도 우리는 아직 이러한 수준의 능력을 달성하는 것으로 부터 멀리 뒤떨어져 있다. 몇몇 흥미있는 비젼시스템이 개발되었지만, 이들은 인간의 유능한 비젼시스템과는 비교할 수 없을 정도로 아무 미숙한 단계이다.

자연어 이해와 마찬가지로 컴퓨터 비젼에 의한 해석은 어려운 문제이다. 복잡한 실상을 해석하고 묘사하는데 필요한 처리와 기억의 양은 엄청나다. 예를들면, 한 장의 고해상도 항공사진에는 400~900 만 화소 (바이트) 의 정보가 있으며, 한 화소에 평균적으로 10~20 번의 계산을 필요로 한다. 따라서 처리할 동안에 몇 장의 사진이 저장되어야 한다면, 100 메가바이트 이상의 기억용량이 필요하고, 10 억번 이상의 계산이 수행되어야 할 것이다.

2. 화상변환과 낮은 단계 (low-level) 처리

이 절에서는 첫 번째 단계의 처리에 대하여 고찰한다. 여기에는 화상을 형성하고, 컴퓨터에 의한 조작이 가능하도록, 이를 숫자의 배열로 변환하는 처리가 포함되어 있다. 이 첫 번째 단계에서는, 잡음이나 불필요한 화상요소를 제거하고 대상물의 경계를 강조하기 위한 국소처리 (local processing) 가 각 화소에 대해서 행하여진다.

1) 빛 에너지 (light energy) 의 숫자로의 변환

화상처리의 첫단계에서는 빛 에너지를 컴퓨터의 언어인 숫자로 변환할 필요가 있다. 이를 위해서, 음극선관 (vidicon tube) 이나 전하결합장치 (CCD : charge-coupled device) 와 같은 빛에 반응하는 변환기를 사용하게 된다.

음극선관은 가정이나 산업용 비디오에서 전형적으로 사용되는 센서 (sensor) 의 한 종류이다. 음극선관의 평면에 화상을 투영하기 위하여 렌즈가 사용된다. 관평면에는 광전도성의 재료가 살포되어 있으며, 그 위의 광도에 반비례한 저항이 생성된다. FSS (Flying Spot Scanner) 는 전자총을 사용하여 평면을 왼쪽에서 오른쪽으로 또한, 위에서 아래로 빠른 속도로 주사 (scan) 한다. 주사 결과는 각 점의 화상 강도에 비례한 전압의 변화로서 나타난다. 연속적으로 변화하는 출력 전압은 ADC (Analogue/Digital Converter) 에 의해 주기적으로 표본화되어 숫자로 변환된다. 전형적인 ADC 는 한 화상에 256 × 256 또는 512 × 512 (또는 그 이상) 의 표본점으로 구성되는 완전히 디지탈화된 프레임들을 1 초당 30 매 생성한다. 각 점은 0 에서 64 (6 bit) 또는 0 에서 255 (8 bit) 범위의 한 숫자 (컬러 화상의 경우는 3 쌍의 숫자) 값을 지닌다. 그림 4 에 화상의 변환 처리가 설명되어 있다.

CCD 는 전하 전달기기로서 알려진 전형적인 고체 촬상소자이며 현재 많은 비젼시스템에서 사용되고 있다. CCD 는 정전하를 축적할 수 있는 광전소자 (photodetector) 의 배열로 구성된 사각형이 칩 (chip) 이다. 전하는 클럭 구동형자리이동 레지스터 (clock-driven shift register) 처럼 주사되어, 소자에 입력된 광도에 비례하여 시간에 따라 변화하는 전압으로 변환된다. 이 전압은 음극선관의 경우와 마찬가지로 ADC 에 의하여 표본화되고 숫자로 변환된다. 칩 위의 광전소자는 매우 밀집되어 있다. 예를 들어, 면적 5 ㎠ 의 CCD 칩에는 1000 × 1000 개 이상의 소자가 포함되어 있다.

ADC 로부터의 출력된 결과는 변환기 표면위에 형성된 화상의 광도에 일치하는 숫자의 배열로서 모아진다. 이것이 그림 4 에서 설명한 처리의 다음 단계에서 사용되는 입력이다.

그림 4

2) 양자화된 배열 (Quantized Arrays) 의 처리

촬상 기기 (image sensing device) 로부터 생성된 수의 배열은 비젼 이해 과정에 있어서 가장 낮고, 원시적인 추상화 단계로 생각될 수 있다. 계층적 처리에 있어서 다음 단계는, 화상에서 영역이나 대상물의 경계를 정의하는 화소군과 같은 구조를 알아내는 것이다. 따라서, 이들 대상물 영역간의 경계 또는 다른 구분선을 발견하기 위하여 원래의 화소 데이터를 분리된 동질의 영역들로 변환할 필요가 있다.

원화상에는 얼마간의 잡음 (noise) 과 왜곡 (distortion) 성분이 포함될 수 있다. 따라서, 경계나 영역을 추출하기 전에 이들의 영향을 제거하기 위한 처리가 필요하다. 응용분야에 따라서는, 이러한 잡음을 제거하기 위한 국소적인 평활화 (smoothing) 가 낮은 단계 처리에서 행하여진다. 그밖의 낮은 단계에서의 처리로는 동질 영역을 정의하기 위한 임계치 처리 (thresholding), 경계선을 정의하기 위한 여러 가지 형태의 에지 검출 (edge detection) 처리가 있다. 다음에는 이러한 몇가지의 낮은 단계 처리들에 대하여 고찰하기로 한다.

임계치 처리는 계조도 (gray level) 를 지니고 있는 화상을 두 가지의 값만으로 표현된 화상으로 변환하는 처리이다. 화상 배열의 모든 요소들에 대하여, 일정 임계치 T 이상의 값은 최대 계조도 값 (black) 으로 설정되고, T 보다 작거나 같은 값을 갖는 경우에는 0 (white) 으로 설정된다. 간단히 말해서, 계조도값이 0 에서 1 사이의 범위로 정규화 되었고, 임계치가 T = 0.7 로 선택되었다고 가정하자. 이 경우, 를 만족하는 모든 배열 요소는 값은 1 로 설정되고, 을 만족하는 경우에는 0 으로 설정된다. 결과는 0 과 1 의 이치값만을 갖는 배열이다. 그림 5 에 임계치를 0.7 로 하여 얻어진 이치화상 (binary image) 의 예를 나타내었다.

그림 5

임계치 처리에 의해서 어떤 부분은 강조하고 잡음 성분이나 불필요한 특징들은 제거할 수 있기 때문에, 화상을 선명한 대상물 영역들로 분할하기 위한 한가지 방법이 된다. 또한, 임계치 처리는 이어지는 처리 단계들을 단순화하는데 도움이 될 수도 있다. 그리고 많은 경우에 있어서, 낮은 농도를 지닌 대상물의 표면이 높은 임계치에 의하여 손실되거나, 낮은 임계치에 의하여 불필요한 배경이 추출되어 강조될 수가 있기 때문에, 몇가지 다른 임계치를 사용할 필요가 있는 경우도 있다. 여러개의 임계치에 의한 처리는 조명 변화나 낮은 명암비 (contrast) 를 보정할 필요가 있는 화상에서 상이한 영역들을 분류하기 위한 가장 좋은 방법이 될 수도 있다.

한 개 또는 여러개의 적정 임계치 를 결정하기 위해서는 우선 화상 농도 히스토그램 (histogram) 의 산출과 같은 부수적인 처리가 필요하다. 히스토그램은 화상에서 상이한 농도 (또는 다른 특징) 값들의 발생 빈도를 나타낸다. 히스토그램 분석에 의하여 상이한 농도값들의 집중적인 발생여부, 돌출부 (peak) 또는 넓고 평탄한 부분의 발생여부, 발생 빈도에 있어서의 돌연한 변화 등이 나타날 수 있다. 이들 정보로부터 가장 좋은 값들의 선택이 명백해 지는 경우가 자주있다. 예를 들어, 상대적으로 발생 빈도가 높은 농도치들에 의해서 2 개 이상으로 명확한 분리가 이루어진 히스토그램에는, 보통 대상물 식별과 분리를 위해 가장 높은 임계치들이 암시되어 있다. 이것은 그림 6 에 나타내져 있다.

그림 6

다음은 화상 평활화 (smoothing) 문제로 전환하자. 평활화는 디지탈 필터링 (filtering) 의 한 형태이다. 이것은 잡음과 불필요한 특징을 제거하며, 일정한 특징을 강조하는데 사용된다. 평활화는 스파이트 (spike) 를 억제하며, 급격하게 변화하는 농도값을 광범위하게 평탄화하는 화상변환의 한 형태이다. 국소적 평균, 모델 이용에 의한 파라메트릭 형상 적응처리 (parametric form fitting) 와 같은 여러 가지 형태의 평활화 기법이 사용되고 있다.

일반적으로 사용하는 평활화 기법중의 하나는 화상 배열에 있어서 각 화소의 값을 해당 화소와 근방 농도값의 가중치에 의한 평균으로 대치하는 것이다. 이것은 평활화된 값을 구하기 위해 사용하는 근방화소 (neighbouring pixel) 의 임의의 배치를 결정하는 마스크 (mask) 에 의해 이루어진다. 4-근방 또는 8-근방 화소로 구성되는 전형적인 2 가지 마스크의 농도치가 가중값의 계산에 사용된다. 만일, 평활화가 화소 위치 에서 실행되고 있다고 가정하면, 8 개의 근방화소들은 다음과 같다. : , , , , , , , 및 . 이들로부터 필요에 따라 4-근방 (상, 하, 좌, 우) 또는 모든 이웃화소를 포함하는 8-근방이 선택된다.

8-근방 및 4-근방 화소에 대한 평활화 마스크의 예는 다음과 같다.

각 마스크에서 밑줄이 처져 있는 숫자는 현재 평활화 중인 화소를 나타낸다. (마스크에서 모든 가중치의 합은 값이 왜곡되는 것을 피하기 위하여 1 이 됨을 주의하라.) 화상 배열에 평활화 마스크를 적용하면, 선명한 경계부분과 같은 의사 잡음 (spurious noise) 이 제거되는 부작용이 발생한다. 즉, 예리한 스파이크 (spike) 를 제거할 뿐 아니라 화상을 흐리게 하는 경향도 있다. 그림 7 에 위의 8-근방 마스크를 사용한 예가 나타나 있으며, 평활화 후의 화상이 원 화상에 비하여 흐려진 것을 잘 알 수 있다.

그림 7

국소적 에지 (edge) 추출은 두 영역 사이의 경제 또는 윤곽을 발견하기 위한 처리이다. 에지는 서로 상이한 두 개의 동일영역간의 경계부문에서 명암 (contrast) 차이로서 나타나는 상대적으로 가는 선 또는 호 (arc) 이다. 같은 대상물에 속하는 영역은 통상적으로 그 영역 전체를 통하여 균일한 한가지 이상의 특징에 의하여 구분할 수 있으며, 이러한 특징으로는 색상, 텍스쳐 (texture), 3 차원 고아규 (optical flow) 효과 또는 농도 등이 있다.

인접한 영역사이를 분리하는 경계선들은 한 개 이상의 이들 특징의 불연속성에 의해 표현되며, 이것은 화상 표면에 걸쳐 특정한 특징값의 변화율을 측정하는 것에 의하여 알아낼 수 있다. 예를 들어, 수평 또는 수직 방향에 있어서 농도의 변화율 또는 기울기 (gradient) 는 다음과 같은 차분함수 (difference function) 와 에 의하여 측정될 수 있다.

여기에서 은 1 이상의 작은 정수값이다.

화상이 수평 또는 수직으로 주사될 때, 동질의 영역에 걸쳐서는 또는  의 값이 거의 변하지 않으나, 특징이 변화하는 곳에서는 이들 값이 크게 증가하거나 감소한다. 위의 식은 미분법에서 사용되는 연속적인 미분 연산자 (operator) 의 이산적 형태에 해당된다. 기울기 (gradient) 의 변화율은 다음에서 보이는 바와 같이 국소적인 에지를 발견하는 데에도 사용될 수 있다. 이차 미분 연산자에 대응하는 이산적인 2 차 차분 연산자가 기울기 변화율을 계산하는데 사용된다.

모든 방향의 에지를 추출하기 위해서는, 모든 방향의 농도 변화에 민감한 기울기의 측정법이 보다 바람직하다. 이는 다음의 벡터 기울기 (vetor gradient) 와 같은 와 의 방향 노름 (directional nrm) 을 구함으로서 이루어질 수 있다.

에 대하여, 동일한 가중치 마스크를 적용할 때 와 를 가장 수월하게 구할 수 있으며, 이때 2 개의 마스크는 각각 과 이다.

그림 8

이 두 마스크를 화상에 적용한 결과를 그림 8 에 나타내었고, 여기에서 수직 방향의 에지가 아주 뚜렷하게 보인다. 이와 유사하게, 보다 넓은 영역에서 여러 화소를 포함하여 기울기 (gradient) 를 측정하기 위한 마스크도 일반화되어 있다. 이러한 마스크는 의사 잡음과 예리한 스파이크 (spike) 를 제거하는 효과도 지니고 있다.

특히 주목할 만한 가치가 있는 2 개의 마스크로는 Prewitt (1970) 와 Sobel (1970) 이 제안한 것이 있으며, 이들을 그림 9 에 나타내었다. 이들 마스크는 위에서 설명한 단순한 마스크보다 더욱 넓고 정규화된 기울기를 계산하는데 이용된다. 이 마스크에 의한 상세한 계산은 이장 마지막의 연습문제로서 남겨두었다.

Generalized edge detection masks.

그림 9

다음에는, 기울기를 계산한 다음에 평활화를 하여주는 에지 (edge) 추출법에 대하여 살펴보기로 한다. 이를 위해서는 연속적인 경우가 고려되어야 한다.

1 차원에 있어서 이산적 평활화 처리의 연속적인 아날로그 형태는 두 개의 함수 와 의 콘벌루션 (convolution, 라 씀) 에 해당한다.

두 개의 함수 와 의 컨벌루션은 상호상관 (cross correlation) 을 구하는 것과 유사하며, 이 처리는 임의의 잡음을 제거하고 동질성 또는 구조적인 변화를 강조한다.

대칭적인 종 (bell) 모양 또는 정규화된 형태를 하고 있는 하나의 특별한 형태의 가중치 함수 에 가우스 (Gaussian) 분포가 있다. 이 함수의 2 차원 형식은 다음과 같다.

여기에서 는 정규화 상수 (nomalizing constant) 이다.

가우스 필터 (Gaussian filter) 는 회전적인 대칭성을 지니고 있기 때문에, 이어서 2 차 미분 (기울기) 연산자를 적용하였을 때, 에지 추출기로서 바람직한 효과를 지니고 있다. 그림 10 에 설명한 바와 같이, 불연속적인 영역사이에는 2 차 미분 수행후에 얻어진 농도값에 영 교차점 (zero crossing) 이 존재한다. 따라서 평활화 및 미분을 수행하는 연산자가 하나의 연산자로서 결합될 수 있으며, 위에 주어진 형태에 근사한 디지탈 마스크 (digital mask) 로서 구현된다 (Marr and Hildreth, 1980).

그림 10

인간의 눈이 수평 반사억제 (lateral inhibition) 라 불리우는 일종의 가우스 변환을 사용한다는 사실이 생리학적으로 뒷받침되고 있으며, 이 현상은 대상물과 이의 배경과 같이 점진적으로 변화하는 물체사이의 경계부분에 존재하는 명암을 더욱 강조하는 현상을 말한다.

디지탈 화상에 적용할 수 있는 다른 필터링 (filtering) 법으로는 Fourier 변환과 같은 주파수 영역에서의 처리가 있다. 에지는 고주파수 성분을 지니고 있기 때문에, 주파수 분포에 기초하여 변환된 화상이 분석될 수 있다. 이를 위한 변환방법으로 Fourier 변환이 가장 일반적으로 사용되고 있으며, 효율적인 계산 알고리즘도 개발되어 있다. 이것은 FFT (Fast Fourier Transform) 로 알려져 있다. 이산적인 이차원 Fourier 변환은 다음과 같이 주어진다.

농도치의 배열에 이 변환을 적용하면, 화상의 각 공간주파수 성분에 일치하는 복소수 배열이 얻어진다 (sin 과 cos 항들의 합). 변환된 배열은 원 화상의 농도에 대한 모든 정보를 지니고 있으며, 상이한 주파수 성분을 지닌 영역들을 식별하기 위한 형태로 더욱 많이 이용된다. Fourier 변환에 의한 필터링 (filtering) 은 높은 (또는 낮은) 와 성분을 0 으로 만들어 줌으로서 행해질 수 있다. 예를들어, 값 는 0 (zero) 주파수 또는 DC 성분에 해당하며, 와 의 값이 높으면 고주파수 성분에 해당된다. 변환된 배열에 대한 임계치 처리 (thresholding) 처리는 원화상에서 서로 다른 주파수 성분을 분리하는데 사용될 수 있다.

임의의 수정을 거친 원화상은 다음식과 같은 역변환 (inverse transform) 에 의하여 복원된다.

에지추출을 위한 다른 방법으로는 모델 적응처리 (model fitting) 가 있다. 이 처리는 원 화상과 에지의 파라메트릭한 단면 (parametric profile) 을 국소적으로 대응시키는 것에 의하여 달성된다. 마스크 형식의 모델이 영역 위를 이동하며 대응하는 농도값과 비교된다. 만일 모델과 농도패턴간에 충분히 높은 일치도를 보이면, 주어진 방향의 에지가 적당한 방법으로 레이블 (label) 된다. 모델 적응처리는 많은 계산량을 필요로 한다. 여기서는 상세한 설명을 생략한다.

3) 텍스쳐 (texture) 와 색상 (color)

앞에서 설명한 바와 같이 텍스쳐와 색상은 영역이나 경계선을 식별하는 데에도 사용된다. 텍스쳐란 대상물 표면위에 발생한 기본적인 모양들의 반복된 패턴이다. 텍스쳐는 규칙적이며 주기적으로, 임의로 또는 부분적인 주기로 나타날 수 있다. 그림 11 에 표면 텍스쳐의 몇가지 예를 설명하였다.

그림 11

텍스쳐는 비록 농도 변화가 충분히 관찰된 수 있을 만큼 크더라도, 그 구조를 분석하기에는 너무 미세한 것이 보통이다. 그럼에도 불구하고, 텍스쳐 분석을 위한 여러 가지 수법들이 개발되었다. 이 수법들은 보통 작은 화소군의 통계학적 분석, 패턴 비교일치 (pattern matching) 의 응용, Fourier 변환의 응용, 또는 프랙탈 (fractal) 로 알려진 특변 함수로서의 모델링 등에 기초하고 있다. 이들 수법은 이장 목적의 범위를 벗어남으로 설명을 생략한다.

영역의 식별과 해석에 색상을 이용하는 데에는 흑백 정보에 비하여 3 배 더 많은 처리를 필요로 한다. 우선, 화상을 red, blue, green 의 필터 (filer) 를 이용하여 3 원색으로 분리하여야 한다. (그림 12).

그림 12

분리된 컬러화상은 흑백에서와 마찬가지로 농도를 표본화하여 3 개의 배열을 만들거나, 각 요소가 3 가지 값을 지닌 한 개의 배열로 만든다. 다음에는 이들 배열이 각각 (때로는 함께) 동일 영역들과 이들간의 경계선을 결정하기 위하여 처리된다. 경계선과 영역을 추출하고 컬러화상을 해석하기 위하여 사용되는 처리들은 흑백 시스템에서와 동일하다.

컬러화상의 분석에 소요되는 부가적인 계산은 무사할 수 없으나, 응용분야에 따라서는 분리된 컬러 화상으로부터 얻을 수 있는 부수적인 정보들로 충분히 보상될 수 있다. 복잡한 실상 (scene) 의 분석에서는 색상 정보가 분할과 대상물 식별을 위한 가장 효과적인 방법이 된다. 비젼 시스템 구조에서 규칙기반 추론 시스템 (rule based inferencing system) 에 근거한 흥미있는 컬러 실상 분석기 (color scene analyzer) 에 대해서 설명한다.

입체시 (stereoscopic) 를 위한 비젼시스템에서는 대상물을 다른 2 개의 시점에서 관찰하기 위하여 서로 떨어진 2 개의 센서 (sensor) 를 필요로 한다. 관찰된 결과의 차이로부터 대상물까지의 거리를 평가하고 실상 (scene) 의 3 차원 모델을 유도할 수 있다. 동일한 물체는 두 개의 화상에서 서로 다른 위치에 투영되며, 이러한 화소간의 위치차이를 변위 (disparity) 라 한다. 두 화상간의 변위로부터 실상에서 대상물들의 거리를 평가할 수 있다. 인간의 비젼시스템은 두 개의 다른 화상을 결부시켜서 대응점들을 형성하고, 이로부터 3 차원의 해석을 이끌어내고 있다. 그림 13 은 임체시 시스템에 있어서 대상물까지의 거리를 평가하는데 이용되는 기하학적 관계를 설명하고 있다.

그림 13

렌즈로부터 대상물까지의 거리 는 삼각형의 닮은 꼴 관계로부터 유도할 수 있다. 즉, 및 로부터

가 성립한다. 와 는 상대적으로 일정하기 때문에, 거리 는 변위 또는 과 의 합에 대한 함수이다.

컴퓨터 비젼시스템에서는 두 개의 화상으로부터 대응점들을 찾아내는 것이 변위를 결정하는데 있어서 가장 어려운 부분이라 할 수 있다. 두 화상간에 일치하는 화소들을 찾아내는 것은 변위를 결정하고 이로부터 거리를 계산하기 위해 반드시 필요하다. 실제로는 상관 (correlation), 농도비교일치 (gray-level matching), 형판비교일치 (template matching), 에지 윤곽선 비교 (edge contour comparisons) 등의 방법이 입체 화상으로부터 변위를 평가하는데 사용된다.

광류 (optical flow) 는 3 차원 실상 분석을 위한 또 다른 방법으로서, 실상에 있어서 센서와 물체의 상대적인 운동에 기초를 둔 것이다. 센서가 이동할 때 (또는 센서에 물체의 상대적인 운동에 기초를 둔 것이다. 센서가 이동할 때 (또는 센서에 대하여 물체가 이동할 때), 센서에 대한 물체의 분명하고 연속적인 흐름이 생기며 이를 광류 (optical flow) 라 한다. 이러한 센서와 물체들의 흐름 또는 상대적인 속도의 변화로부터 거리를 계산할 수 있다. 예를 들면, 그림 14 에서 만일 센서의 속도가 일정하다고 가정하면, 점 과 간의 간격 변화 는 전선 의 크기 변화와 다음의 관계에 의하여 비례하게 된다.

이 관계는, 그림 14 에서 보인 것 같은 고속도로, 기차 선로 또는 전선 등과 같이 거리에 따라 규칙적으로 흐르는 물체의 크기 변화에 있어서 동등하게 성립한다.

그림 14

3. 중간 단계 (intermediate level) 화상처리

위에서 기술한 낮은 단계 (low-level) 또는 초반처리단계 (early processing steps) 에 이어 분석을 위한 다음의 중요한 처리가 이어진다. 이 처리는 화상공간을 보다 큰 전역적인 구조 (global structure) 로 분할하는데 중점을 두며, 화소영역내의 균일한 특징들과 낮은 단계 처리에서 추출한 에지 (edge) 조각들로서 형성된 경계선을 이용한다. 이 단계에서는 에지 조각들을 대상물의 외형을 형성하는 연속적인 윤곽선으로 결합할 필요가 있으며, 화상을 균일한 영역들로 구분하고, 분할된 대상물의 모델을 만든 다음, 대상물 특성을 나타내는 레이블 (label) 을 부여한다.

일련의 대상물을 정의하는 방법중의 하나는 대상물 외형의 윤곽 (silhouette) 또는 스케치 (sketch) 를 만드는 것이다. 이러한 스케치를 Marr (1982) 는 기초 스케치 (low primal sketch) 라 하였다. 이를 위해서는 연속적인 경계선을 형성할 가능성이 높은 에지 조각들을 연결하여야 한다. 예를들어, 다음과 같은 두 개의 에지 조각들을 연결해야 하는지를 결정하는 것이다.

에지 조각들로부터 윤곽선을 형성하는 이러한 일반적인 처리를 분할 (segmentation) 이라 한다.

1) 그래픽적 에지 탐색 (Graphical edge finding)

에지 조각들을 연결하는데 있어서 그래픽적 수법이 사용될 수 있다. 한가지 방법은 최소 스패닝 트리 (MST : Minimum Spanning Tree) 를 이용하는 것이다. 한 에지의 일부분의 밝혀진 화소군으로부터 시작하여, 유사한 특징값들을 지닌 이웃의 화소군을 찾아 하나의 그룹으로 묶는다. 이러한 각 그룹은 에지 트리 (edge tree) 에 있어서 하나의 노드 (node) 에 해당한다. 여러개의 노드들이 찾아지면 MST 알고리즘을 이용하여 이들을 연결하게 된다.

MST 는 선택된 첫 번째 노드와 가장 인접한 노드를 연결하고, 두 개의 노드에 적당히 레이블을 부여 (labeling) 한다. 다음에는 연결된 노드들의 이웃이 탐색된다. 연결된 두 개의 노드들로부터 가장 가까운 노드 (일정한 임계치 거리 이내) 가 발견되면 이것은 트리의 다음 가지로 사용된다. 새롭게 발견된 노드와 가장 가까운 노드간을 연결하고, 앞에서와 같이 새로운 노드에 대하여 레이블을 부여한다. 이러한 처리를 일정값 이하의 아크 (arc) 거리 (예를들어, 평균 아크 거리) 를 지닌 모든 노드들이 연결될 때까지 반복한다. MST 의 예가 그림 15 에 주어져 있다.

그림 15

그밖의 그래픽적 방식으로는 비용을 할당하거나 또는 다른 평가척도에 기초하여 화소들을 그룹화하는 것이다. 비용의 할당은 농도, 방향 또는 색상과 같은 단순한 특징에 기초하여 이루어질 수 있다. 그 다음에 최적일치 (best-first, 분기와 한계) 나 다른 형태의 그래프 탐색방법이 경험적 함수를 이용하여 에지 윤곽선 (edge contour) 를 나타내는 최소비용 경로를 결정하기 위해서 실행된다.

다른 에지추출 방법으로는 국소적인 탐색에 의하여 발견된 에지조각에 낮은 차수의 다항식을 일치 (fitting) 시켜보는 것이다. 그런 다음에 일치하는 다항식의 곡선들이 에지의 경계로서 받아들여 진다. 이 방법은 적은 그룹의 조각들에 에지의 형판 (template) 을 대조하는 것과 유사하다. 만일 특정 형판과의 정합도가 일정 임계치를 넘으면, 그 형판 패턴이 윤곽선을 정의하기 위하여 사용된다.

2) 동적 프로그래밍 (dynamic programming) 에 의한 에지 탐색

가장 바람직한 에지 경로를 추출하는 것은 순차적인 최적화 문제의 한 유형에 속하기 때문에, 에지 추적 (edge following) 은 동적프로그래밍 문제로서 공식화될 수 있다. 후보 에지조각들에 대해서는 농도와 같은 특징에 기초하여 국소적인 비용이 할당되고, 최소비용을 지닌 경로가 에지 윤곽선으로 정의된다.

출발전 가 선택되었다고 가정하자. 동적프로그래밍은 문제의 한 부분으로부터 시작하여, 이 부분문제에 대한 최적해를 발견한다. 다음에 이 부분문제가 확대되고, 확대된 부분문제에 대한 최적해를 발견한다. 전체적인 문제에 대한 최적해 (종단 에지점 까지의 경로) 를 발견할 때까지 이 처리가 단계적으로 반복된다.

이 처리는 회귀 처리로서 수학적으로 기술될 수 있다. 위치 (또는 상태) 에서 출발하여 다음 움직이는 방향으로 을 선택하였을 때, 나머지 경로 증가분에 대한 최적경로의 총비용을 라 하자. 또한, 을 최소화하는 의 값을 이라 하고, 이 때의 을 이라 하자. 각 단계에서 다음 값들이 계산된다.

여기서,

여기서 은 단계 에서의 비용이며, 은 단계 에서 최종단계까지의 비용이다.

계산과정을 예를 들어 알기 쉽게 설명하자. 다음과 같은 화소값을 지닌 5 × 5 배열을 생각한다.

배열의 좌하에서 우상의 요소까지의 최적비용경로를 알아낸다고 가정하자. 어느 방향으로부터도 시작할 수 있으나, 값 8 을 지닌 좌하의 화소로부터 시작하기로 한다. 처음에 8 을 제외한 모든 값을 매우 큰 수 으로 설정하고, 마지막 행의 모든 화소들에 대해서 한 화소로부터 이웃화소로 이동하며 비용을 증가하여 8 이 있는 위치로부터의 최소비용을 계산한다. 이에 의하여 다음의 비용 배열이 얻어진다.

다음으로 마지막 행으로부터 다음 행의 최소 이웃경로비용 (minimum neighbor path cost) 을 계산할 수 있다.

이 행의 두 번째, 세 번째, 네 번째 위치로의 최소비용경로는 대각선 경로 (위치 5, 1 에서 4, 2) 에 이은 동일 행의 오른방향으로의 횡단경로이며, 이 행 마지막 위치의 최소비용 경로는 마지막 행 좌우측 위치를 통과하는 경로이다. 다음 행들에 대해서 동일한 방식에 의하여 나머지의 최소경로 비용들을 계산하면, 다음과 같은 최종 비용 배열이 얻어진다.

이 최종 최소비용 배열로부터 다음과 같은 최소의 비용경로를 알 수 있다.

(5, 1) → (4, 1) 또는 (4, 2) → (3, 2) → (2, 3) → (1, 4) → (1, 5)

이를 이중선으로 나타내면 다음과 같다.

동적프로그래밍 방식으로 방대한 양의 계산과 비교를 행하는 소모적 방법 (탐색과 제어전략) 에 비하여 상당히 계산양을 감소시킬 수 있다.

3) 분리 (Splitting) 와 합병 (Merging) 을 통한 영역분할 (Region Segmentation)

에지에 의하여 영역을 정의하는 것보다, 오히려 영역을 형성하여 나가는 것이 가능성이 높을 수도 있다. 예를 들어, 화소들의 그룹으로부터 색상, 텍스쳐, 농도와 같은 균일한 특징을 지닌 영역의 위치를 알아내고, 이들을 연결, 정의하는 것에 의하여 전체적인 구조를 만들어낼 수 있다. 결과로서 얻어지는 분할 영역들은 실세계에 있어서의 각각 대상물 표면에 일치하는 것으로 기대할 수 있다. 이러한 균일한 영역들이 항상 의미있는 영역에 해당하는 것은 아니지만, 화상 분할을 위해서 사용할 수 있는 방법중의 하나가 될 수 있다. 이러한 방법들이 다른 분할 기법과 결합하여 사용되는 분리된 영역이 의미있는 대상물이 될 수 있는 확신도가 높아질 것이다.

일단 화상이 분리된 대상물 영역들로 분할되면, 그 영역은 그들이 지닌 성격과 다른 대상물들과의 관계에 의해서 레이블이 부여되고, 모델 비교일치 (model matching) 나 묘사만족 (description satisfaction) 과정 통하여 식별된다.

영역분할은 영역분리 (region splitting), 영역확장 (합병, region growing or merging), 또는 이 두가지 방법의 결합에 의하여 이루어질 수 있다. 만일 영역 분리를 이용하면 처리가 하향식으로 진행된다. 일정 조건이 만족될 때까지 계속적으로 화상을 더욱더 작은 균일한 조각들로 분리하여 나간다. 영역확장에 있어서는 처리가 상향식으로 진행된다. 각 화소 또는 화소의 작은 그룹들이 계속해서 연속적이고 균일한 지역들로 합병된다. 분리와 합병이 결합된 방식에 있어서는 상향식과 하향식의 기법이 함께 사용된다.

영역은 보통 다음과 같이 화상을 구분하는 분리된 개체들로서 간주된다.

(1) 주어진 화소는 한 영역에만 나타나고,

(2) 부분영역은 연결된 화소들로서 구성되며,

(3) 다른 영역들은 서로 분리된 지역들이다.

(4) 그리고, 화상전체는 모든 영역들의 조합에 의해서 구성된다.

영역들은 보통 어떤 균일한 성질에 의해서 정의되며, 그 영역에 속하는 모든 화소들은 그 성질을 만족하고, 그 성질을 만족하지 않는 화소는 다른 영역에 존재하게 된다. 어떤 물체는 분리되거나 단절된 표면들로 뒤덮여 있을 수도 있기 때문에, 영역이 연속적인 화소들로만 구성될 필요가 없음을 주목하라. 두 번째 조건은 모든 영역들이 설명이 되고, 그 영역들로 화상이 완전하게 채워지는 것을 보증하기 위해서 필요하다.

영역분리 (region splitting) 에 있어서, 처리는 전체 화상으로부터 시작하여 일정한 특징을 지닌 작은 영역들로 계속해서 나누어가게 된다. 효과적인 한가지 방법으로는 다중 임계치 (multiple thresholding level) 를 이용하는 것이 있으며, 이에 의해 화상을 균일한 특징을 지닌 영역들로 분리할 수 있다. 임계치를 구하기 위해서 우선 히스토그램이 얻어진다. 이것은 복잡한 물체를 효과적으로 분리하기 위해서 화상의 일부분을 마스킹 (masking) 하는데 필요하다. 각각의 임계치는 그 임계치를 넘는 모든 물체들로 구성된 이치화상 (binary image) 을 만들어 낸다. 일단 이치의 영역이 형성되고나면, 이어지는 다음 처리에서 용이하게 윤곽이 그려지고, 분리되고 표시될 수 있다. 이 처리는 화상이 모두 분할되어 마스크내에서 단일 봉우리 (monomodal) 의 히스토그램을 만들어 낼 때까지 계속된다.

영역확장 (region growing) 에 기초한 화상 분할은 아주 작은 영역 (한 화소 또는 몇 개의 화소) 으로부터 출발하여 상향식으로 균질한 화소영역을 구축해 나가게 된다. 근방 화소들의 평균 농도와 차이가 적으면 두 지역은 합병이 되며, 경계부문에서와 같이 두 그룹간이 차이가 클 경우에는 영역분리를 위한 기준이 될 수 있다.

분리-합병 기법은 위의 두가지 방법의 장점을 취한 것이다. 이것은 더 이상은 분리-합병을 위한 기준들이 존재하지 않을 때까지, 상향식과 하향식의 수법을 혼합하여 영역의 분할과 합병을 해나간다. 처리의 각 단계에 있어서 분리와 합병을 위한 임계치가 비교되고, 적절한 조작이 수행된다. 이 방법에서는 과다한 분리 (over-splitting) 나, 미흡한 합병 (under-merging) 을 피할 수 있다.

4. 대상물의 묘사와 레이블 부여 (Labeling)

이 절에서는 보다 높은 수준의 추상화를 목표로 하는 중간단계 처리 (inter-mediate-level processing steps) 들에 대해 계속하여 설명하기로 한다. 여기서의 처리 단계들은 영역의 묘사와 레이블 부여에 관계된 것들이다.

일단 화상이 분리된 영역들로 분할되면, 이어지는 처리를 위하여 각 영역의 모양과 공간적 상호관계 및 다른 특징들이 묘사되고 레이블이 부여된다. 여기서는 물체의 윤곽, 경계, 정점과 표면 등이 어떤 방법에 의해서든지 묘사되어야 한다. 영역의 묘사는 2 차원 또는 3 차원의 화상 해석에 기초할 수 있다. 우선, 2 차원 해석에 초점을 맞추기로 한다.

전형적으로, 영역의 묘사에는 크기, 모양 및 일반적인 외관에 관련된 특성이 포함된다. 예를 들면, 다음과 같은 특징들의 전부 또는 일부가 포함될 수 있다.

• 영역의 면적
• 윤곽 길이 (주변장, perimeter) 및 방향
• 중심 (center of mass) 의 위치
• 최소 외접 사변형
• 밀집도 (compactness, 면적을 주변장으로 나눈 것)
• 화소의 산점 행렬 (scatter matrix)
• 구멍 (hole) 또는 내부 폐포 (internal occlusion) 의 수 및 특성
• 텍스쳐의 각도 및 종류
• 평균농도 (또는, 삼원색의 평균농도)
• 경계 선분들의 종류 (선명함, 애매함 등) 와 위치
• 경계 명암차이 (contrast)
• 연쇄 코드 (chain code)
• 모양 분류 수 (shape classification number)
• 정점 (vertices) 의 위치와 종류 (인접한 선분 수)

이들 중 몇가지의 특징을 그림 16 에 나타내었다.

그림 16

이러한 특징들 이외에도, 또한 영역간 특히 인접한 영역간의 관계가 중요하다. 영역간의 관계에는 그들의 상대적인 방향, 경계선간의 거리, 사이에 있는 영역, 색상의 농도 또는 명암, 접합의 정도, 연결 또는 집중의 정도 등이 포함될 수 있다. 만일 화상 정의역 (image domain) 을 이미 알고 있는 경우에는 그 문제 분야에 특수한 특징들이 사용될 수도 있다.

다음은 영역묘사에 사용되는 몇가지의 정의와 방법들에 대해 알아보기로 한다.

1) 경계선 묘사 (Describing Boundaries)

경계선 (boundary) 은 연결된 직선선분이나 적응된 다항식 곡선 (fitted polynomial curves) 또는 몇가지의 다른 방법에 의해서 묘사될 수 있다. 임의의 경계선에 대하여 직선선분을 일치시키는 가장 단순한 방법은 연속적인 선형분할 적응처리 (liner segmentation fitting) 에 의하는 것이다. 이 방법은 계산비용에 따라 여하한 적응정확도 (degree of fit accuracy) 도 허용할 수 있다. 적응처리의 절차가 그림 17 에 설명되어 있다.

그림 17

일치처리는 두 끝점을 하나의 직선으로 연결함으로서 시작되며, 이것이 곡선 (a) 의 근사치로서 이용된다. 다음에 일치된 선으로부터 가장 큰 수직거리를 지닌 점들을 이용하여 부가적인 선들을 구성하게 된다 (b, c, 및 d)

적응처리를 수행하기 위한 알고리즘은 다음과 같이 진행될 수 있다.

1. 경계곡선의 두 끝점으로부터 시작하여 두점간을 잇는 직선을 구성한다.

2. 곡선을 따라 일정간격으로 직선으로 부터의 수직거리를 계산한다. 만일 최대거리가 어떤 정해진 한계 이내이면, 처리를 중단하고, 경계의 근사치로서 지금까지 분리된 선들을 이용한다.

3. 그렇지 않으면, 최대 거리가 발생한 곡선위의 한점을 선택하고, 이 점을 두 끝점과 연결하여 새로운 두 개의 선을 구성하는 분기점으로 이용한다. 이 처리를 각 부분 곡선들이 단계 2 의 조건을 만족할 때까지 반복한다.

2) 연쇄코드 (Chain Code)

경계 묘사를 위한 다른 방법으로 연쇄코드 (chain code) 로 알려진 수법이 있다. 연쇄코드란 변위의 형식으로 영역의 경계를 묘사하는 일련의 정수이다. 연쇄코드는 이어지는 단위 선분의 방향 변화를 추적할 수 있는 4 개 또는 그 이상의 방향 숫자에 의하여 정의된다. 4 방향 연쇄코드의 예를 그림 18 에 나타내었다.

그림 18

연쇄코드에 의한 묘사는 특정한 유형의 대상물 정합 (matching) 에 유용하다. 만일, 출반 위치가 무시된다면, 연쇄코드는 대상물 위치에 독립적이다. 또한, 연쇄코드의 미분 또는 차분 (mod 4) 결과는 대상물의 회전에 불변하기 때문에 유효하다. 미분결과는 선을 이루는 한 화소에서 다음 화소로 시계반대방향으로 회전하면서 90 도 마다 수를 셈으로서 구할 수 있다. 그림 18 의 연쇄코드에 대한 미분결과는 다음과 같다.

10000303001000103000300003000000000.

3) 다른 묘사 특징

몇가지의 다른 묘사 특징으로는 면적, 농도, 방향, 중심 (center of mass) 및 외접 사변형이 있다. 이들은 다음과 같은 방법에 의하여 결정된다.

1. 면적은 그 영역에 포함된 화소 수를 계산함으로서 주어질 수 있다.

2. 평균 영역 농도는 그 여역의 모든 화소들의 평균계조도에 일치한다. 만일 컬러화상인 경우에는 삼원색의 평균 농도로서 주어진다.

3. 영역의 중심 (center of mass) 는 벡터 위치 의 평균으로 계산될 수 있다.



4. 산점행렬 (scatter matrix) 은 영역의 근사하는 타원형이다. 이것은 다음 식처럼 영역의 중심으로부터의 평균거리로서 계산될 수 있다.



여기서 는 전치행렬을 나타낸다.

5. 최소 외접사변형은 영역의 최소 및 최대 화소위치를 통과하는 수평 및 수직선의 교점에 의해 정의되는 사각형이다.

4) 3 차원 묘사

지금까지는 주로 화상이 2 차원 묘사에 대하여 살펴보았다. 그러나 많은 응용분야에 있어서 3 차원 실상 (scene) 묘사를 위한 분석을 위한 분석이 요구되고 있다. 입체시 시스템이 사용되었을 경우에는, 이 전의 절에서 기술한 입체시 분석이 대상물의 깊이, 부피 및 거리와 같은 값을 평가하기 위하여 이용될 수 있다. 원화상으로 2 차원 화상이 사용되었을 경우에는 이와같은 정보들은 다른 방법들에 의해서 결정되어야 할 것이다.

1960 년대 초반부터 3 차원 다면체 블럭세계의 물체로 구성된 화상을 해석할 수 있는 몇몇의 프로그램이 작성되기 시작하였다 (Roberts 1965, Guzman 1969, Huffman 1972, Clowes 1971, Waltz 1975) 이러한 연구로부터 얻어진 경험에 의하여, 2 차원 화상으로부터 복잡한 다면체들을 분류하고 식별할 수 있는 알고리즘과 기법들이 유도되었다.

Roberts 는 다면체의 에지 (edge) 에 해당하는 선을 알아내는 프로그램을 작성하였다. 이 선들은 미리 저장된 모델 즉 삼각주 (wedge), 입방체 (cube), 프리즘 (prism) 과 같은 원시 물체에 대한 비교일치처리 (matching) 를 수행하기 위하여 묘사된다. 비교일치를 수행하기 위해서는 가장 잘 비교될 수 있도록 대상물의 확대/축소 (scaling), 회전 (rotation), 평행이동 (translation) 등의 변환을 할 필요가 있다. 비교일치처리가 끝나 모든 대상물들이 식별되면 프로그램은 실상의 이해 결과를 모니터를 통해서 그래픽 표현으로 나타내게 된다.

Guzman 은 동일한 물체의 표면들이 어떻게 연결되는가를 알아내는 SEE 라는 프로그램을 개발하였다. 다른 종류의 선 접합점 (정점) 간의 기하학적인 관계가 물체 종류를 결정하는 데 도움이 되었다. Guzman 은 그가 정의한 3 차원 블록 세계의 물체에서 흔히 발생하는 8 가지의 에지 접합점 (edge junction) 을 식별하였다. 이 접합점들은 그의 프로그램에서 상이한 물체들을 분류하기 위한 경험적 규칙들로서 사용되었다 (그림 19).

그림 19

Huffman 과 Clowes 는 각각 이 연구를 발전시켜 체계적으로 다면체의 분류를 실시하기 위한 선 레이블 부여 프로그램을 개발하였다. 이 프로그램에서는 에지를             (concave),            (convex) 또는 폐색선 (occluding) 중의 하나로 분류하였다.                  에지는 두 개의 인접한 표면이 서로 180° 이하의 각도로 두면의 깊이가 변화할 때 생기며, 폐색선은 다른 물체를 가로막는 표면의 윤곽이다.

        에지에는 - 부호 (minus sign) 를 부여한다.          에지에는 + 부호 (plus sign) 를 부여하며, 오른쪽 또는 왼쪽 방향을 향한 화살표 (arrow) 가 폐색선 또는 경계선에 대한 레이블 부여를 위해서 사용된다. 정점을 3 면이 교차하는 것 (3 면정점) 만으로 제한하면, 그림 20 에 나타낸 것처럼 기본적인 정점의 종류를 L, T, Fork 및 Arrow 의 4 가지 만으로 감소시킬 수 있다. 이들 4 가지의 종류의 정점에 부여된 레이블 (label) 의 상이한 조합이 대상물의 분류와 식별을 위해서 사용된다.

가능한 모든 방향으로부터 3 차원 물체를 관찰하였을 때, 4 가지 유형의 정점에 있어서 각 에지에 타당하게 레이블이 부여된 경우, 허용가능한 정점의 형태는 그림 20 에 설명한 바와 같이 18 가지가 존재한다. 이들 타당한 정점 종류를 나타내는 사전을 이용하여, 프로그램은 물체를 묘사하고 있는 정점들에 의해서 분류를 행한다. 그림 21 에 나타낸 것과 같은 존재할 수 없는 물체의 형태도 알아낼 수 있다.

일관성있는 레이블 부여 조작과 함께, 기하학적 제한조건 (geometric constraints) 들을 이용함으로써 대상물 식별 과정을 상당히 단순화할 수 있다. 다른 종류의 대상물에 대하여 이 과정을 용이하게 하기위한 일련의 레이블 부여 규칙이 개발될 수 있다. 예를 들면, 위의 레이블을 이용하여, 다음과 같은 규칙들이 많은 다면체의 대상물에 적용될 수 있다.

(1) 대상물을 시계방향으로 추적하면서 경계선을 표시하기 위한 화살표를 부여한다. (화살표의 오른쪽에 물체면이 오도록 함).

(2) 이어진 선에는 양쪽 끝에 동일한 레이블이 할당되어야 한다.

그림 20

그림 21

그림 22

(3) Fork 에 있어서 하나의 에지 (edge) 가 + 로 레이블이 부여되면, 3 개의 에지 모두가 + 로 레이블 되어야 한다.

(4) Arrow 접합에 있어서 양쪽 두 개의 에지 (barb edge) 가 → 로 레이블되면, 그 가운데의 선 (shaft) 은 + 레이블을 가져야 한다.

이러한 규칙들을 다면체에 적용한 결과를 그림 22 에 나타내었다. 오른쪽에 물체를 지닌 어떠한 에지 (edge) 에서로 부터라도 시작하여, 외부의 경계선을 시계방향으로 → 에 의해 레이블을 부여한다. 그 다음에 내부의 선들을 다른 레이블 부여 규칙에 의거하여 + 또는 - 에 의하여 레이블을 부여하게 된다.

 

5) 제한조건의 만족 방법 (Constraint Satisfaction) 에 의한 필터링

위와 같은 초창기의 연구에 이어서, David Waltz 는 특정한 부류의 물체에 허용가능한 정점의 종류를 설정해 나가는 정점 제한조건의 전파 (vertex constraint propagation) 에 의한 방법을 개발하였다. 그는 조명 조건을 완화하고 그림자, 여러개의 선으로 구성된 몇가지의 접함점 및 다른 종류의 내부선을 수용할 수 있도록 레이블 용어를 확장함으로서 해석가능한 화상의 종류를 늘렸다. 제한조건의 만족 알고리즘은 그의 중요한 업적중의 하나이다.

이 과정이 어떻게 진행되는가를 알아보기 위해서 그림 23 에 설명된 것과 같은 피라미드 (pyramid) 의 그림을 고려하자. 피라미드의 오른편에는 4 개의 정점 A, B, C, D 에 부여될 수 있는 모든 레이블들이 나타나 있다.

그림 23

이러한 레이블들을 연결된 접합점이 상호 제한조건으로 이용하여, 전체 피라미드에 허용가능한 레이블들을 결정할 수 있다. 제한조건의 만족에 의한 처리는 다음과 같이 진행된다.

1. 임의의 접합점 (예를 들어 A) 에서 출발하여, 그 접합점에 허용될 수 있는 모든 레이블들을 기록한다. 다음에 인접함 접합점 (예를 들어 B) 이 선택되고, A 와 B 의 허용될 수 있는 레이블의 리스트에서 선 AB 에 존재할 수 없는 레이블을 제거한다. 이 경우에 B 와 결합된 선에는 +, - 또는 위로 향하는 화살표 → 만이 부여될 수 있다. 결국, A 의 레이블 중에서 두 개가 제거되고 나머지 4 개는 다음과 같다.

2. 다음에 접합점 C 를 선택하면, B 와 C 의 모든 레이블이 BC 이 제한조건을 만족하는 것을 알 수 있다. 따라서 이 단계에서는 아무런 축소가 없다. 그러나, 선 AC 는 모순되지 않도록 - 또는 왼쪽위로 향하는 화살표 ← 로서 레이블되어야 한다. 따라서, A 에서 부가적으로 하나의 레이블이 제거될 수 있고 남는 것은 다음과 같다.

3. 새로운 A 에 대한 제약에 의하여, 일관성을 유지하기 위해서 B 에서 하나의 레이블이 제거된다. 이리하여 허용가능한 B 의 레이블은 다음과 같이 남게 된다.

이 축소는 다시, BC 의 새로운 제약으로 작용하여, C 의 레이블 중에서 하나를 제거하게 되고, BC 는 오직 + 레이블 하나만을 지닐 수 있게 된다. C 의 나머지 레이블은 다음과 같다.

4. 이제 접합점 D 로 이동하면, 6 가지의 가능한 레이블이 있다는 것을 알 수 있고, 그중에서 BD 의 제한조건인 - 또는 아래방향 화살표 → 를 만족하는 것은 3 가지 뿐이다. 그러므로 D 에 허용가능한 레이블은 다음과 같다.

위와 같은 처리를 계속하면, 모든 제약조건이 만족하게 되고 더 이상의 레이블 제거가 불가능하다는 것을 알 수 있다. 위의 처리는 그림에 할당될 수 있는 서로 다른 형식의 레이블 부여 조합들이 모두 발견되었을 때 완성된다. 이는 트리 탐색 과정을 통하여 이루어질 수 있다. 위의 예에서 단순히 마지막까지 남는 레이블들을 열거하면, 오직 3 가지의 다른 형식의 레이블 부여가 가능한 것을 알 수 있다. 이 레이블 부여 과정을 이 장의 연습문제로서 남겨 두었다.

6) 형판 비교일치 (Template Matching)

형판 비교일치 (template matching) 는 화상에서 발견되는 패턴 (pattern) 을 이미 알려진 저장된 형판 (template) 과 비교하는 처리이다. 비교일치처리는 낮은 단계 (low-level) 에서는 각 화소 또는 화소 그룹간의 상관 (correlation) 기법을 이용하여 행할 수도 있고, 높은 단계 (high-level) 에서는 레이블이 부여된 영역구조를 이용할 수도 있다. 대상물과 형편간의 비교는 완전한 또는 부분적인 정합에 기초할 수 있다. 즉, 비교일치처리에 있어서 두개를 비교할 때 전체 또는 부분 조각들을 이용할 수 있다. 또한, 고정된 (rigid) 또는 유동적 (flexible) 인 형판이 사용될 수도 있다 (유동적 형판 비교일치의 예는 부분 매칭에 기술되어 있으며, 거기에 rubber mask 형판의 개념이 소개되어 있다).

형판비교일치는 탐색처리가 어떤 방법으로든지 제한되어 있을 때만 효과적일 수 있다. 예를들어, 실상 (scene) 의 종류와 존재할 수 있는 대상물들이 미리 알려지게 되면, 가능한 패턴-형판의 쌍 (pattern-template pairs) 들이 한정된다. 어떤 형식의 정보가 주어지는 탐색방법을 사용하면 탐색공간의 크기를 제한하는데 도움이 될 수도 있다.

5. 높은 단계 처리 (High-Level Processing)

비젼처리 (vision processing) 에 있어서 마지막 단계 (높은 단계 처리) 의 논의를 진행하기 전에, 지금까지의 처리 단계들을 간단히 뒤돌아 보기로 한다. 우리는 흑백 또는 컬러화상으로부터 시작하여, 화소값의 정수배열을 얻기 위해 이를 디지탈화 하였다. 다음은, 마스크 (mask) 또는 몇몇 변환 (Fourier 와 같은 ) 을 이용하여 잡음이나 불필요한 특징들의 영향을 감소시키기 위한 평활화와 에지 강조처리를 하였다. 이어서 화상을 동질의 영역들로 구분하고 분할하기 위한 에지추출을 하게 된다. 이 단계의 산출물은 대상물들의 기초 스케치 (primal sketch) 이다. 이원적 에지 추출처리인 영역의 분리/합병 (splitting and/or merging) 기법이 독립적으로 또는 함께 분할 (segmentation) 처리의 일부분으로서 에지를 발견하기 위하여 사용될 수 있다.

농도 히스토그램의 계산과 뒤이은 분석들은 분할처리의 중요한 일부분이다. 히스토그램은 대상 분리를 위한 실마리를 제공하는 임계치 (threshold levels) 의 설정에 도움이 된다. 최소 스패닝 트리나 동적 프로그래밍과 같은 기법들이 이들 초반처리단계 (early processing stage) 에서 에지 발견을 위하여 사용되기도 한다.

분할처리에 이어서, 영역들이 분석되고 그들이 지닌 특성에 의하여 레이블이 부여된다. 중간 단계처리 (intermediate-level processing) 의 최종적인 결과는 영역 묘사들의 집합 (데이타 구조) 이다. 이러한 구조들은 마지막 높은 단계 (high-level) 화상처리의 입력으로 사용된다. 가장 낮은 처리 단계로부터 가장 나중에 해석 단계에 이르기까지의 산출되는 데이타 구조는 다음과 같이 요약 설명될 수 있다.

1) 비젼에 있어서 Marr 의 이론 (Marr's Theory of Vision)

David Marr 와 그의 동료들은 처리의 각 단계에서 사용되는 표현 scheme 에 중요성을 강조한 비젼의 한 이론을 제안하였다 (1982, 1980, 1978). 그의 제안은 위에서 설명한 바와 같이 처리가 몇몇 단계로 나뉘어 수행된다는 가정에 기초하고 있다. 이들 단계들과 각 단계의 표현법은 다음과 같다.

1. 계조도 화상 (gray level image, 흑백화상)  가장 낮은 차원의 처리는 화상 농도의 2 차원 배열상에서 구성된다. 이 농도치들은 실세계 대상물의 물리적 성질, 조명, 관찰자에 대한 표면 방향, 기하학 표면 반사율 및 대상물의 불연속성 등에 해상한다. 이 단계의 처리는 암시적인 구조에만 의거한 국소적인 처리이다. 이 수준에서의 표현의 주된 관점은 국소적, 1 차 통계적인 변환을 용이하게 하는 데에 있다.

2. 기초 스케치 (raw primal sketch) 기초 스케치는 대상물의 특징을 더욱 가시적이고 명시적으로 2 차원 표현한 것이다. 이것은 에지 조각 (edge segment), 농도변화 및 텍스쳐와 같은 국소적 특징들로 구성된다. 이 단계에서와 표현은 가시적인 화상 묘사를 강조하고 표면 특징과 크기를 기술하는 다음 단계로의 변환을 용이하게 하는데 중점을 둔다.

3. 2 1/2 차원 스케치 (2 1/2 dimentional sketch) 이 스케치는 관찰자 중심의 좌표계에 있어서 대상물을 3 차원의 명시적인 표현을 취한 것이다. 여기서의 모델들은 거리, 크기, 표면 구조와 같은 것이다. 3 차원 공간으로의 재구성을 위해서는 전에 기술한 바와 같은 입체시, shape contour, shape from shading and texture 및 다른 도구들의 이용이 필요하게 된다.

4. 3 차원 모델     3 차원 모델 단계에서의 표현은 실상 (scene) 의 속성, 관계 및 기하학적인 묘사를 나타내는 기호적인 것들이다. 일반화된 원추 (cones) 나 원통 (cylinders) 의 사용은 많은 물체의 표현에 도움이 되며, 이들의 계층적 묘사가 처리를 용이하게 한다.

2) 높은 단계 처리 (High-Level Processing)

높은 단계 (high-level) 처리의 기법들은 이전의 화상처리 단계들에 비하여 기계적이 아니다. 이들은 고전적인 AI 기법인 기호적 기법들과 더욱 밀접하게 관련되어 있다. 높은 단계 처리에 있어서는 중간 단계 (intermediate-level) 에서의 영역묘사가 제 2 부에서 설명한 것과 같은 지식표현 기법을 이용하여 높은 단계의 실상 묘사 (scene description) 로 변환된다 (연관망, 프레임, FOPL 문장 등, 그림 24 참조).

그림 24

이 단계의 최종 목적은 추론 프로그램에서 사용할 수 있는 높은 단계의 지식구조를 생성하는 것이다. 말할 필요도 없이, 결과로서 얻어진 구조들은 화상에서의 중요한 대상물들을 그들의 내부 관계를 포함하여 유일하게 또한 정확하게 기술하고 있어야 한다.

실상 묘사 문제를 해결하기 위한 접근방식은 여러 가지가 있다. 극단적인 경우에는, 실상에서의 특정 대상물을 분류하기 위하여 단지 패턴 인식수법을 적용하는 것만으로 충분할 수도 있다. 이 경우에는 이전의 장에서 기술한 수법들의 응용이 더 이상 필요없게 된다. 또 다른 극단적인 경우에는, 일반적인 실상에 대한 상세한 묘사가 이루어져서, 대상물들의 기능, 목적, 의도 및 기대 (expectation) 와 같은 해석까지 제공하는 것이 바람직할 경우도 있다. 비록, 이러한 요구들이 현재까지의 최신 기술로서도 실현 불가능한 일이지만, 많은 양의 미리 저장된 패턴 묘사들과 일반 상식들이 필요하다는 점을 말할 수 있다. 또한, 이 장에서 기술된 화상처리 기법들의 개선도 필요할 것이다.

실상 (scene) 을 높은 단계에서 사용되는 구조의 형태로 묘사하기 전에, 대상물들에 대한 모델 묘사 (model description) 가 미리 저장되어 있어야 한다. 이 모델묘사들은 중간 단계 처리중에 생성된 영역묘사들과 비교되어진다. 이를 위한 비교일치 (matching process) 는 규칙 예시 (rule instantiation), 분할 그래프 또는 망의 정합, 프레임 예시, 판별망 (결정 트리) 의 탐색 등을 통하여 이루어질 수 있다. 비교일치처리의 종류는 최종 구조에서 채택한 표현 scheme 에 자연스럽게 영향을 받게 된다.

이 절을 마무리 하기 위해서, 높은 단계 처리에서 사용되는 몇가지 접근방법에 대해서 고려하도록 한다. 한편, 몇 가지 완전한 비젼 시스템에 대해서는 다음 절에서 살펴보기로 한다.

연관망 (associative network) 은 대상물의 관계를 그들의 특징과 함께 잘 보여주기 때문에 실상 묘사를 위해서 자주 사용되는 표현 scheme 이 되었다. 옥외의 실상 (outdoor scene) 을 표현하기 위한 간단한 예가 그림 25 에 설명되어 있다.

이와 같은 실상의 묘사는 그림 16 에서 보인 것과 같은 유형의 영역 묘사를 해석함에 의해서 형성될 수 있다. 해석을 위한 지식은 생성규칙 또는 다른 표현 scheme 을 사용하여 부호화될 것이다. 예를 들어, 옥외 컬러 화상에 있어서 하늘 영역을 식별하기 위한 규칙은 농도, 색상, 모양 등과 같은 하늘이 지닌 성질들에 의해서 예시되어진다. 항공사진에 있어서 집을 식별하기 위한 규칙은 그림 26 에 설명한 것 같은 면적, 밀집도, 텍스쳐, 경계의 종류 등이 조건들과 예시되어질 수 있다. 규칙의 조건부는 절대적인 것보다도 유사한 또는 부분적인 정합을 허용하기 위해서 애매함 (fuzzy) 이나 확률론적 (probability) 인 서술을 지닐 수도 있다. 규칙의 결론부에는 완벽한 환신 대신에 우도 (likelihood) 나 확신을 (certainty factor) 의 등급이 매겨질 수도 있다. 그리고 대상물의 식별은 우도값 (likelihood score) 에 기초하여 이루어진다. 그림 26 의 조건부에 주어진 한 쌍의 숫자는 Dempster-Shafer 확률과 동등한 수용가능한 조건의 범위를 나타내고 있다 (그림에서의 값들은 0 과 1.0 사이에서 임의로 선택되었음).

그림 25

Interpretation rules for a sky and a building.

그림 26

규칙 기반의 식별 시스템이 사용될 경우에는, 비젼시스템에 각 영역을 식별하기 위한 초기의 목표가 주어지게 된다. 이것은 다음과 같은 형식의 높은 단계의 목표 문장에 의해서 이루어질 수 있다.

해석에 있어서 다른 형식의 비교일치처리 (matching) 가 사용될 수도 있다. 예를들어, 결정트리 (decision tree) 가 이용될 수 있는데, 여기에는 트리를 탐색해 내려갈 때 각 노드에 붙여진 가지를 결정하기 위해 사용되는 영역의 속성과 관계 등에 해당하는 값이 부여되어 있다. 결정트리의 잎에는 그림 27 처럼 물체 식별을 위한 레이블이 부여되어 있다.

그림 27

대상물들이 그들의 속성 및 관계와 함께 연관망, 프레임 망 또는 다른 구조를 만들기 위해서 사용된다.

6. 비젼 시스템 구조 (Vision System Architecture)

이 절에서는 비교적 완전한 시스템 구조를 갖추고 있는 2 가지의 대표적인 비젼 시스템을 나타내었다. 첫 번째의 시스템은 가장 초기의 성공적인 비젼 시스템으로, 모델기반 (model-based) 시스템이다. 두 번째는 최근에 일본 교오토대학에서 개발된 컬러 영역 분석기 (color region analyzer) 이다.

1) ACRONYM 시스템

ACRONYM 시스템은 응용 분야에 구애받지 않는 모델기반 (model-based) 시스템으로, 1970 년대 말에 Stanford 대학의 Rodney Brooks (1981) 에 의해서 개발되었다. 이 시스템은 사용자가 정의한 일련의 대상물에 대한 묘사를 모델 또는 패턴으로 받아 들여서, 단안시 (monocular) 에 의한 화상에 나타난 구조를 식별하는 데에 사용한다. 그림 28 에 이 시스템의 주요 구성요소에 대해 나타내었다.

그림 28

사용자는 대상물 또는 일반적인 대상물 클래스와 그들간의 공간적 관계 및 부클래스 (subclass) 와 관계를 LISP 문장의 형태로 묘사한다. 예를들어, 길이가 1 에서 10 인치 사이인 드라이버 (screwdrivers) 의 클래스를 모델화하기 위한 묘사는 다음과 같다.

사용자가 묘사한 것은 시스템에 의해서 기하학적 (geometric) 및 대수학적 (algebraic) 망 표현으로 파싱 (passing) 되고 변환된다. 이들 표현은 국소 좌표계에 있어서 3 차원적 묘사로의 변환이 가능하다. 사용자에 의해서 생성된 입력 모델에 대한 시스템의 해석 결과는 그래픽으로 표현되어 모델링 과정동안에 사용자 피드백 (feed back) 된다. 완전하게 정의된 표현들은 입력화상으로부터 어떠한 종류의 모델화된 대상물의 특징 (모양, 방향, 위치 등) 들이 관찰되는가를 예측하기 위해서 시스템에 의해 사용된다. 예측된 모델들은 예측그래프 (prediction graph) 로서 저장된다.

입력화상의 처리는 계조도 화상처리기 (gray-level image processing arrays), 선 추출기 (line finder) 및 에지연결기 (edge linker) 로 구성된다. 시스템에 있어서 이 부분은 분할된 에지 구조로서 정의된 대상물 묘사를 제공하게 된다. 여기서 생성된 묘사는 관측그래프 (observation graph) 로서 표현된다. 예측기 (predictor) 로 부터의 하나의 출력은 에지 사상 및 연결 모듈 (edge mapping and linking module) 의 입력이 된다. 이것은 예측된 정보 (모델화된 대상물로부터 예측된 에지, ribbon, 타원 등) 를 입력화상에 나타난 물체의 탐색과 식별에 도움을 주기 위해서 사용한다. 예측기 (predictor) 와 에지 사상 및 연결기 (edge mapper and linker) 로부터의 출력은 해석기 (interpreter) 의 입력으로 사용된다. 해석기는 본질적으로 하나의 그래프 비교일치기 (graph matcher) 이다. 이것은 화상 관측그래프 (observation graph) 의 부분그래프 중에서 예측 그래프 (prediction graph) 와 가장 잘 일치하는 것을 발견한다. 정합결과에 의해 해석그래프 (interpretation graph) 가 만들어 진다. 부분적인 정합 결과는 해석과정 중에 일관성 검사에 의해서 조정된다.

기본적인 해석처리가 그림 29 에 요약되어 있다. 여기에서 모델은 동체가 큰 두 종류의 비행기 (Boeing 747 과 Lockheed L-1011) 이고, ACRONYM 에 의한 계조도화상의 해석 결과를 나타내었다.

그림 29

2) Ohta 의 컬러 실상 분석기 (Color Scene Analyzer)

쿄오토대학의 Yuichi Ohta 는 최근 옥외의 컬러 실상 (outdoor color scene) 에 대해 영역 분석을 수행하는 비젼시스템을 개발하였다. 옥외 실상에는 전형적으로 나무, 잡목, 하늘, 도로, 건물과 에지 보다는 영역에 의해서 더욱 자연스럽게 정의되는 물체들이 포함되어 있다. 이 시스템에서는 분할처리에 있어서 색상 (color) 이 유효한 역할을 수행할 수 있도록 하고 있다.

3 가지의 색상 배열 (red, green, blue) 에서 시작하여, 디지털화된 화상이 생성되고, 이로부터 분리 (splitting) 에 의한 분할에 의해 영역들이 정의된다. 분할처리의 출력은 영역들을 보통 숫자로 구성된 화소역들로 구분한 2 차원 배열이다. 이 배열은 경계선 조각, 정점 (vertices) 과 같은 영역을 묘사하는 요소를 포함하는 구조적 자료망 (structured data network) 으로 변환된다. 이 망과 생성규칙의 형태로 저장된 모델 지식을 이용하여 실상에 대한 의미 묘사 (semantic description) 를 구성하게 된다. 그림 30 에 시스템에 의해서 수행되는 주요처리 단계들을 설명하였다.

그림 30

예비 분할단계 (preliminary segmentation stage) 에서는 색상 정보에 기초한 영역분리 방법을 이용하여 화상을 동질의 영역들로 분할한다. 다중 히스토그램 (multihistogram) 이 임계치 처리와 영역분리를 위한 실마리를 제공한다. Karhunen-Loeve 변환 결과에 기초하여 최대의 판별력 (본질적으로 최대 분산) 을 지닌 색상 특징들이 선택된다 (Devijver and Kittler, 1982). 이들 분할된 영역들이 원소 요소가 되고, 이로부터 구조적 자료망이 구축된다.

영역들은 그들의 경계선 조각, 정점, 선분, 구멍 (hole) 등에 의해서 특성지워진다. 이들 기본적인 묘사요소들은 예비분할 단계에서 형성된다. 이들로부터 면적, 평균 색상 농도, 텍스쳐, 윤곽선 길이, 중심위치, 구멍의 개수, 외접 사변형, 원점으로부터의 거리, 방향과 같은 다른 특징들이 유도된다. 이들과 영역간의 관계가 패치자료구조 (patchery data structure) 로서 알려진 자료 구조에 의하여 기술된다. 자료망에 있어서의 요소들은 본질적으로 생성규칙의 형태로 기술된 모델과 지식이 비교된다. 다음으로 규칙이 기동하게 되면 실상의 묘사가 효과적으로 이루어진다.

계획 (plan) 은 대상물의 레이블과 그들의 정확도가 주어진 입력 실상이 가공되지 않은 표현이다. 이것은 실상에 있어서 상이한 부분들에 적용될 수 있는 지식에 관련된 실마리를 제공하기 위해 상향식으로 생성된다.

문제분야에 대한 지식은 일련의 생성규칙으로 표현된다. 이들 중에 하나의 집합은 상향식 처리에서 이용되고 다른 집합은 하향식 처리에서 사용된다. 상향식 집합 (bottom-up set) 에 포함된 각 규칙들은 대상물간의 관계에 있어서의 성질을 나타내기 위한 퍼지서술 (fuzzy predicate) 을 지니고 있다. 또한, 규칙에는 지식의 불확실성 정도를 나타내기 위한 가중치가 부여되어 있다. 하향식 집합 (top-down set) 에 있는 각 규칙은 조건-행동 쌍 (condition-action pair) 으로 구성되어 있고, 조건부는 데이터베이스의 상황을 시험하기 위한 퍼지서술로 되어 있다. 행동부에는 실상 묘사 (scene description) 를 구축하기 위한 조작들이 포함되어 있다. 일정표 (agenda) 가 생성규칙의 활성화를 관리하고, 실행가능한 행동을 계획한다. 특성 규칙 (property rule) 과 관계 규칙 (relation rule) 의 전형적인 예는 다음과 같다.

첫 번째 규칙은 하늘 색 (blue or gray) 에 대한 특성 규칙이다. 두 번째의 규칙은 건물과 하늘 사이의 경계에 관한 관계규칙이다. 둘 사이의 경계에는 많은 선 부분이 있고, 건물은 그 경계의 위에 있지 않다는 것을 나타낸다.

분석기의 마지막 선출물은 물론 실상의 묘사이다. 이것은 그림 31 에 설명한 바와 같이 계층적인 망으로 구성된다.

Ohta 의 시스템은 부분구조를 지닌 물체를 포함한 상당한 복잡한 실상에 대한 처리도 가능하다는 것을 주장하였다. 이것을 증명하기 위해서, 쿄오토 대학 캠퍼스의 많은 옥외 실상들이 정확하게 시스템에 의해 분석되었다.

그림 31

7. 요약

컴퓨터 비젼은 계산 집약적인 처리이다. 이것은 낮은 단계의 화소 배열로부터 시작하여 높은 단계의 실상 묘사 (scene description) 에 이르기까지 많은 변환을 포함하고 있다. 변환처리는 처리의 3 단계로서 살펴볼 수 있다. 즉, 낮은 또는 초반단계 (low-or early-level) 처리, 중간단계 (intermediate-level) 처리 및 높은 또는 후반 단계 (high-or late-level) 처리가 그것이다. 낮은 단계 처리는 수많은 원시 계조도 (또는 삼원색) 화소들로부터 구조를 발견하기 위한 작업들과 관련되어 있다. 이 단계의 목표는 본래의 실상 (scene) 에서 구분되는 각 대상물에 해당하는 균질한 영역들로 분할하는 데 충분한 구조들을 원 화상으로부터 발견하고 정의하는 것이다. 중간 단계 처리는 분할된 영역들을 정확하게 형성하고 묘사하는 작업들과 관련되어 있다. 이 단계의 원시 요소는 영역 (region) 과 부영역 (subregion) 들이다. 마지막으로, 높은 단계 처리에서는 중간 단계 처리에서 만들어진 분할 영역들을 실상 묘사로 변환할 필요가 있다. 이 단계의 처리는 이전의 두 단계에 비하여 덜 기계적이고, 고전적 AI 기법인 기호처리에 더욱 의존한다.

낮은 단계 처리에는 보통 디지털 화상배열에 대한 평활화 (smoothing) 조작을 포함하고 있다. 평활화는 잡음이나 바람직하지 않은 특징들을 감소하는데 도움이 된다. 다음으로는 화상배열에 차분 연산자 (difference operator) 와 같은 것을 응용한 에지 추출작업이 이어지게 된다. 그 후, 대상물을 나타내는 연속적인 윤곽선을 형성하기 위해서 에지의 절편들이 연결된다. 이 조작을 위해서 다양한 기법들을 이용할 수 있다.

영역 분리 (region splitting), 영역 확장 (region growing) 또는 이 두수법의 결합에 의한 이중의 에지 추출조작 (dual-of-the-edge-finding) 은 영역분할을 도와준다. 다중 히스토그램 (multihistogram) 과 임계치처리 (thresholding) 는 분할처리에 일반적으로 이용되는 처리들이다. 균일한 영역을 정의하기 위해서 이들 처리가 한 개 이상의 화상특징에 대해 적용될 수 있으며, 이러한 특징으로는 농도, 색상, 텍스쳐, 그림자, 광류 (optical flow) 등이 있다. 분할처리의 마지막 산물은 균질한 영역들이다. 높은 수준의 처리단계에서 식별될 수 있도록 이들 영역의 특성과 상호 관계가 기술되어져야 한다. 영역들은 경계선 요소, 정점 (vertices), 구멍 수, 밀집도 (compactness), 위치, 방향 등에 의해 기술될 수 있다.

마지막 단계는 영역들이 해석되고 설명되는, 지식의 응용단계이다. 여기에는 일반 세상에 대한 지식과 함께 문제분야에 특수한 지식이 필요하다. 컴퓨터 비젼에 있어서 현재의 최신기술로도 그림 1 에 설명한 것과 같은 임의의 복잡한 실상 (scene) 에 대한 해석은 어렵다. 이를 인식하기 위해서는 아직 해결해야 할 많은 과제가 남아 있다.