==== 1st Semester: Energy Minimization using Distributed Graph Cuts ====
**Semester Topic:** Networks and Distributed Processing\\
**Group Members:** Carsten Høilund, Jeppe Jensen, and Simon J. K. Pedersen\\
**Abstract:**\\
A multitude of computer vision related tasks such as stereo scene reconstruction requires heavy computation when using naive approaches. By formulating the task at hand as an energy minimization problem the computational cost can be
reduced by applying graph cuts. The final result consists of having assigned a suitable label, e.g. a given disparity, to each pixel in an image. Even though graph cuts in many cases are faster than existing methods for energy minimization they are still time consuming.

The computation time was decreased by distributing the workload to network connected clients. Each client works on a subset of all labels, effectively reducing the number of labels each client must evaluate. Label configurations calculated on different computers were merged in order to obtain the final disparity map.

The computation time was in practice reduced by 50.00 % when using three clients. Additional clients only resulted in minor time improvements. The upper bound of theoretical performance increase was found to be 58.82 %. The error, measured in percentage of bad matching pixels (PBMP), was on average 2.37%for the distributed implementation while it for the original implementation was 2.27 %. The standard deviation increased from 0.32 to 0.37, by using the distributed  implementation. 

The potential for improvements of the total computation time increased with the number of labels and clients. In relation to the theoretical performance increase the implementation reached an efficiency of 85.00 %. Differences in accuracy were primarily observed at object boundaries. The main contribution of this paper is a 50.00 % speed increase of energy minimization via graph cuts by using the distributed implementation solely at the cost of a slightly larger variation in PBMP.