精华内容
下载资源
问答
  • 关系数据库数据的逻辑结构是一张扁平的二维表。 1.域(domain) 定义2.1 域是一组具有相同数据类型的值的集合。 2.笛卡尔积(cartesian product) 定义2.2 给定一组域Di , D2 , …,Dn , 允许其中某些域是相同...

    系统讲解关系数据库的重要概念,包括关系模型和关系代数.


    2.1 关系数据结构及形式化定义

    2.1.1关系

    关系数据库中数据的逻辑结构是一张扁平的二维表。

    1.域(domain)

    定义2.1 域是一组具有相同数据类型的值的集合。

    2.笛卡尔积(cartesian product)

    定义2.2 给定一组域Di , D2 , …,Dn , 允许其中某些域是相同的, Di , Di, …, Dn,笛卡儿积为
    D1 xD2 x … xDn= {(di , d2, ···, dn ) l di∈Di, i=1, 2, …,n}
    其中, 每一个元素(di , d2 , …, dn) 叫作一个n 元组(n-tuple), 或简称元组(tuple)。元素中的每一个值di叫做一个分量(component)。

    一个域允许的不同取值个数称为这个域的基数(cardinal number)。

    3. 关系(relation)

    定义2.3 D 1xD 2 X … xD n 的子集叫做在域D1, D2, …, D n 上的关系,表示为
    R(D1, D2, ···D,n)
    这里R表示关系的名字,n是关系的目或度(degree)。
    关系中的每个元素是关系中的元组,通常用t表示。

    若关系中的某一属性组的值能唯一地标识一个元组,而其子集不能,则称该属性组为候选码(candjdate key)。
    若一个关系有多个候选码,则选定其中一个为主码(primary key)。
    候选码的诸属性称为主属性(prime attribute)。不包含在任何候选码中的属性称为非主属性(non-prime attribute)或非码属性(non-key attribute)。

    关系可以有三种类型:基本关系(通常又称为基本表或基表)、查询表和视图表。其中,基本表是实际存在的表,它是实际存储数据的逻辑表示:查询表是查询结果对应的表;视图表是由基本表或其他视图表导出的表,是虚表,不对应实际存储的数据。

    规范条件中最基本的一条就是,关系的每一个分星必须是一个不可分的数据项。规范化的关系简称为范式(Normal Form, NF)。

    2.1.2 关系模式

    定义2.4 关系的描述称为关系模式(relation schema) 。它可以形式化地表示为
    R(U,D,DOM , F)
    其中R 为关系名,U 为组成该关系的属性名集合,D 为U 中属性所来自的域,D O M 属屈性向域的映像集合,F为属性间数据的依赖关系集合。

    2.1.3 关系数据库

    2.1.4 关系模型的存储结构


    2.2 关系操作

    2.2.1 基本的关系操作

    查询(query)操作和插入(insert)、删除(delete)、修改(update)

    查询操作又可以分为选择(select)投影(project)连接(join)除(divide)并(union)差(except)交(intersection)、笛卡儿积等。

    2.2.2 关系数据语言的分类


    2.3 关系的完整性

    关系模型中有三类完整性约束:实体完整性(entity integrity)、参照完整性(referential integrity)和用户定义的完整性(user-defined integrity)。

    2.3.1 实体完整性

    规则2.1 实体完整性规则 若属性(指一个或一组属性)A是基本关系R的主属性,则A不能取空值(null value)。所谓空值就是“不知道” 或“不存在” 或“无意义” 的值。

    2.3.2 参照完整性

    定义2.5 设F 是基本关系R 的一个或一组属性,但不是关系R 的码,凡是基本关系S 的主码。如果F 与凡相对应,则称F 是R 的外码(foreign key), 并称基本关系R 为参照关系(referencing relation), 基本关系S 为被参照关系(referenced relation) 或目标关系
    (target relation) 。关系R 和S 不一定是不同的关系。

    规则2.2 参照完整性规则若属性(或属性组)F是基本关系R的外码,它与基本关系S 的主码K 相对应( 基本关系R 和S 不一定是不同的关系),则对于R 中每个元组在F上的值必须:

    • 或者取空值(F的每个屈性值均为空值);
    • 或者等于S中某个元组的主码值。

    2.3.3 用户定义的完整性


    2.4 关系代数

    关系代数是一种抽象的查询语言,它用对关系的运算来表达查询。

    关系代数的运算按运算符的不同可分为传统的集合运算和专门的关系运算两类。

    2.4.1 传统的集合运算

    (1)并(union)
    关系R 与关系S 的并记作
    R U S = {t | t∈R ∨ t∈S}
    其结果仍为n目关系,由属于R或屈千S的元组组成。
    (2)差(except)
    关系R 与关系S 的差记作
    R-S = {t | t∈R ∧ t∉S}
    其结果关系仍为n目关系,由屈千R而不属千S的所有元组组成。
    ( 3 ) 交(intersection)
    关系R 与关系S 的交记作
    R n S = {t | t∈R∧ t∈S}
    其结果关系仍为n目关系,由既属千R又属千S的元组组成。关系的交可以用差来表示,
    即R n S = R - (R -S)。
    (4)笛卡儿积(cartesian product)
    这里的笛卡儿积严格地讲应该是广义的笛卡儿积(extended cartesian product), 因为这
    里笛卡儿积的元素是元组。
    两个分别为n 目和m 目的关系R 和S 的笛卡儿积是一个(n + m ) 列的元组的集合。元
    组的前n 列是关系R 的一个元组,后m 列是关系S 的一个元组。若R 有幻个元组,S 有
    k2 个元组,则关系R 和关系S 的笛卡儿积有k1Xk2 个元组。记作
    RxS={t,.t slt, ER/\t s ES}

    展开全文
  • 做过类似项目的同学,应该知道此类项目好友之间的关系设计比较复杂,如果用传统的关系型数据库来设计,比如MySQL,那好友之间的关系需要用一张中间来表示,如下所示: user_id follow_id 1 5 ...

    一、引言

    大家都用过各种各样的社交软件,像国人用的最多的就是QQ、微信、微博等,国外用的多的就是推特、脸书等,这些社交软件都是建立在人与人相互之间关系的基础上。

    做过类似项目的同学,应该知道此类项目中好友之间的关系设计比较复杂,如果用传统的关系型数据库来设计,比如MySQL,那好友之间的关系需要用一张中间表来表示,如下表所示:

    user_id follow_id
    1 5
    2 3
    3 4
    4 4
    5 2

    上面这个好友关系表你可以把它看成一个二维矩阵,其实就是我们前面所学数据结构中的图。图实际上研究的是由顶点和边组成的一种数学模型,这种数学模型非常抽象,并且看起来也很枯燥。虽然图论看起来很枯燥,但是如果大家真正的深入研究下去,就会发现图论是一个非常酷的学科。世界中很多的信息之间的联系,都可以使用图这种抽象的数学方式来进行表示,如下就是表示互联网之间关系的连接图。

    二、图对现实生活的表述

    以图作为模型,来表示真实世界之间的关系,那么可以表示什么样的关系呢?

    1.交通运输

    最典型的莫过于交通运输,它可以使用图来表达,如:每个顶点可以是一个城市,每条边可以是城市之间的道路再扩展一下,每个顶点可以是一个航站楼,每条边可以是相应的航线,每个顶点可以是港口,每条边可以是相应的海运线甚至更宏观的,每个顶点可以是一个星球,每条边可以是星球之间宇宙飞船飞行的航线,亦或更微观的,每个顶点可以是城市中的一座楼,每条边可以是楼和楼之间的街道。如上,都是可以的,这是对于图来说,最直观的一种表示方式,但是,其实很多更抽象的数据关系,也可以用图来表示。

    2.社交网络

    对于社交网络来说,每个顶点可以表示一个人,每条边可以表示

    人与人之间的关系。这种关系可以是像 FaceBook 这种好友的关

    系,也可以是像 Twitter 这种关注的关系。

    3.相似关系   

    每个顶点可以表示一部电影,每条边可以表示两部电影之间的相似程度

    4.互联网

    互联网,也可以用图来表示,每个顶点可以表示一个域名,每条边可以表示域名之间的跳转或 每个顶点可以表示一个页面,每条边可以表示页面之间的连接

    5.工作安排

    在工作中的工作安排,也可以用图来表示,每个顶点可以是一个工作内容,每条边可以是两个工作内容之间的相关程度,或 先后执行的优先级顺序。

    6.脑区活动

    像脑区活动的研究这样更复杂、更专业的领域,也经常用到图,每个顶点可以是一个脑区,每条边可以是脑区之间信息的传递。

    7.程序状态执行

    在计算机程序中,程序状态的执行,也可以用图来表示,每个顶点可以表示一个程序状态,每条边可以表示从一种状态执行到另外一种状态。对于这种情况,最典型的一个应用就是自动机,包括制作专业的编译器,甚至是做一个游戏,都可能要设计一个自动机。在这种情况下,或多或少都会使用图论建模的方法。

    三、大数据集下图算法的作用

    经过前面的分析,我们看到图的作用非常大,在一个最简单的模型中,我们可以把图放在传统的关系型数据库中,也可以使用SQL语句对好友关系数据进行查询。但是像微博、微信这种体量的应用,如果还是继续使用传统数据库,那查询效率会很低,所以我们可以使用专业的图数据库来进行保存。

    1.使用图保存数据的方式

    邻接矩阵(Adjacency Matrix)

    用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。对无向图(无向简单图)而言,邻接矩阵一定是对称的,而且对角线一定为零,有向图则不一定如此。

    邻接表(Adjacency List)

    邻接表描述一种紧密相关的数据结构,用于表征图。在邻接表的表示中,对于图中的每个顶点,我们将保存所有其它与之相连的顶点(即“邻接表”)。例如,由吉多·范罗苏姆提出的,使用哈希表将每个顶点和该顶点的邻接点数组关连起来,就可以看作是上述表示方法的一种实现。又如,在Cormenetal中,顶点数组的每个元素都指向一个邻接点单链表

    2.使用图算法进行查询

    不同图算法的时间复杂度是不同的,我们分别来看几种常见的图算法以加深印象。

    • 深度优先搜索
    • 广度优先搜索
    • A*搜索算法:启发式算法
    • 最短路径算法:Dijkstra、Bellman-Ford、Floyd-Warshall
    • 最小生成树 :Prim、Kruskal

    以上这些算法都比较常见,会在后文一一介绍。


    我的微信公众号:架构真经(关注领取免费资源)

    参考文章

    1. https://www.cnblogs.com/wuhan729/p/8481498.html
    2. https://blog.csdn.net/qq_25800311/article/details/89810843
    3. https://blog.csdn.net/simanstar/article/details/78906825
    展开全文
  • 聊聊数据仓库维度设计的三事

    多人点赞 热门讨论 2020-11-21 21:48:57
    维度表是维度建模的灵魂,在维度表设计碰到的问题(如维度变化、维度层次、维度一致性、维度整合和拆分等)都直接关系到维度建模的好坏,因此良好的维表设计就显得至关重要,今天我们就一起来探究下关于维表设计的...

    前言

    大家好,我是云祁!今天和大家聊聊数据仓库中维度表设计的那些事。

    维度表是维度建模的灵魂所在,在维度表设计中碰到的问题(比如维度变化、维度层次、维度一致性、维度整合和拆分等)都会直接关系到维度建模的好坏,因此良好的维表设计就显得至关重要,今天就让我们就一起来探究下关于维表设计的相关概念和一些技术。

    维度变化

    维度表的数据通常来自于前台业务系统,比如商品维度表可能来自于 ERP 或者超市 POS 系统的商品表,但商品是会发生变化的,比如商品所属的类目 、商品标签价格、商品描述等,这些变化有可能是之前有错误需要订正所致的,或者是实际的业务情况变化。

    不管哪种情况,维度设计过程中,确定源头数据变化在维度表中如何表示非常重要。因此在维度建模中,这一现象称为缓慢变化的维度,简称 缓慢变化维(slowly changing dimension, SCD)。

    根据变化内容的不同,下游的分析可能要求用不同的办法来处理

    比如对于商品的描述信息,也许业务人员对此并不敏感,或者认为无关紧要,这种情况可以直接覆盖 。

    但是对于商品所属的类目发生变化,则需要认真考虑, 因为这涉及归类这个商品的销售活动到哪个类目一一是全部归到新类目,还是全部归到旧类目?变化前归到旧类目,还是变化后归到新类目?这实际上也涉及了下面要分享的缓慢变化维的几种处理办法。

    1. 重写维度值

    当一个维度值属性发生变化时,重写维度值方法直接用新值覆盖旧值。

    该技术适用于维度建模中不需要保留此维度属性历史变化的情况,常用于错误订正或者维度属性改变无关紧要的场景,比如用户的生日之前发生输入错误,不需要保留之前的生日历史数据。

    那么采用重写维度值的方法,就将会改变此维度属性的所有历史度量。

    比如,分析师希望分析星座和销售的关系,之前用户的生日属于白羊座,但是修改后的生日属于双子座,那么维度属性修改后,其销售额将都属于双子座。因此维度设计人员只在必要情况下使用此方法,同时需要告知下游分析人员。

    采用重写维度值方法的维度表和事实表变化如图:

    采用重写维度值方法处理变化维示例

    2. 插入新的维度行

    相比重写维度值方法不维护维度属性变化的特点,插入新的维度行方法则通过在维度表中插入新的行来保存和记录变化的情况。

    属性改变前的事实表行和旧的维度值关联,而新的事实表行和新的维度值关联。

    采用插入新的维度行方法处理缓慢变化维示例
    我们仔细观察变化后的维度表可以发现,新复制了一行该用户的信息,唯一不同在于 state 的不同(之前是 AZ,之后是 CA)。同时,仔细观察订单事实表也会发现,过去的订单是和旧的唯独行关联,而新的订单和新的维度行关联。

    通过新增维度行,我们保存了维度的变化,并实现了维度值变化前的 实和变化后的事实分别与各自的新旧维度值关联。

    但是这也给维度表用户带来了困惑,为什么查询会员会在维度表中发现多行记录? 尽管可以向用户解释,但是用户的使用和学习成本无疑增加了, 而且数据开发人员对于维度变化的处理逻辑无疑更复杂了。

    3. 插入新的维度列

    在某些情况下,可能用户会希望既能用变化前的属性值,又能用变化后的属性值来分析变化前后的所有事实。此时可以采用插入新的维度列这种方法。

    采用插入新的维度列处理缓慢变化维示例

    不同于前一种方法的添加一行,这种方法通过新增一列,比如用 region_previous 列表示之前的所属大区,同时新增 region_current 来表示变化后的所属大区。如果有多次变化,就需要有多个列来存储。

    实际上,这三种方法都能从不同角度解决维度变化的问题,还有通过组合这三种方法形成的其他各种技术可用于处理维度变化,这里就不再赘述。

    当然了,不管哪种技术,在大数据时代都不是完美的,而且有一定的处理复杂度和学习使用成本。

    如何以一种最简单、直接的办法来解决维度变化呢?我们在后面会聊聊 快照技术 ,以解决大数据时代的维度变化问题。

    维度层次

    维度层次指的是某个维度表中属性之间存在的从属关系问题。比如商品的类目可能是有层次的(一级类目、二级类目、三级类目等,尤其对于宝洁、联合利华等大的快消企业集团),同时类目、品牌和产品实际上也是有层次的。那么维度建模如何处理这些层次结构呢?

    实际上有两种处理办法:

    1. 第一种是将所有维度层次结构全部扁平化、冗余存储到一个维度表中,比如商品的一至三级类目分别用三个字段来存储,品牌等的处理也是类似的;
    2. 第二种是新建类目维度表,并在维度表中维护父子关系。

    第一种其实就是星型架构,第二种是雪花架构。在维度建模中,我们采用第一种来处理维度的层级问题,这样反规范化的处理牺牲了部分存储,但是给用户使用带来了便捷,也降低了学习使用成本。

    维度的层次结构通常和钻取联系在一起,所谓钻取即是对信息的持续深入挖掘。

    钻取分为向上钻取和向下钻取,比如对于某零售商的年度销售报表,其年度销售总额显示增长20%,那么从时间上分析是哪个季度的增长率比较高呢?

    此时可以向下分析各个季度的增长率,同样可以继续向下分析到月增长率乃至天增长率,同样的分析也可以应用到类目 、品牌等,来分析到底是哪个类目的增长或者哪个品牌的增长导致了年度总销售额的增长 20% 。这就是向下钻取。

    与之相对的是向上钻取,钻取的实质是增加或者减少维度,增加维度(向下钻取)从汇总数据深入到细节数据,而减少维度(向上钻取)则从细节数据概括到汇总数据 。通过钻取,用户对数据能更深入地了解数据,更容易发现问题,从而做出正确的决策。

    维度一致性

    在 Kimball 的维度设计理论中,并没有物理上的数据仓库。数据仓库是在对多个主题、多个业务过程的多次迭代过程中逐步建立的,这些多个问题、多个业务过程的多次迭代过程常被从逻辑上划分为数据集市。

    所谓数据集市一般由一张和多张紧密关联的事实表以及多个维度表组成,一般是部门级的或者面向某个特定的主题。数据仓库则是企业级的、面向主题的、集成的数据集合。

    物理上的数据集市组合成逻辑上的数据仓库, 旦数据集市的建立是逐步完成的,如果分步建立数据集市的过程中维度表不一致,那么数据集市就会变成孤立的集市,不能从逻辑上组合成一个集成的数据仓库,而维度一致性的正是为了解决这个问题。

    维度一致性的意思是指:两个维度如果有关系,要么就是完全一样的,要么就是一个维度在数学意义上是另一个维度的子集。

    不一致既包含维度表内容的不 致,也包含维度属性上的不一致。

    • 比如对于一个电子商务公司,如果其浏览等相关主题域的商品维度表包含了该企业的所有商品的访问信息,但是由于某种原因其交易域的商品缺失了部分商品 (有可能是成交在其他平台完成),那么对这些缺失商品的交易分析就无法完成 。

    • 同样如果两的商品属性不同,比如日期格式、类目划分(有可能浏览分为前天类目,成交是后台类自)等不一致,那么跨浏览域和交易域的对类目和日期的交叉分析就无法进行,因为其类目划分就不一致。

    维度一致性对于数据集市成为数据仓库起着关键作用,实际数据集市设计和开发过程中,必须保证维度一致性,具体可以采用共享同一个维度表或者让其中一个维度表是另外一个维度表的子集等方式来保证一致性,从而避免孤立数据集市的出现。

    维度整合和拆分

    实际维度表设计中,有时候会出现同一个维度表来自于多个前台业务系统的问题,此时就会带来维度整合和拆分问题。

    前台的业务系统通常是比较复杂的,比如移动端交易系统和PC端交易系统的系统架构和底层数据库、表结构等完全不一致,此时就存在维度的整合问题。

    在实际整合中,同一个维度整合需要考虑如下问题:

    • 命名规范:要确保一致和统一
    • 字段类型 :统一整合为一个字段类型
    • 字段编码和含义:编码及含义要整合为一致

    与整合相对的是拆分

    对于大的集团公司来说,以中石化为例,其主业为成品油销售,但是同时其还有中石化加油站的快捷零售店(在此仅做说明问题使用),它们的商品表字段和属性由于业务的不同而存在很大的差异(石油商品和零售店销售的食品、饮料等)。

    此时需要用一个统一整合的商品表么(从直觉来说是不需要的,因为业务差异巨大)?

    在维度建模理论中,对于上述情况通常有两种处理办法

    1. 建一个基础的维度表, 此基础维度表包含这些不同业务的共有属性,同时建立各自业务的单独维度表以包含其独特的业务属性。
      比如,上述例子就可以建立一个共有的商品维度表记录商品价格、商品描述等共有属性字段,同时建立成品油销售的商品维度表记录油标号( 92 95 97 等)等成品油独特的商品属性,另外建立一个零售商品维度表记录便利店的各种商品属性(实际操作中通常先建立两个单独的维度表,然后基于单独维度表生成共有的商品维度表或者视图)

    2. 拆分,即不合并,即各个业务差异独特性的业务各自建立完全独立的两个维度表,各自管理各自维度表和属性。

    我们在实际操作中 ,对于业务差异大的业务,偶合在一起并不能带来很大的便利和好处,因此通常倾向于拆分(即不合并),各自管理各自的维度表。 而对于业务相似度比较大的业务,则可以采用上述的第一种方法。

    展开全文
  • 一 、引言 建立三点云之间的正确匹配关系,也称为点云配准问题,这在三计算机视觉是一个基石。一个至关重要的原因是基于局部形状特征的匹配方式的应用,如三对象识别,点云注册、形状检索和三对象分类...
    论文标题:Performance Evaluation of 3D Correspondence Grouping Algorithms

    作者:Jiaqi Yang, Ke Xian, Yang Xiao and Zhiguo Cao

    译者:仲夏夜之星

    下载地址:https://arxiv.org/pdf/1804.02085.pdf

    摘要:本文针对几种广泛使用三维对应关系聚合算法进行了深入的评价,其目的在于他们在视觉任务中的意义依赖于正确的对应特征关系,一个良好的对应关系的聚合算法的期望是可以从初始的特征匹配中搜索到尽可能多的关系,从而提高准确率和召回率,就这个规则,本文从三个方面分别是处理形状检索、三维目标识别及点云配准来进行实验,该方法受噪音、不同点密度的细微差别、杂波、遮挡和部分重叠的影响,这将会导致内点和对应分布比率的不同而造成结果不同,基于定量结果分析,本文对其总结了优缺点并从性能和效率两方面进行了评估。

    一 、引言

    建立三维点云之间的正确匹配关系,也称为点云配准问题,这在三维计算机视觉中是一个基石。一个至关重要的原因是基于局部形状特征的匹配方式的应用,如三维对象识别,点云注册、形状检索和三维对象分类非常流行。基于局部特征的匹配方式如图1,首先检测表面上的一组独特的关键点并用特征描述符表示局部形状几何,然后生成原始初始匹配用于识别两种形状之间的相似性。然而,这个方式总会出现大量的虚假匹配,主要有两个原因,一个是加载前一个模块的残差,例如,关键点定位错误和重复结构中的特征描述符的不匹配,另一个是其他因素的干忧,包括噪音,不同点密度、杂波、遮挡和部分重叠。为了确保后续变换估计或假设生成的准确性,希望有更高的精度从原始特征匹配中过滤,突显出对应关系分组的重要性。

    图1 基于局部特征匹配的算法流程

    一种流行的对应分组算法是从最初的特征中找到尽可能多的内部线性匹配,可以增加精度和召回率[5]。类似于二维图像域的趋势,最近研究的热点话题是特征由三维对应分组相关算法来驱使特征匹配的视觉任务,如三维对象识别和三维重建。除了重新探索比较流行的二维对应分组技术,如三维领域的相似性分数(SS),最近邻相似比(NNSR),随机抽样一致性(RANSAC)和光谱技术(ST),我们也可以找到许多最近的三维目标算法,如几何一致性(GC),聚类,博弈论,3D霍夫投票(3DHV),和线性搜索(SI)等。随着广泛的三维对应分组算法的不断更新,这些算法的有效性通常在特定的数据集上进行评估有限数量的细微差别和比较,因此研究学者很难选择合适的算法并给出了一个特定的应用范围。为此,对于七种最先进的三维对应分组算法只要有SS、NNSR、RANSAC、ST、GC、3DHV和SI,本文提出了一个全面的评价,这是对三维对应关系分组算法的最新的全面的评估,据我们所知,它考虑了经典和最新的方法对涉及各种应用的基准和其他干扰进行评估。本文用精确率和召回率两个评价指标来测量定量性能,保证分组的对应关系和从原始特征匹配的大量线性关系的准确性来进行平衡的检查。此外,我们将应用的上下文考虑在内,具体来说,不同的应用将导致不同比例的差异和空间初始特征匹配的位置,主要是由于不同干扰的类别和程度来掩盖这些问题,我们分别对实验博洛尼亚三维检索(B3R),UWA三维对象识别和UWA三维建模数据集进行实验来检查这些三维对应分组算法。B3R数据集测试了关于噪声和变化点的算法密度评估结果的鲁棒性,U3OR数据集测试了关于杂波和遮挡的性能,U3M数据集测试了部分重叠的数据的影响,这些干扰全部都已经被量化,以便进行详细的比较。总之,本文的贡献主要有:

    (1)本文对七种主流的对应关系分组算法进行了定量评价,主要是关于不同干扰包括噪声、点密度变化、杂波、遮挡和部分重叠下的三个基准的比较,还测试了不同数量的初始匹配的时间效率。

    (2)本为给出了针对不同算法的局限性以及优缺点。

    本文的结构安排为:第二部分主要介绍七种最新算法中的每个核心计算步骤,第三部分主要验证不同数据集的评估方法以及算法的实施细则,第四部分为实现结果介绍,第五部分为本文的总结。

    二 、三维对应关系分组算法

    最近邻相似比:本文评估的算法的另一个基线为洛必达规则,它对应的关系是特征空间中最近点和第二最近点的距离,可以用独特的区域出口来匹配高分数,其类似于SS的阈值策略,如果满足:

    三维霍夫投票:霍夫变换是一个比较流行的计算机视觉技术最初被用来检测图像的线性关系,在3DHV中,每个对应关系在基于霍夫变换空间的基础上投票。

    线性内部搜索:该算法是最近一项旨在解决3D问题的对应关系配准的问题,其核心思想是结合局部和全局特征描述以确定是否应该投票,本文将该算法总结为三个主要步骤,初始化、局部投票和全局投票。

    三 、评估方法

    在第二部分中提到的所有算法已经在选定的三个基准上进行评价,其中包括不同水平的噪声、点密度变化、杂波、遮挡和局部重叠,所有算法的计算的内点线性关系使用精确率和召回率来进行测量,本节还介绍了每个算法的实现细节。

    3.1 数据集

    数据集主要包括B3R Dataset、U3OR Dataset、U3M Dataset,如图2所示。

    3.2 评价标准

    3.3 实施细节

    本文评估算法的输入,即初始对应集C,通过Harris 3D关键点检测、SHOT特征描述和L2距离特征匹配生成。在默认设置中,我们将Harris三维探测器的Non Maxima-Suppression半径设为3pr,为包含十万个点的点云生成约1000个关键点。SHOT的支撑半径为15pr,而判断阈值等于4pr。关于每个算法的参数,我们将它们列入表1。值得注意的是,我们对tss进行自适应使用,因为一个固定值是很难转向不同质量的特征匹配。NNSR和SI算法中的阈值与其原始文献中的阈值保持一致。对于ST和GC算法,它们的阈值是通过调整实验确定的。在RANSAC算法中,考虑到初始对应集的大小,分配10000个循环在有效性和效率之间达到平衡。

    四 、实验结果

    4.1 B3R数据集上的性能

    对噪声的鲁棒性:噪声对特征描述子的区分能力产生影响,从而产生一定量的虚假匹配。而在检索上下文中,由于B3R数据集中所使用的模型具有丰富的几何信息,inliers的比例通常较高。在这种情况下的结果如图3(a)所示。从图中可以看出,从总体查准率和召回性能来看,RANSAC和SI似乎是所有评估建议中最好的两个。一个有趣的发现是,在极端噪声的情况下,NNSR甚至超过GC和3DHV。这是因为NNSR倾向于选择不同的对应关系,这在该数据集上是特别充分的,因为模型具有丰富的独特结构。而NNSR的召回率则保持在除SS之外的其他算法的较低。SI算法在高斯噪声标准差小于0.15pr时具有良好的性能,当噪声进一步严重时,其性能会出现明显恶化,表明其对高高斯噪声的敏感性。

    对点密度变化的鲁棒性:与噪声类似,这个术语也影响描述符的独特性。我们给出了图3(b)中不同点密度下的结果。我们可以观察到,这些算法在点密度变化影响下的性能与在噪声下的性能类似。例如,RANSAC和ST再次给出最好的整体性能,其次是NNSR,3DHV和GC,但不同的是,在精度方面,当降采样比达到0.3时,SS甚至优于SI,而在低分辨率情况下,NNSR和SI的召回性能均大幅下降,这是因为SHOT对不同的点密度非常敏感,使得对于高分辨率的数据,特征具有弱的区分性(如NNSR原理),虽然SI的原因是SHOT的LRF (例如,SI的全球投票阶段的组成部分)在面对数据分辨率变化时的可重复性较小。

    4.2 U3OR数据集的性能比较

    对杂波的鲁棒性:杂波是场景中非模型表面斑块面积的百分比。在特征匹配过程中,杂波区域的表面贴片与模型中的贴片具有相似的几何特性,会引起异常值。杂波量化电平的结果如图3 (c)所示。由于三维目标识别场景比检索更具挑战性[2],所有算法都会出现明显的性能下降,当杂波程度小于75%时,RANSAC达到最好的精度性能。随着杂波程度的进一步增大,3DHV给出的性能最好。值得注意的是,ST算法在B3R数据集上表现最好,在U3OR数据集上表现相当差,这是因为ST试图寻找大的等距保持的簇,这些簇很少在杂波百分比较高的场景中退出,在召回性能方面,SS、SI和GC表现优于其他,权衡精度和召回率,3DHV和GC是杂波影响下的两种最优越的算法。

    对遮挡的鲁棒性:遮挡会导致形状补丁不完整,给精确的特征描述带来巨大挑战。遮挡程度给定为被遮挡模型表面贴片与模型总面积的比值,如图3(d)所示,当遮挡程度小于70 %时,RANSAC精度性能最好,随着遮挡程度增加到75%,GC优于RANSAC为最佳。当遮挡程度超过75%时,GC、SI和3DHV最终超过其他算法。在召回性能方面,对于所有级别的遮挡,SI均优于其他所有算法,特别是在高度遮挡的场景,SS和ST仍然是本测试中性能较差的两种算法。我们可以推断,基于一致性的算法,如RANSAC和GC等,更适合于有遮挡的场景,而基于初始特征匹配分数的算法,如SS和SI,在处理虚假匹配时具有较高的风险,因为从遮挡的场景块测量的特征匹配分数是可疑的。

    4.3 U3W数据集的性能对比

    对部分重叠的鲁棒性:U3M数据集提供了不同程度重叠的匹配对。重叠度度量为两个形状对应顶点数与最小顶点数之比,不同重叠度的结果如图3(e)所示。所有算法的共同特点是,它们的性能通常随着重叠程度的降低而下降。这是由于初始对应集中异常值的比率与重叠区域的比率密切相关。在精度性能方面,RANSAC在60%~80%的重叠度范围内,对于所有级别的重叠度,一般都会大幅度超过其他,GC和ST表现相当,其次是3DHV、NNSR、SI和SS,在召回率方面,SI优于其他,尤其是重叠度小于70%时。

    4.4 可变阈值ε的性能比较

    阈值决定了我们在多大程度上将通信判断为inlier。我们特此改变此阈值(默认设置为4pr ),以考察被评价算法的性能变化。具体而言,我们在整个U3OR数据集上进行实验,结果如图3(f)所示。正如预期的那样,所有算法都能以更宽松的方式获得更高精度的结果,特别是当阈值在[ 2pr,5pr ]和[ 6pr,10pr ]范围内时,GC和RANSAC分别达到了最高的精度,SS的精度有微弱的提高,说明其判断的多数inlier偏离了地面真实inliers,在召回率的inliers方面,随着阈值的增大,SI和SS呈现增加的趋势,而其他算法的性能几乎不变。

    4.5 不同初始条件的性能对比

    针对不同的应用,需要不同数量的初始对应,例如形状变形的密集匹配和粗扫描对齐的稀疏匹配。为此,我们在U3OR数据集上测试了这些算法对不同数量的初始对应的性能,如图3(g)所示。该图表明,不同的算法在改变初始特征匹配数量时给出的响应不同,一些算法,如GC,RANSAC和3DHV的性能随着初始匹配数目的增加而波动,同时,可以发现初始对应集的大小对SI和ST算法的影响相对较强。具体来说,当初始对应数小于1000时,这两种算法产生的精度较低,然而,随着初始特征匹配变得密集,即1000多个对应,SI和ST的精度性能迅速攀升,SI算法甚至以大约3000个初始对应达到了次优精度,这是由于密集的初始对应关系能够在SI的局部合并表决集中提供更可靠的成分,尽管如此,SI在初始对应集的所有测试尺寸下都取得了最好的召回性能,以较大的差距超过了其他所有尺寸。

    图3 (a-g)7种对应分组算法在实验数据集上的准确率和召回率性能。(h) 同大小的初始对应集的时间效率性能,其中y轴取对数为最佳视图。

    五、结论

    本文在多种数据集上对三维对应分组算法进行了深入的评价,评价指标包括在不同噪声水平、点密度变化、杂波、遮挡、部分重叠、内点判断阈值、初始特征匹配大小和计算效率下的查准率和召回率。鉴于这些评价结果,总结如下:

    (1)SS和NNSR作为依赖特征匹配相似性的两个基线,对杂波、遮挡和部分重叠等干扰非常敏感。给定具有丰富几何结构的高质量形状,NNSR可以是一个同时提供实时性能的有效选择。

    (2)ST算法对含有大量内点的对应集是有效的,但在三维目标识别和2.5维视图匹配等挑战性环境下,ST算法的性能急剧下降。同样,ST也被证明非常耗时,特别是对于大规模的对应问题。

    (3)RANSAC在多种干扰下表现出优越的精度性能,以牺牲相对较长的执行时间为代价。因此,RANSAC适用于依赖稀疏匹配的离线应用,如扫描配准和三维建模。

    (4)3DHV是一种超高效的算法,在许多应用中同时返回可接受的inlier搜索性能。这些优点表明3DHV可以应用于时间关键的应用,如机器人的同步定位与地图构建( SLAM )、物体抓取和三维物体识别等。

    (5)对于需要密集特征对应的应用,SI将是最佳选择。SI的一个核心缺点是在杂波和部分重叠的干扰下精度有限。在这种情况下,GC可以成为显示整体更高精度的替代方案。

    参考文献

    1.M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In Proceedings of the International Conference on Computer Vision,volume 2, pages 1482–1489. IEEE, 2005.

    2.Y. Guo, M. Bennamoun, F. Sohel, M. Lu, J. Wan, and N. M.Kwok. A comprehensive performance evaluation of 3d local feature descriptors. International Journal of Computer Vision, 116(1):66–89, 2016.

    备注:作者也是我们「3D视觉从入门到精通」特邀嘉宾:一个超干货的3D视觉学习社区

    本文仅做学术分享,如有侵权,请联系删文。

    下载1

    在「3D视觉工坊」公众号后台回复:3D视觉即可下载 3D视觉相关资料干货,涉及相机标定、三维重建、立体视觉、SLAM、深度学习、点云后处理、多视图几何等方向。

    下载2

    在「3D视觉工坊」公众号后台回复:3D视觉github资源汇总即可下载包括结构光、标定源码、缺陷检测源码、深度估计与深度补全源码、点云处理相关源码、立体匹配源码、单目、双目3D检测、基于点云的3D检测、6D姿态估计源码汇总等。

    下载3

    在「3D视觉工坊」公众号后台回复:相机标定即可下载独家相机标定学习课件与视频网址;后台回复:立体匹配即可下载独家立体匹配学习课件与视频网址。

     

    重磅!3DCVer-学术论文写作投稿 交流群已成立

    扫码添加小助手微信,可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群,旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。

    同时也可申请加入我们的细分方向交流群,目前主要有3D视觉CV&深度学习SLAM三维重建点云后处理自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。

    一定要备注:研究方向+学校/公司+昵称,例如:”3D视觉 + 上海交大 + 静静“。请按照格式备注,可快速被通过且邀请进群。原创投稿也请联系。

    ▲长按加微信群或投稿

    ▲长按关注公众号

     

    3D视觉从入门到精通知识星球:针对3D视觉领域的知识点汇总、入门进阶学习路线、最新paper分享、疑问解答四个方面进行深耕,更有各类大厂的算法工程人员进行技术指导。与此同时,星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息,打造成集技术与就业为一体的铁杆粉丝聚集区,近2000星球成员为创造更好的AI世界共同进步,知识星球入口:

     

    学习3D视觉核心技术,扫描查看介绍,3天内无条件退款

     圈里有高质量教程资料、可答疑解惑、助你高效解决问题

    觉得有用,麻烦给个赞和在看~  

    展开全文
  • 关系模型

    2020-07-22 21:53:37
    每个关系的数据结构是一张规范的二维表。(注:表没有表) 关系:一个关系对应通常说的一张表。 元组:表的一行即为一个元组。 属性:表的一列即为一个属性,给每一个属性起一个名称即属性名。 码:也称为码键...
  • 维度在维度建模相当重要,在维度设计的一些问题直接关系到维度建模的好坏。 1、维度变化 维度通常来自于业务系统,比如商品维度可能来自超时pos系统的商品,但是商品会变化的,比如类目,标签价格,...
  • 形模型和雪花模型

    2018-01-29 14:54:58
    当所有维表都直接连接到" 事实表"上时,整个图解就像星星一样,故将该模型称为星型模型,如图 1 。 星型架构是一种非正规化的结构,多维数据集的每一个维度都直接与事实表相连接,不存在渐变维度,所以数据有一
  • 这种随时间发生变化的维度我们一般称之为缓慢变化,并且把处理维度的历史变化信息的问题称为处理缓慢变化的问题。 在一个典型的星型模式数据仓库,维度随时间的变化很缓慢。例如, 商店 需要将新产品数据...
  • 还有一种拟合股市衰竭波的方法,就是三明治定理。 “三明治定理又称作夹逼定理, 说的是, 如果一... 即f(x)被夹在(或挤在)g(x)和h(x)之间. 此外,我们假设 limx!ag(x)=L并且 limx!ah(x)=L.那么,我们可以得出结论:limx
  • 方体是数据,方体的维度即各个维表,方体的值即事实表的度量;星型图则是事实表与维表的组织结构,与数据无关。原语:立方体定义(事实表):define cube []:维定义(维表):define dimension as ()度...
  • 点击上方“3D视觉工坊”,选择“星标”干货第一时间送达今天分享的是:深度学习领域基于图像的三物体重建最新方法及未来趋势综述。原文:Image-based 3D Object Recon...
  • GIS校园

    千次阅读 2018-09-22 22:53:38
    国内外很多高校已经建立了校园信息管理系统,二维的校园管理系统无法真实再现校园全景,已经不能满足学校招生宣传、校园导航、信息化管理的多元化功能需求,因此,建立三维数字校园势在必行。三维校园是数字地球的...
  • 雪花表是事实表的衍生品,当维表不直接连接到事实表的时候,就称为是雪花表。 三、形表和雪花表的对比 四)应用场景 星型模型的设计方式主要带来的好处是 能够提升查询效率,因为生成的事实
  • 在日常生活,我们要使用大量的应用程序来生成新的数据、变更数据、删除数据,当然在大多数的情况下我们还要查阅和分析数据。就来想象一个收发 email 的简单应用程序吧。我们已经存储了地址信息,可能还存储了一些...
  • 该模拟题库适用于全国特种作业操作证电工作业–登高架设模拟考试题通用部分,了解更多工种完整题库信息,百度搜索【安考】或关注“安考”微信公众号,支持电脑及手机多端同步练习。 判断题 181、安全带应高挂低...
  • 该模拟题库适用于全国特种作业操作证电工作业–电力电缆模拟考试题通用部分,了解更多工种完整题库信息,百度搜索【安考】或关注“安考”微信公众号,支持电脑及手机多端同步练习。 判断题 181、测温光纤全线...
  • 前言趁着冬促,30元入手了垂涎已久的过山车之(Planet Coaster® )。它的广告词:“过山车公园模拟游戏的明日之光重磅来袭!建造您的过山车公园帝国,为人们带来难以置信的惊奇、欢乐和刺激 — 放飞您的想象力,...
  • 关系模式是指一个关系的属性名表,即二维表的表框架。关系模式的设计是关系模型设计的灵魂。所以,关系模式的设计是关系数据库设计核心的核心。关系模式的设计直接决定着关系数据库的性能。目前,在指导关系模式...
  • 当所有维表都直接连接到“事实表”上时,整个图解就像星星一样,故将该模型称为星型模型,如图 1 。 星型架构是一种非正规化的结构,多维数据集的每一个维度都直接与事实表相连接,不存在渐变维度,所以数据有一定...
  • 多维数据模型是最流行的数据仓库的数据模型,多维数据模型最典型的数据模式包括星型模式、雪花...2.雪花模式是星型模式的扩展,其中某些维表被规范化,进一步分解到附加表(维表。雪花模式示例如下图所示: ...
  • 画圆为方这是二维的办法解决二维的几何问题,金字塔是三维的,但表达的是球体的扩大缩小,是动态的意图,这就需要四维来解读。图表是用代表的方法解读几何结果,螺旋比圆高明,是因为它把圆的路线动态起来了,增加了...
  • 数据库通常分为层次式数据库、网络...如果用D表示数据,用R表示数据对象之间存在的关系集合,则将DS=(D,R)称为数据结构。例如,设有一个电话号码簿,它记录了n个人的名字和相应的电话号码。为了方便地查找某人的电话号
  • astar A算法Java实现 一、适用场景 在一张地图,绘制从起点移动到终点的最优路径,地图会有障碍物,必须...A算法的代价计算使用了称作是启发式的代价函数。 先说明一下各符号意义:G表示的是 从起点到当前结
  • 当所有维表都直接连接到“ 事实表”上时,整个图解就像星星一样,故将该模型称为星型模型,如图 1 。 星型架构是一种非正规化的结构,多维数据集的每一个维度都直接与事实表相连接,不存在渐变维度,所以数据有一
  • 本系列文章由zhmxy555(毛星云)...毛星云(浅墨) 邮箱: happylifemxy@163.com 本篇文章里,我们首先对Direct3D固定功能渲染流水线相关概念进行了深入的剖析,然后介绍了创建三游戏世界的四大变换的概念和使用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,457
精华内容 2,582
关键字:

二维表中的行被称为关系