 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention relates to a method of producing single-class and
multi-class composite classification maps from multispectral data.
BACKGROUND OF THE INVENTION
As ever increasing quantities of digital multichannel data are generated
through the use of such multispectral scanners as the four-channel scanner
on the ERTS-1 satellite, the S192 thirteen-channel scanner on Skylab, and
numerous aircraft scanners including the Bendix Corporation's 24-channel
scanner, the need for improved processing capabilities has become
critical. The current methods of processing this data use a maximum
likelihood pattern recognition program such as LARSYS II. While such a
program provides an optimum classification scheme, at least in the sense
of minimizing the cost of misclassification, the computer processing time
required to produce a classification map increases substantially as the
number of channels of data increases. When digital pattern recognition
techniques are applied to the processing of terrain classification data
for extended areas, the cost of processing all of the data becomes
prohibitive. As a consequence, in such cases it is practical to process
only a small fraction of the data that is acquired. Although grey maps or
color composites for a single channel can readily be made from such
"screened" data, these maps cannot be made to include any information
contained in the multispectral nature of the data.
SUMMARY OF THE INVENTION
The disadvantages of the prior art are substantially overcome by the method
of the present invention wherein multispectral data is transformed from an
n-bit integer format into a binary matrix format, encoded on photographic
film, and holographically correlated with coded patterns representing a
particular spectral signature to produce single-class classification maps.
Several different single-class maps are then optically superimposed to
produce multi-class composite classification maps.
The method of the invention provides a much larger data processing
capability because:
1. Inherent in the use of optical holographic correlation techniques is the
capability of simultaneous parallel processing of data. For example, the
method of the invention will allow the data from a scanner containing well
over a million ground resolution elements (each element individually
containing up to 25 and more separate channels of data) to be processed
and classified simultaneously.
2. The optical encoding techniques of the invention by which the
transformed data is encoded on photographic film allow a higher data
packing density to be achieved than is possible on magnetic tape. These
techniques will allow 25 channels of data for one million resolution
elements to be encoded on about one square inch of film.
3. Packing density is further increased by the coding scheme used to
transform the data, which usually results in a reduction in the number of
bits of information by a factor of two to a factor of eight.
Other features and advantages of the invention will be set forth in, or
apparent from, the detailed description of the preferred embodiments found
hereinbelow.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram representation of the steps in a method in
accordance with a preferred embodiment of the invention for producing
multi-class composite classification maps;
FIG. 2 is a highly schematic representation of a multispectral scanner;
FIGS. 3(a) and 3(b) illustrate the format of the data which is transformed
in accordance with the method represented in FIG. 1, FIG. 3(b) being a
detail of FIG. 3(a);
FIG. 4(a) illustrates the format of the data for a 12-channel, 50 .times.
50 resolution element multispectral scanner which has been transformed and
optically encoded in accordance with the method represented in FIG. 1;
FIG. 4(b) is an exemplary detail of the pattern of FIG. 4(a);
FIGS. 5(a) and 5(b) are diagrammatic perspective views of the basic
elements utilized in the recording phase and the reconstruction phase,
respectively, of one embodiment of the holographic correlation step of the
method of FIG. 1;
FIG. 6(a) is a diagrammatic perspective view of the basic elements utilized
in producing a holographic filter used in a further embodiment of the
holographic correlating step;
FIG. 6(b) is a diagrammatic perspective view of the basic elements utilized
in the further embodiment of the holographic correlating step;
FIG. 7 is a representation of an illustrative 12-channel look-up table used
in the transformation step of one embodiment of the method represented in
FIG. 1; and
FIG. 8 is a representation of a 3-channel look-up table used in the
transformation step of a further embodiment of the method represented in
FIG. 1.
DETAILED DESCRIPTION
Referring to FIG. 1, a block format illustration is provided of the basic
steps of the optical process in accordance with the invention whereby
classification maps are produced from multi-spectral data. The first two
steps, represented by Blocks A and B, result in the transformation of the
spectral data generated by the multispectral scanner, which is generally
stored on magnetic tape in an 8-bit integer format, into a binary matrix
format encoded on photographic film. In the final two steps, represented
by Blocks C and D, the transformed data is holographically correlated with
coded binary matrix formats representing particular spectral classes, or
"signatures", to produce single-class classification maps, and these
single-class maps are then optically superimposed to produce a full-color
multi-class classification map.
In order to understand the transformation and encoding steps, it is helpful
first to consider the original format of the multispectral data. Referring
to FIG. 2, a schematic representation is provided of the pertinent
structural features of an illustrative multispectral scanner, generally
denoted 12. Reference is made to Skylab A EREP User's Handbook,
NASA-S-72-831-V, for a complete description of a representative scanner,
the Skylab S192. Scanner 12 measures the reflectance from a particular
ground resolution element, denoted 16, simultaneously in each of N
different spectral bands. The reflectance measurement of a single ground
resolution element 16 is thus divided into N separate channels, which are
denoted 18, and each of these N measurements is typically quantized as an
integer in the range of 0 to 255. These N measurements are typically
stored on magnetic tape as 8-bit integers. The scanner 12 then
sequentially scans a line of contiguous resolution elements, called a
scan-line and denoted by 14, and records N channels of data for each
resolution element 16 that is scanned. The scanning is done perpendicular
to the line of flight of the scanner 12 and the recording of successive
scan-lines 14 produces data for all ground resolution elements 16 that are
in the flight path.
Assuming the integers referred to are available for processing on magnetic
tape, as is the current practice, the first step of the invention is to
transform the integers, using a classification scheme to be described
below, into a binary format which is susceptible to encoding on
photographic film by a technique which also is to be described more fully
below. It should be noted that an alternative embodiment, which will not
be described in detail, but which employs a laser scanner linked directly
to the multispectral scanner 12, allows the multispectral data to be
recorded directly on the photographic film without first having to record
the data on magnetic tape. However, while such an embodiment simplifies
processing, it does not permit the production of classification maps with
different spectral sensitivities from the same data, such as is permitted
by the preferred embodiment now being described.
FIGS. 3(a) and 3(b) illustrate the ultimate format of the transformed data.
The binary matrix equivalent of the digital integers previously referred
to for each resolution element 16 in a series of scan lines 14 in a
computer memory device is resolution cells 24 of a matrix 26. The location
of the transformed data for a particular resolution element 16 in matrix
26 corresponds to the physical location of that element in a map of the
ground area covered by the data. Within each of the resolution cells 24
corresponding to a particular element 16, the transformed integers for all
of the N channels 18 are coded in a sub-matrix, which is denoted 28 and
which contains a particular quasi-random n .times. n array 30 of .+-.1's,
such as shown in FIG. 3(b). The integer for each channel 18 may be
represented by one or more of these binary .+-.1's, depending on the
classification scheme chosen. In all cases, N, the number of channels 18
of data, is less than or equal to n.sup.2, n.sup.2 representing the number
of sub-cells 31 in sub-matrices 28. A particular arrangement of the .+-.
1's in array 30 is characteristic of a particular spectral "signature",
the various features of the earth's surface each having its own spectral
signature. As indicated earlier, the classification scheme by which the
8-bit integers are transformed to the binary matrix format of array 30
will be discussed more fully below, but for present purposes, it is noted
that the scheme is designed such that a given array 30 of .+-. 1's has a
high correlation (in the sense of the sum of the bit-by-bit multiplication
of the binary +1's and -1's) with other arrays 30 representing similar
spectral signatures while at the same time having a low correlation with
all other arrays 30 representing dissimilar spectral signatures.
Once the integers referred to above have been transformed into the binary
matrix arrays 30 in the sub-matrices 28, the next step is to encode matrix
26 (with its sub-matrices 28 of .+-. 1 arrays 30) onto an optical input
medium such that the amplitude transmittance, with respect to coherent
light, of the input medium is .+-. 1 for each sub-cell 31 of sub-matrix
28, depending on whether the sub-cell 31 contains a +1 or -1 in array 30.
Any encoding method which achieves this result is suitable although
preferred methods are described hereinbelow with reference to FIGS. 4(a)
and 4(b).
Referring to FIG. 4(a), one preferred method of encoding the information
contained in the binary matrix format onto an optical input medium is
illustrated. FIG. 4(a) illustrates an example of the encoding of a 50
.times. 50 matrix 26 which has 5 .times. 5 sub-matrices 28 corresponding
to a 12-channel scanner 12. The encoding is achieved by means of selective
exposure of photographic film 32 by a computer-controlled cathode-ray tube
in a manner which results in a matrix pattern 34 of dot-like exposures
corresponding to the +1 sub-cells 31 of sub-matrices 28. A laser scanner
system can also be used to expose film 32. When film 32 is developed, the
exposed dot-like regions, or dots, 36 of matrix pattern 34, corresponding
to the +1 sub-cells 31 of sub-matrices 28, are opaque with respect to the
unexposed areas corresponding to the -1 sub-cells 31. In FIG. 4(b), which
is a detail of a portion of pattern 34, corresponding to a single
resolution cell 24 of a sub-matrix 28 of the matrix 26 illustrated in FIG.
4(a), exposed regions or dots 36 are black and the unexposed regions of
film 32 represents dots 38 are white. The developed film 32 is then
bleached producing a totally transparent optical medium in the unexposed
regions. The bleaching is controlled so as to produce a relative phase
shift of .pi. radians between a coherent light passing through a +1 region
representing dot 36 and a -1 region representing dot 38. In this way the
amplitude transmittance of the resulting bleached film 32 is equal to +1
in the original exposed regions 36 and is equal to -1 in the unexposed
regions 38.
Alternatively, in accordance with a further preferred embodiment of the
invention, the difference between a +1 region and a -1 region can be
achieved by varying the position of an exposed dot within a sub-cell 31 of
a sub-matrix 28. This corresponds to the so-called detour-phase method
used in computer generated binary holograms. While this detour-phase
method requires no bleaching of the film, the method described above that
utilizes bleaching will provide at least four times the packing density of
the method utilizing detour-phase. For example, with the bleaching method
a laser scanner system with 5.mu. resolution could encode 25 channels of
data for one million resolution elements on about one square inch of film.
Moreover, use of such a laser-scanner system would allow the use of
real-time input media, such as thermoplastic films, in place of
photographic film 32, to store the zero and .pi. phase information.
After multispectral scanner data has been optically encoded into a binary
matrix patterm 34 on an appropriate input medium, the data is ready for
the final two steps of the invention, to wit, holographically correlating
the pattern 34 with various coded, single-cell correlation patterns, which
are similar to the portion of patterm 34 corresponding to a single
resolution cell as shown in FIG. 4(b), but which have a pattern of dots
which represent specified signatures, thereby producing single-class
classification maps. Several single-class maps are then optically
superimposed to produce a full-color multi-class classification map.
Referring to FIGS. 5(a), 5(b), and 6(b), two methods of holographic
correlation are schematically illustrated. FIGS. 5(a) and 5(b) illustrate
a two-step system. In the first, recording step, illustrated in FIGS.
5(a), input media containing a binary matrix pattern 34 and a single-cell
correlation pattern 40 are placed in a first plane x.sub.1 - Y.sub.1 of a
beam of coherent light from a suitable source (not shown) that converges
to a focus in a second plane x.sub.2 - Y.sub.2. A hologram 48 of the
resulting interference pattern is formed in the second plane x.sub.2 -
Y.sub.2. Using the detour-phase method of encoding described above,
hologram 48 is formed at a location centered at the first diffraction
order in the plane x.sub.2 - Y.sub.2. If the laser-scanning method of
encoding described above is used, hologram 48 is centered on the optical
axis in the plane x.sub.2 - Y.sub.2.
In the second step, illustrated in FIG. 5(b), hologram 48 is placed in a
third plane x.sub.3 - Y.sub.3 of a beam of coherent light from a suitable
source (not shown) that converges to a focus at a fourth plane x.sub.4 -
Y.sub.4. A single-class classification map 42 for the spectral signature
whose correlation pattern 40 is used to make hologram 48 appear as a
two-dimensional image displaced along the x.sub.4 axis in the plane
x.sub.4 - Y.sub.4. Map 42 has a format corresponding to that of pattern 34
with a dot of light occurring at the center of each area representing a
resolution cell 24 (sub-matrix 28) of matrix 26, the brightness of the dot
being proportional to the correlation of that particular cell area of
pattern 34 with the single-cell correlation pattern 40.
Referring to FIGS. 6(a) and 6(b), a single-step real-time system is
represented, which utilizes a hologram 50 as a filter. As shown in FIG.
6(a), the filter hologram 50 is produced by placing a correlation pattern
40 at the origin of a first plane x.sub.1 - Y.sub.1 of a beam of coherent
light which converges to a focus at a second plane x.sub.2 - Y.sub.2. A
point light source 52 located along the x.sub.1 axis provides a reference
wave that interferes with the diffraction wave of the correlation pattern
40. The resulting hologram 50 is recorded in the x.sub.2 - Y.sub.2 plane,
either on the optical axis or displaced along the x.sub.2 axis depending
on whether the bleaching or the detour-phase method of encoding,
respectively, is used. The pattern 34 is placed in the x.sub.3 - Y.sub.3
plane of a beam of coherent light that converges to a focus at the x.sub.4
-Y.sub.4 plane. The distances z.sub.2 between the x.sub.3 - Y.sub.3 and
the x.sub.4 - Y.sub.4 planes are identical to the distance z.sub.1 between
the x.sub.1 - Y.sub.1 plane and the x.sub.2 - Y.sub.2 plane if the same
scales were used to encode patterns 34 and 40. It may be more convenient
to use a larger scale for patterns 40 when making the corresponding filter
holograms 50. If this is done, the difference in scales can be compensated
for by making z.sub.2 less than z.sub.1. The filter hologram 50 for a
particular class is placed in the x.sub.4 - Y.sub.4 plane, either on the
optical axis or displaced along the x.sub.4 axis to the first diffraction
order, again depending on whether the cathode ray tube or laser-scanning
method of encoding is used. In either case a lens L placed beyond the
x.sub.4 - Y.sub.4 plane is used to image the x.sub.3 - Y.sub.3 plane onto
the x.sub.5 - Y.sub.5 plane, resulting in the appearance of classification
map 42 in the x.sub.5 - Y.sub.5 plane displaced along the x.sub.5 axis.
Classification maps 42 for different classes are obtained merely by
inserting different filter holograms 50 representing the different classes
or spectral signatures into the x.sub.4 - Y.sub.4 plane.
At this stage of the process, maps 42 represent single-class
classifications. If these maps 42 are photographed on high-gamma
photographic film with controlled development, then only light dots with
intensities above some threshold C.sub.min value representing a minimum
cross-correlation will expose the film. Above this threshold, and within a
defined range, the dots will expose the film in proportion to their
intensities. By developing the film with a reversal process or by
two-stage contact printing (not illustrated), the brightness of each spot
resulting from the projection of the developed film through an image
projector (not shown) will be a measure of the confidence that the data
contained in resolution cell 24 belongs to the same class as that
represented by the correlation pattern 40 used to produce the
classification map 42 from which the projected map is produced.
Full-color multi-class classification maps (not shown) are readily produced
by projecting the developed film for each of several different
single-class maps 42 through a different color filter (not shown) for each
map 42 to produce colored projection maps, and by superimposing these
colored projection maps to produce a full-color multi-class map. This last
step of the process may be advantageously accomplished using commercially
available multiple image projectors with different color filters. In such
a multi-class map any resolution cell 24 that was classified in the
correlation step as correlating with more than one of the spectral classes
represented by the correlation patterns 40 used to produce the
single-class maps 42, will be represented by a projected light spot whose
color is the result of the optical combination of the colors used to
represent each single-class map 42. For example, if red, green, and blue
filters are used to superimpose three different single-class maps,
representing for example the spectral signatures of wheat, corn, and oats,
respectively, then any resolution cell 24 that correlated highly with both
the red "wheat" class and the green "corn" class results in a yellow light
spot. However, if a resolution cell 24 correlates highly with only the red
wheat class, resulting in a bright red spot for a single-class projection
map, and correlates only marginally with the green corn class, resulting
in a dim green spot, upon superimposition, a reddish-yellow spot is
produced.
Thus, different crops, such as soybeans, for example, will have spectral
signatures that are correlated to varying degrees with the signatures of
wheat, corn, and oats. Thus, in each of the three classification maps made
for wheat, corn, and oats, the areas representing soybeans will have a
different "grey" level in the resulting single-class projection map. In
the final full-color composite map, soybeans will be represented by a
particular combination of red, green, and blue and might appear, for
example, as dark yellow. Consequently, all regions in the composite map
will have a color that is characteristic of a particular spectral
signature.
The particular form of the full-color map will depend to some extent on the
particular choices of the spectral classes used to make the holographic
correlation single-class maps 42. These classes may or may not correspond
to spectral data actually viewed by particular ground resolution elements
16. However, classes should be chosen which are as mutually uncorrelated
as possible, and which correlate highly with the data of a significant
number of resolution elements 16. The best method for selecting the three
classes that will produce the best single-class and composite
classification maps will vary with the particular application for which
the maps will be used.
The final multi-class classification map will be a full-color map in which
resolution cells 24 that have similar spectral signatures over a large
number of channels 18, that is, appear the same over a wide spectrum,
produce spots which have the same color. As stated, by using high gamma
photographic film and controlling the development of the film so that only
light dots have light intensities above a minimum threshold value
representing a minimum cross-correlation will expose the film,
single-class and multi-class classification maps with different spectral
sensitivities may be produced. For example, one multiclass map would
differentiate between agricultural and forest areas, but would not
distinguish different agricultural crops in agricultural areas or
different timber species in forest areas. Another multi-class map, with a
higher sensitivity, would distinguish specific crops or specific timber
species. Moreover, as also was mentioned above, above the threshold
referred to and over a particular range, the light dots can be made to
expose the film in proportion to their intensities and thus if the film is
developed using one of the processes referred to and projected through a
color filter, the brightness of each color spot will, as stated, be a
function of the degree to which the corresponding resolution element
belongs to the particular class in question.
An integral part of the transformation steps referred to above is the
classification scheme whereby the integers referred to above are converted
to the binary array 30. In order to facilitate understanding of the
classification scheme, manipulation of the integers by appropriate
computer hardware will be described by reference to mathematical
analogies. Basically, the transformation of the digital integers to a
binary array 30 of .+-. 1's is accomplished by plotting the digital value
(on a scale of 0 to 255) of the integer in each channel 18 as a function
of the channel number on a matrix graph, the size and location of whose
cells depends on the particular statistical strategy used to classify the
data. A detailed discussion of three strategies is provided in Haskell, "A
Correlation Method for Processing Multispectral Data," NASA Report No. ISC
08011. In accordance with a preferred embodiment of the invention a
strategy is employed which provides "unsupervised" classification of the
integers 20 by means of clustering, in which K cells of uniform size are
assigned to each channel, with the possibility that K, the number of
cells, may vary from channel to channel. As an example, FIG. 7 illustrates
the case of 12 channels in which the matrix contains 13 cells for each
channel. A value of +1 or -1 is then assigned to each cell at random with
equal probability, as shown in FIG. 7. In this format, the matrix graph is
known as a look-up table. If the data were to be classified by means of
computer hardware, instead of by the holographic correlation described
above, the following operations would be performed: A row vector is formed
for each resolution element which contains a number of elements equal to
the number of channels 18, the value of each element of the row vector is
either +1 or -1, depending on the value of the cell in the look-up table
corresponding to the value of the integer for each channel. The row
vectors are then correlated with vectors deemed to be characteristic of a
particular spectral signature. In an unsupervised classification scheme,
the correlation is achieved in the following manner: The spectral
signature obtained from the first resolution element 16 deemed to be a
reference signature, called Class 1, and its corresponding row vector
T.sub.1, is stored. A signature from a second resolution element 16 is
then measured and its corresponding row vector S is formed. A scalar
integer pg,18 correlation sum C is then obtained by forming the inner
products of vector S with the transpose (corresponding column vector) of
reference vector T.sub.1. Sum C is compared to some minimum value
C.sub.min and if sum C is greater than C.sub.min, then the signature from
this second resolution element 16 is also assigned to Class 1. Otherwise
the signature is deemed to be another reference signature, called Class 2,
and its corresponding row vector T.sub.2 is also stored for future
comparisons. This procedure is repeated for subsequent resolution elements
16; viz. forming a vector S(J), computing the correlation sum C and
comparing it with previously stored reference vectors T(M), assigning the
signature for the element 16 to the Class M yielding the largest
correlation which exceeds C.sub.min, or otherwise creating a new class.
The total number of clusters into which the data (the integers referred
to) will classify themselves depend on the initial selection of the values
for the number of cells in each channel and the value of C.sub.min. A
number of possibilities exist for an adaptive program that will vary the
number of cells/channels and/or C.sub.min until the data are classified
into a predetermined number of classes. The reference vectors T(M) are
updated so that they always represent the average reference vector of all
elements 16 previously assigned to Class M. However, using the holographic
correlation techniques described above, the vectors T(M) are replaced with
the single-cell correlation patterns 40 whose pattern of dots 36
correspond to the spectral signatures which vectors T(M) represent.
Pattern 34 corresponds to a matrix of all the S(I) vectors. The
holographic correlation of pattern 34 with correlation pattern 40 produces
simultaneously the equivalent of comparing a particular vector T(j) with
all the S(J) vectors. The intensity of light dot produced at the center of
each resolution cell 24 will be proportional to C.sup.2, where C is the
correlation sum defined above. As described above, identification of
correlations exceeding some minimum value C.sub.min is achieved by
controlling the development of high-gamma film.
With the format of the look-up table just described, each integer is
represented by a single +1 or -1 in the array 30 of .+-.1's. This method
is likely to produce good discrimination between classes M only if there
is a sufficient number of channels 18 of data for each resolution element
16. For example, the probability of a +1 or a -1 occurring as the
transformed value in any single channel 18 of a four-channel scanner is
0.5. As a consequence, a significant correlation over only four channels
is possible for some ground resolution elements 16 with vastly different
original spectral signatures. This difficulty may be overcome by assigning
to each channel measurement (each integer) in an array 30 a random
sequence of .+-. 1's that is characteristic of a particular value of the
integer and that has a low correlation with other measurement values that
are significantly different therefrom. One method of obtaining the .+-. 1
sequency is illustrated in FIG. 8 where each of three channels 18 on the
matrix graph of the look-up table has been subdivided into four
subchannels. In general, the width of each sub-cell remains the same as
before, but the sub-cells in each subchannel have been shifted with
respect to adjacent sub-cells by an amount NCELL/NSUBCHNL, where NSUBCHNL
is the number of subchannels in each cell of the look-up table and NCELL
is the width of the cell. The effect of the subchannel division is to
increase the number of effective elements which are cross-correlated, thus
allowing greater discrimination among similar classes of data when only a
few real channels 18 are available for clustering. The selection of the
values for NSUBCHNL and NCELL will determine the spectral sensitivity of
the resulting classification maps. Large values of NCELL, corresponding to
wide cell widths will result in different spectral signatures for elements
16 having the same n .times. n array 30 of .+-. 1's. Thus large values of
NCELL result in classification maps with low spectral sensitivity.
Although the invention has been described relative to exemplary embodiments
thereof, it will be understood by those skilled in the art that variations
and modifications can be effected in these embodiments without departing
from the scope and spirit of the invention.
* * * * *
|
|
 |
|
 |
Description |
|
