User:Rsiddharth/pd3dpr documentation

this text is a draft for the documentation for pd3dpr.

Performance Analysis

Jive is lightweight and it is written in a way that its CPU footprint is minimal. The code-base was predominantly developed and tested on a Pentium 4 machine.

Jive was monitored for its CPU footprint while it crunched a directory full of TIFF real time images to detect and reciprocate about the possible obstacles found in the real time images.

The red rectangle shows the instant of time when jive was executed. As it can be seen the CPU footprint is not as heavy as was expected and the peak level was found to be 46.8%

In the following sections, the performance issues and optimization in jive are discussed briefly.

Disk writes

One of the expensive operations done by is writing to the disk whenever it has to process a Standard Image Path.

    public void processImage() {
        pdmConverter = new PixelMapToPDM(pMap);
        // generate the pdms of the pixel map:
        hPDM = pdmConverter.getHPDM();
        vPDM = pdmConverter.getVPDM();
        // write to respective files:
        print.print(hPDM, "./jive/data/SHPDM");
        print.print(vPDM, "./jive/data/SVPDM");
    }

As can be seen from the code, everytime standard image is processed by jive two disk writes take place -- one for writing the Standard Horizontal Pixel Difference Map & other for the Standard Vertical Pixel Differenc Map.

Disk writes are by default expensive, but given the computers today, two disk writes for a single session of running jive is not performance issue.

Disk reads

The number of disk reads, in jive, are for more than the number of writes that happens during the course of pattern analysis and recognition.

When a real time image has to be processed. The image should be read from the disk. We achieve this by using the TiffToMatrix class.

    ...
    public TiffToMatrix(String imageFile) {
        ImagePlus image = new ImagePlus(imageFile);
        readPixels();
    }
    ...

The ImagePlus class reads the TIFF image from disk. This type of read happens everytime a real time image is processed and it is inevitable.

Next, for the same real time image, when processing the Anomaly Maps, the AnomalyProcessor uses the StandardPDM object.

    ...
    public AnomalyProcessor(Integer[][] hpdm,Integer[][] vpdm) {
        this.hpdm = hpdm;
        this.vpdm = vpdm;
        spdm = new StandardPDM();
        processHorizontalAnomaly();
        processVerticalAnomaly();
    }
    ...

The StandardPDM object, everytime it is created, reads two files which contains the Standard Horizontal and Vertical Pixel Maps.

    ...
    public StandardPDM() {
        hpdm = new FileToArray(new File("./jive/data/SHPDM")).getArray();
        vpdm = new FileToArray(new File("./jive/data/SVPDM")).getArray();
    }
    ...

From above, it can be inferred that for every real time image processed, we have three mandatory reads from the disk.

When Jive is used by the blind user, a real time image is processed every two seconds, therefore for a minute, Jive needs to process thirty images. So, in a minute, we have 30 x 3 = 90 disk reads. If a user is continuously using the device for one hour, then the disk reads will tend to 90 x 60 = 5400 .

Optimization

As was seen from from the previous section, the number of reads seems to be apparently high, but it would have been more than this, if not for an important optimization:

Read the TIFF image into an Integer matrix and perform pattern & magnitude analysis with the matrix instead of the image.

If we hadn't decide to put the image's pixel values into a matrix. If would have had to use TIFF image every time we were in need of the pixel values for pattern and magnitude analysis -- this would have lead to more disk reads and consequently lead to performance issues.

This important optimization is done by the TiffToMatrix class.

public class TiffToMatrix {
    ...
    public void readPixels() {
        int x,y;
        pixels = new Integer[18][9];
        y=0;
        while(y<18) {
            x=0;
            while(x<9) {
                int[] colors = image.getPixel(x,y);
                pixels[y][x] = colors[0];
                ++x;
            }
            ++y;
        }
    }
    ...
}

As can be seen, the class simply reads all the pixels from the image and puts them into a matrix.

Why Integer matrix

we made this decision, because matrix operations are cheap and pattern and magnitude analysis is more straightforward with matrices than with raw images.

Conclusion

The implementation is meant to be run on phone with a 500MHz CPU. Jive was written with this constraint in mind. As as evident from the Optimization section, the program greatly reduces the complexity and thus the CPU footprint, by doing pattern and magnitude analysis on an Integer matrix. This and its modular design makes Jive, perfectly viable solution for the Perspective Dependent Three-Dimensional Path Recognizer.

Appendix

Miscellaneous content for knowing more about the Jive code base and how to use git.

Important Classes in Jive

Here is a bunch of classes that do interesting work and which, according to the authors, has been programmed cleverly.

The ImagePlus class

The ImagePlus class is part of the ImageJ library, which is a image processing library, released under the public domain.

The ImagePlus class is used to read pixel values from a TIFF image.

To use the ImagePlus class, we have to create an object of it:

ImagePlus image = new ImagePlus("path/to/image.tif");

As can be seen, the destination of the image should be given to the ImagePlus constructor when we create the object.

Now we are ready to read pixels from the image. We do that by:

 int pixelValue = image.getPixel(x,y);

Where x & y are coordinates that point to a particular location in the image.

To read all the pixels from the image, we simply use a while construct:

        while(y<18) {
            x=0;
            while(x<9) {
                int[] colors = image.getPixel(x,y);
                pixels[y][x] = colors[0];
                ++x;
            }
            ++y;
        }

So, that's how we use the ImagePlus class to read pixels from the TIFF image and copy it into a Integer matrix.

FileToArray class

Part of the IO package (jive.io), this class is used to read a of pixel map, stored in a plain text file, to a Integer matrix.

We use Regular Expression to detect integers or null values (marked as '-') from the plain text file:

        Pattern pattern = Pattern.compile("((\\-*\\d+)|(\\s+(\\-)\\s+))");

For regex, the java.util.regex.Pattern & java.util.regex.Matcher classes are used.

The pixel reading from the plain text file is done by first putting the whole file into a String object (fileContent) and giving it to the Matcher object

        Matcher matcher = pattern.matcher(fileContent);

After this, the Matcher's find() method is used to detect integer values and if an integer value is found, it is put in the corresponding position in the Integer matrix:

        ...
        while(matcher.find()) {
            match = matcher.group();
            if((matcher.group(4))==null) {
                array[row][column] = Integer.parseInt(match);
            }
            ...
        }
        ...

After the whole pixel map is put into the Integer matrix, The matrix can fetched using the getArray() method part of the same class.

PatternRecognizer interface

One of the best design decisions that was made through the developement of jive was with the PatternRecognizer interface.

It is a generic interface that all classes which do recognition should implement. By virtue of this, we make the jive Eco-system extremely modular -- new recognizers can be added to the code-base just by implementing this interface!

package jive.patterns;

/**                                                                                                                            
 * An interface for implementing classes, which recognize specific                                                             
 * patterns from the anomaly maps.                                                                                             
 */

public interface PatternRecognizer {
    public void analyse(Integer[][] vaMap, Integer[][] haMap);
}

All recognizers that implement this class must be added to the List in the PatternRecognizers class, which is part of the jive.patterns package.

...
public class PatternRecognizers {
    private static List<PatternRecognizer> list = new ArrayList<PatternRecognizer>();
    static {
        list.add(new UpwardStaircase());
        list.add(new ObstacleRecognizerR());
        list.add(new ObstacleRecognizerL());
        list.add(new ObstacleRecognizerTR());
        list.add(new ObstacleRecognizerBR());
        list.add(new ObstacleRecognizerBL());
        list.add(new ObstacleRecognizerTL());
    }
    public static List<PatternRecognizer> list() { return list; }
}
...

Using Git

Git, the fast version control system is used to maintain the jive code base.

We can do interesting things with git:

1. Skim through the project's history
2. Do work on multiple branches -- this is touted to be the kill feature in git.
3. Push the code-base to remote repos -- a back-up solution
4. etc

Browsing History

The Jive code-base is publicly hosted and can be cloned from:

 $ git clone http://rsiddharth.ninth.su/git/jive.git

To browse the jive's history, do:

 $ cd jive

 $ git log

and you'll get:

...

commit d865d08a97b5ecc6de41aa1d265b07aaa75d83e9
Author: rsiddharth <rsiddharth@ninthfloor.org>
Date:   Sun Apr 7 11:11:53 2013 +0530

    new PatterRecognizer:   patterns.ObstacleRecognizerL. it
    recognizes,
    as of now, raises in left side of the vmap.

    add this pattern recognizer to List in
    patterns.PatternRecognizers

commit dc159dca47981f9f98070590e4c7bbac9abbb714
Author: rsiddharth <rsiddharth@ninthfloor.org>
Date:   Sun Apr 7 11:08:34 2013 +0530

    new PatterRecognizer:   patterns.ObstacleRecognizerR. it
    recognizes,
    as of now, raises in right side of the vmap.

    add this pattern recognizer to List in
    patterns.PatternRecognizers

commit f681054781fefeb602a5f1b4c115286bc9e4629b
Author: rsiddharth <rsiddharth@ninthfloor.org>
Date:   Sun Apr 7 11:06:32 2013 +0530

    the stdout in patterns.ObstacleRecognizerBR, was made more
    appropriate.

...

For a more interesting output, you can do:

 $ git log --pretty=format:"%cn %cr %h %s"

and get this:

...

rsiddharth 2 days ago fa22a20 wrote some code for unit & integration testing of a bunch of classes.
rsiddharth 3 days ago 1b39f1d docs/sys-imp (the first draft is complete)
rsiddharth 3 days ago a80189b new file: docs/sys-imp (a blurb about the implementation, started writting, but not yet complete)
rsiddharth 3 days ago 7a6a5c6 started writing some pseudo code at etc/p-code/
rsiddharth 3 days ago 87bb9c7 modified: patterns/PatternRecognizers.java (recognizers re-ordered)
rsiddharth 2 weeks ago 00c0436 cosmetic stdout edit to patterns.ObstacleRecognizerL & patterns.ObstacleRecognizerR
rsiddharth 2 weeks ago 2a80b16 patterns.ObstacleRecognizerL does horizontal anomaly recognition (only rightward tilt) now.
rsiddharth 2 weeks ago 75e099f in util.AnomalyCruncher in, negative() was renamed to negativeRows()
rsiddharth 2 weeks ago 3c8fa6a in util.AnomalyCruncher, cherryPickARows() renamed to cherryPickA()
rsiddharth 2 weeks ago c1474d3 now patterns.ObstacleRecognizerR does horizontal anomaly recognition (right-ward tilt as of now)

...

As it can be observed, the log says who has done the work, when that work was done, its hash and finally a condensed version of the commit message attached to the respective commit.

Checkout out Branches

For Jive, at present, we maintain three different branches.

1. master branch - contains stable working-tree
2. dev branch - all development is done here and later merged into master
3. doc branch - all work related to documentation is done in this branch.

To see, in which branch you're in, do:

 $ git branch
   dev
 * doc
   master

The `*' beside the `doc' implies that, we you're in the `doc' branch at present.

To move to a different branch, do:

 $ git checkout branchname

To learn more about git, go to http://git-scm.com

rsiddharth (talk) 15:33, 24 April 2013 (UTC)