A Robust Method for Interactive segmentation of
Circle of Willis
Zhiyang Song
College of Information Science and Technology
Beijing Normal University, Beijing
Beijing, P.R.C
Email: s2003zy@gmail.com
Xing Chen, Mingquan Zhou*, Zhongke Wu, Wuyang
Shui, Xingce Wang*
College of Information Science and Technology
Beijing Normal University, Beijing
Beijing, P.R.C
Email: vinllen@sina.com, mqzhou@bnu.edu.cn,
wangxingce@bnu.edu.cn, zwu@bnu.edu.cn,
sissun@126.com
Abstract—The Circle of Willis (CoW) is a circulatory
anastomosis that supplies blood to the brain and surrounding
structure. Detecting and quantifying the CoW is essential for the
prevention and treatment of aneurysm rupture and cerebral
Infarction. In this paper, we present a robust interactive method
to segment CoW mesh model from the whole cerebrovascular
mesh base on graph-cut. First we construct the weighted graph G
based on the input sketch. Then we find the minimum cost along
the partitioned edges with Min-Cut/Max-Flow method.
Moreover, we combine the shape-diameter function (SDF) and
the angles between the normal vector of the neighbor face to
construct the penalty energy which makes the method stable.
Computational results show that the proposed interactive
algorithm is robust, real time performance and friendly to user.
Keywords—interactive mesh segmentation; Graph-cut;
cerebrovascular mesh model; CoW; shape diameter function
I. INTRODUCTION
Cerebrovascular disease is a serious threat to human health.
It is a common disease for the elderly people. It is
characterized by high mortality, high recurrence rate, high
fatality rate. The patients often have many complications with
the cerebrovascular disease. Circle of Willis (CoW) are
important part of brain vessels locate at the base of the brain.
Recent researches show that the variations in CoW may be
associated with certain risks such as aneurismal development
[1]. What’s more, it is hard to observe and analysis the CoW,
because of its morphological complexity. The shape
reconstruction of CoW is the fundamental of further shape
analysis and measurement. If we want to focus on the CoW as
region of interest, segmentation the CoW from the
reconstruction cerebrovascular is necessary. It is a challenge to
which we focus on.
Mesh segmentation is a fundamental problem in computer
graphic [2], which is the basis of shape processing, such as
shape correspondence, morphing, skeleton extraction, mesh
editing, and 3D printing etc. [3] Segment mesh into meaningful
part can provide semantic information, which contribute to
some high level application such as shape understanding.
Over the past several years, many mesh segmentation
methods have been developed. In this paper we classified them
into three types: manual, automatic and interactive method. We
must select all the triangle of the interest part. The advantage
of manually segmentation is easy to implement and non-
conflict with user’s intuition. But when we meet a complex
geometric mesh model, the process will be tedious and time-
consuming. What’s more, we will have a very terrible user
experience for lacking of friendly interaction in the method.
Another manual method allows users to use selection tools
such as selection plan, ball or square to select interest part. This
kind of method is not very convenient when user wants to get
more accurate result. Besides there are many automatic
segmentation methods such as K-Means [4], Normalized Cuts
[5], Shape Diameter Function [6] and Randomized Cuts [5] etc.
These automatic segmentation methods are very convenient
and could get consistence result when using the same method
and the same data. But we should use many high level semantic
features to express our intuition, which is difficult to extract
with complex geometric such as brain vessel. So in this paper
we focus on the interactive method.
The common use session allow user to load the original
model as shown in Fig.1(a) and user can select the interested
part (Red color on the mesh) and uninterested part (Green color
on the mesh) on the brain vessel mesh as shown in Fig.1(b).
Then
(a) Original model (b) User selection (c) Result
Fig. 1. (a) is the original model. User selected interested part (Red) and
uninterested part (Green) show in (b). Then perform Graph-Cut to get
result show in (c)
we perform graph-cut to gain the best partition result as shown
in Fig.1(c). At last user can observe and refine the
segmentation result.
The main contributions of our work are