Re: Measuring Fractal Dimension ?

Discussion in 'Python' started by Lawrence D'Oliveiro, Jun 14, 2009.

  1. In message <>, Peter Billam wrote:

    > Are there any modules, packages, whatever, that will
    > measure the fractal dimensions of a dataset, e.g. a time-series ?


    I don't think any countable set, even a countably-infinite set, can have a
    fractal dimension. It's got to be uncountably infinite, and therefore
    uncomputable.
     
    Lawrence D'Oliveiro, Jun 14, 2009
    #1
    1. Advertising

  2. Lawrence D'Oliveiro <_zealand> writes:

    > In message <>, Peter Billam wrote:
    >
    >> Are there any modules, packages, whatever, that will
    >> measure the fractal dimensions of a dataset, e.g. a time-series ?

    >
    > I don't think any countable set, even a countably-infinite set, can have a
    > fractal dimension. It's got to be uncountably infinite, and therefore
    > uncomputable.


    I think there are attempts to estimate the fractal dimension of a set
    using a finite sample from this set. But I can't remember where I got
    this thought from!

    --
    Arnaud
     
    Arnaud Delobelle, Jun 14, 2009
    #2
    1. Advertising

  3. Lawrence D'Oliveiro

    Paul Rubin Guest

    Arnaud Delobelle <> writes:
    > I think there are attempts to estimate the fractal dimension of a set
    > using a finite sample from this set. But I can't remember where I got
    > this thought from!


    There are image data compression schemes that work like that, trying
    to detect self-similarity in the data. It can go the reverse way too.
    There was a program called Genuine Fractals that tried to increase the
    apparent resolution of photographs by adding artificial detail
    constructed from detected self-similarity. Its results were mixed, as
    I remember.
     
    Paul Rubin, Jun 14, 2009
    #3
  4. Lawrence D'Oliveiro wrote:

    > In message <>, Peter Billam wrote:
    >
    >> Are there any modules, packages, whatever, that will
    >> measure the fractal dimensions of a dataset, e.g. a time-series ?

    >
    > I don't think any countable set, even a countably-infinite set, can have a
    > fractal dimension. It's got to be uncountably infinite, and therefore
    > uncomputable.


    Incorrect. Koch's snowflake, for example, has a fractal dimension of log
    4/log 3 ≈ 1.26, a finite area of 8/5 times that of the initial triangle,
    and a perimeter given by lim n->inf (4/3)**n. Although the perimeter is
    infinite, it is countably infinite and computable.

    Strictly speaking, there's not one definition of "fractal dimension", there
    are a number of them. One of the more useful is the "Hausdorf dimension",
    which relates to the idea of how your measurement of the size of a thing
    increases as you decrease the size of your yard-stick. The Hausdorf
    dimension can be statistically estimated for finite objects, e.g. the
    fractal dimension of the coast of Great Britain is approximately 1.25 while
    that of Norway is 1.52; cauliflower has a fractal dimension of 2.33 and
    crumpled balls of paper of 2.5; the surface of the human brain and lungs
    have fractal dimensions of 2.79 and 2.97.



    --
    Steven
     
    Steven D'Aprano, Jun 14, 2009
    #4
  5. Lawrence D'Oliveiro

    Kay Schluehr Guest

    On 14 Jun., 16:00, Steven D'Aprano
    <> wrote:

    > Incorrect. Koch's snowflake, for example, has a fractal dimension of log
    > 4/log 3 ≈ 1.26, a finite area of 8/5 times that of the initial triangle,
    > and a perimeter given by lim n->inf (4/3)**n. Although the perimeter is
    > infinite, it is countably infinite and computable.


    No, the Koch curve is continuous in R^2 and uncountable. Lawrence is
    right and one can trivially cover a countable infinite set with disks
    of the diameter 0, namely by itself. The sum of those diameters to an
    arbitrary power is also 0 and this yields that the Hausdorff dimension
    of any countable set is 0.
     
    Kay Schluehr, Jun 14, 2009
    #5
  6. On Sun, 14 Jun 2009 14:29:04 -0700, Kay Schluehr wrote:

    > On 14 Jun., 16:00, Steven D'Aprano
    > <> wrote:
    >
    >> Incorrect. Koch's snowflake, for example, has a fractal dimension of
    >> log 4/log 3 ≈ 1.26, a finite area of 8/5 times that of the initial
    >> triangle, and a perimeter given by lim n->inf (4/3)**n. Although the
    >> perimeter is infinite, it is countably infinite and computable.

    >
    > No, the Koch curve is continuous in R^2 and uncountable.


    I think we're talking about different things. The *number of points* in
    the Koch curve is uncountably infinite, but that's nothing surprising,
    the number of points in the unit interval [0, 1] is uncountably infinite.
    But the *length* of the Koch curve is not, it's given by the above limit,
    which is countably infinite (it's a rational number for all n).


    > Lawrence is
    > right and one can trivially cover a countable infinite set with disks of
    > the diameter 0, namely by itself. The sum of those diameters to an
    > arbitrary power is also 0 and this yields that the Hausdorff dimension
    > of any countable set is 0.


    Nevertheless, the Hausdorff dimension (or a close approximation thereof)
    can be calculated from the scaling properties of even *finite* objects.
    To say that self-similar objects like broccoli or the inner surface of
    the human lungs fails to nest at all scales is pedantically correct but
    utterly pointless. If it's good enough for Benoît Mandelbrot, it's good
    enough for me.



    --
    Steven
     
    Steven D'Aprano, Jun 15, 2009
    #6
  7. Lawrence D'Oliveiro

    pdpi Guest

    On Jun 15, 5:55 am, Steven D'Aprano
    <> wrote:
    > On Sun, 14 Jun 2009 14:29:04 -0700, Kay Schluehr wrote:
    > > On 14 Jun., 16:00, Steven D'Aprano
    > > <> wrote:

    >
    > >> Incorrect. Koch's snowflake, for example, has a fractal dimension of
    > >> log 4/log 3 ≈ 1.26, a finite area of 8/5 times that of the initial
    > >> triangle, and a perimeter given by lim n->inf (4/3)**n. Although the
    > >> perimeter is infinite, it is countably infinite and computable.

    >
    > > No, the Koch curve is continuous in R^2 and uncountable.

    >
    > I think we're talking about different things. The *number of points* in
    > the Koch curve is uncountably infinite, but that's nothing surprising,
    > the number of points in the unit interval [0, 1] is uncountably infinite.
    > But the *length* of the Koch curve is not, it's given by the above limit,
    > which is countably infinite (it's a rational number for all n).
    >
    > > Lawrence is
    > > right and one can trivially cover a countable infinite set with disks of
    > > the diameter 0, namely by itself. The sum of those diameters to an
    > > arbitrary power is also 0 and this yields that the Hausdorff dimension
    > > of any countable set is 0.

    >
    > Nevertheless, the Hausdorff dimension (or a close approximation thereof)
    > can be calculated from the scaling properties of even *finite* objects.
    > To say that self-similar objects like broccoli or the inner surface of
    > the human lungs fails to nest at all scales is pedantically correct but
    > utterly pointless. If it's good enough for Benoît Mandelbrot, it's good
    > enough for me.
    >
    > --
    > Steven


    You're mixing up the notion of countability. It only applies to set
    sizes. Unless you're saying that there an infinite series has a
    countable number of terms (a completely trivial statement), to say
    that the length is "countably finite" simply does not parse correctly
    (let alone being semantically correct or not). This said, I agree with
    you: I reckon that the Koch curve, while composed of uncountable
    cardinality, is completely described by the vertices, so a countable
    set of points. It follows that you must be able to correctly calculate
    the Hausdorff dimension of the curve from those control points alone,
    so you should also be able to estimate it from a finite sample (you
    can arguably infer self-similarity from a limited number of self-
    similar generations).
     
    pdpi, Jun 15, 2009
    #7
  8. Lawrence D'Oliveiro

    Paul Rubin Guest

    Lawrence D'Oliveiro <_zealand> writes:
    > I don't think any countable set, even a countably-infinite set, can have a
    > fractal dimension. It's got to be uncountably infinite, and therefore
    > uncomputable.


    I think the idea is you assume uniform continuity of the set (as
    expressed by a parametrized curve). That should let you approximate
    the fractal dimension.

    As for countability, remember that the reals are a separable metric
    space, so the value of a continuous function any dense subset of the
    reals (e.g. on the rationals, which are countable) completely
    determines the function, iirc.
     
    Paul Rubin, Jun 16, 2009
    #8
  9. In message <>, wrote:

    > Lawrence D'Oliveiro <_zealand> writes:
    >
    >> I don't think any countable set, even a countably-infinite set, can have
    >> a fractal dimension. It's got to be uncountably infinite, and therefore
    >> uncomputable.

    >
    > I think the idea is you assume uniform continuity of the set (as
    > expressed by a parametrized curve). That should let you approximate
    > the fractal dimension.


    Fractals are, by definition, not uniform in that sense.
     
    Lawrence D'Oliveiro, Jun 17, 2009
    #9
  10. On Wed, Jun 17, 2009 at 4:50 AM, Lawrence
    D'Oliveiro<_zealand> wrote:
    > In message <>,  wrote:
    >
    >> Lawrence D'Oliveiro <_zealand> writes:
    >>
    >>> I don't think any countable set, even a countably-infinite set, can have
    >>> a fractal dimension. It's got to be uncountably infinite, and therefore
    >>> uncomputable.

    >>
    >> I think the idea is you assume uniform continuity of the set (as
    >> expressed by a parametrized curve).  That should let you approximate
    >> the fractal dimension.

    >
    > Fractals are, by definition, not uniform in that sense.


    I had my doubts on this statement being true, so I've gone to my copy
    of Gerald Edgar's "Measure, Topology and Fractal Geometry" and
    Proposition 2.4.10 on page 69 states: "The sequence (gk), in the
    dragon construction of the Koch curve converges uniformly." And
    uniform continuity is a very well defined concept, so there really
    shouldn't be an interpretation issue here either. Would not stick my
    head out for it, but I am pretty sure that a continuous sequence of
    curves that converges to a continuous curve, will do so uniformly.

    Jaime

    --
    (\__/)
    ( o_O)
    ( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus
    planes de dominación mundial.
     
    Jaime Fernandez del Rio, Jun 17, 2009
    #10
  11. Lawrence D'Oliveiro

    Paul Rubin Guest

    Jaime Fernandez del Rio <> writes:
    > I am pretty sure that a continuous sequence of
    > curves that converges to a continuous curve, will do so uniformly.


    I think a typical example of a curve that's continuous but not
    uniformly continuous is

    f(t) = sin(1/t), defined when t > 0

    It is continuous at every t>0 but wiggles violently as you get closer
    to t=0. You wouldn't be able to approximate it by sampling a finite
    number of points. A sequence like

    g_n(t) = sin((1+1/n)/ t) for n=1,2,...

    obviously converges to f, but not uniformly. On a closed interval,
    any continuous function is uniformly continuous.
     
    Paul Rubin, Jun 17, 2009
    #11
  12. On Jun 17, 2009, at 2:04 AM, Paul Rubin wrote:

    > Jaime Fernandez del Rio <> writes:
    >> I am pretty sure that a continuous sequence of
    >> curves that converges to a continuous curve, will do so uniformly.

    >
    > I think a typical example of a curve that's continuous but not
    > uniformly continuous is
    >
    > f(t) = sin(1/t), defined when t > 0
    >
    > It is continuous at every t>0 but wiggles violently as you get closer
    > to t=0. You wouldn't be able to approximate it by sampling a finite
    > number of points. A sequence like
    >
    > g_n(t) = sin((1+1/n)/ t) for n=1,2,...
    >
    > obviously converges to f, but not uniformly. On a closed interval,
    > any continuous function is uniformly continuous.


    Isn't (-∞, ∞) closed?

    Charles Yeomans
     
    Charles Yeomans, Jun 17, 2009
    #12
  13. On Jun 17, 7:04 am, Paul Rubin <http://> wrote:
    > I think a typical example of a curve that's continuous but not
    > uniformly continuous is
    >
    >    f(t) = sin(1/t), defined when t > 0
    >
    > It is continuous at every t>0 but wiggles violently as you get closer
    > to t=0.  You wouldn't be able to approximate it by sampling a finite
    > number of points.  A sequence like
    >
    >    g_n(t) = sin((1+1/n)/ t)    for n=1,2,...
    >
    > obviously converges to f, but not uniformly.  On a closed interval,
    > any continuous function is uniformly continuous.


    Right, but pointwise convergence doesn't imply uniform
    convergence even with continuous functions on a closed
    bounded interval. For an example, take the sequence
    g_n (n >= 0), of continuous real-valued functions on
    [0, 1] defined by:

    g_n(t) = nt if 0 <= t <= 1/n else 1

    Then for any 0 <= t <= 1, g_n(t) -> 0 as n -> infinity.
    But the convergence isn't uniform: max_t(g_n(t)-0) = 1
    for all n.

    Maybe James is thinking of the standard theorem
    that says that if a sequence of continuous functions
    on an interval converges uniformly then its limit
    is continuous?

    Mark
     
    Mark Dickinson, Jun 17, 2009
    #13
  14. On Jun 17, 12:52 pm, Mark Dickinson <> wrote:
    > g_n(t) = nt if 0 <= t <= 1/n else 1


    Whoops. Wrong definition. That should be:

    g_n(t) = nt if 0 <= t <= 1/n else
    n(2/n-t) if 1/n <= t <= 2/n else 0

    Then my claim that g_n(t) -> 0 for all t might
    actually make sense...
     
    Mark Dickinson, Jun 17, 2009
    #14
  15. On Wed, Jun 17, 2009 at 1:52 PM, Mark Dickinson<> wrote:
    > Maybe James is thinking of the standard theorem
    > that says that if a sequence of continuous functions
    > on an interval converges uniformly then its limit
    > is continuous?


    Jaime was simply plain wrong... The example that always comes to mind
    when figuring out uniform convergence (or lack of it), is the step
    function , i.e. f(x)= 0 if x in [0,1), x(x)=1 if x >= 1, being
    approximated by the sequence f_n(x) = x**n if x in [0,1), f_n(x) = 1
    if x>=1, where uniform convergence is broken mostly due to the
    limiting function not being continuous.

    I simply was too quick with my extrapolations, and have realized I
    have a looooot of work to do for my "real and functional analysis"
    exam coming in three weeks...

    Jaime

    P.S. The snowflake curve, on the other hand, is uniformly continuous, right?

    --
    (\__/)
    ( o_O)
    ( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus
    planes de dominación mundial.
     
    Jaime Fernandez del Rio, Jun 17, 2009
    #15
  16. On Jun 17, 1:26 pm, Jaime Fernandez del Rio <>
    wrote:
    > On Wed, Jun 17, 2009 at 1:52 PM, Mark Dickinson<> wrote:
    > > Maybe James is thinking of the standard theorem
    > > that says that if a sequence of continuous functions
    > > on an interval converges uniformly then its limit
    > > is continuous?


    s/James/Jaime. Apologies.

    > P.S. The snowflake curve, on the other hand, is uniformly continuous, right?


    Yes, at least in the sense that it can be parametrized
    by a uniformly continuous function from [0, 1] to the
    Euclidean plane. I'm not sure that it makes a priori
    sense to describe the curve itself (thought of simply
    as a subset of the plane) as uniformly continuous.

    Mark
     
    Mark Dickinson, Jun 17, 2009
    #16
  17. Lawrence D'Oliveiro

    pdpi Guest

    On Jun 17, 1:26 pm, Jaime Fernandez del Rio <>
    wrote:
    > P.S. The snowflake curve, on the other hand, is uniformly continuous, right?



    The definition of uniform continuity is that, for any epsilon > 0,
    there is a delta > 0 such that, for any x and y, if x-y < delta, f(x)-f
    (y) < epsilon. Given that Koch's curve is shaped as recursion over the
    transformation from ___ to _/\_, it's immediately obvious that, for a
    delta of at most the length of ____, epsilon will be at most the
    height of /. It follows that, inversely, for any arbitrary epsilon,
    you find the smallest / that's still taller than epsilon, and delta is
    bound by the respective ____. (hooray for ascii demonstrations)

    Curiously enough, it's the recursive/self-similar nature of the Koch
    curve so easy to prove as uniformly continuous.
     
    pdpi, Jun 17, 2009
    #17
  18. On Jun 17, 2:18 pm, pdpi <> wrote:
    > On Jun 17, 1:26 pm, Jaime Fernandez del Rio <>
    > wrote:
    >
    > > P.S. The snowflake curve, on the other hand, is uniformly continuous, right?

    >
    > The definition of uniform continuity is that, for any epsilon > 0,
    > there is a delta > 0 such that, for any x and y, if x-y < delta, f(x)-f
    > (y) < epsilon. Given that Koch's curve is shaped as recursion over the
    > transformation from ___ to _/\_, it's immediately obvious that, for a
    > delta of at most the length of ____, epsilon will be at most the
    > height of /. It follows that, inversely, for any arbitrary epsilon,
    > you find the smallest / that's still taller than epsilon, and delta is
    > bound by the respective ____. (hooray for ascii demonstrations)


    I think I'm too stupid to follow this. It looks as though
    you're treating (a portion of?) the Koch curve as the graph
    of a function f from R -> R and claiming that f is uniformly
    continuous. But the Koch curve isn't such a graph (it fails
    the 'vertical line test', in the language of precalculus 101),
    so I'm confused.

    Here's an alternative proof:

    Let K_0, K_1, K_2, ... be the successive generations of the Koch
    curve, so that K_0 is the closed line segment from (0, 0) to
    (1, 0), K_1 looks like _/\_, etc.

    Parameterize each Kn by arc length, scaled so that the domain
    of the parametrization is always [0, 1] and oriented so that
    the parametrizing function fn has fn(0) = (0,0) and fn(1) = (1, 0).

    Let d = ||f1 - f0||, a positive real constant whose exact value
    I can't be bothered to calculate[*] (where ||f1 - f0|| means
    the maximum over all x in [0, 1] of the distance from
    f0(x) to f1(x)).

    Then from the self-similarity we get ||f2 - f1|| = d/3,
    ||f3 - f2|| = d/9, ||f4 - f3|| = d/27, etc.

    Hence, since sum_{i >= 0} d/(3^i) converges absolutely,
    the sequence f0, f1, f2, ... converges *uniformly* to
    a limiting function f : [0, 1] -> R^2 that parametrizes the
    Koch curve. And since a uniform limit of uniformly continuous
    function is uniformly continuous, it follows that f is
    uniformly continuous.

    Mark

    [*] I'm guessing 1/sqrt(12).
     
    Mark Dickinson, Jun 17, 2009
    #18
  19. Lawrence D'Oliveiro

    Paul Rubin Guest

    Mark Dickinson <> writes:
    > It looks as though you're treating (a portion of?) the Koch curve as
    > the graph of a function f from R -> R and claiming that f is
    > uniformly continuous. But the Koch curve isn't such a graph (it
    > fails the 'vertical line test',


    I think you treat it as a function f: R -> R**2 with the usual
    distance metric on R**2.
     
    Paul Rubin, Jun 17, 2009
    #19
  20. On Jun 17, 3:46 pm, Paul Rubin <http://> wrote:
    > Mark Dickinson <> writes:
    > > It looks as though you're treating (a portion of?) the Koch curve as
    > > the graph of a function f from R -> R and claiming that f is
    > > uniformly continuous.  But the Koch curve isn't such a graph (it
    > > fails the 'vertical line test',

    >
    > I think you treat it as a function f: R -> R**2 with the usual
    > distance metric on R**2.


    Right. Or rather, you treat it as the image of such a function,
    if you're being careful to distinguish the curve (a subset
    of R^2) from its parametrization (a continuous function
    R -> R**2). It's the parametrization that's uniformly
    continuous, not the curve, and since any curve can be
    parametrized in many different ways any proof of uniform
    continuity should specify exactly which parametrization is
    in use.

    Mark
     
    Mark Dickinson, Jun 17, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Josechu

    An applet of a peculiar fractal

    Josechu, Jan 3, 2004, in forum: Java
    Replies:
    2
    Views:
    403
    Josechu
    Jan 3, 2004
  2. Steve Holden

    Re: Fractal curve

    Steve Holden, Nov 27, 2005, in forum: Python
    Replies:
    0
    Views:
    424
    Steve Holden
    Nov 27, 2005
  3. s.subbarayan
    Replies:
    1
    Views:
    467
  4. Projection of fractal surfaces

    , Feb 25, 2005, in forum: C Programming
    Replies:
    1
    Views:
    352
    Hans-Bernhard Broeker
    Feb 25, 2005
  5. Luuk
    Replies:
    15
    Views:
    831
    Nobody
    Feb 11, 2010
Loading...

Share This Page