Elliptic Fourier analysis



             F. James Rohlf (f.james.rohlf at stonybrook.edu)

                               and

                 Scott Ferson (scott@ramas.com)

               Department of Ecology and Evolution

                   State University of New York

                      Stony Brook, NY 11794



                             4/22/92



   Two sets of programs are a part of this package.  EFA and EFAW

are programs to compute the elliptic Fourier coefficients for an

outline described by a set of x,y-coordinates (EFAW is the version

for use with MS Windows 3.0+).  The program allows for various

simple transformations so that the results will be invariant to

size, location, rotation, and starting point of the digitized

outline.  These methods are described in:



Ferson, S. F., F. J. Rohlf, and R. K. Koehn. 1985.  Measuring

shape variation of two-dimensional outlines.  Syst. Zoology,

34:59-68.



   EFA3 and EFA3W are programs for a generalization of the above

method for outline contours in 3 dimensions (EFA3W is the version

for MS Windows).  The generalization corresponds simply to adding

a Fourier analysis of the delta Z coordinates and making the

analyses of all three coordinates a function of arc length along a

3-dimensional contour curve.



   Size standardization (for the 2-dimensional case) is achieved

by estimating the area of the enclosed region (measured as the

area of the ellipse defined by the first harmonic) and then

dividing everything by its square root.  Invariance to location is

done by estimating the x and y-coordinates of the centroid of the

enclosed region and then subtracting these from the input x and

y-coordinates.



   Invariance to rotation and starting point are achieved by

procedures that are somewhat arbitrary.  The outline is rotated so

that the major axis of the ellipse defined by the first harmonic

is parallel to the x-axis.  Invariance to starting position is

achieved by restarting the outline at a point at the end of this

ellipse in the positive direction along the x-axis.  These two

operations have the problem that they make the alignment of

outlines dependent on their shape.  It is usually best to provide

data that have already been aligned and with the outlines starting

from a well-defined landmark.



   The 3-dimensional case is more comples.  At present, the EFA3

and EFA3W programs do not make any of the adjustements described

above.



   The input is a file of X,Y coordinates (or X, Y, Z coordinates

for a 3-dimensional contour) for 1 or more outlines.  Output is a

file that contains elliptic Fourier coefficients and (optionally)

an estimated outline based on the specified number of harmonics.



   Details of computations are described in comment lines in the

programs.  The program were written in FORTRAN for the Microsoft

FORTRAN compiler version 5.1 for computers compatible with the IBM

PC.  A version for DOS, EFA.EXE, and a version for MS Windows 3.0,

EFAW.EXE, are distributed.



---------------------- Installation ----------------------------



   There is no special installation procedure needed for the DOS

version of the program.  Simply unpack the archive file and copy

the files to your hard disk.



   If you are using a computer that does not have a math

coprocessor then you may have to have to use the following DOS

command to enable the program to correctly detect the fact that

the chip is not present:



     SET NO87=X



   For the Windows version you may wish to intall the program as

an icon in the Program Manager.  To do this copy the EFAW.EXE file

to your hard disk and then click on "Files" and then "New" in the

menu of the Program Manager.



---------------------- Input data format ----------------------------





label for file   <------ comment to label ouput

n                <------ no. points around outline

x1 y1 x2 y2 ...  <------ coordinate pairs, free format

... xn yn

n                <------ start of second outline (if any)

x1 y1 x2 y2 ...          etc.



etc.



   The TESTEFA.DTA file is provided as a simple example of a data

file.  Sample output from that file is provided below.



   Note:  do not duplicate first x,y at the end of the outline

(program assumes it has to complete the contour).



   The input described above can be placed in a file or else

entered interactively as the program runs.



   For 3-dimensional data use the same format as above but list

the X, Y, and Z coordinates for each point along the contour.



---------------------- Program limitations ------------------------



   The program uses dynamic storage allocation procedures so the

limitation on the size of data sets that can be analyzed is simply

the amount of available RAM.



   The amount of RAM available before running EFA can be

determined by using the DOS program MEM. The program itself

requires about 60K.  The program uses 7 arrays of length equal to

the number of data points and 4 arrays of length equal to the

desired number of harmonics.  Each number requires 6 bytes of RAM.

It should normally be possible to process outlines consisting of

several thousand points.



   The Windows version, EFAW.EXE, can take advantage of the large

amount of memory typically made available by Windows.  Click on

"Help" and then "About" in the menu for the Program Manager to see

how much memory is available.  Often around 10MB is available!

Thus very long outlines can be processed.  Normally, the

limitation will be computer time rather than available memory.



----------------------- Running the program ------------------------



DOS version:



   At the DOS prompt type:  EFA (or EFA3).  The program will ask

for the names of the input and output files.  If you enter USER

for the input file then the program will expect to read the data

from the keyboard.  If you enter USER for the output file then the

results will be displayed on the screen.



   You may also enter the input and output file names at the

command line as follows:  "EFA FINPUT FOUTPUT", where FINPUT is

the name of your input file and FOUTPUT is the name of your output

file.



MS Windows version:



   If the program has been installed as an icon then you can just

double click the icon to start the program.  If not, then click on

"Files" and then "Run" in the Program Manager's menu.  Then type

"EFAW" or "EFAW FINPUT FOUTPUT" (or "EFA3W FINPUT FOUTPUT") in the

window and click "OK" or else press the enter key.



   If you did not furnish the names for the input and output

files, the program will ask for them.  If you enter USER for the

input file then the program will expect to read the data from the

keyboard.  If you enter USER for the output file then the results

will be displayed in a window.  After the run is complete you can

copy the information in the results window to the Windows

Clipboard and then save it in a file or else paste it into some

other Windows program (e.g., a wordprocessor or spreadsheet).





----------------------- Program prompts ----------------------------



   The EFA and EFAW programs ask the following questions after it

opens the input data file (both the DOS and the Windows versions):



Number of harmonics to be computed

Make invariant to object size? (Y=yes)

Make invariant to object location?

Make invariant to object rotation?

Make invariant to starting position?

Estimate outline from coefficients?



   The number of harmonics requested will be constrained to

be equal to or less than the number of points divided by 2

(divided by 3 for 3-dimensional data).



   The questions about results being invariant give you the

ability to get a set of descriptors that are invariant under

rotation, scale change, and choice of starting point.

These questions are asked only once for a data file.  If there is

more than one outline in a file then the same options will be

applied to all of them.



   The results are listed in the output file.  If you say "Y" to

the question about estimating the outline then the program will

also try to reproduce the original set of x,y-coordinates based on

the specified number of coordinates.  This can be helpful at first

so you can determine how many harmonics are needed.



   Note:  one does not expect each point in the reproduced outline

to to match the corresponding point in the input.  This is because

the points in the output are equally spaced along the reproduced

outline and that is unlikely to be true in the input.  To check

the results you must plot the reproduced outline to see if it

gives the same shape as the input outline.



------------------------ Output -----------------------------------



   Example of EFA using the TESTEFA.DTA file for input and

answering "Y" to adjusting for size but "N" to all other questions

about invariance.  Six harmonics were requested.





               Elliptic Fourier analysis

                     12/12/91



 Input file: testefa.dta

 Output file: testefa.out

 Label: TEST DATA FOR ELLIPTIC FOURIER





 N points =         12 N harmonics =          6

 Invariant to size (area)

   Area =        1.995527



 Elliptic Fourier coefficients:



 Zeroth harmonic:

 A0=       2.940963 C0=       2.344097



 Coefficients for harmonics:



                A                  B                  C                  D

  1    -.795240700        -.552156200        -.551345500         .486770100

  2    -.114832100         .344645600E-01     .924464600E-01     .390060900E-01

  3     .255298300E-01    -.676450500E-01    -.112082300         .350138700E-01

  4     .735372500E-02     .432591000E-01    -.555184400E-01    -.484213800E-01

  5    -.347009100E-01     .152764000E-01     .817555700E-02    -.251324900E-02

  6    -.799765200E-02    -.159095800E-01    -.930708600E-02     .990867100E-02



 Reproduced outline:

   1    2.02107500        1.71646500

   2    1.96044600        2.21181500

   3    2.04717600        2.65626900

   4    2.60191200        2.65468200

   5    2.94341000        2.82384600

   6    3.14311900        3.19724200

   7    3.62989800        3.02697000

   8    3.94991000        2.62665000

   9    3.91100000        2.12781100

  10    3.54038100        1.75619600

  11    3.04523100        1.65737700

  12    2.49799500        1.67383800



   Note that you get 4 coefficients for each harmonic (ordinary

Fourier analyses only give you 2 numbers per harmonic).

Please read the note about the reproduced outline in the section

on Program Prompts above.



   For the 3-dimensional case you will get 6 coefficients per

harmonic.