三维欧拉—庞加莱特性（Euler-Poincare characteristic）或简称三维欧拉数分为三维表面

http://www.paper.edu.cn

-1-

用相邻数表示三维图像的欧拉

-庞加莱特性1

林小竹，周晓正，王彦敏

北京石油化工学院信息工程学院，北京

(102617)

E-mail

：linzhu1964@263.net

摘要：

图像的欧拉-庞加莱特性是数字拓扑学的重要特征参数之一，计算图像欧拉数的方

法被不断探索更新。为了更好地理解三维图像欧拉数的本质和方便地计算三维图像的欧拉

数，通过对三维图像连通性的深入研究，在定义三维图段和三维相邻数两个基本概念的基础

上，提出了局部计算三维图像欧拉数的新公式和计算三维相邻数的方法。不同于以往对像素

和连通性的描述，为局部计算三维图像的欧拉数提供了新途径。

关键词：数字拓扑学，欧拉数，三维图像，连通性

中图分类号：

TP391.4

1

．引言

三维欧拉

—庞加莱特性（Euler-Poincare characteristic）或简称三维欧拉数分为三维表面

欧拉数和三维体欧拉数，

Lee[1]利用现代微分几何学的Gauss-Bonnet定理对多面体的三维表

面欧拉数做了研究， 多面体的三维表面欧拉数和三维体欧拉数存在固定关系

（

χ(∂S)=2χ(S) ），但对非流形，该关系不再成立。Xia [2，3]则对包括流形和非流形在内

的三维表面欧拉数做了研究，提出了一个新的三维数字物体的表面拓扑不变量

BIUP

（

boundary invariant under propagation）。本文则对三维体欧拉数的计算进行了较为深入的

研究。

对于三维图像，欧拉数可由三个

Betti数表示［4］，公式为：

Ｅ＝ｂ

０－ｂ１＋ｂ２ （1）

其中ｂ

０代表连接体数，ｂ１代表孔洞数，ｂ２代表空穴数。由于三维空间中孔洞定义的

多义与不确定性，

Lee［5，6］对Betti数进行了较好的解释，将ｂ１解释成代表不产生分离的

最大切割数，也被称为

handle或tunnel，ｂ２则被称为bubble或cavity。但Betti数不能由象点和

边这样的局部性质计算得到，因此不能将计算分解成每个网格片的子任务，即公式（

1）是

一种全局测量公式，无法进行局部计算。

除了全局定义公式（

1），三维图像体欧拉数也可以由局部性质计算得到。由局部性质

计算三维图像欧拉数的算法最早可以追溯到

1970年Gray[7]和Park [8]的论文，但他们的算法

只对三维图像的

6-邻域连接有效。另一种欧拉数的局部算法可以参见文献［9］，由

Morgenthaler

在1980年提出，它访问每个2X2X2方块，有256中可能的模式，但该算法只对

三维图像的

26-邻域连接有效，而且被后续的研究[10，11]所沿用。Saha[12，13]描述了计算

三维图像欧拉数的新方法，它是基于计算

3X3X3邻域内前景分量、管道和空穴在数量上的变

化。Serra[14] 在他的《图像分析与数学形态学》一书中第135页给出了计算三维空间体欧拉

数的两个公式（V-8）和（V-9），他是基于代数拓扑学凸环（convex ring）的性质归纳得到

这些公式的，由边界表面的示性数（genus）计算三维空间体欧拉数。我们的工作则从另一

种角度——在定义三维图段和三维相邻数两个新概念的基础上，考虑邻域连接的复杂性，无

论研究思路还是公式内单项的几何意义都与Serra的不相同，尽管所得公式从形式上有相似

之处。

1

本课题得到校内学科点专项科研资助。

http://www.paper.edu.cn

-2-

2

．图段与相邻数的概念

2.1

扫描方式

仿照二维图像中关于图段和相邻数的定义 [15,16]，在三维图像中，重新定义图段及其

相邻数的概念。我们考虑用3D 立方块来表示三维数字图像，如图1（a）所示，用f（

l，i，

j）代表第

l 个切片、i 行、j 列的图像值（0 或1）。对于三维数字图像，常见的扫描方式如

图1（b）所示，切片扫描（

l）采用由后往前的方式，行扫描（i）采用由上而下的方式，列

扫描（j）采用自左向右的方式。

(a) 3D 立方块 （b）三维图像切片

(a) 3D cubic grid (b) 3D cubic slice

图1 三维图像表示

Fig.1 3D image

2.2

三维图段定义

对于三维图像（二值），我们定义图段的概念，它是三维图像的任意切片内的某一行中

被０或图像边界所分隔的值为１的单个或多个像素块。图段的大小由其游程表示，最小是１，

最大不超过行的长度。如果三维图像用函数f（

l，i，j）表示，则图段可以用下式来描述：

若

f（l，i，j:j+K-1）=1,

且

f（l，i，j-1）= f（l，i，j+K）=0, 或j-1 或j+K 超出图像的边界

满足上面条件的前景像素段f（

l，i，j:j+K-1）被称为图段，K 表示图段的大小即游程。

当K=1 时，图段就退化为单个的前景像素块。如图2 所示，该行有三个图段，游程分别为

２、１、3。

图2 图段示意

Fig.2 3D foreground run

http://www.paper.edu.cn

-3-

2.3

三维相邻数定义

三维图像中图段的相邻数，定义为在当前切片和相邻切片内与该图段相邻的行中所能构

成的图段数目，它反映图段邻域连接的复杂程度。如果用f（

l，i，j:j+K-1）代表图段，则

该图段的相邻数只与邻域（

l，i-1，j:j+K-1）、（l-1，i-1，j:j+K-1）、（l-1，i，j:j+K-1）范围内

的像素块有关，三维图段的相邻数可以这样确定：

首先将图段的邻域立方块

f（l，i-1，j:j+K-1）、f（l-1，i-1，j:j+K-1）、f（l-1，i，j:j+K-1）

展开成平面二维图像上的三行，如图

3 所示；然后用已知方法计算该二维图像的欧拉数，

即图段

f（l，i，j:j+K-1）的邻居图段数目，所以它被称为相邻数。

(a)

(b)

图3 计算三维相邻数的展开图（K=3）

Fig.3 The unfolded map of computing 3D neighbor number (K=3)

3

．新公式及其算法

下面直接给出三维图像欧拉数局部计算公式的统一形式，它是文献[17]中二维公式的进

一步推广，并分析探讨在不同邻域连接方式条件下相邻数的计算方法。

ΣΣΣ

= = =

= −

L

l

I

i

N

n

lin

E V

1 1 0

(1 ) (2)

其中，

L 和I 分别是三维图像的切片个数和行数，N（l，i）则是切片l 的第i 行内的图段个

数，

lin V 表示三维图像第l 切片、第i 行、第n 个图段所对应的相邻数。规定0 1 l i V ≡ ，

即当

n = 0时， 1 l in V = 。表示当切片l 的第i 行无图段时，该行对欧拉数无贡献。由（2）

式可见，为了得到三维图像欧拉数，图段的相邻数计算是关键，而相邻数的计算与不同邻域

连接方式有关，不同邻域连接方式其相邻数的具体计算方法在下面给出。注意公式（2）的

求和顺序自左向右，不能交换，因为N 是依赖于

l 和i 的。

为了计算三维图像第

l 切片、第i 行、第n 个图段的相邻数lin V ，首先假定该图段位于切片

l

的第i 行第j 列，且其行程长度是K，即f（l，i，j:j+K-1）=1。为了便于理解可将其邻域

http://www.paper.edu.cn

-4-

立方块f（

l，i-1，j:j+K-1）、f（l-1，i-1，j:j+K-1）、f（l-1，i，j:j+K-1）展开成平面二维图

像上的三行，如图4 所示，然后计算二维图像的欧拉数即可。图段邻域的展开图只用部分邻

域立方块，这与图像的扫描方式有关，本文采用由后往前的方式扫描切片（

l），采用由上而

下的方式扫描行（i）。

(a) 6-邻域连接 (b) 18-邻域连接 (c) 26-邻域连接

图4 不同邻域连接方式的展开图(X=0,1)

Fig.4 The unfolded map under different connectivity (X=0,1)

3.1 6-

邻域连接

当图段的行程长度是3 时，该图段在6 邻域连接的情况下的邻域平面展开图如图4（a）

所示（x=0，1）。三维图段相邻数的计算实际上变成了该展开二维图像欧拉数的计算(关于二

维图像欧拉数的具体计算方法详见文献[16])，值得引起注意的是，尽管6-邻域连接是面连

接，计算图段的相邻数时仍然必须考虑与该图段属于边连接的f（

l-1，i-1，j:j+K-1）立方块

的信息。图5 的例子表示了f（

l-1，i-1，j:j+K-1）的变化会使相邻数不同。但有一个例外，

就是当f（

l，i-1，J）+f（l-1，i，J）=0 时，我们规定f（l-1，i-1，J）=0，这是6-邻域连接

的一个特例。如图6 所示，当展开图第一行和第三行都为零时，无论第二行为何值，根据上

面的规定，其相邻数都为零。

（a）

2 l in V =

（b）

1 l in V =

（c）

0 l in V =

图5 6-邻域连接的具体例子

Fig.5 The detailed examples of 6-connectivity

图6 6-邻域连接的特例(

0 l in V ≡

)

Fig.6 The exceptional example of 6-connectivity

3.2 18-

邻域连接

当图段的行程长度是3 时，18-邻域连接情况下的该图段邻域平面展开图如图4（b）

所示（x=0，1）。由于18-邻域连接方式除了面连接，还包括了边连接，所以在第一行左右

http://www.paper.edu.cn

-5-

各多了一个立方块，分别代表f（

l，i-1，j-1）、f（l，i-1，j+K），另外在第三行左右也各多

了一个立方块，分别代表f（

l-1，i，j-1）、f（l-1，i，j+K）。三维图段相邻数的计算实际上

变成了该展开二维图像欧拉数的计算，与6-邻域连接的计算相似，必须考虑f（

l-1，i-1，

j:j+K-1）的变化对相邻数的影响。

3.3 26-

邻域连接

当图段的行程长度是3 时，26-邻域连接情况下的该图段邻域平面展开图如图4（c）

所示（x=0，1）。由于26-邻域连接方式除了考虑面连接和边连接，还考虑了点连接，所以

在第二行左右各多了一个立方块，分别代表f（

l-1，i-1，j-1）、f（l-1，i-1，j+K）。同样，三

维图段相邻数的计算实际上变成了该展开二维图像欧拉数的计算。三种邻域连接方式的区别

体现在其展开图的不同上，当然由展开图计算的相邻数也会不同，从而影响三维图像欧拉数

的结果。

4

．连接体的例子（考虑不同邻域连接的情况）

如图7所示，考虑3X3X3的三维图像，其中有两个图段，分别为（f 2,2,1:3）=1和（f 3,3,1:3）

=1。

在 6 -邻域连接时，图段f（2，2，1:3）的相邻数由其邻域平面展开图计算得到V

221=0，

图段f（3，3，1:3）的邻域平面展开图正好是图6 所示的特例，它的相

邻数V

331=0，

因此，该三维图像的欧拉数E（6）=（1- V

221）+（1- V331）=2 。

在18 -邻域连接时，图段f（2，2，1:3）的相邻数由展开图计算得到V

221=0，

图段f（3，3，1:3）的相邻数由展开图计算得到V

331=1，

因此，该三维图像的欧拉数E（18）=（1- V

221）+（1- V331）=1。

在26 -邻域连接时，与18 -邻域连接相同，两个图段的相邻数分别是V

221=0，V331=1，

因此，该三维图像的欧拉数E（26）=（1- V

221）+（1- V331）=1。

图7 连接体的例子

Fig.7 Example of different connectivity

http://www.paper.edu.cn

-6-

5

．结论

在三维图像欧拉数的研究中，图段概念的建立非常重要，因为它具有拓扑变换的基本特

征——与长度无关，也是我们建立具有统一形式的三维局部计算公式的基石，图段概念在数

字拓扑学中的作用将是我们下一步要研究和感兴趣的东西。相邻数作为图段的重要属性，反

映图段邻域连接的复杂程度，由三维图像欧拉数的局部计算公式分析可知，它不过是欧拉数

的微观和局部体现。反之，我们对欧拉数本质的认识也进一步深入，它是所有图段邻域连接

复杂度的宏观和综合表示。至此，我们已经能够方便计算三维图像的欧拉数，这是到目前为

止，在计算机视觉和模式识别领域计算三维图像欧拉数的一个新思路。

参考文献

[1] Lee C.N., and Rosenfeld A., Computing the Euler Number of a 3D Image[A], Proceedings - First International

Conference on Computer Vision[C], London: IEEE, 1987, pp.567-571

[2] Xia F., Invariant Property of Contour: PIUD for Closed Sets and VPIUD for Arbitrary Images [A], 9

th

Scandinavian Conf. On Image Analysis[C], 1995, vol.1, pp.103-112

[3] Xia F., BIUP3: Boundary Topological Invariant of 3D Objects Through Front Propagation at a Constant

Speed[A], Proceedings of the Geometric Modeling and Processing 2004[C], 2004

[4] Kong T.Y., and Rosenfeld A., Digital Topology: Introduction and Survey[J], CVGIP, 1989, vol.48, pp.357-393

[5] Lee C.N., Poston T., and Rosenfeld A., Winding and Euler numbers for 2D and 3D digital images[J], CVGIP:

Graph. Models Image Process, 1991, 53(6), pp.522-537

[6] Lee C.N., Poston T., and Rosenfeld A., Holes and Genus of 2D and 3D digital images[J], CVGIP: Graph.

Models Image Process, 1993, 55(1), pp.20-47

[7] Gray S.B., Local Properties of Binary Images in Two and Three Dimensions [M], Boston: Information

International Inc., 1970

[8] Park C.M. and Rosenfeld A., Connectivity and Genus in Three Dimension[D], TR-156, Computer Vision

Laboratory, Computer Science Center, University of Maryland, College Park, MD, 1971

[9] Morgenthaler D.G., Three Dimension Digital Topology: the Genus[D], TR-980, Computer Vision Laboratory,

Computer Science Center, University of Maryland, College Park, MD, 1980

[10] Tsao Y.F. and Fu K.S., A 3D Parallel Skeleton-wise Thinning Algorithm[A], Proc. IEEE Conf. on Pattern

Recognition and Image Processing[C], 1982, pp.678-683

[11] Nakamura A. and Aizawa K., On The Recognition of Properties of Three-Dimension Pictures[J], IEEE Trans.

Pattern Anal. Mach. Intell. , 1985, PAMI-7, pp.708-713

[12] Saha P.K. and Chaudhuri B.B., A New Appoach to Computing The Euler Characteristic[J], Pattern

Recognition, 1995, 28(12), pp.1955-1963

[13] Saha P.K. and Chaudhuri B.B., 3D Digital Topology under Binary Transformation with Applications[J],

Computer Vision and Image Understanding, 1996, 63(3), pp.418-429

[14] Serra J., Image Analysis and Mathematical Morphology[M], London: Academic Press, 1982, pp.133-135

[15] Lin X.Z., Sha Y., Ji J.W. and Wan J.B., Image Euler Number Calculating for Intelligent Counting[A],

Proceedings of the Seventh International Conference on Electronic Measurement & Instruments

(ICEMI’005)[C], Beijing: International Academic Publishers /World Publishing Corporation, August 2005,

Vol.8, pp.642-645

[16] Lin X.Z., Wang Y.M., Sha Y., and Ji J.W., A New Approach to Compute the Euler Number of 2D Image[A],

Proceedings of the International Conference on Sensing, Computing and Automation (ICSCA’006)[C],

Chongqing: Watam Press, May 2006, pp.1376-1379

[17] 林小竹 沙芸 籍俊伟 王彦敏，关于二维图像Euler 数新公式的证明[J]，《中国科学》（E 辑），2006，

36（4），pp.429-436

http://www.paper.edu.cn

-7-

The Euler-Poincare Characteristic of 3D Image Expressed as

Neighbor Number

Xiaozhu Lin，Xiaozheng Zhou，Yanmin Wang

School of Information Engineering， Beijing Institute of Petrochemical Technology，Beijing

(102617)

Abstract

The Euler-Poincare characteristic of image is one of the most important characteristics in digital

topology and its computing methods have been in unceasing exploration. The connectivity of the 3D

binary image was deeply researched in order to understand the essence of Euler Number and to

compute the Euler Number of 3D image conveniently. A formula for locally computing the Euler

Number of 3D image was proposed based on the definitions of Foreground Run and Neighbor Number..

This description was different from former ones between pixels and connectivity. It is a new idea to

locally compute the Euler Number of 3D image.

Keywords

：Digital Topology，Euler Number，3D Image，connectivity

作者简介：林小竹，男，1964 年生，博士，教授，主要研究方向为信号处理与图像识别。