A Survey of
`
`Image Registration
`
`Techniques
`
`LISA GOTTESFELD BROWN
`
`Department
`
`of Computer
`
`Sctence, Colunzbza
`
`Unzl,ersity,
`
`New York, NY 10027
`
`task in image processing used to match two or more
`Registration M a fundamental
`pictures taken, for example, at different
`times, from different sensors, or from different
`viewpoints. Virtually all
`large systems which evaluate images require the registration
`of images, or a closely related operation, as an intermediate step. Specific examples of
`systems where image registration is a significant component include matching a target
`with a real-time image of a scene for target recognition, monitoring global
`land usage
`using satellite images, matching stereo images to recover shape for autonomous
`navigation, and aligning images from different medical modalities for diagnosis.
`Over the years, a broad range of techniques has been developed for various types of
`data and problems. These techniques have been independently studied for several
`different applications,
`resulting in a large body of research. This paper organizes this
`material by estabhshing the relationship between the variations in the images and the
`type of registration techniques which can most appropriately be applied. Three major
`types of variations are distinguished. The first
`type are the variations due to the
`differences in acquisition which cause the images to be misaligned. To register images,
`a spatial
`transformation
`is found which will
`remove these variations. The class of
`transformations which must be searched to find the optimal
`transformation is
`determined by knowledge about the variations of this type. The transformation class in
`turn influences the general
`technique that should be taken. The second type of
`variations are those which are also due to differences in acquisition, but cannot be
`modeled easily such as lighting and atmospheric conditions. This type usually effects
`intensity values, but
`they may also be spatial, such as perspective distortions, The
`thn-d type of variations are differences in the images that are of interest such as object
`movements, growths, or other scene changes. Variations of the second and third type
`are not directly removed by registration, but
`they make registration more difficult
`since an exact match is no longer possible. In particular,
`it is critical
`that variations of
`the third type are not removed. Knowledge about the characteristics of each type of
`variation effect the choice of feature space, similarity measure, search space, and
`search strategy which will make up the final
`technique. All registration techniques can
`be viewed as different combinations of these choices. This framework M useful
`for
`understanding the merits and relationships between the wide variety of existing
`techniques and for assisting in the selection of the most suitable I echnique for a
`specific problem.
`
`Introductory and
`Categories and Subject Descriptors: A. 1 [General
`Literature]:
`Vision and Scene Understanding; 1.4
`Survey; 1.2.10 [Artificial
`Intelligence]:
`Image Processing; 1.5 [Computing
`[Computing
`Methodologies]:
`Methodologies]:
`Pattern Recognition
`General Terms: Algorithms, Design, Measurement, Performance
`Additional Key Words and Phrases: Image registration,
`image warping,
`template matching
`
`rectification,
`
`the copies are not made
`is granted provided that
`fee all o. part of this material
`Permission to copy without
`or distributed for direct commercial advantage,
`the ACM copyright notice and the title of the publication
`and Its data appear, and notie is given that copying is by permission of the Associatlon for Computing
`Machinery. To copy otherwise, or to repubhsh, requires a fee and/or specific permission.
`@ 1992 ACM 0360-0300/92/’ 1200-0325 $01.50
`
`ACM Comput,ng Surveys,VoI 24, No. 4, December 1992
`
`VALEO EX. 1028_001
`
`

`

`326
`
`“
`
`Lisa
`
`G. Brown
`
`CONTENTS
`
`1. INTRODUCTION
`2 IMAGE REGISTRATION IN THEORY
`2 1 Defimtlon
`22 Tran~f~=matlon
`23 Image Varlatlons
`24 Rectlticatlon
`3 REGISTRATION METHODS
`31 Correlatmn and Sequential Methods
`32 Fourier Methods
`33 Point Mapping
`34 E1.ast,cModel-BasedMatch]ng
`35 Summary
`4 CHARACTERISTICS OF REGISTRATION
`METHODS
`41 Feature Space
`42 SlmdarIty Measure
`43 SearchSpaceand Strategy
`44 Summary
`
`~—
`
`1
`
`INTRODUCTION
`
`images
`arises when
`problem
`A frequent
`different
`times,
`by
`different
`taken,
`at
`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
`for a. prototype
`or
`occurs when
`searching
`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-
`in
`tion must
`be found
`so that
`the points
`one image
`can be related
`to their
`corre-
`sponding
`points
`in the other.
`The deter-
`mination
`of
`the
`optimal
`transformation
`of
`for
`registration
`depends
`on the types
`ob-
`variations
`between
`the
`images.
`The
`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
`different
`combinations
`of choices
`for
`following
`four
`components:
`
`as
`the
`
`(1) a feature
`(2) a search
`(3) a search
`(4) a similarity
`
`space,
`space,
`strategy,
`metric.
`
`and
`
`ACM Computmg Surveys,
`
`Vol.
`
`24, No.
`
`4, December
`
`1992
`
`in
`
`The
`informa-
`the
`extracts
`space
`feature
`be used for
`that will
`in the images
`tion
`is the class
`matching.
`The
`search
`space
`capable
`of
`of
`transformations
`that
`is
`aligning
`the images.
`The search
`strategy
`decides
`how to choose the next
`transfor-
`mation
`from this
`space,
`to be tested
`the
`search
`for
`the
`optimal
`transforma-
`determines
`tion.
`The
`similarity
`metric
`the
`relative
`merit
`each test. Search
`for
`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.
`of
`For
`example,
`consider
`the
`problem
`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
`amount
`of data
`the
`to be evaluated.
`If
`is thought
`that
`the
`it
`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
`this
`the outcome
`of
`registration.
`In fact,
`the
`in
`this
`case,
`registration
`will
`un-
`doubtable
`be unsatisfactory
`since the im-
`ages are misaligned
`in a more
`complex
`
`VALEO EX. 1028_002
`
`

`

`image
`
`Registration
`
`Techniques
`
`l
`
`327
`
`Figure 1. X-ray images of a patient’s chest, taken
`at different
`times. (Thanks to A. Goshtasby.)
`
`the
`be-
`the
`
`By establishing
`translation.
`way than
`the
`variations
`between
`relationship
`for
`tween
`the images
`and the choices
`four
`components
`of
`image
`registration,
`this
`paper
`provides
`a framework
`for un-
`derstanding
`the
`exisiting
`registration
`for
`techniques
`and
`also
`a methodology
`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
`for
`choices
`the four
`components
`of
`image
`registration,
`this paper
`provides
`a frame-
`work
`for understanding
`the existing
`reg-
`istration
`techniques
`and also a methodol-
`of
`ogy
`for
`assisting
`in
`the
`selection
`the
`appropriate
`technique
`for
`a specific
`problem.
`has arisen
`images
`The need to register
`in
`diverse
`in many
`practical
`problems
`necessary
`for
`fields. Registration
`is often
`taken
`from
`(1)
`integrating
`information
`changes
`in
`different
`sensors,
`(2)
`finding
`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].
`case is shown
`the first
`of
`An example
`the upper
`right
`figure
`in Figare
`2.
`In this
`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 is a SPECT image of
`Figure 2. The top left
`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
`[Noz 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.)
`
`left
`The upper
`procedure.
`a medical
`plan
`photon
`emission
`is
`from single
`image
`(SPECT).
`It shows
`computed
`tomography
`region
`after
`intra-
`the
`same
`anatomical
`of a Tc-99m (a ra-
`venous
`administration
`compound.
`This
`im-
`dionuclide)
`labeled
`the functional
`behav-
`age depicts
`some of
`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-
`it
`ent
`times,
`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-
`as MRI, CT (computed
`tomog-
`tures
`such
`raphy)
`and ultrasound,
`and images which
`show functional
`and metabolic
`activity
`such as SPECT,
`PET (positron
`emission
`
`ACM Computing Surveys,Vol 24, No. 4, December1992
`
`VALEO EX. 1028_003
`
`

`

`328
`
`*
`
`Lisa
`
`G. Brown
`
`reso-
`and MRS (magnetic
`tomography),
`nance
`spectroscopy)
`has led to improved
`diagnosis,
`better
`surgical
`planning,
`more
`accurate
`radiation
`therapy,
`and
`count-
`less other medical
`benefits
`[Maguire
`et
`al. 1990].
`the
`survey,
`In this
`ods from three major
`studied:
`
`meth-
`areas
`are
`
`registration
`research
`
`(1)
`
`(2)
`
`(3)
`
`Recog-
`tasks
`recogni-
`motion
`and charac-
`
`and Pattern
`Vision
`Computer
`numerous
`different
`nition—for
`such as segmentation,
`object
`tion,
`shape
`reconstruction,
`tracking,
`stereomapping,
`ter
`recognition.
`Analysis-including
`Medical
`Image
`as
`imaging,
`such
`diagnostic
`medical
`tumor
`detection
`and disease
`localiza-
`tion,
`and biomedical
`research
`includ-
`ing
`classification
`of microscopic
`im-
`ages of blood
`cells,
`cervical
`smears,
`and chromosomes.
`Processin~—
`Remotely
`Sensed Data
`applicati~ns
`for civil~an
`and military
`oceanogra-
`in
`agriculture,
`geology,
`phy, oil and mineral
`exploration,
`pol-
`lution
`and
`urban
`studies,
`forestry,
`and
`target
`location
`and
`identifica-
`tion.
`
`related
`specifically
`information
`For more
`the
`reader may
`of
`these
`fields,
`to each
`[ 1991]
`or Horn
`Katuri
`and Jain
`consult
`in
`computer
`vision,
`Stytz
`et al.
`[1989]
`and Petra
`et al.
`[ 1992]
`in medical
`[ 1991]
`and Jensen
`[1986]
`and Thomas
`imaging,
`et al.
`[1986]
`in remote
`sensing.
`Although
`these
`three
`areas
`have
`contributed
`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,
`com-
`robotics
`and
`automatic
`inspection,
`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:
`
`a
`
`_ sensor
`
`noise
`
`ACM Computmg Surveys, Vol 24, No. 4, December 1992
`
`from sensor
`changes
`perspective
`point
`or platform
`perturbations
`object
`changes
`such as movements,
`formations,
`or growths
`lighting
`atmospheric
`and
`cluding
`shadows
`and cloud
`
`changes
`coverage
`
`view-
`
`de-
`
`in-
`
`different
`
`sensors.
`
`of
`examples
`2 contain
`1 and
`Tables
`in registration
`for each
`problems
`specific
`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-
`In
`tion,
`and
`(4)
`temporal
`registration.
`objec-
`classes
`(1),
`(3), and (4)
`the typical
`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
`of
`location
`and orientation,
`if one exists,
`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
`this
`by
`categorization
`scheme.
`Many
`problems
`of
`are combinations
`of
`these
`four
`classes
`problems;
`for example,
`frequently
`images
`are taken
`from different
`perspectives
`and
`under
`different
`conditions.
`Furthermore,
`for
`the
`typical
`applications
`mentioned
`each class of problems
`are often
`applica-
`tions
`in other
`classes
`as well. Similarly,
`to
`method
`characteristics
`are listed
`only
`give an idea of some of
`the more common
`attributes
`used by researchers
`for solving
`In
`these
`kinds
`of
`problems.
`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,
`ap-
`this
`diversity
`in problems
`and their
`plications
`has been the cause for
`the de-
`
`VALEO EX. 1028_004
`
`

`

`Image
`
`Registration
`
`Techniques
`
`“
`
`329
`
`Table 1. Reglstratlon Problems — Part I
`
`MULTIMODAL REGISTRATION
`
`Registration of images of the same scene acquired from different sensors.
`Class of Problems:
`Integration of information for improved segmentation and pixel classification.
`Typical
`Application:
`Often use sensor
`Characteristics
`of Methods:
`models;
`need
`to
`preregister
`intensities;
`image
`acquisition
`using subject frames and fiducial markers can simplify problem.
`Example
`1
`
`Image Analysis
`Field: Medical
`information from radionucleic
`information from CT or MRI with functional
`Integrate structural
`Problem:
`scanners such as PET or SPECT for anatomically locating metabolic function.
`Example
`2
`
`Fteld: Remotely Sensed Data Processing
`infrared, visual,
`Integrating images from different electromagnetic bands, e.g., microwave, radar,
`Problem:
`or multispectral
`for improved scene classification such as classifying buildings,
`roads, vehicles, and type of
`vegetation.
`
`TEMPLATE REGISTRATION
`
`Find a match for a reference pattern in an image.
`Class of Problems:
`Recognizing or locating a pattern such as an atlas, map, or object model in an image.
`Typtcal
`Appltcatzon:
`of Methods: Model-based approaches, preselected features, known properties of objects,
`Characteristics
`higher-level matching.
`
`Field: Remotely Sensed Data Processing
`Interpretation
`of well-defined scenes such as airports;
`Problem:
`known features such as runways,
`terminals, and parking lots.
`Example
`2
`
`Example
`
`1
`
`locating positions and orientations of
`
`Field: Pattern Recognition
`Problem: Character recognition, signature verification, and waveform analysis.
`
`Table 2. Registration Problems — Part II
`
`VIEWPOINT REGISTRATION
`
`Registration of images taken from different viewpoints.
`Class of Problems:
`Depth or shape reconstruction.
`Typtcal
`Application:
`to account for perspecl:ive distortions; often use
`Need local
`transformation
`Characteristics
`of Methods;
`assumptions about viewing geometry and surface properties to reduce search; typical approach is feature
`correspondence, but problem of occlusion must be addressed.
`Example
`1
`
`F6eld: Computer Vision
`Stereomapping to recover depth or shape from disparities.
`Problem:
`Example
`2
`
`Field: Computer Vision
`image sequence analysis may have several
`Tracking object motion;
`Problem:
`slightly, so assumptions about smooth changes are justified.
`TEMPORAL REGISTRATION
`
`images which differ only
`
`Registration of
`
`images of same scene taken at different
`
`of Problems:
`Class
`conditions.
`Detection and monitoring of changes or growths.
`Typzcal Applications:
`tolerate
`Need to address problem of dissimilar
`images, i.e., registration must
`Characteristics
`of Methods:
`distortions due to change, best if can model sensor noise and viewpoint changw;
`frequently use Fourier
`methods to minimize sensitivity to dissimilarity.
`
`times or under different
`
`Example
`
`1
`
`Image Analysis
`Field: Medical
`of images before and after radio isotope
`Digital Subtraction Angiography (DSA)—registration
`Problem:
`injections to characterize functionality, Digital Subtraction Mammography
`to detect tumors. early cataract
`detection.
`
`Fzeld: Remotely Sensed Data Processing
`Problem: Natural
`resource monitoring, surveillance of nuclear plants, urban growth monitoring.
`
`Example
`
`2
`
`ACM Comput]ng Surveys,Vol 24, No 4, December
`
`1992
`
`VALEO EX. 1028_005
`
`

`

`330
`
`“
`
`Lisa
`
`G. Brown
`
`independent
`
`enumerable
`of
`velopment
`methodologies.
`registration
`of methodologies
`spectrum
`This
`broad
`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-
`of
`tion
`classes
`are shown.
`In the top left
`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
`type
`to terrain
`relief.
`In general,
`the
`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
`the
`variations
`be-
`all
`tween
`the images.
`This will
`be discussed
`in more
`detail
`in Section
`2.3.
`A few definitions
`and
`important
`tinctions
`about
`the
`nomenclature
`throughout
`this
`survey may prevent
`confusion;
`see Table
`3.
`are be-
`The distinctions
`to be clarified
`tween
`global/local
`transformations,
`global/local
`and global/local
`variations,
`In addition,
`we will
`define
`computations.
`what we mean
`by transformation,
`varia-
`tion,
`and
`computation
`in the
`context
`of
`registration.
`loca-
`of
`is a mapping
`A transformation
`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
`
`dis-
`used
`some
`
`ACM
`
`Comput]ng
`
`Surveys,
`
`Vol
`
`24, No
`
`4, December
`
`1992
`
`Translation
`
`Rigid Body
`
`/!7
`
`Horizontal Shear
`
`Terrain Relief
`
`- Global
`
`Figure 3. Examples of typical geometric transfor-
`mations.
`
`projective,
`affine,
`the
`are
`2.2)
`Section
`transforma-
`and polynomial
`perspective,
`map the im-
`transformations
`tions.
`Local
`on the
`spatial
`depending
`age differently
`location
`and are thus much more difficult
`to express
`succinctly.
`In this
`survey,
`since
`accord-
`we classify
`registration
`methods
`a
`ing
`to
`their
`transformation
`type,
`method
`is global
`or
`local according
`to the
`transformation
`type
`that
`it uses. This
`is
`not
`always
`case in other
`papers
`on
`this
`subject.
`differences
`to the
`refer
`Variations
`of pixels
`(picture
`locations
`values
`and
`two
`images. We
`the
`between
`elements)
`in values
`as valunzet-
`refer
`to differences
`differences.
`Typically,
`value
`changes
`ric
`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
`
`the
`
`in
`
`VALEO EX. 1028_006
`
`

`

`Image
`
`Registration
`
`Tech niques
`
`0
`
`331
`
`Table 3.
`
`Important Dlstlnct[ons for
`
`Image Registration
`
`Methods
`
`of locations of points in one image to new locations of points in another.
`a mapping
`TRANSFORMATION
`that maps each point
`in the first
`image to new location
`GLOBAIJ
`map is composed
`of a single
`equation
`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, i.e., the parameters of the function do not depend on
`the location.
`location—the map is composed of several
`mapping of points in the image depends on their
`smaller maps (several equati ens) for each piece of the image that
`is considered.
`
`LOCAL:
`
`VARIATIONS:
`distortions
`GLOBAL:
`
`LOCAL:
`
`and their
`
`location
`
`of pixels
`in the values
`differences
`the
`the true measurements.
`have corrupted
`which
`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.
`
`between
`
`the images
`
`including
`
`to the set of calculations performed to determine the parameters of
`
`the
`
`refers
`COMPUTATION
`registration transformation.
`If a local
`the image to compute the parameters of the transformation.
`GLOBAL:
`uses all parts of
`is being calculated,
`then each set of local parameters is computed using the
`transformation
`entire image. This is generally a costly method but has the advantage of using more
`information.
`local parts of the image for each set of local parameters m determining
`uses only the relevant
`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:
`
`den-
`from hydrogen
`everything
`measure
`to
`sity
`(magnetic
`resonance
`imaging)
`temperature
`(thermography).
`Some of the
`variations
`between
`the
`images
`are
`dis-
`Distortions
`refer
`to
`the
`noise
`tortions.
`has
`that
`corrupted
`or altered
`the
`true
`intensity
`values
`their
`locations
`in
`and
`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-
`in
`tion changes),
`or we are not
`interested
`be
`removing
`them,
`i.e.,
`there
`may
`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
`
`be-
`the distortions
`alll
`to remove
`possible
`and because we do not
`the images,
`tween
`to remove
`some of
`the variations,
`it
`want
`is critical
`for
`the understanding
`of regis-
`tration
`methods
`to recognize
`the
`differ-
`ence between
`whether
`certain
`variations
`se-
`are global
`or
`local
`amd whether
`the
`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
`to be detected
`after
`registration.
`the
`The
`important
`distinctions
`between
`various
`types
`of variations
`will
`be ex-
`plained
`in more
`detail
`in Section
`2.3.
`we
`The final
`definition
`and distinction
`address
`are with
`respect
`to the reg-istra-
`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
`the
`trans-
`formation
`require
`information
`from the
`entire
`image
`or whether
`each
`subset
`of
`
`of
`
`ACM Computing Surveys,Vol. 24, No. 4, December 1992
`
`VALEO EX. 1028_007
`
`

`

`332
`
`l
`
`Lisa
`
`G. Brolvn
`
`from small
`can be computed
`parameters
`only makes
`This distinction
`local
`regions.
`is used
`a local
`transformation
`sense when
`a global
`for
`registration,
`since
`when
`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
`require
`global
`they
`computations
`in order
`to determine
`local
`parameters
`since
`they
`use
`information
`from the
`entire
`image
`to find
`the
`best
`alignment.
`In
`is in order.
`comment
`One
`further
`re-
`techniques
`this paper
`the registration
`images which
`for
`viewed were
`developed
`the advent
`of
`With
`are two dimensional.
`computers,
`and
`faster
`cheaper memory,
`capability,
`it
`has
`be-
`improved
`sensor
`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.
`the
`In
`the
`next
`section
`of
`this
`paper
`of
`basic
`theory
`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
`approaches
`
`the major
`paper
`are described
`
`this
`3 of
`to registration
`
`ACM
`
`Computmg
`
`Surveys,
`
`Vol
`
`24, No
`
`4, December
`
`1992
`
`of
`type
`the
`of
`complexity
`on the
`based
`In Sec-
`that
`is searched.
`transformation
`of
`the
`tion
`3.1,
`the traditional
`technique
`close
`its
`cross-correlation
`function
`and
`matched
`relatives,
`statistical
`correlation,
`and se-
`filters,
`the correlation
`coefficient,
`These
`quential
`techniques
`are described.
`small
`methods
`are
`typically
`used
`for
`most
`well-defined
`affine
`transformations,
`Another
`often
`for
`a single
`translation.
`trans-
`class of
`techniques
`used for affine
`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
`the
`cause
`of misregistration,
`not
`techniques
`based
`on specific
`transforma-
`tion models
`such as an elastic membrane
`are used. These
`are described
`in Section
`3.4.
`3 are
`in Section
`described
`The methods
`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. 1028_008
`
`

`

`Image
`
`Registration
`
`Techniques
`
`l
`
`333
`
`to find the best match.
`likely
`and are most
`techniques
`are chosen
`to
`Lastly,
`search
`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 THEORY
`
`2.1 Definition
`
`as a
`can be defined
`registration
`Image
`spa-
`two
`images
`both
`between
`mapping
`If we
`tially
`and with
`respect
`to intensity.
`of a
`define
`these images
`as two 2D arrays
`given
`size denoted
`by
`II
`and
`Iz where
`Il(x,
`y) and
`Iz(x,
`each map
`to their
`respective
`intensity
`(or
`other measure-
`ment)
`values,
`then
`the mapping
`between
`images
`can be expressed
`as:
`
`y)
`
`I,(x,
`
`y) =g(I1(f(x,
`
`y)))
`
`trans-
`is a 2D spatial-coordinate
`f’
`where
`i.e.,
`f
`is
`a transformation
`formation,
`x
`two
`spatial
`coordinates,
`which maps
`and y,
`to new spatial
`coordinates
`x‘ and
`Y’7
`
`(X’,
`
`y’)
`
`=f(x,
`
`y)
`
`or
`
`radiometric
`
`g is a ID intensity
`and
`transformation.
`the
`problem is to find
`The registration
`and
`intensity
`transfor-
`optimal
`spatial
`the images
`are matched
`mations
`so that
`purposes
`of determining
`either
`for
`the
`of
`the matching
`transfor-
`the parameters
`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)
`
`it
`
`of
`infor-
`the
`
`in viewpoint
`is a change
`there
`and when
`to the light
`orientation
`relative
`or surface
`the
`lattler
`case, although
`an
`source.
`In
`transformation
`is
`needed,
`in
`intensity
`is impossible
`to determine
`the
`practice
`it
`transformation
`since
`re-
`necessary
`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
`the
`images
`of
`the
`scene:
`in the
`of
`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
`variat