How to find the most dense regions in an image

Question

Consider a black and white image like this http://img13.imageshack.us/img13/7401/10416827.jpg

What I am trying to do is to find the region where the white points are most dense. In this case there are 20-21 such dense regions. (i.e the clusters of points makes a dense region)

Can anyone give me any hint on how this can be achieved ?

Answer 1

Maybe a naive approach:

You define a square of n*n which is the maximum size of the region in which you measure the density. For each point in the image you consider the point as the center of the square and count around the number of black (b) and white (w) points. Using the difference b-w you can determine in which square(s) is the most white.

The most dense regions must be determined in a fuzzy way. If one region has 600 white points and another 599 then, for the human eye, they are the same density. 600 is 100% dense while 599 is 99% dense and 1% non-dense. Use an epsilon for this.

n can be predefined or based on some function (ie. percent of image size).

You could also use a circle/ellipse instead of square/rectangle. Choose what fits your needs best

Answer 2

Sliding Window (simple but slow)

You could create a sliding window (e.g. 10x10 pixels size) which iterates over the image, and for each position you count the number of white pixels in this 10x10 field, and store the positions with the highest counts.

This whole process is O(n*m) where n is the number of pixels of the image, and m the size of the sliding window.

In other words, you convolve the image with a mean filter (here the box filter), and then use the extrema.

Sliding Window (fast)

At first, calculate a summed area table, which can be done very efficiently in a single pass:

1. create a 2D array sat with the same size as the original image img.

2. Iterate over each index, and calculate for each index x and y

   sat[x, y] = img[x, y] + sat[x-1, y] + sat[x, y-1] - sat[x-1, y-1]
   

   For example, given an image where 0 is dark and 1 is white, this is the result:

      img            sat
   0 0 0 1 0 0   0 0 0 1 1 1 
   0 0 0 1 0 0   0 0 0 2 2 2
   0 1 1 1 0 0   0 1 2 5 5 5
   0 1 0 0 0 0   0 2 3 6 6 6
   0 0 0 0 0 0   0 2 3 6 6 6
   

3. Now iterate over the summed area table's indices with a sliding window, and calculate the number of white pixels in it by using the corners A, B, C, D of the sliding window:

      img            sat          window
   0 0 0 1 0 0   0 0 0 1 1 1   0 A-----B 1 
   0 0 0 1 0 0   0 0 0 2 2 2   0 | 0 2 | 2
   0 1 1 1 0 0   0 1 2 5 5 5   0 | 2 5 | 5
   0 1 0 0 0 0   0 2 3 6 6 6   0 | 3 6 | 6
   0 0 0 0 0 0   0 2 3 6 6 6   0 D-----C 6
   

   Calculate

   density(x', y') = sat(A) + sat(C) - sat(B) - sat(D)
   

   Which in the above example is

   density(1, 0) = 0 + 6 - 1 - 2 = 3
   

This process requires a temporary image, but it is just O(n), so speed is independent of the sliding window's size.

Answer 3

if you have the image processing toolbox, blur it with a gaussian filter, then find the peaks/extrema.

vary the size of the gaussian filter to get the number of 'dense' regions you want.

Answer 4

If you have access to the Image Processing Toolbox, you can take advantage of a number of filtering and morphological operations it contains. Here's one way you could approach your problem, using the functions IMFILTER, IMCLOSE, and IMREGIONALMAX:

%# Load and plot the image data:
imageData = imread('lattice_pic.jpg');  %# Load the lattice image
subplot(221);
imshow(imageData);
title('Original image');

%# Gaussian-filter the image:
gaussFilter = fspecial('gaussian',[31 31],9);  %# Create the filter
filteredData = imfilter(imageData,gaussFilter);
subplot(222);
imshow(filteredData);
title('Gaussian-filtered image');

%# Perform a morphological close operation:
closeElement = strel('disk',31);  %# Create a disk-shaped structuring element
closedData = imclose(filteredData,closeElement);
subplot(223);
imshow(closedData);
title('Closed image');

%# Find the regions where local maxima occur:
maxImage = imregionalmax(closedData);
maxImage = imdilate(maxImage,strel('disk',5));  %# Dilate the points to see
                                                %# them better on the plot
subplot(224);
imshow(maxImage);
title('Maxima locations');

And here's the image the above code creates:

To get things to look good I just kept trying a few different combinations for the parameters for the Gaussian filter (created using FSPECIAL) and the structuring element (created using STREL). However, that little bit of trial and error gave a very nice result.

NOTE: The image returned from IMREGIONALMAX doesn't always have just single pixels set to 1 (to indicate a maxima). The output image often contains clusters of pixels because neighboring pixels in the input image can have equal values, and are therefore both counted as maxima. In the code above I also dilated these points with IMDILATE just to make them easier to see in the image, which makes an even bigger cluster of pixels centered on the maxima. If you want to reduce the cluster of pixels to a single pixel, you should remove the dilation step and modify the image in other ways (add noise to the result or filter it, then find the new maxima, etc.).