Распознавание символов методом наименьшего расстояния Левенштейна

в 10:52, , рубрики: java, Программирование, распознавание символов, расстояние Левенштейна

В последнее время задача распознавания символов в прикладных программах не представляет особой сложности — можно использовать множество готовых OCR-библиотек, многие из которых доведены почти до совершенства. Но все же иногда может возникнуть задача разработать свой алгоритм распознавания без использования сторонних «навороченных» OCR-библиотек.

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

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

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

Распознавание символов методом наименьшего расстояния Левенштейна - 1

Схема алгоритма выглядит следующим образом:

Распознавание символов методом наименьшего расстояния Левенштейна - 2

Так как мы заранее знаем где у нас находится символ, вырезать определенную область не составит труда. Для того чтобы убрать все «неровности» краев символа переводим изображение в монохромное (черно-белое).

Распознавание символов методом наименьшего расстояния Левенштейна - 3

short width = 45, height = 40, offsetTop = -10, offsetLeft = -70;
BufferedImage image = ImageIO.read(file);
BufferedImage symbol = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_BINARY);
Graphics2D g = symbol.createGraphics();
g.drawImage(image, offsetLeft, offsetTop, null);

Далее необходимо преобразовать «попиксельно» полученный фрагмент в бинарную строку, то есть строку, где черному пикселю соответствует, например, '*', а белому — пробел.

Распознавание символов методом наименьшего расстояния Левенштейна - 4

short whiteBg = -1;
StringBuilder binaryString = new StringBuilder();  
for (short y = 1; y < height; y++)
   for (short x = 1; x < width; x++) {
       int rgb = symbol.getRGB(x, y);
       binaryString.append(rgb == whiteBg ? " " : "*");
   }

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

int min = 1000000;
char findSymbol = "";
for (Map.Entry<Character, String> entry : originalMap.entrySet()) {
     int levenshtein = levenshtein(binaryString.toString(), entry.getValue());
     if (levenshtein < min) {
             min = levenshtein;
             findSymbol = entry.getKey();
     }
}

Функция нахождения расстояния Левенштейна реализована в виде метода по стандартному алгоритму:

public static int levenshtein(String targetStr, String sourceStr) {
        int m = targetStr.length(), n = sourceStr.length();
        int[][] delta = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            delta[i][0] = i;
        for (int j = 1; j <= n; j++)
            delta[0][j] = j;
        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= m; i++) {
                if (targetStr.charAt(i - 1) == sourceStr.charAt(j - 1))
                    delta[i][j] = delta[i - 1][j - 1];
                else
                    delta[i][j] = Math.min(delta[i - 1][j] + 1,
                            Math.min(delta[i][j - 1] + 1, delta[i - 1][j - 1] + 1));
            }
        return delta[m][n];
    }

Полученный findSymbol и будет нашим распознанным символом.

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

Практическим способом было обнаружено, что метод качественно справляется даже с такими проблемными вопросами, как «схожесть» символов, например «Л»<->«П», «5»<->«S», «O»<->«0». Так как, к примеру, расстояние между бинарными строками «Л» и «П» будет всегда больше, чем между распознаваемой «Л» и эталонной строкой «Л», даже с некоторыми «неровностями».

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

Автор: alexneuro

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js