Skalinvariant funktionstransformation

Scale- invariant feature transform ( SIFT ) är en  funktionsdetekteringsalgoritm i datorseende för att detektera och beskriva lokala egenskaper i bilder. Algoritmen patenterades i Kanada av University of British Columbia [1] och publicerades av David Lowe 1999 [2] . Tillämpningar inkluderar objektigenkänning kartläggning och navigering, bildsömnad , -modellering , gestigenkänning , spårning , identifiering av vilda djur och positionsspårning .

Först extraheras nyckelpunkter för objekt i SIFT från en uppsättning referensbilder [2] och lagras i databasen. Ett objekt känns igen i en ny bild genom att jämföra varje objekt från den nya bilden med funktioner från databasen och hitta kandidategenskaper baserat på det euklidiska avståndet mellan funktionsvektorer. Från den fullständiga uppsättningen matchningar i den nya bilden väljs delmängder av nyckelpunkter som bäst matchar objektet vad gäller dess plats, skala och orientering. Att fastställa lämpliga funktionsblock går snabbt med en effektiv hashtabellimplementering av den generaliserade Hough-transformen . Varje block med 3 eller fler funktioner som överensstämmer med objektet och dess position är föremål för ytterligare detaljerad verifiering av modellpassningen, och extremvärden kasseras. Slutligen beräknas sannolikheten att en viss uppsättning funktioner indikerar närvaron av ett objekt, vilket ger information om matchningens noggrannhet och antalet möjliga missar. Objekt som klarar alla dessa tester kan anses vara korrekta med hög grad av säkerhet [3] .

Översikt

För alla objekt i en bild kan särdrag extraheras för att ge en "funktionsbeskrivning" av objektet. Denna beskrivning erhållen från träningsbilden kan sedan användas för att identifiera objektet när man försöker lokalisera objektet i en testbild som innehåller många andra objekt. För tillförlitlig igenkänning är det viktigt att funktionerna som extraheras från träningsbilden kan upptäckas även med förändringar i bildskala, brus och ljus. Sådana prickar ligger vanligtvis i områden med hög kontrast, såsom kanterna på föremål.

En annan viktig egenskap hos dessa funktioner är att de relativa positionerna mellan dem inte bör ändras från en bild till nästa. Till exempel, om bara de fyra hörnen på en dörr användes som tecken, skulle de fungera oavsett dörrens placering. Men om dörrkarmen också användes, kan identifieringen misslyckas eftersom dörren kan vara öppen eller stängd. Likaså fungerar inte funktioner som placeras på ledade eller flexibla objekt i allmänhet om någon förändring i intern geometri sker mellan två bilder i bearbetningsuppsättningen. Men i praktiken upptäcker och använder SIFT ett mycket större antal bildfunktioner, vilket minskar bidraget från varje fel som orsakas av dessa lokala ändringar till det totala felet för alla funktionsmatchningsfel.

SIFT [1] kan på ett tillförlitligt sätt välja objekt även i närvaro av brus och partiell överlappning, eftersom SIFT-funktionsbeskrivningen är oföränderlig till proportionell skalning , orientering , ljusändringar och är delvis invariant till affina distorsioner [2] . Det här avsnittet beskriver den ursprungliga SIFT-algoritmen och nämner flera konkurrerande tekniker tillgängliga för bullriga och överlappande objektigenkänning.

SIFT-deskriptorn är baserad på bildmätningar i termer av receptorfält [4] [5] [6] [7] , för vilka lokala skalinvarianta referensramar [8] [9] upprättas genom att välja en lokal skala [10] [11] [9] . En allmän teoretisk förklaring av algoritmen ges i Scholarpedia-projektet om SIFT [12] .

En uppgift Metod Fördel
nyckelplacering / skala / rotation Gaussisk skillnad / pyramid av rymdskalor / tilldelning av riktningar noggrannhet, stabilitet, skala och rotationsinvarians
geometrisk distorsion oskärpa/omsampling av lokala bildorienteringsplan affin invarians
indexering och matchning närmaste granne / sök "Best Bin First" Effektivitet / hastighet
Klusteridentifiering Hough transformera rösta pålitliga positionsmodeller
Modellvalidering / detektering av extremvärden Linjära minsta kvadrater bättre feltolerans med mindre överensstämmelse
Hypotesgodkännande Bayesiansk sannolikhetsanalys pålitlighet

Grundläggande steg

Detektering av skalinvarianta egenskaper

Lowes metod för att generera bildegenskaper omvandlar bilden till en stor uppsättning funktionsvektorer, som var och en är oföränderlig under (parallell) bildöversättning, skalning och rotation, delvis invariant mot ljusförändringar och resistenta mot lokala geometriska distorsioner. Dessa egenskaper har liknande egenskaper som neuroner i den huvudsakliga visuella cortex som kodar för grundläggande form, färg och objektrörelsedetektion i primatsyn [13] . Placeringsnycklarna definieras som det maximala och minimum av Gaussisk skillnadsfunktion tillämpas i skalutrymme på en serie utjämnade och återrenderade bilder. Kandidatpunkter med låg kontrast och punkter längs kanterna kasseras. Lokaliserade nyckelpunkter tilldelas dominerande orienteringar. Dessa steg ger mer stabilitet för nyckelpunkter för matchning och igenkänning. SIFT-deskriptorer som är resistenta mot lokala affina överträdelser erhålls sedan genom att titta på pixlarna runt nyckelplatsen genom att sudda ut och omsampla de lokala bildorienteringsplanen.

Funktionsmatchning och indexering

Indexering består av att komma ihåg SIFT-nycklarna och identifiera motsvarande nycklar från den nya bilden. Lowe använde en modifiering av en k-dimensionell trädalgoritm som kallas best-bin-first (BBF) [14] sökmetoden , som kan identifiera närmaste granne med hög sannolikhet med hjälp av endast ett begränsat antal beräkningar. BBF-algoritmen använder en modifierad sökordning för den k-dimensionella trädalgoritmen så att områden i objektutrymmet genomsöks i ordning efter deras närmaste avstånd från den begärda platsen. Denna sökorder kräver användning av en heap -baserad prioritetskö för att effektivt fastställa sökordningen. Den bästa kandidaten för varje nyckelpunkt hittas genom att etablera sin närmaste granne i nyckelpunktsdatabasen från träningsbilderna. Närmaste grannar definieras som nyckelpunkterna med det minsta euklidiska avståndet från den givna deskriptorvektorn. Sannolikheten för att en matchning är korrekt kan bestämmas genom att beräkna förhållandet mellan avståndet från närmaste granne och avståndet till näst närmaste granne.

Låg [3] avvisade alla matchningar där distansförhållandet är större än 0,8, vilket eliminerar 90 % av felaktiga matchningar, samtidigt som mindre än 5 % av korrekta matchningar förkastas. För att ytterligare förbättra prestandan stoppas sökalgoritmen för bästa bin-först efter att ha kontrollerat de första 200 närmaste grannkandidaterna. För en databas med 100 000 nyckelpunkter ger detta en ökning av hastigheten jämfört med den exakta grannsökningen med 2 storleksordningar, medan fel val inte går längre än 5% av de korrekta matchningarna.

Klusteridentifiering genom att rösta på Hough-transformen

Hough-transformen används för att gruppera en robust hypotesmodell för att hitta nycklar som överensstämmer med en viss modellposition Hough-transformen avslöjar kluster av funktioner med en konsekvent tolkning genom att rösta för varje funktion för alla objektpositioner som är förenliga med funktionen. När kluster av funktioner hittas med röster för samma position av ett objekt, är sannolikheten för en korrekt tolkning mycket högre än för någon enskild funktion. En hashtabellpost skapas som innehåller den uppskattade positionen, orienteringen och skalan från den matchande hypotesen. En hashtabell genomsöks för att identifiera alla kluster med minst 3 element i området, och områdena sorteras efter minskande storlek.

Var och en av SIFT-nyckelpunkterna definierar en 2D-plats, skala och orientering, och varje nyckelpunkt i databasen har en post med sina parametrar relaterade till träningsbilden där den hittades. Den analoga transformationen som resulterar från dessa 4 parametrar är endast en approximation av det fulla positionsutrymmet med 6 frihetsgrader för 3D-objekt och tar inte heller hänsyn till några flexibla deformationer. Sålunda använde Lowe [3] 30 graders områdesstorlekar för orientering för plats, en faktor 2 för skala och en faktor på 0,25 för maximal projektionsstorlek för träningsbilden (med den förutsagda skalan). För SIFT-nycklar genererade i stor skala ges dubbel vikt jämfört med nycklar för en mindre skala. Detta innebär att en större skala kan filtrera bort mer troliga grannar för att testa i mindre skala. Det förbättrar också igenkänningsprestandan genom att ge mer vikt åt en mindre bullrig våg. För att undvika problemet med gränseffekter när man tilldelar ett område, tittar varje nyckelpunkt på rösterna för de 2 närmaste områdena i varje riktning, vilket ger totalt 16 värden för varje hypotes och gör positionsspridningen ytterligare suddig.

Minsta kvadratmodellvalidering

Varje etablerat kluster är föremål för en verifieringsprocedur som utför en minsta kvadratlösning de affina transformationsparametrarna associerade med bildmodellen. En affin transformation av en modellpunkt [xy] T till en bildpunkt [uv] T kan skrivas på följande sätt

där parallell translation är [tx ty] T , och affin rotation, skala och sträckning representeras av parametrarna m1, m2, m3 och m4. För att få fram transformationsparametrarna kan ekvationen skrivas om så att alla okända är i en kolumnvektor.

Likhet visar en enda matchning, men valfritt antal matchningar kan läggas till, där varje matchning lägger till två rader till den första och sista matrisen. Det krävs minst 3 matchningar för att få en lösning. Vi kan skriva detta linjära system som

där A är en känd matris (vanligtvis m > n ), x är en okänd n - dimensionell parametervektor och b är en känd m - dimensionell dimensionsvektor.

Sålunda är minimeringsvektorn lösningen på normalekvationen

Lösningen till systemet med linjära ekvationer ges i form av en matris som kallas pseudoinversmatrisen för A , i formen

,

vilket minimerar summan av de kvadratiska avstånden för modellpositionsprojektionerna till motsvarande bildpositioner.

Identifiering av extremvärden

Outliers kan nu kasseras genom att kontrollera överensstämmelsen mellan funktionen i varje bild och modellen som ges av parameterlösningen. Givet en minsta kvadratlösning måste varje matchning inte överensstämma med mer än halva felintervallet som användes för parametrarna i Hough-transformområdena . Outliers kasseras, minsta kvadratlösningen räknas om för de återstående punkterna och processen upprepas. Om det återstår mindre än 3 poäng efter att avvikelserna kasserats , avvisas matchen. Dessutom används top-down-matchningsfasen för att lägga till andra matchningar som överensstämmer med positionen för den projicerade modellen, som kan missas av Hough-transformområdet på grund av approximation av liknande transformationer eller andra fel.

Det slutliga beslutet att acceptera eller förkasta hypotesmodellen baseras på en detaljerad probabilistisk modell [15] . Denna metod beräknar först det förväntade antalet felmatchningar för positionsmodellen, givet av storleken på modellen, antalet funktioner inom regionen och noggrannheten i passningen. Bayesiansk analys ger sedan sannolikheten för att objektet är närvarande baserat på det faktiska antalet funktionsmatchningar som hittats. Modellen accepteras om den slutliga sannolikheten för korrekt tolkning är större än 0,98. Baserat på SIFT-metoden som utvecklats av Lowe, ger objektigenkänning utmärkta resultat, förutom i fall av stor spridning av belysning och med icke-styva transformationer.

Tecken

Detektering och beskrivning av lokala bildfunktioner kan hjälpa till med objektigenkänning. SIFT-funktioner är lokala och baseras på objektets manifestationer vid specifika singulära punkter. De är skalnings- och rotationsinvarianta. De är också resistenta mot förändringar i belysning, buller och små förändringar i synvinkel. Förutom dessa egenskaper är de mycket särskiljbara, relativt lätta att hämta och tillåter objektidentifiering med lite fel. De är relativt lätta att hitta i en (stor) databas med lokala funktioner, men funktionernas höga dimensionalitet kan dock orsaka svårigheter, så probabilistiska algoritmer som k-dimensionella träd med best-bin-first search ( BBF) används. Beskrivning av ett objekt som använder SIFT-funktioner är också stabil med avseende på partiell överlappning, eftersom även tre SIFT-funktioner för ett objekt räcker för att beräkna platsen och positionen för ett objekt. Igenkänning kan utföras i nästan realtid, åtminstone för små databaser med modern datorutrustning.

Algoritm

Avslöjande extrema av skalutrymmet

Vi börjar med att identifiera punkter, som kallas nyckelpunkter inom SIFT. Bilden konvolveras med gaussiska filter i olika skalor, och sedan beräknas skillnaden mellan på varandra följande Gaussiska suddiga bilder. Nyckelpunkterna samplas sedan som den maximala/minsta skillnaden mellan Gauss som förekommer på olika skalor. Den gaussiska skillnaden ges av uttrycket

, var är faltningen av originalbilden med Gaussisk oskärpa i skala , dvs.

Därför är bilden av den Gaussiska skillnaden mellan skalor och skillnaden mellan Gaussiska suddiga bilder med skalor och . För att bestämma extremumet i skalningsutrymmet , i SIFT-algoritmen, konvolveras bilden först med Gaussisk oskärpa i olika skalor. Miniatyrerna grupperas efter oktav (en oktav motsvarar en fördubbling av värdet på ) och värdet väljs så att vi får ett fast antal miniatyrbilder per oktav. Sedan beräknas den Gaussiska skillnaden från angränsande Gaussiska suddiga bilder i en oktav.

När väl den Gaussiska skillnaden i bilden har erhållits definieras nyckelpunkterna som det lokala minimum/maximum för bildens Gaussiska skillnad över mallarna. Detta görs genom att jämföra varje pixel mot bildens Gaussiska skillnad för dess åtta grannar i samma skala och nio motsvarande angränsande pixlar vid var och en av de intilliggande skalorna. Om pixelvärdet är maximum eller minimum bland alla jämförda punkter, väljs det som en nyckelpunktskandidat.

Detta nyckelpunktsdetekteringssteg är en variant av en av Lindebergs punktdetekteringsmetoder genom att hitta extrema i skalutrymmet normaliserat till den laplaciska skalan [10] [11] . Det vill säga bestämningen av punkter som är lokala extrema, med hänsyn till både rumslig position och skala, i det diskreta fallet, genom jämförelse med de närmaste 26 grannarna i en diskretiserad volym i skalutrymme. Den Gaussiska skillnadsoperatorn kan ses som en approximation av Laplacian, med en implicit normalisering i pyramiden , som också innehåller en diskret approximation av den skalnormaliserade Laplacian [12] . En annan realtidsinkarnation av sökandet efter extrema i Laplace-operatorns skalrum presenterades av Lindeberg och Bretzner, den är baserad på en hybrid pyramidrepresentation [16] som användes för dator-mänsklig interaktion för gestigenkänning i realtid [17] .

Lokalisering av nyckelpunkter

Bestämningen av extrema i skalutrymmet ger för många kandidater för nyckelpunkter, varav några är instabila. Nästa steg i algoritmen är att utföra en detaljerad grannanpassning för den exakta platsen, skalan och det huvudsakliga krökningsförhållandet . Denna information gör att du kan kassera punkter som har låg kontrast (och därför är känsliga för brus) eller som är dåligt placerade längs kanten.

Interpolering av angränsande data för positionsnoggrannhet

För det första, för varje referenspunktskandidat, används näradatainterpolation för att exakt bestämma positionen. Det initiala tillvägagångssättet var att bestämma platsen för varje nyckelpunkt genom positionen och skalan för nyckelpunktskandidaten [2] . Den nya metoden beräknar extremumets interpolerade position, vilket avsevärt förbättrar passformen och stabiliteten [3] . Interpolationen utförs med användning av den kvadratiska Taylor-expansionen av  funktionen Difference- of -Gaussian skala-space med nyckelpunktskandidaten placerad vid origo. Denna Taylor-expansion ges av ekvationen:

,

där D och dess derivata beräknas vid kandidatpunkten och är förskjutningen från denna punkt. Placeringen av extremumet bestäms genom att ta derivatan av denna funktion med avseende på och lika med noll. Om förskjutningen är större i endera riktningen indikerar detta att extremumet ligger närmare en annan nyckelpunktskandidat. I detta fall ändras nyckelpunktskandidaten och interpolering utförs för denna punkt. Annars läggs en förspänning till nyckelpunktskandidaten för att erhålla en interpolerad uppskattning av extremumläget. En liknande subpixelbestämning av platsen för extrema av skalutrymmet, utvecklad av Lindeberg et al., utförs i realtid baserat på hybridpyramider [16] .

Ta bort nyckelpunkter med låg kontrast

För att ignorera nyckelpunkter med låg kontrast beräknas en andra ordningens Taylor-expansion med en bias . Om detta värde är mindre än , kasseras nyckelpunktskandidaten. Annars sparas den med en plats i ändlig skala , där är den ursprungliga platsen för nyckelpunkten.

Uteslutning av kantbidrag

Den Gaussiska skillnadsfunktionen kommer att ha starka värden längs kanterna, även om nyckelpunktskandidaten inte är robust mot litet brus. För att öka stabiliteten bör du därför utesluta nyckelpunkter som har en dåligt definierad plats, men som har ett stort bidrag från kanterna.

För dåligt definierade Gaussiska skillnadsfunktionstoppar kommer den huvudsakliga krökningen över en kant att vara mycket större än den huvudsakliga krökningen längs den. Att hitta dessa huvudkurvaturer motsvarar att hitta egenvärdena för den andra ordningens hessiska matrisen H :

Egenvärdena för H är proportionella mot de huvudsakliga krökningarna av matrisen D. Det visar sig att förhållandet mellan två egenvärden, säg  att det större av dem, a  är det mindre, med förhållandet , är tillräckligt för SIFTs syften . Spåret av matrisen H , dvs , ger oss summan av de två egenvärdena, medan determinanten, dvs , ger oss produkten. Förhållandet kan visas vara , vilket bara beror på förhållandet mellan egenvärdena, inte de enskilda värdena. R är minimum om egenvärdena är lika. Således, ju högre absolutvärdet är av skillnaden mellan två egenvärden, vilket är ekvivalent med det största absoluta värdet av skillnaden mellan de två huvudkurvaturerna D, desto högre är värdet på R. Det följer att för något tröskelegenvärdesförhållande , om R för nyckelpunktskandidaten är större än , då är nyckelpunkten dåligt placerad och därför kasserad. Den nya metoden använder [3] .

Detta kantsvarsundertryckande steg är att överföra det lämpliga tillvägagångssättet till Harris-operatören för hörndetektering . Skillnaden är att måttet för tröskeln beräknas från den hessiska matrisen och inte från matrisen för andra moment .

Orienteringsuppgift

I detta steg tilldelas varje nyckelpunkt en eller flera orienteringar baserat på riktningarna för gradienterna i den lokala bilden. Detta är ett nyckelsteg för att uppnå rotationsinvarians , eftersom nyckelpunktsbeskrivningen kan representeras med avseende på denna orientering och därför blir rotationsinvariant för bilden.

Först och främst tas en Gaussisk suddig bild vid nyckelpunkter med skala , så att alla beräkningar utförs på ett skalinvariant sätt. För en skalad bild är gradientvärdet och orienteringen förberäknade baserat på pixelskillnaden .

Beräkning av storleken och riktningen för gradienten görs för varje pixel i närheten av nyckelpunkten i den Gaussiska suddiga bilden L. Ett riktningshistogram bildas med 36 områden som var och en täcker 10 grader. Varje punkt i den omgivande rutan läggs till histogramområdet, viktad av gradientens storlek och av ett Gauss-vägt cirkulärt fönster med , vilket är 1,5 gånger skalan för nyckelpunkten. Topparna i detta histogram motsvarar de dominerande riktningarna. När histogrammet är fyllt tilldelas riktningar som motsvarar de högsta topparna och lokala toppar som ligger inom 80 % av de högsta topparna till nyckelpunkten. Om flera riktningar tilldelas skapas ytterligare en nyckelpunkt som har samma plats och skala som den ursprungliga punkten för varje ytterligare riktning.

Nyckelpunktsbeskrivning

De föregående stegen hittar placeringen av nyckelpunkter på specifika skalor och tilldelar dem en orientering. Detta ger invarians för punktplacering, skala och rotation. Nu vill vi beräkna en vektor av deskriptorer för varje nyckelpunkt, så att deskriptorn är väldigt olika och delvis oföränderlig för andra förändringar som belysning, synpunkter och så vidare. Detta steg utförs på bilden närmast nyckelpunktens skala i skala.

Först och främst skapas en uppsättning riktningshistogram på 4x4 angränsande pixlar med 8 områden i varje. Dessa histogram beräknas från storleks- och orienteringsvärdena för elementen i 16×16-området runt nyckelpunkten, så att varje histogram innehåller element från en 4×4-delregion av den ursprungliga grannskapsregionen. Värdena viktas ytterligare av en Gaussisk funktion som är lika med halva bredden av deskriptorfönstret. Handtaget blir då en vektor för alla värden i dessa histogram. Eftersom det finns 4×4=16 histogram med 8 regioner vardera, har vektorn 128 element. Denna vektor är normaliserad till enhetslängd för att säkerställa att den är invariant för att affinera förändringar i belysning. För att minska effekten av icke-linjär belysning tillämpas ett tröskelvärde på 0,2 och vektorn normaliseras igen. Tröskelprocessen kan förbättra matchningsresultat även om det inte finns några icke-linjära ljuseffekter [18] . Tröskelvärdet 0,2 väljs empiriskt och att ersätta ett fast tröskelvärde med ett målmedvetet beräknat kan förbättra jämförelseresultaten [18] .

Även om deskriptordimensionen (dvs. 128) verkar hög, fungerar mindre deskriptorer inte lika bra [3] och beräkningskostnaden förblir låg eftersom den ungefärliga BBF-metoden används för att hitta närmaste granne (se nedan). Längre deskriptorer skulle ge bättre resultat, men inte mycket, och det finns en risk för ökad känslighet för distorsion och aliasing. Det har också visat sig att funktionsmatchningsnoggrannheten är större än 50 % för synvinkelförändringar upp till 50 grader. Därför är SIFT-deskriptorer oföränderliga till små affina förändringar. För att testa urskiljbarheten av SIFT-deskriptorer mäts matchningsnoggrannheten också med avseende på ett annat antal nyckelpunkter i testdatabasen, och det har visat sig att matchningsnoggrannheten endast minskar något för stora databaser, vilket indikerar att SIFT-funktioner är mycket särskiljbara. .

Jämförelse av SIFT-funktioner med andra lokala funktioner

Intensiv forskning har utförts för att utvärdera effektiviteten av olika lokala deskriptorer, inklusive SIFT [19] . De viktigaste resultaten visas nedan:

  • SIFT och (liknande SIFT) GLOH funktioner ( Gradient Location and Orientation Histogram ) visar den högsta matchningsnoggrannheten för en affin transformation på 50 grader .  Utöver denna gräns blir konverteringsresultaten opålitliga.
  • Deskriptorers distinkthet mäts genom att summera egenvärdena för deskriptorerna som erhålls med huvudkomponentmetoden för deskriptorer normaliserade med varians. Detta motsvarar mängden varians som motsvarar olika deskriptorer, och därför deras distinktion. Funktioner PCA-SIFT (Principal Component Method tillämpad på SIFT-deskriptorer), GLOH och SIFT ger de högsta värdena.
  • SIFT-baserade deskriptorer överträffar andra moderna lokala deskriptorer för både texturerade och strukturerade scener, samtidigt som de är mer effektiva för texturerade scener.
  • För 2-2,5x zoom och bildrotation mellan 30 och 45 grader överträffar SIFT- och SIFT-baserade deskriptorer återigen andra moderna lokala deskriptorer för strukturerade och strukturerade scener.
  • Oskärpa (suddighet) påverkar alla lokala deskriptorer, särskilt de som baseras på gränser (kanter), som algoritmen "formkontext" (formkontext ), eftersom kanter försvinner vid kraftigt suddiga gränser. Men GLOH, PCA-SIFT och SIFT fortsätter att prestera bättre än resten. Detta gäller även vid belysningsförändringar.

Testerna som genomfördes tyder starkt på att SIFT-baserade deskriptorer är de mest stabila och urskiljbara, och därför de mest rekommenderade för funktionsmatchning. Men nyligen utvecklade funktionsbeskrivningar som SURF har inte undersökts i dessa försök.

SURF har visat sig ha en effektivitet nära SIFT, men samtidigt är algoritmen mycket snabbare [20] . Andra studier har visat att när hastighet inte är en kritisk faktor överträffar SIFT SURF [21] [22] . I synnerhet, om man bortser från samplingseffekter, är SIFT-bilddeskriptorn betydligt bättre än SURF-bilddeskriptorn. Samtidigt består extremumet i skalutrymmet för determinanten av hessian för den enkla singularpunktsdetektorn i SURF av betydligt bättre singularpunkter jämfört med extremumet i skalutrymmet för Laplacian, för vilken algoritmen för att bestämma singular punkt i SIFT utför en numerisk approximation [21] .

Bildmatchningsprestanda för SIFT-deskriptorer kan förbättras när det gäller att uppnå högre prestanda och lägre 1-noggrannhetspoäng[ förtydliga ] ( engelska  1-precisionspoäng ) genom att ersätta det skalbara rumsliga extremumet för den Gaussiska skillnadsoperatorn i den ursprungliga SIFT med extremumet för den hessiska determinanten i det skalbara rummet, eller genom att överväga en mer allmän familj av generaliserade singularpunkter i skalbart utrymme [21] .

Nyligen har en något modifierad version av deskriptorn föreslagits, med användning av ett oenhetligt histogramgitter, vilket avsevärt förbättrar kvaliteten [23] . Istället för att använda ett 4x4-rutnät av histogramregioner expanderar alla regioner mot mitten av objektet. Detta förbättrar deskriptorernas motståndskraft mot skalförändringar.

SIFT-Rank-deskriptorn [24] har visat sig förbättra prestandan för standard SIFT-deskriptorn för affin funktionsmatchning. SIFT-Rank-deskriptorn genereras från standard-SIFT-deskriptorn genom att tilldela varje område i histogrammet en rangordning i en sorterad uppsättning områden. Det euklidiska avståndet mellan SIFT-Rank-deskriptorer är invariant under godtyckliga monotona förändringar i histogramvärden och är relaterat till Spearmans rangkorrelationskoefficienter .

Applikationer

Objektigenkänning med SIFT-funktioner

Om det är möjligt för ett SIFT-system att hitta olika nyckelpunkter som är oföränderliga i läge, skala och rotation och som är resistenta mot affina transformationer (förändringar i skala , rotation , shift och position) och förändringar i belysning, de är användbara för objektigenkänning. Dessa steg ges nedan

  • Först erhålls SIFT-funktioner från ingångsbilden med användning av algoritmen som beskrivs ovan.
  • Dessa funktioner matchas mot databas SIFT-funktioner erhållna från träningsbilder. Denna funktionsmatchning görs med den euklidiska närmaste grannmetoden. För att öka stabiliteten kasseras matchning för nyckelpunkter för vilka förhållandet mellan avståndet till närmaste granne och avståndet till näst närmaste granne är större än 0,8. Detta förkastar många falska matchningar som uppstår från bakgrundsstörande bilder. Slutligen, för att undvika den kostsamma sökningen som krävs för att hitta den euklidiska närmaste granne, används en ungefärlig algoritm som kallas "bästa-bin-först" [14] . Detta är en snabb metod som returnerar närmaste granne med hög sannolikhet och kan påskynda sökprocessen med en faktor 1000, medan det tar 95 % av tiden att hitta närmaste granne.
  • Även om avståndsförhållandetestet som beskrivs ovan kastar bort många falska matchningar som uppstår från bakgrundsstörande bilder, kvarstår vi med matchningar som tillhör andra objekt. Därför, för att öka tillförlitligheten för objektidentifiering, vill vi klustra funktionerna som hör till samma objekt och kassera de matchningar som finns kvar efter klustringsprocessen. Detta görs med hjälp av Hough-transformen . Den identifierar funktionskluster som röstar för någon objektposition. När kluster av objekt hittas med röster för någon position av objektet, kommer sannolikheten för korrekt tolkning att vara mycket högre än för en enskild funktion. Varje nyckelpunkt röstar för en uppsättning funktionspositioner om de överensstämmer med nyckelpunktens plats, skala och orientering. Områden som samlar minst 3 röster anses vara kandidater för objekt/positionsmatchning.
  • För varje klusterkandidat får vi en lösning med minsta kvadrater för de bästa affina projektionsuppskattningarna som relaterar träningsbilderna till ingångsbilden. Om projektionen av nyckelpunkten genom dessa parametrar ligger inom hälften av felintervallet som användes för parametrarna i Hough-transformområdena, bibehålls nyckelpunktsöverensstämmelsen. Om mindre än 3 poäng återstår efter att avvikelserna för regionerna kasserats, avvisas matchningen för objektet. Minst kvadratiska montering upprepas så länge som något kan kasseras. Detta fungerar bättre för platta objektigenkänning, men inte för 3D-objektigenkänning eftersom den affina modellen blir opålitlig för 3D-objekt.
  • Uppsatsen av Sirmachek och Unsalan [25] föreslår ett nytt tillvägagångssätt för att använda SIFT-deskriptorer för att allokera flera objekt. Den föreslagna metoden för detektering av flera objekt testades på flyg- och satellitbilder.

SIFT-funktioner kan i princip tillämpas på alla problem där bildmatchning krävs. Arbete kan utföras med applikationer som igenkänning av specifika kategorier av objekt i 2D-bilder, rekonstruktion av 3D-objekt, rörelsespårning och segmentering, robotlokalisering, panoramabildsömmar och epipolär kalibrering . Några av dessa applikationer diskuteras mer i detalj nedan.

Robotens plats och kartan

Denna applikation [26] använder ett stereo trinokulärt system för att uppskatta 3D-platsen för en referenspunkt. Nyckelpunkter används endast när de förekommer i alla tre bilderna med konsekventa felmatchningar, vilket resulterar i mycket sällsynta bortfall. När roboten rör sig bestämmer den sin plats med hjälp av funktionsrelationer med den befintliga 3D-kartan, och lägger sedan stegvis till funktioner till kartan samtidigt som den uppdaterar 3D-positionen med hjälp av ett Kalman-filter. Detta ger en pålitlig och korrekt lösning på problemet med att lokalisera en robot i en okänd miljö.

Panoramasömmar

SIFT-funktionsmatchning kan användas för bildsammansättning för helautomatisk panoramakonstruktion från ramar utan panorama. SIFT-funktionerna som extraherats från ingångsbilderna matchas mot varandra för att hitta k närmaste grannar i varje bild. Dessa matchningar används sedan för att hitta m bildmatchande kandidater för varje bild. Homografierna mellan bildpar beräknas sedan med RANSAC ( Random sample consensus ) och en probabilistisk modell används för verifiering .  Eftersom det inte finns några begränsningar för ingående bilder, tillämpas en grafsökning på de anslutna bildmatchningskomponenterna så att varje ansluten komponent matchar ett panorama. Slutligen, för varje ansluten komponent, utförs blockjustering för att lösa kameraparametrarna, och panoramat bearbetas med flerbandsblandning . På grund av det SIFT-inspirerade tillvägagångssättet för objektigenkänning för panoramasömmar är det resulterande systemet okänsligt för bildordning, orientering, skala och belysning. Ingångsbilderna kan innehålla flera panoramabilder och bildbrus (av vilka vissa kanske inte ens ingår i den sammansatta bilden) [27] .  

3D-scenmodellering, igenkänning och spårning

Denna applikation använder SIFT-funktioner för 3D-objektigenkänning och 3D-modellering samband med förstärkt verklighet , där de skapade konstgjorda objekten i en exakt pose överlagras på verkliga bilder. En SIFT-matchning definieras för flera 2D-bilder av en scen eller ett objekt tagna från olika vinklar. Detta används med blockjustering för att bygga en sparsam 3D-modell av scenen i fråga och samtidigt återställa kamerapositioner och kalibreringsparametrar. Sedan bestäms det virtuella objektets position, orientering och storlek i förhållande till ramkoordinaterna för den övervägda modellen. För positionsspårning online extraheras SIFT-funktioner från den aktuella videobilden och matchas mot redan beräknade funktioner, vilket resulterar i en uppsättning 2D-till-3D-matchningar. Dessa matchningar används sedan för att beräkna den aktuella kamerapositionen för virtuell projektion och slutbehandling. Regulariseringstekniken används för att minska jitter i den virtuella projektionen [28] . SIFT 3D-tillägg har också implementerats för att känna igen och markera verkliga 3D- objekt [29] [30] .

3D SIFT-liknande deskriptorer för att känna igen mänskliga handlingar

Utvidgningar av SIFT-deskriptorn till 2+1-dimensionella rumsliga data har studerats i samband med att identifiera mänskliga handlingar i video [29] [31] [32] [33] . Skapandet av lokala positionsberoende histogram i 2D SIFT-algoritmen expanderar från 2D till 3D för att beskriva SIFT-funktionerna i rum-tidsdomänen. För tillämpning på igenkänning av mänskliga handlingar i video utförs träningsvideor antingen från specifika spatiotemporala punkter eller på en slumpmässig plats, tid och skala. Rum-tidsregionerna runt dessa singulära punkter beskrivs sedan med hjälp av en 3D SIFT-deskriptor. Dessa deskriptorer sätts sedan samman till en " påse med ord " spatiotemporal modell . 3D SIFT-deskriptorer som extraherats från testklipp matchas mot dessa ord för att klassificera mänskliga handlingar.

Författarna hävdar att deras 3D SIFT-deskriptor presterar betydligt bättre än andra tillvägagångssätt som enkla 2D SIFT-deskriptorer och gradientvärde [34] .

Analys av den mänskliga hjärnan i 3D Magnetic Resonance Imaging

Den funktionsbaserade morfometritekniken ( FBM ) [35] [35] använder extrema i skillnaden mellan det Gaussiska skalningsutrymmet MRI(resonansbildermagnetiskaför att analysera och klassificera 3DFBM modellerar en bild sannolikt som ett kollage av oberoende egenskaper som bestäms av bildgeometri och etikettgrupper, såsom friska föremål och föremål som motsvarar Alzheimers sjukdom. Funktionerna extraheras först till individuella bilder från en 4D Gaussisk skalningsrymdsskillnad, och modelleras sedan i termer av deras utseende, geometri och statistik om samtidig förekomst i en grupp över flera bilder. FBM har validerats i Alzheimers sjukdomsanalys med en uppsättning av ~200 volymetrisk avbildning (MRI) av den mänskliga hjärnan, som automatiskt detekterar etablerade indikatorer på Alzheimers sjukdom i hjärnan och klassificerar icke-akuta sjukdomar i nya bilder med en frekvens på 80 % [ 35] .   

Konkurrerande metoder

Konkurrerande metoder för skalinvariant objektigenkänning under brus och partiell överlappning är följande.

RIFT [36] : Rotations -invariant generalisering av SIFT .  RIFT-deskriptorn är konstruerad med hjälp av cirkulära normaliserade skivor uppdelade i koncentriska ringar med lika bredd, och inom varje ring beräknas ett histogram av gradientens riktning. För att erhålla rotationsinvarians mäts orienteringen vid varje punkt i förhållande till riktningen från mitten.

G-RIF [37] : Generalized Robust Invariant Feature är en  allmän kontextdeskriptor som kodar kantorientering, kantdensitet och färginformation i en enda nyckel, som kombinerar perceptuell information med rumslig kodning. Objektigenkänningsschemat använder grannskapskontexten för att utvärdera objektmodeller baserat på röstning.

"SURF" [38] : Speeded  Up Robust Features är högpresterande skal- och rotationsinvarianta detektorer/deskriptorer som påstås närma sig eller till och med överträffa tidigare föreslagna scheman när det gäller reproducerbarhet, klarhet och tillförlitlighet. SURF förlitar sig på bilder med full faltning för att minska beräkningstiden och är baserat på styrkan hos ledande befintliga detektorer och deskriptorer (med ett snabbt mått baserat på den hessiska matrisen för detektorer och sannolikhetsfördelningsbaserade deskriptorer). Den beskriver fördelningen av Haar wavelet -svaren mellan singulära punktens grannar. Fullständiga bilder används för att öka hastigheten och endast 64-dimensionella funktionsvektorer används för att minska beräknings- och matchningstiden. Indexeringssteget är baserat på tecknet för Laplacian , vilket ökar matchningshastigheten och robustheten hos deskriptorn.

PCA-SIFT [39] och GLOH [19] är varianter av SIFT. PCA-SIFT-deskriptorn är en vektor av bildgradienter i x- och y-riktningarna som beräknas i det stödda området. Gradientområdet är uppdelat i 39×39 platser, så dimensionen på vektorn är 3042. Dimensionen reduceras till 36 med metoden för huvudkomponenter . Platsorienteringsgradienthistogram ( GLOH ) är en förlängning av SIFT-deskriptorn och utvecklades för att öka dess robusthet och särskiljbarhet. SIFT-deskriptorn beräknas i logaritmiska polära koordinater för ett positionsrutnät med tre regioner i de radiella riktningarna (radien satt till 6, 11 och 15) och 8 i vinkelriktningarna, vilket resulterar i 17 regioner. Det centrala området är inte uppdelat i vinkelriktningar. Gradientriktningarna kvantiseras till 16 regioner, vilket resulterar i ett histogram med 272 regioner. Storleken på denna deskriptor reduceras med principal component-metoden . Kovariansmatrisen för Principal Component Method utvärderas på bitar som samlats in från olika bilder. De 128 största egenvektorerna används för beskrivningen.

Gauss-SIFT [21] är en ren bilddeskriptor som definieras genom att mäta alla bilder av den underliggande SIFT-deskriptorn med en Gaussisk derivata, snarare än att approximera derivatan i en bildpyramid som görs i standard SIFT. Med detta tillvägagångssätt kan effekten av diskretisering av utrymme och skala reduceras till ett minimum, vilket potentiellt kan resultera i mer exakta bilddeskriptorer. Lindeberg [21] kombinerade sådana Gauss-SIFT-bilddeskriptorer med en uppsättning generaliserade singulära punktskalrum, inklusive den Gaussiska Laplacian, den Hessiska determinanten, fyra nya funktionsmått för den osignerade och signerade Hessian, såväl som Harris-Laplace och Shea -Thomas singular poäng. I en intensiv experimentell körning på en databas av skyltar som innehåller flera transformationer av 12 skyltar vad gäller zoom upp till 6x och synriktningen upp till en vinkel på 45 grader, visades det att en signifikant ökning av bildbehandlingseffektiviteten (högre effektivitet poäng och lägre poäng 1 -noggrannhet) kan erhållas genom att ersätta Laplacian av Gaussian av singularpunkterna med determinanten av Hessian av singularpunkterna. Eftersom singularpunkten Gaussskillnad antar en numerisk approximation av singularpunkten Gaussisk, visar detta att det är möjligt att signifikant öka matchningsprestandan genom att ersätta singularpunktens Hessiska skillnaden i SIFT med singularpunktshessiska determinanten. Ytterligare prestandavinster kan erhållas ytterligare genom att överväga ett osignerat Hessian  -egenskapsstyrkemått eller 0 på annat sätt. En numerisk jämförelse mellan Gauss-SIFT-deskriptorn och motsvarande Gauss-SURF-deskriptor visade också att Gauss-SIFT generellt presterar betydligt bättre än Gauss-SURF för ett stort antal olika singulära punktskala-rymddetektorer. Studien visar alltså att SIFT-bilddeskriptordiskretiseringseffektreduktionen är betydligt bättre än SURF-bilddeskriptorn, dock funktionspunktdetektorn i SURF, som kan betraktas som en numerisk approximation till extremumet i skalutrymmet för den hessiska determinanten, är betydligt bättre än funktionspunktdetektorn i SIFT.

Wagner och medarbetare har utvecklat två objektigenkänningsalgoritmer som är specifikt anpassade till begränsningarna hos befintliga mobiltelefoner [40] . I motsats till det klassiska tillvägagångssättet använder SIFT Wagner et al. FAST hörndetekteringsalgoritm för funktionsdetektering. Algoritmen innehåller också en offline-förberedelsefas, där funktioner skapas på olika zoomnivåer, och en onlinefas, där funktioner genereras endast för en fast zoomnivå på telefonens kamera. Dessutom skapas funktionerna endast från fasta områden på 15×15 pixlar och endast en 36-dimensionell SIFT-deskriptor skapas. Tillvägagångssättet utökades ytterligare genom integration med Scalable Vocabulary Tree [41 ] . Detta möjliggör effektiv igenkänning av ett stort antal objekt av mobiltelefonen. Tillvägagångssättet begränsas främst av mängden tillgängligt RAM -minne .  

KAZE och A-KAZE (KAZE Features and Kaze Boosted Features) är en ny 2D-funktionsdetektering och karakteriseringsmetod som presterar bättre än SIFT och SURF. Det har vunnit stor popularitet på grund av att det distribueras fritt och har öppna källkoder. Algoritmen är inte heller patenterad. KAZE skapades av Pablo F. Alcantarilla, Adrien Bartoli och Andrew J. Davison [42] .

Se även

Anteckningar

  1. ↑ 12 USA _ Patent 6 711 293 , "Metod och apparat för att identifiera skalinvarianta egenskaper i en bild och användning av densamma för att lokalisera ett objekt i en bild", David Lows patent för SIFT-algoritmen, 23 mars 2004
  2. ↑ 1 2 3 4 Lowe, 1999 , sid. 1150–1157.
  3. ↑ 1 2 3 4 5 6 Lowe, 2004 , sid. 91–110.
  4. ↑ Koenderink, van Doorn, 1987 , sid. 383-396.
  5. ↑ Koenderink, van Doorn, 1992 , sid. 597-605.
  6. ↑ Lindeberg:BICY, 2013 , sid. 589-635.
  7. ↑ Lindeberg:AdvImg, 2013 , sid. 1-96.
  8. ↑ Lindeberg:PLOS ONE, 2013 .
  9. ↑ 12 Lindeberg , 2014 , sid. 701-713.
  10. ↑ 12 Lindeberg , 1994 .
  11. ↑ 1 2 Lindeberg, 1998 , sid. 79–116.
  12. ↑ 12 Lindeberg , 2012 , sid. 10491.
  13. ↑ Serre, Kouh, Cadieu, Knoblich, Kreiman, Poggio, 2005 .
  14. ↑ 1 2 Beis, Lowe, 1997 , sid. 1000–1006.
  15. ↑ Lowe, 2001 , sid. 682-688.
  16. ↑ 1 2 Lindeberg, Bretzner, 2003 , sid. 148–163.
  17. ↑ Bretzner, Laptev, Lindeberg, 2002 , sid. 423-428.
  18. ↑ 12 Kirchner , 2016 , sid. 291-295.
  19. ↑ 1 2 Mikolajczyk, Schmid, 2005 , sid. 1615–1630
  20. ↑ TU-chemnitz.de (nedlänk) . Hämtad 12 november 2018. Arkiverad från originalet 22 maj 2011. 
  21. ↑ 1 2 3 4 5 Lindeberg, 2015 , sid. 3-36.
  22. ↑ Oyallon, Rabin, 2015 .
  23. ↑ Cui, Hasler, Thormaehlen, Seidel, 2009 .
  24. ↑ Toews, Wells III, 2009 , sid. 172–177.
  25. ↑ Sirmacek, Unsalan, 2009 , sid. 1156–1167.
  26. ↑ Se, Lowe, Little, 2001 , sid. 2051.
  27. ↑ Brown, Lowe, 2003 , sid. 1218–1225.
  28. ↑ Gordon, Lowe, 2006 , sid. 67-82.
  29. ↑ 1 2 Flitton, Breckon, 2010 , sid. 11.1–12.
  30. ↑ Flitton, Breckon, Megherbi, 2013 .
  31. ↑ Laptev, Lindeberg, 2004 , sid. 91–103.
  32. ↑ Laptev, Caputo, Schuldt, Lindeberg, 2007 , sid. 207–229.
  33. ↑ Scovanner, Ali, Shah, 2007 , sid. 357–360.
  34. ↑ Niebles, Wang, Li, 2006 , sid. 1156–1167.
  35. ↑ 1 2 3 Toews, Wells III, Collins, Arbel, 2010 , sid. 2318–2327.
  36. ↑ Lazebnik, Schmid, Ponce, 2004 .
  37. ↑ Kim, Yoon, Kweon, 2006 .
  38. ↑ Bay, Tuytelaars, van Gool, 2006 .
  39. ↑ Ke, Sukthankar, 2004 .
  40. ↑ Wagner, Reitmayr, Mulloni, Drummond, Schmalstieg, 2008 .
  41. ↑ Henze, Schinke, Boll, 2009 .
  42. ↑ KAZE-funktioner . Hämtad 12 november 2018. Arkiverad från originalet 3 november 2018.

Litteratur

Länkar