A clustering method for concurrent photos obtained from multiple cameras using max-flow network model

• Published in: Multimedia systems 2012-07, Vol.18 (4), p.295-317
• Main Authors: Jang, Chuljin, Cho, Hwan-Gue
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer Communication Networks; Computer Graphics; Computer Science; Cryptology; Data Storage Representation; Exact sciences and technology; Information, signal and communications theory; Operating Systems; Regular Paper; Signal and communications theory; Signal representation. Spectral analysis; Signal, noise; Telecommunications and information theory
• ISSN: 0942-4962; 1432-1882
• DOI: 10.1007/s00530-011-0250-0

With the popularization of digital cameras, the use of several cameras by group photographers at the same event is becoming common. Photographers can share their contents and even take pictures of each other. So it is becoming important to manage concurrent photos from multiple cameras in order to classify many accumulated photos into proper clusters. In this paper, we propose a novel photo clustering method based on the max-flow network algorithm, and we visualize a network graph for cluster verification. To apply our algorithm, input concurrent photos are used to create an edge-weighted graph structure. In order to transform the photo clustering problem into a graph partition one, first we need to construct an Augmented Concurrent photo Graph (ACG) and then rewrite our original problem in terms of the graph partition one using the min-cut max-flow network model. The previous methods dealt with photo clustering as a 1-D problem using a linear partition. But we consider clustering for concurrent group photos as a 2-D partition based on other users’ photo contents. Each photo is used to create a node and similarities between photos are used to create the edge weights (capacities) of the network. We partition the network into two subgraphs according to the min-cut, which represents the weakest edge connections between the photos. Using repeated graph partitions for each subgraph (sub-network), we can obtain suitable subgraphs corresponding to photo clusters. The graph construction or partition can be adjusted according to user preferences in order to obtain the intended results.