A plague of image artifacts is resolved and a patent rises from the ruins.
I was working at a medical imaging company in Nuclear Medicine product development. The product was a scintillation camera, or gamma camera, used to image gamma radiation-emitting radioisotopes.
The patient was given a radioactive-tagged pharmaceutical that was preferentially absorbed by the area of the body being studied. The gamma rays given off were received by a detector head, which outputted the X-Y position and energy of each photon received. These 3 signals were sampled at 14-bit resolution. However, the data required 3 stages of correction to produce a usable image.
In linearity correction, a correction vector is read from a stored table addressed by the observed X-Y position and added to it to produce the corrected X-Y position. Since storing a complete correction table at 14 bit x 14 bit resolution was impracticable, the correction tables were stored at 7 bit x 7 bit resolution and bi-linear interpolation was used to interpolate from the stored table.
In a flood test with a linearity board using bi-linear interpolation, image artifacts were found, edges at interpolation cell boundaries in what should have been a uniform field after correction. This was brought up at a group meeting and all of us were asked to consider a solution.
I remembered from an image processing class that the human visual system is sensitive to edges, and that edges are characterized as abrupt changes in the first derivative in space of an image. Bi-linear interpolation enforces continuity of the value of a function at cell boundaries, but it produces a discontinuity in the first derivative. I reasoned that such a discontinuity would produce the edge artifacts seen, so what was needed was an improved interpolation method that would enforce continuity at the cell boundaries in both the functional value and the first derivative (but still produce discontinuities in the second derivative).
I consulted a book from the company library to find such an interpolation method. I found a reference to Hermite interpolation, a nonlinear interpolation method between two points at which are tabulated both the functional value, and the slope (first derivative), which does indeed enforce continuity of both at the endpoints. Since we did not have the slope tabulated, I inserted the difference of the two adjacent points divided-by-two for the tabulated slope at the two endpoints, and collected terms to produce a 4-point interpolation formula that I labeled Hermite interpolation with approximate slope.
Just as bi-linear interpolation is a generalization of linear interpolation in 1 dimension to interpolation in 2 dimensions, this too can be generalized to 2 dimensions by doing 4 interpolations in X on parallel rows followed by a single interpolation in Y on the resulting column. But 20 multiply-accumulate operations to calculate the correction, plus more to add in the uncorrected address, would take more time than the minimum arrival time between events. So I made an approximation to save time. Instead I did linear interpolation in X on the outer 2 rows, Hermit interpolation on the inner 2 rows, and a final Hermite interpolation in Y on the results in X, saving 4 operations, so it fit into the allowable time.
I presented this idea and was given the permission to proceed. First I tested it in simulation in 2 stages. For the first simulation I wrote 64-bit fixed-point arithmetic subroutines so that I could calculate the result without any intermediate rounding, though there was a final rounding at the end, to test the algorithm. For input I used a real correction table from the calibration of a real system, and a captured raw image from the same system prior to correction, the same data presented at the group meeting to demonstrate the problem.
The simulation was run, and the corrected image was output onto X-ray film at a much higher resolution than a printer can print on paper. The film was developed and examined, the edge artifacts were gone. This proved both that the interpolation method worked, and that my approximation to save time had not compromised the result enough to cause artifacts. After designing the real data path, I modified the simulation to reflect the real resolution of the MAC, and to include rounding of intermediate results. This second stage simulation was run to verify the proposed data path. Again all artifacts were absent. Then, I completed the schematic design of my linearity correction board.
This was in the mid-1980s so the DSP portion of the data path was built with a MAC, a separate register-file IC to store intermediate values, a preprogrammed EPROM to hold the interpolation coefficients (I wrote a C program to calculate the coefficients and make a S-record file to be used in the EPROM programmer), SRAM for the correction tables, and buffers to connect the different buses. This was duplicated to process the X and Y portions of the correction vector in parallel. The finite state machine that controlled the DSP was in a PAL. The board was built and successfully replaced the earlier linearity correction board that used bilinear interpolation.
In the end, two versions of the board were designed, one as part of a retrofit package to upgrade existing cameras, and the other as part of a design for a new camera. A patent was later granted for this work, United States Patent # 4,808,826 "Smooth dot density spatial distortion correction in photon imaging devices." I shared the patent with others working on the design of the retrofit package, including hardware engineers and software engineers.
Tim R. Johnson is an electrical engineer with 29+ years experience in the design of digital hardware and supporting software for different industries: medical instrumentation, industrial controls, data acquisition and computer systems. He has an MSEE from CWRU, and a BSEE from MIT. He is currently looking for a new position.
The Frankenstein's Fix has just come to an end. Stay tuned to read the submissions and see what kind of difficult job of judging we have ahead of us! Submission details and full contest rules here.