Grayscale segmentation/feature extraction/blob detection?

Question

I'm trying to find a starting point, but I can't seem to find the right answer. I'd be very grateful for some guidance. I also don't know the proper terminology, hence the title.

1. I took an image of a bag with a black background behind it.
2. And I want to extract the bag, similar to this.
3. And if possible, find the center, like this.

Essentially, I want to be able to extract the blob of pixels and then find the center point.

I know these are two separate questions, but I figured if someone can do the latter, then they can do the first. I am using MATLAB, but would like to write my own code and not use their image processing functions, like edge(). What methods/algorithms can I use? Any papers/links would be nice (:

Solution 1

Well, assuming that your image only consists of a black background and a bag inside it, a very common way to perform what you're asking is to threshold the image, then find the centroid of all of the white pixels.

I did a Google search and the closest thing that I can think of that matches what you want looks like this:

http://ak.picdn.net/shutterstock/videos/3455555/preview/stock-footage-single-blank-gray-shopping-bag-loop-rotate-on-black-background.jpg

This image is RGB for some reason, even though it's grayscale so we're going to convert this to grayscale. I'm assuming you can't use any built-in MATLAB functions and so rgb2gray is out. You can still implement it yourself though as rgb2gray implements the SMPTE Rec. 709 standard.

Once we read in the image, you can threshold the image and then find the centroid of all of the white pixels. That can be done using find to determine the non-zero row and column locations and then you'd just find the mean of both of them separately. Once we do that, we can show the image and plot a red circle where the centroid is located. As such:

im = imread('http://ak.picdn.net/shutterstock/videos/3455555/preview/stock-footage-single-blank-gray-shopping-bag-loop-rotate-on-black-background.jpg');
%// Convert colour image to grayscale
im = double(im);
im = 0.299*im(:,:,1) + 0.587*im(:,:,2) + 0.114*im(:,:,3);
im = uint8(im);

thresh = 30; %// Choose threshold here

%// Threshold image
im_thresh = im > thresh;

%// Find non-zero locations
[rows,cols] = find(im_thresh);

%// Find the centroid
mean_row = mean(rows);
mean_col = mean(cols);

%// Show the image and the centroid
imshow(im); hold on;
plot(mean_col, mean_row, 'r.', 'MarkerSize', 18);

When I run the above code, this is what we get:

Not bad! Now your next concern is the case of handling multiple objects. As you have intelligently determined, this code only detects one object. For the case of multiple objects, we're going to have to do something different. What you need to do is identify all of the objects in the image by an ID. This means that we need to create a matrix of IDs where each pixel in this matrix denotes which object the object belongs to. After, we iterate through each object ID and find each centroid. This is performed by creating a mask for each ID, finding the centroid of that mask and saving this result. This is what is known as finding the connected components.

regionprops is the most common way to do this in MATLAB, but as you want to implement this yourself, I will defer you to my post I wrote a while ago on how to find the connected components of a binary image:

How to find all connected components in a binary image in Matlab?

Mind you, that algorithm is not the most efficient one so it may take a few seconds, but I'm sure you don't mind the wait :) So let's deal with the case of multiple objects now. I also found this image on Google:

We'd threshold the image as normal, then what's going to be different is performing a connected components analysis, then we iterate through each label and find the centroid. However, an additional constraint that I'm going to enforce is that we're going to check the area of each object found in the connected components result. If it's less than some number, this means that the object is probably attributed to quantization noise and we should skip this result.

Therefore, assuming that you took the code in the above linked post and placed it into a function called conncomptest which has the following prototype:

B = conncomptest(A);

So, take the code in the referenced post, and place it into a function called conncomptest.m with a function header such that:

function B = conncomptest(A)

where A is the input binary image and B is the matrix of IDs, you would do something like this:

im = imread('http://cdn.c.photoshelter.com/img-get2/I0000dqEHPhmGs.w/fit=1000x750/84483552.jpg');

im = double(im);
im = 0.299*im(:,:,1) + 0.587*im(:,:,2) + 0.114*im(:,:,3);
im = uint8(im);

thresh = 30; %// Choose threshold here

%// Threshold image
im_thresh = im > thresh;

%// Perform connected components analysis
labels = conncomptest(im_thresh);

%// Find the total number of objects in the image
num_labels = max(labels(:));

%// Find centroids of each object and show the image
figure;
imshow(im);
hold on;

for idx = 1 : num_labels
    %// Find the ith object mask
    mask = labels == idx;

    %// Find the area
    arr = sum(mask(:));

    %// If area is less than a threshold
    %// don't process this object
    if arr < 50
        continue;
    end

    %// Else, find the centroid normally
    %// Find non-zero locations
    [rows,cols] = find(mask);

    %// Find the centroid
    mean_row = mean(rows);
    mean_col = mean(cols);

    %// Show the image and the centroid
    plot(mean_col, mean_row, 'r.', 'MarkerSize', 18);
end

We get:

Solution 2

I have no intention of detracting from Ray's (@rayryeng) excellent advice and, as usual, beautifully crafted, reasoned and illustrated answer, however I note that you are interested in solutions other than Matlab and actually want to develop your own code, so I though I would provide some additional options for you.

You could look to the excellent ImageMagick, which is installed in most Linux distros and available for OS X, other good operating systems and Windows. It includes a "Connected Components" method and if you apply it to this image:

like this at the command-line:

convert bags.png -threshold 20%                     \
  -define connected-components:verbose=true         \
  -define connected-components:area-threshold=600   \
  -connected-components 8 -auto-level output.png

The output will be:

  Objects (id: bounding-box centroid area mean-color):
  2: 630x473+0+0 309.0,252.9 195140 srgb(0,0,0)
  1: 248x220+0+0 131.8,105.5 40559 srgb(249,249,249)
  7: 299x231+328+186 507.5,304.8 36620 srgb(254,254,254)
  3: 140x171+403+0 458.0,80.2 13671 srgb(253,253,253)
  12: 125x150+206+323 259.8,382.4 10940 srgb(253,253,253)
  8: 40x50+339+221 357.0,248.0 1060 srgb(0,0,0)

which shows 6 objects, one per line, and gives the bounding boxes, centroids and mean-colour of each. So, the 3rd line means a box 299 pixels wide by 231 pixels tall, with its top-left corner at 328 across from the top-left of the image and 186 pixels down from the top-left corner.

If I draw in the bounding boxes, you can see them here:

The centroids are also listed for you.

The outout image from the command above is like this, showing each shape shaded in a different shade of grey. Note that the darkest one has come up black so is VERY hard to see - nearly impossible :-)

If, as you say, you wish to look at writing your own connected component code, you could look at my code in another answer of mine... here

Anyway, I hope this helps and you see it just as an addition to the excellent answer Ray has already provided.

Comments

[BadProgrammer]

Dude that's awesome!! What if there are multiple objects in the image? For example, 2 bags. By doing find over the whole image, you only get one centroid correct? If I wanted to find a centroid of each bag how can I go about doing that? Also, I don't mind using some of the built in functions like rgb2gray(), I just didn't want the feature extraction portion to be a single MATLAB function.

[rayryeng]

@BadProgrammer - Thanks :) Ah yes. Well a common practice is to perform connected components analysis and iterate through each distinct object and find its centroids. Can you use regionprops? I'd also extend this a bit further with morphology. Can you use things like imfill? imclose?

[BadProgrammer]

I can technically use any of the functions. I just like to be able to right my own when possible because it helps me understand what is going on. I guess if I had the examples with the MATLAB functions, I can figure out how the algorithms work and then write my own later.

[rayryeng]

@BadProgrammer - OK. I'll just assume that you can't use anything lol. I wrote a post on Connected Components from first principles a while ago and I'll defer you to there for the algorithm and the code. I'll update my post for multiple objects

[rayryeng]

@BadProgrammer - Updated. Have a look!

[BadProgrammer]

Seriously, the best answer I have ever gotten to anything. EVER.

[BadProgrammer]

Thanks Mark! That's also a great method that I will mess with. I'm tagging @rayreng in this because I have an additional question and I would be grateful if one of you could possibly answer. My overall goal was to track the bags/blobs and match them through frames as the camera moves. Here are my current results: link. You can see the features moving through the frames and I want to track that distance change between the frames. However, since the center point changes when the object leaves the field of view, will this method work? Should I use another?

[rayryeng]

ehhhhhh - Go ImageMagick!

[rayryeng]

@BadProgrammer - I didn't realize that what you were performing is an object tracking. No, this method won't work if any of the objects leave your view and then re-enter. You'll need to add in additional information about the blobs in order for the tracking to restart once it enters the view. As you said, the object moving out of the frame and re-entering will provide ambiguous information because you don't know what object that centroid belongs to if you're just looking at the centroid themselves. I would recommend you look at object tracking algorithms on top of the centroid detection.

[Mark Setchell]

You could possibly consider adding the area and/or the colour of the objects in order to help re-associating them with their former selves when they leave and re-enter the frame.