Patent US6819795B1 successfully refreshed from Google Patents.
US6819795B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Genetic segmentation method for data, such as image data streams
Assignee: Fujifilm Business Innovation Corp
•
Filing: 2000-07-07
•
Granted: 2004-11-16
•
Expires: 2020-07-07
Abstract
Abstract A method, information system, and computer-readable medium is provided for segmenting a plurality of data, such as multimedia data, and in particular an image document stream. Segment boundary points may be used for retrieving and/or browsing the plurality of data. Similarly, segment boundary points may be used to summarize the plurality of data. Examples of image document streams include video, PowerPoint slides, and NoteLook pages. A genetic method having a fitness or evaluation function using information retrieval concepts, such as importance and precedence, is used to obtain segment boundary points. The genetic method is able to evaluate a large amount of data in a cost effective manner. The genetic method is also able to run incrementally on streaming video and adapt to usage patterns by considering frequently accessed images.
Inventors
- 👤 Patrick Chiu
- 👤 Andreas Girgensohn
- 👤 Wolf Polak
- 👤 Eleanor Rieffel
- 👤 Lynn Wilcox
- 👤 Forrest H. Bennett, III
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:52
CPC Classifications
G; G11; G11B; G11B27/00; G11B27/10; G11B27/19; G11B27/28
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
223 words
A method for segmenting a plurality of data into k segments, comprising the steps of: (a) creating a first and second series of numbers (“first and second strings”) respectively, representing the plurality of data, wherein the first and second strings have k−1 boundaries, respectively; (b) calculating a first and second fitness function values for the data represented by the first and second strings, respectively; (c) creating a third and fourth series of numbers (“third and fourth strings”) respectively, representing the plurality of data based on the first and second fitness function values; (d) selecting a partition point (“crossover”) in the third and fourth strings, wherein the crossover partitions (1) the third string into a head series of numbers and a tail series of numbers, and (2) the fourth string into a head series of numbers and a tail series of numbers; (e) interchanging the third string tail series of numbers with the fourth string tail series of numbers to form a fifth and sixth series of numbers (“fifth and sixth strings”); (f) adjusting the numbers in the fifth and sixth strings to equal k−1 boundaries; (g) calculating a third and fourth fitness function values for the data represented by the fifth and sixth strings; and (h) providing k segments responsive to a comparison of the first, second, third and fourth fitness function values.
Claim 2
Independent Claim
223 words
A method for segmenting a plurality of data into k segments, comprising the steps of: (a) creating a first and second series of numbers (“first and second strings”) respectively, representing the plurality of data, wherein the first and second strings have k−1 boundaries, respectively; (b) calculating a first and second fitness function values for the data represented by the first and second strings, respectively; (c) creating a third and fourth series of numbers (“third and fourth strings”) respectively, representing the plurality of data based on the first and second fitness function values; (d) selecting a partition point (“crossover”) in the third and fourth strings, wherein the crossover partitions (1) the third string into a head series of numbers and a tail series of numbers, and (2) the fourth string into a head series of numbers and a tail series of numbers; (e) interchanging the third string tail series of numbers with the fourth string tail series of numbers to form a fifth and sixth series of numbers (“fifth and sixth strings”); (f) adjusting the numbers in the fifth and sixth strings to equal k−1 boundaries; (g) calculating a third and fourth fitness function values for the data represented by the fifth and sixth strings; and (h) providing k segments responsive to a comparison of the first, second, third and fourth fitness function values.
Claim 3
Dependent Claim
16 words
The method of claim 1 , wherein the plurality of data includes a plurality of images.
Claim 4
Dependent Claim
17 words
The method of claim 1 , wherein the plurality of images includes a plurality of video frames.
Claim 5
Dependent Claim
17 words
The method of claim 1 , wherein the plurality of data includes a plurality of presentation slides.
Claim 6
Dependent Claim
14 words
The method of claim 1 , wherein the plurality of data includes note pages.
Claim 7
Dependent Claim
17 words
The method of claim 1 , wherein the plurality of data includes a plurality of non-image data.
Claim 8
Dependent Claim
19 words
The method of claim 1 , wherein the method further includes a step of reducing the plurality of data.
Claim 9
Dependent Claim
21 words
The method of claim 7 , wherein the reducing of the plurality of data includes a subsampling a plurality of images.
Claim 10
Dependent Claim
19 words
The method of claim 7 , wherein the reducing the plurality of data based on a standard deviation measurement.
Claim 11
Dependent Claim
18 words
The method of claim 1 , wherein the fitness function is based on image similarity, importance and precedence.
Claim 12
Dependent Claim
18 words
The method of claim 1 , wherein the fitness function is based on histogram differences between adjacent data.
Claim 13
Dependent Claim
43 words
The method of claim 1 , wherein the fitness function equals: f ( S k ) = ∑ i , j ∈ S k a ( i , j ) h ( i , j ) .
Claim 14
Dependent Claim
52 words
The method of claim 1 , wherein the fitness function equals: f ( S k ) = ∑ i , j ∈ S k i ≠ j h ( i , j ) ( I i + I j ) i - j 2 .
Claim 15
Dependent Claim
14 words
The method of claim 1 , wherein the fitness function is based on precedence.
Claim 16
Dependent Claim
14 words
The method of claim 1 , wherein the fitness function is based upon importance.
Claim 17
Dependent Claim
20 words
The method of claim 1 , further comprises the step of: (i) adding additional data to the plurality of data.
Claim 18
Dependent Claim
15 words
The method of claim 1 , further comprising the step of: (i) varying k segments.
Claim 19
Dependent Claim
35 words
The method of claim 13 , wherein the fitness function equals: g ( S k ) = f ( S k ) ( 1 + k - k 0 ) .
Claim 20
Dependent Claim
42 words
The method of claim 1 , wherein the fitness function includes an importance factor equal to: I i = A i P i log ( δ ( i ) ) log 1 W i .
Claim 21
Dependent Claim
18 words
The method of claim 1 , wherein the first and second strings include k−1 ones representing segment boundaries.
Claim 22
Dependent Claim
149 words
An article of manufacture, including a computer-readable memory, comprising: (a) a first software program for forming a first string and a second string corresponding to a plurality of data, wherein the first and second strings have boundary points; (b) a second software program for calculating a first and second fitness function values for the plurality of data represented by a first string and the second string, respectively; (c) a third software program for creating a third and fourth string corresponding to the plurality of data based on the first and second fitness function values and a genetic operation, wherein the second software program calculates a third and fourth fitness function values for the data represented by the third and fourth strings; and (d) a fourth software program for selecting a set of data in the plurality of data based on the first, second, third and fourth fitness function values.
Claim 23
Dependent Claim
149 words
An article of manufacture, including a computer-readable memory, comprising: (a) a first software program for forming a first string and a second string corresponding to a plurality of data, wherein the first and second strings have boundary points; (b) a second software program for calculating a first and second fitness function values for the plurality of data represented by a first string and the second string, respectively; (c) a third software program for creating a third and fourth string corresponding to the plurality of data based on the first and second fitness function values and a genetic operation, wherein the second software program calculates a third and fourth fitness function values for the data represented by the third and fourth strings; and (d) a fourth software program for selecting a set of data in the plurality of data based on the first, second, third and fourth fitness function values.
Claim 24
Dependent Claim
30 words
The article of manufacture of claim 21 , wherein the genetic operation includes a crossover operation, wherein the crossover operation interchanges a pair of string tails at a boundary point.
Claim 25
Dependent Claim
31 words
The article of manufacture of claim 21 , wherein the genetic operation includes a mutation operation, wherein the mutation operation adjusts the number of ones in the third and fourth strings.
References Cited (Backward Citations)
US4939672A
Cited
US5048095A
Cited
US5377312A
Cited
US5729623A
Cited
US5764814A
Cited
US6167146A
Cited
US6594375B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-11-16 | 2008-05-17 | 2008-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-11-16 | 2012-05-17 | 2012-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-11-16 | 2016-05-17 | 2016-11-16 | $7700.00 | Window Closed / Lapsed |