`Valeo v. Magna
`IPR2015-____
`
`VALEO EX. 1026_001
`
`
`
`326
`
`'
`
`Lisa G. Brown
`
`CONTENTS
`
`>—I . INTRODUCTION
`I0
`IMAGE REGISTRATION IN THEORY
`2.1 Definition
`2.2 Transformation
`2 3 Image Variations
`2 4 Rectification
`3. REGISTRATION METHODS
`3 1 Correlation and Sequential Methods
`3 2 Fourier Methods
`3 3 Point Mapping
`3.4 Elastic Model-Based Matching
`3 5 Summary
`4 CHARACTERISTICS OF REGISTRATION
`METHODS
`4 1 Feature Space
`4.2 Similarity Measure
`4.3 Search Space and Strategy
`4.4 Summary
` .m
`
`1.
`
`INTRODUCTION
`
`A frequent problem arises when images
`taken, at different
`times, by different
`sensors or from different viewpoints need
`to be compared. The images need to be
`aligned with one another so that differ-
`ences can be detected. A similar problem
`occurs when searching for a prototype or
`template in another image. To find the
`optimal match for the template in the
`image, the proper alignment between the
`image and template must be found. All of
`these problems, and many related varia-
`tions. are solved by methods that per-
`form image registration. A transforma-
`tion must be found so that the points in
`one image can be related to their corre-
`sponding points in the other. The deter-
`mination of the optimal transformation
`for registration depends on the types of
`variations between the images. The ob-
`jective of this paper is to provide a frame-
`work for solving image registration tasks
`and to survey the classical approaches.
`Registration methods can be viewed as
`different combinations of choices for the
`
`following four components:
`
`(1) a feature space,
`(2) a search space,
`(3) a search strategy, and
`(4) a similarity metric.
`
`ACM Computing Surveys, Vol. 24. No. 4, December 1992
`
`The feature space extracts the informa-
`tion in the images that will be used for
`matching. The Search space is the class
`of transformations that
`is capable of
`aligning the images. The search strategy
`decides how to choose the next transfor-
`
`mation from this space, to be tested in
`the search for the optimal transforma-
`tion. The similarity metric determines
`the relative merit for each test. Search
`
`continues according to the search strat-
`egy until a transformation is found whose
`similarity measure is satisfactory. As we
`shall see, the types of variations present
`in the images will determine the selec-
`tion for each of these components.
`For example, consider the problem of
`registering the two x-ray images of chest
`taken of the same patient at different
`times shown in Figure 1. Properly align-
`ing the two images is useful for detect-
`ing, locating, and measuring pathological
`and other physical changes. A standard
`approach to registration for these images
`might be as follows:
`the images might
`first be reduced to binary images by de-
`tecting the edges or regions of highest
`contrast using a standard edge detection
`scheme. This removes extraneous infor-
`mation and reduces the amount of data
`
`to be evaluated. If it is thought that the
`primary difference in acquisition of the
`images was a small translation of the
`scanner, the search space might be a set
`of small translations. For each transla-
`tion of the edges of the left image onto
`the edges of the right image, a measure
`of similarity would be computed. A typi-
`cal similarity measure would be the cor-
`relation between the images. If the simi-
`larity measure is computed for all trans-
`lations then the search strategy is simply
`exhaustive. The images are registered
`using the translation which optimizes the
`similarity criterion. However, the choice
`of using edges for features, translations
`for the search space, exhaustive search
`for the search strategy and correlation
`for the similarity metric will
`influence
`the outcome of this registration. In fact,
`in this case,
`the registration will un-
`doubtably be unsatisfactory since the im-
`ages are misaligned in a more complex
`
`VALEO EX. 1026_002
`VALEO EX. 1026_002
`
`
`
` %
`
`5‘
`.
`.
`.
`.
`V’ I
`¢f4¥§£%?:f%Z’v"§§"2fi;‘I§$”é.’Z£*’$Z£5“’
`
`g...
`*é’3%é?3? z
`
`.
`
`,_
`
`Figure 1. X-ray images of a patient’s chest, taken
`at different times. (Thanks to A. Goshtasby.)
`
`way than translation. By establishing the
`relationship between the variations be-
`tween the images and the choices for the
`four components of image registration,
`this paper provides a framework for un-
`derstanding the exisiting registration
`techniques and also a methodology for
`assisting in the selection of the appropri-
`ate technique for a specific problem. By
`establishing the relationship between the
`variations among the images and the
`choices for the four components of image
`registration, this paper provides a frame-
`work for understanding the existing reg-
`istration techniques and also a methodol-
`ogy for assisting in the selection of
`the appropriate technique for a specific
`problem.
`The need to register images has arisen
`in many practical problems in diverse
`fields. Registration is often necessary for
`(1) integrating information taken from
`different sensors, (2) finding changes in
`images taken at different times or under
`different conditions, (3) inferring three-
`dimensional information from images in
`which either the camera or the objects in
`the scene have moved, and (4) for model-
`based object recognition [Rosenfeld and
`Kak 1982].
`An example of the first case is shown
`in Figure 2. In this figure the upper right
`image is a Magnetic Resonance Image
`(MRI) of a patient’s liver. From this im-
`age it is possible to discern the anatomi-
`cal structures. Since this image is similar
`to what a surgeon will see during an
`operation, this image might be used to
`
`Image Registration Techniques
`
`°
`
`327
`
`
`
`Figure 2. The top left image is a SPECT image of
`a patient’s liver. The top right shows the same
`region viewed by MRI. A contour was manually
`drawn around the liver in the MRI image. The
`location of this contour in the SPECT image shows
`the mismatch between the two images. At the bot-
`tom right the MRI image has been registered to the
`SPECT image, and the location of the transformed
`contour is shown on the SPECT image, bottom left.
`A brief description of the registration method em-
`ployed is in Section 3.3.3. (Courtesy of QSH, an
`image display and processing toolkit [N02 1988]
`and New York University; I would like to thank B.
`A. Birnbaum, E. L. Kramer, M. E. Noz, and J. J.
`Sanger of New York University, and G. Q. Maguire,
`Jr. of Columbia University.)
`
`plan a medical procedure. The upper left
`image is from single photon emission
`computed tomography (SPECT). It shows
`the same anatomical region after intra-
`venous administration of a Tc-99m (a ra-
`dionuclide) labeled compound. This im-
`age depicts some of the functional behav-
`ior of the liver (the Tc-99m compound
`binds to red blood cells) and can more
`accurately distinguish between cancers
`and other benign lesions. Since the two
`images are taken at different resolutions,
`from different viewpoints, and at differ-
`ent times,
`it is not possible to simply
`overlay the two images. However, if the
`images can be registered, then the func-
`tional information of the SPECT image
`can be structurally localized using the
`MRI image. Indeed, the registration of
`images which show anatomical struc-
`tures such as MRI, CT (computed tomog-
`raphy) and ultrasound, and images which
`show functional and metabolic activity
`such as SPECT, PET (positron emission
`
`ACM Computing Surveys, Vol. 24, No. 4, December 1992
`
`VALEO EX. 1026_003
`VALEO EX. 1026_003
`
`
`
`328
`
`*
`
`Lisa G. Brown
`
`tomography), and MRS (magnetic reso-
`nance spectroscopy) has led to improved
`diagnosis, better surgical planning, more
`accurate radiation therapy, and count-
`less other medical benefits [Maguire et
`al. 1990].
`In this survey, the registration meth-
`ods from three major research areas are
`studied:
`
`(1) Computer Vision and Pattern Recog-
`nition~for numerous different tasks
`
`such as segmentation, object recogni-
`tion,
`shape reconstruction, motion
`tracking, stereomapping, and charac-
`ter recognition.
`
`Image Analysis—including
`(2) Medical
`diagnostic medical imaging, such as
`tumor detection and disease localiza-
`tion, and biomedical research includ-
`ing classification of microscopic im-
`ages of blood cells, cervical smears,
`and chromosomes.
`
`(3) Remotely Sensed Data Processing-
`for civilian and military applications
`in agriculture, geology, oceanogra-
`phy, oil and mineral exploration, pol-
`lution and urban studies, forestry,
`and target
`location and identifica-
`tion.
`
`For more information specifically related
`to each of these fields, the reader may
`consult Katuri and Jain [1991] or Horn
`[1989]
`in computer vision, Stytz et al.
`[1991] and Petra et al. [1992] in medical
`imaging, and Jensen [1986] and Thomas
`et al. [1986] in remote sensing. Although
`these three areas have contributed a
`
`great deal to the development of registra-
`tion techniques,
`there are still many
`other areas which have developed their
`own specialized matching techniques. for
`example,
`in speech understanding,
`robotics and automatic inspection, com-
`puter-aided design and manufacturing
`(CAD / CAM), and astronomy. The three
`areas studied in this paper include many
`instances from the four classes of prob-
`lems mentioned above and a good range
`of distortion types including:
`
`0 sensor noise
`
`ACM Computing Surveys, Vol 24, No. 4, December 1992
`
`0 perspective changes from sensor view-
`point or platform perturbations
`
`0 object changes such as movements, de-
`formations, or growths
`
`0 lighting and atmospheric changes in-
`cluding shadows and cloud coverage
`0 different sensors.
`
`Tables 1 and 2 contain examples of
`specific problems in registration for each
`of the four classes of problems taken from
`computer vision and pattern recognition,
`medical
`image analysis, and remotely
`sensed data processing. The four classes
`are (1) multimodal registration, (2) tem-
`plate matching,
`(3) viewpoint registra-
`tion, and (4)
`temporal registration. In
`classes (1), (3), and (4) the typical objec-
`tive of registration is to align the images
`so that the respective changes in sensors,
`in viewpoint, and over time can be de-
`tected. In class (2), template matching,
`the usual objective is to find the optimal
`location and orientation, if one exists, of
`a template image in another image, often
`as part of a larger problem of object
`recognition. Each class of problems is de-
`scribed by its typical applications and
`the characteristics of methods commonly
`used for that class. Registration prob-
`lems are by no means limited by this
`categorization scheme. Many problems
`are combinations of these four classes of
`
`problems; for example, frequently images
`are taken from different perspectives and
`under different conditions. Furthermore,
`the typical applications mentioned for
`each class of problems are often applica-
`tions in other classes as well. Similarly,
`method characteristics are listed only to
`give an idea of some of the more common
`attributes used by researchers for solving
`these kinds of problems.
`In general,
`methods are developed to match images
`for a wide range of possible distortions,
`and it is not obvious exactly for which
`types of problems they are best suited.
`One of the objectives of these tables is to
`present to the reader the wide range of
`registration problems. Not surprisingly,
`this diversity in problems and their ap-
`plications has been the cause for the de-
`
`VALEO EX. 1026_004
`VALEO EX. 1026_004
`
`
`
`Image Registration Techniques
`
`'
`
`329
`
`Table 1. Registration Problems— Part I
`MULTIMODAL REGISTRATION
`
`Class of Problems: Registration of images of the same scene acquired from different sensors.
`Typical Application: Integration of information for improved segmentation and pixel classification.
`Characteristics of Methods: Often use sensor models; need to preregister intensities; image acquisition
`using subject frames and fiducial markers can simplify problem.
`Example 1
`
`Field: Medical Image Analysis
`Problem: Integrate structural information from CT or MRI with functional information from radionucleic
`scanners such as PET or SPECT for anatomically locating metabolic function.
`Example 2
`
`Field: Remotely Sensed Data Processing
`Problem: Integrating images from different electromagnetic bands, e.g., microwave, radar, infrared, visual,
`or multispectral for improved scene classification such as classifying buildings. roads, vehicles, and type of
`vegetation.
`
`TEMPLATE REGISTRATION
`
`Class of Problems: Find a match for a reference pattern in an image.
`Typical Application: Recognizing or locating a pattern such as an atlas, map, or object model in an image.
`Characteristics of Methods: Model—based approaches, preselected features, known properties of objects,
`higher-level matching.
`
`Example 1
`
`Field: Remotely Sensed Data Processing
`Problem: Interpretation of we1l—defined scenes such as airports; locating positions and orientations of
`known features such as runways, terminals, and parking lots.
`Example 2
`
`Field: Pattern Recognition
`Problem: Character recognition, signature verification, and waveform analysis.
`
`Table 2. Registration Problems— Part II
`VIEWPOINT REGISTRATION
`
`Class of Problems: Registration of images taken from different viewpoints.
`Typical Application: Depth or shape reconstruction.
`Characteristics of Methods: Need local transformation to account for perspective distortions; often use
`assumptions about viewing geometry and surface properties to reduce search; typical approach is feature
`correspondence, but problem of occlusion must be addressed.
`Example 1
`
`Field: Computer Vision
`Problem: Stereomapping to recover depth or shape from disparities.
`Example 2
`
`Field: Computer Vision
`Problem: Tracking object motion; image sequence analysis may have several images which differ only
`slightly, so assumptions about smooth changes are justified.
`TEMPORAL REGISTRATION
`
`Class of Problems: Registration of images of same scene taken at different times or under different
`conditions.
`Typical Applications: Detection and monitoring of changes or growths.
`Characteristics of Methods: Need to address problem of dissimilar images, i.e., registration must tolerate
`distortions clue to change, best if can model sensor noise and viewpoint changes; frequently use Fourier
`methods to minimize sensitivity to dissimilarity.
`Example 1
`
`Field: Medical Image Analysis
`Problem: Digital Subtraction Angiography (DSA)—registration of images before and after radio isotope
`injections to characterize functionality, Digital Subtraction Mammiography to detect tumors. early cataract
`detection.
`
`Field: Remotely Sensed Data Processing
`Problem: Natural resource monitoring, surveillance of nuclear plants, urban growth monitoring.
`
`Example 2
`
`ACM Computing Surveys, Vol. 24, No. 4, December 1992
`
`VALEO EX. 1026_005
`VALEO EX. 1026_005
`
`
`
`330
`
`'
`
`Lisa G. Brown
`
`velopment of enumerable independent
`registration methodologies.
`This broad spectrum of methodologies
`makes it difficult to classify and compare
`techniques since each technique is often
`designed for specific applications and not
`necessarily for specific types of problems
`or data. However, most registration tech-
`niques involve searching over the space
`of transformations of a certain type to
`find the optimal
`transformation for a
`particular problem. In Figure 3, an ex-
`ample of several of the major transforma-
`tion classes are shown. In the top left of
`Figure 3, an example is shown in which
`images are misaligned by a small shift
`due to a small change in the camera’s
`position. Registration,
`in this case,
`in-
`volves a search for the direction and
`amount of translation needed to match
`the images. The transformation class is
`thus the class of small translations. The
`
`other transformations shown in Figure 3
`are a rotational, rigid body, shear, and a
`more general global transformation due
`to terrain relief. In general, the type of
`transformation used to register images is
`one of the best ways to categorize the
`methodology and assist in selecting tech-
`niques for particular applications. The
`transformation type depends on the cause
`of the misalignment which may or may
`not account for all
`the variations be-
`tween the images. This will be discussed
`in more detail in Section 2.3.
`A few definitions and important dis-
`tinctions about
`the nomenclature used
`throughout this survey may prevent some
`confusion; see Table 3.
`The distinctions to be clarified are be-
`tween global/local
`transformations,
`global/local variations, and global /local
`computations. In addition, we will define
`what we mean by transformation, varia-
`tion, and computation in the context of
`registration.
`A transformation is a mapping of loca-
`tions of points in one image to new loca-
`tions in another. Transformations used
`to align two images may be global or
`local. A global
`transformation is given
`by a single equation which maps the en-
`tire image. Examples (to be described in
`
`ACM Computing Surveys, Vol. 24, No. 4, December 1992
`
`Translation
`
`Rigid Body
`
`Rotation
`
`Horizontal Shear
`
`Terrain Relief — Global
`
`Figure 3. Examples of typical geometric transfor-
`mations.
`
`Section 2.2) are the affine, projective,
`perspective, and polynomial transforma-
`tions. Local transformations map the im-
`age differently depending on the spatial
`location and are thus much more difficult
`to express succinctly. In this survey, since
`we classify registration methods accord-
`ing to their
`transforination type,
`a
`method is global or local according to the
`transformation type that it uses. This is
`not always the case in other papers on
`this subject.
`Variations refer to the differences in
`
`values and locations of pixels (picture
`elements) between the two images. We
`refer to differences in values as valumet-
`
`ric differences. Typically, value changes
`are differences in intensity or radiome-
`try, but we use this more general term in
`order to include the wide variety of exist-
`ing sensors whose Values are not intensi-
`ties, such as many medical sensors which
`
`VALEO EX. 1026_006
`VALEO EX. 1026_006
`
`
`
`Image Registration Tech niques
`
`'
`
`33 1
`
`Table 3.
`
`Important Distinctions for Image Registration Methods
`
`TRANSFORMATION: a mapping of locations of points in one image to new locations of points in another.
`GLOBAL: map is composed of a single equation that maps each point in the first image to new location
`in the second image. The equation is a function of the locations of the first image, but it is the
`same function for all parts of the image, ie, the parameters of the function do not depend on
`the location.
`
`LOCAL:
`
`mapping of points in the image depends on their location—the map is composed of several
`smaller maps (several equations) for each piece of the image that is considered.
`
`VARIATIONS: the differences in the values of pixels and their location between the images including
`distortions which have corrupted the true measurements.
`GLOBAL:
`the images differ similarly throughout the entire image. For example, variations due to
`additive white noise affect the intensity values of all pixels in the same way. Each pixel will
`be affected differently, but the difference does not depend on the location of the pixel.
`the variation between images depends on the location in the image. For example, distortions
`due to perspective depend on the depth of the objects projected onto the image. Regions in the
`image which correspond to objects which are farther away are distorted in a different way
`than regions which correspond to closer objects.
`
`LOCAL:
`
`COMPUTATION: refers to the set of calculations performed to determine the parameters of the
`registration transformation.
`GLOBAL:
`uses all parts of the image to compute the parameters of the transformation. If a local
`transformation is being calculated, then each set of local parameters is computed using the
`entire image. This is generally a costly method but has the advantage of using more
`information.
`uses only the relevant local parts of the image for each set of local parameters in determining
`a local transformation. By using only local parts of the image for each calculation, the method
`is faster. It can also have the advantage of not being erroneously influenced by other parts of
`the image.
`
`LOCAL:
`
`measure everything from hydrogen den-
`sity (magnetic resonance imaging)
`to
`temperature (thermography). Some of the
`variations between the images are dis-
`tortions. Distortions refer to the noise
`
`that has corrupted or altered the true
`intensity values and their locations in
`the image. What is a distortion and What
`is not depend on what assumptions are
`made about the sensor and the condi-
`tions under which the images are taken.
`This will be discussed in more detail in
`Section 2.3. The variations in the image
`may be due to changes in the scene or
`the changes caused by a sensor and its
`position and viewpoint. We would like to
`remove some of these changes via regis-
`tration; but others may be difficult
`to
`remove (such as the effects of illumina-
`tion changes), or we are not interested in
`removing them,
`i.e.,
`there may be
`changes that we would like to detect.
`When we describe a set of variations as
`global or
`local, we are referring to
`whether or not the variations can be re-
`
`moved by a global or a local transfor-
`mation. However, since it is not always
`
`possible to remove alll the distortions be-
`tween the images, and because we do not
`want to remove some of the variations, it
`is critical for the understanding of regis-
`tration methods to recognize the differ-
`ence between whether certain variations
`
`are global or local and whether the se-
`lected transformation is global or local.
`For example, images may have local vari-
`ations, but a registration method may
`use a global transformation to align them
`because some of the variations are differ-
`ences Lo be detected after registration.
`The important distinctions between the
`various types of variations will be ex-
`plained in more detail in Section 2.3.
`The final definition and distinction we
`
`address are with respect to the registra-
`tion computation. The registration com-
`putation refers to the calculations per-
`formed to determine the parameters of
`the transformation. When a computation
`is described as global or local this refers
`to Whether the calculations needed to
`
`determine the parameters of the trans-
`formation require information from the
`entire image or whether each subset of
`
`ACM Computing Surveys, Vol. 24, No. 4, December 1992
`
`VALEO EX. 1026_007
`VALEO EX. 1026_007
`
`
`
`332
`
`'
`
`Lisa G. Brown
`
`parameters can be computed from small
`local regions. This distinction only makes
`sense when a local transformation is used
`for
`registration,
`since when a global
`transformation is required only one set of
`parameters are computed. However, this
`is again distinct from the type of trans-
`formation used. For example, registra-
`tion methods which search for the opti-
`mal
`local transformation may be more
`accurate and slower if they require global
`computations in order to determine local
`parameters since they use information
`from the entire image to find the best
`alignment.
`One further comment is in order. In
`
`this paper the registration techniques re-
`viewed were developed for images which
`are two dimensional. With the advent of
`
`cheaper memory, faster computers, and
`improved sensor capability,
`it has be-
`come more and more common to acquire
`three-dimensional images, for example,
`with laser
`range finders, motion se-
`quences, and the latest 3D medical mo-
`dalities. Registration problems abound in
`both 2D and 3D cases, but in this paper
`only 2D techniques are examined. Al-
`though many of the 2D techniques can be
`generalized to higher-dimensional data,
`there are several additional aspects that
`inevitably need to be considered when
`dealing with the immense amount of data
`and the associated computational cost in
`the 3D case. Furthermore, many of the
`problems arising from the projection of
`3—space onto a 2D image are no longer
`relevant. Techniques developed to over-
`come the unique problems of 3D registra-
`tion are not surveyed in this paper.
`In the next section of this paper the
`basic theory of the registration problem
`is given. Image registration is defined
`mathematically as are the most com-
`monly used transformations. Then image
`variations and distortions and their rela-
`
`tionship to solving the registration prob-
`lem are described. Finally the related
`problem of rectification, which refers to
`the correction of geometric distortions
`produced by the projection of a flat plane,
`is detailed.
`
`In Section 3 of this paper the major
`approaches to registration are described
`
`ACM Computing Surveys, Vol. 24, No 4, December 1992
`
`based on the complexity of the type of
`transformation that is searched. In Sec-
`tion 3.l, the traditional technique of the
`cross—correlation function and its close
`relatives, statistical correlation, matched
`filters, the correlation coefficient, and se-
`quential techniques are described. These
`methods are typically used for small
`well-defined affine transformations, most
`often for a single translation. Another
`class of techniques used for affine trans-
`formations,
`in cases where frequency-
`dependent noise is present, are the
`Fourier methods described in Section 3.2.
`If an affine transformation is not suffi-
`
`cient to match the images then a more
`general global
`transformation is
`re-
`quired. The primary approach in this case
`requires feature point mapping to define
`a polynomial transformation. These tech-
`niques are described in 3.3. However, if
`the source of misregistration is not global,
`i.e.,
`the images are misaligned in dif-
`ferent ways over different parts of the
`image,
`then a local
`transformation is
`needed. In the last section of 3.3,
`the
`techniques which use the simplest
`lo-
`cal transformation based on piecewise in-
`terpolation are described.
`In the most
`complex cases, where the registration
`technique must determine a local trans-
`formation when legitimate local distor-
`tions are present,
`i.e., distortions that
`are not
`the cause of misregistration,
`techniques based on specific transforma-
`tion models such as an elastic membrane
`are used. These are described in Section
`3.4.
`The methods described in Section 3 are
`used as examples for the last section of
`this survey. Section 4 offers a framework
`for the broad range of possible registra-
`tion techniques. Given knowledge of the
`kinds of variations present, and those
`which need to be corrected, registration
`techniques can be designed, based on the
`transformation class which will be suffi-
`
`cient to align the images. The transfor-
`mation class may be one of the classical
`ones described in Section 2.2 or a specific
`class defined by the parameters of the
`problem. Then a feature space and simi-
`larity measure are selected which are
`least sensitive to remaining variations
`
`VALEO EX. 1026_008
`VALEO EX. 1026_008
`
`
`
`Image Registration Techniques
`
`'
`
`333
`
`and are most likely to find the best match.
`Lastly, search techniques are chosen to
`reduce the cost of computations and guide
`the search to the best match given the
`nature of the remaining Variations. In
`Section 4, several alternatives for each
`component of a registration method are
`discussed using the framework devel-
`oped, in particular, with respect to the
`characteristics of the Variations between
`
`the images as categorized in Section 2.3.
`
`2.
`
`IMAGE REGISTRATION IN THEOFIY
`
`2.1 Definition
`
`Image registration can be defined as a
`mapping between two images both spa-
`tially and with respect to intensity. If we
`define these images as two 2D arrays of a
`given size denoted by I1 and 12 where
`I1(x,y) and I2(x,y) each map to their
`respective intensity (or other measure-
`ment) values, then the mapping between
`images can be expressed as:
`
`where f is a 2D spatial—coordinate trans-
`formation,
`i.e., f is a transformation
`which maps two spatial coordinates, x
`and y, to new spatial coordinates x’ and
`y’,
`
`(x’,y') =f(x,y)
`
`and g is a 1D intensity or radiometric
`transformation.
`
`The registration problem is to find the
`optimal spatial and intensity transfor-
`mations so that the images are matched
`either for the purposes of determining
`the parameters of the matching transfor-
`mation or to expose differences of inter-
`est between the images. The intensity
`transformation is not always necessary,
`and often a simple lookup table deter-
`mined by sensor calibration techniques is
`sufficient [Bernstein 1976]. An example
`where an intensity transformation is used
`is in the case where there is a change in
`sensor type (such as optical
`to radar
`[Wong 1977]). Another example when an
`intensity transformation is needed is
`when objects in the scene are highly
`specular (their reflectance is mirror-like)
`
`and when there is a change in viewpoint
`or surface orientation relative to the light
`source. In the latter case, although an
`intensity transformation is needed,
`in
`practice it is impossible to determine the
`necessary transformation since it
`re-
`quires knowing the reflectance properties
`of the objects in the scene and their shape
`and distance from the sensor. Notice, that
`in these two examples, the intensity vari-
`ations are due to changes in the acquisi-
`tion of the images of the scene: in the
`first case by the change in sensors and in
`the second by the change in reflectance
`seen by the sensor. In many other in-
`stances of variations in intensity,
`the
`changes are due to differences in the
`scene that are not due to how the scene
`
`was projected by the sensor onto an im-
`age, but rather the changes are intrinsic
`differences in the scene, such as move-
`ments, growths, or differences in relative
`depths, that are to be exposed by the
`registration process—not removed. After
`all, if the images are matched exactly,
`then besides learning the parameters of
`the best
`transformation, what
`infor-
`mation is obtained by performing the
`registration?
`Finding the parameters of the optimal
`spatial or geometric transformation is
`generally the key to any registration
`problem. It is frequently expressed para-
`metrically as
`two single-valued func-
`tions, fwfy:
`
`I2(x> : I1(fx(x>y)7
`
`which may be more easily implemented.
`
`2.2 Transformations
`
`The fundamental characteristic of any
`image registration technique is the type
`of spatial
`transformation or mapping
`used to properly overlay two images. Al-
`though many types of variations may be
`present in each image, the registration
`technique must select the class of trans-
`formation which will remove only the
`spatial distortions between images due to
`differences in acquisition and scene char-
`acteristics which affect acquisition. Other
`differences in scene characteristics that
`are to be exposed by registration should
`
`ACM Computing Surveys, Vol. 24, No. 4, December 1992
`
`VALEO EX. 1026_009
`VALEO EX. 1026_009
`
`
`
`334
`
`'
`
`Lisa G. Brown
`
`not be used to select the class of transfor-
`mation. In this section, We will define
`several
`types of
`transformations and
`their parameters, but we defer our dis-
`cussion of how the transformation type is
`selected for a specific problem and what
`procedures are used to find its parame-
`ters until later.
`
`The most common general transforma-
`tions are rigid, affine, projective, perspec-
`tive, and global polynomial. Rigid trans-
`formations account for object or sensor
`movement in which objects in the images
`retain their relative shape and size. A
`rigid-body transformation is composed of
`a combination of a rotation, a transla-
`tion, and a scale change. An example is
`shown in Figure 3. Affine transforma-
`tions are more general than rigid and
`can therefore tolerate more complicated
`distortions while still maintaining some
`nice mathematical properties. A shear
`transformation, also shown in Figure 3,
`is an example of one type of affine trans-
`formation. Projective transformations
`and the more general perspective trans-
`formations account for distortions due to
`the projection of objects at varying dis-
`tances to the sensor onto the image plane.
`In order to use the perspective transfor-
`mation for registration, knowledge of the
`distance of the objects of the scene rela-
`tive to the sensor is needed. Polynomial
`transformations are one of the most gen-
`eral global
`transformations (of which
`affine is the simplest) and can account
`for many types of distortions so long as
`the distortions do not vary too much over
`the image. Distortions due to moderate
`terrain relief (see the bottom example in
`Figure 3) can often be corrected by a
`polynomial
`transformation. The trans-
`formations just described are all well-
`defined mappings of one image onto an-
`other. Given the intrinsic nature of
`imagery of nonrigid objects, it has been
`suggested (personal communication,
`Maguire, G. Q., Jr., 1989)
`that some
`problems, especially in medical diagno-
`sis, might benefit from the use of fuzzy or
`probabilistic transformations.
`In this section we will briefly define
`the different transformation classes and
`
`ACM Computing Surveys, Vol 24. No. 4, D