Logo Search packages:      
Sourcecode: ocrad version File versions  Download package

bitmap_layout.cc

/*  GNU Ocrad - Optical Character Recognition program
    Copyright (C) 2003, 2004, 2005 Antonio Diaz Diaz.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/

#include <algorithm>
#include <cstdio>
#include <vector>

#include "common.h"
#include "rational.h"
#include "rectangle.h"
#include "track.h"
#include "bitmap.h"


namespace {

void find_rows( const std::vector< std::vector< char > > & data,
                const Rectangle & rdata, const Rectangle & rin,
                std::vector< Rectangle > & rvout, bool recursive ) throw();

void find_columns( const std::vector< std::vector< char > > & data,
                   const Rectangle & rdata, const Rectangle & rin,
                   std::vector< Rectangle > & rvout, bool recursive ) throw()
  {
  if( !rdata.includes( rin ) ) return;
  const int colmin = ( rdata.width() > 100 ) ? rdata.width() / 10 : 10;
  const int gapmin = ( rdata.width() > 300 ) ? rdata.width() / 100 : 3;
  const int min_width = ( 2 * colmin ) + gapmin;
  if( rin.width() < min_width ) { rvout.push_back( rin ); return; }
  const unsigned int rvout_size_orig = rvout.size();
  const int ldiff = rin.left()-rdata.left();
  const int tdiff = rin.top()-rdata.top();
  std::vector< int > h_outline( rin.width(), 0 );

  for( int row = 0; row < rin.height(); ++row )
    {
    const std::vector< char > & datarow = data[row+tdiff];
    for( int col = 0; col < rin.width(); ++col )
      if( datarow[col+ldiff] ) ++h_outline[col];
    }
  int total_dots = 0;
  for( int col = 0; col < rin.width(); ++col ) total_dots += h_outline[col];
  if( 10 * total_dots > 8 * rin.size() ) return;      // eliminates images

  const int threshold_col = std::max( total_dots / ( rin.width() * 4 ), 10 );
  const int threshold_gap = std::max( total_dots / ( rin.width() * 20 ), 1 );
  int left = 0, right = rin.width() - 1;

  while( left < right && h_outline[left] <= 0 ) ++left;     // cut left border
  if( rin.left() == rdata.left() && 10 * left < right )     // cut left border noise
    {
    int l = left + gapmin;
    while( l < right && h_outline[l] <= 0 ) ++l;
    if( l > left + ( 2 * gapmin ) ) left = l;
    }
  left = std::max( 0, left - gapmin );

  while( right > left && h_outline[right] <= 0 ) --right; // cut right border
  right = std::min( right + gapmin, rin.width() - 1 );

  while( right - left >= 2 * colmin )
    {
    int l, r;
    for( l = r = left; r < right; ++r )               // look for text
      if( h_outline[r] < threshold_col )
        { if( r - l >= colmin ) break; else l = r; }
    if( r - l < colmin ) break;

    for( l = r; r < right; ++r )                // look for gap
      if( h_outline[r] > threshold_gap )
        { if( r - l >= gapmin ) break; else l = r; }
    if( r - l < gapmin ) break;

    if( r < right )                 // cut by a minimum near the center
      {
      int mid = ( r + l ) / 2, half = ( r - l ) / 2;
      r = mid;
      for( int i = 1; i <= half && h_outline[r] > 0; ++i )
        {
        if( h_outline[mid+i] < h_outline[r] ) r = mid + i;
        if( h_outline[mid-i] < h_outline[r] ) r = mid - i;
        }
      }
    Rectangle re( rin.left() + left, rin.top(), rin.left() + r, rin.bottom() );
    if( recursive ) find_rows( data, rdata, re, rvout, re.width() >= min_width );
    else rvout.push_back( re );
    left = r;
    }
  if( right - left > gapmin )
    {
    Rectangle re( rin.left() + left, rin.top(), rin.left() + right, rin.bottom() );
    if( recursive && ( rvout.size() > rvout_size_orig || rvout.size() == 0 ) )
      find_rows( data, rdata, re, rvout, re.width() >= min_width );
    else rvout.push_back( re );
    }
  }


void find_rows( const std::vector< std::vector< char > > & data,
                const Rectangle & rdata, const Rectangle & rin,
                std::vector< Rectangle > & rvout, bool recursive ) throw()
  {
  if( !rdata.includes( rin ) ) return;
  const int rowmin = ( rdata.height() > 100 ) ? rdata.height() / 10 : 10;
  const int gapmin = ( rdata.height() > 300 ) ? rdata.height() / 100 : 3;
  const int min_height = ( 2 * rowmin ) + gapmin;
  if( rin.height() < min_height ) { rvout.push_back( rin ); return; }
  const unsigned int rvout_size_orig = rvout.size();
  const int ldiff = rin.left()-rdata.left();
  const int tdiff = rin.top()-rdata.top();
  std::vector< int > v_outline( rin.height(), 0 );

  int total_dots = 0;
  for( int row = 0; row < rin.height(); ++row )
    {
    const std::vector< char > & datarow = data[row+tdiff];
    for( int col = 0; col < rin.width(); ++col )
      if( datarow[col+ldiff] ) ++v_outline[row];
    total_dots += v_outline[row];
    }
  if( 10 * total_dots > 8 * rin.size() ) return;      // eliminates images

  const int threshold_gap = ( total_dots / ( rin.height() * 20 ) ) + 1;
  int top = 0, bottom = rin.height() - 1;

  while( top < bottom && v_outline[top] <= 0 ) ++top; // cut top border
  top = std::max( 0, top - gapmin );
  while( bottom > top && v_outline[bottom] <= 0 ) --bottom; // cut bottom border
  bottom = std::min( bottom + gapmin, rin.height() - 1 );

  while( bottom - top >= min_height )
    {
    int t, b;                             // top and bottom of gap
    for( t = b = top + gapmin; t < bottom - gapmin; ++t )
      if( v_outline[t] < threshold_gap )
        {
        for( b = t + 1; b < bottom && v_outline[b] < threshold_gap; ++b );
        if( b - t >= gapmin ) break; else t = b;
        }
    if( b - t < gapmin ) break;

    if( b < bottom )                // cut by a minimum near the center
      {
      int mid = ( b + t ) / 2, half = ( b - t ) / 2;
      b = mid;
      for( int i = 1; i <= half && v_outline[b] > 0; ++i )
        {
        if( v_outline[mid+i] < v_outline[b] ) b = mid + i;
        if( v_outline[mid-i] < v_outline[b] ) b = mid - i;
        }
      }
    Rectangle re( rin.left(), rin.top() + top, rin.right(), rin.top() + b );
    if( recursive ) find_columns( data, rdata, re, rvout, re.height() >= min_height && bottom - b > gapmin );
    else rvout.push_back( re );
    top = b;
    }
  if( bottom - top > gapmin )
    {
    Rectangle re( rin.left(), rin.top() + top, rin.right(), rin.top() + bottom );
    if( recursive && rvout.size() > rvout_size_orig )
      find_columns( data, rdata, re, rvout, re.height() >= min_height );
    else rvout.push_back( re );
    }
  }

} // end namespace


// Creates a reduced bitmap
//
Bitmap::Bitmap( const Bitmap & source, const int scale, const Rational & th ) throw()
  : Rectangle( source )
  {
  if( scale < 2 || scale > source.width() || scale > source.height() )
    Ocrad::internal_error( "bad parameter building a reduced Bitmap" );

  const int ith = ( th >= 0 && th <= 1 ) ?
                  ( th * ( scale * scale ) ).trunc() :
                  ( ( scale * scale ) - 1 ) / 2;
  Rectangle::height( source.height() / scale );
  Rectangle::width( source.width() / scale );

  data.resize( height() );
  for( int row = 0; row < height(); ++row )
    {
    const int srow = ( row * scale ) + scale;
    data[row].reserve( width() );
    std::vector< char > & datarow = data[row];
    for( int col = 0; col < width(); ++col )
      {
      const int scol = ( col * scale ) + scale;
      int counter = 0;
      for( int i = srow - scale; i < srow; ++i )
        {
        const std::vector< char > & sdatarow = source.data[i];
        for( int j = scol - scale; j < scol; ++j )
          if( sdatarow[j] && ++counter > ith ) goto L1;
        }
      L1: datarow.push_back( counter > ith );
      }
    }
  }


int Bitmap::analyse_layout( std::vector< Rectangle > & rv,
                            const int layout_level ) const throw()
  {
  rv.clear();

  if( layout_level >= 1 && layout_level <= 2 &&
      left() == 0 && top() == 0 && width() > 200 && height() > 200 )
    {
    Bitmap reduced( *this, 10, Rational( 9, 100 ) );
    find_columns( reduced.data, reduced, reduced, rv, layout_level >= 2 );
    for( unsigned int i = 0; i < rv.size(); ++i )
      rv[i].enlarge( 10 );
    }
  if( rv.size() == 0 ) rv.push_back( *this );
  return rv.size();
  }


void Bitmap::draw_rectangle( const Rectangle & re ) throw()
  {
  int l = std::max( left(), re.left() );
  int t = std::max( top(), re.top() );
  int r = std::min( right(), re.right() );
  int b = std::min( bottom(), re.bottom() );
  if( l == re.left() )
    for( int row = t; row <= b; ++row ) set_bit( row, l, true );
  if( t == re.top() )
    for( int col = l; col <= r; ++col ) set_bit( t, col, true );
  if( r == re.right() )
    for( int row = t; row <= b; ++row ) set_bit( row, r, true );
  if( b == re.bottom() )
    for( int col = l; col <= r; ++col ) set_bit( b, col, true );
  }


void Bitmap::draw_track( const Track & tr ) throw()
  {
  int l = std::max( left(), tr.left() );
  int r = std::min( right(), tr.right() );
  if( l == tr.left() )
    for( int row = tr.top( l ); row <= tr.bottom( l ); ++row )
      if( row >= top() && row <= bottom() ) set_bit( row, l, true );
  if( r == tr.right() )
    for( int row = tr.top( r ); row <= tr.bottom( r ); ++row )
      if( row >= top() && row <= bottom() ) set_bit( row, r, true );
  for( int col = l; col <= r; ++col )
    {
    int row = tr.top( col );
    if( row >= top() && row <= bottom() ) set_bit( row, col, true );
    row = tr.bottom( col );
    if( row >= top() && row <= bottom() ) set_bit( row, col, true );
    }
  }


void Bitmap::histogramize( const bool vertical ) throw()
  {
  if( vertical )
    {
    for( int col = left(); col <= right(); ++col )
      for( int row = top(), y = bottom(); row <= bottom(); ++row )
        if( get_bit( row, col ) )
          { set_bit( row, col, false ); set_bit( y--, col, true ); }
    }
  else
    {
    for( int row = top(); row <= bottom(); ++row )
      for( int col = left(), x = left(); col <= right(); ++col )
        if( get_bit( row, col ) )
          { set_bit( row, col, false ); set_bit( row, x++, true ); }
    }
  }

Generated by  Doxygen 1.6.0   Back to index