[PYTHON] Versuchen Sie, einen Shazam-ähnlichen Algorithmus für Sprachfingerabdrücke zu implementieren

Wie bei Shazam wird eine Technik namens ** Audio Fingerprinting ** verwendet, um die Musikinformationen, die von der auf dem Smartphone aufgezeichneten Stimme abgespielt werden, schnell zu identifizieren (auch im Umriss des inhaltsbasierten Musikabrufs). eingeben). Diese Suchtechnologie scheint angesichts der Low-Fidelity-Klangqualität von Smartphones, Geräuschen wie Umgebungsgeräuschen und der riesigen Musikdatenbank nicht sehr einfach zu sein, wurde jedoch in der Realität vor langer Zeit in verschiedenen Diensten praktisch eingesetzt. Es wurde auch in Siri installiert. Ich denke, es gibt verschiedene Ansätze für das Ablesen von Sprachfingerabdrücken, aber die gängigste und am einfachsten zu verstehende Methode ist das "Hashing und Speichern / Abrufen von Spektrogrammspitzen". Es wird in der Nachbarschaft ** "Landmark-based Fingerprinting" ** genannt. Dieses Mal möchte ich die Fingerabdrucktechnologie mit dieser Methode implementieren. Referenz finden Sie in diesem Blog: Audio Fingerprinting with Python and Numpy Und dieses Papier: Wang, Avery. "An Industrial Strength Audio Search Algorithm." Ismir. Vol. 2003. 2003.

LabROSA hat ein Open Source-Projekt namens AUD FPRINT: AUDFPRINT - Audio fingerprint database creation + query

Spektrogrammumwandlung und Peakerkennung

STFTEN Sie zuerst das Sprachsignal und suchen Sie dann den Spitzenwert auf dem T-F-Display. Suchen Sie hier nach Art der Bildverarbeitung. Auf das Spektrogramm wird ein Scipy-Maximum-Filter angewendet, und Punkte, bei denen das Ergebnis und der Wert des ursprünglichen Spektrogramms gleich sind, werden als Peaks betrachtet (Punkte mit kleineren Werten werden unbedingt ausgeschlossen). Es kann sinnvoll sein, einen 2D-Tiefpassfilter auf die Vorverarbeitung anzuwenden.

analyze.py

def find_peaks(y,size):
    """
    y:Sprachsignal
    size:maximale Filtergröße(Kontrollieren Sie die Spitzendichte)
    """
    sgram = np.abs(stft(y,n_fft=512,hop_length=256))
    sgram_max = ndi.maximum_filter(sgram,size=size,mode="constant")
    maxima = (sgram==sgram_max) & (sgram > 0.2)
    peaks_freq,peaks_time = np.where(maxima)
    return peaks_freq,peaks_time

Mit numpy.where konnte ich eine Liste der Spitzenpunkte abrufen. Wird auch als Wahrzeichen bezeichnet.

Peak Pairing → Hashing

Ein einzelner Peak enthält nur Informationen zur Frequenz dieses Peaks (der Zeitpunkt der Abfrage ist willkürlich, sodass die Zeitposition des Peaks bedeutungslos ist) und kann nicht wie beim Hashing verwendet werden. Daher verbinden wir nahegelegene Peaks, um zwei Peaks zu einem Fingerabdruck zu machen. Dieses Spitzenpaar enthält Informationen zu ** (Frequenz von Spitze 1, Frequenz von Spitze 2, Zeitdifferenz) **, und Sie können diese Werte verketten, um einen weniger duplizierten Hash zu erstellen. Ich werde. Wie in der Abbildung gezeigt, sind insbesondere Punkte innerhalb eines bestimmten Bereichs vor ihnen verbunden, wenn sie von einem bestimmten Ankerpunkt aus betrachtet werden.

Im folgenden Code wird nach Auswahl eines Paares ** (Frequenz von Spitze 1, Frequenzdifferenz, Zeitdifferenz) ** in eine 20-Bit-Zahl gepackt und gehasht.

analyze.py

F1_BITS = 8
DF_BITS = 6
DT_BITS = 6

B1_MASK = (1<<F1_BITS) - 1
B1_SHIFT = DF_BITS + DT_BITS
DF_MASK = (1<<DF_BITS) - 1
DF_SHIFT = DT_BITS
DT_MASK = (1<<DT_BITS) - 1

def peaks_to_landmarks(peaks_freq,peaks_time,target_dist=30,target_time=30,target_freq=30):
    peak_mat = np.zeros((np.max(peaks_freq)+target_freq,np.max(peaks_time)+target_dist+target_time),dtype=np.bool)
    peak_mat[peaks_freq,peaks_time] = True
    list_landmarks = []
    for pfreq,ptime in zip(peaks_freq,peaks_time):
        #(pfreq,ptime) -- current anchor
        target_mask = np.zeros(peak_mat.shape,dtype=np.bool)
        target_mask[pfreq-target_freq:pfreq+target_freq,ptime+target_dist:py+target_dist+target_time] = 1
        #target_mask:Geben Sie den Bereich an, in dem der Zielpeak ausgewählt werden soll
        targets_freq,targets_time = np.where(peak_mat & target_mask)
        for pfreq_target,ptime_target in zip(targets_freq,targets_time):
            dtime = ptime_target-ptime
            #Erstellen Sie einen Hash
            hsh = (((pfreq & B1_MASK)<<B1_SHIFT) | (((pfreq_target+target_freq-pfreq)&DF_MASK)<<DF_SHIFT)|(dtime&DT_MASK))
            list_landmarks.append((hsh,ptime))   #Speichern Sie Hash und Peak 1 Mal
        
        
    return list_landmarks

Dieser Hash-Wert ist mit ** (Song-ID, Peak-1-Zeitposition) ** verknüpft und in der Hash-Tabelle registriert. Ich verwende ein Python-Wörterbuchobjekt.

#hash_table:Python-Wörterbuchobjekt
for landmark in list_landmarks:
    hsh = landmark[0]
    starttime = landmark[1]
    if hash_table.has_key(hsh):
        hash_table[hsh].append((audio_id,starttime))
    else:
        hash_table[hsh] = [(audio_id,starttime)]

Speichern Sie alle Hashes mit dem Pickle-Modul, nachdem Sie sie registriert haben.

Abfrage

In einer Datenbank wurden insgesamt 497 Songs erstellt, die als Datensatz für die Akkordfortschrittserkennung verwendet werden. Es hat lange gedauert, aber die Größe des eingelegten Hash-Tisches betrug ungefähr 250 MB. Als Test habe ich Beatles ** "Back In the U.S.S.R" ** aus dem Datensatz gespielt und mit einem Taschenrekorder eine Aufnahme von ca. 10 Sekunden gemacht. Es ist eine ziemlich ideale Aufnahme, weil sie in Innenräumen aufgenommen wurde, aber ich werde es versuchen. Ich habe die aufgezeichnete Stimme auf die gleiche Weise wie oben eingestellt, den Peak erkannt und den Fingerabdruck (Hash-Wert) gefunden. Wie kommst du von hier zu dem Song? Ich habe eine Datenbankklasse geschrieben, die Hash-Tabellen und Abfragen verwaltet.

Database.py

DIFF_RANGE = 2000000

class Database:
    def __init__(self):
        with open("hashtable.pkl","rb") as f:
            self.hash_table = pickle.load(f)
        with open("titlelist.pkl","rb") as f:
            self.title_list = pickle.load(f)
    #Methode 1
	def query_histogram(self,y,best=5):
		list_landmarks = analyze.extract_landmarks(y)
		id_candidates = self._find_candidate_id(list_landmarks)
		candidate_landmark_histogram = np.zeros(id_candidates.size,dtype=np.int32)
		for landmark in list_landmarks:
			hsh = landmark[0]
			if self.hash_table.has_key(hsh):
				hit_ids = [item[0] for item in self.hash_table[hsh]]
				for i in hit_ids:
					candidate_landmark_histogram[np.where(id_candidates==i)[0]] += 1
			else:
				continue
		
		idxsort = np.argsort(candidate_landmark_histogram)[::-1]
		title_sort = self.title_list[id_candidates[idxsort]]
		fingerprint_histogram_sort = candidate_landmark_histogram[idxsort]
		return title_sort[:best],fingerprint_histogram_sort[:best]

    #Methode 2
    def query_diff_histogram(self,y,best=5):
        list_landmarks = analyze.extract_landmarks(y)
        id_candidates = self._find_candidate_id(list_landmarks)
        diff_histogram = np.zeros((id_candidates.size,DIFF_RANGE),dtype=np.int32)
        diff_start_offset = np.zeros(id_candidates.size,dtype=np.int32)
        
        for landmark in list_landmarks:
            hsh_query = landmark[0]
            offset_query = landmark[1]
            if self.hash_table.has_key(hsh_query):
                hits = self.hash_table[hsh_query]
                for hit in hits:
                    id_hit = hit[0]
                    offset_hit = hit[1]
                    diff = offset_hit - offset_query
                    if diff >= 0:
                        id_hist = np.where(id_candidates==id_hit)[0]
                        diff_histogram[id_hist,diff] += 1
                        diff_start_offset[id_hist] = min([diff_start_offset[id_hist],offset_query])
            else:
                continue
            
        candidate_match_score = np.max(diff_histogram,axis=1)
        candidate_max_offset = np.argmax(diff_histogram,axis=1)
        idxsort = np.argsort(candidate_match_score)[::-1]
        title_sort = self.title_list[id_candidates[idxsort]]
        match_score_sort = candidate_match_score[idxsort]
        best_match_offset = (candidate_max_offset[idxsort[0]] - diff_start_offset[idxsort[0]]) * 256/11025.0
        return title_sort[:best],match_score_sort[:best],best_match_offset
        
                    
                    
    def _find_candidate_id(self,landmarks):
        candidate = set()
        for landmark in landmarks:
            hsh = landmark[0]
            if self.hash_table.has_key(hsh):
                id_hits = [item[0] for item in self.hash_table[hsh]]
                candidate = candidate.union(id_hits)
            else:
                continue
            
        return np.array(list(candidate),dtype=np.int32)

analyse.extract_landmarks (y) integriert Peakerkennung und Hashing.

analyze.py

def extract_landmarks(y,peak_dist=20):
    peaks_x,peaks_y = find_peaks(y,peak_dist)
    landmarks = peaks_to_landmarks(peaks_x,peaks_y)
    return landmarks

1. Zählen Sie die Anzahl der Treffer

Entspricht Database.query_histogram. Jeder in der Datenbank registrierte Hash ist einer Song-ID (einer oder mehreren) zugeordnet. Überprüfen Sie alle in der Aufnahme enthaltenen Hashes, zählen Sie die Anzahl der Treffer für das Lied, und das Lied mit den meisten Treffern ist die richtige Antwort. Dies ist die einfachste Methode, aber was ist mit der Leistung? Ich habe versucht, die Top 5 Songs mit der Anzahl der Treffer anzuzeigen.

Die Abfrage dauerte ungefähr 0,5 Sekunden (Ladezeit der Hash-Tabelle ist nicht möglich). Die meisten Hash-Übereinstimmungen mit dem Original-Song von Back In The U.S.S.R. Es ist eine richtige Antwort, aber der Unterschied zu anderen Songs ist nicht so auffällig. Wenn die Aufnahme etwas schlechter ist, wird es bald eine falsche Antwort geben. Ein weiteres Problem ist, dass Sie mit dieser Methode nicht herausfinden können, mit welchem Teil des Songs die Aufnahme übereinstimmt. Es kann je nach Anwendung nicht notwendig sein, aber ich würde es trotzdem gerne wissen.

2. Zählen Sie Fingerabdrücke, die "in Linie" sind.

Wählen Sie das richtige Lied und die beiden anderen Lieder aus und zeichnen Sie die Abfragestimme und die Nummer ** (Zeitposition in der Originalstimme, Zeitposition in der Aufnahme) ** des getroffenen Fingerabdrucks in der 2D-Ebene.

Selbst wenn das Lied falsch ist, kann die Anzahl der Treffer im Hash moderat sein, aber die Verteilung der Punkte ist in jedem Fall unterschiedlich. Auf der anderen Seite gibt es in der richtigen Übereinstimmung (oberste Darstellung) einen Teil, in dem die Punkte diagonal ausgerichtet sind. Dies bedeutet, dass der Fingerabdruck innerhalb eines bestimmten Zeitraums ein kontinuierlicher Treffer ist. Aus diesem Grund speichern Sie beim Registrieren des Hash die Zeitposition im Original-Song. Daher wird derjenige mit vielen "aufgereihten" Fingerabdrücken als die richtige Antwort beurteilt. Da sie diagonal ausgerichtet sind, dh die Differenz zwischen x und y eine Konstante ist (auf der Geraden x-y = b), wird für jedes Lied ein Histogramm von (x-y) erhalten, und der Maximalwert wird als Punktzahl angesehen. Entspricht Database.query_diff_histogram. Das Ergebnis ist hier.

Es ist leicht zu verstehen und es gibt einen Unterschied. Die Abfrage dauerte ca. 1,8 Sekunden. Es scheint Raum für Verbesserungen bei der Effizienz der Implementierung zu geben, aber dies ist als Beweis für das Prinzip in Ordnung. Die Berechnungsmenge ist N (die Anzahl der Hashes der Abfragestimme), daher sollte sie sich nicht wesentlich verschlechtern, selbst wenn die Datenbank größer wird. Der best_match_offset des Quellcodes ermittelt die Position der Abfragestimme im Original-Song. Dies löste auch das Problem, wo es übereinstimmte.

Weitere Verbesserungsmaßnahmen

Es ist zu beachten, dass diese Methode auf der Annahme basiert, dass ** "das ursprüngliche Lied und die Abfrage die gleiche Wiedergabegeschwindigkeit und keine Modulation haben" **. Wenn sich die Wiedergabegeschwindigkeit oder die Gesamtmodulation ändert, vergrößert und verkleinert sich der relative Zeitabstand zwischen den Orientierungspunkten und dem Frequenzabstand (aufgrund des linearen Frequenzbereichs), sodass es unmöglich ist, mit Hash übereinzustimmen. In der Praxis ist dies kein großes Problem, aber es wurde eine Lösung vorgeschlagen.

• Frequenzprobleme: Verwenden Sie CQT (Constant-Q Transform) anstelle von FFT. Im logarithmischen Frequenzbereich sollte sich der relative Abstand der Frequenzen nicht ändern (es ist schwer zu ändern), selbst wenn eine Modulation auftritt. Es scheint, dass derjenige, der von FFT in den logarithmischen Frequenzbereich konvertiert wurde, ebenfalls gut ist.
• Probleme mit der Wiedergabegeschwindigkeit: Verbinden Sie drei oder mehr Orientierungspunkte und speichern Sie das "Verhältnis" ihrer Zeitdistanz in einem Hash. Wenn es sich um ein Verhältnis handelt, sollte es sich nicht ändern (es ist schwer zu ändern), selbst wenn sich die Wiedergabegeschwindigkeit ändert. Da es sich jedoch um reelle Zahlen anstelle von ganzen Zahlen handelt, wird die Robustheit des Hashs selbst wahrscheinlich erheblich abnehmen.

Zusammenfassung

Ich habe einen einfachen Algorithmus für Fingerabdrücke eingeführt. audfprint basiert ebenfalls auf Orientierungspunkten, aber die Erkennung und Abfrage von Spitzen scheint auch auf etwas andere Weise implementiert zu sein. Möglicherweise möchten Sie den Quellcode lesen. Wenn Sie es verstehen können, würde ich gerne einen weiteren Artikel schreiben.