Сортировка блоков (blocksorting)

Общая теория

Рассмотрим операцию \(\rm sortby\) — сортировки одной строки по другой. Будем писать \(s_1 \mathop{\rm sortby} s_2\), если мы сортируем строку \(s_1\), используя символы строки \(s_2\). Что это означает?

Мы берем строку \(s_2\) и сортируем ее, используя устойчивую сортировку (stable sort), в результате получаем строку \(s_2'\). Очевидно, мы можем определить в какие позиции в строке \(s_2'\) перешли символы из \(s_2\). Таким образом, мы получаем перестановку, которая рассказывает нам о перемещении символов в \(s_2\). Далее эту перестановку мы должны применить к строке \(s_1\), т.е. переставить в ней символы точно так же, как они были переставлены при переходе от \(s_2\) к \(s_2'\). Результат \(s_3\) этой операции и будет нужным нам преобразованием : \(s_1 \mathop{\rm sortby} s_2\).

Заметим, что по \(s_3\) и \(s_2\) можно однозначно восстановить \(s_1\). Как это сделать? Раз нам доступна строка \(s_2\), то мы ее можем отсортировать и получить \(s_2'\), т.е. найти нужную перестановку, которая определяется однозначно. Далее нужно обратить эту перестановку и применить к \(s_3\), что в итоге даст \(s_1\).

Пример. Пусть дано два алфавита \(A = \{a, b, c\}\) и \(B = \{1,2,3,4\}\), а также две строки \(s_1 = abbc\) и \(s_2 = 2431\) над этими алфавитами. Нужно вычислить \(s_3 = s_1 \mathop{\rm sortby} s_2\). После сортировки \(s_2\) получим строку \(s_2'=1234\). Перестановка для перехода от \(s_2\) к \(s_2'\) при устойчивой сортировке — \(1320\). Применим эту перестановку к исходной строке \(s_1\). Это означает, что мы должны поменять элементы \(s_1\) местами по следующей схеме:

\[\begin{array}{label} s_1[0] \to s_1[1] \\ s_1[1] \to s_1[3] \\ s_1[2] \to s_1[2] \\ s_1[3] \to s_1[0] \end{array}\]

В итоге получаем результат \(s_3 = cabb\).

Применение к изображениям

Рассмотрим изображение шириной \(w\) и высотой \(h\) пикселей. Будем считать, что изображение — это набор \(h\) строк \(s[0],\ldots,s[h-1]\) (“сверху вниз”) и длина каждой строки \(w\). Применим операцию \(\mathop{\rm sortby}\) к нашим строкам следующим образом: \(s[i] = s[i] \mathop{\rm sortby} s[i-1]\). Это означает, что каждую строку \(s[i]\) в изображении мы заменим на результат \(s[i] \mathop{\rm sortby} s[i-1]\). В нашем случае индекс \(i\) меняется от \(h-1\) до \(1\) (движемся по картинке “снизу вверх”). Первая строка \(s[0]\) останется без изменений.

После применения преобразования мы получим новое изображение как результат перестановки пикселей исходного. Это новое изображение обладает тем замечательным свойством, что позволяет вернуться в точности к исходному изображению. Это прямое следствие обратимости операции \(\mathop{\rm sortby}\) и того, что первую строку изображения мы оставили без изменений.

Исходное изображение Lena:

Изображение Lena после применения blocksorting:

Реализация

Задача заключается в реализации описанного алгоритма преобразования изображений. Заметим, что операция \(\mathop{\rm sortby}\) может выполняться независимо для каждой строки изображения. Поэтому возможно одновременное преобразование всех строк, что дает выигрыш в производительности в \(h\) раз по сравнению с последовательной обработкой.

Для решения задачи нужно уметь сортировать строки. Рекомендуется обратить внимание на Counting Sort, которая позволяет делать сортировку чисел из фиксированного диапазона крайне быстро.