Хабрахабр

[Из песочницы] Распознавание символов методом наименьшего расстояния Левенштейна

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

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

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

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

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

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

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);

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

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». Так как, к примеру, расстояние между бинарными строками «Л» и «П» будет всегда больше, чем между распознаваемой «Л» и эталонной строкой «Л», даже с некоторыми «неровностями».

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

Показать больше

Похожие публикации

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Хабрахабр

[Из песочницы] Распознавание символов методом наименьшего расстояния Левенштейна

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

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

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

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

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

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

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);

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

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». Так как, к примеру, расстояние между бинарными строками «Л» и «П» будет всегда больше, чем между распознаваемой «Л» и эталонной строкой «Л», даже с некоторыми «неровностями».

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

Показать больше

Похожие публикации

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»