Page - 109 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

row: Πp1(x) = Πp(x) (6) Πp2(x) = { Πp(W)−Πp(x) ifx 6=W, Πp(W) ifx=W. (7) Equations (8) and (9) provide a mathematical formulation of this, in both cases c corresponds to the constant Πp(W) per row. In other words, we only need to compute a single integral image, and compute theminimum andmaximumper row,by whichwehavehalf of thecomputationdone to get thediscrepancynorm according to (1): max{Πp2(x)}= max{c,c−min{Πp1(x)}}, (8) min{Πp2(x)}= min{c,c−max{Πp1(x)}}. (9) Thethirdcomponentbehavessimilar to thesecondone—theonlydifference is that theconstantnow is per column and we need the maximum and minimum for each column. Unfortunately, the fourth and last component is more complex. Here, each value is based both on the last value per column and the last value per row. The problem is that for normal maximum or minimum we only take care of numbers that are larger or smaller but not the equal ones. Yet, for the problem mentioned above, we would need all maximized subexpressions with the same value and their corresponding position consistingof thexandy indexpair. Further research isnecessary tocheckwhether theminimumand maximum of the fourth component could be determined in a more convenient and less complex way. However, a subexpression refers to the third component and only one addition is necessary to get the fourthcomponent. 2.2. Proposed algorithm Based on the previous findings, we will now consider the complete algorithm and compare it to the base implementation in termsof runtimecomplexity. Thebasealgorithmconsistsof fourpassesover the data; each will compute one integral image component and, simultaneously, yield minimum and maximum by compare operations. The optimized version consists of only two passes. The first pass will calculate one integral image and get the first and the second component at the same time. Here, the second component needs a small overhead at the end of each row. The second pass will deduce the thirdand fourthcomponentbasedon thepreviouslycomputed integral image. Basically, both versions haveO(n ·m) complexity, wheren is the image width andm the image height. If we take a closer look at it, the proposed version hasO(2n ·m), compared to the initial O(4n ·m). The optimized version will show further improvements if we consider the number of operations more precisely. Additions and subtractions will be considered as the same operation from the view of complexity. The base version has four very similar passes, consisting of integral image computation and comparisons. Computing an integral image point takes three additions, though, there isanoptimizedversionneedingonly twowhich requiresextra storage forcumulative rowsums [13]. The reference version from [14] is implemented with three operations and will be used for real performancecomparison. Table1comparesbothversion in termsof theoverall operationcount. Additionsare reducedheavily down to less than a half. Comparisons are brought down by a fourth approximately. As each pass consistsofadouble-nestedloopthatproducesoverhead, thecolumnPasses isveryimportant. Another 109