Applicazione per la vettorializzazione di immagini a pixel sparsi: SPVector

Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         5 
notevole perdita di tempo. L’uso, invece, di software di conversione automatica 
permettono riconoscimenti molto accurati degli originali e supportano vari formati di 
file in uscita. Il processo di trasformazione dell’immagine da un formato mappato a bit 
ad un formato vettoriale viene detto “conversione da raster a vector”. La vettorizzazione 
è dunque la trasformazione di immagini raster nelle corrispondenti figure geometriche 
primitive che la compongono, di solito vettori. Essa gioca un ruolo importante in una 
vasta area di applicazione. 
  Gli usi più diffusi sono, per esempio, l’applicazione di software di vettorializzazione 
ad immagini passate da satellite per riconoscere le caratteristiche topografiche di area 
geografiche o ancora la lettura di frame passati da telecamere in linee di montaggio per 
il riconoscimento e rilevazione della posizione spaziale di pezzi meccanici e non. Il 
riconoscimento di documenti cartacei è un altro campo di applicazione in cui spiccano il 
riconoscimento di testi (sostare OCR (“optical carachter recognition”) e il 
riconoscimento geometrico di disegni tecnici. Non ultime le nuove applicazioni che si 
sono venute a sviluppare pari passo con lo sviluppo delle nuove tecnologie e il sempre 
più diffuso uso di internet, vale a dire il riconoscimento delle firme digitali e il 
riconoscimento delle impronte digitali che trova applicazione anche nei sistemi di 
sicurezza. In definitiva tutte le applicazioni che richiedono informazioni specifiche e di 
livello qualitativo superiore della semplice rappresentazione bit a bit dell’immagine 
sono basate su processi di vettorializzazione dell’immagine. 
Le fonti principali dalle quali attingiamo immagini sono i principali sistemi di input dei 
calcolatori quali scanner, fotocamere e telecamere digitali, ma anche e sempre di più 
attraverso lo scambio informatico tramite tutti i supporti di massa e di rete disponibili 
attualmente. 
Da questi otteniamo i formati di immagine più comuni che la traducono tramite un 
susseguirsi di bit che rappresentano una griglia (o mappa di bit o retino) di quadratini 
delle dimensioni dell’immagine stessa. Ogni quadratino viene detto pixel e ad esso 
vengono assegnati dei bit che ne rappresentano la posizione in griglia e il valore 
cromatico. 
Quindi cercando di manipolare questo tipo di file ci troviamo ad elaborare gruppi di 
pixel invece di oggetti geometrici definiti. E’ a questo punto che tornano molto utili i 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         6 
software di vettorializazione che analizzando le immagini raster riconoscendone le 
forme geometriche primitive e permettendo di salvarle in formati facilmente leggibili da 
sistemi CAD e quindi facilmente modificabili e personalizzabili. In poche parole da un 
insieme di pixel colorati (di solito neri), detta anche macchia ricaviamo un vettore o più 
vettori che la rappresentano. Quindi da un notevole numero di bit (più di uno per pixel) 
passiamo ad una rappresentazione che ne usa pochissimi dovendo indicare di un vettore 
solo il punto iniziale, quello finale e lo spessore della linea che li unisce. 
Se un formato di immagine ricavata dallo scanner può essere vettorializzata in un 
insieme di linee e di curve gli spazi in archivio possono essere notevolmente ridotti 
essendo i formati derivanti poco importanti dal punto si vista della quantità di dati 
rispetto al formato precedente. Da non sottovalutare che se l’immagine vettoriale 
ricavata viene salvata in file di formato CAD, essa può essere facilmente modificabile o 
aggiornata con i software CAD stessi. 
I programmi di vettorializzazione sono molteplici essendo molteplici le loro 
applicazioni, quindi per ogni scopo preciso il programma vieni mirato e studiato per i 
particolari tipi di immagini che si trova ad elaborare. 
Nel calderone di tutte queste applicazioni rivestono particolare importanza i software di 
riconoscimento di disegni tecnici che da rilevazioni raster elaborano file in formato 
solitamente dxf esportabili nei maggiori sistemi CAD e quindi elaborabili. E’ proprio in 
questo settore che abbiamo rivolto la nostra attenzione, all’analisi di immagini statiche 
derivanti da disegni tecnici, cercando di creare un’applicazione che produca una 
primitiva vettorializzazione iniziale distinguendo i diversi spessori delle linee che 
compongono il disegno e fornendo un formato di file in uscita facilmente gestibile per 
future modifiche o archiviazioni poco gravose. 
 
 
1.2 L’evoluzione dei metodi 
La vettorializzazione di immagini raster è un è ad un livello di sviluppo e di analisi 
relativamente maturo nell’analisi di documenti e nel campo del riconoscimento 
geometrico ma è ancora lontana dall’essere perfetta. In questo paragrafo farò una 
carrellate delle principali metodologie sino ad oggi implementate spiegandone le 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         7 
metodologie ed i principi di base. Tutto questo lo ritengo utile per dare una carrellata 
generale delle tecniche ma soprattutto credo possa essere un valido appoggio 
decisionale per chi intenda sviluppare una propria metodologia o migliorarne una, 
potendo decidere quale ritiene più efficace o prendendo spunto per apportare migliorie 
alla propria. 
Tutte le tecniche sviluppate in questi anni partono da una vettorializzazione di base che 
raggruppa serie di pixel in linee primitive descritte da alcuni attributi come punti 
caratteristici e spessori delle linee. Una successiva vettorializzazione avanzata invece 
ricerca forme avanzate elaborando i risultati della vettorializzazione di base. E’ proprio 
alla vettorializzazione di base (detta anche cruda vettorializzazione) che si applicano 
tutte le diverse metodologie sviluppate, in cui da un’immagine raster (binaria) in entrata 
generano barre (segmenti con spessore di linea diverso da zero) o polilinee (catene di 
barre lincate tra loro alle estremità). 
Molti metodi di cruda vettorializzazione sono stati sviluppati e implementati fin da 
quando le tecniche di analisi delle immagini sono state introdotte più di trenta anni 
fa.Questi metodi possono essere grossolanamente divisi in sei categorie: Hough 
Trasform (HT), Thinning based mathods, contour based methods, run-graph based 
methods, mesh pattern based methods and sparse pixel based mathods. 
Con l’eccezione del metodo HT un tipico processo di vettorializzazione consiste nel 
seguente schema di base: 
1. Campionamento dei punti medi o ricerca dell’asse medio o delle linee.Questo è 
il cuore del processo per la riduzione delle informazioni, dopo il quale 
rimangono solo i punti significativi che rappresentano gli assi medi.  
2. Tracciamento delle linee, che segue il riconoscimento dei punti medi per avere 
una catena di punti per ogni vettore. 
3. Approssimazione o poligonalizzazione dei punti trovati che rimuove i punti non 
critici dalla catena trovata nel secondo step e linca i punti rimanenti in barre o 
polilinee. I punti critici rimanenti sono usati infine per rappresentare i vettori 
estratti dall’immagine raster. 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         8 
La differenza maggiore tra tutti i metodi sviluppati risiede nei primi due sottoprocessi. 
Diversi algoritmi di poligonalizzazione  possono essere implementati nel terzo 
sottoprocesso. 
 
 
1.2.1 Hough Trasform based method 
I metodi basati sulla trasformazione di Hugh 
1
(HT , Hough Trasform) trasformano un 
disegno esteso con rappresentazione binaria in un disegno con caratteristiche compatte 
in una spazio parametrico. La trasformazione converte un difficoltoso problema di 
riconoscimento di un’immagine complessa in una più facile selezione di picchi  
significativi in una spazio parametrizzato. Un metodo con il quale l’HT può essere usato 
per riconoscere linee diritte (segmenti in genere, parti di figure geometriche più 
complesse) è di parametrizzarle in relazione alla loro pendenza e allo loro intercetta. 
Una linea nel piano (x,y) è definita dall’equazione: 
y = mx + c           (1) 
Ogni linea nel piano (x,y) corrisponde ad un punto nel piano (m,c). Ogni punto nel 
piano (x,y) può avere un infinito numero di linee passante per esso. La pendenza e 
l’intercetta di questa linea formano nel piano (m,c) una linea descritta dall’equazione: 
c = -xm + y       (2) 
Il piano (m,c) è diviso in « cassette » (contenitori) che accumulano per ogni pixel nero 
nel piano (x,y) tutti i punti che giacciono lungo la linea di equazione (2). Quando la 
linea di equazione (2) è stata analizzata in ogni pixel la cella attraverso la quale essa 
passa viene incrementata. 
Dopo il controllo di tutti i pixel nell’immagine, le linee sono individuate come picchi 
nello spazio trasformato. Tenendo conto delle distorsioni, ogni singolo picco che risulta 
maggiore di una predeterminata soglia è usato per definire la linea definita 
nell’equazione (1). In pratica, queste linee determinate sono una combinazione di 
numerosi segmenti sulla stessa linea (barra). Dunque, i pixel nell’immagine originale 
lungo la supposta linea sono seguiti fino a quando non viene trovato il punto finale di 
                                                 
1
 Huogh PVC. A method and means for recognizing complex patterns . USA Patent 3,096,654, 1962 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         9 
questi segmenti. Anche la larghezza della linea viene ricavata durante la ricerca 
analizzando la larghezza in corrispondenza di ogni pixel. 
Per il riconoscimento di linee diritte il metodo HT visita una volta tutti i pixel che 
compongono l’immagine. Quindi la sua complessità in termini di tempo è lineare con il 
numero totale dei pixel, che risulta il prodotto dell’altezza e della larghezza 
dell’immagine. Poichè ogni lato dell’immagine è lineare alla risoluzione della stessa, è 
plausibile usare la risoluzione dell’immagine come unità per analizzare la complessità 
temporale di analisi dei metodi di vettorializzazione. Quindi, la complessità in ordine di 
tempo del metodo HT per la vettorializzazione di base è di ordine quadrato rispetto alla 
risoluzione dell’immagine. 
Siccome i picchi vengono ricercati nel piano (m,c) anche per punti i cui valori m  e c 
derivano da spezzate o distorsioni delle linee nell’immagine originale, HT può essere 
usato per determinare le linee in immagini disturbate. Poiché, le pendenze e le intercette 
sono ricavate in modo sparso, esse non possono essere precise come nelle linee 
originali. Quindi, la qualità delle linee ricavate è molto meno precisa per le linee 
pendenti. Questo può essere osservato nella figura 8 che rappresenta una 
implementazione del metodo HT. Inoltre i metodi basati sul sistema HT possono 
produrre soltanto barre e non possono generare polilinee. 
 
 
1.2.2 Thinning based methods. 
Tamura
2
, Smith
3
 and Lam
4
 forniscono convincenti implementazioni ed analisi di metodi 
Thinning (o metodi che snelliscono l’immagine). I metodi Thinning-based sono stati 
largamente utilizzati in molti dei primi sistemi di vettorializzazione (Fahn 
5
, Kasturi
6
 
                                                 
2
 Tamura H. A Comparison of line thinning alghoritms from digital geometry viewpoint. In Proceedings 
of the 4
th
 International Conference on Pattern Recognition , Kyoto, Japan, 1978, pp 715-719. 
3
 Smith RW. Computer processing of line images : A survey. Pattern Recognition 1987; ,20(1):7-15. 
4
 Lam L, Lee SW and Suen CY. Thinning methodologies – A comprehensive survey. IEEE Transaction 
on Pattern Analysis and Machine Intelligence 1992; 14(9):869.887. 
5
 Fahn CS, Wang JF, and Lee JY. A Topology-Based Component Extractor for Understanding 
Electrical Circuit Diagram. Computer Vision,Graphic and Image Processing 1988; 44:119-138. 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         10 
and Nagasamy and Langrana 
7
) e alcuni successivi metodi corretti (Hori and Tanigawa
8
) 
li adottano come primo approccio al problema. Tutti questi processi implementano una 
procedura di snellimento nel sottoprocesso di ricerca dei punti medi atta ad ottenere uno 
scheletro di larghezza di un pixel rappresentante la regione di punti neri prima che il 
processo di ricerca della linea abbia inizio. 
I metodi sottili (Thinning) (detti anche Skeletonization, Skeletoniziong, Core-line 
Detection, Medial Axis Trasformation o Symmetric Axis Transformation in letteratura) 
sono che operano delle operazioni morfologiche (Haralick and Shapiro
9
) nell’immagine 
raster in entrata e restituiscono uno scheletro di spessore unitario (1 pixel) dell’area di 
pixel neri. Lo scheletro dell’area scura è il minor numero di punti che la rappresentano, 
mantenendo la struttura topologica  identica  della forma della figura di partenza. 
Quindi è molto più facile da analizzare dell’immagine originale. Questo scheletro è 
definito da Montanari
10
 come il luogo delle intersezioni delle creste delle onde che si 
propagano dai margini opposti dell’area in analisi verso l’interno. Pfaltz and Rosenfelt 
11
definiscono che lo scheletro è formato dai centri dei massimi cerchi inscrivibili 
nell’area in questione. Davies and Plummer
12
 aggiungono punti supplementari 
sufficienti allo scheletro definito da Pfaltz and Rosenfeld tanto da renderlo connesso. 
Basati sulle sopraccitate definizioni di scheletro gli algoritmi sottili sono do tre 
tipologie: erosione iterattiva dei bordi (come la propagazione delle creste di onda) 
                                                                                                                                               
6
 Kasturi R, Bow ST, El-Masri W,Shan J, Gattiker JR, Mokate UB. A System for Interpretation of Line 
Drawings. IEEE Transaction on Pattern Analysis and Machine Inteligence 1990; 12(10): 978-992. 
7
 Nagasamy V, Langrana N. Engineering Drawing Processing and Vectorization System .Computer 
Vision, Graphics and Image Processing 1990; 49(3): 379-397. 
8
 Hori O,and Tanigawa S. Raster-to-Vector Conversion by Line Fitting Based on Contours and 
Skeleton. In Proceedings of the 2
nd
 International Conference on Document Analysis and Recognition, 
Tsukuba, Japan, 1993, pp 623-626. 
9
 Haralik RM, and ShapiroL, Computer and Robot Vision. Addison Wesley, Reading MA, 1992. 
10
 Montanari U. Continuos skeleton from digitised images, Journal of the ACM 1969; 16:534-549 
11
 Pfaltz JL and Rosenfeld A. Computer Rapresentation of plannar regions by their skeleton. 
Communications of the ACM 1967 ; 10:119-125. 
12
 Davis ER and Plummer APN. Thinning Algorithm: a critique and a new methodology. Pattern 
Recognition 1981; 14: 53-53. 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         11 
(Nacchache and Shinghal
13
), trasformazioni di distanza (“Distance 
Transform”)(Rosenfeld and Pfaltz 
14
, Peleg and Rosenfeld
15
) e lo scheletro adeguato 
(“Adeguate Skeleton”)(Davies and Plummer).  
I metodi di snellimento ricorsivo (thinning mathod) sviluppano l’idea di un continuo 
restringimento del contorno (o di una rimozione dello strato più esterno dei pixel) 
dell’oggetto in analisi (di solito linee) come il propagarsi di un fronte d’onda 
immaginario dall’estreno all’interno della figura geometrica fino a che solo lo scheletro 
della forma rimanga (formato da un pixel di spessore). Questi  metodi, eccetto quello 
sviluppato da Montanari, che lavora sul contorno della figura, sono sorprendentemente 
simili tra loro come desritto da Naccache e Shingahal. 
Seguendo la definizione di scheletro, Montanari considera il vettore dalla linea esterna 
del contorno dell’oggetto come un fronte di onda. Questo si propaga in maniera 
iterattiva verso l’interno della regione tenendo conto che la sovrapposizione dei fronti 
non è concessa. I punti di intersezione dei fronti d’onda sono considerati come i punti 
facenti parte lo scheletro dell’immagine. I pixel che definiscono il contorno della figura 
sono ricavati con un algoritmo di riconoscimento del contorno, che risulta una comune 
operazione ormai a livelli avanzati nell’analisi delle immagini (Haralick e Shapiro, e 
Nalwa
16
). I pixel del contorno sono quindi raggruppati in una catena che viene 
nuovamente analizzata con una procedura di poligonalizzazione (vedere paragrafo 
1.2.7). Quindi, il grosso dell’analisi riguarda il riconoscimento del bordo della figura la 
cui complessità in termini di tempo risulta lineare al numero totale dei pixel 
dell’immagine e quindi quadratica rispetto alla sua risoluzione. Il tempo necessario per 
la poligonalizzazione è trascurabilmente inglobato nel processo di ricerca dei contorni. 
                                                 
13
 Naccache NJ and Shinghal R. An Investigation into the skeletonization approach of Hilditch. Pattern 
Recognition 1984; 17: 279-284. 
    Nacchache Njand Shingal R. SPTA: a proposed algorithm for thinning binary patterns. IEEE 
transaction on System, Man, and Cybernetics 1984; 14:409-418.   
14
 Rosenfeld A and Pfaltz JL. Sequentiial operation in digital pictures processing. Journal of the ACM 
1996; 13:471-494. 
15
 Peleg S and Rosenfald A. A Min-max medial axis transformation. IEEE Transaction on Pattern 
Analysisi and Machine Inteligence 1981; 3;208-210. 
16
 Nalwa VS. A Guided Tour of Computer Vision. Addison-Wesley, New York, 1993 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         12 
Quindi essendo la propagazione delle creste di onda lineare con gli spessori delle linee 
(che sono lineari alla risoluzione dell’immagine) e la ricerca dei contorni (che è 
anch’essa lineare alla risoluzione dell’immagine dato che il perimetro di una regione 
piana è lineare alla raggio della regione stessa), la complessità totale del metodo e 
quadratica rispetto alla risoluzione. 
Il metodo snellimento iterattivo è come l’iterattiva erosione del bordo dell’oggetto in 
questione. Come è stato proposto da Hilditch
17
, il cuore della procedura è di muovere 
una finestra di dimensioni 3 x 3 sopra l’immagine applicando una serie di regole per 
etichettare il punto in centro. Al completamento di ogni ricerca dei pixel tutti i punti 
etichettati sono cancellati. Il processo di ricerca viene ripetuto fino a quando più nessun 
punto può essere eliminato. Il metodo di codifica dei punti nelle finestre 3 x 3 è esposto 
nella figura  1 . 
 
 
 
 
 
 
Le regole seguite per etichettare i punti sono descritte da Naccache and Shinghal come 
segue. P viene etichettato per essere eliminato se tutte le regole seguenti sono 
soddisfatte. 
• P deve avere almeno 1 pixel bianco attorniato da 4 (Rosenfeld 
18
) vicini. P è un 
punto sul bordo. 
• P deve avere almeno 2 pixel neri attorniati da 8 (Rosenfeld) vicini. P non è un 
punto finale. 
• Almeno uno degli 8 punti neri vicini a P non deve essere etichettato. 
• P non deve essere un punto di interruzione (la cui eliminazione disconnetterebbe 
due parti di una linea). 
                                                 
17
 Hilditch CJ. Linear Skeleton from square cupboards. Machine Intelligence 1969 ; 4: 403-420 
18
 Rosenfeld A. Connectivity in digital pictures. Journal of the ACM 1970; 17: 146-160. 
P3 P2 P1 
P4 P P0 
P5 P6 P6 
Figura 1  Il pixel P e 3 x 3 punti vicini 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         13 
• Se P2 è un punto etichettato, settare P2 bianco non deve rendere P un punto di 
interruzione. 
• Se P4 è un punto etichettato, settando P4 bianco non deve rendere P un punto di 
interruzione. 
Il problema maggiore degli algoritmi di iterattiva erosione dei contorni è la complessità 
in termini di tempo che risulta O(wN) dove w è lo spessore della linea e N è il numero 
totale dei pixel che compongono l’immagine. Siccome anche lo spessore della linea è 
direttamente proporzionale alla risoluzione dell’immagine, la complessità totale di 
tempo è di ordine cubico rispetto alla risoluzione. Inoltre questi metodi sono inclini alla 
distorsione analizzando le giunzioni come “X” e “T” (Naccache e Shingal) come 
esposto in figura 2. Nessuno di questi metodi è adatto per lavorare in diversi casi a 
causa della sua scarsa accuratezza nel rilevare le immagini. Benché l’algoritmo di 
Montanari sia veloce, rimane la distorsione delle forme nelle giunzioni che è un difetto 
dovuto alla sua natura iterattiva. Metodi similari di fine regolazione delle tecniche di 
erosione iterattiva dei contorni  includono la giustificazione delle regole di etichettatura 
(Tamura) e la variazione della dimensione delle finestre di analisi. Deutsch
19
 per 
esempio usa finestre non quadrate mentre O’Gordam
20
 generalizza il metodo per 
finestre di dimensioni k x k. Comunque queste modifiche comportano solo un piccolo 
incremento delle performance in termini ti tempo e della qualità delle figure 
riconosciute. Per maggiori dettagli sugli algoritmi Tamura, Smith e Lam forniscono 
consistenti supporti. 
Pfaltz and Rosenfeld definiscono lo scheletro con un metodo più formale, sulla base del 
quale la “trasformazione della distanza” (Distance Transform , Rosenfeld and Pfaltz
21
) 
viene introdotta alle procedure thinning. Rosenfeld and Pfaltz definiscono la 
trasformazione della distanza delle immagini binarie come la sostituzione di tutti i 
singoli pixel con un numero che indica la minima distanza del punto dal punto bianco 
più vicino. 
                                                 
19
 Deutsch ES. Thinning algorithm on rectangular , hexagonal, and triangular arrays. Communications 
of the ACM 1972; 15:827-837. 
20
 O’Gordam L. k x k thinning Computer Vision , Graphics and Image Processinf 1990; 51:195-215. 
21
 Rosenfeld A and Pfaltz JL. Distance functions in digital pictures. Pattern Recognition 1968; 1: 33-61 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         14 
Le distanze tra due punti è definito dal 
numero di pixel nelle più piccole 4 connesse 
catene tra i punti.Questa trasformazione è 
calcolata valutando la funzione in 
successione con una ricerca sull’immagine 
seguita da una secondo passaggio di ricerca 
in senso inverso. 
Una volta che le distanze sono calcolate un’ 
operazione di ricerca dei massimi relativi 
viene usata per la ricerca dello scheletro. 
E’ stato dimostrato che risulta essere il 
minimo numero di punti necessario per ricostruire esattamente l’immagine di partenza. 
La trasformazione delle distanze e lo scheletro ottenuto sono rappresentate nella figura 
3. Anche Haralick e Shapiro hanno presentato un’approfondita analisi 
dell’implementazione del metodo con la trasformazione delle distanze tenendo in 
considerazione sia operazione ricorsive che non-ricorsive. 
Il principale problema di questi algoritmi, come si vede nella figura 3(c), è che lo 
scheletro risulta spesso non connesso, specialmente in caso di giunzioni. Comunque il 
tempo di elaborazione è direttamente proporzionale al numero di pixel presenti 
nell’immagine, quindi la velocità risulta solo di ordine quadratico rispetto alla 
risoluzione. Questo metodo , risulta quindi più veloce dei metodi iterattivi che avevano 
una relazione cubica di complessità in termini di tempo. 
In modo similare alla trasformazione delle distanza per immagine binarie, Peleg and 
Rosenfeld definiscono la “Max Medial Axis Transform” o MMMAT in breve, per le 
immagini a toni di grigio . La connettività dello scheletro ricavato non è ancora 
garantita, nonostante che la complessità venga incrementata al livello dei metodi 
iterattivi . 
Un differente ma veloce algoritmo per il riconoscimento di linee in immagini in bianco 
e nero viene proposto da Watson
22
. Viene usato un filtro Gaussiano per modificare 
                                                 
22
 Watson LT, Arvid K, Ehrich RW,Haralick RM, Extraction of line and region from greytone line 
drawing images. Pattern Tecognition 1984; 17: 493-507. 
 
 
Figura 2 Distorsioni alle giunzioni 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         15 
l’immagine prima che le linee siano tracciate tra i picchi che sono supposti essere i punti 
dell’asse medio della linea. 
 
••• 111 ---
••••• 12221 -•-•-
••••• 12321 -----
••••••• 1234321 -------
••••••••••• 11234543211 -----------
••••••••••••• 1223456543221 ------•------
••••••••••••••• 123223454322321 --•---------•--
••••••••••••••••• 12321123432112321 --•-----------•--
••••• ••••• ••••• 12321 12321 12321 --•-- ----- --•--
••••• ••••• ••••• 12321 12321 12321 --•-- --•-- --•--
•••• ••••• •••• 1221 12321 1221 --•- --•-- -•--
••••• ••••• ••••• 12321 12321 12321 --•-- --•-- --•--
•••• ••••• •••• 1221 12321 1221 ---- ----- ----
••••••••••••••••••••••••••• 112332111112343211111233211 -------------------------
••••••••••••••••••••••••••••• 12234432222234543222223443221 ----••--•••---•---•••--••-
••••••••••••••••••••••••••••• 12234432222234543222223443221 ----••--•••---•---•••--••-
••••••••••••••••••••••••••• 112332111112343211111233211 -------------------------
•••• ••••• •••• 1221 12321 1221 ---- ----- ----
••••• ••••• ••••• 12321 12321 12321 --•-- --•-- --•--
•••• ••••• •••• 1221 12321 1221 --•- --•-- -•--
••••• ••••• ••••• 12321 12321 12321 --•-- --•-- --•--
••••• ••••• ••••• 12321 12321 12321 --•-- ----- --•--
••••••••••••••••• 12321123432112321 --•-----------•--
••••••••••••••• 123223454322321 --•---------•--
••••••••••••• 1223456543221 ------•------
••••••••••• 11234543211 -----------
••••••• 1234321 -------
••••• 12321 -----
••••• 12221 -•-•-
••• 111 ---
            (a)                                                  (b)                                                (c) 
 
Figura 3 Esempio di trasformazione sulle distanze. (a) image. (b) trasformazione. (c) scheletro 
 
Sebbene esso riesca a distinguere le linee dalle regioni, il filtro risulta difficile da 
determinare trovando un compromesso tra linee e regioni. Quindi risulta di difficile 
applicazione per la vettorializzazione di disegni tecnici ed ingegneristici in generale. 
Comunque nonostante il metodo sia lineare rispetto al numero dei pixel se uno spessore 
del filtro è stato determinato, risulta anche di ordine cubico rispetto alla risoluzione se il 
filtro cambia al variare della risoluzione dell’immagine. 
Combinando i punti dello scheletro ottenuto da Rosenfeld e Pfaltz, con quelli prodotti 
dai semplici metodi convenzionali di erosione dei contorni, Davies e Plummer 
definiscono uno “scheletro adeguato” (adeguate skeleton) e sviluppano un metodo 
composito. La combinazione porta ad uno scheletro con al massimo due pixel di 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         16 
spessore che viene in un secondo momento assotigliato ad uno di spessore unitario. 
L’algoritmo ottiene degli scheletri più accurati rispetto ai metodi convenzionali di 
erosione dei contorni ma richiede più tempo  per elaborare i processi aggiuntivi. 
Generalmente, l’obiettivo delle metodologie thinning è quello di ridurre il volume dei 
dati da analizzare, fino a quando rimane solo la struttura topologica della forma la cui 
grandezza e il cui orientamento rimangono invariati. Il risultato di solito necessita di 
processi aggiuntivi. Molti degli algoritmi sono in grado di mantenere la connetività. 
Comunque lo svantaggio maggiore è la notevole complessità in termini di tempo, la 
perdita di informazioni sulla forma (come la perdita degli spessori), la distorsione alle 
giunture, e la creazione di falsi e imperfetti rami. Nonostante  tutto essi possono essere 
usati nella vettorializzazione di disegni, ma la loro principale applicazione è nel campo 
degli OCR, in cui le dimensione delle immagini sono di solito ridotte  e la dimensione 
delle linee non risulta un parametro critico. 
Valutazione sulle performance dei metodi thinning sono state studiate da Lee
23
, Lam
24
, 
Suen, Jaisimha
25
 e Cordella e Marcelli
26
. Differenti algoritmi possono essere adatti a 
differenti applicazioni, esempio OCR o riconoscimento di linee. Per esempio, Lee 
giudica l’algoritmo di Tamura buono dal punto di vista della velocità di elaborazione, 
discreto nel mantenimento delle connettività ma povero nella qualità dello scheletro, per 
l’algoritmo di Naccache e Shinghal invece ne fornisce buone impressioni per tutte e tre 
                                                 
23
 Lee L, Lam L,  Suen CY.Performance Evaluation of Skeletonization Algorithm for Document Image 
Processing. In Proceedings of the 1
st 
Inernational Conference on Document Analysis and Recognition, 
Saint-Malò, France, 1991, pp 260-271. 
24
 Lam L, Suen CY. Evaluation of Thinning Algorithm from an OCR Viewpoint. I Proceedings of the 
2
nd
 Internationale Conference on Document Analysisi and Recognition, Tsukuba, Japan, 1993, pp 287-
290. 
25
 Jaisimha MY, Haralick RM, Dori D, A Methodology for the Characterization of the Performance of 
thinning Alghorithms. In Proceedings of the 2
nd
 International Conference on Document Analysis and 
Recognition , Tsukuba, Japan, 1993, pp282-286.  
26
 Cordella LP, and Marcelli A. An Alternative Approach to the Performance Evaluation of Thinning 
Algorithms for Document Processing Application. In: Kasturi R, Tombe K (eds). Graphics recognition – 
Methods and Apllications (Lecture Notes in Computer Science, vol 1072). Springer, Berlin, 1996, pp 13-
22 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         17 
le caratteristiche.da sottolineare che la sua analisi è sviluppata solo considerando 
applicazioni OCR. 
La scheletro prodotto da queste metodologie thinning rimane comunque mappato per bit 
quindi necessita di essere vettorializzato per applicazioni successive. Lo scheletro di 
larghezza unitaria (1 pixel) viene esaminato e connesso in una catena da un processo di 
riconoscimento delle linee. A questo punto può essere applicato un algoritmo di 
poligonalizzazione per convertire la catena di pixel trovati in una polilinea (o in una 
singola barra – una “monolinea”), che contenga solo i punti critici. I metodi di 
poligonalizzazione vengono affrontati nel paragrafo 1.2.7 . 
 
 
2.1.3 Contour based Methods 
Mirando a diminuire il carico computazionele dei metodi thinning, un altro gruppo di 
algoritmi di vettorializzazione tenta di ridurre il volume di dati prima di cercare i punti 
dell’ asse medio delle figure. L’idea generale è quella di trovare il contorno delle figure 
il loro bordo e poi calcolare i punti medi come i punti a metà strada tra due punti apposti 
nel contorno tramite linee parallele. Questo tipo di algoritmo ricava e semplifica 
simultaneamente i punti che si trovano sull’asse medio. Questa è la differenza dai 
metodi thinnig che cercano le linee dopo che tutti i punti medi sono stati analizzati. Le 
due principali operazioni computazionali di questi metodi sono il riconoscimento dei 
bordi e la successiva poligonalizzazione dei punti trovati. La complessità in termini di 
tempo nel trovare i confini delle figure è solamente lineare alla quantità dei pixel 
presenti, quadratica rispetto alla risoluzione dell’immagine. La poligonalizzazione è 
lineare ai pixel presenti al contorno, come discusso al paragrafo 2.1.2, quindi questo 
gruppo di metodologie presenta una complessità quadratica e risultano molto più veloci 
dei metodi thinning. Da sottolineare anche il fatto che gli spessori delle linee in questi 
cosi sono molto più semplici da ricavare ,cosa che risulta molto importante per 
interpretazioni di livello superiore delle immagini tecniche. Il rilevamento dei contorni è 
un’operazione che presenta una certa maturità nel campo della vettorializzazione e 
alcuni esempi di queste metodologie possono essere ritrovati nei volumi di Heralick and 
Shapiro o di Nalwa. 
Capitolo 1 – La Vettorializzazione 
Vettorializzazione a Pixel Sparsi - SPVector                                                         18 
Quando i contorni sono stati individuati e poligonalizzati, il punto medio dell’asse tra 
due punti paralleli ai due bordi estremi è definito da Jimenez e Navalon 
27
 come il punto 
medio della perpendicolare proiettata da un lato all’altro, come esposto in figura 4(a) e 
4(b). Quando il contorno è ben delineato (ricordo che è un vettore) una ricerca in senso 
lineare trova il punto più vicino nel bordo opposto dell’oggetto ed una perpendicolare 
viene proiettata da un punto verso l’altro. Continuando i contorni sono più facili da 
ricavare semplicemente seguendo il contorno fina a che un altro punto non viene 
trovato. 
Il problema con tutti gli algoritmi di questo tipo è il loro comportamento in prossimità 
di giunzioni.Ci sono due problematiche principali associate alle giunzioni. 
La prima è rappresentata nella Figura 4(c) in cui un’intersezione con un piccolo angolo 
di incidenza forma una giunzione, che molto probabilmente non verrà riconosciuta 
durante la ricerca. La seconda  esposta dalla figura 4 (d) viene incontrata in una 
giunzione a forma di croce. Unire le linee che si incontrano risulta un problema 
corposo. E’ importante che l’algoritmo sia robusto e capace di adeguarsi a tutte le 
dimensioni di linee presenti  senza mal giudicare le giunzioni e produrre un scheletro 
non corretto. Per questo motivo non è indicato per essere usato nella vettorializzazione 
di curve e di linee che si incrociano spesso. 
                                                 
27
 Jimenez J, and Navalon JL. Some Experiments in Image Vectorization. IBM Journal of Research. 
Computer Graphics and Image Processing 1981; 15: 136-153. 
 
 
 
 
 
 
 
 
           (a)                            (b)                               (c)                                   (d) 
Figura 4 Metodo per ricavare il punto medio tra due punti su contorni opposti. (a) contorni paralleli (b) 
contorni quasi paralleli (c) giunzione non rilevata (d) confuzione alla giunzione