6 ms·

Hello HN, I've been working for some time on an algorithm for recovering unknown text just by analyzing the recorded audio of a person tapping on their keyboard

Hello HN, I've been working for some time on an algorithm for recovering unknown text just by analyzing the recorded audio of a person tapping on their keyboard (i.e. acoustic eavesdropping). In this post, I present my new approach which I think is quite interesting - it matches detected keystrokes with each other based on their sound similarity and converts the problem of recovering the unknown text into a problem of breaking a substitution cipher! The great advantage of this method is that it does not require prior training - it exploits the n-gram frequencies in the English language. Would love to hear your thoughts and suggestions about this.

cnity 6y ago
Hey. I've been working on an audio recognition tool that is remarkably similar to this one, and there are a few areas I strongly recommend exploring if you want to improve the classification performance. For waveform similarity, you may achieve better results by comparing the spectrogram (computed by taking the FFT of each "clack") instead of comparing the time domain signal. Next, the best performing sound classification algorithms (at least in music note classification, which is a very similar problem to yours) utilise non-negative matrix factorisation[0] to do the comparison against a bank of note templates. I recommend reading "Real-time Polyphonic Music Transcription with Non-negative Matrix Factorization and Beta-divergence" (Dessein et. al.) for a more comprehensive description of the algorithm[1]. I actually tried applying my algorithm to detect taps on different parts of my laptop for fun, so that I could send keyboard events when e.g. I tap the bottom right corner of my laptop, and it was quite effective. The approach is incredibly accurate for classification of short spectrograms. Feel free to reach out to me if you want to discuss a bit more. [0] https://en.wikipedia.org/wiki/Non-negative_matrix_factorization https://en.wikipedia.org/wiki/Non-negative_matrix_factorizat... [1] https://www.researchgate.net/publication/220723421_Real-time_Polyphonic_Music_Transcription_with_Non-negative_Matrix_Factorization_and_Beta-divergence https://www.researchgate.net/publication/220723421_Real-time... Edit: Also, this is great work. I don't mean to denigrate it at all.
- ggerganov 6y ago
  Thank you for these suggestions! The idea for comparing sounds in the frequency domain was something that I was considering, but couldn't figure out a proper way to do it. I will definitely check the resources that you provided and see if I can utilize this approach in Keytap.
- waffletower 6y ago
  I don't recommend using DFT (FFT) analysis unless you can constrain N to small sizes (<= 256 at 44.1KHz sampling rate perhaps) to reduce time aliasing. Use of wavelets may be a better fit for this application.
  - ggerganov 6y ago
    I have found that I need to use about 75-100 ms of audio around the keystroke-down peak when comparing waveforms. At the sample rate that I am using - 16kHz, I would probably need samples of size about 1024 - 2048. Not sure if this is feasible, just giving some additional info.
    - cnity 6y ago
      If you want to compute an FFT with fewer bins you can also use STFT and configure the bin count and hop size (essentially computing many FFTs of smaller regions of the signal and computing the average). A quick side note, 16kHz is quite a low sample rate for your use case, since you won't be able to capture frequencies over 8kHz (the Nyquist frequency), and key clicks at least intuitively I'd imagine to contain a lot of detail at higher frequencies. I have no data to back this up though!
      - ggerganov 6y ago
        Regarding the sampling rate: I switched down to 16kHz from 48kHz, because I found that with my approach there wasn't much of a difference in the key-matching performance. At the same time, I gained computational performance. At some point, I was looking at the spectrum of the key sounds and I think that almost the entire signal is in the lower few kHz. It might be just my keyboard - not sure. I still have the tool, so I can easily check if there is some high-frequency portion that I am missing.
raxxorrax 6y ago
Very interesting problem. Naively I would have thought every keystroke sounds the same aside from special keys like space or enter. Apparently this is not the case. Like the other comment suggested, a frequency analysis might help. Here is a good explanation you could quickly use in C++: https://unix4lyfe.org/dct-1d/ https://unix4lyfe.org/dct-1d/ Otherwise popular libraries like openCV have tools to convert signals, but most are focused on imaging (2d signals).
- jlokier 6y ago
  > Naively I would have thought every keystroke sounds the same Even if the keystroke sounds were identical at source, the acoustic environment between the key and mics (key position, shape of the surrounding keyboard area, position of hands, screen etc.) adds its own unique reverb signature too. Speaking of mics - a lot of laptops have stereo mics. That's enough to start locating the acoustic source spatially by phase, in addition to the other characteristics.

cnity 6y ago

Hey. I've been working on an audio recognition tool that is remarkably similar to this one, and there are a few areas I strongly recommend exploring if you want to improve the classification performance. For waveform similarity, you may achieve better results by comparing the spectrogram (computed by taking the FFT of each "clack") instead of comparing the time domain signal. Next, the best performing sound classification algorithms (at least in music note classification, which is a very similar problem to yours) utilise non-negative matrix factorisation[0] to do the comparison against a bank of note templates. I recommend reading "Real-time Polyphonic Music Transcription with Non-negative Matrix Factorization and Beta-divergence" (Dessein et. al.) for a more comprehensive description of the algorithm[1]. I actually tried applying my algorithm to detect taps on different parts of my laptop for fun, so that I could send keyboard events when e.g. I tap the bottom right corner of my laptop, and it was quite effective. The approach is incredibly accurate for classification of short spectrograms. Feel free to reach out to me if you want to discuss a bit more. [0] https://en.wikipedia.org/wiki/Non-negative_matrix_factorization https://en.wikipedia.org/wiki/Non-negative_matrix_factorizat... [1] https://www.researchgate.net/publication/220723421_Real-time_Polyphonic_Music_Transcription_with_Non-negative_Matrix_Factorization_and_Beta-divergence https://www.researchgate.net/publication/220723421_Real-time... Edit: Also, this is great work. I don't mean to denigrate it at all.

ggerganov 6y ago
Thank you for these suggestions! The idea for comparing sounds in the frequency domain was something that I was considering, but couldn't figure out a proper way to do it. I will definitely check the resources that you provided and see if I can utilize this approach in Keytap.
waffletower 6y ago
I don't recommend using DFT (FFT) analysis unless you can constrain N to small sizes (<= 256 at 44.1KHz sampling rate perhaps) to reduce time aliasing. Use of wavelets may be a better fit for this application.
- ggerganov 6y ago
  I have found that I need to use about 75-100 ms of audio around the keystroke-down peak when comparing waveforms. At the sample rate that I am using - 16kHz, I would probably need samples of size about 1024 - 2048. Not sure if this is feasible, just giving some additional info.
  - cnity 6y ago
    If you want to compute an FFT with fewer bins you can also use STFT and configure the bin count and hop size (essentially computing many FFTs of smaller regions of the signal and computing the average). A quick side note, 16kHz is quite a low sample rate for your use case, since you won't be able to capture frequencies over 8kHz (the Nyquist frequency), and key clicks at least intuitively I'd imagine to contain a lot of detail at higher frequencies. I have no data to back this up though!
    - ggerganov 6y ago
      Regarding the sampling rate: I switched down to 16kHz from 48kHz, because I found that with my approach there wasn't much of a difference in the key-matching performance. At the same time, I gained computational performance. At some point, I was looking at the spectrum of the key sounds and I think that almost the entire signal is in the lower few kHz. It might be just my keyboard - not sure. I still have the tool, so I can easily check if there is some high-frequency portion that I am missing.

raxxorrax 6y ago

Very interesting problem. Naively I would have thought every keystroke sounds the same aside from special keys like space or enter. Apparently this is not the case. Like the other comment suggested, a frequency analysis might help. Here is a good explanation you could quickly use in C++: https://unix4lyfe.org/dct-1d/ https://unix4lyfe.org/dct-1d/ Otherwise popular libraries like openCV have tools to convert signals, but most are focused on imaging (2d signals).

jlokier 6y ago
> Naively I would have thought every keystroke sounds the same Even if the keystroke sounds were identical at source, the acoustic environment between the key and mics (key position, shape of the surrounding keyboard area, position of hands, screen etc.) adds its own unique reverb signature too. Speaking of mics - a lot of laptops have stereo mics. That's enough to start locating the acoustic source spatially by phase, in addition to the other characteristics.