Pertanyaan Apakah ada algoritma yang efisien untuk segmentasi teks tulisan tangan?


Saya ingin secara otomatis membagi gambar teks tulisan tangan kuno dengan garis (dan dengan kata-kata di masa depan).

Bagian yang jelas pertama adalah preprocessing gambar ...

Saya hanya menggunakan digitalisasi sederhana (berdasarkan kecerahan piksel). Setelah itu saya menyimpan data ke dalam array dua dimensi.

Bagian jelas berikutnya adalah menganalisa array biner.

  1. Algoritma pertama saya cukup sederhana - jika ada lebih banyak piksel hitam di deretan array daripada akar-rata-persegi Maksimum dan Minimum nilai, maka baris ini adalah bagian dari garis.

    Setelah membentuk daftar garis saya memotong garis dengan tinggi itu kurang dari rata-rata. Akhirnya itu berubah menjadi semacam regresi linier, mencoba untuk meminimalkan perbedaan antara baris kosong dan baris teks. (Saya berasumsi fakta itu) First results

  2. Upaya kedua saya - saya mencoba menggunakan GA dengan beberapa fungsi kebugaran. Kromosom mengandung 3 nilai - xo, x1, x2. xo [-1; 0] x1 [0; 0,5] x2 [0, 0,5]

Fungsi, yang menentukan identitas baris ke baris adalah (xo + α1 x1 + α2 x2)> 0, di mana α1 adalah jumlah piksel hitam di baris, α2 adalah nilai tengah rentang antara piksel hitam ekstrim di baris. (a1, a2 [0,1]) Fungsi lain, yang saya coba adalah (x1 <α1 ATAU x2> α2) dan (1 / xo + [a1 x1] / [a2 x2])> 0 Fungsi terakhir adalah yang paling efisien. Results with GA Fungsi kebugarannya (1 / (HeigthRange + SpacesRange)

Dimana range adalah selisih antara maksimum dan minimum. Ini mewakili homogenitas teks. Optimal global dari fungsi ini - cara paling halus untuk membagi gambar menjadi garis.

Saya menggunakan C # dengan GA berkode sendiri (klasik, dengan 2-point crossover, kode-abu kromosom, populasi maksimum adalah 40, tingkat mutasi adalah 0,05)

Sekarang saya kehabisan ide bagaimana membagi gambar ini menjadi garis dengan akurasi ~ 100%.

Apa algoritma yang efisien untuk melakukan ini?


MEMPERBARUI: Gambar asli BMP Asli (1,3 MB)


UPDATE2: Hasil yang ditingkatkan pada teks ini menjadi 100% Nev results

Bagaimana saya melakukannya:

  • bug minor tetap dalam hitungan jangkauan
  • mengubah fungsi kebugaran menjadi 1 / (jarakRentang + 1) * (ketinggianRentang + 1))
  • fungsi klasifikasi minimal ke (1 / xo + x2 / range)> 0 (poin dalam baris sekarang tidak mempengaruhi klasifikasi) (yaitu data input yang dioptimalkan dan membuat pengoptimalan fungsi kebugaran lebih eksplisit)

Masalah:

Problem

GA mengejutkan gagal mengenali baris ini. Saya melihat data debug dari fungsi 'temukan rage' dan temukan, bahwa ada terlalu banyak noise di tempat yang 'tidak dikenal'. Kode fungsi di bawah ini:

public double[] Ranges()
{
            var ranges = new double[_original.Height];

            for (int y = 0; y < _original.Height; y++ )
            {
                ranges[y] = 0;
                var dx = new List<int>();
                int last = 0;
                int x = 0; 

                while (last == 0 && x<_original.Width)
                {
                    if (_bit[x, y])
                        last = x;
                    x++;
                }

                if (last == 0)
                {
                    ranges[y] = 0;
                    continue;
                }

                for (x = last; x<_original.Width; x++)
                {
                    if (!_bit[x, y]) continue; 

                    if (last != x - 1)
                    {
                        dx.Add((x-last)+1);
                    }
                    last = x;
                }
                if (dx.Count > 2)
                {
                    dx.Sort();
                    ranges[y] = dx[dx.Count / 2];
                    //ranges[y] = dx.Average();
                }
                else
                    ranges[y] = 0;
            }

        var maximum = ranges.Max();
        for (int i = 0; i < ranges.Length; i++)
        {
            if (Math.Abs(ranges[i] - 0) < 0.9)
                ranges[i] = maximum;
        }
        return ranges;
}

Saya menggunakan beberapa peretasan dalam kode ini. Alasan utama - Saya ingin meminimalkan kisaran antara piksel hitam terdekat, tetapi jika tidak ada piksel, nilainya menjadi '0', dan menjadi tidak mungkin untuk memecahkan masalah ini dengan menemukan optimas. Alasan kedua - kode ini terlalu sering berubah. Saya akan mencoba sepenuhnya mengubah kode ini, tetapi saya tidak tahu cara melakukannya.

Q:

  1. Jika ada fungsi kebugaran yang lebih efisien?
  2. Bagaimana menemukan fungsi penentuan yang lebih serbaguna?

32
2017-11-04 19:55


asal


Jawaban:


Meskipun saya tidak yakin bagaimana menerjemahkan algoritme berikut ke dalam GA (dan saya tidak yakin mengapa Anda perlu menggunakan GA untuk masalah ini), dan saya dapat melenceng dalam mengusulkannya, begini.

Teknik sederhana yang akan saya usulkan adalah menghitung jumlah piksel hitam per baris. (Sebenarnya kepadatan pixel gelap per baris.) Ini membutuhkan sangat sedikit operasi, dan dengan beberapa perhitungan tambahan tidak sulit untuk menemukan puncak dalam histogram piksel-sum.

Histogram mentah akan terlihat seperti ini, di mana profil di sepanjang sisi kiri menunjukkan jumlah piksel gelap berturut-turut. Untuk visibilitas, hitungan aktual dinormalisasi untuk merentangkan ke x = 200.

raw horizontal count

Setelah beberapa tambahan, proses sederhana ditambahkan (dijelaskan di bawah), kita dapat menghasilkan histogram seperti ini yang dapat dipangkas pada beberapa nilai ambang. Yang tersisa adalah puncak yang menunjukkan pusat garis teks.

processed horizontal count

Dari sana itu masalah sederhana untuk menemukan garis: hanya klip (ambang) histogram pada beberapa nilai seperti 1/2 atau 2/3 maksimum, dan opsional periksa bahwa lebar puncak pada ambang kliping Anda adalah beberapa nilai minimum w.

Salah satu implementasi dari algoritma lengkap (namun masih sederhana!) Untuk menemukan histogram yang lebih bagus adalah sebagai berikut:

  1. Binarize gambar menggunakan "moving average" threshold atau teknik thresholding lokal yang serupa dalam kasus ambang batas Otsu standar yang beroperasi pada piksel dekat tidak memuaskan. Atau, jika Anda memiliki gambar hitam-putih yang bagus, cukup gunakan 128 sebagai ambang binerisasi Anda.
  2. Buat array untuk menyimpan histogram Anda. Panjang larik ini akan menjadi tinggi dari gambar.
  3. Untuk setiap piksel (x, y) dalam gambar biner, temukan jumlah piksel gelap di atas dan di bawah (x, y) pada beberapa radius R. Artinya, hitung jumlah piksel gelap dari (x, y - R) ke x (y + R), inklusif.
  4. Jika jumlah piksel gelap dalam radius vertikal R sama atau lebih besar dengan R - yaitu, setidaknya setengah piksel gelap - maka piksel (x, y) memiliki cukup tetangga gelap yang gelap. Menambah jumlah bin Anda untuk baris y.
  5. Saat Anda berbaris di sepanjang setiap baris, lacak nilai x paling kiri dan paling kanan untuk piksel dengan tetangga yang memadai. Sepanjang lebar (kanan-kiri + 1) melebihi beberapa nilai minimum, bagilah jumlah total piksel gelap dengan lebar ini. Ini menormalkan hitungan untuk memastikan garis pendek seperti baris teks terakhir disertakan.
  6. (Opsional) Menghaluskan histogram yang dihasilkan. Saya hanya menggunakan rata-rata lebih dari 3 baris.

"Hitungan vertikal" (langkah 3) menghilangkan goresan horizontal yang kebetulan terletak di atas atau di bawah garis tengah teks. Algoritma yang lebih canggih hanya akan memeriksa langsung di atas dan di bawah (x, y), tetapi juga ke kiri atas, kanan atas, kiri bawah, dan kanan bawah.

Dengan implementasi agak kasar saya di C # saya mampu memproses gambar dalam waktu kurang dari 75 milidetik. Dalam C ++, dan dengan beberapa pengoptimalan dasar, saya tidak ragu lagi waktu dapat dikurangi.

Metode histogram ini mengasumsikan teks itu horisontal. Karena algoritma ini cukup cepat, Anda mungkin memiliki cukup waktu untuk menghitung histogram hitungan piksel dengan penambahan setiap 5 derajat dari horizontal. Orientasi pemindaian dengan perbedaan puncak / lembah terbesar akan menunjukkan rotasi.

Saya tidak akrab dengan terminologi GA, tetapi jika apa yang saya sarankan adalah beberapa nilai saya yakin Anda dapat menerjemahkannya ke dalam istilah GA. Bagaimanapun, saya tertarik pada masalah ini, jadi saya mungkin juga berbagi.

EDIT: mungkin untuk menggunakan GA, lebih baik untuk berpikir dalam hal "jarak sejak piksel gelap sebelumnya di X" (atau sepanjang sudut theta) dan "jarak sejak piksel gelap sebelumnya di Y" (atau sepanjang sudut [theta - pi / 2] ). Anda juga dapat memeriksa jarak dari piksel putih ke piksel gelap di semua arah radial (untuk menemukan loop).

byte[,] arr = get2DArrayFromBitamp();   //source array from originalBitmap
int w = arr.GetLength(0);               //width of 2D array
int h = arr.GetLength(1);               //height of 2D array

//we can use a second 2D array of dark pixels that belong to vertical strokes
byte[,] bytes = new byte[w, h];         //dark pixels in vertical strokes


//initial morph
int r = 4;        //radius to check for dark pixels
int count = 0;    //number of dark pixels within radius

//fill the bytes[,] array only with pixels belonging to vertical strokes
for (int x = 0; x < w; x++)
{
    //for the first r rows, just set pixels to white
    for (int y = 0; y < r; y++)
    {
        bytes[x, y] = 255;
    }

    //assume pixels of value < 128 are dark pixels in text
    for (int y = r; y < h - r - 1; y++)
    {
        count = 0;

        //count the dark pixels above and below (x,y)
        //total range of check is 2r, from -r to +r
        for (int j = -r; j <= r; j++)
        {
            if (arr[x, y + j] < 128) count++;
        }

        //if half the pixels are dark, [x,y] is part of vertical stroke
        bytes[x, y] = count >= r ? (byte)0 : (byte)255;
    }

    //for the last r rows, just set pixels to white
    for (int y = h - r - 1; y < h; y++)
    {
        bytes[x, y] = 255;
    }
}

//count the number of valid dark pixels in each row
float max = 0;

float[] bins = new float[h];    //normalized "dark pixel strength" for all h rows
int left, right, width;         //leftmost and rightmost dark pixels in row
bool dark = false;              //tracking variable

for (int y = 0; y < h; y++)
{
    //initialize values at beginning of loop iteration
    left = 0;
    right = 0;
    width = 100;

    for (int x = 0; x < w; x++)
    {
        //use value of 128 as threshold between light and dark
        dark = bytes[x, y] < 128;  

        //increment bin if pixel is dark
        bins[y] += dark ? 1 : 0;    

        //update leftmost and rightmost dark pixels
        if (dark)
        {
            if (left == 0) left = x;    
            if (x > right) right = x;   
        }
    }

    width = right - left + 1;

    //for bins with few pixels, treat them as empty
    if (bins[y] < 10) bins[y] = 0;      

    //normalize value according to width
    //divide bin count by width (leftmost to rightmost)
    bins[y] /= width;

    //calculate the maximum bin value so that bins can be scaled when drawn
    if (bins[y] > max) max = bins[y];   
}

//calculated the smoothed value of each bin i by averaging bin i-1, i, and i+1
float[] smooth = new float[bins.Length];

smooth[0] = bins[0];
smooth[smooth.Length - 1] = bins[bins.Length - 1];

for (int i = 1; i < bins.Length - 1; i++)
{
    smooth[i] = (bins[i - 1] + bins[i] + bins[i + 1])/3;
}

//create a new bitmap based on the original bitmap, then draw bins on top
Bitmap bmp = new Bitmap(originalBitmap);

using (Graphics gr = Graphics.FromImage(bmp))
{
    for (int y = 0; y < bins.Length; y++)
    {
        //scale each bin so that it is drawn 200 pixels wide from the left edge
        float value = 200 * (float)smooth[y] / max;
        gr.DrawLine(Pens.Red, new PointF(0, y), new PointF(value, y)); 
    }
}

pictureBox1.Image = bmp;

13
2018-01-16 03:07



Setelah mengotak-atik ini untuk sementara waktu saya menemukan bahwa saya hanya perlu menghitung jumlah penyeberangan untuk setiap baris, yaitu, beralih dari putih menjadi hitam akan dihitung sebagai satu, dan sebuah saklar dari hitam menjadi putih akan bertambah satu lagi. Dengan menyorot setiap baris dengan hitungan> 66 saya mendekati 100% akurasi, kecuali untuk baris paling bawah.

Tentu saja, tidak akan kuat untuk dokumen yang dipindai sedikit diputar. Dan ada kerugian ini karena perlu menentukan ambang batas yang benar.


6
2017-11-07 01:59



IMHO dengan gambar yang ditampilkan akan sangat sulit untuk dilakukan 100% dengan sempurna.   Jawaban saya adalah memberi Anda ide alternatif.

Ide 1: Buatlah versi ReCaptcha Anda sendiri (untuk diletakkan di situs pron Anda sendiri) - dan buatlah permainan yang menyenangkan .. "Seperti memotong sebuah kata (ujung-ujungnya semua harus ruang putih - dengan beberapa toleransi untuk karakter yang tumpang tindih di atas dan di bawah garis ). "

Ide 2:  Ini adalah permainan yang kami mainkan sebagai anak-anak, kawat gantungan baju semuanya dibengkokkan ke dalam gelombang dan terhubung ke bel dan Anda harus menavigasi tongkat dengan cincin pada akhirnya dengan kawat melalui itu, di satu sisi ke sisi yang lain. tanpa membuat bel berbunyi. Mungkin Anda bisa menyesuaikan ide ini dan membuat gim ponsel di mana orang menelusuri garis tanpa menyentuh teks hitam (dengan toleransi untuk karakter yang tumpang tindih) ... ketika mereka dapat melakukan garis, mereka mendapatkan poin dan mencapai level baru di mana Anda memberi mereka lebih keras gambar ..

Ide 3: Cari tahu cara google / recaptcha mengitarinya

Ide 4: Dapatkan SDK untuk photoshop dan kuasai fungsi alat Extract Edge

Ide 5: Regangkan tumpukan gambar di Y Axis yang seharusnya membantu, menerapkan algoritme, lalu kurangi pengukuran lokasi dan terapkan pada gambar berukuran normal.


2
2017-11-05 04:21