Cvičení 11: RANSAC Tomáš Sixta 23. listopadu 2012
1 Úvod V tomto cvičení se naučíte pracovat s algoritmem RANSAC pro nalezení transformace mezi dvěma množinami bodových korespondencí. Mějme dva obrázky (označme je jako levý a pravý), v každém několik klíčových bodů a předpokládejme, že pro každý bod z levého obrázku máme kandidátské korespondence s body v pravém obrázku. Ne všechny jsou však správné, některé dvojice neodpovídají jednomu fyzickému prvku scény. Vaším úkolem bude najít takovou transformaci mezi levou a pravou množinou, která má co možná největší podporu (support).
2 Automatická registrace obrázků Automatickou registraci obrázků pomocí klíčových bodů lze rozdělit na několik fází: • • • • •
Nalezení klíčových bodů v obou obrázcích. Výpočet popisů klíčových bodů invariantních vůči nějaké třídě transformací. Vytvoření tentativních (kandidátských) korespondencí mezi body v obou obrázcích. Nalezení transformace mezi obrázky (např. algoritmem RANSAC). Transformace jednoho z obrázků.
2.1 Hledání klíčových bodů Kvalitní klíčový bod (keypoint) by měl ležet v místě, jehož pozice je dobře určena (tedy ne v jednobarevných oblastech nebo na hranách). Takovými místy mohou být např. rohy (průsečíky dvou hran, lokální extrém intenzity atd.), pro které existuje mnoho postupů, jak je detekovat. Prvním prakticky použitelným byl Harrisův detektor, který hledá body, v nichž se gradient mění ve dvou ortogonálních směrech. Využívá vlastností tzv. autokorelační matice gradientu
1
A=
XX u
v
w(u, v)
Ix2 (u, v) Ix Iy (u, v) Ix Iy (u, v) Iy2 (u, v)
! ,
(1)
kde w je nějaká okenní funkce centrovaná ve vyšetřovaném bodě (typicky gaussián) a Ix a Iy jsou parciální derivace obrázku I. Je-li výraz det(A) − κtrace2 (A)
(2)
větší než zvolený práh, prohlásíme takový bod za rohový (konstanta κ nastavuje citlivost detektoru). Další detektory klíčových bodů (oblastí) jsou např. Hessian detector, FAST a další.
2.2 Deskriptory Porovnávání dvou klíčových bodů pouze na základě obrazové informace v jejich okolí dává očekávané výsledky jen pro mírně odlišné obrázky (rotace o malý úhel, malá změna měřítka). Pokud se liší více, je vhodné použít deskriptory invariantní vůči nějaké třídě transformací. Odhad měřítka a natočení okolí klíčového bodu nám někdy vrátí jejich detektor. V tomto cvičení budete používat implementaci deskriptoru SIFT (Scale Invariant Feature Transform), které jsou v současné době velmi populární. Další významné metody popisu klíčových bodů jsou např. SURF (Speeded Up Robust Feature), HOG (Histogram of Oriented Gradients) a další.
2.3 Tentativní korespondence Nejjednodušší způsob, jak nalézt možné protějšky bodu z levé množiny, je povolit jeho párování se všemi body pravé množiny. Takový postup však vytváří velké množství možných korespondencí, a proto je vhodný jen pro malé množiny bodů a jednoduché transformace (rigidní). Lepší způsob je popsat klíčové body vhodnými deskriptory a každému bodu z levé přiřadit bod z pravé množiny s nejpodobnějším deskriptorem.
3 Zadání 1.
Pomocí funkce find_keypoints z doprovodného archivu najděte klíčové body a jejich popisy v obrázcích 1a, 1b, 2a a 2b. Význam parametrů je následující: Vstupní parametry: image [w × h] nebo [w × h × 3]: Obrazová data. Výstupní parametry: frames: [n × 2]. Klíčové body. První sloupec jsou x-ové souřadnice, ve druhém sloupci jsou y-ové souřadnice. descriptors [128 × n]: Popisy klíčových bodů. Aby mohla find_keypoints správně pracovat, je třeba rozbalit a přidat do cesty Matlabu archiv sift-0.9.19-bin.tar.gz, který obsahuje potřebné mex soubory.
2.
Napište funkci [c]=get_correspondences(descriptors1,descriptors2), která pro každý klíčový bod z levého obrázku najde v pravém obrázku klíčový bod s nejpodobnějším popisem (0,5 bodu). Vstupní parametry: 2
descriptors1 [128 × n]: Popisy klíčových bodů z levého obrázku. descriptors2 [128 × m]: Popisy klíčových bodů z pravého obrázku. Výstupní parametry: c: [n × 2]. Pole indexů, v prvním sloupci jsou body z levého obrázku, ve druhém z pravého. Podobnost dvou deskriptorů měřte jako euklidovskou vzdálenost daných vektorů. 3.
Napište funkci [support inl]=get_support(points1,points2,T,threshold), která spočítá podporu (support) transformace T (1 bod). Vstupní parametry: points1 [n × 2]: Body z levé množiny, první sloupec obsahuje x-ové souřadnice, druhý sloupec obsahuje y-ové souřadnice. points2 [n × 2]: Body z pravé množiny, první sloupec obsahuje x-ové souřadnice, druhý sloupec obsahuje y-ové souřadnice. T [3 × 3]: Transformační matice zobrazující levou množinu na pravou. threshold [1 × 1]: Maximální vzdálenost bodu z pravé množiny a transformovaného bodu z levé množiny, pro kterou jsou tyto body označeny za inliery. Výstupní parametry: support [1 × 1]: Podpora (support) transformace T, tedy počet bodů takových, že #x : ||x0 − T (x)|| < threshold
(3)
inl [n × 1]: Pole obsahující na i-té pozici 1, je-li i-tý bod z levé množiny inlier, jinak 0. 4.
Napište funkci [T inl]=ransac(points1,points2,c,confidence,threshold,type), která pomocí algoritmu RANSAC najde similaritní transformaci mezi množinami points1 a points2. (2,5 bodu). Vstupní parametry: points1 [n × 2]: Body z levé množiny, první sloupec obsahuje x-ové souřadnice, druhý sloupec obsahuje y-ové souřadnice. points2 [m × 2]: Body z pravé množiny, první sloupec obsahuje x-ové souřadnice, druhý sloupec obsahuje y-ové souřadnice. c [n × 2]: Indexy korespondujícíh bodů z levé a pravé množiny. confidence [1 × 1]: Číslo z intervalu (0,1) udávající požadovanou pravděpodobnost, že vrácená transformace je správná (confidence). threshold [1 × 1]: Maximální vzdálenost bodu z pravé množiny a transformovaného bodu z levé množiny, pro kterou jsou tyto body označeny za inliery. type: Typ transformace. Řetězec ’similarity’ pro similaritu, ’affine’ pro afinní z bonusu 2 a ’homography’ pro obecnou homografii z bonusu 3. Výstupní parametry: T [3 × 3]: Transformační matice mezi množinami points1 a points2. inl [n × 1]: Pole obsahující na i-té pozici 1, je-li i-tý bod z levé množiny inlier, jinak 0. Kandidátské similaritní transformace můžete hledat pomocí funkce find_transformation ze 4. cvičení (předejte jí vždy tři korespondující páry). Počet zbývajících iterací odhadujte vždy při změně nejlepší dosud nalezené transformace. Označímeli požadovanou pravděpodobnost správnosti modelu (confidence) jako p, počet skutečných inlierů v datech jako w a počet datových bodů jako n, je odhad počtu zbývajících iterací roven
3
k=
log(1 − p) log(1 − wn )
(4)
Protože počet skutečných inlierů není typicky znám, odhaduje se z počtu parametrů transformace a počtu bodů, které podporují dosud nejlepší nalezenou transformaci. K odhadu počtu zbývajících iterací můžete využít funkci [SampleCnt] = nsamples(ni, ptNum, pf, conf), jejíž parametry mají následující význam: ni [1 × 1]: Support dosud nejlepší nalezené transformace. ptNum [1 × 1]: Počet všech dvojic bodů. pf [1 × 1]: Počet dvojic bodů potřebných k výpočtu parametrů transformace. conf [1 × 1]: Požadovaná pravděpodobnost, že vrácená transformace je správná (confidence). 5.
Použijte funkci ransac k nalezení similaritní transformace mezi dvojicemi obrázků 1a – 1b a 2a – 2b. Pro každou dvojici obrázků vložte do reportu: • •
• •
Pravý obrázek se zakreslenými body points2. Levý obrázek se zakreslenými body points1 a s jejich transformovanými protějšky z množiny points2. Sobě odpovídající body spojte úsečkou. Zakreslujte body tak, aby bylo možné odlišit points1 od points2 a inliery od outlierů. Rozdílový obrázek po transformaci. Pokud se obrázky překrývají jen částečně, doplňte myšleně každý za jeho okrajem nulami. Počet detekovaných klíčových bodů v obou obrázcích, nejlepší dosažený support a hodnoty všech parametrů (confidence, threshold). Rozumné hodnoty jsou confidence=0.99 a threshold=1, avšak nebojte se experimentovat.
K transformaci obrázků můžete využít funkci transform_image ze 3. cvičení. 6.
Bonus. Použijte funkce find_keypoints a ransac k nalezení transformace mezi dvěma obrázky Vašeho výběru, které se částečně překrývají, a vytvořte z nich panorama. Pokud se rozhodnete naprogramovat také afinní transformaci nebo obecnou homografii, můžete je v tomto bodě využít namísto prosté similarity. Výstupem bude skript, který složí panorama ze dvou obrázků bez zásahu uživatele. Zdrojové obrázky a výsledné panorama vložte do reportu (2 body).
7.
Bonus. Implementujte funkci [T]=find_transformation_affine(points1,points2), která nalezne parametry afinní transformace (významy parametrů jsou stejné jako u funkce find_transformation ze 4. cvičení) (1 bod). Obecnou afinní transformaci bodů v rovině lze zapsat pomocí následujícího maticového násobení: h11 h12 h13 x0 x 0 λ y = h21 h22 h23 y (5) 1 0 0 1 1 Tuto soustavu můžeme rozepsat na λx0 = h11 x + h12 y + h13 λy 0 = h21 x + h22 y + h23 λ=1 a dosazením tří různých párů x ↔ x0 dostaneme (rozmyslete si přechod k maticovému zápisu!)
4
x1 0 x2 0 x3 0
y1 0 y2 0 y3 0
x01 h11 1 0 0 0 0 0 x1 y1 1 h12 y1 0 1 0 0 0 h13 = x2 0 0 x2 y2 1 h21 y2 0 1 0 0 0 h22 x3 y30 h23 0 x3 y3 1
(6)
Aby měla matice soustavy 6 plnou hodnost, nesmí být body v pravé ani levé množině kolineární. 8.
Bonus. Odvoďte a implementujte funkci [T]=find_transformation_homography(points1,points2), která nalezne parametry obecné homografie, tedy transformace h11 h12 h13 x x0 (7) λ y 0 = h21 h22 h23 y 1 1 h31 h32 h33 (pozor, λ v tomto není případě pro všechny body rovna 1, což musíte vzít v úvahu při výpočtu supportu). Odvození vložte do reportu. (3 body za odvození, 1 za implementaci).
a) MRI scan lebky
b) MRI scan lebky po similaritní transformaci
c) MRI scan lebky po afinní transformaci
d) MRI scan lebky po transformaci obecnou homografíí
Obrázek 1
5
a) Obrázek 2
b) Histologický řez krysí ledvinou
4 Literatura [1] Harris C., Stephens M.. A Combined Corner and Edge Detector. In Proceedings of The Fourth Alvey Vision Conference, pp. 147-151., 1988. [2] Lowe D. G.. Object Recognition from Local Scale-Invariant Features. Computer Vision. The Proceedings of the Seventh IEEE International Conference on, pp 1150 - 1157, 1999. [3] Chum O.. Two-View Geometry Estimation by Random Sample and Consensus (PhD thesis). Online available at: cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf, 2005.
6
