Digital Imaging & Data Compression

 

IMAGE INDEXING

AND RETRIEVAL IN COMPRESSED DOMAIN

Overview

Present research in content-based image indexing and retrieval is based on pixels[1-2,54-56,58], which means that the imaging information system is constructed by storing original images. As the huge amount of storage required grow, data compression technology becomes essential. In such a case, the only possible way of using data compression to reduce the size of the database is to compress the population of images separately after each original image is analysed and indexed. In this context, decompression is required before any automatic retrieval could be performed. On the other hand, data compression is developed not only for saving the storage space but, more importantly, also for improving the efficiency of information retrieval and processing, since unnecessary redundancy has been removed in the compressed data. Therefore, our research is focused on investigating a number of original ideas to develop an image indexing and compression algorithm via which, automatic image retrieval can be directly operated in compressed data domain.

Present research in automatic image indexing and retrieval is based on two approaches[38,41]: attribute based retrieval and feature-extraction/object-recognition based retrieval. The former manually models the contents of the image into a set of attributes which can then be managed and processed by conventional database management systems. The latter represents the latest efforts by image processing communities to extract automatically a set of features such as texture, colour, shapes, edges, etc. to interpret images stored inside a database. Retrieval is carried out by similarity measurements, which produce a ranking order of similar images. One of the typical examples for such a system is QBIC[9] developed by IBM researchers which extracts semi-automatically object motion (for video images), colour and texture patterns (for still images) as the main features. Users may then use these features to construct sketches and example images with which to query the database.

This direction of research for image indexing and retrieval in pixel domain is very active both in UK and around the world. Fruitful research in the UK is represented by research groups in Universities of Glasgow, City, Bristol, Northumbria and Sheffield etc[52-58]. Further details about the UK efforts in this area are available from the Library & Information Commission, UK.

In this context, our approach will firstly decompose images into a number of features such as colour, texture, shape, spatial relationship etc. in the domain of ortho-normal transforms[44]. The analysis of all the features mentioned will be integrated by a technique called visual activity analysis which will act as the major parameter to control both data compression and key construction for image indexing. On the one hand, a data compression algorithm can be designed by exploiting human visual perception[50,51,55] of different features to determine the appropriate approach for the best possible performance and, on the other hand, a new compressed image indexing technique is developed by using these compressed features as multiple keys to retrieve images. Hence, only compressed codes are stored inside the image database, and the compressed image quality can be controlled by providing three categories of data compression, i.e., (i) lossy compression; (ii) near lossless compression and (iii) lossless compression. As a result, both image indexing and data compression are achieved using one algorithm.

Our Research Programme

The research programme consists of the following phases.

Phase 1. Conventional Image Database Design

In this phase, the primary goal is to design a conventional image database to provide a research platform and establish a benchmarking system for the proposed research. This work will also enable the investigators to build up a simple yet demonstrable working model, upon which further improvements can be built in areas such as user-friendly access and convenience, retrieving speed, on-line editing and browsing etc. Apart from those images publicly available on the Internet (such as QBIC), some special images will also be added to test both the data compression performance and image retrieval in compressed domain.

Phase 2. Algorithm Development for Image Indexing in Compressed Data Domain (month 5-30)

In this phase, effort is concentrated on developing algorithms for image indexing using multiple keys in the compressed data domain. The research will be carried out in three stages.

Data compression for image indexing: The data compression technology to be developed in this stage of the project is specifically aimed at providing a transparent compression working seamlessly with automatic image indexing and retrieval. This will be achieved by developing a quality adaptive, content based and rate controllable image compression technique.

The term, quality adaptive, means that the compression performance of the algorithm can be controlled by a quality requirement automatically for each individual reconstructed image, with compression ranging from lossy through near lossless to lossless. In response to the quality requirement specified by end users, the algorithm determines which of these three compression techniques is appropriate. With lossy compression, DCT based JPEG is a good candidate to work on, especially the quality index controlling mechanism. With near lossless and lossless compression, however, it will be necessary to investigate: (a) small quantization, (b) statistics modelling for entropy coding and (c) non-linear prediction based on local feature analysis. To integrate DCT-based lossy compression with the prediction-based near lossless and lossless compression, further investigations will be required to streamline the operations for all three categories and hence make the overall algorithm cost effective and easy to implement on various computing platforms.

For indexing-based compression, established object identification and recognition techniques will be exploited. We are not, however, going to carry out any development work in object recognition and, instead, we will use those well established techniques such as bit mapping alpha planes etc. to reflect the features of images in data compression. The emerging world-wide standard MPEG-4[51], for instance, is a successful example in this context. It is envisaged that the indexing based compression will provide better linkage with automatic retrieval, especially when manual editing and highlighting of those areas of interests are added.

For rate-controllable compression, it means that the compressed bit rate is controlled around a fixed value independent of the variety of images inside the database. This will provide a better management of the storage space for the whole image population. One example of such a scenario is that users often expect the storage space be the same if one image is deleted and replaced by another. Hence, to provide such a concealed data compression for image database management, rate control is inevitable. This will be implemented by adaptively controlling the quantization step in the local feature analysis of those surrounding pixels when each pixel is encoded[35]. In addition, the texture analysis can be embedded in the non-linear prediction process. The JPEG-LS is a good example of this non-linear prediction in which a horizontal or vertical edge is to be detected first before the predictive value is selected. The rate controllable technique, however, is only applicable to lossy and near lossless compression.

Construction of multiple keys: From the success of our previous work[26], we will use histograms as the starting point from which to build multiple keys. To reflect the content of each image, the histograms will be constructed from various mature feature analysis techniques including colour mapping[37], texture analysis[38,39] and pattern recognition[41] etc. To improve the indexing performance, manual editing and highlighting of query images are to be added in those areas of interest in the query image deemed to be of importance before the database population is searched.

To develop the image indexing and data compression into one single algorithm, it is required in principle that the multiple keys or histograms be constructed from the compressed codes or from the compression process. A number of approaches will be investigated depending on what techniques are to be adopted for feature analysis and identification, such as colour, shape and spatial relationship, texture etc. Specific ideas to be investigated will include:

  1. For colour based histograms, the number of elements can be initially set up as three corresponding to R (red), G (green), and B (blue). Further expansion can be considered by constructing an array in which the number of elements is associated with those regions of interest highlighted. Each element of the histogram is then obtained by counting the number of code-words used for each basic colour (R,G,B). In this way, the count, arising from the compression process that produces the code-words for each basic colour, will represent the colour texture of the input image. Hence it can be used for automatic retrieval in the compressed data domain. In addition, the counting process can also be weighted by factors obtained from the feature analysis process similar to that used in our previous work[26].

  2. Visual activity analysis is a technique which allocates an activity value for each pixel to be encoded. High activity reflects noisier areas and low activity represents smooth areas. In data compression, the activity value can be used to determine the extent of information loss (quantization step for instance) in lossy compression and the predictive value in lossless compression. Consequently, the number of activity values defines a range of image content or the feature of the local image gradient. Hence, histograms of activity values can be used directly for automatic image indexing and retrieval. Specifically, histograms can be constructed in such a way that each activity value is counted during data compression while each pixel is being compressed. In addition, features of human visual perception can also be exploited based on this activity analysis.

  3. The activity analysis can be performed using mature feature analysis techniques developed in image processing community, such as segmentation[37,44], edge detection[37-39,41], contour and texture analysis[7,37], spatial relationship construction[37-39,41] etc. Correspondingly, a number of histograms can be built up during the process to reflect various aspects of the image features for more efficient image indexing and retrieval.

  4. Various distance measurements need to be extensively investigated in order to provide the best possible performance for indexing and retrieval in various contexts. For those query images with manually highlighted regions, adaptive measurement and search will be developed in the algorithm by adding weighting factors and priorities to these highlighted regions. For the database population, however, it is sufficient to develop the search process in terms of the shape and the size of these highlighted regions.

  5. Co-ordination of multiple keys is required to optimise the overall performance not only for the image indexing but also for data compression.

  6. Browsing of targeted images will be further designed to enable users to achieve accurate retrieval, exhaustive search and flexibility in working procedures.

Feature analysis in the transformed coefficients domain: A number of possible options are investigated to see if mature feature analysis techniques can be implemented in terms of transformed coefficients rather than pixels. The benefits of so doing will enable us to construct histograms directly from these coefficients rather than from the activity values used to determine the encoding of each pixel or coefficient. In this stage, wavelet transforms[43,45,49], DCT[51], and K-L transforms implemented by various neural networks[28,51] will be the candidates for investigation. The development work carried out at this stage will only be useful for lossy compression based indexing and retrieval, due to the fact that, in this project, lossy compression will be developed from established transform based compression techniques such as DCT-based JPEG.

Figure 1 illustrates an overall structure of our image indexing and retrieval system.

                               wpe1.jpg (22721 bytes)

Phase 3. Database Management Systems

Image databases, capable of supporting large visual information systems, could contain millions of images and video clips. To improve the searching speed, so as to achieve effective on-line retrieval, a high performance algorithm will be designed to classify and map the database population into an appropriate structure to support comprehensive and efficient multi-key access.

To enable users to explore the database interactivity, the possibility of allowing users to be given facilities to analyse and modify the query image will be investigated.

The starting point for our investigation is quad-tree[46] and R* tree[2]. http://www.lic.gov.uk/research/information_retrieval/ir-calla.html

This project is funded by Library & Information Commission in the UK.

 

References

  1. Ballard D.H. ‘Generalizing the hough transform to detect arbitrary shapes’, Pattern Recognition, Vol. 13, 1981, pp 111-122.

  2. Beckmann N. et al. ‘The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of ACM SIGMOD, pp 322-331, May 1990.

  3. Brink A. et al. ‘Heterogeneous multimedia reasoning’, IEEE Computer, September 1995, pp 33-39.

  4. Butler, D and Jiang, J. ‘Distortion equalized fuzzy competitive learning for image data vector quantization’ IEEE Proceedings of ICASSP’96, Vol. 6, 1996. ISBN: 0-7803-3193-1, pp3390-3394.

  5. Cagigal M.P. et al. ‘Erroe reduction in centroid estimates using nonlinear image detectors’, Optical Engineering, Vol 35, No 10, 1995, pp 2894-2897.

  6. Chen C.W. ‘A cellular neural network architecture for image segmentation and video coding’ Electronic Imaging, SPIE, Vol 7, No 1, 1997.

  7. Dunn D.F. et al. ‘Extracting halftones from printed documents using texture analysis’ Optical Engineering, Vol 36, No 4, April 1997, pp 1044-1052.

  8. Egger O. and Li W. ‘Subband coding of images using asymmetrical filter banks’, IEEE Trans. on Image Processing, Vol 4, No 4, 1995, pp 478-485.

  9. Flickner M. et. al. ‘Query by image and video content: The QBIC system’, IEEE Computer, September 1995, pp 23-32.

  10. Guan L, ‘Full custom texture measurement and applications in multiresolution video coding’ Optical Engineering, Vol 36, No 4, 1997, pp 1053-1058.

  11. Iftekharuddin K.M. et al. ‘Feature-based neural wavelet optical character recognition system’ Optical Engineering, Vol 34, No 11, 1995, pp 3193-3199.

  12. Jiang, J. ‘A neural network design for image compression and indexing’, Proceedings of IASTED International Conference: Artificial Intelligence, Expert Systems & Neural Networks, August 19-22, 1996 Hawaii, USA, ISBN 0-88986-211-7, pp296-299.

  13. Jiang J. and Jones S. ‘Word-based dynamic algorithms for data compression’ IEE Proceedings-I: Communications Vol. 139, No. 6, December 1992 pp 582-586.

  14. Jiang, J. and Jones S. ‘Parallel design of arithmetic coding’ IEE Proceedings-E: Computer and Digital Techniques, Vol. 141, No. 6, November, 1994, pp 327-323, ISSN: 1350-2387.

  15. Jiang J. ‘Lossless image compression with wavelet transform’ Proceedings of EUSIPCO-96: VIII European Signal Processing Conference, Vol 2, pp 1147-1150, September 10-13, 1996 Trieste, Italy, ISBN: 88-86179-83-9.

  16. Jiang J. ‘Compressed Image Processing - A New Research Area and Challenge’ Proceedings of IBC’97: International Broadcasting Convention. Amsterdam,1997, ISBN: 0-85296-694-6, pp314-319.

  17. Jiang, J. ‘Design of a LVQ neural network for compressed image indexing’, IEE Proceedings of Fifth International Conference on Artificial Neural Networks, Churchill College, University of Cambridge, UK, 1997, pp 94-99, ISBN: 0 85296 690 3.

  18. Jiang, J. ‘Parallel and neural network implementation of LBG vector quantization’, IEE Proceedings of IPA97: IEE Sixth International Conference on Image Processing, Trinity College, Dublin, Ireland, 1997, ISBN: 0-85296-692-x, ISSN: 0537-9989, pp 27-31

  19. Jiang J. ‘A novel design of arithmetic coding for data compression’ IEE Proceedings-E: Computer and Digital Techniques, Vol 142, No. 6, November 1995, pp 419-424, ISSN 1350-2387.

  20. Jiang, J. ‘Design of neural networks for lossless data compression’ Optical Engineering, Vol 35, No 7, July 1996, pp 1837-1843, ISSN: 0091-3286.

  21. Jiang, J. ‘A novel parallel design of a codec for black and white image compression’ Image Communication, Journal of EUROSIP, Vol 8, August 1996 ELSEVIER, ISSN: 0923-5965. pp 465-474.

  22. Jiang J. ‘Image compression with neural networks - A survey’ Image Communication, Journal of EUROSIP, ELSEVIER, Vol 14,No 9, ISSN: 0923-5965, 1999.

  23. Edirisinghe E.A. Jiang, J, ‘A contour based object extraction algorithm for MPEG-4’, Accepted to IEEE International conference on Multimedia Computing & Systems, Italy, 1999.

  24. Jiang, J. ‘Neural network based lossless image compression’ Proceedings of Visual’96: International Conference on Visual Information Systems, 5-6 February 1996, Australia, pp 192-200, ISBN: 1-875-33852-7.

  25. Jiang, J. ‘A fast competitive learning algorithm for image compression neural networks’, IEE Electronic Letters, Vol 32, No 15, 1996, pp 1380-1381.

  26. Jiang, J. ‘Image compression and indexing with neural networks’ Journal of Visual Communication and Image Representation. Academic Press, Vol 8, No 2, June 1997, ISSN: 1047-3203, pp135-145.

  27. Jiang, J., Edirisinghe E.A. and Schroder H ‘Algorithm for compression of stereo image pairs’ IEE Electronic Letters, Vol 33, No 12, June, 1997, pp 1034-1035.

  28. Jiang, J. ‘Neural network - next generation technology for image compression’ Proceedings of IBC’95: International Broadcasting Convention, Amsterdam, 14-18, September 1995, pp 250-256, ISBN: 0-85296-644-x.

  29. Jiang, J. Edirisinghe E.A. and Schroder H. ‘A novel predictive coding algorithm for 3-D image compression’, IEEE Transactions on Consumer Electronics, Vol 43, No 3, August,1997, pp430-437.

  30. Lee H. et al. ‘A predictive classified vector quantizer and its sujective quality evaluation for X-ray CT images’ IEEE Trans. on Image processing, Vol 14, No 2, 1995, pp 397-406.

  31. Lee W.C and Lee S.U. ‘Classified vector quantizer techniques for image coding employing the linear phase paraunitary M-band filter bank’, Optical Engineering, Vol 35, No 8, 1996, pp 2266-2275.

  32. Basil G. and Jiang J. ‘An improvement on competitive learning neural network by LBG vector quantization’ Accepted to IEEE International conference on Multimedia Computing & Systems, Italy, 1999.

  33. Jiang, J. ‘A low cost content adaptive and rate controllable near lossless image codec in DPCM domain’ Accepted to IEEE Trans. On Image Processing.

  34. Edirisinghe E.A. Jiang, J, ‘An object driven, block based algorithm for the compression of stereo image pairs’, Accepted to SPIE Proceedings, 1999.

  35. Jiang, J. Reddy M. ‘ An open-loop rate control scheme for JPEG-LS near lossless image compression’ IEE Electronics Letters, Vol 35, No. 6, 1999, pp465-466.

  36. Maller V.A.J. ‘Criminal investigation systems: The growing dependence on advanced computer systems’ IEE Journal of Computing and Control, April 1996.

  37. Marsicoi, M.D. et. al. ‘Indexing pictorial documents by their content: a survey of current techniques’ Image and Vision Computing Vol 15, 1997, pp 119-141.

  38. Narasimhalu, A.D. Guest Editor, special issue on content-based retrieval, ACM Multimedia Systems, Vol. 3, No. 1, Feb. 1995.

  39. Ogle V.E. et al ‘Chabot: Retrieval from a relational database of images’ IEEE Computer, September 1995, pp 40-48.

  40. Radha H. et al. ‘Image compression using binary space partitioning trees’, IEEE Trans. on Image Processing, Vol 5, No. 12, December 1996, pp 1610-1624.

  41. Ralescu A. and Jain R., Guest Editors, Special Issue on Advances in Visual Information Management Systems, J. Intelligent Informations Systems, Vol. 3, No.3, July 1994.

  42. Ranganathan N. et al. ‘A lossless image compression algorithm using variable block size segmentation’ IEEE Trans. On Image Processing, Vol 4, No 10, 1995, pp 1396-1406.

  43. Rinaldo R. and Calvagno G. ‘Image coding by block prediction of multiresolution subimages’ IEEE Trans. On Image Processing, Vol 4, No 7, 1995, pp 909-920.

  44. Ryan T.W. et al. ‘Image compression by texture modeling in the wavelet domain’ IEEE Trans. on Image Processing, Vol 5, No.1, Jan. 1996, pp 26-36.

  45. Said A. and Pearlman W.A. ‘An image multiresolution representation for lossless and lossy compression’ IEEE Trans. On Image Processing, Vol 5, No 9, Sept. 1996, pp 1303-1310.

  46. Samet H. ‘The quadtree and related hierarchical data structures’ ACM Computing Survey, Vol 16, No 2, June 1984, pp 188-260.

  47. Shanbehzadeh J. and Ogunbona P.O. ‘Index-compressed vector quantisation based on index mapping’ IEE Proceedings: Vision, Image and Signal Processing, Vol 144, No 1, Feb. 1997, pp 31-38.

  48. Srihari R. K. ‘Automatic indexing and content-based retrieval of captioned images’ IEEE Computer, September, 1995, pp 49-62.

  49. Wilson R. ‘Multiresolution image modelling’, IEE Electronics & Communication Engineering Journal, April 1997, pp 90-96.

  50. Wu X. ‘Image coding by adaptive tree-structured segmentation’, IEEE Trans. on Information Theory, Vol. 38, No 6, November 1992, pp 1755-1767.

  51. Jiang, J. ‘Video Compression in MPEG-4’, International Conference: Television and Broadcasting on the Internet, WWW and Networks, 21-23, April, 1998, Bradford, UK.

  52. Jones S. and Willett P. ‘readings in information retrieval’ San Francisco: Morgan Kaufmann, 1997.

  53. Agosti M, Crestani F. and Melucci M. ‘Design and implementation of a tool for the automatic construction of hypertexts for information retrieval’ Information Processing & Management, 32(4): 459-476, 1996.

  54. Crestani F., Sebastiani F. and Rijsbergen C.J.’Imaging and information retrieval: variations on a theme’ WIRUL’96, Glasgow.

  55. Eakins, JP, Graham ME and Boardman J.M. ‘Trademark image retrieval by shape similarity’ IEEE Multimedia, 5(2), 1998, pp 53-63.

  56. Shields K, Eakins J.P. and Boardman J.M. ‘Automatic image retrieval using shape features’, New Review of Document and Text Management, 1, 1995, pp 183-198.

  57. Furner J., Ellis D. and Willett P. ‘The representation and comparison of hypertext documents using graphs’, Information Retrieval and Hypertext, Kluwer Academic Publishers, 1996, pp 75-96.

  58. Eakins J.P., Harper DJ and Jose J.M. ‘The challenge of image retrieval’ BCS Electronic Workshops in Computing Series, April 1999.

Back to Research Activities