Simple object recognition

Question

===SOLVED===

Thanks for your suggestions and comments. By working on the flood_fill algorithm given in Beginning Python Visualization book (Chapter 9 - Image Processing) I have implemented what I have wanted. I can count the objects, get enclosing rectangles for each object (therefore height and widths), and lastly can construct NumPy arrays or matrices for each of them.

Although it is not an optimized approach it does what I want. The source code (lab2.py) and the png file (lab2-particles.png) that I use have been put under http://code.google.com/p/ccnworks/source/browse/#svn/trunk/AtSc450.

You need NumPy and PIL installed, and matplotlib to see the histogram. Core of the code lies within the objfind function where the main recursive object search action occurs.

One further update:

SciPy's ndimage.label() does exactly what I want, too.

Cheers for David-Warde Farley and Zachary Pincus from the NumPy and SciPy mailing-lists for pointing this right into my eyes :)

=============

Hello,

I have an image that contains the shadows of ice particles measured by a particle spectrometer. I want to be able to identify each object, so that I can later classify and use them further in my calculations.

In essence, what I am willing to do is to simply implement a fuzzy selection tool where I can simply select each entity.

How could I easily solve this problem? (Preferably using Python)

Thanks.

NOTE: In my question I am referring to each specific connected pixels as objects or entities. My intention to extract them and create NumPy array representations as shown below. (Here I am using the top-left object; if a pixel exist use 1's if not use 0's. This object's shape is 3 by 3 which correspondingly 3 pixel height by 3 pixel width. These are projections of real ice-particles onto 2D domain, under the assumption of their being spherical and equivalent radius is (height+width)/2, and later some scalings --from pixels to actual sizes and volume calculations will follow)

import numpy as np

np.array([[1,1,1], [1,1,1], [0,0,1]])

array([[1, 1, 1],
       [1, 1, 1],
       [0, 0, 1]])

Here is a section from the image which I am going to use.

screenshot http://img43.imageshack.us/img43/2327/particles.png

Solution 1

1. Scan every square (e.g. from the top-left, left-to-right, top-to-bottom)

2. When you hit a blue square then:

   a. Record this square as a location of a new object

   b. Find all the other contiguous blue squares (e.g. by looking at the neighbours of this square, and the neighbours of those neighbours, etc.) and mark them as being part of the same object

3. Continue to scan

4. When you find another blue square, test to see whether it's part of a known object before going to step 2; alternatively in step 2b, erase any square after you've associated it with an object

Solution 2

Looking at the image you provided, all you need to do next is to apply a simple region growing algorithm.

If I were using MATLAB, I would use bwlabel/bwboundaries functions. I believe there's an equivalent function somewhere in Numpy, or use OpenCV with python wrappers as suggested by @kwatford

Solution 3

I used to do this kind of analysis on micrographs and eventually put everything I needed into an image processing and analysis package written in C, driven via Tcl. (It worked with 512 x 512 images only, which explains why 512 crops up so often. There were images with pixels of various sizes allocated, but most of the work was done with 8-bit pixels, which explains why there is that business of 0xff and maximum meaningful count of 254 on an image.)

Briefly, the 'zz' at the begining of the Tcl commands sends the remainder of the line to the package's parser which calls the appropriate C routine with the given arguments. Right after the 'zz' is an argument that indicates the input and output of the command. (There can be multiple inputs but only a single output.) 'r' indicates a 512 x 512 x 8-bit image. The third word is the name of the command to be invoked; 'graphs' marks up an image as described in the text below. So, 'zz rr graphs' means 'Call the ZZ parser; input an r image to the graphs command and get back an r image.' The rest of the Tcl command line specifies which of the pre-allocated images to use. (The 'g' image is an ROI, i.e., region-of-interest, image; almost all ZZ ops are done under ROI control.) So, 'r1 r1 g8' means 'Use r1 as input, use r1 as output (that is, mark up the input image itself), and do the operation wherever the corresponding pixel on image g8 --- that is, r8, used as an ROI --- is >0.

I don't think it is available online anywhere, but if you want to pick through the source code or even compile the whole shebang, I'll be happy to send it to you. Here's an excerpt from the manual (but I think I see some errors in the manual at this late date --- that's embarrassing ...):

Example 6. Counting features.

Problem

Counting is a common task. The items counted are called “features”, and it is usually necessary to prepare images carefully so that features correspond in a one-to-one way with things that are the real objects to be counted. Here, however, we ignore image preparation and consider, instead, the mechanics of counting. The first counting exercise is to find out how many features are on the images in the directory ./cells?

Approach

First, let us define “feature”. A feature is the largest group of “set” (non-zero) pixels all of which can be reached by travelling from one set pixel to another along north-south-east-west (up-down-right-left) routes, starting from a given set pixel. The zz command that detects and marks such features on an image is “zz rr graphs R:src R:dest G:ROI”, so called because the mathematical term for such a feature is a “graph”. If all the pixels on an image are set, then there is only a single graph on the image, but it contains 262144 pixels (512 * 512). If pixels are set and clear (equal to zero) in a checkerboard pattern, then there will be 131072 (512 * 512 / 2) graphs, but each will containing only one pixel. Briefly explained, “zz rr graphs” starts in the upper-left corner of an image and scans each succeeding row left to right until it finds a set pixel, then finds all the set pixels attached to that through north, south, east, or west borders (“4-connected”). It then sets all pixels in that graph to 1 (0x01). After finding and marking graph 1, it starts scanning again at the pixel after the one where it first discovered graph 1, this time ignoring any pixels that already belong to a graph. The first 254 graphs that it finds will be marked uniquely; all graphs found after that, however, will be marked with the value 255 (0xff) and so cannot be distinguished from each other. The key to being able to count any number of graphs accurately is to process each image in stages, that is, find the number of graphs on an image and, if the number is greater than 254, erase the 254 graphs just found, repeating the process until 254 or fewer graphs are found. The Tcl language provides the means to set up control of this operation.

Let us begin to build the commands needed by reading a ZZ image file into an R image and detecting and marking the graphs. Before the processing loop, we declare and zero a variable to hold the total number of features in the image series. Within the processing loop, we begin by reading the image file into an R image and detecting and marking the graphs.

zz ur to $inDir/$img r1
zz rr graphs r1 r1 g8

Next, we zero some variables to keep track of the counts, then use the “ra max” command to find out whether more than 254 graphs were detected.

set nGraphs [ zz ra max r1 a1 g1 ]

If nGraphs does equal 255, then the 254 accurately counted graphs should be added to the total, the graphs from 1 through 254 should be erased, and the count repeated for as many times as it takes to reduce the number of graphs below 255.

while {$nGraphs == 255} {
  incr sumGraphs 254
  zz rbr lt r1 155 r1 g1 0 255 
  set sumGraphs 0
  zz rr graphs r1 r1 g8
  set nGraphs [ zz ra max r1 a1 g8 ]
}

When the “while” loop exits, the variable nGraphs must hold a number less than 255, that is, a number of accurately counted graphs; this is added to the rising total of the number of features in the image series.

incr sumGraphs $nGraphs

After the processing loop, print out the total number of features found in the series.

puts “Total number of features in $inDir \
images $beginImg through $endImg is $sumGraphs.”

After the processing loop, print out the total number of features found in the series.

Solution 4

OpenCV has a Python interface that you might find useful.

Solution 5

Connected component analysis may be what you are looking for.

View more solutions

Comments

[Gökhan Sever]

I was thinking to implement something similar what you have mentioned here. Thanks for laying out clearly than I am :)

[Gökhan Sever]

Found this: opencv.willowgarage.com/documentation/python/… However somewhat confusing to me, and example isn't very helpful.

[Gökhan Sever]

SciPy package has a similar labelling function (docs.scipy.org/doc/scipy/reference/generated/…) which I could label all the pixels correctly by using it. But that only solves the first part of the problem. I should be able distinguish each entity separately. Unfortunately, there is no function for this. Needs to be written :)

[Amro]

The way I understand it, is that each blue object in the image is an entity, right? Then by labeling all pixels into regions, you just select all pixels labeled as one, then the ones labeled as two, and so on to get each object... Next step would be to extract some features for each object (boundaries, shape, area, size, ...), which would be used in a supervised classification task.

[Gökhan Sever]

With some help I wrote a simple flood_fill implementation and can count the number of objects (ice particle shadows) on the given image. And, yes it includes recursion as I expected. Now I want to be able construct simple numpy arrays representing each object. (as additionally demonstrated on my question) In the end I am thinking of appending all these arrays in to an array, where later I can simply loop over and get their shapes. Shapes are important because I will use them for height and widths of ice particle objects.

[Gökhan Sever]

I clarified my usage of entities in my question under NOTE section. For now, all I have to do is get the boundary rectangle or square for some cases width and height for each object.

[Gökhan Sever]

I knew that there must be a new for this technique :) Thanks for the pointers. Both pygraph (code.google.com/p/python-graph) and opencv with Python wrappings have some support for these algorithm, however their usage isn't very clear to me. Have you used any of those functions?

[Gökhan Sever]

This is a very lengthy answer. It will take some time to grasp your explanations :)

[behindthefall]

Note that I added para 2 as a minature intro to the package's Tcl commandline syntax. That might help your 'grasping'. BTW, there are other examples in the manual that show how to prepare images using morphological operations and then, after finding and counting the features, do things like making size distributions of them. I've never seriously tried to adapt it to Python, although it has been in my mind to do to for some time.

[behindthefall]

Also BTW: 'graphs' basically uses the algorithm from Graphics Gems, Vol.I, p.721, by Paul Heckbert.

[Gökhan Sever]

Thanks for your lengthy explanations again. I have solved the problem, and it does what I need.

[monksy]

To make this even similar [outside of matlab] all of the bw commands use the connected components algorithm.