Visual Radar Detection

Final Presentation

2009-03-11T13:36:00.001-07:00

Feature Extraction

Tracking/Stabilization

Helix

Delta Matrix

2009-03-07T16:30:00.000-08:00

The following images are of Delta matrices generated by running RANSAC between every possible frame. There are 86 frames with an x and y component estimated. This created a Delta_X and Delta_Y matrix each of size 86x86.

There are instances where the RANSAC algorithm will not converge well. I indicate this by leaving an entry in the Delta matrix as . These invalid estimates are indicated by the pepper boxes that stick out in the Delta matrices.

I ran selective median filter on these matrices to remove the invalid entries. This was achieved by first starting with a 3x3 box and median filter only on locations that are invalid. Then enlarge the box to a 5x5 and refilter. Do this until all the values are gone. I padded the images by replicating the edges to account for border issues.

Another method which I will try later is to scan from left to right then top to bottom on the matrix. If an invalid entry is encountered, replace it with the previous value. For example, if the translation (x direction) from Frame 1 to Frame 20 is 10, then the translation from Frame 1 to Frame 21 should be close to 10 as well (not 1, -10, etc.).

It's noticeable that these Delta matrices are negative transposes of themselves. This is a skew-symmetric matrix. The trace of a skew-symmetric matrix is zero which indeed is the case for these Delta matrices.

What's interesting is that a skew-symmetric matrix, , satisfies

Generating the Delta matrices and then cleaning them with the median filter provide a method to stabilize any frame to another. This of course is non-causal but can provide a richer set of data to measure periodicity.

RANSAC on Translation Model

2009-03-06T19:06:00.000-08:00

I implemented a RANSAC algorithm thanks to Marco Zuliani.
This toolbox provides an engine style design where the estimate and error computing are customizable using a callback function.

The model I used was a simple translation model. The algorithm would take 2 features sets from two video frames then compute the translation vector (for stabilization).

What is important is that for each frame, 10 feature points were calculated. Now the correspondence is unknown between the two frames. Therefore I had to replicated the vectors to give the RANSAC algorithm all possible correspondences. It then selects which pairs are in consensus.

Below are plots of the results. The inliers selected by RANSAC are indicated by the boxed points.

Spatial-Temporal III

2009-03-04T10:47:00.000-08:00

Above are spatio-temporal plots of features acquired for 86 frames from ship video. For each frame a new set of features were computed and the top 10 were selected. Therefore there are 10 features for each frame. There are no correspondence assignments from frame to frame. These plots show how some features come and go as time progresses as well as the "wiggling" from an unstable video.

The idea now is to use RANSAC on these feature points to generate a delta matrix containing all the translations for any 2 frames. From that matrix we should be able to stabilize a buffered video sequence.

On a logistical note, I used matlab surface plotting to generate this:

FRAMES = 86;
mov = aviread('rdr.avi',1);
I = double(rgb2gray(mov.cdata));
[x, y, val] = klt_read_featuretable('Featgen.ft');

hold on

for k = 1:FRAMES
plot3(y(:,k),x(:,k),ones(1,10)*k,'r.')
end
legend('Feature Point')
grid on

surface(ones(720,480),flipud(I),...
'FaceColor','texturemap',...
'EdgeColor','none',...
'CDataMapping','scaled');
view(-18,72);
colormap gray

xlabel('x')
ylabel('y')
zlabel('frame')

Stablize and Helix

2009-02-27T14:55:00.000-08:00

I implemented the stabilization method proposed in the previous post. I then wrote another video filter that grabbed a scanline after each frame. Below are video sequences of these methods.

Notice that the tracking works well for several frames until all the features die off. This shows there must be a more robust method for tracking accounting for the unstable nature of the KLT feature extractions.

The helix image was generated by grabbing a 480x1 pixels scanline directly over the radar. The scanline vertical position was dependent on the stabilization parameters.

Revisiting Stabilization

2009-02-25T13:18:00.000-08:00

In order to test the algorithm I proposed in the last post I need more video samples. This has forced me to revisit stabilization.

I plan to implement a crude stabilization using KLT to get feature points and then use a variation of the trajectory conditioning algorithm presented by Rabaud and Belongie (Counting Crowded Moving Objects).

The conditioning algorithm is used in a model assuming several small pixel subsets exhibit the same translative behavior. I can simplify this by assuming there is one large subset of pixels in the video frame that exhibit the same translation. This large subset of pixels is the ship in the video sequence.

I propose a method to generate several KLT points which should be "stuck" on the ship. I then calculate the centroid of the points. The next frame I track the KLT features and compute the new centroid. The translation motion is then estimated by taking the difference of centroids.

This doesn't account for loss of features during the KLT tracking process. I am considering using a method of penalizing the translation vector estimate if features are lost. I do this by calculating the variance of the feature points in each frame. If the variance decreases, then I want the translation to be minimized.

Let's consider a 1 dimensional case.

Each horizontal line is a 1 dimensional real line where a feature point may lie at time Fx. The features are indicated by red crosses.
The blue diamond is the calculated centroid of the feature points at time Fx. The green circle is the "true" centroid of the hidden object the feature points are attached.
A solid line indicates the correct translation vector and the dashed line is the false trajectory.
The translation from F1 to F2 is correct with no variance change in the feature points.
F2 to F3 has a loss in a feature causing the variance to decrease. This causes a false trajectory estimate.
F3 to F4 also has a false trajectory due to a loss of a feature point. Note the variance decreases.
F3 to F4 has a correct trajectory estimate with the variance not changing.

From this scenario I will induce a weight term on the trajectory shown in equation (1).
(1)
is the centroid of the feature points at frame z
is the variance of the feature points at frame z
is the estimate translation

Simpler Match Metric

2009-02-20T15:20:00.000-08:00

After working with the lattice match method for measuring the period, I thought there would possibly be a simpler method given the type of data I'm working with.

Suppose I do a match metric only on the scanline plot. I would compare scanlines separted by time (in frames) and use a simple match metric (sum of absolute differences.) I also know the typical period the radar and can limit the match search window.

As shown above, a match matrix would be generated by:

(1)

Where Tmin and Tmax are the minimum and maximum period times.
is the pixel value at scanline at time (or frame)

A plot of for the stabilized scanline image is shown below:

If everything was ideal, there should be a vertical minimum channel at the period location (72 frames).

Taking a look at the 3D meshplot shows this behaviour:

If suspect that I can take the matrix and stack the rows by summing them together and select the frame that has the minimum value. That frame will correspond to the periodic rate. This indeed is the case with value of 73, which is really close. If I do the same calculation with the raw scanline image, I get a value of 71 frames. I definitely need more data to test this idea.

Lattice Match

2009-02-18T14:12:00.000-08:00

I had to decipher jargon in the Cutler-Davis paper a little bit more to figure out how they developed the algorithm to measure the periodic rate.

The following are the match measure requirements for :

(1)

(2)

The trick was to develop the matrix containing the peaks from the autocorrelation matrix,
This was achieved by gaussian filtering the autocor. matrix and then running through each pixel and label it a peak if it is a strictly maximum value within some local neighborhood radius N.

The above image is the autocorrelation matrix of the stabilized and weighted similarity matrix.

Below is image illustrating the peaks found from the autocor. matrix. where there are 7 white pixels indicating the peak locations. A neighborhood radius of 11 was chosen

The next step was to create synthetic lattice matrices parameterized by a distance value which directly relates to the periodic rate. A square lattice and a 45 degree rotated lattice are used. These lattices are labeled as in the match metric conditions in equations (1) and (2). Below is an illustration of the square and rotated lattice structures overllapping the autocorr. matrix.
The results from this technique measures a distance value of 71 frames which is very accurate. I have noticed the parameters used for selecting the peaks (such as neighborhood radius) can make the estimation way off. For instance, the minimum value a peak can have was set to 0.25 to generate the 72 frame estimate. If I changed the peak value to 0.2 then a distance of 61 frames was chosen. I will need more data sequences to test this algorithm more to see how sensitive it is to the parameters chosen.

Autocorrelation of Similarity Matrix

2009-02-16T15:42:00.000-08:00

The next step from creating similarity matrices is to generate an autocorrelation matrix. I use the matlab function normxcorr2() function for creating a normalized autocorrelation matrix.

Below is an autocorrelation plot of the similarity matrix generated by the unstabilized weighted scanline buffer. It is very difficult to see any pattern in this matrix.

Stabilizing the image affords a much more tractible autocorrelation of the similarity matrix as seen below.

Using a weight function improves the autocorrelation matrix even more:
What is interesting from these autocorrelation plots is that the peaks coincide with the periodic nature of the image sequence.

For this particular case, the distance between each peak correspond to the periodic rate of the radar. Shown below, the distance between each peak is 72 frames. This equates to 72 frames/29.97 fps = 2.4024 seconds/cycle which is roughly 25 rpm which is very accurate.

Cutler and Davis propose a mechanism for solving for the period by creating two different synthetic lattice matrices with the parameter d forming the distance between each lattice point. They run a match of these synthetic lattices with the autocorrelation matrix and choose d according to the lattice point that best matches. My first implementation of this method affords an estimate a distance of 68 instead of 72. There is an issue with implementation which I will look into later.

The main problem I see at this point is that even if I can measure the periodic rate of the radar, I'm still not detecting the position of the radar which is the main purpose of the effort. However measuring the periodicity will provide a means of queuing on pixels with this known periodic parameter.

Similarity Plots

2009-02-14T10:26:00.001-08:00

I started to follow the Cutler-Davis paper by generating similarity matrix plots. These plots are essentially recurrence matrices.

The similarity matrix was generated by using an absolute difference match metric:

(1)
Where is an image pixel value at time .

For this application, I used the buffered image created by grabbing a horizontal slice that overllaped the region where the radar was rotating. (See the Spatial-Temporal II posting)

This changes the match metric to be:

(2)
Where is all pixel coordinates in an image.
is a pixel value from the scanline buffer at time . This is simply a match metric between two scanlines separated by time. is a constant because it is just a single horizontal scanline slice at time t.

The similarity matrix, , should have a constant valued main diagonal component () which is the match of image to itself. () The diagonal is just a self-matching indicator.

If there is periodicity, there should also be a pattern of values outside the main diagonal. This is from the image matching itself a period of time later. For example, suppose you take a snapshot of a clock with the second hand over the 6. Take another snapshot 60 seconds later and the second hand is in the exact same orientation.

I also noticed that since the radar is mainly in the center column region of the temporal/spatial buffer I should probably do a weighted version of the absolute difference to attempt to ignore the irrelevant data. I did this by applying a Hanning window on each horizontal slice. This gave more weight to the region where the radar is located and does improve the similarity plots. This changes (2) into

(3)
where

(4)

and is width of the image.

In all these plots, notice the blue main diagonal running from top-left down to the bottom-right corner. Also, the lobes or peaks coincide with the periodic rate of the radar.

The best of these similarity images is the stabilized and weighted version. It has a more uniform appearance. This shows that stabilization and weighting can improve the similarity plots.

Rotation Periods

2009-02-11T14:29:00.000-08:00

RPM
I browsed around for typical rotation periods for the radars of interest. What is common among Furuno and Raytheon are the values in RPM:

24 rpm
36 rpm
48 rpm

This is an interval of 20 to 50 rpm which is equivalent to a 1.5 to 2.5 second period. This will be very useful in designing a bandpass type filter that will allow us to ignore unwanted periodic signals.

Periodic Measurement
There are at least two methods of measuring the period.

Grab a horizontal slice and match it with another frame X frames later. Do this for several slices to get a large sample size. Measure the average. This method may be a very simplified version of what Cutler and Davis do. I will need to read their paper.
Measure the harmonic signals within the "helix" shape using 1D signal processing and resolve the period value.

Spatial-Temporal II

2009-02-05T17:01:00.001-08:00

The above video is from stabilizing and differencing a ship with radar video sequence. The motion of the radar is noticed by the vertical edges of the spinning armature.

Keeping in mind the findings from the previous post, let's take a horizontal slice of each frame instead of vectorizing the whole frame. I'm going to cheat by taking a scanline that directly overlaps where the radar is located which is the 204th row. Below is a snapshot of a video frame with a yellow box indicating the general region of the scanline location.

Suppose we take a horizontal scanline at the same location for each frame and stack them into a matrix where each successive frame is a new row in the matrix. The size of this matrix is (number of frames)x(scanwidth). Essentially this new matrix is a spatio-temporal image of one slice.

What's really interesting is the result from doing this procedure on a video with a periodic rigid object.

Below is spatio-temporal image scanline of the raw video sequence (no stabilization or differencing).

The radar in this video had one side that was blue and the other side was white. This is seen in the blue boxed region. Notice the shape induced by the periodic motion of the radar is distinct, like a helix. This video sequence did not have stabilization therefore the radar "vanishes" starting near the 70th frame. This is from the ship moving up or down in the image. It is also evident the video is not stabilized from the skewed vertical lines.

The next spatial-temporal scanline image is from a stabilized version of the video. The radar "helix" signature doesn't vanish. The period can be measured by counting the number of frames between each junction. Since this video was stabilized, the vertical lines are almost perfectly verticle. One can see the left 1/3rd of the radar armature is occluded.

These images took advantage of the fact that the radar has a distinct color difference between the front and back of the armature. Looking at difference frames can possibly remove the dependence on color and still afford the same "helix" shape.

The above image is the same spatial-temporal image using the stabilized difference video shown at the very beginning of this video. The colormap "Jet" was used to enhance the lines more. It's more useful to view this with a threshold as shown below. Again, the helix shape appears.

I will investigate other video sequences with this same approach and will see if the same results occur.

Another observation was made during this process. Pertaining the previous post, it seams that if I know the periodic rate of the radar, I may be able to stabilize the image. Whereas if I stabilize the image, a periodic signal will arise.

The images generated in this post is dependent on knowing where the radar is. A brute force method may be to move the scanline sequentially until this "helix" shape appears. Or, maybe do an angled scanline instead. The line would run from top-left down to the bottom-right corner (or vice-versa). Also, I could scan vertically which would provide results similar to the previous post.

The trick is coming up with methods that are accurate but not processor intensive.

Spatial-Temporal I

2009-02-02T14:24:00.000-08:00

I was able to generate a rather stabilized image sequence using the KLT method mentioned previously. I disabled recreating features for each one lost and this provided a rather stable transformation for this particular video.

Before I delved into more research I decided to investigate the periodicity of the video sequence myself. I first grabbed the first 60 frames from the video. For each frame, I created a vector form of it using matlab. Each video frame is a 720x480 RGB frame. I converted each frame to Gray and then reshaped it into a 1x(720*480) vector. This 1x345600 vector was stored in a 60x345600 matrix: M.

The rows in M represent each frame of the video. Each column of M represented each individual pixel of the image.

I conjectured that if the video is perfectly stabilized, I should see a periodic signal in individual pixels caused by the spinning radar.

I used intuition to save time and memory by viewing the pixels that are located at the center of the video. This is because the center of the video is where the radar is located.

Below is an image of that matrix:

One can see a periodic signal within this matrix representation at pixel ranges 70, 528, 1004, and 1484. I was perplexed by the pixel locations of this periodic signal. However notice that these periodic pixels are ~480 apart. This is the width of the image.

I plotted the signals at the latter three pixel ranges and I get a desired periodic (cosine) signal. This periodic signal is verified as the same period as the radar which is 2.4 seconds. Each frame is 30ms.

What really helped in this investigation is the radar was a Furuno which has a dark blue strip on one side and is white on the other. This gives the nice pixel variation seen above.

There is a tool called Recurrence matrices which are a "qualitative and quantitative tool used to perform time series analysis of non-linear dynamical systems" (Cutler, Davis 2000) This was first introduced by Eckmann et al. in "Recurrence plots of dynamical systems". I will look into this tool to see what benefits I can gain from it. However, I may get by with just running a bandpass filter or an fft on the pixels of interest like the above.

Dirty Eyes

2009-01-27T11:34:00.000-08:00

I grabbed some video this week and ran them through my filter and found an interesting issue.
The camera I used had small hair follicle and dirt on it. This caused the KLT feature selection to select the features of the dirt over the imagery behind it.

I need to either to ignore this by cleaning the lens or take this into consideration by thinking differently about what behaviors am I interested in from the set of features.

I want features that are initially translative in "nature" to become fixed (stabilization).
Initially, I want to ignore stationary features with the assumption that there is no feature I'm interested in having the nature of being perfectly stationary. i.e. A stationary feature must be from dirt or an object stuck to the viewing apparatus that is of no interest.

Of course, the big issue is that once we are tracked, we then fall into category two where the objects on the lens are moving and the interesting features are stationary. Yikes.

Initial KLT Implementation

2009-01-19T20:18:00.000-08:00

I wrote a directshow transform filter that implements the KLT algorithm.
My goal was to get the nitty-gritty stuff completed, such as compiling issues, linking errors, image manipulation issues, etc.

This is a snapshot of graphedit using the "radar filter" I created.

I needed to convert the video frames into grayscale or convert to HSV and grab the V channel. Using OpenCV SDK was very helpful with this.

I found for the most part everything rather easy to piece together. I wrote code to overlay red crosses to indicate features being tracked. Below is a sample video of the implementation. I have better video sequences but I don't feel comfortable posting those online. This video is obscure enough to post. However it's so obscure you can see that several feature points get lost during tracking. This could be due to the fact I was using a sub-par divx decoder along with a very washed out image sequence.

The processing of the video is slow. It brings the frame rate down from 30 fps to around 2-3 fps. There exists a KLT SDK that uses the video card GPU to significantly increase speed. However I don't have a GPU to use on my laptop. For the sake of researching and investigation methods, I may have to post-process video into "stabilized" video.

Registration Investigation

2009-01-16T10:30:00.000-08:00

I manually registered images together to see how well it worked. Overall using the affine method works well.

The following image sequences are registered by pairs.

I then investigated a different video sequence. I grabbed the first frame, the 91st frame, and the 182nd frame. I then registered the 91st and 182nd frame to the first frame. I only used 3 corresponding points.

Looking carefully, the registration worked well. Also, note the blurry area caused by the rotation of the radar.

Verification of Pure Translation

2009-01-14T13:55:00.000-08:00

The goal of this investigation was to verify the assumption that the stabilization method will only require translation. The first attempt was to grab corresponding points between frames and calculate the transformation.

I grabbed 7 frames from a video sequence. The separation of time between frames was arbitrary. The above image shows such a procedure using "cpselect" from matlab. This was a very helpful tool.

I used the corresponding points from cpselect to compute a transformation matrix in matlab:

t1 = cp2tform(input_points1,base_points1,'affine');

The affine and nonreflective similarity modes gave almost the same transformation results. Each of which exhibited almost pure translation.

The tables below show the results. Given a transformation matrix with elements (a-f):
a-d is rotation
e: Translation in X direction
f: Translation in Y direction

Transformation a	b	0
c	d	0
e	f	1
Rotation				Tx	Ty
a	b	c	d	e	f
1.0008	-0.0019	0.0019	1.0008	35.6126	-5.3519
0.9924	0.0093	-0.0093	0.9924	-67.2525	15.4407
0.9962	0.0017	-0.0017	0.9962	42.1087	3.0828
1.0055	0.009	-0.009	1.0055	41.0118	-10.823
1.0102	0.0069	-0.0069	1.0102	-77.1081	1.3819
0.9964	-0.0026	0.0026	0.9964	-58.1613	20.9519

1.00025	0.003733	-0.00373	1.00025	x	x	Mean
4.3943E-05	2.89E-05	2.89E-05	4.39E-05	x	x	Variance

What is evident is the rotation is identity with very small variance.

Just from this video sequence, it appears to be safe to assume pure translation.

My next approach will be to use the KLT software development kit.

2009-01-09T16:03:00.001-08:00

Researching the Basics

I started reading the following papers:

I jumped to the Cutler/Davis paper simply because the Laptev paper referred to it multiple times. I found it useful for building a simple foundation for understanding periodic motion.

Based on the Cutler/Davis paper, w+e begin defining periodic motion for a given pixel as: At time t, a pixel point will repeat itself again at time t+p. There may be a translation, T(.), of the point at time t.

(1)

We restrict our definition of the periodic value, p, to be the smallest possible value. From this, we can define the frequency as:

(2)

A radar period, p, is a constant for each radar. However each radar has a different period.
For most cases, if there are multiple radars on a ship, they will not have the same rotation period. This is because when there are 2 or more radars, they are using different frequency bands. Each radar frequency band has a different physical size and rotation period.

From that deduction I may be able to make an assumption that if there are multiple radars in the field of view, they will not have the same period.

for (3)

Equation (3) may come in handy when we need to distinguish from multiple radars.

Stabilization
My first phase now is to stabilized the video sequence. In order to tackle this I will assume there is only translation motion. There are several methods to tackle this problem.

First I'll try doing this manually to get a good understanding of what's going on. This will be done by points on the image then finding corresponding points in successive frames. This will verify that the translation model assumption is valid.

Vincent Rabaud suggested looking into the following methods for feature tracking:
KLT: http://www.ces.clemson.edu/~stb/klt/
Black's : http://www.cs.brown.edu/~black/framework.html

Black's uses optical flow which will more than likely be expensive to compute. Therefore I will first look into the KLT (Kanade-Lucas-Tomasi) algorithm.

2009-01-07T20:52:00.000-08:00

Last year Prof. Belongie discussed this research topic and I gave him some video samples. From there he suggested:

"It looks to me like the first task is image background stabilization. It appears that an affine model would do the trick. As an example, you could try http://www.irisa.fr/vista/Motion2D/
(Laptev and I used this in http://www.irisa.fr/vista/Papers/2005_iccv_laptev.pdf
for dominant motion estimation.)
This would assume that the camera is far enough away that the ship could be approximated as a flat surface. It would also be valid if the camera is close but is restricted to move on a pan-tilt head, i.e., not able to translate.
After the stabilization step, we can proceed to study all the pixels that don't belong to that layer, e.g., the radar arm, the people on board, and noise."

My tight schedule requires me to implement background stabilization so I will look into using the Inria Motion2D functions. I have a few video samples already to try out with the software package.

I still need to gather more data using the surveillance system at work. I plan to have a controlled data set that has no motion. This will be achieved by recording a spinning radar that is mounted on top of my office building.

Typically there is more boat traffic on Fridays so I will gather several video clips this Friday.

2009-01-05T08:54:00.000-08:00

SEI stands for Specific Emitter Identification. This technology is widely referenced in the book by
Wiley R. G.: Electronic Infelligence: The Analysis of Radar Signals. Artech House, Inc, Norwood 1993

The basic idea is to collect the electronic pulse data from a radar using an antenna dish. The signal received is then processed to determine unique coefficients. These coefficients are different for each radar.

Image from SEI AND CLASSICAL PARAMETER FUSION TECHNOLOGY white paper from Litton Applied Technology

There are other requirements to properly collect information on the radar pulse.

Collect features of target (name, color, etc.)
Determine source of collection

The collection of name and color is crucial in determining the status of the radar. For instance, if the ship owner changed radars, a collection will notice this only if features of the ship are collected.

Determining the source of collection is crucial to provide collection integrity. A collection antenna is capable of receiving signals with a wide acceptance angle. A human-in-the-loop must determine the signal received is from the expected source. This is done by listening to the pulse generated by the antenna and watching the rotation of the radar. Verification is met when the pulse and postion of the radar are in sync.

This leads to determining the rotation of the radar with computer vision to eliminate the need for human intervention.

The above video demonstrates a typical scenario for detecting the spin of a Radar. It shows potential artifacts that must be accounted for in detecting periodicity:

Flag motion
Rotation of a second radar
People walking nearby
Birds flying across field of view