Кривая Гильберта: от бесконечной математики к реальным приложениям

Кривая Гильберта: от бесконечной математики к реальным приложениям

Спикер: 3Blue1Brown | Длительность: 18:18

Транскрипт

Идея преобразования изображений в звук

Представьте, что вы хотите написать программу, которая позволит людям видеть ушами. Она будет получать данные с камеры и преобразовывать их в осмысленный звук. Мозг достаточно пластичен, чтобы построить интуицию из зрения, даже если исходные данные искажены. Для упрощения можно начать с изображений низкого разрешения, например, 256x256 пикселей. Представим изображение как квадратную сетку, где каждая ячейка — пиксель.

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

Основная задача — найти функцию, которая отображает пиксельное пространство (2D) в частотное (1D). Случайное отображение возможно, но лучше использовать интуицию, связанную со звуком. Если частоты близки, то и соответствующие им пиксели должны быть близки в пространстве.

Для этого можно провести линию через каждый пиксель, а затем выпрямить эту линию, интерпретируя ее как частотное пространство. Так мы получим связь между пикселями и частотами.

"Змеиная" кривая

Один из способов провести линию — идти построчно, чередуя направление вверх и вниз. Это похоже на игру "Змейка", поэтому назовем это "змеиной" кривой.

Псевдо-кривые Гильберта

Когда вы рассказываете об этой идее математику, он предлагает использовать кривую Гильберта. Это не одна кривая, а целое семейство.

Для кривой порядка 1, квадрат делится на 4 части (2x2). Кривая соединяет центры квадрантов: нижний левый, верхний левый, верхний правый, нижний правый.

Для порядка 2, квадрат делится на 16 частей (4x4). В каждом квадранте рисуется мини-кривая порядка 1. Чтобы соединения были короче, кривые в нижнем левом и нижнем правом квадрантах переворачиваются.

Для порядка 3, квадрат делится на 64 части (8x8). В каждом квадранте рисуется мини-кривая порядка 2, с соответствующими переворотами. Этот паттерн продолжается.

Для сетки 256x256 пикселей используется кривая порядка 8.

Преимущество кривой Гильберта

"Змеиная" кривая хороша как арт-объект, но кривая Гильберта имеет важное преимущество. Если мы увеличим разрешение изображения (с 256x256 до 512x512), "змеиная" кривая приведет к тому, что многие точки на линии частот окажутся в совершенно других частях пиксельного пространства. Это потребует от пользователей полного переобучения. Кривая Гильберта же, при увеличении порядка, позволяет точке на линии перемещаться все меньше и меньше, приближаясь к определенной точке в пространстве. Это дает пользователям возможность донастраивать свои интуиции.

Истоки: бесконечная математика

Изначальная мотивация создания таких кривых — решение философского вопроса: как бесконечная математика может быть полезна в конечном мире?

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

До 1890 года считалось, что это невозможно. Но затем Пеано открыл первую пространственно-заполняющую кривую, а в 1891 году Гильберт предложил свою, более простую.

Математики называют "кривой" линию, даже если у нее есть острые углы. Пространственно-заполняющая кривая состоит из острых углов, поэтому ее можно назвать "фракталом, заполняющим пространство".

Псевдо-кривые Гильберта, используемые для пиксельных сеток, не являются настоящими пространственно-заполняющими кривыми, так как они проходят лишь через малую часть бесконечного пространства.

Формальное определение кривой

Настоящая кривая Гильберта — это предел всех псевдо-кривых. Формально, кривые — это функции, которые принимают одно число от 0 до 1 (точка на линии) и выдают пару чисел (координаты в 2D).

Например, псевдо-кривая порядка 2 отображает 0.3 в (0.125, 0.75). Псевдо-кривая порядка 3 отображает 0.3 в (0.0758, 0.6875).

Ключевое свойство кривой — непрерывность. Функция непрерывна, если малые изменения входных данных приводят к малым изменениям выходных. Формально: для любой окрестности входной точки, существует такая окрестность выходной точки, что все выходные точки, соответствующие входным в первой окрестности, попадают во вторую.

Предел псевдо-кривых

Если взять входную точку, например 0.3, и применить к ней последовательно функции псевдо-кривых Гильберта разных порядков, то выходные точки будут сходиться к определенной точке в 2D пространстве. Это не работает для "змеиных" кривых.

Благодаря этой свойству, кривую Гильберта можно определить как предел последовательности точек, полученных применением псевдо-кривых Гильберта.

Чтобы доказать, что это пространственно-заполняющая кривая, нужно показать: 1) что это корректно определенная функция (точки сходятся), 2) что она непрерывна, 3) что она заполняет все точки единичного квадрата.

Чтобы заполнить все пространство, можно использовать спиральное расположение квадратов, заполненных кривыми Гильберта, соединяя их линиями.

Связь бесконечного и конечного

Основное свойство, делающее кривые Гильберта полезными, — уменьшение перемещения точек при увеличении порядка. Это полезно как для практических приложений (апгрейд разрешения), так и для математики (предел последовательности).

Связь между бесконечным и конечным в математике — скорее правило, чем исключение. Пример — связь между расходящейся суммой степеней двойки и двоичным представлением чисел.

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

Формализация стабильности последовательности кривых при увеличении разрешения эквивалентна определению существования предела у последовательности.

Часто утверждение о бесконечном объекте — это способ компактно описать истину о семействе конечных объектов.

Практические задания

Задание 1: Визуализация псевдо-кривой Гильберта

Реализуйте функцию для построения псевдо-кривой Гильберта заданного порядка N. Начните с порядка 1 (квадрат, разделенный на 4 части, с соответствующими соединениями). Затем реализуйте рекурсивное построение для порядка 2 (4 мини-кривые порядка 1 в каждом квадранте) и выше. Проверьте, что кривая проходит через центры всех ячеек сетки.

• Цель: Построить визуальное представление псевдо-кривой Гильберта.
• Шаги:
  1. Определите базовый случай: кривая порядка 0 (одна ячейка) или 1 (квадрат 2x2).
  2. Реализуйте рекурсивную функцию, которая делит квадрат на 4 квадранта.
  3. В каждом квадранте рекурсивно вызывайте функцию для построения мини-кривой, учитывая необходимость поворота/отражения.
  4. Соедините мини-кривые в правильном порядке.
  5. Визуализируйте результат (например, с помощью matplotlib).
• Проверка: Убедитесь, что линия проходит через центры всех ячеек сетки заданного порядка.

Оценка времени: 2 часа

Задание 2: Сравнение "Змеиной" и "Гильберта" на стабильность

Напишите код, который генерирует "змеиную" кривую и псевдо-кривую Гильберта для разрешения N x N. Затем, выберите фиксированную точку на "линии частот" (например, 0.5) и проследите, как ее пиксельные координаты меняются при увеличении разрешения (например, с 4x4 до 8x8, до 16x16). Сравните стабильность координат для обоих типов кривых.

• Цель: Продемонстрировать разницу в стабильности отображения пиксельных координат при изменении разрешения для "змеиной" и "Гильберта" кривых.
• Шаги:
  1. Реализуйте функцию для генерации "змеиной" кривой (построчное сканирование).
  2. Используйте код из Задания 1 для генерации псевдо-кривой Гильберта.
  3. Создайте функцию, которая для заданного N x N разрешения и координаты на линии (0-1) возвращает координаты пикселя.
  4. Итерируйте по возрастающим разрешениям (например, 4, 8, 16, 32) и вычисляйте координаты пикселя для фиксированной координаты линии (0.5) для обеих кривых.
  5. Визуализируйте или выведите разницу в координатах.
• Проверка: Убедитесь, что колебания координат для кривой Гильберта значительно меньше, чем для "змеиной" кривой.

Оценка времени: 3 часа

Задание 3: Исследование непрерывности

Используя пример отображения из видео (например, из псевдо-кривой порядка 2), найдите входное значение, которое вызывает "прыжок" в выходных координатах. Проанализируйте, почему оно не соответствует определению непрерывности, подставив значения в формальное определение.

• Цель: Понять формальное определение непрерывности функции и его значение для кривых.
• Шаги:
  1. Возьмите функцию, представляющую псевдо-кривую Гильберта (или другую функцию, которая может иметь разрывы).
  2. Определите формальное условие непрерывности: для любой $\epsilon > 0$, существует $\delta > 0$ такое, что если $|x - a| < \delta$, то $|f(x) - f(a)| < \epsilon$.
  3. Найдите точку $a$, где функция может быть разрывной (например, на границе квадрантов).
  4. Подставьте значения $a$ и $f(a)$ в определение и покажите, что для малых $\delta$ (малые изменения $x$ вокруг $a$), разница $|f(x) - f(a)|$ не может быть сколь угодно малой.
• Проверка: Объясните своими словами, почему найденная точка является точкой разрыва и почему это нарушает свойство кривой.

Оценка времени: 1 час

Лучшие цитаты

"Math often deals with infinite quantities, sometimes so intimately that the very substance of a result only actually makes sense in an infinite world." — 3Blue1Brown

"The trick is that pixel space is two-dimensional, but frequency space is one-dimensional." — 3Blue1Brown

"The intuition behind continuity is that you don't want the output of your function to suddenly jump at any point when the input is only changing smoothly." — 3Blue1Brown

"A line, the platonic form of thinness itself, can wander through an infinitely extending and richly dense space and hit every single point." — 3Blue1Brown

"The lesson to take away here is that even when a statement seems very far removed from reality, you should always be willing to look under the hood and at the nuts and bolts of what's really being said." — 3Blue1Brown

Ключевые выводы (Takeaways)

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