US5841888A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for fingerprint indexing and searching
Assignee: Apple Inc
•
Filing: 1996-01-23
•
Granted: 1998-11-24
•
Expires: 2016-01-23
Abstract
Abstract A method for indexing and searching a plurality of reference fingerprints to determine if a sample fingerprint matches one of the reference fingerprints includes the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon characteristics of the fingerprints and with the index values being generally evenly distributed and continuous over a relatively large population of individuals; selecting a first subset of the reference fingerprints having index values in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints. The step of determining index values for the reference fingerprints and the sample fingerprint preferably comprises determining same based upon ridge flow curvature of the fingerprints. The step of selecting the first subset of reference fingerprints preferably comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset. Apparatus aspects of the invention are also disclosed.
Inventors
- 👤 Dale R. Setlak
- 👤 John C. Schmitt
- 👤 Mark E. Boss
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:30
CPC Classifications
A; A61; A61B; A61B5/00; A61B5/117; A61B5/1171; A61B5/1172; G; G06; G06V; G06V40/00; G06V40/10; G06V40/12; G06V40/1347; G06V40/1365; G06V40/16; G06V40/168; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
182 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon ridge flow characteristics of the fingerprints wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the ridge flow fingerprint characteristics of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function within a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints.
Claim 2
Independent Claim
182 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon ridge flow characteristics of the fingerprints wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the ridge flow fingerprint characteristics of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function within a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints.
Claim 3
Dependent Claim
32 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining same based upon ridge flow curvature of the fingerprints.
Claim 4
Dependent Claim
62 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center for each fingerprint; selecting a predetermined portion of each fingerprint relative to a center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 5
Dependent Claim
27 words
A method according to claim 3 wherein the step of selecting a predetermined portion of each fingerprint comprises selecting a generally annularly shaped portion of each fingerprint.
Claim 6
Dependent Claim
38 words
A method according to claim 1 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 7
Dependent Claim
43 words
A method according to claim 1 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 8
Dependent Claim
57 words
A method according to claim 1 further comprising the step of selecting a second subset of reference fingerprints having index values along the generally continuous and generally monotonically varying function within a second range larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 9
Dependent Claim
39 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 10
Dependent Claim
40 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 11
Dependent Claim
36 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 12
Dependent Claim
37 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from fingerprint information developed for the comparing step.
Claim 13
Dependent Claim
31 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be at least one-dimensional.
Claim 14
Dependent Claim
33 words
A method according to claim 1 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of ridge flow characteristics.
Claim 15
Independent Claim
203 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith a curliness index value based upon an aggregate of a rate of change of ridge direction vectors, the method comprising the steps of: determining a curliness index value for the sample fingerprint based upon an aggregate of a rate of change of ridge direction vectors of the sample fingerprint wherein the index values are both generally evenly distributed over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the aggregate of a rate of change of ridge direction vectors of fingerprints of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having curliness index values along the generally even distribution in a first range relative to the curliness index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 16
Independent Claim
203 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith a curliness index value based upon an aggregate of a rate of change of ridge direction vectors, the method comprising the steps of: determining a curliness index value for the sample fingerprint based upon an aggregate of a rate of change of ridge direction vectors of the sample fingerprint wherein the index values are both generally evenly distributed over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the aggregate of a rate of change of ridge direction vectors of fingerprints of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having curliness index values along the generally even distribution in a first range relative to the curliness index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 17
Dependent Claim
63 words
A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises the steps of: determining a center of the sample fingerprint; selecting a predetermined portion of the sample fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.
Claim 18
Dependent Claim
26 words
A method according to claim 15 wherein the step of selecting a predetermined portion of the sample fingerprint comprises selecting a generally annularly shaped portion thereof.
Claim 19
Dependent Claim
38 words
A method according to claim 14 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 20
Dependent Claim
43 words
A method according to claim 14 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 21
Dependent Claim
53 words
A method according to claim 14 further comprising the step of selecting a second subset of reference fingerprints along the generally even distribution having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 22
Dependent Claim
29 words
A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises determining such index value to be at least one-dimensional.
Claim 23
Dependent Claim
41 words
A method according to claim 14 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of an aggregate of a rate of change of ridge direction vectors.
Claim 24
Independent Claim
171 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 25
Independent Claim
171 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 26
Dependent Claim
39 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 27
Dependent Claim
40 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 28
Dependent Claim
36 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.
Claim 29
Dependent Claim
36 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 30
Dependent Claim
38 words
A method according to claim 22 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 31
Dependent Claim
43 words
A method according to claim 22 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 32
Dependent Claim
57 words
A method according to claim 22 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 33
Dependent Claim
34 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 34
Dependent Claim
62 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 35
Independent Claim
129 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals, the method comprising the steps of: determining respective index values for the reference fingerprints and a sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; and selecting for searching a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint.
Claim 36
Independent Claim
129 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals, the method comprising the steps of: determining respective index values for the reference fingerprints and a sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; and selecting for searching a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint.
Claim 37
Dependent Claim
39 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 38
Dependent Claim
40 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 39
Dependent Claim
36 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 40
Dependent Claim
38 words
A method according to claim 32 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 41
Dependent Claim
34 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 42
Dependent Claim
62 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 43
Independent Claim
194 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith an index value based upon at least one predetermined fingerprint characteristic wherein the index values for the reference and sample fingerprints are both generally evenly distributed and continuous over the relatively large population of individuals and wherein the reference index values are sorted to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals, the method comprising the steps of: determining the index value for the sample fingerprint based upon the at least one predetermined fingerprint characteristic; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 44
Independent Claim
194 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith an index value based upon at least one predetermined fingerprint characteristic wherein the index values for the reference and sample fingerprints are both generally evenly distributed and continuous over the relatively large population of individuals and wherein the reference index values are sorted to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals, the method comprising the steps of: determining the index value for the sample fingerprint based upon the at least one predetermined fingerprint characteristic; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 45
Dependent Claim
38 words
A method according to claim 31 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 46
Dependent Claim
57 words
A method according to claim 39 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 47
Dependent Claim
33 words
A method according to claim 39 wherein the step of determining an index value for the sample fingerprint comprises determining such an index value based upon ridge flow characteristics of the sample fingerprint.
Claim 48
Dependent Claim
62 words
A method according to claim 42 wherein the step of determining an index value for the sample fingerprint comprises the steps of: determining a center of the sample fingerprint; selecting a predetermined portion of the sample fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.
Claim 49
Independent Claim
190 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index value to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint and based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 50
Independent Claim
190 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index value to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint and based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 51
Dependent Claim
39 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 52
Dependent Claim
40 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 53
Dependent Claim
36 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.
Claim 54
Dependent Claim
36 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 55
Dependent Claim
43 words
A method according to claim 44 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 56
Dependent Claim
48 words
A method according to claim 44 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 57
Dependent Claim
34 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 58
Dependent Claim
62 words
A method according to claim 51 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
References Cited (Backward Citations)
US3781855A
Cited
US3859633A
Cited
US4210899A
Cited
US3959884A
Cited
US4185270A
Cited
US4151512A
Cited
US4140272A
Cited
US4156230A
Cited
EP0040838A1
Cited
US4336998A
Cited
EP0041693A1
Cited
US4353056A
Cited
US4394773A
Cited
US4582985A
Cited
US4429413A
Cited
US4525859A
Cited
US4581760A
Cited
US4526043A
Cited
US4577345A
Cited
US4607384A
Cited
US4845610A
Cited
US4747147A
Cited
US5010772A
Cited
US4947443A
Cited
US4932776A
Cited
US5040223A
Cited
US5040224A
Cited
GB2219870A
Cited
DE4026167A1
Cited
US5363453A
Cited
US4993068A
Cited
EP0444891A1
Cited
US5325442A
Cited
EP0459808A2
Cited
US5050220A
Cited
US5239590A
Cited
US5140642A
Cited
US5351304A
Cited
EP0513612A2
Cited
US5488719A
Cited
US5429006A
Cited
US5400662A
Cited
US5337369A
Cited
US5420936A
Cited
US5373181A
Cited
US5559504A
Cited
WO1994025938A1
Cited
US5337357A
Cited
US5497429A
Cited
US5436972A
Cited
US5503029A
Cited
US5526701A
Cited
US5465303A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-23 | 2002-05-25 | 2002-11-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-23 | 2006-05-25 | 2006-11-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-23 | 2010-05-25 | 2010-11-24 | $7700.00 | Window Closed / Lapsed |