A Sphere-Packing Model for the Optimal Treatment Plan
Long Yun
Ye Yungqing
Wei Zhen
Peking University
Beijing,China
Advisor:Liu Xufeng
Abstract
We develop a sphere-packing model for gamma knife treatment planning to determine the number of shots of each diameter and their positions in an optimal plan.
We use a heuristic approach to solve the packing problem,which is refined by simulated annealing.The criteria for an optimal plan are efficiency,conformity,fitness,and avoidance.We constru
ct a penalty function to judge whether one packing strategy is better than the other.The number of spheres of each size is fixed,the total number of spheres has an upper bound,and critical tissue near the target is avoided.
Computer simulation shows that our algorithmfits the four requirements well and runs faster than the traditional nonlinear approach.After detailed evaluation, we not only demonstrate theflexibility and robustness of our algorithm but also show its wide applicability.
Introduction
We develop an effective sphere-packing algorithm for gamma-knife treat-ment planning using a heuristic approach,optimized by simulated annealing.
In our model,we take into consideration the following basic requirements: 1.At least90%shot coverage of the target volume is guaranteed.This re-
quirement is the main standard for evaluating our algorithm,or an efficiency requirement.
2.Minimize the non-target volume that is covered by a shot or by a series of
delivered shots.This requirement is a conformity requirement.
The UMAP Journal24(3)(2003)339–350.c Copyright2003by COMAP,Inc.All rights reserved. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice.Abstracting with credit is permitted,but copyrights for components of this work owned by others than COMAP must be honored.To copy otherwise, to republish,to post on servers,or to redistribute to lists requires prior permission from COMAP.
3.Minimize the overlapped region of the delivered shots in order to avoid the
hot spots as well as to economize shot usage.This is a afitness requirement.
4.Limit the dosage delivered to certain critical structures close to the target.
Such requirements are avoidance requirements.
The traditional model for radiosurgery treatment planning via nonlinear programming assumes that the weights of the shots conform to a certain dis-tribution,from which the construction of the objective function is possible.To avoid the complicated computation of nonlinear programming,we devise a more feasible and rapid heuristic algorithm without reducing any precision of the outcome.
•We consider an optimal sphere-packing plan for a given number of spheres in each size,satisfying requirements1–3.That is,in this step,we assume that the lesion part is far from any critical organ and try tofind an optimal position for afixed set of the spheres using the heuristic sphere-packing algorithm.
•We try all possible combinations of up to15spheres;for each,we use the above algorithm to get an optimal plan.We develop a criterion to select from the different combinations the best packing solution for our model,which is optimized by simulated annealing.
•We consider the real situation infield practice,in which the effect of a critical organ is added.Accordingly,we modify the judgment criterion so that requirement4is satisfied.
网站建设流程图•Finally,to apply the above method to more general situations,we add the weights of the shots.
Though we admit that the inherent limitations of this model due to the simplification of the problem and the restriction of the hardware capacity are unavoidable,we believe that our model has successfully solved the given prob-lem.Our algorithm is not only fast in generating solutions but alsoflexible in allowing parameter settings to solve more difficult tasks.
Assumptions
•Shots can be represented as spheres with four different diameters:4,8,14, and18mm.
•The target volume is of moderate size with a mean spherical diameter of35 mm(and usually less)[The d.]
•The maximum number of shots allowed is15.
•The target object is represented as a three-dimensional digital map with 100×100×100=1million pixels.
•The volume of a object is measured by the total number of pixels in it.•The dose delivered is above the lower bound of the effective level to kill the tumor.
Table1.Description of the variables.
N total number of shots
n i number of shots of type i
s the s th shot used,s=1,...,N
(x s,y s,z s)position of the s th shot center
Position matrix storing all the positions of the shot centers
echarts地图城市代码M average shot width
Radius vector storing the four types of radius:[9742]
Bitmap M×M×M boolean matrix storing information
information from the CT/MRI image
Dose dose delivered,a linear function of exposure time
satisfyingθ≤Dose(i,j,k)≤1,whereθis the
lower bound of the isodose contour
Covered total number of covered pixels in the target volume;
directly reflects the efficiency requirement
Miscovered total number of covered pixels in the normal tissue;
directly reflects the conformity requirement
Overlap total number of overlapped pixels among different shots;
directly reflects thefitness requirement
Ratio percentage of the target volume covered
SphereInof vector representing the number of each type of shot
SphereRadius vector representing the radius of N shots Background Knowledgecmake 安装
Gamma knife radiosurgery allows for the destruction of a brain lesions without cutting the skin.By focusing many small beams of radiation on ab-normal brain tissue,the abnormality can be destroyed while preserving the normal surrounding structures.Before the surgery,the neurosurgeon uses the digitally transformed images from the CT/MRI to outline the tumor or lesion as well as the critical structures of the surrounding brain.Then a treatment plan is devised to target the tumor.
The determination of the treatment plan varies substantially in difficulty. When the tumor is large,has an irregular shape,or is close to a sensitive struc-ture,many shots of different sizes could be needed to achieve appropriate cov-erage of the tumor.The treatment planning process can be very tedious and time-consuming due to the variety of conflicting objectives,and the quality of the plan produced depends heavily on the experience of the user.Therefore,a unified and automated treatment process is desired.
In our model,we reduce the treatment planning problem to an optimal sphere-packing problem by focusing onfinding the appropriate number of spheres of different sizes and their positions to achieve the efficiency,confor-mity,fitness,and avoidance requirements.
Construction and Development of the Model Fixed Set of Spheres
The main idea is to let a randomly chosen sphere move gradually to an optimal position.
In the beginning,N spheres are randomly positioned inside the target vol-ume.Then one sphere is moved to a new position and we estimate whether the new location is better;if so,the sphere is moved,otherwise it remains in place. We repeat this process until a relatively good packing solution is achieved.
To implement our algorithm,we need a criterion to judge a packing solution. According to our four requirements,it is reasonable to take the weighted linear combination of the volume of those covered,miscovered,and overlapped parts as our criterion—that is,a good packing solution means less miscovered,less overlapped,and more covered volumes.
img文件解包工具
Let sphere A move to location B Figure1.We restrict our consideration to just the pixels in the shaded
area,which is very thin and thus has few pixels in it.The program judges which region a pixel belongs to:covered,miscovered or overlapped,and we count the pixels of each kind.We implement this idea using a function PenaltyJudge that returns a signed integer indicating whether the change of the packing strategy results in a better solution.
Figure1.Sphere A moves to location B.Figure2.The centers of the18mm spheres are set at O, the the centers of the three smaller spheres at random points in regions1,2,and3,respectively.
How do we set the initial position of the spheres?Our results will be affected significantly if the starting positions are not properly set.Cramming the spheres together will not do any harm,because according to our algorithm, all of the spheres move in different directions andfinally scatter through the
target volume.But there is one constraint that the initial positions must obey: Larger spheres cannot cover smaller ones.Otherwise,the smaller spheres will never move out of the larger ones,which means they are useless and wasted. Since spheres of the same size will not be covered by each other as long as their centers differ,we need to avoid only coverings between spheres of different sizes.Our technique is to set the spheres of different size in different regions of the target volume,which ensures that the spheres never cover each other.
In Figure2,point O represents the center of the CT image of the target volume.We set the centers of all the18-mm spheres at point O and center the 14-mm,8-mm,and4-mm spheres randomly at the tumor pixels lying in the shadowed regions1,2,3,respectively.Thus,a relatively good starting status is generated.
We perturb the location of one sphere by a ,one pixel)in the North, South,East,West,Up,and Down directions.If a perturbation in one of these directions generate a better packing,we move the sphere one step in that di-rection.Then we choose another sphere and repeat the process.Applying this process to all of the spheres successively is one iteration.Our program generally generates a relatively good packing in about10–15iterations. Results and Data Analysis
Heuristic Method
position of the day
To test the effectiveness of our algorithm,we construct a3D target object with100×100×100pixels through the combination of two spheres and a segment of a circle.For the effect of live simulation,we blur and distort the edge of the object through photoprocessing software so that it is very similar to the shape of a real tumor.The simulated results and the solution given by our program are excitingly good,as shown in Table2.
链表c语言的写法
Table1.
Final distribution of shots from the heuristic algorithm on a simulated target.
Iterations%covered%miscovered%overlapped Time consumed(s) 0373914—
57525820
109611540
159611562
209611583
Visualization of the Results
Plotting the resulting bitmap,we can see clearly from Figures3–4the evo-lution of the locations of the spheres as well as the stability and robustness of our program.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。