CSE222-Homework 5 Max Priority Queues for Color Pixels Solved

Imagine a color digital image of width W and height H. You can use any online software library in order  to load it into your program. Once you load it, it will be represented as a 2D array (with W columns and H rows) of 3D 8bit unsigned integer valued vectors. Each element of this 2D array will correspond to a color point (or pixel) in this image. Each color pixel is made up of 3 integer values in the range 0-255, inclusive. The first dimension corresponds to the amount of red in that color, the second dimension to the amount of green in that color and the third dimension to the amount of blue in that color.

OBJECTIVE: we want to construct max priority queues for color pixels. We want to enter those pixels one by one into priority queues, and then extract them according to different priority schemes (or ordering relations).

INPUT: your program will admit as command line input a color digital image’s path (in either png or jpg format).

HOW: Your program will support 3 vector (or color) comparison methods: lexicographical comparison (LEX), Euclidean norm based comparison (EUC) and bitmix comparison (BMX).

-  LEX: standard lexicographical comparison from discrete math.

-  EUC: whichever vector has the greater L2 norm is considered greater (this is actually a preordering relation since it’s not anti-symmetric but that’s ok for this context). - BMX: read section 3 of the attached pdf.

Your program will have 4 threads (study the online thread tutorial of Java on how to create and start them).

Thread 1: responsible for reading the pixels from the image starting from the top-left corner and advancing column first until the bottom-right pixel. Every color pixel read, will be inserted to each of the 3 priority queues (named PQLEX, PQEUC and PQBMX: one per ordering relation). As soon as the first 100 pixels are inserted, it will create and start the following 3 threads, and then continue inserting the remaining pixels.

Thread 2: will remove from PQLEX the color pixels and print them on screen one after the other, up until a total of WxH pixels are printed.

Thread 3: will do the same as Thread2 but it will use PQEUC.

Thread 4: will do the same as Thread2 but it will use PQBMX.

Note on threads 2, 3, 4: careful, if the PQ that is being processed by a thread happens to be temporarily empty, and the number of pixels it has processed so far is less than WxH, then it must wait without keeping the CPU busy (e.g. without constanly checking if there is an element in the priority queue). Hint: take a look into the producer consumer problem.

Note: if thread 1 tries to insert a value into a PQ run by thread X while thread X hasn’t completed its removing method from it, all hell will break loose, and the PQ will become corrupt. Similarly, thread X must not try to remove from its PQ anything while thread 1 hasn’t completed inserting into it. Hint: take a look into java’s synchronized keyword.

OUTPUT: all your output will be at the terminal, threads 2, 3, 4, will print out WxH 3D color pixel values, in the order that they are extracted from their corresponding PQs, and thread 1 will print the pixel values in the order that they inserted:

e.g.

Thread 1: [100, 50, 200]

Thread 1: [78, 11, 111] //... etc inserting all the way to at least the first 100 pixels..

Thread2-PQLEX: [255,45,178]

Thread 1: [99, 1, 77]

Thread4-PQBMX: [255,234,128]

Thread3-PQEUC: [255,247,198]

…

[The above values are imaginary].

It is up to the OS to determine which thread will run how many times before yielding its priority to another thread. Maybe thread 2 will run 300 times before switching to thread 1, or 200 times before switching to thread 4, etc. If everything goes fine, each thread must print out exactly WxH pixels.