DCT - Дискретное косинусное преобразование

Есть ли у кого нибудь исходники прямого и обратного ДКП?

www.fftw.org - Быстрое Преобразование Фурье

ты линк не по той теме дал ему нужно DCT, а не DFT
2Vadim
если хотишь я тебе дам исходник для разжатия блоков 8*8, с 4 (по-моему) умножениями
(и то с фиксированной точкой - good). недавно придумали более крутой алгоритм - без
умножений _вообще_ называется binary DCT. только вот исходников нигде нет!

Сообщение отредактировано: vot - 01.06.02, 12:01

Вы простите чайника, а чем собсно отличается FFT и DCT? Ну так, по сути?

У меня есть такой старый-старй журнал (года эдак 94) "Монитор".
В нём есть не только сорсы, но итекстовое описание.
Так что если надо пиши на майл, отсканирую - отправлю, но не обессудь,
мыло проверю не ранее вторника, а тправлю скорее всего в четверг
(да не, не после дождичка)

Сообщение отредактировано: vot - 01.06.02, 12:02

У меня есть все исходники  :P

Сообщение отредактировано: Codemaster - 06.03.02, 10:44

Цитата Codemaster, 06.03.02, 13:43:38

У меня есть все исходники  

Слушай, а может исходнички Win98 подкинешь?  ;) А то никак, что-то в инете не найду... ;D

DCT прямое и обратное делается умножением на одну и туже матрицу констант.
DFT делается несколько сложнее, т.к. работаем с комплексными числами.
Хорошо знаем что кайф делать быстрое DFT. А вот есть ли кайф городить быстрое
DCT и на сколько? Во всех справочниках молчат про быстрое DCT, хотя на первый взгляд
алгоритм просматривается. Если кому интересно можно поболтать на эту тему.

int ForwardDCT(long *pSrc,                      long **ppDst,                      long iN){      long u, v, x, y;      for(v=0; v<iN; v++)            for(u=0; u<iN; u++)            {                  float F = 0.0f;                                    float cu = 1.0f, cv = 1.0f;                  if(u==0) cu = 1.0f / sqrtf(2.0f);                  if(v==0) cv = 1.0f / sqrtf(2.0f);                  for(y=0; y<iN; y++)                        for(x=0; x<iN; x++)                              F+=(float)pSrc[y*iN + x] *                               cosf(((2*(float)x + 1) * (float)u * PI)/(2*(float)iN)) *                              cosf(((2*(float)y + 1) * (float)v * PI)/(2*(float)iN));                  F*=(2.0f/(float)iN)*cu*cv;                  (*ppDst)[v*iN + u] = (long)F;                              }      return 0;}int InverseDCT(long *pSrc,                      long **ppDst,                      long iN){      long u, v, x, y;      for(y=0; y<iN; y++)            for(x=0; x<iN; x++)            {                  float f = 0.0f;                                    for(v=0; v<iN; v++)                        for(u=0; u<iN; u++)                        {                              float cu = 1.0f, cv = 1.0f;                              if(u==0) cu = 1.0f / sqrtf(2.0f);                              if(v==0) cv = 1.0f / sqrtf(2.0f);                              f+=cu*cv*(float)pSrc[v*iN + u] *                                   cosf(((2*(float)x + 1) * (float)u * PI)/(2*(float)iN)) *                                   cosf(((2*(float)y + 1) * (float)v * PI)/(2*(float)iN));                        }                  f*=(2.0f/(float)iN);                  (*ppDst)[y*iN + x] = (long)f;            }      return 0;}

Сообщение отредактировано: vot - 01.06.02, 12:04

2andyag
угу, только этот вариант офигенно тормознутый.
нет ли у тебя удобопонимаемого примера который делает ОДКТ быстрее?

...вот тебе и спасибо...

Могу кинуть .pdf про оптимизацию сабжа...

Цитата andyag, 27.04.02, 22:36:47

...вот тебе и спасибо...

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

лови pdf

Почитал я ребята про быстрое Фурье. Написал прогу ,вообще не имеет отношение к делу.
О ни в ЖПГ фазу сдвигают.Вот и Аndiag 1 в косинус добавил. Это делается быстрее если
матрицу косинусов заранее посчитать и потом на матрицы умножать.Некоторые процессоры ,кстати , для этого пытаются оптимизировать. Так хотелось разбить 2-мерную фигню на 2 одномерные и быстро их просчитать, но для этого видимо нужно или повышать размерность матрицы дополняя ее симметричной, или считать полное Фурье.
А может у кого мысль какая есть, или желание хотябы прикинуть как считать быстрее,
или положить на ЖПГ и FFT попробывать?

2 Codemaster:
Если у тебя есть все исходники ,может подкинешь исходник I-Worm.Klez.e

Чего-то я не понимаю - о чем вы говорите? Какие нафиг просчеты матриц косинусов?
Вроде исходники jpeg'а открытые валяются где хочешь! Там дкт на 5 умножениях и 25 сложениях, а вы блин велосипед изобретаете, вам че делать не хера нечего?

Сообщение отредактировано: vot - 17.07.02, 16:56

2 Sablin Sergey
Здесь не принято ругаться...

2Sablin Sergey
дык если везде валяются на 5 умножений и 25 сложений, дай, именно этот кусок.
было у меня сколько-то исходников, а вот выдрать это ОДКТ так, чтобы отдельно, не получилось, куча define'ов левых, глобалдьных переменных и левых подпрограмм. конечно, понятно, что так быстрее, но разобраться в этом у меня не получилось...\%)
ЗЫ может я тупой?

2 Demo_S:

<br>int ForwardDCT(      long *lvBlockIn, <br>                        long **lplvBlockSpecOut,<br>                        float *fvDCTCosTable,<br>                        long iN)<br>{<br>      long i, j, k;<br><br>      float *fvTmp = new float[iN*iN];<br><br>      for(i=0; i<iN; i++)<br>            for(j=0; j<iN; j++)<br>            {<br>                  float fSum = 0.0f;<br><br>                  for(k=0; k<iN; k++)<br>                        fSum+=(float)lvBlockIn[i*iN + k]*fvDCTCosTable[j*iN + k];<br><br>                  fvTmp[i*iN + j] = fSum;<br>            }<br><br>      for(i=0; i<iN; i++)<br>            for(j=0; j<iN; j++)<br>            {<br>                  float fSum = 0.0f;<br><br>                  for(k=0; k<iN; k++)<br>                        fSum+=(float)fvTmp[k*iN + j]*fvDCTCosTable[i*iN + k];<br><br>                  (*lplvBlockSpecOut)[i*iN + j] = (long)fSum;<br>            }<br><br>      RELEASE(fvTmp);<br><br>      return 0;<br>}<br><br>int InverseDCT(      long *lvBlockSpecIn, <br>                        long **lplvBlockOut,<br>                        float *fvDCTCosTable,<br>                        long iN)<br>{<br>      long i, j, k;<br><br>      float *fvTmp = new float[iN*iN];<br>      for(i=0; i<iN; i++)<br>            for(j=0; j<iN; j++)<br>            {<br>                  float fSum = 0.0f;<br><br>                  for(k=0; k<iN; k++)<br>                        fSum+=(float)lvBlockSpecIn[i*iN + k]*fvDCTCosTable[k*iN + j];<br><br>                  fvTmp[i*iN + j] = fSum;<br>            }<br><br>      for(i=0; i<iN; i++)<br>            for(j=0; j<iN; j++)<br>            {<br>                  float fSum = 0.0f;<br><br>                  for(k=0; k<iN; k++)<br>                        fSum+=(float)fvDCTCosTable[k*iN + i]*fvTmp[k*iN + j];<br><br>                  (*lplvBlockOut)[i*iN + j] = (long)fSum;<br>            }<br><br>      RELEASE(fvTmp);<br><br>      return 0;<br>}<br><br>int GenDCTCosTable(      float **lpfvDCTCosTable, <br>                              long iN)<br>{<br>      long i, j;<br><br>      float k1 = 1.0f/sqrtf((float)iN);<br>      float k2 = sqrtf(2.0f/iN);<br>      <br>      for(i=0; i<iN; i++)<br>            for(j=0; j<iN; j++)<br>                  (*lpfvDCTCosTable)[i*iN + j] = i ? k2*cosf((2.0f*j+1)*i*PI/2.0f/iN) : k1;<br><br>      return 0;<br>}<br>

Работает довольно быстро. Теперь-то спасибо скажешь?  ;D

Сообщение отредактировано: andyag - 25.07.02, 17:36

Чего-то вы прислали 2*iN*iN умножений и сложений к ним немало, к тому же таблицы
косинусов не дослали. Вобщем матрицы умножаем, а гдеже быстрый счет. Пришлите что-нибудь другое, а то уже велосипедов наизобретал, хотелось бы сравнить с фирменными моделями.

Цитата rem, 08.08.02, 18:37:33

...к тому же таблицы
косинусов не дослали...

Не понял...
Функция GenDCTCosTable генерит матрицу преобразования (aka таблица косинусов). Там есть ее реализация (снизу)

…я нашел исходник DCT для MMX…  : Но, по-моему, это понять вообще невозможно… Автор – какой-то японец, и все комментарии по-ихнему. Только readme на английском.

Вот кусочек:   MMX_DCT is a implementation for 8x8 FDCT/IDCT with MMX technology.  With the help of MMX, only about 1000 cpu cycle is needed to do a 8x8 IDCT…

Скачать можно здесь: http://homex.coolconnect.com/user/xkwang/mmxdct/mmxdct-1.0.tar.gz  

Цитата MYSTiQUE, 01.06.02, 02:17:51

2 Codemaster:
Если у тебя есть все исходники ,может подкинешь исходник I-Worm.Klez.e

Тебе исходник в кодах (готовый рабочий модуль) или в виде путевого листинга

Dr.Andiag. Извини, уезжал на море, толком не посмотрел. Это умножение матриц, данный алгоритм не относится к т.н. быстрым алгоритмам. Давай посчитаем число операций:   2*n*n*(n*( умнож.+слож.)). Быстрое двумерное DCT описано в книге под редакцией В.А.Сойфера "Методы компьютерной обработки". Напиши почему ты этим интересуешься ?" P.S. Ехал с моря, заезжал в Воронеж.    :)  

Цитата rem, 30.08.02, 12:20:35

Dr.Andiag. Извини, уезжал на море, толком не посмотрел. Это умножение матриц, данный алгоритм не относится к т.н. быстрым алгоритмам. Давай посчитаем число операций:   2*n*n*(n*( умнож.+слож.)). Быстрое двумерное DCT описано в книге под редакцией В.А.Сойфера "Методы компьютерной обработки". Напиши почему ты этим интересуешься ?" P.S. Ехал с моря, заезжал в Воронеж.      

Я знаю, что этот алгоритм не относится к быстрым. Я сказал, что он работает быстро
Быстрее, чем без матриц.
Где б мне взять В.А.Сойфера "Методы компьютерной обработки"?  ???
Интересуюсь я этим потому, что... Гм... а хз. Мне интересно все, что не базы данных и не системное  ;)
А как тебе Воронеж?

Книга п.р. Сойфера(Москва,физматлит,2001) рекомендована Министерством образования как учебник для обучающихся по специальности "Прикладная математика".Думаю, что она должна быть в библиотеке ВГУ, или любого ВУЗа, где есть эта специальность. Для понимания двумерных алгоритмов вводятся понятия кватерниона и кватернионного спектра. При желании можно в этом поупражняться ,но, в этом случае, думаю нужно переходить на мыло. Понять написанное проще если ранее доводилось писать быстрые алгоритмы.  
   В Воронеже мне показалось, что плохо работают коммунальные службы, из-за чего люди несколько озлоблены. Если бы основные предприятия города работали эффективно , то это бы был крупнейший в Европе промышленный центр.
         Ждем вестей из Воронежа и других городов.        

А я завтра какраз в ВГУ иду
У меня препод по информатике умный - может у него есть?

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

посмотри в матлабе там есть и формулы и исходника на аля матлабовском языке

трехмерный трансформ пишется с помощью одномерного применненого три раза

GrAnd мне бы прислал исходники клеза, всё чё есть forb@nvkz.net плиз

я так и не понял, нашли вы быстрое дискретное косинус преобразование, или нет?

я сам писал обычное DCT 2,3,4,5 рода
а также быстрое DCT 2,3 рода, где время пропорционально N. (N - степень двойки)

кому надо, давайте адреса, скину.

javascript:emoticon(':whistle:')

Jedago
залей плиз на kast2k2001@mail.ru

Отправил, наслаждайся...

и сюда пожалуйста vip_delete@mail.ru, еще Вы еще сюда заглядываете.

Привет, если у кого-то остались исходники прямого и обратного ДКП скиньте их пожалуйста на vale-kapu@yandex.ru, буду оч. признательна!

Привет! Тоже актуально, если есть у кого исходники прямого и обратного ДКП залейте, пожалуйста на dronja@bigmir.net

http://www.srcc.msu.su/num_anal/lib_na/cat/ft/fta5r.htm