4
\$\begingroup\$

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. enter image description here

\$\endgroup\$
  • \$\begingroup\$ @KIKO Software condition can be seen in the function call at the bottom. \$\endgroup\$ – Hasen Jun 26 at 11:08
  • \$\begingroup\$ I don't think edge dectection is the right concept for what this routine does. It finds the minimum and maximum occurrence, along the x and y axis, of a pixel value. The fact that you mention "cropping" indicates that this is by design. Now I should, of course, propose an alternative name.... Ahem.... What about: findCropBoxByColor()? It finds the cropping box by color. \$\endgroup\$ – KIKO Software Jun 26 at 15:14
3
\$\begingroup\$

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]
}
\$\endgroup\$
  • 5
    \$\begingroup\$ @Hasan: If you provide a sample canvas then everybody can test their code against your code and see if the results match. Joost_96 could write a more complete answer as well. \$\endgroup\$ – KIKO Software Jun 26 at 11:09
  • 4
    \$\begingroup\$ Please keep in mind alternative implementations do not substitute a review. They can be part of one, but every answer on CR should take a look at the code and/or approach in the question. Welcome to Code Review! \$\endgroup\$ – Mast Jun 26 at 12:07
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Malachi Jun 26 at 14:05
  • 3
    \$\begingroup\$ Welcome to Code Review Joost_96! there is quite a bit of conversation going on here, so I moved the comments to a new chat room for further discussion (Click Here), you both should have enough Reputation to participate in Chat. Please keep in mind that comments are not first class citizens on Code Review and can be removed at any time, so please elaborate in your answer the changes that were made and what it adds to the code in terms of a review. \$\endgroup\$ – Malachi Jun 26 at 14:11
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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