臺灣博碩士論文加值系統

本論文提出一個在點對點網路資料庫進行影像檢索(P2P-CBIR)的系統。系統中包含一個自動化前級處理單元，並提供檢索範圍可調與漸進檢索的功能。在前級處理方面，以多階層的灰階型態運算來辨別出前景物件的區域。本法運算規律性高，非常適合應用在大型影像資料庫處理影像前景切割。在檢索方法上，我們採用可結合多種特徵之多詢例檢索法，運用在點對點網路上可以在維持原有精確度的情況下，有效的降低網路流量。本論文所提出的範圍與精確度可調的P2P-CBIR方法可以有效改進檢索效能(回取率/檢索範圍)，主要是同時考量:(1) 傳送檢索訊息策略降低檢索範圍與; (2) 回傳相關資料時利用多層點對點過率有效提升準確度。實驗結果顯示本論文所提的方法，比之前所提之煙火式(Firework Query Model) 檢索及廣先搜尋 (Breadth-First Search)方法之檢索效能都還要好。我們也就系統觀點提出最佳化的程序:當線上使用者人數固定時，可以提供設定參數使得檢索精確度最高。實驗結果顯示最佳化程序可以提高回取率達1.5至2倍，在相同回取率下，可降低處理時間約50%。我們也採取系統參數更新的程序，可有效提昇回取率25%。

A peer-to-peer content-based image retrieval system (P2P-CBIR) that utilizes an intelligent preprocessing to identify the foregrounds (FGs) and provides scalable retrieval function has been proposed. In the FG identification unit, the gray-level Morphological open/close by reconstruction (MOR/MCR) operations are utilized in a multi-scale approach to construct a background mesh to identify the image foregrounds (FGs). With the highly regular MOR/MCR process, the proposed FGID method is capable of dealing with FG segmentations for volume images. The proposed peer CBIR search engine that utilized multi-stance query with multi-feature types helps to effectively reduce network traffic while maintaining high retrieval accuracy. The scalable retrieval function can adaptively control the query scope and progressively refine the query results. It improves the query efficiency (recall-rate/query-scope) by effectively combining the: (1) forwarding query message (forward phase) to reduce the query scope and; (2) transmitting retrieval results (backward phase) that activated peers keep filtering high similarity images on the link-path toward the query peer. Experiments show that the query efficiency of the scalable retrieval approach is better than previous methods, i.e., firework query model and breadth-first search (BFS). We also proposed to optimally configure the P2P-CBIR system and perform regular update procedures such that, under a certain number of online users, it would yield the highest recall rate. Simulations demonstrate that, with the optimal configuration, recall rates can be improved to 1.5 to 2.0 times larger while the retrieval processing time is reduced to 50% of the original, under the same number of on-line users. The update procedure can further improve the recall rate up to 25%.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
2 Preprocessing and retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 8
2.1 MPEG7 and CBIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Image features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Shape Descriptors . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Color Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Similarity measure between image databases . . . . . . . . . . . . 14
2.4 Retrieval Method - NCCA . . . . . . . . . . . . . . . . . . . . . . . 15
3 Image Segmentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Multi-scale Mathematical Morphology . . . . . . . . . . . . . . . . 18
3.1.1 Multi-scale Opening and Closing . . . . . . . . . . . . . . . 19
3.2 Morphological Multiscale Opening and Closing by Reconstruction 20
3.3 Image Background Identification . . . . . . . . . . . . . . . . . . . 21
3.3.1 Foreground Object segmentation . . . . . . . . . . . . . . . 22
3.3.2 Segmentation Using the Multi-scale Morphology . . . . . . 24
3.3.3 Refinement of the foreground object with 2D mesh and
JSEG algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.4 The Result of Image Segmentation . . . . . . . . . . . . . . 34
4 The P2P-CBIR System. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1 Peer clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Peer architecture & operations . . . . . . . . . . . . . . . . . . . . 39
4.3 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Scalable retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Retrieval operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Time analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3 Optimal configuration . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4 Update strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.5 Bandwidth loading . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6 Simulation study. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.1 Previous methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.2 Performance evaluations . . . . . . . . . . . . . . . . . . . . . . . . 57
7 Conclusions & Future Researches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

[1] C. T. Zhan, et al., “Fourier descriptors for plane closed curves,”IEEE Trans. Computer, vol. 21, pp. 269-281, 1972.
[2] C. Xu and J. L. Prince, “Snakes, shapes, and gradient vector flow,”IEEE Trans. Image Processing, vol. 7, no. 3, pp. 359-369, March 1998.
[3] F. Mokhtarian, et al., “A theory of multi-scale, curvature-based shape representation for planar curves,” IEEE Trans. PAMI, vol. 14, no. 8, pp. 789-805, 1992.
[4] A. Khotanzad and Y. H. Hong, “Rotational invariant image recognition using features selected via a systematic method,” Pattern Recognition, vol. 23, no. 10, pp. 1089-1101, 1990.
[5] J. Ricard, et al., “Generalization of angular radial transform,”IEEE Conf. Image Processing, vol. 4, pp. 2211-2214, 2004.
[6] S. Mukhopadhyay, et al., “Multiscale morphological segmentation of gray-scale images,”IEEE Trans. Image Processing, vol. 12, no. 5, May 2003.
[7] J. Serra and L. Vincent, “An overview of morphological filtering,”IEEE Trans. Circuits. Sys. Signal Processing, vol. 11. no. 1, pp. 47-108, Jan. 1992.
[8] Y. Deng, and B. S. Manjunath, “Unsupervised segmentation of color-texture regions in images and video,” IEEE Trans. Pattern Anal. Machine Intell., August 2001.
[9] D. Comanicu and P. Meer, “Mean shift: a robust approach toward feature space analysis.” IEEE Trans. Pattern Anal. Machine Intell., vol. 24, pp. 603-619, May 2002.
[10] The Gnutella protocol specification v0.41,http://www9.limewire.com/developer/gnutella protocol 0.4.pdf/.
[11] Morpheus v5.4, ttp://morpheus.com Jan. 18, 2007.
[12] B. Liu, et al., “Supporting complex multi-dimensional queries in P2P Systems,”IEEE Conf. Distributed Comp. Sys., pp. 155-164, June 2005.
[13] I. King et al, “Distributed content-based visual information retrieval system on peer-to-peer networks,”ACM Transactions on Information Systems, vol. 22, no. 3,pp. 477-501, 2004.
[14] Shawn Fanning, Napster, ¡http://www.napster.com/¿, Feb. 9, 2007.
[15] S. Ratnasamy, et al., “Routing algorithm for DHTs: some open question,” In Proc. First International Peer-to-Peer Workshop, pp. 45-52, 2002.
[16] I. Clarke, et al., “Freenet: a distributed anonymous information storage and retrieval system,” In H. Federrath, editor, Designing Privacy Enhancing Tech., no. 2009 in LNCS, pp. 46-66, Berkeley, CA, USA, July 2000.
[17] M. Eisenhardt, et al., “Clustering-based source selection for efficient image retrieval in peer-to-peer networks,” IEEE Int. Symb. Multimedia, 2006.
[18] T. Inaba, et al., “Design and implementation of an efficient search mechanism based on the hybrid P2P model for ubiquitous computing systems,” Int. Symb. Applications Internet, pp. 45-53, 23-27 Jan. 2006.
[19] J. Yang, et al., “An efficient interest-group based search mechanism in unstructured peer-to-peer networks,” Int. Conf. Computer Networks and Mobile Computing, pp. 247-252, 20-23 Oct. 2003.
[20] X. Li and J. Wu, “A hybrid searching scheme in unstructured P2P networks,” Int. Conf. Parallel Processing, pp. 277-284, June 2005.
[21] D. Zeinalipour-Yazti, et al., “Information retrieval techniques for peer-to-peer networks,”IEEE CS and AIP, vol. 06, issue 4, pp. 20-26, 2004.
[22] Y. Zhu, et al., “Making search efficient on Gnutella-like P2P systems,” Int. Parallel Distributed Processing Symp., pp. 56a-56a, 2005.
[23] T. Lin, et al., “Search performance analysis and robust search algorithm in unstructured peer-to-peer networks,” IEEE/ACM Int. Symp. Cluster Comput. and the Grid, pp. 346-354, 2004.
[24] H. Zhang, et al., “A multi-agent approach for peer-to-peer-based information retrieval systems,” Int. Joint Conf. Autonomous Agents and Multiagent Systems, pp. 456-464, 2004.
[25] I. Lee and L. Guan, “A distributed content-based image retrieval system over the peer-to-peer network,”IEEE Conf. Upcoming Engineer, 2003.
[26] E. Ardizzone, et al.,“Enhanced P2P services providing multimedia content,”IEEE Int. Symb. Multimedia, 2006.
[27] L. Cieplinski, et al, “MPEG-7 visual part of eXperimentati-on model version 11.1,”ISO/IEC JTC1/SC29/WG11 MPEG01 / M7691, 2001.
[28] Overview of the MPEG-7 Standard (version 7), ISO/IEC JTC1/SC29/WG11
N4674, March 2002.
[29] B. S. Manjunath, P. Salembier, and T. Sikora, Introduction to MPEG-7: Multimedia Content Description Interface, New York: Wiley, 2002
[30] Z. Li and M. S. Drew, Fundamentals of Multimedia, New Jersey: Prentice Hall, 2004.
[31] P. Maragos and R. W. Schaffer, “Morphological filters-part I: their set theoretic analysis and relations to linear shift-invariant filters,”IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-35, Aug. 1987.
[32] J.-J. Chen, Chia-Jung Hu and Che-Kang Chang, “An image retrieval system that provides multi-instance query with multiple features,” in preparation for submission.
[33] C. H The and R. T.Chin, “Image analysis by the methods of moments,”IEEE
Trans.Pattern Anal. Machine Intell., vol. 10, no. 4, pp. 496-513, July 1988.
[34] J.-J. Chen et al, “Similarity retrieval in image databases by boosted common shape features among query images,” IEEE The 2nd Pacific-Rim Conference on Multimedia, PCM 2001, pp. 285-292, Oct. 2001.
[35] S. J. Jeong, et al., “An effective method for combining multiple features of images retrieval,” IEEE TENCON, pp. 982-985, 1999.
[36] J.-J. Chen et al, “A dynamically adapted retrieval algorithm for multi-instance image query with heterogeneous features,”to appear in IEEE Consumer Communications & Networking 2004.
[37] J.-J. Chen and C.-Y. Liu, “A universal query mechanism for similarity retrieval based on shape information in image databases,” IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 4, pp. 3676-3679, 2002.
[38] J. SerN4674, March 2002.ra, Image Analysis Using Mathematical Morphology,
London,U.K.: Academic, 1982.
[39] S. Mukhopadhyay and B. habatosh Chanda,“Multiscale Morphological Segmentation of Gray-Scale Images,” IEEE Trans. on Image Processing, vol. 12, no. 5, May 2003,
[40] P. Maragos, “Pattern spectrum and multiscale shape representation,”IEEE
Trans. Pattern Anal. Machine Intell., vol. 11, pp. 701V716, 1989.
[41] J. Serra and L. Vincent, “An overview of morphological filtering,”IEEE Trans. Circuits,Systems and Signal Proc., vol. 11, no. 1, pp. 47V107, 1992.
[42] Z. Li and M. S. Drew, Fundamentals of Multimedia,New Jersey: Prentice Hall, 2004.
[43] M. Abdel-Mottaleb, S. Krishnamachari,“Multimedia descriptions based on
MPEG-7: extraction and applications,”IEEE Transactions on Multimedia., vol.
6,issue 3, pp. 459V468, June. 2004.