Characteristic Neighbourhood

The characteristic neighbourhood for a generic MGRF model consists of a group of the most energetic clique families and represents most probably pixel interactions in a texture.

The simplest approach to estimating the structure is to select most energetic clique families by using a threshold of partial energy [37,36]. But the selection of threshold is largely heuristic and the statistical interplay between clique families have not been taken into account.

An alternative sequential approach in [107] selects each next characteristic clique family by comparing the training GLCHs to those for an image sampled from the MGRF with the currently estimated neighbourhood. Since each step involves image sampling (generation) and re-collection of the GLCHs, the process is very computationally complex, i.e. to find a neighbourhood structure $\mathcal{N}$, the time complexity is $O(\max\{\vert\mathcal{R}\vert\vert\mathcal{N}\vert T, \vert\mathcal{R}\vert\vert\mathcal{W}\vert\})$ where $T$ is the expected number of steps, which, at least, theoretically $T$ grows exponentially with $\vert\mathcal{R}\vert$ although it is limited to a few hundred steps empirically to generate a single MGRF sample using the MCMC process of pixel-wise stochastic relaxation.

The structural identification simplifies selection of the characteristic neighbourhood due to the observation that most energetic clique families form isolated clusters (or blobs) in the MBIMs shown in Figs 6.3 and 6.4. From the statistical point of view, the clique family having maximum energy in each cluster is related to locally the most probable pixel interaction. Pixel interactions represented by other clique families in the vicinity are also likely but with lower probability. This indicates variations of neighbourhood structure at different locations of an image. The size and shape of the clusters reflect the degree of local variations and could be used to measure texture homogeneity, i.e. a strict homogeneous texture should have a smaller cluster.

It is reasonable to use the local maximum of each cluster as a representative clique family for a local region. A two-step approach is proposed to find these local maxima. First, all the significant clusters are identified from the MBIM, and second, the clique family having the maximal partial energy in each cluster is added into the characteristic neighbourhood.

Most MBIMs have their corresponding histograms of partial energies as a unimodal distribution, i.e. each histogram is positively skewed and has a single peak at the lower energy end, as in Fig 6.6. This allows to apply a unimodal thresholding algorithm [87] to determine a threshold that separates high-energy clique families from the majority of low-energy ones. Consequently, clusters formed by high-energy families are isolated and can be easily identified by grouping connected clique families using the classic connected-component labelling algorithm [86]. A local maximum is then identified by as the clique family with maximal energy from each cluster.

Figure 6.6: Energy histograms for textures in Figs 6.3 and 6.4.

D29	bark0009
D34	D101

Figure 6.7: Unimodal thresholding [87]. The algorithm computes the distance between every point on the histogram curve to the straight line. The threshold is at the point on the histogram curve where the maximum distance occurs.