US6625310B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Video segmentation using statistical pixel modeling
Assignee: Avigilon Fortress Corp
•
Filing: 2001-03-23
•
Granted: 2003-09-23
•
Expires: 2021-03-23
Abstract
Abstract A method for segmenting video data into foreground and background portions utilizes statistical modeling of the pixels. A statistical model of the background is built for each pixel, and each pixel in an incoming video frame is compared with the background statistical model for that pixel. Pixels are determined to be foreground or background based on the comparisons.
Inventors
- 👤 Alan J. Lipton
- 👤 Mark Allmen
- 👤 Niels Haering
- 👤 William Severson
- 👤 Thomas M. Strat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 12:47
CPC Classifications
G; G08; G08B; G08B13/00; G08B13/18; G08B13/189; G08B13/194; G08B13/196; G06; G06T; G06T7/00; G06T7/10; G06T7/11; G06T7/143; G06T7/194; G06T7/20; G06T7/277; G06V; G06V10/00; G06V10/20; G06V10/26; G06V10/28; G06V20/00; G06V20/50; G06V20/52; G08B31/00; G06T2207/00; G06T2207/10; G06T2207/10016; G06T2207/30; G06T2207/30241; G06V2201/00; G06V2201/01
Claims Analysis
Total Claims: 65
Claim 1
Independent Claim
99 words
A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from an input video stream; executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of: aligning the frame with a scene model; and updating a background statistical model; and finalizing the background statistical model; executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of: labeling each region of the frame; and performing spatial/temporal filtering of the regions of the frame.
Claim 2
Dependent Claim
99 words
A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from an input video stream; executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of: aligning the frame with a scene model; and updating a background statistical model; and finalizing the background statistical model; executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of: labeling each region of the frame; and performing spatial/temporal filtering of the regions of the frame.
Claim 3
Dependent Claim
19 words
A computer system comprising: a computer; and a computer-readable medium containing software implementing the method of claim 1 .
Claim 4
Dependent Claim
12 words
A computer-readable medium comprising software implementing the method of claim 1 .
Claim 5
Dependent Claim
40 words
The method according to claim 1 , wherein the step of updating a background statistical model comprises the steps of: compiling values corresponding to the regions of the frames; and computing a standard deviation for each region of the frames.
Claim 6
Dependent Claim
51 words
The method according to claim 1 , wherein the step of finalizing the background statistical model comprises the step of: for each region of the frames, determining a statistical mode based on the compiled values; and assigning the statistical mode of each region as its value in the background statistical model.
Claim 7
Dependent Claim
44 words
The method according to claim 1 , wherein the step of labeling each region of the frame comprises the steps of: determining whether or not the region matches the background statistical model; and assigning a label based on the result of the determining step.
Claim 8
Dependent Claim
92 words
The method according to claim 6 , wherein the step of determining comprises the step of determining whether a value of the region of the frame falls within some range about a corresponding value of the region in the background statistical model; and wherein the step of assigning a label comprises the steps of: assigning a first label if the value of the region of the frame does fall within the range; and assigning a second label if the value of the region of the frame does not fall within the range.
Claim 9
Dependent Claim
19 words
The method according to claim 7 , wherein said first label is background and said second label is foreground.
Claim 10
Dependent Claim
158 words
The method according to claim 6 , wherein the step of determining comprises the steps of: determining whether a value of the region of the frame falls within a first range about a corresponding value of the region in the background statistical model; and if the value of the region of the frame does not fall within the first range, determining if it falls within a second range about said corresponding value of the region in the background statistical model; and wherein the step of assigning a label comprises the steps of: assigning a first label if the value of the region of the frame falls within the first range; assigning a second label if the value of the region of the frame does not fall within the first range and does lie within the second range; and assigning a third label if the value of the region of the frame does not fall within the second range.
Claim 11
Dependent Claim
25 words
The method according to claim 9 , wherein said first label is background, said second label is foreground, and said third label is definite foreground.
Claim 12
Dependent Claim
85 words
The method according to claim 1 , wherein the step of labeling each region of the frame comprises the steps of: determining whether or not the region matches the background statistical model, comprising the step of performing determinations as to whether or not a value of the region of the frame falls within each of an arbitrary number of ranges about a corresponding value of the region in the background statistical model ; and assigning a label based on the result of the determining step.
Claim 13
Dependent Claim
36 words
The method according to claim 1 , wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame: performing neighborhood filtering; and performing spatial filtering, temporal filtering, or a combination thereof.
Claim 14
Dependent Claim
44 words
The method according to claim 12 , wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.
Claim 15
Dependent Claim
60 words
The method according to claim 13 , wherein said step of performing morphological erosions and dilations comprises the steps of: performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded; following the step of performing n erosions, performing n dilations; and following the step of performing n dilations, performing a second number, m, of dilations.
Claim 16
Dependent Claim
114 words
The method according to claim 12 , wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P i , not labeled background: determining a location, P m , in the scene model corresponding to P i ; determining a neighborhood of regions, P′ m around P m ; determining if any of the P′ m matches P i ; if any of the P′ m matches P i , determining a neighborhood of regions P′ i around P i ; determining if any of the P′ i matches P m ; and if any of the P′ m matches P i , relabeling P i background.
Claim 17
Dependent Claim
61 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model; labeling the regions of the frame; and performing spatial/temporal filtering.
Claim 18
Dependent Claim
61 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model; labeling the regions of the frame; and performing spatial/temporal filtering.
Claim 19
Dependent Claim
19 words
A computer system comprising: a computer; and a computer-readable medium containing software implementing the method of claim 16 .
Claim 20
Dependent Claim
12 words
A computer-readable medium comprising software implementing the method of claim 16 .
Claim 21
Dependent Claim
36 words
The method according to claim 16 , wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame: performing neighborhood filtering; and performing spatial filtering, temporal filtering, or a combination thereof.
Claim 22
Dependent Claim
44 words
The method according to claim 19 , wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.
Claim 23
Dependent Claim
60 words
The method according to claim 20 , wherein said step of performing morphological erosions and dilations comprises the steps of: performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded; following the step of performing n erosions, performing n dilations; and following the step of performing n dilations, performing a second number, m, of dilations.
Claim 24
Dependent Claim
114 words
The method according to claim 19 , wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P i , not labeled background: determining a location, P m , in the scene model corresponding to P i ; determining a neighborhood of regions, P′ m around P m ; determining if any of the P′ m matches P i ; if any of the P′ m matches P i , determining a neighborhood of regions P′ i around P i ; determining if any of the P′ i matches P m ; and if any of the P′ m matches P i , relabeling P i background.
Claim 25
Dependent Claim
91 words
The method according to claim 16 , wherein said step of building a background statistical model comprises the steps of: for each region of the frame, performing the steps of: determining if the background statistical model is mature and stable; if the background statistical model is mature and stable, determining if a value of the region matches a corresponding value of the background statistical model; and if the value of the region matches the value of the background statistical model, updating the background statistical model using the value of the region.
Claim 26
Dependent Claim
89 words
The method according to claim 23 , wherein the step of determining if the background statistical model is mature and stable comprises the steps of: determining if the background statistical model is mature, and if it is not, updating the background statistical model using the value of the region; if the background statistical model is determined to be mature, determining if the background statistical model is stable; if the background statistical model is determined not to be stable, updating the background statistical model using the value of the region.
Claim 27
Dependent Claim
44 words
The method according to claim 24 , wherein each step of updating the background statistical model using the value of the region comprises the steps of: updating a running mean value for the region; and updating a running standard deviation value for the region.
Claim 28
Dependent Claim
44 words
The method according to claim 23 , wherein the step of updating the background statistical model using the value of the region comprises the steps of: updating a running mean value for the region; and updating a running standard deviation value for the region.
Claim 29
Dependent Claim
26 words
The method according to claim 23 , wherein said step of building a background statistical model further comprises the step of finalizing the background statistical model.
Claim 30
Dependent Claim
122 words
The method according to claim 16 , wherein said step of labeling the regions of the frame comprises, for each region of the frame, the steps of: making determinations as to the maturity and stability of the background statistical model for that region; determining if a value of the background statistical model for that region matches a value of the scene model for that region; determining if a value of the region matches the value of the scene model for that region; and determining to what extent the value of the region matches the value of the background statistical model for that region; and wherein, based on the results of the making and determining steps, a label is assigned to the region.
Claim 31
Dependent Claim
64 words
The method according to claim 28 , wherein the step of making determinations as to the maturity and stability of the background statistical model comprises the steps of: determining whether or not the background statistical model is mature; determining whether or not the background statistical model is stable; and if the background statistical model is not stable, determining if it was ever previously stable.
Claim 32
Dependent Claim
67 words
The method according to claim 29 , wherein the step of determining if the background statistical model is stable is executed only if the background statistical model is determined to be mature; and wherein, if the background statistical model is determined not to be mature, the step of determining if a value of the region matches the value of the scene model for that region is executed.
Claim 33
Dependent Claim
45 words
The method according to claim 29 , wherein, if the background statistical model is determined to be stable, the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region is executed.
Claim 34
Dependent Claim
75 words
The method according to claim 29 , wherein, if the step of determining if the background statistical model was ever previously stable returns an affirmative result, the step of determining if a value of the region matches the value of the scene model for that region is executed; and wherein, if the step of determining if the background statistical model was ever previously stable returns a negative result, then the region is labeled definite foreground.
Claim 35
Dependent Claim
50 words
The method according to claim 28 , wherein if the step of determining if a value of the region matches the value of the scene model for that region returns an affirmative result, the region is labeled background, and if it returns a negative result, the region is labeled foreground.
Claim 36
Dependent Claim
118 words
The method according to claim 28 , wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns an affirmative result, the step of determining to what extent the value of the region matches the value of the background statistical model for that region is executed; and wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns a negative result, then the step of determining if a value of the region matches the value of the scene model for that region is executed.
Claim 37
Dependent Claim
120 words
The method according to claim 28 , wherein the step of determining to what extent the value of the region matches the value of the background statistical model for that region comprises the steps of: determining if the value of the region matches the value of the background statistical model for that region; if the step of determining if the value of the region matches the value of the background statistical model for that region, labeling the region background; and if the step of determining if the value of the region matches the value of the background statistical model for that region returns a negative result, determining if the value of the region falls far from the background statistical model.
Claim 38
Dependent Claim
89 words
The method according to claim 35 , wherein the step of determining if the value of the region falls far from the background statistical model comprises the step of performing a threshold comparison; and wherein: if the step of determining if the value of the region falls far from the background statistical model returns an affirmative result, labeling the region definite foreground, and if the step of determining if the value of the region falls far from the background statistical model returns a negative result, labeling the region foreground.
Claim 39
Dependent Claim
66 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model and a secondary statistical model; labeling the regions of the frame; and performing spatial/temporal filtering.
Claim 40
Dependent Claim
66 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model and a secondary statistical model; labeling the regions of the frame; and performing spatial/temporal filtering.
Claim 41
Dependent Claim
19 words
A computer system comprising: a computer; and a computer-readable medium containing software implementing the method of claim 37 .
Claim 42
Dependent Claim
12 words
A computer-readable medium comprising software implementing the method of claim 37 .
Claim 43
Dependent Claim
36 words
The method according to claim 37 , wherein the step of spatial/temporal filtering comprises the steps of, for each region of the frame: performing neighborhood filtering; and performing spatial filtering, temporal filtering, or a combination thereof.
Claim 44
Dependent Claim
44 words
The method according to claim 40 , wherein the step of performing spatial filtering, temporal filtering, or a combination thereof comprises the step of performing morphological erosions and dilations, wherein the morphological erosions and dilations are performed in two dimensions or in three dimensions.
Claim 45
Dependent Claim
60 words
The method according to claim 41 , wherein said step of performing morphological erosions and dilations comprises the steps of: performing a number, n, of erosions, wherein any region labeled definite foreground is not eroded; following the step of performing n erosions, performing n dilations; and following the step of performing n dilations, performing a second number, m, of dilations.
Claim 46
Dependent Claim
114 words
The method according to claim 40 , wherein the step of performing neighborhood filtering comprises the steps of, for each region of the frame, P i , not labeled background: determining a location, P m , in the scene model corresponding to P i ; determining a neighborhood of regions, P′ m around P m ; determining if any of the P′ m matches P i ; if any of the P′ m matches P i , determining a neighborhood of regions P′ i around P i ; determining if any of the P′ i matches P m ; and if any of the P′ m matches P i , relabeling P i background.
Claim 47
Dependent Claim
118 words
The method according to claim 37 , wherein said step of building a background statistical model comprises the steps of: for each region of the frame, performing the steps of: determining if the background statistical model is mature and stable; if the background statistical model is mature and stable, determining if a value of the region matches a corresponding value of the background statistical model; if the value of the region matches the value of the background statistical model, updating the background statistical model using the value of the region; and if the value of the region does not match the value of the background statistical model, updating the secondary statistical model using the value of the region.
Claim 48
Dependent Claim
89 words
The method according to claim 44 , wherein the step of determining if the background statistical model is mature and stable comprises the steps of: determining if the background statistical model is mature, and if it is not, updating the background statistical model using the value of the region; if the background statistical model is determined to be mature, determining if the background statistical model is stable; if the background statistical model is determined not to be stable, updating the background statistical model using the value of the region.
Claim 49
Dependent Claim
44 words
The method according to claim 45 , wherein each step of updating the background statistical model using the value of the region comprises the steps of: updating a running mean value for the region; and updating a running standard deviation value for the region.
Claim 50
Dependent Claim
44 words
The method according to claim 44 , wherein the step of updating the background statistical model using the value of the region comprises the steps of: updating a running mean value for the region; and updating a running standard deviation value for the region.
Claim 51
Dependent Claim
105 words
The method according to claim 44 , wherein said step of updating the secondary statistical model comprises the steps of: determining if the secondary statistical model is mature; if the secondary statistical model is not mature, updating the secondary statistical model using the value of the region; if the secondary statistical model is mature, determining if the secondary statistical model is stable; if the secondary statistical model is not stable, updating the secondary statistical model using the value of the region; and if the secondary statistical model is stable, replacing the background statistical model for the region with the secondary statistical model for the region.
Claim 52
Dependent Claim
26 words
The method according to claim 44 , wherein said step of building a background statistical model further comprises the step of finalizing the background statistical model.
Claim 53
Dependent Claim
122 words
The method according to claim 37 , wherein said step of labeling the regions of the frame comprises, for each region of the frame, the steps of: making determinations as to the maturity and stability of the background statistical model for that region; determining if the value of a background statistical model for that region matches a value of the scene model for that region; determining if a value of the region matches the value of the scene model for that region; and determining to what extent the value of the region matches the value of the background statistical model for that region; and wherein, based on the results of the making and determining steps, a label is assigned to the region.
Claim 54
Dependent Claim
64 words
The method according to claim 50 , wherein the step of making determinations as to the maturity and stability of the background statistical model comprises the steps of: determining whether or not the background statistical model is mature; determining whether or not the background statistical model is stable; and if the background statistical model is not stable, determining if it was ever previously stable.
Claim 55
Dependent Claim
67 words
The method according to claim 51 , wherein the step of determining if the background statistical model is stable is executed only if the background statistical model is determined to be mature; and wherein, if the background statistical model is determined not to be mature, the step of determining if a value of the region matches the value of the scene model for that region is executed.
Claim 56
Dependent Claim
45 words
The method according to claim 51 , wherein, if the background statistical model is determined to be stable, the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region is executed.
Claim 57
Dependent Claim
75 words
The method according to claim 51 , wherein, if the step of determining if the background statistical model was ever previously stable returns an affirmative result, the step of determining if a value of the region matches the value of the scene model for that region is executed; and wherein, if the step of determining if the background statistical model was ever previously stable returns a negative result, then the region is labeled definite foreground.
Claim 58
Dependent Claim
50 words
The method according to claim 50 , wherein if the step of determining if a value of the region matches the value of the scene model for that region returns an affirmative result, the region is labeled background, and if it returns a negative result, the region is labeled foreground.
Claim 59
Dependent Claim
118 words
The method according to claim 50 , wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns an affirmative result, the step of determining to what extent the value of the region matches the value of the background statistical model for that region is executed; and wherein, if the step of determining if a value of the background statistical model for that region matches a value of the scene model for that region returns a negative result, then the step of determining if a value of the region matches the value of the scene model for that region is executed.
Claim 60
Dependent Claim
120 words
The method according to claim 50 , wherein the step of determining to what extent the value of the region matches the value of the background statistical model for that region comprises the steps of: determining if the value of the region matches the value of the background statistical model for that region; if the step of determining if the value of the region matches the value of the background statistical model for that region, labeling the region background; and if the step of determining if the value of the region matches the value of the background statistical model for that region returns a negative result, determining if the value of the region falls far from the background statistical model.
Claim 61
Dependent Claim
89 words
The method according to claim 57 , wherein the step of determining if the value of the region falls far from the background statistical model comprises the step of performing a threshold comparison; and wherein: if the step of determining if the value of the region falls far from the background statistical model returns an affirmative result, labeling the region definite foreground, and if the step of determining if the value of the region falls far from the background statistical model returns a negative result, labeling the region foreground.
Claim 62
Dependent Claim
119 words
A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from an input video stream; executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of: aligning the frame with a scene model; and updating a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions; finalizing the background statistical model; and executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of: labeling each region of the frame; and performing spatial/temporal filtering of the regions of the frame.
Claim 63
Dependent Claim
119 words
A two-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from an input video stream; executing a first-pass method for each frame of the frame sequence, the first-pass method comprising the steps of: aligning the frame with a scene model; and updating a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions; finalizing the background statistical model; and executing a second-pass method for each frame of the frame sequence, the second-pass method comprising the steps of: labeling each region of the frame; and performing spatial/temporal filtering of the regions of the frame.
Claim 64
Dependent Claim
81 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions; labeling the regions of the frame; and performing spatial/temporal filtering.
Claim 65
Dependent Claim
81 words
A one-pass method of video segmentation, for differentiating between foreground and background portions of video, comprising the steps of: obtaining a frame sequence from a video stream; and for each frame in the frame sequence, performing the following steps: aligning the frame with a scene model; building a background statistical model, the background statistical model comprising values corresponding to regions of frames of the frame sequence and variances for the regions; labeling the regions of the frame; and performing spatial/temporal filtering.
References Cited (Backward Citations)
US4764971A
Cited
US4949389A
Cited
US5448651A
Cited
US5048095A
Cited
US5519789A
Cited
US5586200A
Cited
US5671294A
Cited
US5724456A
Cited
US5802203A
Cited
US5696551A
Cited
US5768413A
Cited
US6078619A
Cited
US6337917B1
Cited
US6008865A
Cited
US5764306A
Cited
US6249613B1
Cited
US6195458B1
Cited
US6396876B1
Cited
US6058210A
Cited
US5990955A
Cited
US6349113B1
Cited
US6393054B1
Cited
US6278466B1
Cited
US6404925B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-09-22 | 2007-03-24 | 2007-09-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-09-22 | 2011-03-24 | 2011-09-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-09-22 | 2015-03-24 | 2015-09-23 | $7700.00 | Window Closed / Lapsed |