Image Object Finder

Instructions

For this project you will be designing and implementing a system, in C++, to label and count the number of objects in a given image(input file). Each image consists of a number of pixels, and initially all pixels will have one of two labels, 0 and 1. 0 is considered a background pixel while a 1 represents a pixel that is part of an object. Your system will apply, over multiple iterations, the same label to pixels that are connected to form objects, and then count the number of objects for a given image. Additionally, sample input files.

Requirements:

This assignment has two parts: a design portion and an implementation portion.

Design:

For the design portion, you must generate documentation, in PDF format, describing your system and design process. The purpose of this is for you to explain not just what your system is doing, and how it is doing it, but why. You will need to justify your design decisions in a concise, informative manner. Justifications such as I did this because it was easy are not sufficient, as you should actually explain why a particular data structure or algorithm was more efficient, effective, or optimal. Additionally, commented code, while sometimes helpful in small examples, is not a sufficient explanation in and of itself. Your explanations and justifications are expected to be presented in prose and in paragraph format, i.e. not bulleted lists. Further, part of the evaluation of your design document is the apparent amount of thought and effort that went into its creation.

This document should be divided into three main parts, each with an appropriate header.

In the first part, you should describe your design process. Did you work out the algorithm on paper or a whiteboard before hand? Did you draw UML diagrams of the system? Did you create a small prototype? Did you simply start coding away and then recode once or twice with newfound understanding? In a few paragraphs, describe in detail how you went about designing the system, and be sure to provide sufficient justification of your methodology. For the second part, you should describe the data structures you used in your system. What, if any, objects or structs did you create to store data? How did you organize and manage them? What types of formal data structures did you make use of (trees, graphs, arrays, hashes, etc)? In a few paragraphs, describe in detail how you stored the various data elements in your system, and be sure to provide sufficient justification of your methodology. For the third part, you should describe functionality of your system. How is data moved and transformed? How is it read in? How is it output? What are the various major functions you constructed and how do they work? In a few paragraphs, describe in detail how your system works, and be sure to provide sufficient justification of your methodology. You might also consider including diagrams to more easily visualize how all of the pieces fit together

Implementation:

Your program must provide the following functionality and adhere to the following constraints:

• Allow the user to input the name of the file describing the image
  • This file will be a comma delimited list of pixel labels
  • All pixels will be labelled 0 or 1
  • You will need to store this information to process the image
• Every pixel needs to be examined. One by one, starting at the top left corner, and moving linearly to the bottom right corner

In the first pass:

• If a pixel is a background pixel (its label is 0), simply ignore it and move on to the next pixel
• Otherwise, check the label of the pixel above and to the left of the current pixel if they exist. There may be 3 possible cases:
  • Case 1: If the top and left pixels are background pixels or do not exist, create a new label
  • Case 2: If one is a background pixel or does not exist and the other has a label, the current pixel will be labeled the same as the labeled pixel
  • Case 3: If both the above and left pixels have different labels, assign the current pixel the smallest label and store that there is a relationship between the two labels. This will be used in the second pass.

In the second pass:

• Consider the information you saved during the first pass for case 3. Any time you find a pixel whose label has a relationship with another label, assign the current pixel the smaller value of the relationship.
• After both passes are complete, count the number of unique labels. This represents the number of objects in the image
• Output the image with the new labels and the count of the number of objects in the image Example: Input Image

Example:

Input Image: see image.

First Pass: see image.

Second Pass: see image.

All input files will be a comma delimited matrix of 1 and 0s that represent the input image. The dimensions of the matrix will be always square but size will vary.

Suggestions

This program requires the use of a few different data structures to store and represent the label within the model. First, you will need a way to store image information. This is a good opportunity to use either vectors or dynamic arrays, as you do not know how big the image is until you have read the entire input file. Additionally, updating the label from given image to the final one could be done with two grids, one for the first pass and one for the second pass. Trying to update in place may cause problems. Thus, consider using a temporary grid for image.

Requirements:

• Code for just reading the file and outputting the first case.
• Code for the whole program, which is reading the file and output the final cases (similar to the example).
• Design Document for the whole program.