Loop through canvas image to find the biggest spot of (almost) solid color

Question

I'm working on a project where I have a canvas with an image drawn onto it (for example this image: https://images.pexels.com/photos/188963/pexels-photo-188963.jpeg?w=1260&h=750&auto=compress&cs=tinysrgb)

Now what I've accomplished so far is to put filters on the image, giving me the following result:

Click me

What I now try to do is to find the location of the biggest blob of red. What I originally thought of was to loop through all pixels, and save the red pixels with a red pixel to it's right in an array, calculating the size and the X and Y position of the spot.

However, I don't think this would be very efficient, thus my question is, what's the easiest and most efficient way to detect a spot of solid color in a canvas image?

Answer 1

First of all, checking for blobs or clusters on large images (like yours) may be kinda expensive, since there's a total of 2582 * 1556 = 4017592 pixels.

Now, to find the biggest groups of pixels, you may want to travel the image as a Graph, and do a deep search from each pixel. Since you don't want to re-visit pixels, you need to keep which pixels are visited on an array (something called visited), and also some variables to store the biggests clusters found.

Here's the pseudocode:

// Search the biggest red blob on an image
findBiggestBlob(image):
  visited := array[image.height][image.width]
  biggest_blob_x := -1
  biggest_blob_y := -1
  biggest_blob_count := 0

  // Initialize the array
  for x in image.width
    for y in image.height
      visited[y][x] := false

  // Search on each pixel
  for x in image.width
    for y in image.height

      // Deep travel that pixel
      count = deepCount(image, x, y, visited, 0)

      // Check if it's big enoug
      if count > biggest_blob_count
        biggest_blob_x = x
        biggest_blog_y = y

  // Return the position and the size of the blob
  return x, y, biggest_blob_count


  // This is the deep search function
  deepCount(image, x, y, visited, count):
    // Ignore the pixel if it's out of bounds
    if x < 0 || x >= image.width || y < 0 || y >= image.height
      return count

    // Ignore the pixel if it's already visited
    if visited[y][x] == true
      return count

    // Mark the pixel as visited
    visited[y][x] := true

    // Skip if the pixel is not red
    if !isRed(image[y][x])
      return count

    // Increment count by 1
    count := count + 1

    // Search for adjacent pixels (up, left, right, down)
    // recursively
    count := count + deepCount(image, x, y-1, visited, 0)
    count := count + deepCount(image, x-1, y, visited, 0)
    count := count + deepCount(image, x+1, y, visited, 0)
    count := count + deepCount(image, x, y+1, visited, 0)

    // return the total count
    return count

Note that the isRed(c) is a checker to see if a color is red or not, which. Assuming that your filter image has only a red channel, this function can be implemented this way:

function isRed(c):
  if c.r > 200
    return true
  else
    return false

Being 200 the lowest acceptable value of the R channel (threshold).

If you want to also calculate the Bounds of the pixels' blob, you need to track the list of current's blob red pixels (and their positions) and compare the most upper-left pixel with the most bottom-right pixel.

---

If you want to speed up the process, you may want to setup some Heuristic rules; instead of searching every pixel on the image, try searching on N pixels on the image. For example, if your image has a total of 4017592 pixels, you may want to only traverse a total of, as a random number, 100513.

There's a high probability that some of those pixels land on a blob area. Of course, there's the (low) posibility too that all pixels lands on the smallest blob.

Basically, to select those N pixels, you can chose N random pixels of the image, iterate them 5 by 5, etc.

You can also execute this multiple times (5 or 10), and pick the best solution.

Applied to the algortihm above, it's something like this:

heuristicFindBiggestBlob(image):
  hot_pixels = selectRandomPixels(image)

  visited := array[image.height][image.width]
  biggest_blob_x := -1
  biggest_blob_y := -1
  biggest_blob_count := 0

  // Initialize the array
  for x in image.width
    for y in image.height
      visited[y][x] := false

  // Search on each pixel of the random list
  for pixel in hot_pixels
      x := pixel.x
      y := pixel.y

      // Deep travel that pixel
      count = deepCount(image, x, y, visited, 0)

      // Check if it's big enoug
      if count > biggest_blob_count
        biggest_blob_x = x
        biggest_blog_y = y

  // Return the position and the size of the blob
  return x, y, biggest_blob_count

// ...

---

In my humble opinion, this is probably a heavy task to be executed on the client side (JS on WebBrowser). You may want to consider delegating the task to a remote server:

1. The client works with the image.
2. The client sends the edited image to the server.
3. The server (some fast C++ cool app) process and find the biggest blob of the image.
4. The client recieves the information and fo whatever it wants with it.