United States Patent [19]
`Moed et al.
`
`[54] SYSTEM AND METHOD FOR SEGMENTING
`IMAGE REGIONS FROM ASCENE LIKELY
`TO REPRESENT PARTICULAR OBJECTS IN
`THE SCENE
`
`[75] Inventors: Michael C. Moed, Roswell; Ralph N.
`Crabtree, Atlanta, both of Ga.
`[73] Assignee: NCR Corporation, Dayton, Ohio
`
`[21] Appl. No.: 08/998,211
`[22] Filed:
`Dec. 24, 1997
`Related U.S. Application Data
`[60] Provisional application No. 60/050,972, Jun. 19, 1997.
`[51] Int. Cl." .............................. G06K 9/00; G06K 9/46;
`H04N 9/47
`[52] U.S. Cl. .......................... 382/103; 382/164; 38.2/236;
`348/143
`[58] Field of Search ..................................... 382/103, 164,
`382/165, 236, 257; 348/143, 152, 155,
`169, 700, 701, 590, 591, 592
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`1/1985 Tisdale et al. .......................... 382/103
`4,497,065
`7/1991 Karmann et al. ....................... 382/103
`5,034,986
`3/1993 Grimaldi et al. .
`... 348/587
`5,194,941
`5,301.239 4/1994 Toyama et al. ...
`... 382/104
`5,359,363 10/1994 Kuban et al. .....
`... 382/103
`5,677,733 10/1997 Yoshimura et al. ..
`... 348/362
`5,896,176 4/1999 Das et al. ..........
`... 348/416
`5,912,980 6/1999 Hunke ...........
`... 382/103
`6/1999 Parulski et al. ......................-º 348/239
`5,914,748
`OTHER PUBLICATIONS
`Pattern Recognition, “A Survey on Image Segmentation”,
`Fu et al., vol. 13, pp. 3–16, 1981.
`Pattern Recognition, “A Review on Image Segmentation
`Techniques”, Palet al., vol. 26, No. 9, pp. 1277–1294, 1993.
`
`US006141433A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,141,433
`Oct. 31, 2000
`
`Proc. 11” IAPR International Conference on Pattern Rec
`ognition,
`“Color Segmentation
`Using Perceptual
`Attributes”, Tseng et al., vol. III, pp. 228–231, 1992.
`IEEE, “Fusion of Color and Edge Information for Improved
`Segmentation and Edge Linking”, Saber et al., pp.
`2176—2179, 1996.
`Pattern Recognition, “A segmentation Algorithm for Color
`Images”, Schettini, Letters 14, pp. 499–506, 1993.
`IEEE 10” Conf. Pattern Recognition, “Color Segmentation
`by Hierarchical Connected Components Analysis with
`Image Enhancement by Symmetric Neighborhood Filters”,
`pp. 796–802, 1990.
`
`Primary Examiner—Amelia Au
`Assistant Examiner—Mehrdad Dastouri
`Attorney, Agent, or Firm—Needle & Rosenberg
`[57]
`ABSTRACT
`
`A system and method for extracting image information from
`a video frame for regions of a the video frame that likely are
`objects of interest in a scene. An initial region set is
`generated by comparing luminance image information and
`color image information of a video frame with luminance
`image information and color image information of a back
`ground image for the scene. A high confidence region set is
`generated comprising regions from the initial based upon
`edge information of the regions and edge information in the
`background image. A final region set is generated by com
`bining one or more regions in the high confidence region set
`if such combinations satisfy predetermined criteria, includ
`ing size, region proximity and morphological region dila
`tion.
`
`38 Claims, 9 Drawing Sheets
`
`400
`
`430
`
`EDGE 3ETERMINATION AND
`REGION CONFIDENCE GENERATION
`
`GENERATE BACKGROUND EDGE IMAGE BY
`EXTRACTING EDGES FROM BACKGROUND
`|MAGE WHENEVER THE BACKGROUND
`|MAGE IS NEW OR IS UPDATED
`
`410
`
`EXTRACTEDGES FROM EACH
`REGION IN THE INITIAL REGION SET
`
`420
`
`
`
`GENERATE A CONFEDENCE WALUE FOR EACH REGION IN NITIAL
`REGION SET BY EXAMINING EACH PIXELIN A REGION AND
`COMPARING |T WITH A CORRESPOND|NG Pl).ELIN BACKGROUND
`EDGE IMAGE FOREACH PIXELINEACH REGION,
`A. REDUCE CONFIDENCEVALUE OF THE REGION IF THE
`PixEL IN THE REGION AND CORRESPONDING PAEXELIN
`THE BACKGROUND MAGE BOTH REPRESENT AN EDGE.
`... INCREASE GONFIDENCE WALUE OF THE REGION IF THE
`PXELIN THE REGION REPRESENTS AN EDGE AND
`CORRESPONDING PIXEL IN BACKGROUND IMAGE
`DOES NOT,
`... INCREASE CONFIDENCE WALUE OF THE REG|ON IF THE
`PIXELIN THE REGION DOES NOT REPRESENT AN EDGE
`AND CORRESPONDING PIXEL N BACKGROUND IMAGE
`DOES REPRESENT AN EDGE,
`
`COMPARE CONFIDENCE WALUE FOR EACH
`REGION WITH PREDETERMINED CONFIDENCE
`THRESHOLD-DISCARD THOSE BELOW THRESHOLD,
`REMAINING REGONS ARE HIGH CONFIDENCE REGION SET
`
`440
`
`Legend3D, Inc. Ex. 2025-0001
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 1 of 9
`
`6,141,433
`
`150
`
`1 — — — — — — — — — — — — — — — — — — — — — —l
`
`FIG. 2
`
`COLOR IMAGE
`FOR CURRENT
`FRAME
`
`
`
`SEGMENTATION
`PARAMETERS
`
`
`
`BACKGROUND
`|MAGE
`
`
`
`200
`
`REGION
`SEGMENTER
`
`PREVIOUS FRAME
`REGION INFORMATION
`
`REGIONS AND
`THEIR DESCRIPTORS
`
`Legend3D, Inc. Ex. 2025-0002
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 2 of 9
`
`6,141,433
`
`FIG. 3
`
`~~
`
`
`
`
`
`|NITIAL REGION EXTRACTION
`TO CREATE INITIAL REGION SET
`OF REGIONS THAT POTENTIALLY
`REPRESENT OBJECTS TO TRACK
`
`300
`
`
`
`
`
`EDGE DETERMINATION AND REGION
`CONFIDENCE GENERATION TO
`CREATE A HIGH CONFIDENCE REGION
`SET BASED ON EDGE INFORMATION
`
`400
`
`MERGE REGIONS IN HIGH CONFIDENCE
`REGION SETBASEDUPONPREDETERMINED H 500
`CRITERIA TO FORM FINAL REGION SET
`
`OUTPUT REGIONS OF FINAL
`REGION SET AND THEIR DESCRIPTORS
`
`600
`
`Legend3D, Inc. Ex. 2025-0003
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 3 of 9
`
`6,141,433
`
`FIG. 4
`
`|NITIAL REGION EXTRACTION
`
`300
`2^
`
`GENERATE DIFFERENCE IMAGES FOR EACH
`OF THE LUMINANCE (Y) AND COLOR (UAND V)
`|MAGE COMPONENTS BETWEEN CURRENT
`VIDEO FRAME AND BACKGROUND IMAGE
`
`
`
`310
`
`
`
`ADJUST VALUES OF PIXELS IN
`LUMINANCE (Y) DIFFERENCE IMAGE
`BASED UPON VALUES OF CORRESPONDING
`PIXELS IN THE BACKGROUND IMAGE
`
`320
`
`
`
`
`
`SCALE THE ADJUSTED Y DIFFERENCE IMAGE AND
`THE U AND V DIFFERENCE IMAGES AND FORM
`COMPOSITE IMAGE WITH A PREDETERMINED
`EMPHASIS ON THEY DIFFERENCE IMAGE
`
`
`
`330
`
`
`
`
`
`
`
`COMPARE COMPOSITE IMAGE WITH A
`PREDETERMINED IMAGE DIFFERENCE THRESHOLD
`TO EXTRACT REGIONS OF SIGNIFICANT DIFFERENCE
`AND GENERATE A BINARY INTEREST IMAGE
`
`
`
`340
`
`GENERATE GRAY INTEREST IMAGE BY MASKING
`THE Y|MAGE COMPONENT FOR THE CURRENT FRAME
`
`350
`
`EXTRACT REGIONS OF SIM|LAR GRAY
`LEVEL TO FORM INITIAL REGION SET
`
`360
`
`Legend3D, Inc. Ex. 2025-0004
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 4 of 9
`
`6,141,433
`
`400
`
`430
`
`FIG. 5
`
`EDGE DETERMINATION AND
`REGION CONFIDENCE GENERATION
`
`GENERATE BACKGROUND EDGE IMAGE BY
`EXTRACTING EDGES FROM BACKGROUND
`|MAGE WHENEVER THE BACKGROUND
`|MAGE IS NEW OR IS UPDATED
`
`410
`
`EXTRACT EDGES FROM EACH
`REGION IN THE INITIAL REGION SET
`
`420
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GENERATE A CONFIDENCE VALUE FOR EACH REGION |N||N|TIAL
`REGION SET BY EXAMINING EACH PIXEL IN A REGION AND
`COMPARING |T WITH A CORRESPONDING PIXEL IN BACKGROUND
`EDGE IMAGE. FOR EACH PIXELINEACH REGION,
`A. REDUCE CONFIDENCEVALUE OF THE REGION IF THE
`PIXEL IN THE REGION AND CORRESPONDING PIXEL IN
`THE BACKGROUND IMAGE BOTH REPRESENT AN EDGE.
`. INCREASE CONFIDENCE VALUE OF THE REGION IF THE
`PIXEL IN THE REGION REPRESENTS AN EDGE AND
`CORRESPONDING PIXELIN BACKGROUND IMAGE
`DOES NOT.
`. INCREASE CONFIDENCE VALUE OF THE REGION IF THE
`PIXEL IN THE REGION DOES NOT REPRESENT AN EDGE
`AND CORRESPONDING PIXEL IN BACKGROUND IMAGE
`DOES REPRESENT AN EDGE.
`
`
`
`
`
`
`
`
`
`COMPARE CONFIDENCE VALUE FOR EACH
`REGION WITH PREDETERMINED CONFIDENCE
`THRESHOLD – DISCARD THOSE BELOW THRESHOLD,
`REMAINING REGIONS ARE HIGH CONFIDENCE REGION SET
`
`
`
`440
`
`Legend3D, Inc. Ex. 2025-0005
`IPR2016-01243
`
`

`

`U.S. Patent
`Oct. 31, 2000
`FIG. 6
`
`Sheet 5 of 9
`
`6,141,433
`
`MERGE AND FINAL REGION DETERMINATION
`
`500
`2^
`
`COMPARE EACH REGION IN HIGH CONFIDENCE REGION SET WITH
`EVERY OTHER REGION IN THE HIGH CONFIDENCE REGION SET
`
`510
`
`
`
`
`
`WOULD
`COMBINATION CREATE
`A REGION GREATER THAN
`MAXIMUM SIZE LIMITS
`º
`
`
`
`
`
`
`
`514
`
`
`
`
`
`NO
`
`
`
`ARE THE
`TWO REGIONS
`SUFFICIENTLY CLOSE
`|N PROXIMITY
`7
`
`YES
`
`COMBINABLE
`
`NO
`
`NOT
`COMBINABLE
`
`516—MORPHOLOGICALLY DILATEEACH REGION
`
`
`
`
`
`518
`
`
`
`DO DILATED
`REGIONS OVERLAP
`7
`
`NO
`
`NOT
`COMBINABLE
`
`519
`
`RETAIN AREA OF INTERSECTION
`
`Legend3D, Inc. Ex. 2025-0006
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 6 of 9
`
`6,141,433
`
`FIG. 7
`
`
`
`
`
`COMPARE LIST OF PAIRWISE
`COMBINABLE REGIONS TO
`FORM GROUPINGS OF REGIONS
`BASED UPON A COMMON REGION
`
`520
`
`
`
`MERGE REGIONS IN
`EACH GROUPING TO
`FORM SINGLE LARGER
`REGIONS OF THE
`FINAL REGION SET
`
`
`
`
`
`
`
`530
`
`Legend3D, Inc. Ex. 2025-0007
`IPR2016-01243
`
`

`

`6,141,433
`
`
`
`Legend3D, Inc. Ex. 2025-0008
`IPR2016-01243
`
`

`

`U.S. Patent
`Oct. 31, 2000
`FIG
`... 10
`
`
`
`Sheet 8 of 9
`
`6,141,433
`
`FIG
`. 11
`
`
`
`Legend3D, Inc. Ex. 2025-0009
`IPR2016-01243
`
`

`

`Oct. 31, 2000
`U.S. Patent
`FIG. 12
`
`
`
`Sheet 9 of 9
`
`6,141,433
`
`Legend3D, Inc. Ex. 2025-0010
`IPR2016-01243
`
`

`

`1
`SYSTEM AND METHOD FOR SEGMENTING
`IMAGE REGIONS FROM ASCENE LIKELY
`TO REPRESENT PARTICULAR OBJECTS IN
`THE SCENE
`
`This application claims the benefit of U.S. Provisional
`Application Ser. No. 60/050,972 filed Jun. 19, 1997.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention generally relates to video tracking
`systems, and more particularly, to a system and method for
`extracting regions of a video frame for a scene that likely
`represent particular types objects, such as people.
`2. Description of the Prior Art
`In video identification or tracking systems, it is necessary
`to isolate and/or extract those portions of a video frame
`image that represent items or objects of interest. Many prior
`art systems utilize complex model information representing
`features of the objects to be identified and/or tracked.
`However, using such complex comparison schemes at an
`early stage of a identification or tracking process does not
`yield optimal results.
`
`SUMMARY OF THE INVENTION
`Briefly, the present invention is directed to a system and
`method for extracting regions from a video frame that
`represent objects of interest with respect to a background
`image for the scene. A first set of regions, called an initial
`region set, is generated based upon differences between
`luminance information for the video frame and luminance
`information for a background image of the scene. A second
`set of regions, called a high confidence region set, is
`generated from the first set of regions based upon edge
`information for regions in the first set and edge information
`for the background image. A third set of regions, called the
`final region set, is generated from the second set of regions
`by combining regions in the second set with each other if
`resulting combined regions satisfy predetermined criteria,
`including size, proximity and other features.
`The objects and advantages of the present invention will
`become more readily apparent when reference is made to the
`following description taken in conjunction with the accom
`panying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram showing the basic hardware
`components of the image region segmentation system
`according to the present invention.
`FIG. 2 is a diagram showing how the region segmentation
`process interfaces with other information in a tracking
`system.
`FIG. 3 is a flow chart generally showing the region
`segmentation process according to the present invention.
`FIG. 4 is a flow chart showing the initial region extraction
`portion of the region segmentation process.
`FIG. 5 is a flow chart showing the edge determining and
`region confidence generation portion of the region segmen
`tation process.
`FIGS. 6 and 7 show a flow chart for the merge and final
`region determination portion of the region segmentation
`process.
`FIG. 8 is a pictorial diagram showing a background
`image.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,141,433
`
`2
`FIG. 9 is a pictorial diagram showing image for a video
`frame.
`FIG. 10 is a pictorial diagram showing a binary interest
`image generated by the region segmentation process of the
`present invention for the images shown in FIGS. 8 and 9.
`FIG. 11 is a pictorial diagram of regions in an initial
`region set for the image information of the video frame
`shown in FIG. 9.
`FIG. 12 is a pictorial diagram of a background edge image
`for the background image shown in FIG. 8.
`FIG. 13 is a pictorial diagram of regions extracted from
`the image information for the video frame shown in FIG. 9,
`and forming the final region set.
`DETAILED DESCRIPTION OF THE
`INVENTION
`FIG. 1 illustrates the hardware components of a system
`which performs region segmentation according to the
`present invention. The hardware components are standard
`off-the-shelf components, and include one or more video
`cameras 110, one or more frame grabbers 120, and a
`processor 130, such as a personal computer (PC), having a
`memory 135 which stores software programs for controlling
`the processor 130. The combination of the video camera 110
`and frame grabber 120 may collectively be referred to as an
`“image acquisition module” 145. The frame grabber 120
`receives a standard video signal output by the video camera
`110, such as a RS-170, NTSC, CCIR, or PAL video signal,
`which can be monochrome or color. In a preferred
`embodiment, the video camera(s) 110 are mounted or posi
`tioned to view a selected viewing area or scene 150 of
`interest, such as a checkout lane in a retail establishment, an
`automated teller machine (ATM), an entrance, an exit, or any
`other localized area where people may move and/or interact
`with devices or other people.
`The frame grabber 120 is embodied, for example, by a
`Meteor"M Color Frame Grabber, available from Matrox. The
`frame grabber 120 operates to convert the analog video
`signal into a sequence or stream of digital video frame
`images that are stored within the memory 135, and pro
`cessed by the processor 130. For example, in one
`implementation, the frame grabber 120 converts the video
`signal into a 2×2 sub-sampled NTSC image which is 320x
`240 pixels (whereas the normal NTSC image is 640×480) or
`a 2×2 sub-sampled PAL color image which is 384×288
`pixels (whereas the normal PAL image is 768×576), or in
`general a WXL image defining a single video frame of video
`information. A variety of other digital image formats and
`resolutions are also suitable, as will be recognized by one of
`ordinary skill in the art. Each pixel of a video frame has a
`predetermined bit resolution, such as 8 bits, and color data
`may be used to increase system performance.
`The region segmentation finctionality is preferably imple
`mented by way of a software program that may be installed
`in the memory 135 from another memory/storage medium,
`such as a CD-ROM, floppy disk(s), hard disk, etc., or it may
`be downloaded from an internet site, or from an on-line
`service for installation into the memory 135. The image
`segmentation program comprises a plurality of executable
`instructions which, when stored in the memory 135, cause
`the processor 130 to perform the processes depicted in FIGS.
`3–7. However, one with ordinary skill in the art will appre
`ciate that the region segmentation functionality could be
`implemented by one or more application specific integrated
`circuits, a digital signal processor or other suitable signal
`processing architectures.
`
`Legend3D, Inc. Ex. 2025-0011
`IPR2016-01243
`
`

`

`6,141,433
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`25
`
`3
`The region segmentation process is represented by the
`region segmenter shown at reference numeral 200 in FIG. 2.
`The region segmenter 200 utilizes color image information
`to extract the regions of interest. The inputs to the region
`segmenter are image information for the current video
`frame, predetermined and adjustable segmentation param
`eters (such as thresholds, etc.), and image information for a
`background image. The output of the region segmenter 200
`is a set of regions and their descriptors (described in more
`detail hereinafter). The background image is generated by
`one of many processes known in the art, and represents the
`current or updated background image for the scene.
`The region segmentation process described hereinafter is
`tailored to extract regions from an image that are likely to
`represent to people within the scene. However, one with
`ordinary skill in the art will appreciate that the region
`segmentation process can be tailored to extract regions that
`represent other objects within a scene, such as vehicles,
`particular classes of people, etc.
`To extract regions potentially representing people within
`the scene, the region segmentation process is based on
`several basic ideas in order to segment regions that represent
`people. First, people moving through a scene tend to have
`different color attributes that the background image for the
`scene. In areas where the background image is dark, it is
`more difficult to detect these color differences than where the
`background image is light. Second, people tend to create
`new edges in the scene, and to obscure edges in the
`background image. Third, shadows and highlights are
`largely due to intensity changes in the gray component of a
`color image, and therefore, do not create significant color
`differences, nor do they obscure edges in the background
`image. Finally, regions that are preliminarily determined to
`represent a person that share a large, common perimeter,
`belong to the same person.
`Turning to FIG. 3, the overall architecture of the region
`segmentation process is described. The region segmentation
`process comprises three processing portions: an initial
`region extraction process 300; an edge determination and
`region confidence generation process 400; and a region
`merge and final region determination process 500. After final
`region determination, the regions and their descriptors are
`output in step 600.
`The initial region extraction process 300 involves gener
`ating a first set of regions called an initial region set, by
`comparing image information with image information of a
`background image for the scene. The output of the initial
`region extraction process 300 is an initial region set com
`prising one or more regions that preliminarily or potentially
`50
`represent an object (such as a person) in the scene. As will
`explained hereinafter, the initial region set can be generated
`from both luminance and color image information, from
`luminance information only (such as for non-color video
`signals) and from color information only.
`The edge determination and region confidence generation
`process 400 compares edge information for the regions in
`the initial region set with edge information of the back
`ground image to generate a second set of regions called a
`high confidence region. Those regions from the initial region
`set which have edge information that does not correspond to
`edge information in the background image tend to be
`retained in the high confidence region set, as do those
`regions that obscure edges in the background image.
`The region merge and final region determination process
`500 combines one or more regions in the high confidence
`region set if the resulting combined regions satisfy prede
`
`55
`
`60
`
`65
`
`4
`termined criteria. The combined regions make up a third set
`of regions called the final region set. The location informa
`tion and image information for the regions in the final region
`set are output in step 600.
`Thus, in brief summary, the region segmentation process
`involves steps of:
`(a) generating a first set of regions based upon differences
`between image information for the video frame and
`image information for a background image of the
`Scene;
`(b) generating a second set of regions from the first set of
`regions based upon edge information for regions in the
`first set and edge information for the background
`image; and
`(c) generating a third set of regions from the second set of
`regions by combining regions in the second set with
`each other if resulting combined regions satisfy prede
`termined criteria.
`Referring to FIG. 4, the initial region extraction process
`300 will be described. The following description is directed
`to a preferred embodiment in which the luminance and color
`image information portions of a color video signal are
`analyzed. For example, if the PAL color coding system is
`used, then the luminance image information is the Y com
`ponent of a YUV image and the color image information
`consists of the U component and the V component of the
`YUV image. Other color coding systems are also suitable for
`use in the region segmentation process.
`In step 310, difference images are generated for both the
`luminance image and the color difference image, between
`the video frame and the background image. An example of
`a background image is shown in FIG. 8 and an example of
`a image for a video frame is shown in FIG. 9. The view of
`the scene is from video camera mounted above the scene
`being monitored. FIG. 9 shows an image for a video frame
`in which there are objects 601, 602, 603, 604 and 605, such
`as people, to be detected and tracked.
`In step 310, three difference images are generated, a Y
`difference image, U difference image and V difference
`image. The difference image for each signal component is
`generated by computing the absolute value of the difference,
`or distance, between pixels in the video frame and corre
`sponding pixels in the background image. Specifically, for
`each of the Y, U and V component images (also known as
`bands), the value of each pixel in the background image is
`subtracted from the value of the corresponding pixel for the
`component image. The absolute value of the result of the
`subtraction of the pixel values is stored at the corresponding
`location in the difference image for that component image.
`Next, in step 320, the Y difference image is adjusted based
`upon values of corresponding pixels in the background
`image. Specifically, each pixel in the Y difference image is
`multiplied by a factor which is proportional to a luminance
`intensity of the corresponding pixel in the background
`image. The factor is greater than or equal to 1. In particular,
`the factor is greater than 1 when the corresponding pixel in
`the background image is dark with respect to a threshold and
`is equal to 1 when the corresponding pixel in the background
`image is light with respect to a threshold. The new Y
`difference image is called an adjusted Y difference image.
`The Y difference image is adjusted in this way to accentuate
`small luminance differences in a dark background image.
`This helps to locate objects in the video frame that are only
`slightly darker than the background environment. This step
`is not necessary and it there may be circumstances in which
`it is not required.
`In step 330, a composite image is formed. The adjusted Y
`difference image and the U and V difference images are
`
`Legend3D, Inc. Ex. 2025-0012
`IPR2016-01243
`
`

`

`6,141,433
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`5
`scaled to equalize their respective pixel range values. The U
`and V difference images tend to have a compressed range of
`pixel values, e.g., the gray values only range from 100–156,
`instead of 0–255 (the full range). Therefore, small differ
`ences in the gray values of the U and V images for the video
`frame and the U and V images for the background image are
`equally as important as large differences in the gray value in
`the Y image component for the video frame and the back
`ground image (which tends to contain a much broader range
`of gray values). Also, there may be some range differences
`between the U and V images. To accentuate the small
`differences in the U and V image components with respect
`to the Y image components, several steps are performed.
`First, the range of gray values for the U and V difference
`images is examined. The difference image with the smaller
`range of values is scaled to the same range as the difference
`image with the larger range. Scaling is performed by mul
`tiplying each pixel value of the first image by an appropriate
`constant that yields a resulting scaled image with approxi
`mately the same range as the other difference image. This
`scaled difference image and the non-scaled difference image
`are combined to form a combined UV difference image by
`either taking the maximum value of each pixel for the two
`difference images, or by summing each pixel in the two
`images. There are other ways to combine the two difference
`images as is well known in the art.
`Next, the range of gray values for the Y difference image
`and the combined UV difference image is examined. Again,
`the difference image with the smaller range of values,
`usually the combined UV difference image, is scaled to the
`same range as the difference image with the larger range of
`values by multiplying each pixel in the difference image
`with the smaller range by an appropriate constant. The
`appropriate scaled and non-scaled versions of the Y differ
`ence image and the combined UV difference image are
`combined to form a composite image.
`The adjusted Y difference image is given a weight in the
`composite image based upon a predetermined emphasis
`factor. The predetermined emphasis factor is one of the
`adjustable segmentation parameters and it is used to control
`the emphasis of either the color differences or intensity
`differences between the video frame and the background
`image in the segmentation process. A greater weight is given
`to the adjusted Y difference image to emphasize intensity
`differences in the composite image, and a lesser weight is
`given to emphasize color differences in the composite
`image. Thus, appropriate scaled and non-scaled versions of
`a weighted adjusted Y difference image is combined with the
`combined UV difference image. The combined image is
`formed by taking the pixel-by-pixel maximum of the two
`images, or by taking the sum of the two images, or by some
`other suitable means well known in the art.
`Controlling the emphasis factor allows for compensation
`for variable scene conditions. Scenes that are shadowy or
`that are subject to glare generally experience these effects
`mostly in the luminance band of the image. For these scenes
`it may be appropriate to give the Y difference image a
`smaller weight and accentuate the color difference images.
`Typical weight values for this case may be 0.4 for the Y
`difference image, and 0.6 for the color difference images. On
`the other hand for dark scenes that have little lighting, color
`differences may be the result of scene noise, so it is appro
`priate to more highly weight the Y difference image than the
`color differences images. Typical weight values for this case
`may be 0.8 for the Y difference image, and 0.2 for the color
`difference images.
`In step 340, the composite image is compared, pixel by
`pixel, with a predetermined image difference threshold. If
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`the pixel has a value greater than the threshold, the corre
`sponding pixel in the binary interest image is set to “TRUE’.
`Otherwise, the corresponding pixel is set to “FALSE”.
`Therefore, those regions in the composite image that are
`greater than the predetermined image difference threshold
`are regions of significant image difference, and make up an
`image called the binary interest image. FIG. 10 illustrates
`the binary interest image corresponding to the image infor
`mation for the background image of FIG. 8 and the video
`frame of FIG. 9.
`In step 350, a gray interest image is generated by masking
`the luminance image information, the Y component image,
`of the video frame with the binary interest image. The gray
`interest image includes gray scale areas of interest.
`The masking process operates as follows. The binary
`interest image contains pixels of two values, TRUE and
`FALSE. If a given pixel in the binary interest image is
`labeled TRUE, the gray value at the same (x,y) location in
`the luminance image is copied to the same location in the
`gray interest image. If a given pixel in the binary interest
`images is labeled FALSE, a value indicating “no interest” is
`written to the corresponding location in the gray interest
`image. Pixels in the gray interest image that are assigned the
`“no interest” value are not considered for further processing.
`Finally, in step 360, the initial region set is created by
`extracting from the gray interest image those regions that are
`connected and have a similar gray level. This is accom
`plished with a gray level connected component extraction
`process. There are many such processes known in the art.
`Small gray level regions are filtered out, and not considered
`as part of the initial region set. FIG. 11 shows an example of
`the initial region set for the image information of the video
`frame shown in FIG. 9.
`The region segmentation process according to the present
`invention is described as being performed on luminance and
`color image information for a video frame and a background
`image. It is envisioned, however, that the initial region set is
`generated based solely on luminance image information or
`based solely on color image information. If initial region
`extraction is performed based on luminance image informa
`tion only, then the segmentation process is suitable for use
`on non-color video signals, though it may be performed on
`the luminance image component of a color video signal.
`In the case where the first set of regions is generated based
`only on luminance image information, the initial region
`extraction procedure is slightly different than that described
`above. A luminance difference image is generated based
`upon the luminance image information for the video frame
`and the luminance image information for the background
`image. Next, the values of the pixels of the luminance
`difference image are adjusted based upon corresponding
`values of pixels in the background image to generate an
`adjusted luminance difference image. Again, this adjustment
`step is optional. The adjusted (or non-adjusted) luminance
`difference image is then compared with a predetermined
`image difference threshold to generate a binary interest
`image. The gray interest image is generated by masking the
`luminance image information of the video frame with the
`binary interest image. Finally, regions that are connected and
`have similar gray levels are extracted from the gray interest
`image to form the first set of regions.
`In the case where initial region extraction is performed on
`color image information only, the procedure involves gen
`erating a color difference image based upon image informa
`tion for the video frame and image information for the
`background image. The color difference image is compared
`with a predetermined image difference threshold to generate
`
`Legend3D, Inc. Ex. 2025-0013
`IPR2016-01243
`
`

`

`6,141,433
`
`7
`a binary interest image. Agray interest image is generated by
`masking color image information of the video frame with
`the binary interest image. Those regions in the gray interest
`image that are connected and have similar gray levels are
`extracted and form the first set of regions.
`Turning now to FIG. 5, the edge determination and region
`confidence generation process will be described. In step 410,
`the background edge image is generated by extracting edges
`(edge information) from the background image. There are
`many ways well known in the art to extract edges from an
`image, such as the well known Sobel process and the
`Roberts process. This step is performed whenever the back-
`ground image is new, or when any part of the background
`image is updated. Weak edges, those less than a predeter-
`mined edge threshold, are discarded. FIG. 12 illustrates an
`example of a background edge image for the background
`image shown in FIG. 8.
`In step 420, edge information is extracted from each
`region in the first set of regions. This occurs by extracting
`edge information from those areas of the gray interest image
`corresponding to the regions in the first set. Weak edges are
`discarded from the resulting edge image.
`Next, in step 430, a confidence value is generated for each
`region in the first set of regions by examining each pixel in
`the edge image for a region and comparing it with a
`corresponding pixel in the background edge image. The
`confidence value is dependent on whether the pixels of a
`region and corresponding pixels in the background image
`represent edge information.
`The confidence value is adduced as each pixel of a region
`is examined. Specifically, the confidence value of the region
`is reduced when a pixel in the region and a corresponding
`pixel in the background image both represent an