IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0216295
(2011-08-24)
|
등록번호 |
US-8711015
(2014-04-29)
|
발명자
/ 주소 |
- Mustiere, Frederic
- Najaf-Zadeh, Hossein
- Pishehvar, Ramin
- Lahdili, Hassan
- Thibault, Louis
- Bouchard, Martin
|
출원인 / 주소 |
- Her Majesty the Queen in Right of Canada as represented by the Minister of Industry, through the Communications Research Centre Canada
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
3 인용 특허 :
5 |
초록
▼
The invention relates to compressing of sparse data sets contains sequences of data values and position information therefor. The position information may be in the form of position indices defining active positions of the data values in a sparse vector of length N. The position information is encod
The invention relates to compressing of sparse data sets contains sequences of data values and position information therefor. The position information may be in the form of position indices defining active positions of the data values in a sparse vector of length N. The position information is encoded into the data values by adjusting one or more of the data values within a pre-defined tolerance range, so that a pre-defined mapping function of the data values and their positions is close to a target value. In one embodiment, the mapping function is defined using a sub-set of N filler values which elements are used to fill empty positions in the input sparse data vector. At the decoder, the correct data positions are identified by searching though possible sub-sets of filler values.
대표청구항
▼
1. A method for electronically compressing sparse data, the method comprising: a) obtaining a sparse data set comprising a sequence of data values and position information therefor, wherein the position information individually associates the data values from the sequence with a subset of active pos
1. A method for electronically compressing sparse data, the method comprising: a) obtaining a sparse data set comprising a sequence of data values and position information therefor, wherein the position information individually associates the data values from the sequence with a subset of active positions from an ordered set of N possible positions, wherein N>K≧1, and wherein K is a number of the data values in the sequence;b) adjusting one or more of the data values using a pre-defined value modification process so as to obtain compressed sparse data wherein the position information is encoded in the data values; and,c) store or transmit the compressed sparse data for use by a decoder. 2. The method of claim 1, further comprising: providing a set of N different filler values individually associated with the N possible positions;wherein step (b) comprises: b1) using a pre-defined mapping rule ƒ to generate a mapped value F based on the data values and a filler sub-set v of the set of N filler values, wherein the filler sub-set v is obtained from the set of N filler values by excluding the filler values associated with the sub-set of active positions; and,b2) adjusting one or more of the data values so that the mapped value generated in step b1) is within a threshold distance ε from a target value T. 3. The method of claim 2, wherein step b1) comprises computing a sum of the K data values and the (N−K) filler values from the filler sub-set. 4. The method of claim 2, wherein the target value T is an integer. 5. The method of claim 2, further comprising verifying that step (b2) changes the one or more data values by no more than a pre-determined tolerance value Δ. 6. The method of claim 2, wherein the sequence of data values and position information therefor constitutes one sub-frame of the sparse data set, and wherein the method further comprises decomposing the sparse data set into a plurality of sub-frames including the one sub-frame. 7. The method of claim 3, wherein the data values are quantized, and wherein step (b2) comprises determining a minimal subset of the data values which, when adjusted by one or more quantization levels, reduces a distance |F−T| between the mapped value F and the target value T to below the threshold distance. 8. The method of claim 7, wherein the step of finding the minimal subset of the data values comprises using a binary linear optimization algorithm to determine a set of binary coefficients, each said binary coefficient defining whether one of the data values is to be adjusted by one quantization level. 9. The method of claim 1, further comprising using the decoder for: extracting the data values from the compressed sparse data;recovering the position information from the data values based on known information about the pre-defined value modification process. 10. The method of claim 2, further comprising: providing at the decoder the set of N different filler values individually associated with the N possible positions; and,using the decoder for: d) extracting the data values from the compressed sparse data;e) applying the pre-defined mapping to the received data values and different selections of (N−K) filler values from the set of N filler values and comparing resulting mapped values to the target value T;f) determining positions associated with K filler values which, when excluded from the mapping in step (e), result in a mapped value that is within the threshold distance ε from the target value T; and,g) individually assigning the positions of the K filler values determined in step (f) to the received data values in accordance with an order thereof in the received compressed sparse data. 11. The method of claim 10, wherein the compressed sparse data comprises information indicating a number P of false positives, and wherein step (e) comprises sequentially testing different selections of (N−K) filler values in a specified order until (P+1) mapped values are obtained that lie within the threshold distance ε from the target T. 12. The method of claim 2, wherein the sparse data represents a digital media signal that is encoded using a sparse encoder followed by a quantizer, and wherein the data values represent gain coefficients for K dictionary elements from an ordered plurality of N dictionary elements, and wherein the active positions correspond to positions of the K dictionary elements in the ordered plurality of N dictionary elements. 13. The method of claim 12, wherein the digital media signal comprises audio signal, and wherein the data values represent gain coefficients in a sparse representation of the audio signal. 14. The method of claim 2, further comprising transmitting to the decoder information indicating the number K of the data values in the sequence of data values. 15. The method of claim 2, further comprising transmitting to the decoder information indicating at least one of: the target value T, and the threshold distance ε. 16. A digital processing system for electronically compressing sparse data, comprising: input circuitry for obtaining a sparse data set comprising a sequence of data values and position information therefor, wherein the position information individually associates the data values from the sequence with a subset of active positions from an ordered set of N possible positions, wherein N>K≧1, wherein K is a total number of the data values in the sequence;a position encoder coupled to the input circuitry for receiving the sparse data set therefrom and for adjusting one or more of the data values using a pre-defined value modification process so as to obtain compressed sparse data wherein the position information is encoded in the data values; and,circuitry for storing the compressed sparse data or transmitting the compressed sparse data to a user. 17. A digital processing system of claim 16, wherein the position encoder comprises: filler memory for storing a full ordered set of N filler values individually associated with the N possible positions;a mapping unit coupled to the filler memory for generating a mapped value F based on the K data values and a filler set of (N−K) filler values using a pre-defined mapping rule, wherein the filler set is obtained by selecting from the filler memory all filler values stored therein excluding the filler values corresponding to the K active positions; and,a data modifier unit coupled to the mapping unit for adjusting one or more data values until the mapped value is within a pre-defined distance ε from a target value. 18. A digital processing system for de-compressing the compressed sparse data received from the digital processing system of claim 16, comprising: input circuitry for receiving the compressed sparse data and for extracting the sequence of data values therefrom; and,a position decoder for recovering the position information from the sequence of data values based on known information about the pre-defined value modification process, so as to restore the sparse data set. 19. A digital processing system of claim 18, wherein the position decoder comprises: a mapping unit for applying the pre-defined mapping to the received data values and different combinations of (N−K) filler values from the ordered set of N filler values for computing mapped values,a comparator for comparing the mapped values to the target value T, anda position memory unit for storing positions associated with K filler values which, when excluded from the pre-defined mapping, result in a mapped value that is within the pre-defined distance ε from the target value T; and,an output circuitry for outputting a restored sparse data set formed of the received data values and the positions stored in the memory unit. 20. The digital processing system of claim 19, wherein the position decoder comprises a plurality of parallel position decoding processors for testing different selections of (N−K) filler values.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.