Dubbio su teorema di Parseval

[Net_Raider]

salve a tutti, non so se è la sezione giusta, dato che l'argomento è l'indicizzazione delle immagini, ma dato il contenuto teorico ho preferito postare qui. nel caso fosse opportuno spostare, fate pure.

la questione è questa:
contesto: indicizzazione delle del vettore delle caratteristiche di un immagine (caratteristiche come l'istogramma, oppure qualche caratteristica shape-based tipo la distanza di ogni punto dal baricentro, o qualsiasi altra possibile caratteristica non è importante. l'importante è che otteniamo un vettore n-dimensionale con n piuttosto grande)

il pezzo in questione che non riesco a comprendere è:

INDEXING THE IMAGE DESCRIPTION
The major problem when dealing with large image databases is the efficiency of the
image retrieval. This efficiency depends on the used schema for indexing.
An image features could be represented as a feature vector that corresponds to a point
in a multi-dimensional feature space. There are three popular approaches for multidimensional
indexing: R-trees (particularly R* trees), linear quadtrees, and grid files. Except
them the following techniques for increasing the efficiency of the image indexing can be
used:
a.) Technique for minimising the number of dimensions for the multi-dimensional
vector which represents the logical view of the image
Let the vector be $X(x_0, x_1, …, x_(n-1))$. The Discrete Fourier Transform $X_f$ of a $X$ is
defined as a sequence Xf of n complex numbers:

$X_f = \frac{1}{sqrt(N)}\sum_{t = 0}^{N-1} x_t e^{{-i \omegat}/N}$

$f = 0, ... , N - 1$

The Parseval theorem gives that:
$\sum_{t = 0}^{N-1}|x_t^2| = \sum_{f = 0}^{N-1}|X_f^2|$
Let a query is described with a sequence of real numbers $q_i (i = 0, …, N-1)$ and an
image from the database with a sequence of real numbers $d_i (i = 0, …, N-1)$. Let’s consider
the two images being $\epsilon$; close if :
$\sqrt{\sum_{i = 0}^{N - 1}|q_i - d_i|^2} <= \epsilon$, but using the Parseval theorem
$\sqrt{\sum_{f = 0}^{N - 1}|Q_f - D_f|^2} = \sqrt{\sum_{i = 0}^{N - 1}|q_i - d_i|^2} <= \epsilon$. Keeping only the first $f_c < N$ coefficients,
we have:
$\sqrt{\sum_{f = 0}^{f_c}|Q_f - D_f|^2} <= \sqrt{\sum_{f = 0}^{N - 1}|Q_f - D_f|^2} = \sqrt{\sum_{i = 0}^{N - 1}|q_i - d_i|^2} <= \epsilon$
In other words if we keep only $f_c$ elements of the complex vector the result subset will
contain all the images from the database in $\epsilon$ vicinity of the query image, but as there will be
spurious images also which are further then $\epsilon$ from the query image. In [8] an experiment
was conducted. It shows that the optimal choice for $f_c$ is $3$.

ecco, quello che non mi è chiaro è il perchè nello spazio della trasformata vengono restituite TUTTE le immagini che si trovano ad una distanza minore di $\epsilon$ dalla query, eliminando così il problema dei false dismissals (immagini pertinenti ma non incluse nel ResultSet)

spero riusciate a chiarirmi le idee, ciao

[dissonance]

Il teorema di Parseval (qui nella versione discreta) è meglio formulato in termini astratti:

la DFT è un isomorfismo isometrico di $CC^N$ in sé [size=75](*)[/size].

"Isomorfismo isometrico" tra spazi normati $X, Y$ è una applicazione $F:X\to Y$ lineare, bigettiva, che preserva le distanze. Il tuo testo non ha sottolineato bene questo punto, ha solo ricordato che la DFT preserva le distanze.

______________
(*) Mi riferisco alla definizione di DFT che usa il tuo libro, quella con coefficiente $1/(sqrt(N))$.

[Net_Raider]

prima di tutto grazie per la risposta, ma purtroppo non mi ha aiutato a capire T.T

[dissonance]

Chiamiamo $F$ la DFT, vista come applicazione $F: CC^N \to CC^N$. Abbiamo detto che è un isomorfismo isometrico: questo concretamente significa che, fissato $epsilon>0$

$|x-y|\le epsilon \iff |Fx-Fy|\le epsilon$.

Ecco perché, dovendo cercare i vettori $x$ distanti da $y$ meno di $epsilon$, puoi invece cercare i vettori $Fx$ distanti da $Fy$ meno di $epsilon$ e sei sicuro di beccarli tutti.

[Net_Raider]

mmm non riesco a convincermi: se la DFT conserva le distanze, perchè allora vorrei cercare i vettori $F_x$ distanti meno di $\epsilon$ da $F_y$? cerco direttamente gli $x$.
inoltre (collegato a questo dubbio), perchè cercando gli $x$ a distanza minore di $\epsilon$ da $y$ rischio di tralasciarne qualcuno?

[dissonance]

"Net_Raider":mmm non riesco a convincermi: se la DFT conserva le distanze, perchè allora vorrei cercare i vettori $F_x$ distanti meno di $\epsilon$ da $F_y$? cerco direttamente gli $x$.

Questo non lo so, dipende dall'applicazione. Evidentemente è più semplice ragionare sui trasformati che sui vettori originari.

inoltre (collegato a questo dubbio), perchè cercando gli $x$ a distanza minore di $\epsilon$ da $y$ rischio di tralasciarne qualcuno?

Ok. Dimostriamo formalmente l'affermazione di prima. Siano $epsilon>0$ e $y\inCC^N$ fissati, sia $Y=Fy$.

Se $x\inCC^N$ è tale che $|x-y| Se $X=Fx \in CC^N$ è tale che $|X-Y|
Quindi $|x-y|

Cita

Segnala

[Net_Raider]

questo l'ho capito.

quello che non mi è chiaro (rifacendomi agli appunti):
considerando $k < < n$ coefficienti di fourier ottengo che la distanza tra $F_x$ e $F_y$ considerando solo tali $k$ coefficienti è minore della distanza tra $F_x$ e $F_y$ considerata su tutti i coefficienti, che a sua volta è uaguale alla distanza tra $x$ e $y$, che a sua volta è minore o uguale ad $\epsilon$, cioe

$\sqrt{\sum_{f = 0}^{k}|Q_f - D_f|^2} <= \sqrt{\sum_{f = 0}^{N - 1}|Q_f - D_f|^2} = \sqrt{\sum_{i = 0}^{N - 1}|q_i - d_i|^2} <= \epsilon$

ora, computazionalmente confrontare $k$ coefficienti, anzichè $n$ è chiaramente un vantaggio. ma sfruttando tale caratteristica cosa mi consente di dire: "con questo metodo becco al 100% tutte le immagini che distano meno di $\epsilon$ dalla query più qualche falso positivo"?

a questo punto mi viene da pensare che è un metodo equivalente a confrontare gli $x$ ma computazionalmente molto più veloce. ma allora perchè specificare che si rimuove il problema dei falsi negativi? (false dismissals)

[Net_Raider]

ok, credo di aver capito.

cercando in internet altri papers penso di aver compreso la situazione.

dunque il problema è: indicizzare dati multimediali (segnali, suoni, volti, immagini ecc...)
abbiamo bisogno di un metodo che in fase di ricerca dei risultati (nel caso di whole match queries, cioè ricerca su tutto il db) sia
-veloce
-corretto, cioè deve includere almeno tutti gli oggetti qualificanti
-dinamico, cioè che sia facile da gestire (inserimenti, cancellazioni, modifiche nel db).

un'idea sarebbe una scansione sequenziale, ma ovviamente questo sarebbe impensabile per db di grosse dimensioni

una alternativa è la sequente:
-un metodo veloce (ma rozzo) per eliminare tutti gli oggetti non qualificanti
-utilizzare uno spatial access method per ottenere risultati più veloci rispetto alla scansione sequenziale

l'idea alla base di questo metodo è quella di trovare una trasformazione che non distorce le distanze (l'ideale sarebbe una trasformazione che le mantiene uguali, in pratica si determina una distanza che è un limite inferiore) per garantire l'assenza di falsi negativi.

[...]



ecco il punto! per effettuare l'alternativa faster ho bisogno di una trasformazione che non mi altera le distanze. io invece pensavo che attraverso la trasformata ero sicuro di prendere tutti i dati significativi, invece il problema era il contrario: determinare un modo più veloce di potatura che però mi conservi la correttezza dei dati

grazie per il tempo che mi hai dedicato. ^^