Comments 41
Спасибо за статью.
Есть хаб «Обработка Изображений» (Image Processing) — его вполне достаточно.
ого спасибо за наводку, сейчас перенесу туда, а то я поставил хаб c#, что бы был третьим
а изображение-то совсем не плоское)
(если что я о «филейной части Дженифер»)
Фрактальная размерность — единственная известная измеримая характеристика фракталов. Спасибо за понятное объяснение!
Любопытно, какая размерность у шума, либо сильно зашумленного изображения?
смотря что понимать под шумом, например возьмите фрактал, это множество которое находится в некотором шаре, но очень не эффективно использует весь его объем; а куб находящийся внутри описанного шара, довольно таки не плохо использует его объем; так что для ответа на ваш вопрос нужно определиться что такое шум

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


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

кстати этот опыт вы легко сможете провести, используя вышеприведенный код =)
как пример шума — броуновское движение. Если так, то ответ: размерность траектории (следа) случайного блуждания равняется 3/2
можно я не буду вспоминать вывод? :)

кажется, видел в книге Заславский, Сагдеев «Введение в нелинейную физику — от маятника до турбулентности и хаоса.»
вот тут пишут что у Random walk with no self-intersection размерность 1.55, а у Броуновского движения, не зависимо от размерности пространства, размерность Хаусдорфа всегда 2
Хм. no-intersection — точно не про броуновское движение. Видимо, я запомнил то число, которое в википедии называется Graph of a regular Brownian function (Wiener process) (ну, со случйными перемещениями, распределёнными по Гауссу).

Впрочем, откуда они взяли 2 — тоже понятно. В идеале, если оставить броуновскую частицу бродить вечно, она побывает в каждой точке пространства, поэтому 2. Но насколько этот идеал можно применять к реальности? Надо бы померить реальное движение.
И почему это получается 2 для любой размерности — непонятно.
В идеале, если оставить броуновскую частицу бродить вечно, она побывает в каждой точке пространства, поэтому 2.

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

И почему это получается 2 для любой размерности — непонятно.

мне тоже с ходу так не понятно, но вот статья в которой это доказывается
Вообще больше читайте википедию, вот вами указанной странице размерность цветов цветной капусты 2.33, а на другой странице (http://ru.wikipedia.org/wiki/%D0%A6%D0%B2%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BA%D0%B0%D0%BF%D1%83%D1%81%D1%82%D0%B0) написано 2.88, причём со ссылкой на статью, в которой «we believe 2.8».

Википедию всегда надо перепроверять :)
ну русская википедия часто этим грешит, хотя местами она лучше, например гляньте статьи по размерности Хаусдорфа в англ и русской. хотяв большинстве своем это не так, например посмотрите сколько материала по линейной регрессии в англ, и сколько у нас
Однозначно в избранное, хотелось бы еще статей. И да фраза
так сказать филейной части Дженифер
просто замечательна.
А границы России в каком масштабе брались? Там ведь, вроде как, есть особенность, которая роднит границы стран с фракталами: чем больше масштаб, тем больше особенностей кривой видно. На картах ведь границы сглаженными подаются.
так и есть, чем более точную взять картинку с картой, ну и конечно же более высокого разрешения, тем точнее будет аппроксимация фрактальной размерности, я потому для примера с множеством Жюлиа и нашел картинку почти 4000 на 3000 пикселей, что бы получить высокое значение размерности
Правильно ли я понимаю, что если линия гладкая (не фрактальная), то ее размерность будет всегда 1?
Тогда дробная размерность ваших изображений должна в основном возникать из-за островов для карты России и из-за волос и кед для Дженифер.
очевидно что точную размерность вычислить нельзя, и мы вычисляем приближенное значение, имитируя предел итерациями, и используя данные о количестве и стороне прямоугольника (ими мы имитируем полное покрытие) для вычисления углового коэффициента; и у алгоритма есть очевидные ограничения: разрешение картинки и размер окна сканирования.

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

так же и с картой России, чем выше качество, тем меньше мы можем сделать окно сканирования, тем более точная будет аппроксимация

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

это можно вывести из определения размерности Минковского, скажем длина кривой равна L, тогда что бы покрыть ее всю множествами диаметра e, нужно L/e множеств (по сути это такие одномерные дуги, маленькие отрезки кривой), ну и рассматриваем предел

А как сиё можно применять на практике? Просто устойчивость у признака будет только в случае, когда кривая математическая, как я понимаю. Та же карта России при повышении разрешения должна изменить число к которому стремиться последовательность.
А значит можно использовать разве что в качестве одного из дополнительных признаков в какой-то сложной системе. При этом признак достаточно сложный и не сильно устойчивый.

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

  • множество по опухолям молочной железы состоит из 30 полей, и в принципе сам факт добавления такого признака в этот датасет университетом Висконсина; т.е. было сделано предположение что у ядер раковых и доброкачественных клеток края сильно отличаются, и что бы учесть этот факт, был добавлен такой признак
  • в моей работе все более прозаичнее, всего навсего нужно написать классификатор который будет определять каким шрифтом написан текст; шрифты могут быть как с засечками, так и без
Это плоское изображение?
image
Мне это 'плоское' изображение чуть глаз не выкололо из монитора своей 'плоскостью' :)
Картинка очень сильно влияет на способность к чтению. Только с третьего раза прочитал заголовок статьи правильно.
Мне вот интересно, почему многие люди/книжки так упираются в box counting оценки размерности, тогда как давно известны оценки, дающие более чем на порядок лучшую точность при тех же объемах выборки. Посмотрите на досуге на корреляционную размерность Грассбергера-Прокаччи и бросайте к богам этот 50 лет назад устаревший box counting.
не нужно быть таким категоричным, корреляционная размерность не нова тоже, 31 год назад статья была; утверждая это
тогда как давно известны оценки, дающие более чем на порядок лучшую точность при тех же объемах выборки

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

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

но я вот к чему, не нужно делать так категорично такие почти не доказуемые утверждения; ладно аналитически это почти не доказать, но проведите тогда исследование робастности двух признаков на данных разной природы, и покажите что статистически корреляционная размерность эффективнее, тогда это будет не голословное утверждение
Я говорил, не о степени «современности» алгоритмов, а о том, что примерно 50 лет назад уже стало ясно, что у box counting методов есть неустранимый генетический недостаток, связанный со скоростью сходимости, связанный с использованием тривиальной оценки меры. Корреляционный интеграл фактически одновременно оценивает индуцированную меру, причем используя для этого адаптивную сетку, так что для хаотических данных его преимущества как бы очевидны. На самом деле корреляционная размерность имеет свои недостатки, приводящие к проблемам на нехаотических данных — для множеств с целой размерностью оценки получаются очень неточными. Ну и довольно давно в этой области отказались от попыток оценивать размерности и перешли к использованию энтропии, для которой есть очень эффективные оценки.

Эмпирические и экспериментальные соображения относительно сравнительных свойст разных оченок размерности неплохо описаны вот тут: public.lanl.gov/jt/Papers/est-fractal-dim.pdf

В статьях www.mathnet.ru/php/person.phtml?option_lang=rus&personid=18717 содержится строгое обоснование части приведенных выше утверждений, хотя его и не очень просто оттуда извлечь (как минимум нужно понимать связь между размерностями и мультифрактальным спектром). Понятно, что бессмысленно надеяться на такое доказательство в общем случае, все делается для модельных мер типа бернуллиевой меры, но это довольно хороший пример (в том смысле, что он очень плох с точки зрения точности самих оценок).
почему многие люди/книжки так упираются в box counting оценки размерности

кстати, про box-counting, вот алгоритм тупо в лоб например не эффективен с точки зрения вычисления

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

Тем самым, представляя контур как набор прямых, мы должны прийти к значению 1. Что, собственно, и наблюдается с попцом дженифер и картой России. Да и кривой Коха тоже, если вы ее не генерировали в рантайм режиме. Если мы представим, как совокупность точек — то 0.

На отклонение от 1 ( в случае рассмотрения, как совокупности прямых) для контура, увы и ах, сильно влияет расположение сетки относительно контура. Это хорошо видно, если повернуть квадрат относительно сетки на 45 градусов.
Only those users with full accounts are able to leave comments. Log in, please.