Русский English Тэги View Sergey Zolotaryov's profile on LinkedIn Вход
Автоматическое выравнивание изображений
Постоянная ссылка 27-10-2010 anydoby java graphics

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

Я пользовался поначалу алгоритмом Хуфа, который хорошо описан в интернете и даёт в принципе неплохие результаты. Но - только на изображениях, состоящих целиком из текста. А у меня задача - выравнивать картинки с текстом и рисунками. (Я занимаюсь в свободное время сканированием и восстановлением советских книжек. И вот это самое преобразование настолько изумительно распознает линии и вычисляет угол наклона, что я решил найти, откуда ж ноги растут, и попробовать переписать это на Java. Исходники находятся тут. Код настолько запутанный и оптимизированный под С++, что перевод занял где-то дня 2. Вот, что из этого получилось:



public double doIt(BufferedImage image) {
    final double skewRadians;
    BufferedImage black = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_BYTE_BINARY);
    final Graphics2D g = black.createGraphics();
    g.drawImage(image, 0, 0, null);
    g.dispose();

    skewRadians = findSkew(black);
    System.out.println(-57.295779513082320876798154814105 * skewRadians);
    return skewRadians;
}

  static int getByteWidth(final int width) {
    return (width + 7) / 8;
  }

  static int next_pow2(final int n) {
    int retval = 1;
    while (retval < n) {
      retval <<= 1;
    }
    return retval;
  }

  static class BitUtils {
    static int[] bitcount_ = new int[256];
    static int[] invbits_ = new int[256];

    static {
      for (int i = 0; i < 256; i++) {
        int j = i, cnt = 0;
        do {
          cnt += j & 1;
        } while ((j >>= 1) != 0);
        int x = (i << 4) | (i >> 4);
        x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
        x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
        bitcount_[i] = cnt;
        invbits_[i] = x;
      }
    }
  }

  static double findSkew(final BufferedImage img) {
    final DataBuffer buffer = img.getRaster().getDataBuffer();
    final int byteWidth = getByteWidth(img.getWidth());
    final int padmask = 0xFF << ((img.getWidth() + 7) % 8);
    int elementIndex = 0;
    for (int row = 0; row < img.getHeight(); row++) {
      for (int col = 0; col < byteWidth; col++) {
        int elem = buffer.getElem(elementIndex);
        elem ^= 0xff;// invert colors
        elem = BitUtils.invbits_[elem]; // Change the bit order
        buffer.setElem(elementIndex, elem);
        elementIndex++;
      }
      final int lastElement = buffer.getElem(elementIndex - 1) & padmask;
      buffer.setElem(elementIndex - 1, lastElement); // Zero trailing bits
    }
    final int w2 = next_pow2(byteWidth);
    final int ssize = 2 * w2 - 1; // Size of sharpness table
    final int sharpness[] = new int[ssize];
    radon(img.getWidth(), img.getHeight(), buffer, 1, sharpness);
    radon(img.getWidth(), img.getHeight(), buffer, -1, sharpness);
    int i, imax = 0;
    int vmax = 0;
    double sum = 0.;
    for (i = 0; i < ssize; i++) {
      final int s = sharpness[i];
      if (s > vmax) {
        imax = i;
        vmax = s;
      }
      sum += s;
    }
    final int h = img.getHeight();
    if (vmax <= 3 * sum / h) { // Heuristics !!!
      return 0;
    }
    final double iskew = imax - w2 + 1;
    return Math.atan(iskew / (8 * w2));
  }

  static void radon(final int width, final int height, final DataBuffer buffer, final int sign,
      final int sharpness[]) {

    int[] p1_, p2_; // Stored columnwise

    final int w2 = next_pow2(getByteWidth(width));
    final int w = getByteWidth(width);
    final int h = height;

    final int s = h * w2;
    p1_ = new int[s];
    p2_ = new int[s];
    // Fill in the first table
    int row, column;
    int scanlinePosition = 0;
    for (row = 0; row < h; row++) {
      scanlinePosition = row * w;
      for (column = 0; column < w; column++) {
        if (sign > 0) {
          final int b = buffer.getElem(0, scanlinePosition + w - 1 - column);
          p1_[h * column + row] = BitUtils.bitcount_[b];
        } else {
          final int b = buffer.getElem(0, scanlinePosition + column);
          p1_[h * column + row] = BitUtils.bitcount_[b];
        }
      }
    }

    int[] x1 = p1_;
    int[] x2 = p2_;
    // Iterate
    int step = 1;
    for (;;) {
      int i;
      for (i = 0; i < w2; i += 2 * step) {
        int j;
        for (j = 0; j < step; j++) {
          // Columns-sources:
          final int s1 = h * (i + j);// x1 pointer
          final int s2 = h * (i + j + step); // x1 pointer

          // Columns-targets:
          final int t1 = h * (i + 2 * j); // x2 pointer
          final int t2 = h * (i + 2 * j + 1); // x2 pointer
          int m;
          for (m = 0; m < h; m++) {
            x2[t1 + m] = x1[s1 + m];
            x2[t2 + m] = x1[s1 + m];
            if (m + j < h) {
              x2[t1 + m] += x1[s2 + m + j];
            }
            if (m + j + 1 < h) {
              x2[t2 + m] += x1[s2 + m + j + 1];
            }
          }
        }
      }

      // Swap the tables:
      final int[] aux = x1;
      x1 = x2;
      x2 = aux;
      // Increase the step:
      step *= 2;
      if (step >= w2) {
        break;
      }
    }
    // Now, compute the sum of squared finite differences:
    for (column = 0; column < w2; column++) {
      int acc = 0;
      final int col = h * column;
      for (row = 0; row + 1 < h; row++) {
        final int diff = x1[col + row] - x1[col + row + 1];
        acc += diff * diff;
      }
      sharpness[w2 - 1 + sign * column] = acc;
    }
  }

Алгоритм работает чертовки быстро за счёт карты всех возможных вариантов битов в байте, то есть за одну итерацию просчитывается сразу 8 пикселей. Но как он работает и что происходит внутри, для меня загадка :) Главное, что работает.

Добавить комментарий

4
31-10-2010

Не верю своим глазам!!! Бывают же совпадения!!!

Два дня назад я закончил портировать этот же код на Java. И процесс, кстати, тоже занял пару дней. В основном, по причине тотального непонимания сути алгоритма. Попытка почитать теорию всё только окончательно запутала. Но вроде всё заработало как надо.

Сейчас вот думаю как решить вопрос с autocrop. Ищу какие есть уже наработки в сети - и вот нарвался на твой пост.

Если интересно - мне эта функциональность нужна в Djvu->PDF конвертере. http://pd4ml.com/djvu.htm

anydoby
31-10-2010

Привет.

С autocrop можно взять кусочек из ImageMagic - там есть trim опция, которая простенько вырезает область с наибольшей плотностью контента.

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

anydoby
31-10-2010

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

4
04-11-2010

> Кстати, а зачем DJVU в PDF конвертить? Первый формат же > ж лучше подходит для сканированных книг. В PDF доки > получаются больше и качество не очень - разрешение > уменьшается.

Всё это так, пока не возникает необходимость читать djvu документы на eink ридере. Даже в том редком случае, когда ридер понимает формат djvu, сразу выясняется, что 5-6 дюймов - это маловато для отсканированной книжной страницы, и деление её на две части не всегда решает проблему. Вот тогда начинается борьба за каждый полезный кусочек площади: отрезал немного полей -> немного укрупнил шрифт... Другая беда сканированных djvu - грязный светло-серый фон и блёклые тёмно-серые буквы на нём. В общем, простор для творчества имеется. Ну а PDF позволяет зафиксировать результаты этой "борьбы" в формате, поддерживаемом практически всеми.

> Я тоже думаю над autocrop, но у меня специфика другая - > я вырезаю сканы - там по краям бяки и остаточные линии > после очистки от фона. Когда напишу, выложу.

У меня постановка задачи идеентична: точно такие же необработанные грязные сканы, но только свёрстанные в djvu.

Я эту неделю в отпуске, вернусь - займусь вопросом плотнее (если не будет завалов по основной работе). Появятся какие идейки - поделюсь.

anydoby
04-11-2010

Кстати, если интересно, ещё одна проблема - блёклые цвета шрифта. Решил уже почти. Проблема в том, что хочется делать это автоматически, и нельзя просто определенный цвет (цвет шрифта) сделать чёрным, потому как он еще встречается в других местах - например, книга с цветными картинками, или фон у шрифта есть из картинки. Я делаю так - выбирается в книге страница, где есть и картинка, и текст. Потом выделаем область, где есть только текст. Определяем объекты, содержащиеся на странице. Тем объектам, которые в зоне текста, присваиваем лейбл "Текст", остальным "Image". Соединяем ближайщие друг к другу объекты в некие группы, например, по 3-4 и записываем связи и размеры объектов в массив признаков. Потом самоорганизующейся мапе даём их все - тренируем. В конце получается очень качественный распознаватель, что есть текст, а что нет. Попробовал на одной детской книге, результаты 100% угадывания на странице, по которой учились. Надо теперь для подкрепления попробовать на других страницах. Если все это получится, напишу еще статейку, как это делать. Единственная бяка, это что алгоритму надо сначала показать область с текстом - обучить. Но нигде в интернете ничего лучшего я не нашёл.

4
17-11-2010

Сделал я более-менее приемлемый алгоритм обрезания полей. Конечно, во многом он подогнан под мои тестовые документы и на универсальность не претендует. Но вот тестирую всё подряд - в основном запарывается только на обложках и обильно иллюстрированных страницах (не может распознать, где заканчивается грязь и начинается картинка или края картинки может принять за тень от переплёта). Думаю за недельку слеплю новую версию.

Твои наработки по отбеливанию страниц-зачернению букв мне очень интересны. Сейчас я просто заливаю белым или чёрным все пикселы, не попадающие в определённые границы. В результате - дырявые и драные по краям буквы.

anydoby
17-11-2010

Вот чего я нарыл по поводу autocrop.

Ребята предлагают неплохой метод. Имплементацию можно подсмотреть в ocropus.

Предыдущая статья Новое и улучшенное Следующая статья Легкое чтиво (поля Маркова)