在谈论空间索引之前，我们必须了解索引的概念。索引是为了提高数据集的检索效率。打个比喻，一本书的目录就是这本书的内容的“索引”，我们查看感兴趣的内容前，通过查看书的目录去快速查找对应的内容，而不是一字一句地找我们感兴趣的内容。所以，索引是一种“前人栽树，后人乘凉”的东西。
 
        空间索引不同于书本“目录”，“目录”对应的书本内容是不变的，而我们讨论的空间索引是根据空间数据的改变而变化的，包括数据的创建、修改、删除等基本操作都会重新建立新的索引。空间数据是含有位置、大小、形状以及自身分布特征等多方面信息的数据，因其数据复杂性，我们需要一种索引去提高检索空间数据集合中空间数据的效率，减少空间数据操作时间。我们把检索空间数据集合的“目录”称作空间索引。
 
        基础的内容这里不多说，直接介绍常见的空间索引
 
综合各种文献资料，把常用空间索引的方法大致分为以下几类：
 
 
 
 
 
 
在介绍空间索引方法前，我们先介绍一种经典的索引法——B树索引，并介绍基于B树的索引方法。
 
 
 
基于B树的索引方法
 
B树索引
 
B树，即二叉搜索树，结构特点：
     1. 所有非叶子节点至多拥有两个子节点（Left和Right）；
     2. 所有的节点存储一个关键字；
 
    3. 非页子节点的左指针指向小于其关键字的子树，右节点指向大于其关键字的子树；
 
 
 
 
实际的使用B树都是在B树的基础上加上平衡算法，是一种平衡多路查找树，其原理是把数据划分为树状层次索引，每个节点占一个存储块。该树所有的特点是：
     1. 定义任意非叶子子节点最多只有M个子节点，且M>2；
     2. 根节点的子节点数为[2,M]；
     3. 除根节点意外的非叶子节点的子节点数为[M/2，M]；
     4. 每个节点存放至少M/2-1(取上整)和至多M-1个关键字；（至少两个关键字）
     5. 非叶子节点的关键字个数=指向子节点的指针个数-1；
     6. 非叶子节点的关键字：k[1],k[2]…k[M-1],且k[i]<k[i+1];
     7. 非叶子节点的指针：p[1]，p[2]....p[M]；其中p[1]指向关键字k[1]的子树，p[M]指向关键字大于K[M-1]的子树，其他p[i]指向关键字属于（K[i-1],K[i]）的子树；
 
    8. 所有叶子节点位于同一层；
 
 
 
R树、R+树、R*树索引
 R树是空间数据索引结构中重要的一种层次结构，目前已成为许多空间索引方法的基础，不少前沿的空间索引都使用到R树或者对R树改良。其构建思想是以最小边界矩形（MBR）递归地对空间数据集的空间按照“面积”规划进行划分。它的特点如下：
     1. R树中非叶子节点代表一个划分的空间区域，即一个矩形空间区域；
     2. R树中的叶子节点包含的矩形区域对应空间对象的MBR；
     R+树主要针对R树中兄弟节点的MBR重叠后，导致空间搜索性能较差的特点提出的。R+树中，兄弟节点之间的MBR不允许重叠，这使得空间搜索的性能较好，但由于在插入和删除时需保证兄弟节点之间的MBR不能重叠，因此R+树的插入和删除操作的效率较低。
     R+树中间节点的所有矩形都是不相交的。如果一个对象的MBR被两个或多个R+树高层节点中的矩形分割，与这些非叶节点中矩形相联系的每个项都有指向这个对象的一个后继叶节点。这样树的高度增加，但搜索操作的性能会大大提高。
 
    R*树相对R树优化的地方是强制重新插入算法，R树中，插入操作导致节点溢出时，采用分裂的方法进行处理，R*树思路是：当新的空间对象索引项的插入导致节点溢出时，选择部分节点在同层节点间进行调整，以推迟节点分裂，从而达到优化R树整体结构的目的。基于R*树的空间索引算法提高了空间利用率，减少了节点分裂次数，但同时增加了CPU的计算代价。
 
 
基于网格的空间索引
 
        网格索引的基本思想是将研究区域按一定规则用横竖线分为小的网格，记录每个网格所包含的地理对象。当用户进行空间查询时，首先计算查询对象所在的网格，然后通过该网格快速查询所选的地理对象。网格索引算法大致分为三类：基于固定网格划分的空间索引算法、基于多层次网格的空间索引算法和自适应层次网格空间索引算法。
基于固定网格的空间索引
 
    将一幅地图分割成a*b的固定网格，再根据一定的方法将网格编码，为落入每个格网内的地图目标建立索引，这样只需检索原来区域的1/a*b，以达到快速检索的目的。该算法的优点是操作简单，在涉及的数据量不大、不需要进行复杂操作时具有一定的适应性。例如对点对象的检索特点适合使用。
 
 
        常用的网格编码方法有行排序、Z排序和Hilbert值排序，其中Hilbert值排序最能反应空间邻近性。因此，基于Hibert曲线分形的算法被广泛应用到空间索引中。
 
 
基于多层次网格的空间索引
 
    将一幅地图分割成若干大小相同的小块，将落入该小块内的地图目标存入该小块、块对应的存储区域中，根据需要可以将小块划分成更小的块，建立多级索引。该算法的优点是检索的效率比较高，相比于纯粹的网格索引减少了特定的比较次数。但是网格划分的精细程度无法保证最优。对处于网格边缘的对象没有一个很好的解决办法，没有考虑到地图目标的水平与垂直分布对网格划分的影响。
 
自适应层次网格空间索引算法
 
    其网格大小由各具体的地图目标的外接矩形决定，避免了网格索引中网格划分的人为因素。算法的优点是网格划分稳定自动，以各地图目标的外接矩形的大小作为划分依据，避免了重复存储，在存储效率上有一定改善。不足就是算法实现复杂，建立索引前，必须知道各地图目标外界矩形的长、宽，按其面积大小排序；建立索引后，进行插入或删除操作时，涉及的地图目标的外接矩形面积若不是原有面积大小，则需要重新进行排序，效率反而会下降。
 
 
 
 
 
基于二叉树的空间索引
 
四叉树空间索引
 
        四叉树索引可能是最早的专门为存取空间数据而设计的数据结构，不仅可用于二维变量，也可以用于任意维数。它是二叉树用于二维数据的一种推广。
 四叉树索引，类似于网格索引，也是对地理空间进行网格划分，对地理空间递归进行四分来构建四叉树，直到自行设定的终止条件（比如每个节点关联图元的个数不超过3 个，超过 3 个，就再四分），最终形成一颗有层次的四叉树。它的特点如下
     1. 每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围；
     2. 非叶子节点仅存储本区域地理范围。
 
由于四叉树的生成和维护比较简单，且当空间数据对象分布比较均匀时，基于四叉树的空间索引可以获得比较高的空间数据插入和查询效率。如下两图：
 
 
 
 
KD树——K近邻算法的实现
 
        K邻近算法在这里就不提及了，KD树（K维搜索树）是把二叉树推广到多维数据的一种主存数据结构，它是一个K维空间中的平衡二叉树，主要用于存储点数据。在每一个内部节点中，它用一个k-1维的超平面（如二维空间的线）将节点所表示的k维空间分成两个部分，这些超平面在k个可能的方向上交替出现，而且在每一个超平面中至少包括一个点数据。在KD树中查找一个所有维都给定值得对象的处理如同在二叉树中一样，只需在每个内部节点上决定沿哪个走向，直至搜索到叶节点为止。
 
        假设有6个二维数据点{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，数据点位于二维空间内，如下图八所示。为了能有效的找到最近邻，kd树采用分而治之的思想，即将整个空间划分为几个小部分。首先，粗黑线将空间一分为二，然后在两个子空间中，细黑直线又将整个空间划分为四部分，最后虚黑直线将这四部分进一步划分。
 
 
6个二维数据点{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}构建kd树的具体步骤为：
     1. 确定：split域=x。具体是：6个数据点在x，y维度上的数据方差分别为39，28.63，所以在x轴上方差更大，故split域值为x；
     2. 确定：Node-data = （7,2）。具体是：根据x维上的值将数据排序，6个数据的中值(所谓中值，即中间大小的值)为7，所以Node-data域位数据点（7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于：split=x轴的直线x=7；
     3. 确定：左子空间和右子空间。具体是：分割超平面x=7将整个空间分为两部分：x<=7的部分为左子空间，包含3个节点={(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点={(9,6)，(8,1)}；
 
        如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。如此便成了下面这样一棵k-d树：
 
 
    关于KD的内容很多，我就简单阐述到这里。
 
 
 
KDB树
 
    KDB树兼有KD树和B树的特性，以B树的方式进行插入和删除，是完全平衡的，且可以进行局部重组，她的主要缺陷是不能保证最小空间利用率。KDB树是B树享多味空间发展的一种形式。它对于多维空间中的点进行索引，具有较好的动态特性，删除和增加地理要素可以很方便地实现。其缺点是不直接支持占据一定空间范围的地理要素，如2维空间中的线和面。
 
BSP树
 
    BSP表示二叉空间分割，BSP树能很好地与空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。
     它的基本思想是基于这样一个事实，任何平面都可以将空间分割成两个半空间。所有位于这个平面的一侧的点定义了一个半空间，位于另一侧的点定义了另一个半空间。此外，如果我们在任何半空间中有一个平面，它会进一步将此半空间分割为更小的两个子空间。我们可以使用多边形列表将这一过程一直进行下去，将子空间分割得越来越小，直到构造成一个二叉树。在这个树中，一个进行分割的多边形被存储在树的节点，所有位于子空间中的多边形都在相应的子树上。当然，这一规则使用于树中每一个节点。
 
    假设某多边形的平面投影如图十，在它上面，所有多边形都能映射为直线段
 
 
    多边形B所在的平面将空间分割为两个部分，使得多边形D和E位于同一个半空间中，多边形C在另一个半空间中。在这个例子中， 多边形A穿越了两个半空间。接下步骤一和二：
 
 
        现在已经将问题分成了两个子问题。我们可以在子树中再次使用上述算法，在左边子树中选择E作为分割多边形，在右边子树中选择A2作为分割多边形。这样，我们将建立图十的BSP树，如图十一步骤2。
 
        必须注意，任何给定的BSP树都不是唯一的。我们可以对同样的多边形找到多个有效的二叉分割方法。根据我们的选择来进行分割的多边形的顺序，可以得到不同的树。
 
 
 
空间索引方法的比较
 
 
 
 
新型空间索引
 
 
 
    目前，成熟的空间索引包括R树索引、网格索引、四叉树索引等等，在实际运用中具有新算法的空间索引很少，基本都是结合上述的空间索引中的一种或两种以上，融合它们的特点变成新的空间索引。
 
PostGis的通用搜索树
 
 
 
    数据库对多维数据的存取有两种索引方案，R-Tree和GiST（Generalized Search Tree）简称“通用搜索树”，在PostgreSQL中的GiST比R-Tree的健壮性更好，因此PostGIS对空间数据的索引一般采用GiST实现。
 
通用搜索树是一棵平衡树，其特点如下：
 
 
 
    1.  除根节点的扇出数在2和M之间外，每个节点的扇出数在kM和M之间，这里2/M<=k<=1/2。常量k称作该树的最小填充因子，M为一个节点可以容纳索引项的最大数目。
 
    2.  索引项形式为（p，ptr），其中p是用作搜索码的谓词（谓词中可以包含自由变量，只要相应子树中叶节点标识的所有元组能实例化这些变量即可）。在叶节点中，ptr为指向数据库中某一元组的指针；而在非叶结点中，ptr为指向其子树根结点的指针。
 
    它是一种可扩展的树型索引结构框架。这里的“可扩展”包含 层意思：一是支持数据类型的可扩展性；二是支持查询谓词的可扩展性。
 
 
 
QR树——基于R树与四叉树的空间索引
 
    从R-树的特征出发，为了提高查找性能，减少索引空间重叠，避免或减少查找分支，而引入索引空间的“四叉树”层次划分方法，将整个索引空间划分为多级子索引空间，然后对每级的子索引空间均采用R-树进行索引。其实质是将一棵“大”的R-树分解成多课“小”的R-树（即一群R-树的集合）将查询尽可能限定在局部空间区域，从而提高查找性能。
 
实验证明，与R树相比，QR树以略大的空间开销为代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。
 
 
 
HR树——基于Hilbert分形曲线的空间索引
 
    上文阐述网格索引时，提及到网格编码方式中有一种叫Hilbert值编码方式。空间数据沿着Hilbert曲线的特性编码成为Hilbert码。
 
    基于Hilbert码的R树建立思想是：先将待索引的空间对象按照最小外包矩形MBR的中心的Hilebert码值进行排序分组，然后按照自底而上的模式生成R树。这种算法可以获得几乎100%的空间利用率，而且查询性能优于会产生节点分裂的R树系列。
 
 

Py之cv2：cv2库(OpenCV，opencv-python)的简介、安装、使用方法(常见函数、方法等)最强详细攻略
 
 
 
目录
 
关于OpenCV简介
 
OpenCV应用领域
 
1、计算机视觉领域方向
 
2、计算机操作底层技术
 
安装OpenCV的的两种方法
 
T1、使用whl文件法
 
T2、直接命令法  
 
T3、Anaconda 环境下安装
 
OpenCV常见函数、方法
 
0、基本库函数
 
1、图像基本运算
 
2、Image.open 和cv2.imread 的区别及其转换
 

 
 
相关文章：
Py之cv2：cv2库(OpenCV)的简介、安装、使用方法(常见函数、方法等)最强详细攻略
CV：计算机视觉技术之图像基础知识(一)—以python的cv2库来了解计算机视觉图像基础(傅里叶变换-频域-时域/各种滤波器-线性-非线性-均值-中值-高斯-双边)
CV：计算机视觉图像的基础知识—以python的cv2库来了解计算机视觉图像基础(边缘检测算子+平滑+轮廓标注+形态学+金字塔+傅里叶变换)—代码实现
CV：计算机视觉技术之图像基础知识(一)—以python的cv2库来了解计算机视觉图像基础—代码实现(图像显示+加文本+变换+通道)—图像基础各种操作(函数及案例)
CV：计算机视觉技术之图像基础知识(二)—以python的skimage和numpy库来了解计算机视觉图像基础(图像存储原理-模糊核-锐化核-边缘检测核，进阶卷积神经网络(CNN)的必备基础)
CV：利用python的cv2库实现图像数据增强—随机裁剪、随机旋转、随机hsv变换、随机gamma变换代码实现
 
 
 
 
 
关于OpenCV简介
 
       OpenCV是一个基于BSD许可（开源）发行的跨平台计算机视觉库，可以运行在Linux、Windows、Android和Mac OS操作系统上。它轻量级而且高效——由一系列 C 函数和少量 C++ 类构成，同时提供了Python、Ruby、MATLAB等语言的接口，实现了图像处理和计算机视觉方面的很多通用算法。 OpenCV用C++语言编写，它的主要接口也是C++语言，但是依然保留了大量的C语言接口。 
 
       在计算机视觉项目的开发中，OpenCV作为较大众的开源库，拥有了丰富的常用图像处理函数库，采用C/C++语言编写，可以运行在Linux/Windows/Mac等操作系统上，能够快速的实现一些图像处理和识别的任务。此外，OpenCV还提供了Java、python、cuda等的使用接口、机器学习的基础算法调用，从而使得图像处理和图像分析变得更加易于上手，让开发人员更多的精力花在算法的设计上。
 
 
 
OpenCV应用领域
 
1、计算机视觉领域方向
 
1、人机互动
2、物体识别
3、图像分割
4、人脸识别
5、动作识别
6、运动跟踪
7、机器人
8、运动分析
9、机器视觉
10、结构分析
11、汽车安全驾驶
2、计算机操作底层技术
 
图像数据的操作： 分配、释放、复制、设置和转换。 图像是视频的输入输出I/O ，文件与摄像头的输入、图像和视频文件输出）。
 矩阵和向量的操作以及线性代数的算法程序：矩阵积、解方程、特征值以及奇异值等。
各种动态数据结构：列表、队列、集合、树、图等。 
基本的数字图像处理：滤波、边缘检测、角点检测、采样与差值、色彩转换、形态操作、直方图、图像金字塔等。 
结构分析：连接部件、轮廓处理、距离变换、各自距计算、模板匹配、Hough变换、多边形逼近、直线拟合、椭圆拟合、Delaunay 三角划分等。 
摄像头定标：发现与跟踪定标模式、定标、基本矩阵估计、齐次矩阵估计、立体对应。
运动分析：光流、运动分割、跟踪。 
目标识别：特征法、隐马尔可夫模型：HMM。
基本的GUI：图像与视频显示、键盘和鼠标事件处理、滚动条。 
图像标注：线、二次曲线、多边形、画文字。
 
 
安装OpenCV的的两种方法
 
1、几点注意事项：
 
安装的时候是 opencv_python，但在导入的时候采用 import cv2。
因为OpenCV依赖一些库，可以在本博客中查找一些依赖库的安装方法，例如安装Numpy方法等，本博客应有尽有！
T1、使用whl文件法
 
先去官网https://www.lfd.uci.edu/~gohlke/pythonlibs/#opencv，下载相应Python版本的OpenCV的whl文件，如本人下载的opencv_python‑3.4.1‑cp36‑cp36m‑win_amd64.whl，然后在whl文件所在目录下，命令 进行安装即可
 
pip install opencv_python‑3.4.1‑cp36‑cp36m‑win_amd64.whl
 
 
 
T2、直接命令法  
 
pip install opencv-python  
 
 
 
 
最后，检测安装情况
 
 
哈哈，大功告成！
 
 
 
T3、Anaconda 环境下安装
 
pip install opencv-python      //Anaconda 环境下安装，先打开Anaconda Prompt，再输入本命令进行安装！
 
 
 
 
 
20191128更新记录
 
 
 
 
 
 
 
 
OpenCV常见函数、方法
 
Welcome to OpenCV-Python Tutorials’s documentation!
CV：计算机视觉图像的基础知识—以python的cv2库来了解计算机视觉图像基础
 
 
 
0、基本库函数
 
cv2.imread(filepath,flags)     #读入一张图像
 
filepath：要读入图片的完整路径
flags：读入图片的标志  
  
cv2.IMREAD_COLOR：默认参数，读入一副彩色图片，忽略alpha通道
cv2.IMREAD_GRAYSCALE：读入灰度图片
cv2.IMREAD_UNCHANGED：顾名思义，读入完整图片，包括alpha通道
cv2.imshow(wname,img)     #显示图像
 
第一个参数是显示图像的窗口的名字
第二个参数是要显示的图像（imread读入的图像），窗口大小自动调整为图片大小
cv2.imshow('image',img)
cv2.waitKey(0)   #等待键盘输入，单位为毫秒，即等待指定的毫秒数看是否有键盘输入，若在等待时间内按下任意键则返回按键的ASCII码，程序继续运行。
#若没有按下任何键，超时后返回-1。参数为0表示无限等待。不调用waitKey的话，窗口会一闪而逝，看不到显示的图片。
cv2.destroyAllWindow()     #销毁所有窗口
cv2.destroyWindow(wname)   #销毁指定窗口
 
cv2.imwrite(file，img，num)    #保存一张图像
 
第一个参数是要保存的文件名
第二个参数是要保存的图像。可选的第三个参数，它针对特定的格式：对于JPEG，其表示的是图像的质量，用0 - 100的整数表示，默认95。
第三个参数表示的是压缩级别。默认为3.
img.copy()    #图像复制
 
 
 
cv2.cvtColor()      #图像颜色空间转换
 
img2 = cv2.cvtColor(img,cv2.COLOR_RGB2GRAY)   #灰度化：彩色图像转为灰度图像
img3 = cv2.cvtColor(img,cv2.COLOR_GRAY2RGB)   #彩色化：灰度图像转为彩色图像
# cv2.COLOR_X2Y，其中X,Y = RGB, BGR, GRAY, HSV, YCrCb, XYZ, Lab, Luv, HLS
cv2.resize(image, image2,dsize)     #图像缩放：(输入原始图像，输出新图像，图像的大小)
cv2.flip(img,flipcode)                       #图像翻转，flipcode控制翻转效果。
 
flipcode = 0：沿x轴翻转；flipcode > 0：沿y轴翻转；flipcode < 0：x,y轴同时翻转
cv2.warpAffine(img, M, (400, 600))       #图像仿射变换 ：平移；裁剪、剪切、旋转、仿射变换，
 M、M_crop、M_shear、M_rotate
 
cv2.putText(img,'text',(50,150)   #图像添加文字：(照片，添加的文字，左上角坐标，字体，字体大小，颜色，字体粗细)
 
cv2.putText(image, caption, (b[0], b[1] - 10), cv2.FONT_HERSHEY_PLAIN, 1, (255, 0, 0), 1)
cv2.putText(I,'there 0 error(s):',(50,150),cv2.FONT_HERSHEY_COMPLEX,6,(0,0,255),25)
 
cv2.rectangle(img, (x,y), (x+w,y+h), (0,255,0), 2)    #画出矩行：img原图、(x，y)是矩阵的左上点坐标、(x+w，y+h)是矩阵的右下点坐标、(0,255,0)是画线对应的rgb颜色、2是所画的线的宽度。
 
 
 
cv2.boundingRect(img)          #返回图像的四值属性：img是一个二值图，即是它的参数； 返回四个值，分别是x，y，w，h； x，y是矩阵左上点的坐标，w，h是矩阵的宽和高。
 
 
 
 
1、图像基本运算
 
     图像的基本运算有很多种，比如两幅图像可以相加、相减、相乘、相除、位运算、平方根、对数、绝对值等；图像也可以放大、缩小、旋转，还可以截取其中的一部分作为ROI（感兴趣区域）进行操作，各个颜色通道还可以分别提取及对各个颜色通道进行各种运算操作。
 bitwise_and、bitwise_or、bitwise_xor、bitwise_not四个按位操作函数，是将基础数学运算应用于图像像素的处理中。
 
bitwise_and、bitwise_or、bitwise_xor、bitwise_not这四个按位操作函数。
void bitwise_and(InputArray src1, InputArray src2,OutputArray dst, InputArray mask=noArray());//dst = src1 & src2
void bitwise_or(InputArray src1, InputArray src2,OutputArray dst, InputArray mask=noArray());//dst = src1 | src2
void bitwise_xor(InputArray src1, InputArray src2,OutputArray dst, InputArray mask=noArray());//dst = src1 ^ src2
void bitwise_not(InputArray src, OutputArray dst,InputArray mask=noArray());//dst = ~src
 
bitwise_and()：是对二进制数据进行“与”操作，即对图像（灰度图像或彩色图像均可）每个像素值进行二进制“与”操作，1&1=1，1&0=0，0&1=0，0&0=0
bitwise_or()：是对二进制数据进行“或”操作，即对图像（灰度图像或彩色图像均可）每个像素值进行二进制“或”操作，1|1=1，1|0=0，0|1=0，0|0=0
bitwise_xor()：是对二进制数据进行“异或”操作，即对图像（灰度图像或彩色图像均可）每个像素值进行二进制“异或”操作，1^1=0,1^0=1,0^1=1,0^0=0
bitwise_not()：是对二进制数据进行“非”操作，即对图像（灰度图像或彩色图像均可）每个像素值进行二进制“非”操作，~1=0，~0=1
2、Image.open 和cv2.imread 的区别及其转换
 
Image.open 打开来的图像格式，cv2.imread  读出来是像素格式。
 
# 1、PIL.Image转换成OpenCV格式：
import cv2
from PIL import Image
import numpy
 
path = 'F:/File_Python/Resources/face_images/LZT01.jpg'
img = Image.open(path).convert("RGB")#.convert("RGB")可不要，默认打开就是RGB
img.show()
#转opencv
#img = cv2.cvtColor(numpy.asarray(image),cv2.COLOR_RGB2BGR)
img = cv2.cvtColor(np.array(img),cv2.COLOR_RGB2BGR)
cv2.imshow("OpenCV",img)
cv2.waitKey()
 
# 2、OpenCV转换成PIL.Image格式
import cv2
from PIL import Image
import numpy
 
img = cv2.imread('F:/File_Python/Resources/face_images/LZT01.jpg') # opencv打开的是BRG
cv2.imshow("OpenCV",img)
image = Image.fromarray(cv2.cvtColor(img,cv2.COLOR_BGR2RGB))
image.show()
cv2.waitKey()
 

  
  
 
 
 
 
 
 
 
相关应用：CV：利用python的cv2库实现图像数据增强—随机裁剪、随机旋转、随机hsv变换、随机gamma变换代码实现
 
 
 
 
 
 
 
参考文章
OpenCV之bitwise_and、bitwise_not等图像基本运算及掩膜
模块cv2的用法
  

前言
 
 
 
不知道大家注意到之前有一个寻找相邻个体的方法叫做getNeighbors没有，该方法的实现如下： 
 - 遍历所有个体，计算距离是否小于一定范围，确定邻居
 
 
我们可以预知，该方法在个体总数较小的时候效率较高，一旦个体数突破上百个，就很容易造成极大的cpu开销，所以此处我们需要研究出另外的索引方案来得到邻居。
 
 
空间划分的方案主流的有很多，例如四叉树，八叉树，bsp树，四叉树主要用于数据库的底层方案，它会将二维的点转化为一条有规律的曲线；八叉树是四叉树的3d版；bsp树是三维的空间二分；这几种主流算法对于我这款游戏都不合适，此处我们介绍两个不是很常见的算法，cell space和geo hash。
 
 
Cell_Space_Partition(单元空间划分)
 
 
 
我们想象如下的场景： 
 Y君上了出租车 
 Y：“师傅，到XX小区。” 
 出租车司机：“XX小区在哪儿啊？” 
 Y：”就在电视塔附近。“
 
 
很常见的情况，我们注意到，当我们不知道地理位置的时候，我们会查找“标志性建筑”，Cell_Space_Partition（以下简称CSP）就是引用了这样一种思路：通过hash（索引）来减少遍历的难度或者广度。（笔者最近在思考有没有可能性直接用一种关联启发算法，来实现这种多对多的划分逻辑）
 
这种空间划分是将二维空间划分为小方格子，然后每个小方格存放个体指针的集合，我们在查询个体邻居的时候就只需要遍历小方格里的个体集合。
 
#pragma once

#include"BaseEntity.h"
#include<algorithm>
#include"cocos2d.h"
using namespace cocos2d;

struct Cell
{
    std::list<BaseEntity*> members_;
    Rect box_;
    Cell(Rect new_box) :box_(new_box){}
};

class CellSpacePartition
{
private:
    //all cells
    std::vector<Cell> _cells;

    //world space 
    Rect _spaceRect;

    //cell nums
    int _cellNumX;
    int _cellNumY;

    //cell space
    double _cellSizeX;
    double _cellSizeY;

protected:
    int positionToIndex(const Vec2)const;

public:
    CellSpacePartition(Rect, int,int);
    void addEntity(BaseEntity*);
    void updateEntity(BaseEntity*, Vec2);
    std::vector<BaseEntity*> getNeighbors(Vec2, double);
    void clear();
};

CellSpacePartition::CellSpacePartition(Rect spaceSize, int cellNumX, int cellNumY) :
_spaceRect(spaceSize),
_cellNumX(cellNumX),
_cellNumY(cellNumY)
{
    double _cellSizeX = _spaceRect.size.width;
    double _cellSizeY = _spaceRect.size.height;

    for (int y = 0; y<_cellNumY; y++)
    {
        for (int x = 0; x<_cellNumX; x++)
        {
            double left = x * _cellSizeX;
            double bot = y * _cellSizeY;
            _cells.push_back(Cell(Rect(left, bot, _cellSizeX, _cellSizeY)));
        }
    }
}

void CellSpacePartition::addEntity(BaseEntity* entity)
{
    assert(entity&&
        "NULL entity");
    this->_cells.at(positionToIndex(entity->position())).members_.push_back(entity);
}

int CellSpacePartition::positionToIndex(const Vec2 position)const
{
    assert((position.x<_spaceRect.getMaxX()) && (position.y < _spaceRect.getMaxY()) &&
        "outside the world");

    int index = (int)(position.x / _cellSizeX) + (int)(position.y / _cellSizeY)*_cellNumX;
    return index;
}

void CellSpacePartition::updateEntity(BaseEntity* entity, Vec2 old_position)
{
    assert(entity&&
        "NULL entity");

    int old_idx = positionToIndex(old_position);

    int cur_idx = positionToIndex(entity->position());

    if (old_idx == cur_idx)
        return;
    else
    {
        this->_cells.at(old_idx).members_.remove(entity);
        this->_cells.at(cur_idx).members_.push_back(entity);
    }
}

std::vector<BaseEntity*> CellSpacePartition::getNeighbors(Vec2 position,double radius)
{
    Vec2 temp = Vec2(position - Vec2(radius, radius));
    Rect queryRect = Rect(temp.x, temp.y, 2 * radius, 2 * radius);

    std::vector<BaseEntity*> neighbors;

    for (int i = 0; i < _cellNumX*_cellNumY; i++)
    {
        if (queryRect.intersectsRect(_cells.at(i).box_)&&!(_cells.at(i).members_.empty()))
        {
            std::for_each(_cells.at(i).members_.cbegin(), _cells.at(i).members_.cend(), [&neighbors,position,radius](BaseEntity* neighbor){
                Vec2 toNeighbor = neighbor->position() - position;
                if (toNeighbor.getLengthSq() < (radius*radius))
                {
                    neighbors.push_back(neighbor);
                }
            });//end for each
        }
    }//end for

    return neighbors;
}
 
大家可以看到，很简单的代码，此处我们将空间划分的方格数目固定，当然也可以用固定大小的方格。 
 在面对运动的个体时，我们需要在物体产生位移的同时更新它的所属方块。
 
GeoHash_Space_Partition（字符索引）
 
如果你开发过基于LBS+的地图程序，你应该对这个算法很熟悉了，但是应用在游戏上还是大姑娘上轿——头一回！真令人兴奋，我们每当做出一小步创新，人类的科技就会有一个大的进步。
 
这里有一篇文章写得很好，推荐一下。view here
 
我在此就不班门弄斧介绍这种算法了，我讲一下我的实现。 
 难点有几个： 
 - c++内部对2进制变量的处理比较糟糕 
 - 我们需要写一个base32编码的方法，而且要尽量高效，一旦该方法不高效，那反而会比空间划分以前更慢 
 - 我们需要写一个数据库查询的like算法，其实也就是基本模糊查询，笔者的数据库知识非常尴尬 ：），这一块在找做数据库的朋友帮忙讲解一下
 
基本步骤： 
 - 1·为地址结构添加string类型储存hash值 
 - 2·传入一个地理信息point（x,y），对其x和y值做如下操作 
 - 3·将其不断二分，此处我们使用递归方案，属于左区间值为0或者1，右区间与之相反 
 - 4·小于设定精度后，结束二分（此处的精度需要根据你的hash字符串长度和整个地图大小来计算） 
 - 5·我们将x，y值复合，偶数位为x或者y，奇数位为另一个 
 - 6·我们这时得到一串二进制码，对其进行base32编码 
 - 7·得到GeoHash值
 
 
 
关于base32编码，就是把二进制数转换为32进制数，5位代表一个32进制数，此处的编码表为约定版本，详情见代码 
 关于like方法，由于对效率至关重要，所以笔者不敢妄下定论，大家有好的方案可以m我
 
 

class GeoHash
{
public:
    static char base32_encode[32];

#define precision 10

#define world_size Vec2(1000,1000)//wathc out!if x!=y,there will be problems in combining binary code 

protected://dividision
    void halfDivision(double, double, double,string&);//half division,declare the left part as '0' there
    bool between(double value,double min,double max)
    {
        return value > min&&value < max;
    }
protected://convert to base32 code
    string base32Encoding(string);

public:
    static string getIndex(Vec2);//get GeoHash code
    static bool like(string,string);
    std::vector<BaseEntity*> getNeighbors(Vec2, std::vector<BaseEntity*>);
};

char GeoHash::base32_encode[] = {
    '0', '1', '2', '3', '4', '5', '6', '7',
    '8', '9', 'b', 'c', 'd', 'e', 'f', 'g',
    'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r',
    's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
};

string GeoHash::base32Encoding(string bitStr)
{
    string outPutStr;
    int count = 0;
    while (bitStr.length>count * 5)
    {
        string eachStr;
        for (int i = 0; i < 5; i++)
        {
            eachStr.push_back(bitStr.at(count + i));
        }
        int refer = 0;
        for (int j = 0; j < 5; j++)
        {
            refer = refer * 2 + (eachStr[j] - '0');
        }
        outPutStr.push_back(base32_encode[refer]);
    }

    if (bitStr.length > count * 5)//push '0' to fill the rest
    {
        int addTo5 = (count + 1) * 5 - bitStr.length;
        string eachStr;
        for (int i = 0; i < addTo5; i++)
        {
            eachStr.push_back('0');
        }
        int refer = 0;
        for (int j = 0; j < 5; j++)
        {
            refer = refer * 2 + (bitStr[j] - '0');
        }
        outPutStr.push_back(base32_encode[refer]);
    }
    return outPutStr;
}

string GeoHash::getIndex(Vec2 po)
{
    string bitX;
    halfDivision(world_size.x, world_size.y, po.x, bitX);

    string bitY;
    halfDivision(world_size.x, world_size.y, po.y, bitY);

    //将xy轴组合，偶数位放y，奇数位放x
    string totalBit;
    for (int i = 0; i < bitX.size(); i++)
    {
        totalBit.push_back(bitY.at(i));
        totalBit.push_back(bitX.at(i));
    }

    return base32Encoding(totalBit);
}

void GeoHash::halfDivision(double min, double max, double value,string& bit)
{
    if (max - min < precision)
    {
        return;
    }
    if (between(value, min, (min + max) / 2))
    {
        bit += "0";
        halfDivision(value, min, (min + max) / 2, bit);
    }
    else
    {
        bit += "1";
        halfDivision(value, (min + max) / 2, max, bit);
    }
}

bool GeoHash::like(string index1,string index2)
{
    if (index1&index2 > "111000")
    {
        //具体代码读者自行实现，:)
    }
}

std::vector<BaseEntity*> GeoHash::getNeighbors(Vec2 centre, vector<BaseEntity*> preSelectedEntities)
{
    vector<BaseEntity*> temp;
    for_each(preSelectedEntities.cbegin(), preSelectedEntities.cend(), [](){

    });
}
 
该算法笔者还没有进行全面测试，估计在处理静态物体，超大空间的时候效率会远远高于CSP，毕竟后者在储存空间格子申请的内存就会让处理器爆炸。
 
这两种算法有一个好处，将额外的计算开销（CSP空间格子的指针操作，GeoHash额外的索引计算）平均分配，位置改变是一直进行的，所以cpu的开销就变成异步的了。总体来看，总的计算量增加了，然而却被分配到了实体们每次发生位移时候，计算效率当然大大提高。
 
 
准备写一个有关游戏底层算法，物理算法，以及AI（重点是机器学习在游戏中的应用）的长篇博客，欢迎大家指正交流╰(￣▽￣)╯

1.        空间数据对空间聚类算法的要求
1)       空间拓扑关系
2)       密度问题
3)       空间簇形态多样性
2.        空间聚类算法分析
1)       基于划分的算法
          i.             K-means算法
优点：处理大型数据有较高效率和伸缩性
缺点：
a)        初始点敏感
b)       只能发现近似球状簇
c)        对噪点敏感
d)       只能处理数值型数据
        ii.             K-mediods算法：克服K-means算法对噪点的敏感性
PAM是K-mediods算法之一
CLARA基于K-mediods
CLARANS基于K-mediods
      iii.             K-modes算法：克服K-means不能对分类数据进行聚类的局限性
      iv.             ISODATA算法：K-means的重要扩展，获得高质量聚类
        v.             FCM（fuzzy-c-means）：模糊C均值聚类算法
2)       基于层次的算法
          i.             经典的层次聚类算法
优点：执行简单
缺点：
a)        聚类操作不可恢复，受噪点影响
b)       聚类终止条件难以确定
c)        聚类开销大
        ii.             BIRCH（balanced iterative reducing and clustering using hierarchies）算法：改进的算法
优点：适应大型数据库
缺点：
a)        主要识别球型空间簇
b)       需要先验知识
c)        受数据输入次序影响
      iii.             CURE（clustering using representative）算法
优点：
a)        发现复杂空间簇
b)       受早点影响小
缺点：
a)        实际复杂
b)       抽样有误差
c)        难以发现形状非常复杂的空间簇，对空间数据密度差异敏感
      iv.             CHAMLELON算法
优点：发现任意形状簇和密度不同的簇
缺点：
a)        依赖子图划分
b)       参数选择缺乏普遍性
c)        密度有渐变时误差大
        v.             AMOEBA算法：借助Delaunay三角网描述空间实体间的邻近关系
优点：发现不同密度、大小、形状的空间簇
缺点：链式问题、颈问题
      vi.             尺度空间算法
    vii.             MSCMO算法
3)       基于密度的算法
          i.             DBSCAN（density-based spatial clustering of application with noise）算法
优点：发现任意形状的空间簇、识别孤立点
缺点：
a)        全局参数难以设定
b)       难以识别空间簇相互邻接（颈问题）情况下的空间聚类操作
GDBSCAN算法
DBRS算法
ST-DBSCAN算法
        ii.             OPTICS（ordering points to identify the clustering structure）算法：克服DBSCAN算法设置的全局参数难以适应空间数据分布不均匀情况下聚类操作的局限
缺点：空间簇相互邻接的情况仍旧难以解决
      iii.             DENCLUE（density based clustering）算法：基于核密度与核密度估计的空间聚类算法，基本思想是采用一个数学函数来表达一个空间实体对其淋雨内其他实体的影响，每个实体的密度定义为一定范围内实体影响函数之和。
优点：比DBSCAN聚类的质量高
缺点：同DBCSAN
      iv.             SNN算法:基于共享最临近密度的空间聚类算法，采用共享最邻近密度代替传统密度定义，再用DBSCAN
优点：更好地适应空间实体密度差异
缺点：聚类结果过分依赖参数设置，可能会分裂真正的簇
4)       基于图论的算法
          i.             MST算法：基于最小生成树的聚类算法
优点：可以进行复杂空间聚类操作
缺点：不稳健
        ii.             AAUTOCLUST算法：基于Delaunay三角网
优点：效率高，发现任意形状、不同密度的空间簇，解决多链问题
缺点：对空间簇内部密度变异过于敏感
      iii.             2-MSTClus算法：基于二轮最小生成树的聚类算法
优点：比MST稳健
缺点：
a)        对噪声敏感
b)       多个参数输入，需要先验知识
c)        没有考虑多个簇接触问题
5)       基于模型的算法
          i.             EM（expectation-maximization）算法
        ii.             SOM（self-organizing feature map）算法
6)       基于格网的算法
          i.             STING（statistical information grid）算法
        ii.             WaveCluster（cluster using wavelet transformation ）算法
7)       混合算法
          i.             NN-Density算法
        ii.             CSM（cohesion-based self merging）算法