1 Description Design, develop, and test a program that labels groups of connected pixels in a binary image. For this project, a binary image will be represented as a 2-D array of r rows and c columns of characters. A . character represents a black pixel and a * character represents a white pixel. A group of white pixels are said to be connected if they share a common north, south, east or west edge (not diagonal). For example, in the following 8 x 10 image...

.........*

...**....*

..........

....*..*..

...*...*..

.......**.

....**....

..........

one such coloring would be the following...

.........a

...bb....a

..........

....c..d..

...e...d..

.......dd.

....ff....

..........

There are two groups of one pixel (c and e), three groups of two pixels (a, b and f) and one group of four pixels (d). Your program is to color the white pixels with a unique alphabetic character that identifies all the 4-way (north, south, east and west) adjacent pixels in a common connected component. Your program must implement a recursive solution to find the connected components.

2 Input

Your program will read several images from keyboard input. The following is the input format: 1. An integer n indicating the number of images that follow. 2. Two integers r and c representing the dimensions (rows and columns) of the image. 3. The image characters consisting of r rows and c characters per row. 4. A blank line will separate each image. For example, the following input is valid.

2

3 3

*..

.**

*..

8 10

.........*

...**....*

..........

....*..*..

...*...*..

.......**.

....**....

..........

When testing the program, you can directly enter the input data from your keyboard. However, it is recommended that you make a plain text file that contains input data. Open a text editor and type in the data like the above sample input. You can then redirect keyboard input to the plain text file. Here is an example of using input redirection: linux$ java Project1 < test1.txt [LOTS OF OUTPUT GOES HERE] linux$ 3 Output Output the results to the terminal/console. The output must be terse (no unnecessary characters, spaces or blank lines). For each image, the output format is the following: 1. The colored image. 2. A tabulation. Each row consists of size, a space and count. size is the number of white pixels contained in a connected component. count is the number of connected components that have the corresponding size. A row is displayed only if count is not 0. In addition, rows should be sorted by size. 3. A blank line. 2 Here is the output for the above sample input.

a..

.bb

c..

1 2

2 1

.........a

...bb....a

..........

....c..d..

...e...d..

.......dd.

....ff....

..........

1 2

2 3

4 1

Note 1: There is a blank line at the very end of the above output. Note 2: The letter assignment is not important. For example, the first image can be also colored as: b.. .cc a.. 4 Design

1. Your program can contain one class or multiple classes. Either way, there must be a class named Project1.java, which contains the main method.

2. Your program must implement a recursive solution to find the connected components.

3. Each image must be stored in some form of a 2-D array. For example, you can use a 3-D array to manage all images. The first level is for image indexing, and the second and third levels are for storing images. Another example is that you can use an ArrayList to manage all images, and each element of the ArrayList is a 2-D array to store an image.

4. The smallest image size is a 1 x 1. The largest image size is not specified.

5. There is no need to validate the input. We assume that the input data will always be correct.