О плавающей точке и точности вычислений...

lexa - 05/Дек/2010 22:46

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

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

Илья Борг не поленился и запихал ту же "дикобразовую мишень" в реализацию AHD, которая полностью повторяет AHD-алгоритм dcraw/LibRaw, но использует для вычислений плавающую точку. Результаты для неразмытой картинки отличаются кардинально (картинки кликабельны, открываются превьюшки в 2/3 оригинала):

Для более фотографически реальной размытой мишени разница не столь огромна, ибо результаты AHD в целых числах не столь безобразны, однако тоже весьма велики. Второй набор картинок и полноразмерная первая пара рассматривайте в заметке Ильи:

Поспешай медленно

От себя замечу, что AHD в плавучке работает на уровне "лучших образцов" (LMMSE, AMaZE), а для неразмытой мишени - и получше. Оные лучшие образцы тоже реализованы в плавучке, не в этом ли секрет их хорошести?

Comments

J0hn - 06/Дек/2010 00:54

А там используется какое-либо суммирование(больше двух чисел)? В смысле floating values складываются?
Если да, то можно ещё складывать всё время два самых наименьших по модулю числа, либо как компромисс http://en.wikipedia.org/wiki/Kahan_summation_algorithm , чтобы немного точность увеличить.

lexa - 06/Дек/2010 08:33

Не, тут дело не в переполнении, а в вычитании.

J0hn - 06/Дек/2010 09:21

я не про переполнение.. я про то, что если в "AHD-интерполяция, плавающая точка" есть места где суммируются, либо вычитаются больше двух чисел, то можно получить ещё немного точности просто правильно выбрав порядок операций, либо использую трюки типа Kahan sum.
Операции сложения и вычитания в плавающей точке не ассоциативны - sad but true

lexa - 06/Дек/2010 10:40

Да, не коммутативны. Но парить себе этим голову бессмысленно, потому что на выходе опять округлят до целого (а на выводе на монитор-принтер и вовсе до 8 бит).

J0hn - 06/Дек/2010 11:03

Я не в теме какие именно там вычисления, но при длинной цепочке сложений/вычитаний и при большом разбросе значений погрешность может отразится и на целых.

lexa - 06/Дек/2010 11:11

Если мне в новогоднюю ночь реально будет нечем заняться, я посчитаю того же самого в 32 и 128-битах /без переупорядочений/ и посмотрю на (видимую) разницу. Но ее не ожидаю.

_slw (not verified) - 06/Дек/2010 01:50

а что, тупо пару бит в целых числах не добавить?

sanmai (not verified) - 06/Дек/2010 06:02

Можно многое, только будет ли от этого достаточно толка, чтобы оправдать затраты времени на очередное "изобретение колеса"?

J0hn - 06/Дек/2010 07:05

Вы понимаете разницу между fixed point и floating point?

lexa - 06/Дек/2010 08:05

Парой - не обойдется, посмотри на разницу.

Но зачем, если правильно реализованные вычисления в плавучке, как минимум, не медленнее (хотя и муторнее в реализации)

_slw (not verified) - 06/Дек/2010 11:57

Парой - не обойдется, посмотри на разницу.

ну у нас как бе не 16 их в запасе?
разница не показатель, 1 бит ошибок накопили и потом усилили.

Но зачем, если правильно реализованные вычисления в плавучке, как минимум, не медленнее (хотя и муторнее в реализации)
ой ли? что, плавучка стала быстра как целые? и давно?
а эти SSE2 тоже в плавучке? и тоже быстрые?

lexa - 06/Дек/2010 12:05

Але, пиковая производительность SSE на i7 - 8 операций на такт в плавучке.
И это гораздо быстрее, чем целые на CPU.

wrest (not verified) - 06/Дек/2010 11:37

имеется в виду, при том же количестве бит?

lexa - 06/Дек/2010 11:53

Входных/выходных? Да, и там и сям по 16(48), а картинки тут и в статье - вообще 8-bit indexed.

wrest (not verified) - 06/Дек/2010 11:58

Сорри, я имел в виду - какая длина в битах чисел с плавающей точкой? Тоже 16?

lexa - 06/Дек/2010 12:07

А операций с half на CPU вроде не бывает? Я к тому, что конечно 32.

wrest (not verified) - 06/Дек/2010 12:13

Ну а тогда о чём речь? О том что вычисления с числами бОльшей битовой длины - точнее, или именно о том, что логарифмический подход (мантисса отдельно, порядок - отдельно) точнее (и менее подвержен артефактам)?

Скажем, взять 16-битный вход, преобразовать в 32-битный, сдвинуть на 10 бит, дебайрить целочисленно, сдвинуть обратно на 10 бит, преобразовать обратно в 16-бит - будет же лучше чем чем всё считать в целочисленных входных 16 битах?

lexa - 06/Дек/2010 12:18

Речь о том, что "неоднократно приходилось читать и слышать", что точность float избыточна и 16-битных целых достаточно "разница если и будет, то микроскопическая". См. начальный пост.
А она - макроскопическая.

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

wrest (not verified) - 06/Дек/2010 12:37

>Речь о том, что "неоднократно приходилось читать и слышать", что точность float избыточна и 16-битных целых достаточно "разница если и будет, то микроскопическая". См. начальный пост.
А она - макроскопическая.

Напоминает интернет-флейм a la Margulis на тему 8 и 16 бит. Тогда Маргулис предложил что-то типа пари - ему дают 8-битную картинку (но не генерированную а реальную фотку), последовательность осмысленных действий по коррекции в шопе в 16-битном режиме с возвратом на 8 бит, он делает тоже самое без перевода в 16 бит и если разница будет заметной - Маргулис проиграл.

На него там потом катили бочку что он меняет условия на ходу и т.п...

Так вот, эти целочисленные вычисления с 16-ю битами и макроскопической разницей проявились на генерированной картинке что не удивительно, не так ли?

Потом, когда говорят о 16 битах - на самом деле говорят о них, или например о 12 битах? Ну например, после ацп идут 12 бит - их дополняют старшими нулями или например сдвигают на пару бит, делая и старшие и младшие нули?

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

А вопрос ещё есть другой все-таки. А вот если сохранить ту же битовую длину (16 бит) но перевести в логарифмический вид на время вычислений - тоже станет лучше?

Понятно же что дебайеризация - это умножение, а умножение логарифмов -- это сложение. Если какие-то коэффициенты при умножении сильно меньше единицы (ну скажем на порядок), да плюс ещё будут умножаемые величины небольшими, то ошибки (относительные) будут большими.

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

Может те кто утверждают, не видели логарифмической линейки? Иногда наглядность доставляет.

lexa - 06/Дек/2010 12:49

На всерьез размытой мишени (более размытой, чем камера размывает) разница тоже более чем есть.

Что же касается замены умножения сложением, то я ниасилил. Почему "дебайеризация - это умножение"? Ну и выигрыш от замены умножения сложением мне непонятен.

wrest (not verified) - 06/Дек/2010 13:09

>Что же касается замены умножения сложением, то я ниасилил.
При умножении логарифмы же складываются.
Вся "бяка" и макроскопическая разница integer vs float - она же появляется при умножениях, а не при сложениях.

>Почему "дебайеризация - это умножение"?
А что же ещё? (сорри конечно что задаю такой вопрос автору libraw). Есть входные raw-числа, есть матрица преобразования в rgb. Одно на второе умножается.

>Ну и выигрыш от замены умножения сложением мне непонятен.
Выигрыш по точности. У float, типа, все биты что-нибудь значат. А у integer впереди или сзади может быть куча ненужных нулей.

lexa - 06/Дек/2010 13:14

Нет, бяка проявляется в первую очередь при вычитаниях и делениях. При этом младшие нули вовсе не лишние.

а "умножение на матрицу" - это не дебайеризация, это преобразование цвета.

Дебайеризация может быть, например, bilinear/bicubic интерполяция.

wrest (not verified) - 06/Дек/2010 13:31

>Нет, бяка проявляется в первую очередь при вычитаниях и делениях.

Деление и умножение - одно и то же, в общем. Как и сложение с вычитанием.

>Дебайеризация может быть, например, bilinear/bicubic интерполяция.
Интерполяция - это тоже по сути умножение (умножения вектора на матрицу, или решение системы линейных уравнений и умножение на полученный коэффициенты, которое в основном состоит из умножений).

В итоге : как тебе кажется,
1. Если вычислять (дебайеризовать) в числах с плавающей точкой, но длинной 16 бит, это даст заметную разницу с целочисленными 16-бит вычислениями?
2. Если вычислять в целых числах, но с 32 битами (и предварительным сдвигом на несколько бит - на 10 например) с обратной конвертацией (и обратным сдвигом на те же 10 бит) по завершении вычислений в 16 бит - это даст заметную разницу?

lexa - 06/Дек/2010 16:07

Мне никак не кажется, потому что оба упражнения глупые
half-точности нету на CPU, без native-операций считаться будет бесконечное примерно время.
32-bit int на CPU есть, но никакой экономии по памяти и скорости относительно float не дает, а float имеет сильно большее количество значащих цифр в тенях.

J0hn - 06/Дек/2010 13:31

При умножении логарифмы же складываются

Ну да, как потом вытаскивать от туда? Экспонента? Не дороговато-ли будет? И какой удар по точности получится?
И вообще, сколько времени занимает перевод из одного цветового пространство в другое? "premature optimization is the root of all evil"

lexa - 06/Дек/2010 16:04

Простая реализация на C для colorspace conversion - довольно долгая, порядка 0.3 сек для 8-мпикс.

Но это где-то пятый по счету хотспот, хотя и очень локальный. Дойдут руки и до него

Алексей (not verified) - 06/Дек/2010 17:43

Алексей! А в последней бетке либрава какая точность используется? Целочисленная или плавающая. Будут ли в релиз версии новые алгоритмы?

lexa - 06/Дек/2010 17:48

В 0.12, которая пока бета, новых (для libraw) алгоритмов аж семь штук. В релизе 0.12 они тоже будут.

Но. Постпроцессинг для LibRaw - не приоритет. Мы с удовольствием принимаем патчи, но сами разве только баги будем фиксить (и фиксим), самостоятельно развивать это место планов нет.

michael_mach (not verified) - 07/Дек/2010 09:07

А какие raw-конверторы используют вычисления с floating point?

lexa - 07/Дек/2010 09:27

RPP, Raw Magick

RawTherapee - по меньшей мере частично (всерьез ейные исходники не читал)

Alexandr (not verified) - 10/Дек/2010 23:59

Плавающая точка не так интересна, как тот кот - который одновременно и мертвый, и живой ;) Догадались, о чем речь?

lexa - 13/Дек/2010 14:50

Нет, куда мне. Поясните.

and_lv (not verified) - 13/Дек/2010 14:23

Не поленился, тупо переделал dcraw ahd_interpolate на float. Все таки похоже про сметану речь. :-) Долго пытался понять откуда взялась такая разница в статье. Искал ошибки у себя.
А показанная разница - результат преобразования в output color space. Попробуйте с ключем -o 0. Результат меня удивил.

lexa - 13/Дек/2010 14:49

Вообще, в RPP, где тоже муар маленький, для работы с цветом используется ColorSync, который целый (и проблемный).
(пример с плавающей AHD - не из RPP).

Но с -o 0 переделаю обязательно, спасибо за идею.

and_lv (not verified) - 13/Дек/2010 15:18

Там еще до кучи #define TS 256
добавит на краях у ahd . Их как то с перекрытием делать надо бы.

Ну если руки дойдут - загляну на convert_to_rgb и apply_profile
А может таки не зря никон хочет gamma corrected профайлы?
И откуда пример с плавающей AHD если не секрет?

lexa - 13/Дек/2010 15:37

Плавающая AHD - это некий экспериментальный код, который Илья сделал давно-давно, как я понимаю.

and_lv (not verified) - 13/Дек/2010 18:36

Да вот еще не поленился-вспомнил-повторил
Результат применения примерно того же фильтра, который у lmmse у нутре прикручен к остальным демозаикам ну и с ключом -o 0 (амазе и дцб по состоянию на июль. после этого амазе улучшили, дцб ухудшили):

http://www.faonet.com/tmp/tutubalin/porcupine_ahd_o0_mo5_2p.tiff
http://www.faonet.com/tmp/tutubalin/porcupine_amz_o0_mo5_2p.tiff
http://www.faonet.com/tmp/tutubalin/porcupine_dcb_o0_mo5_2p.tiff
http://www.faonet.com/tmp/tutubalin/porcupine_lmmse_o0_mo5_2p.tiff

и lmmse оригинальный (ему не помогает, так как он уже у него приделан).
http://www.faonet.com/tmp/tutubalin/porcupine_lmmse_o0.tiff

lexa - 13/Дек/2010 19:28

Тшорт, до чего же неудобно с TIFF и браузером. Это сохранить каждый....
PNG в этом смысле рулит.

Касаемо фильтров: CA_correct_RT в master теперь для всех интерполяций. И позволяет руками задать коррекции по осям.

and_lv (not verified) - 13/Дек/2010 19:40

Обещаю, в следующий раз в png сохранять (если будет чего). А wget curl не спасет отца русской демократии? Это ж все переделывать.
Про фильтры: Я не про CA_correct_RT я про low pass filter on differential colors
Тут то у нас откуда ха появятся?

lexa - 13/Дек/2010 19:52

Ну откуда у меня в виндах wget и прочий curl.

Переделывать старое не надо, конечно. Просто потом tiff2png (и вполне можно pngquant потом, богатство красок немножко портится, но не очень сильно)

А про CA_correct - это просто к слову было.

and_lv (not verified) - 13/Дек/2010 20:15

Оттуда же откуда и в bsd и в linux. Вполне себе работают. Проверено.
Вот результат конвертации imagemagick convert:

http://www.faonet.com/tmp/tutubalin/porcupine_ahd_o0_mo5_2p.png
http://www.faonet.com/tmp/tutubalin/porcupine_amz_o0_mo5_2p.png
http://www.faonet.com/tmp/tutubalin/porcupine_dcb_o0_mo5_2p.png
http://www.faonet.com/tmp/tutubalin/porcupine_lmmse_o0_mo5_2p.png

и lmmse оригинальный (ему не помогает, так как он уже у него приделан).
http://www.faonet.com/tmp/tutubalin/porcupine_lmmse_o0.png

lexa - 13/Дек/2010 20:23

Так гораздо удобнее, спасибо!

dimas - 13/Дек/2010 20:25

http://gnuwin32.sourceforge.net/packages/wget.htm

скачивается zip, из него берется один exe-ник, всё :)

lexa - 13/Дек/2010 20:34

Не, ну а толку то с него?

Firefox по клику тоже все скачает. И по еще одному клику - посмотрю. Но прямо в браузере это несколько удобнее, не находите?

lexa - 14/Дек/2010 18:25

Ага, попробовал, тоже удивился и разобрался.

Фишка в том, какой профиль (camera matrix) у этого DNG. А там - просто единичная (диагональная) матрица. Отчего при конверсии ее в sRGB получается чудо клиппинга в минус (выпадение каналов).

and_lv (not verified) - 15/Дек/2010 11:45

Хотел было написать, что не совсем удачная мишень получается для демонстрации разницы между демозаиками, но потом решил немного переждать. А потом запустил dcraw с такими вот ключами: -v -w -W -T -k 0 -o 0 -D -b 1.9. Ну основное тут -D, а -b 1.9 - чтобы уровень фона был такой же. Все остальное лень убирать было. Тоже интересно. Я надеюсь правильно все понимаю?
Ну и вывод для себя - в данном конкретном случае на примере AHD демозаика, реализации этого алгоритма в целых вполне достаточно, а если вспомнить и применить то чему учили еще в младшей группе детского сада :-), тем более все внутри уже есть (ни кого не хочу обидеть заранее приношу извинения если задел), то результаты становятся близки к идеальным результатам. Да результат амазе дцб и лммсе я тоже показывал.

lexa - 15/Дек/2010 12:08

Я про -D не вполне понял вашу мысль, ну восстановили вы мне исходный TIFF, ну да, я его и так знаю :)

А мишень получилась совершенно отличная, но то что там особенности демозаики усиливаются свойствами absolute colormetric - это просто не сразу осознали.

Если с этим местом (CameraMatrix) поиграться, можно еще вывести на чистую воду конвертеры, которые не берут из DNG цветовых данных. Такие тоже есть.

and_lv (not verified) - 15/Дек/2010 12:42

Вы то знаете. А я?
Но теперь тоже знаю. Это правильно ведь я понял? Есть с чем сравнивать. Объективные данные.

lexa - 15/Дек/2010 12:48

В каком смысле "правильно"?

Вы вынули один компонент (больше в DNG и не было) и положили в grayscale tiff. Провраться особо и негде.

А при подготовке - брался RGB Tiff, из каждого пикселя - нужный компонент. Понятно что в мишени "в три раза меньше данных", чем в исходнике.

and_lv (not verified) - 15/Дек/2010 13:27

В том смысле, что для данной конкретной мишени это получится идеальное восстановление если тупо скопировать имеющийся байеровский сэмпл в недостающие на этом цвете. А grayscale для визуального контроля.

lexa - 15/Дек/2010 13:42

Ну естественно, если исходные компоненты были равны, а на выходе мы "тупо скопировали", то они тоже будут равны. Не вижу предмета для обсуждения.

and_lv (not verified) - 15/Дек/2010 13:45

Да я сам себя проверяю. Я не волшебник, я только учусь. Спасибо.