Image Segmentation

A closely related task to region labeling is "image segmentation." It is about partitioning a digital image into multiple segments (or regions). The goal of segmentation is typically to simplify or change the representation of an image into something easier to analyze.

For example, consider the following image, gradient.png file inside the src/main/resource/small folder.

If we were to label the regions of this image using our ImageRegions program, it would find 72 regions (essentially, each pixel is considered a region because their colors are not the same). That many regions may not be useful for some applications. For instance, if this image was the background where a picture of a puppy was imposed on it (as a foreground), and we wanted to detect and separate the puppy, we would have preferred if the entire gradient area was detected as one single region. We can adjust the color similarity threshold in ImageRegions program to achieve this. However, we would have to adjust the threshold for different images differently! What if we could tell the program we see $k$ regions in the image and ask it to segment the image to the desired number of regions. This idea is implemented in the ImageSegmentation program. The program segments the given image to the desired number of regions. Moreover, it colors each region with the "average color" of all the pixels in that region. Finally, it saves the segmented image to the out/production/final folder.

Another example is using the stripes.png file inside the src/main/resource/small folder.

The ImageSegmentation program employs a "minimum spanning tree-based segmentation approach" where Kruskal's algorithm is modified to solve the task at hand. It relies on the Union-Find data structure. So if your implementation of UnionFind is erroneous, the segmentation will not work! At any rate, the code is well written, modularized, and documented.

Discussion

Please open the README.md file and answer the following questions.

1. Briefly describe how the minimum spanning tree-based segmentation works. Please describe the algorithm at a high-level (don't describe the code). Keep the answer to a paragraph or two; be brief and to the point.

2. Carefully inspect the addAllEdges method. "It seems that each edge is added twice to the priority queue." Is this statement true or false? If it is false, state why. If it is true, state why this is not a problem (not a bug).

3. Carefully inspect the kruskal method. "It seems the implementation of kruskal is missing the step to check for cycles and avoid it." Is this statement true or false? If it is false, state why. If it is true, state why this is not a problem (not a bug).

4. Consider this statement: "Kruskal is a better choice compared to Prim's algorithm for minimum spanning tree-based segmentation." Is this statement true or false? Justify your answer. Keep the response to a paragraph; be brief and to the point. Hint: think about the similarity and differences between Prim's and Kruskal's algorithms. It is okay to Google something like "Difference between Prim's and Kruskal's algorithm for MST" and use your understanding to answer this question.

5. Finally, complete the following code snippet by providing the missing running times. Please describe the running time as a function of image width ($w$) and image height ($h$). Assume Java's priority queue is implemented as a binary heap where all core operations are logarithmic. Assume Java's hash table (HashMap) operates under uniform hashing assumption with excellent collision resolution that results in constant time operations!

Color[][] pixels = ImageUtility.getPixels(image); // O(w x h)
PriorityQueue<Edge> edges = addAllEdges(pixels);  // O(?)
UnionFind<Integer> regions = new RasterUnionFind(image.getWidth(), image.getHeight()); // O(?)

while (!edges.isEmpty()) { // O(?)
  Edge e = edges.poll();   // O(?)
  regions.union(e.fromPixelID, e.toPixelID);  // O(?)
  if (regions.count() == numberOfDesiredRegions) { // O(?)
    break; // O(?)
  }
}

HashMap<Integer, Color> colors = assignColorToEachRegion(pixels, regions); // O(?)
reColor(image, regions, colors); // O(?)

Hint: Visit Wikipedia's entry on Regular graph to figure out the upper bound on the number of edges that gets stored to the priority queue.