Sparse Bundle Adjustation (SBA) är standardmetoden för att optimera ett struktur-from-motion problem i datorseende. Med framgång för Photosynth och liknande system för att sy ihop stora samlingar av bilder [5] har uppmärksamheten vänts mot problemet med att göra SBA mer effektivt. Det finns två typiska användningsmönster för SBA. I en, en uppsättning bilder tas av ett objekt, så de flesta av bilderna har funktioner gemensamt och den sekundära strukturen är tät. Till exempel, i Venedig datauppsättning av turist bilder 1, densiteten av H är 40%, det vill säga icke-noll står för 40% av matrisen poster. I andra änden av spektrumet finns datauppsättningar från visuell kartläggning, där vanligtvis en enda kamera rör sig runt ett område, och bilderna registreras för att producera en utökad karta. Till exempel, i Intel Seattle inomhus dataset 2, kamerans rörelse är mestadels längs korridorer, och densiteten är bara 1,4%. Skillnaden i gleshetsmönstret visas i figur 1. Observera att kartmönstret består av ett fett diagonalt band, med några parallella band för överlappande banor. (Guilbert m.fl.) kallar dessa "sparse systems" [2]). I detta dokument är vi intresserade av snabba SBA-metoder för kartläggningsfallet, där det är möjligt att utnyttja problemets glesa sekundärstruktur (kamera-till-kamera-relationer). Icke-linjär optimering i SBA fortskrider vanligtvis genom iteration: bildar ett linjärt subproblem runt den nuvarande lösningen, lösa den, och upprepa tills konvergens. För stora problem är den beräkningsmässiga flaskhalsen vanligtvis lösningen på det linjära subproblemet, som kan växa som kuben av antalet kameror. Fyllningen av det linjära problemet är direkt knuten till kamerans punktstruktur av problemet: om varje kamera bara ser funktioner i ett litet område av andra kameror, antalet icke-noll element växer endast linjärt eller nästan linjärt med antalet kameror. Det linjära systemet bildas från projektionen av punkter p på kameror c. Den linjära ekvationen kan skrivas som: där J c är Jacobian med avseende på kameravariabler, och J p med avseende på punktvariabler. Eftersom alla felfunktioner involverar en kamera och en punkt, Jacobian produkter J  på c J c och J P J p är blockdiagonal. Efter viss manipulering är det reducerade systemet där H xy hänvisar till de jakobska produkterna i ekvation 1. Observera matrisen inversion är enkel på grund av den block-diagonala strukturen av H pp. Lösa denna ekvation producerar en ökning  och c som justerar kameravariabler, och sedan används för att uppdatera punktvariabler enligt När du bildar den vänstra sidan av ekvation 2, den viktigaste beräkning flaskhalsen är att beräkna produkten H cp H −1 pp H pc. Vi är intresserade av stora system, där antalet kameravariabler kan vara 10k eller mer (den största verkliga datauppsättningen vi har använt är ca 3k poser, men vi kan generera syntetiska datauppsättningar av alla ordningar). Antalet systemvariabler är 6 ·  och den reducerade systemmatrisen för ekvation 2 har storlek 36 ·  och 2, eller över 10 9 element. Att manipulera sådana stora matriser är dyrt. För att göra det effektivt måste vi utnyttja dess glesa struktur. Det reducerade SBA-systemets sparsamhetsmönster kallas sekundärstruktur. Den mest beräkna-intensiva delen av att skapa H innebär en yttre produkt över projektionerna i varje punkt spår (för detaljer om hela algoritmen, se Engels et al. [1] )................................................................................................................ I vår version av denna algoritm skapar vi en sparsam struktur för att komma åt godtyckliga 6x6 block i, j av H. Vi använder en C++ std::karta behållare för varje kolumn av H. Kartan är keyed by rad
REF införde Sparse SBA (sSBA) som utnyttjar den glesa sekundära strukturen hos gles kamera till kamerarelationer, vilket ökar beräknings- och minneseffektiviteten.
Sparse Sparse Bundle Adjustment
{'venue': 'BMVC', 'journal': None, 'mag_field_of_study': ['Computer Science']}