АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ
Аннотация
Настоящий обзор посвящён алгоритмам кластеризации и возможности их применения к задачам сег-
ментации спутниковых изображений. Рассмотрены основные подходы к разработке алгоритмов, дан
анализ их достоинств и недостатков.
ментации спутниковых изображений. Рассмотрены основные подходы к разработке алгоритмов, дан
анализ их достоинств и недостатков.
Об авторах
Игорь Алексеевич Пестунов
Институт вычислительных технологий СО РАН
Россия
Россия
Юрий Николаевич Синявский
Институт вычислительных технологий СО РАН
Россия
Россия
Список литературы
1. Achtert, E. DeLiClu: boosting robustness, completeness, usability, and efficiency of hierarchical clustering by a closest pair ranking / E. Achtert, C. Bohm, P. Kroger // Proc. 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'06). - Singapore, 2006. - P. 119 - 128.
2. Agrawal, R. Automatic subspace clustering of high dimensional data for data mining applications / R. Agrawal, J. Gehrke, D. Gunopulos, P. Raghavan // SIGMOD Record ACM Special Interest Group on Management of Data. - 1998. - P. 94 - 105.
3. Anderberg, M. R. Cluster analysis for applications / M. R. Anderberg. - Acad. press, 1973.
4. Ankerst, M. OPTICS: ordering points to identify the clustering structure / M. Ankerst, M. M. Breunig, H.-P. Kriegel, J. Sander // Proc. 1999 ACM SIGMOD Intern. Conf. on Management of data. - 1999. - P. 49 - 60.
5. Ball, G. A clustering technique for summarizing multivariate data / G. Ball, D. Hall // Behavioral Sci. -1967. - Vol . 12. - P. 153 - 155.
6. Barbara, D. Using the fractal dimension to cluster datasets / D. Barbara, P. Chen // Proc. 6th ACM SIGKDD. - Boston, MA, 2000. - P. 260 - 264.
7. Berkhin, P. Survey of clustering data mining techniques / P. Berkhin // Tech. Rep. - Accrue Software, 2002.
8. Bouguettaya, A. Comparison of group-based and object-based data clustering techniques / A. Bouguettaya, Q. Le Viet, M. Golea // Proc. 8th Intern. Database Workshop Data Mining, Data Warehousing and Client/Server Databases. - Hong Kong, Singapore: Springer-Verlag, 1997. - P. 119 - 136.
9. Brecheisen, S. Density-based data analysis and similarity search / S. Brecheisen, H.-P. Kriegel, P. Kroger et al. // Multimedia Data Mining and Knowledge Discovery. - Springer, 2006. - P. 94 - 115.
10. Brecheisen, S. Parallel density-based clustering of complex objects / S. Brecheisen, H.-P. Kriegel, M. Pfeifle // Proc. 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'06). - Singapore, 2006. - Lect. Notes in Artificial Intelligence. - Springer, 2006. - Vol. 3918. - P. 179 - 188.
11. Chang, C.-I. An axis-shifted grid-clustering algorithm / C.-I. Chang, N. P. Lin, N.-Y. Jan // Tamkang J. of Sci. and Engineering. - 2009. - Vol. 12. № 2. - P. 183 - 192.
12. Cheng, C.-H. Entropy-based subspace clustering for mining numerical data / C.-H. Cheng, A. W. Fu, Y. Zhang // Proc. ACM SIGKDD Intern. Conf. on Knowledge discovery and data mining. - ACM Press, 1999. - P. 84 - 93.
13. Comaniciu, D. Distribution free decomposition of multivariate data / D. Comaniciu, P. Meer // Patt. Anal. And Appl. - 1999. - V. 2. - P. 22 - 30.
14. Comaiciu, D. Mean shift: a robust approach towards feature space analysis / D. Comaniciu, P. Meer // IEEE Trans. Patt. Anal. Mach. Intell. - 2002. - V. 24. - № 5. - P. 603 - 619.
15. Comaniciu, D. The variable bandwidth mean shift and data-driven scale selection / D. Comaniciu, V. Ramesh, P. Meer // Proc. Eighth IEEE Intern. Conf. on Comp. Vision. - Vancouver, 2001. - V. 1. - P. 438 - 445.
16. Cutting, D. Scatter/gather: a cluster-based approach to browsing large document collections / D. Cutting, D. Karger, J. Pedersen, J. Tukey // Proc. Fifteenth Annual Intern. ACM SIGIR Conf. on Research and Development in Information Retrieval. - Copenhagen, Denmark, 1992. - P. 318 - 329.
17. Dash, M. '1+1>2': merging distance and density based clustering / M. Dash, H. Liu, X. Xu // Proc. Seventh Intern. Conf. on Database Systems for Advanced Applications. - Hong-Kong: IEEE Computer Society, 2001. - P. 32 - 39.
18. Dey, V. A review on image segmentation techniques with remote sensing perspective / V. Dey, Y. Zhang, M. Zhong // ISPRS TC VII Symp. - 100 Years ISPRS, Vienna, Austria, July 5 - 7, 2010. - IAPRS. - Vol. XXXVIII, pt 7A. - P. 31 - 42.
19. Du, K.-L. Clustering: a neural network approach / K.-L. Du // Neural Networks. - 2010. - Vol. 23. - P. 89 - 107.
20. Duda, R. Pattern classification. 2nd ed. / R. Duda, P. Hart, D. Stork. - N.Y.: John Wiley & Sons, 2001.
21. Incremental clustering for mining in a data warehousing environment / M. Ester, H. Kriegel, J. Sander et al. // Proc. 24th Intern. Conf. on Very Large Data Bases. - N.Y.: Morgan Kaufmann, 1998. - P. 323 - 333.
22. A density-based algorithm for discovering clusters in large spatial database / M. Ester, H.-P. Kriegel, J. Sander, X. Xu // Proc. 1996 Intern. Conf. on Knowledge Discovery and Data Mining. - 1996. - P. 226 - 231.
23. Forgy, E. Cluster analysis of multivariate data: efficiency vs. interpretability of classifications / E. Forgy // Biometrics. - 1965. - Vol. 21. - P. 768 - 780.
24. Freedman, D. Fast mean shift by compact density representation / D. Freedman, P. Kisilev // Proc. IEEE Conf. on Comp. Vision and Patt. Recogn. - 2009. - P. 1818 - 1825.
25. Fukunaga, K. The estimation of the gradient of a density function, with applications in patter recognition / K. Fukunaga, L.D. Hosteeler // IEEE Tras. on Infor. Theory. - 1975. - V. 21. - P. 32 - 40.
26. Gan, G. Data clustering: theory, algorithms, and applications / G. Gan, C. Ma, J. Wu // ASA-SIAM Ser. On Statistics and Appl. Probability. - SIAM, Philadelphia, ASA, Alexandria, VA, 2007. - 466 p.
27. Goil, S. Mafia: efficient and scalable subspace clustering for very large data sets / S. Goil, H. Nagesh, A. Choudhary // Tech. Rep. CPDC-TR-9906-010. - Center for Parallel and Distributed Computing, Department of Electrical & Computer Engineering, Northwestern University, June 1999.
28. Guha, S. CURE: an efficient clustering algorithm for large databases / S. Guha, R. Rastogi, K. Shim // Proc. ACM SIGMOD Intern. Conf. on Management of Data. - 1998. - P. 73 - 84.
29. Hartigan, J. A. Clustering algorithms / J. A. Hartigan. - N.Y.: John Wiley & Sons, 1975.
30. Hinneburg, A. An efficient approach to clustering in large multimedia databases with noise / A. Hinneburg, D. A. Keim // Proc 4th Intern. Conf. on Knowledge Discovery and Data Mining. - N.Y., Aug. 1998. - P. 58 - 65.
31. Ilango, M. A survey of grid based clustering algorithms / M. Ilango, V. Mohan // Intern. J. of Eng. Sci. and Technology. - 2010. - Vol. 2(8). - P. 3441 - 3446.
32. Jain, A.K. Data clustering: 50 years beyond K-means / A.K. Jain // Patt. Recogn. Lett. - 2010. - Vol. 31. - Is. 8. - P. 651 - 666.
33. Jain, A. K. Statistical pattern recognition: a review / A. K. Jain, R. P. W. Duin, J. Mao // IEEE Trans. on Patt. Anal. and Machine Intell. - 2000. Vol. 22. - № 1. - P. 4 - 37.
34. Jain, A. K. Data clustering: a review / A. K. Jain, M. N. Murty // ACM Computing Surveys. - 1999. - Vol. 31. - № 3. - P. 264 - 323.
35. Kaufman, L. Finding groups in data: an Introduction to cluster analysis / L. Kaufman, P. Rousseeuw. - N.Y.: Wiley & Sons, 1990. - 368 p.
36. Kriegel, H.-P. Incremental OPTICS: efficient computation of updates in a hierarchical cluster ordering / H.-P. Kriegel, P. Kröger, I. Gotlibovich // Proc. 5th Intern. Conf. on Data Warehousing and Knowledge Discovery. - Prague, Czech Republic, 2003. - P. 224 - 233.
37. Kroger, P. Density-connected subspace clustering for high-dimensional data / P. Kroger, H.-P. Kriegel, K. Kailing // Proc. 4th SIAM Intern. Conf. on Data Mining. - Lake Buena Vista, FL, 2004. - P. 246 - 257.
38. Li, X. A note on the convergence of the mean shift / X. Li, Z. Hu, F. Wu // Patt. Recogn. - 2007. - V. 40. - P. 1756 - 1762.
39. Ma, E. W. M. A new shifting grid clustering algorithm / E. W. M. Ma, T. W. S. Chow // Patt. Recogn. - 2004. - Vol. 37. - № 3. - P. 503 - 514.
40. Mercer, D. P. Clustering large datasets / D. P. Mercer // Linacre College, 2003. - Режим доступа: http://ldc.usb.ve/~mcuriel/Cursos/WC/Transfer.pdf.
41. Nagesh, H. S. Adaptive grids for clustering massive data sets / H. S. Nagesh, S. Goil, A. Choudhary // Proc. 1st SIAM Intern. Conf. on Data Mining. - Chicago, IL, 2001. - Vol. 417. - P. 1 - 17.
42. Nagesh, H. S. A scalable parallel subspace clustering algorithm for massive data sets / H. S. Nagesh, S. Goil, A. N. Choudhary // Proc. Intern. Conf. on Parallel Processing. - 2000. - P. 477 - 484.
43. Narendra, P. M. A non-parametric clustering scheme for LANDSAT / P.M. Narendra, M. Goldberg // Patt. Recogn. - 1977. - P. 207.
44. Ng, R. T. Efficient and effective clustering methods for spatial data mining / R. T. Ng, J. Han // Proc. 20th Conf. on Very Large Data Bases. - 1994. - P. 144 - 155.
45. Pal, P. A symmetry based clustering technique for multi-spectral satellite imagery / P. Pal, B. Chanda // Proc. Third Indian Conf. on Computer Vision, Graphics and Image Processing. - 2002. - Режим доступа: http://www.ee.iitb.ac.in/~icvgip/PAPERS/252.pdf.
46. Pestunov, I. A. Algoriythms for processing polizonal video information for detection and classification of forests infested with insects / I. A. Pestunov // Patt. Recogn. And Image Anal. - 2001. - V. 11. - № 2. - P. 368 - 371.
47. Pilevar, A. H. GCHL: a grid-clustering algorithm for high-dimensional very large spatial data bases / A. H. Pilevar, M. Sukumar // Patt. Recogn. Lett. - 2005. - Vol. 26. - № 7. - P. 999 - 1010.
48. Rekik, A. Review of satellite image segmentation for an optimal fusion system based on the edge and region approaches / A. Rekik, M. Zribi, A. Hamida, M. Benjellounl // IJCSNS Intern. J. of Comp. Sci. and Network 242 Security. - 2007. - Vol. 7. - № 10. - P. 242 - 250.
49. Sarmah, S. A grid-density based technique for finding clusters in satellite image / S. Sarmah, D. K. Bhattacharyya // Patt. Recogn. Lett. - 2012. - V. 33. - P. 589 - 604.
50. Schikuta, E. Grid-Clustering: a hierarchical clustering method for very large data sets / E. Schikuta // Proc. 13th Intern. Conf. on Patt. Recogn. - 1993. - Vol. 2. - P. 101 - 105.
51. Selim, S. K-means-type algorithms: a generalized convergence theorem and characterization of local optimality / S. Selim, M. Ismail // IEEE Trans. on Patt. Anal. and Machine Intelligence. - 1984. - Vol. 6. - Is. 1. - P. 81 - 87.
52. Sheikholeslami, G. WaveCluster: a multi-resolution clustering approach for very large spatial databases / G. Sheikholeslami, S. Chatterjee, A. Zhang // Proc. 24th Conf. on Very Large Data Bases. - N.Y., 1998. - P. 428 - 439.
53. Shi Y. A shrinking-based approach for multi-dimensional data analysis / Shi Y., Y. Song, A. Zhang // Proc. 29th Intern. Conf. on Very Large Data Bases. - Berlin, Germany, 2003. - P. 440 - 451.
54. Tantrum, J. Model-based clustering of large datasets through fractionization and refractionization / J. Tantrum, A. Murua, W. Stuetzle // Proc. ACM SIG KDD Conf. - Edmonton, Alberta, Canada, 2002. - P. 183 - 190.
55. Terrell, G. R. Variable kernel density estimation / G. R. Terrell, D. W. Scott // The Annals of Statistics. - 1992. - V. 20. - № 3. - P. 1236 - 1265.
56. Titterington, D. Statistical analysis of finite mixture distributions / D. Titterington, A. Smith, U. Makov - Chichester, U.K.: John Wiley & Sons, 1985.
57. Wang, W. STING: a statistical information grid approach to spatial data mining / W. Wang, J. Yang, M. Muntz // Proc. 1997 Intern. Conf. on Very Large Data Bases. - 1997. - P. 186 - 195.
58. Xu, R. Clustering / R. Xu, D. C. II Wunch. - N.Y.: John Wiley & Sons, 2009. - 358 p.
59. Xu, R. Survey on clustering algorithms / R. Xu, D. C. II. Wunsch // IEEE Trans. On Neural Networks. -2005. - Vol. 16. - № 3. - P. 645 - 678.
60. Xu, X. A fast parallel clustering algorithm for large spatial databases / X. Xu, M. Ester, H.-P. Kriegel // Proc. 1999 Intern. Conf. on Knowledge Discovery and Data Mining. - 1999. - Vol. 3, is. 3. - P. 263 - 290.
61. A distribution-based clustering algorithm for mining in large spatial databases / X. Xu, M. Ester, H.-P. Kriegel, J. Sander // Proc. IEEE Intern. Conf. on Data Eng. - 1998. - P. 324 - 331.
62. Yanchang, Z. GDILC: A grid-based density iso-line clustering algorithm / Z. Yanchang, S. Junde // Proc. Intern. Conf. Info-tech and Info-net. - Beijing, China, 2001. - Vol. 3. - P. 140 - 145.
63. Zhang, T. BIRCH: An efficient data clustering method for very large databases / T. Zhang, R. Ramakhrisnan, M. Livny // Proc. ACM-SIGMOD Intern. Conf. on Management of Data. - 1996. - P. 103 - 114.
64. Zhao, Y. Enhancing grid-density based clustering for high dimensional data / Y. Zhao, J. Cao, C. Zhang, S. Zhang // J. of Systems and Software. - 2011. - Vol. 84, is. 9. - P. 1524 - 1539.
65. Zhao, Y. AGRID: An efficient algorithm for clustering large high-dimensional datasets / Y. Zhao, J. Song // Proc. 7th Pacific-Asia Conf. on Knowledge Discovery and Data Mining. - Seoul, Korea, 2003. - P. 271 - 282.
66. Прикладная статистика: классификация и снижение размерности / С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешалкин - М: Финансы и статистика, 1989. - 607 с.
67. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. - М.: Техносфера, 2006. - С. 812.
68. Загоруйко, Н. Г. Прикладные методы анализа данных и знаний / Н. Г. Загоруйко. - Новосибирск: Изд-во Ин-та математики, 1999. - 270 с.
69. Дидэ, Э. Методы анализа данных: Подход, основанный на методе динамических сгущений: Пер. с фр. / Кол. авт. под рук. Э. Дидэ. - М.: Финансы и статистика, 1985. - 357 с.
70. Дюран, Н. Кластерный анализ / Н. Дюран, П. Оделл. - М.: Статистика, 1977. - 128 с.
71. Епанечников, В. А. Непараметрическая оценка многомерной плотности вероятности / В. А. Епанечников // Теория вероятностей и ее применение. - 1969. - Т. 14, № 1. - С. 156 - 160.
72. Ёлкин, Е. А. О возможности применения методов распознавания в палеонтологии / Е. А. Ёлкин, В. Н. Ёлкина, Н. Г. Загоруйко // Геология и геофизика. - 1967. - № 9. - С. 75 - 78.
73. Миркин, Б. Г. Группировки в социально-экономических исследованиях: Методы построения и анализа / Б. Г. Миркин. - М.: Финансы и статистика, 1985. - 223 с.
74. Пестунов, И. А. Непараметрический алгоритм кластеризации данных дистанционного зондирования на основе grid-подхода / И. А. Пестунов, Ю. Н. Синявский // Автометрия. - 2006. - Т. 42. - № 2. - С. 90 - 99.
75. Пестунов, И. А. Сегментация многоспектральных изображений на основе ансамбля непараметрических алгоритмов кластеризации / И. А. Пестунов, В. Б. Бериков, Ю. Н. Синявский // Вестн. СибГАУ. - 2010. - T. 31. - № 5. - С. 45 - 56.
76. Ансамблевый алгоритм кластеризации больших массивов данных / И. А. Пестунов, В. Б. Бериков, Е. А. Куликова, С. А. Рылов // Автометрия. - 2011. - Т. 47. - № 3. - С. 49 - 58.
77. Сидорова, В. С. Анализ многоспектральных данных дистанционного зондирования покрова Земли с помощью гистограммного иерархического кластерного алгоритма / В. С. Сидорова // Тр. Междунар. конгр. «ГЕО-СИБИРЬ-2011». - 2011. - Т. 4. - С. 116 - 122.
78. Ту, Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес. - М.: Мир, 1978. - 411 с.
79. Фукунага, К. Введение в статистическую теорию распознавания образов / К. Фукунага. - М.: Наука, 1979. - 368 с.
80. Системы искусственного интеллекта. Практический курс: учебное пособие / В. А. Чулюков, И. Ф. Астахова, А. С. Потапов [и др.]. - М.: Бином, 2008. - 292 с.
Рецензия
Для цитирования:
Пестунов И.А., Синявский Ю.Н. АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ. Вестник Кемеровского государственного университета. 2012;(4-2):110-125.
For citation:
Pestunov I.A., Sinyavskiy Yu.N. CLUSTERING ALGORITHMS IN SATELLITE IMAGES SEGMENTATION TASKS. The Bulletin of Kemerovo State University. 2012;(4-2):110-125. (In Russ.)
Просмотров:
190
Послать статью по эл. почте 