1 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

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

Petr Chmelař Ivana Rudolfová

Fakulta informačních technologií VUT v Brně

3

Annotation Voronoi Tessellation Based Clustering for Video Classification and Retrieval

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.

4 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Úvod

Shlukování je rozdělování objektů do tříd (clusterů) na základě podobnosti objektů.

Jednotlivé shluky jsou tvořeny objekty, které jsou si podobné více, než z jiných tříd.

Podobnost objektů je na základě hodnot jednotlivých atributů objektů pomocí vzdálenostní funkce.

Shlukování používáme pro redukci dat především pro klasifikaci a vyhledávání ve videu… z lokálních rysů vytvořit „slova“, čím více, tím lépe z 25 mil. a 38 mil. řádků (128D, 32GB a 41GB … v literatuře zmínka o 1GB :)

Problém je neshlukovatelný – objekty, které chceme shlukovat, jsou si navzájem tak podobné (pokrývají datový prostor téměř spojitě), že je není možné rozdělit tak, aby podobnost mezi objekty z různých shluků byla menší než podobnost objektů uvnitř jednotlivých shluků.

5

TRECVid

TRECVid je série evaluací sponzorovaná NIST (National Institute of Standards and Technology, NIST) od 2003, kdy se oddělila od TREC.

Cílem je podpořit výzkum v oblasti vyhledávání informací ve videu.

6

Úlohy TRECVid 2008 High-level feature extraction Content-based copy detection pilot Search

Nalezení snímků (úseků videa) co možná nejvíce relevantních k položeným dotazům z hlediska lidského chápání.

Dotazem může být libovolný obrázek nebo snímek videa.

Nebo textový dotaz na konkrétní osoby, objekty, jejich akce a interakce v rámci nějakého dalšího kontextu tvaru “Najdi snímek několika lidí nastupujících do autobusu, musí být vidět jeho řidič.“

Surveillance event detection pilot Rushes summarization

7

Dostupná dataNIST, respektive komunita TRECVid poskytuje:

Video data „Sound and Vision“ z Netherlands Institute for Sound and Vision, news magazine, science news, news reports, documentaries, educational programming, and archival video in MPEG-2. Devel podmnožina pro vývoj aplikací (219 videí ~100 hodin, 60GB) Test podmnožina pro evaluaci (219 videí ~100 hodin, 60GB)

Master shot reference, Fraunhofer (Heinrich Hertz) Institute in Berlin.

Anotace podmnožiny Devel dat pro klasifikaci a vyhledávání je kolaborativní – poskytuje komunita, nicméně především CAS.

ASR (Automatic Speech Recognition) v Holanštině (University of Twente).

MT (Machine Translation) z holandštiny do angličtiny (Queen Mary, London).

Celkem více než 600GB visuálních dat (společně s meziprodukty zpracování), které musí být „okamžitě“ prohledány.

8

Příklad dat (HLF, Search) Snímky (keyframes) spolu s anotacemi, extrahovány pomocí FFMPEG.

9 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Současný stav

Shlukování

Voronoiovo dláždění

Extrakce vizuálních rysů

Vyhledávání a klasifikace MM dat

10

Shluková analýza Proces rozdělování objektů do tříd na základě podobnosti Podobnost objektů se určuje pomocí vzdálenostní funkce Všeobecně akceptovaná formální definice shlukování není známa, nicméně

metody lze obecně rozdělit do následujících skupin: Metody založené na rozdělování O(NKd) K! Hierarchické metody O(N2d) složitost Metody založené na hustotě O(Ndlog(N)) selhaly… Metody založené na mřížce O(Ndlog(N)) (kde neukrást?) Metody založené na modelech O(???) (implementace?)

Vlastnosti shlukovacích metod: Škálovatelnost Schopnost dobře zpracovat data, která obsahují šum a odlehlé hodnoty… Vytváření shluků různých tvarů

11

Voronoiovo dláždění

Vzdálenostní funkce (Minkowského):

Eukleidova vzdálenost, p = 2

Hrany dělení prostoru S jsou definovány jako množiny bodů o shodné vzdálenosti ke dvěma bodům B(p1, p2) = {x | d(p1, x) = d(x, p2)}.

Uzly jsou body o shodné vzdálenosti alespoň ke třem bodům.

Voronoiovým regionem nebo dlaždicí R(p, S) nazýváme průnik všech polorovin bodu p se sousedními pi p.

Voronoiovo dláždění V(S) je sjednocení těchto regionů v S.

pn

i

pipipppdist

1

12121 ][][),(

12

Extrakce vizuálních rysů (MPEG7)Barvadominantní,histogramy,rozložení…

Texturahomogenní,lokální

Tvarregiony, obrysy

2D – 3D

Pohyb

kamery, objektů,lokální, globální

Umístění

bounding box, region

spatio-temporal

Objekty - tváře…detekce,rozpoznání

další úlohy…

[x,y]

(f/ )t

13

Škálovatelné rozložení barvyDeskriptor popsaný v MPEG-7, podobný kódování JPEG.

Používám 20 + 2x15 = 50 koeficientů.53,133,98,112,126,104,122,138,133,129,138,128,143,128,117,159,148,137,139,125,130,84,166,143,115,183,157,125,126,127,130,130,123,129,104,163,116,121,135,84,110,141,133,132,129,133,144,135,156

Obrázekpřeveden do Y’CbCr,

převzorkován do 8x8 (3x)

TransformovánDCT

Kvantizován,koeficienty jsou

vybírány Zig-Zag

14

Textura

Textura je projekce 3D povrchů objektů do 2D.

Gaborovy filtry

1 + 5x6 = 31 koeficientů.

2

2

2

2

2)(exp

2)(exp),(

,rs

rsrs

PG

15 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Extrakce lokálních rysů

Jak najít vhodnou reprezentaci pro nalezení objektů tak, jak je chápou lidé, složených pomocí objektů, které dokáží “pochopit” počítače?

Detekce “regionů zájmu” (ROI), jako jsou hrany, rohy nebo (barevně) spojité oblasti (bloby).

Extrakce lokálních obrazových rysů včetně jejich okolí.

Nejdůležitější vlastností je opakovatelnost – schopnost stejných detekcí a popisu při různých fotometrických, geometrických podmínkách a šumu.

16

Affine Region Detectors

17

Affine Invariant FeaturesMSER (Maximaly Stable Extremal Regions) pro nalezení spojitých komponent

vhodně prahovaného obrazu (zkusmo) tak, aby byly maximálně stabilní. Extrémní zde pak znamená, že všechny pixely uvnitř regionu mají intenzitu nižší (tmavší) nebo vyšší, než pixely na okraji regionu (Matas, …)

SIFT (Scale Invariant Feature Transform) využívám pro popis regionů nalezených pomocí MSER. Zachycuje určitou informaci o (elipsovitém okolí) bodu zájmu (středu regionu) pomocí histogramu lokálně orientovaných gradientů a ukládá je jako 128-bitový vektor (8 orientací, každá 4x4 umístění).

SURF - Speeded Up Robust Features je pro detekci mnoha zajímavých bodů je založený na výpočtu determinantu Hessovy matice (druhých parciálních derivací) z integrálního obrazu. Popis metodou založenou na Haarově vlnkové transformaci, obdoba SIFT.

18 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Podobnostní vyhledávání a klasifikace videa Úlohy klasifikace a zejména vyhledávání dle obsahu

jsou chápány jako těžké (obrovské množství dat).

Provádí se předložením vzorového multimediálního objektu (obrázku, snímku videa, zvuku),

z něj se extrahují rysy, stejně jako z indexovaných objektů v databázi.

Vyhledávání může fungovat přímo, pomocí vzdálenostní funkce nad vektory rysů (nižší),

pomocí vztahu ke třídám konceptům získaných klasifikací (vyšší úroveň)

nebo dokumentů tvořených vizuálními slovy (…)

19

Vyhledávání informací (IR)Term frequency

četnost výskytu klíčového slova (indexační termíny t) v … dokumentu d váha termínu - důležitost

Inverse document frequency

inverzní log četnosti dokumentů, ve kterých se tem vyskytuje informační hodnota termínu

t

iii tttH

12 )p(log)p()(

dtd

vtf)(

)(

)(log)(

tDD

tidf

w = tf-idf(t) = tf(t) idf(t)

20

Vektorový modelVáhový vektor přiřazen dotazu q i dokumentům dj …

pak vzdálenost (kosinová) je

ale může být i Minkovského

O vzdálenosti platí:

dist(x, y) ≥ 0

dist(x, x) = 0

dist(x, y) = dist(y, x)

dist(x, y) ≤ dist(x, z) + dist(z, y)

qtq wwq ,,1 ,, jtjj wwd ,,1 ,,

t

i jit

i qi

t

i jiqi

j

jj

ww

ww

dq

dqdq

1,

21

,2

1 ,,,dist

q

dj

pn

i

pjj idiqdqdist

1

1][][),(

21 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Popis metody

Založena na předpokladu, že některé objekty shluku mohou být mírně podobné, respektive blízké ve vektorovém prostoru rysů, některým objektům jiného shluku, ale prvky jednoho shluku musí být vždy podobnější středu (medoidu) svého shluku více, než středům jiných shluků.

22

Voronoiovo shlukování – vytvoření kandidátů Nová metoda pracuje ve 3 fázích, vyžaduje maximálně dva průchody daty.

Je založená 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 tříd.

První průchod je možné kdykoliv zastavit, například pokud se odhad prahu jeví jako nevhodný, nebo bylo dosaženo množství kandidátních tříd.

Algoritmus 1: Nalezení medoidů kandidátních tříd.

for each (SELECT f.id, f.features FROM lf_table AS f) { // rand

SELECT c.id, distance(f.features, c.features) AS dist

FROM lf_clusters AS c

ORDER BY dist LIMIT 1;

if (dist > treshold) // log2(|f|^avg(stdev(f[i]))))

INSERT INTO lf_clusters VALUES (f.id=next(id), c.features);

UPDATE lf_table SET cluster=c.id WHERE id=f.id;

} // if(SELECT COUNT(*) FROM lf_clusters > 10*classes) break;

23

Voronoiovo shlukování – redukce tříd Z vytvořených kandidátních tříd je poté možno vybrat takové, které uspokojí naše

požadavky – tak, abychom docílili:

a) minimálního počtu objektů v jednom shluku,

b) maximálního počtu tříd (nižšího, ale stále velkého).

Algoritmus 2: Varianty výběru konečných tříd.

a) DELETE FROM lf_clusters WHERE id IN ( SELECT cluster, count(id) AS cnt FROM lf_table GROUP BY cluster HAVING cnt < min_objects )b) DELETE FROM lf_clusters WHERE id NOT IN ( SELECT cluster, count(id) as cnt FROM lf_table GROUP BY cluster ORDER BY cnt LIMIT max_clusters )

Přestože jsou kroky jednoduché a logické, nejsou popsány ve známé literatuře.

24

Voronoiovo shlukování – volitelné přiřazení Ve druhém (volitelném) průchodu daty se provede přiřazení (i nezpracovaných) dat do

tříd na základě vzdálenosti k jejich medoidům.

Algoritmus 3: Přiřazení všech dat do tříd.

for each (SELECT f.id, f.features FROM lf_table as f) { // all

SELECT c.id, distance(f.features, c.features) AS dist

FROM lf_clusters AS c

ORDER BY dist LIMIT 1;

UPDATE lf_table SET cluster=c.id WHERE id=f.id;

}

25

Evaluace shlukování lokálních LLF (1% dat)

SURF Požadováno [tříd] Vytvořeno [tříd] Čas [h:m]

DBScan > 1 x >> 320

Kmeans 10 1 01:23

100 1 15:20

1000 1 317:02

VoronoiCluster 10000 10000 11:41

100000 100000 16:57

SIFT / MSER Požadováno [tříd] Vytvořeno [tříd] Čas [h:m]

DBScan > 1 x >> 320

Kmeans 10 10 03:16

100 1 18:36

1000 x >> 320

VoronoiCluster 10000 10000 19:16

100000 100000 25:10

26 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Závěr

Podařilo se nám shluknout 25 mil. a 38 mil. vektorů (128D, 32GB a 41GB … v literatuře zmínka o 1GB :)do statisíců tříd v řádu dní.

Vyhledávání funguje.

Optimalizace, paralelismus :) Kvalita u malého množství dat ? Nutné nalézt práh (DBSCAN) - hierarchie, fuzzy?

Problém shlukovatelnosti a chybějící formální teorie shlukování obecně.

27 / 27

Petr Chmelař Ivana Rudolfová

Znalosti 2009

Shlukování založené na Voronoiově dláždění

pro klasifikaci a vyhledávání ve videu

Úvod

Současný stavShlukování

Voronoiovo dlážděníExtrakce vizuálních rysů

Vyhledávání a klasifikace

Popis metody

Evaluace

Závěr

Děkuji

za otázky.

28

ReferenceAurenhammer F. – Klein R. Voronoi Diagrams. Handbook of Computational Geometry, 1 ed. North Holland, 2000. ISBN

0444825371.

Bay H. – Tuytelaars T. – Van Gool L. SURF: Speeded Up Robust Features. Computer Vision – ECCV 2006, 2006, 404-417.

Berkhin P. A Survey of Clustering Data Mining Techniques. Grouping Multidimensional Data. 2006. p. 25-71, 978-3-540-28348-5.

Ester M. – Kriegel H. P. – Sander J. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD. 1996, 226-231.

Han J. – Kamber M. Data Mining: Concepts and Techniques, 2 ed. San Francisco: Morgan Kaufmann, 2006. ISBN 1-55860-901-6.

Lowe D. G. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60, no. 2 November 1, 2004, 91-110.

Mierswa I. et. al. YALE: Rapid Prototyping for Complex Data Mining Tasks. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-06). 2006.

Mikolajczyk K. et al. A Comparison of Affine Region Detectors. International Journal of Computer Vision 65, no. 1 November 13, 2005, 43-72.

PostgreSQL Global Development Group. PostgreSQL 8.3 Documentation: GIN Indexes. http://www.postgresql.org/docs/8.3/static/gin.html.

Robotics Research Group, University of Oxford. Affine Covariant Features. http://www.robots.ox.ac.uk/~vgg/research/affine/.

Sivic J. – Zisserman A. Efficient Visual Search for Objects in Videos. Proceedings of the IEEE 96, no. 4. 2008. ISSN 0018-9219.

Šilhavá J. et al. Testbench for Evaluation of Image Classifiers. Computer Graphics & Geometry, 2007, no. 9, p. 31-47. ISSN 1811-8992.

Van Rijsbergen C. J. Information Retrieval. Butterworth-Heinemann, 1979. ISBN 0408709294. http://www.dcs.gla.ac.uk/Keith/Preface.html.

Whitemarsh Information Systems Corp. SQL:2008 Draft International Standard Documents. http://www.wiscorp.com/SQLStandards.html.

Feature detection (computer vision). Wikipedia, The Free Encyclopedia.http://en.wikipedia.org/wiki/Feature_detection_(computer_vision).

Smeaton A. F. – Over P. – Kraaij W. Evaluation campaigns and TRECVid. Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval. ACM Press, 2006. http://www-nlpir.nist.gov/projects/trecvid/.