Refine
Document Type
- Preprint (2) (remove)
Language
- English (2) (remove)
Has Fulltext
- yes (2)
Keywords
- Audio Hashing (1)
- Extremal radial graphs (1)
- Hash-Algorithmus (1)
- Minimal non-planarity (1)
- Radial graphs (1)
- Telephone Spam Detection (1)
- Wavelet Transform (1)
- Wavelet-Transformation (1)
Faculty
A level graph G = (V,E,λ) is a graph with a mapping λ : V → {1,...,k}, k ≥ 1, that partitions the vertex set V as V = V1 ∪...∪ Vk, Vj = λ-1(j), Vi ∩ Vj = ∅ for i ≠ j, such that λ(v) = λ(u) + 1 for each edge (u, v) ∈ E. Thus a level planar graph can be drawn with the vertices of every Vj, 1 ≤ j ≤ k, placed on a horizontal line, representing the level lj , and without crossings of edges, which can be drawn as straight line segments between the levels. Healy, Kuusik and Leipert gave a complete characterization of minimal forbidden subgraphs for level planar graphs (MLNP patterns) for hierarchies [4]. Minimal in terms of deleting an ar- bitrary edge leads to level planarity. A radial graph partitions the vertex set on radii, which can be pictured as concentric circles, instead of levels, lj = (j cos(α), j sin(α)), α ∈ [0,2π), mapped around a shared center, where j, 1 ≤ j ≤ k indicates the concentric circles’ radius. Comparing embeddings of radial graphs with that of level graphs we gain a further possibility to place an edge and eventually avoid edge crossings which we wish to prevent for planarity reasons. This offers a new set of minimal radial non planar subgraphs (MRNP patterns). Some of the MLNP pat- terns can be adopted as MRNP patterns while some turn out to be radial planar. But based on the radial planar MLNP patterns and the use of augmentation we can build additional MRNP patterns that did not occur in the level case. Furthermore we point out a new upper bound for the number of edges of radial planar graphs. It depends on the subgraphs in- duced between two radii. Because of the MRNP patterns these subgraphs can either consist of a forest or a cycle with several branches. Applying the bound we are able to characterize extremal radial planar graphs. Keywords: radial graphs, minimal non-planarity, extremal radial planar
For audio signals, we use the sign of the coefficients of the redundant discrete wavelet transform to generate primary hash vectors assigning bit 1 to positive or zero coefficients and bit 0 in the negative case. Discarding the highest frequency band and using a 6 step transform we get for each sample a 6 bit primary hash value which we may save as an integer. We then select a possible primary hash value (in our experiments we chose 0 or 63) and take the time indices where this primary hash value occurs as the secondary hash vector which is attributed to the whole audio signal. Comparing two audio signals, the number of elements in the intersection of the corresponding time indices are called "number of matches", a high number may indicate a similarity between the files. This secondary hash vector turns out to be robust against addition of noise, GSM-, G.726-, MP3 coding and packet loss. It may therefore be useful to detect spam telephone calls without analyzing the semantic content by the similarity of the corresponding signals. An algorithm is given to detect similar but shifted signals. Results of experiments are reported using a test corpus of 5 000 audio files of regular calls and 200 audio files of different versions of 20 original spam recordings augmented by a set of 45 files of different versions of 9 "special spam" signals.