# Code to compare pixels by color

**URL:** <https://discourse.processing.org/t/code-to-compare-pixels-by-color/34764>\
**Category:** Coding Questions\
**Created:** [January 20, 2022, 10:43pm UTC](https://discourse.processing.org/t/code-to-compare-pixels-by-color/34764 "2022-01-20T22:43:02Z")\
**Posts on this page:** 1\
**Page:** 2

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [February 3, 2022, 9:48pm UTC](https://discourse.processing.org/t/code-to-compare-pixels-by-color/34764/21 "2022-02-03T21:48:36Z")

</div>

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**
>
> ```auto
> /*
> * 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("+- ");
> }
> }
> 
> ```

[Previous page](https://discourse.processing.org/t/code-to-compare-pixels-by-color/34764.md?page=1)