Quando guardiamo un'immagine bidimensionale di qualsiasi scena tridimensionale (in un dipinto, una fotografia, uno schermo monitor), ci sembra che ci siano direttamente tutti quegli oggetti che potremmo vedere se osservassimo direttamente la stessa scena nella vita. Nel frattempo, tutto ciò che ci viene effettivamente dato in un'immagine bidimensionale è campo visibile, che è solo alcuni funzione di distribuzione della luminositào colorisu un piano bidimensionale: f(x, y) dove xe y- Coordinate cartesiane che descrivono il piano dell'immagine.
Inoltre, se ti avvicini allo schermo del monitor del computer, puoi vedere che l'immagine sullo schermo non è in realtà liscia e continua, ma è un discreto "mosaico" costituito da rettangoli colorati separati disposti in una matrice rettangolare regolare. Ecco cos'è immagine digitale... Da un punto di vista matematico immagine digitaleè una matrice bidimensionale Im di dimensione (DimXDimY), dove x è un numero intero da 0 a DimX– 1 che descrive il numero di un elemento nella riga della matrice, y è un numero intero da 0 a DimY– 1 che descrive il numero di riga della matrice in cui si trova questo elemento. In questo caso, viene chiamato l'elemento dell'immagine digitale stessa (la cella di una matrice rettangolare) pixel(pixel, elemento dell'immagine). Nel caso più semplice, ogni pixel Im ha un valore intero scalare proporzionale al valore della funzione di distribuzione della luminosità f(x, y) in un dato punto dell'aereo.
Nella fig. 1.1.1 a sinistra è un'immagine del volto di una donna presentato come immagine, ea destra è un frammento ingrandito dell'immagine dello stesso volto (occhio destro), dove per ogni elemento dell'immagine è indicato il valore numerico del pixel corrispondente. Gli elementi chiari dell'immagine corrispondono a b divalori più alti della matrice, scuro - valori più bassi. L'immagine digitale non contiene altre informazioni.
@Figura. 1.1.1 Immagine digitale come matrice bidimensionale di intensità
Quando si inizia a studiare la visione artificiale, è necessario comprendere chiaramente che solo ed esclusivamente una matrice bidimensionale di numeri di un formato o di un altro viene memorizzata in un computer come immagine digitale. Qualsiasi altro dato che vorremmo estrarre dall'immagine (forme, linee, oggetti, dimensioni, il contenuto del testo visualizzato, ecc., Ecc.) - può essere ottenuto solo come risultato dell'applicazione di una serie di procedure di elaborazione e analisi dell'immagine che dobbiamo programmare noi stessi o utilizzare procedure già pronte disponibili in noti pacchetti software di analisi delle immagini. Allo stesso tempo, per risolvere semplici problemi di visione artificiale, probabilmente si troveranno strumenti già pronti nelle librerie standard di procedure di elaborazione delle immagini, per risolvere problemi più complicati sarà necessario combinare alcune procedure già pronte, e per molti compiti abbastanza "ordinari" che la visione umana "biologica", sembrerebbe , risolve facilmente e in modo giocoso, la visione artificiale non ha ancora soluzioni e continua a cercarle. Dopotutto, usando la sua visione naturale, una persona può facilmente navigare in qualsiasi ambiente, riconoscere oggetti, scegliere un percorso, guidare un'auto e molto, molto altro ancora. Perché un computer che riceve un'immagine da una videocamera non è in grado di fare tutto questo? Forse è la struttura dell'occhio umano?
In effetti, l'occhio umano, come una videocamera, forma solo un "campo visibile" simile a un'immagine digitale. In questo caso, il sistema ottico, costituito da una pupilla e una lente, proietta un'immagine bidimensionale sulla retina, dove le cellule fotosensibili (“bastoncelli” e “coni”) convertono l'immagine risultante in impulsi nervosi. E solo dopo, un complesso meccanismo di elaborazione delle informazioni ricevute, funzionante nella parte corrispondente del nostro cervello, interpreta questi impulsi come un'immagine della scena visibile che comprendiamo. Pertanto, negli esseri umani, la funzione di "vedere" è svolta non solo dall'occhio, ma dal sistema "occhio + cervello" ("sensore + computer"). Sono gli algoritmi di elaborazione delle informazioni integrati nel cervello che consentono a una persona di capire ciò che vede. Il ruolo di questi algoritmi incorporati può essere illustrato dal seguente esempio.
Quando, a metà del XX secolo, i chirurghi oftalmologici impararono a eseguire operazioni sul cristallino, molte persone cieche dalla nascita ebbero l'opportunità tecnica di vedere la loro luce. Cioè, dopo una tale operazione in una persona che fino a quel momento era cieca (la luce semplicemente non passava attraverso l'obiettivo), ha iniziato a formarsi un'immagine sulla retina ei segnali corrispondenti hanno iniziato ad entrare nel cervello esattamente allo stesso modo delle persone sane. Purtroppo, in questo caso, "vedere la luce" non significava "iniziare a vedere". Come la storia ha dimostrato, la maggior parte dei pazienti adulti "tecnicamente illuminati" non è mai stata in grado di ottenere risultati più significativi nel campo visivo del riconoscimento di semplici forme geometriche - e anche questo ha richiesto loro un serio impegno cosciente. Il riconoscimento delle persone dai loro volti e l'orientamento nello spazio sono rimasti compiti travolgenti per loro. Il fatto è che quei meccanismi incorporati di analisi visiva "automatica" che si sviluppano nelle persone nella prima infanzia non sono stati sviluppati in questi pazienti in modo tempestivo, e si sono trovati nella posizione di un computer con un dispositivo per l'immissione di immagini, ma privo del software necessario per la sua analisi.
Per convincerci finalmente della complessità del compito che ci attende di analizzare un'immagine che è un array bidimensionale di dati numerici, proviamo a metterci al posto di un programma per computer che si occupa di numeri astratti. Per fare ciò, cambieremo mentalmente la modalità di percezione dell'immagine - la trasferiremo dal dominio visivo a quello tattile. Immaginiamo un array bidimensionale di valori di intensità come una scacchiera, la cui dimensione è uguale alla dimensione dell'immagine (DimXimDimY), e una colonna è bloccata al centro di ogni cella, la cui altezza è proporzionale al valore del pixel corrispondente nell'immagine. In altre parole, consideriamo un'immagine bidimensionale come una sorta di superficie tridimensionale convenzionale. Nella fig. 1.1.2 a sinistra, un frammento del viso di una donna è mostrato come immagine, ea destra è raffigurato come un rilievo pseudo-tridimensionale.
@Figura. 1.1.2. Immagine digitale come rilievo pseudo-tridimensionale
Ora immagina che, senza guardare l'immagine, devi sentire il corrispondente "sollievo" e cercare di determinare cosa rappresenta esattamente questo "sollievo": una casa, un cane o un occhio umano? Gli esperimenti mostrano che la persona media non è in grado di far fronte a un simile compito. Anche il riconoscimento delle forme geometriche più semplici in una tale rappresentazione "in rilievo" sarà associato a uno sforzo considerevole e richiederà lo sviluppo cosciente di una speciale abilità, strategia e algoritmi per sentire. Questa è, nonostante l'apparente semplicità dell'oggetto "immagine digitale", la vera complessità dei compiti del computer e della visione artificiale.
UDC 004932: 621.396
T.M. VLASOV, V.G. KALMYKOV
ALGORITMO E PROGRAMMA PER IL RICONOSCIMENTO DEI PROFILI DI IMMAGINE COME SEQUENZA DI INTERVALLI DI LINEE DIGITALI
Abstract: Nel lavoro dato viene considerato l'algoritmo del riconoscimento del segmento di linea diretta digitale nei contorni delle immagini binarie e l'implementazione software dell'algoritmo. L'utilizzo di questo algoritmo per elaborare le immagini risulterà in una descrizione più naturale ed economica rispetto ai modi noti di descrizione delle immagini. L'algoritmo considerato e l'implementazione del software possono essere utilizzati anche per la descrizione dei contorni durante l'elaborazione delle immagini a mezzitoni ea colori.
Parole chiave: immagine, contorno, segmenti retti digitali, algoritmo, programma.
Abstract: Al dato del robot viene indotto l'algoritmo per la creazione delle immagini in linee rette digitali ai contorni delle immagini binarie, così come il software per l'implementazione dell'algoritmo. L'algoritmo per l'elaborazione dell'immagine del prodotto prima della descrizione dell'immagine sarà più naturale ed economico, a seconda di come viene elaborata l'immagine. L'algoritmo proprietario e l'implementazione del software possono essere utilizzati per codificare i contorni nel processo di raffinamento di immagini nuove e colorate. Parole chiave: immagine, contorno, azionamenti diretti digitali, algoritmo, programma.
Riassunto: questo articolo considera un algoritmo per il riconoscimento di segmenti di linee digitali nei contorni di immagini binarie e l'implementazione software dell'algoritmo. L'uso di questo algoritmo nell'elaborazione delle immagini si tradurrà in una descrizione delle immagini più naturale ed economica rispetto ai metodi noti. L'algoritmo considerato e l'implementazione del software possono essere utilizzati anche per descrivere i contorni durante l'elaborazione di immagini in scala di grigi ea colori. Parole chiave: immagine, contorno, segmenti di linee digitali, algoritmo, programma.
1. Introduzione
L'analisi strutturale dei contorni delle immagini come sequenze di segmenti di linea e archi di curve è uno dei compiti principali nell'elaborazione delle immagini con l'obiettivo di interpretarli in sistemi di intelligenza artificiale.
Nella maggior parte dei casi, un'immagine può essere vista come parte di un piano, suddivisa in regioni con parametri costanti o variabili, ad esempio densità ottica, colore, trama, definizione dello sfondo e oggetti immagine. Una proprietà integrale di ciascuna di queste aree è il suo confine, cioè il contorno è una sequenza semplicemente connessa composta da segmenti di linea e archi di curve. Durante l'elaborazione bitmap i contorni degli oggetti sono solitamente evidenziati. Tuttavia, i contorni degli oggetti, presentati come un insieme di singoli pixel di confine, non sono molto adatti per ulteriori elaborazioni, poiché non esprimono sufficientemente la sua essenza geometrica.
Il riconoscimento dei contorni dell'immagine sotto forma di una sequenza di segmenti di linea retta può essere considerato uno dei compiti principali nel processo di elaborazione di un'immagine raster. La soluzione del problema di rappresentare il contorno sotto forma di una sequenza di segmenti di retta consente di ottenere una descrizione dell'immagine in forma compatta, naturale per la percezione umana, invariante rispetto alle trasformazioni affini, conveniente, in particolare, per l'elaborazione da reti neurali. I segmenti di linea sono i principali elementi del profilo. L'arco di una curva è anche spesso sostituito da una linea spezzata inscritta in esso, sia nei fondamenti dell'analisi matematica che in un gran numero di applicazioni pratiche.
Metodi e algoritmi noti, in particolare quelli proposti nel lavoro, consentono di ottenere una soluzione approssimativa, non accettabile per tutte le applicazioni.
In questo articolo, consideriamo il riconoscimento del contorno di un'immagine binaria come una sequenza di segmenti di linee digitali senza perdita di informazioni.
2. Contorno come una sequenza di segmenti di linee rette digitali
NEL questa sezione l'analisi strutturale dei contorni dell'immagine è considerata come una sequenza di segmenti di rette digitali, che sono i dati iniziali per la segmentazione del contorno in archi di curve digitali e segmenti di rette digitali.
Ci limitiamo a considerare le immagini binarie, i cui oggetti sono completamente determinati dai loro contorni di delimitazione. Archi di curve digitali, così come segmenti di linee digitali, si formano durante la discretizzazione di immagini contenenti contorni formati da segmenti di linea e archi di curve.
Le caratteristiche dei segmenti di linea e degli archi delle curve si perdono durante la trasformazione. Considerando l'immagine campionata con un ingrandimento sufficiente, è spesso difficile riconoscere singoli segmenti di linea e archi di curve in una sequenza
segmenti di linea verticali e orizzontali. Ulteriori difficoltà sorgono durante l'elaborazione a causa del fatto che le linee di contorno - linee matematiche senza spessore - vengono visualizzate sullo schermo del monitor da sequenze collegate di pixel, cioè linee visive aventi uno spessore.
Per eliminare i problemi che ne derivano, considereremo l'immagine ottenuta dall'originale come risultato del campionamento come un complesso cellulare bidimensionale. In questo caso
i pixel sono elementi bidimensionali di questo complesso cellulare. Oltre ai pixel, ci sono crepe e punti. Cracky è
lati pixel che sono elementi unidimensionali. I punti sono i punti finali delle crepe e i punti d'angolo dei pixel. I punti sono elementi a dimensione zero. Così
pertanto, nel caso in esame, il contorno dell'oggetto è una sequenza chiusa collegata di crepe del contorno che confinano tra i pixel dell'oggetto e lo sfondo. Un contorno può essere descritto come una sequenza di coordinate di punti interi,
delimitazione di crepe di contorno. Come mostrato in, rappresenta il piano dell'immagine come
il complesso cellulare offre molti vantaggi. In particolare, il confine della regione diventa una curva sottile con area zero.
Nella fig. 1 mostra un esempio del contorno originale di un oggetto formato da un arco di una curva e un segmento di linea retta, nonché il suo equivalente digitale come una sequenza di crepe. I punti appartenenti a fessure in direzioni diverse sono numerati. Come nelle opere, per elemento L si intende una sequenza connessa di fessure della stessa direzione, emergenti da un certo punto e terminanti con una fessura della stessa direzione o perpendicolare. Nella fig. 1 mostra una delle possibili partizioni del contorno in elementi a L, che sono formati da crepe tra i punti: (0-2), (2-4), (4-6), (6-8), (8-9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25), (25-27 ), (27-0). Ogni elemento L è caratterizzato dai seguenti parametri: direzione relativa al suo punto iniziale g (preso g \u003d 0 - per la direzione verso l'alto, 1 - a destra, 2 - in basso, 3 - a sinistra); l - il numero di crepe nella direzione g (! \u003d 1,2, ...); la direzione dell'ultima crepa q rispetto alla direzione g delle crepe precedenti (q \u003d -1 - l'ultima crepa è diretta a sinistra rispetto alla direzione g, +1 - a destra, 0 - coincide con la direzione g). Il numero di crepe l sarà convenzionalmente chiamato "lunghezza" dell'elemento b. Per l'elemento b (0-2) g \u003d 0,! \u003d 3, q \u200b\u200b\u003d + 1. Per l'elemento b (27-0) g \u003d 3, \u003d 1, q \u003d 0.
Il metodo di selezione di segmenti di linee digitali in un contorno utilizza la seguente proprietà di una sequenza di elementi L che formano un segmento. Una tale sequenza include L -elementi con gli stessi valori di g, q; le loro lunghezze assumono valori! +1. inoltre
l'alternanza di b -elementi di lunghezze! + 1 è determinata dalla frazione continua ottenuta dividendo interi n \u003d Ax \u003d | x1 - x2 | e m \u003d Ay \u003d | y1 - y2 \\, dove (x13y1), (x2, y2) sono le coordinate dell'iniziale
ei punti finali del segmento di linea: o
Assumiamo per definizione che n\u003e m Come segue dalla formula (1), l - la parte intera della divisione di n per m - corrisponde in un segmento di una retta digitale al numero di l crepe consecutive di una direzione. Insieme alla fessura perpendicolare adiacente, formano l'elemento L di lunghezza!. k1 elementi b consecutivi di lunghezza le un elemento b di lunghezza! +1 (o k1 elementi b consecutivi di lunghezza +1 e un elemento b di lunghezza!) formano un elemento K1 di "lunghezza" k1 (per analogia con la "lunghezza "Elemento B). Un elemento b che differisce in lunghezza di 1 da elementi b consecutivi sarà chiamato elemento b modificato di questo elemento K1. Allo stesso modo, k2 elementi K1 consecutivi di "lunghezza" k1 e un elemento K1 di "lunghezza" k1 +1 (o k2 elementi K1 consecutivi di "lunghezza" k1 +1 e un elemento K1 di "lunghezza" k1) formano K2- elemento di "lunghezza" k1. Così
k + k 2 + k z + ... + kg
ulteriormente fino a quando i membri della frazione continua sono esauriti. Elemento K1 (generalmente elemento K-1), che differisce in lunghezza di 1 dai successivi elementi K1 (elemento Kg-1), chiameremo l'elemento K1 modificato (elemento Kg-1) di questo elemento K2 (Kg -elemento). Quindi, tutti
un segmento di linea retta digitale corrisponde a una frazione continua, i cui elementi determinano la struttura di questo segmento.
Nel contorno in Fig. 1 è possibile selezionare i seguenti segmenti di linee rette digitali: 0-3, 3-9, 910, 10-17, 17-0.
3. Selezione di segmenti di una linea digitale in un contorno
Quando si elaborano i contorni delle immagini, in particolare le immagini binarie, nella sequenza di crepe che formano il contorno, è necessario selezionare le parti della sequenza che formano i segmenti di linea. Questo problema può essere considerato come il problema di determinare gli elementi della frazione continua mediante la sequenza di elementi L del contorno. Questo compito è inverso al problema di determinare la struttura di un segmento di retta dalla sequenza di termini della frazione continua, ottenuta come rapporto tra le differenze tra le coordinate dell'inizio e della fine del segmento.
Il metodo per selezionare i segmenti di una linea retta digitale consiste nell'eseguire sequenzialmente le seguenti azioni.
1. Isolamento di una sequenza di elementi L in una sequenza di fessure. Questa azione soddisfa la definizione di una parte intera! frazione continua (1).
2. Isolamento della sequenza di elementi Kr con r \u003d 1 nella sequenza di elementi L, e uno degli elementi L di ciascun elemento K1 deve contenere 1 fessura in più o in meno degli altri. Questa azione corrisponde alla definizione del k1 -esimo elemento della frazione continua (1). Dopo la sua esecuzione, il valore di r dovrebbe essere aumentato di 1.
3. Selezione di una sequenza di Kg-elementi in una sequenza di Kg-1 -elementi,
inoltre, uno degli elementi da Kg-1 di ciascun elemento da Kg deve contenere un elemento K-2 in più o in meno degli altri. Questa azione corrisponde alla definizione di k (il th elemento della frazione continua (1). Dopo la sua esecuzione, il valore di r deve essere aumentato di 1.
4. Il paragrafo 3 viene ripetuto fino a quando è ancora possibile dai successivi Kg-elementi
modulo Km -elemento.
5. Determinare i punti di confine tra due elementi L adiacenti che non sono inclusi nello stesso elemento Kr. Questi punti sono i punti finali dei segmenti di linea digitale che formano il contorno.
Considera un algoritmo per separare segmenti di linea in una sequenza di elementi L
Sia [b5 (fs, gs, qs)); 5 \u003d 0.1, ..., t è una sequenza di elementi L che formano un contorno; x5, y5- coordinate dell'inizio dell'e-esimo elemento b; [xy, yy); y \u003d; r \u003d 0,1, ...,!; !< £ - множество
punti di interruzione del contorno. I punti di interruzione definiscono i punti finali dei segmenti di linea che formano il contorno. Trovare punti di interruzione significa definire i segmenti di linea che formano un contorno.
Ogni segmento preso in considerazione è caratterizzato da un elemento Kr, oltre che da una catena
frazione. Al momento iniziale di riconoscimento di un segmento di retta, gli elementi della corrispondente frazione continua sono uguali a 0. Il segmento può essere considerato riconosciuto se vengono riconosciuti i parametri dell'elemento Kr, compreso il suo ordine r ei valori degli elementi della corrispondente frazione continua.
1. Condizioni iniziali.
Vengono fornite le sequenze [b5 (f5, gs, qs)) e (x5, y5).
È necessario trovare le coordinate dei punti di interruzione | x;., Y,).
k0p: \u003d 0, k1p: \u003d 0, k2p: \u003d 0, ..., kr: \u003d 0 sono i valori di lavoro degli elementi della frazione continua.
Prendiamo il punto 5 \u003d 0 come punto iniziale del primo segmento; i \u003d 0; io \u003d 0.
2. Prendi il primo elemento b nella sequenza come l'inizio del primo segmento di linea. Il suo punto iniziale è x5, y. La lunghezza / \u003d / 0 è anche il valore del primo elemento della frazione continua.
5: \u003d 5 + 1; k1p: \u003d k1p + 1.
3. Verificare la presenza del successivo elemento L, se si forma, insieme al precedente elemento K0.
3.1. Se ((q3 \u003d\u003d q3-1) && (q3 \u003d\u003d 73-1) && (4 \u003d\u003d / 3-1)), allora la continuazione dell'elemento Kg k0p: \u003d k0p +1; 5: \u003d 5 + 1; e continuazione di un segmento di linea. Vai al passaggio 3.
3.2. Se ((q3 q3-1) || (q3 q73-1) 11 (| / e - / є-1!\u003e 1)), la fine del segmento di linea. Vai al passaggio 5.
3.3. Se ((& \u003d\u003d 9s + 1) && (% \u003d\u003d 7s + 1) && ((/ 3 + 1 \u003d\u003d / 3 + 1) 1! (/ 3 - 1 \u003d\u003d / 3 + 1))), quindi il completamento dell'elemento K0; Ї \u003d Ї + 1.
4. Verifica della continuazione / completamento di K (-element.
4.1. Se (k \u003d\u003d 0), allora k ^ \u003d k ^; cr: \u003d 0; k ^ 1p: \u003d k1 + 1p + 1; 5: \u003d 5 +1; l'inizio dell'elemento Km.
Vai al passaggio 3.
4.2. Se ((kif 0) && (k \u003d\u003d k ^)), allora k ^ 1p: \u003d k ^ 1p + 1; 5: \u003d 5 + 1; continuazione di Ki + 1 -elemento. Vai al passaggio 3.
4.3. Se ((k (Ф 0) && ((k + 1 \u003d\u003d k1p) 11 (k1-1 \u003d\u003d k ^))), allora Ї: \u003d +1; fine dell'elemento Km.
Vai al passaggio 4.
4.4. Se ((^ φ0) && (| k - k1p |\u003e 1)), la fine del segmento è una linea retta per il passaggio 5.
5. Fine del segmento.
X] \u003d Xs; y \u003d Uz; k1p: \u003d 0, k2p: \u003d 0,., kir: \u003d 0; k: \u003d 0, k2: \u003d 0,., k: \u003d 0.
Se (s< S), то s:= s +1; переход к п. 2.
Altrimenti, la fine della sequenza di L -elementi. La fine dell'algoritmo.
L'algoritmo proposto, infatti, trova gli elementi della frazione continua e per ogni elemento Kt ottenuto e verifica se la frazione continua dell'elemento Kt di nuova costruzione è adatta a quella già costruita.
4. Il programma per la selezione dei segmenti di una linea digitale
Come puoi vedere dalla descrizione dell'algoritmo, contiene un numero significativo di salti condizionali, il cui utilizzo contraddice le raccomandazioni programmazione strutturata a causa delle difficoltà incontrate nel debug dei programmi. Inoltre, il numero di parametri Kt in anticipo
è impossibile determinarlo, poiché la variabile t non è limitata in anticipo. Limita il valore di t
Ciò significa limitare in anticipo le dimensioni dell'immagine. L'implementazione del software, in particolare il debugging dell'algoritmo proposto con mezzi banali, per i motivi indicati, è notevolmente difficile. È possibile ridurre le difficoltà di sviluppo e debug di un'implementazione software se si utilizzano moderni strumenti di programmazione orientata agli oggetti.
L'algoritmo proposto è implementato sotto forma del programma LINESEGM, che fa parte del laboratorio pacchetto software sull'elaborazione delle immagini nell'ambiente Visual C ++.
Come informazione iniziale, il programma LINESEGM utilizza le sequenze di elementi L costruiti per ciascuno dei contorni dell'immagine elaborata.
Il risultato del programma è una sequenza collegata di segmenti di linea retta digitali costruiti per ogni contorno, rappresentati dalle coordinate dei punti finali dei segmenti.
Come si può vedere dall'algoritmo, le operazioni di costruzione di Kt -elementi da Kt-l -elementi
sono gli stessi per tutti i valori di t. Nota che valore iniziale t \u003d 0 e nel corso dell'operazione dell'algoritmo viene incrementato ogni volta di 1. La classe speciale CKForLn include metodi corrispondenti alle operazioni dell'algoritmo. Nel processo di esecuzione del programma che implementa l'algoritmo per ogni aumento di t di 1, viene creato un nuovo oggetto contenente funzioni che eseguono le operazioni dell'algoritmo per ogni valore di t.
Considerando che a livello zero gli elementi K0 non sono formati da elementi K, ma da L -
elementi, per implementare l'algoritmo a livello zero, è stata creata una modifica speciale della classe CKForLn: la classe Cmini.
Il principio di funzionamento del programma è che per ogni valore di t nel programma viene implementato un oggetto della classe CKForLn di livello t-esimo, contenente funzioni che determinano i parametri dell'elemento Kt. I parametri iniziali dell'elemento Kt sono già i parametri
l'elemento Kt-l completato, i cui parametri sono stati determinati dall'oggetto della classe CKForLn t-1
Livello wow.
Gli oggetti della classe CKForLn vengono implementati quando si presentano le condizioni, vale a dire: la necessità di costruire un elemento K del livello successivo, - e si accumulano in uno speciale array dinamico. Un oggetto a livello zero viene creato immediatamente all'inizio del programma.
L'implementazione di oggetti in un array dinamico all'aumentare di t consente di non imporre restrizioni sulla dimensione dell'immagine. I limiti delle dimensioni dell'immagine sono determinati solo dalle risorse del computer utilizzato.
Quando si descrive il funzionamento del programma, verrà utilizzato il concetto di Kt completato:
elemento. Ogni elemento Kt completato contiene kt elementi Kt-l e un elemento Kt-l modificato che contiene kt-l ± 1 elementi Kt-2, al contrario di un elemento Kt incompleto, che non contiene un elemento Kt incompleto.
La classe CKForLn include i seguenti metodi.
1. Metodo DK (), (definire l'elemento K) - definire l'elemento K.
Determinare l'elemento Kt significa determinare il numero di elementi Kt-1 che formano un dato elemento Kt.
2. Metodo VK§, (verifica elemento K) - per verificare l'identità dell'elemento K considerato con l'elemento K dello stesso livello, precedentemente determinato dalla funzione del metodo DK ().
3. Metodo DEO, (definire la fine dell'elemento K) - determinare la fine dell'elemento K, ovvero, quando si definisce un elemento Kt, trovare il suo elemento Kt-1 modificato. La funzione del metodo DE () al livello t-1 viene chiamata dalla funzione del metodo DK () al livello t.
4. Metodo VE (), (verifica la fine dell'elemento K) - controlla l'identità della fine dell'elemento K considerato dall'elemento K modificato, precedentemente determinato dalla funzione del metodo DE ().
La classe Cmini include gli stessi metodi, che differiscono dai metodi della classe CKForLn in quanto i metodi della classe Cmini funzionano con gli elementi L e determinano o controllano gli elementi K0.
Metodi di classe Cmini
I metodi della classe Cmini utilizzano come dati iniziali le sequenze di elementi L costruiti per ciascuno dei contorni dell'immagine elaborata, a partire dal numero corrente dell'elemento L al momento della chiamata della funzione del metodo.
La funzione del metodo DK () della classe Cmini confronta i parametri di ogni successivo elemento L con i parametri dell'elemento L iniziale fintanto che corrispondono. Se i parametri non corrispondono, la funzione DK () controlla se l'elemento K0 è completato e termina
lavoro. Completato è l'elemento K0, che termina con un elemento L modificato, la cui lunghezza differisce di 1 dagli altri elementi L dell'elemento K0 (operazione 3.1 per l'inizio del segmento - t \u003d 0).
La funzione del metodo VK () controlla se i parametri dei successivi elementi k0 L coincidono con i parametri degli elementi L dell'elemento K0 predeterminati dalla funzione del metodo DK ()
lo stesso livello. Se i parametri dell'elemento K0 corrente coincidono con il preliminare
la funzione definita VK () forma un segno della continuazione del segmento e completa il lavoro (operazione 3.1 per la continuazione del segmento - t\u003e 0).
In caso contrario, la funzione VK () genera un segno della fine del segmento e termina
La funzione del metodo DE () confronta i parametri dell'elemento Kci corrente con i parametri dell'elemento K0 precedentemente definito dalla funzione DK () per determinare se l'elemento K0 corrente è stato modificato. Se gli altri parametri sono uguali, il numero di elementi L k0
elemento K0 modificato rispetto all'elemento K0, determinato in precedenza
funzione DK (), deve differire di 1 (operazioni 3.2, 3.3 per determinare il completamento
l'elemento iniziale К0 del segmento - t \u003d 0). Risultato: i parametri dell'elemento K0 modificato
vengono utilizzati nel metodo VE () della classe Cmini.
La funzione del metodo VE () confronta i parametri dell'elemento K0 corrente con i parametri dell'elemento K0 modificato precedentemente definito dalla funzione DE () per determinare
coincidono (operazione 3.2, 3.3 per la continuazione del segmento - t\u003e 0). Il risultato - un segno di coincidenza o non coincidenza - viene utilizzato nel metodo VК () della classe CKForLn.
Metodi di classe CKForLn
I metodi utilizzano i parametri degli elementi K costruiti per il livello più basso come dati di input. Cioè, per determinare i parametri dell'elemento Kt, i parametri
elementi Kt-l già costruiti.
La funzione del metodo DK () di livello t della classe CKForLn, quando definisce i parametri di un ^ -elemento, chiama la funzione VK () di livello t-1 della classe CKForLn, che controlla se l'elemento Kt-l già definito è seguito da un elemento Kt-l con gli stessi parametri. In tal caso, la chiamata alla funzione VK () viene ripetuta. In questo caso, viene conteggiato il numero di ripetizioni, ovvero viene determinato il parametro kt.
Altrimenti, la funzione DK () livello t chiama la funzione DE () livello t-1 per determinare l'elemento Kt-l modificato ed esce. Alla fine del lavoro, la funzione DK () di livello t della classe CKForLn determina i parametri e forma i segni di un elemento Kt completato o incompleto (operazioni 4.1, 4.2 al valore massimo corrente di t).
La funzione del metodo VK () di livello t della classe CKForLn controlla se i parametri dei successivi kt -elementi Kt coincidono con i parametri dell'elemento Kt precedentemente definito
funzione del metodo DK () dello stesso livello. Se i parametri dell'elemento Kt corrente coincidono con
da una funzione predeterminata DK () Kt -elemento dello stesso livello, la funzione VK ()
genera un segno di prosecuzione del segmento ed esce.
In caso contrario, la funzione VK () genera un segno di fine segmento e termina il lavoro (operazione 4.1, 4.2 con il valore corrente di t inferiore al massimo).
Elemento Kt La funzione del metodo DE0 di livello t della classe CKForLn, quando determina i parametri dell'elemento Kt, confronta i parametri dell'elemento Kt corrente con i parametri dell'elemento Kt precedentemente definito dalla funzione DK () per determinare se l'elemento Kt corrente è stato modificato. Se altri parametri sono uguali, i loro valori kt-1 devono differire di 1. Se questa condizione è soddisfatta, la funzione DE () forma il segno dell'elemento Kt modificato e
esce (operazione 4.3, 4.4 al valore massimo corrente di t).
La funzione del metodo VE () di livello t della classe CKForLn confronta i parametri dell'elemento Kt corrente con i parametri dell'elemento Kt modificato precedentemente allocato dalla funzione DE () per determinare se i valori dei loro parametri sono gli stessi.
Se i valori dei parametri dell'elemento Kt corrente coincidono con il preliminare
definita dalla funzione DK () dello stesso livello, la funzione VK () forma un segno della coincidenza dei valori dei parametri e termina il lavoro (operazione 4.3,4.4 al valore corrente di t inferiore al massimo).
Il diagramma temporale (Fig. 2) illustra il lavoro del programma LINESEGM utilizzando l'esempio del riconoscimento di un segmento di retta. La parte inferiore della figura mostra la parte linea digitalecostituito da elementi a L delle stesse direzioni principali e ausiliarie e lunghezze diverse.
Al passo 0 viene creato un oggetto di classe Stypi, che definisce i parametri dell'elemento K0.
Al passo 10, la determinazione dei parametri dell'elemento K0 è completata e viene creato un oggetto 1 della classe CKPrbn, che utilizza le funzioni dell'oggetto creato in precedenza per determinare i parametri dell'elemento K1. Al passo 19, la determinazione dei parametri dell'elemento K1 è completata e viene creato un oggetto 2 della classe CKPorbn, che utilizza le funzioni degli oggetti precedentemente creati per determinare i parametri dell'elemento K2. Al passo 49, la determinazione dei parametri dell'elemento K2 è completata e viene creato un oggetto 3 della classe CKPorbn, che utilizza le funzioni degli oggetti precedentemente creati per determinare i parametri dell'elemento K3. Viene eseguito il passaggio 79
condizione di terminazione del segmento. Il funzionamento del programma è descritto in dettaglio nell'appendice.
Nella sezione 0-6, due elementi L formano un elemento K0 incompleto. È ovvio che b -
l'elemento 3-6 di lunghezza 3 completa un segmento di linea, poiché b -elemento 6-7 di lunghezza 1 non può essere la sua continuazione. Pertanto, l'elemento b 6-7 è l'inizio del segmento di linea digitale.
Nella fig. 3 mostra un esempio del programma. Il contorno dell'immagine binaria della freccia riccia è diviso da quadrati in segmenti di linea. Il risultato del programma - una sequenza di segmenti di linea - è stato utilizzato per selezionare archi di curve digitali. I grandi quadrati mostrano i confini degli archi delle curve digitali.
Il lavoro del programma è stato testato su un numero significativo (più di 2000) esempi ed è utilizzato per studiare l'analisi strutturale di immagini a mezzitoni.
5. Funzionamento del programma per il riconoscimento di segmenti di linea
Consideriamo il funzionamento del programma UEEBSM utilizzando l'esempio di Fig. 4. La parte inferiore della figura mostra una parte di una linea digitale, costituita da elementi a L delle stesse direzioni principali e ausiliarie e lunghezze diverse. Nella sezione 0-6, due elementi L formano un K0- incompleto
Figura: 3. Un esempio del programma per l'analisi strutturale del contorno - segmentazione del contorno per segmenti di rette digitali
elemento. Ovviamente, l'elemento b 3-6 di lunghezza 3 completa un segmento di linea, poiché l'elemento b 6-7 di lunghezza 1 non può essere la sua continuazione. Pertanto, l'elemento b 6-7 è l'inizio del segmento di linea digitale.
Il lavoro del programma per determinare il segmento successivo della linea retta inizia con la funzione OK () del livello zero, che determina l'elemento K0 6-10 completato, costituito da elementi L
lunghezze 1,1,2; k0 \u003d 2. Questo elemento K0 è l'iniziale dell'elemento K1. Il programma crea un oggetto di primo livello e trasferisce il controllo alla funzione OK () di questo oggetto. La funzione OK () livello 1 chiama la funzione VKQ livello 0. La funzione VKQ confronta i parametri degli elementi L dell'elemento K0 6-10 con i successivi elementi L e conferma la presenza dell'elemento K0 10-14,
identico all'elemento K0 6-10. Continuando il suo lavoro, la funzione VKQ rileva che i seguenti elementi L non formano lo stesso elemento K0, termina il suo lavoro e trasferisce il controllo alla funzione OK () di livello 1. La funzione OK () di livello 1 chiama la funzione OE () di livello 0. Quest'ultima, iniziando con l'elemento b 6-7, determina la presenza di un elemento K0 modificato 14-19, costituito da elementi b di lunghezza 1,1,1,2; k0 \u003d 3, esce e trasferisce il controllo alla funzione OK () livello 1. Questa funzione determina la presenza di un elemento K1 6-19 completato, composto da due K0 -
elementi 1,1,2, (k1 \u003d 2) e uno modificato 1,1,1,2 (k0 \u003d 3). Il programma crea un oggetto di secondo livello e trasferisce il controllo alla funzione OK () di questo oggetto. La funzione OK () livello 2 chiama la funzione VKQ livello 1, che a sua volta chiama la funzione VKQ livello 0. La funzione VKQ confronta i parametri di b -elementi di K0 -elemento 6-10 con i successivi b -
elementi e conferma la presenza degli elementi K0 19-23, 23-27, identici all'elemento K0 6-10, cioè lo stesso numero di tali elementi K0 contenuti nell'elemento K1 6-19. Inoltre, la funzione VKQ di livello 0 restituisce il controllo con il segno della continuazione del segmento della funzione VKQ di livello 1. La funzione VKQ chiama la funzione VE0 di livello 0, che determina la presenza di un K0 modificato -
elemento 27-32, identico all'elemento K0 14-19. Pertanto, l'elemento K1 19-32 è definito,
identico all'elemento K1 6-19. Inoltre, la funzione VKQ livello 1 non definisce il successivo elemento K1 identico all'elemento K1 6-19, a causa del fatto che la funzione VE0 livello 0 non determina l'elemento K1 modificato identico all'elemento K1 6-19, a partire dall'elemento b 40-41 e restituisce il controllo al livello OK () 2. La funzione OK () livello 2 chiama la funzione OE () livello 1, che determina la presenza di un elemento K1 modificato 32-49, costituito da elementi K0 32-36, 36- 40,
40-44, 44-49. Successivamente, viene determinato l'elemento K2 6-49, viene formato un oggetto di livello 3, viene determinato l'elemento K2 modificato 49-79. Questi due elementi K2 formano l'elemento K3 6-79. Questo completa la costruzione del segmento, poiché i successivi elementi L 79-81 e 81-83 non formano un elemento K0,
identico all'elemento K0 6-10 e la funzione di livello 0 VKQ non forma un segno di continuazione
segmento. Nella sequenza degli elementi L, viene evidenziato il segmento della retta digitale 6-79. Il programma inizia a definire il segmento successivo, a partire dall'elemento L 80-82.
b. conclusioni
1. Proposto nuovo algoritmo selezione di segmenti di linea nei contorni dell'immagine e implementazione software non banale dell'algoritmo, che consentono di ottenere una soluzione esatta al problema del riconoscimento dei contorni dell'immagine come sequenze di segmenti di linea.
2. L'implementazione software dell'algoritmo per la selezione dei segmenti di linea nei contorni delle immagini è realizzata utilizzando moderni mezzi di programmazione orientata agli oggetti, che hanno permesso di non imporre restrizioni esplicite sulla dimensione dell'immagine elaborata con il massimo utilizzo delle risorse del computer utilizzato.
3. Sulla base dell'algoritmo proposto e della sua implementazione software, è stata ottenuta una soluzione teorica e sono stati condotti esperimenti per riconoscere archi di curve digitali e segmentazione del contorno di immagini binarie su un segmento di linee rette digitali e un arco di curve digitali.
LISTA DI REFERENZE
1. Kovalevsky V.A. Applicazioni dei segmenti rettilinei digitali alla codifica economica delle immagini, in Atti del 7 ° seminario internazionale, DGCI "97, Montpellier. - Francia, 1997. - 3-5 dicembre. - P. 51-62.
2. Kalmykov V.G. Metodo strutturale per descrivere e riconoscere segmenti di linee rette digitali nei contorni di immagini binarie // Piece іntelekt. - 2002. - N. 4. - C. 450-457.
3. Kalmykov V.G., Vishnevsky V.V. Analisi dei contorni degli oggetti in immagini binarie // Macchine e sistemi matematici. - 1997. - N. 2. - P. 68 - 71.
4. Kalmikov V.G. L'arco della curva digitale è il valore e il fissaggio // L'elaborazione dei segnali e dell'immagine e la generazione delle immagini. Pratsi somoi Conferenza internazionale tutta ucraina. - Kiev. - 2004 .-- 11-15 zhovten.
Da tempo desideravo scrivere un articolo generale contenente le basi del riconoscimento delle immagini, una guida ai metodi di base, che spieghi quando usarli, quali compiti risolvono, cosa si può fare la sera in ginocchio e cosa è meglio non pensare senza un team di persone in 20.
Scrivo da molto tempo alcuni articoli sul riconoscimento ottico, quindi mi scrivono un paio di volte al mese persone diverse con domande su questo argomento. A volte hai la sensazione di vivere con loro in mondi diversi. Da un lato, capisci che una persona è molto probabilmente un professionista in un argomento correlato, ma sa molto poco sui metodi di riconoscimento ottico. E la cosa più offensiva è che sta cercando di applicare un metodo da un'area di conoscenza vicina, il che è logico, ma non funziona completamente in Image Recognition, ma non lo capisce ed è molto offeso se inizia a raccontare qualcosa dalle basi. E considerando che raccontare dalle basi è molto tempo, il che spesso non lo è, diventa ancora più triste.
Questo articolo è concepito in modo che una persona che non si è mai occupata di metodi di riconoscimento delle immagini possa, entro 10-15 minuti, creare nella sua testa una sorta di immagine di base del mondo corrispondente all'argomento e capire in quale direzione dovrebbe scavare. Molte delle tecniche qui descritte sono applicabili all'elaborazione radar e audio.
Inizierò con un paio di principi che iniziamo sempre a raccontare a un potenziale cliente oa una persona che vuole iniziare a fare il riconoscimento ottico:
- Quando risolvi un problema, vai sempre dal più semplice. È molto più facile appendere un'etichetta arancione su una persona che seguire una persona, evidenziandola con cascate. È molto più facile prendere una fotocamera con una risoluzione maggiore che sviluppare un algoritmo di super risoluzione.
- Una formulazione rigorosa del problema nei metodi di riconoscimento ottico è ordini di grandezza più importante che nei problemi di programmazione del sistema: una parola in più nella specifica tecnica può aggiungere il 50% del lavoro.
- Non esistono soluzioni universali ai problemi di riconoscimento. Non è possibile creare un algoritmo che semplicemente "riconoscerà qualsiasi iscrizione". Un segno per strada e un foglio di testo sono oggetti fondamentalmente diversi. Probabilmente, puoi creare un algoritmo generale (ecco un buon esempio di Google), ma richiederà molto lavoro di un grande team e sarà composto da dozzine di routine diverse.
- OpenCV è una Bibbia che ha molti metodi e con cui puoi risolvere il 50% del volume di quasi tutti i problemi, ma OpenCV è solo una piccola parte di ciò che puoi effettivamente fare. In uno studio, è stata scritta la conclusione: "Il problema non è risolto con i metodi OpenCV, quindi è irrisolvibile". Cerca di evitarlo, non essere pigro e valuta con sobrietà l'attività corrente ogni volta da zero, senza utilizzare i modelli OpenCV.
L'elenco dei metodi fornito qui non è completo. Suggerisco di aggiungere metodi critici che non ho scritto nei commenti e di assegnare 2-3 parole di accompagnamento a ciascuno.
Parte 1. Filtrazione
In questo gruppo ho inserito metodi che consentono di evidenziare aree di interesse nelle immagini senza analizzarle. La maggior parte di questi metodi applica una sorta di trasformazione uniforme a tutti i pixel dell'immagine. A livello di filtraggio, l'immagine non viene analizzata, ma i punti filtrati possono essere considerati come aree con caratteristiche speciali.Binarizzazione per soglia, selezione dell'area dell'istogramma
La trasformazione più semplice è la binarizzazione della soglia dell'immagine. Per le immagini RGB e le immagini in scala di grigi, la soglia è il valore del colore. Ci sono compiti ideali in cui una tale trasformazione è sufficiente. Supponiamo che tu voglia selezionare automaticamente gli oggetti su un foglio di carta bianco:
La scelta della soglia alla quale avviene la binarizzazione determina in gran parte il processo di binarizzazione stesso. In questo caso, l'immagine è stata binarizzata dal colore medio. Di solito la binarizzazione viene eseguita utilizzando un algoritmo che seleziona in modo adattivo la soglia. Questo algoritmo può essere la scelta dell'aspettativa o della modalità. E puoi scegliere il picco più grande dell'istogramma.
La binarizzazione può dare risultati molto interessanti quando si lavora con gli istogrammi, anche in una situazione in cui si considera un'immagine non in RGB, ma in HSV. Ad esempio, segmenta i colori di interesse. Questo principio può essere utilizzato per costruire sia un rilevatore di tag che un rilevatore di pelle umana.
Filtraggio classico: Fourier, LPF, HPF
I metodi classici di filtraggio dal radar e l'elaborazione del segnale possono essere applicati con successo in una varietà di attività di riconoscimento di pattern. Il metodo tradizionale nel radar, che non viene quasi mai utilizzato nelle immagini pure, è la trasformata di Fourier (più specificamente, la FFT). Una delle poche eccezioni a cui viene utilizzata la trasformata di Fourier unidimensionale è la compressione dell'immagine. Per l'analisi delle immagini, una trasformazione unidimensionale di solito non è sufficiente; è necessario utilizzare una trasformazione bidimensionale molto più dispendiosa in termini di risorse.
Poche persone lo calcolano effettivamente, di solito è molto più veloce e più facile usare la convoluzione della regione di interesse con un filtro già pronto per le frequenze alte (HPF) o basse (LPF). Un tale metodo, ovviamente, non consente l'analisi dello spettro, ma in una specifica attività di elaborazione video, di solito non è necessaria un'analisi, ma un risultato.
Gli esempi più semplici di filtri che implementano la sottolineatura basse frequenze (Filtro gaussiano) e passa alto (filtro Gabor).
Per ogni punto dell'immagine viene selezionata una finestra e moltiplicata con un filtro della stessa dimensione. Il risultato di questa convoluzione è il nuovo valore in punti. Quando si implementa un filtro passa basso e un filtro passa alto, si ottengono immagini del tipo seguente:
Wavelets
Ma cosa succede se usiamo qualche funzione caratteristica arbitraria per la convoluzione con un segnale? Quindi si chiamerà "trasformata Wavelet". Questa definizione di wavelet non è corretta, ma tradizionalmente si è sviluppato che in molti comandi l'analisi wavelet è la ricerca di un pattern arbitrario nell'immagine utilizzando la convoluzione con il modello di questo pattern. Esiste un insieme di funzioni classiche utilizzate nell'analisi wavelet. Questi includono il wavelet di Haar, il wavelet di Morlet, il wavelet del cappello messicano, ecc. Le primitive di Haar, su cui c'erano molti dei miei articoli precedenti (,), si riferiscono a tali funzioni per lo spazio bidimensionale.
Sopra sono 4 esempi di wavelet classiche. Wavelet 3-D Haar, wavelet 2-D Meyer, wavelet Cappello messicano, wavelet Daubechies. Un buon esempio usare l'interpretazione estesa delle wavelet è il problema di trovare un flare nell'occhio, per il quale il flare stesso è l'ondina:
Le wavelet classiche vengono solitamente utilizzate per comprimere le immagini o per classificarle (descritto di seguito).
Correlazione
Dopo una così libera interpretazione delle wavelet da parte mia, vale la pena menzionare l'effettiva correlazione sottostante. Questo è uno strumento indispensabile quando si filtrano le immagini. L'applicazione classica è la correlazione del flusso video per trovare turni o flussi ottici. Il più semplice rilevatore di spostamento è anche, in un certo senso, un correlatore di differenza. Dove le immagini non sono correlate, c'era movimento.
Funzioni di filtraggio
Una classe interessante di filtri è il filtro delle funzioni. Si tratta di filtri puramente matematici che consentono di rilevare una semplice funzione matematica nell'immagine (linea, parabola, cerchio). Viene costruita un'immagine accumulante in cui per ogni punto dell'immagine sorgente vengono disegnati un insieme di funzioni che la generano. La trasformazione più classica è la trasformazione di Hough per le linee. In questa trasformazione, per ogni punto (x; y), viene disegnato l'insieme di punti (a; b) della retta y \u003d ax + b, per cui l'uguaglianza è vera. Si ottengono belle immagini:
(il primo vantaggio è quello che è il primo a trovare il fermo nella foto e tale definizione e spiegarlo, il secondo più a quello che è il primo a dire ciò che è mostrato qui)
La trasformata di Hough ti consente di trovare qualsiasi funzione parametrizzabile. Ad esempio cerchi. C'è una trasformazione modificata che ti consente di cercare qualsiasi forma. Questa trasformazione è terribilmente affezionata ai matematici. Ma durante l'elaborazione delle immagini, sfortunatamente, non sempre funziona. Velocità molto bassa, sensibilità molto alta alla qualità della binarizzazione. Anche in situazioni ideali, ho preferito cavarmela con altri metodi.
L'analogo della trasformata di Hough per le linee è la trasformata di Radon. Viene calcolato tramite la FFT, che offre un guadagno in termini di prestazioni in una situazione in cui ci sono molti punti. Inoltre, può essere applicato a un'immagine non binarizzata.
Filtrare i contorni
Una classe separata di filtri è quella dei bordi e dei contorni. I contorni sono molto utili quando vogliamo passare dal lavorare con un'immagine al lavorare con gli oggetti in quell'immagine. Quando un oggetto è abbastanza complesso, ma ben definito, spesso l'unico modo per lavorarci è selezionarne i contorni. Esistono numerosi algoritmi che risolvono il problema del filtro dei contorni:Il più delle volte viene utilizzato Canny, che funziona bene e la cui implementazione è in OpenCV (c'è anche Sobel, ma sembra peggio per i contorni).
Altri filtri
Sopra ci sono i filtri, le cui modifiche aiutano a risolvere l'80-90% dei problemi. Ma oltre a loro, ci sono filtri più rari usati nelle attività locali. Esistono dozzine di filtri di questo tipo, non li elencherò tutti. Interessanti sono i filtri iterativi (ad esempio, un modello di aspetto attivo), così come le trasformazioni ridgelet e curvlet, che sono una lega del filtraggio wavelet classico e dell'analisi nel campo della trasformata del radon. La trasformazione beamlet funziona magnificamente sul confine della trasformata wavelet e dell'analisi logica, consentendo di evidenziare i contorni:
Ma queste trasformazioni sono molto specifiche e adatte a compiti rari.
Parte 2. Elaborazione logica dei risultati di filtrazione
Il filtraggio fornisce una serie di dati adatti per l'elaborazione. Ma spesso non puoi semplicemente prendere e utilizzare questi dati senza elaborarli. In questa sezione, ci saranno diversi metodi classici per passare dall'immagine alle proprietà degli oggetti, o agli oggetti stessi.Morfologia
Il passaggio dal filtraggio alla logica, secondo me, è dovuto ai metodi della morfologia matematica (,,). In realtà, queste sono le operazioni più semplici per costruire ed erodere immagini binarie. Questi metodi consentono di rimuovere il rumore da un'immagine binaria aumentando o diminuendo gli elementi esistenti. Esistono algoritmi di contornatura basati sulla morfologia matematica, ma di solito utilizzano una combinazione di algoritmi o algoritmi ibridi.
Analisi del contorno
Gli algoritmi per ottenere i confini sono già stati menzionati nella sezione sul filtraggio. I confini risultanti vengono semplicemente convertiti in contorni. Per l'algoritmo di Canny, ciò avviene automaticamente; per altri algoritmi, è necessaria una binarizzazione aggiuntiva. È possibile ottenere un contorno per un algoritmo binario, ad esempio, con un algoritmo di scarabeo.Il contorno è una caratteristica unica di un oggetto. Questo spesso rende possibile identificare l'oggetto lungo il contorno. Esiste un potente apparato matematico che ti consente di farlo. L'apparato si chiama analisi del contorno (,).
Ad essere onesto, non sono mai riuscito ad applicare l'analisi dei contorni a problemi reali. Sono necessarie condizioni troppo ideali. O non c'è confine o c'è troppo rumore. Ma se hai bisogno di riconoscere qualcosa in condizioni ideali, l'analisi del contorno è un'ottima opzione. Funziona molto velocemente, con una bella matematica e una logica chiara.
Punti speciali
I punti singolari sono caratteristiche uniche di un oggetto che consentono di associare un oggetto a se stesso o a classi di oggetti simili. Esistono diverse dozzine di modi per evidenziare questi punti. Alcuni metodi evidenziano punti speciali nei fotogrammi vicini, alcuni dopo un lungo periodo di tempo e quando si cambia l'illuminazione, altri consentono di trovare punti speciali che rimangono tali anche quando l'oggetto viene ruotato. Cominciamo con metodi che ci permettono di trovare punti singolari che non sono così stabili, ma vengono calcolati rapidamente, e poi andiamo in complessità crescente:Primo grado. Punti singolari stabili per secondi. Tali punti vengono utilizzati per guidare l'oggetto tra fotogrammi video adiacenti o per unire immagini da telecamere vicine. Questi punti includono i massimi dell'immagine locale, gli angoli dell'immagine (il migliore dei rivelatori, forse il rivelatore Haris), i punti in cui vengono raggiunti i massimi di dispersione, alcuni gradienti, ecc.
Seconda classe. Punti speciali che sono stabili con variazioni leggere e piccoli movimenti di oggetti. Tali punti vengono utilizzati principalmente per l'addestramento e la successiva classificazione dei tipi di oggetto. Ad esempio, un classificatore di pedoni o un classificatore di volti è un prodotto di un sistema costruito attorno a tali punti. Alcune delle wavelet precedentemente menzionate possono essere la base per tali punti. Ad esempio, primitive di Haar, ricerca di abbagliamento, ricerca di altre funzioni specifiche. Questi punti includono i punti trovati con il metodo dell'istogramma del gradiente direzionale (HOG).
Terza classe. Punti stabili. Conosco solo due metodi che danno stabilità completa e le loro modifiche. Questi sono SURF e SIFT. Ti permettono di trovare punti speciali anche quando ruoti l'immagine. Il calcolo di tali punti richiede più tempo rispetto ad altri metodi, ma sufficiente tempo limitato... Purtroppo, questi metodi sono brevettati. Sebbene, in Russia, gli algoritmi non siano brevettati, quindi usali per il mercato interno.
Parte 3. Formazione
La terza parte della storia sarà dedicata a metodi che non lavorano direttamente con l'immagine, ma che consentono di prendere decisioni. Si tratta principalmente di vari metodi di apprendimento automatico e processo decisionale. Di recente, Yandyks ha pubblicato un corso su questo argomento su Habr, c'è un'ottima selezione. Eccolo nella versione testuale. Per uno studio serio dell'argomento, consiglio vivamente di guardarli. Qui cercherò di delineare diversi metodi di base utilizzati nel riconoscimento di pattern.Nell'80% delle situazioni, l'essenza dell'apprendimento nel problema del riconoscimento è la seguente:
Esiste un set di test con diverse classi di oggetti. Lascia che sia la presenza / assenza di una persona nella foto. Per ogni immagine, c'è un insieme di caratteristiche che sono state identificate da qualche caratteristica, sia essa Haar, HOG, SURF o qualche tipo di wavelet. L'algoritmo di apprendimento deve costruire un tale modello, in base al quale sarà in grado di analizzare una nuova immagine e decidere quale degli oggetti è nell'immagine.
Come è fatto? Ciascuna delle immagini di prova è un punto nello spazio delle caratteristiche. Le sue coordinate sono il peso di ogni elemento nell'immagine. Lascia che i nostri segni siano: "La presenza degli occhi", "La presenza di un naso", "La presenza di due mani", "La presenza delle orecchie", ecc. Evidenzieremo tutti questi segni con i nostri rilevatori esistenti, che sono addestrati per umano. Per una persona in uno spazio del genere, il punto sarà corretto. Per la scimmia, il punto è per il cavallo. Il classificatore viene addestrato su un campione di esempi. Ma non tutte le fotografie mostravano le mani, altre mancano di occhi e nella terza la scimmia ha un naso umano a causa di un errore nel classificatore. Il classificatore umano addestrato suddivide automaticamente lo spazio delle caratteristiche in modo tale da dire: se la prima caratteristica si trova nell'intervallo 0,5
Esistono molti classificatori. Ognuno di loro lavora meglio in qualche compito proprio. Il compito di selezionare un classificatore per un'attività specifica è per molti versi un'arte. Ecco alcune belle immagini sull'argomento.
Case semplice, separazione unidimensionale
Analizziamo con l'esempio il caso più semplice di classificazione, quando lo spazio delle caratteristiche è unidimensionale e abbiamo bisogno di separare 2 classi. La situazione è più comune di quanto si possa immaginare: ad esempio, quando è necessario distinguere due segnali o confrontare un pattern con un campione. Supponiamo di avere un campione di formazione. In questo caso, si ottiene un'immagine, in cui l'asse X sarà una misura di somiglianza e l'asse Y è il numero di eventi con tale misura. Quando l'oggetto cercato si presenta come se stesso, si ottiene la gaussiana sinistra. Quando non è come ... giusto. Un valore di X \u003d 0.4 divide i campioni in modo che una decisione sbagliata riduca al minimo la probabilità che venga presa una decisione sbagliata. È la ricerca di un tale separatore il problema di classificazione.
Una piccola osservazione. Il criterio che minimizza l'errore non sarà sempre ottimale. Il grafico successivo è un grafico di un vero sistema di riconoscimento dell'iride. Per un tale sistema, il criterio è scelto in modo da ridurre al minimo la probabilità di una falsa ammissione di una persona non autorizzata all'oggetto. Questa probabilità è chiamata "errore del primo tipo", "probabilità di falso allarme", "falso positivo". Nella letteratura in lingua inglese "False Access Rate".
) AdaBusta è uno dei classificatori più comuni. Ad esempio, la cascata Haar è costruita su di essa. Di solito vengono utilizzati quando è necessaria una classificazione binaria, ma nulla impedisce di insegnare per un numero maggiore di classi.
SVM (,,,) Uno dei classificatori più potenti con molte implementazioni. Fondamentalmente, sui compiti di apprendimento che ho affrontato, ha funzionato in modo simile all'adabusta. È considerato abbastanza veloce, ma il suo allenamento è più difficile di quello di Adabusta ed è richiesta la selezione del nucleo corretto.
Esistono anche reti neurali e regressione. Ma per classificarli brevemente e mostrare come differiscono, è necessario un articolo molto più di questo.
________________________________________________
Spero di essere riuscito a fare una rapida panoramica dei metodi utilizzati senza immergermi nella matematica e nella descrizione. Forse aiuterà qualcuno. Anche se, ovviamente, l'articolo è incompleto e non c'è una parola su come lavorare con immagini stereo, o su OLS con filtro di Kalman, o sull'approccio bayesiano adattivo.
Se ti piace l'articolo, cercherò di fare la seconda parte con una selezione di esempi di come vengono risolte le attività di ImageRecognition esistenti.
E infine
Cosa leggere?1) Una volta mi è piaciuto molto il libro "Digital Image Processing" di B. Yane, che è scritto in modo semplice e chiaro, ma allo stesso tempo viene presentata quasi tutta la matematica. Ottimo per familiarizzare con i metodi esistenti.
2) I classici del genere sono R. Gonzalez, R. Woods "Digital Image Processing". Per qualche motivo è stato più difficile per me del primo. Molto meno matematica, ma più metodi e immagini.
3) "Elaborazione e analisi delle immagini in compiti di visione artificiale" - scritto sulla base di un corso tenuto in uno dei dipartimenti di PhysTech. Ci sono molti metodi e le loro descrizioni dettagliate. Ma secondo me, il libro ha due grossi inconvenienti: il libro è fortemente focalizzato sul pacchetto software che lo accompagna, nel libro troppo spesso la descrizione di un metodo semplice si trasforma in giungla matematica, da cui è difficile fare un diagramma strutturale del metodo. Ma gli autori hanno creato un comodo sito Web in cui viene presentato quasi tutto il contenuto: wiki.technicalvision.ru
4) Per qualche ragione, mi sembra che un buon libro che struttura e collega l'immagine del mondo che emerge quando si studia il riconoscimento delle immagini e l'apprendimento automatico sia "About Intelligence" di Jeff Hawkins. I metodi diretti non esistono, ma ci sono molti pensieri su cui pensare da dove provengono i metodi diretti di elaborazione delle immagini. Quando lo leggi attentamente, ti rendi conto di aver già visto i metodi del cervello umano, ma in compiti di elaborazione video.
Formulazione del problema determinato dallo scopo e dalle possibilità della sua attuazione.
Scopo. Sviluppare un programma per classificare le parti rettangolari in parti difettose e di alta qualità.
Opportunità per l'implementazione del compito determinato dalle capacità del computer. Il computer è in grado di elaborare informazioni numeriche in una sequenza algoritmica. Per realizzare le capacità di un computer, è necessario simulare il problema da risolvere.
La simulazione utilizzando un computer implica una transizione da un oggetto reale (mondo) a una descrizione codificata delle sue proprietà utilizzando dati e operazioni su di essi. Tale transizione, di regola, viene eseguita in più fasi:
Astrazione - selezione delle caratteristiche più essenziali dell'oggetto rispetto al compito da svolgere.
È necessario condurre una ricerca che permetta di passare dall'oggetto della modellazione all'argomento della modellazione, scartando tutto ciò che non è necessario in conformità con l'obiettivo del compito
In che modo un rettangolo è diverso dagli altri quadrilateri?
- Uguaglianza dei lati opposti.
- Parallelismo di lati opposti.
- Uguaglianza delle diagonali.
- Tutti gli angoli sono dritti.
Qual è il minimo di segni necessari per risolvere in modo univoco il problema?
- Uguaglianza di 2 lati opposti + uguaglianza delle diagonali.
- Parallelismo di 2 lati opposti + uguaglianza delle diagonali.
- Tre angoli sono diritti.
Quindi, grazie all'astrazione, abbiamo ottenuto un modello di informazione verbale. Ma è ancora incomprensibile per il computer. Comprende un modello matematico presentato come un algoritmo e implementato nel software.
Metodologia per l'implementazione dell'attività.
Un disegno di una parte di qualità (rettangolo) o di una parte difettosa (quadrilatero) viene creato da segmenti (comando LINEA) nel sistema grafico di AutoCAD ed esportato in. Il programma kntrs.lsp () legge i dati del segmento (coordinate del vertice) dal file DXF e lo scrive nel file di testo vrtks.txt in un ordine circolare di attraversamento del vertice.
Il file di testo vrtks.txt può essere creato manualmente prendendo le coordinate dei vertici direttamente dal disegno.
Il programma sviluppato rct.lsp dovrebbe leggere i dati dal file vrtks.txt, analizzarli ed emettere un record della conformità della parte ai requisiti (rettangolo o meno) nel file result.txt.
Formalizzazione delle caratteristiche
Uguaglianza delle lunghezze dei segmenti (lati o diagonali): La lunghezza di ogni segmento è determinata come l'ipotenusa di un rettangolo rettangolare (secondo il teorema di Pitagora) attraverso la differenza di coordinate dei segmenti:
(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Parallelismo di linee: K2 \u003d K1dove PER - pendenza di una linea retta K \u003d (Y2-Y1) / (X2-X1)
Come formalizzare il concetto di "Angolo retto"? Nell'ambito dell'attività in esame, la presenza di un "Angolo retto" può essere determinata dalla perpendicolarità dei segmenti: K2 \u003d -1 / K1dove PER È la pendenza della linea retta. K \u003d (Y-Y0) / (X-X0).
Visualizzazione del modello sul computer
Qualsiasi informazione viene infine visualizzata in un computer utilizzando numeri binari (codici) in un modello in macchina. In precedenza, la codifica veniva eseguita da un programmatore. Al giorno d'oggi, la maggior parte dei programmi sono scritti in linguaggi algoritmici.
