A Faster, Better Way To Compute Medical Models From Noisy Images

March 30, 1998

BERKELEY, CA -- Physicians and surgeons are constantly confronted with questions about the invisible. How big is a brain tumor? Is it shrinking with treatment? How thin is a heart-chamber wall, and how much blood does the heart pump? What is the exact shape and volume of a liver?

A fast new way to compute three-dimensional models of internal organs and other anatomical features has been developed by Ravi Malladi and James Sethian of the Department of Energy's Lawrence Berkeley National Laboratory. Both are in the Mathematics Department of Berkeley Lab's Computing Sciences Directorate; Sethian is also a professor of mathematics at the University of California, Berkeley.

"We want to make the task of visualizing and reconstructing medical shapes easy for doctors," says Malladi, who notes that noninvasive imaging has made great advances in recent decades. Whether from x rays or ultrasound or magnetic-resonance imaging or computed tomography, however, even the best images have problems. They are flat -- at best a series of map-like slices through the anatomical region of interest -- and they are usually noisy, like a TV picture plagued with snow.

"One of the first things we set out to do was make cleaner images without destroying essential information," says Malladi. "Of course trained physicians and medical technicians can find the boundaries even in noisy images, and indeed hospitals hire interns to sit in front of computers and painstakingly click out the edges on series of images. The challenge is to create a program that can make these decisions in automatic fashion."

Malladi and Sethian have used their methods to make images of organs with shapes as intricate as those of the human brain; from sonograms they have modeled the fetus in the womb; they have made movies of a pumping heart, relating blood flow in and out of the chambers to the thickness of the heart walls.

"Now all a physician has to do is click once or twice inside the region of interest and the program will build a model in a few seconds," Malladi says. The new methods make medical images useful to doctors in real time, aiding fast, well informed decisions for effective treatment.

The way Malladi and Sethian build cleaner images is closely related to the way they build three-dimensional models from a series of flat images. An "implicit representation of curves" is the underlying mathematical approach, a form of partial-differential equations pioneered by Sethian which tracks boundaries as they evolve in space and time. "Level Sets" and "Fast Marching" are two methods important in recovering medical shapes. (See background information, below.)

Level Sets is a method of modeling curves and solids by incorporating an extra dimension -- viewing the representation from above, as it were. Fast Marching is a method of approximating the position of curves and surfaces moving under a simple "speed law," which attracts the evolving curve to a boundary and closely relates it to the regularity of the emerging shape. With these methods a computer algorithm can determine the internal and external boundaries of anatomical solids more quickly and less ambiguously than traditional ways of interpreting visual information.

The process begins when the physician uses the computer to plant a visual seed in the image to be modeled. "Even a single point, represented by a computer mouse click, can be thought of as a very small circle or sphere," Malladi says. From that point an increasingly complex shape starts to grow. Knowing when to stop, however, depends on the algorithm recognizing edges that are often hard to read.

The trick lies in mathematically adjusting the speed of the growing curve. As the curve advances, it encounters changes in the gray-scale values of the pixels in the image. Where changes are small from one pixel to the next, the curve moves quickly -- the algorithm assumes there is no nearby boundary -- but where changes are large, the curve senses a boundary and slows down. Too-abrupt changes in curvature are also smoothed by the calculation.

Since the mathematical view is always from one dimension "above" the shape being modeled, a complex 3-D model can be quickly constructed, with the propagating boundary curve easily working its way around holes and voids. What's inside and outside a complex solid can be modeled separately. Models constructed at different moments in time produce movies of 3-D shapes in action.

Malladi's and Sethian's recent results were published in Proceedings of the Sixth International Conference on Computer Vision, Mumbai (Bombay), India, January, 1998. Movies of anatomical model construction can be found on the web at http://www.lbl.gov/~malladi.

The Berkeley Lab (http://www.lbl.gov) is a U.S. Department of Energy national laboratory located in Berkeley, California. It conducts unclassified scientific research and is managed by the University of California.

Background: Implicit Representations of Curves

Level Sets and Fast Marching, combined with other mathematical techniques, have yielded quick, efficient, and manageable programs for anatomical images.

Imagine tracking the changing boundary of two rings of fire burning outward in dry grass. One way to follow the changing boundary between the burned area and the unburned area is to track points on each expanding circle. But as soon as the circles overlap, all the points formerly on boundaries but now in the burned area must be abruptly discarded, which makes the calculation messy.

Now instead of two circles on a plane, picture two upright cones, partly overlapping: the original two rings of fire lie on the boundary where a level plane slices through the surfaces of both cones near their tips. Move the plane up, and the circles grow together. The boundary follows automatically, with no points to be tracked or arbitrarily discarded -- only a level to be determined, which describes the evolving curve.

It's easy to imagine adding a third dimension to a two-dimensional curve; it's hard to picture a fourth spatial dimension associated with a volume. Yet mathematically it is no more difficult to use this Level Sets approach with solids.

What drives a curve's evolution, whether in two dimensions or three, is a "speed law." Typically a speed law might move a point on a boundary faster in regions of tight curvature and slower in less curved regions. This would have the effect of smoothing out transitions where the curve changes direction abruptly, an effect known as "viscosity" because it resembles the slow, smooth transitions of a thick liquid like honey.

Fast Marching equations come into play in making choices to compute the evolving curve most efficiently. Curvature can be negative (inward) or positive (outward). Any closed curve, no matter how complex, whose points move perpendicularly inward in the positive regions and outward in the negative regions, at curvature-dependent speed, will inevitably form a circle -- which in turn will shrink to a point.

To build smooth maps and 3-D images of internal organs, however, the curve or surface has to move in the opposite direction, starting from small geometric shapes or solids and evolving outward to complex ones. Therefore a speed law is written containing two terms, one that attracts the curve or surface to the boundary of the target object and another that closely relates the curve or surface to the regularity of the evolving shape -- for example by adding a little "viscosity" from changes in curvature. In this way a complex shape can be quickly and accurately bounded and filled in.

The principles of Level Sets and the method's many applications are discussed in "Tracking interfaces with level sets," by James Sethian, American Scientist, May-June 1997, p. 254. A discussion with movies can be found on the web at http://math.berkeley.edu/~sethian/level_set.html.

DOE/Lawrence Berkeley National Laboratory

Related Computer Articles from Brightsurf:

UCLA computer scientists set benchmarks to optimize quantum computer performance
Two UCLA computer scientists have shown that existing compilers, which tell quantum computers how to use their circuits to execute quantum programs, inhibit the computers' ability to achieve optimal performance.

Digitize your dog into a computer game
Researchers from CAMERA at the University of Bath have developed motion capture technology that enables you to digitise your dog without a motion capture suit and using only one camera.

Stabilizing brain-computer interfaces
Researchers from Carnegie Mellon University (CMU) and the University of Pittsburgh (Pitt) have published research in Nature Biomedical Engineering that will drastically improve brain-computer interfaces and their ability to remain stabilized during use, greatly reducing or potentially eliminating the need to recalibrate these devices during or between experiments.

Computer-generated genomes
Professor Beat Christen, ETH Zurich to speak in the AAAS 2020 session, 'Synthetic Biology: Digital Design of Living Systems.' Christen will describe how computational algorithms paired with chemical DNA synthesis enable digital manufacturing of biological systems up to the size of entire microbial genomes.

Computer-based weather forecast: New algorithm outperforms mainframe computer systems
The exponential growth in computer processing power seen over the past 60 years may soon come to a halt.

A computer that understands how you feel
Neuroscientists have developed a brain-inspired computer system that can look at an image and determine what emotion it evokes in people.

Computer program looks five minutes into the future
Scientists from the University of Bonn have developed software that can look minutes into the future: The program learns the typical sequence of actions, such as cooking, from video sequences.

Computer redesigns enzyme
University of Groningen biotechnologists used a computational method to redesign aspartase and convert it to a catalyst for asymmetric hydroamination reactions.

Mining for gold with a computer
Engineers from Texas A&M University and Virginia Tech report important new insights into nanoporous gold -- a material with growing applications in several areas, including energy storage and biomedical devices -- all without stepping into a lab.

Teaching quantum physics to a computer
An international collaboration led by ETH physicists has used machine learning to teach a computer how to predict the outcomes of quantum experiments.

Read More: Computer News and Computer Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.