遥感数字图像处理复习.docx

遥感数字图像处理复习.docx

《遥感数字图像处理复习.docx》由会员分享，可在线阅读，更多相关《遥感数字图像处理复习.docx（23页珍藏版）》请在冰点文库上搜索。

遥感数字图像处理复习

✹命题公式（propositionformula）

✹由命题常元、变元和联结词组成的形式更为复杂的命题

✹命题公式（propositionformula）定义

✹命题常元和命题变元是命题公式，特别的称作原子公式或原子

✹如果A,B是命题公式，那么（¬A）,（A∧B）,（A∨B）,（A→B）,（A↔B）也是命题公式

✹只有有限步引用上述两条所组成的符号串是命题公式

✹重言式（永真式）tautology

✹命题变元的所有赋值都是命题公式的成真赋值

✹矛盾式（永假式、不可满足式）contradiction

✹命题变元的所有赋值都是命题公式的成假赋值

✹可满足式（contingency）

✹命题公式至少有一个成真赋值

✹

✹重言式的代入原理（ruleofsubstitution）

✹将重言式A中的某个命题变元p的所有出现都代换为命题公式B，得到的命题公式记作A（B/p），A（B/p）也是重言式。

✹命题公式的替换原理（ruleofreplacement）

✹将命题公式A中的子公式C的部分出现替换为和C逻辑等价的公式D（C╞╡D），得到的命题公式记作B，则A╞╡B。

✹真值函数（truthfunction）

✹如果将联结词看作逻辑运算符，那么包含命题变元p1,p2,…pn的公式A可以看作是p1,p2,…pn的真值函数

✹指派（赋值assignments）

✹对任意给定的p1,p2,…pn的一种取值状况，称为指派或者赋值

✹析取范式（disjunctivenormalform）

✹公式A’称作公式A的析取范式，如果

✹A’╞╡A

✹A’为合取子句或者若干合取子句的析取

✹合取范式（conjunctivenormalform）

✹公式A’称作公式A的合取范式，如果

✹A’╞╡A

✹A’为析取子句或者若干析取子句的合取

✹主析取范式（majordisjunctiveform）

✹公式A’称作公式A（p1,p2,…pn）的主析取范式，如果

✹A’是A的析取范式

✹A’中每一个合取子句里p1,p2,…pn均恰出现一次

✹主合取范式（majorconjunctiveform）

✹公式A’称作公式A（p1,p2,…pn）的主合取范式，如果

✹A’是A的合取范式

A’中每一个析取子句里p1,p2,…pn均恰出现一次

✹联结词集的完备性

✹如果任意一个真值函数都可以用仅包含某个联结词集中的联结词的命题公式表示，则称这个联结词集为功能完备集

✹形式系统是一个符号体系

✹系统中的概念由符号表示

✹推理过程即符号变换的过程

✹以若干最基本的重言式作为基础，称作公理（axioms）

✹系统内符号变换的依据是若干确保由重言式导出重言式的规则，称作推理规则（rulesofinference）

✹公理和推理规则确保系统内由正确的前提总能得到正确的推理结果

✹证明（proof）

✹公式序列A1,A2,…,Am称作Am的一个证明，如果Ai（1≤i≤m）或者是公理，或者由Aj1,…,Ajk（j1,…,jk

✹当这样的证明存在时，称Am为系统的定理（theorem），记作┠*Am（*是形式系统的名称），或者简记为┠Am

✹演绎（deduction）

✹设Γ为一公式集合。

公式序列A1,A2,…,Am称作Am的以Γ为前提的演绎，如果Ai（1≤i≤m）或者是Γ中的公式，或者是公理，或者由Aj1,…,Ajk（j1,…,jk

✹当有这样的演绎时，Am称作Γ的演绎结果，记作Γ┠*Am（*是形式系统的名称），或者简记为Γ┠Am

✹称Γ和Γ的成员为Am的前提（hypothesis）

✹证明是演绎在Γ为空集时的特例

✹命题演算形式系统PC（PropositionCalculus）

✹PC的符号系统

✹命题变元：

p,q,r,s,p1,q1,r1,s1,…

✹命题常元：

t,f

✹联结词：

¬,→（注意是完备集）

✹括号：

（,）

✹命题公式

✹命题变元和命题常元是公式

✹如果A,B是公式，则（¬A），（A→B）均为公式（结合优先级和括号省略约定同前）

✹只有有限次使用上面两条规则得到的符号串才是命题公式

✹PC的合理性（soundness）

✹如果公式A是系统PC的定理，则A是重言式（如果┠PCA，则╞A）

✹如果A是公式集合Γ的演绎结果，那么A是Γ的逻辑结果（如果Γ┠PCA，则Γ╞A）

✹PC的一致性（consistency）

✹没有公式A，使得┠PCA和┠PC¬A同时成立

✹由PC的合理性容易证明

✹PC的完备性（completeness）

✹如果公式A是重言式，则A一定是PC中的定理（如果╞A，则┠PCA）

✹如果公式A是公式集合Γ的逻辑结果，则A一定是Γ的演绎结果（如果Γ╞A，则Γ┠PCA）

证明很难，略。

✹谓词命名式

✹将谓词中的个体空位用变元字母代替，称作谓词命名式

✹谓词填式

✹将谓词中的个体空位用个体变元或常元代替，称作谓词填式

✹谓词填式在形式上和命名式相同，但是属于不同的概念，需要根据上下文加以区分

✹谓词公式（predicateformula）

✹谓词填式是公式，命题常元（零元谓词）是公式，称作原子公式

✹如果A,B是公式，x为任一变元，那么（¬A）,（A→B）,（xA）,（xA）都是公式（5个联结词还要包括∧,∨,↔）

✹只有有限次使用上述两个条款形成的符号串是公式

✹谓词公式成为命题，有确定真值的条件：

✹给定个体域

✹公式中的所有谓词都有明确意义（解释）

✹公式中的所有自由变元取定个体

✹谓词公式成真的几个层次

✹给定个体域D，公式A中各谓词符号的解释I，如果A中的自由变元x1,…,xn分别取值u1,…,un时A真，称A在u1,…,un处真

✹如果A在自由变元的任何取值下都真，称A在解释I下真

✹如果A在每个解释I下均真，称A在D上永真

✹如果A在任何个体域D永真，称A永真

✹一阶谓词演算形式系统（FirstorderpredicateCalculus）

✹FC的符号系统

✹个体变元：

x,y,z,u,v,w,…

✹个体常元：

a,b,c,d,e,…

✹个体间运算符号（函数符）f（n）,g（n）,h（n）,…

✹其中n是正整数，表示函数的元数

✹谓词符号：

P（n）,Q（n）,R（n）,S（n）,…

✹其中n是非负整数，表示谓词的元数

✹当n=0时，谓词公式退化为命题常元

✹真值联结词：

¬，→

量词：

（x等价于¬x¬）

✹FC的高级语言成分

✹个体项（term），简称项

✹个体变元和个体常元是项

✹对任意正整数n，如果f（n）为一n元函数符，t1,…,tn为项，则f（n）（t1,…,tn）也是项

✹除有限次数使用上述两个条款确定的符号串外，没有别的东西是项

✹合式公式（well-formedformula），简称公式

✹对任意非负整数n，如果P（n）是一n元谓词符，t1,…,tn为项，那么P（0）（命题常元）和P（n）（t1,…,tn）（n>0）是公式；

✹如果A,B是公式，v为任一个体变元，那么（¬A）,（A→B）,（vA）（或（vA（v）））均为公式

✹除有限次数使用上述两个条款确定的符号串外，没有别的东西是公式

✹全称封闭式（generalizationclosure）

✹设v1,…,vn是公式A中的自由变元，那么公式v1…vnA（或v1…vnA（v1,…,vn））称为公式A的全称封闭式。

✹A中不含自由变元时，A的全称封闭式为其自身

✹演绎结果

✹在ND中，称A为Γ的演绎结果，即Γ┠NDA简记为Γ┠A，如果存在如下序列：

✹（Γ=Γ1）Γ1┠A1,Γ2┠A2,…,Γn┠An（Γn=Γ,An=A）

✹使得Γi┠Ai（1≤i≤n）

✹或者是公理；

✹或者是Γj┠Aj（j

✹或者是对Γj1┠Aj1，…，Γjk┠Ajk（j1,…,jk

✹如果有Γ┠A，且Γ=ø，则称A为ND的定理

✹外延公理（extensionalityaxiom）

✹两个集合A和B相等当且仅当它们具有相同的元素。

✹A=B↔x（x∈A↔x∈B）

✹{0,1}={1,0}={x|x=0∨x=1}

✹说明集合元素的无序性，以及集合表示形式的不唯一性

✹概括公理（comprehensionaxiom）

✹对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S。

✹S={x|x∈U∧P（x）}

✹规定了集合成员的确定性

空集：

P（x）为永假式

✹正规公理（regularityaxiom）

✹不存在集合A1,A2,A3,…使得…∈A3∈A2∈A1

✹直观来说就是集合的有限可分，个体域的元素是“基本粒子”

✹正规公理确立了元素和集合的不同层次性，集合不能是自己的成员

✹排除了A={A}这样的“病态”集合

✹幂集（powerset）运算

✹对任意集合A，ρ（A）称作A的幂集，定义为：

ρ（A）={x|xA}

✹A的所有子集作为元素构成的集合

✹集合族（collections）

✹如果集合C中的每个元素都是集合，称C为集合族

✹集合族的标志集（indexset）

✹如果集合族C可以表示为某种下标的形式

✹C={Sd|d∈D}

✹那么这些下标组成的集合称作集合族C的标志集

✹标志集可以是自然数、某些连续符号等

✹广义并

✹∪C={x|S（S∈C∧x∈S）}

✹集合族中所有集合的并集

✹广义交

✹∩C={x|S（S∈C→x∈S）}

✹集合族中所有集合的交集

✹归纳定义（inductivedefinition）

✹基础条款

✹规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定

✹归纳条款

✹规定由已确定的集合元素去进一步确定其它元素的规则

✹终极条款

✹规定待定义集合只含有基础条款和归纳条款所确定的成员

✹基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员

✹终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象

✹二元有序组，或者二元组（2-tuple），或者序偶（orderedpairs）

✹设a,b为任意对象，称集合族{{a},{a,b}}为二元有序组，简记为

✹称a为的第一分量，b为第二分量

✹n元有序组（n-tuple）

✹递归定义：

n=2时，={{a1},{a1,a2}}

✹n>2时，=<,an>

✹ai称为n元组的第i分量

✹对任意集合A,A2,…,A，A1×A2称作集合A1，A2的笛卡儿积，定义如下：

✹A1×A2={|u∈A1,v∈A2}

✹A1×A2×…×An=（A1×A2×…×An-1）×An

✹R称为集合A1,A2,…,An-1到An的n元关系，如果R是A1×A2×…×An的一个子集。

当A1=A2=…=An-1=An时，也称R为A上的n元关系

✹关系相等

✹如果关系R和S具有相同的前域和陪域，并且xy（xRy↔xSy）

✹合成运算（composition）（复合运算）

✹R为A到B的二元关系，RA×B，S为B到C的二元关系，SB×C，R和S的合成关系RS定义为：

✹RS={|x∈A∧z∈C∧y（y∈B∧xRy∧ySz）}

✹简化形式：

RS={|y（xRy∧ySz）}

✹关系矩阵表示的合成运算

✹关系合成运算对应关系矩阵的乘法

✹将数乘换成合取，将数加换成析取

✹运算的封闭性

✹如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭

✹类比：

整数大于0的性质，对加运算封闭，但是对于减运算不封闭

✹等价关系（equivalentrelation）

✹等价关系R为A上的自反、对称、传递的二元关系

✹xRx；xRy→yRx；xRy∧yRz→xRz

✹等价类（equivalentclass）

✹设R为A上的等价关系，对于每个a∈A，a的等价类记做[a]R（简记[a]），定义为：

[a]R={x|x∈A∧xRa}，a称作[a]R的代表元素

✹等价类是A的子集，每个代表元素确定一个等价类

✹例子：

“模2相等”，有2个等价类：

[0]和[1]

✹相等关系EA有|A|个不同的等价类，每个等价类都是单元素集合

✹全关系A×A只有一个等价类A

✹划分（partitions）

✹满足下列条件的集合A的子集族π

✹B（B∈π→B≠）

✹∪π=A

✹BB’（B∈π∧B’∈π∧B≠B’→B∩B’=）

✹π中的元素称为划分的单元

✹特别约定A=时只有划分

✹很明显，A上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分

✹{[x]R|x∈A}，所有等价类的集合是一个划分

✹反过来，集合A的一个划分π，也对应A上的一个等价关系R，称作划分π对应的等价关系

✹R={|B（B∈π∧x∈B∧y∈B）}

✹R=∪B∈πB×B=∪{B×B|B∈π}

✹积划分运算

✹划分π1和π2的积划分π1•π2是满足如下条件的划分：

✹π1•π2细于π1和π2

✹如果某个划分π细于π1和π2，则π一定细于π1•π2

✹也就是说，π1•π2是细于π1和π2的最粗划分

✹积划分对应于等价关系交运算

✹那么和划分是否对应于等价关系的并运算呢？

✹否！

等价关系中的传递性质对于并运算不封闭

✹针对传递性质扩展并运算结果

✹二元关系R的传递闭包t（R）

✹t（R）是传递的，Rt（R）

✹对于A上的任意一个具有传递性质且包含R的关系R’，t（R）R’

✹和划分对应于等价关系并运算结果的传递闭包

✹R1和R2分别是π1和π2对应的等价关系，则π1+π2是等价关系t（R1∪R2）对应的划分

✹商集（quotientsets）

✹R是A上的等价关系，称A的划分{[a]R|a∈A}为A的R商集，记做A/R

✹每一个划分π均为A上的一个商集，相应的商集的和、积对应于划分的和与积。

✹序关系（orderedrelation）

✹序关系R为集合A上的自反、反对称、传递的二元关系

✹xRx,xRy∧yRx→x=y,xRy∧yRz→xRz

✹存在序关系R的集合A称作有序集（orderedset），用二元有序组表示，一般的有序集表示成

✹哈斯图（Hassegraph）

✹对序关系关系图的一种简化画法

✹由于序关系自反，各结点都有环，省去；

✹由于序关系反对称且传递，所以关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向

✹由于序关系传递，所以省去所有推定的边，即a≤b,b≤c有a≤c，省去ac边

✹链（chain）

✹如果子集B中的任意两个元素都是可以比较的

✹xy（x,y∈B→x≤y∨y≤x）

✹反链（antichain）

子集B中的任意两个元素都是不可比较的xy（x,y∈B∧x≠y→¬（x≤y）∧¬（y≤x））

✹是有限的有序集，BA

✹如果A中最长的链长度为n

✹则A存在一个划分，划分有n个单元，每个单元都是一反链

✹半序关系（Partiallyorderedrelation）

✹序关系R为集合A上的反自反、反对称、传递的二元关系

✹¬（xRx）,xRy∧yRx→x=y,xRy∧yRz→xRz

✹函数（function）定义

✹如果X到Y的二元关系fX×Y，对于每个x∈X，都有唯一的y∈Y，使得∈f，则称f为X到Y的函数，记做：

f:

X→Y

✹当X=X1×…×Xn时，称f为n元函数

✹函数的相等和包含

✹f:

A→B，g:

C→D

✹如果A=C，B=D，且对每个x∈A，都有f（x）=g（x），则函数f等于g，记为f=g

✹如果AC，B=D，且对每个x∈A，都有f（x）=g（x），则函数f包含于g，记为fg

✹单射函数（injection）

✹如果任意x1≠x2有f（x1）≠f（x2）

✹满射函数（surjection）

✹如果任意y都有x使得y=f（x），即Ran（f）=Y

✹双射函数（bejection）

✹如果f既是单射函数又是满射函数，称作双射函数

也称作“一一对应”

✹函数作为关系，可以求逆，但是f~是否函数？

✹如果f不是单射，则f~无法满足单值性

✹如果f不是满射，则Dom（f~）≠Y

✹所以只有双射函数存在逆函数

✹双射函数f的逆函数（inversefunction）记做f-1，也是双射函数，称f是可逆的

✹简单图simplegraph：

无环和重边的无向图

✹完全图completegraph：

任何两个不同结点间都有边关联的简单图，记做Kn

✹孤立结点isolatedvertex：

不是任何边的端点的结点

✹零图：

仅有孤立结点构成的图（E=）

✹正则图

✹所有顶点的度均相同的图称为正则图（regulargraph），按照顶点的度数k称作k-正则图

✹Kn是n-1正则图

✹生成子图spanningsubgraph

✹如果G1是G2的子图，且V1=V2

✹G1,G2互为补图

✹V1=V2,E1∩E2=,是完全图

✹图的同构isomorphic

✹|V1|=|V2|,|E1|=|E2|

✹如果可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2

✹u可达v（accessible）

✹u=v，或者存在一条u到v的路径

✹连通的无向图connected

✹无向图中任意两个顶点都是可达的

✹强连通的有向图

✹有向图中任意两个顶点都是互相可达的

✹单向连通的有向图

✹任意两个顶点，至少从一个顶点到另一个是可达的

✹弱连通的有向图

✹将有向图看作无向图时是连通的

✹连通分支（connectedcomponent）

✹图G的连通子图G’，而且G’不是任何其它连通子图的真子图（最大性）

✹欧拉图Eulergraph

✹如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复）

✹欧拉路径Eulerwalk

✹如果图G上有一条经过所有顶点、所有边的路径（允许顶点重复）

✹哈密顿图Hamiltongraph

✹如果图G上有一条经过所有顶点的回路（不要求经过所有边）

✹也称作哈密顿回路

✹哈密顿通路Hamiltonpath

✹如果图G上有一条经过所有顶点的通路（非回路）

✹邻接矩阵（adjacencymatrix）

✹无重边的有向图G=，其邻接矩阵A[G]定义为

✹aij=1,当∈E

✹aij=0,当E

是一个|V|×|V|矩阵

✹关联矩阵（简单无向图）

✹表示顶点和边的关联关系，n*m矩阵

✹通过矩阵的秩来判定图的连通分支个数

✹路径矩阵walkmatrix

✹图G=的邻接矩阵A

✹A（m）=A∧A∧…∧A

✹路径矩阵B=A∨A

（2）∨A（3）∨…∨A（|V|）

✹B的每个分量bij表示vi到vj是否有路径

✹可达性矩阵

✹P=I∨B，I是n*n的单位矩阵

✹加上顶点的自身可达性

✹满足如下条件的无向图G=

✹有非空集合X,Y,X∪Y=V,X∩Y=，且

✹每个{vi,vj}∈E，都有vi∈X∧vj∈Y或者vi∈Y∧vj∈X

✹可以用G=表示二分图bipartitegraph

✹如果X,Y中任意两个顶点之间都有边，则称为完全二分图completebipartitegraph

✹完全二分图可以记作K|X|,|Y|

✹二分图的等价条件：

G至少要有两个顶点，而且G中所有回路的长度都是偶数

✹匹配matching

✹将E的子集M称作一个匹配，如果M中的任意两条边都没有公共端点

✹边数最多的匹配称作最大匹配maximalmatching

✹如果X（Y）中的所有的顶点都出现在匹配M中，则称M是X（Y）-完全匹配perfectmatching

✹如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配

✹如果无向图G可以在一个平面上图示出来，并且各边仅在顶点处相交，称作平面图planargraph，否则是非平面图

✹K5和K3,3都不是平面图

✹它们都是正则图

✹任意去掉一条边，都成为平面图

✹K5是顶点数最少的非平面图

✹K3,3是边数最少的非平面图

✹平面图等价条件

✹G或者G的子图作任何同胚操作后得到的图均不能以K5及K3,3为子图（1930,Kuratowski）

✹同胚操作就是在原图的边上增加或者删除二度节点

✹根树rootedtree递归定义

✹一个孤立节点v0是根树，v0称为树根

✹如果T1,T2,…Tk是根树，其树根分别是v1,v2,…,vk，则

✹V=V（T1）∪V（T2）∪…∪V（Tk）∪{v0}；

✹E=E（T1）∪E（T2）∪…∪E（Tk）∪{v0,,v1}∪{v0,,v2}…∪{v0,,vk}

✹T=也是根树，v0称为树根

✹代数结构algebraicstructure

✹在一个对象集合上定义若干运算，并设定若干公理描述运算的性质

✹运算operator

✹Sn到S的一个函数，称为n元运算

✹常用*表示二元运算，*（x,y）常记做x*y

✹常用Δ表示一元运算

✹运算的基本性质

✹普遍性：

S中的所有元素都可参加运算

✹"x"y$z（x*y=z）

✹单值性：

相同的元素运算结果也相同且唯一

✹"x"y"x’"y’（x=x’∧y=y’→x*y=x’*y’）

✹封闭性：

任何元素参加运算的结果也是S中的元素

✹"x"y$z（x*y=z→z∈S）

✹代数结构的定义

✹非空集合S，称作代数结构的载体

✹载体S上的若干运算

✹一组刻画载体上各运算性质的公理

✹可约cancelable元素

✹中元素a，如果对任意x,y∈S有

✹a*x=a*y蕴涵x=y（左可约）

✹x*a=y*a蕴涵x=y（右可约）

✹那么a称为可约的

✹同类型代数结构

✹|S|=|S’|

✹运算的元数相同

✹同构的代数结构

✹存在S->S’的一一映射h

✹S中运算的像等于运算数像在S’的运算结果

✹h（x*y）=h（x）*’h（y）

✹同态映射homomorphism

✹对于代数结构和