# Extracting Information about the Rotator Cuff from Magnetic Resonance Images Using Deterministic and Random Techniques

Authors: F. A. De Los Ríos; M. Paluszny
Journal: Computational and Mathematical Methods in Medicine
 (2015)

---

## Abstract

We consider some methods to extract information about the rotator cuff based on magnetic resonance images; the study aims to define an alternative method of display that might facilitate the detection of partial tears in the supraspinatus tendon. Specifically, we are going to use families of ellipsoidal triangular patches to cover the humerus head near the affected area. These patches are going to be textured and displayed with the information of the magnetic resonance images using the trilinear interpolation technique. For the generation of points to texture each patch, we propose a new method that guarantees the uniform distribution of its points using a random statistical method. Its computational cost, defined as the average computing time to generate a fixed number of points, is significantly lower as compared with deterministic and other standard statistical techniques.


---

## Body

## 1. Introduction and Preliminaries

The rotator cuff is a group of muscles and tendons connected to the humerus head whose function is the mobility and stability of the shoulder. The anatomy and physiology of the rotator cuff is complex and it is interconnected to other muscle groups in the shoulder. These muscle groups perform multiple functions and are often stressed during various activities. Disease of the rotator cuff is the most common cause of shoulder pain and dysfunction in adults; see [1, 2].A rotator cuff tear is a tear of one or more of the tendons of the four rotator cuff muscles; these can be classified according to their depth into full thickness and partial thickness tears; see [1, 2]. Magnetic resonance imaging plays a major role in helping to identify rotator cuff affections. In fact many surgeons rely on magnetic resonance images to assist in decision making and presurgical planning for patients with rotator cuff pain; see [3].In this research, we explore methodologies to extract information about the rotator cuff from magnetic resonance images; particularly we emphasize on the detection of supraspinatus tendon partial tears. We consider special domains on ellipsoids and in particular triangular Bézier patches to cover the humerus head close to the affected area; these patches are textured with the information of the magnetic resonance images using the trilinear interpolation technique; see [4]. To texture the patch two techniques are considered: a deterministic method and a random method. The random generation methodology can be chosen in a way that it ensures a uniform distribution of points and hence it avoids the systematic accumulation in specific areas. Therefore, we define families of special ellipsoidal patches, and we present an algorithm for the random generation of points uniformly distributed on the patch (see [5]). The computational efficiency of this algorithm, measured as the average computing time to generate a fixed number of points, is compared with other nonrandom generating techniques, namely, the classical de Casteljau algorithm and the Bernstein polynomial evaluation of triangular Bézier patches; see [6–11].The paper is organized as follows. In Section2, we describe a statistical technique to generate uniformly distributed points on patches, focusing on the case of the upper half of an ellipsoid. In Section 3, we center our discussion on the sphere and the ellipsoid of revolution, and we compare them with the case of the general ellipsoid. Finally, in Section 5 we present the comparison of the computational costs.


## 2. Random Evaluation of Uniformly Distributed Points

In this section, we review the problem of sampling uniformly distributed points on a parametric surface that lies on the upper half of an ellipsoid centered at the origin with semiaxesa1≥a2≥a3>0. Let us denote this surface by sx=sx1,x2=x1,x2,x3x1,x2. Namely, s is defined as the graph of the function x3 on the domain D:
(1)x3=a31-x1a12-x2a22,D=x:α2a21-x1a12<x2<α1a21-x1a12,1-x1a12β2<x1<β1,
where i=1,2 and αi≤1, βi≤a1. We want to generate uniformly distributed points in the image of the domain D. This allows us to guarantee that the generated points will not accumulate; this feature is very important for the visualization.That is to say, we will generate values of a random vectorX=X1,X2 such that sX is uniformly distributed on sD. This condition means that, given A∈R2 in D and denoting by λ the Lebesgue measure of dimension 2 for the surface, the probability of sX∈sA must be equal to λsA/λsD; see [5, 12]. Taking into account the fact that x3 is continuously differentiable, according to [13] the uniformity implies that
(2)Pω:sXω∈sA=Pω:Xω∈A=λsAλsD=∫A‍1+∂x3/∂x12+∂x3/∂x22dxλsD.The expression (2) implies that X must have density with respect to the Lebesgue measure of dimension 2, given by
(3)fx1,x2=1λsD1+∂x3∂x12+∂x3∂x22,
if x∈D and 0 otherwise.In this sense, if we compute the partial derivatives ofx3 with respect to x1 and x2 and let δ1=1-a3/a12, δ2=1-a3/a22, and κ=λsD-1, the density function f for x∈D can be written as
(4)fx1,x2=κ1-δ1x1/a12-δ2x2/a221-x1/a12-x2/a22,
and, given that a1≥a2≥a3>0, we have 1>δ1≥δ2≥0. Namely, to satisfy the uniformity condition, it is necessary to generate the random vector X with distribution f given by (4).The strategy to generateX consists in making a change of variables to transform D into a rectangle. Let y=y1,y2=gx1,x2 be a variable change such that its inverse x1,x2=g-1y1,y2 is
(5)x1=a1y1,x2=a2y21-y12,inthedomainDg=y1,y2:β2a1<y1<β1a1,α2<y2<α1.The mappingg is one-to-one and continuously differentiable so, using the change of variables theorem, we find that the density of the vector Y=(Y1,Y2)=g(X) with respect to the Lebesgue measure is
(6)fgy=κa1a21-δ1y121-my1y221-y22
for y∈Dg, and m(y1)=δ21-y12/1-δ1y12; see [14].Note that the problem of generatingX can be solved by generating the random vector Y and then pulling back by g.Next, to generate the random vectorY for a spherical patch or for a patch of an ellipsoid of revolution, we will consider a simplified technique. This is what we will do in the next section and we will compare it with the general ellipsoid.


## 3. Patch Evaluation: Sphere and Ellipsoid

### 3.1. Sphere

In the case of a sphere we havea1=a2=a3 and δ1=δ2=0; hence the joint density of Y on Dg is
(7)fgy=κa1211-y22.
In this case the function fgy can be written as the product of its two marginal functions fg,1 and fg,2; therefore the random variables Y1 and Y2 are independent.The independence condition allows for the generation ofY using the inverse transform method; see [5]. We consider inverse images of the accumulated distributions of fg,1 and fg,2, namely, Fg,1-1 and Fg,2-1, respectively. To generate Y, we take into account the fact that if U=U1,U2 are uniformly distributed in the interval 0,1, then Y=Fg,1-1U1,Fg,2-1U2 is distributed with density fg. Explicitly, we compute
(8)Fg,1-1U1=β1U1+β21-U1a1,Fg,2-1U2=sinU2arcsinα1+1-U2arcsinα2.


### 3.2. Ellipsoid of Revolution

For an ellipsoid of revolution we havea2=a3 and δ2=0; hence the joint density of Y on Dg is
(9)fgy=κa1a21-δ1y1211-y22.
Let us note that the random variables Y1,Y2 whose marginal distributions we denote by fg,1 and fg,2, respectively, are statistically independent; therefore it is again possible to use the inverse transform method to generate the random vector Y.Namely, to generateY, we generate the vector U=U1,U2 of independent components and uniformly distributed and then we compute the vector Y=Fg,1-1U1,Fg,2-1U2. Specifically,
(10)Fg,1-1U1=ϕ-1U1ϕβ1a1;δ1+1-U1ϕβ2a1;δ1;δ1,Fg,2-1U2=sinU2arcsinα1+1-U2arcsinα2,
where
(11)ϕt;δ1=∫1-δ1t2dt=2δ1-1δ1t1-δ1t2+arcsinδ1t.
The function ϕ is strictly monotone on the interval β2/a1,β1/a1, so its inverse function ϕ-1 exists, and it is also strictly monotone.The functionϕ-1 has no closed analytic expression but it can be approximated numerically. We would like the approximation to be independent of the shape parameter δ1. Consider the random variable Z=δ1Y1. It has accumulated distribution:
(12)FZz=ϕz;1-ϕr2;1ϕr1;1-ϕr2;1,
and it is defined on the interval r2,r1, where ri=βi/a1δ1. Let FZ* be the distribution FZ in the special case that the interval r2,r1 is -1,1. In the literature FZ* is referred to as the semicircular distribution; see [15]. In accordance with [16], it is possible to sample Z from the inverse function FZ*-1(u):
(13)FZ-1u=FZ*-1uFZ*r1+1-uFZ*r2=ϕ-1uϕr1;1+1-uϕr2;1;1,
for u∈0,1 and ri as above. In this sense, to generate Z, we could draw a random number U with uniform density on the interval I=ϕr2;1,ϕr1;1 and then evaluate ϕ-1U;1.


#### 3.2.1. Approximation ofϕ-1

To generate the random variableZ, we approximate the function ϕ-1u;1 with a cubic spline. More precisely, let s0<s1<⋯<sn-1 be a partition of I, we compute ϕsk;1 for k=0,1,…,n-1, and we do monotone piecewise cubic Hermite interpolation of the data set ϕsk;1,skk=0n-1 according to the method described in [17]. There, the authors derive the necessary and sufficient conditions for a cubic Hermite interpolator to be piecewise monotone and develop an algorithm to build it for a monotone data set. In MATLAB, for example, we can do monotone interpolation with the function pchip.For the sake of completeness, next we review two general methods to sample random variables with arbitrary distributions. We will compare these with the special techniques presented here for the ellipsoid of revolution.


#### 3.2.2. Acceptance-Rejection Method

The acceptance-rejection method is one of the most useful general methods for sampling from general distributions. It can be applied to both discrete and continuous distributions and even to multidimensional distributions although its efficiency rapidly decreases as the dimension increases [5].We want to simulate a random variableX with density given by f(x). Let us suppose that we have a method to sample a random variable Y with density g(y). In addition, let us assume that it is possible to bound the ratio f(x)/g(x) by a constant c>0; c=sup⁡x{f(x)/g(x)}.The acceptance-rejection method is based on the following algorithm [5].(1)
GenerateX with density gx.(2)
GenerateU with uniform density on the interval 0,1.(3)
IfU≤f(x)/cg(x) output X; else return to step (2).This is to say, generateX with density gx and accept it with probability f(x)/cg(x); else reject X and try again. The efficiency of the acceptance-rejection method is defined as PU≤f(X)/cg(X), and it is 1/c; see [5].Specifically, to simulate the random variableY1 whose density we have denoted by fg,1(y1), we could use the acceptance-rejection algorithm taking fx=fg,1x and g(x)=a1/β1-β2χ(β2/a1,β1/a1)x. Namely, the random variable X will be sampled uniformly on the interval β2/a1,β1/a1.To determine the constantc in the algorithm, let us note that the maximum of the function fg,1(x) which will be denoted by f* is fg,1(0) if 0∈β2/a1,β1/a1 or max⁡fg,1(β2/a1),fg,1(β1/a1) otherwise. Choosing c=β1-β2/a1f* and taking into account the fact that g(x)=a1/β1-β2 on the interval β2/a1,β1/a1, it is clear that f(x)≤cg(x).


#### 3.2.3. Hastings Algorithm

The Hastings algorithm is a popular technique to simulate random variables with densities difficult to handle. Given a particular probability densityπ(x) defined on a region S and an arbitrary probability density qx∣y that depends on (x,y)∈S×S, a sketch of Hastings’ algorithm (see [18]) is as follows.(1)
Select an initial pointX0∈S.(2)
On thet iteration do the following.
(a)
GenerateX′ of the density qx∣xt-1.(b)
Compute(14)ρXt-1,X′=min⁡1,πX′qXt-1∣X′πXt-1qX′∣Xt-1.(c)
Take(15)Xt=X′withprobabilityρXt-1,X′Xt-1withprobability1-ρXt-1,X′.(3)
Repeat step (2) until equilibrium is reached.In other words, in the iterationt, the Hastings sampler chooses a sample X′ of the instrumental density q; this density could depend on the last sampled variable Xt-1. The algorithm decides to accept the new random variable X′ according to (15).The Hastings algorithm induces a Markov chain whose stationary distribution has densityπ(x), regardless of the choice of the instrumental density q. In practice, q is chosen as being easy to sample and close to the density π(x).


### 3.3. General Ellipsoid

We can apply Hastings or acceptance-rejection method to each of the components of a vector but this leads to the computation of elliptic integrals which is computationally very expensive.Alternatively using Hastings on the random vector is less costly but exceeds by a factor much greater the deterministic evaluation using the classical methods of de Casteljau and Bézier.


## 3.1. Sphere

In the case of a sphere we havea1=a2=a3 and δ1=δ2=0; hence the joint density of Y on Dg is
(7)fgy=κa1211-y22.
In this case the function fgy can be written as the product of its two marginal functions fg,1 and fg,2; therefore the random variables Y1 and Y2 are independent.The independence condition allows for the generation ofY using the inverse transform method; see [5]. We consider inverse images of the accumulated distributions of fg,1 and fg,2, namely, Fg,1-1 and Fg,2-1, respectively. To generate Y, we take into account the fact that if U=U1,U2 are uniformly distributed in the interval 0,1, then Y=Fg,1-1U1,Fg,2-1U2 is distributed with density fg. Explicitly, we compute
(8)Fg,1-1U1=β1U1+β21-U1a1,Fg,2-1U2=sinU2arcsinα1+1-U2arcsinα2.


## 3.2. Ellipsoid of Revolution

For an ellipsoid of revolution we havea2=a3 and δ2=0; hence the joint density of Y on Dg is
(9)fgy=κa1a21-δ1y1211-y22.
Let us note that the random variables Y1,Y2 whose marginal distributions we denote by fg,1 and fg,2, respectively, are statistically independent; therefore it is again possible to use the inverse transform method to generate the random vector Y.Namely, to generateY, we generate the vector U=U1,U2 of independent components and uniformly distributed and then we compute the vector Y=Fg,1-1U1,Fg,2-1U2. Specifically,
(10)Fg,1-1U1=ϕ-1U1ϕβ1a1;δ1+1-U1ϕβ2a1;δ1;δ1,Fg,2-1U2=sinU2arcsinα1+1-U2arcsinα2,
where
(11)ϕt;δ1=∫1-δ1t2dt=2δ1-1δ1t1-δ1t2+arcsinδ1t.
The function ϕ is strictly monotone on the interval β2/a1,β1/a1, so its inverse function ϕ-1 exists, and it is also strictly monotone.The functionϕ-1 has no closed analytic expression but it can be approximated numerically. We would like the approximation to be independent of the shape parameter δ1. Consider the random variable Z=δ1Y1. It has accumulated distribution:
(12)FZz=ϕz;1-ϕr2;1ϕr1;1-ϕr2;1,
and it is defined on the interval r2,r1, where ri=βi/a1δ1. Let FZ* be the distribution FZ in the special case that the interval r2,r1 is -1,1. In the literature FZ* is referred to as the semicircular distribution; see [15]. In accordance with [16], it is possible to sample Z from the inverse function FZ*-1(u):
(13)FZ-1u=FZ*-1uFZ*r1+1-uFZ*r2=ϕ-1uϕr1;1+1-uϕr2;1;1,
for u∈0,1 and ri as above. In this sense, to generate Z, we could draw a random number U with uniform density on the interval I=ϕr2;1,ϕr1;1 and then evaluate ϕ-1U;1.


### 3.2.1. Approximation ofϕ-1

To generate the random variableZ, we approximate the function ϕ-1u;1 with a cubic spline. More precisely, let s0<s1<⋯<sn-1 be a partition of I, we compute ϕsk;1 for k=0,1,…,n-1, and we do monotone piecewise cubic Hermite interpolation of the data set ϕsk;1,skk=0n-1 according to the method described in [17]. There, the authors derive the necessary and sufficient conditions for a cubic Hermite interpolator to be piecewise monotone and develop an algorithm to build it for a monotone data set. In MATLAB, for example, we can do monotone interpolation with the function pchip.For the sake of completeness, next we review two general methods to sample random variables with arbitrary distributions. We will compare these with the special techniques presented here for the ellipsoid of revolution.


### 3.2.2. Acceptance-Rejection Method

The acceptance-rejection method is one of the most useful general methods for sampling from general distributions. It can be applied to both discrete and continuous distributions and even to multidimensional distributions although its efficiency rapidly decreases as the dimension increases [5].We want to simulate a random variableX with density given by f(x). Let us suppose that we have a method to sample a random variable Y with density g(y). In addition, let us assume that it is possible to bound the ratio f(x)/g(x) by a constant c>0; c=sup⁡x{f(x)/g(x)}.The acceptance-rejection method is based on the following algorithm [5].(1)
GenerateX with density gx.(2)
GenerateU with uniform density on the interval 0,1.(3)
IfU≤f(x)/cg(x) output X; else return to step (2).This is to say, generateX with density gx and accept it with probability f(x)/cg(x); else reject X and try again. The efficiency of the acceptance-rejection method is defined as PU≤f(X)/cg(X), and it is 1/c; see [5].Specifically, to simulate the random variableY1 whose density we have denoted by fg,1(y1), we could use the acceptance-rejection algorithm taking fx=fg,1x and g(x)=a1/β1-β2χ(β2/a1,β1/a1)x. Namely, the random variable X will be sampled uniformly on the interval β2/a1,β1/a1.To determine the constantc in the algorithm, let us note that the maximum of the function fg,1(x) which will be denoted by f* is fg,1(0) if 0∈β2/a1,β1/a1 or max⁡fg,1(β2/a1),fg,1(β1/a1) otherwise. Choosing c=β1-β2/a1f* and taking into account the fact that g(x)=a1/β1-β2 on the interval β2/a1,β1/a1, it is clear that f(x)≤cg(x).


### 3.2.3. Hastings Algorithm

The Hastings algorithm is a popular technique to simulate random variables with densities difficult to handle. Given a particular probability densityπ(x) defined on a region S and an arbitrary probability density qx∣y that depends on (x,y)∈S×S, a sketch of Hastings’ algorithm (see [18]) is as follows.(1)
Select an initial pointX0∈S.(2)
On thet iteration do the following.
(a)
GenerateX′ of the density qx∣xt-1.(b)
Compute(14)ρXt-1,X′=min⁡1,πX′qXt-1∣X′πXt-1qX′∣Xt-1.(c)
Take(15)Xt=X′withprobabilityρXt-1,X′Xt-1withprobability1-ρXt-1,X′.(3)
Repeat step (2) until equilibrium is reached.In other words, in the iterationt, the Hastings sampler chooses a sample X′ of the instrumental density q; this density could depend on the last sampled variable Xt-1. The algorithm decides to accept the new random variable X′ according to (15).The Hastings algorithm induces a Markov chain whose stationary distribution has densityπ(x), regardless of the choice of the instrumental density q. In practice, q is chosen as being easy to sample and close to the density π(x).


## 3.2.1. Approximation ofϕ-1

To generate the random variableZ, we approximate the function ϕ-1u;1 with a cubic spline. More precisely, let s0<s1<⋯<sn-1 be a partition of I, we compute ϕsk;1 for k=0,1,…,n-1, and we do monotone piecewise cubic Hermite interpolation of the data set ϕsk;1,skk=0n-1 according to the method described in [17]. There, the authors derive the necessary and sufficient conditions for a cubic Hermite interpolator to be piecewise monotone and develop an algorithm to build it for a monotone data set. In MATLAB, for example, we can do monotone interpolation with the function pchip.For the sake of completeness, next we review two general methods to sample random variables with arbitrary distributions. We will compare these with the special techniques presented here for the ellipsoid of revolution.


## 3.2.2. Acceptance-Rejection Method

The acceptance-rejection method is one of the most useful general methods for sampling from general distributions. It can be applied to both discrete and continuous distributions and even to multidimensional distributions although its efficiency rapidly decreases as the dimension increases [5].We want to simulate a random variableX with density given by f(x). Let us suppose that we have a method to sample a random variable Y with density g(y). In addition, let us assume that it is possible to bound the ratio f(x)/g(x) by a constant c>0; c=sup⁡x{f(x)/g(x)}.The acceptance-rejection method is based on the following algorithm [5].(1)
GenerateX with density gx.(2)
GenerateU with uniform density on the interval 0,1.(3)
IfU≤f(x)/cg(x) output X; else return to step (2).This is to say, generateX with density gx and accept it with probability f(x)/cg(x); else reject X and try again. The efficiency of the acceptance-rejection method is defined as PU≤f(X)/cg(X), and it is 1/c; see [5].Specifically, to simulate the random variableY1 whose density we have denoted by fg,1(y1), we could use the acceptance-rejection algorithm taking fx=fg,1x and g(x)=a1/β1-β2χ(β2/a1,β1/a1)x. Namely, the random variable X will be sampled uniformly on the interval β2/a1,β1/a1.To determine the constantc in the algorithm, let us note that the maximum of the function fg,1(x) which will be denoted by f* is fg,1(0) if 0∈β2/a1,β1/a1 or max⁡fg,1(β2/a1),fg,1(β1/a1) otherwise. Choosing c=β1-β2/a1f* and taking into account the fact that g(x)=a1/β1-β2 on the interval β2/a1,β1/a1, it is clear that f(x)≤cg(x).


## 3.2.3. Hastings Algorithm

The Hastings algorithm is a popular technique to simulate random variables with densities difficult to handle. Given a particular probability densityπ(x) defined on a region S and an arbitrary probability density qx∣y that depends on (x,y)∈S×S, a sketch of Hastings’ algorithm (see [18]) is as follows.(1)
Select an initial pointX0∈S.(2)
On thet iteration do the following.
(a)
GenerateX′ of the density qx∣xt-1.(b)
Compute(14)ρXt-1,X′=min⁡1,πX′qXt-1∣X′πXt-1qX′∣Xt-1.(c)
Take(15)Xt=X′withprobabilityρXt-1,X′Xt-1withprobability1-ρXt-1,X′.(3)
Repeat step (2) until equilibrium is reached.In other words, in the iterationt, the Hastings sampler chooses a sample X′ of the instrumental density q; this density could depend on the last sampled variable Xt-1. The algorithm decides to accept the new random variable X′ according to (15).The Hastings algorithm induces a Markov chain whose stationary distribution has densityπ(x), regardless of the choice of the instrumental density q. In practice, q is chosen as being easy to sample and close to the density π(x).


## 3.3. General Ellipsoid

We can apply Hastings or acceptance-rejection method to each of the components of a vector but this leads to the computation of elliptic integrals which is computationally very expensive.Alternatively using Hastings on the random vector is less costly but exceeds by a factor much greater the deterministic evaluation using the classical methods of de Casteljau and Bézier.


## 4. Surfaces in Medical Visualization

Medical imaging is the set of techniques and procedures used to create digital images of parts of the human body for clinical purposes or medical research. Digital images are composed of individual pixels, to which discrete brightness or color values are assigned. They can be efficiently processed, objectively evaluated, and made available at many places at the same time by means of appropriate communication networks and protocols, such as Picture Archiving and Communication Systems (PACS) and the Digital Imaging and Communications in Medicine (DICOM) protocol, respectively.In fact, DICOM is a standard for handling, storing, printing, and transmitting information in medical imaging; see [19].Since the discovery of X-rays by Wilhelm Conrad Rötgen in 1895, medical images have become a major component of diagnostics, treatment planning and procedures, and follow-up studies; therein lies its importance in healthcare. Medical images are acquired using a variety of techniques and devices, including conventional radiography, computed tomography (CT), magnetic resonance imaging (MRI), ultrasound, and nuclear medicine. As stated in the preliminaries we will focus on rotator cuff MRI.The usual technique for the visualization of rotator cuff tears is by inspection of a sequence of parallel sections. We propose an alternative technique. We look at a curved surface along the humerus near the suspected area of the tear. This exhibits the full tear extension in a single view which is positioned in a natural way with respect to the humerus head. We choose the curved surface fitting the humerus head to be a patch of sphere or ellipsoid of revolution. These are estimated using standard least squares techniques.For the visualization of the tear we need to texturize it with the MRI data, that is, to evaluate (To evaluate the patch means to find the coordinates of all its points.) the patch and assign a gray level to each point.In the next section we look at various evaluation techniques, deterministic and random, and present comparison tables of their relative central processing unit (CPU) performance.


## 5. Comparison of Various Surface Evaluation Techniques

To generate the points of the patch we have several options. For the sake of comparison we will consider both a sphere octant and an ellipsoid of revolution octant. As mentioned in the introduction the patch evaluation methods are of two types: deterministic and random.In the case of a patch on the sphere a uniform distribution of points can be generated using the inverse transform method. On the other hand, if the surface is an ellipsoid of revolution we generate its points by combining the method of inverse transform in one dimension with methods such as the method based on the approximation ofϕ-1, acceptance and rejection, and Hastings algorithm.From the deterministic point of view, we will use the representation of the octant as a triangular Bézier patch; see [6].A triangular Bézier patch of degreen with control network bi∈E3 and associated weights wi∈R is a parametric surface b0n(u)∈E3. The parameter u=u,v,w represents the barycentric coordinates of a point in a triangular patch and the multi-index i=(i1,i2,i3) is related with a particular location in a triangular array of degree n. The triangular Bézier patch can be evaluated by means of either the de Casteljau algorithm or the Bernstein representation.The de Casteljau algorithm is a recursive procedure to compute a point on the triangular patch as follows (see [6]):
(16)biru=uwi+e1bi+e1r-1u+vwi+e2bi+e2r-1u+wwi+e3bi+e3r-1uwir,
where e1, e2, and e3 are the unit canonical vectors:
(17)wiru=uwi+e1u+vwi+e2u+wwi+e3u,r=1,…,n;i=n-r;bi0=bi.
Then b0nu is the position of the point corresponding to u.The second deterministic method uses homogeneous Bernstein polynomialsBin (see [6]):
(18)bnu=b0nu=∑i=n‍wibiBinu∑i=n‍wiBinu,
where bi are the control points and wi are the weights.De Casteljau and Bézier patch evaluation are the two standard techniques to compute points of a triangular patch. The Bézier evaluation is given by an analytic formula and the algorithm of de Casteljau is iterative but has some potentially useful side products such as the computation of the surface curvature. Nevertheless, none of these deterministic algorithms guarantees a uniform distribution of points on the patch.The random technique is based on methodologies that provide asymptotically uniform distribution of points on the patch. In practical terms this means that as the resolution is increased the information is retrieved more faithfully on the whole patch.Table1 illustrates the CPU performance of the algorithms in a standard personal computer (PC) for the generation of n points on an octant of a sphere (The sphere octant is realized in a rational Bézier patch of degree 4.). Our experiments show that, regardless of the number of points generated, the algorithm based on the inverse transform technique is faster than the deterministic algorithms. Further, the efficiency ratio for the random method with respect to the deterministic methods increases as the number of points generated increases.Table 1
Average computing time to generaten points on the octant of a sphere (seconds).
Method
n = 1035
n = 10011
n = 50086
Inverse transform
0.000168
0.000987
0.003989
Bernstein representation
0.003485
0.026029
0.125881
De Casteljau algorithm
0.002890
0.043633
0.212243For the ellipsoid, the comparison is given in Table2. Our results suggest that, regardless of the number of points generated, the algorithm based on an approximation of the inverse transform technique is faster than the other algorithms both deterministic and random. In addition, the efficiency ratio for the discussed method with respect to the other methods increases as the number of points generated increases.Table 2
Average computing time to generaten points on the octant of an ellipsoid of revolution (seconds).
Method
n = 1035
n = 10011
n = 50086
ϕ
-
1 approximation
0.001318
0.003352
0.010890
Acceptance-rejection
0.013956
0.125176
0.636031
Hastings
0.406324
2.225163
10.38507
Bernstein representation
0.003517
0.026096
0.126542
De Casteljau algorithm
0.002904
0.044050
0.212913


## 6. Conclusions

Visualization of medical data along curved surface patches is potentially a useful tool in medical research and clinical praxis. We consider the specific application in the case of the rotator cuff. We propose a family of patches fitted to the humerus head and texturing methods which are highly competitive with the standard Bernstein-de Casteljau deterministic algorithms.



---

*Source: 974562-2015-01-12.xml*