Estrazione real-time di caratteristiche immagine di basso livello a bordo di telecamera

UNIVERSITA DEGLI STUDI DI FIRENZEFacolta di Ingegneria - Dipartimento di Sistemi e Informatica

Tesi di laurea in Ingegneria Informatica

Estrazione real-time dicaratteristiche immagine di bassolivello a bordo di telecamera

CandidatoLeonardo Galteri

RelatoriProf. Alberto Del Bimbo

Ing. Marco Bertini

CorrelatoreIng. Lorenzo Seidenari

Anno Accademico 2010/2011

A mio padre

i

Indice

1 Introduzione 1

1.1 Feature Locali . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Estrattori di feature . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Obiettivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Struttura della tesi . . . . . . . . . . . . . . . . . . . . . . . 6

2 Rilevamento di feature 7

2.1 FAST Corner Detection . . . . . . . . . . . . . . . . . . . . . 7

2.1.1 Cerchio di Bresenham . . . . . . . . . . . . . . . . . . 8

2.1.2 Il criterio Segment Test . . . . . . . . . . . . . . . . . 9

2.1.3 Original FAST . . . . . . . . . . . . . . . . . . . . . . 10

2.1.4 Generic FAST . . . . . . . . . . . . . . . . . . . . . . 13

2.1.5 Learned FAST . . . . . . . . . . . . . . . . . . . . . . 16

2.1.6 Punteggio e soppressione dei non massimi . . . . . . . 17

2.1.7 Stima di ripetitivita . . . . . . . . . . . . . . . . . . . 19

2.2 Rilevamento dei contorni . . . . . . . . . . . . . . . . . . . . 20

2.2.1 Gradiente . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.2 Sviluppo del rilevamento contorni . . . . . . . . . . . 23

2.2.3 Operatore di Sobel . . . . . . . . . . . . . . . . . . . 24

2.2.4 Quantizzazione . . . . . . . . . . . . . . . . . . . . . 26

3 Data mining 30

3.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.1 Misura di clustering . . . . . . . . . . . . . . . . . . . 33

3.1.2 Algoritmi di clustering . . . . . . . . . . . . . . . . . 35

ii

3.2 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2.1 Metodi di inizializzazione . . . . . . . . . . . . . . . . 41

3.2.2 Diagramma di Voronoi . . . . . . . . . . . . . . . . . 43

3.3 Validita dei cluster . . . . . . . . . . . . . . . . . . . . . . . 44

3.3.1 Concetti fondamentali . . . . . . . . . . . . . . . . . 44

3.3.2 Indici di validita . . . . . . . . . . . . . . . . . . . . . 45

4 Sviluppo del Software 49

4.1 Piattaforma Axis . . . . . . . . . . . . . . . . . . . . . . . . 50

4.1.1 Specifiche P1343 . . . . . . . . . . . . . . . . . . . . . 50

4.1.2 Codec video . . . . . . . . . . . . . . . . . . . . . . . 51

4.1.3 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2 Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2.1 Esecuzione dell’applicazione . . . . . . . . . . . . . . 54

4.2.2 Acquisizione delle immagini . . . . . . . . . . . . . . 56

4.2.3 Esecuzione algoritmi . . . . . . . . . . . . . . . . . . 58

4.2.4 Interfaccia di rete . . . . . . . . . . . . . . . . . . . . 62

4.3 Interfaccia utente . . . . . . . . . . . . . . . . . . . . . . . . 65

4.3.1 Tecnologia AJAX . . . . . . . . . . . . . . . . . . . . 66

4.3.2 XMLHttpRequest . . . . . . . . . . . . . . . . . . . . 67

4.3.3 Streaming dei dati . . . . . . . . . . . . . . . . . . . 70

4.3.4 Interfaccia grafica . . . . . . . . . . . . . . . . . . . . 73

4.4 Metodi di trasmissione . . . . . . . . . . . . . . . . . . . . . 78

4.4.1 Codifica dei dati . . . . . . . . . . . . . . . . . . . . . 78

4.4.2 Multipart Mixed-Replace . . . . . . . . . . . . . . . . 82

5 Risultati Sperimentali 83

5.1 Valutazione della performance . . . . . . . . . . . . . . . . . 85

5.2 Velocita di esecuzione . . . . . . . . . . . . . . . . . . . . . . 86

5.2.1 Stima di analisi senza rappresentazione . . . . . . . . 87

5.2.2 Stima di analisi con rappresentazione . . . . . . . . . 91

5.2.3 Modifica del frame rate di acquisizione . . . . . . . . 94

5.3 Compressione dei dati . . . . . . . . . . . . . . . . . . . . . . 96

iii

6 Conclusioni e sviluppi futuri 99

A Codice sorgente dell’algoritmo Generic FAST 103

A.1 Fast.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

A.2 Fast.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

A.3 Fast9.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

A.4 Nonmax.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

A.5 Pixel.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

B Software Development Kit 116

B.1 Compilatore CRIS . . . . . . . . . . . . . . . . . . . . . . . . 116

B.2 Installazione SDK . . . . . . . . . . . . . . . . . . . . . . . . 117

B.3 Creazione del package . . . . . . . . . . . . . . . . . . . . . . 117

B.4 Upload sulla camera . . . . . . . . . . . . . . . . . . . . . . . 118

B.5 Interfacce dell’SDK . . . . . . . . . . . . . . . . . . . . . . . 119

Bibliografia 121

Ringraziamenti 129

iv

Elenco delle figure

2.1 Cerchio di Bresenham di raggio 3 . . . . . . . . . . . . . . . . 9

2.2 Esempio del criterio Segment Test per n = 9 e n = 12 . . . . . 10

2.3 Algoritmi FAST a confronto . . . . . . . . . . . . . . . . . . . 15

2.4 L’effetto dell’eliminazione dei non massimi . . . . . . . . . . . 19

2.5 Il funzionamento dell’operatore di Sobel e le componenti del

gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.6 Quantizzazione dell’immagine ottenuta con Sobel . . . . . . . 27

2.7 Thresholding dell’immagine al variare della soglia t . . . . . . 29

3.1 Esempio di dendrogramma . . . . . . . . . . . . . . . . . . . . 36

3.2 Algoritmo di Lloyd . . . . . . . . . . . . . . . . . . . . . . . . 39

3.3 Diagramma di Voronoi . . . . . . . . . . . . . . . . . . . . . . 44

4.1 La camera Axis P1343 . . . . . . . . . . . . . . . . . . . . . . 50

4.2 Il diagramma degli stati dell’applicazione . . . . . . . . . . . . 55

4.3 Il funzionamento di XMLHttpRequest . . . . . . . . . . . . . 69

4.4 Client Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.5 Server Push . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.6 Rappresentazione dei corner . . . . . . . . . . . . . . . . . . . 74

4.7 Rappresentazione degli edge . . . . . . . . . . . . . . . . . . . 75

5.1 Le scene utilizzate per misurare la performance dell’applicazione 84

5.2 Quantita di corner rilevati in una scena molto dettagliata . . . 85

5.3 Tempi di esecuzione in una scena di medio dettaglio . . . . . . 88

5.4 Performance dell’algoritmo FAST . . . . . . . . . . . . . . . . 89

5.5 Performance dell’algoritmo Sobel . . . . . . . . . . . . . . . . 90

v

5.6 Performance dell’algoritmo k-means . . . . . . . . . . . . . . . 92

5.7 Differenza di performance . . . . . . . . . . . . . . . . . . . . 93

5.8 Tempo di esecuzione di FAST al variare del tasso di acquisizione 95

5.9 Dimensione media delle immagini codificate . . . . . . . . . . 96

5.10 Confronto della codifica Run-length su scene diverse . . . . . . 98

vi

Elenco degli algoritmi

1 Original FAST n = 12 and r = 3 . . . . . . . . . . . . . . . . 11

2 Generic FAST n = 9 and r = 3 . . . . . . . . . . . . . . . . . 14

vii

Sommario

La realizzazione di tecniche di visione computazionale in grado di rileva-

re caratteristiche immagine di basso livello e un argomento che ha ricevuto

una grande attenzione nella comunita scientifica. Metodi sempre piu inno-

vativi hanno permesso di eseguire l’estrazione dei punti di interesse in tem-

po reale consentendo lo sviluppo di applicazioni complesse nell’ambito della

videosorveglianza.

Questo lavoro di tesi studia alcune tecniche di rilevazione e fornisce inoltre

i seguenti contributi:

• La creazione di una variante di un algoritmo di rilevazione corner che

si adatta perfettamente a qualsiasi tipo di immagine e che mantiene le

caratteristiche di velocita e robustezza.

• L’applicazione di una tecnica di clustering per l’interpretazione dei

punti di interesse estratti e lo studio di metodi di inizializzazione e

di validazione di tale metodo.

• Lo sviluppo di una applicazione per una telecamera di videosorveglian-

za finalizzata all’estrazione delle feature in tempo reale mediante le

suddette tecniche.

• La realizzazione di un sistema client-server per la rappresentazione dei

punti di interesse rilevati dall’applicazione.

• L’analisi delle prestazioni e del carico di trasmissione dell’applicazione.

Capitolo 1

Introduzione

Il settore della visione artificiale ha subito negli ultimi anni un processo di

continuo sviluppo, ed e stato oggetto di numerosi studi. Tecniche di elabo-

razione di immagini sempre piu performanti sono state studiate per la riso-

luzione di problemi in molti ambiti di ricerca e implementate su macchine

sempre piu potenti.

La recente evoluzione tecnologica ha inoltre favorito la creazione e la dif-

fusione sempre maggiore di dispositivi digitali per l’acquisizione video, come

ad esempio fotocamere, webcam e telefoni cellulari di ultima generazione.

Le telecamere di videosorveglianza hanno avuto un forte sviluppo in questo

contesto. Alla fine degli anni ’90 inizia l’era della videosorveglianza basata

su dispositivi digitali andando a sostituire la precedente tecnologia analogi-

ca. Il cavo coassiale usato dalle camere a circuito chiuso non e piu adatto

al trasferimento dei dati, viene quindi utilizzato lo standard Ethernet per il

trasferimento dati sul protocollo TCP/IP.

L’evoluzione della videosorveglianza digitale con le nuove telecamere, chia-

mate IP, ha permesso la completa integrazione di questi sistemi nelle reti

di calcolatori moderne, favorendone la diffusione. Inoltre la possibilita di

trattare le immagini come dati digitali ha favorito il continuo sviluppo di

applicazioni di elaborazione ed analisi che lavorano in tempo reale. Fanno

parte di questo ambito le applicazioni che rilevano feature di basso livello.

1

CAPITOLO 1. INTRODUZIONE

1.1 Feature Locali

Una feature locale e una parte di immagine che differisce dalle zone circo-

stanti ad essa. Tipicamente e associata alla variazione di una o piu proprieta

dell’immagine, compresi intensita e colore. Le feature possono essere semplici

punti ma anche contorni o piccole zone dell’immagine stessa.

Di seguito diamo le possibili definizioni di edge e corner al fine di miglio-

rare l’intera comprensione del testo.

Definizione 1.1.1 (Edge) Si parla di edge o contorno quando esiste un

confine tra due regioni di un’immagine.

In generale gli edge possono essere di qualsiasi forma. Una definizione piu

formale e adeguata al contesto della visione computazionale puo essere:

Definizione 1.1.2 (Edge) Un edge o contorno e l’insieme dei punti del-

l’immagine il cui gradiente ha intensita elevata.

Anche i corner possono avere diverse interpretazioni:

Definizione 1.1.3 (Corner) Un corner o angolo e l’intersezione di due

edge.

Oppure piu genericamente:

Definizione 1.1.4 (Corner) Un corner o angolo e un punto per il quale

esistono due edge nella zona circostante che hanno direzioni differenti.

Le feature locali costituiscono un potente strumento che viene utilizzato

in un’ampia gamma di sistemi ed applicazioni. Le motivazioni di impiego

possono essere molteplici e dipendono dal contesto in cui si lavora. Per prima

cosa si puo focalizzare l’interesse su alcune tipologie di feature locali poiche

esse possono assumere particolari interpretazioni semantiche nel contesto di

una applicazione. Ad esempio gli edge rilevati da fotografie aeree possono

corrispondere a strade [71].

In secondo luogo le feature possono rappresentare un insieme limitato di

punti localizzati e individuabili singolarmente, tali che la loro posizione possa

2


essere valutata con precisione in ogni istante nel tempo. Questo e il caso delle

applicazioni di riconoscimento [9, 64] e tracciamento oggetti [36,66].

Infine un insieme di feature locali puo anche essere usato per la rappresen-

tazione di un’immagine che permetta di riconoscere oggetti o scene particolari

senza ricorrere all’uso della segmentazione. In questo caso quindi l’attenzio-

ne viene posta sull’analisi statistica dei punti caratteristici. Questo modo di

impiego delle feature locali e stato introdotto da Schiele e Crowley [55] e poi

anche da Schmid e Mohr [56].

Vale la pena ricordare il fatto che le feature locali hanno un ruolo centrale

anche nel riconoscimento di oggetti da parte del sistema visivo umano [11].

1.2 Estrattori di feature

Nel campo della visione computazionale e dell’elaborazione di immagini, il

concetto di estrazione di feature si riferisce a quei metodi il cui scopo e quello

di analizzare i pixel presenti nell’immagine mediante operatori matematici

al fine di decidere sulla presenza dei punti di interesse cercati. Le feature

risultanti sono un sottoinsieme del dominio dell’immagine, spesso sotto forma

di punti isolati, curve continue oppure regioni interconnesse.

Gli estrattori di feature possono essere classificati in base al tipo di

caratteristica rilevata:

• Rilevatori di contorni o edge;

• Rilevatori di angoli o corner ;

• Rilevatori di regioni o blob;

Rilevatori di angoli

Il primo rilevatore di corner risale al 1977 per opera di Moravec [41, 42].

Lo scopo era quello di studiare la similarita tra una determinata zona e le

regioni circostanti ad essa, usando come misura la somme dei quadrati delle

differenze. Beaudet propose una misura per il riconoscimento dei corner

basata sul determinante della matrice Hessiana [10].

3


Kitchen e Rosenfeld [34] furono i primi ad introdurre gli operatori della

geometria differenziale per la risoluzione di questo tipo di problema. Il rile-

vamento in questo caso si basava sulla misura della direzione del gradiente

lungo un egde.

Harris e Stevens [23] introdussero un operatore, derivandolo dal rilevatore

di Moravec,che considera una finestra locale nell’immagine e determina la me-

dia delle variazioni di intensita ottenute traslando tale finestra di poche posi-

zioni nelle varie direzioni. Zheng and Wang [78] migliorarono questo metodo

proponendone una versione meno onerosa dal punto di vista computazionale.

Wang e Brady [72] proposero un metodo per rilevare i corner basato

sulla misurazione delle curvature superficiali, agevolando inoltre l’estrazione

in tempo reale.

Un algoritmo piu recente, il SUSAN [60], da vita ad un nuovo tipo di

rilevatori di corner basati sul paragone di intensita di pixel all’interno di una

maschera circolare. Trajkovic e Hedley [70] hanno proposto un rilevatore

che usa la stessa intuizione dell’operatore SUSAN ma con qualche differenza,

vengono considerate le variazioni di intensita lungo ogni linea che attraversa

il punto preso in considerazione. Anni dopo viene introdotto l’algoritmo

FAST [51,52], una versione rilassata del precedente metodo SUSAN, il quale

e particolarmente performante in termini di velocita di esecuzione e fornisce

ottimi risultati anche dal punto di vista della robustezza. La tecnica piu

recente appartenente a questo gruppo si chiama AGAST [39] che rappresenta

una versione di FAST adattiva.

Rilevatori di contorni

Alcuni rilevatori di edge basati su immagini a livelli di grigio furono sviluppati

negli anni ’60 e ’70, tra i piu famosi si citano Roberts [49], Prewitt [47] e

Sobel [62]. Questi semplici metodi vengono utilizzati ancora oggi in varie

applicazioni nonostante il successivo sviluppo di tanti altri rilevatori [26].

L’operatore di Canny [14] fa parte della categoria di questi operatori, tuttavia

e molto piu sofisticato rispetto ai precedenti.

4


Per quanto riguarda le immagini a colori sono stati inizialmente propo-

sti metodi che estendevano le funzionalita dei precedenti operatori di Ro-

berts [18], Sobel e Canny. Altri metodi successivamente vennero sviluppati

basandosi su una analisi vettoriale dell’immagine, come il rilevatore MVD

(minimum vector dispersion) [69] e l’operatore vettoriale range [68].

Altri metodi studiati riguardavano l’analisi della distanza Euclidea tra un

pixel e le zone circostanti [77], altri risolvevano il problema da un punto di

vista matriciale, analizzando gli autovettori [77], e altri ancora tentavano un

approccio basato sull’entropia di una data regione rispetto ai vettori dello

spazio dei colori RGB dell’immagine [59].

1.3 Obiettivi

L’obiettivo del lavoro svolto e la progettazione di una applicazione per una

telecamera IP. Lo scopo principale di tale applicazione e l’estrazione real-time

di feature di basso livello, quali corner e edge. In letteratura e presente una

notevole quantita di rilevatori di feature, tuttavia solo una parte di essi si pre-

sta all’impiego in un’applicazione che lavora in tempo reale. L’algoritmo di

rilevamento corner chiamato FAST risulta particolarmente adatto allo scopo

grazie alla sua velocita di esecuzione. Tra gli obiettivi della tesi si include

anche la creazione di un algoritmo simile a FAST ma che si adatta meglio

alle specifiche di qualita dell’output e di portabilita del codice. L’operatore

di Sobel, nonostante sia un metodo ormai datato, fornisce ottime prestazioni

per quanto riguarda l’estrazione di edge.

Al fine di interpretare i dati prodotti dagli algoritmi si tenta di par-

tizionare le feature in cluster secondo il metodo tradizionale di clustering

k-means.

Un altro scopo della tesi e quello di realizzare un sistema client-server

finalizzato alla rappresentazione real-time delle feature rilevate su una pa-

gina Web, utilizzando le recenti tecnologie per il trasferimento dei dati e

studiando vari approcci ingegneristici per velocizzare i tempi di risposta

dell’applicazione.

5


1.4 Struttura della tesi

Il lavoro di tesi e organizzato in questo modo:

• Capitolo 2: viene descritto l’algoritmo FAST per il rilevamento corner

e proposta una sua variante adatta al progetto, viene descritto un siste-

ma di rimozione dei non massimi e proposta una stima per l’accuratezza

dei risultati ottenuti. Viene inoltre trattato l’argomento dell’estrazione

dei contorni di un’immagine, specificando il funzionamento dell’opera-

tore di Sobel e discusso un possibile metodo per elaborare ulteriormente

l’immagine ottenuta mediante il rilevatore di edge.

• Capitolo 3: viene discusso il concetto generale di data mining, detta-

gliando la parte riguardante il clustering e descrivendo il funzionamento

del k-means. Vengono discussi anche metodi possibili per l’inizializza-

zione degli algoritmi di partizionamento ed esposte alcune tecniche di

validazione dei cluster.

• Capitolo 4: rappresenta la parte fondamentale del progetto, viene

mostrato il funzionamento dell’applicazione in tutte le sue componenti.

Viene anche descritta la parte riguardante la piattaforma della camera

Axis e viene discussa la recente tecnologia Web chiamata AJAX.

• Capitolo 5: contiene alcuni risultati sperimentali sulla performance

dell’applicazione e sulla quantita di dati trasmessa.

• Capitolo 6: si conclude la tesi secondo alcune considerazioni e vengono

proposte alcune tematiche per gli sviluppi futuri.

6

Capitolo 2

Rilevamento di feature

In questo capitolo vengono discusse in dettaglio alcune tecniche di rilevamen-

to di feature. In particolare viene studiato un recente algoritmo di estrazione

di corner particolamente veloce e viene proposta una variante che si adatta

meglio a qualsiasi tipo di immagine. Successivamente viene discusso anche

il problema di rilevamento degli edge, trattando tecniche tradizionali e stu-

diando alcuni metodi possibili per il trattamento delle immagini elaborate

dagli estrattori di edge.

2.1 FAST Corner Detection

Il rilevamento degli angoli o corner in un immagine e un approccio usato nei

sistemi di visione computazionale per estrarre alcune tipologie di informa-

zione e trarre conclusioni riguardo i contenuti di un’immagine. I rilevatori

presenti in letteratura in genere non sono molto robusti e nel caso in cui si

utilizzi algoritmi appartenenti all’amibito di machine learning spesso si ri-

chiede una consistente supervisione durante l’elaborazione. Un altro grosso

problema riguarda la velocita di esecuzione. Non tutti gli algoritmi presentati

sono veloci dal punto di vista computazionale e solo pochi di essi si prestano

ad elaborare i dati in applicazioni real-time.

L’algoritmo FAST costituisce la base per la costruzione di un rilevatore

di angoli robusto e veloce. Questo metodo rappresenta una versione rilassata

7

CAPITOLO 2. RILEVAMENTO DI FEATURE

dell’algoritmo SUSAN.

In questa sezione verra illustrato il funzionamento dell’algoritmo FAST,

le tecniche utilizzate per migliorare le sue prestazioni e verra anche discusso

un metodo per la stima dell’accuratezza nel trovare gli angoli.

2.1.1 Cerchio di Bresenham

L’algoritmo FAST elabora ogni pixel di un’immagine I, a meno di un sot-

toinsieme molto limitato di pixel, estraendo informazioni dai punti circostanti

ciascun pixel. Nel nostro caso, la zona dei punti adiacenti al pixel di interesse

p, si chiama cerchio di Bresenham.

Definizione 2.1.1 (Cerchio di Bresenham) Si definisce cerchio di Bre-

senham l’insieme di punti che approssima un cerchio in un sistema di visua-

lizzazione composto da pixel.

Il cerchio, centrato in p e con raggio r, viene generato mediante un algoritmo

iterativo [13]. L’idea e quella di suddividere idealmente il cerchio in 8 ottanti,

creare il primo e generare i restanti basandosi sulla simmetria.

Siano xp e yp le coordinate del punto p, supponiamo di iniziare a generare

il cerchio da (xp+ r, yp) andando in senso antiorario. Sotto queste condizioni

i candidati ad essere il prossimo punto del cerchio sono:

PixelNordOvest = (xp + r − 1, yp − 1)

PixelNord = (xp + r, yp − 1)

Per selezionare il pixel corretto si considera il punto medio tra i due pixel

candidati: se questo cade all’interno del cerchio ideale si sceglie il PixelNord,

altrimenti se cade all’esterno si sceglie il PixelNordOvest. La procedura viene

quindi iterata anche per i restanti punti dell’ottante e il cerchio quindi viene

completato come mostrato in figura 2.1.

Per l’algoritmo FAST viene scelto il cerchio di Bresenham con raggio 3,

quindi i pixel circostanti che vengono presi in esame sono 16. Per semplicita di

notazione, faremo riferimento ai pixel del cerchio in base alle loro posizioni

cardinali rispetto al centro del cerchio p, i pixel piu significativi saranno

rappresentati dai quattro punti cardinali del cerchio:

8


Figura 2.1: Cerchio di Bresenham di raggio 3

• pN di coordinate (xp, yp − 3).

• pW di coordinate (xp − 3, yp)

• pS di coordinate (xp, yp + 3)

• pE di coordinate (xp − 3, yp)

Poiche questi pixel saranno utilizzati per decidere come effettuare i test

dell’algoritmo FAST, verranno in seguito chiamati pixel di decisione. Una

modalita alternativa di notazione e quella di assegnare un numero ad ogni pi-

xel del cerchio, partendo da pN a cui viene assegnato il numero 1 e procedendo

in senso orario secondo l’ordinamento dei numeri naturali.

2.1.2 Il criterio Segment Test

Il criterio Segment Test e il principio su cui si basa l’algoritmo FAST [51].

Si considera un cerchio di Bresenham con raggio r uguale a 3, attorno ad un

angolo candidato p e si cerca l’arco piu lungo nel quale l’intensita di ogni suo

pixel e maggiore di p di una certa soglia t, oppure l’intensita di ogni pixel e

minore dell’intensita di p dellla medesima soglia t. Sia nc il numero di pixel

contigui con questa proprieta e sia n una soglia prefissata, se

nc ≥ n

allora p e un angolo.

9


Definizione 2.1.2 Siano a e b due pixel appartenenti ad un’immagine e

siano I(a) e I(b) rispettivamente le loro intensita. Si dice che a e piu chiaro

di b se I(a) > I(b). Analogamente si dice che a e piu scuro di b se I(a) <

I(b).

Sia I(p) l’intensita del pixel p, allora si definisce il criterio Segment Test:

Definizione 2.1.3 (Criterio Segment Test) Esiste un angolo in p se, in

un cerchio di Bresenham di raggio r e centro in p, ci sono almeno n pixel i

quali sono tutti piu chiari di I(p) di una soglia t, oppure sono tutti piu scuri

di I(p) di una soglia t.

In figura 2.2 e mostrato un esempio relativo ai pixel contigui necessari affinche

il criterio Segment Test dia esito positivo in base al numero n.

Figura 2.2: Esempio del criterio Segment Test per n = 9 e n = 12

2.1.3 Original FAST

Il criterio Segment Test e utilizzato per rilevare gli angoli in un’immagine,

tuttavia si possono usare metodi per velocizzare il procedimento, incremen-

tando quindi la performance. Sia n il numero minimo di pixel contigui richie-

sti affinche p sia un angolo. Allora se di fatto p e un corner saranno necessari

almeno n test per determinarlo. Tuttavia saranno sufficienti meno test nel

caso in cui p non e un angolo. Questo rappresenta il punto di partenza per

diminuire il carico computazionale dell’algoritmo.

10


Algoritmo 1 Original FAST n = 12 and r = 3

Examine pixel N and S

if |I(p) - I(pN)| < t e |I(p) - I(pS)| < t

p not a corner

Examine pixel E

if 2 o more pixels are brighter than p by t

if Only 2 pixels are brighter than p by t

Examine pixel W

if 3 pixels are brighter than p by t

Execute Segment Test Criterion

else

p not a corner

else if 2 o more pixels are darker than p by t

if Only 2 pixels are darker than p by t

Examine pixel W

if 3 pixel are darker than p byt


else

p not a corner

11


Consideriamo a tal proposito due pixel diametralmente opposti del cerchio

di Bresenham pN e pS. Se entrambi hanno intensita tale che:

|I(p)− I(pN)| < t e |I(p)− I(pS)| < t

allora, dato nNS il numero di pixel compreso tra pN e pS, p non puo essere un

angolo se n e maggiore di nNS. Nel nostro caso, poiche il raggio del cerchio

di Bresenham e lungo 3, il numero di pixel totale e 16 e quindi si avra che il

numero di pixel compresi tra due estremi opposti del cerchio nNS e pari a 7.

Mediante un’accurata selezione dell’ordine in cui vengono eseguiti i test

si ottengono risultati migliori in termini di performance. L’ordine dei test

dipende dal valore di n, il numero di pixel contigui richiesto perche p si clas-

sificato come angolo. Tuttavia si devono limitare le possibilita sulla scelta

di n in quanto ci sono valori per cui l’algoritmo FAST non funziona bene,

ovvero non riconosce correttamente gli angoli presenti all’interno dell’imma-

gine. Infatti per n < 9, si ha un vincolo troppo debole, oltre che agli angoli

vengono rilevati anche gli edge. Al contrario, se n > 12 il vincolo e troppo

forte, quindi tutti gli angoli meno acuti dell’immagine vengono ignorati. Nel

caso in cui n sia uguale a 12, verra eseguito l’Algoritmo 1 [50]. Seguendo

queste regole si ottiene un metodo molto performante per il rilevamento degli

angoli, tuttavia mostra alcuni limiti:

1. Vengono rilevati piu angoli adiacenti.

2. L’ordine dei test usato per n = 12, non generalizza bene per n < 12.

3. La scelta e l’ordine dei test contiene assunzioni implicite riguardo a

come l’angolo appare nell’immagine.

4. La conoscenza appresa svolgendo i primi 4 test diventa inutile una volta

eseguito il Segment Test.

Il problema del punto numero 1 verra trattato e risolto nella sezione Punteggio

e soppressione dei non massimi, per il problema posto al punto 2 verra invece

proposto un algoritmo originale, che deriva dal metodo appena proposto,

nella sezione Generic Fast, infine i problemi dei punti 3 e 4 verranno trattati

nella sezione Learned Fast.

12


2.1.4 Generic FAST

Utilizzando l’Algoritmo Original FAST per n minore di 12, si ottengono

pessimi risultati in quanto tanti angoli non vengono riconosciuti. Il motivo

risiede nel fatto che nell’algoritmo originale per effettuare il criterio Segment

Test, e quindi per riconoscere che il pixel in questione e un angolo, e necessario

che almeno 3 pixel dei 4 scelti sul cerchio di Bresenham abbiano un’intensita

maggiore del pixel centrale piu una soglia. Tuttavia se n e minore di 12,

saranno sufficienti 2 di essi per potersi candidare ad essere corner.

Consideriamo a tal proposito i 4 pixel di decisione pN , pW , pS e pE.

Se di questi solo 2 superano il test ma sono diametralmente opposti, allora

necessariamente p necessariamente non potra essere un corner. Al contrario,

se 2 pixel di decisione su 4 passano il test e non sono situati ai lati opposti del

cerchio di Bresenham, allora p puo essere un angolo, quindi verra eseguito il

criterio Segment Test per stabilire se il pixel e etichettabile come corner. A

causa di questa condizione piu ristretta, ovvero il fatto che sono sufficienti 2

pixel di decisione su 4 invece dei 3 rispetto alla versione originale, comporta

il fatto che il criterio Segment Test venga eseguito piu frequentemente. La

conseguenza immediata di questo fenomeno e ovviamente un leggero calo di

performance, tuttavia molto attenuato dal fatto che se da una parte il criterio

viene eseguito piu volte rispetto all’algoritmoOriginal FAST, dall’altra i pixel

richiesti da esso per verificare l’esistenza del corner sono di meno. Lo pseudo-

codice dell’algoritmo e mostrato in Algoritmo 2 mentre il codice scritto in

C++ si trova nell’appendice A.

Come nell’algoritmo originale, la procedura viene eseguita per ogni pixel

dell’immagine ma in questo caso i risultati sono migliori. Come si puo vedere

dalla figura 2.3, il Generic FAST rileva perfettamente tutti i corner delle

forme all’interno dell’immagine, mentre l’algoritmo originale non riesce ad

estrarre gli angoli della stella ad otto punte, in quanto hanno un’ampiezza

troppo elevata per superare il test dei 12 pixel.

13


Algoritmo 2 Generic FAST n = 9 and r = 3

Examine pixel N and S

if |I(p) - I(pN)| < t e |I(p) - I(pS)| < t

p not a corner

Examine pixel E

if 1 or more pixels are brighter than p by t

if Only 1 pixel are brighter than p by t

Examine pixel W

if 2 pixels or more are brighter than p by t

if Only 2 pixels are brighter than p by t

if pixels are diametrically opposed and W not examined

p not a bright corner

else


else


p not a bright corner

if 1 or more pixels are darker than p by t and p not a bright corner

if Only 1 pixel are darker than p by t

Examine pixel W

if 2 pixels or more are darker than p by t

if Only 2 pixels are darker than p by t

if pixels are diametrically opposed and W not examined

p not dark a corner

else


else


p not a dark corner

14


(a) Generic FAST (n = 9)

(b) Original FAST (n = 12)

Figura 2.3: Algoritmi FAST a confronto

15


2.1.5 Learned FAST

Un altro approccio al problema del riconoscimento degli angoli e basato sul-

l’apprendimento automatico. Rosten [52] propone un metodo composto da

2 fasi. Per costruire un buon rilevatore, fissato n e un’opportuna soglia t,

gli angoli vengono rilevati da un insieme di immagini definite a priori (pre-

feribilmente prese dal contesto in cui si deve lavorare). Il passo successivo e

quello di eseguire un algoritmo lento che testa tutti i 16 pixel del cerchio di

Bresenham per ogni pixel dell’immagine.

I pixel circostanti p presi in esame possono trovarsi in 3 stati diversi:

• Piu chiaro di p;

• Piu scuro di p;

• Simile a p,

Formalizzando, sia Sx lo stato del pixel px, con x ∈ 0..16, allora:

Sx =

b, Ix ≤ Ip − t (Chiaro)

d, Ix ≥ Ip + t (Scuro)

s, Ip − t < Ix < Ip + t (Simile)

(2.1)

Scegliendo un x, si calcola Sx per ogni p ∈ P , dove P rappresenta l’insieme di

tutti i pixel di ogni immagine del set iniziale. Il passo successivo e quello di

partizionare P in tre sottoinsiemi Pb, Pd e Ps, dove ogni pixel p e assegnato

a PSx .

Sia Kp la variabile booleana che indica vero se p e un angolo e falso

altrimenti. La seconda fase del metodo prevede di utilizzare l’algoritmo ID3,

selezionando all’inizio la x che contiene la maggior quantita di informazioni

riguardo alla caratteristica di essere un angolo, misurata dall’entropia di Kp.

L’entropia K per l’insieme P viene calcolata come:

H(P ) = (c+ c) log2(c+ c)− c log2 c− c log2 c

dove c = 〈p|Kp vero〉 (numero di angoli)

e c = 〈p|Kp falso〉 (numero di non angoli)

(2.2)

16


La scelta di x determina quindi il guadagno di informazione:

H(P )−H(Pd)−H(Pb)−H(Ps) (2.3)

Avendo selezionato la x che massimizza il guadagno di informazione, il pro-

cesso viene applicato ricorsivamente su tutte le tre partizioni, ovvero xb viene

selezionato per partizionare Pb in Pb,d, Pb,s e Pb,b e cosı via, dove ogni x vie-

ne scelta in modo da massimizzare il guadagno di informazione relativo alla

partizione a cui si riferisce. Questo procedimento termina quando l’entro-

pia di una partizione e nulla, ovvero quando tutti i p in questo sottoinsieme

hanno lo stesso valore di Kp. Questo procedimento crea un albero di decisio-

ne che puo classificare correttamente tutti gli angoli rilevati nell’insieme di

apprendimento e che quindi contiene implicitamente le regole del rilevatore

di angoli prescelto. Il fatto che i dati di allenamento non contengono una

copertura completa su tutti gli angoli possibili implica che questo metodo di

rilevamento non e del tutto uguale al metodo che usa il Segment Test, quindi

i risultati non saranno uguali. Una buona tecnica per migliorare la qualita

dei dati estratti e quella di modificare leggermente l’albero di decisione ot-

tenuto in seguito all’apprendimento, in modo che esso dia gli stessi risultati

del Segment Test sull’insieme di immagini iniziale.

2.1.6 Punteggio e soppressione dei non massimi

Il criterio Segment Test tende a rilevare tanti angoli adiacenti l’un l’altro,

quindi per trovare un unico candidato di un gruppo di angoli adiacenti biso-

gna usare un metodo per assegnare un punteggio a ciascuno di essi, scegliere

quello con punteggio migliore e rimuovere tutti gli altri.

Punteggio

L’idea e quella di trovare una funzione V che per ogni angolo rilevato me-

diante il criterio Segment Test, assegni un punteggio in modo da scegliere il

migliore in un intorno scelto a priori. Ci possono essere piu modi per definire

V :

1. Il valore piu alto di n tale che p sia rilevato come angolo.

17


2. Il valore piu alto di t tale che p sia rilevato come angolo.

3. La somma delle differenze di intensita in valore assoluto tra i pixel

nell’arco contiguo e il pixel centrale.

Le definizioni dei punti 1 e 2, nonostante la semplicita di implementazione,

non sono adatte come funzione di punteggio in quanto sono grandezze for-

temente quantizzate, ovvero in prossimita di un gruppo di angoli molti di

questi avranno lo stesso punteggio e non sara possibile scegliere un singolo

candidato. La soluzione quindi e selezionare la terza definizione, con qual-

che modifica per incrementare la performance. L’idea e quella di trovare la

massima soglia per cui l’angolo viene rilevato ancora come tale. Infatti se

la soglia t e sufficiente per annotare un pixel come angolo, non e detto che

anche la soglia t + 1 lo sia. Allora quello che accade e una ricerca binaria

della soglia massima, ripetendo ciclicamente l’algoritmo FAST utilizzato per

rilevare gli angoli finche tale soglia non viene rilevata. Quel valore sara il

punteggio dell’angolo, in generale differente dai vicini. Formalizzando:

V = max

(∑x∈B

|Ix − Ip| − t,∑x∈D

|Ix − Ip| − t

)(2.4)

dove

B = x|Ix ≥ Ip + t (Pixel chiari)

D = x|Ix ≤ Ip − t (Pixel scuri)

Se viene utilizzata la versione Generic FAST esiste un ulteriore accorgimento

da fare per migliorare la performance. Il problema risiede nella duplice natura

degli angoli, che posso essere chiari o scuri. Quando deve essere assegnato un

punteggio agli angoli, si e gia a conoscenza di questa loro proprieta. Quindi

quando si esegue il criterio Segment Test, lo si effettua in base alla natura

dell’angolo, evitando cosı un deterioramento di performance.

Soppressioni dei non massimi

Una volta assegnato il punteggio a ciascun corner, si puo procedere con l’eli-

minazione dei non-massimi, ovvero di quei corner che non rappresentano un

18


punto di massimo locale rispetto ai vicini. La tecnica usata e quella di fare

scorrere sopra ogni candidato una finestra 3x3 di pixel e guardare se ci sono

altri angoli in tale zona. Se sono presenti allora si mettono a confronto i pun-

teggi ottenuti in precedenza, quindi nel caso ne trovasse almeno uno con un

punteggio superiore, l’angolo al centro della finestra 3x3 viene rimosso dalla

lista. Alla fine rimarranno solo i massimi locali in ogni regione dell’immagine

come mostrato in figura 2.4

Figura 2.4: L’effetto dell’eliminazione dei non massimi

2.1.7 Stima di ripetitivita

La ripetitivita indica che il rilevamento di feature e indipendente dai cambia-

menti delle condizioni di una data immagine, in questo caso di angoli. Tali

condizioni possono essere i parametri della camera utilizzata, la posizione di

essa rispetto alla scena, le variazioni di luminosita e il rumore presente. Un

rilevatore di angoli e ben costruito se in due differenti immagini, prese sulla

stessa scena, rileva gli stessi punti caratteristici in entrambe.

Il tasso di ripetitivita e definito come il numero di punti che si ripetono

in due immagini sul numero totale di punti rilevati [57]. Per misurare il

19


numero totale di punti rilevati bisogna tenere conto che le immagini che

stanno riprendendo la medesima scena possono differire, come nel caso in

cui esse siano state riprese da due punti di vista diversi oppure nel caso in

cui una delle due sia ridotta in scala rispetto all’altra. In presenza di tali

eventi esistono dei punti che potrebbero non essere osservabili in entrambe

le immagini, quindi si avrebbe un condizionamento negativo sulla misura del

tasso di ripetitivita. In questi caso quindi vengono considerati esclusivamente

i punti che giacciono sulla medesima scena.

Esiste un’altra considerazione da fare, ovvero quella dell’incertezza del

rilevamento. Puo accadere che un punto rilevato su una prima immagine

non cada esattamente dove previsto sulla seconda immagine, ma in una zona

vicina. L’area di questo intorno si denota con ε e quindi considerando questa

eventualita si parla di ε-ripetitivita.

Nel caso in cui si desideri verificare la ripetitivita di due immagini che

differiscono per il punto di vista, ovvero se si e nelle condizioni in cui una

scena viene ripresa da due angolazioni diverse, allora sara necessario che esse

siano in relazione mediante una omografia.

2.2 Rilevamento dei contorni

I contorni di un’immagine, detti anche edge fanno parte di quelle caratte-

ristiche che rappresentano la struttura e le proprieta di un oggetto in una

scena. Bruschi cambiamenti delle proprieta di un’immagine indicano in gene-

re eventi o cambiamenti importanti del mondo fisico di cui le immagini sono

la rappresentazione. Questi cambiamenti possono essere ad esempio: discon-

tinuita della profondita, discontinuita dell’orientamento delle superfici, mo-

difica delle proprieta dei materiali, e variazioni dell’illuminazione proveniente

dall’ambiente circostante.

Esistono molti metodi per rilevare gli edge, in generale e possibile classi-

ficarli in due categorie: metodi basati sulla ricerca e metodi basati sull’at-

traversamento dello zero. I metodi basati sulla ricerca rilevano i contorni

cercando i massimi ed i minimi della derivata del primo ordine dell’immagi-

ne, di solito cercando la direzione in cui si ha il massimo gradiente locale. I

20


metodi basati sull’attraversamento dello zero cercano i punti in cui la deri-

vata del secondo ordine passa per lo zero, solitamente la funzione laplaciana

o un’espressione differenziale di una funzione non-lineare. L’operatore di

Sobel [62] fa parte della prima categoria.

In questa sezione verra introdotto il concetto di gradiente, verranno il-

lustrati i passi fondamentali dell’edge detection e successivamente verra de-

scritto il funzionamento dell’operatore di Sobel sia dal punto di vista pratico

che da quello matematico. Infine verranno discussi metodi per trattare i

risultati dell’operatore di Sobel, come la binarizzazione dell’immagine e la

quantizzazione.

2.2.1 Gradiente

Il gradiente di una funzione f(x) indica come essa cambia al variare della

x. Si puo pensare ad un immagine come un array di campioni di qualche

funzione continua che rappresenta l’intensita dell’immagine. Quindi per ana-

logia cambiamenti significativi tra i valori di grigio di un’immagine possono

essere rilevati utilizzando un’approssimazione discreta del gradiente. Il gra-

diente e l’equivalente bidimensionale della derivata prima di una funzione ed

e definito dal vettore:

∇f(x, y) = G[f(x, y)] =

[Gx

Gy

]=

[∂f∂x∂f∂y

](2.5)

Ci sono due importanti proprieta associate al gradiente:

1. Il vettoreG[f(x, y)] punta in direzione del tasso di massimo incremento

della funzione f(x, y).

2. La norma del gradiente data da√G2

x +G2y, equivale al tasso di massimo

incremento di f(x, y) per distanza unitaria nella direzione del gradiente

G.

Ad ogni modo e di uso comune approssimare la norma del gradiente come:

‖G‖ ≈ |Gx|+ |Gy| (2.6)

21


La direzione del gradiente e definita da:

θ(x, y) = arctan

(Gy

Gx

)(2.7)

dove l’angolo θ e misurato rispetto all’asse x.

Approssimazione del gradiente

Per le immagini digitali, le derivate nell’equazione 2.5 sono approssimate

mediante differenze. La piu semplice tra le possibili approssimazioni del

gradiente e:

Gx ≈ f [i, j + 1]− f [i, j] (2.8)

Gy ≈ f [i, j]− f [i+ 1, j] (2.9)

tenendo conto che j corrisponde alla direzione positiva sulle x e i alla quella

negativa sulle y. Tutto questo puo essere implementato mediante le maschere

di convoluzione:

Gx =[−1 1

]Gy =

[1

−1

](2.10)

Quando viene calcolata l’approssimazione del gradiente e di fondamentale

importanza che le derivate parziali rispetto a x e y siano calcolate esattamente

nella stessa posizione nello spazio. Tuttavia, usando queste approssimazioni

Gx e l’approssimazione del gradiente nel punto interpolato(i, j + 1

2

)e Gy

quella in(i+ 1

2, j).

Per questa ragione vengono usate le matrici di convoluzione 2×2 piuttosto

che le 2× 1 e 1× 2:

Gx =

[−1 1

−1 1

]Gy =

[1 1

−1 −1

](2.11)

In questo modo i punti sui quali viene calcolato il gradiente rispetto a x e a

y coincidono nella stessa posizione. Il punto pero giace in mezzo ai 4 pixel

nell’intorno 2×2 nella posizione interpolata(i+ 1

2, j + 1

2

). Questa situazione

puo generare qualche ambiguita, quindi la procedura classica e quella di

utilizzare un approccio alternativo basato sulle matrici di convoluzione 3× 3

22


e calcolare il gradiente del pixel centrale. Questo metodo e quello utilizzato

nell’operatore di Sobel che verra descritto in seguito.

2.2.2 Sviluppo del rilevamento contorni

In generale prima di eseguire il vero e proprio algoritmo di rilevamento dei

contorni, le immagini vengono trattate con tecniche apposite in modo da

migliorare la qualita dei risultati. Queste fasi preliminari sono opzionali, e

possibile procedere direttamente col rilevamento dei contorni ma si otterra

una immagine di qualita peggiore.

Rimozione del rumore

Poiche il calcolo del gradiente basato sui valori dell’intensita di solo due punti

e molto sensibile al rumore, in genere l’immagine viene filtrata per miglio-

rare la qualita dei risultati di rilevamento. I filtri utilizzati possono essere

diversi, in genere si sceglie quello piu adatto per il tipo di rumore presente

nell’immagine. Tuttavia esiste un trade-off tra l’intensita dei contorni e la

riduzione di rumore, infatti aumentando il filtraggio si ottengono contorni

meno marcati.

Miglioramento dell’immagine

Per facilitare il rilevamento dei contorni, e necessario determinare i cam-

biamenti di intensita nelle zone adiacenti ad un punto preso in esame. Il

miglioramento dell’immagine enfatizza quei pixel dove esiste un significativo

cambiamento nei valori dell’intensita in un dato intorno. In questo modo

l’immagine si adatta meglio allo scopo dell’applicazione. Una tecnica comu-

ne di miglioramento e detta contrast stretching che ha lo scopo di aumentare

la dinamica dell’immagine il cui istogramma e concentrato in un intervallo

limitato dei valori possibili.

23


Rilevamento

Una volta eseguiti i due passi precedenti si esegue l’algoritmo vero e proprio

di rilevamento. Quello che viene richiesto consiste nel trovare quei punti ad

alto contenuto di edge. Tuttavia alcuni pixel hanno valore diverso da zero

per il gradiente, e non tutti rappresentano un contorno per una particolare

applicazione. Quindi vengono usati alcuni metodi per determinare quali punti

sono edge, come ad esempio il Thresholding.

2.2.3 Operatore di Sobel

L’operatore di Sobel e uno dei rilevatori di contorni piu utilizzati. Esso

fornisce un’approssimazione poco accurata del gradiente dell’immagine, ma

e comunque di qualita sufficiente per poter essere utilmente usato in molte

applicazioni. Un altro fattore molto importante e la sua velocita di esecuzione

che e un requisito fondamentale per le applicazioni real-time.

L’operatore applica due matrici di convoluzione 3 × 3 all’immagine ori-

ginale per calcolare valori approssimati delle derivate, una in direzione oriz-

zontale ed una in direzione verticale. Se chiamiamo I l’immagine sorgente,

e Gx e Gy le due immagini i cui punti rappresentano rispettivamente i va-

lori approssimati delle derivate in orizzontale ed in verticale, l’operazione e

descritta da:

Gx =

−1 0 +1

−2 0 +2

−1 0 +1

∗ I e Gy =

−1 −2 −1

0 0 0

+1 +2 +1

∗ I (2.12)

dove ∗ indica l’operatore di convoluzione.

Combinando le due approssimazioni derivative ottenute in ogni pixel

dell’immagine si ottiene quindi la norma del vettore gradiente:

‖G‖ =√G2

x +G2y (2.13)

L’immagine ottenuta e quindi la composizione delle due immagini ottenute

calcolando il gradiente in una singola direzione, una volta rispetto all’asse

orizzontale ed una rispetto all’asse verticale, come si puo vedere in figura

2.5.

24


(a) Immagine originale (b) Operatore di Sobel

(c) Gradiente orizzontale normaliz-

zato

(d) Gradiente verticale normalizzato

Figura 2.5: Il funzionamento dell’operatore di Sobel e le componenti del

gradiente

25


In questo modo e possibile creare un’immagine composta dai valori risul-

tanti dell’operatore. Infatti se questo algoritmo di rilevazione viene eseguito

su un’immagine a 256 livelli di grigio, quello che si ottiene e una nuova

immagine dove i valori della norma del gradiente rappresentano l’intensita

dei nuovi pixel. Nel caso in cui la norma risultasse maggiore dell’intensita

massima, il valore del pixel verra posto al massimo consentito dalla scala di

grigi.

Da un punto di vista formale, poiche la funzione che definisce l’intensita

luminosa di un’immagine digitale e nota solo in punti discreti, le derivate

di questa funzione non possono a rigore essere definite a meno di assume-

re l’esistenza di una sottostante funzione luminosita continua che sia stata

campionata nei punti dell’immagine. Con alcune altre assunzioni la deriva-

ta della funzione luminosita puo essere calcolata come funzione della stessa

immagine digitale. Quindi i valori del gradiente in ogni pixel dell’immagine

sono funzioni dei valori della luminosita in quel punto.

2.2.4 Quantizzazione

I risultati dell’operatore di Sobel possono essere trattati in modo da enfatiz-

zare le caratteristiche degli edge, ma anche in modo da creare una sorta di

suddivisione dell’immagine in aree nelle quali le variazioni di grigi avvengono

lentamente. Il metodo utilizzato si chiama quantizzazione e in questo caso e

applicato ad un immagine in scala di grigi.

Formalmente, sia n il numero di bit usato per rappresentare l’immagine,

allora il numero totale di livelli di grigio che descrive l’immagine sara dato

da:

N = 2n (2.14)

Per rappresentare l’immagine ottenuta dall’operatore di Sobel servono 8 bit

per pixel, quindi ci saranno 256 grigi in totale. Se vogliamo rappresentare la

stessa immagine con meno bit allora sara necessario quantizzare l’immagine

appropriatamente. Sia f(x, y) la funzione che indica il valore dell’intensita

del pixel situato nelle coordinate x e y, e sia l il numero di bit desiderato per

rappresentare l’immagine iniziale di b = 8 bit. Allora definito d = b− l come

26


(a) Originale (b) Sobel (c) 7 bit

(d) 6 bit (e) 5 bit (f) 4 bit

(g) 3 bit (h) 2 bit (i) 1 bit

Figura 2.6: Quantizzazione dell’immagine ottenuta con Sobel

la differenza tra il numero di bit delle due rappresentazioni si ottiene che:

q(x, y) = bf(x, y)2d

c (2.15)

sara la funzione che ad ogni pixel assegna una classe di appartenenza nella

scala quantizzata, ovvero un valore intero compreso tra 0 e 2l − 1. In base

a questi valori discreti trovati, quindi e possibile assegnare i nuovi valori di

grigi per visualizzare l’immagine quantizzata, secondo la formula:

fq(x, y) = q(x, y) · 2d + 2d−1 (2.16)

27


Un effetto che si ottiene e sicuramente un peggioramento della qualita

dell’immagine, infatti appaiono dei falsi contorni e non e piu possibile distin-

guere due oggetti che differiscono per variazioni di grigi della stessa classe di

appartenenza. D’altra parte si osserva un notevole risparmio nella codifica

dell’immagine poiche i livelli di grigio da memorizzare saranno minori rispet-

to allo stato di partenza di 256 colori in modo proporzionale al numero di bit

utilizzati nell’immagine quantizzata. Nella figura 2.6 si nota come variano le

immagini elaborate in base al livello di grigi scelto. Si osservi che le diffe-

renze tra le immagini con piu di 32 colori sono quasi impercettibili all’occhio

umano.

Thresholding

Esiste un approccio particolare nel caso in cui si intenda quantizzare l’im-

magine sorgente con un solo bit, ovvero quando un pixel o assume valore

0 (nero) oppure assume valore 1 (bianco). Si tratta della binarizzazione

dell’immagine, che puo essere eseguita con il metodo della quantizzazione

precedentemente descritto, oppure possono essere fatte ulteriori osservazioni.

Dovendo trattare un immagine modellata dall’operatore Sobel, si cerca di

utilizzare la binarizzazione per esaltare le caratteristiche dei contorni, quindi

di fatto assegnando un valore a cio che e ritenuto un edge e l’altro valore a

cio che non lo e ritenuto. Questa selezione puo essere fatta in maniera molto

semplice introducendo una soglia t. La tecnica in questione viene chiamata

sogliatura o thresholding.

L’immagine su cui viene eseguita la sogliatura diventa una funzione cosı

definita:

ft(x, y) =

0 f(x, y) < t

1 altrimenti(2.17)

Nelle implementazioni piu semplici i pixel neri rappresentano lo scenario del-

l’immagine, mentre quelli bianchi sono in primo piano. Poiche stiamo trat-

tando edge nel nostro caso, e utile invece invertire le parti, evidenziando i

contorni col nero e lasciare lo sfondo bianco. Rimane da decidere come sce-

gliere t in modo che risulti la migliore soglia per mettere in rilievo i contorni

28


estratti dall’operatore di Sobel. Esistono diversi metodi in letteratura per

scegliere il parametro automaticamente. Una semplice tecnica consiste nello

scegliere il valore medio o il valore mediano tra i valori presenti nell’immagi-

ne. Otsu [44] propone un metodo di scelta adattivo, ponendo come obiettivo

la minimizzazione della somma pesata delle varianze delle due classi (bianco

e nero). Sauvola [54] utilizza un metodo computazionalmente piu oneroso,

ma di qualita superiore che prevede il calcolo della media e della deviazione

standard dell’intensita dei pixel appartenenti all’immagine. Tipicamente si

cerca di calcolare la soglia in modo che gli edge risultino il 30% del numero

totale dei pixel. In figura 2.7 si nota come gli egde siano piu netti e marcati

all’aumentare della soglia.

(a) t = 64 (b) t = 128 (c) t = 192

Figura 2.7: Thresholding dell’immagine al variare della soglia t

29

Capitolo 3

Data mining

Il data mining e una scienza piuttosto recente che comprende vari campi di

studio dell’informatica. Consiste nel processo di estrazione di nuove informa-

zioni da grandi quantita di dati, includendo metodi statistici oppure tecniche

derivate dall’intelligenza artificiale, ma anche dalla gestione dei database.

A differenza dell’apprendimento automatico l’attenzione viene focalizzata

sulla ricerca di informazioni ancora non conosciute piuttosto che generaliz-

zare modelli conosciuti a nuovi insiemi di dati. L’attuale scopo del data

mining e l’analisi automatica o semiautomatica di grandi quantita di da-

ti per estrarre modelli precedentemente sconosciuti come il raggruppamento

dei dati (clustering), avvenimenti insoliti (rilevamento anomalie) oppure ge-

nerazione di dipendenze fra i dati(regole di associazione). Le informazioni

estratte possono essere viste come una sintesi delle caratteristiche dei dati in

ingresso e utilizzate successivamente per ulteriori analisi oppure come esempi

nel campo dell’apprendimento automatico.

I due primari obiettivi del data mining tendono ad essere la predizione e

la descrizione. La predizione implica l’utilizzo di variabili dell’insieme di dati

per prevedere valori ancora sconosciuti oppure valori che alcune variabili di

interesse assumeranno in futuro. D’altra parte la descrizione concentra la sua

funzione nel trovare modelli che descrivano i dati che in seguito possano essere

interpretati dagli umani. Sotto queste assunzioni e possibile suddividere il

campo delle attivita del data mining in due categorie principali:

30

CAPITOLO 3. DATA MINING

1. Data mining predittivo: produzione del modello del sistema descrit-

to dall’insieme dei dati fornito.

2. Data mining descrittivo: produzione di informazioni nuove e non

banali basate sull’insieme dei dati fornito.

L’importanza relativa di predizione e descrizione in particolare applica-

zioni del data mining puo variare notevolmente a seconda del problema. Gli

obiettivi di descrizione e predizione vengono raggiunti in seguito all’utilizzo

di varie tecniche che Kantardzic [29] suddivide in 6 categorie:

1. Classificazione: ricerca di una funzione di apprendimento predittiva

che classifica gli oggetti in una o piu classi predefinite.

2. Regressione: ricerca di una funzione di apprendimento predittiva che

associ un elemento dell’insieme di dati ad una variabile di predizione a

valori reali.

3. Clustering: problema descrittivo in cui si cerca di identificare un

insieme finito di categorie o settori per descrivere i dati.

4. Sommarizzazione: problema descrittivo che comprende metodi per

trovare una descrizione compatta dell’insieme dei dati.

5. Dependency modeling: ricerca di un modello locale che descrive

dipendenze significative tra le variabili o tra i valori di una caratteristica

in un insieme di dati.

6. Rilevamento cambiamenti e deviazioni: rilevamento dei cambia-

menti piu significativi in un insieme di dati.

In questo capitolo verra discusso il problema descrittivo del clustering e in

particolare verra descritto il funzionamento dell’algoritmo k-means e una sua

inizializzazione ottimale. In seguito verra trattato il problema della selezione

del numero di cluster e la rappresentazione di questi su un’immagine.

31


3.1 Clustering

Il clustering e un insieme di tecniche il cui scopo e assegnare un insieme di

oggetti ad un certo numero di gruppi, chiamati cluster o settori, in modo che

gli oggetti all’interno di uno stesso cluster siano piu simili tra loro rispetto

agli oggetti all’interno degli altri settori.

Gli algoritmi di clustering differiscono significativamente tra di loro in

base alla definizione stessa di cluster. Le tipiche definizioni di settore variano

in base al problema proposto: gruppi entro i quali i propri membri hanno

distanza minima fra di loro, aree dense all’interno dell’insieme di dati iniziale,

intervalli o particolari distribuzioni statistiche.

Il significato di cluster varia a seconda dell’algoritmo utilizzato ed e una

delle molte decisioni da prendere quando si deve selezionare la migliore tec-

nica per il risolvere il particolare problema. I modelli di cluster si possono

differenziare in base alle seguenti dicotomie:

• Agglomerativo/Divisivo: Questo aspetto e relativo alla struttura e

alle operazioni dell’algoritmo. Un approccio agglomerativo inizia con

molteplici cluster di un solo elemento e successivamente unisce i settori

insieme fino a quando non si verifica una determinata condizione di

stop. Al contrario un approccio divisivo inizia con tutti gli oggetti

all’interno di un singolo cluster, quindi inizia a dividersi in piu settori

fino a quando non si verifica un data condizione di arresto.

• Monotetico/Politetico: Questo aspetto si riferisce all’utilizzo se-

quenziale o simultaneo degli oggetti. La maggior parte degli algoritmi

ha un approccio politetico, ovvero ogni oggetto e partecipe nel calcolo

della distanza tra settori, e le decisioni vengono prese in base a ta-

li distanze. Gli algoritmi monotetici invece considerano gli oggetti in

sequenza per dividere il data set nei vari settori.

• Hard/Fuzzy: Unclustering di tipo hard assegna ogni oggetto ad un

singolo cluster durante le sue operazioni e anche alle fine del processo

nel suo output. Un clustering di tipo fuzzy assegna un grado di appar-

tenenza ad alcuni settori ad ogni oggetto dell’insieme iniziale. Si puo

32


passare dal tipo fuzzy all’altro tipo diclustering assegnando ad ad ogni

oggetto il settore con il maggior grado di appartenenza.

• Deterministico/Stocastico: Questo problema e il piu rilevante tra

gli approcci di partizionamento per ottimizzare l’errore quadratico di

una funzione. L’ottimizzazione puo essere ottenuta utilizzando le tecni-

che tradizionali oppure tramite una ricerca aleatoria nello spazio degli

stati che consiste nell’insieme totale delle possibili label.

• Incrementale/Non-incrementale: Questo problema sorge nel caso

in cui l’insieme di oggetti da essere partizionato e ampio e quindi i

vincoli sul tempo di esecuzione o sullo spazio di memoria influiscono

sull’architettura dell’algoritmo. L’avvento del data mining ha favorito

lo sviluppo di algoritmi diclustering che minimizzano il numero di ite-

razioni sull’insieme di oggetti durante l’esecuzione, oppure che riducono

l’ampiezza delle strutture dati usate nelle operazioni dell’algoritmo.

Ad ogni modo la costruzione di un algoritmo diclustering lascia molta flessi-

bilita nel decidere la sua implementazione.

3.1.1 Misura di clustering

Come e stato detto in precedenza, lo scopo delclustering e di identificare un

numero opportuno di gruppi tali che gli elementi appartenenti ad un gruppo

siano in qualche modo piu’ simili tra loro che non agli oggetti appartenenti

ad altri gruppi. Si necessita quindi di una definizione di similarita o distanza

tra oggetti per sviluppare gli algoritmi. In base ai dati dell’insieme iniziale si

hanno misure differenti, infatti nel caso di dati quantitativi si usano misure

di distanza mentre se siamo in presenza di dati qualitativi abbiamo bisogno

di misure di associazione.

Sia X la matrice dei dati che identifica i valori dell’insieme di elementi

di partenza. Tale matrice ha n righe pari al numero totale di elementi e m

colonne, una per ogni variabile descrive l’elemento da elaborare.

33


Misura di distanza

Supponendo che le m variabili della matrice X siano numeri e non attributi,

si puo definire la distanza tra due unita p e q in diversi modi:

• Distanza Euclidea:

d(p, q) =

√√√√ n∑i=1

(pi − qi)2 (3.1)

• Distanza Manhattan:

d(p, q) =n∑

i=1

|pi − qi| (3.2)

• Distanza Mahalanobis [38](vettoriale):

d(p,q) =√

(p− q)TS−1(p− q) (3.3)

dove S e la matrice di covarianza tra le componenti dei due vettori.

Misura di associazione

Nel caso in cui non si stia trattando dati quantitativi ma dati che rappresen-

tano attributi bisogna usare una strategia diversa. Supponiamo di avere m

attributi, ciascuno dei quali puo essere presente (valore 1) o assente (valore

0) in una generica unita. Supponiamo di voler confrontare la similarita tra

un elemento p e un altro q, allora si dovra dare riferimento alla tabella:

p/q 1 0 tot

1 a b a+ b

0 c d c+ d

tot a+ c b+ d t

Tabella 3.1: Tabella di similarita

34


dove a rappresenta il numero di attributi comuni ai due elementi, d il

numero di attributi assenti in entrambi gli elementi, b il numero di elementi

presenti in p ma non in q e c il numero di elementi presenti in q ma non in p.

Si possono definire diversi indici di similarita:

• Indice di Russell e Rao [53]:

S(p, q) =a

t(3.4)

• Indice di Jaccard [27]:

S(p, q) =a

a+ b+ c(3.5)

• Indice di Sokal e Michenener [63]:

S(p, q) =a+ d

t(3.6)

Si osservi che l’indice di Jaccard ha importanza quando le co-assenze hanno

poco significato nel problema.

Nel caso in cui invece gli attributi non siano dicotomici, ovvero quando gli

attributi possono assumere piu di due modalita, la misura e piu complessa.

Lo scopo iniziale e quello di trovare una codifica di tipo disgiuntivo per ogni

variabile qualitativa. In seguito si valuta la costruzione di indici che non

prendono in considerazione le co-assenze, in quanto queste non avrebbero

alcun significato.

3.1.2 Algoritmi di clustering

Dopo la definizione delle misure di distanza e di associazione, e necessario

scegliere il metodo di classificazione ed un eventuale criterio di aggregazione o

suddivisione. I metodi di classificazione si differenziano in base alle dicotomie

introdotte in precedenza, anche se i confini di definizione di tali algoritmi non

sono cosı ben marcati.

35


Algoritmi gerarchici

Definizione 3.1.1 (Dendrogramma) Si definisce dendrogramma un dia-

gramma ad albero che rappresenta una gerarchia di categorie basate sul grado

di similarita o sul numero di caratteristiche in comune.

Un esempio di dendrogramma e mostrato in Figura 3.1.

Figura 3.1: Esempio di dendrogramma

Un algoritmo diclustering di tipo gerarchico costruisce un dendrogramma

che rappresenta il raggruppamento annidato di elementi e livelli di similarita

lungo i quali questi raggruppamenti cambiano. La maggior parte di questi

algoritmi sono varianti degli algoritmi single-link [61], complete-link [33] e

minimum-variance [43, 73].

Nell’algoritmo single-link la distanza tra due cluster e la minima distanza

fra tutte le coppie di elementi presi dai due settori, un oggetto preso dal primo

cluster l’altro dal secondo. Nel complete-link la distanza tra due cluster e

la massima fra tutte le coppie di distanze tra gli oggetti nei due cluster.

In entrambi i casi, due settori vengono uniti per formarne uno piu grande

basandosi sul criterio di minima distanza.

In generale il complete-link genera cluster compatti, mentre il single-link

tende a creare settori che sono irregolari o allungati. D’altra parte il metodo

single-link risulta essere piu versatile, in quanto riesce in alcuni casi a rilevare

cluster concentrici.

36


Algoritmi partizionali

Un algoritmo partizionale diclustering ottiene una singola partizione dei dati

invece di una struttura dei cluster, come il dendrogramma prodotto dagli

algoritmi gerarchici. Questo comporta un vantaggio nelle applicazioni che

devono lavorare su grandi quantita di dati in quanto le costruzioni delle

strutture sono molto onerose dal punto di vista computazionale.

Le tecniche partizionali di solito producono i cluster ottimizzando una

funzione definita localmente o globalmente, a seconda se si intende compren-

dere l’intero data set o solo un sottoinsieme di esso. Una ricerca combinatoria

all’interno dell’intero insieme delle partizioni per un valore ottimo e proibi-

tiva, quindi il tipico approccio e quello di iterare l’algoritmo piu volte con

differenti stati iniziali e scegliere la migliore configurazione ottenuta da queste

iterazioni come output.

Questo tipo di algoritmi puo essere ulteriormente suddiviso in due tron-

coni:

• Algoritmi basati sull’errore quadratico: Lo scopo e di minimizzare

una funzione di errore e calcolare in tal modo i centroidi del cluster.

Funziona molto bene nel caso in cui si abbia un data set con cluster

“naturali” isolati e compatti. Di questi algoritmi fanno parte il k-means

che verra trattato in dettaglio successivamente, e il criterio dell’errore

quadratico del clustering.

• Algoritmi basati sulla teoria dei grafi: Il piu famoso di questi e

basato sulla costruzione dell’albero ricoprente minimo (Minimum Span-

ning Tree o MST) dei dati [76]. Una volta generato l’albero, vengono

rimossi gli archi del MST con le maggiori lunghezze in modo da creare

le partizioni.

Algoritmi Mixture-Resolving

In questo tipo di metodi, si fa l’assunzione che gli elementi in un cluster

siano estratti da una distribuzione, di solito si assume che ogni elemento sia

generato da una mistura di Gaussiane e l’obiettivo e quello di identificare

37


i suoi parametri. I tradizionali approcci a questo problema sono quelli di

ottenere iterativamente uno stimatore di massima similarita dei vettori pa-

rametrici della densita [28]. Per stimare i parametri delle distribuzioni, viene

utilizzato l’algoritmo Expectation-Maximization (EM) [16] .

La maggior parte di metodi Mixture-Resolving considera ogni cluster

come una distribuzione singola e successivamente vincola la forma dei settori.

Algoritmi Fuzzy

I tradizionali metodi diclustering generano partizioni; in una partizione ogni

oggetto appartiene ad uno ed un solo cluster. Da questo punto di vista i

cluster sono quindi disgiunti fra di loro. La tipologia di clustering chiamata

Fuzzy estende questa nozione, dando la possibilita di associare ogni elemento

ad ogni settore definendo una funzione di appartenenza [75]. Il piu comune

algoritmo Fuzzy diclustering e il fuzzy c-means (FCM).

La scelta della funzione di appartenenza e il problema piu importante in

questo tipo di clustering. Puo essere selezionata basandosi sulla similarita

tra cluster oppure in base ai centroidi dei cluster.

3.2 K-means

Il k-means e un tradizionale metodo diclustering il cui scopo e di partizionare

un insieme di n elementi in k cluster in modo tale che ogni oggetto appartenga

al settore con la distanza minore.

Questo problema e computazionalmente costoso (NP-completo), tuttavia

in genere che vengono usate delle euristiche per la convergenza ad un ottimo

locale. Di fatto il k-means puo essere considerato una variante dell’algoritmo

EM per le misture delle distribuzioni Gaussiane.

Dato un insieme di elementi (x1,x2, ..., xn), dove ogni oggetto e un

vettore reale d-dimensionale, l’algoritmo k-means ha lo scopo di partizionare

gli n elementi in k insiemi S = (S1, S2, ... , Sk), con k ≤ n, in modo da

38


minimizzare la somma dei quadrati della distanza intra-cluster :

arg minS

n∑i=1

∑xj∈Si

‖xj − µi‖2 (3.7)

dove µi rappresenta la media dei punti in Si.

Il k-means e molto dispendioso dal punto di vista computazionale, infatti

in generale:

• il problema e NP-completo nello spazio euclideo d anche se esistono

solo 2 settori;

• il problema e NP-completo per un numero generico di k anche in uno

spazio bidimensionale;

• se k e d sono fissati il problema ha complessita O(ndk+1 log n).

Il problema dell’elevato costo computazionale viene risolto mediante l’utilizzo

di euristiche.

L’implementazione piu comune deriva dall’algoritmo di Lloyd [35], un

procedimento iterativo mediante il quale i centroidi dei cluster vengono

aggiornati, come illustrato in Figura 3.2.

1. Scegli k centroidi che coincidano con altrettanti k elementicasuali dell’insieme dei dati oppure scegli k centroidi casualicontenuti all’interno dell’ipervolume contenente l’insieme dei dati.2. Assegna ogni elemento al centroide piu vicino.3. Per ogni cluster, ricalcola il centroide in base agli elementi delcluster stesso.4. Se non si verifica il criterio di convergenza, torna al passo 2.

Figura 3.2: Algoritmo di Lloyd

La convergenza dell’algoritmo avviene quando i valori dei centroidi non

sono cambiati rispetto all’ultima iterazione oppure sono variati di una quan-

tita inferiore ad una soglia definita a priori. Tuttavia, data la natura euri-

stica di questo algoritmo, la convergenza all’ottimo globale non e garantita

39


e il risultato dipende strettamente dall’inizializzazione dei centroidi. Inoltre

nonostante sia un metodo piuttosto veloce in genere, nel caso peggiore esso

puo essere molto lento nel convergere e in tale contesto e stato dimostrato

che anche nel caso bidimensionale esiste un particolare stato iniziale per cui

l’algoritmo prende un tempo esponenziale per convergere, ovvero 2Ω(n).

Questo metodo nonostante la particolare facilita di implementazione e la

velocita di convergenza, presenta diversi punti deboli. Oltre al fatto che non

garantisce la convergenza ad un ottimo globale come detto in precedenza,

si puo notare che l’algoritmo funziona bene solo nel caso di cluster isolati,

compatti e di dimensioni simili. Infatti il metodo tende a creare cluster della

stessa dimensione anche in presenza di settori naturali di grandezza diversa.

Per questi motivi sono state proposte tante varianti all’algoritmo, la let-

teratura infatti contiene versioni modificate mirate a compensare le difficolta

incontrate dal k-means. Alcune di queste varianti cercano di selezionare una

buona partizione iniziale in modo che l’algoritmo possa convergere piu agevol-

mente all’ottimo globale [6]. Un’altra variazione prevede invece la possibilita

di dividere o unire i cluster generati dall’iniziale algoritmo. In genere per fare

questo si impone che un cluster venga diviso quando la sua varianza risulta

maggiore di una certa soglia, mentre due cluster vengono uniti quando la di-

stanza tra i due centroidi e minore di un’altra soglia [8]. Utilizzando questa

variante e possibile ottenere la partizione ottimale partendo da un’arbitraria

partizione iniziale.

Un’altra versione dell’algoritmo prevede la selezione di una differente fun-

zione da minimizzare, Diday e Symon [17] presentano unclustering dinamico

basato sulla stima della funzione di massima verosimiglianza (maximum-

likelihood).

Pelleg e Moore [46], piu recentemente, hanno proposto una versione mo-

dificata chiamata x-means, che risolve il problema del costo computazionale

che cresce all’aumentare del valore dei parametri, risolve il problema del-

l’inizializzazione di k e cerca un rimedio per il problema della convergenza

all’ottimo globale.

40


3.2.1 Metodi di inizializzazione

Lo stato iniziale del modello del k-means condiziona il risultato finale del-

l’output, infatti esso tende a posizionare i centroidi direzionandosi verso un

ottimo locale. Poiche il problema dell’ottimizzazione globale e NP-completo,

di recente lo studio dei metodi di inizializzazione alla ricerca di un risultato

sub-ottimo e risultato di particolare interesse.

He et al. [25] categorizzano i metodi di inizializzazione in tre maggiori fa-

miglie chiamate metodi di campionamento aleatorio, metodi di ottimizzazione

della distanza e metodi di stima della densita

Metodi di campionamento aleatorio

Forse i piu utilizzati in letteratura, questi metodi inizializzano i cluster sele-

zionando campioni casuali, anche non appartenenti all’insieme dei dati, op-

pure scegliendo parametri casuali generati in modo non euristico dagli input.

Il metodo di Forgy [20] prevede l’inizializzazione dell’algoritmo mediante la

generazione di input casuali predisposti ad essere i centroidi iniziali, men-

tre MacQueen [37] propone una tecnica riconducibile alla precedente, con la

differenza che i dati non vengono generati in maniera aleatoria, ma i cluster

vengono inizializzati mediante le prime k istanze del data set.

Il problema di questi metodi risiede nel fatto che se k e troppo piccolo

la soluzione trovata potrebbe non essere soddisfacente alla luce della dispo-

sizione naturale dei cluster, e d’altra parte se k e troppo grande potrebbe

avvenire il fenomeno dei cluster vuoti.

Un metodo alternativo e quello di generare i cluster iniziali perturbando

leggermente la media dei valori di input [24, 65]. In questa maniera ogni

centroide iniziale ha quasi la stessa probabilita di essere scelto all’inizio

dell’algoritmo k-means, in modo da evitare quindi il problema dei cluster

vuoti.

Metodi di ottimizzazione della distanza

In molti metodi diclustering riconoscere le caratteristiche di un insieme di

dati significa minimizzare localmente le varianze intra-cluster senza ottimiz-

41


zare la separazione intra-cluster. Tuttavia ottimizzare le distanze tra le po-

sizioni iniziali dei centroidi al fine di ottenere una soddisfacente separazione

intra-cluster e una buona considerazione da fare. Il metodo Simple Cluster

Seeking (SCS) [67] e stato proposto per fare quanto appena detto, attraver-

so l’aggiornamento di un soglia esso stabilisce quali siano i centroidi iniziali

ottimizzando le distanze tra i centroidi iniziali.

Un metodo piu semplice ma eventualmente piu oneroso dal punto di vista

computazionale e stato proposto da Katsavounidis [30], utilizzando coppie or-

dinate di distanze per l’inizializzazione. La differenza dal precedente metodo

e che non viene utilizzata una soglia per l’inizializzazione. Inoltre poiche la

generazione di nuovi centroidi non influisce su quelli gia esistenti, la com-

plessita di questo algoritmo puo essere paragonabile ad una iterazione dello

stesso k-means utilizzando una tecnica di buffering per salvare le distanze

tra ogni esempio di input e i centroidi esistenti.

Metodi di stima della densita

Questa categoria di metodi di inizializzazione si basa sull’assunzione che i

dati di input seguano una distribuzione Gaussiana. Percio identificando le

aree dense dello spazio generato dai dati di ingresso, i centroidi cosı creati

aiutano il k-means a creare cluster compatti. Kaufman e Rousseeuw [31]

hanno introdotto un metodo che stima la densita mediante il paragone tra

coppie di distanze e inizializza i centroidi iniziali usando gli esempi di ingresso

dalle aree ad alta densita locale. Questo metodo pero ha il difetto che il tempo

richiesto potrebbe essere superiore a quello del k-means stesso nel caso in cui

il numero di n esempi sia molto grande.

Piu recentemente Al-Daoud e Roberts [5] hanno proposto un metodo che

combina l’approssimazione della densita locale con l’inizializzazione random.

Metodo Range

Esiste un metodo non classificabile tra una delle precedente famiglie, pro-

posto da Mohamudally e Khan [32], chiamato metodo Range, che prevede

l’inizializzazione dei centroidi facendo leva sul massimo intervallo dei valori

42


che ogni parametro puo assumere. Supponiamo di avere due parametri X, Y

e supponiamo di avere scelto k come numero di cluster. Allora la posizione

iniziale dei centroidi sara data dalle equazioni:

ci =(maxX −minX)

k· n (3.8)

e

cj =(maxY −minY )

k· n (3.9)

dove n indica il numero del cluster per cui viene calcolato il centroide, che

quindi varia tra 1 e k.

Usando la distanza Euclidea e necessario che gli attributi vengano norma-

lizzati in modo che essi abbiano un impatto uguale sul calcolo della distanza.

In questo modo si evita di generare cluster che sono influenzati dagli attributi

con le piu forti variazioni di valori. Questo metodo fornisce la normalizza-

zione dei dati, infatti i centroidi sono calcolati mediante la suddivisione dei

massimi intervalli degli attributi e dal numero di cluster.

3.2.2 Diagramma di Voronoi

Un tipico modo di rappresentazione dei cluster in uno spazio bidimensionale

e la costruzione di un diagramma di Voronoi a partire dei centroidi generati

dall’algoritmo di clustering. Un diagramma di Voronoi e uno speciale tipo

di decomposizione di uno spazio metrico, determinato dalle distanze rispetto

ad un insieme discreto di elementi dello spazio. In questo caso gli elementi

corrispondono ai centroidi dei cluster ed ognuno di essi e associato ad una

cella di Voronoi ovvero all’insieme dei punti dello spazio la cui distanza da

un dato centroide non e piu distante dagli altri centroidi. La metrica per

definire questi diagrammi non deve essere necessariamente euclidea, infatti

esistono anche implementazioni con metriche di Mahalanobis o Manhattan.

Un esempio di diagramma e mostrato in figura 3.3, dove sono rappresentati

i centroidi e i relativi cluster. I metodi usati per generare i diagrammi di

Voronoi sono l’algoritmo di Bowyer–Watson [12, 74] e l’algoritmo di Fortu-

ne [21] che calcola il diagramma in un tempo O(n log n), dove n rappresenta

il numero di centroidi, quindi computazionalmente vantaggioso.

43


Figura 3.3: Diagramma di Voronoi

3.3 Validita dei cluster

Uno dei problemi piu importanti delclustering e la stima dei risultati nel

trovare il partizionamento che soddisfa al meglio i dati di input. Questo e il

tema principale della validita dei cluster.

3.3.1 Concetti fondamentali

In termini generali ci sono tre approcci per stimare la validita dei cluster.

Il primo e basato sui criteri esterni, ovvero vengono stimati i risultati di un

algoritmo diclustering basato su una struttura dati prefissata. Il secondo

approccio e basato su criteri interni. Si puo stimare i risultati dell’algoritmo

diclustering in termini quantitativi, quindi coinvolgendo anche i vettori dei

dati stessi. Infine il terzo criterio e basato sui criteri relativi, ovvero si stima

una struttura diclustering mettendola a confronto con altri risultati generati

dallo stesso algoritmo ma con parametri differenti.

Questi sono i due criteri per la stima della validita dei cluster e per la

loro ottimalita:

44


1. Compattezza: i membri di ciascun cluster devono essere vicini fra di

loro il piu possibile. Una tipica misura di compattezza e la varianza,

che quindi deve essere minimizzata.

2. Separazione: i cluster stessi devono essere ben distanziati. Ci sono

tre comuni approcci che misurano le distanze tra due cluster differenti:

• Collegamento singolo: misura la distanza tra i membri piu vicini

dei cluster.

• Collegamento completo: misura la distanza tra i membri piu di-

stanti.

• Paragone dei centroidi : misura la distanza tra i centroidi dei

cluster.

I primi due approcci sono basati su test statistici e il loro maggiore svan-

taggio e l’alto costo computazionale. Inoltre, gli indici relativi a questi ap-

procci hanno lo scopo di misurare il grado in cui un data set soddisfi una

struttura definita a priori.

3.3.2 Indici di validita

I metodi di validita che verranno discussi in questa sezione sono un ottimo

mezzo a disposizione per dare una stima quantitativa ai risultati dell’algorit-

mo diclustering usato.

Criteri esterni

L’idea base in questo approccio e quella di verificare se i dati del set iniziale

sono strutturati o meno. A tal proposito si consideri una struttura di cluster

C = C1, C2, ... , Cn e una partizione P = P1, P2, ... , Pn. Facendo rife-

rimento a una coppia di punti (x1, x2), si utilizza la misura di associazione

definita al punto 3.3.1. Nello specifico a rappresenta il caso in cui entrambi

punti appartengano allo stesso cluster C e alla stessa partizione P, e analo-

gamente vengono descritti b, c e d. Gli indici gia presentati, Jaccard, Russel

45


e Rao e Sokal e Michenener, prendono valori tra 0 e 1. Un altro indice e

quello di Folwkes e Mallows [22]:

FM =a

√m1m2

(3.10)

dove m1 = a + b e m2 = a + c. Per tutte queste misure, alti valori indicano

forte correlazione tra C e P.

Esiste anche un approccio piu statistico alla validita mediante criteri

esterni, infatti si puo utilizzare il metodo Monte Carlo oppure la statistica Γ

di Huberts.

Criteri interni

Con questo approccio si cerca di stimare la validita del metodo diclustering

esclusivamente basandosi sulle caratteristiche e sui valori dei dati dell’insieme

di input.

Per i cluster generati da un algoritmo gerarchico, si usa una Cophenetic

Matrix Pc, ovvero una matrice che rappresenta il diagramma gerarchico di

creazione dei cluster. L’elemento della matrice Pc(i, j) rappresenta il numero

dell’iterazione nella quale due vettori xi e xj coesistevano nello stesso cluster

per la prima volta. Si puo quindi definire un indice chiamato Cophenetic

Correlation Coefficient, che misura il grado di similarita tra la Cophenetic

Matrix Pc e la matrice di similarita tra i due vettori P .

Criteri relativi

I precedenti approcci si basano su test statistici, pertanto hanno il forte svan-

taggio di essere computazionalmente costosi. Un metodo di validita differente

e quello basato su i criteri relativi chee non include test statistici. L’idea fon-

damentale di questo approccio e di scegliere il migliore schema diclustering

secondo un criterio predefinito. Piu precisamente, sia Palg l’insieme di para-

metri associato ad uno specifico algoritmo di clustering. Tra tutte le possibili

strutture diclustering Ci, i = 1, ... , nc, si sceglie quello che soddisfa meglio

l’insieme dei dati. Tipicamente si utilizza il parametro nc che identifica il

numero di cluster per scegliere la migliore struttura.

46


Selezionando un indice di performance q, si procede in questo modo:

1. Si fa lavorare l’algoritmo per ogni valore di nc, tra un minimo cmin e

un massimo cmax, valori definiti a priori.

2. Per ogni valore di nc si esegue l’algoritmo r volte facendo variare gli

altri parametri (se esistono).

3. Si valutano i migliori valori di q ottenuti da ciascun nc.

In generale possiamo interpretare i risultati di questa procedura in base a

come si comporta q in base a nc. Infatti se q non sembra diminuire (aumen-

tare) al crescere di nc, si cerca il massimo (minimo) tra i risultati. D’altra

parte, per gli indici che aumentano (diminuiscono) all’aumentare del numero

di cluster si cercano i valori di nc per i quali si verificano variazioni locali

significative nei risultati.

L’indice Dunn [19] cerca di identificare cluster compatti e ben separati

mediante l’equazione:

Dnc = mini=1,...,nc

min

j=i+1,...,nc

(s(ci, cj)

maxk=1,...,nc diam(ck)

)(3.11)

dove s(i, j) e la funzione di dissimilarita tra due cluster definita da:

s(i, j) = minx∈Ci,y∈Cj

d(x, y) (3.12)

mentre diam(c) e la funzione che rappresenta il diametro di un cluster, che

puo essere interpretata come una misura di dispersione dei cluster, definita

da:

diam(C) = maxx,y∈C

d(x, y) (3.13)

L’obiettivo primario di questa misura e quello di massimizzare le distanze

fra cluster e minimizzare i loro diametri. Tuttavia ci sono diversi svantaggi

nell’utilizzo di questo metodo, a cominciare dall’alto costo computazionale.

Inoltre si osserva come l’indice sia molto sensibile al rumore presente nei

dati che tende ad aumentare le lunghezze dei diametri dei cluster. Pal e

Biswas [45] hanno presentato una versione modificata del calcolo dell’indice

47


facendo uso degli alberi di minima copertura (MST) in modo da minimizzare

l’influenza del rumore sui risultati.

Una altro indice utilizzato e quello di Davies-Bouldin [15]. Si definisce

la misura di dispersione di un cluster Sn(Ck) come la distanza media degli

elementi di un dato cluster Ck dal suo centroide e una misura di dissimilarita

tra due cluster S(Ci, Cj). L’indice di Davies-Bouldin sara definito da:

DB =1

nc

nc∑i=1

maxi6=j

(Sn(Ci) + Sn(Cj)

S(Ci, Cj)

)(3.14)

I cluster sono compatti e ben separati se il risultato di questo indice e piccolo.

Anche per questo indice sono state presentate varianti [45] per migliore la

performance, anche grazie all’utilizzo di MST.

Per quanto riguarda ilclustering gerarchico esistono quattro tipi di indici

di validita, che vengono calcolati ad ogni passo delle loro iterazioni. Si trat-

ta degli indici RMSSTD [58] (Root-mean-square standard deviation), SPR

(Semi-partial R-squared), RS (R-squared) e CD(Cluster Distance).

48

Capitolo 4

Sviluppo del Software

Lo sviluppo del progetto per l’estrazione di feature e stato realizzato mediante

l’utilizzo di una telecamera di rete Axis [1]. In seguito all’acquisizione delle

immagini e stato possibile elaborare le informazioni ottenute per rilevare le

caratteristiche desiderate, nel nostro caso edge e corner, e inviarle ad un

client connesso. La telecamera utilizzata e una Axis P1343 fissa, adatta

alla videosorveglianza di luoghi pubblici sia interni che esterni. Il lavoro

si e sviluppato mediante la creazione dell’applicazione su un PC usando un

apposito Software Development Kit (SDK) fornito dalla societa Axis (si faccia

riferimento all’appendice B). L’applicazione e stata poi montata sulla camera

e mandata in esecuzione.

L’applicazione si basa sulla continua interazione tra client, il browser,

e server, la camera Axis stessa. Il server e stato programmato in C++

utilizzando le interfacce messe a disposizione dal Software Development Kit

della societa Axis. Lo scopo e stato quello di creare un sistema di cattura

ed elaborazione immagini mediante gli algoritmi di rilevamento feature. Il

passo successivo e stato quello della creazione di uno standard per salvare

le caratteristiche ottenute e inviarle al client in attesa. Il client invece e

basato su una semplice pagina HTML che viene resa dinamica dall’utilizzo

di JavaScript. Ogni richiesta al server e stata fatta usando la tecnologia

AJAX.

In questo capitolo verra esposto il funzionamento della telecamera utiliz-

49

CAPITOLO 4. SVILUPPO DEL SOFTWARE

zata, sia dal punto di vista delle sue componenti che dell’ambiente di svi-

luppo, la progettazione del server dell’applicazione in tutte le sue principali

componenti e la realizzazione dell’interfaccia lato client con l’utilizzo delle

recenti tecnologie per i browser.

4.1 Piattaforma Axis

La telecamera Axis e un dispositivo che genera flussi video di alta qualita.

Questi dati vengono trasmessi su rete IP e sono visualizzabili in tempo reale

da qualsiasi computer che sia collegato in rete.

4.1.1 Specifiche P1343

La telecamera Axis P1343 e fissa, ovvero non e possibile farla ruotare lungo

l’asse orizzontale (pan) o inclinare rispetto all’asse verticale (tilt), e varifocale

ma non consente un controllo remoto dello zoom. La camera e provvista del

Figura 4.1: La camera Axis P1343

processore integrato ARTPEC-3 (Axis Real Time Picture Encoder), creato

per la compressione delle immagini. Questo chip supporta vari tipi di sensori

CCD e CMOS; dispone di funzioni incorporate per la regolazione della ni-

tidezza, la compensazione della retroilluminazione, la riduzione dei disturbi

e il bilanciamento del bianco. Supporta l’elaborazione simultanea di flussi

Motion-JPEG e H.264, ed e in grado di elaborare le immagini acquisite in

contemporanea da un massimo di 4 fonti video a una velocita massima di

30 fotogrammi al secondo nonche di comprimerle in tempo reale. Tuttavia

il processore non e in grado di eseguire calcoli in virgola mobile in quanto e

sprovvisto di FPU.

50


La telecamera e dotata di una memoria RAM di 128 MB e una memoria

flash di 128 MB. In questo modello e presente anche un sistema I/O audio,

con microfono integrato e uscita a livello di linea.

La camera P1343 puo essere alimentata anche per mezzo della tecnologia

Power over Ethernet, ovvero puo usare lo stesso cavo Ethernet che la collega

alla rete come fonte elettrica.

Infine, per quanto riguarda le caratteristiche ottiche, l’obiettivo della ca-

mera e varifocale, ovvero la lente garantisce un ampia gamma di lunghez-

ze focali in cui il fuoco (e l’ingrandimento) cambia a seconda della loro

variazione.

4.1.2 Codec video

Il processore della camera Axis P1343 e in grado di elaborare ed inviare flussi

di video nei formati Motion-JPEG e H.264 a seconda della scelta dell’utente,

ma non ha la capacita di codificare nel formato MPEG-4 Part 2, come diversi

altri modelli.

Motion-JPEG

Il Motion-JPEG, o M-JPEG, e un nome informale di una classe di formati

video dove ciascun frame o semiquadro interlacciato di un video digitale viene

compresso separatamente come un’immagine JPEG. Inizialmente sviluppato

per le applicazioni multimediali per PC, questo tipo di formato e utilizza-

to adesso da diversi dispositivi video portatili, come ad esempio le camere

digitali.

Il formato Motion-JPEG usa forma di compressione con perdita, basata

sulla trasformata discreta del coseno (DCT) in modo da convertire ciascun

frame o semiquadro del video originale dal dominio del tempo al dominio

della frequenza. In questo dominio l’informazione viene ridotta mediante il

processo di quantizzazione. Questo metodo e conveniente perche nel dominio

della frequenza i coefficienti delle frequenze alte che caratterizzano l’imma-

gine sono tipicamente valori relativamente piccoli con alta compressibilita.

51


I coefficienti quantizzati vengono quindi messi in sequenza e inviati senza

ulteriore perdita di informazione.

Nella maggior parte delle implementazioni M-JPEG e consentito all’uten-

te di avere il controllo sul tasso di compressione, mentre nei sistemi embedded

questi parametri sono spesso prefissati e non modificabili. La camera Axis

offre la possibilita di controllare la qualita della compressione mediante le

sue API (Application Programming Interface).

Il fatto che ogni frame venga elaborato indipendentemente dagli altri, a

differenza dei formati MPEG 2 e H.264/MPEG-4 AVC, limita la sua efficienza

di compressione, ma da un altro punto di vista il costo computazionale e

l’occupazione di memoria sono inferiori. Da questa analisi segue che la qualita

dell’immagine del formato M-JPEG e funzione direttamente della complessita

spaziale di ciascun frame.

H.264

Lo standard H.264 e uno dei formati piu utilizzati per la compressione video.

Questo standard e utilizzato in un grande numero di applicazioni come per

esempio nella trasmissione di contenuti video a basso bit-rate attraverso le

reti wireless, nel video streaming attraverso internet e nella distribuzione di

contenuti in Blu Ray Disc. Il punto di forza di H.264 sta nella compressione

che rispetto al precedente MPEG2 e migliore di oltre il 50%. Offre una

qualita pari allo standard MPEG2 a quasi la meta del data-rate, con una

risoluzione fino a quattro volte superiore a quella supportata dal formato

MPEG-4 Part 2 a parita di data-rate.

Il formato H.264 usa sostanzialmente lo stesso processo di compressione

del precedente MPEG2 ma, a spese di una maggiore complessita e quindi

di tempo di calcolo, esso consente un migliore sfruttamento delle ridondanze

statistiche e riduce la percezione soggettiva delle distorsioni. La trasformata

DCT viene applicata su blocchi di immagine piu piccoli (4x4), viene ridotto

l’effetto brick mediante un filtro di ricostruzione nel processo di decodifica e

si ha anche un miglioramento della codifica entropica.

52


4.1.3 API

La camera Axis ha a disposizione un insieme di API (Application Program-

ming Interface) basate sul protocollo HTTP, chiamato VAPIXR© [2]. Questo

strumento consente all’utente di richiedere immagini, controllare le funzio-

nalita della camera, variare o richiedere i valori dei parametri interni ed

altro. Ogni richiesta inviata e gestita dal Web server integrato della camera.

VAPIX R© e composto da:

• HTTP API

• Parameter API

• RTSP API

Per ottenere lo stream di un video dalla camera in genere si usa M-JPEG

o H.264. Un’altra opzione molto inefficiente e quella di richiedere periodica-

mente immagini singole e poi riordinarle. In questo caso viene aperta una

connessione HTTP per ogni richiesta e una volta ultimato il trasferimen-

to dell’immagine viene subito chiusa. Il numero di stream video che puo

fornire la camera e variabile in base al modello. La P1343 riesce a servire

circa 10 stream al massimo, ma in tal caso le prestazioni di servizio risulta-

no estremamente deteriorate ed il frame-rate del video ricevuto sara molto

basso.

Una caratteristica molto vantaggiosa di queste API e la possibilita di

richiedere uno stream video con caratteristiche in base alle proprie esigenze.

Infatti in seguito alla richiesta HTTP e possibile specificare dei parametri,

seguendo un’apposita sintassi, in modo da ricevere il tipo video desiderato.

Tra i parametri selezionabili ci sono il numero di frame al secondo dello

stream (frame-rate o FPS), la risoluzione del video, la compressione JPEG

delle immagini (nel caso di uno stream M-JPEG), il testo in sovrimpressione

ed altri.

53


4.2 Server

Il server del progetto sviluppato e rappresentato dalla telecamera stessa.

Esso si occupa di fornire tutti i servizi e le funzionalita richiesti da un utente

tramite browser.

La costruzione del server e stata interamente scritta nel linguaggio ad

oggetti C++, utilizzando alcune librerie standard e appoggiandosi alle inter-

facce fornite dall’SDK della Axis. Il ruolo fondamentale del progetto viene

assunto dai vari gestori, ovvero oggetti che hanno il compito di organizzare e

sincronizzare le operazioni principali per l’esecuzione. I gestori si suddividono

in:

• Gestore immagini: apre uno stream di immagini non compresse in

base alla risoluzione desiderata e gestisce l’elaborazione dei dati secondo

i parametri scelti dall’utente;

• Gestore segnali: e il responsabile della gestione dei segnali di control-

lo dell’applicazione, quando il client invia un segnale di stop il gestore

si occupa di avvisare l’applicazione e interromperla;

• Gestore parametri: usando l’interfaccia predisposta dall’SDK questo

gestore si pone da intermediario tra l’utente e l’applicazione per la

selezione e l’aggiornamento in tempo reale dei parametri;

• Gestore HTTP: si occupa di gestire l’interazione tra applicazione e

utente, quindi disponendo i dati in uscita in modo da essere inviati al

browser;

• Gestore thread: crea un nuovo thread nel caso in cui ci sia bisogno

di flussi di esecuzione separati.

4.2.1 Esecuzione dell’applicazione

Il flusso dell’esecuzione del programma prevede una prima fase di inizializ-

zazione delegata ai vari gestori, i parametri inizialmente assumono valori

assegnati in base alle decisioni dell’utente oppure in base ai valori di default

54


e inoltre vengono create le CGI usate per il trasferimento dei dati. Una volta

terminate queste operazioni preliminari si entra nel ciclo principale dell’ap-

plicazione. Questa fase e composta da cinque stati diversi che l’applicazione

puo assumere nel tempo:

• IDLE: in questo stato l’applicazione e ferma, rimane in attesa finche

non riceve un segnale di inizio esecuzione;

• START: viene aperto uno stream secondo la risoluzione di immagine

definita dall’utente e poi si predispone un cambio di stato immediato;

• RUN: stato principale dell’applicazione, vengono eseguiti gli algoritmi

di rilevamento feature e si tiene traccia di eventuali cambiamenti;

• RECONFIG: il parametro della risoluzione e stato cambiato, quin-

di in questo stato si chiude il vecchio stream per aprirne uno nuovo

secondo le nuove disposizioni;

• STOP: lo stream video viene chiuso e l’applicazione torna nello stato

di quiete;

Il diagramma degli stati e mostrato in figura 4.2.

Figura 4.2: Il diagramma degli stati dell’applicazione

Il programma quindi rimane all’interno questo ciclo, elaborando ogni

frame che viene acquisito dal relativo gestore.

55


4.2.2 Acquisizione delle immagini

L’acquisizione delle immagini e delegata all’apposito gestore, che si occupa

anche di assegnare le operazioni di elaborazione dell’immagine agli oggetti

competenti e salvare le feature ottenute.

Sostanzialmente il processo e suddiviso in due fasi: apertura e elabora-

zione. Nella fase di apertura vengono letti i parametri desiderati dall’utente

e quelli default per aprire uno stream video di immagini non compresse. La

prima scelta riguarda la risoluzione del video, ovvero la quantita di pixel

che compone la larghezza e l’altezza dell’immagine. Questo e un punto di

decisione fondamentale perche l’applicazione spende parte del tempo per ese-

guire l’acquisizione dell’immagine e inoltre la scelta di risoluzioni piu elevate

implica un tempo di elaborazione maggiore anche da parte degli algoritmi.

Perche l’esecuzione sia veloce in genere si scelgono risoluzioni basse, ovvero

160× 120, 240× 180 o 320× 240. Superato questo scalino il tempo di acqui-

sizione ed elaborazione delle immagini sara troppo alto e compromettera la

velocita di esecuzione dell’applicazione, riuscendo ad inviare le informazioni

elaborate solo poche volte al secondo.

In questa sezione e possibile anche decidere il frame-rate di acquisizione e

il formato dell’immagine. Al fine dell’elaborazione dell’immagine, viene scelto

il formato YUV chiamato Y800, per cui si ottiene un immagine non compressa

in scala di grigi. L’altra opzione sarebbe stata di acquisire l’immagine in

formato JPEG, ma cio non avrebbe consentito un facile accesso ai singoli

pixel per l’estrazione dei punti caratteristici.

La seconda fase invece prevede l’utilizzo dello stream precedentemente

aperto per salvare il frame corrente in un buffer di memoria. Successivamente

i dati memorizzati vengono inviati ai blocchi degli algoritmi di competenza,

a seconda di quali vengano abilitati dall’utente, ovvero l’algoritmo FAST,

l’operatore di Sobel e il k-means. Qualora si decidesse di attivare uno di

questi algoritmi, e necessario passare anche i parametri specifici per ognuno

di essi.

56


Frame-rate

Esiste un punto di fondamentale importanza in questa sezione dell’applica-

zione riguardante il frame-rate di acquisizione. Si parte dal fatto che la tele-

camera puo al massimo acquisire 30 frame al secondo, valore che rappresenta

non solo un limite superiore ma anche un importante punto di riferimento. Il

problema della scelta della risoluzione dello stream video limita fortemente

la quantita di frame al secondo che la camera riesce poi a elaborare con gli

algoritmi; infatti questo numero diminuisce all’aumentare della risoluzione.

Una possibile soluzione per massimizzare la quantita di immagini elaborate

e quello di diminuire il frame-rate di acquisizione opportunamente. Infatti se

viene scelta una risoluzione piuttosto elevata e piuttosto inutile mantenere

un frame-rate di acquisizione a 30 FPS quando l’applicazione in realta riesce

a lavorarne molte di meno.

La soluzione ottimale e quella di far coincidere il valore del parametro

di FPS con il numero di immagini elaborate al secondo, ma di fatto non e

realizzabile. Il problema sta nel fatto che il frame-rate di acquisizione non e

modificabile in tempo reale, ovvero la procedura e sempre quella di chiudere

lo stream esistente e crearne uno nuovo secondo i nuovi input. Questa ope-

razione comporta alcuni secondi di elaborazione, pertanto non si puo creare

un sistema adattivo per la scelta di questo valore.

Un’altra soluzione, questa volta sub-ottimale, e quella di trovare il valore

ottimo per ogni risoluzione possibile e selezionarlo opportunamente ogni volta

che viene aperto uno stream. Il problema che si pone in questo contesto e

di natura diversa, ovvero la soluzione e funzionale solo nel caso in cui si

ha la sicurezza che la scena rimanga sempre la stessa. Infatti basta che la

telecamera inquadri una scena piu dettagliata o meno dettagliata che il valore

scelto non e piu ottimo e la situazione diventa sconveniente. Infatti se una

scena ha un alto contenuto informativo, la camera impiega piu tempo sia ad

acquisire e memorizzare l’immagine che successivamente ad elaborarla con

gli algoritmi di rilevamento. D’altra parte se la scena e scarna di dettagli, la

riduzione del frame-rate funge da freno per l’applicazione, che quindi elabora

ed invia i dati ad una frequenza minore rispetto alle sue potenzialita.

57


Per il progetto si e scelto una modalita alternativa, che prende i tratti

principali dalle due soluzioni proposte in precedenza. Per prima cosa sono

stati confrontati i risultati di performance relativi alla generazione di dati

elaborati sulle varie scene alle diverse risoluzioni. Valutando il numero di FPS

generati nel caso peggiore (scena molto dettagliata) e caso migliore (scena

monocromatica) si e scelto il valore medio. Assumendo che la probabilita di

avere piu o meno dettagli in una scena segua una distribuzione Gaussiana, il

valore medio scelto rappresenterebbe anche l’evento piu probabile.

Ovviamente questa situazione ideale si dissocia dalla realta, ma e stato

osservato che scegliendo il valore in questo modo ci si trova il piu delle volte in

condizioni ottimali, e gli svantaggi dovuti alla presenza o assenza di dettagli

sono considerevolmente ridotti.

4.2.3 Esecuzione algoritmi

Gli algoritmi di rilevamento feature rappresentano l’essenza dell’applicazio-

ne, quello per cui l’intero progetto e stato creato. Il punto di partenza e

rappresentato dal gestore immagini che si occupa di passare il frame appena

ottenuto alle strutture di competenza.

L’applicazione prevede due algoritmi di rilevamento diversi, FAST e So-

bel, che possono essere attivati a discrezione dell’utente e inoltre e data la

possibilita di una loro coesistenza. Un algoritmo di clustering, il k-means,

puo essere eseguito sui dati ricevuti dall’algoritmo di rilevamento di corner,

ovviamente solo nel caso in cui questo sia attivo. Per memorizzare le feature

risultanti dagli algoritmi sono stati predisposti tre buffer di testo all’interno

del gestore immagini, uno per ogni algoritmo. Lo stesso gestore si occupa di

svuotare i buffer una volta ottenuta una nuova immagine.

Implementazione FAST

Per quanto riguarda l’algoritmo FAST, viene creato un oggetto apposito che

si occupa di tutte le funzioni possibili del metodo, quindi rilevamento, asse-

gnazione di punteggio, rimozione non massimi. Viene dunque passato all’og-

58


getto non solo il buffer contenente i valori di ogni singolo pixel dell’immagine

acquisita, ma anche tutti i parametri necessari all’elaborazione:

• dimensione dell’immagine;

• valore della soglia di rilevamento;

• attivazione/disattivazione della soppressione dei non massimi;

• attivazione/disattivazione del k-means ;

• numero di cluster per il k-means

L’algoritmo di rilevazione corner utilizzato e il Generic FAST discusso

al paragrafo 2.1.4. Questa scelta deriva dal fatto che l’algoritmo originale

ha una qualita di rilevamento inferiore. D’altra parte nemmeno il Learned

FAST e stato ritenuto adatto al nostro scopo. Infatti se da una parte ha

un tempo di esecuzione inferiore al Generic FAST, dall’altra presenta due

grosse limitazioni in questo contesto applicativo. La prima riguarda il fatto

che allenare un rilevatore su una scena particolare implica che, nel caso in

cui la camera acquisisca un panorama completamente diverso, non si avrebbe

garanzia della stessa qualita della scena iniziale. Il Generic FAST invece ha

lo stesso comportamento in qualsiasi scenario si trovi a lavorare. La seconda

limitazione e in qualche modo legata alla prima. L’allenamento di un rileva-

tore prevede la creazione di migliaia di righe di codice in C++, quindi per

inserire le righe di codice nel programma il procedimento diventa oltremodo

macchinoso, perdendo quindi la portabilita dell’applicazione stessa. Quindi

in questo contesto, a scapito di un breve intervallo di ritardo di tempo rispet-

to alla versione automatizzata, e stata scelta una versione leggera, portabile

e robusta dell’algoritmo.

Il metodo di memorizzazione dei risultati derivati dall’esecuzione del FA-

ST e stato scelto in modo da facilitare la lettura da parte del client. Il buffer

di testo creato nel gestore immagini viene quindi riempito dalle coordinate

degli angoli rilevati, assegnando ad ogni cifra del numero di coordinata il

rispettivo carattere ASCII, e inoltre sono stati usati due caratteri speciali

per creare una sorta di sintassi. Infatti c’era la necessita che le coordinate

59


x e y fossero separate tra di loro cosı come le coppie stesse di coordinate. Il

carattere usato per la separazione inter-coordinate e stato scelto il punto e

virologa, mentre per la separazione intra-coordinate il carattere virgola.

Ai fini di una migliore performance, e stato realizzato un ulteriore artificio

nel caso di soppressione dei non massimi. Infatti in questa situazione, per

l’assegnazione dei punteggi e la successiva rimozione degli angoli, e necessario

che i dati rilevati dall’algoritmo siano rappresentati come coppie di interi

e non come array di caratteri. D’altra parte, durante il rilevamento delle

feature e superfluo salvare le coordinate dei corner nel buffer testuale poiche

la successiva soppressione dei non massimi comporta la creazione di una

differente stringa testuale. Quindi e stato sufficiente selezionare il modo di

memorizzazione delle feature (testuale/intero) in base alla presenza o assenza

della soppressione dei non massimi, in modo da non spendere tempo per

l’esecuzione di operazioni che poi sarebbero risultate inutili.

Implementazione Sobel

L’algoritmo di rilevamento di edge utilizzato e l’operatore di Sobel. La sua

implementazione e piuttosto semplice e non ci sono artifici particolari per

migliorare la performance. Allo stesso modo dell’algoritmo FAST, l’intensita

dei pixel viene memorizzata come testo in un buffer creato appositamente, in

modo che ad ogni cifra del valore venga assegnato il corrispondente carattere

ASCII. In questo caso la creazione di una specifica sintassi e semplificata,

visto che ogni pixel e identificato da un valore e i dati vengono elaborati

sequenzialmente. Per distanziare i caratteri che indicano l’intensita dei vari

pixel gli uni dagli altri e stato utilizzato il carattere punto e virgola.

Anche in questo caso l’utente puo interagire direttamente per specifica-

re il comportamento dell’algoritmo, quindi il gestore immagini oltre ai dati

dei pixel invia all’oggetto responsabile dell’algoritmo di rilevamento edge i

parametri:

• dimensione dell’immagine;

• tipo di quantizzazione richiesta;

60


• livello di soglia, nel caso in cui l’immagine venga binarizzata;

Per quanto riguarda la quantizzazione, viene passato un valore intero n

compreso tra 0 e 7. L’idea e stata quella di assegnare ognuno di questi valori

ad una classe di quantizzazione, rendendo il procedimento automatico. In-

fatti eseguendo n volte lo shift-left di 2 si ottiene un risultato che corrisponde

al numero totale di grigi che rappresenta l’immagine. Quindi ricalibrando i

valori in uscita dall’algoritmo di Sobel in base alla nuova scala di grigi si e

potuto costruire l’immagine quantizzata.

Implementazione k-means

L’algoritmo di clustering k-means e stato integrato all’interno dell’algoritmo

FAST, in quanto i dati estrapolati dal rilevamento corner sono stati usati

come l’insieme iniziale del k-means. Anche in questo caso, le coordinate dei

centroidi sono state salvate come testo in un apposito buffer seguendo la

stessa sintassi utilizzata per l’algoritmo FAST.

Il numero di partizioni k e scelto dall’utente e tale valore viene passato

alla struttura di competenza del k-means ; tuttavia e stato reso disponibile

l’utilizzo un indice di validita per trovare il numero ottimale di partizioni.

L’idea di base e stata quella di dover scegliere un’opportuna misura di qualita

delle partizioni in modo tale che non fosse troppo complessa dal punto di

vista computazionale, non comprendesse calcoli in virgola mobile e desse un

buon risultato sull’insieme di feature rilevate. L’indice scelto e stato quello

di Davies-Bouldin perche risponde a tutti questi requisiti. Tuttavia e stata

fatta un’ulteriore considerazione sul calcolo dell’indice. Nonostante questo

metodo preveda un tempo di esecuzione relativamente basso se effettuato su

un numero di cluster definito a priori, bisogna considerare che questo tipo

di indice fa parte dei criteri relativi di misura, quindi richiede che il calcolo

venga effettuato su un intervallo di partizioni, ovvero a partire da un numero

minimo di cluster fino ad un massimo. Dal punto di vista computazionale puo

essere davvero proibitivo assumere una strategia di questo tipo, soprattutto

al crescere del volume dell’insieme di feature. La decisione presa e stata

quella di creare una funzione gestibile direttamente dall’utente, in modo che

61


l’indice migliore potesse essere selezionato solo quando richiesto. Un’altra

soluzione studiata e quella di aggiornare il numero di partizioni chiamando

la stessa funzione periodicamente dopo un certo numero di frame.

Il metodo scelto per l’inizializzazione dei centroidi e stato il metodo Ran-

ge, in quanto e risultato quello che ha soddisfatto al meglio i requisiti di

qualita e velocita di esecuzione. I metodi random utilizzati nonostante la

buona performance hanno mostrato scarsi risultati in prossimita di cluster

non troppo separati tra di loro.

Sempre in merito all’inizializzazione dei centroidi e stata fatta un’altra

considerazione. Il punto principale si basa sul fatto che una scena sia per

la maggior parte del tempo statica, ovvero con apparente assenza di movi-

mento all’interno di essa. In tale contesto, calcolando i centroidi dei cluster

tra due frame consecutivi si puo notare come la posizione di questi vari in

misura molto ridotta rispetto alla grandezza dell’immagine. La probabilita

che un centroide sia situato in un intorno di pochi pixel rispetto allo stesso

centroide del frame precedente e molto alta. Quindi la procedura utilizza-

ta per l’inizializzazione e stata quella di creare un primo input di centroidi

mediante il metodo Range e poi per ogni altro frame inizializzare i centroidi

con i valori ottenuti dall’esecuzione del k-means sull’immagine precedente.

In questo modo, essendo l’errore tra due centroidi consecutivi molto ridotto,

viene aumentata la velocita di convergenza dell’algoritmo, di fatto limitando

considerevolmente il numero di iterazioni.

4.2.4 Interfaccia di rete

Dopo l’acquisizione delle immagini e la relativa elaborazione, il problema che

si pone e quello di realizzare un sistema efficace per l’invio dei dati ottenuti

al client. Queste mansioni vengono ricoperte dal gestore HTTP mediante

l’uso delle interfacce dell’ambiente Axis.

Definizione 4.2.1 (Common Gateway Interface) Una Common Gate-

way Interface o CGI e una tecnologia standard usata dai Web server per

interfacciarsi con applicazioni esterne. Ogni volta che un client richiede al

62


Web server un URL corrispondente ad un programma CGI, il server lo esegue

in tempo reale, generando dinamicamente informazioni.

Il Gestore HTTP viene inizializzato mediante la creazione di due CGI

specifiche per l’interazione con il client :

• Data CGI : utilizzata per l’invio dei dati riguardanti le feature al client ;

• Update CGI : utilizzata per l’aggiornamento dei parametri riguardanti

i vari algoritmi;

In questo modo ogni volta che il client richiede l’utilizzo di un programma

CGI, il server risponde mediante l’output e lo invia al client in tempo reale.

Invio dei dati

Il sistema di invio dei dati e stato creato in modo che per ogni tipo di featu-

re richiesta venga utilizzata una singola CGI in grado di lavorare in base al

contesto in cui si trova. Infatti la scelta del tipo di feature richiesta e stata de-

legata all’utente, che interagisce mediante il browser. La richiesta dell’utente

contiene un parametro secondo il quale la CGI decide come comportarsi. Ci

sono tre tipi di richiesta:

1. Corner ;

2. Edge;

3. Corner + Edge;

Una volta selezionata la modalita, il gestore HTTP si occupa anche di atti-

vare l’algoritmo relativo prima dell’invio dei dati e di disattivarlo una volta

terminato il compito. Il buffer di memoria contenente le feature desiderate

viene posto in uscita e inviato al client mediante il protocollo HTTP, usando

l’apposita libreria fornita da Axis.

63


Multithreading

Il punto fondamentale nell’invio dei dati e che viene aperta una sola connes-

sione tra client e server per tutta la durata della trasmissione. Il motivo di

questa scelta nasce dal fatto che per mantenere aperta una singola connessio-

ne, il flusso di esecuzione deve iterare dentro un ciclo all’interno del relativo

programma CGI per ogni frame elaborato. Tuttavia una volta inviata la

richiesta di dati, il flusso di esecuzione esegue correttamente il rilevamento

feature per la prima immagine acquisita, riempie il buffer di competenza ed

entra nel ciclo della CGI. A questo punto, per mantenere la connessione aper-

ta, l’applicazione rimane intrappolata all’interno del ciclo e, non potendo piu

elaborare nuove immagini, continua a mandare i risultati del primo frame

acquisito finche l’utente non termina la comunicazione.

La soluzione e stata quella di creare un sistema multithread, in modo che

ogni richiesta dell’utente possa essere gestita tramite un flusso di esecuzione

parallelo a quello principale. Il passo successivo e stato quello di coordinare i

due thread, quello principale e quello di richiesta, in modo che ad ogni elabo-

razione di un frame corrisponda un output verso il client. Il primo approccio

e stato quello di creare un semplice semaforo creato con le apposite variabili

di mutua esclusione. Quindi, imponendo che l’invio dei dati avvenga solo

dopo la terminazione del rilevamento delle feature e quindi dopo il riempi-

mento dei buffer di memoria, e garantito che i pacchetti dei dati riguardanti

le caratteristiche immagine vengano inviati integri e sequenzialmente.

La soluzione piu complessa e quella di creare una coda di priorita per la

gestione dei thread, in modo che piu client possano collegarsi ai programmi

CGI e ottenere contemporaneamente dati, anche di diverse feature. Il pro-

blema in questo caso e che le risorse a disposizione sono limitate e la gestione

dell’invio di dati verso piu client e computazionalmente pesante se trattata

dalla singola camera, quindi il contributo dell’efficienza di elaborazione degli

algoritmi scelti viene in questo modo perso.

64


Delimitazione dei pacchetti

L’ultima considerazione fatta riguardo la trasmissione dei dati e stata quel-

la di porre alcune delimitazioni ai pacchetti inviati, in modo che il client

potesse distinguere le sezioni di dati inviate e elaborarle come blocchi a se

stanti. Inoltre nel caso di invio di pacchetti con piu tipologie di feature al suo

interno, ad esempio l’invio contemporaneo di corner ed edge, si e fatto uso

di altri delimitatori speciali, in modo diverse caratteristiche potessero essere

riconosciute e trattate differentemente per la rappresentazione.

Aggiornamento dei parametri

Per conferire all’applicazione una certa dinamicita, e stato reso possibile l’ag-

giornamento in tempo reale dei parametri degli algoritmi utilizzati, come ad

esempio la soglia per l’algoritmo FAST, la quantizzazione dell’immagine ot-

tenuta con Sobel e altri. Il principio su cui si basa questa operazione e

piuttosto banale: l’utente agisce mediante interfaccia grafica facendo variare

i parametri in base alle proprie esigenze; in questo modo viene inviata una

richiesta alla CGI di aggiornamento che si occupa di riconfigurare il para-

metro variato in base al valore ricevuto. La funzione callback che gestisce il

parametro viene chiamata, quindi il valore viene aggiornato in tempo reale

senza bisogno di riavviare l’applicazione.

Esiste solo un caso in cui l’aggiornamento non avviene in tempo reale ov-

vero quando si desidera cambiare la risoluzione di acquisizione dell’immagine.

Questo fatto e dovuto dai limiti della camera stessa, che ha bisogno del tempo

necessario per chiudere lo stream video ed aprirne uno nuovo con la risoluzio-

ne desiderata, quindi avviare un nuovo thread e ricominciare l’elaborazione

dei dati.

4.3 Interfaccia utente

Quello descritto fino adesso riguardava tutto cio che avviene all’interno della

camera, ovvero le modalita di generazione ed invio dei dati. L’altro aspetto

65


di fondamentale interesse riguarda la richiesta e la rappresentazione dei dati

riguardanti le feature.

Il client dell’applicazione e rappresentato da un semplice Web browser,

che collegandosi alla camera mediante l’indirizzo IP e in grado di ricevere i

flussi di informazione. Tuttavia per sviluppare un sistema di richieste ade-

guato alle specifiche di dinamicita e velocita di interazione e stato necessario

l’utilizzo della tecnologia AJAX.

Per la rappresentazione delle feature ottenute, quindi allo scopo di dare

un senso ai dati elaborati e stato utilizzato il JavaScript, in modo tale da

disegnare le caratteristiche direttamente sulla pagina web.

4.3.1 Tecnologia AJAX

Con il termine AJAX (Asynchronous JavaScript and XML) [3] si indica un

insieme di alcune tecnologie, sviluppate in modo indipendente, che aggre-

gandosi tra loro danno vita ad un meccanismo ancora piu potente. AJAX

incorpora le seguenti tecniche:

• HTML e CSS per il markup e lo stile di presentazione;

• DOM (Document Object Model) manipolato attraverso un linguaggio

ECMAScript come JavaScript o JScript per mostrare le informazioni

ed interagirvi;

• XML e XSLT per interscambio e manipolazione dei dati;

• XMLHttpRequest per le richieste asincrone di dati al server ;

• JavaScript che funge da collante per tutta la struttura;

Le prime applicazioni Web lavoravano secondo un solito schema: ad ogni ri-

chiesta HTTP verso unWeb server succedeva un processo interno di recupero

ed elaborazione dati, un’eventuale comunicazione verso sistemi collegati ad

esso e infine l’invio di una pagina HTML al client. Questo modello tuttavia e

un adattamento dell’originale utilizzo del Web come mezzo di comunicazione

66


ipertestuale, e quindi non ha la stessa efficacia se utilizzato per le applicazio-

ni. Infatti il problema nasce dal fatto che durante il tempo di elaborazione

del server, il client non esegue nessuna operazione perche in attesa della

risposta. Inoltre si deve tenere conto del tempo che impiega il client a rica-

ricare l’interfaccia di una pagina per ogni richiesta. Tutto questo ha favorito

l’introduzione di AJAX per migliorare le prestazioni delle applicazioni Web.

Un’applicazione AJAX elimina la classica interazione invia/ricevi tra le

due parti introducendo uno strato intermediario, chiamatomotore AJAX, tra

l’utente e il server. Invece di caricare una paginaWeb, all’inizio della sessione,

il browser carica un motore AJAX scritto in JavaScript e in genere nascosto

all’utente. Questa struttura e responsabile sia del rendering dell’interfaccia

grafica che della comunicazione con il server come intermediario per conto

dell’utente. In questo modo il client non si trova mai nella situazione in cui

deve attendere la risposta del server prima di intraprendere qualsiasi azione.

Ogni azione dell’utente che avrebbe generato una richiesta HTTP assu-

me la forma di una chiamata di una funzione in JavaScript verso il motore

AJAX. Ogni richiesta che non richiede un riscontro diretto del server, viene

gestita dal motore stesso, mentre se c’e la necessita di qualche dato aggiun-

tivo di qualsiasi natura, AJAX invia richieste asincrone senza congestionare

l’interazione con l’utente.

4.3.2 XMLHttpRequest

XMLHTTP e un set di API che possono essere usate da JavaScript, JScript,

VBScript e altri linguaggi di scripting dei browser per trasferire XML o altri

dati tra un Web server e un client tramite il protocollo HTTP. Il piu grande

vantaggio di XMLHTTP e la possibilita di aggiornare dinamicamente una

pagina Web senza ricaricare l’intera pagina. Viene usato da alcun siti Web

per velocizzare applicazioni dinamiche.

XMLHttpRequest e un elemento fondamentale di AJAX, ed e utilizzato in

molti siti Web per implementare applicazioni fruibili via browser dinamiche

ed interattive. Questo oggetto ha la caratteristica di consentire lo sviluppo di

un’interfaccia utente molto dinamica e allo stesso tempo permette di mante-

67


nere le strutture di funzionamento piu importanti nel livello applicativo della

pila protocollare.

Dopo avere istanziato l’oggetto si ha a disposizione una serie di metodi ed

attributi per modellare l’applicazione secondo i requisiti. Il metodo open()

pone le basi per eseguire la richiesta, specificando il tipo di operazione de-

siderata e l’URL per la connessione. Le operazioni possibili in una richiesta

XMLHttpRequest sono:

• GET: richiede la rappresentazione di una risorsa specifica;

• POST: invia i dati da essere elaborati alla risorsa specifica, includendoli

nella richiesta stessa;

• PUT: carica una rappresentazione nella risorsa specifica;

• DELETE: cancella una risorsa specifica;

• HEAD: richiede la stessa risposta che avrebbe ricevuto con il metodo

GET, ma senza il corpo della risposta;

• OPTIONS: ritorna le operazioni possibili che il server supporta per

l’URL specificato;

Oltre a questi due parametri obbligatori per eseguire una richiesta, l’oggetto

consente di specificarne altri opzionali. Il primo di questi riguarda la natura

della richiesta, asincrona (di default) o sincrona. Oltre a questo e possibile

inserire utente e password, nel caso in cui si necessiti di autenticazione per

accedere al server.

Il metodo send() e il responsabile dell’invio della richiesta e, a seconda

dell’operazione scelta, puo includere al suo interno dei contenuti per il server.

Per riuscire a modellare un’interfaccia funzionale e necessario conosce-

re a fondo gli attributi dell’oggetto XMLHttpRequest, in quanto essi com-

prendono sia i dati inerenti alla richiesta che i controlli relativi allo stato

dell’interazione. Essi sono cosı composti:

• onreadystatechange: gestore dell’evento lanciato ad ogni cambiamento

di stato della richiesta;

68


• readyState: indica lo stato corrente dell’istanza di XMLHttpRequest;

• responseText : costituisce la risposta del server in formato testuale;

• status : indica il codice HTTP restituito dal server ;

Figura 4.3: Il funzionamento di XMLHttpRequest

L’attributo readyState e particolarmente importante in quanto al variare

del valore assunto l’applicazione si comporta in modo diverso:

• Stato 0: richiesta non inizializzata;

• Stato 1: richiesta inizializzata;

• Stato 2: richiesta inviata;

• Stato 3: richiesta in ricezione;

• Stato 4: richiesta terminata;

In Figura 4.3 e mostrato il diagramma degli stati riferito alla richiesta

XMLHTTP.

69


4.3.3 Streaming dei dati

Grazie all’utilizzo della tecnologia AJAX ed in particolare dell’oggetto XM-

LHttpRequest e possibile ottenere uno stream di dati dalla telecamera, costi-

tuito da pacchetti informativi opportunamente delimitati. Ognuno di questi

pacchetti contiene al suo interno un blocco di feature, ovvero una lista di cop-

pie di coordinate nel caso in cui l’utente intenda rilevare gli angoli della scena,

una lista di intensita di pixel se intende rilevare i contorni, una combinazione

delle precedenti se l’utente desidera visualizzarli contemporaneamente.

Sono state messe a punto due diverse tecniche per realizzare lo streaming

che fanno parte di due filosofie di interazione client-server completamente

diverse:

• Client Polling;

• Server Push;

Una volta ottenuti i pacchetti di feature e stato possibile interpretarli e

rappresentarli sulla pagina Web in tempo reale.

Client Polling

Questa tecnica e stata piuttosto facile da implementare vista la sua natura,

che si basa sulla richiesta dei dati effettuata in un dato intervallo di tempo

periodico al server. Dopo che l’utente decide il tipo di algoritmo di rile-

vamento viene creato un oggetto XMLHttpRequest, una connessione viene

aperta con il server, i dati delle caratteristiche immagine vengono prelevati

dai buffer di memoria e inviati dal gestore di rete del server. La camera

in questo caso chiude subito la connessione, quindi termina l’esecuzione del

programma CGI. Dall’altra parte, il client ottiene i dati, li interpreta e li ela-

bora per la rappresentazione e infine distrugge l’oggetto XMLHttpRequest.

Al termine di tutta questa procedura invia una nuova richiesta esattamente

come prima e si ripete finche l’utente chiude l’applicazione. La Figura 4.4

mostra il funzionamento della tecnica.

Ci sono due possibili implementazioni di questa tecnica, ma entrambe

hanno pesanti svantaggi. La prima, quella appena descritta che prevede la

70


Figura 4.4: Client Polling

creazione e la distruzione di oggetti XMLHttpRequest ogni intervallo di tem-

po prefissato, ha il grosso svantaggio di effettuare tante richieste al secondo

provocando un deterioramento delle risorse, sia per quanto riguarda la came-

ra che il browser stesso. Inoltre il fatto di dovere instaurare una connessione

ad ogni richiesta rende necessario un intervallo di tempo perche le due parti

si mettano in comunicazione, aumentando cosı il ritardo di arrivo del pac-

chetto. Il risultato e pessimo, il browser riceve meno pacchetti di quanti ne

riesce a generare la camera a causa della lag ed entrambi i sistemi sono sotto

costante stress computazionale a causa delle continue richieste. La seconda

implementazione e migliore dal punto di vista di utilizzo delle risorse, ma

invia ancora meno pacchetti della precedente. L’idea e quella di effettuare

una richiesta ogni volta che un pacchetto viene completamente ricevuto. In

questo modo vengono fatte meno richieste, ma i pacchetti arrivati saranno

pochi e il sistema sara molto dipendente dal ritardo di trasmissione.

Server Push

Questa tecnica e un po’ piu complessa della precedente, anche perche e stato

necessario modificare il funzionamento server adattandolo allo scopo (pa-

ragrafo 4.2.4). L’idea si basa sul mantenere aperta un’unica connessione

tra le due parti, eliminando il ritardo di arrivo dei pacchetti e rendendo il

trasferimento dei dati molto piu leggero. Per realizzare la richiesta e stata

utilizzata una caratteristica di XMLHttpRequest che ha permesso l’elabo-

71


razione dei dati per ogni pacchetto mandato dal server in tempo reale. Il

funzionamento generale di questo metodo e mostrato in Figura 4.5.

Figura 4.5: Server Push

L’attributo onreadystatechange viene creato in modo che contenga al suo

interno la funzione che elabora la risposta dal server. Quindi ogni volta che

l’attributo readyState varia, questa funzione viene eseguita. Per fare in mo-

do di avere una connessione permanente si sfrutta lo stato 3 dell’attributo

readyState. Il motivo risiede nel fatto che la camera non chiude la finestra

di connessione finche l’utente stesso non termina l’applicazione (o esce dalla

pagina della visualizzazione), quindi fino a quando vengono elaborate imma-

gini e inviati pacchetti contenenti le stringhe di feature, il readyState non

potra mai assumere valore 4, ovvero la richiesta non potra essere considera-

ta terminata. Invece durante lo stato 3, ovvero quando si stanno ricevendo

progressivamente i pacchetti e la connessione quindi e ancora attiva, si puo

leggere lo stream di dati ed interpretarli per la visualizzazione. I caratteri ine-

renti le feature verranno salvati sequenzialmente nell’attributo responseText,

con le opportune separazioni interne ed esterne. Bastera scorrere l’array di

caratteri ricevuto mediante un indice ed isolare le parti di competenza per

preparare i dati alla rappresentazione. Quando l’utente chiude l’applicazio-

ne, l’attributo readyState si stabilisce sul valore 4 e la connessione termina

normalmente.

Questa soluzione e di gran lunga migliore rispetto al Client Polling in

quanto il numero di pacchetti informativi inviati e pari alla quantita di im-

magini che la camera riesce ad elaborare, riferendosi ovviamente all’unita

72


di tempo. Il ritardo di connessione e presente solo all’inizio, in quanto le

variabili per il collegamento vengono allocate una sola volta, quindi si ha

la garanzia che i pacchetti arrivino ordinati senza ritardo gli uni dagli altri.

Infine l’altro grande vantaggio nell’utilizzo di questa tecnica riguarda l’uti-

lizzo delle risorse dei sistemi coinvolti, in particolare il browser, che vengono

alleggeriti dei carichi computazionali dovuti alle continue connessioni.

4.3.4 Interfaccia grafica

Il sistema di rappresentazione dei dati si basa sul JavaScript e ovviamente su

HTML. Non potendo andare a modificare direttamente lo stream di immagi-

ni ottenuto con le API della camera, e stato necessario trovare una soluzione

alternativa basandosi appunto sulle richieste XMLHTTP. D’altra parte per

garantire all’utente la possibilita di utilizzo dell’applicazione in modo dina-

mico, interattivo e semplice e stata creata un’interfaccia grafica per mezzo

degli oggetti HTML in modo da trattare gli algoritmi secondo i parametri

desiderati in tempo reale.

Come precedentemente descritto, e possibile usare l’applicazione secon-

do tre modalita che si differenziano tra loro dal tipo di algoritmo utilizzato

(FAST, Sobel o entrambi). A tale scopo sono state create tre pagine Web dif-

ferenti, una per ogni modalita, in modo da disegnare l’interfaccia piu consona

allo scopo.

Rappresentazione corner

Quando l’utente intende rilevare i corner della scena, quindi utilizzare l’al-

goritmo FAST, si utilizza un tipo di rappresentazione che interagisce con le

API fornite da Axis. Infatti l’idea e stata quella di sovrapporre un canvas

HTML ad uno stream video ottenuto mediante le API, entrambi di dimen-

sione 480×360. Canvas e una estensione dell’HTML standard che permette

il rendering dinamico di immagini bitmap gestibili attraverso un linguaggio

di scripting, JavaScript nel caso specifico. La rappresentazione dei corner

avviene semplicemente disegnando sul canvas, quindi colorando ogni pixel

corrispondente alle coordinate ricevute mediante la richiesta XMLHTTP,

73


come si puo vedere in Figura 4.6. L’effetto ottenuto e lo stesso di come se

avessimo modificato direttamente le immagini dello stream video delle API.

Figura 4.6: Rappresentazione dei corner

L’interpretazione dei pacchetti avviene in modo molto semplice avendo

definito le regole di separazione dei contenuti, basta trovare i caratteri speciali

e convertire le stringhe di caratteri che rappresentano le coordinate in interi.

Questi numeri vengono usati per disegnare i corner sul canvas.

Poiche il disegno delle feature avviene alla ricezione di ogni pacchetto,

sara necessario cancellare i risultati della precedente elaborazione sul canvas

prima di andare a disegnare la nuova lista di corner, altrimenti si crea una

situazione che non corrisponde alla realta in quanto feature appartenenti alla

scena verrebbero a coesistere con le altre del frame successivo. Il modo piu

semplice per ovviare a questo e quello di utilizzare una funzione specifica che

consiste semplicemente di rendere ogni pixel del canvas “trasparente”.

74


Rappresentazione edge

Nel caso in cui si intenda visualizzare l’output dell’operatore di Sobel, e

quindi anche le relative quantizzazioni dell’immagine, si dovra agire in mo-

do differente. Non e possibile appoggiarsi ad uno stream video fornito dalle

API, infatti l’immagine elaborata della scena viene mandata al client inte-

ramente, specificando ogni singolo valore di intensita dei pixel. Conoscendo

la risoluzione dell’acquisizione dell’immagine e sapendo che i valori dei pi-

xel elaborati vengono mandati sequenzialmente, si ricostruisce l’immagine

disegnando ogni punto sul canvas col valore intero interpretato nella richie-

sta XMLHTTP. Poiche ogni pixel e rappresentato in scala di grigi, bisogna

costruire la struttura delegata al disegno su canvas in modo appropriato. In-

fatti la modifica del colore di un pixel appartenente al canvas viene eseguita

mediante una funzione specifica che richiede i valori di rosso, verde e blu del

punto. La soluzione e stata banalmente quella di prendere il valore di grigio

della richiesta e assegnarlo ad tutti e tre i canali di colore necessari. In Figura

4.7 e mostrata la rappresentazione degli edge.

(a) Sobel (b) Thresholding

Figura 4.7: Rappresentazione degli edge

Rispetto alla rappresentazione dei corner si ha un notevole peggioramen-

to della performance, infatti nonostante il corpo della risposta del server

contenga tanti pacchetti quanti vengono generati dall’elaborazione della ca-

mera, il motore JavaScript non riesce a disegnare i frame sufficientemente

75


veloce. Questo e dovuto al fatto che l’accesso ai singoli valori di un array in

JavaScript e molto lento.

Rappresentazione cluster

L’algoritmo k-means viene eseguito sulla camera elaborando i corner rilevati

mediante l’algoritmo FAST. I cluster vengono quindi disegnati, a discrezione

dell’utente, nello stesso canvas dove risiedono i corner. La camera non calcola

i confini dei cluster ne assegna agli angoli rilevati segni di appartenenza

ad un settore. Vengono inviate esclusivamente le coordinate dei centroidi

e il client stesso disegna il diagramma di Voronoi relativo in tempo reale.

Questa scelta e stata dettata dal fatto che per calcolare il diagramma sarebbe

stato necessario fare calcoli in virgola mobile, cosa che la camera non puo

fare. L’alternativa sarebbe stata quella di usare l’apposita libreria messa a

disposizione da Axis per poter approssimare calcoli di questo tipo ma al costo

di un pesante deterioramento delle prestazioni.

La responsabilita della rappresentazione del diagramma di Voronoi la

prende quindi il client, grazie all’utilizzo di JavaScript. E stata utilizzata

a tale scopo una libreria open-source di Raimond Hill [4] per il calcolo dei

confini dei cluster. Per quanto riguarda il rendering delle linee di separa-

zione cosı ottenute sono state fatte modifiche ed adattamenti in modo che

il diagramma venisse disegnato sul canvas delle feature e avesse grandezza

esattamente uguale alla dimensione del canvas stesso.

Stima della velocita di rappresentazione

Per valutare l’effettiva frequenza di pacchetti al secondo che il browser riesce

a rappresentare e stato utilizzato un sistema di misura simile a quello per

la stima del frame-rate di un video. Per eseguire la stima si inizializza la

misura che chiamiamo FT a 0. Quindi supponendo di avere ricevuto il k-

esimo pacchetto, la stima del tempo medio di arrivo tra un frame e l’altro si

ottiene mediante l’equazione:

FTk = FTk−1 +(tk − tk−1)− FTk−1

fs(4.1)

76


dove tk e un valore intero che rappresenta l’istante di tempo dell’arrivo del

pacchetto e fs e un valore stabilito a priori, usato per stabilizzare la stima in

modo che il suo valore non oscilli troppo bruscamente attorno ad una soglia

dopo l’arrivo di ogni pacchetto. Si osservi che in JavaScript l’istante di tempo

di arrivo puo essere calcolato con un’apposita funzione che restituisce la data

attuale, che comprende anche i millesimi di secondo. In ogni caso vale sempre

la proprieta tk > tk−1.

Il calcolo effettivo della frequenza di disegno delle feature, definita come

CDPS (Corner Drawn Per Second), sempre supponendo di disegnare la

k-esima lista di corner, sara dato da:

CDPSk =1

FTk

(4.2)

assumendo che FTk sia misurato in secondi. Questo valore e il numero to-

tale di corner contenuti all’interno del pacchetto ricevuto vengono disegnati

anch’essi sul canvas e aggiornati in tempo reale assieme alle feature.

Si puo fare una stima delle prestazioni di rappresentazione degli edge

usando le stesse formule relative al calcolo dei corner, in tal caso pero viene

definita come EDPS (Edge Drawn Per Second).

Controlli manuali

Una delle peculiarita piu importanti dell’applicazione e la possibilita di avere

il controllo sui parametri di qualsiasi algoritmo utilizzato in tempo reale.

L’utente quindi puo gestire semplicemente il funzionamento dell’applicazione

utilizzando dei controlli integrati nell’interfaccia grafica della pagina Web,

senza necessita di riavviare l’applicazione ne di ricaricare la pagina stessa.

Gli input vengono gestiti da oggetti HTML, come slider, bottoni e menu a

cascata, in base al parametro da regolare. Ad esempio, per variare la soglia

del rilevatore di angoli e stato utilizzato uno slider mentre per attivare la

soppressione dei non massimi e stato scelto un semplice bottone.

Gli oggetti HTML ovviamente non possono interagire col server da soli.

Ancora una volta JavaScript risolve il problema integrandosi con tali oggetti.

A seconda dell’evento legato all’oggetto HTML esiste una specifica funzione

77


che gestisce la situazione per comunicare con la camera. Il passo successivo

e quello di fare una richiesta con l’oggetto XMLHttpRequest alla CGI di ag-

giornamento del server che provvedera alla variazione del parametro secondo

il valore scelto dall’utente.

4.4 Metodi di trasmissione

La trasmissione di dati tra il server e il client e stata ulteriormente migliorata

focalizzando l’attenzione sull’utilizzo delle risorse a disposizione. Infatti sono

stati usati alcuni approcci ingegneristici per rendere la comunicazione tra le

due parti piu leggera e per contenere la spesa di risorse del browser.

Il primo studio fatto riguarda le situazioni in cui la banda a disposi-

zione per la connessione non e molto ampia, quindi quando si necessita di

diminuire la quantita dei bit trasmessi pero mantenendo la stessa qualita di

informazione. La codifica dei dati in uscita del server e utile per i contesti in

cui si dispone di scarse risorse e inoltre comporta un altro risultato inatteso

riguardo il tempo impiegato nel rappresentare le feature.

Il secondo studio svolto riguarda invece l’utilizzo della memoria del bro-

wser e di conseguenza l’efficienza del motore JavaScript. L’utilizzo di una

singola connessione per il trasferimento dati comporta il fatto che il buffer

contenente la stringa delle feature venga continuamente riempito. Poiche

la dimensione del buffer e limitata dal browser, dopo un certo intervallo di

tempo giunge al limite massimo e quindi causa l’interruzione della rappre-

sentazione delle feature. Sfruttando il fatto che uno stream di dati e di fatto

un messaggio formato di piu parti si ovvia a questo problema con un tipo di

contenuto che permette di contenere il corpo della risposta entro dimensioni

molto limitate.

4.4.1 Codifica dei dati

I dati inviati dalla camera verso l’utente inizialmente non erano codificati in

modo da risparmiare sulla banda della trasmissione dati. La situazione che

si presentava era condizionata dal fatto che i valori delle feature non erano

78


rappresentati come interi ma come caratteri, uno per ogni cifra e inoltre si

aggiungevano i caratteri di separazione. Nel caso peggiore, per inviare una

coppia di coordinate riferite ad un corner, erano necessari tre caratteri per

il numero dell’ascissa, tre per l’ordinata e in piu altri due caratteri speciali

per separare le due coordinate sia tra di loro che rispetto a quelle degli altri

angoli.

Il motivo della scelta di codifica testuale dei dati e legato al fatto che il

browser possa comunicare con la camera senza la perdita di alcuna informa-

zioni.

In questo caso tuttavia non c’era la disponibilita di un compressore JPEG

e i dati inviati avevano una grandezza eccessiva che si desiderava tentare di

ridurre. Vista l’impossibilita di trattare i dati come numeri interi, si e scelto

di utilizzare codifiche alternative che si adattavano al tipo di problema.

Il progetto si sviluppa in modo che i caratteri in uscita vengano codificati

dalla camera e decodificati dal client prima della loro rappresentazione, uti-

lizzando pero un linguaggio diverso, ovvero JavaScript. La codifica delta e la

codifica Run-length sono le compressioni dati scelte. Per motivi di efficienza

non e possibile risolvere questo problema facendo uso di algoritmi comples-

si, e quindi piu performanti dal punto di vista della compressione. Le due

codifiche usate infatti sono metodi molto banali e non sempre sono funzio-

nali, tuttavia la loro velocita di esecuzione non compromette la performance

dell’applicazione. Inoltre la scelta di questi metodi di compressione molto

semplici e dettata dal fatto che la codifica e la decodifica delle informazioni

viene svolta mediante due linguaggi diversi, C++ e JavaScript.

Codifica delta

La codifica delta e un modo per immagazzinare o trasmettere dati usando le

differenze tra i dati sequenziali piuttosto che sull’insieme completo dei dati,

attualmente utilizzata anche dai Web server per mandare gli aggiornamenti

delle pagine Web in forma di differenza tra le versioni [40]. A volte la codifica

delta e chiamata compressione delta, in particolare quando e richiesta la

storia dei cambiamenti (per esempio nei progetti software). Le differenze

79


sono registrate in valori discreti chiamati delta o diff. Poiche i cambiamenti

sono di solito piccoli, la codifica delta riduce notevolmente la ridondanza

dei dati. Insiemi di uniche delta sono sostanzialmente piu efficienti nella

riduzione di spazio che i loro equivalenti non codificati.

La natura dei dati da codificare influenza l’efficacia di un particolare

algoritmo di compressione. La compressione delta offre il suo meglio quando

i dati hanno variazioni piccole o costanti. Per un insieme non ordinato di

dati, questo metodo potrebbe offrire una compressione piccola o nulla.

Questo tipo di codifica e stato particolarmente performante nel caso di

invio di corner, riducendo notevolmente la grandezza del pacchetto trasmes-

so. Il motivo sta nel fatto che l’algoritmo FAST rileva gli angoli in sequenza,

partendo dalla prima riga e scendendo lungo l’altezza dell’immagine fino ad

elaborare l’ultima riga. Alla luce di queste considerazioni si osserva imme-

diatamente che nel caso in cui due angoli si trovino sulla stessa riga dell’im-

magine, l’ordinata del secondo angolo viene sicuramente codificata col valore

nullo e quindi sara necessario solo un carattere invece dei tre potenziali. Al-

lo stesso modo anche l’ascissa ha buone probabilita di essere codificata con

meno di tre caratteri in quanto esiste una buona probabilita che due angoli

consecutivi possano trovarsi a meno di 10 (quindi un carattere per la codifica)

o 100 pixel (due caratteri) di distanza su una stessa riga.

Nel caso invece dell’invio di edge invece questa tecnica non ha prodotto

risultati eccellenti, tuttavia per la rappresentazione delle immagini con tanti

livelli di grigio ha comunque fornito una piccola riduzione del traffico dati

rispetto al formato non compresso.

Codifica Run-length

La codifica Run-length cerca nei dati da comprimere una serie di valori uguali

e la sostituisce con un solo elemento, quindi un carattere speciale e infine il

numero di volte che esso va ripetuto. Per esempio supponiamo di avere

un’immagine dove la prima riga e formata da cento pixel neri, la codifica

memorizzera il primo pixel nero poi mettera il carattere speciale e in seguito

memorizzera il numero 100. Cosı invece di occupare cento locazioni la prima

80


riga ne occupera solo tre. Il carattere speciale e definito diversamente da ogni

implementazione dell’algoritmo e serve a distinguere un elemento normale da

uno compresso. L’algoritmo funziona bene in presenza di immagini con pochi

colori molto uniformi, ovvero in serie di dati che abbiano molte ripetizioni al

loro interno.

Questo tipo di codifica e stato impiegato per le immagini trattate con

l’algoritmo di Sobel e i risultati ottenuti sono stati differenti a seconda della

modalita di rappresentazione desiderata. Nel caso dell’immagine non quan-

tizzata, non solo la dimensione dell’informazione inviata non diminuiva ma

addirittura aumentava considerevolmente. Tuttavia quantizzando l’immagi-

ne, quindi scegliendo rappresentazioni con sempre meno quantita di grigi,

l’efficienza della codifica aumentava in modo sorprendente, fino ad arrivare

ad un risultato eccellente nel caso della binarizzazione. Il fenomeno si spie-

ga semplicemente considerando il fatto che in un’immagine non quantizzata,

quindi con 256 livelli di grigio, la probabilita di trovare due pixel consecutivi

con la stessa intensita e molto bassa, sia per la natura della scena ripresa

che per il rumore presente. Al contrario, diminuendo il numero di grigi usati

per la rappresentazione, la probabilita aumenta in modo sostanziale, gli ef-

fetti dovuti al rumore contribuiscono sempre di meno e la quantita di dati

trasmessi diminuisce di conseguenza.

Il caso limite della binarizzazione e particolarmente adatto a questo tipo

di codifica, in quanto si puo codificare intere righe di immagine con pochis-

simi caratteri. Un effetto molto significativo in questo contesto riguarda

la rappresentazione stessa. La codifica Run-length non solo abbatte i costi

dimensionali di trasmissione, ma consente a JavaScript di poter disegnare

l’immagine ricevuta in un tempo minore. Infatti poiche ogni coppia di valori

presenti nel pacchetto indica il valore dell’intensita e il numero di occorrenze

consecutive, e possibile disegnare con JavaScript interi rettangoli monocro-

matici di pixel, a seconda del colore, senza accedere ad ogni singolo punto

appartenente al canvas. L’aumento di velocita in questo caso e rilevante nel

caso in cui i pixel da disegnare siano un numero sufficientemente elevato.

81


4.4.2 Multipart Mixed-Replace

Lo streaming delle feature dalla camera verso il client inizialmente veniva

effettuato riempendo un buffer di caratteri all’interno dell’oggetto XMLHtt-

pRequest il quale all’arrivo di ogni pacchetto accodava la nuova stringa di

caratteri all’ultima posizione occupata, determinando quindi una crescita co-

stante della dimensione del buffer. Col passare del tempo il processo veniva

ripetetuto ciclicamente e si giungeva ad una situazione limite in cui il buf-

fer raggiungeva la grandezza massima consentita e il motore JavaScript si

arrestava fin quando non veniva ricaricata la pagina stessa.

La soluzione utilizzata per questo grave problema e stata quella di con-

siderare lo streaming come l’invio di un messaggio composto da piu parti,

ovvero in questo caso da piu blocchi di feature. A tal proposito la standard

internet MIME Multipurpose Internet Mail Extensions permette di specifica-

re e descrivere il formato dei messaggi [48]. Un messaggio MIME Multipart

contiene un confine che viene posto tra tutte le coppie di pacchetti che com-

pongono l’intero messaggio. Ogni parte ha un proprio header che ne specifica

il tipo di contenuto, nel nostro caso semplice testo, e un corpo.

La potenzialita di MIME permette di utilizzare estensioni dello standard

stesso che specificandola natura del messaggio e in che modo le parti che lo

compongono sono correlate. Una di queste estensioni e stata ritenuta partico-

larmente adatta allo scopo: Mixed-Replace. Il tipo di contenuto multipart/x-

mixed-replace e stato sviluppato come parte della tecnologia server push e

dello streaming HTTP. Ogni parte che compone il messaggio mixed-replace

ha una propria semantica, tuttavia ognuna di esse invalida la precedente,

prendendone il posto sul buffer che memorizza il messaggio, nel momento

in cui essa viene ricevuta completamente. Questa e la stessa infrastruttura

utilizzata dagli stream M-JPEG che quindi permette il trasferimento di dati

nel tempo senza problemi relativi alla memorizzazione sul client.

82

Capitolo 5

Risultati Sperimentali

La stima della velocita di esecuzione e uno studio molto importante per

questa tipologia di programmi, in quanto l’estrazione di feature di basso

livello rappresenta la fase iniziale di analisi di algoritmi molto piu complessi

e di conseguenza limitando il costo computazionale nel rilevamento dei punti

di interesse, si migliora la velocita di esecuzione anche delle operazioni piu

sofisticate.

Per misurare le prestazioni dell’applicazione sviluppata, sono stati ese-

guiti gli algoritmi di rilevamento feature e sono stati calcolati i loro tempi di

esecuzione su un piccolo insieme di scene che di differenziano in base al nume-

ro di corner rilevati a parita di soglia e di risoluzione di acquisizione. Le scene

che vengono prese di riferimento sono quelle mostrate nelle figure 5.1a, 5.1b e

5.1c. Ognuna di queste scene avra un numero di corner caratteristico che di-

pendera sia dalla risoluzione che dalla soglia impostata sull’algoritmo FAST.

Un’immagine ad alto dettaglio avra verosimilmente un numero piu elevato di

angoli rispetto alle scene meno dettagliate. Una stima del numero al variare

della soglia e della risoluzione puo essere vista in Figura 5.2. La quantita di

corner diminuisce notevolmente all’aumentare della soglia in quanto il crite-

rio Segment Test 2.1.2 assegna sempre piu risultati negativi. Idealmente se

si impostasse la soglia al valore massimo, ovvero 255, non verrebbe rilevato

alcun angolo indipendentemente dalla risoluzione di acquisizione o dal livello

di dettaglio della scena. Al contrario si nota che al diminuire della soglia

83

CAPITOLO 5. RISULTATI SPERIMENTALI

(a) Scena ad alto contenuto di dettagli

(b) Scena a medio contenuto di dettagli

(c) Scena a basso contenuto di dettagli

Figura 5.1: Le scene utilizzate per misurare la performance dell’applicazione

84


il numero di angoli rilevati cresce in modo quadratico, il criterio Segment

Test assegna sempre piu risultati positivi. Anche in questo caso, impostando

idealmente la soglia dell’algoritmo FAST al minimo valore possibile, ovvero

0, si ottiene un numero di corner pari esattamente alla dimensione dell’im-

magine stessa, quindi un numero dipendente dalla risoluzione di acquisizione

ma indipendente dal livello di dettaglio della scena.

0

2000

4000

6000

8000

10000

12000

10 20 30 40 50 60

Cor

ner

Threshold

160x120240x180360x240480x360640x480

Figura 5.2: Quantita di corner rilevati in una scena molto dettagliata

5.1 Valutazione della performance

Le prestazioni dell’applicazione vengono misurate in base al numero di frame

al secondo che la camera riesce ad elaborare, che definiamo FPPS (Frame

Processed Per Second), da non confondere con la quantita di frame al secondo

che la telecamera acquisisce, che definiamo FCPS (Frame Captured Per

Second). Questo numero rappresenta il limite superiore per la stima della

performance, perche sicuramente l’applicazione non puo elaborare piu frame

85


di quanti ne vengano acquisiti, pertanto vale sempre la relazione:

FCPS ≥ FPPS (5.1)

Il numero di frame acquisiti in un secondo inoltre non puo superare la soglia

di 30, in quanto e vincolato dalle impostazioni di fabbrica della telecamera

stessa.

Per calcolare il numero di frame elaborati non e possibile utilizzare un

apposito profiler, in quanto il firmware presente sulla camera non lo prevede.

La soluzione e quindi quella di creare una struttura adatta alla misurazione

dei tempi mediante l’utilizzo della libreria standard <time.h>. In questo

modo tuttavia la valutazione del tempo effettivo di esecuzione dei singoli

algoritmi misurato in millisecondi e poco accurata per le scene troppo detta-

gliate, quindi in generale si preferisce utilizzare la misura di performance in

termini di frame elaborati al secondo, ovvero considerando anche i tempi di

acquisizione e memorizzazione delle immagini. Ad ogni modo e interessante

valutare i tempi di esecuzione di tutti gli algoritmi su scene non particolar-

mente dettagliate, poiche in questi casi i tempi rilevati variano con meno

intensita e si puo eseguire una stima piu accurata.

Per quanto riguarda il trasferimento di dati si svolge uno studio sulla

quantita media di informazione trasferita per ogni tipologia di codifica uti-

lizzata. Le misurazioni vengono effettuate al variare del numero di livelli di

grigio desiderato per la rappresentazione dell’immagine.

5.2 Velocita di esecuzione

La stima della performance degli algoritmi viene fatta impostando il valore

massimo del tasso di acquisizione di frame da parte della telecamera, ovvero

30 FCPS. Esiste un’importante considerazione da fare riguardo la perfor-

mance. La necessita di rappresentazione dei dati implica l’utilizzo di alcune

strutture e funzioni che rallentano pesantemente l’esecuzione degli algoritmi.

Come e stato discusso nel capitolo 4, non e possibile modificare direttamente

lo stream di immagini ottenuto mediante le API e quindi si deve inviare i

dati riguardanti le feature su uno stream parallelo a quelle delle immagini,

86


delegando il compito di riunire i due flussi al client. D’altra parte lo stream

delle feature deve essere convertito in formato testuale prima dell’invio ver-

so il browser, tuttavia in questo modo si condiziona l’effettiva performance

dell’applicazione. A tal proposito viene fatta uno studio parallelo sulla ve-

locita di esecuzione dei vari algoritmi, considerando prima il caso senza la

rappresentazione dei dati e poi il caso con la rappresentazione.

5.2.1 Stima di analisi senza rappresentazione

Per calcolare l’effettiva velocita dell’applicazione senza la penalizzazione do-

vuta alla trasmissione, vengono eseguiti gli algoritmi per estrarre le feature

ma non vengono codificati come caratteri e non vengono inviati al client. Vie-

ne preso il tempo che intercorre tra l’elaborazione di due frame consecutivi e

fatta una stima del tutto simile al calcolo della velocita di rappresentazione

delle caratteristiche del paragrafo 4.3.4. L’analisi di performance si concen-

tra sulla stima di FPPS per l’algoritmo FAST al variare della soglia, della

risoluzione e del tipo di scena ripresa, per l’algoritmo Sobel al variare della

risoluzione dell’immagine e per l’algoritmo k-means al variare del numero di

cluster e della soglia riferita all’algoritmo FAST. Per valutare quanto influi-

scono i vari algoritmi sull’esecuzione dell’applicazione si faccia riferimento

alla Figura 5.3. In questo caso la risoluzione viene fissata a 320×240 e viene

fatta variare la soglia dell’algoritmo FAST. Da una prima analisi si nota che

in generale l’algoritmo FAST e l’algoritmo Sobel hanno quasi lo stesso tempo

di esecuzione, anche se il primo aumenta al diminuire della soglia. Il motivo

risiede nel fatto che diminuendo tale valore l’algoritmo di rilevamento corner

effettua il criterio Segment Test con probabilita maggiore e di conseguenza

si richiede piu tempo per terminare. D’altra parte l’operatore di Sobel e

indipendente dalla scena ripresa o dal valore della soglia, quindi il tempo di

esecuzione rimane sempre uguale.

La soppressione dei non massimi per l’algoritmo FAST invece assume un

comportamento differente. Se la soglia viene diminuita il numero di corner

aumenta in modo quadratico, e quindi l’operazione di eliminazione deve es-

sere eseguita su buffer sempre piu grandi. Il tempo di esecuzione pertanto

87


0

10

20

30

40

50

60

70

80

90

100

60 50 40 30 20 10

Exe

cutio

n T

ime

(ms)

Threshold

FASTSuppressionSobelK-means

Figura 5.3: Tempi di esecuzione in una scena di medio dettaglio

segue l’andamento quadratico del numero di angoli. Allo stesso modo anche

l’algoritmo k-means e strettamente legato al numero di corner rilevati, ma

avra un aumento piu consistente del tempo di esecuzione poiche dipende an-

che da altri fattori, quali il numero di partizioni e il numero di iterazioni per

la convergenza.

Stima dell’algoritmo FAST

Il tempo di esecuzione dell’algoritmo FAST dipende strettamente dalla scena

inquadrata poiche ad un’immagine con tanti dettagli corrispondono tanti

corner, quindi viene speso piu tempo per l’elaborazione rispetto ad una scena

poco dettagliata. In Figura 5.4a sono mostrati i valori di FPPS al variare

del valore della soglia confrontati tra le scene di riferimento utilizzate.

La risoluzione di acquisizione dei frame influisce notevolmente nel tempo

di esecuzione di FAST come mostrato in Figura 5.4b. Il fatto piu rilevan-

te e il forte calo di performance dalla risoluzione di 320×240 pixel a quella

di 480×360 pixel. Il motivo di questo deterioramento di performance e do-

88


16

18

20

22

24

26

28

30

10 20 30 40 50 60

FF

PS

Threshold

HighMidLow

(a)

0

5

10

15

20

25

30

10 20 30 40 50 60

FF

PS

Threshold

240x180320x240480x360

(b)

Figura 5.4: Performance dell’algoritmo FAST

89


vuto al fatto che all’aumento dei pixel da elaborare coincide un incremento

del tempo necessario alla telecamera per l’acquisizione dei frame e per la

memorizzazione dei dati.

Stima dell’algoritmo Sobel

Il tempo di esecuzione per l’estrazione degli edge mediante l’operatore di

Sobel non dipende dalla scena ripresa ne da altri parametri. L’unica cosa

che influisce e la quantita di pixel appartenenti all’immagine, ovvero alla

risoluzione. Come mostrato in Figura 5.5, anche in questo caso il calo di

performance piu netto si ha tra la risoluzione di 320×240 pixel e 480×360

pixel.

0

5

10

15

20

25

30

35

160x120 240x180 360x240 480x360 640x480

FP

PS

Resolution

Figura 5.5: Performance dell’algoritmo Sobel

Stima dell’algoritmo k-means

L’analisi dell’algoritmo k-means e piuttosto interessante perche permette di

valutare la performance secondo diversi punti di vista. Infatti questo algo-

90


ritmo dipende sia dal numero di feature rilevato, sia dal numero di iterazioni

prima della convergenza, sia dal numero di cluster impostato. Facendo varia-

re il numero di settori k, si ottiene il risultato mostrato in Figura 5.6a. Il calo

di performance all’aumentare dei cluster varia in modo pressoche lineare.

Fissando invece il numero di partizioni e facendo variare la soglia del

rilevamento di corner si nota come questo algoritmo sia particolarmente

performante nel caso in cui l’insieme di feature sia piuttosto limitato, co-

me mostrato in Figura 5.6b. Ovviamente per la stima del k-means bisogna

prendere in considerazione anche il tempo di esecuzione dell’algoritmo FAST

che fornisce i dati necessari al partizionamento.

5.2.2 Stima di analisi con rappresentazione

La rappresentazione delle feature sul client implica che i dati riguardanti le

feature prodotte dagli estrattori vengano codificati in forma testuale, causan-

do un netto calo della performance di quasi tutti gli algoritmi. In questo caso

conviene trattare la stima della velocita di esecuzione in termini di differenza

di performance tra le due modalita, ovvero si calcolano le differenze di FPPS

tra il caso senza rappresentazione dei dati e il caso con la rappresentazione.

A tal scopo si definisce la misura che indica la differenza di frame al secondo

elaborati come:

DFPPS = FPPSnr − FPPSr (5.2)

dove i pedici r e nr indicano rispettivamente la presenza e l’assenza della

rappresentazione dei dati. Nel caso dell’algoritmo FAST questo valore e

abbastanza importante, ma a bassissime risoluzioni non e molto rilevante in

quanto i corner rilevati sono pochi. In Figura 5.7a si nota come anche ad

alte risoluzioni questa differenza venga attenuata.

Ancora piu significativa e la differenza nell’esecuzione dell’algoritmo So-

bel, soprattutto a basse risoluzioni come si puo vedere in Figura 5.7b. Il

motivo di questo fenomeno risiede nel fatto che nel caso dell’utilizzo dell’o-

peratore di Sobel si ha la necessita di trasmettere l’intera immagine al client,

quindi ogni singolo valore dei pixel dell’immagine elaborata deve essere codi-

91


8

10

12

14

16

18

20

3 4 5 6 7 8 9 10

FP

PS

K

240x180360x240

(a)

0

5

10

15

20

25

30

10 20 30 40 50 60

FP

PS

Threshold

160x120240x180360x240

(b)

Figura 5.6: Performance dell’algoritmo k-means

92


0

2

4

6

8

10

12

14

16

10 20 30 40 50 60

Diff

eren

ce F

FP

S

Threshold

240x180320x240480x360

(a) Algoritmo FAST

0

5

10

15

20

25

30

160x120 240x180 360x240 480x360 640x480

Diff

eren

ce F

PP

S

Threshold

(b) Algoritmo Sobel

Figura 5.7: Differenza di performance

93


ficato in forma testuale e di conseguenza il tempo di esecuzione totale viene

drasticamente aumentato.

Per quanto riguarda l’algoritmo k-means non c’e un deterioramento delle

prestazioni, in quanto e necessario il salvataggio e l’invio di pochi centroidi

e quindi il tempo di esecuzione rimane praticamente invariato.

L’ultimo punto su cui e importante focalizzarsi riguarda la soppressione

dei non massimi per l’algoritmo FAST. In condizioni normali, eseguire questo

tipo di operazione comporta una spesa accessoria, in termini di tempo di

esecuzione, oltre la normale esecuzione dell’algoritmo FAST. Tuttavia nel

caso in cui si necessita di una rappresentazione delle feature rilevate, e quindi

dell’invio al client delle informazioni, questo tipo di operazione diminuisce

il tempo di esecuzione dell’algoritmo FAST. Questo risultato puo sembrare

contraddittorio, tuttavia il risultato si spiega banalmente. Se c’e necessita di

rimuovere i non massimi, allora non c’e alcun motivo di codificare le feature

estratte in formato testuale prima della soppressione. Questo procedimento

puo essere normalmente svolto alla fine, quindi eseguito su una quantita di

dati relativamente piu piccola. Di conseguenza il tempo di esecuzione totale

risulta minore rispetto al caso senza soppressione.

5.2.3 Modifica del frame rate di acquisizione

Nella sezione 4.2.2 e stato discusso un metodo molto efficace per aumentare

la performance dell’applicazione. La tecnica si basa sulla possibilita di cam-

biare il tasso di acquisizione di frame da parte della telecamera, quindi di

fatto risparmiando sul tempo totale impiegato per la memorizzazione delle

immagini riprese. Effettuando dei test sull’esecuzione dell’algoritmo FAST si

notano notevoli miglioramenti soprattutto se vengono selezionate risoluzioni

molto alte. Come si osserva dalla Figura 5.8, se viene scelto un opportuno

tasso di acquisizione il guadagno di performance e notevole. Ad esempio, ad

una risoluzione di 320×240 pixel l’esecuzione dell’algoritmo facendo riferi-

mento a questa tecnica comporta fino ad un guadagno di 3 FPPS rispetto

all’esecuzione originale, ovvero quella a 30 FCPS. Nel caso della risoluzione

480×360 pixel si hanno ottimi risultati, infatti nel caso migliore si ha un

94


guadagno di quasi 8 FPPS rispetto all’esecuzione originale. Alla luce dei

0

5

10

15

20

25

0 5 10 15 20 25 30

FP

PS

FCPS

320x240480x360

MAX1MAX2

Figura 5.8: Tempo di esecuzione di FAST al variare del tasso di acquisizione

risultati ottenuti e importante conoscere quali sono le condizioni in cui la

telecamera deve lavorare e calibrare i parametri di acquisizione in modo da

ottenere il valore di FPPS piu vicino possibile al massimo.

La stessa tecnica puo essere applicata per l’esecuzione dell’algoritmo So-

bel, tuttavia non e altrettanto efficace. Esiste un minimo guadagno ma solo

a risoluzioni piuttosto alte, mentre nel resto dei casi questo metodo si rivela

completamente inefficace. D’altra parte esiste un grande vantaggio rispet-

to all’esecuzione dell’algoritmo FAST. Il tempo di esecuzione dell’operatore

di Sobel non dipende dalla scena inquadrata, quindi il valore massimo di

FPPS rilevato facendo variare il numero di FCPS potra essere preso come

riferimento per garantire un’esecuzione piu efficiente dell’algoritmo.

95


5.3 Compressione dei dati

Lo studio della quantita di dati trasmessi e molto importante per una ap-

plicazione che prevede uno scambio continuo di informazioni in un sistema

client-server. Nei casi in cui la banda disponibile della connessione non sia

sufficientemente ampia e necessario configurare l’applicazione in modo da

minimizzare il piu possibile la grandezza dei dati. A tal proposito nel pa-

ragrafo 4.4.1 sono stati presentati alcuni metodi per ridurre la quantita di

informazione trasmessa.

0

10

20

30

40

50

60

70

80

90

2 4 8 16 32 64 128 256

KB

Livelli di grigio

RawRun-Length

Delta

Figura 5.9: Dimensione media delle immagini codificate

Facendo variare il numero di livelli di grigio usati per la rappresentazione

dell’immagine elaborata con l’operatore di Sobel si puo mettere a confron-

to la quantita di dati trasmessa per ogni codifica utilizzata. I test vengono

eseguiti acquisendo immagini di una scena molto dettagliata ad una risolu-

zione di 160×120 pixel e per ogni numero discreto di livelli di grigio viene

calcolato il valore medio della quantita di dati trasmessa utilizzando le varie

codifiche. In Figura 5.9 si puo notare che non esiste una codifica migliore

96


per tutti i livelli di grigio, ma ogni codifica risulta la migliore in un certo

intervallo. La trasmissione di immagini con 16 o piu livelli di grigio e piu

conveniente eseguirla la codifica delta, altrimenti conviene utilizzare la codifi-

ca Run-length che risulta estremamente conveniente per le immagini binarie,

riuscendo a comprimere i dati di oltre il 67% rispetto al formato non com-

presso. Tuttavia al crescere dei livelli di grigio i risultati diventano pessimi,

soprattutto per la rappresentazione a 256 colori che viene trasmessa con una

quantita di dati grande piu del doppio rispetto al formato non compresso.

Questo fenomeno si spiega banalmente considerando la natura della codifica

stessa, infatti nel caso di immagini binarie ci sono lunghe ripetizioni di uno

stesso valore, mentre nel caso di immagini a 256 colori le ripetizioni di valori

all’interno del buffer dei pixel saranno molto improbabili.

La dimensione delle immagini codificate con Run-Length dipende anche

dalla scena ripresa, infatti se e poco dettagliata serviranno molti meno ca-

ratteri per codificare l’immagine. Come si puo vedere in Figura 5.10 in una

scena in cui ci sono meno dettagli la dimensione dell’immagine codificata e

molto minore rispetto ad una piu dettagliata e inoltre al crescere dei livel-

li di grigio segue un andamento quadratico. Questo determina una buona

compressione anche per le immagini codificate con pochi livelli di grigio ri-

spetto in piu alle immagini binarie, ma resta sempre molto inefficace per le

immagini a 256 colori.

97


0

10

20

30

40

50

60

70

80

90

2 4 8 16 32 64 128 256

KB

Livelli di grigio

RL-Hi-txtRL-Low-txt

Figura 5.10: Confronto della codifica Run-length su scene diverse

98

Capitolo 6

Conclusioni e sviluppi futuri

In questo lavoro e stata sviluppata un’applicazione per l’estrazione in tempo

reale di feature di basso livello a bordo di una telecamera Axis. In letteratura

e presente un’ampia gamma di rilevatori di corner e di edge, ma solo pochi

di essi sono adatti ad un sistema con risorse molto limitate, nel caso specifico

una camera di videosorveglianza. I risultati del lavoro svolto sono:

• La creazione e l’implementazione di un rilevatore di corner molto ve-

loce, robusto e portabile.

• L’implementazione di un rilevatore di edge basato sull’operatore di

Sobel.

• L’interpretazione delle feature estratte con un algoritmo di clustering.

• La realizzazione di un sistema client-server per la rappresentazione

delle feature.

• La riduzione del traffico di dati mediante opportune codifiche.

Il rilevatore di corner creato con l’algoritmo Generic FAST e risultato

particolarmente performante in termini di velocita di esecuzione a basse ri-

soluzioni di immagine. Anche dal punto di vista della qualita delle feature i

risultati ottenuti sono stati quelli attesi. Tuttavia le risorse limitate della ca-

mera non hanno permesso una efficiente elaborazione delle immagini ad alta

99

CAPITOLO 6. CONCLUSIONI E SVILUPPI FUTURI

risoluzione, quindi di fatto limitando i possibili utilizzi dei rilevatori creati

ad applicazioni che non richiedono immagini con grandi quantita di pixel.

L’algoritmo k-means e stato utilizzato per dare una possibile interpreta-

zione riguardo gli angoli estratti ed e risultato particolarmente efficiente per

insiemi di dati non troppo grandi. Per quanto riguarda la qualita del parti-

zionamento dell’algoritmo si puo fare diverse considerazioni. Questo metodo

funziona molto bene in caso di insiemi di dati compatti e ben separati tra

di loro. Nel caso dei corner estratti dal rilevatore proposto, vengono utiliz-

zate esclusivamente le coordinate spaziali degli angoli come parametri per

l’esecuzione dell’algoritmo, quindi non c’e garanzia di avere insiemi di da-

ti compatti in modo da avere separazioni nette e anche mediante l’utilizzo

dell’indice di compattezza il risultato non e sempre quello atteso. Tuttavia

e possibile pensare ad un’estensione del metodo utilizzato, includendo nei

parametri dell’algoritmo di partizionamento anche gli edge. Supponendo di

eseguire il metodo di thresholding sull’immagine elaborata dall’operatore di

Sobel con una soglia opportuna, si possono unire i contenuti informativi delle

due tipologie di feature ed eseguire lo stesso algoritmo di partizionamento.

Successivamente stimando il numero di feature per ogni settore ottenuto si

puo avere un’idea generale sulla qualita di informazione all’interno dei va-

ri cluster. Se l’applicazione viene eseguita su una telecamera PTZ in questo

modo e possibile direzionare l’inquadratura in base alle informazioni ottenute

dall’algoritmo k-means.

L’utilizzo dell’algoritmo k-means ha permesso di fare un’ulteriore osser-

vazione. Facendo variare la soglia dell’algoritmo FAST si e potuto notare

che i centroidi si comportavano in maniera diversa. Se si imposta una so-

glia molto alta i corner rilevati sono pochi, quindi le posizioni dei centroidi

variano considerevolmente tra un frame e l’altro e di conseguenza le forme

dei cluster sono molto differerenti. Diminuendo la soglia invece si e osserva-

to che le posizioni dei centroidi tendono ad essere piu stabili, mantenendo

le loro coordinate in un intorno di pixel sempre piu piccolo. Tuttavia se la

soglia viene diminuita eccessivamente, allora l’algoritmo FAST rileva anche

i corner “deboli”, ovvero la rilevazione viene pesantemente influenzata dal

rumore termico presente nelle immagini riprese. L’effetto ottenuto in questo

100


caso e che i centroidi perdono la stabilita e la loro posizione torna a variare

intensamente. L’idea di fondo e che ci sia una correlazione tra la soglia del-

l’algoritmo FAST e la stabilita dei centroidi. A tal proposito si puo pensare

di eseguire uno studio sull’errore medio delle posizioni dei centroidi tra un

frame e il successivo al variare della soglia, e in seguito scegliere in modo

adattivo il valore di soglia che minimizza quell’errore.

Il sistema di interazione tra client e server e pesantemente condizionato

dal fatto che non e possibile modificare lo stream video direttamente a bor-

do della camera, ne e possibile utilizzare il compressore JPEG per inviare

le immagini annotate. Questo comporta due grandi svantaggi, da una par-

te la diminuzione delle prestazioni della telecamera e dall’altra un eccessivo

traffico dati. Pertanto se la societa Axis rendera possibile le operazioni cita-

te si otterranno risultati decisamente migliori per la rappresentazione delle

caratteristiche estratte.

Il lavoro svolto per l’estrazione delle feature di basso livello ha posto le

basi per una serie di possibili sviluppi futuri:

• Tracking - I corner hanno in genere un alto livello di ripetitivita, quin-

di un oggetto in movimento presentera verosimilmente le stesse feature

in ogni frame. Una camera PTZ puo seguire un oggetto mediante i

propri meccanismi basandosi sui corner rilevati. Inoltre le feature si

possono anche usare per stimare il moto della telecamera stessa.

• Classificazione - Gli oggetti tendono ad assumere una disposizione

di feature caratteristica, quindi una camera puo essere in grado di ri-

conoscere e classificare alcune tipologie di elementi grazie ai rilevatori.

Ad esempio si puo allenare un’applicazione per riconoscere i veicoli che

transitano in un certo punto di un’autostrada, quindi classificandoli in

automobili, camion, moto o SUV.

• Compressione - Lo studio delle feature all’interno di un’immagine ri-

presa puo essere molto indicativo riguardo il contenuto di informazione

della scena. Infatti elementi molto dettagliati, come ad esempio tar-

ghe delle automobili, insegne, volti umani e altro, tendono ad avere un

101


grande numero di punti di interesse, sia corner che edge. Invece zone

piuttosto uniformi, ad esempio muri e strade, presentano un numero di

feature molto basso. Si possono sfruttare queste caratteristiche strut-

turali per creare un’applicazione che comprime l’immagine in base al

livello di dettaglio delle zone riprese [7], quindi in base al numero di

feature rilevate. In pratica, lo scopo e quello di ottenere un’immagine

che abbia una qualita molto elevata nelle zone con molti punti di inte-

resse e la minima possibile nei luoghi in cui le feature sono assenti. In

questo modo si ha anche il vantaggio del risparmio nella compressione

dei dati.

102

Appendice A

Codice sorgente dell’algoritmo

Generic FAST

A.1 Fast.h

#ifndef FAST H

#define FAST H

#include <s t r i n g . h>

#include ” P ixe l . h”

using namespace std ;

typedef unsigned char u i n t 8 t ;

class Fast

protected :

int m lower t ;

int m higher t ;

int m n ;

void make o f f s e t s ( int p i x e l [ ] , int r ow s t r i d e ) ;

bool ze ro dark ( const u i n t 8 t ∗ p , const int p i x e l [ ] ) ;

bool z e r o b r i g h t ( const u i n t 8 t ∗ p , const int p i x e l [ ] ) ;

103

APPENDICE A. CODICE SORGENTE DELL’ALGORITMO GENERIC FAST

bool e i gh t da rk ( const u i n t 8 t ∗ p , const int p i x e l [ ] ) ;

bool e i g h t b r i g h t ( const u i n t 8 t ∗ p , const int p i x e l [ ] ) ;

public :

Fast ( ) ˜Fast ( )

Pixe l ∗ f a s t d e t e c t ( const u i n t 8 t ∗ im , int xs i z e , int ys i z e ,

int s t r i d e , int b , int &ret num corners ) ;

void f a s t detect nonmax ( const u i n t 8 t ∗ im , const int &xs i z e ,

const int &ys i z e , const int &st r i d e , const int &b , int&

ret num corners , int suppre s s i on ) ;

int f a s t c o r n e r s c o r e ( const u i n t 8 t ∗ p , const int p i x e l [ ] , int

t s t a r t , bool br i gh t ) ;

int ∗ f a s t s c o r e ( const u i n t 8 t ∗ i , int s t r i d e , P ixe l ∗ corners ,

int num corners , int b) ;

P ixe l ∗ nonmax suppression ( const Pixe l ∗ corners , const int∗s co re s , int num corners , int &ret num nonmax ) ;

bool f u l l s e g t e s t b r i g h t ( const u i n t 8 t ∗ p , const int p i x e l [ ] )

;

bool f u l l s e g t e s t d a r k ( const u i n t 8 t ∗ p , const int p i x e l [ ] ) ;

;

#endif

A.2 Fast.cpp

#include ”Fast . h”

void Fast : : f a s t detect nonmax ( const u i n t 8 t ∗ im , const int&

xs i z e , const int& ys i z e , const int &st r i d e , const int &b , int

& ret num corners , int suppre s s i on )

int num corners ;

int∗ s c o r e s ;

104


Pixe l ∗ co rne r s ;

P ixe l ∗ nonmax ;

co rne r s = f a s t d e t e c t ( im , xs i z e , y s i z e , s t r i d e , b ,

r e t num corners ) ;

num corners = ret num corners ;

i f ( suppre s s i on )

s c o r e s = f a s t s c o r e ( im , s t r i d e , corners , num corners , b ) ;

nonmax = nonmax suppression ( corners , s co re s , num corners ,

r e t num corner s ) ;

f r e e ( s c o r e s ) ;

f r e e (nonmax) ;

f r e e ( co rne r s ) ;

bool Fast : : f u l l s e g t e s t b r i g h t ( const u i n t 8 t ∗ p , const int

p i x e l [ ] )

int pix count = 1 ;

int ptr = 1 ;

i f (p [ p i x e l [ 0 ] ] > m higher t )

while (p [ p i x e l [ ptr ] ] > m higher t )

i f (++pix count >= 9)

return true ;

ptr ++;

ptr = 15 ;

//CounterClockWise



return true ;

105


ptr−−;

i f (p [ p i x e l [ 8 ] ] > m higher t )

pix count = 1 ;

ptr = 9 ;

//ClockWise



return true ;

ptr = ( ptr + 1) % 16 ;

ptr = 7 ;

//CounterClockWise



return true ;

ptr > 0 ? ptr −− : ptr = 15 ;

return fa l se ;

bool Fast : : f u l l s e g t e s t d a r k ( const u i n t 8 t ∗ p , const int p i x e l

[ ] )

int pix count = 1 ;

int ptr = 1 ;

i f (p [ p i x e l [ 0 ] ] < m lower t )

while (p [ p i x e l [ ptr ] ] < m lower t )


return true ;

ptr ++;

106


ptr = 15 ;

//CounterClockWise



return true ;

ptr−−;

i f (p [ p i x e l [ 8 ] ] < m lower t )

pix count = 1 ;

ptr = 9 ;

//ClockWise



return true ;

ptr = ( ptr + 1) % 16 ;

ptr = 7 ;

//CounterClockWise



return true ;

ptr > 0 ? ptr −− : ptr = 15 ;

return fa l se ;

A.3 Fast9.cpp


int Fast : : f a s t c o r n e r s c o r e ( const u i n t 8 t ∗ p , const int p i x e l [ ] ,

int t s t a r t , bool br i gh t )

107


int t max = 255 ;

int t min = t s t a r t ;

int t ;

i f ( b r i gh t )

while ( t min != ( t max − 1) && t min != t max )

t = ( t max + t min ) / 2 ;

m higher t = ∗p + t ;

i f ( ! f u l l s e g t e s t b r i g h t (p , p i x e l ) )

t max = t ;

else

t min = t ;

else

while ( t min != ( t max − 1) && t min != t max )

t = ( t max + t min ) / 2 ;

m lower t = ∗p − t ;

i f ( ! f u l l s e g t e s t d a r k (p , p i x e l ) )

t max = t ;

else

t min = t ;

return t min ;

void Fast : : make o f f s e t s ( int p i x e l [ ] , int r ow s t r i d e )

p i x e l [ 0 ] = 0 + row s t r i d e ∗ 3 ;

p i x e l [ 1 ] = 1 + row s t r i d e ∗ 3 ;

p i x e l [ 2 ] = 2 + row s t r i d e ∗ 2 ;

p i x e l [ 3 ] = 3 + row s t r i d e ∗ 1 ;

108


p i x e l [ 4 ] = 3 + row s t r i d e ∗ 0 ;

p i x e l [ 5 ] = 3 + row s t r i d e ∗ −1;

p i x e l [ 6 ] = 2 + row s t r i d e ∗ −2;

p i x e l [ 7 ] = 1 + row s t r i d e ∗ −3;

p i x e l [ 8 ] = 0 + row s t r i d e ∗ −3;

p i x e l [ 9 ] = −1 + row s t r i d e ∗ −3;

p i x e l [ 1 0 ] = −2 + row s t r i d e ∗ −2;

p i x e l [ 1 1 ] = −3 + row s t r i d e ∗ −1;

p i x e l [ 1 2 ] = −3 + row s t r i d e ∗ 0 ;

p i x e l [ 1 3 ] = −3 + row s t r i d e ∗ 1 ;

p i x e l [ 1 4 ] = −2 + row s t r i d e ∗ 2 ;

p i x e l [ 1 5 ] = −1 + row s t r i d e ∗ 3 ;

int∗ Fast : : f a s t s c o r e ( const u i n t 8 t ∗ i , int s t r i d e , P ixe l ∗corners , int num corners , int t )

int n ;

int p i x e l [ 1 6 ] ;

int∗ s c o r e s = ( int ∗) mal loc ( s izeof ( int ) ∗ num corners ) ;

make o f f s e t s ( p ixe l , s t r i d e ) ;

for (n=0; n < num corners ; n++)

s c o r e s [ n ] = f a s t c o r n e r s c o r e ( i + corne r s [ n ] . y ∗ s t r i d e +

corne r s [ n ] . x , p ixe l , t , c o rne r s [ n ] . b r i gh t ) ;

return s c o r e s ;

Pixe l ∗ Fast : : f a s t d e t e c t ( const u i n t 8 t ∗ im , int xs i z e , int ys i z e

, int s t r i d e , int t , int &ret num corners )

int num corners = 0 ;

int n pos = 0 ;

int r s i z e =512;

109


int p i x e l [ 1 6 ] ;

int x , y ;

int pos t r , n eg t r ;

int b count , d count ;

const u i n t 8 t ∗ p ;

P ixe l px ;

P ixe l ∗ r e t c o r n e r s ;

r e t c o r n e r s = ( P ixe l ∗) mal loc ( s izeof ( P ixe l ) ∗ r s i z e ) ;make o f f s e t s ( p ixe l , s t r i d e ) ;

for ( y=3; y < y s i z e − 3 ; y++)

for ( x=3; x < x s i z e − 3 ; x++)

p = im + y ∗ s t r i d e + x ;

b count = 0 ;

d count = 0 ;

po s t r = ∗p + t ;

neg t r = ∗p − t ;

i f (p [ p i x e l [ 0 ] ] > po s t r )

b count++;

i f (p [ p i x e l [ 8 ] ] > po s t r )

b count++;

i f ( b count >= 1)

i f (p [ p i x e l [ 1 2 ] ] > po s t r )

b count++;

i f ( b count == 1)

i f (p [ p i x e l [ 4 ] ] > po s t r )

b count ++;

i f ( b count >=2)

110


m higher t = po s t r ;

i f ( f u l l s e g t e s t b r i g h t (p , p i x e l ) )

i f ( num corners == r s i z e )

r s i z e ∗=2;

r e t c o r n e r s = ( P ixe l ∗) r e a l l o c ( r e t c o rn e r s , s izeof (

P ixe l ) ∗ r s i z e ) ;r e t c o r n e r s [ num corners ] . x = x ;

r e t c o r n e r s [ num corners ] . y = y ;

r e t c o r n e r s [ num corners ] . b r i gh t = true ;

num corners++;

continue ;

i f (p [ p i x e l [ 0 ] ] < neg t r )

d count++;

i f (p [ p i x e l [ 8 ] ] < neg t r )

d count++;

i f ( d count >= 1)

i f (p [ p i x e l [ 1 2 ] ] < neg t r )

d count++;

i f ( d count == 1)

i f (p [ p i x e l [ 4 ] ] < neg t r )

d count ++;

i f ( d count >= 2)

m lower t = neg t r ;

i f ( f u l l s e g t e s t d a r k (p , p i x e l ) )

i f ( num corners == r s i z e )

r s i z e ∗=2;

111


r e t c o r n e r s = ( P ixe l ∗) r e a l l o c ( r e t c o rn e r s , s izeof (

P ixe l ) ∗ r s i z e ) ;r e t c o r n e r s [ num corners ] . x = x ;

r e t c o r n e r s [ num corners ] . y = y ;

r e t c o r n e r s [ num corners ] . b r i gh t = fa l se ;

num corners++;

continue ;

re t num corners = num corners ;

return r e t c o r n e r s ;

A.4 Nonmax.cpp


#define Compare (X, Y) ( (X)>=(Y) )

P ixe l ∗ Fast : : nonmax suppression ( const Pixe l ∗ corners , const int∗s co re s , int num corners , int &ret num nonmax )

int num nonmax = 0 ;

int l a s t r ow ;

int∗ r ow s ta r t ;

int i , j ;

int n pos = 0 ;

P ixe l ∗ ret nonmax ;

const int sz = ( int ) num corners ;

int point above = 0 ;

int po int be low = 0 ;

int prev row ;

int s c o r e ;

112


Pixe l pos ;

i f ( num corners < 1)

ret num nonmax = 0 ;

return 0 ;

ret nonmax = ( Pixe l ∗) mal loc ( num corners ∗ s izeof ( P ixe l ) ) ;

l a s t r ow = corne r s [ num corners −1] . y ;

r ow s ta r t = ( int ∗) mal loc ( ( l a s t r ow+1)∗ s izeof ( int ) ) ;

for ( i =0; i < l a s t r ow+1; i++)

row s ta r t [ i ] = −1;

prev row = −1;

for ( i =0; i< num corners ; i++)

i f ( co rne r s [ i ] . y != prev row )

r ow s ta r t [ c o rne r s [ i ] . y ] = i ;

prev row = corne r s [ i ] . y ;

for ( i =0; i < sz ; i++)

s co r e = s c o r e s [ i ] ;

pos = corne r s [ i ] ;

i f ( i > 0)

i f ( co rne r s [ i −1] . x == pos . x−1 && corne r s [ i −1] . y == pos . y &&

Compare ( s c o r e s [ i −1] , s c o r e ) )

continue ;

i f ( i < ( sz − 1) )

113


i f ( co rne r s [ i +1] . x == pos . x+1 && corne r s [ i +1] . y == pos . y &&

Compare ( s c o r e s [ i +1] , s c o r e ) )

continue ;

i f ( pos . y != 0 && row s ta r t [ pos . y − 1 ] != −1)

i f ( co rne r s [ po int above ] . y < pos . y − 1)

po int above = row s ta r t [ pos . y−1] ;

for ( ; c o rne r s [ po int above ] . y < pos . y && corne r s [

po int above ] . x < pos . x − 1 ; po int above++)

for ( j=point above ; co rne r s [ j ] . y < pos . y && corne r s [ j ] . x <=

pos . x + 1 ; j++)

int x = corne r s [ j ] . x ;

i f ( ( x == pos . x − 1 | | x ==pos . x | | x == pos . x+1) &&

Compare ( s c o r e s [ j ] , s c o r e ) )

goto cont ;

i f ( pos . y != l a s t r ow && row s ta r t [ pos . y + 1 ] != −1 &&

point be low < sz )

i f ( co rne r s [ po int be low ] . y < pos . y + 1)

po int be low = row s ta r t [ pos . y+1] ;

for ( ; po int be low < sz && corne r s [ po int be low ] . y == pos . y

+1 && corne r s [ po int be low ] . x < pos . x − 1 ; po int be low

++)

for ( j=po int be low ; j < sz && corne r s [ j ] . y == pos . y+1 &&

corne r s [ j ] . x <= pos . x + 1 ; j++)

114


int x = corne r s [ j ] . x ;

i f ( ( x == pos . x − 1 | | x ==pos . x | | x == pos . x+1) &&

Compare ( s c o r e s [ j ] , s c o r e ) )

goto cont ;

ret nonmax [ num nonmax++] = corne r s [ i ] ;

cont :

;

f r e e ( r ow s ta r t ) ;

ret num nonmax = num nonmax ;

return ret nonmax ;

A.5 Pixel.h

#ifndef PIXEL H

#define PIXEL H

#include <s t d i n t . h>

typedef struct

u in t 16 t x , y ;

bool br i gh t ;

Pixe l ;

#endif

115

Appendice B

Software Development Kit

Il Software Development Kit integrato di Axis e un insieme di strumenti

ed interfacce finalizzato allo sviluppo di applicazioni per i prodotti Axis.

Ogni software viene sviluppato come un Embedded Axis Package(EAP) e poi

installato sulla telecamera.

B.1 Compilatore CRIS

Prima di utilizzare l’SDK e necessario installare compilatore CRIS, fornito

dalla stessa Axis, che e un GCC GNU Compiler Collection per i processori

usati nei prodotti Axis, come ad esempio l’ARTPEC-3. Per poter creare

applicazioni compatibili con la camera Axis, quindi utilizzare il compila-

tore CRIS, e necessario lavorare in un sistema UNIX. Per l’installazione e

sufficiente usare il comando:

===============================================================

> dpkg -i cris-dist-v32-r93-i386.deb

===============================================================

Questo provvedera ad installare il compilatore sotto /usr/local.

116

APPENDICE B. SOFTWARE DEVELOPMENT KIT

B.2 Installazione SDK

Per quanto riguarda l’installazione dell’SDK e necessario avere il file in-

stall sdk.bin. I comandi da eseguire in questo caso sono:

===============================================================

> chown nome_utente install_sdk.bin

> ./install_sdk.bin

> cd axis/emb-app-sdk-[ver]

===============================================================

dove ver si riferisce alla versione dell’SDK che si desidera installare.

Gli strumenti forniti dal Software Development Kit installato, compren-

dono librerie ed interfacce, file di ambiente, binari precompilati, manuali e

documentazione, applicazioni di esempio e, a seconda della versione utiliz-

zata, possono essere disponibili strumenti opzionali come debugger e profiler

specifici per la telecamera.

B.3 Creazione del package

Il primo passo per la creazione del software e l’inizializzazione delle variabili

d’ambiente per l’SDK. La procedura e quella di posizionarsi sulla directory

root dell’SDK mediante la shell e digitare il comando:

===============================================================

> . ./init_env

===============================================================

Tale comando provvedera ad eseguire le seguenti operazioni:

• controllare la posizione del compilatore e il suo corretto funzionamento;

• impostare la variabile d’ambiente AXIS TOP DIR;

• aggiungere AXIS TOP DIR/tools/build/bin al path;

• aggiungere AXIS TOP DIR/tools/scripts al path.

117


Il passo successivo prevede la compilazione dei sorgenti al fine di creare

un package EAP. Posizionandosi nella directory contenente i file sorgenti

dell’applicazione, si digita il seguente comando per ottenere il package:

===============================================================

> create-package.sh

===============================================================

Tale comando fara le seguenti operazioni:

• creazione del file .target-makefrag;

• esecuzione del comando make nella directory corrente;

• controlla se il file package.conf esiste ed e sintatticamente corretto e

se necessario, chiede i parametri mancanti e provvede a creare il file

package.conf;

• se non esiste, crea e lascia vuoto il file param.conf ;

• crea un pacchetto che comprende i file binari insieme con i file html e

i file di configurazione.

Una volta eseguito questo comando, verranno aggiunti i seguenti file nella

directory corrente:

• .target-makefrag: specifiche di compilazione;

• nomeApplicazione: applicazione eseguibile (file binario);

• nomeApplicazione maxVersion minVersion ARTPEC-3.eap:

package file.

B.4 Upload sulla camera

L’output prodotto viene infine caricato sulla telecamera attraverso l’interfac-

cia grafica oppure mediante uno script da shell di comando:

118


===============================================================

> eap-install.sh axis_device_ip psw_root install

===============================================================

Allo stesso modo per mandare in esecuzione o fermare l’applicazione si puo

usare l’interfaccia grafica oppure i comandi da shell:

===============================================================

> install-onto-target.sh start

> install-onto-target.sh stop

===============================================================

B.5 Interfacce dell’SDK

Le interfacce messe a disposizione svolgono un ruolo fondamentale per lo

sviluppo dell’applicazione, infatti esse contengono tutte le funzioni inerenti

alla gestione dello stream video e alla interazione con i client.

Interfaccia Media Capture

Questa interfaccia viene utilizzata per leggere le immagini dalla camera, sia

nel formato non compresso YUV che nel formato compresso JPEG. Si puo

specificare il frame-rate secondo il quale le immagini vengono catturate e

modificare anche altri parametri dello stream, come la risoluzione e la rota-

zione. Si puo inoltre ricevere una serie di immagini consecutive, una quantita

predefinita chiamata burst.

Interfaccia Parameter

Lo scopo di questa interfaccia e quello di fornire allo sviluppatore un modo

semplice per memorizzare dati e impostazioni dell’applicazione. I parametri

specifici del software possono essere prefissati in sede di creazione, ma in

questo modo si ha anche la possibilita di farli variare a run-time. Possono

essere definite funzioni callback per specificare azioni da compiere ogni qual

volta un parametro venga aggiornato.

119


Interfaccia Http

L’interfaccia in questo caso fa in modo che l’applicazione si comporti come

una CGI (Common Gateway Interface) o come una pagina web dinamica.

Cio e reso possibile da un re-indirizzamento URL che invece di mostrare la

pagina web indicata, manda direttamente all’applicazione. L’utente in questo

modo puo vedere le informazioni grazie al browser.

120

Bibliografia

[1] http://www.axis.com.

[2] http://www.axis.com/techsup/cam_servers/dev/cam_http_api_

index.php.

[3] http://www.adaptivepath.com/publications/essays/archives/

000385.php.

[4] http://www.raymondhill.net/voronoi/rhill-voronoi.php.

[5] Moh B. Al-Daoud and Stuart A. Roberts. New methods for the

initialisation of clusters. Pattern Recogn. Lett., 17:451–455, May 1996.

[6] Michael R. Anderberg. Cluster analysis for applications / Michael R.

Anderberg. Academic Press, New York, 1973.

[7] Andrew D. Bagdanov, Marco Bertini, Alberto Del Bimbo, and Lorenzo

Seidenari. Adaptive video compression for video surveillance applica-

tions. In Proc. of ISM Int‘l Symposium on Multimedia, Dana Point,

California, USA, December 2011. IEEE. (Oral).

[8] G. Ball and D. Hall. Isodata: A novel method of data analysis and

pattern classification. Technical report, Stanford Research Institute,

Menlo Park, 1965.

[9] Adam Baumberg. Reliable feature matching across widely separated

views, 2000.

121

BIBLIOGRAFIA

[10] P.R. Beaudet. Rotational invariant image operators. In Proceedings of

the 4th International Joint Conference on Pattern Recognition, pages

579–583, 1978.

[11] I. Biederman. Recognition-by-components: A theory of human image

understanding. Psychol Review, 94(2):115–147, 1987.

[12] A. Bowyer. Computing Dirichlet tessellations. The Computer Journal,

24(2):162–166, January 1981.

[13] J. E. Bresenham. Algorithm for computer control of a digital plotter,

pages 1–6. ACM, New York, NY, USA, 1998.

[14] J Canny. A computational approach to edge detection. IEEE Trans.

Pattern Anal. Mach. Intell., 8:679–698, November 1986.

[15] D L Davies and D W Bouldin. A cluster separation measure. IEEE

Transactions on Pattern Analysis and Machine Intelligence, 1(2):224–

227, 1979.

[16] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likeli-

hood from incomplete data via the em algorithm. JOURNAL OF THE

ROYAL STATISTICAL SOCIETY, SERIES B, 39(1):1–38, 1977.

[17] E. Diday and J. Simon. Clustering Analysis. In K. Fu, editor, Digital

Pattern Recognition. Springer-Verlag, Berlin/Heidelberg/NY, 1976.

[18] Robert D. Dony and Ieee Simon Haykin. Neural network approaches to

image compression. In Proc. IEEE, pages 288–303, 1995.

[19] J. C. Dunn. Well separated clusters and optimal fuzzy-partitions.

Journal of Cybernetics, 4:95–104, 1974.

[20] E. Forgy. Cluster analysis of multivariate data: efficiency versus

interpretability of classifications. Biometrics, 21:768–780, 1965.

[21] S Fortune. A sweepline algorithm for voronoi diagrams. In Proceedings

of the second annual symposium on Computational geometry, SCG ’86,

pages 313–322, New York, NY, USA, 1986. ACM.

122

BIBLIOGRAFIA

[22] E. B. Fowlkes and C. L. Mallows. A Method for Comparing Two Hie-

rarchical Clusterings. Journal of the American Statistical Association,

78(383):553–569, 1983.

[23] C. Harris and M. Stephens. A Combined Corner and Edge Detection.

In Proceedings of The Fourth Alvey Vision Conference, pages 147–151,

1988.

[24] Ji He, Ah hwee Tan, and Chew lim Tan. Art-c: A neural architecture for

self-organization under constraints. In In Proceedings of International

Joint Conference on Neural Networks (IJCNN, pages 2550–2555, 2002.

[25] Ji He, Man Lan, Chew lim Tan, Sam yuan Sung, and Hwee boon

Low. Initialization of cluster refinement algorithms:. In in Proceedings

of International Joint Conference on Neural Networks (IJCNN, pages

297–302, 2004.

[26] Mike Heath, Sudeep Sarkar, Thomas Sanocki, and Kevin Bowyer. Com-

parison of edge detectors: A methodology and initial study. In Initial

Study,” Computer Vision and Image Understanding, pages 38–54. IEEE

Computer Society Press, 1996.

[27] Paul Jaccard. Etude comparative de la distribution florale dans une

portion des Alpes et des Jura. Bulletin del la Societe Vaudoise des

Sciences Naturelles, 37:547–579, 1901.

[28] Anil K. Jain and Richard C. Dubes. Algorithms for clustering data.

Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988.

[29] Mehmed Kantardzic. Data Mining: Concepts, Models, Methods and

Algorithms. John Wiley & Sons, Inc., New York, NY, USA, 2002.

[30] I. Katsavounidis, C. C. Jay Kuo, and Zhen Zhang. A new initializa-

tion technique for generalized Lloyd iteration. IEEE Signal Processing

Letters, 1(10):144–146, October 1994.

[31] Leonard Kaufman and Peter J. Rousseeuw. Finding Groups in Data:

An Introduction to Cluster Analysis. John Wiley & Sons, 1990.

123

BIBLIOGRAFIA

[32] N. Khan, D.M. Mohamudally. A multiagent system (mas) for the gene-

ration of initial centroids for k-means clustering data mining algorithm

based on actual sample. In Journal of Next Generation Information

Technology, volume 1, page 495, 2010.

[33] Benjamin King. Step-Wise Clustering Procedures. Journal of the

American Statistical Association, 62(317):86–101, 1967.

[34] Les Kitchen and Azriel Rosenfeld. Gray-level corner detection. Pattern

Recognition Letters, 1(2):95 – 102, 1982.

[35] Stuart P. Lloyd. Least squares quantization in pcm. IEEE Transactions

on Information Theory, 28:129–137, 1982.

[36] Bruce D. Lucas and Takeo Kanade. An iterative image registration

technique with an application to stereo vision. pages 674–679, 1981.

[37] J. B. MacQueen. Some methods for classification and analysis of multi-

variate observations. In L. M. Le Cam and J. Neyman, editors, Proc. of

the fifth Berkeley Symposium on Mathematical Statistics and Probability,

volume 1, pages 281–297. University of California Press, 1967.

[38] P. C. Mahalanobis. On the generalised distance in statistics. In Procee-

dings National Institute of Science, India, volume 2, pages 49–55, April

1936.

[39] Elmar Mair, Gregory D. Hager, Darius Burschka, Michael Suppa, and

Gerhard Hirzinger. Adaptive and generic corner detection based on the

accelerated segment test. In European Conference on Computer Vision

(ECCV’10), September 2010.

[40] J. Mogul, B. Krishnamurthy, F. Douglis, A. Feldmann, Y. Goland,

A. van Hoff, and D. Hellerstein. Delta encoding in HTTP. RFC 3229

(Proposed Standard), January 2002.

[41] Hans Moravec. Towards automatic visual obstacle avoidance. In Procee-

dings of the 5th International Joint Conference on Artificial Intelligence,

page 584, August 1977.

124

BIBLIOGRAFIA

[42] Hans P. Moravec. Visual mapping by a robot rover. In Proceedings of

the 6th international joint conference on Artificial intelligence - Volume

1, pages 598–600, San Francisco, CA, USA, 1979. Morgan Kaufmann

Publishers Inc.

[43] F. Murtagh. A survey of recent advances in hierarchical clustering

algorithms which use cluster centers. Computer Journal, 26:354–359,

1984.

[44] N. Otsu. A threshold selection method from gray-level histograms. IEEE

Transactions on Systems, Man and Cybernetics, 9(1):62–66, January

1979.

[45] N.R. Pal and J. Biswas. Cluster validation using graph theoretic

concepts. Pattern Recognition, 30(6):847 – 857, 1997.

[46] Dan Pelleg and Andrew W. Moore. X-means: Extending k-means wi-

th efficient estimation of the number of clusters. In Proceedings of

the Seventeenth International Conference on Machine Learning, ICML

’00, pages 727–734, San Francisco, CA, USA, 2000. Morgan Kaufmann

Publishers Inc.

[47] J. M. S. Prewitt. Object enhancement and extraction. Picture Processing

and Psychopictorics. Lipkin and Rosenfeld, Eds. New York, 1970.

[48] P. Resnick. Internet Message Format. RFC 5322 (Draft Standard),

October 2008.

[49] Lawrence G. Roberts. Machine Perception of Three-Dimensional So-

lids. Outstanding Dissertations in the Computer Sciences. Garland

Publishing, New York, 1963.

[50] Edward Rosten. High performance rigid body tracking. PhD thesis,

University of Cambridge, Febuary 2006.

[51] Edward Rosten and Tom Drummond. Fusing points and lines for high

performance tracking. In IEEE International Conference on Computer

Vision, volume 2, pages 1508–1511, October 2005.

125

BIBLIOGRAFIA

[52] Edward Rosten and Tom Drummond. Machine learning for high-

speed corner detection. In European Conference on Computer Vision,

volume 1, pages 430–443, May 2006.

[53] P F Russell and T R Rao. On habitat and association of species of ano-

pheline larvae in south-eastern madras. Journal of the Malaria Institute

of India, 3(1):153–178, 1940.

[54] J. Sauvola and M. Pietikainen. Adaptive document image binarization.

Pattern Recognition, 33(2):225 – 236, 2000.

[55] Bernt Schiele and James L. Crowley. Probabilistic object recognition

using multidimensional receptive field histograms. pages 610–619, 1996.

[56] Cordelia Schmid and Roger Mohr. Local grayvalue invariants for ima-

ge retrieval. IEEE Transactions on Pattern Analysis and Machine

Intelligence, 19:530–535, 1997.

[57] Cordelia Schmid, Roger Mohr, and Christian Bauckhage. Evaluation of

interest point detectors. Int. J. Comput. Vision, 37:151–172, June 2000.

[58] Subhash Sharma. Applied multivariate techniques. John Wiley & Sons,

Inc., New York, NY, USA, 1996.

[59] Akira Shiozaki. Edge extraction using entropy operator. Comput. Vision

Graph. Image Process., 36:1–9, November 1986.

[60] S. M. Smith and J. M. Brady. Susan - a new approach to low level image

processing. International Journal of Computer Vision, 23:45–78, 1995.

[61] P.H.A. Sneath and R.R. Sokal. Numerical Taxonomy. The Principles

and Practice of Numerical Classification. Freeman, 1973.

[62] Irwin Edward Sobel. Camera models and machine perception. PhD

thesis, Stanford, CA, USA, 1970.

[63] R. R. Sokal and C. D. Michener. A statistical method for evalua-

ting systematic relationships. University of Kansas Science Bulletin,

38:1409–1438, 1958.

126

BIBLIOGRAFIA

[64] Simon Taylor, Edward Rosten, and Tom Drummond. Robust feature

matching in 2.3µs. In IEEE CVPR Workshop on Feature Detectors and

Descriptors: The State Of The Art and Beyond, June 2009.

[65] Bo Thiesson, Christopher Meek, David Maxwell Chickering, and David

Heckerman. Learning mixtures of bayesian networks. In in Cooper &

Moral, 1997.

[66] Carlo Tomasi and Takeo Kanade. Detection and tracking of point

features. Technical report, International Journal of Computer Vision,

1991.

[67] J T Tou and R C Gonzalez. Pattern recognition principles. Image

Rochester NY, 7:377, 1974.

[68] Panos E. Trahanias and Anastasios N. Venetsanopoulos. Color edge

detection using vector order statistics. IEEE Transactions on Image

Processing, 2(2):259–264, 1993.

[69] Panos E. Trahanias and Anastasios N. Venetsanopoulos. Vector or-

der statistics operators as color edge detectors. IEEE Transactions on

Systems, Man and Cybernetics, Part B (Cybernetics), 26(1):135–143,

February 1996.

[70] Miroslav Trajkovic and Mark Hedley. Fast corner detection. Image and

Vision Computing, 16(2):75 – 87, 1998.

[71] John C. Trinder and Yandong Wang. Automatic road extraction from

aerial images. Digital Signal Processing, 8(4):215 – 224, 1998.

[72] Han Wang and Michael Brady. Real-time corner detection algorithm

for motion estimation. Image and Vision Computing, 13(9):695 – 703,

1995.

[73] Jr. Ward. Hierarchical grouping to optimize an objective function.

Journal of the American Statistical Association, 58:236–244, 1963.

127

BIBLIOGRAFIA

[74] D. F. Watson. Computing the n-dimensional Delaunay tessellation with

application to Voronoi polytopes. The Computer Journal, 24(2):167–

172, January 1981.

[75] Lotfi A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353,

1965.

[76] C. T. Zahn. Graph-theoretical methods for detecting and describing

gestalt clusters. IEEE Trans. Comput., 20:68–86, January 1971.

[77] Silvano Di Zenzo. A note on the gradient of a multi-image. Computer

Vision, Graphics, and Image Processing, 33(1):116–125, 1986.

[78] Zhiqiang Zheng, Han Wang, and Eam Khwang Teoh. Analysis of gray

level corner detection. Pattern Recogn. Lett., 20:149–162, February 1999.

128

Ringraziamenti

Desidero per prima cosa ringraziare il Prof. Alberto Del Bimbo per avermi

dato l’opportunita di poter lavorare su questo progetto e quindi avere reso

possibile questa magnifica esperienza.

Ringrazio vivamente anche Lorenzo Seidenari e Marco Bertini per aver-

mi guidato durante tutto lo sviluppo dell’applicazione e per tutti i preziosi

consigli che mi hanno dato, e ringrazio anche tutti gli altri ragazzi del MICC

per avermi fatto sempre sentire a mio agio.

Desidero ringraziare fortemente i miei genitori e mia sorella per avermi

sostenuto in tutti questi anni di studio. Ringrazio Elisabetta per essermi

stata sempre accanto anche nei momenti piu difficili e per avermi stimolato

a dare sempre il massimo.

Un doveroso ringraziamento a tutti i ragazzi con cui ho condiviso questi

anni di studio, che tra LAN party e Tressette mi hanno fatto dimenticare

il significato della parola noia: Niccolo, Sandro, Simone, Federico, Dimo,

Marco, Claudio, Lorenzo, Andrea, Giacomo, David, Alessandro, Giovanni e

tutti gli altri.

Un particolare grazie a Tommaso, anche se ora abita a Trieste mi e sempre

rimasto vicino.

Infine ringrazio anche Bruco, Papia, Aloha, Cicce, Army e Invinciball

perche suonare insieme a loro e una delle cose piu belle nella mia vita.

129

Estrazione real-time di caratteristiche immagine di basso livello a bordo di telecamera

Documents

Transcript of Estrazione real-time di caratteristiche immagine di basso livello a bordo di telecamera