Content deleted Content added
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><ref name="EHSV">{{cite journal | last1 = Abu | first1 = Patricia Angela | last2 = Fernandez | first2 = Proceso| title = Extending the of the Teknomo-Fernandez Background Image Generation Algorithm on the HSV Colour Space| url = http://www.wseas.org/multimedia/journals/information/2015/a465709-432.pdf }}</ref>
By assuming that the background image is shown in the majority of the video, the algorithm is able to generate
==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<ref name="EHSV" /> 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_Subtraction |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" />
==Assumptions==
Line 21:
==Background Image Generation==
===Equations===
# For three frames of image sequence
#The Boolean mode function <math>S</math> 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 <math>B</math> 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" />
Line 38 ⟶ 39:
==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" />
==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 Algorithmfor Background Generation | url =https://www.researchgate.net/publication/273391116_A_Monte-Carlo-based_Algorithm_for_Background_Generation}}</ref>
==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 }}
*{{cite thesis |last=Abu |first=Patricia Angela R. |title=Improving the Teknomo-Fernandez Background Image Modeling Algorithm for Foreground Segmentation |date=2015 |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.
| |||