1

I am trying to implement an algorithm that detects regions in an image, i.e. starting from a seed pixel, neighboring pixels should be added to the region, highest values first.

I am looking for a data structure to serve as a queue to which the neighboring pixels can be added. It should be able to

  • index into a matrix (the image), to find the highest-value pixel
  • remove points efficiently
  • add an element, if not already present

Here is what I have come up with

% given:
% I     image (2d matrix)
% x, y  seed point

list = [];
region = zeros(size(I));

while [...]
    % Add all neighbors of (x, y) to list
    if x > 1
        % neighboring pixel to the left
        ind = sub2ind(size(I), x - 1, y);
        if length(find(list == ind)) == 0
            list(end+1) = ind;
        end
    end
    % similarly for all other neighbors
    % [...]

    % Find max in I among points in list
    [dummy, list_max_i] = max(I(list));
    max_i = list(list_max_i);
    [x, y] = ind2sub(size(I), max_i);

    % remove from list
    list(list_max_i) = [];

    region(x, y) = 1;
end

But I would like to replace list by a data structure, which is better suited for adding and removing elements. Any ideas?

ValarDohaeris
  • 6,064
  • 5
  • 31
  • 43
  • There are a few things I don't understand about your algorithm. What is the role of `region` (you seem to set it to `1` if it has a max, but never refer to it. Would you not end up stuck in a loop?). What is the point of removing `list_max_i` from the list? When does your `while` loop terminate? What values do you want to end up with? Are you trying to create a "steepest ascent" to the largest pixel value, starting from the one you used as the seed point, and maintaining the path information? A bit more info and you might get a better solution than the ones that have been suggested so far... – Floris Apr 29 '13 at 04:57
  • This code is actually inside a function, and `region` is the result, a contiguous region in an image. The list should only contain "candidates" for adding to the region, and since you don't want to keep adding the same candidate over and over again, elements have to be removed from the list, when added to the region. – ValarDohaeris Apr 29 '13 at 08:33

2 Answers2

3

How about you keep using a matrix/vector only grown in batches instead of one-by-one. This has the benefit of pre-allocation and the flexibility of dynamically expanding array. Here are two posts of interest:

Also, it looks like you are implementing a region growing algorithm. Here is a submission on FEX that uses this exact same technique of growing a matrix.

Community
  • 1
  • 1
Amro
  • 123,847
  • 25
  • 243
  • 454
  • Yes, [the FEX submission](http://www.mathworks.com/matlabcentral/fileexchange/19084-region-growing) does exactly what I was looking for, thank you! – ValarDohaeris Apr 29 '13 at 08:28
3

I think you need to re-think your approach. Instead of maintaining a list that keeps changes it size (very un-Matlabish design), why don't you keep a mask for each pixel? mask will be the same size as I initially started to zero. Then when a pixel is inserted into the list it's mask is changed to 1 and when it leaves the list it changes its value to -1. You may find the max over pixels in the list using max( I( mask == 1 ) ) and so on.
This way you only changes values in the mask, but not its size and its allocation.

What do you think?

Shai
  • 111,146
  • 38
  • 238
  • 371