Patent US5724435A successfully refreshed from Google Patents.
US5724435A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital filter and method of tracking a structure extending in three spatial dimensions
Assignee: Hewlett Packard Development Co LP
•
Filing: 1996-12-18
•
Granted: 1998-03-03
•
Expires: 2016-12-18
Abstract
Abstract A tracking technique which tracks a structure in three-dimensional data is disclosed. The tracking technique uses a geometric shape to model the structure to be tracked. Tracking is achieved by altering the orientation (and perhaps scale) of the geometric shape at a given three-dimensional point until it best fits the structure being tracked. Using this best fit information, a subsequent point within the structure being tracked can be identified. The tracking continues by thereafter altering the orientation (and perhaps scale) of the geometric shape at or near the subsequent point until a best fit is identified. The invention can be implemented as a digital filter, a tracking system or a method.
Inventors
- 👤 Thomas Malzbender
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:48
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/0002; G06T7/0012; G06T5/00; G06T5/80; G06T7/10; G06T7/11; G06T7/70; G06T2207/00; G06T2207/10; G06T2207/10072; G06T2207/10088; G06T2207/30; G06T2207/30004; G06T2207/30101
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
99 words
A digital filter having six-degrees of freedom, said filter operates to filter three-dimensional data having varying intensity, said digital filter comprising: a set of filter coefficients arranged in a predetermined geometric shape; sampling means for sampling the three-dimensional data at three-dimensional locations of each of the filter coefficients to produce a filter response for a given orientation; and transformation means for altering at least the orientation and scale of the geometric shape of said set of filter coefficients about a central three-dimensional location in the three-dimensional data to identify at least an orientation corresponding to a maximized filter response.
Claim 2
Dependent Claim
99 words
A digital filter having six-degrees of freedom, said filter operates to filter three-dimensional data having varying intensity, said digital filter comprising: a set of filter coefficients arranged in a predetermined geometric shape; sampling means for sampling the three-dimensional data at three-dimensional locations of each of the filter coefficients to produce a filter response for a given orientation; and transformation means for altering at least the orientation and scale of the geometric shape of said set of filter coefficients about a central three-dimensional location in the three-dimensional data to identify at least an orientation corresponding to a maximized filter response.
Claim 3
Dependent Claim
32 words
A finite impulse response filter as recited in claim 1, wherein said transformation means further translates the geometric shape of the filter coefficients from a base location to the central three-dimensional location.
Claim 4
Dependent Claim
39 words
A finite impulse response filter as recited in claim 1, wherein the filter is used to track a structure through the three-dimensional data, and wherein the central three-dimensional location is an approximate medial axis of the structure being tracked.
Claim 5
Dependent Claim
117 words
A spatial filter including having six-degrees of freedom, said filter operates to filter three-dimensional data having varying intensity, said spatial filter comprising: a first tier including a first geometric shape having a first set of filter coefficients, and a second geometric shape having a second set of filter coefficients; a second tier including a third geometric shape having a third set of filter coefficients, and a fourth geometric shape having a fourth set of filter coefficients; means for altering the six-degrees of freedom of said filter, wherein said first and second geometric shapes being in a first plane, the third and fourth geometric shapes being in a second plane, and the first and second planes are parallel.
Claim 6
Dependent Claim
117 words
A spatial filter including having six-degrees of freedom, said filter operates to filter three-dimensional data having varying intensity, said spatial filter comprising: a first tier including a first geometric shape having a first set of filter coefficients, and a second geometric shape having a second set of filter coefficients; a second tier including a third geometric shape having a third set of filter coefficients, and a fourth geometric shape having a fourth set of filter coefficients; means for altering the six-degrees of freedom of said filter, wherein said first and second geometric shapes being in a first plane, the third and fourth geometric shapes being in a second plane, and the first and second planes are parallel.
Claim 7
Dependent Claim
17 words
A spatial filter as recited in claim 4, wherein said first and second geometric shapes are coplanar.
Claim 8
Dependent Claim
62 words
A spatial filter as recited in claim 4, wherein said first set of filter coefficients are arranged in a first two-dimensional circle with radius r, and said second set of filter coefficients are arranged in a second two-dimensional circle with radius 1/r, where r is a positive real number, and wherein the first and second two-dimensional circles are concentric with one another.
Claim 9
Dependent Claim
19 words
A spatial filter as recited in claim 4, wherein the first and second geometric shapes are substantially the same.
Claim 10
Independent Claim
133 words
A method for tracking a three-dimensional structure defined within a data set including data representing three spatial dimensions, using an image processing device, said method comprising: selecting a digital filter having first and second tiers which are each at least two-dimensional and are separated along a third independent spatial dimension; approximating a medial axis point in the three spatial dimensions for the structure to be tracked; using the image processing device to compare the digital filter with the data set and ascertain a rotational orientation of the digital filter about at least one of the three spatial dimensions, that causes the digital filter to correspond to the three-dimensional structure; and approximating a next medial axis point for the structure based on the previous medial axis point and the orientation of the digital filter.
Claim 11
Independent Claim
133 words
A method for tracking a three-dimensional structure defined within a data set including data representing three spatial dimensions, using an image processing device, said method comprising: selecting a digital filter having first and second tiers which are each at least two-dimensional and are separated along a third independent spatial dimension; approximating a medial axis point in the three spatial dimensions for the structure to be tracked; using the image processing device to compare the digital filter with the data set and ascertain a rotational orientation of the digital filter about at least one of the three spatial dimensions, that causes the digital filter to correspond to the three-dimensional structure; and approximating a next medial axis point for the structure based on the previous medial axis point and the orientation of the digital filter.
Claim 12
Independent Claim
176 words
A method for tracking a three-dimensional structure defined within a data set including data representing three spatial dimensions, using an image processing device, said method comprising: selecting a geometric shape that occupies at least two independent dimensions; approximating a medial axis point in the three spatial dimensions for the structure to be tracked; obtaining a best fit between the structure and the geometric shape by three-dimensional processing using at least one of adjusting size of the geometric shape in at least two independent dimensions to thereby cause the shape to correspond to the structure, and also ascertaining a rotational orientation of the shape around one of the at least two independent dimensions such that the shape corresponds to the structure, or adjusting position of the geometric shape within the three spatial dimensions and also ascertaining a rotational orientation of the shape around at least two independent axes such that it corresponds to the structure; and approximating a next medial axis point for the structure based on the best fit and the orientation of the geometric shape.
Claim 13
Independent Claim
176 words
A method for tracking a three-dimensional structure defined within a data set including data representing three spatial dimensions, using an image processing device, said method comprising: selecting a geometric shape that occupies at least two independent dimensions; approximating a medial axis point in the three spatial dimensions for the structure to be tracked; obtaining a best fit between the structure and the geometric shape by three-dimensional processing using at least one of adjusting size of the geometric shape in at least two independent dimensions to thereby cause the shape to correspond to the structure, and also ascertaining a rotational orientation of the shape around one of the at least two independent dimensions such that the shape corresponds to the structure, or adjusting position of the geometric shape within the three spatial dimensions and also ascertaining a rotational orientation of the shape around at least two independent axes such that it corresponds to the structure; and approximating a next medial axis point for the structure based on the best fit and the orientation of the geometric shape.
Claim 14
Dependent Claim
56 words
A method according to claim 9, wherein obtaining a best fit includes: applying a digital filter to the data represented by the geometric shape; and readjusting size of the digital filter along each of two independent dimensions of the digital filter and repeatedly comparing the filter to the structure while varying size to optimize filter response.
Claim 15
Dependent Claim
41 words
A method according to claim 10, wherein obtaining a best fit also includes: readjusting a position of the digital filter in three-dimensional space and repeatedly comparing the filter to the structure while varying the position and size to optimize filter response.
Claim 16
Dependent Claim
51 words
A method according to claim 9, wherein obtaining a best fit includes: applying a digital filter to the data represented by the geometric shape; and readjusting a position of the digital filter in three-dimensional space and repeatedly comparing the filter to the structure while varying the position to optimize filter response.
Claim 17
Dependent Claim
48 words
A method according to claim 9, wherein obtaining a best fit also includes readjusting the digital filter in at least five degrees of freedom, including in position along three spatial dimensions of the data and around two rotational axes of the geometric shape, to obtain the best fit.
Claim 18
Dependent Claim
47 words
A method according to claim 9, wherein approximating a next medial axis point includes: determining a projected axis point out from the best fit a distance in response to the orientation; and approximating the next medial axis point for the structure based on the projected axis point.
Claim 19
Dependent Claim
51 words
A method according to claim 9, wherein approximating the next medial axis point includes: approximating a temporary medial axis point in the data; performing a constrained search in the immediate vicinity of the temporary medial axis point; and selecting as a result of the constrained search the next medial axis point.
Claim 20
Dependent Claim
174 words
Software stored on machine-readable media which tracks a three-dimensional structure defined within a data set including data representing three spatial dimensions, said software directing an image processing device to: select a geometric shape that occupies at least two independent dimensions; approximate a medial axis point in the three spatial dimensions for the structure to be tracked; obtain a best fit between the structure and the geometric shape by three-dimensional processing using at least one of adjusting size of the geometric shape along at least two independent dimensions to thereby match the structure, and also ascertaining a rotational orientation of the shape around one of the at least two independent dimensions such that the shape corresponds to the structure, or adjusting position of the geometric shape in the three spatial dimensions, and also ascertaining a rotational orientation of the shape around at least two independent axes such that it corresponds to the structure; and approximate a next medial axis point for the structure based on the best fit and the orientation of the geometric shape.
Claim 21
Dependent Claim
174 words
Software stored on machine-readable media which tracks a three-dimensional structure defined within a data set including data representing three spatial dimensions, said software directing an image processing device to: select a geometric shape that occupies at least two independent dimensions; approximate a medial axis point in the three spatial dimensions for the structure to be tracked; obtain a best fit between the structure and the geometric shape by three-dimensional processing using at least one of adjusting size of the geometric shape along at least two independent dimensions to thereby match the structure, and also ascertaining a rotational orientation of the shape around one of the at least two independent dimensions such that the shape corresponds to the structure, or adjusting position of the geometric shape in the three spatial dimensions, and also ascertaining a rotational orientation of the shape around at least two independent axes such that it corresponds to the structure; and approximate a next medial axis point for the structure based on the best fit and the orientation of the geometric shape.
Claim 22
Dependent Claim
53 words
Software according to claim 16, wherein said software directs the image processing device to: apply a digital filter to the data represented by the geometric shape; and readjust size of the digital filter along two independent dimensions and repeatedly compare the filter to the structure while varying the size to optimize filter response.
Claim 23
Dependent Claim
43 words
Software according to claim 17, wherein said software further directs the image processing device to: readjust a position of the digital filter in three-dimensional space and repeatedly compare the filter to the structure while varying the position and size to optimize filter response.
Claim 24
Dependent Claim
43 words
Software according to claim 16, wherein said software directs the image processing device to: select a geometric shape that is a three-dimensional digital filter; and ascertain a rotational orientation by selecting a rotational orientation of the filter which produces a maximized filter response.
Claim 25
Dependent Claim
56 words
Software according to claim 16, wherein said software further directs the image processing device to obtain a best fit by readjusting the digital filter in at least five degrees of freedom, including in position along three spatial dimensions of the data and about two rotational axes of the geometric shape, to thereby obtain the best fit.
Claim 26
Dependent Claim
54 words
Software according to claim 16, wherein said software directs the image processing device to approximate a next medial axis point by: determining a projected axis point out from the best fit a distance in response to the orientation; and approximating the next medial axis point for the structure based on the projected axis point.
Claim 27
Dependent Claim
58 words
Software according to claim 16, wherein said software directs the image processing device to approximate the next medial axis point by: approximating a temporary medial axis point in the data; performing a constrained search in the immediate vicinity of the temporary medial axis point; and selecting as a result of the constrained search the next medial axis point.
References Cited (Backward Citations)
US4742557A
Cited
US4956869A
Cited
US4875165A
Cited
US5023920A
Cited
US5150292A
Cited
US5121191A
Cited
US5271064A
Cited
US5283837A
Cited
US5369678A
Cited
US5237646A
Cited
US5454371A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-02 | 2001-09-01 | 2002-03-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-02 | 2005-09-01 | 2006-03-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-02 | 2009-09-01 | 2010-03-03 | $7700.00 | Window Closed / Lapsed |