Objectives

My primary goal was development of a new vectorization algorithm for the edge detection. The Outliner project is a test ground for this algorithm – it should help to refine the idea of contour dots, and provide the window through which I can look at the algorithm’s work and estimate it.

After publishing this project, everybody else can also participate in refining this particular edge detection algorithm, or just estimate it, or find a practical usage.

In this project I pursued the combination of both accuracy and performance. For the sake of accuracy, the averaging matrix is calculated from the analytical formula, and the real numbers are used. For the sake of performance, the STL library is not used in the classes that make intensive calculations over pixel data: Calculator, SubpixelInfoProvider, Booker.

Portability

This project was designed on 32-bit Intel machine, Windows XP, and using Microsoft Visual C++ Express.

I have not paid much attention to portability. Although, the classes that perform calculations should be easily ported, because they are written in C++ without assembly code, and they do not have calls to WinAPI, except for drawing.

It seems, the porting to 16-bit processors do not have sense, because the processor should be quite powerful for extensive calculations.

In porting to 64-bit processors, the constant kMagnificationBit can be made bigger, thus reducing the rounding errors. Also the attention should be paid to the size of SubpixelInfo structure because it influences the memory footprint of the application.

Files and Classes

There are standard files created by the AppWizard of Visual C++, see the “Readme.txt” for details. There are also the project specific files that implement the Outliner functionality.

The file outliner.cpp is a collection of C-functions that are the glue code between the UI and the calculations. Its counterpart file outliner.h is not very interesting; it remains untouched from the time of its creation by AppWizard.

The project specific files are organized into classes. In most cases these are the simple classes (without the base class) that have the declaration in the header file (*.h) and the implementation in the single (*.cpp) file. The names of files are the same as the name of classes.

There are three exceptions though.

1. The file IBitmapPicture.h is the interface to the some functionality of class Picture. I believe that this interface can facilitate the porting of Outliner to other platforms.

2. The implementation of VectorSketch class is spread between two files: VectorSketch.cpp and VectorSketch_Save.cpp. The last file contains only the methods that save information in various vector formats.

3. The files Utilities.h, Utilities.cpp contain a collection of the global C-functions. These functions help to visualize the various transformations of the bitmap picture.

Description of Classes and Structures

· Picture – plays two roles, and ideally it should be separates into two classes. The first role deals with bitmap image: loading file, providing IBitmapPicture interface, drawing and saving the bitmap picture and its transformations. The second role is building the VectorSketch in Calculate() method, and be the mediator between UI and VectorSketch class.

· ThresholdingIterator – sequentially checks every pixel of the gradient, and returns those coordinates where the gradient exceeds the threshold and that were not covered by the existing contour dots.

· Booker – the booking agent that marks the sub-pixels as occupied by contour dots. This information is important for the closed strokes, and for skipping the processed pixels by ThresholdinIterator. This class uses a custom memory management instead of std::deque, for the sake of performance.

· VectorSketch – the result of calculation of outlines. Now it is just a collection of strokes.

· Stroke – a curve that goes along the line of biggest gradient. This curve is the edge between differently colored regions. It can be a closed loop or an arc with two ends. At the end the stroke cannot be extended due to several reasons: stroke bumps into the bitmap bounds; the gradient magnitude diminishes; there is a sharp turn of the gradient direction. In the Outliner project, the stroke contains the sequence of contour dots, and builds the curve using the information in contour dots.

· ContourDot – is a central idea of edge detection. See “Contour Dots” document for details. It can be thought of as an intelligent object that can adjust its position to the centerline of the edge, and also can find a place for the neighbor contour dot, thus extending the stroke.

· SubpixelInfo – the structure contains some processed picture information: the smoothed color values (see “Smoothing” documents for details), the squared gradient (a, b) of the smoothed colors (see “Gradient” document), and the booking marks. This information is calculated at twice the resolution of the original bitmap, at integer (x, y) coordinates and at the half-integer coordinates also.

· SubpixelInfoProvider – the class that calculates SubpixelInfo at the given coordinates when it is necessary. Note that, for performance reason, the calculation is not performed in coordinates that were not requested.

· Calculator – the class that contains the calculation of the contour dots, split into several operations, and save the intermediate results that are passed from one operation to another.

· BufferKeeper – the class that provides a reusable buffer of sufficient size. It is used in Calculator class instead of std::vector, for performance reason.

ToDos, Problems and Proposals

This section contains some considerations of various importance. Some of them can be implemented in the Outliner project, others will be left unimplemented or there is need to create separate projects for them.

1. Split the “Picture” class into two.

2. Make a satisfactory implementation of SaveToVML(), or else delete the VML from the Save Outlines dialog.

3. Save outlines to more vector formats.

4. Performance of vector drawings on screen.

5. Support the mouse wheel.MirroringCrescent

6. Find the better algorithm for outlining the small object, and more accurate at the ends of the strokes. The problem is seen on the picture of mirroring crescent – at the corners and in the center. (see picture at right, also the icon 128x128 of the Outliner utility).

7. Find the meeting points of strokes. The most important case is T-shaped meeting point (the case of three overlapping smooth objects, like circles).

8. Make the picture segmentation. Connect the adjacent strokes into the closed loop around the smooth colored region. Note, there is currently unused function SubpixelInfoProvider:: UpdateGradientABCustomColor() that can be handy. But this functionality requires some investigation.

9. Devise the algorithm of comparison of the two strokes that were built from the two different pictures. Just consider that there is a circle on each of the two pictures. The stroke, that outlines this circle, will be a closed loop of the contour dots; or we can regard it as a polygon. On the other picture, the polygon will be similar by the view of the human eye, but mathematically has slightly rotated vertexes. What calculation should do the application in order to come to the conclusion that these two strokes are equivalent?

10. Make the two optimized versions of the Outliner algorithm – one is the utmost optimization for speed, using assembly language, fixed-point arithmetic and hardware accelerations; the other is the quality optimization. It is assumed that in robotic missions, the fast algorithm will be used in traffic estimation during the movement of the robot; and the quality algorithm will be used for scrutinizing over the object of interest (some target).

11. Make the acceptable smoothing of strokes. If the stroke curve (or its segment) can be approximated with a straight line or other analytical curve, then we can throw away contour dots and describe the stroke with analytical formula. Please note, this would help in the high-level task to determine where the imaginary extensions of the two strokes will meet.

12. Apply to the algorithms of picture compression. The artifacts of JPEG compression are the greatest at the edges. Incorporation of the outline information into the JPEG format can mitigate those artifacts.

Last edited Nov 25, 2010 at 8:32 PM by wladik, version 1

Comments

No comments yet.