Pixel-perfect Downsampling — идеальная отрисовка 50 миллионов точек без потерь

Вот что видит пользователь, когда мы рисуем график давления в скважине за два года — 50 миллионов точек:

Мы решаем эту задачу через матричный фильтр. На датасете в 50 млн точек это даёт ~100% Coverage, ~100% Visual Score. LTTB на тех же данных — 16.4% и 40.8% соответственно. По производительности мы остаёмся в тех же пределах.

Под катом — почему стандартные алгоритмы фундаментально не подходят для scatter-графиков, как устроен наш подход и результаты бенчмарка на ~3 000 реальных промышленных датасетах от 19 тысяч до 50+ миллионов точек.

---

Сразу важный дисклеймер: для примера выше мы намерено выбрали худший кейс, чтобы отобразить проблему наглядно.

Большинство систем визуализации работают с линейными графиками — и для них классические алгоритмы даунсемплинга справляются. При правильном подборе алгоритма и бюджета точек артефакты минимальны или незаметны.

Проблема начинается там, где линия — это не упрощение, а искажение. Она соединяет точки, между которыми ничего не происходило, сглаживает разрывы и создаёт ложную непрерывность. В таких случаях единственный честный способ визуализации — scatter-график.

Почему мы используем scatter, а не line chart

Наш контекст — исследование нефтяных скважин: десятки лет данных в одной куче, где ручные единичные замеры соседствуют со старой нестабильной телеметрией и современными высокоточными датчиками. У нас три конкретные причины:

Технические пропуски — не пустота, а слепая зона. Когда запись прерывается из-за сбоя, давление в этот момент могло вести себя как угодно. Линия соединит точки до и после разрыва плавным переходом — и исследователь увидит «стабильную работу» там, где была авария. Точки честно показывают: здесь данных нет.

Нерегулярная дискретность делает алгоритм соединения невозможным. Разные датчики, разные эпохи, разные частоты записи. Чтобы корректно рвать линию там, где пропуск слишком большой — нужен порог. Универсального порога не существует. Точкам правила соединения не нужны вообще.

Паттерны лучше видны без линий. Мы ищем конкретные режимы и аномалии. На scatter-графике глаз сразу считывает плотность, кластеры и выбросы. Линии создают визуальный шум, который эти паттерны скрывает.

Стандартные алгоритмы проектировались под line chart — они оптимизируют сохранение формы кривой, а не структуры данных.

Как работают классические алгоритмы даунсемплинга

Почти все популярные алгоритмы работают по одному принципу: разбивают ось времени на интервалы («корзины») и по определённой логике выбирают из каждой корзины одну или несколько точек.

MinMax — самый простой и быстрый. Из каждого интервала берёт две точки: минимум и максимум по Y. Все пики и провалы сохраняются, но распределение данных внутри корзины полностью теряется.

M4 — разбивает время на интервалы шириной в один пиксель и для каждого берёт четыре точки: первую, последнюю, минимум и максимум. Для линейных графиков даёт практически pixel-perfect результат.

LTTB (Largest Triangle Three Buckets) — де-факто стандарт для фронтенда. В каждой корзине ищет точку, которая образует треугольник наибольшей площади с соседними корзинами. Отлично сохраняет визуальный «силуэт» линии.

MinMaxLTTB — гибрид: сначала MinMax фиксирует критические экстремумы, затем LTTB сглаживает результат. Попытка совместить точность пиков и визуальную гладкость.

---

Van Der Donckt J., Van Der Donckt J., Van Hoecke S. tsdownsample: high-performance time series downsampling for scalable visualization // SoftwareX. — 2025. — arXiv:2307.05389

Все они работают только вдоль оси X. Возьмём пиксельный столбец, в который попало 100 точек, разбросанных по всей высоте экрана: MinMax оставит 2, M4 — 4, LTTB — 1. Для линейного графика этого достаточно — линия сама закроет вертикаль между крайними точками. На scatter-графике мы потеряем 96–99% данных в этом столбце: плотное облако схлопнется в редкий скелет из экстремумов. Форма кривой сохранится, внутренняя структура — нет.

Матричный фильтр: двумерное прореживание

Принцип, который мы используем, давно известен в компьютерной графике под названием Voxel Grid Filter. Ключевой принцип: пространство разбивается на дискретную сетку ячеек, внутри каждой сохраняется только одна точка, избыточная плотность отсекается. Мы проецируем эту логику на плоскость, где роль вокселей играют физические пиксели экрана.

Входные данные: два массива double[] times, double[] values. Разрешение области построения W × H в пикселях. Порядок точек роли не играет — в отличие от LTTB и M4, алгоритму не нужна сортировка по времени.

Шаг 1 — Границы. Один проход по массивам: находим tMin, tMax, vMin, vMax. Если метаданные уже известны из БД, шаг пропускается.

Шаг 2 — Сетка. Создаём плоский булев массив размером W × H. Это виртуальная проекция будущего графика на пиксели экрана, изначально пустая.

Шаг 3 — Фильтрация. Для каждой точки вычисляем её пиксельные координаты (px, py) и проверяем ячейку grid[py * W + px]. Если пиксель свободен — точка попадает в результат, пиксель помечается занятым. Если занят — точка отбрасывается.

public static void downsample(        double[] times, double[] values,        int width, int height,        List<double[]> result) {    int n = times.length;    if (n == 0) return;    // Шаг 1: границы    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);    // Шаг 2: сетка    boolean[] grid = new boolean[width * height];    // Шаг 3: фильтрация    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]});        }    }}

Максимальный размер выходного массива ограничен W × H — числом пикселей экрана. На практике он всегда меньше: точки распределены неравномерно, и большинство пикселей остаются пустыми.

Почему это работает: рендеринг против математики

Секрет визуального сходства в том, что матричный фильтр решает задачу не математического сжатия ряда, а прямого рендеринга.

Классические алгоритмы прореживают данные вдоль оси X, сохраняя форму кривой. В плотных участках они неизбежно оставляют пустоты. Матричный фильтр переносит задачу в плоскость монитора: вычисляет, какие пиксели активировались бы при отрисовке всех точек, и оставляет ровно по одной точке на каждый такой пиксель.

Из этого следует важное ограничение. Метод оптимизирован под отрисовку — и только под неё. Какая именно точка остаётся из группы, попавшей в один пиксель, определяется порядком обхода, а не аналитической значимостью. Для задач, где важна выборка как таковая — статистика, дальнейшие вычисления, экспорт — этот подход не подходит. Его область применения строго одна: показать данные так, как они выглядели бы при полной отрисовке.

Методология тестирования: как измерить «идеальность» графика

Все тесты проводились на реальной исторической телеметрии — логах забойного давления нефтяных скважин. В этих данных есть всё: долгие базовые линии, плавные тренды, периодические колебания, резкие пики от остановок и запусков и большие пропуски в записях.

Тестовый стенд

Тесты запускались в один поток:

• CPU: Intel Core i7-7700K (4.20 GHz)

• RAM: 32 ГБ

• ОС: Windows 10 Pro

• Стек: Java 17 (OpenJDK), тесты через JUnit 5

Каждый датасет прогонялся через 6 алгоритмов: MatrixFilter 1920×1080 (эталон), MatrixFilter 800×600 (оценка работы при меньшем разрешении), M4, MinMax, LTTB и MinMaxLTTB (×4).

Бюджет точек для классических алгоритмов определялся через сам матричный фильтр: сначала запускается MatrixFilter 1920×1080, и количество точек на его выходе становится targetSize для всех остальных. Это заведомо щедрый лимит — классическим алгоритмам для качественного line chart достаточно числа точек, соизмеримого с количеством пиксельных столбцов на изображении. Мы даём им больше: столько, сколько нужно для полного двумерного покрытия.

Как мы оценивали качество визуализации

Для каждого алгоритма мы строили график в виртуальном буфере и сравнивали его попиксельно с графиком по сырым, непрореженным данным.

Сравнение проводилось в двух режимах рендера:

1. Scatter — точки размером 2×2 пикселя, без соединительных линий.

2. Lines — классические линии толщиной 1px.

Метрики:

• Coverage — процент пикселей оригинала, которые покрыл алгоритм. Не потеряли ли мы данные?

• Precision — процент закрашенных пикселей алгоритма, присутствующих в оригинале. Не нарисовали ли мы лишнего?

• F1-score — гармоническое среднее Coverage и Precision.

• Visual Score — тот же F1, но с допуском ±1 пиксель. Из-за округлений координат точка может сдвинуться на субпиксель: строгий F1 это фиксирует, глаз — нет. Visual Score ближе к реальному восприятию.

Датасеты

Данные разбиты на 3 группы:

1. Regular (2 930 файлов, в среднем ~20 000 точек). Основной датасет для оценки качества: широкий охват разных типов кривых, датчиков и режимов записи. Акцент здесь не на скорости — на том, как точно алгоритмы воспроизводят scatter и line chart после прореживания.

2. Medium (24 файла, в среднем ~500 000 точек). Данные за периоды от нескольких месяцев до года непрерывной записи.

3. Large (13 файлов, в среднем ~25 000 000 точек, максимум — более 50 млн). Проверка поведения алгоритмов на предельных объёмах: качество картинки и замер производительности.

Результаты тестирования: цифры и визуализация

Ниже — результаты прогонов по каждой из трёх групп. В таблицах оставлена только суть:

• Avg Out — среднее количество точек на выходе алгоритма;

• Total ms — суммарное время работы на всём датасете;

• Cover, Prec, F1 — строгие попиксельные метрики (полнота, точность, их баланс);

• Visual — F1-score с допуском ±1 пиксель, ближе к реальному восприятию глазом.

Этап 1: Базовый датасет (Regular)

Параметры: 2 930 файлов | В среднем ~20 000 точек на файл. Стандартный сценарий: данные с манометров за 1–12 месяцев, низкая дискретность.

Scatter-графики (Точечные)

Наблюдения по Scatter: На большой выборке реальных данных классические алгоритмы в среднем теряют около 20% покрытия, хотя визуально потери ощущаются мягче — на уровне 5–10%. Матричный фильтр 800×600 показал почти идеальное визуальное качество, вернув при этом вдвое меньше точек. Разница во времени работы на этом объёме незначительна: сами алгоритмы отрабатывают за миллисекунды, и накладные расходы влияют сильнее, чем выбор метода.

Line-графики (Линейные)

Наблюдения по Line: При отрисовке линий разрыв между матричным фильтром и классическими алгоритмами минимален. Visual Score у всех — выше 97%. Соединительная линия закрашивает вертикальные пустоты, которые на scatter-графике были бы заметны.

Этап 2: Данные среднего размера (Medium)

Параметры: 24 файла | В среднем 500 000 точек на файл. Более плотные данные: непрерывная запись за периоды до года.

Scatter-графики (Точечные)

Наблюдения по Scatter: С ростом плотности классические алгоритмы начинают терять покрытие. LTTB сохраняет лишь 31.5% исходного облака, M4 — 20.1%. Визуально графики становятся разреженными: плотные области теряют структуру. Матричный фильтр остаётся стабильным независимо от объёма.

Line-графики (Линейные)

Наблюдения по Line: На линейных графиках ситуация принципиально иная. Вертикальные отрезки линий компенсируют потерю отдельных точек, показывая почти идеальную визуализацию — Visual > 98%.

Отдельного внимания заслуживает просадка чистого LTTB до 83% по визуализации. Причина — в механике алгоритма: он оставляет строго по одной точке на корзину. В зонах с высокой плотностью и большим разбросом по вертикали одной точки недостаточно, чтобы передать «толщину» зашумлённого сигнала — линия начинает отклоняться от оригинала.

Этап 3: Большие данные (Large)

Параметры: 13 файлов | В среднем 25 000 000 точек на файл (максимум — более 50 млн). Стресс-тест на предельных объёмах.

Примечание: выборка на этом этапе малая, поэтому процентные метрики следует воспринимать как оценочные. Основная цель — замер производительности.

Scatter-графики (Точечные)

Line-графики (Линейные)

Наблюдения: Результаты подтверждают тенденцию предыдущего этапа. На scatter-графиках классические алгоритмы продолжают терять покрытие — у LTTB оно составляет 33%. На линейных графиках ситуация выравнивается: M4 выдаёт 100% Visual Score, выполняя именно ту задачу, под которую проектировался. На этом объёме показательна степень сжатия: все алгоритмы укладывают 25 миллионов точек в 5–13 тысяч — разница лишь в том, что именно из исходной картины сохраняется.

Ключевой показатель на этом этапе — время работы. Матричный фильтр обрабатывает 13 файлов (около 324 млн точек суммарно) за 1657 мс — примерно в 2.5–3 раза медленнее классических алгоритмов. Это прямое следствие двойного прохода: сначала поиск экстремумов для границ сетки, затем растеризация. Размер матрицы (1920×1080 против 800×600) на скорость практически не влияет — меньшая сетка экономит только память и количество возвращаемых точек.

Главные выводы

Результаты всех прогонов сводятся к нескольким фактам:

• Классические алгоритмы непригодны для scatter. Одномерные алгоритмы (LTTB, M4, MinMax) деградируют на точечных графиках пропорционально росту данных. Они отбрасывают 10–30% визуально значимой информации, разрежая плотные области до скелета из экстремумов.

• Матричный фильтр сохраняет плотность. На точечных графиках он абсолютно стабилен. Опора на физические пиксели, а не на ось времени, гарантирует 100% покрытие независимо от объёма данных на входе.

• Линейные графики компенсируют потери. Для line chart разрыв в качестве минимален. Соединительная линия закрашивает вертикальные пустоты в пиксельных столбцах, вытягивая метрики классических алгоритмов.

• M4 решает свою задачу. На линейных графиках и больших объёмах M4 показал 100% Visual Score. Для line chart это по-прежнему быстрое и точное решение.

• Слабость чистого LTTB. На зашумлённых данных, где в один пиксельный столбец попадают сотни точек с большим разбросом амплитуды, LTTB проседает даже на линейных графиках. Одна точка на корзину — недостаточно для передачи визуальной «толщины» сигнала.

• Размер матрицы — рычаг для трафика. Уменьшение сетки с 1920×1080 до 800×600 практически не снижает визуальное качество (~99% Visual Score), но возвращает в 2–2.5 раза меньше точек.

• Размер матрицы не влияет на скорость. Фильтр 800×600 работает за то же время, что и Full HD. Меньшая сетка экономит память, но не процессорное время.

• Матричный фильтр медленнее в 2–3 раза. Это следствие двойного прохода по массиву: сначала поиск границ, затем растеризация.

• В абсолютных величинах скорость достаточна. 25 миллионов точек обрабатываются примерно за 130 мс в один поток. На таких объёмах разница легко растворяется в накладных расходах: сериализация, сеть, рендеринг в браузере.

• Единый подход. Матричный фильтр одинаково точно работает и на scatter, и на line chart. Это позволяет использовать один алгоритм вместо набора специализированных — при условии, что задача сводится к визуализации.

Заключение

Если продукт отображает исключительно линейные графики, матричный фильтр, вероятно, не нужен. M4 или MinMaxLTTB работают в один проход, считают быстрее и дают отличный результат на непрерывных кривых.

Но в промышленной телеметрии — где данные рвутся, датчики шумят, а scatter-график остаётся основным инструментом аналитика — одномерные алгоритмы систематически искажают картину, отбрасывая визуально значимую плотность. Для таких задач двумерное прореживание оказывается более релевантным.

Матричный фильтр медленнее в 2–3 раза. На практике это десятки миллисекунд, которые растворяются в накладных расходах стека. Взамен мы получаем пиксельно точную визуализацию и единый алгоритм, одинаково пригодный для любого типа графика.

Исходный код

Код эксперимента — все фильтры и тестовые стенды — выделен в открытый репозиторий. Алгоритм реализован на Java без сторонних библиотек, легко читается и переносится на любой другой язык.

Исходный код на GitHub: https://github.com/gearquicker/time-series-filter