Condensation algorithm

The condensation algorithm (Conditional Density Propagation) is a computer vision algorithm. The principal application is to detect and track the contour of objects moving in a cluttered environment. Object tracking is one of the more basic and difficult aspects of computer vision and is generally a prerequisite to object recognition. Being able to identify which pixels in an image make up the contour of an object is a non-trivial problem. Condensation is a probabilistic algorithm that attempts to solve this problem.

The algorithm itself is described in detail by Isard and Blake in a publication in the International Journal of Computer Vision in 1998.[1] One of the most interesting facets of the algorithm is that it does not compute on every pixel of the image. Rather, pixels to process are chosen at random, and only a subset of the pixels end up being processed. Multiple hypotheses about what is moving are supported naturally by the probabilistic nature of the approach. The evaluation functions come largely from previous work in the area and include many standard statistical approaches. The original part of this work is the application of particle filter estimation techniques.

The algorithm’s creation was inspired by the inability of Kalman filtering to perform object tracking well in the presence of significant background clutter. The presence of clutter tends to produce probability distributions for the object state which are multi-modal and therefore poorly modeled by the Kalman filter. The condensation algorithm in its most general form requires no assumptions about the probability distributions of the object or measurements.

Algorithm overview

The condensation algorithm seeks to solve the problem of estimating the conformation of an object described by a vector at time , given observations of the detected features in the images up to and including the current time. The algorithm outputs an estimate to the state conditional probability density by applying a nonlinear filter based on factored sampling and can be thought of as a development of a Monte-Carlo method.[1] is a representation of the probability of possible conformations for the objects based on previous conformations and measurements. The condensation algorithm is a generative model[2] since it models the joint distribution of the object and the observer.

The conditional density of the object at the current time is estimated as a weighted, time-indexed sample set with weights . N is a parameter determining the number of sample sets chosen. A realization of is obtained by sampling with replacement from the set with probability equal to the corresponding element of .[1]

The assumptions that object dynamics form a temporal Markov chain and that observations are independent of each other and the dynamics facilitate the implementation of the condensation algorithm. The first assumption allows the dynamics of the object to be entirely determined by the conditional density . The model of the system dynamics determined by must also be selected for the algorithm, and generally includes both deterministic and stochastic dynamics.

The algorithm can be summarized by initialization at time and three steps at each time t:

Initialization

Form the initial sample set and weights by sampling according to the prior distribution. For example, specify as Gaussian and set the weights equal to each other.

Iterative procedure

  1. Sample with replacement times from the set with probability to generate a realization of .
  2. Apply the learned dynamics to each element of this new set, to generate a new set .
  3. To take into account the current observation , set for each element .

This algorithm outputs the probability distribution which can be directly used to calculate the mean position of the tracked object, as well as the other moments of the tracked object.

Cumulative weights can instead be used to achieve a more efficient sampling.[1]

Implementation considerations

Since object-tracking can be a real-time objective, consideration of algorithm efficiency becomes important. The condensation algorithm is relatively simple when compared to the computational intensity of the Ricatti equation required for Kalman filtering. The parameter , which determines the number of samples in the sample set, will clearly hold a trade-off in efficiency versus performance.

One way to increase efficiency of the algorithm is by selecting a low degree of freedom model for representing the shape of the object. The model used by Isard 1998 is a linear parameterization of B-splines in which the splines are limited to certain configurations. Suitable configurations were found by analytically determining combinations of contours from multiple views, of the object in different poses, and through principal component analysis (PCA) on the deforming object.

Isard and Blake model the object dynamics as a second order difference equation with deterministic and stochastic components:

where is the mean value of the state, and , are matrices representing the deterministic and stochastic components of the dynamical model respectively. , , and are estimated via Maximum Likelihood Estimation while the object performs typical movements.[1][3]

The observation model cannot be directly estimated from the data, requiring assumptions to be made in order to estimate it. Isard 1998 assumes that the clutter which may make the object not visible is a Poisson random process with spatial density and that any true target measurement is unbiased and normally distributed with standard deviation .

The basic condensation algorithm is used to track a single object in time. It is possible to extend the condensation algorithm using a single probability distribution to describe the likely states of multiple objects to track multiple objects in a scene at the same time.[4]

Since clutter can cause the object probability distribution to split into multiple peaks, each peak represents a hypothesis about the object configuration. Smoothing is a statistical technique of conditioning the distribution based on both past and future measurements once the tracking is complete in order to reduce the effects of multiple peaks.[5] Smoothing cannot be directly done in real-time since it requires information of future measurements.

Applications

The algorithm can be used for vision-based robot localization of mobile robots.[6] Instead of tracking the position of an object in the scene, however, the position of the camera platform is tracked. This allows the camera platform to be globally localized given a visual map of the environment.

Extensions of the condensation algorithm have also been used to recognize human gestures in image sequences. This application of the condensation algorithm impacts the range of human–computer interactions possible. It has been used to recognize simple gestures of a user at a whiteboard to control actions such as selecting regions of the boards to print or save them.[7] Other extensions have also been used for tracking multiple cars in the same scene.[8]

The condensation algorithm has also been used for face recognition in a video sequence.[9]

Resources

An implementation of the condensation algorithm in C can be found on Michael Isard’s website.

An implementation in MATLAB can be found on the Mathworks File Exchange.

An example of implementation using the OpenCV library can be found on the OpenCV forums.

See also

  • Particle filter – Condensation is the application of Sampling Importance Resampling (SIR) estimation to contour tracking

References

  1. ^ a b c d e Isard, M.; Blake, A (August 1998). "CONDENSATION-- conditional density propagation of visual tracking". International Journal of Computer Vision. 29 (1): 5–28. doi:10.1023/A:1008078328650. S2CID 6821810.
  2. ^ Sminchisescu, C.; Kanaujia, A.; Metaxas, D.N. (November 2007). "BM3E: Discriminative Density Propagation for Visual Tracking". IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (11): 2030–2044. CiteSeerX 10.1.1.78.1751. doi:10.1109/tpami.2007.1111. PMID 17848782. S2CID 1949783.
  3. ^ Blake, Andrea; Isard, Michael; Reynard, David (October 1995). "Learning to track the visual motion of contours". Artificial Intelligence. 78 (1–2): 179–212. doi:10.1016/0004-3702(95)00032-1.
  4. ^ Koller-Meier, Esther B.; Ade, Frank (28 February 2001). "Tracking multiple objects using the Condensation algorithm". Robotics and Autonomous Systems. 34 (2–3): 93–105. doi:10.1016/s0921-8890(00)00114-7.
  5. ^ Isard, Michael; Blake, Andrew (28 May 2006). "A smoothing filter for condensation". Computer Vision — ECCV'98. Lecture Notes in Computer Science. Vol. 1406. pp. 767–781. doi:10.1007/BFb0055703. ISBN 978-3-540-64569-6.
  6. ^ Dellaert, F.; Burgard, W.; Fox, D.; Thrun, S. (1999). "Using the CONDENSATION algorithm for robust, vision-based mobile robot localization". Proceedings. 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No PR00149). Vol. 2. pp. 588–594. doi:10.1109/CVPR.1999.784976. hdl:1853/21565. ISBN 0-7695-0149-4. S2CID 16130780. {{cite book}}: |journal= ignored (help)
  7. ^ Black, M.J.; Jepson, A.D. (14 April 1998). "Recognizing temporal trajectories using the condensation algorithm". Proceedings Third IEEE International Conference on Automatic Face and Gesture Recognition. pp. 16–21. CiteSeerX 10.1.1.154.1402. doi:10.1109/AFGR.1998.670919. ISBN 0-8186-8344-9. S2CID 5159845. {{cite book}}: |journal= ignored (help)
  8. ^ Meier, E.B.; Ade, Frank (1999). "Tracking cars in range images using the CONDENSATION algorithm". Proceedings 199 IEEE/IEEJ/JSAI International Conference on Intelligent Transportation Systems (Cat. No.99TH8383). pp. 129–134. doi:10.1109/ITSC.1999.821040. ISBN 0-7803-4975-X. S2CID 12548469. {{cite book}}: |journal= ignored (help)
  9. ^ Zhou, Shaohua; Krueger, V.; Chellappa, R. (21 May 2002). "Face recognition from video: A CONDENSATION approach". Proceedings of Fifth IEEE International Conference on Automatic Face Gesture Recognition. pp. 221–226. doi:10.1109/AFGR.2002.1004158. ISBN 0-7695-1602-5. S2CID 8505547. {{cite book}}: |journal= ignored (help)

Read other articles:

Borneo FC SamarindaJulukanPesut EtamKota/KabupatenSamarindaNegaraIndonesiaFederasiPersatuan Sepakbola Seluruh IndonesiaBerdiri7 Maret 2014; 9 tahun lalu (2014-03-07)StadionStadion Segiri, Samarinda, Kalimantan Timur(Kapasitas: 12,000)PemilikPT Nahusam Pratama IndonesiaPresiden Nabil Hussein Said AminManajer Andri Dauri HusainPelatih Pieter HuistraAsisten Pelatih Demerson Akhyar Ilyas Sultan SammaDokter Tim Dr. Hilda Khoirun NisaLigaLiga 12022–23Peringkat 4Situs webSitus web resmi ...

 

This article is missing information about the background and main plot. Please expand the article to include this information. Further details may exist on the talk page. (September 2019) Year of the VillainOfficial promotional logoPublication informationPublisherDC ComicsGenre Superhero Publication dateMay 2019 – March 2020Main character(s)DC Universe Year of the Villain is a crossover comic book event published by DC Comics. Since May 2019, the event narrates the aftermath ...

 

Irish political party The Workers' Party Páirtí na nOibrithePresidentMichael McCorry[1] (disputed)Founded28 November 1905(original form)17 January 1970(current form)[a]Split fromSinn FéinHeadquarters8 Cabra Road,Dublin 7, IrelandYouth wingWorkers' Party Youth[2]IdeologyCommunismMarxism–LeninismIrish republicanismPolitical positionFar-leftEuropean affiliationINITIATIVE (2013–2023)ECA (2023–present)[3]International affiliationIMCWPWAPColoursRed...

  لمعانٍ أخرى، طالع شارلوت (توضيح). شارلوت   الإحداثيات 42°18′18″N 79°14′17″W / 42.305°N 79.238°W / 42.305; -79.238   [1] تاريخ التأسيس 1809  تقسيم إداري  البلد الولايات المتحدة  التقسيم الأعلى مقاطعة تشاتوكوا  خصائص جغرافية  المساحة 36.42 ميل مربع  ارتفاع 470...

 

Amore & Vita-Selle SMP-Fondriest 2017GénéralitésÉquipe Amore & VitaCode UCI AMOStatut Équipe continentalePays  AlbanieSport Cyclisme sur routeEffectif 18 (dont 2 stagiaires)Manager général Cristian Fanini (d)Directeurs sportifs Francesco Frassi, Marco Andreini (d), Maurizio Giorgini (d), Volodymyr StarchykPalmarèsNombre de victoires 1Amore & Vita-Selle SMP 2016 (d)Amore & Vita-Prodir 2018modifier - modifier le code - modifier Wikidata La saison 2017 de l'équipe c...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Javier Garrido Informasi pribadiNama lengkap Javier Garrido BehobideTanggal lahir 15 Maret 1985 (umur 39)Tempat lahir Irun, SpanyolTinggi 1,78 m (5 ft 10 in)[1]Posisi bermain Bek kiriInformasi klubKlub saat ini AEK LarnacaN...

Ma' RosaPoster filmSutradaraBrillante MendozaProduserLarry CastilloDitulis olehTroy EspirituPemeranJaclyn JosePenata musikTeresa BarrozoSinematograferOdyssey FloresPenyuntingDiego Marx DoblesPerusahaanproduksiCenter Stage ProductionsDistributorFilms Distribution, ParisTanggal rilis 18 Mei 2016 (2016-05-18) (Cannes) 06 Juli 2016 (2016-07-06) (Filipina) Durasi110 menitNegaraFilipinaBahasaFilipina Ma' Rosa adalah sebuah film drama Filipina 2016 yang disutradarai oleh Bril...

 

Questa voce sull'argomento calciatori norvegesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Pål Jacobsen Nazionalità  Norvegia Calcio Ruolo Attaccante Termine carriera 1987 CarrieraSquadre di club1 1973-1980 HamKam? (?)1981-1984 Vålerenga73 (37)1985-1987 HamKam? (?)Nazionale 1975-1986 Norvegia42 (13) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite d...

 

Totaka redirects here. For the acharya named Totaka, see Totakacharya. Japanese composer and voice actor In this Japanese name, the surname is Totaka. Kazumi Totaka戸高一生Born (1967-08-23) August 23, 1967 (age 56)Tokyo, JapanAlma materKunitachi College of MusicOccupationsComposersound directorvoice actorYears active1990–presentEmployerNintendoMusical careerGenresVideo game music, jazz, easy listeningInstrument(s)Pianoguitarbassvibraphone Musical artist Kazumi Totaka (戸...

Disambiguazione – Se stai cercando altri omonimi, vedi Ferdinando Gonzaga (disambigua). Questa voce sull'argomento vescovi italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Ferdinando Tiburzio Gonzagavescovo della Chiesa cattolica  Incarichi ricopertiVescovo di Mantova (1671-1672)  Nato14 aprile 1611 a Vescovato Ordinato presbitero28 dicembre 1639 Nominato vescovo23 febbraio 1671 da ...

 

Association football club in England For other uses, see Fram (disambiguation). Football clubFramlingham TownFull nameFramlingham Town Football ClubNickname(s)The Castlemen, Fram, GreensFounded1887GroundBadingham Road, FramlinghamChairmanDean WarnerManagerLiam AbrahamLeagueEastern Counties League Division One North2023–24Eastern Counties League Division One North, 2nd of 21 Home colours Framlingham Town Football Club is a football club based in Framlingham, Suffolk, England. Affiliated to t...

 

Altair The C-23, an Altair 8D purchased by the US Army Air Corps for use as a staff transport Role Civilian sportType of aircraft National origin United States of America Manufacturer Lockheed Aircraft Limited First flight September 1930 Number built 11 Developed from Lockheed Sirius The Lockheed Altair was a single-engined sport aircraft produced by Lockheed Aircraft Limited in the 1930s. It was a development of the Lockheed Sirius with a retractable undercarriage, and was the first Lockhee...

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (مارس 2018) مقاطعة لويس أند كلارك     الإحداثيات 47°07′N 112°23′W / 47.11°N 112.38°W / 4...

 

Morhof Daniel Georg Morhof Daniel Georg (Wismar, 6 febbraio 1639 – Lubecca, 30 luglio 1691) è stato un poeta, critico letterario e poligrafo tedesco. Fece ripetuti viaggi in Olanda e Inghilterra; fu professore a Rostock, poi dal 1665 a Kiel. Opere D. G. Morhofii Polyhistor, sive de notitia auctorum et rerum commentarii. Quibus præterea varia ad omnes disciplinas consilia et subsidia proponuntur Delle sue poesie latine (Opera poëtica latina omnia, 1697) e tedesche (Teutsche Gedichte, 1682...

 

Università Telematica Pegaso Uninversidad Telemática Pegaso Palazzo Zapata en Nápoles, que alberga la sede de representación del AteneoSigla UNIPEGASOTipo Privada, educación a distanciaFundación 2006Fundador Danilo IervolinoLocalizaciónDirección Centro Direzionale Isola F2Nápoles,  Campania, Italia ItaliaCoordenadas 40°51′27″N 14°16′49″E / 40.857468333333, 14.280386388889Otras sedes 75 en totalAdministraciónRector Alessandro Bianchi[2]​Acade...

En talskrivare är en person som, oftast anonymt utåt sett, bistår med att skriva tal och förbättra kommunikationen med omvärlden för politiker, direktörer och andra offentliga personer, som behöver framträda inför grupper eller allmänheten och ofta representera någon organisation eller verksamhet. En annan kategori av talskrivare kan också bistå privatpersoner med talunderlag vid till exempel högtidsdagar, föredrag etc.[1] Inte sällan har sedermera kända offentliga personer...

 

French translator, writer and lawyer (1608–1658) Engraving by Charles Louis Simonneau, c. 1695, after a portrait by Philippe de Champaigne Antoine Le Maistre (2 May 1608 – 4 November 1658)[1] was a French Jansenist lawyer, author and translator. His name has also been written as Lemaistre and Le Maître, and he sometimes used the pseudonym of Lamy. Background and early life Le Maistre was the son of Isaac Le Maistre, a king’s counsellor, and of Catherine Arnauld, who was t...

 

Mathematical function of two positive real arguments This article is about the particular type of mean. For the similarly named inequality, see Inequality of arithmetic and geometric means. Plot of the arithmetic–geometric mean agm ⁡ ( 1 , x ) {\displaystyle \operatorname {agm} (1,x)} among several generalized means. In mathematics, the arithmetic–geometric mean (AGM or agM[1]) of two positive real numbers x and y is the mutual limit of a sequence of arithmetic means and a ...

Train collision on the Singapore MRT Joo Koon rail accidentJoo Koon MRT Station, where the accident occurred at the platform towards Tuas Link.DetailsDate15 November 2017; 6 years ago (2017-11-15) approximately 8.30 a.m. (SST)LocationJoo Koon MRT stationCoordinates1°19′39.86″N 103°40′42.55″E / 1.3277389°N 103.6784861°E / 1.3277389; 103.6784861CountrySingaporeLineEast–West MRT lineOperatorSMRT Trains Ltd (SMRT Corporation)Incident typeSig...

 

Experimental object-oriented programming language This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: AmbientTalk – news · newspapers · books · scholar · JSTOR (July 2019) (Learn how and when to remove this message...