Техника отыскания аффинных отображений

Сообщение №581 от Mikhail.Pasechnikov 09 сентября 2001 г. 12:01
Тема: Техника отыскания аффинных отображений

Hi All
Приветствую всех прочитавших

Интересует новое в технике отыскания аффинных отображений для произвольного аттрактора. Какие есть новые идеи и методы?

Интересны комментарии увлекающихся этим вопросом к отрывку из Р.М.Кроновер Фракталы и хаос в динамических системах. Основы теории М.Постмаркет.2000.-352 с.
с.121
"Рассмотрим гипотетический пример. Пусть нам требуется передать изображение ковра Серпинского размером 512 на 512. Не применяя сжатия, придется послать 262144 бит информации, нуль или единицу для каждого пиксела. С другой стороны, если бы мы передали всего лишь 18 аффинных коэффициентов трех аффинных преобразований, связанных с ковром Серпинского, мы смогли бы полностью восстановить оригинал в приемной части. Можно сказать, что в этом случае мы достигли бы сжатия 262144:18 = 14563:1..."
Как Вы считаете, в данном примере, корректны ли расчеты Кроновера?


Отклики на это сообщение:

> Hi All
> Приветствую всех прочитавших

> Интересует новое в технике отыскания аффинных отображений для произвольного аттрактора. Какие есть новые идеи и методы?

> Интересны комментарии увлекающихся этим вопросом к отрывку из Р.М.Кроновер Фракталы и хаос в динамических системах. Основы теории М.Постмаркет.2000.-352 с.
> с.121
> "Рассмотрим гипотетический пример. Пусть нам требуется передать изображение ковра Серпинского размером 512 на 512. Не применяя сжатия, придется послать 262144 бит информации, нуль или единицу для каждого пиксела. С другой стороны, если бы мы передали всего лишь 18 аффинных коэффициентов трех аффинных преобразований, связанных с ковром Серпинского, мы смогли бы полностью восстановить оригинал в приемной части. Можно сказать, что в этом случае мы достигли бы сжатия 262144:18 = 14563:1..."
> Как Вы считаете, в данном примере, корректны ли расчеты Кроновера?

$$ А по-моему весь ковер Серпинского можно описать задав только один шаг inflation rule, то есть скажем десяток байт


> Hi All
> Какие есть новые идеи и методы?

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

> Как Вы считаете, в данном примере, корректны ли расчеты
Кроновера?

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

iterated.com - там, 10 лет назад зародился метод фрактального сжатия. Некто Барнсли (IFS) и его аспирант Jacquin (не помню точно фамилию), а еще можно почитать Y.Fisher'a.


Приветствую Вас zet

> > Как Вы считаете, в данном примере, корректны ли расчеты
> Кроновера?
> Как идея корректны, но ошибочны на 16%. Он забыл добавить значения вероятностей, с которыми надо применять линейные преобразования.
> Для сжатия любого изобр-я, конечно же, не удастся найти единое преобразование и придется искать их для отдельных частей изобр-я, поэтому в этом смысле расчеты некорректны.
> В результате, коэффициент сжатия практически не отличается от JPEG.
Аффинные отображения только для сжатия с потерями?
> iterated.com - там, 10 лет назад зародился метод фрактального сжатия. Некто Барнсли (IFS) и его аспирант Jacquin (не помню точно фамилию), а еще можно почитать Y.Fisher'a.
Благодарю за информацию


>> В результате, коэффициент сжатия практически не отличается от JPEG.
> Аффинные отображения только для сжатия с потерями?

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

Мой взгляд тогда был, что либо выч/ресурсов не хватит для того, чтобы без потерь, либо с потерями.
Идея отталкивалась от теоремы Банаха о неподвижной точке.
Строилось "сдвинутое" изобр-е, "близкое" к нужному, разбивалось на мелкие области, а затем уж в каждой части подбиралось свое фрактальное преобразование, которое должно сходиться к изобр-ю, близкому к "сдвинутому".
Подбор преобразований производился из БД афинных преобр-й спц/вида. Своего рода кодирование по кодовой книге.


У Фишера иной подход. Но результат тот же самый:

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


> ...разбивалось на мелкие области, а затем уж в каждой части подбиралось свое ... преобразование, которое должно сходиться к изобр-ю, близкому...
> Подбор преобразований производился из БД ...преобр-й спц/вида. Своего рода кодирование по кодовой книге.
> У Фишера иной подход. Но результат тот же самый:
> Поскольку итерации когда-то надо остановить, получается приближенное решение. Однако природа "приближенности" совсем иная, чем в JPEG. Там - принципиальная потеря данных, здесь - как повезет.
Тогда это все похоже на сжатие полиномами Якоби??


> Тогда это все похоже на сжатие полиномами Якоби??

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

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

Т.о. кодируется не изображение, а преобразование. А поскольку пр-ние линейное, то оно задается матрицей и вектором сдвига вместо паттерна.



Разбиение на подобласти - не является необходимостью, а только следствие ограниченности ресурсов + требование реального времени. Разбиение сокращает перебор претендентов на "подходящие" преобр-я.


Приветствую Вас zet

> Строилось "сдвинутое" изобр-е, "близкое" к нужному, разбивалось на мелкие области, а затем уж в каждой
> части подбиралось свое фрактальное преобразование, которое должно сходиться к изобр-ю, близкому к
> "сдвинутому".
> Подбор преобразований производился из БД афинных преобр-й спц/вида. Своего рода кодирование по
> кодовой книге.
Аналогии проводились по этой цитате, а вот где написано про полиномы Якоби и сжатие

ФФ Дедус и др. Обобщенный спектрально-аналитический метод об-работки информационных массивов М Машиностроение 1999

Всего наилучшего



> Аналогии проводились по этой цитате, а вот где написано про полиномы Якоби и сжатие
> ФФ Дедус и др. Обобщенный спектрально-аналитический метод об-работки информационных массивов М Машиностроение 1999

Может и не нужно так пространно?

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

Сама по себе идея приближать поверхность или одномерную кривую аналитическим способом - не нова.
Использовать для этого разложение по функциональному базису - тоже.
Заслуживает внимания разработаность алгоритмов, хотя отдельные важные случаи умалчиваются.

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

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

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

Однако можно попробовать приложить метод к распознаванию машинописного текста. Но не уверен, что Арлазаров и Ян не рассматривали этот вариант. К тому же опять же вычислительная эффективность и коэффициент распознавания оставляют желать лучшего.
Или анализ сцен, например, в следящих системах (чем не замена МPEG'у).

Согласен, что некоторая аналогия с методом Jacquшn'a есть - запоминаются параметры преобразования.
Но в книге - преобразование одно и оно сразу восстанавливает образец.

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

Что касается методов непосредственно Барнсли и Жаквина, то они на ранних стадиях использовали специально
подобранные такие преобр-я из очень ограниченного набора и для очень маленьких элементов изображения (8-8, 16-16), что существенно снизило коэффициент сжатия.

Ну хватит на сегодня, а то самолетопад чтой-то в США начался.


> Приветствую Вас zet

> > Строилось "сдвинутое" изобр-е, "близкое" к нужному, разбивалось на мелкие области, а затем уж в каждой
> > части подбиралось свое фрактальное преобразование, которое должно сходиться к изобр-ю, близкому к
> > "сдвинутому".
> > Подбор преобразований производился из БД афинных преобр-й спц/вида. Своего рода кодирование по
> > кодовой книге.
> Аналогии проводились по этой цитате, а вот где написано про полиномы Якоби и сжатие

> ФФ Дедус и др. Обобщенный спектрально-аналитический метод об-работки информационных массивов М Машиностроение 1999

> Всего наилучшего
>

Ф.Ф. Дедус с командой работают с очень специфичекими изображениями, подчеркивая специфику, как водится в этих случаях, "закрытостью" тематики.
Убедить их, что часто желаемое выдается за действительное и абсолютно безосновательно (нередки принципиальные ошибки)
мне не удалось.
А в чем первоначальная суть проблемы?
Что ХОЧЕМ?


Приветствую Вас Михалыч

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

> А в чем первоначальная суть проблемы?
> Что ХОЧЕМ?

Интересует новое в технике отыскания аффинных (и не только) отображений для произвольного аттрактора.
Какие есть новые идеи и методы?



> Приветствую Вас Михалыч

> Интересует новое в технике отыскания аффинных (и не только) отображений для произвольного аттрактора.
> Какие есть новые идеи и методы?

А СТАРЫЕ-то были?
Как писал Гайдар-дед про пику, которую сделал Чук (или Гек) для охоты на медведя: "Если чем-нибудь проткнуть шкуру медведя, а потом ткнуть этой пикой в сердце, то медведь, конечно, околеет".
Если серьезно, то все что я увидел в существующих работах- это базовая идея + более или менее разумная организация по-существу переборного процесса.

Убедиться сами можете посмотрев
1) abstracts на сайте конференций "FRACTAL'"
2) на ВМК МГУ работает команда, связанная с конференциями GraphiCon. На сайте есть е-библиотека по фракталам.

Из "свежака" с какой-то математикой могу отметить:
1) диссертация Н.Поликарповой (защита в ВЦ РАН лет 5 назад)
2) работы Левковича из ин-та Келдыша

Из моих европейских знакомых:
1) W. Skarbek (Poland) - фрактальные базисы в задачах Pattern Recognition (интересно)
2) Saupe (Germany) - один из "последних могикан" работающих в теории аффинных фракталов.
На сайте есть доступ к статьям, вышла книга (видел, разговаривал,листал; по-моему - амбициозный ликбез).

Личные взаимоотношения с фракталами.
1) У нас они не пошли. Глаз радует, а по геометрии - плохо.
2) Решал задачу аппроксимации "фрактальной" кривой фрактальными.
Цель - сжатие - цепного кода для представления контура.
Сделал быстрые "Фурьеподобные преобразования, модулированные фрактально".
Работа была заказная, поэтому в публикациях почти не отражена.

В целом, по моему мнению, уровень основной массы современных работ - диплом, или при очень хорошем прикладе и в "родном" Совете - к.т.н.

Нужны подробности, прямые контакты - свяжитесь через модератора.
Успехов!


Приветствую Вас Михалыч

Искренне благодарен.


С уважением Михаил Пасечников


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100