How to optimize the algorithm of generating images in javascript canvas?

Question

I added this question on Stackoverflow, but it was suggested that I post it here.

Currently, I create 2000x2000 pixels canvas and tile the image on it, and then tiling the texture on top and applying multiply and alpha effects to it to make it look more natural.

So, in detail, function imageUrlToFile is used to get the image from URL and convert it to File, function replaceColors used to first convert the colors from black/white/gray into the given colors, tile both the image and texture in a 2000x2000 pixel canvas and apply the multiply effect to the texture to make it look like a knitting pattern.

const imageUrl = 'https://i.imgur.com/JbzgtBV.png';
const textureUrl = 'https://i.imgur.com/Nl2A3ZC.png';
const colors = [
  [0, 0, 0],
  [70, 200, 100]
];

async function imageUrlToFile(imageUrl) {
  try {
    const response = await fetch(imageUrl);
    if (!response.ok) {
      throw new Error(`Failed to fetch image (status ${response.status})`);
    }
    const blob = await response.blob();
    const filename = imageUrl.substring(imageUrl.lastIndexOf('/') + 1);
    const file = new File([blob], filename, {
      type: blob.type
    });
    return file;
  } catch (error) {
    console.error('Error in imageUrlToFile:', error);
    throw error;
  }
}

async function replaceColors(imageDataFile, colorArray, textureFile) {
  return new Promise((resolve, reject) => {
    const image = new Image();
    const texture = new Image();
    const reader = new FileReader();
    const textureReader = new FileReader();

    const canvasSize = 2000;

    // Image loading and tiling
    reader.onload = function(event) {
      image.onload = async() => {
        const canvas = new OffscreenCanvas(canvasSize, canvasSize);
        const context = canvas.getContext('2d');

        const imageWidth = image.width;
        const imageHeight = image.height;

        if (imageWidth >= canvasSize && imageHeight >= canvasSize) {
          context.drawImage(image, 0, 0, canvasSize, canvasSize);
        } else {
          // Tile the image only if necessary
          const numTilesX = Math.ceil(canvasSize / imageWidth);
          const numTilesY = Math.ceil(canvasSize / imageHeight);

          for (let x = 0; x < numTilesX; x++) {
            for (let y = 0; y < numTilesY; y++) {
              context.drawImage(image, x * imageWidth, y * imageHeight, imageWidth, imageHeight);
            }
          }
        }

        const imageData = context.getImageData(0, 0, canvasSize, canvasSize);
        const imageDataArray = imageData.data;

        const numColors = colorArray.length;
        const thresholdStep = 255 / numColors;

        for (let i = 0; i < imageDataArray.length; i += 4) {
          const avg = (imageDataArray[i] + imageDataArray[i + 1] + imageDataArray[i + 2]) / 3;
          let colorIndex = Math.floor(avg / thresholdStep);
          colorIndex = Math.min(colorIndex, numColors - 1);

          imageDataArray[i] = colorArray[colorIndex][0];
          imageDataArray[i + 1] = colorArray[colorIndex][1];
          imageDataArray[i + 2] = colorArray[colorIndex][2];
        }

        context.putImageData(imageData, 0, 0);

        textureReader.onload = (e) => {
          texture.onload = () => {
            context.globalAlpha = 1.0;
            context.globalCompositeOperation = 'multiply';

            const textureWidth = texture.width;
            const textureHeight = texture.height;

            const numTextureTilesX = Math.ceil(canvasSize / textureWidth);
            const numTextureTilesY = Math.ceil(canvasSize / textureHeight);

            for (let x = 0; x < numTextureTilesX; x++) {
              for (let y = 0; y < numTextureTilesY; y++) {
                context.drawImage(texture, x * textureWidth, y * textureHeight, textureWidth, textureHeight);
              }
            }

            context.globalAlpha = 1;
            context.globalCompositeOperation = 'source-over';

            canvas.convertToBlob({
              type: 'image/png'
            }).then((blob) => {
              if (blob) {
                const file = new File([blob], 'replaced.png', {
                  type: 'image/png'
                });
                resolve(file);
              } else {
                reject(new Error('Failed to create blob from canvas.'));
              }
            }).catch(reject);
          };

          texture.onerror = () => reject(new Error('Failed to load texture.'));
          texture.src = e.target.result;
        };

        textureReader.onerror = () => reject(new Error('Failed to read texture file.'));
        textureReader.readAsDataURL(textureFile);
      };

      image.onerror = () => reject(new Error('Failed to load image.'));
      image.src = event.target.result;
    };

    reader.onerror = () => reject(new Error('Failed to read image file.'));
    reader.readAsDataURL(imageDataFile);
  });
}



async function displayImage() {
  try {
    const imageFile = await imageUrlToFile(imageUrl);
    const textureFile = await imageUrlToFile(textureUrl);
    const finalFile = await replaceColors(imageFile, colors, textureFile);

    const imgElement = document.getElementById('resultImage');
    const imageBlobUrl = URL.createObjectURL(finalFile);
    imgElement.src = imageBlobUrl;
    imgElement.onload = () => URL.revokeObjectURL(imageBlobUrl);
  } catch (error) {
    console.error('Error displaying image:', error);
  }
}

// Call the displayImage function when the page loads
window.onload = displayImage;

* {
  padding: 0;
  margin: 0;
  box-sizing: border-box;
}

<img id="resultImage" alt="Result Image" />

Code works as expected, however in my old question I was told that for different users it took more than a minute to get the result image, which is bad because it is part of our big project.

I have debugged the code and also run it in following machines:

1. Macbook Pro 2016 (13 inch)
2. Asus ROG Strix G15
3. Macbook Pro 2017 (15 inch)

But, in my case it was taking maximum 3-4 seconds to run and return the image with 2000x2000 pixels. I have tried it with different browsers including Chrome, Firefox and Safari and all of them had similar results.

Thus, my question is, if possible, is there any better way to optimize the algorithm to make it faster?

Answer 1

Performance review

Your task should be realtime (under 16ms) as the overhead is tiny but you have missed many of the optimisations available to you.

• Avoid encoding/decoding images when not required.

• Use the GPU to repeat rendering (rather than JavaScript)

• Process minimum number of pixels.

Encoding / Decoding images

You for some reason are using the slowest methods to load and display images you could possibly find.

Loading

To load an image using async function

async function loadImage(src) {
    const img = new Image();
    img.crossOrigin = "anonymous";  // needed as your image has cors in the header
    img.src = src;
    await img.decode();
    return img;
}

• Note: To await the image load use HTMLImageElement.decode

• Note: One of the images has a CORS header so you need to add the crossOrigin: "anonymous" pair to the request header.

• Note: The above example returns an image. Personally as there is a lot of processing and image manipulation in your task I would suggest that you return a standard canvas.

  async function loadImage(src) {
      const img = new Image();
      img.crossOrigin = "anonymous";
      img.src = src;
      await img.decode();
      const canvas = Object.assign(
          document.createElement("canvas"), 
          {width: img.naturalWidth, height: img.naturalHeight}
      );
      canvas.getContext("2d").drawImage(img, 0, 0);
      return canvas;
  }
  

Displaying

When you display an image there is no reason to convert the canvas to an image. The process of encoding and image to png, convert to base64, then back to raw, then decoding the png into a image is slow compared to just putting the image / canvas into the DOM.

Use a container to hold the image / canvas

<div id="resultImageContainer"></div>

Rather than use an offscreen canvas use a standard canvas

// don't use OffscreenCanvas if you want to display the canvas
// const canvas = new OffscreenCanvas(canvasSize, canvasSize);
const canvas = Object.assign(
    document.createElement("canvas"), 
    {width: canvasSize, height: canvasSize}
);

The function replaceColors should return the canvas (as created above) reference not a blob.

You can place the canvas directly onto the DOM with the minimum of overhead.

const processedCanvas = replaceColors(... // returns a HTMLCanvasElement
const imgContainer = document.getElementById("resultImageContainer");
imgContainer.append(processedCanvas);

This will reduce the processing and memory overheads of your code by a significant amount. However this is not the source of your slowdown.

Image processing

Always process the minimum number of pixels posible. Processing one hundred pixels is a lot faster than processing four million.

Have the GPU do the hard work. It is excellent at tiling, JavaScript, at its best, is not.

GPU to draw a pattern

You code draws a source image tiled onto a larger image. If you debug the code you can see that you generate 40,000 drawImage calls. That is a lot!!!

Rather than tile the image in JavaScript let the renderer do the hard work via CanvasRenderingContext2D.createPattern

Set the context ctx.fillStyle to the pattern and fill the canvas with a rect ctx.fillRect(0, 0, ctx.canvas.width, ctx.canvas.height). The CPU/GPU cost of using a pattern is equivalent to about 4-5 drawImage calls (GPU is very good at tiling)

D.R.Y. Pixel processing!

Don't repeat yourself. (DRY)

When you process the colors you do this to the tiled pixels drawn onto the large canvas. However the processing for each tile is identical.

Rather than process the colors after drawing the tiled image. Process the tile image, convert that to a pattern then draw the processed pattern to the result image.

The tile image contains only 100 pixels, while the result image has 4,000,000 pixels. That is a CPU task reduction of a HUGE 40,000 to 1

Result

Most of the overhead I see is in terms of memory allocations/deallocations but users see the time.

Avoiding the Blob image manipulation saves a lot of the memory management overhead.

Smarter image processing (using pattern and process minimum pixels) saves the time (the part the client notices).

All up if you implement all of the above the task should take at most a few ms (ignoring image download time)

Answer 2

performance measurements

This code is running on at least four machines. Two MacBooks and an Asus ROG Strix G15 manage to render at least a thousand pixels per millisecond, while other machine(s) render more slowly. You need to make measurements on slow machines.

Minimally, record total rendering time, and plot how that varies with image size. You may find that small images go "fast", and then upon exceeding some L2 or L3 cache size the render speed is noticeably slower. Ideally, profile your app so you know which source lines are responsible for most of the delay.

task granularity

You're performing 40 thousand separate operations on a 10px × 10px image, to produce a large periodically repeating pattern. Stitch subimages together so you perform fewer operations on e.g. a 20px × 20px image. Then you will suffer overhead from fewer function calls, and can let the underlying graphics primitives work more efficiently on bigger chunks.

magic number

const colors = [
  [0, 0, 0],
  [70, 200, 100]
];

"Black" is pretty straightforward. It wouldn't hurt for a // comment to spell out what that other RGB value denotes.

Answer 3

In replaceColors(), the special handling of just one tile is not justified.
There are two places that open-code tiling.

Process data before replication!
Depending on the relative size of image and texture, this may include multiplication/combination/convolution.