Content deleted Content added
+ refs. section |
No edit summary |
||
Line 1:
{{redirect|TF Algorithm}}
[[File:Street in Sendai.png|thumb|400px|The TF algorithm produces the background image from a video of a street with many pedestrians crossing.]]
The '''Teknomo-Fernandez Algorithm''', also known as '''TF Algorithm''', is an efficient algorithm for generating the background image of a given video sequence. <ref>{{cite journal | last1 = Abu | first1 = Patricia Angela | last2 = Fernandez | first2 = Proceso| title = Extendibility of the Teknomo-Fernandez Algorithm for Background Image Generation | pages = 28-37 | url = http://www.wseas.us/e-library/conferences/2014/Malaysia/ACACOS/ACACOS-03.pdf }}</ref>
By assuming that the background image is shown in the majority of the video, the algorithm is able to generate the background image of a video using only a small number of [[binary operations]] in O(R)-time.<ref name="TF">{{cite journal | last1 = Teknomo | first1 = Kardi | last2 = Fernandez | first2 = Proceso| title = Background Image Generation Using Boolean Operations | url =https://arxiv.org/abs/1510.00889}}</ref>
==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 [[motion tracking]], [[object tracking]], and [[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_Segmentation}}</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. <ref name="TF" />
Line 17 ⟶ 19:
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" />
==Background Image Generation==
===Equations===
# For three frames of image sequence x<sub>1</sub>, x<sub>2</sub>, and x<sub>3</sub>, the background image B is obtained using <math>B = x_3(x_1\oplus x_2)+x_1x_2 </math><ref name="TF" />
#The Boolean mode function S of the table occurs when the number of 1 entries is larger than half of the number of images such that <math>S=\begin{cases}1,&
\text{if }\sum_{i=1}^{n}x_i\ge\left \lceil \frac{n}{2}+1\right\rceil,n\ge 3 \\0, &\text{if otherwise}\end{cases}</math><ref name="TF" />
# For three images, the background image B can be taken as the value <math>\bar{x_1}x_2x_3+x_1\bar{x_2}x_3+x_1x_2\bar{x_3}+x_1x_2x_3</math> <ref name="TF" />
===Background Generation Algorithm===
At the first level, three frames are selected at random from the image sequence to produce a background image by combining them using the first equation. This yields a better background image at the second level. The procedure is repeated until desired level <math>L</math>.<ref name="TF" />
==Theoretical Accuracy==
At level <math>l</math>, the probability <math>p_l</math> that the modal bit predicted is the actual modal bit is represented by the equation <math>p_l = (p_{l-1})^3 + 3(p_{l-1})^2(1-p_{l-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|inline|center|400px|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 6 levels.]]
==Space Complexity==
The space requirement of the Teknomo-Fernandez Algorithm is given by the function <math>O(RF+R3^L)</math>, depending on the resolution <math>R</math> of the image, the number <math>F</math> of frames in the video, and the desired number <math>L</math> of levels. However, the fact that <math>L</math> will probably not exceed 6 reduces the space complexity to <math>O(RF)</math>.<ref name="TF" />
==Time Complexity==
The entire algorithm runs in <math>O(R</math>)-time, only depending on the resolution of the image. Computing the modal bit for each bit can be done in <math>O(1)</math>-time while the computation of the resulting image from the three given images can be done in <math>O(R)</math>-time. The number of the images to be processed in <math>L</math> levels is <math>O(3^L)</math>. However, since <math>L \le 6</math>, then this is actually <math>O(1)</math>, thus the algorithm runs in <math>O(R)</math>.<ref name="TF" />
==References==
{{reflist}}
==Further reading==
* {{cite thesis |last=Chu |first=Varian Sherwin B. |title=Background image reconstruction using random frame sampling and logical bit operations |date=2013 |publisher=Ateneo de Manila University }}
==External links==
* [https://www.researchgate.net/publication/273391116_A_Monte-Carlo-based_Algorithm_for_Background_Generation A Monte-Carlo-based Algorithm for Background Generation] - a variant of the [[Teknomo-Fernandez algorithm]] that incorporates the [[Monte-Carlo method]] was developed in this study.
*[http://www.wseas.us/e-library/conferences/2014/Malaysia/ACACOS/ACACOS-03.pdf Background Image Generation Using Boolean Operations] - describes the [[TF algorithm]], its assumptions, processes, accuracy, time and space complexity, and sample results.
*[http://www.wseas.org/multimedia/journals/information/2015/a465709-432.pdf Extending the of the Teknomo-Fernandez Background Image Generation Algorithm on the HSV Colour Space] - explores extending the [[TF algorithm]] from the original [[RGB]] color space to the [[HSV]] color space.
*[https://www.researchgate.net/publication/298791390_Modifying_the_Teknomo-Fernandez_Algorithm_for_Accurate_Real-Time_Background_Subtraction Modifying the Teknomo-Fernandez Algorithm for Accurate Real-Time Background Subtraction] - proposes the use of the [[TF algorithm]] for real-time background subtraction and also the application of some modifications for better accuracy.
*[http://www.wseas.us/e-library/conferences/2014/Malaysia/ACACOS/ACACOS-03.pdf Extendibility of the Teknomo-Fernandez Algorithm for Background Image Generation] - performs the theoretical and empirical analyses of the extendibility of TF3 by considering tournament sizes of 5 (TF5), 7 (TF7) and higher.
*[https://www.semanticscholar.org/paper/Performance-comparison-of-the-Teknomo-Fernandez-al-Abu-Fernandez/c45c7e300e2bbc800f269ddfe22596a8fe7b301f Performance comparison of the Teknomo-Fernandez algorithm on the RGB and HSV colour spaces] - examines the performance of the [[TF algorithm]] on both [[RGB]] and [[HSV]] color spaces.
*[https://www.researchgate.net/publication/273445070_Improving_the_Teknomo-Fernandez_Background_Image_Modeling_Algorithm_for_Foreground_Segmentation Improving the Teknomo-Fernandez Background Image Modeling Algorithm for Foreground Segmentation] - creates a significantly improved TF3 variant and evaluates it using the [[Wallflower dataset]]. It is also compared to state-of-the-art background subtraction algorithms.
| |||