Распознавание символов из изображения C++

*Примечание: в то время как этот пост в значительной степени посвящен билинейной интерполяции, я оставил заголовок более общим и включил дополнительную информацию на случай, если у кого-то возникнут какие-либо идеи о том, как я могу сделать это лучше

У меня возникли проблемы с реализацией способа идентификации букв на изображении, чтобы создать программу решения поиска слов. В основном в образовательных целях, а также в целях переносимости я пытался сделать это без использования библиотеки. Можно предположить, что изображение, с которого будут собираться персонажи, содержит не что иное, как пазл. Хотя эта страница распознает только небольшой набор символов, Я использовал его, чтобы направлять свои усилия вместе с этим также. Как было предложено в статье, у меня есть изображение каждой буквы, уменьшенное до 5x5, чтобы сравнить каждую неизвестную букву. Я добился наибольшего успеха, уменьшив неизвестное до 5x5, используя билинейную повторную выборку и суммируя квадраты разницы в интенсивности каждого соответствующего пикселя в известном и неизвестном изображениях. Чтобы попытаться получить более точные результаты, я также добавил квадрат разницы в соотношении ширины и высоты и соотношении белого и черного пикселей в верхней и нижней половине каждого изображения. Известное изображение с наиболее близким «показателем различия» к неизвестному изображению затем считается неизвестной буквой. Проблема в том, что это, кажется, имеет только около 50% точности. Чтобы улучшить это, я попытался использовать образцы большего размера (вместо 5x5 я попробовал 15x15), но это оказалось еще менее эффективным. Я также попытался просмотреть известные и неизвестные изображения, найти черты и формы и определить совпадение на основе двух изображений, имеющих примерно одинаковое количество одинаковых характеристик. Например, были идентифицированы и подсчитаны фигуры, подобные приведенным ниже (где ■ представляет собой черный пиксель). Это оказалось менее эффективным, чем исходный метод.

  ■ ■                 ■   ■
  ■                     ■

Итак, вот пример: загружается следующее изображение:

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

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

*Примечание: в известных образцах используется шрифт Arial размером 12, масштабированный в фотошопе до 5x5 с использованием билинейной интерполяции.

Вот пример успешного сопоставления: Выбирается следующая буква:

который выглядит как

издалека. Это успешно соответствует известному образцу N:

Вот неудачный матч:

который, что неудивительно, не соответствует известному образцу R

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

void Image::scaleTo(int width, int height)
{
    int originalWidth = this->width;
    int originalHeight = this->height;
    Image * originalData = new Image(this->width, this->height, 0, 0);
    for (int i = 0; i < this->width * this->height; i++) {
        int x = i % this->width;
        int y = i / this->width;
        originalData->setPixel(x, y, this->getPixel(x, y));
    }
    this->resize(width, height); //simply resizes the image, after the resize it is just a black bmp.
    double factorX = (double)originalWidth / width;
    double factorY = (double)originalHeight / height;
    float * xCenters = new float[originalWidth]; //the following stores the "centers" of each pixel.
    float * yCenters = new float[originalHeight];
    float * newXCenters = new float[width];
    float * newYCenters = new float[height];
    //1 represents one of the originally sized pixel's side length
    for (int i = 0; i < originalWidth; i++)
        xCenters[i] = i + 0.5;
    for (int i = 0; i < width; i++)
        newXCenters[i] = (factorX * i) + (factorX / 2.0);
    for (int i = 0; i < height; i++)
        newYCenters[i] = (factorY * i) + (factorY / 2.0);
    for (int i = 0; i < originalHeight; i++)
        yCenters[i] = i + 0.5;

    /*  p[0]            p[1]
                  p
        p[2]            p[3] */
    //the following will find the closest points to the sampled pixel that still remain in this order
    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            POINT p[4]; //POINT used is the Win32 struct POINT
            float pDists[4] = { FLT_MAX, FLT_MAX, FLT_MAX, FLT_MAX };
            float xDists[4];
            float yDists[4];
            for (int i = 0; i < originalWidth; i++) {
                for (int j = 0; j < originalHeight; j++) {
                    float xDist = abs(xCenters[i] - newXCenters[x]);
                    float yDist = abs(yCenters[j] - newYCenters[y]);
                    float dist = sqrt(xDist * xDist + yDist * yDist);
                    if (xCenters[i] < newXCenters[x] && yCenters[j] < newYCenters[y] && dist < pDists[0]) {
                        p[0] = { i, j };
                        pDists[0] = dist;
                        xDists[0] = xDist;
                        yDists[0] = yDist;
                    }
                    else if (xCenters[i] > newXCenters[x] && yCenters[j] < newYCenters[y] && dist < pDists[1]) {
                        p[1] = { i, j };
                        pDists[1] = dist;
                        xDists[1] = xDist;
                        yDists[1] = yDist;
                    }
                    else if (xCenters[i] < newXCenters[x] && yCenters[j] > newYCenters[y] && dist < pDists[2]) {
                        p[2] = { i, j };
                        pDists[2] = dist;
                        xDists[2] = xDist;
                        yDists[2] = yDist;
                    }
                    else if (xCenters[i] > newXCenters[x] && yCenters[j] > newYCenters[y] && dist < pDists[3]) {
                        p[3] = { i, j };
                        pDists[3] = dist;
                        xDists[3] = xDist;
                        yDists[3] = yDist;
                    }
                }
            }
            //channel is a typedef for unsigned char
            //getOPixel(point) is a macro for originalData->getPixel(point.x, point.y)
            float r1 = (xDists[3] / (xDists[2] + xDists[3])) * getOPixel(p[2]).r + (xDists[2] / (xDists[2] + xDists[3])) * getOPixel(p[3]).r; 
            float r2 = (xDists[1] / (xDists[0] + xDists[1])) * getOPixel(p[0]).r + (xDists[0] / (xDists[0] + xDists[1])) * getOPixel(p[1]).r; 
            float interpolated = (yDists[0] / (yDists[0] + yDists[3])) * r1 + (yDists[3] / (yDists[0] + yDists[3])) * r2;
            channel r = (channel)round(interpolated);

            r1 = (xDists[3] / (xDists[2] + xDists[3])) * getOPixel(p[2]).g + (xDists[2] / (xDists[2] + xDists[3])) * getOPixel(p[3]).g; //yDist[3]
            r2 = (xDists[1] / (xDists[0] + xDists[1])) * getOPixel(p[0]).g + (xDists[0] / (xDists[0] + xDists[1])) * getOPixel(p[1]).g; //yDist[0]
            interpolated = (yDists[0] / (yDists[0] + yDists[3])) * r1 + (yDists[3] / (yDists[0] + yDists[3])) * r2;
            channel g = (channel)round(interpolated);

            r1 = (xDists[3] / (xDists[2] + xDists[3])) * getOPixel(p[2]).b + (xDists[2] / (xDists[2] + xDists[3])) * getOPixel(p[3]).b; //yDist[3]
            r2 = (xDists[1] / (xDists[0] + xDists[1])) * getOPixel(p[0]).b + (xDists[0] / (xDists[0] + xDists[1])) * getOPixel(p[1]).b; //yDist[0]
            interpolated = (yDists[0] / (yDists[0] + yDists[3])) * r1 + (yDists[3] / (yDists[0] + yDists[3])) * r2;
            channel b = (channel)round(interpolated);

            this->setPixel(x, y, { r, g, b });
        }

    }
    delete[] xCenters;
    delete[] yCenters;
    delete[] newXCenters;
    delete[] newYCenters;
    delete originalData;
}

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

ОБНОВЛЕНИЕ: Итак, как и было предложено, я начал дополнять известный набор данных уменьшенными буквами из поиска слов. Это значительно повысило точность примерно с 50% до 70% (проценты рассчитаны для очень небольшого размера выборки, поэтому относитесь к цифрам легкомысленно). В основном я использую исходный набор символов в качестве основы (этот исходный набор был на самом деле наиболее точным из других наборов, которые я пробовал, например: набор, рассчитанный с использованием того же алгоритма передискретизации, набор с использованием другого шрифта и т. д.) И я просто вручную добавляю известных в этот набор. В основном я вручную назначаю первым 20 или около того изображениям, выбранным в поиске, соответствующую букву и сохраняю их в известную заданную папку. Я до сих пор выбираю наиболее близкий из всего известного набора, чтобы соответствовать букве. Будет ли это по-прежнему хорошим методом или следует внести какие-то изменения? Я также реализовал функцию, при которой, если буква примерно на 90% совпадает с известной буквой, я предполагаю, что совпадение правильное, и текущее «неизвестное» в список известных. Я мог видеть, что это, возможно, идет в обоих направлениях, я чувствую, что это может быть либо a. сделать программу более точной с течением времени или b. подтвердить первоначальное предположение и, возможно, со временем сделать программу менее точной. Я на самом деле не заметил, чтобы это вызвало изменения (ни в лучшую, ни в худшую сторону). Я на правильном пути с этим? Я пока не буду называть это решенным, пока не увеличу точность немного выше и не проверю программу на большем количестве примеров.