Extinction Filter

MainPage

The Extinction Filter (EF) is a connected filter that preserves the relevant maxima of the image, while reducing the tree complexity, i.e. the number of tree nodes. Most natural images are contaminated by noise, therefore they probably contain many irrelevant extrema with low extinction values. For instance, the famous Lena image with dimensions pixels is shown in Figure 1(a). Its corresponding max-tree using connectivity has nodes of which are leaves, i.e. maxima. The height, area and volume normalized extinction histograms, respectively are shown in Figure 1(b)-(d). Only the lower extinction values are displayed for better visualization. It is clear that the histograms are highly concentrated on the lower extinction values, and probably most of these maxima in the image correspond to noise or irrelevant artifacts.

(a) Lena image

(b)Height Extinction Values Histogram

(c) Area Extinction Values Histogram

(d) Volume Extinction Values Histogram

Figure 1. Lena image (a), and its height (b), area (c), and volume (d) normalized extinction histograms.

The EF operation is very simple. The leaves with highest extinction values concerning the crescent attribute being analyzed are chosen. The nodes in the paths from these leaves to the the root are marked as to be kept. All the other nodes are fully contracted. Since the contraction of max-tree nodes is a connected filter, the EF is also a connected filter. The EF procedure is illustrated in Figure 2. Suppose that and nodes , and (the yellow nodes) of Figure 2(a) are the leaves with highest extinction value according to the attribute being analyzed. The nodes in the paths from these leaves to the the root are marked in red, Figure 2(b), the remaining nodes are pruned. The resulting tree is illustrated in Figure 2(c).

Figure 2. Original max-tree (a), the yellow nodes are the three nodes with highest extinction values. Nodes in the path from the three leaves with highest extinction values to the root are marked in red (b). The result of the pruning of the nodes not marked in red (c).

In order to illustrate, and analyze the EF, it was chosen sample images with different characteristics: a brain MRI, a lung CT, a natural image with text in it, a cameraman picture, and an image with many objects in it. They are 8 bits images with their pixel intensities varying between and , their information is summarized in Table 1, and the images are displayed in Figure 3.

Image Name Dimensions Nb. of max-tree nodes Nb. of Sub-branches
MRI 1280 x 1105 197203 79784
CT 512 x 512 44829 27572
Cameraman 256 x 256 11123 5883
Objects 406 x 409 8398 4442
Text 384 x 512 13054 9238

Table 1. Summary of the information concerning the sample images.

(a) MRI

(b) CT

(c) Cameraman

(d) Objects

(e) Text

Figure 3. Sample images.

(a) (197203,3751) nodes,(64766,64) leaves SSIM = 0.992572

(b) (44829,961) nodes,(20449,20) leaves SSIM = 0.994954

(c) (11123,535) nodes,(4241,4) leaves SSIM = 0.952583

(d) (8398,267) nodes,(3336,3) leaves SSIM = 0.979984

(e) (13054,685) nodes,(8249,8) leaves SSIM = 0.977748

Figure 4. Illustration of the Area EF applied to the sample images. The parameter was equal to of the number of maxima in the corresponding original image.

The results of applying the Area EF to the sample images are illustrated in Figure 4. The parameter was set as being of the number of maxima in the original images. The average reduction in the number of max-tree nodes after the filtering was around a factor of , and all filtered images have an SSIM index higher than in relation to their corresponding original image. It is hard to visually notice differences between the original images and the filtered images. These results support the hypothesis that in general most of the extrema in natural images correspond to noise.

The variation of the number of nodes, sub-branches according to the parameter used in the Area EF are illustrated in Figure 5. The abscissas of the plots represent the percentage of maxima with lower extinction values that were chosen to be removed, i.e. . The ordinate of Figure 5(a) represents one minus the ratio between the number of nodes of the original max-tree and the number of nodes after the EF. The ordinate of Figure 5(b) represents one minus the ratio between the number of sub-branches in the filtered max-tree and the number of sub-branches of the original max-tree.

(a) Nodes reduction rate.

(b) Sub-branches reduction rate.