readme.txt

基于＂trace transform＂的识别２Ｄ图像的Ｃ＋＋源程序

Trace Transform Package, version 1, June 2004


This package presents C++ tools to the trace transform of a 2D image, and related objects, i.e. circuses and triple features, matlab tools to visualise these entities, and tools to check newly coded functionals.  This version is released with a small number of functionals only. 
=====================================

THEORY

The theory of the trace transform is described in papers

A Kadyrov and M Petrou, 2001. "The Trace transform and its applications". IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI, Vol 23, pp 811-828.

M Petrou and A Kadyrov ''Affine invariant features from the Trace transform'', IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.26, No.1, January 2004, pp 30-44.

A Kadyrov and M Petrou "Object signatures invariant to affine distortions derived from the trace transform", Image and Vision Computing, 1 December 2003, vol. 21, no. 13, pp. 1135-1143,  Elsevier Science.


     PART 1. Program tt.cpp

     PREAMBLE 

A program "tt.cpp" version 0.1 takes one or more images as input and outputs trace transforms, circuses and triple features.

The code is in C++; the main source program is "tt.cpp" and there are a few include files with extension *.h.

The program can be compiled by any C++ compiler with optimisation: for example, using gnu compiler g++, as 

    g++ tt.cpp -o tt -O3

If matlab is available, the user can view the results using matlab. For that purpose a set of matlab m-files is provided. To make results accessible by matlab, a set of options in the form 
    -*w*txt
 is provided, where "w" stands for "write", and "txt" indicates text file, that can be read by the standard matlab function "textread".

Running the program uses a standard "-" way of description in the form 
          tt -option1  -option2 argument -option3 argument argument...

The order of the options is not significant. 

To check that the program properly understood your input, tt will print input variables.  To make it silent, use "silent" option
   -S
On the other hand, to retrieve maximum information, including timing and long list of images, use the "verbose" option
   -V

     TWO SPEED OPTIONS

The user is not supposed to change the code except the first line which is

//#define USEPEANO

This directive can be commented out as above or uncommented as 

#define USEPEANO

This directive makes available the use of Peano indexing of images. For some computers this speeds up the program by a factor of 2.  However, in other computers this indexing slows it down. 


     FILE SYSTEM

Place the program tt in a current directory, in our example it is directory tr4all. 

The result of the program may encompass many files of different nature, so a file system is proposed to find a way to output the data. 

For writing down the results, the user should create an output directory <Dir>,  and its three subdirectories with predefined names: "TrMatrs\", "Circuses\" and "Triple\".  As it is obvious from the names, these three directories will accumulate information about the trace matrices, the circuses and the triple features, respectively. 

It is advisable to use different output directories <Dir> for different sets of images and functionals. If <Dir> is not specified in the options, program tt.cpp uses as  default <Dir>="Outinfo/".


     PATH TO IMAGES 

The most important argument is an image or a list of images. All images should be in *.pgm format; both P5 (byte) or P2 (text) are allowed.  It should be mentioned that matlab Release 13 reads and writes *.pgm files. 

The images should be in a single directory and the path can be given as an argument:

-Ipath <path to images>
Comment:   a path should end with the symbol "/". 

If this option is omitted, the default is an empty string "", pointing to the current directory

     LIST OF IMAGES: TWO ALTERNATIVES:

-I <name of an image file> <name of an image file>...
Comment:   one or more names of image files.

-Ifile <text file of names of images, in each line one image file name is placed>

Comment:  It is used if the list of image names is too long for the command line.

     OUTPUT INFORMATION DIRECTORY

To provide the program with an output directory, the following option is used
-Dir <Dir>
where <Dir> is the path to a directory for the output information
Comment: default: <Dir>=Outinfo/ 

As it was mentioned earlier, this directory <Dir> must have three subdirectories
TrMatrs/
Circuses/ 
Triple/

The first one is for the trace matrices, the second one is for circuses, and the last one is for triple features.
  

     FUNCTIONALS

The following overview of basic ideas may help one understand our functional enumeration system.

A functional is an operation that produces a number out of a function. In the program we use notions of "modus operandi" and an "object". Modi operandi and objects have independent numbering.  A modus operandi computes one or more objects, and in computations it uses some (or none) other objects. An object may be a number or a more complicated object, like an array, as in the case of the Fourier transform.  Some objects are numbers and therefore they may be obtained as results of functional computations.  This explains why the enumeration of functionals is not successive, since not all objects are functionals.  Another implication is that the user may only use legitimate code numbers of functionals. If the user tries to refer to numbers that identify helping objects, as opposed to functionals, a run time error may occur.  The list of available functionals will grow in the next versions of our program. 

Having a list of functionals, the program finds an economical set of modi operandi in order to share computations.  Occurring symmetries also are taken into consideration to shorten computations.  This explains why computation of several functionals in one run of the program may be faster than several runs for each functional separately. 

In an argument list <a functional> means identify the functional you want to use by its index. For example, "sum" is functional 33; being used as a trace functional, it will produce the Radon transform of an image, see an example below.

     LISTS OF FUNCTIONALS

Trace, diametrical and circus functionals are specified  as follows:

-T <trace_functional> <trace_functional> ..
-P <diametrical_functional> < diametrical_functional> ..
-F <circus_functional> <circus_functional> ..

The option "-T" is necessary, the other two options may be omitted.  For example, if the user does not want to compute triple features, then option "-F" is superfluous.

The indices of the functionals should be given in ascending order.  If not, the program will rearrange the lists in ascending order.

We designated the number of trace functionals by LtrList, the number of diametric functionals as LdiList, and the number of circus functionals as LcirList.  These designations are used in this manual and in the program. 

     A SIMPLE FUNCTION CALL

To demonstrate an idea of a program call consider the following minimalistic example.

Suppose you have an image "image1.pgm" in the current directory.  Then, to refer to it, you do not need to specify an image directory.  Let a directory "Outinfo/" be in the current directory and its subdirectory "TrMatrs/" be created.  Then, the following call

       tt  -I  image1.pgm  -T  33  -wTtxt

will compute the Radon transform of the image.  Here option "-wTtxt" means that all trace matrices, (one only in this example), are to be written as text files. 

The result of the program is a file 

     Outinfo/TrMatrs/image1T033.txt

To view the Radon transform, the following matlab command may be used:

     T33=textread('Outinfo/TrMatrs/image1T033.txt')'; imagesc(T33);

Here transposition (') is involved to make the angle axis horizontal. 

     TRACE DISCRETISATION PARAMETERS

An image function considered along a line is called a trace.  This explains the term "Trace transform": each trace is converted into a number and the numbers are organised in a trace matrix. A line position is identified by parameters p and fi.  Along the line the varying parameter is t.  The user can specify discretisation of these parameters as 

-dt <distance_in_pixels>
Comment: default 1.0.  The distance between successive points along each tracing line is measured in terms of inter-pixel distances

 -dp < distance_in_pixels>
Comment: default 1.0

-360 <number N2pi of angles sampling a full circle>
Comment: default N2pi=128, that is 360/128=1.8125 degrees between consecutive directions. Hence, N2pi is the length of any circus which will appear in the program. This number should be divisible by 4. 

These three arguments allow the shortening of computation time.  Even a moderate increase of dt and dp improves the time, which is proportional to N2pi/(dt*dp). 

In order to choose these arguments, we may speculate that the optimal size of a trace matrix should be approximately equal to the size of the image in order to store equivalent information, or smaller, if many trace matrices are used to characterise a particular image. 


     OUTPUT TEXT INFORMATION

The option ending with "txt" forces writing the text output readable for matlab.

-wTtxt
Comment: all trace matrices to be written in files with names according to the convention: 
<image name>"T"<functional number, 3 digits>".txt"

-wCtxt
Comment: all circuses to be written in files with names according to the convention: 
<image name>"T"<functional number, 3 digits>"C"<functional number, 3 digits>".txt"

-wCAtxt
Comment: all associated normalised circuses to be written in files. If a circus cannot be normalised, the file is filled with zeros. File names follow the convention:
<image name>"T"<functional number, 3 digits>"CA"<functional number, 3 digits>".txt". 


-wCPtxt
Comment: all plain normalised circuses to be written in files. If a circus cannot be normalised, the file is filled with zeros. The file name is in the form
<image name>"T"<functional number, 3 digits>"CP"< functional number, 3 digits >".txt"

The last three options may lead to a huge number of files. Overall LtrList* LdiList files per image will be written. They can be merged into one file corresponding to a particular image.  The following options produce a long line of concatenated LtrList*LdiList circuses for each image, 

-iwCtxt
Comment: the file names are in the form: <image name>"C.txt"

-iwCAtxt
Comment: the file names are in the form: <image name>"CA.txt"

-iwCPtxt
Comment: the file names are in the form: <image name>"CP.txt"

In each file the circuses follow in lexigraphical order corresponding to pairs 
         (<trace_functional, diametrical_functional>).  
Therefore, the circuses for a given trace matrix are concatenated.  Overall one file per image will be produced. 


     OUTPUT pgm INFORMATION

-wTpgm
Comment: all trace matrices being scaled to the range [0,255] to be written for visualisation in files with names following the convention:
<image name>"T"<functional number, 3 digits>".pgm"


     OUTPUT BYTE INFORMATION

Text files are unnecessarily big and take time for reading and writing. Then, for working with a big database, we use the formats *.sm and *.sc, which allow smaller (by more than a factor of 10) files. As for Unix and Windows, files in these formats are portable.

For writing a trace matrix M, its minimum (min) and maximum (max) element are found. Then a matrix M1 is composed as 
    M1=round(255*(M-min)/(max-min))
Then max and delta=max-min are coded in 4 bytes each.  Therefore, the numerical information has an 8 byte scale normalising prefix. For the rule of coding and decoding the numbers, see in unit2.h, functions "packdouble" and "unpackdouble".  Coding and decoding the matrix is done by "writeMatrixSmall" and "readMatrixSmall"

For writing a set of concatenated circuses into one *.sc file, each circus is preceded by its 8 byte scale normalising prefix. Therefore, the number of bytes in *.sc is equal to the product

    (number of trace functionals = LtrList)*
    (number of diametrical functionals = LdiList)*
    (8+(length of one circus = N2pi))

Consequently, to read these files the user should know numbers LtrList, LdiList and N2pi beforehand.  Functions writeAllCircByParts and readAllCircByParts write and read *.sc format. 

The following options correspond the options listed above, except they use a different output format

-wT
  Comment: the file name is in the form <image name>"T"<trace functional>C<diametrical functional>".sm"
-wC
  Comment: the file name is in the form <image name>"T"<trace functional>C<diametrical functional>".sm"