传说，Tango有一大水王，他不但喜欢发帖，还会回复其他ID发的贴子，坊间风闻该水王发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

最直接的方法，我们可以对所有ID进行排序，然后再扫描一边排好序的ID列表，统计各个ID出现的次数，如果某个ID出现的次数超过总数的一半，那么就输出这个ID。这个算法的时间复杂度是 O(N*logN + N)

如果ID列表已经是有序的，还需要扫描一遍整个列表来统计各个ID出现的次数吗？

当列表已经是有序时候，第N/2项就是水王ID。

但上面两种方法都需要先对ID列表进行排序，时间复杂度没有本质的改进，能否避免排序呢？

如果每次删除两个不同的ID（不管是否包含水王的ID），那么，在剩下的ID列表中，水王ID出现的次数仍然超过总数的一半，可以不断通过重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到答案，新的思路，避免了排序这个耗时的步骤，总的时间复杂度只有O(N)，且只需要常数的额外内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Type Find(Type* ID, int N)
{
    Type candidate;
    int nTimes, i;
    for(i = nTimes = 0; i < N; i++)
    {
        if(nTimes == 0)
        {
            candidate = ID[i], nTimes = 1;
        }
        else
        {
            if(candidate == ID[i])
                nTimes++;
            else
                nTimes--;
        }
    }
    return candidate;
}

把一个问题转化为规模较小的若干个问题，小的问题跟原问题本质上一直。

扩展问题：

统计发现，有三个发帖很多的ID，他们的发帖数目都超过了帖子总书N的1/4，你能从发帖ID列表中快速找出他们的ID吗？

二分查找

复杂度：时间复杂度 O(log2n)，空间复杂度O(n)

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

//递归与非递归
#include <iostream>
using namespace std;

int a[] = {1,2,3,4,5,6,7,8};

int BinarySearch1(int l, int r, int value)
{
    int mid = (l + r) / 2;
    if(l == r && a[l] != value)
        return -1;
    if(a[mid] == value)
        return mid;
    if(a[mid] > value)
        return BinarySearch1(l, mid-1, value);
    else
        return BinarySearch1(mid+1, r, value);
}

int BinarySearch2(int value)
{
    int l = 0;
    int r = sizeof(a) / sizeof(a[0]) - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(a[mid] == vlaue);
            return (l + r) /2;
        if(a[mid] > value)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}

int main()
{
    cout << "Binary Search (recursive) result: " << BinarySearch1(0, sizeof(a) / sizeof(a[0]) - 1, 5) << endl;;
    cout << "Binary Search (no recursive) result: " << BinarySearch2(4) << endl;
}

斐波那契查找

黄金分割：

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之间，其比值约为1：0.618 或1.618：1

然后我们会发现，随着斐波拉契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

基本思想：

也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率，同样地，斐波拉契查找也属于一种有序查找算法。

斐波拉契查找与折半查找相似，他是根据斐波拉契序列地特点对有序表进行分割地，他要求开始表中记录地个数为某个斐波拉契数小1，即n = F(k) - 1;

开始将k值与第F(k-1)位置的记录进行比较(即mid = F(k-1) - 1), 比较结果：

1. 相等
2. >, low = mid+1, k-=2;

说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

3. <，high=mid-1,k-=1。

说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

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

#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 20;

int a[] = {1,5,15,22,25,31,39,42,47,49,59,68,88};

void Fibonacci(int F[])
{
    F[0] = 0;
    F[1] = 1;
    for(size_t i = 2; i < MAX_SIZE; i++)
        F[i] = F[i-1] + F[i-2];
}

int FibonacciSearch(int value)
{
    int F[MAX_SIZE];
    Fibonacci(F);
    int n = sizeof(a) / sizeof(int);

    int k = 0;
    while(n > F[k]-1)
        k++;
    vector<int> temp;
    temp.assign(a, a+n);
    for(size_t i = n; i < F[k] - 1; i++)
        temp.push_back(a[n-1]);
    
    int l = 0, r = n - 1;

    while(l <= r)
    {
        int mid = l + F[k-1] - 1;
        if(temp[mid] < value)
        {
            l = mid + 1;
            k = k - 2;
        }
        else if(temp[mid] > value)
        {
            r = mid-1;
            k = k-1;
        }
        else
        {
            if(mid < n)
                return mid;
            else
                return n-1;
        }
    }
    return -1;
}

int main()
{
    int index = FibonacciSearch(88);
    cout << index << endl;
}

直线分割平面

在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。

当添加第N条，为了使平面最多， 则第N条直线要与前面的N-1条直线都相交，且没有任何三条直线相交一个点。
则添加第N条直线会多N-1个交点。由于每增加N个交点，就增加N+1个平面，所以添加第N条直线来会在之前的基础上增加N个平面，用F[i]表示i条直线能把平面切分成的个数。

1
2
3

F[1]=2; 
F[n]=F[n-1]+n; 
递推得F[n]=1+n*(n+1)/2

折线分割平面

平面上有n条折线，问这些折线最多能将平面分割成多少块?

分析先以问题一作为基础，

再看每次增加两条相互平行的直线的情况。

根据题型一分析可以知道

当第N次添加时，前面已经有2N-2条直线了，所以第N次添加时，第2N-1条直线和第2N条直线都各能增加2*（n-1）+1 个平面。

所以第N次添加增加的面数是2[2(n-1) + 1] = 4n - 2 个。因此，总面数应该是

1 + 4n(n+1)/2 - 2n = 2n^2 + 1

如果把每次加进来的平行边让它们一头相交

则平面1、3已经合为一个面，因此，每一组平行线相交后，就会较少一个面，

所以所求就是平行线分割平面数减去N，为2n^2 -n + 1.

利用上述总结公式f(n)=2n^2 -n + 1

拓展

说起佐罗，大家首先想到的除了他脸上的面具，恐怕还有他每次刻下的“Z”字。我们知道，一个“Z”可以把平面分为2部分，两个“Z”可以把平面分为12部分，那么，现在的问题是：如果平面上有n个“Z”,平面最多可以分割为几部分呢？

说明1：“Z”的两端应看成射线

说明2：“Z”的两条射线规定为平行的

分析：

设f(n)表示n个z字型折线至多平面划分数。

现在增加一条边a，和3(n-1)条线都相交，增加3(n-1)+1个区域。

再增加一条边b，与a平行，同样增加3(n-1)+1个区域。

最后增加一条边c，与已有的边都相交，增加3(n-1)+3个区域。又因为要与a，b形成锯齿形，所以又减去2*2个区域

所以得出递推式 f(n)=f(n-1)+9*(n-1)+1

抓包（packet capture）就是将网络传输发送与接收的数据包进行截获、重发、编辑、转存等操作，也用来检查网络安全。 抓包也经常被用来进行数据截取等。

wireshark使用教程

使用wireshark抓取ping包

cmd输入ping baidu.com

过滤器输入ip.addr == 39.156.69.79 and icmp

wireshark抓包界面

数据包列表区中不同的协议使用了不同的颜色区分。

1. Display Filter(显示过滤器)， 用于设置过滤条件进行数据包列表过滤。

2. Packet List Pane(数据包列表)， 显示捕获到的数据包，每个数据包包含编号，时间戳，源地址，目标地址，协议，长度，以及数据包信息。 不同协议的数据包使用了不同的颜色区分显示。

3. Packet Details Pane(数据包详细信息), 在数据包列表中选择指定数据包，在数据包详细信息中会显示数据包的所有详细信息内容。数据包详细信息面板是最重要的，用来查看协议中的每一个字段。各行信息分别为

   （1）Frame: 物理层的数据帧概况

   （2）Ethernet II: 数据链路层以太网帧头部信息

   （3）Internet Protocol Version 4: 互联网层IP包头部信息

   （4）Transmission Control Protocol: 传输层T的数据段头部信息，此处是TCP

   （5）Hypertext Transfer Protocol: 应用层的信息，此处是HTTP协议

wireshark过滤器表达式的规则

1、抓包过滤器语法和实例

抓包过滤器类型Type（host、net、port）、方向Dir（src、dst）、协议Proto（ether、ip、tcp、udp、http、icmp、ftp等）、逻辑运算符（&& 与、|| 或、！非）

（1）协议过滤

比较简单，直接在抓包过滤框中直接输入协议名即可。

tcp，只显示TCP协议的数据包列表

http，只查看HTTP协议的数据包列表

icmp，只显示ICMP协议的数据包列表

（2）IP过滤

host 192.168.1.104

src host 192.168.1.104

dst host 192.168.1.104

（3）端口过滤

port 80

src port 80

dst port 80

（4）逻辑运算符&& 与、|| 或、！非

src host 192.168.1.104 && dst port 80 抓取主机地址为192.168.1.80、目的端口为80的数据包

host 192.168.1.104 || host 192.168.1.102 抓取主机为192.168.1.104或者192.168.1.102的数据包

！broadcast 不抓取广播数据包

2、显示过滤器语法和实例

（1）比较操作符

比较操作符有== 等于、！= 不等于、> 大于、< 小于、>= 大于等于、<=小于等于。

（2）协议过滤

比较简单，直接在Filter框中直接输入协议名即可。注意：协议名称需要输入小写。

tcp，只显示TCP协议的数据包列表

http，只查看HTTP协议的数据包列表

icmp，只显示ICMP协议的数据包列表

（3） ip过滤

ip.src ==192.168.1.104 显示源地址为192.168.1.104的数据包列表

ip.dst==192.168.1.104, 显示目标地址为192.168.1.104的数据包列表

ip.addr == 192.168.1.104 显示源IP地址或目标IP地址为192.168.1.104的数据包列表

（4）端口过滤

tcp.port ==80, 显示源主机或者目的主机端口为80的数据包列表。

tcp.srcport == 80, 只显示TCP协议的源主机端口为80的数据包列表。

tcp.dstport == 80，只显示TCP协议的目的主机端口为80的数据包列表。

（5） Http模式过滤

http.request.method==”GET”, 只显示HTTP GET方法的。

（6）逻辑运算符为 and/or/not

过滤多个条件组合时，使用and/or。比如获取IP地址为192.168.1.104的ICMP数据包表达式为ip.addr == 192.168.1.104 and icmp

Wireshark抓包分析TCP三次握手

（1）TCP三次握手连接建立过程

Step1：客户端发送一个SYN=1，ACK=0标志的数据包给服务端，请求进行连接，这是第一次握手；

Step2：服务端收到请求并且允许连接的话，就会发送一个SYN=1，ACK=1标志的数据包给发送端，告诉它，可以通讯了，并且让客户端发送一个确认数据包，这是第二次握手；

Step3：服务端发送一个SYN=0，ACK=1的数据包给客户端端，告诉它连接已被确认，这就是第三次握手。TCP连接建立，开始通讯。

（2）wireshark抓包获取访问指定服务端数据包

Step1：启动wireshark抓包，打开浏览器输入www.huawei.com。

Step2：使用ping www.huawei.com获取IP。

 Step3：输入过滤条件获取待分析数据包列表 ip.addr == 211.162.2.183

可以看到wireshark截获到了三次握手的三个tcp数据包。第四个包才是HTTP的， 这说明HTTP的确是使用TCP建立连接的。

网络协议

网络协议为计算机网络中进行数据交换而建立的规则、标准或约定的集合。

为了使不同计算机厂家生产的计算机能够相互通信，以便在更大的范围内建立计算机网络，国际标准化组织（ISO）在1978年提出了“开放系统互联参考模型”，即著名的OSI/RM模型（Open System Interconnection/Reference Model）。它将计算机网络体系结构的通信协议划分为七层，自下而上依次为：物理层（Physics Layer）、数据链路层（Data Link Layer）、网络层（Network Layer）、传输层（Transport Layer）、会话层（Session Layer）、表示层（Presentation Layer）、应用层（Application Layer）。

其中第四层完成数据传送服务，上面三层面向用户。对于每一层，至少制定两项标准：服务定义和协议规范。前者给出了该层所提供的服务的准确定义，后者详细描述了该协议的动作和各种有关规程，以保证服务的提供。

阶乘相关问题：

1. 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N=10，N！=3628800，N！的末尾有两个0。
2. N！的二进制表示中最低位1的位置。

引理：

N！中含有质因数2的个数，等于[N/2]+[N/4]+[N/8]+[N/16]+···

对于问题一：

角度一：从“哪些数相乘能得到10”考虑

如果N！=K*10^M, 且K不能被10整除， 那么N!末尾有M个0。

再考虑对N！进行质因数分解，N！=（2^x）*（3^y）*（5*z）···

由于10 = 2*5，所以M只跟X和Z有关，每一对2和5相乘能得到一个10，所以M = min（X，Z）

因为能被2整除的数出现的频率比能被5整除的数高得多，所以X大于等于Z，所以把公式简化为M = Z。

所以只要计算出Z的值，就可以得到N！末尾0的个数

1
2
3
4
5
6
7
8
9
10

ret = 0;
for(i = 1; i<=N; i++)
{
    j = i;
    while(j % 5 == 0)
    {
        ret++;
        j/=5;
    }
}

角度二：思路类似角度一，找“5”的数

公式： Z=[N/5]+[N/5^2]+[N/5^3]+···（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^k > N, [N/5^k]=0）

公式中，[N/5]表示不大于N的数中5的倍数贡献一个5，[N/5^2]表示不大于N的数中5*5的倍数再贡献一个5···

1
2
3
4
5
6

ret = 0;
while(N)
{
    ret += N/5;
    N /= 5;
}

对于问题二：

判断最后一个二进制位是否为0，若为0，则将此二进制右移一位，即为商值；反之，若为1，则说明这个二进制数是奇数，无法被2整除

所以，这个问题实际上等同于求N！含有质因数2的个数。即答案等于N！含有质因数2的个数加1。

解法一：

N！中含有质因数2的个数，等于[N/2]+[N/4]+[N/8]+[N/16]+···

[N/k]等于1，2，3，···，N中能被k整除的数的个数

1
2
3
4
5
6
7
8
9
10

int lowestOne(int N)
{
    int Ret = 0;
    while(N)
    {
        N >>= 1;
        Ret += N;
    }
    return Ret;
}

解法二：

N！含有质因数2的个数，还等于N减去N的二进制表示中1的数目。

证明：

N！中含有质因数2的个数为：[N/2]+[N/4]+[N/8]+[N/16]+···

假设N = 11011

即

1
2
3
4
5
6

1101 + 110 + 11 + 1
= (1000 + 100 + 1) + (100 + 10) + (10 + 1) + 1
= (1000 + 100 + 10 + 1) + (100 + 10 + 1) + 1
= 1111 + 111 + 1
= (10000 - 1) + (1000 - 1) + (10-1) + (1-1)
= 11011-(N二进制数表示中1的个数)

相关问题

给定整数n，判断它是否为2的方幂。

(n>0 && ((n&(n-1)) == 0))

求二进制数中1的个数

对于一个字节（8bit）的无符号整型变量，求其二进制表示中‘1’的个数，要求算法执行的效率尽可能高

解法一：

利用整型数据除法的特点，通过相除和判断余数的值来分析

1
2
3
4
5
6
7
8
9
10
11
12
13

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        if(v%2 == 1)
        {
            num++;
        }
        v /= 2;
    }
    return num;
}

解法二：使用位操作

向右移位操作同样可以达到相除的目的，唯一的不同之处在于，移位之后如何来判断是否有1存在。

需要判断最后一位是否为1，“与”操作可以达到目的，可以把该数与00000001进行与操作，如果结果为1，则表示当前八位数的最后一位为1，否则为0.

1
2
3
4
5
6
7
8
9
10

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

解法三：

位操作比除、余操作的效率高了很多，但是，即使使用位操作，时间复杂度仍然为O(log2v)

能否将复杂度进一步降低？

为了简化这个问题，我们考虑只有一个1的情况，例如：01000000

如何判断给定的二进制数只有一个1呢？可以通过判断这个数是否为2的整数次幂来实现。另外，如果只和这个1进行判断，如果希望操作后的结果为0，01000000可以和00111111来进行与操作。

这样，要进行的操作就是0100000 & （01000000 - 00000001） = 01000000 & 00111111 = 0

将这种判断只有一个1的做法推广到有不确定1的情况即有如下代码：

1
2
3
4
5
6
7
8
9
10

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        v &= (v-1);
        num++;
    }
    return num;
}

解法四：

解法三的复杂度已经降低到O(M)，M为v中1的个数

若想继续降低时间复杂度，还可以利用空间换时间，提前制好8bit二进制数（255个）各自对应的num的一个数组（表），然后进行查表操作，无需进行任何比较。

相关问题：

给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A和B的二进制表示中有多少位是不同的？

与非 -> 求有多少个1

快速找出故障机器

我们假设一个机器仅存储一个标号为ID的记录（假设ID是小于10亿的整数），假设每份数据保存两个备份，这样就有两个机器存储了同样的数据。

1. 在某个时间，如果得到一个数据文件ID的列表，是否能够快速地找出这个表中仅出现一次的ID？
2. 如果已经知道只有一台机器死机（也就是说只有一个备份丢失）呢？如果有两台机器死机呢（假设同一个数据的两个备份不会同时消失）？

解法一：

这个问题可以转化为，有很多ID，其中只有一个ID出现的次数小于2，其余正常ID出现的次数都等于2，问如何找到这个次数为1的ID。

为了达到这个目的，最简单的方法就是直接遍历列表，利用一个数组记下每个ID出现的次数，遍历完毕之后，出现次数小于2的ID就是我们想要的结果。

假设有N个ID，且ID的取值在0~（N-1）之间，这个解法占用的时间复杂度为O（N），空间复杂度为O（N）。

空间复杂度并不理想，如果ID的数量多达几十GB，这样的空间复杂度在实际运算中会带来效率问题，考虑进一步减少空间复杂度。

解法二：

哪些数据是不必存储的？大部分的机器ID出现次数都等于2，这些机器肯定不是故障的机器，可以不予考虑，可以把解法1数组中等于2的元素清空，然后用来存储下一个机器ID的出现次数，这样就可以减少需要的空间。

具体方法如下：遍历列表，利用哈希表记下每个ID出现的次数，每次遇到一个ID，就向哈希表中增加一个元素，如果这个ID出现的次数为2，那么就从哈希表中删除这个ID，最后剩下的ID就是我们想要的结果。这个算法空间复杂度在最好情况下，可以达到O（1），在最坏情况下仍然为O（N）

解法三：

如何进一步降低空间复杂度？

如果想继续降低空间复杂度，就要摒弃遍历列表计数这种方法了。

是否可以降到常数级别（甚至O（1））呢？

如果这样，我们可以把这个变量写成：x(i) = f(list[0],list[1],…,list[i])，也就是说这个变量是已经遍历过的列表元素的函数。

这个函数需要满足的条件是：x(N) = ID_Lost。

也就说遍历完整个列表后，这个变量的值应该等于丢失备份的ID。

我们需要找到整个f

可以考虑使用异或关系来帮忙找到结果。

因为正确的机器都会有两个ID，不正确的机器只有一个ID。所以所有ID的异或值就等于这个仅出现一次的ID（因为异或运算满足交换律和结合律，其他出现两次的ID异或完都为0）。这样我们只使用一次遍历运算就得到了只有一台故障机器情况下故障机器的ID。

因此，就可以使用 x(i) = list[0]⊕list[1]⊕…⊕list[i]

这种情况下，时间复杂度为O（N）， 空间复杂度为O（1）。

对于第二问：由于有两个ID仅出现一次，设它们为A和B，那么所有ID的异或值为A⊕B。无法确定A和B的值

如果A=B，则A⊕B为0，也就是说丢失的是同一份数据的两个拷贝，我们可以通过求和的方法得到A和B（A=B=（所有ID之和-所有正常工作机器ID之和）/2）

如果A⊕B不等于0，那么这个异或值的二进制中某一位为1，显然，A和B中有且仅有一个数的相同位上也为1。

我们就把所有ID分成两类，一类在这位上为1，另一类这位上为0，那么对于这两类ID，每一类分别含有A和B中的一个。那么我们使用两个变量，在遍历列表时，分别计算这两类ID的异或和，即可得到A和B的值。

解法四：

如果需要考虑死机的两台机器ID相同的情况，还有没有办法解决？

这个问题可以抽象为：在一个事先预定的整数（ID）集合当中，怎么样找出其中丢失的一个数（ID）或两个数（ID）？

对于一个数，预先存好所有ID的和，然后减去后来的，就得到少了的那一个

对于两个数，预先存好所有ID的和以及积（为降低数据大小，还可以改为存平方和），然后两个方程求两个未知数

扩展问题

如果是N个备份？

N小的时候列几个方程？

N多的时候还是用遍历数组？

影响分析（上）

Read and Show An Image

• imread()
• imshow()

1
2
3

clear, close all
I = imread('pout.tif');
imshow(I);

immultiply()

1
2
3
4

I = imread('rice.png');
subplot(1,2,1); imshow(I);
J = immultiply(I, 1.5);
subplot(1,2,2); imshow(J); % J更亮了

imadd()

1
2
3
4
5
6

I = imread('rice.png');
J = imread('cameraman.tif');
K = imadd(I, J);
subplot(1,3,1); imshow(I);
subplot(1,3,2); imshow(K);
subplot(1,3,3); imshow(J);

两张图片相加会变亮，相加的条件是大小要相等

imhist()

1

imhist(I)

将每一个graylevel拿出来统计，得到一个统计图表，横坐标为0~255，纵坐标为frequency

histeq()

1
2
3
4
5

I = imread('pout.tif'); I2 = histeq(I);
subplot(1,4,1); imhist(I);
subplot(1,4,2); imshow(I);
subplot(1,4,3); imshow(I2);
subplot(1,4,4); imhist(I2);

对比度增加

imrotate()

1
2
3
4
5
6

I = imread('rice.png'); 
subplot(1,2,1);imshow(I); 
J = imrotate(I, 35, 'bilinear');
subplot(1,2,2); imshow(J);
size(I)
size(J)

imwrite()

1

imwrite(I, 'pout2.png');

影像分析（下）

Problem Setup

对于下图，如何通过影像分析数到有多少颗米，米的大小有多大？

策略：

1. 将该图二值化，即米变成白色，背景变成黑色
2. 计算连在一起的白色的点数

Image Thresholding

1

I = imread('rice.png'); imhist(I);

A gray-level image can be turned into a binary image by using a threshold

通过观察直方图，选出一个值(threshold)，对于每个像素，大于那个值的设置为白色，小于的设置为黑色

graythresh() and im2bw()

• graythresh() find an optimal threshold level
• im2bw() converts an images into binary image

1
2
3
4
5
6
7

I = imread('rice.png');
level = graythresh(I);
bw = im2bw(I, level);
subplot(1,2,1);
imshow(I);
subplot(1,2,2);
imshow(bw);

由于部分亮的背景被误认为米粒而变白，所以二进制图里面会有一些闪光点，为了不让这些点影响计算米粒数量结果，需要想办法让背景更加纯洁，就需要割去原有的背景

Background Estimation

• Estimation for the gray level of the background

1
2
3

I = imread('rice.png');
BG = imopen(I, strel('disk', 15));
imshow(BG);

BG就是该图的背景，要去掉背景，就将原图减去这个背景图

Background Subtraction

1
2
3
4
5
6

I = imread('rice.png');
subplot(1,3,1); imshow(I);
BG = imopen(I, strel('disk', 15));
subplot(1,3,2); imshow(BG);
I2 = imsubtract(I, BG);  % I2 = I - BG
subplot(1,3,3); imshow(I2);

这样就能让背近更加纯净

Thresholding on Background Removed Image

1
2
3
4
5
6
7

I = imread('rice.png'); level = graythresh(I);
bw = im2bw(I, level);
subplot(1,2,1); imshow(bw); 
BG = imopen(I, strel('desk', 15));
I2 = imsubtract(I, BG); level = graythresh(I2);
bw2 = im2bw(I2, level);
subplot(1,2,2); imshow(bw2);

可以见到由I2生成的bw2中没有了之前的闪点（sparkle）

这样让误差减少了很多

identify how many grains are there in the image

使用的算法：Connected-component Labeling

A procedure for assigning a unique label to each object

对于原来的binary image，每个像素要么1要么0；

对于每个区域的1，用不同的label来标记，1、2、3.。。

1
2
3
4
5

0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 0 0 1 0 0
0 0 0 1 1 0 0
0 0 0 0 0 0 0

变成

1
2
3
4
5

0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 0 0 2 0 0
0 0 0 2 2 0 0
0 0 0 0 0 0 0

Connected-component Labeling: bwlabel()

1
2
3
4
5

I = imread('rice.png');
BG = imopen(I, strel('disk',15));
I2 = imsubtract(I, BG); level = graythresh(I2);
BW = im2bw(I2, level);
[labeled, numObjects] = bwlabel(BW, 8);

labeled就是一个用不同lebal标记后的一个矩阵

看最大的label是多少就是米的数量有多少

• What is the size of the largest grain?
• what is the mean size of the grains?

Color-coding Objects: label2rgb()

• Converts a label matrix into an RGB color image
• Visualize the labeled regions

1
2
3
4
5
6
7

I = imread('rice.png');
BG = imopen(I, strel('disk', 15));
I2 = imsubtract(I, BG); level = graythresh(I2);
BW = im2bw(I2, level);
[labeled, numObjects] = bwlabel(BW, 8);
RGB_label = label2rgb(labeled);
imshow(RGB_label);

label2rgb()就是添加不同颜色，无其他功能

Object Properties: regionprops()

• Provedes a set of properties for each connected component

可以知道米的大小

1
2
3
4
5
6
7
8

I = imread('rice.png');
BG = imopen(I, strel('disk', 15));
I2 = imsubtract(I, BG);
level = graythresh(I2);
BW = im2bw(I2, level);
[labeled, numObjects] = bwlabel(BW, 8);
graindata = regionprops(labeled, 'basic');
graindata(51)

Starting A GUI Program

1. 将当前目录设置到你想存储GUI program的地方
2. 在命令窗口打入guide创建一个MATLAB GUI