编辑距离

• 编辑距离是衡量字符串相似度的距离
• 主要应用比如衡量DNA的相似性，衡量什么地方断字，文件的差异等等

基本操作

• 对于字符串里面的两个字母，有三种操作方法能让他们改变
  • 插入一个新的字母
  • 删除一个已经存在的字母
  • 把现有的字母替换成其他字母
• 对于两个string，有四种基本的操作
  • 第一种，不变 （比如ruopeng和fag）
    • 原本的操作 ruopeng[0,6] -> fag[0,2]
    • 变换之后 ruopen[0,5] -> fa[0,1]
    • 因为最后一位相同，这个问题可以拆分成最后一个字母，和不包括最后一个字母的substring，这个问题就可以拆分了
  • 第二种，替代 replace （比如 peng 和 zhou）
    • 原本操作 peng[0,3] -> zhou[0,3]
    • 变换之后 pen[0,2] -> zho[0,2] + replace(g -> u)
    • 其中，替换的操作是一步，替换之后最后一位的字母相同，这个问题就可以拆分成更小的问题了
  • 第三种，插入 insert
    • 原本操作 peng[0,3] -> zhou[0,3]
    • 变换之后 peng[0,3] -> zho[0,2] + insert(u)
    • 首先，直接把这个问题里面的zhou拆分成了更小的问题zho，然后再进行一个插入操作（一步），使zho重新变成了u
  • 第四种，删除 deletion
    • 原本操作 peng[0,3] -> zhou[0,3]
    • 变换之后 pen[0,2] -> zhou[0,3] + delete(g)
    • 同时也可以尝试尝试删除掉前一个string里面的最后一个字母g，不再管里面的g，把这个字符串尝试变成pen来进行比较

核心思想

• 首先，我们针对这两个string制作一个table
  • 对于这个表来说，每一个位置都相当于这个位置对应的两个substring的相似程度，比如E和F对应的就是 ”RUOPE“ 和 ”F“两个substring对应的相似度
  • 在每个单词开始之前，还有一个空白符号，对应的substring就是空白。比如空白符号这一列对应的就是”“分别和”F“，”FA“，”FAN“等元素的比较
    
• 对于每个表格里面的位置，从(1,1)开始，这个位置和周围位置的关系如下
  • 上面一格是插入，指的是在FANGZHOU这个string的substring里面插入
  • 左边一格是删除，指的是把RUOPENG这个单词删除一个字母
  • 左上角一格是替代，指的是把这两个单词的字母分别退一位。如果当前位的字母相同，当前位的值等于退一位之后的值，如果当前不同，是退一位的值+替代花费的操作（也就是1）
    
• 表格初始化
  • 首先需要确定这个表格的边缘情况，也就是横坐标和纵坐标分别是0的部分，这个部分不能用上面总结出来的公式表示
  • 因为这部分其实就是把不同的substring和空白符号比较，那么需要的最小操作就等于当前字母的位数
    
• 填表
  • 从当前的初始状况出发，逐渐把这个表填完，每一个新的格子的值都取决于上一个格子的值
    • insert = M[i-1][j]+1
    • delete = M[i][j-1] + 1
    • replace = M[i-1][j-1] + 1
    • dont change = M[i-1][j-1] （两个字母匹配）
  • 如果两个字母不匹配的时候，now = min(insert,delete,replace)
  • 最终结果如下，红色部分为字母相同部分
    

python代码实现

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

def EditDistance(a, b):
    m = len(a)
    n = len(b)
    # 构建表格，注意需要比长度大一格，储存空字符串
    M = [[0 for i in range(m + 1)] for j in range(n + 1)]
    # 初始化表格，substring分别和空字符串比较
    for i in range(1, n + 1):
        M[i][0] = i
    for i in range(1, m + 1):
        M[0][i] = i
    # DP
    for i in range(1, n + 1):
        for j in range(1, m + 1):
                # 判断是否相同，注意这里要减一
            if b[i - 1] == a[j - 1]:
                M[i][j] = M[i - 1][j - 1]
            else:
                insert = M[i - 1][j] + 1
                delete = M[i][j - 1] + 1
                replace = M[i - 1][j - 1] + 1
                M[i][j] = min(insert, delete, replace)
    return M[n][m]

• 注意分清矩阵的行和列，在这个实现里a是行，b是列
• 考虑到最前面的空字符串
  • 注意从string里面读取的时候要记得减1
  • 注意构建矩阵的时候行数和列数要加一
• 右下角的结果就是两个完整字符串对比的结果

时间复杂度

• 这个方法需要遍历左右的substring的组合，并且把所有的结果都存在一个矩阵里
• 如果两个string的长度分别是m和n，那么时间复杂度O(mn),空间复杂度O(mn)

最后，RUOPENG在8月8号这天祝距离为8的FANGZHOU，八(7+1)夕快乐

第一章 算法简介

二分查找

• 必须是有序的数组
• 对于n个元素的列表，使用二分查找最多需要 log2 n步，用普通的查找最多需要n步

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

  def binary_search(l, item): low = 0 high = len(l) - 1 while low <= high: mid = int((low + high) / 2) # 这里需要转成int，不然没办法做index if l[mid] == item: return mid elif l[mid] < item: low = mid + 1 else: high = mid - 1 return None

运行时间

• 大O表示法表示了操作数，表示的是这个算法的增量
• 大O表示了在最糟情况下的运行时间 -> 但是也是需要讨论平均时间的
• 常见的大O时间
  • logN 对数时间 Logarithmic
  • N 线性时间 Linear
  • N * logN 包括快速排序等，速度较快
  • N ^ 2 选择排序等，速度较慢
  • N！ Factorial time 非常慢

旅行商问题 travelling salesman problem, TSP

• 一个搞不好可以用n！来解决的问题
• 你要去五个不同的地方，需要规划怎么样路线最短，最开始的思路就是把每种可能性都列出来，然后对每种路线进行计算。这样的话五个地方就是120种，地方越多越呈阶乘增长

第二章 选择排序

数组和链表

• 数组需要的空间是固定的（也就是说必须连在一起），所以如果后面加进去了其他东西的话就不行了，需要转移位置，或者预留空间
• 链表的每一个位置都会有到下一个位置的指针，所以不需要移动元素。
  • 但是链表的问题在于，如果想直接找后面的东西的时候需要一个接着一个读取
• 需要读取整个数据的时候链表效率很高，需要跳跃的时候链表效率很低。而数组在读取随机元素的时候效率很高
  • 数组插入 / 删除线性，读取常数。
  • 链表读取线性，插入 / 删除常数。
• 在实际中，因为数组支持随机访问（但是链表只支持顺序访问），所以数组的适用范围大一些

选择排序

• 实现方法：每次都从所有的里面选出最大 / 最小，然后放在最开头
• 时间复杂度 n ^ 2

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

  def select_sort(l): newArr = [] for j in range(len(l)): smallest = float('inf') index = None for i, item in enumerate(l): if item < smallest: smallest = item index = i newArr.append(l.pop(index)) # 注意这里需要把l的大小改变了 # 但是是在带l的loop外面变得所以没有关系 return newArr

第三章 递归 recursion

何为递归

• 函数自己调用自己
• 递归和循环的作用效果是相同的，没有性能上的优势，但是可以让方案更加清晰
  • base case：告诉函数什么时候不再调用自己，停止循环
  • recursive case：函数调用自己

栈 stack

• 先进后出的数据结构，push（压入）和pop（读取和删除）
• 在调用另一个函数的时候，当前函数暂停并且处于未完成状态，函数的所有变量都储存在内存里
• 使用递归的一个问题：如果调用栈的时候很长，会占据大量内存
  • 这种时候需要重新编写代码使用循环
  • 或者使用尾递归（并不是所有语言都支持）

第四章 快速排序（分而治之 divide and conquer）

分治

• 核心：把一个问题分成子问题，再把子问题分成更小的子问题，最后的子问题可以直接求解，这样的话原问题的解就是子问题的解的合并
  • 比如把n规模的问题分成k份，然后在k个问题里面分别再分开
• 特征
  • 问题缩小规模可以轻松解决
  • 可以分解成若干个小问题
  • 分解出的子问题可以再合并（如果不满足这条，应该考虑贪心或者DP）
  • 分解出的各个子问题是独立的（不满足应该考虑DP）
• 不用循环而用递归：函数式编程里面没有循环（Haskell）

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

def RecursiveSum(l):
    if l == []:
        return 0
    else:
        return l[0] + RecursiveSum(l[1:])  # 这里不能改变l本身的大小


def MaxNum(l):
    if len(l) == 2:
        return l[0] if l[0] > l[1] else l[1]
    submax = MaxNum(l[1:])
    return l[0] if l[0] > submax else submax

• 注意：
  • 需要找好基本条件，如果找最大值的base就是还剩下两个值
  • 注意return的内容

快速排序

• 比选择排序速度快很多
• base条件，一个元素或者空的数组就不需要排序了
• 需要设定一个基本值（比如取第一个值，根据这个值把原数组分成两部分），这样这三个大块就分类完成了。然后对于每个小块，再继续分组
  • 比基准小的子数组
  • 基准
  • 比基准大的子数组

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

    def QuickSort(l): if len(l) < 2: return l else: piv = l[0] # 这里是快读得到比他大和比他小的写法，主要从l[1:]开始 less_part = [i for i in l[1:] if i < piv] more_part = [i for i in l[1:] if i > piv] return QuickSort(less_part) + [piv] + QuickSort(more_part) # 注意这里piv是个int，所以连接的时候需要改成list

时间复杂度

• 快速排序的速度取决于选择的piv的值的大小，也就是说如果完全排好的情况下，复杂度是n2
• 合并排序的速度是 nlogn，快速排序的平均速度是 nlogn，最佳情况是 logn
  • 快速排序需要logn层，每层需要把n个元素全都遍历一次，所以最终的结果是nlogn
• 在计算复杂度的时候，复杂度是操作的次数，而这个次数需要乘一个每次操作的常量，在快速排序的时候常量更小，而且快速排序没那么容易遇到最糟情况

第五章 散列表（hash表）

hash函数

• 最终的目的是查找的时候时间复杂度是 1
• 函数构造：把输入映射到一个数字
  • 无论你什么时候输入，输出的数字是一致的
  • 将不同的输入映射到不同的数字
  • 知道整个存储的范围有多大，不会返回超过这个大小的数字

应用：缓存

• 网站的缓存数据就存在hash表里面，这样访问速度更快，网站本身需要做的工作更少
• 访问一个网页 -> 是否在缓存里 -> 有的话调用缓存 -> 没有的话存进缓存

冲突

• 虽然假设的时候认为每个东西都被映射到不同地方，其实会产生冲突
• 这种情况下要在hash后面加上list
  • hash函数需要把内容比较平均分分配
  • 如果储存的链表很长，那么性能就会急剧下降

性能

• 最佳性能，1
• 最糟性能，插入，删除，查询全都是n
• 装填因子： 装填的元素数 / 元素总数
  • 一旦超过0.7就需要调整hash的长度了

第六章 BFS：最短路径问题

BFS

• 用于图的查找算法，可以解决两种问题
  • 从A出发有前往B的路径吗
  • 从A出发到B的路径最短是什么
• 实现图 -> hash表，需要将node映射到所有的邻居
• 在python里面使用deque创建双端队列
• 算法实现（广度搜索）：
  • 创建一个队列，储存用于查找的人
  • 首先把初始化的人载入队列
  • 从队列里弹出一个人，查找他是不是（查过之后标记成已检查，列表记录），不是的话把这个人的相邻加入队列（一直重复）
    • 标记成已检查非常重要，因为不标记的话可能会陷入无限循环
  • 如果最后队列空了还没找到，那就是没有

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

def BFS(name, graph):
    search_queue = deque()
    search_queue += graph[name]
    searched = [name]  # 用来储存已经探索过的人数
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person[-1] == "m":  # 只是一个判断是不是这个人的办法
                return person
            else:
                search_queue += graph[person]
                searched.append(person)
    return None

更新版本，不但可以搜索还可以计算长度

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

def BFS(name, graph):
    search_queue = deque()
    search_queue.append(name)
    searched = [name]  # 用来储存已经探索过的人数
    distance = {name: 0}
    while search_queue:
        current = search_queue.popleft()
        for person in graph[current]:
            if person not in searched:
                searched.append(person)
                distance[person] = distance[current] + 1
                if person[-1] == "m":
                    return person, distance[person]
                else:
                    search_queue.append(person)
    return None, None

• 注意点：
  • 增加了distance这个dict来储存开始点到这个点的距离
  • 在初始化的时候只在已搜索队列里添加了第一个点的信息，在后面的循环里才添加后面的点
  • 对于每个从queue里面拿出来的点，如果不在已经查找的点里就一定需要加进去，并且计算距离，距离即是和上一点的距离+1
  • 计算过距离之后再判断是不是要找的点

• 运行时间

  • 需要沿着每条边前进，所以在边上的运行时间是 O(E)
  • 把每个人加到queue里面也需要时间，每个人的时间是常数，所以人数的时间是 O(V)
  • 总的运行时间 E + V

• 拓扑排序

  • 如果任务A依赖于任务B，那么任务A就必须排在B的后面，这种就是拓扑排序

第七章 狄克斯特拉算法

• 之前的图找的是最短路径，现在需要给图加权，找加权之后的最短路径
• 加权之后的最短不一定是边数最短
• 负的权重不顶用，因为负权重不能确定没有比目前消耗更小的
• 书里写的错的地方：可以有环，没环都是树了！有向无环图可以直接拓扑排序
• 核心思想：找到到这个点消耗最少的路径，并且确保没有路径比这个小了

算法流程

• 找出消耗最低的点
• 更新这个点相邻点的开销
• 重复这个过程，直到对所有点都做了（即A点最小之后更新B点，然后更新C点，以此类推）
• 计算最终流程

具体实现

• 创建一个表格
  • 包含了每一项和每一项的具体开销，目前不知道的开销标记成inf
  • 需要包含每个点的父节点，才能保证最后可以计算流程
• 不停的更新这个表，从开销最低的一直更新到开销最高的，如果更新了开销的话同样需要更新父节点
• 在确定路径的时候，从结尾的地方开始找，然后一路找到开头

一个问题：关于图在python里面的表示

• 实际就是一个dict叠dict，如果直接访问G[a][b]就可以直接得到这两个点的距离

• 如果没有加权的话，可以直接dict叠list，因为不需要记录距离了

• 注意点

  • 最好是最开始指定了第一个消耗最低点，然后再循环里面最后找消耗最低点
  • 初始化的时候注意：cost里面初始为0，father里面去掉这个点，Node（cost最低点）初始化成这个点，循环的条件是Node不是空

    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

    def dijkstra(graph, src, target): # 需要创建一个cost表和一个父节点表 cost = {} father = {} visited = [] for i in graph.keys(): # 访问这个图里面所有的key，就是所有的店 cost[i] = float('inf') father[i] = None cost[src] = 0 # 起始点的cost是0 father.pop(src) # 起始点不需要父节点 Node = src # 最小开销点还存在的时候更新所有的点 while Node is not None: for near in graph[Node]: new_distance = cost[Node] + graph[Node][near] if new_distance < cost[near]: cost[near] = new_distance father[near] = Node visited.append(Node) # 找到最小开销的点(放在循环里面好一点) Node = None smallest = float('inf') for i in cost: if i not in visited: if cost[i] < smallest: smallest = cost[i] Node = i # 跳出循环，得到结果 N = { "start": {"a": 2, "b": 6}, "a": {"fin": 1}, "b": {"a": 3, "fin": 5}, "fin": {} } # print(N["start"]["a"]) dijkstra(N, "start", "fin")

第八章 贪心算法

• 处理npc问题，即没有快速算法的解法的问题
• 对NPC问题找到近似解

例子问题

• 课表问题：
  • 希望尽可能多的课在这个屋子里面上，但是上课时间冲突，如何排课
  • 先找到这个教室里最早开始的课，然后找到这节课结束之后最早开始的课
• 装东西
  • 背着包去装东西，容量有限，如何装到最大价值的
  • 从最大的开始装，但是得到的不是最优解，最优解应该动态规划
• 核心思想：每一步都用局部最优解，得到的结果就是全局最优解。即使得不到最优解，也可以得到近似最优解

只能用贪心的问题

• 集合覆盖问题，比如想在全部区域广播，但是每家电台只覆盖特定区域，如果才能花费最小的计划
• 列出所有的可能性的话，复杂度是 2^n
• 近似算法：从覆盖最多地方的电台开始找，一直到覆盖所有地方
• 贪心算法的复杂度是 n^2，n是广播台的数量
  • 因为每次都需要遍历一次找出最需要的那个（n)，这样的操作需要进行最多n次（万一每次都覆盖不上）

NPC问题：从旅行商问题详解

• 旅行商问题和求路径问题的区别在于，旅行商问题需要访问一遍所有的地方，找到最短路线
• 旅行商问题需要查看所有的可能的路线
• 从简单问题出发
  • 两个地方的时候，可能的路线有两条（一来一回）
  • 三个地方的时候 6条
• 需要计算出所有的解才有可能从中选出最短的路线 -> NPC问题
• 近似方法：每次都去离得最近的地方

识别问题

• 元素较少的时候速度快，随着元素增加非常慢
• 涉及所有组合
• 不能分成小问题，必须考虑所有情况
• 涉及序列（比如旅行商中的城市序列），集合（集合覆盖问题）且难以解决。或者可以转换成这种问题的

第九章 动态规划

核心思想

• 把一个大的问题拆分成很多小问题的解的合并
• 最终的结果其实类似一个表，每次再得到新的结果的时候，其实是在比较
  • 同等大小下上一个的值（即上一行的值，这个值已经是之前储存下来的最大的值了）
  • 当前放新的东西的价值+放完这个东西之后剩下空间可以放的东西的最大价值（这个最大价值同样也被记录了）
• DP处理问题的时候只能整件的处理，也就是说分布应该是离散的而不是连续的
• 而且DP处理问题的时候各个子问题之间不能互相依赖，如果互相依赖了就很复杂了

最长公共子串

• 比如搜索引擎误输入，怎么判断相近词
• 每种动态规划都涉及网络，每个网格里面的值就是我需要优化的值
  • 每个单元格里是什么
    • 每个单元格是这个格子之前相同的字母数量
  • 如何把这个问题分成子问题
    • 如果相同，就是前一个的字母数+1，如果不同就是0
  • 网络的坐标轴是什么
    • 在这个问题中，是两个单词的各个字母
• 注意在这个问题里面，最终答案不是在最后出现的
• 最长公共字序列！！和子串不一样，对比的是序列而不是字母的个数
  • 当字母不同的时候，选择上边或者左边最大的那个

应用

• levenshtein distance（字符串的相似程度，也就是上面的公共子序列）
• 指出文件的差异，DNA的相似性，确定什么地方断字
• 核心思想：需要把两个str里面所有的substr的combination都计算一下
• 实现
  • 初始化条件：插入
  • 实际上来说一个格子有三种操作，删除，插入和置换，这个格子需要改变的操作是这三个操作的最小值
  • 删除 = d[i - 1][j] + 1
  • 插入 = d[i][j - 1] + 1 （相当于这个单词的前一个字母，加上一个插入，这两个没有本质区别）
  • 替换 = d[i - 1][j - 1] + cost，其中这个cost，如果两个相同就是0，两个不同就是1
• 具体说明见levenshtein distance说明

第十章 K最近邻

创建推荐系统

• 向这个人推荐电影，找到离这个人最近的五个用户
• 如何判断最近：特征抽取

第十一章 接下来如何

树（数据库 + 高级数据结构）

• 二叉查找树：对于每一个节点，左节点都比他小，右节点都比他大
  • 时间复杂度 logn
  • 平衡问题
• 延伸： B树，红黑树，堆，延展树

反向索引

• 搜索引擎的工作原理
• 把网页创建hash表，key是单词，value是包含单词的页面

傅里叶变换

• 信号处理

并行算法（提高速度）

• 对速度的提升是非线性的
  • 并行管理开销
  • 负载均匀

MapReduce

• 分布式算法
  • 把一台电脑上面处理的工作分布到多台电脑，处理大量数据
• 分布+归并

布隆过滤器

• 概率型数据结构：可能出现错报，但是不可能出现漏报
  • 储存空间很少

HyperLogLog

• 类似于布隆过滤器的算法，不能给出准确的答案但是占据的空间很小

SHA

• 另一种hash，安全散列算法，给定一个字符串返回hash
• 比较大型文件
• 检查密码
• 局部不敏感，修改其中一个字符，会改变很多

Diffie-Hellman 密钥交换

• 如何对消息加密，让只有收件人看得懂

线性规划

• 在给定的约束条件下最大限度的改善指定的指标

给予特征

• 拉伸指令

修饰外形

• 修改边缘
  • 圆角
  • 倒角
• 外观处理
  • 选择贴图
  • 右键选择外观
  • 可以选择加到面上面或者加到所有东西上面

render（3D模型2D化）

• 从model改成渲染
• 点那个台灯，修改图片的场景设置，比如高宽比
• 所有东西都弄好了之后直接渲染，渲染到自己满意的地方

画草图

• 可以把参考的图放在平面上来，这样画起来比较轻松（插入）
• 需要校准加进去图片的比例
• 修建偏移之类的对标CAD
• 画曲线
  • 直接关键点画曲线，可以再调整
• 几何关系靠计算来

咖啡杯

• 杯身
  • 旋转体成型
• 杯盖
  • 新建新的零部件
  • 修改 – 合并（相交运算
  • 草图 – 投影，可以把其他的东西投影到现在的平面

Binarizer.cpp

这个部分是来计算图像的binary的，包括

• 计算这个图片的threshold
• 做背景substract

Cpp相关

• 构造函数
  • 构造一个类的时候使用的函数，这个函数的名字和类名相同，默认是没有参数的，可以自己加上参数，这样创建对象的时候就需要给参数
  • 对标python里面的init
• 析构函数
  • 名字和构造函数完全相同，但是在前面增加了一个波浪线，没有返回值也没有参数，只是用来在关闭程序的时候释放资源

• 虚函数

  • 借助指针来达到多态的效果
  • 定义一个函数是虚函数，不代表这个函数不被实现，而是代表基类的指针可以调用子类的这个函数
  • 如果定义为纯虚函数，才说明不会实现
  • 比如下面的例子里面，B是子类，A是基类，创建的是A的指针，但是调用的却是B的函数，这说明这个函数的调用不是在编译的时候被确定的，而是在运行的时候被确定的

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

    class A { public: virtual void foo() { cout<<"A::foo() is called"<<endl; } }; class B:public A { public: void foo() { cout<<"B::foo() is called"<<endl; } }; int main(void) { A *a = new B(); a->foo(); // 在这里，a虽然是指向A的指针，但是被调用的函数(foo)却是B的! return 0; }

• 纯虚函数，在函数的定义后面加上 =0

  • 经常会在定义基类的时候用纯虚函数，因为基类可能有很多的派生，但是基类本身生成的对象可能是不合理的
    • 比如动物可以派生狮子老虎，但是动物本身不是很合理
  • 在子类里面必须重新声明这个函数，也就是说在子类的时候必须提供一个这个函数的实现，但是基类的作者不知道你怎么实现它

看了别人写的代码，感觉好多openCV里面的基础功能我都不知道，当时还是在自己写的，比如降噪啊，减去背景啊等等的

关于载入模型

看了一个Github上面的项目，是自己训练了一个五个手势的识别，然后用这些手势来控制自己屋子里面的灯光变化，用keras训练的所以先载入了这个的模型，然后有两个不同的预测的函数

• 第一个函数用了model.predict_classes，这个函数预测出来的直接是类别，打印出来的就是类别的编号
• 第二个用的是model.predict，这个预测出来的是一个数字，不能直接用，还需要把这个数值argmax(predict_test,axis=1)才可以用（也就是找到最大的）

createBackgroundSubtractorMOG2()

retval = cv.createBackgroundSubtractorMOG2( [, history[, varThreshold[, detectShadows]]] )

• 创建了一个MOG2的background substructor
• 参数分别是
  • history的长度
  • 计算的是曼哈顿距离，这个的阈值
  • 是否检测影子，如果检测的话速度回慢一点

创建完的模型有很多功能

• 这里用到了一个apply，就是对一张图进行这个操作，来计算出这张图片的foreground
  • 这里有一个参数叫learning rate，指的是你的这个模型会不会随着时间而改变，0的话就是不变，1的话就是完全由上一帧形成，然后负数的话会自动选择一个

bitwise_and()

dst = cv.bitwise_and( src1, src2[, dst[, mask]] )

• 这里计算了每一位的与（and）计算，加上了一个可选的参数mask，这样可以直接计算出来前景去掉背景

videoCapture.set()

dst = cv.bitwise_and( src1, src2[, dst[, mask]] )

• 这里他的代码没有用属性，直接设置了两个数字，每个数字会代表一个属性，数字的范围是0-18
• 也就是说她设置了10这个属性，然后把这个属性的大小设置成了200

cv2.bilateralFilter(frame, 5, 50, 100)

• 一个叫这个名字的滤镜，可以消除掉图片里面你不想要的噪音
• 效果比较好，可以在消除噪音的同时保证图像比较清晰，但是与此同时这个filter的速度会比大多数的慢一些

图像翻转 flip

• 两个参数，翻转的图像以及翻转参数
• 0是竖直翻转，1是水平翻转，小于0的时候是旋转180度（先竖直再水平翻转）

inRange

dst = cv.inRange( src, lowerb, upperb[, dst] )

• 查看是否有数字在这个范围里面，三个channel都在的话就输出1，不在的话就输出0
• 可以给不同的channel赋不同的值

calcHist

hist = cv.calcHist( images, channels, mask, histSize, ranges[, hist[, accumulate]] )

• 计算一系列输入的histogram
• 原来有这个函数，把这个输入normalize到255个channel上面就能得到，这样就可以得到这张图片里面的分布了
• 而且考虑了上面的mask的情况

calcBackProject（存疑！）

dst = cv.calcBackProject( images, channels, hist, ranges, scale[, dst] )

• 计算一个hist的back projection

CamShift()

Touch180: Finger Identification on Mobile Touchscreen using Fisheye Camera and Convolutional Neural Network

abstract

• 鱼眼+深度学习，证明检测手指的准确性和鲁棒性
• 生成了一个dataset
• 训练了一个CNN，确定手指touch的位置

intro

• 可以通过给不同的手指不同的职责来增强对触摸屏的使用
• 以前的分别手指的论文
  • wearable device -> 比较贵
  • 确定触摸的区域 -> 必须多个手指触控
  • 还有一个方法是在手上戴上了一个有颜色的戒指（诶这个方法用来实现现在的device的画画功能感觉怎么样）
  • 用了深度相机的 -> 不适合mobile device
  • 其他用CNN的没有使用鱼眼相机

dataset

• 直接用不同的frame来做的dataset
• 用五个二进制的数字来表示labeling

net

目标

• 这个游戏是和雷电类似的游戏
• 需要设定碰撞等等游戏逻辑，然后设计音乐，图等等东西

setup，player，camera

set up

• 需要确定好应用的开发平台file-build setting
  • 注意这个游戏想开发网页版的，但是现在已经不支持web player，建议使用web GL
• 可以在project setting-player里面改变一些游戏的设置（这里改变了宽度和高度）
• 在右上角的layout可以改变窗口的布局

放置游戏的object

• 直接从model里面拖进来放进scene或者hierarchy里面
  • 点击F可以锁定这个东西（最佳视角）
• 需要设置这个object在原点
• 有一个mesh filiter来决定这个东西用的什么模型
• 一个mesh renderer来渲染这个模型
  • 这个里面有两个不同的材料
• 因为需要物体之间的碰撞，所以需要增加physics--rigidbody
  • 加入了这个东西之后，物体就有了物理上的特征
• 下面由于需要碰撞，所以需要定义这个物体的体积
  • 增加一个physics -- capsule collision
  • 相当于把这个物体的周围加上了一个cage，来确定他的体积
  • 需要在这里面定义碰撞的方向（因为这里面是沿着z运动的，所以碰撞在z轴上面）
  • 可以改一改视角，然后直接拉bar来调节这个consule的大小
• 关于coliider
  • 除了这里面用到的胶囊型的以外，还有square的sphere的，confound的（混合）？，在能解决问题的时候尽量用上面的基础图形
  • 除此之外，还有一个mesh coillder，用来专门契合这个物体的体积的，但是是最后的选择，选择的时候最好也选择一些比较简单的形状(如图所示，新的碰撞范围会完整契合这个物体)
  • 在coillder里面可以自己设定这个对应的mesh的种类，即使和使用的模型不同也可以（也就是说可以建立一个相对于这个模型简单的模型，然后建立碰撞）
    
    
• 为了选中的这个东西可以被识别为碰撞物体，选择is trigger
• 为了增加一点神奇的新功能，在预设好的prefab（一个可以重复克隆的对象）里面找到一个引擎的动画，拖到player的子目录下面，这个东西就自动加进去了

相机和light

相机

• 因为一开始相机会初始化在物体之后的位置，所以现在在game界面只能看到这个物体的屁股部分，需要设置相机
• 点击main camera，这时候右下角会出现相机位置的缩略图
• 位置 -> 调节到物体上方，并且旋转90度
• 设置相机的种类
  • 如果选择perspective的相机，可以通过调节FOV来决定看到的是多大
  • 这里选择orthographic（正投影，主视图那种感觉）的相机，然后直接调节看到的size就可以了
  • 因为希望object保持在原点上，所以在这里移动camera
• 可以在game画面里面直接调节object的位置等等东西
• 下面把在camera里面把背景改成黑色（soild color）
  • 但是这时候object的颜色并没有变黑，这是因为打开了ambiant light
  • 在window--rendering--lighting setting里面，把source改成color就可以改变环境光的颜色
• 环境光：ambient light
  • 这个光没有方向，所以如果都加上了的话可能会很奇怪

光

• 创建一个有方向的light -> main light

  • 应该是最亮的光
  • 希望可以看到飞机的颜色但是不希望太亮
  • 调整这个光的角度以及强度
    

• 建立第二个光，来照亮不怎么亮的部分 -> fill light

  • 还是调整角度，照亮第一个光照不到的部分
  • 为了不让这个光那么强，把这个光的强度适当调小
  • 为了适应太空的冷色调，把光源颜色改成蓝绿色
    

• 最后增加第三个光，把暗部勾边（相当于素描里面的在边上的高亮部分） -> rim light

  • 为了不照亮东西的上层，在x轴把角度调成复数
  • 为了勾边，颜色是白色的
  • 降低亮度
• 最后建立一个新的空的object，位置reset好，来整理上面的三个光
  • 注意，因为这里的光是directional light，所以光照的效果和光源的位置无关，只和光源的角度有关
    

背景

• 新创建一个quad，调整位置和角度让相机能看到他
• remove掉碰撞的部分，因为背景不需要
• 加上texture -> 可以直接把这张图片拽到对应的位置上面
  • 这样会创建一个新的material加到这个mesh的renderer上面去
• 缩放这个方块，让这个图片可以完全显示（高宽比必须保持！）
• 这时候照在player上面的光也可以照在背景上面，但是不是很希望这种结果
  • 一种方法是把background完全独立一个layer出来
  • 另一种方法是改变这个texture的shader
    • 这里改成完全的testure，这样就不会受到光的影响了
• 最后把船从陷入的background里拽出来
  

移动player

• 首先需要在player底下建立新的scripts
• fixedupdate -> 确定物体现在的位置
  • 首先得到垂直和平行的输入（键盘或者鼠标输入）
  • 物体的移动是一个三维的数组，分别是xyz轴，这里y轴的移动是0.0f，其他两个分别是平行和垂直的移动
  • 因为已经用了rigid body，可以从里面给物体一个速度GetComponent<Rigidbody>().velocity -> 这时候移动的非常慢，因为input接收的只是0和1，所以每秒移动一个unit
  • 这时候加上了一个新的speed参数，每次在计算速度的时候乘上这个参数就可以了
  • 注意，因为这里的speed是个public的值，所以可以直接在unity的UI里面进行操作
    
• 这时候出现了一个问题，player会跑出屏幕
  • 增加一个判断条件，移动这个东西如果到了边界，那么把position从先reset到边界上
  • 因为这样在更新下一帧之前都不会出界
  • 使用了mathf里面的一个函数clamp，来设定x和z的范围
    • 这个函数超过了下界就会一直显示下界，超过了上届就会一直显示上届
  • 为了不让设定的xmax，xmin，zmax，zmin在UI里面太占地，所以建立了一个新的class来装这些东西（注意新的class不需要继承），然后在需要用的时候建立新的对象，call
  • 为了能在UI里显示，需要在新创建的class上面加上[System.Serializable]
  • 这些边缘设置什么值可以直接把东西拖到边缘然后看看是什么值就可以了
• tilt或者bank：让飞船到左右移动的时候可以旋转一下
  • 增加了旋转功能Quaternion.Euler
    

shots

希望把这部分的逻辑和这部分的图像分隔开：这样换模型的时候就很方便了

• 首先创建一个新的quan，在这个上面加上texture
  • 创建一个新的material，然后再这个里面选择一个texture
  • 然后再把新的material加到对应的东西里面
• 希望这个东西黑色的部分消失，shader选择mobile--particle--addtive（mobile比较有效率）
• 增加这个东西的碰撞，去掉VFX的碰撞
• 然后加上这个光的运动逻辑
  • transform.forward()向前运动，乘上速度
• 把这个东西设定成一个prefab（直接拖到prefab的文件夹里面）

shoot shots

• 已经把需要射出去的光线设定成了一个prefab，这时候只要在每次点鼠标的时候把这个东西射出去就可以了
• 创建一个新的空的object作为player的子目录来定义发出去激光的位置（shotSpawn）
• 在player中新增一个功能，public的对象是shot和shotSpawn，这两个东西都可以直接从UI里面拖进来，然后设定这个子弹发射的逻辑，每次按下鼠标都并且在0.25秒外会发射子弹
  • 按下鼠标后把showSpawn的transform赋值给shot，这样就知道shot的位置了
• 问题：现在游戏进行过程中会往root里面增加很多prefab

boundary，hazards，enemy

boundary

在画面里面消失的子弹也删掉 -> 建立一个box

• 打开trigger
• 给这个box里面用一个函数，判断是否撞上这个边框，撞上了的话就删除撞上的物体OnTriggerExit

1
2
3
4
5
6
7

public class DestroyByBoundry : MonoBehaviour
{
    void OnTriggerExit(Collider other)
    {
        Destroy(other.gameObject);
    }
}

hazrads

会撞上player的陨石

• 首先建立一个新的陨石对象，这个对象应该可以被撞击的，加上碰撞和刚体
• 加上这个陨石的自动旋转，使用随机的数字，并且把angular drag改成0
• 加上激光和陨石碰撞之后，两个东西同时消失的效果
  • 单纯的加碰撞效果会发现因为边界引发的陨石消失bug
  • 因为陨石先和边界碰撞了，然后两个一起消失了
  • 需要把Boundary加上一个新的tag

    1 2 3 4

    if (other.tag == "Boundary") { return; }

爆炸！就是艺术！

• 在contact destroy的文件里面增加新的爆炸效果
• 新建一个explosion的gameobject，给这个对象赋值位置Instantiate(explosion, transform.position, transform.rotation);
• 给player一个新的tag，然后在碰撞里面判断是陨石撞player还是陨石撞激光，赋值不同的爆炸效果
• 把mover增加到陨石里面，速度设置为负值，这样陨石就能往自己身上掉了

game controller

• 创建整个游戏的逻辑
• 设置好的陨石创建成新的prefab
• 创建一个新的对象作为控制器，加入一个新的对象hazard，初始化好掉下来的敌人的位置，让敌人可以从随机的位置往下掉
• 每次掉落之间隔着时间（这部分和C++有些不一样），把所有的掉落放在一个while里面
• 去掉剩余的爆炸效果

score，audio，building

加声音

• 首先把陨石爆炸的背景音加到陨石的prefab里面
• 背景音乐加到game controller，武器的音乐加到player
  • 武器的音乐需要在每次发射的时候触发
• 调整各个音量的大小

计算score

• 新建一个text，设定好这个text的字体效果之类的
• 然后把这个text reference到gamecontroller里面，然后把最开始的分数初始化，并且写出来更新score的代码
• 把这个score reference陨石里面

增加文字效果

• 需要增加重新开始游戏和游戏结束的text
• 在游戏逻辑里面加上的是这个玩意怎么更新和计算，需要两个flag判断有没有游戏结束
• 需要在碰撞里面把player弄死

增加最后的效果

• 增加陨石
  • 复制之前的asteroid并且给他们不同的模型和碰撞
  • 把之前的对象改成一个数组就可以handle很多个对象了，随机选择
• 增加移动的小星星（项目里面自带的）
• 让背景重复起来
  • 把背景设置在一个范围内，一旦超过了这个范围就重新开始

无法打开源文件问题

• 直接从老师那里得到的项目，第一次运行直接出错，查了一下主要需要注意下面几个
  • 装VS的时候有没有装标准库之类的
  • 尝试使用window的其他版本的SDK
    • 右键项目，属性里面
• 上面两个问题都可以在VS的installer里面找到相关的安装

多个main的问题

• 这回的文件里面有两个cpp都带着main，如果想要运行的话需要把一个cpp右键移除出项目再运行另一个

最近写面试题的时候遇到了自己都想不到的奇怪小错误

多维数组

在创建多维数组的时候，本来应该是用嵌套的for循环来生成[[0 for i in range(m)] for j in range(n)]
(因为一般网测不能调用numpy，不然就直接用numpy搞了)

但是最近想要偷懒的时候尝试用 [[0] * n] * m 来创建，结果疯狂遭遇bug。

最终原因是发现这样创建出来的数组，每一行都是第一行的引用，所以每次操作大家都会一起变

(但是这种方法可以创建一维的)

list的复制

我一直以为a=b就是list的复制了，但是并不是这样的！！这样的话a是一个关于b的reference，并不是复制b，改变的时候是会一起改变的

下面几种方法可以用：

• a = list(b)
• a = b[:]
• a = b * 1
• a = copy.copy(b) #需要import copy