是否有一种有效的手写文本分割算法？

Question

我想通过线条(以及将来的文字)自动划分古代手写文字的图像.

第一个明显的部分是预处理图像......

我只是使用简单的数字化(基于像素的亮度).之后我将数据存储到二维数组中.

下一个显而易见的部分是分析二进制数组.

1. 我的第一个算法很简单 - 如果数组的一行中的黑色像素多于最大值和最小值的均方根,则该行是行的一部分.

   在形成线条列表后,我切断了高度低于平均值的线条.最后它变成了某种线性回归,试图最小化空行和文本行之间的差异.(我以为这个事实)

2. 我的第二次尝试 - 我尝试使用GA和几个健身功能.染色体包含3个值 - xo,x1,x2.xo [-1; 0] x1 [0; 0.5] x2 [0; 0.5]

确定行到行的同一性的函数是(xo +α1x1+α2x2)> 0,其中α1是行中黑色像素的缩放和,α2是行中极端黑色像素之间的范围的中值.(a1,a2 [0,1])我试过的另一个函数是(x1 <α1或x2>α2)和(1/xo + [a1 x1]/[a2 x2])> 0 最后一个函数是最多的高效. 适应度函数是 (1 /(HeigthRange + SpacesRange))

范围是最大值和最小值之间的差异.它代表了文本的同质性.此功能的全局最佳 - 将图像划分为线条的最平滑方式.

我使用C#和我的自编码GA(经典,2点交叉,灰色代码染色体,最大群体为40,突变率为0.05)

现在我没有想法如何将这个图像分成几行,精度达到100%.

这样做的有效算法是什么？

---

更新: 原始图像 原始BMP(1.3 MB)

---

更新2: 将此文本的结果改进为100%

我是怎么做到的:

• 修复范围计数中的小错误
• 将健身功能改为1 /(distanceRange + 1)*(heightsRange + 1))
• 将分类函数最小化为(1/xo + x2 /范围)> 0(行中的点现在不影响分类)(即优化的输入数据并使适应度函数优化更明确)

问题:

GA令人惊讶地未能认识到这一点.我看了'find rages'函数的调试数据,发现在'无法识别'的地方有太多的噪音.功能代码如下:

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

我在这段代码中使用了一些黑客.主要原因 - 我想最小化最近的黑色像素之间的范围,但如果没有像素,则该值变为"0",并且找不到optima就不可能解决这个问题.第二个原因 - 这段代码变化太频繁了.我将尝试完全更改此代码,但我不知道该怎么做.

问:

1. 如果有更有效的健身功能？
2. 如何找到更多功能的测定功能？

Answer 1

虽然我不确定如何将以下算法转换为GA(并且我不确定为什么你需要使用GA来解决这个问题),而且我可能会在提出它的基础上做出决定.

我建议的简单技术是计算每行的黑色像素数.(实际上它是每行的暗像素密度.)这需要很少的操作,并且通过一些额外的计算,在像素和直方图中找到峰值并不困难.

原始直方图看起来像这样,左侧的轮廓显示一行中的暗像素数.为了可见性,将实际计数标准化为伸展到x = 200.

在添加了一些额外的简单处理(如下所述)之后,我们可以生成这样的直方图,可以将其剪切到某个阈值.剩下的是指示文本行中心的峰.

从那里找到线条是一件简单的事情:只需将直方图剪切(阈值)到某个值,例如1/2或最大值的2/3,并可选择检查剪切阈值处的峰值宽度是否为某个最小值W上.

完整(但仍然简单!)算法的一个实现,以找到更好的直方图如下:

1. 在对边缘附近的像素进行操作的标准Otsu阈值不令人满意的情况下,使用"移动平均"阈值或类似的局部阈值技术对图像进行二值化.或者,如果你有一个漂亮的黑白图像,只需使用128作为二值化阈值.
2. 创建一个数组来存储直方图.此数组的长度将是图像的高度.
3. 对于二值化图像中的每个像素(x,y),找到某个半径R上方和下方(x,y)的暗像素数.也就是说,计算从(x,y - R)到(x,y - R)的暗像素数x(y + R),包括端值.
4. 如果垂直半径R内的暗像素的数量等于或大于R - 即,至少一半的像素是暗的 - 那么像素(x,y)具有足够的垂直暗邻居.增加行y的bin计数.
5. 当您沿着每一行行进时,跟踪具有足够邻居的像素的最左侧和最右侧x值.只要宽度(右 - 左+ 1)超过某个最小值,就将暗像素的总数除以此宽度.这会对计数进行标准化,以确保包含最后一行文本等短行.
6. (可选)平滑生成的直方图.我刚用了超过3行的平均值.

"垂直计数"(步骤3)消除了恰好位于文本中心线上方或下方的水平笔划.更复杂的算法只能直接检查上方和下方(x,y),但也可以检查左上角,右上角,左下角和右下角.

通过我在C#中相当粗略的实现,我能够在不到75毫秒的时间内处理图像.在C++中,通过一些基本的优化,我毫不怀疑时间可以大大减少.

此直方图方法假定文本是水平的.由于算法相当快,您可能有足够的时间以与水平方向每5度的增量计算像素数直方图.具有最大峰/谷差异的扫描方向将指示旋转.

我不熟悉GA术语,但如果我所建议的有一些价值,我相信你可以把它翻译成GA术语.无论如何,我对这个问题感兴趣,所以我不妨分享一下.

编辑:也许是使用GA,最好用"从X中的前一个暗像素开始的距离"(或沿着角度θ)和"从Y中的前一个暗像素开始的距离"(或沿着角度[θ-pi/2])来考虑).您还可以检查所有径向方向上从白色像素到暗像素的距离(以查找循环).

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;

Answer 2

在摆弄了一段时间之后,我发现我只需要计算每条线的交叉数,也就是说,从白色到黑色的切换将计为一个,而从黑色到白色的切换将再次增加一个.通过突出显示计数> 66的每一行,我得到接近100%的准确度,除了最底线.

当然,稍微旋转的扫描文档也不会很健壮.并且存在需要确定正确阈值的缺点.