Efficient way to replace a value in packed array of integers

Question

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["https://i.sstatic.net/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.

Answer 1

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}]

Answer 2

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.

Answer 3

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