लेवेनशीन कम से कम दूरी की चरित्र पहचान

हाल ही में, आवेदन कार्यक्रमों में चरित्र मान्यता का कार्य विशेष रूप से कठिन नहीं है - आप कई तैयार ओसीआर-पुस्तकालयों का उपयोग कर सकते हैं, जिनमें से कई लगभग पूर्ण हैं। लेकिन फिर भी, कभी-कभी तृतीय-पक्ष "परिष्कृत" ओसीआर पुस्तकालयों का उपयोग किए बिना अपने स्वयं के मान्यता एल्गोरिदम को विकसित करने के लिए एक कार्य उत्पन्न हो सकता है।

यह ठीक वही कार्य है जो मेरे काम के दौरान उत्पन्न हुआ था, और कई कारण हैं कि तैयार पुस्तकालयों का उपयोग न करना बेहतर है: बंद परियोजना, इसके आगे प्रमाणीकरण के साथ, कोड की लाइनों की संख्या पर एक निश्चित प्रतिबंध और जुड़े पुस्तकालयों के आकार, सभी और अधिक इसलिए कि आपको विषय क्षेत्र में पर्याप्त पहचान करनी है विशिष्ट वर्ण सेट।

मान्यता एल्गोरिथ्म सरल है, और निश्चित रूप से, सबसे सटीक, तेज और प्रभावी होने का दिखावा नहीं करता है, लेकिन अपने अच्छे कार्य के साथ मुकाबला करता है।

मान लीजिए कि हमारे पास संरचित रूप में दस्तावेजों की स्कैन की गई छवियों के रूप में इनपुट है। इन दस्तावेजों में ऊपरी बाएं कोने में स्थित एक विशेष एक-वर्ण कोड है। हमारा कार्य इस प्रतीक को पहचानना है और फिर कुछ क्रियाएं करना है, उदाहरण के लिए, दिए गए नियमों के अनुसार स्रोत दस्तावेज़ को वर्गीकृत करें।

एल्गोरिथ्म आरेख इस प्रकार है:

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];
    }