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

Ona Fast Implementationofa2D-Variant of Weyl’sDiscrepancyMeasure Christian Motz1 ,BernhardA.Moser1 Knowledge-BasedVision Systems SoftwareCompetenceCenterHagenberg,Austria christian.motz@scch.at, bernhard.moser@scch.at Abstract Applying the concept of Hermann Weyl’s discrepancy as image similarity measure leads to outstand- ingrobustnessproperties fortemplatematching. However, incomparisonwithstandardmeasuresthis approach iscomputationallymore involving. Thispaperanalyzes thismeasure fromthepointofview of efficient implementation for embedded vision settings. A fast implementation is proposed based on vectorization of summed-area tables, resulting in a speed-up factor 16 compared to a standard integral imagebased computation. 1. Introduction In this paper we take up a novel concept of similarity measure due to [1] and investigate its applica- bility for the requirements of embedded vision. The core idea of this measure is its design principle based on a family of subsets rather than evaluating the aggregation of point-wise comparisons on a pixel-by-pixel level. Incontrast topixel-by-pixelbasedapproacheswithsubsequentcommutativeag- gregation such as mutual information of normalized cross correlation the subset-based approach also takes spatial arrangements into account which makes this approach interesting for pattern analysis andmatchingpurposes [2]. ThismeasuregoesbacktoH.Weylalready100yearsagoandwasstudiedin thecontextofevaluating the quality of pseudo-random numbers and measuring irregularities of probability distributions [3]. Forone-dimensional signals (vectors) it isdefinedas ‖(x1, . . . ,xn)‖D= max 1≤a,b≤n | b∑ i=a xi|= max r {0, r∑ i=1 xi}−min s {0, s∑ i=1 xi} Interestingly, this measure not only plays a central role in discrepancy theory which is related to low complexityalgorithmicdesignbymeansof lowdiscrepancysequences [4],butas foundout recently, also inotherfieldsofapplications, e.g. inevent-basedsignalprocessing [5,6], randomwalkanalysis [7]and imageandvolumetricdataanalysisbyextending it tohigherdimensionsbymeansof integral images [1]. As pointed out in [1] the extension is not unique. A possible extension is given by Equation (1). 105