System and method for fingerprinting datasets

• US 8,681,950 B2
• Filed: 03/28/2012
• Issued: 03/25/2014
• Est. Priority Date: 03/28/2012
• Status: Active Grant

• Current Assignee: Genesys Telecommunications Laboratories Incorporated (Genesys Cloud Services Incorporated)
• Original Assignee: Interactive Intelligence Incorporated (Genesys Cloud Services Incorporated)
• Inventors: Vlack, Kevin, Wyss, Felix Immanual
• Primary Examiner(s): Elahee, Md. S
• Application Number:
  US13/432,838
• Publication Number:
  US 20130259211A1
• Time in Patent Office: 727 Days
• Field of Search: 379 8801- 8802, 379/88.04, 379/88.08, 379/88.09, 379/88.16, 379/88.14, 379/88.19, 379/88.21, 379/93.34, 379/406.03, 379/907, 341/57
• US Class Current: 379/88.01
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G10L 25/54 for retrieval
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3066 by means of a mask or a bit-map
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04M 2203/2027 Live party detection
• CPC Class Codes: H04M 3/5158 in combination with automated outdialling systems devices for signalling identity of wanted subscriber H04M1/26

Abstract

Systems and methods for the matching of datasets, such as input audio segments, with known datasets in a database are disclosed. In an illustrative embodiment, the use of the presently disclosed systems and methods is described in conjunction with recognizing known network message recordings encountered during an outbound telephone call. The methodologies include creation of a ternary fingerprint bitmap to make the comparison process more efficient. Also disclosed are automated methodologies for creating the database of known datasets from a larger collection of datasets.

Claims

1. A method for identifying a candidate audio segment from an outbound telephone call, the method comprising the steps of:

a) creating a spectrogram of the candidate audio segment;

b) creating a candidate binary acoustic fingerprint bitmap of the spectrogram;

c) comparing the candidate binary acoustic fingerprint bitmap to at least one known binary acoustic fingerprint bitmap of a known network message;

d) if the candidate binary acoustic fingerprint bitmap matches one of said at least one known binary acoustic fingerprint bitmap within a predetermined threshold, declaring the match; and

e) if the candidate binary acoustic fingerprint bitmap does not match one of said at least one known binary acoustic fingerprint bitmap within the predetermined threshold, using an answering machine detection algorithm to analyze the candidate audio segment.

2. The method of claim 1, wherein step (a) comprises transforming the candidate audio segment using a transform selected from the group consisting of:

discrete fourier transform, discrete cosine transform, wavelet transform, and filter bank.

3. The method of claim 1, wherein step (b) comprises the steps of:

b.1) transforming the spectrogram data into Mel space with N+1 frames, where N is an integer;

b.2) computing N-bit binary fingerprint frame values based on band energy differences over successive frames according to the following formula;

4. The method of claim 1, wherein step (c) comprises computing a Hamming distance between the candidate binary acoustic fingerprint bitmap and the at least one known binary acoustic fingerprint bitmap.

5. The method of claim 1, wherein the predetermined threshold is a bit error rate.

6. A method for identifying a candidate audio segment from an outbound telephone call, the method comprising the steps of:

a) creating a spectrogram of the candidate audio segment;

b) creating a candidate binary fingerprint bitmap of the spectrogram;

c) comparing the candidate binary fingerprint bitmap to at least one known binary fingerprint bitmap of a known recording;

d) if the candidate binary fingerprint bitmap matches one of said at least one known binary fingerprint bitmaps within a predetermined threshold, declaring the match; and

e) if the candidate binary fingerprint bitmap does not match one of said at least one known binary fingerprint bitmap within the predetermined threshold, using an alternate process to analyze the candidate audio segment.

7. The method of claim 6, wherein said candidate binary fingerprint bitmap and said known binary fingerprint bitmap each comprise an acoustic fingerprint bitmap.

8. The method of claim 6, wherein said recording comprises a network message.

9. The method of claim 6, wherein said alternate process comprises a process selected from the group consisting of:

an answering machine detection algorithm, a voice activity detection algorithm, and a call progress analysis algorithm.

10. The method of claim 6, wherein step (a) comprises transforming the candidate audio segment using a transform selected from the group consisting of:

discrete fourier transform, discrete cosine transform, wavelet transform, and filter bank.

11. The method of claim 7, wherein step (b) comprises the steps of:

b.1) transforming the spectrogram data into Mel space with N+1 frames, where N is an integer;

b.2) computing N-bit binary fingerprint frame values based on band energy differences over successive frames according to the following formula;

12. The method of claim 6, wherein step (c) comprises computing a Hamming distance between the candidate binary fingerprint bitmap and the at least one known binary fingerprint bitmap.

13. The method of claim 6, wherein the predetermined threshold is a bit error rate.

14. A method for creating a ternary bitmap of an audio database from an outbound call, the method comprising the steps of:

a) computing a binary fingerprint bitmap of the dataset;

b) deleting a first number of samples from the dataset;

c) after step (b), computing another binary fingerprint bitmap of the dataset;

d) repeating steps (b) and (c) a plurality of times to create a plurality of binary fingerprint bitmaps; and

e) combining the plurality of binary fingerprint bitmaps into the ternary bitmap, where each bit in the ternary bitmap is determined as follows;

e.1) If a bit is 0 (zero) in a first predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 0 (zero);

e.2) If a bit is 1 (one) in a second predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 1 (one); and

e.3) Otherwise, set the bit of the ternary bitmap to *, wherein * is a Don'"'"'t Care bit.

15. The method of claim 14, wherein said first number of samples comprises a first sample from the dataset.

16. The method of claim 14, wherein said first predetermined number comprises all of the plurality of binary bitmaps and said second predetermined number comprises all of the plurality of binary bitmaps.

17. The method of claim 14, wherein said first predetermined number and said second predetermined number are equal.

18. The method of claim 14, wherein the dataset is artificially degraded prior to step (a).

19. The method of claim 14, wherein said binary fingerprint bitmap comprises an acoustic fingerprint bitmap.

20. The method of claim 14, wherein said dataset comprises an audio segment.

21. The method of claim 20, wherein said audio segment comprises an audio segment from an outbound telephone call.

22. A method for identifying a candidate audio dataset, the method comprising the steps of:

a) computing a binary fingerprint bitmap of a known dataset in a known dataset database;

b) deleting a first number of samples from the known dataset;

c) after step (b), computing another binary fingerprint bitmap of the known dataset;

d) repeating steps (b) and (c) a plurality of times to create a plurality of binary fingerprint bitmaps; and

e) combining the plurality of binary fingerprint bitmaps into a ternary bitmap, where each bit in the ternary bitmap is determined as follows;

e.1) If a bit is 0 in a first predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 0;

e.2) If a bit is 1 in a second predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 1; and

e.3) Otherwise, set the bit of the ternary bitmap to *, wherein * is a Don'"'"'t Care bit;

f) saving the ternary bitmap into a ternary bitmap database;

g) repeating steps (a)-(f) for all known datasets in the known dataset database;

h) creating a candidate dataset binary fingerprint bitmap from the candidate dataset; and

i) comparing the candidate dataset binary fingerprint bitmap to each ternary bitmap in the ternary bitmap database, wherein said comparison ignores the Don'"'"'t Care bit.

23. The method of claim 22, wherein said first number of samples comprises a first sample from the dataset.

24. The method of claim 22, wherein said first predetermined number comprises all of the plurality of binary bitmaps and said second predetermined number comprises all of the plurality of binary bitmaps.

25. The method of claim 22, wherein said first predetermined number and said second predetermined number are equal.

26. The method of claim 22, wherein the dataset is artificially degraded prior to step (a).

27. The method of claim 22, wherein said binary fingerprint bitmap and said candidate binary fingerprint bitmap each comprise an acoustic fingerprint bitmap.

28. The method of claim 22, wherein said dataset comprises an audio segment.

29. The method of claim 28, wherein said audio segment comprises an audio segment from an outbound telephone call.

30. A method for creating a ternary bitmap of an audio segment from an outbound call, the method comprising the steps of:

a) computing a binary acoustic fingerprint bitmap of the audio segment;

b) deleting a first number of samples from the audio segment;

c) after step (b), computing another binary acoustic fingerprint bitmap of the audio segment;

d) repeating steps (b) and (c) a plurality of times to create a plurality of binary acoustic fingerprint bitmaps; and

e) combining the plurality of binary acoustic fingerprint bitmaps into the ternary bitmap, where each bit in the ternary bitmap is determined as follows;

e.1) If a bit is 0 in a first predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 0;

e.2) If a bit is 1 in a second predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 1; and

e.3) Otherwise, set the bit of the ternary bitmap to *, wherein * is a Don'"'"'t Care.

31. The method of claim 30, wherein said first number of samples comprises a first sample from the audio segment.

32. The method of claim 30, wherein said first predetermined number comprises all of the plurality of binary bitmaps and said second predetermined number comprises all of the plurality of binary bitmaps.

33. The method of claim 30, wherein said first predetermined number and said second predetermined number are equal.

34. The method of claim 30, wherein the dataset is artificially degraded prior to step (a).

35. The method of claim 30, wherein said audio segment comprises an audio segment from an outbound telephone call.

36. A method for identifying a candidate audio segment from an outbound call, the method comprising the steps of:

a) computing a binary acoustic fingerprint bitmap of a known audio segment in a known audio segment database;

b) deleting a first number of samples from the known audio segment;

c) after step (b), computing another binary acoustic fingerprint bitmap of the known audio segment;

d) repeating steps (b) and (c) a plurality of times to create a plurality of binary acoustic fingerprint bitmaps; and

e) combining the plurality of binary acoustic fingerprint bitmaps into a ternary bitmap, where each bit in the ternary bitmap is determined as follows;

e.

     1) If a bit is 0 in a first predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 0;

e.2) If a bit is 1 in a second predetermined number of the plurality of binary bitmaps, set the bit in the ternary bitmap to 1; and

e.3) Otherwise, set the bit of the ternary bitmap to *, wherein * is a Don'"'"'t Care;

f) saving the ternary bitmap into a ternary bitmap database;

g) repeating steps (a)-(f) for all known audio segments in the known audio segment database;

h) creating a candidate audio segment binary acoustic fingerprint bitmap from the candidate audio segment; and

i) comparing the candidate audio segment binary acoustic fingerprint bitmap to each ternary bitmap in the ternary bitmap database, wherein said comparison ignores the Don'"'"'t Care bit.

37. The method of claim 36, wherein said first number of samples comprises a first sample from the dataset.

38. The method of claim 36, wherein said first predetermined number comprises all of the plurality of binary bitmaps and said second predetermined number comprises all of the plurality of binary bitmaps.

39. The method of claim 36, wherein said first predetermined number and said second predetermined number are equal.

40. The method of claim 36, wherein the dataset is artificially degraded prior to step (a).

41. The method of claim 36, wherein said audio segment comprises an audio segment from an outbound telephone call.