发表于

INTRODUCTION

GFS(Google File System)由一个 master和多个 chunkserver组成，是一个可部署在廉价商用硬件(ICH,inexpensive commodity hardware)上的分布式文件系统。为了不使master成为系统的瓶颈GFS会尽量减少master的工作。master和chunkserver使用心跳信息来交换信息。为了保持高可用性，GFS中的每个chunk都有多个副本，并且对每个副本的chunkserver选择地加以限制。GFS使用租约(Lease)、 操作日志 (OL,Operation Log)、 诊断日志 (DL,Diagnostic Log)来增加容错，其中 租约解决了并发情况下写入的同步问题，除了 租约，GFS还提供了 record append (RA,Record Append)用来解决并发的写入问题。GFS使用一个较为宽松的 一致性模型 (CM,Consistency Model)，用来适应这个高度分布式的系统(HD,highly distributed)。为了最大化利用网络，GFS将数据流和控制流分离，且使用 重负载均(Rebalancing)。chunk的副本失效时，GFS会使用 重复制 (Re-replication)解决。master会定期扫描命名空间，在此期间会进行 垃圾回收 (GC,Garbage Collection)。GFS中大部分都是追加操作(append)，GFS只针对追加进行了优化，但是GFS仍然支持随机写入。

COMPONENT

  1. chunk
  2. master
  3. chunkserver
  4. client
  5. operation log
  6. diagnostic log
  7. consistency model

Chunk

GFS中每个文件会被分为若干个chunk而每个chunk大小为64MB。相对较大的chunk size可以减少与master的交互，且master中需要存储的元数据也较少同时client可以储存一个file所有的chunk的位置信息。每个chunk都有64字节的独一无二的全局的handle，这样保证了每个chunk都可以根据他的handle来找到。GFS对每个chunk都会有备份，默认是三个，可为不同命名空间配置不同的复制级别。为了提高容灾，所以对于一个副本是不会放在同一个机架上。每个chunk的都是一个无格式的linux file只有在需要的时候才会扩展。每一个chunk会被分为64KB的block，每一个block对应一个32位的检验和。

Master

用于控制整个GFS。但是不储存信息，仅仅缓存每个chunk的元数据(metadata)在内存中。如果master太多，则会导致许多问题，如何同步master中的信息、如何让master保持同步、如何分配指令……对于多个master会让系统变得很复杂，产生很多一致性问题。因此GFS只有一个master，当然master也有备份。因为只有一个master，所以如果给master分配很重的任务会很容易让master成为一个瓶颈(bottleneck)，所以GFS尽量简化master的任务。简化了master的任务，这也可以让master不需要做很复杂耗时的任务，因此储存很多信息是没有必要的，所以master中储存的元数据只是一些基本信息。master主要存储三种信息。

  1. 文件和chunk的命名空间(namespace)。
  2. 从文件到chunk的映射
  3. 每个chunk和他的副本(replica)的地址

master中的各种关于chunk和chunkserver的信息来自于chunkserver的心跳机制，但当master启动或者新的chunkserver加入到集群的时候GFS会询问chunkserver每个chunk的位置。每隔一段时间chunkserver就会将其信息告诉给master，届时，master更新信息。此外，GFS还有一个“阴影”master(SM,Shadow Master)他不是master的完全副本，只在master宕机的时候提供读访问，且状态落后master一秒左右。

Chunkserver

用于存储每个chunk。使用心跳机制给master提供自己的信息。如果用master来询问chunkserver中的各种信息，会增加master的工作量，且效果不好。

Client

GFS 自己实现了一系列类似于POSIX API的接口。client会从master中读取chunk的信息并且缓存。在每次请求中，client会请求除了当前需要的chunk外的chunk以减少之后与master的交互。提供给用户使用

Operation Log

日志记录了master所有的历史操作，master只有在将操作写入到日志中才会进行操作。他还承担了逻辑上的时间标准，为并发操作定义顺序。对于每一个文件，chunk和他们的版本都会创建一个永远独一无二的标识。日志是GFS的核心所以日志也有许多副本，master会捆绑许多日志，一起刷新，以此减少刷新和复制对系统的冲击。master可以通过重放日志中的请求来恢复元数据。日志文件内容很多，如果从头开始重放则会很耗时。GFS对日志设计了存档(checkpoint)在日志文件增长超过一个数目的时候就会进行存档。需要回复数据时只需要重放最近的存档点即可。在建立存档的时候，GFS会切换到一个新的日志文件中，创建存档的工作交给一个线程来处理。

Diagnostic Log

GFS的诊断日志。存储很多重要事件和所有的RPC请求还有回复。诊断日志可以被任意删除，但是会尽量保存。可用异步缓冲等各种手段优化。

Consistency Model

consistent:对于文件区域A，客户端无论从哪个副本看到的数据都一样。
defined:如果A是一致的，并且客户端可以看到突变(mutation)写入完整内容。当一个突变在并发且没有干扰的情况下写入，则该区域是一致的。所有用户都可以看到变异写入的数据(只需要变异写入的数据可被看见，无须consistent)。

如果并发情况下突变成功被写入，则该区域是consistent但是可能是undefined(如果A用户在chunkB上偏移量为0的地方写入abc，用户C在chunkB的偏移量为0的地方上写入dddd这样前者写入内容会被覆盖，这样A用户看不到自己写的东西但是所有副本都可以看见C用户写的东西所以是consistent但是不是defined)。当并发突变失败时该区域便是undefined也是unconsistent。
GFS保证变异写入区域是defined，解决方式有两种。

  1. 使用chunk版本检测旧版本
  2. 使用 lease让并发写入变成串行写入

GFS在每次写入后会给写入后的chunk分配新的版本。当chunk因为一些故障写入失败时会错过版本分配，在之后读取的时候就会跳过该版本。

GFS保证写入区域是defined但是不保证是consistent。其中不一致的区域可以由应用使用检验和让应用来过滤掉重复或者无意义内容。

WRITING OPERATION

GFS设计时尽最大努力减少master的工作。在写入时master会使用 lease 下放写入权利，并使用lease解决并发写入问题，此外GFS还提供了 record append以用来解决并发的写入问题。为了提高传输效率，将数据流和控制流分开。快照方面GFS也做了一些优化。GFS支持所以写入，所以在每个副本中，数据的偏移量都要是一样的。

Record Append

append record 是GFS提供的一个原子性append，每次追加的大小被限制在chunk最大大小的四分之一，追加前会进行判断追加的部分加入后是否会超出chunk的容量范围，如果超出就会将该chunk填充满，然后提醒客户端需要重试，并使用下一个chunk，如果没有超出则会在文件尾做append操作并在写完后将数据偏移量返回给用户，用户在使用该操作是只需要提供数据。record append保证至少一次将数据append到文件尾(如果数据同步到某一副本时出故障了会重复append，这样就导致了未出故障的副本重复写入，但是出故障的副本只写入一次，但是最后的写入数据的偏移量都是一样的，出故障的副本会使用特殊字符填充这样就导致了unconsistent但是defined)即数据是defined。

Lease

master将写入的权利下放到chunkserver中，且有时间限制(预设60s)，所以称之为lease。
当用户向master请求写入操作时master会选定一个chunk的副本授权lease，该chunk被称为首要(primary)副本。拥有租约的副本要为这个chunk上的并发写入确定一个顺序将并发写入变成串行。当租约过期后chunk可进行续租。master和chunkserver会持续交换心跳消息，租赁信息、请求连任的信息都在这之中完成。master有时会撤回一个chunk的租约。如果master和首要分配失去联系则他会在租赁过期后选出一个新的首要副本。

写入过程如下

  1. 用户询问master，哪一个chunkserver拥有他要写入的chuank的租约，如果有则会告知用户chunk的地址，如果没有master会进行租约授权
  2. master将授权的副本信息返回给用户，用户将其储存，在chunk不可接触前都不会master再进行交互(权利下放)。
  3. 因为数据流分离，所以用户将数据以任意顺序推向所有副本。所有副本将数据缓存知道数据被使用或者超时。
  4. 一旦所有副本确认收到数据，客户端发送一个写请求到首要副本。这个请求只包含身份认证信息。首要副本会持续接收到很多写请求，他会为每个他接收到的突变分配一个连续的串行序号，依照这个副本会将突变应用到本地状态上。
  5. 首要副本将包含了文件写入顺序的写请求推送给其他副本
  6. 其他的副本应用请求中的顺序将缓存的内容写入
  7. 首要副本回复客户端。任何遭遇的错误都会反馈给客户端。当遭遇错误时，客户端请求将写入区域更改为undefined状态。客户端重复步骤3-7直至成功。

Data Flow

为最大化利用网络，GFS将控制流和数据流分离。控制流如上文所言，从客户端流向首要副本然后再流向其他副本。数据流之间的流动依靠一种被选择的线性管道方式。每个chunk将数据发送到拓扑中距离最近的chunkserver，接收数据后再进行传输。

Snapshot

进行快照时GFS会向要进行快照区域中的chunkserver回收租赁。GFS的spanshot使用copy-on-write技术。在写入某个chunk C时，chunkserver会在本地复制一个chunk C’ 再通知其他副本建立 chunk C’。master的值副本创建完成后将副本返回给客户端。

MASTER OPERATION

Namespace Management And Locking

GFS没有结构化的list来映射文件夹中的文件，而是使用的命名空间和映射，且映射表中的chunk handle使用前缀压缩高效的存储在master内存中。GFS中很多操作会很消耗时间，为了提高效率，提高并发量是很重要的。master每一步操作中都会对命名空间申请锁或者使用锁，只有当没有操作时才会释放锁。为了避免错误，客户端在操作时需要对每一层都申请锁。如果一个snapshot操作需要在将/a/b/c/d/save 快照到 /a/b/d/e/user中，则需要对/a /a/b /a/b/c /a/b/c/d /a/b/c/d/save 申请读操作 /a/b/c/d/user /a/b/c/d/user 申请写操作。这样就防止了在快照过程中有用户对/a/b/c/d/save 创建文件或者进行其他的写操作，如果有则会串行执行。

Replica Placement

有三种情况会发生chunk副本的创建

  1. chunk创建
  2. 重复制
  3. 重负载均衡
    在chunk和其副本的选择方面，GFS选择将他们放在不同的架子上，虽然会导致流量增加，但是安全性上升很多。为了尽最大可能利用网络，GFS会根据负载问题来进行重负载均衡，将负载较重的chunkserver中的chunk移动一部分到chunkserver负载较轻的地方。在副本失效时GFS会使用重复制，并且根据失效的情况选择复制的优先级。

Replica Placement Principle

  1. 选择的chunkserver的磁盘利用率低于均值
  2. 选择的chunkserver不是最近选择过的，或者频繁选择的
  3. 副本的放置地要在不同的机架上

Rebalancing

master会周期性的进行检测当前副本分布，为了更加均衡的磁盘使用和负载，会对一些副本进行迁移。新加入的chunkserver在这个过程中会被填充，而不是一开始加入时就被一次性填充。一般会填充空间利用率较低的chunkserver。副本的布置基于以上副本布置规则，且会优先迁移副本空闲较少的chunkserver。

Re-replicaiton

在副本存活个数少于用户指定值时会发生重复制。每个需要被重复制的chunk会被赋予一个优先级，存活个数越少的优先级越高。同时会提高阻塞用户进程的chunk。master会选择优先级最高的chunk来进行复制，master只需要指示某些chunkserver直接从一个存在的合法副本上创建数据和创建副本。副本的放置规则也上文提到的副本放置规则(RPP,Replica Placement Principle)相似。为了减少复制的影响，master会限制每个chunkserver上同时执行的副本复制的数量。

Garbage Collection

当一个文件(由多个chunk组成)被应用删除时，master会记录删除操作，但是不会立马删除文件而是将文件重命名为一个包含删除时间戳的匿名名字(Hidden Name)。此外，被删除文件还会有一个预定的时间(可修改)，当master进行命名空间扫描时，只有文件距他被进行删除操作已经存在超过预定时间就会被删除，在此期间匿名文件重命名、恢复(将他的名字变为普通名字)和读取。当被匿名文件被删除时，master中关于他的元数据也会被删除，切断这个文件对它所有chunk的引用。在另一次命名空间扫描时，master只要发现孤儿chunk(Orphan Chunk)，就会删除那些孤儿chunk的元数据。在chunkserver和master交换心跳信息时，chunkserver会告诉master他有的chunk，而master会回复chunkserver他元数据中没有的chunk，这样chunkserver就可以删除被删除的chunk。当文件被重复删除时，会立即触发一些回收动作。不同的命名空间可配置不同的回收策略。

Stale Replica Detection

当chunk进行修改时，chunk的版本就会改变。master回味每个chunk维护一个版本号，来区别新旧版本。
当master授予新的lease给某个chunk时，都会增长chunk版本号并且通知各个副本，并持久化记录。这项操作是在写操作之前完成。当chunk不可用他的版本就不会更新。当chunkserver重启时会汇报自己的信息，这时master可以检测到旧的版本。当master看到一个比自己保存的版本号还高的版本号时会更新版本号。在垃圾回收阶段，会回收被删除的chunk和旧版本的chunk。且在master与各种客户端和chunkserver的交互中也会带上版本号。

Data Integrity

Reliability

GFS为了保证高可用性有两个策略

  1. 快速恢复(Fast Recovery)
    • master和chunkserver可以在几秒中内恢复他们的状态
  2. chunk复制(Chunk Replicaiton)
    • 每个chunk有多个副本，用户可以指定每个命名空间的不同复制策略。

Checksum

每个chunk都会用检验和(checksum)来检测存储的数据。一个chunk被分为多个等大的块每个64KB，每个块有一个32位的检验和。检验和也是元数据，也会被持久化地保存在内存中，且会被日志记录。对于读操作，chunkserver会在读之前进行检验和的验证，如果不匹配会返回错误信息给请求者。请求者会向其他副本请求，master则会clone一个新的chunk，并在clone完成后删除问题副本。系统空闲时，chunkserver会去扫描和检查不太活跃的chunk，删除数据损坏的副本，并创建新的副本。

发表于

chapter 2

空间和灰度分辨率分别是什么。

  1. 空间：由一幅图像的坐标张成的实平面部分称为空间域。空间域是包含图像像素的简单平面。
  2. 灰度分辨率：灰度级中可分辨的最小变化。

图像内插

  1. 双线性插值
  2. 双三次线性插值
  3. 最邻近插值

针对降噪的带噪图像相加 $f(x,y)$,$g(x,y)$表示什么

考虑函数
$g(x,y)=f(x,y)+\eta (x,y)$
$f(x,y)$ 原图像即污染后图像
$g(x,y)$ 无噪声图像
$\eta (x,y)$ 加性噪声

chapter 3

灰度变换是什么

指根据某种目标条件按一定变换关系逐点改变源图像中每一个像素灰度值的方法。目的是为了改善画质，使图像的显示效果更加清晰。

灰度变换分为集中

  1. 对数变换
  2. 伽马(幂律)变换
  3. 分段线性函数变换
    1. 对比度拉伸
    2. 比特位分层
    3. 灰度级分层
  4. 灰度反转

进行灰度变换时对图像的影响是什么

将图像中的像素的灰度值进行改变。

直方图是什么

图像直方图是反映一个图像像素分布的统计表，其实横坐标代表了图像像素的种类，可以是灰度的，也可以是彩色的。纵坐标代表了每一种颜色值在图像中的像素总数或者占所有像素个数的百分比。

直方图均衡化是什么

是一种增强图像对比度的方法,其主要思想是将一副图像的直方图分布变成近似均匀分布,从而增强图像的对比度。直方图均衡化是输入图像中各灰度级别通过式子映射到输出图像中，该灰度级别对应的Y值不变。通过这样处理能达到图像中灰度级别均衡分布的目的

直方图均衡化是将原图像通过某种变换，得到一幅灰度直方图为均匀分布的新图像的方法，这样增加了像素灰度值的动态范围，从而达到增强图像整体对比度的效果。

直方图匹配(规定化)

又称直方图规定化。是指将一幅图像的直方图变成规定形状的直方图而进行的图像增强方法。有时我们希望处理后的图像具有规定的直方图形状可能更有用。这种于产生处理后有特殊直方图的方法称为直方图匹配。

空间滤波和卷积有什么区别他们是什么

卷积：
滤波器旋转$180^。$然后与图像进行相关操作。
空间滤波：
滤波器与图像做相关操作。

锐化空间滤波器有几个

使用二阶微分锐化图像：拉普拉斯算子
使用一阶微分也就是梯度锐化图像：sobel算子

chapter 4

图像的频率域是什么

指从函数的频率角度出发分析函数。频率是横坐标，振幅是纵坐标。傅里叶变换得到的正余弦函数的频率。

傅里叶变换是$f(t)$乘以正弦项的展开,正弦项的频率由$\mu$的值决定。因为积分后左边的唯一变量是$\mu$所以我们说傅里叶变换域是频率域,而图像的傅里叶变换后同样也是频率域。

傅里叶变换是什么

对于任意周期函数都可以表示为不同频率的正弦/余弦之和的形式。每个正弦/余弦都乘以不同的系数。对于非周期性函数也可用正弦/余弦乘以加权的函数积分来表示。这种公式就是傅里叶变换

图像信息是连续的为什么能进行傅里叶变换

图像信息经过冲激后可以得到离散的图像。离散的图像可以经过傅里叶变换,所以图像信息可以经过傅里叶变换。

保存下来的图像是离散的为什么能进行傅里叶变换

图像信息是连续的但是我们使用矩阵来保存图像就是离散的，经过取样后的
然后连续的傅立叶可以推广到离散函数上

取样的三种情况及混淆

欠采样：采样频率小于最高频率的两倍
临界采样：采样频率等于最高频率的两倍
过采样：采样频率大于最高频率的两倍

欠采样会导致混淆。

最高频率两倍的采样率被称为奈奎斯特采样率。

以低于奈奎斯特采样率的采样,最终结果会是周期重叠,这样会导致变换后的周期被来自邻近的周期频率破坏,然后方变化会产生一个被破坏了的函数。这种效果就被称为频率混淆或者混淆。

傅里叶变换的性质

  1. 对称性
  2. 周期性
  3. 平移不影响傅里叶变换的幅度值,空间域旋转多少,频率域就会旋转多少
  4. 若对分别在$t$和$z$方向上所取的$M \times N$个样点组成。令$\Delta T$和$\Delta Z$表示样本间的间隔则离散频率域变量间的间隔分别由$\Delta u=\frac{1}{M \Delta T}$和$\Delta v=\frac{1}{N \Delta Z}$

傅里叶谱和相角

图像经过傅里叶变换后我们可以的得到两个矩阵,一个代表实部一个代表虚部。我们将虚部平方和实部平方相加后再开方最后得到一个矩阵,那个就是傅里叶谱,如果我们将虚部与实部相除再对其去arctan则得到的角就是相角。

others problem

题目集合1
题目集合2

发表于

绪论

一幅图像可以定义为一个二维函数f(x,y),其中x,y是空间坐标,而在任何一对空间坐标(x,y)处的幅值f称为图像在该点的强度、灰度。当x,y和灰度值f是有限的离散数值时,我们称该图像为数字图像。
 
数字图像：数字图像是由有限数量单元的元素组成,每个元素都有一个特定的位置或者幅值。这些元素称为图画元素、图像元素、像素。
 
数字图像处理：借助于数字计算机来处理图像。
 
低级处理：涉及初级操作,如降低噪声的图像预处理、对比图增强和图像锐化。低级处理以输入、输出都是图像为特征。
 
中级处理：涉及诸多任务,如分割(把一幅图像分割为不同区域或则目标),减少这些目标物的描述,以使其更适合计算机处理以及对不同目标的的分类(识别)。中级处理以输入为图像但是输出为从这些图像中提取的特征(边缘、轮廓及各类标识)为特征。
 
高级处理：涉及”理解”已识别目标的总体,就像图像分析一般,以及连续统一体的远端执行与视觉相关的功能。
 

数字图像处理基础

眼睛：三层膜包括。角膜、巩膜外层 脉络膜 视网膜。
 
亮度适应级别：对于任何条件,视觉系统当前灵敏度级别称为亮度适应级别。原因：视觉系统不能同时在一个范围内工作被称为亮度适应。
 
对于不同的强度的边界区域会出现下冲,上冲现象。
 
没有颜色的光被称为单色光,无色光。唯一属性强度或大小。单色光的强度从黑色到灰色变化,最后到白色。灰度级用来描述单色光的强度。
 
灰度级：从黑色(0)到白色(L-1)的单色光的度量范围。
 
灰度图像：单色光图像。
 
三个基本量描述彩色光源的质量：发光强度(从光流出的能量总量用瓦特W来度量)、光通量(流明数lm度量。给出了观察者从光源感受到能量)、亮度(主观描绘子,具体体现了强度的无色概念)。
 
一副图像的x和y坐标及幅值都可能是连续的。为将他们转换为数字形式,必须对坐标和幅值进行取样操作。对坐标进行数字化称为取取样。对幅值数字化称为量化。
 
由一幅图像的坐标张成的实平面部分称为空间域。x,y被称为空间变量或者空间坐标。
 
处于储存和量化硬件考虑,灰度级数通常取为2的整数次幂。
 
动态范围：灰度跨越的值域非正式的称为动态范围。系统的最大可度量灰度(取决于饱和度。饱和度：超过这个值就要被剪掉的最高值)与最小可检测灰度(取决于噪声)之比。
 
灰度分辨率：灰度级中可分辨的最小变化。

内插

内插：用已知数据来估计未知位置的数值的处理。
图像内插：为了覆盖每个点赋以灰度值。

  1. 最邻近插值
  2. 双线性插值
  3. 双三次插值

双线性插值：$v(x,y)=ax+by+cxy+d$使用四个点为基准点。
双三次插值：$v(x,y)$ = $\sum{i=0}^3\sum{j=0}^3a_{ij}x^iy^j$使用16个点为基准点。

邻接&&邻域

  1. 四邻域：$(x+1,y), (x,y+1), (x-1,y), (x,y-1)被称为N_4(p)$
  2. D邻域：$(x+1,y+1), (x+1,y-1) ,(x-1,y+1) ,(x-1,y-1)被称为N_D(p)$
  3. 8邻域：$包含N_4(p)和N_D(p)被称为N_8(p)$
  4. m邻接/混合邻接：$设p在N_4(q)或者p在N_D(q)中(p,q在v中),且N_4(p) \bigcap N_D(q) \bigcap v = \emptyset 称v中的数值p,q是m邻接的$
    前两种邻域称为4邻接,8领域称为8邻接。
    邻接
     

连通性、边界、区域

设$S$为一个像素子集。如果$S$的全部像素之间存在一个通路则称两个像素$p,q$是连通的。对于$S$中任何像素$p,S$中连通到该像素的像素集称为$S$的连通分量。如果$S$中只有一个连通分量则称,集合$S$为连通集。
 
如果$R$是图像的一个像素子集,且为连通集则称$R$为一个区域。两个区域将他们联合成一个连通集则称他们为邻接区域。不邻接区域称为不邻接区域。
 
设一幅图像中有$K$个不连接的区域,即$R_k,k=1,2,3…..,K$且他们都不接触图像的边界。令$R_u$为$K$个区域的并集,$(R_u)^c$为补集。则我们称$R_u$为图像前景。$(R_u)^c$为图像背景。
 
区域$R$的边界：与$R$的补集用的点邻接。一个区域及其背景的邻接要根据8连通定义。此为内边界。

距离

欧式距离：$D_e(p,q)=[(x-s)^2+(y-t)^2]^{1/2}$
城市区间距离$D_4$距离：$D_4=|x-s|-|y-t|$
$D_8$距离棋盘距离：$D_8(p,q)=max(||x-s,|y-t|)$
$D_m$：最短m通路距离。

工具介绍

  1. 针对降噪的带噪音图像的相加
  2. 增强差别图片的相减
  3. 使用图像相除或者相乘来校正阴影

灰度变换和空间滤波

空间域：空间域是包含图像像素的简单平面。
空间域技术：直接操作图像的像素。
灰度变换：指根据某种目标条件按一定变换关系逐点改变源图像中每一个像素灰度值的方法。目的是为了改善画质，使图像的显示效果更加清晰。

滤波

空间滤波
考虑一个式子
$g(x,y)=T[f(x,y)]$
其中$f(x,y)$是输入图像。$g(x,y)$是处理后的图像。$T$是在点$(x,y)$处领域上定义的关于$f$的一种算子。

  1. 设有一个算子$T$
  2. 邻域原点从一个像素到另一个像素移动。
  3. 对领域中的像素应用算子$T$,并在该位置输出
  4. 对于任意指定位置$(x,y)$,输出图像$g$在这些坐标出的值,等于对$f$中以$(x,y)$为原点的邻域应用算子$T$的结果。
  5. 当该邻域的原点位于图像的边界上时,部分领域将位于图像外部,此时不是用$T$做指定的计算时忽略外侧邻点就是使用0或者其他的指定灰度值进行填充。

以上的操作为空间滤波,其中邻域与预定义的操作一起被称为空间滤波器。

基本的灰度变换函数

图像反转

将得到的图像的灰度图反转。
得到的灰度级范围$[0,L-1]$。反转公式$s=L-1-r$。
灰度图反转

对数变换

变换公式为$s=clog(l+r)$。其中$c$为常数,假设$r\geq0$。变换输入的$r$可达到输出的$s$的图像。
对数变换
对数变换图形

对于对数变换来说。我们可以从图中看出,对数变换将输入范围内较窄的灰度值映射到到较宽的的灰度值,或者将范围较宽的灰度值映射到范围较窄的灰度值。反对数与此相反。

幂律(伽马)变换

考虑公式。
$s=cr^\gamma$。其中$r,\gamma$为常数,式子可以写成$s=c(r+\varepsilon)^\gamma$。但是其中的$\varepsilon$可以忽略不记。对于不同的$r和c$可以得到以下图像。
伽马变换
和对数变换不同的是随着$\gamma$的变换我们可以得到一族可能的变换曲线,可以看到当$c,r$不变时,$\gamma 和 \gamma<1 $ 生成的曲线完全相反。
$c=\gamma=1$时变成了恒等变换。

用于图像获取、打印和显示各种设备根据幂律来产生响应。用于校正这些幂律现象的处理方式被称为伽马校正。
伽马校正

伽马校正不会改变图片的亮度但是会改变彩色图片中的红、绿、蓝的比率。

分段线性变换函数
对比度拉伸动

低对比度图像由于照明不足、成像传感器态范围太小、图像获取过程中镜头光圈设置错误引起。对比度拉伸是扩展图像灰度级动态范围的处理,因此可以跨越记录介质和显示装置的全部灰度范围。
对比度拉伸

灰度级分层

将感兴趣的灰度范围突出出来。

  1. 使用二值函数,将感兴趣设为一个值其他的设为另外一个值
  2. 将感兴趣的变亮或者变暗。其他不变。
    灰度分层函数
    比特位分层
    例如在256灰度图中(灰度级范围$[0-255]$)每个像素灰度由8个比特组成。
    用于突出特定比特来突出图像的外观。
    比特分层函数

比特分层实例

直方图处理

直方图均衡

是一种增强图像对比度的方法,其主要思想是将一副图像的直方图分布变成近似均匀分布,从而增强图像的对比度。直方图均衡化是输入图像中各灰度级别通过式子映射到输出图像中，该灰度级别对应的Y值不变。通过这样处理能达到图像中灰度级别均衡分布的目的

直方图匹配

又称直方图规定化。是指将一幅图像的直方图变成规定形状的直方图而进行的图像增强方法。有时我们希望处理后的图像具有规定的直方图形状可能更有用。这种于产生处理后有特殊直方图的方法称为直方图匹配。

空间滤波基础

空间滤波机理

空间滤波器组成

  1. 一个邻域(通常是一个小矩形)
  2. 对该邻域所包围的图像像素执行的预定义操作组成。

滤波产生新的像素,新的像素坐标等于邻域中心的坐标,像素的值是滤波操作的结果。

如果滤波器在图像像素上执行的是线性操作则该滤波器被称为线性滤波器。否则为非线性滤波器。

相关：滤波器模板移过图像并计算每个位置乘积之和的处理,是滤波器位移的函数。
卷积：与相关相似,但是将滤波模板反转了$180^。$
离散单位冲激：包含单个1而其余都是0的函数称为离散单位冲激。
某个函数与单位冲激相关,则会在改冲激位置产生该函数的一个翻转。
卷积的一个基本特性：某个函数与某个离散单位冲激卷积,得到该函数在该冲激出的一个副本。
线性滤波：实现乘积求和操作。
二维高斯函数具有钟型,标准差控制钟的”紧度”。

平滑空间滤波器
平滑线性滤波器

输出(响应)：包含在滤波器模板邻域内的像素的简单平均值也被称为均值滤波器。可以把他归为低通滤波器。
所有系数都相等的空间均值滤波器被称为盒装滤波器。

统计排序滤波器(非线性)

是一种非线性空间滤波器。

中值滤波器：处理椒盐噪声很有效。使拥有不同的灰度的点看起来更接近他的相邻点。
其他：最大值滤波器、最小值滤波器等。

锐化空间滤波器

主要目的：突出灰度的过度部分也就是细节。
一维函数$f(x)$的一维积分基本定义是差。
$\frac{\partial f}{\partial x}=f(x+1)-f(x)$
二阶微积分定义为差分也就是细节。
$\frac{\partial^2 f}{\partial x^2}=f(x+1)+f(x-1)-2f(x)$
扩展到x,y方向上。
x方向上
$\frac{\partial^2 f}{\partial x^2}=f(x+1,y)+f(x-1,y)-2f(x,y)$
y方向上
$\frac{\partial^2 f}{\partial x^2}=f(x,y+1)+f(x,y-1)-2f(x,y)$

拉普拉斯算子

定义
$\nabla ^2f(x,y)=\frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}$
公式
$\nabla^2 f(x,y)=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)+4f(x,y)$

laplas

非锐化掩蔽和高提升滤波

印刷业和出版业使用。

  1. 模糊原图
  2. 从原图中减去模糊图像得到模板
  3. 将模板加到原图上

设$\overline{f}(x,y)$为模糊图像则我们得到模板$g_{mask}(x,y)$则

当$k>1$称该处理为高提升滤波。当$k<1$不强调非锐化模板的贡献。
$k=1$则称为非锐化遮掩。

使用一阶微分锐化(非线性)图像——梯度

梯度：指出了在位置$(x,y)$处$f$的最大变化率方向。
sobel算子：使用X方向的梯度和Y方向的梯度的绝对值之和作为该点的输出像素值。
sobel

频率与滤波

傅里叶变换

对于任意周期函数都可以表示为不同频率的正弦/余弦之和的形式。每个正弦/余弦都乘以不同的系数。对于非周期性函数也可用正弦/余弦乘以加权的函数积分来表示。这种公式就是傅里叶变换。
特征：用傅里叶技术或者变换得来的函数特征完全可以通过傅里叶反变换来重建且不会丢失任何信息。

离散冲激是一个普通函数。

卷积定理：频率域的卷积等于空间域的相乘。空间域的相乘等于频率域的卷积。
带限函数：对于中心点为原点的有限区间(带宽)之外的频率,其傅里叶变换为零的函数。
取样定理：如果以超过函数最高频率两倍的取样率来获得样本,连续带限函数能完全由样本集恢复。
$\frac{1}{\Delta T}>2\mu_{max}$。
完全等于最高频率的两倍的采样率称为奈奎斯特取样率。

三种取样：过取样、欠取样、临界取样。

低通滤波器：消除所有较高的频率,让低频率通过。
高通滤波器：消除较低的频率,让高频率通过。

使用低于奈奎斯特取样率的频率取样会导致周期重叠。这就是频率混淆,或简称混淆。
波尔模式(波纹)：两个近似登间隔的光栅之间产生的差拍模式。

图像的空间域是指图像平面所在的二维平面，对于空间域的图像处理主要是对像元灰度值的改变，其位置不变。

图像的频率域是图像像元的灰度值随位置变化的空间频率，以频谱表示信息分布特征，傅立叶变换能把遥感图像从空间域变换到只包含不同频率信息的频率域，原图像上的灰度突变部位、图像结构复杂的区域、图像细节及干扰噪声等信息集中在高频区，，而原图像上灰度变化平缓部位的信息集中在低频区。

空间域的旋转与频率旋转等效。

任意函数都可以表示为一个奇函数部分和一个偶函数部分的和(都可以含有虚部和实部)。
对频谱图翻转：将低频信息集中到中心点,更好得进行滤波。
高频信息：尖锐过度造成。
低频信息：缓慢变化的灰度成分。

使用频率滤波器平滑图像

理想低通滤波器
布特沃斯低通滤波器
高斯低通滤波器
其他低通滤波器

使用频率滤波锐化图像

理想高通滤波器
布特沃斯高通滤波器
高斯高通滤波器
频率域拉普拉斯滤波器

选择性滤波

处理指定频率段或频率矩形的小区域

  1. 带阻滤波器/带通滤波器
  2. 陷波滤波器
带阻滤波器
  1. 理想带阻滤波器
  2. 布特沃斯带阻滤波器
  3. 高斯带阻滤波器
陷波滤波器

可以用中心已被平移到陷波滤波器中心的高通滤波器的乘积来构造。
使用n阶布特沃斯带阻滤波器。

图像复原与重建

图像的退化/复原过程模型

退化过程：被建模为一个退化函数和一个加性噪音。

图像复原的目的就是获得原始图像的一个估计$\hat{f}(x,y)$。我们希望这一估计能尽可能的接近原始输入图像。

图像复原模型

噪声模型

主要来源于图像的获取和传输过程。

频率特性：指的是傅里叶域中噪声的频率内容。

一些重要的噪声概率密度函数
  1. 高斯噪声
  2. 爱尔兰(伽马)噪声
  3. 指数噪声
  4. 均匀噪声
  5. 瑞利噪声
  6. 脉冲(椒盐)噪声
周期噪声

周期噪声可通过频率域滤波显著减少。

噪声参数估计

周期噪声趋于产生频率尖峰。

只存在噪声的复原——空间滤波

均值滤波器
  1. 几何均值滤波器
  2. 算数均值滤波器
  3. 谐波均值滤波器
  4. 逆谐波均值滤波器
统计排序滤波器
  1. 中值滤波器
  2. 最大值和最小值滤波器
  3. 中点滤波器
  4. 修正的阿尔法均值滤波器
自适应滤波器
  1. 自适应局部降低噪声滤波器
  2. 自适应中值滤波器

使用频率域滤波消除周期噪声

带阻滤波器
带通滤波器
陷波滤波器
最佳陷波滤波器

彩色图像处理

彩色基础

光的三原色：蓝色、绿色、红色。
颜料(印刷业)三原色：深红色、青色、黄色。

前者颜色叠加可以生成各种颜色。后者则是减去另一种颜色,其原色定义为减去或者吸收光的一种原色,并反射或传输另外两种原色。

灰度级仅提供一个亮度标量度量,他的范围是从黑色到灰色最终到白色。

描述光源质量的三个基本量：辐射、光强、亮度。

辐射：从光源流出的能量总量。从光流出的能量总量用瓦特W来度量。
光强：流明数lm度量。给出了观察者从光源感受到能量。
亮度：主观描绘子,具体体现了无色的强度概念。

通常用于区别不同颜色特性：亮度、色调、饱和度。

亮度：主观描绘子,具体体现了无色强度概念。
色调：波长混合中主波长有关的属性。表示感知者感知的主要颜色。
饱和度：相对纯净度,一个光混合白光的量。混合的越多饱和度越低。

色调和饱和度一起称为色度。
所以颜色可以用亮度、色度来表征。

颜色模型

颜色模型(彩色空间\彩色系统)目的：某些标准下用通常可以接受的方式方便对颜色加以说明。

RBG 模型

红色、蓝色、绿色

面向硬件,用于彩色监视和一大类彩色视频摄像机。

各个系统的颜色不同,所以有一个通用色色彩集,独立于硬件。被称为稳定RGB色集合,或者称为全系统稳定色集合。互联网中这种结合被称为Web色或者稳定浏览器色。

216色中每个颜色只可区：0、51、102、153、204、255。

CMY CMY(K)模型

用于打色打印机。

等量的CMY三原色可以生成黑色但是不纯于是出现了CMYK,其中K为黑色。

CMY：青色、深红色、黄色
CMYK：青色、深红色、黄色、黑色

HSI 模型

便于人来描述图像的工具。
色调、饱和度、强度

伪彩色处理

灰度分层

如果一副图像被描述成三维函数,则分层的方法可视为放置一些平行于该图像的的坐标平面的平面。然后在这个平面相交的区域中”切割“函数图像,平面上方设置为一种彩色,下方设置为另一种彩色。

灰度分层模型

灰度分层2
灰度分层2

灰度到彩色变换
  1. 对像素的灰度进行三个独立变换(RGB)。
  2. 将变换结果分别送到彩色监视器的红、绿、蓝通道。
  3. 合成一幅图像。

全彩色图像处理

分为两类。1. 分别处理每一幅分量图像,然后由分别处理过的分量图像来形成一副处理过的合成彩色图像。2. 直接处理像素。

对于第一种情况要满足两种情况。

  1. 处理必须对向量和标量都可用
  2. 对向量的每个分量的操作杜宇其他分量都必须独立。
公式

$g(x,y)=T[f(x,y)]$

补色

在色彩环上,与色调直接相对的另一端被称为补色。补色对于增强嵌在彩色图像暗区的细节很有用。

彩色分层

把不感兴趣的之外的彩色设为中性色。

色调和颜色校正

与数字摄像机、平板扫描仪和喷墨打印机相连,个人计算机就成了数字暗室,从而允许我们对图像进行色调调整和彩色校正。

平滑和锐化

彩色图像平滑
如灰度图像平滑一样,但是使用分量向量代替灰度标量值。

彩色图像锐化
可使用laplas。

基于彩色的图像分割

基于HSI彩色空间的分割
RGB向量空间中的分割
彩色边缘检测

彩色图像中的噪声

使用中值操作时需要找到一种有意义的向量排序方式。

彩色图像压缩

对象：每个彩色像素的分量。

发表于

disjkstra

  1. 从队列中选取最短的边
  2. 以该边的终结点为头进行松弛操作并将终结点标记以便后续不在遍历该点
  3. 将松弛过的点加入要遍历的队列中
  4. 重复 1-3 直至遍历完所有结点

bellman-ford

  1. 遍历边集合,对所有可以进行松弛操作的边进行松弛操作
  2. 将步骤1重复n次

spfa

  1. 遍历队列中的点的边进行松弛操作
  2. 将松弛的点放入队列中
  3. 重复1-2直至无法更新

差别

  1. disjkstra基于贪心思想,当有负权边的时候可能得不到正确答案
  2. bellman-ford 算法可以算出通过k个路径可以到达的点
  3. spfa算法基于bellman-ford 算法进行优化。bellman-ford算法中未松弛过的点说明已无法松弛,所以后续如果再遍历则是浪费时间,所以spfa对其进行优化将松弛过得点放入队列中,以便后续遍历
  4. 对于寻找k条路径可以到达的点仍需要使用bellman-ford算法
  5. 当求负权环的时候,使用spfa算法。需添加一个cnt数组记录到达该点所走过的路径数,当路径大于n时,说明经过了n+1个点。由抽屉原理可得至少有一个点经过了两次
    即存在负环。其中dis数组也不需要初始化。因为是求是否有负权环所以一定可以更新dis数组。

发表于

状态压缩dp

蒙德里安的梦想

motana

解法：
数据很小,所以这题我们可以考虑状压dp。我们考虑一种解法。先放横着的1 x 2方格 然后再用2 x 1 方格将空处填满。则状态dp[i][j]为前i-1列已经排好,且第i-1列插入的1 x 2 小方格的状态为j,此时第i行状态为j的情况的所有合法数。设dp[i-1][k]为可以转移到dp[i][j]的状态。当状态j合法的时候,集中连续的空格应该为偶数个,即j中连续的0应为偶数个。
dp[i-1][k]中k合法的条件。

  1. j,k中所插入方格不在同一行,即j,K无交集 -> j&k==0
  2. i列j状态的连续空格被i-i列中k状态中延伸出来到i行的方格占据后连续的空方格仍然是偶数个 -> j|k 状态合法 -> j|k 中连续的空格的个数为偶数。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include <sstream>
#include<set>
#include<bitset>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;



const int N=1<<12;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;

/*
        ***                ***************      ***************       ***
        ***                ***************      ***************       ***
        ***                      ***                  ***             ***
        ***                      ***                  ***             ***
        ***                      ***                  ***             ***
        ***                      ***                  ***
        *************      ***************            ***             ***
        *************      ***************            ***             ***
*/

ll dp[12][N];
bool st[N];
vector<int> vec[N];


int main() {
    int n,m;
    for(int i=0; i<1<<12; i++) {
        st[i]=true;
        bool flag=true;
        int cnt=0;
        for(int j=0; j<12; j++) {
            if(i>>j&1) {
                if(cnt&1) {
                    flag=false;
                    break;
                }
                cnt=0;
            } else cnt++;
        }
        if(cnt&1) flag=false;
        st[i]=flag;
    }
    for(int i=0; i<1<<12; i++) {
    vec[i].clear();
        for(int j=0; j<1<<12; j++) {
            if(!(i&j)&&st[i|j]) {
                vec[i].push_back(j);
            }
        }
    }

    while(scanf("%d%d",&n,&m),n||m) {

        memset(dp,0,sizeof dp);
        dp[0][0]=1;

        for(int i=1; i<=m; i++) {
            for(int j=0; j<1<<n; j++) {
                for(auto k:vec[j])
                    dp[i][j]+=dp[i-1][k];
            }   
        }
        printf("%lld\n",dp[m][0]);
    }
    return 0;
}

此处进行了一个优化,即提前将合法状态求出。所需要注意的是,优化步骤不可在大循环外一次性更行到1<<12。每个案例中的n,m不同,则可转移状态也不相同,所以依靠n,m来求出合法状态。

最短Hamilton路径

hamilton

解法:
将路径的选择压缩成二进制数。dp数组dp[i][j]则表示,到达路径i时是状态j的最小值,j为经过的路径的状态压缩。设k,i中有一条路径,则dp[i][j]=min(dp[i][j],dp[k][m]+value[k][i])。第k个点的状态m合法需满足以下条件。

  1. 状态m为已经到了k所以m中须有路径k,但是此时未到达i所以m中不可有路径i。状态j中,因为已经到达了点i,且经过点k所以状态j中须有路径i、k。
  2. j去除点i后还需要有点k -> j-(1<>K&1 == 1
    code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include <sstream>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;

const int N=1e5+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;


int mapp[25][25];
int cnt=0;

int dp[25][1<<21];
int main() {
    FAST
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%d",&mapp[i][j]);
        }
    }
    memset(dp,88,sizeof dp);
    dp[0][1]=0;

    for(int j=0; j<1<<n; j++) {
        for(int i=0; i<n; i++) {
            if(j>>i&1) {
                for(int k=0; k<n; k++) {
                    if(j-(1<<i)>>k&1) {
                        dp[i][j]=min(dp[i][j],dp[k][j-(1<<i)]+mapp[k][i]);
                    }
                }
            }
        }
    }
    printf("%d\n",dp[n-1][(1<<n)-1]);
    return 0;
}

发表于

前提

a,b,x为数轴上三个点
绝对值不等式
|x-a|+|x-b|>=|a-b|
当x位于a,b之间的时候x到a,b的距离最短

仓库选址解决

在一条数轴上有 N 家商店，它们的坐标分别为A1 ∼AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

  1. 将所有商店在数轴上的位置排序
  2. 将i,n-i+1的点配对
  3. 使用绝对值不等式
  4. 可以得出最小值点是n/2或者n/2+1的点

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include <sstream>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;



const int N=1e6+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;

int a[N];

int main() {    
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=abs(a[n/2]-a[i]);
    }
    printf("%d\n",ans);
    return 0;
}

发表于

多重背包

对于没有数据小的时候我们可以在完全背包的问题上加一重循环来判断取多少个物品,但是当数据量太大时就会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include <sstream>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;



const int N=1e6+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;

int w[N];
int v[N];
int s[N];
int dp[N];
int main() {
    int n,t;
    scanf("%d%d",&n,&t);
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&w[i],&v[i],&s[i]);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=t;j>=w[i];j--){
            for(int k=0;k<=s[i];k++){
                if(k*w[i]>j) break;
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
                ans=max(dp[j],ans);
            }
        }
    }
    printf("%d\n",dp[t]);
    return 0;
}

我们考虑多重背包的另外一种解法。将s[i]个物品拆成s[i]个一个物品放入数组中,这时题目转换成了01背包问题。在这个基础上我们可以做优化。
我们可以在拆分物品的时候做优化,将s[i]个物品不拆分为s[i]个一个物品而是拆分成floor(log2(s[i]))+1个数。

1
2
3
4
若我们想拆分 7
则我们可以拆成1、2、4份这样可以组成 1-7中任意的数
同理 拆分10 
可以拆成 1、2、4、10-7 也就是 1、2、4、3

拆分过后将数放入数组中,转换成01完全背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include <sstream>
#define FAST    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;



const int N=1e6+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double E=2.718281828459045;


int s,w,v;
int dp[N];
P pa[N*3];
int main() {
    int n,t;
    scanf("%d%d",&n,&t);
    int cnt=0;
    for(int i=0; i<n; i++) {
        scanf("%d%d%d",&w,&v,&s);
        int k=1;
        for(; k<=s; k*=2) {
            pa[cnt++]= {w*k,v*k};
            s-=k;
        }
        if(s>0) 
            pa[cnt++]= {w*s,v*s};
    }
    for(int i=0; i<cnt; i++) {
        for(int j=t; j>=pa[i].first; j--) {
            dp[j]=max(dp[j],dp[j-pa[i].first]+pa[i].second);
        }
    }
    printf("%d\n",dp[t]);
    return 0;
}

发表于

二分

本文只考虑闭区间即[l,r]

lower_bound

查找第一个大于等于x的数
查找左边界边界，因为当l>r时跳出，即l为r后一位时跳出，所以r始终要在左边界前面一位，所以当a[mid]>=x时r=mid-1

1
2
3
4
5
6
7
8
9
10
int binary_lower_bound(int l,int r,int x){
	int mid;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]<x){
			l=mid+1;
		}else r=mid-1;
	}
	return l;
}

upper_bound

查找第一个大于x的数
查找第一个大于c的数，循环在l>r时跳出，即r后一位时跳出，所以r只需比所求值小一位，所以当a[mid]>x时，r向左移动r-mid-1

1
2
3
4
5
6
7
8
9
10
int binary_lower_bound(int l,int r,int x){
	int mid;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]<=x){
			l=mid+1;
		}else r=mid-1;
	}
	return l;
}

其他模板

左边界

跳出循环条件为l==r,r为左边界时跳出。所以a[mid]==左边界,当a[mid]==x时,r=mid;

1
2
3
4
5
6
7
8
9
int left_bound(int l,int r,int x){
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]<x){
			l=mid+1;
		}else r=mid;
	}
	return l;
}

右边界

跳出循环条件为l==r,r为左边界时跳出。所以a[mid]==左边界,当a[mid]>x时,r需要向左靠近所以r=mid-1;

1
2
3
4
5
6
7
8
9
int right_bound(int l,int r,int x){
	while(l<r){
		int mid=l+r+1>>1;
		if(a[mid]<=x){
			l=mid;
		}else r=mid-1;
	}
	return l;
}

发表于

五层构架

  1. 应用层：通过引用进程间的交互来完成特定网络的连接。应用层协议，应用进程间通信 交互的法则。
  2. 运输层：为两台主机中进程之间的通信提供通用 数据传输服务。主要协议TCP、UDP。
  3. 网络层：为分组交换网上的不同主机提供 通信服务。选择合适的路由。主要协议IP协议。
  4. 链路层：将网络层的IP数据报 组成帧，在两个相邻的结点间的链路上 传送帧，检查纠错接收到的数据帧。每一帧包括数据和必要的控制信息。
  5. 物理层：物理层上所传数据为比特流，考虑怎样才能在各种计算机的传输媒体上传输数据比特流。传送信息所需要的媒介不为物理层 。
    1
    2
    3
    应用进程间->主机间进程->主机->主机->数据流
    进程间协议->提供主机间进程通信->寻找路由->封装成帧和控制信息->考虑传输的比特流的大小等参数
    TCP/IP协议为四层：应用层、运输层、网络层，网络接口层 
    1
    2
    3
    4
    TCP:传输控制协议
    提供面向连接的、可靠的数据传输服务单位，报文段(segment)
    UDP：用户数据报协议
    提供无连接、尽最大努力的数据传输服务（不保证数据传输的可靠性）、单位用户数据报
    协议的控制下，两个对等的实体间的通信使得本层能够向上一层提供服务。要实现本层协议，还需要下面一层所提供的服务。
    服务是垂直的，协议是水平的

    物理层

    用于物理层的协议也被称为规程。

    四大特性

  6. 机械特性：接口所用接线器的形状和尺寸等
  7. 电气特性：电平的范围
  8. 功能特性：某范围电平的意义
  9. 过程特性：不同功能的各种可能事件的出现顺序

数据通信系统：源系统（发送端、发送方）、传输系统（传输网络）、目的系统（接收端、接收方）
单向通信：单工信道，只有一个方向课通信
双向替换通信：半双工信道，一方发一方接收，一段时间过后可以反过来
双向同时信道：全双工信道，双方可以同时发送和接收信号
基带信号：来自信源的信号
调制：解决基带信号中的低频分量或直流分量，使信道可以传输（许多信道不能传输这种低频分量或直流分量）

调制

  1. 基带调制：对基带信号的波形进行变换，使得与信道特性相适应，变换后仍然是基带信号，这种调制是吧一种数字信号转换成另外一种数字信号，大多数人愿意把这种过程称为（编码）
  2. 带通调制：使用载波进行调制，将基带信号的频率范围搬到较高的频段，并转化为模拟信号、调制之后的信号被称为带通信号。

从概念上讲，限制码元在信道上传输速率的因素有两个：信道能通过的频率的范围，信噪比；
奈氏准则：在任何信道中，码元的速率都有上限，传输速率超过此上限，就会出现严重的码间串扰的问题，使接收端对码元的判断成为不可能。
信噪比：S/N 信号的平均功率/噪声的平均功率
信噪比=10log10(S/N)
香农公式：C=Wlog2(1+S/N)
C：信道极限传输功率
W：信号的带宽（Hz为单位）
频分复用：所有用户在同一时间占用不同的带宽资源
时分复用：所有用户在不同时间占用同样带宽资源
统计时分复用：将多个用户数据集中起来通过高速路线发送到一个远地计算机
github
本地
波分复用：光的频分复用
码分复用：接收到的为所有信息的叠加

Tx为其他站的码片不止一个

3.数据链路层

数据链路层三个基本问题：封装成帧、透明传输、差错检测
MTU：最大传送单元
数据链路层的透明传输：对于数据来说本层为透明的，没有对数据做任何处理，但是去确实经过本层。无论什么样的比特组合·的数据，都能够按照原样没有差错地通过这个数据链路层。
在帧的头部和尾部都有一个控制符标识帧的开始和结束。
字节填充（字符字符填充）：为区别控制符和数据部分，解决透明传输问题。
在SOH，EOT前加一个转义字符（比如：ESC），如果数据本身还有转义字符则在转义字符前面添加一个转义字符。
误码率BER：传输错误比特数/传输总比特数

CRC

循环冗余检验（CRC）：把数据划分组。在每组后面添加n位冗余码。
循环冗余检验：只能做到对帧的无差错接受。实现无比特差错。
模二运算：加法和减法的时候不进位或者借位
冗余码：将待传数据M长度为k（2进制）与2n相乘，相当于为M尾部添加了n位0.得到（k+n）长度的数据。再用的得到的数据除以除数P（长度为n+1）得到n位余数加在之前的（k+n）位数据上。后面的n位就是冗余码。
如果传输过程无差错，则帧除以余数P得到的是0
FCS：在数据后面添加冗余码的的检错方法
CRC：实现FCS的一种方法

PPP协议点对点协议

需满足要求：简单、封装成帧、透明性、支持多种网络协议、支持多种类型链路、差错检测、检测连接状态、最大传送单元、网络层地址协商、数据压缩协商

PPP协议组成
  1. 将IP数据报封装到串行链路的方法
  2. 建立、配置和测试数据连接的链路控制协议LCP
  3. 网络控制协议NCP
帧组成
F A C 协议 信息部分 FCS F
7E FF 03 协议 数据部分 冗余码 7E
1 1 1 2 MTU=1500 2 1

AC字段目前未规定明确意义，实际上是未携带PPP协议的信息

协议部分为0x0021时是IP数据报0xC021是PPP链路控制协议LCP

为解决数据部分与标志字段的冲突，解决有两种方式。

  • 异步传输（连续字符）：字节填充
    • 将0x7E 转换成 0x7D 0x5E
    • 将0x7D（即转义字符）转换成0x7D 0x5D
  • 同步传输（连续比特）：0比特填充
    • 每五个1填充一个0避免出现6个1（0x7F：01111110）

局域网

特点：1.为一个单位所拥有的。2.地理范围和站点数目均有限制
以太网是局域网的一个标准
共享信道

  1. 静态划分
    • 如频分复用、波分复用等
  2. 动态划分
    • 随机接入：所有用户随意发送信息。
    • 受控接入：不可随意发送信息，需要收到控制

为了使数据链路层更好适应局域网标准IEEE802将其拆分为两个子层：LLC逻辑链路控制子层 MAC媒体接入控制子层。后续采用另外一协议基本只剩下MAC协议
计算机与外界局域网通过通信适配器连接。上有RAM和ROM

以太网

帧间最小间隔：9.6μs
最短有效帧：64字节
为了通信简便以太网采取两种措施

  1. 无连接。不可靠连接。同一时间只允许一台计算机发送数据=>CSMA/CD（载波监听多点接入/碰撞）检测
  2. 发送的数据都使用曼彻斯特编码

电磁波在电缆中的传播时间约为5μs

CSMA/CD：协议实质是载波监听和碰撞检测

  1. 多点接入：多个设备接入
  2. 载波监听：监听信道上是否有信号
  3. 碰撞检测：检测是否有有碰撞（信号叠加会导致电压变化）。

总线型=>不可能是全双工=>半双工通信/双向交替通信
争用期/碰撞窗口：2 * 总线端到端的传播时延（只有过了这段时间才可知道到底有没有碰撞）

以太网在发生碰撞后使用截断二进制指数退避算法。在检测到碰撞后的一个随机时间后再次发送数据

截断二进制退避算法：
r=random [ 0,1,2…..2k ]
k=min[重传次数,10]
等待时间t=r*争用期
重传16次未仍然不成功丢带该帧，向高层报告。

使用集线器的星型以太网，逻辑上仍然是一个总线网，仍然使用CMSA/CD协议
集线器工作在物理层仅仅只做转发比特的工作
单程端到端时延b，帧的发送时延c
a=b/c
极限信道利用率S=b/(c+b)=>S=1/(1+a)

MAC层

硬件地址被称为物理地址、MAC地址（只存在MAC帧中）。固化在适配器的ROM中48位
前24位需向注册管理机构RA购买，名称为组织唯一标识符OUI，通常公司标识符
后24位由公司指派，被称为扩展标识符。
MAC地址的前24位不能用来标志一个公司，可能有好几个公司购买一个OUI。

第一字节最低位：0为单个站地址。1位组地址，用来多播。
第一字节最低第二位：0全球管理。1本地管理。（G/L位，以太网不太会理会）。

路由器每连接到一个网络都需要一个MAC地址。（同时连接两个网络时需要两个MAC地址和两个适配器）。

适配器有过滤功能。当适配器每接收到一个MAC帧的时候就先用硬件检查MAC帧中的目的地址。如果是发往本站的帧，然后做其他处理，不然丢弃。“发往本站的帧”包括三种：

  1. 单播帧（一对一），收到的帧的MAC地址与本站硬件相同
  2. 广播（一对全部 ），发送给本局域网上的所有站点的帧
  3. 多播（一对一多），发给本局域网上一部分站点的帧

只有目的地址才可使用多播地址或者广播地址。
广播地址：48位全1
混杂方式：收到帧先收下来。可以用做窃听，或者监事分析以太网流量，以便找出提高网络性能的具体措施。嗅探器（Sniffer）。

MAC帧构成：
假定为IP数据报
假定为IP数据报

以太网发送数据使用曼彻斯特编码，每一个码元都有一次电压变化。发送完最后一个码元之后发送方适配器无电压变化。接收方可以很容易找到帧结束地方。

以太网最小有效帧为64字节=>数据部分最小长度为46字节。
插入八字节：考试1/0交替，为了使接收的适配器在接收的时候调成时钟保证与数据保持位同步，后续两个连续1标识MAC帧的到来。
FCS使用CRC。
无效帧

  1. MAC帧不为整数个字节
  2. FCS查出数据有误
  3. MAC客户数据字段不在46-1500自己之间

拓展以太网

物理层拓展
  1. 使用集线器，将多个碰撞域连接成一个更大的碰撞域（冲突域），前提是每个以太网（每系）的以太网技术相同。
    数据链路层扩展
    网桥：对收到的帧根据MAC的目的地址进行转发和过滤。
    交换机：交换式集线器，工作在数据链路层
    使用交换机扩展以太网
    以太网交换机：
  2. 全双工工作模式，具有并行性。相互通信的主机都是独占传输媒体，无碰撞的传输数据。
  3. 是一个即插即用的设备，内部的帧交换表（地址表）是通过自学习算法自动地逐渐建立起来的。
  4. 以太网交换机使用了专用的交换结构芯片，用硬件转发，其转发速率要比使用软件转发的网桥快很多。
  5. 用户独享宽带，增加了总容量

虚拟局域网vlan

由一些局域网网段构成的鱼物理位置无关的逻辑组。，这些网段具有某些共同的需求。每一个vlan帧中都有一个明确的标识，指明发送这个帧属于哪一个vlan。
优点：

  1. 改善了性能
  2. 简化了管理
  3. 降低了成本
  4. 增加了安全性

划分方式：

  1. 基于交换机端口
  2. 基于MAC地址
  3. 基于所使用的协议
  4. 基于IP子网地址
  5. 基于高层应用或服务

vlan的以太网帧

高速以太网

超过或者达到100Mb/s

100BASE-T
  1. 100BASE-T 在双绞线上传送 100 Mbit/s 基带信号的星形拓扑以太网，仍使用 IEEE 802.3 的 CSMA/CD 协议。
  2. 被称为快速以太网
  3. 可在全双工方式下工作而无冲突发生。在全双工方式下工作时，不使用 CSMA/CD 协议。
  4. 保持最短帧长不变，但将一个网段的最大电缆长度减小到 100 米。
    帧间时间间隔从原来的 9.6 s 改为现在的 0.96 s 。
吉比特以太网

使用全双工/半双工
全双工使用CMSA/CD协议，半双工不使用
为保持 64 字节最小帧长度，以及 100 米的网段的最大长度，吉比特以太网增加了两个功能：
载波延伸 (carrier extension)
分组突发 (packet bursting)
为保持信道利用率高，所以规定MAC最小512字节，不足512字节进行填充（载波延伸）
分组突发：第一个短帧使用载波延伸，后续短波不需要填充，但是有必要的帧间间隔。
全双工，不需要，载波延伸和分组突发。

发表于

1.总线的概念

  • 总线是各个信息的传输线，是各个部件共享的传输介质
  • 有串行和并行传输方式，并行传输一般比较短

    2.总线的分类

  • 片内总线：芯片内总线
  • 系统总线：计算机各个部件之间的信息传输线
    • 数据总线：双向和机器字长和储存字长有关
    • 地址总线：单向与存储地址和I/O地址有关
    • 控制总线：有出有入
  • 通信总线
    • 计算机之间或者计算机系统的与其他系统之间的通信
    • 有串行和并行传输方式

      3.总线的特性和性能指标

  • 总线的物理实现
    • 总线印刷在电路板上
  • 总线特性
    • 机械特性：尺寸、形状、管脚数、排列顺序
    • 电气特性：传输方向和有效电平范围
    • 时间特性：信号的时序关系
    • 功能特性：每根传输线的类型（数据、地址、控制）
  • 总线的性能指标
    1. 总线宽度：数据线根数
    2. 标准传输率：每秒传输最大数据率
    3. 时钟同步/异步：同步不同步
    4. 总线复用：地址总线和数据总线复用
    5. 信号线书：地址线、数据线、控制线位数总和
    6. 总线的控制方式：突发、自动、仲裁、逻辑、计数
    7. 其他指标：负载能力

      4.总线的结构

  • 双总线结构：主存总线、I/O总线
  • 三总线：主存总线、I/O总线、DMA总线
  • 三总线：局部总线、系统总线、扩展总线
  • 四总线：局部总线、系统总线、扩展总线、高速总线