Matrix-Downsampling-Filter 50M Punkte

Matrixfilter für pixelgenaues Downsampling von Streudiagrammen mit 50 Mio. Punkten

Der Matrixfilter sorgt für 100% Abdeckung und visuelle Treue beim Rendern von 50 Millionen Druckpunkten aus Bohrlöchern. Traditionelle Algorithmen wie LTTB verlieren bis zu 59% der Datenintensität. Dieser Ansatz arbeitet in einem Durchgang ohne Sortierung und begrenzt die Ausgabe auf die Bildschirmpixelanzahl.

Streudiagramme sind essenziell für unregelmäßige Daten mit Lücken: Linien verzerren Unterbrechungen und verbergen Cluster. Standardmethoden sind für Liniendiagramme optimiert und übersehen die 2D-Struktur.

Grenzen traditioneller Algorithmen

MinMax, M4, LTTB und Hybride teilen die X-Achse in Bins ein und wählen 1–4 Y-Punkte pro Bin. In dichten Spalten werfen sie 96–99% der Daten weg: Wolken kollabieren zu Extremwerten.

• MinMax: Minimum und Maximum — erfasst Spitzen, ignoriert Verteilung.
• M4: Erster, letzter, Min/Max — pixelgenau für Linien.
• LTTB: Größtes Dreiecksareal — Silhouette von Kurven.
• MinMaxLTTB: Fixiert Extreme, dann Glättung.

Bei Streudiagrammen ist das ein grundlegender Mangel: Algorithmen ignorieren Y-Koordinaten innerhalb der Bins.

Funktionsweise des Matrixfilters

Ähnlich dem Voxel-Grid-Filter in der Grafik: Projiziert Punkte auf ein W×H-Pixelgitter. Pro Zelle bleibt ein Punkt in Traversierungsreihenfolge.

public static void downsample(
        double[] times, double[] values,
        int width, int height,
        List<double[]> result) {

    int n = times.length;
    if (n == 0) return;

    // Schritt 1: Grenzen
    double tMin = times[0], tMax = times[0];
    double vMin = values[0], vMax = values[0];
    for (int i = 1; i < n; i++) {
        if (times[i]  < tMin) tMin = times[i];
        if (times[i]  > tMax) tMax = times[i];
        if (values[i] < vMin) vMin = values[i];
        if (values[i] > vMax) vMax = values[i];
    }
    double tRange = Math.max(tMax - tMin, 1e-10);
    double vRange = Math.max(vMax - vMin, 1e-10);

    // Schritt 2: Gitter
    boolean[] grid = new boolean[width * height];

    // Schritt 3: Filter
    for (int i = 0; i < n; i++) {
        int px = (int) Math.min(width  - 1, (times[i]  - tMin) / tRange * (width  - 1));
        int py = (int) Math.min(height - 1, (values[i] - vMin) / vRange * (height - 1));
        int idx = py * width + px;
        if (!grid[idx]) {
            grid[idx] = true;
            result.add(new double[]{times[i], values[i]});
        }
    }
}

Die Methode ahmt das Rendern nach: Sie beleuchtet Pixel, die mit dem vollen Datensatz leuchten würden. Sie ist strikt für Visualisierung gedacht, nicht für Statistik.

Testmethodik

~3000 Telemetriedatensätze von Bohrlöchern: 19k bis 50M+ Punkte. Pixel-für-Pixel-Vergleich mit Originalen in Streu- (2×2px) und Linienmodus (1px).

Metriken:

• Abdeckung: % der Originalpixel, die vom Algorithmus abgedeckt werden.
• Präzision: % der Algorithmus-Pixel im Original.
• F1-Score: Harmonisches Mittel.
• Visueller Score: F1 mit ±1px Toleranz (Subpixel-Berücksichtigung).

Klassische Algorithmen mit Budget angepasst an MatrixFilter-Ausgabe bei 1920×1080. Benchmark: i7-7700K, Java 17, Single-Thread.

Ergebnisse mit Real-Daten

Regelmäßig (~20k Punkte, 2930 Dateien)

Streu: MatrixFilter 1920×1080 — 100% bei allen Metriken. MatrixFilter 800×600 — Visuell 99,6%, halb so viele Punkte. Klassiker: Abdeckung 63–84%, Visuell 76–95%.

| Algorithmus | Ø Ausgabe | Gesamt ms | Abdeck. | Präz. | F1 | Visuell |

|------------------|-----------|-----------|---------|-------|------|---------|

| Matrix 1920×1080 | 4939 | 695 | 100% | 100% | 100% | 100% |

| Matrix 800×600 | 2867 | 497 | 84,6% | 100% | 91,5%| 99,6% |

| MinMaxLTTB x4 | 4932 | 494 | 84,1% | 100% | 90,9%| 95,2% |

Mittelgroß und Groß

Bei 500k–50M Punkten hält Matrix 100% Visuell bei ~ms/10k Punkten. LTTB fällt auf 16–40% Abdeckung bei dichten Daten.

Wichtige Erkenntnisse

• Matrixfilter liefert pixelgenaue Streus ohne Sortierung, O(n)-Zeit.
• Traditionelle Algorithmen verlieren dichte Wolkenstrukturen, selbst bei großzügigem Budget.
• Visueller Score mit ±1px passt zur Wahrnehmung: Matrix 800×600 ist vom Vollrender ununterscheidbar.
• Strikt für Visuals: Für Linien/Statistik andere Methoden nutzen.
• Getestet an industriellen Ölfeld-Datensätzen mit unregelmäßigen Lücken.

— Editorial Team