avi2gif чем?

mplayer разве не умеет?

в кадре есть только изменившиеся части

а гиф это умеет?

GIMP

Да, гиф так и устроен.

в кадре есть только изменившиеся части
для каждого (или группы) кадра своя локальная палитра

Кстати, не думаю, что возможно, чтобы одновременно было и то, и другое.

Уточнение: Возможно и то и другое. mplayer и Ко не специализированное ПО. Ключевое слово - оптимизация. Вообще, самое главное цвета, а именно сохранение их многообразия. У тех программ, что я находил, есть проблема: палитра создается для всех кадров, т.е. общая. Проблема это потому, что, как, я думаю, всем известно, палитра gif ограничена 256-ю цветами. Но для каждого кадра могут быть свои 256 цветов. Если для каждого кадра создавать свою палитру, то анимация получится более красочной, т.е. она может содержать больше 256 цветов.

т.е. она может содержать больше 256 цветов.

А я всегда думал, что там 1 бит на цвет отводится, потому цвета только те что есть, никаких других не впихнуть

Да, но у каждого чанка(кадра) своя палитра, т.е в разные кадры можно «впихивать» разные 256 цветов. Пример

У меня верхняя гифка - чёрный квадрат (: