Building a map from a matrix in Matlab

Question

I have a matrix A which holds integers in a bounded range (0..255) and I need to build a table mapping a value (0..255) to all the coordinates in the matrix which hold this value.

What is the best way to achieve this? - I thought about using containers.Map for the task but Map doesn't support multiple values per key. I could have used lists but that would seem inefficient as I would have to create a new list on each iteration.

Answer 1

What about using a cell array? You can index it with integers. For example:

map = {[1,1;13,56], [], [4,5]};

In this example index 0 is in the matrix in 1,1 and 13,56, index 1 in none and index 2 in 4,5

Your cell would have 256 elements (mine has 3) and to acces you would simply add 1 to the index.

You could also store indices linearly so the code to fill the table would be:

for ii = 0:255
    map{ii+1} = find( mat(:)==ii )
end

Answer 2

Well, I wrote the following and it seems to work in reasonable time. I think the thing that does the trick is preallocating the cell arrays based on the histogram for each value:

[H, W] = size(A);
histogram = hist(A, 256);
AGT = arrayfun(@(avg) {0 cell(1, histogram(avg))}, 1:256, 'UniformOutput', false);
for y = 1:H
    for x = 1:W
        idx = A(y, x) + 1;
        count = AGT{idx}{1};
        AGT{idx}{2}{count + 1} =  [y x];
        AGT{idx}{1} = count + 1;
    end
end

Accessing the table is a bit annoyting though :

AGT{200}{2}{:}

to access all coordinates with value 200.

Answer 3

A vectorized solution, which gives the same output as the solution from Mikhail, is to sort all the pixel values in your image using the SORT function, convert the linear indices returned from SORT into subscripted indices using the function IND2SUB, and collect them together into a single cell array using the functions ACCUMARRAY and MAT2CELL:

A = randi([0 255],[5 5],'uint8');         %# A sample matrix
[values,indices] = sort(double(A(:)));    %# Sort all the pixel values
[y,x] = ind2sub(size(A),indices);         %# Convert linear index to subscript
counts = accumarray(values+1,1,[256 1]);  %# Count number of each value
map = mat2cell([y x],counts);             %# Create a 256-by-1 cell array

Now, for a given integer value iValue you can get the N-by-2 matrix containing the y (first column) and x (second column) coordinates for the N pixels in the image with that value by doing the following:

key = double(iValue)+1;  %# Need to use double to avoid integer saturation
points = map{key};       %# An N-by-2 coordinate matrix

In addition, just in case you're interested, you could also make map a structure array with fields x and y using the function STRUCT:

map = struct('x',mat2cell(x,counts),'y',mat2cell(y,counts));

And you can then access the x and y coordinates for pixels with a value iValue as follows:

key = double(iValue)+1;
x = map(key).x;
y = map(key).y