BM立体匹配算法的参数详解

OpenCV3.4两种⽴体匹配算法效果对⽐以OpenCV⾃带的Aloe图像对为例：1.BM算法（Block Matching）参数设置如下：int numberOfDisparities = ((imgSize.width / 8) + 15) & -16;cv::Ptr<cv::StereoBM> bm = cv::StereoBM::create(16, 9);cv::Rect roi1, roi2;bm->setROI1(roi1);bm->setROI2(roi2);bm->setPreFilterCap(31);bm->setBlockSize(9);bm->setMinDisparity(0);bm->setNumDisparities(numberOfDisparities);bm->setTextureThreshold(10);bm->setUniquenessRatio(15);bm->setSpeckleWindowSize(100);bm->setSpeckleRange(32);bm->setDisp12MaxDiff(1);bm->compute(imgL, imgR, disp);效果如下：BM算法得到的视差图（左），空洞填充后得到的视差图（右）2.SGBM（Semi-Global Block matching）算法:参数设置如下：enum { STEREO_BM = 0, STEREO_SGBM = 1, STEREO_HH = 2, STEREO_VAR = 3, STEREO_3WAY = 4 };int numberOfDisparities = ((imgSize.width / 8) + 15) & -16;cv::Ptr<cv::StereoSGBM> sgbm = cv::StereoSGBM::create(0, 16, 3);sgbm->setPreFilterCap(63);int SADWindowSize = 9;int sgbmWinSize = SADWindowSize > 0 ? SADWindowSize : 3;sgbm->setBlockSize(sgbmWinSize);int cn = imgL.channels();sgbm->setP1(8 * cn*sgbmWinSize*sgbmWinSize);sgbm->setP2(32 * cn*sgbmWinSize*sgbmWinSize);sgbm->setMinDisparity(0);sgbm->setNumDisparities(numberOfDisparities);sgbm->setUniquenessRatio(10);sgbm->setSpeckleWindowSize(100);sgbm->setSpeckleRange(32);sgbm->setDisp12MaxDiff(1);int alg = STEREO_SGBM;if (alg == STEREO_HH)sgbm->setMode(cv::StereoSGBM::MODE_HH);else if (alg == STEREO_SGBM)sgbm->setMode(cv::StereoSGBM::MODE_SGBM);else if (alg == STEREO_3WAY)sgbm->setMode(cv::StereoSGBM::MODE_SGBM_3WAY);sgbm->compute(imgL, imgR, disp);效果如图：SGBM算法得到的视差图（左），空洞填充后得到的视差图（右）可见SGBM算法得到的视差图相⽐于BM算法来说，减少了很多不准确的匹配点，尤其是在深度不连续区域，速度上SGBM要慢于BM算法。

BM算法详解BM算法 后缀匹配，是指模式串的⽐较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮⼒匹配算法的改进。

为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利⽤好后缀和坏字符可以⼤⼤加快模式串的移动距离，不是简单的++j，⽽是j+=max (shift(好后缀), shift(坏字符)) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个字符，继续⽐较，如下图：坏字符出现在模式串中，这时可以把模式串第⼀个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图： 此处配的图是不准确的，因为显然加粗的那个b并不是”最靠右的”b。

⽽且也与下⾯给出的代码冲突！我看了论⽂，论⽂的意思是最右边的。

当然了，尽管⼀时⼤意图配错了，论述还是没有问题的，我们可以把图改正⼀下，把圈圈中的b改为字母f就好了。

接下来的图就不再更改了，⼤家⼼⾥有数就好。

为了⽤代码来描述上述的两种情况，设计⼀个数组bmBc['k']，表⽰坏字符‘k’在模式串中出现的位置距离模式串末尾的最⼤长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。

如下图： 数组bmBc的创建⾮常简单，直接贴出代码如下：1 void preBmBc(char *x, int m, int bmBc[]) {23 int i;45 for (i = 0; i < ASIZE; ++i)67 bmBc[i] = m;89 for (i = 0; i <= m - 1; ++i)1011 bmBc[x[i]] = m - i - 1;1213 } 代码分析：ASIZE是指字符种类个数，为了⽅便起见，就直接把ASCII表中的256个字符全表⽰了，哈哈，这样就不会漏掉哪个字符了。

BM算法BM算法，即Boyer-Moore算法，是一种被广泛应用于字符串匹配的算法。

它由Robert S. Boyer和J Strother Moore于1977年提出，并在一些文本搜索和字符串匹配的应用中表现出优异的性能。

下面将对BM算法进行详细的介绍。

一、算法概述BM算法是一种自底向上的字符串匹配算法，它通过构建坏字符规则和好后缀规则来决定模式串的移动距离。

相比于朴素的字符串匹配算法，BM算法在匹配失败时能够根据模式串和文本串的已知信息进行跳跃，从而提高了匹配的效率。

二、坏字符规则坏字符规则是指当模式串与文本串的某个字符不匹配时，我们可以根据这个不匹配的字符来确定模式串应该向右移动的距离。

为了实现这个规则，我们需要预先构建一个坏字符表，其中记录了每个字符在模式串中最后一次出现的位置。

当发生不匹配时，我们可以直接将模式串向右移动到坏字符表中对应字符的位置。

三、好后缀规则好后缀规则是指当模式串与文本串的后缀部分匹配成功时，我们可以根据这个好后缀来确定模式串应该向右移动的距离。

为了实现这个规则，我们需要预先构建一个前缀表和后缀表，其中记录了每个前缀或后缀在模式串中第一次出现的位置。

当发生匹配时，我们可以根据前缀表和后缀表中的信息来确定模式串应该向右移动的距离。

四、算法步骤1.预处理阶段：构建坏字符表和前缀表、后缀表。

2.匹配阶段：从左到右依次比较模式串和文本串的字符。

3.如果发生不匹配：根据坏字符规则将模式串向右移动相应的距离。

4.如果匹配成功：根据好后缀规则将模式串向右移动相应的距离。

5.重复步骤2-4直到模式串移动到文本串的末尾位置。

五、算法性能分析BM算法的时间复杂度为O(n)，其中n为文本串的长度。

在最好的情况下，BM 算法的时间复杂度可以达到O(n/m)，其中m为模式串的长度。

相比于朴素的字符串匹配算法，BM算法在处理较长的文本串时具有更好的性能表现。

六、总结BM算法是一种经典的字符串匹配算法，它通过结合坏字符规则和好后缀规则来实现高效的字符串匹配。

块匹配算法 bm3d算法的原理bm3d算法是一种用于图像去噪的块匹配算法，它具有高效、准确的特点。

本文将详细介绍bm3d算法的原理和实现过程。

一、引言图像去噪是图像处理中的一项重要任务，在图像采集和传输过程中，常常会受到噪声的干扰，导致图像质量下降。

因此，开发一种高效的图像去噪算法对于提升图像质量具有重要意义。

bm3d算法是一种基于块匹配的图像去噪算法，通过将图像分成若干个块，并在每个块内进行自适应的块匹配和块滤波，从而实现图像去噪的目的。

二、原理介绍1. 块划分将待去噪的图像分成大小相同的块，每个块包含一定数量的像素点。

这里使用非重叠的块划分方式，即每个块之间没有重叠的像素点。

2. 块匹配对于每个块，将其与图像中所有其他块进行匹配，找出与之最相似的一组块。

这里使用块匹配算法来寻找相似的块，常用的块匹配算法有均方差匹配、相关系数匹配等。

3. 3D变换将匹配到的相似块按照一定的方式进行3D变换，将其表示为一组3D数据。

这样可以提取出块内的结构信息，便于后续的块滤波操作。

4. 块滤波对于每个块，利用其相似块的3D数据进行块滤波操作，即对3D 数据进行滤波，得到去噪后的3D数据。

常用的块滤波方法有硬阈值滤波、软阈值滤波等。

5. 逆3D变换将去噪后的3D数据进行逆3D变换，得到去噪后的块。

6. 块合并将所有去噪后的块合并起来，得到最终的去噪图像。

三、算法流程1. 输入待去噪的图像。

2. 对图像进行块划分，得到一组块。

3. 对每个块进行块匹配，找出相似的块。

4. 对匹配到的相似块进行3D变换，得到一组3D数据。

5. 对每个块的3D数据进行块滤波，得到去噪后的3D数据。

6. 对去噪后的3D数据进行逆3D变换，得到去噪后的块。

7. 将所有去噪后的块合并起来，得到最终的去噪图像。

8. 输出去噪后的图像。

四、实验结果bm3d算法在图像去噪方面取得了较好的效果。

通过实验证明，与传统的去噪算法相比，bm3d算法在保持图像细节的同时，有效地去除了噪声，提升了图像质量。

由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。

首先，先简单说明一下有关BM算法的一些基本概念。

BM算法是一种精确字符串匹配算法（区别于模糊匹配）。

BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

BM算法的基本流程: 设文本串T，模式串为P。

首先将T与P进行左对齐，然后进行从右向左比较，如下图所示:若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。

下面，来详细介绍一下坏字符规则和好后缀规则。

首先，诠释一下坏字符和好后缀的概念。

请看下图：图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。

1）坏字符规则（Bad Character）：在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。

ii. 如果x在模式P中出现，则以该字符进行对齐。

用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。

例1：下图红色部分，发生了一次不匹配。

计算移动距离Skip(c) = 5 - 3 = 2，则P向右移动2位。

移动后如下图：2）好后缀规则（Good Suffix）：若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。

ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。

BM算法详解来源在没有BM算法时，其原始算法是从后往前进⾏匹配，需要两层循环，判断以某个字符为结尾的⼦串是否和模式串相等，这种算法也称作暴搜；贴上代码：void BLS(string s, string p) {int s_len = s.size(), p_len = p.size();int j = 0, i = 0;while (j <= s_len - p_len) {for (i = p_len - 1; i >= 0 && p[i] == s[i + j]; --i) {}if (i < 0) {cout << "match: " << i + j + 1 << endl;j += p_len;}elsej++;}}算法的思想还是⽐较容易理解的，i和j分别指的是，模式串中已经匹配的位数，模式串相对于原串移动的位数；移动规则算法包含了两个重要的内容，分别是好后缀和坏字符的规则；坏字符：当模式串和原串的字符并不匹配时，原串中的字符就称为坏字符；好后缀：模式串和原串的字符相等时所有的字符串，⽐如ABCD和BCD，那么它的好后缀则包括第⼀次匹配的D，和第⼆次匹配的CD，还有第三次的BCD；例⼦：BM算法的向右移动模式串的距离就是取坏字符和好后缀算法得到的最⼤值；这两个内容分别拥有着⼏条规则，需要注意：坏字符1. 坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个位置，继续⽐较；⽐如说，ABC和D，其中D和A对齐，因为不匹配，所以D会移动到和B对齐；2. 坏字符出现在模式串中，这时可以把模式串中第⼀个出现（从后往前数第⼀个出现，也就是从前往后数，最靠右出现的）的坏字符和原串的坏字符对齐；⽐如说，BCCBCAD和AAD，假如其中AAD和BCC对齐，发现D和C⽆法匹配，移动到和BCA匹配，此时同样不匹配，但是A存在于模式串中，所以移动到模式串中坏字符出现的上⼀次位置，也就是向后移⼀位，和CAD对齐；当⾸次⽐较就⽆法匹配时，那么肯定是运⽤坏字符规则，因为并不存在好后缀；所以我们发现坏字符的移动规则公式为：后移位数＝坏字符的位置－模式串中的上⼀次出现位置那⽤代码表⽰则是void preBmBc(string x, vector<int>& bmBc) {int i = 0;int len = (int)x.size();// 全部更新为⾃⼰的长度for (i = 0; i < ASIZE; ++i) {bmBc[i] = len;}// 计算字符串中每个字符距离字符串尾部的长度for (i = 0; i < x.size() - 1; ++i) {bmBc[x[i]] = len - i - 1;}}⾸先应该知道的是，bmBc存储的是坏字符出现的位置距离模式串末尾的最⼤长度；前⼀个循环⽤来处理第⼀种规则，因为遇见不匹配时，直接移动模式串的长度；后⼀个循环处理第⼆种规则，需要注意的是，因为要保证最靠右原则，所以要从头开始循环，从⽽使得当遇见相同的字符，后者可以将前者进⾏覆盖。

立体匹配算法指标立体匹配算法是一种用于计算机视觉中的重要技术，它可以通过分析图像中的特征点和深度信息来实现图像的立体重建和三维场景的恢复。

在立体匹配算法中，评价算法的指标是十分重要的，可以用来衡量算法的准确性、鲁棒性和效率等方面。

本文将介绍几个常用的立体匹配算法指标，并对其进行详细的解释和分析。

一、视差误差视差误差是衡量立体匹配算法准确性的重要指标之一。

视差是指左右图像中对应像素点之间的水平偏移量，视差误差则是算法计算得到的视差值与真实值之间的差异。

视差误差可以通过计算平均绝对误差（MAE）或均方根误差（RMSE）得到，较小的视差误差代表算法的准确性较高。

二、匹配正确率匹配正确率是衡量立体匹配算法鲁棒性的指标之一。

它表示算法成功找到了正确的匹配点的比例。

匹配正确率可以通过计算正确匹配点的数量与总匹配点数的比值得到，较高的匹配正确率代表算法对噪声和变化较鲁棒。

三、计算时间计算时间是衡量立体匹配算法效率的指标之一。

立体匹配算法需要对图像进行特征提取、匹配计算等复杂操作，因此算法的计算时间直接影响到实时性和实用性。

通常使用算法的平均运行时间或计算复杂度来评估算法的计算效率，较短的计算时间代表算法的效率较高。

四、稠密度稠密度是衡量立体匹配算法完整性的指标之一。

它表示算法成功计算出的视差值的比例。

立体匹配算法的目标是计算图像中所有像素点的视差值，较高的稠密度代表算法对整个图像的处理能力较强。

五、误匹配率误匹配率是衡量立体匹配算法鲁棒性的指标之一。

它表示算法错误匹配的点的比例。

误匹配率可以通过计算错误匹配点的数量与总匹配点数的比值得到，较低的误匹配率代表算法对噪声和变化较鲁棒。

六、可扩展性可扩展性是衡量立体匹配算法适应性的指标之一。

它表示算法在处理不同场景和不同图像时的表现能力。

立体匹配算法需要具备一定的适应性，能够处理复杂场景、光照变化、纹理缺乏等情况，并保持较好的准确性和鲁棒性。

七、内存占用内存占用是衡量立体匹配算法资源消耗的指标之一。

BM算法一、概述字符串是一种线性表，在计算机科学领域，模式匹配问题一直都是学者们研究和关心的热点。

模式匹配时指在目标文本串检索子串的过程，其中字串成为模式。

模式匹配算法分为多模式匹配算法和单模式匹配算法，其中多模式匹配算法主要有AC算法及其他一些改进算法；单模式匹配算法主要有BF法、KMP法、BM算法及其一些改进算法（BMH算法和BMHS算法等）。

二、算法介绍1.常规的BF算法常规的BF算法在进行匹配时，移动模式串的方向时从左到右，而进行比较的时候也是从左到右，基本框架如下。

set j = 0;while( j <= ( strlen(主串) - strlen(模式串) ){For(i=0; i<strlen(模式串) && 模式串[i]==主串[j+i]; ++i);If(i==srlen(模式串))Return 结果;Else++j;}2.BM算法BM算法在移动模式串的时候是从左到右，而进行比较的时候是从右到左的，今本框架如下。

set j = 0;while( j <= ( strlen(主串) - strlen(模式串) ){For(i=stlen(模式串)-1; i>=0 && 模式串[i]==主串[j+i]; -- i);If(i<0)Return 结果;Else++j;}三、BM算法思想BM算法在进行字符串匹配的时候包含两个并行的算法，也就是所谓的bad-character shift，good-suffix shifit，即坏字符规则和好后缀规则，来决定字符不匹配时向后跳跃的距离。

下面来介绍这两个规则。

注：1.shilf就是模式串向后跳跃的距离2.x是模式串3.Y是目标串第一个规则：“bad-charact shift”(1)第一种情况很简单，就是在匹配的过程中，x中的a与y中的b没有匹配上，这时候判断b。

如果在x中没有发现b，就说明只要含有b的y的字串就不可能匹配成功，所以这时要直接跳到b的后面，继续匹配。

BM立体匹配算法的参数详解BM（Boyer-Moore）算法是一种常见的字符串匹配算法，其主要思想是通过匹配过程中的字符比较以及预处理过程中的坏字符规则和好后缀规则，来实现高效的字符串匹配。

BM立体匹配算法是对BM算法进行了改进和优化，使其更加高效和实用。

1. 坏字符规则（Bad Character Rule）：坏字符规则是BM立体匹配算法的核心，通过预处理待匹配字符串，找出模式串在匹配过程中的每个字符在模式串中最右边出现的位置。

当发生不匹配时，根据坏字符的位置，将模式串向右移动到能够使坏字符与文本串对应的位置对齐。

2. 好后缀规则（Good Suffix Rule）：好后缀规则是BM立体匹配算法的关键之一，通过预处理模式串，找出每个好后缀在模式串中最右边出现的位置。

当发生不匹配时，根据好后缀的位置，将模式串向右移动到能够使好后缀与文本串对应的位置对齐。

3. 好后缀上边界（Good Suffix Upper Bound）：好后缀上边界是BM立体匹配算法中的一个重要参数，用于判断是否需要进行好后缀规则的处理。

当好后缀的长度小于等于好后缀上边界时，直接移动模式串到文本串的位置（也可以称之为滑动窗口）。

当好后缀的长度大于好后缀上边界时，再根据好后缀规则进行处理。

4. 坏字符规则失效位置（Bad Character Failure Position）：坏字符规则失效位置是BM立体匹配算法的一个辅助参数，用于确定当一些字符发生不匹配时，模式串需要向右移动的位置。

根据坏字符的位置和坏字符规则失效位置，选择较大的位置进行模式串的移动。

以上就是BM立体匹配算法的主要参数。

通过预处理模式串和待匹配串，找出坏字符和好后缀在模式串中的位置，以及好后缀的上边界，可以有效地减少字符的比较次数，提高字符串匹配的效率。

同时，通过选择合适的坏字符规则失效位置，可以进一步优化算法的性能。

总结起来，BM立体匹配算法的参数详解如下：-坏字符规则：根据每个字符在模式串中最右边出现的位置，将模式串向右移动。

字符串匹配算法之BM算法 BM算法，全称是Boyer-Moore算法，1977年，德克萨斯⼤学的Robert S. Boyer教授和J Strother Moore教授发明了⼀种新的字符串匹配算法。

BM算法定义了两个规则：1、坏字符规则：当⽂本串中的某个字符跟模式串的某个字符不匹配时，我们称⽂本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。

此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。

2、好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上⼀次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

关于坏字符规则和好后缀规则的具体讲解，以及怎么移动，可以查看阮⼀峰⽼师的详细讲解：这⾥根据讲解画了两张图，⽅便⾃⼰理解坏字符规则：2019年11⽉14⽇15:38:41 修改具体代码如下：1private static final int SIZE = 256; // 全局变量或者是局部变量23/**4 * 坏字符规则哈希表构建⽅法5 *6 * @param b7 * 模式串8 * @param m9 * 模式串的长度10 * @param bc11 * 散列表12*/13private void generateBC(char[] b, int m, int[] bc) {14for (int i = 0; i < SIZE; ++i) {15 bc[i] = -1; // 初始化bc16 }1718for (int i = 0; i < m; ++i) {19int ascii = (int) b[i]; // 计算b[i]的ASCII值20 bc[ascii] = i;21 }22 }2324/**25 * 好后缀规则构建哈希表26 *27 * @param b28 * 模式串29 * @param m30 * 模式串长度31 * @param suffix32 * suffix数组的下标 k，表⽰后缀⼦串的长度，33 * 下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的⼦串{u*}的起始下标值34 * @param prefix35 * 记录模式串的后缀⼦串是否能匹配模式串的前缀⼦串36*/37private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {38for (int i = 0; i < m; ++i) { // 初始化39 suffix[i] = -1;40 prefix[i] = false;41 }4243for (int i = 0; i < m - 1; ++i) {44int j = i;45int k = 0; // 公共后缀⼦串长度46while (j >= 0 && b[j] == b[m - 1 - k]) { // 与b[0, m-1]求公共后缀⼦串47 --j;48 ++k;49 suffix[k] = j + 1; // j+1表⽰公共后缀在b[0，i]中的起始下标50 }51if (j == -1) {52 prefix[k] = true; // 如果公共后缀⼦串也是模式串的后缀⼦串53 }54 }55 }5657/**58 * 完整的BM算法好后缀+坏字符59 *60 * @param a61 * 主串62 * @param n63 * 主串的长度64 * @param b65 * 模式串66 * @param m67 * 模式串的长度68 * @return69*/70public int bm(char[] a, int n, char[] b, int m) {71int[] bc = new int[SIZE];72 generateBC(b, m, bc); // 构建坏字符哈希表73int[] suffix = new int[m];74boolean[] prefix = new boolean[m];75 generateGS(b, m, suffix, prefix); // 构建好字符哈希表76int i = 0; // j 表⽰主串与模式串匹配的第⼀个字符77while (i < n - m) {78int j = 0;79for (j = m - 1; j >= 0; --j) {// 模式串从后向前匹配80if (a[i + j] != b[j]) {81break; // 坏字符串82 }83 }84if (j < 0) {85return i;// 匹配成功，返回主串和模式串第⼀个匹配字符的位置86 }87int x = j - bc[(int) a[i + j]];88int y = 0;89if (j < m - 1) { // 如果有好后缀的话90 y = moveByGS(j, m, suffix, prefix);91 }92 i = i + Math.max(x, y);93 }94return -1;95 }9697private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {98int k = m - 1 - j; // 好后缀的长度99if (suffix[k] != -1) {100return j - suffix[k] + 1;101 }102for (int r = j + 2; r <= m - 1; ++r) {103if (prefix[m - r] == true) {104return r;105 }106 }107return m;108 }现在再看BM算法，原来之前⾃⼰是⼀点也没弄懂！只是当做⽂章简单读了⼀遍，阿西吧！⾸先，那个坏字符的散列表的构建就没有弄懂：1、为什么在散列表数组中要初始化每⼀个值为-1？这⾥是在坏字符匹配的时候，如果主串与模式串中字符没有匹配上（把坏字符在模式串中下标记做xi），此时的xi=-12、你有没有考虑过模式串中的相同的字符的ASCII码是相同的，那样循环处理的话，只是记录模式串中相同字符中最后⾯的那个字符的下标，没有问题吗？这个是没有问题的！这⾥⽆⾮有两种情况，就是坏字符与⾮坏字符：坏字符：因为是从后向前倒序匹配，只需要知道后⾯的字符下标，就可以计算出移动距离⾮坏字符：需要去寻找坏字符或者使⽤好后缀规则2019年11⽉14⽇15:34:37 修改此⼤部分内容来⾃极客时间专栏，王争⽼师的《数据结构与算法之美》极客时间：。

那些经典算法：字符串匹配算法BM算法单模式串匹配算法中BM（Boyer-Moore）算法算是很难理解的算法了，不过性能高效，据说比KMP算法性能提升3到4倍，suricata里面的单模式匹配就是用这种算法，所以有必要学习下，再把suricata的这部分代码过一下还是不错的。

一、BM算法原理BM算法是1975年发明的,它是一种后匹配算法，我们普通的字符串匹配算法是从左向右的，BM算法是从右向做的，即先判断模式串最后一个字符是否匹配，最后判断模式串第一个字符是否匹配。

原来我们在BF算法中，如果模式串和主串不匹配，则将主串或模式串后移一位继续匹配，BM算法根据模式串的特定规律，将后移一位的步子迈的更大一些，后移几位。

来看个图简单说明下，图来自《数据结构与算法之美》课程：但是如果我们仔细观察，c字符在abd中不存在，那么abd可以直接移动到主串中c字符的后面再继续匹配：这样移动的步数变大了，匹配起来肯定更快了。

BM算法根据模式串的特定规律，这里面的特定规律有两种，一种是好后缀规则，一种是坏字符规则，初次看到这种规则的介绍后，心里嘀咕着这性能会好吗，后面才发现经典的BM算法做了不少优化，所以性能高。

下面分别介绍下好后缀规则（good suffix shift）和坏字符规则（bad character rule）。

1.1 BM坏字符规则首先在BM算法里面何谓好坏那，匹配上的，我们称为好，匹配不上的叫坏。

按照刚才说的，BM算法是倒着匹配字符串的，我们在倒着匹配字符串的过程中，当我们发现某个字符没法匹配的时候，我们把主串中这个没法匹配的字符称为坏字符。

我们发现在模式串中，字符c是不存在的，所以可以直接将模式字符串向后滑动3位继续匹配。

滑动后，我们继续匹配，发现主串中的字符a和模式串的d不匹配，这时候的情况和上一种不一样，因为主串中的坏字符a在模式串中存在，则后移动2位，让主串和模式串中的a对齐继续匹配。

那么每次后移多少位那，我们假设把匹配不到的坏字符的位置记作si，如果坏字符在模式串中存在，则坏字符在模式串中的位置记作xi，那么模式串后移为si-xi；如果坏字符在模式串中不存在，xi就为-1。

一种基于双重分割的立体匹配算法一、导言介绍论文的研究背景和意义，阐述立体匹配的概念和发展历程，引出本文提出的基于双重分割的立体匹配算法。

二、相关研究综述介绍当前常用的立体匹配算法，对它们的优缺点进行比较分析，指出现有算法存在的问题和不足之处，说明本文提出的算法的创新性。

三、基于双重分割的立体匹配算法详细阐述本文提出的基于双重分割的立体匹配算法的原理和步骤，包括预处理、特征提取、灰度校正、匹配代价计算、视差优化等。

四、实验结果分析对提出的算法进行实验验证，比较其与现有算法的效果，包括视差图的质量、误差分析、算法的速度等方面，分析实验结果，并说明本文算法的优越性。

五、结论与展望总结本文所述内容，强调本文提出的算法的重要性和实用价值，并指出下一步的研究方向，为未来立体匹配算法的发展指明方向。

第1章节：导言随着计算机视觉的发展，立体视觉成为了研究的热点之一。

立体匹配是在两幅图像中找到对应像素点的过程，是实现立体视觉的关键环节。

立体匹配的准确性直接影响到计算机视觉应用的效果，因此引起了广泛的研究。

立体匹配的基本思路是将左右两幅图像进行比较，找到它们之间的对应关系。

然而，在实际应用中，如何准确地找到两幅图像中像素点的对应关系仍然是一个具有挑战性的问题。

单一的立体匹配算法难以解决所有场景下的匹配问题，而组合多种算法的复合立体匹配方法仍然存在计算复杂度高、精度低等问题。

因此，设计高效、精确的立体匹配算法至关重要。

本文以基于双重分割的立体匹配算法为例进行论述。

该算法基于分割和像素级别的特征匹配，结合了全局和局部的特征信息，从而实现了更准确的立体匹配。

本文的目的在于阐述立体视觉与立体匹配的基本概念，介绍立体匹配的发展历程，同时引出本文的研究问题。

本文的结构为：第1章导言，主要介绍论文的研究背景和目的；第2章相关研究综述，介绍当前常用的立体匹配算法的特点和一些存在的不足；第3章基于双重分割的立体匹配算法，详细阐述本文所提出的算法的原理和具体实现过程；第4章实验结果分析，通过实验验证本文所提算法的有效性，并比较其与其他算法的效果；第5章结论与展望，总结本文所述内容，指出研究的局限性及未来的发展方向。

⽴体匹配算法转载请注明出处：⽴体匹配算法最新动态：相关⽂献：介绍⽴体匹配的基本原理:⽴体匹配综述性⽂章：⽴体匹配算法的基本⽬标：找出图像的每个像素点在另⼀个视⾓的图像上对应的像素点，算出视差图像，估算出景深图像。

最简单的SAD块匹配算法//Stereo Match By SAD#include <opencv2/opencv.hpp>#include <vector>#include <algorithm>#include <iostream>#include <windows.h>#include <string>using namespace std;using namespace cv;DWORD t1;DWORD t2;void timebegin(){t1 = GetTickCount();}void timeend(string str){t2 = GetTickCount();cout << str << " is "<< (t2 - t1)/1000 << "s" << endl;}float sadvalue(const Mat &src1, const Mat &src2){Mat matdiff = cv::abs(src1 -src2);int saddiff = cv::sum(matdiff)[0];return saddiff;}float GetMinSadIndex(std::vector<float> &sad){float minsad = sad[0];int index = 0;int len = sad.size();for (int i = 1; i < len; ++i){if (sad[i] < minsad){minsad = sad[i];index = i;}}return index;}void MatDataNormal(const Mat &src, Mat &dst){normalize(src, dst, 255, 0, NORM_MINMAX );dst.convertTo(dst, CV_8UC1);}void GetPointDepthRight(Mat &disparity, const Mat &leftimg, const Mat &rightimg,const int MaxDisparity, const int winsize){int row = leftimg.rows;int col = leftimg.cols;if (leftimg.channels() == 3 && rightimg.channels() == 3){cvtColor(leftimg, leftimg, CV_BGR2GRAY);cvtColor(rightimg, rightimg, CV_BGR2GRAY);}//Mat disparity = Mat ::zeros(row,col, CV_32S);int w = winsize;int rowrange = row - w;int colrange = col - w - MaxDisparity;for (int i = w; i < rowrange; ++i){int *ptr = disparity.ptr<int>(i);for (int j = w; j < colrange; ++j){//Rect rightrect;Mat rightwin = rightimg(Range(i - w,i + w + 1),Range(j - w,j + w + 1));std::vector<float> sad(MaxDisparity);for (int d = j; d < j + MaxDisparity; ++d){//Rect leftrect;Mat leftwin = leftimg(Range(i - w,i + w + 1),Range(d - w,d + w + 1));sad[d - j] = sadvalue(leftwin, rightwin);}*(ptr + j) = GetMinSadIndex(sad);}}}void GetPointDepthLeft(Mat &disparity, const Mat &leftimg, const Mat &rightimg,const int MaxDisparity, const int winsize){int row = leftimg.rows;int col = leftimg.cols;if (leftimg.channels() == 3 && rightimg.channels() == 3){cvtColor(leftimg, leftimg, CV_BGR2GRAY);cvtColor(rightimg, rightimg, CV_BGR2GRAY);}//Mat disparity = Mat ::zeros(row,col, CV_32S);int w = winsize;int rowrange = row - w;int colrange = col - w;for (int i = w; i < rowrange; ++i){int *ptr = disparity.ptr<int>(i);for (int j = MaxDisparity + w; j < colrange; ++j){//Rect leftrect;Mat leftwin = leftimg(Range(i - w,i + w + 1),Range(j - w,j + w + 1));std::vector<float> sad(MaxDisparity);for (int d = j; d > j - MaxDisparity; --d){//Rect rightrect;Mat rightwin = rightimg(Range(i - w,i + w + 1),Range(d - w,d + w + 1));sad[j - d] = sadvalue(leftwin, rightwin);}*(ptr + j) = GetMinSadIndex(sad);}}}//(Left-Right Consistency (LRC)void CrossCheckDiaparity(const Mat &leftdisp, const Mat &rightdisp, Mat &lastdisp,const int MaxDisparity, const int winsize){int row = leftdisp.rows;int col = rightdisp.cols;int w = winsize;int rowrange = row - w;int colrange = col - MaxDisparity - w;int diffthreshold = 2;for (int i = w; i < row -w; ++i){const int *ptrleft = leftdisp.ptr<int>(i);const int *ptrright = rightdisp.ptr<int>(i);int *ptrdisp = lastdisp.ptr<int>(i);for (int j = MaxDisparity + w; j < col - MaxDisparity - w; ++j){int leftvalue = *(ptrleft + j);int rightvalue = *(ptrright + j - leftvalue );int diff = abs(leftvalue - rightvalue);if (diff > diffthreshold){*(ptrdisp + j) = 0;}else{*(ptrdisp + j) = leftvalue;}}}}int main(){Mat leftimg = imread("left1.png",0);Mat rightimg = imread("right1.png",0);if (leftimg.channels() == 3 && rightimg.channels() == 3){cvtColor(leftimg, leftimg, CV_BGR2GRAY);cvtColor(rightimg, rightimg, CV_BGR2GRAY);}float scale = 1;int row = leftimg.rows * scale;int col = leftimg.cols * scale;resize(leftimg, leftimg, Size( col, row));resize(rightimg,rightimg, Size(col, row));Mat depthleft = Mat ::zeros(row,col, CV_32S);Mat depthright = Mat ::zeros(row,col, CV_32S);Mat lastdisp = Mat ::zeros(row,col, CV_32S);int MaxDisparity = 60 * scale;int winsize = 31*scale;timebegin();GetPointDepthLeft(depthleft, leftimg, rightimg, MaxDisparity, winsize);GetPointDepthRight(depthright, leftimg, rightimg, MaxDisparity, winsize);CrossCheckDiaparity(depthleft,depthright, lastdisp, MaxDisparity, winsize);timeend("time ");MatDataNormal(depthleft,depthleft);MatDataNormal(depthright, depthright);MatDataNormal(lastdisp, lastdisp);namedWindow("left", 0);namedWindow("right", 0);namedWindow("depthleft", 0);namedWindow("depthright", 0);namedWindow("lastdisp",0);imshow("left", leftimg);imshow("right", rightimg);imshow("depthleft", depthleft);imshow("depthright", depthright);imshow("lastdisp",lastdisp);string strsave = "result_";imwrite(strsave +"depthleft.jpg", depthleft);imwrite(strsave +"depthright.jpg", depthright);imwrite(strsave +"lastdisp.jpg",lastdisp);waitKey(0);return0;} left.png right.png left1_depthleft.jpg right1_depthleft.jpg lastdispOpenCv中实现了三种⽴体匹配算法：BM算法SGBM算法 Stereo Processing by Semiglobal Matching and Mutual InformationGC算法算法⽂献：Realistic CG Stereo Image Dataset with Ground Truth Disparity Maps参考：BM算法：速度很快，效果⼀般void BM(){ IplImage * img1 = cvLoadImage("left.png",0);IplImage * img2 = cvLoadImage("right.png",0);CvStereoBMState* BMState=cvCreateStereoBMState();assert(BMState);BMState->preFilterSize=9;BMState->preFilterCap=31;BMState->SADWindowSize=15;BMState->minDisparity=0;BMState->numberOfDisparities=64;BMState->textureThreshold=10;BMState->uniquenessRatio=15;BMState->speckleWindowSize=100;BMState->speckleRange=32;BMState->disp12MaxDiff=1;CvMat* disp=cvCreateMat(img1->height,img1->width,CV_16S);CvMat* vdisp=cvCreateMat(img1->height,img1->width,CV_8U);int64 t=getTickCount();cvFindStereoCorrespondenceBM(img1,img2,disp,BMState);t=getTickCount()-t;cout<<"Time elapsed:"<<t*1000/getTickFrequency()<<endl;cvSave("disp.xml",disp);cvNormalize(disp,vdisp,0,255,CV_MINMAX);cvNamedWindow("BM_disparity",0);cvShowImage("BM_disparity",vdisp);cvWaitKey(0);//cvSaveImage("cones\\BM_disparity.png",vdisp);cvReleaseMat(&disp);cvReleaseMat(&vdisp);cvDestroyWindow("BM_disparity");} left.png right.png disparity.jpgSGBM算法，作为⼀种全局匹配算法，⽴体匹配的效果明显好于局部匹配算法，但是同时复杂度上也要远远⼤于局部匹配算法。

⽴体匹配算法⼀、⽴体匹配算法的分类在⽴体匹配中，匹配问题可以看成是寻找两组数据相关程度的过程。

⽴体匹配算法由多种分类。

①根据算法运⾏时约束的作⽤范围：分为局部（local）匹配算法和全局（Global）匹配算法。

②基于⽣成的视差图：可分为稠密（Dense）匹配和稀疏（Sparse）匹配。

稠密匹配：是基于⽣成的视差图，对于所有像素都能⽣成确定视差值，称为稠密匹配。

稀疏匹配：只选择关键像素点[通常为⾓点或者边缘点]计算视差值的⽅法称为稀疏匹配，该算法计算速度较快，但后续还需要通过插值算法计算缺失像素点的视差值，因此应⽤场景上有很⼤限制。

由于⾃⼰最近研究主要集中于局部匹配算法和全局匹配算法，因此以下也将针对此处描述下。

1、全局匹配算法全局（半全局）⽴体匹配算法主要是采⽤了全局的优化理论⽅法估计视差，建⽴⼀个全局能量函数，其包含⼀个数据项和平滑项，通过最⼩化全局能量函数得到最优的视差值。

其中，图割(Graph cuts， GC）、置信传播（Belief Propagation，BP）、动态规划（Dynamic Programming,DP）,粒⼦群算法（Particle Swarm Optimization,PSO）、遗传算法（Genetic Algorithm，GA）等优化算法都是常⽤的求解能量最⼩化的⽅法。

全局匹配算法⼀般定义如下能量函数：其中数据项描述了匹配程度，平滑项体现了定义场景的约束，C是匹配代价，P是不同两像素p和q视差的函数，⼀般称之为惩罚项（penalty），当p点和q点视差不相等时，P>0，且与两者差值越⼤，P值越⼤。

当p和q视差相等时，P=0。

由于全局匹配算法在数学上是⼀个能量函数的优化问题，因此可以找到最优解。

这个问题被证明在⼆维空间是NP困难的。

因此，即使全局算法具有准确性较⾼的优点，其计算速度确⾮常慢，在实时性要求⾼的场合不适合使⽤全局⽴体匹配算法。

考虑到能量优化问题在⼀维空间的复杂度是多项式级的，因此⼀些研究试图做⼀些近似来降低算法的复杂度。

BM算法详解及Java实现1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。

该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。

在实践中，比KMP算法的实际效能高。

一、后缀暴力匹配算法后缀匹配，是指模式串的比较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀暴力匹配算法的改进。

所以还是先从最简单的后缀暴力匹配算法开始。

下面直接给出伪代码，注意这一行代码：j++；BM算法所做的唯一的事情就是改进了这行代码，即模式串不是每次移动一步，而是根据已经匹配的后缀信息，从而移动更多的距离。

/*** 后缀暴力匹配** @param T 正文字符数组* @param P 模式字符数组* @return匹配位置*/public static int bf(char[] T, char[] P) {for (int j = 0; j <= T.length - P.length; j++) {int i = P.length - 1;for (; i >= 0 && P[i] == T[i + j]; --i) {}if (i < 0) {return j;}}return -1;}二、BM算法介绍为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利用好后缀和坏字符可以大大加快模式串的移动距离，不是简单的++j，而是j+=max (shift(好后缀), shift(坏字符))。

下面举例说明BM算法。

例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

1. 首先，"文本串"与"模式串"头部对齐，从尾部开始比较。

BM字符串匹配算法字符串匹配是一种常见的操作，可以用来判断一个字符串中是否包含另一个字符串。

比如在搜索引擎中输入一个关键字，搜索引擎会根据关键字在文本中匹配相似的内容。

在编程中，字符串匹配也是一种常见的操作。

BM字符串匹配算法是一种高效的字符串匹配算法，本文将介绍BM算法的原理、优化和应用场景。

BM字符串匹配算法的原理BM字符串匹配算法是由Boyer和Moore两个人于1977年提出的，它是一种模式匹配算法，用于在一个主串中查找一个模式串的出现位置。

BM算法是一种启发式算法，它利用了在主串中匹配失败时，模式串能够“跳过”一些已经匹配的字符的特点，从而提高匹配的效率。

BM算法的核心思想是利用两个规则：坏字符规则和好后缀规则。

坏字符规则是指如果在匹配过程中发现不匹配，就找到主串中与模式串中不匹配的那个字符相同的最右位置，将模式串向右滑动这个位置。

而好后缀规则是指如果在匹配过程中发现不匹配的位置包含一个好后缀，就将模式串向右滑动这个好后缀和主串中和它匹配的最靠右的模式串位置对齐。

BM算法的优化BM算法在实际应用中可以进一步优化。

其中一种优化是使用哈希表。

在坏字符规则中，每次需要在主串中找到不匹配的字符，在O(n)的时间复杂度内搜索。

如果主串中出现了大量相同的字符，那么哈希表可以大大减少搜索的时间。

哈希表将字符映射到桶中，桶中存储的是出现该字符的最右位置，这样就可以在O(1)的时间复杂度内找到该字符出现的最右位置。

另一种优化是使用suffix数组。

suffix数组是一个字符串排序之后的结果，它可以用于快速查找当前位置后面的所有后缀。

在好后缀规则中，需要找到与好后缀相匹配的子串，然后滑动这个子串到最右位置。

如果每次都从当前位置开始往后搜索，时间复杂度是很高的。

而使用suffix数组可以快速查找到所有与好后缀匹配的子串，然后选择离当前位置最远的那个子串进行滑动，这样可以大大提高匹配的效率。

BM算法的应用场景BM算法的应用场景非常广泛，比如在文本编辑器中查找某个单词、在搜索引擎中根据关键字搜索相似文章、在代码中查找某个变量或函数等等。

BM算法详解/joylnwang/article/details/67857432011.091977年，Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内，完成字符串匹配的算法，其在绝大多数场合的性能表现，比KMP算法还要出色，下面我们就来详细了解一下这一出色的单模式匹配算法，在此之前推荐读者读一下我的另一篇文章《KMP 算法详解》，对于透彻理解BM算法大有裨益。

在讲解Boyer-Moore算法之前，我们还是要提一提KMP算法的老例子，当模式串与目标串匹配至如下位置时：我们发现target[13]!=pattern[7]，此时根据KMP算法的next值，我们将target[13]与pattern[5]对齐，再依次执行匹配。

这里target[13]='a'。

如果target[13]='d'，因为'd'不是模式串pattern中的字符，所以无论将target[13]与pattern中任何一个字符对齐都会匹配失败，所以当我们在匹配过程中发现target[i]是不属于模式串的字符，则我们可以直接将target[i+1]，与pattern[1]对齐，再向后执行匹配。

这样就获得了更大的跳转幅度，同时也能保证匹配的正确性。

这便是BM算法相较于KMP算法的一个重要改进。

BM算法之所以能够在单模式匹配中有更加出色的表现，主要是其使用了两个跳转表，一个是坏字符表（论文中称为delta1），一个是好后缀表（论文中称为delta2），下面我们以BM算法对目标串的一次匹配操作，来讲解这两个表的具体跳转策略，这里模式串为"AT-THAT"，目标串为"WHICH-FINALLY-HALTS.--AT-THAT-POINT"。

BM算法与KMP算法的最大的不同之处在于，当目标串与模式串在某个位置对齐之后，KMP算法是从对齐位置向后依次执行匹配（不一定是模式串的第一个元素）。