VCLib Documentation  6.12.2

Efficient Programming of Image Processing Programs

Efficient Programming of Image Processing Programs

Image processing involves relatively large amounts of data. A video image of the size 512×512 pixels requires 256 kByte of memory, an image with 740×574 pixels requires 415 kByte, and a high-resolution image of the size 1024×1024 pixels even requires 1 MByte of memory. This fact naturally affects computing time. Let's assume some format-filling image operation requires only one microsecond per pixel. Then, a 512×512 image requires 262 ms, a 740×574 image requires 425 ms, and a format of 1024×1024 requires around 1 s. This is unacceptable in many cases, especially in industrial image processing. Naturally, one can try to work around this problem by use of faster and faster processors. On the other hand, technical progress which produces faster processors also produces higher-resolution sensors. This comparison illustrates the problem well. If the clock rate of a processor is doubled, it will work twice as fast (assuming a double-speed memory). However, if the format of a sensor changes from 512×512 to 1024×1024, this is four times as much. For this reason, there are some rules for developing fast image processing programs.

The following techniques are covered below:

  • affip
  • uop
  • upwaasap
  • ttepmcb
  • urlcfbi

Avoid format-filling image processing

In most cases, it is not necessary to evaluate all pixels of an image, even though their existence, i.e., a high resolution, is often very useful. Numerous examples will be provided below which illustrate how this can be done. Knowledge of the problem to be solved is of vital importance. If certain pixels are unimportant for a particular task, then they do not need to be evaluated. With this method, the computing speed can often be increased several thousand times.

Methods for avoiding format-filling image processing

The following methods are covered below:

  • aoi
  • fhr
  • odiotdip

Areas of Interest

This procedure limits itself to the relevant image sections (windows, areas of interest). E.g., in a relatively large image section first the position of an object could be determined. Depending on this search, much smaller windows are calculated. The presence, for instance, of a bored hole or a bar code could be evaluated with these windows. This relatively simple procedure often increases speed considerably. Remember that the number of pixels in a square window increases with the square of the length of one side. A window with a side 100 px long has an area of only 10000 pixels, while one with a side of 1000 px has an area of a million pixels. That is one hundred times more!

Forgoing high resolution

Some operations do not need the full resolution of the image. As an example, if you want to look for an object which a certain known minimum size, then it suffices to include every other, every fourth, or more generally every nth pixel in the search. This effect can be used horizontally as well as vertically, so the acceleration is n2.

One dimensional instead of two-dimensional image processing

One-dimensional image processing includes the following procedures:

  • Edge sampling - a sudden change of brightness is located along on a line (one-dimensional).
  • Contour following - the contour of an object is a one-dimensional structure, even if it is very jagged due to poor image quality.

For edge sampling, the maximum number of pixels to be examined is the number of pixels in the image diagonal (and it is only this number under difficult circumstances). As a rule, a few hundred pixels are evaluated in such cases.

For contour following, experience shows a few thousand pixels are evaluated (in seldom cases, up to ten thousand pixels).

In both cases, the number of pixels to be evaluated is much less than for a full frame, even though the algorithms used here are often somewhat more complex.

Use optimized programs

The programs included in the library described here are almost all highly optimized assembly language programs. Thus, in many cases it pays to find a way to create the desired image processing program from library calls, even if the required algorithm cannot be found in the library. In most cases, this is better than writing your own program in C.

Use processes which are as simple as possible

Complicated algorithms tend to require a lot of processor time. If this is not possible, at least try to use a combination of simple steps.

To the extent possible, make calculations beforehand

Many calculations can be made beforehand, and the results can be saved in tables. This includes, for example, trigonometric functions which can be calculated from a table faster than from an algorithm. Also, in many cases image coordinates can be converted to video memory addresses beforehand.

Use run length code for binary images

Many programs in this library work with run length code (described in detail below). In many cases, the use of run length code (specifically for binary images) can increase the evaluation speed several fold. Only the function which creates run length code from a gray-scale image requires some processing time.