Mapping images into ordinal networks

An increasing abstraction has marked some recent investigations in network science. Examples include the development of algorithms that map time series data into networks whose vertices and edges can have different interpretations, beyond the classical idea of parts and interactions of a complex system. These approaches have proven useful for dealing with the growing complexity and volume of diverse data sets. However, the use of such algorithms is mostly limited to one-dimensional data, and there has been little effort towards extending these methods to higher-dimensional data such as images. Here we propose a generalization for the ordinal network algorithm for mapping images into networks. We investigate the emergence of connectivity constraints inherited from the symbolization process used for defining the network nodes and links, which in turn allows us to derive the exact structure of ordinal networks obtained from random images. We illustrate the use of this new algorithm in a series of applications involving randomization of periodic ornaments, images generated by two-dimensional fractional Brownian motion and the Ising model, and a data set of natural textures. These examples show that measures obtained from ordinal networks (such as average shortest path and global node entropy) extract important image properties related to roughness and symmetry, are robust against noise, and can achieve higher accuracy than traditional texture descriptors extracted from gray-level co-occurrence matrices in simple image classification tasks.

Figure 1

Mapping two-dimensional data into ordinal networks. (a) A small illustrative array of data ${\left\{y_i^j\right\}}_{i=1,\cdots ,N_x}^{j=1,\cdots ,N_y}$ of size $N_x=3$ and $N_y=4$. (b) Illustration of the symbolization process applied to the data with embedding dimensions $d_x=d_y=2$. This process essentially consists in evaluating the ordering of the values within each data partition. (c) Array with the symbolic sequences (or permutation patterns) ${\left\{{\pi }_s^t\right\}}_{s=1,\cdots ,n_x}^{t=1,\cdots ,n_y}$ ($n_x=3$ and $n_y=2$) obtained from the original data. (d) All first-neighbor transitions (or vertical and horizontal successions) among ordinal patterns occurring in the symbolic array. (e) Representation of data array as an ordinal network. In this example, all permutation successions occur only once and so the network edges have all the same weight. Self-loops [as in the permutation $\mathrm{\Pi }=(0,1,2,3)]$ emerge whenever a permutation pattern is adjacent to itself in the symbolic array.

Figure 2

Emergence of random ordinal networks in noisy-periodic ornaments. (a) Visualizations of geometric ornament images for different randomization probabilities $p$ (shown below images). (b) Ordinal networks with $d_x=d_y=2$ mapped from ornament images displayed in the previous panel. The thicker and darker the edge, the higher is the edge weight (probability associated with permutation transition). Node sizes reflect total in-strength so that the bigger node the more frequently it is found in the symbolic sequence. Dependence of the (c) Gini index of edge weights $G$, (d) global node entropy $H_{\mathrm{GN}}$, and (e) average weighted shortest paths $\langle l\rangle$ on the randomization probability $p$. In the last three panels, the continuous lines show the average values of the network measures and the shaded regions indicate one standard deviation band estimated from an ensemble of 100 ornament samples of size $250\times 250$ for each value of $p$. The black dashed lines indicate the exact values of the network measures for random ordinal networks.

Figure 3

Ordinal networks of fractional Brownian landscapes. (a) Examples of fractional Brownian surfaces for a few values of the Hurst exponent (shown below each image). We have normalized all surfaces so that blue shades indicate low-height regions and red shades the opposite. (b) Ordinal networks mapped from the fractal surfaces shown in the previous panel. Dependence of the (c) Gini index of edge weights $G$, (d) global node entropy $H_{\mathrm{GN}}$, and (e) average weighted shortest paths $\langle l\rangle$ on the Hurst exponent $h$ of two-dimensional fractional Brownian motion. In these last three panels, the continuous lines represent average values (from an ensemble of 100 landscape samples for each $h$), and shaded regions stand for one standard deviation band. The black dashed horizontal lines represent the values of these network metrics estimated from random ordinal networks.

Figure 4

Ordinal networks of Ising surfaces. (a) Illustration of Ising surfaces for different values of reduced temperatures $T_r$ (indicated below each image). We note that more complex patterns emerge around criticality ($T_r=1$). (b) Examples of ordinal networks mapped from the images in the previous panel. Dependence of the (c) Gini index of edge weights $G$, (d) global node entropy $H_{\mathrm{GN}}$, and (e) average weighted shortest path $\langle l\rangle$ on the reduced temperature $T_r$. The horizontal dashed lines in the previous three panels indicate values of the corresponding metric estimated from random ordinal networks.

Figure 5

Ordinal networks mapped from Brodatz textures. (a) Locations of all Brodatz textures at the plane of global node entropy $H_{\mathrm{GN}}$ versus average weighted shortest path $\langle l\rangle$. (b) Six different images corresponding to highlighted textures in the previous panel (blue markers). (c) Difference between the global network entropy estimated from horizontal and vertical ordinal networks ($H_{\mathrm{GN}}^{\mathrm{Horizontal}}-H_{\mathrm{GN}}^{\mathrm{Vertical}}$). (d) Six pictures corresponding to highlighted textures in the previous panel (red markers).

Figure 6

Comparison with other approaches and robustness against noise. (a) Bars show the accuracy (fraction of correct classifications) for the classification task of predicting the Hurst exponent based on image features obtained from ordinal networks (blue bars) and the gray-level co-occurrence matrices (GLCM—red bars). (b) True and predicted Hurst exponent. This confusion matrix details the performance of global node entropy in comparison with the best feature obtained from the GLCM approach (homogeneity). (c) Classification scores when using the Gini index of edge weights, GLCM correlation, five PCA components of the edges weights, and all five GLCM features for predicting the Hurst exponent as a function of the noise fraction added to the fractional Brownian landscapes. (d) Bars show the accuracy for the tasks of predicting whether Ising surfaces are above ($T_r=1.01$) or below ($T_r=0.99$) the critical temperature using image qualifiers obtained from ordinal networks (blue bars) and GLCM (red bars). (e) Accuracy of the classification tasks related to the Ising surfaces as a function of the noise fraction added to these images when using Gini index of edge weights, GLCM correlation, the first PCA component of the edges weights, and all five GLCM features. In all panels, the dashed lines indicate the baseline accuracy while error bars and shaded regions stand for one standard deviation.