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

[R2] the distance measure behaves continuously at least with respect to arbitrary small misalign- ments, [R3] an increasing extent of misalignment implies an increasing distance measure and vice versa (monotonicity). It is interesting that it can be shown that these natural properties are not satisfied simultaneously by commonlyusedmatchingandregistration techniques [1]. Figure1 illustrates its robustnessbyapply- ing this measure as fitness function for finding the best match between a reference and a test image. In thisdemonstration thediscrepancymeasure isdirectlyappliedwithoutany imagepreprocessingor denoising. As this measure relies only on the evaluation of integral images and max/min operations, it is well-suited for parallelization. An efficient implementation can be tackled by means of of the concept of a summed-area table [10] which is a matrix generated from an input image in which each entry in the matrix stores the sum of all pixel values between the entry location and the lower-left corner of the input image. For applications of summed-area table see also [11] and related concepts based on integral images e.g. [12]. The power of the summed-area table comes from the fact that it canbeusedtoperformfiltersofdifferentwidthsateverypixel in the imageinconstant timeperpixel. ThismakesSATveryuseful for embeddedvisionpurposes. The paper is organized as follows: Section 2. introduces a two-dimensional definition of the discrep- ancy norm and makes algorithmic optimizations to reduce computation effort. Section 3. presents a vectorization concept for the previously optimized algorithm. Section 4. presents the speedup achievedby the optimizations. 2. AlgorithmicAnalysis for Implementation While in the 1-dimensional case partial sums over intervals are evaluated in the 2-dimensional case rectangles are taken instead of intervals. As shown in [1] is suffices to restrict on the rectangles with one corner being coincident with a corner of the image. This suggests to use integral images spread- ing of each of the four corners of the image. However, a single integral image already contains the information of the remaining integral images from the other corners. This leads to the first optimiza- tionstepbydeducing thevalues for the four integral images fromtheoriginal integral imagewith the top left corner as the starting point. Assume pointP1 is our current index. The value at this position naturally corresponds with the first integral image in the definition of discrepancy norm. The second integral image in the definition has the top right corner as a reference. This corresponds to area II2 in the figure, which can be computed by subtracting sumsP2−P1. The third and fourth integral im- ages are very similar. Equations (2) to (3) provide a mathematical formulation of the integral image 107