LlosLab Software Development BlogNotatki inżynieryjne dla programistów PDF, Delphi i oprogramowania do dokumentów.

Artykuł techniczny

Wbudowany OCR z dopasowaniem szablonów w Delphi i HotPDF

HotPDF Delphi Component

HotPDF dostarcza THPDFBuiltInOCREngine, ograniczony silnik OCR napisany w całości w Object Pascalu: binaryzuje wyrenderowaną stronę metodą Otsu, wyodrębnia glify jako spójne składowe i ocenia każdy glif na podstawie pokrycia szarością względem buforowanych szablonów z wielu fontów, dzięki czemu aplikacja Delphi może zbudować przeszukiwalną warstwę tekstową bez zewnętrznej zależności OCR. Silnik trzeba było odtworzyć od zera w v2.731.0, a powodem nie był matcher. Powodem były piksele

Stary silnik przechodził swoje testy. Rozpoznawał wielkie litery ASCII na syntetycznych bitmapach i na Win32 robił to przez wiele miesięcy. Potem ten sam kod uruchomiono na Win64 i nie zwrócił niczego: żadnych słów, żadnej diagnostyki poza "found no high-contrast foreground", żadnego crasha. Okazało się, że ścieżka odczytu pikseli zawierała dwa niezależne błędy, które wzajemnie się maskowały, a ich rozdzielenie dobrze pokazuje, dlaczego kod OCR zawodzi po cichu, zamiast głośno

Dlaczego stary silnik OCR działał tylko przypadkiem?

Stary silnik działał, ponieważ jego bitmapy szablonów i bitmapy docelowe były odwrócone w ten sam sposób, więc pionowe odwrócenie w czytniku pikseli było niewidoczne dla matchera. TBitmap.ScanLine zwraca wiersze w kolejności przeciwnej do konwencji DIB z dodatnim biHeight, której zakłada reszta ścieżki obrazowania. Wyrenderuj odwróconą literę M, porównaj ją z również odwróconym szablonem, a różnica L1 będzie identyczna jak przy poprawnym porównaniu. Każdy glif pasował. Nic nie było poprawne

Właśnie ta symetria sprawia, że ta klasa błędów jest kosztowna. Jednostronna poprawka psuje dopasowanie: popraw odczyt celu i pozostaw szablony bez zmian, a rozpoznawanie załamie się w szum; popraw najpierw szablony i otrzymasz ten sam efekt z drugiej strony. Nie ma tu ścieżki naprawy przyrostowej. Dlatego przebudowa zastąpiła cały odczyt wywołaniem GetDIBits z jawnie zadeklarowanym BITMAPINFOHEADER, gdzie dodatni biHeight zgodnie z kontraktem oznacza wiersze bottom-up, a następnie wykonuje jedno, zamierzone odwrócenie podczas kopiowania do bufora skali szarości

Drugi błąd ujawnił się dopiero na Win64. HDC przekazywany do GetDIBits nie może być własnym memory DC bitmapy, ponieważ bitmapa jest już w nim wybrana, a dokumentacja Windows uznaje to za nieprawidłowe. Przekazanie Bitmap.Canvas.Handle było tolerowane przez proces Win32 i konsekwentnie zawodziło w procesie testowym Win64. Poprawka używa tymczasowego ekranowego DC z GetDC(0), zwalnianego w bloku finally, który nie ma żadnego związku z bitmapą

procedure BitmapToGray(Bitmap: TBitmap; out Gray: TBytes);
var
  Work: TBitmap;
  Info: TBitmapInfo;
  Buffer: TBytes;
  DC: HDC;
  P: PByte;
  Stride, X, Y: Integer;
begin
  Work := TBitmap.Create;
  try
    Work.Assign(Bitmap);
    Work.PixelFormat := pf24bit;
    Stride := ((Work.Width * 24 + 31) div 32) * 4;
    SetLength(Buffer, Stride * Work.Height);
    FillChar(Info, SizeOf(Info), 0);
    Info.bmiHeader.biSize := SizeOf(BITMAPINFOHEADER);
    Info.bmiHeader.biWidth := Work.Width;
    Info.bmiHeader.biHeight := Work.Height;   // dodatnia wartość => wiersze bottom-up
    Info.bmiHeader.biPlanes := 1;
    Info.bmiHeader.biBitCount := 24;
    Info.bmiHeader.biCompression := BI_RGB;
    DC := GetDC(0);            // nigdy Work.Canvas.Handle: Work jest tam wybrana
    if DC = 0 then
      raise EInvalidOperation.Create('Recognition bitmap pixels could not be read');
    try
      if GetDIBits(DC, Work.Handle, 0, Work.Height,
        @Buffer[0], Info, DIB_RGB_COLORS) <> Work.Height then
        raise EInvalidOperation.Create('Recognition bitmap pixels could not be read');
    finally
      ReleaseDC(0, DC);
    end;
    SetLength(Gray, Work.Width * Work.Height);
    for Y := 0 to Work.Height - 1 do
    begin
      P := @Buffer[(Work.Height - 1 - Y) * Stride];   // jedno zamierzone odwrócenie
      for X := 0 to Work.Width - 1 do
        Gray[Y * Work.Width + X] :=
          (Integer(P[X * 3]) * 29 + Integer(P[X * 3 + 1]) * 150 +
           Integer(P[X * 3 + 2]) * 77) shr 8;
    end;
  finally
    Work.Free;
  end;
end;

Binaryzacja i spójne składowe: od pikseli szarości do ramek glifów

HotPDF najpierw binaryzuje obraz metodą Otsu, a do progu w lokalnym oknie przechodzi tylko wtedy, gdy Otsu nie ma zastosowania. Ścieżka globalna wymaga rzeczywistego bimodalnego histogramu: silnik oblicza maksimum wariancji międzyklasowej, a dodatkowo wymaga, aby zakres szarości obejmował co najmniej 64 poziomy, zanim zaufa wynikowi. Wyblakły skan, strona z gradientowym tłem albo bitmapa niemal całkowicie wypełniona tuszem nie przechodzą tego testu. Fallback porównuje wtedy każdy piksel ze średnią z okna 31 na 31 z przesunięciem o 6 poziomów szarości, obliczaną przez bieżące sumy kolumn, dzięki czemu przesuwne okno zachowuje liniową złożoność względem liczby pikseli

Wyodrębnianie glifów jest etykietowaniem składowych 8-sąsiednich na wynikowej masce, z jawnym stosem zamiast rekursji, ponieważ maska całej strony z łatwością przepełni stos wątku Delphi podczas głębokiego flood fill. Podczas etykietowania działają dwa filtry: składowe mniejsze niż 9 pikseli są odrzucane jako szum punktowy, a każda składowa obejmująca więcej niż trzy piąte szerokości i wysokości obrazu jest odrzucana jako ramka lub linia, a nie glif. Drugi przebieg scala pionowo ułożone ramki, których poziome nakładanie obejmuje co najmniej jedną czwartą węższej ramki, co ponownie łączy kropkę i trzon litery i albo j. Wszystko działa na rastrze, a raster pochodzi z tego samego renderera opisanego w artykule o renderowaniu załadowanej strony PDF do bitmapy w Delphi, co ma praktyczne znaczenie: jakość OCR ma górną granicę wyznaczoną przez jakość renderowania, a domyślne 300 DPI warstwy tekstowej jest zamierzonym kompromisem, a nie maksimum

Co sprawia, że wielkie I i małe l są nierozróżnialne?

W foncie Arial wielkie I i małe l rasteryzują się do identycznych pasków pikseli, więc żadna cecha kształtu nie może ich rozdzielić i wielkość liter musi pochodzić z zupełnie innego źródła. Silnik wykorzystuje klasteryzację wysokości na poziomie wiersza. Ramki glifów są grupowane w wiersze tekstu według nakładania w pionie, każdy wiersz analizuje wysokość wersalików i modalną linię bazową, a wysokości w wierszu dzielone są na klaster krótki i wysoki. Pasek w klastrze krótkim to l, a ten sam pasek w klastrze wysokim to I

Oczywistą implementacją tego podziału jest stały próg ilorazu, ale ona nie działa. Stosunek wysokości x do wysokości wersalików w Arialu wynosi około 0,72, czyli dokładnie trafia w wartości 0,70 i 0,75, po które wszyscy sięgają w pierwszej kolejności. Przesuń stałą o jedną setną w dowolną stronę, a cały korpus zmieni rozpoznaną wielkość liter. HotPDF zamiast tego wykonuje jednowymiarowy podział k=2 minimalizujący wariancję: sortuje kandydackie wysokości, próbuje każdego punktu cięcia i zachowuje ten, dla którego suma kwadratów odchyleń wewnątrz klastrów jest najmniejsza. Próg staje się właściwością strony, a nie stałą w źródle

// ClusterHeights jest posortowane rosnąco; znajdź podział k=2 o najmniejszej wariancji
BestSplit := 1;
BestVariance := 1E18;
for I := 1 to ClusterCount - 1 do
begin
  SumA := 0;
  for J := 0 to I - 1 do SumA := SumA + ClusterHeights[J];
  SumB := 0;
  for J := I to ClusterCount - 1 do SumB := SumB + ClusterHeights[J];
  MeanA := SumA / I;
  MeanB := SumB / (ClusterCount - I);
  Variance := 0;
  for J := 0 to I - 1 do
    Variance := Variance + Sqr(ClusterHeights[J] - MeanA);
  for J := I to ClusterCount - 1 do
    Variance := Variance + Sqr(ClusterHeights[J] - MeanB);
  if Variance < BestVariance then
  begin
    BestVariance := Variance;
    BestSplit := I;
  end;
end;
// tylko iloraz średnich obu klastrów decyduje, które pasmo jest krótkie
if SmallMean / TallMean <= 0.80 then
  SmallGroup := ggSmall          // prawdziwe pasmo wysokości x: kształty małych liter
else
  SmallGroup := ggTall;          // jedno pasmo wysokości: wszystko ma wysokość wersalików
Line.LowercaseContext := (SmallGroup = ggSmall);

Wiersze z jednym pasmem wysokości nie niosą żadnych wewnętrznych dowodów. Nagłówek pisany wielkimi literami i podpis pisany wyłącznie małymi wyglądają osobno tak samo. W takich przypadkach HotPDF porównuje medianę wysokości wiersza z medianą wysokości x na poziomie strony, pobraną z wierszy, które zostały podzielone: iloraz równy najwyżej 1,10 oznacza kontekst małych liter, iloraz równy co najmniej 1,18 oznacza kontekst wersalików, a wartości pomiędzy pozostają bez ograniczenia. Dopasowanie dodaje następnie niewielki bonus preferencji wielkości liter 0,03 dla kandydata zgodnego z tym kontekstem, co rozstrzyga remisy, ale nigdy nie nadpisuje wyraźnej różnicy kształtu

Dlaczego siatka szablonu 12x18 myliła c z o?

Siatkę szablonu poszerzono z 12 na 18 komórek do 16 na 24, ponieważ przy mniejszej rozdzielczości margines pokrycia szarością między c i o spadał poniżej 0,007, czyli znacznie wewnątrz progu niejednoznaczności silnika. Każdy prostokąt glifu jest próbkowany do siatki jako wartości pokrycia od 0 do 255, a nie jako binarna maska, więc komórka wypełniona w jednej trzeciej ma wartość około 85 zamiast zaokrąglenia do czerni albo bieli. Przy 12 na 18 otwarta strona c zajmuje niewiele więcej niż jedną kolumnę komórek, a uśrednienie antyaliasingu zmywa przerwę. Przy 16 na 24 przerwa przetrwa ponowne próbkowanie, a większość łatwo mylonych par wraca do bezpiecznej odległości

Wynik jest znormalizowaną odległością L1 między dwiema siatkami pokrycia plus kara równa 0,30 razy różnica logarytmów proporcji boków oraz 0,16 razy różnica gęstości tuszu, z twardym filtrem wstępnym pomijającym każdy szablon, którego proporcja boków różni się ponad 2,6 raza. Szablony są rasteryzowane raz na proces z pięciu fontów systemowych (Arial, Times New Roman, Courier New, Tahoma i Segoe UI) dla alfabetu 62 znaków, buforowane za sekcją krytyczną i używane przy każdym kolejnym wywołaniu

Ostatnia stała jest interesująca. Gdy wynik drugiego kandydata mieści się w odległości 0,018 od zwycięzcy, HotPDF ogranicza pewność glifu do 0,5, czyli poniżej progu akceptacji 0,55, więc glif nie jest w ogóle emitowany. To zamierzone odcięcie fail-closed, a nie przypadkowy efekt strojenia: ograniczony silnik, który zgaduje, tworzy warstwę tekstową, której treść nie odpowiada obrazowi, a błędne słowo w warstwie tekstowej jest gorsze od brakującego, bo osoba przeglądająca skan go nie widzi

Dzielenie słów bez stałego progu przerwy

HotPDF wyprowadza próg odstępu między słowami dla każdego wiersza z rozkładu przerw między glifami, a nie ze stałej wielokrotności średniej szerokości glifu. Klasyczna heurystyka, "przerwa szersza niż 0,75 średniego wysunięcia oznacza spację", załamuje się, gdy wiersz miesza cyfry z wąskimi literami, ponieważ średnie wysunięcie przestaje opisywać cokolwiek rzeczywistego. Silnik sortuje przerwy w wierszu i szuka największego skoku między kolejnymi wartościami po sortowaniu, który jest granicą między klastrem wewnątrzsłownym i międzysłownym, jeśli taki klaster istnieje. Trzy zabezpieczenia uniemożliwiają reakcję na szum: skok musi wynosić co najmniej 0,22 średniej szerokości glifu, pierwsza przerwa powyżej podziału musi wynosić co najmniej 0,32 tej szerokości, a ostatnia przerwa poniżej podziału nie może przekraczać 0,65 tej szerokości. Jeśli którekolwiek zabezpieczenie nie przejdzie, próg pozostaje równy MaxInt, a cały wiersz staje się jednym słowem. To ostatnie zabezpieczenie nie pozwala, aby pojedyncza wyjątkowo szeroka para kerningu rozcięła słowo na pół, co byłoby znacznie bardziej szkodliwe niż połączenie dwóch słów, ponieważ połączony token nadal zawiera właściwe znaki we właściwej kolejności dla wyszukiwania podłańcuchów

Zapisywanie niewidocznej warstwy tekstowej nad skanowanym obrazem

ApplyLoadedOCRTextLayer zamienia rozpoznane słowa w przeszukiwalną warstwę, rysując je w trybie renderowania tekstu 3, czyli trybie ani-wypełnienie-ani-obrys zdefiniowanym w ISO 32000-1 §9.3.6, i umieszczając nad skanowanym obrazem, z którego pochodzą. Strumień treści zaczyna się od BT, po którym następuje 3 Tr, a każde słowo jest umieszczane macierzą tekstu zbudowaną z raportowanej linii bazowej, wysokości wersalików przeliczonej z pikseli przy żądanym DPI oraz skali poziomej rozciągającej syntetyczny przebieg glifów do zmierzonej szerokości słowa. Wynik można kopiować i przeszukiwać jak tekst, ale niczego nie maluje

Istnieje przeciążenie bez silnika, które samo tworzy wbudowany recognizer, i właśnie jego powinni używać najczęściej wywołujący wbudowanej ścieżki. Rozpoznawanie, walidacja Unicode, rozliczanie budżetu i budowa treści kończą się przed otwarciem transakcji copy-on-write, więc anulowanie, przekroczenie budżetu albo awaria silnika pozostawia graf obiektów i numer wersji bez zmian. Słowa są filtrowane dwukrotnie: silnik odrzuca wszystko poniżej własnego progu pewności pojedynczego glifu 0,55, a następnie THPDFOCRTextLayerOptions.MinimumConfidence (domyślnie 0,5) odrzuca całe słowa poniżej progu wywołującego

var
  Doc: THotPDF;
  Options: THPDFOCRTextLayerOptions;
  Info: THPDFOCRTextLayerInfo;
begin
  Doc := THotPDF.Create(nil);
  try
    Doc.AutoLaunch := False;
    if Doc.LoadFromFile('scan.pdf') < 1 then
      Exit;
    Options := THPDFOCRTextLayerOptions.Default;   // DPI 300, MinimumConfidence 0.5
    Options.SkipPagesWithText := True;             // pozostaw strony born-digital bez zmian
    Options.UseOptionalContentGroup := True;
    Options.OptionalContentGroupName := 'OCR Text Layer';
    // przeciążenie bez silnika: HotPDF dostarcza wbudowany ograniczony recognizer
    if Doc.ApplyLoadedOCRTextLayer([0], Options, Info) then
    begin
      Writeln(Info.AcceptedWordCount, ' words accepted by ',
        string(Info.EngineName));
      Doc.SaveLoadedDocument('scan-searchable.pdf');
    end
    else
      Writeln('No text layer written: ', string(Info.Diagnostic));
  finally
    Doc.Free;
  end;
end;

Warto jasno nazwać jedno ograniczenie, zamiast odkrywać je później. Niewidoczna warstwa używa współdzielonego syntetycznego osadzonego fontu Type0, co wystarcza do wyszukiwania i kopiowania w każdym viewerze, ale nie spełnia wymogu osadzania fontu z ISO 19005. Jeśli wynik musi być PDF/A, wywołujący musi osobno osadzić zgodny font. Warstwa tekstowa OCR niesie też geometrię, a nie strukturę, więc kolejność czytania wynika wyłącznie z pozycji glifów; jeśli potrzebujesz kolejności logicznej ze strony, która ma już prawdziwy tekst, ekstrakcja tekstu w kolejności struktury sterowana drzewem tagów jest innym narzędziem dla innego problemu

Gdzie kończy się wbudowany silnik?

Wbudowany silnik jest celowo wąski, a znajomość jego granic pozwala zachować jego użyteczność. Obsługuje wysokokontrastowy, maszynowo drukowany ASCII z fontów zbliżonych do pięciu twarzy szablonów, a wszystko poza tym zwraca brak słowa zamiast zgadywania. Konkretne granice są następujące:

  • Obrazy do 4096 na 4096 i 4 194 304 pikseli, z limitem rozpoznawania 2000 ms i kooperatywnym anulowaniem przez THPDFCancellationToken
  • Alfabet 62 znaków: litery ASCII i cyfry; bez interpunkcji, znaków diakrytycznych i CJK
  • Wyłącznie tekst osiowo wyrównany, przy obrocie strony już znormalizowanym przez renderer; skany skośne nie są prostowane
  • Niejednoznaczne pary glifów pozostają nierozstrzygnięte, więc strona może zwrócić częściowe słowa albo diagnostykę "found no unambiguous ASCII words"

Gdy ten zakres jest zbyt mały, punktem integracji jest IHPDFOCREngine. Zaimplementuj Recognize we własnym silniku, przekaż go do trzyargumentowego przeciążenia ApplyLoadedOCRTextLayer, a wszystko poniżej — mapowanie współrzędnych, obsługa obrotu, walidacja Unicode, budżety i atomowy commit — pozostanie takie samo. Bitmapa jest wypożyczona na czas synchronicznego wywołania i nie wolno jej zachowywać. Aby potwierdzić, że warstwa została poprawnie zapisana, wczytaj zapisany plik ponownie i uruchom zwykłą ścieżkę tekstową opisaną w artykule o wyodrębnianiu tekstu z załadowanego PDF-a w Delphi; jeśli słowa wrócą, warstwa jest prawdziwa

Wbudowany OCR z dopasowaniem szablonów, niewidoczna warstwa tekstowa, renderer stron, który je zasila, oraz ekstrakcja tekstu z załadowanego dokumentu, która je weryfikuje, są dostarczane w tym samym natywnym komponencie VCL, bez zewnętrznego runtime'u OCR i bez DLL do wdrażania obok aplikacji. Jeśli budujesz przechwytywanie dokumentów, archiwum albo wyszukiwanie w skanowanych PDF-ach w Delphi lub C++Builder, komponent PDF HotPDF dla Delphi daje cały pipeline w jednej zależności