Find regions of similar color in image

Question

I've been working on this problem for some time now with little promising results. I am trying to split up an image into connected regions of similar color. (basically split a list of all the pixels into multiple groups (each group containing the coordinates of the pixels that belong to it and share a similar color).

For example: http://unsplash.com/photos/SoC1ex6sI4w/

In this image the dark clouds at the top would probably fall into one group. Some of the grey rock on the mountain in another, and some of the orange grass in another. The snow would be another - the red of the backpack - etc.

I'm trying to design an algorithm that will be both accurate and efficient (it needs to run in a matter of ms on midrange laptop grade hardware)

---

Below is what I have tried:

Using a connected component based algorithm to go through every pixel from top left scanning every line of pixels from left to right (and comparing the current pixel to the top pixel and left pixel). Using the CIEDE2000 color difference formula if the pixel at the top or left was within a certain range then it would be considered "similar" and part of the group.

This sort of worked - but the problem is it relies on color regions having sharp edges - if any color groups are connected by a soft gradient it will travel down that gradient and continue to "join" the pixels as the difference between the individual pixels being compared is small enough to be considered "similar".

To try to fix this I chose to set every visited pixel's color to the color of most "similar" adjacent pixel (either top or left). If there are no similar pixels than it retains it's original color. This somewhat fixes the issue of more blurred boundaries or soft edges because the first color of a new group will be "carried" along as the algorithm progresses and eventually the difference between that color and the current compared color will exceed the "similarity" threashold and no longer be part of that group.

Hopefully this is making sense. The problem is neither of these options are really working. On the image above what is returned are not clean groups but noisy fragmented groups that is not what I am looking for.

I'm not looking for code specifically - but more ideas as to how an algorithm could be structured to successfully combat this problem. Does anyone have ideas about this?

Thanks!

Answer 1

You could convert from RGB to HSL to make it easier to calculate the distance between the colors. I'm setting the color difference tolerance in the line:

if (color_distance(original_pixels[i], group_headers[j]) < 0.3) {...}

If you change 0.3, you can get different results.

See it working.

Please, let me know if it helps.

function hsl_to_rgb(h, s, l) {
    // from http://stackoverflow.com/questions/2353211/hsl-to-rgb-color-conversion
    var r, g, b;

    if (s == 0) {
      r = g = b = l; // achromatic
    } else {
      var hue2rgb = function hue2rgb(p, q, t) {
        if (t < 0) t += 1;
        if (t > 1) t -= 1;
        if (t < 1 / 6) return p + (q - p) * 6 * t;
        if (t < 1 / 2) return q;
        if (t < 2 / 3) return p + (q - p) * (2 / 3 - t) * 6;
        return p;
      }

      var q = l < 0.5 ? l * (1 + s) : l + s - l * s;
      var p = 2 * l - q;
      r = hue2rgb(p, q, h + 1 / 3);
      g = hue2rgb(p, q, h);
      b = hue2rgb(p, q, h - 1 / 3);
    }

    return [Math.round(r * 255), Math.round(g * 255), Math.round(b * 255)];
  }

function rgb_to_hsl(r, g, b) {
    // from http://stackoverflow.com/questions/2353211/hsl-to-rgb-color-conversion
    r /= 255, g /= 255, b /= 255;
    var max = Math.max(r, g, b),
      min = Math.min(r, g, b);
    var h, s, l = (max + min) / 2;

    if (max == min) {
      h = s = 0; // achromatic
    } else {
      var d = max - min;
      s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
      switch (max) {
        case r:
          h = (g - b) / d + (g < b ? 6 : 0);
          break;
        case g:
          h = (b - r) / d + 2;
          break;
        case b:
          h = (r - g) / d + 4;
          break;
      }
      h /= 6;
    }

    return [h, s, l];
  }

function color_distance(v1, v2) {
  // from http://stackoverflow.com/a/13587077/1204332
  var i,
    d = 0;

  for (i = 0; i < v1.length; i++) {
    d += (v1[i] - v2[i]) * (v1[i] - v2[i]);
  }
  return Math.sqrt(d);
};

function round_to_groups(group_nr, x) {
  var divisor = 255 / group_nr;
  return Math.ceil(x / divisor) * divisor;
};

function pixel_data_to_key(pixel_data) {
  return pixel_data[0].toString() + '-' + pixel_data[1].toString() + '-' + pixel_data[2].toString();

}

function posterize(context, image_data, palette) {
  for (var i = 0; i < image_data.data.length; i += 4) {
    rgb = image_data.data.slice(i, i + 3);
    hsl = rgb_to_hsl(rgb[0], rgb[1], rgb[2]);
    key = pixel_data_to_key(hsl);
    if (key in palette) {
      new_hsl = palette[key];

      new_rgb = hsl_to_rgb(new_hsl[0], new_hsl[1], new_hsl[2]);
      rgb = hsl_to_rgb(hsl);
      image_data.data[i] = new_rgb[0];
      image_data.data[i + 1] = new_rgb[1];
      image_data.data[i + 2] = new_rgb[2];
    }
  }
  context.putImageData(image_data, 0, 0);
}


function draw(img) {


  var canvas = document.getElementById('canvas');
  var context = canvas.getContext('2d');
  context.drawImage(img, 0, 0, canvas.width, canvas.height);
  img.style.display = 'none';
  var image_data = context.getImageData(0, 0, canvas.width, canvas.height);
  var data = image_data.data;


  context.drawImage(target_image, 0, 0, canvas.width, canvas.height);
  data = context.getImageData(0, 0, canvas.width, canvas.height).data;

  original_pixels = [];
  for (i = 0; i < data.length; i += 4) {
    rgb = data.slice(i, i + 3);
    hsl = rgb_to_hsl(rgb[0], rgb[1], rgb[2]);
    original_pixels.push(hsl);
  }

  group_headers = [];
  groups = {};
  for (i = 0; i < original_pixels.length; i += 1) {
    if (group_headers.length == 0) {
      group_headers.push(original_pixels[i]);
    }
    group_found = false;
    for (j = 0; j < group_headers.length; j += 1) {
      // if a similar color was already observed
      if (color_distance(original_pixels[i], group_headers[j]) < 0.3) {
        group_found = true;
        if (!(pixel_data_to_key(original_pixels[i]) in groups)) {
          groups[pixel_data_to_key(original_pixels[i])] = group_headers[j];
        }
      }
      if (group_found) {
        break;
      }
    }
    if (!group_found) {
      if (group_headers.indexOf(original_pixels[i]) == -1) {
        group_headers.push(original_pixels[i]);
      }
      if (!(pixel_data_to_key(original_pixels[i]) in groups)) {
        groups[pixel_data_to_key(original_pixels[i])] = original_pixels[i];
      }
    }
  }
  posterize(context, image_data, groups)
}


var target_image = new Image();
target_image.crossOrigin = "";
target_image.onload = function() {
  draw(target_image)
};
target_image.src = "http://i.imgur.com/zRzdADA.jpg";

canvas {
  width: 300px;
  height: 200px;
}

<canvas id="canvas"></canvas>

Answer 2

You can use "Mean Shift Filtering" algorithm to do the same.

Here's an example.

You will have to determine function parameters heuristically.

And here's the wrapper for the same in node.js

npm Wrapper for meanshift algorithm

Hope this helps!