Monday, November 17, 2008

Computer vision C++ libraries review

I am trying to create an easy to use, minimalistic C++ cross-platform computer vision system, with a non-restrictive license. My biggest challenge was to chose the best libraries and to get them to work together; this took some investigation and experimenting. This posting is a brief description of my findings.

This is what ShapeLogic C++ currently looks like:


Windows


Linux

In order to construct ShapeLogic C++, I had to make choices within the following categories:
  • Computer vision and image processing libraries
  • GUI libraries
  • Unit test systems
  • Build systems
  • Compilers under Windows
  • C++ IDEs under UNIX
ImageJ, the Java open source image processing tool, is the inspiration for the first part of my work: it is very simple to learn, use and program in. This is a follow up to my last posting: Computer Vision C++ vs Java. The result of my work is released as an open source project ShapeLogic C++, under the MIT license.

Computer vision and image processing libraries

The candidates I considered were:
  • GIL, Generic Image Library
  • OpenCV
  • VXL

GIL, Generic Image Library

GIL, Generic Image Library by Adobe.

Pros
  • Very non intrusive, only based on header files
  • Puts a wrapper around most image format
  • You can write a algorithm once and it will work for most image types
  • Part of Boost since 1.35
Cons
  • Does not come with a lot of image processing algorithms

OpenCV

OpenCV, Open Computer Vision by Intel.

Pros
  • Very simple
  • Works with both C and C++
  • Very broad range of algorithms
  • Complex algorithms: face detection, convexity defects
  • Very popular
Cons
  • You have to use OpenCV's IplImage
  • IplImage byte order is BGR instead of the normal RGB

VXL, Vision X Library

VXL a combination of 2 big older vision libraries TargetJR and IUE

Pros
  • Well tested technology
  • Simpler build process using cmake
  • Uses modern programming techniques: classes, template and STL
  • It has a lot of functionality
  • Simple to get started with
Cons
  • It is not using normal STL, but in order to work on different compiler it had to make its own version with different names.
  • Class structure is somewhat complex.
Choice computer vision library for ShapeLogic C++
OpenCV for existing image processing and vision algorithms. GIL for writing new algorithms.

Cross platform GUI

The candidates I considered were:
  • GIMP plugin
  • GTK+, GIMP toolkit
  • FLTK
  • HighGui from OpenCV
  • PhotoShop plugin
  • wxWidget

Run ShapeLogic as a GIMP plugin

Pros
  • GIMP is the main cross platform OSS image editing programs.
  • It is in wide use.
  • Has a lot of powerful features including scripting functionality in Scheme and Python.
  • From a user perspective this would be an excellent choice.
Cons
  • GIMP is GPL, but you could have a wrapper around plugins in order to access them as GIMP plugins.
  • The plugin works with tiles, which gives good performance, but does not fit well with either the way OpenCV or GIL are processing images.

GTK+, GIMP Toolkit

Pros
  • GTK+ is a great looking and very powerful framework that works on: Windows, Linux, Mac, a.o.
Cons
  • It is written in C and has a homegrown object system, which is not type safe.

GTKMM C++ wrapper around GTK+

Pros
  • CTKMM is a great looking and very powerful framework, that works on: Windows, Linux, Mac, a.o.
  • It feels natural to program in for a C++ programmer.
Cons
  • The class hierarchy is somewhat deep since it is built on top of GTK.

FLTK, Fast light toolkit

Pros
  • FLTK is very lightweight.
  • Very clean C++, you actually have a main().
  • Native C++ build on top of X11 or Windows.
  • Fluid, a simple GUI builder
Cons
  • Not as many widgets.
  • Dated look.

HighGui from OpenCV

Pros
  • Very lightweight.
  • There is some functionality for displaying images, video and an event handler for mouse events.
Cons
  • Does not come with a menu system.

Run ShapeLogic as a PhotoShop plugin

Pros
  • PhotoShop is the main image editing programs.
  • It is in wide use, has a lot of powerful features including macros.
  • From a user perspective this would be an excellent choice.
Cons
  • The PhotoShop SDK is not freely available, you have to apply to get it.
  • The plugin does not fit well with either the way OpenCV or GIL are processing images.

wxWidgets

Pros
  • wxWidgets is a full featured GUI toolkit, built on top of native toolkits: Win32, Mac OS X, GTK+, X11, Motif, WinCE and more.
  • Looks good and modern.
  • Big community.
  • Several GUI builders.
Cons
  • The programming style is close to Windows MFC programming.
  • There are many layers.
Choice
This was a hard choice and I went back and forth between FLTK and wxWidgets, but went with FLTK. All the GUI code is separate from the image processing code, so if I wanted to change from FLTK to another toolkit later it should not be too dramatic.

C++ unit test frameworks

There are a lot of different choices and no clear leader. Some of the candidates were:
  • Boost.test
  • CppUnit
  • Google C++ Testing Framework

Boost.test

Pros
  • Boost.test is part of the Boost library.
  • Powerful with a lot of options.
Cons
  • You have to manually set up test suites.
  • It is somewhat heavy.
  • The documentation is extensive but not easy to read.

CppUnit

Pros
  • CppUnit is following a standard unit testing convention XUnit.
  • Integration with Eclipse CDT.
Cons
  • You have to manually set up test suites.
  • It is an extra library to install.

Google C++ Testing Frameworks

Pros
  • Google test is following a standard unit testing convention XUnit.
  • Strong focus on simplicity.
  • Documentation is short and easy to read.
Cons
  • It is an extra library to install.

Choice of C++ unit test framework for ShapeLogic C++

I spent quite a bit of time reading the Boost Test documentation, finally I tried Google C++ Testing Framework and got it working very fast.

Build system

The candidates I considered were:
  • Boost build
  • Make

Boost build

Pros
  • Boost build is part of Boost.
  • Clean design, made as a Make replacement.
  • Works on most platforms and with most compilers.
  • The scripts are pretty short.
Cons
  • There is a learning curve.

Make

Pros
  • Make is the standard for build on C++.
  • Widely used.
  • Works with Eclipse, MSVC, NetBeans.
  • Short scripts.
Cons
  • It has gotten messy over time.
  • Shell script dependency.
  • There is too much magic for my taste.

Choice of build system for ShapeLogic C++

I chose to go with Boost Build because it has a cleaner design, but Make looks very competitive when looking over the pros and cons.

Compilers under Windows

In order to compile Boost you need a pretty modern and standard compliant compiler. The candidates that I looked at are:
  • Cygwin GCC
  • MinGW GCC
  • MSVC Microsoft Visual C++

Cygwin GCC

Pros
  • Cygwin GCC is close to GCC under UNIX
Cons
  • Uses emulation of UNIX system call.
  • You can only use it to build GPL compatible application.

MinGW GCC

Pros
  • MingGW integrates well with Eclipse CDT.
  • Works more natively with Windows.
  • Most libraries build fine with MinGW.
Cons
  • It was supposed to be able to build FLTK, but I tried a few times and could not get it to work.
  • In order to run Make files you also have to install MSYS, which is a minimal shell.

MSVC, Microsoft Visual C++

Pros
  • MSVC is a high quality compiler.
  • Most used compiler under Windows.
  • There is a free Express version.
Cons
  • There seems to be some restrictions of the Express version that I did not quite understand.

Choice of compiler under Windows for ShapeLogic C++

MSVC.

C++ IDEs under UNIX

The candidates I considered were:
  • Eclipse 3.4
  • Emacs / Xemacs
  • NetBeans 6.1

Eclipse 3.4

Pros
  • Eclipse 3.4 CDT has a good debugger.
  • Easy to jump from classes to files defining the classes.
Cons
  • Not nearly as good as Eclipse for Java.
  • Unstable under Linux AMD64.

Emacs

Pros
  • Emacs is powerful tools that runs in a terminal.
  • Takes up less resources.
  • Not dependent on Java.
Cons
  • The Java bases IDE have more features.
  • Demands more knowledge to use.

NetBeans 6.1

Pros
Cons
  • It is made to work with Make files, and ShapeLogic C++ is using Boost Build / Bjam.

Choice of IDE under UNIX for ShapeLogic C++

Eclipse.

Summary of libraries and tools used

Status of ShapeLogic C++

ShapeLogic C++ 0.4 is the first alpha release. It can do some useful work, but it still mainly an example application.

Currently has
  • Comes with some image processing operation
  • Comes with 3 brushes
  • It is pretty simple to program an image processing algorithm
Missing
  • Drawing is currently slow and there is only one pen size
  • None of the ShapeLogic Java algorithms have been ported yet
  • Documentation is poor

Hardest problems

  • Learning how FLTK works
  • Building a cross platform C++ build script covering several libraries
None of these problems will effect ShapeLogic users.

Porting computer vision code from Java to C++

Before I started porting ShapeLogic from Java, I thought that C++ was moving towards becoming a legacy language. What I have learned from this work is that C++ has advanced substantially since 2002, when I last used it professionally. C++ still seems competitive, at least in computer vision, and according to my old video game colleagues also in games, where I though that C# might have taken a lead by now. Both C++ and Java have substantial advantages.

C++
  • OpenCV has a lot of vision algorithms, e.g. face recognition
  • C++ is faster than Java
  • Better for video processing
  • Programs are shorter
  • Generic programming working on primitive types
  • You can make build script that build under both Windows and UNIX
Java / ImageJ
  • ImageJ has more open source algorithms for medical image processing
  • Better support for medical image files formats under ImageJ
  • IDEs are better under Java
  • Build process is simpler than C++
  • Simpler language
  • Better support for parallel processing
  • A lot easier to dynamically load plugins
The next step is to port my framework for declarative programming -- it is based on lazy streams -- and port the Color Particle Analyzer. C++ / Boost have good support for functional programming techniques: Boost.Bind and Boost.Lambda, and the Phoenix library has just been accepted into Boost. When complete, I will do another posting about how it went.

-Sami Badawi
http://www.shapelogic.org

Tuesday, September 2, 2008

Computer Vision C++ vs Java review

In 2007 I created an open source computer vision project, ShapeLogic, built in Java to work with ImageJ. This setup has been very easy to work with and very productive. Bjarne Stroustrup the creator of C++ gave an interview about the new features in the C++0x standard and TR1. C++ now has a lot of innovating programming constructs e.g. template meta programming, lambda functions, concepts and traits. When I found out that "axiom" is going to be a keyword in C++ my inner mathematician demanded that I take a second look at C++ in connection with computer vision.

This post is a review of my personal past experience with computer vision in C++ and Java. I did my masters thesis in computer vision in the early 90ies, but I ended up working in other fields: video games, Internet and finance, which only left a little time to do vision in my free time. While both C++ and Java were good choices for professional vision programmers, several of the approaches I chose caused me to run out of steam. I also tried to do computer vision with functional, declarative and hybrid languages e.g. Oz, Scheme and Scala but will not cover that here.

Borland C++ early 90ies

C++ did not have STL or any other standard library so I used Borland's OWL library for images and for the application. I used C++ templates, classes with multiple inheritance, RTTI just to set up basic container functionality. There were a few books that has some free C or C++ source code for image processing and vision, but they did not spawn a user community. I did not really get to do anything interesting.

JAI, Java Advanced Imaging late 90ies

I was very excited when Java came around, this was the language to cure all programming ailments. Now they had added a library that could be used for vision and a lot of big companies were sponsoring JAI. It turned out to be a very complex framework with a deep class hierarchy, I spent a lot of time reading the manual trying to find out how to get access to image pixels. I gave up using it and the framework never gained much popularity.

VXL, C++, STL, Boost, Python, GCC, Linux around 2000

Open source software, OSS had started to become prominent. There were 2 OSS libraries:
  • OpenCV (Open Computer Vision), wich was still in alpha.
  • VXL (Vision X Library) wich was a merge of 2 big non OSS libs TargetJR and IUE.
VXL finally got into beta and I tried to combine it with Python for more high level processing.

Tools needed for build and GUI
  • VXL does builds using CMake to create Make files
  • Boost uses BJam to do builds
  • Python bindings using Pyste from Boost
  • VXL used FLTK and OpenGL as a GUI
Problems encountered
  • It was hard to get the different build systems, CMake, Bjam and Make, to work together
  • GCC 3.1 and 3.2 core dumped when compiling certain Boost classes
  • Python bindings worked for simple C++ classes, but not for the nested template classes in VXL
  • It was hard to debug the template programs
  • Emacs was not really as easy to use as Visual Studio
  • Bad drivers for OpenGL on Linux
I actually got some examples set up, but spent more time fighting with the tool stack than doing vision work.

ImageJ in Java around 2004

A colleague showed me a visualization tool he had worked on and said that he did it in around 1 month. I barely believed him, but tried the underlying framework, ImageJ. To my big surprise I was up and running and doing real work in a few hours. ImageJ just got things right. It was built using pure Java by one man, Wayne Rasband. It is very easy to work with and very modular, so a lot of people have made plugins and there is a vibrant development community. When I started working on ShapeLogic that was the best choice.

OpenCV, GIL Generic Image Library, Boost and Eclipse in C++ 2008

In the light of advance in the C++ language and tools, I have decided to try it again.
C++ image libraries choices
I chose to start with OpenCV made by Intel and GIL made by Adobe but a part of Boost since 1.35.

C++ IDE tried
  • Eclipse 3.4
  • NetBeans 6.1
Eclipse worked better for me, it has its own build system so you do not have to mess with Make files.

C++ cross platform GUIs Not sure which one will be best for my purpose.

First attempt
I tried Boost, OpenCV and GIL and got them up and running under both Linux and Windows in a few hours. Eclipse CDT C++ IDE works great.

Porting ShapeLogic algorithms to C++ version

My plan is to port some algorithms from ShapeLogic from Java to C++. ShapeLogic is a toolkit for declarative programming, specialized for vision. In principle you should be able to make a list of rules for categorizing say the shape of a particle in a particle analyzer. You put them in a database or a flat file and the same rules should work for C++ and Java version of ShapeLogic. In practice this might not work out.

Advantages of C++ and Java

This is a loose first assessment.
Constructs used in ShapeLogic that are missing or less convenient in C++
  • Uniform cross platform GUI
  • Dynamic cross platform libraries
  • HashTable
  • Reflection
  • Garbage collection
  • Antlr for parsing logic language
Advantages of C++ over Java in vision
  • Substantially higher speed
  • Better handling of video
  • Used more frequently for computer vision programming
  • Good tracking and face recognition algorithms in OpenCV
For me, Java has been very good for doing medical image processing algorithms. I have heard conflicting evidence about whether it is feasible for doing computer vision on video using Java. Video handling in Java has been bad up to now, this is supposed to be fixed with the new JavaFX. Shadow Monsters is a computer vision based art piece taking video footage of silhouette of the viewer and adding monsters to them, I saw it on display at Museum of Modern Art. It was programmed using Processing, which is a Java based image processing tool for artists. I discussed the issue with a computer programmer / artist who said that he had tried to do a motion algorithm in Processing and had to port it to C++ based Openframeworks since Java was too slow. After being discouraged by my prior attempts to do vision in C++, I am very happy to see the dramatic developments in C++ and see if it is suitable for a simple port of ShapeLogic algorithms. The result of this C++ port will be covered in 2 postings:

-Sami Badawi
http://www.shapelogic.org

Monday, July 7, 2008

ShapeLogic 1.2 with color particle analyzer released

Here are the release notes for ShapeLogic 1.2

Changes

  • Particle analyzer working directly on color and gray scale images without manual user intervention
  • Both particle counter and particle analyzer now take parameters and print reports about each particle's color, area, standard deviation to result table
  • Color replacer replaces one color within a tolerance with another color. Parameter input dialog with preview check box
  • Organize plugins and macros under ShapeLogic? and ShapeLogicOld? menus, until 1.1 they where all placed under shapelogic menu
  • ShapeLogic still has beta development status
The particle analyzer in ShapeLogic v 1.2 has gone through limited
testing and seems to work well. There is still a bug in the edge
tracer.

Using particle analyzer as a ImageJ plugin

The particle analyzer was tested on the particle sample images from ImageJ embryos.jpg

embryos.jpg

To run it from ImageJ select "Color Particle Analyzer" in the ShapeLogic? menu:


First a particle count dialog is displayed:

Here is the result of running the non-customized particle analyzer on it. This is written to a result table that can be exported to Excel:

The categories for the particles are only examples, it is easy to setup different rules for categorizing particles. In ShapeLogic? 1.3 there will be custom rules to recognize specific cells.

ShapeLogic? 1.2 also contains the second version of a color particle counter. It also prints a smaller report of the particle's properties.

Plans for next release

The next release, ShapeLogic v 1.3, will be a more mature particle analyzer which will come with custom rules to recognize specific cells.

Seeking particle images

In order to create these rules, I am looking for images of particles on a relatively uniform background. Please let me know if you have sample images that I could work from, preferably standard images like the embryo sample image that comes with ImageJ.

Possible future plans for particle analyzer

  • Create rule for recognizing cells using neural networks or machine learning techniques
  • Be able to handle a background that is not uniform, and cell organelles
  • Incorporate reasoning under uncertainty using the lazy stream library
  • Find overlapping particles and distinguish them as separate
Download ShapeLogic 1.2


-Sami Badawi
http://www.shapelogic.org


Friday, May 9, 2008

ShapeLogic 1.1 with particle counter released

Here are the release notes for ShapeLogic 1.1

Changes

  • Particle counter working directly on color and gray scale images without manual user intervention
  • Particle counter finds average color, standard deviation, area and location for each particle
  • Framework to build more advanced particle counters and particle analyzers
  • Color clustering using K-mean algorithm
  • Background color finder
  • Extend all the image processing algorithms in ShapeLogic to work in both ImageJ and in plain Java
  • Better support for NetBeans
  • ShapeLogic still has beta development status
  • 29000 lines of Java code
  • 440 unit test that all works on local machine
The particle counter in ShapeLogic v 1.1 has gone through limited testing, and seems to work well though tweaking the parameters is still a bit clumsy. Users looking for a mature particle counter should probably wait for ShapeLogic v 1.2.

Test on sample images from ImageJ

The particle counter was tested on the particle images from ImageJ:

embryos.jpg

embryos.jpg. The un-tweaked particle counter in ShapeLogic 1.1 found

particle count = 9

embryos.jpg contains 6 particles and a few shadows.

After changing the parameter setting it found

particle count = 5

which is the correct value since ShapeLogic 1.1 cannot split overlapping particles.

Direction

This is the first use of ShapeLogic in medical image processing. The next few releases should also be focused on the particle counter, making it more robust and automatic. This is the plan for ShapeLogic 1.2:

  • More testing and tweaking of particle counter
  • Make it easier to set parameters for particle counter in a macro or a configuration file
  • Print report about each particle's color, area, standard deviation to a file
  • Different implementations of particle counters
  • Vectorize particles by tracing the edge
  • Filter particles based geometric properties of the edge using the same techniques as letter matcher

Download ShapeLogic 1.1

-Sami Badawi
http://www.shapelogic.org

Friday, March 7, 2008

ShapeLogic 1.0 with stream based rules released

Here are the release notes for ShapeLogic 1.0

Changes

  • Rule for image processing have been migrated, previously they were implemented as goal driven tasks with sub tasks. Version 1.0 uses lazy streams which are simpler and more powerful.
  • Letter match example now matches all polygons instead of just the first found.
  • When running ShapeLogic as ImageJ plugin, it is now easy for users to define rules for matching in external Java files.
  • New number matcher to demonstrate how to define rules for matching in an external Java file in 130 lines of code.
  • Enabled use of Java 6 Scripting for rule database, which gives the user access to the 25 scripting languages that are supported
  • ShapeLogic now has beta development status
  • Many unit tests added for Lazy Stream library
  • Fixed bugs in Lazy Stream library
  • Fixed bugs in vectorizer

Lazy streams features

  • Lazy streams can be named and defined based on other lazy streams
  • They work similarly to UNIX pipes or calculation Legos
  • They serve as your query construct, you can directly query them
  • A stream can be wrapped around an Iterator
  • A stream can be created from an input stream and a Calculation
  • They can be instantiated lazily, so you can load calculation networks independently
The lazy stream worked very well with the letter match. It started out as a functional construct, but with the named streams they got a more declarative feel to them.

The Calculation in the stream is using the same signature as Neal Grafter's Java 7 closure prototype. This might make integration with Java 7 easier.

User defined rules for number match

The most significant change is that it has become a lot simpler for users to define rules. Here is the start of DigitStreamVectorizer_ the number matchre in 130 lines of code. Notice that there is barely any setup code. It is almost only rules, defined in a very simple format.

public class DigitStreamVectorizer_ extends StreamVectorizer_ {

@Override
public void matchSetup(ImageProcessor ip) {
loadDigitStream();
}

public static void loadDigitStream() {
LoadPolygonStreams.loadStreamsRequiredForLetterMatch();
makeDigitStream();
String[] digits = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
LoadLetterStreams.makeLetterXOrStream(digits);
}

public static void makeDigitStream() {

rule("0", HOLE_COUNT, "==", 1.);
rule("0", T_JUNCTION_POINT_COUNT, "==", 0.);
rule("0", END_POINT_COUNT, "==", 0.);
rule("0", MULTI_LINE_COUNT, "==", 1.);
rule("0", CURVE_ARCH_COUNT, ">", 0.);
rule("0", HARD_CORNER_COUNT, "==", 0.);
rule("0", SOFT_POINT_COUNT, ">", 0.);

rule("1", HOLE_COUNT, "==", 0.);
rule("1", T_JUNCTION_LEFT_POINT_COUNT, "==", 0.);
rule("1", T_JUNCTION_RIGHT_POINT_COUNT, "==", 0.);
rule("1", END_POINT_BOTTOM_POINT_COUNT, "==", 1.);
rule("1", HORIZONTAL_LINE_COUNT, "==", 0.);
rule("1", VERTICAL_LINE_COUNT, "==", 1.);
rule("1", END_POINT_COUNT, "==", 2.);
rule("1", MULTI_LINE_COUNT, "==", 0.);
rule("1", SOFT_POINT_COUNT, "==", 0.);
rule("1", ASPECT_RATIO, "<", 0.4);

ShapeLogic's 3 different approaches to declarative programming

Here is a chronological listing of ShapeLogic's 3 different approaches declarative logic:
  1. Declarative goal driven logic engine. From ShapeLogic 0.2.
  2. Logic filter language. From ShapeLogic 0.8 The syntax and development of the logic language is better described in Logic language.
  3. Lazy streams. From ShapeLogic 0.9.

Result of different approaches so far

For the letter matching example, the lazy stream approach has been both simpler and more powerful than the goal driven logic engine.

The Artificial Intelligence choice tree is built into the logical structure of goal driven logic engine, so this approach might work well when reasoning under uncertainty.

The logic filter language is used with both lazy streams and goal driven approach.

ShapeLogic is a toolkit, all 3 approaches are available with unit tests.

For now development is focused on the lazy stream approach.

JSR 223 scripting surprise

I had put a lot of energy into making it easy to create a stream from a Scripting snippet in either Groovy, JRuby or JavaScript. This was clearly superior to text snippet rules defined using Apache Commons JEXL under the Declarative goal driven approach, but using the new Stream it turned out not to be necessary. The rules could easily be defined in plain Java. I still think that good integration with streams and Scripting from ShapeLogic might turn out to be useful.

Download ShapeLogic 1.0

-Sami Badawi
http://www.shapelogic.org

Tuesday, January 29, 2008

Lazy streams in mathematics and vision

ShapeLogic 0.9 contains new functional and declarative constructs
  1. Lazy streams
  2. Simplified and expanded lazy calculations
The functional and declarative construct of ShapeLogic can be used independently of the image processing code. It only requires a 200 KB jar file to use this in other application, and there is no dependency of third party jars.

ShapeLogic 0.9 letter recognition example is still using a different system for declarative programming. More on that later in this post.

To test lazy streams in pure form I tried them on the 10 first mathematical problems in Project Euler. I think that ShapeLogic streams provided for simple solutions to the mathematical problems.
However they are more verbose that say solutions in the Scala language:
http://scala-blogs.org/2007/12/project-euler-fun-in-scala.html

Solutions to a few of the Project Euler mathematical problems

Project Euler is a list of 178, mathematical problems, that can be solved by computers.

1 Add all the natural numbers below 1000 that are multiples of 3 or 5

NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,999);
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(naturalNumberStream) {
public boolean evaluate(Integer object) {return object % 3 == 0 || object % 5 == 0;}
};
SumAccumulator accumulator = new SumAccumulator(filter);
System.out.println(accumulator.getValue());

2 Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million

BaseListStream1<Object,Integer>fibonacci = new BaseListStream1<Object,Integer>(){
{ _list.add(1); _list.add(2);}
public Integer invoke(Object input, int index) {return get(index-2) + get(index-1);}
};
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(fibonacci) {
public boolean evaluate(Integer object) { return object % 2 == 0; }
};
SumAccumulator accumulator = new SumAccumulator(filter) {
{_inputElement = 0;}
public boolean hasNext(){ return _inputElement <= theNumber; }
};
System.out.println(accumulator.getValue());

More solutions to Project Euler


Here are the next 8 solutions:
10 first solutions to Project Euler in ShapeLogic
10 first solutions to Project Euler as Java unit tests

Comparison between streams and old declarative constructs

In ShapeLogic 0.8 a cornerstone in declarative programming was a goal driven system of tasks with sub tasks. The letter recognition example reads in a rule database and translated it into goals/tasks with sub tasks. Somewhat like the programming language Prolog.
In case of uncertainty the different choices would live in an artificial intelligence choice tree that is tied to the tree of tasks and sub tasks.

Integrating old declarative constructs with lazy streams

Based on what is needed in the current letter match example. It seems like the stream based approach is simpler and able to handle all the problem that the goal driven approach could.
I expect the stream approach to supersede the goal approach.
The rule database will be read and translated to streams. So the rule for the letter A would be translated into a filter that could filter a stream of polygons into a stream of polygons that represent the letter A.

Also currently the rules now are using JEXL to translate a text rule into something executable.
Example:
Rule for letter A: polygon.holeCount == 1.
In ShapeLogic 1.0, you should be able to use Java 6 Scripting, JSR 223, to be able to define these rules, in one of the 25 supported scripting languages. In ShapeLogic 0.9: Groovy, JRuby, and JavaScript was tested with streams, but not with the rule databases.

Using streams for concurrent programming

Streams can also support parallel or concurrent programming, which is important with the CPU intensive operations in image processing and computer vision. Especially with the advent of cheap multi processor machines.

Example: Find polygons in a stack of images

You define a lazy data stream for this and set a stream property
randomAccess = true
This indicates that individual elements can be calculated independently. The factory creating the stream could create a parallel version of the stream and assign each operation its own thread. Note that the result would be a stream of polygons for each image.

-Sami Badawi

Wednesday, January 23, 2008

ShapeLogic 0.9 with lazy stream library released

Here are the release notes, I will soon describe the changes in more details.

This is the first release where ShapeLogic is moving beyond current parameters as a plugin library for ImageJ, currently only used in a letter recognition example. The improved system will be for declarative programming where the user can define rules in either a database or flat file. The focus will still be on image processing and computer vision, but the system will be more broadly applicable. There has been no new work on image processing or letter recognition in this release. ShapeLogic 1.0 will combine these new changes with the current image processing code.

Changes

  • Introduce new functional, declarative and query constructs to Java
  • Implement lazy streams like Haskell, Scala or Scheme
  • These functional constructs are very lightweight and you only need one 200KB jar file to use it in other applications
  • Test streams by solving the first 10 mathematical problems from Project Euler
  • Enabled Java 6 Scripting for evaluating expressions.
  • Tested with Groovy, JRuby, JavaScript, but should work with other supported Scripting languages, currently that are 25 of these. This makes it possible for users to add rule, formulas and queries in real time using text format. They can interact with a running Java application, which can be useful in science, finance or web applications.
-Sami Badawi

Saturday, January 12, 2008

Lazy streams in Java, Groovy, JavaScript, JRuby

This is a follow up to my last blog: Functional constructs Java 7, Groovy, Commons

I have finished coding the first part of the lazy streams for ShapeLogic. They are going to be key for the declarative programming query interface to ShapeLogic. As a proof of concept I wanted to see how easy it would be to implement a lazy stream of Fibonacci numbers. So far I have tested my framework with definitions written in:
  1. Groovy
  2. JavaScript
  3. JRuby
  4. Java
It is essential that lazy streams are are easy to define so they can be put in a flat file or a database. I was very satisfied with the concise definitions of the Fibonacci streams in the different languages:

Lazy Fibonacci stream in Groovy

new FunctionStream("fibo","def fibo_FUNCTION_ = { fibo.get(it-2) + fibo.get(it-1) };",1,1);

fibo is the name the lazy stream has in the context / name space
fibo_FUNCTION_ it is a naming convention that the function that is use to create the stream has this name
1,1 is the first part of the lazy stream

Lazy Fibonacci stream in JRuby

new FunctionStream("fibo","jruby",null,"def fibo_FUNCTION_(it) return $fibo.get(it-2) + $fibo.get(it-1) end",1,1)

Lazy Fibonacci stream in JavaScript

new FunctionStream("fibo","javascript",null,"function fibo_FUNCTION_(it) { return parseInt(fibo.get(it-2) ) + parseInt(fibo.get(it-1))};",1,1);

Scripting using JSR 223

I added a formula language for users to an enterprise Java system a few years back using Antlr and BeanShell. JSR 223 is dramatically easier to work with, but there are still some problems.

The only scripting language that works out of the box with Java 6 is JavaScript. To get others to work you have to download jsr223-engines.zip from:
https://scripting.dev.java.net/servlets/ProjectDocumentList
For each language you want to use there is a engine jar file.
E.g. jruby-engine.jar.
They have to be on your path. So does the jar file implementing the language.

JSR 223 and Maven 2 problems

JSR 223 does not work well with Maven 2. The engine jar file does not reside in the Maven repository so you have to separately install them into you local Maven repository. Here is the command to install JRuby:
~/bin/maven-2.0.8/bin/mvn install:install-file -Dfile=jruby-engine.jar -DgroupId=org.jruby -DartifactId=jruby-engine -Dversion=1.0.1 -Dpackaging=jar

Scripting languages currently under JSR 223

beanshell, browserjs, ejs, freemarker, groovy, jacl, jaskell, java, javascript, jawk, jelly, jep, jexl, jruby, jst, judo, juel, jython, ognl, pnuts, scheme, sleep, velocity, xpath, xslt.
These languages should in theory work with ShapeLogic, without any additional code.

Other implementations of lazy streams

  1. BaseStream: That is the abstract base class with most of the lazy stream functionality
  2. IteratorStream: Generates elements using Java Iterator
  3. TransformerStream: Generates elements using Java interface
  4. FunctionStream: Generates elements using JRS 223 as described above

Next step for functional constructs for ShapeLogic

  1. Filter that is easy to define in external text using scripting
  2. Transformer transforming one lazy stream to the next
  3. Query interface from where a result can be retrieved
-Sami Badawi

Wednesday, January 9, 2008

Functional constructs Java 7, Groovy, Commons

What functional constructs to use for ShapeLogic

I have started to code the lazy streams for ShapeLogic. They are going to be key for the query interface to ShapeLogic. I need some functional constructs to work with these. The top sources candidates are:
  1. Apache Commons
  2. Groovy
  3. Java 7
  4. Hand coding
None of these are a perfect fit. This post list some of the advantages and disadvantages of these.

Apache Commons functional constructs

I am currently using Apache Commons JEXL for user expressions.
  1. Apache Commons do not use templates
  2. Apache Commons Functor are still in the sandbox and not actively developed
  3. The code is not uniform
  4. You cannot make user define functions in Apache Commons JEXL

Groovy functional constructs

I need to use a scripting language, to define user functions.
  1. Groovy contains all of Java's constructs
  2. Groovy comes with good functional constructs
  3. I like the Groovy syntax for using these
  4. I cannot use these expressions directly since Groovy is not a lazy language

Java 7 functional constructs

Java 7 comes with good functional constructs.
  1. There are a lot of interest for functional constructs in Java 7
  2. I would rather use Java 7 than compete with it
  3. Java 7 still seem to be pretty far away
  4. It is not sure that closures will make it into Java 7

Thoughts on immutable constructs

I will probably make the convention that a lazy stream like the Fibonacci numbers are immutable, but not enforce this by making a LISP list.

Scala envy

Now I suffer from Scala language envy. These Scala language features would come in handy now:
  1. Lazy streams
  2. List comprehension, with same syntax for lists, iterators and streams
  3. First class function
  4. Closures
  5. Lazy calculation
  6. Uniform access to functions and lists
I could of cause try to include the scala.jar and directly use the Scala constructs in ShapeLogic, but there lay the road to madness.

Hand coding functional constructs

This might not be too much work, but I would rather not create yet another implementation of functional constructs. Apache Commons Functor never took off, despite some good press. That is probably an indication that Java was not that well suited for elegant functional constructs when this library was made, and maybe still isn't.

Current work plan

  1. I will start by implementing a lazy Fibonacci stream
  2. Then I will move the polygon finder to a lazy stream, before it could only find one polygon
I will try to get ShapeLogic 0.9 out soon, even if it is a very limited version.

If you know of any libraries that would fit my need and not be too heavyweight, please let me know.

Two Fibonacci implementations

The Haskell language has an incredibly elegant lazy stream implementation:
fibs :: [Int]
fibs = 1 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Drools Fibonacci implemented. This is not a good fit for my computer vision project.

-Sami Badawi

Saturday, January 5, 2008

Good resources about generating a Site and Documentation in Maven 2

The ShapeLogic project site is generated with Maven site generation tool.

I am trying to customize the ShapeLogic site a little more. Unfortunately the documentation for using Maven site generation tool is very spotty, but Eric Redmond has made 2 great resources about this:

His online Maven 2 book:
http://propellors.net/maven/book/site-generation.html

His blog entry:
過労死 Death by Overcoding: Generating a Site and Documentation in Maven

Now the whole ShapeLogic site is generated cleanly with this command:
mvn clean site
Before you manually had to copy the directories: images and css

-Sami Badawi

Wednesday, January 2, 2008

ShapeLogic for general declarative programming

ShapeLogic 0.9 is going to be the first release where users define rule sets read from either databases or flat files. I have decided to broaden the scope of the project.

First I hoped that I would be able to make minor adjustment to ShapeLogic's letter match example so that it would read the rules from an external source and gradually expand. But since backward compatibility is not a problem yet, I came to the conclusion that it was better to try to construct a solid foundation for declarative programming. While it will be primarily geared toward computer vision problem solving, the system will have other, broader, applications as well.

Do we need another system for declarative programming?


SQL rules supreme in the field of simple data, but once you go outside this field there are many different directions that you can take.

The declarative logic programming system that I had highest expectations for was CYC. It is a large, hand coded knowledge base trying to capture common sense, using many different inference techniques. Strangely, it never got a big following even after they released part of the engine as open source.

I hope to find a sweet spot where a simple system will be able to do some real work and be simple to learn. My work is geared toward a domain where there are a limited number of objects with somewhat constant features.

A few of the changes in ShapeLogic 0.9


Lazy data streams


Implement lazy data streams like Scala or Scheme.

Decouple annotation


Make the annotation of shapes more loosely coupled to classes in ShapeLogic. I was not super happy with the first solution that I came up with of how to annotate point, lines and polygon.
If ShapeLogic should be used for more general problem this is completely unacceptable.

Better interpreter


I order to save user defined rule in a database or a flat file, I need to be able to compile or interpret this code. This code in the rules should mainly be fairly straightforward.

The top contenders are:


  • Java 6 Scripting interface, that should give access to different scripting languages for the JDK

  • Java 6 Compiler interface, the problem is that Java is pretty verbose

  • Groovy intepreter

  • Do the parsing in ShapeLogic and write a little interpreter

  • Stick with JEXL for now, and make the move in a later release



-Sami Badawi