Abstract

We propose the use of approximate digital signatures of selected multimedia feature vectors for fast content-based retrieval in large multimedia databases. We adapt and extend the approximate message authentication code (AMAC), introduced by some of the authors recently in the area of message authentication, to the multimedia searching problem. An AMAC is a binary signature with the ability to reflect changes in the message it represents. The Hamming distance between two AMACs is used to measure the degree of the similarity between multimedia objects. We develop a method to compress AMAC signatures to create a direct look-up table that allows for fast searching of a database. The color histogram is used as the example feature space to show how the signature is applied. Experimental results show that the performance of the proposed method is comparable with existing methods based on other popular metrics, but it significantly decreases search time.

© 2003 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. V. N. Gudivada, J. V. Raghavan, “Special issue on content-based image retrieval system,” IEEE Comput. 28, 18–22 (1995).
    [CrossRef]
  2. Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
    [CrossRef]
  3. R. F. Gravemen, K. Fu, “Approximate message authentication codes,” in Proceedings of the Third Annual Fedlab Symposium on Advanced Telecommunications Information Distribution (College Park, Md., 1999), Vol. 1, pp. 411–416.
  4. L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).
  5. A. Gionis, P. Indyk, R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the Twenty-Fifth Very Large Database Conference (Morgan Kaufmann, San Francisco, 1999).
  6. M. Swain, D. Ballard, “Color indexing,” Int. J. Comput. Vision 7, 11–32 (1991).
    [CrossRef]
  7. M. Ioka, “A method of defining the similarity of images on the basis of color information,” IBM Research Technique Report RT-0030 (IBM Research, Tokyo Research Laboratory, 1989).
  8. W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).
  9. J. Smith, S. F. Chang, “VisualSEEK: a fully automated content-based image query system,” in Proceedings of the Fourth ACM Multimedia (ACM, New York1996), pp. 87–98.

2001 (1)

L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).

1999 (1)

Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
[CrossRef]

1995 (1)

V. N. Gudivada, J. V. Raghavan, “Special issue on content-based image retrieval system,” IEEE Comput. 28, 18–22 (1995).
[CrossRef]

1991 (1)

M. Swain, D. Ballard, “Color indexing,” Int. J. Comput. Vision 7, 11–32 (1991).
[CrossRef]

Arce, G. R.

L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).

Ballard, D.

M. Swain, D. Ballard, “Color indexing,” Int. J. Comput. Vision 7, 11–32 (1991).
[CrossRef]

Barber, R.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Chang, S.

Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
[CrossRef]

Chang, S. F.

J. Smith, S. F. Chang, “VisualSEEK: a fully automated content-based image query system,” in Proceedings of the Fourth ACM Multimedia (ACM, New York1996), pp. 87–98.

Equitz, W.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Faloutsos, C.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Flickner, M.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Fu, K.

R. F. Gravemen, K. Fu, “Approximate message authentication codes,” in Proceedings of the Third Annual Fedlab Symposium on Advanced Telecommunications Information Distribution (College Park, Md., 1999), Vol. 1, pp. 411–416.

Gionis, A.

A. Gionis, P. Indyk, R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the Twenty-Fifth Very Large Database Conference (Morgan Kaufmann, San Francisco, 1999).

Glasman, E.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Graveman, R. F.

L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).

Gravemen, R. F.

R. F. Gravemen, K. Fu, “Approximate message authentication codes,” in Proceedings of the Third Annual Fedlab Symposium on Advanced Telecommunications Information Distribution (College Park, Md., 1999), Vol. 1, pp. 411–416.

Gudivada, V. N.

V. N. Gudivada, J. V. Raghavan, “Special issue on content-based image retrieval system,” IEEE Comput. 28, 18–22 (1995).
[CrossRef]

Huang, T. S.

Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
[CrossRef]

Indyk, P.

A. Gionis, P. Indyk, R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the Twenty-Fifth Very Large Database Conference (Morgan Kaufmann, San Francisco, 1999).

Ioka, M.

M. Ioka, “A method of defining the similarity of images on the basis of color information,” IBM Research Technique Report RT-0030 (IBM Research, Tokyo Research Laboratory, 1989).

Motwani, R.

A. Gionis, P. Indyk, R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the Twenty-Fifth Very Large Database Conference (Morgan Kaufmann, San Francisco, 1999).

Niblack, W.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Petkovic, D.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

Raghavan, J. V.

V. N. Gudivada, J. V. Raghavan, “Special issue on content-based image retrieval system,” IEEE Comput. 28, 18–22 (1995).
[CrossRef]

Rui, Y.

Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
[CrossRef]

Smith, J.

J. Smith, S. F. Chang, “VisualSEEK: a fully automated content-based image query system,” in Proceedings of the Fourth ACM Multimedia (ACM, New York1996), pp. 87–98.

Swain, M.

M. Swain, D. Ballard, “Color indexing,” Int. J. Comput. Vision 7, 11–32 (1991).
[CrossRef]

Xie, L.

L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).

Yanker, P.

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

IEEE Comput. (1)

V. N. Gudivada, J. V. Raghavan, “Special issue on content-based image retrieval system,” IEEE Comput. 28, 18–22 (1995).
[CrossRef]

IEEE Trans. Multimedia (1)

L. Xie, G. R. Arce, R. F. Graveman, “Approximate image message authentication codes,” IEEE Trans. Multimedia 2, 242–252 (2001).

Int. J. Comput. Vision (1)

M. Swain, D. Ballard, “Color indexing,” Int. J. Comput. Vision 7, 11–32 (1991).
[CrossRef]

J. Visual Commun. Image Represent. (1)

Y. Rui, T. S. Huang, S. Chang, “Image retrieval: current techniques, promising directions and open issues,” J. Visual Commun. Image Represent. 10, 1–23 (1999).
[CrossRef]

Other (5)

R. F. Gravemen, K. Fu, “Approximate message authentication codes,” in Proceedings of the Third Annual Fedlab Symposium on Advanced Telecommunications Information Distribution (College Park, Md., 1999), Vol. 1, pp. 411–416.

A. Gionis, P. Indyk, R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the Twenty-Fifth Very Large Database Conference (Morgan Kaufmann, San Francisco, 1999).

M. Ioka, “A method of defining the similarity of images on the basis of color information,” IBM Research Technique Report RT-0030 (IBM Research, Tokyo Research Laboratory, 1989).

W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, “QBIC project: querying images by content, using color, texture, and shape,” in Storage and Retrieval for Image and Video Databases, C. W. Niblack, ed., Proc. SPIE1908, 172–187 (1994).

J. Smith, S. F. Chang, “VisualSEEK: a fully automated content-based image query system,” in Proceedings of the Fourth ACM Multimedia (ACM, New York1996), pp. 87–98.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (20)

Fig. 1
Fig. 1

Adapted AMAC algorithm.

Fig. 2
Fig. 2

Characteristic AMAC probability curve.

Fig. 3
Fig. 3

Content-based digital signature-generation system.

Fig. 4
Fig. 4

Compressing AMACs.

Fig. 5
Fig. 5

HSV space and its quantization. In this example, quantization gives six hues, two saturations, and two values.

Fig. 6
Fig. 6

Average rank of the top ten L 1 matches with the direct-search AMAC algorithm.

Fig. 7
Fig. 7

Metric: Hamming distance between the signatures; query image: sunset.

Fig. 8
Fig. 8

Metric: L 1 distance between the coupled histograms; query image: sunset.

Fig. 9
Fig. 9

Metric: quadratic distance; query image: sunset.

Fig. 10
Fig. 10

Metric: histogram intersection; query image: sunset.

Fig. 11
Fig. 11

Metric: Hamming distance between the signatures; query image: grassland.

Fig. 12
Fig. 12

Metric: L 1 distance between the coupled histograms; query image: grassland.

Fig. 13
Fig. 13

Metric: quadratic distance; query image: grassland.

Fig. 14
Fig. 14

Metric: histogram intersection; query image: grassland.

Fig. 15
Fig. 15

Metric: Hamming distance between the signatures; query image: flowers.

Fig. 16
Fig. 16

Metric: L 1 distance between the coupled histograms; query image: flowers.

Fig. 17
Fig. 17

Metric: quadratic distance; query image: flowers.

Fig. 18
Fig. 18

Metric: histogram intersection; query image: flowers.

Fig. 19
Fig. 19

Comparison of the coupled histograms that use various α. (a) The original histogram is shown. (b), (c), and (d) The coupled histograms that use α = 4, 10, and 1 are shown, respectively.

Fig. 20
Fig. 20

Absolute distance of the coupled histograms varies with α.

Tables (2)

Tables Icon

Table 1 Average Ranks by Use of Various Metrics

Tables Icon

Table 2 Comparison of Different Histogram Metrics

Equations (10)

Equations on this page are rendered with MathJax. Learn more.

PN1= Rn112R, n1=0, 1,, R.
PAR, d=n1=0RPN1n1k=0n1 PKk|R, d, n1×PX|R, d, n1, k,
PK=n1kR-n1d-kRd.
signR-2n1signR-2n1+4k-2d.
bij= 00j<vi1vij<N-1,
majorityv= 0n0>n11n0<n1.
dsh1, h2=m=0N-1minh1m, h2mm=0N-1 h1m,
dqh1, h2=m=0N-1n=0N-1h1m-h2mam,n× h1n-h2n,
hcj=i=0N-1 ai,jαh i,
T= D/2K1+KD= 1+K2K

Metrics