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

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

윤곽선 검출 바깥 윤곽선과 안쪽 윤곽선 2018-09-22 영상처리

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

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

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

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

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

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

윤곽선 검출 2018-09-22 영상처리

윤곽선 검출 2018-09-22 영상처리

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

선분으로의 근사화 필요성 간단한 도형을 훨씬 더 용이하게 검출 윤곽선의 표현이 보다 간결해지고 데이터의 양도 줄어듬 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) } 2018-09-22 영상처리

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

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

선분으로의 근사화 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  2018-09-22 영상처리

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

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

선분으로의 근사화 다음의 윤곽선 조각 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  2018-09-22 영상처리

선분으로의 근사화 다음의 윤곽선 조각 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은 선분으로 근사화 2018-09-22 영상처리

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

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

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

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

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

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

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

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

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

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

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

단순한 패턴 검출 이진화 예 2018-09-22 영상처리

단순한 패턴 검출 윤곽선 검출 결과 2018-09-22 영상처리

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