教你通过python利用近邻法实现图片缩小后变成另一张图（类似幻影坦克）

做一个柔情的程序猿 2021-03-08

1005

近邻法简介

近邻法的一些常见算法包括如下：最近邻法、k-近邻法、近邻法的快速算法、剪辑近邻法、压缩近邻法。

K-近邻法

基本思想：为了提高分类判别的鲁棒性，很自然的引入一种投票机制：选择前若干个离新样本最近的已知样本，通过这些已知样本的类别投票，来决定新样本的类别，这种方法就称作为k-近邻法。

PS: 当k=1时，k-近邻法就是最近邻算法。

错误率：随着k的增加，k-近邻法的渐进错误率逐渐降低，当趋近无穷大时，接近贝叶斯错误率。

问题1：当样本比较稀疏时，前k个近邻到新样本的距离可能会差别很大，此时只根据样本是否在k个近邻中进行投票就显得“有失公允”。

改进：可以引入加权机制，将k个近邻样本到新样本之间的距离作为加权系数，距离近的样本对新样本的影响大。

问题2：需要始终存储所有的已知样本，并将每一个新样本与所有已知样本进行比较和排序，计算量和存储成本都很大。

改进：下面着重介绍的快速算法。

近邻法的快速算法

基本思想：把已知样本集分级划分成多个子集，形成一个树状结构，每个节点是一个子集，每个子集只用少量的样本来代表，通过把新样本按顺序与各节点进行比较来排除不可能包含最近邻的子集，只在最后的节点上才需要与每个样本进行比较。

具体做法：

第一阶段：样本集X的分级分解。

第二阶段：搜索

剪辑近邻法

改进点：在很多情况下，两类数据的分布可能会有一定的重叠，这时样本就不会完全可分，并且分错的样本还将会误导决策，使分类效果不佳，并且可能会使分类面的形状过于复杂。

基本思想：设法将交界区（阴影部分）的已知样本去掉，决策时就不会受到这些样本的影响，使近邻法的决策面更加接近最优分类面。

压缩近邻法

基本思想：从近邻法的分类原理，可以发现，那些原理分类边界的样本对于最后的分类决策没有贡献，只要能够设法找出各类样本中最有利于用来与其他类区分的代表性样本，就可以把很多训练样本都去掉，从而简化决策过程中的计算。

DONDENSE算法

补充：压缩近邻法的思想与后来的支持向量机方法有一些相似之处，

支持向量机求解最大化分类间隔的最优分类面，得到一组能够代表样本集中全部分类信息的支持向量；
压缩近邻法是通过启发式的方法，寻找用较少的样本来代表样本集中的分类信息；
尤其是经过对分类交叠区域的剪辑，可以使两类的边界更清晰，直观上可以提高分类面的推广能力。

图源展示

大图：（图b）

小图：（图a）

代码运行得到的图片：（图c）

功能介绍

利用了近邻法缩放的弱点，可以将图a的像素按顺序嵌入到图b中，然后生成图c。图c看起来和图b是基本一样的。不过，在PS软件或者python的PIL模块中使用近邻法把图c缩小到图a的尺寸时，图a就显示出来了。算是一种形式的“幻影坦克”吧。

代码展示

import sys
from PIL import Image

#将small_img中的像素用近邻法嵌入到big_img中
def my_nearest_resize(big_img, small_img):

    big_w, big_h = big_img.size 
    small_w, small_h = small_img.size 

    dst_im = big_img.copy()

    stepx = big_w/small_w
    stepy = big_h/small_h

for i in range(0, small_w):
for j in range(0, small_h):
            map_x = int( i*stepx + stepx*0.5 )
            map_y = int( j*stepy + stepy*0.5 )

if map_x < big_w and map_y < big_h :
                dst_im.putpixel( (map_x, map_y), small_img.getpixel( (i, j) ) )

return dst_im



if __name__ == '__main__':
    big_img=Image.open(sys.argv[1])     # 大图
    small_img=Image.open(sys.argv[2])   # 小图

    dst_im = my_nearest_resize(big_img, small_img)
    dst_im.save(sys.argv[3])            # 嵌入小图像素的大图