title: Is there an efficient algorithm for segmentation of handwritten text?
body: <p>I want to automatically divide an image of ancient handwritten text by lines (and by words in future).</p>
  
  <h2>The first obvious part is preprocessing the image...</h2>
  
  <p>I'm just using a simple digitization (based on brightness of pixel). After that I store data into two-dimensional array.</p>
  
  <h2>The next obvious part is analyzing the binary array.</h2>
  
  <ol>
  <li><p>My first algorithm was pretty simple - if there are more black pixels in a row of the array than the root-mean-square of <em>Maximum</em> and <em>Minimum</em> value, then this row is part of line.</p>
  
  <p>After forming the list of lines I cut off lines with <em>height</em> that is less than average.
  Finally it turned out into some kind of linear regression, trying to minimize the difference between the blank rows and text rows. (I assumed that fact)
  <img src="https://i.stack.imgur.com/Nbmwp.png" alt="First results"></p></li>
  <li><p>My second attempt - I tried to use GA with several fitness functions. 
  The chromosome contained 3 values - <em>xo, x1, x2. xo [-1;0] x1 [0;0.5] x2 [0;0.5]</em></p></li>
  </ol>
  
  <p>Function, that determines identity the row to line is <strong>(xo +  α1 x1 +  α2 x2) > 0</strong>, where α1 is scaled sum of black pixels in row, α2 is median value of ranges between the extreme black pixels in row. (a1,a2 [0,1])
  Another functions, that I tried is <strong>(x1 &lt; α1 OR x2 >  α2)</strong> and <strong>(1/xo + [a1 x1] / [a2 x2] ) > 0</strong>
  The last function is the most efficient.
  <img src="https://i.stack.imgur.com/IJSeq.png" alt="Results with GA">
  The fitness function is 
  <strong>(1 / (HeigthRange + SpacesRange)</strong></p>
  
  <p>Where range is difference between maximum and minimum. It represents the homogeneity of text. The global optimum of this function - the most smooth way to divide the image into lines.</p>
  
  <p>I am using C# with my self-coded GA (classical, with 2-point crossover, gray-code chromosomes, maximum population is 40, mutation rate is 0.05)</p>
  
  <p>Now I ran out of ideas how to divide this image into lines with ~100% accuracy.</p>
  
  <p>What is the efficient algorithm to do this?</p>
  
  <hr>
  
  <p><strong>UPDATE:</strong>
  <a href="http://www.mediafire.com/?u7sflf2ib741acw" rel="nofollow noreferrer">Original BMP (1.3 MB)</a></p>
  
  <hr>
  
  <p><strong>UPDATE2:</strong>
  Improved results on this text to 100%
  <img src="https://i.stack.imgur.com/UR1fo.png" alt="Nev results"></p>
  
  <p><em>How I did it:</em></p>
  
  <ul>
  <li>fixed minor bug in range count</li>
  <li>changed fitness function to 1/(distancesRange+1)*(heightsRange+1))</li>
  <li>minimized classifying function to (1/xo + x2/range) > 0 (points in row now don't affect classification)
  (i.e. optimized input data and made fitness function optimizations more explicit)</li>
  </ul>
  
  <p>Problem:</p>
  
  <p><img src="https://i.stack.imgur.com/udyjX.png" alt="Problem"></p>
  
  <p>GA surprisingly failed to recognize this line. I looked at debug data of 'find rages' function and found, that there is too much noise in 'unrecognized' place.
  The function code is below:</p>
  
  <pre><code>public double[] Ranges()
  {
      var ranges = new double[_original.Height];
  
      for (int y = 0; y &lt; _original.Height; y++ )
      {
          ranges[y] = 0;
          var dx = new List&lt;int&gt;();
          int last = 0;
          int x = 0; 
  
          while (last == 0 &amp;&amp; x&lt;_original.Width)
          {
              if (_bit[x, y])
                  last = x;
              x++;
          }
  
          if (last == 0)
          {
              ranges[y] = 0;
              continue;
          }
  
          for (x = last; x&lt;_original.Width; x++)
          {
              if (!_bit[x, y]) continue; 
  
              if (last != x - 1)
              {
                  dx.Add((x-last)+1);
              }
              last = x;
          }
          if (dx.Count &gt; 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 &lt; ranges.Length; i++)
      {
          if (Math.Abs(ranges[i] - 0) &lt; 0.9)
              ranges[i] = maximum;
      }
      return ranges;
  }
  </code></pre>
  
  <p>I'm using some hacks in this code. The main reason - I want to minimize the range between nearest black pixels, but if there are no pixels, the value becomes '0', and it becomes impossible to solve this problem with finding optimas. The second reason - this code is changing too frequently.
  I'll try to fully change this code, but I have no idea how to do it.</p>
  
  <p><strong>Q:</strong></p>
  
  <ol>
  <li>If there is more efficient fitness function? </li>
  <li>How to find more versatile determination function?</li>
  </ol>