Convert an image into characters and colors for the windows console

Question

I've written a function to convert an image into characters and colors for the windows console. At the moment the calculation takes about 13 seconds with a 700x700 pixel image but that time is undesirable especially when I plan on making the function more complex in order to account for character shapes.

What are some methods to speed up heavy calculations and loops like below in C++? I've been recommended multiple threads, SIMD, and inline assembly but how would I go about improving a function like below with those methods?

This is the current code I'm using.

unsigned char characterValues[256] = { 0 };

// This operation can be done ahead of time when the program is started up
{
    ResourceInputStream in = ResourceInputStream();
    // This image is the font for the console. The background color is black while the foreground color is white
    in.open(BMP_FONT, 2); // 2 is for RT_BITMAP, BMP_FONT is a resource
    if (in.isOpen()) {
        auto bmp = readBitmap(&in, true);
        in.close();
        for (int x = 0; x < bmp->size.x; x++) {
            for (int y = 0; y < bmp->size.y; y++) {
                int charIndex = (x / 8) + (y / 12) * 16;
                if (bmp->pixels[x][y].r == 255)
                    characterValues[charIndex]++;
            }
        }
    }
}
// This operation is for asciifying the image
{
    FileInputStream in = FileInputStream();
    in.open(R"(image-path.bmp)");
    if (in.isOpen()) {
        auto bmp = readBitmap(&in, false);
        in.close();

        // The size of the image in characters
        Point2I imageSize = (Point2I)GMath::ceil((Point2F)bmp->size / Point2F(8.0f, 12.0f));
        int totalImageSize = imageSize.x * imageSize.y;
        auto palette = /* get palette of 16 colors here */

        // Iterate through each (character area)
        for (int imgx = 0; imgx < imageSize.x; imgx++) {
            for (int imgy = 0; imgy < imageSize.y; imgy++) {

                // Read image color value
                int r = 0, g = 0, b = 0;
                int totalRead = 0;
                // Read each pixel inside the bounds of a single character
                // 8x12 is the size of a character
                for (int px = 0; px < 8; px++) {
                    for (int py = 0; py < 12; py++) {
                        Point2I p = Point2I(imgx * 8 + px, imgy * 12 + py);
                        if (p < bmp->size) {
                            r += bmp->pixels[p.x][p.y].r;
                            g += bmp->pixels[p.x][p.y].g;
                            b += bmp->pixels[p.x][p.y].b;
                            totalRead++;
                        }
                    }
                }
                Color imageValue = Color(r / totalRead, g / totalRead, b / totalRead);

                // A combo of a character and foreground/background color
                Pixel closestPixel = Pixel();
                float closestScore = std::numeric_limits<float>().max();
                for (int col = 1; col < 255; col++) {
                    unsigned char f = getFColor(col);
                    unsigned char b = getBColor(col);
                    for (int ch = 1; ch < 255; ch++) {
                        // Calculate values
                        Color value = Color(
                            (palette[f].r * characterValues[ch] + palette[b].r * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
                            (palette[f].g * characterValues[ch] + palette[b].g * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
                            (palette[f].b * characterValues[ch] + palette[b].b * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE
                        );
                        Color fvalue = Color(
                            (palette[f].r * characterValues[ch]) / TOTAL_CHARACTER_VALUE,
                            (palette[f].g * characterValues[ch]) / TOTAL_CHARACTER_VALUE,
                            (palette[f].b * characterValues[ch]) / TOTAL_CHARACTER_VALUE
                        );
                        Color bvalue = Color(
                            (palette[b].r * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
                            (palette[b].g * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
                            (palette[b].b * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE
                        );
                        // Add up score here
                        float score =
                            (float)((int)value.r - (int)imageValue.r) * (float)((int)value.r - (int)imageValue.r) +
                            (float)((int)value.g - (int)imageValue.g) * (float)((int)value.g - (int)imageValue.g) +
                            (float)((int)value.b - (int)imageValue.b) * (float)((int)value.b - (int)imageValue.b) +
                            (float)((int)fvalue.r - (int)imageValue.r) * (float)((int)fvalue.r - (int)imageValue.r) +
                            (float)((int)fvalue.g - (int)imageValue.g) * (float)((int)fvalue.g - (int)imageValue.g) +
                            (float)((int)fvalue.b - (int)imageValue.b) * (float)((int)fvalue.b - (int)imageValue.b) +
                            (float)((int)bvalue.r - (int)imageValue.r) * (float)((int)bvalue.r - (int)imageValue.r) +
                            (float)((int)bvalue.g - (int)imageValue.g) * (float)((int)bvalue.g - (int)imageValue.g) +
                            (float)((int)bvalue.b - (int)imageValue.b) * (float)((int)bvalue.b - (int)imageValue.b);
                        // More
                        if (score < closestScore) {
                            closestPixel = Pixel((unsigned char)ch, (unsigned char)col);
                            closestScore = score;
                        }
                    }
                }
                // Set the character/color combo here
            }
        }
    }
}

As a bonus, this is the result of my calculation. There's definitely room for improvement with the scoring but at least you can see the shape and colors.

Answer 1

Here's pretty much my end result for an algorithm. It takes about 20 seconds for a 1024x1280 with (4x6) pixel precision. I switched from primarily using Euclidean color difference to LAB color difference which also happens to run faster since most of the calculations can be done ahead of time.

For those of you who are curious to see what the results look like:

• LAB Delta E (4x6) precision
• LAB Delta E (8x12), (4x6), (2x3), & (1x1) precision (It's very picky about only working with pixels in its range.
• Euclidean (4x6) precision (This one actually looks worse with LAB)

Here's the final output for the algorithm:

#define SPLIT_X split.x
#define SPLIT_Y split.y
#define SPLIT_MAG (SPLIT_X * SPLIT_Y)
#define TOTAL_CHARACTER_VALUE (96 / SPLIT_MAG)
#define NUM_CHARACTERS 256
#define NUM_COLORS 256

AsciiAnimationSPtr Asciifier::asciifyImagePrecision(const std::string& path, Point2I split, ColorMetrics metric, ProgressDialogSPtr progressDialog) {
    #pragma region Declarations
    int totalTime = clock();
    BitmapData2* bmp = nullptr;

    int** characterCounts = nullptr;
    ColorI** characterValues = nullptr;
    ColorI** characterFValues = nullptr;
    ColorI** characterBValues = nullptr;
    ColorF** characterLABs = nullptr;
    ColorI* imageValues = nullptr;
    ColorF* imageLABs = nullptr;

    init2DArray(characterCounts, int, NUM_CHARACTERS, SPLIT_MAG);
    if (metric == ColorMetrics::Euclidean) {
        init2DArray( characterValues, ColorI, NUM_CHARACTERS * NUM_COLORS, SPLIT_MAG);
        init2DArray(characterFValues, ColorI, NUM_CHARACTERS * NUM_COLORS, SPLIT_MAG);
        init2DArray(characterBValues, ColorI, NUM_CHARACTERS * NUM_COLORS, SPLIT_MAG);
        init1DArray(imageValues, ColorI, SPLIT_MAG);
    }
    else {
        init2DArray(characterLABs, ColorF, NUM_CHARACTERS * NUM_COLORS, SPLIT_MAG);
        init1DArray(imageLABs, ColorF, SPLIT_MAG);
    }
    #pragma endregion

    #pragma region Init A
    progressDialog->setActionMessage("Reading console font...");
    updateProgress();

    CoInitialize(nullptr);
    IStream* stream = CreateStreamOnResource(PNG_FONT, "PNG");
    IWICBitmapSource* bitmap = LoadBitmapFromStream(stream);
    bmp = readBitmap(bitmap);
    stream->Release();
    #pragma endregion

    #pragma region Read Character Values
    progressDialog->setActionMessage("Reading image...");
    if (progressDialog->update()) {
        return nullptr;
    }
    for (int x = 0; x < bmp->size.x; x++) {
        for (int y = 0; y < bmp->size.y; y++) {
            if (bmp->pixels[xyToIndex(x, y, bmp->size.x)].r == 255) {
                int charIndex = (x / 8) + (y / 12) * 16;
                int subIndex = (x % 8 * SPLIT_X / 8) + (y % 12 * SPLIT_Y / 12) * SPLIT_X;
                characterCounts[charIndex][subIndex]++;
            }
        }
    }
    delete bmp;
    bmp = nullptr;
    #pragma endregion

    #pragma region Init B
    stream = CreateStreamOnFile(path);
    bitmap = LoadBitmapFromStream(stream);
    bmp = readBitmap(bitmap);
    stream->Release();

    Point2I imageSize = (Point2I)GMath::ceil((Point2F)bmp->size / Point2F(8.0f, 12.0f));
    int totalImageSize = imageSize.x * imageSize.y;
    auto image = std::make_shared<AsciiAnimation>(imageSize, ImageFormats::Basic, Pixel());

    image->resize(imageSize);
    auto graphics = image->createGraphics();

    ColorI palette[16] = {
        ColorI(0,   0,   0),
        ColorI(0,   0, 128),
        ColorI(0, 128,   0),
        ColorI(0, 128, 128),
        ColorI(128,   0,   0),
        ColorI(128,   0, 128),
        ColorI(128, 128,   0),
        ColorI(192, 192, 192),
        ColorI(128, 128, 128),
        ColorI(0,   0, 255),
        ColorI(0, 255,   0),
        ColorI(0, 255, 255),
        ColorI(255,   0,   0),
        ColorI(255,   0, 255),
        ColorI(255, 255,   0),
        ColorI(255, 255, 255)
    };
    #pragma endregion

    #pragma region Init C
    progressDialog->setActionMessage("Calculating character LABs...");
    updateProgress();

    for (int col = 1; col < 255; col++) {
        unsigned char f = getFColor(col);
        unsigned char b = getBColor(col);
        if (f == b)
            continue;
        ColorI fcolor = palette[f];
        ColorI bcolor = palette[b];
        for (int ch = 1; ch < 255; ch++) {
            if (ch == 8 || ch == 10 || ch == 219 || ch == 222 || ch == 223)
                continue;
            for (int s = 0; s < SPLIT_MAG; s++) {
                if (metric == ColorMetrics::Euclidean) {
                    ColorI fvalue = fcolor * characterCounts[ch][s];
                    ColorI bvalue = bcolor * (TOTAL_CHARACTER_VALUE - characterCounts[ch][s]);
                    ColorI value = (fvalue + bvalue) / TOTAL_CHARACTER_VALUE;
                    fvalue /= TOTAL_CHARACTER_VALUE;
                    bvalue /= TOTAL_CHARACTER_VALUE;
                    int charIndex = col + (ch << 8);
                    characterValues [charIndex][s] =  value;
                    characterFValues[charIndex][s] = fvalue;
                    characterBValues[charIndex][s] = bvalue;
                }
                else {
                    ColorI characterValue = (
                        fcolor * characterCounts[ch][s] +
                        bcolor * (TOTAL_CHARACTER_VALUE - characterCounts[ch][s])
                    ) / TOTAL_CHARACTER_VALUE;
                    characterLABs[col + (ch << 8)][s] = RGB2LAB(characterValue);
                }
            }
        }
    }
    #pragma endregion

    updateAsciifierProgress(-1, imageSize.x, clock() - totalTime, progressDialog);
    updateProgress();
    for (int imgx = 0; imgx < imageSize.x; imgx++) {
        for (int imgy = 0; imgy < imageSize.y; imgy++) {

            #pragma region Read Image Values
            int ix = imgx * 8;
            int iy = imgy * 12;
            for (int s = 0; s < SPLIT_MAG; s++) {
                ColorI imageValue;
                cint totalRead = 0;
                int sx = ix + (s % SPLIT_X * 8 / SPLIT_X);
                int sy = iy + (s / SPLIT_X * 12 / SPLIT_Y);
                for (int px = 0; px < 8 / SPLIT_X; px++) {
                    int p_x = sx + px;
                    if (p_x >= bmp->size.x)
                        continue;
                    for (int py = 0; py < 12 / SPLIT_Y; py++) {
                        int p_y = sy + py;
                        if (p_y >= bmp->size.y)
                            continue;
                        imageValue += bmp->pixels[xyToIndex(p_x, p_y, bmp->size.x)];
                        totalRead++;
                    }
                }
                if (totalRead > 0) {
                    if (metric == ColorMetrics::Euclidean)
                        imageValues[s] = imageValue / totalRead;
                    else
                        imageLABs[s] = RGB2LAB(imageValue / totalRead);
                }
                else {
                    if (metric == ColorMetrics::Euclidean)
                        imageValues[s] = ColorI();
                    else
                        imageLABs[s] = ColorF();
                }
            }
            #pragma endregion

            Pixel closestPixel = Pixel();
            float closestScore = std::numeric_limits<float>().max();
            for (int col = 1; col < 255; col++) {
                unsigned char f = getFColor(col);
                unsigned char b = getBColor(col);
                if (f == b)
                    continue;
                ColorI fcolor = palette[f];
                ColorI bcolor = palette[b];
                for (int ch = 1; ch < 255; ch++) {
                    if (ch == 8 || ch == 10 || ch == 219 || ch == 222 || ch == 223)
                        continue;
                    float score = 0.0f;

                    for (int s = 0; s < SPLIT_MAG; s++) {
                        #pragma region Euclidean
                        if (metric == ColorMetrics::Euclidean) {
                            int charIndex = col + (ch << 8);
                            ColorI imageValue = imageValues[s];
                            ColorI  value =  characterValues[charIndex][s] - imageValue;
                            ColorI fvalue = characterFValues[charIndex][s] - imageValue;
                            ColorI bvalue = characterBValues[charIndex][s] - imageValue;

                            #pragma region Calc Score
                            score +=
                                std::pow(
                                    std::pow(
                                        float(value.r * value.r) +
                                        float(value.g * value.g) +
                                        float(value.b * value.b),
                                    2) +
                                    std::pow(
                                        float(fvalue.r * fvalue.r) +
                                        float(fvalue.g * fvalue.g) +
                                        float(fvalue.b * fvalue.b),
                                    2) +
                                    std::pow(
                                        float(bvalue.r * bvalue.r) +
                                        float(bvalue.g * bvalue.g) +
                                        float(bvalue.b * bvalue.b),
                                    2),
                                2);
                            #pragma endregion
                        }
                        #pragma endregion
                        #pragma region LAB Delta E
                        else {
                            score += std::pow(LAB2Value(imageLABs[s], characterLABs[col + (ch << 8)][s]), 2);
                        }
                        #pragma endregion
                    }

                    if (score < closestScore) {
                        closestPixel = Pixel((unsigned char)ch, (unsigned char)col);
                        closestScore = score;
                    }
                }
            }
            graphics->setPixel(Point2I(imgx, imgy), closestPixel);
        }
        updateAsciifierProgress(imgx, imageSize.x, clock() - totalTime, progressDialog);
        updateProgress();
    }

    #pragma region Cleanup
    progressDialog->setPercentage(100);
    progressDialog->setActionMessage("Completed");
    updateProgress();

    progressDialog->console().sleep(200);
    progressDialog->close();
    cleanup();
    return image;
    #pragma endregion
};

As for why this improvement works. For LAB, all of the character/color combo calculations are done in one loop ahead of time and stored in a large array. This increases the memory usage by a bit but that shouldn't be a problem for the short lifespan of the arrays.

Euclidean was a little tougher to improve (my original calulation method). I calculated the original character values ahead of time. Unlike the LAB values, for Euclidean I compared the total color, the foreground color, and the background color. This means 3 times the amount of arrays I used for LAB to do calculations ahead of time and even then some of them cannot be avoided during the loop. Over this method had minor improvements but not as significant.

The other issue that was causing long calulation times was reading the bitmap. I didn't show how I did it before in my question but I was reading it manually and reading each pixel one character at a time. I discovered this was taking about 5 seconds with a 700x700 image. Now I'm using Windows Imaging Component (WIC) and it loads in an instant. If anyone is in need of help using WIC to load images and read the pixels I'll be happy to show how I did it since it's a bit complicated to start out with.