Page - 153 - in Joint Austrian Computer Vision and Robotics Workshop 2020

Figure2.Left: Setof30samplepoints intheplane. Right: Map of half-space depths w.r.t. the sample points. Points in thewhiteareaare half-space medians. amplify noise. Whereas theL1 median filter yields thevisuallymostappealingresult in thisexample, its underlying median concept relies on Euclidean dis- tances which might not be always be meaningful in applications. The Oja simplex median as well as the half-spacemediancure thisweakness(theyareaffine equivariant), with the half-space median yielding a betterdenoising result in this example. Discrete half-space median. Let us shortly recall the definition of half-space median based on [6, 11]. Givenpointsx1, .. . ,xm∈Rn, thehalf-spacedepth of a point p ∈ Rn is the minimal number of data points that can lie on one side of a hyperplane throughp. For example, the half-space depth of any poutside the convex hull of the given points is zero because there exists a hyperplane through pwhich does not split the data points at all. In contrast, if there is a p somewhere in the middle of the given points for which any hyperplane throughp splits the data set in half, it will have a half-space depth equal or close tom/2. A half-space median of the given data is then simply a point of maximal half-space depth, see Fig. 2 for an example. For discrete data sets, there is in general a convex polyhedron inRn consisting entirely of half-space medians. We will notfurtherdiscuss thisunderdetermination,however, as it playsno role in thecontinuous situation. Application of the discrete half-space median for the filtering of Rn-valued images is in principle straightforward: Aslidingwindowisusedtoselectat each pixel location a set of neighbouring pixels, and the half-space median of their values becomes the newimagevalueat thegivenpixel. Practically,how- ever, the algorithmic complexity of the half-space median computation is an issue which requires fur- therwork, see the remarks in [15]. Havingshownasyntheticexample inFigure1,we Figure 3. Left: Test image sailboat (512× 512 pixels) reduced to yellow–blue colour space. Right: Half-space median filtering result, using a discrete disc of radius2as slidingwindow,5 iterations. present the result of half-space median filtering on a natural colour image (reduced to two colour chan- nels) in Figure 3. Similar to the classical median filter for grey-value images, the iterated multivari- atemedianfilter removessmalldetailsandsimplifies contours. Notice, however, that a slight blurring of edges occurs, albeit much less than in linear filters suchasboxaveraging(with thesamewindowsizeas in the median filter) or Gaussian smoothing (with a comparable standarddeviation). Continuous half-space median. In a continuous setting, thediscretesetofdatapoints is replacedwith a density overRn, i.e., an integrable functionγwith total weight 1. The half-space depth ofp∈Rn then is the minimum among all integrals of γ over half- spaces cut off by hyperplanes throughp. Again, the half-space median ofγ is the point of maximal half- spacedensity,whichwill beunique ingeneric cases. The construction of a half-space median filter for space-continuous Rn-valued images is again a straightforward adaptation of the univariate proce- dure, with the density of image values within a slid- ing neighbourhood of each image location being the input from which the continuous half-space median is taken. Affineequivariance. Thedefinitionsofhalf-space depths and and half-space medians rely only on in- cidence relations between points and half-spaces in the data space. Affine transforms of the data space preserveallof these relations. Asaconsequence, for any such affine transform the half-space median of the transformed input data coincides with the trans- formed half-space median of the original data. This is dubbed by saying that the half-space median is affine equivariant. This property ensures that the 153