Sometimes SRS (Stereotactic Radio Surgery) requires using sphere packing on a Region of Interest (ROI) such as cancer to determine a treatment plan.   We have developed a sphere packing algorithm which packs non-intersecting spheres inside the ROI.   The region of interest in our case are those voxels which are identified as cancer tissues.   In this paper, we analyze the rotational invariant properties of  our sphere-packing algorithm which is based on distance transformations. Epsilon-Rotation invariant means the ability to arbitrary rotate the 3D ROI while keeping the volume properties remaining (almost) same within some limit of epsilon. The applied rotations produce spherical packing which remains highly correlated as we analyze the geometrically properties of sphere packing before and after the rotation of the volume data for the ROI. Our novel sphere packing algorithm has high degree of rotation invariance within the range of +/- epsilon. Our method used a shape descriptor derived from the values of the disjoint set of spheres form the distance-based sphere packing algorithm to extract the invariant descriptor from the ROI. We demonstrated by implementing these ideas using Slicer3D platform available for our research.   The data is based on sing MRI Stereotactic images. We presented several performance results on different benchmarks data of over 30 patients in Slicer3D platform. In several applications such as inspection of tumor or interacting with portion of a 3D volume data, the ROI could be rotated at arbitrary angles. If a sphere packing algorithm is used before and after such rotation, then rotational invariance suggests that there might be high correlation between spheres found by our sphere packing algorithm before and after the rotation. Defining correspondences between the original and rotated ROIs is an important task that could be solved by spheres' descriptors. If these descriptors are highly correlated, then we can anticipate that the ROIs might be similar as well. Li et al. (Li & Simske, 2002) stated that translation and scaling are easy compared to rotation. Rotation of a 3D volume data or 3D image involves simultaneous manipulation of three coordinates to maintain invariance. In the case of sphere packing, as we capture the ROI with nonintersecting spheres, the rotation invariance means that set of spheres will remain identical in size although their placement is expected to change under an arbitrary rotation. There are three major techniques to prove the rotation invariance: landmarking, rotation invariant features/shape extraction descriptor, and brute force rotation alignment. The landmarking is normally carried out by following two methods, domain specific landmarking and generic landmarking (Szeptycki, Ardabilian, & Chen, 2009 ). The domain specific landmarking accepts some fixed point in the image and does rotation with respect to that about an arbitrary axis. The generic landmarking method on the other hand, finds the major axes of the 3D/2D image and that can rotate the volume or image as a whole in carrying out the rotation. Because the size of the volume data can be typically large based on the size of the data, both these approaches require that large memory storage is available as the complete voxel information is required, and usually is time consuming. The brute force alignment method divides/degrades the object into large number of smaller parts and works with them for rotation. This method is time consuming, complex and complicated because parts have to be organized. The developed code for a particular shape in this method may only apply to the data in hand and may not be generalizable. Finally, Invariant feature/shape descriptor involves identification of certain invariant features (measurable quantities) that remains unaltered under rotations of the 3D image or volume data. The invariant features are indexed with a feature vector also known as shape signatures. Then, the optimal rotation can be defined by measuring model's similarities in terms of the distance such that the rotation invariant property would mean that these distance measures are as close to each other with certain limit before and after the rotation. There are literally many of rotation invariant features that been used in the past, including ratio of perimeter to area, fractal measures, circularity, min/max/mean curvature, and shape histograms, etc. Lin et al. (Lin, Khade, & Li, 2012) and Yankov et al. (Yankov, Keogh, Wei, Xi, & Hodges, 2008) use time series representation as a feature vector to match the 3D shapes to prove the rotation invariance. Based on our research, most of the studies have been used spherical harmonic method to map the features of objects into a unit sphere to prove the invariance under rotation (Kazhdan, Funkhouser, & Rusinkiewicz, 2003; Nina-Paravecino & Manian, 2010; Vranic, 2003) . The spherical harmonic method does not always give accurate results to distinguish between models since the internal parts of the 3D shapes may not fit in same sphere. Other researchers combined the spherical harmonic with spatial geometric moments (El Mallahi, Zouhri, El-Mekkaoui, & Qjidaa, 2017; Kakarala & Mao, 2010) . The most common graph method used is skeletons. The skeletons are based on medial axis. The medial axis of the 3D objects has been used as a shape descriptor in a number of researches Iyer, Jayanti, Lou, Kalyanaraman, & Ramani, 2004; Liu, 2009; Lou et al., 2003; S'anchezCruz & Bribiesca, 2003; Sundar, Silver, Gagvani, & Dickinson, 2003) . However, this method is sensitive to noise and has a heavy computationally cost. In this paper, we considered the set of spheres as shape-descriptors and analyzed the sphere packing before and after the rotations and looked for the similarity measure. We aimed to show that set of spheres are invariant such that even if we rotate the image, the size of the spheres and center's distances are highly correlated. We used our sphere packing algorithm to pack non-intersecting spheres into the ROIs before and after rotations. As mentioned earlier, those spheres could provide invariant shape descriptor. After rotation the voxels will be populated with the new voxel orientation. Our shape descriptor provides a novel featureless method that doesn't depend on any specific feature or texture, instead is related to sphere packing generated by our sphere packing algorithm. Our method characterizes the 3D object similarity by the shape geometries of the sphere packing, and sphere's correspondence with one another and their spatial relationships. In this paper, we show that our previous work for sphere packing (Anonymous, 2019) can be used to show the invariance under rotation since our algorithm can describe volumetric shapes more succinctly than voxel representation. In this work, the spheres packing together with the radiuses and centers functions provided an shape descriptor, a novel approach for characterization and compression of shape information for 3D volume and voxel data. The spheres radius works the best for our study for finding the similarity after rotation. Even though there are differences between the total number of calculated distances before and after rotation, our algorithm accuracy is reasonably high because it is able to calculate almost similar radiuses each time within epsilon. The consistency of spheres radius is because our algorithm at each iteration finds the maximum radius distance to pick first, so increasing the number of packed spheres to cover the required voxels based on the desired packing density doesn't affect the epsilon value. Changing the topology due to equal spheres is the main reason of the increase of the epsilon value of the distance ratios. The algorithm decision of choosing which sphere of the same size to place first, is the big issue here. Therefore, increasing the number of packed spheres will significantly increase the changes in topology which will results in increasing the epsilon value. When the radiuses are equal, the descriptor graph before and after might change considerably based on which sphere our algorithm suggests. In this case, aggregate we will need to collect all those spheres which are equal and replace them by the average of the center of the sphere in the shape descriptor, and so then (e) value will be similar in the shape description before and after the rotation. Thus, set of spheres whose radius are equal are replaced with one sphere. That is expected to reduce the epsilon (e) value further. Moreover, the topology changing in our study affect our accuracy results. We believe that eliminating equal spheres by using the enclosing sphere in our implementation will decrease the distance ratio results comparing the shape descriptors before and after the rotation of the ROI. Our novel medical visualization techniques promise to improve the efficiency, diagnostic quality and the treatment. The field of 3D shape approximation and similarity have been a focus in the area of geometry in general for several hundred years now. Shape analysis for feature extraction is the key problem in the shape approximation and similarity issues. The best way for similarity matching is to identify certain shape signatures (prominent features in the image). These signatures are then compared between the transformed images through similarity assessment, distance computation or any other appropriate methods. This paper presented a method for defining a possible invariant shape descriptor from 3D-image or 3D-volume data to be used to match the objects from different rotations/viewpoints. Our method can be applied to a wide variety of data types such as 2D images and even polygonal meshes. Our heuristics is e-invariant and has an impressive result of 96% invariant under rotations. The experimental results prove the effectiveness of our novel idea. The proposed system was fully software implemented in Slicer3D and has been tested on 30 patient's databases. For future works, we will apply other measures such as 3D-spatial sorting based on the spheres found, or identifying a minimal volume enclosing sphere surrounding all spheres of equal radius (as mentioned earlier) to improve epsilon (e) value further. Moreover, as Slicer3D is experimental, not FDA approved, yet used worldwide, our plan is to upload our implementations under BSD license so that worldwide communities can try the system and provide more feedback using their 3D volume data and reporting e-value for their data.
Packing region of Interest (ROI) such as cancerous regions identified in 3D Volume Data, Packing spheres inside the ROI, rotating the ROI , measures of difference in sphere packing before and after the rotation.
{"src": "scitldr-AIC_train", "paper_id": "EaXNbizsb"}