隨著多媒體與網際網路的快速發展，每天都在產生大量的數位影像。因此，如何讓使用者在龐大的資料庫中，有效且準確的搜尋出自己想要的影像，就顯得相當的重要。目前基於內容的影像檢索（CBIR）已經成為影像檢索技術的研究主流。

本論文採用具有仿射不變性的ASIFT 算法, 並且建立一個ASIFT 特徵點資料庫。我們提出對特徵點資料庫預先分群，來降低影像檢索的特徵點搜尋範圍。另外，我們提出基於分散式運算架構Spark 的影像檢索，Spark 提供一個可以駐留在記憶體內的彈性分散式數據集（RDD），我們利用RDD 建立一個可動態調整的工作資料集，根據每張影像的群集重要性來選擇群集。

實驗結果發現，影像檢索中使用Spark 相較於使用Hadoop，在檢索時間上可節省54%。此外，對影像特徵點預先分群，並動態調整工作資料集，在檢索時間上可節省將近46% 的時間。最後，利用F-Measure 指標找到良好的群集使用比例，則可以再取得更好的檢索效能。

With rapid development of multimedia and internet, massive amounts of digital images are being generated every day. It is important for users to effectively and accurately obtain their desired image from large image database. Nowadays,
Content-Based Image Retrieval (CBIR) has become the mainstream of image retrieval technology research.

This paper uses Affine SIFT (ASIFT) which is fully invariant to affine transformation and built database with ASIFT features. We propose a pre-clustered feature database which reduced feature’s search range on image retrieval. Moreover,we propose a distributed computing architecture which is Spark on image retrieval. Spark provides a resilient distributed dataset (RDD) which can be resident in memory. We used RDD to build a dynamically-adjust working dataset according to importance of each image in clusters.

The results show that Spark can be saved 54% of the retrieval time as compared with Hadoop. In addition, we applied pre-clustered feature database and dynamically-adjust the working dataset to Spark that can be saved 46% of the retrieval time. Finally, we used F-Measure to find the best cluster proportion and increase the performance of image retrieval.

[1] J. Wu, Z. Cui, V. S. Sheng, P. Zhao, D. Su, and S. Gong, “A comparative study of SIFT and its variants,” Measurement Science Review, vol. 13, no. 3,pp. 122–131, 2013.
[2] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J.Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets: A faulttolerant abstraction for in-memory cluster computing,” in Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation,pp. 2–2, 2012.
[3] M. Aly, M. Munich, and P. Perona, “Distributed KD-trees for retrieval from very large image collections,” in Proceedings of the British Machine Vision Conference (BMVC), 2011.
[4] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International journal of computer vision, vol. 60, no. 2, pp. 91–110, 2004.
[5] Y. Ke and R. Sukthankar, “PCA-SIFT: A more distinctive representation for local image descriptors,” in CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2004, vol. 2, pp. II–506, 2004.
[6] A. E. Abdel-Hakim and A. A. Farag, “CSIFT: A SIFT descriptor with color invariant characteristics,” in 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 1978–1983, 2006.
[7] H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool, “Speeded-up robust features SURF,” Computer vision and image understanding, vol. 110, no. 3, pp. 346–
359, 2008.
[8] J.-M. Morel and G. Yu, “ASIFT: A new framework for fully affine invariant image comparison,” SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 438–469, 2009.
[9] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE Transactions on Pattern Analysis and Machine Intelligence,vol. 33, no. 1, pp. 117–128, 2011.
[10] M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration.,” VISAPP (1), vol. 2, 2009.
[11] M. Muja and D. G. Lowe, “Scalable nearest neighbor algorithms for high dimensional data,” IEEE Transactions on Pattern Analysis and Machine Intelligence,vol. 36, no. 11, pp. 2227–2240, 2014.
[12] A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high dimensions via hashing,” in Very Large Data Bases,VLDB, vol. 99, pp. 518–529, 1999.
[13] “Apache hadoop,” in http://hadoop.apache.org/.
[14] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,” in ACM SIGOPS operating systems review, vol. 37, pp. 29–43, 2003.
[15] A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoff, and R. Murthy, “Hive: a warehousing solution over a map-reduce framework,” Proceedings of the VLDB Endowment, vol. 2, no. 2, pp. 1626–1629, 2009.
[16] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on large clusters,” Communications of the ACM, vol. 51, no. 1, pp. 107–113, 2008.
[17] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The hadoop distributed file system,” in 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST), pp. 1–10, 2010.
[18] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark:cluster computing with working sets,” in Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, pp. 10–10, 2010.
[19] “Apache spark-lightning-fast cluster computing,” in https://spark.apache.org/.
[20] M. Aly, M. Munich, and P. Perona, “Indexing in large scale image collections:Scaling properties and benchmark,” in 2011 IEEE Workshop on Applications of Computer Vision (WACV), pp. 418–425, 2011.
[21] J. Sivic and A. Zisserman, “Video google: A text retrieval approach to object matching in videos,” in Proceedings. Ninth IEEE International Conference on Computer Vision, 2003, pp. 1470–1477, 2003.
[22] H. Jegou, M. Douze, and C. Schmid, “Improving bag-of-features for large scale image search,” International Journal of Computer Vision, vol. 87, no. 3, pp. 316–336, 2010.
[23] J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACM Transactions on Mathematical Software (TOMS), vol. 3, no. 3, pp. 209–226, 1977.
[24] C. Silpa-Anan and R. Hartley, “Optimised KD-trees for fast image descriptor matching,” in IEEE Conference on Computer Vision and Pattern Recognition 2008. CVPR 2008., pp. 1–8, 2008.
[25] A. Andoni and P. Indyk, “Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,” in IEEE Symposium on Foundations of Computer Science 47th Annual, pp. 459–468, 2006.
[26] K. Terasawa and Y. Tanaka, “Spherical lsh for approximate nearest neighbor search on unit hypersphere,” in Algorithms and Data Structures, pp. 27–38, 2007.
[27] J. Zobel and A. Moffat, “Inverted files for text search engines,” ACM computing surveys (CSUR), vol. 38, no. 2, p. 6, 2006.
[28] B. R.-N. R Baeza-Yates, “Modern information retrieval,” in ACM press New York, vol. 463, 1999.
[29] A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig, “Syntactic clustering of the web,” Computer Networks and ISDN Systems, vol. 29, no. 8, pp. 1157–1166, 1997.
[30] A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher, “Min-wise independent permutations,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 327–336, 1998.
[31] A. Z. Broder, “On the resemblance and containment of documents,” in Compression and Complexity of Sequences 1997. Proceedings, pp. 21–29, 1997.
[32] O. Chum, J. Philbin, M. Isard, and A. Zisserman, “Scalable near identical image and shot detection,” in Proceedings of the 6th ACM international conference on Image and video retrieval, pp. 549–556, 2007.
[33] G. H. Ball and D. J. Hall, “Isodata, a novel method of data analysis and pattern classification,” tech. rep., 1965.
[34] D. Nister and H. Stewenius, “Scalable recognition with a vocabulary tree,” in 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 2161–2168, 2006.
[35] Y. Li and S. M. Chung, “Parallel bisecting k-means with prediction clustering algorithm,” The Journal of Supercomputing, vol. 39, no. 1, pp. 19–37, 2007.
[36] D. Pelleg and A. W. Moore, “X-means: Extending k-means with efficient estimation of the number of clusters.,” in ICML, pp. 727–734, 2000.
[37] M. Muhr and M. Granitzer, “Automatic cluster number selection using a split
and merge k-means approach,” in 20th International Workshop on Database and Expert Systems Application 2009. DEXA’09, pp. 363–367, 2009.
[38] F. Chierichetti, A. Panconesi, P. Raghavan, M. Sozio, A. Tiberi, and E. Upfal,“Finding near neighbors through cluster pruning,” in Proceedings of the
twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 103–112, ACM, 2007.
[39] D. Moise, D. Shestakov, G. Gudmundsson, and L. Amsaleg, “Indexing and searching 100m images with map-reduce,” in Proceedings of the 3rd ACM conference on International conference on multimedia retrieval, pp. 17–24,2013.
[40] D. Shestakov, D. Moise, G. Gudmundsson, and L. Amsaleg,“Scalable highdimensional indexing with hadoop,” in 2013 11th International Workshop on Content-Based Multimedia Indexing (CBMI), pp. 207–212, 2013.
[41] “The TUMindoor Dataset,” in http://www.navvis.lmt.ei.tum.de/.