## 2 Methodology
### Refinement  
Thus far, regions that have been identified via segmentation in 2D space have been classified as either trees or non-trees. Some of these segments are in fact sub-segments of the same tree (different part of the canopy or the stem), some segments may be a mixture of tree and background, while some may hold tree characteristics but are, in fact, non-tree segments. The refinement phase aims at: (i) linking segments that are part of the same tree, (ii) minimizing the number of false alarm detections, and (iii) separating mixture segments into object and background. Generally, this can be described as a split and merge problem among segments. It is approached here differently by weighing the inter-relation between the individual points, so that neighboring points (by 3D proximity measures) indicate potentially tight relations and consequently stronger utility in their link. A common theme in object to background separation algorithms is the desire to group pixels that have a similar appearance (statistics) and to have distinct boundaries between pixels in different classes. Restricting the boundary measurements to be between immediate neighbors and compute region membership statistics by summing over pixels, we can formulate this as a classic pixel-based energy function problem, which is addressed here via graph cut energy minimization of the following term:  
\[E=\sum_{i}E_{d}\left(i\right)+E_{s}\left(i\right) \tag{7}\]  
with \(E\) the total energy, _Ed_, the data term, related to the \"wish\" of laser point to maintain its original classification and _Es_ is the smoothness term, which relates to the \"wish\" of highly connected points to share the same label. Labeling here refers to the binary value of the classified point in the point cloud and not to the outcome of the classification process. The energy function, \(E\), can be modeled by a flow graph, where each point, \(i\), in the cloud is a vertex (\(V_{i}\)), and additionally, two more vertices, a source (\(S\)) and the sink (\(T\)) are added. The \(E_{d}\), term is computed by  
\[E_{d}=f\left(p_{i}\right) \tag{8}\]  
where \(p_{i}\) is the probability that \(i\) is an object. The probability is set according to the segment classification stage (high value to pixels that were assigned as an object and low to those assigned as non-object). The \(E_{d}\) elements are applied through the weights (capacities) assigned to the edges that link each point to the source and the sink. Points that are more compatible with the foreground (tree) or background (non-tree) region obtain stronger connections to the source or sink, respectively. Thus, the weights on the edges of a source-to-node and on a node-to-sink is set according to  
\[w\left(S,v_{i}\right) =\left|p_{i}-\alpha\right|\] \[w\left(v_{i},T\right) =1-\left|p_{i}-\alpha\right| \tag{9}\]  
where \(\alpha\) is the possible error in assigning a point to a given class (an 0.05 value was applied here). The capacities of the other edges in the graph are derived from the smoothness energy term (\(E_{s}\)), _i.e._, adjacent points have stronger links. The boundary term is therefore set as the inverse proportion of the 3D Euclidian distance between points \(i,j\). In order to avoid a full graph containing all possible \(i,j\) links, the only pairs we assign are nearest-neighbor points, \(j\), for each point \(i\) in the point-cloud. For each such pair (\(i\)_j_) a link between the two nodes is built. The search for the nearest neighbor is performed via the Approximate Nearest Neighbor (ANN) method [27]. This process leads to a sparse and controllable graph. Once the flow-graph is set, a minimum-cut/maximum-flow problem can be solved using a polynomial time algorithm (e.g., [28, 29]), pixels on either side of the computed cut are labeled according to the source or sink to which they remain connected. The graph-cut algorithm finds the minimal cut (and the maximal flow) of the graph which also minimizes the energy function.