Levenshtein التعرف على الأقل مسافة

في الآونة الأخيرة ، ليست مهمة التعرف على الأحرف في البرامج التطبيقية صعبة بشكل خاص - يمكنك استخدام العديد من مكتبات 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];
    }