Publication detail

Shlukování založené na Voronoiově dláždění pro klasifikaci a vyhledávání ve videu

CHMELAŘ, P. BURGETOVÁ, I.

Original Title

Shlukování založené na Voronoiově dláždění pro klasifikaci a vyhledávání ve videu

English Title

Voronoi Tesselation Based Clustering for Video Classification and Retrieval

Type

article in a collection out of WoS and Scopus

Language

Czech

Original Abstract

Přestože existuje mnoho shlukovacích algoritmů, obecně není možné je použít pro všechny typy úloh. Iniciujícím problémem bylo vytvoření co možná nejvyššího počtu (tisíce) tříd pro klasifikaci popisu lokálních obrazových rysů ve velkém množství videa pro evaluaci TRECvid 2008. Tyto mnohorozměrné vektory pokrývají prostor téměř spojitě a běžně používané shlukovací metody nejsou schopny vytvořit potřebný počet tříd nebo skončit v "rozumném" čase. Proto jsme vyvinuli metodu založenou na Voronoiově dělení prostoru, která vyžaduje maximálně 2 průchody daty. Je založena na náhodném nalezení shluků v místech s (teoreticky) nejvyšší hustotou. Vzhledem k velkému množství dat, je možné vytvořit dostatečně vyšší množství kandidátních shluků, z nich vybrat požadovaný počet tříd (nižší, ale stále velký), a zbytek dat přiřadit do těchto tříd. Provedené experimenty prokázaly, že navržená metoda implementovaná jako sada SQL funkcí a dotazů, otestovaná na rozsáhlém problému a velkém množství výsledných shluků, je řádově rychlejší, než běžně používané přístupy.

English abstract

Although there are many clustering techniques, it is not possible to use them for all purposes. The initiative problem was to create as many clusters as possible (eg. thousands) for the local image features description in huge amount of video for TRECVid 2008 evaluation. These large dimensional vectors cover the space almost continuously and commonly used clustering methods are unable to create enough classes or to finish in serious time. Therefore, we have invented a new method based on Voronoi tessellation that needs no more than two passes through the data. It is based on discovery of clusters in higher density locations. Because of large dataset, it is possible to create higher amount of candidate clusters and select appropriate number of classes (large but not huge) and the rest data assign to these classes. The method has been implemented as a set of SQL functions and queries and tested on a huge problem and large amount of classes. Performed experiments have proven that it is significantly faster than common techniques.

Keywords

Shlukování, klasifikace, vyhledávání, video, lokální rysy

Key words in English

Clustering, Classification, Video Search, Local Features

Authors

CHMELAŘ, P.; BURGETOVÁ, I.

RIV year

2009

Released

4. 2. 2009

Publisher

Vydavateľstvo STU

Location

Brno

ISBN

978-80-227-3015-0

Book

ZNALOSTI 2008, Proceedings of the 8th annual conference

Pages from

71

Pages to

82

Pages count

12

BibTex

@inproceedings{BUT30195,
  author="Petr {Chmelař} and Ivana {Burgetová}",
  title="Shlukování založené na Voronoiově dláždění  pro klasifikaci a vyhledávání ve videu",
  booktitle="ZNALOSTI 2008, Proceedings of the 8th annual conference",
  year="2009",
  pages="71--82",
  publisher="Vydavateľstvo STU",
  address="Brno",
  isbn="978-80-227-3015-0"
}