Random bounds

By applying bounds we greatly reduce the size of the problem. Even though the weight matrix (${\bf W}$) is stored as a sparse matrix (only non-zero values are stored), it can still be very large. Typically, the size of the sparse weight matrix is the size of the input image multiplied by the number of samples taken from each pixel's search neighborhood. In 2D, this can be twenty to thirty times the size of the input image. In 3D, this problem may be even worse. Therefore, any reduction in the size on the input image is helpful. These bounds can acquired from several sources. For instance, these initial rough bounds can be found by first running the algorithm with small search neighborhoods and coarse sampling.

 

pic2
Figure 1 A cartoon of a masked salt boundary. It is long and thin with a discontinuous salt boundary snaking across it.

Unfortunately, the normalized cut segmentation method tends to partition elongated images along their shortest dimension. For instance, Figure is a cartoon of an elongated image with a salt boundary snaking across it. If the segmentation algorithm were to function as hoped, the minimum cut would be found along the salt boundary. However, because the salt boundary is discontinuous, it is likely that the minimum of the normalized cut in equation (1) will be found by cutting the image vertically where the image is thin.

To correct this problem, we exploit the fact that the upper boundary will necessarily be in Group A and the lower boundary will be in Group B. In other words, we want to force the segmentation algorithm to put the coarsely picked bounds in different groups.

We can enforce this constraint during the creation of the weight matrix (${\bf W}$). Recall that this matrix contains weights relating each sample to other samples along paths within a neighborhood. For any given sample, if its search neighborhood happens to cross a coarse boundary, it becomes weighted to another sample at a random distance along the boundary. This can be imagined by wrapping the image on a globe so that both the upper and lower bounds collapse to points at the poles. When estimating the weight matrix, every time a path crosses the north or south pole, it continues down the other side. By implementing these ``Random'' boundaries, we are effectively removing the upper and lower boundaries.

 

fig1
Figure 2 A cartoon illustrating random bounds.

In Figure , two nodes, ${\it i}$ and ${\it j}$, of a 2D image are plotted separated by a boundary indicating that node ${\it j}$ is outside of the bounds. Vector ${\bf v}_{ij}$ represents the shortest path connecting them but excluding the nodes themselves. ${\bf n}_{b}$ and ${\bf t}_{b}$ are the unit normal and tangent vectors where ${\bf v}_{ij}$ crosses the boundary at location ${\it b}$. Together, ${\bf n}_{b}$ and ${\bf t}_{b}$, make a basis on to which vector ${\bf v}_{bj}$ is projected and then mapped on to another basis at ${\bf b'}$ at a random distance along the boundary. In summary, if ${\it j}$ is outside the boundary, then ${\bf v}_{ij'}$ defines the path instead of ${\bf v}_{ij}$ as:

$$\begin{eqnarray} {\bf v}_{ij}&=&{\bf v}_{ib}+{\bf v}_{bj} \ {\bf v}_{b'j'}&=&{\... ..._{b} ){\bf t}_{b'} \ {\bf v}_{ij'}&=&{\bf v}_{ib}+{\bf v}_{b'j'}.\end{eqnarray}$$ (4) (5) (6)