Capitolo 3

Accesso alle immagini per contenuto spaziale.

Le Virtual Images e Query by Icons.

 

 

 

Uno dei più importanti problemi affrontati nella progettazione di database di immagini consiste nel trovare un誕ppropriata descrizione delle immagini per il loro salvataggio ed eventuale recupero. Un primo approccio è stato fatto nel capitolo precedente, adesso ci interessiamo non solo della singola anomalia, ma dell段mmagine completa e di tutti gli oggetti in essa contenuti.

In effetti, ad ogni immagine associamo una quantità di oggetti, dei quali non interessa la forma, bensì la loro posizione e la loro grandezza. In questo modo le informazioni che noi andiamo a registrare nel database non saranno relative alla forma, ma alle relazioni spaziali che intercorrono tra i vari oggetti.

Verrà quindi illustrato un algoritmo generale per il recupero delle immagini e sarà menzionato il nostro caso particolare, dove per oggetti particolari quali gli organi del corpo umano le relazioni spaziali sono sempre le stesse, mentre cambiano le relazioni tra questi e l誕nomalia di cui sappiamo anche le caratteristiche geo-morfologiche.

In questo modo possiamo ulteriormente filtrare il database in fase di recupero o comunque scegliere la modalità, se per caratteristiche geo-morfologiche o per relazioni spaziali rispetto agli oggetti canonici.

 

3.1 Indice iconico delle immagini

L段ndice iconico che associamo alle immagini è una descizione virtuale chiamata virtual image[29,30].

La virtual image di un段mmagine reale consiste di un insieme di oggetti ed un insieme di relazioni binarie tra gli oggetti. Per rappresentare i tredici tipi di relazione (vedi figura 3.1) in ogni dimensione, usiamo un insieme di relazioni spaziali {<,|,=,[,],%,/} definite nella tabella 3.2 in termini di punti di inizio e di fine degli oggetti coinvolti.

 

Notazione

Significato

Condizione

A<B

A disgiunto B

End(A) < Begin(B)

A=B

A ha gli stessi punti di inizio e di fine di B

Begin(A)=Begin(B)

End(A)=End(B)

A|B

A è edge-to-edge con B

End(A)=Begin(B)

A%B

A e B non hanno gli stessi confini e A contiene B

Begin(A)<Begin(B)

End(A)>End(B)

A[B

A e B hanno lo stesso punto di inizio ma A contiene B

Begin(A)=Begin(B)

End(A)>End(B)

A]B

A e B hanno lo stesso punto di fine ma A contiene B

Begin(A)<Begin(B)

End(A)=End(B)

A/B

A è parzialmente sovrapposto a B

Begin(A)<Begin(B)

<End(A)<End(B)

Definizione 3.1.Data un段mmagine reale im, la virtual image ad essa associata imvi è una coppia (Ob,Rel) dove:

Come esempio possiamo notare che la virtual image associata alla figura 3.3 è la seguente

O = {A, B, C, D}

Rx = {A<O, B<O, C<O, D%O}

Ry = {A%O, B<O, C%O, D%O}.

 

3.2 Query by icons.

Per catturare la natura fuzzy della sistemazione spaziale degli oggetti, per grado di similitudine tra una query Q ed una virtual image imvi consideriamo il fatto che coppie di oggetti di Q possono avere relazioni spaziali diverse in imvi, considerando che Q e imvi hanno lo stesso contesto visuale. Quindi assumiamo che il valore di similitudine sim(g1,g2)Î [0,1] sia definito tra ogni coppia (g1,g2) di relazioni spaziali. Per esempio gli operatori | e < possono essere considerati molto simili dato che sia A<B e A|B indicano che l弛ggetto B è alla destra dell弛ggetto A. Diversamente l弛peratore totalmente contenuto (%) e l弛peratore disgiunto (<) sono intuitivamente molto differenti.

Per costruire una tabella delle somiglianze è necessario stabilire la distanza tra i nuovi operatori spaziali. Per far ciò è stato adoperato l段nterval neighborhood graph[29,30], in cui due relazioni si definiscono vicine se possono essere trasformate l置na nell誕ltra deformando in maniera continua, ovvero accorciando, allungando e muovendo le proiezioni degli oggetti. La figura 3.4 mostra un grafo di vicinanza per le relazioni corrispondenti agli operatori spaziali della tavola 3.2, dove i nodi rappresentano le relazioni e gli archi la loro vicinanza. La distanza tra due relazioni, denotata con distance(g 1, g 2), è definita come la lunghezza del cammino più breve tra i corrispondenti nodi nel grafo.

Poiché la massima distanza nell段nterval neighborhood graph è 4 e la minima è 0, il valore di somiglianza sim(g 1, g 2) può essere definito come:

sim(g 1, g 2) = 1 - (distance(g 1, g 2) / 4)

per ogni coppia (g 1, g 2) di relazioni spaziali.

Nel nostro caso la funzione sim è definita nella tavola 3.5.

Il grado di similitudine tra una query Q ed una virtual image imvi, denotata SIM_deg(Q, imvi), è calcolata in base ad una formula che tiene conto di quanti oggetti sono contenuti in Q e imvi e delle relazioni spaziali che essi hanno sia in Q sia in imvi, e ritorna un valore compreso nel range [0,1].

Definizione 3.2. Una query su relazioni spaziali Q è una 4-tupla (F,G,Rel,t) dove ({FÈ G},Rel) è una virtual image e tÎ [0,1] è la soglia del grado di similitudine.

Nella definizione precedente F è l段nsieme di oggetti obbligatori: un段mmagine im del database soddisfa la query Q solo se la sua virtual image imvi contiene tutti gli oggetti di F, con le stesse relazioni spaziali che hanno in Q. G è un段nsieme di oggetti opzionali: intuitivamente, il grado di similitudine tra Q e im cresce se qualche oggetto in G è contenuti in imvi. L置ltima componente, t, è un parametro che indica il minimo grado di similitudine richiesto.

Definizione 3.3. Sia Q=(F,G,Rel,t) una query con F={q1,...,qn} e G={qn+1,...,n+m} e Rel=(RelX,RelY), e sia imvi=(Obim,Relim) una virtual image di un段mmagine im. Con (risp. ) denotiamo il sottoinsieme di RelX (risp. RelY) composti da tutte le relazioni spaziali tra le coppie di oggetti di F lungo la proiezione sull誕sse delle ascisse (risp. ordinate). Gli insiemi X e Y indicano il più alto valore di similitudine tra ogni coppia di relazioni atomiche come segue:

Gli insiemi X e Y sono calcolati in relazione al fatto che gli oggetti richiesti in una query possono apparire più di una volta in una virtual image imvi , possibilmente con differenti relazioni spaziali. Così viene scelto il più alto valore di grado di similitudine.

Definizione 3.4. Siano Q e imvi definite come nella definizione 3.3, allora il grado di similitudine tra Q e imvi , denotato da Sim_deg(Q, imvi) è definito dalla formula:

 

3.3 La strategia di ricerca proposta

Il concetto di somiglianza tra immagini

Il metodo utilizzato nella fase di ricerca basata sulle relazioni spaziali, prevede che a partire da un段mmagine query si estrapolino dal database tutte le immagini che presentano un誕nomalia la cui posizione, rispetto agli altri oggetti presenti nella scena pittorica, è simile a quella specificata nella query. Il sistema, poi, fornirà un ordinamento delle immagini comprese nel set di risposta in base al grado di somiglianza che esse presentano rispetto alla query, in modo tale che l置tente medico possa selezionare da tale insieme solo quelle la cui somiglianza supera la soglia che egli stesso ha stabilito. E necessario, quindi, definire delle condizioni che permettano, a partire dalle caratteristiche della query in input, di riconoscere a priori le Virtual Image nel database il cui grado di similarità rispetto alla query sia maggiore di zero e tagliar fuori dal calcolo della funzione di somiglianza quelle che, non soddisfacendo tali condizioni, non faranno parte del set di risposta.

Una volta individuato il blocco su cui mirare la ricerca attraverso la verifica degli oggetti presenti nella scena pittorica (FÍ O), per ridurre ulteriormente l段nsieme di immagini su cui applicare la funzione di somiglianza si procede al controllo della validità delle due condizioni:

RXF Í RXVI (1a)

RYF Í RYVI (1b)

le quali garantiscono che la funzione Sim_deg(Q, VI) sia maggiore di zero.

In realtà, però, le condizioni applicate non sono le (1a), (1b) bensì le seguenti:

num(g , RxF) < = num(g , RxVI), " g Î Op (2a)

num(g , RYF) < = num(g , RYVI), " g Î Op (2b);

queste sono condizioni necessarie ma non sufficienti affinché valgano le condizioni effettive (1a), (1b), e che fanno sì che una Virtual Image sia inserita nel set di risposta solo se, per entrambi gli assi cartesiani, il numero di volte che un determinato operatore spaziale compare in essa coincide, o è maggiore, del numero di volte in cui lo stesso operatore compare nella query, indipendentemente dalla coppia di oggetti che tale operatore mette in relazione. Come verrà evidenziato dagli esempi che seguono, ciò può comportare l段nclusione nel set di risposta di una notevole quantità di false allarms, in contraddizione con l弛biettivo di ridurre quanto più possibile il sottoinsieme di immagini dell誕rchivio su cui applicare la funzione di somiglianza Sim_deg. Tuttavia, utilizzando una tale strategia di selezione non si corre alcun rischio di false dismissal in quanto le immagini soddisfacenti le suddette condizioni includeranno certamente anche tutte quelle per le quali la corrispondenza tra gli operatori cercati e le coppie di oggetti di F è esattamente quella specificata nella query.

Esempio:

Data la query Q = (F, G, Rel, d) mostrata in (Fig. 3.6) dove

F = {a, c} G = {b}

Rx = { c / a, c < b, a < b}

Ry = {a / b, b < c, a < c}

l段mmagine di figura 3.7 verrà inclusa nel set di risposta, mentre l段mmagine di figura 3.8 ne verrà esclusa.

Questo si verifica perché all段mmagine di fig. 3.7 è associata la Virtual Image

O = {a, b, c}

Rx = {c / a, c < b, a | b} RY = {a < c, a < b, b [ c}

in cui, come si può notare, vengono mantenute le stesse relazioni tra gli oggetti di F, mentre la Virtual Image che codifica la figura 3.8

O = {a, b, c}

Rx = {a % c, c < b, a < b} RY = {a < c, a / b, b < c}

presenta, tra gli oggetti a e c, una relazione lungo l誕sse x diversa da quella richiesta nella query.

Nel caso in cui ci sia un motivo per reputare diverse due immagini apparentemente così simili questo modo di procedere garantisce ottimi risultati.

Tuttavia, se si vuole che la misura di similitudine esprima il concetto umano di somiglianza è necessario, a nostro avviso, che il criterio di selezione divenga più elastico, affinché si possa includere nel set di risposta anche quelle immagini che presentano una relazione leggermente diversa fra gli oggetti di F. In molti campi di applicazione, ed in modo particolare nel caso di immagini mediche, infatti, due immagini possono essere ritenute simili se presentano gli stessi oggetti e se tali oggetti sono arrangiati allo stesso modo nella scena pittorica ma, ciò non significa che presentano la stessa relazione spaziale tra tali oggetti. Consideriamo, ad esempio, la seguente situazione; sia:

la query grafica in input, e

F= {A, B, D, O} G= {C}

Rx = {A%O, O<B, O<C, O<D}, RY = {A%O, B%O, O<C, D%O}

la corrispondente Virtual Image.

La strategia di selezione adoperata da [4] richiede che le immagini del set di risposta soddisfino le seguenti condizioni:

num(<, RXVI) >= 2

num(%, RXVI) >= 1

num(%, RYVI) >= 3

Il sistema, quindi, selezionerà come potenziale elemento del set di risposta la seguente immagine:

a cui corrisponde la Virtual image:

O = {A, B, C, D, O}

RXVI = {A<O, B%O, O|C, O<D}, RYVI = {A%O, B%O, O<C, D%O}

mentre escluderà immagini molto simili alla query come, ad esempio, la seguente:

in quanto tale immagine corrisponde alla Virtual Image:

O = {A, B, C, D, O}

Rx = {A%O, O<B, O<C, O<D}, RY = {A%O, B/O, O<C, D%O}

che non soddisfa le suddette condizioni, a causa della diversa relazione tra l誕nomalia O e la sezione della spina B lungo l誕sse y.

Quindi, per effettuare una ricerca per somiglianza non può essere eseguito un match esatto per cui la definizione di query e di funzione di somiglianza non sono più adatte per i nostri scopi e di conseguenza devono essere modificate. Oltre al fatto che tra gli oggetti di F si richiedono relazioni identiche rispetto alle immagini del database, la divisione degli oggetti della query nei due insiemi F e G, genera un置lteriore difficoltà in quanto solo un medico è in grado di stabilire quali siano gli oggetti appartenenti a F e quali a G, rendendo inevitabile questa inutile interazione. Risolvere questi problemi eliminando l段nsieme F ed includendo tutti gli oggetti della query in G renderebbe la ricerca non più mirata perché, essendo F vuoto, le condizioni  F Í O, (1a), (1b) continuerebbero a valere. I problemi vengono, invece, risolti eliminando l段nsieme G e le condizioni relative agli oggetti di F, facendo in modo che l置nico criterio di selezione delle immagini su cui applicare la funzione di somiglianza rimanga quello relativo agli oggetti presenti nella scena pittorica (FÍ O). Ma nel nostro specifico campo di applicazione, in cui gli oggetti presenti sono sempre gli stessi, tale criterio risulta ancora del tutto inefficiente.

In ciò che segue sarà illustrato come il problema è stato da noi affrontato e risolto, attraverso l置tilizzo di nuove condizioni di taglio sulle relazioni spaziali, stabilite sulla base della diversa interpretazione del concetto di similitudine.

La logica del motore di ricerca

Gli esperti del settore reputano due immagini simili se presentano gli stessi oggetti ed inoltre, le relazioni spaziali tra l誕nomalia e ciascuno di tali oggetti in un段mmagine sono simili, secondo la tabella delle somiglianze precedentemente definita, alle corrispondenti relazioni spaziali nell誕ltra immagine.

Formalmente, abbiamo la seguente:

Definizione 3.5. Data una query:

Q = (F, RqX, RqY, d) = { (objq1, relq1x, relq1Y), ..., (objqn, relqnx, relqnY), d}, dove n=|F|,

una Virtual Image:

VI = (O, RXVI, RYVI) = { (objVI1, relxVI1, relYVI1), ...,(objvm, relXVIm, relYVIm)}, con m>=n,

è simile alla query Q se e solo se sono soddisfatte le seguenti condizioni:

- F Í O

- relXVIj Î Sim-op(relxqj), " j Î [1, n]

- relYVIj Î Sim-op(relYqj), " j Î [1, n],

con:

Sim-op (g ) = {g Î Op| sim(g , g ) >= t }

dove t Î [0, 1] è detta 壮oglia di minima somiglianza tra gli operatori.

Il valore t viene stabilito dall置tente in fase di query per regolare la rigidità del criterio di matching. Ovviamente se t = 1 il sistema eseguirà una ricerca per exact match.

Per consentire un retrieval efficiente basato sul tipo di match appena definito, i dati devono essere opportunamente organizzati. In particolare, si è ritenuto conveniente raggruppare le Virtual Images del database in modo da mantenere vicine quelle che condividono la stessa tripla (oggetto, relazione-x, relazioney), dando origine all弛rganizzazione che segue:

Data una query, sotto forma di un insieme di triple ordinate, la logica del motore di ricerca consiste nel considerare singolarmente ognuna di tali triple, individuarne la locazione nel database, servendosi di un indice opportunamente costruito, ed accedere direttamente all段nsieme dei codici identificatori delle Virtual Images (VIID) che contengono proprio quella tripla. Il set di risposta finale sarà ricavato dall段ntersezione di tutti gli insiemi di VIID associati alle singole triple della query. Ma, poiché lo scopo non è quello di effettuare ricerche basate sull弾xact match è necessaria una fase di elaborazione preliminare che consiste nel generare per ogni tripla nella query tutte le triple ad essa simili, in accordo alla seguente definizione:

Definizione

Una tripla (obj1, relx1, rely1) è simile alla tripla (obj2, relx2, rely2) se e solo se:

- obj1 = obj2

- relx1 Î Simil-op(relx2)

- rely1 Î Simil-op(rely2)

E importante sottolineare che la generazione delle triple simili non è un passo computazionalmente oneroso, come poi si mostrerà attraverso i risultati sperimentali, grazie alla possibilità di organizzare i dati in modo che un qualunque operatore sia memorizzato fisicamente insieme ai suoi somiglianti. Nell誕ppendice del presente lavoro vengono descritti i dettagli dell段mplementazione e le strutture dati utilizzate nello sviluppo di ITSS.

Una volta generate le triple simili a quelle estratte dalla query è possibile, come prima, accedere velocemente ai corrispondenti insiemi dei VIID delle Virtual Images, a partire da ognuna di esse. Quindi, ad ogni tripla nella query verrà associato un insieme di VIID, che contengono tale tripla o triple somiglianti, ed il set di risposta finale sarà dato dall段ntersezione di tutti questi insiemi, ottenuti considerando una per una tutte le triple che costituiscono la query.

Considerando uno alla volta gli oggetti della query, o meglio le triple che la costituiscono, si restringe gradualmente l誕mpiezza del set di risposta attraverso un meccanismo di tagli successivi. Infatti, le relazioni spaziali dell誕nomalia rispetto ad ognuno di tali oggetti selezionano una regione dell段mmagine, e l段ntersezione di tutte le regioni individua, con buona approssimazione, la posizione in cui l誕nomalia deve essere localizzata nelle immagini restituite, affinché tali immagini possano essere ritenute simili.

Si capisce, quindi, che maggiore è il numero di oggetti che l置tente medico specifica nella query, maggiore sarà il livello di dettaglio nella ricerca in quanto meno ampia è la regione individuata dall段ntersezione.

Una nuova funzione di somiglianza

Al termine della fase di ricerca basata sulle relazioni spaziali, il sistema avrà selezionato un insieme di immagini il cui grado di somiglianza rispetto all段mmagine query viene calcolato applicando la funzione Sim_deg dopo aver ad essa apportatto le modifiche discusse in precedenza, ossia

l弾liminazione dell段nsieme G e delle condizioni (1a) e (1b).

A questo punto, però, è ancora possibile fare qualche altra considerazione. Nel nostro specifico campo di applicazione, poiché si considerano solo le relazioni spaziali tra l誕nomalia e gli oggetti canonici, si avrà |F| = |RXF| = |RYF| = |RX| = |RY|.

Inoltre, la condizione F Í O è sicuramente verificata per le immagini che appartengono al sottoinsieme selezionato applicando i criteri di matching esaminati in precedenza. Di conseguenza le immagini per cui la funzione Sim_deg assume valore zero sono già state tagliate fuori dal set di risposta. Alla luce di queste considerazioni la funzione diventa

Secondo tale funzione se due immagini presentano esattamente gli stessi oggetti, ma tra tali oggetti esistono relazioni spaziali tali che:

il valore della Sim_deg sarà:

Nel caso generale due immagini abbiano esattamente gli stessi oggetti, a prescindere dalle loro posizioni relative, è già sufficiente per definirle simili e la funzione Sim_deg così come definita esprime questa situazione. Ma, nel nostro specifico campo di applicazione le immagini costituite da Tac polmonari presentano tutte gli stessi oggetti e sono le relazioni spaziali tra l誕nomalia e tali oggetti a renderle più o meno simili; per cui il valore 3/5 risultante dal calcolo della Sim_deg per immagini le cui relazioni spaziali sono totalmente diverse da quelle della query, risulta eccessivamente alto per esprimere il loro effettivo grado di somiglianza rispetto alla query stessa.

Si è pensato, quindi, di modificare la funzione di somiglianza in modo tale che potesse assumere valore uguale a zero nel caso in cui non esista alcuna somiglianza tra le relazioni spaziali dell段mmagine e della query. La nuova funzione di somiglianza risulta essere:

dove il valore 2|F| al denominatore è giustificato dalla necessità di normalizzare la sommatoria rispetto alla cardinalità dell段nsieme di relazioni spaziali della query lungo entrambi gli assi, in modo da avere valore 1 in caso di exact match.

E questa, dunque, la funzione di somiglianza che abbiamo utilizzato per calcolare il grado di similarità tra un段mmagine e la query.

Home