R: Count objects in a picture

Question

I am currently working on a problem where I build a classifier using pictures to predict an outcome. Basically, I have objects on a picture (one or several), and I want to identify them. As I can have one object or several of them (not always identical), I first would like to be able to count how many objects are present on my picture. I don't want to run any machine learning algorithm and I'd like to have some way of doing it as fast as possible.

Running a k-means (using color) enables me to separate the picture in 2 color groups which gives already a pretty good separation between background and objects. From this picture I'd like to find a way to count all the different "regions". I tried to run a k-means using both color and positions to try to do all in one step but it does not work out very well since adding positions to the kmeans degrades its result.

Here is an example of what the picture would like, once having separated it in two color regions with the kmeans:

Obviously there are 5 objects and one background here. Or, alternatively, 6 distinctive regions.

What I would like to do is run an algorithm on that picture that would tell me that number. I am not familiar with image processing so I cannot think of a fast and efficient way of doing it. One solution I would think of would be to take a pixel from the objects class and test if the neighbouring pixels belong to the same class or are actually part of the background class. But this would be a painfully long way of doing things.

I have tried blob recognition but it does not look like this algorithm is suited for what I need.

I would be quite interested in knowing how to do that kind of problem. I don't mind having to code the algorithm myself but I'm also interested in knowing if there are R packages that enables this kind of thing easily.

I hope everything is clear enough. Thank you a lot in advance!

Answer 1

Update Found a link to an implementation of bwlabel in the R image processing toolbox. So the following is probably not necessary, but it was fun to create :-) You should take a look at that package as it has other object segmentation algorithms (i.e., watershed) that may be better than your first step of k-means clustering.

If your segmentation is correctly labeling between background and object with at least one background pixel separating the boundaries between distinct objects, then you would want to implement matlab's bwlabel function in R. For an explanation of that see this SO question/answer

Below is an implementation that does not perform labeling (although it can be easily adopted to do so):

find.contiguous <- function(img, x, bg) {
  ## we need to deal with a single (row,col) matrix index
  ## versus a collection of them in a two column matrix separately.
  if (length(x) > 2) {
    lbl <- img[x][1]
    img[x] <- bg
    xc <- x[,1]
    yc <- x[,2]
  } else {
    lbl <- img[x[1],x[2]]
    img[x[1],x[2]] <- bg
    xc <- x[1]
    yc <- x[2]
  }    
  ## find all neighbors of x
  x <- rbind(cbind(xc-1, yc-1),
             cbind(xc  , yc-1),
             cbind(xc+1, yc-1),
             cbind(xc-1, yc),
             cbind(xc+1, yc),
             cbind(xc-1, yc+1),
             cbind(xc  , yc+1),
             cbind(xc+1, yc+1))
  ## that have the same label as the original x
  x <- x[img[x] == lbl,]
  ## if there is none, we stop and return the updated image
  if (length(x)==0) return(img);
  ## otherwise, we call this function recursively
  find.contiguous(img,x,bg)
}

find.contiguous is a recursive function in which for each call it receives:

1. A working copy of the image img.
2. A collection of pixel (matrix) indices x (row,col) that belong to an object in the image img.
3. The background value bg

find.contiguous then proceeds to:

1. Set all pixels at x in img to the bg color. This marks that we have visited the pixels.
2. Find all neighboring pixels of x that have the same label (value) as that in x. This grows the region of the same object. Note that since x is not necessarily a single pixel, x grows geometrically so that, in fact, this function is no slouch.
3. If there are no more neighbors belonging to the same object, we return the updated image; otherwise, we make the recursive call.

Starting from a single pixel that correspond to an object, a call to find.contiguous will grow the region to include all the object's pixels and return an updated image where the object is replaced by the background. This process can then be repeated in a loop until there are no more objects in the image, hence the ability to generate a count.

To illustrate, I assume that your binary image is a matrix named img:

## set the background pixel value
bg <- 0
## set the object pixel value
obj <- 1

## pad image so that the edge is background, this is necessary because 
## the neighborhood generated in find.contiguous must lie strictly within 
## the image
tmp <- matrix(bg,nrow=nrow(img)+2,ncol=ncol(img)+2)
tmp[2:(nrow(img)+1),2:(ncol(img)+1)] <- img
img <- tmp

## initialize the count to zero
count <- 0
## get all pixel coordinates that are objects
x <- which(img==obj, arr.ind=TRUE)
## loop until there are no more pixels that are objects
while (length(x) > 0) {
  ## choose a single (e.g., first) pixel location. This belongs to the current
  ## object that we will grow and remove from the image using find.contiguous
  if (length(x) > 2) {
    x <- x[1,]
  }
  ## increment the count
  count <- count + 1
  ## make the call to remove the object from img
  img <- find.contiguous(img, x, bg)
  ## find the remaining pixel locations belonging to objects
  x <- which(img==obj, arr.ind=TRUE)
}

Your answer is in count. Running this on a sample data from the previous link:

img <- as.matrix(read.table(text="
0  0  0  0  0  1  1  1  0  0 
0  1  0  1  0  0  1  1  0  0
0  1  1  1  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  1
0  0  0  0  0  0  0  0  1  1
0  0  1  1  1  1  0  0  1  1", header=FALSE))

we get:

print(paste("number of objects: ",count))
##[1] "number of objects:  4"

Answer 2

I am not an expert in picture recognition - so my approach might fail. If your contrast is that good and all rectangles are aligned horizontally, you could perhaps try the following:

• Find the boundaries - reduce to 1D: Build the gradient of the picture and take the points with a gradient above a certain threshold (Hopefully this gives the "boundary line" of all rectangles)
• Get the 4 corners: Pic one point randomly. Take a small step size delta and find the neigbours (There should be 2 - the "previous neigbbour is not allowed => Always go in the same direction). Track the change in x and y at the same time. Iterate that procedure until you get back to the first). The points where x or y change belong to the corners.
• Reconstruct rectangle: Fit the points between the corners with a line (Exculde area of stepsize delta) from corners. Restrict the lines to the space between two corners.
• Remove the found rectangle: If the fit is good enough (e.g. r squared), delete all points in data which are close to your fit - nothing should remain from the previously found rectangle and you you can increase the number of found rectangles.
• Iterate the above until data is empthy.

If that works, you also have the centers of the rectangles. I hope that helps...