[RHnd 0]

Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут.

Задача ставиться так - в памяти лежит картинка 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 28]

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

Скорее, к транспонированию с последующим зеркальным отражением относительно

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

Можно выполнить поворот "на месте", если зарезервировать память под

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

Изменено 18 мая, 2007 пользователем blackfin

[Doka 4]

В линейном виде (как в памяти лежит):

Было: 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 адреса

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

[SasaTheProgrammer 0]

Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут.

Задача ставиться так - в памяти лежит картинка 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 4]

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

кстати, да.. забавно, что этого никто не предложил)

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

[RHnd 0]

Скорее, к транспонированию с последующим зеркальным отражением относительно

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

Да, точно. :)

Можно выполнить поворот "на месте", если зарезервировать память под

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

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

Квадратную матрицу делать нельзя - массив может быть как 1000x1000, так и 10000x1. А памяти мало. :(

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

 

а тогда если так: переписывать начиная с 0 адреса

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

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

 

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

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

Изменено 18 мая, 2007 пользователем RHnd

[anton 0]

1. В дсп камнях часто присутствует двумерное дма.

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

[RHnd 0]

1. В дсп камнях часто присутствует двумерное дма.

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

 

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

[SasaTheProgrammer 0]

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

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

 

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

Изменено 19 мая, 2007 пользователем SasaTheProgrammer

[gfdsa 0]

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

 

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

[SasaTheProgrammer 0]

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

Изменено 20 мая, 2007 пользователем SasaTheProgrammer

[RHnd 0]

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

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

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

[shasik 0]

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

 

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

[Oldring 0]

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

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 0]

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

 

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

 

Из уравнений

 

a = M*i+j

b = N*j+i

 

следует, что

 

b = N*a mod N*M-1

 

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