Content deleted Content added
→References: formatting list of references |
GreenC bot (talk | contribs) Move 1 url. Wayback Medic 2.5 per WP:URLREQ#nih.gov |
||
| (40 intermediate revisions by 26 users not shown) | |||
Line 1:
{{Short description|Fractal analysis technique}}
{{Anchor|32seg}}[[Image:32 segment fractal.jpg|thumb|left|400px|Figure 1. A 32-segment [[fractal#iterated|quadric fractal]] viewed through "boxes" of different sizes. The pattern illustrates [[self similarity]].]]▼
{{Use American English|date = January 2019}}
▲{{Anchor|32seg}}[[Image:32 segment fractal.jpg|thumb|
'''Box counting''' is a method of gathering [[#data|data]] for analyzing [[complex systems|complex patterns]] by breaking a [[Data set|dataset]], object, image, etc. into smaller and smaller pieces, typically "box"-shaped, and analyzing the pieces at each smaller scale. The essence of the process has been compared to zooming in or out using optical or computer based methods to examine how observations of detail change with scale. In box counting, however, rather than changing the magnification or resolution of a lens, the investigator changes the [[#boxsize|size of the element]] used to inspect the object or pattern (see [[#32seg|Figure 1]]). Computer based box counting algorithms have been applied to patterns in 1-, 2-, and 3-dimensional spaces.<ref>{{
== The method ==
Theoretically, the intent of box counting is to quantify [[fractal]] scaling, but from a practical perspective this would require that the scaling be known ahead of time. This can be seen in [[#32seg|Figure 1]] where choosing boxes of the right relative sizes readily shows how the pattern repeats itself at smaller scales. In fractal analysis, however, the scaling factor is not always known ahead of time, so box counting algorithms attempt to find an optimized way of cutting a pattern up that will reveal the scaling factor. The fundamental method for doing this starts with a
{{anchor|extracting patterns}}[[Image:Binarizing neuron image.
{{anchor|data}}
=== The data ===
The relevant features gathered during box counting depend on the subject being investigated and the type of analysis being done. Two well-studied subjects of box counting, for instance, are binary (meaning having only two colours, usually black and white)<ref name="smith"/> and gray-scale<ref name="gray">{{
| last1 = Karperien | first1 = Audrey
| last2 = Jelinek | first2 = Herbert F.
| last3 = Leandro | first3 = Jorge de Jesus Gomes
| last4 = Soares | first4 = João V. B.
| last5 = Cesar Jr | first5 = Roberto M.
| last6 = Luckie | first6 = Alan
| title = Automated detection of proliferative retinopathy in clinical practice
| journal = Clinical Ophthalmology
| volume = 2
| issue = 1
| pages = 109–122
| year = 2008
| pmid = 19668394
| pmc = 2698675
| doi = 10.2147/OPTH.S1579
| doi-access = free
}}</ref><ref name="landini"/><ref name="mf"/>
=== Scan types ===
{{anchor|scan}}Every box counting algorithm has a scanning plan that describes how the data will be gathered, in essence, how the box will be moved over the space containing the pattern. A variety of scanning strategies has been used in box counting algorithms, where a few basic approaches have been modified in order to address issues such as sampling, analysis methods, etc.
{{Anchor|scanimages}}[[Image:Fixedstack.gif|thumb|left|400px|Figure 2a. Boxes laid over an image as a fixed grid.
[[Image:Slidestack.gif|thumb|left|400px|Figure 2b. Boxes slid over an image in an overlapping pattern.]]
[[Image:lcfd.gif|thumb|left|400px|Figure 2c. Boxes laid over an image concentrically focused on each pixel of interest.]] ]]
{{anchor|retina}}[[Image:Retina lcfd.gif|thumb|right|200px|Figure 3. Retinal vasculature revealed through box counting analysis; colour
{{anchor|grids}}[[Image:optimal covering grids.png|thumb|right|200px|Figure 4. It takes 12 green but 14 yellow boxes to completely cover the black pixels in these identical images. The difference is attributable to the position of the grid, illustrating the importance of grid placement in box counting.]]
==== Fixed grid scans ====
The traditional approach is to scan in a non-overlapping regular grid or lattice pattern.<ref name="mandelbrot"/><ref name="fil"/> To illustrate, [[#scanimages|Figure 2]]a shows the typical pattern used in software that calculates box counting dimensions from patterns extracted into binary digital images of contours such as the fractal contour illustrated in [[#32seg|Figure 1]] or the classic example of the coastline of Britain often used to explain the method of finding a [[box counting dimension]]. The strategy simulates repeatedly laying a square box as though it were part of a grid overlaid on the image, such that the box for each <math>\epsilon</math> never overlaps where it has previously been (see [[#grids|Figure 4
<ref>{{
==== Sliding box scans ====
Another approach that has been used is a sliding box algorithm, in which each box is slid over the image overlapping the previous placement. [[#scanimages|Figure 2]]b illustrates the basic pattern of scanning using a sliding box. The fixed grid approach can be seen as a sliding box algorithm with the increments horizontally and vertically equal to <math>\epsilon</math>. Sliding box algorithms are often used for analyzing textures in [[lacunarity]] analysis and have also been applied to [[multifractal analysis]].<ref name="
| last1 = Plotnick | first1 = R. E.
| last2 = Gardner | first2 = R. H.
| last3 = Hargrove | first3 = W. W.
| last4 = Prestegaard | first4 = K.
| last5 = Perlmutter | first5 = M.
| title = Lacunarity analysis: A general technique for the analysis of spatial patterns
| journal = Physical Review E
| volume = 53
| issue = 5
| pages = 5461–5468
| year = 1996
| pmid = 9964879 | doi=10.1103/physreve.53.5461
| bibcode = 1996PhRvE..53.5461P
}}</ref><ref name="plotnick">{{Cite journal | last1 = Plotnick | first1 = R. E. | last2 = Gardner | first2 = R. H. | last3 = O'Neill | first3 = R. V. | doi = 10.1007/BF00125351 | title = Lacunarity indices as measures of landscape texture | journal = Landscape Ecology | volume = 8 | issue = 3 | pages = 201–211 | year = 1993 | s2cid = 7112365 }}</ref><ref name="wiens">{{Cite journal | last1 = McIntyre | first1 = N. E. | last2 = Wiens | first2 = J. A. | journal = Landscape Ecology | volume = 15 |title=A novel use of the lacunarity index to discern landscape function| issue = 4 | pages = 313–321 | year = 2000 | doi = 10.1023/A:1008148514268 | s2cid = 18644861 }}</ref>
==== Subsampling and local dimensions ====
Box counting may also be used to determine local variation as opposed to global measures describing an entire pattern. Local variation can be assessed after the data have been gathered and analyzed (e.g., some software colour codes areas according to the fractal dimension for each subsample), but a third approach to box counting is to move the box according to some feature related to the pixels of interest. In [[local connected dimension]] box counting algorithms, for instance, the box for each <math>\epsilon</math> is centred on each pixel of interest, as illustrated in [[#scanimages|Figure 2]]c.<ref name="landini">{{
| last1 = Landini | first1 = G.
| last2 = Murray | first2 = P. I.
| last3 = Misson | first3 = G. P.
| title = Local connected fractal dimensions and lacunarity analyses of 60 degrees fluorescein angiograms
| journal = Investigative Ophthalmology & Visual Science
| volume = 36
| issue = 13
| pages = 2749–2755
| year = 1995
| pmid = 7499097
}}</ref>
== Methodological considerations ==
The implementation of any box counting algorithm has to specify certain details such as how to determine the actual values in <math>\Epsilon</math>, including the minimum and maximum sizes to use and the method of incrementing between sizes. Many such details reflect practical matters such as the size of a digital image but also technical issues related to the specific analysis that will be performed on the data. {{anchor| optimal covering}}Another issue that has received considerable attention is how to approximate the so-called "optimal covering" for determining [[box counting dimension]]s and assessing [[multifractal analysis|multifractal scaling]].<ref name="gray"/><ref>{{
| last1 = Chhabra | first1 = A.
| last2 = Jensen | first2 = R. V.
| title = Direct determination of the f( alpha ) singularity spectrum
| journal = Physical Review Letters
| volume = 62
| issue = 12
| pages = 1327–1330
| year = 1989
| pmid = 10039645
| doi=10.1103/PhysRevLett.62.1327
| bibcode = 1989PhRvL..62.1327C
}}</ref><ref name="neurons">{{Cite journal
| last1 = Fernández | first1 = E.
| last2 = Bolea | first2 = J. A.
| last3 = Ortega | first3 = G.
| last4 = Louis | first4 = E.
| title = Are neurons multifractals?
| journal = Journal of Neuroscience Methods
| volume = 89
| issue = 2
| pages = 151–157
| year = 1999
| pmid = 10491946 | doi=10.1016/s0165-0270(99)00066-7
| s2cid = 31745811
}}</ref>
=== Edge effects ===
One known issue in this respect is deciding what constitutes the edge of the useful information in a digital image, as the limits employed in the box counting strategy can affect the data gathered.
=== Scaling box size ===
The algorithm has to specify the type of increment to use between box sizes (e.g., linear vs exponential), which can have a profound effect on the results of a scan.
=== Grid orientation ===
As [[#grids|Figure 4]] illustrates, the overall positioning of the boxes also influences the results of a box count. One approach in this respect is to scan from multiple orientations and use averaged or optimized data.<ref>{{cite book|author=Karperien|title=Defining Microglial Morphology: Form, Function, and Fractal Dimension|
To address various methodological considerations, some software is written so users can specify many such details, and some includes methods such as smoothing the data after the fact to be more amenable to the type of analysis being done.<ref>{{citation |author=Karperien|
== See also ==
* [[Fractal analysis]]
* [[Fractal dimension]]
* [[Minkowski–Bouligand dimension]]
* [[Multifractal]] analysis
* [[Lacunarity]]
== References ==
{{Reflist|2}}
{{Fractals|state=collapsed}}
[[Category:Fractals]]
[[Category:Dimension theory]]
| |||