Deteksi “Sungai” dalam teks

Di atas tentang pertukaran stack TeX, kami telah mendiskusikan bagaimana mendeteksi "sungai" dalam paragraf dalam pertanyaan ini .

Dalam konteks ini, sungai adalah pita ruang putih yang dihasilkan dari penyelarasan tak sengaja dari ruang kata dalam teks. Karena ini bisa sangat mengganggu pembaca, sungai yang buruk dianggap sebagai gejala tipografi yang buruk. Contoh teks dengan sungai adalah yang ini, di mana ada dua sungai yang mengalir secara diagonal.

Ada minat dalam mendeteksi sungai-sungai ini secara otomatis, sehingga mereka dapat dihindari (mungkin dengan mengedit teks secara manual). Raphink membuat beberapa kemajuan pada level TeX (yang hanya tahu posisi mesin terbang dan kotak pembatas), tapi saya merasa yakin bahwa cara terbaik untuk mendeteksi sungai adalah dengan beberapa pemrosesan gambar (karena bentuk mesin terbang sangat penting dan tidak tersedia untuk TeX) . Saya telah mencoba berbagai cara untuk mengekstrak sungai dari gambar di atas, tetapi ide sederhana saya untuk menerapkan sedikit ellipsoidal blurring tampaknya tidak cukup baik. Saya juga mencoba beberapa RadonHough mengubah pemfilteran berdasarkan, tapi saya juga tidak berhasil. Sungai-sungai sangat terlihat oleh sirkuit pendeteksian fitur mata / retina / otak manusia dan entah bagaimana saya akan berpikir ini dapat diterjemahkan ke beberapa jenis operasi penyaringan, tetapi saya tidak dapat membuatnya berfungsi. Ada ide?

Untuk lebih spesifik, saya mencari beberapa operasi yang akan mendeteksi 2 sungai pada gambar di atas, tetapi tidak memiliki terlalu banyak deteksi positif palsu lainnya.

EDIT: endolith bertanya mengapa saya mengejar pendekatan berbasis pemrosesan gambar mengingat bahwa di TeX kita memiliki akses ke posisi mesin terbang, jarak, dll, dan mungkin akan jauh lebih cepat dan lebih dapat diandalkan untuk menggunakan algoritma yang memeriksa teks yang sebenarnya. Alasan saya melakukan sesuatu dengan cara lain adalah karena bentuknyadari mesin terbang dapat mempengaruhi seberapa terlihat sungai, dan pada tingkat teks sangat sulit untuk mempertimbangkan bentuk ini (yang tergantung pada font, ligaturing, dll). Untuk contoh bagaimana bentuk mesin terbang dapat menjadi penting, pertimbangkan dua contoh berikut, di mana perbedaan di antara mereka adalah bahwa saya telah mengganti beberapa mesin terbang dengan yang hampir sama lebarnya, sehingga analisis berbasis teks akan mempertimbangkan mereka sama-sama baik / buruk. Perhatikan, bagaimanapun, bahwa sungai-sungai dalam contoh pertama jauh lebih buruk daripada yang kedua.

Saya telah memikirkan hal ini lagi, dan berpikir bahwa yang berikut ini harusnya cukup stabil. Perhatikan bahwa saya membatasi diri pada operasi morfologis, karena ini harus tersedia di pustaka pemrosesan gambar standar.

(1) Buka gambar dengan topeng nPix-by-1, di mana nPix adalah tentang jarak vertikal antara huruf

#% 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) Buka gambar dengan topeng 1-by-mPix untuk menghilangkan apa pun yang terlalu sempit untuk menjadi sungai.

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

(3) Hapus "sungai dan danau" horisontal yang disebabkan oleh jarak antar paragraf, atau lekukan. Untuk ini, kami menghapus semua baris yang semuanya benar, dan membuka dengan topeng nPix-by-1 yang kami tahu tidak akan memengaruhi sungai yang telah kami temukan sebelumnya.

Untuk menghapus danau, kita bisa menggunakan topeng pembuka yang sedikit lebih besar dari nPix-by-nPix.

Pada langkah ini, kita juga dapat membuang segala sesuatu yang terlalu kecil untuk menjadi sungai sungguhan, yaitu segala sesuatu yang luasnya kurang dari (nPix + 2) * (mPix + 2) * 4 (yang akan memberi kita ~ 3 baris). +2 ada di sana karena kita tahu bahwa semua objek setidaknya memiliki ketinggian nPix, dan lebar mPix, dan kami ingin sedikit lebih tinggi dari itu.

%# 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) Jika kita tertarik tidak hanya panjangnya, tetapi juga lebar sungai, kita dapat menggabungkan transformasi jarak dengan kerangka.

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

   riversWithWidth = dt.*sk;

(warna sesuai dengan lebar sungai (meskipun bilah warna tidak aktif karena faktor 2)

Sekarang Anda bisa mendapatkan perkiraan panjang sungai dengan menghitung jumlah piksel di setiap komponen yang terhubung, dan lebar rata-rata dengan rata-rata nilai pikselnya.

Inilah analisis yang persis sama yang diterapkan pada gambar "no-river" yang kedua:

Dalam Mathematica, menggunakan erosi dan transformasi Hough:

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

Edit Menjawab komentar Pak Wisaya

Jika Anda ingin menghilangkan garis horizontal, lakukan saja hal seperti ini (mungkin seseorang bisa membuatnya lebih sederhana):

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

Hmmm ... Saya kira transformasi Radon tidak mudah untuk diekstrak. (Transformasi Radon pada dasarnya merotasi gambar sambil "melihat menembusnya". Ini adalah prinsip di balik pemindaian CAT.) Transformasi gambar Anda menghasilkan sinogram ini, dengan "sungai" membentuk puncak cerah, yang dilingkari:

Yang pada rotasi 70 derajat dapat dilihat cukup jelas sebagai puncak di sebelah kiri plot potongan ini sepanjang sumbu horizontal:

Terutama jika teksnya Gaussian kabur terlebih dahulu:

Tapi saya tidak yakin bagaimana cara mengekstrak puncak-puncak ini dari kebisingan. Ujung atas dan bawah sinogram yang terang mewakili "sungai" di antara garis-garis horizontal teks, yang jelas tidak Anda pedulikan. Mungkin fungsi bobot vs sudut yang lebih menekankan garis vertikal dan meminimalkan yang horizontal?

Fungsi pembobotan kosinus sederhana bekerja dengan baik pada gambar ini:

menemukan sungai vertikal pada 90 derajat, yang merupakan puncak global dalam sinogram:

dan pada gambar ini menemukan satu pada 104 derajat, meskipun kabur pertama membuatnya lebih akurat:

( radon()Fungsi SciPy agak bodoh , atau saya akan memetakan puncak ini kembali ke gambar asli sebagai garis yang melewati tengah sungai.)

Tapi itu tidak menemukan salah satu dari dua puncak utama dalam sinogram untuk gambar Anda, setelah kabur dan berat:

Mereka ada di sana, tetapi mereka kewalahan oleh hal-hal di dekat puncak tengah dari fungsi pembobotan. Dengan pembobotan yang tepat dan penyesuaian metode ini mungkin bisa berhasil, tetapi saya tidak yakin apa yang benar. Mungkin juga tergantung pada properti pemindaian halaman. Mungkin pembobotan perlu berasal dari energi keseluruhan dalam irisan atau sesuatu, seperti normalisasi.

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'

Saya melatih classifier diskriminatif pada piksel menggunakan fitur turunan (hingga urutan ke-2) pada skala yang berbeda.

Label saya:

Prediksi pada gambar pelatihan:

Prediksi pada dua gambar lainnya:

Saya kira ini terlihat menjanjikan dan dapat menghasilkan hasil yang dapat digunakan mengingat lebih banyak data pelatihan dan mungkin fitur yang lebih cerdas. Di sisi lain saya hanya butuh beberapa menit untuk mendapatkan hasil ini. Anda dapat mereproduksi hasil sendiri dengan menggunakan ilastik perangkat lunak sumber terbuka . [Penafian: Saya salah satu pengembang utama.]

(Maaf, pos ini tidak disertai demonstrasi yang luar biasa.)

Jika Anda ingin bekerja dengan informasi yang sudah dimiliki TeX (huruf dan posisi), Anda dapat secara manual mengklasifikasikan pasangan surat dan huruf sebagai "miring" dalam satu arah atau lainnya. Sebagai contoh, "w" memiliki sudut sudut SW dan SE, kombo "al" memiliki kemiringan sudut NW, "k" memiliki kemiringan sudut sudut NE. (Jangan lupa tanda baca - kutipan yang diikuti oleh surat yang mengisi bagian bawah kotak mesin terbang menghasilkan kemiringan yang bagus; kutipan yang diikuti oleh q sangat kuat.)

Kemudian, cari kejadian kemiringan yang sesuai pada sisi berlawanan dari suatu ruang - "dengan" untuk sungai SW-ke-NE atau "k T" untuk sungai NW-ke-SE. Ketika Anda menemukan satu di garis, lihat apakah yang serupa terjadi, bergeser ke kanan atau kanan, pada garis di atas / di bawah; ketika Anda menemukan jalannya, mungkin ada sungai.

Juga, jelas, hanya mencari ruang yang ditumpuk hampir vertikal, untuk sungai vertikal polos.

Anda bisa mendapatkan sedikit lebih canggih dengan mengukur "kekuatan" lereng: berapa banyak kotak muka "kosong" karena kemiringan dan dengan demikian berkontribusi pada lebar sungai. "w" cukup kecil, karena hanya memiliki sudut kecil kotak muka untuk berkontribusi ke sungai, tetapi "V" sangat kuat. "b" sedikit lebih kuat dari "k"; kurva yang lebih lembut memberikan tepi sungai yang lebih kontinyu secara visual, menjadikannya lebih kuat dan lebih luas secara visual.