Directed Research
LOIS for an Embedded Linux System
Ryan A. Dibble
&
Sridhar Lakshmanan
21 Apr 2000
12 Jul 2000
Department of Electrical and Computer Engineering
The University of Michigan -- Dearborn
Evergreen Road, Dearborn, MI 48128-1491 USA
Tel: (313) 593-5420 Fax: (313) 593-9967
Overview:
Lane tracking is a deeply studied problem in the area of intelligent vehicle systems. Here in the University of Michigan -- Dearborn Vehicle Engineering Labs it is approached as an exercise in image processing.
The main algorithm that uses a template approach to lane detection is called LOIS. LOIS is well designed but computationally intensive. Since its creation one of the goals has been to have LOIS run in soft real-time to allow for the creation of a LOIS lane departure warning "black box".
Originally designed on a Sun workstation LOIS was ported to the Microsoft Windows Operating System a few years ago to try to make use of emerging and inexpensive technologies that would allow it to run faster approaching the soft real-time frame rates. However, because of Microsoft Windows poor design and huge overhead, the outdated OS simply can not handle the task.
This project is to port the initial LOIS code to Linux. Once ported the code needs to be redesigned, modify, optimized for Linux, and finally installed on a Linux based embedded system. In doing so we have created a new edition of LOIS for Linux that runs exceptionally well! All development was done under Linux using the RedHat distribution. Only GNU / Open Source / Free tools (tcsh, vi, gcc, gdb, gprof, and Electric Fence) were used in creation of the Linux LOIS.
This document is a guide to the new Embedded Linux LOIS port. It is written to be read by someone who will be maintaining the source code in the future and needs an overview of what everything does. It is the document I never had.
Requirements:
The original directed research had two primary goals however as the project progressed the goals were expanded.
Porting the lane detection algorithm to the Linux OS
Creating an embedded system that runs the Linux OS and the LOIS algorithm in real time to detect lanes
The new expanded goals are in three phases. Phase 1 is the initial port of seqLois to Linux. Phase 2 refining the code using lessons learned in Phase 1 and implementing some changes. Phase 3 is creating the embedded system to run LinuxLOIS. The new goals:
Port seqLois to Linux
In porting keep in mind an orthogonal, objected oriented approach
Remove as much external dependency on the KGIL library as possible
Handle external input and output with ImLib graphics library which have been ported to numerous other operating systems (upgrade to ImLib version 2 if time permits)
Refine code and implement as LinuxLOIS with support for additional features
Combine seqLois with Real-Time video capture system into Linux seqLois.
Implement a caching system for likelihood function
Implement a new prior function for Lois
Implement a new lane departure warning system
Implement temporal correlation
Implement serial port yaw sensor data
Create an Embedded PC running LinuxLOIS.
Acquire hardware
Install RedHat Linux
Install LinuxLOIS software
Tune LinuxLOIS parameters
Architecture / Design:
The LinuxLOIS Embedded System has a hardware architecture of a standard Intel/AMD PC (motherboard,CPU,network,video capture,etc) -- but much smaller.
The LinuxLOIS Embedded System has a software architecture is divided into subsystems:
LinuxLOIS Core (custom design)
LOIS Algorithm Subsystem (custom design)
Temporal Correlation Subsystem (custom design)
Serial Data Input Subsystem (custom design)
Error Handling Subsystem (open source -- Ryan Dibble)
Timer Control Subsystem (open source -- Ryan Dibble)
Configuration Subsystem (open source -- Linux Terminal Server)
Frame Capture Subsystem (open source -- libbgrab)
Image File Access Subsystem (open source -- ImLib)
X Display Subsystem (open source -- ImLib)
The LinuxLOIS system makes use of some open source libraries to implement as many subsystems as possible. Most of these libraries come standard on a RedHat Linux 6.x install. The most important of these is ImLib which handles the complex tasks of the X Display Subsystem and the Image File Access Subsystem.
ImLib is an image library under Linux that is an advanced replacement for libXpm. It is released under GPL and has been ported to other operating systems (like solaris). Using ImLib will allow us to form an abstraction layer between our program and normal image I/O (such as image file loading, saving, and displaying). It allows us to forget about all things that go along with image displaying (zooming, dithering, color map, etc.), and loading/saving (file formats, compression method, etc.) and concentrate on what needs to be done with Image Processing. Taking this step to form this abstraction layer is important. It removes the necessity for the future LinuxLOIS programmers to understand and/or deal with the details of designing, programming, testing, and maintaining the I/O functions. This is critical since the I/O functions back end (file format, X resolution, etc) can change rapidly and unexpectedly in the computer world. Allowing for the independent open source maintenance of this layer of code frees future programmers to work on the algorithm itself.
The next open source library is the libbgrab-2.0 library which handles the Frame Capture Subsystem. This library interfaces with the frame capture kernel module (in our case the BT848) using the Video For Linux standard allowing easy portability between modules that support the V4L.
The final section that uses open source code is the Configuration Subsystem. This subsystem uses code encapsulated into library format from the Linux Terminal Server Project and is released under LGPL.
The Error Handling and Timer Control Subsystems uses code created by Ryan Dibble and others and is released under LGPL.
The remaining subsystems: LinuxLOIS Core, LOIS Algorithm, Temporal Correlation Subsystem, Serial Data Input Subsystem, are custom designed. The image processing in the LOIS Algorithm subsystem is done using custom code that assumed the image was in a KGIL (a custom designed image processing library) format. In most cases grayscale one byte per pixel. In order to make a smooth transition between the older code and the newer code image conversion is performed after I/O, but before the calls to the lois algorithm and the temporal correlation algorithm, and then again after before displaying or saving the results. The total overhead for these conversions is small compared to the amount of time spent inside the lois() function performing the algorithm itself. In addition the flexibility of using ImLib is a much needed relief.
Lois Directory Structure:
lois/Resources -- contains reference materials for libraries and software programs that are or at one time were used in the LOIS code base. It should also contain the original tarballs for open source code used in the project.
lois/serialData -- the code to read serial port data to be used with the encoded audio channel tapes that contain raw position information
lois/cameraCaptureMeteor -- the code to drive the raw video capture program for the matrox meteor frame grabber
lois/libgrab-2.0 -- the code to drive the raw video capture for the BT848 series chips
lois/gamma -- code that performs gamma correction on an image
lois/linuxLOIS -- the main LinuxLOIS directory
lois/linuxLOIS/bin -- the place for executables
lois/linuxLOIS/etc -- the place for configuration files (*.cfg)
lois/linuxLOIS/include -- the place for the header files (outdated)
lois/linuxLOIS/lib -- the place for custom libraries (outdated)
lois/linuxLOIS/src -- the source code tree
lois/linuxLOIS/src/kgil -- the source for kgil modified to remove some unneeded features
lois/linuxLOIS/src/disptool -- the source for the disptool (outdated)
lois/linuxLOIS/src/libcm -- the source for the cm library (soon to be outdated)
lois/linuxLOIS/src/old -- copies of older source files that have not been removed yet
lois/linuxLOIS/src/misc -- This is one of the most important directories. It contains the source code for the linuxLOIS program. It may also contain a few images and data files for easier development testing.
Details of Source Code Files within lois/linuxLOIS/src/misc
The source code is the misc subdirectory is broken into a couple of different pieces. This is an attempt to modularize the code. The files that make up the linuxLOIS program are: linuxlois.c eprintf.c config.c lois.c temporal.c serialdata.c and a few open source libraries. A few select files will be covered in more detail.
lois.c -- This is the main lois algorithm file. If someone were to want to look at the LOIS algorithm itself this is where to look. If someone were to try to port LOIS itself this file shouldn't have to be changed. The functions in this file are for processing a single image. These form a nice abstraction layer between the interface and the algorithm.
temporal.c -- This file contains the temporal functions. They store the values inside state structures and modify these accordingly based on the output for that frames call to LOIS. They are self contained and for a nice abstraction layer between the interface and the temporal correlation. Any modifications to the temporal code should take place within this file and it's header.
serialdata.c -- This file contains the serial data reader code. This code runs as a separate thread and updates the data structures that contain the information from the serial port yaw sensor. This information is then used in the main processing loop.
config.c -- This file contains the configuration functions. These functions allow you to read key value pairs from a configuration file. This configuration file is used to set the parameters on linuxLOIS.
eprintf.c -- This file contains the error handling functions. These functions take care of direct error messages, encapsulating error handling in commonly used functions and debugging messages.
linuxlois.c -- This file contains the interface code. If you wanted to change the interface for Linux LOIS you would replace this file with your own code. In the code it shows how to use the functions inside lois.c and temporal.c and ImLib to some degree. It starts the serial data reader thread, and the video capture thread.
linuxlois.c
The code begins execution in the main function, which is inside the seqlois.c source file. The code pseudocode summary is:
main() {
parse command line parameters
load configuration information
open log and output files
setup signal handlers
start serial data thread
init display, capture, lois, image_convert
while(!timetoquit) {
acquire source image
convert source to ImLib and KGIL if necessary
call lois
call temporal_prediction
create target image
draw parameters on target image
convert target to ImLib format
draw distance lines on target
save to disk if necessary
display info
}
display summary
stop serial data thread
deinit display, lois, image_convert
restore signal handlers
close log and output files
}
The parsing of command line parameters begin immediately after variable declaration and default value assignment. The parsing is done using the getopt_long() function contained in unistd.h. The getopt() function is the POSIX standard option parsing. getopt_long() implements the POSIX standard with the command GNU long format support as well. Option parsing is kept to a minimum where most the configuration choices are down within the INI style configuration file. The INI file is a simple setup using name value pairs.
Next the log and output files are opened and set up and the signal handlers are installed. Shortly afterward the default values for the temporal prediction configuration are set. At this point this is the only way to change these values. Hopefully this will change in some time. Finally after the configuration is set there is a call to temporal_prediction_init() that takes both the configuration and the state structure to initialize. This function will be discussed later.
The next step is to open the display if possible. Right now the X display must be present in order to allow ImLib to initialize. It is possible to initialize ImLib with a "fake" structure that has a static setup within it instead of using the one returned by XopenDisplay(). In order for this to work one must not use any of the "displaying" features of ImLib. This would allow ImLib to function only as a file I/O library. In the future an embedded system may choose to use this approach to eliminate the need of installing X. However, at this time in order to support debugging of the algorithm this has not been done since it is necessary to see the results. There are a few calls to XCreateWindow, XMapWindow, and friends that actually open the windows on the display. For more information read the main page on these functions.
Next the initialization of the global memory pool used in image conversion is done. This is done for speed. If at any time it appears there will be two of more threads that could call the image_convert_*() functions then these functions need to be rewritten to be thread safe. At this point the system model suggests that and threading will allow for additional devices to be looked at, which will not require image processing.
Now comes the big loop. This loop will continue until all the images in a file series are complete or, in the soft real-time capture mode, the SIGINT is sent to the process.
In mode 1 the images are read off the disk at this point using Imlib_load_image() that takes care of all file format and resolution problems. Leaving use with a pointer to the ImLib image structure. Within that structure are values like height and width, and there is a pointer to a block of RGB data values. At this point the scaling factors are adjusted for this image (allowing a file series with different size images to be processed correctly). Finally the image is converted to the grayscale KGIL format with image_convert_rgb_to_kgil_gray().
In mode 2 the image data is being written by hardware and a thread to a memory location in BGRA format. The first setup is to convert this format to the RGB data that ImLib understands and the grayscale KGIL format. This is done with the function image_convert_bgra_to_rgb_buf_and_kgil(). After that we make a quick call to ImLib function Imlib_create_image_from_data() to actually create the image structure. At this point it should be noted that when ImLib Version 2 is finished things will be much smoother. The internal structure of the ImLib 2 image data is the same as the video hardware and the capture card hardware aligned at 4 byte boundaries allowing for faster access. In addition ImLib 2 supports creating a shared data segment that can point directly to the memory begin used by the video capture card. ImLib 2 is then smart enough to know when it renders something to use the most recent data. This will make it so there is no need to convert from the BGRA format to the RGB format making the only conversion the BGRA format to the grayscale KGIL format.
At this point we have two things guaranteed. First that we have a ImLib structure that holds the correct information and that we have a KGIL structure that holds the grayscale KGIL image. One might ask why the program flow is not more serial in guaranteeing a valid ImLib structure and then converting it to a KGIL. The reason is you lose speed for the added clarity.
Next, after printing some information to the output text, is to actually call the LOIS() function. Then if the useTemporal flag is set to call temporal_prediction(), the LOIS() function takes an image, LOIS parameters, and likelihood parameters and returns a final likelihood as well as setting the values for the variable for curvature (k), vanishing point (vp), distance to left lane edge (Lb), distance to the right lane edge (Rb). The temporal_prediction() functions take a configuration structure (tpc), a state structure (tps), the five lois values (fin_lik,k,vp,rb,lb) and a flag lane_crossed. It updates tps with the new state information and changes any of (fin_lik,k,vp,rb,lb) to the new temporal adjusted values based on what the algorithm says, because of the current configuration and state.
Then a copy of the input KGIL image is created and the parameters are drawn over it. If the output image is being saved or displayed to the screen, the KGIL image is then converted to the ImLib format and an output image structure is created. Once this is finished the KGIL images are closed. Next if there is a need to draw distance lines on the output image the lines are drawn in place. If there was lane crossing then the lane crossing boxes are drawn.
At this point the output image (and/or input image) are saved if desired and displayed to screen if desired. The next little section of code calculates the time per image and then frames per second every couple of images. The program continues processing images until it is finished.
When finished it displays the images per second average, destroys the X windows, and closes out the X display. Then it deinits lois and the image conversion buffers. Finally it restores the signal handlers and closes the log and output files.
lois.c
The heart of the code is contained inside this file. It holds the code that performs the LOIS lane detection algorithm. This code is not written for clarity or for ease of understanding and there remains many gray areas of understanding. However it is highly optimized since that program spends 89% of execution within the function in the file. It is highly portable. If one ports a lois algorithm to any platform the code in this file should not need to be changed assuming KGIL is successfully ported.
In an attempt to create a more object oriented code the functions lois_init() and lois_deinit() have been added. They do not do much, but any changes should probably be added here. One top of those there are basically five more functions and a few support functions. The first is called pretreat(). This function does an average blurring of the image in 4x4 blocks. It is outdated and should be removed. Next is the draw_param() function, which given a KGIL image and the 4 lane shape parameters draw them on the image. After that is the PrewittMag() function, which performs the Prewitt image gradient computation. This was probably chosen because it is fast and easy to implement with a convulsion matrix. It is being replaced with the GradCalc() function that Karl is working with.
The next major function is the lik_fun2x() function which is the likelihood function for the road model. It takes five inputs: an image, curvature (k), vanishing point (vp), left edge (lb), and right edge (rb). With these is calculates a likelihood that those parameters match the feature in the image (note the image is the edge detected image not the original source image).
After that is Metropolis(). Metropolis is a method of minimizing or maximizing another function. In this case we want to maximize the lik_fun. The details of metropolis are beyond the scope of this document. Many other references exist for those who are interested. Metropolis basically takes a set of inputs that configure how it works and a set of inputs that are initial guesses to be passed on to the likelihood function while Metropolis runs to changes the initial guesses and tries to find better values. After a certain amount of time it returns the best likelihood it has seen and what the optimized guesses for the likelihood function were to produce that value.
The last function in the LOIS() function. This creates an abstraction layer between the interface and the workings of the lois algorithm. It takes an input image, some initial lane guesses, some image adjustment parameters, and a few flags and changes the k,vp,lb,rb values to the best fit that Metropolis() could produce. Along the way LOIS() preprocesses the image as necessary, runs it through an edge detection method, and finally calls Metropolis().
One major area for improvement in this code is to create more object oriented version of the LOIS() function that takes a lois data structure and a lois configuration structure. In addition it needs better comments. Until a fuller understanding has been gained, and the comments added, this is a terrible problem.
temporal.c
The functions contained within this file were written in about 2 hours one Saturday afternoon. The code is written in an object oriented fashion without static variables. There are two main structure that are needed in the code. The first is the temporal prediction configuration structure. This holds flags and settings that effect the way the temporal prediction is performed. One of these structures should be set with correct values before calling the initialization function and it would be wise not to change the values once the init function is called. Next is the temporal prediction state structure, which holds the current state of the temporal prediction algorithm. It would be unwise (and bad programming practice) to directly read or change state information outside of the temporal.c file.
The first function encountered is the regression() function, which is a slightly customized linear regression calculation that makes some assumptions about the data it is getting.
Next is the temporal_prediction_init() function. This function initializes the state structure based on the parameters in the configuration structure. Any type of memory allocation should be done in here. If allocation is performed there should be a temporal_prediction_deinit() function added that frees this memory. It would be good programming practice not to allocate or free memory outside of these two functions if the memory allocation pertains to the temporal_prediction code.
After this is the temporal_prediction() function itself. It takes a configuration structure, a state structure, and the lois parameters. Hopefully in the future the lois parameters will be encapsulated inside a structure and this function will be modified to reflect this change. It is this function's responsibility to modify, if necessary, the values of the current k, vp, rb, lb that will be used as the initial guesses the next time LOIS() is called. It does this by first adjusting the state information, moving stacks and queues, and recalculating moving averages of various types. It also calls the regression if necessary. Then it passes these values though a large bunch of logic that is still under development. Afterward it has predicted values. Then if the configuration says to it sets the values in the main() loop to these predicted value through pointers.
serialData.c
The serial data processing code is relativity simple when compared to the complexity of the LOIS algorithm or other subsystems. The important key to understanding this module is to realize that it runs as a separate thread in the whole program. The code is designed in an object oriented fashion. There are two primary objects implemented as C structures.
The first is the serial_data_config_t. This structure holds information about the serial port device including its name, its file descriptor, as well as its old and new terminal IO structure. The second is the serialdata_info_t. This structure holds the information after it has been read from the serial port and processed. If the type of information being gathered on the serial port were to change this structure would have to change to reflect the new information.
The modules also contains five functions. The first two serialdata_info_init() and serialdata_info_deinit() create and destroy the configuration structure. The init function is responsible for opening the serial port device, saving its current configuration, and setting it in the proper mode to read data. The deinit function restores its old setting. The second two functions serialdata_info_init() and serialdata_info_deinit() create and destroy information structures accordingly.
Since this module runs as a separate thread in the whole program the information structure contains a very important feature -- a mutex. A mutex acts like a lock protecting access to a shared resource, it is locked before data is read or written and unlocked afterward. In this case the mutex is protecting the information structure which is shared between this subsystem and the main core subsystem.
The final function, the serialdata_reader_thread() , is started by the main core code and acts like a separate program modifying the contents of the two structures passed to it. Since the main core has access to these structures the thread passes the information back to the main core through them.
The code in the serialdata_reader_thread() is straightforward. Until the thread is shutdown by the main core the reader loops. During the loop it reads in ten bytes of information from the serial port (if the data on the serial port were to change this number would change too). Once this information is read it verifies that the sync bytes are in the correct place. If they are not it reads one character at a time until it finds the sync bytes then goes back and waits for the other eight bytes of data. Once it has a full ten byte data set with the two valid sync bytes it processes them converting them to the correct format. Once converted it locks the mutex, stores the data in the information structure, and unlocks the mutex. Finally it sleeps a little while to allow for more data to be waiting at the serial port and repeats the process.
At any point the main core code can lock the mutex and read the latest up to date serial port data.
config.c
This is a small set of C functions that read in configuration file information into a structure. It is very immature and only supports a static amount of information. It uses linear search to find the value in a key/value pair. It does little error checking. The API is all but finished however and only the internal workings within the function will change. Future goals is to support configuration groups.
The basis of this library is the config_t type. This data structure holds a fixed maximum of key/value pairs, which can be thought of much like environment variables. There are a total of nine functions within this library. The first two config_init() and config_deinit() create and destroy config_t data structures. Next config_add(), which adds a single key / value pair to the config_t structure. This function does not check for duplicate keys and will just append whatever is passed into it onto the end of the array. Next is the config_read_file(), which parses a configuration file and calls config_add for each key/value pair found within it (The file format will be discussed in a moment.).
The next four functions functions begin with config_get_*() and retrieve information from the config_t structure. The primary function config_get() returns a pointer to the value string stored in the structure. The next two config_get_int() and config_get_float() call config_get() and convert the text string to the appropriate type before returning it. The final function in the set of four is config_get_char(), which is just a wrapper function to fit the naming convention of the previous two. Ideally an application would never call config_get() itself to allow the internal method of storing the value to be changed without breaking the program.
The final function is for support and debugging only and is called config_display(), which displays the contents of a config_t structure to stdout. It is useful to visually check that there are not duplicate key within the key/value list.
Future enhancements include options for case insensitive matching, duplicate key checks, and most importantly handling errors if a key is requested and is not present. At this point if a key is not in the list, and is requested, a core dump is highly probable.
eprintf.c
This subsystem comes from Ryan's Archive of Good Utilities after years of programming. It encapsulates single line debugging messages, low level error handling on memory allocation, and error handling in a single file.
The first function to know about is the setProgName(), which stores a string and is a static global variable that defines the program name to be used when reporting errors and debugging messages. Next is the setDebugLevel() function, which sets the debug level. Generally the higher the debug level the more information that is displayed. Debug level zero should have no debug messages and debug level one should have a minimal amount that only traces general program subsystem flow.
The error handling function is called eprintf(). It takes a first parameter an unsigned integer and the remaining arguments just like printf. Once invoked the function prints the program name, then processes the printf like parameters, and finally prints the contents of errorno (the system error number) and the system string error message. If the integer is zero then it returns to the code (useful for printing warnings) otherwise it exits with that value.
The next function is called emalloc(), which does the same thing as regular malloc() however it checks to ensure that memory was actually allocated and, if not, kills the program right on the spot.
Finally the dprintf(), or debug printf, function works similar to eprintf however the first parameter sets the debug level at which the message will be printed. If the debug level is below that value the message is not printed.
Tests:
The focus of this project is not to test the lois algorithm, which has undergone extensive testing in the past, but to create a new implementation on an embedded system. However the importance of testing can never be overlooked. Throughout the project verification and validation testing was done to compare the results of the new LinuxLOIS to the old seqLois program and fix any error that might appear.
In addition the linuxLOIS code and algorithm have been tested on a variety of road conditions from the video archives, still frame images from the image library, and even tested on live road.
Conclusion:
Overall this directed research has been successful. There now exists linuxLOIS that runs in soft real-time. It successfully processes 320x240 images at minimum of 5 Hz. (Other resolutions allow as fast as 15 Hz processing). The port attempts to break the LOIS code into separate pieces with clear abstraction layers to ease maintenance. To assist in that process the image I/O is all being handled with ImLib. All external dependence on KGIL has been removed and the only place it still exists is within the LOIS() function itself.
The video capture code has allowed for fast video capture at 30 frames per second without processing. This will place the speed burden on the algorithm not the video capture system. This capture code is isolated in a separate open source library with only a few function calls to be changed if a new capture device is to de used.
Other important algorithmic changes have been implemented that improve the algorithm performance: lik_fun() caching, a new prior function, temporal prediction, and a new algorithm for a lane departure warning -- all of which have been isolated is there section of the source code.
The performance and maintainability of the code has improved greatly from the previous versions. It is my hope that all people working on this project adopt this as a standard version.
Appendix:
...source code dump...