Пиксельный рисунок в отображенной зоне может быть в достаточной степени похож на соответствующий рисунок в блоке, если не считать большую или меньшую яркость. Поэтому алгоритм поиска также ищет наилучшее линейное преобразование уровней яркости пикселов зоны в уровни яркости
(9.9)
(9.10)1 В этой теореме содержится достаточно сложная математика, поскольку Барнсли для измерения похожести двух изображений использует специальное понятие «расстояния» между двумя множествами точек.
Приближение к бесконечности
пикселов блока1. В этом случае двумерные аффинные преобразования неизбежно превращаются в трехмерные:
Рис. 9.35. Нахождение аффинных преобразований в системе PIFS
Здесь точка (х, у) преобразуется в точку (х\ у') обычным способом, а яркость b преобразуется в яркость V с использованием коэффициентов g и h. (Значение коэффициента g следует выбрать меньше единицы - для того, чтобы данное преобразование было сжимающим.) Тогда закодированное изображение будет состоять из списка трехмерных аффинных преобразований, а также из информации о зоне для каждого преобразования, например о координатах ее верхнего левого угла.
Теперь на стадии реконструкции мы больше не играем в чистую «Игру в Хаос». Вместо этого мы начинаем с произвольного изображения /0, возможно, целиком состоящего из черных пикселов. Затем при каждой итерации каждое преобразование из списка применяется ко всем пикселам в зоне этого отображения. Поскольку блоки не перекрываются, то каждое такое преобразование изменяет значения пикселов в одном наборе блоков. В силу того, что преобразование является сжимающим, последовательность изображений /0, будет гарантированно сходиться к неподвижной точке данного преобразования - на практике этот процесс требует от 8 до 10 итераций.
Подробное исследование этого метода наряду с кодом на языке С для его реализации можно найти в книге Марка Нельсона «Сжатие данных» (Mark Nelson. Data Compression - [Nelson, 145]). На рис. 9.36 приведено исходное изображение (занимающее 64 ООО байт), на котором выделены две зоны и два блока (на рисунке они крупнее, чем четыре на четыре или восемь на восемь). Имеет место сильное сходство между одним блоком и одной зоной и также сильное сходство между другим блоком и другой зоной. (Между какими именно?) (Фрактальное сжатие уменьшает требуемое пространство до 2849 байт!)