Отправлено ReAl 17 января 2005 г. 15:46 В ответ на: а как в простонародье называют этот алгоритм? отправлено Aleksey_N 17 января 2005 г. 13:44

Это толи первый из факосвых алгоритмов, толи вообще их "предтеча".
По сути это результат кодирования расстояний между ошибками предсказания предсказателя нулевого порядка.
Делаем предсказатель "пиксел N+1 имеет тот же цвет, что и пиксел N" (два цвета - белый и чёрный).
Вычисляем ошибку предсказания для него. Поскольку цветов всего два, ошибку делаем как XOR предсказанного и действительного.
Т.е. в ошибке единички будут в момент смены цвета, а на выход мы посылаем расстояния между ошибками.
Для

0,0,0,0,0,1,1,0,0,1,0,1,1,1,1,1,1

ошибка будет

0,0,0,0,0,1,0,1,0,1,1,1,0,0,0,0,0

что и кодируется как

5,2,2,1,1,6

Последнюю 6-рку можно и не передавать, но только если есть другой флаг конца строки.

Дальше факсовые алгоритмы наворачивались по усложнению предсказателя. Кажется, в class III предсказатель двумерный по семи точкам,

ABCDEF
GHX

Для предсказания цвета точки X использовались точки A-H

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

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

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

Если отклонение B от A меньше, чем отклонение С от A, то предсказание ведём по паре X и C, а если будет меньше отклонение C от A, то предсказание - по паре X и B.
В переводе не бинарную картинку считаем, что если A==B, то X==C, иначе X==B.

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

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

Кстати, я не ошибся на слове "монохромное"?
Вообще-то "монохромное" изображение - это градации одного цвета, но чаще под монохромным понимают бинарное и я так и отвечаю :-)