Uno dei più importanti problemi affrontati nella progettazione di database di immagini consiste nel trovare un’appropriata 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’immagine 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’anomalia 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.

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

La virtual image di un’immagine 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.

• Ob = {ob₁,...,ob_n} è un’insieme di oggetti di im
• Rel = {Rel_x, Rel_y} è una coppia di insiemi di relazione binarie spaziali su Ob, dove Rel_x (risp. Rel_y) contiene sottoinsiemi reciprocamente disgiunti di Ob ´ Ob che esprimono la relazione ‘ < ’,’ | ’,’ = ’,’ [ ‘,’ ] ’,’ / ’,’ % ’ che c’è tra le coppie degli oggetti di im lungo la proiezione sull’asse delle ascisse (risp. ordinate).

O = {A, B, C, D}

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

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

Per catturare la natura fuzzy della sistemazione spaziale degli oggetti, per grado di similitudine tra una query Q ed una virtual image im_vi consideriamo il fatto che coppie di oggetti di Q possono avere relazioni spaziali diverse in im_vi, considerando che Q e im_vi 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’oggetto B è alla destra dell’oggetto A. Diversamente l’operatore totalmente contenuto (%) e l’operatore disgiunto (<) sono intuitivamente molto differenti.

Poiché la massima distanza nell’interval neighborhood graph è 4 e la minima è 0, il valore di somiglianza sim(g ₁, g ₂) può essere definito come:

sim(g ₁, g ₂) = 1 - (distance(g ₁, g ₂) / 4)

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

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

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

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 im_vi , possibilmente con differenti relazioni spaziali. Così viene scelto il più alto valore di grado di similitudine.

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’insieme di immagini su cui applicare la funzione di somiglianza si procede al controllo della validità delle due condizioni:

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:

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’inclusione nel set di risposta di una notevole quantità di false allarms, in contraddizione con l’obiettivo di ridurre quanto più possibile il sottoinsieme di immagini dell’archivio 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.

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

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

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

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

O = {a, 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}

presenta, tra gli oggetti a e c, una relazione lungo l’asse 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

la corrispondente Virtual Image.

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

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}

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

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

che non soddisfa le suddette condizioni, a causa della diversa relazione tra l’anomalia O e la sezione della spina B lungo l’asse 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’ulteriore 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’insieme 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’insieme G e le condizioni relative agli oggetti di F, facendo in modo che l’unico 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’utilizzo di nuove condizioni di taglio sulle relazioni spaziali, stabilite sulla base della diversa interpretazione del concetto di similitudine.

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

Formalmente, abbiamo la seguente:

Definizione 3.5. Data una query:

una Virtual Image:

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

- F Í O

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

dove t Î [0, 1] è detta ‘soglia di minima somiglianza’ tra gli operatori.

Il valore t viene stabilito dall’utente 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’organizzazione 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’insieme dei codici identificatori delle Virtual Images (VIID) che contengono proprio quella tripla. Il set di risposta finale sarà ricavato dall’intersezione di tutti gli insiemi di VIID associati alle singole triple della query. Ma, poiché lo scopo non è quello di effettuare ricerche basate sull’exact 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

- 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’appendice del presente lavoro vengono descritti i dettagli dell’implementazione 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’intersezione 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’ampiezza del set di risposta attraverso un meccanismo di tagli successivi. Infatti, le relazioni spaziali dell’anomalia rispetto ad ognuno di tali oggetti selezionano una regione dell’immagine, e l’intersezione di tutte le regioni individua, con buona approssimazione, la posizione in cui l’anomalia deve essere localizzata nelle immagini restituite, affinché tali immagini possano essere ritenute simili.

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

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’immagine query viene calcolato applicando la funzione Sim_deg dopo aver ad essa apportatto le modifiche discusse in precedenza, ossia

l’eliminazione dell’insieme G e delle condizioni (1a) e (1b).

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’anomalia 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’immagine 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’insieme 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’immagine e la query.