United States Patent [191
`Burt et al.
`
`[54]
`
`SYSTEM FOR AUTOMATICALLY ALIGNING
`IMAGES TO FORM A MOSAIC MAGE
`
`[75] Inventors: Peter J. Burt, Princeton; Michal Irani,
`Princeton Junction; Stephen Charles
`Hsu, East Windsor; Padmanabhan
`Anandan, Lawrenceville, all of N .J .;
`Michael W. Hansen. New Hope, Pa.
`
`[73] Assignee: David Sarnoif Research Center, Inc,
`Princeton, NJ.
`
`Appl. N0.: 339,491
`Filed:
`Nov. 14, 1994
`
`USO05649032A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,649,032
`Jul. 15, 1997
`
`Burt et al., “A Multiresolution Spline With Application to
`Image Mosaics”, ACM Transactions on Graphics, vol. 2,
`No. 4, pp. 217-236, Oct. 1983.
`Bove et al., “Real-Time Decoding and Display of Structured
`Video”, IEEE ICMCS, May 1994.
`Lundmark et al., “Image Sequence Coding at Very Low
`Bitrates: A Review”, IEEE Transactions on Image Process
`ing, vol. 3, No. 5, pp. 589-609, Sep. 1994.
`McLean, “Structured Video Coding”, Massachusetts Insti
`tute of Technology, 1991.
`Bergen et al., “Hierarchical Model-Based Motion Estima
`tion”, Proceedings of European Conference on Computer
`Vision, Mar. 23, 1992.
`
`[21]
`[22]
`[5 1]
`[52]
`
`[56]
`
`rm. C16 ..................................................... .. G06K 9/36
`Us. 01. ......................... .. 382/284; 348/588; 382/294
`Field of Search ................................... .. 382/100, 284,
`382/294; 358/450; 348/564, 588; 345/115;
`395/111, 135, 153
`
`Primary Examiner—Andrew Johns
`Attorney, Agent, or F irm—-Wi1]iam J. Burke
`
`[57]
`
`ABSTRACT
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,928,252
`5,034,986
`5,040,067
`5,187,754
`5,258,837
`5,325,449
`5,339,104
`5,416,606
`
`5/1990 Gabbe et a1. ......................... .. 364/519
`7/1991 Kannann et al. ..
`382/1
`8/1991
`2/1993 Currin et al. ..
`11/1993 Gormley ...... ..
`6/1994 Burt et al. ..
`8/1994 Hong ............ ..
`5/1995 Katayama et a1. .................... .. 358/467
`
`GI‘ HER PUBLICATIONS
`
`Michal Irani, “Isolating Multiple 2D Image Motions for
`Image Enhancement and for 3D Motion Analysis”, Hebrew
`University of Jerusalem, 1993.
`Burt et al., “Enhanced Image Capture Through Fusion”,
`International Conference on Computer Vision Proceedings,
`1993.
`Burt et al., “Merging Images Through Pattern Decomposi
`tion”, Applications of Digital Processing V111, SPIE, vol.
`575, pp. 173-181, 1985.
`
`A system for automatically generating a mosaic from a
`plurality of input images. The system sequentially executes
`an image alignment process, an editing process, and a
`combining process such that, from a sequence of images, the
`system automatically produces a seamless mosaic for vari
`ous applications. Illustrative applications for the mosaic
`include: (1) a mosaic based display system including an
`image printing system, (2) a surveillance system and (3) a
`mosaic based compression system. The mosaic based dis
`play system pennits a system user to display, manipulate and
`alter a mosaic. The mosaic based compression system
`exploits the temporal and spatial redundancy in image
`sequences and et?ciently compresses the image information.
`The compression system can be used for compressing image
`information for storage in a storage device or can be used for
`compressing image information for transmission through a
`band-limited transmission channel. The surveillance system
`combines the mosaic construction system, the compression
`system and the display system into a comprehensive system
`for remote motion detection.
`
`30 Claims, 14 Drawing Sheets
`
`IMAGE INPUT
`
`g);
`
`300
`ALIGNMENT
`PROCESS ,J
`
`3 2
`SELECTION
`PROCESS / 0
`
`ALIGNMENT
`INFORMATION
`
`MOSAIC
`COMPOSITION
`PROCESS
`
`306
`/
`
`COMBINATION
`PROCESS
`
`_/‘3(>4
`
`faoa
`
`DYNAMIC
`MOSAIC
`
`Prime Focus Ex 1033-1
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 1 0f 14
`
`5,649,032
`
`INIAGE INPUT
`l
`
`1 00
`
`102
`MOSAIC
`CONSTRUCTION W)
`SYSTEM
`
`V
`
`SURVEILLANCE
`SYSTEM
`
`\108
`
`"gig/Q}?
`COMPRESSION
`SYSTEM
`
`X110
`
`“gag/2%:
`DISPLAY
`SYSTEM
`
`I
`l
`I
`|
`l
`l
`I
`I
`Y
`
`\104
`
`IMAGE
`PRINTING
`SYSTEM
`
`"\106
`
`FIG. 1
`
`Prime Focus Ex 1033-2
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 2 0f 14
`
`5,649,032
`
`t—--+
`
`FIG. 2A
`
`l:
`
`FIG. 20% W /
`
`Prime Focus Ex 1033-3
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15,1997
`
`Sheet 3 of 14
`
`5,649,032
`
`IMAGE INPUT
`
`l
`
`L1
`
`300
`ALIGNMENT
`PROCESS )
`
`‘
`'
`
`IF
`
`=
`
`SELECTION
`PROCESS
`
`A/Q’OZ
`
`V
`
`ALIGNMENT
`INFORMATION
`
`MOSAIC
`COMPOSITION
`PROCESS
`
`I
`
`COMBINATION
`PROCESS -f304
`
`fans
`
`306
`/
`
`I
`
`DYNAMIC
`MOSAIC
`
`FIG. 3
`
`Prime Focus Ex 1033-4
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 4 Of 14
`
`5,649,032
`
`IMAGE
`ALIGNMENT
`PROOESS
`3_0_0
`
`COARSE
`ALIGNMENT
`,
`
`4031
`
`GENERATE IMAGE
`402
`_ PYRAMID FOR
`'
`INPUTIMAGE /) '
`AND MOSAIO
`
`I
`
`404
`SELECT RESOLUTION
`LEvEL FOR OORRELATION I.)
`
`II
`406
`SELECT AREA WITHIN
`SELECTED RESOLUTION /)
`LEvEL OF INPUT IMAGE
`
`L"
`408
`OORRELATE AREA WITH
`SELECTED RESOLUTION f)
`LEvEL OF MOSAIO
`
`MOvE AREA
`RELATIVE
`TO MOSAIC
`
`I
`
`A
`
`412
`
`STORE
`
`ALIGNMENT
`
`PARAMETERS
`
`-
`
`f414
`
`-
`
`/ 422
`
`418
`SELECT NEXT
`RESOLUTION LEvEL
`IN PYRAMIOS -/_
`I
`
`FIG. 4
`
`Prime Focus Ex 1033-5
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Jul. 15, 1997
`
`Sheet 5 0f 14
`
`5,649,032
`
`500
`INPUT
`ALIGNMENT INFORMATION, /)
`MOSAIC AND INPuT IMAGE
`
`SELECTION
`PROCESS
`go_2
`
`V‘
`SELECT
`SELECTION FUNCTION
`AND PARAMETERS
`
`502
`I
`
`4
`
`‘r
`
`;
`
`504
`1 II
`CROPPING
`
`508
`
`II
`MASKING
`
`512
`1 I
`MOSAIC
`TRUNCATION
`
`511
`
`II
`WEIGHTING
`
`506
`II
`\
`SELECT
`REGION OF
`INTEREST
`SIzE AND
`SHAPE
`
`510
`HI
`
`II
`SELECT
`REGION OF
`INTEREST
`SIZE AND
`SHAPE
`
`514
`
`513
`
`II
`SELECT
`WEIGHTS
`
`II
`SELECT
`NUMBER OF
`IMAGES
`INCLUDED
`IN MOSAIC
`
`\
`
`OTHER
`
`II
`
`II
`
`V t
`
`6
`
`II
`
`V
`
`I
`
`518
`APPLY
`SELECTION FUNCTION f
`
`522
`
`R
`
`YES
`
`520
`
`FIG. 5
`
`Prime Focus Ex 1033-6
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 6 0f 14
`
`5,649,032
`
`INPUT
`600
`SELECTION PROCESSED
`MOSAIC AND SELECTION ,)
`PROCESSED INPUT IMAGE
`
`COMBINING
`PROCESS
`g);
`
`II
`SELECT
`COMBINING FUNCTION
`
`602
`I
`
`604
`
`4
`
`I
`
`r
`
`606
`
`608
`
`610
`
`612
`
`614
`
`
`
`\I II MERGING
`
`
`
`‘V FUSION
`
`V INTERZSEATION
`
`EXTRAPOLATION
`
`
`
`7 v ENHANCEMENT CORING OTHER II
`
`
`
`V
`
`V
`
`II
`
`V
`
`V
`
`V
`
`5
`
`YES
`
`MORE
`COMBINING
`?
`
`620
`
`FIG. 6
`
`Prime Focus Ex 1033-7
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Jul. 15,1997
`
`Sheet 7 of 14
`
`5,649,032
`
`750
`
`'
`IMAGE
`SEQUENCE
`
`102
`MOSAIC
`E CONSTRUCTION /J
`SYSTEM
`
`104
`
`705
`v (
`D'SPLAY
`MOSAIC
`BUFFER
`
`‘
`‘V
`IMAGE SELECTION
`PROCESS
`
`L
`
`702
`
`E MOSAIC
`ANALYZER
`
`‘
`
`II
`
`
`
`I‘ ANCILLARY J6
`
`712
`
`IMAGE
`INFORMATION
`
`'
`
`=
`-__->
`
`I,
`IMAGE COMBINING
`PROCESS
`
`704
`y
`
`V
`
`I L
`
`-I I_
`
`_ /“706
`
`DISPLAY
`MOSAIC
`
`‘
`vIEwPORT
`SELECTOR
`
`708
`-—f
`
`I,
`DISPLAY
`MOSAIC EDITOR
`
`710
`'/_
`=
`
`DISPLAY FOR A PORTION I /~ 714
`OF THE MOSAIC
`
`FIG. 7
`
`Prime Focus Ex 1033-8
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 8 of 14
`
`5,649,032
`
`IMAGE
`SUBSEQUENCE
`
`STATIC
`1401
`MOSAIC
`CONSTRUCTION f)
`SYSTEM
`
`L0
`
`802
`7 ‘y
`TRANSFORMATION
`PARAMETERS
`CODER
`
`804
`
`l
`
`MOSAIC
`COMPOSER
`
`7
`
`RESIDUAL
`‘ANALYZER
`806_/
`
`II
`SIGNIFICANCE
`r,’ ANALYZER
`808
`
`‘
`
`RESIDUALS
`810k‘ CODER
`
`CODING
`SYSTEM
`52.6
`
`MOSAIC
`D‘ECODER
`(
`814
`
`DECODING
`SYSTEM
`5.251
`
`V
`
`STORAGE
`
`812
`
`TRANSFORMATION
`PARAMETERS
`OECODER
`L816
`
`MOSAIC
`COMPOSER
`
`820
`
`FIG. 8
`
`RESIDUALS
`DECODE.R
`(
`818
`
`822~1
`
`DI PLAY
`8
`
`Prime Focus Ex 1033-9
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 9 0f 14
`
`5,649,032
`
`% vgPi
`G k
`
`k
`
`k w
`
`INPUT
`IMAGES
`
`O
`
`STATIC
`BACKGROUND
`MOSAIC
`
`7-70
`
`770
`
`RESIDUALS
`
`770
`
`\ 906
`
`FIG. 9
`
`Prime Focus Ex 1033-10
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 10 0f 14
`
`5,649,032
`
`82
`
`A mozwmwmwm 2 <
`
`= 028:
`
`
`
`
`
`32 woz<o_u__zo_w \kézgwmm \, 5&1‘; Emzzgé 5%: p > 22 H 22 #22
`
`EN5<z< M 55.22,‘ “ mwwoomm lwmgz
`
`
`
`u \ < . “ N22
`
`
`
`NNOJ " Q2 82 $2 @282 - LT}? 22
`
`“ 580mg @282 A82 m
`\ A 258 nipzawwwm ................ -2 ...... in ,__ 25% k
`
`
`
`
`, “ E55 855% _ _ w,
`
`@2510 __ .................................. :m T v mwwomzoo
`
`wzaoomo
`
`Q2
`
`
`
`v $825 mwwmwwsmék >52.
`
`(m2 2 £2 22 <
`55% 82K
`
`39 o_<wo_>_ mozmmmmmm K Emmi
`
`
`
`OF G?‘ 0282
`
`. 556
`
`
`95225 +
`
`J \
`
`Prime Focus Ex 1033-11
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 11 0f 14
`
`5,649,032
`
`FIG. 1 1
`
`Prime Focus Ex 1033-12
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`Prime Focus Ex 1033-13
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`US. Patent
`
`Jul. 15, 1997
`
`Sheet 13 of 14
`
`5,649,032
`
`1300
`GENERATE
`PANORAMA /)
`OF IMAGES
`
`SURVElLLANCE
`SYSTEM
`108
`—
`
`V
`CONSTRUCT
`MOSAIC
`
`CAPJYVURE
`NEW IMAGE
`
`V
`COMPARE
`NEw IMAGE
`TO MOSAIC
`
`1302
`/)
`
`1304
`/)
`
`1306
`Ii
`
`1308
`
`NO
`
`YES
`TRANSMIT MOSAIC
`[1310
`AND NEW lMAGE
`(on PORTION THEREOF)"
`
`RECEIVE MOSAIC
`AND NEW IMAGE
`
`/—1312
`
`V
`DISPLAY MOSAIC
`AND NEW IMAGE
`
`[1314
`'
`
`FIG. 13
`
`>
`
`Prime Focus Ex 1033-14
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Jul. 15, 1997
`
`Sheet 14 of 14
`
`5,649,032
`
`1401
`
`j
`
`K '
`
`SuBSEOuENCE
`OF
`IMAGES
`
`I
`
`l
`
`1400
`. BIIIXENSING
`SEO IMAGE 2
`ALIGNMENT
`PROCESS
`
`_ , _
`
`ALIGNMENT
`INFORMATION
`
`IR
`
`V V V v ‘V SELECTION /
`
`
`PROCESS
`‘
`
`COMBlNATION
`PROCESS _/‘M06
`
`MOSAIC
`COMPOSITION
`PROCESS
`
`II
`STATIC
`MOSAIC
`
`FIG. 14
`
`Prime Focus Ex 1033-15
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`1
`SYSTEM FOR AUTOMATICALLY ALIGNING
`IMAGES TO FORM A MOSAIC IlVIAGE
`
`5,649,032
`
`2
`is updated with new content over time, while the content of
`a static mosaic is time invariant.
`More speci?cally, the image alignment process automati
`cally aligns one input image to another input image, an input
`image to an existing mosaic (generated from previously
`occurring input images) such that the input image can be
`added to the mosaic, or an existing mosaic to an input image.
`In each of these instances, the coordinate system of the
`aligned images is either the coordinate system of the input
`image, the coordinate system of the mosaic or an arbitrary
`reference coordinate system. The arbitrary reference coor
`dinate system can be either time invariant or time variant.
`Furthermore, the input image and mosaic can be aligned
`to one another within an image pyramid framework. As
`such, the system converts both the input image and the
`mosaic into Laplacian image pyramids and the alignment
`process is applied to the levels within the respective pyra
`mids. Consequently, the system uses an accurate coarse-to
`?ne image alignment approach that results in sub-pixel
`alignment accuracy. The outcome of the alignment process
`is alignment information that de?nes the transformations
`required to achieve alignment, a dynamic mosaic, between
`the input image and the mosaic such that the mosaic can be
`updated with the image information contained in the input
`image and, in a static mosaic, between the images compris
`ing the mosaic.
`Once the alignment process is complete, the invention
`utilizes a mosaic composition process to construct (or
`update) a mosaic. The mosaic composition process contains
`two processes: a selection process and a combination pro
`cess. The selection process automatically selects images for
`incorporation into the mosaic and may include masking and
`cropping functions. Once the selection process selects which
`image(s), or portions thereof, are to be included in the
`mosaic, the combination process combines the various
`images to form the mosaic. The combination process applies
`various image processing techniques, such as merging,
`fusing, ?ltering, image enhancement, and the like, to achieve
`a seamless combination of the images. The resulting mosaic
`is a smooth image that combines the constituent images such
`that temporal and spatial information redundancy are mini
`mized in the mosaic.
`The automatically generated mosaic ?nds many practical
`uses. Illustrative uses include: (1) a mosaic based display
`system including an image printing system, (2) a surveil
`lance system and (3) a mosaic based compression system.
`The mosaic based display system permits a system user to
`display, manipulate, search and alter a mosaic. The mosaic
`based compression system exploits the temporal and spatial
`redundancy in image sequences and e?iciently compresses
`the image information. The compression system can be used
`for compressing image information for storage in a storage
`device or can be used for compressing image information for
`transmission through a band-limited transmission channel.
`The surveillance system combines the mosaic construction
`system, the compression system and the display system to
`provide a comprehensive system for remote motion detec
`tion.
`
`The invention was made with Government support under
`Contract No. DAAAl5-93-C-0O6l. The Government has
`certain rights in this invention.
`
`BACKGROUND OF THE DISCLOSURE
`
`1. Field of the Invention
`The invention relates systems that process images and,
`more particularly, to systems that automatically generate a
`mosaic of individual images and process the mosaic.
`2. Description of the Prior Art
`Until recently, image processing systems have generally
`processed images, such as frames of video, still
`photographs, and the like, in an individual manner. Each
`individual frame or photograph is typically processed by
`?ltering, warping, and applying various parametric transfor
`mations. After processing. the individual images are com
`bined to form a mosaic, i.e., an image that contains a
`plurality of individual images. Additional image processing
`is performed on the mosaic to ensure that the seams between
`the images are invisible such that the mosaic looks like a
`single large image. The alignment of the images and the
`additional processing to remove seams is typically accom
`plished manually by a technician using a computer
`workstation, i.e., the image alignment and combination
`processes are computer aided. In such computer aided image
`processing systems, the technician manually selects pro
`cessed images, manually aligns those images, and a com
`puter applies various image combining processes to the
`images to remove any seams or gaps between the images.
`Manipulation of the images is typically accomplished using
`various computer input devices such as a mouse, trackball,
`keyboard and the like. Unfortunately, such manual mosaic
`construction is time consuming and costly. Furthermore,
`manual mosaic construction cannot be accomplished in
`real-time, i.e., the mosaic cannot be constructed as the
`images are generated by an image source such as a video
`camera. Consequently, the images in a real-time image
`generation system are stored for subsequent computer aided
`processing at a later time.
`Since manually generated mosaics are costly, such mosa
`ics do not ?nd much practical use except in publishing
`applications and image retouching systems. Although mosa
`ics hold much promise, the lack of an automatic mosaic
`construction system has limited their use.
`Therefcne, a need exists in the art for a system that
`automatically generates a mosaic from either pre-existing
`images or in real-time as the images are generated by an
`image source. Furthermore, a need exists for systems that
`utilize the automatically generated mosaic in various prac
`tical applications.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`SUMMARY OF THE INVENTION
`
`The present invention overcomes the disadvantages here
`tofore associated with the prior art by automatically gener
`ating a mosaic from a plurality of input images. Speci?cally,
`the invention is a mosaic construction system that sequen
`tially executes an image alignment process and a mosaic
`composition process such that, from a sequence of images,
`the system automatically produces a mosaic for utilization
`by various applications. The invention is capable of con
`structing both dynamic and static mosaics. A dynamic
`mosaic includes imagery that is time variant, e.g., the mosaic
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The teachings of the present invention can be readily
`understood by considering the following detailed descrip
`tion in conjunction with the accompanying drawings, in
`which:
`FIG. 1 shows a block diagram of a system for automati
`cally constructing a mosaic and various systems for utilizing
`the mosaic in image compression, surveillance, and image
`display;
`
`65
`
`Prime Focus Ex 1033-16
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`3
`FIG. 2A, 2B and 2C respectively depict a schematic
`rendering of batch mosaic construction sequencing, recur
`sive mosaic construction sequencing and hierarchical
`mosaic construction sequencing;
`FIG. 3 depicts a detailed block diagram of a dynamic
`mosaic construction system;
`FIG. 4 depicts a ?ow chart of an image alignment process
`that aligns an input image to a mosaic of images;
`FIG. 5 depicts a ?ow chart of a selection process that
`selects the image(s), or portions thereof, for inclusion in the
`mosaic;
`FIG. 6 depicts a ?ow chart of a combination process that
`combines the aligned image with the mosaic;
`FIG. 7 depicts a block diagram of a mosaic based display
`system;
`FIG. 8 depicts a block diagram of a static mosaic based
`compression system;
`FIG. 9 depicts a schematic rendering of the relationship
`between input images, background information, and residu
`als for the static mosaic based compression system of FIG.
`8;
`FIG. 10 depicts a block diagram of a dynamic mosaic
`based compression system;
`FIG. 11 depicts a schematic rendering of a temporal
`pyramid;
`FIG. 12 depicts a block diagram of a surveillance system;
`FIG. 13 depicts a ?ow chart of the operative process of the
`surveillance system of FIG. 12; and
`FIG. 14 depicts a detailed block diagram of a static
`mosaic construction system.
`To facilitate understanding, identical reference numerals
`have been used, where possible, to designate identical
`elements that are common to the ?gures.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`DETAlLED DESCRIPTION
`Generally, a mosaic is a data structure that melds visual
`information from a set of images taken at a plurality of time
`instants, viewpoints, or ?elds of view. The various images
`are aligned and combined to form, for example, a panoramic
`view of a scene as a single still image. Importantly, a mosaic
`is not limited to a combination of distinct images, but may
`also be a combination of mosaics. The invention is a system
`that automatically forms a mosaic from a plurality of images
`for utilization by various application systems. The invention
`includes one or more of these application systems.
`There are two types of mosaics: dynamic mosaics and
`static mosaics. Dynamic mosaics are time variant in that
`they are recursively updated over time with new imagery. As
`such, a series of input images (e.g., video frames) are
`combined one at a time with the other images in the series
`to produce the dynamic mosaic. Thereafter, the system
`aligns and combines each new input image with the previous
`mosaic, i.e., the mosaic is updated.
`In a static mosaic, the content of the mosaic is time
`invariant. For example, a series of existing input images are
`divided into subsequences of images. The individual images
`in each subsequence are aligned with one another and
`combined into a static mosaic. The static mosaic is not
`updated with new information, i.e., the content of the mosaic
`is static.
`In each of these two types of mosaics, the mosaics are
`constructed with reference to an arbitrary reference coordi
`nate system which can be either time variant or time
`invariant. In other words, the coordinate system can be
`
`45
`
`50
`
`55
`
`65
`
`5,649,032
`
`4
`either altered while the mosaic is constructed or it can be
`?xed over time. The arbitrary reference coordinate system
`can be selected as the coordinate system of the latest input
`image of a dynamic mosaic, the coordinate system of the
`mosaic in a dynamic mosaic, the coordinate system of one
`of the images in a static mosaic, an arbitrary ?xed coordinate
`system that is not related to the images or the mosaics, or it
`can be an arbitrary time variant coordinate system. Through
`out the remainder of this discussion, the general term
`reference coordinate system is used, this general term is
`intended to encompass any form of reference coordinate
`system.
`FIG. 1 depicts a block diagram of a mosaic based image
`processing system 100 that contains a mosaic construction
`system 102 as well as one or more application systems 104,
`106, 108, 110 for a mosaic. Speci?cally, the application
`systems include a mosaic based display system 104 which
`may include a mosaic based printing system 106, a mosaic
`based surveillance system 108, and a mosaic based com
`pression system 110. The following disclosure ?rst provides
`an overview of the mosaic construction system and its
`interaction with the application systems. Thereafter, the
`disclosure describes, in a series of distinct subsections, the
`details of the mosaic construction system for constructing
`both static and dynamic mosaics and each application sys
`tem.
`The mosaic construction system 102 has as an input a
`series of images. These images can be a video frame
`sequence, a series of satellite infra-red or visible
`photographs, a sequence of aerial photographs, or any other
`series of images that, when aligned with one another, form
`a mosaic. The images may be provided in real-time, i.e., the
`images may be provided directly from, for example, a video
`camera. In operation, the mosaic construction system 102
`automatically aligns the input images and combines them to
`form a mosaic.
`More speci?cally, depending upon the application for the
`mosaic, the system can construct either a dynamic mosaic or
`a static mosaic. In addition, the system can utilize any
`reference coordinate system while constructing a mosaic.
`Furthermore, in composing the mosaic from the aligned
`images, the system may use any one of a number of image
`fusing, merging, ?ltering, and averaging processes to best
`produce a seamless mosaic. Also, as shown in FIG. 2, the
`system forms the mosaic using various input image and
`mosaic construction sequencing processes including batch
`(FIG. 2A), recm'sive (FIG. 2B), and hierarchical (FIG. 2C)
`sequencing.
`Returning to FIG. 1, the mosaic is used by one or more of
`the application systems. For example, the mosaic based
`display system 104 utilizes special mosaic storage and
`manipulation techniques that enable a system user to rapidly
`have a mosaic displayed upon a computer monitor and
`enable the user to manipulate the displayed mosaic. The
`mosaic based display removes the image source (e.g.,
`camera) motion ?om the mosaic image, i.e., the image is
`stabilized. A user may select to leave some camera move
`ment in the displayed image to provide a sense of the
`camera’s movement, but entirely remove high frequency
`jitter. Such a display is especially useful when displaying
`aerial photographs taken from, for example, a helicopter.
`The moving display provides the user with a sense of motion
`over the depicted terrain without any camera jitter.
`Furthermore, to provide additional information to a user, this
`display system merges other data into the mosaic display.
`This other data may be numerical or graphical terrain
`elevation information, motion vectors, graphical indicators
`
`Prime Focus Ex 1033-17
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`10
`
`25
`
`35
`
`40
`
`45
`
`5
`showing the most recent image, and the like. The details of
`this system are described below with respect to FIG. 7.
`In addition to displaying the mosaic, or portions thereof
`on a computer monitor, this mosaic based display system
`may optionally be used in conjunction with an image
`printing system 106. The printing system is capable of
`generating high-resolution color or monochrome still
`images of the mosaic or any portion thereof.
`The surveillance system 108 uses a mosaic for detection
`of motion, for example, for security purposes or for motion
`detection on a battle?eld. Generally, a panoramic view of an
`area of interest is captured by, for example, a high-resolution
`video camera. The mosaic construction system 102 gener
`ates a single high-resolution mosaic of the entire panoramic
`view. This mosaic is used as a reference view. Subsequent
`frames captured by the video camera are compared to the
`reference view. Any movement in the reference is detected
`as residuals from comparing the new image to the reference
`mosaic. The details of the surveillance system are provided
`with respect to FIGS. 12 and 13.
`The mosaic based compression system 110 uses the
`mosaic as a basis for e?iciently compressing image infor
`mation for transmission through a low bandwidth transmis—
`sion channel. An alternative of the compression system is
`used to compress image information for e?icient storage
`within a storage medium such as a disk drive or compact
`disk. To achieve e?icient compression, the compression
`system exploits the large spatial and temporal correlation’s
`that exist in sequences of images. The details of the mosaic
`based compression system are provided below in connection
`with FIGS. 8, 9, 10, and 11.
`Next. the mosaic construction system is described in
`detail. This description is followed by a detailed description
`of each of the illustrative applications for a mosaic con
`structed by the mosaic construction system.
`I. MOSAIC CONSTRUCTION SYSTEM 102
`To best understand the diiferences between construction
`of a dynamic mosaic and construction of a static mosaic,
`each construction process is described separately. First the
`dynamic mosaic construction process is described (FIGS. 3,
`4, 5, and 6) and then a static mosaic construction process
`(FIG. 14) is described.
`A. Dynamic Mosaic Construction 301
`FIG. 3 depicts a ?ow chart of the operation of a dynamic
`mosaic construction system 301. The system contains two
`sequentially executed processes; namely, an image align
`ment process 300 and a mosaic composition process 303.
`The mosaic composition process 303 further contains two
`processes; namely, a selection process 302 and a combina
`tion process 304. The alignment process 300 aligns the input
`image with a previously constructed mosaic (if any), sup
`plied via line 306. If a mosaic does not currently exist, i.e.,
`the input image is the ?rst image of a sequence of images,
`then the ?rst image is used as a previously constructed
`mosaic. In effect, the ?rst image becomes the mosaic for the
`second image. In generating a dynamic mosaic, typically, the
`system uses recursive mosaic construction sequencing.
`Thus, the next image in the sequence is aligned with the
`current mosaic (a mosaic constructed of preceding images in
`a series of images). Alignment is accomplished by aligning
`the input image with the mosaic. i.e., the mosaic and input
`images are aligned with the reference coordinate system.
`The aligning process is accomplished by warping the images
`to one another. The image alignment process generates, for
`each image. the necessary alignment information to align the
`input image such that its image information can be com
`bined with the existing mosaic. The alignment information
`
`5,649,032
`
`6
`de?nes the a?ine transformation required to align. for
`example, a given input image with the reference coordinate
`system.
`If hierarchical mosaic construction sequencing is used, or
`if sub-mosaics are desired, the image alignment process
`generates alignment information for each of the sub-mosaics
`as well as for each of the constituent images of these
`subrnosaics.
`Within the mosaic composition process 303, the selection
`process 302 selects which portions of the input image and
`current mosaic will be used to form an updated mosaic. The
`updated mosaic is a mosaic including at least a portion of the
`latest input image and at least a portion of the previous
`mosaic. The selection process may perform masking or
`cropping to limit the size of the mosaic. It may also perform
`image selection in which untimely (“old”) images are
`removed from the mosaic.
`The combination process 304 combines the aligned
`images to form an updated mosaic. The combination process
`performs one or more of the following processes to seam
`lessly combine the input image with the mosaic: merging,
`fusion, interpolation. extrapolation, enhancement, coring, as
`well as other conventional image combining processes. The
`output is an updated dynamic mosaic containing seamlessly
`combined image information from the latest input image.
`To perform the alignment and ultimately combine the
`input image with the mosaic. the resolution of the input
`image can be transformed to the resolution of the mosaic or
`vice versa. However, it is best to generate a conventional
`Laplacian image pyramid of the input image and also of the
`entire mosaic, i.e., the system 102 becomes multi
`resolutional. As such, alignment is performed on a course
`to-?ne basis such that an initial alignment is performed
`using a relatively low resolution level in each of the pyra
`mids and then sequentially higher resolution pyramid levels
`are used to perfect the alignment. Such a pyramid frame
`work improves the speed at which an alignment can be
`accomplished as well as the accuracy of the alignment.
`Throughout the remainder of the discussion of the mosaic
`construction system and its applications, it is assumed that
`the input image and the mosaic are pyramids. However,
`those skilled in the art should realize that the pyramid
`framework is not necessary to practice the invention and that
`simple resolution transformation could be used instead of a
`pyramid framework.
`Furthermore, since the reference coordinates to which the
`latest image, the mosaic, or both are warped to can be
`arbitrarily selected, the display system is ?exible. For
`example, in an airline display application, the system
`displays, at a central location on a cathode ray tube (CRT ),
`the latest image captured by a nose mounted video camera.
`The remainder of the mosaic trails from that central area to
`the bounds of the display area. As such, the pilot can view
`what is in front of the aircraft, e.g., an approaching airport,
`as well as what had just previously passed through carnera’s
`?eld of view. Thus, the pilot can see a historical record of the
`aircraft’s approach to the airport. The importance of the
`ability to freely select a reference coordinate system shall
`become more apparent when the various applications for the
`mosaic are described.
`FIG. 4 depicts a detailed ?ow chart of the alignment
`process 300. Generally speaking, prior art systems have
`accomplished image alignment to align two sequential video
`frames by correlating the image information contained in
`each frame. Such a video frame alignment system is dis
`closed in a US. patent application entitled “SYSTEM AND
`METHOD FOR ELECTRONIC IMAGE
`
`50
`
`55
`
`65
`
`Prime Focus Ex 1033-18
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`7
`SI‘ABlLIZATION", ?led Oct. 28, 1994, accorded Ser. No.
`08/328,783, and herein incorporated by reference. The
`present invention uses an alignment system very similar to
`the alignment system disclosed in this patent application,
`except that the alignment system for the present invention
`aligns an input image to an entire mosaic rather than to a
`single previous input image. Nonetheless the alignmen
`concepts are similar.
`'
`Speci?cally, the alignment process ?rst conducts a coarse
`alignment to generally align the latest image with the
`existing mosaic. Thereafter, a coarse-to-?ne alignment pro
`cess aligns the lowest resolution level of the pyramid for the
`input image with respect to a comparable resolution level of
`the pyramid for the current mosaic (assuming a recursive
`mosaiciconstruction sequencing and the mosaic coordinate
`system forms the reference coordinate system). To achieve
`alignment of comparable resolutions, the lowest level of one
`pyramid may be aligned with higher level of the other
`Pyrami¢
`To begin aligmnent, step 401, coarsely aligns the input
`image and the mosaic. The coarse alignment is accom
`plished using information from image pyramids of the input
`image and the mosaic. Therefore, at step 402, the process
`generates an image pyramid for both the input image and the
`mosaic. Information from the pyramids are carried along
`line 403 to the coarse alignment step. Typically, the syste