A robust approximate algorithm for large-scale  clustering of visual features

LI Darui; YANG Linjun; HUA Xiansheng; ZHANG Hongjiang

doi:10.3969/j.issn.0253-2778.2014.10.008

JUSTC > 2014 > 44(10): 844-852. > DOI: 10.3969/j.issn.0253-2778.2014.10.008 CSTR: 32290.14.j.issn.0253-2778.2014.10.008

PDF (1618 KB)

Open Access JUSTC Original Paper

A robust approximate algorithm for large-scale clustering of visual features

1.
MOE-Microsoft Key Lab, USTC, Hefei 230027, China
2.
Microsoft Bing, Bellevue 98004, USA
3.
Microsoft Research, Redmond 98052, USA
4.
Kingsoft,Beijing 100085, China

Cite this: JUSTC, 2014, 44(10): 844-852

https://doi.org/10.3969/j.issn.0253-2778.2014.10.008

CSTR: 32290.14.j.issn.0253-2778.2014.10.008

More Information

Received Date: September 12, 2013
Revised Date: May 15, 2014
Accepted Date: May 15, 2014
Published Date: October 29, 2014

Full text PDF

Abstract

Abstract

The large-scale clustering problem of visual features is crucial for image recognition and retrieval. The state-of-the-art algorithm, the approximate k-means, approximately guarantees the clustering performance by applying the high-precision approximate search. An improved algorithm was proposed, which requires no extra memory cost and nearly no extra time consumption. The robust approximate algorithm can better guarantee its convergence and clustering performance by utilizing more information in the iteration to update the partition, so that clustering loss is non-increasing and reduced rapidly. Theoretical proofs guarantee that the algorithm converges to the converged solution of the Lloyd algorithm, regard less of the precision values of approximate search. The experiment results show that the algorithm has about 10 times the speed of the approximate k-means algorithm. Besides, the clustering performance is also directly verified by comparing the images in the clustering results of global features.

Abstract

The large-scale clustering problem of visual features is crucial for image recognition and retrieval. The state-of-the-art algorithm, the approximate k-means, approximately guarantees the clustering performance by applying the high-precision approximate search. An improved algorithm was proposed, which requires no extra memory cost and nearly no extra time consumption. The robust approximate algorithm can better guarantee its convergence and clustering performance by utilizing more information in the iteration to update the partition, so that clustering loss is non-increasing and reduced rapidly. Theoretical proofs guarantee that the algorithm converges to the converged solution of the Lloyd algorithm, regard less of the precision values of approximate search. The experiment results show that the algorithm has about 10 times the speed of the approximate k-means algorithm. Besides, the clustering performance is also directly verified by comparing the images in the clustering results of global features.

FullText(HTML)

References (14)

References

[1]	Nister D, Stewenius H. Scalable recognition with a vocabulary tree[C]// 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE Press, 2006, 2: 2 161-2 168.
[2]	Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]// IEEE Conference on Computer Vision and Pattern Recognition. Minneapolis, USA: IEEE Press, 2007: 1-8.
[3]	Tuytelaars T, Lampert C H, Blaschko M B, et al. Unsupervised object discovery: A comparison[J]. International Journal of Computer Vision, 2010, 88(2): 284-302.
[4]	Philbin J, Zisserman A. Object mining using a matching graph on very large image collections[C]//Proceedings of the Inidan Conference on Computer Vision, Graphics & Image Processing. Bhubaneswar, India: IEEE Press, 2008: 738-745.
[5]	Li X W, Wu C C, Zach C, et al. Modeling and recognition of landmark image collections using iconic scene graphs[C]// Proceedings of 10th European Conference on Computer Vision. Marseille, France: Springer, 2008: 427-440.
[6]	Torralba A, Fergus R, Freeman W T. 80 million tiny images: A large data set for nonparametric object and scene recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(11): 1 958-1 970.
[7]	Lloyd S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982,28(2):129-136.
[8]	Selim S Z, Ismail M A. K-means-type algorithms: A generalized convergence theorem and characterization of local optimality[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(1): 81-87.
[9]	Jain A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010,31(8):651-666.
[10]	Judd D, McKinley P K, Jain A K. Large-scale parallel data clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998,20(8): 871-876.
[11]	Kollios G, Gunopulos D, Koudas N, et al. Efficient biased sampling for approximate clustering and outlier detection in large data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(5): 1 170-1 187.
[12]	Silpa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching[C]// IEEE Conference on Computer Vision and Pattern Recognition. Anchorage,USA: IEEE Press, 2008: 1-8.
[13]	Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration[C]// Proceedings of the 4th International Conference on Computer Vision Theory and Applications. Lisboa, Portugal: IEEE Press, 2009: 331-340.
[14]	Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]// Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Portland, USA: ACM Press, 2007: 1 027-1 035.

Cited By

Track Citations

Get Citation

{{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF

XML

References

[1]	Nister D, Stewenius H. Scalable recognition with a vocabulary tree[C]// 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE Press, 2006, 2: 2 161-2 168.
[2]	Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]// IEEE Conference on Computer Vision and Pattern Recognition. Minneapolis, USA: IEEE Press, 2007: 1-8.
[3]	Tuytelaars T, Lampert C H, Blaschko M B, et al. Unsupervised object discovery: A comparison[J]. International Journal of Computer Vision, 2010, 88(2): 284-302.
[4]	Philbin J, Zisserman A. Object mining using a matching graph on very large image collections[C]//Proceedings of the Inidan Conference on Computer Vision, Graphics & Image Processing. Bhubaneswar, India: IEEE Press, 2008: 738-745.
[5]	Li X W, Wu C C, Zach C, et al. Modeling and recognition of landmark image collections using iconic scene graphs[C]// Proceedings of 10th European Conference on Computer Vision. Marseille, France: Springer, 2008: 427-440.
[6]	Torralba A, Fergus R, Freeman W T. 80 million tiny images: A large data set for nonparametric object and scene recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(11): 1 958-1 970.
[7]	Lloyd S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982,28(2):129-136.
[8]	Selim S Z, Ismail M A. K-means-type algorithms: A generalized convergence theorem and characterization of local optimality[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(1): 81-87.
[9]	Jain A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010,31(8):651-666.
[10]	Judd D, McKinley P K, Jain A K. Large-scale parallel data clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998,20(8): 871-876.
[11]	Kollios G, Gunopulos D, Koudas N, et al. Efficient biased sampling for approximate clustering and outlier detection in large data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(5): 1 170-1 187.
[12]	Silpa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching[C]// IEEE Conference on Computer Vision and Pattern Recognition. Anchorage,USA: IEEE Press, 2008: 1-8.
[13]	Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration[C]// Proceedings of the 4th International Conference on Computer Vision Theory and Applications. Lisboa, Portugal: IEEE Press, 2009: 331-340.
[14]	Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]// Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Portland, USA: ACM Press, 2007: 1 027-1 035.

[1]	Jun Li, Xi Chen, Liang Wan. Is digital transformation boosting green innovation in logistics enterprises? Evidence from listed firms in China’s logistics industry[J]. JUSTC, 2025, 55(1): 0102. DOI: 10.52396/JUSTC-2023-0146
[2]	Quan Du, Zhixin Chen, Jie Wu, Xiang Ji. Live-streaming selling strategies for competitive firms[J]. JUSTC, 2024, 54(5): 0503. DOI: 10.52396/JUSTC-2022-0171
[3]	Xiaolong Guo, Ning Zhang, Jingjing Yang, Chenchen Yang. Entry or not? Manufacturers’ product sharing strategy when facing competition[J]. JUSTC, 2023, 53(2): 5-1-5-15. DOI: 10.52396/JUSTC-2022-0110
[4]	Yaliang Chen, Manman Wang. Delivery mode selection of home furnishing e-retailer based on a combination of logistics delivery and installation service[J]. JUSTC, 2023, 53(1): 5-1-5-13. DOI: 10.52396/JUSTC-2021-0282
[5]	Xiaoxing Liang, Zhixiang Zhou. Cooperation and competition among urban agglomerations in environmental efficiency measurement: A cross-efficiency approach[J]. JUSTC, 2022, 52(4): 3-1-3-11. DOI: 10.52396/JUSTC-2022-0028
[6]	CUI Huiming, JI Lei. The optimal decisions of remanufactured products and profit allocation under competitions of service and price[J]. JUSTC, 2020, 50(6): 738-743. DOI: 10.3969/j.issn.0253-2778.2020.06.004
[7]	LI Meixuan, SUN Yue, HUANG He, XIN Yu, BU Xiaofei. Completely-competitive-equilibrium-based crowdsensing pricing mechanism[J]. JUSTC, 2019, 49(7): 595-602. DOI: 10.3969/j.issn.0253-2778.2019.07.010
[8]	YUAN Wei, Fan Jin, ZHAO Dingtao, ZHANG Minxian. Empirical study on the impact of third-party logistics service quality on customer loyalty[J]. JUSTC, 2017, 47(6): 508-513. DOI: 10.3969/j.issn.0253-2778.2017.06.009
[9]	LI Du, HE Ping. Service quality standard and pricing decision for wedding-car leasing platforms[J]. JUSTC, 2016, 46(12): 1022. DOI: 10.3969/j.issn.0253-2778.2016.12.009
[10]	CHEN Ping-ping, ZHONG Xiao-feng, WANG Jing. Soft real-time service and green communications[J]. JUSTC, 2009, 39(10): 1016.

TrendMD

Volume 44 Issue 10 PP. 844-852

Cover

Keywords

Article Metrics

Article views (79) PDF downloads (175)

A robust approximate algorithm for large-scale clustering of visual features

Abstract

Abstract

References

Related Articles

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

A robust approximate algorithm for large-scale clustering of visual features

Share

Tools

Abstract

Abstract

References

Related Articles

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

Export File

Citation

Format

Content