제 11 장 단순한 형태의 패턴 검출.

Presentation on theme: "제 11 장 단순한 형태의 패턴 검출."— Presentation transcript:

1 제 11 장 단순한 형태의 패턴 검출

2 단순한 형태의 패턴 검출 사각형, 삼각형, 원 등의 단순한 형태의 패턴 검출 패턴 검출 과정
윤곽선의 기하학적 특징을 이용하여 검출 가능 정사각형 4개의 선분으로 구성 사이각이 90도 선분의 길이가 동일 패턴 검출 과정 윤곽선 검출  선분으로 근사화  기하학적 특징 추출  패턴 판별 영상처리

3 윤곽선 검출 바깥 윤곽선과 안쪽 윤곽선 영상처리

4 윤곽선 검출 픽셀 탐색에 의한 윤곽선 검출 단계 1 - 윤곽선 검출의 시작점 탐색
영상의 맨 윗줄의 좌측에 있는 픽셀부터 시작하여 오른쪽방향으로 스캔하면서 다음의 두 조건을 만족하는 픽셀 P(x, y)를 선택    1) P(x, y)의 값이 물체의 색과 일치     2) P(x, y) 바로 위의 픽셀이 배경 픽셀이거나 P(x, y)가 맨 윗줄에 있는 픽셀 영상처리

5 윤곽선 검출 P(2,1)이 조건을 만족하여 시작점으로 선택됨 1 2 3 4 5 255 영상처리

6 윤곽선 검출 단계 2 - 인접한 가장자리 픽셀 탐색 픽셀 P(x, y)가 가장자리 픽셀일 경우에 인접한 가장자리 픽셀은 픽셀 P(x, y) 주위의 8개 픽셀 중에 존재    1) 인접 픽셀중의 한 픽셀에서 검사를 시작    2) 픽셀값이 배경색이면 계속해서 다음 픽셀을 검사 픽셀값이 물체색이면 그 픽셀을 인접한 가장자리 픽셀로 정하고 검사를 멈춤  8개의 픽셀의 값을 어느 픽셀부터 검사를 시작해야 할 것인지와 어떤 순서로 검사해야 할 것인가가 중요  본 교재 바깥쪽 윤곽선 : 시계 방향으로 탐색 안쪽 윤곽선 : 반시계 방향으로 탐색 영상처리

7 윤곽선 검출 픽셀 번호 인접 픽셀 검사 순서 시계 방향으로 탐색 7 1 6 P(x, y) 2 5 4 3 2018-09-22
1 6 P(x, y) 2 5 4 3 영상처리

8 윤곽선 검출 시작점의 경우 0번 부터 시작하여 시계 방향으로 탐색하면 이웃한 경계 픽셀을 만나게 됨 255 255 255
255 255 255 255 영상처리

9 윤곽선 검출 인접 픽셀의 검사 시작 위치 현재까지 가장자리 픽셀을 탐색해온 방향에 따라 다르게 결정 가장자리 픽셀 발견 위치
다음 검사 시작 위치 7 1 2 3 4 5 6 영상처리

10 윤곽선 검출 영상처리

11 윤곽선 검출 영상처리

12 윤곽선 검출 단계 3 - 탐색 종료 더 이상 연결된 가장자리 픽셀이 없는 경우 탐색의 시작점을 만나는 경우 2018-09-22
영상처리

13 선분으로의 근사화 필요성 간단한 도형을 훨씬 더 용이하게 검출 윤곽선의 표현이 보다 간결해지고 데이터의 양도 줄어듬
255 0  윤곽선 픽셀 = { (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 2) } 윤곽선 선분의 정점 = { (1, 1), (3, 1), (3, 3), (1, 3) } 영상처리

14 선분으로의 근사화 Douglas-Peucker 알고리즘 윤곽선의 점들 중에서 가장 먼 거리에 있는 두 점을 발견
가장 먼 거리에 있는 두 점을 기점으로 윤곽선을 두 개의 조각으로 분할하여 스택에 저장 스택이 비워질 때까지 다음 과정을 반복 i) 스택으로부터 윤곽선 조각 하나를 가져온 다음에 그 길이를 검사 ii) 윤곽선 조각을 구성하는 점의 수가 2개이면 그 윤곽선 조각은 선분으로 출력 iii) 윤곽선 조각을 구성하는 점의 수가 2개 보다 많은 경우에는 그 조각의 점들 중에서 그 조각의 양 끝점 A와 B를 잇는 선분 AB로부터 가장 먼 거리에 있는 점 C를 발견 iv) 선분 AB와 점 C 사이의 거리가 임계값 이하이면 A와 B 사이의 윤곽선을 선분 AB로 근사화하고 그렇지 않으면 점 C를 기점으로 윤곽선을 2개로 분할하여 스택에 저장 영상처리

15 선분으로의 근사화 윤곽선의 점들 중에서 가장 먼 거리에 있는 두 점을 찾는 방법
임의의 한 점에서 시작하여 그 점에서 제일 먼 점을 찾음 앞에서 발견된 점으로부터 제일 먼 점을 다시 찾음 2번 과정을 더 이상 두점 사이의 거리가 늘어나지 않을 때까지 반복 영상처리

16 선분으로의 근사화 P(2,1)에서 시작하여 가장 멀리 있는 두점을 찾으면 P(1, 1)과 P(3, 3)이 선택됨
S1 = < (1, 1), (2, 1), (3, 1), (3, 2), (3, 3) > S2 = < (3, 3), (2, 3), (1, 3), (1, 2), (1, 1) > 255 0  영상처리

17 선분으로의 근사화 조각의 양 끝점을 지나는 직선으로부터 가장 먼 거리에 있는 점
점과 직선 사이의 거리를 구하는 공식을 이용하여 발견 영상처리

18 선분으로의 근사화 윤곽선 조각 양 끝점의 좌표가 일때에 두 점을 지나는 직선의 방정식
윤곽선 조각 양 끝점의 좌표가 일때에 두 점을 지나는 직선의 방정식 윤곽선 조각 직선과 점 (x0, y0) 거리 영상처리

19 선분으로의 근사화 다음의 윤곽선 조각 S1 = < (1, 1), (2, 1), (3, 1), (3, 2), (3, 3) > 가장 멀리 있는 점 점 (3, 1) : 윤곽선 조각 직선사이의 거리 = 1.414 임계값 응용에 따라 달라질 수 있음 여기에서는 임계값으로 윤곽선 조각 길이에 0.1을 곱한 값 사용 여기에서는 윤곽선 조각 길이를 픽셀수로 사용 S1의 길이 = 5 임계값 = 0.5 윤곽선 조각 분할 : 거리(1.414) > 임계값(0.5) S3 = < (1, 1), (2, 1), (3, 1) > S4 = < (3, 1), (3, 2), (3, 3) > 255 0  영상처리

20 선분으로의 근사화 다음의 윤곽선 조각 S3 = < (1, 1), (2, 1), (3, 1) >
분할되지 않고 하나의 선분으로 근사화 가장 먼 거리 = 0 임계값 = 0.3 S2 = < (3, 3), (2, 3), (1, 3), (1, 2), (1, 1) > 다음의 두 조각으로 분할 S5 = < (3, 3), (2, 3), (1, 3) > S6 = < (1, 3), (1, 2), (1, 1) > S5, S6은 선분으로 근사화 영상처리

21 기하학적 특징 추출 다음과 같은 기하학적 특징을 이용하여 단순한 패턴 검출 가능 윤곽선 길이 윤곽선 내부 면적 원형 지수
물체의 무게 중심 선분 사이의 각도 영상처리

22 기하학적 특징 추출 윤곽선 길이 영상처리

23 기하학적 특징 추출 윤곽선 내부 면적 계산 N-각형의 각 정점의 좌표가 연결되어 있는 순서대로 다음과 같은 경우
다각형 내부의 면적은 다음과 같이 계산 영상처리

24 기하학적 특징 추출 앞의 공식에 의한 아래 사각형의 면적 계산 영상처리

25 기하학적 특징 추출 원형 지수 완벽한 원의 원형 지수 = 1 가장 원과 먼 경우의 원형 지수 = 0 계산 식
255 0  A = 4, l = 8, C = 0.785 영상처리

26 기하학적 특징 추출 몇가지 도형에 대한 원형 지수 영상처리

27 기하학적 특징 추출 물체의 무게 중심 255 0  위 식을 적용하면 무게중심 = (2, 2) 영상처리

28 기하학적 특징 추출 선분 사이의 각도 사이각을 구하려는 두 선분 벡터를 이용한 표현 영상처리

29 기하학적 특징 추출 사이각 계산 공식 유도 영상처리

30 기하학적 특징 추출 사이각 계산 예 (라디안)  일반각으로 변환하면 90도 영상처리

31 단순한 패턴 검출 입력 영상 예 영상의 이진화 영상 분석을 용이하게 하기 위해 이진화 필요
배경색과 물체색를 구분하는 임계값이 일정하지 않음 영상을 분석하여 자동으로 임계값을 발견 여러 임계값을 사용하여 이진 영상을 생성 영상처리

32 단순한 패턴 검출 이진화 예 영상처리

33 단순한 패턴 검출 윤곽선 검출 결과 영상처리

34 단순한 패턴 검출 선분으로 근사화한 후에 기하학적 특징을 이용하여 패턴 검출 삼각형 검출 결과
구체적인 방법은 교재의 실습 내용 참조 삼각형 검출 결과 영상처리