# 112-2 PDSA HW1

**Release date: 02/19 16:00
Due date: 02/28 21:00**

## HW1 - Image Segmentation

The images are segmented into several parts. For this assignment, your goal is to implement the **Union-Find** algorithm to efficiently extract essential information.

## Introduction

**Image Segmentation** plays a crucial role in the field of Computer Vision, where images are divided into distinct regions. This essential task has several subcategories, such as **Semantic Segmentation, Instance Segmentation, Panoramic Segmentation, etc.**

To simplify the task, we will concentrate on **Semantic Segmentation** in this assignment and subsequent descriptions. If you want to learn more about Image Segmentation, please refer to [this link](https://nirmalamurali.medium.com/image-classification-vs-semantic-segmentation-vs-instance-segmentation-625c33a08d50) or [this link](https://medium.com/ching-i/%E5%BD%B1%E5%83%8F%E5%88%86%E5%89%B2-image-segmentation-%E8%AA%9E%E7%BE%A9%E5%88%86%E5%89%B2-semantic-segmentation-1-53a1dde9ed92).

## Description

In the provided N x N segmented image, which is represented as a 2D array of Integers, color values are used to distinguish objects. A color value of 0 denotes the uncolored background, while any non-zero color value signifies the presence of an object.

Your objective is to design a Java program that utilizes **Union-Find** algorithm to process the segmented images. The program should extract information, specifically:

+ **Count the Number of Distinct Segments**.
+ **Find the Size and Color of the Largest Segment**.

Here are some supplementary instructions:

+ Uncolored background pixels **are not considered as Segments**
+ If there are unconnected segments with the same color, they will **be treated as Multiple Segments** (i.e., counted as separate segments), and their pixels will not be combined when calculating the number of pixels.
+ If two or more segments are of the same size, the segment with the smallest color index is considered the larger segment.

## Template

class ImageSegmentation {
    
    private int size;
    private int segmentCount;
    private int largestColor;
    private int largestSize;

    public ImageSegmentation(int N, int[][] inputImage) {
        // Initialize a N-by-N segmented image
    }

    public int countDistinctSegments() {
        // Count the number of distinct segments in the image.
        return segmentCount;
    }

    public int[] findLargestSegment() {
        // Find the largest connected segment and return an array
        // containing the number of pixels and the color of the segment.
        return new int[]{largestSize, largestColor};
    }

    public void mergeSegment(int x1, int y1, int x2, int y2) {
        // Implement the function to merge two adjacent segments if necessary.
    }

    public static void main(String args[]) {

        // Example 1:
        int[][] inputImage1 = {
            {0, 0, 0},
            {0, 1, 1},
            {0, 0, 1}
        };

        System.out.println("Example 1:");

        ImageSegmentation s = new ImageSegmentation(3, inputImage1);
        System.out.println("Distinct Segments Count: " + s.countDistinctSegments());

        int[] largest = s.findLargestSegment();
        System.out.println("Largest Segment Size: " + largest[0]);
        System.out.println("Largest Segment Color: " + largest[1]);


        // Example 2:
        int[][] inputImage2 = {
               {0, 0, 0, 3, 0},
               {0, 2, 3, 3, 0},
               {1, 2, 2, 0, 0},
               {1, 2, 2, 1, 1},
               {0, 0, 1, 1, 1}
        };

        System.out.println("\nExample 2:");

        s = new ImageSegmentation(5, inputImage2);
        System.out.println("Distinct Segments Count: " + s.countDistinctSegments());

        largest = s.findLargestSegment();
        System.out.println("Largest Segment Size: " + largest[0]);
        System.out.println("Largest Segment Color: " + largest[1]);

    }

}

## Expected Output

Example 1:
Distinct Segments Count: 1
Largest Segment Size: 3
Largest Segment Color: 1

Example 2:
Distinct Segments Count: 4
Largest Segment Size: 5
Largest Segment Color: 1

## TestCase

Time Limit: 200ms
+ N: size of the image
+ C: num of colors in this image
+ 20 points: N <= 3, C <= 2 (Easy)
+ 20 points: N <= 5, C <= 5 (Special Case)
+ 20 points: N <= 25, C <= 10
+ 20 points: N <= 100, C <= 50
+ 20 points: N <= 500, C <= 100

## File Download

[Lib](https://drive.google.com/drive/folders/1PA-RsQGZ1ohV2GhuWWL-x5NLBL9k9j4L?usp=sharing)
[Test Code](https://drive.google.com/file/d/1P-pfGVZd10p-MVQH9tpQUi6iS3TLkg9F/view?usp=drive_link)
[Test Case](https://drive.google.com/file/d/1gbA6bSKtGWAXo3JK-O5mF07qxom0kBa2/view?usp=drive_link)