Оптимизированный OCR черный/белый пиксельный алгоритм

Вы можете создать дерево.

Выберите пиксель и разделите буквы на два сегмента в зависимости от того, является ли пиксель белым или черным. Затем выберите второй пиксель, разделите сегменты на два сегмента, каждое на основе этого пикселя, и так далее.

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

Создание дерева - это однократный этап предварительной обработки. Вам не придется делать это несколько раз.

Теперь, когда у вас есть соответствующий алфавит, проследуйте по дереву на основе установленных / не установленных пикселей и получите свою букву.

Почему бы просто не рассматривать изображение как 25-битное целое число? 32-битное int может работать. Например, букву «I» можно рассматривать как целое число 14815374 в десятичной системе, поскольку ее двоичное выражение равно 0111000100001000010001110. Вам будет удобно сравнивать два изображения с операцией «==» как два целых числа.

Один из способов - определить черный пиксель примерно в половине букв и белый в другом наборе. Затем это можно использовать для разделения букв на две группы, рекурсивно используя один и тот же алгоритм на обеих половинах, пока вы не дойдете до отдельных символов.

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

Чтобы найти пиксель, начните с массива целых чисел того же размера, что и ваши буквы, инициализируйте все элементы до 0, затем увеличивайте элементы, если соответствующий пиксель в букве (скажем) черный. Те, которые вас интересуют, находятся в диапазоне (примерно) 10≤sum≤16 (для верхнего уровня, нижние уровни должны будут использовать другие границы).

Вот что у меня есть. Это не протестировано, но, надеюсь, будет менее гениально для вас работать с.: -)

double
roundd(double n, short mode)
{
    short cw, newcw;

    __asm__("fstcw %w0" : "=m" (cw));
    newcw = cw & 0xf3ff | mode;
    __asm__("fldcw %w0" : : "m" (newcw));
    __asm__("frndint" : "+t" (n));
    __asm__("fldcw %w0" : : "m" (cw));
    return n;
}

Хотя, если вы не обязаны использовать сборку для достижения вашего режима округления, подумайте об использовании функций в < fenv.h > вместо этого.: -)

Если вы используете ветвь с именем heroku в качестве «альтернативной главной» ветви (с конфиденциальными данными) и старую главную ветвь без конфиденциальных данных, то вы всегда можете сделать

git merge master

Так что вы можете протолкнуть ветвь heroku в heroku, а не главную ветвь.

У меня нет алгоритма, чтобы дать вам ключевые функции, но вот некоторые вещи, которые могут помочь.

Во-первых, я бы не стал слишком беспокоиться о поиске характерного пикселя для каждого символа, потому что, в среднем, проверка соответствия данного символа заданному образу (5x5) двоичного изображения не должна занимать больше 5-7 проверок, чтобы сказать, что нет совпадения. Почему? Вероятность. Для 7 двоичных пикселей существует 2 * * 7 = 128 различных возможностей. Это означает, что вероятность совпадения символа до 7 пикселей составляет 1/128 < 1%. Просто убедитесь, что вы остановите сравнения, когда обнаружите несоответствие.

Во-вторых, если вы не хотите делать хэш-таблицу, вы можете использовать trie для хранения всех ваших символьных данных. Он будет использовать меньше памяти, и вы будете проверять все символы одновременно. Поиск не будет таким быстрым, как в хэш-таблице, но также не придется преобразовывать в последовательность. В каждом узле дерева может быть не более 2 потомков. Например, если у вас есть два символа 2x2 (назовем их A и B):

A   B
01  00
10  11

У вас будет только один потомок в первом узле - только слева (ветвь 0). Переходим к следующему узлу. Он имеет два потомка, левая (0) ветвь ведёт к остальной части B, а правая (1) ветвь ведёт к остальной части A. Вы получаете картину. Дайте мне знать, если эта часть не ясна.

Хорошо, я нашел решение.

Вы просто используете поиск в глубину для каждого пикселя с каждой другой комбинацией пикселей, пока не найдете набор уникальных характеристик буквы.При выполнении поиска в глубину убедитесь, что вы не начинаете каждый раз с x = 0 и y = 0, поскольку вы хотите обрабатывать каждую комбинацию только один раз, поэтому в конечном итоге вы увеличиваете значения x и y в каждом итерация.

Я создал вспомогательный объект, который содержит следующие свойства:

public Point LastPoint { get; set; }
public List<OcrChar> CharsWithSimilarProperties { get; set; }
public List<Point> BlackPixels { get; set; }
public List<Point> WhitePixels { get; set; }

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

Некоторый псевдо-код:

rootNode.LastPoint = new Point(-1, -1)
rootNode.CharsWithSimilarProperties = all letters in alphabet except for this one
queue.Add(rootNode)

while queue.HasNodes()
  for each pixel after node.LastPoint
    if node.IsBlackPixel(pixel) && node.CharsWithSimilarProperties.IsAlwaysWhite(pixel)
      node.BlackPixels.Add(pixel)
      return node.BlackPixels and node.WhitePixels

    if node.IsWhitePixel(pixel) && node.CharsWithSimilarProperties.IsAlwaysBlack(pixel)
      node.WhitePixels.Add(pixel)
      return node.BlackPixels and node.WhitePixels

    newNode = new Node();
    newNode.BlackPixels = node.BlackPixels.Copy();
    newNode.WhitePixels = node.WhitePixels.Copy();
    newNode.LastPoint = pixel
    if node.IsBlackPixel(pixel)
      newNode.BlackPixels.Add(pixel)
      newNode.CharsWithSimilarProperties = list of chars from node.CharsWithSimilarProperties that also had this pixel as black
    else
      newNode.WhitePixels.Add(pixel)
      newNode.CharsWithSimilarProperties = list of chars from node.CharsWithSimilarProperties that also had this pixel as white
    queue.Add(newNode)

Чтобы определить, является ли «node.CharsWithSimilarProperites.IsAlwaysWhite ()» или «IsAlwaysBlack ()», вы можете сгенерировать композитную карту в каждой итерации очереди:

  for each pixel after node.LastPoint
    for each char in node.CharsWithSimilarProperties
      if char.IsBlackPixel(pixel)
        compositeMap[pixel].Add(char)

Прежде чем делать все это, я также обработал весь алфавит, чтобы найти пиксели, которые всегда белые или всегда черные, поскольку их нельзя использовать. Я добавил их в список List ignoredPixels , и каждый раз, когда я перебираю пиксели, я всегда использую if (ignoredPixels [x, y]) continue; .

Это работает отлично и очень быстро. Хотя имейте в виду, что эта часть моего решения совсем не обязательно должна быть быстрой, поскольку это разовая оптимизация, которая поможет мне в дальнейшем. В моих тестовых случаях максимум 8 символов в наборе «алфавит» обычно дает одну или две характеристики для каждого символа. Мне еще предстоит запустить его для полного набора из 26 символов.

Я иду по похожему пути, пытаясь изобрести алгоритм, который даст мне минимальное количество тестов, которые я могу использовать для сопоставления изображения с тем, которое я видел ранее. Моя задача - OCR, но в ограниченной области - распознать изображение из фиксированного набора изображений как можно быстрее.

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

Если мы не можем найти один такой пиксель, тогда мы (нехотя) ищем два пикселя, которые в комбинации являются уникальными. Или три. И так далее, пока у нас не будет минимального теста для каждого из изображений.

Я должен отметить, что у меня есть сильное чувство, что в моей конкретной области я смогу найти такие уникальные пиксели. Это может быть не так для вашего приложения, где у вас, похоже, много "перекрытий".

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

Вот что у меня получилось на данный момент. Метод, который я описываю ниже, написан абстрактно, но в моем приложении каждый "тест" - это пиксель, идентифицированный точкой плюс цвет, а "результат" представляет собой идентификацию изображения. Идентификация этих изображений является моей конечной целью.

Рассмотрим следующие тесты, пронумерованные от T1 до T4.

• T1: A B C
• T2: B
• T3: A C D
• T4: A D

Этот список тестов можно интерпретировать следующим образом;

• Если тест T1 истинен, мы заключаем, что имеем результат A или B или C.
• Если тест T2 истинен, мы заключаем, что имеем результат B.
• Если тест T3 истинен, мы заключаем, что имеем результат A или C или D.
• Если тест T4 истинен, мы заключаем, что имеем результат A или D.

Для каждого отдельного результата A, B, C, D мы хотим найти комбинацию тестов (в идеале всего один тест), которая позволит нам проверить однозначный результат.

Применив интуицию и немного прищурившись на экран, мы можем с трудом найти следующую комбинацию тестов.

Для A мы можем проверить комбинацию T4 (либо A, либо D) и T1 (A, но не D)

B - легко, поскольку существует тест T2, который дает результат B и ничего больше.

C немного сложнее, но в итоге мы видим, что комбинация T3 (A или C или D) и NOT T4 (не A и не D) дает желаемый результат.

И аналогично, D можно найти с помощью комбинации T4 и (не T1).

Итого

A <- T4 && T1
B <- T2
C <- T3 && ¬T4
D <- T4 && ¬T1

(где <- следует читать как "может быть найдено, если следующие тесты оцениваются как true")

Интуиция и прищуривание - это хорошо, но мы, вероятно, не получим эти техники встроенными в язык по крайней мере до C# 5.0, так что вот попытка формализации метода для реализации в менее распространенных языках.

Чтобы найти результат R,

1. Найдите тест Tr, который дает желаемый результат R и как можно меньше нежелательных результатов (в идеале никаких других)
2. Если тест дает результат R и ничего больше, то мы закончили. Мы можем подобрать R, где Tr истинно.
3. Для каждого нежелательного результата X в тесте Tr;
   • (a) Найдите кратчайший тест Tn, который дает R, но не X. Если мы найдем такой тест, то сможем найти R, где (T && Tn)
   • (b) Если ни один тест не соответствует условию (a), то найдите самый короткий тест Tx, который включает X, но не включает R. (Такая проверка исключит X как результат проверки Tr). Затем мы можем проверить R, где (T && ¬Tx)

Теперь я попытаюсь следовать этим правилам для каждого из желаемых результатов, A, B, C, D.

Вот тесты еще раз для справки;

• T1: A B C
• T2: B
• T3: A C D
• T4: A D

For A

Согласно правилу (1) мы начинаем с T4, так как это самый простой тест, который дает результат A. Но он также дает результат 'D', который является нежелательным результатом. Согласно правилу (3), мы можем использовать тест T1, поскольку он включает в себя 'A', но не включает 'D'.

Поэтому мы можем проверить A с помощью

A <- T4 && T1

Для B

Чтобы найти B, мы быстро находим тест T2, который является самым коротким тестом для B, и поскольку он дает только результат B, мы закончили.

B <- T2

Для C

Чтобы найти 'C', мы начинаем с T1 и T3. Поскольку результаты этих тестов одинаково коротки, мы произвольно выбираем T1 в качестве начальной точки.

Теперь, согласно (3a), нам нужно найти тест, который включает 'C', но не 'A'. Поскольку ни один тест не удовлетворяет этому условию, мы не можем использовать T1 в качестве первого теста. У T3 та же проблема.

Не найдя теста, удовлетворяющего условию (3a), мы теперь ищем тест, удовлетворяющий условию (3b). Мы ищем тест, который дает 'A', но не 'C'. Мы видим, что тест T4 удовлетворяет этому условию, поэтому мы можем проверить C с помощью

C <- T1 && ¬T4

Для D

Чтобы найти D, мы начнем с T4. T4 включает нежелательный результат A. Нет других тестов, которые дают результат D, но не A, поэтому мы ищем тест, который дает A, но не D. Тест T1 удовлетворяет этому условию, поэтому мы можем проверить D с помощью

D <= T4 && ¬T1

Эти результаты хороши, но я не думаю, что достаточно отладил этот алгоритм, чтобы быть уверенным на 100%. Я собираюсь подумать над ним еще немного и, возможно, составить несколько тестов, чтобы посмотреть, как он работает. К сожалению, алгоритм достаточно сложен, чтобы его тщательная реализация заняла более нескольких минут. Возможно, пройдут дни, прежде чем я приду к какому-либо дальнейшему выводу.

Обновление

Я обнаружил, что оптимально одновременно искать тесты, которые удовлетворяют (a) ИЛИ (b), а не искать (a), а затем (b). Если сначала искать (a), то можно получить длинный список тестов, а можно было бы получить более короткий список, допустив некоторые тесты (b).