{'fraction_non_alphanumeric': 0.03049738219895288, 'fraction_numerical': 0.008376963350785341, 'mean_word_length': 4.385198237885462, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Diverse M-Best Solutions by Dynamic Programming

Many computer vision pipelines involve dynamic programming primitives such as finding a shortest path or the minimum energy solution in a tree-shaped probabilistic graphical model. In such cases, extracting not merely the best, but the set of M-best solutions is useful to generate a rich collection of candidate proposals that can be used in downstream processing. In this work, we show how M-best solutions of tree-shaped graphical models can be obtained by dynamic programming on a special graph with M layers. The proposed multi-layer concept is optimal for searching M-best solutions, and so flexible that it can also approximate M-best diverse solutions. We illustrate the usefulness with applications to object detection, panorama stitching and centerline extraction. Note: We have observed that an assumption in section 4 of our paper is not always fulfilled, see the attached corrigendum for details.


Introduction
A large number of problems in image analysis and computer vision involve the search for the shortest path (e.g., finding seams and contours) or for the maximum-a-posteriori (MAP) configuration in a tree structured graphical model, as in hierarchies of segmentation hypotheses or deformable part models. To compute the solution to those problems, one relies on efficient and optimal methods from dynamic programming [4] such as Dijkstra's algorithm [7]. In many of these scenarios, it is of interest to find not merely the single lowest energy (i.e., MAP) solution, but the M solutions of lowest energy (Mbest) [17,26,19,23,3]. This can e.g. be useful for learning [16], tracking-by-detection methods that allow competing hypotheses [18,13,24], or for re-ranking [28] solutions based on higher order features which would be prohibitively complex for the original optimization problem. If these M solutions are required to differ in more than one label, the problem is referred to as diverse M -best [2,14,22].

Contributions:
In this work, we show how the optimal second best (M = 2) solution of a tree-shaped graphical model can be found through dynamic programming in a multi-layer graph by using a replica of the original graph as second layer and connecting both layers through edges with special jump potentials (Section 3). Using these building blocks, we extend our approach to exactly find the M > 2 best solutions sequentially by constructing M -layer graphs (Section 4). While the above can be seen as a special case of [29], our multi-layer approach is an intuitive interpretation that allows flexible modeling of the desired result. We thus develop two heuristics using multiple layers to find Diverse M -Best: For general graphical models, the first formulation of the diverse M -best problem can be found in [2]. Even though their Lagrangian relaxation of the diversity constraint can work with any choice of metric, it is not even tight for Hamming distances of k > 1. Different diversity metrics are explored in [22], where a greedy method to find good instances from the (exponentially big) set of possible solutions is designed by setting up a factor graph with higher order potentials, assuming that the diversity metric is submodular. In [14], the authors construct a factor graph that jointly finds the diverse M -best solutions by replicating the original model M times and inserting factors for the diversity penalty depending on the structure of the chosen distance. It is shown that maximizing the diversity of the M -best solutions jointly, not only sequentially as in [2], can yield better results. They propose a reformulation that preserves solvability with α-β-swap-like methods. Still, when applied to trees, the factors introduced for diversity unfortunately turn the problem into a loopy graph and prevent the (a) (b) Fig. 1. A schematized two-layer grid-graph construction to find the second best shortest path from the source σ in the lower, to the target τ in the upper layer. A valid path is required to jump between layers, which is allowed everywhere for the best path. (a) Shown in blue is the best solution, which could have jumped to the upper layer at every node along the path with the lowest cost. (b) To find the second best path, layer jumps are forbidden at the nodes used by the best solution. Thus the second path diverges to the jump location leading to the next minimal cost path.
application of dynamic programming. All those approaches incorporate the diversity constraint into the original optimization problem by Lagrangian relaxation. In contrast, the constructions we propose in this work yield a solution with the desired diversity in a single shot. A different line of work [6,5] focused on extracting the M -best modes, but those methods' computational complexity renders them intractable for large graphs.

Optimal Second Best Tree Solutions
We now present how the second best solution of a tree-shaped graphical model can be obtained using dynamic programming on a special graph construction. By second best, we mean a solution that differs from the best configuration in at least one node, i.e., that has a Hamming distance of k ≥ 1 to the best solution. We begin with an informal motivation based on the search for the second best shortest path.
Motivation: The Dual Dijkstra method from [11] allows finding not only the best, but a collection of M shortest paths from a source σ to a target τ in a graph. To do so, two shortest path trees are constructed, one starting at the source and one at the target. Thus, for every node v, the shortest path from the source P σ,v and to the target P v,τ is known. Summing the distances to source and target gives the length of the shortest path from σ to τ via v. An important property is that, for all vertices along the shortest path from σ to τ , this sum is equal to the length of the shortest path. Now imagine these shortest path trees as two copies of the initial graph stacked as two layers, as seen in Figure 1(a). The lower layer indicates the lowest cost to reach every vertex v from σ, and the upper layer the cost of the shortest path to reach τ from v. By selecting any vertex v and connecting the paths at v in the lower and upper layer, one can again find the shortest path from σ to τ via v, this time by introducing an auxiliary jump edge between the two layers.
The benefit of this two layer setup is that to find the second best solution, we simply have to search for the vertex that does not lie on the best path, at which jumping between the layers leads to the minimal cost path.   , v 2 , and v 3 , with two states each, visualized as stacked boxes. v 3 is arbitrarily designated as the root, or target. Unary and pairwise costs are shown as numbers in boxes and along edges, respectively. Its optimal solution is highlighted in red in (b). Green edges correspond to the arg min incoming configurations for each state, and green numbers depict the accumulated min-sum messages. (c) Two-layer tree used to find the second best solution. Blue arcs represent layer-jump-edges with finite potential, which are available at states not occupied by the best solution. Purple dashed edges need to be considered if, at a branching point (such as v 2 3 ), not all incoming messages are coming from the upper layer. The second best solution is represented in green. (d) Searching for the 3 rd -best solution (blue) with a Hamming distance of k = 1 to the best (red) and second best solution. The new solution must jump twice to reach the upper layer, by taking a state that was not used in the configuration represented by layers 1 and 2.
Dynamic Programming: Let us briefly review the dynamic programming (DP) paradigm on an undirected tree-shaped graphḠ = (V,Ē). We denote the state of a node v ∈ V as x v , and the full state vector as x = {x v : v ∈ V}. The potentials of node v (unary potential) and of the edge connecting nodes u and v (pairwise potential) are represented by θ v (x v ) and θ uv (x u , x v ), respectively. From this, we define the inference problem as an energy minimization task [15] with objective When applying dynamic programming, one successively computes the energy E of optimal solutions of subproblems of increasing size. One node of the graphḠ is arbitrarily selected as the root node r. This results in a directed graph G = (V, E) where edges point towards the root. Let ← − N (v) denote the neighboring nodes along incoming edges of v in G. Using the tree-imposed ordering of edges, one starts processing at the leaves and sends messages embodying the respective subproblem solutions towards the root. Whenever a node v has received a message from all incoming edges, it can -disregarding its successors in G -compute the lowest energies E v (x v ) of the subtree rooted at v for every state x v , and send a message to its parent [21]. Because leaves have no incoming edges, their energy is equal to their unary potentials. All subsequent nodes combine the incoming messages with their unary potentials to obtain the energy of the subtree rooted at them by While sending these messages, each node v stores which state (arg min xu ) of the previous node (u ∈ ← − N (v), v) along each incoming edge led to the minimal energy of every state x v . When the root has been processed, the state that led to the minimal energy is selected and, by backtracking all the recorded arg min, the best global configuration x can be found. Figure 2 shows a minimal tree example.
Regarding DP runtime complexity, consider that (2) needs to be evaluated for every state of every node exactly once. In addition, in (2), we consider all states of every incoming edge, of which there are |E| = |V| − 1 in a tree. If L denotes the maximum number of states, one obtains O(|V|L 2 ).

Two-layer Model:
Once the optimal solution is found, we might be interested in the second best solution x, which assigns a different state to at least one node ∃v ∈ V : x v = x v . Because messages in DP only convey the optimal subtree energies, we cannot immediately extract this second best solution. Hence we are looking for a way to enforce that a different state is attained at least once, but we do not know at which node(s) this should happen to yield the optimal energy. Fortunately, we can apply the same idea as in the second shortest path example: We duplicate the graph to get a second layer and insert edges connecting the two layers such that jumping is only permitted at states not used in the optimal solution x . After propagating messages through both layers, the second best solution can be obtained by backtracking from the minimum energy state of the root in the second layer to leaves in the first layer. This means that messages must have jumped to the second layer at least once at some node v with a state different to x v , fulfilling our requirement for the second best solution.
We here state the layer setup conceptually and provide the formal construction in the Supplementary. To create the two layers, we duplicate graph G (Figure 2a) such that we get a layer 1, and a layer 2 replica. We address the instances of every node v ∈ V by v 1 and v 2 for layer 1 and layer 2, respectively. When duplicating the graph, the unary and pairwise potentials of nodes and edges are copied to layer 2. At every node v ∈ V, we insert a layer-jump-edge from v 1 to v 2 (blue edges in Figure 2c) with a pairwise potential θ v 1 v 2 that is only zero if both variables take the same state x v 1 = x v 2 different from v's state in x , and infinity (forbidden) otherwise. This way, finite valued messages in layer two represent configurations that did differ from x at least once. These jump edges would suffice for a chain graph, but the branching points in a tree need special consideration. When a layer 2 branching point is not reached by a layer jump, the current construction only allows considering incoming messages from layer 2. However, since we only require one variable to take a new state, only one branch is necessary to reach layer 2 on a path with finite cost. To cope with this situation, we insert layer-crossing edges from u 1 to v 2 for all edges (u, v) ∈ E (dashed purple edges in Figure 2c) with the same pairwise potential as in the original graph θ u 1 v 2 = θ uv , and alter the DP update equation for nodes in layer 2 to Compared to (2), we now have two options instead of one at every node v in layer 2. Firstly, we can reach v 2 by a layer jump. Note that, in case of a jump (S5), we do not account for the unary Alternatively, at least one of the incoming messages must come from a nonenpty set L 2 of predecessors in layer 2 (S6), while the remaining messages could cross layers. These options are visualized in Figure 2c.
Optimality and Runtime: By duplicating the directed graph and inserting two sets of new edges which are oriented towards the root in layer two, the topology of the graph remains a directed acyclic graph, and DP hence yields the optimal configuration. As long as the solution has finite energy, no forbidden layer-jump-edge is used, giving us the second best solution. In terms of runtime complexity, we have duplicated the number of vertices and have four times as many edges, which are small constant factors that disappear in O(|V|L 2 ). For optimal performance, one can reuse the messages in layer 1 because these do not change.

Optimal M -Best Tree Solutions
The two-layer setup can easily be extended to multiple layers, which allows us to search for the M -best solutions with a Hamming distance of k ≥ 1. We use one additional layer per previous best configuration; that is, M layers. Each layer is responsible for one of the previous solutions, hence its layer-jump-edges are restricted according to the respective solution. Solutions must be ordered by increasing cost; such that the first layer constrains jumps with respect to the best configuration, the second layer for the second best, and so on. The new update rules from in Section 3 can then be applied to every consecutive pair of layers. Figure 2d shows an example.
Optimality and Runtime: When considering more than one previous solution using the multi-layer setup, the jump restrictions encoded in the layer-jump-edge potentials are independent at each layer. For any given node and state in a layer, the cost and path to reach it are optimal with respect to all layers below. This straightforwardly holds for the one and two layer cases, and is the reason why layers must be ordered by increasing cost of the represented previous solutions. For the sake of argument, layers could be flattened as they are getting processed, bringing back the problem to a series of M − 1 optimal two-layer cases, which yields a computational complexity of O(M |V|L 2 ).

Approximate Diverse M -Best Solutions
In the classical diverse-M -best setting [2], additional solutions are required to have e.g. a Hamming distance of k > 1. Here, we look at the straightforward multi-layer extension of Section 3 to handle k > 1. We argue that this approach is suboptimal, and present a two-layer approximation that trades quality for efficiency. Lastly, we discuss how this could be used to find M diverse solutions.
Multi-layer Model: To ensure that the next solution differs by at least k from the best one, we could construct a k + 1-layer graph using the same jumping criteria between all layers. To reach the top layer, a solution must hence jump k times. This raises two challenges: (a) a branching point at layer N can be reached by a combination of edges from different layers such that the predecessors in total account for a Hamming distance of N , and (b) a solution should never jump more than once at a single node, otherwise it will not have the desired diversity. Both can be achieved by adjusting the DP update equation to consider a set of admissible incoming edge combinations. We provide the precise expression in the Supplementary. Unfortunately, this simple setup does not yield optimal solutions. To forbid two jumps in a row, one needs to introduce a dependence on a previously made decision. These dependencies invalidate the subproblem optimality criterion for DP to yield the correct result. It is thus possible that DP does not reach the root on layer k with finite cost, as shown in the Supplementary. Using the same reasoning, even if a valid solution is found, it is not necessarily optimal. Additionally, the set of admissible combinations of incoming edges grows combinatorially, making this approach unsuited for large k.
Diversity Accumulation: Instead of using k layers, one can also formulate a heuristic on a two-layer graph that ensures that any found solution contains the desired amount of diversity. To do so, we reformulate the Hamming distance constraint (that the new solution must differ from the previous one at k nodes) as a constraint on accumulated diversity, i.e., that v∈V α v (x v ) > T , where α is a measure of diversity per node and state, and T a threshold. We change the DP update rules as follows. First, while propagating messages from the leaves of the tree to the root in layer 1, one must also propagate the amount of diversity accumulated by the corresponding configuration of the subtree. Let us denote nodes and edges of the subtree rooted at node v in layer 1 by ←− V v 1 and ← − E v 1 , respectively. The accumulated diversity A is given by Then, we define the layer jump potentialθ v 1 v 2 (x v 1 , x v 2 ) to be infinity as long as the accumulated diversity is below the desired threshold A v 1 (x v 1 ) < k. The limitation of this heuristic is that, at each node and state, we find the optimal subtree configuration by minimizing the energy without considering diversity. This can prevent us from finding solutions with large diversity. Yet, as we will see in the experiments, this approach has an attractive runtime because it only requires two layers to find a solution with any Hamming distance k, and thus has the constant runtime complexity of O(|V|L 2 ) per solution.
Extension to M Diverse Solutions: Finding M solutions with a Hamming distance of k could be achieved by stacking M × (k + 1) layers, but then the long range dependency problems depicted above are even more prominent. With diversity accumulation on the other hand, M diverse solutions can be obtained heuristically by using one diversity map α and one accumulator A per previous solution. The jump criterion must then ensure that enough diversity has been accumulated with respect to each previous solution.

Applications and Experiments
We now evaluate the performance of our heuristics to obtain diverse solutions with prior work, and demonstrate its applicability to several problems in Computer Vision 1 .
Comparison with Existing Works: [2,28,14] search for the diverse-M -best solutions by incorporating the diversity constraint via Lagrangian relaxation. Our heuristics follow a different approach and turn the constraint into a lower bound instead of relaxing it. The resulting advantage is that we guarantee the set of solutions to be as diverse as required, at the possible expense of a higher cost or the inability to find a solution at all. On 50 random trees, with 100 nodes each, all nodes having 3 states with unary and pairwise potentials drawn uniformly from the range [0, 1], we evaluate different Hamming distances in Figure 3. We let the method of [2] run for 100 iterations with a step size of 1/n in iteration n or stop at convergence. In terms of runtime, diversity accumulation stands out as it constantly requires only two layers. Because the distance to the best configuration is not enforced by hard constraints, solutions found by [2] often contain too little diversity, yielding a too low mean Hamming distance. Diversity accumulation gives solutions with more diversity than required, and hence also deviates more from the optimal energy. In terms of returned diversity and energy, the multilayer dynamic programming solution yields favorable results compared to the other two methods, but is unfortunately slower -it suffers from the combinatorial explosion of admissible edge sets to consider -and fails to find a valid solution on several trees due to the limitations described in Section 5.
Medial Axis Identification in Biological Objects: Identifying the medial axis of biological objects is a common problem in bioimage analysis, as it serves as a basis for length or growth estimation and tracking-by-assignment. Simple dynamic programming can achieve this task given the end points, although, as biological images tend to get noisy or crowded, designing a robust cost function is difficult. In Figure 4, we illustrate the usefulness of searching for a collection of possible best solutions instead of only one shortest path in brightfield microscopy images of C. elegans nematodes.

Selection of Segmentation Hypotheses:
In datasets with cell clumps, it is often hard to select the correct detections from a set of segmentation hypotheses. We illustrate this problem in images from the Mitocheck project dataset 2 [12] using the tree model proposed in [1]. There, the task is to assign a class label to each element of a set of nested maximally stable extremal regions. The labels indicate the number of objects that each particular region represents. In the tree, nodes correspond to regions, and edges between parent and child node model the nestedness properties. In Figure 5, we show results obtained when constraining dynamic programming with our M -best approach. This is useful to generate segmentation or pose candidates as needed by joint segmentation and tracking procedures, e.g. [13,24]. (a) (b) Fig. 6. Finding diverse best paths (seams) for panorama stitching. Once the best solution (a) has been found, layer-jump-edges were blocked in a corridor around it to obtain the diverse second best solution (b).
Panorama Stitching: In our motivation in Section 3, we mentioned that the proposed multi-layer setup can also be used for shortest paths. Here, we apply that in the context of boundary seam computation for panorama stitching [27]. We stitch images taken during the Apollo 11 moon landing (Apollo-Armstrong: 2 images of 2349×2366, courtesy of NASA). As observed in Figure 6, the second diverse shortest path also corresponds to a visually correct stitching, although the resulting path significantly differs from the globally optimal one.

Conclusion
We have presented a multi-layer graph construction that allows formulating the M -best problem for tree-shaped graphical models efficiently through dynamic programming. This flexible framework can be used to find M -best solutions for a Hamming distance of k = 1 optimally. For k > 1, we present two heuristics, one using a multi-layer graph, and one using two-layers where each new configuration must accumulate diversity before it can reach the upper layer. We evaluated both heuristics against diverse-Mbest [2], revealing that both perform favourably with certain strengths over the baseline.
We demonstrated for several practical applications that the presented methods can reveal interesting alternative solutions.

Optimal Second Best Tree Solutions: Graph Construction
We formally construct the auxiliary directed graphG = (Ṽ,Ẽ) composed of two instances of the original directed graph G = (V, E) stacked up vertically. We address the lower layer with index 1, and the upper one with index 2. The new set of nodes and edges is given byṼ In the following, the first and second layer copies of an original node v ∈ V are written as v 1 and v 2 , respectively.
Edges are duplicated for each layer (S1), (S2). Additionally, we introduce layerjump-edges (S3) that directly go from any node v 1 in layer 1 to its duplicate v 2 in layer 2. Lastly, we add edge duplicates that originate in layer 1 and go to layer 2. These layer-crossing-edges (S4) are needed for message passing at branching points. Unary and pairwise potentialsθ are also replicated for all nodes v ∈ V and edges (u, v) ∈ E as To run dynamic programming on this new graphG, messages are propagated starting at all leaves in layer 1, towards the designated root r 2 ∈Ṽ on the upper layer. From every node v 1 in the lower layer, a message -embodying the partial solution of the subtree rooted at v 1 in layer 1 -is propagated in three directions: directly to its successors within layer 1, crossing layers to the successors' duplicates in the upper layer, and as a jump to this node's duplicate v 2 subject to a user-specified jumping criterion.
In summary, in the lower layer, standard messages are being sent as in the lowest energy solution. In the upper layer, every junction point is reached by three kinds of messages: those from within layer 2, those that are incoming from predecessors in layer 1, and those along layer jump edges between node duplicates. At junction points in layer 2, these incoming messages from both layers must be combined. The important requirement for a valid configuration of any layer 2 junction point is that at least one of the incoming messages must have come from layer 2 (we denote this nonempty set of predecessor nodes as L 2 ), and must thus have jumped to layer 2 in the subtree rooted at this junction point. We therefore change the DP rules in layer 2 to Compared to the standard dynamic programming rules, we now have two options instead of one in layer 2. Firstly, we can reach the node by a layer jump. Note that, in case of a jump (S5), we do not account forθ v 2 (x v 2 ) as E v 1 (x v 1 ) already contains this term. Alternatively, at least one of the incoming messages is coming from layer 2 using edges from E 2 in (S6), while the remaining messages may cross layers and originate from E cross .
If we choose to set all layer-jump-edge potentials to zero, every vertex qualifies as jump location and we obtain at the root the same solution we would get in the original graph G. If we want to find the second best solution with a Hamming distance of 1, we set the jump potentials of all states used by the previous solution to infinity. Then, a jump can only happen when the current solution differs from the previous one at this node. In addition, note that the duplicates of all leaf nodes v 2 must be reached via a layer jump. This can be achieved by setting their unaries to infinityθ v 2 := ∞.

Approximate Diverse M -Best Solutions
In (S5) and (S6), we already considered edges from layer 1 and 2 such that at least one of them came from layer 2 if that specific node was not used for a jump. In the case of k + 1 layers, we define the set of admissible incoming edge combinations A . We thus , one can jump two times at different nodes (green) and arrive in layer 3, jump once before to layer 2 and then to 3 at v 5 (orange), or combine two incoming branches from layer 2 to get to layer 3 (blue). (b) Counterexample for k = 2. If E j2 < E j1 , the minimization will pick the predecessors shown in blue, which prevents the algorithm from jumping to layer 3 and finding a valid solution.
generalize the update equation as follows: To prevent two successive jumps at the same variable (a), one must incorporate a check whether a node was reached by a jump. We thus include a dependence on the previous step. We denote by Pred v (x v ) the predecessor node of v and its state on the best path to reach v's state x v . To model that the cumulative number of jumps to reach layer N must be N − 1 (b) at each junction on layer N > 1, (S8) defines A as the set of admissible combinations of selecting incoming nodes u i ∈ ← − N (v) from layers l i . Some admissible sets are visualized in Figure S1a.

Applications and Experiments
Disparity Map Estimation from Stereo Images: To generate different disparity maps from stereo images, we build a minimal spanning tree of the pixel grid graph, using the intensity gradient as edge weight as in [31]. Neighboring pixels are connected by an edge whenever they have similar intensities. Those that are not similar are not linked and hence are not penalized when generating depth discontinuities. We allow disparities of up to 40 pixels in either direction while computing matching costs on patches of 11 × 5 pixels, and use a (non-truncated) quadratic attractive potential on the edges. While this setup is far from state-of-the-art in stereo, it demonstrates that our approach scales to large trees with many labels. We used the proposed diversity accumulation method where one unit of diversity is collected at every state that is at least a distance of 5 away from the previous solution in label space, and requested a large amount of diversity to obtain visually different depth maps. We have observed that the method presented in section 4 of our paper [32] rested on an assumption that is not always fulfilled.
Specifically, when looking for the M th best solution in a tree shaped graphical model, when M > 2 the solution found by our method can depend on the order of jumps in previous solutions, and hence does not always represent the optimal M th best configuration. This is due to the layer ordering from first to (M − 1) th best solution. In Figure C1, we provide a counterexample indicating that our algorithm sometimes erroneously blocks jumping to the next layer for the next best solution.
A possible way to circumvent this blocking would be to consider every possible ordering of the layers responsible for the M − 1 previous solutions, find the next best solution in that ordering, and at the end choose the solution that has the minimal cost. This is illustrated in Figure C1 (e). Unfortunately, this approach increases the runtime complexity by a factor of (M − 1)!.
The above shows that our method is not optimal for the M th best solution with M > 2. For M = 2, the scheme we presented in [32] section 3 remains optimal as a single jump is required to reach the second layer, which can only be blocked by the first best solution. The approximation schemes from section 5 were presented for a second best diverse solution and are hence not affected.   If first and second solution are represented by layers in the order they were found, there is no possibility to jump to the top layer that would give the fourth best solution (purple). Remember that jumps are only allowed at states not used in the solution represented by the layer from which one jumps up. (e) When representing the second best solution in the third layer and the third best solution in the second layer, we can find the optimal fourth best solution.