betaFeedback

WorksMathematics

The Volume Exchange Metric

Abstract

The volume exchange metric between cell structures embedded in Euclidean space is introduced. Intuitively, it measures the minimum amount of volume that must be swept out to continuously transform one cell structure into another. The main result is that the volume exchange metric coincides with a discrete analogue defined as a minimum over matchings between cells. Algorithms are described to compute the discrete volume exchange metric and illustrate its effectiveness at distinguishing polycrystalline microstructures in computational experiments.

Introduction

Cell structures appear throughout the natural world. Examples include the decomposition of a polycrystalline material into its constituent grains (Figure 1a) and the representation of a biological tissue as a union of cells (Figure 1b). Recent advances in microscopy techniques have made possible the collection of large datasets of two-dimensional images of cell structures, and for some specific applications three-dimensional images are available as well [3] [4, 5, 6]. The underlying physical processes are often stochastic though, and the analysis of the resulting images continues to be challenging. Specifically, the scarcity of established techniques to compare such images, or even to identify natural classes, has significant practical consequences. For example, it is difficult to evaluate whether a simulated material microstructure is a reasonable approximation of a manufactured one without the ability to quantitatively measure the extent of their differences. As a second example, there would

Micrographs of a polycrystalline metal and cancerous bone tissue

Figure 1. (a) A micrograph of a metal showing the polycrystal microstructure, reprinted from Ref. [1], Fig. 4, with permission from John Wiley and Sons. (b) A histopathology slide of cancerous bone tissue [2].

be considerable implications for human health if a computer vision model could be trained on the histopathological classification problem to distinguish images of healthy and cancerous biological tissues.

Previous literature on this subject has generally either (i) treated the image as an array of greyscale or colored pixels and applied general image analysis techniques, or (ii) compared ad hoc selections of geometric statistics for individual or small groups of cells. While the former does not require expert knowledge and can be highly accurate for specific applications [7, 8], the performance rapidly degrades for structures outside the support of the training set, and the analysis usually does not indicate which image features are most significant. The latter instead uses expert knowledge to identify the geometric features most relevant to the properties of interest [9, 10], but this effectively prohibits meaningful comparison with structure classes for which the selected features are irrelevant or undefined [11]. It is also significant that both approaches are practically limited to comparatively small sets of cell structures for which the extent of geometric variation is known beforehand. This can increase the difficulty of analyzing newly-discovered cell structures, discourage the intentional design and exploration of cell structures outside of well-established classes, and promote the fragmentation of the physical science communities concerned with such systems. This situation has motivated several recent studies that have sought to develop comprehensive and general geometric summaries of the overall cell arrangement, ideally providing sufficient information to reliably identify structural differences and predict system properties while remaining flexible enough to be useful for the analysis of general cell structures.

Here we introduce two dissimilarities between cell structures called the one-to-one volume exchange metric and the many-to-many volume exchange dissimilarity. Intuitively, they measure the minimum amount of volume that must be swept out by the cell boundaries to transform one structure into the other, as for example in Figure 2. The one-to-one volume exchange metric additionally requires that each cell in one structure either transforms into exactly one cell in the other structure or disappears in the process. The many-to-many volume exchange dissimilarity instead allows initially non-adjacent cells to merge during the transformation. One advantage that these have over alternatives like the Hausdorff metric is that they are less sensitive to the geometric noise that is often introduced either by the imaging method or by the cell segmentation process.

Cellular filling $\mathcal{W}$ between $\mathcal{P}$ and $\mathcal{Q}$, and its projection into the plane

Figure 2. (Left) A cellular filling W\mathcal{W} between P\mathcal{P} and Q\mathcal{Q} that realizes the minimal one-to-one volume exchange. (Right) The projection into the plane shows the volume exchange distance between P\mathcal{P} and Q\mathcal{Q} as the area in grey.

The underlying physical motivation though is that there are many examples of cell structures for which the transport of volume across the cell boundaries is the slowest (rate-limiting) process involved in changing the cell configuration, and geometric properties that are the slowest to change are likely to be highly significant to physical systems. With reference to Figure 1, cell boundary motion in a polycrystal occurs precisely by atoms leaving one grain, passing through the boundary, and joining the crystal lattice of the adjoining grain. A biological cell of fixed volume is easily able to redistribute the contents of the cell, but the volume changes that accompany general cell configuration changes involve a slower process of water transport across the cell membrane. Gas transport through the liquid boundaries of the bubbles in a dry soap foam is so slow relative to other processes that in the limit the cell configuration is entirely specified by the topology of the cell boundary network and the cell volumes. These examples suggest that meaningful dissimilarities could be based directly on the amount of volume exchanged by adjoining cells rather than on, e.g., changes to the area of the cell boundaries or the amount of displacement of the cell boundaries.

The dissimilarities can also be motivated by considering distances on labeled cell structures, with there being many applications for which there is a natural set of labels in a metric space (Y,δ)(Y,\delta). For example, in materials science the grains of a polycrystalline material could be labeled by a crystal orientation that indicates the misorientation of the crystal lattice relative to a suitable reference, i.e., an element of the quotient Y=SO(3)/HY = SO(3)/H of the three-dimensional rotation group SO(3)SO(3) by the point symmetry group HH of the crystal lattice [12]. Such a labeled cell structure P\mathcal{P} in an ambient space Ω⊂Rn\Omega\subset\mathbb{R}^{n} can be identified with a piecewise constant function p:Ω→Yp:\Omega\to Y whose level sets are the cells. A natural distance between cell structures P\mathcal{P} and Q\mathcal{Q} is then given by the L1L^{1} norm of δ(p,q)\delta(p,q). However, in the absence of specific knowledge about the cell labels or a natural distance between them, minimal assumptions could be that labels on adjacent cells are distinct and that distinct labels are a unit distance apart. Given two cell structures P\mathcal{P} and Q\mathcal{Q}, the many-to-many volume exchange dissimilarity is then the minimal L1L^{1} distance between gPg_{\mathcal{P}} and gQg_{\mathcal{Q}} over all possible labeling gPg_{\mathcal{P}} and gQg_{\mathcal{Q}} which assign distinct labels to adjacent cells. The one-to-one volume exchange metric—a true metric which is more efficient to compute in practice—is obtained by adding the further assumption that the labels are distinct for each cell in a cell structure regardless of adjacency.

We now formally define cell structures, transformations between them called cellular fillings, and the volume exchange metric and dissimilarity. A cell structure in Ω⊂Rn\Omega\subset\mathbb{R}^{n} is a countable partition P\mathcal{P} of Ω\Omega so that each cell E∈PE \in\mathcal{P} has positive Lebesgue measure, and the collection has finite interfacial surface energy (see Definition 8 for a precise definition). We assume that Ω\Omega is open bounded open and connected, and we consider two cell structures to be equal if they differ up to a rearrangement of a set of measure zero. We do not make assumptions about the topology of cells, but call them “cells” because of the proposed applications.

We introduce two different ways to “fill” the space between two nn-dimensional cell structures P,Q\mathcal{P},\mathcal{Q} defined on the ends of a cylinder Ω×(0,1)\Omega\times(0,1). Either notion defines an (n+1)(n+1)-dimensional cell structure W\mathcal{W} of Ω×(0,1)\Omega\times(0,1). To avoid pathologies, we introduce the notions of essential interior and essential boundary from geometric measure theory. With the notion of the density of E⊂RnE \subset\mathbb{R}^{n} at xx,

Θ(E,x):=lim⁡r→0+Ln(E∩B(x,r))Ln(B(x,r)),\Theta(E,x) := \lim_{r\to0+} \frac{\mathcal{L}^{n}(E \cap B(x,r))}{\mathcal{L}^{n}(B(x,r))},

we can define the essential interior E(1)E^{(1)} of EE consists of the set of points where the density of EE is 1, and the essential boundary ∂∗E\partial^{*}E of EE consists of the points where the density of EE is not in {0,1}\{0,1\}. In particular, if we define adjacency of cells via their essential boundaries, the adjacency is unchanged by rearranging a set of Lebesgue measure zero (for instance, adding a path connecting one cell to another).

A one-to-one cellular filling between cell structures P\mathcal{P} and Q\mathcal{Q} is an (n+1)(n+1)-dimensional cell structure W\mathcal{W} in Ω×(0,1)\Omega\times(0,1) so that for each cell W∈WW \in\mathcal{W} with Hn(∂∗W∩(Ω×0))>0\mathcal{H}^{n}(\partial^{*}W \cap(\Omega\times0)) > 0, there exists a cell E∈PE \in\mathcal{P} such that

Hn((E×0)△∂∗W∩(Ω×0))=0,\mathcal{H}^{n}\bigl((E \times0) \mathbin{\triangle} \partial^{*}W \cap(\Omega\times0)\bigr)=0,

and similarly for a cell W∈WW \in\mathcal{W} with Hn(∂∗W∩(Ω×1))>0\mathcal{H}^{n}(\partial^{*}W \cap(\Omega\times1)) > 0.

Call two cells of a cell structure P\mathcal{P} adjacent if the intersection of their essential boundaries has positive (n−1)(n-1)-dimensional Hausdorff measure. A coarsening of a cell structure P\mathcal{P} is a cell structure P′\mathcal{P}' so that each E′∈P′E' \in\mathcal{P}' is a union of non-adjacent cells of P\mathcal{P}. A many-to-many cellular filling between cell structures P\mathcal{P} and Q\mathcal{Q} in Ω\Omega is a one-to-one cellular filling between coarsenings of P\mathcal{P} and Q\mathcal{Q}. See Figure 3.

Many-to-many cellular filling between $\mathcal{P}$ and $\mathcal{Q}$

Figure 3. (Left) A many-to-many cellular filling W\mathcal{W} between P\mathcal{P} and Q\mathcal{Q} that is not a one-to-one cellular filling. Note that two cells are merged via a pair of pants. (Right) The projection into the plane shows the volume exchange dissimilarity between P\mathcal{P} and Q\mathcal{Q} as the area in grey.

Denote the collections of such fillings by F1(P,Q)\mathcal{F}^{1}(\mathcal{P},\mathcal{Q}) and F2(P,Q)\mathcal{F}^{2}(\mathcal{P},\mathcal{Q}), respectively. The restriction on one-to-one fillings may seem artificial as they do not allow a single connected cell to be transformed into two disjoint connected cells via a “pair of pants,” but as we will see below the resulting metric has nicer properties and is easier to compute.

Let W\mathcal{W} be an (n+1)(n+1)-dimensional cell structure in Ω×(0,1)\Omega\times(0,1), let ∂∘W\partial^{\circ}\mathcal{W} the union of the essential boundaries of the elements of the partition W\mathcal{W}, in the open cylinder, i.e.,

∂∘W=⋃W∈W∂∗W∩(Ω×(0,1))\partial^{\circ}\mathcal{W}=\bigcup_{W\in\mathcal{W}}\partial^{*}W\cap(\Omega\times(0,1))

and let π:Ω×(0,1)→Ω×0\pi:\Omega\times(0,1)\to\Omega\times0 be the projection. We define the volume exchange of a filling W\mathcal{W} by

E[W]=∫Ω×0H0(∂∘W∩π−1(x)) dLn(x)=∫∂∘W∣⟨v,n(x)⟩∣ dHn(x),(1)\mathcal{E}[\mathcal{W}]=\int_{\Omega\times0}\mathcal{H}^{0}\bigl(\partial^{\circ}\mathcal{W}\cap\pi^{-1}(x)\bigr)\,d\mathcal{L}^{n}(x)=\int_{\partial^{\circ}\mathcal{W}}|\langle v,n(x)\rangle|\,d\mathcal{H}^{n}(x), \tag*{(1)}

where n(x)\boldsymbol{n}(x) is the unit normal vector to the approximate tangent space Tan⁡n(∂∗W,x)\operatorname{Tan}^{n}(\partial^{*}W,x) (which coincides with the usual tangent space where ∂∗W\partial^{*}W is smooth), v=(0,…,0,1)\boldsymbol{v}=(0,\ldots,0,1), Ln\mathcal{L}^{n} is the Lebesgue measure, and Hn\mathcal{H}^{n} is the Hausdorff measure. The equality of the two expressions above follows from the area formula (see [13, Remark 2.94] or [14, 3.2.22]).

Definition 1. Let P,Q\mathcal{P},\mathcal{Q} be cell structures in Ω\Omega. The one-to-one volume exchange metric is

dV1(P,Q)=min⁡W∈F1(P,Q)E[W]d_{\mathrm{V}}^{1}(\mathcal{P},\mathcal{Q})=\min_{W\in\mathcal{F}^{1}(\mathcal{P},\mathcal{Q})}\mathcal{E}[W]

and the many-to-many volume exchange dissimilarity is

dV2(P,Q)=min⁡W∈F2(P,Q)E[W].d_{\mathrm{V}}^{2}(\mathcal{P},\mathcal{Q})=\min_{W\in\mathcal{F}^{2}(\mathcal{P},\mathcal{Q})}\mathcal{E}[W].

The existence of these minima will be shown in Proposition 24 below as a corollary of our main theorem.

We now define discrete analogues of the two volume exchange metrics.

Definition 2. A partial matching between two sets P\mathcal{P} and Q\mathcal{Q} is a subset R\mathcal{R} of (P∪{∗})×(Q∪{∗})(\mathcal{P}\cup\{\ast\})\times(\mathcal{Q}\cup\{\ast\}) such that each cell of P\mathcal{P} is matched to exactly one element of (Q∪{∗})(\mathcal{Q}\cup\{\ast\}) and each cell of Q\mathcal{Q} is matched to exactly one element of (P∪{∗})(\mathcal{P}\cup\{\ast\}).

We denote the collection of partial matchings between P\mathcal{P} and Q\mathcal{Q} as PM⁡(P,Q)\operatorname{PM}(\mathcal{P},\mathcal{Q}).

See Figure 4. Note that PM⁡(P,Q)=PM⁡(Q,P)\operatorname{PM}(\mathcal{P},\mathcal{Q})=\operatorname{PM}(\mathcal{Q},\mathcal{P}).

Optimal partial matching between cell structures

Figure 4. The optimal partial matching between the cell structures in the top row is illustrated by the colors in the bottom row. That is, the dark blue, orange, and green cells are matched with each other, whereas the pink, light blue, yellow, and red cells are matched to ∗\ast. The cost of the matching is the area of the shaded region on the right. The optimal independent matching would also pair the yellow cell with the green cell, reducing the cost by the area of the former.

Definition 3. An independent matching between P\mathcal{P} and Q\mathcal{Q} is a partial matching between coarsenings of P\mathcal{P} and Q\mathcal{Q}.

For cell structures P,Q⊂Ω\mathcal{P},\mathcal{Q}\subset\Omega denote by PM⁡(P,Q)\operatorname{PM}(\mathcal{P},\mathcal{Q}) the collection of partial matchings between the cells of P\mathcal{P} and Q\mathcal{Q} and by IM⁡(P,Q)\operatorname{IM}(\mathcal{P},\mathcal{Q}) the collection of independent matchings of the cells of P\mathcal{P} and Q\mathcal{Q}.

Definition 4. Let P,Q\mathcal{P},\mathcal{Q} be cell structures in Ω\Omega. The one-to-one discrete volume exchange metric between P\mathcal{P} and Q\mathcal{Q} is defined as

dDV1(P,Q):=12min⁡R∈PM⁡(P,Q)∑(E,F)∈RLn(E△F)(2)d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q}) := \frac{1}{2}\min_{\mathcal{R}\in\operatorname{PM}(\mathcal{P},\mathcal{Q})}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^{n}(E\mathbin{\triangle}F) \tag*{(2)}

where E△F:=(E∖F)∪(F∖E)E\mathbin{\triangle}F:=(E\setminus F)\cup(F\setminus E) denotes the symmetric difference between sets EE and $F and we treat ∗\ast as the empty set. Similarly, the many-to-many discrete volume exchange dissimilarity is

dDV2(P,Q):=12min⁡R∈IM⁡(P,Q)∑(E′,F′)∈RLn(E′△F′)(3)d_{\mathrm{DV}}^{2}(\mathcal{P},\mathcal{Q}) := \frac{1}{2}\min_{\mathcal{R}\in\operatorname{IM}(\mathcal{P},\mathcal{Q})}\sum_{(E',F')\in\mathcal{R}}\mathcal{L}^{n}(E'\mathbin{\triangle}F') \tag*{(3)}

We show that the minima are attained when P\mathcal{P} and Q\mathcal{Q} have countably many cells in Proposition 24. As we explain below, dDV1(P,Q)d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q}) can be computed efficiently by converting to an equivalent linear assignment problem.

Our main theorem is the equality of the continuous and discrete volume exchange metrics.

Theorem 5. Let Ω\Omega be a bounded, connected, open subset of Rn\mathbb{R}^{n} and let P,Q\mathcal{P},\mathcal{Q} be cell structures in Ω\Omega. Then

dV1(P,Q)=dDV1(P,Q)d_{\mathrm{V}}^{1}(\mathcal{P},\mathcal{Q})=d_{\mathrm{DV}}^{1}(\mathcal{P},\mathcal{Q})

and

dV2(P,Q)=dDV2(P,Q).d_{\mathrm{V}}^{2}(\mathcal{P},\mathcal{Q})=d_{\mathrm{DV}}^{2}(\mathcal{P},\mathcal{Q}).

The proof of Theorem 5 relies heavily upon the tools of geometric measure theory, a field that arose from the study of Plateau’s problem on minimal surfaces and its generalizations. Towards that end, we convert the statement into one concerning a distance between piecewise-constant functions, where a piecewise-constant function is one whose non-empty level sets form the cells of a cell structure. Note that the assignment of labels in a metric space (Y,δ)(Y,\delta) to the cells of a cell structure P\mathcal{P} induces to a piecewise-constant function p:Ω→Yp:\Omega\to Y, which is well-defined up to a set of Lebesgue measure zero. Given a partial matching R\mathcal{R} between the cells of P\mathcal{P} and those of Q\mathcal{Q}, we may choose YY to be a discrete metric space and label the cells of P\mathcal{P} and Q\mathcal{Q} so that matched cells have the same labels. In Lemma 23 we show

12∑(E,F)∈RLn(E△F)=∫Ωδ(p,q) dLn.\frac{1}{2}\sum_{(E,F)\in\mathcal{R}}\mathcal{L}^{n}(E\mathbin{\triangle}F)=\int_{\Omega}\delta(p,q)\,\mathrm{d}\mathcal{L}^{n}.

References

  1. [1]Zhi Jia, Zexi Gao, Jinjin Ji, Dexue Liu, Tingbiao Guo, and Yutian Ding. Evolution of twin boundaries and contribution to dynamic recrystallization and grain growth of Inconel 625. Advanced Engineering Materials, 21(9):1900426, 2019.DOI
  2. [2]P. Leavey, A. Sengupta, D. Rakhеja, O. Daescu, H.B. Arunachalam, and R. Mishra. Osteosarcoma data from UT Southwestern/UT Dallas for viable and necrotic tumor assessment (osteosarcoma-tumor-assessment). The Cancer Imaging Archive. https://doi.org/10.7937/tcia.2019.bvhjhdas, 2019.
  3. [3]Lívia Vásárhelyi, Zoltán Kónya, Ákos Kukovecz, and Róbert Vajtai. Microcomputed tomography–based characterization of advanced materials: a review. Materials Today Advances, 8:100084, 2020.DOI

Paper details

vlnc:W_e9qqd5yy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

LLMs

View statement
Looking for related papers…
Contents