Heap Sorting with 2D arrays. HELP!!
A Gray-level image may be represented as a 2-D array of pixels with a pixel at row (y) and column (x) having an intensity F(x,y). For an image of size N x N pixels, the values of x and y range between 0 and N-1. The gray-level intensity F(x,y) is usually an integer between 0 and 255, with 0 representing pure black and 255 representing pure white.
Given such image, we would like to find the locations (xi , yi) and (xj , yj) of the pair of pixels (i , j) having the closest intensities F.
The problem can be solved by different methods. The following is an efficient method:
Sort the pixels according to their intensities. After the pixels are sorted, the closest pair will lie next to each other somewhere in sorted order. Thus a linear-time scan through them completes the job. Sorting using HeapSort will cost O(N log N) and the scan will cost O(N) so that the total cost is O(N log N) + O(N) = O(N log N).
Required Implementations:
1. Implement the PQ (minimum Heap) class.
2. Implement the HeapSort algorithm using the above class.
3. Implement a program to do the following:
• Generate a 2-D array representing an image of size N xN (a typical value of N is 128) with random integer intensities F(x,y) in the range 0 to 255.
• Use HeapSort to sort the intensities.
• Use a linear scan to determine the locations of the pixel pair having the closest intensities.
• Display a sample output.
Given such image, we would like to find the locations (xi , yi) and (xj , yj) of the pair of pixels (i , j) having the closest intensities F.
The problem can be solved by different methods. The following is an efficient method:
Sort the pixels according to their intensities. After the pixels are sorted, the closest pair will lie next to each other somewhere in sorted order. Thus a linear-time scan through them completes the job. Sorting using HeapSort will cost O(N log N) and the scan will cost O(N) so that the total cost is O(N log N) + O(N) = O(N log N).
Required Implementations:
1. Implement the PQ (minimum Heap) class.
2. Implement the HeapSort algorithm using the above class.
3. Implement a program to do the following:
• Generate a 2-D array representing an image of size N xN (a typical value of N is 128) with random integer intensities F(x,y) in the range 0 to 255.
• Use HeapSort to sort the intensities.
• Use a linear scan to determine the locations of the pixel pair having the closest intensities.
• Display a sample output.
Topic archived. No new replies allowed.