Makes me wonder if this could be even faster, if you cheated and just generated copies of the masks already colored, for every color available. From looking at the video, I see you have 10-11 colors available at any given moment with possibility of changing them to, presumably, arbitrary RGB value. That means you only need to keep 11 color variants of each mask, which should still fit in RAM. You also need to be able to replace a single group of masks with a new set of masks faster than the user can switch colors in the custom color picker.

(I know, it's a dumb idea in this case; I'm posting it as a reminder to both myself and everyone else, that many problems can be solved by checking or caching every possible state.)