Capitolo 9 - Indici Multimediali

download Capitolo 9 - Indici Multimediali

of 12

  • date post

    07-Apr-2018
  • Category

    Documents

  • view

    218
  • download

    0

Embed Size (px)

Transcript of Capitolo 9 - Indici Multimediali

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    1/12

    Capitolo 9Indici Multimediali

    IntroduzioneIl termine indice un termine che pu avere molteplici significati, ma nellambito multimediale sonodue le definizioni che possono interessare particolarmente:

    1. una lista ordinata in ordine alfabetico in funzione di un particolare dato;2. E un oggetto che permette il puntamento e laccesso a un particolare contenuto, come nel

    caso de libri quando si fa riferimento allindice analitico.

    La definizione piu corretta per la prima presa in considerazione. In generale un indice ha unastruttura ad albero, ossia un grafo connesso formato da nodi e frecce che collegano i livelli dellalbero (

    si parla infatti di alberi k-ary).

    Un albero di ordine k un albero bilanciato (tutti i nodi allo stesso livello) che per ogni nodo possiede knodi figli, e la complessit dellalbero . Il problema che alberi di questo tipo devonoessere ribilanciati ogni qual volta si effettuano operazioni di aggiornamento delle informazionidellalbero, e la complessit aumenta fino ad arrivare allordine O(N)

    Si utilizzano dei B- Tree che sono degli alberi bilanciati dove ogni nodo pu ammettere al massimo o N oN/2 figli.

    Spazi K - Dimensionali

    Ricordiamo inoltre che i dati multimediali sono dati definiti in un o spazio bidimensionale, mentre iclassici dati sono monodimensionali. In generale per si ha che data un informazione a k caratteristicheessa definita in uno spazio k dimensionale.Dunque le query definibili su uno spazio di questo tipo possono essere di tre tipi:

    Matching esatto: si ricerca un punto esatto dello spazio, che pu esserci o meno; Matching nelle vicinanze: si ricerca il punto piu vicino a un punto dato; Matching regionale: si ricerca un intera regione di punti.

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    2/12

    Linserimento di un nuovo oggetto nello spazio comporta una divisione dello spazio k dimensionale inregioni distinte. Linserimento delloggetto avverr in una di queste regioni e se la regione piena allora

    si effettua una nuova divisione della regione.

    Conversione dello spazio

    Un metodo pi efficiente per quello della conversione dello spazio K Dimensionale in unomonodimensionale, pagando pero una piccola perdita di informazione. Una prima tecnica la Spacefillingcurves, che trasforma lo spazio da K a monodimensionale mantenendo punti che erano vicininello spazio K Dimensionale anche in quello Monodimensionale.

    In generale la trasformazione applicata una linearizzazione di una matrice k dimensionale. Se k = 2possiamo introdurre i seguenti metodi di trasformazione:

    Ordinamento di riga/colonna: comporta la linearizzazione degli elementi per riga o colonna, glielementi vengono inseriti allinterno di un vettore o un indice, presenta problemi in accesso ai

    dati quando si accede per colonna ( si passa da 0 a 8)

    Ordinamento prima riga/ prima colonna: presenta una curva di ordinamento diversa dal metodoprecedente, a forma rettangolare. Anche in questo casi si evidenziano problemi in colonna similial metodo precedente

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    3/12

    Diagonale di Cantor: risolve il problema degli accessi con una disposizione diversa di elementivicini:

    Curva di Hilbert o curva Z: simile a quella di Cantor ma con disposizione di elementi tali che lacurva abbia una forma a Z.

    Indicizzazione bidimensionale

    Cerchiamo di definire un metodo di indicizzazione ritornando al concetto di feature di un immagine.Supponiamo di voler considerare uno spazio N dimensionale con k punti distinti su cui definita unafunzione di distanza.

    RAGIONAMENTO BASE

    Allora se possiamo attribuire a ogni punto dello spazio una feature di un oggetto, allora trovare unoggetto simile vuol dire trovare un oggetto che abbia un punto associato alla stessa feature con laminore distanza dal punto a cui associata quella feature per loggetto in questione.

    Nel caso di uno spazio bidimensionale possiamo pensare di voelr dividere come vogliamo tale spaziocon divisioni di qualsiasi forma ( rettangolari, quadrate o triangolari o arbitrarie.). Se la dimensionedello spazio 2 possiamo definire su un immagine un meccanismo di indicizzazione basato su alberibidimensionali.La struttura di ogni elemento dellalbero bidimensionale la seguente:

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    4/12

    INSERIMENTO

    Dunque ogni elemento dellalbero possieder due valori, un tag che identifica lelemento e due

    collegamenti, uno sinistro e uno destro. Per ogni nodo N e M distinti valgono le seguenti regole diinserimento,se il livello pari:

    Se M.XVAL < N.XVAL allora il collegamento a sinistra; Se M.XVAL >= N.XVAL allora il collegamento a destra;

    Se il livello dispari si fanno considerazioni sul valore Y e si stabilisce che:

    Se M.YVAL < N.YVAL allora il collegamento a sinistra; Se M.YVAL >= N.YVAL allora il collegamento a destra;

    dove M il nodo radice.

    CANCELLAZIONE

    La cancellazione risulta essere molto semplice se lelemento da eliminare una foglia, ma complesso

    se un elemento intermedio, poich potrebbe avere dei figli da gestire. Dunque si deve cercare unelemento che possa sostituire quello in cancellazione.

    Lalgoritmo di cancellazione il seguente:

    Si trova un candidato; Si sostituiscono i valori nel nodo da cancellare; Si cancella il vecchio candidato.

    Analizziamo ora la procedura per la determinazione del candidato R. Se dividiamo lalbero in duesottoalberi TL e TR per lalbero TL:

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    5/12

    se li livello dispari M.XVAL < R.XVAL; se li livello pari M.YVAL < R.YVAL;

    mentre per il sottoalbero TR si ha che:

    se li livello dispari M.XVAL >= R.XVAL;

    se li livello pari M.YVAL >= R.YVAL;

    Indicizzazione quadtree

    Il meccanismo di indicizzazione quadre un meccanisco ad albero dove ogni nodo dellalbero definisce

    una regione rettangolare. La radice rappresenta una regione vuota e il quadrante rettangolare divisoin quattro sottoaree che definiscono quattro figli per ciascun nodo dellalbero. Dunque un elemento

    dellalbero sar strutturato in questo modo:

    Dove:

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    6/12

    X e Y sono i valori che per un nodo radice identificano la regione vuota di partenza; NW,SW,SE e NE sono i 4 figli corrispondenti alle sottoregioni:

    Linserimento tra elementi successivi avviene mediante le sottoregioni, in funzione del punto cheidentifica la radice o una sottoregione.

    Algoritmo di inserimento PT_insert(P,R)

    Funzione PT_COMPARE(P,R)

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    7/12

    CANCELLAZIONE

    Il meccanismo di cancellazione un meccanismo che pu essere semplice se il nodo che si vuolecancellare non ha riferimenti ad altri nodi (non ha figli), mentre problematico a seconda dellespecifiche situazioni, dato che per ogni situazione abbiamo bisogno di adottare una specifica soluzione.

    SITUAZIONE 1Problema: Sia N un punto figlio di N radice. N non ha figli.Vogliamo cancellare N. Soluzione: Copiamo N in N e cancelliamo N.SITUAZIONE 2Problema: Sia N un punto figlio di N radice. N ha un solo figlio .Vogliamo cancellare N. Soluzione:Cancelliamo il figlio temporaneamente e copiamo N in N e cancelliamo N.Poi reinseriamo ilfiglio.

    Possono verificarsi altre situazioni specifiche che si risolvono sulla stessa linea condotta in queste duesoluzioni: cancellazione temporanea dei figli e copia di nodi in altri nodi, e reinserimento dei figli.

    Algoritmi di ricerca dei punti

    K NN SearchLalgoritmo di ricerca K NN permette di trovare i K punti alla minima distanza da un punto Q dato iningresso. Supponiamo di voler considerare K = 1. Siamo dunque interessati alla ricerca del punto piuvicino ad un punto fornito in ingresso.

    Definito dunque uno spazio bidimensionale (caso particolare) e definito su di essa una funzione didistanza lalgoritmo procede secondo questi step

    STEP 1 : Si definiscono due parametri: bestdist = +inf e bestdist = NULL;

    STEP 2: si ispeziona la distanza a partire dalla radice, mantenendo sempre aggiornato il parametrobestsol con il punto a distanza piu piccola e bestdist con tale distanza, ricordando che punti a distanzamaggiore dalla distanza bestdist vengono scartati;

    STEP 3: il punto con la minor distanza il punto cercato.

    IMPORTANTE

    Tale algoritmo reiterabile anche per K valori distinti; basta infatti considerare un array di soluzioni eprendere le k soluzioni a distanza minima dal punto in ingresso.

  • 8/4/2019 Capitolo 9 - Indici Multimediali

    8/12

    Range SearchSi ricercano tutti i punti di uno spazio in funzione del punto in ingresso fornito Q e un certo raggio R.Tutti i punti che vengono scartati sono tutti quelli al di fuori dellimmaginaria regione centrata nel puntoQ e raggio R,anche se la condizione di scarto molte delle volte si modifica leggermente ai bordi.

    La valutazione sempre in funzione della funzione di distanza.

    Problemi degli alberi quadtreeUn problema sostanziale degli alberi quadtree che il processo di cancellazione di un nodo moltolento e anche i meccanismi di ricerca di un dato nodo richiedono una complessit molto elevata.

    Alberi R - TreeSupponiamo di voler considerare uno spazio k dimensionale. Una regione in uno spazio k dimensionale pu essere definito come linsieme delle disuguaglianze

    Dove ogni immagine dunque pu essere rappresentata come una regione, invece di un insieme dipunti, come nel caso quadtree.

    In tale spazio k dimensionale si definiscono gli alberi R Tree, generalizzazione degli alberi B Tre