6月28日在南京理工大学我们听取了何教授有关social information access的报告。何教授提出随着互联网的发展,产生了大量的用户生成内容(UGC),其可以分为两类,一类是显性的UGC包括社会化标签、评论、排序,一类是隐性的UGC包括用户查询式、点击浏览情况,这些信息就给我们提供了大量可供我们研究用户的数据,通过研究这些数据可以帮助用户更好的获取社会信息。接着何教授给我们报告了他的研究组4个相关项目,第一个是开发的一个协同检索系统,以2个人共同参与检索一个话题为基础,通过提供实时沟通以及检索结果的存储实现协同,何教授提出现在的协同检索主要集中在两个人的协同,而对于3个人及其以上的协同情况比较复杂,是以后需要进一步研究的方向。第二个是一个找专家的系统,通过收集文献信息,利用文献作者之间的关系,利用pagerank等算法找出各个领域的专家,用户可以在系统中设置自己需要查找的专家权威度的大小。第三个是一个结合图片标签和subject headings的检索系统,比较利用标签和subject headings进行检索的异同。第四个是分析比较图书馆的虚拟参考咨询和问答系统,如百度知道,soso问问等,对用户提问回答情况进行对比,发现其异同。
学术报告通知 题 目 : Information Access on the Social Web ( 社会化 Web 信息获取 ) 报告 人 :何大庆博士 Associate Professor Director, Information Retrieval,Integration and Synthesis Lab School of Information Sciences, Universityof Pittsburgh 时 间 : 2013 年 6 月 28 日(星期五)下午 3 : 00~5 : 00 地 点 :南京理工大学经管楼 105 会议室 报告提要 : SocialWeb not only provides user generated contents for people to use, but alsofundamentally changed information access in people’s mind and on the Web.Consumers of information can at the same time be the participants of informationproduction, organization, retrieval and utilization. It is under thisinnovative infrastructure that social information access thrives and becomesone of the most actively developed topic in both academia and industry. In thistalk, I will using four research projects conducted in my research lab as the examplesto illustrate some interesting recent developments on this topic. My goal is tointroduce social information access, to discuss some of its findings, and toelicit potential collaborations on this topic. 报告人简介 : Dr.Daqing He is an associate professor at the School of Information Sciences(iSchool), and associate professor at the Intelligent Systems Program, both ofwhich are at the University of Pittsburgh. He earned his PhD degree in ArtificialIntelligence from the University of Edinburgh, Scotland. Prior joining theUniversity of Pittsburgh in 2004, he served on the research faculties of theRobert Gordon University, Scotland and the University of Maryland at CollegePark, United States. His work centered on adaptive and interactive monolingual/multilingualinformation retrieval. Currently, Dr. He’s main research interests coverinformation retrieval (monolingual and multilingual), information access on thesocial web, adaptive Web systems and user modeling, interactive retrievalinterface design, and Web log mining and analysis. Dr. He is the PrincipalInvestigator (PI) and Co-PI for more than ten research projects, funded by theNational Science Foundation (NSF), United States Defense Advanced Research ProjectsAgency (DARPA), University of Pittsburgh, and other agencies. He has publishedmore than 100 articles in internationally-recognized journals and conferencesin these areas. Dr. He has served as a member on the program committees formore than 15 major international conferences in the area of informationretrieval and web technologies, and has been called upon to be a reviewer formany top-ranked international journals in the same areas. Dr. He is also thechair of the SIS council, the faculty governing body for the iSchool. 欢迎校内外各界人士参加! 南京理工大学经济管理学院 信息管理系 二零一三年六月十七日
From: http://www.ccf.org.cn/resources/1190201776262/fujian/信息检索学科05202011-05-20-09_44_22.doc 中国计算机学会《学科前沿讲习班》 The CCF A dvanced D isciplines L ectures 主题 信息检索 前沿 2011 年 7 月 29-31 日 北京 信息检索是计算机学科相关研究中的一大热点,也是各种互联网应用服务(例如搜索引擎)的关键技术。信息检索技术的发展,拉近了不同地域、阶层和职业的人们与信息之间的距离,在消除信息鸿沟和加速知识化进程过程中发挥着越来越重要的作用,正日益渗透到社会生活和国家发展的各个层面,成为衡量一个国家信息技术发展水平的重要标志。 本期 CCF 学科前沿讲习班《 信息检索前沿 》 与国际信息检索大会 (SIGIR 2011) 密切合作,邀请到了信息检索领域重量级的专家学者做主题报告。他们将对信息检索的热点问题、相关理论和方法进行深入浅出的介绍,并对如何开展本领域前沿技术研究等进行探讨。 使参加者在了解学科热点、提高学术水平的同时,增加信息检索的交流机会和实践体验。 特邀讲者 l Dr. Susan Dumais 微软雷德蒙研究院首席研究员,人机交互和信息检索方面的国际知名专家。美国计算机学会信息检索专委会前主席,国际信息检索大会( SIGIR ) 2006 的程序委员会主席,美国计算机学会院士,美国国家工程院院士,格拉德•撒尔顿奖( Gerard Salton Award , 信息检索领域最高奖项)得主。 l Dr. Ricardo Baeza-Yates 雅虎欧洲、中东、拉美研究院副总裁,信息检索和数据挖掘方面的国际知名专家。国际信息检索大会 2011 年的程序委员会主席,美国计算机学会院士,国际电子电气工程师学会院士,信息检索领域经典著作《现代信息检索》 (Modern Information Retrieval) 的作者。 l Dr. Stephen Robertson 微软剑桥研究院高级研究员,信息检索模型方面国际公认的先驱,著名的信息检索模型 Okapi BM25 的发明人。英国剑桥哥顿学院院士,格拉德•撒尔顿奖得主。 l 杨益铭 教授 ( Prof. Yiming Yang ) 美国卡耐基梅隆大学教授,文本分类领域国际公认的先驱,多篇经典论文已被引用千次以上。多次担任国际信息检索大会领域主席。 l 翟成祥 教授 ( Prof. Chengxiang Zhai ) 美国伊利诺伊大学香槟分校副教授 , 语言模型方面的国际知名专家。国际信息检索大会 2009 年的程序委员会主席,美国计算机学会杰出科学家。 学术主任 l 刘铁岩 博士 微软亚洲研究院研究主管。信息检索和排序学习领域的国际知名专家,曾获得国际信息检索大会最佳论文奖和国际图像通信和视觉表达期刊的最高引用论文奖。多次担任国际信息检索大会 (SIGIR) 和国际互联网大会 (WWW) 的领域主席,现任国际信息检索期刊 (IR Journal) 编委,美国计算机学会信息系统期刊 (TOIS) 副主编,国际电子电气工程师学会高级会员。 l 张敏 博士 清华大学计算机科学与技术系副教授 ,信息检索和数据挖掘领域的专家。曾多次担任亚洲信息检索大会的领域主席,国际信息检索大会 (SIGIR) 、国际互联网大会 (WWW) 、知识发现与数据挖据大会( KDD )、网络搜索与数据挖掘( WSDM )等会议的程序委员会成员。在国际文本检索会议中连续多年多次获得最佳结果。 计算机学会中文信息技术专业委员会委员、人工智能学会机器学习专业委员会委员、中文信息学会信息检索与内容安全专业委员会委员。 时间: 2011 年 7 月 29 - 31 日 上课地点: 北京市海淀区丹棱街 5 号,微软大厦 1 号楼多功能厅 (参见地图,新东方大厦西侧, 注 :参会者需要在 X 号楼 1 楼前台登记) 注册费: (含资料和 3 天的午餐) 1 、 7 月 20 日 前报名并缴费:会员 900 元,非会员 1200 元 2 、 7 月 28 日 前缴费:会员 1035 元,非会员 1380 元 3 、 7 月 29 日 缴费:会员 1200 元,非会员 1560 元 优惠办法: 1 、 同一单位一次有 5 人报名者,可免交 1 人的注册费(当天不办理此项业务,缴费‘额度见上标准) 2 、 2010 年参加过讲习班学员可在原缴费标准基础上降低 100 元。 3 、 2011 年参加 3 次讲习班的学员,第四次免费。 4 、 学员每推荐一名新学员,推荐者当期注册费优惠 100 元(以被推荐者参加讲习班为有效)。 食宿自理 缴费方式: 邮寄:北京 2704 信箱,邮编: 100190 收款人:中国计算机学会, 银行转账:开户行:北京银行北京大学支行;户名:中国计算机学会 帐号: 01090519 5001 201 097 020 28 请务必注明: ADL- 信息检索前沿 现场:报到时缴纳(需事先在报名表中承诺栏中填写名字) 报名方式: 即日起至 2011 年 7 月 20 日 , 报名者请填写附表并发送至: ccf-yx@ict.ac.cn , 按报名先后录取。学会秘书处将与邮寄联系确认。 联系人 :余遐 E-Mail: ccf-yx@ict.ac.cn 电话: 010-6256 2503-22/ 010-6260 0336 /139 1065 9011 传真: 010-6252 7485 地址:北京科学院南路 6 号计算所大楼 336 室 日程安排 2011 年 7 月 29 日 8:30-9:00 开班仪式 9:00-9:15 合影 9:15-12:15 学术专题讲座 1 网络挖掘 ( Web Mining or The Wisdom of the Crowds ) Ricardo Baeza-Yates , 雅虎欧洲、中东、拉美研究院副总裁 12:30-14:00 午餐 及 信息检索前沿技术演示 14:00-17:00 学术专题讲座 2 文本分类综述 ( Tutorial on Text Categorization ) 杨益铭, 美国卡耐基梅隆大学教授 2011 年 7 月 30 日 9:00-12:00 学术专题讲座 3 从概率的观点看信息检索( On taking a probabilistic view of information retrieval ) Stephen Robertson , 微软剑桥研究院高级研究员 12:30-14:00 午餐 14:00-17:00 学术专题讲座 4 面向信息检索的统计语言模型 ( Statistical Language Models for Information Retrieval ) 翟成祥 , 美国伊利诺伊大学香槟分校副教授 2011 年 7 月 31 日 9::00-12:00 学术专题讲座 5 时间动态信息检索 ( Temporal Dynamics and Information Retrieval ) Susan Dumais , 微软雷德蒙研究院首席研究员 12:30-14:00 午餐 14:00-16:00 专题讨论 16:00 结业式 附:学术专题讲座详细信息 学术讲座 1 : Web Mining or The Wisdom of the Crowds , Ricardo Baeza-Yates 摘要 : The Web continues to grow and evolve very fast, changing our daily lives. This activity represents the collaborative work of the millions of institutions and people that contribute content to the Web as well as the one billion people that use it. In this ocean of hyperlinked data there is explicit and implicit information and knowledge. Web Mining is the task of analyzing this data and extracting information and knowledge for many different purposes. The data comes in three main flavors: content (text, images, etc.), structure (hyperlinks) and usage (navigation, queries, etc.), implying different techniques such as text, graph or log mining. Each case reflects the wisdom of some group of people that can be used to make the Web better. For example, user generated tags in Web 2.0 sites. In this talk we walk through this process and give specific examples. 讲者简介 : Ricardo Baeza-Yates is VP of Yahoo! Research for Europe, Middle East and Latin America, leading the labs at Barcelona, Spain and Santiago, Chile, as well as supervising the newer lab in Haifa, Israel. Until 2005 he was the director of the Center for Web Research at the Department of Computer Science of the Engineering School of the University of Chile; and ICREA Professor at the Dept. of Technology of the Univ. Pompeu Fabra in Barcelona, Spain. He is co-author of the best-seller book Modern Information Retrieval, published in 1999 by Addison-Wesley with a second edition in 2010, as well as co-author of the 2nd edition of the Handbook of Algorithms and Data Structures, Addison-Wesley, 1991; and co-editor of Information Retrieval: Algorithms and Data Structures, Prentice-Hall, 1992, among more than 200 other publications. He has received the Organization of American States award for young researchers in exact sciences (1993) and with two Brazilian colleagues obtained the COMPAQ prize for the best CS Brazilian research article (1997). In 2003 he was the first computer scientist to be elected to the Chilean Academy of Sciences. During 2007 he was awarded the Graham Medal for innovation in computing, given by the University of Waterloo to distinguished ex-alumni. In 2009 he was awarded the Latin American distinction for contributions to CS in the region and became an ACM Fellow. Finally, in 2011 he also became IEEE Fellow. 学术讲座 2: Tutorial on Text Categorization , Yiming Yang 摘要 : Text categorization (a.k.a. text classification) is the task of assigning predefined categories to free-text documents. It can provide conceptual views of document collections and has broad applications in the real world. For example, news stories are typically organized by subject categories (topics) or geographical regions; academic papers are often indexed by technical domains and sub-domains in a concept hierarchy; search queries can be classified based on both content words and empirical associations from queries to different types of search engines and data sources in the Internet environments. This lecture will be a tutorial, introducing fundamental concepts and techniques in supervised learning for text categorization, with concrete examples such as linear classifiers (e.g., Nave Bayes or NB) vs. non-linear classifiers (e.g., k-nearest neighbor or kNN), generative models (e.g., NB) vs. discriminative models (e.g. logistic regression or LR), eager learning (NB and LR) vs. lazy learning (kNN), and large-margin classification (e.g., Support Vector Machines and regularized LR). We will also discuss open research topics such as multi-label classification with learning-to-rank algorithms, and large-scale classification with distributed computing (if time permits). 讲者简介 : Yiming Yang is a professor in the Language Technologies Institute and the Machine Learning Department in the School of Computer Science at Carnegie Mellon University. Her research has centered on statistical learning methods and their applications to a broad range of challenging problems, including large-scale text categorization, utility (relevance and novelty) based retrieval and adaptive filtering, personalization and active learning for recommendation systems, social network analysis for personalized email prioritization, etc. She received her Ph.D. in Computer Science from Kyoto University (Japan), and has been a faculty member at Carnegie Mellon University since 1996. 学术讲座 3 : On taking a probabilistic view of information retrieval , Stephen Robertson 摘要 : Why is it so useful to think of information retrieval as a probabilistic process? This talk will start from basics (ideas about the evaluation of IR systems, the probabilistic model of Maron and Kuhns, the Probability Ranking Principle) and go on to develop the probabilistic relevance model (the binary independence model of Robertson and Sprck Jones, BM25, and its successors). The emphasis will be on the reasons for choosing certain conceptualizations, the assumptions involved, the strengths and limitations of the resulting models. It will not attempt to cover in detail all probabilistic models that have been used in IR, but it will provide pointers to some other models, such as the language modeling approach and learning-to-rank models. 讲者简介 : Stephen Robertson . First degree in mathematics from Cambridge; masters in information science from City University; doctorate from University College London, with BC Brookes (all a very long time ago now!). Researcher at Aslib for five years, then held a research fellowship at University College London. Began collaborations with Karen Sprck Jones and Nick Belkin at this time. Then returned to City University. Three months on a Fulbright at the University of California Berkeley, collaborating with Bill Cooper and Bill Maron. Started the Centre for Interactive Systems Research at City, and built a research group with a strong focus on the design and evaluation of information retrieval systems. Other members of the Centre included Micheline Beaulieu and Stephen Walker; the Okapi system was our main vehicle for research. Developed the BM25 ranking function. Also head of department of information science during part of this time. Joined Microsoft Research Cambridge in 1998. Tony Kent STRIX award (Institute of Information Scientists) 1998. Gerard Salton Award (SIGIR) 2000. Fellow, Girton College Cambridge, 2003. Professor Emeritus, City University, 2010. 学术讲座 4 : Statistical Language Models for Information Retrieval , Chengxiang Zhai 摘要 : Statistical language models have been successfully applied to many problems in information retrieval in the past decade. A great deal of work has shown that statistical language models not only achieve superior empirical performance, but also facilitate parameter tuning and provide a principled general way for modeling various kinds of complex and non-traditional retrieval problems. The purpose of this tutorial is to systematically review the major progress in applying statistical language models to information retrieval with an emphasis on the underlying principles and framework, empirically effective language models, and language models developed for non-traditional retrieval tasks. Tutorial attendees can expect to learn the major principles and methods of applying statistical language models to information retrieval, the outstanding problems in this area, as well as obtain comprehensive pointers to the research literature. Attendees will be assumed to know basic probability and statistics. 讲者简介 : Chengxiang Zhai is an Associate Professor of Computer Science at the University of Illinois at Urbana-Champaign, where he also holds a joint appointment at the Graduate School of Library and Information Science, the Institute for Genomic Biology, and Department of Statistics. He received a Ph.D. in Computer Science from Nanjing University in 1990, and a Ph.D. in Language and Information Technologies from Carnegie Mellon University in 2002. He worked at Clairvoyance Corp. as a Research Scientist and a Senior Research Scientist from 1997 to 2000. His research interests include information retrieval, text mining, natural language processing, machine learning, and biomedical informatics. He has published over 100 papers on these topics in major conferences and journals. He serves as an Associate Editor for ACM Transactions on Information Systems, and Information Processing and Management, and is also on the Editorial Board for Information Retrieval Journal. He is a program co-chair of ACM CIKM 2004 , NAACL HLT 2007, and ACM SIGIR 2009. He is an ACM Distinguished Scientist, and a recipient of an Alfred P. Sloan Research Fellowship, the ACM SIGIR 2004 Best Paper Award, and the 2004 Presidential Early Career Award for Scientists and Engineers (PECASE). 学术讲座 5 : Temporal Dynamics and Information Retrieval , Susan Dumais 摘要 : Many digital resources, like the Web, are dynamic and ever-changing collections of information. However, most of the information retrieval tools that have been developed for interacting with Web content, such as browsers and search engines, focus on a single static snapshot of the information. In this course, I will present analyses of how Web content changes over time, how people re-visit Web pages over time, and how re-visitation patterns are influenced by changes in user intent and content. These results have implications for many aspects of information retrieval and management including crawling, ranking and information extraction algorithms, result presentation, and evaluation. I will describe a prototype system that supports people in understanding how the information they interact with changes over time, and a new retrieval model that incorporates features about the temporal evolution of content to improve core ranking. Finally, I will conclude with an overview of some general challenges that need to be addressed to fully incorporate temporal dynamics in information retrieval systems. 讲者简介 : Susan Dumais is a Principal Researcher and manager of the Context, Learning and User Experience for Search (CLUES) Group at Microsoft Research. Prior to joining Microsoft Research, she was at Bellcore and Bell Labs for many years, where she worked on Latent Semantic Indexing (a statistical method for concept-based retrieval), interfaces for combining search and navigation, and organizational impacts of new technology. Her current research focuses on temporal dynamics of information, user modeling and personalization, context and information retrieval, interactive retrieval, and novel evaluation methods. She has worked closely with several Microsoft groups (Bing, Windows Desktop Search, SharePoint Portal Server, and Office Online Help) on search-related innovations. Susan has published more than 250 articles in the fields of information science, human-computer interaction, and cognitive science, and holds several patents on novel retrieval algorithms and interfaces. Susan is also an adjunct professor in the Information School at the University of Washington. She is Past-Chair of ACM's Special Interest Group in Information Retrieval (SIGIR), and serves on several editorial boards, technical program committees, and government panels. She was elected to the CHI Academy in 2005, an ACM Fellow in 2006, a member of the National Academy of Engineering (NAE) in 2011, and received the Gerard Salton Award from SIGIR for Lifetime Achievement in 2009.
近日Baeza-Yates B. Ribeiro-Neto 出版了Modern Information Retrieval第二版。以前读书时曾细读过该书的第一版多遍,感觉是一本非常好的介绍信息检索相关内容的技术书籍。大牛门总是能比较及时总结最新的进展,以简易的语言,系统而且全面将相关内容介绍给读者。希望能尽快买到该书,细读一番。 单纯从封面可以看出,第二版体现了网络的新特性,即Web2.0下的一些特性。 巧合的是, 最近(2011年2月11日)出版的《科学》杂志上的 “Dealing with Data”专题 ,其封面也体现了Web2.0的特色(尽管内容和Web2.0关系并不是太大)。 设想一下,Semantic Web和物联网都成为现实之前,海量数据处理与信息检索上面临的新问题,都值得研究。期待这方面的成果尽早问世。 以上仅供参考,欢迎指正和讨论。 --------------------------------------------------------------------------------------------------------------- 注: 以下内容转载于网络。 一、《科学》 “Dealing with Data”专题 From: http://www.sciencemag.org/content/331/6018.cover-expansion COVER A word cloud generated from all of the content from the Dealing with Data special section beginning on p. 692 . The size of each word relates to the frequency with which it appears in the combined texts. References and figure legends were included; common words, authors, and affiliations were excluded. All words are lowercase. See an expanded version of this cloud and other features at www.sciencemag.org/special/data/ . Credit: Yael Fitzpatrick, using www.wordle.net --------------------------------------------------------------------------------------------------------------- 二、 Modern Information Retrieval 第二版 新书网址: http://www.mir2ed.org/ 1、内容目录 From: http://www.mir2ed.org/ Preface and Acknoledgments (Download) 1 Introduction (Download) (R. Baeza-Yates B. Ribeiro-Neto) 2 User Interfaces for Search (Download) (Marti Hearst) 3 Modeling (R. Baeza-Yates B. Ribeiro-Neto) 4 Retrieval Evaluation (R. Baeza-Yates B. Ribeiro-Neto) 5 Relevance Feedback and Query Expansion (R. Baeza-Yates B. Ribeiro-Neto) 6 Documents: Languages Properties (with Gonzalo Navarro Nivio Ziviani) 7 Queries: Languages Properties (with Gonzalo Navarro) 8 Text Classification (with Marcos Gonalves) 9 Indexing and Searching (with Gonzalo Navarro) 10 Parallel and Distributed IR (with Eric Brown) 11 Web Retrieval (Download) (with Yoelle Maarek) 12 Web Crawling (with Carlos Castillo) 13 Structured Text Retrieval (with Mounia Lalmas) 14 Multimedia Information Retrieval (Dulce Ponceleón Malcolm Slaney) 15 Enterprise Search (Download) (David Hawking) 16 Library Systems (Edie Rasmussen) 17 Digital Libraries (Marcos Gonalves) A Open Source Search Engines (with Christian Middleton) B Biographies References (Download) --------------------------------------------------------------------------------------------------------------- 2、教学PPT From: http://www.mir2ed.org/ Slides for Teaching 1 Introduction (PDF) (34 slides) 2 User Interfaces for Search (PDF) (87 slides) 3 Modeling (PDF) (263 slides) 4 Retrieval Evaluation (PDF) (144 slides) 5 Relevance Feedback and Query Expansion (PDF) (104 slides) 6 Documents: Languages Properties (PDF) (147 slides) 7 Queries: Languages Properties (PDF) (67 slides) 8 Text Classification (PDF) (157 slides) 9 Indexing and Searching (PDF) (153 slides) 10 Parallel and Distributed IR (PDF) (138 slides) 12 Web Crawling (PDF) (91 slides) 13 Structured Text Retrieval (with Mounia Lalmas) (PDF) (135 slides) 14 Multimedia Information Retrieval (PDF) (164 slides) 15 Enterprise Search (PDF) (128 slides) 16 Library Systems (PDF) (35 slides) A Open Source Search Engines (PDF) (25 slides) --------------------------------------------------------------------------------------------------------------- 3、其他 以下转载于: http://www.newsmth.net/bbstcon.php?board=NLPgid=11722 发信人: zibuyu (得之我幸), 信区: NLP 标 题: 新书:现代信息检索(英文版·第2版) 发信站: 水木社区 (Wed Feb 16 19:05:59 2011), 站内 现代信息检索(英文版·第2版) 丛书名:经典原版书库 原书名:Modern Information Retrieval: The Concepts and Technology behind Search, Second Edition 作者:(西班牙) Ricardo Baeza-Yates (巴西)Berthier Ribeiro-Neto ISBN:978-7-111-33174-2 定价:78.00 页数:940 出版社:机械工业出版社 【内容简介】 本书不仅详细介绍了信息检索的所有主要概念和技术,以及有关信息检索面的所有新变化,而且其组织使读者既可以对现代信息检索有一个全面的了解,又可以获取现代信息检索所有关键主题的详细知识。本书的主要内容由信息检索领域的代表人物Baeza-Yates和Ribeiro-Neto编写,对于那些希望深入研究关键领域的读者,书中还提供了由其他主要研究人员编写的关于特殊主题的发展现状。 与上一版相比,本版在内容和结构上都有大量调整、更新和充实,其中新增内容在60%到70%左右。具体更新情况如下: ● 新增了文本分类、网络信息爬取、结构化文本检索和企业搜索等章节,以及关于开源搜索的一个附录。 ● 全面改写了用户界面、多媒体检索和数字图书馆等内容。 ● 拓展了一些章节,介绍了信息检索方面的新的重要进展,如语言模型、新的评价方法、查询的特点、基于聚类和分布式信息检索等。 【作者简介】 Ricardo Baeza-Yates于加拿大滑铁卢大学获得计算机科学博士学位,现为Yahoo!欧洲和拉丁美洲研究院副总裁,主管Yahoo!在巴塞罗纳(西班牙)和圣地亚哥(智力)的研究中心,并监管海法研究中心。他曾担任智利计算机科学学会主席、智力大学计算机科学系Web研究中心主任、ICREA教授,并且他还在巴塞罗纳发布拉大学创立了信息与通信技术系Web研究组。现在他仍是智力大学和发布拉大学的兼职教授。他的主要研究方向为算法与数据结构、信息检索、用户界面以及可视化在数据库中的应用等。 Berthier Ribeiro-Neto于加利福尼亚大学洛杉矶分校获得计算机科学博士学位,现任巴西Minas Gerais联合大学计算机科学系副教授,同时也是ACM、ASIS及IEEE会员。他的主要研究方向是信息检索系统、数字图书馆、Web界面及视频点播。
美研究发现:呼吸仪可缓解睡眠呼吸暂停症 http://news.sciencenet.cn/htmlnews/2011/1/242272.shtm (Reuters) - People with breathing problems that disrupt their sleep were less tired after three weeks of treatment with a breathing device compared to those treated with a placebo, U.S. researchers said on Saturday. http://www.reuters.com/article/idUSTRE7000BY20110101 http://www.ncbi.nlm.nih.gov/pubmed/details Search Details 详细检索策略 Query Translation: (therapy OR therapy OR treatment OR therapeutics OR therapeutics ) AND (obstructive sleep apnoea syndrome OR sleep apnea, obstructive OR (sleep AND apnea AND obstructive ) OR obstructive sleep apnea OR (obstructive AND sleep AND apnea AND syndrome ) OR obstructive sleep apnea syndrome ) AND (respiration OR respiration OR breathing ) AND (equipment and supplies OR (equipment AND supplies ) OR equipment and supplies OR device ) Search URL Result: 334 检索结果 Stopword(s) Ignored: and Translations: breathing respiration OR respiration OR breathing device equipment and supplies OR (equipment AND supplies ) OR equipment and supplies OR device obstructive sleep apnea syndrome obstructive sleep apnoea syndrome OR sleep apnea, obstructive OR (sleep AND apnea AND obstructive ) OR obstructive sleep apnea OR (obstructive AND sleep AND apnea AND syndrome ) OR obstructive sleep apnea syndrome treatment therapy OR therapy OR treatment OR therapeutics OR therapeutics Database: PubMed User query: 检索课题 treatment and obstructive sleep apnea syndrome and breathing device
2011年的2000多篇论文已发表在77种医学期刊上,读者可以检索到最新的医学研究论文。 http://www.gopubmed.org/web/gopubmed/ http://www.gopubmed.org/web/gopubmed/1?WEB04wjjllxchklwI2cI4jI00h001000j100200010 2,065 documents semantically analyzed Term: 2011 Description: year 2011 Top Years Publications 2011 2,065 2010 44 2009 2 1 2 3 4 Top Countries Publications USA 536 China 157 Germany 132 United Kingdom 119 Japan 111 France 88 Canada 77 Italy 74 India 69 Brazil 45 Spain 43 Australia 41 Sweden 36 South Korea 35 Ireland 35 Taiwan 34 Netherlands 28 Switzerland 26 Iran 26 Belgium 16 1 2 3 4 1 2 3 ... 34 Top Cities Publications Boston 29 Beijing, China 28 London 28 Dublin, Ireland 25 Tokyo 23 New York City 21 Stockholm, Sweden 19 Ann Arbor 16 Paris 16 San Francisco 15 Los Angeles 15 Seoul, South Korea 14 Guangzhou 14 Chicago 13 Durham 13 Shanghai, China 13 Cambridge 12 Houston 12 Montreal 12 Barcelona 12 1 2 3 ... 34 1 2 3 4 Top Journals Publications Methods Mol Biol 462 Ultrason Sonochem 107 J Colloid Interface Sci 80 Neuroimage 76 Handb Clin Neurol 75 Evid Based Complement Alternat Med 70 Behav Brain Res 66 J Pharm Biomed Anal 65 Bioresour Technol 60 Appl Radiat Isot 44 Acta Biomater 44 Acta Neurochir Suppl (wien) 41 J Cogn Neurosci 40 Colloids Surf B Biointerfaces 39 J Cell Physiol 36 Cell Signal 34 Epigenetics 32 Int J Cancer 31 J Environ Manage 29 J Biomed Biotechnol 27 1 2 3 4 1 2 3 ... 451 Top Terms Publications Proteins 382 Evaluation Studies as Topic 269 Genes 255 Tissues 212 Patients 206 Pharmaceutical Preparations 186 mannosyl-oligosaccharide 1,2-alpha-mannosidase activity 177 DNA 142 Methods 141 Mice 130 Nature 128 Neoplasms 127 Therapeutics 122 signal transduction 115 Membranes 113 membrane 113 Animals 111 Peptides 105 Technology 103 Enzymes 103 1 2 3 ... 451 1 2 3 ... 18 Top Authors Publications Lamme V 2 Yu H 1 Li W 1 Sheng G 1 Liu X 1 Everling S 1 Phillips J 1 Johnston K 1 Rockmore D 1 Graham D 1 Petrosini L 1 Torriero S 1 Oliveri M 1 Koch G 1 Lo Gerfo E 1 Salerno S 1 Ferlazzo F 1 Caltagirone C 1 Kawashima R 1 Tsukiura T 1 1 2 3 ... 18
From: http://www.newsmth.net/bbstcon.php?board=SearchEngineTechgid=23434 第四代搜索引擎前沿综述 发信站: 水木社区 (Wed May 26 00:39:14 2010), 站内 一个课程论文,我把长久以来关于下一代搜索引擎的想法总结了下,希望和大家交流。 我只是入门水平,不正确之处望指正。下面贴上我的主要想法: 另外推荐下文中提到的问答平台Quora.com,上面有个帖子很有意思 Could two smart CS PhD students create a search engine that unseats Google? How vulnerable is Google to this possibility? 需要邀请的站短我邮件地址吧。登录要翻墙用facebook一次,以后就不用了。 2.3 第三代搜索引擎的缺陷 基于链接分析的第三代搜索引擎呈现出以下几点局限性: 1,一个关键字查询词对所有用户呈现的搜索结果均相同。但是实际上,比如一个计算 机用户搜索树可能指数据结构,与其他用户有很大区别。 2,Pagerank基于链接反映网页质量的方法,只反映了网页制作者对于网页质量的评 价,并没有反映网页浏览着对于网页的评价。对于一些不善于进行链接优化的网站,虽 然内容可能很优质,但是Pagerank可能并不高。同时,一些新网站很难在短期内提高 Pagerank,而一些擅长优化技术的网站会用大量垃圾链接作弊。 3,基于关键词的搜索方法是建立在用户对于搜索有明确目的,并能清晰表述这种目的 的假设上。但是实际上,用户的搜索引擎使用水平参差不齐;并且由于存在同义词等现 象,同一个搜索请求有不同的表示方法,搜索结果也大为不同。 4,现在的图像搜索,视频搜索,音乐搜索也都是基于关键字,如图像Tag,音乐电影介 绍等,而文字对于这些信息的表现能力是很有限的,也不直观。 5,并不是所有有价值的信息都能被搜索引擎爬取到,比如学校论坛,公司内网资料等 有价值的资料就无法被搜索引擎检索,这叫做Hidden Web现象;同时一些信息需要经过 人脑的加工,这方面问答平台更能胜任。这部分不能被爬取的信息实际上占了人类所有 信息的大部分。 2.4 下一代搜索的趋势 此处的下一代搜索即指第四代搜索引擎,一个主要的变化是从信息检索(Information Retrieval)到信息推送(Information Supply)的转变,信息推送将主要通过个性化搜 索和社交搜索实现。 第四代搜索将呈现出以下几个主要趋势: 1,个性化的搜索。基于个人的网页浏览历史,搜索关键词历史,个人档案信息,使得 即使是同一个搜索关键词,也能为不同用户呈现不同的搜索结果。个性化搜索将基本解 决2.3节提到的第一点局限。 2,社交搜索大大提高网页排序质量,其影响主要在两方面:a,网页浏览者(普通用 户)对于网页的评价(收藏行为,评分,举报等)将可以作为排序的依据b,通过用户的 社交圈推测用户兴趣,通过用户间的不同程度信任关系为其提供不同权重的网页排序推 荐。社交搜索也包括问答系统,用优质的设置提高信息的质量。社交搜索将基本解决 2.3节中提到的2,3,5中Pagerank和关键字搜索的局限。 3,跨媒体搜索将打通文字,图像,声音,视频间的界限,使得用图像搜图像,用声音 搜声音,用图像搜视频等都成为可能。 本文的以下3,4,5节就将分别从个性化搜索,社交搜索,跨媒体搜索三个主要趋势进 行探讨,并且尝试探讨基因搜索,移动搜索,情绪搜索。 3. 个性化搜索(Personalized Search) 个性化搜索是搜索引擎根据用户搜索的历史记录,包括用户所搜索的关键词,在搜索结 果中的点击情况,在各个网站的访问情况,书签情况等,然后对这些信息进行分析,在 用户搜索新的关键词时,能返回更有针对性的搜索结果,从而提高用户体验 个性化搜索主要存在两个难点:a,搜索引擎怎样才能准确猜测用户在特定时间的搜索目 的?人的需求是不断变更的,依据历史记录完全可能得出相差十万八千里的猜测。b,如 何在利用用户信息为其提供个性化服务的同时,保护用户的隐私? 对于第二个问题,Yabo Xu 等人的文章中进行了有益的探讨。 首先,他们观察到两个有趣的现象: a,如果能够提供个性化的服务,用户愿意牺牲一些隐私。 b,不一定需要用户隐私的细节来猜测用户兴趣,实际用更普遍的信息也可推测用户兴 趣。 4. 社交搜索 (Social Search) 随着Facebook为代表的社交网站兴起,互联网用户通过网络进行社交的时间大大增加, 并且在网络上留下了真实社交关系的数字表达,这使得利用社交关系改善搜索质量成为 了可能。如第2节所说,社交关系将从三个方面大大改善搜索质量。 4.1用户对网页评价改善搜索结果排序质量 用户对网页的评价包括主动评价和行为暗示。主动评价包括通过delicious收藏夹的评 分,评论等,行为暗示则包括用户对网页的收藏等。Shenghua Bao 通过delicious收 藏夹的数据,进行了这方面的研究。 他们引入了两个评价指标及相应算法:SSR(SocialSimRank)评价搜索关键词和用户对收 藏夹评价的关联性,SPR(SocialPageRank)揭示了网页在浏览者中的热度。 他们的结果显示,通过SSR和SPR建立的搜索引擎,更容易发现优质但是外链较少的网 页。比如这个网页 http://37signals.com/papers/introtopatterns//index 虽然内容很 少,但是Pagerank为0,而SPR为10,这样有效的发掘出了内容优质但是不善于搜索引擎 优化的网页,并且新网站也更容易得到推广。 但是Shenghua Bao等人的这篇论文也存在一定的局限性,首先数据集delicious仅有用 户对网页的文字评论而没有评分,因此无法对网页质量进行较大区分。其次没有考虑不 同的社交圈子对于网站的不同评价。另外可以做的提升就是对用户的评价进行opinion mining。 4.2 根据用户社交圈推测用户兴趣 一个社交圈子通常有相似的喜好,在社交关系的基础上,可以通过用户的社交圈子来推 测其兴趣,从而有产生更准确的搜索结果。同时,用户之间可以建立信任关系,也可改 善搜索效果。信任关系的应用比如如下情景:A是搜索引擎专家,B是一个本科生,B通 过twitter与A建立了信任关系,同时A又通过delicious对很多搜索引擎研究网站进行了 评价和打分;因此,B可以声称在搜索引擎领域对A十分信任,从而在B搜索此领域关键 词时A推荐的网页将有更高的排序权重。 4.3 高效的问答系统 问答系统是另一个高效的获取信息的渠道,我们熟知的问答系统包括百度知道, AskJeeves等,但是他们主要存在两个关键问题:1,问答者水平参差不齐,十分缺少领 域专家的参与;2,通过积分奖励的办法并不能吸引有价值的回答,经常看到的回答都 是互联网上的复制粘贴,而缺乏思考。 现在我发现的最好的问答系统是美国Quora.com。 Quora的优势主要体现在:1,新用户需要通过原有用户的邀请才能加入,并且通过 Facebook Connect登录,自然地在问答系统内形成了社交关系;同时由于初始用户都是 硅谷的IT人士,因此从一开始就聚集了大量领域专家,保持了问答的水平。2,由于社 交关系的引入,即使系统并没有设置积分奖励,用户仍然十分活跃,他们的参与完全是 因为对知识的渴望和分享的欲望,进一步保证了信息质量。3,良好的信息组织形式, 包括类似wiki的用户自主建立,编辑Topic,每个Topic下有一系列问题,问题之间又通 过Related Question联系起来。4,在现有Quora的信息架构上,未来还可以利用机器学 习推测用户的话题喜好等。 5. 跨媒体搜索 (Cross Media Search) 传统的文本、图像、音频和视频分析与检索技术都是相互独立的,缺乏面向多种媒体的 跨媒体搜索技术。这些多媒体信息应用的发展,要求信息搜索必须是跨媒体的,也就 是说用户通过统一的界面和单一的提问,就能够获得以各种媒体形式存在的语义相似的 结果。为了提供支持多种检索方式和多模态用户信息需求的跨媒体检索,跨媒体搜索 技术研究涉及海量多媒体数据的智能处理、多通道信息的融合和集成、快速准确的跨媒 体索引等关键问题研究和应用。最终,跨媒体将打通图像,文字,声音,视频的界限, 使得用图像搜图像,用声音搜声音,用图像搜视频等都成为可能。 6. 其他趋势 Jeonghee Yi 等人发现在移动用户的搜索关键词通常在2.35个词,短于通过PC提交的 关键词。另外移动用户的搜索集中在娱乐领域(44%)及旅游(7%)。移动互联网将是 新的科技周期,如何根据移动设备的特点优化搜索将是重要的课题。同时基于地理位置 的广告和聚会建议也大有可为。 生物信息的发展方兴未艾,测定大众基因序列有可能在近10年普及。当基因信息也可用 时,个性化搜索将更有可为,比如根据基因的药物建议,餐饮建议等。 NLP的发展有助于更准确理解用户搜索意图。 参考文献 The Next Generation Web Search and the Demise of the Classic IR model Andrei Broder Yahoo! Research March, 2007 The Anatomy of a Large-Scale Hypertextual Web Search Engine Sergey Brin and Lawrence Page Stanford University 网页链接分析算法的研究进展 孟涛 北京大学 2005年 Privacy-Enhancing Personalized Web Search Yabo Xu,Benyu Zhang, Zheng Chen,Ke Wang SFUMSRA WWW2007 Optimizing Web Search Using Social Annotations Shenghua Bao, Xiaoyuan Wu1 etc 上海交大/IBM中国 WWW2007 Personalized Social Search Based on the Users Social Network David Carmel,etc IBM Haifer/L3S research CIKM09 Image Retrieval: Ideas, Influences, and Trends of the New Age Ritendra Datta etc The Pennsylvania State University ACM Computing Surveys Deciphering Mobile Search Patterns:A Study of Yahoo! Mobile Search Queries 附件: 第四代搜索引擎前沿综述-刁轶夫-3061401080.pdf (889KB)
http://www.ncbi.nlm.nih.gov/sites/myncbi/searches/ 建立 My NCBI My NCBI Home Saved Data Saved Searches Saved Searches PubMed Searches Name Last Searched Schedule H1N1 FLU ( Settings ) yesterday daily lung cancer and radiotherapy ( Settings ) today daily breast cancer and therapy ( Settings ) today daily Delete PubMed Searches Show What's New 将检索策略保存到 My NCBI http://www.ncbi.nlm.nih.gov/sites/entrez U.S. National Library of Medicine National Institutes of Health Search: aids and therapy Search: All Databases PubMed Protein Nucleotide GSS EST Structure Genome BioSystems Books CancerChromosomes Conserved Domains dbGaP 3D Domains Gene Genome Project GENSAT GEO Profiles GEO DataSets HomoloGene Journals MeSH NCBI Web Site NLM Catalog OMIA OMIM Peptidome PMC PopSet Probe Protein Clusters PubChem BioAssay PubChem Compound PubChem Substance SNP SRA Taxonomy ToolKit ToolKitAll UniGene UniSTS Search Clear RSS Settings Search: aids and therapy Number of items displayed: 5 10 15 20 50 100 Feed name: var d = document.getElementById('search_term'); if (d) {d.focus();} 有什么问题吗?看看My NCBI Help http://www.ncbi.nlm.nih.gov/sites/myncbi/about/ My NCBI Help Topics About My NCBI Accesskeys About My NCBI Linked Accounts Registering for My NCBI Signing in and out of My NCBI Forgot your My NCBI username or password Changing your My NCBI password Saving your searches automatic e-mail updates Running a saved search and checking for new results Deleting a search Changing a saved search Creating collections Viewing collections Creating Bibliographies Editing collections Merging collections Sharing collections Managing your recent activity User preferences including storing or changing an e-mail address, highlighting search terms changing the Links menu display Changing your filter preferences Setting LinkOut preferences Setting your document delivery provider preference and setting an outside tool preference Sharing filters, highlighting, document delivery, and outside tool settings
7th International Symposium on Computer Music Modeling and Retrieval (CMMR 2010) 会议网址: http://www.icad.org/node/3106 论文提交截止日期:2010年1月15日,录用通知:2010年3月1日 会议地点:西班牙马拉加,2010年6月21日2010年6月24日 该会议基本是每年召开一次,CMMR 2010已是7届,历届会议论文均刊登在Springer出版的丛书丛刊《Lecture Notes in Computer Science》上,2010年的7届会议论文仍旧刊登在《Lecture Notes in Computer Science》,该会议论文均被EI、ISTP收录。 2008年5届CMMR会议刊登在Lecture Notes in Computer Science,2009年Volume 4969被EI、ISTP收录23篇,其中芬兰5篇,丹麦、德国各3篇,法国2篇,比利时、巴西、意大利、挪威、西班牙、突尼斯等各1篇。 会议主题: Auditory perception and cognition * Virtual reality, augmented reality and human-computer interaction * Digital music libraries * New methods for music representation and visualization * Retrieval and recommendation tools * Games and interactive learning * Music production and composition tools * Structuring of audio data * Cooperative music networks * Analysis, recognition, comparison, classification, and modeling of sound and music * Music and sound data mining * Sound synthesis * Optical music recognition * Semantic music technologies * Sound source separation * Music structure analysis * Music transcription * Artificial intelligence and cognitive science for sound and music
信息检索领域最著名的奖是Gerald Salton奖,由信息检索领域顶级会议SIGIR发布,获得Salton奖的,毫无疑问是IR里公认的大牛,比如仙逝的Salton与Karen、Rijsbergen、Robertson、Dumais、Croft等。 欧盟向来有与美国争夺科技制高点的传统,老美搞SIGIR,EU就搞ECIR(European Conference in Information Retrieval),SIGIR设立SALTON奖,ECIR就出来了Karen Sparck Jones奖。 无论从纪念Karen教授的角度,还是从推动IR研究与应用的角度来说,这都是大好事。 关于Karen奖的情况可以参见下面附件。 -------------------------------------------------------------------------- 附: Karen Sparck Jones Award情况 BCS / BCS IRSG Karen Sparck Jones Award An Award to Commemorate Karen Sparck Jones *** Information Retrieval and Natural Language Processing **** *** Deadline for nominations 30 October, 2009 **** The British Computer Society Information Retrieval Specialist Group (BCS IRSG) in conjunction with the BCS has created an award to commemorate the achievements of Karen Sparck Jones. Karen was an Emeritus Professor of Computing and Information at the University of Cambridge and one of the most remarkable women in computer science. Her contributions to the fields of Information Retrieval (IR) and Natural Language Processing (NLP), especially with regards to experimentation, have been outstanding and highly influential. Karen's achievements resulted in her receiving a number of prestigious accolades such as the BCS Lovelace medal, for her advancement in Information Systems, and the ACM Salton Award for her significant, sustained and continuing contributions to research in information retrieval. In order to honour Karen's achievements, the BCS/BCS-IRSG has established an annual award to encourage and promote talented researchers who have endeavoured to advance our understanding of Information Retrieval and Natural Language Processing with significant experimental contributions. To celebrate the commemorative event, the recipient of the award would be invited to present a keynote lecture at the BCS-IRSG's annual conference the European Conference in Information Retrieval (ECIR). This forum provides an excellent venue to present and announce the award as the conference attracts many new and younger researchers. The recipient would also be presented with a prize consisting of a certificate, a trophy and a cash prize of 1000 plus expenses to travel to ECIR. BCS/BCS-IRSG Karen Sparck Jones Award: Eligibility: Open to all IR/NLP researchers, who have no more than 10 years post doctoral or equivalent experience. Criteria: To have endeavoured to advance our understanding of IR and/or NLP through experimentation. Nominations: The following should be provided - name, position, affiliation, years since completing PhD, a short case for the award (composed of a short description of why the individual should receive the award), a short description of what contributions the individual has made, a list of the individuals top five publications reflecting the relevant contributions, and two referees. The nomination text should not exceed 2500 words. If you are intending to nominate someone or yourself, it would be helpful, at this stage nearing the deadline, if you could let us know in as soon aspossible in advance (contact as per further below ayse.goker.1@soi.city.ac.uk). Award Panel: The Panel Chair, appointed by the BCS IRSG Committee, will invite panel members from amongst representatives of the BCS main council, the BCSIRSG Committee, sponsoring organisation(s), as well as at least two experts appointed by the BCS-IRSG committee and the Awards Coordinator of the BCSIRSG. Prize: The recipient of the award would receive a certificate, a trophy, a cash prize of 1000 plus expenses to travel to ECIR to present the keynote lecture. Presentation: The recipient of the award is expected to give a keynote lecture at ECIR when he/she would also be presented with their trophy, and cash prize. Timeline: 8 April, 2009 - Call for nominations. 30 October, 2009 - Deadline for nominations. 15 December, 2009 - Notification of the prize winner. 28-31 March, 2010- Winner presents keynote at ECIR. Sponsors: Currently, the award is being sponsored by the BCS IRSG and Microsoft Research Cambridge. Contact: Ayse Goker, ayse.goker.1@soi.city.ac.uk http://irsg.bcs.org/ksjaward.php http://irsg.bcs.org/ksjaward/KSJ_Award_Flyer_final.pd
1 、 引言 在互联网、计算机辅助设计( CAD )、分子生物学( 3D 蛋白质模型)、计算机图形学、医药以及考古学等不同领域中,大型的三维( 3D )数据库变得越来越普遍。近期在激光扫描技术的进展使我们可以方便地构造一个物体精确的 3D 几何模型。这方面的应用包括对文化遗产的重建,例如斯坦福大学的数字米可朗基罗 和数字罗马 项目。激光扫描也可以生成工业和动画中人体头部、身体等真实对象的 3D 模型。 其他领域也有很多 3D 数据库。例如,国立设计库为在线的 CAD 模型数据库 ,蛋白质数据银行 是在线的 3D 生物高分子结构数据库。 HUGO 则为基于可视化人体项目 的 3D 解剖体和表皮数据库。 近年来,计算机科学在计算机辅助检索和分析多媒体数据方面取得了惊人的进展。例如,假设你需要为演讲准备一张马的图片。在十年前,你要么( 1 )绘制一张图片;( 2 )去图书馆复印一张图片;或( 3 )去农场照一张马的照片。现在你只需简单的从网络成千上万的资源中挑选一张合适的图片。虽然文本、图像和音频的搜索已较为常用,但 3D 数据信息的检索仍在起步阶段。 然而,新的扫描和交互工具降低了构造精致的 3D 模型的开销;图形硬件变得越来越便宜(摩尔法则),扩大了广大用户对 3D 模型的需求;互联网为 3D 模型的传播提供了平台。这三个趋势加速了 3D 模型的繁衍,使其在不久的将来将会变得和当今其他多媒体数据一样普遍。 这些进展正在改变我们对 3D 数据的观念。以前计算机图形学中主要的挑战将由以前的如何建立有趣的 3D 模型发展成如何寻找它们。例如,假设用户想创建一个城市场景的 3D 虚拟世界,他将需要骑车、街灯、路标等 3D 模型。那么,他是自己购买 3D 建模工具构造模型,还是从大型 3D 模型网络数据库中获取模型呢?与当前文本、图像、音频等其他媒体相同,信 3D 模型的检索、匹配、识别和分类的也将迅速的发展。 那么接下来的问题就是人类如何搜索 3D 模型。最简单的方法仍然是基于文件名、标题或上下文的关键字检索。然而这种方法在以下情况的鲁棒性不高:包括对象无标注(例如 B19745.wrl ),对象标注不具体(例如 yellow.wrl 或 sarah.wrl ),关键字无区分性(例如搜索脸部却标注为非多边形人体),用户不知道的关键字(例如错误的拼写或外文标记),以及标注对象时还不确定其关键字。 在这样的情况下,我们认为基于形状的查询将更有效的搜索 3D 对象。例如,形状可以和功能相结合来定义对象的类别(例如圆形咖啡桌),形状也可以用于区分相似的对象(例如办公椅和沙发)。有很多类别可以由形状单独定义(例如卷形物),这时一幅图片抵过千言万语。 本文将研究基于形状的 3D 模型自动检索方法,其挑战有两个方面:首先,我们必须开发 3D 形状的计算表示(形状描述子),并建立相应的索引以加快查询的速度。本文将介绍新颖的采用方向不变的球面谐波描述子的 3D 数据库搜索方法。其次,我们需要支持未训练用户表达基于形状查询的交互界面。本文将 3D 草图、 2D 草图、文本和基于形状相似度的交互式修改组合起来,并将其整合到搜索引擎中,实现 3D 模型的网络检索(见图 1 )。 随着 3D 模型数量和种类的不断增长,浏览这些大型数据库的应用也越来越多。在这些大型的 3D 数据库中进行检索并不容易。虽然模型可能有相关的名字或文字描述,但多数情况下这些信息无法完整精确地描述模型本身。相比标注对象,更好的办法是让模型表达自身,也就是说,采用模型的内容而不是用户标注的主观文本信息。 多数具有真实生命的对象的 3D 模型可以通过颜色、纹理和形状信息进行区分。颜色和纹理在某些模型中可能会失效,例如 3D 蛋白质模型。因此,形状是描述 3D 数据最基本的特征。用户对形状的概念并没有统一的定义。下面给出一些最常用的定义: 韦氏字典形状(名词): 1、 某个或某种特定对象的可见组成特性。 2、 轮廓的空间形态。 3、 标注的或普遍公认的空间形态。 Kendall's 的定义 : 形状是对象的位置、比例、方向被去除后剩下的所有几何信息。 Kendall's 的定义认为对象的形状与其相似性变换无关,例如,汽车的 3D 模型再旋转、缩放或平移情况下应该是保持不变的。对给定的 2 个模型,直观上确定其是否相似的方法是寻找模型直接的对应关系并将模型重合。重合的程度即说明了模型的相似度。这种方法被 Besl 和 McKay 提出,称为形状注册问题。其主要应用是从多视角(例如 3D 点阵)重合模型以进行 3D 重建。但这在大型数据库的 3D 模型检索中的效率并不高。 目前 3D 模型检索的方法以简洁的方式描述模型(特征向量或图等结构化描述),并比较这些简洁的描述子来加快匹配的速度。因为形状是旋转、平移和缩放无关的,描述子也应该是变换无关的,或者数据库中的 3D 模型都预先被变换到规范的坐标系中。这即为姿态规范化问题。 本文对基于内容的 3D 形状检索的进行调研。上文以指出形状是 3D 数据最基本的特征,因此文中会交替使用 3D 形状、 3D 模型和 3D 对象等术语。同样,文献中 3D 模型检索或 3D 模型搜索引擎都代表同样的研究领域。 荷兰乌特列支大学的 Tangelder 和 Veltkamp 在形状表示、相似度 / 不相似度度量、检索性能、部分匹配能力、鲁棒性和姿态规范化需求等方面对形状检索方法进行评价。普度大学机械工程学院的 Lyer 等人 对包括具体 CAD 方法的形状搜索技术进行了概述。新加坡国立大学的 Atmosukarto 和 Naval 给出了当前技术的介绍。此外, Siggraph2004 的 3D 想着检索课程也由 Funkhouser 和 Kazhdan 在普林斯顿大学的计算机科学系开展。 本文的结构如下: 第二章给出 3D 形状表示技术的综述。由于 3D 形状重建(激光扫描、基于立体视觉的重建、运动结构)和建模( CAD 根据)的方法不同,这些数据在数字环境中的组织方法也不同。文中给出静态和动态模型(摆动或变形)的表示方法,但只给出静态模型的相似度和匹配方法。 第三章介绍形状相似度和匹配的概念。 第四章介绍相似度匹配和模型检索中的 3D 形状描述方法。这些方法分为 2 类:直接从 3D 模型抽取(基于模型的)或从其 2D 投影中抽取(基于视图的)。基于模型的方法可以是纯几何的、结构的或两者的结合。几何方法包括全局或局部的形状描述。 第五章介绍 3D 形状搜索引擎的整体结构及各部分子系统。 第六章给出 3D 形状检索系统的评价和性能描述。 2 、数字世界中的 3D 形状表示 许多应用都需要在数字环境中构造真实时间中的对象,这些模型的质量受到硬件和软件能力的限制。近来硬件的发展是用户可以更方便的可视化和操作复杂的模型。当前的扫描技术也可以生产几何精确的对象模型。除了硬件的发展,建模软件(例如 CAD 工具)的功能也越来越健全。 由于创建对象模型有不同的方法,数字环境中数据的技术也有不同。本章将对这些技术做简单的介绍。如前所述,这里只讲述对象形状的表示方法,不包括纹理和颜色。本章的 3D 对象表示方法可用于处理 3D 形状建设系统的输入数据。由于模型生产过程本身的原因,其中一些方法比其他方法更为普遍。 在数字世界中, 3D 模型的首要工作是可视化,有时也需要对模型进行编辑。 3D 模型的存储和显示的效率是主要关心的问题。不同的任务可能需要不同的表示方法。例如,如果需要识别场景中的对象,我们不需要非常细致的对象模型。本文不涉及 3D 模型重建、对象识别和相关的技术。读者可参阅这些技术的相关文献,包括 Campbell 和 Flynn , Jain 和 Dorai , Bennamoun 和 Mamic 以及 Pope 。 形状大致可以分为 2 类:静态形状和动态形状。静态形状为不受形变和转动而改变的刚性形状。例如咖啡杯的模型为静态形状,而人脸则为动态形状,因为其形状随说话、微笑等动作而变化。本文主要考虑静态形状的检索技术,因此只会稍微提及动态形状的表示。 2.1 静态形状 表示对象有 2 种不同的方法:基于模型(对象为中心)和基于试图(观察者为中心)的方法。基于模型的方法直接作用于 3D 数据,而基于试图的方法则存储 3D 模型的若干 2D 投影。 2.1.1 基于模型的表示 3D 对象可在不同抽象层次进行表示。首先是 3D 空间的原始数据点集表示,这种表示缺乏结构性,但足够进行可视化。这相当于 2D 图像中的像素。第二抽象层是形状的轮廓,也就是 3D 形状的表面,这与 2D 曲线相对应。第三抽象层为体表示,这与 2D 形状的面积相对应。 2.1.1.1 基于点的表示 点集 点集的定义为点 P={p1,p2,,pN} 的集合,其中 P R 3 且 pi=(xi,yi,zi) T 。 图 2.1: 两个点集的 2D 抽点打印( Bunny 兔子和 CAD 模型) 范围图像 范围图像与密度图像都从某个视角捕捉形状,但与捕捉颜色信息不同的是,范围图像捕捉距离的深度信息。图 2.2 由 Ohio 州立大学给出了的天使的密度和范围图像。这种表示多用于 3D 模型重建,将不同视角的图像进行合并。这是 3D 形状注册的一个例子。 图 2.2: Ohio 州立大学的天使图像(密度和范围图像) 范围图像中深度值根据不同的图像生成方式而变化。例如,在图 2.2 中,对象离摄像机越远,则相应的像素值越深。反之依然,见图 2.3 。 图 2.3: 范围图像数据库中的多面体对象(密度和范围图像) 2.1.1.2 表面表示 3D 形状可由其外表面表示,这类似 2D 形状的轮廓。本节介绍表示形状表面的数学模型。 多边形 Soups 这种表示多用于 CAD 工具,也称作多边形 Soup 模型。这种模型中所有的多边形不完全相连。 3D 模型检索中多认为这种模型是错误定义的,而网上的很多 3D 模型都是以多边形 Soups 表示的。 图 2.4: 一个多边形 Soup 的 CAD 模型 多边形网格 多边形网格由于其简单性成为表示 3D 模型的常用方法。 3D 模型的多边形网格的定义为一对有序的链表: M= P , V 其中, V={v1,v2,,vN} 为顶点的列表且 vn=(xn,yn,zn) T ; P={p1,p2,,pN} 为平面多边形的列表,且 pr=(v n,1 , v n,2 , , v n,kr ) 。 Kr 为多边形 pr 的顶点数目。如果所有 pr 的 k=3 ,则所有 pr 均为三角形网格。 图 2.5: 人脚骨的多边形网格模型 ( ) 参数形式 一般 3D 表面的参数形式由如下定义: 图 2.6: 以网格形式显示的 NURBS 曲线 ( ) 其中 u 和 v 为参数变量。 3D 表面由两曲线进行笛卡尔积生成。非均匀有理 B 样条( NURBS )是一种参数形式,其定义如下: 其中 N 和 M 为 k 阶和 l 阶的 B 样条基函数, B h i,j 为控制点的齐次坐标。 参数形式通常用于最初的模型表示,之后再由此生成多边形网格的表示 。 子分表面 由提出的子分表面的思想是很简单的:子分定义了一系列逐渐精化的光滑曲线或表面。 下图介绍如何从粗略的表示构建精确的表面。左边网格中的每个三角形都根据子分规则细分成 4 个三角形,得到中间网格。再进行子分操作则得到右边的网格。 图 2.7: 子分表面 ( ) 子分表面是建模和动画中非常有用的表示方法,它可以捕捉不同分辨率层的模型。具体介绍间文献 隐式表面 3D 表面可隐式定义为任意函数 f 的 0 集如下: 下图给出了由公式 生成的模型。 图 2.8: 隐式表面 ( ) 超二次曲面 超二次曲面的定义为由向量包含的闭合曲面,向量的 x,y,z 由角度函数和两个 2D 参数曲线进行球积确定。 超椭圆体为一种超二次曲面,其参数形式如下: 其中 (a1; a2; a3) T 为缩放向量, 1 2 表示平面经纬度上的正方度。 超二次曲面可以通过增加特定的加尖、扭转、弯曲等操作对多种自由形体进行建模。下图给出了由沿 z 轴加尖后绕 z 轴扭转变化后的超二次曲面 。 图 2.9: 变形的超二次曲面 ( ) 2.1.1.3 体表示 体素 体素是体绘制中最小的 3D 单元,相当于 2D 绘制中的像素。 该方法是最简单的空间子分表示方法,但耗费内存。在医学应用中使用较多。 图 2.10: 由体素表示的飞机模型 ( ) 八分树 八分树是基于空间的子分表示方法,立方体空间被递归地分成更小的立方体,进而建立层次的数据结构。下图给出了实体模型的八分树。 图 2.11: 八分树表示 白色节点表示空的子立方体,黑色节点表示完全填充的子立方体,灰色节点表示部分填充的子立方体。这种方法比体素的更节省内存。 空间二分树( BSP ) 空间二分树是八分树的另外一种表示方式。 BSP 树提供了对象或空间中的多个对象的搜索结构和几何表示。 图 2.12: 2D 对象的 BSP 树 ( ) 非叶结点表示被二份的平面。平面可从任何方向进行子分。 图 2.13: 多对象的 2DBSP 树表示 ( ) 构造实体几何 (CSG) 构造实体几何是一种层次化的表示。每个形状由形状单元通过二值操作组合而成。 图 2.14: CSG 通用圆柱体 这种方法也称作扫描表示,由环状轮廓 C(s, ) 沿模型主轴(样条)的空间曲线 A(s) 移动生成。 图 2.15: 通用圆柱体 ( ) 2.1.2 基于视图的表示 基于试图的表示的出发点是相似的 3D 形状从相同的视角看起来也是相似的,因此可采用对象的一系列视角( 2D 投影)来表示形状。 该方法通常用于对象识别,本节将介绍一些主要技术。 轮廓 轮廓包括对象某个视角的边界。为了表示 3D 形状,需要生成并存储轮廓的集合。相对于基于模型的表示,这种方法更加简洁。该方法通常用于对象分类,采用一系列轮廓表示模型并从匹配相应的视图。但不同的 3D 形状可能具有相同的轮廓图像组。 图 2.16: 椅子的轮廓图像 ( ) 视点图 3D 形状从不同视角看起来可能是不同的。例如,立方体的上视图是一个正方形。因此,可将视图空间分成视图类或典型视图。每类的视图具有某种相同的属性,并可由聚类算法生成试图类。 1979 年 Koenderink 和 van Doorn 将视图类表示称为视点图。图中的结点表示根据视点命名的视图类,连接不同结点的边表示视点的改变。结点之间的不同称作视觉事件。但这种表示较复杂,使用受限。 图 2.17: 视点图表示 2.2 动态形状 在建模和视觉应用中常涉及到动态形状。这些形状可以随时间摆动或形变,且有多种表示方法。下面是一些例子 。 Snakes: 主动轮廓模型 对给定点集拟合其形变轮廓 (snakes) 是一个约束的能量最小化问题。主动轮廓模型由 Kass, Witkin 和 Terzopoulos 于 1987 年提出 。其中总能量包括三个组成部分:弯曲或伸展轮廓的内部轮廓能量, . 轮廓和图像密度或梯度间的图像能量,和预定义约束下的外部能量。 形变体模型 Park, Metaxas 和 Axel 根据心脏运动的四面体元素对人类心脏的运动进行建模。 气球模型 这是一种形变的网格表示,其中通过弹簧建模网格的边,使得整个网格可随用户而拉伸或压缩。 Chen 和 Medioni 给出了这种表示的例子。 3 、形状相似度和匹配概念 形状匹配比较两个形状的相似性,是检索、识别和注册等应用中非常重要的概念。通常,这通过计算距离进行不相似度度量,其中距离越小不相似性越小,相似性越大 。 定义 :给定形状集合 S={s 1 ,s 2 ,,s N } ,相似度距离由 d(s i ,s j ):S S R + 0 定义,其中 s i ,s j S ,距离函数 d 具有如下性质: (i) 自相似性 : s i S, d(s i ,s i ) = 0 (ii) 正定性 : s i , s j S, s i s j , d(s i ,s j ) 0 (iii) 对称性 : s i , s j S, d(s i , s j ) = d(s j , s i ) (iv) 三角不等性 : s i , s j ,s k S,d(s i , s k ) d(s i ,s j ) + d(s j ,s k ) (v) 变换无关性 : 对给定变换组 G , s i , s j S,g G,d(s i ,g(s j ))=d(s i ,s j ). 自相似性表示形状与本身完全匹配。正定性表示两个不同的形状无法完全匹配。 定义: 具有自相似性、正定性、对称性和三角不等性的距离函数称作度量。 定义: 具有自相似性、对称性和三角不等性的距离函数称作伪度量。 定义: 具有自相似性、正定性、对称性的距离函数称作半度量。 3.1 形状匹配问题分类 给定两形状 s 1 , s 2 和不相似度度量 d , Veltkamp 对形状匹配做了如下分类: ▲ 计算问题 令 d 为变换无关的不相似度函数,计算 d(s 1 ; s 2 ). ▲ 决策问题 令 d 为变换无关的不相似度函数,给定阈值 t ,判断是否 d(s 1 ; s 2 ) t 。 ▲ 决策问题 给定阈值 t ,判断是否存在变换 g ,其中 d(g(s 1 ); s 2 ) t. ▲ 最优化问题 寻找变换 g ,其中 d(g(s 1 ); s 2 ) 最小。很多形状匹配的应用需要以此为基础。 ● 基于形状的检索 给定形状数据库 S={s1, s2, sN} 和查询形状 q ,检索与 q 相似的形状。有两种方法: 1 )(决策问题)给定阈值 t ,寻找所有 d(q,si)t 的形状。 2 )(计算问题)寻找 d(q,si) 最小的 k 个形状。 ● 形状识别和分类 1 )(决策问题)给定形状 s 和模型 o ,判断是否 d(s,o) 足够小。 2 )(计算问题)给定形状 s , k 类形状以及各类形状表示 r1, r2, ,,,, rk ,找到类 ri ,使得 d(ri,s) 最小。 ● 形状校准和注册 ( 优化问题 ) 给定两形状 s1 和 s2 ,寻找变换 g 使得 d(g(s1),s2) 最小。 如上所述,这个问题通常被 3D 形状检索的文献归为计算问题。给定查询模型,系统返回数据库中最相似的模型。 形状匹配中形状的表示方法,决定了相似度度量的选择。 第四章对 3D 形状检索中的匹配技术做综述。本节给出最常用的相似度度量。 Veltkamp 给出了计算几何模型中的形状匹配以及多边形和曲线匹配的相似度度量方法的综述。 ● L p 范式 (Minkowski 距离 ) 该方法用于匹配数字的向量形式的形状描述子。 定义: 给定 x , y 两点,则 Lp 距离定义为: 对 p1 , Lp 距离为一种度量。 若 p=1 ,称为 L1 范式或曼哈顿距离或城市块距离。 若 p=2 ,称为 L2 范式或欧几里德距离。 Lp 距离不是变换无关的不相似性度量。 图 3.1: 2D 空间满足 ||x||p=1 的点 ● Hausdorff 距离 定义 给定由点集表示的两个形状 X={x1,x2,,xM} 和 Y={y1,y2,,yN} ,则 X 和 Y 之间的 Hausdorff 距离定义为: H(X,Y) = max(h(X,Y),h(Y,X)) 其中 , ||.|| 为欧几里德距离。 图 3.2: Hausdorff 距离的可视化 Hausdorff 距离是一种度量。但它不是变换无关的,且对噪音不够鲁棒。这种方法的优点是可以进行局部匹配。 点集 A 和 B 之间的 Hausdorff 距离定义为: H(A,B) = max(h(A,B),h(B,A)) 其中 且 。 ||a-b|| 表示点 a 和 b 之间的距离度量(例如欧几里德距离)。 h(A;B) 称为 A 到 B 的有向 Hausdorff 距离,等于 A 中点到 B 中点最近距离的最大值。直观上如果 h ( A;B ) = d ,则 A 中的每个点距离 B 中点的距离不超过 d 。 h(B;A) 称为 B 到 A 的有向 Hausdorff 距离,按照同样的方法计算。注意通常 h ( A;B ) h ( B;A ) ,图 5 给出了示例。 Hausdorff 距离为两有向距离中的最大值。 图 5: 有向 Hausdorff 距离距离示意图。 Hausdorff 距离为两有向距离的最大值,即本图中的 h ( A;B ) . 原始 Hausdorff 距离对噪音敏感。如图 5 所示,如果两个接近的点集中有一个较远的噪音点,则 Hausdorff 距离将受噪音影响而无法确定两点集的相似性。在模式识别中,噪音和异常通常会导致这样的问题。 提出了变形的局部 Hausdorff 距离来缓解这一问题,他对 A 中点到 B 中点的距离进行降序排列,并将第 k 个点的距离赋为 h ( A;B ) 。 A 到 B 的局部 Hausdorff 距离可如下定义: 例如,对 k=3 , h 3 (A,B) 将忽略 A 中较远的两点,而选择 A 到 B 第三远的距离。 h k (B;A) 按照同样方法计算。局部 Hausdorff 距离通过舍弃较远的噪声点使得距离度量更加灵活。接下来的文章中我们采用 6% 排序进行有向距离的计算,其中舍弃 6% 远的点。该数值根据我们的系统由经验确定。 尽管在实现中采用局部 Hausdorff 距离代替原始 Hausdorff 距离,方便起见在下文中我们仍使用 Hausdorff 距离指代局部 Hausdorff 距离。由于 Hausdorff 距离的原始形式使用的较少,在文献中这两者的称呼也经常通用。但我们需要区分 Hausdorff 距离与接下来在下节中介绍的变形 Hausdorff 距离。 不管是计算第 k 个还是最大有向距离值, h(A;B) 都需要计算 A 中每个点到 B 中点的最近距离。通过距离变换可加速计算的过程。主要思想在训练阶段预先 一次 计算所有需要的距离值,在识别过程中通过索引快速地获取想要的距离值。在系统中,我们通过距离的阶进行加速变换。具体的变换方法和模版匹配的应用可在 4.5 节,相似度度量之后进行介。, 变形 Hausdorff 距离 提出了变形 Hausdorff 距离 (MHD) ,将有向距离计算中的 max 操作符替换为距离的平均值 : 其中 N a 为 A 中点的数目。变形 Hausdorff 距离则等于两有向平均距离中的最大值 : Although 虽然当 k = 50% 时 与 相似, 但前者为平均有向距离而后者为其中值。 Dubuisson 和 Jain 认为在对象匹配时,平均有向距离比局部有向距离更可靠,因为前者收噪音影响较小。 我们仍然采用距离变换辅助距离计算。变形 Hausdorff 距离比原始 Hausdorff 距离的计算性能更高,因为无需存储最小距离信息。 ● 弹性匹配距离 定义 令 A={a1,a2,,aM} 和 B={b1,b2,,bN} 为有限的有序轮廓点集, f 为 A 与 B 中所有点的相关性并满足 : { ai,aj A,aiaj f(ai)f(aj)} 。伸缩 s 定义为 : 则 A 与 B 之间的非线性弹性匹配距离为 : 其中 d(a i ; b j ) 为 ai 与 bi 正切角的差。 距离可通过动态规划方法计算。弹性匹配距离不满足三角不等性,因此不是度量。 ● 地面移动距离 这也被称作传输距离。 定义 给定加权点对 A={(A1,w(A1)),(A2,w(A2)),,(AM,w(AM))} 以及 B={(B1,w(B1)),(B2,w(B2)),,(BN,w(BN))} ,其中 A i ;B i R 2 。 A 与 B 之间的传输距离为将 A 转换到 B 的所需的最小工作量。 3.2 3D 形状匹配的距离函数 根据定义, 3D 对象的形状独立于任何平移、算法和旋转。因此距离函数也应具有变换无关性。独立于所有可能变换的距离函数可由如下公式给出 : 其中 G 为变换组。 该距离函数对 3D 形状匹配并不十分有效。下面给出两种变换无关的定义 定义 ( 姿态规整化 ) : 给定形状集合 S={s1,s2,,sN} ,度量 d(si,sj) 和变换组 G 。设 n 为多到一的函数,其中 g G , si S,n(g(si))=?i 且 si,sj S,d(si,sj)~d(?i, ?j) ,则 d(si,sj)~d(?i, ?j)=d(g(si),g(sj)) G 为平移、缩放和旋转等变换的任意组合。 G 上定义的函数 n 即称作姿态规整化函数。 定义 ( 不变特征 ) : 给定形状集合 S={s1,s2,,sN} ,度量 d(si,sj) 和变换组 G 。令 f + 为函数,其中 g G, si S,f+(g(si))=f+(si) 且 d(si,sj)~d(f+(si), f+(sj)) ,则 d(si,sj)~d(f+(si), f+(sj))=d(g(f+(si)),g(f+(sj)) 函数 f+ 称作 不变特征抽取函数 。 3D 形状的表示形式无法用于匹配。因此需要简化的描述子(形状描述子)来捕捉这些重要的形状特征。 定义 ( 形状描述子生成 ) : 给定形状集合 S={s1,s2,,sN} , 度量 d(si,sj) 。令 f 为函数 , 其中 si S, d(si,sj)~d(f(si), f(sj)) 。则 f 称作形状描述子生成函数。 若 f 对平移、缩放和旋转无关,则称作无关形状描述子生成函数。 形状描述子可以是数字的或结构化的。 数字形状描述子生成映射 X-Rn ,其中 X 为原始形状表示空间。 定义 ( 基于 3D 形状的检索问题 ) : 给定 3D 形状数据库 S={s 1, s 2 ;, s N} 以及查询形状 q ,寻找与 q 相似的形状。 解决方案 : (决策问题)给定阈值 t ,寻找所有 d(f(q),f(si))t 的形状。 (计算问题)寻找 d(f(q),f(si)) 最小的 k 个形状。其中 d 为距离函数或度量, f 为形状描述子生成函数。 若 f 不满足变换无关性,则需要先进行姿态规整化。 4 、 3D 检索中的形状匹配 近年来 3D 形状检索技术取得了很大的发展,本节对这些方法进行介绍。由于计算机图形学和 CAD 应用中常使用多边形模型,因此采用多边形表示作为 3D 模型的表示方法。 对给定多边形模型,可通过体素化生成体素模型,因此 3D 形状检索多采用多边形模型或体素模型作为输入。给定不同的 3D 模型数据库,需要创建简单的可高效计算的模型表示方法,用于模型的匹配。这在数据库规模庞大的时候更加重要,因为检索的环境是实时的。在 3D 形状检索的文献中,从初始模型中抽取的简化的表示方法称作形状描述子。这些描述子应该具有足够的描述能力来区分相似和不相似的形状,并且尽可能的简约。形状描述子可以是数字的(例如特征向量、直方图等)或结构的(例如图)。 形状匹配的方法有两种。首先是根据 3D 模型生成基于几何或拓扑特性的形状描述子,这称作基于模型的方法。有些基于模型的方法需要先预处理,将模型放置到正交坐标系中。这称作姿态规整化,在形状描述子不满足变换无关性时是必要的。平移无关性可将对象中心移到原点满足,缩放无关性可将所有的模型都缩放到相同的维数。旋转无关性稍微复杂一些,通常需要通过主元素分析 PCA 方法计算主轴,并将模型旋转使其主轴与预定义的正交坐标系重合。但这种方法有一些问题。首先 PCA 不保证主轴的正确排序,可能导致某些模型对其错误。其次,多边形网格中每个多边形的面积可能不同,将影响模型主轴的计算。加权的 PCA 算法已提出,用于解决这些问题 第二种形状匹配的方法是基于视图的方法,其中根据模型的若干 2D 投影生成形状描述子,并进行匹配。基于视图的方法一般采用 2D 形状描述子, Zhang 和 Lu 对其进行了比较详尽的介绍。这种方法需要捕捉足够多的视图来反映 3D 模型的各个方面。 4.1 基于模型的技术 3D 形状检索中基于模型的方法作用于 3D 形状本身,主要有两类方法。有些方法只考虑全局或局部的形状特性,其他方法考虑形状的结构特性,如空洞和组件等。 4.1.1 几何方法 这些方法挖掘形状的量化的特性,包括从形状中抽取出的体积、纵横比、表面积、曲率或其他数字的描述子。这些特性可以是全局的或局部的。全局特性计算速度快但无法进行局部匹配,而局部的方法则刚好相反。 4.1.1.1 全局形状描述子 全局方法把形状看作一个整体,已有很多描述对象全局形状的方法。本节按照主要思想对这些方法进行分类。 特征 给定形状,直观的方法是提取可区分不同形状的特征,例如体积、表面积或由形状表面或体积计算得到的矩。但这些特征描述里不强,因此可用于 3D 形状检索的初步过滤。 Elad 等人 提出了应用于多边形网格的基于矩的方法。他们定义了近似矩,检索如下: 作者首先在模型表面采用 N 的点。对一阶矩中心化可使其满足平移无关性,对采样点计算二阶矩的 3*3 矩阵进行分解可满足缩放和旋转无关性。规整化后计算 3D 模型的矩并生成特征向量,再根据欧几里德距离计算相似度。 Zhang 和 Chen 描述了有效计算多边形网格体积、表面积和矩的有效方法。 特征分布 这些方法采用特征的分布,本节将稍作介绍。 Osada 等人 提出了全局特征的分布方法,并通过概率分布比较得到相似度。他们定义了不同的全局几何形状函数: A3: 3D 形状表面上任意三点的角度度量。 D1: 固定点与表面上任意点的距离度量。通常固定点选择形状边界质心。 D2: 表面上任意两点的距离度量。 D3: 表面上任意三点组成三角形的面积的开发度量。 D4: 表面上任意四点组成四面体体积的开立方度量。 这些函数容易计算,且具有旋转和平移无关性。为了从这些函数产生形状分布,研究者在上述函数的每个形状分布中采样 N 个点,再创建 B 等宽的直方图。这些直方图即为分布的近似。形状相似度匹配也就转换为直方图匹配,可根据 Minkowski 范式、 Kolmogorov-Smirnov 距离、 Kullback-Leibler 散度、地面移动距离、 Bhattacharyya 距离、 X 2 统计等方法计算。 作者实现了八种计算简单的相似度度量。设 a 、 b 为待比较的两个形状, fa 、 fb 为通过直方图近似的形状概率分布函数( pdf ), f^a 、 f^b 为累积分布函数。相似度度量为: ? ? Bhattacharyya 距离: ? Pdf 的 Minkowski ( Lp )范式: ? Cdf 的 Minkowski ( Lp )范式: 这些方法不满足缩放无关性,需要进行规整化处理。作者表示 D2 函数在实验中效果最好。 Obhuchi 等人 和 Ip 等人 给出了 D2 方法的扩展。 Obhuchi 等人 提出了一种方法,沿 3D 模型的主轴计算若干统计数据,并应用于多边形网格模型。首先他们沿主轴对其模型,再计算直方图:( 1 )轴惯量的矩,( 2 )表面到轴的平均距离,( 3 )表面到轴距离的方差。这样每个模型得到由 9 个特征向量组成的特征向量,并采用欧式距离和弹性匹配对其匹配。实验表示该方法仅对旋转对称的模型效果较好。 空间图 这些方法意图捕捉形状的空间组成。 3D 形状首先被分割,再计算各部分的点分布或其特征。相似度匹配也考虑各部分之间的关系。下面给出一个例子。 Ankerst 等人 的方法包括两部分。第一部分基于离散表示产生形状直方图。第二部分定义二次距离函数。形状要事先按其质心对齐,并在表面上均匀采样以计算直方图。 他们提出了三种生成形状直方图的方法。每种方法定义了不同的形状分解:壳模型( 3D 模型被分解为绕中心点的同心壳)、扇模型( 3D 模型被分解为从中心点出发的若干扇块)和蜘蛛网模型(前两者结合)。 除了扇模型,其他两者都不是旋转无关的。作者认为欧式距离不考虑组件直接的关系而导致匹配效果不好。在这种情况下,组件反映了当前空间分解情况下点分布的空间关系,他们定义了如下的二次距离函数形式: 其中 N 为特征向量维数,或空间分解模型中 bin 的个数。 A 为相似度矩阵,其中 aij 表示特征向量中组件的相似度。可以看出,如果 A 为对称矩阵,则表示欧式距离。采用该公式可根据空间关系方便为不同的 bin 设定权值。 积分变换和特别函数 微积分的方法也被用于数字图像识别和信号处理。在 3D 检索中,一些方法采用了积分变换(变换系数)和一些特殊的函数。本节做简单的介绍。 定义 一般积分变换的定义如下 : 其中函数 K(s,t) 称作核函数。根据核函数的不同积分变换也有不同的名字。常用的包括 Hough 变换、傅利叶变换、小波变换、 Radon 变换和 Laplace 变换。 3D 形状检索对离散数据进行变换,并采用系数最为形状描述子组成特征向量。 Zaharia 和 Preteux 提出了基于 Hough 变换( 3DHT )的 3D 形状检索系统。由于 PCA 的局限性,,他们在姿态规整化过后计算所有可能的坐标轴顺序上的 3DHT 。他们称得到的 48 个 3DHT 为优化 3DHT ( O3DHT ),满足形状无关性。再计算 48 个 3DHT 形状描述子直接的 L1 和 L2 距离,并选择其中的最小值来比较模型。 Vranic 和 Saupe 采用离散 3D 傅利叶变换 (3DDFT) 产生多边形网格模型的描述子。 通过多种 PCA 算法满足旋转无关性,再对体素模型应用 3D 傅利叶变换。并由变换的实系数生成特征向量,实验中采用 L1 和 L2 距离进行度量。 Paquet 等人 采用基于小波变换的 3D 模型检索。 Daras 等人 则采用 3D Radon 变换和 L1 距离进行匹配。 3D 形状检索中也用到一些特殊的函数。 Kazhdan 等人 提出了采用球谐函数的方法,他们首先将多边形网格模型进行体素化,采用同心球面与其相交,并根据球面包含的模型多少描述每个球面函数。接下来对其进行谐波分解(频率分解)。他们总结了每个频率的谐波并生成由球面半径和频率索引的 L2 距离的 2D 图。该描述子具有形状无关性,也可应用于任何体素网格。 Novotni 和 Klein 采用 3D Zernike 矩生成形状描述子,该方法也是旋转无关的。 信息理论方法 Page 等人 对 3D 模型表面的形状复杂度进行度量。他们计算曲率熵,并称其为形状信息。他们认为曲别针比球面的复杂度更大,因此可进行量化的度量,并定义了离散情况下墒的概念 : 对网格进行均匀点采样并估计这些点的高斯曲率生成 M 个等宽的 bin ,由此估计形状的曲率概率密度函数 pdf 。根据上述定义,从 M 个 bin 中计算熵 H ,表示了 3D 形状再高斯曲率方面的复杂度。 作者表示球面为曲率复杂度最低的形状。因此上述公式计算球面的信息值为 0 。他们的实验证明具有不同曲率的模型比对称模型或重复曲率的模型更加复杂。 体积差 这种方法的前提是不同形状的空间体积构成是不同的,无法由简单的体积差技术捕捉。两个形状可能体积相同,但却不相似。为了匹配,所以的形状必须先进行姿态规整化,如下所示。 Kaku 等人 的方法采用有 Gottschalk 提出的 OBB 树数据结构。姿态规整化后,数据库中每个 3D 模型表示为二叉树,其中节点表示定向包围盒 OBB 的中心。他们根据对应节点差的总和进行相似度匹配。同时也保留原始模型的纵横比以进行其他的相似度度量。最终的相似度由加权上述两种方法的结果组成。作者与 D2 方法 进行了对比。 Leifman 等人 提出基于体积差的 oc 树。对模型进行 oc 树表示后,根节点的体积差 D 由底向上递归计算。这种方法相对较慢。 Ichida 等人 提出了交互的 3D 形状检索界面 ActiveCube 。用户可采用边长 5 厘米的立方体构建查询形状。系统实时识别用户创建的模型。数据库中的模型和查询形状均由体素表示,并通过对比体素的重叠进行匹配。 对规范形状的投影(变形) 基于投影的方法的思想是将一个形状变形到另一个所需的能量可用于两个形状的相似度匹配。在 3D 形状检索中,数据库中的每个模型都被变形对哦规范形状(如球面),变换所需的能量即作为匹配的描述子。计算能量的方法有很多,下面做些介绍。 Leifman 等人 提出了球面投影方法。首先进行姿态规整化以满足相似变换的无关性。将形状变形为其半径为 R 的包围球面的能量定义为 ,其中 为应用的力, dist 为对象表面到包围球面的距离。对表面上所有点的力假设是相同的。因此能量与球面与模型表面的距离成正比。 他们对球面上的点进行采样并计算距离。第一个距离 d1 是球面到模型的最小欧式距离,第二个距离 d2 为从模型到球面的距离,计算如下:模型上的每个点由球面坐标 ( a,q, r) 表示,对模型上每个点,寻找球面上 a,q 最为相近的点。对应关系建立以后,球面上的每个点对应表面上的一个点集。 d 2 即为从球面点到其对应点集的平均距离 (|R-r|) 。最终距离 d 为 d1 和 d2 的平均或串联。 作者从因特网收集了 1068 个任意的对象,手动将其中 258 个对象分成 17 类(人、导弹、汽车等等)。他们的方法在多数情况下性能优于形状矩 和形状分布 的方法,但对对不具有通用全局形状的类别效果不好,因为该法只捕捉全局性质。 Yu 等人 提出了相似的方法。他们生成从对象到包围球面的距离图,事先仍然需要进行姿态规整化,还对这些距离图应用快速傅利叶变换 FFT 来处理姿态规整化中的错误对齐。这些图的规整化的加权欧式距离用于相似度计算。 作者在由 34 个类、 52 个模型的数据库上进行了实验,但没与其他方法进行对比。 加权点集 这些方法从形状生成点集,按某种方式进行加权,并采用不同方法计算相似度。 Tangelder 和 Veltkamp 提出三种不同的生成加权点集的方法。将姿态规整化后的 3D 多边形网格放置在 3D 网格中。每个非空网格单元包含一个显著点。显著点的选取和加权有不同的方式:( 1 )选取高斯曲率最高的点,并将曲率值作为点的权值,( 2 )选择按面积加权的顶点的均值点,将面的法向方差作为权值,( 3 )计算所有顶点的质心,并赋权值为 1 。 他们采用地面移动距离的变种来进行相似度度量,使其满足三角不等性。作者表示他们的方法由于形状分布的方法。 4.1.1.2 局部形状描述子 这些方法考虑表面上邻居点之间的局部性质。曲率是局部性质的一个例子,在全局方法中也被用于表示上下文信息。在上下文环境中,将所有局部性质组合起来,可以作为形状的全局描述子。 这里我们不考虑组合局部性质的方法,因此可以进行局部匹配。同时这些方法的描述能力更好,因为虽然有些耗时,但它们可以捕捉形状的细节信息。该类方法多用于聚类环境中的对象识别和表面注册问题,也有一些已用于 3D 形状检索。这些方法不需要预先进行姿态规整化。 Johnson 和 Hebert 提出了旋转图像方法。旋转图像是在模型表面某点处计算的 2D 直方图。对一个网格模型,可对网格的每个顶点检索旋转图像。表面法线可在选定作为定向点的顶点处进行估计。与定向点距离 D 最大的点集中,满足其法线和定向点法线之间夹角在允许范围内的点将作为候选点。 2D 直方图则根据到表面法线和定向点处切平面的垂直距离进行计算。该直方图可用作图像。作者给出了聚类场景中的对象识别算法。 De Alarcon 等人 将旋转图像用于 3D 形状检索。对多边形 3D 网格,生成大量的旋转图像,并应用自组织映射 SOM 算法生成旋转图像的简化集合。此外,他们还采用 k 均值聚类方法对旋转图像进行聚类,以对数据库进行索引。作者在小数据库上进行了实验。 Yamany 等人 的方法捕捉表面上某点的曲率,并为每个点生成表面签名图像。该方法用于表面注册。他们发现为了对齐表面,至少需要对模型的三个对应点进行表面签名匹配并对其参数进行相似度变换。 Kortgen 等人 将 Belongie 等人 提出的 2D 形状上下文扩展到 3D 形状上下文。他们对表面上的 N 个点计算直方图。某采样点的直方图包含其余 N-1 个点的坐标。根据采样点集的大小,该方法的局部描述功能也不同。他们的分级方法将空间分解为壳或扇区。形状匹配则通过比较形状上下文来寻找模型上的对应点。 4.1.2 结构和拓扑技术 3D 形状的几何特性无法表达形状的语义。他们描述形状的全局或局部特性,却无法表达形状各部分之间的关系,也无法区分拓扑不同的形状。例如,采用拓扑方法可以方便地区分圆环和球面。同样,拓扑相似而几何不同的形状有时需要被分成一类。例如,不同种类的桌子应属于一类。长方形或圆形桌面、三条腿或四条腿的桌子尽管几何不相似,但确实拓扑相似的。 结构描述子更加直观,但匹配却比几何方法耗时。他们比几何方法的优势在于可以进行局部匹配。 表面透射图 Yu 等人 通过将模型变形到球面来抽取拓扑信息,这称作表面透射图,基本思想为:假设从模型中心发出射线到其包围球,则将根据模型的拓扑和凹度穿透一个或多个表面。包围球被分为多个扇区,并计算每个扇区射线穿透表面的平均值。作者没有与其他方法进行对比。 图结构 Hilaga 等人 提出了拓扑匹配的方法。他们构建多分辨率 Reeb 图( MRG )来匹配 3D 模型。 Reeb 图是对象上连续标量函数的骨架,作者采用测地距离分布作为连续函数。该方法对回转形状同样有效。 Tung 和 Schmit 加入体积和曲率对 Reeb 图进行扩展。因为在人体匹配中,仅采用拓扑相似,无法区分胳膊和腿。 Sundar 等人 采用骨架图匹配 3D 模型。他们同时利用了拓扑和几何信息,生成 3D 模型骨架也有很多方法。作者采用基于参数的细化算法抽取体素 3D 模型。模型各部分的骨架图也包括半径等几何信息。 关系结构 3D 模型可看作一系列单元何其关系的组合。每个单元可由面积、半径等几何属性描述。由关系匹配得到的检索框架由 Vosselman 给出。同时 Haralick 和 Shapiro 给出了基于关系距离定义的一致标记框架。 4.2 基于视图的技术 在利用 3D 几何或结构的同时, 3D 形状的外观或视图也可用于形状描述,其基本思想是相似的物体在各个角度上看起来都是相近的,已有一些相关研究。本节将介绍采用 3D 模型的视图来进行模型的相似度匹配。 Chen 等人 提出了基于光场的方法。光场为一个五维的函数,表示给定 3D 点在给定方向上的半径。对平移和缩放无关的 3D 模型,他们在近似包围球上均匀取 10 个点,并创建其轮廓生成光场。结合使用面积的 Zernike 矩(基于区域的描述子)和边界的傅立叶变换(基于轮廓的描述子)作为每个轮廓的 2D 描述子。这十个不同旋转球面产生十个光场的集合将保存下来。设 a 、 b 为待比较的两个模型,则相似度度量定义如下: 其中 I a ik ,I b ik 为轮廓的 2D 描述子,距离 d 为 L1 范式。 作者将他们的方法与 Funkhouser 提出 提出的 3D 球谐函数方法做比较,并说明他们的方法的处理效率较高。 Obhuchi 等人 提出应用于多边形 soup 3D 模型的方法。这些模型是平移和缩放无关的。他们计算 N=42 个深度的渲染图像,基本上包含了模型的所有视图。再对每幅图像应用傅立叶变换作为 2D 描述子。总共 42 个描述子形成 3D 模型的形状描述子。设 a 、 b 为待比较的两个模型,则相似度度量定义如下: 其中 I a i , I b j 为 2D 描述子,距离 d 为 L 1 范式。 因为所有的旋转是无序的,相似度度量比较所有可能的对并选取最小的 L 1 距离用来计算所有的 42 的视图。 5 、 3D 模型搜索引擎分析 前面的章节讲述了数字世界中 3D 模型的表示、相似度和匹配的概念以及 3D 形状检索技术。本节给出概念框架,将这些模块组合到一起形成 3D 形状搜索引擎。 3D 形状搜索引擎的主要组件是模型数据库。模型可表示为不同形式,例如多边形网格、多边形 soup 、体素模型。数据库可以针对领域的,例如 CAD 模型,或包含各种模型。除了名字之外,模型还可以包含文本描述。 对用户最重要的组件是查询界面,可有不同的形式: 用户提供 3D 模型,检索所有相似的模型。 草绘 3D 草图,检索相似的模型。 草图一个或多个 2D 视图,检索相似的模型。 用户还可以加入文本描述进行搜索,例如汽车。 由于模型本身不适用于匹配,需要创建简化的形状描述子,这些描述子通常预先离线创建。因此相似度匹配可以达到在线情况下的实时性。描述子也可以建立索引,提高检索的效率。下图给出了概念框架的各个组件 : 图 5.1: 概念 3D 形状搜索引擎框架图 6 、 3D 形状检索性能和相关问题 前面我们给出了基于形状的 3D 模型检索的方法,本章将更加细致地讨论这些系统的性能。 本章的结构是: 6.1 节对 3D 模型搜索系统的检索性能做综述。 6.2 节给出检索中主观评价的方法。多数系统采用形状等底层特征进行相似度匹配,但语义特征同样不能被忽略。因此,需要将用户的喜好加入相似度匹配。 6.3 节提出根据查询选择最佳的形状描述子。 6.1 性能评估和 Benchmarking 多数 3D 形状检索检索的性能通过结果与预定义分类之间的相近程度来评估。因为数据库随不同的系统分类而不同,需要一个统一的框架来比较不同的匹配算法。普林斯顿的形状 Benchmark 对此做出了贡献,它提供了不同类别的测试数据库,还附带一些比较检索性能的工具。 如果匹配算法通过计算形状之间的距离大小来进行匹配,通常有一些性能度量方法。 给定形状匹配算法和 3D 模型 (M = {m 1 ;m 2 ; :::;m N }), 可以计算模型之间的距离。对任意模型 q M ,可根据距离矩阵选择 k 个最相似的模型。 以下是评价 3D 形状检索性能的量化方法: 最匹配的图像根据相似度递减的顺序排列。 查准率 - 查全率图 距离图像 等级图像 6.2 主观检索 3D 模型搜索系统抽取底层的形状特征,但它们无法捕捉形状的语义。用户对形状的理解包括形状和语义两方面,同时每个人对语义的理解也可能不同。一个成功的搜索引擎应该能够适应用户的喜好。本节对这些方法做介绍。 Suzuki 等人 创建了对象特征框架 OFS 和用户喜好框架 UPS 并建立两者之间的映射。在特征抽取阶段,他们只考虑多边形网格的顶点,生成模型的规整化包围立方体,并将其分割为单位单元。最后,每个立方体内规整化顶点的个数即作为模型的特征向量。 算法其余部分如下 : 1. 选择数据库中的模型子集(训练集),要求用户提供这些模型的相似度,为每个用户建立相似度矩阵 2. 采用多维缩放 MDS 对上一步中建立的相似度矩阵进行降维。这是用户喜好空间。 3. 对不属于训练集中的模型进行预测。采用多元回归分析建立对象特征空间到每个用户的喜好空间的映射。 Elad 等人 提出循环优化算法允许用户标记相关和不相关的结果来调整距离度量函数。他们采用的特征是规整化矩,并采用加权欧式距离进行相似度度量。 用户反馈通过修改距离度量的权重是结果靠近相关匹配而远离不相关的匹配。支撑向量机 SVM 被用于训练距离函数的权重。这样,系统学习不同用户的主观相似度度量方式。 Zhang 和 Chen 提出主动式学习的概念将语义特征融合到检索过程。他们采用的底层特征是体表面纵横比、不变矩和傅利叶系数。 该系统采用汽车、身体、飞机等 53 个预定义的属性,对每个对象计算其属于每种属性的概率。训练过程中,随机选择若干模型给用户进行标记。用户判断对象是否具有某种属性,给出 0 或 1 的赋值,这称作隐式标注。因为无法收到标注所有模型,系统将估计其余模型的概率。作者采用有偏核回归技术估计未标注样本的概率。有偏估计表示如果一个对象远离标注的模型,则不应受某种标记的影响。 下一步即从数据库中选择最不确定的模型,并要用户进行标注。这采用知识增益进行判断,主要目的是降低数据库的不确定性。 检索过程采用底层特征的加权距离度量和基于模型概率的语义相似度度量。系统性能随标注模型的数量增多而提高。 6.3 形状描述子选择 前面介绍了匹配和检索 3D 形状的方法,以及比较不同形状描述子的性能评估方法和 benchmarking 技术。 本节将形状描述子选择问题看作模式识别环境下的特征子集选择问题。每个形状描述子被看作一种特征,多种特征组合可进行形状检索,问题是如何进行组合以取得最好的检索效果。 本文介绍文献中包含的两种形状描述子选择方法。 Vandeborre 等人 从多边形网格模型生成三种形状描述子(特征),包括:由每个网格面住曲率直方图组成的曲率索引,面之间的距离直方图(距离索引),和每个面的体积直方图(体积索引)所以特征对欧式变换无关。他们采用 L1 范式度量相似度,模型数据库包括飞机、汽车、鱼、象棋等类别。 作者提出两种方法组合形状描述子: 将结果集中对象的排名的曲率、距离和体积索引表示为 Rc , Rd 和 Rv 。 N 为每个查询检索到的模型, F 表示某种特征组合模式下,检索到模型与查询的相关程度。 ? OR 方法: ? MEAN 方法: 上述方法返回 0 到 1 之间的实数值,因此可根据 F 的大小选择最佳的 N 个匹配。 实验表面组合的形状描述子比单独使用其中任何一种的效果都要好。 Bustos 等人 采用基于熵不纯度的方法进行特征选择。 数据库中包括 1838 个 3D 模型,其中 292 个被预分类成汽车、飞机、海洋生物等。分类后的模型用作查询检索其同类的模型。模型特征向量之间的 L1 范式用于相似度度量。 检索的有效性通过结果集的一致性进行评估。查询应返回同类的模型,有些特征的区分性可能好于其他特征,特征组合一般会取得比较好的效果。其出发点是没有一种特征抽取可以对每种查询都有效,例如有效对汽车模型描述效果好,其他则对海洋生物效果好。 作者实现了 15 种特征抽取技术,并表示为特征向量。其共性是他们都描述了 3D 形状的全局特征,表 6.1 给出了这些特征和其出处。 方法 引用 深度缓存 Heczko 等人 体素 Heczko 等人 轮廓 Heczko 等人 体积 Heczko 等人 阴影 Vranic 和 Saupe 3D 谐波 Funkhouser 等人 形状复合函数 Vranic and Saupe 球谐射线 Vranic and Saupe 弦 Paquet et al. 矩 Paquet et al. D2 形状分布 Osada et al 3D FFT Vranic and Saupe 基于射线的方法 Vranic and Saupe 关系无关特征 Kato et al. 形状图谱 Zaharia and Preteux 表 6.1: Bustos 等人抽取的特征种类 . 作者采用熵不纯度度量来估计每种特征的性能,实验表面熵不纯度比 Gini 和误分类不纯度的效果要好。 他们开发了两种方法:独立于查询的特征选择和组合。 设 U 为 3D 模型空间, M 为 U 的有限模型子集(数据库)。对每个模型 m M ,都对应类别 c1; c2; :::; cN ,且 。 设 q U 为查询模型。对特征抽取函数 f , R q f 为按照 d(f(q),f(r)) 升序排列的模型序列,其中 d 为 L1 范式距离度量, q 为查询模型, r 为检索到的模型。 设 P k (c n , R q f ) 为类 cn 中属于 R q f 前 k 个模型的比例。 ? 最佳特征抽取选择的熵不纯度度量 搞定查询 q ,特征抽取函数 f 的 k 熵不纯度为: 若所有 k 个结果属于同一类,则 k 熵不纯度为 0 。当结果集合中不同类别的数目达到最大是,熵不纯度取得最大值。 最佳特征抽取函数根据下式选择: 其中 F ={f1; f2; :::; fT} 为特征抽取函数集合。 ? 最佳特征抽取组合的熵不纯度度量 这里选择查询 q 的最佳特征组合,而不是最佳特征抽取函数 f 。作者采用上述 k 熵不纯度进行特征函数的加权组合。不纯度值越小则权值越大, 并根据 k 熵不纯度建立查询 q 和对象 o U 之间新的距离度量函数如下: 其中 i(f t ,q,k) 为特征抽取函数 f t 和查询模型 q 的 k 熵不纯度。 D max t 为 q 到数据库中模型的最大距离( L1 范式)。 d t (q,o) 为 q 到模型 o 的距离。根据距离 d (q,o) 对结果进行排序。 作者采用查准率 P 和查全率 R 图对各种特征抽取方法和 k 熵不纯度的最佳特征效果进行对比。同样,也用 PR 图对特征组合结果进行评价。结果表面,特征组合可以提高 30% 左右的性能。 下图为查询的一个例子,采用赛车模型作为查询,给出了深度缓存、轮廓以及两者组合的检索效果。 图 6.1: 采用深度缓存、轮廓以及两者组合的查询结果 (Bustos 等人 ) 但这种方法需要手动对数据库中的对象进行分类。对未分类的数据库,则需要预先进行分类处理。如果不知道数据库的规模,可以通过聚类算法等非监督学习技术。但分类有很多方法,也可以考虑主观信息。例如纯基于形状的聚类可能将不相关的模型分为一类,比如导弹和笔。因此需要其他的成组方法,比如基于模型功能的费力或其他相关的文本信息。 参考文献 Mihael Ankerst, Gabi Kastenmuller, Hans-Peter Kriegel, and Thomas Seidl. 3d shape histograms for similarity search and classi_cation in spatial databases. In Ralf Hartmut Guting, Dimitris Papadias, and Frederick H. Lochovsky, editors, Advances in Spatial Databases, 6th International Symposium, SSD'99, Hong Kong, China, July 20-23, 1999, Proceedings, volume 1651 of Lecture Notes in Computer Science, pages 207-226. Springer, 1999. I. Atmosukarto and P. Naval. A survey of 3d model retrieval systems. not published, N/A 2003. not published. B. Bustos, D. Keim, D. Saupe, T. Schreck, and D. Vrani_c. Using entropy impurity for improved 3d object similarity search. In Proc. IEEE International Conference on Multimedia and Expo (ICME'04), 2004. P. J Besl and N. D. MacKay. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239-256, 1992. M. Bennamoun and G. J. Mamic. Object recognition: fundamentals and case studies. Springer- Verlag New York, Inc., 2002. Serge Belongie, Jitendra Malik, and Jan Puzicha. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(24):509-522, April 2002. Richard J. Cambell and Patrick J. Flynn. A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding, (81):166-210, 2001. Yang Chen and G_erard Medioni. Description of complex objects from multiple range images using an inating balloon model. Computer Vision and Image Understanding: CVIU, 61(3):325-334, 1995. De-Alarcon, Pascual-Montano PA, and JM Carazo. Spin images and neural networks for e_cient content-based retrieval in 3d object databases. In CIVR, 2002. Yu-Te Shen Ding-Yun Chen, Xiao-Pei Tian and Ming Ouhyoung. On visual similarity based 3d model retrieval. In Computer Graphics Forum (EUROGRAPHICS'03), volume 22, pages 223-232, September 2003. P. Daras, D. Zarpalas, D. Tzovaras, and M.G. Strintzis. Shape matching using the 3d radon transform. In 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004, pages 953{960, september 2004. Michael Elad, Ayellet Tal, and Sigal Ar. Directed search in a 3d objects database using svm. Technical report, HP Laboratories, Israel, 2000. M. Elad, A. Tal, and S. Ar. Content based retrieval of vrml objects-an iterative and interactive approach. Eurographics Multimedia Workshop, pages 97{108, 2001. Thomas Funkhouser and Michael Kazhdan. Shape based retrieval and analysis of 3d models. Siggraph2004 Course 15, 2004. Thomas Funkhouser, Patrick Min, Michael Kazhdan, Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs. A search engine for 3d models. ACM Trans. Graph., 22(1):83{105, 2003. M. Heczko, Keim, D. D., Saupe, and D. V. Vranic. Verfahren zur hnlichkeitssuche auf 3dobjekten. In Datenbank Spektrum Zeitschrift fr Datenbanktechnologie, volume 2, pages 54-63, 2002. Robert M. Haralick and Linda G. Shapiro. Computer and Robot Vision. Addison-Wesley Longman Publishing Co., Inc., 1993. Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L. Kunii. Topology matching for fully automatic similarity estimation of 3d shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 203{212. ACM Press, 2001. Hiroyasu Ichida, Yuichi Itoh, Yoshifumi Kitamura, and Fumio Kishino. Interactive retrieval of 3d virtual shapes using physical objects. In IEEE Virtual Reality, 2004. N. Iyer, K. Lou, S. Janyanti, Y. Kalyanaraman, and K. Ramani. Three dimensional shape searching : State-of-the-art review and future trends. Computer Aided Design, 2004. Cheuk Yiu Ip, Daniel Lapadat, Leonard Sieger, and William C. Regli. Using shape distributions to compare solid models. In Proceedings of the seventh ACM symposium on Solid modeling and applications, pages 273{280. ACM Press, 2002. Anil J. Jain and Chitra Dorai. 3d object recognition: Representation and matching. Statistics and Computing, (10):167{182, 2000. A.E Johnson and M. Hebert. Using spin images for e_cient object recognition in cluttered 3d scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5):433{449, May 1999. A. Young J. Park, D. Mataxas and L. Axel. Deformable models with parameter functions for cardiac motion analysis from tagged mri data. IEEE Transactions on Medical Imaging, 15:278{ 289, 1996. J. J. Koenderink and A. J. van Doorn. The internal representation of shape with respect to vision. In Biological Cybernetics, volume 32, pages 211{216, 1979. D.G. Kendall, Barden D., Carne T.K., and Le H. Shape and Shape Theory. Wiley Series in Probability and Statistics, 1999. Michael Kazhdan, Thomas Funkhouser, and Szymon Rusinkiewicz. Rotation invariant spherical harmonic representation of 3d shape descriptors. In Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 156{164. Eurographics Association, 2003. Keitaro Kaku, Yoshihiro Okada, and Koichi Niijima. Similarity measure based on obbtree for 3d model search. In International Conference on Computer Graphics, Imaging and Visualization (CGIV'04), volume I, pages 46{51, july 2004. M. Kortgen, G.J Park, M. Novotni, and R. Klein. 3d shape matching with 3d shape contexts. The 7th Central European Seminar on Computer Graphics, April 2003. Toshikazu Kato, Motofumi T. Suzuki, and Nobuyuki Otsu. A similarity retrieval of 3d polygonal models using rotation invariant shape descriptors. In IEEE International Conference on Systems, Man, and Cybernetics (SMC2000), pages 2946{2952, 2000. G. Leifman, S. Katz, A. Tal, and R. Meir. Signatures of 3d models for retrieval. 4th Israel Korea Bi-National Conference on Geometric Modeling and Computer Graphics, pages 159{163, 2003. A. Witkin M. Kass and D. Terzopoulos. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321{331, 1987. Bruce Naylor. Representations of geometry for computer graphics. In Siggraph 1996 Course Notes, 1996. M. Novotni and R. Klein. 3d zernike descriptors for content based shape retrieval. Solid Modeling, 2003. Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. Shape distributions. ACM Transactions on Graphics, 21(4):807{832, October 2002. Ryutarou Ohbuchi, Takahiro Minamitani, and Tsuyoshi Takei. Shape-similarity search of 3d models by using enhanced shape functions. In Proceedings of the Theory and Practice of Computer Graphics 2003, page 97. IEEE Computer Society, 2003. Ryutarou Ohbuchi, Masatoshi Nakazawa, and Tsuyoshi Takei. Retrieving 3d shapes based on their appearance. Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, pages 39{45, 2003. Ryutarou Ohbuchi, Tomo Otagiri, Masatoshi Ibato, and Tsuyoshi Takei. Shape-similarity search of three-dimensional models using parameterized statistics. In Proceedings of the 10th Paci_c Conference on Computer Graphics and Applications, page 265. IEEE Computer Society, 2002. D. L. Page, A. F. Koschan, J. K. Paik, and M. A. Abidi. Shape analysis algorithm based on information theory. In Proceedings of the International Conference on Image Processing, volume I, pages 229{232, 2003. E. Paquet, A. Murching, T. Naveen, A. Tabatabai, and M. Rioux. Description of shape information for 2-d and 3-d objects. In Signal Processing: Image Communication, volume 16, pages 103{122, 2000. A. R. Pope. Model-based object recognition: A survey of recent research. Technical report, Univ. of British Columbia, 1994. P. Shilane, M. Kazhdan, P. Min, and T. Funkhouser. The princeton shape benchmark. SMI, 2004. Motofumi T. Suzuki, Toshikazu Kato, and Hideo Tsukune. 3d object retrieval based on subjective measures. In Proceedings of the 9th International Workshop on Database and Expert Systems Applications, page 850. IEEE Computer Society, 1998. Linda G. Shapiro and George C. Stockman. Computer Vision. Prentice Hall, 2001. H. Sundar, D. Silver, N. Gagvani, and S. Dickinson. Skeleton based shape matching and retrieval. In Shape Modeling International, 2003, 2003. T.Tung and F.Schmitt. Augmented reeb graphs for content-based retrieval of 3d mesh models,. In International Conference on Shape Modeling and Applications (SMI'04), pages 157{166, 2004. J. Tangelder and R. Veltkamp. Polyhedral model retrieval using weighted point sets. Int. Journal of Image and Graphics, 3(1), pp. 209-229 (2003)., 2003. Johan W. H Tangelder and Remco C. Veltkamp. A survey of content based 3d shape retrieval methods. Shape Modeling Conference, 2004. Jean-Philippe Vandeborre, Vincent Couillet, and Mohamed Daoudi. A practical approach for 3d model indexing by combining local and global invariants. In 1st International Symposium on 3D Data Processing Visualization and Transmission, pages 644{647, 2002. R.C Veltkamp. Shape matching: Similarity measure and algorithms. In Proceedings Shape Modelling International, pages 188{197, 2001. G. Vosselman. Relational Matching. Lecture Notes in Computer Science, vol. 628, Springer Verlag., 1992. D. V. Vranic and D. Saupe. 3d model retrieval. In Proceedings Spring Conference on Computer Graphics 2000(SCCG2000), Budmerice, Slovakia, may 2000. D. V. Vranic and D. Saupe. 3d shape descriptor based on 3d fourier transform. In Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services(ECMCS 2001),Budapest, Hungary, pages 271{274, september 2001. D. V. Vranic and D. Saupe. Description of 3d-shape using a complex function on the sphere. In Proceedings IEEE International Conference on Multimedia and Expo, Lausanne, Switzerland, pages 177{180, August 2002. M. Yu, I. Atmosukarto, W. K. Leow, Z. Huang, and R. Xu. 3d model retrieval with morphingbased geometric and topological feature maps. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 2003. Sameh M. Yamany and Aly A. Farag. Free-form surface registration using surface signatures. In Proceedings of the International Conference on Computer Vision-Volume 2, page 1098. IEEE Computer Society, 1999. C. Zhang and T. Chen. E_cient feature extraction for 2d/3d objects in mesh representation. CIP, 2001. C. Zhang and T. Chen. An active learning framework for content based information retrieval. Technical report, CMU, 2002. D. S. Zhang and G. Lu. Review of shape representation and description techniques. Pattern Recognition, 37(1):1{19, 2004. T. Zaharia and F. Preteux. Hough transform-based 3d mesh retrieval. In Proceedings of SPIE 4476 on Vision Geometry X, San Diego, USA, august 2001. Dennis Zorin and Peter Schroder. Subdivision for modeling and animation. In Siggraph 1999 Course Notes, 1999. ( http://www.graphics.stanford.edu/data/mich ) ( http://www.formaurbis.stanford.edu/index.html ) ( http://edge.mcs.drexel.edu/repository/frameset.html ) ( http://www.rcsb.org/pdb ) ( http://www.viewtec.ch/meddiv/hugo_e.html ) ( http://www.nlm.nih.gov/research/visible/visible_human.html ) ( http://marathon.csee.usf.edu/range/DataBase.html ) ( http://sampl.eng.ohio-state.edu/~sampl/data/3DDB/RID/minolta/angel.0699/index.html )