An Adaptive Regular Structure for Web
7.2 Creating the ExploreMaps graph
The input scene is assumed to have a geometry, used for view discovery, as well as a shaded representation, used for high quality rendering. The only assumptions made on the geometric representation is that its bounding box is known, that it can be rasterized producing depth and normal buffers, and (optionally) has a preferential up vector (+Y by default). The explicit definition of the up direction can be removed by employing an unsupervised upright direction solver for man-made objects [Fu 08,Jin 12]. The shaded representation, instead, is any
Chapter 7.ExploreMaps: Efficient Construction of Panoramic View Graphs of Complex 3D
Environments
85
description of the same scene that can be given as input to an external high-quality renderer. In the simplest form, it consists of the geometric representation enriched with lights and material properties.
VirtualExploration () {
Listing 7.1:Placing a set of probes to cover all visible surfaces
Listing 7.2:Moving a probe to maxi-mize the new surface seen
7.2.1 Discovering the scene
We start by formally defining the problem of exploring a scene given only its bounding box and an abstract method for rasterizing the geometry. Let v = {v0, . . . , vn 1}be a set ofn probes,S the entire input surface to be discovered, S(vi)✓Sthe portion of surfaceseenby probevi, andS(v) = S
8vi2vS(vi). With this notation, the exploration problem is posed as the problem of finding a set of probesvsuch thatS ✓S(v). We say that a set of probes satisfying this condition iscomplete, which means it sees the whole input surface. Note that we do not have prior knowledge ofS, which must bediscoveredby the algorithm.
Figure 7.2: Finding probe positions.Occlusion surfaces and occlusion volumes.
7.2.1.1 Incremental algorithm
Our incremental algorithm, see Listing7.1, starts with an empty set of probes and, at each iteration, adds a new probe and optimizes its position so that it sees a portion of the surface not visible from previous probes, until the coverage is complete1. Fig. 7.2illustrates a 2D example of an object, with two probes, the portion of surface seen, and the occluded surfaces Os(vi), i.e., the surfaces
1Note that, while in this paper we focus on complete automation, the method could also start with user-defined set of probes, e.g., to force inclusion of semantically relevant/nice shots in the graph
Chapter 7.ExploreMaps: Efficient Construction of Panoramic View Graphs of Complex 3D
Environments
86
joining the discontinuities ofS(vi). The occluded volume for a probe,Ov(vi)is the (infinite) region of 3D space non visible fromvi and the occluded volume from a set of probes is the intersection of the single viewing volumesOv(v) = T
vi2vOv(vi). Finally the occluded surfaces of a set of probes,Os(v)is the union of the single occluded surfaces intersected with the occluded volume: Os(v) = S
vi2vOs(vi)\Ov(v). The occluded surfaces are typically used as candidate locations to place the next probe [Wils 03] as a way to look “behind the corner".
It is easy to prove that if we found a set of probesvsuch that the occluded surface is empty, it means that all the reachable surface is seen by some probe, that is: if Os(v) =;thenS(v) =S. Since we are interested only on the surface reachable from the outside, placing the first probe outside the scene bounding box is a sufficient initialization (PlaceFirstProbe()).
Figure 7.3: Optimizing probe positions. Illustration of the view optimization algorithm. (a) Probev1is added on the occluded surfaceOs(v0); (b) the new surface portion seen byv1and its barycenterbare shown; (c) the probe is moved tob, and visible surface and barycenter are recomputed; (d) the probe ends up on the barycenter of the surface seen.
7.2.1.2 Finding a new probe position
The position for placing a new probe (PlaceNewProbe()) is chosen at random in the current occluded surface. This is a common choice for many view planning strategies, as it guarantees that some new portion of the surface that will be seen.
We then start an iterative optimization algorithm, described in Listing7.2. At each step, the algorithm tries to maximize the area of the surface seen by the new probe and unseen by previous ones. This is done by iteratively moving the probe position towards the barycenter of the surface visible from its current position (MoveTo(b)). If this is not possible because the segment connecting the current position andbintersects the surface, the probe is put halfway between the current position and the intersection point. This strategy, reminiscent of Lloyd relaxation [Lloy 82], ends when an equilibrium position is reached, i.e., when the barycenter of the surface seen is the same as current position itself (up to a small threshold). The approach implicitly assumes that the probe is at the interior of a closed surface, e.g., inside a building, since, otherwise, the location of the barycenter of the unseen surface would tend to be too close to the surface
Chapter 7.ExploreMaps: Efficient Construction of Panoramic View Graphs of Complex 3D
Environments
87
itself, or even collapse onto it. We therefore artificially bound the scene with a spherical background object, used by the discovery algorithm, but ignored in the final panoramas. Figure7.3illustrates the positioning of a probe, from its placement on the occluded surface to the convergence of the algorithm. The situation depicted in the example is fairly common. We can see that a probe
“entering” in a room tends to position itself at the room’s center. Note that not all the surface seen by the new probe during the first steps of the optimization will be visible also from the final position (see the portion indicated by a red arrow in Fig.7.3.(d)).
7.2.2 Optimizing the set of probes
Our exploration algorithm finds a set of probes that globally guarantee the full coverage of the reachable surface (see Figure 7.4, left). While in principle we could build a graph over this set, we infer a new graph that also takes into account perceptual criteria, in order to enhance user experience. This is done by clustering the set of probes obtained by the exploration phase and replacing each cluster with a representative probe so that the resulting graph is almost equivalent in terms of coverage butbetterin terms of browsing.
Figure 7.4: Resulting probes.Left: result of Virtual Exploration; middle: two clusters highlighted;
right: synthesis of the clusters.
7.2.2.1 Probe Clustering
The clustering is performed by applying the Markov Cluster Algorithm (a.k.a.
MCL [Van 08]), with default power and inflation parameters (e = 2,r = 2) to the coverage graph. MCL is a well known randomized algorithm that finds out naturalclusters of nodes in a graph. The key idea is that when you take random walks starting from a node, it is more likely that you stay in the same cluster of the starting node than you jump to another cluster. MCL can use weights on the arcs (i.e., the weight determines how likely the arc is crossed in the random walk), and we assign the weights as the amount of overlap in visible surface between the two probes connected by the arc. This will tend to cluster together
Chapter 7.ExploreMaps: Efficient Construction of Panoramic View Graphs of Complex 3D
Environments
88
probes that see the same area. The algorithm terminates when it reaches a steady state, obtaining a number of clustersc0. . . cm. Two examples of these clusters are shown on Figure7.4(middle). In a second phase, we find thesynthesisof each clusterci, i.e., a single new probe that sees most of the surface seen by all the probes in the cluster, while providing a significant panorama in terms of perceptual criteria.
7.2.2.2 Stability Criterion
Secord et al. [Seco 11] introduce criteria for assessing the quality of a view with the purpose of automatically defining the best point of view in a perceptual sense. However, there are important differences with our case, because we must support general object viewing, including exploration of indoor scenes, while the metric proposed in [Seco 11] is only concerned with the object-in-hand paradigm, assuming that the object silhouette is entirely visible. This means that attributes concerning the projected surface area, silhouette and semantic (see [Seco 11]) are hardly applicable in our case, and the linear goodness function they propose would reduce to:
whereM axdepthis the maximum depth value,His the normalized histogram of the depth values and↵ and are[0,1]weights to combine the two metrics.
However, it is easy to verify that these criteria alone could lead to unnatural positions. A clear example is a point of view “behind” a column, from where there may be large maximal depth and uniform depth distribution, but where the feeling is to hide behind a column and not exploring the scene. Therefore, we weightG(v)with thestabilitySt(v)of the point of viewv, leading to a goodness function
Gs(v) =G(v)·St(v)
We say that a point of view is stable if the view does not change much with respect to the neighborhood. In the previous example, it is clear that a position behind a column (that is, near to an occluder) is not stable because a small displacement would unveil a large part of the scene. In order to formalize this idea, we define a distance function between two points of view v and w as (v, w) = max{ (v, w), (w, v)}, where (v, w) = Diff(Pw(S(v)), D(w))),S(v) is the 3D surface seen fromv,Pw(.)is the projection of a 3D surface onw,D(.) is the depth map from a point of view andDiff(., .)is the number of different depth values in the comparison between two depth maps. We thus define the stability of a point asSt(v) =maxw2N(v){ (v, w)}, whereN(v)is a set of point
Chapter 7.ExploreMaps: Efficient Construction of Panoramic View Graphs of Complex 3D
Environments
89
nearv. In our system we used the points distributed on the sphere centered atv with radius equal to the distance of thenear planeused to produce the panoramas.
7.2.2.3 Probe synthesis
The synthesis step starts from the position of the probe within the cluster that has the largest coverage of the surface seen by all probes in the cluster. We then perform a local randomized search using asimulated annealingapproach, which applies small random perturbations of a probe’s position, with an objective function that combines the coverage and the perceptual metric using a weighted average. Upon convergence, using the same perceptual metric, we determine a small set of orientations for each probe that will serve both as preferred arrival orientations when the user move to the probe, and as thelook-atorientation used when generating thumbnails to represent the probes in a navigation application.
Best orientations for each view are selected by finding the dominant peaks in the goodness function with mean-shift clustering [Coma 02]. The up vector for the data-set, if present, is used to avoid upside-down views.
7.2.3 Connecting probes
Once we have the new set of probes, we have to define which probes must be connected with an arc and the geometric path that connects them. One simplistic choice would be to connect two probes if they are mutually visible from each other. This solution is definitely not acceptable, since it would drastically reduce navigation possibilities. For instance, see Fig. 7.5, a probe in a room may not necessarily directly see a probe out of the window, nonetheless the transition from the first to the second makes perfect sense. More generally, view planning does not even guarantee that nearby probes are in general mutually visible. A smarter choice would be connect probes that see a common point in the surface.
Even though this strategy would perform much better, it is easy to see that a number of common cases break the same rule (see, e.g., the same example in Fig.7.5). We have thus decided toconnect two probes if there exists a point in space that is visible from both of them. which generally leads to a meaningful set of arcs (see Figure7.5right and accompanying video). The technique for finding smooth feasible paths is explained in Sec.7.3.2.