Unique-ifying an image

Question

I'm writing a program that takes an input image, and generates a set of unique colors, and repaints the image using only those colors. It takes a long time, and I'm hoping to improve the running time. It's on GitHub, if you want more context.

This is an example of the output, running from left to right:

output

This is the main program, which has the main logic:

public class Program {
 private static final String IMAGE_FILE = "/Untitled.png";
 // This adds more colors to choose from, more = slower
 private static final float ACCURACY_COEF = 2f;
 public static void main(final String[] args) throws IOException {
 final JFrame frame = new JFrame();
 final BufferedImage image = GraphicsUtils.loadImage(IMAGE_FILE);
 final BufferedImage newImage = createNewImage(image);
 saveImage(newImage);
 @SuppressWarnings("serial")
 final JPanel panel = new JPanel() {
 @Override
 public void paintComponent(final Graphics g) {
 g.drawImage(newImage, 0, 0, null);
 g.drawImage(image, newImage.getWidth(), 0, null);
 }
 };
 panel.setPreferredSize(new Dimension(newImage.getWidth() * 2, newImage.getHeight()));
 frame.add(panel);
 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 frame.pack();
 frame.setVisible(true);
 }
 private static void saveImage(final BufferedImage image) {
 final File outputfile = new File("image.png");
 try {
 ImageIO.write(image, "png", outputfile);
 } catch (final IOException e) {
 e.printStackTrace();
 }
 }
 /**
 * Recreates the image using only unique pixels, starting from the left of the image.
 *
 * @param image
 * @return
 */
 private static BufferedImage createNewImage(final BufferedImage image) {
 System.out.println("Generating points");
 final List<Point> points = generateAllPoints(image.getWidth(), image.getHeight());
 System.out.println("Generating colors");
 final KDTree colors = generateAllColors((int) (image.getWidth() * image.getHeight() * ACCURACY_COEF));
 System.out.println("Number of points: " + points.size() + ", Number of colors: " + colors.size());
 return createNewImage(image, points, colors);
 }
 /**
 * Creates the new image
 *
 * @param preImage
 * the original image
 * @param points
 * @param colors
 * @return
 */
 private static BufferedImage createNewImage(final BufferedImage preImage, final List<Point> points, KDTree colors) {
 final long start = System.currentTimeMillis();
 final BufferedImage newImage = GraphicsUtils.createImage(preImage.getWidth(), preImage.getHeight(), Transparency.OPAQUE);
 System.out.println("Creating image");
 int i = 1;
 long time = System.currentTimeMillis();
 // prints debug information and rebalances tree every so many iterations
 final int iterationsPerPrint = 5000;
 for (final Point p : points) {
 final Color c = getAndRemoveClosestColor(new Color(preImage.getRGB(p.x, p.y)), colors);
 newImage.setRGB(p.x, p.y, c.getRGB());
 if (i++ % iterationsPerPrint == 0) {
 final long timeTaken = System.currentTimeMillis() - time;
 final int remaining = points.size() - i;
 final long remainingMillis = (long) (remaining * (timeTaken / (double) iterationsPerPrint));
 System.out.println(remaining + " points remaining. Time taken for " + iterationsPerPrint + " iterations: " + timeTaken + " ms, or "
 + (float) timeTaken / iterationsPerPrint + " ms per iteration. Projected remaining time: " + extractTime(remainingMillis)
 + "\nTime elapsed: " + extractTime(System.currentTimeMillis() - start) + ", percent finished: " + (float) i / points.size()
 * 100f);
 time = System.currentTimeMillis();
 // PRUNING STEP
 colors = colors.pruneAndRebalance(new HPoint(new int[] { c.getRed(), c.getGreen(), c.getBlue() }));
 }
 }
 System.out.println("Finished!");
 return newImage;
 }
 private static String extractTime(final long millis) {
 return String.format("%d min, %d sec", TimeUnit.MILLISECONDS.toMinutes(millis),
 TimeUnit.MILLISECONDS.toSeconds(millis) - TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis)));
 }
 /**
 * Finds the color most similar to a specified color in the tree, removes it, and returns it.
 *
 * @param color
 * @param colors
 * @return
 */
 private static Color getAndRemoveClosestColor(final Color color, final KDTree colors) {
 try {
 final Color nearest = (Color) colors.nearest(new int[] { color.getRed(), color.getGreen(), color.getBlue() });
 colors.delete(new int[] { nearest.getRed(), nearest.getGreen(), nearest.getBlue() });
 return nearest;
 } catch (final KeySizeException | KeyMissingException e) {
 throw new RuntimeException(e);
 }
 }
 /**
 * Generates a list of all points in a rectangle
 *
 * @param width
 * @param height
 * @return
 */
 private static List<Point> generateAllPoints(final int width, final int height) {
 final List<Point> points = new ArrayList<>(width * height);
 for (int x = 0; x < width; x++) {
 for (int y = 0; y < height; y++) {
 points.add(new Point(x, y));
 }
 }
 return points;
 }
 private static KDTree generateAllColors(final int i) {
 if (i > 255 * 255 * 255 && i >= 0) {
 throw new IllegalArgumentException();
 }
 final float perColor = (float) Math.cbrt(i);
 assert perColor >= 0 && perColor <= 255;
 System.out.println("Generating with this many per channel: " + perColor);
 final KDTree tree = new KDTree(3);
 final float step = 255f / perColor;
 for (float r = 0; r < 255; r += step) {
 for (float g = 0; g < 255; g += step) {
 for (float b = 0; b < 255; b += step) {
 try {
 tree.insert(new int[] { (int) r, (int) g, (int) b }, new Color((int) r, (int) g, (int) b));
 } catch (KeySizeException | KeyDuplicateException e) {
 e.printStackTrace();
 }
 }
 }
 }
 return tree;
 }
}

I took a KD Tree implementation from the java-ml library, but I added my own rebalancing features in order to make it run quickly with a lot of deletions. I'm not sure if the way I implemented balancing is logical or optimal, but it improved performance; I profiled it and got this graph (the without pruning line was taking too long, so I ended it early):

enter image description here

public class KDTree {
 // K = number of dimensions
 private final int m_K;
 // root of KD-tree
 private KDNode m_root;
 // count of nodes
 private int m_count;
 /**
 * Creates a KD-tree with specified number of dimensions.
 *
 * @param k
 * number of dimensions
 */
 public KDTree(final int k) {
 m_K = k;
 m_root = null;
 }
 /**
 * Insert a node in a KD-tree. Uses algorithm translated from 352.ins.c of
 *
 * <PRE>
 * &#064;Book{GonnetBaezaYates1991,
 * author = {G.H. Gonnet and R. Baeza-Yates},
 * title = {Handbook of Algorithms and Data Structures},
 * publisher = {Addison-Wesley},
 * year = {1991}
 * }
 * </PRE>
 *
 * @param key
 * key for KD-tree node
 * @param value
 * value at that key
 *
 * @throws KeySizeException
 * if key.length mismatches K
 * @throws KeyDuplicateException
 * if key already in tree
 */
 public void insert(final int[] key, final Object value) throws KeySizeException, KeyDuplicateException {
 if (key.length != m_K) {
 throw new KeySizeException();
 } else {
 try {
 m_root = KDNode.ins(new HPoint(key), value, m_root, 0, m_K);
 }
 catch (final KeyDuplicateException e) {
 throw e;
 }
 }
 m_count++;
 }
 /**
 * Find KD-tree node whose key is identical to key. Uses algorithm translated from 352.srch.c of Gonnet &
 * Baeza-Yates.
 *
 * @param key
 * key for KD-tree node
 *
 * @return object at key, or null if not found
 *
 * @throws KeySizeException
 * if key.length mismatches K
 */
 public Object search(final int[] key) throws KeySizeException {
 if (key.length != m_K) {
 throw new KeySizeException();
 }
 final KDNode kd = KDNode.srch(new HPoint(key), m_root, m_K);
 return kd == null ? null : kd.v;
 }
 /**
 * Delete a node from a KD-tree. Instead of actually deleting node and rebuilding tree, marks node as deleted.
 * Hence, it is up to the caller to rebuild the tree as needed for efficiency.
 *
 * @param key
 * key for KD-tree node
 *
 * @throws KeySizeException
 * if key.length mismatches K
 * @throws KeyMissingException
 * if no node in tree has key
 */
 public void delete(final int[] key) throws KeySizeException, KeyMissingException {
 if (key.length != m_K) {
 throw new KeySizeException();
 }
 else {
 final KDNode t = KDNode.srch(new HPoint(key), m_root, m_K);
 if (t == null) {
 throw new KeyMissingException();
 } else {
 t.deleted = true;
 }
 m_count--;
 }
 }
 public int size() {
 return m_count;
 }
 /**
 * Find KD-tree node whose key is nearest neighbor to key. Implements the Nearest Neighbor algorithm (Table 6.4) of
 *
 * <PRE>
 * &#064;techreport{AndrewMooreNearestNeighbor,
 * author = {Andrew Moore},
 * title = {An introductory tutorial on kd-trees},
 * institution = {Robotics Institute, Carnegie Mellon University},
 * year = {1991},
 * number = {Technical Report No. 209, Computer Laboratory,
 * University of Cambridge},
 * address = {Pittsburgh, PA}
 * }
 * </PRE>
 *
 * @param key
 * key for KD-tree node
 *
 * @return object at node nearest to key, or null on failure
 *
 * @throws KeySizeException
 * if key.length mismatches K
 */
 public Object nearest(final int[] key) throws KeySizeException {
 return nearest(key, 1)[0];
 }
 /**
 * Find KD-tree nodes whose keys are <I>n</I> nearest neighbors to key. Uses algorithm above. Neighbors are returned
 * in ascending order of distance to key.
 *
 * @param key
 * key for KD-tree node
 * @param n
 * how many neighbors to find
 *
 * @return objects at node nearest to key, or null on failure
 *
 * @throws KeySizeException
 * if key.length mismatches K
 * @throws IllegalArgumentException
 * if <I>n</I> is negative or exceeds tree size
 */
 public Object[] nearest(final int[] key, final int n) throws KeySizeException, IllegalArgumentException {
 if (n < 0 || n > m_count) {
 throw new IllegalArgumentException("Number of neighbors cannot" + " be negative or greater than number of nodes");
 }
 if (key.length != m_K) {
 throw new KeySizeException();
 }
 final Object[] nbrs = new Object[n];
 final NearestNeighborList nnl = new NearestNeighborList(n);
 // initial call is with infinite hyper-rectangle and max distance
 final HRect hr = HRect.infiniteHRect(key.length);
 final int max_dist_sqd = Integer.MAX_VALUE;
 final HPoint keyp = new HPoint(key);
 KDNode.nnbr(m_root, keyp, hr, max_dist_sqd, 0, m_K, nnl);
 for (int i = 0; i < n; ++i) {
 final KDNode kd = (KDNode) nnl.removeHighest();
 nbrs[n - i - 1] = kd.v;
 }
 return nbrs;
 }
 /**
 * Range search in a KD-tree. Uses algorithm translated from 352.range.c of Gonnet & Baeza-Yates.
 *
 * @param lowk
 * lower-bounds for key
 * @param uppk
 * upper-bounds for key
 *
 * @return array of Objects whose keys fall in range [lowk,uppk]
 *
 * @throws KeySizeException
 * on mismatch among lowk.length, uppk.length, or K
 */
 public Object[] range(final int[] lowk, final int[] uppk) throws KeySizeException {
 if (lowk.length != uppk.length) {
 throw new KeySizeException();
 }
 else if (lowk.length != m_K) {
 throw new KeySizeException();
 }
 else {
 final Vector<KDNode> v = new Vector<KDNode>();
 KDNode.rsearch(new HPoint(lowk), new HPoint(uppk), m_root, 0, m_K, v);
 final Object[] o = new Object[v.size()];
 for (int i = 0; i < v.size(); ++i) {
 final KDNode n = v.elementAt(i);
 o[i] = n.v;
 }
 return o;
 }
 }
 @Override
 public String toString() {
 return m_root.toString(0);
 }
 /**
 * Removes deleted nodes and rebalances the tree based around a point.
 * 
 * @param point
 * @return
 */
 public KDTree pruneAndRebalance(final HPoint point) {
 final KDTree newTree = new KDTree(m_K);
 if (m_root != null) {
 m_root.addTo(newTree, point);
 }
 return newTree;
 }
}

KDNode.java

class KDNode {
 // these are seen by KDTree
 protected HPoint k;
 protected Object v;
 protected KDNode left, right;
 protected boolean deleted;
 // Method ins translated from 352.ins.c of Gonnet & Baeza-Yates
 protected static KDNode ins(final HPoint key, final Object val, KDNode t, final int lev, final int K) throws KeyDuplicateException {
 if (t == null) {
 t = new KDNode(key, val);
 }
 else if (key.equals(t.k)) {
 // "re-insert"
 if (t.deleted) {
 t.deleted = false;
 t.v = val;
 } else {
 throw new KeyDuplicateException();
 }
 }
 else if (key.coord[lev] > t.k.coord[lev]) {
 t.right = ins(key, val, t.right, (lev + 1) % K, K);
 } else {
 t.left = ins(key, val, t.left, (lev + 1) % K, K);
 }
 return t;
 }
 // Method srch translated from 352.srch.c of Gonnet & Baeza-Yates
 protected static KDNode srch(final HPoint key, KDNode t, final int K) {
 for (int lev = 0; t != null; lev = (lev + 1) % K) {
 if (!t.deleted && key.equals(t.k)) {
 return t;
 } else if (key.coord[lev] > t.k.coord[lev]) {
 t = t.right;
 } else {
 t = t.left;
 }
 }
 return null;
 }
 // Method rsearch translated from 352.range.c of Gonnet & Baeza-Yates
 protected static void rsearch(final HPoint lowk, final HPoint uppk, final KDNode t, final int lev, final int K, final Vector<KDNode> v) {
 if (t == null) {
 return;
 }
 if (lowk.coord[lev] <= t.k.coord[lev]) {
 rsearch(lowk, uppk, t.left, (lev + 1) % K, K, v);
 }
 int j;
 for (j = 0; j < K && lowk.coord[j] <= t.k.coord[j] && uppk.coord[j] >= t.k.coord[j]; j++) {
 ;
 }
 if (j == K) {
 v.add(t);
 }
 if (uppk.coord[lev] > t.k.coord[lev]) {
 rsearch(lowk, uppk, t.right, (lev + 1) % K, K, v);
 }
 }
 // Method Nearest Neighbor from Andrew Moore's thesis. Numbered
 // comments are direct quotes from there. Step "SDL" is added to
 // make the algorithm work correctly. NearestNeighborList solution
 // courtesy of Bjoern Heckel.
 protected static void nnbr(final KDNode kd, final HPoint target, final HRect hr, double max_dist_sqd, final int lev, final int K,
 final NearestNeighborList nnl) {
 // 1. if kd is empty then set dist-sqd to infinity and exit.
 if (kd == null) {
 return;
 }
 // 2. s := split field of kd
 final int s = lev % K;
 // 3. pivot := dom-elt field of kd
 final HPoint pivot = kd.k;
 final double pivot_to_target = HPoint.sqrdist(pivot, target);
 // 4. Cut hr into to sub-hyperrectangles left-hr and right-hr.
 // The cut plane is through pivot and perpendicular to the s
 // dimension.
 final HRect left_hr = hr; // optimize by not cloning
 final HRect right_hr = (HRect) hr.clone();
 left_hr.max.coord[s] = pivot.coord[s];
 right_hr.min.coord[s] = pivot.coord[s];
 // 5. target-in-left := target_s <= pivot_s
 final boolean target_in_left = target.coord[s] < pivot.coord[s];
 KDNode nearer_kd;
 HRect nearer_hr;
 KDNode further_kd;
 HRect further_hr;
 // 6. if target-in-left then
 // 6.1. nearer-kd := left field of kd and nearer-hr := left-hr
 // 6.2. further-kd := right field of kd and further-hr := right-hr
 if (target_in_left) {
 nearer_kd = kd.left;
 nearer_hr = left_hr;
 further_kd = kd.right;
 further_hr = right_hr;
 }
 //
 // 7. if not target-in-left then
 // 7.1. nearer-kd := right field of kd and nearer-hr := right-hr
 // 7.2. further-kd := left field of kd and further-hr := left-hr
 else {
 nearer_kd = kd.right;
 nearer_hr = right_hr;
 further_kd = kd.left;
 further_hr = left_hr;
 }
 // 8. Recursively call Nearest Neighbor with paramters
 // (nearer-kd, target, nearer-hr, max-dist-sqd), storing the
 // results in nearest and dist-sqd
 nnbr(nearer_kd, target, nearer_hr, max_dist_sqd, lev + 1, K, nnl);
 double dist_sqd;
 if (!nnl.isCapacityReached()) {
 dist_sqd = Double.MAX_VALUE;
 } else {
 dist_sqd = nnl.getMaxPriority();
 }
 // 9. max-dist-sqd := minimum of max-dist-sqd and dist-sqd
 max_dist_sqd = Math.min(max_dist_sqd, dist_sqd);
 // 10. A nearer point could only lie in further-kd if there were some
 // part of further-hr within distance sqrt(max-dist-sqd) of
 // target. If this is the case then
 final HPoint closest = further_hr.closest(target);
 if (HPoint.sqrdist(closest, target) < max_dist_sqd) {
 // 10.1 if (pivot-target)^2 < dist-sqd then
 if (pivot_to_target < dist_sqd) {
 // 10.1.2 dist-sqd = (pivot-target)^2
 dist_sqd = pivot_to_target;
 // add to nnl
 if (!kd.deleted) {
 nnl.insert(kd, dist_sqd);
 }
 // 10.1.3 max-dist-sqd = dist-sqd
 // max_dist_sqd = dist_sqd;
 if (nnl.isCapacityReached()) {
 max_dist_sqd = nnl.getMaxPriority();
 } else {
 max_dist_sqd = Double.MAX_VALUE;
 }
 }
 // 10.2 Recursively call Nearest Neighbor with parameters
 // (further-kd, target, further-hr, max-dist_sqd),
 // storing results in temp-nearest and temp-dist-sqd
 nnbr(further_kd, target, further_hr, max_dist_sqd, lev + 1, K, nnl);
 final double temp_dist_sqd = nnl.getMaxPriority();
 // 10.3 If tmp-dist-sqd < dist-sqd then
 if (temp_dist_sqd < dist_sqd) {
 // 10.3.1 nearest := temp_nearest and dist_sqd := temp_dist_sqd
 dist_sqd = temp_dist_sqd;
 }
 }
 // SDL: otherwise, current point is nearest
 else if (pivot_to_target < max_dist_sqd) {
 dist_sqd = pivot_to_target;
 }
 }
 // constructor is used only by class; other methods are static
 private KDNode(final HPoint key, final Object val) {
 k = key;
 v = val;
 left = null;
 right = null;
 deleted = false;
 }
 protected String toString(final int depth) {
 String s = k + " " + v + (deleted ? "*" : "");
 if (left != null) {
 s = s + "\n" + pad(depth) + "L " + left.toString(depth + 1);
 }
 if (right != null) {
 s = s + "\n" + pad(depth) + "R " + right.toString(depth + 1);
 }
 return s;
 }
 private static String pad(final int n) {
 final StringBuilder s = new StringBuilder();
 for (int i = 0; i < n; ++i) {
 s.append(' ');
 }
 return s.toString();
 }
 /**
 * Adds this node and subnodes to a tree. Tries to balance around a point.
 *
 * @param tree
 * @param middle
 */
 public void addTo(final KDTree tree, final HPoint middle) {
 final double distThis = deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, k);
 final double distLeft = left == null || left.deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, left.k);
 final double distRight = right == null || right.deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, right.k);
 // Add closest nodes first
 if (isMin(distThis, distLeft, distRight)) {
 addThis(tree);
 if (distLeft <= distRight) {
 addLeft(tree, middle);
 addRight(tree, middle);
 } else {
 addRight(tree, middle);
 addLeft(tree, middle);
 }
 } else if (isMin(distLeft, distThis, distRight)) {
 addLeft(tree, middle);
 if (distThis <= distRight) {
 addThis(tree);
 addRight(tree, middle);
 } else {
 addRight(tree, middle);
 addThis(tree);
 }
 } else {
 addRight(tree, middle);
 if (distLeft <= distThis) {
 addLeft(tree, middle);
 addThis(tree);
 } else {
 addThis(tree);
 addLeft(tree, middle);
 }
 }
 }
 private boolean isMin(final double a, final double b, final double c) {
 // returns whether a is the least
 return a <= b && a <= c;
 }
 private void addThis(final KDTree tree) {
 if (!deleted) {
 try {
 tree.insert(k.coord, v);
 } catch (KeySizeException | KeyDuplicateException e) {
 e.printStackTrace();
 }
 }
 }
 private void addLeft(final KDTree tree, final HPoint middle) {
 if (left != null) {
 left.addTo(tree, middle);
 }
 }
 private void addRight(final KDTree tree, final HPoint middle) {
 if (right != null) {
 right.addTo(tree, middle);
 }
 }
}

• JS1: Can you clarify the goal of the program? Is it enough that each pixel has a unique color? Or must the leftmost pixels be as close as possible to their original colors? Because you could speed things up a lot if your nearest color search returned an approximately correct answer instead of the exact answer.
• Kyranstar: @JS1 The goal of the program is really just to make a cool picture; I thought the effect of the image being less and less accurate from left to right was pretty cool. Considering I'm now using a kd tree, are you saying there's an even faster method that would return the approximate nearest neighbor?
• JS1: Yes, for example in your nnbr() function you could eliminate what you have commented as "step 10". That part searches other parts of the tree for even closer neighbors, but if you can approximate, you can skip that step.

Answer 1

How it runs

I started by cloning your app, setting it up and running. Then I started looking at it. I initially ran it 4 times, to see how it will work (CPU, memory - off-heap, on-heap - threads, what eats most resources etc. All runs are on same settings.

First run - little measurements

first run without any changes and almost no monitoring

1. The low resources time is when app started, I chose image and then, slightly after 10:22 I pressed "run" (and all hell broke loose... naah, kidding).
2. 10:22 - 10:23 - initial spike was when all data was loaded. Heap jumped high, CPU jumped high, actual work began.
3. Overall, not much!
   1. initial spike in CPU 65%, then less than 40%.
   2. GC negligible.
   3. the only thing to dwell on is heap graph. Consumption is too jumpy.

Clearly things are being allocated and deallocated, over and over again. Large things, or large number of things. This can happen if you have arrays. Large arrays. Or large number of not so large arrays. The heap is under 2GB, so that's nothing to be scared of.

Threads?

Threads are simple, there's one thread that does the job. It's named "Thread-x", where x is some number. Whatever AWT thread pool has currently, that gets tasked with this "run" button handling. Usual stack trace:

"Thread-17" - Thread t@56
 java.lang.Thread.State: RUNNABLE
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDNode.nnbr(KDNode.java:181)
 at kdtree.KDNode.nnbr(KDNode.java:139)
 at kdtree.KDTree.nearest(KDTree.java:229)
 at kdtree.KDTree.nearest(KDTree.java:192)
 at main.ImageTask.getAndRemoveClosestColor(ImageTask.java:77)
 at main.ImageTask.run(ImageTask.java:50)
 at java.lang.Thread.run(Thread.java:745)

thread that works

So, I know now what to focus on.

2nd run, sampling

CPU sampling during 2nd run

I've limited sampling to only methods from your packages. Clearly nnbr and ins are doing nearly all the work there is. What to focus on, identified!

All 4 runs and observations

patterns are seen

So, we have initial spike every time. Then we have stabilization. 3rd run is me overdoing monitoring (sampling CPU, mem, profiling CPU and using 3 tools at the same time). Thus the initial spike. Disregard that run (10:30 - 10:35) aside from the fact it's similar enough to others.

4th run is with a different image. New image had more colors. You can see heap being nicely used up till some point, where all of a sudden much work was to be done. Unfortunately, I didn't notice where it was (how far on "completion index" that you have or where on the image itself (which part of it).

4th run - heap

JConsole heap 4th run

Looks nice at first, then (not captured above) grows worse. Notice GC time: you may tune it to be better. Question is: do you need it? While I wouldn't want such times in production system, I don't feel so strongly about them here. But - your call.

4th run - CPU sampling

same old Same two methods eat CPU the most.

4th run - heap sampling

heap reinforces it So, you deal with graphics and use coordinates (int arrays). Big surprise. Also, KDNode is the class where it all happens. Again, big surprise.

Summarizing

These 4 runs are by no means exhaustive. They are rather preliminary. We see where to focus the efforts.

Code

Of course, I also looked at code.

Copying array

Use System.arraycopy if you want to be fast, instead of manual copying.

public HPoint(final int[] x) {
 coord = new int[x.length];
 for (int i = 0; i < x.length; ++i) {
 coord[i] = x[i];
 }
}

could be

public HPoint(final int[] x) {
 coord = new int[x.length];
 System.arraycopy(x, 0, coord, 0, x.length);
}

https://stackoverflow.com/questions/2589741/what-is-more-efficient-system-arraycopy-vs-arrays-copyof

Empty exception handling can be collapsed to 'throws'

 } catch (final UnsupportedLookAndFeelException e) {
 // handle exception
 } catch (final ClassNotFoundException e) {
 // handle exception
 } catch (final InstantiationException e) {
 // handle exception
 } catch (final IllegalAccessException e) {
 // handle exception
 }

in effect can be just a list of exceptions added to throws declaration, or - if you insists on swallowing - just swallow it once, don't set up 4 handlers for 4 exceptions and make Java check each case to do nothing.

Empty for loop

Noticed you had empty for loop to actually iterate through some data and find first case where XYZ. Spent few minutes puzzled by it.

 int j = 0;
 for (j = 0; j < K && lowk.coord[j] <= t.k.coord[j] && uppk.coord[j] >= t.k.coord[j]; j++) {
 ;
 }
 if (j == K) {
 v.add(t);
 }

this can be replaced with streaming:

 IntStream is = IntStream.range(0, K);
 OptionalInt j = is.filter(element -> lowk.coord[element] > t.k.coord[element] || uppk.coord[element] < t.k.coord[element]).findFirst();
 if (j.getAsInt() == K) {

If I understood it correctly of course (but seems for loop was only till first index that met the criteria, and then element so indexed in table t was the one we were after).

Extras

I had to do few things when writing this, so I stopped taking care of it. After an hour and a half, I went back and noticed, that you have some slowly growing activity:

leak perhaps

If your heap behaves like that when your app sits in the background and does nothing, you are likely to have a memory leak.

For first set of remarks I think that will be quite enough. :-) If you want, take a look at these findings (I've also opened pull request against your code) and once you made some changes, open a new question and I'll proceed from there.

https://github.com/kyranstar/UniquePixels/pull/1

Final remark: your code is serial. Splitting the image in n-sections may well allow you to have n-threads working on it at the "same" time (where "same" depends on your machine/OS/CPUs).