Математика Зображення

Транспорт Монжа

Оптимальний транспорт - давня проблема, сформульована Монжем у 18 столітті. Він полягає у пошуку найбільш економічного способу, наприклад в часі, для транспортування об’єктів між набором початкової та кінцевої точок. Ця стаття обговорює цю проблему, труднощі пошуку рішення, коли є багато моментів, та ілюструє деякі додатки. Незабаром опублікована супутня стаття представляє переформулювання Канторовичем проблеми Монжа, що дозволило йому стати важливим інструментом як в теорії, так і на практиці.

Гаспард Монж, крім того, що був великим математиком, брав активну участь у французькій революції і створив Політехніку Ecole, а також Ecole Normale Supérieure. Мотивований військовими додатками, він сформулював у 1781 р. Проблему оптимального транспорту [1]: він поставив собі питання про розрахунок найбільш економічного способу транспортування землі між двома місцями для набережних.

Проблема Монжа

Щоб проілюструвати проблему та її математичну постановку, давайте розглянемо оптимальний спосіб розподілу круасанів від пекарень до кафе вранці в Парижі. Для простоти припустимо, що є лише шість пекарень та кафе, що видно на наступному малюнку (пекарні червоного кольору, а кафе синього кольору).
Припустимо, що всі пекарні виробляють однакову кількість круасанів і що всі кафе також потребують однакової кількості круасанів.
У своєму оригінальному тексті Монж висуває гіпотезу, що вартість переміщення одиниці маси дорівнює пройденій відстані, але ми можемо використовувати будь-які витрати, що підходять для вирішення проблеми.
Ми мінімізуємо вартість, яку ми розглянемо, це загальний час у дорозі, і ми записуємо $ C_ $ час між пекарнею $ \ iC \ in \ $ та кафе $ \ jC \ in \ $. Наприклад, ми маємо $ C _, \ Blu> = 10 $, це означає, що між хлібобулочним номером $ \ Red $ та номером кафе $ \ Blu $ є десять хвилин їзди.

Для того, щоб задовольнити обмеження поставки, кожна пекарня повинна бути підключена до одного кафе, а кожне кафе - до однієї пекарні. Це, зокрема, означає, що кафе стільки, скільки пекарень. Відзначимо
\ [\ si: \ iC \ in \ \ longmapsto \ jC \ in \ \]
такий вибір зв’язків. Ми називаємо такий вибір $ \, якщо $ з'єднань, що задовольняють обмеженням постачання, є перестановкою.

Транспортні витрати, пов'язані з такою перестановкою, є сумою витрат $ C_ $, обраних перестановкою $ \ si $, тобто
\ [\ begin \ text (\ si) \ eqdef C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Red)> + C _, \ si (\ Червоний)> + C _, \ si (\ Червоний)> + C _, \ si (\ Червоний)>. \ кінець \]
Наприклад, для перестановки ($ \ ref $), показаної на попередньому малюнку, ми отримуємо як вартість
\ [\ початок C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> + C _, \ Blu> = 10 + 7 + 15 + 10 + 14 + 9 = 65. \ кінець \]

Проблема Монжа полягає у пошуку перестановки $ \ si $, яка має мінімальну вартість, тобто вирішення задачі оптимізації
\ [\ почати \ umin \ text (\ si), \ end \]
де ми позначаємо $ \ Si_6 $ множину перестановок множини $ \ $.


Вартість = 64	Вартість = 65	Вартість = 66	Вартість = 152

На попередньому малюнку наведено приклади перестановок з різними витратами. Таким чином, ми можемо побачити, що перестановка ($ \ ref $) не найкраща: існує, наприклад, інша перестановка, вартість якої 64. Але чи найкраща? Виявляється, так, ми дійсно можемо перевірити всі перестановки $ \ $ на комп’ютері та обчислити їх вартість. Скільки всього перестановок? Для цього підрахунку ми бачимо, що існує шість можливих варіантів призначення від $ \ Red $ до $ \ si (\ Red) \ in \, \ ldots, \ Blu \> $, а потім п'ять можливих варіантів призначення $ \ Red $ до $ \ if (\ Red) $ у наборі $ \< \Blu,\ldots,\Blu \>$, який ми виключаємо $ \ si (\ Red) $ тощо. Отже, загальна кількість можливостей дорівнює $ 6 \ раз 5 \ по 4 \ по 3 \ по 2 \ по 1 = 720 $, що ми позначаємо $ 6! $, "Фактор 6". Якщо ми розглянемо кількість $ n $ пекарень, то кількість перестановок, які потрібно перевірити, щоб знайти найкращу, становить $ n! = n \ разів (n-1) \ times \ cdots \ разів 2 \ разів 1 $. Це число надзвичайно швидко зростає із $ n $, наприклад 70 $! \ приблизно 1198 \ разів 10 ^ $, порівняйте з нейронами $ 10 ^ $ у мозку та атомами $ 10 ^ $ у Всесвіті. Тому така вичерпна стратегія пошуку можлива лише для дуже малих значень $ n $.

У 1D та 2D

Потрібно було майже 200 років, щоб з’явилися нові ідеї, щоб ефективно розрахувати оптимальний транспорт $ \ sigma $ навіть при великих значеннях $ n $. Ці математичні досягнення будуть докладно описані в супутній статті. Почнемо зі випадку, коли оптимальний транспорт легко розрахувати. Найбільш елементарний випадок - коли точки, що мають узгоджуватися, розташовані вздовж осі 1D, наприклад, якщо кафе та пекарні розташовані вздовж лінії метро. Також необхідно, щоб вартість $ C_ $ являла собою відстань вздовж цієї осі (наприклад, час подорожі на метро між станціями).
Ми йдемо ліворуч від усіх пунктів у грі і проїжджаємо лінію метро зліва направо. Перша червона точка асоціюється з першою синьою точкою, друга червона точка - з другою синьою точкою тощо.
Цей процес проілюстровано на наступному малюнку, де оптимальною перестановкою є $ \ if: (\ Red, \ Red, \ Red, \ Red, \ Red) \ mapsto (\ Blu, \ Blu, \ Blu, \ Blu, \ Blu) $.

Таким чином, час обчислення, необхідний для розрахунку оптимального транспорту метро, - це час, необхідний для класифікації індексів. Найпростіший алгоритм ранжирування - це, як правило, сортування набору $ n $ карток: це вставне сортування, яке ітеративно вставляє кожну карту на своє місце щодо вже класифікованих карт. Він виконує порівняння $ n (n-1)/2 $. Отже, для $ n = 70 $ для цього потрібно лише 2415 операцій, що робить метод придатним для використання, на відміну від вичерпного пошуку всіх перестановок $ n! $. У нас є ще швидші алгоритми (наприклад, сортування злиттям), які виконуються в порядку $ n \ log (n) $ операцій, і тому для $ n = $ 70 такі методи вимагають менше 1000 операцій.

На жаль, використовувати цей прийом ранжування в більш загальних випадках вже неможливо. Для точок у розмірності 2, якщо взяти за вартість $ C_ $ відстань, на яку летить ворона між точками, тоді Гаспард Мондж показав у своєму оригінальному документі (див. Наступну рисунку), що оптимальний транспорт не може містити перетину.

Наприклад, як показано на наступному малюнку, якщо ми намалюємо всі відрізки між точками $ \ iC \ mapsto \ jC = \ si (\ iC) $, які ми з'єднуємо перестановкою, визначеною оптимальною $ \ si $, ці ніколи не перетинаються.


2D транспорт, $ n = 10 $	Двовимірний транспорт, $ n = 70 $	Двовимірний транспорт, $ n = 200 $

Однак цього геометричного спостереження недостатньо для розрахунку оптимального переносу в 2D: дійсно існує багато перестановок $ \ if $ таких, що пов'язані відрізки не перетинаються.
Потрібно буде більш детально проаналізувати структуру оптимальних перестановок, щоб мати можливість їх ефективно розрахувати.
Супутня стаття покаже, як Леонід Канторович переформулював проблему Монжа, щоб досягти цього.

Програми

Початковою мотивацією Монжа була насамперед військова. Програми, передбачені Канторовичем, були економічними [2], і оптимальний транспорт мав значний вплив на оптимізацію промислового виробництва. Справді, кожного разу, коли нам доводиться співвідносити обсяги виробництва та споживання, ми маємо вирішити оптимальну транспортну проблему. Канторович отримав Нобелівську премію з економіки в 1975 році за свою роботу в цій галузі, яка буде детально описана в супутній статті.

Оптимальний транспорт знайшов багато інших застосувань, як теоретичних, так і більш конкретних. Математично ми можемо розглядати "безперервний" розподіл мас, таким чином, обмеження, коли кількість точок $ n $ прагне до нескінченності. Це дозволяє визначити транспортну проблему між будь-якими розподілами ймовірностей. Ця теоретична точка зору надзвичайно плідна, і саме французький математик Ян Бреньє вперше продемонстрував еквівалентність у безперервних рамках формулювань Монжа та Канторовича [3]. Ці новаторські роботи продемонстрували зв’язок між транспортною проблемою та диференціальними рівняннями з частковими частками та, серед іншого, призвели до медалей Філдса Седріка Віллані (2010) та Алесіо Фігаллі (2018).

Оптимальний транспорт останнім часом лежить в основі більш прикладних проблем науки про дані, зокрема для вирішення проблем в обробці зображень та машинному навчанні.
Перша і найближча ідея полягає у використанні перестановки $ \ si $ для перетворення даних, наприклад зображень. У цьому випадку ми розглядаємо пікселі $ (\ Red, \ ldots, \ Red) $ і $ (\ Blu, \ ldots, \ Blu) $ двох кольорових зображень. Кожен піксель $ \ Red, \ Blu \ in \ RR ^ 3 $ є вектором розмірності 3, який представляє інтенсивність кожного з трьох елементарних кольорів - червоного, зеленого та синього. Для того, щоб змінити кольори першого зображення та накласти на нього палітру другого зображення, ми розраховуємо транспорт $ \ si $, використовуючи вартість $ C_ $, яка враховує схожість кольору $ \ Red $ і колір $ \ Blu $ двох пікселів, що означає, що $ C_ $ тим слабкіший, чим ближче кольори цих пікселів. Зображення із зміненими кольорами становить $ (y _, \ ldots, y _) $, тобто на першому зображенні ми замінюємо піксель $ \ Red $ на піксель $ y_ $. Це зображення виглядає як перше, але має колірну гамму другого.

Наступний малюнок ілюструє цей процес накладання кольорової палітри Пікассо на картину Сезанна. У верхньому рядку малюнка пікселі знаходяться на сітці дисплея, щоб сформувати кольорове зображення. У нижньому рядку пікселі розміщуються на своїх позиціях у $ \ RR ^ 3 $, утворюючи хмару точок. Дві хмари точок у центрі та праворуч однакові: оптимальний транспорт, застосований до пікселів картини Сезанна, дає нове зображення (показано праворуч), набір пікселів якого є перестановкою пікселів у Пікассо живопис.


Зображення $ (\ Червоне) _ ^ n $	Зображення $ (\ Blu) _ ^ n $	Зображення $ (y _) _ ^ n $

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

Пов’язані статті

Я хотів би подякувати Вінсенту Беку, Гвен Гічауа та Марі-Ноел Пейре за ретельну коректуру, а також коректорам Масоку, Яссіну Галему, Офелі та Франсуа Бруно за їхні коментарі та виправлення.

Примітки

[1] Гаспард Мондж. Дисертація з теорії живців та засипок. Історія Королівської академії наук, стор. 666-704, 1781.

[2] Леонід Канторович. Про передачу мас (російською мовою). Доклади Академії Наук, 37 (2), с. 227-229, 1942.

[3] Ян Бреньє. Полярна факторизація та монотонна перебудова векторнозначних функцій. Повідомлення з чистої та прикладної математики, 44 (4): с.375-417, 1991.

Поділіться цією статтею

Щоб процитувати цю статтю:

Габріель Пейре - "Оптимальний цифровий транспорт та його застосування - Частина 1" - Зображення математики, CNRS, 2019