Content-based retrieval using heuristic search
Inhaltsverzeichnis
Referenz
D. Papadias, M. Mantzourogiannis, P. Kalnis, N. Mamoulis and I. Ahmad: Content-based retrieval using heuristic search. Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, 1999
DOI
http://dx.doi.org/10.1145/312624.312673
Abstract
The fast growth of multimedia information in image and video databases has triggered research on efficient retrieval methods. This paper deals with structural queries, a type of content-based retrieval where similarity is not defined on visual properties such as color and texture, but on object relations in space. We propose the application of heuristic algorithms which provide good, but not necessarily optimal, solutions in a pre-determined time period, and compare our approach with systematic search methods which are guaranteed to find optimal solutions but require exponential time in the worst case. The quality of the output is calculated using a relation framework which is an extension of Allen’s relations. With this framework our methods can be applied in multiple resolutions and dimensions, thus covering a wide range of applications in spatial, multimedia and video systems.
Extended Abstract
Bibtex
@inproceedings{Papadias:1999:CRU:312624.312673,
author = {Papadias, Dimitris and Mantzourogiannis, Marios and Kalnis, Panos and Mamoulis, Nikos and Ahmad, Ishfaq},
title = {Content-based Retrieval Using Heuristic Search},
booktitle = {Proceedings of the 22Nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval},
series = {SIGIR '99},
year = {1999},
isbn = {1-58113-096-1},
location = {Berkeley, California, USA},
pages = {168--175},
numpages = {8},
url = {http://dx.doi.org/10.1145/312624.312673 http://de.evo-art.org/index.php?title=Content-based_retrieval_using_heuristic_search},
doi = {10.1145/312624.312673},
acmid = {312673},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {MMIR, content-based indexing/retrieval, image indexing/retrieval},
}
Used References
1 James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 http://doi.acm.org/10.1145/182.358434
2 Bach J., Fuller C., Gupta A., Hampapur A., Horowitz B., Humphrey R., Jain R. "The Virage Image Search Engine: An Open framework for Image Management". SPIE, Storage and Retrieval for Still Image and Video Databases, vol. 2670, pp. 76-87, 1996.
3 Bergman, L. Castelli, V., Li C-S. "Progressive Content- Based Retrieval from Satellite Image Archives". D-Lib Magazine, October 1997.
4 Fahiem Bacchus , Adam J. Grove, On the Forward Checking Algorithm, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.292-308, September 19-22, 1995 http://dl.acm.org/citation.cfm?id=726152&CFID=558819604&CFTOKEN=68186175
5 Cerny V. "Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulation Algorithm". J. Opt. Theory Appl., 45, 41-51, 1985.
6 Clark, D., Frank, J., Gent, I., MacIntyre, E., Tomov, N., Walsh, T. "Local Search and the Number of Solutions". International Conference on Principles and Practice of Constraint Programming, 1998.
7 Chang S.F, Smith J.R., Meng H.J, Wang H., Zhong D. "Finding Images/Video in Large Archives". CNRI Digital Library Magazine, Feb. 1997.
8 Vasilis Delis , Dimitris Papadias , Nikos Mamoulis, Assessing multimedia similarity: a framework for structure and motion, Proceedings of the sixth ACM international conference on Multimedia, p.333-338, September 13-16, 1998, Bristol, United Kingdom http://doi.acm.org/10.1145/290747.290797
9 Kenneth A. De Jong , William M. Spears, An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms, Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, p.38-47, October 01-03, 1990 http://dl.acm.org/citation.cfm?id=670188&CFID=558819604&CFTOKEN=68186175
10 Egenhofer, M. "Query Processing in Spatial-Query-by- Sketch". Journal of Visual Languages and Computing, Vol. 8, 403-424, 1997. http://dx.doi.org/10.1016/0004-3702(92)90090-K
11 Christian Freksa, Temporal reasoning based on semi-intervals, Artificial Intelligence, v.54 n.1-2, p.199-227, March 1992 http://dx.doi.org/10.1016/0004-3702(92)90090-K
12 Ferman A.M., Gunsel B., Tekalp A.M., "Object-Based Indexing of MPEG4 Compressed Video". Visual Communications and Image Processing, SPIE 1997, Vol. 3024, pp. 953-963.
13 J Grefenstette, Optimization of control parameters for genetic algorithms, IEEE Transactions on Systems, Man and Cybernetics, v.16 n.1, p.122-128, Jan./Feb. 1986 http://dx.doi.org/10.1109/TSMC.1986.289288
14 David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989 http://dl.acm.org/citation.cfm?id=534133&CFID=558819604&CFTOKEN=68186175
15 Amarnath Gupta , Ramesh Jain, Visual information retrieval, Communications of the ACM, v.40 n.5, p.70-79, May 1997 http://doi.acm.org/10.1145/253769.253798
16 Venkat N. Gudivada , Vijay V. Raghavan, Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Transactions on Information Systems (TOIS), v.13 n.2, p.115-144, April 1995 http://doi.acm.org/10.1145/201040.201041
17 John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992 http://dl.acm.org/citation.cfm?id=129194&CFID=558819604&CFTOKEN=68186175
18 Haralick R.M., Elliot G.L. "Increasing Tree Search Efficiency for Constraint Satisfaction Problems". Artificial Intelligence, vol. 14, pp. 263-313, 1980.
19 Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, USA http://doi.acm.org/10.1145/93597.98740
20 David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 http://dx.doi.org/10.1287/opre.37.6.865
21 Kirkpatrick S., Gelat, C., Vecchi, M. "Optimization by Simulated Annealing". Science, 220, 671-680, 1983.
22 Niblack W. Barber R., Equitz W., Flickner M., Glasman E., Petkovic D., Yanker P., Faloutsos C., Taubin G. "The QBIC Project: Querying Images by Content Using Color Texture, and Shape". SPIE, vol. 1908, Storage Retrieval for Image and Video Databases, pp. 173-187, 1993.
23 Mohammad Nabil , Anne H. H. Ngu , John Shepherd, Picture Similarity Retrieval Using the 2D Projection Interval Representation, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.533-539, August 1996 http://dx.doi.org/10.1109/69.536246
24 Surendra Nahar , Sartaj Sahni , Eugene Shragowitz, Simulated annealing and combinatorial optimization, Proceedings of the 23rd ACM/IEEE Design Automation Conference, p.293-299, July 1986, Las Vegas, Nevada, USA http://dl.acm.org/citation.cfm?id=318059&CFID=558819604&CFTOKEN=68186175
25 Dimitris Papadias , Nikos Mamoulis , Vasilis Delis, Algorithms for Querying by Spatial Structure, Proceedings of the 24rd International Conference on Very Large Data Bases, p.546-557, August 24-27, 1998 http://dl.acm.org/citation.cfm?id=671163&CFID=558819604&CFTOKEN=68186175
26 Dimitris Papadias , Nikos Mamoulis , Dimitris Meretakis, Image similarity retrieval by spatial constraints, Proceedings of the seventh international conference on Information and knowledge management, p.289-296, November 02-07, 1998, Bethesda, Maryland, USA http://doi.acm.org/10.1145/288627.288669
27 Papadias, D., Karacapilidis, N., Arkoumanis, D. "Processing Fuzzy Spatial Queries: A Configuration Similarity Approach". International Journal of Geographic Information Science Vol. 13(2), pp. 93-118, 1999.
28 Pentland A., Picard R., Sclaroff S. "Photobook: Tools for Content-Based Manipulation of Image Databases". SPIE, vol. 2185, Storage and Retrieval for Image and Video Databases, pp.34-47, 1994.
29 John R. Smith , Shih-Fu Chang, VisualSEEk: a fully automated content-based image query system, Proceedings of the fourth ACM international conference on Multimedia, p.87-98, November 18-22, 1996, Boston, Massachusetts, USA http://doi.acm.org/10.1145/244130.244151
30 Srinivas, M., Patnaik, L.M. "Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms". IEEE Trans. Systems, Man and Cybernetics, vol. 24(4), 656-667, 1994.
Links
Full Text
http://i.cs.hku.hk/~nikos/sigir99.pdf
