A tutorial on well-composedness (Q1799490)

The well-known ``paradox'' of digital topology, coming from the early works of Rosenfeld, is that for binary images on a square/cubic grid (in $\mathbb{Z}^n$), with connectivity given by graph adjacency, the preservation of standard Euclidean topological properties requires that one chooses opposite adjacencies on foreground and background: axial adjacency (linked to the $L_1$-norm) for one, and diagonal adjacency (linked to the $L_\infty$-norm) for the other. This presents several problems: a binary digital image will have two topologies corresponding to the two choices of adjacency for foreground, and the idea does not extend easily to non-binary images, whose values can for instance form an anti-chain of labels, or a chain of grey-levels. To overcome that problem, Latecki and co-workers introduced the notion of \textit{well-composed} images, those for which the topology does not depend on the choice of adjacencies. This paper gives a survey of this concept, covering its various definitions and its possible applications. First, four definitions of well-composedness are presented and analysed: \begin{itemize} \item DWC: digital well-composedness, characterised by the absence of ``critical configurations'' (for instance in 2D, a $2\times2$-square with one diagonal with one value, and the other diagonal with another value). \item AWC: well-composedness in the Alexandrov sense, where the image is embedded in a cellular complex with Alexandrov topology, then the boundary of each connected component will be a discrete $(n-1)$-surface. \item EWC: well-composedness by connectivity equivalence: all choices of adjacencies will lead to the same connected components for all image values. \item CWC: well-composedness in the continuous sense: replacing each pixel/voxel by the corresponding Euclidean closed unit square/cube, one obtains an object whose boundary is an $(n-1)$-manifold. \end{itemize} These four definitions are related as follows: \begin{itemize} \item DWC implies EWC; in 2D the two are equivalent; on the other hand, in $n\ge3$ dimensions, the implication is strict, there are examples of binary images satisfying EWC, but not DWC. \item In 2D and 3D, AWC, DWC and CWC are proven to be equivalent; in $n\ge4$ dimensions, their equivalence is conjectured. \end{itemize} The authors consider also well-composedness on arbitrary grids, for instance in 2D the grid obtained from a hexagonal tessellation, where there is a unique adjacency relation. It can be generalised in $\mathbb{Z}^n$, by taking an anisotropic adjacency where each pixel/voxel has $2(2^n-1)$ neighbours. Next, the authors extend well-composedness to grey-level images with the help of threshold sets, then to images with interval values and label images (where values form an anti-chain). They describe two methods for making an image well-composed: topological repair and well-composed interpolation. Two long sections detail possible applications of well-composedness, first to binary images, next to grey-level ones. These include a better digitisation, more robust geometrical or topological transformations, local computation of the Euler number, the Jordan separation theorem, visualisation by marching cubes, topological watershed segmentation, auto-dual representations of images, trees of shapes, and detection of saliency. The article adopts a pedagogical style, where all concepts, including elementary ones, are precisely defined. It is also very detailed and complete. It constitutes thus a good survey both for the beginner and for the expert.