Find random points inside binary mask

Question

Kay Raymond 2018-2-7

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/381338-find-random-points-inside-binary-mask

评论： Jan 2018-2-8

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?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2018-2-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/381338-find-random-points-inside-binary-mask#answer_303937

编辑：Jan 2018-2-8

在 MATLAB Online 中打开

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.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Kay Raymond 2018-2-8

编辑：Kay Raymond 2018-2-8

在 MATLAB Online 中打开

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.

Kay Raymond 2018-2-8

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

Thaks again.

Jan 2018-2-8

在 MATLAB Online 中打开

@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.

请先登录，再进行评论。