Video Motion Detection

[Luhan]

Hi,

I got this idea on video motion detection and built it. It works.

http://members.cox.net/berniekm/vax.html

My question is: has anybody done it this way before? (Referring to
figures 1,2, and 3)

Lemme know.

Luhan

 

[Rich Grise]

Hi,

I got this idea on video motion detection and built it. It works.

http://members.cox.net/berniekm/vax.html

My question is: has anybody done it this way before? (Referring to
figures 1,2, and 3)

Lemme know.

I like it a lot. It somehow reminds me philosophically, of an idea
I had for a speakwrite, but the spectral pattern recognition was beyond
my expertise. )-;

Thanks,
Rich

 

[Joel Kolstad]

I got this idea on video motion detection and built it. It works.
http://members.cox.net/berniekm/vax.html

Clever design, Luhan... well done!

 

[Jim Thompson]

Clever design, Luhan... well done!

Indeed!!

...Jim Thompson

 

[Mochuelo]

Hi,

I got this idea on video motion detection and built it. It works.

http://members.cox.net/berniekm/vax.html

My question is: has anybody done it this way before? (Referring to
figures 1,2, and 3)

Lemme know.

Luhan

If an object the size of one cell moves diagonally one position
(vector=(+1,+1)) along certain diagonals, none of your three sums will
detect it.

You can use cyclic redundancy codes (CRC) to detect almost any kind of
change in the picture. Just feed the 64 samples serially, and keep the
remainder of the polynomial division. 8-bit CRC should probably be
enough, but 16-bit would be safer, and it is quite easy to compute it.
There are many C and assembly CRC libraries on the internet.

Best,

 

[Joerg]

Hello Luhan,

I got this idea on video motion detection and built it. It works.

http://members.cox.net/berniekm/vax.html

My question is: has anybody done it this way before? (Referring to
figures 1,2, and 3)

Lemme know.

Very clever. Haven't seen anything like it. In filter design or
ultrasound, yes, but not with video.

Hey, maybe you could patent that? Oh wait, I don't know but a usenet
post would probably constitute a publication.

 

[Luhan]

If an object the size of one cell moves diagonally one position
(vector=(+1,+1)) along certain diagonals, none of your three sums will
detect it.

You can use cyclic redundancy codes (CRC) to detect almost any kind of
change in the picture. Just feed the 64 samples serially, and keep the
remainder of the polynomial division. 8-bit CRC should probably be
enough, but 16-bit would be safer, and it is quite easy to compute it.
There are many C and assembly CRC libraries on the internet.

Best,

Its true that there are some cases where the object is not detected,
but a moving object is unlikely to contantly move in such specific
directions.

Using a simple checksum makes the system overly sensitive to ambient
light variations. This is just the opposite of detecting objects. The
+/- operations cancel out much of the ambient variations.

I'm not sure how a more complex CRC would react, but that is an idea.

Luhan

 

[Luhan]

Its true that there are some cases where the object is not detected,
but a moving object is unlikely to contantly move in such specific
directions.

Using a simple checksum makes the system overly sensitive to ambient
light variations. This is just the opposite of detecting objects. The
+/- operations cancel out much of the ambient variations.

I'm not sure how a more complex CRC would react, but that is an idea.

Luhan

Yikes! A CRC will not work at all. There is no way to set a
'threshhold' level for detecting significant changes vs random
variations.

Luhan

 

[Mochuelo]

Its true that there are some cases where the object is not detected,
but a moving object is unlikely to contantly move in such specific
directions.

Using a simple checksum makes the system overly sensitive to ambient
light variations. This is just the opposite of detecting objects. The
+/- operations cancel out much of the ambient variations.

Just remove the dc offset from the 64 samples, and then send them to
the CRC.

Best,

 

[Luhan]

Just remove the dc offset from the 64 samples, and then send them to
the CRC.

CRC's cannot be used. They respond wildly to even a singe bit change.
Since there is always some variation in the video data, the CRC would
change with every video frame regardless of whether motion was present.

Luhan

 

[Mochuelo]

Yikes! A CRC will not work at all. There is no way to set a
'threshhold' level for detecting significant changes vs random
variations.

[...]

CRC's cannot be used. They respond wildly to even a singe bit change.
Since there is always some variation in the video data, the CRC would
change with every video frame regardless of whether motion was present.

What do you mean by "will not work at all," "there is no way" and
"cannot be used"? You mean:

a) Nobody can come up with a way to use CRCs in this application, and
end up with better performance than with your proposed scheme.
b) You can't.

a or b?

 

[Ken Smith]

CRC's cannot be used. They respond wildly to even a singe bit change.

Since there is always some variation in the video data, the CRC would
change with every video frame regardless of whether motion was present.

If you reduce the number of values and the number of bits in each sample,
you reduce the odds of a change of one bit. If backlash is built into the
digitizer, a further reduction in the odds can be had. If we are looking
for a change in the picture that is large enough, the CRC will work.

The way I would attack doing it with a CRC (assuming I had to) would be to
do the following.

(1) Run the video signal into a "log(x)" circuit so that (roughly), the
same change in value always means that the brightness changed by the same
percentage. The bottom end of the curve will not be a true log function
so that we don't amplify the noise too much in very dark areas.

(2) Digitize with a, lets say, 12 bit ADC that is well synced to the
video. and feed that into a FPGA that does the following steps.

(3) Only clock samples through while we are in the scan area of the video
image.

(4) Implement a IIR bandpass filter in the column direction with about 3
memories.

(5) Using, lets say, 256*3 memory locations sellected according to the
column number, implement an IIR filter in the row direction.

(6) Perhaps snip off the LSBs and decimate the data a bit to reduce the
need for the next bit of memory.

(7) Arrange a chunk of memory such that we get a, lets say, 12 bit value
for the previous scan at this location and then overwrite it with a new 12
bit value.

(8) Impement the following function between the read and write of the
memory from step (7):

if abs(New - Old) > BackLash
then Y = New
else Y = Old

(9) Make a CRC from, lets say, the top 8 bits of the results from 8.


My reasoning is like this:

A reflective object reflects a constant percentage of the light falling
on it regardless of the absolute brightness. This is way I take the
log(x).

The bandpass filter in the row direction implements a homomorphic
amplitude compression. This mostly removes the effects of over all
dimming and brightening of the scene. Cutting out the high frequencies
removes much of the noise and jitter and rejects small objects such as
flies in the scene.

The bandpas filter in the column direction removes the variations in
brightness from left to right and again rejects small objects.

After the filtering, the signal, more or less, contains only information
about the locations of the objects in the scene plus some remaining noise.

If the backlash in step (8) is much more than this noise, the Y=Old case
will happen every time unless something in the scene changes.

A CRC can easily be arranged so that it has its repeat values widely
spaced on the scene.

 

[Luhan]

If you reduce the number of values and the number of bits in each sample,
you reduce the odds of a change of one bit. If backlash is built into the
digitizer, a further reduction in the odds can be had.

The digitizer would have to remember the previous data at exactly that
location.

If we are looking

for a change in the picture that is large enough, the CRC will work.

No, all of the CRC's I have seen react to single bit changes.

The way I would attack doing it with a CRC (assuming I had to) would be to
do the following.

(1) Run the video signal into a "log(x)" circuit so that (roughly), the
same change in value always means that the brightness changed by the same
percentage. The bottom end of the curve will not be a true log function
so that we don't amplify the noise too much in very dark areas.

I prefer my one resistor and one capacitor.

(2) Digitize with a, lets say, 12 bit ADC that is well synced to the
video. and feed that into a FPGA that does the following steps.

The PIC has 10 bits, using 12 contradicts your comment above about
reducing the number of bits. I use 8 bits for 'easy handling'.

(3) Only clock samples through while we are in the scan area of the video
image.

Check the website, thats always done.

(4) Implement a IIR bandpass filter in the column direction with about 3
memories.

(5) Using, lets say, 256*3 memory locations sellected according to the
column number, implement an IIR filter in the row direction.

The PIC has only about 100 memory locations.

(6) Perhaps snip off the LSBs and decimate the data a bit to reduce the
need for the next bit of memory.

Conflicts with your #2.

(7) Arrange a chunk of memory such that we get a, lets say, 12 bit value
for the previous scan at this location and then overwrite it with a new 12
bit value.

(8) Impement the following function between the read and write of the
memory from step (7):

if abs(New - Old) > BackLash
then Y = New
else Y = Old

(9) Make a CRC from, lets say, the top 8 bits of the results from 8.


My reasoning is like this:

A reflective object reflects a constant percentage of the light falling
on it regardless of the absolute brightness. This is way I take the
log(x).
Yes.


The bandpass filter in the row direction implements a homomorphic
amplitude compression. This mostly removes the effects of over all
dimming and brightening of the scene. Cutting out the high frequencies
removes much of the noise and jitter and rejects small objects such as
flies in the scene.

The bandpas filter in the column direction removes the variations in
brightness from left to right and again rejects small objects.

After the filtering, the signal, more or less, contains only information
about the locations of the objects in the scene plus some remaining noise.

If the backlash in step (8) is much more than this noise, the Y=Old case
will happen every time unless something in the scene changes.

A CRC can easily be arranged so that it has its repeat values widely
spaced on the scene.

Build it and show us the design. Let us all know how it works. You
are going in the opposite direction from my design - better
recoginition with much greater complexity.

My design is a compromise on recognition with greatly reduced
complexity.

You may have some very good ideas here on an implementation using maybe
a PC to do the processing. This may have its uses depending on design
constraints.

Good luck,
Luhan

 

[Ken Smith]

Ken Smith wrote: [....]

If you reduce the number of values and the number of bits in each sample,
you reduce the odds of a change of one bit. If backlash is built into the
digitizer, a further reduction in the odds can be had.

The digitizer would have to remember the previous data at exactly that
location.

No, it would not.

I think you will agree that, if the digitizer was lets say 1 bit and the
backlash was greater than the video signal, the output would always be either
high or low depending on which way it started.

I think you would also agree that if the entire video frame was reduced to
a single pixel, a low resolution multibit digitizer would produce the same
result assuming the overall lighting did not change.

With some filtering before it, the one bit digitizer could be replaced
with a window comparitor. When you go to multiple pixels, the required
backlash circuit would become a majority logic circuit in the simple case.

If we are looking

No, all of the CRC's I have seen react to single bit changes.

.... and if the change in picture does not cause a change on the input to
the CRC, the CRC's output does not change. So all that is required is a
circuit that doesn't change the digital input if the picture doesn't have
some huge change in it.

I prefer my one resistor and one capacitor.

To each his own, I guess but it sounds quite primative to me. With my
version, changes in overall brightness don't produce a changed output.

The PIC has 10 bits, using 12 contradicts your comment above about
reducing the number of bits. I use 8 bits for 'easy handling'.

This was about "using a CRC" so the details of the hardware doesn't matter
it is just getting it to involve a CRC that was the goal.

Check the website, thats always done.

It still needs to be stated for the description to be complete.

The PIC has only about 100 memory locations.

Then don't use a PIC!

Conflicts with your #2.

How does that conflict. I sure don't see any way that it does.

Build it and show us the design.

Why? Do you think it won't work or that it doesn't use a CRC?

Let us all know how it works. You
are going in the opposite direction from my design - better
recoginition with much greater complexity.

My design is a compromise on recognition with greatly reduced
complexity.

You may have some very good ideas here on an implementation using maybe
a PC to do the processing. This may have its uses depending on design
constraints.

No, like I suggested, an FPGA is the way to go. All of the logic will fit
into a not very large one. The memory pushes you up in size a bit but not
all that much these days. The amount of electronics to make the FPGA go
would not be much.

 

[Luhan]

Ken Smith wrote: [....]

If you reduce the number of values and the number of bits in each sample,
you reduce the odds of a change of one bit. If backlash is built into the
digitizer, a further reduction in the odds can be had.

The digitizer would have to remember the previous data at exactly that
location.

No, it would not.

I think you will agree that, if the digitizer was lets say 1 bit and the
backlash was greater than the video signal, the output would always be either
high or low depending on which way it started.

I think you would also agree that if the entire video frame was reduced to
a single pixel, a low resolution multibit digitizer would produce the same
result assuming the overall lighting did not change.

With some filtering before it, the one bit digitizer could be replaced
with a window comparitor. When you go to multiple pixels, the required
backlash circuit would become a majority logic circuit in the simple case.

If we are looking

No, all of the CRC's I have seen react to single bit changes.

... and if the change in picture does not cause a change on the input to
the CRC, the CRC's output does not change. So all that is required is a
circuit that doesn't change the digital input if the picture doesn't have
some huge change in it.

I prefer my one resistor and one capacitor.

To each his own, I guess but it sounds quite primative to me. With my
version, changes in overall brightness don't produce a changed output.

The PIC has 10 bits, using 12 contradicts your comment above about
reducing the number of bits. I use 8 bits for 'easy handling'.

This was about "using a CRC" so the details of the hardware doesn't matter
it is just getting it to involve a CRC that was the goal.

Check the website, thats always done.

It still needs to be stated for the description to be complete.

The PIC has only about 100 memory locations.

Then don't use a PIC!

Conflicts with your #2.

How does that conflict. I sure don't see any way that it does.

Build it and show us the design.

Why? Do you think it won't work or that it doesn't use a CRC?

Let us all know how it works. You
are going in the opposite direction from my design - better
recoginition with much greater complexity.

My design is a compromise on recognition with greatly reduced
complexity.

You may have some very good ideas here on an implementation using maybe
a PC to do the processing. This may have its uses depending on design
constraints.

No, like I suggested, an FPGA is the way to go. All of the logic will fit
into a not very large one. The memory pushes you up in size a bit but not
all that much these days. The amount of electronics to make the FPGA go
would not be much.

I'll leave it to others decide if what you propose makes sense.

Luhan

 

[Luhan]

Ken Smith wrote: [....]

If you reduce the number of values and the number of bits in each sample,
you reduce the odds of a change of one bit. If backlash is built into the
digitizer, a further reduction in the odds can be had.

The digitizer would have to remember the previous data at exactly that
location.

No, it would not.

I think you will agree that, if the digitizer was lets say 1 bit and the
backlash was greater than the video signal, the output would always be either
high or low depending on which way it started.

I think you would also agree that if the entire video frame was reduced to
a single pixel, a low resolution multibit digitizer would produce the same
result assuming the overall lighting did not change.

With some filtering before it, the one bit digitizer could be replaced
with a window comparitor. When you go to multiple pixels, the required
backlash circuit would become a majority logic circuit in the simple case.

If we are looking

No, all of the CRC's I have seen react to single bit changes.

... and if the change in picture does not cause a change on the input to
the CRC, the CRC's output does not change. So all that is required is a
circuit that doesn't change the digital input if the picture doesn't have
some huge change in it.

I prefer my one resistor and one capacitor.

To each his own, I guess but it sounds quite primative to me. With my
version, changes in overall brightness don't produce a changed output.

The PIC has 10 bits, using 12 contradicts your comment above about
reducing the number of bits. I use 8 bits for 'easy handling'.

This was about "using a CRC" so the details of the hardware doesn't matter
it is just getting it to involve a CRC that was the goal.

Check the website, thats always done.

It still needs to be stated for the description to be complete.

The PIC has only about 100 memory locations.

Then don't use a PIC!

Conflicts with your #2.

How does that conflict. I sure don't see any way that it does.

Build it and show us the design.

Why? Do you think it won't work or that it doesn't use a CRC?

Let us all know how it works. You
are going in the opposite direction from my design - better
recoginition with much greater complexity.

My design is a compromise on recognition with greatly reduced
complexity.

You may have some very good ideas here on an implementation using maybe
a PC to do the processing. This may have its uses depending on design
constraints.

No, like I suggested, an FPGA is the way to go. All of the logic will fit
into a not very large one. The memory pushes you up in size a bit but not
all that much these days. The amount of electronics to make the FPGA go
would not be much.

I leave it for others to decide if what you say makes sense.

Luhan

 

[Mochuelo]

Ken Smith wrote:

I prefer my one resistor and one capacitor.

Your one resistor and one capacitor have nothing to do with this point
(1). They have to do with (5). They do a spatial low-pass filtering,
in the horizontal direction.

How do you filter vertically the image? How do you anti-alias in that
direction? You said you are taking 8x8 samples, but an NTSC frame has
480 viewable lines. 480/8=60. What do you do with the other 59 lines
per group? The fact that your ADC does not take two samples from the
same line does not change this reasoning. Vertically speaking, you are
only looking at 1.7% of the image, and ignoring the rest. You have
98.3% odds of not detecting a change, even if it is huge. In the case
of PAL, the situation is worse.

The PIC has 10 bits, using 12 contradicts your comment above about
reducing the number of bits.

No, it doesn't contradict anything. His bit reduction was in (9).

I use 8 bits for 'easy handling'.

Is 16-bit algebra with 8-bit words difficult for you, taking into
account that you don't even have to multiply or divide?

The PIC has only about 100 memory locations.

No way. The PIC16F819 that you are using has 256 RAM bytes. You have
space for _four_ 64-byte frame buffers, in case you wanted to use
them. You were using 8-bit algebra, right?

Vertical spatial filtering is memory consuming but provides clear
benefits to any scheme that uses it --be it yours or one using CRCs.
The choice of including it is totally independent on the choice of the
change detection mechanism. Since we are trying to compare your scheme
with one using CRCs, the choice of including or not including vertical
spatial filtering has to be the same for both. Your scheme does not
use it, so disregard the complexity of this section.

Conflicts with your #2.
??

Build it and show us the design.

That sounds like an order.

Let us all know how it works.

Regarding your scheme, you just said "it works." I've heard those two
words from so many people, meaning so many different things , that
I don't know why I should believe you, especially after having seen
how easily you write strong statements --positive and negative.


By the way, strictly speaking, this thread is not about _motion_
detection. None of the ideas proposed here can tell whether something
that has been detected is just a change in luminosity, a movement, or
both. So, all this is just about _change_ detection. Motion detection
is much more complex.

 

[Luhan]

No way. The PIC16F819 that you are using has 256 RAM bytes. You have
space for _four_ 64-byte frame buffers, in case you wanted to use
them. You were using 8-bit algebra, right?

Yea, but they are in memory banks. Resolving down to a single 8 bit
value has implications for units with more cameras, or doing various
time-dimention detection schemes, to say nothing about being just plain
nifty.

Vertical spatial filtering is memory consuming but provides clear
benefits to any scheme that uses it --be it yours or one using CRCs.
The choice of including it is totally independent on the choice of the
change detection mechanism. Since we are trying to compare your scheme
with one using CRCs, the choice of including or not including vertical
spatial filtering has to be the same for both. Your scheme does not
use it, so disregard the complexity of this section


That sounds like an order.

Hot air is not currently in short supply here in Arizon Sorry, I've
had just toooo much work experience with 'engineers' who talk a good
line, but fail at producing real, working designs. Also, the fact that
a 'better' scheme can be achieved using a lots more parts, more time,
and even totally different hardware is not suprising, but of little
interest to me in this application.

Regarding your scheme, you just said "it works." I've heard those two
words from so many people, meaning so many different things , that
I don't know why I should believe you, especially after having seen
how easily you write strong statements --positive and negative.

Well, it means it works for the desired application. In this case,
mine. So if it works good enough for me, thats it.

By the way, strictly speaking, this thread is not about _motion_
detection. None of the ideas proposed here can tell whether something
that has been detected is just a change in luminosity, a movement, or
both. So, all this is just about _change_ detection. Motion detection
is much more complex.

The fact that it responds to luminosity is not relevent in my
application. False positives just happen to switch cameras, not a
problem. The unit does, however, seem to not miss objects moving into
the video frame.

Q.E.D.

Luhan

 

[Ken Smith]

Vertical spatial filtering is memory consuming but provides clear
benefits to any scheme that uses it

I think even a very crude spatial filter that doesn't use a lot of memory
for the vertical part would be helpful. A notch filter at the vertical
sweep rate and perhaps a harmonic or two would remove overall trends in
the frame. This would leave a few more bits for the stuff we care about.

By the way, strictly speaking, this thread is not about _motion_
detection. None of the ideas proposed here can tell whether something
that has been detected is just a change in luminosity,

The compression in my method removes an overall change in luminosity. By
taking the log() and then high passing, you remove the effect of
multiplying the input by a constant.

 

[Mochuelo]

Yea, but they are in memory banks.

This is one of those moments that I would like to have here, reading
us, some of those PIC-minded persons that say that PICs are as good as
other MCUs and that they don't give any problems. At least you just
admitted you are having problems.

Step by step. Let's not get lost.

Your MCU:
Microchip PIC16F819
----------------------------
1.95 GBP (qty 1) @ Farnell
4.03 USD (qty 1) @ DigiKey
3584 bytes flash
256 bytes RAM + 1 register.
Memory is divided in banks
No analog comparator
35 instructions
No hardware multiplier
ADC: 5 x 10-bit

A cheaper and better option:
Atmel ATmega48
----------------------------
1.40 GBP (qty 1) @ Farnell
2.58 USD (qty 1) @ DigiKey
4098 bytes flash
256 bytes RAM + 32 registers.
Linear memory map
With analog comparator
131 instructions
2-cycle hardware multiplier
ADC: 8 x 10-bit

See any difference?

The analog comparator in the ATmega would save you one external
comparator. The 131 vs. 35 instructions would mean shorter code, and
the capability to do more things. Dividing 256 bytes into banks is
something from the cave times. We are in 2006!

Hot air is not currently in short supply here in Arizon Sorry, I've
had just toooo much work experience with 'engineers' who talk a good
line, but fail at producing real, working designs.

You may have a loooong experience, but you just gave me a good example
of a real...ly suboptimal design.
Even a _32-bit_ ARM7 LPC2101 is cheaper (3.15 USD (qty 1) @ DigiKey)
than your PIC!

Also, the fact that
a 'better' scheme can be achieved using a lots more parts, more time,
and even totally different hardware is not suprising, but of little
interest to me in this application.

Ok, let's forget about checker boards and CRCs. We don't need them, to
beat your scheme.

Take your hardware. Exactly as it is. Take your wonderful PIC. Let's
assume exactly the same 8x8 sampling matrix. Change your software to
do this:

Reserve 64 bytes of RAM for a frame buffer (you still spare 192 bytes.
The code you published needs much less than 192 bytes of RAM).

At the beginning of each frame:
- Reset flag_change.

For each pixel in your matrix:
- Read the 10-bit sample from the ADC.
- Use it to compute the average value of the current frame.
- Subtract from the sample the average value of the previous frame,
for which you have the exact value from the very first pixel. This way
you don't need a second frame buffer.
- Keep the 8 most significant bits (it was your choice to work with
8-bit algebra).
- Subtract from it the corresponding value in the frame buffer,
compute the absolute value, and compare with a threshold. If smaller,
do nothing. If larger, set flag_change, and update the frame buffer
with the 8-bit value.

At the end of each frame:
- Compare the average value of the current frame with the average
value of the previous frame. If the difference is larger, in absolute
value, than a certain threshold, reset flag_change.
- Check flag_change. If true, decide that there has been some change
in your image, and switch cameras. Otherwise, do not switch cameras
(unless a timer says it is time to do it).


No checker boards. No CRCs. This scheme detects many more cases of
change than yours, yet easily avoids noise. It does not miss neither
the diagonal movements that your scheme misses, nor many other
changes. It fits in your PIC, and the conceptual complexity is lower.

Now, change the PIC for the ATmega, and you'll save money and parts
(one comparator).

Paraphrasing your text, it turns out that "a better scheme can be
achieved using less parts, less conceptual complexity, and less
money."


H.L.C.