快速MSER算法的改进及性能提升

33800Fast MSER0Hailiang Xu 1 , 2 � , Siqi Xie 3 , Fan Chen 401 阿里巴巴集团  2 南京大学  3 北京语言文化大学  4 哥伦比亚大学0xhl0student@163.com, coderxiesiqi1996@126.com, fc2484@columbia.edu0摘要0最大稳定极值区域（MSER）算法基于组件树，用于检测不变区域。OpenCVMSER是最流行的MSER实现，它使用链表将像素与ER关联起来。ER的数据结构包含头部和尾部链接节点的属性，这使得OpenCVMSER难以使用现有的并行组件树策略进行并行处理。此外，OpenCVMSER中的像素提取（即提取MSER中的像素）非常慢。在本文中，我们提出了两种新颖的MSER算法，称为FastMSERV1和V2。它们首先将图像分成几个空间分区，然后在分区上并行构建子树和双向链表（对于V1）或标记图像（对于V2）。V1使用一种新颖的子树合并算法将子树合并为最终树，并在过程中合并双向链表。而V2使用现有的合并算法合并子树。最后，通过利用父子MSER中大量重复的像素，通过两种新颖的像素提取方法识别MSER并提取其中的像素。V1和V2都优于三个开源MSER算法（比OpenCVMSER快28倍和26倍），并将MSER中的像素内存减少了78%。01. 引言0不变区域提取[36, 21, 14, 17, 42, 4, 32, 31, 34, 43, 5, 18,6,3]已广泛应用于大规模图像检索任务、目标检测和识别、目标跟踪和视图匹配。最大稳定极值区域（MSER）算法由Matas等人发明[20]，并由Nister等人进行了优化[28]。它构建了一个组件树[33,24]，从树中识别MSER，并提取MSER中的像素。我们将这三个步骤称为组件树构建、MSER识别和像素提取。需要注意的是，一些任务，如宽基线01 本研究是一项业余研究。HailiangXu在阿里巴巴集团工作期间（利用业余时间）完成了部分工作。0立体声不需要像素提取。树中的每个节点都是一个极值区域（ER），其特点是ER内部的像素比其外边缘的像素更亮（亮ER）或更暗（暗ER）。MSER是一种在一系列灰度阈值下稳定的ER。MSER算法分为两个不同的步骤：从暗到亮的步骤（检测暗MSER）和从亮到暗的步骤（检测亮MSER）。它已经被应用于宽基线立体匹配[20, 10,19]、大规模图像检索[27]、目标跟踪[8]、目标识别[29]和场景文本检测[46, 13, 26, 25, 45, 44,12]。它已经扩展到彩色图像[9]、体积图像[7]、1-D图像[41]并在FPGA上进行了优化[16]。0MSER算法需要较低的计算资源（适用于嵌入式设备和手机），并且在小训练数据上表现良好（MSER特征是高级手工特征）。尽管深度学习技术在学术领域非常流行，但MSER算法仍然在工业任务中活跃，如立体匹配（可能与SIFT、SURF和ORB特征描述符结合使用）、文档文本处理和交通标志检测等。我们还可以使用MSER算法分析热图，即找到热度超过一定阈值的区域。因此，MSER算法需要运行非常快，并且使用较少的内存（考虑到嵌入式设备和手机的相对较小内存）。此外，MSER算法的一些优化技术可以扩展到其他组件树算法。并行策略[39,23]已被提出来加速基于组件树的算法。它们将图像分成几个分区。使用子树合并算法[39]在所有分区上并行构建子树。子树合并算法可以正确累积每个树节点的属性（属性必须足够简单以便累积，例如区域的面积）。我们将这种分区并行策略称为分区并行策略。Moschini等人[23]描述了两种分区策略：空间分区和强度分区，如图1所示。强度分区适用于按灰度级排序的像素的算法[23]。0图2显示了分区和通道的比较1112222223334555T1T2T3T4T1T2T3T42215233513415222MemoryMemoryMemoryMemoryMemoryMemoryReuseT1T2T4T3T1T2T3T4T1P2T3P4T1T2T3T4T1T2T3T4MemoryMemoryReuseReuse(a) Channel parallel(b) Partition parallelTi: thread iFour colors denote R, G, B and gray-scale channels111222333ER 5ER 6ER 1ER 2ER 3ER 4Linked listHead nodeTail node246135566(b) CV-MSER(c) Fast MSER V2ER 62ER 41ER 11ER 21ER 3ER 51231122331122(b) CV-MSER(c) Fast MSER V1(a)Linked listMSER 1MSER 2MSER 3MSER 4MSER 5MSER 6MSER 6MSER 5MSER 4MSER 2MSER 1MSER 3Record begin and end indexes:MSER 1: 0,2 MSER 2: 3,4MSER 3: 5,5 MSER 4: 6,7MSER 5: 0,4 MSER 6: 5,7Pixels in top MSERs:ER 1ER 2ER 3ER 1ER 3ER 1ER 2ER 333810Ti: 线程i像素被排序0图1. 左：空间分区。右：强度分区。0图2.通道并行算法同时处理4个通道，因此分配4个内存块。然而，分区并行算法只分配1个内存块（该内存将在所有分区中重复使用）。0(a) 6个暗ER0源图像0标记的图像0图3. (a) 6个暗ER。(b)CV-MSER从源图像生成一个链表。ER的数据结构包含一个头部和一个尾部链接节点。在Fast MSERV1中，链表是一个双向链表。(c) Fast MSERV2使用一个标记的图像，其中每个像素记录相应的MSER索引。0并行策略。由于分区并行算法使用的运行内存较少，比通道并行算法更少，我们关注分区并行策略。MSER算法可以分为两类：标准MSER [20]和线性MSER[28]。标准MSER在像素数量上几乎是线性时间，而线性MSER则需要真正的最坏情况线性时间。VLFeatMSER（VF-MSER）[37]是标准MSER。它在分水岭分割任务中使用了众所周知的泛洪模拟算法[38]的方式，并且可以很容易地在分区并行中使用[39]中的合并算法。由于VL-MSER首先对像素进行排序，因此适用于强度分区。IdiapMSER（ID-MSER）[2]是线性MSER。通过使用不同的像素计算顺序，它使用的内存明显较少，并且具有更好的缓存局部性（适用于强度分区），从而实现更快的执行。它们都没有实现像素提取，只能计算容易累积的矩特征。无法提取更复杂的特征，如骨架[11]。OpenCVMSER（CV-MSER）[1]是另一种线性MSER算法，其过程如图7所示。计算0图4. (a) 识别出6个MSER。(b)CV-MSER独立提取6个MSER中的像素。MSER1、2和3中的像素在其父MSER 5和6中被重复提取。(c) Fast MSERV1首先将这些顶级MSER（没有父MSER）中的像素存储在一块连续内存中。然后，所有MSER在连续内存中记录开始和结束索引。所有像素只被提取一次。0(a) CV-MSER (b) Fast MSER V1和V20绿色ER被识别为MSER0计算像素的总数并为所有MSER分配一块连续内存0像素提取 像素提取0像素提取 像素提取0为每个识别出的MSER分配一块连续内存0图5. (a) 在将ER识别为MSER后立即进行像素提取。(b)V1和V2首先完成MSER识别，然后提取MSER中的像素。在FastMSER中释放一块连续内存比在CV-MSER中释放多块连续内存更快。0MSER的复杂特征，它提取了每个MSER中的像素，并将像素存储在一个链表中，该链表包含头部和尾部节点的属性（参见图3（b））。它成功地提取了像素，但没有利用父子MSER之间的关系，从而降低了提取速度，参见图4（b）。此外，CV-MSER与分区并行策略不兼容，因为链接节点的属性无法通过[39]中的合并算法进行累积。限制执行速度的另一个主要缺陷是CV-MSER没有分配一块连续内存来存储像素，从而减慢了内存释放速度，参见图5（a）。Fast MSERV1.由于MSER中的像素也属于其父MSER，因此MSER中的像素可以被其父MSER共享。通过使用链表，我们可以显著加速像素提取，如图4所示。因此，我们希望通过访问链表来提取像素。为了合并子树并正确更新链接节点的属性，我们需要将链表断开为子列表，并在一定条件下合并子列表。因此，双向链表可能会有用。此外，为所有MSER中存储的像素释放一块连续内存非常快速（参见图5（b））。受此启发，我们提出了Fast MSER V1，它MSER 62MSER 41MSER 11MSER 21MSER 3MSER 51231122331122MSER 62ER 4111MSER 5123112233112251432MSER 1MSER 2MSER 333820(a) CV-MSER (b) Fast MSER V20图6.我们假设像素和索引的内存为1字节。红色像素中的数字表示MSER索引，而绿色和灰色像素中的数字表示灰度级别。 (a)中的绿色像素通过访问链表直接提取。在 (b) 中，MSER R中的像素被分为子像素（属于 R和其子MSERs，例如灰色像素）和自身像素（仅属于 R，例如绿色像素）。首先通过访问标记图像提取自身像素（绿色像素）。我们存储子MSERs的索引（红色像素），而不是提取子MSERs中的像素（灰色像素）。请注意，像素在 (a)中被提取了三次，而在 (b)中只被提取了一次。V2减少了访问次数，从而使像素提取更快。此外，(a) 中ER 6 的内存大小为9字节，而 (b)中为9字节（三个像素和三个MSER索引）。V2压缩了ER 6的内存。然而，MSER 5的内存未压缩，因为其两个子区域的面积是1的小值（等于一个MSER索引的大小）。0在多个图像分区上并行形成，减少像素提取时间、内存释放时间和MSERs中像素的内存。如图7所示，V1首先将图像分成空间分区。然后在分区上并行构建子树和双向链表。使用一种新型的子树合并算法将子树合并成最终的树，并在此过程中合并双向链表。链接节点的属性可以正确更新。最后，识别MSERs，并通过一种新型的像素提取方法（参见图4(c)）在分区并行中提取其中的像素。Fast MSERV2。连接组件算法使用图像标记组件索引，然后提取每个组件中的像素。此外，由于MSER中的像素也属于其父MSER，因此R中的像素可以由父ER共享，参见图6。受此启发，我们提出了Fast MSERV2，其遵循与V1相同的流程。然而，V2使用标记图像（参见图3(c)）而不是链表来构建子树，从而更容易地使用现有的子树合并算法合并子树。此外，V2使用一种新型的像素提取方法（参见图6(b)）加速像素提取。V1和V2都可以显著加速MSER提取并减少MSERs中像素的内存。我们的贡献总结为三个方面：01组件树构建、MSER识别和像素提取在V1和V2中都是分区并行的。作为分区并行算法，V1和V2使用0(d) 组件树构建0(e)MSER识别0(f) 像素提取0(a) 算法初始化 (b) MSER检测0CV-MSER0Fast MSER V104个阶段：c-f0算法内存0(c) 算法初始化0算法内存0组件树构建和MSER识别 像素提取0链表0分区1中的双向链表和树0分区2中的双向链表和树0合并02个阶段：a，b0图7. CV-MSER和Fast MSER V1的比较。CV-MSER (a)分配所需的内存，(b)构建组件树并识别MSERs（左侧），提取MSERs中的像素（右侧）。V1将输入图像分成多个分区，(c) 分配所需的内存，(d)使用我们的新型子树合并算法在分区中构建组件树，(e)识别MSERs并 (f)使用我们的新型像素提取方法提取像素。请注意，V2与V1类似，但消除了链表。0比通道并行算法使用更少的内存。请注意，它们在没有同步机制的情况下工作。我们的代码已在[40]上公开。在V1中，提出了一种新颖的子树合并算法，用于合并所有分区上产生的子树。ER的数据结构中的链接节点的属性可以被正确更新。V1和V2分别提出了两种新颖的像素提取方法，以加速像素提取和内存释放，并减少MSER中像素的内存大小。02. 相关工作0标准MSER [20]首先使用BINSORT按灰度级对图像中的像素进行排序。计算复杂度为O（N），其中N是像素数量。然后应用高效的并查集算法[35]来获取组件树。并查集的复杂度是准线性的。最后，将在一定灰度范围内最稳定的ER视为MSER。标准MSER的一些性能优化技术可以在[30]中找到。VF-MSER [37]是标准MSER。它可以通过合并算法[39]在分区并行中轻松执行。然而，VF-MSER比线性MSER慢得多。此外，它不实现像素提取。因此，这种复杂特征（骨架[11]）无法被提取。而我们的算法中的组件树构建与线性MSER中的相似，并且我们的算法可以提取MSER中的像素。33830线性MSER [28]表现得像真正的泛洪填充，提供与标准MSER完全相同的结果，并且在像素数量上花费线性时间。通过与单个像素的连通分量一起工作，线性MSER使用更少的运行内存并具有更好的缓存局部性。因此，线性MSER比标准MSER快得多。ID-MSER和CV-MSER都是线性MSER。对于ID-MSER，它不实现像素提取。此外，ER的数据结构包含一个大小为5的双数组，用于存储矩特征。只有MSER在后续过程中使用矩特征。因此，矩特征浪费了大量的运行内存，因为只有少量的ER（1%）可以被识别为MSER。CV-MSER包含算法初始化和MSER检测步骤（见图7）。ER的数据结构包含链接列表中的头节点和尾节点的属性。CV-MSER可以通过访问链接列表来提取MSER中的像素。然而，它不能并行执行，因为合并算法无法累积链接节点的属性[39]。此外，CV-MSER中的像素提取和内存释放非常慢，如图5（a）和图4（b）所示。与CV-MSER不同，Fast MSERV1使用双向链表而不是链表来合并子树并正确更新链接节点的属性，并使用一种新颖的子树合并算法。而V2在ER的数据结构中消除了链接节点的属性，并使用标记图像（每个像素记录其对应的ER索引）。V2可以通过使用子树合并算法在分区并行中轻松执行。V1和V2将CV-MSER中的MSER检测分为三个顺序状态：组件树构建、MSER识别和像素提取（见图7）。在MSER识别中计算MSER的总内存大小，因此可以在像素提取之前分配连续的内存（见图5（b））。此外，V1只提取顶部MSER中的像素（见图4（c）），而V2只直接提取MSER中的自身像素（见图6（b））。03. 快速MSER V10为了简单起见，我们以从暗到亮的过程作为介绍V1的示例。图7显示了V1的四个阶段。我们在以下几节中介绍它们。03.1. 算法初始化0我们定义了5种数据结构：1）ER数组。ER的数据结构包含灰度级、面积、父节点指针、变异性、分区索引、头尾链接节点；2）像素数组。每个条目包含灰度级和可访问像素的二进制掩码；3）双向链表。每个节点包含4个变量：对应像素的坐标，指向前一个条目的索引，指向0到下一个条目和引用索引（用于我们的子树合并算法）；4）边界像素的优先级队列[28]；5）组件堆栈[28]。数据结构1在组件树构建中动态分配。数据结构5中的条目数等于灰度级别（256）的数量。其他数据结构的大小为N（像素数）。每个数据结构的内存被分成P个分区，其中P等于线程数。03.2.组件树构建0我们将图像分成P个分区，然后并行在分区上构建P个组件树（子树）。每个分区上的树构建类似于CV-MSER。请注意，我们使用双向链表，而CV-MSER使用单向链表。最后，所有子树合并为最终树。例如，在图8中，树1和2被合并（每次合并两棵树），树3和4也被合并。然后我们合并由前面的合并过程生成的两棵新树。具体来说，对于树1和2，我们得到与绿色相邻像素对应的每个ER对，然后使用算法1将它们连接起来。我们合并算法中的一些重要符号是：split0par：确定ER属于哪个分区；chg：0表示此连接没有更改；merged0set：记录已更改的节点；discon0ers：记录已从原始链表中删除的ERs；parent[s]，gray[s]，area[s]，t0area[s]：ER s的父节点、灰度级别、面积和临时面积（用于过程ChangeNode）。parent[s]=⊥表示s没有父节点；head[a]，tail[a]：ER a的头节点和尾节点；next[n]，prev[n]，ref[n]：节点n的下一个索引、上一个索引和引用索引。在图9中，在连接ER1和4（它们相邻）的过程中，我们将ER1的父节点更改为ER 4。这里的关键问题是如何更新ER1和4的数据结构中链接节点的属性。由于链接节点的属性无法累积，现有的合并算法无法处理这个问题。在我们的合并算法中，我们断开（参见算法2）与ER1和4对应的双向链表的部分（参见图9（b）），从而得到一个新的链表。在算法1中的后续合并过程中，其他链接节点将连接到新的链表上。请注意，在断开过程之后，ER2和3的真实尾节点是灰色节点（real0tail）与灰度级别为3的灰色节点相连。然而，ER2和3的数据结构中尾节点的属性仍然是黄色节点（tail）01）与灰度级别为1的灰色节点相连。因此，我们设置tail的引用索引，参见算法2中的第12行。为0ER 12 P1232514153413ER 5ER 7ER 821523ER 2ER 3ER 42222225ER 9ER 10ER 13123122ER 1143332243143322(a) Two partitions13432214332235121523132512353251152312125533152351321212553315235132̸̸̸33840（a）（b）0P20树2 树3 树40P3 P4 树10ER 20图8.（a）一个4×4的图像被分成4个分区。（b）在4个分区上构建的4个子树。绿色像素与其他分区相邻。数字表示灰度级别。0ER 30（d）连接ER 1和4 1的结果0ER 1 ER 40ER 1 ER 20（b）两个链表0ER 40ER 30ER 50（c）两个组件树0更改父节点。0通过断开与ER1和4相对应的链表部分，并将ER1的父节点更改为ER 4，生成的新链表。0ER 1。0ER 2。0ER 3。0ER 4。0ER 5。0ER 2。0ER 3。0ER 1。0ER 4。0ER 5。0图9。为了连接ER 1和4，我们断开与它们相对应的链表部分，并将ER1的父节点更改为ER 4。0(c) 组件树 (b) 双向链表。0左分区：0右分区：0(a) 两个分区。0图10。如果我们先合并顶部的一对，然后合并底部的一对，那么链表将被修改两次。然而，如果我们先合并底部，其他的合并就不需要了（组件树和链表已经是最终结果）。0最小灰度级在一对中的最大值）。换句话说，灰度级较低的ER对将首先被合并。0算法1 连接两个ER。01:  过程  连接ER ( s, b, split。0par )。0set  ← {} 3:  while  s  � = ⊥  do。04: if  b  � = ⊥  and  gray  [ s ]  > gray  [ b ]  then。05: 交换s和b  end if 6: sp  ←LevelRoot ( parent [ s ] )。07: if  sp  =  b  and  chg  = 1  then  Break loop  end if。08: if  b  = ⊥  then 9: ProcessSmall ( s, sp ) ;s  ←  sp ;  chg  ←  1。010: else 11: bp  ←  LevelRoot (parent [ b ] )。012: if  gray[s] = gray[b]  or  sp  = ⊥  or  gray [ sp ]  >gray [ b ]  then 13: for  r  ∈ { s, b }  do。014: if  discon。0ers  [ Index  ( r )]  � =  r  then。0set )  // 见算法2 16: discon。0ers  [ Index  ( r )]  ←  s。017: end if 18: endfor。019: ChangeNode ( b, s )  // 见算法2。020: parent [ s ]  ←  b ;  s  ←  b ;  b  ←  sp ;  chg←  1 21: else。022: ProcessSmall ( s, sp ) ;  s  ←  sp ;  chg  ←  1。023: end if 24:end if。025: 结束循环 26: ref [ node ]  ←⊥，其中node ∈ merged。0set。03.3. MSER识别。0我们使用4个规则来识别MSERs：1）面积在[min0p]的范围内；2）它的变异性小于var是稳定的；3）它是最大稳定的；4）它明显大于其子MSERs的1 + dvar倍。0在规则2中，我们使用δ来计算ER的变异性var。var定义为var = | R (+ δ ) |−| R |。0| R | [37, 2]，其中| R |表示ER R的面积，R (+ δ)是包含R的ER + δ级别，| R  +  δ | − | R|是两个区域的面积差异。我们首先计算所有ER的变异性，并同时应用规则1和2以并行过滤ER。规则3和4不能同时应用，因为同时使用了父节点和子节点信息。03.4. 像素提取。0一旦识别出MSERs，我们首先通过并行访问双向链表提取顶部MSERs中的像素（参见图4(c)）。提取的像素存储在连续内存块中。然后，每个MSER在连续内存中记录开始和结束索引。set)̸̸̸20:̸̸4. Fast MSER V233850算法2 帮助函数。01: procedure Disconnect(a, merged0tail ← RealTail(tail[a]) 3: ifprev[head[a]] ≠ ⊥ then04: next[prev[head[a]]] ← next[real0tail] end if0tail] ≠ ⊥ then 6:prev[next[real0tail]] ← prev[head[a]] end if07: p ← LevelRoot(parent[a])08: if p ≠ ⊥then 9: p0tail ← RealTail(tail[p])0area[a] 11: if tail[a] = tail[p] or p0tail = real0tail then012: ref[real0tail] ← prev[head[a]]0set end if 14: end if015: tail[r] ← real0tail; prev[head[r]], next[tail[r]] ←⊥016: 17: procedureLevelRoot(r)018: while gray[parent[r]] = gray[r] do r ← parent[r]19: end while return r021: procedure ChangeNode(a, b) 22: next[tail[a]] ←head[b]; prev[head[b]] ← tail[a]023: tail[a] ← tail[b]0area[a] ← area[a] 25:026: procedure ProcessSmall(s, sp)0ers[Index(s)] = s then 28: Disconnect(sp); discon0ers[Index(s)] ← s029: ChangeNode(sp, s) end if 30:031: procedure RealTail(a)032: while ref[a] ≠ ⊥ do a ← ref[a] end while return a 33:034: procedure Index(a, split0par )035: return partition[a] < split0par ? 0 : 10Fast MSER V2与Fast MSERV1在两个方面有所不同（有关V2的更多细节可以在我们的代码中找到）。首先，V2使用了一个标记图像而不是一个链表（ER的数据结构不包含链接节点），从而可以轻松地使用合并算法[39]合并子树。其次，V2首先通过访问标记图像将自身像素的坐标（参见图6）添加到它们对应的MSER中（这个过程可以很容易地在分区并行中执行）。如果一个像素对应于一个非MSERRn（被识别为非MSER），则具有最小灰度级的MSER在Rn的父ER中是它对应的MSER。在图6中，自身像素按顺序（行优先顺序）提取到MSER 4、6、1、6、2、6、5、5中。0图11.ICDAR数据集中的3个图像（左）和DetectorEval数据集中的2个图像（右）的示例。0注意，MSER 6的内存地址被重定位了3次，导致像素提取速度较慢。然后V2迭代遍历MSER数组（按灰度级从小到大排序），并将它们的MSER索引（而不是复制它们的像素）添加到它们的父MSER中。请注意，这个过程不能并行执行，因为它按顺序访问MSER数组。05. 实验验证0该算法是用C++实现的。计时是在一台联想笔记本电脑上进行的，配备了4核Inteli7-6700HQ处理器和8GB的RAM内存。我们使用了两个指标：执行时间和内存使用情况。请注意，如果没有另外说明，执行时间和内存使用情况都是每张图像的平均值。05.1. 数据集0为了评估Fast MSERV1和V2在不同大小的图像上的性能，选择了几个具有固定大小的图像，然后将其调整为不同的大小。我们使用两个真实世界的图像数据集：ICDAR鲁棒阅读竞赛的测试集[15]（ICDAR数据集）和[22]的特征检测器评估序列（DetectorEval数据集）。ICDAR数据集包含233个大小不同的图像，从350×200到3888×2592，而DetectorEval数据集包含49个大小不同的图像，从800×640到1000×700。我们将这两个数据集中的所有图像调整为固定大小的3888×2592（图像大小约为10M，其中M表示百万像素）。然后我们生成包含从2M大小（对应于1732×1154的大小）到10M大小的5个尺度的图像数据集。每个图像包含3个通道：R、G和B。我们希望在我们的计算机上使用4个核心（每个核心上执行一个线程）上比较通道并行的MSER算法，因此为每个图像添加了一个灰度通道。这样，一个具有10M大小的图像（4个通道）实际上有40百万像素。图11显示了一些图像示例。为了避免进程调度，执行时间是通过在每个大小的图像上运行五次并选择最快的运行来产生的[28]。05.2. 参数配置0p = 20, max0p = 0.25 × N, var = 0.5, dvar = 0.1, δ =0p = 0.25 × N, var = 0.25, dvar = 0.2, δ = 5）。仅配置22.229.132.536.539.82026.829.333.634.62230.832.540.7843.82025.530.23334.733860类别02 M04 M06 M08 M010 M0ICDAR0ICDAR排序0DE0DE排序0表1.不同大小图像上我们的新型子树合并算法的执行时间（毫秒）。ICDAR和DE分别表示合并算法在ICDAR和DetectorEval数据集上运行。后缀“Sort”表示合并算法使用排序的ER对（见第3.2节）。0影响MSER识别和像素提取的执行时间。TextDetection[45]用于场景文本检测任务。δ设置为1，这使得它能够检测到大多数具有挑战性的情况[13]。在DetectorEval中识别的MSER较少，因为ER被识别为MSER的标准更严格（两个配置中的var、dvar和δ不同）。在我们的实验中，我们只展示了在ICDAR数据集下的TextDetection结果和在DetectorEval数据集下的DetectorEval结果（实际上，两个数据集上相同配置的结果是相似的）。05.3. 合并时间测试0V1中的子树合并过程非常快（处理一个具有1000万像素的图像大约需要1毫秒），这里我们只评估V2中的合并过程。表1显示了使用排序的ER对进行合并的速度比不使用排序的ER对进行合并的速度更快，这证明在合并两个子树之前对ER对进行排序是必要的。05.4. 内存使用比较0MSER算法的内存使用主要由输入图像的大小决定。图13显示了不同算法的内存使用情况。CV-MSER+是我们通过用指针数组替换向量数据结构（分配内存较慢）并利用连续内存存储输出MSERs而不是独立存储MSERs（释放内存较耗时）来完全优化CV-MSER的实现。带有“CP”的算法是通道并行版本。对于非并行算法，ID-MSER在组件树构建过程中动态分配运行内存，从而实现最小的内存使用和较慢的组件树构建。VF-MSER中的ER数据结构非常简单，因为它不提取MSERs中的像素。与CV-MSER相比，CV-MSER+使用更少的内存，因为该区域仅存储其父区域而不是存储其父区域和子区域。对于并行算法，V1和V2使用的内存明显少于其他并行算法。V1和V2都动态地合并子树的过程非常快（处理一个具有1000万像素的图像大约需要1毫秒），这里我们只评估V2中的合并过程。表1显示了使用排序的ER对进行合并的速度比不使用排序的ER对进行合并的速度更快，这证明在合并两个子树之前对ER对进行排序是必要的。0与V1相比，V2使用的内存更少，因为它使用的是标记图像而不是双向链表。V2是所有并行算法中内存使用最少的。注意，CPCV-MSER、CPCV-MSER+、CPVF-MSER和CPID-MSER的内存使用量是它们的非并行版本的4倍。05.5. 执行时间测试。0在图12(a)中，10M张图像上的速度（兆像素/秒）分别为0.36（CV-MSER）、7.94（CV-MSER+）、0.43（VF-MSER）、4.41（ID-MSER）、0.98（CPCV-MSER）、18.78（CPCV-MSER+）、1.05（CPVF-MSER）、15.51（CPID-MSER）、27.15（Fast MSERV1）和25.23（Fast MSERV2）。V1和V2的速度比CPCV-MSER快28倍和26倍，并且只使用1018运行内存。与CV-MSER+相比，V1和V2的加速比分别为3.42和3.18。作为标准MSER，VF-MSER花费的时间太长。ID-MSER没有完全优化。尽管它们都没有提取MSER中的像素，但它们及其并行版本的速度都比FastMSER慢。CV-MSER+比CV-MSER快得多，因为它经过了完全优化。在图12(b)中，结论与图12(a)中的结论相似。图12(b)中的所有算法都更快，因为在DetectorEval下识别的MSER较少。我们还研究了V1和V2在不同δ（MSER算法中的一个关键参数）下的性能。如图14所示，较低的δ意味着检测到更多的MSER（像素提取可能需要更长的运行时间），而较高的δ意味着检测到较少的MSER（像素提取可能需要较少的时间）。与CV-MSER+相比，V1的加速比分别为3.42（δ=1）、3.28（δ=2）、3.25（δ=3）、3.09（δ=4）和3.09（δ=5）。而V2的加速比分别为3.18、3.17、3.21、3.07和3.06。因此，δ越大，加速比越低。05.6. 不同步骤的执行时间测试。0在表2中，与CV-MSER+相比，V1和V2在组件树构建方面的加速比分别为2.8和2.95，在像素提取方面的加速比分别为6.7和3.6，这证明了我们算法的效率。然而，在MSER识别方面的加速比为1.1和1.2，因为变化的最小抑制不是并行的。由于MSER识别所花费的时间较少，V1和V2的整体加速比仍然是较高的3.42和3.18。V1在像素提取方面比V2更快（请参阅第4节中的原因），但在其他阶段稍微慢一些。因此，当识别的MSER较少（在平滑图像中或在具有较高δ和较小var的配置下）或不需要像素提取时，我们更倾向于使用V2。注意，V2使用的内存也比V1少。与CV-MSER+相比，V1和V2在像素提取方面减少了85%和72%的执行时间。平均0.3393.40.13383.122.860.0023.1160.0831.3990.4410.00191.750.058\0.0250.0468.8070.156\0.0240.0021.1070.0740.2090.0810.0011.0540.0680.3850.0770.3064.0150.10114.273.970.0024.1840.070.5180.1730.00157.680.024\0.0250.0619.450.571\0.020.0021.190.0510.1320.0580.0011.150.050.3120.04833870图12. 两个配置下的执行时间。0图13. 所有算法的内存使用比较。注意，ID-MSER和Fast MSERV2的内存使用量非常接近，它们的线重叠在一起。0图14. Fast MSERV1和V2在ICDAR数据集的10M张图像上对不同δ的执行时间（秒）。其他参数与配置TextDetection相同。0CV-MSER+和FastMSER（V1和V2）在图像中产生的MSER中像素的内存大小分别为1.3GB和296MB。我们的两种新型像素提取方法都将MSER中像素的内存压缩了78%，从而将内存释放时间减少了82%。作为标准MSER，VF-MSER在组件树构建方面花费了很多时间。ID-MSER没有完全优化，比其他线性MSER算法慢。在表3中，结论与表2类似。请注意，与CV-MSER+相比，V1和V2仅将像素提取时间减少了75%和40%，因为检测到的MSER较少。0算法0Init0Tree0Reco0Extr0Rele0CV-MSER0CV-MSER+0VF-MSER0ID-MSER0快速MSER V10快速MSER V20表2.在ICDAR数据集的10M图像中，不同步骤的执行时间（秒）在TextDetection下。Init，Tree，Reco，Extr和Rela表示算法初始化，组件树构建，MSER识别，像素提取和内存释放。在一幅图像中识别出约147,000个MSER。0算法0Init0Tree0Reco0Extr0Rele0CV-MSER0CV-MSER+0VF-MSER0ID-MSER0快速MSER V10快速MSER V20表3.在DetectorEval数据集的10M图像中，不同步骤的执行时间（秒）在DetectorEval下。在一幅图像中识别出约33,000个MSER。0在DetectorEval下识别。06. 结论0在本文中，我们提出了快速MSERV1和V2。V1集成了一种新颖的子树合并算法和一种新颖的像素提取方法，而V2使用了一种现有的子树合并算法和另一种新颖的像素提取方法。V1和V2比OpenCVMSER快28倍和26倍，并且使用的内存更少。在未来的工作中，我们将改进MSER识别的加速，并进一步减少V1和V2的运行内存。33880参考文献0[1] https://opencv.org/opencv-3-4-1.html。[2] Idiapmser。https://gith