Deepanshu Tyagi

följ

Mar 16, 2019 · 7 min läs

sift står för Scale-invariant feature Transform och presenterades först 2004 av D. Lowe, University of British Columbia. SIFT är invariance till bildskala och rotation. Denna algoritm är patenterad, så denna algoritm ingår i den icke-fria modulen i OpenCV.

stora fördelar med sift är

• lokalitet: funktioner är lokala, så robusta för ocklusion och röran (ingen tidigare segmentering)
• distinktivitet: enskilda funktioner kan matchas med en stor databas med objekt
• kvantitet: många funktioner kan genereras för även små objekt
• effektivitet: nära realtidsprestanda
• töjbarhet: kan enkelt utökas till ett brett utbud av olika funktionstyper, där varje lägger till robusthet

detta är en del av en 7-serie feature Detection and Matching. Andra artiklar inkluderade

• introduktion till Funktionsdetektering och Matchning
• introduktion till Harris Corner Detector
• introduktion till SURF (snabbare robusta funktioner)
• introduktion till snabb (funktioner från accelererat Segmenttest)
• introduktion till kort (binär Robust oberoende elementära funktioner)
• introduktion till ORB (orienterad snabb och roterad kort)

SIFT är ganska involverad algoritm. Det finns huvudsakligen fyra steg involverade i SIFT-algoritmen. Vi kommer att se dem en efter en.

• skala-utrymme toppval: Potentiell plats för att hitta funktioner.
• Keypoint Lokalisering: exakt lokalisera funktionen keypoints.
• Orienteringstilldelning: tilldela orientering till tangentpunkter.
• Keypoint descriptor: beskriver keypoints som en högdimensionell vektor.
• Keypoint Matching

skala-space peak Selection

verkliga objekt är meningsfulla endast i en viss skala. Du kan se en sockerkub perfekt på ett bord. Men om man tittar på hela Vintergatan, så finns det helt enkelt inte. Denna flerskaliga natur av objekt är ganska vanlig i naturen. Och ett skalutrymme försöker replikera detta koncept på digitala bilder.

skalautrymmet för en bild är en funktion L(x,y,Kubi) som produceras från konvolutionen av en gaussisk kärna(oskärpa) i olika skalor med inmatningsbilden. Skala-utrymmet separeras i oktaver och antalet oktaver och skala beror på originalbildens storlek. Så vi genererar flera oktaver av originalbilden. Varje oktavs bildstorlek är hälften av den föregående.

oskärpa

inom en oktav suddas bilderna gradvis med hjälp av Gaussian Blur-operatören. Matematiskt kallas ”suddning” som den gaussiska operatörens konvolution och bilden. Gaussian blur har ett visst uttryck eller” operatör ” som appliceras på varje pixel. Vilka resultat är den suddiga bilden.

suddig bild

g är den gaussiska suddighetsoperatören och jag är en bild. Medan x, y är platskoordinaterna och Xiaomi är parametern ”skala”. Tänk på det som mängden oskärpa. Större värde, större oskärpa.

Gaussian Blur operator

hund(skillnad i Gaussisk kärna)

nu använder vi de suddiga bilderna för att generera en annan uppsättning bilder, skillnaden mellan gaussier (hund). Dessa hundbilder är bra för att ta reda på intressanta nyckelpunkter i bilden. Skillnaden mellan Gaussian erhålls som skillnaden mellan Gaussisk suddning av en bild med två olika Kubi, låt det vara en Kubi och en k-Kubi. Denna process görs för olika oktaver av bilden i den gaussiska pyramiden. Det representeras i bilden nedan:

hitta nyckelpunkter

hittills har vi genererat ett skalutrymme och använt skalutrymmet för att beräkna skillnaden mellan gaussier. De används sedan för att beräkna Laplacian av gaussiska approximationer som är skala invariant.

en pixel i en bild jämförs med sina 8 grannar samt 9 pixlar i nästa skala och 9 pixlar i tidigare skalor. På så sätt görs totalt 26 kontroller. Om det är en lokal extrema, det är en potentiell nyckelpunkt. Det betyder i princip att keypoint bäst representeras i den skalan.

Keypoint Localization

Key0points genererade i föregående steg ger många keypoints. Några av dem ligger längs en kant, eller de har inte tillräckligt med kontrast. I båda fallen är de inte lika användbara som funktioner. Så vi blir av med dem. Tillvägagångssättet liknar det som används i Harris Corner Detector för att ta bort kantfunktioner. För funktioner med låg kontrast kontrollerar vi helt enkelt deras intensiteter.

de använde Taylor – serieutvidgning av skalutrymme för att få en mer exakt plats för extrema, och om intensiteten vid denna extrema är mindre än ett tröskelvärde (0,03 enligt papperet) avvisas det. Hunden har ett högre svar för kanter, så kanterna måste också tas bort. De använde en 2×2 Hessian matris (H) för att beräkna huvudkurvaturen.

orienteringstilldelning

nu har vi legitima nyckelpunkter. De har testats för att vara stabila. Vi vet redan i vilken skala knapppunkten upptäcktes (det är samma som skalan på den suddiga bilden). Så vi har skala invariance. Nästa sak är att tilldela en orientering till varje knapppunkt för att göra det rotation invariance.

ett grannskap tas runt knapppunktsplatsen beroende på skalan, och gradientstorleken och riktningen beräknas i den regionen. Ett orienteringshistogram med 36 fack som täcker 360 grader skapas. Låt oss säga att gradientriktningen vid en viss punkt (i ”orienteringsuppsamlingsregionen”) är 18.759 grader, då går den in i 10-19 graders bin. Och ”mängden” som läggs till facket är proportionell mot gradientens storlek vid den punkten. När du har gjort detta för alla pixlar runt knapppunkten kommer histogrammet att ha en topp vid någon tidpunkt.

den högsta toppen i histogrammet tas och varje topp över 80% av den anses också beräkna orienteringen. Det skapar nyckelpunkter med samma plats och skala, men olika riktningar. Det bidrar till matchningens stabilitet.

Keypoint descriptor

vid denna punkt har varje keypoint en plats, skala, orientering. Nästa är att beräkna en deskriptor för den lokala bildregionen om varje knapppunkt som är mycket distinkt och invariant som möjligt för variationer som förändringar i synvinkel och Belysning.

för att göra detta tas ett 16×16-fönster runt knapppunkten. Den är uppdelad i 16 underblock med 4×4 storlek.

For each sub-block, 8 bin orientation histogram is created.

So 4 X 4 descriptors over 16 X 16 sample array were used in practice. 4 X 4 X 8 directions give 128 bin values. It is represented as a feature vector to form keypoint descriptor. Denna funktionsvektor introducerar några komplikationer. Vi måste bli av med dem innan vi slutför fingeravtrycket.

1. Rotationsberoende funktionsvektorn använder gradientorienteringar. Det är uppenbart att om du roterar bilden ändras allt. Alla gradientorienteringar ändras också. För att uppnå rotationsoberoende subtraheras knapppunktens rotation från varje orientering. Således är varje gradientorientering relativt tangentpunktens orientering.
2. Belysningsberoende om vi trösklar siffror som är stora kan vi uppnå belysningsoberoende. Så ändras något tal (av 128) större än 0,2 till 0,2. Denna resulterande funktionsvektor normaliseras igen. Och nu har du en illumination independent feature vector!

Tangentpunktsmatchning

Tangentpunkter mellan två bilder matchas genom att identifiera sina närmaste grannar. Men i vissa fall, den andra närmaste matchen kan vara mycket nära den första. Det kan hända på grund av buller eller andra orsaker. I så fall tas förhållandet mellan närmaste avstånd till näst närmaste avstånd. Om det är större än 0,8 avvisas de. Det eliminerar cirka 90% av falska matchningar medan kasserar endast 5% korrekta matchningar, enligt papperet.

implementering

Jag kunde implementera sift med OpenCV (3.4). Så här gjorde jag det:

GitHub länk för koden: https://github.com/deepanshut041/feature-detection/tree/master/sift