Hashing geometrico: Algoritmi efficienti per il riconoscimento e la corrispondenza delle immagini

Di Fouad Sabry

Cos'è l'hashing geometrico

In informatica, l'hashing geometrico è un metodo per trovare in modo efficiente oggetti bidimensionali rappresentati da punti discreti che hanno subito una trasformazione affine, attraverso estensioni esistere per altre rappresentazioni e trasformazioni di oggetti. In una fase offline, gli oggetti vengono codificati trattando ciascuna coppia di punti come una base geometrica. I restanti punti possono essere rappresentati in modo invariante rispetto a questa base utilizzando due parametri. Per ciascun punto, le sue coordinate trasformate quantizzate vengono memorizzate nella tabella hash come chiave e gli indici dei punti base come valore. Quindi viene selezionata una nuova coppia di punti base e il processo viene ripetuto. Nella fase on-line (riconoscimento), coppie di punti dati selezionati casualmente vengono considerate come basi candidate. Per ciascuna base candidata, i restanti punti dati vengono codificati secondo la base e le possibili corrispondenze dell'oggetto si trovano nella tabella precedentemente costruita. La base candidata è accettata se un numero sufficientemente elevato di punti dati indicizza una base di oggetti coerente.

Come trarrai vantaggio

(I) Approfondimenti, e convalide sui seguenti argomenti:

Capitolo 1: Hashing geometrico

Capitolo 2: Geometria analitica

Capitolo 3: Sistema di coordinate cartesiane

Capitolo 4: Grafica computerizzata 2D

Capitolo 5: Sistema di coordinate

Capitolo 6: Traslazione (geometria)

Capitolo 7: Trasformata di Hough

Capitolo 8: Trasformazione di caratteristiche invarianti di scala

Capitolo 9: Omografia

Capitolo 10: Apprendimento delle caratteristiche geometriche

(II) Rispondere alle principali domande del pubblico su hashing geometrico.

(III) Esempi reali dell'utilizzo dell'hashing geometrico in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che vogliono andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di hashing geometrico.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 11 mag 2024

Anteprima del libro

Capitolo 1: Hashing geometrico

Ci sono espansioni a varie rappresentazioni e trasformazioni di oggetti, ma in informatica, l'hashing geometrico viene utilizzato per localizzare in modo efficiente oggetti in due dimensioni rappresentate da punti discreti che hanno subito una trasformazione affine. In modalità offline, ogni coppia di punti viene utilizzata come base geometrica per la codifica degli oggetti. Due parametri consentono una rappresentazione invariante in base dei punti rimanenti. La tabella hash mantiene una coppia di valori: gli indici dei punti base per ogni chiave e le coordinate convertite quantizzate per ogni valore. La procedura viene quindi ripetuta, questa volta utilizzando un diverso set di punti base. Nella fase online (di riconoscimento), gli abbinamenti arbitrari di punti dati vengono valutati come potenziali basi. Al fine di trovare corrispondenze fattibili tra l'oggetto e ciascuna base candidata, i punti dati rimanenti vengono codificati in base alla base. Se una frazione sufficientemente grande dei punti dati punta a una base di oggetto costante, viene accettata la base candidata.

Nella visione artificiale, l'hashing geometrico è stato proposto per la prima volta per il riconoscimento di oggetti 2D e 3D, il riconoscimento di oggetti utilizzando l'hashing geometrico.

Supponiamo di voler verificare se un'immagine del modello può essere vista in un'immagine di input.

L'hashing geometrico è un metodo che può essere utilizzato per raggiungere questo obiettivo.

La tecnica potrebbe essere utilizzata per identificare un singolo oggetto tra i tanti in un database, In questo scenario, la tabella hash deve tenere traccia sia dei dati di posa che dell'indice di base del modello a oggetti.

Al fine di mantenere l'esempio semplice, useremo semplicemente alcune caratteristiche puntiformi e assumeremo che le loro descrizioni provengano esclusivamente dalle loro coordinate (in pratica i descrittori locali come SIFT potrebbero essere usati per l'indicizzazione).

Impara le caratteristiche distintive del modello.

Si supponga che nell'immagine del modello si trovino 5 punti caratteristici con le coordinate (12,17); (45,13); (40,46); (20,35); (35,25) , visualizzare la fotografia.

Fornire una base per descrivere le coordinate dei punti caratteristici.

I due punti che forniscono la base per una trasformazione di similarità nello spazio bidimensionale.

Il punto di partenza si trova a metà della linea che unisce i due punti (P1, P2), il P4 del nostro caso di studio, l' x' asse è diretto verso uno di essi, è y' ortogonale e passa per l'origine.

La scala viene selezionata in modo tale che il valore assoluto di x' per entrambi i punti base sia 1.

Spiega dove si trovano le cose in relazione a quel fondamento, ad es.

Calcola le trasformazioni ai nuovi assi.

Per rendere il riconoscimento più resistente al rumore, le coordinate devono essere discretizzate, viene utilizzato un contenitore da 0,25 unità.

Otteniamo così le coordinate (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

Utilizzare una tabella hash con le feature come indice per memorizzare la base (in questo caso solo le coordinate trasformate). Il numero di articoli da memorizzare con la coppia di base se ce ne sono più di due con cui abbinare.

Passare a una nuova coppia di basi e proseguire da lì (passaggio 2). Per affrontare le occlusioni, questo è essenziale. Tutte le coppie che non sono lineari dovrebbero idealmente essere elencate. Dopo due iterazioni, in cui viene scelta la coppia (P1, P3), presentiamo la tabella hash.

Tabella hash:

La maggior parte delle tabelle hash non consente l'associazione di chiavi duplicate a valori separati.

Quindi nella vita reale non si codificheranno le chiavi di base (1.0, 0.0) e (-1.0, (tabella hash, valore 0).

Individua i punti di attrazione visiva nell'immagine data.

Scegli un punto di partenza casuale. L'immagine di input probabilmente non contiene l'elemento di destinazione se non esiste un'adeguata base arbitraria per determinare se è presente o meno.

Specificate in dettaglio le posizioni dei punti di feature del nuovo sistema di coordinate. Eseguire la quantizzazione tradizionale delle coordinate risultanti.

Verificare le feature punto convertite dell'immagine di input rispetto alla tabella hash. Nel caso in cui le feature puntuali siano uguali o molto simili, è necessario aumentare il conteggio per la base pertinente (e il tipo di oggetto, se presente).

Se il conteggio di una determinata base è maggiore di una certa soglia, è probabile che questa base corrisponda a una base di immagine selezionata nel passaggio 2. Per fare ciò, convertiamo prima il sistema di coordinate dell'immagine in quello del modello (per l'oggetto fittizio). Se funziona, l'elemento viene individuato. In caso contrario, tornare al passaggio precedente.

Sembra che le uniche trasformazioni che questo approccio può gestire siano quelle di dimensione, posizione e orientamento. Tuttavia, l'elemento potrebbe già esistere nell'immagine fornita in un formato immagine speculare. Di conseguenza, l'oggetto deve essere individuabile anche mediante hashing geometrico. Gli oggetti specchiati possono essere identificati in due modi diversi.

Rendi positivo il lato sinistro del grafico vettoriale e negativo il lato destro. Per ottenere lo stesso risultato quando si moltiplica per x, basta aggiungere -1.

Usa una triade come punto di partenza. Ciò consente l'identificazione di riflessi (o oggetti). Un altro metodo di hashing geometrico utilizza un insieme di tre punti come base.

L'hashing funziona in modo simile per i dati di dimensioni superiori, come mostrato sopra. Per la base dei dati tridimensionali sono necessari tre punti. L'asse x è definito dai primi due punti e l'asse y dal terzo (con il primo punto). Usando la regola della mano destra, è possibile costruire un asse e l'asse z sarà perpendicolare ad esso. La base risultante è sensibile alla sequenza in cui vengono inseriti i punti.

{Fine Capitolo 1}

Capitolo 2: Geometria analitica

La geometria analitica, spesso chiamata geometria delle coordinate o geometria cartesiana, è una branca della matematica che si occupa dello studio della geometria da una prospettiva cartesiana. La geometria sintetica è l'opposto di questo.

La fisica, l'ingegneria, l'aviazione, la missilistica, la scienza spaziale e i viaggi spaziali fanno tutti uso della geometria analitica. È la base per diverse branche della geometria contemporanea, come la geometria algebrica, differenziale, discreta e computazionale.

Quando si lavora con equazioni che coinvolgono piani, rette e cerchi, viene in genere utilizzato il sistema di coordinate cartesiane. In geometria si studiano il piano euclideo bidimensionale e lo spazio euclideo tridimensionale. La geometria analitica, come viene tipicamente definita e insegnata nei libri di testo, si occupa di creare e rappresentare forme geometriche in senso numerico e di estrarre informazioni numeriche da queste rappresentazioni. L'assioma di Cantor-Dedekind garantisce che i calcoli nella geometria del continuo lineare possano essere eseguiti usando solo l'algebra dei numeri reali.

È stato sostenuto che il matematico greco Menecmo sviluppò la geometria analitica a causa del suo uso di una tecnica che assomigliava all'uso delle coordinate nella risoluzione dei problemi e nella dimostrazione dei teoremi.

Il matematico persiano dell'XI secolo Omar Khayyam vide una forte relazione tra geometria e algebra e si stava muovendo nella giusta direzione quando contribuì a colmare il divario tra l'algebra numerica e quella geometrica:

La geometria analitica è stata inventata indipendentemente da René Descartes e Pierre de Fermat, la geometria cartesiana, sinonimo di geometria analitica, porta il nome di Cartesio.

Cartesio fece progressi significativi con i metodi in un saggio intitolato La Géométrie (Geometria), un'appendice al suo Discorso sul metodo per dirigere rettamente la propria ragione e cercare la verità nelle scienze, pubblicato nel 1637, Discorso sul metodo è un nome popolare per questo lavoro.

La Geometrie, composta interamente nella sua prima lingua, il francese, i suoi fondamenti teorici, ecc., ha gettato le basi per lo sviluppo del calcolo infinitesimale in Europa.

Il lavoro è stato accolto con scetticismo in un primo momento, dovuto, in parte, a causa dei numerosi buchi nell'argomento e della matematica ingarbugliata.

Il capolavoro di Cartesio non fu riconosciuto per quello che era fino a quando van Schooten non lo tradusse in latino e aggiunse un commento nel 1649 (e dopo aver continuato a lavorarci).

Come risultato di questa scelta, Cartesio fu incaricato di risolvere equazioni più complesse, che richiedevano il perfezionamento delle tecniche per gestire equazioni polinomiali di grado maggiore.

Leonhard Euler fu il primo a studiare sistematicamente curve e superfici nello spazio utilizzando il metodo delle coordinate.

Nella geometria analitica, viene introdotto un sistema di coordinate per il piano e a ciascun punto vengono assegnati due numeri reali. Ad ogni punto nello spazio euclideo vengono assegnate tre coordinate. Il significato delle coordinate è determinato dal punto di riferimento scelto. Esistono molti sistemi di coordinate diversi, ma i seguenti sono i più comuni:

Le coordinate cartesiane, in cui ogni punto ha una coordinata x che rappresenta la sua posizione orizzontale e una coordinata y che rappresenta la sua posizione verticale, sono il sistema di coordinate più utilizzato. Questi sono in genere presentati come un'espressione accoppiata (x, y). Ogni punto nello spazio euclideo tridimensionale può essere rappresentato da una terna ordinata di coordinate usando questo metodo (x, y, z).

In notazione polare, ogni punto del piano è