Image Communities

Definition

Image communites are visually coherent subgroups of images within a large set of images.

Description

This page presents a novel community detection method that is specifically designed for image communities. We define image community as a coherent subgroup of images within a large set of images. For this purpose, we construct an image graph by utilizing visual affinity between each image pair and then pruning most of the links. Instead of affinity values, we prefer ranking of neighboring images and get rid of range mismatch of affinity values. The resulting directed graph is processed to detect the image communities by using the proposed deterministic method. The proposed method is compared against state-of-the-art community detection methods that can operate on directed graphs. In the experiments, we use various sets of images for which ground truths are determined manually. The results indicate that our method significantly outperforms the other compared state-of-the-art methods. Furthermore, the proposed method appears to have a consistent performance between sets unlike the compared methods. We believe that the proposed community detection method can be successfully utilized in many different applications.

Datasets

Set Mosaic Ground Truth Our Method Edge Betweenness Label Propagation Random Walk
batman rises (part 1,part 2) file / page result result result result
bourne identity (part 1,part 2) file / page result result result result
cappadocia (part 1,part 2) file / page result result result result
led zeppelin album (part 1,part 2) file / page result result result result
new york (part 1,part 2) file / page result result result result
pink floyd album(part 1,part 2) file / page result result result result
terminator (part 1,part 2) file / page result result result result
lord of the rings (part 1,part 2) file / page result result result result

Ground Truth

Datasets are composed of the first 201 images retrieved using the dataset title as search keywords in Yandex search engine. Ground truths are determined manually by 4 different subjects. Ground truth file is a text file containing a single line. Each integer element in the line denotes the community id of the image in the respective order.

Comparison Results

We compare the proposed method against state-of-the-art community detection methods that are capable of handling directed graphs in terms of Normalized Mutual Information [1], for which 1 is best and 0 is worst.

DatasetOursRandom Walk [2]Edge Betweenness [3]Label Propagation [4]
Bourne Identity 0.89 0.7 0.7 0.55
Led Zeppelin Album 0.89 0.69 0.67 0.69
Cappadocia 0.86 0.36 0.1 0.30
New York 0.8 0.48 0.66 0.26
Pink Floyd Album 0.9 0.7 0.38 0.57
Terminator 0.75 0.38 0.63 0.35
Batman Rises 0.93 0.65 0.643 0.7
Lord of the Rings 0.92 0.54 0.77 0.36

References

[1] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, p. P09008, 2005.

[2] P. Pons and M. Latapy, “Computing communities in large networks using random walks,” in Computer and Information Sciences-ISCIS 2005. Springer, 2005, pp. 284–293.

[3] U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical Sociolog, vol. 25, no. 2, pp. 163–177, Feb 2001.

[4] U. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys Review E, vol. 76, no. 3, p. 036106, 2007.