《making 3d binary digital images well composed》由会员分享，可在线阅读，更多相关《making 3d binary digital images well composed（1页珍藏版）》请在金锄头文库上搜索。
1、5SPIEs International Technical Group Newsletter ELECTRONIC IMAGING 15.2JUNE 2005 Making 3D binary digital images well composed Marcelo Siqueira, Jean Gallier, Department of Computer and Information Science, University of Pennsylvania; Longin Jan Latecki, Department of Computer and Information Scienc
2、es, Temple University A three-dimensional binary digital image is said to be well composed if, and only if, the set of points in the voxel faces consisting of every voxel face that is shared by a foreground and a background voxel of the image is a 2D manifold.1 A well-composed image enjoys very usef
3、ul topological and geometric properties. These prop- erties make simpler several basic al- gorithms in computer vision, com- puter graphics, and image processing. For instance, thinning algorithms do not suffer from the irreducible thick- ness problem if the image is well composed.2 Also, algorithms
4、 that rely on curvature computation to extract approximating iso-surfaces directly from binary images can be applied to well-com- posed images with no need to handle special cases resulting from non-manifold topol- ogy.3,4 On the other hand, if a 3D digital binary image is the result of the digitiza
5、tion of a solid object, such as a bone, and it lacks the prop- erty of being well composed. In this case, the digitization process that gave rise to it is not topology-preserving. As the results in Refer- ence 5 show, if the resolution of the digitiza- tion process is fine enough to ensure preserva-
6、 tion of topology, then the resulting image is well composed. This fact has motivated us to develop an iterative and randomized algorithm for repairing non well-composed 3D digital binary images. Our algorithm restores the given image by converting background voxels into foreground ones. Although th
7、is algorithm always produces a well-composed image, it cannot guarantee that the result is the same as would be obtained from a topology-preserving digitization pro- cess. This is because our algorithm does not assume any knowledge about the original digi- tization process. Even so, if the number of
8、 back- ground voxels converted into foreground ones is not too large, the input and output images will be similar, which is satisfactory for sev- eral applications that benefit from using well- composed images. The conversion process relies on the fact that well composedness is a local property: tha
9、t is, the condition of being well composed is equivalent to the nonexistence of two types of local critical configurations of image voxels1 (see Figure 1). The first of these is where four voxels share an edge, two of them are back- ground voxels, two of them are foreground voxels, and the backgroun
10、d (or foreground) voxels share an edge but not a face. The sec- ond is where eight voxels share a vertex, two of them are background (or foreground), six of them are foreground (or background) voxels, and the two background (or foreground) voxels share a vertex but not an edge. It can be shown that
11、a 3D binary digital image is well composed if, and only if, it does not contain any instances of these critical configurations. Note that we can decide if a given 3D bi- nary digital image is well composed by simply verifying if any 221 neighborhood of voxels of the image is an instance of the first
12、 critical configuration, and if any 222 neighborhood of voxels of the image is an instance of the sec- ond. This test can be performed in linear time with the number of voxels of the image. The first step of our algorithm is to verify if the in- put 3D binary digital image is well composed. If so, t
13、he algorithm finds a subset P of back- ground voxels such that, if they were converted into foreground voxels, then the resulting im- age would be well composed. Then this con- version is performed. Ideally, P should be as small as possible, so that the input and output images are similar. Although
14、such a smallest set can be found us- ing an exponential-time search, this is com- pletely unfeasible in the context of practical applications. Our repairing algorithm is not guaranteed to find the smallest set P, but its time complexity is linear in the number of voxels of the input image. Our algor
15、ithm builds P iteratively, starting with an empty set. Each iteration inserts a background voxel into P. Each such voxel is randomly chosen from those in the background in the critical configurations of the input image, and when such a voxel is converted into a foreground one, at least one instance
16、of a critical configu- ration is eliminated. This conversion can also give rise to a new critical con- figuration, which is further eliminated by choosing another background point. However, this process is guar- anteed to converge to a correct solu- tion after a finite number of iterations. We tested our algorithm against several magnetic resonance (MR) im- ages of parts of the human body, such as the brain, torso, and lungs. In all cases, our algorithm generated a well- composed imag
