CN109949261B - 处理图形的方法、图形处理装置和电子设备 - Google Patents

Abstract

本公开提供一种用于图形处理装置的处理图形的方法、图形处理装置和电子设备。所述方法包括以下步骤：在所述图形上选取多个目标区域；将所述多个目标区域划分为多个组；和将所述多个组中的每个组划分为多个区块，包括确定包含每个组中的目标区域的约束区，拼接单位网格以形成覆盖所述约束区的多个区块，其中每个所述单位网格充当所述多个区块中的单个区块；和从每个组的所述多个区块提取至少部分地包含有效特征的期望区块。

Description

处理图形的方法、图形处理装置和电子设备

技术领域

本公开涉及图形处理领域，涉及处理图形的方法和图形处理装置、以及电子设备，尤其是用于分割图形的方法和装置以及电子设备。

背景技术

近年来，在图形处理领域，由于需处理的数据量规模日益增大，在应对大数据量的同时，也需要同时兼顾有效减少和移除图形中的干扰因素、以及确保和提升图形处理的品质，带来了对于图形处理装置的处理能力的挑战。并且，对于图形处理的这种日益严格的需求存在于众多应用领域中。

例如，在半导体工艺的芯片生产过程中，对硅片进行缺陷检测是必不可少的环节，例如采用电子束检测工艺。具体地，在基于硅片的芯片制造工艺中，从最初阶段就必需对硅片进行检测。早期的生产线上，熟练的技术人员在例如观察硅片表面的氧化物薄膜后就能凭经验预测相应薄膜的厚度，并且例如利用氧化物薄膜所呈现色泽与比色表的对比，由此实现生产过程中的缺陷检测。随着硅片加工技术的进展，例如特征尺寸不断缩小，同时在硅片上的芯片密度不断增加，从而带来了诸如沾污、结深等影响加工效果的问题；并且，新材料的应用和新工艺的引入也会带来易于导致芯片失效的新问题。此外，硅片的测量也是对于描绘硅片的特征与检查其成品率而言至关重要的。由此，硅片的检测技术相应地也经历重大改变。

在工艺线上被图案化的硅片通常是待用于在线检测表面缺陷的生产硅片。通常，集成电路中的生产硅片例如具备多层(例如六层)金属薄膜或其他薄膜，这些多层薄膜使得对硅片上的表面缺陷和电路图案进行有效区分是更有挑战性的。现有技术中利用光散射技术来检查经图案化的硅片的主要缺陷。从20世纪90年代初，扫描电子显微镜作为一种非破坏性/非接触性的、且扫描倍数显著高于光学显微镜的测量仪器，逐渐成为在亚微米时代进行检测和关键尺寸控制的主要仪器。其典型原理在于利用磁焦距系统控制电子枪发射的电子打在样片上，由于二者的相互作用，产生二次电子和背散射电子被探测器收集并且产生描绘样本表面状况的电子束图像。基于所述电子束图像，可以进行缺陷检测。然而，扫描电子显微镜的相对较大的放大倍数也导致了其成像视场范围狭小；并且，在对硅片的同一部位进行重复扫描的情况下，往往由于电荷积聚导致局部成像效果的劣化。

并且，还存在众多应用领域，都需要以尽量不重复的方式针对重点区域进行诸如扫描/成像等处理，以及相应地提高针对含有平面图形中的具备有效特征的部位进行处理的图形处理速度。

除了二维图形的处理领域，当前技术的发展也涉及到例如空间扫描和三维图形中的处理，类似地也需要以尽量不重复的方式针对终点区域进行诸如空间扫描/成像等处理，以及相应地提高针对空间图形中的具备有效特征的部位进行处理的图形处理速度。

因此亟需一种处理图形的方法和设备，其能够在视场尺寸确定的情况下，以位置上不重复的方式来实现利用尽量少的扫描和/或处理次数以覆盖尽可能大面积的待处理的对象区域，由此有效减少进行图形处理的时间和提高处理效率。

发明内容

为至少部分地克服上述现有技术中的缺陷和/或不足，本公开的实施例提供了一种用于处理图形的方法和一种图形处理装置以及一种电子设备，尤其是用于分割图形的方法、装置、和电子设备。所述技术方案如下：

为实现上述目的，本公开提供以下技术方案：

根据本公开实施例的一方面，提供一种用于图形处理装置的处理图形的方法，其中，所述方法包括：在所述图形上选取多个目标区域；将所述多个目标区域划分为多个组；和将所述多个组中的每个组划分为多个区块，包括：确定包含每个组中的目标区域的约束区，和拼接单位网格以形成覆盖所述约束区的多个区块，其中每个所述单位网格充当所述多个区块中的单个区块；和从每个组的所述多个区块提取至少部分地包含有效特征的期望区块。

根据本公开的一个实施例，从每个组的所述多个区块提取至少部分地包含有效特征的期望区块的步骤包括：利用图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块。

根据本公开的一个实施例，利用图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块包括：

在每个组的约束区中，利用图形布尔运算获取所述多个区块与所述每个组中的包含有效特征的部位的多个交集；和

选取所述多个交集中的非空交集为所述期望区块，且移除所述多个交集中的空交集。

根据本公开的一个实施例，在所述图形是二维图形的情况下，所述图形布尔运算是二维图形布尔运算；或

在所述图形是三维图形的情况下，所述图形布尔运算是三维图形布尔运算。

根据本公开的一个实施例，所述方法还包括：

在从每个组的所述多个区块提取至少部分地包含有效特征的期望区块之后，将经划分的每个组中的所述期望区块置入单一的集合。

根据本公开的一个实施例，在所述图形是二维图形的情况下，所述多个目标区域中的每个呈如下平面形状之一：矩形、三角形、圆形、椭圆形、其它多边形、和不规则平面异形形状；或

在所述图形是三维图形的情况下，所述多个目标区域中的每个呈如下空间形状之一：长方体、空间四边形、球体、椭球体、其它空间多面体、和不规则三维异形形状。

根据本公开的一个实施例，所述将所述多个目标区域划分为多个组包括：将所述多个目标区域基于各自的分布特点划分为多个组。

根据本公开的一个实施例，所述分布特点包括以下至少之一：所述多个目标区域之间的最小间距，所述多个目标区域的分布周期性，经选取的多个热点区域。

根据本公开的一个实施例，

在所述图形是二维图形的情况下，所述约束区是包围所述每个组的目标区域的最小化的封闭的边界框；或

在所述图像是三维图像的情况下，所述约束区是包围所述每个组的的目标区域的最小化的封闭的包围盒。

根据本公开的一个实施例，

所述拼接单位网格以形成覆盖所述约束区的多个区块包括：所述单位网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在坐标系的各个坐标轴的方向上均齐平和/或超出所述约束区的边界。

根据本公开的一个实施例，用于划分每个组的各自单位网格呈相同的形状和大小。

根据本公开的一个实施例，在所述图形是二维图形的情况下，每个所述单位网格呈矩形；或

在所述图形是三维图形的情况下，每个所述单位网格呈空间四面体或长方体。

根据本公开的一个实施例，在所述图形是二维图形的情况下，每个所述单位网格被配置呈小于或长度等于所述图形处理装置的视场的横向长度、且宽度小于或等于所述图形处理装置的视场的纵向长度的矩形；

在所述图形是三维图像的情况下，每个所述单位网格被配置呈三维尺寸被限定为小于或等于所述图像处理装置的视场范围的空间四面体或长方体。

根据本公开的一个实施例，所述每个组的所述最小化的封闭的边界框或包围盒被配置成其各个顶点的坐标分别为所述每个组中的目标区域在不同坐标轴上的坐标极值的组合。

根据本公开的一个实施例，所述方法还包括：在将所述多个目标区域划分为多个组之前，对所述多个目标区域进行预处理，包括以下至少之一：

第一预处理，其中利用图形布尔运算移除非目标区域和每个目标区域的与所述非目标区域相交的部分的图案；和

第二预处理，其中利用图形布尔运算拆分至少部分地交叠的目标区域以创建不相交地邻接的多个新的目标区域，且所述多个新的目标区域的面积总和等于至少部分地交叠的目标区域在所述图形上的投影面积。

根据本公开实施例的又一方面，提供一种图形扫描装置，包括：

扫描器，用于执行根据前述的方法。

根据本公开实施例的再一方面，提供一种电子束检测设备，包括：

根据前述的图形扫描装置，和电子束成像装置，所述电子束成像装置包括下列至少一个部件：电子束发射源；电子束控制装置；以及扫描偏转器。

根据本公开实施例的又再一方面，提供一种电子设备，包括：

存储器，用于存储可执行指令；和

处理器，用于执行存储器中存储的可执行指令，以执行根据前述的方法。

根据本公开实施例的又再一方面，提供一种图形处理装置，包括：

执行器，用于执行根据前述的方法。

根据本公开实施例的又再一方面，提供一种用于地图的地理信息系统，包括：

处理器，被配置用于执行根据前述的方法来选择和处理所述地图上的目标区域，和

执行器，被配置用于加载与经处理的所述目标区域相关的信息。

根据本公开实施例的又再一方面，提供一种用于布设目标物的装置，包括：

采集器，被配置用于获取待布设目标物的区域的图形；

扫描器，被配置用于执行根据前述的方法来对待布设目标物的区域的图形进行扫描；和

执行器，根据所述扫描器的扫描结果布设目标物。

根据本公开实施例的又再一方面，提供一种用于区域统计的设备，包括：

采集器，被配置用于获取待统计的区域的图形；

扫描器，被配置用于执行根据前述的方法来对待统计的区域的图形进行扫描；和

计算装置，被配置用于根据所述扫描器的扫描结果通过计算来进行对于待统计的区域的统计操作。

根据本公开实施例的又再一方面，提供一种用于排版的装置，包括：

采集模块，被配置用于获取待排版打印的区域的图形；

扫描模块，被配置用于执行根据前述的方法来对待排版打印的区域的图形进行扫描；和

排版模块，被配置用于根据所述扫描器的扫描结果来对于待排版打印的区域进行排版操作。

附图说明

通过下文中参照附图对本公开实施例所作的详细描述，本公开实施例的上述和其它特征和优点将显而易见，并帮助获得对本公开实施例有全面的理解。在附图中：

图1(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图。

图1(b)图示出针对根据图1(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图。

图2(a)图示出根据图1(a)所示的待处理的多个目标区域中的第一分组中的目标区域的局部放大示意图，其中所述第一分组中仅有单个目标区域。

图2(b)图示出针对根据图2(a)所示的第一分组中的目标区域进行网格化分块处理之后的示意图，其中在右侧边缘处局部示出执行提取有效特征的操作。

图2(c)图示出根据图2(b)的椭圆部分处的局部放大图，其中示出经分块处理后在右侧边缘处进行图形布尔运算的交集操作以通过去除不包含有效特征的非期望区块而提取有效特征。

图2(d)图示出根据图1(a)所示的待处理的多个目标区域中的第一分组10’中的目标区域110’的局部放大示意图，其中所述第一分组中仅有单个目标区域，且所述目标区域非矩形。

图2(e)图示出针对根据图2(d)所示的第一分组中的非矩形目标区域110’进行网格化分块处理之后的示意图。

图3(a)图示出根据图1(a)所示的待处理的多个目标区域中的第二分组中的目标区域的局部放大示意图，其中在所述第二分组中的目标区域紧邻。

图3(b)图示出针对根据图2(a)所示的第二分组中的目标区域进行网格化分块处理之后的示意图。

图4(a)图示出待处理的多个目标区域中的第三分组的目标区域的示意图，其中在所述第三分组中的目标区域相交。

图4(b)图示出针对根据图4(a)所示的第三分组中的目标区域进行网格化分块处理之后的示意图。

图5(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图，其中存在着与至少一个目标区域相交叠的非目标区域(例如硅片掩盖层)。

图5(b)图示出针对根据图5(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图，并且在分组和网格化分块处理之前进行了移除非目标区域(例如硅片掩盖层)的第一预处理。

图6(a)图示出待处理的多个目标区域中的第四分组中的目标区域的示意图，其中在所述第四分组中的目标区域位于非目标区域(例如硅片掩盖层)一侧与之相邻。

图6(b)图示出针对根据图6(a)所示的第四分组中的目标区域进行网格化分块处理之后的示意图。

图7(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图，其与图5(a)所示实施例类似且区别仅在于存在着非矩形的异形形状目标区域。

图7(b)图示出针对根据图7(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图，并且在分组和网格化分块处理之前进行了移除非目标区域(例如硅片掩盖层)的第一预处理。

图8(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性目标区域为立方体。

图8(b)图示出针对根据图8(a)所示的单个目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位立方体网格。

图9(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性目标区域为长方体。

图9(b)图示出针对根据图9(a)所示的单个目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位四面体网格。

图10(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性目标区域为圆柱体。

图10(b)图示出针对根据图10(a)所示的单个目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位四面体网格。

图10(c)图示出图10(b)所示的经网格化分块处理之后的目标区域分组的示意图，其中包络有未处理前的所述圆柱体形的目标区域。

具体实施方式

为下面通过实施例，并结合附图，对本发明的技术方案作进一步具体的说明。在说明书中，相同或相似的附图标号指示相同或相似的部件。下述参照附图对本发明实施方式的说明旨在对本发明的总体发明构思进行解释，而不应当理解为对本发明的一种限制。

另外，在下面的详细描述中，为便于解释，阐述了许多具体的细节以提供对本披露实施例的全面理解。然而明显地，一个或多个实施例在没有这些具体细节的情况下也可以被实施。在其他情况下，公知的结构和装置以图示的方式体现以简化附图。

附图被用于说明本公开的内容。附图中各部件尺寸和形状不反映部件的真实比例。

出于下文表面描述的目的，如其在附图中被标定方向那样，方位术语“上”、“下”、“左”、“右”“垂直”、“水平”、“顶”、“底”及其派生词应涉及公开文本，用于解释附图所示的方位关系。方位术语“上覆”、“在……顶上”、“定位在……上”或者“定位在……顶上”意味着诸如第一结构的第一要素存在于诸如第二结构的第二要素上，其中，在第一要素和第二要素之间可存在诸如界面结构的中间要素。这些方位术语不应解释为对本公开保护范围的限制。

根据本公开的一种总体发明构思，在本公开的一方面实施例中，提供了一种用于图形处理装置的处理图形的方法，其中，所述方法包括以下步骤：在所述图形上选取多个目标区域；将所述多个目标区域划分为多个组；将所述多个组中的每个组划分为多个区块，包括：确定包含每个组中的目标区域的约束区、和拼接单位网格以形成覆盖所述约束区的多个区块，其中每个单位网格充当单个区块；和从每个组的所述多个区块提取至少部分地包含有效特征的期望区块，即待检测区块。

首先，例如针对当前图形处理领域中较为典型的生产硅片的图形处理过程，即在所述图形是二维图形的情况下，阐述本公开所基于的工作原理。

在图形处理领域，例如对所采集的生产硅片的图像进行诸如检测等处理时，例如基于所采集的图像上显示的硅片图形中的刻蚀区域的分布状况和刻蚀图案的不同，来在所述硅片的图形上选取并划分出若干待检测的目标区域(targeted area)，以及可选地存在的无需检测的非目标区域(non-targeted area)，且为简化起见每个目标区域被限定为矩形区域，且所述非目标区域也例如类似地位矩形区域。所述非目标区域例如是人为添加的无需检测的区域；具体地，所述非目标区域诸如其中不存在刻蚀图案而必须被去除而不加考察的区域(例如起到遮蔽作用的掩盖区，更具体地诸如硅片工艺中的掩模)，或者其中刻蚀工艺出错概率极低的必然区域或高置信度区域，从而不必纳入本发明方案的考察/处理中。由此，这些人为添加的非目标区域在利用本发明进行图形检测时，对这些非目标区域的图案(例如缺陷图案)进行强行忽略。

进而，将这些待检测的目标区域分割为多个群组/集合进行处理(例如进一步细分为众多拼接的区块，并且选取其中的至少部分含有有效特征/信息的部位(下文称为有效部位)的区块，即下文的期望区块或对象区块(object block))，实际工作中也可替代地称为待检测区块。之后，再对这些群组/集合中的经处理后的待检测目标区域中的对象区块进行多次拍摄成像以进行检测。具体地，例如，在拍摄的生产硅片的图像中，硅片上形成的图案化区域作为有效特征；除此之外，由于实际工艺中，还例如存在尘埃污染、以及用于曝光的实际布置相比于设计的/预期的布置而言的差异而导致在蚀刻过程中出现若干非预期的图案，这些非预期的图案往往由于不符合设计要求而潜在地引起电路中的故障，例如局部短路和/或断路，是需要在图形处理时去除的无效特征。

作为本公开的基本实施例，例如，如图1(a)和图1(b)所示，图1(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图。图1(b)图示出针对根据图1(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图。在本公开的一个示例性实施例中，提供一种用于图形处理装置的处理图形的方法，其中，所述方法包括以下步骤：

S10：选区步骤，包括在所述图形上选取多个目标区域；

S20：分组步骤，包括将所述多个目标区域划分为多个组；

S30：分块步骤，包括将所述多个组中的每个组划分为多个区块；和

S40：提取步骤，包括从每个组的所述多个区块提取至少部分地包含有效特征的期望区块。

经过如上四个主要步骤，能够避免现有技术的图形处理过程中由于遍历处理导致的处理时间长和可能重复对相同位置进行处理的缺陷，替代地以位置上不重复的方式对具备有效特征的重点部位进行图形处理，而忽略掉对于不含有效特征的其余部位，从而提高了图形处理效率。

图1(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图。

在示例性实施例中，具体地，所述选区步骤S10中，例如，所述多个目标区域中的每个呈如下平面形状之一：矩形、三角形、圆形、椭圆形、其它多边形、和不规则平面异形形状；且如图1(a)所示，多个目标区域110、210、220、310、320中的每个例如优选地为矩形，以便利简化后续处理。

图1(b)图示出针对根据图1(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图。

在示例性实施例中，具体地，所述分组步骤S20包括将所述多个目标区域基于各自的分布特点划分为多个组。更具体地，如图1(b)所示，所述分布特点例如是所述多个目标区域之间的最小间距，从而能够例如分别基于目标区域之间的分布疏密程度将毗邻定位的若干目标区域划分入同一组内，便利于后续处理中诸如在分块步骤S30中就近地以相同大小的单位网格连续进行同一组内的网格化处理从而简化操作。例如，目标区域210、220由于彼此毗邻而被划入同一分组20内，目标区域310、320由于彼此毗邻而被划入同一分组30内，而目标区域110由于远离开其它各个目标区域而被单独划分为分组10。

另外，在所示多个目标区域按照一定规律性重复分布的情况下，所述分布特点还可以例如是所述多个目标区域的分布周期性，从而能够对于类似或相同的目标区域进行单次的同样处理，减少了对于目标区域而言的重复的操作步骤，提高了总体处理效率。另外替代地，所述分布特点还可以例如是由用户以手动方式选取的多个热点区域，从而在经用户观察后发现某些目标区域由于例如存在某些特征而需特别关注的情况下，方便对于这些需特别关注的目标区域的优先处理，从而有效将自动化流程与人工决策相接合以进行有效的分组操作。

在本公开的进一步的实施例中，例如仍如图1(b)所示，所述分块步骤S30例如具体包括如下子步骤：

S310：即限定约束区子步骤，其中，确定包含每个组中的目标区域的约束区；和

S320：即网格化子步骤，其中，拼接单位网格以形成覆盖所述约束区的多个区块，其中每个所述单位网格充当所述多个区块中的单个区块。

在示例性实施例中，具体地，所述限定约束区子步骤S310中，例如，所述约束区可以是包围所述每个组的目标区域的任何封闭的边界框，优选地例如是包围所述每个组的目标区域的最小化的封闭的边界框。所限定的边界框所占据面积越小，则相应地后续在子步骤S320中进行网格化处理的过程中所需的处理量越少，从而最小化的封闭的边界框对应于最小化的网格化处理量。

进一步地，图2(a)图示出根据图1(a)所示的待处理的多个目标区域中的第一分组10中的目标区域的局部放大示意图，其中所述第一分组中仅有单个目标区域；而图2(b)图示出针对根据图2(a)所示的第一分组中的目标区域进行网格化分块处理之后的示意图。例如，如图2(a)所示，对于仅包含目标区域110的分组10，由于目标区域110本身呈矩形，则用于包围该分组10的所有目标区域110的最小化的封闭的边界框例如视为目标区域110本身。

在示例性实施例中，如图1(b)所示，所述网格化子步骤S320例如包括：所述单位网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在平面直角坐标系的纵向和横向均齐平和/或超出所述约束区的边界。

所述单位网格是被定义用以划分图形的单位。例如，为处理简单和减少网格化的工作量起见，用于划分每个组的各自单位网格呈相同的形状和大小。例如，如图1(a)所示，用于对分组10的单位网格110进行划分的单位网格，是与对于分组20的单位网格210、220进行划分的单位网格、以及对于分组30的单位网格310、320进行划分的单位网格呈完全一致的形状和大小。

优选地，由于对任何平面图形进行网格化时，例如在诸如有限元分析等图形细分的过程中，往往采用均一的三角形或均一的矩形的单位网格来进行网格化，以便利于利用单位网格之间仅边缘抵紧或贴合的方式来不重复地进行网格化，即单位网格之间不存在面积的交叠，从而避免了由于网格化过程中由于单个部位处重复被网格化而导致的冗余工作量。更具体地，例如，如图2(b)所示，所述拼接单位网格以形成覆盖所述目标区域110的约束区的多个区块包括：所述单位网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在平面直角坐标系的纵向和横向均齐平和/或超出所述约束区的边界。其中，如图2(b)所示，基于对尽量少的网格化工作量和仅边缘交叠的要求的折衷考虑，所述单位网格，图示为呈均一的矩形单位网格，例如从目标区域110的约束区中的目标区域分布最密集点(例如左上角)开始，开始在其所在的平面直角坐标系中分别沿着X和Y两个主方向(即图中的横向和纵向)以边缘抵紧或贴合的方式延伸以覆盖所述目标区域110的约束区。

作为更具体的实施例，由于对生产硅片进行缺陷检测通常利用扫描电子显微镜进行，因而进行网格化的单位网格实质上受到扫描电子显微镜的视场所施加的物理限制，从而，例如，每个所述单位网格被配置呈长度等于所述图形处理装置例如扫描电子显微镜的视场FOV的横向长度、且宽度等于所述图形处理装置的视场FOV的纵向长度的矩形。具体而言，如图2(b)所示，单位网格选择为FOV，在图中示出为FOV_110-x-y的形式，其中，x,y分别表示单位区域在横向和纵向上的序号，即单位网格FOV_110-x-y表示从作为目标区域110的约束区中的目标区域分布最密集点的左上角开始，位于第x行、第y列处的单位网格。在替代的实施例中，每个所述单位网格也能够被配置呈长度小于所述图形处理装置例如扫描电子显微镜的视场FOV的横向长度、且宽度小于所述图形处理装置的视场FOV的纵向长度的矩形。

具体的网格化过程描述为：从目标区域110的约束区(即该矩形目标区域本身)的左上角开始，首先以选中的顶点作为第一个视场图像区域矩形的顶点，在横向上延伸视场区域的横向长度，在纵向上延伸视场的纵向长度，从而分割出第一个和FOV同等大小的扫描区域FOV_110-1-1。然而在第一主方向X上以各个面积等同于FOV的扫描区域之间呈边缘抵紧或贴合的方式多次重复这个操作，即重叠宽度例如为0，由此继续生成扫描区域FOV_110-1-2，...，至最后一个在主方向X上位于约束区内的扫描区域FOV_110-1-(j1-1)，并且继续进行网格化直至分割出的第一行最末扫描区域FOV_110-1-j1首次超出约束区的横向边界。紧接着，继续在第二主方向Y上以各个面积等同于FOV的扫描区域之间呈边缘抵紧或贴合的方式重复进行与该第一行类似的分割操作，直至该Y方向上的一列的矩形扫描区域FOV_110-i1-1也首次超出约束区的纵向边界。继而进行第二行、第二列的网格化。以此行-列交替的方式进行网格化直至整个约束区的最后一个角落的边界被首次超出，即形成右下角的最后一个扫描区域FOV_110-i1-j1位置，由此形成i1行×j1列的网格阵列，从而实现全部单位网格的整体完全覆盖约束区。且如果存在面积等同于FOV的单个扫描区域未能与其需覆盖的约束区的部分完全重叠/叠合，则需要减去该FOV扫描区域已重叠的区域，并且进而获得一个与其需覆盖的约束区的部分的尺寸相符的非重叠的替代FOV，以完成该处的扫描。并且，还存在一种替代的实施例，即单个约束区恰好包括成行且成列的网格阵列，而没有网格超出其边界的范围，即网格阵列的边缘恰好与约束区齐平，从而也实现全部单位网格的整体完全覆盖约束区。

此外，关于网格化的具体操作方式，作为替代的实施例，也可逐行进行网格化和逐列进行网格化，直至在平面直角坐标系的纵向和横向均齐平和/或超出所述约束区的全部边界，从而实现单位网格整体完全覆盖约束区。

并且，作为示例性的实施例，在确定目标区域的约束区的各个角落处的顶点位置时，例如所述每个组的所述最小化的封闭的边界框被配置成其各个顶点的坐标分别为所述每个组中的目标区域在不同坐标轴上的坐标极值的组合。具体而言，例如，如图2(a)和图2(b)所示，矩形目标区域110的矩形约束区的各顶点即其四个角的坐标分别为(X_min，Y_min),(X_max，Y_min)，(X_min，Y_max)，和(X_max，Y_max)，其中，X_max，Y_max，X_min，和Y_min分别为所述每个组中的所有目标区域的沿着图2(b)所示的X方向正向和Y方向正向的最大横坐标、最大纵坐标、最小横坐标、和最小纵坐标，即目标区域的坐标最值。由此，通过确定顶点的坐标，可以确定平面矩形目标区域；且由于任何平面形状的区域可以由一个矩形包围约束，则也可以通过以上方式确定矩形约束区的顶点的坐标，来表征任何平面形状的目标区域的矩形约束区。

并且，对每个待检测的目标区域的分组重复上一步骤，直到所有分组中的目标区域均被网格化分割完毕。

下面继续具体讨论提取步骤S40。

图2(b)中在右侧边缘处局部示出执行提取有效特征的操作；且图2(c)图示出根据图2(b)的椭圆部分处的局部放大图，其中示出经分块处理后在右侧边缘处进行二维图形布尔运算的交集操作以通过去除不包含有效特征的非期望区块而提取有效特征。

在示例性实施例中，具体地，所述提取步骤S40包括利用二维图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块。更具体地，例如如图2(b)分别所示，所述提取步骤S40中，特别是与网格化后获得的区块FOV_110-4-j1、FOV_110-5-j1和FOV_110-6-j1相邻的边缘部位处，存在着如斜阴影线示出的边缘区块A，其中存在有效区域B和无效区域即B在A中的补集(A-B)(所述无效区域(A-B)例如是缺陷区域，由于蚀刻工艺而在硅片图形边缘处形成的不期望的凹槽造成，该凹槽在理想的设计硅片图案中例如不存在)，从而其中的图形信息为无效信息。因此，提取步骤S40旨在从网格化区块FOV_110-4-j1、FOV_110-5-j1和FOV_110-6-j1中提取与该边缘区块A相交的由折线阴影线示出的区域B(如图2(c)中的加深框内部分所示)以视为部分地包含有效特征的期望区块，而从该三个区块中去除的B外侧的图形区域则视为缺陷部分而放弃。

在本公开的进一步的实施例中，例如仍如图2(c)中的局部放大图所示，所述提取步骤S40例如具体包括如下子步骤：

S410：求取交集子步骤，即在每个组的约束区中，利用图形布尔运算获取所述多个区块与所述每个组中的包含有效特征的部位的多个交集；和

S420：去除非空交集子步骤，即选取所述多个交集中的非空交集为所述期望区块，且移除所述多个交集中的空交集。

在示例性实施例中，具体地，在所述求取交集子步骤S410中，例如，分别将网格化区块FOV_110-4-j1、FOV_110-5-j1和FOV_110-6-j1与边缘区块A求取交集。

并且例如，在所述去除非空交集子步骤S420中，例如，将区块交集(FOV_110-4-j1∩A)、(FOV_110-5-j1∩A)和(FOV_110-6-j1∩A)作为期望区块的值保留下来。

这种在网格化之后利用各个网格化的区块与相邻的至少部分含有有效信息的区块进行求取交集来提取期望区块的方法，相比于常规的直接基于大的图形例如整体硅片图案来提取其边缘的局部处的期望区块的方法，能够充分利用图形处理装置例如扫描电子显微镜的精细视场，从而处理图形的分辨率更精细；并且由于采用二维图形布尔运算，使得处理简化直观，减少了工作量。

额外地，在示例性实施例中，所述用于图形处理装置的处理图形的方法还包括步骤S50，即归集步骤，包括在提取步骤S40之后，将经划分的每个组中的所述期望区块置入单一的集合而保存，且在需要图形处理时输出。从而可以得到直观的图形的整体有效信息分布、而有效去除无效信息的图形部位。

下面进一步讨论扩展实施例。

图2(d)图示出根据图1(a)所示的待处理的多个目标区域中的第一分组10’中的目标区域110’的局部放大示意图，其中所述第一分组中仅有单个目标区域，且所述目标区域非矩形；图2(e)图示出针对根据图2(d)所示的第一分组中的非矩形目标区域110’进行网格化分块处理之后的示意图。

当然，作为替代的可选实施例，可以针对所述多个组中的每个组采用不同的单位网格，例如不同形状和/或尺寸。例如，由于目标区域也可能为非矩形形状，例如椭圆形，或诸如凹入的封闭形状等不规则平面异形形状，例如，如图2(d)中的目标区域110’。则相应地，仅有该单个非矩形目标区域110’的分组10’的约束区除了如图2(d)中虚线所示选择为矩形，也可根据与目标区域的轮廓的边界仿形的非规则的约束区，从而实际上有可能以比矩形约束区更少的工作量实现约束区对于整个目标区域的覆盖。此时，需要根据目标区域的轮廓确定的作为网格化起始点的顶点数目不一定限于四个，且各个顶点的坐标需根据目标区域的具体轮廓而定，不一定选择目标区域的坐标最值，而是可能选择目标区域的局部子区域的坐标极值，从而如图2(e)所示，使得约束区的轮廓更加贴合目标区域的各个局部边缘的凹凸状况以最小化网格化的工作量。

下面继续具体讨论分块步骤S30中的网格化子步骤S320的其它示例性实施例。

图3(a)图示出根据图1(a)所示的待处理的多个目标区域中的第二分组30中的目标区域310、320的局部放大示意图，其中在所述第二分组30中的目标区域310、320紧邻；图3(b)图示出针对根据图2(a)所示的第二分组中的目标区域进行网格化分块处理之后的示意图。

如图3(a)所示，存在两个相邻的矩形目标区域310、320且二者如图1(b)所示被划分到同一分组即第二分组30内。若完全遵循如对第一分组10的网格化方式，则需要先对目标区域310、320中的每个分别选定顶点之一确定各自的矩形约束区，再分别对各自的矩形约束区进行网格化。

然而，由于这两个目标区域非常靠近，如图所示为二者间距小于图形处理装置例如扫描电子显微镜的FOV，从而二者的分块步骤可协同进行，包括协同进行限定约束区子步骤S310和协同进行网格化子步骤S320。例如，如图所示，仅需先确定用于其中一个矩形目标区域310的第一矩形约束区，然后再基于该第一矩形约束区延伸出恰好超越或齐平于另一矩形目标区域320边缘的第二矩形约束区，从而不必分别确定各自约束区的起始点，由此仅需确定共同的起始点和各自分别的终止点，减少了工作量。

作为一种具体的实施例，例如，如图3(b)所示，在完成用于目标区域310第一矩形约束区的网格化之后，由于该第一矩形约束区相对于目标区域310在右侧和下侧存在溢出的部分且尺寸在单个单位网格内，则选定该第一矩形约束区的与另一个矩形目标区域320的侧边之一平行延伸且偏移最小的侧边作为共同的网格化起始侧边，并且以该共同起始侧边上的第一矩形约束区的最末单位网格FOV_310-i3-1延伸一个单位作为起点来确定第二矩形目标区域的约束区,并从该起点开始生成对于目标区域320的约束区的第一个单位网格FOV_320-1-1来进行网格化。

类似地，如图1(b)所示，可以近似地对另一第二分组20中的两个目标区域210、220进行网格化。

并且，作为扩展的实施例，也可以在两个以上相毗邻但不相交叠的目标区域之中采用这种协同的网格化，从而仅需仅需确定一个共同的起始点和各自分别的终止点，减少了工作量。

另外，除了如图3(a)和图3(b)所示的单个分组中不同目标区域毗邻但不相交的情况，还存在单个分组中的至少两个目标区域相交的情况，如图4(a)和图4(b)所示。图4(a)图示出待处理的多个目标区域中的第三分组40的目标区域410、420的示意图，其中在所述第三分组中的目标区域相交；图4(b)图示出针对根据图4(a)所示的第三分组40中的目标区域410、420进行网格化分块处理之后的示意图。

如图4(a)所示，在第三分组40中，两个相交的目标区域410和420彼此的相交叠部分表示为410∩420。

作为一种具体的实施例，例如，如图4(b)所示，在完成用于目标区域410的第三矩形约束区的网格化之后，实质上目标区域410与另一目标区域420的交集部分410∩420也已经完成网格化，仅需对目标区域420相对于目标区域410的差集部分进行网格化。具体地，例如选定该第三矩形约束区的跨越其与另一个矩形目标区域420的相交侧边的所有单位网格继续沿着横向和纵向延伸进行网格化，直至达到或超越目标区域420相对于目标区域410的差集部分的所有边缘位置，从而完成对整个第三分组40的网格化。

实质上，为简化对于两个矩形区间410、420的相交边缘的计算/寻址，可以在分组时对目标区域410、420进行预处理，例如，利用二维图形布尔运算拆分至少部分地交叠的目标区域410、420以创建不相交地邻接的多个新的目标区域即差集(410-420)、差集(420-410)、和交集410∩420，即(410-(410∩420))、(420-(410∩420))和410∩420。且所述多个新的目标区域的面积总和等于至少部分地交叠的目标区域410和420在所述图形上的投影面积，即二者并集410∪420。即将二者的并集拆分成三个彼此不相交的区域。并且在此拆分预处理之后，继而例如利用上述如图3(a)和图3(b)图示实施例中的不同目标区域之间协同进行分块步骤的处理来进行网格化，即，仅需先确定三个拆分后的区域之一的约束区，然后在基于该约束区延伸出用于其他两个拆分后的区域的约束区，通过采用这种协同的网格化，从而仅需仅需确定一个共同的起始点和各自分别的终止点，减少了工作量。

通常，这种相交目标区域的拆分预处理例如在分组步骤S20之前执行，从而便于后续仅需前述简单的分块步骤30。

另外，图5(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图，其中存在着与至少一个目标区域相交叠的非目标区域(例如，硅片掩盖层)；图5(b)图示出针对根据图5(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图，并且在分组和网格化分块处理之前进行了移除硅片掩盖层的预处理。

如图5(a)所示，硅片图形类似于图1(a)，区别在于新增了与目标区域310、320部分交叠布置的目标区域410，且所述目标区域410与其它原目标区域110、210、220均远离地间隔开；另外，目标区域410、310、320均被它们之间的掩盖层shield部分地遮蔽。因此，在分组步骤之前，并且也例如在选区步骤之前，需要进行额外的预处理与移除shield的遮盖效果。这种额外的预处理例如是利用二维图形布尔运算来移除充当非目标区域的图示掩盖层shield、和每个目标区域例如410、310和320的与所述非目标区域(图示为shield)相交的部分的图案。在这种移除遮盖的预处理步骤之后，由于形成了新的目标区域，需要新的选取步骤操作S10，如图所示为差集(310-shield)、差集(320-shield)、以及原目标区域410的分别位于shield两侧的部分。进而，如图5(b)所示，在分组步骤S20中，将原目标区域410的位于shield右侧的部分410’单独分为一个第四分组；并且将shield左侧的目标区域即差集(310-shield)、差集(320-shield)、和原目标区域410的位于shield左侧的部分410”分为新的第二分组之一。

更具体地，作为局部放大视图，图6(a)图示出待处理的多个目标区域中的第四分组50中的目标区域的示意图，其中在所述第四分组中的目标区域410’位于掩盖层shield右侧；图6(b)图示出针对根据图6(a)所示的第四分组中的目标区域进行网格化分块处理之后的示意图。

即，如图所示，原目标区域410的分别位于shield两侧的部分相距足够远，分别属于不同分组且使用各自的单位网格进行划分。各自的具体网格化操作如前实施例所述，在此不再赘述。

如上所述移除遮盖的预处理通常需要在对于相交目标区域的拆分预处理和正式的选区步骤S10、分组步骤S20之前执行，因此，例如将移除遮盖的预处理步骤限定为第一预处理步骤，而相应将拆分相交目标区域的预处理步骤限定为第二与处理步骤。

在另外实施例中，例如，图7(a)图示出根据本公开实施例的待处理平面图形上分布的多个目标区域的示意平面图，其与图5(a)所示实施例类似且区别仅在于存在着非矩形的异形形状目标区域；图7(b)图示出针对根据图7(a)所示的多个目标区域进行包括分组和网格化分块处理之后的示意平面图，并且在分组和网格化分块处理之前进行了移除非目标区域的第一预处理。

图7(a)所示实施例与图5(a)类似，区别仅在于以异形的目标区域310’、320’分别代替了之前的矩形目标区域310、320。相应地，如图7(b)所示，新的异形的目标区域310’、320’各自的约束区例如可仍旧选择为如虚线所示的矩形边界框约束区，也可例如选择为实线所示的异形约束区。并且进而以执行如前实施例的网格化处理，单位网格例如选择为与FOV相同或不同的矩形网格；或另外选择为三角形等网格以使得约束区尽可能贴合目标区域310’、320”的边缘轮廓以减少网格数量。在此不再赘述。

综上所述，本公开的实施例的用于二维图形的处理方法，能够基于网格化和图形布尔运算以尽量不重复的方式针对二维图形中的重点区域进行诸如扫描/成像等处理，以及相应地提高针对含有平面图形中的具备有效特征的部位进行处理的图形处理速度。

在本公开的另外的方面实施例中，也提供了一种二维图形扫描装置，其包括扫描器，所述扫描器被配置用以实施如前所述的处理二维图形的方法。例如，常规的扫描仪扫描速度慢，需要机械设备。而基于本公开实施例，现在可以通过光源在物体上投影出明亮的网格进行拍照，使用图像分析软件分析因为物体表面凹凸不平引起的网格的变形，获得要扫描物体表面的3d模型。

在本公开的再一个方面实施例中，还提供了一种电子束检测设备，其旨在用于对诸如硅片等样片的缺陷检测，所述电子束检测设备例如包括电子束成像装置和如前所述的图形扫描装置，其中所述电子束成像装置包括下列至少一个部件：电子束发射源；电子束控制装置；以及扫描偏转器。由于在芯片的电子束扫描检测过程中，使用该方法对检测区域进行分割，可以通过减少扫描次数来有效的降低检测的时间成本，也可以有效的减少因电荷积累导致对邻近区域的成像干扰，提升成像质量。

在本公开的又再一个方面实施例中，作为对于二维图形处理的推广应用，还提供了一种用于地图的地理信息系统，包括：处理器，被配置用于执行根据前述的处理二维图形的方法来选择和处理所述地图上的目标区域，和执行器，被配置用于加载与经处理的所述目标区域相关的信息。在用于地图的地理信息系统中,地图的数据信息是非常庞大的，如果同时呈现所有数据，无论是对单机版程序的数据加载、还是网络版程序的数据传输而言都会造成对于数据处理能力的巨大负担。所以用同样的方法对地图区域进行划分为不同的网格，将地图的区域信息保存在对应的网格中，通过网格定位可以有效的获得查看地区的地图信息，并根据缩放比例等设置选择性的显示，由此提升数据的加载速度或降低数据的网络传输成本。在本公开的又再一个方面实施例中，作为对于二维图形处理的推广应用，还提供了一种用于排版的装置，包括：采集模块，被配置用于获取待排版打印的区域的图形；扫描模块，被配置用于执行根据前述的处理二维图形的方法来对待排版打印的区域的图形进行扫描；和排版模块，被配置用于根据所述扫描器的扫描结果来对于待排版打印的区域进行排版操作。平面排版中，通常将排版区域分割成等距的网格，在此基础上对不同的网格区域进行合并。以本公开实施例为基础生成的版面可以产生整齐的美感。

除了二维图形的处理领域，当前技术的发展也涉及到例如空间扫描和三维图形中的处理，例如3D扫描仪和3D打印机领域中的三维图形处理，类似地也需要以尽量不重复的方式针对终点区域进行诸如空间扫描/成像等处理，以及相应地提高针对空间图形中的具备有效特征的部位进行处理的图形处理速度。

在本公开的另外的实施例中，也提供了用于处理三维图形的方法。

例如，如图8(a)和图8(b)所示，图8(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性目标区域为立方体；图8(b)图示出针对根据图8(a)所示的单个目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位立方体网格。在本公开的一个示例性实施例中，提供一种用于图形处理装置的处理三维图形的方法，与之前用于处理二维平面图形类似，包括以下步骤：

S10’：选区步骤，包括在所述图形(即空间图形/三维图形)上选取多个目标区域(即空间目标区域)；

S20’：分组步骤，包括将所述多个目标区域划分为多个组；

S30’：分块步骤，包括将所述多个组中的每个组划分为多个区块(即三维区块)；和

S40’：提取步骤，包括从每个组的所述多个区块提取至少部分地包含有效特征的期望区块。

经过如上四个主要步骤，能够避免现有技术的三维图形处理过程中由于遍历处理导致的处理时间长和可能重复对相同位置进行处理的缺陷，替代地以位置上不重复的方式对具备有效特征的重点部位进行图形处理，而忽略掉对于不含有效特征的其余部位，从而提高了图形处理效率。

在示例性实施例中，具体地，所述选区步骤S10’中，例如，所述多个目标区域中的每个呈如下空间形状之一：长方体、空间四边形、球体、椭球体、其它空间多面体、和不规则三维异形形状；且如图8(a)所示，其中的单个空间目标区域610中例如优选地为矩形，以便利简化后续处理。

在示例性实施例中，具体地，所述分组步骤S20’包括将所述多个空间目标区域基于各自的分布特点划分为多个组。更具体地，所述分布特点例如是所述多个空间目标区域之间的最小间距，从而能够例如分别基于目标区域之间的分布疏密程度将毗邻定位的若干目标区域划分入同一组内，便利于后续处理中诸如在分块步骤S30’中就近地以相同大小的单位的三维网格连续进行同一组内的空间网格化处理从而简化操作。

另外，在所示多个空间目标区域按照一定规律性重复分布的情况下，所述分布特点还可以例如是所述多个空间目标区域的分布周期性，从而能够对于类似或相同的空间目标区域进行单次的同样处理，减少了对于空间目标区域而言的重复的操作步骤，提高了总体处理效率。另外替代地，所述分布特点还可以例如是由用户以手动方式选取的多个热点区域，从而在经用户观察后发现某些空间目标区域由于例如存在某些特征而需特别关注的情况下，方便对于这些需特别关注的空间目标区域的优先处理，从而有效将自动化流程与人工决策相接合以进行有效的分组操作。

在本公开的进一步的实施例中，例如如图8(b)所示，所述分块步骤S30’例如具体包括如下子步骤：

S310’：即限定约束区子步骤，其中，确定包含每个组中的空间目标区域的约束区即包围盒；和

S320’：即网格化子步骤，其中，拼接单位的三维网格以形成覆盖所述约束区的多个三维区块，其中每个所述单位的三维网格充当所述多个三维区块中的单个。

在示例性实施例中，具体地，所述限定约束区子步骤S310’中，例如，所述约束区可以是包围所述每个组的目标区域的任何封闭的包围盒，优选地例如是包围所述每个组的目标区域的最小化的封闭的包围盒。所限定的包围盒所占据体积越小，则相应地后续在子步骤S320中进行网格化处理的过程中所需的处理量越少，从而最小化的封闭的包围盒对应于相对较小的空间网格化处理量。

进一步地，例如，如图8(a)所示，对于仅包含空间目标区域610的分组，由于空间目标区域610本身呈矩形，则用于包围该分组的目标区域的最小化的封闭的包围盒可例如视为空间目标区域本身。

在示例性实施例中，如图8(b)所示，所述网格化子步骤S320’例如包括：所述单位的三维网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在空间直角坐标系的相互正交的三个方向，例如纵向、横向和竖向上均齐平和/或超出所述包围盒式约束区的边界。

所述单位的三维网格是被定义用以划分图形的单位。例如，为处理简单和减少网格化的工作量起见，用于划分每个组的各自单位网格呈相同的形状和大小。

优选地，由于对任何空间立体图形进行网格化时，例如在诸如有限元分析等图形细分的过程中，往往采用均一的空间四面体或长方体的单位三维网格来进行网格化，以便利于利用单位三维网格之间仅边缘抵紧或贴合的方式来不重复地进行网格化，即单位网格之间不存在体积的交叠，从而避免了由于网格化过程中由于单个部位处重复被网格化而导致的冗余工作量。

类似地，图9(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性目标区域为长方体；图9(b)图示出针对根据图9(a)所示的单个目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位四面体网格。

由此，例如，如图8(b)和图9(b)所示，所述拼接单位三维网格以形成覆盖所述目标区域610、610’的包围盒式约束区的多个三维区块包括：所述单位网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在空间直角坐标系的纵向、横向好竖向均齐平和/或超出所述约束区的边界。其中，如图8(b)所示，所述单位的三维网格例如呈均一的长方体形状的单位三维网格。而如图9(b)所示，基于对尽量少的网格化工作量和仅边缘交叠的要求的折衷考虑，所述单位网格，图示为呈均一的立体四面体单位网格，例如从空间目标区域610的约束区中的目标区域分布最密集点(例如远侧左上角)开始，开始在其所在的空间直角坐标系中分别沿着X、Y、Z三个主方向(即图中的横向、纵向和竖向)以边缘抵紧或贴合的方式延伸以覆盖所述目标区域610’的包围盒约束区。

作为更具体的实施例，例如由于对物体进行三维检测/扫描时通常利用3D扫描仪进行，因而进行网格化的单位三维网格实质上受到3D扫描仪的视场所施加的物理限制，从而，例如，每个所述单位三维网格被配置呈尺寸等于所述图形处理装置例如3D扫描仪的视场FOV三维尺寸，或其能够以一定精确度感测到的最大三维形体的尺寸。且单位三维网格例如从作为空间目标区域的包围盒约束区中的空间目标区域分布最密集点开始延伸，例如以三个主方向上交替进行的方式进行网格化直至整个包围盒约束区的最后一个角落的边界被首次超出，从而实现全部单位三维网格的整体完全覆盖包围盒约束区。并且，还存在一种替代的实施例，即单个约束区恰好包括在X-Y平面中成行且成列布置且在Z方向上呈均一高度的空间网格阵列，而没有网格超出其边界的范围，即所有网格的整体的边缘恰好与包围盒约束区的边缘齐平，从而也实现全部单位三维网格的整体完全覆盖约束区。

此外，关于网格化的具体操作方式，作为替代的实施例，也可逐行、逐列、逐层高度地进行空间网格化，直至在空间直角坐标系的三个主方向均齐平和/或超出所述包围盒约束区的全部边界，从而实现单位三维网格整体完全覆盖约束区。

并且，作为示例性的实施例，在确定空间目标区域的约束区的各个角落处的顶点位置时，例如所述每个组的所述最小化的封闭的包围盒被配置成其各个顶点的坐标分别为所述每个组中的空间目标区域在不同坐标轴上的坐标最值的组合。由此，通过确定顶点的坐标，可以确定例如典型地呈长方体的空间目标区域；且由于任何空间形状的区域可以由一个长方体包围约束，则也可以通过以上方式确定长方体约束区的顶点的坐标，来表征任何空间形状的空间目标区域的长方体约束区。

并且，对每个待检测的空间目标区域的分组重复上一步骤，直到所有分组中的空间目标区域均被空间网格化分割完毕。

下面继续具体讨论提取步骤S40’。

在示例性实施例中，具体地，所述提取步骤S40’例如包括利用二维图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块。

在本公开的进一步的实施例中，与平面图形的处理方法中的提取步骤类似，用于空间图形的有效三维区块的所述提取步骤S40’例如具体包括如下子步骤：

S410：求取交集子步骤，即在每个组的包围盒约束区中，利用三维图形布尔运算获取所述多个三维区块与所述每个组中的包含有效特征的部位的多个交集；和

S420：去除非空交集子步骤，即选取所述多个交集中的非空交集为所述期望区块，且移除所述多个交集中的空交集。

这种在空间网格化之后利用各个空间网格化的三维区块与相邻的至少部分含有有效信息的区块进行求取交集来提取期望区块的方法，相比于常规的直接基于大的三维图形来提取其边缘的局部处的期望区块的方法，能够充分利用网格化的划分造成的精细视场，从而处理图形的分辨率更精细；并且由于采用三维图形布尔运算，使得处理简化直观，减少了工作量。

额外地，在示例性实施例中，所述用于图形处理装置的处理图形的方法还包括步骤S50’，即归集步骤，包括在提取步骤S40’之后，将经划分的每个组中的所述有效三维区块置入单一的集合而保存，且在需要图形处理时输出。从而可以得到直观的图形的整体有效信息分布、而有效去除无效信息的图形部位。

下面进一步讨论扩展实施例。

作为替代的可选实施例，可以针对所述多个组中的每个组采用不同的单位三维网格，例如不同形状和/或尺寸。则相应地，也可根据与目标区域的轮廓的边界仿形的非规则的约束区，从而实际上有可能以比长方体形包围盒式约束区更少的工作量实现约束区对于整个目标区域的覆盖。此时，需要根据目标区域的轮廓确定的作为网格化起始点的顶点数目不一定限于八个，且各个顶点的坐标需根据目标区域的具体轮廓而定，不一定选择目标区域的坐标最值，而是可能选择目标区域的局部子区域的坐标极值，使得包围盒约束区的轮廓更加贴合空间目标区域的各个局部边缘的轮廓凹凸状况以最小化空间网格化的工作量。

并且，作为替代的可选实施例，由于三维图形占据一定空间体积，而在三维扫描/观测中，其内部的情况并非考察对象，从而仅需要在三维图像表面附近进行空间网格化。而由于图形领域的几何常识可知，任何空间立体形状可以由细分的空间四面体构成，从而，例如采用呈空间四面体形状的单位三维网格来进行对于三维图形对象的涵盖其表面的单层空间网格化，从而可根据与空间目标区域的表面轮廓的边界仿形的非规则的约束区，实际上有可能以比对于三维图形进行从外至内的整个空间体积的网格化更少的工作量来实现对于整个空间目标区域的覆盖。

图10(a)图示出根据本公开实施例的待处理空间图形上的一个示例性目标区域的示意平面图，所述示例性空间目标区域710为圆柱体；图10(b)图示出针对根据图10(a)所示的单个空间目标区域进行包括分组和网格化分块处理之后的示意平面图，其中用于网格化分块的单位网格是单位四面体网格；和图10(c)图示出图10(b)所示的经网格化分块处理之后的目标区域分组的示意图，其中包络有未处理前的所述圆柱体形的目标区域。例如如图所示，能够仅在圆柱体对象的表面附近进行仿形的单层网格化以覆盖其整个空间形体的表面，从而最小化其空间网格化的工作量。

在另外的实施例中，在同一分组的不同空间目标区域至少部分地相交以具备共有占据的空间体积的情况下，为简化处理器件，例如还进行预处理。具体地，可以例如利用三维图形布尔运算拆分至少部分地交叠的空间目标区域以创建不相交地邻接的多个新的空间目标区域，且所述多个新的目标区域的体积总和等于至少部分地交叠的目标区域在所述三维图形中的并集的体积。

并且在此拆分预处理之后，获得在空间上不存在共同占据的交叠体积的空间目标区域。

在本公开的示例实施例中，对于在空间上不交叠的空间目标区域而言，可以例如利用与前述用于处理平面图形的实施例中的不同空间目标区域之间协同进行分块步骤的类似处理来进行空间网格化，即，仅需先确定所述多个拆分后的空间目标区域之一的包围盒约束区，然后在基于该包围盒约束区延伸出用于其他的经拆分后的空间目标区域的约束区，通过采用这种协同的空间网格化，从而仅需仅需确定一个共同的起始点和各自分别的终止点，减少了工作量。

通常，这种相交的空间目标区域的拆分预处理例如在分组步骤S20’之前执行，从而便于后续仅需前述简单的分块步骤30’。

综上所述，本公开的实施例的用于三维图形的处理方法，能够基于空间网格化和三维图形布尔运算以尽量不重复的方式针对三维图形中的重点区域进行诸如扫描/成像等处理，特别是仅对三维图形进行表面附近的单层空间网格化，来相应地提高针对含有三维图形中的具备有效特征的部位进行处理的图形处理速度。

在本公开的另外的方面实施例中，也提供了一种三维图形扫描装置，其包括扫描器，所述扫描器被配置用以实施如前所述的处理三维图形的方法。由此，所述三维图形扫描装置具备与所述方法相同的优点，在此不再赘述。

在本公开的又一个方面实施例中，还提供了一种电子设备，包括：存储器，用于存储可执行指令；和处理器，用于执行存储器中存储的可执行指令，以执行根据前述的处理图形的方法。由此，所述电子设备具备与所述方法相同的优点，在此不再赘述。

在本公开的再一个方面实施例中，还提供了一种用于布设目标物(例如用于铺设地面/墙面装修材料、用于农田播种)的装置，包括：采集器，被配置用于获取待布设目标物的区域的图形，例如二维平面或三维形貌；扫描器，被配置用于执行根据前述的方法来对待布设目标物的区域的图形进行扫描；和执行器，根据所述扫描器的扫描结果布设目标物。例如在装修中，通常大量使用壁砖、地板砖等装修材料；而在实际操作中，对这一类材料往往是对固定图案的重复使用，错误的排布方式可能会在消耗更多的装修材料同时、也造成装修图案排布不美观。而通过使用本公开实施例的方案对装修区域进行划分可有效的降低装修成本，使得最终形成的装修区域美观。且设施农业中，往往需要对种植地区进行大量的建设以提升种植的自动化水平，而利用本公开实施例，通过全局网格的办法划分种植区域，按照不同区域内部的面积，形状可以有效的提升设备的使用效率，降低投资成本。

在本公开的再又一个方面实施例中，还提供了一种用于区域统计的设备，包括：采集器，被配置用于获取待统计的二维或三维区域的图形；扫描器，被配置用于执行根据前述的方法来对待统计的区域的图形进行扫描；和计算装置，被配置用于根据所述扫描器的扫描结果通过计算来进行对于待统计的区域的统计操作。现实生产中，存在大量和地理信息相关的统计操作，比如分析某个城市特定区域的交通拥堵信息，分析某个粮食种植区的产量信息等等。这些信息在分布上的具体位置往往存在比较大的关系。基于本公开实施例，按全局网格的方法将统计地区分割为不同的区域，并针对不同区域分别统计，能获得更多的有用信息。

综上，本公开实施例提供的技术方案带来的有益效果是：

首先，所述方法和所述装置从整体上来考虑区域的分割，避免传统单个区域分割的计算难度。

继而，所述方法和所述装置的计算时间只与在区域边缘处外接的例如呈矩形的封闭包围盒的大小有关，降低了对区域的分布的依赖性

并且，所述方法的编程简单，易于实现。

进而，所述方法和所述装置对区域的矩形分割采用图形布尔运算实现，简单易行，且节省运算量。

此外，所述方法易于扩展，可应用在众多应用场景中。

另外，根据前述的本公开实施例可以理解，经由任意两种或两种以上的组合的任何技术方案，也落入本公开的保护范围内。

本公开的实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各实施例之间相同相似的部分互相参见即可。

以上所述仅为本发明的优选实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (22)

1.一种用于图形处理装置的处理图形的方法，其中，所述方法包括：

在所述图形上选取多个目标区域；

将所述多个目标区域划分为多个组；和

将所述多个组中的每个组划分为多个区块，包括：

确定包含每个组中的目标区域的约束区；

拼接单位网格以形成覆盖所述约束区的多个区块，其中每个所述单位网格充当所述多个区块中的单个区块；和

从每个组的所述多个区块提取至少部分地包含有效特征的期望区块，

其中，

在所述图形是二维图形的情况下，所述约束区是包围所述每个组的目标区域的最小化的封闭的边界框；或

在所述图形是三维图像的情况下，所述约束区是包围所述每个组的的目标区域的最小化的封闭的包围盒。

2.根据权利要求1所述的方法，其中，从每个组的所述多个区块提取至少部分地包含有效特征的期望区块的步骤包括：利用图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块。

3.根据权利要求2所述的方法，其中，利用图形布尔运算从所述多个区块中选取至少部分地包含有效特征的期望区块包括：

在每个组的约束区中，利用图形布尔运算获取所述多个区块与所述每个组中的包含有效特征的部位的多个交集；和

选取所述多个交集中的非空交集为所述期望区块，且移除所述多个交集中的空交集。

4.根据权利要求2或3所述的方法，其中，在所述图形是二维图形的情况下，所述图形布尔运算是二维图形布尔运算；或

在所述图形是三维图形的情况下，所述图形布尔运算是三维图形布尔运算。

5.根据权利要求1所述的方法，还包括：

在从每个组的所述多个区块提取至少部分地包含有效特征的期望区块之后，将经划分的每个组中的所述期望区块置入单一的集合。

6.根据权利要求1所述的方法，其中，在所述图形是二维图形的情况下，所述多个目标区域中的每个呈如下平面形状之一：矩形、三角形、圆形、椭圆形、其它多边形、和不规则平面异形形状；或

在所述图形是三维图形的情况下，所述多个目标区域中的每个呈如下空间形状之一：长方体、空间四边形、球体、椭球体、其它空间多面体、和不规则三维异形形状。

7.根据权利要求1所述的方法，其中，所述将所述多个目标区域划分为多个组包括：将所述多个目标区域基于各自的分布特点划分为多个组。

8.根据权利要求7所述的方法，其中，所述分布特点包括以下至少之一：所述多个目标区域之间的最小间距，所述多个目标区域的分布周期性，经选取的多个热点区域。

9.根据权利要求1所述的方法，其中，

所述拼接单位网格以形成覆盖所述约束区的多个区块包括：所述单位网格被布置成以边缘抵紧或贴合的方式彼此拼接以进行覆盖，直至在坐标系的各个坐标轴的方向上均齐平和/或超出所述约束区的边界。

10.根据权利要求1所述的方法，其中，用于划分每个组的各自单位网格呈相同的形状和大小。

11.根据权利要求10所述的方法，其中，在所述图形是二维图形的情况下，每个所述单位网格呈矩形；或

在所述图形是三维图形的情况下，每个所述单位网格呈空间四面体或长方体。

12.根据权利要求11所述的方法，其中，在所述图形是二维图形的情况下，每个所述单位网格被配置呈小于或长度等于所述图形处理装置的视场的横向长度、且宽度小于或等于所述图形处理装置的视场的纵向长度的矩形；

在所述图形是三维图像的情况下，每个所述单位网格被配置呈三维尺寸被限定为小于或等于所述图像处理装置的视场范围的空间四面体或长方体。

13.根据权利要求1所述的方法，其中，所述每个组的所述最小化的封闭的边界框或包围盒被配置成其各个顶点的坐标分别为所述每个组中的目标区域在不同坐标轴上的坐标极值的组合。

14.根据权利要求1所述的方法，还包括：在将所述多个目标区域划分为多个组之前，对所述多个目标区域进行预处理，包括以下至少之一：

第一预处理，其中利用图形布尔运算移除非目标区域和每个目标区域的与所述非目标区域相交的部分的图案；和

第二预处理，其中利用图形布尔运算拆分至少部分地交叠的目标区域以创建不相交地邻接的多个新的目标区域，且所述多个新的目标区域的面积总和等于至少部分地交叠的目标区域在所述图形上的投影面积。

15.一种图形扫描装置，包括：

扫描器，用于执行根据权利要求1至14中任一项所述的方法。

16.一种电子束检测设备，包括：

根据权利要求15所述的图形扫描装置，和

电子束成像装置，包括下列至少一个部件：

电子束发射源；

电子束控制装置；以及

扫描偏转器。

17.一种电子设备，包括：

存储器，用于存储可执行指令；和

处理器，用于执行存储器中存储的可执行指令，以执行根据权利要求1至14中任一项所述的方法。

18.一种图形处理装置，包括：

执行器，用于执行根据权利要求1至14中任一项所述的方法。

19.一种用于地图的地理信息系统，包括：

处理器，被配置用于执行根据权利要求1至14中任一项所述的方法来选择和处理所述地图上的目标区域，和

执行器，被配置用于加载与经处理的所述目标区域相关的信息。

20.一种用于布设目标物的装置，包括：

采集器，被配置用于获取待布设目标物的区域的图形；

扫描器，被配置用于执行根据权利要求1至14中任一项所述的方法来对待布设目标物的区域的图形进行扫描；和

执行器，根据所述扫描器的扫描结果布设目标物。

21.一种用于区域统计的设备，包括：

采集器，被配置用于获取待统计的区域的图形；

扫描器，被配置用于执行根据权利要求1至14中任一项所述的方法来对待统计的区域的图形进行扫描；和

计算装置，被配置用于根据所述扫描器的扫描结果通过计算来进行对于待统计的区域的统计操作。

22.一种用于排版的装置，包括：

采集模块，被配置用于获取待排版打印的区域的图形；

扫描模块，被配置用于执行根据权利要求1至14中任一项所述的方法来对待排版打印的区域的图形进行扫描；和

排版模块，被配置用于根据所述扫描模块的扫描结果来对于待排版打印的区域进行排版操作。

Images