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

put the points into the existing region, because we would not be able to get from one argmin to another via a monotonic path. Instead, we need to add a new region foreach individualdale. Both cases can be dealt with by contracting con- nected points into their connected component, and creating a new region for each resulting component. Thiswill ensure thatplateausareassigned toasingle region. As the water rises, we can add points to an exist- ingregiongrowing itupwards if theyare justoutside the region1. Otherwise they correspond to a distant local minimum and have to be dealt with as before, by opening a new region for each point (or rather, eachconnectedcomponent). This is showninFigure 4, Image2. With the water rising further still, the regions will grow upwards to a point where they meet (Figure 4, Image 3). Any such point is a saddle point, and we have to account for it the next time we want to grow any one of the touching regions. The saddle point connects the edges of the regions which meet in it, at the current height of the water level. It might be the case that the not-yet-assigned points (the ones above the water) get separated into multiple con- nectedcomponents,or theymight remainconnected. If thepoints remainconnected, thenwedecide for a single one of the involved regions to be allowed to grow upwards from the component. This means that one region effectively inherits the growth direc- tions from the other region(s). The other region(s) lose their potential for expansion and remain frozen in their current state. If theunassignedpointshavemultiplecomponents (as in Figure 4, Image 3: the unassigned grey points are separated into the lower left and upper right ar- eas), then we may assign one component to each in- volvedregion. Theregionswill thengrowonlyin the directionsdeterminedbytheassignedcomponentsas the water rises. This can be observed in Figure 4, Image 4: The green region is allowed to grow to the lowerleft,while theredregionfloodstheupperright. The same procedure of swapping areas of expansion alsohappensaswemovefromImage5 to6. Anyre- gionwithoutanassignedcomponent remains frozen. 1Why canwe do that? Byadding onlypoints which arecon- nectedtotheregionweensurepath-connectedness,andbygrow- ing the region upwards, we can construct ascending paths from old points to new ones. The smoothness of the surface guaran- tees that while moving at a fixed height, we can reach all points of the regionwith thatheight. Should there be more components than regions, then weopenupanewregionforeachsurpluscomponent, as in the topof Image7. An oddity which can occur are self-loops: A re- gion might grow into a ”C”-shape, and then proceed to close up into an ”O”-shape. This case can be treated similarly as above, the only difference is that thesaddleisfoundbyrecognizingthat theregioncol- lideswith itself, notwithanother region. Eventually this procedure will arrive at the global maximum,and theentire surfacewillbedivided into regions. Since we proceeded with the necessary care and attention along the way, we ensured that the re- gions remained slope regions, and we also only cre- ated additional regions when we absolutely had to, showing that the resulting composition is maximally coarse. The same algorithm can be applied in higher di- mensions. We deal with iso-hyper-surfaces as level sets, but the topological considerations about con- nectedness remain the same as in the illustrative 2D case. 5.DiscreteBP ThesomewhatvaguedescriptionofBPin thepre- vious section assumed a continuous surface. In most applications, however, the data will be provided in a discrete raster format. Some intricacies arise from this discretization, most notably iso-surfaces of a smooth function f will not have a straight-forward representation in the discrete grid obtained from ras- terizing f. The data structure we use is a set of in- dices, representing the positions in the discrete array alreadyassigned toa region. Each region also has a set of (yet) unassigned points, which determine where the region might growin thenext iteration, called theborder. This ef- fectively models the smooth levelsets in the discrete representation. The pseudo-code for the algorithm is printed below, the executable python code can be accessed in our github repository: https://github.com/SirFloIII/MustererkennungLVA 6.FurtherPotential Development The result of BP is satisfactory, but we assume that improvements can be made in running time. The code was profiled multiple times and has been adapted to run faster with significant gains in many instances. 141