Publication detail

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

Original Title

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

Czech Title

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

Language

cs

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.

Czech 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.

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",
  annote="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.",
  address="Vydavateľstvo STU",
  booktitle="ZNALOSTI 2008, Proceedings of the 8th annual conference",
  chapter="30195",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Vydavateľstvo STU",
  year="2009",
  month="february",
  pages="71--82",
  publisher="Vydavateľstvo STU",
  type="conference paper"
}