Поворот картинки (транспонирование матрицы), Как сделать через перестановки? Опции

[RHnd]

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

Пример:
По сути, задача сводится к транспонированию матрицы. Есть матрица 4x3, из нее получается 3x4:

Код

1 2 3                       3 6 9 C
4 5 6           =>          2 5 8 B
7 8 9                       1 4 7 A
A B C

В линейном виде (как в памяти лежит):
Было: Picture[12] = 1 2 3 4 5 6 7 8 9 A B C
Стало: NewPictute[12] = 3 6 9 С 2 5 8 B 1 4 7 A

А вот каким алгоритмом можно переставить элементы Picture так чтобы получился NewPicture для произвольных N и M, я не знаю. Подскажите, пожалуйста!

[blackfin]

По сути, задача сводится к транспонированию матрицы. Есть матрица 4x3, из нее получается 3x4:

Скорее, к транспонированию с последующим зеркальным отражением относительно
горизональной линии проходящей через середину матрицы (M/2).
Можно выполнить поворот "на месте", если зарезервировать память под
квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке.

Сообщение отредактировал blackfin - May 18 2007, 18:04

[Doka]

В линейном виде (как в памяти лежит):
Было: Picture[12] = 1 2 3 4 5 6 7 8 9 A B C
Стало: NewPictute[12] = 3 6 9 С 2 5 8 B 1 4 7 A

Попробуйте оперировать двумерными массивами (для памяти всё равно - а программить легче).

тогда задача хорошо параметризуется:
два вложенных цикла с переписыванием массивов.
внешний - по столбцам - с последнего по первый (из столбцов в строки)
внутренний - по элементам столбца (строкам) - с первого по последний




upd: прошу прощения - не увидел про ограничение на память(

а тогда если так: переписывать начиная с 0 адреса
притом ячейку назначение перезаписывать (запоминая старое значение) и потом перезаписывать уже это запомненное значение (т.е. куда оно должно быть перемещено (опять перед перезаписью запомнив старое) и т.д. пока вновь не прийдете на нулевой адрес?

[SasaTheProgramme...]

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

Пример:
По сути, задача сводится к транспонированию матрицы. Есть матрица 4x3, из нее получается 3x4:

Код

1 2 3                       3 6 9 C
4 5 6           =>          2 5 8 B
7 8 9                       1 4 7 A
A B C

В линейном виде (как в памяти лежит):
Было: Picture[12] = 1 2 3 4 5 6 7 8 9 A B C
Стало: NewPictute[12] = 3 6 9 С 2 5 8 B 1 4 7 A

А вот каким алгоритмом можно переставить элементы Picture так чтобы получился NewPicture для произвольных N и M, я не знаю. Подскажите, пожалуйста!

Подозреваю, что просто не получится. Допустим, мы "подняли" некий элемент, вычислили его новый адрес, "подняли" эелемент по новому адресу, положили на его место первый "поднятый". Теперь нужно "пристроить" "висящий" элемент - вычисляем его новый адрес и т.д. Но тут может получиься кольцо, т.е. не перебрав всей матрицы мы вернёмся к адресу первого "поднятого" элемента. Эту ситуацию нужно уметь детектировать и выбирать новый "первый" элемент. Насколько эта ситуация реальна мне сказать трудно, теория чисел не является моим сильным местом. Я бы посоветовал обратиться в fido7.ru.math - там точно с этим справятся. Но если это действительно может случится, то алгоритм может получиться жутко прожорливым как по памяти, так и по времени.
А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ?

[Doka]

А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ?

кстати, да.. забавно, что этого никто не предложил)
вполне рабочее решение если массив потом используется для вывода (или для обработки не требующей строгой ориентации (верт/гориз))

[RHnd]

Скорее, к транспонированию с последующим зеркальным отражением относительно
горизональной линии проходящей через середину матрицы (M/2).

Да, точно.

Можно выполнить поворот "на месте", если зарезервировать память под
квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке.

А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ?

Квадратную матрицу делать нельзя - массив может быть как 1000x1000, так и 10000x1. А памяти мало.
Так же не получится изначально записывать в нужном порядке - в момент начала прихода картинки мы еще ничего не знаем о ее размерах. Фактически, можно сказать, что нам постфактум сообщаются адрес начала, ширина и высота. На счет вычисления адресса руками тоже не пройдет - на выходе мы так же должны предоставить адрес начала, ширину и высоту (новые), а там дальше внешняя прога начнет эти данные гнать наружу.

а тогда если так: переписывать начиная с 0 адреса
притом ячейку назначение перезаписывать (запоминая старое значение) и потом перезаписывать уже это запомненное значение (т.е. куда оно должно быть перемещено (опять перед перезаписью запомнив старое) и т.д. пока вновь не прийдете на нулевой адрес?

Нет, так не получится. Действительно, как отметил SasaTheProgrammer, зацикливание произойдет. Причем, произойдет обязательно.

Я бы посоветовал обратиться в fido7.ru.math - там точно с этим справятся.

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

Сообщение отредактировал RHnd - May 18 2007, 20:35

[anton]

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

[RHnd]

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

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

[SasaTheProgramme...]

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

Ничего специального не нужно, только зарегистрироваться для того чтобы постить. Читать можно даже через гугль :-). Видел в некоторых письмах "отправлено через форум mail.ru", а сам предпочитаю доступаться через ddt.demos.su . Аутлук или тандербирд...

P.S. Отфорвардил туда исходный вопрос, можно гуглить ветку по сабжу "Вопрос с форума".

Сообщение отредактировал SasaTheProgrammer - May 19 2007, 23:21

[gfdsa]

Алгоритм циклической перестановки для поворота картинки достаточно прост. В Ваших терминах:

Picture[12] = 1 2 3 4 5 6 7 8 9 A B C

NewPictute[12] = 3 6 9 С 2 5 8 B 1 4 7 A

берём первый элемент исходного массива «1», он попадает в 9-ю позицию, переставляем, предварительно подняв 9-ку, она переходит в 3-ю позицию и т.д. Для наглядности удобно карандашом рисовать стрелки перестановок – т.е. от верхней «1» кривая стрелка к нижней «1». От нижней «1» вертикально вверх стрелка попадает в девятку и т.д.
В пределах массива образуется группа циклической перестановки элементов. Т.к. элементы исходного и конечного массивов соответствуют 1:1, то никаких пересечений быть не может. Проблема в другом.

Ниже текст примитивной программки выполняющей вышеописанные действия (программа не правильная :-)).

#include <stdio.h>
#include <math.h>

#define MaxA 4
#define MaxB 3
#define MaxC MaxB
#define MaxD MaxA

//--------------------------------

int main(void) {
int a,b,c,d, x,pp,tmp1,tmp2;

union {
int In[MaxA*MaxB];
int Out[MaxC*MaxD];
} Matrix;



x = 0;
for(b=0;b<MaxB;b++)
for(a=0;a<MaxA;a++)
Matrix.In[a + b*MaxA] = x++;


for(b=0;b<MaxB;b++)
{ printf("\n");
for(a=0;a<MaxA;a++)
printf(" %5d ",Matrix.In[a + b*MaxA]);
}

printf("\n");printf("\n");printf("\n");


//#################################
x=0;
a=0; b=0;
tmp1 = Matrix.In[0];

for(;;)
{ if (x++ > MaxA * MaxB) break;

c=b; d=MaxD-1-a;
tmp2 = Matrix.Out[c + d*MaxC];
Matrix.Out[c + d*MaxC] = tmp1;

tmp1 = tmp2;

pp= c + d*MaxC;
b= (int) pp/MaxA;
a= (int) pp - (b*MaxA);

if ((a==0)&&(b==0)) break;
}
//#################################


for(d=0;d<MaxD;d++)
{ printf("\n");
for(c=0;c<MaxC;c++ )
printf(" %5d ",Matrix.In[c + d*MaxC]);
}

return 0;
}

Основная проблема (как и неправильность программы) заключается в том, что группа циклических перестановок не обязательно одна, полностью охватывающая весь массив. Например, для массива 2х3 цепочка одна, а уже для 3х4 циклическая перестановка захватывает только часть элементов. Т.е. для произвольного массива может быть несколько цепочек перестановки – вот в нахождение этих цепочек и есть большая засада. Выполнив одну цепь перестановок тяжело сказать какие элементы ещё остались не переставленными.

Можно предложить несколько путей решения, начну с наихудшего (как для меня):

1. Аналитическое решение. Как для меня – совершенно не интересная задача :-)

2. Написать программку моделирования и прогнать все допустимые размеры входных массивов. Возможно там что-то можно будет увидеть и составить типа таблички или вывести формулку.

3. Выделить битовый массив, с размерами исходного, и в нём отмечать переставленные элементы. После окончания цепи перестановок (окончание цепи – попадаем на позицию элемента, с которого начинали) – в случае недостающего количества перестановок – по массиву находим любой незадействованный элемент и начинаем новую цепь. Дополнительные расходы памяти, чего Вы страшно не хотите.

4. Самое простое, и на мой взгляд, правильное решение – переход к квадратным матрицам. В этом случае всё становится предельно просто – все перестановки осуществляются только в пределах квадрата (например, сначала переставляются только элементы находящиеся на рёбрах самого большого квадрата, потом – предпоследний квадрат массива и т.д.)

[SasaTheProgramme...]

Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала...

Сообщение отредактировал SasaTheProgrammer - May 20 2007, 18:56

[RHnd]

Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала...

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

[shasik]

Не знаю на сколько еще актуально...

Посмотрите книгу "Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры" Под ред. Т.С. Хуанга. Там целый раздел посвящен вопросу транспонирования матриц, причем большое внимание уделяется работе с запоминающими устройствами с последовательным доступом (читай: двумерный массив представлен одномерным). Описаны быстрые (!) алгоритмы, приведены книги где еще можно посмотреть (тот же Кнут упоминается). Почитайте. В свое время книгу эту качал на dsp-book.narod.ru. Ищите, если не найдете, то выложу куда скажете....

[Oldring]

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

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

Считайте, что у вас матрица в одномерном массиве (так и есть - память линейная ). Транспонирование матрицы - это перестановка элементов линейного массива в этой линейной памяти. Любая перестановка элементов упорядоченного множества распадается на набор циклических перестановок. Для квадратной матрицы это - попарные перестановки, для приямоугольной - более длинные циклы. Если элемент матрицы размера MxN имел индекс (i,j), его смещение в исходном массиве было M*i+j, и он переходит в элемент N*j+i. Пусть в этой ячейке располагается элемент (k,m). Имеем уравнение:

M*k+m = N*j+i

откуда

k = floor( (N*j+i) / M )
m = mod( N*j+i, M )

Далее мы переносим уже этот элемент в ячейку с индексом N*k+m и так далее, пока цикл не завершается. Можно бойтись вообще без дополнительной памяти - на каждом шаге переставлять элементы с началом цикла.

Ну и осталось правильно вычислить набор начальных элементов циклов и немного соптимизировать процесс вычисления индексов

[Oldring]

Ну и осталось правильно вычислить набор начальных элементов циклов и немного соптимизировать процесс вычисления индексов

По поводу оптимизации вычисления индексов.

Из уравнений

a = M*i+j
b = N*j+i

следует, что

b = N*a mod N*M-1

Если N*M является степенью двойки, или степенью двойки + 1 - то на поцессоре с быстрым умножением итерация становится тривиальной.