29.02.2016 06:41
Beetle_ru 4 5900 Источник


Есть мнение, что система электронного документооборота полностью избавляет от работы с бумагами, но это не так. Для оцифровки бумажных экземпляров документов их обычно пропускают через сканер. Когда поток документов и требования к качеству сканов превышают некоторый порог возникает ряд вопросов, которые необходимо решать программно.

Какие проблемы приходится решать:
  • Корректировать угол наклона изображения, т.к. фидер сканера неизбежно наклоняет документ при протяжке. Неряшливость в важных документах недопустима.
  • Выделять полезную часть на скане, остальное — удалять, так как это не информативно и занимает дисковое пространство впустую.
  • Находить и удалять пустые страницы, которые обязательно будут при дуплекс-сканировании.


Алгоритмы, решающие поставленные задачи разработаны и вероятно даже выложены в интернетах, но найти их внятное описание не удалось. Конечно, эти проблемы решают дорогие профессиональные сканеры, но использовать встроенное ПО не всегда возможно.
Идея статьи родилась как раз в процессе разработки инструмента для решения этих проблем. Надеюсь, она дополнит доступную информацию по оцифровке документов и окажется полезной разработчикам, которые занимаются схожей задачей.

Рассмотрим три скана документов, которые мы получили при помощи старого-доброго сканера Futjitsu fi-6140.
  1. Скан бланка анкеты на получение карты Тинькофф банка;
  2. Скан ксерокопии паспорта;
  3. Скан почтового конверта.




Коррекция наклона


После получения скана документа, нужно привести его к строго вертикальному или горизонтальному виду. Подразумевается, что на вход могут быть поданы произвольные документы без каких-либо меток, по которым можно скорректировать наклон. Поэтому привяжемся к горизонтальным и вертикальным составляющим документа: строки, линии таблиц, штрих-коды и даже места сгиба.
Первым делом устраняем избыточность изображения, т.е. выделяем контур. Для этого применяем детектор границ.
Мы выбрали детектор границ Канни —поскольку он дает наиболее качественный результат.



Тепреь на изображении следует найти прямые линии. Для этого применяем популярное решение используемое в компьютерном зрении — преобразование Хафа. Я не буду подробно расписывать его принцип, его можно найти в интернете. Суть преобразования заключается в перереборе всех возможных вариантов линий на изображении и вычисления для них отклика. Чем больше отклик, тем выраженнее линия. В результате преобразования будет построена фазовая плоскость, где по Y взят угол наклона, по X — расстояние до линии.



На визуализации фазовой плоскости каждому пикселю соотвествует уникальная линия. Координаты будем вычислять по наиболее выраженным линиям.

Возьмем 5 наиболее интенсивных линий, для наглядности покажем их на контуре исходного изображения:



Видно, что уголы наклона линий соответсвуют наклону осей координат документа.

Чтобы получить угол на который нужно повернуть изображение вычисляем угол отклонения линий от глобальных осей координат(от 0 и 90 градусов), усредняем значение и получаем угол наклона изображения. Поворачиваем изображение на полученный угол со знаком минус. Теперь с этим изображением можно работать дальше.

! Угол наклона некоторых линий будет сильно отличаться от других, т.е. они далеко не параллельны. Такие линии лучше исключить из вычислений, чтобы они не портили результат.



Для работы с графикой мы воспользовались замечательной библиотекой aforgenet. В ней уже есть реализация описанного выше алгоритма поиска угла наклона документа. В результате всего 15 строк кода и коррекция налона готова.

! Функция GetAverageBorderColor возвращает средний цвет периметра исходного изображения. Ее можно заменить константой или другой более продвинутой функцией.
public static Bitmap DocumentAngleCorrection(Bitmap image) {
  var grayImage = Grayscale.CommonAlgorithms.RMY.Apply(image);
  var skewChecker = new DocumentSkewChecker();

  var angle = skewChecker.GetSkewAngle(grayImage);

  while (angle >= 90) {
    angle -= 90;
  }

  while (angle <= -90) {
    angle += 90;
  }

  var rotator = new RotateBilinear(-angle, false);
  rotator.FillColor = GetAverageBorderColor(image);
  image = rotator.Apply(image);

  return image;
}


Кадрирование


Мы выровнили изображение. Теперь нужно кадрировать его информативную часть. На этом этапе важно учесть некоторые особенности.

Алгоритм должен исправно работать:
  • при любом цвете текста и фона;
  • со сканами любого качества;
  • с документами любого типа.

За основу алгоритма мы взяли предположение: в информативной области изображения будет много перепадов яркости, в пустой — мало. Поэтому решение задачи сводится к трем действиям:
  1. Разбиваем изображения на фрагменты, подсчитываем количество перепадов яркости по вертикали и горизонтали для каждого фрагмента.
  2. Ищем фрагменты с большим количеством перепадов яркости.
  3. Вырезаем информативную область.

Для быстрого доступа к пикселям изображения, лучше работать с массивом байтов. Его можно получить так:
var bitmapData = sourceBitmap.LockBits(new Rectangle(0, 0, sourceBitmap.Width, sourceBitmap.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

var bytes = bitmapData.Stride * sourceBitmap.Height;
var sourceBytes = new byte[bytes];

System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

Алгоритм выглядит так: 
const int sensitivity = 25;
const int widthQuantum = 100;

var regionSize = bitmapData.Width / widthQuantum;


for (var y = 0; y < bitmapData.Height + regionSize; y += regionSize) { // x processing
  for (var x = 0; x < bitmapData.Width + regionSize; x += regionSize) { // y processing
    var value = 0;

    for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) { // Horosontal counting
      var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, x, yy);

      for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) {
        var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

        if (Math.Abs(pixel - nextPixel) > sensitivity) {
          value++;
        }

        pixel = nextPixel;
      }
    }

    for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) { // Vertical counting
      var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, y);

      for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) {
        var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

        if (Math.Abs(pixel - nextPixel) > sensitivity) {
          value++;
        }

        pixel = nextPixel;
      }
    }

    // value TODO
  }
}


Переменная value в обозначенном месте будет содержать количество перепадов яркости по вертикали и горизонтали в обрабатываемом фрагменте. Это значение и координаты фрагмента можно, например сохранить в список.

! Функция GetGrayPixel возвращает среднее значение интенсивности пикселя.
private static byte GetGrayPixel(byte[] src, int w, int x, int y) {
  var s = GetShift(w, x, y);

  if ((s + 3 > src.Length) || (s < 0)) {
    return 127;
  }

  int b = src[s++];
  b += src[s++];
  b += src[s];
  b = (int)(b / 3.0);
  return (byte)b;
}


После применения алгоритма получили карту перепадов яркости изображения. На которой выделяем область включающую наибольшие перепады.



! Для экономии ресурсов лучше работать с уменьшенной копией изображения. Потом масштабировать результат и применять к исходной картинке.



Смотрим результат. Алгоритм сработал корректно — не оставил и не срезал ничего лишнего.



Такой результат мы получили в большинстве случаев.

Удаление пустых страниц


Получилось так, что задача удаления пустых страниц документов появилась уже после того, как мы разработали алгоритм выделения информативной части документа. Поэтому для удаления пустых страниц мы использовали тот же алгоритм, только немного видоизменили его. Вместо построения карты перепадов яркости изображения, мы подсчитывали количество фрагментов с большим и малым перепадом яркости. Если высокочастотных блоков много, изображение содержит ценную информацию и не является пустым.
Казалось бы чтобы сократить время обработки можно удалять лишние страницы и кадрировать изображение в один подход, т.е. один проходить циклом только один раз. Но очевидно, что кадрировать изображение можно только после выравнивания. При этом пришлось бы так же поворачивать карту перепадов. Поэтому, чтобы не усложнять себе жизнь, мы определили такой порядок действий:
удаление пустых страниц --> коррекция наклона --> кадрирование
Мы получили один лишний проход по пикселям для подсчета частоты. Но это не является проблемой в наше время благодаря закону Гордона Мура.

! Полный сырок
public static Bitmap DocumentAngleCorrection(Bitmap image) {
  var grayImage = Grayscale.CommonAlgorithms.RMY.Apply(image);
  var skewChecker = new DocumentSkewChecker();

  var angle = skewChecker.GetSkewAngle(grayImage);

  while (angle >= 90) {
    angle -= 90;
  }

  while (angle <= -90) {
    angle += 90;
  }

  var rotator = new RotateBilinear(-angle, false);
  rotator.FillColor = GetAverageBorderColor(image);
  image = rotator.Apply(image);

  return image;
}

private static Color GetAverageBorderColor(Bitmap bitmap) {
  var widthProcImage = (double)200;

  var sourceImage = bitmap;
  var sizeFactor = widthProcImage / sourceImage.Width;
  var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
  var bitmapData = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

  var bytes = Math.Abs(bitmapData.Stride) * procBtmp.Height;
  var sourceBytes = new byte[bytes];
  System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

  var channels = new Dictionary<char, int>();
  channels.Add('r', 0);
  channels.Add('g', 0);
  channels.Add('b', 0);

  var cnt = 0;

  for (var y = 0; y < bitmapData.Height; y++) { // vertical
    var c = GetColorPixel(sourceBytes, bitmapData.Width, 0, y);
    channels['r'] += c.R;
    channels['g'] += c.G;
    channels['b'] += c.B;
    cnt++;

    c = GetColorPixel(sourceBytes, bitmapData.Width, bitmapData.Width - 1, y);
    channels['r'] += c.R;
    channels['g'] += c.G;
    channels['b'] += c.B;
    cnt++;
  }

  for (var x = 0; x < bitmapData.Width; x++) { // horisontal
    var c = GetColorPixel(sourceBytes, bitmapData.Width, x, 0);
    channels['r'] += c.R;
    channels['g'] += c.G;
    channels['b'] += c.B;
    cnt++;

    c = GetColorPixel(sourceBytes, bitmapData.Width, x, bitmapData.Height - 1);
    channels['r'] += c.R;
    channels['g'] += c.G;
    channels['b'] += c.B;
    cnt++;
  }

  procBtmp.UnlockBits(bitmapData);

  var r = (int)Math.Round(((double)channels['r']) / cnt);
  var g = (int)Math.Round(((double)channels['g']) / cnt);
  var b = (int)Math.Round(((double)channels['b']) / cnt);

  var color = Color.FromArgb(r > 255 ? 255 : r, g > 255 ? 255 : g, b > 255 ? 255 : b);

  return color;
}

private static byte GetGrayPixel(byte[] src, int w, int x, int y) {
  var s = GetShift(w, x, y);

  if ((s + 3 > src.Length) || (s < 0)) {
    return 127;
  }

  int b = src[s++];
  b += src[s++];
  b += src[s];
  b = (int)(b / 3.0);
  return (byte)b;
}

private static Color GetColorPixel(byte[] src, int w, int x, int y) {
  var s = GetShift(w, x, y);

  if ((s + 3 > src.Length) || (s < 0)) {
    return Color.Gray;
  }

  byte r = src[s++];
  byte b = src[s++];
  byte g = src[s];

  var c = Color.FromArgb(r, g, b);

  return c;
}
private static int GetShift(int width, int x, int y) {
  return y * width * 3 + x * 3;
}

public static bool DocumentDetectInfo(Bitmap image) {
  const double widthProcImage = 200;
  const int sens = 15;
  const int treshold = 25;
  const int widthQuantum = 10;


  var sourceImage = image;
  var sizeFactor = widthProcImage / sourceImage.Width;
  var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
  var bd = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
  var bytes = Math.Abs(bd.Stride) * procBtmp.Height;
  var source = new byte[bytes];

  System.Runtime.InteropServices.Marshal.Copy(bd.Scan0, source, 0, bytes);

  var maxV = 0;

  var size = bd.Width / widthQuantum;

  var hight = 0;
  var low = 0;

  for (var y = 0; y < bd.Height + size; y += size) { // x processing
    for (var x = 0; x < bd.Width + size; x += size) { // y processing
      var value = 0;

      for (var yy = y; (yy < y + size) && (yy < bd.Height); yy++) { // Horosontal counting
        var pixel = GetGrayPixel(source, bd.Width, x, yy);

        for (var xx = x; (xx < x + size) && (xx < bd.Width); xx++) {
          var point = GetGrayPixel(source, bd.Width, xx, yy);

          if (Math.Abs(pixel - point) > sens) {
            value++;
          }

          pixel = point;
        }
      }

      for (var xx = x; (xx < x + size) && (xx < bd.Width); xx++) { // Vertical counting
        var pixel = GetGrayPixel(source, bd.Width, xx, y);

        for (var yy = y; (yy < y + size) && (yy < bd.Height); yy++) {
          var point = GetGrayPixel(source, bd.Width, xx, yy);

          if (Math.Abs(pixel - point) > sens) {
            value++;
          }

          pixel = point;
        }
      }

      maxV = Math.Max(maxV, value);

      if (value > treshold) {
        hight++;
      } else {
        low++;
      }
    }
  }

  double cnt = hight + low;
  hight = (int)Math.Round(hight / cnt * 100);

  procBtmp.UnlockBits(bd);

  return (hight > treshold);
}

public static Bitmap DocumentCropInfo(Bitmap image) {
  const double widthProcImage = 1000;
  const int sensitivity = 25;
  const int treshold = 50;
  const int widthQuantum = 100;


  var sourceImage = image;
  var sizeFactor = widthProcImage / sourceImage.Width;
  var procBtmp = new Bitmap(sourceImage, (int)Math.Round(sourceImage.Width * sizeFactor), (int)Math.Round(sourceImage.Height * sizeFactor));
  var bitmapData = procBtmp.LockBits(new Rectangle(0, 0, procBtmp.Width, procBtmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
  var bytes = Math.Abs(bitmapData.Stride) * procBtmp.Height;
  var sourceBytes = new byte[bytes];

  System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, sourceBytes, 0, bytes);

  var x1 = procBtmp.Width;
  var y1 = procBtmp.Height;
  var x2 = 0;
  var y2 = 0;
  var maxV = 0;

  var pointList = new List<Point>();
  var regionSize = bitmapData.Width / widthQuantum;

  for (var y = 0; y < bitmapData.Height + regionSize; y += regionSize) { // x processing
    for (var x = 0; x < bitmapData.Width + regionSize; x += regionSize) { // y processing
      var value = 0;

      for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) { // Horosontal counting
        var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, x, yy);

        for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) {
          var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

          if (Math.Abs(pixel - nextPixel) > sensitivity) {
            value++;
          }

          pixel = nextPixel;
        }
      }

      for (var xx = x; (xx < x + regionSize) && (xx < bitmapData.Width); xx++) { // Vertical counting
        var pixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, y);

        for (var yy = y; (yy < y + regionSize) && (yy < bitmapData.Height); yy++) {
          var nextPixel = GetGrayPixel(sourceBytes, bitmapData.Width, xx, yy);

          if (Math.Abs(pixel - nextPixel) > sensitivity) {
            value++;
          }

          pixel = nextPixel;
        }
      }
      
      pointList.Add(new Point() { V = value, X = x, Y = y });
      maxV = Math.Max(maxV, value);
    }
  }

  var vFactor = 255.0 / maxV;

  foreach (var point in pointList) {
    var v = (byte)(point.V * vFactor);

    if (v > treshold) {
      x1 = Math.Min(x1, point.X);
      y1 = Math.Min(y1, point.Y);

      x2 = Math.Max(x2, point.X + regionSize);
      y2 = Math.Max(y2, point.Y + regionSize);
    }
  }

  procBtmp.UnlockBits(bitmapData);

  x1 = (int)Math.Round((x1 - regionSize) / sizeFactor);
  x2 = (int)Math.Round((x2 + regionSize) / sizeFactor);
  y1 = (int)Math.Round((y1 - regionSize) / sizeFactor);
  y2 = (int)Math.Round((y2 + regionSize) / sizeFactor);

  var bigRect = new Rectangle(x1, y1, x2 - x1, y2 - y1);
  var clippedImg = CropImage(sourceImage, bigRect);

  return clippedImg;
}
public static Bitmap CropImage(Bitmap source, Rectangle section) {
  section.X = Math.Max(0, section.X);
  section.Y = Math.Max(0, section.Y);
  section.Width = Math.Min(source.Width, section.Width);
  section.Height = Math.Min(source.Height, section.Height);

  var bmp = new Bitmap(section.Width, section.Height);

  var g = Graphics.FromImage(bmp);

  g.DrawImage(source, 0, 0, section, GraphicsUnit.Pixel);

  return bmp;
}

private class Point {
  public int X;
  public int Y;
  public int V;
}



Заключение


Алгоритмы отлично справляются со своей задачей и по сей день. Вполне вероятно, что это не самое эффективное решение. Поэтому приглашаем всех желающих в комментарии, чтобы обсудить другие возможные алгоритмы и подходы для решения конкретной задачи.

До скорых встреч!

Комментарии (4)


  1. KvanTTT
    29.02.2016 13:48
    #8787081

    Спасибо за статью. Когда-то тоже решал похожую задачу, правда для автоматического выравнивания горизонта.

    Есть одно вопрос: вот у вас есть функция GetGrayPixel, которая вычисляет результирующую интенсивность цвета как арифметическое среднее трех цветовых компонентов R, G, B. Не лучше ли использовать хотя бы такие формулы: 0.3R+0.6G+0.11B или 0.25R+ 0.5G+0.25B (т.к. разные компоненты по-разному влияют на то, как цвет в целом воспринимается. Изменения зеленого, например, больше чувствуются, чем изменения синего. Подробнее на SO и в вики). Хотя если и так все работает, то может и не надо трогать :)


    1. Beetle_ru
      29.02.2016 17:34
      #8787341

      Про разность восприятия цветов в курсе, но для данной задачи такие тонкости не к чему.
      А вот статью "Выравнивание горизонта" взял на заметку, спасибо.


  1. UksusoFF
    29.02.2016 23:22
    #8787649

    Очень странно что для ПК нет софта который все это дело автоматизирует. Хотя даже на Android есть CamScanner который вполне сносно даже фотки обрабатывает.


  1. Dywar
    29.02.2016 23:36
    #8787659

    Спасибо, классно.
    Point кандидат на структуру.