Faculté de génie Faculty of Engineering
d’informatique Engineering et de génie électrique and Computer Science
Problem Description :
This assignment asks you to implement solutions to the optimal assignment problem. We look at in the context of visual face tracking. We assume that we have implemented some neural network-based face detector which in each video frame detects all faces in the frame. Below is an example from the face detector running in a House-of-Commons recording.
© Cable Public Affairs Channel Inc. (“CPAC”)
We get therefore a list of detected faces in one frame and another list of faces in the next frame. We would like to know which face in the list of the first frame matches which face in the second frame. Our matching algorithm is to find the optimal match of faces based on some criteria. A simple criterion is the Euclidian distance between the centre of the first detection. Consider the following simple example with only 3 detected faces in each frame. Frame 1:
Face Label Upper-
Corner Width in
X Height in Y
X Y
100 80 41 52
B 300 392 32 45
C 405 160 28 31
Face Label Chat: orcsUpper- Width in X
C Height in Y
X Y
I 300 120 43 51
II 312 236 28 40
III 395 241 25 30
Frame 2:
Based on these detections and the Euclidean cost function between the box centers, we can construct a 3×3 table. We round the cost to integer values which prevents issues with floating point calculations.
I II III A
205 254 324
269 159 183
102 123 81
B
C
We could now simply try all possible assignments:
{(𝐴, 𝐼), (𝐵, 𝐼𝐼), (𝐶, 𝐼𝐼𝐼)}, {(𝐴, 𝐼), (𝐵, 𝐼𝐼𝐼), (𝐶, 𝐼𝐼)},
{(𝐴, 𝐼𝐼), (𝐵, 𝐼), (𝐶, 𝐼𝐼𝐼)}, {(𝐴, 𝐼𝐼), (𝐵, 𝐼𝐼𝐼), (𝐶, 𝐼)},
{(𝐴, 𝐼𝐼𝐼), (𝐵, 𝐼), (𝐶, 𝐼𝐼)}, {(𝐴, 𝐼𝐼𝐼), (𝐵, 𝐼𝐼), (𝐶, 𝐼)}
In our example, we have an optimal solution {(𝐴, 𝐼), (𝐵, 𝐼𝐼), (𝐶, 𝐼𝐼𝐼)} with a total cost of 445.
There are 3 ∗ 2 ∗ 1 possible assignments, or in general 𝑛 ∗ (𝑛 − 1) ∗ … ∗ 1 = 𝑛! In other words, trying all possibilities with a large number of detection becomes, very quickly prohibitively expensive to calculate.
Fortunately, there is a much more efficient algorithm which run 𝑂(𝑛^3). It proceeds in five steps:
1. Row reduction
2. Colum reduction
3. Test for an optimal assignment, if an optimal assignment is found, go to step 5
4. Shift zeros, go to step 3
5. Making the final assignment
The most difficult part of the algorithm is finding the minimum lines to cover all 0 in step 3. Below is pseudocode for this step with its 5 sub steps.
// 3.a
// This is the same as step 5 assuming we always pick the first 0 for r in rows first = true for c in cols if A(r,c) = 0 if first
if A(rr,c) = 0 and r != rr
A(rr,c) is crossed out
else
A(r,c) is crossed out
// 3.b
// 3.b
// Ticking cols for r in rows if not(tick( r )) continue: for c in cols if A(r,c) is crossed out tick( c ) = true
// 3.c
// Ticking rows again
// 3.d
// Go back to step 3.b unless no new ticks were made
// 3.e
// Draw lines for all ticked columns and all unticked rows. for r in rows if not(tick(r)) line(r) = true else line(r) = false
for c in cols if tick(c)
line(c) = true else line(c) =
Create the classes needed to solve the visual face tracking problem based on the Hungarian algorithm as exactly as described above. Your program must be a Java application called FaceTracker that takes as input the names of two files containing all detections for two frames as csv files. Your program must print the optimal assignment to a csv file called tracker_java_n.csv where n is the size of in the problem. The file should have n rows and 2 columns corresponding to one match per row and the id of the detection in the two columns (see the attached example). The file is to be saved in the current directory. If there is more than one optimal assignment, your implementation must simply return one of them. If the number of detections is not the same in each frame (i.e., your cost matrix would not be square), your implementation can simply throw an exception.
numbers covered by lines after step 3. Your implementation must also save the initial cost matrix to a csv-file.
The above cost function is the Euclidean distance. You must design and use at least one alternative cost function which the user can select, e.g., matching the area of the detected boxes or the aspect ratio of the box or any combinations of criteria. Give an equation how you calculate the cost along with your UML diagram.
In addition to the source code, you must also submit a UML class diagram showing all classes, their attributes, methods, and associations. Hand-drawings are not acceptable (if you are looking for a drawing program, you can use draw.io). You can not use static methods (except main).
Create the following Prolog predicate
hungarianMatch( CostMatrix, OptimalAssign, OptimalCost )
that is true if the Hungarian matching problem with the given cost matrix by the optimal assignment with an optimal cost.
Create also the following two Prolog helper predicates, to read the cost matrix (as in the attached example) and to save one optimal assignment, respectively.
readCostMatrixCSV( “face_cost3.csv”, CostMatrix ) saveOptimalAssignment( OptimalAssign, “tracker_prolog_3.csv”)
Create a Scheme function that implements the Hungarian algorithm. Your Scheme application is to read a cost matrix from a csv file. Your function prototype must work as follows:
CSI 2120 page 8
(hungarianMatch (readCostMatrixCSV “face_cost3.csv”)
“tracker_scheme_3.csv”)
((“A” “I”) (“B” “II”) (“C” “III”))
Your function takes as input the cost matrix and a file name to save the optimal assignment to as a side effect. The format of the csv file should be the same as in Part 1. It is suggested that you use tracker_scheme_n.csv where n is the size of in the problem as a file name. As for Part 1, your implementation must print the cost matrix at the beginning and after each step of the main algorithm. Make sure to print out the row and column numbers covered by lines after step 3.
:
