next up previous
Next: Objectives/Overview Up: Parallel Hoshen-Kopelman Algorithm Title Page Previous: Abstract


In landscape ecology, computer modeling can be used to assess habitat fragmentation, the migration patterns of individuals or groups of competing animal species, and the impact of human activities on ecosystems. In such applications, the primary data structure used within spatially explicit landscape models are maps (2-dimensional grids). These maps typically reflect habitat clusters or patches that can be analyzed to determine their numbers, sizes, and geometries. A core function of map analysis is cluster identification---a process by which individual pixels (or cells) in a map that have been grouped in the same map class are given the same cluster label.

Cluster identification algorithms (Zallen, 1983) (Stauffer, 1985), (Orbach, 1986) can be classified by their approach to pixel labeling as holistic or aggregate. Holistic-type algorithms find every pixel belonging to a particular cluster before analyzing the next cluster. These algorithms can be implemented either recursively or by using a working set to maintain a list of candidate pixels. In a working set implementation, each candidate pixel on the list is labeled and in turn, each of the pixel's neighbors is analyzed. If a neighboring pixel is in the same cluster and is currently unlabeled, the pixel is added to the list. This process continues until the list is exhausted and all pixels belonging to the cluster have been properly labeled.

In a recursive implementation, the original call to the cluster identification function (CIF) will accept a pointer to the first candidate pixel and will correctly label the pixel and its North-East-West-South (NEWS) neighbors. The CIF function labels the NEWS neighbors by issuing recursive calls to itself, one for each of the NEWS neighbors that are in the current map class (pixel type) and have not already been labeled. When the original call to the CIF returns, the entire cluster will have been correctly labeled. The process is repeated for each unique cluster found in the input map.

A recursive implementation requires the entire cluster to be in memory and large amounts of memory to store the execution stack during the recursion. Such memory requirements make this approach impractical for large dense maps. Aggregate-type algorithms traverse a map assigning pixels to temporary clusters and apply merge rules when two temporary clusters overlap. Aggregate-type algorithms are not subject to the high memory requirements of the recursive algorithms and are better suited for cluster identification on large, dense maps. The Hoshen-Kopelman (Hoshen and Kopelman, 1976) cluster identification algorithm is an aggregate-type algorithm.

next up previous
Next: Objectives/Overview Up: Parallel Hoshen-Kopelman Algorithm Title Previous: Abstract

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996