Ok, last post…
I actually implemented the idea in the edit above but without the parallelization part.
Meaning that instead of pairing again the removed source pixels straight away I put them in a backlog and pair them pass after pass.
On the previous pictures (1920*1280) and with a threshold of 100 i get:
- 02 minutes 02 seconds with the first method
- 01 minute 40 seconds with the new method
Almost 18% improvement! I should probably try several times with several images to be sure but good enough for me 
The impacted part of the code
/*
* This class is actually a KDTree with D = 3. The 3 dimensions being the R, G and B channels of a color space.
* Each unique color of a target image is used to create the nodes of the tree.
* The tree is build from the idea from the following paper: https://arxiv.org/pdf/1410.5420.pdf
*/
class PixelProcessor {
private Node m_root;
private Node m_nearest;
private int m_bestDist;
private PImage m_target;
/*
* Class constructor.
*/
public PixelProcessor(PImage l_targetImg) {
m_target = l_targetImg;
createTree(l_targetImg);
println("Tree built");
addTargetPixels(l_targetImg);
println("Target pixels coordinates added");
}
/*
* Create the tree from a target image.
* First the doubles are removed.
* Then the colors are sorted by 3 differents super keys RGB, GBR and BRG. => It will allow the tree to be balanced
* Finally the root node is created and the recursion begin.
*
* @param l_targetImg The target image containing the pixel to be used for creating the tree
*/
private void createTree(PImage l_targetImg) {
HashMap<Integer, Integer> targetColorNb = new HashMap<Integer, Integer>((int)(1 + (l_targetImg.width * l_targetImg.height) / 0.75));
//Get unique RGB values
l_targetImg.loadPixels();
for (int i = 0; i < l_targetImg.width; i++) {
for (int j = 0; j < l_targetImg.height; j++) {
int idx = j * l_targetImg.width + i;
Integer key = (0xFFFFFF & l_targetImg.pixels[idx]);
if (targetColorNb.containsKey(key)) {
Integer value = targetColorNb.get(key) + 1;
targetColorNb.put(key, value);
} else {
targetColorNb.put(key, Integer.valueOf(1));
}
}
}
//Initialize preSortedPixels with the unique RGB value
PixelColor[][] preSortedPixels;
preSortedPixels = new PixelColor[4][targetColorNb.size()];
int idx = 0;
for (Integer key : targetColorNb.keySet()) {
preSortedPixels[0][idx] = new PixelColor(key);
preSortedPixels[1][idx] = new PixelColor(key);
preSortedPixels[2][idx] = new PixelColor(key);
idx++;
}
//Sort first column with super key RGB
Arrays.sort(preSortedPixels[0], new Comparator<PixelColor>()
{
public int compare(PixelColor o1, PixelColor o2)
{
return o1.RGBCompareTo(o2);
}
}
);
//Sort second column with super key GBR
Arrays.sort(preSortedPixels[1], new Comparator<PixelColor>()
{
public int compare(PixelColor o1, PixelColor o2)
{
return o1.GBRCompareTo(o2);
}
}
);
//Sort third column with super key BRG
Arrays.sort(preSortedPixels[2], new Comparator<PixelColor>()
{
public int compare(PixelColor o1, PixelColor o2)
{
return o1.BRGCompareTo(o2);
}
}
);
m_root = new Node(preSortedPixels, targetColorNb);
}
/*
* Initialize the pixelPairings of each node with the list of pixels from the target image that share the exact same color as the node.
*
* @param l_targetImg The target image containing the pixels to be used for creating the tree
*/
private void addTargetPixels(PImage l_targetImg) {
//Add target pixels on proper nodes
for (int i = 0; i < l_targetImg.width; i++) {
for (int j = 0; j < l_targetImg.height; j++) {
int idx = j * l_targetImg.width + i;
PixelColor pixColor = new PixelColor(l_targetImg.pixels[idx]);
PixelCoord coord = new PixelCoord(i, j);
addTargetPixel(pixColor, coord);
}
}
}
/*
* Select the pixels from the target image to be removed based on the proximity of the pixel colors from a source image.
*
* @param l_sourceImg The source image containing the pixels to be used for removing the pixels in the target image
* @param l_threshold Distance squared at which a pixel from the source image can be paired to a pixel from the target image
*/
public PImage removePixelWith(PImage l_sourceImg, int l_threshold) {
findMatchingPixels(l_sourceImg, l_threshold);
println("Source image pixels matched");
PImage result = createImage(m_target.width, m_target.height, RGB);
result.copy(m_target, 0, 0, m_target.width, m_target.height, 0, 0, m_target.width, m_target.height);
removePixelsOf(result);
println("Result image updated");
return result;
}
/*
* Find to which target pixel the source pixels should be paired
*
* @param l_sourceImg The source image containing the pixels to be used for removing the pixels in the target image
* @param l_threshold Distance squared at which a pixel from the source image can be paired to a pixel from the target image
*/
private void findMatchingPixels(PImage l_sourceImg, int l_threshold) {
int previousTime = millis();
l_sourceImg.loadPixels();
for (int j = 0; j < l_sourceImg.height; j++) {
for (int i = 0; i < l_sourceImg.width; i++) {
int idx = j * l_sourceImg.width + i;
PixelColor pixColor = new PixelColor(l_sourceImg.pixels[idx]);
findBestMatch(pixColor, l_threshold);
int now = millis();
if (now - previousTime > 5000) {
println("Source pixels analyzed: " + idx + " / " + l_sourceImg.height * l_sourceImg.width);
previousTime = now;
}
}
}
}
/*
* Find to which target pixel one given source pixel should be paired.
*
* @param l_color The source image pixel to be paired to a target image pixel
* @param l_threshold Distance squared at which a pixel from the source image can be paired to a pixel from the target image
*/
public void findBestMatch(PixelColor l_color, int l_threshold) {
m_nearest = null;
m_bestDist = 50000000; // Max dist is 3 * 255 * 255 * 255. It needs to be higher.
bestMatch(m_root, l_color);
if (m_nearest == null) return;
if (m_nearest.m_color.distFrom(l_color) > l_threshold) {
return;
}
PixelColor toReinsert = m_nearest.m_pixelPairings.addSourcePoint(l_color, m_bestDist);
if (toReinsert == null) return;
findBestMatch(toReinsert, l_threshold);
}
/*
* Find to which target pixel one given source pixel should be paired.
* Recursion part of the findBestMatch method
*
* @param l_node The node to investigate
* @param l_color The source image pixel to be paired to a target image pixel
* @param l_threshold Distance squared at which a pixel from the source image can be paired to a pixel from the target image
*/
public void bestMatch(Node l_node, PixelColor l_color) {
if (l_node == null)
return;
int d = l_node.m_color.distFrom(l_color);
if (d < m_bestDist) {
if (l_node.m_pixelPairings.isBetterMatch(d)) {
m_bestDist = d;
m_nearest = l_node;
}
}
if (m_bestDist == 0)
return;
int pivotSide = l_color.compareTo(l_node.m_color, l_node.m_depth % 3);
bestMatch( (pivotSide < 0) ? l_node.m_left : l_node.m_right, l_color);
if (l_color.distFromPlane(l_node.m_color, l_node.m_depth % 3) < m_bestDist)
bestMatch( (pivotSide < 0) ? l_node.m_right : l_node.m_left, l_color);
}
/*
* Add a target pixel coordinate to the pixelParings of the proper node that have the exact same color as the target pixel.
*
* @param l_color The color of the target pixel to add
* @param l_coord The coordinate of the target pixel to add
*/
public void addTargetPixel(PixelColor l_color, PixelCoord l_coord) {
addTargetPixelRecursion(l_color, l_coord, m_root);
}
/*
* Add a target pixel coordinate to the pixelParings of the proper node that have the exact same color as the target pixel.
* Recursion part of the addTargetPixel method.
*
* @param l_color The color of the target pixel to add
* @param l_coord The coordinate of the target pixel to add
* @param l_node The node to investigate
*/
private void addTargetPixelRecursion(PixelColor l_t, PixelCoord l_coord, Node l_node) {
if (l_t.isEqualTo(l_node.m_color)) {
l_node.m_pixelPairings.addTargetPixelCoord(l_coord);
return;
}
int pivotSide = l_t.compareTo(l_node.m_color, l_node.m_depth % 3);
addTargetPixelRecursion(l_t, l_coord, (pivotSide < 0) ? l_node.m_left : l_node.m_right);
}
/*
* Remove (turn to white) the pixels of the target image base on the pixel pairing done with the source image.
*
* @param l_resultImg The result image (same as the target image) on which to remove the pixels
*/
public void removePixelsOf(PImage l_resultImg) {
l_resultImg.loadPixels();
removePixelsOfRecursion(l_resultImg.pixels, l_resultImg.width, m_root);
l_resultImg.updatePixels();
}
/*
* Remove (turn to white) the pixels of the target image base on the pixel pairing done with the source image.
* Recursion part of the removePixelsOf method.
*
* @param l_p The pixel array of the result image (same as the target image) on which to remove the pixels
* @param l_imgWidth The width of the result image
* @param l_node The node to investigate
*/
private void removePixelsOfRecursion(int[] l_p, int l_imgWidth, Node l_node) {
if (l_node == null) return;
PixelCoord[] coord = l_node.m_pixelPairings.m_targetCoords;
for (int i = 0; i < l_node.m_pixelPairings.m_nbOfPairedColors; i++) {
int idx = coord[i].y * l_imgWidth + coord[i].x;
l_p[idx] = color(255);
}
removePixelsOfRecursion(l_p, l_imgWidth, l_node.m_left);
removePixelsOfRecursion(l_p, l_imgWidth, l_node.m_right);
}
/*
* Print the tree nodes in the console with indents
*/
void prettyPrint() {
m_root.prettyPrint("+- ");
}
}