Teknomo–Fernandez algorithm: Difference between revisions

Revision as of 14:09, 6 December 2017

Latest revision as of 21:29, 14 October 2024

(9 intermediate revisions by 7 users not shown)

Line 3:

The '''Teknomo–Fernandez algorithm (TF algorithm)''', is an efficient algorithm for generating the background image of a given video sequence.

By assuming that the background image is shown in the majority of the video, the algorithm is able to generate a good background image of a video in <math>O(R)</math>-time using only a small number of [[binary operations]] and Boolean Bitbit operations, which require a small amount of memory and has built-in operators found in many programming languages such as [[C (programming language)|C]], [[C++]], and [[Java (programming language)|Java]].<ref name="TF">{{cite journalarXiv | last1 = Teknomo | first1 = Kardi | last2 = Fernandez | first2 = Proceso| title = Background Image Generation Using Boolean Operations | urlyear =https://arxiv 2015 | class = cs.org/abs/1510.00889CV | arxiveprint = 1510.00889 }}</ref><ref name="PCTF">{{cite journalbook | last1 = Abu | first1 = Patricia Angela | last2 = Fernandez | first2 = Proceso| title = 2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM) | chapter = Performance Comparison of the Teknomo-Fernandez Algorithm on the RGB and HSV Colour Spaces | urlyear =https: 2014 | pages = 1–6 | doi = 10.1109//wwwHNICEM.semanticscholar2014.org/paper/Performance7016262 | isbn = 978-comparison1-of4799-the4020-Teknomo-Fernandez-al-Abu-Fernandez/c45c7e300e2bbc800f269ddfe22596a8fe7b301f2 | s2cid = 15493318 }}</ref><ref name="ITF" />

==History==

[[File:Sample Colored Result.png|thumb|500px|The TF algorithm generates the colored background image and uses it for background subtraction.]]

People tracking from videos usually involves some form of [[background subtraction]] to segment foreground from background. Once foreground images are extracted, then desired algorithms (such as those for [[Video tracking|motion tracking]], [[Optical motion tracking|object tracking]], and [[facial recognition system|facial recognition]]) may be executed using these images.<ref name="TF" /><ref name="ITF">{{cite thesis |last=Abu|first=Patricia Angela|date=March 2015|title=Improving the Teknomo–Fernandez Background Image Modeling Algorithm for Foreground Segmentation|type=Ph.D|publisher=Ateneo de Manila University|url=https://www.researchgate.net/publication/273445070_Improving_the_Teknomo-Fernandez_Background_Image_Modeling_Algorithm_for_Foreground_Segmentation273445070}}</ref>

However, [[background subtraction]] requires that the background image is already available and unfortunately, this is not always the case. Traditionally, the background image is searched for manually or automatically from the video images when there are no objects. More recently, automatic background generation through [[object detection]], [[medial filtering]], [[medoid filtering]], [[approximated median filtering]], [[linear predictive filter]], [[non-parametric model]], [[Kalman filter]], and [[adaptive smoothening]] have been suggested; however, most of these methods have high computational complexity and are resource-intensive.<ref name="TF" /><ref name="RTTF">{{cite conference |url=https://www.researchgate.net/publication/298791390_Modifying_the_Teknomo-Fernandez_Algorithm_for_Accurate_Real-Time_Background_Subtraction298791390 |title=Modifying the Teknomo–Fernandez Algorithm for Accurate Real-Time Background Subtraction | last1 = Abu | first1 = Patricia Angela | last2 = Fernandez | first2 = Proceso|date=March 2016| conference=Philippine Computing Science Congress}}</ref>

The Teknomo–Fernandez algorithm is also an automatic background generation algorithm. Its advantage, however, is its computational speed of only <math>O(R)</math>-time, depending on the resolution <math>R</math> of an image and its accuracy gained within a manageable number of frames. Only at least three frames from a video is needed to produce the background image assuming that for every pixel position, the background occurs in the majority of the videos. Furthermore, it can be performed for both grayscale and colored videos.<ref name="TF" />

Line 16:

* The camera is stationary.

* The light of the environment changes only slowly relative to the motions of the people in the scene.

* The number of people does not occupy the scene for the most of the time at the same place.

Generally, however, the algorithm will certainly work whenever the following single important assumption holds: <blockquote>For each pixel position, the majority of the pixel values in the entire video contain the pixel value of the actual background image (at that position).<ref name="TF" /></blockquote>As long as each part of the background is shown in the majority of the video, the entire background image needs not to appear in any of its frames. The algorithm is expected to work accurately.<ref name="TF" />

Line 34:

At level <math>\ell</math>, the probability <math>p_\ell</math> that the modal bit predicted is the actual modal bit is represented by the equation <math>p_\ell = (p_{\ell-1})^3 + 3(p_{\ell-1})^2(1-p_{\ell-1})</math>.

The table below gives the computed probability values across several levels using some specific initial probabilities. It can be observed that even if the modal bit at the considered position is at a low 60% of the frames, the probability of accurate modal bit determination is already more than 99% at 6 levels.<ref name="TF" />

[[File:Probability Table.png|inlineframed|center|400pxalt=Computed probabilities table|This table gives the computed probability values across several levels using some specific initial probabilities. It can be observed that even if the modal bit at the considered position is at a low 60% of the frames, the probability of accurate modal bit determination is already more than 99% at six levels.]]

==Space complexity==

Line 43:

==Variants==

A variant of the Teknomo–Fernandez algorithm that incorporates the [[Monte-Carlo method]] named CRF has been developed. Two different configurations of CRF were implemented: CRF9,2 and CRF81,1. Experiments on some colored video sequences showed that the CRF configurations outperform the TF algorithm in terms of accuracy. However, the TF algorithm remains more efficient in terms of processing time.<ref name="CRF">{{cite journal | last1 = Abu | first1 = Patricia Angela | last2 = Chu | first2 = Varian Sherwin| last3 = Fernandez | first3 = Proceso| title = A Monte-Carlo-based AlgorithmforAlgorithm for Background Generation | url =https://www.researchgate.net/publication/273391116_A_Monte-Carlo-based_Algorithm_for_Background_Generation273391116}}</ref>

==Applications==