Lambda-connectedness explained

In applied mathematics, lambda-connectedness (or λ-connectedness) deals with partial connectivity for a discrete space.

Assume that a function on a discrete space (usually a graph) is given. A degree of connectivity (connectedness) will be defined to measure the connectedness of the space with respect to the function. It was invented to create a new method for image segmentation. The method has expanded to handle other problems related to uncertainty for incomplete information analysis. ^{[1] [2]}

For a digital image and a certain value of

λ , two pixels are called λ -connected if there is a path linking those two pixels and the connectedness of this path is at least λ . λ -connectedness is an equivalence relation.^[3]

Background

Connectedness is a basic measure in many areas of mathematical science and social sciences. In graph theory, two vertices are said to be connected if there is a path between them. In topology, two points are connected if there is a continuous function that could move from one point to another continuously. In management science, for example, in an institution, two individuals are connected if one person is under the supervision of the other. Such connected relations only describe either full connection or no connection. lambda-connectedness is introduced to measure incomplete or fuzzy relations between two vertices, points, human beings, etc.

In fact, partial relations have been studied in other aspects. Random graph theory allows one to assign a probability to each edge of a graph. This method assumes, in most cases, each edge has the same probability. On the other hand, Bayesian networks are often used for inference and analysis when relationships between each pair of states/events, denoted by vertices, are known. These relationships are usually represented by conditional probabilities among these vertices and are usually obtained from outside of the system.

λ -connectedness is based on graph theory; however, graph theory only deals with vertices and edges with or without weights. In order to define a partial, incomplete, or fuzzy connectedness, one needs to assign a function on the vertex in the graph. Such a function is called a potential function. It can be used to represent the intensity of an image, the surface of a XY-domain, or the utility function of a management or economic network.

Basic concepts

A generalized definition of

λ -connectedness can be described as follows: a simple system \langle G,\rho\rangle , where \rho is called a potential function of G . If \langle G,\rho\rangle is an image, then G is a 2D or 2D grid space and \rho is an intensity function. For a color image, one can use f = ( red , green , blue ) to represent \rho . Neighbor connectivity will be first defined on a pair of adjacent points. Then one can define the general connectedness for any two points.

Assume

\alpha _{\rho(x,y)} is used to measure the neighbor-connectivity of x,y where x and y are adjacent.In graph G = (V, E), a finite sequence x _{1,x} _{2,\ldots,x} _{n} is called a path, if (x _{i,x} _{i+1} )\in E .

The path-connectivity

\beta of a path \pi = \pi(x _{1,x} _{n)=\{x} _{1,x} _{2,...,x} _{n\}} is defined as \beta _{\rho(\pi(x} _{1,x} _{n))} = min \{ \alpha _{\rho} (x _{i,x} _{i+1} ) | i =1 ,\ldots,n -1 \} Finally, the degree of connectedness (connectivity) of two vertices x,y with respect to \rho is defined as C _{\rho(x,y)} = max \{ \beta(\pi(x,y)) | \pi isa(simple)path . \} For a given λ \in [ 0 , 1 ] , point p = (x,\rho(x)) and q = (y,\rho(y)) are said to be λ -connected if C _{\rho} (x,y)\ge λ .λ -connectedness is a equivalence relation. It can be used in image segmentation.

Relations to Image Segmentation

The lambda-connected segmentation is a region-growing segmentation method in general. It can also be made for split-and-merge segmentation.^[4] Its time complexity also reaches the optimum at

O(n log n ) where n is the number of pixels in the image.^[5]

The lambda-connectedness has close relationships to Data Science that can be found in the Book entitled Mathematical Problems in Data Science.^[6]

New Developments

Researchers applied related techniques to smooth 3D data processing and transportation network management recently.^{[7] [8]}

Notes and References

1. Book: 10.1109/ICSMC.2000.886243 . Λ-connectedness: Method and application . SMC 2000 Conference Proceedings. 2000 IEEE International Conference on Systems, Man and Cybernetics. 'Cybernetics Evolving to Systems, Humans, Organizations, and their Complex Interactions' (Cat. No.00CH37166) . 2000 . Li Chen . Adjei . O. . Cooley . D.H. . 3 . 1557–1562 . 0-7803-6583-6 . 46359405 .
2. Chen . Li . Adjei . Osei . λ-Connectedness and Its Applications . Journal of Scientific and Practical Computing . 2009 . 3 . 1 . 19–52 . 42002184 .
3. Chen . Li . Cheng . Heng-da . Zhang . Jianping . Fuzzy subfiber and its application to seismic lithology classification . Information Sciences - Applications . March 1994 . 1 . 2 . 77–95 . 10.1016/1069-0115(94)90009-4 .
4. L. . Chen . The lambda-connected segmentation and the optimal algorithm for split-and-merge segmentation . Chinese Journal of Computers . 14 . 1991 . 321–331 . 0254-4164 .
5. L. Chen, Digital and Discrete Geometry, Springer, 2014.
6. L. Chen, Z. Su, B. Jiang, Mathematical Problems in Data Science, Springer, 2015.
7. Spradley . Jackson P. . Pampush . James D. . Morse . Paul E. . Kay . Richard F. . Smooth operator: The effects of different 3D mesh retriangulation protocols on the computation of Dirichlet normal energy . American Journal of Physical Anthropology . May 2017 . 163 . 1 . 94–109 . 10.1002/ajpa.23188 . 28218399 . free .
8. An . Kang . Chiu . Yi-Chang . Hu . Xianbiao . Chen . Xiaohong . A Network Partitioning Algorithmic Approach for Macroscopic Fundamental Diagram-Based Hierarchical Traffic Network Management . IEEE Transactions on Intelligent Transportation Systems . April 2018 . 19 . 4 . 1130–1139 . 10.1109/TITS.2017.2713808 . 4623967 .