Indexation multimédia par dictionnaires visuels en environnement décentralisé - Une approche par protocoles Gossip

Indexation multimédia par dictionnaires visuels en environnement décentralisé

Une approche par protocoles Gossip

Jérôme Fellus David Picard  Philippe-Henri Gosselin 

ETIS - UMR CNRS 8051 - ENSEA - Université de Cergy-Pontoise France

INRIA, Texmex project, Campus de Beaulieu, Rennes France

Corresponding Author Email: 
jerome.fellus@ensea.fr,picard@ensea.fr
Page: 
39-64
|
DOI: 
https://doi.org/10.3166/TS.32.39-64
Received: 
27 September 2013
| |
Accepted: 
14 April 2014
| | Citation

OPEN ACCESS

Abstract: 

In order to allow content-based retrieval of multimedia documents spread over large networks, we propose an indexing system based on decentralized and asynchronous learning of visual codebooks. We propose a Gossip-based decentralized algorithm to compute an accurate visual codebook at each networking node. We provide an empirical law to define the optimal parameters, given the targetted network size, to get codebooks which are equal between nodes with low communication costs. An experimental study highlights the scaling abilities and the retrieval accuracy of our system.

RÉSUMÉ

Pour permettre la recherche par le contenu de documents multimédias repartis sur de larges réseaux, nous proposons un système d’indexation basé sur l’apprentissage décentralisé et asynchrone de dictionnaires visuels. Nous proposons un algorithme décentralisé pour le calcul des dictionnaires basé sur un protocole d’agrégation Gossip, qui produit un dictionnaire local performant en chaque nœud du réseau. Nous fournissons une loi empirique pour déterminer les paramètres optimaux du système selon la taille du réseau ciblé, qui permettent d’obtenir des dictionnaires égaux entre nœuds pour un coût de communication faible. Une étude expé-rimentale met en évidence les capacités de passage à l’échelle et la qualité de recherche du système.

Keywords: 

distributed content-based retrieval (D-CBR), multimedia indexing, visual codebooks, decentralized clustering, Gossip aggregation protocols.

MOTS-CLÉS

recherche par le contenu distribuée (D-CBR), indexation multimédia, dictionnaires visuels, clustering décentralisé, protocoles Gossip.

1. Introduction
2. État De L’art
3. Système D’indexation Multimédia Décentralisé Et Asynchrone
4. Expériences Et Résultats
5. Conclusion
  References

Ailon N., Jaiswal R., Monteleoni C. (2009). Streaming k-means approximation. Advances in Neural Information Processing Systems, vol. 22, p. 10–18.

Bandyopadhyay S., Giannella C., Maulik U., Kargupta H., Liu K., Datta S. (2006). Clustering distributed data streams in peer-to-peer environments. Inf. Sci., vol. 176, no 14, p. 1952-1985.

Bay H., Ess A., Tuytelaars T., Gool L. V. (2008). Surf: Speeded up robust features. Computer Vision and Image Understanding, vol. 110, no 3, p. 346–359.

Bénézit F., Blondel V., Thiran P., Tsitsiklis J., Vetterli M. (2010). Weighted gossip: Distributed averaging using non-doubly stochastic matrices. In Information theory proceedings (isit), 2010 ieee international symposium on, p. 1753–1757.

Boyd S., Ghosh A., Prabhakar B., Shah D. (2006). Randomized gossip algorithms. Information Theory, IEEE Transactions on, vol. 52, no 6, p. 2508–2530.

Datta S., Giannella C., Kargupta H. (2006). K-means clustering over a large, dynamic network.

Datta S., Giannella C., Kargupta H. (2009, October). Approximate distributed k-means clustering over a peer-to-peer network. IEEE Trans. on Knowl. and Data Eng., vol. 21, no 10, p. 1372–1388. Retrieved from http://dx.doi.org/10.1109/TKDE.2008.222

Demers A., Greene D., Houser C., Irish W. (1988). Epidemic algorithms for replicated database maintenance. SIGOPS Oper. Syst. Rev., vol. 22, no 1, p. 8–32. Retrieved from http://doi.acm.org/10.1145/43921.43922

Dempster A. P., Laird N. M., Rubin D. B. (1977). Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), p. 1–38.

Durut M., Patra B., Rossi F. (2012). A discussion on parallelization schemes for stochastic vector quantization algorithms. In 20-th european symposium on artificial neural networks, computational intelligence and machine learning (esann 2012), p. 477–482.

Eisenhardt M., Muller W., Henrich A. (2003). Classifying documents by distributed p2p clustering. GI Jahrestagung, p. 286–291.

Fatta G. D., Blasa F., Cafiero S., Fortino G. (2011, December). Epidemic k-means clustering. In 2011 ieee 11th international conference on data mining workshops, p. 151–158. IEEE. Retrieved from http://centaur.reading.ac.uk/27053/ (Print ISBN: 9781467300056 Issue Date: 11-11 Dec. 2011 On page(s): 151 - 158)

Fatta G. D., Blasa F., Cafiero S., Fortino G. (2012, September). Fault tolerant decentralised k-means clustering for asynchronous large-scale networks. Journal of Parallel and Distributed Computing. Retrieved from http://centaur.reading.ac.uk/29421/

Gemert J. C. van, Veenman C. J., Smeulders A. W. M., Geusebroek J. M. (2010). Visual word ambiguity. IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 32, no 7, p. 1271–1283. Retrieved from http://www.science.uva.nl/research/publications/2010/vanGemertTPAMI2010

Iutzeler F., Ciblat P., Hachem W. (2013). Analysis of sum-weight-like algorithms for averaging in wireless sensor networks. Signal Processing, IEEE Transactions on, vol. 61, no 11, p. 2802–2814.

Januzaj E., Kriegel H.-P., Pfeifle M. (2004). Dbdc: Density based distributed clustering. In Advances in database technology-edbt 2004, p. 88–105. Springer.

Jégou H., Douze M., Schmid C. (2008, oct). Hamming embedding and weak geometric consistency for large scale image search. In A. Z. David Forsyth Philip Torr (Ed.), European conference on computer vision, vol. I, p. 304–317. Springer. Retrieved from http://lear.inrialpes.fr/pubs/2008/JDS08

Jégou H., Douze M., Schmid C., Pérez P. (2010, June). Aggregating local descriptors into a compact image representation. In Ieee international conference on computer vision and pattern recognition, p. 3304–3311.

Jégou H., Perronnin F., Douze M., Sánchez J., Pérez P., Schmid C. (2012). Aggregating local image descriptors into compact codes. IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 1, p. 3304-3311. Retrieved from http://hal.inria.fr/inria-00633013/en/(QUAERO)

Jelasity M., Kowalczyk W., Van Steen M. (2003). Newscast computing. Tech. Rep.. Technical Report IR-CS-006, Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands.

Kempe D., Dobra A., Gehrke J. (2003). Gossip-based computation of aggregate information. In Proceedings of the 44th annual ieee symposium on foundations of computer science, p. 482–. Washington, DC, USA, IEEE Computer Society. Retrieved from http://dl.acm.org/citation.cfm?id=946243.946317

Kohonen T. (1990). The self-organizing map. Proceedings of the IEEE, vol. 78, no 9, p. 1464–1480.

Kowalczyk W., Vlassis N. A. (2004). Newscast em. In Advances in neural information processing systems, p. 713–720.

Linde Y., Buzo A., Gray R. (1980). An algorithm for vector quantizer design. IEEE Transaction on Communication, vol. 28, p. 84–94.

Lloyd S. P. (1982). Least squares quantization in pcm. IEEE Transactions on Information Theory, vol. 28, p. 129–137.

Lowe D. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, vol. 2, no 60, p. 91–110.

Lu T.-C., Chang C.-Y. (2010). A survey of vq codebook generation. Journal of Information Hiding and Multimedia Signal Processing, vol. 1, no 3, p. 190–203.

Marée R., Denis P., Wehenkel L., Geurts P. (2010). Incremental indexing and distributed image search using shared randomized vocabularies. In Proceedings of the international conference on multimedia information retrieval, p. 91–100.

Müller W. T., Eisenhardt M., Henrich A. (2003, December). Efficient content-based P2P image retrieval using peer content descriptions. In Internet imaging v. edited by santini, simone; schettini, raimondo. proceedings of the spie, volume 5304, pp. 57-68 (2003)., p. 57–68.

Nikseresht A., Gelgon M. (2008). Gossip-based computation of a gaussian mixture model for distributed multimedia indexing. Multimedia, IEEE Transactions on, vol. 10, no 3, p. 385–392.

Patanè G., Russo M. (2001, November). The enhanced LBG algorithm. Neural Networks, vol. 14, no 9, p. 1219–1237.

Patanè G., Russo M. (2000). Elbg implementation. International Journal of Knowledge based Intelligent Engineering Systems, vol. 2, p. 2–4.

Perronnin F., Dance C. R. (2007, June). Fisher kernels on visual vocabularies for image categorization. In Ieee international conference on computer vision and pattern recognition, p. 1–8.

Picard D., Gosselin P.-H. (2011, September). Improving image similarity with vectors of locally aggregated tensors. In Ieee international conference on image processing. Brussels, Belgique. Retrieved from http://hal.archives-ouvertes.fr/hal-00591993/en/

Picard D., Revel A., Cord M. (2012). An application of swarm intelligence to distributed image retrieval. Information Sciences, vol. 192, p. 71–81.

Shah D. (2009). Gossip algorithms. Now Publishers Inc.

Shindler M., Meyerson A., Wong A. (2011). Fast and accurate k-means for large datasets. In Proc. of twenty-fifth annual conference on neural information processing systems (nips).

Sivic J., Zisserman A. (2003). Video google: A text retrieval approach to object matching in videos. In Ieee international conference on computer vision, vol. 2, p. 1470–1477.

Wang J., Yang J., Yu K., Lv F., Huang T., Gong Y. (2010). Locality-constrained linear coding for image classification. In Ieee international conference on computer vision and pattern recognition, p. 3360–3367.

Yang J., Yu K., Gong Y., Huang T. (2009). Linear spatial pyramid matching using sparse coding for image classification. In Computer vision and pattern recognition, 2009. cvpr 2009. ieee conference on, p. 1794–1801.