Аргументация ad hominem

[pargentum]

Публикуется по настоятельной просьбе самого hominem.

Вкратце - Куздра широко растопыривал пальцы, что умеет решать сложные компьютерные задачи.  Настолько сложные, что при капитализме его навыки не востребованы.  Я ему дал нетривиальную компьютерную задачу.  Он взялся ее решать, не решил (впрочем, понятно, что я и не ждал решения в виде работающего кода, речь была лишь о подходе к решению) и начал кричать, что я ему задачу неправильно объяснил и вообще так нечестно, а на самом деле он умный и может написать неоптимизирующий компилятор, совместимый с турбо паскалем, и даже писал его два раза - один раз для PDP-11, второй - для x86 в 32разрядном режиме.

http://www.livejournal.com/users/pargentum/579778.html?thread=2515906#t2515906

Саму задачку, наверное, тоже интересно было бы обсудить.

Comments

[oblomov-jerusal.livejournal.com]

А разве не лучше сжимать не картинки, а запросы к графическому интерфейсу? (В этом и был подвох для kouzdra?). Да, и не ad homini, а ad hominem.

[kouzdra.livejournal.com]

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

В ситации описанной автором поста, данные вообще не графические по своей сути. Это набор приямоугольных областей, поверх которых текст (повторяющиеся небольшие прямоугольные объекты) и иконки (опять же - небольшие повторяющиеся объекты).

Соответственно - ничего лучше все равно не сделать. Если так уж надо "с потерями" - надо как и в browser'ах терять наименее значимые компоненты (а скорее - просто передавать в правильном порядке) - приоритет (по убыванию важности) - layout, текст, настоящие bitmap'ы.

[pargentum.livejournal.com]

>Подвох был в том, что в постановке речь шла однозначно про картинки. Я в общем привык, что если уж, по крайней мере программист дает довольно точную формулировку "что надо", то значит - кроме картинок ничего нет.

Ну вот я и говорю - вы сами себя [подсознательно] позиционируете как кодера. Поставили задачу - значит она отсюда и до обеда и не разговаривать. Мне дали список - я закодировал. А я нарочно дал задачу, которая допускает решения в виде переформулировок, потому что вы ведь мне перед этим рассказывали, что слишком умны, чтобы работать кодером.

[kouzdra.livejournal.com]

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

А теперь ответьте мне, если можно, на несколько вопросов
1) Это ваш собственный проект?
2) Вы имеете свое представление о том, как ее решать?
И какой объем при Вашем подходе вы собираетесь получить допустим,
для такйо картинки ну скажем обычный Linux-ный screenshot - 8
бит/1600x1200 - FF с LJ максимизирован, сбоку гномовский toolbar.

Вы на этот вопрос так и не ответили (я задавал его уже три раза), а он важен.

[pargentum.livejournal.com]

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

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

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

А задумка была в том, что если у нас будет гарантированный уровень упаковки, мы можем пропустить это дело по резервированному реалтаймовому каналу MPLS.

[a-bronx.livejournal.com]

> по сети идет 4-6 бит на пиксел с палитрой, а юзер вполне доволен

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

В общем, идея та же, что и в mpeg: первым делом передавать яркостную составляющую, затем цветовую. Только яркостную получать не ресурсоёмким косинусным преобразованием, а "в лоб": брать старшие биты самых информативных цветов данного региона (точнее, его диффа), и до поры до времени "перекрашивать" их в монохром.

Что до вашего спора: я бы тоже подумал, что "сжимать запросы" - это не то решение, которого ждут. Ибо оно приходит в голову первым, и раз постановщику это не помогло решить задачу (а оно не помогло - ибо тогда и задача бы не стояла), значит суть именно в том, чтобы сжимать поток готовых картинок.

[a-bronx.livejournal.com]

Тьфу, пишу одно, думаю о другом... Разумеется, косинусное преобразование к яркостной составляющей никакого отношения не имеет. Сорри за прогон.

[pargentum.livejournal.com]

Интересно было бы такое сделать в виде прототипа, насколько это будет визуально терпимо.

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

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

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

[a-bronx.livejournal.com]

Интересно было бы такое сделать в виде прототипа, насколько это будет визуально терпимо.

Нужно найти кодера... :)

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

если она превосходит порог, делать интерлейс

В принципе, оба этих подхода совместимы - в особо тяжёлых случаях можно делать интерлейс как по строкам, так и по битовым плоскостям. Думаю, со строками должно неплохо смотреться при вертикальном скроллинге. А вот при горизонтальных движениях может появиться "пила" - как на изображении с тв-тюнеров.

[akovalenko.livejournal.com]

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

Паковать можно и так, чтобы интерлейсить уже упакованное было легко. Вообще, с помощью нетривиальных траекторий по пикселам обновляемого региона можно достичь много интересного.

Что же касается запросов к windowing system -- они были бы полезны в качестве хинта (где скоро будет перерисовка? а где, скорее всего, в ближайшее время не будет?). Проблема в том, что перехватывать поток запросов, не подменяя всю графическую подсистему, не слишком тривиально в X11 (прокси+разбиралка запросов к Xlib) и неочевидно-что-вообще-возможно в win32. Однако много полезного можно извлечь и из WM_PAINT/ XExposeEvent, WM_MOVE/ WM_SIZE/ XConfigureEvent, которые можно перехватить без проблем.

Много интересного можно сказать об очереди неотправленных запросов. 1) сжатие должно быть по возможности ближе к отправке, 2) более поздние апдейты не только должны удалять перекрываемые ими более ранние из очереди, но и "обрезать" неполностью перекрываемые (для чего и п.1). Идеи о том, что никакой существенной очереди запросов не будет, а всё сплошной hard realtime, мы сразу же отвергаем как wishful thinking.

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

Окончательное сжатие перед отправкой -- тут вариантов много; в силу постановки задачи отпадают (скорее всего) все картиночно-ориентированные алгоритмы, которые занимаются анализом/смешиванием цветов разных пикселов (справедливо помянутое выделение яркостной компоненты и прочие подобные вещи лучше делать в фазе снятия картинки); сжатие со словарём должно учитывать тот факт, что кусок апдейта чаще будет совпадать не с другим куском того же апдейта, а с куском одного из более ранних апдейтов (соответственно, словарь должен быть как минимум общим для сессии, а лучше и между сессиями); любопытно также, что ICON и BITMAP ресурсы выполняющихся приложений могут поспособствовать первоначальному наполнению словаря. Всё это, естественно, в предположении, что у нас в качестве транспорта TCP (как минимум, для не-внутрикорпоративного приложения это самый резонный выбор).

В целом же, ниши, в которую можно воткнуться, совершенствуя этот аспект remote desktop, я не вижу (то есть я не взялся бы за такую разработку с идеей "продавать потом самому"). Вот проект вроде того, о котором пишет Joel Spolsky (не помню как оно называется, с упором на лёгкость установки, ненужность настройки и всевозможную дружественность) показался бы мне существенно более потенциально-прибыльным, — хоть там и нет вообще ничего алгоритмически-нетривиального.

[pargentum.livejournal.com]

Перехватить поток рисовальных запросов к X11 тривиально. Собственно, X11 - это и есть поток рисовальных запросов, передаваемых по последовательному каналу - TCP или Unix Domain сокету. То есть воткнуться в качестве прокси в этот сокет и ваши волосы - ... Единственная трудность - что когда у вас реальный десктоп, там идет много таких потоков.

[akovalenko.livejournal.com]

Это из серии "легко сказать". Точнее, запросы поймать легко, а дальше начинается самое интересное.

Xserver — это существо с богатым внутренним миром. Есть такая штука &mdash xonx, которая изображает из себя Xserver и пытается таким образом обеспечить возможность динамической смены настоящего Xserverа. Она довольно сложная внутри даже при том, что не пытается поддерживать вообще никаких нетривиальных расширений. И, самое главное, она так влияет на локальную работу приложения, что на десктоп пользователя ничего подобного водружать нельзя. Я могу обойтись и без backing-store и много без чего ещё ради возможности удалённой работы, но только временно и в каком-либо конкретном приложении, а не на всём десктопе и постоянно.

Кстати, мы можем обнаружить, что приложение использует Xshm, и весь наш перехват запросов снова превращается в анализ картинки (если Вы уверены, что "нормальный офисно-админский гуй" не будет пользоваться Xshm - не будьте так уверены). Я подробности опущу, так как X11 явно не Ваша среда; никто, с этим работавший, не упомянул бы в качестве единственной трудности нечто, которое вообще трудностью не является (у Xserver'а практически нет per-connection state, если не считать очень простого механизма прибивания ресурсов в случае гибели создателя и (неинтересного нам) распределения событий — детские игры по сравнению со всем остальным в этом подходе. Асинхронность же его операций точно так же добавляет прелести и в рамках одного соединения).

В общем, запросы X11 в Вашей задачке реально использовать только в качестве хинта и никак иначе. Всякого, кто пожелает по ним что-нибудь рисовать, ожидает множество граблей, из которых здесь упомянуты только наиболее очевидные. Ловить же изменения картинки, кстати, скоро станет гораздо проще (спасибо X.org за XDamage extension, которого пока нигде нет, но это временно).

[kouzdra.livejournal.com]

Вообще-то 4-6 бит с палитрой это глупость - как минимум надо выделять большие участки с четко выраженным фоном/бэкграундом (если суметь их сделать влжоженными) то, у меня на экране 1600x1200 их сейчас около 2 десятков и в их пределах занимться одноцветной картинкой. Потери цветов не будет вообще, а на точку сразу же получает не 4-6, а 1 бит.
Во вторых - есть довольно много алгоритмов сжатия b/w текстовых изображений: Я потратил 15 минут на выполнение совета, который давал вам - посмотреть в INet. Есть стандарт ISO (lossless/progressive) - JBIG1/JBIG2. В поставку Fedora3 входят тулы и библиотеки.

Я сейчас произвел опыт - взял скриншот. Вот примерно этот самый (LJ, только запись другая), 1600x1200, сконвертировал в монохромный (практически без потери качества, только иконки пострадали, но все равно - вполне узнаваемы) сжал - 10279 байт (из 1.9MB файла). Видимо это типичный случай. Ну добаваляем 100-200 байт на "раскаску фона/бэкграунда". Остальное - как получится. Время сжатия на этом файле - 0.6".

Если вам надо 1280x1024 - наверное все гарантировано впишется в 7-8 KB. Формат, как я сказал - progressive. Это был JBIG1. Я сомневаюсь, что вы "на коленке" изобретете что-то хотя бы сравнимое.

JBIG2 наверное лучше. Еще по ходу дела попалась статья про GRID (двуменрая варианция на тему LZ), она если верить автору дает результат в среднем в полтора раза лучше. Попадались еще ссылки на lossy можификации JBIG. Они тоже должны быть лучше.

Заняло все вместе с опытами 40 минут.

[pargentum.livejournal.com]

Если этот инцидент окажется стимулом для вашего личностного и профессионального роста, я буду только рад.

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

[kouzdra.livejournal.com]

Я Вам русским языком сказал - формат progressive. Что означает, что Вы в любой момент можете прекратить передачу данных - и получите приличное изображение с потерей качества. Что есть его lossy модификации - я Вам тоже сказал. Поскольку это надо Вам, а не мне - можете продолжить поиск сами. Или же продолжать изобретать велосипед с квадратными колесами.

Тема сжатия изъезжена вдоль и поперек и что-то оригинальное Вы, если не являетесь, специалистом в этой узкой области, не выдумаете. Есть еще такая полезная эха - comp.compression. Там есть faq (который Вы похоже не читали) и там есть народ, который можно спросить.

Есть куча статей на эту тему.

PS: Так вот, то, чем Вы сейчас занимаетесь - и есть классическая совковвя "инженерная деятельность" именно в том смысле, который Вы в это вкладываете. Когда "мы сами с усами", а в книжку загляднуть - лень. Оно к СССР никак не привязано и меньше его не стало.

[pargentum.livejournal.com]

Я же говорю - я очень рад, что этот инцидент послужил вам стимулом для профессионального и личностного роста.

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

Кроме того, вы сами меряли - время упаковки измеряется десятыми долями секунды. Это неприемлемо.

[kouzdra.livejournal.com]

Upd: повторил опыт - только выбрал так, чтобы текстом был заполнен весь экран (шрифт у меня мелкий) - получилось 19KB. Случай тяжелый - Объем только текста в окне собственн LJ - около 5KB.

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

[kouzdra.livejournal.com]

Ну - я много чего написал. Но спасибо - я очень люблю Вашу незамутненность сознания.

2All: Собственно к высказываниям автора мне добавить нечего. Разве, что его демаогические приемы собрать в одном месте. Там их есть (я даже не все комментировал) и они для л-ской публики характеры.

Но пока - некогда.

[trurle.livejournal.com]

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

[pargentum.livejournal.com]

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

[kouzdra.livejournal.com]

Гм. По итогам уже этого обсуждения я скорретктирровал мнение - тогда я Вам говорил, что Вы сформулировали не ту задачу, решение которой Вам требовалось. Вот сейчас - да - сейчас я действительно полагаю что Вы "ничего не понимаете в своей задаче".

[nine_k]

Т.е. вам желалось бы, чтобы собеседник сказал: "постановка-то кривая, давайте лучше вызовы рисования перехватывать, и будет куда лучше"?
BTW, насколько я понял, вся штука именно в резких перерисовках (через минуту размышлений это становится ясно), и там всё равно, картинка или вызовы xlib/gdi.

Кстати, нельзя ли использовать тот факт, что трафик от GUI носит "взрывной" характер (90% времени ничего не меняется, зато потом вдруг полная перерисовка)? Выделить "статическую" и "динамическую" компоненты. "Статическая" -- то же окно браузера, которое надо один раз нарисовать, и оно с высокой вероятностью долго не будет меняться, динамическое -- скажем, контрол, в который я тыкаю мышкой, или там часы. Тогда можно сначала грубо нарисовать "статику" (interlace + сжатие), а потом, постоянно перерисовывая "динамику", дорисовать "статику" до полной картинки во время относительного затишья.

[pargentum.livejournal.com]

Ну да, идея именно такая. Вопрос только в том, как это сделать в реалтайме, т.е. не используя ни в какой форме подход "упаковали так, не влезло, перепаковали сяк - ..."

[nine_k]

Да хоть тем же interlace, который заодно жать по RLE.
Можно, кстати, как тут предлагали, брать "нетривиальные траектории". Разбить картинку на квадраты, скажем, 8*8, и перебирать в них точки заранее заданным, но непоследовательным образом. Дальше смотреть -- сколько точек успели выбрать/сжать, пока буфер не кончился, столько передаём, а номер шага запоминаем.

[pargentum.livejournal.com]

>Да хоть тем же interlace, который заодно жать по RLE.

Разумеется это все потом жмется. :)

Насчет сложной траектории - смысл, я так понимаю, в том, чтобы получить более точную оценку сжимаемости картинки? Пока единственная проблема, которую я в этом вижу - что испортим работу RLE, :) придется переходить на более сложные схемы упаковки.