毕业设计外文资料翻译-BOLB分析

1、毕业设计外文资料翻译学 院： 专业班级： 学生姓名： 学 号： 指导教师： 外文出处：T.B. Moeslund, Introduction to Video and Image Processing,Undergraduate Topics in Computer Science,DOI 10.1007/978-1-4471-2503-7_7,Springer-Verlag London Limited 2012附 件：1.外文资料翻译译文； 2.外文原文 指导教师评语：该生的外文翻译与本次的毕业设计内容有一定的关联性，翻译文章通顺，语法正确，工作量也达到了要求的内容。签名： 2015年10

2、月14日外文资料翻译译文 BOLB分析在描述本章陌生的标题是什么意思之前，让我们先看一些例子。第一个例子的任务是设计一个可以算出呈现在左边的图片（见图7.1）上有多少个圆的算法，显而易见，答案是三个，但是我们该怎么让电脑算出它？另一个例子就是计算出右边的图片上任务的位置，我们该怎么让电脑计算出这个？这两个问题的答案是双重的。首先，我们需要将图片上不同的元素分离开，然后分别评估哪个元素是我们例子中要找的圆和人。前过程又名BLOB提取，后者又称BLOB分类。BLOB代表二进制大对象（Binary Large OBject），指一组在二进制图像中相连的像素点。“大”一词表明只有一定规模的对象才包括，

3、小的二进制对象通常是忽略。本章的题目指的是分析二进制图像，分析二进制图像的过程是，首先提取BLOBs，接着简洁得描述他们，最后对每个BLOB进行分类。以下是对这三个话题进行详细的描述。7.1 BLOB 提取提取BLOB的目的是为了将二进制图像上的BLOB对象隔离开来。如上所述，一个BLOB由一组相连的像素点构成。是否两个像素点被连接是被连接性定义的，也就是说，哪些是相邻的，哪些又不是。图7.2显示的是两个最常见的应用类型的连接。八连接比四连接更精确，但是四连接却因为它需要更少的计算而被经常应用。这两个不同类型连接的效果被显示在图7.2，图7.2中显示二进制图像包含一个还是两个BLOBs这取决于

4、连接性。存在许多不同的算法用来找到BLOBs，这些算法通常被称为连接成分分析或连接组件标签。接下来，我们描述其中一种著称为Grass-fire的算法。简单起见，我们使用四连接。T.B.Moeslund，介绍视频和图像处理，本科主题计算机科学，DOI10.1007/978-1-4471-2503-7_7，施普林格出版社伦敦有限公司2012图7.1 (a)是一个二进制图像包含不同的图形，(b)是一个二进制图像包含一个人和一些杂质。图7.2 四连接和八连接，应用这两个不同类型连接的效果提取BLOBs图像连接提取BLOBs图像连接7.1.1 循环的 GRASS-FIRE算法这个算法开始于二进制图像的左

5、上角，然后从左到右从上到下扫描整张图像，如图4.28。当扫描一个对象的像素点（白色的像素点）的某一时刻，GRASS-FIRE算法的概念开始发挥作用。在二进制图像7.3中在坐标（2,0）上发现第一个对象像素点。在这个点上你应该想象自己站在一个覆盖着干燥的草的地方。想象自己有四个手臂并且每个手都拿着一根燃烧着的火柴。朝四个不同的地方伸出你的手臂（与四连接中相邻的相一致）同时扔掉燃烧的火柴，当他们碰到干燥的草，他们将会开始燃烧并且向四个新的方向（上下左右）再次传播等。其结果是每个连接到你处事位置的稻草将会燃烧。这就是GRASS-FIRE的本质。需要注意的是，如果草地包含一条河流那么另一边的草地将不会

6、被燃烧。返回到我们的二进制图像，对象像素点是干草，非对象像素点的是河流。所以，这个算法从四个不同的方向看，如果它看到一个可以被燃烧的像素点，说明它是一个对象像素点，它做两件事。首先，在输出的图像中，它获得这个对象的像素点（基本上很多），然后它在输入的图像中通过将它置为0（白色）燃烧像素点。将它置为0表明它已经被燃烧了并且不会是另一个火的一部分。在真实的草地上，这个火将会同时向所有方向传播。但是在电脑中，我们只能每次进行一个动作，GRASS-FIRE就是如下进行的。让我们应用图7.3的原理，在坐标（2,0）位置的像素点被标号为1，这是因为它是第一个BLOB然后燃烧（在右下角标记为1）。然后这个算

7、法通过判断这个是否对象像素点尝试在第一个相邻像素点（3，0）处开始燃烧。如果它是确实是一个对象像素点并因此被标记为1（同一个对象）燃烧。因为（3,0）是一个对象像素点所以它现在变成了注意的中心并且它的第一个相邻的坐标是（4,0）.再次重复，直到（4,0）的第一个相邻点已经在图像外边，因此每个定义都不是一个对象的像素点，因此该算法会继续调查它的第二个相邻的点（4,1）。它不是一个对象像素点并且（3，0）是（4,0）的第三个像素点。这已经被燃烧并且没有比它更远的对象像素点了。然后（4,0）最后的相邻点是（4，-1），它已经在图像外面因此不是一个对象像素点。（4,0）所有相邻的点现在都已经被调查过了

8、，算法因此追溯并着眼于（3,0）的第二个相邻点（3,1），这是一个对象像素点因此被标记为1并且燃烧变成新的中心。用这种方式，这个算法同样找到（3,2）也是第一个对象的一部分，最终在调查第四个相邻点（2,0）的时候终止。图7.3 GRASS-FIRE算法，大的数字表示相邻的访问的顺序，小的数字表示像素点的标签。所有最上面的对象的像素点现在都已经被做了同样的标记1，这意味着这个BLOB已经被隔离出来了。这个算法继续按照图4.28扫描路径移动，直到遇见下一个对象像素点（1,3），这个点将会被标记为2并且开始一个新的GRASS-FIRE。图7.2显示的就是结果，每一个BLOB都有一个唯一的标识。图7.

9、4的BLOBs就是图7.1中提取出来的，颜色是根据他们的BLOB标签来确定的。一个方法调用自己来有效的实现这个算法。这样的算法被称为递归，这种算法需要注意的是，要保证作为没有内置终端战略的递归算法能够被正常的终止。还有另一个安全隐患，那就是电脑分配给方法调用的内存有限。因为GRASS-FIRE算法可能有成千上万的方法进行排列，电脑可以运行分配的内存。图4.28 访问像素点的顺序。以10*10的图像举例 图7.4两个提取BLOBs的例子，每一个BLOB都有一个唯一的颜色。7.1.2 连续的GRASS-FIRE算法GRASS-FIRE算法也可以通过连续的方式实现。从编程的角度来看，这种方式效率低，

10、但是这不是由递归的GRASS-FIRE算法中提交的问题引起的。连续的GRASS-FIRE算法同样是从上到下从左到右扫描图像。当发现一个对象扫描点的时候，它会做两件事，第一，在输出的图像中它会得到一个对象像素点标记为1，然后燃烧输入的图像的像素点（将它标记为0），第二件事是查看相邻的点（4个或8个取决于连接性），看是否其中有对象像素点。到目前为止这是跟递归的GRASS-FIRE算法完全一样的，但是接下来就会出现不同了。任何一个是对象像素点的点在输出图像上都会被标记为1，在输入图像上都会被标记为0。同时，它们被显示在一个列表中。接着，获取列表中的第一个像素点并且查看它们的相邻点，如果是对象像素点它

11、们就会在输出中被标记，在输入中被标记为0并且放置在列表中，这个步骤直到列表中所有像素点都被调查过就结束。直到遇到下一个对象像素点，这个算法将一直按照图4.28的顺序执行，然后标记为2并且开始新的GRASS-FIRE。7.2 GRASS-FIRE特性当面临图7.1的例子时，提取BLOBs是第一步。接下来就是对不同的BLOBs进行分类。用圆来举例，我们想要分出每一个是圆或不是圆的BLOBs。从另一个例子来看，就是人或者不是人的BLOBs。这个分类的过程包括两步。首先，一系列的特征代表一个BLOB，这是代表特点，第二，应用一些匹配的方法来比较每个BLOB的特点和我们预期的对象的特点有什么异同。举个例

12、子来说，为了找到圆形，我们需要计算每个BLOB的圆，并且把它和一个完美的圆作比较。接下来，我们将演示如何提取不同的特性，在下一个章节会演示如何去比较这些特性。提取特性即，将每一个BLOB转换成一系列的代表性的数字，就是保存相关信息并且忽略其他。但是在计算每个特性之前，我们需要配出每个连接到图像边界的BLOB。这是因为，通常来说，我们没有任何有关在图像外的对象的部分的信息。举个例子，在图7.1中，这个半圆从人的右边的角度来看有可能就是个圆，但是它也可能是躺着的人的头顶。因此，需要排除这些BLOBs。像这样做，每个BLOB的一系列特性就会被计算出来。下面显示着大多出普遍的特性的描述，但是有一些其他

13、的存的的或者是新的也可以被定义。1、一个BLOB的面积是大多数BLOB都有的特性。这个特性通常被用来从图像中移动一些非常小或非常大的BLOBs。举例说明，在图7.1中，通过忽略所有比特定大小更小的BLOB，人就可以被简单的分离出来。2、一个BLOB的边界框是包含着BLOB的最小的长方形，如图7.5。它分别通过穿过一个BLOB的所有像素点并且找到坐标x,y的最大最小值的方法被定义。从这些值中可以获取边界框的长（X的最大值最小值）和宽（Y的最大值最小值）。一个边界框可以被用来作为一个ROI。3、一个BLOB的边界圆是一个包含着BLOB的最小的圆，如图7.5。首先，通过下面描述的任意一种方法定位BL

14、OB的中心，接着，我们从中心向一个方向往外开始搜索直到找到BLOB结束的点。这个点到中心点的距离是在这个方向的半径。对所有可能的方向我们都做这个操作（例如10%的角分辨率），最长的半径就是这个最小的圆的半径。 图7.5 （a）边界框 （b）边界圆 （c）凸壳外文原文BLOB AnalysisBefore describing what is meant by the somewhat strange title of this chapter, let us look at a few examples. In the first example the task is to design a

15、n algorithm which can figure out how many circles are present in the image to the left (see Fig. 7.1).Obviously the answer is three, but how will we make the computer figure this out?Another example could be to find the position of the person in the image to the right. How can we make the computer c

16、alculate this? The answer to both questions is twofold. First we have to separate the different objects in the image and then we have to evaluate which object is the one we are looking for, i.e., circles and humans, respectively. The former process is known as BLOB extraction and the latter as BLOB

17、classification. BLOB stands for Binary Large OBject and refers to a group of connected pixels in a binary image. The term “Large” indicates that only objects of a certain size are of interest and that “small” binary objects are usually noise.The title of the chapter refers to analyzing binary images

18、 by first extracting the BLOBs, then representing them compactly, and finally classifying the type of each BLOB. These three topics are described in more detail below.7.1 BLOB ExtractionThe purpose of BLOB extraction is to isolate the BLOBs (objects) in a binary image.As mentioned above, a BLOB cons

19、ists of a group of connected pixels. Whether or not two pixels are connected is defined by the connectivity, that is, which pixels are neighbors and which are not. The two most often applied types of connectivity are illustrated in Fig. 7.2. The 8-connectivity is more accurate than the 4-connectivit

20、y, but the 4-connectivity is often applied since it requires fewer computations, hence it can process the image faster. The effect of the two different types of connectivity is illustrated in Fig. 7.2 where the binary images contain either one or two BLOBs depending on the connectivity. A number of

21、different algorithms exist for finding the BLOBs and such algo rithms are usually referred to as connected component analysis or connected com ponent labeling. In the following we describe one of these algorithms known as the Grass-fire algorithm. We use 4-connectivity for simplicity. T.B. Moeslund,

22、 Introduction to Video and Image Processing,Undergraduate Topics in Computer Science,DOI 10.1007/978-1-4471-2503-7_7, Springer-Verlag London Limited 2012Fig. 7.1 (a) A binary image containing different shapes. (b) A binary image containing a human and some noise.Fig. 7.2 4- and 8-connectivity. The e

23、ffect of applying the two different types of connectivity7.1.1 The Recursive Grass-Fire AlgorithmThe algorithm starts in the upper-left corner of the binary image. It then scans the entire image from left to right and from top to bottom, as seen in Fig. 4.28.At some point during the scan an object p

24、ixel (white pixel) is encountered and the notion of grass-fire comes into play. In the binary image in Fig. 7.3 the first object pixel is found at the coordinate (2, 0). At this point you should imagine yourself standing in a field covered with dry grass. Imagine you have four arms (!) and are holdi

25、ng a burning match in each hand. You then stretch out your arms in four different directions (corresponding to the neighbors in the 4-connectivity) and simultaneously drop the burning matches. When they hit the dry grass they will each start a fire which again will spread in four new directions (up,

26、 down, left, right) etc.The result is that every single straw which is connected to your initial position will burn. This is the grass-fire principle. Note that if the grass field contains a river the grass on the other side will not be burned.Returning to our binary image, the object pixels are the

27、 “dry grass” and the nonobject pixels are water. So, the algorithm looks in four different directions and if it finds a pixel which can be “burned”, meaning an object pixel, it does two things.Fig. 7.3 The grass-fire algorithm. The “big” numbers indicate the order in which the neighbors are visited.

28、 The small numbers indicate the label of a pixel. Firstly, in the output image it gives this pixel an object label (basically a number) and secondly it “burns” the pixel in the input image by setting it to zero (black). Setting it to zero indicates that it has been burned and will therefore not be p

29、artof yet another fire. In the real grass field the fire will spread simultaneously in all directions. In the computer, however, we can only perform one action at the time and the grass-fire is therefore performed as follows.Let us apply the principle on Fig. 7.3. The pixel at the coordinate (2, 0)

30、is labeled 1, since it is the first BLOB and then burned (marked by a 1 in the lower right corner). Next the algorithm tries to start a fire at the first neighbor (3, 0), by checking if it is an object pixel or not. It is indeed an object pixel and is therefore labeled 1 (same object) and “burned”.

31、Since (3, 0) is an object pixel, it now becomes the center of attention and its first neighbor is investigated (4, 0). Again, this is an object pixel and is therefore labeled 1, “burned” and made center of attention. The first neighbor of (4, 0) is outside the image and therefore per definition not

32、an object pixel. The algorithm therefore investigates its second neighbor (4, 1). This is not an object pixel and the third neighbor of (4, 0) is therefore investigated (3, 0). This has been burned and is therefore no longer an object pixel. Then the last neighbor of Fig. 7.4 Two examples of extract

33、ed BLOBs. Each BLOB has a unique color (4, 0) is investigated (4,1). This is outside the image and therefore not an object pixel. All the neighbors of (4, 0) have now been investigated and the algorithm therefore traces back and looks at the second neighbor of (3, 0), namely (3, 1). This is an objec

34、t pixel and is therefore labeled 1, burned and becomes the new focus of attention. In this way the algorithm also finds (3, 2) to be part of object 1 and finally ends by investigating the fourth neighbor of (2, 0).All pixels which are part of the top object have now been labeled with the same label

35、1 meaning that this BLOB has been segmented. The algorithm then moves on following the scan path in Fig. 4.28 until it meets the next object pixel (1, 3), which is then labeled 2, and starts a new grass-fire. The result will be the image shown in Fig. 7.2, where each BLOB has a unique label. In Fig.

36、 7.4 the BLOBs from Fig. 7.1 have been extracted and color coded according to their BLOB label.The algorithm can be implemented very efficiently by a function calling itself. Such an algorithm is said to be recursive and care should be taking to ensure the program is terminated properly as recursive

37、 algorithms have no built-in termination strategy. Another danger is that a computer has a limited amount of memory allocated to function calls. And since the grass-fire algorithm can have many thousands function calls queued up, the computer can run out of allocated memory.7.1.2 The Sequential Gras

38、s-Fire AlgorithmThe grass-fire algorithm can also be implemented in a sequential manner. This is less efficient from a programming point of view, but it does not suffer from the problems mentioned above for the recursive grass-fire algorithm.The sequential grass-fire algorithm also scans the image f

39、rom top left to bottom right. When an object pixel is found it does two things. Firstly, in the output image it gives this pixel an object label, 1, and secondly it “burns” the pixel in the input image by setting it to zero (black). The next step is to check the neighbors (four or eight pixels depen

40、ding on the connectivity) and see if any of them is an object pixel. So far this is exactly the same as the recursive grass-fire algorithm, but now comes the difference. If any of the neighbors is an object pixel they are labeled 1 in the output image and set to zero (burned) in the input image. Als

41、o, they are placed in a list. Next step is to take the first pixel in the list and check its neighbors. If any are object pixels they are labeled in the output, set to zero in the input and placedin the list. This is continued until all pixels in the list have been investigated. The algorithm then c

42、ontinues following the scan path in Fig. 4.28 until it meets the next object pixel, which is then labeled 2, and starts a new grass-fire.7.2 BLOB FeaturesExtracting the BLOBs is the first step when confronted with examples like those presented in Fig. 7.1. The next step is now to classify the differ

43、ent BLOBs. For the example with the circles, we want to classify each BLOB as either a circle or not a circle, and, for the other example, human vs. non-human BLOBs. The classification process consists of two steps. First, each BLOB is represented by a number of characteristics, denoted features, an

44、d second, some matching method is applied to compare the features of each BLOB with the features of the type of object we are looking for. For example, to find circles we could calculate the circularity of each BLOB and compare that to the circularity of a perfect circle. Below we will present how w

45、e can extract different features and in the next section then show how to compare features.Feature extraction is a matter of converting each BLOB into a few representative numbers. That is, keep the relevant information and ignore the rest. But before calculating any features we first want to exclude every BLOB which is connected to the border of the image. The reason is that we in general have no info