空域滤波技术根据功能主要分为平滑滤波与锐化滤波，平滑滤波能减弱或消除图像中的高频率分量而不影响低频分量。因为高频分量对应图像中的区域边缘等灰度值 具有较大变化的部分，平滑滤波可将这些分量滤去减少局部灰度起伏，是图像变得比较平滑。实际应用中，平滑滤波还可用于消除噪声，或在提取较大目标前去除太 小的细节或将目标的小间断连接起来。锐化滤波正好相反，实际应用中锐化滤波常用于增强被模糊的细节或目标的边缘。

      空域滤波是在图像空间通过邻域操作完成的，实现的方式基本都是利用模板（窗）进行卷积来进行，实现的基本步骤为：

      1、将模板中心与图中某个像素位置重合；

      2、将模板的各个系数与模板下各对应像素的灰度值相乘；

      3、将所有乘积相加，再除以模板的系数个数；

      4、将上述运算结果赋给图中对应模板中心位置的像素。

      常见的空域滤波器：

      1、邻域平均：将一个像素邻域平均值作为滤波结果，此时滤波器模板的所有系数都取为1。

      2、加权平均：对同一尺寸的模板，可对不同位置的系数采用不同的数值。实际应用中，常取模板周边最小的系数为1，而取内部的系数成比例增加，中心系数最 大。

           加权平均模板示例：

                                                1     2     1

                                                2     4     2

                                                1     2     1

      3、高斯分布：借助杨辉三角对高斯函数进行近似。

           高斯模板系数：

                                                    1

                                                 1    1

                                              1    2    1    

                                           1    3    3    1

                                        1    4    6    4    1

                                     1    5    10  10    5    1 

      4、中值滤波：中值滤波是一种非线性滤波方式，可用如下步骤完成。

          （1）将模板在图中漫游，并将模板中心与图中某个像素位置重合；

          （2）读取模板下各对应像素的灰度值；

          （3）将这些灰度值从小到大进行排序；

          （4）找出中间值并赋给对应模板中心位置的像素。

          一般情况下中值滤波的效果要比邻域平均处理的低通滤波效果好，主要特点是滤波后图像中的轮廓比较清晰。

      5、最频值滤波：通过直方图统计中心像素点的灰度分布情况，将出现次数最多的灰度值（即直方图波峰位置）赋给中心位置的像素。如果直方图是对称的且仅有一 个峰，那么均值、中值和最频值相同。如果直方图仅有一个波峰但不对称，那么最频值对应波峰，而中值总比均值更接近最频值。

      6、锐化滤波：图像锐化一般是通过微分运算来实现的，图像处理中最常用的微分方法是利用梯度（基于一阶微分）。在离散空间，微分用差分实现，常用的差分模板如下：

                            -1        1                           1   1   1

                            -1        1                          

用F[i]表示得到i面值所需要的最少邮票个数，Value[j](j=1..Stamps)表示每个邮票的面值，可得以下转移方程：

F[i]=Min ( F[i-Value[j]] + 1 ) (i-Value[j]>=0 j=1..Stamps)
初始状态：F[0]=0;F[i]=INFINITE;

Poj 1597 – Uniform Generator

题目的意思就是一个生成随机数的函数，

     Seed[x+1] = （ seed[x] + STEP ） % MOD

其中seed就是我们生成出来的随机数，至于seed[0]是哪个数并不重要，后面会证明。STEP就是我们每次往前一个所加的值，再module上MOD得到下一个随机数。

判断这个随机生成函数的好坏的依据是如果能够产生0~MOD-1内的所有数，就是一个好的，否则坏。

我们知道了同余的特性，便可以假设在k步之后，生成的seed[k] = seed[0]，所以由此有

        Seed[k] = （ seed[0] + STEP*k ） % MOD

那么，

        STEP * k = MOD

而我们如果要生产MOD个数，必须使k≥MOD，而且k不可能大于MOD，因为这个条件下生成的数又开始重复，所以k=MOD；在前面的条件下，如果STEP和MOD有大于1的公约数例如d，那么会有STEP*(k/d) = MOD，这就是一个循环了，只会产生k/d<MOD个随机数。

结论：iff gcd(STEP, MOD) == 1, good choice.

Poj 3370 Halloween treats

这道题在集训手册上标志是“抽屉原理”，老实说，在看到这道题的具体解法之前，我还不知道为什么是抽屉原理，这明明是判断一些数的同余嘛，后来才发现鸽笼原理的巧妙之处。

4 5

1 2 3 7 5

例如对于第一组数据，

1 2 3 7 5模上4分别是：

1 2 3 3 1

如果采用同余+dp的方法，难度会相当大，规则比较复杂；

这时，我们采用一种巧妙地方法，就是用一个sum[i]数组来记录前i个数之和%4，例如上例中，我们得到：

由此，我们在碰到1.sum[i] == 0 或者2.sum[i]的值已经在前面出现过的情况时，就可以知道有解，并且解是从上一个出现该sum[i]数值的后一个位置开始→现在sum[i]的位置，这个貌似可以解出可能的解；但由于加和的顺序随机，所以还不清楚是否可以在该case有解的情况下一定能够解出解。这时候，我们就要用到鸽笼原理了。

运用《离散数学与组合数学》书中的方法，我们可以把sum[1~n=nneighbor](或0~n)看做n+1只鸽子（注意上面的隐含0列），飞入c=nchild个鸽笼中，再注意到题目中有这样的数据范围：

The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000) （这是本题能用鸽笼原理的最重要的前提）

由此我们可以知道一定有两只鸽子是飞入同一个笼子当中的，所以加法的顺序就自然不用考虑了；而且由这个我们也可以知道，此题一定不存在无解的情况。