BOX COUNTING
A series of grids of decreasing calibre being laid over an image. This is the basic method of box counting.
Box Counting Sampling Methods
- Introduction
- Fixed Grid Sampling
- Sampling Issues
- Sliding Scan and Other Sampling Methods
- Box Counting Options
- Home
What is Box Counting?
Box counting is a sampling
or data gathering process that FracLac uses to find
several types of
fractal dimension
(DF),
and a feature known as
lacunarity.
The main type of fractal dimension is
the box counting dimension
(Dʙ); but FracLac calculates
average cover (D͞ᵪ) and
mass dimensions (Dʍ),
as well as
filtered
values based on basic box counting and other values based on
variations of basic box counting.
The basic procedure is to systematically lay a
series
of grids of decreasing calibre (the boxes) over
an image and record data (the counting) for each
successive calibre. In this way it emulates
scaling
to approximate
complexity as
a DF.
You can see what that basic task looks like in the
animation.
Counting usually
means tallying how many of the boxes within a grid had
any part of the important detail in the image in them.
In the image shown here, the important detail
is the white pixels,
or
foreground,
which are separate from the "unimportant" black
background.
Calculating the Box Counting Dimension
Box counting solves the problem identified on another page of our not usually knowing the relationship between scale and detail ahead of time when trying to find a scaling rule. The solution? Sample a pattern as we saw in the above illustration using arbitrary scaling, then make inferences using the handy-dandy technique of determining how detail (N) changes with scale (ε) by finding the slope of the logarithmic regression line for N and ε. That is, the Dʙ = the slope of ln N / ln ε. Too much, too fast? Read on to fill in some blanks.
Detail vs Scale or Count vs Box Size
To recap from another page, for scaling rules, detail and scale are the critical factors in determining a DF. "Detail" is N and "scale" is ε. N = ε-DF, which we then solve using logs to get that DF = ln N / ln ε.
Essentials of Box Counting
In a nutshell, the two key features of box counting are the count and the calibre for each sampling element. From the previous discussion of scaling rules, N is approximated by the count, and ε or scale by the calibre. Changing the calibre (size or scale) of the boxes in a grid is the way of approximating scaling in box counting. These are the essential points you need to know.
Before scanning an image, FracLac calculates the calibres or sizes of boxes in the grids it is going to use. To learn to do this now, jump to the practical use section where it tells how to set the sizes.
Scaling
Fixed Grid Sampling
The sampling illustrated at the top of this page used a fixed grid, meaning the image was sampled by dividing it into a regular array of non-overlapping boxes (a grid) for each box size. The figure below shows fixed grid sampling again, this time for a binary image of a diffusion limited aggregate scanned using 3 calibres, in order to highlight how the count changes with calibre. The calibres are listed in pixels, and the numbers, N, are the counts, meaning the number of boxes that had foreground pixels in them.
Change in Count with Change in Calibre in Fixed Grid Sampling
 |
Calibre 11 (N=84) |
 |
Calibre 14 (N=48) |
 |
Calibre 22 (N=24) |
Regression
The image below graphs the relationship between size and count from the images above. It also shows the fractal dimension, 1.77, determined from the data using the method alluded to in the opening sections of this page.
Deriving the Fractal Dimension From the log-log Regression Line
The fractal dimension for the above images is inferred from the relationship between size and count. The value, 1.77, was determined as the slope of the regression line for log N (count) vs log ε (calibre).
Arbitrary Scaling
Count
As you noticed above, with each change in grid calibre, the number of boxes in a grid, the area sampled by any box, and the count changed. In general, for binary images, the count is the number of boxes that had any foreground pixels in them. This is the measure that changes with scale. It is considered a proxy for detail, akin to the number of boxes required to cover an image or the number of scaled parts in an image, and is what FracLac uses to calculate the Dʙ for binary scans. In addition to the count of boxes, FracLac uses the pixels per box, in this case for calculating the Dʍ and lacunarity.
Determining Scaling
So, how N or the count is obtained is simple enough. But how does FracLac know what scaling to use? For canonical fractal patterns, the scaling is generally known ahead of time. But this is not usually so, and indeed when we do fractal analysis we are interested in finding scaling, because the change in count is not necessarily easy to predict from knowing the change in size or scale, ε. This is especially important because the count and mass used to approximate a DF vary with the series of sizes used to sample an image in box counting. Fortunately, there are many arbitrary scaling plans (e.g., linear, power, relative) for making a series of box sizes, and there are also options to filter the data in order to optimize sampling and find the most efficient series for each image.
Other Sampling Issues
Whereas this page so far has probably told you all you need to know to understand how box counting can be used to find box counting fractal dimensions for binary images, it has not touched on certain key points you should know when you are doing box counting with FracLac. These key points are all exceptions to or variations of the standard box counting technique.
Grid Location
Not only grid calibre, but also grid position and rotation can affect the count. This section discusses grid position in fixed grid scans; the next section talks about sliding grids.
Difference in Count With Grid Position
In this example, it takes 12 green versus 14 yellow boxes to cover the same image with the same calibre of grid when it is laid at different locations.
To understand the effect of grid position, consider again the binary diffusion limited aggregate image we saw above. You can see in the illustration here, which shows two identical copies of that image, that even though both the grid calibres and foreground pixels are identical in both pictures, the number of boxes within a grid needed to cover the foreground pixels is different. It depends on where the grid is positioned. As a corollary, the distribution of pixels counted, used in mass scans, also depends on grid orientation.
Difference in Box Counting Dimension With Rotation
Image rotation also affects the count. FracLac calculates dimensions using multiple rotations as well as grid locations.
Averages and Filters
To account for this variation, FracLac tests the set of grid calibres from many orientations and calculates fractal dimensions by transforming the data from those positions.
FracLac reports two basic kinds of average results based on many origins and rotations. Dʙavg, the average of all Dʙs over all grid orientations, and Davg, an average computed by compiling all of the counts at a calibre into one number then assessing that number against calibre to find the fractal dimension as the log-log slope.
In addition, FracLac reports results based on multiple origins that find the minimum cover and smoothed dimensions.
Mass Dimensions
The number of pixels or "mass" in each box also changes with grid calibre. FracLac uses the mean mass, the average number of foreground pixels per box at any particular size, for calculating a different type of fractal dimension known as a mass dimension, lacunarity, sliding box lacunarity, and multifractality.
Grayscale Images
The box count described above is applicable to binary images but box counting is done differently in some respects for grayscale images. In particular, the "count" that changes for grayscale images is the average intensity of pixels per box. Thus, in grayscale scans, the sampling method changes to measure this value. FracLac calculates the grayscale fractal dimension or DBGray from the relationship between the change in average intensity and the change in grid calibre.
Sliding Scans
In addition to fixed grid box counting, FracLac does sliding grid scanning to calculate an image feature called sliding box lacunarity (which you might see as Sλ, SΛ, SLacunarity, SLAC, or SLac, all referring to variations of one type of lacunarity).
The fractal dimension reported during sliding box lacunarity scans is the slope of the ln-ln regression line from the average pixels per box and calibre or ε (its r² is also reported). This DF will generally be different from a regular Dʙ, because of differences in sampling using sliding box scanning.
Essentials of Sliding Scans
Sliding vs Fixed Scanning
 |
 |
Sliding scans (left) overlap; fixed scans (right) do not. The two animations here illustrate how a fixed scan can cover an entire image with multiple grid sizes before a sliding scan is done with even one calibre.
The essential feature of a sliding scan is that
one sampling unit
moves over the image, overlapping itself at each slide.
The distance slid is an
option the user sets.
If the
distances to slide
horizontally and vertically are
set equal to a
calibre,
then the results for that calibre would be essentially a
fixed scan.
One consequence of sliding distances that are less than
the size of a
grid calibre is that,
compared to a fixed scan, a sliding scan is considerably slower.
The same box was laid over the image for the sliding scan (top of the figure) and the fixed scan (bottom), and traced at each location, to highlight the overlap in a sliding scan and the lack of it in the fixed.
The figure comparing methods illustrates how all that sliding would look if we drew the box at each location and left it there.
Resampling and Data
Another consequence of a sliding scan method is that there is a notable difference in the data obtained compared to fixed scan methods. As can be seen in the image comparing scanning methods, in a regular fixed scan, each part of an image is sampled only once by any particular box size in a series of grid calibres, but in the sliding scan, parts of the image can be re-sampled multiple times by one box size.
When many calibres of grids are used, the difference in sampling becomes even more meaningful. To delve into this concept, look at the image of a scaled version of an 8-segment quadric fractal shown here (DF = 1.50), along with a part of it zoomed in.
The zoomed in part shows the detail as we look at how sampling is different between fixed and sliding scans using a series of grid sizes.
Re-sampling in sliding scans dramatically increases the time to scan as noted earlier, but also affects the data gathered, especially as calibre increases. Accordingly, rather than the count or number of boxes, the average pixels per box is used in the calculations from overlapping scans.
The images below illustrate this difference in sampling. Below are 3 pairs of grid images made from the original image shown above. The left side of each pair is made from a sliding scan and the right from a fixed scan. The boxes that contained foreground pixels for each type of scan at the same grid calibre are drawn in cyan on each image in the pair. The top two images show the part corresponding to the zoomed in part above.
Grid Calibre = 2 pixels
Grid Calibre = 4 pixels over the same part of the image.
Grid Calibre = 26 pixels over the entire image. At this large calibre, the boxes drawn on the sliding scan overlap so much that they obscure the pattern beneath, whereas it is barely covered and easy to see in the image of boxes drawn on the fixed scan.
Connected Set Scanning
Local Connected Fractal Dimension
FracLac also samples images to find the local connected fractal dimension (abbreviated Dʟᴄ for the dimension itself, and LCFD for the type of scan). FracLac calculates the Dʟᴄ for binary images only, sampling pixel by pixel, finding a local connected set around each pixel.
Finding the Connected Set
The basic rule for finding the connected set is that all foreground pixels that are in the 8x8 environment of a seed pixel are considered connected. This basic rule is applied to find the connected set for some predetermined arbitrary distance around a starting pixel (the arbitrary distance is a user setting).
Grid Drawings for Local Connected Set Scans
A series of changing calibres is centred, one by one, on a starting pixel, and the number of foreground pixels that were in the connected set is counted for each calibre for each starting pixel.
The rule for data gathering is based on this
connected set rather than the image at large. The actual data
gathering uses fixed boxes, but not in the same way as for a
standard box count, but
rather, as is illustrated in the figure above.
Because they are centred
on a pixel, for consistency in the sampling area,
the sizes in a Dʟᴄ scan should be
odd numbers. The default
for Dʟᴄ scans is an odd series.
There is also
an option to use circles
as shown in the figure, which was generated as an
optional part of the
Dʟᴄ scan.
With this method of sampling, the count of boxes at any size is always 1, so the mass of pixels rather than the count of boxes is used in the regression equation to determine the Dʟᴄ.
Visuals for LCFD Scans
One binary image scanned once, but colour-coded multiple times to highlight different types of local variations.
An important part of Dʟᴄ analysis is the potential for visual presentation (see Landini at http://www.iovs.org/content/36/13/2749.abstract Invest. Ophthalmol. Vis. Sci. December 1995 vol. 36 no. 13 2749-2755). This type of analysis can be used in diagnostics, for instance, where "hot spots" need to be detected and located with the same area being differentiated for multiple features.
Mass vs Distance Scanning
Another type of sampling FracLac does is Mass vs Distance sampling. This involves counting the pixels within concentric squares or ovals centered on a point. The animation below illustrates the basic sampling strategy. See the Box Counting Options for details of how to set up Mass vs Distance scans.
Mass vs Distance sampling using an oval sampling unit. The left shows starting from a seed and the right starting with no seed (using the centre of the image).
Block Texture Analysis
FracLac also does block texture analyses for sliding box lacunarity and standard box counts. These scans assume a texture is consistent over an image, and use a special algorithm that samples the inner part of an image as a large block, calculating the grid calibres so they avoid edge effects.
Block Texture Analysis of an Image as Binary and Grayscale
Intro to Local Dimension Sub Scans
FracLac calculates local Dʙs for subareas of an image. In these cases, the sample is different to start with - rather than scanning the image as a whole, parts are analyzed individually. But the actual scanning method is otherwise the same as for regular fixed grid box counting.
Particle Analyzer Scans
In Particle Analyzer scans, portions of an image are automatically selected using ImageJ's particle analyzer. The image here, for instance, shows the results of a single scan of an image containing multiple cells, where each cell was automatically selected, analyzed, and displayed colour-coded according to its calculated Dʙ.
Particle Analyzer Scan
Each cell in the image was automatically selected, analyzed, and colour-coded.
Rectangular Array and Random Scans
In this sub scan type,
images are divided into a non-overlapping
rectangular array
from which image blocks are
selected systematically, or
image blocks are selected randomly,
depending on the
sampling method selected.
The sample image blocks can be rectangular or oval.
For further discussion, see the
Sub scans page.
Regular Array Sub Scans
The image illustrates graphics generated from a rectangular array sub scan using oval and rectangular samples.
HOME