Method and apparatus for data analysis

• US 5,983,251 A
• Filed: 03/08/1996
• Issued: 11/09/1999
• Est. Priority Date: 09/08/1993
• Status: Expired due to Fees

• Current Assignee: IDT Incorporated (IDT Corporation)
• Original Assignee: IDT Incorporated (IDT Corporation)
• Inventors: Martens, Harald Aagaard, Reberg, Jan Otto
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/624,382
• Time in Patent Office: 1,341 Days
• Field of Search: 364/715.02, 395/200.77, 348/402, 348/405, 348/409, 382/232, 382/235, 382/236, 382/238, 382/239, 382/244, 382/251
• US Class Current: 708/203
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic

Abstract

A modelling technique for compact representation of related images is disclosed. The images are described as collections of spatial segments, each of which is modelled with a multivariate bi-linear model in the intensity and similarity also in the address domain. As applied to digitized video sequences, each bi-linear model consists of a set of spatial change patterns relative to a reference and a set of corresponding temporal scores that indicate how much of each change pattern is present in each image. Both the structure of the encoding and decoding algorithms and also the data structure of the compact representation are disclosed. This multi-domain modelling allows efficient data representation by removal of redundancies in the spatial, temporal and other domains. Examples of uses of the modelling technique include video compression, interactive video and games, and search in and analysis of compressed image data bases The system generalizes to a method and apparatus for multi-domain multivariate representation of large amounts of inter-related data.

Claims

1. A method for converting samples of an input signal to an encoded signal composed of a plurality of component signals each representing a characteristic of the input signal in a different domain, said input signal being comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, characterized in that each component signal is formed as the combination of a plurality of factors, each factor being the product of a score signal and a load signal, the score signal defining the variation of data samples from record to record and the load signal defining the relative variation of a subgroup of samples in different positions of a record.

2. The method in accordance with claim 1 wherein a set of reference signal values is provided which represents a reference pattern of samples and the component signals indicate how the reference signal should be transformed to provide a reconstruction of each record.

3. The method in accordance with claim 2 wherein the set of reference signal values are collected as transformed parts of records of the input signal.

4. The method of claim 2 wherein a first of said component signals, called magnitude signal, represents changes in magnitude of samples from the reference signal to each record, and a second of said component signals, called position signal, represents changes in position of samples from the reference signal to each record.

5. The method of claim 4 wherein a component change signal may result in several samples of the reference signal being mapped to a common position in one of the records, the intensity of the sample at the common position in the record being equal to a weighted sum of the intensities of the several samples.

6. The method of claim 1 wherein at least one of a set of load signals and a set of score signals is selected for each component signal so as to be statistically representative of variations in the corresponding characteristic among all records.

7. The method of claim 4 wherein the number of factors and the precision of factors are selected so that the storage space required therefor will not exceed a predefined amount.

8. The method of claim 4 further comprising providing a plurality of error signals each corresponding to one of the component signals, each error signal providing correction to the extent that the corresponding component signal does not represent the corresponding characteristic of the input signal within a predefined range.

9. The method of claim 8 wherein the number of factors and the precision of factors is selected to achieve error signals which remain below a predefined threshold value.

10. The method of claim 8 wherein the number of factors and the precision of factors are selected so that the storage space required therefor will not exceed a predefined amount.

11. The method according to claim 4 wherein the number of factors and the precision of factors is chosen according to storage requirements, fidelity in reconstruction, transmission channel capacity, encoder or decoder processing time limitations or a combination thereof.

12. The method of claim 1 further comprising providing a plurality of error signals each corresponding to one of the component signals, each error signal providing correction to the extent that the corresponding component signal does not represent the corresponding characteristic of the input signal within a predefined range.

13. The method in accordance with claim 12 wherein a set of reference signal values is provided which represents a reference pattern of samples and the component signals indicate how the reference signal should be transformed to provide a reconstruction of the records.

14. The method of claim 1 wherein a first of said component signals, called magnitude signal, represents changes in magnitude of samples between records, and a second of said component changes, called position signal, represents changes in position between records.

15. The method according to claim 14, the method comprising the steps of:

(1) forming a reference image,

(2) for each frame, estimating motion from the reference image to the frame, thereby for each frame producing a motion field,

(3) performing a Principal Component Analysis on the collection of the motion fields, thereby producing a bilinear model of motion, the bilinear model of motion comprising motion score vectors and motion loading vectors,

(4) for each frame, moving the contents of the frame according to the inverse of a motion field calculated by multiplying the motion score vectors for the frame with the motion loadings, thereby producing for each frame a motion compensated frame, and

(5) performing a Principal Component Analysis on the collection of motion compensated frames, thereby producing a bilinear model of intensity, the bilinear model of intensity comprising intensity score vectors and intensity loading vectors, wherein the collection of the bilinear model of motion and the bilinear model of intensity together comprise the encoded signal.

16. The method according to claim 4, the method comprising the steps of:

(1) computing a magnitude loading signal and a position loading signal based on a subset of the records, and

(2) for at least one of the remaining records, computing a magnitude score signal and a position score signal based on the magnitude loading signal and the position loading signal produced in step (1).

17. The method according to claim 16, wherein the computing of the position score signal in step (2) comprises the following steps for each remaining record:

(2a) estimating motion from the reference image to the remaining record, thereby producing a motion field, and

(2b) projecting the motion field on the position loading, thereby producing a position score signal.

18. The method according to claim 16, wherein the computing of the position score signal in step (2) comprises the following steps:

(2a) choosing a set of candidate score vectors,

(2b) for each candidate score vector, decoding a frame according to the candidate score vector and the position loading signal, measuring a value for fit between the original frame and the decoded frame,

(2c) selecting the candidate score vectors corresponding to the best fit, and

(2d) iterating steps (2a) to (2c), choosing new sets of candidate score vectors based on the score vector selected in step (2c), until a convergence criterion is met, wherein the candidate score vector corresponding to the best fit found in step (2c) is the computed position score signal.

19. The method according to claim 16, wherein the computing of the magnitude score signal in step (2) comprises the following steps for each remaining record:

(2a) computing a position score signal,

(2b) forming a motion field by multiplying the position score signal by the position loading signal,

(2c) moving the remaining record according to the inverse of the motion field, giving a motion compensated record,

(2d) calculating the difference between the motion compensated record and the reference image, and

(2e) projecting the difference image on each of the magnitude loading signals, thereby producing a magnitude score signal.

20. The method according to claim 14, comprising the steps of:

(1) dividing the sequence into at least two subsequences of records,

(2) encoding each subsequence as a plurality of component signals, and

(3) for each domain, combining the component signals for each of the subsequences into a component signal for the entire sequence.

21. The method of claim 2 wherein at least one factor or reference image that was relevant for some records is later updated to be relevant for other records.

22. The method of claim 15 wherein several passes are made through the records of the input signal, where the first pass is made with low resolution or higher weight on position modelling, and later passes are made to refine the results with regard to resolution, compression or fidelity.

23. The method of claim 14 wherein a choice of including magnitude or position factors in the encoded representation is done based on how much of the signal a factor can explain and the cost of including the factor in the encoded representation, the cost being measured in entropy, storage requirement, decoding time consumption, or a combination thereof.

24. The method of claim 23 wherein the factors to be chosen between are calculated by developing bi-linear models of the part of the signal that has not already been explained by earlier factors of the component signals.

25. The method of claim 15 wherein estimated uncertainties in magnitude or position estimates are used to influence the Principal Component Analysis.

26. The method of claim 14, wherein for each sample position in the component change signals, there is a corresponding value of an alpha signal, the alpha signal indicating degree of presence.

27. The method of claim 26, wherein the alpha values are represented as a component signal comprising score and load signals.

28. A method for encoding an input signal, the input signal being comprised of data samples organized into records of multiple samples with each sample occupying a unique position within its record, wherein the sequence is first encoded according to the method of claim 1, producing score and loading signals, the method according to claim 1 is then applied on a subset of the score signals or a subset of the loading signals, producing meta-score signals and meta-loading signals, and wherein the meta-score signals, meta-loading signals and those score and loading signals that have not been expressed as meta-score signals and meta-loading signals together comprise an encoded representation.

29. The method of claim 14 wherein one or more score or load signal is compressed according to a data compression method exploiting redundancy or irrelevance in spatial or temporal dimensions.

30. The method of claim 14 wherein the input signal is an audio signal, each record is a frequency spectrum computed for one frame of audio, the first component signal represents changes in magnitude of given frequencies, and the second component signal represents shifts in frequency.

31. The method of claim 14 wherein the input signal is an audio signal, each sample represents air pressure at a given point of time, the first component signal represents magnitude changes in air pressure, and the second component signal represents shifts in time.

32. The method of claim 14 wherein at least one score or load signal is found or modified with human assistance.

33. The method of claim 14 wherein the encoded signal is adapted to be decoded according to another frame rate or frame resolution than the original.

34. The method of claim 14 wherein a component change signal may result in several samples of the reference image being mapped to a common sample position in one of the frames, the intensity of the sample in the common sample position being equal to the sum of the intensities of the several samples.

35. The method of claim 14 wherein the input signal is a conventional video signal, each record is a video frame, each sample is a pixel of a video frame, said first component signal represents pixel intensity and said second component signal represents the location of pixels in each frame.

36. The method of claim 35 further comprising providing a plurality of error signals each corresponding to one of the component signals, each error signal providing correction to the extent that the corresponding component signal does not represent the corresponding characteristic of the input signal within a predefined range.

37. The method in accordance with claim 35 wherein a set of reference component signal values is provided which represents a reference pattern of samples and the component signals indicate how the reference signal should be transformed to provide a reconstruction of the input signal.

38. The method of claim 2 wherein a component signal may result in several samples of the reference signal being mapped to a common sample position in one of the records, the intensity of the sample in the common position being equal to a weighted sum of the values of the several pixels.

39. The method of claim 2 wherein a component signal may result in several samples of the reference signal being mapped to a common sample position in one of the records, the intensity of the sample in the common position being equal to the difference between a constant and the sum of the values of the several samples.

40. The method of claim 2 wherein a component signal may result in several samples of the reference signal being mapped to a common sample position in one of the records, said method further comprising defining a depth for each of the several samples, the value of the sample in the common sample position being equal to the value of the sample among the several samples which has the least depth.

41. The method of claim 40 wherein the depth of samples is defined as a separate domain represented as a third component signal comprising score and load signals.

42. The method of claim 2 wherein the encoded signal comprises a collection of holons, each holon having its own reference signal and component signals, and the effect of each holon is aggregated to produce the final reconstructed records.

43. The method of claim 42 wherein the location of a sample within the reference image is represented in a first system of coordinates and the location of a sample within at least one of the holons is represented in a different system of coordinates.

44. The method of claim 42 wherein the location of a sample within different holons is represented in a different system of coordinates.

45. The method of claim 42 wherein the holons include a set of samples exhibiting coordinated behavior in at least one domain, and at least one of a load signal and score signal of at least one component signal operates only on said set of samples.

46. The method of claim 2, the method comprising the steps of:

a. determining the plurality of component change signal values as the difference between each record and the reference pattern of samples;

b. performing principal component analysis on the plurality of component change signal values to extract a plurality of loads;

c. projecting the plurality of component change signal values on the plurality of loads to produce a set of score values which are applied to the plurality of loads to produce an approximated record;

d. determining the difference between each approximated record and each record;

e. repeating steps c and d until the difference between each approximated record and each record is less than a predetermined value.

47. The method of claim 46, wherein the principal component analysis is a weighted principal component analysis.

48. The method of claim 14, comprising the further step of extending the set of reference component signals.

55. A method for editing an input signal comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, the method comprising:

(1) encoding the input signal according to the method of claim 1,

(2) editing at least one loading or score signal,

(3) decoding the edited encoded signal according to the method of claim 49, wherein the decoded signal from step (3) comprise the edited signal.

77. A system comprising a recording apparatus and a data carrier containing an encoded signal produced by the method of any one of claims 1-48.

80. A system comprising a recording apparatus, a data carrier and a reading apparatus, wherein the data carrier contains an encoded signal produced according to the method of any one of claims 1-48.

85. A data carrier containing an encoded signal produced by the method of any one of claims 1-48.

86. An apparatus producing a transmitted signal containing an encoded signal produced by the method of any one of claims 1-48.

87. The encoded signal produced by the method of any one of claims 1-48 provided on one of a storage medium and a transmission medium.

49. A method for decoding an encoded signal composed of a plurality of component signals in different domains and a reference signal to a reconstructed input signal comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, said encoded signal represented as a combination of a plurality of factors, each factor being the product of a score signal and a load signal, the score signal defining the variation of data samples from record to record and the load signal defining the relative variation of a subgroup of samples in different positions of a record, said method utilizing a reference pattern of samples, comprising the steps of:

a. multiplying each load signal by its associated score signal to produce each factor;

b. combining the factors produced in step a;

c. modifying the set of reference signal values according to the combined factors produced in step b to produce the records of a reconstructed input signal.

50. The method according to claim 49, wherein a first component signal is a magnitude signal and a second component signal is a position signal, the method for each record comprising the steps of:

(1) for each magnitude factor, multiplying the magnitude score signal corresponding to the record with the magnitude load signal, thereby yielding a magnitude factor signal,

(2) summing the magnitude factor signals, thereby yielding a magnitude signal,

(3) adding the magnitude signal to the reference signal, thereby yielding a magnitude corrected reference signal,

(4) for each position factor, multiplying the position score signal corresponding to the record with the position load signal, thereby yielding a position factor signal,

(5) summing the position factor signals, thereby yielding a position signal,

(6) repositioning the magnitude corrected reference signal according to the position signal, thereby yielding a reconstructed record.

51. A method for decoding an encoded signal as in claim 49 wherein at least one of the load signals and score signals is provided on a storage medium.

52. A method for decoding an encoded signal as in claim 49, wherein the reference component signal values are provided on the storage medium.

53. A method for decoding an encoded signal as in claim 49 wherein the method comprises the further step of receiving at least one of the load signals and score signals from a remote location over a communications medium.

54. The method of claim 49 wherein the reference component signal values are also received over the communications medium.

76. A system comprising a reading apparatus and a data carrier containing data and adapted to be decoded according to the method of any one of claims 49-54.

81. The system of claim 80, wherein the encoded signal is adapted to be decoded by the method of claim 49.

84. A data carrier containing data recorded thereon and adapted to be decoded by the method of any one of claims 49-54.

56. An apparatus for converting an input signal to an encoded signal, said input signal being comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, characterized in that the encoded signal is composed of a plurality of component signals each representing a characteristic of the input signal in a different domain, each component signal is composed of a plurality of factors, each factor being the product of a score signal and a load signal, the score signal defining the variation of data samples from record to record and the load signal defining the relative variation of a subgroup of samples in different positions of a record.

57. The apparatus in accordance with claim 56 further comprising means for generating a set of reference signal values which represents a reference pattern of samples, wherein the component signals indicate how the reference signal should be transformed to provide a reconstruction of each record.

58. The apparatus of claim 57 wherein a first of said component signals, called magnitude signal, represents changes in magnitude of samples from the reference signal to each record, and a second of said component changes, called position signal, represents changes in position of samples from the reference signal to each record.

59. The apparatus of claim 58 wherein a component signal may result in several samples of the reference image being mapped to a common sample position in one of the frames, further comprising means for causing the intensity of the sample in the common sample position to be equal to a weighted sum of the intensities of the several samples.

60. The apparatus of claim 58 further comprising means for providing a plurality of error signals each corresponding to one of the component signals, each error signal providing correction to the extent that the corresponding component signal does not represent the corresponding characteristic of the input signal within a predefined range.

61. The apparatus of claim 56 further comprising means for providing a plurality of error signals each corresponding to one of the component signals, each error signal providing correction to the extent that the corresponding component signal does not represent the corresponding characteristic of the input signal within a predefined range.

62. The apparatus of claim 56 wherein each record has the same number of samples arranged in a multi-dimensional array and said means for encoding causes a first of said component signals to represent the magnitude of samples and a second of said component signals to represent the position of samples in the array.

63. The apparatus of claim 62 wherein the input signal is a conventional video signal, each sample is a pixel of a video image, each record is a frame of video, said first component signal represents pixel intensities and said second component signal represents the location of pixels in a frame.

64. The apparatus in accordance with claim 63 further comprising means for generating a reference image which represents a reference pattern of samples, wherein the component signals indicate how the reference signal should be transformed to provide a reconstruction of each record.

65. The apparatus of claim 64 wherein a component signal may result in several pixels of the reference image being mapped to a common pixel of one of the frames, further comprising means for controlling the intensity of the common pixel to be equal to a weighted sum of the intensities of the several pixels.

66. The apparatus of claim 64 wherein a component signal may result in several pixels of the reference image being mapped to a common pixel of one of the frames, further comprising means for controlling the intensity of the common pixel to equal the difference between a constant and the sum of the intensities of the several pixels.

67. The apparatus of claim 64 wherein a component signal may result in several pixels of the reference image being mapped to a common pixel of one of the frames, further comprising means for defining a depth for each of the several pixels, and means for controlling the intensity of the common pixel to be equal to the intensity of the pixel among the several pixels which has the least depth.

68. The apparatus of claim 64 wherein the encoded signal comprises a collection of holons, each holon having its own reference signal and component signals, and the effect of each holon is aggregated to produce the final reconstructed records.

69. The apparatus of claim 64 wherein the holons include a set of pixels exhibiting coordinated behavior in at least one domain, said means for encoding producing at least one of a load signal and score signal of at least one component signal which operates only on said set of pixels.

75. An apparatus for editing an input signal comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, the apparatus comprising:

(1) means for converting samples of the input signal to an encoded signal composed of a plurality of component signals each representing a characteristic of the input signal in a different domain, characterized in that each component signal is formed as the combination of a plurality of factors, each factor being the product of a score signal and a load signal, the score signal defining the variation of data samples from record to record and the load signal defining the relative variation of a subgroup of samples in different positions of a record,

(2) means for editing at least one loading or score signal, and

(3) means for decoding the edited encoded signal according to the method of claim 69, wherein the decoded signal from step (3) comprise the edited signal.

79. A system comprising a recording apparatus and a data carrier containing an encoded signal produced by the apparatus of any one of claims 56-69.

82. A system comprising a recording apparatus, a data carrier and a reading apparatus, wherein the data carrier contains an encoded signal produced by the apparatus of any one of claims 56-69.

70. An apparatus for decoding an encoded signal composed of a plurality of component signals in different domains to a reconstructed input signal comprised of data samples organized into records of multiple samples, with each sample occupying a unique position within its record, said encoded signal represented as a combination of a reference signal and a plurality of factors, each factor being the product of a score signal and a load signal, the score signal defining the variation of data samples from record to record and the load signal defining the relative variation of a subgroup of samples in different positions of a record, said apparatus utilizing a reference pattern of samples, comprising:

a. means for multiplying each load signal by its associated score signal to produce each factor;

b. means for combining the factors produced in step a;

c. means for modifying the set of reference signal values according to the combined factors produced in step b to produce the records of a reproduced input signal.

71. An apparatus as in claim 70 further comprising a storage medium containing at least one of the load signals and score signals.

72. An apparatus as in claim 70, wherein the storage medium contains the reference component signal values.

73. An apparatus as in claim 70 further comprising means for receiving at least one of the load signals and score signals from a remote location over a communications medium.

74. The apparatus of claim 70 wherein the reference signal values are received over the communications medium.

78. A system comprising a reading apparatus and a data carrier comprising data and adapted to be decoded by the apparatus of any one of claims 70-75.

83. The system of claim 82, wherein the encoded signal is read by the apparatus of claim 70.