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

Question

我想按行(以及将来的单词)自动划分古代手写文本的图像。

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

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

下一个明显的部分是分析二进制数组。

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

   在形成行列表后，我切断了高度低于平均水平的行。 最后它变成了某种线性回归，试图最小化空白行和文本行之间的差异。 (我假设了这个事实)

2. 我的第二次尝试 - 我尝试使用具有多个适应度函数的 GA。 染色体包含 3 个值 - xo、x1、x2。 xo [-1;0] x1 [0;0.5] x2 [0;0.5]

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

其中范围是最大值和最小值之间的差值。它代表了文本的同质性。该函数的全局最优——将图像分割成线的最平滑方式。

我正在使用 C# 和我的自编码 GA(经典，2 点交叉，格雷码染色体，最大种群为 40，变异率为 0.05)

现在我想不出如何以约 100% 的准确度将此图像分成几行。

执行此操作的有效算法是什么？

---

更新: Original BMP (1.3 MB)

---

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

我是怎么做到的:

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

问题:

GA 出人意料地未能识别这条线。我查看了“查找愤怒”功能的调试数据，发现“无法识别”的地方有太多噪音。 功能代码如下:

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”，并且无法通过寻找最优解来解决这个问题。第二个原因——这段代码变化太频繁了。 我将尝试完全更改此代码，但我不知道该怎么做。

问:

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)，包括在内。
4. 如果垂直半径 R 内的暗像素数等于或大于 R(即至少一半像素为暗像素)，则像素 (x,y) 具有足够的垂直暗相邻像素。增加第 y 行的 bin 计数。
5. 当您沿着每一行行进时，跟踪具有足够邻居的像素的最左边和最右边的 x 值。只要宽度(右 - 左 + 1)超过某个最小值，就将暗像素的总数除以该宽度。这会将计数标准化，以确保包含文本的最后一行等短行。
6. (可选)平滑生成的直方图。我只使用了超过 3 行的平均值。

“垂直计数”(第 3 步)消除了恰好位于文本中心线上方或下方的水平笔划。更复杂的算法会直接检查 (x,y) 的上方和下方，但也会检查左上、右上、左下和右下。

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

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

我不熟悉 GA 术语，但如果我的建议有一定值(value)，我相信您可以将其翻译成 GA 术语。无论如何，我对这个问题很感兴趣，所以我不妨分享一下。

编辑:也许对于使用 GA，最好考虑“自 X 中上一个暗像素以来的距离”(或沿角度 theta)和“自上一个 Y 中暗像素的距离”(或沿角度 [theta - 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;