RHnd 0 18 мая, 2007 Опубликовано 18 мая, 2007 · Жалоба Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут. Задача ставиться так - в памяти лежит картинка 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 23 18 мая, 2007 Опубликовано 18 мая, 2007 (изменено) · Жалоба По сути, задача сводится к транспонированию матрицы. Есть матрица 4x3, из нее получается 3x4: Скорее, к транспонированию с последующим зеркальным отражением относительно горизональной линии проходящей через середину матрицы (M/2). Можно выполнить поворот "на месте", если зарезервировать память под квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке. Изменено 18 мая, 2007 пользователем blackfin Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Doka 4 18 мая, 2007 Опубликовано 18 мая, 2007 · Жалоба В линейном виде (как в памяти лежит): Было: 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 18 мая, 2007 Опубликовано 18 мая, 2007 · Жалоба Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут. Задача ставиться так - в памяти лежит картинка 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 18 мая, 2007 Опубликовано 18 мая, 2007 · Жалоба А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ? кстати, да.. забавно, что этого никто не предложил) вполне рабочее решение если массив потом используется для вывода (или для обработки не требующей строгой ориентации (верт/гориз)) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RHnd 0 18 мая, 2007 Опубликовано 18 мая, 2007 (изменено) · Жалоба Скорее, к транспонированию с последующим зеркальным отражением относительно горизональной линии проходящей через середину матрицы (M/2). Да, точно. :) Можно выполнить поворот "на месте", если зарезервировать память под квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке. А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ? Квадратную матрицу делать нельзя - массив может быть как 1000x1000, так и 10000x1. А памяти мало. :( Так же не получится изначально записывать в нужном порядке - в момент начала прихода картинки мы еще ничего не знаем о ее размерах. Фактически, можно сказать, что нам постфактум сообщаются адрес начала, ширина и высота. На счет вычисления адресса руками тоже не пройдет - на выходе мы так же должны предоставить адрес начала, ширину и высоту (новые), а там дальше внешняя прога начнет эти данные гнать наружу. а тогда если так: переписывать начиная с 0 адреса притом ячейку назначение перезаписывать (запоминая старое значение) и потом перезаписывать уже это запомненное значение (т.е. куда оно должно быть перемещено (опять перед перезаписью запомнив старое) и т.д. пока вновь не прийдете на нулевой адрес? Нет, так не получится. Действительно, как отметил SasaTheProgrammer, зацикливание произойдет. Причем, произойдет обязательно. :( Я бы посоветовал обратиться в fido7.ru.math - там точно с этим справятся. А не подскажете, как туда обратиться? Когда-то давно и сам был фидошником, но с тех пор, как интернет прочно вошел в мою жизнь, отстал от положения дел. Там, вроде, надо какой-то специальный софт ставить или что-то такое? Изменено 18 мая, 2007 пользователем RHnd Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
anton 0 19 мая, 2007 Опубликовано 19 мая, 2007 · Жалоба 1. В дсп камнях часто присутствует двумерное дма. 2. Двумерный массив отличается от одномерного только расчетом индекса т.е. можеш в начале засыпать в одномерный массив а потом по этому же начальному адресу обьявить двумерный массив нужной размерности (нужно аккуратно делать поскольку если неправильно то можно вылететь в чужую память), второй вариант самому считать индекс для массива при считывании. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RHnd 0 19 мая, 2007 Опубликовано 19 мая, 2007 · Жалоба 1. В дсп камнях часто присутствует двумерное дма. 2. Двумерный массив отличается от одномерного только расчетом индекса т.е. можеш в начале засыпать в одномерный массив а потом по этому же начальному адресу обьявить двумерный массив нужной размерности (нужно аккуратно делать поскольку если неправильно то можно вылететь в чужую память), второй вариант самому считать индекс для массива при считывании. И чем это поможет? Мне-то нужно в рамках имеющейся памяти упорядочить масив так, чтоб он представлял собой повернутую картинку. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SasaTheProgrammer 0 19 мая, 2007 Опубликовано 19 мая, 2007 (изменено) · Жалоба А не подскажете, как туда обратиться? Когда-то давно и сам был фидошником, но с тех пор, как интернет прочно вошел в мою жизнь, отстал от положения дел. Там, вроде, надо какой-то специальный софт ставить или что-то такое? Ничего специального не нужно, только зарегистрироваться для того чтобы постить. Читать можно даже через гугль :-). Видел в некоторых письмах "отправлено через форум mail.ru", а сам предпочитаю доступаться через ddt.demos.su . Аутлук или тандербирд... P.S. Отфорвардил туда исходный вопрос, можно гуглить ветку по сабжу "Вопрос с форума". Изменено 19 мая, 2007 пользователем SasaTheProgrammer Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
gfdsa 0 20 мая, 2007 Опубликовано 20 мая, 2007 · Жалоба Алгоритм циклической перестановки для поворота картинки достаточно прост. В Ваших терминах: 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 20 мая, 2007 Опубликовано 20 мая, 2007 (изменено) · Жалоба Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала... Изменено 20 мая, 2007 пользователем SasaTheProgrammer Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RHnd 0 21 мая, 2007 Опубликовано 21 мая, 2007 · Жалоба Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала... учитывая, что время нам не критично, то это действительно пока-что лучший алгоритм. PS: Сегодня согласовывал память. Возможно, выделится место под дополнительный кадр. :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
shasik 0 25 мая, 2007 Опубликовано 25 мая, 2007 · Жалоба Не знаю на сколько еще актуально... Посмотрите книгу "Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры" Под ред. Т.С. Хуанга. Там целый раздел посвящен вопросу транспонирования матриц, причем большое внимание уделяется работе с запоминающими устройствами с последовательным доступом (читай: двумерный массив представлен одномерным). Описаны быстрые (!) алгоритмы, приведены книги где еще можно посмотреть (тот же Кнут упоминается). Почитайте. В свое время книгу эту качал на dsp-book.narod.ru. Ищите, если не найдете, то выложу куда скажете.... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 25 мая, 2007 Опубликовано 25 мая, 2007 · Жалоба учитывая, что время нам не критично, то это действительно пока-что лучший алгоритм. 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 26 мая, 2007 Опубликовано 26 мая, 2007 · Жалоба Ну и осталось правильно вычислить набор начальных элементов циклов и немного соптимизировать процесс вычисления индексов :) По поводу оптимизации вычисления индексов. Из уравнений a = M*i+j b = N*j+i следует, что b = N*a mod N*M-1 Если N*M является степенью двойки, или степенью двойки + 1 - то на поцессоре с быстрым умножением итерация становится тривиальной. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться