Journal of Digital Contents Society (디지털콘텐츠학회 논문지)

Digital Contents Society (한국디지털콘텐츠학회)
권호 표지
DOI QR코드

DOI QR Code

An Efficient Vector Quantization Codebook generation using a Triangle Inequality

삼각 부등식을 이용한 빠른 벡터 양자화 코드북 생성

  • 이현진 (숭실사이버대학교 컴퓨터정보통신학과)
  • Received : 2012.08.01
  • Accepted : 2012.08.20
  • Published : 2012.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

Active data are the input data which are changed its membership as Vector Quantization codebook generation algorithm is processed. In the process of VQ codebook generation algorithm performed, the actual active data out of the entire input data will be less presented as the process is performed. Therefore, if we can accurately find the active data and only if we are going to do VQ codebook generation on the active data, then we can significantly reduce the overall generation time. In this paper, we presented the triangle inequality based algorithm to select the active data. Experimental results show that our algorithm is superior to other methods in terms of the VQ codebook generation time.

액티브 데이터는 벡터 양자화 코드북이 생성될 때 소속된 군집이 변경되는 입력 데이터이다. 벡터 양자화 코드북 생성 알고리즘의 수행 과정을 살펴보면, 전체 입력 데이터 중 실제 액티브 데이터는 알고리즘이 반복될 수록 감소된다. 따라서 액티브 데이터를 정확히 추정하여, 추정된 액티브 데이터에 대해서 코드북 생성을 수행하면, 전체 코드북 생성 시간을 크게 단축할 수 있다. 본 논문에서는 삼각 부등식을 이용하여 액티브 데이터를 선택하는 방법을 제안한다. 실험결과 액티브 데이터들을 빠른 시간에 추정할 할 수 있었고, 이를 통해 전체 벡터 양자화 코드북 생성 시간 측면에서 우수한 성능을 보였다.

Keywords

References

  1. Tzu-Chuen Lu, and Ching-Yun Chang, "A Survey of VQ Codebook Generation," Journal of Information Hiding and Multimedia Signal Processing, vol. 1, no. 3, pp. 190-203, 2010.
  2. Gersho A, and Gray RM, "Vector Quantization and Signal Compression," Boston, MA: Kluwer Academic Publishers, 1991.
  3. Liaw YC, Lai JZC, and Lo W, "Image restoration of compressed image using classified vector quantiz ation," Pattern Recognition 35: 329-340, 2002 https://doi.org/10.1016/S0031-3203(01)00048-6
  4. Theodoridis S, and Koutroumbas, "Pattern Recognition. 2nd edn.," New York: Elsevier Academic Press, 2003.
  5. Lai JZC, and Liaw YC, "Fast-searching algorithm for vector quantization using projection and triangular inequality," IEEE Trans. Image Processing 13: 1554-1558, 2004 https://doi.org/10.1109/TIP.2004.837559
  6. C. W. Tsai, C. Y. Lee, M. C. Chiang, and C. S. Yang, "A Fast VQ Codebook Generation Algorithm via Pat tern Reduction, Pattern Recognition Letters", vol. 30, pp. 653-660, 2009. https://doi.org/10.1016/j.patrec.2009.02.003
  7. Xiao-Gang W, and Yue L, "Web mining based on user access patterns for web personalization," ISECS International Colloquium on Computing, Communication, Control, and Management. 1: 194-197, 2009.
  8. Gan G, Ma C, and Wu J, "Data Clustering: Theory, Algorithms, and Applications," Philadelphia, PA: SIAM, 2007.
  9. Krishnamoorthy R, Kalpana J, "Minimum distortion clustering technique for orthogonal polynomials tra nsform vector quantizer," Proc. 2011 Inter. Conf. Communication, Computing & Security. 443-448, 2011.
  10. Dumitrescu S, Wu X, "On properties of locally optimal multiple description scalar quantizers with convexcells," IEEE Trans. Inform. Theor. 55: 5591-5606, 2009. https://doi.org/10.1109/TIT.2009.2032831
  11. Lai JZC, and Lue CC, "Fast search algorithms for VQ codebook generation," J. Vis. Comm. Image Represent. 7: 163-168, 1996. https://doi.org/10.1006/jvci.1996.0016
  12. Huang CM, Bi Q, Stiles GS, and Harris RW, "Fast full search equivalent encoding algorithms for image compression using vector quantization", IEEE Trans. Image Process. 1: 413-416, 1992. https://doi.org/10.1109/83.148613
  13. Pelleg D, and Moore A, "Accelerating exact K-means algorithms with geometric reasoning," Proc. AC M SIGKDD. 277-281, 1999.
  14. Kanungo T, Mount D, Netanyahu N, Piatko C, and Silverman R, "An efficient K-means clustering algo rithm: Analysis and implementation," IEEE Trans. Pattern Anal. Mach. Intell. 24: 881-892, 2002. https://doi.org/10.1109/TPAMI.2002.1017616
  15. 김성재, 안철응, 김승호, "벡터 양자화를 위한 삼각 부등식을 이용하는 빠른 코드북 탐색법," 한국정보과학회 1998년도 가을 학술발표논문집 제25권 제2호(II), pp. 526-528, 1998.
  16. Charles Elkan, "Using the Triangle Inequality to Accelerate k-Means," Proceedings of the Twentieth International Conference on Machine Learning, 147-153, 2003.
  17. T. Zhang, R. Ramakrishnan, and M. Livny, "BIRCH: an efficient data clustering method for very large databases," Proceedings of the ACM SIGMOD, pp. 103-114, 1996.
  18. A.W. Moore, "The anchors hierarchy: Using the tria ngle inequality to survive high dimensional data," Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, pp. 397-405, 2000.
  19. KDDCUP 1993, www.cs.purdue.edu/commugrate/data/kddcpu/1998
  20. MNIST Dataset, yann.lecun.com/exdb/mnist
  21. Ji He, Man Lan, Chew-Lim Tan, Sam-Yuan Sung and Hwee-Boon Low, "Initialization of clusters refinement algorithms: a review and comparative study," International Joint Conference on Neural Networks, pp. 25-29, 2004.

Cited by

  1. Online VQ Codebook Generation using a Triangle Inequality vol.16, pp.3, 2015, https://doi.org/10.9728/dcs.2015.16.3.373
  2. Mathematical Thinking of Elementary School Students and Teacher Roles during Problem-Solving Process to Form the Concept of Triangle Inequality vol.28, pp.2, 2012, https://doi.org/10.29275/jerm.2018.05.28.2.203