图像二值化

图像二值化是将像素点的灰度值设为0或255,使图像呈现明显的黑白效果。二值化之前需要把图像进行灰度处理。

(全局阈值法)固定阈值法   
Threshold为全局阈值,但是全局阈值不好确定,先尝试使用灰度图的平均像素作为全局阈值。

import cv2
import numpy as np
import matplotlib.pyplot as plt
image = cv2.imread("chatgpt.png")
# 加权求出灰度图
def weight_gray(image):
    weight_image = image[:, :, 0] * 0.11 + image[:, :, 1] * 0.59 + image[:, :, 2] * 0.3 # 三个通道加权求和
    weight_image = weight_image.astype(np.uint8)
    return weight_image
    
"""
像素平均值二值化
gray: 灰度图(ndarray)
return: 二值化图像(ndarray)
"""
def mean_threshold(gray):
    threshold = np.mean(gray)# 求平均像素值
    binary = np.where(gray >= threshold, 255, 0)
    binary = binary.astype(np.uint8)
    return binary
    
gray = weight_gray(image)
plt.figure(figsize=(10,10))
plt.subplot(121)#画子图   
plt.imshow(gray, cmap='gray')
plt.title("gray")
plt.subplot(122)#画子图   
plt.title("threshold")
plt.imshow(mean_threshold(gray), cmap='gray')

OTSU算法
OTSU是阈值分割中一种常用的算法,它可以根据图像自动生成最佳分割阈值。 OTSU的核心思想是类间方差最大化。

  1. 初始化一个阈值T0,将图像分为前景f和背景b;
  2. 图像像素点个数为图像N=height x width,前景像素个数Nf,背景像素个数Nb;
  3. 图像灰度等级L-1(0~255=256),每个灰度等级像素个数Ni,满足以下公式:
  4. 前景和背景的灰度平均值分别为:
  5. 整个图像灰度平均值:
  6. 求前景和背景之间的方差:
  7. 找到阈值T0,使得公式4最大;
  8. 怎么找?可以采用优化算法,本文中直接遍历灰度等级,查找最优阈值。
"""
统计像素点函数
image: 输入灰度图(ndarray)
reutrn: {像素:个数}(dict)
"""
def pixel_num(image):
    h, w = image.shape
    pdict = {}
    for i in range(h):
        for j in range(w):
            if image[i,j] in pdict:
                pdict[image[i,j]] += 1
            else:
                pdict[image[i,j]] = 0
    return pdict

"""
求公式4中sigma2的值
T0: 预设阈值(int)
gray: 灰度图(ndarray)
L: 灰度等级(int)
"""
def sigma2(T0, gray, L=256):
    h, w = gray.shape
    N = h * w
    pdict = pixel_num(gray)
    pf = sum([v for k,v in pdict.items() if k < T0]) / N#公式1
    pb = sum([v for k,v in pdict.items() if k >= T0]) / N#公式1
    pf = [pf if pf > 1e-6 else 1e-6][0]#控制最小值,避免除以0
    pb = [pb if pb > 1e-6 else 1e-6][0]#控制最小值,避免除以0
    mf = sum([k * pdict.get(k, 0) / N for k in range(T0)]) / pf#公式2
    mb = sum([k * pdict.get(k, 0) / N for k in range(T0, L)]) / pb#公式2
    M = pf * mf + pb * mb#公式3
    s2 = pf * (mf - M) ** 2 + pb * (mb - M) ** 2#公式4
    return s2, T0

"""
遍历查找最大sigma2
gray: 灰度图(ndarray)
L: 灰度等级(int)
"""
def otsu(gray, L=256):
    smax = 0
    tmax = 0
    for t in range(1, L):
        s2, T0 = sigma2(t, gray, L)
        if s2 > smax:
            smax = s2
            tmax = T0
    return smax, tmax

"""
根据最佳阈值求二值化图像
threshold: 最佳阈值(int)
return: 二值化图像(ndarray)
"""
def otsu_threshold(max_threshold, gray):
    threshold = np.mean(gray)
    binary = np.where(gray >= max_threshold, 255, 0)
    binary = binary.astype(np.uint8)
    return binary
    
smax, tmax = otsu(gray, 256)  
oimage = otsu_threshold(tmax, gray)
plt.figure(figsize=(10,10))
plt.subplot(121)#画子图
plt.imshow(mean_threshold(gray), cmap='gray')
plt.title("threshold")
plt.subplot(122)#画子图
plt.title("otsu")
plt.imshow(oimage, cmap='gray')

原文链接:https://blog.csdn.net/weixin_43828944/article/details/128911462

正整数倒数和

正整数倒数的前n项和形式是这样的.正整数倒数的前n项和
数学家和广大的数学爱好者凭着过往积累的自信,认为应该也能推导出一个公式来计算上式,这个自信来自于下面的事实.

我们能求正整数的前n项和.

我们能求正整数平方的前n项和.

我们能求正整数立方的前n项和.

可是,几百年的实践至今,我们依然找不到合适的公式去计算从1开始的连续的正整数的倒数和.

近似估计

正整数的倒数数列也称为调和数列.这个无穷数列的和是发散的.

但并不说,数列发散就没有求和公式.比如,正整数数列也是发散的,但显然有求和公式;首项大于0、公比大于1的等比数列也是发散的,但也有求和公式.

不管怎样,这个调和数列目前就是没有找到合适的求和公式.我们只能尝试去估计它的范围.

当n很大的时候,我们能够用下面的公式去估计它.

欧拉常数

但是,在我们目前学到的初等数学中,如何处理这类求和问题呢?

基本的思想就是,通过适当地放缩,放缩为能够求和的形式,最后研究这个和式的范围.

用函数不等式实现放缩

能够用于放缩的不等式有: lnx<=x-1 (当且仅当 x=1时取等号)

然后采用赋值的方法朝正整数的倒数和靠近.

以上是朝小的方法去放缩,如果我们希望朝大的方向去放缩呢?

总结,用放缩法得出正整数前n项倒数和的范围是

数学家解决了42的丢番图难题,顺便回答了生命的意义[转]

在道格拉斯·亚当斯的科幻系列小说《银河系漫游指南》中,程序员向这台银河系最大的超级计算机提出了一个终极问题:生命、宇宙和一切的意义。经过750万年的处理,计算机得出了一个答案:42。

2019年,两位数学家使用了一个由50万台计算机组成的全球网络来解决一个百年前的数学难题,这个难题恰好包含了最关键的数字:42。

这个问题至少可以追溯到1955年,并且可能早在公元三世纪希腊思想家就开始思考这个问题了。这个问题是:你怎么把1到100之间的每一个数字表示为三个整数的立方的总和?或者用代数的方法表示,如何解x^3+y^3+z^3=k,其中k等于1到100之间的任何整数?

这个看似简单的难题被称为丢番图方程,以亚历山大的古代数学家丢番图命名,他在1800年前提出了一组类似的问题。

20世纪50年代重温这一难题的现代数学家很快找到了答案,当时k等于许多较小的数,但很快就出现了一些特别顽固的整数。最棘手的两个数字,分别是33和42。

今年4月,英国布里斯托尔大学数学家安德鲁·布克(Andrew Booker)解决了33难题。布克用一种计算机算法寻找x、y和z值在正负99万亿之间的丢番图方程的解,经过数周的计算后,找到了33的解。如你所见,答案是超长的。

8866128975287528^3-8778405442862239^3-2736111468807040^3=33

尽管如此,这一详尽的搜索仍然没有找到42的解。这表明如果解存在,一些整数必须大于99万亿。计算这么大的数值需要极大的计算能力,因此在他的下一次尝试中,布克请求麻省理工学院数学家安德鲁·萨瑟兰(Andrew Sutherland)的帮助,他帮助布克在一个名为慈善引擎(Charity Engine)的全球计算机网络上预定了一段时间。

根据布里斯托尔大学的一份声明,这个网络是一个“世界性的计算机”,它借用了全球50多万台家用电脑的闲置计算能力。利用这台众包的超级计算机和100万小时的处理时间,布克和萨瑟兰最终找到了k = 42的丢番图方程的答案。

所以,直截了当地说,生命、宇宙和一切事物的意义的问题和答案是:(-80538738812075974)^3+(80435758145817515)^3+ (12602123297335631)^3 = 42。

毕达哥拉斯素数

毕达哥拉斯质bai数是指可以表示为 4n + 1 形式的质数,若直角三角形的三边均为整数,斜边为质数,其斜边的边长即为毕达哥拉斯质数.
前几个毕达哥拉斯质数为
5,13,17,29,37,41,53,61,73,89,97,101,109,113,… (OEIS中的数列A002144).
费马平方和定理陈述,毕达哥拉斯质数可以表示为二个平方数的和,其他质数除了2以外(2=1^2+1^2)都不能表示为二个平方数的和.毕达哥拉斯质数及2会在高斯整数的范数中出现,其他的质数不会是高斯整数的范数.
毕达哥拉斯质数可以表示为一个奇数的平方数与一个偶数的平方数的和:
毕达哥拉斯质数是可以表示为a^2+4b^2形式的质数.
依照二次互反律陈述,若p及q为奇质数,其中至少有一个为毕达哥拉斯质数,则 p是模q的二次剩余的充份必要条件是q是模p的二次剩余 .相反的,若p及q都不是毕达哥拉斯质数,则p是模q的二次剩余的充份必要条件是q不是模p的二次剩余.−1是是模p的二次剩余的充份必要条件是p是毕达哥拉斯质数(或2).
在p为毕达哥拉斯质数的域Z/p中,多项式x^2 = -1有二个解.

素数部分定理

1.素数本身只能被自身整除。也就是质数的约数只有两个,即1和本身。
2.所有大于3的素数,都可以用6n-5 和6n-1表达,或6n+1和6n+5来表示。
3.若”k”不是”6xy+x-y”的方程解,也就是”k≠6xy+x-y”,那么”6k-1″一定是个素数。 4.若”k”不是”6xy+-(x+y)”的方程解,也就是”k≠6xy+-(x+y)”,那么”6k+1″一定是个素数。
5.由3.和4.假设,素数集合是由两条元素不重复的独立集合。

6.质数的个数公式π(n)是不减函数。且素数的分布个数接近于x/ln (x),这是素数定理。
7.素数本身是不可能有传统意义上的通项公式。
8.任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,当代入1时候这种分解是无限的,去掉1时分解则是唯一的。
9.质数的个数是无限的。
10.所有大于10的质数中,个位数只有1,3,7,9。

11.若n为正整数,在n^2到(n+1)^2之间至少有一个质数。
12.若n为大于或等于2的正整数,在n到n!之间至少有一个质数
13.若质数p为不超过n(n≥4)的最大质数,则p>n/2。
14.两个连续素数最大间隔可以任意大。
15.任意大于5的奇数都可以表示为三个素数之和。

加密中数论基础知识,RSA加密算法及证明

记法

设n为正整数,a和b为整数,若a和b被n除后所得余数相同,
称a和b模n同余,记为a≡b(mod n);或  a≡b(% n)
此式被称为同余式。

或表达为:a % n =b % n  或 a mod n =b mod n;

若n能整除a则同余式表示为a ≡ 0(mod n)。

欧拉函数

对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数,记作φ(N)。即欧拉函数。

欧拉定理:

若N>2; a与N互质,则a^(φ(N))  ≡ 1 (mod N )

欧拉函数的性质:

(1)   p^k型欧拉函数:

若N是质数p(即N=p), φ(N)= φ(p)=p-p^(k-1)=p-1。

若N是质数p的k次幂(即N=p^k),φ(N)=p^k-p^(k-1)=(p-1)p^(k-1)。

(2)  mn型欧拉函数

若m,n互质,φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

(3)  特殊性质:

若n为奇数时,φ(2n)=φ(n)。

费马小定理:

设任意整数a和素数p互素 ,则 a^p-1 ≡ 1(mod p)

运算规则

模运算与基本四则运算有些相似,但是除法例外。其规则如下:

 (a + b) % p = (a % p + b % p) % p (1)

 (a - b) % p = (a % p - b % p) % p  (2)

 (a * b) % p = (a % p * b % p) % p (3)

 (a^b) % p =   ( (a % p)^b ) % p     (4)

结合率:

((a+b) % p + c) % p = (a + (b+c) % p) % p (5)

 ((a*b) % p * c)% p = (a * (b*c) % p) % p   (6)

交换率:

 (a + b) % p = (b+a) % p (7)

 (a * b) % p = (b * a) % p (8)

分配率:

 ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p (9)

重要定理

若a≡b (% p),则对于任意的c,都有(a + c) ≡ (b + c) (%p);(10)

若a≡b (% p),则对于任意的c,都有(a * c) ≡ (b * c) (%p);(11)

若a≡b (% p),c≡d (% p),则 (a + c) ≡ (b + d) (%p),(a - c) ≡ (b - d) (%p),

(a * c) ≡ (b * d) (%p),(a / c) ≡ (b / d) (%p); (12)

若a≡b (% p),则对于任意的c,都有ac≡ bc (%p); (13)

RSA中重要的推论

m 和 n 是互质的正整数,则:

(a^m) %n  =  ((a%n)^m) %n

推论证明

   a^m % n 
   =a*a ^(m-1) %n
   =(a%n) *(a ^(m-1) %n ) % n  //后续不断展开,一直至a ^0,即共有m项
   =((a%n)^m) %n 

推论中举例:

比如:2^3 mod 5
 = (2 mod 5)^ 3 mod5
 = 8 mod5
 = 3
还有:3^3 mod 2
= (3 mod 2) ^3  mod 2
=1^3 mod 2
=1

加密思路:加密本质上是对加密内容的字节数组进行加密。不是对字符的本身进行加密。这样,整数对整数就可以进行相关的变换,即加密了。

比如:"I love Rust,Julia & Python, they are so cool! "的字节数组为:
[73, 32, 108, 111, 118, 101, 32, 82, 117, 115, 116, 
44, 74, 117, 108, 105, 97, 32, 38, 32, 80, 121, 116, 
104, 111, 110, 44, 32, 116, 104, 101, 121, 32,
 97, 114, 101, 32, 115, 111, 32, 99, 111, 111, 108, 33, 32]

RSA加密算法为:

(1) 取两个大素数p,q (保密);
(2) 计算 n=p*q (公开), φ(n)=(p-1)*(q-1) (保密);
(3) 随机选取整数e,满足 gcd(e, φ(n))=1 (e与φ(n)互素)(公开);
(4) 计算 d 满足 d*e≡1 (mod φ(n)) (保密); (d为e的逆元,可通过扩展的欧几里得算法进行求解)
(5) {e,n}为公钥,{d,n}为私钥,也可以用{e,d}表示密钥对
(6) m为加密内容(如73),此时c为加密后的密文;
       加密时 c = m^e mod n 
       解密时 m = c^d mod n
(7) m为签名内容,
       签名时c = m^d mod n ;
       解密时 m = m^e mod n

为什么RSA算法能保证其安全性?

要破解m =>
必须知道  d或e =>
必须知道  φ(n) =>
必须知道  p及q;  =>
必须能破解 n=p*q =>
大质数因式分解的难度 => 公认

RSA证明

主要要证明m是否c^d mod n。由c = m^e mod n 。设M =m^e
证式
 =    c^d mod n
 =  (m^e mod n )^d mod n 
 =    (M mod n) ^d mod n
 =    M^d mod n                   //见上面的推论
 =    m^(d*e )mod n ; 
因为 d*e≡1 (mod φ(n)) 
得到:d*e =k *φ(n) +1 ; k是正整数。
上面证式还有,
 =    m^(k *φ(n) +1 ) mod n
 =    m^(k *φ(n))*m  mod n     // 
 =    (m^(k *φ(n))mod  n ) *(m mod n)  mod n         //  乘法 
 =    1 * m mod n  // 由欧拉定理
 =    m
 证毕。
 所以解密的公式是对的。

埃拉托斯特尼筛法

求解第N个素数,求第 10,0000、100,0000、1000,0000 … 个素数(要求精确解)。

埃拉托斯特尼筛法(Sieve of Eratosthenes),这是一种非常古老但是非常有效的求解𝑝𝑛pn的方法,其原理非常简单:从2开始,将每个素数的各个倍数都标记成合数。其原理如下图所示:

程序编码就是对数学逻辑的具体实现

为什么你的代码一坨坨?其实来自你有那么多为什么你要这样写代码!
为什么你的代码那么多for循环?因为没有合理的数据结构和算法逻辑。
为什么你的代码那么多ifelse?因为缺少设计模式对业务场景的运用。
为什么你的程序应用复杂对接困难?因为没有良好的系统架构拆分和规划。
为什么你的程序逻辑开发交付慢返工多?因为不具备某些业务场景的开发经验。
为什么你的程序展现都是看上去不说人话?因为没有产品思维都是程序员逻辑的体现。
最终,所有的这些不合理交织在一起,就是你能看到的一坨坨的代码!所以,要想把代码写好、写美,写到自己愿意反复欣赏,那么基本需要你有一定的:基础能力(数据结构、算法逻辑、设计模式)、应用能力(系统架构、开发经验)、拓展能力(产品思维),这三方面综合起来才能更好的开发程序。

数据结构:数组、链表、红黑树 算法逻辑:哈希、扰动函数、负载因子、拉链寻址、

其实我们所开发的业务程序,哪怕是CRUD也都是对数学逻辑的具体实现过程。只不过简单的业务有简单的数学逻辑、复杂的业务有复杂的数学逻辑。数学逻辑是对数据结构的使用,(例如:把大象装进冰箱分几步)合理的数据的结构有利于数据逻辑的实现和复杂程度。

在我们常用的API中,HashMap 就是一个非常好的例子,既有非常好的数据结构的使用,也有强大的数学逻辑的实现。为此也让 HashMap 成为开发过程中非常常用的API,当然也成为面试过程中最常问的技术点。

完善的产品设计需要有对付杠精的思维

如:树上10只鸟开一枪还剩下几只,你会想到什么

  1. 开枪人有没有幻觉?
  2. 枪是真的吗?
  3. 手抢是无声的吗?
  4. 枪声大吗?
  5. 这个城市打鸟犯不犯法?
  6. 确定那只鸟被打死了?
  7. 树上的鸟有没有聋子?
  8. 有没有被关在笼子里或者绑在树上的鸟?
  9. 旁边还有其他树吗?
  10. 鸟是不是真的?
  11. 有残疾或者飞不动的鸟吗?
  12. 打鸟的人眼睛花没花?
  13. 保证是10只吗?
  14. 有没有那种不怕死的鸟?
  15. 会不会一枪打死两只或者更多?
  16. 所有的鸟都可以自由活动飞离树以外吗?
  17. 打死以后挂在树上还是掉下来了?

汉明距离

汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如: 1011101 与 1001001 之间的汉明距离是 2。 2143896 与 2233796 之间的汉明距离是 3。 “toned” 与 “roses” 之间的汉明距离是 3。

汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。

对于固定的长度 n,汉明距离是该长度字符向量空间上的度量,很显然它满足非负、唯一及对称性,并且可以很容易地通过完全归纳法证明它满足三角不等式。 如果把a和b两个单词看作是向量空间中的元素,则它们之间的汉明距离等于它们汉明重量的差a-b。如果是二进制字符串a和b,汉明距离等于它们汉明重量的和a+b或者a和b汉明重量的异或a XOR b。汉明距离也等于一个n维的超立方体上两个顶点间的曼哈顿距离,n指的是单词的长度。 给予两个任何的字码,10001001和10110001,即可决定有多少个相对位是不一样的。在此例中,有三个位不同。要决定有多少个位不同,只需将exclusive OR运算加诸于两个字码就可以,并在结果中计算有多个为1的位。

曼哈顿距离

欧氏距离是人们在解析几何里最常用的一种计算方法,但是计算起来比较复杂,要平方,加和,再开方,而人们在空间几何中度量距离很多场合其实是可以做一些简化的。曼哈顿距离就是由 19 世纪著名的德国犹太人数学家赫尔曼·闵可夫斯基发明的(图 1)。


赫尔曼·闵可夫斯基


赫尔曼·闵可夫斯基在少年时期就在数学方面表现出极高的天分,他是后来四维时空理论的创立者,也曾经是著名物理学家爱因斯坦的老师。

曼哈顿距离也叫出租车距离,用来标明两个点在标准坐标系上的绝对轴距总和。

欧氏距离里的距离计算:

曼哈顿距离中的距离计算:

曼哈顿距离中的距离计算公式比欧氏距离的计算公式看起来简洁很多,只需要把两个点坐标的 x 坐标相减取绝对值,y 坐标相减取绝对值,再加和。

从公式定义上看,曼哈顿距离一定是一个非负数,距离最小的情况就是两个点重合,距离为 0,这一点和欧氏距离一样。曼哈顿距离和欧氏距离的意义相近,也是为了描述两个点之间的距离,不同的是曼哈顿距离只需要做加减法,这使得计算机在大量的计算过程中代价更低,而且会消除在开平方过程中取近似值而带来的误差。不仅如此,曼哈顿距离在人脱离计算机做计算的时候也会很方便。

胡不归问题

胡不归问题,是一个非常古老的数学问题,曾经是历史上非常著名的“难题”。近年来陆续成为各地中考模拟题的小热门考点,学生不易把握,今天给大家普及讲解一下。

话说,从前有一小伙子外出务工,某天不幸得知老父亲病危的消息,便立即赶路回家.小伙子略懂数学常识,考虑到“两点之间线段最短”的知识,就走布满沙石的路直线路径,而忽视了走折线虽然路程多但速度快的实际情况,当赶到家时,老人刚咽了气,小伙子追悔莫及失声痛哭.邻居告诉小伙子说,老人弥留之际不断念叨着“胡不归?胡不归?…”

这个问题引起了人们的思索,小伙子能否节省路上时间提前到家?如果可以,他应该选择一条怎样的路线呢?这就是流传千百年的“胡不归问题.

如图,A是出发点,B是目的地,直线AC是一条驿道,而驿道靠目的地一侧全是砂土,为了选择合适的路线,根据不同路面速度不同(驿道速度为a米/秒,砂土速度为b米/秒),小伙子需要在AC上选取一点D,再折往至B.

上述数学解释用到了三角函数知识将两个线段的系数权重都化为1,从而降低了求最值难度。聪明的同学或许一下就发现转化成了我之前讲过的“将军饮马(小河取水)”模型,进而作对称求得最值。