Programs & Scripts

Programs & Scripts

A number of different programs were written to perform the experiments. The VisionX toolkit was heavily leveraged as it contains many useful image processing and computer vision applications which would otherwise take additional time to code. The entire code repository is located on Github here. Below are descriptions of the important programs in the repository. Specific documentation can be found in the man pages.

nninterp.c / nninterp-ct.c

These programs perform zero-order hold (nearest neighbor) interpolation on byte and short images, respectively. The byte images are the synthetic test images and the short images are the CT scans. The image is mapped from the input to the interpolated output space by using the ratio of the new voxel dimensions to the old voxel dimensions. The algorithm generates an empty output image of the appropriate size, each voxel in the output is then mapped back to the input space and the single nearest neighbor is found using the round() function in each dimension. The program is compiled using vcc with the standard optimization flag.

linterp.c / linterp-ct.c

These programs perform linear interpolation on the input images. As with nninterp, the first operates on byte images while the latter is intended for short CT images. Also similarly to nninterp, the nearest two neighbors are found using ceil() and floor() in each of the three dimensions. This yields the eight points constituting the cube around the interpolated point. As a result of these extra points, however, the edge voxels of the output are not calculated to avoid errors stemming from accessing voxels outside the bounding box. The interpolated value is calculated by performing one-dimensional linear interpolation in each of the z-, y-, and x-dimensions. There are thus a total of seven linear interpolations to flatten the cube to a single point.

tcinterp.c / tcinterp-ct.c / lekien-tcinterp.c

These programs perform tricubic interpolation on the input images. This requires more points than the trilinear algorithm, up to a total of 64. To obtain these points the program unmaps the pixel from the output space to the input space, applies ceil() and floor(), and then additionally obtains the value of the voxels one unit above the ceiling and one voxel below the floor. These voxels are labeled 0, 1, 2, and 3, in each dimension.

Two approaches are used to calculate the tricubic interpolation. The CINT() function performs a stepwise approximation of the first and second derivatives at points 1 and 2, and uses these values along with the point values to calculate the tricubic-interpolated value. In tcinterp and tcinterp-ct, CINT() is used to generate the output. This necessitates 21 calls to the cubic interpolation function, as the 64 points must be reduced to a single one. Because of the additional points, the program does not calculate interpolated values for the outer 3 voxels to avoid bounding box errors.

Lekien-tcinterp uses the algorithm described by Lekien and Marsden, which stacks the values of the nearest eight points and their derivatives into a matrix which is then multiplied by a specified 64x64 matrix to yield the coefficients of the tricubic interpolant. In this way, the algorithm is more efficient because coefficients can be reused provided that the interpolated point falls within the same cube as the previously processed point. This code is functional but incomplete, as it does not fully take advantage of this feature.

Tests on synthetic images show that both tricubic interpolators produce the same results. Future development might see the latter algorithm fully developed to run faster. For this project, however, the relatively small size of the input images means that both algorithms will run suitably quickly.

v3dvol.c / v3dvol_voxel.c

These programs performed the volume calculation of 3D images. Binary images are accepted as input files, and they are iterated through pixel by pixel. Every pixel with a value of 255 is considered part of the object. At the end, the total number of object pictures - qualitatively the volume - is returned. In the more advanced v3dvol voxel, voxel density is also taken into account, as is specified upon invocation of the program as xres, yres, and zres values, specifying the size of the voxel in each dimension. This information is then used to multiply the resulting object volume by xres*yres*zres, thus scaling the object volume by the voxel resolution.

vits_byte.c / vits_short.c

The vits program is what performs adaptive iterative thresholding of an input image. The only argument it expects other than an input file and output location is the number of ”bins” in the image. This is essentially the range of pixel values possible in the image. Specifying a lower number of bins than actually exist in the image will simply cause pixels of greater value to be truncated down to the max value. The two incarnations of vits work on byte and short images respectively.

adaptive_segment_byte / adaptive_segment_short

The adaptive segment script encapsulates all the steps necessary to take an input image in VisionX format, and generate a segmented, morphologically filtered, VisionX 3D output image. It takes as input the input image location, desired kernel size for morphological filtering, number of bins for iterative thresholding, and output location. The name is sort of a misnomer because this script performs not only segmentation, but also filtering. Again, the two versions work on byte and short images respectively.

test_byte_images / test_short_images

These two scripts tie in all the other software components associated with segmentation, filtering, and volume calculation into one command line invocation. This script exists mainly for convenience, and expects as arguments for filter kernel size, number of bins for iterative thresholding, x-y-z voxel resolution for volume calculation, and the folder location containing the images to be run through the system. When run correctly, it will perform all the steps on an image necessary to arrive at a final volume result and isolated nodule.

All the code for this project is hosted on Github and can be forked: