Wykrywanie „rzeki” w tekście

175

W trakcie wymiany stosów TeX rozmawialiśmy o tym, jak wykryć „rzeki” w akapitach tego pytania .

W tym kontekście rzeki to pasma białych znaków, które powstają w wyniku przypadkowego wyrównania odstępów międzytekstowych w tekście. Ponieważ może to być dość rozpraszające dla czytelnika, złe rzeki są uważane za objaw złej typografii. Przykładem tekstu z rzekami jest ta, w której dwie rzeki płyną po przekątnej.

wprowadź opis zdjęcia tutaj

Istnieje zainteresowanie automatycznym wykrywaniem rzek, aby można było ich uniknąć (prawdopodobnie poprzez ręczną edycję tekstu). Raphink robi pewne postępy na poziomie TeX (który zna tylko pozycje glifów i ramki ograniczające), ale jestem przekonany, że najlepszym sposobem na wykrycie rzek jest trochę przetwarzania obrazu (ponieważ kształty glifów są bardzo ważne i niedostępne dla TeXa) . Próbowałem różnych sposobów na wydobycie rzek z powyższego obrazu, ale mój prosty pomysł zastosowania niewielkiej ilości elipsoidalnego rozmycia nie wydaje się wystarczający. Spróbowałem też RadonaFiltrowanie oparte na transformacji Hougha, ale z nimi też nie dotarłem. Rzeki są bardzo widoczne dla obwodów detekcji ludzkiego oka / siatkówki / mózgu i jakoś sądzę, że można to przełożyć na jakąś operację filtrowania, ale nie jestem w stanie sprawić, by działała. Jakieś pomysły?

Mówiąc ściślej, szukam operacji, która wykryje 2 rzeki na powyższym obrazie, ale nie wykryje zbyt wielu innych fałszywych alarmów.

EDYCJA: endolith zapytał, dlaczego stosuję podejście oparte na przetwarzaniu obrazu, biorąc pod uwagę, że w TeXie mamy dostęp do pozycji glifów, odstępów itp. I może być znacznie szybsze i bardziej niezawodne użycie algorytmu, który bada rzeczywisty tekst. Moim powodem robienia rzeczy w inny sposób jest kształtglifów może wpływać na to, jak zauważalna jest rzeka, a na poziomie tekstu bardzo trudno jest wziąć pod uwagę ten kształt (który zależy od czcionki, ligaturacji itp.). Na przykład, w jaki sposób kształt glifów może być ważny, rozważ dwa następujące przykłady, w których różnica między nimi polega na tym, że zamieniłem kilka glifów na inne o prawie takiej samej szerokości, aby analiza tekstowa rozważyła są równie dobre / złe. Należy jednak pamiętać, że rzeki w pierwszym przykładzie są znacznie gorsze niż w drugim.

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

Lev Bishop
źródło
5
+1 Podoba mi się to pytanie. Moją pierwszą myślą jest transformacja Hougha , ale prawdopodobnie wymagałaby ona wstępnego przetworzenia. Może najpierw filtr dylatacyjny .
Datageist
Dziwi mnie, że transformacja Radona właściwie nie działała. Jak to zrobiłeś?
endolith,
@endolith: Nic wyszukanego. Użyłem ImageLines[]z Mathematica, z pewnym przetwarzaniem wstępnym i bez niego. Myślę, że technicznie używa się transformacji Hougha zamiast Radona. Nie zdziwię się, jeśli poprawne przetwarzanie wstępne (nie próbowałem sugerowanego przez filtr danych filtru dylatacyjnego) i / lub ustawienia parametrów mogą zadziałać.
Lev Bishop
Wyszukiwarka grafiki Google dla rzek także pokazuje rzeki „kręte”. Czy chcesz je znaleźć? cdn.ilovetypography.com/img/text-river1.gif
endolit
@endolith Wydaje mi się, że ostatecznie chcę zreplikować przetwarzanie ludzkiego systemu wzrokowego, który rozprasza niektóre konfiguracje przestrzeni. Ponieważ może się to zdarzyć również w przypadku meandrujących rzek, chciałbym je złapać, chociaż te proste wydają się ogólnie stanowić większy problem. Jeszcze lepszy byłby sposób na oszacowanie „zła” rzek w sposób, który odpowiada ich silnej widoczności podczas czytania tekstu. Ale to wszystko jest bardzo subiektywne i trudne do oszacowania. Po pierwsze, wystarczy po prostu złapać naprawdę wszystkie złe rzeki bez zbyt wielu fałszywych trafień.
Lev Bishop

Odpowiedzi:

135

Zastanowiłem się nad tym trochę i uważam, że następujące elementy powinny być dość stabilne. Zauważ, że ograniczyłem się do operacji morfologicznych, ponieważ powinny one być dostępne w dowolnej standardowej bibliotece przetwarzania obrazu.

(1) Otwórz obraz za pomocą maski nPix-by-1, gdzie nPix jest mniej więcej pionową odległością między literami

#% read image
img = rgb2gray('http://i.stack.imgur.com/4ShOW.png');

%# threshold and open with a rectangle
%# that is roughly letter sized
bwImg = img > 200; %# threshold of 200 is better than 128

opImg = imopen(bwImg,ones(13,1));

wprowadź opis zdjęcia tutaj

(2) Otwórz zdjęcie za pomocą maski 1 na mPix, aby wyeliminować wszystko, co jest zbyt wąskie, aby mogło być rzeką.

opImg = imopen(opImg,ones(1,5));

wprowadź opis zdjęcia tutaj

(3) Usuń poziome „rzeki i jeziora”, które są spowodowane odstępem między akapitami lub wcięciem. W tym celu usuwamy wszystkie wiersze, które są prawdziwe, i otwieramy za pomocą maski nPix-by-1, która, jak wiemy, nie wpłynie na rzeki, które znaleźliśmy wcześniej.

Aby usunąć jeziora, możemy użyć maski otwierającej, która jest nieco większa niż nPix-by-nPix.

Na tym etapie możemy również wyrzucić wszystko, co jest zbyt małe, aby być prawdziwą rzeką, tj. Wszystko, co obejmuje mniejszy obszar niż (nPix + 2) * (mPix + 2) * 4 (co da nam ~ 3 linie). Jest tam +2, ponieważ wiemy, że wszystkie obiekty mają co najmniej nPix wysokości i mPix szerokości, i chcemy pójść nieco wyżej.

%# horizontal river: just look for rows that are all true
opImg(all(opImg,2),:) = false;
%# open with line spacing (nPix)
opImg = imopen(opImg,ones(13,1));

%# remove lakes with nPix+2
opImg = opImg & ~imopen(opImg,ones(15,15)); 

%# remove small fry
opImg = bwareaopen(opImg,7*15*4);

wprowadź opis zdjęcia tutaj

(4) Jeśli interesuje nas nie tylko długość, ale także szerokość rzeki, możemy połączyć transformację odległości ze szkieletem.

   dt = bwdist(~opImg);
   sk = bwmorph(opImg,'skel',inf);
   %# prune the skeleton a bit to remove branches
   sk = bwmorph(sk,'spur',7);

   riversWithWidth = dt.*sk;

wprowadź opis zdjęcia tutaj (kolory odpowiadają szerokości rzeki (choć pasek kolorów jest wyłączony 2 razy)

Teraz możesz uzyskać przybliżoną długość rzek, zliczając liczbę pikseli w każdym podłączonym komponencie i średnią szerokość, uśredniając ich wartości pikseli.


Oto dokładna analiza zastosowana do drugiego obrazu „no-river”:

wprowadź opis zdjęcia tutaj

Jonas
źródło
Dzięki. Mam Matlaba, więc wypróbuję to w innych tekstach, aby zobaczyć, jak będzie solidny.
Lev Bishop
Ponowne zintegrowanie go z TeXem może być innym problemem, chyba że możemy jakoś przenieść to na Luę.
ℝaphink
@LevBishop: Myślę, że rozumiem ten problem nieco lepiej. Nowe rozwiązanie powinno być dość solidne.
Jonas
@levBishop: Jeszcze jedna aktualizacja.
Jonas
1
@LevBishop: Właśnie zauważyłem drugi obraz. Okazuje się, że analiza oparta na morfologii spełnia swoje zadanie.
Jonas
56

W Mathematica za pomocą erozji i transformacji Hougha:

(*Get Your Images*)
i = Import /@ {"http://i.stack.imgur.com/4ShOW.png", 
               "http://i.stack.imgur.com/5UQwb.png"};

(*Erode and binarize*)
i1 = Binarize /@ (Erosion[#, 2] & /@ i);

(*Hough transform*)
lines = ImageLines[#, .5, "Segmented" -> True] & /@ i1;

(*Ready, show them*)
Show[#[[1]],Graphics[{Thick,Orange, Line /@ #[[2]]}]] & /@ Transpose[{i, lines}]

wprowadź opis zdjęcia tutaj

Edytuj odpowiedź na komentarz pana Kreatora

Jeśli chcesz pozbyć się poziomych linii, po prostu zrób coś takiego (prawdopodobnie ktoś mógłby to uprościć):

Show[#[[1]], Graphics[{Thick, Orange, Line /@ #[[2]]}]] & /@ 
 Transpose[{i, Select[Flatten[#, 1], Chop@Last@(Subtract @@ #) != 0 &] & /@ lines}]

wprowadź opis zdjęcia tutaj

Dr Belizariusz
źródło
1
Dlaczego nie pozbyć się wszystkich poziomych linii? (+1)
Mr.Wizard
@Pan. Aby pokazać, że wszystkie linie są wykrywane ...
Dr Belisarius
1
To nie jest jednak część problemu, prawda?
Mr.Wizard
@Pan. Edytowane zgodnie z prośbą
Dr Belisarius
4
@belisarius Układ współrzędnych użyty w transformacie Hougha zmienił się po wersji 8.0.0, aby dopasować ją do transformacji Radona. To z kolei zmieniło zachowanie ImageLines. Ogólnie rzecz biorąc, jest to poprawa, choć w tym przypadku preferowane byłoby wcześniejsze zachowanie. Jeśli nie chcą eksperymentować z szczytowych wykryć, można zmienić proporcje obrazu wejściowego, aby być bliżej 1 i uzyskania efektu podobnego do 8.0.0: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. Biorąc to wszystko pod uwagę, podejście morfologiczne wydaje się bardziej solidne.
Matthias Odisio
29

Hmmm ... Myślę, że transformacja Radona nie jest taka łatwa do wydobycia. (Transformacja radonowa zasadniczo obraca obraz podczas „patrzenia przez niego” brzegiem. Jest to zasada skanów CAT). Transformacja twojego obrazu tworzy ten sinogram, z „rzekami” tworzącymi jasne szczyty, które są zakreślone:

wprowadź opis zdjęcia tutaj

Ten przy obrocie o 70 stopni jest dość wyraźnie widoczny jako szczyt po lewej stronie tego wykresu plastra wzdłuż osi poziomej:

wprowadź opis zdjęcia tutaj

Zwłaszcza jeśli tekst był najpierw rozmazany Gaussa:

wprowadź opis zdjęcia tutaj

Ale nie jestem pewien, jak niezawodnie wydobyć te szczyty z reszty szumu. Jasne górne i dolne końce sinogramu reprezentują „rzeki” między poziomymi liniami tekstu, na których oczywiście nie masz znaczenia. Może funkcja ważenia w funkcji kąta podkreśla więcej linii pionowych i minimalizuje linie poziome?

Prosta funkcja ważenia cosinus dobrze działa na tym obrazie:

wprowadź opis zdjęcia tutaj

znajdowanie pionowej rzeki pod kątem 90 stopni, która jest globalnymi maksimami na sinogramie:

wprowadź opis zdjęcia tutaj

a na tym zdjęciu znalezienie tego przy 104 stopniach, choć najpierw rozmycie powoduje, że jest bardziej dokładne:

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

( radon()Funkcja SciPy jest trochę głupia , inaczej odwzoruję ten szczyt z powrotem na oryginalny obraz jako linię przechodzącą przez środek rzeki.)

Ale po rozmyciu i ważeniu nie znajduje żadnego z dwóch głównych pików na sinogramie dla twojego obrazu:

wprowadź opis zdjęcia tutaj

Są tam, ale są przytłoczeni materiałami w pobliżu środkowego szczytu funkcji ważenia. Przy odpowiednim ważeniu i poprawianiu ta metoda prawdopodobnie mogłaby działać, ale nie jestem pewien, jakie są poprawne poprawki. Prawdopodobnie zależy to również od właściwości skanów strony. Może ważenie musi być wyprowadzone z ogólnej energii w plasterku lub czymś takim, jak normalizacja.

from pylab import *
from scipy.misc import radon
import Image

filename = 'rivers.png'
I = asarray(Image.open(filename).convert('L').rotate(90))

# Do the radon transform and display the result
a = radon(I, theta = mgrid[0:180])

# Remove offset
a = a - min(a.flat)

# Weight it to emphasize vertical lines
b = arange(shape(a)[1]) #
d = (0.5-0.5*cos(b*pi/90))*a

figure()
imshow(d.T)
gray()
show()

# Find the global maximum, plot it, print it
peak_x, peak_y = unravel_index(argmax(d),shape(d))
plot(peak_x, peak_y,'ro')
print len(d)- peak_x, 'pixels', peak_y, 'degrees'
endolit
źródło
Co jeśli najpierw rozmyjesz asymetryczny gaussowski? Tj. Wąski w kierunku poziomym, szeroki w kierunku pionowym.
Jonas,
@Jonas: To prawdopodobnie by pomogło. Głównym problemem jest automatyczne wybieranie pików z tła, gdy tło zmienia się tak bardzo wraz z obrotem. Asymetryczne rozmycie może wygładzić poziome paski od linii do linii.
endolith,
Działa to dobrze dla wykrywania obrót linii w tekście co najmniej: gist.github.com/endolith/334196bac1cac45a4893
endolit
16

Przeszkoliłem klasyfikator dyskryminujący piksele przy użyciu funkcji pochodnych (do 2. rzędu) w różnych skalach.

Moje etykiety:

Etykietowanie

Prognozy dotyczące obrazu treningowego:

wprowadź opis zdjęcia tutaj

Prognozy na pozostałe dwa obrazy:

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

Wydaje mi się, że wygląda to obiecująco i może przynieść użyteczne wyniki, biorąc pod uwagę więcej danych szkoleniowych i być może inteligentniejsze funkcje. Z drugiej strony uzyskanie tych wyników zajęło mi tylko kilka minut. Możesz odtworzyć wyniki samodzielnie, korzystając z oprogramowania open source ilastik . [Oświadczenie: Jestem jednym z głównych programistów.]

Bernhard Kausler
źródło
2

(Przepraszamy, ten post nie zawiera niesamowitych demonstracji).

Jeśli chcesz pracować z informacjami, które TeX już posiada (litery i pozycje), możesz ręcznie klasyfikować litery i pary liter jako „pochyłe” w jednym lub drugim kierunku. Na przykład „w” ma nachylenie narożne SW i SE, kombinacja „al” ma nachylenie narożne NW, „k” ma nachylenie narożne NE. (Nie zapomnij interpunkcji - cytat, po którym następuje litera wypełniająca dolną połowę pola glifu, tworzy przyjemne nachylenie; cytat po którym następuje q jest szczególnie silny.)

Następnie poszukaj występowania odpowiadających stoków po przeciwnych stronach przestrzeni - „w al” dla rzeki SW-do-NE lub „k T” dla rzeki NW-do-SE. Kiedy znajdziesz jeden w linii, sprawdź, czy podobny wiersz występuje odpowiednio przesunięty w lewo lub w prawo na liniach powyżej / poniżej; kiedy znajdziesz ich szereg, prawdopodobnie jest tam rzeka.

Oczywiście po prostu poszukaj przestrzeni ułożonych prawie pionowo, dla prostych pionowych rzek.

Możesz się nieco bardziej wyrafinować, mierząc „siłę” stoku: ile skrzynek postępowych jest „pustych” ze względu na nachylenie, a tym samym wpływa na szerokość rzeki. „w” jest dość małe, ponieważ ma tylko niewielki narożnik swojego pudełka awansu, aby przyczynić się do rzeki, ale „V” jest bardzo silny. „b” jest nieco silniejsze niż „k”; łagodna krzywa zapewnia bardziej ciągłą wizualnie krawędź rzeki, czyniąc ją silniejszą i wizualnie szerszą.

Xanthir
źródło