Find random points inside binary mask

I am extracting random tiles from huge binary image masks. I do this by finding the random upper left corner of the tiles as shown below. And then check if enough of the tile is inside the mask. But I have some memory issues.

[y_cord, x_cord] = find(mask);         % Find all xy-pairs inside mask
xy_rand = randperm(length(x_cord), 1e4);     % Select 1e4 random xy-pairs

This works fine for most of my masks, but when the masks are getting really big I'm running out of memory. As an example: one of the masks ( 48500x63000 logical) result in x_cord and y_cord having the dim 11e9 x 1, which is more than my machine can handle.

Any ideas on how to solve this more memory efficient?

Answer 1

[Jan]

Using the linear index needs the half of the memory:

index  = find(mask);
select = index(randperm(length(index), 1e4));
[y, x] = ind2sub(size(mask), select);

Another approach:

n = sum(mask(:));
v = false(1, n);
s = randperm(n, 1e4);
v(s)  = true;
mask2 = false(size(mask));
mask2(mask) = v;
[y_cord, x_cord] = find(mask2);

This uses the mask as logical mask to create a new mask with 1e4 true elements.

The problem would be leaner in a loop:

% !!! UNTESTED !!!
idx  = zeros(1, 1e4);

n  = sum(mask(:));            % Number of all TRUE elements
s  = sort(randperm(n, 1e4));  % Select 1e4 of them
si = 1;                       % index related to s
c  = 0;                       % Counter of found TRUE elements
for k = 1:numel(mask)
  if mask(k)                  % If element is TRUE
    c = c + 1;                % Increase the counter
    if c == s(si)             % If counter equals current s
      idx(si) = k;            % Remember this linear index
      si      = si + 1;       % Proceed to the next s
      if si > length(s)       % Break if 1e4 elements are found
        break;
      end
    end
  end
end

[y, x] = ind2sub(size(mask), idx);

This would be very fast as C-Mex function and it does not use any temporary memory.

[Kay Raymond]

Thanks for the answer. I've run some tests with your alternatives. All of them works fine on my computer (16gb memory), but there is some differences in computing time.

(Edit: alternative 3 wont generate random points. All points are clustered in one area).

Alternative 1:

%%Alternative 1
clear x y
tic
idx = find(mask);
selct = idx(randperm(length(idx), 1e6));
clear idx
[y, x] = ind2sub(size(mask), selct);
clear selct
toc

>>Elapsed time is 18.301527 seconds.

Alternative 2:

%%Alternative 2
clear x y
tic
n = sum(mask(:));
v = false(1, n);
s = randperm(n, 1e6);
v(s)  = true;
mask2 = false(size(mask));
mask2(mask) = v;
[y, x] = find(mask2);
clear n v s mask2
toc

>>Elapsed time is 56.523265 seconds.

Alternative 3:

%%Alternative 3
clear x y
tic
idx  = zeros(1, 1e6);
idxi = 1;
n  = sum(mask(:));            % Number of all TRUE elements
s  = sort(randperm(n, 1e6));  % Select 1e4 of them
si = 1;                       % index related to s
c  = 0;                       % Counter of found TRUE elements
for k = 1:numel(mask)
  if mask(k)                  % If element is TRUE
    c = c + 1;                % Increase the counter
    if c == s(si)             % If counter equals current s
      idx(idxi) = k;          % Remember this linear index
      idxi      = idxi + 1;   
      si        = si + 1;     % Proceed to the next s
      if si > length(s)       % Break if 1e4 elements are found
        break;
      end
    end
  end
end
[y, x] = ind2sub(size(mask), idx);
clear c s idx idxi k n si
toc

>>Elapsed time is 18.917770 seconds.

[Jan]

 alternative 3 wont generate random points. All points are
 clustered in one area

I'll check this when I can access Matlab.

[Kay Raymond]

No worries. I went for alternative 1. It helped me alot :)

Thaks again.

[Jan]

@Kay: I'm eager to implement this in C, because I needed a "nested logical indexing" multiple times by my own also. The job is easy, but does not match to Matlab's vectorized methods.

X     = rand(huge, giant);
mask  = logical(X < 0.5);
mask2 = 1:1000:nnz(mask);   % Every 1000th selected element

Y = X(mask);   % Very large temporary array
Z = Y(mask2);  % Small result

Here it would be useful, if mask and mask2 could be "linked" at first. mask2 could be a linear index vector or another logical mask.

I was astonished, that even the logical indexing can be accelerated compared to the built-in methods: FEX: CopyMask. Then a "linked masking" might be nice.