5
$\begingroup$

When working with integer label matrices returned by such functions as MorphologicalComponents, ImageForestingComponents etc. it is often necessary to replace a certain label (or a list of labels) with other label(s) without unpacking the matrix. The immediately obvious solutions via Replace/ReplaceAll or via Position unpack packed arrays and for this reason aren't appropriate.

I can imagine writing a Do loop and performing in-place modification of the matrix using Part but it is ugly and expectedly slow (although it is memory-efficient because it won't create a copy of the original matrix). Probably compilation can help with the performance, but I'm sure there must be simpler way to perform such a basic operation without unpacking the matrix.

The question is: what is the best way to replace a list of values in a packed array of integers with other integer values while keeping the array packed?


Here is a couple of examples:

  1. Setting the largest component to be background:

    img = Import["http://i.stack.imgur.com/2a2j6.png"];
    cellM = MorphologicalComponents[ColorNegate@img, CornerNeighbors -> False];
    largest = SortBy[ComponentMeasurements[cellM, "Area"], Last][[-1, 1]];
    (*the obvious solution: inefficient and unpacks*)
    cellM2 = cellM /. largest -> 0;
    cellM2 // Colorize
    
  2. Shifting indices of all the components except the background (0) by a constant value (motivation: combining two label matrices):

    (*the obvious solution: inefficient and unpacks*)
    cellM3 = cellM /. i_Integer /; i != 0 :> i + 10000;
    cellM3 // Colorize
    

Answers to questions in the comments (now deleted):

  • From my little experience, the most usual needs are split into the two cases shown above:

    1. a very few (usually only one) values need to be replaced;

    2. all the values excepting a very few (usually only one) need to be replaced.

  • Since the obtained label matrices are intended for further processing with ComponentMeasurements, SelectComponents etc. it is highly desirable to keep them packed just for achieving decent timings. But from the other side, it is very easy to hit the memory limit of a usual laptop (or even PC) just keeping in the memory 2-3 unpacked label matrices of the usual size of modern photos (for example, about 2000×1200 pixels) during image processing.

$\endgroup$
  • $\begingroup$ I just have found that Map won't unpack if the function is both pure and compilable at the same time, so one simple solution is Map[If[# == 1, 2, #] &, RandomInteger[{0, 10}, {100, 100}], {2}]. But I'll wait for more complete/potentially better answer(s). $\endgroup$ – Alexey Popkov Jun 11 '17 at 5:52
  • 1
    $\begingroup$ Map[Switch[..., Map[If[..., Map[Piecewise[... all seem to work. I'm curious if there are more readable/faster alternatives $\endgroup$ – Niki Estner Jun 11 '17 at 6:57
  • 1
    $\begingroup$ Related: (2822), (9719), (48805) $\endgroup$ – Mr.Wizard Jun 11 '17 at 7:08
  • 2
    $\begingroup$ ((1 - Unitize[#1 - #2])*(#3 - #2) + #1) &[mat, 1, 2] s/b quick... $\endgroup$ – ciao Jun 11 '17 at 7:38
  • 1
    $\begingroup$ @Alexey That code takes ~0.097 second on my machine, slower than cellM /. largest -> 0. Perhaps surprisingly nearly all the time is spent in ColorReplace itself; Image and ImageData are insignificant. Another slow built-in. :-/ $\endgroup$ – Mr.Wizard Jun 12 '17 at 7:16
5
$\begingroup$

Using the method I showed for directly change the background value of a SparseArray? we can efficiently replace the Background of a SparseArray. Conversion to sparse allows specification of the background. Therefore one replacement method is:

fn1[array_?ArrayQ, old_, new_] :=
  SparseArray[array, Automatic, old] /.
    (sa : SparseArray)[a_, b_, _, d_] :> sa[a, b, new, d]

However this does not achieve the goal of keeping the array packed.

Better appears to be the numeric approach that I alluded to in my Related: links and which ciao posted in a comment. With a tweak or two of my own:

fn2[a_?ArrayQ, old_, new_] := BitXor[1, Unitize[a - old]] (new - old) + a;

Test:

(* cellM from Question example data *)

(r0 = cellM /. largest -> 0); // RepeatedTiming
(r1 = fn1[cellM, 2, 0]);      // RepeatedTiming
(r2 = fn2[cellM, 2, 0]);      // RepeatedTiming

r0 == r1 == r2
{0.0620, Null}

{0.00557, Null}

{0.00499, Null}

True

r1 is a SparseArray; conversion overhead is modest:

Developer`ToPackedArray @ Normal @ r1; // RepeatedTiming
{0.0014, Null}

The second operation is easily recast in terms this one, e.g.

(s0 = cellM /. i_Integer /; i != 0 :> i + 10000); // RepeatedTiming

(s2 = fn2[cellM + 10000, 10000, 0]);              // RepeatedTiming

s0 == s2
{0.3270, Null}

{0.00621, Null}

True

With the syntax change requested and extension to multiple replacements by repeated application:

rep[
  a_ /; MatrixQ[a, IntegerQ],
  {rls__} | rls_ /; MatchQ[{rls}, {(_Integer -> _Integer) ..}]
] :=
  Fold[BitXor[1, Unitize[# - #2[[1]]]] (#2[[2]] - #2[[1]]) + # &, a, {rls}]
$\endgroup$
  • $\begingroup$ @Alexey I know of nothing better than to Fold over the rules. I'll continue to think about this problem but for now I'll make the requested changes. $\endgroup$ – Mr.Wizard Jun 13 '17 at 7:01
3
$\begingroup$

In my first answer I attempted to provide general methods that could be applied to an arbitrary integer matrix. However for the example given there is a much different approach.

cellM has a particular content:

Union @@ cellM == Range[0, 46]   (* True *)

We can therefore make multiple replacements like this:

set = Range[0, 46];
set[[1 + {2, 7, 9, 14, 22}]] = 0;

r1 = set[[# + 1]] & /@ cellM; // RepeatedTiming
{0.00420, Null}

Compared to rep from the bottom of my first answer:

r2 = rep[cellM, Thread[{2, 7, 9, 14, 22} -> 0]]; // RepeatedTiming

r1 === r2
{0.026, Null}

The example above replaces multiple values with the same value (zero) but the method will work just as well with unique values, e.g.:

set = Range[0, 46];
set[[1 + {2, 7, 9, 14, 22}]] = Range[5];

(set[[# + 1]] & /@ cellM) === 
   rep[cellM, Thread[{2, 7, 9, 14, 22} -> Range[5]]]
True

This method can be applied to any array containing integers falling into a known range which is fairly small. (Different offsets may be needed to avoid non-positive values.)

Actually the range of integers is not so important, rather the total number of unique values. We would essentially be working in "indexed color" i.e. our array is filled with index values 1 .. 256 but these may represent a sampling of a much larger space. I don't know if this kind of functionality already exists in Mathematica, but I intend to explore it later.

$\endgroup$
  • $\begingroup$ Wow, this is so simple and elegant! And the speed gain is impressive! (+1) $\endgroup$ – Alexey Popkov Jun 13 '17 at 8:31
  • $\begingroup$ "... rather the total number of unique values" - probably you mean the range of unique values? For example, if we have only two unique values: 1 and 10^6, we still have to create an array with 10^6 numbers what will slow down the method substantially. $\endgroup$ – Alexey Popkov Jun 13 '17 at 8:34
  • $\begingroup$ @Alexey No, what I am alluding to in my last paragraph is the idea of keeping the data and the values separate. We would have something like idx = {{1, 2}, {1, 1}} and ints = {1, 10^6}, and processing would be done independently on those two objects. Of course this would require reimplementation of a great many things for general processing, but it may still be a valid approach in some cases. Reference: en.wikipedia.org/wiki/Indexed_color $\endgroup$ – Mr.Wizard Jun 13 '17 at 8:39
2
$\begingroup$

Here is Clip-based method which on my machine is little faster than BitXor& Unitize solution by Mr.Wizard:

fn3[a_?ArrayQ, old_, new_] := 
 a + (new - old) + Clip[a - old, {0, 0}, {old - new, old - new}] 

r2 = fn2[cellM, 2, 10]; // RepeatedTiming
r3 = fn3[cellM, 2, 10]; // RepeatedTiming
r2 == r3
{0.022, Null}

{0.019, Null}

True
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.