Mech - User contributions [en]

Serial communication with Matlab

2009-04-25T22:53:05Z

ScottMcLeod: /* Matlab Code */

== Overview ==
Matlab has a "serial" function that allows it to communicate through a serial port. This project is to establish serial port connection with the PIC microcontroller and demonstrate bidirectional communication between the PIC and a Matlab program. For demonstration purposes, the PIC will send digital potentiometer readings to Matlab as well as receive keystrokes from the Matlab user to light up LEDs on its circuit board.

A USB to RS232 adapter and level shifter chip were used to connect the computer to the PIC. In this lab, we used a cheap cable found at http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=220199148938&ih=012&category=41995&ssPageName=WDVW&rd=1

'''**Important! DO NOT connect the serial Rx/Tx lines DIRECTLY to the PIC!!!**'''

A level shifter chip is necessary to convert the high and low logic voltages from the desktop computer (+12V/-5V) to (+5V,0V) for the PIC. A standard RS232 connection is called a DB9 connector and follows the pin diagram shown here: http://www.aggsoft.com/rs232-pinout-cable/serial-cable-connections.htm
This cable requires 1 driver installation as included on the mini-cd. To install this driver, you must first plug in the USB cable, and run the installation program located on the CD corresponding to the model on the USB Cable (<CDROM>:\HL-232-340\HL-340.exe). This driver is also available online at this link:
http://129.105.69.13/pic/usb_drivers/HL-340_USB_serial_drivers_WinXP/ . To configure the Matlab script to connect to the proper serial port, use the device manager (Right click My Computer->manage) and expand the section "Ports (COM & LPT)". Make a note of the COM port number corresponding to "USB-SERIAL CH340" as listed in this section. In our program, our serial port was COM4. A picture is shown below of how to get this information in the device manager.

[[Image:ComPortLookup.JPG |thumb|300px|right| COM Port Lookup - Device Manager]]

A female DB9 connector was wired to our level shifter to convert the voltages, with the level shifter connected to our PIC. The female DB9 connector is used so no wires need to be directly soldered to the serial cable. Refer to the Circuit section for details on this connection.

The PIC was programmed with our C code as shown below. Our program was designed to read a potentiometer through the PIC's ADC (Analog to Digital Converter) port and transmit the digitized readings over the serial cable to the PC (upon request). In Matlab, if a users sends data to the PIC by entering a character, the PIC responds with the current potentiometer reading and the last received byte from the PC. The PIC is also programmed to display the character received from the PC on its LED array (D register) as a 8-bit ASCII number. The programs can easily be modified to create any custom protocol, but are designed to show simple 2-way communication between Matlab and the PIC.

== Circuit ==
The wiring diagram for serial communication is shown below. There are three basic components in this setup. The potentiometer serves as an analog input to the PIC, which is converted to a digital signal through the PIC's analog to digital converter pin. The MAX232N level converter provides bidirectional voltage shifting for digital communication between the PIC and PC (read more about this chip and level conversion on the RS232 wiki [http://hades.mech.northwestern.edu/wiki/index.php/PIC_RS232 here]). Finally, the female DB-9 connector allows the circuit to connect to the PC's serial port.

[[Image:Team26-SerialComCircuit.jpg |thumb|640x470 px|center| Circuit Diagram for Serial Communication between PIC and PC]]

The connections to the female DB-9 adapter are shown below. '''These wires are soldered to the cup-side of the adapter, not directly to the serial cable.''' Our DB-9 adapter is pictured below and follows the given connections:

PIN5:DB-9 (green wire) -> Common Ground
PIN3:DB-9 (yellow wire) -> Receive (RX) -> PIN14:MAX232
PIN2:DB-9 (white wire) -> Transmit (TX) -> PIN13:MAX232

[[Image:DB9Connector.jpg |thumb|300px|center| Closeup of DB-9 Connector]]

Our final circuit is pictured below.

[[Image:P1120664.JPG |thumb|640x470 px|center| Image of wiring for serial communication between PIC 18F4520 and PC]]

== PIC Code ==

/*
SerialComm.c Scott McLeod, Sandeep Prabhu, Brett Pihl 2/4/2008
This program is designed to communicate to a computer using RS232 (Serial) Communication.

The main loop of this program waits for a data transmission over the Serial port, and
responds with a current reading of an analog input (potentiometer) and the last received data.

Note the analog input is only for testing purposes, and is not necessary for serial communication.
Lines unnecessary for RS232 communication are commented with enclosing asterisks ('*..*').
*/

#include <18f4520.h>

#fuses HS,NOLVP,NOWDT,NOPROTECT
#DEVICE ADC=8 // *set ADC to 8 bit accuracy*
#use delay(clock=20000000) // 20 MHz clock
#use rs232(baud=19200, UART1) // Set up PIC UART on RC6 (tx) and RC7 (rx)

int8 data_tx, data_rx = 0; // Set up data_tx (transmit value), data_rx (recieve value)

void main()
{
setup_adc_ports(AN0); // *Enable AN0 as analog potentiometer input*
setup_adc(ADC_CLOCK_INTERNAL); // *the range selected has to start with AN0*
set_adc_channel(0); // *Enable AN0 as analog input*
delay_us(10); // *Pause 10us to set up ADC*

while (TRUE)
{
data_tx = read_adc(); // *Read POT on analog port (0-255)*
output_d(data_rx); // Output last recieved value from computer
delay_ms(10);

if (kbhit()) // If PIC senses data pushed to serial buffer
{
data_rx = fgetc(); // Read in recieved value from buffer
printf("Pot: %u Char: %u\n", data_tx, data_rx); // Once data sent and read, PIC sends data back

//delay_ms(10); // As tested briefly, this delay is unnecessary for our (relatively) slow data rate
// If you are receiving data errors, you may want to introduce a slight delay

}
}
}

== Tips on Designing a Protocol ==
A good way to start or debug your program is to use the PIC-C Serial Port Monitor (Tools Tab->Serial Port Monitor). This will allow you to send and receive raw data over the serial port, which is much easier for understanding why a protocol isn't behaving correctly. You can also use HyperTerminal on windows XP (Start->Programs->Accessories->Communications->HyperTerminal), although in our testing this appeared to be less stable than the PIC-C Compiler's monitor. Note for both programs, you will have to configure which serial port to monitor using the same method described in the Overview.

Be sure to close all other programs accessing the serial ports (PIC-C/Hypterm etc.) if you are having difficulty opening the port in MATLAB.

== Matlab Code ==

'''**** THIS MATLAB CODE SHOULD BE UPDATED TO USE "fread(s,1)" instead of "fscanf(s)". fread(s,1) reads 1 bitwise value at a time (opposed to an ascii value). Without this change, matlab can only read 8 bit ASCII characters and will reject a subset of the values between 0 and 255. *****'''

'''If your program doesn't close and delete the serial port object correctly, you can use the command shown below to delete all of the serial port objects.'''

delete(instrfind)

% SerialComm.m Scott McLeod, Sandeep Prabhu, Brett Pihl 2/4/2008
% This program is designed to communicate to a PIC 18F4520 via RS232 (Serial) Communication.
%
% The main loop of this program waits for a character input from the user,
% upon which it transmits the ascii value and waits for data to be written.

s = serial('COM4','BAUD',19200); % Create serial object (PORT Dependent)
fopen(s) % Open the serial port for r/w

myChar = 'a';
prompt = 'Enter a character (q to exit): ';

while (myChar ~= 'q') % While user hasn't typed 'q'
fprintf(s, '%s', myChar(1)) % Write first char of user input to serial port
fprintf(fscanf(s)) % Read Data back from PIC
myChar = input(prompt, 's'); % Get user input
end

fclose(s); % Close the serial port
delete(s); % Delete the serial object

== External Links ==

More on Serial and the PIC: http://hades.mech.northwestern.edu/wiki/index.php/PIC_RS232

MAX232 Data Sheet: http://rocky.digikey.com/WebLib/Texas%20Instruments/Web%20data/MAX232,232I.pdf

Overview of RS232 Protocol: http://en.wikipedia.org/wiki/RS-232

Serial communication with Matlab

2009-04-25T22:52:41Z

ScottMcLeod: /* Matlab Code */

== Overview ==
Matlab has a "serial" function that allows it to communicate through a serial port. This project is to establish serial port connection with the PIC microcontroller and demonstrate bidirectional communication between the PIC and a Matlab program. For demonstration purposes, the PIC will send digital potentiometer readings to Matlab as well as receive keystrokes from the Matlab user to light up LEDs on its circuit board.

A USB to RS232 adapter and level shifter chip were used to connect the computer to the PIC. In this lab, we used a cheap cable found at http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=220199148938&ih=012&category=41995&ssPageName=WDVW&rd=1

'''**Important! DO NOT connect the serial Rx/Tx lines DIRECTLY to the PIC!!!**'''

A level shifter chip is necessary to convert the high and low logic voltages from the desktop computer (+12V/-5V) to (+5V,0V) for the PIC. A standard RS232 connection is called a DB9 connector and follows the pin diagram shown here: http://www.aggsoft.com/rs232-pinout-cable/serial-cable-connections.htm
This cable requires 1 driver installation as included on the mini-cd. To install this driver, you must first plug in the USB cable, and run the installation program located on the CD corresponding to the model on the USB Cable (<CDROM>:\HL-232-340\HL-340.exe). This driver is also available online at this link:
http://129.105.69.13/pic/usb_drivers/HL-340_USB_serial_drivers_WinXP/ . To configure the Matlab script to connect to the proper serial port, use the device manager (Right click My Computer->manage) and expand the section "Ports (COM & LPT)". Make a note of the COM port number corresponding to "USB-SERIAL CH340" as listed in this section. In our program, our serial port was COM4. A picture is shown below of how to get this information in the device manager.

[[Image:ComPortLookup.JPG |thumb|300px|right| COM Port Lookup - Device Manager]]

A female DB9 connector was wired to our level shifter to convert the voltages, with the level shifter connected to our PIC. The female DB9 connector is used so no wires need to be directly soldered to the serial cable. Refer to the Circuit section for details on this connection.

The PIC was programmed with our C code as shown below. Our program was designed to read a potentiometer through the PIC's ADC (Analog to Digital Converter) port and transmit the digitized readings over the serial cable to the PC (upon request). In Matlab, if a users sends data to the PIC by entering a character, the PIC responds with the current potentiometer reading and the last received byte from the PC. The PIC is also programmed to display the character received from the PC on its LED array (D register) as a 8-bit ASCII number. The programs can easily be modified to create any custom protocol, but are designed to show simple 2-way communication between Matlab and the PIC.

== Circuit ==
The wiring diagram for serial communication is shown below. There are three basic components in this setup. The potentiometer serves as an analog input to the PIC, which is converted to a digital signal through the PIC's analog to digital converter pin. The MAX232N level converter provides bidirectional voltage shifting for digital communication between the PIC and PC (read more about this chip and level conversion on the RS232 wiki [http://hades.mech.northwestern.edu/wiki/index.php/PIC_RS232 here]). Finally, the female DB-9 connector allows the circuit to connect to the PC's serial port.

[[Image:Team26-SerialComCircuit.jpg |thumb|640x470 px|center| Circuit Diagram for Serial Communication between PIC and PC]]

The connections to the female DB-9 adapter are shown below. '''These wires are soldered to the cup-side of the adapter, not directly to the serial cable.''' Our DB-9 adapter is pictured below and follows the given connections:

PIN5:DB-9 (green wire) -> Common Ground
PIN3:DB-9 (yellow wire) -> Receive (RX) -> PIN14:MAX232
PIN2:DB-9 (white wire) -> Transmit (TX) -> PIN13:MAX232

[[Image:DB9Connector.jpg |thumb|300px|center| Closeup of DB-9 Connector]]

Our final circuit is pictured below.

[[Image:P1120664.JPG |thumb|640x470 px|center| Image of wiring for serial communication between PIC 18F4520 and PC]]

== PIC Code ==

/*
SerialComm.c Scott McLeod, Sandeep Prabhu, Brett Pihl 2/4/2008
This program is designed to communicate to a computer using RS232 (Serial) Communication.

The main loop of this program waits for a data transmission over the Serial port, and
responds with a current reading of an analog input (potentiometer) and the last received data.

Note the analog input is only for testing purposes, and is not necessary for serial communication.
Lines unnecessary for RS232 communication are commented with enclosing asterisks ('*..*').
*/

#include <18f4520.h>

#fuses HS,NOLVP,NOWDT,NOPROTECT
#DEVICE ADC=8 // *set ADC to 8 bit accuracy*
#use delay(clock=20000000) // 20 MHz clock
#use rs232(baud=19200, UART1) // Set up PIC UART on RC6 (tx) and RC7 (rx)

int8 data_tx, data_rx = 0; // Set up data_tx (transmit value), data_rx (recieve value)

void main()
{
setup_adc_ports(AN0); // *Enable AN0 as analog potentiometer input*
setup_adc(ADC_CLOCK_INTERNAL); // *the range selected has to start with AN0*
set_adc_channel(0); // *Enable AN0 as analog input*
delay_us(10); // *Pause 10us to set up ADC*

while (TRUE)
{
data_tx = read_adc(); // *Read POT on analog port (0-255)*
output_d(data_rx); // Output last recieved value from computer
delay_ms(10);

if (kbhit()) // If PIC senses data pushed to serial buffer
{
data_rx = fgetc(); // Read in recieved value from buffer
printf("Pot: %u Char: %u\n", data_tx, data_rx); // Once data sent and read, PIC sends data back

//delay_ms(10); // As tested briefly, this delay is unnecessary for our (relatively) slow data rate
// If you are receiving data errors, you may want to introduce a slight delay

}
}
}

== Tips on Designing a Protocol ==
A good way to start or debug your program is to use the PIC-C Serial Port Monitor (Tools Tab->Serial Port Monitor). This will allow you to send and receive raw data over the serial port, which is much easier for understanding why a protocol isn't behaving correctly. You can also use HyperTerminal on windows XP (Start->Programs->Accessories->Communications->HyperTerminal), although in our testing this appeared to be less stable than the PIC-C Compiler's monitor. Note for both programs, you will have to configure which serial port to monitor using the same method described in the Overview.

Be sure to close all other programs accessing the serial ports (PIC-C/Hypterm etc.) if you are having difficulty opening the port in MATLAB.

== Matlab Code ==

'''**** THIS MATLAB CODE SHOULD BE UPDATED TO USE "fread(s,1)". fread(s,1) reads 1 bitwise value at a time (opposed to an ascii value). Without this change, matlab can only read 8 bit ASCII characters and will reject a subset of the values between 0 and 255. *****'''

'''If your program doesn't close and delete the serial port object correctly, you can use the command shown below to delete all of the serial port objects.'''

delete(instrfind)

% SerialComm.m Scott McLeod, Sandeep Prabhu, Brett Pihl 2/4/2008
% This program is designed to communicate to a PIC 18F4520 via RS232 (Serial) Communication.
%
% The main loop of this program waits for a character input from the user,
% upon which it transmits the ascii value and waits for data to be written.

s = serial('COM4','BAUD',19200); % Create serial object (PORT Dependent)
fopen(s) % Open the serial port for r/w

myChar = 'a';
prompt = 'Enter a character (q to exit): ';

while (myChar ~= 'q') % While user hasn't typed 'q'
fprintf(s, '%s', myChar(1)) % Write first char of user input to serial port
fprintf(fscanf(s)) % Read Data back from PIC
myChar = input(prompt, 's'); % Get user input
end

fclose(s); % Close the serial port
delete(s); % Delete the serial object

== External Links ==

More on Serial and the PIC: http://hades.mech.northwestern.edu/wiki/index.php/PIC_RS232

MAX232 Data Sheet: http://rocky.digikey.com/WebLib/Texas%20Instruments/Web%20data/MAX232,232I.pdf

Overview of RS232 Protocol: http://en.wikipedia.org/wiki/RS-232

Indoor Localization System

2008-06-21T04:15:26Z

ScottMcLeod: /* Final Project Code */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software (though this has not been implemented).

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

[[Image:visual_localization_calibration_alignment.jpg|center|thumb|300px|Calibration Pattern Alignment]]

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program. To quit the program, Press 'Esc'.
[[Image:visual_localization_real_time.jpg|center|thumb|300px|Real-Time Processing]]
[[Image:visual_localization_data.jpg|center|thumb|300px|Real-Time Data]]

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Real-time algorithm source:

http://hades.mech.northwestern.edu/wiki/images/8/85/TrackSysV1_6_20_08.zip

Pre-processing program source with final patterns:

http://hades.mech.northwestern.edu/wiki/images/f/fe/TrackSysTraining_6_20_08.zip

Indoor Localization System

2008-06-21T04:14:50Z

ScottMcLeod: /* Final Project Code */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software (though this has not been implemented).

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

[[Image:visual_localization_calibration_alignment.jpg|center|thumb|300px|Calibration Pattern Alignment]]

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program. To quit the program, Press 'Esc'.
[[Image:visual_localization_real_time.jpg|center|thumb|300px|Real-Time Processing]]
[[Image:visual_localization_data.jpg|center|thumb|300px|Real-Time Data]]

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Real-time algorithm source:

http://hades.mech.northwestern.edu/wiki/images/f/fe/TrackSysTraining_6_20_08.zip

Pre-processing program source with final patterns:

http://hades.mech.northwestern.edu/wiki/images/8/85/TrackSysV1_6_20_08.zip

File:TrackSysV1 6 20 08.zip

2008-06-21T04:12:53Z

ScottMcLeod: Real-Time Pattern Tracking program Scott McLeod 6-20-2008

Real-Time Pattern Tracking program
Scott McLeod 6-20-2008

File:TrackSysTraining 6 20 08.zip

2008-06-21T04:10:03Z

ScottMcLeod: Real-Time pattern tracking algorithm c++ Scott McLeod 6-20-2008

Real-Time pattern tracking algorithm c++
Scott McLeod 6-20-2008

Granular Flow Rotating Sphere

2008-06-13T02:37:03Z

ScottMcLeod: /* Spring Quarter Update */

[[ME 333 final projects]]

[[Image:Team-21-main-picture.JPG|right|Our Final Design|thumb|500px]] 

==Spring Quarter Update==

This zip file contains the documentation, MATLAB code/examples, PIC code and circuit diagram.

http://hades.mech.northwestern.edu/wiki/images/3/3d/Tumbler.zip

Contact Scott McLeod for further questions.

==Team Members==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Overview==

A clear sphere is filled with grains of different sizes. Our apparatus rotates this ball about two different axis based on a series of user inputs. The user inputs the specific values for things such as angle and rotational speed into Matlab. Our device takes these inputs and processes them using a series of master and slave PICs to appropriately control the motors. The motors then turn for the input duration at the desired speed causing the ball to spin correctly due to the frictional connection between both motors and the sphere or lazy susan, respectively.

This apparatus will be used for the study of granular flow and the mixing of particles within the sphere. It was important to leave the ball as visible as possible to allow for pictures to be taken of the grains within from many angles. With this apparatus we hope to aide the study of granular flow theory and allow the researches to use the device for many different applications.

==Mechanical Set-up==

====Main Housing====

The main housing, or case, for our design is composed of the following pieces.

*One 13.5” x 12” x ¾” plywood rectangle
*One 13.5” x 12” x ¾” plywood rectangle with a 3.5” diameter circle removed from the center
*Two 12” x 2.5”x ¾” plywood rectangles

The two larger rectangles form the top and bottom of the set-up with the two smaller rectangles placed vertically between to form a box with two open ends on the front and back face.

====Ball Support====

Three ball casters are placed on vertical mounts around the center circle of the top piece of the housing at equal angles. These casters prevent the ball from moving in any horizontal direction so it is only free to rotate. One of these casters is adjustable to allow the user to make sure the ball is correctly supported above the drive wheel. The force of gravity is strong enough to prevent the ball from moving up and out of the housing and also ensures a good connection with the drive wheel that is placed directly under the center of the sphere.

====Main Drive Wheel====

The main drive wheel is centered under the rotating sphere. The wheel is mounted onto a ¼” aluminum shaft which is connected to the Pittman motor with a flexible coupling and is also supported by a sleeve bearing on the other side of the wheel.

====Lazy Susan====

The main drive wheel with its corresponding motor and other components are all mounted on top of a lazy susan that is centered on the bottom piece of the housing and secured with screws. This lazy susan allows rotational motion but prevents movement in any other direction allowing the wheel to turn but always have the same center of contact with the sphere above. It is important to ensure that the drive wheel has a good connection with the sphere above because the frictional force between the wheel and the sphere must be as large as possible so that as the wheel spins the ball spins at the same rate.

====Position Control Motor====

A second motor is used in our design to turn the lazy susan. The motor is mounted vertically through the top plate. Another, smaller, drive wheel is mounted directly to the motor shaft and then aligned with only the top, free half of the lazy susan. A second, idler wheel is mounted on the bottom plate, so the drive wheel is sandwiched between this wheel and the lazy susan. This ensures that the drive wheel is always in contact with the lazy susan because the idler wheel exerts only a normal force. Again, this is to ensure there is no slip between the lazy susan and the drive wheel so it is automatically controlled more easily.

====Complete Parts List====

<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>Pittman GM8224 motor </td><td>---</td><td>2</td>
<tr><td>Helical Beam Set-Screw Shaft Coupling</td><td> 9861T508 </td><td>1</td>
<tr><td>Mounted Sleeve Bearing</td><td>5912K21 </td><td>1</td>
<tr><td>Flange Mount Ball Caster</td><td>5674K77 </td><td>3</td>
<tr><td>Lazy Susan</td><td>1443T2</td><td>1</td>
<tr><td>Drive Wheel</td><td>60885K23 </td><td>1</td>
<tr><td>Small Drive Wheel</td><td>2471K12 </td><td>1</td>
<tr><td>Idler Wheel</td><td>60885K79 </td><td>1</td>
<tr><td>1/4” Aluminum Rod</td><td>---</td><td>---</td>
<tr><td>Aluminum Sheet Metal</td><td>---</td><td>---</td>
<tr><td>Plywood</td><td>---</td><td>---</td>
</table>

==Circuitry==

===Summary===
Our project was unique in that we relied on the use of three different PICs to precisely coordinate the motion of our ball. The main reason for this was because the 18F4520 chip only has enough encoder inputs for one Pittman motor.

===Component List===
<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>PIC18F4520 Prototyping Board</td><td>---</td><td>1</td>
<tr><td>Microchip 8-bit PIC Microcontroller</td><td>PIC18F4520</td><td>3</td>
<tr><td>Pittman Motor with Encoder</td><td>GM8224</td><td>3</td>
<tr><td>Hex Inverter Chip</td><td>SN74HC04</td><td>1</td>
<tr><td>Counter Chip</td><td>LS7083</td><td>2</td>
<tr><td>H-Bridge Chip</td><td>L293</td><td>1</td>
<tr><td>Diodes</td><td>1N4001</td><td>8</td>
<tr><td>10K Resistor</td><td>---</td><td>2</td>
<tr><td>Hall Effect Sensor</td><td>A3240LUA-T</td><td>1</td>
<tr><td>Big Cat Super Strong Magnet</td><td>PM20134</td><td>1</td>
</table>

===Set Up===
The electrical design for our project was pretty basic. All of our components (including the Pittman motors) were powered with 5V DC.

PICs

The three PICs communicated via I2C, which enabled us to control the two motors by telling the master PIC what to do (more information can be found [[I2C communication between PICs|here]]). We designated the PIC on the 18F4520 Prototyping Board as the "Master" and the other two PICs as the "Slaves." It is important to connect the clock from the prototyping board to the two Slave PICs, but the two main lines of communication are shared on pin 18 (RC3) on each chip, and pin 23 (RC4).

H-Bridge

Each slave PIC sends an individual pulse to one of the two H-bridges (the L298 has two). The pulse width determines the direction and speed of each motor. At 50% duty cycle, the motor is at rest, while at 0 and 100% duty cycles the motor runs at maximum speed but in opposite directions. Pin 16 from the first slave PIC needs to connect to pin 10 on the L298, while other other should connect to pin 5.

Hex Inverter

Now pins 5 and 10 from the H-bridge needs to go into pins 1 and 13 on the hex inverter chip. The outputs of these two need to go back the the H-bridge as an inverted signal for pulse width modulation (pin 1 to L298's pin 12, and pin 14 to L298's pin 7).

Counter

The last main component that needs to be implemented in the counter chip. This enables us to take fewer counts from the high encoder on the Pittman motors to control the movement of the motor. Pins 4 and 5 are used to connect directly to the blue and yellow lines on each Pittman encoder. Pins 1, 3, and 6 should all be hooked to ground, while pin 2 should be +5V. Pins 7 and 8 should connect to pins 15 and 6, respectively on the slave PIC that is correspondent to this counter chip.

===Schematic===
Here is a visual representation of how our circuit components fit together: 
[[Image:Team-21-circuit.JPG|left|Team Granular Flow Schematic|thumb|400px]]

[[Image:Team-21-circuit-image.JPG|left|Team Granular Flow Circuit|thumb|300px]]
 
 
 

==Programming==

===Code Overview===

Three sets of code were required for our project: the MATLAB code for the user interface, C code for the master PIC, and C code for the slave PICs. The MATLAB code set up a GUI for intuitive control of the ball. The master PIC code read all the serial communication from MATLAB and converted it into appropriate I2C commands for the slave PICs, which were completely dedicated to motor control and encoding. All required code is provided below (note an additional file BKSMotorControllerFunctions.c which is used by the master PIC as well).

Note: Thanks to Matt Turpin (of the [[IR Tracker]] project) whose code from his 399 independent study proved incredibly useful for our project.

===PIC Code===

[[Media:BKSBallMasterv1.c|BKSBallMasterv1.c]] 
[[Media:BKSMotorControllerFunctions.c|BKSMotorControllerFunctions.c]] 
[[Media:BKSBallSlavev1.c|BKSBallSlavev1.c]]

===MATLAB Code===

The GUIDE toolset in MATLAB was used to create the GUI. Once all the code is loaded onto the correct PICs, everything can be run through BKSBallControl.m.

[[Media:BKSBallControl.m|BKSBallControl.m]] 
[[Media:BKSBallControl.fig|BKSBallControl.fig]]

==Results==

At the time of our presentation, we were able to demonstrate rotation along two axes by using the drive motor and Lazy Susan. Additionally, we were able to show effective and consistent communication of multiple bytes of data from MATLAB to the master PIC vis RS-232. Unfortunately, we were unable to get the hardware for I2C working, despite the code working on Matt's setup. Overall, we were pleased with our progress in a relatively short amount of time.

We hope to fix the hardware issue in the near future and possibly consolidate all the circuitry onto a PCB for a more robust device. We would also like to add a hall effect switch or limit switch to indicate a set "Home" position. Additional work can be done on the motor control functions to implement feedback control as necessary. As there are clients that would like to see this project come to fruition, we want to make sure they are given a robust and flexible system for their use.

Granular Flow Rotating Sphere

2008-06-13T02:36:48Z

ScottMcLeod: /* Spring Quarter Update */

[[ME 333 final projects]]

[[Image:Team-21-main-picture.JPG|right|Our Final Design|thumb|500px]] 

==Spring Quarter Update==

This zip file contains the documentation, MATLAB code/examples, PIC code and circuit diagram.
http://hades.mech.northwestern.edu/wiki/images/3/3d/Tumbler.zip
Contact Scott McLeod for further questions.

==Team Members==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Overview==

A clear sphere is filled with grains of different sizes. Our apparatus rotates this ball about two different axis based on a series of user inputs. The user inputs the specific values for things such as angle and rotational speed into Matlab. Our device takes these inputs and processes them using a series of master and slave PICs to appropriately control the motors. The motors then turn for the input duration at the desired speed causing the ball to spin correctly due to the frictional connection between both motors and the sphere or lazy susan, respectively.

This apparatus will be used for the study of granular flow and the mixing of particles within the sphere. It was important to leave the ball as visible as possible to allow for pictures to be taken of the grains within from many angles. With this apparatus we hope to aide the study of granular flow theory and allow the researches to use the device for many different applications.

==Mechanical Set-up==

====Main Housing====

The main housing, or case, for our design is composed of the following pieces.

*One 13.5” x 12” x ¾” plywood rectangle
*One 13.5” x 12” x ¾” plywood rectangle with a 3.5” diameter circle removed from the center
*Two 12” x 2.5”x ¾” plywood rectangles

The two larger rectangles form the top and bottom of the set-up with the two smaller rectangles placed vertically between to form a box with two open ends on the front and back face.

====Ball Support====

Three ball casters are placed on vertical mounts around the center circle of the top piece of the housing at equal angles. These casters prevent the ball from moving in any horizontal direction so it is only free to rotate. One of these casters is adjustable to allow the user to make sure the ball is correctly supported above the drive wheel. The force of gravity is strong enough to prevent the ball from moving up and out of the housing and also ensures a good connection with the drive wheel that is placed directly under the center of the sphere.

====Main Drive Wheel====

The main drive wheel is centered under the rotating sphere. The wheel is mounted onto a ¼” aluminum shaft which is connected to the Pittman motor with a flexible coupling and is also supported by a sleeve bearing on the other side of the wheel.

====Lazy Susan====

The main drive wheel with its corresponding motor and other components are all mounted on top of a lazy susan that is centered on the bottom piece of the housing and secured with screws. This lazy susan allows rotational motion but prevents movement in any other direction allowing the wheel to turn but always have the same center of contact with the sphere above. It is important to ensure that the drive wheel has a good connection with the sphere above because the frictional force between the wheel and the sphere must be as large as possible so that as the wheel spins the ball spins at the same rate.

====Position Control Motor====

A second motor is used in our design to turn the lazy susan. The motor is mounted vertically through the top plate. Another, smaller, drive wheel is mounted directly to the motor shaft and then aligned with only the top, free half of the lazy susan. A second, idler wheel is mounted on the bottom plate, so the drive wheel is sandwiched between this wheel and the lazy susan. This ensures that the drive wheel is always in contact with the lazy susan because the idler wheel exerts only a normal force. Again, this is to ensure there is no slip between the lazy susan and the drive wheel so it is automatically controlled more easily.

====Complete Parts List====

<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>Pittman GM8224 motor </td><td>---</td><td>2</td>
<tr><td>Helical Beam Set-Screw Shaft Coupling</td><td> 9861T508 </td><td>1</td>
<tr><td>Mounted Sleeve Bearing</td><td>5912K21 </td><td>1</td>
<tr><td>Flange Mount Ball Caster</td><td>5674K77 </td><td>3</td>
<tr><td>Lazy Susan</td><td>1443T2</td><td>1</td>
<tr><td>Drive Wheel</td><td>60885K23 </td><td>1</td>
<tr><td>Small Drive Wheel</td><td>2471K12 </td><td>1</td>
<tr><td>Idler Wheel</td><td>60885K79 </td><td>1</td>
<tr><td>1/4” Aluminum Rod</td><td>---</td><td>---</td>
<tr><td>Aluminum Sheet Metal</td><td>---</td><td>---</td>
<tr><td>Plywood</td><td>---</td><td>---</td>
</table>

==Circuitry==

===Summary===
Our project was unique in that we relied on the use of three different PICs to precisely coordinate the motion of our ball. The main reason for this was because the 18F4520 chip only has enough encoder inputs for one Pittman motor.

===Component List===
<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>PIC18F4520 Prototyping Board</td><td>---</td><td>1</td>
<tr><td>Microchip 8-bit PIC Microcontroller</td><td>PIC18F4520</td><td>3</td>
<tr><td>Pittman Motor with Encoder</td><td>GM8224</td><td>3</td>
<tr><td>Hex Inverter Chip</td><td>SN74HC04</td><td>1</td>
<tr><td>Counter Chip</td><td>LS7083</td><td>2</td>
<tr><td>H-Bridge Chip</td><td>L293</td><td>1</td>
<tr><td>Diodes</td><td>1N4001</td><td>8</td>
<tr><td>10K Resistor</td><td>---</td><td>2</td>
<tr><td>Hall Effect Sensor</td><td>A3240LUA-T</td><td>1</td>
<tr><td>Big Cat Super Strong Magnet</td><td>PM20134</td><td>1</td>
</table>

===Set Up===
The electrical design for our project was pretty basic. All of our components (including the Pittman motors) were powered with 5V DC.

PICs

The three PICs communicated via I2C, which enabled us to control the two motors by telling the master PIC what to do (more information can be found [[I2C communication between PICs|here]]). We designated the PIC on the 18F4520 Prototyping Board as the "Master" and the other two PICs as the "Slaves." It is important to connect the clock from the prototyping board to the two Slave PICs, but the two main lines of communication are shared on pin 18 (RC3) on each chip, and pin 23 (RC4).

H-Bridge

Each slave PIC sends an individual pulse to one of the two H-bridges (the L298 has two). The pulse width determines the direction and speed of each motor. At 50% duty cycle, the motor is at rest, while at 0 and 100% duty cycles the motor runs at maximum speed but in opposite directions. Pin 16 from the first slave PIC needs to connect to pin 10 on the L298, while other other should connect to pin 5.

Hex Inverter

Now pins 5 and 10 from the H-bridge needs to go into pins 1 and 13 on the hex inverter chip. The outputs of these two need to go back the the H-bridge as an inverted signal for pulse width modulation (pin 1 to L298's pin 12, and pin 14 to L298's pin 7).

Counter

The last main component that needs to be implemented in the counter chip. This enables us to take fewer counts from the high encoder on the Pittman motors to control the movement of the motor. Pins 4 and 5 are used to connect directly to the blue and yellow lines on each Pittman encoder. Pins 1, 3, and 6 should all be hooked to ground, while pin 2 should be +5V. Pins 7 and 8 should connect to pins 15 and 6, respectively on the slave PIC that is correspondent to this counter chip.

===Schematic===
Here is a visual representation of how our circuit components fit together: 
[[Image:Team-21-circuit.JPG|left|Team Granular Flow Schematic|thumb|400px]]

[[Image:Team-21-circuit-image.JPG|left|Team Granular Flow Circuit|thumb|300px]]
 
 
 

==Programming==

===Code Overview===

Three sets of code were required for our project: the MATLAB code for the user interface, C code for the master PIC, and C code for the slave PICs. The MATLAB code set up a GUI for intuitive control of the ball. The master PIC code read all the serial communication from MATLAB and converted it into appropriate I2C commands for the slave PICs, which were completely dedicated to motor control and encoding. All required code is provided below (note an additional file BKSMotorControllerFunctions.c which is used by the master PIC as well).

Note: Thanks to Matt Turpin (of the [[IR Tracker]] project) whose code from his 399 independent study proved incredibly useful for our project.

===PIC Code===

[[Media:BKSBallMasterv1.c|BKSBallMasterv1.c]] 
[[Media:BKSMotorControllerFunctions.c|BKSMotorControllerFunctions.c]] 
[[Media:BKSBallSlavev1.c|BKSBallSlavev1.c]]

===MATLAB Code===

The GUIDE toolset in MATLAB was used to create the GUI. Once all the code is loaded onto the correct PICs, everything can be run through BKSBallControl.m.

[[Media:BKSBallControl.m|BKSBallControl.m]] 
[[Media:BKSBallControl.fig|BKSBallControl.fig]]

==Results==

At the time of our presentation, we were able to demonstrate rotation along two axes by using the drive motor and Lazy Susan. Additionally, we were able to show effective and consistent communication of multiple bytes of data from MATLAB to the master PIC vis RS-232. Unfortunately, we were unable to get the hardware for I2C working, despite the code working on Matt's setup. Overall, we were pleased with our progress in a relatively short amount of time.

We hope to fix the hardware issue in the near future and possibly consolidate all the circuitry onto a PCB for a more robust device. We would also like to add a hall effect switch or limit switch to indicate a set "Home" position. Additional work can be done on the motor control functions to implement feedback control as necessary. As there are clients that would like to see this project come to fruition, we want to make sure they are given a robust and flexible system for their use.

File:Tumbler.zip

2008-06-13T02:36:27Z

ScottMcLeod: Granular Flow Spring quarter update Produced by Scott McLeod

Granular Flow Spring quarter update
Produced by Scott McLeod

Granular Flow Rotating Sphere

2008-06-13T02:34:27Z

ScottMcLeod: /* Spring Quarter Update */

[[ME 333 final projects]]

[[Image:Team-21-main-picture.JPG|right|Our Final Design|thumb|500px]] 

==Spring Quarter Update==

This zip file contains the documentation, MATLAB code/examples, PIC code and circuit diagram.

Contact Scott McLeod for further questions.

==Team Members==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Overview==

A clear sphere is filled with grains of different sizes. Our apparatus rotates this ball about two different axis based on a series of user inputs. The user inputs the specific values for things such as angle and rotational speed into Matlab. Our device takes these inputs and processes them using a series of master and slave PICs to appropriately control the motors. The motors then turn for the input duration at the desired speed causing the ball to spin correctly due to the frictional connection between both motors and the sphere or lazy susan, respectively.

This apparatus will be used for the study of granular flow and the mixing of particles within the sphere. It was important to leave the ball as visible as possible to allow for pictures to be taken of the grains within from many angles. With this apparatus we hope to aide the study of granular flow theory and allow the researches to use the device for many different applications.

==Mechanical Set-up==

====Main Housing====

The main housing, or case, for our design is composed of the following pieces.

*One 13.5” x 12” x ¾” plywood rectangle
*One 13.5” x 12” x ¾” plywood rectangle with a 3.5” diameter circle removed from the center
*Two 12” x 2.5”x ¾” plywood rectangles

The two larger rectangles form the top and bottom of the set-up with the two smaller rectangles placed vertically between to form a box with two open ends on the front and back face.

====Ball Support====

Three ball casters are placed on vertical mounts around the center circle of the top piece of the housing at equal angles. These casters prevent the ball from moving in any horizontal direction so it is only free to rotate. One of these casters is adjustable to allow the user to make sure the ball is correctly supported above the drive wheel. The force of gravity is strong enough to prevent the ball from moving up and out of the housing and also ensures a good connection with the drive wheel that is placed directly under the center of the sphere.

====Main Drive Wheel====

The main drive wheel is centered under the rotating sphere. The wheel is mounted onto a ¼” aluminum shaft which is connected to the Pittman motor with a flexible coupling and is also supported by a sleeve bearing on the other side of the wheel.

====Lazy Susan====

The main drive wheel with its corresponding motor and other components are all mounted on top of a lazy susan that is centered on the bottom piece of the housing and secured with screws. This lazy susan allows rotational motion but prevents movement in any other direction allowing the wheel to turn but always have the same center of contact with the sphere above. It is important to ensure that the drive wheel has a good connection with the sphere above because the frictional force between the wheel and the sphere must be as large as possible so that as the wheel spins the ball spins at the same rate.

====Position Control Motor====

A second motor is used in our design to turn the lazy susan. The motor is mounted vertically through the top plate. Another, smaller, drive wheel is mounted directly to the motor shaft and then aligned with only the top, free half of the lazy susan. A second, idler wheel is mounted on the bottom plate, so the drive wheel is sandwiched between this wheel and the lazy susan. This ensures that the drive wheel is always in contact with the lazy susan because the idler wheel exerts only a normal force. Again, this is to ensure there is no slip between the lazy susan and the drive wheel so it is automatically controlled more easily.

====Complete Parts List====

<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>Pittman GM8224 motor </td><td>---</td><td>2</td>
<tr><td>Helical Beam Set-Screw Shaft Coupling</td><td> 9861T508 </td><td>1</td>
<tr><td>Mounted Sleeve Bearing</td><td>5912K21 </td><td>1</td>
<tr><td>Flange Mount Ball Caster</td><td>5674K77 </td><td>3</td>
<tr><td>Lazy Susan</td><td>1443T2</td><td>1</td>
<tr><td>Drive Wheel</td><td>60885K23 </td><td>1</td>
<tr><td>Small Drive Wheel</td><td>2471K12 </td><td>1</td>
<tr><td>Idler Wheel</td><td>60885K79 </td><td>1</td>
<tr><td>1/4” Aluminum Rod</td><td>---</td><td>---</td>
<tr><td>Aluminum Sheet Metal</td><td>---</td><td>---</td>
<tr><td>Plywood</td><td>---</td><td>---</td>
</table>

==Circuitry==

===Summary===
Our project was unique in that we relied on the use of three different PICs to precisely coordinate the motion of our ball. The main reason for this was because the 18F4520 chip only has enough encoder inputs for one Pittman motor.

===Component List===
<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>PIC18F4520 Prototyping Board</td><td>---</td><td>1</td>
<tr><td>Microchip 8-bit PIC Microcontroller</td><td>PIC18F4520</td><td>3</td>
<tr><td>Pittman Motor with Encoder</td><td>GM8224</td><td>3</td>
<tr><td>Hex Inverter Chip</td><td>SN74HC04</td><td>1</td>
<tr><td>Counter Chip</td><td>LS7083</td><td>2</td>
<tr><td>H-Bridge Chip</td><td>L293</td><td>1</td>
<tr><td>Diodes</td><td>1N4001</td><td>8</td>
<tr><td>10K Resistor</td><td>---</td><td>2</td>
<tr><td>Hall Effect Sensor</td><td>A3240LUA-T</td><td>1</td>
<tr><td>Big Cat Super Strong Magnet</td><td>PM20134</td><td>1</td>
</table>

===Set Up===
The electrical design for our project was pretty basic. All of our components (including the Pittman motors) were powered with 5V DC.

PICs

The three PICs communicated via I2C, which enabled us to control the two motors by telling the master PIC what to do (more information can be found [[I2C communication between PICs|here]]). We designated the PIC on the 18F4520 Prototyping Board as the "Master" and the other two PICs as the "Slaves." It is important to connect the clock from the prototyping board to the two Slave PICs, but the two main lines of communication are shared on pin 18 (RC3) on each chip, and pin 23 (RC4).

H-Bridge

Each slave PIC sends an individual pulse to one of the two H-bridges (the L298 has two). The pulse width determines the direction and speed of each motor. At 50% duty cycle, the motor is at rest, while at 0 and 100% duty cycles the motor runs at maximum speed but in opposite directions. Pin 16 from the first slave PIC needs to connect to pin 10 on the L298, while other other should connect to pin 5.

Hex Inverter

Now pins 5 and 10 from the H-bridge needs to go into pins 1 and 13 on the hex inverter chip. The outputs of these two need to go back the the H-bridge as an inverted signal for pulse width modulation (pin 1 to L298's pin 12, and pin 14 to L298's pin 7).

Counter

The last main component that needs to be implemented in the counter chip. This enables us to take fewer counts from the high encoder on the Pittman motors to control the movement of the motor. Pins 4 and 5 are used to connect directly to the blue and yellow lines on each Pittman encoder. Pins 1, 3, and 6 should all be hooked to ground, while pin 2 should be +5V. Pins 7 and 8 should connect to pins 15 and 6, respectively on the slave PIC that is correspondent to this counter chip.

===Schematic===
Here is a visual representation of how our circuit components fit together: 
[[Image:Team-21-circuit.JPG|left|Team Granular Flow Schematic|thumb|400px]]

[[Image:Team-21-circuit-image.JPG|left|Team Granular Flow Circuit|thumb|300px]]
 
 
 

==Programming==

===Code Overview===

Three sets of code were required for our project: the MATLAB code for the user interface, C code for the master PIC, and C code for the slave PICs. The MATLAB code set up a GUI for intuitive control of the ball. The master PIC code read all the serial communication from MATLAB and converted it into appropriate I2C commands for the slave PICs, which were completely dedicated to motor control and encoding. All required code is provided below (note an additional file BKSMotorControllerFunctions.c which is used by the master PIC as well).

Note: Thanks to Matt Turpin (of the [[IR Tracker]] project) whose code from his 399 independent study proved incredibly useful for our project.

===PIC Code===

[[Media:BKSBallMasterv1.c|BKSBallMasterv1.c]] 
[[Media:BKSMotorControllerFunctions.c|BKSMotorControllerFunctions.c]] 
[[Media:BKSBallSlavev1.c|BKSBallSlavev1.c]]

===MATLAB Code===

The GUIDE toolset in MATLAB was used to create the GUI. Once all the code is loaded onto the correct PICs, everything can be run through BKSBallControl.m.

[[Media:BKSBallControl.m|BKSBallControl.m]] 
[[Media:BKSBallControl.fig|BKSBallControl.fig]]

==Results==

At the time of our presentation, we were able to demonstrate rotation along two axes by using the drive motor and Lazy Susan. Additionally, we were able to show effective and consistent communication of multiple bytes of data from MATLAB to the master PIC vis RS-232. Unfortunately, we were unable to get the hardware for I2C working, despite the code working on Matt's setup. Overall, we were pleased with our progress in a relatively short amount of time.

We hope to fix the hardware issue in the near future and possibly consolidate all the circuitry onto a PCB for a more robust device. We would also like to add a hall effect switch or limit switch to indicate a set "Home" position. Additional work can be done on the motor control functions to implement feedback control as necessary. As there are clients that would like to see this project come to fruition, we want to make sure they are given a robust and flexible system for their use.

Granular Flow Rotating Sphere

2008-06-13T02:34:02Z

ScottMcLeod: /* Spring Quarter Update */

[[ME 333 final projects]]

[[Image:Team-21-main-picture.JPG|right|Our Final Design|thumb|500px]] 

==Spring Quarter Update==

This zip file contains the documentation, MATLAB code/examples, PIC code and circuit diagram.

==Team Members==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Overview==

A clear sphere is filled with grains of different sizes. Our apparatus rotates this ball about two different axis based on a series of user inputs. The user inputs the specific values for things such as angle and rotational speed into Matlab. Our device takes these inputs and processes them using a series of master and slave PICs to appropriately control the motors. The motors then turn for the input duration at the desired speed causing the ball to spin correctly due to the frictional connection between both motors and the sphere or lazy susan, respectively.

This apparatus will be used for the study of granular flow and the mixing of particles within the sphere. It was important to leave the ball as visible as possible to allow for pictures to be taken of the grains within from many angles. With this apparatus we hope to aide the study of granular flow theory and allow the researches to use the device for many different applications.

==Mechanical Set-up==

====Main Housing====

The main housing, or case, for our design is composed of the following pieces.

*One 13.5” x 12” x ¾” plywood rectangle
*One 13.5” x 12” x ¾” plywood rectangle with a 3.5” diameter circle removed from the center
*Two 12” x 2.5”x ¾” plywood rectangles

The two larger rectangles form the top and bottom of the set-up with the two smaller rectangles placed vertically between to form a box with two open ends on the front and back face.

====Ball Support====

Three ball casters are placed on vertical mounts around the center circle of the top piece of the housing at equal angles. These casters prevent the ball from moving in any horizontal direction so it is only free to rotate. One of these casters is adjustable to allow the user to make sure the ball is correctly supported above the drive wheel. The force of gravity is strong enough to prevent the ball from moving up and out of the housing and also ensures a good connection with the drive wheel that is placed directly under the center of the sphere.

====Main Drive Wheel====

The main drive wheel is centered under the rotating sphere. The wheel is mounted onto a ¼” aluminum shaft which is connected to the Pittman motor with a flexible coupling and is also supported by a sleeve bearing on the other side of the wheel.

====Lazy Susan====

The main drive wheel with its corresponding motor and other components are all mounted on top of a lazy susan that is centered on the bottom piece of the housing and secured with screws. This lazy susan allows rotational motion but prevents movement in any other direction allowing the wheel to turn but always have the same center of contact with the sphere above. It is important to ensure that the drive wheel has a good connection with the sphere above because the frictional force between the wheel and the sphere must be as large as possible so that as the wheel spins the ball spins at the same rate.

====Position Control Motor====

A second motor is used in our design to turn the lazy susan. The motor is mounted vertically through the top plate. Another, smaller, drive wheel is mounted directly to the motor shaft and then aligned with only the top, free half of the lazy susan. A second, idler wheel is mounted on the bottom plate, so the drive wheel is sandwiched between this wheel and the lazy susan. This ensures that the drive wheel is always in contact with the lazy susan because the idler wheel exerts only a normal force. Again, this is to ensure there is no slip between the lazy susan and the drive wheel so it is automatically controlled more easily.

====Complete Parts List====

<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>Pittman GM8224 motor </td><td>---</td><td>2</td>
<tr><td>Helical Beam Set-Screw Shaft Coupling</td><td> 9861T508 </td><td>1</td>
<tr><td>Mounted Sleeve Bearing</td><td>5912K21 </td><td>1</td>
<tr><td>Flange Mount Ball Caster</td><td>5674K77 </td><td>3</td>
<tr><td>Lazy Susan</td><td>1443T2</td><td>1</td>
<tr><td>Drive Wheel</td><td>60885K23 </td><td>1</td>
<tr><td>Small Drive Wheel</td><td>2471K12 </td><td>1</td>
<tr><td>Idler Wheel</td><td>60885K79 </td><td>1</td>
<tr><td>1/4” Aluminum Rod</td><td>---</td><td>---</td>
<tr><td>Aluminum Sheet Metal</td><td>---</td><td>---</td>
<tr><td>Plywood</td><td>---</td><td>---</td>
</table>

==Circuitry==

===Summary===
Our project was unique in that we relied on the use of three different PICs to precisely coordinate the motion of our ball. The main reason for this was because the 18F4520 chip only has enough encoder inputs for one Pittman motor.

===Component List===
<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>PIC18F4520 Prototyping Board</td><td>---</td><td>1</td>
<tr><td>Microchip 8-bit PIC Microcontroller</td><td>PIC18F4520</td><td>3</td>
<tr><td>Pittman Motor with Encoder</td><td>GM8224</td><td>3</td>
<tr><td>Hex Inverter Chip</td><td>SN74HC04</td><td>1</td>
<tr><td>Counter Chip</td><td>LS7083</td><td>2</td>
<tr><td>H-Bridge Chip</td><td>L293</td><td>1</td>
<tr><td>Diodes</td><td>1N4001</td><td>8</td>
<tr><td>10K Resistor</td><td>---</td><td>2</td>
<tr><td>Hall Effect Sensor</td><td>A3240LUA-T</td><td>1</td>
<tr><td>Big Cat Super Strong Magnet</td><td>PM20134</td><td>1</td>
</table>

===Set Up===
The electrical design for our project was pretty basic. All of our components (including the Pittman motors) were powered with 5V DC.

PICs

The three PICs communicated via I2C, which enabled us to control the two motors by telling the master PIC what to do (more information can be found [[I2C communication between PICs|here]]). We designated the PIC on the 18F4520 Prototyping Board as the "Master" and the other two PICs as the "Slaves." It is important to connect the clock from the prototyping board to the two Slave PICs, but the two main lines of communication are shared on pin 18 (RC3) on each chip, and pin 23 (RC4).

H-Bridge

Each slave PIC sends an individual pulse to one of the two H-bridges (the L298 has two). The pulse width determines the direction and speed of each motor. At 50% duty cycle, the motor is at rest, while at 0 and 100% duty cycles the motor runs at maximum speed but in opposite directions. Pin 16 from the first slave PIC needs to connect to pin 10 on the L298, while other other should connect to pin 5.

Hex Inverter

Now pins 5 and 10 from the H-bridge needs to go into pins 1 and 13 on the hex inverter chip. The outputs of these two need to go back the the H-bridge as an inverted signal for pulse width modulation (pin 1 to L298's pin 12, and pin 14 to L298's pin 7).

Counter

The last main component that needs to be implemented in the counter chip. This enables us to take fewer counts from the high encoder on the Pittman motors to control the movement of the motor. Pins 4 and 5 are used to connect directly to the blue and yellow lines on each Pittman encoder. Pins 1, 3, and 6 should all be hooked to ground, while pin 2 should be +5V. Pins 7 and 8 should connect to pins 15 and 6, respectively on the slave PIC that is correspondent to this counter chip.

===Schematic===
Here is a visual representation of how our circuit components fit together: 
[[Image:Team-21-circuit.JPG|left|Team Granular Flow Schematic|thumb|400px]]

[[Image:Team-21-circuit-image.JPG|left|Team Granular Flow Circuit|thumb|300px]]
 
 
 

==Programming==

===Code Overview===

Three sets of code were required for our project: the MATLAB code for the user interface, C code for the master PIC, and C code for the slave PICs. The MATLAB code set up a GUI for intuitive control of the ball. The master PIC code read all the serial communication from MATLAB and converted it into appropriate I2C commands for the slave PICs, which were completely dedicated to motor control and encoding. All required code is provided below (note an additional file BKSMotorControllerFunctions.c which is used by the master PIC as well).

Note: Thanks to Matt Turpin (of the [[IR Tracker]] project) whose code from his 399 independent study proved incredibly useful for our project.

===PIC Code===

[[Media:BKSBallMasterv1.c|BKSBallMasterv1.c]] 
[[Media:BKSMotorControllerFunctions.c|BKSMotorControllerFunctions.c]] 
[[Media:BKSBallSlavev1.c|BKSBallSlavev1.c]]

===MATLAB Code===

The GUIDE toolset in MATLAB was used to create the GUI. Once all the code is loaded onto the correct PICs, everything can be run through BKSBallControl.m.

[[Media:BKSBallControl.m|BKSBallControl.m]] 
[[Media:BKSBallControl.fig|BKSBallControl.fig]]

==Results==

At the time of our presentation, we were able to demonstrate rotation along two axes by using the drive motor and Lazy Susan. Additionally, we were able to show effective and consistent communication of multiple bytes of data from MATLAB to the master PIC vis RS-232. Unfortunately, we were unable to get the hardware for I2C working, despite the code working on Matt's setup. Overall, we were pleased with our progress in a relatively short amount of time.

We hope to fix the hardware issue in the near future and possibly consolidate all the circuitry onto a PCB for a more robust device. We would also like to add a hall effect switch or limit switch to indicate a set "Home" position. Additional work can be done on the motor control functions to implement feedback control as necessary. As there are clients that would like to see this project come to fruition, we want to make sure they are given a robust and flexible system for their use.

Granular Flow Rotating Sphere

2008-06-13T02:32:42Z

ScottMcLeod: /* Team Members */

[[ME 333 final projects]]

[[Image:Team-21-main-picture.JPG|right|Our Final Design|thumb|500px]] 

==Spring Quarter Update==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Team Members==
*Brian Kephart - Electrical Engineering Class of 2009
*Jonathan Shih - Mechanical Engineering Class of 2009
*Kristi Bond - Mechanical Engineering Class of 2008

==Overview==

A clear sphere is filled with grains of different sizes. Our apparatus rotates this ball about two different axis based on a series of user inputs. The user inputs the specific values for things such as angle and rotational speed into Matlab. Our device takes these inputs and processes them using a series of master and slave PICs to appropriately control the motors. The motors then turn for the input duration at the desired speed causing the ball to spin correctly due to the frictional connection between both motors and the sphere or lazy susan, respectively.

This apparatus will be used for the study of granular flow and the mixing of particles within the sphere. It was important to leave the ball as visible as possible to allow for pictures to be taken of the grains within from many angles. With this apparatus we hope to aide the study of granular flow theory and allow the researches to use the device for many different applications.

==Mechanical Set-up==

====Main Housing====

The main housing, or case, for our design is composed of the following pieces.

*One 13.5” x 12” x ¾” plywood rectangle
*One 13.5” x 12” x ¾” plywood rectangle with a 3.5” diameter circle removed from the center
*Two 12” x 2.5”x ¾” plywood rectangles

The two larger rectangles form the top and bottom of the set-up with the two smaller rectangles placed vertically between to form a box with two open ends on the front and back face.

====Ball Support====

Three ball casters are placed on vertical mounts around the center circle of the top piece of the housing at equal angles. These casters prevent the ball from moving in any horizontal direction so it is only free to rotate. One of these casters is adjustable to allow the user to make sure the ball is correctly supported above the drive wheel. The force of gravity is strong enough to prevent the ball from moving up and out of the housing and also ensures a good connection with the drive wheel that is placed directly under the center of the sphere.

====Main Drive Wheel====

The main drive wheel is centered under the rotating sphere. The wheel is mounted onto a ¼” aluminum shaft which is connected to the Pittman motor with a flexible coupling and is also supported by a sleeve bearing on the other side of the wheel.

====Lazy Susan====

The main drive wheel with its corresponding motor and other components are all mounted on top of a lazy susan that is centered on the bottom piece of the housing and secured with screws. This lazy susan allows rotational motion but prevents movement in any other direction allowing the wheel to turn but always have the same center of contact with the sphere above. It is important to ensure that the drive wheel has a good connection with the sphere above because the frictional force between the wheel and the sphere must be as large as possible so that as the wheel spins the ball spins at the same rate.

====Position Control Motor====

A second motor is used in our design to turn the lazy susan. The motor is mounted vertically through the top plate. Another, smaller, drive wheel is mounted directly to the motor shaft and then aligned with only the top, free half of the lazy susan. A second, idler wheel is mounted on the bottom plate, so the drive wheel is sandwiched between this wheel and the lazy susan. This ensures that the drive wheel is always in contact with the lazy susan because the idler wheel exerts only a normal force. Again, this is to ensure there is no slip between the lazy susan and the drive wheel so it is automatically controlled more easily.

====Complete Parts List====

<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>Pittman GM8224 motor </td><td>---</td><td>2</td>
<tr><td>Helical Beam Set-Screw Shaft Coupling</td><td> 9861T508 </td><td>1</td>
<tr><td>Mounted Sleeve Bearing</td><td>5912K21 </td><td>1</td>
<tr><td>Flange Mount Ball Caster</td><td>5674K77 </td><td>3</td>
<tr><td>Lazy Susan</td><td>1443T2</td><td>1</td>
<tr><td>Drive Wheel</td><td>60885K23 </td><td>1</td>
<tr><td>Small Drive Wheel</td><td>2471K12 </td><td>1</td>
<tr><td>Idler Wheel</td><td>60885K79 </td><td>1</td>
<tr><td>1/4” Aluminum Rod</td><td>---</td><td>---</td>
<tr><td>Aluminum Sheet Metal</td><td>---</td><td>---</td>
<tr><td>Plywood</td><td>---</td><td>---</td>
</table>

==Circuitry==

===Summary===
Our project was unique in that we relied on the use of three different PICs to precisely coordinate the motion of our ball. The main reason for this was because the 18F4520 chip only has enough encoder inputs for one Pittman motor.

===Component List===
<table border=1>
<tr><th>Part</th><th>Part No.</th><th>Qty</th>
<tr><td>PIC18F4520 Prototyping Board</td><td>---</td><td>1</td>
<tr><td>Microchip 8-bit PIC Microcontroller</td><td>PIC18F4520</td><td>3</td>
<tr><td>Pittman Motor with Encoder</td><td>GM8224</td><td>3</td>
<tr><td>Hex Inverter Chip</td><td>SN74HC04</td><td>1</td>
<tr><td>Counter Chip</td><td>LS7083</td><td>2</td>
<tr><td>H-Bridge Chip</td><td>L293</td><td>1</td>
<tr><td>Diodes</td><td>1N4001</td><td>8</td>
<tr><td>10K Resistor</td><td>---</td><td>2</td>
<tr><td>Hall Effect Sensor</td><td>A3240LUA-T</td><td>1</td>
<tr><td>Big Cat Super Strong Magnet</td><td>PM20134</td><td>1</td>
</table>

===Set Up===
The electrical design for our project was pretty basic. All of our components (including the Pittman motors) were powered with 5V DC.

PICs

The three PICs communicated via I2C, which enabled us to control the two motors by telling the master PIC what to do (more information can be found [[I2C communication between PICs|here]]). We designated the PIC on the 18F4520 Prototyping Board as the "Master" and the other two PICs as the "Slaves." It is important to connect the clock from the prototyping board to the two Slave PICs, but the two main lines of communication are shared on pin 18 (RC3) on each chip, and pin 23 (RC4).

H-Bridge

Each slave PIC sends an individual pulse to one of the two H-bridges (the L298 has two). The pulse width determines the direction and speed of each motor. At 50% duty cycle, the motor is at rest, while at 0 and 100% duty cycles the motor runs at maximum speed but in opposite directions. Pin 16 from the first slave PIC needs to connect to pin 10 on the L298, while other other should connect to pin 5.

Hex Inverter

Now pins 5 and 10 from the H-bridge needs to go into pins 1 and 13 on the hex inverter chip. The outputs of these two need to go back the the H-bridge as an inverted signal for pulse width modulation (pin 1 to L298's pin 12, and pin 14 to L298's pin 7).

Counter

The last main component that needs to be implemented in the counter chip. This enables us to take fewer counts from the high encoder on the Pittman motors to control the movement of the motor. Pins 4 and 5 are used to connect directly to the blue and yellow lines on each Pittman encoder. Pins 1, 3, and 6 should all be hooked to ground, while pin 2 should be +5V. Pins 7 and 8 should connect to pins 15 and 6, respectively on the slave PIC that is correspondent to this counter chip.

===Schematic===
Here is a visual representation of how our circuit components fit together: 
[[Image:Team-21-circuit.JPG|left|Team Granular Flow Schematic|thumb|400px]]

[[Image:Team-21-circuit-image.JPG|left|Team Granular Flow Circuit|thumb|300px]]
 
 
 

==Programming==

===Code Overview===

Three sets of code were required for our project: the MATLAB code for the user interface, C code for the master PIC, and C code for the slave PICs. The MATLAB code set up a GUI for intuitive control of the ball. The master PIC code read all the serial communication from MATLAB and converted it into appropriate I2C commands for the slave PICs, which were completely dedicated to motor control and encoding. All required code is provided below (note an additional file BKSMotorControllerFunctions.c which is used by the master PIC as well).

Note: Thanks to Matt Turpin (of the [[IR Tracker]] project) whose code from his 399 independent study proved incredibly useful for our project.

===PIC Code===

[[Media:BKSBallMasterv1.c|BKSBallMasterv1.c]] 
[[Media:BKSMotorControllerFunctions.c|BKSMotorControllerFunctions.c]] 
[[Media:BKSBallSlavev1.c|BKSBallSlavev1.c]]

===MATLAB Code===

The GUIDE toolset in MATLAB was used to create the GUI. Once all the code is loaded onto the correct PICs, everything can be run through BKSBallControl.m.

[[Media:BKSBallControl.m|BKSBallControl.m]] 
[[Media:BKSBallControl.fig|BKSBallControl.fig]]

==Results==

At the time of our presentation, we were able to demonstrate rotation along two axes by using the drive motor and Lazy Susan. Additionally, we were able to show effective and consistent communication of multiple bytes of data from MATLAB to the master PIC vis RS-232. Unfortunately, we were unable to get the hardware for I2C working, despite the code working on Matt's setup. Overall, we were pleased with our progress in a relatively short amount of time.

We hope to fix the hardware issue in the near future and possibly consolidate all the circuitry onto a PCB for a more robust device. We would also like to add a hall effect switch or limit switch to indicate a set "Home" position. Additional work can be done on the motor control functions to implement feedback control as necessary. As there are clients that would like to see this project come to fruition, we want to make sure they are given a robust and flexible system for their use.

Indoor Localization System

2008-03-29T21:12:38Z

ScottMcLeod: /* How to Run the Program */

File:Visual localization data.jpg

2008-03-29T21:11:42Z

ScottMcLeod: Real-Time Visual Localization Data

Real-Time Visual Localization Data

File:Visual localization real time.jpg

2008-03-29T21:11:15Z

ScottMcLeod: Real-Time Visual Localization Tracking

Real-Time Visual Localization Tracking

File:Visual localization calibration alignment.jpg

2008-03-29T21:10:49Z

ScottMcLeod: How to Align Calibration Patterns for Visual Localization System

How to Align Calibration Patterns for Visual Localization System

Indoor Localization System

2008-03-29T21:10:11Z

ScottMcLeod: /* How to Run the Program */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software (though this has not been implemented).

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

[[Image:visual_localization_calibration_alignment.jpg|center|thumb|300px|Calibration Pattern Alignment]]

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.
[[Image:visual_localization_real_time.jpg|center|thumb|300px|Real-Time Processing]]
[[Image:visual_localization_data.jpg|center|thumb|300px|Real-Time Data]]

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T20:25:07Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software (though this has not been implemented).

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T01:29:14Z

ScottMcLeod: /* Pattern Isolation */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T01:28:45Z

ScottMcLeod: /* Pattern Isolation */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T01:24:03Z

ScottMcLeod: /* Computer Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install the Logitech QuickCam Deluxe Webcam Drivers - http://www.logitech.com/index.cfm/435/3057&cl=us,en

2. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

3. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

4. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

5. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

6. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

7. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T01:21:06Z

ScottMcLeod: /* Real time Adjustable Parameters = */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

2. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

3. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

4. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

5. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

6. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ===
During the real time operation of the program, many of the algorithm parameters will need to be adjusted for the current setup. These parameters and keys are listed below.

'+'/'-': Binary Thresholding: To adjust the black and white levels, use the + and - keys to increase or decrease the threshold. Ideally, this should be increased as high as possible without producing random noise.

'['/']': Target Size: This measurement corresponds to the maximum distance between dots in a target. If your 3x3 grid is spaced at 1 inch intervals, this value is ideally 1 inch. This parameter should be decreased as much as possible before targets are lost. If this parameter is too large, the algorithm will blend the patterns together.

'z'/'x': Area Thresholding: This parameter controls the desired size of 'dots'. This is used to remove relatively large or small noise artifacts. This parameter should be as large as possible to remove specular noise.

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T01:14:57Z

ScottMcLeod: /* How to Run the Program */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

2. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

3. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

4. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

5. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

6. Download the program as listed at the end of this page.

=== How to Run the Program ===

Open the project file as listed at the bottom of this page. Compile and run the program from Visual Studio or as in the build folder.

Once running, the program should outline what is necessary to setup and operate. The steps are also outlined below.

1. Connect to cameras. You will have to type the 4 numbers (in the command prompt) associated with the correct capture devices. Most likely, these will be 0-3.

2. Orient cameras. To correlate an individual camera with its position overhead, you must click once on the quadrant corresponding to the live camera image shown. You will click 4 times, once for each camera.

3. Check. Once you have selected the quadrants for each camera, you can look at the combined image in the main window to make sure the cameras are positioned correctly and that the background is all white. Press the Enter button in the main window to continue.

4. Enter Calibration Parameters. To calibrate the cameras to world coordinates, you must type in numbers relating to the patterns positions. Ensure that you place the patterns down in a rectangular fashion (in the world frame not the images). The numbers are typed into the command prompt. You will enter three numbers as measured (they may be in inches or cm or whatever unit desired).

5. Capture Calibration Pattern. To calibrate the cameras, you must now take a picture of the patterns as viewed by ALL FOUR Cameras. By now, you should have the calibration pattern arranged on the surface. ****ENSURE THAT THE ONLY VISIBLE OBJECTS IN THE IMAGE ARE THE DOTS FROM THE CALIBRATION PATTERN**** The program is designed to calibrate to the first 9 dots in each image that it sees. If there are more than 9 dots in ANY camera image, the program will correlate the FIRST 9 dots to the measured positions. If one camera sees more than one calibration pattern (fully or partially) it will NOT calibrate properly. You may adjust the threshold with the + and - keys dynamically to remove any specular noise.

6. Remove the Calibration Pattern. Now remove or cover up the calibration dots and press 'Enter' to proceed to the real time operation of the program.

=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:59:35Z

ScottMcLeod: /* Computer Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

2. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

3. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

4. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

5. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

6. Download the program as listed at the end of this page.

=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:58:36Z

ScottMcLeod: /* Computer Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx

2. Download and install Microsoft Windows Platform SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=0BAF2B35-C656-4969-ACE8-E4C0C0716ADB&displaylang=en

3. Download and install Microsoft DirectX 9+ SDK - http://www.microsoft.com/downloads/details.aspx?FamilyId=572BE8A6-263A-4424-A7FE-69CFF1A5B180&displaylang=en

4. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

5. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:55:49Z

ScottMcLeod:

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express - http://www.microsoft.com/express/default.aspx.

2. Download and install Intel OpenCV Library - http://sourceforge.net/projects/opencvlibrary/

3. Download and install the videoInput Library - http://muonics.net/school/spring05/videoInput/

=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:54:16Z

ScottMcLeod: /* Computer Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
In the current implementation, this system has been developed for a Windows based computer (as restricted by the videoInput library). The system should run in Windows XP or Vista. To setup the computer to develop and run the software, the three required libraries must be installed.

1. Download and install Microsoft Visual Studio Express here.
2. Download and install

=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:50:10Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired ALL WHITE area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:18:55Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.
 

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-29T00:18:03Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Approximate Viewing Angle of Logitech Cameras]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

File:Visual localization viewing angle.jpg

2008-03-29T00:17:17Z

ScottMcLeod: Viewing angle of logitech cameras

Viewing angle of logitech cameras

Indoor Localization System

2008-03-29T00:16:50Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).

[[Image:visual_localization_viewing_angle.jpg|right|thumb|300px|Pattern Recognition]]

Before attaching the cameras, several considerations must be made.

'''1. Choose a desired area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-28T23:48:30Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).
Before attaching the cameras, several considerations must be made.

'''1. Choose a desired area to cover.''' '''***IMPORTANT: If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera***''' Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-28T23:48:09Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).
Before attaching the cameras, several considerations must be made.

'''1. Choose a desired area to cover.''' ***If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera*** Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

'''2. Ensure that the cameras are all facing the same direction. ''' As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

'''3. Try to mount the cameras as "normal" as possible.''' Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-28T23:47:42Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).
Before attaching the cameras, several considerations must be made.

1. Choose a desired area to cover. ***If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera*** Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.

2. Ensure that the cameras are all facing the same direction. As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.

3. Try to mount the cameras as "normal" as possible. Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-28T23:47:27Z

ScottMcLeod: /* Camera Setup */

== Motivation ==

For relatively simple autonomous robots, knowing an absolute position in the world frame is a very complex challenge. Many systems attempt to approximate this positioning information using relative measurements from encoders, or local landmarks. Opposed to an absolute system, these relativistic designs are subject to cumulating errors. In this design, the positioning information is calculated by an external computer which then transmits data over a wireless module.

This system can be envisioned as an indoor GPS, where positioning information of known patterns is transmitted over a wireless module available for anyone to read. Unlike a GPS, this vision system is designed for indoor use on a smaller scale (in/cm).

== Overview of Design ==

This system uses four standard webcams to locate known patterns in a real time image, and transmit positioning information over a serial interface. This serial interface is most often connected to a wireless Zigbee® module. The cameras are mounted in fixed positions above the target area. The height of the cameras can be adjusted to increase either the positioning resolution or the area of the world frame. These constraints are a function of the field of view of the lenses. Below is a diagram illustrating this system’s basic setup.

[[Image:visual_localization_system.jpg|center|thumb|600px|Overview of System]]

Here, we can see the four cameras are mounted rigidly above the world frame. Note that the cameras actual placement must have an overlap along inside edges at least the size of one target. This is necessary to ensure any given target is at least fully inside one camera’s frame.

== Goals ==
• To provide real-time (X, Y, θ) position information to an arbitrary number of targets (<20) in a fixed world frame using a home-made computer vision system.

• Maximize throughput and accuracy

• Minimize latency and noise

• Easy re-calibration of camera poses.

• Reduced cost (as compared to real-time operating systems and frame grabbing technology)

== Tools Used ==
=== Software ===
• IDE: Microsoft Visual C++ Express Edition – freeware (http://www.microsoft.com/express/default.aspx)

• Vision Library: Intel OpenCV – open source c++ (http://sourceforge.net/projects/opencvlibrary/)

• Camera Capture Library: VideoInput – open source c++ (http://muonics.net/school/spring05/videoInput/)

=== Hardware ===

• Four Logitech QuickCam Communicate Deluxe USB2.0 webcams

• One 4-port USB2.0 Hub

• Computer to run algorithm

== How to Use The System ==
=== Camera Setup ===
The four cameras used were standard Logitech QuickCam Communicate Deluxes. For future use, the videoInput library used is very compatible and works with most capture devices. As measured, the viewing angle (from center) of the Logitech cameras was around 30 degrees (horizontal plane) and 25 degrees (vertical plane).
Before attaching the cameras, several considerations must be made.
1. Choose a desired area to cover. ***If you want to be able to cover an continuous region, the images as seen by the cameras must overlap to ensure a target is at least fully visible in one frame of a camera*** Keep in mind that there is a trade-off between area, and resolution. In addition, the size of the patterns will have to be increased above the threshold of noise.
2. Ensure that the cameras are all facing the same direction. As viewed from above, the "top" of the cameras should all be facing the same direction (N/S/E/W). For future use, if these directions must be variable, the image reflection and rotation parameters can be adjusted in software.
3. Try to mount the cameras as "normal" as possible. Although the camera calibration should determine the correct pose information, keeping the lenses of the cameras as normal as possible will reduce the amount of noise at the edges of the images.

=== Computer Setup ===
=== How to Run the Program ===
=== Real time Adjustable Parameters ====

== Algorithm Design ==
=== Overview ===
To identify different objects and transmit position and rotation information a 3x3 pattern of black circles is used for each object. To create both position and orientation, each pattern must have at least 3 dots in a rotationally invariant configuration. The algorithm identifies unique patterns by assuming dots within a certain adjustable distance are part of the same pattern. It then identifies which pattern is associated with the dots via a comparison of the relative distances between the dots.

=== Pre-Processing ===
==== Target Classification ====
Before the system is executed in real time, two tasks must be completed. The first is pre-processing the possible targets to match (the patterns of 3x3 dots). This is done by first creating a subset of targets from the master template. Each target must be invariant in rotation, reflection, scale and translation. A set of targets has been included in the final project, with sample patterns. When the program is executed in real time, it will only identify targets from the trained subset of patterns.

When the targets are pre-processed, unique information is recorded to identify each pattern. In particular, the algorithm counts the number of dots and the relative spacing between each dot. In this sense, the pattern is identified as a unique number (corresponding to the order of target patterns in the image directory), the number of dots in the pattern, and the normalized spacing between each dot. Since the pattern is a fixed 3x3 grid, the only possible spacing between dots is 1, √2, 2, √5, or √8 units. As in networking theory, this is a fully connected network and thus has at most n*(n-1)/2 links. Since the most number of dots in a pattern is 9, the maximum number of interspacing distances is 9*8/2 = 36.

The last piece of information recorded is the orientation of the target. Below is a picture of this configuration. *Note to change the target, various dots are removed.

[[Image:visual_localization_patterns.jpg|center|thumb|300px|Pattern Recognition]]

==== Camera Calibration ====
The second required step before the system can be used is training the cameras both their intrinsic parameters (focal length, geometric distortions, pixel to plane transformation) and their extrinsic pose parameters (rotation and translation of origins). In other words, the pixels in the image must be correlated to the world frame in centimeters or inches. This step is performed by using a simple linear least squares best fit model. The calibration process needs at least 6 points as measured in the world and image frames to compute a 3x4 projection matrix. In practice, we use more than these 6 points to add redundancy and help best compute an accurate projection matrix. The method used is outlined in ''Multiple View Geometry in Computer Vision'' by Richard Harley and Andrew Zisserman.

=== Real Time Operation ===
In the actual operation of the program, it flows in an infinite loop performing three basic tasks. As soon as all four cameras have reported a new frame, the program follows the following outlined steps.

==== Image Formation ====
First, the computer converts the image to a grayscale (0-255) image. After this operation is performed, the algorithm thresholds the image based on a set level. This converts the grayscale image to a binary image by converting colors above the threshold to white (255) and all other values to black (0). After these two operations are performed, the resultant image is a black and white binary image. The default threshold level is set to 80.

==== Pattern Isolation ====

After the image has been prepared in the binary format, all the contours must be outlined. This process is known as connected-component-labeling (CCL) in computer vision. This process identifies continuous “blobs” or regions of pixels that are adjacent. In OpenCV the connected components are stored into a linked list data structure called a contour.
Fortunately, the connected component labeling process is a native function of OpenCV and we only have to process the resultant contour data structure. To do this, the program iterates through each contour in the data structure, extracting position and area information (in pixels). This data is stored into a custom data structure called dotData. While processing each contour, the algorithm groups the individual dots into their 3x3 patterns by using a second custom data structure called a “target”. The target data structure is a linked list and has elements for the number of dots in the pattern, dotData structures for each dot in the pattern, and other data to be generated later such as group position and orientation. To group the dots into targets, the program follows the outlined algorithm.

1. For each new dot, check each dot inside each existing target.

2. If there exists a dot in any target such that the new dot is within the maximum spacing between dots, add the new dot to this target.

3. Else; create a new target and add the new dot to the new target.

We can see that this is not necessary the best method for grouping dots together as it is based on a maximum distance between dots. In fact, this forces the patterns to be a certain distance away from each other to avoid confusion. In concept, the patterns should be at least half the size of the robot to avoid this conflict. The benefits of this classification scheme are its simplicity and speed for computation.

==== Pattern Identification ====
Once the contours (dots) have been grouped into the linked list of targets, the targets must be matched to the trained patterns. This data appears extremely robust since the spacing between dots is at such clean and quantized intervals. To match each target to a trained pattern, the algorithm compares all patterns with the same number of dots and searches for the best match. The comparison between patterns with the same number of dots is done with a simple squared differences error calculation. After this process, each region of dots is classified by the global number as trained by the pre-processing algorithm.

==== Position and Angle ====
To calculate the position and orientation of each target, the camera calibration matrix comes into play. First, the position is calculated by finding the center of mass of each dot in a target in the image frame (pixels). For each dot, the camera calibration matrix is used to transform this data into world coordinates. Finally, the world coordinates of the dots are summed to find the group center of mass. This group center of mass becomes the world coordinates for the target position. To calculate the angle, specific angle information is extracted from the patterns. This angle information is then used in combination with the pre-processed offset angle to generate a group orientation. These two vectors are then sent out to the user-specified serial port.

==== Blind Spot Rejection ====
Since the images recorded by the cameras overlap by at least the size of one pattern, the algorithm will identify the same pattern for each overlapping section. Ideally, the images of the cameras would be perfectly matched such that this information was redundant. In practice, the simple camera calibration scheme results in slightly different data. When the same pattern is identified in multiple images, it position information is averaged. The other scenario for errors is if a pattern is only partially visible in one image (which can make it appear as a different pattern). To correct this problem, the algorithm analyzes the individual outputs of each image at the same time. If any two patterns are within the thresholded distance of each other, the program rejects the pattern with fewer dots.

== Final Project Code ==

Indoor Localization System

2008-03-28T23:35:12Z

ScottMcLeod: /* Camera Setup */

Indoor Localization System

2008-03-28T23:31:41Z

ScottMcLeod: /* Results */

Indoor Localization System

2008-03-28T23:31:10Z

ScottMcLeod: /* How to Use The System */

Indoor Localization System

2008-03-28T23:29:31Z

ScottMcLeod:

Indoor Localization System

2008-03-28T23:29:13Z

ScottMcLeod: /* Algorithm Design */

Indoor Localization System

2008-03-28T23:24:33Z

ScottMcLeod: /* Real Time Operation */

Indoor Localization System

2008-03-28T23:23:26Z

ScottMcLeod: /* Overview */

Indoor Localization System

2008-03-28T23:20:01Z

ScottMcLeod:

Indoor Localization System

2008-03-28T23:07:28Z

ScottMcLeod: /* Motivation */

Intelligent Oscillation Controller

2008-03-20T17:13:00Z

ScottMcLeod: /* Circuitry */

== Team Members ==
'''Scott Mcleod:''' ''Electrical Engineering Class of 2009''

'''Brett Pihl:''' ''Mechanical Engineering Class of 2008''

'''Sandeep Prabhu:''' ''Mechanical Engineering Class of 2008
''

== Overview ==

The overall goal of this project is to create a system that induces a forcing function upon a basic, spring, mass, wall system to achieve an arbitrary periodic acceleration profile (a combination of a 10 and 20 Hz sine wave for our system) on the mass. An accelerometer is mounted upon the mass in the system. A PIC microprocessor records this acceleration data as well as controls a speaker (with the help of a DAC) that provides the external force to the system. This PIC communicates with MATLAB via Serial RS-232 communication. MATLAB processes this data and sends back a control signal for the speaker. After several iterations the actual mass acceleration profile begins to match the chosen profile it is told to "learn."

== Mechanics ==

The basic mechanical system for this device is a simple one, but must be assembled with precision. The major components are the speaker, linear ball bearings on a precision rod, and a spring. First, the speaker is mounted perpendicular to the ground. This must then be attached via a rod to the mass. We tried several approaches, but what seemed to be the best solution was to epoxy about a one inch section of PVC pipe to the center of the speaker. The diameter of the pipe we used matched the diameter of the junction in the speaker where the cone turns from concave to convex. This pipe also had two tapped holes running along the length of the section for a plate to attach to. The plate attached to this PVC also had a threaded hole in the center for the rod that attaches to the mass. The forces exerted by the speaker are small enough (our measurements show only about 3 Newtons) that only about an 8 ounce mass is needed. The bearing we used didn't require any additional mass to satisfy this constraint. The other end of the rod simply attached to the block which we machined and mounted atop the bearing. A piece of sheet metal was screwed into the other side of the block with spacers. This piece of metal is used to anchor spring to the mass, and allows the spring to easily be removed. A similar piece of sheet metal is attached to the wall on the opposite side of the spring. However, this sheet has a vertical slot about an eighth of an inch wide cut from the bottom. This allows the coil of the spring to slide up further on the plate, thereby creating a more solid connection.

It is important to design each component with all other components in mind at the same time. Mainly, making sure that the linear slide is level, and the rod attached to the speaker is centered, level, and in line with the mount on the mass and spring on the opposite side of the mass. This will help to ensure that all motion in the system is one dimensional.

The above was not the first iteration of our mechanical design. We originally had a homemade linear slide. However, we found the lack of precision resulted in unreliable bode plots of the system due to loose tolerances of the design creating side-to-side motion. The first iteration also had the rod epoxied directly to the mass and speaker. During initial testing the connection between the speaker and rod actually severed.

This current design is advantageous because it is modular. The threaded rod allows for minor distance changes to ensure the spring attached to the wall is at its natural rest length. To attach it the plate is detached from the PVC on the speaker and screwed onto the rod. With the spring detached, the other end of the rod is screwed into the threaded hole on the mass. Finally, the plate is then screwed into the PVC through the threaded holes. The non-permanent spring attachment also allows for springs with different k-values to be added to the system. If the spring is longer or shorter then desired, a simple change in rod length is all that is needed to incorporate the new spring into the system.

== Circuitry ==

[[Image:LearningOscMC |thumb|150px|right| Main Circuit]]

[[Image:LearningOscAM |thumb|150px|right| Accelerometer on mass]]

The main elements of the circuit were a PIC, DAC ([[http://hades.mech.northwestern.edu/wiki/index.php/PIC18F4520:_Serial_Digital-to-Analog_Conversion Digital-to-Analog converter]]) and accelerometer. The PIC would store a discretized sine waveform with integer values from 0-255. It would then output a function of this sine wave (our control signal) to the DAC. The analog signal output from the DAC would be sent to the amplifier, which would then power the speaker. The accelerometer on the mass would feedback the actual acceleration profile of the mass back to Matlab. Matlab would then recompute the next control signal and repeat the cycle until the mass was moving with the desired acceleration profile.

 

== Programming ==
=== PIC Code ===
In our project, a PIC was used to drive the speaker via its I2C digital-to-analog converter and record accelerometer values at fixed intervals. Since the control system’s algorithm requires too much processing for the PIC, all the computations are performed in Matlab after the accelerometer data is transported to a computer via a serial cable. This setup simplified the program for the PIC.

To generate the waveform of voltage levels sent to the speaker, a single quantized period was used. Since the waveform is periodic in nature, the wave can be repeated indefinitely in a continuous fashion. The nature of our processing algorithm constrained the number of samples for the accelerometer data to be equal to the number of samples for the control voltage.

Since our system used a waveform of fixed intervals, we used an interrupt service routine (ISR) to change the wave and record accelerations at precise intervals. We chose to sample each signal every 1ms (as this is an achievable I2C speed and ISR). To oscillate our system at 10 and 20Hz, we needed at least 100 samples per waveform (1/10Hz / 1ms = 100 samples/waveform). For this reason, we created two 100-byte long vectors for the control voltage ‘u’, and the acceleration data ‘acc’.

[[Media:ME333_Learning_Oscillator_pic_main.c|'''PIC Learning Control''']]
[[Media:ME333_Learning_Oscillator_pic_bode.c|'''PIC Bode Plot Generator''']]

=== Matlab Code ===
The Matlab code simply follows the protocol as established above. The user specifies in Matlab the parameters for the amplitude and phase of the desired acceleration waveform. *Note that the frequencies of these waves are set to 10 and 20Hz (as constrained by the transfer functions captured from the Bode and the periodic nature of 100 samples/wave).

Below are the 4 m files used in Matlab. Their names must be changed to the last part of their filenames as they are functions.

[[Media:ME333_Learning_Oscillator_main.m|'''Main Matlab Loop''']]
[[Media:ME333_Learning_Oscillator_learn.m|'''Learning Control Algorithm''']]
[[Media:ME333_Learning_Oscillator_smooth.m|'''Smoothing Algorithm''']]
[[Media:ME333_Learning_Oscillator_startplot.m|'''Plot Initialization Code''']]
[[Media:ME333_Learning_Oscillator_bode.m|'''Bode Plot Generator''']]

=== Program Flow ===

[[Image:Oscillator_Program_Flow.jpg|center|thumb|400px|Program Flow]]

=== Control System ===
To “learn” the control voltages to create a desired waveform, a simple proportional control system was used. We should note much of this code was developed, tested and debugged by Tom Vose, who was invaluable to our final project. Below is our understanding of Tom’s control algorithm.

The system first guesses a control voltage of all zeros. This ideally results in no forcing of the speaker and a flat response of acceleration. After this initial guess, the program uses proportional control to match the desired acceleration waveform. Mathematically, it multiplies the error by a proportional factor k. The error is computed by subtracting the Fast Fourier Transform (fft) of the measured acceleration from the fft of the desired acceleration. This error is multiplied by the proportional control k, and two discrete Bode plot values corresponding to the transfer function of voltage to acceleration at 10 and 20Hz. The resulting signal is the control signal u, in the frequency domain. From here, the control signal is converted back to the time domain via an inverse fft, and sent to the PIC. All of the math is computed in discrete time, for the waveforms of 100 samples long. Below is a block diagram of this control system. Note that it is in the standard unity feedback form.

[[Image:Oscillator_Control_System.jpg|center|933x200 px|Learning Control System]]

== Results ==
Below are three tests performed on various superpositions of sin waves at 10 and 20Hz. We have adjusted the phase of the waves to produce different results.

<gallery Caption="Matlab Plots Acceleration Desired vs. Experimental Acceleration">
Image:Oscillator_test1.jpg|Wave 1
Image:Oscillator_test2.jpg|Wave 2
Image:Oscillator_test3.jpg|Wave 3
</gallery>

Each diagram, shows one period of an acceleration profile. The faint blue curve in the left subplot is the desired acceleration motion. The red lines on top of the blue curve are experimental accelerations as recorded by the pic. We can see that the red lines converge on top of the desired blue motion. The right subplot (green) shows the learned voltage waveform to create the desired acceleration profile.

Each wave follows the equation below with the given parameters:

acceleration_desired = amp1*sin(2*pi*base_freq*t+phi1) + amp2*sin(2*pi*(2*base_freq)*t+phi2)

Wave 1: phi1 = 1, phi2 = 2
Wave 2: phi1 = 0, phi2 = 0
Wave 3: phi1 = 1, phi2 = 0

== Potential Applications ==

A common question regarding this project is its applications to the real world. In the Northwestern University LIMS lab, a similar type of undertaking is being researched, but on a much grander scale. This same type of oscillation control is being done for 6 dimensions (X, Y, Z, Roll, Pitch, Yaw). However, the microprocessors used in this type of control are extremely expensive, and this one dimensional test of a learning system provides a possibly cheaper solution. The six dimensional control system has possible real-world applications in product assembly.

== Reflections ==
Great results were achieved from the learning algorithm. For engineers working on it in the future, here are some topics for further investigation to get a more complete understanding about the control system:

* In this project, the control signal was manually phase-shifted by pi radians before outputting it to the speaker
** This made the algorithm work perfectly
** It is not well-understood why this step was necessary
** The algorithm would not work otherwise

* In the input for the FFT, the transfer function used in this project did not have an imaginary component
** The robust algorithm still worked perfectly, and would shift phase and 'learn' when the program was run
** In future experiments, a transfer function including an imaginary term could be used, to fully utilize the capabilities of the algorithm

* Faster learning
** The various constants in the algorithm equations can be tweaked for faster learning
** Currently, it takes about 10-20 iterations to hit the desired waveform
** More rapid learning would be a huge benefit in real-world applications

== References ==
* [http://electronics.howstuffworks.com/speaker5.htm How speakers work]
* [[Iterative Learning Control]]
* [http://lims.mech.northwestern.edu/~lynch/ Professor Kevin Lynch]
* [http://lims.mech.northwestern.edu/students/vose/ Tom Vose], author of the learning algorithm used in this project

File:ME333 learning oscillator.jpg

2008-03-20T00:23:12Z

ScottMcLeod: Project Picture

Project Picture

ME 333 final projects

2008-03-20T00:22:48Z

ScottMcLeod: /* Intelligent Oscillation Controller */

'''[[ME 333 end of course schedule]]'''

__TOC__

== ME 333 Final Projects 2008 ==

=== [[IR Tracker]] ===

[[Image:IR_Tracker_Main.jpg|right|thumb|200px]]

The IR Tracker (aka "Spot") is a device that follows a moving infrared light. It continuously detects the position of an infrared emitter in two axises, and then tracks the emitter with a laser.

 

=== [[Robot Snake]] ===
[[Image:HLSSnakeMain.jpg|right|thumb|200px]]

A wirelessly controlled robotic snake which uses a traveling sine wave and servo motors to mimic serpentine motion. The snake is capable of going forward, left, right and in reverse.

 

=== [[Programmable Stiffness Joint]] ===

[[Image:SteelToePic.jpg|thumb|200px|The 'Steel Toe' programmable stiffness joint|right]]

The Programmable Stiffness Joint varies rotational stiffness as desired by the user. It is the first step in modeling the mechanical impedance of the human ankle joint (both stiffness and damping) for the purpose of determining the respective breakdown of the two properties over the gait cycle.

 

=== [[Magnetic based sample purification]] ===

 

=== [[Continuously Variable Transmission]] ===

[[image:CVT_setup1.jpg|thumb|200px]]

A continuously variable tramsission is intended to provide a transition from low to high gear ratios while keeping the engine input running at the max efficient speed. It is achieved by a system of variable radius pulleys and a v-belt.

 

=== [[Granular Flow Rotating Sphere]] ===

This device will be used to study the granular flow of particles within a rotating sphere. The sphere is filled with grains of varying size and then rotated about two different axes according to a series of position and angular velocity inputs.

 

=== [[Vibratory Clock]] ===

[[Image:Vibratory_Clock.jpg|right|thumb|Vibratory Clock|200px]]

The Vibratory Clock allows a small object to act as an hour "hand" on a horizontal circular platform that is actuated from underneath by three speakers. The object slides around the circular platform, impelled by friction forces due to the vibration. [http://www.youtube.com/watch?v=PV9utFL5J6w Check it out!]

 

=== [[WiiMouse]] ===

[[Image:HPIM1027.jpg|right|thumb|200px]]

The WiiMouse is a handheld remote that can be used to move a cursor on a windows-based PC, via accelerometer input captured through device movement.

 

=== [[Intelligent Oscillation Controller]] ===

[[image:ME333_learning_oscillator.jpg|thumb|200px]]

This device "learns" a forcing function that is applied to a spring and mass system to match an arbitrary, periodic acceleration profile.

 

=== [[Baseball]] ===

[[Image:Baseball_Playfield.jpg|right|thumb|200px]]

An interactive baseball game inspired by pinball, featuring pitching, batting, light up bases and a scoreboard to keep track of the game.

Interfacing to External EEPROM

2008-03-20T00:19:19Z

ScottMcLeod: /* Circuit */

== Overview ==

An external EEPROM can be useful for several different reasons.
External EEPROMs allow much more data to be stored than is available on the 18F4520. In addition, EEPROM memory saves state when power is removed.

In this project, we interfaced to a Microchip EEPROM in random read/write mode. "Random" write mode specifies that the memory locations accessed do not come in any sequential form. Although one can use this mode to access data sequentially in the EEPROM, there is a different protocol structure for sequential reads that increases throughput. In this project, we only developed the random write protocol.

== Circuit ==

We used a Microchip 24FC515 external EEPROM.
(http://ww1.microchip.com/downloads/en/devicedoc/21673E.pdf)

To the right is the circuit diagram for interfacing to the 18F4520.

[[Image:i2c_eeprom_circuit.jpg|500x400 px|right]]

PIN1 and PIN2, A0 and A1 are hardware addressing bits, they correspond to 0xA0 (writing data) and 0xA1 (reading data). The first 4 bits are internally set to 1010 (A) and the second four correspond to the block of memory (0 or 1), A0 and A1 (hardware addressing we set to low in this circuit diagram) and read/(NOT write).

PIN3, A2 must be connected to high for normal operation.

PIN4, Vss is for grounding the chip.

PIN5, SDA is the serial data line. This is connected to RC4 (PIN18) on the PIC.

PIN6, SCL is the serial clock line. This is connected to RC3 (PIN34) on the PIC, this wire must be soldered on the left side of the board.

PIN7, WP is the write protect line which has two states. When connected to logic high, normal read/write operation can be performed. When this pin is set low, only read operations are permitted.

PIN8, Vcc is required to power the EEPROM.

[[Image:i2c_eeprom_circuit_picture.jpg|thumb|400x300 px|center|Picture of Circuit Layout]]
[[Image:i2c_eeprom_RC3_pullout.jpg|thumb|400x300 px|center|Picture of RC3 (PIN18) on PIC18F4520]]

== Code ==
Below is the code generated to interface properly to this Microchip EEPROM.
It can also be downloaded [[Media:eeprom_rand_access.c|'''here''']].

/*
eeprom_rand_access.c Scott McLeod 03-05-2008
This program shows how to interface to an I2C extrenal Microchip EEPROM.
This code is written for random reads and writes to the EEPROM
*/

#include <18f4520.h>
#fuses HS,NOLVP,NOWDT,NOPROTECT
#use delay(clock=20000000)
#use i2c(MASTER, FAST, SCL=PIN_C3, SDA=PIN_C4, FORCE_HW) // use hardware i2c controller

int8 EEPROM_WR = 0xA0; // I2C Address. 1010 0000. last bit = 0 => write command
// First Nibble is fixed as 1010 (internal address);
// Second Nibble is ABCD,
// A = Block Set
// B, C = Hardware Addresses (Configured when you Wire the CHIP)
// D = (0 = write, 1 = read)
int8 EEPROM_RD = 0xA1; // Same as EEPROM_WR except last bit = 1 for READ command

int read = 0;
int data = 128;
int16 loc;
int temp = 0;

void rand_write(int16 address, int data)
{
i2c_start(); // Claim I2C BUS
i2c_write(EEPROM_WR); // Tell all I2C devices you are talking to EEPROM in WRITE MODE
i2c_write(address>>8); // Address High Byte (0x00 - 0x)
i2c_write(address); // Address Low Byte (0x00 - 0xAA)
i2c_write(data); // Data to write
i2c_stop(); // Release BUS
delay_ms(5); // Let EEPROM Write Data (5ms from data sheet)
}

int rand_read(int16 address)
{
i2c_start(); // Claim I2C BUS
i2c_write(EEPROM_WR); // Tell all I2C devices you are talking to EEPROM in WRITE MODE
// (you are first writing to the EEPROM to set the address. Later you will read)

i2c_write(address>>8); // Address High Byte (0x00 - 0x
i2c_write(address); // Address Low Byte (0x00 - 0xAA)

i2c_start(); // RESTART I2C BUS (necissary for microchip protocol)
i2c_write(EEPROM_RD); // Tell all I2C you are talking to EEPROM in READ MODE.
read = i2c_read(); // Read in the data
i2c_read(0); // Read last byte with no ACK
i2c_stop(); // release the bus
return(read);
}

void main()
{
output_d(1); // Output a 1 for reference to start
delay_ms(1000); // *Not necissary pause, just for debugging

loc = 0x00; // Random Location in memory
temp = 15; // Byte to write
rand_write(loc, temp); // Random Write: rand_write(address, data)

output_d(255);
delay_ms(1000); // *Not necissary pause, just for visual purposes

temp = 0; // Reset temp
temp = rand_read(loc); // Random Read: rand_read(address);
output_d(temp); // Output temp

while(true)
{
}
}

Interfacing to External EEPROM

2008-03-20T00:18:52Z

ScottMcLeod: /* Circuit */

== Overview ==

An external EEPROM can be useful for several different reasons.
External EEPROMs allow much more data to be stored than is available on the 18F4520. In addition, EEPROM memory saves state when power is removed.

In this project, we interfaced to a Microchip EEPROM in random read/write mode. "Random" write mode specifies that the memory locations accessed do not come in any sequential form. Although one can use this mode to access data sequentially in the EEPROM, there is a different protocol structure for sequential reads that increases throughput. In this project, we only developed the random write protocol.

== Circuit ==

We used a Microchip 24FC515 external EEPROM.
(http://ww1.microchip.com/downloads/en/devicedoc/21673E.pdf)

To the right is the circuit diagram for interfacing to the 18F4520.

[[Image:i2c_eeprom_circuit.jpg|500x400 px|right]]

PIN1 and PIN2, A0 and A1 are hardware addressing bits, they correspond to 0xA0 (writing data) and 0xA1 (reading data). The first 4 bits are internally set to 1010 (A) and the second four correspond to the block of memory (0 or 1), A0 and A1 (hardware addressing we set to low in this circuit diagram) and read/(NOT write).

PIN3, A2 must be connected to high for normal operation.

PIN4, Vss is for grounding the chip.

PIN5, SDA is the serial data line. This is connected to RC4 (PIN18) on the PIC.

PIN6, SCL is the serial clock line. This is connected to RC3 (PIN34) on the PIC, this wire must be soldered on the left side of the board.

PIN7, WP is the write protect line which has two states. When connected to logic high, normal read/write operation can be performed. When this pin is set low, only read operations are permitted.

PIN8, Vcc is required to power the EEPROM.

[[Image:i2c_eeprom_circuit_picture.jpg|thumb|400x300 px|center]]
[[Image:i2c_eeprom_RC3_pullout.jpg|thumb|400x300 px|center]]

== Code ==
Below is the code generated to interface properly to this Microchip EEPROM.
It can also be downloaded [[Media:eeprom_rand_access.c|'''here''']].

/*
eeprom_rand_access.c Scott McLeod 03-05-2008
This program shows how to interface to an I2C extrenal Microchip EEPROM.
This code is written for random reads and writes to the EEPROM
*/

#include <18f4520.h>
#fuses HS,NOLVP,NOWDT,NOPROTECT
#use delay(clock=20000000)
#use i2c(MASTER, FAST, SCL=PIN_C3, SDA=PIN_C4, FORCE_HW) // use hardware i2c controller

int8 EEPROM_WR = 0xA0; // I2C Address. 1010 0000. last bit = 0 => write command
// First Nibble is fixed as 1010 (internal address);
// Second Nibble is ABCD,
// A = Block Set
// B, C = Hardware Addresses (Configured when you Wire the CHIP)
// D = (0 = write, 1 = read)
int8 EEPROM_RD = 0xA1; // Same as EEPROM_WR except last bit = 1 for READ command

int read = 0;
int data = 128;
int16 loc;
int temp = 0;

void rand_write(int16 address, int data)
{
i2c_start(); // Claim I2C BUS
i2c_write(EEPROM_WR); // Tell all I2C devices you are talking to EEPROM in WRITE MODE
i2c_write(address>>8); // Address High Byte (0x00 - 0x)
i2c_write(address); // Address Low Byte (0x00 - 0xAA)
i2c_write(data); // Data to write
i2c_stop(); // Release BUS
delay_ms(5); // Let EEPROM Write Data (5ms from data sheet)
}

int rand_read(int16 address)
{
i2c_start(); // Claim I2C BUS
i2c_write(EEPROM_WR); // Tell all I2C devices you are talking to EEPROM in WRITE MODE
// (you are first writing to the EEPROM to set the address. Later you will read)

i2c_write(address>>8); // Address High Byte (0x00 - 0x
i2c_write(address); // Address Low Byte (0x00 - 0xAA)

i2c_start(); // RESTART I2C BUS (necissary for microchip protocol)
i2c_write(EEPROM_RD); // Tell all I2C you are talking to EEPROM in READ MODE.
read = i2c_read(); // Read in the data
i2c_read(0); // Read last byte with no ACK
i2c_stop(); // release the bus
return(read);
}

void main()
{
output_d(1); // Output a 1 for reference to start
delay_ms(1000); // *Not necissary pause, just for debugging

loc = 0x00; // Random Location in memory
temp = 15; // Byte to write
rand_write(loc, temp); // Random Write: rand_write(address, data)

output_d(255);
delay_ms(1000); // *Not necissary pause, just for visual purposes

temp = 0; // Reset temp
temp = rand_read(loc); // Random Read: rand_read(address);
output_d(temp); // Output temp

while(true)
{
}
}