Войти
ПрограммированиеФорумОбщее

Упаковка графика функции (4 стр)

Страницы: 1 2 3 4 5 Следующая »
#45
4:42, 28 ноя. 2016

foxes
Там подразумевался доступ по произвольному индексу, а не последовательно. Если последовательно - можно быстрее. Не ухудшит ли это нам качество - хз.

>В идеале приближения с равными порядками, 0xFFFFnnnn, 0x0000nnnn - я думаю это поможет.
Мой код как раз вычитает битовые представления.

}:+()___ [Smile]
То взятие дробной части, которое n-floor(n) - всего лишь ведь выделяет младшие биты мантиссы. То, которое внутри синуса - да, добавляет рандом. Как и умножение.
Можно видимо без синуса, тупо дробной частью.
Ну и я не особо видел использование синуса в качестве рандома за пределами шейдеров, где какбы и от безрыбья.


#46
9:30, 28 ноя. 2016

foxes

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

> Если взять твой пример с разницей 0,0001 между "табличным" 0.0011
Мой пример - когда одна разница 0.0001, а следующая - в десять раз больше, поэтому разница 0xFFF2E48F там никак не получится.

> Но я бы вообще разделил хранение порядка и мантисы
Что толку то? Мантисса это шум - я тебе это показал на примере с разностями, отличающимися больше чем в два раза.

> Но я бы вообще разделил хранение порядка и мантисы
У тебя за последние две страницы алгоритм уже несколько раз изменился. Так что я не очень понимаю фразу
> Вот вы оба либо не видите либо ни когда этого не делали
Ты сам то это делал хоть раз? Если делал - напиши по пунктам. Какое преобразование нужно использовать, сколько коэффициентов оставлять, какое при этом получалось значение PSNR, что дальше с разностями делалось.

#47
12:17, 28 ноя. 2016

IROV..
>Тут ты прав, первое что в голову приходит это преобразовать такой график в dF и хранить дельта значение - но чем паковать даже такое?
Это опять таки частное решение.
Как например тогда паковать такой график y² =x ? или что-нибудь посложнее ?

#48
17:38, 28 ноя. 2016

Ghost2
> У тебя за последние две страницы алгоритм уже несколько раз изменился.
как я изначально хотел найти приближенную функцию, каким бы то ни было способом разложения (очевидно лучшим вариантом будет комбинирование нескольких), для последующего сжатия данных повышающих точность до оригинала, так он и остался.
Ghost2
> Мой пример - когда одна разница..
наглядно можешь представить ряд чисел и приближенную функцию чтобы это продемонстрировать, потому как я этого не увидел.
Ghost2
> а следующая - в десять раз больше
что значит следующая?
есть числа рада 0.0001 (0x38d1b717), 0.001 (0x3a83126f) - предположим приближенная функция здесь будет просто средне арифметическое 0,00055 (0x3a102de0)
(средне арифметическое это наихудшее приблежение на которое способны ряды Фурье или вейвлеты)
первая разница (0x38d1b717 - 0x3a102de0 = 0xFEC18937) следующая (0x3a83126f - 0x3a102de0 = 0x0072E48F)
так?

и разницы я сильной не вижу вычитаются ли целые числа (11-10=1) или их кодировка во float  (0x41300000-0x41200000=0x00100000)
с таким же успехом можно взять целые числа (12563398 - 23547789 = -10984391) и получить тот же хеш.
Ghost2
> Какое преобразование нужно использовать
foxes
> очевидно лучшим вариантом будет комбинирование нескольких
я тебе с самого начал уже предлогал один из методов приближения взять ряд Фурье для сегментов (для вейвлетов данные автоматически сегментируются), и либо его коэффициенты напрямую сжимать, либо квантовать и вычислить остаток, тоже написал как.
https://habrahabr.ru/post/168517/

+ коэффициенты Добеши 9/7

http://www.gamedev.ru/code/forum/?id=194803&page=2#m23

Да есть проблема чем меньше приближение тем больше разница, случайные числа не сжимаются ни чем - ваш кеп.

Ghost2
> Ты сам то это делал хоть раз?
здравствуй троль.

#49
1:59, 29 ноя. 2016

foxes

> наглядно можешь представить ряд чисел и приближенную функцию чтобы это продемонстрировать
Ты вот упорно не хочешь написать алгоритм. Я тебе помогу:
1. Есть f(i), заданная в формате float и размером N:

  [49546; 4233; 65580; 5299; 47700; 35025; 14395; 62648; 141; 59568; 19698; 28972; 52822; 2530; 65231 7598; 44107; 38887; 11371; 63948; 972] / 65536

2. Мы находим, скажем, DCT от f - F(i):

  2.265126; 0.092002; -0.050218; 0.094417; -0.052230; 0.099669; -0.055971; 0.108595; -0.062151; 0.123157; -0.072280; 0.147679; -0.090120; 0.194074; -0.127898; 0.312192; -0.264139; 1.456292; 0.514641; -0.271978; 0.049178
 
3. Дальше продолжай...

> предположим приближенная функция здесь будет просто средне арифметическое 0,00055 (0x3a102de0)
Omg, какое среднее арифметическое? 0.0001 и 0.001 это уже разница между приближением и исходными данными в двух соседних точках.

> здравствуй троль.
Это значит "да, делал" или "нет, я тут фантазирую"?

> https://habrahabr.ru/post/168517/
Не нужно мне залечивать про вейвлеты, добешей и прочее. Я первый диплом дцать лет назад писал по сжатию радиолокационной картинки вейвлетами, так что немного в курсе. Так вот все что ты говоришь безумно далеко от lossless сжатия чисел с плавающей точкой.

#50
11:06, 29 ноя. 2016

Наличие таких как фоксес хорошо объясняет почему на интервью надо обязательно просить всех, даже типа крутых чуваков, кодить на бумажке/ноутбуке и почему нельзя идти в контору, если на интервью тебя не попросили писать код.

#51
11:13, 29 ноя. 2016

foxes
> что думаю его одного бы хватило чтобы LZW не справился

У меня вопрос - ты знаешь как работает LZW ?

#52
20:44, 29 ноя. 2016

Ghost2
Могу я прикинуть.
Не уверен, что я правильно распарсил foxes. Как мне видится:
>2. Мы находим, скажем, DCT от f - F(i):
Что такое у тебя F(i)? Аппроксимация исходной функции? Допустим. Можно вообще тупо DCT(f(i)).

Правка: а, тю, или "-" - это тире, а не минус и F и есть DCT(f)? Тогда вообще понятно.

>3. Дальше продолжай...
3. Получили коэффициенты. Квантизуем результаты. Каким-нибудь методом. Начиная от int(1024*dct(i)), можно взя что-то более продвинутое.
4. Жмём получившиеся целые числа, чем там принято DCT жать. Можно Хаффманом, как в JPEG. Можно диапазонами.
5. У нас теперь есть lossy приближение, и детерминированный алгоритм  восстановления по нему аппроксимированной функции: g(i)=F(i)+IDCT(unpack(compressed_quantized_dct_coefficients))(i).
Правка: ну в смысле g(i)=IDCT(unpack(compressed_quantized_dct_coefficients))(i).

6. Берём разности битовых представлений f и g. Получаем кучу целых чисел, типично небольших по величине.
7. Жмём, чем-то. Например DEFLATE или диапазоны.
Соответственно compressed_quantized_dct_coefficients и compressed_deltas совместно дают сжатое представление функции.

Я в #40 брал тупой квадратичный линейный, блин, предсказатель, а не трансформацию вроде DCT.

#53
21:27, 29 ноя. 2016

FordPerfect

> Что такое у тебя F(i)
DCT(f(i))

> g(i)=F(i)+IDCT(unpack(compressed_quantized_dct_coefficients)).
F(i) тут как появилось?

> 6. Берём разности битовых представлений f и g. Получаем кучу целых чисел, типично небольших по величине.
Неа. Неизвестно, каких по величине. Конкретно для тех чисел получится такое:

-3106; 1048; -1211; -16878; 14856; 2210; 37242; -210; 1633719 (а вот тут скачек из-за экспоненты); 3331; 5506; 8482; 2769; -113530; 3032; 43020; -241; 5197; -6504; 890; -347136

Итого: нам надо сжать 21 коэффициент DCT и 21 разницу, которая будет неизвестно какая. И это мы еще ничего не выкидывали из DCT, как хочет foxes (там ведь пары коэффициентов достаточно, ага).
Если повезет, на втором шаге уменьшится разрядность, но у разности, очевидно, будет шумовой характер.

#54
22:37, 29 ноя. 2016

Ghost2
>F(i) тут как появилось?
Я ж говорю - неправильно тебя понял сначала.
Там ниже строчка:
>g(i)=IDCT(unpack(compressed_quantized_dct_coefficients))(i).

>-3106; 1048; -1211; -16878; 14856; 2210; 37242; -210; 1633719 (а вот тут скачек из-за экспоненты); 3331; 5506; 8482; 2769; -113530; 3032; 43020; -241; 5197; -6504; 890; -347136
Не совсем очевидно, почему из-за экспоненты скачок (ведь битовые представления идут подряд, как и сами числа с плавающей точкой), но ок, перепроверять твои выкладки влом.
Если числа такие, то суммарно это (кодируя диапазоны [-2^{n-1}; 2^{n-1}-1]):
13+11+12+16+15+13+17+9+22+13+14+15+13+18+13+17+9+14+14+11+20=299 бит, вместо исходных 21*32=672. Вполне себе неплохая экономия. Ну плюс ещё сколько-то бит на закодировать сам диапазон.
Ещё около 300 бит остаётся на кодирование квантизованых коэффициентов DCT. Вроде можно жить.
Ну и в моём кодере, как ты мог видеть - вполне себе неплохо сжимает (втрое), правда довольно хорошую функцию. Он впрочем, кодирует без DCT.

#55
22:52, 29 ноя. 2016

FordPerfect

> Я ж говорю - неправильно тебя понял сначала.
Я долго пост рожал )

> Не совсем очевидно, почему из-за экспоненты скачок
Потому что приближенное значение легко может иметь другую экспоненту.

#56
0:05, 30 ноя. 2016

В общем, я хз откуда ты получил такие коэффициенты, я взял DCT-II, и замерил сжатие:
http://rextester.com/NHF21707

Ну у тебя данные изначально 16-битные.

И ещё ~50..70 бит на кодировку вида самих диапазонов.

#57
12:45, 30 ноя. 2016

FordPerfect

> Ну у тебя данные изначально 16-битные.
Так в том и дело, что просто скоррелировав нолики из мантисс можно больше поиметь, чем со всего этого траха.

#58
21:19, 30 ноя. 2016

Репрезентативность сомнительна.
Для энтропийных - удобно. Но если младший байт не 0 - энтропийным влияет, а здесь сожмёт вроде так же.

А так да - результаты не ахти.
Предлагал foxes не DCT, а вейвлеты.

#59
22:58, 30 ноя. 2016

Ghost2
> Я первый диплом дцать лет назад писал по сжатию радиолокационной картинки
> вейвлетами, так что немного в курсе.
Ghost2
> Что такое фильтр квантования?
innuendo
> У меня вопрос - ты знаешь как работает LZW ?
Вкратце, по мере чтения данных формируется словарь последовательностей, которые кодируются минимально возможным количеством бит.
Думаешь сожмет 1 2 3 4 5 6 7 8..? явно нет.
читай внимательней:
foxes
> если это не шаг кратный ПИ
для примера в функцию примера FordPerfect можешь записать просто sin(x) - даст не меньше 90% сжатия.
у меня получилось так
  uncompressed:    256000 (100.0%)
  compressed:      265730 (103.8%)
  block-compressed: 269780 (105.4%)

Ghost2
> 3. Дальше продолжай...
Ghost2
> Omg, какое среднее арифметическое?
2.265126;
Первый коэффициент DCT условно средне арифметическое - постоянная составляющая.
только вот значение коэффициента 2.265126 для чисел меньше единицы очень странное.
FordPerfect
> 3. Получили коэффициенты. Квантизуем результаты.
было бы неплохо здесь запомнить диапазон для исходного отрезка и представить усеченные коэффициенты целыми числами, или усечь сами мантисы, но такие числа будет хранить бессмысленно потому что их матисы попадают в диапазон точности с фиксированной точкой.
Некоторые коэффициенты придеться обработать по маске чтобы биты мантисы меньше 0.00000000023283064365386962890625 (0x2f800000) обнулялись, это изменение не должно давать искажений точности, поскольку будет попадать за предел точности float. Любое число коэффициента меньше 0.00000000023283064365386962890625 нужно обнулять.

FordPerfect
> int(1024*dct(i))
Это многое решает но только для конкретного примера здесь будет int(65536*dct(i)).

Только потом делать квантизацию - если не делать то будет lossless сжатие. Но так как разброс на отрезке может быть большим то при обратном DCT это уже будет приближенная функция. Поэтому тут также нужен обратный процесс и сравнение.
В случае не соответствия:
FordPerfect
> 6. Берём разности битовых представлений f и g. Получаем кучу целых чисел,
> типично небольших по величине.
f и g - как исходные данные и восстановленные из полученных коэффициентов.
В этом случае можно отбросить часть высоко частотных коэффициентов. Или сделать алгоритм заведомо через приближение, то есть в любом случае отбрасывать коэффициенты и квантизировать.

Ghost2
> И это мы еще ничего не выкидывали из DCT, как хочет foxes (там ведь пары
> коэффициентов достаточно, ага).
суть квантизации в том, помимо того что она нормализует коэффициенты и убирает избыточность, что при высоких значениях делителей (a(16бит)/65536=0) будет ноль - что собственно и будет полным выкидыванием значения. Обычно это половина коэффициентов.

FordPerfect
> Предлагал foxes не DCT, а вейвлеты.
да этот вариант даст больше точности за счет малых отрезков в самом вейвлете, вероятность появления отрезков с большим разбросом будет меньше.
FordPerfect
> 7. Жмём, чем-то.
так я себе это представлял.
Еще раз уточню если диапазоны не будут выходить за рамки 32-бит то разницы между сжатием только коэффициентов или части коэффициентов и хранения дополнительных бит не должно быть.

Ghost2
> Потому что приближенное значение легко может иметь другую экспоненту.
Это такая же проблема и для целых чисел, в случае большой потери точности в коэффициентах.
foxes
> 12563398 - 23547789 = -10984391
но не для всего ряда, а для отдельных значений.
Ghost2
> Неизвестно, каких по величине.
как так то?

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.