Teknomo–Fernandez algorithm: Difference between revisions

Revision as of 08:45, 16 August 2017

Revision as of 02:15, 20 August 2017

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 (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 a good background image of a video in <math>O(R)</math>-time using only a small number of [[binary operations]] and Boolean Bit 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 journal | last1 = Teknomo | first1 = Kardi | last2 = Fernandez | first2 = Proceso| title = Background Image Generation Using Boolean Operations | url =https://arxiv.org/abs/1510.00889| arxiv = 1510.00889 }}</ref><ref name="PCTF">{{cite journal | last1 = Abu | first1 = Patricia Angela | last2 = Fernandez | first2 = Proceso| title = Performance Comparison of the Teknomo-Fernandez Algorithm on the RGB and HSV Colour Spaces | url =https://www.semanticscholar.org/paper/Performance-comparison-of-the-Teknomo-Fernandez-al-Abu-Fernandez/c45c7e300e2bbc800f269ddfe22596a8fe7b301f}}</ref><ref name="ITF" />

==History==

Line 9:

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" />

Line 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>

==Applications==

Line 67:

* [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.

{{DEFAULTSORT:Teknomo-Fernandez algorithm}}

[[Category:Mathematical examples]]

[[Category:Image processing]]