前言 这是公众号【3D视觉工坊】出品的第一门课，视觉三维重建，基于colmap框架，保姆级教程，详细内容请见大纲，课程购买链接：彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进；  介绍 视觉三维重建 = 定位定姿 + 稠密重建 + surface reconstruction +纹理贴图。三维重建技术是计算机视觉的重要技术之一，基于视觉的三维重建技术通过深度数据获取、预处理、点云配准与融合、生成物体表面等过程，把真实场景刻画成符合计算机逻辑表达的数学模型。  然而，由于视觉三维重建对图像、光学、成像理论、以及重要数学公式的的推导要求较高，其次，三维重建也有其应用上的痛点、难点，比如成本预算、大场景、物体运动、纹理缺失、暗环境等，因而其涉及的算法也多种多样。鉴于视觉三维重建学习相关教材寥寥无几，网上资料也比较零散，国内外几乎没有系统讲解三维重建相关的课程。 为此，3D视觉工坊推出了国内首个《彻底搞透基于colmap的视觉三维重建：原理剖析、代码讲解、及优化改进》，本课程是国内首个深入剖析colmap原理、代码讲解、并对开源代码进行优化改进的课程，由资深三维重建算法工程师主讲及指导。 开课时间：6月5号20点开课，课程历时4个月，一年内有效。 课程购买链接：彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进  课程讲师 李城，资深三维重建算法工程师，担任过知名企业的图形图像算法工程师，高精度地图算法工程师。  课程大纲  适合人群 理工科相关专业，熟悉三维重建、线性代数、概率论等相关理论知识、有一定c++、python编程基础； 已经入门三维重建研究领域的本科、硕士及博士研究生； 希望通过此课程能够快速实现三维重建算法，并能在项目中应用的研究人员； 学后收获 掌握视觉三维重建整个流程，对colmap框架能够有较深的理解，其它开源视觉框架也能快速着手。 掌握colmap中的多视图几何算法、光束法平差算法以及内在的实现技巧，为后续思考colmap框架的优化方法铺垫了夯实的基础。 锻炼举一反三能力，将colmap中的优秀算法融合到实际问题中，如恢复尺度、雷达和相机的标定等。 学会借鉴其它开源框架的优点，如openmvg、opensfm 等，将其原理融合到colmap 中。 还能收获什么？ 优质的学习圈子 但凡购买本课程的学员，同时将会被赠予高额的《3D视觉从入门到精通》知识星球优惠券一张（100~180元优惠券）。星球汇集了国内外各个高校的研究生、博士生，包括但不限于清华大学、上海交通大学、华中科技大学、武汉大学、南京大学、北京理工大学、北京航空航天大学；以及国外留学的小伙伴，主要就读于南加州大学、墨尔本大学、慕尼黑工业大学、亚琛工业大学等。除此之外，还有很多一线工作的算法工程师、开发人员，包括但不限于百度、旷视、华为、奥比中光、云从、阿丘科技等。3D视觉从入门到精通知识星球是一个技术社区，在这里你可以讨论任何3D视觉相关的难题、前沿技术。星球邀请了国内外高校博士（北航、慕尼黑工业大学等）、CV独角兽公司CTO/CEO、以及各大厂的算法工程师解惑。在这里，你可以一对一和大佬交流，提出自己在工作学习上的疑问。 课程服务 主讲及助理全程答疑 可以在专属微信群或者知识星球内，每天晚上8~10点为集中答疑时间。 课程亮点 亮点一：算法原理结合代码详解，线下设置答疑群，可以面对面和讲师沟通难题，更能和国内外各大高校学员一起交流，创造一个优异的学习环境；  亮点二：作者不仅仅只停留在讲解原算法本身，会对算法处理数据存在的问题进行改进；  亮点三：举一反三，会与目前主流的应用(如自动驾驶、VR)进行结合；  vslam或lslam的 prior pose 加上colmap 进行重定位地图的建立 利用colmap 进行激光雷达和相机的标定 利用colmap 进行相机和GPS 的时间同步(或者说顾忌曝光延迟的gps约束) 恢复单目的绝对尺度，应用到实际场景中(也可隶属课程亮点2中） i、利用先验的gps 恢复绝对尺度 ii、利用GCP 或者Marker 来恢复绝对尺度 iii、利用已知的模型比例(scale)来恢复绝对尺度 亮点四：采用问答方式来解析重点部分的代码和算法原理 ———————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/116568555 

 计算机视觉入门的一些pdf书籍，【计算机视觉工坊】按照不同领域帮大家划分了下，涉及深度学习基础、目标检测、Opencv、SLAM、点云、多视图集合、三维重建等~  计算机视觉 1、 计算机视觉算法与应用（第二版）  2、 OpenCV3编程入门  3、 数字图像处理（冈萨雷斯，第三版）  深度学习 1、 深度学习（花书）  2、 深度学习、优化与识别  3、 吴恩达DeepLearning.ai中文版笔记  4、 《神经网络与深度学习》(邱锡鹏)  目标检测 1、 深度学习之PyTorch物体检测实战  SLAM 1、 视觉SLAM十四讲  2、 概率机器人（中文版）  3、 基于视觉的自主机器人导航  多视图几何 1、计算机视觉中的多视图几何  点云处理 1、 点云库PCL学习教程  机器视觉 1、 机器视觉算法与应用（第一版）  2、 机器视觉算法与应用（第二版）  编程语言 1、 C Primer Plus（第五版）  2、 C++Primer中文版  3、 C++ STL源码剖析  3、 Effective C++（中文版第三版）  4、 泛型编程与STL中文版 ———————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/112439461 

 前言 这一篇的内容主要要讲一点在深度学习的3D目标检测网络中，我们都采用了哪些数据预处理的方法，主要讲两个方面的知识，第一个是representation，第二个数据预处理内容是数据增广。 作为本篇博文的引言，我们先给一种博主制作的比较重要的3D检测方法图鉴，如下，就笔者的个人理解，今年的CVPR出现了很多的one-stage的方法，同时出现了很多融合的方法，这里的融合有信息融合，有representation融合，同时根据近两年的发展来看,voxel-based的方法占据了主导地位，这是得益于卷积结构优越性（point-based方法采用pointnet++结构，是MLP搭建的），但是今年的oral文章3D-SSD是一篇在point-based方法上很有建树的文章，所以在3D检测中了解主要的representation代表方法也是很重要的。  1.representation 做3D视觉的，尤其是基于点云做3D视觉任务的同学们都比较清楚的知道，点云因为其具有稀疏性和无规则性使得在二维上非常成熟的CNN结构不能直接的运用在点云中。我们先了解一下点云的这两个特性，如下图所示，下图中的(i)表示二维图像的排列方式，（ii），（ii），（iv）表示的是点云的数据，可以看出点云的排列稀疏性，对比（ii）和（iii）可以得知虽然点云数据的排列顺序假使是一样的，但是其对应的几何结构不同，而（iii）和（iv）则可以看出尽管几何结构表示同一个，但是排列顺序却是可以不一样的。  知道了上述的两个点云数据的两种特性，所以设计一种合适的点云表达形式是比寻找到一个高效的深度学习框架更加重要的内容，就3D检测方面而言，到CVPR20，至少有三种比较重要和值得探究的representation方式，分表示pointrepresentation，voxel representation和graph representation。 1.1 point representation 如题，就是采用最原始的点作为深度学习网络的输入，不采用任何的预处理工作，这类工作都是在pointnet++的基础上进行的。 这里首选插入一点采用point-based方法的基础backbone，如下所示，左图表示的是pointnet的特征提取结构，也就是point-based的基础模块，右图就是point-based方法的基础架构，由point-encoder层和point-decoder层组成，encoder层主要逐渐下采样采点特取语义信息，decoder过程是将encoder过程得到的特征信息传递给没有被采样到的点。使得全局的点都具有encoder的特征信息。最后再通过每个点作为anchor提出候选框。  最早的工作是CVPR18上的F-pointnet，该文章的作者也是pointnet/pointnet++的作者，具体做法如下可知，首先通过二维的检测框架得到二维目标检测结果，然后将二维检测结果通过视锥投影到三维，再采用三维破pointnet++延伸结构检测为三维目标框。算是三阶段的基于point输入的目标检测方法  随后的CVPR19的比较经典的Point_based方法是point-rcnn，该工作不仅仅采用point作为representation,同时和上诉的F-pointnet比较没有采用二维信息，仅仅采用点云作为网络输入。如下图所示，该工作是一个两阶段的检测方法，第一阶段根据语义分割信息对每一个点都提出一个候选框，随后再采用多特征融合进一步优化proposals。  除了CVPR会议，在IROS和ICRA机器人相关的会议上也有很多这方面的研究，其中有一篇在F-pointnet上做出更细致的优化的文章F-ConvNet也是很优秀的工作，有兴趣的同学可以去了解下；这里直接介绍今年CVPR20上的基于Pointrepresentation的文章 3D-SSD，如下图所示，平平无奇的一阶段encoder过程，也就是把pointnet++的decoder部分给去除掉（这样做的目的是减少网络前馈时间，在KITTI上达到35FPS），本文的最主要的贡献点在于将Pointnet++的采样方法由欧式空间度量改为特征空间度量和欧式空间度量相结合的方法，同样的也采用了anchor-free的设计方法，使得显存占用更少。  point representation方法小总结 就笔者个人对这方面的理解，该类方法的优点是作为最原始的点云数据，保留了最细致的几何结构信息，网络的输入信息损失几乎是所有representation方法中最小的。但是缺点也很明显，第一点，MLP的感知能力不如CNN，因此主流的effective的方法都是voxel-based的，第二点，pointnet++结构的采样是很耗时的，所以在实时性上也不及voxel-based的方法。所以今年的CVPR oral文章3D-SSD为了实时性，丢掉了FP层，同时设计了新的SA模块。  1.2 voxel representation 1.2.1 Voxelization 步骤 在3D目标检测中，对整个场景的point2voxel的过程可以简单描述为如下： 1.设置Voxelization参数（每个voxel可以存放点的个数(max_points_number)，voxel长宽高的大小(whl)） 2.对依次每一个点，根据其对应的坐标（x,y,z）得到该点在voxel的索引。 3.根据索引判断该voxel种是否已经存在max_points_number个点，如果存在，则将该点直接丢弃，如果不满足，则将该点加入到该voxel中。 4. 计算voxel特征 采用voxelnet的图表示为如下：  ​1.2.2 Voxelization 参数 上文中的体素化过程涉及到两个重要的内容，一个是体素参数，另外一个是voxel特征根据该voxel中的特征如何求取。 Voxelization对参数的要求比较高，就发展历史来说，VoxelNet(CVPR18)是第一篇采用voxel-representation作为点云输入的网络结构，该文章中max_points_number设置的为35，voxel大小设置为0.5；采用的voxel特征提取方式为增加一个pointnet对每个voxel中的35个点特征提取得到相应的voxel特征（如下图中的featurelearning network所示的内容），但是该参数很明显是会丢失比较多的几何结构信息，但是以这样的参数划分在当时还受到VoxelNet网络后续的3D卷积的显存占用的影响（3D卷积很占显存，因此网络预处理的参数受到影响）。  18年的SECOND提出的3D稀疏卷积大大减少了3D卷积的内存占用，（我们知道，3D卷积本身会对空间中每一个voxel都进行卷积，但是3D稀疏卷积只保留了空间中非空的voxel，采用map映射的方式得到卷积后的voxel空间索引）；因此参数的设置自由了很多，就目前在KITTI和Nuscence上的sota的内容而言，我们一般采用的参数和特征提取方为： max−points−number=5,(w,l)=(0.05,0.05),h=0.1 采用的voxel特征直接为mean特征，即对每一个voxel中的所有点的坐标求均值即可。 1.2.3 related paper 这里只介绍一些在voxelrepresentation上做文章的研究内容，而不是采用voxel作为网络输入的研究工作，因此voxel-based的研究方法比较多，后续笔者会出一篇在这方面的研究综述，所以这里推荐的几篇文章都是在voxel-representation上的做出研究的工作。 voxel-based的先驱的两篇文章voxelnet和second的主要贡献分别是第一个提出采用voxel作为网络输入的方法和引入稀疏卷积替代3D卷积。这里补充一点voxel-based方法的backbone，目前几乎所有的voxel-based方法都采用如下的encoder的backone作为特征提取器。下图左图表示的是点的voxel表示，经过Voxelization化后，经过逐步下采样的encoder过程降为二维 feature map，最后再根据二维的feature的每一个像素点作为anchor point提出候选框。  在voxel-representation上做文章的研究工作，如下图，这是一篇发表在sensors2020上的文章Voxel-FPN:multi-scale voxel feature aggregation in 3D object detection frompoint clouds，该研究工作的主要内容是通过不同scale的体素划分，最后将其整合成到RPN网络结构中的FPN网络中，需要注意的是，这里的scale的大小要和最初划分的scale对应起来。  同样采用该思想的还有今年的CVPR20的文章HVNet，如下图所示，也是对场景中点云采用multi-scale的体素划分，最后也会形成一个FPN的结构，但是不同的细节和实现之处还是有很多的，HVNet采用了多线程同时并行处理每一个scale的体素划分，同时对于voxel的特征提取和Voxel-FPN也是不一样的。  在voxel划分上做研究的工作还有如下的waymo组的MVF工作，可以看到，之前的研究工作如果对于一个voxel中点数没有占据max_points_number实际上也会采用全0占据空间，而这一篇文章的一点创新则是修改成可自适应的储存点，不必强行每个voxel的空间占用一样大，可以节省不少内存占用。  1.2.4 voxelrepresentation方法小结 voxel-representation的方法的优点即是性能好又高效，不仅仅在精度上有着point-based的方法目前无法比拟的精度，在速度上也是很可观的，尤其是在稀疏卷积和3D流型卷积引入到3D目标检测后，发展更为迅速。但是缺点则是该类方法对参数比较敏感，预处理划分voxel的时候需要设置合适的参数，当然从信息论的方面理解，体素划分必然带来信息的丢失，尤其是局部细节信息的丢失，因此今年CVPR20上至少有三篇文章（SA-SSD，pointpainting，HVnet）在细节几何结构上做了一定的研究工作。  1.3 graph represention 这是一个比较新的representation，在3D检测中,今年CVPR20第一次出现了以graph作为representation的网络结构，如下图所示，graphrepresentation的核心问题也在于构建一个graph网络，即下图中的图左所示的内容。这也是很多在语义分割中遇到的问题，在目前的建图中大多是采用的knn的方法构建图结构，后续再送入到图卷积进行特种提取，最后根据pointrpn-head提出proposals。 ​ 就该类方法而言，目前的研究还不是很多，因为GCN非常耗时，可以理解为时pointnet++特征提取网络的升级版，不仅仅提取点之间的信息，同时根据‘点-边’信息提取到更加局部细节的信息，但是优点也可以理解到，3D shape实际上在增加边信息后，会更加容易感知（对比mesh结构可知），但是采用何种方式构建合适的graph都还是很需要研究的内容。  1.4 point-voxel fusion 既然我们知道point-based的方法具有保持了几何structure的能力，同时voxel-based的方法具有高效的感知能力，那么最新的研究就在考虑如何做这方面的fusion工作，PV-RCNN（CVPR20）采用的将voxel特征经过multi-scale的形式赋予到point上，最后再refine阶段将点的局部信息融合到pointnet中。SA-SSD采用voxel2point添加附加任务使得voxelbackbone具有structure aware能力。实际上根据representation fusion的经验，应该还是大有可做的。  2 Augmentation 实际上3D目标检测的数据增广方式和二维目标检测的方式大多相同，我们总结为如下一些比较常见的数据增广方式，根据动态图很容易的看到的出来数据增广的方式，这里笔者着重介绍一下groundtruth augmentor的方法，这应该是根据3D点云的稀疏空间特性所特有的数据增广方式。  ​​​​​​​​ground truth augmentor 就KITTIobject 3D的数据而言，每一帧的object数量从无到二十多个不等，ground truth augmentor的想法则是先从所有训练集中根据类别把groundtruth建立成一个data base，然后在训练的时候将data base中的gt按照类别丢一定数量的gt到当前训练的帧中，这里笔者给出一般在KITTI上数据增广的数量如下。即表示一般会选择在场景中丢进去15个car，丢进10个Pedestrians和Cyclists。 SAMPLE_GROUPS: [‘Car:15’,‘Pedestrian:10’, ‘Cyclist:10’] 因为该数据增广的工作在3D目标检测中比较重要，后续还延伸到一些涉及到该方面的研究工作，笔者做一点简单介绍. 这一篇文章（Class-balanced Grouping and Sampling for Point Cloud 3D Object Detection）的后续研究工作做成了一个detectionzoo，在github上叫det3D，但是该文章的初始问题是想解决在nuscene数据中的数据不平衡问题，根据作者的采样得到如下图表，这里也就是目标检测的longtail问题，数据不平衡问题  ​这里作者采用的gt数据增广方式采样如下个数的gt来平衡数据集本身存在的long tail问题，并最终在nuscence上取得了榜一的成绩。  笔者再介绍一篇今年CVPR20上涉及到gt augmentation的工作(oral)(What You See is What You Get:Exploiting Visibility for 3D Object Detection),，如下图，在本文gt数据增广后，俯视图下由（a）变成了(b)，但是作者指出这里出现的问题在于有的增广的物体出现在墙后，这在Lidar扫描过程中是不符合规律的，因此作者采取的增广策略是把对应的墙体去掉，如(d)图所示的内容。这就比较符合lidar扫描的特性，即遇到object就会反弹。  3 笔者的思考 实际上数据预处理在深度学习中也是比较重要的内容，就representation来说，voxel的方法高效但存在信息丢失,point-basde的方法感知能力不及cnn但输入为最原始的结构，Graph构建了更容易感知的结构，但也要承担GCN网络过长的前馈时间；就augmentation来说，gtaugmentation尽管在涨点上成了众人皆知的trick，但是要能很好的用起来该方法还是有一些值得研究的trick在里面，就比如上述提到的两篇文章。最后写一个flag，后续尽快写一个voxel-based方法研究的发展概述，主要也是笔者的理解。  推荐文献 [1]VoxelNet: End-to-End Learning for Point Cloud Based 3D Object Detection [2]Frustum PointNets for 3D Object Detection from RGB-D Data [3]PointRCNN: 3D Object Proposal Generation and Detection from Point Cloud’ [4]3DSSD: Point-based 3D Single Stage Object Detector [5]Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud ———————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/106439643 

前言 除了对应点方式，还可以将点云将与整个形状对齐，获得6D姿态。通常，首先进行粗配准以提供初始对准，然后进行密集配准方法，如迭代最近点（ICP），以获得最终的6D姿态。针对点云方式，挑选了一些相关的paper，在这里做下基本思想分享。  1、Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration 迭代最近点（ICP）算法是目前应用最广泛的点集配准方法之一。然而，基于局部迭代优化的ICP算法易受局部极小值的影响。它的性能严重依赖于初始化的质量，并且只保证局部最优性。本文提出了在ICP定义的L2误差度量下，两个三维点集欧氏（刚性）配准的第一个全局最优算法Go-ICP。Go-ICP方法基于搜索整个3D运动空间SE（3）的分枝定界（BnB）方案。利用SE（3）几何的特殊结构，推导了新的配准误差函数的上下界。在BnB方案中引入局部ICP，在保证全局最优的同时加快了新方法的速度。本文还讨论了扩展，解决了异常值健壮性问题。实验结果表明，该方法能够在不考虑初始值的情况下产生可靠的配准结果。Go-ICP可应用于需要最佳解决方案或无法始终获得良好初始化的情况。    2、SUPER 4PCS Fast Global Pointcloud Registration via Smart Indexing 大规模场景中的数据采集通常需要通过多次扫描积累信息。一种常见的方法是使用迭代最近点（ICP）算法（或其变体）局部对齐扫描对，但需要静态场景和扫描对之间的小运动。这可防止在多个扫描会话和/或不同采集模式（如立体声、深度扫描）之间积累数据。或者，可以使用允许扫描处于任意初始姿势的全局注册算法。然而，最先进的全局配准算法4PCS在数据点的数量上具有二次时间复杂度，这大大限制了它在获取大型环境方面的适用性。本文提出了Super 4PCS全局点云配准，它可以在线性时间（数据点的数目）中运行，并且在基于扫描对的（未知）重叠对齐问题的复杂性上输出敏感。算法简单，内存利用率高，速度快。本文证明，Super 4PCS比其他方法有显著的加速效果，并允许在以前不可能的尺度上非结构化高效地获取场景。   3、3DRegNet: A Deep Neural Network for 3D Point Registration 本文提出了一种三维扫描配准的深度学习算法3DRegNet。近年来随着廉价的3D商品传感器的出现，开发一种基于学习的3D配准算法将是非常有益的。本文在给定一组三维点对应关系的情况下，利用深度残差层和卷积层建立深度网络3DRegNet，主要完成两项任务： （1）将点对应关系分类为正确/错误的点对应关系 （2）可以回归将扫描对齐到公共参考帧的运动参数 与经典方法相比，3DRegNet有几个优点。首先，由于3DRegNet的工作原理是点对应，而不是原始扫描，因此明显快于许多传统方法。其次，论文证明该算法可以扩展到多视图场景，即同时处理两次以上扫描的注册。与使用四元数表示旋转的四变量位姿回归网络不同，本文使用李代数仅使用三个变量表示旋转。在两个具有挑战性的数据集（ICL-NUIM和SUN3D）上进行的大量实验表明3DRegNet性能优于其他方法，并取得了最新的结果。   4、3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions（斯坦福大学，代码开源） 由于三维扫描数据的噪声、低分辨率和不完整性，在真实深度图像上进行局部几何特征匹配是一项具有挑战性的任务。这些困难限制了目前最先进的方法的性能，这些方法通常基于几何特性上的直方图。本文提出了一个数据驱动的模型3DMatch，该模型学习局部体块描述符以建立部分3D数据之间的对应关系。为了积累模型的训练数据，提出了一种自监督的特征学习方法，利用现有的RGB-D重建中发现的数百万个对应标签。实验表明，该描述子不仅能够匹配新场景中的局部几何特征进行重建，而且可以推广到不同的任务和空间尺度（如Amazon Picking Challenge的实例级对象模型对齐和网格曲面对应）。结果表明，3DMatch始终优于其他最先进的方法，具有显著的优势。    ———————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/104537112 

 前言 近期读取了一些最新基于RGB图像下的机器人抓取论文，在这里分享下思路。  1、Optimizing Correlated Graspability Score and Grasp Regression for Better Grasp Prediction 本文提出了一种新的深度卷积网络结构，该结构通过引入新的丢失量，利用抓取质量评价来改进抓取回归。除此之外发布了Jacquard+，它是Jacquard数据集的一个扩展，允许在一个可变装饰上放置多个对象的模拟场景中评估抓取检测模型。Jacquard+通过物理模拟创建的，允许在完全可复制的条件下进行测试。实验结果表明，所提出的抓取检测方法无论在Jacquard数据集还是Jacquard+上都明显优于现有的抓取检测方法；  网络结构：  实验结果：   2、Real-time Grasp Pose Estimation for Novel Objects in Densely Cluttered Environment 现有抓取方式主要为从物体的质心抓取以及沿物体的长轴抓取，但是这类方式对复杂形状物体常常失败。本文提出了一种用于机器人拾取和定位的新目标实时抓取姿态估计策略。该方法在点云中估计目标轮廓，并在图像平面上预测抓取姿态和目标骨架。被测试对象主要有球形容器，网球，甚至复杂形状的对象，如鼓风机（非凸形）。结果表明，该策略对复杂形状物体的抓取效果良好，并与上述策略进行了比较，预测出了有效的抓取配置。实验验证了该抓取技术在两种情况下的有效性，即物体被清晰地放置和物体被放置在密集的杂波中。抓取准确率分别为88.16%和77.03%。所有的实验都是用一个真实的UR10机械手和WSG-50双指抓取器进行的。   3、GRIP: Generative Robust Inference and Perception for Semantic Robot Manipulation in Adversarial Environments 本文提出了一种两阶段的生成性鲁棒推理与感知（GRIP）方法，以探索在生成对抗环境中进行物体识别和姿态估计。生成鲁棒推理与感知（GRIP）作为一个两阶段的目标检测与姿态估计系统，目的是结合CNN的可区分相对优势和生成推理方法来实现鲁棒估计。在GRIP中，将推理的第一阶段表示为基于CNN的识别分布。CNN识别分布用于第二阶段的生成性多假设优化，这种优化是作为一个静态过程的粒子滤波器来实现的。本文证明，GRIP方法在不同光照和拥挤遮挡的对抗场景下，相对于最先进的姿态估计系统PoseCNN和DOPE，达到了SOTA。使用密歇根进度抓取机器人演示了抓取和目标定向顺序操作在对象拾取和放置任务中的兼容性。  4、Domain Independent Unsupervised Learning to grasp the Novel Objects 本文提出了一种基于无监督学习的可行抓取区域选择算法，监督学习在没有任何外部标签的情况下推断数据集中的模式。论文在图像平面上应用k-均值聚类来识别抓取区域，然后用轴指派方法。除此之外，定义了一个新的抓取决定指数（GDI）概念来选择图像平面上的最佳抓取姿势，并在杂乱或孤立的环境中对Amazon Robotics Challenge 2017 和Amazon Picking Challenge 2016的标准物体进行了多次实验。论文还将结果与基于先验学习的方法进行比较，以验证提出的算法对于不同领域中的各种新对象的鲁棒性和自适应性。   5、Multi-View Picking: Next-best-view Reaching for Improved Grasping in Clutter（代码开源） 摄像机视点选择是视觉抓取检测的一个重要方面，特别是在杂波中存在许多遮挡的情况下。现有方法使用静态相机位置或固定数据收集例程，本文的多视图拾取（MVP）控制器通过使用主动感知方法直接基于实时抓取姿势估计的分布来选择信息视点，从而减少杂波和遮挡造成的抓取姿势的不确定性。在从杂波中抓取20个目标的实验中，MVP控制器获得了80%的抓取成功率，比单视点抓取检测器的性能提高了12%。论文还证明了提出的方法比考虑多个固定视点的方法更准确和高效。   6、ROI-based Robotic Grasp Detection for Object Overlapping Scene 本文提出了一种基于感兴趣区域（ROI）的机器人抓取检测算法ROI-GD。ROI-GD使用ROI中的特征来检测抓取，而不是整个场景。它分为两个阶段：第一阶段是在输入图像中提供ROI，第二阶段是基于ROI特征的抓取检测器。通过标注视觉操作关系数据集，论文还构建了一个比康奈尔抓取数据集大得多的multi-object抓取数据集。实验结果表明，ROI-GD算法在对象重叠场景中有较好的表现，同时与康奈尔抓取数据集和Jacquard Dataset上的最新抓取检测算法具有可比性。机器人实验表明，ROI-GD可以帮助机器人在单目标场景和多目标场景中抓取目标，总体成功率分别为92.5%和83.8%。  ———————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/104505732 

00 前言 01 基于传统多视图几何的三维重建算法 1.1 主动式 （1）结构光 （2）TOF 激光飞行时间法 （3）三角测距法 1.2 被动式 （1）单目视觉 （2）双目/多目视觉 1.3 基于消费级RGB-D相机 02 基于深度学习的三维重建算法 2.1 在传统三维重建算法中引入深度学习方法进行改进 2.2 深度学习重建算法和传统三维重建算法进行融合，优势互补 2.3 模仿动物视觉，直接利用深度学习算法进行三维重建 （1）基于体素 （2）基于点云 （3）基于网格 03 总结 04 参考文献  00 前言 目前，三维重建技术已在游戏、电影、测绘、定位、导航、自动驾驶、VR/AR、工业制造以及消费品领域等方面得到了广泛的应用。方法同样也层出不穷，我们将这些方法依据原理分为两类：  基于传统多视图几何的三维重建算法 基于深度学习的三维重建算法 总地来说，尽管目前传统的三维重建算法依旧占据研究的主要部分，但是越来越多的研究者开始关注于用CNN探索三维重建，或者说，两者之间的交叉与融合。  有人问，在三维重建中引入深度学习方法有什么意义？我将意义概括为三部分：  为传统重建算法性能优化提供新的思路  一项名为 Code SLAM1 的工作，这项研究获得了CVPR 2018年的best paper提名奖，研究利用神经网络框架，并结合图像几何信息实现了单目相机的稠密SLAM。主要贡献在于使用了深度学习方法从单张图像中用神经网络提取出若干个基函数来表示场景的深度，这些基函数表示可以极大简化传统几何方法中的优化问题。显然，深度学习方法的引入可以给传统方法的性能提升提供新的思路，而以前，这部分工作大多由机器学习方法来做。  将深度学习重建算法和传统三维重建算法进行融合，优势互补  业界对算法的鲁棒性要求比较高，因此多传感器、乃至多种算法的融合以提升算法鲁棒性是个必然趋势，而深度学习在一些场景中具有天然优势，比如不可见部分的建模，传统算法就很难凭借“经验”来估计物体的深度。  模仿动物视觉，直接利用深度学习算法进行三维重建  动物跟人类直接基于大脑而非严格的几何计算来进行物体的三维重建，那么直接基于深度学习的方法在原理上也是可行的。特别需要注意的是，在一些研究中，有些方法直接基于单张图像（非单目，单目指利用单个摄像头）进行三维重建。理论上讲，单张图像已经丢失了物体的三维信息，因此在原理上即不能恢复深度信息，但是人类又能凭借经验大致估计物体的距离，因而也具有一定的“合理性”。  两者形成了各自的理论和体系，但未来三维重建领域研究一定是传统优化方法与深度学习的结合。目前，这方面研究仍处于起步阶段，还有许多问题亟待解决。下面的综述主要侧重于深度学习方法，但也仅列出重要文献，更详细的综述将会在公众后续的文章中介绍。  01 基于传统多视图几何的三维重建算法 传统的三维重建算法按传感器是否主动向物体照射光源可以分为 主动式 和 被动式 两种方法。这些年，也有不少研究直接基于消费级的 RGB-D 相机进行三维重建，如基于微软的 Kinect V1 产品，同样取得了不错的效果。基于传统多视图几何的三维重建算法概括如下：  主动式，指通过传感器主动地向物体照射信号，然后依靠解析返回的信号来获得物体的三维信息，常见的有：  结构光 TOF 激光飞行时间 三角测距法 被动式，直接依靠周围环境光源来获取RGB图像，通过依据多视图几何原理对图像进行解析，从而获取物体的三维信息。常见的依据原理可以分为：  单目视觉 双目/多目视觉 基于消费级RGB-D相机，相机可以基于主动式、被动式不同原理，优点在于基于这些设备的算法更具备实用性。  这些方法它们各自有着各自的优点和缺点，同样有各自所适用的应用范围。下面为想要入门基于深度学习进行三维重建领域的同学简要介绍这些方法，如需要深入了解，请仔细阅读相关文献，SfM和多视图几何等经典算法作为入门三维重建领域的基础永远都不会过时。  1.1 主动式 （1）结构光  结构光法依靠投影仪将编码的结构光投射到被拍摄物体上，然后由摄像头进行拍摄。由于被拍摄物体上的不同部分相对于相机的距离精度和方向不同，结构光编码的图案的大小和形状也会发生改变。这种变化可以被摄像头捕获，然后通过运算单元将其换算成深度信息，进而获取物体的三维轮廓信息。这种方法缺点是容易受环境光干扰，因此室外体验差。另外，随检测距离增加，其精度也会变差。目前，一些研究通过增大功率、改变编码方式等形式解决这些问题，取得了一定的效果。  （2）TOF 激光飞行时间法  TOF 飞行时间法依靠通过向目标连续发送光脉冲，然后依据传感器接收到返回光的时间或相位差来计算距离目标的距离。但显然这种方式足够的精度需要极为精确的时间测量模块，因此成本相对较高。好处是这种方法测量距离比较远，受环境光干扰比较小。目前这方面研究旨在降低计时器良品率及成本，相应的算法性能也在提升。  （3）三角测距法  三角测距法，即依据三角测距原理，不同于前两者需要较为精密的传感器，三角测距法整体成本较低，并且在近距离的时候精度较高，因而广泛应用于民用和商用产品中，如扫地机器人中。但三角测距的测量误差与距离有关，随着测量距离越来越大，测量误差也越来越大，这是由三角测量的原理导致的，不可避免。  1.2 被动式 被动式方面依靠多视图几何原理基于视差进行计算，我们简要叙述一下这些方法。  （1）单目视觉  单目视觉只使用单一摄像头作为采集设备，具有低成本、易部署等优点。其依靠一段时间内获得的连续图像的视差来重建三维环境。但其存在固有的问题：单张图像可能对应无数真实物理世界场景（病态），因此使用单目视觉方法从图像中估计深度进而实现三维重建的难度较大。依据原理，可以分类为：  目前这种算法广泛应用于手机等移动设备中，常见的算法有SfM ，REMODE 和SVO 等。  （2）双目/多目视觉  双目视觉主要利用左右相机得到的两幅校正图像找到左右图片的匹配点，然后根据几何原理恢复出环境的三维信息。但该方法难点在于左右相机图片的匹配，匹配地不精确都会影响最后算法成像的效果。多目视觉采用三个或三个以上摄像机来提高匹配的精度，缺点也很明显，需要消耗更多的时间，实时性也更差。  这两种方法理论上都可较精确恢复深度信息，但实际上受拍摄条件的影响，其精度往往无法得到保证。常见的有SGM 和SGBM 算法等，其中自动驾驶数据集KITTI中，排名前五十的算法几乎有一半都是对SGM 的改进。  1.3 基于消费级RGB-D相机 近年来，也有不少研究直接基于消费级的RGB-D相机进行三维重建，如在微软的Kinect V1、V2产品上，取得了不错的效果。最早，由帝国理工大学的Newcombe等人于2011年提出的Kinect Fusion 开启了RGB相机实时三维重建的序幕。此后有 Dynamic Fusion 和Bundle Fusion 等算法。  02 基于深度学习的三维重建算法 我们将基于深度学习的三维重建算法简要地分为三部分，更详细的文献综述将会在后续的公众号的系列文章中做介绍：  在传统三维重建算法中引入深度学习方法进行改进 深度学习重建算法和传统三维重建算法进行融合，优势互补 模仿动物视觉，直接利用深度学习算法进行三维重建 2.1 在传统三维重建算法中引入深度学习方法进行改进 因为CNN在图像的特征匹配上有着巨大优势，所以这方面的研究有很多，比如：  DeepVO，其基于深度递归卷积神经网络（RCNN）直接从一系列原始RGB图像（视频）中推断出姿态，而不采用传统视觉里程计中的任何模块，改进了三维重建中的视觉里程计这一环。  BA-Net ，其将 SfM 算法中的一环集束调整（Bundle Adjustment,BA）优化算法作为神经网络的一层，以便训练出更好的基函数生成网络，从而简化重建中的后端优化过程。  Code SLAM ，如之前所提，其通过神经网络提取出若干个基函数来表示场景的深度，这些基函数可以简化传统几何方法的优化问题。  2.2 深度学习重建算法和传统三维重建算法进行融合，优势互补 CNN-SLAM13将CNN预测的致密深度图和单目SLAM的结果进行融合，在单目SLAM接近失败的图像位置如低纹理区域，其融合方案给予更多权重于深度方案，提高了重建的效果。  2.3 模仿动物视觉，直接利用深度学习算法进行三维重建 我们知道，三维重建领域主要的数据格式有四种：  深度图(depth map)，2D图片，每个像素记录从视点到物体的距离，以灰度图表示，越近越黑；  体素(voxel)，体积像素概念，类似于2D之于像素定义；  点云(point cloud)，每个点逗含有三维坐标，乃至色彩、反射强度信息；  网格(mesh)，即多边形网格，容易计算。  因而，依据处理的数据形式不同我们将研究简要分为三部分：1）基于体素；2）基于点云；3）基于网格。而基于深度图的三维重建算法暂时还没有，因为它更多的是用来在2D图像中可视化具体的三维信息而非处理数据。  （1）基于体素  体素，作为最简单的形式，通过将2D卷积扩展到3D进行最简单的三维重建：  Depth Map Prediction from a Single Image using a Multi-Scale Deep Network, 2014 该方法是用深度学习做三维重建的开山之作，基于体素形式，其直接用单张图像使用神经网络直接恢复深度图方法，将网络分为全局粗估计和局部精估计，并用一个尺度不变的损失函数进行回归。  3D-R2N2: A unified approach for single and multi-view 3d object reconstruction, 2016 Christopher等人基于体素形式提出的3D-R2N2模型使用Encoder-3DLSTM-Decoder的网络结构建立2D图形到3D体素模型的映射，完成了基于体素的单视图/多视图三维重建（多视图的输入会被当做一个序列输入到LSTM中，并输出多个结果）。  但这种基于体素的方法存在一个问题，提升精度即需要提升分辨率，而分辨率的增加将大幅增加计算耗时（3D卷积，立次方的计算量）。  （2）基于点云  相较而言，点云是一种更为简单，统一的结构，更容易学习，并且点云在几何变换和变形时更容易操作，因为其连接性不需要更新。但需要注意的是，点云中的点缺少连接性，因而会缺乏物体表面信息，而直观的感受就是重建后的表面不平整。  A Point Set Generation Network for 3D Object Reconstruction From a Single Image, 2017。该方法是用点云做三维重建的开山之作，最大贡献在于解决了训练点云网络时候的损失问题，因为相同的几何形状可能在相同的近似程度上可以用不同的点云表示，如何用恰当的损失函数来进行衡量一直是基于深度学习用点云进行三维重建方法的难题。  Point-Based Multi-View Stereo Network, 2019。该方法通过对场景的点云进行处理，融合三维深度和二维纹理信息，提高了点云的重建精度。  （3）基于网格  我们知道之前的方法的缺点：  基于体素，计算量大，并且分辨率和精度难平衡 基于点云，点云的点之间缺少连接性，重建后物体表面不光滑 相较而言，网格的表示方法具有轻量、形状细节丰富的特点，重要是相邻点之间有连接关系。因而研究者基于网格来做三维重建。我们知道，网格是由顶点，边，面来描述3D物体的，这正好对应于图卷积神经网络的 M=(V,E,F) 所对应。  Pixel2Mesh ，用三角网格来做单张RGB图像的三维重建，相应的算法流程如下： （1）对于任意的输入图像都初始化一个椭球体作为初始三维形状。 （2）然后网络分为两部分： 一部分用全卷积神经网络来提取输入图像的特征；另一部分用图卷积网络来表示三维网格结构。 （3）对三维网格不断进行变形，最终输出物体的形状。 模型通过四种损失函数来约束形状，取得了很好的效果。贡献在于用端到端的神经网络实现了从单张彩色图直接生成用网格表示的物体三维信息。  03 总结 传统的三维重建算法可以分为：  这些方法各自有各自优点和使用范围，简要概括一下：  而基于深度学习的三维重建算法研究主要有三种：  在传统三维重建算法中引入深度学习方法进行改进 深度学习重建算法和传统三维重建算法进行融合，优势互补 模仿动物视觉，直接利用深度学习算法进行三维重建：基于体素 ，基于点云，基于网格 才疏学浅，做了简单的关于用深度学习做三维重建的叙述，更详细的综述将会在后续公众号的文章中给出。  ——————————————— 版权声明：本文为CSDN博主「Tom Hardy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_29462849/article/details/104442128 

前言物体检测是计算机视觉领域的一个重要任务，旨在从图像中准确识别并定位不同类别的物体。随着深度学习技术的飞速发展，目标检测与实例分割成为物体检测领域的前沿算法。本文将深入介绍目标检测与实例分割的原理和常见算法，以及它们在实际应用中的重要意义。 一、目标检测与实例分割的基本原理 目标检测是指在图像中找到并定位一个或多个感兴趣的物体，同时判断物体的类别。实例分割则更进一步，要求在像素级别对图像中的每个物体进行分割，实现对不同物体的精确分割与定位。 二、传统目标检测算法 1. Haar特征与级联分类器：经典的目标检测算法之一，通过Haar-like特征和级联分类器进行物体的检测，然而其性能相对较弱，适用于一些简单场景。 2. HOG+SVM：采用梯度方向直方图（HOG）特征结合支持向量机（SVM）进行目标检测，效果相对较好，但对于复杂场景仍存在一定的限制。  三、深度学习目标检测算法 1. R-CNN系列算法：包括R-CNN、Fast R-CNN、Faster R-CNN，这些算法通过候选框提取、特征提取和分类回归网络来实现目标检测。Faster R-CNN引入了Region Proposal Network（RPN）来加速候选框的提取，取得了较好的检测性能。 2. YOLO（You Only Look Once）：采用单个神经网络同时预测候选框的位置和类别，实现实时目标检测。YOLO的速度非常快，适用于实时应用，但在小物体上性能稍逊于Faster R-CNN。  四、实例分割算法 1. Mask R-CNN：基于Faster R-CNN的框架，通过增加分割分支来实现物体实例的像素级分割。Mask R-CNN在目标检测和实例分割任务上均表现出色，成为实例分割领域的代表算法。 2. FCN（Fully Convolutional Network）：不同于传统的基于区域的方法，FCN采用全卷积神经网络进行像素级别的语义分割，是实例分割算法的重要起源之一。  五、物体检测算法的应用领域 1. 自动驾驶：物体检测算法在自动驾驶系统中用于识别交通标志、行人、车辆等，实现智能驾驶与交通安全。 2. 工业自动化：应用于生产线上的物体检测，可以实现产品质量检测、零部件装配等自动化工作。 3. 智能安防：用于视频监控系统中的物体检测，可以识别异常行为、盗窃等安全事件。 结语： 目标检测与实例分割作为计算机视觉领域的研究热点，近年来取得了巨大的进步。随着深度学习技术的不断演进，我们相信这些算法在未来会进一步提升，为各行业带来更多智能化的应用。 

 在计算机视觉领域，卷积神经网络（Convolutional Neural Network，CNN）是一项具有革命性意义的深度学习算法。通过模拟人类视觉系统的工作原理，CNN在图像识别任务中取得了令人瞩目的成就，成为图像处理和计算机视觉领域的里程碑之一。 卷积层的特色 CNN的核心在于卷积层，其中包含了多个卷积核，它们类似于生物学中的神经元。这些卷积核通过滑动窗口的方式在输入图像上进行局部特征检测。通过卷积操作，CNN能够捕捉图像中的边缘、纹理和形状等重要特征，从而实现对图像的有效表示和抽象。 池化层的有效降维 CNN中的池化层对特征图进行降维处理，它通过选择局部区域内的最大值（最大池化）来减少特征图的尺寸和复杂性。这种降维有助于减少计算负担，防止过拟合，并提高模型的泛化能力。 全连接层的分类能力 在经过卷积层和池化层处理之后，CNN通过全连接层将提取到的高级特征映射到具体的类别。全连接层的非线性映射能力，使得CNN能够准确地对图像进行分类。 梯度下降优化 在训练CNN模型时，采用梯度下降优化算法，通过最小化损失函数来不断调整模型参数，使得预测结果与真实标签尽可能接近。这样的优化过程使得CNN逐步学习到图像的特征和模式，从而提高了识别准确率。 迁移学习的巧妙运用 鉴于CNN的庞大参数量，对于某些特定任务或数据较少的情况，单独训练一个大型CNN模型可能导致过拟合。在这种情况下，迁移学习成为一种有效的技术。通过利用在大规模图像数据集上预训练的CNN模型作为初始模型，在特定任务上进行微调，能够在较小数据集上取得优秀的识别性能。  总结：卷积神经网络（CNN）的出现在图像识别领域引起了一场革命。它通过卷积、池化和全连接层等核心技术，实现了对图像特征的高效提取和表示。其在图像分类、物体检测、人脸识别等任务上取得的卓越成就，彰显了其在计算机视觉领域的重要地位和广泛应用前景。通过持续的技术优化和迁移学习策略，CNN必将在未来继续推动图像识别技术的发展，为人们带来更多便捷和智能的应用体验。 

经过我今年对深度学习 机器学习的研究发现 其算法是错误的 计算机是一台以指令为单位的机器 它是不会学习的 所以没有学习算法一说 那是没有认清计算机的本质 学习是人才有的行为 机器怎么会学习吗 它只有指令啊 经过研究发现我们常说的人工智能 主要是如下四个函数构成的 下面我以常见的游戏AI为例讲解其实现 由于已有多年未碰编程 这里只给出大致算法 在游戏中 当角色或者NPC看/听到什么的时候 就开始学习过程 如何学习呢 其实所有的学习都是从理解开始的 下面给出Understand()函数 int Understand(string type, string action, string p1, string p2) {     string memory;     switch(type)     {         case 'walk'         memory=Walk(action,p1,p2);  // Walk()函数根据词典定义及参数p1, p2解释action并将相应的字符串写入memory         break;         case 'run'         memory=Run(action,p1,p2);         break;         case 'fight'         memory=Fight(action,p1,p2);         break;         case 'look'         memory=Look(action,p1,p2);  // 比如看这个行为 Understand()函数会把它解释成使视线接触人或事物 并把记忆记在数据库里                                                         // 实际上人在想看东西的时候 检索记忆也是找到上面的解释并做出相应的行为的         break;         ......         各种人的行为的函数  // 这里要注意的是行为的归类一定要仔细不要冗余 比如躺和侧躺是一类不能归为2类 我个人估算25个行为左右已经有很好                                         // 的人工智能70个基本上完美 这个时候Understand才两三百行 对游戏来说是个微不足道的小函数                                         // 要特别指出的是像跳绳 踢毽子等应该归属于一类Playing()玩游戏         break;     }     Remember(action, memory);  // 记忆理解所得的结果即把原始记忆和理解得出的记忆写入数据库 如表hero/NPC} 第二个函数是Study() 人要认识世界就要各种学习 理解了就学习了 所以 bool Study(string action) {     action=Look()/action=Listen();  // 通过看或者听学习     string type=IsAction(action);  // 判断是某种行为 比如走 跑 说话 看等     string p1,p2;     p1=IsParam1(action); p2=IsParam2(action);  // 对行为的一些描述p1 p2     Understand(type, action, p1, p2);  // 对行为进行理解并记忆 } 然后 NPC在空闲的时候还会想事情(就是普通的漫无目的想 假定其函数名为Thinking) 想了之后就做某种事情 第三个函数如下 int Thinking() {     int n=0;  // n是随机数 NPC在空闲的时候想什么事情是个随机事件 它随机性的发生     int type=rand()/2;  // 2可用其它值 处于某种想之中     switch(type)     {         case 1:         n=OnIdle();  // 在空想 函数给n赋予随机值         break;         case 2:         n=Memory();  // 在回忆 函数给n赋予随机值         break;         ......      }     switch(n)     {         case 1:         Walk();  // 某种形式某种目的的行走 与Understand()中那个不同这个是实际的行为 那个是把行走理解成某种行动的字符串数据         break;         case 2:         Talk();   // 某种目的某种内容的谈话         break;         ......         default         break;      } } 最后一个函数 也是最难的一个函数 就是思考(Thought) 对某个问题经过思考得出结果 int Thought(string question) {     if(LookupMemory(question))  // 在记忆中查找看是否找到 实际上是一个查找数据库的表并在表中的数据项查找的函数      {         string law;         law=Haslaw(question);  // 函数中可用IsNum() IsMathChar() IsLaw()等函数判断question里面是否有数字 数学符号 数学/物理法则等         if(law.IsNotNull())  // 看是否包含有法则         {             RunLogic(law);  // 运行相应的逻辑法则         }         else         {                                      // 做其它的事 比如和某个NPC对话         }         return 1;     }     else     {         if(Research(question))  // 研究问题         {             ......    // 成功相应的行为             return 1;         }         else        {            ......    // 失败相应的行为            return 0;        }     } } 通过以上四个函数就可以把理解 学习 想事情 思考问题完整的实现出来 完成人工智能的全部功能 这里根本不需要什么深度学习 机器学习 这就是全部的人工智能函数 下面再写两个跟游戏有关及常用的人工智能函数 第一个自动寻路/自动驾驶 自动寻路要注意的一点就是不能把HitTest()当成"轻重缓急"算法写在判断避让那里 因为自动寻路避让障碍的时候是个轻重缓急行为 不是进行碰撞检测 bool AutoDriving(int Character) {     bool obstacle=Look();  // 看道路上有无障碍     if(obstacle)     {          int distance=OrderofPriority(Character);  // 判断轻重缓急          int direction=GetInput(keyboard);          ChangeDirection(direction, distance);  // 在距离distance处转向     } } 一个可能的轻重缓急算法是 int OrderofPriority(int Character) {     int type=rand()/2;  // 轻和重 缓和急是个随机产生情况 这是客观世界的真实反应 游戏世界也是一样的     switch(type)     {         int min=GetMinimum();  // 测出物体中心到前端的距离的最大值即碰撞距离 不碰撞只要大于它就行了 比如可以略大于它 也可以+1 +2 +5厘米或者加个随机数         int senmin,senmax;         GetDistanceSensitivity(Character,senmin,senmax);  // 得到角色的最小最大距离敏感度 一个查询数据库的函数         case 1:  // 轻/缓         return min+(rand()/0.1~1)+senmax;  //  大于碰撞距离小于等于角色最大距离敏感度并略有出入的随机数 或者其它可自定         break;         case 2:  // 重/急         return min+(rand()/0.1~1)+senmin;  //  大于碰撞距离小于等于角色最小距离敏感度并略有出入的随机数 或者其它可自定         break;     } } 第二个真实打斗 这个函数主要是随机数加上一些三十六计计谋即可 如 int RealFighting() {      int type=rand()/50;  // 计谋中的一种 包括连环计 计中计      switch(type)      {           case 1:           声东击西();           break;           case 2:           围魏救赵();           break;           case 3:           四面楚歌();           火上浇油();           break;           ......      } } 甚至还可以写出复合体及变体 提到游戏中人工智能 很多时候都是个随机数问题 因为自然界中的事都是随机发生的 当然到了虚拟世界里面 各种事情也是个随机性的 恰好有rand()函数能很好的解决这一问题 欢迎转载

经过我今年对深度学习 机器学习的研究发现 其算法是错误的 计算机是一台以指令为单位的机器 它是不会学习的 所以没有学习算法一说 那是没有认清计算机的本质 学习是人才有的行为 机器怎么会学习吗 它只有指令啊 经过研究发现我们常说的人工智能 主要是如下四个函数构成的 下面我以常见的游戏AI为例讲解其实现 由于已有多年未碰编程 这里只给出大致算法 在游戏中 当角色或者NPC看/听到什么的时候 就开始学习过程 如何学习呢 其实所有的学习都是从理解开始的 下面给出Understand()函数 int Understand(string type, string action, string p1, string p2) {     string memory;     switch(type)     {         case 'walk'         memory=Walk(action,p1,p2);  // Walk()函数根据词典定义及参数p1, p2解释action并将相应的字符串写入memory         break;         case 'run'         memory=Run(action,p1,p2);         break;         case 'fight'         memory=Fight(action,p1,p2);         break;         case 'look'         memory=Look(action,p1,p2);  // 比如看这个行为 Understand()函数会把它解释成使视线接触人或事物 并把记忆记在数据库里                                                         // 实际上人在想看东西的时候 检索记忆也是找到上面的解释并做出相应的行为的         break;         ......         各种人的行为的函数  // 这里要注意的是行为的归类一定要仔细不要冗余 比如躺和侧躺是一类不能归为2类 我个人估算25个行为左右已经有很好                                         // 的人工智能70个基本上完美 这个时候Understand才两三百行 对游戏来说是个微不足道的小函数                                         // 要特别指出的是像跳绳 踢毽子等应该归属于一类Playing()玩游戏         break;     }     Remember(action, memory);  // 记忆理解所得的结果即把原始记忆和理解得出的记忆写入数据库 如表hero/NPC} 第二个函数是Study() 人要认识世界就要各种学习 理解了就学习了 所以 bool Study(string action) {     action=Look()/action=Listen();  // 通过看或者听学习     string type=IsAction(action);  // 判断是某种行为 比如走 跑 说话 看等     string p1,p2;     p1=IsParam1(action); p2=IsParam2(action);  // 对行为的一些描述p1 p2     Understand(type, action, p1, p2);  // 对行为进行理解并记忆 } 然后 NPC在空闲的时候还会想事情(就是普通的漫无目的想 假定其函数名为Thinking) 想了之后就做某种事情 第三个函数如下 int Thinking() {     int n=0;  // n是随机数 NPC在空闲的时候想什么事情是个随机事件 它随机性的发生     int type=rand()/2;  // 2可用其它值 处于某种想之中     switch(type)     {         case 1:         n=OnIdle();  // 在空想 函数给n赋予随机值         break;         case 2:         n=Memory();  // 在回忆 函数给n赋予随机值         break;         ......      }     switch(n)     {         case 1:         Walk();  // 某种形式某种目的的行走 与Understand()中那个不同这个是实际的行为 那个是把行走理解成某种行动的字符串数据         break;         case 2:         Talk();   // 某种目的某种内容的谈话         break;         ......         default         break;      } } 最后一个函数 也是最难的一个函数 就是思考(Thought) 对某个问题经过思考得出结果 int Thought(string question) {     if(LookupMemory(question))  // 在记忆中查找看是否找到 实际上是一个查找数据库的表并在表中的数据项查找的函数      {         string law;         law=Haslaw(question);  // 函数中可用IsNum() IsMathChar() IsLaw()等函数判断question里面是否有数字 数学符号 数学/物理法则等         if(law.IsNotNull())  // 看是否包含有法则         {             RunLogic(law);  // 运行相应的逻辑法则         }         else         {                                      // 做其它的事 比如和某个NPC对话         }         return 1;     }     else     {         if(Research(question))  // 研究问题         {             ......    // 成功相应的行为             return 1;         }         else        {            ......    // 失败相应的行为            return 0;        }     } } 通过以上四个函数就可以把理解 学习 想事情 思考问题完整的实现出来 完成人工智能的全部功能 这里根本不需要什么深度学习 机器学习 这就是全部的人工智能函数 下面再写两个跟游戏有关及常用的人工智能函数 第一个自动寻路/自动驾驶 自动寻路要注意的一点就是不能把HitTest()当成"轻重缓急"算法写在判断避让那里 因为自动寻路避让障碍的时候是个轻重缓急行为 不是进行碰撞检测 bool AutoDriving(int Character) {     bool obstacle=Look();  // 看道路上有无障碍     if(obstacle)     {          int distance=OrderofPriority(Character);  // 判断轻重缓急          int direction=GetInput(keyboard);          ChangeDirection(direction, distance);  // 在距离distance处转向     } } 一个可能的轻重缓急算法是 int OrderofPriority(int Character) {     int type=rand()/2;  // 轻和重 缓和急是个随机产生情况 这是客观世界的真实反应 游戏世界也是一样的     switch(type)     {         int min=GetMinimum();  // 测出物体中心到前端的距离的最大值即碰撞距离 不碰撞只要大于它就行了 比如可以略大于它 也可以+1 +2 +5厘米或者加个随机数         int senmin,senmax;         GetDistanceSensitivity(Character,senmin,senmax);  // 得到角色的最小最大距离敏感度 一个查询数据库的函数         case 1:  // 轻/缓         return min+(rand()/0.1~1)+senmax;  //  大于碰撞距离小于等于角色最大距离敏感度并略有出入的随机数 或者其它可自定         break;         case 2:  // 重/急         return min+(rand()/0.1~1)+senmin;  //  大于碰撞距离小于等于角色最小距离敏感度并略有出入的随机数 或者其它可自定         break;     } } 第二个真实打斗 这个函数主要是随机数加上一些三十六计计谋即可 如 int RealFighting() {      int type=rand()/50;  // 计谋中的一种 包括连环计 计中计      switch(type)      {           case 1:           声东击西();           break;           case 2:           围魏救赵();           break;           case 3:           四面楚歌();           火上浇油();           break;           ......      } } 甚至还可以写出复合体及变体 提到游戏中人工智能 很多时候都是个随机数问题 因为自然界中的事都是随机发生的 当然到了虚拟世界里面 各种事情也是个随机性的 恰好有rand()函数能很好的解决这一问题 欢迎转载

0x01 编码发展史0x20以下的编码用作控制码，接下来一直到127号的的字节用来表示大小写字母，标点符号，空格，数字，这就是ascii码，只能满足美国人的需要。中国人民通过对 ASCII 编码的中文扩充改造，产生了 GB2312 编码，可以表示6000多个常用汉字。汉字实在是太多了，包括繁体和各种字符，于是产生了 GBK 编码，它包括了 GB2312 中的编码，同时扩充了很多。中国是个多民族国家，各个民族几乎都有自己独立的语言系统，为了表示那些字符，继续把 GBK 编码扩充为 GB18030 编码。每个国家都像中国一样，把自己的语言编码，于是出现了各种各样的编码，如果你不安装相应的编码，就无法解释相应编码想表达的内容。终于，有个叫 ISO 的组织看不下去了。他们一起创造了一种编码 UNICODE ，这种编码非常大，大到可以容纳世界上任何一个文字和标志。所以只要电脑上有 UNICODE 这种编码系统，无论是全球哪种文字，只需要保存文件的时候，保存成 UNICODE 编码就可以被其他电脑正常解释。UNICODE 在网络传输中，出现了两个标准 UTF-8 和 UTF-16，分别每次传输 8个位和 16个位。于是就会有人产生疑问，UTF-8 既然能保存那么多文字、符号，为什么国内还有这么多使用 GBK 等编码的人？因为 UTF-8 等编码体积比较大，占电脑空间比较多，如果面向的使用人群绝大部分都是中国人，用 GBK 等编码也可以。但是目前的电脑来看，硬盘都是白菜价，电脑性能也已经足够无视这点性能的消耗了。所以推荐所有的网页使用统一编码：UTF-8。0x02 各种编码URL编码一个百分号和该字符的ASCII编码所对应的2位十六进制数字，例如“/”的URL编码为%2F(一般大写，但不强求)具体情况：网址路径的编码，用的是utf-8编码查询字符串的编码，用的是操作系统的默认编码GET和POST方法的编码，用的是网页的编码在Ajax调用中，IE采用GB2312编码（操作系统的默认编码），而Firefox采用utf-8编码。escape()不能直接用于URL编码，它的真正作用是返回一个字符的Unicode编码值。比如"春节"的返回结果是%u6625%u8282，也就是说在Unicode字符集中，"春"是第6625个（十六进制）字符，"节"是第8282个（十六进制）字符。它的具体规则是，除了ASCII字母、数字、标点符号"@ * _ + - . /"以外，对其他所有字符进行编码。在\u0000到\u00ff之间的符号被转成%xx的形式，其余符号被转成%uxxxx的形式。对应的解码函数是unescape()。所以，"Hello World"的escape()编码就是"Hello%20World"。因为空格的Unicode值是20（十六进制）。HTML实体编码命名实体：以&开头，分号结尾的，例如“<”的编码是“<”字符编码：十进制、十六进制ASCII码或unicode字符编码，样式为“&#数值;”,例如“<”可以编码为“<”和“<”JS编码js提供了四种字符编码的策略，三个八进制数字，如果不够个数，前面补0，例如“e”编码为“\145”两个十六进制数字，如果不够个数，前面补0，例如“e”编码为“\x65”四个十六进制数字，如果不够个数，前面补0，例如“e”编码为“\u0065”对于一些控制字符，使用特殊的C类型的转义风格（例如\n和\r）CSS编码用一个反斜线()后面跟1~6位的十六进制数字，例如e可以编码为“\65”或“65”或“00065”复合编码所谓复合编码，也就是说输出的内容输出在多个环境中，例如<td onclick=”openUrl(add.do?userName=’<%=value%>’);”>11</td>value的内容首先出现在一个URL中，这个URL在一段javascript中，而javascript代码又是html的一部分。所以解码的顺序就是HTML解码–>js解码–>url解码，那么正确的编码顺序就应该是url编码–>js编码–>html编码。0x03 浏览器解析浏览器解析HTML的步骤浏览器收到从服务器发送来的HTML内容，会从头解析，当遇到<script></script>时，会调用javascript脚本解析器解析javascript，并执行脚本，然后继续解析其他的HTML内容，对于一些需要触发才能执行的事件，当触发事件发送时，脚本解析器才会解析其中的脚本，在事件触发之前，它是HTML的一部分。编码问题实例解析分析1、URL编码"javascript:alert(1)" <a href="%6a%61%76%61%73%63%72%69%70%74:%61%6c%65%72%74%28%31%29"></a>Answer: The javascript will NOT execute.url不能对协议以及协议后的冒号进行编码，否则url解析器会认为其是无类型的。这里JavaScript是个伪协议，而且对javascript进行了url编码，会导致url解析器认为其是无类型，无法进行url解码。最终也就不会弹窗。2、HTML字符实体编码 "javascript" 和 URL 编码 "alert(2)"<a href="&#x6a;&#x61;&#x76;&#x61;&#x73;&#x63;&#x72;&#x69;&#x70;&#x74;:%61%6c%65%72%74%28%32%29">Answer: The javascript will execute.这里javascript属于html解析中的”属性值中的字符引用“，所以可以先被html解码，然后被url解析器识别出来，后面的alert(2)由于不是协议，url解析器可以正常解析，最后会弹窗。3、URL 编码 ":" <a href="javascript%3aalert(3)"></a>Answer: The javascript will NOT execute.url不能对协议以及协议后的冒号进行编码，否则url解析器会认为其是无类型的。这里JavaScript是个伪协议，而且对javascript后的冒号进行了url编码，会导致url解析器认为其是无类型，无法进行url解码。最终也就不会弹窗。4、HTML字符实体编码 < 和 > <div>&#60;img src=x onerror=alert(4)&#62;</div>Answer: The javascript will NOT execute.“<”和“>”字符被编码为“<”和“>”。当解析器解析完“<div>”并处于“数据状态”时，这两个字符将会被解析。当解析器遇到“&”字符，它会知道这是“数据状态的字符引用”，因此会消耗一个字符引用（例如“<”）并释放出对应字符的token。在这个例子中，对应字符指的是“<”和“>”。读者可能会想：这是不是意味着“<”和“>”的token将会被理解为标签的开始和结束，然后其中的脚本会被执行？答案是脚本并不会被执行。原因是解析器在解析这个字符引用后不会转换到“标签开始状态”。正因为如此，就不会建立新标签。因此，我们能够利用字符实体编码这个行为来转义用户输入的数据从而确保用户输入的数据只能被解析成“数据”。5、HTML字符实体编码 < 和 > <textarea>&#60;script&#62;alert(5)&#60;/script&#62;</textarea>Answer: The javascript will NOT execute AND the character entities will NOT be decoded either在<textarea>和<title>标签中的字符引用会被HTML解析器解码，在解析这些字符引用的过程中不会进入“标签开始状态”，甚至在<textarea>和<title>的内容中都无法创建标签，更不会有javascript执行了。6、<textarea>和<title><textarea><script>alert(6)</script></textarea>Answer: The javascript will NOT execute.在浏览器解析RCDATA元素的过程中，解析器会进入“RCDATA状态”。在这个状态中，如果遇到“<”字符，它会转换到“RCDATA小于号状态”。如果“<”字符后没有紧跟着“/”和对应的标签名，解析器会转换回“RCDATA状态”。这意味着在RCDATA元素标签的内容中（例如<textarea>或<title>的内容中），唯一能够被解析器认做是标签的就是“</textarea>”或者“</title>”。当然，这要看开始标签是哪一个。因此，在“<textarea>”和“<title>”的内容中不会创建标签，就不会有脚本能够执行。7、HTML字符实体编码 " ' " （单引号）<button onclick="confirm('7&#39;);">Button</button>Answer: The javascript will execute.html先将'解码为一个控制字符'，闭合成功，然后javascript进行解析，最终执行。8、Unicode编码 " ' " （单引号）<button onclick="confirm('8\u0027);">Button</button>Answer: The javascript will NOT execute.javascript把uniocde\u0027解析为一个常量'，而不是控制字符'，所以无法闭合。//像圆括号、双引号、单引号等等这些控制字符的unicode编码，在进行JavaScript解析的时候仅会被解码为字符串文本或者标识符名称9、HTML字符实体编码 alert(9);<script>&#97;&#108;&#101;&#114;&#116&#40;&#57;&#41;&#59</script>Answer: The javascript will NOT execute.在script块中的字符引用并不会被解析和解码，对于unicode字符视情况而定。10、Unicode 编码 alert<script>\u0061\u006c\u0065\u0072\u0074(10);</script>Answer: The javascript will execute.Unicode转义序列只有在标识符名称里不被当作字符串，也只有在标识符名称里的编码字符能够被正常的解析。当Unicode转义序列出现在标识符名称中时，它会被解码并解释为标识符名称的一部分，比如标识符alert,所以可以弹框。11、Unicode 编码 alert(11)<script>\u0061\u006c\u0065\u0072\u0074\u0028\u0031\u0031\u0029</script>Answer: The javascript will NOT execute.这里的unicode转义序列 (11) 不是标识符，所以无法正常解析，即无法弹窗。12、Unicode 编码 alert 和 12 <script>\u0061\u006c\u0065\u0072\u0074(\u0031\u0032)</script>Answer: The javascript will NOT execute.\u0031\u0032不会被解释为字符串常量（因为它们没有用引号闭合）13、Unicode 编码 " ' " （单引号） <script>alert('13\u0027)</script>Answer: The javascript will NOT execute.这里\u0027没有被解析为控制字符，无法闭合，所以无法弹窗。（当用Unicode转义序列来表示一个控制字符时，例如单引号、双引号、圆括号等等，它们将不会被解释成控制字符，而仅仅被解码并解析为标识符名称或者字符串常量。）14、Unicode 编码换行符（0x0A） <script>alert('14\u000a')</script>Answer: The javascript will execute.这里会执行程序并弹窗，因为\u000a被解析成了换行字符文本，避免了因为换行符的出现而导致的javascript语法错误。15、混合加密解析<a href="&#x6a;&#x61;&#x76;&#x61;&#x73;&#x63;&#x72;&#x69;&#x70;&#x74;&#x3a;&#x25;&#x35;&#x63;&#x25;&#x37;&#x35;&#x25;&#x33;&#x30;&#x25;&#x33;&#x30;&#x25;&#x33;&#x36;&#x25;&#x33;&#x31;&#x25;&#x35;&#x63;&#x25;&#x37;&#x35;&#x25;&#x33;&#x30;&#x25;&#x33;&#x30;&#x25;&#x33;&#x36;&#x25;&#x36;&#x33;&#x25;&#x35;&#x63;&#x25;&#x37;&#x35;&#x25;&#x33;&#x30;&#x25;&#x33;&#x30;&#x25;&#x33;&#x36;&#x25;&#x33;&#x35;&#x25;&#x35;&#x63;&#x25;&#x37;&#x35;&#x25;&#x33;&#x30;&#x25;&#x33;&#x30;&#x25;&#x33;&#x37;&#x25;&#x33;&#x32;&#x25;&#x35;&#x63;&#x25;&#x37;&#x35;&#x25;&#x33;&#x30;&#x25;&#x33;&#x30;&#x25;&#x33;&#x37;&#x25;&#x33;&#x34;&#x28;&#x31;&#x35;&#x29;"></a>Answer: The javascript will execute.(1)先经过html解析(题目2，属性值中的字符引用，正常解析)<a href="javascript:%5c%75%30%30%36%31%5c%75%30%30%36%63%5c%75%30%30%36%35%5c%75%30%30%37%32%5c%75%30%30%37%34(15)"></a>(2)然后url解析(依旧题目2，url解析的内容为非协议内容，正常解析)<a href="javascript:\u0061\u006c\u0065\u0072\u0074(15)"></a>(3)unicode解析(题目10，unicode转义字符出现在标识符名称中，正常解析)<a href="javascript:alert(15)"></a>(4)最后语法正确，javascript正常解析并弹窗。（当然，这里需要在</a>前面随便加点字符，不然无法显示并弹窗）资料索引：对于xss等有关的html，url，unicode编码做的一个小结深入理解浏览器解析机制和XSS向量编码浏览器编码流程從XSS理解編碼解析原理 网页编码就是那点事作者：Hf1dw链接：https://www.jianshu.com/p/19d8172d730b来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

0x01 二分法原理：二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。一般步驟：（1）确定该区间的中间位置K；（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。0x02 递归原理：一种通过重复将问题分解为同类的子问题而解决问题的方法典型例子：斐波那契数列描述：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契数列") 自然中的斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。解决方式：def f(n, mermory={}): if n == 1 or n == 2: return 1 else: try: return mermory[n] except KeyError: result = f(n-1)+f(n-2) mermory[n] = result return resultprint(f(9))0x03 回溯法原理：在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。解决问题一般步骤：1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。典型例子：八皇后问题描述：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。解决方式：https://blog.csdn.net/weixin_41865447/article/details/800344330x04 排序算法概念：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。分类：非稳定排序算法：快速排序、希尔排序、堆排序、直接选择排序稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序十个常用排序算法0x05 搜索算法利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。分类：枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。0x06 哈希算法将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。很难找到逆向规律只要符合散列思想的算法都可以被称为是Hash算法对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称为碰撞。0x07 贪心算法原理在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。一种近似算法一般步骤：1、建立数学模型来描述问题；2、把求解的问题分成若干个子问题；3、对每一子问题求解，得到子问题的局部最优解；4、把子问题的解局部最优解合成原来解问题的一个解。典型例子：0/1背包问题马踏棋盘均分纸牌例题：https://www.cnblogs.com/hust-chen/p/8646009.html0x08 分治算法概念：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。典型例子：排序中：归并排序、堆排序、快速排序；实例：找伪币、求最值、棋盘覆盖https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/32632970x09 动态规划概念：用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。举例：线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济）等；应用实例：最短路径问题 ，项目管理，网络流优化等；https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin0x10 字符串匹配算法概念：在一个给定的字符文本内搜寻出自己想要找的一个字符串，平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。分类：KMP、BM、Sunday、Horspool、RK参考：https://cloud.tencent.com/developer/news/282694https://blog.csdn.net/paincupid/article/details/81159320作者：Hf1dw链接：https://www.jianshu.com/p/4b29805f9fa7来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个， 并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。 输入：s = "baaca", k = 3。 输出："aaabc"。

2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。输入：n = 4, a = 2, b = 3。输出：6。

工程概论 - 电梯调度模拟软件设计思路问题建模及基本假设查阅18层大楼的层高和电梯速度，再结合便于软件开发的目的，不妨设电梯的速度为0.5层/秒，且为匀速运动，没有加减速过程。考虑到实际电梯容量和便于图形化的原因，不妨设电梯容量为12人。考虑到进出电梯的人越多，电梯停留时间越长，不妨设为每秒钟电梯可以出一人或者进一人。考虑到出现人群的分布不是均匀的，尤其在 1楼有非常大的吞吐量，所以设置人群生成规则如下:    25%的人群 : 1楼出发,到达 random(0,20)    25%的人群 : random(0,20)出发,到达1楼    50%的人群 : random(0,20)出发 到达 random(0,20)设人群的人数为 random(1,5)技术选型首先，在所有同学都已经有 C 和 Java学习经验的基础上，最关键的技术瓶颈在于GUI层。经过交流，团队中只有一名同学掌握有GUI 开发的经验，技术栈是 .NET 的 C# + WPF。但是会 C#的只有一人，如果承担了所有的开发工作就会导致效率低下，所以要将程序解耦为算法层和GUI层。后来算法同学决定使用Python。因为程序的数据规模非常低，使用 Python不会造成性能瓶颈，而且可以降低语言层面的复杂度。算法层和GUI层之间的通信，一开始使用了命令行调用、标准输入输出的方式。算法层和GUI层定义了一致的数据结构，并且使用JSON 进行数据传递。但这种方式需要使用者也拥有 Python环境，且该方式在非GUI开发者的电脑上出现异常，难以调试。所以决定转用 HTTP协议，使用 Flask 对算法进行服务端的封装，再使用 Docker部署在服务器上，对外提供API。这样使用者的电脑只需要 .NET Framework环境就可以运行程序。此外，以后还可以使用 Web 端 / QT / Android / IOS等不同前端技术及平台开发运行在不同操作系统上的前端程序。核心算法简介该电梯调度算法主要基于 LOOK调度算法。该算法按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求，当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，从而实现对电梯的有效调度。此外由于电梯1只停在单数层,电梯2只停在双数层,只有电梯3可以停在任意层。这个约束条件看似引入了新的复杂度，其实恰恰让三个电梯失去了联系，大大降低了复杂度。显然，只存在唯一一种调度分配情况，就是单数层到单数层的人由电梯1负责，双数层到双数层的人由电梯2负责，剩下由电梯3负责。3个电梯之间互不干扰，实现非常简便。在后续实践中，也验证了此调度分配情况可以基本完成负载均衡分配，效率高。基本数据类型定义person：搭乘电梯的乘客。其属性包括：come_time（出现的时间）、from_floor（起始楼层）to_floor（目标楼层）、current_floor（当前楼层）、in_which_elevator（所在电梯,可取0，1，2，3，分别指不在电梯中、在第一个电梯中、在第二个电梯中、在第三个电梯中）、is_out（是否完成电梯乘坐）elevator：电梯。其属性包括：current_floor（当前楼层）、move_direction（运行方向）floor：楼层。其属性包括：floor_up_people =[]（上行人群）、self.floor_down_people =[]（下行人群）、up_button（上升按钮）、down_button（下降按钮）算法伪代码//已知第t秒时的状态,进行调度,给出t+1时的状态时间循环（每循环一轮为一秒）//处理person到达事件遍历person数组，如果p.come_time==t（该乘客首次出现）将该乘客分配给对应的楼层 更新对应楼层电梯按钮更新楼层people数组（分为上行人群和下行人群）//处理电梯//对每个电梯，根据电梯的move_direction分类处理（move_direction取0，1，2，分别代表电梯静止、上行、下行）//（这一秒结束）代表continue，不再执行循环体剩下的部分 如果电梯静止遍历所有楼层，检测楼层电梯按钮 如果楼上有人按电梯电梯设置为上行（这一秒结束） 如果楼下有人按电梯电梯设置为下行（这一秒结束） 如果本层楼有人 如果此人上行电梯设置为上行（这一秒结束） 如果此人下行 电梯设置为下行（这一秒结束）如果电梯上行 如果电梯没有对齐某一楼层（如在3.5层） 电梯向上运行半层更新乘客状态（这一秒结束） 如果电梯对齐了某一楼层如果电梯中有乘客抵达目标楼层 更新该乘客的状态（这一秒结束）如果电梯人数已满 电梯向上运行半层 更新乘客状态（这一秒结束）如果楼层有人要进电梯 更新人的状态 更新楼层的状态如果楼层上行person数组为空 楼层上行按钮置False （这一秒结束）如果电梯内人数不为零 向上半层，并且更新乘客状态（这一秒结束）如果电梯内人数为零 如果电梯以上的楼层还有人向上半层，并且更新乘客状态（这一秒结束） 如果电梯以上的楼层没有人电梯状态改为静止（这一秒结束） //下行同理 //其余两个电梯同理软件功能不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。每天早上，那些差5分钟就迟到的人，在等电梯时，一般会做两件事：    第一，在心里骂电梯慢    第二，在心里暗算着电梯调度如何优化前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。为了上班不扣工资不迟到，我们决定通过调整电梯调度算法来实现对电梯运行载客的优化，以达到节约时间的目的。本程序基于我们的电梯调度算法，计划使用三个电梯同时模拟各层楼随机出现人前往不同楼层来验证本算法的可靠性。并且为了使运行结果明显，本程序还增添了可视化界面，使测试人能够清晰明了的观察本程序的运行情况。运行结果通过分析最终采用3个电梯，1号电梯只停奇数楼层和1楼，2号电梯只停偶数电梯和1楼，三号电梯所有楼层都停。经过多次测试，每次测试时长均超过10分钟，程序运行稳定，能够满足预想的最优化调度电梯，尽可能的缩短人员的等待时间，来实现效率最大化。in.json 运行顺利，没有故障，对实际的电梯调度具有参考意义。结构框图在这里插入图片描述软件流程图在这里插入图片描述在这里插入图片描述运行界面截图在这里插入图片描述在这里插入图片描述在这里插入图片描述软件测试及截图测试文件为algorithm_test.py文件。该文件为测试算法的一个测试文件，读取test_json文件夹中的测试文件，调用算法运行，与正确结果进行对比，相同returntestsuccess。交互选择初始人为设定乘楼梯人的属性（come_time,from_floor,to_floor,current_floor,in_which-elevator,is_out）,把设定的属性写在test_json文件夹中的in1.json和in2.json文件中，把正确的结果写在该文件夹下的out1.json和out2.json文件中。在这里插入图片描述在这里插入图片描述♻️ 资源在这里插入图片描述大小： 1.33MB➡️ 资源下载：https://download.csdn.net/download/s1t16/87390787————————————————版权声明：本文为CSDN博主「神仙别闹」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/s1t16/article/details/129314916