Replica inference approach to unsupervised multiscale image segmentation

We apply a replica-inference-based Potts model method to unsupervised image segmentation on multiple scales. This approach was inspired by the statistical mechanics problem of “community detection” and its phase diagram. Specifically, the problem is cast as identifying tightly bound clusters (“communities” or “solutes”) against a background or “solvent.” Within our multiresolution approach, we compute information-theory-based correlations among multiple solutions (“replicas”) of the same graph over a range of resolutions. Significant multiresolution structures are identified by replica correlations manifest by information theory overlaps. We further employ such information theory measures (such as normalized mutual information and variation of information), thermodynamic quantities such as the system entropy and energy, and dynamic measures monitoring the convergence time to viable solutions as metrics for transitions between various solvable and unsolvable phases. Within the solvable phase, transitions between contending solutions (such as those corresponding to segmentations on different scales) may also appear. With the aid of these correlations as well as thermodynamic measures, the phase diagram of the corresponding Potts model is analyzed at both zero and finite temperatures. Optimal parameters corresponding to a sensible unsupervised segmentations appear within the “easy phase” of the Potts model. Our algorithm is fast and shown to be at least as accurate as the best algorithms to date and to be especially suited to the detection of camouflaged images.

Figure 1

Examples of currently challenging problems in image segmentation. The image on the left is that of a zebra with a similar “stripe” background (this image is reproduced with permission from the website of Ref. [35]). The image on the right is that of a dalmatian dog (this image is reproduced with permission from the website of Ref. [36]). Most people do not initially recognize the dog before given clues as to its presence. However, once the dog is seen it is nearly impossible to perceive the image in a meaningless way [36].

Figure 2

A caricature example of overlapping blocks. In this figure, the block size is $L_x\times L_y=5\times 5$. The nearest neighbor of the block enclosed by purple in the $x$ direction is the one enclosed by red, and its nearest neighbor in the $y$ direction is the one enclosed by yellow. They are connected due to the nearest-neighbor condition.

Figure 3

Heterogeneous hierarchical system corresponding to the plots in Fig. 4. In this figure, the 1024-node system is divided into a three-level hierarchy. Level 3 has 59 communities with sizes from 10 to 24 nodes. Level 2 has 16 communities with sizes from 26 to 95 nodes. Level 1 is the completely merged system of 1024 nodes. The average edge density is $p=0.054$. This system has $28185$ edges.

Figure 4

Plots of information measures $I_N$, $V$, $H$, and $I$ and the community number $q$ vs Potts model weight $\gamma$ in Eq. (1) for the three-level heterogeneous hierarchy depicted in Fig. 3. In panel (a), the peak (plateau) $I_N$ denoted by the arrows correspond to levels 2 and 3 of the hierarchy depicted in Fig. 3. Similarly in panel (b), the minimal $V$ values, indicated by arrows, accurately correspond to levels 2 and 3 of the hierarchy. The number of communities $q$ is 16 and 59 in disparate plateau regions (denoted by the arrows) in both panels. These communities' assignments (and, obviously, also their numbers) are exactly the same as those of the communities in levels 2 and 3 of the original hierarchical graph of Fig. 3. In panels (a) and (b), both the mutual information $I$ and the Shannon entropy $H$ display a plateau behavior corresponding to the correct solutions.

Figure 5

(a) The result of the multiresolution algorithm applied to the unweighted brain image shown in (b): the plot of the normalized mutual information $I_N$, variation of information $V$, and the number of communities $q$ as a function of the resolution parameter $\gamma$ for the brain image. [The original unsegmented image in the upper lefthand corner of panel (b) was reproduced with permission from Dr. E. Aul and the Iowa Neuroradiology Library.] The axis for $\gamma$ is on a logarithmic scale. We objectively choose three local peaks in $V$ (or equivalently local minima in $I_N$) and apply our community detection algorithm to the gray-scale brain image at the corresponding three values of $\gamma$. The corresponding results are shown in panel (b). Note that the results show a three-level hierarchy as $\gamma$ varies.

Figure 6

(a) The result of the multiresolution algorithm for the weighted brain image shown in (b): $I_N$, $V$, and $q$ in terms of the resolution parameter $\gamma$. The original unsegmented brain image is reproduced with permission from Dr. E. Aul and the Iowa Neuroradiology Library. In panel (a), the multiresolution result behaves differently from Fig. 5, but it maintains the same trend. The structure that we find is only stable in the resolution range of $\gamma <0.01$, compared to the wider range of $\gamma <0.1$ in Fig. 5. We objectively choose three peaks of $I_N$ and $V$ and apply our community detection algorithm to the gray-scale brain image at the corresponding three values of $\gamma$ in panel (b).

Figure 7

(a) The result of multiresolution algorithm for the weighted brain image shown in (b): $I_N$, $V$, and $q$ in terms of the threshold $\overline{V}$. (b) The weighted result of the images with different $\overline{V}$. The original unsegmented brain image is reproduced with permission from Dr. E. Aul and the Iowa Neuroradiology Library. The “multiresolution” result also shows the hierarchy structure as the threshold $\overline{V}$ varies, as in Fig. 6. Higher $\overline{V}$ corresponds to lower $\gamma$, which means pixels tend to merge in higher $\overline{V}$. The structure is stable in the range of $\overline{V}>25$, below which the structure is sensitive.

Figure 8

(a) The variation of information $V$ as a function of resolution $\gamma$ for the image shown in panel (b). (b) The original image and the corresponding segmentation for the specific resolution marked (I) in panel (a). (c) The corresponding images in the specific resolution marked (II), (III), (IV), and (V) in panel (a). The original unsegmented specific image is reproduced with permission from Ref. [65]. At close distance, this is “Gala contemplating the Mediterranean sea,” while at larger distance it is “a portrait of Abraham Lincoln.” Panel (a), again, shows the variation of information as a function of resolution. We pick the resolution at each “peak” position and apply our algorithm at these particular resolutions. Panels (b) and (c) show the resulting images at the corresponding resolutions marked in panel (a). Note that at low resolution, the resulting segmentation clearly depicts “the portrait of Abraham Lincoln” as shown in panel (b) on the right. In particular, notwithstanding noise, as $\gamma$ increases, the segmentation results show more details and we could detect the lady in the middle in (II)–(V) of panel (c).

Figure 9

Image segmentation results of our algorithm when tested with examples from the Berkeley BSDS300 benchmark. In the lefthand column, the original images are depicted. The central column contains the results of our method, and the right column provides the boundaries of the images by running EdgeDetect in mathematica on the results of our run in the central column. In the current benchmark, we did not apply the multiresolution algorithm or choose parameters according to Eq. (21). Instead, we arbitrarily selected a range of $\gamma$'s spanning several decades. The small range of values for $\overline{V}$ were selected by experimentation. Better results may be obtained if the optimal parameters are determined. The parameters of the community detection algorithm used for these images are as follows: In (a), $\gamma =0.001$, $\overline{V}=15$. In (b), $\gamma =0.0001$, $\overline{V}=20$. In (c), $\gamma =0.001$, $\overline{V}=20$. In (d), $\gamma =0.01$, $\overline{V}=15$. In (e), $\gamma =0.01$, $\overline{V}=15$. We performed the boundary detection on the results of our community detection algorithm (i.e., the central column) and employed the F-measure accuracy parameter in order to compare the results of our algorithm with earlier results reported for the Berkeley image segmentation benchmark (shown in Table ).

Figure 10

The results of some image segmentations by our Potts model in Eq. (2) and community detection algorithm [42]. The images are downloaded from the website of the Microsoft Research database [62]. The left column contains the original images. The central column depicts the “ground truths” as defined by Microsoft Research [62], which are the desirable image segmentation results. These ground truth images were not generated by algorithm, but by humans. The right column shows the segmentation results of our algorithm. The parameters used for each image are as follows: (1) $\gamma =0.001$, $\overline{V}=20$ for the flower image. (2) $\gamma =0.01$, $\overline{V}=15$ for the image of the picnic table. (3) Similarly, $\gamma =0.01$, $\overline{V}=15$ for the image of the two sheep. Our algorithm generally appears to find the ground truth, and it appears to work very well for these kinds of images where the color is nearly uniform within each object.

Figure 11

The image segmentation results by the community detection algorithm with Fourier weights as described in Sec. 4b3. The top original unsegmented three images are downloaded from the Microsoft Research database [62]. The original unsegmented fourth is downloaded from the Berkeley image segmentation benchmark image [57]. The original unsegmented fifth image is reproduced with permission from the website of Ref. [66]. The left column contains the original images. The central column (apart from the last two rows) provides the “ground truths.” The images on the right are our results. The parameters used in the images are as follows: (1) $\gamma =0.01$, $\overline{V}=-300$ for the tree image. (2) $\gamma =0.1$ and $\overline{V}=-300$ for the car image. (3) $\gamma =0.01$ and $\overline{V}=-400$ for the bench image. (4) $\gamma =0.01$, $\overline{V}=-100$ for the image of corn. (5) $\gamma =0.1$, $\overline{V}=-900$ for the zebra image. Even though the color is not uniform inside the targets, we can nevertheless easily detect the targets by this method.

Figure 12

The results of the image segmentation for a “camouflaged image.” The original image of the leopard is reproduced with permission from Ref. [67]. (The original image is that of a great male leopard, made in Sabi Sand Private Game Reserve, South Africa, by Lukas Kaffer.) The original unsegmented image of the lizard is provided in the Berkeley image segmentation benchmark [57]. The original image of the zebra is reproduced with the permission from the website of the EECS department of Berkeley [35]. The parameters for the shown segmentations are as follows: (1) $\gamma =1$, $\overline{V}=-700$ for the image of the leopard, (2) $\gamma =0.1$, $\overline{V}=-500$ in the image of the lizard, and (3) $\gamma =1$, $\overline{V}=-1100$ for the zebra image.

Figure 13

The “multiresolution” result of the zebra image with resolution $\gamma =1$. The original image in the upper lefthand corner is reproduced with permission from Ref. [35]. In panel (a), we plot the variation of information $V$ as a function of negative threshold $-\overline{V}$ for the zebra image in panel (b). The peaks in $V$ correspond to the changes of structures. We choose three peaks and run the algorithm at these three particular thresholds, and the result images are shown in panel (b). (b) The weighted results of the zebra images at the corresponding thresholds: ${\overline{V}}_1=-760$ (I), ${\overline{V}}_2=-1040$ (II), and ${\overline{V}}_3=-1200$ (III). As $|\overline{V}|$ increases, fewer regions in the zebra merge to the background, and the boundary becomes more clear. If we increase the threshold further, the result is more noisy as the last image of $\overline{V}=-1200$ (III) illustrates.

Figure 14

Results of our algorithm as a function of the length scale $\ell$ in Eq. (7) for the dalmatian dog image. (The original unsegmented dalmatian dog image is reproduced with permission from Ref. [36].) Plots of the variation of information and the normalized mutual information ($V$, $I_N$) as a function of the length scale $\ell$ appear in panels (a) and (b) (at a resolution of $\gamma =0.1$) and (d) and (e) ($\gamma =0.05$). Panel (c) left shows the original image. As seen in panels (a) and (b), a coincident local maximum of $V$ and local minimum of $I_N$ appears (for $\gamma =0.1$) at $\ell =0.63$. Panel (c) right, the number of communities $q$ in this image with $l=0.63$ is $q=8$. Similarly, panel (f) right shows the images corresponding to the peak of $V$ (coincident with a local minimum of $I_N)$ in panels (d) and (e) at ${\ell }_2=1.29$ and $\gamma =0.05$. We also examine the results for ${\ell }_1=1$ and $\gamma =0.05$ in panel (f) left. The number of communities in the image of panel (f) left with $\ell =1$ is $q=33$. In the image of panel (f) right with $\ell =1.29$, $q=42$. We are able to detect the body and the back two legs of the dog, even though with some “bleeding” in panel (f). In panel (c) right, we are detecting well except for the inclusion of some “shade” noise under the body. Overall, the viable solutions found by our method detect the pertinent features of the image (and the dog therein).

Figure 15

Plots of $I_N$, $V$, $\chi$, $H$, and the energy $E$ as a function of $\log \left(\ell \right)$ and $\log \left(\gamma \right)$ for the “dalmatian dog” image in Fig. 14. (a) A 3D plot of the normalized mutual information $I_N$ as a function of $\log \left(\ell \right)$ and $\log \left(\gamma \right)$. (b) The 3D plot of the variation of information $V$ as the function of $\log \left(\ell \right)$ and $\log \left(\gamma \right).$ (c) Plots of the susceptibility $\chi$ as a function of $\log \left(\ell \right)$ and $\log \left(\gamma \right).$ (d) The Shannon entropy $H$ as a function of $\log \left(\ell \right)$ and $\log \left(\gamma \right)$. (e) The energy $E$ as a function of $\log \left(\ell \right)$ and $\log \left(\gamma \right)$.

Figure 16

Information theory and thermodynamic measures relating to the dalmatian dog image of Fig. 14. The squares of the gradients of $I_N$, $V$, $\chi$, $H$, and $E$ [panels (a)–(e)] and the sum of the squares of the gradients of $I_N$, $V$, and $\chi$ [panel (f)] as functions of $\log \left(\ell \right)$ and $\log \left(\gamma \right)$. The red dot in each panel denotes the location of the parameters $(\log \left(\ell \right)$, $\log \left(\gamma \right))=(0,-1.3)$ [i.e., $(\ell ,\gamma )=(1,0.05)$] of the results in Fig. 14. The good segmentation found for these parameters correlates with a local minimum within each panel.

Figure 17

The normalized mutual information $I_N$, variation of information $V$, susceptibility $\chi$, energy $E$, and Shannon entropy $H$ as a function of the resolution $\log \left(\gamma \right)$ and temperature $T$ for the “bird” image in Fig. 18. In panel (a), we mark (i) the “easy” phase (where $I_N$ is almost 1) as “A”, (ii) the “hard” phase (where $I_N$ decreases) by “B”, and (iii) denote the “unsolvable” phase (where $I_N$ forms a plateau whose value is less than 1) by “C”. The physical character of the easy, hard, and unsolvable phases is further evinced by the corresponding image segmentation results in Fig. 18. We can determine the signatures of the three phases in all panels apart from panel (c), the 3D plot of the susceptibility $\chi$.

Figure 18

The image segmentation results of the “bird” image. (The original unsegmented image in the top lefthand corner is reproduced from the Berkeley image segmentation benchmark.) The original image is on the upper left. The segmentations denoted by “A”, “B”, and “C” correspond to results with different parameter pairs $(\log \left(\gamma \right)$, $T)$ that are marked in panel (a) of Fig. 17. Both results A and B are able to distinguish the bird from the background. However, in panel (b), the bird is composed of numerous of small clusters. The segmentation C does not detect the bird. The results shown here at points A, B, and C correlate with the corresponding easy-hard-unsolvable phases in the phase diagram in Fig. 17.

Figure 19

Further image segmentation results by our algorithm for a well known benchmark. The original unsegmented images in the leftmost column are downloaded from the Berkeley image segmentation benchmark. The central image in the first row and the third row is the result of our algorithm at $\gamma =0.01$ and $\overline{V}=20$. The rightmost image in the first and third rows is the boundary detection result of the corresponding central image by the software mathematica. There are many dots or circles which denote the white spray in original image in the first row. The small dots or circles in the third row denote the shadow in the original image. We merge these small dots in the first and third rows into the background and the results shown in the second and fourth rows are smoother and close to the ground truth. This is validated by the larger F value as shown in Table .

Figure 20

The “multiresolution” result of the zebra (reproduced with permission from the website of Ref. [35]) with fixed community number $q=3$ and resolution $\gamma =1$. In panel (a), we plot the normalized mutual information $I_N$ as a function of negative threshold $\overline{V}$. The peaks in $I_N$ also correspond to the changes of structures. We choose three peaks and run the algorithm at these three particular thresholds, ${\overline{V}}_1=-680$, ${\overline{V}}_2=-960$, and ${\overline{V}}_3=-1100$, and the resulting images are shown in panel (b). As $|\overline{V}|$ increases, fewer regions in the zebra merge to the background, and the boundary becomes more clear.

Figure 21

The image segmentation results (II and III) of a camouflaged zebra. (The original unsegmented image of the zebra is reproduced with permission from the website of Ref. [35]) in (I). In panel (II), we used the Fourier-based edge weights of Eq. (11) and with a negative background $\overline{V}=-1200$ (other parameters are $\gamma =1$, block size $l_x\times l_y=11\times 11$). (III) The resulting segmentation when the sign on the right-hand side of Eq. (11) is flipped. Here, we applied a positive background $\overline{V}=900$ (other parameters are $\gamma =1$, block size $l_x\times l_y=7\times 7$). Both of the results shown here (i.e., II and III) are able to detect the zebra.

Figure 22

Quasicrystal images are displayed in panels (I). The corresponding image segmentation results by our algorithm are shown in (II). In (III), we connect the basic object by line, resulting in large basic blocks. This process can be repeated recursively leading to larger and larger scale structures. Note that we are able to reveal the underlying quasiperiodic structures in rows II and III of (a). (The original image in (I) is reproduced with permission from the website of Ref. [71] by J. Baez and also the website of Ref. [72] by G. Egan.) and (b) (the original image shown in (I) is from Ref. [74], adapted by permission from Macmillan Publishers Ltd.). We show the first Penrose tiling (tiling P1) in (a) and the structural motif of the ($3^2.4.3.4$) Archimedean tiling in (b).