Ryan Mathewson, a student
in data structures, requested, "I have a list of at least 1 million
elements and need to find certain elements quickly. The elements are a
Double value containing the color value of every pixel on the screen. I
also have a method that will extract the Red, Green and Blue values from this
number. I need a way to find all the pixels on the screen that match a
given criteria (e.x. 134 red value, 23 green value, 255 blue value, or
preferably near those values)."
Perhaps the student has other criteria, such all the all the pixels with
a specified red value but not a specified green value.
Although an image is a 2 dimensional structure it is generally represented by a 1 dimensional array. See PixelGrabber in Java API. We will call the image arrary, the image array. To save space the red, green, and blue (RGB) value are store in a single long integer or double.
Because this is a course in data structurss and not graphics, we will assume that the RGB values have already been extracted, and we have three integer image arrays for an image, a red image array, a green image array, and a blue image array. The indices will retain their association with the original image array. Meaning that for array image index, i, then red[i], green[i], and blue[i] will all refer to the same pixel. The arrays specify the amount red, green, and blue at a pixel. By specify the only the red, green, and blue (RGB) values of the pixel, we can express all the colors that a monitor can produce. Typical we express the range of RGB as integers from 0 to 255. This gives enough resolution to make the colors seem continuous to the human eye. So we will assume the RGB image arrays have integer values from 0 to 255.
If we know nothing about the image, I do not think that we can do better then the naive approach of iterating through the image arrays and selecting the indices that match the specified target color, which would have cost O(n), where n is the size of image, number of pixels. But if we are to perform this operation multiple times with different target colors, then with an additional data structures and algorithms we can perform the operation faster. The idea is if we do some work up front (before the actual operation), and use additional space then we can perform the operation quicker for latter requests. In other words the first time we try to find all the pixels matching the color the cost is higher, but for the second, third etc. requests for finding pixels that match the target colors cost us far less. This technique is called preconditioning.
The problem would be easier to solve if we had a data structure that gave us image pixel indices that had a specified red value, also specified green value, and blue value. This suggest using three dictionaries, one for red, green, and blue, which are keyed by the red value, green value, and blue value. The value of the dictionary will be the image indices. We will call the dictionary redValue2IndicesDictionary, greenValue2IndicesDictionary, and blueValue2IndicesDictionary. I think that it will be obvious to you that the correct implementation of these dictionaries is hash tables using separate chaining. The size of the bucket array, N, will be 256. The total additional space cost for the three dictionaries is O(n).
So the preconditioning step will be to iterate through the image RGB arrays inserting into the three dictionaries. The cost for the preconditioning step is O(n).
Now we need to select the indices that have RGB values that match the target RGB value. The naοve approach would be to get the chain associated with the specified red value from the redValue2IndicesDictionary, and then check each the other two image arrays that the pixel have the target green and blue value. Assuming that the each pixel has equal probability for any of the RGB values then the cost would be O(n/256). Why?
We can not do much better, but we can organize the process, so that the different types of selections can be performed. For example assume we want all pixels that have specified red value, or a specified green value, or a specified blue value. Maybe we want all the pixels that have a specified red value but not a specified green value, etc. Note that these are set operations on three sets specified by the chains from the three RGB Values to Indices Dictionaries.
To simplify the problem we will assume that the image is composed of only two colors, red and green. For example assume that we wanted to find all the image indices that matched a specified red and green value, this corresponds to an intersection between the two chains. If there was no order to the entries in the red and green chains then for each index value in the red chain we would iterate through the green chain to find a matching index. This would cost O(nred*ngreen), where nred, ngreen are the length of the red and green chains. If the chains are sorted by the index values then we can do better, O(nred+ ngreen).
The technique uses an algorithm called merger. I will illustrate the merge for intersection.
List intersectMerge(Iterator redItr, Iterator greenItr)
// inputs two iterator representing sets,
// the iterator return the sentinel END when they have reached the end
// also the iterators are sorted in ascending order
// output a list, which is the intersection of the two sets.
Make List list
red = redItr.next
green = greenItr.next
While red and green are not END do
If red < green then
do nothing
red = redItr.next
Else if red = = green then
add red to list
red = redItr.next
green = greenItr.next
Else // green < red then
do nothing
green = greenItr.next.
While red.hasNext do
do nothing // the same as what you did for red < green
red = redItr.next
While green.hasNext do
do nothing // // the same as what you did for green < red
green = greenItr.next
This algorithm has a lot of statements that do nothing. Why? Because I want to illustrate the similarity between the other two set operations, union and subtraction.
List unionMerge(Iterator redItr, Iterator greenItr)
// inputs two iterator representing sets,
// the iterator return the sentinel END when they have reached the end
// also the iterators are sorted in ascending order
// output a list, which is the union of the two sets.
Make List list
red = redItr.next
green = greenItr.next
While red and green are not END do
If red < green then
add red to the list
red = redItr.next
Else if red = = green then
add red to list
red = redItr.next
green = greenItr.next
Else // green < red then
add green to the list
green = greenItr.next.
While red.hasNext do
add red to the list // the same as what you did for red < green
red = redItr.next
While green.hasNext do
add green to the list // the same as what you did for green < red
green = greenItr.next
Finally for red subtract green set operation:
List subtractMerge(Iterator redItr, Iterator greenItr)
// inputs two iterator representing sets,
// the iterator return the sentinel END when they have reached the end
// also the iterators are sorted in ascending order
// output a list, which is the red - green
Make List list
red = redItr.next
green = greenItr.next
While red and green are not END do
If red < green then
add red to the list
red = redItr.next
Else if red = = green then
do nothing
red = redItr.next
green = greenItr.next
Else // green < red then
do nothing
green = greenItr.next.
While red.hasNext do
add red to the list // the same as what you did for red < green
red = redItr.next
While green.hasNext do
do nothing // the same as what you did for green < red
green = greenItr.next
Do you see all the similarities of the different merges? Why write three different classes representing each operation? You would have three types the debugging to do. What we should do is write an abstract class, an abstract class has methods that are not defined or methods that do nothing. Our abstract class, GenericMerger does have one defined method, in particular the method which is the template for the three set operations, listed below:
List templateMerge(Iterator redItr, Iterator greenItr)
// inputs two iterator representing sets,
// the iterator return the sentinel END when they have reached the end
// also the iterators are sorted in ascending order
// output a list, which is sorted and the result of the set operation
Make List list
red = redItr.next
green = greenItr.next
While red and green are not END do
If red < green then
doRedIsLess(red, list)
red = redItr.next
Else if red = = green then
doRedGreenEqual(red, green, list)
red = redItr.next
green = greenItr.next
Else // green < red then
doGreenIsLest(green, list)
green = greenItr.next.
While red.hasNext do
doRedIsLess(red, list) // the same as what you did for red < green
red = redItr.next
While green.hasNext do
doGreenIsLess(green, list) // the same as what you did for green < red
green = greenItr.next
The methods doRedIsLess, doRedGreenEqual, and doGreenIsLess do nothing in the GenericMerger class. Then the intersectMerger, unionMerger and subtractMerger extend GenericMerger by overloading the do nothing methods; doRedIsLess, doRedGreenEqual, and doGreenIsLess, with the function they need to do.
This technique of using a generic class to define a template that others class extend and make specific is so common that it is given a name in software engineering, the template design pattern. Please read the Set ADT in your text book for the details.
The goal of this assign is to you experience making hash tables using separate chaining, they are easy, and writing the template design pattern. To make the assignment easier we will assume that the image has only two colors, red and green.
The red values for input will appear first followed by the green values:
red5
255
5
20