Edge detection in a canvas

Question

I have one function in my code to detect edges in a canvas but it's the slowest part of my code and is used everywhere. If I could just optimise this, my whole program would speed up considerably.

Maybe something better can be done with Em6?

Basically the function goes from the left until it finds a pixel colour greater (or less than) the colour value passed to the function. Then it gets the maximum or minimum of all the values which is the edge of whatever is inside the image.

Then it does the same for the top, the right the bottom to find all edges. Useful for cropping something within a canvas.

function getEdges(tempcanv, colour, which, condition) {
    let ledge = [], redge = [], tedge = [], bedge = [];
    const canvwidth = tempcanv.width, canvheight = tempcanv.height;
    const contextd = tempcanv.getContext('2d');
    for (let y = 0; y < canvheight; y++) {//left edge
        for (let x = 0; x < canvwidth; x++) {
            const data = contextd.getImageData(x, y, 1, 1).data;
            if (condition(data[which], colour)) {
                ledge.push(x);
                break;
            }
        }
    }
    ledge = Math.min(...ledge);
    const llim = ledge === 0 ? ledge : ledge - 1;
    for (let x = llim; x < canvwidth; x++) {//top edge
        for (let y = 0; y < canvheight; y++) {
            const data = contextd.getImageData(x, y, 1, 1).data;
            if (condition(data[which], colour)) {
                tedge.push(y);
                break;
            }
        }
    }
    tedge = Math.min(...tedge);
    const tlim = tedge === 0 ? tedge : tedge - 1;
    for (let y = tlim; y < canvheight; y++) {//right edge
        for (let x = canvwidth - 1; x >= ledge; x--) {
            const data = contextd.getImageData(x, y, 1, 1).data;
            if (condition(data[which], colour)) {
                redge.push(x);
                break;
            }
        }
    }
    redge = Math.max(...redge);
    for (let x = llim; x <= redge; x++) {//bottom edge
        for (let y = canvheight - 1; y >= tedge; y--) {
            const data = contextd.getImageData(x, y, 1, 1).data;
            if (condition(data[which], colour)) {
                bedge.push(y);
                break;
            }
        }
    }
    return [ledge, tedge, redge + 1, Math.max(...bedge) + 1]
}

//(canvas passed, colour threshold, R,G or B, greater or less than)
getEdges(canvas, 180, 0, (a, b) => a > b))

My code does have some optimisation since as it finds an edge, the next edge check does not check the dead space already checked.

Here is a test shape.

Answer 1

In your code you're calling GetImageData for each pixel adding a lot of call that are not necessary, you can do this by calling it once for the entire canvas and getting the data from the array.

GetImageData returns a 1 dim array with RGBA for each pixel like :

[R(pixel1),G(Pixel1),B(Pixel1),A(Pixel1),R(pixel2),G(Pixel2),...etc]

this means that you can get the pixel value by using (y * canvasWidth+ x)*4+RGBA (RBGA is a 0-3 value representing the 4 values)

Another thing you can improve on is the order of your for loops. The way you're looping now you need to loop through the whole image before you can know the edge, however if you turn the loops around you can lessen the amount of pixels you need to check.

For example when going for the left edge you can start the double loop with x then y. This means that whenever the condition first becomes true you can be sure that it is the outer most left edge.

If you implement these relative easy changes the code would look more like this:

function getEdges(tempcanv, colour, which, condition) {
    let ledge = -1, redge = -1, tedge = -1, bedge = -1;
    const canvwidth = tempcanv.width, canvheight = tempcanv.height;
    const imageData = tempcanv.getContext('2d').getImageData(0, 0, canvwidth, canvheight).data; //gets all image data
    for (let x = 0; x < canvwidth; x++) {//left edge
        if (ledge >= 0) {
            break;
        }
        for (let y = 0; y < canvheight; y++) {
            //(y * canvwidth + x) * 4 is for getting the current location
            if (condition(imageData[(y * canvwidth + x) * 4 + which], colour)) {
                ledge = x;
                break;
            }
        }
    }
    for (let x = canvwidth - 1; x >= ledge; x--) {//right edge
        if (redge >= 0) {
            break;
        }
        for (let y = 0; y < canvheight; y++) {
            //(y * canvwidth + x) * 4 is for getting the current location
            if (condition(imageData[(y * canvwidth + x) * 4 + which], colour)) {
                redge = x;
                break;
            }
        }
    }
    for (let y = 0; y < canvheight; y++) {//top edge
        if (tedge >= 0) {
            break;
        }
        for (let x = ledge; x <= redge; x++) {
            //(y * canvwidth + x) * 4 is for getting the current location
            if (condition(imageData[(y * canvwidth + x) * 4 + which], colour)) {
                tedge = y;
                break;
            }
        }
    }
    for (let y = canvheight-1; y >= tedge; y--) {//bottom edge
        if (bedge >= 0) {
            break;
        }
        for (let x = ledge; x <= redge; x++) {
            //(y * canvwidth + x) * 4 is for getting the current location
            if (condition(imageData[(y * canvwidth + x) * 4 + which], colour)) {
                bedge = y;
                break;
            }
        }
    }
    console.log('edges', [ledge, tedge, redge + 1, bedge + 1]);
    return [ledge, tedge, redge + 1, bedge + 1]
}

Answer 2

Oh my you are right that is rather slow.

I see that the accepted answer is a significant improvement however it can be done even faster

Flat array

The pixel buffer is a flat array of bytes, you waste a lot of cycles converting 2D coordinates {x,y} to the flat index. It is quicker to convert the flat index to 2D for each of the four points you find.

You can convert from an byte index to coordinates as follows x = Math.floor(idx / 4) % width, y = Math.floor(idx / width / 4); Or for a little better performance using bit-wise math. x = (idx >> 2) % width, y = (idx >> 2) / width | 0;

Example finding the first row

 const pixels = ctx.getImageData(0,0,width,height).data;
 var top;
 var idx = which; // start on the channel you are reading
 while (idx < pixels.length) {
     if (condition(pixels[idx], colour)) {
         top = idx / (width * 4);
         break;
     }
     idx += 4;
 }

The conditional

You are passing a function to test each pixel. It is likely that the JS engine will inline that function if it is not too complex, but it is still not ideal. Passing the same colour every call is also unneeded overhead

You do not give much detail on what that function does apart from you are checking for high or low values. You will get some improvement if you manually inline the test. It will mean a few more copies of the whole test function, but that is the cost of performance.

Words, bytes, and bits

Again it is unclear what the conditional is but using some bit wise math you can test all 4 channels in 1 operation.

First map a 32 bit array to the pixel data using a typed array Uint32Array

 const pix32 = new Uint32Array(ctx.getImageData(0, 0, width, height).data.buffer);

Now you read a pixel at a time as a 32bit unsigned word (Number).

Say for example you want to test if a pixel has an alpha value of 128 or higher

 if (pix32[idx] & 0x80000000) { // alpha >= 128

Or check if red is within a range 64 to 128

 if ((pix32[idx] & 0xC0) === 0x40) { // red >= 64 && red < 128

Or for a specific colour

 if ((pix32[idx] & 0xFFFF00) === 0xFFFF00) { pixel with any alpha and color cyan
 if ((pix32[idx] & 0xFFFF00) === 0xFF0000) { pixel with any alpha and color blue
 if ((pix32[idx] & 0xFFFF) === 0xFFFF) { pixel with any alpha and color Yellow
 if ((pix32[idx] & 0xFFFFFF) === 0xFFFFFF) { pixel with any alpha and color White

You will not have the fine control of boolean logic, but it will be way faster.

(NOTE most CPU will have the channels in reverse order Alpha, Blue, Green, Red. little-endian)

More speed?

Next step would be a web worker. You can have 4 concurrent workers each checking a size.

These types of problem can have solutions that give huge performance increases when the big picture is incorporated into the code. Without knowing why you are processing these images, what rendered them, their quality and how dynamic the changes are there is not much more I can give apart from an example brute force solution implementing the points in this answer.

Example

The example is not for the faint of heart and is not to spec as this version only handles bit masked conditions. it is however fast processing an image the size of your example image in under 1ms and is around 4 times faster than the accepted answer, and 100s of times faster than your original.

As there is already an accepted answer I did not bother going into fine detail to match your spec.

// example call canvas has context as property 
canvas.ctx = canvas.getContext("2d");
getEdges(canvas, 0xFC); // find bounds for red channel value > 3
getEdges(canvas, 0xF000); // find bounds for green channel value > 15


function getEdges(img, mask, result = {}) {
    const w = img.width, h = img.height;
    var top, bot, idx = 0;
    const D32 = new Uint32Array(img.ctx.getImageData(0, 0, w, h).data.buffer);
    const pixelCount = D32.length;

    while (idx < pixelCount) {  // find top
        if (D32[idx++] && mask) { 
            result.top = top = (idx - 1) / w | 0; 
            break;
        }
    }
    if (idx < pixelCount) {  // continue only if pixels found 
        idx = pixelCount;
        while (idx--) {  // find bottom
            if (D32[idx] && mask) { 
                result.bot = bot = idx / w | 0; 
                break;
            }
        }    
        top *= w;  // side checks only between top and bottom found bounds
        bot *= w;
        const len = bot - top - 1;
        idx = top;  // start top left scans down and across
        while (true) {
            if (D32[idx] && mask) { 
                result.left = idx % w;
                break;
            }
            ++idx > bot && (idx -= len); // move to top and one right
        }
        idx = bot + w - 1;  // start bottom right scans up and left
        while (true) {
            if (D32[idx] && mask) { 
                result.right = idx % w;
                break;
            }
            --idx < bot && (idx += len); // move to bot and one left
        }
    }
    return result;
}