Code to compare pixels by color

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 :sweat_smile:

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("+- ");
  }
}
1 Like