It’s been a while but I kept thinking of your little challenge and came up with a better version I think.
This time, the algorithm will always match the best possible pixels together (the closest ones) so if you input twice the same pictures, every pixel gets deleted.
The performance are greatly improved compare to my last post. I managed to deal with a 4K by 6K image quite fast. The 2 main factors impacted the performance are the size of the source image as well as the threshold used to consider if there is a match or not.
Here an example outcome with a threshold = 100 (the threshold represent the distance squared).
I fully commented the code and described as much as possible the mechanics so it shouldn’t be to hard to understand how the code is structured and how it works.
Summary
import java.util.*;
PixelProcessor pp;
void setup() {
PImage targetImg, srcImg, processedImg;
targetImg = loadImage("Target_02.jpg");
srcImg = loadImage("Source_02.jpg");
pp = new PixelProcessor(targetImg);
processedImg = pp.removePixelWith(srcImg, 100);
processedImg.save("data/Result_02.jpg");
println("Processed image saved");
}
/**
* This class is a lightweight class used to keep track of the RGB channels of a color.
* It aims at facilitating the comparaison of the colors and the computation of distances to other colors or plane.
*/
class PixelColor {
public byte r, g, b;
/*
* Class constructor from an int encoding a color where the bits are ordered as followed: ********RRRRRRRRGGGGGGGGBBBBBB.
* R's contain the red value, G's the green and B's the blue one.
*/
public PixelColor(int l_rgb) {
r = (byte)(l_rgb >> 16);
g = (byte)(l_rgb >> 8);
b = (byte)l_rgb;
}
/*
* Class constructor from each individual channel.
*/
public PixelColor(int l_r,int l_g,int l_b) {
r = (byte)l_r;
g = (byte)l_g;
b = (byte)l_b;
}
/*
* Print the color in the console with format "(RRR, GGG, BBB)"
*/
public void prettyPrint() {
print("(" + nf(0xFF & r, 3) + ", " + nf(0xFF & g, 3) + ", " + nf(0xFF & b, 3) + ")");
}
/*
* Combine each color channel in an int with the bits ordered as followed: 00000000RRRRRRRRGGGGGGGGBBBBBBBB
* R's contain the red value, G's the green and B's the blue one.
*/
public int getInt() {
return ((0xFF & r) << 16) | ((0xFF & g) << 8) | (0xFF & b);
}
/*
* Check if each channel of the colors are equal.
*
* @param l_o The other color to compare to
* @return true if each channels are equals, false otherwise
*/
public boolean isEqualTo(PixelColor l_o) {
return RGBCompareTo(l_o) == 0;
}
/*
* Compare two colors for order.
* The comparaison is done on super keys: RGB, GBR or BRG. Meaning each color is converted in an int with the bits ordered as specified before comparing the 2 values.
*
* @param l_o The other color to compare to
* @param l_sortOrder The order in which to arrange the bits
* 1: bits ordered as RGB: 00000000RRRRRRRRGGGGGGGGBBBBBBBB
* 2: bits ordered as GBR: 00000000GGGGGGGGBBBBBBBBRRRRRRRR
* 3: bits ordered as BRG: 00000000BBBBBBBBRRRRRRRRGGGGGGGG
* Any other values than 1 or 2 will end up using the GBR order
* @return A positive value, zero or a negative value depending if the current color is bigger, equal or smaller than the color argument
*/
public int compareTo(PixelColor l_o, int l_sortOrder) {
if (l_sortOrder == 0) return RGBCompareTo(l_o);
if (l_sortOrder == 1) return GBRCompareTo(l_o);
return BRGCompareTo(l_o);
}
/*
* Compare two colors for order.
* The comparaison is done on the super key: RGB. Meaning each color is converted in an int with the bits ordered as follow 00000000RRRRRRRRGGGGGGGGBBBBBBBB
*
* @param l_o The color with which to compare
* @return A positive value, zero or a negative value depending if the current color is bigger, equal or smaller than the color argument
*/
public int RGBCompareTo(PixelColor l_o) {
return (((0xFF & r) << 16) | ((0xFF & g) << 8) | (0xFF & b)) - (((0xFF & l_o.r) << 16) | ((0xFF & l_o.g) << 8) | (0xFF & l_o.b));
}
/*
* Compare two colors for order.
* The comparaison is done on the super key: GBR. Meaning each color is converted in an int with the bits ordered as follow 00000000GGGGGGGGBBBBBBBBRRRRRRRR
*
* @param l_o The color with which to compare
* @return A positive value, zero or a negative value depending if the current color is bigger, equal or smaller than the color argument
*/
public int GBRCompareTo(PixelColor l_o) {
return (((0xFF & g) << 16) | ((0xFF & b) << 8) | (0xFF & r)) - (((0xFF & l_o.g) << 16) | ((0xFF & l_o.b) << 8) | (0xFF & l_o.r));
}
/*
* Compare two colors for order.
* The comparaison is done on the super key: BRG. Meaning each color is converted in an int with the bits ordered as follow 00000000BBBBBBBBRRRRRRRRGGGGGGGG
*
* @param l_o The color with which to compare
* @return A positive value, zero or a negative value depending if the current color is bigger, equal or smaller than the color argument
*/
public int BRGCompareTo(PixelColor l_o) {
return (((0xFF & b) << 16) | ((0xFF & r) << 8) | (0xFF & g)) - (((0xFF & l_o.b) << 16) | ((0xFF & l_o.r) << 8) | (0xFF & l_o.g));
}
/*
* A color can be thought as a point in 3D space where R, G and B are the unit vectors of the space.
* Compute the distance squared between the color and a plane normal to one of the R, G or B direction going through a given color.
*
* @param l_o Color belonging to the plane
* @param l_normal The direction of the normal to the plane
* 1: the normal is the R direction
* 2: the normal is the G direction
* 3: the normal is the B direction
* Any other values will return 0
* @return The distance squared
*/
public int distFromPlane(PixelColor l_o, int l_normal) {
int delta = 0;
if (l_normal == 0) delta = (0xFF & r) - (0xFF & l_o.r);
if (l_normal == 1) delta = (0xFF & g) - (0xFF & l_o.g);
if (l_normal == 2) delta = (0xFF & b) - (0xFF & l_o.b);
return delta * delta;
}
/*
* A color can be thought as a point in 3D space where R, G and B are the unit vectors of the space.
* Compute the distance squared between 2 colors.
*
* @param l_o The color with which to compute the distance
* @return The distance squared
*/
public int distFrom(PixelColor l_o) {
int dr = (0xFF & r) - (0xFF & l_o.r);
int dg = (0xFF & g) - (0xFF & l_o.g);
int db = (0xFF & b) - (0xFF & l_o.b);
return dr * dr + dg * dg + db * db;
}
}
/**
* A simple classe to hold the (x, y) coordinates of a pixel
*/
class PixelCoord {
public int x, y;
/*
* Class constructor.
*/
public PixelCoord(int l_x, int l_y) {
x = l_x;
y = l_y;
}
}
/*
* Class designed to work in pair with the Node class.
* It allows to keep track of which pixels on the target image shares the same color as the node that created the object and if it should be deleted during the post processing or not.
* To know weither or not a target pixel should be deleted, the pixels from the source image are analysed and paired against target pixel with the closest color.
* If a target pixel is paired, it should be deleted, otherwise it is not.
* Of course it is not possible to pair more source pixel that there are available target pixels with a given color.
* If it happens, the distance from that source pixel is compared to the one already matched and if the distance is smaller (a better match) then this source pixel is added and the other one checked against the next closet target pixel.
*
* This class offers method to help identifying when all the target pixels are paired and help pairing new source pixels.
*/
class PixelPairings {
public PixelCoord[] m_targetCoords; // Coordinates of all the pixels of the target image sharing the same color of the node using that object
public PixelColor[] m_pairedColors; // Colors of the source image that got paired with the target image color with ascending order of distances from the target color of this object.
public int[] m_pairedColorsDist; // Distance squared from the colors that got paired to the color of the node using that object with ascending order. Always match the m_pairedColors array to give the corresponding distance.
public int m_nbOfPairedColors; // Number of colors that got paired so fare
public int m_nbOfTargetCoords; // Number of pixels from the target image that got added so far
public int m_size; // Size of the 3 arrays
/*
* Class constructor.
* It takse as input the number of target pixels sharing the node color to give the proper size to the arrays.
*/
public PixelPairings(int l_size) {
m_size = l_size;
m_nbOfPairedColors = 0;
m_nbOfTargetCoords = 0;
m_targetCoords = new PixelCoord[l_size];
m_pairedColorsDist = new int[l_size];
m_pairedColors = new PixelColor[l_size];
initDistances();
}
/*
* The m_pairedColorsDist is used to store the distance squared from the source colors that got paired to this object target color.
* The distances are stored in ascending order.
* To know if a new source color should be added, it is simply a matter of checking the last distance of that array with the new source color distance.
* If it is smaller then the new color need to be added.
* For this reason all the distances are initialized with a value higher than the maximum possible value wich is: 3 * 255 * 255 * 255 = 49 744 125
* It is also usefull to detect target point that got paired as the distance will necessarily be lower than the max value.
*/
private void initDistances() {
for (int i = 0; i < m_size; i++) {
m_pairedColorsDist[i] = 50000000;
}
}
/*
* Add the coordinate of a target pixel sharing the same color as the node that created this object.
* There is no check on out of bound insertion since the size of the array has been defined knowing how many pixels in the target image share the node color.
*
* @param l_coord The target pixel coordinate to add to the object
*/
public void addTargetPixelCoord(PixelCoord l_coord) {
m_targetCoords[m_nbOfTargetCoords] = l_coord;
m_nbOfTargetCoords++;
}
/*
* Check if a new source color distance to the node color is smaller than the biggest distance from the source colors currently paired.
*
* @param l_d The new source color distance
* @return true if the new source color distance is smaller than the biggest distance from the source colors currently paired, false otherwise
*/
public boolean isBetterMatch(int l_d) {
if (m_nbOfPairedColors < m_size) return true;
if (l_d < m_pairedColorsDist[m_size - 1]) return true;
return false;
}
/*
* Add a new source color to the paired source colors array.
* It keeps the paired source colors and distances arrays paired and ensure that they are sorted by ascending order leaving the furthest source colors in the back of the array.
* It also return the paired source color that got deleted if any in order to be able to pair that color with another target pixel.
*
* @param l_t The source pixel color to pair
* @param l_d The distance from that source color to the node color that created that object
* @return The furthest paired color that got removed from the array if any, null otherwise
*/
public PixelColor addSourcePoint(PixelColor l_color, int l_d) {
PixelColor toReturn = m_pairedColors[m_size - 1];
// Array of any size but no element in it
if (m_nbOfPairedColors == 0) {
m_pairedColors[0] = l_color;
m_pairedColorsDist[0] = l_d;
m_nbOfPairedColors++;
return toReturn;
}
// Array of size 1 with 1 element in it
if (m_size == 1) {
if (l_d < m_pairedColorsDist[0]) {
m_pairedColors[0] = l_color;
m_pairedColorsDist[0] = l_d;
return toReturn;
} else {
return null;
}
}
// Array of size >= 2 with only 1 element in it
if (m_nbOfPairedColors == 1) {
if (l_d < m_pairedColorsDist[0]) {
m_pairedColors[1] = m_pairedColors[0];
m_pairedColorsDist[1] = m_pairedColorsDist[0];
m_pairedColors[0] = l_color;
m_pairedColorsDist[0] = l_d;
m_nbOfPairedColors++;
return toReturn;
} else {
m_pairedColors[1] = l_color;
m_pairedColorsDist[1] = l_d;
m_nbOfPairedColors++;
return toReturn;
}
}
// If array is full and point worse than last element
if (m_nbOfPairedColors == m_size && l_d >= m_pairedColorsDist[m_size - 1]) {
return null;
}
// Any other cases find where to insert the element
int low = 0, high = m_nbOfPairedColors;
if(l_d < m_pairedColorsDist[0]) {
low = -1;
high = -1;
}
while (high - low > 1) {
int mid = (high + low) / 2;
if (l_d < m_pairedColorsDist[mid]) {
high = mid;
} else if (l_d > m_pairedColorsDist[mid]) {
low = mid;
} else {
low = mid;
high = mid;
}
}
// Shift worst elements
int start = min(m_nbOfPairedColors, m_size - 1);
for (int i = start; i > low + 1; i--) {
m_pairedColors[i] = m_pairedColors[i-1];
m_pairedColorsDist[i] = m_pairedColorsDist[i-1];
}
// Add new element
m_pairedColors[low + 1] = l_color;
m_pairedColorsDist[low + 1] = l_d;
if (m_nbOfPairedColors < m_size) m_nbOfPairedColors++;
return toReturn;
}
/*
* Print the paired colors array with the associated distances
*/
void prettyPrint(String l_indent) {
for (int i = 0; i < m_size; i++) {
if (m_pairedColors[i] == null) {
println(l_indent + "null");
} else {
m_pairedColors[i].prettyPrint();
println(l_indent + " " + m_pairedColorsDist[i]);
}
}
}
}
/*
* Class representing a node of the tree.
* Each node represent a color in the target image.
*/
class Node {
Node m_parent, m_left, m_right;
PixelColor m_color;
int m_depth;
PixelPairings m_pixelPairings;
/*
* Class constructor. Only publicly available constructor.
* Construct all the node of the tree from the list of colors.
*
* @param l_colors The list of colors where the tree needs to split
* @param l_targetColorNb A hashmap containing the number of pixels of a given color (the key) in the target image
*/
public Node(PixelColor[][] l_colors, HashMap<Integer, Integer> l_targetColorNb) {
m_parent = null;
m_color = l_colors[0][l_colors[0].length / 2];
m_pixelPairings = new PixelPairings(l_targetColorNb.get(m_color.getInt()));
m_depth = 0;
createChildren(l_colors, l_targetColorNb, 0, l_colors[0].length);
}
/*
* Class constructor used in the tree construction to add a children node and continue the recursion (left and right children to be determined by recursion)
*/
private Node(PixelColor[][] l_colors, HashMap<Integer, Integer> l_targetColorNb, Node l_parent, int l_depth, PixelColor l_nodeColor, int l_from, int l_to) {
m_parent = l_parent;
m_color = l_nodeColor;
m_pixelPairings = new PixelPairings(l_targetColorNb.get(m_color.getInt()));
m_depth = l_depth;
createChildren(l_colors, l_targetColorNb, l_from, l_to);
}
/*
* Class constructor used in the tree construction to add a children node and end the recursion (left and right children are null).
*/
private Node(HashMap<Integer, Integer> l_targetColorNb, Node l_parent, int l_depth, PixelColor l_nodeColor) {
m_parent = l_parent;
m_color = l_nodeColor;
m_pixelPairings = new PixelPairings(l_targetColorNb.get(m_color.getInt()));
m_depth = l_depth;
m_left = null;
m_right = null;
}
/*
* Brain of the tree construction.
* Creates the nodes by recursively dividing the space in two, looping through the 3 R, G and B directions
* It uses an implementation of the following paper: https://arxiv.org/pdf/1410.5420.pdf
*/
private void createChildren(PixelColor[][] l_colors, HashMap<Integer, Integer> l_targetColorNb, int l_from, int l_to) {
//If there is no more node to create we can stop the recursion
if (l_to - l_from == 1) {
m_left = null;
m_right = null;
return;
}
// If there is only one node left to create we can stop the recursion. The solution is trivial.
if (l_to - l_from == 2) {
m_left = new Node(l_targetColorNb, this, m_depth + 1, l_colors[0][l_from]);
m_right = null;
return;
}
// If there is only 2 nodes left to create we can stop the recursion. The solution is trivial.
if (l_to - l_from == 3) {
m_left = new Node(l_targetColorNb, this, m_depth + 1, l_colors[0][l_from]);
m_right = new Node(l_targetColorNb, this, m_depth + 1, l_colors[0][l_to - 1]);
return;
}
//Init helper variables
int midPt = (l_to + l_from) / 2;
PixelColor midPixelColor = l_colors[0][midPt];
int lowerIdx, higherIdx;
//Copy first column to last column
for (int i = l_from; i < l_to; i++) {
l_colors[3][i] = l_colors[0][i];
}
l_colors[3][midPt] = null;
//Sort 2nd column in the 2 halves of the first column according to current direction
lowerIdx = l_from;
higherIdx = midPt + 1;
for (int i = l_from; i < l_to; i++) {
int comparator = l_colors[1][i].compareTo(midPixelColor, m_depth % 3);
if (comparator > 0) {
l_colors[0][higherIdx] = l_colors[1][i];
higherIdx++;
} else if (comparator < 0) {
l_colors[0][lowerIdx] = l_colors[1][i];
lowerIdx++;
}
}
l_colors[0][midPt] = null;
//Sort 3rd column in the 2 halves of the second column according to current direction
lowerIdx = l_from;
higherIdx = midPt + 1;
for (int i = l_from; i < l_to; i++) {
int comparator = l_colors[2][i].compareTo(midPixelColor, m_depth % 3);
if (comparator > 0) {
l_colors[1][higherIdx] = l_colors[2][i];
higherIdx++;
} else if (comparator < 0) {
l_colors[1][lowerIdx] = l_colors[2][i];
lowerIdx++;
}
}
l_colors[1][midPt] = null;
//Copy last column to Third column
for (int i = l_from; i < l_to; i++) {
l_colors[2][i] = l_colors[3][i];
}
//Recursion
m_left = new Node(l_colors, l_targetColorNb, this, m_depth + 1, l_colors[0][(l_from + midPt) / 2], l_from, midPt);
m_right = new Node(l_colors, l_targetColorNb, this, m_depth + 1, l_colors[0][(midPt + 1 + l_to) / 2], midPt + 1, l_to);
}
/*
* Print the color of each node using the specified string as an indent
*/
public void prettyPrint(String l_indent) {
print(l_indent);
m_color.prettyPrint();
println("");
if(m_left != null) m_left.prettyPrint(" " + l_indent);
if(m_right != null) m_right.prettyPrint(" " + l_indent);
}
}
/*
* 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("+- ");
}
}
