Search

In this paper we discuss several heuristic strategies which allow one to solve the Whitehead's minimization problem much faster (on most inputs) than the classical Whitehead algorithm. The mere fact that these strategies work in practice leads to several interesting mathematical conjectures. In particular, we conjecture that the length of most non-minimal elements in a free group can be reduced by a Nielsen automorphism which can be identified by inspecting the structure of the corresponding Whitehead Graph.

The Whitehead Minimization problem is a problem of finding elements of the minimal length in the automorphic orbit of a given element of a free group. The classical algorithm of Whitehead that solves the problem depends exponentially on the group rank. Moreover, it can be easily shown that exponential blowout occurs when a word of minimal length has been reached and, therefore, is inevitable except for some trivial cases. In this paper we introduce a deterministic Hybrid search algorithm and its stochastic variation for solving the Whitehead minimization problem. Both algorithms use search heuristics that allow one to find a length-reducing automorphism in polynomial time on most inputs and significantly improve the reduction procedure. The stochastic version of the algorithm employs a probabilistic system that decides in polynomial time whether or not a word is minimal. The stochastic algorithm is very robust. It has never happened that a non-minimal element has been claimed to be minimal.

In LANDSAT imagery, spectral and spatial information can be used to detect the drainage network as well as the relative elevation model in mountainous terrain. To do this, mixed information of material reflectance in the original LANDSAT imagery must be separated. From the material reflectance information, big visible rivers can be detected. From the topographic modulation information, ridges and valleys can be detected and assigned relative elevations. A complete elevation model can be generated by interpolating values for nonridge and non-valley pixels. The small streams not detectable from material reflectance information can be located in the valleys with flow direction known from the elevation model. Finally, the flow directions of big visible rivers can be inferred by solving a consistent labeling problem based on a set of spatial reasoning constraints.

In LANDSAT imagery, spectral and spatial information can be used to detect the drainage network as well as the relative elevation model in mountainous terrain. To do this, the mixed information of material reflectance and topographic modulation in the original LANDSAT imagery must be first separated. From the material reflectance information, big visible rivers can be detected. From the topographic modulation information, ridges and valleys can be detected and assigned relative elevations. Finally, a relative elevation model can be generated by interpolating values for nonridge and nonvalley pixels.

The facet model was used to accomplish step edge detection. The essence of the facet model is that any analysis made on the basis of the pixel values in some neighborhood has its final authoritative interpretation relative to the underlying grey tone intensity surface of which the neighborhood pixel values are observed noisy samples. Pixels which are part of regions have simple grey tone intensity surfaces over their areas. Pixels which have an edge in them have complex grey tone intensity surfaces over their areas. Specially, an edge moves through a pixel only if there is some point in the pixel's area having a zero crossing of the second directional derivative taken in the direction of a non-zero gradient at the pixel's center. To determine whether or not a pixel should be marked as a step edge pixel, its underlying grey tone intensity surface was estimated on the basis of the pixels in its neighborhood.

The methodologies and capabilities of image segmentation techniques are reviewed. Single linkage schemes, hybrid linkage schemes, centroid linkage schemes, histogram mode seeking, spatial clustering, and split and merge schemes are addressed.

Photointerpreters employ a variety of implicit spatial models to provide interpretations from remotely sensed aerial or satellite imagery. In this paper one application is illustrated: how ridges and valleys can be automatically interpreted from Landsat imagery of a mountainous area, and how a relative elevation terrain model can be constructed from this interpretation. How to examine valleys for the possible presence of streams or rivers is shown, and how a spatial relational model can be set up to make a final interpretation of the river drainage network is explored.

There are no author-identified significant results in this report.

The author has identified the following significant results. A procedure was developed to extract cross-band textural features from ERTS MSS imagery. Evolving from a single image texture extraction procedure which uses spatial dependence matrices to measure relative co-occurrence of nearest neighbor grey tones, the cross-band texture procedure uses the distribution of neighboring grey tone N-tuple differences to measure the spatial interrelationships, or co-occurrences, of the grey tone N-tuples present in a texture pattern. In both procedures, texture is characterized in such a way as to be invariant under linear grey tone transformations. However, the cross-band procedure complements the single image procedure by extracting texture information and spectral information contained in ERTS multi-images. Classification experiments show that when used alone, without spectral processing, the cross-band texture procedure extracts more information than the single image texture analysis. Results show an improvement in average correct classification from 86.2% to 88.8% for ERTS image no. 1021-16333 with the cross-band texture procedure. However, when used together with spectral features, the single image texture plus spectral features perform better than the cross-band texture plus spectral features, with an average correct classification of 93.8% and 91.6%, respectively.

The author has identified the following significant results. The phenological method of crop identification involves the creation of crop signatures which characterize multispectral observations as phenological growth states. The phenological signature models spectral reflectance explicitly as a function of crop maturity rather than as a function of date. A correspondence of time to growth state is established which minimizes the smallest difference between the given multispectral multitemporal vector and a category mean vector. The application of the method to the identification of winter wheat and corn shows (1) the method is capable of discriminating crop type with about the same degree of accuracy as more traditional classifiers; (2) the use of LANDSAT observations on two or more dates yields better results than the use of a single observation; and (3) some potential is demonstrated for labeling the degree of maturity of the crop, as well as the crop type.

Thermal infrared imagery was used to locate ground-water inflow along three streams and one lake in Montana. The thermal scanner used in May 1972, March 1973, and November 1975 was mounted in a twin-engined aircraft. On the 1973 and 1975 flights, the data were recorded in an analog format on magnetic tape in flight, later were converted to digital format, and were computer processed using an assignment of patterns to indicate differences in water temperature. Output from the image processing program was converted to a temperature map having an isotherm spacing of 0.5 C. Computerization was found to be the most efficient method to manipulate data from lakes, large rivers, and narrow sinuous streams.

There are no author-identified significant results in this report.

A C-130 aircraft was flown over the Sam Houston National Forest on March 21, 1973 at 10,000 feet altitude to collect multispectral scanner (MSS) data. Existing textural and spatial automatic processing techniques were used to classify the MSS imagery into specified timber categories. Several classification experiments were performed on this data using features selected from the spectral bands and a textural transform band. The results indicate that (1) spatial post-processing a classified image can cut the classification error to 1/2 or 1/3 of its initial value, (2) spatial post-processing the classified image using combined spectral and textural features produces a resulting image with less error than post-processing a classified image using only spectral features and (3) classification without spatial post processing using the combined spectral textural features tends to produce about the same error rate as a classification without spatial post processing using only spectral features.

Two systems for processing remotely sensed image data have been discussed. The first system, IDECS, is a near real-time hardware system oriented towards processing multi-image data sets quickly and economically. The IDECS has convenient film input and color display output capabilities and implements simple kinds of decision rules. The second system, KANDIDATS, is a software system capable of performing many of the more sophisticated processing methods. Because of its monitor which handles all bookkeeping and its modular design, KANDIDATS easily allows the testing of new automatic processing techniques. After a new technique has been proven on KANDIDATS, it may be simplified and hard-wired in IDECS, thereby keeping the volume processing of remotely sensed data always up to the current state-of-the-art.

Iterative clustering technique for minimizing probability of differences between binary data reconstructions from cluster codes and initial data

Radar imagery for crop discrimination, discussing sensor and data requirements and statistical analysis methods

Adaptive pattern recognition by using predictive model in construction of similarity sets

A general procedure is presented for extracting textural properties of blocks of image data. These features are calculated in the spatial domain, taking into account the statistical nature of texture. The procedure is based on the assumption that the texture information in an image is contained in the overall or 'average' spatial relationship which the gray tones in the image have to one another. The spatial gray-tone dependence matrix is discussed together with the spectral features used in the study and the land use classification studies conducted. The results of the study show the usefulness of using both spectral and textural characteristics of ERTS multispectral scanner data for developing classification procedures.

A procedure is developed to simultaneously extract textural features from all bands of ERTS multispectral scanner imagery for automatic analysis. Multi-images lead to excessively large grey tone N-tuple co-occurrence matrices; therefore, neighboring grey N-tuple differences are measured and an ellipsoidally symmetric functional form is assumed for the co-occurrence distribution of multiimage greytone N-tuple differences. On the basis of past data the ellipsoidally symmetric approximation is shown to be reasonable. Initial evaluation of the procedure is encouraging.

The author has identified the following significant results. Improvement in the land use classification accuracy of ERTS-1 MSS multi-images over Kansas can be made using two distances between neighboring grey tone N-tuples instead of one distance. Much more information is contained texturally than spectrally on the Kansas image. Ground truth measurements indicate that reflectance ratios of the 545 and 655 nm wavebands provide an index of plant development and possibly physiological stress. Preliminary analysis of MSS 4 and 5 channels substantiate the ground truth interpretation. Results of the land use mapping experiment indicate that ERTS-1 imagery has major potential in regionalization. The ways in which land is utilized within these regions may then be studied more effectively than if no adequate regionalization is available. A model for estimating wheat yield per acre has been applied to acreage estimates derived from ERTS-1 imagery to project the 1973 wheat yields for a ten county area in southwest Kansas. The results are within 3% of the preharvest estimates for the same area prepared by the USDA. Visual identification of winter wheat is readily achieved by using a temporal sequence of images. Identification can be improve by stratifying the project area into subregions having more or less homogeneous agricultural practices and crop mixes.

Description of some easily computable textural features based on gray-tone spatial dependances, and illustration of their application in category-identification tasks of three different kinds of image data - namely, photomicrographs of five kinds of sandstones, 1:20,000 panchromatic aerial photographs of eight land-use categories, and ERTS multispectral imagery containing several land-use categories. Two kinds of decision rules are used - one for which the decision regions are convex polyhedra (a piecewise-linear decision rule), and one for which the decision regions are rectangular parallelpipeds (a min-max decision rule). In each experiment the data set was divided into two parts, a training set and a test set. Test set identification accuracy is 89% for the photomicrographs, 82% for the aerial photographic imagery, and 83% for the satellite imagery. These results indicate that the easily computable textural features probably have a general applicability for a wide variety of image-classification applications.

There are no author-identified significant results in this report.

The author has identified the following significant results. The land use category of subimage regions over Kansas within an MSS image can be identified with an accuracy of about 70% using the textural-spectral features of the multi-images from the four MSS bands.

Combined spectral and spatial processing of ERTS-1 imagery data

The author has identified the following significant results. Comparison of ERTS-1 imagery in three bands (MSS-4, 5, and 7) acquired over southwestern Kansas on 1 Dec. 72 reveals that low solar altitude has a pronounced different effect on apparent scene illumination in different bands.

A procedure for extracting a set of textural features for ERTS-1 MSS data is presented. The textural features were combined with a set of spectral features and were used to develop a classification algorithm for identifying the land use categories of blocks of digital MSS data. The classification algorithm was derived from a training set of 314 blocks and tested on a set of 310 blocks. The overall accuracy of the classifier was found to be 83.5% on seven land use categories.

The author has identified the following significant results. Preliminary digital analysis of ERTS-1 MSS imagery reveals that the textural features of the imagery are very useful for land use classification. A procedure for extracting the textural features of ERTS-1 imagery is presented and the results of a land use classification scheme based on the textural features are also presented. The land use classification algorithm using textural features was tested on a 5100 square mile area covered by part of an ERTS-1 MSS band 5 image over the California coastline. The image covering this area was blocked into 648 subimages of size 8.9 square miles each. Based on a color composite of the image set, a total of 7 land use categories were identified. These land use categories are: coastal forest, woodlands, annual grasslands, urban areas, large irrigated fields, small irrigated fields, and water. The automatic classifier was trained to identify the land use categories using only the textural characteristics of the subimages; 75 percent of the subimages were assigned correct identifications. Since texture and spectral features provide completely different kinds of information, a significant increase in identification accuracy will take place when both features are used together.

The author has identified the following significant results. The ability of ERTS-1 MSS imagery to detect small urban places appears to vary with the position of the place in the image, as well as from band to band. Urban places of smallest size (approximately 2000 population) seem more detectable in the westernmost 3.5 degree scan segment. A relationship may exist between shadowing of vertical features and detectability.

There are no author-identified significant results in this report.

There are no author identified significant results in this report. Environmental and resources investigations in Kansas utilizing ERTS-1 imagery are summarized for the following areas: (1) use of feature extraction techniqued for texture context information in ERTS imagery; (2) interpretation and automatic image enhancement; (3) water use, production, and disease detection and predictions for wheat; (4) ERTS-1 agricultural statistics; (5) monitoring fresh water resources; and (6) ground pattern analysis in the Great Plains.

There are no author-identified significant results in this report.

There are no author-identified significant results in this report.