Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Il prossimo argomento di cui parleremo nel cercare di abbinare forme o qualsiasi altro modello su un'immagine è il metodo noto come Hough Transform. Ancora una volta queste slide di lezione si basano anche sulle eccellenti lezioni del professor Yannis, all'Inria Ren, così come le lezioni del professore Mubarak Shah all'università della Florida Centrale. Abbiamo già visto un paio di metodi di adattamento di linea. Abbiamo visto meno squarci fit e poi abbiamo visto RANSAC. La domanda che si sta per chiedere ora è: cosa si fa se ci sono più linee inserite in un particolare orientamento o inserite in una particolare configurazione in un'immagine? Potrebbero essere più linee, potrebbe essere un poligono, potrebbe essere un cerchio, poi come si fa ad affrontare una forma sul set di punti dati che si ha? Ed è di questo che parleremo ora, quando noi Hough Transform. (1.30) Questo metodo risale agli inizi del 60s, da Hough, che ha depositato il brevetto americano per questo, ma da allora ci sono stati molti sforzi che hanno tradotto questo in quello che vediamo oggi. Nei primi anni 70s, l'Hough Transform è stato utilizzato per rilevare linee e curve. Poi nei primi anni ' 80s c'era un metodo che veniva definito una trasformazione generalizzata e vedremo tutti questi sopra le prossime slide. Iniziamo con la semplice equazione di una linea e coordinate cartesiane, che tutti conosciamo è y = mx + c, dove diciamo che m è la pendenza e c è l'intercettazione y. Si potrebbe semplicemente giocare con i termini dell'equazione un po' e poi scrivere questo come c = − mx + y. Piuttosto ora viviamo in un m, c spazio dove x è c intercetta, y definire la linea in quello spazio. Allora, erano originariamente nello spazio x, y, dove m definiscono la pendenza e c definiscono l'intercetta y. Potremmo semplicemente riorganizzare questi termini leggermente per ora andare in un m, c spazio dove − x diventa la pendenza e la y diventa l'intercetta c. In questo tipo di contesto, ogni punto in m, c spazio diventa l'equazione di una linea nello spazio x, y, ricordati per ogni scelta di m e c, otterrete l'equazione di una linea come vediamo qui. E ogni punto dello spazio x y similmente diventerebbe l'equazione di una linea nello spazio m, c. C'è una duplice corrispondenza tra questi due spazi. Quindi cosa facciamo con questo? (3.35) Sappiamo che per adattarsi a qualsiasi modello abbiamo bisogno di un certo numero di campioni. Ad esempio, per adattarsi ad una linea, servono due campioni. Se si trattava di un qualsiasi altro modello, se si stava allestendo un quadrato o un cerchio, abbiamo bisogno di un numero diverso di punti. Per adattarsi ad una linea, potreste avere bisogno di due punti. Cominciamo con quell' esempio. Ma anche se avevi solo un punto invece di due punti, sai che potrebbe appartenere a una certa famiglia di linee. Ti dà alcune informazioni parziali sull'equazione della linea stessa. Quindi, quello che possiamo chiedere ad ogni punto del tuo x, y space da fare è votare certe configurazioni di m e c, nel caso si parli di una linea, se allineata. Ogni punto può votare per quale configurazione di m e c avrebbe comportato in questo punto essere in quel determinato luogo. E poi si raccolgono parole per tutti questi punti e cercano di cercare consenso e ovunque si vota il voto di maggioranza, si va a dire che quella è l'equazione della linea che sto cercando. Cerchiamo di elaborare su questo e di passare lentamente. (4.50) Prima di andare avanti, abbiamo parlato delle coordinate cartesiane sulla slide precedente. Purtroppo la formulazione Cartesiana può essere problematica per le linee verticali. Si può dire perché? Quando hai una linea verticale, la tua pendenza è sconfinata, diventa difficile rappresentare una tale linea nel tuo m, c spazio perché m deve essere infinito. Quindi, in uno scenario del genere, può essere più saggio utilizzare una parametrizzazione leggermente diversa, la parametrizzazione polare, che è scritta in termini di ρ e θ, dove ρ è la distanza della linea dall'origine e θ è l'angolo fatto dal normale all'asse X. Puoi anche scrivere ρ = x cos θ + y peccato θ. Si tratta di una parametrizzazione polare standard che viene utilizzata dalle coordinate cartesiane alle coordinate polari. Sappiamo ora che in questo spazio, ρ è almeno inferiore delimitato dal 0 e θ si trova tra il 0 e il 360. Sappiamo che queste quantità sono delimitate, il che rende leggermente più facile lavorare con. (6.17) Così, ogni punto del tuo spazio originale, nel tuo spazio Cartesiano (x, y) vota per molti punti nel tuo spazio dei parametri. Quindi, se avessi una certa linea, un certo punto x1 nel tuo spazio cartesiano originale. Per il momento si parlerà di questo metodo generalmente, in termini di uno spazio cartesiano e di allestimento di una linea o allestimento di un cerchio e così via. Un po' più tardi in questa lezione parleremo di come si usa questo con le immagini. Se avete già un senso di quello che sta arrivando, stiamo cercando di scoprire come si usa Hough Transform per abbinare linee o cerchi o qualsiasi altra forma in un'immagine. Questo è l'obiettivo di questa lezione o del metodo discusso in questa lezione. Ma prima di andare a un'immagine, parleremo solo in genere di coordinate cartesiane. Quindi, se hai un punto x nello spazio, sai che ci sono una famiglia di righe che 1 (x, y) possono passare per x, e ognuna di quelle linee ha un corrispondente che avrà un 1 m, c pendente e l'intercetto y, e tutti si tradurranno in punti corrispondenti nello spazio m, c o nello spazio ρ, θ spazio. Se si passa allo spazio di registrazione, si avrà una variazione leggermente diversa. Corrisponderanno ad un punto qui nello spazio di r theta. Così, per ogni punto x, y può votare per molti punti nel vostro spazio dei parametri, che quel particolare x punto avrebbe potuto smentire. Quindi, ogni riga a questo punto, è un 1 (x,) 1 y1 voto per un punto in uno spazio di parametro che soddisfa ρ = x cos + y il peccato θ. Vediamo qualche esempio. (8.12) Ecco un'altra linea che passa per x e che funzionerebbe per un punto diverso nello spazio dei parametri 1, che è qui. (8.23) Ecco un'altra linea che passa per x, che voterebbe per un punto diverso nello spazio dei parametri 1. Ricordare lo spazio dei parametri ora è definito in una parametrizzazione polare. (8.36) E continuate a ripeterlo per diverse linee che avrebbero potuto passare per x e tutte le 1 hanno ottenuto voti nello spazio dei parametri. (8.46) Allo stesso modo, potresti avere un altro punto x nel tuo spazio originale attraverso il quale avresti 2 un altro set di linee che possono passare nel tuo spazio cartesiano originale e ognuna di quelle righe può votare per loro per una parametrizzazione diversa nel tuo spazio di parametri. Si può vedere che di nuovo, qui, questi sono piccoli esempi per diverse linee che passano x, si ottengono diversi 2 voti nello spazio dei parametri. (9.17) Promettiamola di ri - raccontarlo attraverso un algoritmo. Quindi, hai i tuoi dati X, hai una serie di parametri quantizzati, theta min a theta max. Ad esempio, se si assume la parametrizzazione polare, non si può voler votare per ogni angolo compreso tra 0 e 360, si può voler dividere da 0 a 360 in piedini a 10 gradi e avere solo 36 possibili valori theta. Questo è ciò che intendiamo per un parametro quantizzato qui. Si inizializza anche un array di accumulatori, che è semplicemente un conteggio di frequenza. Si tratta semplicemente di un conteggio di frequenza di voto. Si può guardare in quel modo. Così, per ogni punto (x, y) nel tuo spazio Cartesiano, cerchiamo di vedere per la theta appartenente a theta, hai 10 possibilità di thetas. Se scrivi ρ = x cos θ + y peccato θ. Cerchiamo di vedere per ogni serie di parametri modello coerenti con il campione, quindi quale rho e quale theta si allineerebbe con questa particolare X, Y che abbiamo preso. Si incrementa A per quella theta e rho. Quindi, immaginate che l'accumulatore sia una matrice 2D definita dai valori theta su un asse e valori rho sull'altro asse, che potrebbe anche essere quantizzato, si potrebbe quantizzare la distanza in, a distanza di dire un certo numero di unità. E qualunque sia la rho e la theta che conosciamo corrisponde a questa X e Y che abbiamo, andate a quella rho e theta e in ognuno di questi casi, potreste verificare la consistenza e l'incremento che cellula nella matrice degli accumulatori entro il 1. E continui a fare questo per ogni punto X Y che ti viene dato. Quelli sono il tuo set di punti che ti vengono dati e che continui ad accumulare e alla fine fai una soppressione non massima in A. Quindi, se hai molti bidoni diversi che hanno un voto alto, fai una non massima soppressione locale, locale non massimo per vedere quale bidone ha i voti davvero più alti e la tua definizione che la theta e rho deve corrispondere al modello che corrisponde al tuo, che ha direttamente un cuscinetto sui dati nella tua matrice X. Questo ti dà modo di stimare la theta e rho o in coordinate cartesiane, trovando l'equazione della linea, corrispondente a questa serie di punti che ti vengono dati. Come potete vedere questo è molto simile ad un adattamento meno quadrato, ma farlo in modo leggermente diverso. Stiamo ancora cercando di adattare una linea a una serie di punti che ci viene dato, ma lo stiamo facendo usando l'approccio di voto dell'Hough. (11.54) Ora, come promesso, ecco un esempio da una prospettiva di immagine. Diciamo che abbiamo un'immagine e l'immagine ha diverse linee e vogliamo trovare le equazioni di quelle linee. Potrebbero essere diverse le applicazioni in cui questo può essere richiesto. Diciamo per esempio che state cercando di scattare immagini di un chip informatico e di cercare di scoprire come quelle linee siano allineate su un chip di computer e così via. Vuoi trovare le equazioni di quelle linee. (12.24) Quindi, usando lo stesso approccio di cui abbiamo appena parlato sulla slide precedente, si assume una certa parametrizzazione, si chiede ad ogni punto di votare a quale parametrizzazione potrebbe aver generato in quel determinato punto, e si finisce per ottenere voti sulla matrice di accumulatore 2D, diciamo solo un ρ e θ. Così, potete vedere qui che avete un mucchio di voti che si diffondono in molti bidoni di accumulatori diversi, abbiamo detto che accumulato come matrice che è rho e theta. (12.54) Ora, stai facendo la soppressione non massima per mantenere solo i minimi locali nel tuo accumulatore. E una volta che si fa questa maxima locale, scopri che qui ci sono quattro maxi che corrispondono a quattro valori o quattro parametrizzazioni di righe, che sono le quattro righe che in realtà hai nell'immagine originale. E quelli sono i punti che votavano ciascuno di quei bidoni di accumulatori. In questo modo è possibile scoprire le equazioni di quelle linee, oltre a quali punti nell'immagine originale corrispondono a quelle equazioni, per poter estrarre quella forma in quell' immagine. Quindi, è possibile trovare equazioni di linee in qualsiasi immagine data a voi utilizzando questo approccio. (13.44) Facciamo questo un po' più forte ora. Diciamo che vogliamo ora trovare cerchi in un'immagine. Abbiamo parlato di rilevamento di blocco prima, ma ora vogliamo esattamente trovare il cerchio con il suo raggio e centro ed essere in grado di parametrizzarlo perfettamente. Quindi, l'allestimento del cerchio è molto simile all'allestimento della linea, questo sarà l'allestimento che state cercando (x − x) y). 0 2 + (− y0 2 − r 2 = 0 Quali dovrebbero essere le dimensioni dell'accumulatore? Per la linea, l'accumulatore era una matrice 2D. Quale sarebbe la dimensione dell'accumulatore per l'allestimento del cerchio? (14.29) Sarebbe un accumulatore tridimensionale 3D, dove si ha x, y, che corrisponde 0 0 al centro del cerchio e r che corrisponde al raggio del cerchio. Quelli sono i tre voti che ogni punto andrà a votare. Dato che qui abbiamo tre possibilità, un'opzione è quella di fissare uno dei parametri e generalmente si fissa il raggio e poi si cerca il resto, chiedere ad ogni punto di votare qual è il centro e poi si può continuare ad andare in giro e andare in giro per un round Robin per assicurarsi che ogni punto funzioni per tutti e tre i parametri alla fine. Così, continuate ad incrementare l'accumulatore per ogni voto che un punto fa a ciascuno di questi valori e alla fine si fa una maxima locale in un, e in questo modo si può effettivamente stimare la parametrizzazione del cerchio che si sta cercando. Ecco un'illustrazione visiva, dove date una serie di monete in un'immagine, in realtà si può ora scoprire dove risiedono quelle monete e qual è il raggio di quella moneta per primi spigoli. Quindi, in questo, bisogna prima estrarre i bordi e quindi essere in grado di utilizzare quelle informazioni edge per poter trovare le esatte parametrizzazioni sulla superficie. Quindi quando dico parametrizzazioni, intendo definire i centri e i raggi di ognuno di quei cerchi che hai, (15.56) Non hai bisogno di fermarti con solo linee o cerchi, puoi ovviamente farlo per qualsiasi altra forma. Finché si può parametrizzare qualsiasi forma in modo analitico, è possibile dare una serie di equazioni per definire una forma. Tutto quello che devi fare è prendere un punto nella tua immagine originale e chiederti di votare per quello che sarebbero i parametri di un poligono a cui quel punto appartiene o si trova. E poi basta contare quale parametrizzazione ha ottenuto i voti più alti tra tutte le possibilità nel proprio spazio di parametro, e semplicemente definire che per essere il poligono o qualsiasi forma che state cercando. Ma cosa, se cercate la forma che non ha alcuna descrizione analitica. Ad esempio, su questa slide si vede questa forma irregolare, che non ha alcuna distribuzione analitica, che non ha alcuna definizione analitica. Come si stima, come si trovano tali forme in un'immagine? Suppitiamo che la forma ci abbia dato. Quindi, sai che questa è la forma che stai cercando in una data immagine e potrebbe essere di dimensioni diverse, potrebbe essere ruotata in modi diversi, potrebbe essere scalata, tutte quelle trasformazioni sono possibili. Ma vogliamo trovare dove nell'immagine si trova. L'unica cosa che sappiamo è che la forma in questo caso particolare potrebbe non avere una definizione analitica. Non si può scrivere come un'equazione. Cosa si fa in questo caso particolare? Si definisce un punto di riferimento nella forma. Come si potrebbe definire, ad esempio, un x naught y naught come punto di riferimento in quella forma e ora ogni punto edge di questa forma può essere definito rispetto a quel punto di riferimento. Quindi ogni punto qui (x, y) ha una certa lunghezza dal tuo punto di riferimento (x,) e un certo angolo rispetto al punto di riferimento 0 y0 (x,). Come esempio, potrebbe essere il centroide di quell' oggetto che state cercando. 0 y0 (x,) 0 y0 Ma non serve che sia il centroide, potrebbe essere qualsiasi punto di riferimento. Quindi, una volta che hai un centroide o qualsiasi altro punto di riferimento, per ogni punto di bordo che hai, quindi ricordati ancora, che data una nuova immagine, devi prima fare un rilevamento di bordo per ottenere i punti di bordo. Poi per ogni punto di bordo si calcola qual è la distanza al centroide. Lo faresti per primo per l'oggetto modello che hai prima di eseguirlo su qualsiasi nuova immagine. Questo quando si sa che questa è la forma che state cercando, si definisce un punto di riferimento per ogni punto di bordo in questa particolare forma, si calcola una distanza al centroide, che è r e un ogni orientamento. i Io Io faccio e poi si crea qualcosa chiamato un tavolo r. E quello che dice il tavolo r è che, per un determinato orientamento all'orientamento, quali sono tutte le possibilità? Quali sono tutti i punti che potrebbero avere un 1 di radii con lo stesso orientamento, rispetto al punto di riferimento? Allo stesso modo, per un altro punto con un altro orientamento di orientamento, diciamo che è questo particolare punto di bordo. Che 2 ϕ2 ha un certo raggio rispetto al punto di riferimento. Analogamente, potrebbe esserci un altro punto con lo stesso angolo, che avrebbe un certo raggio r21, potrebbe esserci un terzo punto con lo stesso angolo, stesso orientamento dell'immagine e che potrebbe avere un raggio r e si crea una tabella r 23, che connette questi orientamenti e queste distanze a quel centroide del punto di riferimento. Così una volta che avete costruito questo tavolo di r, cosa facciamo? (19.31) Ecco l'algoritmo di quello che è noto come Generalized Hough Transform. Quindi, hai i tuoi dati. Ti viene data la tua tabella r, che hai già costruito dalla forma che ti è stata data. Ricorda ancora una volta, che la forma è definita per te. Non definito è dato a te, non è ben definito matematicamente te stesso. Usando quella forma si costruiscono qualcosa chiamato tabella r e si costruiscono anche una matrice di accumulatori per quante dimensioni bisogna stimare. Quindi, se quel punto di riferimento ha due coordinate, si hanno solo due coordinate per votare. In caso contrario, anche tu potresti avere altri parametri. Se permettete alla vostra forma di cambiare in più modi, potreste avere altre dimensioni nel vostro accumulatore per cui anche i punti possono votare. In questo caso particolare, per mantenerlo semplice, suppamiamo che la forma sia la stessa, solo che la forma potrebbe essere posizionata ovunque nell'immagine. Nessuna scaletta, nessuna rotazione. Suppamiamo che questo sia lo scenario qui. Quindi, l'unica cosa che stiamo cercando di trovare è dove sarebbe il centroide di quell' oggetto? Quindi, si ha una matrice accumulata, che è di due dimensioni che vanno da X a, cmin Xcmax Y cm a Y c sono i valori massimi che il centroide può assumere nell'asse X. in max similare, Y c e. E iniziate l'accumulatore, ogni cellula dell'accumulatore min Y cmax a 0. Poi per ogni punto per ogni ri, immerso nella tua tabella r, prova a scrivere se il tuo centroide può essere scritto come questo x + r,. i cos / i cos io y + ri peccato di peccato Se riesci a scrivere il tuo centroide rispetto a questo, dato x y usando questa particolare formula, aumenteresti l'accumulatore per quel particolare centroide. E continuate a farlo per varie possibilità di centrocampo diverse, dove le vostre possibilità di centrocampo arriveranno da Xc a e verso, dove screditate le vostre possibilità di centroide e min Xcmax Y cmin Y cmax si crea una matrice accumulativa. Questo è il modo in cui lo faresti. E alla fine si otterrebbe una serie di valori, un insieme di frequenza conta su quello che ogni x y ha votato e si fa una soppressione non massima per trovare la maxima locale e che vi darà il xc yc finale che corrisponde a questa nuova serie di punti che vi vengono date. Parlando in termini di immagini. Ancora una volta, supponiamo che questa sia la forma che state cercando. Come ho detto, assumiamo in questo esempio qui, che stiamo solo cercando la forma come è, nessuna modifica di scala non cambia rotazione. Quindi, il che significa che l'unica cosa che può cambiare è il centro dell'oggetto potrebbe essere tutte parti diverse. Quindi, ecco perché si vota solo per dove si trova il centro. E così data una nuova immagine, si esegue un rilevatore di bordo e per ogni punto di bordo, lasciatelo lavorare per dove il centroide sarebbe e ovunque si ottenga il massimo dei voti per il centroide è dove potenzialmente potrebbe essere il vostro centroide. Potresti usare questo tipo di approccio per dire, trovare un'auto in un'immagine. Se sapevi che un'auto ha una forma particolare, hai definito quella forma, ora chiedi ad ogni, corri un rilevatore di bordo sulla nuova immagine, e poi chiedi a ogni punto sul bordo di votare per dove si trova il centro dell'auto e in base a quello, puoi probabilmente risalire dove si trova l'auto nell'immagine data. Quindi, si potrebbe usare un tale approccio anche per il rilevamento degli oggetti. Di nuovo, all'interno di cambiamenti improvvisi nelle tue forme nelle possibilità della forma. Se la posa di un'auto cambia completamente, ovviamente questo tipo di approccio non funzionerà in quello scenario. Quindi, funziona solo con una certa tolleranza. (23.23) Per riassumere l'Hough Transform, è un approccio efficace per il rilevamento delle forme, degli oggetti, tra cui si dice multiplo, anche se ci fossero più auto, probabilmente potete trovarle tutte. Si potrebbe avere più maxima in dove, i bordi votano per i centroidi delle auto e ognuno di essi può essere istanze diverse di un'auto in una determinata immagine. Quindi, è possibile utilizzare anche questo per il rilevamento di più istanze di oggetto in un'immagine. I vantaggi dell'Hough Transform è che si occupa di occlusione abbastanza bene perché si tratta di una procedura di voto. Finché il numero dei voti è alto, non importa se certi voti sono andati male. Quindi, anche se una certa parte dell'oggetto era occlusa può funzionare. Ovviamente, se una parte significativa dell'oggetto è occlusa non funzionerà. Inoltre è robusto anche per il rumore per lo stesso motivo, perché basti guardare a determinate serie di pixel, e finché votano per una maggioranza, come maggiorenne, si va a prendere la tua forma o oggetto nell'immagine. Il problema qui è che può essere computazionalmente costoso perché a seconda di come si quantizza lo spazio dei parametri. Ricordate che ogni punto deve gettare un voto per diverse possibilità nel vostro spazio di parametro, che può essere tempo di consumazione. E impostare i tuoi parametri e quantizzarli potrebbe non essere facile per diversi tipi di forme. Per la linea, il cerchio e alcune forme realmente definite, può essere semplice, per certe altre forme questo potrebbe non essere facile o quantizzarle potrebbe non dare risposte molto precise. Quelle sono alcune limitazioni al lavoro con qui. (25:02) Ecco la visualizzazione dell'esempio dell'auto. Quindi, hai un'immagine modello e ci sono alcuni punti chiave rispetto a un punto di riferimento al centro dell'immagine. Quindi, si registrano le coordinate relative al punto di riferimento nell'immagine del modello e per ogni immagine di prova, si cerca la stessa configurazione dei punti chiave rispetto al centroide dell'oggetto. (25:37) Quindi, in questi casi particolari, l'auto è invertita, ma quando l'immagine di prova è dello stesso confismo dell'oggetto originale troverete una corrispondenza in questo particolare scenario. (25:47) Ecco un altro esempio. Quindi se si considera la vostra immagine modello la Torre Eiffel ed ecco un'immagine di prova che è anche la Torre Eiffel scattata in una scala diversa in un giorno diverso con diverse condizioni di illuminazione. (26:02) Hai poi il tuo accumulatore dopo aver trovato i punti immagine del tuo modello nella tua immagine originale e la tua immagine di prova, hai il tuo accumulatore che vota per il centroide dell'oggetto rispetto a vari punti chiave di quell' oggetto. Si considera una maxima locale, non si vede molto chiaramente qui, ma la maxima locale è da qualche parte in mezzo. (26:29) E in base a quella si vota per dove si trova la Torre Eiffel nell'immagine di prova. (26:36) Il tuo lavoro a domicilio per questa lezione è il capitolo 4,3 del libro di Szeliski e un paio di domande a cui pensare. Come si farebbe a Hough Transform per rilevare le ellissi, le piazze e i rettangoli? Cercate di capire quali sono le parametrizzazioni o le forme analitiche di ciascuna di queste forme e cercate di scoprire come la matrice degli accumulatori guarderebbe in ognuno di questi casi. Questo dovrebbe aiutarti ad affrontare questi problemi. E un caso di uso real-world. Suppamiamo che il tuo amico che lavora in una startup diagnostica ti chiede come contare il numero di globuli rossi in un campione di sangue automaticamente? Quindi si ha un campione di sangue, si desidera un modo automatizzato per contare il numero di globuli rossi che utilizzano Hough Transform. Cosa consiglieresti a lui o a lei? Qualcosa per cui pensare. E qui ci sono i riferimenti.