Wykrywanie „rzeki” w tekście

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.

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.

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));

(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));

(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);

(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;

(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”:

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}]

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}]

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:

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

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

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:

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

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

( 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:

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'

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

Moje etykiety:

Prognozy dotyczące obrazu treningowego:

Prognozy na pozostałe dwa obrazy:

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.]

(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ą.