Maximal Max-tree Simplification

MainPage

MMS Filter

Definition: The Maximal Max-Tree Simplification (MMS) is a filter that selects one node in each sub-branch of the Max-Tree, and fully contracts all other nodes, i.e. all sub-branches become trivial, therefore the resulting tree is the minimal tree that preserves the same ramifications with the same degrees and ordering as the sub-branches tree.

The MMS filter is a connected filter, since its operation consists in contracting Max-Tree nodes. It greatly reduces the number of Max-Tree nodes. Since every sub-branch is now a trivial sub-branch, the number of Max-Tree nodes is bounded between and , where is the number of Max-Tree leaves.

Notice that the MMS filter removes intermediary nodes, i.e., it is not a pruning, which many authors consider an operation that is not robust. We believe that with the right criterion it provides robust results. We propose two criteria to choose the sub-branch node to be preserved, the first is a normalized threshold criterion and will be called MMS-T and the second uses the MSER stability criterion and will be called MMS-MSER.

MMS-T

The MMS-T uses a normalized threshold criterion to select the node to be preserved. A threshold value between 0 and 1 is chosen, and this threshold value is mapped into a node in the sub-branch. The procedure is the following: suppose we are analyzing , the grey-level of the node to be preserved in this sub-branch is given by the following equation:

where is the grey-level of the sub-branch node closer to the root. The node to be preserved is:

After choosing the node to be preserved in each sub-branch, all other nodes are fully contracted. For each node to be preserved, if , the node is partially contracted by . Setting corresponds to choose the sub-branch node closest to the root, which is the connected component with highest area in the sub-branch. Setting corresponds to choose the sub-branch node further away from the root, which is the connected component with smallest area in the sub-branch.

MMS-MSER

The MMS-MSER chooses to preserve the node in the sub-branch with the highest stability measure given by a slightly modified formulation of the MSER stability criterion given by:

where represents the area of the connected component in the argument, and is the first ancestor of , where . The region represented by node is said a MSER region if is a local maximum.

The stability measures of the connected components hidden in the composite nodes do not have to be considered, since the connected component in the highest level of the composite node will always have the highest stability measure according to this slightly modified MSER formulation. This happens because its area remains constant for , and the components hidden below it will vary sooner.

The node to be preserved in the sub-branch using the MMS-MSER is given by the following equation:

After choosing the node to be preserved in each sub-branch, all other nodes are fully contracted.

Analysis of the MMS Filter

It was seen in the Extinction Filters section that the average sub-branch length of a natural image is around , therefore applying the MMS filter with no pre-processing will reduce the number of Max-Tree nodes on average by a factor of . The direct application of the MMS-T filter with , , , and the MMS-MSER filter to the sample images presented in Figure 1 are illustrated in Figure 2. Since, the average sub-branch length of the original images is around , basically the MMS filter is choosing one among two nodes to preserve in the Max-Tree, and regardless of the criterion used the filtering results are expected to be similar. The smallest SSIM index obtained was of at the CT image with the MMS-T filter and .

(a) MRI

(b) CT

(c) Cameraman

(d) Objects

(e) Text

Figure 1. Sample images.

(a) SSIM = 0.997117

(b) SSIM = 0.999004

(c) SSIM = 0.997357

(d) SSIM = 0.998391

(d) SSIM = 0.970518

(e) SSIM = 0.992817

(f) SSIM = 0.977765

(g) SSIM = 0.997036

(g) SSIM = 0.995321

(h) SSIM = 0.998470

(i) SSIM = 0.996782

(j) SSIM = 0.997601

(j) SSIM = 0.992988

(k) SSIM = 0.998133

(l) SSIM = 0.994231

(m) SSIM = 0.996278

(m) SSIM = 0.990038

(n) SSIM = 0.997315

(o) SSIM = 0.993583

(p) SSIM = 0.995867

Figure 2. Illustration of the direct application of the MMS-T filter with , (first column), (second column), (third column), and the MMS-MSER filter (fourth column).

A sensible case of the MMS filter occurs when the sub-branches in the image are long and represent a great variation in size and/or shape of a connected component. When this happens, the filter may lose important image information. For instance, a synthetic image that contains a rectangle inside a circle, which is inside a triangle, each shape darker than the object that it contains, is illustrated in Figure 3(a). These shapes constitute a sub-branch (the only sub-branch) of this image. The results of the direct application of the MMS-T filter, with , , and are illustrated in Figure 3(b)-(d) , respectively. In each filtered image only one of the shapes in the original image is preserved, if more than one shape was important to the problem the method would fail, fortunately this case does not occur in many problems.

(a) Original image

(b) MMS-T t = 0.5

(c) MMS-T t = 0.75

(d) MMS-T t = 1.0

Figure 3. Shapes image (a), and the result of applying the MMS-T filter with (b), (c), and (d).