数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.doc

《数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.doc》由会员分享，可在线阅读，更多相关《数字图像处理 外文翻译 外文文献 英文文献 数字图像处理.doc（11页珍藏版）》请在三一办公上搜索。

1、 Digital Image Processing1 IntroductionMany operators have been proposed for presenting a connected component n a digital image by a reduced amount of data or simplied shape. In general we have to state that the development, choice and modi_cation of such algorithms in practical applications are dom

2、ain and task dependent, and there is no best method. However, it is interesting to note that there are several equivalences between published methods and notions, and characterizing such equivalences or di_erences should be useful to categorize the broad diversity of published methods for skeletoniz

3、ation. Discussing equivalences is a main intention of this report.1.1 Categories of MethodsOne class of shape reduction operators is based on distance transforms. A distance skeleton is a subset of points of a given component such that every point of this subset represents the center of a maximal di

4、sc (labeled with the radius of this disc) contained in the given component. As an example in this _rst class of operators, this report discusses one method for calculating a distance skeleton using the d4 distance function which is appropriate to digitized pictures. A second class of operators produ

5、ces median or center lines of the digital object in a non-iterative way. Normally such operators locate critical points _rst, and calculate a speci_ed path through the object by connecting these points.The third class of operators is characterized by iterative thinning. Historically, Listing 10 used

6、 already in 1862 the term linear skeleton for the result of a continuous deformation of the frontier of a connected subset of a Euclidean space without changing the connectivity of the original set, until only a set of lines and points remains. Many algorithms in image analysis are based on this gen

7、eral concept of thinning. The goal is a calculation of characteristic properties of digital objects which are not related to size or quantity. Methods should be independent from the position of a set in the plane or space, grid resolution (for digitizing this set) or the shape complexity of the give

8、n set. In the literature the term thinning is not usedin a unique interpretation besides that it always denotes a connectivity preserving reduction operation applied to digital images, involving iterations of transformations of speci_ed contour points into background points. A subset Q _ I of object

9、 points is reduced by a de_ned set D in one iteration, and the result Q0 = Q n D becomes Q for the next iteration. Topology-preserving skeletonization is a special case of thinning resulting in a connected set of digital arcs or curves. A digital curve is a path p =p0; p1; p2; :; pn = q such that pi

10、 is a neighbor of pi􀀀1, 1 _ i _ n, and p = q. A digital curve is called simple if each point pi has exactly two neighbors in this curve. A digital arc is a subset of a digital curve such that p 6= q. A point of a digital arc which has exactly one neighbor is called an end point of this arc.

11、 Within this third class of operators (thinning algorithms) we may classify with respect to algorithmic strategies: individual pixels are either removed in a sequential order or in parallel. For example, the often cited algorithm by Hilditch 5 is an iterative process of testing and deleting contour

12、pixels sequentially in standard raster scan order. Another sequential algorithm by Pavlidis 12 uses the de_nition of multiple points and proceeds by contour following. Examples of parallel algorithms in this third class are reduction operators which transform contour points into background points. D

13、i_erences between these parallel algorithms are typically de_ned by tests implemented to ensure connectedness in a local neighborhood. The notion of a simple point is of basic importance for thinning and it will be shown in this report that di_erent de_nitions of simple points are actually equivalen

14、t. Several publications characterize properties of a set D of points (to be turned from object points to background points) to ensure that connectivity of object and background remain unchanged. The report discusses some of these properties in order to justify parallel thinning algorithms.1.2 Basics

15、The used notation follows 17. A digital image I is a function de_ned on a discrete set C , which is called the carrier of the image. The elements of C are grid points or grid cells, and the elements (p; I(p) of an image are pixels (2D case) or voxels (3D case). The range of a (scalar) image is f0; :

16、Gmaxg with Gmax _ 1. The range of a binary image is f0; 1g. We only use binary images I in this report. Let hIi be the set of all pixel locations with value 1, i.e. hIi = I􀀀1(1). The image carrier is de_ned on an orthogonal grid in 2D or 3D space. There are two options: using the grid cell

17、model a 2D pixel location p is a closed square (2-cell) in the Euclidean plane and a 3D pixel location is a closed cube (3-cell) in the Euclidean space, where edges are of length 1 and parallel to the coordinate axes, and centers have integer coordinates. As a second option, using the grid point mod

18、el a 2D or 3D pixel location is a grid point.Two pixel locations p and q in the grid cell model are called 0-adjacent i_ p 6= q and they share at least one vertex (which is a 0-cell). Note that this speci_es 8-adjacency in 2D or 26-adjacency in 3D if the grid point model is used. Two pixel locations

19、 p and q in the grid cell model are called 1- adjacent i_ p 6= q and they share at least one edge (which is a 1-cell). Note that this speci_es 4-adjacency in 2D or 18-adjacency in 3D if the grid point model is used. Finally, two 3D pixel locations p and q in the grid cell model are called 2-adjacent

20、 i_ p 6= q and they share at least one face (which is a 2-cell). Note that this speci_es 6-adjacency if the grid point model is used. Any of these adjacency relations A_, _ 2 f0; 1; 2; 4; 6; 18; 26g, is irreexive and symmetric on an image carrier C. The _-neighborhood N_(p) of a pixel location p inc

21、ludes p and its _-adjacent pixel locations. Coordinates of 2D grid points are denoted by (i; j), with 1 _ i _ n and 1 _ j _ m; i; j are integers and n;m are the numbers of rows and columns of C. In 3Dwe use integer coordinates (i; j; k). Based on neighborhood relations we de_ne connectedness as usua

22、l: two points p; q 2 C are _-connected with respect to M _ C and neighborhood relation N_ i_ there is a sequence of points p = p0; p1; p2; :; pn = q such that pi is an _-neighbor of pi􀀀1, for 1 _ i _ n, and all points on this sequence are either in M or all in the complement of M. A subset

23、M _ C of an image carrier is called _-connected i_ M is not empty and all points in M are pairwise _-connected with respect to set M. An _-component of a subset S of C is a maximal _-connected subset of S. The study of connectivity in digital images has been introduced in 15. It follows that any set

24、 hIi consists of a number of _-components. In case of the grid cell model, a component is the union of closed squares (2D case) or closed cubes (3D case). The boundary of a 2-cell is the union of its four edges and the boundary of a 3-cell is the union of its six faces. For practical purposes it is

25、easy to use neighborhood operations (called local operations) on a digital image I which de_ne a value at p 2 C in the transformed image based on pixel values in I at p 2 C and its immediate neighbors in N_(p).2 Non-iterative AlgorithmsNon-iterative algorithms deliver subsets of components in specie

26、d scan orders without testing connectivity preservation in a number of iterations. In this section we only use the grid point model.2.1 Distance Skeleton AlgorithmsBlum 3 suggested a skeleton representation by a set of symmetric points.In a closed subset of the Euclidean plane a point p is called sy

27、mmetric i_ at least 2 points exist on the boundary with equal distances to p. For every symmetric point, the associated maximal disc is the largest disc in this set. The set of symmetric points, each labeled with the radius of the associated maximal disc, constitutes the skeleton of the set. This id

28、ea of presenting a component of a digital image as a distance skeleton is based on the calculation of a speci_ed distance from each point in a connected subset M _ C to the complement of the subset. The local maxima of the subset represent a distance skeleton. In 15 the d4-distance is specied as fol

29、lows. De_nition 1 The distance d4(p; q) from point p to point q, p 6= q, is the smallest positive integer n such that there exists a sequence of distinct grid points p = p0,p1; p2; :; pn = q with pi is a 4-neighbor of pi􀀀1, 1 _ i _ n. If p = q the distance between them is de_ned to be zero.

30、 The distance d4(p; q) has all properties of a metric. Given a binary digital image. We transform this image into a new one which represents at each point p 2 hIi the d4-distance to pixels having value zero. The transformation includes two steps. We apply functions f1 to the image I in standard scan

31、 order, producing I_(i; j) = f1(i; j; I(i; j), and f2 in reverse standard scan order, producing T(i; j) = f2(i; j; I_(i; j), as follows:f1(i; j; I(i; j) =8:0 if I(i; j) = 0minfI_(i 􀀀 1; j)+ 1; I_(i; j 􀀀 1) + 1gif I(i; j) = 1 and i 6= 1 or j 6= 1m+ n otherwisef2(i; j; I_(i; j) = min

32、fI_(i; j); T(i+ 1; j)+ 1; T(i; j + 1) + 1gThe resulting image T is the distance transform image of I. Note that T is a set f(i; j); T(i; j) : 1 _ i _ n 1 _ j _ mg, and let T_ _ T such that (i; j); T(i; j) 2 T_ i_ none of the four points in A4(i; j) has a value in T equal to T(i; j)+1. For all remain

33、ing points (i; j) let T_(i; j) = 0. This image T_ is called distance skeleton. Now we apply functions g1 to the distance skeleton T_ in standard scan order, producing T_(i; j) = g1(i; j; T_(i; j), and g2 to the result of g1 in reverse standard scan order, producing T_(i; j) = g2(i; j; T_(i; j), as f

34、ollows:g1(i; j; T_(i; j) = maxfT_(i; j); T_(i 􀀀 1; j)􀀀 1; T_(i; j 􀀀 1) 􀀀 1gg2(i; j; T_(i; j) = maxfT_(i; j); T_(i + 1; j)􀀀 1; T_(i; j + 1) 􀀀 1gThe result T_ is equal to the distance transform image T. Both functions g1 and g2 de_ne an operator G,

35、 with G(T_) = g2(g1(T_) = T_, and we have 15: Theorem 1 G(T_) = T, and if T0 is any subset of image T (extended to an image by having value 0 in all remaining positions) such that G(T0) = T, then T0(i; j) = T_(i; j) at all positions of T_ with non-zero values. Informally, the theorem says that the d

36、istance transform image is reconstructible from the distance skeleton, and it is the smallest data set needed for such a reconstruction. The used distance d4 di_ers from the Euclidean metric. For instance, this d4-distance skeleton is not invariant under rotation. For an approximation of the Euclide

37、an distance, some authors suggested the use of di_erent weights for grid point neighborhoods 4. Montanari 11 introduced a quasi-Euclidean distance. In general, the d4-distance skeleton is a subset of pixels (p; T(p) of the transformed image, and it is not necessarily connected.2.2 Critical Points Al

38、gorithmsThe simplest category of these algorithms determines the midpoints of subsets of connected components in standard scan order for each row. Let l be an index for the number of connected components in one row of the original image. We de_ne the following functions for 1 _ i _ n: ei(l) = _ j if

39、 this is the lth case I(i; j) = 1 I(i; j 􀀀 1) = 0 in row i, counting from the left, with I(i;􀀀1) = 0 ，oi(l) = _ j if this is the lth case I(i; j) = 1 I(i; j+ 1) = 0 ，in row i, counting from the left, with I(i;m+ 1) = 0 ，mi(l) = int(oi(l) 􀀀 ei(l)=2)+ oi(l) ，The result of sc

40、anning row i is a set of coordinates (i;mi(l) of midpoints ，of the connected components in row i. The set of midpoints of all rows constitutes a critical point skeleton of an image I. This method is computationally ecient.The results are subsets of pixels of the original objects, and these subsets a

41、re not necessarily connected. They can form noisy branches when object components are nearly parallel to image rows. They may be useful for special applications where the scanning direction is approximately perpendicular to main orientations of object components.References1 C. Arcelli, L. Cordella,

42、S. Levialdi: Parallel thinning of binary pictures. Electron. Lett. 11:148149, 1975.2 C. Arcelli, G. Sanniti di Baja: Skeletons of planar patterns. in: Topolog- ical Algorithms for Digital Image Processing (T. Y. Kong, A. Rosenfeld, eds.), North-Holland, 99143, 1996.3 H. Blum: A transformation for ex

43、tracting new descriptors of shape. in: Models for the Perception of Speech and Visual Form (W. Wathen- Dunn, ed.), MIT Press, Cambridge, Mass., 362380, 1967.19 数字图像处理1引言许多研究者已提议提出了在数字图像里的连接组件是由一个减少的数据量或简化的形状。一般我们不得不陈诉在实际应用中的运算法则的发展，选择和更改，它是依赖于邻域和任务的，除此之外没有更好的办法了。不过，有趣的是，请注意， 有几个等价之间出版的方法和观念，和表征这种等价应

44、该是有用的分类的广泛和多样性，讨论等价是这份报告一个主要的意图，。 1.1分类方法 一类形状减少算子是基于距离变换的。一个距离骨架是一个子集点，某一特定的组成部分，例如，每点子，这代表了该中心的一个最大光盘（标记半径这片光碟）载于特定的组成部分。作为一个例子，在这类算子，本报告讨论了一个计算方法距离骨架使用的D4距离函数，这是适当的数字化图片。 第二类算子产生的中位数或中心线数字对象在一个非迭代的方式。通常这样的算子找到临界点，并计算出特殊路径通过对象连接这些点。 第三类是算子的特点是迭代细化。从历史上看， 用已经在1862年任期线性骨架为结果连续变形的前一个连接子一欧氏空间没有改变的连通原来

45、的设置，直到只有一套线和点仍然存在。许多算法在图像分析是在此基础上的一般概念的细化。目标是计算特性的数字对象，其中不相关的大小或数量。方法应是独立的立场从一组，在平面或空间，网格的决议（数字化这套）或形状复杂该给定。在文献中的任期间是没有用在一个独特的解释，此外，它始终是指连接维护减少运作，适用于数字图像，所涉及的迭代变革的特殊轮廓点到背景点。一个字集 Q_I的对象点是减少了设置，在一迭代和Q0的结果= Q N D成为Q报表下次迭代。拓扑维护骨架是一个特殊的案件细化，导致连接的一套数码化的圆弧或曲线。数字曲线的道路是一条在P=p0 ;P1 ; P2的 ;qn= q等,pi是pi 1的近邻， ，

46、 1 _ i _N和P =q,数字曲线是所谓的简单元素，如果每点pi有准确的两个邻域在这曲线。数码弧是一个子集数字曲线，如p6 =q.一点的数码弧其中，正是一邻居是所谓的一归宿，这电弧。在这第三类算子（细化算法） ，我们可能分类方面的算法策略：个别像素要么拆除在一个顺序或平行进行。举例来说，经常提到的算法hilditch 是一个迭代的过程中的测试和删去的轮廓像素，按顺序在标准光栅扫描秩序。另一种序贯算法pavlidis 使用的多点和收益由轮廓下列的的例子，并行算法在这第三类是减少算子，其中变换轮廓点到背景点。这些并行算法通常是测试实施连通性，以确保在目标连接和内部数据没有改变。概念一简单点是基

47、本的重要性细化且它将会显示在这报告说，简单点，其实是相等的。 若干出版物的特点性能是一套署点（可从对象点到背景点转变）去确定目标和背景的连贯性仍然没变.报告讨论了一些性质是为了证明平行细算法的正确性.1.2基础所用符号如下 17 。数字图像I是一个功能离散集C ，即所谓的载体的形象。要素的C 是网格点或网格细胞和分子性（ P ;I（ p ） 一个图像像素（ 2维）或体素（三维案件）。范围的形象是f0 ; gmaxg 与gmax _ 1 。范围二进制的形象是f0 ，我们只使用在此报告的二进制图像。让它成为一套所有像素的位置与价值1 。 形象载体是对一正交网格在二维或三维空间。 有两种选择：使用网

48、格细胞模型的二维像素位置， P是一个封闭的广场（ 2细胞）在欧氏平面和三维像素的位置是封闭立方体（ 3细胞） ，在欧氏空间，那里边的长度为1和平行于坐标轴，中心有整数坐标。作为一个第二个选项，使用网格点模型一二维或三维像素的位置是一个网格点。 两个像素的位置P和Q在网格中的细胞模型是所谓的0 -毗邻i_ p 6 = Q和他们分享至少有一个顶点（这是一个零细胞） 。 两个三维像素的位置P和Q在网格中的细胞模型是所谓的毗邻i_ p 6 = Q和他们分享至少有一个优势（这是一细胞） 。注意：如果格点模型是用这邻接在二维或邻接在三维。最后，两个像素的三维位置P和Q在网格中的细胞模型被称为2 -毗邻i_

49、 p 6 = Q和他们分享至少有一个面对的（这是一个2细胞） 。请注意，如果格点模型是用这邻接的。 任何这些邻接关系; 1 ; 2 ; 4 ; 6 ; 18; 26是和对称对一的形象， n_ （ p ）条像素位置p包括P和其_ -相邻像素的位置。 坐标的二维网格点是指由（i; j ）中，与1_i n和1_j_m; j是整数和N ;M 是多少行和列正在3维中使用整数坐标（i; j ; k ）段。 基于邻域的关系，我们连通如常： 2 点p; q 2 C是有关n_ i_有一个序列点，p = p0; p1; p2; pn = q 近邻，在此序列无论是在M或全部在补M的一个子集M_ C的形象承运人是所谓的_连接i_M，是不是空洞和所有点，在M都成对设置M 组成的一个子集S的C是一个极大值,连接子S的研究连通性数码影像已在 15 介绍了。 因此，任何一套集合组成了若干组件。在案件该网格的细胞模型，一个组成部分，是联接的封闭空间（二维情况下） 或关闭的立方体（三维案件） 。边界2细胞是联接在其4 细胞和5细胞的。3细胞是连接在其6接口。 为实际目的是易于对数字图像