움직임 추적에서 보통 많이 사용하는 mean-shift와 cam-shift에 대해 정리해본다.

1. mean-shift(민시프트)

mean-shift 알고리즘은 데이터 집합의 밀도 분포에서 지역 극값(local extrema)을 찾아내는 방법이다.

언덕오르기 알고리즘과 비슷한 방법으로 생각할 수 있다. 

데이터 집합이 있을때 보통 mean-shift는 데이터의 이상치(outlier)를 무시한다. 쉽게 말하면 데이터의

정점(peak)으로부터 너무 멀리 떨어진 데이터는 무시한다는 것을 의미한다. 

따라서 특정 지역내의 윈도우 안에 존재하는 데이터 점들만을 사용하여 윈도우를 움직인다.

mean-shift 알고리즘은 다음과 같이 동작한다.

보통 윈도우 내의 데이터들로 부터 무게중심을 구할때 가우시안 분포(Gaussian distribution)을 사용한다.

보통 중심으로 부터 가까이 있는 데이터에 가중치를 좀더 높여 주는 방식이 좋다.

위 그림은 mean-shift 알고리즘의 이동 분포를 표현한 것이다. 사진을 보면 데이터의 중심(많은 픽셀이 분포한 점)

으로 윈도우가 이동하는것을 확인할 수 있다.

mean-shift알고리즘은 지역적 정점을 찾기 때문에 여러 지점에서 정점이 발견 될 수도 있다.

이런 움직임으로 인하여 윈도우 아래 존재하는 데이터들이 바뀌게 되고, 반복적으로 중심 이동 작업을 수행할 

수행할 수 있다. 중심 이동이 반복되면 mean-shift 벡터가 0이 되는 경우가 생기면 이때 수렴하는 순간이라고

판단하면 된다.

OpenCV는 mean-shift 함수를 제공한다.

probImage는 역투영 히스토그램 이미지를 입력으로 받는다. calcBackProject()함수를 이용하면 된다.

window는 커널 윈도우 초기위치, 크기를 나타낸다. criteria는 반복연산의 종료조건을 입력하면 된다.

2. camshift(캠시프트)

[Bradski98] Bradski, Gary R. "Computer vision face tracking for use in a perceptual user interface." (1998).

예를 들어 얼굴 특징을 이용하여 추적하는 경우, 카메라로부터 사람이 가까워지거나 멀어짐에

따라 얼굴 크기에 맞게 자동으로 윈도우 크기를 변화시킨다. 

mean shift와 cam shift 알고리즘은 색상 특징값을 이용하는 추적 알고리즘이라고 생각하기 쉬운데, 

이 생각은 잘못된 생각일 수 있다. 이 두 알고리즘은 확률적 분포에서 표현되는 모든 종류의 특징 분포를 추적한다.

 백색소음은 주변의 소음을 중화시켜 차단하고, 심신에 안정을 준다고 알려져 있다. 한국산업심리학회의 연구 결과에 따르면 백색소음은 집중력을 47.7% 향상시키며, 기억력을 9.6% 높여준다. 이와 함께 스트레스를 27.1% 낮춰준다. 이런 원리를 이용한 학습 보조 기기도 있다. 이런 기기를 통해 효과를 봤다는 사람도 있으니, 백색소음의 효과에 관한 이야기는 전혀 허황된 것은 아닌 듯하다.

1. RAINY MOOD

http://www.rainymood.com/

소나기가 오는 소리를 들을 수 있다. 가끔 천둥 소리도 들린다. 실제로 비가 오고 있는 듯한 착각을 불러 일으킨다. 

2. Jazz and Rain

http://fauxfire.com/?nr=0

벽난로에서 나무가 타는 소리와 함께 음악이 재생된다. 음악을 듣고 싶지 않다면 끌 수도 있고 다른 음악을 선택할 수도 있다. 

7. AUGUST AMBIENCE

http://augustambience.com/

8.SNOWY MOOD

http://snowymood.demouth.net/

눈을 밟으며 걷는 소리

현재 가장 많이 사용하고 있는 옵티컬 플로우 방법은 Lucas와 Kanade방법이다.

[Lucas81] Lucas, Bruce D., and Takeo Kanade. "An iterative image registration technique with an application 

to stereo vision." IJCAI. Vol. 81. 1981.

위 영상을 보면 추적 영상의 외곡에도 상당히 추적을 잘하는 것을 볼수 있다.

각 화소에 대하여 특정 범위 안 윈도우 크기 내의 이웃 화소 들에 대해서 광류식(Optical Flow Equation)의 에러 제곱을

최소화하는 벡터를 구하기 위해 벡터를 지역 최소자승법(local least squares)로 계산한다.

예를 들면 윈도우 크기 3x3일 떄 9개의 화소에 대하여 에러 제곱을 최소화하는 (u,v)을 의사 역행렬(pseudo inverse matrix)을

최소자승법으로 계산한다.

위와 같이 광류식을 새워놓고 에러 제곱을 최소화 하는 광류 벡터(u,v)를 구하이 위해 u와 v로 각각 미분한다.

(에러 제곱을 최소화 하는 광류 벡터)

각각 미분한 식을 0으로 놓고 계산하면 아래 수식을 얻을 수 있다.

을 아래 수식으로 변형한다.

OpenCV에는 Lucas와 Kanade의 Optical Flow함수를 2가지 제공한다.

첫번째는 위 수식을 그대로 적용한 기본 방법이고,

소스 참조 : http://lueseypid.tistory.com/archive/20130122

지금 소개할 Optical Flow는 Horn이 1981년 

[Horn81] Horn, Berthold K., and Brian G. Schunck. "Determining optical flow." 1981 Technical Symposium East. 

International Society for Optics and Photonics, 1981. 

논문에서 소개한 방법이다.

Horn과 Schunck는 밝기값 패턴에서 임의의 화소에서의 발기값이 시간에 따라 변화하지 않는 상수로 가정하고, 

속도 분포가 영상의 모든 화소에서 부드럽게(smooth) 변화한다라는 제약조건을 추가했다. 쉽게 말하면 프레임 간의

간격은 매우 짧은 시간이므로 픽셀의 움직임이 크지 않다는 것을 가정한 것이다.

따라서 제곱에러 e^2를 최소화하는 속도 벡터 u와 v를 반복적으로 계산한다. (아래 수식)

Ex, Ey, Et를 2x2윈도우를 사용하여 다음과 같이 계산한다.

위 방법은 모든 화소에서 광류 계산을 수행하기 때문에 좀 느린 단점이 있다.

어떤 물체를 추적할때 가장 간단한 방법이 해당 블록(영역)을 다음 프레임에서 어딨을지 찾아가는
방법이 가장 간단한 추적 방법일 것이다.

OpenCV에서는 이 방법을 하나의 메소드 형태로 제공한다.

파라메타로 prev는 이전프레임으로 (8비트, 1채널 영상)을 입력받으며, curr는 현재 프레임으로 

이전 프레임과 동일하게 8비트 1채널 영상을 입력 받는다.

block_size는 두 영상에서 비교할 블록의 크기를 의미하며, shift_size는 탐색할 영역 크기를 나타낸다.

velx와 vely는 속도 벡터를 나타내는 변수로 1채널 32비트 실수 영상이다. 

max_range는 curr에서 최대 탐색 범위를 나타내고 usePreviosu가 1이면 velx와 vely에 있는 이전 결과를 사용한다.

입력 영상 및 결과 영상

 결과 영상      (vely)   (velx)

영상의 패치 정합

1. SSD(Sum of Squared Difference)

같은 위치에 있는 픽셀의 차를 구해서 제곱한 값을 다 더해 영역의 유사성 측정을 한다.

유사할 경우 0에 가깝다.

2. SAD(Sum Of Absolute Difference)

같은 위치에 있는 픽셀의 차를 절대값 하고 다 더해 영역의 유사성 측정을 한다.

SSD와 마찬가지로 유사할 경우 0에 가깝다.

3. NCC(Normalized Cross Correlation)

NCC는 SSD와 SAD가 갖는 밝기 차의 문제를 결하기 위해 사용하는 중 하나이다. 

두 영역의 픽셀 평균값과 표준편차를 계산하여 평균 값기가 0, 표준편차는 1이 되도록 정규화한다.

m은 평균 밝기를 나타내며 σ는 표준편차이다.

해리스 코너는 크리스 해리스(Chris Harris)라는 사람이 1988년 제안한 것이다.

해리스 코너 검출기는 미분값에 기반을 둔 검출 방법이다. 코너 응답 함수(CRF-Corner Response Function)을 기반으로

코너를 파악한다. 코너 응답 함수(CRF)는 코너가 얼마나 강한지 판별하는 함수이다.

※ 해리스 코너 검출은 다음 5가지 과정을 거친다.

위 행렬식은 2x2행렬의 고유 벡터(Eigen vector)가 얼마나 서로 수직인 방향으로 큰 값을 갖는지를 측정하는 값이다.

여기서 Ix와 Iy는 각각 영상에서 가로와 세로 방향의 미분값을 나타낸다. 이러한 행렬에서 고유 벡터를 구하면 경계선

방향에 수직인 벡터 두개를 얻을 수 있다. 아래 그림과 같이 두 방향의 벡터를 구할 수 있다.

각각 두 벡터는 수직일 경우와 수직보다 작을 경우, 수직보다 클 경우로 구할 수 있다. 

이때 수직인 경우가 가장 좋은 코너점으로 생각하면 된다. 코너의 벡터는 미분을 이용해 고유벡터를 구하면 된다.

고유 벡터를 구하는 것은 고유값 분해(Eigen Value Decomposition)을 계산해야 하지만 조금 복잡하고 시간이 많이 소요된다.

따라서 해리스 코너 검출기에서는 고유 벡터를 직접 구하지 않고 코너 응답 함수(CRF)를 사용한다.

여기서 det(M)은 행렬식을 뜻하고, Trace(M)은 행렬의 대각합을 뜻한다. K값은 보통 0.04를 사용한다.

위와 같이 모든 점들에 관해 코너 응답함수(CRF)를 구하고, 그 값이 적절한 임계값(Threshold)이상이면 코너로 판별하면 된다.

2차원 공간상의 직선을 표현하는 방법중 가장 쉬운 방법은 y = ax+b이다.

a값이 직선의 기울기, b 값이 y축과 만나는 y절편이다.

직선의 방정식을 이용하면 모든 직선을 실수 a와 b의 조합으로 나타낼 수 있으며, 입력 영상에 나타날 수 있는

직선이 가지는 a, b값의 범위는 매우 많다.

기울기와, y절편값을 조절하면 수많은 직선을 만들 수 있다. 

따라서 직선을 찾기 위해 이 모든 값을 조사하는건 현실적으로 불가능하다.

이 문제를 해결하기 위해 사용하는 방법이 바로 허프 변환(Hough Transform)이다.

좀더 효율적으로 변수를 조합하여 직선을 표현하여 문제를 해결하는 것이다.

허프 변환은 직선 뿐만 아니라 2차원 평면, 원, 3차원 공간평면 등 다양한 도형에 대해 적용이 가능하다.

허프 변환은 아주 신기한 방법이다. 직선의 방정식을 x, y 극좌표계에서 a값(기울기)와 b(y절편)을 아래와 같은

극좌표계로 변형했을때 같은 기울기를 갖는 직선은 한점에서 만난다는 점이다.

따라서 이를 이용하면 직선을 구할 수 있다.

직선을 위 그림과 같이 표현하면 ρ는 원점에서부터 직선 까지의 거리를 나타내며, Θ는 y축과 직선에서 수직으로 그린

선의 각도를 나타낸다. 위 직선의 방정식을 이용하면 유한한 범위의 ρ와 Θ값을 이용하여 평면 위의 직선을 표현할 수 있다.

따라서 기존 직선의 방정식을 위와 같은 직선의 방정식으로 변형하면 한정 범위안의 직선을 찾을 수 있을 것이다.

극좌표계를 사용하면 평면 위의 한점(x,y)을 지나는 모든 직선을 ρ와 Θ의 조합으로 표현할 수 있다.

영상에서 모든 경계선 좌표 (x,y)에 대해 위 작업을 수행하면 많은 수의 ρ와 Θ 조합을 얻을 수 있다.

만약 한 점에서 많은 직선이 교차할 경우 하나의 픽셀 에 많은 점이 교차할 것이다. 

이것을 이용하여 같은 직선상의 좌표를 구할 수 있다.

허프 변환을 구현할 때 각도 Θ값의 범위를 0'~360' 사이가 아닌 0'~180'로 하고, ρ 값이 음수 값을 가질 수 있도록 한다.