집밖은 위험해

민시프트

- 클러스터링 알고리즘 중 하나

- 파젠창 방식 : 각점에 대한 샘플의 확률들을 구함

- 초기점을 지정하고, 커널 안에서 같은 분류에 속하는 점들의 방향으로 따라감

- 장점

 1) kmeans 같은 군집화 알고리즘과 달리 군집 개수를 알 필요 없음. 자동으로 군집 개수 찾음

 2) kmeans 같은 알고리즘은 일정 형태의 분포를 가정하여 변수들을 추정하는 모수적 방법

  <-> 민시프트는 임의의 분포에서 찾음. 비모수적 방법

 3) 필요한 파라미터가 커널의 폭 h뿐임

=> 얼굴 추적, 영상 검색 등 많이 활용

다른 대표적인 군집화 알고리즘

- kmeans

- DBSCAN

kmenas

- 유명한 군집화 알고리즘 중 하나

1) 군집 개수를 지정

2) 군집 개수만큼 임의의 중심점들을 생성

3) 중심점과 점들 사이의 거리로 점들의 소속 중심점 분류

4) 소속 중심점들의 평균 위치로 중심점을 이동

5) 반복하면 처음 지정한 군집개수만큼 분류 완료

- 장점 : 빠름

- 단점 : 군집 개수 지정해야함, 임의의 중심점으로 초기화하므로 매번 결과가 다를수 있음

DBSCAN Density Based Spatial Clustering of Application with Noise

1) 임의의 시작점에서 시작

2) 거리 엡실론에 속하는 이웃들을 추출.

3) 이 이웃들이 충분히 있으면 클러스터링 수행. (노이즈 샘플이라) 충분히 존재하지 않는 부분에는 클러스터링 x

4) 반복하면 하나의 클러스터가 완료

5) 다른 방문하지 않은 점들에 대해 클러스터링을 다시 수행

- 장점 : 군집 개수 지정 필요 없음. 민시프트에서 점들이 다르면 다른 군집으로 판단했으나, 아웃라이어를 노이즈로 판단해서 포함시킴

- 단점 : 동작이 힘듬

https://michigusa-nlp.tistory.com/27

민시프트를 이용한 영상 분할 예시

확률 밀도 함수의 모드

- PDF에서의 모드란 봉우리를 의미함

- 아래의 그림은 모드, 미디안, 평균의 차이를 보여줌

모드 탐색 mode seeking

- 주어진 점이 어느 모드에 속하는지 찾는 것

- x가 주어질때 어느 모드에 속할까?

샘플로부터 확률 밀도 함수 구하기

- 가우시안 분포를 따르는 데이터들의 산점도

- 모집단 확률 밀도 함수

확률 밀도 함수에 커널 적용하기

- 특정 샘플 x의 확률 값을 추정하는 공식

- 파젠창(평평한 커널)을 사용한 경우. 대역폭 0.5

- 가우시안 커널을 적용한 경우. 대역폭 0.1

- 가우시안 커널. 대역폭 1

 -> 대역폭이 클수록 커널 안에 많은 점들이 들어와 매끄러워짐. 커널이 작으면 거칠어짐

*http://prayingforfamily.blogspot.com/2016/08/blog-post.html

차원의 저주

- 방금 본 예제는 2차원 공간에서의 확률 값 계산

-> 차원이 커지면 계산해야할 양이 급격히 커짐

정규화 절단 영상 분할

1) 입력 영상을 유사도 그래프와 인접 행렬로 표현

2) 연결 요소의 유사도 행렬 계산

3) 인접 행렬과 대각 요소로부터 고유 값과 고유 벡터 계산

4) 고유 벡터로 연결 요소 분할

5) 재귀적으로 수행

최소 신장 트리를 이용한 영역 분할

- 최소 신장 트리 minimum spanning tree

- 입력 영상을 그래프로 표현 -> 최소 신장 트리를 구함

=> 최소 신장 트리의 연결에 따라 영상을 분할

영역 분할

- 입력 영상이 주어질때 물체와 배경을 나누는 기술

- 저분할 : 너무 약하게 분할한 경우

- 과분할 : 너무 세밀하게 분할한 경우 

- 에지 사용하기 ? -> 폐곡선이 안되는 경우가 많음

- 특징을 사용하는 경우 ? -> 여러개의 특징점으로 매칭도 수행해야함

임계치를 이용한 분할

- 임계치 이진화를 이용한 영역 분할 예시

- 하나의 임계치를 사용할때 영역 분할을 실패한 경우 -> 원본 영상에 명암으로 인해 이진 분할 실패

- 밝기 변화를 근사한 영상 활용 -> 기존의 입력 영상 - 밝기 변화 근사 영상 => 밝기 요소가 제거된 영상 

- 밝기 요소를 제거한 영상의 임계치 이진화를 통한 영역 분할

색상 분할

- 색상 군집화를 이용한 영역 분할

SURF Speeded Up Robust Feature

- 말그대로 고속 강인 특징.

- SIFT 특징 검출이 오래 걸리므로 이를 근사화 시킨 특징이라 할수 있음.

가우시안 필터의 근사화

- 가우시안 필터를 근사화 하여 박스 필터로 만듬

적분 영상 integral image

- 적분 영상을 이용하여 특정 블록의 박스 필터 적용 결과를 빠르게 획득함

박스 필터의 확장

- 각 박스 필터를 옥타브 마다 확장.

- 4개의 옥타브에 대한 박스 필터를 사용하여 검출한 특징이 SURF

SIFT Scale Invariant Feature Transform

- 컴퓨터 비전을 공부할때 가장 유명한 특징이라고 할수 있을것 같다.

- 이름 그대로 영상을 크기에 불변 특징들로 변환하는 알고리즘.

- 한 스케일을 옥타브라 하고, 한 옥타브에 분산 값에 따라 여러개의 가우시안 차분 DOG들로 이루어짐

- SIFT 특징(키포인트)의 구성 : <y, x, o, i> (o는 옥타브, i는 DOG 번호) 

DOG Difference of Gaussian

- 가우시안 차분 영상

- DOG 피라미드

 1) 한 옥타브의 영상들을 가우시안 스무딩 수행

 2) 스무딩 영상 간 -연산하여 차분 영상들을 획득

 3) 모든 옥타브에 수행하여 DOG 피라미드 획득

특징점의 필요성

- 대응점 찾기 correspondence나 매칭 문제에서 특징점이 필요

- 입력영상에섯 꼭지점들이 주로 특징점으로 사용됨

- 이러한 특징점들은 영상에서 변환이 일어나도 검출  할 수 있어야 함.

지역 특징 local feature

- 구성 요소 : 스케일, 위치, 방향 특징 벡터 등

- 검출 단계에서 스케일과 위치, 기술 단계에서 방향과 특징 벡터를 구함

지역 특징의 특성

- 분별력 : 영상의 다른 부분들과 구분 가능해야함

- 반복성 : 비슷 한 영상에서 동일하게 검출가능해야함

- 지역성 : 다른 물체로 가려지는 상황에 대처할 수 있도록 특정 지점에서 지역적이여야 함

- 계산 효율 : 빠른 시간에 수행해야함

모라벡 알고리즘

- 입력 영상과 마스크(특정 픽셀의 상하좌우 4방향)가 주어질 때, 제곱차합(SSD) S(v, u) 맵 계산

- S(v, u) 맵이 수직이나 수평 방향으로 값을 가진다 -> 에지

- S(v, u) 맵이 모든 방향으로 값이 크다 -> 특징

=> but. 노이즈나 회전시 대각선 방향에서 찾을수 없음

해리스 코너

- 모라벡 알고리즘에서 노이즈 대처할 수 있도록 가우시안 마스크를 사용.

- 입력 영상과 마스크(가우시안)이 주어질 때 가중치 제곱차합(WSSD)로 S(v,u)맵 계산

- 태일러 전개를 통해 각 방향에 대한 미분 영상 획득

 => 가우시안 마스크와 미분 영상들을 컨볼루션하여 2차 모멘트 행렬 구함

- 2차 모멘트 행렬의 고유치로 특징 여부를 계산 가능

- 아래의 이미지는 opencv의 해리스 코너 검출기로 검출한 특징 결과

비최대 억제 non-maximum suprresion

- 지역 특징을 제외한 지점들을 억제시키는 방법

- 특징 계산시 : 모라벡 알고리즘, 해리스 알고리즘, LOG 등 선정하여 사용

- 특징 가능성 지도로 특징점 찾기 가능

스케일에 강인한 특징

- 원본 영상의 다양한 크기(다중 스케일 영상)에서 검출 가능한 특징 + 다양한 표준 편차로 가우시안 스무딩 적용

- 가우시안 피라미드

그라디언트, 라플라시안, 헤시안

- 그라디언트 : 1함수(영상), 다변수 미분

- 자코비안 : 다함수, 다변수 미분

- 헤시안 : 다함수, 다변수 2차 미분

- 라플라시안 : 함수의 2차 편미분들의 합

그라디언트의 크기와 방향 영상 비교

- 그라디언트의 크기 영상과, 그라디언트의 방향 영상

원본 영상, 라플라시안 영상, 그라디언트 크기 영상 비교

- 라플라시안 영상 : x축 2차미분, y축 2차 미분 영상들의 합

- 그라디언트 크기 영상 : x축 1차 미분, y축 1차 미분 영상의 유클리디안 노름

허프 변환 hough transform

- 에지들로부터 선분 검출하는 알고리즘

1. y-x 공간에 존재하는 점(에지)들을 직선의 방정식으로 나타내는 b-a 공간에서 표시

2. b-a 공간상에서 교점이 점들을 지나는  y-x공간에서의 직선 방정식을 나타냄

3. y-x 공간에서 수직선은 기울기가 무한대 이므로 b-a 공간 대신, 극 좌표계 공간상에서의 교점을 찾으면 해결

RANSAC RANdom SAmple Consensus

- 인라이어와 아웃라이어가 혼합된 데이터에서 인라이어를 찾아 모델로 만드는 방법

 => 모델이 직선의 방정식인 경우 y = ax + b. RANSAC은 잡음을 제거한 a, b를 구함

- RANSAC으로 아웃라이어를 제거한 근사화된 모델 예시

에지 edge

- 영상에 존재하는 물체 간 혹은 물체와 배경 사이의 경계

- 영상의 미분을 통해 구함

에지 검출 전 주의사항

- 잡음이 심한 경우 에지가 매우 커짐

=> 에지 검출전 스무딩 수행 필요

그라디언트 벡터 gradient vector

- 영상 f(y,x)에서 y방향에 대한 편도함수와 x방향에 대한 편도함수

에지 검출에 사용되는 마스크

- 그라디언트 계산에 사용됨.

- 단순한 마스크를 확장하여 스무딩 효과를 갖는 대표적인 마스크 3가지

- 로버츠 연산자 : 잘 안씀.

- 프레윗 연산자 : 위 아래 행과 열을 고려.

- 소벨 연산자 : 가장 많이 쓰임. 가까운 화소일수록 더 큰 가중치

- 아래의 그림은 로버츠, 소벨, 프레윗 연산자 순서

그라디언트, 에지 강도, 그라디언트 방향

- 그라디언트로 에지 강도와 그라디언트 방향을 계산 가능

- 그라디언트 방향과 에지 방향의 관계 => 서로 수직

Marr의 알고리즘

- 1970년대까지 소벨 연산자가 많이 쓰임

- 가우시안 마스크의 분산에 따라 여러가지의 에지 영상을 얻을 수 있음

LOG Laplacian Of Gaussian

- 라플라시안 : 2차 편도함수의 합

- LOG 란 ? 기존 영상에 가우시안 필터를 컨볼루션 한 후 라플라시안을 적용하는 것

 => 여기서 사용하는 연산자를 LOG 연산자

캐니 에지

- 1986년 발표.

- 기존의 에지 알고리즘들은 가장 좋아보이는 휴리스틱한 방법으로 찾음.

- 캐니 에지는 에지 검출을 최적화로 다룸

- 가우시안의 표준편차, 이력 임계값 T_high, T_low 가 주어지면 캐니 에지 영상을 획득 가능

에지 영상 비교