Easyelectronics.ru

Электроника для всех
Текущее время: 23 сен 2020, 09:02

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/5шт. два слоя. $5/5шт. четыре слоя
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 02 июн 2016, 02:39 
Заглядывает иногда

Зарегистрирован: 12 апр 2013, 18:59
Сообщения: 33
Здравствуйте,
Пытаюсь реализовать алгоритм сабжа. Нашел вот такое описание. Вот обычный DCT, с примером, на странице 3 есть исходная матрица значений 8х8, а чуть ниже матрица с вычисленными значениями DCT коэфициентов.
Для начала я пробую реализовать сам алгоритм binDCT (версию А) на Питоне, что бы понять последовательность действий и получить хотя бы приблизительно такой же результат как в обычном примере. В документации на binDCT описан 1D алгоритм, но двумерную матрицу надо обрабатывать в таком порядке:
1. Сначала преобразуем каждую строку по алгоритму в схеме.
2. Затем преобразованию подвергаются столбцы матрицы полученной в результате пункта один.
Т.е. проходим строки, транспонируем матрицу, проходим строки опять же, транспонируем обратно
Сам алгоритм в доке(я использую версию А) можно разбить на 7 этапов. Показано на рисунке.
Show Рисунок

Вот питоновский скрипт этого алгоритма(специально разбит на этапы и избыточен для удобства поиска ошибок и быстрой замены коэф.)
Show Код

DCT коэфициенты которые я получаю в результат и близко не подходят к примеру.
Show Результат


Подскажите что я делаю не так ?


Последний раз редактировалось birst 02 июн 2016, 10:36, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 02 июн 2016, 03:09 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
http://web.archive.org/web/200910271636 ... ar/dct.htm


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 05 июн 2016, 16:55 
Заглядывает иногда

Зарегистрирован: 12 апр 2013, 18:59
Сообщения: 33
Кажется нашел в чем ошибка. Но возник вопрос по матрицам.
В примере матрица трансформации разлагается на произведение матриц. Вот нашел статью на русском и взял матрицу трансформации оттуда.
Матрица P' разлалается на произведение 4 матриц, P' = a*b*c*d. По свойству ассоциативности порядок перемножения матриц не играет роли, однако результаты получаются совсем другими.
Т.е.
Код:
import numpy as np
a = np.matrix ('16 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 22 0 0 0 8 0; 0 0 0 1 0 0 0 0; 0 0 0 0 16 0 0 0; 0 0 0 0 0 1 0 0; 0 0 8 0 0 0 -22 0; 0 0 0 0 0 0 0 1')
b = np.matrix ('1 0 0 0 1 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 1 0 0 0 -1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1')
c = np.matrix ('1 0 0 0 0 0 1 0; 0 22 0 18 0 12 0 4; 1 0 0 0 0 0 -1 0; 0 18 0 -4 0 -22 0 -12; 0 0 1 0 1 0 0 0; 0 12 0 -22 0 4 0 18; 0 0 1 0 -1 0 0 0; 0 4 0 -12 0 18 0 -22')
d = np.matrix ('1 0 0 0 0 0 0 1; 1 0 0 0 0 0 0 -1; 0 1 0 0 0 0 1 0; 0 1 0 0 0 0 -1 0; 0 0 1 0 0 1 0 0; 0 0 1 0 0 -1 0 0; 0 0 0 1 1 0 0 0 ; 0 0 0 1 -1 0 0 0')

P = a*b*c*d
print P

Результат - как и должно быть.
Код:
[ 16  16  16  16  16  16  16  16]
[ 22  18  12   4  -4 -12 -18 -22]
[ 22   8  -8 -22 -22  -8   8  22]
[ 18  -4 -22 -12  12  22   4 -18]
[ 16 -16 -16  16  16 -16 -16  16]
[ 12 -22   4  18 -18  -4  22 -12]
[  8 -22  22  -8  -8  22 -22   8]
[  4 -12  18 -22  22 -18  12  -4]


Меняем порядок

Код:
import numpy as np
a = np.matrix ('16 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 22 0 0 0 8 0; 0 0 0 1 0 0 0 0; 0 0 0 0 16 0 0 0; 0 0 0 0 0 1 0 0; 0 0 8 0 0 0 -22 0; 0 0 0 0 0 0 0 1')
b = np.matrix ('1 0 0 0 1 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 1 0 0 0 -1 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 1')
c = np.matrix ('1 0 0 0 0 0 1 0; 0 22 0 18 0 12 0 4; 1 0 0 0 0 0 -1 0; 0 18 0 -4 0 -22 0 -12; 0 0 1 0 1 0 0 0; 0 12 0 -22 0 4 0 18; 0 0 1 0 -1 0 0 0; 0 4 0 -12 0 18 0 -22')
d = np.matrix ('1 0 0 0 0 0 0 1; 1 0 0 0 0 0 0 -1; 0 1 0 0 0 0 1 0; 0 1 0 0 0 0 -1 0; 0 0 1 0 0 1 0 0; 0 0 1 0 0 -1 0 0; 0 0 0 1 1 0 0 0 ; 0 0 0 1 -1 0 0 0')

P = d*b*c*a
print P


Результат
Код:
[ 16   4  30 -12  16  18 -14 -22]
[ 16  -4  30  12  16 -18 -14  22]
[  0  22  22  18 -16  12   8   4]
[  0  22 -22  18  16  12  -8   4]
[ 16  12  -8 -22   0   4  22  18]
[ 16 -12  -8  22   0  -4  22 -18]
[ 16  18 -14  -4 -16 -22 -30 -12]
[-16  18  14  -4  16 -22  30 -12]


Как так то ? Ничего не понимаю.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 05 июн 2016, 18:02 
Старожил

Зарегистрирован: 14 сен 2015, 08:50
Сообщения: 206
Откуда: Россия, Ростов-на-Дону
birst писал(а):
По свойству ассоциативности порядок перемножения матриц не играет роли, однако результаты получаются совсем другими.

Как так то ? Ничего не понимаю.

Ассоциативность это (A*B)*C=A*(B*C) для матриц действительно выполняется. Но умножение у матриц (в общем случае) не коммутативно, т.е. A*B<>B*A. Если бы у Вас матрицы были бы не квадратными, то вообще нельзя было бы переставлять множители местами. Так что все с результатами у Вас нормально (саму арифметику не проверял).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 05 июн 2016, 19:24 
Заглядывает иногда

Зарегистрирован: 12 апр 2013, 18:59
Сообщения: 33
vbogom писал(а):
birst писал(а):
По свойству ассоциативности порядок перемножения матриц не играет роли, однако результаты получаются совсем другими.
Как так то ? Ничего не понимаю.

Ассоциативность это (A*B)*C=A*(B*C) для матриц действительно выполняется. Но умножение у матриц (в общем случае) не коммутативно, т.е. A*B<>B*A. Если бы у Вас матрицы были бы не квадратными, то вообще нельзя было бы переставлять множители местами. Так что все с результатами у Вас нормально (саму арифметику не проверял).

Большое спасибо за ответ. Но не подскажите тогда по следующему ? Суть метода описанного в статье (как я понимаю) заключается в том что бы матрицу трансформации Р представить в ввиде произведения более простых матриц, таким образом при умножении на этой матрицы(Р) на вектор снизить вычислительную нагрузку, путем перемножения вектора на отдельные множители-матрицы(более простые). Иными словами Х = P*V, где Р = a*b*c*d (произведение более простых матриц). Т.е. Х = (a*b*c*d)*V. Где V вектор входных значений. Как тогда можно записать это уравнение что бы соблюдалось условие (последовательное умножение вектора на эти матрицы) ? Х = a*(b*c*d*V) ? Тогда метод не имеет смысла, потому что вначале придется перемножать матрицы b*c*d между собой (зачем тогда раскладывать) ?
Заранее спасибо.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Дискретное косинусное преобразование. BinDCT
СообщениеДобавлено: 06 июн 2016, 00:03 
Старожил

Зарегистрирован: 30 апр 2010, 22:56
Сообщения: 1589
Откуда: Киев
birst писал(а):
Тогда метод не имеет смысла, потому что вначале придется перемножать матрицы b*c*d между собой (зачем тогда раскладывать) ?
Заранее спасибо.

Не на абы какие, а на максимально разреженные, содержащие как можно больше нулей. Если в матрице нуль, то мы избавляемся от пачки умножений.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB