영상처리 7. 움직임을 어떻게 감지할까

Motion Detected for Surveillance

Video는 시간의 흐름에 따라 연속적으로 촬영된 이미지다. 움직임은 프레임 사이에서 발생하는 시각적 변화와 같다. Video의 Pixel 정보는 \((x,y)\)와 시간 \(t\)인 3차원 정보 \(f(x,y,t)\)로 표현할 수 있다.

Motion이 무엇인가? Video의 Pixel 정보가 시간 \(t\)의 흐름에 따라 어떻게 변하는지 나타낸 것이다. 특정 픽셀이 임의의 프레임에서 \(dt\) 시간 이후의 프레임으로 어떤 방향으로 움직였는지 \((u,v)\) Vector로 나타낼 수 있다. 이것을 Motion Vector라고 한다.

Motion Field란 특정 파라미터 \((x,y,t)\)를 넣었을 때, 그 픽셀의 Motion Vector를 반환하는 Vector Field와 같다.

Motion을 어떻게 Detected할까? 두가지 방법이 있다.

Feature-based Methods

이미지의 특정한 특징들이 프레임 사이에서 어떻게 이동하는지를 추적한 방법이다. 일부 특징점에 대해서만 움직임을 계산하므로, 희소한sparse Motion Vector들이 계산된다.

(1) Block Matching 아이디어는, 두 프레임 이미지를 16x16 크기의 블럭으로 쪼갠다. 이후 현재 프레임 블럭을 이전 프레임에서 가장 유사한 블럭을 찾는다. 두 블럭의 위치 차이를 계산하여, Motion Vector를 생성한다.

현재 프레임 블럭과 가장 유사한 블럭을 이전 프레임에서 어떻게 찾는가? 프레임 블럭의 차이로 계산한다. 두 프레임의 각 픽셀의 절댓값 차이를 평균낸 값이 가장 작은 프레임 블럭을 가장 유사한 프레임 블럭으로 인식한다.

그렇다면, 현재 프레임의 한 블럭과 이전 프레임의 모든 블럭끼리 비교하는가? 만약 한 이미지당 블럭이 N개 있으면, \(O(N^2)\)번 연산해야 하는가? 그렇지 않다. 굳이 전체 영역과 비교할 필요 없다. 현실의 물체는 연속적으로 움직이기 때문에, 주변만 비교해보면 된다. 탐색 영역 파라미터를 \(w\)라고 하자. \(w=7\)이면 현재 블록 위치에서 상하좌우로 7픽셀만 더 탐색해본다. 이를 탐색 영역이라고 한다.

탐색 영역의 가로 또는 세로의 길이는 \(2w + 1\)이다. 만약 \(w=7\)이면 길이는 15이며, 하나의 탐색 영역당 \(15 \times 15 = 255\)번 블럭을 대조해봐야 한다. 총 연산 횟수는 \(255 \times N\)번이다. 계산 양이 너무 많으므로, 다양한 Fast Algorithms이 개발되었다.

(2) Fast Algorithms Fast Algorithm의 아이디어는 움직임이 갑자기 변하지 않을 것이라는 가정 하에 동작한다. 이 알고리즘이 항상 정확한 Motion Vector 결과를 내놓는 것은 아니다. Greedy로 당장 주변부의 오차값이 작다고 해서, 그것이 Motion Vector 방향이라는 보장이 없기 때문이다.

(2-1) 2D Logarithmic Search 2D Logarithmic Search는 Block Matching의 속도 개선 버전이다. **어떻게 더 빨리 해당 블록의 Motion Vector를 찾아낼까?

알고리즘은 다음과 같다. 블록의 탐색 영역의 중심에서 시작하여, Step Size만큼 중심점을 포함한 상하좌우 5개의 픽셀의 오차값을 계산한다. 오차값이 가장 작은 픽셀을 새로운 중심으로 설정한다. 만약 새로운 중심이 상하좌우였다면 Step Size를 유지한다. 그렇지 않고 중심이 그대로라면 Step Size를 절반으로 줄인다. Step Size = 1이 될 때까지 이 과정을 반복한다. Step Size = 1이되면, 마지막 중심점을 기준으로 모든 이웃 픽셀 9개와 처음 픽셀의 오차가 가장 작은 값을 기준점으로 잡는다. 기준점과 처음 픽셀의 차이를 Motion Vector로 간주한다.

초기 Step Size는 어떻게 잡는가? 보통 \(w/2\)로 설정한다.

(2-2) 3SS (Three-Step Search) 2D Logarithmic Search과는 다르게, 딱 3스탭만 반복하여 탐색을 완료하는 방법이다.

탐색 영역 중심에서 Step Size로 주변 8개 지점을 포함해 총 9개 지점을 검사한다. 가장 오차가 작은 픽셀을 중심으로, 간격을 절반으로 줄여 주변 8개의 픽셀과 비교한다. 마지막으로 간격을 절반으로 줄여 주변 8개의 픽셀과 비교하여 최종 중심과 처음 중심의 차이를 Motion Vector로 간주한다.

이 방법은 한 블럭당 연산 횟수가 25번으로 고정된다.

(2-3) DS (Diamond Search) 다이아몬드 패턴으로 탐색한다. 다이아몬드 모양으로 9개의 점을 탐색하여 오차가 가장 작은 점을 중심으로 재탐색한다. 이를 선택된 중심점이 자기 자신이 될때까지 반복한다. 자기 자신이 선택되었다면, 최종적으로 자신과 상하좌우 5픽셀 오차값을 계산하여 가장 작은 픽셀을 중심점으로 선택한다. 최종 중심점과 마지막 중심점의 차이를 Motion Vector로 간주한다.

3SS보다 더 적은 지점을 탐색하면서 성능이 우수하다고 한다.

Direct Methods

구하고 싶은 것은 \((x,y,t)\)에서 Motion Vector \((u,v)\)이다. 만약 이미지의 밝기가 변하지 않는다는 가정을 도입하면, 다음 방정식을 세울 수 있다.

\[I_{x}u + I_{y}v + I_{t} \simeq 0\]

그러나 변수가 2개고 식이 하나이므로 \((u, v)\)를 결정할 수 없다. 따라서 공간적 일관성을 가정한다. 이웃한 픽셀은 서로 비슷하게 움직인다고 가정한다.

따라서, 특정 픽셀 주변에 작은 Window(5x5)를 설정한다. 이 창 안의 픽셀은 같은 Motion Vector \((u,v)\)를 공유한다고 가정한다. 방정식은 창 안의 픽셀 수 (25개)만큼 얻게 된다. 최소제곱법을 사용하여 모든 방정식을 가장 잘 만족시키는 최적의 해 \((u,v)\)를 결정할 수 있다.

[!tip] 활용 분야{title}

• 비디오 압축: MPEG, H.264/HEVC 같은 비디오 코덱의 핵심 기술입니다. 이전 프레임과의 차이점, 즉 움직임 벡터만 저장하여 데이터 용량을 획기적으로 줄입니다56.
• 객체 추적 및 분할: 움직임 정보를 기반으로 영상 속에서 특정 객체를 분리하고 그 경로를 추적하여 CCTV 감시 등에 활용합니다17.
• 3D 구조 복원: 카메라가 움직일 때 촬영된 여러 이미지의 움직임 차이를 분석하여 장면의 3차원 구조를 재구성합니다15.
• 영상 품질 개선: 카메라의 흔들림으로 인한 움직임을 계산하고 상쇄하여 안정적인 영상을 만드는 손 떨림 보정(Stabilization)에 사용됩니다1.
• 로보틱스 및 자율주행: 로봇이나 드론이 주변 환경의 움직임을 파악하여 장애물을 피하고 경로를 탐색하는 데 사용됩니다6.
• 특수효과(VFX) 및 증강현실(AR): 영화에서 컴퓨터 그래픽을 자연스럽게 합성하거나, 현실 세계에 가상 객체를 정확히 위치시키기 위해 움직임을 추적합니다6.