Crack Modeling via Minimum-Weight Surfaces in 3d Voronoi Diagrams Christian Jung1Claudia Redenbach1

2025-04-27 0 0 5.74MB 14 页 10玖币

侵权投诉

Crack Modeling via Minimum-Weight

Surfaces in 3d Voronoi Diagrams

Christian Jung1Claudia Redenbach1

1Technische Universit¨at Kaiserslautern

Gottlieb-Daimler-Straße 47, 67663 Kaiserslautern, Germany

Abstract: Shortest paths play an important role in mathematical modeling and image

processing. Usually, shortest path problems are formulated on planar graphs that con-

sist of vertices and weighted arcs. In this context, one is interested in ﬁnding a path of

minimum weight from a start vertex to an end vertex. The concept of minimum-weight

surfaces extends shortest paths to 3d. The minimum-weight surface problem is formu-

lated on a cellular complex with weighted facets. A cycle on the arcs of the complex

serves as input and one is interested in ﬁnding a surface of minimum weight bounded

by that cycle. In practice, minimum-weight surfaces can be used to segment 3d images.

Vice versa, it is possible to use them as a modeling tool for geometric structures such

as cracks. In this work, we present an approach for using minimum-weight surfaces in

bounded Voronoi diagrams to generate synthetic 3d images of cracks.

Keywords: cracks, shortest paths, macrostructure modeling, minimum-weight surfaces,

Voronoi diagram, integer programming, 3d images, microstructure modeling, adaptive

dilation

1 Introduction

The shortest path problem (SPP) is formulated on a planar (directed) graph consisting

of vertices and weighted arcs. Given a start and an end vertex, one is interested in

ﬁnding a path of minimal weight connecting these vertices. Shortest paths represent a

useful tool in 2d image processing in several contexts including image quilting [19] and

image segmentation. In particular, shortest paths have been used to segment linear, 1d

structures such as cracks in 2d images [2].

Minimum-weight surfaces were introduced in [21] and [15] as an extension of shortest

paths to 3d. The minimum-weight surface problem (MSP) is formulated on a cellular

complex consisting of vertices, arcs, weighted facets and cells. Here, the goal is to ﬁnd

a set of facets of minimal weight that is bounded by an input cycle. The voxel lattice in

arXiv:2210.05093v1 [cs.GR] 11 Oct 2022

a 3d image can be interpreted as a cellular complex. In this context, minimum-weight

surfaces have been used to segment ﬂat structures in medical 3d images [15].

The segmentation of cracks in images of concrete is a broad ﬁeld of research. A large

variety of segmentation methods have been studied for 2d and 3d images. Comprehensive

overviews and comparison studies in 2d and 3d can be found in [9] and [4], respectively.

In image segmentation, ground truths are necessary for an objective output evaluation.

Furthermore, they are prerequisite for training machine learning models such as convo-

lutional neural networks [8] and random forests [7]. In 2d, annotated data is abundantly

available, for example SDNET2018 [11]. For 3d images, manual annotation is not feas-

ible due to the large amount of data. Therefore, 3d ground truth images are scarce and

one has to rely on artiﬁcial data. Previously, the generation of synthetic cracks has been

realized via fractional Brownian surfaces [1, 4]. However, the Hurst index - a measure of

roughness - is the only parameter that can be used to control the shape of the surface.

Therefore, this model is rather limited.

Voronoi diagrams have been used previously for simulating crack propagation via ﬁnite

element methods [13, 16]. In this work, we propose a novel method to synthesize crack

structures in 3d images using Voronoi diagrams generated from random point processes.

The method includes two aspects:

First, we use minimum-weight surfaces as a tool to model the macrostructure of cracks.

Bounded 3d Voronoi diagrams serve as the underlying cell complexes. This leaves several

degrees of freedom such as the choice of the generating point processes, bounding cycles

and the facet weights.

Second, the computed surfaces are discretized to 3d binary images. The rough micro-

structure of cracks is modeled via a second Voronoi diagram on a ﬁner scale. Then, the

cracks are embedded into patches of real computed tomography (CT) images of concrete.

This paper is structured as follows. In Section 2, we outline the concept of shortest

paths. Their extension to minimum-weight surfaces is described in Section 3. Section 4

comprises our crack modeling pipeline using Voronoi diagrams. It includes a description

of our approach for macro- and microstructure modeling. Section 5 serves as conclusion

and outlook to possible future research.

2 Shortest paths

Let G= (V, A) be a directed graph consisting of a set of vertices Vand directed arcs

A⊆V×V. We use the notation α(a) for the start vertex and ω(a) for the end vertex

of an arc a∈A.

Furthermore, let c:A→R>0be a function assigning a non-negative weight to every arc

in A. A path in Gis a ﬁnite sequence of vertices and arcs, P= (v0, a0, v1, a1, . . . , ak−1, vk),

k≥0, with vi∈Vand ai∈Awith α(ai) = viand ω(ai) = vi+1 for i= 0, . . . , k −1. It

is called a cycle (or closed contour) if no arc and no vertex is included more than once

except for v0=vk. The weight of a path Pis given as c(P) = Pk−1

i=0 c(ai).

Given two vertices s, t ∈V, the SPP is looking for a path of minimum weight from sto

t. Many algorithms for solving the SPP exist, for example Dijkstra’s [10] or Bellman’s

and Ford’s algorithm [5].

SPPs can also be formulated as binary integer programs [17, 22]. Note that this approach

is less eﬃcient than the ones described in [10] or [5]. However, it gives a good intuition

for an analogue approach to compute minimum-weight surfaces which we describe in

Section 3.

Let sbe the start- and tthe end vertex of the path and let xbe a vector of binary

variables xi∈ {0,1}assigned to each arc ai. The SPP can then be formulated as

minimize X

i:ai∈A

c(ai)xi(1)

subject to Bx =p(2)

xi∈ {0,1}.(3)

The vertex-arc incidence matrix Band the vector pin constraints (2) are given as

Bj,i =





1 if vj=α(ai),

−1 if vj=ω(ai),

0 else

and pj=





1 if vj=s,

−1 if vj=t,

0 else.

The constraints (2) are ﬂow-conservation constraints. They ensure that every vertex

that is part of the path is incident to exactly one incoming and one outgoing arc, except

for the start- and end vertex. This results in the fact that any feasible solution must

contain a path from sto tand, by the assumption that all costs are strictly positive,

this ensures that the optimal solution is in fact a path without repeated vertices. The

variables xiare binary by constraint (3) and indicate whether arc aibelongs to the path

(xi= 1) or not (xi= 0). Finally, the objective in (1) is to minimize the weight over all

paths from sto t.

Note that, in case of negative arc costs, the problem of ﬁnding a shortest path without

repeated vertices becomes NP-hard (which can be seen by a reduction from the Hamilto-

nian Path Problem [12]). Thus, additional constraints become necessary and, hence, we

assume that all arc costs are strictly positive.

3 Minimum-weight surfaces

Minimum-weight surfaces have been presented in [21] and [15] as an extension of shortest

paths to 3d.

For our purposes, let K= (V, A, F, C) be a cellular complex consisting of a set of vertices

V, directed arcs A⊆V×V, facets F⊆A×. . . ×Aand cells C⊆F×. . . ×F.

Further, let w:F→R>0be a function assigning a non-negative weight to every facet

in F.

Note that (V, A) deﬁnes a (directed) graph. Given a cycle Hon (V, A), the MSP is

looking for a connected set of facets in Kof mimimum weight that is bounded by H.

To this end, arc directions may be assigned arbitrarily. Every facet is considered twice,

once in clockwise and once in counterclockwise orientation. The orientation of Hmust

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

CrackModelingviaMinimum-WeightSurfacesin3dVoronoiDiagramsChristianJung1ClaudiaRedenbach11TechnischeUniversitatKaiserslauternGottlieb-Daimler-Strae47,67663Kaiserslautern,GermanyAbstract:Shortestpathsplayanimportantroleinmathematicalmodelingandimageprocessing.Usually,shortestpathproblemsareformulate...

展开>> 收起<<

Crack Modeling via Minimum-Weight Surfaces in 3d Voronoi Diagrams Christian Jung1Claudia Redenbach1.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Crack Modeling via Minimum-Weight Surfaces in 3d Voronoi Diagrams Christian Jung1Claudia Redenbach1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: