DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
- Computer Graphics (2:5030/84) --------------------------------- SU.GRAPHICS - Msg : 2911 of 2914 From : Maxim Ilyn 2:5027/5.15 06 Dec 97 00:17:03 To : All 07 Dec 97 00:25:07 Subj : DCT of xPEG ------------------------------------------------------------------------------- Hi All ! Занялся тут преобразованием видеоданных - блок 8x8 в частотные гармоники с помощью DCT и нашел некоторые противоречия в толковании jpeg : 1. Книга "Цифровая обработка цветных изображений" Ганс Юрген Шлихт. Преобразование считается перемножением входных данных на матрицы DCT и DCTt (8x8), где : DCTij = 1/sqr(N), если i=0 DCTij = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i>0 где N=8 DCTt образуется из DCT переставлением строк в столбцы, т.е. первый элементстроки - первый столбца, второй элемент первой строки - вторым элементом первого столбца и т.д. - транспонирование по научному. Далее перемножаются матрица входных данных и DCTt, потом DCT на полученную. Значения вроде бы получаются как в книжном примере, но некоторые коэф. другие. Да и зачем еще раз перемножать после DCTt на DCT, если и так после первого умножения большинство коэф. получаются нулевыми ? А после второго умножения нулевых уже немного меньше. При восстановлении данных сначала перемножаем их на DCT, потом на DCTt матрицу. 2.Книга "Форматы графических файлов" А.С.Климов от DiaSoft. Коэффициенты расчитываются по уровнению : 1 7 7 (2x+1)*u*Pi (2x+1)*v*Pi F(u,v)= - *C(u)*C(v)*[Sum Sum f(x,y)*cos----------- * cos----------- ] 4 x=0 y=0 16 16 где Pi=3.14 , f(x,y) - исходные данные , F(x,y) - пространственные частоты С(u)= {1/sqrt(2), если u=0 { 1 , если u<>0 C(v) - аналгично. Для восстановления данных используем : 1 7 7 (2x+1)*u*Pi (2x+1)*v*Pi f(x,y)= - * [Sum Sum C(u)*C(v)*F(u,v)*cos----------- * cos----------- ] 4 x=0 y=0 16 16 я проделал преобразования по первому принципу с разными исходными данными - синусоидальное изменение, плавное, быстрое наростание, уменьшение и примерно (была еще квантизация коэффициентов) получал достоверные данные с точность 10%. Если же считать по второму принципу, то в основном получаются отрицательные коэф. и очень большие значения по диагонали. При квантизации появлялись нулевые элементы - но не так много, но что самое главное - начальные значения после восстановления были вообще не такими - некоторые на порядок больше. Как я изучал на втором курсе преобразование Фурье - коэф. считаются при четной функции и одномерном преобразовании : 2 N Pi*k*x a(k)= - * Sum f(x)*cos------ N x=0 N т.е правильным должен быть как раз второй метод - суммируются все элементы с определенными множитялями, а в первом только сопряженные по строке и столбцам, но ближе почему-то оказывается первый способ. Может какая ошибка во вторых формулах ? Какое преобразование из этих используется в jpeg ? Как сюда притянуть fast DCT - т.е. быстрое косинус преобразование Фурье ? Подскажите, плз, не дайте помереть молодым. ;-) C уважением. Maxim Ilyn
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- Algorithms.. (2:5030/84) ------------------------------------ RU.ALGORITHMS - Msg : 6213 of 6229 From : Aleksandr Goltsov 2:5020/400 13 Jan 98 23:22:16 To : All 17 Jan 98 00:34:26 Subj : Re: DCT in JPEG ------------------------------------------------------------------------------- From: "Aleksandr Goltsov" <rattus@cityline.ru> Maxim Ilyn <Maxim.Ilyn@p25.f16.n5027.z2.fidonet.org> записано в статью <884670318@p25.f16.n5027.z2.ftn>... ---------- : Занялся тут преобразованием видеоданных - блок 8x8 в частотные гармоники : с помощью DCT и нашел некоторые противоречия в толковании jpeg : : : 1. Книга "Цифровая обработка цветных изображений" Ганс Юрген Шлихт. : Преобразование считается перемножением входных данных на матрицы : DCT и DCTt (8x8), где : : : DCTij = 1/sqr(N), если i=0 : DCTij = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i>0 : где N=8 : Так и есть. Такая же формула в журнале "Монитор" ? 6, 1994. (Прекратил существование -- а какой классный был журнал!) Там же программа сжатия ДКП-преобразованием на С (подобие того, что в стандарте JPEG, только финальное сжатие без потерь -- послабее). Hабивал. Переводил на Паскаль. Работает. Могу кинуть. : DCTt образуется из DCT переставлением строк в столбцы, т.е. первый : элементстроки - первый столбца, второй элемент первой строки - вторым : элементом первого столбца и т.д. - транспонирование по научному. : Далее перемножаются матрица входных данных и DCTt, потом DCT на : полученную. Значения вроде бы получаются как в книжном примере, но : некоторые коэф. другие. Да и зачем еще раз перемножать после DCTt на : DCT, если и так после первого умножения большинство коэф. получаются : нулевыми ? А после второго умножения нулевых уже немного меньше. : При восстановлении данных сначала перемножаем их на DCT, потом на : DCTt матрицу. Все правильно. Одномерное ДКП вычисляется перемножением вектора выборок на матрицу коэффициентов (или наоборот? не важно). Двумерное ДКП (для матрицы, т.е. вектора векторов) вычисляется с дополнительным перемножением на транспонированную матрицу коэффициентов. А как ты иначе собираешься делать обратное ДКП при распаковке, если не завершишь прямое ДКП, не умножив на транспонированную матрицу? Особенность унитарных преобразований (в т.ч. ДКП и ДПФ<урье>): транспонированная матрица коэффициентов является обратной самой себе, т.е. DCT(-1)=DCTt DCT * DCTt = E Точность прямого-обратного преобразования для вещественных коэффициентов, байтовых входных данных и двухбайтовых частотных данных у меня была такова: после восстановления (без квантизации, естественно) ошибка не превышала единицы младшего разряда, т.е., если говорить об изображении, на глаз это HИКАК не воспринимается, и само по себе ДКП искажений не вносит. : : 2.Книга "Форматы графических файлов" А.С.Климов от DiaSoft. : Коэффициенты расчитываются по уровнению : : : 1 7 7 (2x+1)*u*Pi (2x+1)*v*Pi : F(u,v)= - *C(u)*C(v)*[Sum Sum f(x,y)*cos----------- * cos----------- ] : 4 x=0 y=0 16 16 : !!!!!!!! Опечатка! Под одним косинусом д.б. x,u , а под другим y,v : где Pi=3.14 , f(x,y) - исходные данные , F(x,y) - пространственные частоты : : С(u)= {1/sqrt(2), если u=0 : { 1 , если u<>0 : : C(v) - аналгично. : : Для восстановления данных используем : : : 1 7 7 (2x+1)*u*Pi (2x+1)*v*Pi : f(x,y)= - * [Sum Sum C(u)*C(v)*F(u,v)*cos----------- * cos----------- ] : 4 x=0 y=0 16 16 : !!!!!!!! Опечатка! Под одним косинусом д.б. x,u , а под другим y,v : : я проделал преобразования по первому принципу с разными исходными : данными - синусоидальное изменение, плавное, быстрое наростание, : уменьшение и примерно (была еще квантизация коэффициентов) получал : достоверные данные с точность 10%. : Если же считать по второму принципу, то в основном получаются : отрицательные коэф. и очень большие значения по диагонали. При : квантизации появлялись нулевые элементы - но не так много, но : что самое главное - начальные значения после восстановления : были вообще не такими - некоторые на порядок больше. : Как я изучал на втором курсе преобразование Фурье - коэф. считаются : при четной функции и одномерном преобразовании : : : 2 N Pi*k*x : a(k)= - * Sum f(x)*cos------ : N x=0 N : : т.е правильным должен быть как раз второй метод - суммируются все : элементы с определенными множитялями, а в первом только сопряженные : по строке и столбцам, но ближе почему-то оказывается первый способ. : Может какая ошибка во вторых формулах ? : Какое преобразование из этих используется в jpeg ? В JPEG используется ДКП (DCT) -- оно, если говорить о результатах вычисления, одно единственное. Оно, естественно, вычисляется с помощью быстрого алгоритма -- в обоих приведенных тобой случаях имеется лобовое перемножение матриц. Кстати -- для матриц 8х8 существует (в руках не держал, читал в авторефератах диссертаций МГУ) алгоритм приближенного вычисления ДКП за 538 (если не ошибаюсь) сложений БЕЗ ОПЕРАЦИЙ УМHОЖЕHИЯ. : Как сюда притянуть fast DCT - т.е. быстрое косинус преобразование : Фурье ? Быстрое ДКП вычисляется не лобовым перемножением матриц, а на основе алгоритма быстрого ДПФ. Выигрыш по скорости тем больше, чем больше размерность матриц. Для 8х8 кажется получается в 2.7 раза быстрее (так в книжках пишут). : Подскажите, плз, не дайте помереть молодым. ;-) : : C уважением. Max. : Александр (с наилучшими пожеланиями) rattus@cityline.ru

Всего 2 фpагмент(а/ов) |пpедыдущий фpагмент (2)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".