8
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Is there any reason you cast everything to float? It seems to me that your big calculation would work just fine if you left the score as an int. Also, it would be even cooler if your program compared each pixel to each pixel (instead of block by block), because then you might even see details within each character show up (like lines and curves). Of course that would take 96x more time but I'd be interested in the result. \$\endgroup\$
    – JS1
    Mar 23, 2017 at 5:34
  • \$\begingroup\$ Yeah I noticed later in the night that I could switch that float to an int. As for precision, I was planning on upping it to support character shapes but it wouldn't be realistic with the current speeds. \$\endgroup\$ Mar 23, 2017 at 14:30
  • \$\begingroup\$ @JS1 I've posted a final algorithm and results since you said you were interested. \$\endgroup\$ Mar 24, 2017 at 2:47

1 Answer 1

5
\$\begingroup\$

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:

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.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Review! You have presented an improved solution, but haven't reviewed the code. Please explain your reasoning (how this solution works and how it improves upon the original) so that others can learn from your thought process. \$\endgroup\$
    – Vogel612
    Mar 24, 2017 at 9:18
  • \$\begingroup\$ @trigger_death Do you have a github repo for your solution? I have a couple of thoughts and can contribute into it. \$\endgroup\$
    – mtkachenko
    May 26 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.