Box Counting, Measuring a Pattern Across Scales, math that surprises you lesson

Counting exact smaller copies gives the dimension of Sierpinski’s triangle, but a photograph of a coastline or a computer image of a fractal comes with no list of copies. Can a grid of boxes, made finer and finer, still tell how densely a shape fills space? This page defines the box-counting dimension, reads it as the slope of a log-log plot, and tests it on an image of Sierpinski’s triangle whose dimension is known, to see how the resolution of the grid, its position and the chosen range of box sizes move a finite estimate.

Key terms

Box-counting dimension

Definition Let $F$ be a bounded set in the plane with at least one point, and let $\varepsilon > 0$ be a box width. The grid of width $\varepsilon$ is made of the squares $[i\varepsilon, (i + 1)\varepsilon) \times [j\varepsilon, (j + 1)\varepsilon)$ for all whole numbers $i$ and $j$ , each containing its left and bottom edges but not its right and top edges, so that every point of the plane lies in exactly one box. Let $N(\varepsilon)$ be the number of boxes that contain at least one point of $F$ . The box-counting dimension of $F$ is

\dim_{\mathrm{B}} F = \lim_{\varepsilon \to 0} \frac{\log N(\varepsilon)}{\log (1/\varepsilon)}

when this limit exists. When it does not, the smallest and the largest values that the quotient keeps coming back to as $\varepsilon$ shrinks, its lower and upper limits, are the lower and upper box-counting dimensions. Shifting the grid, using closed boxes, or counting the fewest squares of side $\varepsilon$ that cover $F$ changes $N(\varepsilon)$ by at most a fixed factor that does not depend on $\varepsilon$ . The logarithm of a fixed factor divided by $\log (1/\varepsilon)$ tends to $0$ , so none of these choices changes the limits. On a line the boxes are intervals $[i\varepsilon, (i + 1)\varepsilon)$ , and in space they are cubes. For a self-similar set whose pieces satisfy the open set condition, the box-counting dimension equals the similarity dimension and the Hausdorff dimension. In general the Hausdorff dimension is at most the lower box-counting dimension, and the two can differ.

In plain words Lay a grid over the shape, count the boxes it touches, and see how fast the count grows as the boxes shrink. If halving the box width multiplies the count by about $2^d$ , the dimension is $d$ .

Example Take the segment from $(0, 0.37)$ to $(1, 0.37)$ . With $\varepsilon = \tfrac{1}{4}$ it lies in one row of boxes and meets 5 of them, the four over $0 \le x < 1$ and one more that holds only its right end. With $\varepsilon = \tfrac{1}{8}$ it meets 9, and whenever $1/\varepsilon$ is a whole number it meets $1/\varepsilon + 1$ boxes. The filled unit square with corners $(0, 0)$ and $(1, 1)$ meets $(1/\varepsilon + 1)^2$ boxes, 25 for $\varepsilon = \tfrac{1}{4}$ and 81 for $\varepsilon = \tfrac{1}{8}$ , because a row and a column of boxes hold only points of its top and right edges. Halving the width roughly doubles the first count and roughly multiplies the second by 4. The extra boxes come from a convention at the edges and fade in the limit. For $\varepsilon = \tfrac{1}{1000}$ the two quotients are already about 1.0001 and 2.0003, and they tend to the dimensions 1 and 2.

Log-log plot

Definition A log-log plot of box counts marks, for each box width $\varepsilon$ used, the point with horizontal coordinate $\log (1/\varepsilon)$ and vertical coordinate $\log N(\varepsilon)$ , with the same base of logarithm on both axes. If $N(\varepsilon) = C\varepsilon^{-d}$ for constants $C > 0$ and $d$ over a range of widths, then

\begin{aligned} \log N(\varepsilon) &= \log C \\[0.4em] &\quad + d \log (1/\varepsilon), \end{aligned}

so the points lie on a straight line with slope $d$ . The slope between two widths $\varepsilon_1 > \varepsilon_2$ is

\frac{\log \bigl(N(\varepsilon_2) / N(\varepsilon_1)\bigr)}{\log (\varepsilon_1 / \varepsilon_2)},

and it does not depend on the base. The single quotient $\log N(\varepsilon) / \log (1/\varepsilon)$ at one width is not the slope, because the constant $C$ adds $\log C$ to its numerator. It approaches the slope only as $\varepsilon$ shrinks, which is why the definition of the dimension takes a limit.

In plain words On a log-log plot, multiplying the count by the same factor at each halving of the width becomes climbing the same height at each equal step to the right. A power law turns into a straight line, and its slope is the exponent.

Example If halving the width multiplies the count by 3, say from 100 boxes to 300, the slope is $\log 3 / \log 2 \approx 1.585$ , the value for Sierpinski’s triangle. For an exact case, take the Cantor set, what remains of the interval from 0 to 1 after removing open middle thirds forever, and widths $\varepsilon = 3^{-k}$ . Each of the $2^k$ intervals left after $k$ removal steps fills one box of this grid except for its right end, which lies in the next box, and that next box holds no other point of the set. So $N(3^{-k}) = 2^{k+1}$ , a power law with $C = 2$ , and the points

\bigl(k \log 3,\ (k + 1) \log 2\bigr)

lie exactly on a line of slope $\log 2 / \log 3 \approx 0.631$ . The single quotient is much larger at coarse widths. It is $\log 16 / \log 27 \approx 0.841$ at $\varepsilon = \tfrac{1}{27}$ , and still about $0.721$ at $\varepsilon = 3^{-7}$ .

Grid resolution

Definition The grid resolution of a box count is its box width $\varepsilon$ , often stated as the number of boxes across the frame, which is $1/\varepsilon$ for a frame of width 1. A study uses a list of resolutions, usually halving the width each time, which places the points of the log-log plot at equal steps of $\log 2$ along the horizontal axis. A digital image has a resolution of its own, its pixel size, which is the finest scale at which it carries any information about the shape. Boxes near the size of a pixel measure the pixels, the thickness of drawn lines or the gray levels, not the ideal shape. Boxes so large that only a few of them cover the whole image mostly measure where the grid happens to sit. Only a middle range of resolutions says something about the shape itself, and the image has to be fine enough for that range to exist.

In plain words The resolution is how fine the grid is. Too coarse, and a handful of boxes hide all the structure. Too fine, and the boxes see the pixels instead of the shape.

Example Start with a square, keep three of its four quarter squares, the bottom left, the bottom right and the top left, and repeat this in every kept square. The limit is a right-angled Sierpinski triangle, made of 3 half-size copies of itself, with dimension $\log 3 / \log 2$ . After 10 steps, $3^{10} = 59049$ squares remain, and drawing each as one black pixel gives an image 1024 pixels wide. Number the pixel columns and rows from 0 to 1023, starting at the bottom left. Then pixel $(i, j)$ is black exactly when the binary digits of $i$ and $j$ never have a 1 in the same place, which is also exactly when the binomial coefficient $\binom{i+j}{i}$ in Pascal’s triangle is odd. With the grid aligned to the corner of the image, boxes of 512, 256, 128 and so on down to 1 pixel give $3, 9, 27, \ldots, 59049$ occupied boxes, exactly 3 times as many at each halving, because every aligned box holds a copy of the construction or nothing. Below the pixel size the pattern breaks. Boxes of half a pixel give $4 \cdot 59049 = 236196$ occupied boxes, 4 times as many, because at that scale each black pixel is a filled square and the image looks two dimensional. At the coarse end, one box of 1024 pixels covers everything, while the same grid shifted by half a box spreads the image over 4 boxes and meets 3 of them.

Dimension estimate

Definition A dimension estimate is a number computed from box counts at finitely many widths $\varepsilon_1, \ldots, \varepsilon_m$ , most often the slope of the least-squares line through the points $(x_k, y_k)$ with $x_k = \log (1/\varepsilon_k)$ and $y_k = \log N(\varepsilon_k)$ ,

\hat{d} = \frac{\sum_k (x_k - \bar{x})(y_k - \bar{y})}{\sum_k (x_k - \bar{x})^2},

where $\bar{x}$ and $\bar{y}$ are the averages of the $x_k$ and of the $y_k$ . It depends on how the image was made, including its resolution and, for an image with gray pixels, the threshold rule that decides which pixels count as part of the shape. It also depends on where the grid sits, on which widths were used and on the range of widths included in the fit. A report should state all of these and repeat the count for several positions of the grid to show the spread. No finite set of counts proves the limiting dimension, because counts at smaller widths, which were not measured, could follow a different slope.

In plain words An estimate is the slope you measure from the counts you actually have. It is only as good as the image, the grid and the range of box sizes behind it, and it should be reported together with all three.

Example For the 1024 pixel image of the right-angled Sierpinski triangle, compare the grid aligned with the corner and the grid shifted by half a box both to the right and up.

Box width in pixels	Aligned grid	Shifted grid
1024	1	3
512	3	6
256	9	15
128	27	42
64	81	123
32	243	366
16	729	1095
8	2187	3282
4	6561	9843

The aligned counts give exactly $\log 3 / \log 2 \approx 1.585$ over any range of these widths, but only because each aligned box matches a step of the construction, a coincidence an unfamiliar image will not offer. The shifted counts grow by factors that approach 3 from below, from 2 at the coarsest step to 2.999 at the finest step shown. Fitting them from 4 to 256 pixels gives about 1.564, from 16 to 256 pixels about 1.550, and from 64 to 1024 pixels only about 1.352, because the coarsest boxes pull the slope down. Shifting the grid only to the right, or only up, gives about 1.578 over 4 to 256 pixels, and aligned boxes of 3, 6, 12 and so on up to 192 pixels give about 1.592. With the coarsest boxes left out, these estimates lie between about 1.55 and 1.59, close to the true value, and that spread belongs in the report as much as any single number.

Check yourself

Change a number. A shape gives 12, 48 and 192 occupied boxes at widths $\tfrac{1}{3}$ , $\tfrac{1}{9}$ and $\tfrac{1}{27}$ . Estimate its dimension.

Show the answer

Each division of the width by 3 multiplies the count by 4, so the slope between the first two widths is

\frac{\log (48/12)}{\log 3} = \frac{\log 4}{\log 3} \approx 1.262,

and the slope between the last two is the same. The three points lie on one line, so the least-squares slope is also about 1.262. This is the growth of a set made of 4 copies at one third of the size, like the Koch curve. If the pattern continued, the count at width $\tfrac{1}{81}$ would be 768, but three counts cannot show that it does continue, so 1.262 remains an estimate.

Find a common mistake. Cover a filled square of side 3 with the fewest boxes of width $\varepsilon$ , which takes $(3/\varepsilon)^2$ boxes when $3/\varepsilon$ is a whole number. A friend divides $\log N(\varepsilon)$ by $\log (1/\varepsilon)$ at $\varepsilon = \tfrac{1}{2}$ and reports the dimension. What does the friend get, and what is wrong?

Show the answer

At $\varepsilon = \tfrac{1}{2}$ the count is $6^2 = 36$ , and the quotient is $\log 36 / \log 2 \approx 5.17$ , impossible for a set in the plane, whose dimension is at most 2. The quotient is not the slope. Since $N(\varepsilon) = 9\varepsilon^{-2}$ ,

\frac{\log N(\varepsilon)}{\log (1/\varepsilon)} = 2 + \frac{\log 9}{\log (1/\varepsilon)},

and the constant 9 inflates the quotient. It tends to 2 only slowly, and is still about 2.318 at $\varepsilon = \tfrac{1}{1000}$ . Comparing two widths removes the constant. At $\varepsilon = \tfrac{1}{4}$ the count is $12^2 = 144$ , and the slope between the two widths is $\log (144/36) / \log 2 = \log 4 / \log 2 = 2$ , the correct dimension.

Test a condition. Use box counting on the set of rational numbers between 0 and 1, the fractions $p/q$ in that interval. What dimension does it give, and why does the Hausdorff dimension of this set, defined in Fractal Dimension, Between a Line and an Area, come out as 0 instead?

Show the answer

Every interval $[i\varepsilon, (i + 1)\varepsilon)$ that meets the interval from 0 to 1 either overlaps it in a stretch of positive length, which contains a fraction, or is the interval starting at 1, which contains the fraction 1. So the rationals meet exactly as many boxes as the whole interval at every width, and their box-counting dimension is 1, the same as for the interval. Box counting cannot notice the missing irrational numbers, because every box that meets the interval also catches a fraction. For the Hausdorff dimension, list the rationals as $q_1, q_2, q_3, \ldots$ , which is possible because they are countable. Fix $d > 0$ and a small number $\eta > 0$ , and cover $q_n$ by an interval of length $\ell_n$ with $\ell_n^d = \eta \, 2^{-n}$ . Then

\sum_n \ell_n^d = \eta \bigl(2^{-1} + 2^{-2} + \cdots\bigr) = \eta,

and every $\ell_n$ is at most $\eta^{1/d}$ . Given any $\delta > 0$ , every small enough $\eta$ makes all these lengths at most $\delta$ , so $\mathcal{H}^d_\delta$ of the rationals is at most every small $\eta$ and is therefore $0$ . Hence $\mathcal{H}^d$ of the rationals is $0$ for every $d > 0$ , and their Hausdorff dimension is 0. The two dimensions disagree here, which is why a box-counting value should be quoted as a box-counting dimension.

Box Counting, Measuring a Pattern Across Scales

Key terms

Box-counting dimension

Log-log plot

Grid resolution

Dimension estimate

Check yourself

How this lesson connects

Builds on