From the * Department of Medical Computer Sciences, Models of coronary arterial trees are generated by the algorithm of constrained constructive optimization (CCO). In a given perfusion area a binary branching network of straight cylindrical tubes is generated by
successively adding terminal segments to the growing structure. In each step the site of connection is chosen according to an optimization target function (total intravascular volume), and in any stage of development the tree
fulfills physiologic boundary conditions (constraints involving pressures, flows and bifurcation rules). CCO generates structures which in many aspects resemble real coronary arterial trees, except for very asymmetric bifurcations, occurring when a large branch gives off a tiny terminal segment. In the present work we evaluate an additional constraint within CCO, namely imposing a limit on the asymmetry of bifurcations during the construction
process. Model trees are grown with different limits imposed, and the effects on structure are studied both phenomenologically and via statistical descriptors. As the limit to asymmetry is tightened, blood is conveyed to the
perfusion sites via detours rather than directly and the comparison with measured data shows the structure to
change from a conveying to a delivering type of function. Simultaneously total intravascular volume, surface and
sum of segments' lengths increase. It is shown why and how local bifurcation asymmetry is able to determine the global structure of the optimized arterial tree model. Surprisingly, the pressure profile from inlet to terminals, being a functional characteristic, remains unaffected.
Assuming that arterial trees fulfill their task in an optimized fashion, one can expect that a procedure involving "optimization" has the potential of inducing model
structures closely related to what is found in reality
(Cohn, 1955 In previous reports we have described in detail the
method of CCO and the choice of physiological parameters (Schreiner and Buxbaum, 1993 In the present work we focus on a more refined aspect of CCO-generated trees, namely very small vessels
branching off from large segments. This morphometrical detail is considered an artifact of CCO trees, at least
in comparison with real coronary artery trees. We analyze the consequences, demonstrate a remedy, and reanalyze the results of an improved CCO-procedure,
having a "limit to asymmetry" included.
The Method of Constrained Constructive Optimization (CCO)
Structure and constraints.
Intending to create a dichotomously
branching (binary) tree of cylindrical tubes with Nterm terminal
segments, we first formulate appropriate constraints in order to
represent reasonable physiological conditions. To these ends we
select a perfusion area within which the model is allowed to
evolve. Somewhere along the boundary the site of inlet is adopted,
where blood enters via the feeding artery at a perfusion pressure
(pperf) and a total flow (Qperf). "Perfusion sites" are distributed all
over the perfusion area as evenly as possible, and at each perfusion site the distal end of a "terminal segment" (i.e., a segment
not bifurcating into daughters) yields a terminal flow (Qterm) at the
terminal pressure (pterm) to a microcirculatory black-box (not being modeled in detail). We require equal flows (Qterm = Qperf/
Nterm) and equal pressure at the entrance into all microcirculatory black-boxes (i.e., at the distal ends of all terminal segments).
Moreover, at each bifurcation we require the bifurcation constraint,
Department of Cardiothoracic Surgery, § Institute for Experimental Physics,
ABSTRACT
INTRODUCTION
METHODS
RESULTS
DISCUSSION
ACKNOWLEDGEMENTS
Abbreviation used in this paper
REFERENCES
ABSTRACT
INTRODUCTION
; Thompson, 1952
; LaBarbera, 1990
). This
is the basic idea of constrained constructive optimization (CCO),1 a computational technique developed to
generate optimized models of arterial trees from first
principles. Without the input of anatomical data, CCO
generates the structure of a tree of tubes by adding segment by segment in a geometrically optimized fashion. Since the growth of such a model is only limited by the
computational resources, highly complex models of
several thousand segments can easily be generated even
on medium scale facilities (Schreiner, 1993
).
). Moreover, the
generated trees have been analyzed with regard to
branching angles, pressure profiles, segment radii, and
perfusion inhomogeneity (Bassingthwaighte et al. 1989
;
Schreiner and Buxbaum, 1993
; Schreiner et al. 1994
),
all of which showed satisfactory agreement with experimental measurements (Zamir and Chee, 1986
, 1987
).
METHODS
(1)
![]() |
(2) |
![]() |
![]() |
(4) |
The constructive procedure: optimally adding another terminal segment.
The operations explained so far were based on the assumption
that a model tree already exists. Now we consider the constructive element of CCO by explaining how a new terminal segment
is added to a given tree. A flow chart of the CCO algorithm is
shown in Fig. 1.
CCO starts from a scaled but degenerate tree with one segment, carrying the flow 1 × Qterm to some arbitrary location within the perfusion area. Then, segments are added step by step to grow a tree model which fulfills all constraints as well as the criteria of optimality at all stages of its development. The resulting model trees may comprise several thousand segments, combining the fineness of fractal arterial tree models (Levin et al., 1986
Modification of CCO: Limiting Bifurcation Asymmetry
Motivation. There is one feature of CCO trees which deserves attention and remedy: In CCO-trees we find very thin segments branching off from thick mainstream segments. The reason is that CCO does not draw on any quantitative anatomical data and within "pure CCO" no restrictions are implemented precluding such structures. The degree of asymmetry of a bifurcation is usually expressed by the "symmetry index":
![]() |
(5) |
Imposing a limit on asymmetry. Extremely asymmetric bifurcations are avoided by one additional check during the "connection search" procedure:
Following optimization, each new bifurcation is subjected to a test of its symmetry index (as part of the restriction checks 2.1.3 in Fig. 1 showing the algorithm). The tentative connection site is only given the chance to be accepted if the symmetry index exceeds a preset threshold (On an intuitive basis the structural changes can be described most clearly by focusing on a specific region of interest. We focus on an area immediately below two major branches bifurcating from the mainstream (cf. Fig. 2, the path to the respective terminal sites marked blue) and inspect how the route of blood supply changes from panel A to D :
low = 0:
Without restriction of asymmetry the microcirculatorial area is supplied via a tiny side branch emerging directly from
one of the major branches (note that the bifurcation from the
major branch into this side branch has a very low value of
rad),
resulting in a very direct access to the site of supply.
low = 0.1:
With a slight restriction on asymmetry, we observe
that most regions in the vicinity of large branches are supplied by
small subtrees with approximately four to six terminals. The roots
of these subtrees are thick enough to pass the check for asymmetry and thus can directly branch off from one of the major branches. However, the route of blood supply is in most cases slightly longer than in Fig. 2 A (passing through the subtree is a small detour).
low = 0.3:
Imposing a more severe restriction on asymmetry
continues the above trend and allows only larger subtrees to
emerge from the major branches. Concomitantly the detour to
the site of supply becomes larger.
low = 0.4:
With this very severe restriction, another additional
portion of bifurcations of the tree are forced to be "even more
symmetric". The very basic and dramatic changes induced in global structure may in fact be seen as a "switch in topology". In particular, the terminal site on which we have focused above, is now
supplied via a totally different subtree emerging from the left (instead of the right) major branch. (Please note that "right" and
"left" refers to the direction of blood flow.) The former route of
supply is no longer feasible, since the subtree has vanished. Instead, a new subtree has emerged far more distally.
Quantifying the Structural Impact Caused by the Limit to Asymmetry
The effect of low is not only visually evident (Fig. 2) but
can also be easily quantified.
In a binary branching tree, each segment belongs to a certain "bifurcation
level," defined by the number of bifurcations along the
path from the root of the tree towards the respective
segment (Zamir and Chee, 1987). The highest bifurcation level is usually reached by one (or several) of the
terminal segments most remote from the root of the
tree, and thus also characterizes the tree as a whole.
Limiting asymmetry drastically reduced the number of
bifurcation levels from approximately 100 (for
low= 0)
to as few as 28 for
low= 0.4 (Table I).
Table I. Dependence of Segment Radii and Number of Bifurcation Levels on the Limit to Asymmetry |
Another very useful classification criterion, the Strahler
order (Strahler, 1952, 1957
), is virtually unaffected by
the structural changes induced by
low (Table I).
A CCO-generated
tree with low= 0, i.e., without restriction on asymmetry, has a typical frequency chart of the symmetry indices displayed in Fig. 3 (solid curve), showing very asymmetric bifurcations with
rad as low as 0.05. Introducing
a limit on asymmetry cuts off the low-value tail of the
distribution and diverts new bifurcations towards the
right part of the frequency chart. In the plot this effect
is reflected by two features:
(a) The minimum values of rad are shifted to the
right as
low increases. Qualitatively this is exactly what
one would expect; quantitatively we have to notice,
however, that in the fully developed tree values of
rad
exist which are smaller than the limit imposed during
construction. The explanation for this surprising result is as follows: Even if symmetry indices
rad <
low are
prohibited in the instance of connecting a new terminal, the symmetry index of an existing bifurcation may
change later (item 2.1.2 in the algorithm) and violate
the limit. This will be the case if the two subtrees supplied by a bifurcation grow at different speeds (e.g.,
much more terminals are added to the left than to the
right subtree). Then segment radii must be adapted so
as to maintain a correct splitting of flow, thereby shifting
rad (towards asymmetry). Since this process of scaling cannot be subjected to any limitation, it may lead to
values of
rad (e.g.
0.16) well below the corresponding threshold (
low = 0.4).
(b) The modal value of the distribution is stable at
rad = 0.58 for all choices of
low. Frequencies left to the
mode decrease, while frequencies right to the mode increase as
low increases.
Without imposing a limit on asymmetry (Fig. 2 A) the
most asymmetric bifurcations occur along the main
branches when these give off single terminals. When
these structures are precluded via low > 0, the bifurcations with the lowest symmetry indices become distributed more or less evenly over the tree.
The detour of blood flow to a given perfusion site, as
induced by imposing a limit on asymmetry, can easily
be quantified by the ratio between the actual path
length of blood transport to a particular terminal segment and the corresponding bee-line (Schreiner et al.
1995). The actual path of blood from the tree's inlet to
any specific terminal site traverses a sequence of segments (contained in the set {path}) and has a total
length:
![]() |
(6) |
The bee-line, being defined as the straight connection between the inlet of the tree and the terminal site (Lbee-line) allows to define the "path-to-bee-line-ratio":
![]() |
(7) |
By definition, RL 1, since the path can never be
shorter than the bee-line. In fact, in any tree there are
several terminals for which RL is close to 1. A necessary
condition is a very straight arrangement of the segments, not significantly deviating from a common direction, usually that of a mainstream artery (Fig. 4).
Generally, the majority of segments show moderate values of RL, whereas a minority of segments have very
large values of RL (the distribution of RL is right
skewed, with the skewness increasing from 1.73 to 12.0 as
low increases from 0 to 0.4). The mean values of RL
rise only from 1.23 to 1.53, whereas the maximum values of RL (characterizing the most severe detour in a
tree) increase drastically from 2.13 to 35.8. All these
features quantitatively characterize the effect of a restriction on local asymmetry.
Orientation of terminal segments.
In the CCO-tree with
low = 0 blood accesses the terminal sites in a rather direct fashion, whereas detours arise with increasing
low.
One can expect that, following a detour, the perfusion
site is finally reached from a direction more at random
than in the case of a direct access. To investigate this
quantitatively, the orientation of each terminal segment is computed relative to the most direct access,
namely the orientation of the respective bee-line:
![]() |
(8) |
where and
are the vectors of bee line and segment,
respectively. Fig. 5 shows the resulting distribution of
angles. Surprisingly, almost no difference is noticeable
between limited and unlimited asymmetry.
Dependence of Global Quantities on the Limit to Asymmetry
The change in structure, characterized by additional
detours in reaching the perfusion sites, is accompanied
by changes in global morphometric descriptors such as
total volume, total surface, and the sum of segment
lengths. As local asymmetry is reduced by increasing
lowfrom 0 to 0.4, the total volume and total surface rise
by ~10 and 8%, respectively (Fig. 6). The sum of segment lengths shows only a very small and random variation (0.7%).
Increasing path lengths requires a concomitant increase in radii so as to keep the total resistance constant. The largest radius within the tree, i.e., that of the
root segment, increases by 1.7% when low varies between 0 and 0.4 (see Table I). At the same time, the relation between the radii of the smallest segment of the
tree and its root segment remains almost constant (Table I).
Quantifying the Functional Impact Caused by the Limit to Asymmetry
Branching rate, conveying and delivering type of function.Human coronary arteries have been analyzed regarding their "conveying" and "delivering" type of function
(Zamir, 1988), which is closely related to bifurcation
asymmetry. Conveying vessels are those which accomplish the transport of blood to a remote part of tissue.
Along their way they can only "afford" to lose little flow
through small side branches and diminish in radius only slightly across such bifurcations. In contrast, delivering vessels bifurcate close to symmetric (thereby severely diminish in radius) and thus yield the whole flow
carried to the tissue within a short distance. The decline of radius across a bifurcation is described by the
"branching rate" (Zamir, 1988
):
![]() |
(9) |
which is related to the symmetry index via Eq. 1:
![]() |
(10) |
Eq. 10 shows that increasing symmetry (rad) is coupled
to decreasing branching rate (
).
Following the "main path" (i.e., choosing always the
larger daughter along a particular path) of a vessel
tree, the radius diminishes at each bifurcation according to the respective branching rate . One usually encounters different values of
, since the reduction in radius of the main vessel depends on the radius of the
branch according to Eq. 10. Eq. 1 is not identically but
approximately fulfilled in real trees (Kamiya and Togawa, 1972
). If the branching rate were constant, the
relative decrease in radius after traversing n bifurcations along a main path would simply be given by:
![]() |
(11) |
In a semi-log plot over n this ratio appears as a
straight (descending) line, the slope of which is given
by log(). For real coronary trees (Zamir, 1988
) and
for realistic models the average value of
may be computed via a linear regression.
It is now very interesting to compare experimental
measurements on the branching rate (Zamir, 1988)
with the results obtained from the CCO-model. We extracted the radii of successive segments along the
"main branch" of each CCO-tree and plotted the ratio of segment radius and radius of the root in a semi-log
plot over the bifurcation level (Fig. 7).
Table II. Dependence of Branching Rate on the Limit to Asymmetry |
Linear regressions were computed according to least
squares, and the corresponding values of (computed
from the regression coefficient) are given in Table II.
The CCO-tree without a limit to asymmetry shows the
slowest decline in radius with ( = 0.978; this means that
on the average the larger daughter of a bifurcation shrinks
to 97.8% of the parent's radius. According to experimental work (Zamir, 1988
), where vessels with
\> 0.96
are classified as conveying, this CCO-tree definitely belongs to the conveying or "distributing" type of vessel.
If bifurcation asymmetry is increasingly limited, the
radii along the main path diminish more rapidly (Fig.
7). The corresponding branching rate declines to = 0.883 for
lim = 0.4, thus classifying the main path of
this tree as a delivering vessel in terms of experimental
data (Zamir, 1988
).
The same is true for the flow carried by the segments along the main path: With unlimited asymmetry the flow decreases in numerous small steps due to the flow loss into small side branches, bifurcating from the main path in close succession. With a limit to asymmetry, about the same average flow loss per unit path length is observed, however flow decreases in fewer but more pronounced steps.
It is important to notice that the branching rate is solely
defined on a structural basis (bifurcation levels) whereas
actual segment lengths are completely ignored. It is interesting to show that this structural approach is able to
discriminate between conveying and delivering types of
vessels whereas a "metric approach," using segment
lengths, is not. Therefore we also plot against the
(metric quantity) path length (Fig. 8) rather than against the bifurcation level. The decline in radius with reference to the root is approximately linear in path length,
but regressions show very similar slopes (
l) and are unable to discriminate between trees (Table II).
Pressure profile and bifurcation asymmetry.
To obtain the pressure profile over a CCO model tree we consider the pressure at the distal end as representative for the whole segment. For any segment, pdist can be computed by adding up the segmental pressure gradients along the path from the root to the respective segment:
![]() |
(12) |
Specifically for terminal segments, summing up segmental pressure gradients identically yields the unique terminal pressure, pterm, which enters the model as a constraint.
To obtain the pressure profile, pressures of single
segments are usually grouped into classes equidistantly
spaced in the logarithm of segment radius (Chilian et
al. 1990). In such a semi-log plot, the pressure profile
of a real arterial tree should appear close to a straight
line (van Beek et al. 1989
). The fact that the CCO
model reproduces this feature nicely (Fig. 9) is an additional confirmation of model adequacy.
With regard to bifurcation asymmetry, we were surprised to find that the pressure profiles are almost identical for the CCO-tree with unlimited asymmetry (low = 0) and the tree with
low = 0.4, despite the markedly different structures of these trees.
In the range of very small radii, an increasing number of terminal segments contribute to the pressure average of each class, and for r 0.06 mm there are exclusively terminals. They all contribute the unique pressure (pterm = 60 mm Hg), and hence the spread is zero
(error bars coincide with mean values).
CCO generates the structure and geometry of arterial
tree models without drawing on any information from
topographic anatomy. Yet the models resemble real
coronary arterial trees in many features, as discussed
and evaluated in previous reports (Schreiner and Buxbaum, 1993; Schreiner et al., 1994
; Schreiner et al.,
1995
). However, the existence of very small side
branches emerging from big vessels is conspicuous
(Fig. 2 A) when compared with real coronary trees,
where these structures are rarely found. Therefore we
added an additional constraint to CCO by limiting the
asymmetry of any new bifurcation when the tree is generated. The resulting changes in structure are not only
obvious to visual inspection (detours emerge as a consequence of avoiding highly asymmetric bifurcations,
see Fig. 2, B-D) but can also be quantified by a set of
statistical descriptors.
In the literature the asymmetry of bifurcations has
also been related to the functional capabilities of coronary arteries (Zamir, 1988). Asymmetric bifurcations
only give off small side-branches and allow the vessel to
convey blood across larger distances, which may allow
for a large number of bifurcation levels along such a
vessel. In contrast, symmetrically bifurcating vessel
trees readily deliver blood to the tissue and reach the
terminal level after only a few bifurcation levels. These
functional differences are most clearly reflected in the
branching rate analysis. First, the low number of bifurcation levels in "more symmetric trees" most naturally
leads to a more rapid decline in radius (see Fig. 7). The
low spread of data around the regression line proves
that the trees with a severe limit on asymmetry exhibit
almost constant branching rates. The result for the tree
without a limit on asymmetry is completely different: in
the large-caliber region of its main path we observe several series of consecutive segments, with radii decreasing only slightly within each series. This is due to very small but numerous side branches, each leaving the radius of the continuing main-stream vessel almost unaffected. Two adjacent series are divided by a distinct
downward step in radius, corresponding to a more
prominent sidebranch. Thus the slope of the regression line represents only the average decline in radius,
resulting in lower values of R2 (cf., Table II). Moreover,
the peripheral part of the main path shows a markedly
steeper slope in the semi-log plot, indicating that bifurcations become more and more symmetric. In fact, the local slope for bifurcations beyond a level of 80 is similar to that found for
low = 0.4.
The interpretation of these results and the comparison with measured data taken from the literature
(Zamir, 1988) shows that, in terms of Zamir's definition (Zamir, 1988
), CCO-models have been turned
from conveying to delivering by imposing a limit on asymmetry.
Another descriptor most directly affected is the probability distribution of rad, which is skewed towards
larger values while its modal value remains constant as
low increases (Fig. 3). We recall the striking observation that during further growth of the tree, existing bifurcations may be diverted towards asymmetry, even beyond the limit valid for newly generated ones.
Simultaneously with the probability distribution, the
geometrical and topological locations of the most asymmetric bifurcations in the tree change: for low = 0 these are concentrated along the major branches
whereas for
low = 0.4 the most asymmetric bifurcations
are randomly distributed over the tree.
The "amount of detours" itself was characterized by
the path-to-bee-line-ratio (Fig. 4). Imposing a limit on
asymmetry increases the "mean amount of detours"
only moderately (from 1.23 for low = 0 to 1.53 for
low = 0.4, i.e., by a factor of 1.53/1.23 = 1.24) whereas
the most excessive detours increase drastically in length
(from 2.13 to 35.8, respectively, i.e., by a factor of 35.8/
2.13 = 16.8).
The effects of the limit to asymmetry on global quantities is easily understood by considering the implications of detours replacing the straight access: (a) detours lengthen the paths and thus directly increase the
total sum of segment lengths. Since total surface and
volume are both proportional to segment lengths (S l · r, V
l · r2), they also increase (Fig. 6). (b) Despite
longer paths the total resistance to flow (according to
Poiseuille's law [Fung, 1984
]) must remain constant
(R
l/r4), so as to fulfill the boundary conditions. This
is only possible if radii increase (to compensate for increasing lengths). This contributes a second factor to
the growth in surface and volume (proportional to r
and r2, respectively), which together with the effect of
segment lengths, yields increases of 8 and 10%, respectively.
The pressure profile from the inlet to the terminal
segments of the tree was found to be almost unaffected
by the structural changes induced by limited asymmetry (Fig. 9). This finding parallels a result found earlier,
namely that the structural changes induced by different
optimization targets do not influence the pressure profile either (Schreiner et al., 1995). We may therefore
conclude that structural changes on the whole do not
severely influence the pressure profile.
The horizontal portion belonging exclusively to terminal segments (r 0.06 mm) is certainly an artifact
due to the need to truncate the model tree distally (to
keep the total number of segments within computational resources). In other words, the pressure profile
offers a glimpse of "boundary conditions artifacts," which may be evaluated by considering CCO trees of
increasing resolution in coming studies. From the
present work we can draw the preliminary conclusion
that predictions regarding pressures or flows are only
reliable if one keeps off from terminal segments (and
probably from their immediate parents as well).
The main result of the present work was to show qualitatively and quantitatively why and how a local restriction on asymmetry is able to influence the global structure of optimized arterial tree models.
Original version received 12 June 1996 and accepted version received 16 October 1996.
Address correspondence to Wolfgang Schreiner, Ph.D., FACA, Department of Medical Computer Sciences, University of Vienna, Spitalgasse 23, A-1090 Vienna, Austria. Fax: 43-1-40400-6677; E-mail: wolfgang.schreiner{at}akh-wien.ac.at
The authors wish to thank Mrs. E. Sumetzberger for preparing the manuscript.
This work was supported by the Bundesministerium für Wissenschaft und Forschung, grant 49.820/4-24/92.
CCO, constrained constructive optimization.