Please contact me for more details
Quadtrees are created from images whose sizes are integer powers of 2. Each node of the quadtree corresponds to a square area in the binary image. The node at level 0 of the tree corresponds to the whole image area. Child nodes correspond to the areas given by dividing the image into 4 non-overlapping quadrants. The quadrants are denoted NW (north-west), NE (north- east), SE (south-east) and SW (south-west) respectively.
1. Read a square binary image from a text file into an array structure,
2. Generate a pointer based quadtree from the binary image,
3. Traverse through the pointer based quadtree and print out for each black terminal node the position of the top left of the quadrant and its size.
The program must read the image data from a text file which contains coded information on the size of the image and the number and position of black pixels in the image. The image file contains integers and the file has the following format:
image width in pixels
number of black pixels
x y location of each black pixel
For the example of the image in Figure 1, the file would contain the data shown in Figure 3. You can assume that the image size will never exceed 64 columns by 64 rows.
8 15 41 51 22 32 42 52 23 33 43 53 44 54 64 45 55
Figure 3: Input file example
Use an integer array as an intermediate data structure to help in generating the pointer based quadtree. Producing the pointer based quadtree involves taking the array and generating a node to represent it. The array can then be tested for colour uniformity. If it is not of a uniform colour then the array must be divided into four quadrants and nodes created for these. Each quadrant must then be tested and the same process recursively performed until all terminal nodes of the tree represent uniformly coloured areas. Internally your program should represent each node of the quadtree as a struct datatype containing 9 fields. The first five pieces of information are pointers to the parent, P, and four children of the node (NW, NE, SE, SW), the next piece of information is the colour of the node (i.e. B, W or G), and the final three pieces of information are the size and centre coordinates of the block of pixels that the node represents.
Your program should read data from a file with path specified using a command line parameter.
This parameters should be the only parameter expected by the program, and should be required to be specified immediately after the executable name at run-time e.g. quadtree
[url removed, login to view]
The input file will contain the image data in a format as illustrated in Figure 3 and in the example
file [url removed, login to view] provided.
Your program should print out on the screen the list of all terminal black nodes. The output should indicate for each black terminal node the position of the top left of the quadrant and its size. For example, the output of processing the example file [url removed, login to view] provided on is shown in Figure 4. It should be noted that there is no specific requirement in terms of the order in which the black terminal nodes are printed out. Therefore any output where
the lines shown in Figure 4 are permuted would be equally valid.
Black terminal node at position (2,2) with size 2
Black terminal node at position (4,1) with size 1
Black terminal node at position (5,1) with size 1
Black terminal node at position (4,2) with size 2
Black terminal node at position (4,4) with size 2
Black terminal node at position (6,4) with size 1
Figure 4: Example screen output when processing input file shown
The purpose of the procedure or function,
The description of all input and output parameters.
The deliverables for this project will be:
Program in C and Report explaining it.