Vytvoření mobilního skeneru dokumentů s nulovými závislostmi:Rozděl a panuj

Prvním krokem při ponoření se do každého nového projektu je vytvoření mentálního seznamu kroků, které je třeba podniknout k postupnému sestavení první verze. Po dokončení počátečního prototypu je jeho leštění a finalizace docela snadné (pokud nepředěláváte žádné základní komponenty). Před vytvořením skeneru dokumentů jsem neměl téměř žádné znalosti o algoritmech počítačového vidění, takže jsem začal s plánem na vysoké úrovni a rozdělil každý krok na několik menších úkolů, které jsem mohl řešit jeden po druhém. Myslel jsem, že proces bude probíhat nějak takto:

  1. Získejte od uživatele obrázek obsahující dokument
  2. Najděte dokument na obrázku
  3. Změňte perspektivu tak, aby dokument vyplnil celou obdélníkovou oblast nového obrázku

Pokud jste viděli první díl této série, jistě si vzpomenete, jak jsme si tyto kroky vizualizovali.



S tímto plánem jsem začal svůj výzkum. Jak jsem brzy zjistil, tyto kroky se dramaticky liší svou obtížností. Krok 1 je triviální a na konci prvního dne práce na projektu jsem měl funkční uživatelské rozhraní pro výběr obrázků. Krok 3 je složitý, ale relativně přímočarý:tato vynikající odpověď Stack Exchange dokonce poskytla základní implementaci transformace perspektivy v JavaScriptu, kterou bych lehce upravil pro použití ve svém prototypu. Krok 2 je však neuvěřitelně obtížný a je třeba jej rozdělit na několik menších částí.

Zpočátku jsem si myslel, že nejsnazší způsob, jak najít dokument na obrázku, bude najít čtyři nejvíce rohové body na obrázku a ty považovat za rohy skutečného dokumentu (o kterém jsem předpokládal, že je obdélník). To mě vedlo k divoké honičce zahrnující detekci Harrisových rohů a detekci obrysů, ale poté, co jsem nenašel žádný úspěch ve svých hacknutých implementacích, zkusil jsem výzkum na vyšší úrovni.

Nakonec jsem našel tento příspěvek z Dropboxu, který mi poskytl přehled o současných nejmodernějších technikách detekce dokumentů. Namísto hledání čtyř rohů by můj program našel všechny okraje v obrázku a pak by hledal čtyři z nich, které jsou nejpravděpodobněji okraji dokumentu. Konkrétněji bych potřeboval vymyslet funkci bodování, která by ohodnotila všechny kombinace čtyř hran a použila kombinaci s nejvyšším skóre v mém transformačním kódu perspektivy.

Vymyslel jsem několik vylepšení oproti technikám Dropboxu. Použili algoritmus detekce hran Canny k vytvoření vizuální reprezentace oblastí podobných hranám na obrázku a poté na tento výstup použili Houghovu transformaci, aby našli matematické znázornění nejpravděpodobnějších hran v obrázku.

Místo toho jsem se rozhodl použít pouze první krok Cannyho, operátor Sobel, a směr gradientu, který vygeneroval (což je obvykle považováno za vedlejší efekt), abych snížil počet hlasů v Houghově prostoru. Tato změna dramaticky zlepšuje výkon (odhaduji 5x nebo více) a snižuje množství šumu, který se objevuje v řádcích detekovaných pomocí Houghovy transformace.

Dropbox také zkontroloval všechny kombinace čtyř hran, včetně těch, které z geometrického hlediska nemohly být dokumentem (například kde se dvě „strany“ papíru překříží a místo čtyřúhelníku vytvoří tvar přesýpacích hodin) a odfiltroval tyto nemožné tvary. později. Zvažoval jsem pouze každou kombinaci čtyř čar, která vytvořila platný čtyřúhelník, což také trochu zlepšuje výkon, ale co je důležitější, usnadňuje návrh vhodné skórovací funkce tím, že snižuje rozsah vstupu, se kterým se musí vypořádat.

Nakonec jsem se rozhodl zmenšit měřítko obrázků před použitím všech těchto algoritmů, protože to snižuje pravděpodobnost, že text uvnitř dokumentu způsobí problémy při detekci okrajů, a protože to zlepšuje výkon kvadraticky s ohledem na faktor měřítka, přičemž má teoretický maximální dopad na faktor měřítka na umístění každé hrany. Jednodušeji řečeno, zmenšení šířky a výšky obrázku o 5x by zlepšilo výkon 25x, ale v nejhorším případě by způsobilo, že detekované okraje budou posunuty o 5 pixelů ve srovnání s jejich skutečným umístěním, a když jsou vstupní obrázky obvykle alespoň 1080p, tato malá chyba není na konečném obrázku po projektivní transformaci patrná.

Po dokončení mého výzkumu byl můj upravený plán následující:

  1. Získejte od uživatele obrázek obsahující dokument
  2. Najděte dokument na obrázku
    • Převeďte obrázek na zmenšenou verzi ve stupních šedi
    • Použijte Gaussovské rozostření ke snížení šumu
    • Použijte Sobelův operátor k nalezení velikosti a směru gradientu v každém pixelu
    • Použijte Houghovu transformaci k nalezení skóre pro každou možnou čáru, která prochází obrázkem. Úhel každé čáry rozložte zhruba po 1 stupni od 0 do 180 stupňů a pozici po 2 pixelech od záporné do kladné hodnoty přepony rozměrů obrázku
    • Použijte směr přechodu z operátoru Sobel k přidání větší váhy v Houghově transformaci k okrajům téměř ortogonálním k přechodu v každém pixelu
    • Najděte prvních několik tisíc řádků v Houghově transformaci a použijte nemaximální potlačení, abyste našli několik desítek řádků, které mají nejvyšší konečné skóre
    • Prosejte každou kombinaci čtyř čar, které tvoří platné čtyřúhelníky, a použijte funkci heuristického bodování, abyste našli kandidáta, který bude s největší pravděpodobností dokumentem
    • Najděte průsečíky čar v nejlepším kandidátovi k nalezení čtyř rohů dokumentu
  3. Použijte projektivní transformaci k deformaci perspektivy původní fotografie do konečného obrázku
    • Vypočítejte projektivní transformaci:použijte nějakou maticovou algebru k řešení lineárních rovnic, které mapují souřadnice rohů dokumentu na základní vektory představující homogenní souřadnice.
    • Udělejte totéž v opačném směru, abyste namapovali homogenní souřadnice na 2D souřadnice na plochou, obdélníkovou rovinu představující dokument z čelního pohledu (a tedy konečný obrázek)
    • Iterujte přes každou cílovou souřadnici v promítaném obrazu a najděte zdrojovou souřadnici z původního RGB obrazu (který bude pravděpodobně obsahovat desetinná místa, nikoli celá čísla)
    • Použijte bilineární interpolaci k simulaci hodnot pixelů na desetinných zdrojových souřadnicích a použijte tyto hodnoty na cílových souřadnicích k vytvoření promítaného obrazu

Pokud vám něco z toho přeletělo přes hlavu, nebojte se; Tento popis píšu až poté, co dokončím projekt a probojuji se matematikou za každým z těchto algoritmů. O tom, jak jednotlivé kroky fungují, půjdeme hlouběji v dalším článku, počínaje operátorem Sobel.