PaperlayerView exact revision on arXiv

Source-linked AI summary

FellWalker - a Clump Identification Algorithm

David Berry

arXiv:1411.6267v1astro-ph.IM

TL;DR

CLUMPFIND’s contour interval can make clump identification sensitive to parameter settings, while most data values do not lie on its contours. FellWalker traces uphill paths from above-threshold pixels to peaks, and comparisons report more consistent clump data sums and lower parameter sensitivity than CLUMPFIND. Its current implementation can jump between islands and merge distinct clumps.

  • Problem

    CLUMPFIND’s decomposition can be sensitive to its contour interval, which may miss real peaks when large or interpret noise spikes as peaks when small.

    Source: §1 · p. 1

  • Method

    FellWalker assigns above-threshold pixels to clumps by tracing paths of steepest ascent until they reach significant summits.

    Source: §2 · p. 2, §2.1 · p. 2

  • Results

    FellWalker is less sensitive to parameter settings and more reliable at reproducing expected clump data sums than CLUMPFIND in the reported comparisons.

    Source: §3.6 · p. 8, §3.5 · p. 8

  • Takeaways & Limitations

    The comparisons support using FellWalker when reproducing expected clump data sums with less dependence on parameter settings is important.

    Source: §3.6 · p. 8

    A walk can jump to a higher pixel on another island, potentially merging clumps that are distinct.

    Source: §4 · p. 10

Abstract

from arXiv · show

This paper describes the FellWalker algorithm, a watershed algorithm that segments a 1-, 2- or 3-dimensional array of data values into a set of disjoint clumps of emission, each containing a single significant peak. Pixels below a nominated constant data level are assumed to be background pixels and are not assigned to any clump. FellWalker is thus equivalent in purpose to the CLUMPFIND algorithm. However, unlike CLUMPFIND, which segments the array on the basis of a set of evenly-spaced contours and thus uses only a small fraction of the available data values, the FellWalker algorithm is based on a gradient-tracing scheme which uses all available data values. Comparisons of CLUMPFIND and FellWalker using a crowded field of artificial Gaussian clumps, all of equal peak value and width, suggest that the results produced by FellWalker are less dependent on specific parameter settings than are those of CLUMPFIND.

1. Introduction

CLUMPFIND decomposes emission data into disjoint, single-peak clumps using evenly spaced contours, but its results can be sensitive to the contour interval. FellWalker instead traces uphill paths using all data values above a threshold; its scope remains disjoint clumps, not overlapping or hierarchical structures.

1. Introduction

  • CLUMPFIND’s contour interval can make its decomposition sensitive: large intervals may miss real peaks, while small ones may treat noise spikes as peaks.Most pixel values fall between the contours and do not affect the decomposition.Source: §1 · p. 1
  • FellWalker uses all available pixel values above a stated threshold, rather than relying on the small fraction that fall on CLUMPFIND’s contour levels.It follows an upward path from a low-valued pixel to a significant summit.Source: §1 · p. 1
  • FellWalker is a watershed algorithm that associates each segment with a local maximum rather than a low-lying catchment basin.It shares features with HOP but is designed for gridded observational data rather than particles in an N-body simulation.Source: §1 · p. 1
  • FellWalker is available in the Starlink CUPID package alongside GaussClumps and CLUMPFIND.CUPID is open-source; FITS data can be handled through the Starlink CONVERT package.Source: §1 · p. 2
  • FellWalker and CLUMPFIND produce disjoint, single-peak regions; overlapping clumps and cloud hierarchy are outside this paper’s comparison.The paper notes GaussClumps and dendrograms as alternative approaches for those cases.Source: §1 · p. 2

2. The FellWalker Algorithm

FellWalker assigns above-threshold pixels to clumps by tracing uphill walks to significant peaks, then can merge, smooth, and filter clumps before producing masks and statistics. Its peak search distinguishes local maxima from noise spikes by checking a larger neighborhood.

2.1. Identifying Raw Clumps

  • Above-threshold pixels follow steepest-ascent walks to significant peaks; walks that meet assigned pixels inherit their clump, while larger-neighborhood searches distinguish peaks from noise spikes.The algorithm records usable and unusable pixels in a clump assignment array; low-gradient initial walk segments can also be flagged unusable.Source: §2 · p. 2, §2.1 · pp. 2–3

2. The FellWalker Algorithm

  • The algorithm’s core is to trace many uphill paths, with subsequent merging and optional boundary smoothing addressing fragmentation and noise effects.It then characterizes the resulting clumps and creates a catalogue and pixel mask.Source: §2 · p. 2

2.2. Merging Clumps

  • MaxJump controls peak separation: larger jumps classify more local peaks as noise spikes, while shallow-valley merging can reunite adjacent clumps.Candidate clumps merge when a peak is less than MinDip above the intervening col; the process repeats until no further merges are possible.Source: §2.2 · p. 3

2.3. Cleaning Clump Outlines

  • Optional cellular-automaton steps smooth clump boundaries by assigning each pixel the most common clump index in its 3-pixel neighborhood.The default is one step; smoothing can have a more pronounced effect on real data than on the smooth artificial example.Source: §2.3 · p. 4, Figure 6 · p. 5

2.4. Removing Unusable Clumps

  • Clumps can be excluded for touching array edges or missing pixels, having too little peak intensity, or containing too few pixels; rejection counts are reported.Source: §2.4 · p. 4

2.5. Characterising Each Clump

  • FellWalker outputs a clump mask, per-clump cut-outs, and a table of peak and centroid positions, sizes, sums, peaks, volumes, and optional spatial shapes.Sizes are intensity-above-background-weighted RMS deviations from the centroid and equal Gaussian standard deviations for Gaussian profiles; optional beam correction requires a known beam size.Source: §2.5 · p. 5

3. Comparing FellWalker and CLUMPFIND

In artificial-clump tests, FellWalker produced more consistent clump sums across parameter settings, while CLUMPFIND’s results varied with its contour interval. The methods also showed different segmentation errors, and CLUMPFIND continued to fragment clump edges at lower noise.

3. Comparing FellWalker and CLUMPFIND

  • At lower noise, CLUMPFIND still fragmented clump edges, while the interiors of clumps were largely unfragmented.Watson (2010) likewise found FellWalker less likely than CLUMPFIND to split large clumps or create false detections under that study’s conditions. For known Gaussian merged sources, Gaussian-model methods provide better decomposition than either method, though real-source shapes are generally unknown.Source: §3 · p. 6
  • In Figure 7’s noisy field, FellWalker detected 133 clumps versus CLUMPFIND’s 1239; CLUMPFIND fragmented sources, while FellWalker possibly missed visible clumps.The input was a 500 × 500 image of 200 Gaussian clumps with added noise.Source: Figure 7 · p. 6, §3 · p. 6

3.1. The Artificial Data

  • Tests used 500 × 500 images of 200 randomly positioned Gaussian clumps, each with peak 100 and FWHM 15 pixels, across eight noise levels from 2 to 16.Source: §3.1 · p. 7

3.2. The Clump-finding Parameters

  • Tests varied CLUMPFIND DeltaT from 20 to 1 times noise, FellWalker MaxJump from 2 to 14 pixels and MinDip from 0 to 5 times noise, fixing the shared cutoff at 2 times noise.CLUMPFIND enhancements disabled by default in CUPID were enabled for the comparison.Source: §3.2 · p. 7

3.3. Measuring Performance

  • Performance was measured by median gain: measured clump sum divided by the artificial source’s sum above the 2-sigma cutoff, limiting overlap-tail effects and accounting for threshold losses.Source: §3 · p. 6, §3.3 · pp. 7–8

3.4. CLUMPFIND Results

  • CLUMPFIND typically reached unit median gain near DeltaT=10 times the noise, but gain varied unpredictably with DeltaT and RMS; at recommended DeltaT=2, all noise levels were below expectation.Source: Figure 10 · p. 8, §3.4 · p. 8

3.5. FellWalker Results

  • FellWalker’s median clump sums were much more consistent and closer to expected sums across tested MaxJump/MinDip values and noise levels.Source: §3.5 · p. 8

CLUMPFIND.

FellWalker’s clump-sum results are less sensitive to parameter settings than CLUMPFIND’s in the 3D tests, though MaxJump matters more in 3D. FellWalker also runs faster than both CUPID and IDL implementations of CLUMPFIND.

CLUMPFIND.

  • In 2D, small MaxJump and MinDip split clumps into fragments, while large MaxJump can merge real peaks, especially at larger MinDip.Between these extremes, MaxJump 4–10 and MinDip 0–4 times the noise level produce predictable gain values close to unity.Source: CLUMPFIND · p. 8

3.6. Comparisons Using Three-Dimensional Data

  • The 3D tests used 200 × 200 × 200-pixel cubes containing 600 artificial Gaussian clumps, each 10 pixels wide and with peak value 100.The tests otherwise used the same procedure and parameter ranges as the 2D tests.Source: §3.6 · p. 8
  • In 3D tests, FellWalker is less sensitive to parameter settings and more reliable at reproducing expected clump data sums than CLUMPFIND.CLUMPFIND is very sensitive to DeltaT; its recommended DeltaT of 2∗RMS splits clumps into pieces with smaller-than-expected data sums.Source: §3.6 · p. 8
  • In 3D, FellWalker is more sensitive to MaxJump; best results use MinDip between 1.0 and 3.0 and MaxJump below 8.CUPID’s defaults are MinDip 2.0 and MaxJump 4.Source: §3.6 · p. 8

3.7. Execution Times

  • For both 2D and 3D data, FellWalker is 1–2 orders of magnitude faster than CUPID CLUMPFIND, which is about an order faster than IDL CLUMPFIND.CUPID uses single-threaded implementations of all clump-finding algorithms.Source: §3.7 · p. 8

4. Future Enhancements to FellWalker

The paper identifies two issues in the current FellWalker implementation for future work: cleaning can split some clumps, and the higher-pixel search can jump between islands and merge distinct clumps.

4. Future Enhancements to FellWalker

  • Cleaning can split dog-bone-shaped clumps with a narrow, steep-sided central ridge into discontiguous parts by eroding pixels from the ridge.The gap can separate the two wider end regions.Source: §4 · p. 10
  • The higher-pixel search near a local maximum does not check whether the higher pixel lies on the same island, so walks can merge distinct clumps.Source: §4 · p. 10

Appendix A. Configuration Parameter Values

The appendix describes the CUPID commands and configuration files used for the 2D tests.

Appendix A. Configuration Parameter Values

  • The 2D tests varied rms, maxjump, mindip, and deltat; data.sdf is the input, mask.sdf the generated clump-pixel mask, and cat.fit the generated catalogue.The appendix refers readers to the CUPID documentation for command and parameter descriptions.Source: Appendix A · p. 10

Appendix A.1. FellWalker

The FellWalker configuration example specifies output files and a configuration string.

Appendix A.1. FellWalker

  • The example command writes a clump mask and catalogue and supplies a FellWalker configuration string.Source: Appendix A.1 · p. 10

Appendix A.2. ClumpFind

Appendix A.2 lists the ClumpFind command configuration and parameter settings, including a change to the axis setting for 3-dimensional tests.

Appendix A.2. ClumpFind

  • The listed command writes mask.sdf and cat.fit and uses the specified RMS-based configuration with backoff enabled.Source: Appendix A.2 · p. 11
  • ClumpFind is configured with Minpix=16, Tlow=2*RMS, Naxis=2, and the listed edge, beam, IDL algorithm, bad-pixel, and velocity-resolution settings.Source: Appendix A.2 · p. 11
  • For the 3-dimensional tests, ClumpFind.Naxis was changed from 2 to 3.Source: Appendix A.2 · p. 11
Loading 1411.6267v1…