Поворот изображения на 90 градусов

[Mikle]

Имеется одномерный long массив ar(dX * dY - 1), содержащий изображение.
Требуется повернуть изображение на 90 градусов. Если выделить память - задать второй массив такого же размера, то это делается элементарно, в цикле:

ar2(y + (dx - x - 1) * dy) = ar(x + y * dx)

По идее можно повернуть массив на месте, не выделяя память, точнее выделяя всего одну long ячейку:

dim c as long
c = ar(y + (dx - x - 1) * dy)
ar(y + (dx - x - 1) * dy) = ar(x + y * dx)

И так далее, пока не подходим к ячейке, значение которой должно быть равно первоначальной. Адреса каждой следующей ячейки в таком цикле легко вычисляются, но цикл, по завершении, должен каким-то образом отметить обработанные ячейки, чтобы не обработать повторно, а это опять выделение памяти.
Вопрос - кто-нибудь занимался подобной задачей? Может есть готовый алгоритм?

[HiSER]

Как вариант:

Код: Выделить всё

For y = 0 To dY - 1
For x = y To dX - y - 2
a1 = x + y * dX
a2 = (dX - y - 1) + x * dX
a3 = (dX - x - 1) + (dY - y - 1) * dX
a4 = y + (dY - x - 1) * dX
c = ar(a4)
ar(a4) = ar(a3)
ar(a3) = ar(a2)
ar(a2) = ar(a1)
ar(a1) = c
Next x, y


[Mikle]

HiSER
Что-то не работает. Тут тестовый проект (Test.vbp) с твоим кодом, проверочный вариант с копированием массива закомментирован. И ещё проект для изучения циклов зависимостей адресов на полях разных размеров (Num.vbp).

[HiSER]

Мой просто только квадраты крутит
надо до думать его...

[Mikle]

Задача только на первый взгляд проста. Есть решение подобной задачи:
http://en.wikipedia.org/wiki/In-place_m ... nsposition
Но тут рекурсия - то же самое выделение памяти, только по-другому.

[Nord777]

Задача только на первый взгляд проста.

Она невыполнима(так как оно тебе хочется).
Либо доп. выделение памяти, либо лишние проходы.

[Александр Дмитриев]

Ну и как с лишними проходами, но без доп. памяти?

[Nord777]

Ну и как с лишними проходами, но без доп. памяти?

Никак. Фигню спорол
При проходе по уже пройденному, значения опять поменяются местами.
В итоге будет "каша".

[Хакер]

Ну для квадратных же можно, юзая xchg.

[Александр Дмитриев]

В том-то и дело, что для сколь угодно больших квадратных матриц можно, но если в матрице, например, высоту сделать на один пиксель меньше, то операция уже станет на порядок сложнее (хотя, если, например, это была фотография, то эта нижняя строчка может не играть никакой роли).
В принципе я придумал алгоритм, с помощью которого можно без доп. памяти (и за квадратное время) повернуть изображение, у которого высота в два раза больше ширины. Нужно повернуть сначала по отдельности верхнюю и нижнюю половины (алгоритмом Хайзера), а потом "вплести" половины друг в друга, получив конечное изображение (вроде придумал алгоритм вплетения, который линеен относительно полосок и, соответственно, квадратичен относительно пикселей). Можно разбить изображение на квадратики, повернуть каждый квадратик, а затем каким-то сложным алгоритмом вплетения получить из них конечное изображение. Можно как-нибудь попробовать использовать оба алгоритма (Mikl'а и HiSER'а), получая в одном то, чего нет в другом.

[Mikle]

Возможные полумеры - выделять 1/32 от памяти массива, помечая пройденные ячейки в битовом массиве. Если учесть, что адресация симметрична - можно выделять 1/64 от памяти массива.
Многие частные случаи неплохо описываются формулами, в т. ч. когда разница ширины с высотой равна одному пикселю. Когда ширина на высоту делится нацело - вообще всё просто.

[Александр Дмитриев]

Кажется, есть алгоритм!
Идея пришла в этот понедельник вечером. Потом додумал и реализовал, чтобы протестить на больших картинках.
Исходник программы на Си во вложении (rotate.c). Вызов: rotate src.ppm dest.ppm (для простоты читает и пишет только самый примитивный формат изображений - PPM).
Общая суть алгоритма такова. Все операции записи с массивом производятся при помощи только одной элементарной операции - swap каких-то двух пикселей, таким образом информация в принципе никуда никогда не теряется, а только перетасовывается внутри изображения. Все без исключения операции swap приводят к перемещению какого-то пикселя на своё окончательное место, так что больше он оттуда уже не уходит, а сидит там до самого конца. Таким образом, всего мы производим ровно width * height операций swap. Соответственно, при каждом swap'е элемент, который сидит на месте, на которое мы окончательно перемещаем очередной пиксель, перемещается в какой-то другой промежуточный для него неокончательный пиксель. Далее вся фишка алгоритма. Мы сначала перемещаем те пиксели, у которых конечное положение в массиве лежит позже начального, а затем те, у которых оно лежит раньше начального (то есть сначала те, которые глобально нужно переместить вперёд в массиве, а потом те, которые глобально нужно переместить назад в массиве). Делаем это очень просто. Берём пиксель, который нужно переместить и перемещаем его. Здесь именно два действия: берём и перемещаем. Причём первое намного более трудоёмкое. Мы знаем глобальное начальное положение пикселя и глобальное конечное положение. Перемещать будем swap'ом в глобальное конечное положение. А вот откуда мы будем его брать? Мы знаем, где оно находилось в самом начале алгоритма. Далее в процессе алгоритма действиями "перемещения в какой-то другой промежуточный для пикселя неокончательный пиксель" при swap'ах, ставящих на место совсем другие пиксели, он переместился в какое-то другое место. Мы просто берём и отслеживаем по шагам всю историю таких действий с этим пикселем. И выясняем, где он сейчас. В программе это реализуется функцией realPixelPosition(). С ним могли производится следующие операции. Сначала были постановки на место пикселей, глобально перемещаемых вперёд. На место нашего пикселя могли переместить какой-то другой пиксель. Но мы знаем, что это за пиксель. Для каждого пикселя мы знаем координату не только того места, в которое мы должны его переместить, но и то, откуда в него мы должны переместить. Оно тоже вычисляется по простой формуле. Таким образом, на первом этапе единственное, что могли сделать с нашим пикселем - это переместить в него известный нам пиксель. При этом наш пиксель переместился на место пикселя-жлоба. Но где был этот жлоб? Он глобально находится раньше нашего, потому что глобально перемещается вперёд. Мы знаем его начальное положение, но перед своим актом жлобства он мог переместиться. Он мог переместиться только во время первого этапа, потому что он перемещается глобально вперёд. При этом его мог свергнуть с места только какой-то другой жлоб, который тоже перемещается глобально вперёд и который тоже глобально находится раньше первого жлоба. И его начальное место мы тоже знаем (вычисляется по той же простой формуле, что и место первого жлоба, но только не относительно безвредного пикселя, а относительно первого жлоба). Короче, применяя эту простую формулу, мы будем двигаться назад до тех пор, пока не наткнёмся на пиксель, который никто на первом этапе не трогал (его мы определим по тому признаку, что в него пиксель перемещается глобально назад). Координата этого последнего пикселя и будет искомой координатой, в которую при swap'е попал наш пиксель. Далее отслеживается второй этап (где пиксели перемещаются глобально назад). На втором этапе пиксель могли сдвинуть только при перемещении какого-то пикселя глобально назад. Мы знаем начальную координату пикселя-циника, который сделал это. Она вычисляется по той же самой простой формуле. Причём сдвинуть его могли уже несколько раз, поскольку при сдвиганиях он перемещается вперёд. Мы вычисляем начальную координату первого циника. Если мы этого пикселя-циника уже переместили на место раньше, или мы его только будем ещё перемещать позже, то это перемещение реально не оказало влияния на наш пиксель, и он реально на втором этапе остался на месте, и текущая имеющаяся наша координата является ответом (местом, на котором реально находится пиксель). Если же указанное условие не выполнено, то перемещение пикселя произошло. Мы рекурсивно (да, да) вызываем функцию realPixelPosition() и находим реальную позицию пикселя-циника, на место которого переместился наш пиксель. Далее мы проверяем не сместил ли его кто другой далее таким же образом. В цикле (ура). Когда-нибудь мы придём в такое место, с которого его уже никто не смещал, так как мы двигались только вперёд. В обшем-то вот и весь алгоритм.
Насчёт рекурсии. Я с самого начал чувствовал, что она не будет глубоко заходить (максимальная глубина не будет зависеть от размера изображения при больших изображениях). При повышении размера изображения она медленно увеличивается, пока где-то в районе 20 килопикселей не достигает значения насыщения 20 (это гдё-то 0,5 килобайта памяти). Далее колеблется в районе 20-25 с редкими выбросами. Для квадратных изображений глубина рекурсии всегда 2 (видимо, тут что-то принципиальное). Я протестировал кучу изображений от 6 пикселей до 42 мегапикселей. Максимальное значение выброса было 44 на фотографии 3 мегапикселя (кстати, изображённой ниже). Таким образом, получается, что доп. память в среднем не зависит от размера изображения при больших изображениях.
Алгоритм работает примерно в 6 раз медленнее, чем алгоритм с созданием второго массива.
Есть алгоритм (rotate_back2.c), который поворачивает изображения приближённо, но кушает всегда константные 16 байт и работает по скорости почти как алгоритм с созданием второго массива. Приближённо здесь значит, что половина конечного изображения получается всегда правильно, а вторая половина замусорена, но общий смысл изображённого понять можно (~ 1 Мб трафика):

[Mikle]

Выглядит правдоподобно. То есть с точки зрения логики это правильно, а с точки зрения программирования - очень неоптимально.

При повышении размера изображения она медленно увеличивается, пока где-то в районе 20 килопикселей не достигает значения насыщения 20 (это гдё-то 0,5 килобайта памяти). Далее колеблется в районе 20-25 с редкими выбросами.

Это проверено на всех отношениях Width/Height?

[Александр Дмитриев]

Это проверено на всех отношениях Width/Height?

Не на всех, конечно. На тот момент я протестил его где-то на 30 изображениях (с разным кол-вом пикселей и разными отношениями Width/Height), которые просто накачал из инета отовсюду разных. С тех пор протестил только ещё на двух: 100 и 200 мегапикселей. Вот то, для чего была сохранена инфа (слева - размер изображения в пикселях, справа - макс. кол-во экземпляров рекурсивной функции на стеке вызовов):

Код: Выделить всё

           16 - 2
           20 - 3
            6 - 2
    1 024 000 - 23
      432 800 - 20
    1 119 364 - 2
      200 000 - 19
    2 743 296 - 44
      559 872 - 23
           18 - 3
   15 781 248 - 26
   43 234 951 - 32
  200 975 232 - 41
  101 314 124 - 30

По ходу асимптоты у глубины рекурсии всё-таки нет, а зависимость больше похожа на логарифмическую (я это понял после того как протестил 100 и 200 МП). Я хотел провести большой автоматизированный тестинг с проверкой большого кол-ва значений размера изображения и отношения Width/Height с построением графиков зависимостей и т. д., но так и не сделал это по нижеследующей причине.

Почитав Википедию и Кнута, я нашёл некий алгоритм Говера. Он поворачивает изображение на 90 градусов, делает это точно и совершенно без какой-либо доп. памяти. При этом он намного быстрее моего алгоритма. Суть его проста до невозможности. Опирается она всё на ту же теорию циклов, и на ту же проблему "как определить, что этот цикл мы ещё не обрабатывали". Для каждого пикселя проверяется, является ли он наименьшим по номеру в своём цикле или нет. Если является, то поворачиваем цикл, если не является - не поворачиваем. У каждого цикла есть только один наименьший по номеру элемент, поэтому каждый цикл мы повернём ровно один раз, что и нужно.

Тем не менее, по-моему, мой алгоритм может применяться для приближённого поворота изображений, при сочетании условий 1) нужно экономить память, 2) хочется быстрее что-то увидеть, хотя бы приближённо (аналогично черезстрочной развётке). Ограничив рекурсию и немножко усовершенствовав алгоритм (чтобы мусор был равномернее), я думаю, можно получить скорость, сравнимую с копированием в другой массив.

Программа для тестинга всех вышеприведённых алгоритмов в приложении.

[Mikle]

слева - размер изображения в пикселях, справа - макс. кол-во экземпляров рекурсивной функции

Важен не просто размер, а конкретные Width и Height, причём у 132*147 и у 147*132 может быть разное кол-во циклов.

я нашёл некий алгоритм Говера

Качаю...