1	Segmentation Approaches in the Visible Human Tom McTavish Tom.McTavish@UCHSC.edu
2	We Use Painful Segmentation Methods Hand drawing (tracing) Paint, fill, erase... Spline tracing Easier and faster than hand drawing, but still a rather painful process.
3	Why? Isn’t it obvious?
4	Why? Isn’t it obvious?
5	The Visible Human Dataset The VH dataset is high-resolution and in color. This makes it easier for anatomists to distinguish structures and define borders. The computer can capitalize on this, too, but segmentation is still a very difficult problem because the computer doesn’t know anatomy, the classification of tissues is difficult, and borders aren’t always well defined.
6	Muscle Muscles have a grain, but when we try to differentiate one muscle from an adjacent one, we can’t, especially if we say the muscles include the intermuscular fat.
7	Is it fat?
8	Bone Marrow has a noise pattern of gray and red
9	The Brain ?!?!
10	It’s sometimes obvious It’s comparatively easy for humans to recognize many structures, even when they’re not familiar with the object. You don’t have to be an anatomist to recognize many structures and see where their borders are, and…
11	It’s easy if you’re sloppy Even when it might appear that the structure is obvious, hand segmentation varies from slice to slice, day to day, and person to person. The core of the object being segmented will be consistent, but the border is very variable. If you don’t need precision, then it’s relatively easy to get close, even for the computer.
12	Segmentation Approach Anatomist is in control, not the computer. The segmentation application should help guide and implement the anatomist’s decision. Easy and intuitive paint tools and simple navigation interface help hand segmentation some. “Smart” tools can help even more.
13	“Smart” tools - Spline Splines make tracing faster and smoother and aren’t really “smart” on their own, but… our tool adds edge detection blending from the normal-plotted spline and we perform a minimum differences of the neighbors of control points to adjust them between slices.
14	“Smart” tools - Interpolator Many structures don’t change much from slice to slice, or they change in a consistent way (rotation, scale, translation). For these structures, we can apply a “Shape” morph between the start slice and the end slice n slices later.
15	Interpolator Algorithm Capture the outline of the segmented structure in the start and end slice. Interpolate (expand) the smaller one to match the same number of samples as the first. Establish a correspondence point Because the structures form loops and are now the same size, we can rotate one about the other, comparing minimum differences of their neighbors. Once we have a correspondence, we have a mapping from x₁y₁to x₂y₂ that we migrate over n slices.
16	Establishing Correspondence
17	Establishing Correspondence
18	Establishing Correspondence
19	Establishing Correspondence
20	Establishing Correspondence
21	Establishing Correspondence
22	“Smart” tools – Binary Segmentation “Binary Segmentation” describes the segmentation problem as “What are we classifying” and “What aren’t we classifying”. The idea is to separate the pixels into two sets – those that make up the structure of interest and those that don’t. By having different descriptors of the two sets, we should be able to develop an algorithm that can judge to which set a given pixel should belong.
23	Min-Cut/ Max Flow We can set up the binary segmentation problem as a minimum cut/ maximum flow problem on a graph. The pixels (voxels) define the nodes two types of edges run through the network Region weights that connect to what we want and what we don’t want (the source and sink terminals). Edges between neighbors.
24	Min-Cut/ Max Flow
25	Some problems with Max-Flow algorithms Min-Cut/ Max-Flow algorithms run in O(V³) time. On a 800x800x200 volume, that’s 2x10²⁴ instructions! There are ways to make the algorithm so that it doesn’t run in this worst case, but still, it can take even hours to come up with a segmentation. If it’s not perfect that first time (which it won’t be), updates can be performed faster by keeping track of a residual graph, but it is not a very interactive approach. Still, if it can provide a good segmentation in the same time or better than it would take somebody to do by hand, it should be explored.
26	Region Classifiers What can speed up binary segmentation more than anything is a fairly accurate region classifier that makes strong connections to either the source or the sink. It’s the gray area that slows down the algorithm. Instead or in addition to region classifiers being used in Binary Segmentation, they can also be applied in a “Magic Wand” type of flood fill.
27	Magic Wand The idea with a “Magic Wand” tool is that it performs a fill starting at the point clicked, growing as long as it finds something similar to what was originally clicked. In Photoshop and most paint programs, this just takes the color value of the pixel that was clicked and as long as the color of adjacent pixels is close enough to this value, it continues on with the fill. If it doesn’t cross the threshold (the color is too different from the one that was clicked) the fill stops at that pixel.
28	Magic Wand vs. Binary Segmentation If the classification of the structure of interest is good enough, we don’t need to specify what is not the structure. The flood fill of the Magic Wand can be a lot faster. The Binary Segmentation Tool accounts for edges. When the region weights can’t make a determination, the edge detection kicks into gear, but Binary Segmentation tends to still cut edges short.
29	Magic Wand vs. Binary Segmentation If the classification of the structure of interest is good enough, we don’t need to specify what is not the structure. The flood fill of the Magic Wand can be a lot faster. The Binary Segmentation Tool accounts for edges. When the region weights can’t make a determination, the edge detection kicks into gear, but Binary Segmentation tends to still cut edges short.
30	Magic Wand Use The Magic Wand and Binary Segmentation tool have the danger of not including enough, or selecting too many pixels (or voxels if segmenting in 3D). The edge is always going to be difficult. Because the Magic Wand’s fill is fast and requires only one click, we can set it to have a low threshold (requires high-confidence of matching). To segment, then, we just click until the structure is completely filled. Even twenty clicks is easier than tracing a structure!
31	Region Classification Because we have color data, our region classifiers are (for the moment) based on color, employing various forms of histogram weighting and most recently, color space distance matching.
32	Color Space In the RGB color space, we can think of a pixel residing in a 3D space. When we take a sample of a texture, we can picture each of those pixels of the sample sitting in their R, G, and B, locations. With a large number of samples, sampling at any location in the texture should result in about the same signature.
33	Color Space
34	Color Space Distance Matching The idea here is to see if the pixel under consideration is close to one of the clumps that defined the signature of the texture. We determine if it’s close to a clump by taking the distance of this pixel to every other pixel from the samples, and then averaging the distance of the closest n samples. For simply using color, this delivers great results.
35	More Classifiers? Texture does exist in human tissues, even if they’re not the easiest to classify, so yes, we can certainly use more than our color distance matching. Even with the color distance matching we can maybe get more clever in saying not only does the pixel match (because pixels that we don’t want can still match colors from the samples), but maybe the pixel needs to be attached to at least n others for it to really be considered part of a texture. Fourier Transform for texture classifiers? Other ideas?
36	The Edge The edge detection is hard. Sure we can use Laplacian of Gaussians, Canny, Sobel, whatever, but it takes experimenting with parameters to get the edge desired. Most edge detection methods highlight the pixel that is on the edge and not which side it really is!
37	Avoiding the Edge For a given voxel to ask if there’s a path to n number of other voxels that are all part of the region is a test that helps ensure the voxel belongs to the region and gets around edge detection. This involves path-finding algorithms. When the pixel doesn’t think it belongs much at all to a region, it can feel around to make sure.
38	Paths to Determine Belonging If we ask if a voxel’s surroundings are part of the region we’re looking for, we might get the wrong answer.
39	Segmentation is a Holy Grail Object and pattern recognition, computer vision, graphics, and image processing have come a long way, but there’s so much ahead!