테르노모-페르난데스 알고리즘

테르노모-페르난데스 알고리즘(TF 알고리즘)은 주어진 비디오 시퀀스의 배경 이미지를 생성하기 위한 효율적인 알고리즘이다.null

배경 영상이 대다수의 비디오에 나타난다고 가정하면 알고리즘은 적은 수의 이진 연산과 많은 프로그에서 소량의 메모리가 필요하고 내장된 운영자가 있는 부울 비트 연산만을 사용하여 $O{\displaystyle }$( R${\displaystyle }$) ${\displaystyle O(R)}$ -time에서$$ 비디오의 좋은 배경 영상을 생성할 수 있다.C, C++, Java와 같은 ramming 언어.^[1][2][3]null

역사

비디오에서 추적하는 사람들은 보통 배경에서 전경을 분할하기 위한 어떤 형태의 배경 감산을 포함한다.포그라운드 이미지가 추출되면 원하는 알고리즘(모션 추적, 객체 추적, 안면 인식 등)을 이 이미지를 사용하여 실행할 수 있다.^[1][3]null

그러나, 배경 감산은 배경 이미지를 이미 사용할 수 있어야 하며, 불행하게도 항상 그렇지는 않다.전통적으로 배경 이미지는 물체가 없을 때 비디오 이미지에서 수동으로 또는 자동으로 검색된다.보다 최근에는 객체 감지,^[1][4] 중간 필터링, 중간 필터링, 중간 필터링, 근사치 중위수 필터링, 선형 예측 필터, 비모수 모델, Kalman 필터, 적응형 평활화를 통한 자동 백그라운드 생성이 제안되었지만, 이러한 방법의 대부분은 계산 복잡성이 높고 자원이 집약적이다.null

테르노모-페르난데스 알고리즘도 자동 배경 생성 알고리즘이다.그러나, 이것의 장점은$$ $이미지$의 해상도 R {\$displaystyle$ R$}$에 따라 $O{\displaystyle }$($$R${\displaystyle }$) {\$displaystyle$ $(R)}$ -time의$$ 계산 속도뿐이며, 관리 가능한 프레임 수 내에서 얻은 정확도이다.모든 픽셀 위치에 대해 대부분의 비디오에서 배경이 발생한다고 가정할 때 배경 이미지를 생성하려면 비디오에서 최소 3개의 프레임만 있으면 된다.또한 그레이스케일과 컬러 비디오 모두에 대해 공연할 수 있다.^[1]null

가정

• 카메라가 정지해 있다.
• 환경의 빛은 현장에 있는 사람들의 움직임에 비례하여 느리게 변할 뿐이다.
• 인원은 같은 장소에서 대부분 현장을 차지하지 않는다.

그러나 일반적으로 알고리즘은 다음과 같은 단일의 중요한 가정이 유지될 때마다 확실히 작동할 것이다.

각 픽셀 위치에 대해 전체 비디오에서 대부분의 픽셀 값은 실제 배경 영상의 픽셀 값(해당 위치)을 포함한다.^[1]

배경의 각 부분이 영상의 대부분에 나타나는 한 전체 배경 이미지는 어떤 프레임에도 나타나지 않아도 된다.그 알고리즘은 정확하게 작동할 것으로 예상된다.^[1]null

배경 이미지 생성

방정식

1. 영상 시퀀스 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {x\mathrm{}}_{}}$ 2 ${\$ $x{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 세 프레임에 대해 다음 명령을 사용하여 배경$$ 이미지 $B{\displaystyle }$ ${\displaystyle$ B}을$($를) 얻으십시오$.$
   ${\displaystyle B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}}$^[1]
2. 표의$$ Boolean $모드{\displaystyle }$ 함수$$S {\$displaystyle S}$는 1개 항목 수가 다음과^[1] 같이 영상 수의 절반보다 클 때 발생한다.
   ${\displaystyle S={\begin{case}1,&#{\text{}\sum _{i=1}^{n}x_{i}\geq \lceil \\\\{n}+1\right\ceil,{n}\geq 3\0,&\n\wise}}}}}}}}}}}}:{n\case}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}:{n$
3. 세 개의 이미지에 대해 배경 이미지 $B{\displaystyle }$ ${\displaystyle B}$을(를) 값으로 취할 수 있다$$.

${\displaystyle {\bar}_{1}x_{1}x_{2}x_{3}+x_{1}}}{\bar {{x}_{2}x_{3}+x_{1}}x_{2}{\bar {x}_{3}+x_{1}x_{2}x_{3}}}$ ^[1]

백그라운드 생성 알고리즘

첫 번째 레벨에서는 영상 시퀀스에서 무작위로 3개의 프레임을 선택하여 첫 번째 방정식을 사용하여 조합하여 배경 이미지를 생성한다.이것은 2단계에서 더 나은 배경 이미지를 만들어낸다.이 절차는 원하는 $레벨{\displaystyle }$ L ${\displaystyle$ L$}$까지 반복된다$.$^[1]

이론적 정확도

At level ${\displaystyle \ell }$, the probability ${\displaystyle p_{\ell }}$ that the modal bit predicted is the actual modal bit is represented by the equation ${\displaystyle p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{2}(1-p_{\ell -1})}$.아래 표는 특정 초기 확률을 사용하여 여러 수준에 걸쳐 계산된 확률 값을 제공한다.고려된 위치에서 모달 비트가 프레임의 낮은 60%에 있더라도 정확한 모달 비트 결정 확률은 이미 6개 레벨에서 99% 이상임을 알 수 있다.^[1]null

공간 복잡성

The space requirement of the Teknomo–Fernandez algorithm is given by the function ${\displaystyle O(RF+R3^{L})}$, depending on the resolution ${\displaystyle R}$ of the image, the number ${\displaystyle F}$ of frames in the video, and the desired number ${\displaystyle L}$ of levels.그러나 $L{\displaystyle }$ ${\displaystyle L}$이(가) 6을 초과하지 않을$$ 것이라는 사실은 공간 복잡성을 $O{\displaystyle (\mathrm{RF})}$ ${\displaystyle O($RF$)}$로 감소시킨다$.$^[1]

시간 복잡성

전체 알고리즘은 영상의 해상도에 따라서만 $O{\displaystyle }$ (${\displaystyle R}$) ${\displaystyle O(R)}$ - time으로$$ 실행된다.각 비트에 대한 모달 비트 $계산$은${\displaystyle }$O ( ${\displaystyle 1}$)$${\$displaystyle$O($1)}$ - time으로$$ 할 수 있으며, 주어진 영상 3개의 결과 영상 $계산$은 ${\displaystyle O}$( R${\displaystyle }$) ${\displaystyle$ O$(R)}$ - time에서$$ 할 수 있다.The number of the images to be processed in ${\displaystyle L}$ levels is ${\displaystyle O(3^{L})}$. However, since ${\displaystyle L\leq 6}$, then this is actually ${\displaystyle O(1)}$, thus the algorithm runs in ${\displaystyle O(R)}$.^[1]

변형

몬테카를로 방식인 CRF를 접목한 테르노모-페르난데스 알고리즘의 변종이 개발됐다.CRF의 두 가지 다른 구성이 구현되었다: CRF9,2와 CRF81,1. 일부 컬러 비디오 시퀀스에 대한 실험 결과 CRF 구성이 정확도 면에서 TF 알고리즘을 능가하는 것으로 나타났다.그러나 TF 알고리즘은 처리 시간의 측면에서 보다 효율적인 상태를 유지하고 있다.^[5]null

적용들

• 물체 탐지
• 안면탐지
• 얼굴 인식
• 보행자 감지
• 비디오 감시
• 모션 캡쳐
• 인간과 컴퓨터의 상호작용
• 콘텐츠 기반 비디오 코딩
• 트래픽 모니터링
• 실시간 제스처 인식

참조

추가 읽기

• Chu, Varian Sherwin B. (2013). Background image reconstruction using random frame sampling and logical bit operations (Thesis). Ateneo de Manila University.
• Abu, Patricia Angela R. (2015). Improving the Teknomo-Fernandez Background Image Modeling Algorithm for Foreground Segmentation (Thesis). Ateneo de Manila University.

외부 링크

• Boolean Operation을 사용한 Background Image Generation – TF 알고리즘, TF 알고리즘의 가정, 프로세스, 정확도, 시간과 공간의 복잡성, 샘플 결과 등을 설명한다.
• 몬테카를로 기반 백그라운드 생성을 위한 알고리즘 - 몬테카를로 방법을 통합한 테르노모-페르난데스 알고리즘의 변형이 본 연구에서 개발되었다.