2
$\begingroup$

How an algorithm can be developed to count numbers and bolts in the image below.

enter image description here

$\endgroup$
  • $\begingroup$ possible duplicate of How to compute regions of matrix $\endgroup$ – nidhin Jul 13 '14 at 19:16
  • 1
    $\begingroup$ @nidhin - This is not an exact duplicate. You need to do some pre-processing to the image first before being able to represent the image into binary. $\endgroup$ – rayryeng Jul 14 '14 at 4:53
  • $\begingroup$ It gives an error that Error using - Matrix dimensions must agree. Error in check dists = sqrt((cols - centroidX ).^2 + (rows - centroidY).^2); how to resolve it? $\endgroup$ – user17345 Sep 11 '15 at 20:58
4
$\begingroup$

I will be using MATLAB as part of my solution. The basic algorithm will be this:

  1. Read in the image and convert to black and white
  2. Invert the intensities and fill in the holes. There are speckles in the image where when you convert the image to black and white, the objects are not solid. We want to ensure these are solid
  3. Count how many unique objects there are using bwlabel.

You'll need the Image Processing Toolbox for this algorithm. If you don't have this and are using MATLAB, let me know and I'll edit my post.


Without further ado:

% Read in image, convert to black and white - Link comes from your image posted here
im = imread('http://i.stack.imgur.com/lBGU1.png');
imBW = im2bw(im, 0.3); %// Specify manual threshold of 0.3

% Invert intensities and fill in holes
imBWFilled = imfill(~imBW, 'holes');

% Count how many unique objects there are
[L,num] = bwlabel(imBWFilled);

% Show final image and display number of objects counted in the title
imshow(imBWFilled);
title(['Total number of objects: ' num2str(num)]);

L contains a map where each pixel is an ID of which object that belongs to. 0 means that the pixel belongs to the background while any pixel that has values greater than or equal to 1 means that the pixel belongs to a particular object associated with that ID number. num gives you the total number of objects seen in the image. The output of this code thus gives:

enter image description here


If you don't have MATLAB and want to compute this using another language, let me know. You can find the number of objects by considering an image as a connected graph. If you don't have bwlabel, you can use any graph searching algorithm (breadth-first search, depth-first search, etc.) to help you compute this. Start with any pixel that belongs to an object, and perform BFS / DFS to visit those pixels that belong to the object. You then set all of these pixels to belong to an ID number. When the queue / stack is empty, you then select another pixel that belongs to an object and repeat the algorithm. You stop when you have visited all pixels that belong to objects. The total number of IDs you have issued will essentially be how many unique objects you have in your image.


Edit - July 14th, 2014

Seeing your comments, you wish to be able to distinguish between what is a nut and what is a bolt. As such, we can simply add on top of the current code. The algorithm that I have developed is loosely based on circularity:

  1. For each object, find the centre of mass. This is simply taking all of the X and Y co-ordinates and averaging them.
  2. For each object, find their boundaries / perimeters
  3. For each centre of mass we have, calculate the distance between this point and all of the object boundary points.
  4. Find the difference between the maximum and minimum of these distances - denote this the range
  5. We will have N ranges for N objects. Simply take a look at these ranges and threshold the array. If you take a look at the bolts, they have a longer vertical direction than horizontal direction. For the bolts, the vertical and horizontal direction is pretty much the same. As such, the range should give us an idea of what is a nut and bolt because the difference between the maximum distance to the centre and the minimum distances should be very large in comparison to the nut. As such, for each object we have, check to see if the range is below a certain value (nut) or above a certain value (bolt).

Without further ado, here is the code:

%%% For each object in the image, find the centre of mass
centres = zeros(num,2);
% Cycle through each unique object label and extract (X,Y) co-ordinates
% that belong to each object.  Compute centre of mass for each.
for n = 1 : num
    bmap = L == n;
    [rows,cols] = find(bmap == 1);
    centres(n,:) = [mean(cols) mean(rows)];
end

% Find boundaries of all objects
bwBound = bwperim(imBWFilled, 8);

% For each object, find the distances between the centre of mass with all
% of the pixels along the boundary for each object.  Find the range (max -
% min).
ranges = zeros(num,1);
for n = 1 : num
    bmap = L == n; % Obtain all pixels for an object
    boundPix = bwBound & bmap; % Logical AND with boundaries map to extract
                               % only those pixels around the perimeter
    [rows,cols] = find(boundPix == 1); % Find these locations
    % Compute the distances between the centre of mass with these points
    dists = sqrt((cols - centres(n,1)).^2 + (rows - centres(n,2)).^2);

    % Find the difference between the maximum and minimum distances
    ranges(n) = max(dists(:)) - min(dists(:));
end

This isn't complete yet. I stopped here so you can see what the ranges for all of the objects look like:

ranges =

37.9615
63.9613
54.9266
 5.0716
 4.1578
 6.3114
 7.2356
41.6381
10.3123
34.0938
 5.0021
67.3290

As you can see, there are some ranges that are quite small ($< 10$) while there are some ranges that are large. To be safe, let's choose a threshold of 15. As such, for those ranges that are less than 15, this is classified as a nut while those that are larger are classified as a bolt. When we're done, we simply count how many of these fall within each range, and those are the number of nuts and bolts we have. Let's continue with the algorithm:

% Find those object IDs that have less than a range of 15.  These are the
% bolts
% The rest are nuts
indBolts = find(ranges < 15);
indNuts =  find(ranges >= 15);

% Total number of nuts and bolts
numBolts = numel(indBolts);
numNuts = numel(indNuts);

This will give you 6 and 6 respectively as you expected. Now to finish up the algorithm, I'm going to give you an added bonus. For each unique object we have, I'm going to colour their interiors to be a certain shade of gray. The background will be black, while a nut is gray and a bolt is white. The code to do this is:

finalMap = uint8(zeros(size(imBW)));

for n = 1 : numBolts
    finalMap(L == indBolts(n)) = 128;
end
for n = 1 : numNuts
    finalMap(L == indNuts(n)) = 255;
end

figure;
imshow(finalMap);
title(['Number of Nuts: ' num2str(numNuts) ', Number of Bolts: ' num2str(numBolts)]);

The final image we get is:

enter image description here

$\endgroup$
  • $\begingroup$ Here i want to count the number nuts and bolts separately. (Ex Nuts -: 6, Bolts :- 6) $\endgroup$ – Zonik Jul 14 '14 at 11:46
  • 1
    $\begingroup$ I would do a check on circularity to separate bolts and nuts although lots of other methods could be used. $\endgroup$ – nivag Jul 14 '14 at 12:21
  • 1
    $\begingroup$ @Zonik - I agree with nivag's method. However, I'm not going to do that for you because you haven't tried anything on your own yet. What I would do is compute the location of the centre of mass for each object, and find the range between the distance between this point and the points around the objects. You'll see that the range will be higher for the bolts than they are for the nuts. You can perhaps threshold these ranges to figure this out. $\endgroup$ – rayryeng Jul 14 '14 at 13:51
  • $\begingroup$ @rayryeng - Thank you so much for the comments. Really appreciate it. I just want to find out a correct path to perform it. Now i think i have what i wanted. Thank you so much!!! $\endgroup$ – Zonik Jul 14 '14 at 15:00
  • $\begingroup$ @Zonik - I wrote a solution for you anyway :) Let me update my post. $\endgroup$ – rayryeng Jul 14 '14 at 15:03
2
$\begingroup$

Let me give a solution in Mathematica, for good measure. Like Ray, I simply binarized the image, then counted the number of connected, filled components:

img = Import["http://i.stack.imgur.com/lBGU1.png"]
ComponentMeasurements[ColorNegate@Binarize@img, "FilledCount"]

The output is:

{1 -> 5779, 2 -> 3426, 3 -> 3433, 4 -> 4716, 5 -> 6680, 6 -> 4294, 
 7 -> 1734, 8 -> 5807, 9 -> 3406, 10 -> 6345, 11 -> 3371, 12 -> 2696}

If you want to count the nuts and bolts separately, we can leverage the fact that the genus of the two object types is different: 0 for the bolts, and 1 for the nuts.

ComponentMeasurements[ColorNegate@Binarize@Opening[img, 2], "Holes"]

Opening is to smooth over the tiny holes caused by compression noise. The output is:

{1 -> 0, 2 -> 1, 3 -> 1, 4 -> 0, 5 -> 0, 6 -> 0, 7 -> 1, 8 -> 1, 
 9 -> 1, 10 -> 0, 11 -> 1, 12 -> 0}

We can easily collate like items using Last /@ % // BinCounts. This simply takes the last item (i.e., the genus) of each element in the previous result, and bins them. The final answer is {0, 6, 6}; six bolts and six nuts.

$\endgroup$
  • $\begingroup$ Mathematica is so cool and powerful for prototyping, shame it's very rarely used in Engineering. $\endgroup$ – jojek Jul 14 '14 at 7:25
  • $\begingroup$ @Emre - Nice solution! I've always wanted to use and learn Mathematica. Probably should start learning now! +1 from me $\endgroup$ – rayryeng Jul 14 '14 at 7:40
  • 1
    $\begingroup$ @jojek - I agree. However, Mathematica has very elegant Image Processing algorithms from what I've seen. Actually, there's a very cool post on StackOverflow on finding Waldo in images using Mathematica. Cool read! stackoverflow.com/questions/8479058/… $\endgroup$ – rayryeng Jul 14 '14 at 7:43
1
$\begingroup$

Binarize the image and perform connected components analysis.

You will find 12 objects. Select those with a hole.

To avoid spurious tiny holes due to the texture, remove these with a 3x3 erosion (or opening) step before binarization.

enter image description here

$\endgroup$
  • $\begingroup$ Same solution as @emre $\endgroup$ – Yves Daoust Sep 11 '15 at 22:11

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.