计算机专业学算法的都学些什么算法，有什么书可以看的学的话需要些什么基础的_CMS教程

计算机算法非常多的

A搜寻算法

俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Beam Search

束搜索(beam search)方法是解决优化问题的一种启发式方法，它是在分枝定界方法基础上发展起来的，它使用启发式方法估计k个最好的路径，仅从这k个路径出发向下搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70年代中期首先被应用于人工智能领域,1976 年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯，并快速地获得一个解。

二分取中查找算法

一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

Branch and bound

分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

数据压缩

数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。

Diffie–Hellman密钥协商

Diffie–Hellman key exchange，简称“D–H”，是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

Dijkstra’s 算法

迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，迪科斯彻算法可以用来找到两个城市之间的最短路径。

动态规划

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。比较著名的应用实例有：求解最短路径问题，背包问题，项目管理，网络流优化等。这里也有一篇文章说得比较详细。

欧几里得算法

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

最大期望（EM）算法

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

快速傅里叶变换(FFT)

快速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。

哈希函数

HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

堆排序

Heapsort是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。

归并排序

Merge sort是建立在归并 *** 作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

RANSAC 算法

RANSAC 是”RANdom SAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法，由Fischler and Bolles在1981提出，它是一种非确定性算法，因为它只能以一定的概率得到合理的结果，随着迭代次数的增加，这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”（那些对模型参数估计起到支持作用的点）和”outliers”（不符合模型的点），并且这组观测数据受到噪声影响。RANSAC 假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。

RSA加密演算法

这是一个公钥加密算法，也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效，其被广泛地用于电子商务加密，大家都相信，只要密钥足够长，这个算法就会是安全的。

并查集Union-find

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

Viterbi algorithm

寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)。

OpenMVG (open Multiple View Geometry)：开源多视角立体几何库，这是一个cv届处理多视角立体几何的著名开源库，信奉逗简单，可维护地，提供了一套强大的接口，每个模块都被测试过，尽力提供一致可靠的体验。

地址：github

文档：documents

openMVG能够：

解决多视角立体几何的精准匹配问题；

提供一系列SfM需要用到的特征提取和匹配方法；

完整的SfM工具链（校正，参估，重建，表面处理等）；

openMVG尽力提供可读性性强的代码，方便开发者二次开发，核心功能是尽量精简的，所以你可能需要其它库来完善你的系统。openMVG分成了几个大的模块：

核心库：各个功能的核心算法实现；

样例：教你怎么用；

工具链：也就是连起来用咯（乱序图像集的特征匹配，SfM，处理色彩和纹理）；

#0 安装（win10+VS2013）

第一步当然是从github clone代码，然后按照 BUILD 说明 *** 作，需要注意的是：

template <class T> inline T operator|(T x, T y){

return static_cast<T>(static_cast<int>(x) | static_cast<int>(y));

};

建议和opencv一起编译，方法是在CMakeListstxt文件中修改相应选项为 ON，然后在cmake的GUI中添加一个叫OpenCV_DIR的入口，值就是你已经安装好的opencv的路径。

openMVG写的非常不错，对Windows也提供了良好的支持，所以cmake之后用VS打开生成的openMVGsln解决方案就可以进行编译了，编译的时间稍久。我用的VS2013不支持C++新特性：constexpr，所以建议你使用VS2015或更新版本，如果一定要用VS2013，可以这样做：在src/openMVG/cameras/Camera_Commonhpp文件中将有constexpr的地方直接去掉，或者改成模板函数也是可以的：

运行样例，这里遇到一个坑：DenseStoraageh line 86报错：R6010 Assertion failed，这是一个断言错误，在release模式下不会出现，但在debug模式下几乎是必现。原因嘛，打开Eigen给出的网址可以明确：数据结构未对齐（unaligned arrays）。这个问题对于刚接触openMVG的人来说还是很烦人的，openMVG代码很优雅，很多数据类型都是从模板类或函数延伸，通过虚函数扩展各项具体方法，而且非常强烈的依赖Eigen这个库，所以给定位问题带来了阻碍。经过一天的攻坚，最后大概确认了原因：

regionsh这个文件中定义的Regions类包含了fixed-size vectorizable Eigen types的stl容器vector，按照Eigen提供的解决方法，需要做的是：

//原来

typedef std::vector<FeatureT> FeatsT;

//改成

typedef std::vector<FeatureT, Eigen::aligned_allocator<FeatureT>> FeatsT;

//其它类似的地方都要改，包括返回vector的函数，最好也加上 EIGEN_MAKE_ALIGNED_OPERATOR_NEW

#1 核心库

#11 图像

#Image Container

openMVG提供一个基本的类用作图像容器：Image<T>，T代表像素类型，这个类可以处理灰度，RGB，RGBA或者自定义类型的图像。用法很简单：

// A 8-bit gray image:

Image<unsigned char> grayscale_image_8bit;

// Multichannel image: (use pre-defined pixel type)

// A 8-bit RGB image:

Image<RGBColor> rgb_image_8bit;

// 8-bit RGBA image

Image<RGBAColor> rgba_image_8bit;

Image<Rgba<unsigned char> > rgba_image2_8bit;

这里的 RGBColor，RGBAColor等是openMVG基于Eigen定义好的类型，具体是定义在pixel_typeshpp中。

#Image I/O

openMVG支持ppm/pgm,jpeg,png,tiff格式的文件，例子：

Image<RGBColor> rgb_image_gray;

bool bRet = ReadImage("FooimgExtension", &rgb_image);

#Drawing operations

用于在图像上画圆，椭圆，直线等。

#12 数值

openMVG重新包装了Eigen的基本类型和算法，以便更简单的调用。比如 Vec2代表一个二维点（char型）。

#13 特征

这个模块主要是提供特征容器的封装，包括特征，特征描述，关键点集等，基本都是模板类，比如顶一个sift特征描述子可以这样做：

// SIFT like descriptor

typedef Descriptor<float, 128> siftDescriptorData;

#14 相机

此模块提供不同的相机模型的抽象类，包括：

#小孔相机模型

最简单的相机模型，如图：相机模型包括内参和外参，关键词也就是大家熟悉的几样：投影矩阵，旋转、平移矩阵，焦距、主点等，具体参见说明。看一个例子：openMVG提供的PinholeCamera类：

/// Pinhole camera P = K[R|t], t = -RC

struct PinholeCamera

{

//构造函数

PinholeCamera(

const Mat3 & K = Mat3::Identity(),

const Mat3 & R = Mat3::Identity(),

const Vec3 & t = Vec3::Zero())

: _K(K), _R(R), _t(t)

{

_C = -Rtranspose() t;

P_From_KRt(_K, _R, _t, &_P);

}

PinholeCamera(const Mat34 & P)

{

_P = P;

KRt_From_P(_P, &_K, &_R, &_t);

_C = -_Rtranspose() _t;

}

/// Projection matrix P = K[R|t]

Mat34 _P;

/// Intrinsic parameter (Focal, principal point)

Mat3 _K;

/// Extrinsic Rotation

Mat3 _R;

/// Extrinsic translation

Vec3 _t;

/// Camera center

Vec3 _C;

};

#15 多视角几何

这部分是比较基础和重要的模块之一，包括了：

多视角集几何中n（>=2）视角的求解算法；

将这些求解算法综合起来以便进行鲁棒估计的通用框架——Kernel；

文档中讲解了单应矩阵，本征矩阵，本质矩阵，位置矩阵等的概念，讲得非常好，建议仔细阅读文档。简单的解释一下：

单应矩阵：描述两个投影平面之间的关系；

本征矩阵：同一个场景在两个相机成像下的关系，也就是物体上的点A在两个视角下成像位置的关系；

本质矩阵：基于本征矩阵和内参矩阵建立，描述相机和本征矩阵位置之间的相对关系；

位置矩阵：估计相机的绝对位置（被转化为一个最小化问题求解）；

Kernel：一个将求解器、数据、度量方案等结合起来的类，这个类将用于鲁棒的估计以上的参数和矩阵；

#16 线性规划

一个用于求解多视角几何中线性优化（参数估计）的工具集，文档。

#17 鲁棒估计

提供一些列鲁棒估计方法，比如：Max-Consensus，Max-Consensus，AC-Ransac A Contrario Ransac等。

#17 匹配

提供的接口包括：NNS，K-NN，FLANN，KVLD，Cascade hashing Nearest Neighbor等。这些接口可用于在二维或三维点集，以及更高维的特征描述集中。

#18 追踪

多视几何里的追踪是指在一系列的中找到对应的特征点（同一点在不同视角下的位置）。

#19 sfm

openMVG提供的sfm模块包含了处理SfM问题的一系列方法个数据存储接口，例如相机位置估计，结构测量，BA等。 SfM_Data类包含了SfM所有的输入：

struct SfM_Data

{

/// Considered views

Views views; // 包含图像文件名，id_view，id_pose，id_intrinsic，image size。

/// Considered poses (indexed by viewid_pose)

Poses poses; // 相机的三维位置

/// Considered camera intrinsics (indexed by viewid_cam)

Intrinsics intrinsics; // 相机内参

/// Structure (3D points with their 2D observations)

Landmarks structure; // 二维视图特征关联的3D点

}

下面是例子：

#1 features_siftPutativeMatches

这个样例做了这么几件事（直接翻译官方）：

分别提取两张图像的SIFT特征（使用非免费的vlsift）并形成特征描述；

根据特征描述子匹配两张图像上的特征点（BRUTE_FORCE_L2方法）；

展示匹配结果；

刚开始的时候会遇到Assertion failed断言错误，处理办法见上一篇文章。运行成功项目目录下会生成三个文件：00_imagesjpg，01_featuresjpg，02_siftMatchessvg。

#2 features_affine_demo

这个例子是图像MSER（参考）和TBMR特征提取的样例，MSER（Maximally Stable Extremal Regions）最大极值稳定区域是一种对图像灰度具有仿射变换不变性，也许也是这个样例起名的原因。TBMR（tree-based Morse regions）这个算法不是特别了解，具体可以在google学术中搜索。

#3 features_image_matching

这个样例给出了利用Image_describer接口提取特征描述子，并匹配和显示结果的样例。示例中可以选择SIFT，AKAZE_MLDB或者AKAZE算法，AKAZE介绍可看这里，是一种比SIFT更稳定的特征检测算法。程序中关于解析输入参数的部分可以注释掉（如果你是用过VS2013 debug），直接修改sImage_describer_type这个值以测试。

#4 features_kvld_filter 和 features_repeatability

这两个也是关于特征提取和匹配的，kvld这个例子中由于之前更改了regionsh中的内容，所以有些函数接口也要做相应改变，具体也是在vector中增加对齐函数选项。

#5 multiview_robust_homography_guided 和 multiview_robust_fundamental_guided

这两个样例是估计单应矩阵和本征矩阵的，并且能够根据这些信息反过来确定匹配点。两个样例运行时间都很长（分辨率教大时），第一个在用另外的照片时还遇到报错，大概是在DoG时出错，具体也没有细究了·····

#6 exif_Parsing

提取EXIF信息，编译后通过命令行执行，给出的参数格式：--imafile 你的照片路径，路径中使用/斜杠。

另一篇：learn openMVG-安装和简介

#7 multiview_robust_essential

估计本质矩阵并计算3D结构。这个例子可以直接运行，生成的点云十分稀疏且不带颜色信息。

计算机的算法具有可行性，有穷性、输入\输出、确定性。

计算机算法特点

1有穷性。一个算法应包含有限的 *** 作步骤，而不能是无限的。事实上“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们不把他视为有效算法。

2 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。算法中的每一个步骤应当不致被解释成不同的含义，而应是十分明确的。也就是说，算法的含义应当是唯一的，而不应当产生“歧义性”。

3 有零个或多个输入、所谓输入是指在执行算法是需要从外界取得必要的信息。

4 有一个或多个输出。算法的目的是为了求解，没有输出的算法是没有意义的。

5有效性。算法中的每一个步骤都应当能有效的执行。并得到确定的结果。

：

重要算法