• 一图流解释 Alpha-Beta 剪枝(Alpha-Beta Pruning)

    Alpha-Beta剪枝用于裁剪搜索树中不需要搜索的树枝,以提高运算速度。它基本的原理是:

    • 当一个 Min 节点的 β值≤任何一个父节点的α值时 ,剪掉该节点的所有子节点
    • 当一个 Max 节点的 α值≥任何一个父节点的β值时 ,剪掉该节点的所有子节点

    下面为只使用 MiniMax 和使用 Alpha-Beta 剪枝的简单对比。

    MiniMax search without alpha-beta pruning
    MiniMax search with alpha-beta pruning

    需要注意的是,剪枝的效果与树节点的访问顺序有关。

    Alpha-Beta剪枝的伪代码如下:

    Initialize MAX_VALUE(node,game,-∞,∞)
    
    function MAX_VALUE(state,game,α,β) returns the minimax value of state
        inputs: state, current state in game
                game, game description
                α, the best score for MAX along the path to state
                β, the best score for MIN along the path to state
    
        if CUTOFF_TEST(state) then return EVAL(state)
        for each s in SUCCESSORS(state) do
            α = MAX(α, MIN_VALUE(s,game,α,β))
            if α ≥ β then return β
        end
        return α
    
    function MIN_VALUE(state,game,α,β) returns the minimax value of state
        if CUTOFF-TEST(state) then return EVAL(state)
        for each s in SUCCESSORS(state) do
            β = MIN(β, MAX_VALUE(s,game,α,β))
            if α ≥ β then return α
        end
        return β

    下面用一个例子说明。规定从左节点开始展开。原搜索树为:

    阅读更多…
  • 使用 Python OpenCV 3.4.x 进行 SIFT 特征检测与匹配

    前言

    Harris算法和Shi-Tomasi 算法,由于算法原理,具有旋转不变性,在目标图片发生旋转时依然能够获得相同的角点。但是如果对图像进行缩放以后,再使用之前的算法就会检测不出来,如图:

    图像放大,窗口不变,导致检测结果发生变化

    在2004年,University of British Columbia 的 D.Lowe 在他的论文 Distinctive Image Features from Scale-Invariant Keypoints 中提出了一个新的算法,Scale Invariant Feature Transform (简称SIFT),它可以提取关键点及计算其描述符。OpenCV的文档指出这篇论文容易理解,推荐阅读。

    SIFT算法主要有4个步骤,详情请见文末的相关参考。

    流程

    1. 尺度空间极值检测(Scale-space Extrema Detection)
    2. 关键点定位(Keypoint Localization)
    3. 方向分配(Orientation Assignment)
    4. 关键点描述符(Keypoint Descriptor)
    阅读更多…
  • 霍夫变换(Hough Transform)

    简介

    霍夫变换(Hough Transform)最初用于检测图像中的直线或者圆等几何图形,主要应用在图像分析、计算机视觉和数字图像处理领域。后来经过拓展,可适用于任意图形的检测,及一些参数取值的检测。

    霍夫直线变换的基本思想

    如果两点 (xi, yi) 和 (xj, yj) 都在一条直线上,那么它们在x-y平面上有相同的斜率和y轴的截距。

    对于一个点 (xi, yi) ,经过直线 yi = axi + b,其中a为斜率,b为y轴截距。可以把该式改写为 b = (-xi)a+ yi ,使a为自变量,b为因变量,a可取[amin, amax],代入a可求出对应的b值。a和b的关系可以在参数空间(即a-b平面)上作图。把参数空间分隔为一个一个格子(累加器),然后把 (a, b) 对应的格子A(a, b) 加 1。
    也就是说,一个点可以使参数空间的一系列累加器都加 1。

    对于另外一个点 (xj, yj) ,把 yj = axj + b 改写为 b = (-xj)a+ yj ,作同样的操作,对应的一系列累加器加1。

    阅读更多…
  • Python 的 __new__() 方法与实践

    本文主要转自:http://www.cnblogs.com/ifantastic/p/3175735.html

    __new__() 是在新式类中新出现的方法,它作用在构造方法建造实例之前,可以这么理解,在 Python 中存在于类里面的构造方法 __init__() 负责将类的实例化,而在 __init__() 启动之前,__new__() 决定是否要使用该 __init__() 方法,因为__new__() 可以调用其他类的构造方法或者直接返回别的对象来作为本类的实例

    如果将类比喻为工厂,那么__init__()方法则是该工厂的生产工人,__init__()方法接受的初始化参数则是生产所需原料,__init__()方法会按照方法中的语句负责将原料加工成实例以供工厂出货。而__new__()则是生产部经理,__new__()方法可以决定是否将原料提供给该生产部工人,同时它还决定着出货产品是否为该生产部的产品,因为这名经理可以借该工厂的名义向客户出售完全不是该工厂的产品。

    __new__() 方法的特性:

    • __new__() 方法是在类准备将自身实例化时调用
    • __new__() 方法始终都是类的静态方法,即使没有被加上静态方法装饰器

    类的实例化和它的构造方法通常都是这个样子:

    class MyClass(object):
        def __init__(self, *args, **kwargs):
            pass
    
    myclass = MyClass(*args, **kwargs)  # 实例化

    正如以上所示,一个类可以有多个位置参数和多个命名参数,而在实例化开始之后,在调用 __init__() 方法之前,Python 首先调用 __new__() 方法:

    def __new__(cls, *args, **kwargs):
        pass

    第一个参数cls是当前正在实例化的类。

    如果要得到当前类的实例,应当在当前类中的 __new__() 方法语句中调用当前类的父类的 __new__() 方法。例如,如果当前类是直接继承自 object,那当前类的 __new__() 方法返回的对象应该为:

    def __new__(cls, *args, **kwargs):
        ...
        return object.__new__(cls, *args, **kwargs)  # Python 2 是这样的,但这不适用于Python 3,会报错,后文不重复提示这点

    注意:
          事实上如果(新式)类中没有重写__new__()方法,即在定义新式类时没有重新定义__new__()时,Python默认调用该类的直接父类的__new__()方法来构造该类的实例,如果该类的父类也没有重写__new__(),那么将一直按此规矩追溯至object的__new__()方法,因为object是所有新式类的基类。
          而如果新式类中重写了__new__()方法,那么你可以自由选择任意一个的其他的新式类(必定要是新式类,只有新式类必定都有__new__(),因为所有新式类都是object的后代,而经典类则没有__new__()方法)的__new__()方法来制造实例,包括这个新式类的所有前代类和后代类,只要它们不会造成递归死循环。具体看以下代码解释:

    class Foo(object):
        def __init__(self, *args, **kwargs):
            ...
        def __new__(cls, *args, **kwargs):
            return object.__new__(cls, *args, **kwargs)    
    
    # 以上return等同于 
    # return object.__new__(Foo, *args, **kwargs)
    # return Stranger.__new__(cls, *args, **kwargs)
    # return Child.__new__(cls, *args, **kwargs)
    
    class Child(Foo):
        def __new__(cls, *args, **kwargs):
            return object.__new__(cls, *args, **kwargs)
    
    class Stranger(object):  # 在制造Stranger实例时,会自动调用 object.__new__(cls)
        ...
    
    # 如果Child中没有定义__new__()方法,那么会自动调用其父类的__new__()方法来制造实例,即 Foo.__new__(cls, *args, **kwargs)。
    # 在任何新式类的__new__()方法,不能调用自身的__new__()来制造实例,因为这会造成死循环。因此必须避免类似以下的写法:
    # 在Foo中避免:return Foo.__new__(cls, *args, **kwargs) 或 return cls.__new__(cls, *args, **kwargs)。Child同理。
    # 使用object或者没有血缘关系的新式类的__new__()是安全的,但是如果是在有继承关系的两个类之间,应避免互调造成死循环,例如:(Foo)return Child.__new__(cls), (Child)return Foo.__new__(cls)。

    通常来说,新式类开始实例化时,__new__()方法会返回cls(cls指代当前类)的实例,然后该类的__init__()方法作为构造方法会接收这个实例(即self)作为自己的第一个参数,然后依次传入__new__()方法中接收的位置参数和命名参数。

    注意:如果__new__()没有返回cls(即当前类)的实例,那么当前类的__init__()方法是不会被调用的。如果__new__()返回其他类(新式类或经典类均可)的实例,那么只会调用被返回的那个类的构造方法【不包括__init__()方法】

    class Foo(object):
        def __init__(self, *args, **kwargs):
            ...
        def __new__(cls, *args, **kwargs):
            return object.__new__(Stranger, *args, **kwargs)  
    
    class Stranger(object):
        ...
    
    foo = Foo()
    print type(foo)    
    
    # 打印的结果显示foo其实是Stranger类的实例
    
    # 因此可以这么描述__new__()和__init__()的区别,在新式类中__new__()才是真正的实例化方法,为类提供外壳制造出实例框架,然后调用该框架内的构造方法__init__()使其丰满。
    # 如果以建房子做比喻,__new__()方法负责开发地皮,打下地基,并将原料存放在工地。而__init__()方法负责从工地取材料建造出地皮开发招标书中规定的大楼,__init__()负责大楼的细节设计,建造,装修使其可交付给客户。

    ================ 以上是转载的原文 =========================

    下面是我的一点使用经验。此前我也没具体使用过__new__()方法,只是大概听过有这么一个事。

    最近项目新增了一种网络协议,而API不变,希望同时适配不同的网络协议(数据包中有给出版本号可以判断)。然后就想到了在实例化的__new__()方法里面返回一个其他类的实例,进而拜读了原文……

     

    粗略阅读原文后,写出来了类似这样的代码:

    condition = None
    
    class A(object):
        def __new__(cls, *args, **kwargs):
            print('A new')
            if condition == 'A':
                return object.__new__(cls)  # cls == A
            elif condition == 'B':
                return object.__new__(B)
    
        def __init__(self, value):
            self.value = value
    
    
    class B(object):
        def __new__(cls, *args, **kwargs):
            print('B new')
            return object.__new__(B)
    
        def __init__(self, value):
            self.value = value
    
    condition = 'A'
    a = A(123)
    print(type(a))
    print(a.value)
    
    condition = 'B'
    b = A(456)
    print(type(b))
    print(b.value)

    运行结果为:

    A new
    <class '__main__.A'>
    123
    
    A new
    <class '__main__.B'>
    Traceback (most recent call last):
      File "/xxxxx/main.py", line 31, in <module>
        print(b.value)
    AttributeError: 'B' object has no attribute 'value'

    A这块是正常的,而B这块就很不正常了:没有value这个属性不说,print(‘B new’) 都没有执行!
    ——这是 return object.__new__(B) 导致的,因为object的__new__() 方法没有 print(‘B new’) 这句。

    我们把 return object.__new__(B) 改成 return B.__new__(cls) ,像这样:

    class A(object):
        def __new__(cls, *args, **kwargs):
            print('A new')
            if condition == 'A':
                return object.__new__(cls)  # cls == A
            elif condition == 'B':
                return B.__new__(cls)

    这下执行结果有显示 B new 了。然而,’B’ object has no attribute ‘value’,还是没有。
    把 return B.__new__(cls) 改为 return B.__new__(cls, *args, **kwargs) ,把参数传进去,结果还是一样。

    难道是B类的问题?把它改成:

    class B(object):
        def __new__(cls, *args, **kwargs):
            print('B new')
            return object.__new__(B, *args, **kwargs)

    依旧报错(在Python 3下还会报 TypeError: object() takes no parameters)!有点抓狂了,再去精读一下,发现了上面被我标红的一句“如果__new__()返回其他类(新式类或经典类均可)的实例,那么只会调用被返回的那个类的构造方法”。就是说,__init__()方法没有被调用啊!我来手动调用一下:

    condition = None
    
    class A(object):
        def __new__(cls, *args, **kwargs):
            print('A new')
            if condition == 'A':
                return object.__new__(cls)  # cls == A
            elif condition == 'B':
                return B.__new__(cls, *args, **kwargs)
    
        def __init__(self, value):
            self.value = value
    
    
    class B(object):
        def __new__(cls, *args, **kwargs):
            print('B new')
            self = object.__new__(B)  # 创建对象
            self.__init__(*args, **kwargs)  # 初始化对象
            return self  # 初始化之后再返回结果
    
        def __init__(self, value):
            self.value = value
    
    condition = 'A'
    a = A(123)
    print(type(a))
    print(a.value)
    
    condition = 'B'
    b = A(456)
    print(type(b))
    print(b.value)

    这次终于和期望一致了……

     

    总结:

    1. 如果__new__()返回其他类的实例,那么只会调用被返回的那个类的构造方法【不包括__init__()方法】;
    2. 如果__new__()返回当前类的实例,可以直接 return object.__new__(cls) ,不需要手动传参数;若返回其他类的参数,需 return ClassName.__new__(cls, *args, **kwargs) 手动传参数,万万不能 return object.__new__(ClassName, *args, **kwargs) 。
  • 搭建 git 本地中转站

    局域网内有多台开发机器,因为种种原因,与服务器同步代码有不便之处。于是打算在本地做一个 git 的镜像,所有机器都统一 clone 这个本地镜像库,然后由这个镜像库负责与服务器更新。

    1. 使用 –mirror 参数 clone

    cd /some/where/
    git clone --mirror git@server.com:user/someproject.git

    执行以上命令后,在本地的 /some/where/someproject.git/ 下建立了对应项目的镜像,它是一个裸版本库(不包含工作区,直接就是版本库的内容),对于我这样的新手来说不是很好懂什么是“裸版本库”,但是进去目录看一下就知道了。

    2. 本地操作

    在同一台机器上,我们这样写代码:

    cd ~/workspace/
    git clone /some/where/someproject.git

    这样 clone 出来的就是平时熟悉的、包含工作区的内容,平时怎么用就怎么用。
    阅读更多…

  • 申请 Let’s Encrypt 通配符 HTTPS 证书,并配置 Apache2

    3月中旬, Let’s Encrypt 终于正式发布通配符 HTTPS 证书了,赶紧去申请一个玩玩(然而我的网站暂时还不支持加SSL,只能先在VPS上试试了 /(ㄒoㄒ)/)。

    1. 安装 Let’s Encrypt 客户端

    系统为 Ubuntu 16.04,参照 Certbot 官网的教程,运行以下命令安装(我这里由于是用 root 用户,所以非 root 请自行加 sudo):

    # apt-get update
    # apt-get install software-properties-common
    # add-apt-repository ppa:certbot/certbot
    # apt-get update
    # apt-get install python-certbot-apache

    2. 获取通配符证书

    先查看 certbot 的版本是否 > 0.22,否则不支持通配符证书:

    # certbot --version
    certbot 0.22.2
    

    自带的 –apache 模式似乎并不能处理通配符证书的情况,所以需要手动获取。

    在对应的 support 页面[1]中,了解到还需要手动指定服务器,执行:

    # certbot -d *.xxxx.com --manual --preferred-challenges dns-01 --server https://acme-v02.api.letsencrypt.org/directory certonly

    之后按提示操作,并添加自己的域名的 TXT 记录,以通过 ACME 认证。完成后,可在 /etc/letsencrypt/live/xxxx.com/ 下看到几个 .pem 文件。

    阅读更多…

  • 在OpenWrt中使用iptables过滤特定字符串

    当前的需求如下:需要选择性地过滤掉远程客户端向NAT下的服务器发送的特定请求。
    网络拓扑:Client—Internet—WAN–OpenWrt Router–LAN–Server

    经过实践,方法如下:

    # 安装iptables-mod-filter
    opkg update
    opkg install iptables-mod-filter
    
    # 丢弃包含 abcd 字符串的数据包
    iptables -I FORWARD 1 -p tcp -m string --string "abcd" --algo bm -j DROP
    iptables -I FORWARD 1 -p udp -m string --string "abcd" --algo bm -j DROP
    
    # 恢复正常
    iptables -L --line-numbers
    iptables -D FORWARD 1   # 这个1是刚才输出的对应序号

    在执行命令后,在LAN抓包,发现对应的数据包果然不见了,证明命令生效。再执行后续的命令,在LAN抓包,又可恢复正常的不丢包状态。

    对于其他网络拓扑,可把FORWARD链改为INPUT或OUTPUT。

  • 在cmd中使用echo输出空行

    众所周知,在Windows的cmd中,echo可以用来输出信息,但如果想输出空行,用“echo 加空格”的方法,无论加多少个空格都是不行的,都相当于“echo”,而返回当前的echo状态(on/off)。

    找了一下,方法至少有10种:

    @echo off 
    
    echo= 
    echo, 
    echo; 
    
    echo+ 
    echo/ 
    echo[ 
    echo] 
    
    echo: 
    echo. 
    echo\

    这10种方法可以分为三组,每组的效率依次递减。至于为什么效率会低,可参考本文转载的出处。

    简而言之,要输出一个空行,用第一组的 “=” “,” “;” 紧接在echo后面,是最好的选择。

    转载自 http://www.jb51.net/article/30987.htm

  • 所有无线设备都不安全了?Wi-Fi加密被破解影响有限

    多年来保护我们无线连接安全的WPA2加密协议日前被成功破解。比利时鲁汶大学的Mathy Vanhoef发现了WPA2加密协议的漏洞,并披露了实施攻击的详细细节。Mathy Vanhoef计划将在11月1日举办的计算机和通信安全(CCS)2017会议和Black Hat欧洲会议上发表这一研究成果。

    WPA2被破解 全世界的WiFi设备都不安全了?

    在这一消息被披露之后,有些媒体认为,由于目前几乎所有的WiFi加密都使用了WPA/WPA2加密协议,这一协议被黑客破解之后,全世界的WiFi上网设备都不安全了。

    Mathy Vanhoef称,这一漏洞名为“KRACK”,是“Key Reinstallation Attack”(密钥重安装攻击)的缩写。Mathy Vanhoef表示,通过研发,其发现WPA2在四路握手(four-way handshake)时,允许拥有预共享密码的新设备加入网络。

    有中国黑客教父之称的goodwell对搜狐科技表示,这个KRACK ATTACK攻击应该是目前最取巧的针对WPA/WPA2的中间人攻击方法。这一攻击并不针对WPA加密本身,而是通过多次重播四次握手的信息3,来强制复位client本地保存的WPA2密钥,即把原来正确真实的WPA密码替换掉,不破解直接替换成全0密钥,这样就可以将受害者连到伪造的AP上,无需任何提示。再配合SSLStrip之类的工具做中间人,就圆满地实现了基于WIFI的无缝中间人攻击。

    goodwell称,攻击者并不能通过这种攻击手段达到蹭网的目的。主要是影响客户端而非路由器。最冤的是Linux系统,其只有wpa_supplicant,严格遵守IEEE“不能重复使用密钥”的提醒,密钥用后即刻清零。也因为如此,其连接密钥就真的变成全“0”,造成了比其他设备严重得多的问题。

    Mathy Vanhoef也确认,这种攻击对Linux和Android 6.0或更高版本是非常有破坏性的。这是因为Android和Linux可以被欺骗(重新)安装一个全零加密密钥。

    goodwell对搜狐科技表示,这种攻击并不能攻击WiFi路由器,而是在用户连接到路由器并正常使用后,攻击者切入进来,替换用户原来的连接,让其连到攻击者的路由器上去,从而达到数据挟持的目的。

    KRACK 攻击 Wi-Fi WPA2 加密演示视频

    业界厂商声明将尽快发布补丁

    这一漏洞披露之后,微软称于10月10日发布安全补丁,使用Windows Update的客户可以自动或手动升级补丁,达到自动防卫的目的。

    Google称,其已经了解到这一问题的存在,未来几周内会给任何受影响的设备打上补丁。

    而苹果也表示,已经证实iOS、MacOS、WatchOS、TVOS会受影响,在未来几周内会通过软件升级的形式提供修复补丁。

    Linksys/贝尔金称,已经了解到了KRACK漏洞的存在。安全团队正在确认这一漏洞的影响,会根据情况提供支持及升级。网件也称,已经为多款产品发布了修复补丁,公司也正在为其它产品开发相关补丁。用户可以在支持页面查询升级情况。

    KRACK攻击原理致其影响程度有限

    尽管这一漏洞几乎影响了所有的WiFi上网设备。但专注无线安全的RadioWar创始人SandMAN对搜狐科技称,利用KRACK漏洞,对于近端攻击或者劫持信息的人来说,这个手法很好用。但这一攻击手法并无法批量对无线客户端进行攻击,只能一个一个地攻击客户端,使用户在不知情的情况下连接到伪造的AP。因此,其攻击效率很低下。对动辄数以亿计的无线设备来讲,个人中招的机率非常低。

    SandMAN称,KRACK攻击的意义在于大型WLAN或者是特定的核心目标。另外,现有的WiFi防御对这种攻击也是可以做到预先防御的,因为攻击的套路本身是不会改变的。

    提高WiFi设备安全要做这样的功课

    360方面对搜狐科技表示,要避免受到KRACK攻击,用户需要做如下功课:

    1.及时更新无线路由器、手机,智能硬件等所有使用WPA2无线认证客户端的软件版本(在有补丁的前提下)。

    2.有条件的企业及个人请合理部署WIPS,及时监测合法WiFi区域内的恶意钓鱼WiFi,并加以阻断干扰,使其恶意WiFi无法正常工作。(WIPS的重要性)

    3.无线通信连接使用VPN加密隧道及强制SSL规避流量劫持与中间人攻击造成的信息泄漏。

    4.国标WAPI无线认证暂不受该漏洞影响。

    搜狐科技 文/丁丁

     

    我的总结:攻击者在抓到目标AP的BSSID和被攻击目标的MAC地址后,通过修改自身网卡的MAC地址为目标AP的MAC地址,以作为伪装的AP(伪装AP的密码与目标AP的密码无关);然后让被攻击目标神不知鬼不觉地转而连接伪装AP,连接成功后,所有的流量都会经过攻击者(MITM)。对于HTTP等不加密的协议,可以轻松抓下来;对于HTTPS,作者使用了sslstrip软件,把HTTPS降为HTTP,然后就可以抓取下来明文数据。