Checking two similar images for significant change.

Hi, this is a toughy.  I am quite prepared to up the points for this one at any time.

Right we have a webcam monitoring a security gate.  I would like to reduce the amount of image data being sent.  The solution I see as being optimal is as follows.

We would only like to transmit an image to the security workstation clients if there is a significant change in image detail, ie a truck parks at a gate or person(s) walk past.

This sort of coding is just way out of my depth, so I am asking for help.

The only technique I can think of is an edge-detection algorithimn that produces, say a monochrome map of all the sharp colour edges in the image and then only transmit it if the monochrome count is significantly different.

I don't know how to write an edge detection algorithim.  Maybe if I convert it to 8-bit achromatic will help, but in general I feel a little overwhelmed.

Thanks in advance.

aho.
aho1Asked:
Who is Participating?
 
leesssConnect With a Mentor Commented:
aho1

The gradient matrix is called Sobel matrix.  

It IS an edge detection algorithm, which works really well.  This is what you have been asking for so I dig into my book and found it for you.

This matrix is called gradient because for a given pixel it uses the derivatives to comput how fast or slow the intensity changes for surrounding pixels.

It is good because most other edge detection method introduces noise where as this one reduces noise.

The workings behind it is too long to explain it here but if you read the book you will see.

Try the matrix and this one is simple (the theroy behind it is translated/reduced into 2 simple Gx and Gy algorithms).

If you don't want to use Sobel (I think it is your best choice for edge detection), you can use others but they do NOT give you a binary image, they give you edge enhanced image (meaning you still see the background with edge enhanced):

Roberts

1  0
0 -1

0  1
-1 0


or Prewitt

-1 -1 -1
 0  0  0
 1  1  1

-1 0 1
-1 0 1
-1 0 1


mark2150

The matrix you give is a highpass sharpening filter.  We may or may not want to use it as an edge detection matrix because:

(1)  The sum of the coefficeints is o.  Thus when the mask (matrix) is over an area  of SLOWLY varying gray level, the output of the mask is zero or very small.  

(2)  This mask (filter) also eliminates the zero-frequency term which reduces the average gray-level value in the image to zero, reducing significantly the global contrast of the image.

The resulting image is also not a binary image.
0
 
matthewmayerCommented:
this may be over-simple, but, assuming the camera is fixed, the image shouldn't change much usually. Why not loop through all the pixels in the two images and compare them. If there are more than say 5% different pixels then use the picture. Alternatively why not have a motion sensor to trigger the camera.
0
 
mark2150Commented:
There are hardware solutions to this. Better and easier than tying up CPU resource. You're still going to have to transmit the frame to evalute it.

M
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
leesssCommented:
Edge detection algorithm is very slow, it is used to recognizing objects what a robot sees and matches that with defined objects in its system...

Also for police face match.

With frame difference, it is probably faster.  You can send a whole frame for evaulation or you can send the difference (mpeg/jpeg).

I suggest you use the latter.

It is too long to explain the pros and cons for each method (I studied image processing for a few years).

What you need is a book on image processing with sample code so you don't have to write your own.  I don't have any book titles.  Just go to a bit book store with lots of computer books.  Try "Visual C++ 6 Power Toolkit".  But it may not have what you want.

Also, for speed, you better use C/C++ for that.
0
 
leesssCommented:
Just keep in mind that with each frame taken by the camera, even if nothing changes in the images, the value of each corresponding pixel in both images may be different (a small difference).

This is because of light intensity (lots of different lights) may change, and the hardware that captures the image.
0
 
aho1Author Commented:
CPU usage will not be a problem, the reason I suggested edge detection is because it is independant of change of light/camera angle.  By working on a local grey-scale image, the CPU usage chould be reduced substatially.

I did manage to find some image processing code, what I need to find out an edge detection matrix.  I have found some that detect vertical/horizontal/diagonal edges, but not all edges.  Anyone with any ideas will do.

aho.
0
 
mark2150Commented:
Apply all three matrix at the same time!

Basically you're looking at calculating the delta between a pixel and it's adjacent neighbors. If you multiply the center pixel by eight (a fast, three shift operation in ASM) and then subtract the eight adjacent pixels. If the field is evenly lit (all pixels equal), you'll get a zero - no edge. If the ABS() of the sum is large, then you've got an edge. If you only look at the pixels above/below or left/right then you'll have directional sensitivity.

Edge detection *IS* sensitive to lighting changes. Look at an image of a face illuminated from the top, bottom, each side. The resulting edge map is radically different as you're finding *intensity* edges and not *object* edges. Object edge detection is a hugely complex task and you not only have to detect intensity 'edges' but you also need intensity contour following with closure detection and broken line connectivity - which are a major task to compute!

To compare two images simply subtract them. If the images are relatively unchanged the ABS() of the result will be small. If the sum of all the pixels after subtraction is large, then you've had a significant change in the image.

If you're comparing samples taken at reasonable intervals (say every minute) and keep the last sample as a reference then sun shadows and other slow changes will be below the threshold, but rapid changes (a person entering the field) will trigger the result. Problem is that you have to empirically "tune" the threshold for any given scene. You also can't use panning or movable cameras.

I've got a DOS based image processor on my web page that you can tinker with if you want. Visit www.cyberchute.com/rvbus/madmark

Leesss, Where did you study image processing? Have you written any apps I might have seen? I studied it at Northrop years back for automated manufacturing and weapons development. I also developed a series of image processing systems for jails and sheriff's offices.

M

0
 
leesssCommented:
OK I found my technical book "Digital Image Processing" by Rafael C. Gonzalez / Richard E. Woods, Addison-Wesley

It has everything you need (I think anyway) but no code, just theories, including edge detection that mark2150 mentioned.

Mark2150, what a fun job you have!

I studied it in U of Alberta.  I wrote a simple program on both edge detection and frame difference.  But my master thesis was on image warping (morphing) and I didn't have time to write a real app.  I also did some teleconferencing stuff (an image compression algo. that my prof. developed).  After that I didn't work in image processing fields which I still like to.
0
 
leesssCommented:
using gradient method (from the above mentioned book)

To compute new z5 (see below matrix):

new pixel value = abs(Gx) + abs(Gy)

Gx = (z7 + 2z8 + z9) - (z1 + 2z2 + z3)
Gy = (z3 + 2z6 + z9) - (z1 + 2z4 + z7)

z = orginal pixel values

in matrix form:

z1 z2 z3
z4 z5 z6
z7 z8 z9

Gx in matrix form:

-1 -2 -1
 0  0  0
 1  2  1

Gy in matrix form:

-1  0  1
-2  0  2
-1  0  1
0
 
leesssCommented:
I still don't think edge detection is a good method but it is up to you.

To detect lines (see if these are the matrix that you had):

horizontal

-1 -1 -1
 2  2  2
-1 -1 -1

+ 45 degrees

-1 -1  2
-1  2 -1
 2 -1 -1

vertical:

-1  2 -1
-1  2 -1
-1  2 -1

- 45 degrees

 2 -1 -1
-1  2 -1
-1 -1  2

0
 
aho1Author Commented:
leesss,

Are you suggesting that gradient detection is better.  You also suggest that edge detection is no good.  sigh.  It appears that I have been left behind in image processing, I haven't touched it since 1995.  We didn't get a textbook at uni for that subject, just hand written class notes (if you've ever seen my hand writing you'll know why I am asking rather than reading my artwork).

The edge matrices work well (thanks), but I will have to define regions in the bitmap (it is a two way road with boom gates).  But that isn't so bad.  I have just about all the info I need, so I thought that I might summarise this disscussion.

The possible solutions I see that could increase efficiency of transmissions is as follows.

1. Edge/Gradient matrix methods and transmitting the clean image if the subtractions are 'significantly' different.

2. Image subtraction (mpeg), but I am unsure how that would work if you are only sending one frame at a time.

3. Motion sensors, is perfectly valid solution.  It is just that our sparky's (electricians) are just about booked out for the next few months.

4. Heat sensory equipment, reading a thermal image and transmitting a new image every time the coloured pixel count increases/decreases significantly.  A little more costly, but for that expense we might as well put a 100MB hub at the security gate.  That would reslove lots of problems :-).

aho.
0
 
mark2150Commented:
Yep. This is a problem that's crying for a little bit of hardware out at the far end. There are security camera controllers that automatically scan multiple cameras and will pop up the one with a change.

You can also get a RS-170 to Fiber converter that will take standard video signals and convert it to something you can shove thru a fiber. You have the same box at the other end and you can send plenty fast data over the fiber.

If you want a non-directional edge detection matrix you need:

-1  -1  -1
-1   8  -1
-1  -1  -1

You can also use this matrix as a sharpening filter...

M
0
 
mark2150Commented:
Now you see the items you're flagging as bugs are actually *features*! :-)

Yes, the sum of the coefficients is zero and yes, when the field is uniform then there is little or no output. Not too many edges in a uniform field, eh?

Yes, the average grey is reduced to zero. The contrast is *shot*, but you're not LOOKING for contrast, you're looking for EDGES! You should always use a pair (or sometimes *THREE* image matrix's) so you can have the reference image *and* the edge (or otherwise convolved image).

The resulting image is not a binary image - Quite true and if it were you'ld lose the added information of the *strength* of the edge. The relative intensity of the edge is shown by the level of the output matrix. Strong edges are shown as bright portions, weak as dim. You can then shove the result thru a threshold filter if you want/need a binary image. You can also *scale* the image up for normalization of the edges.

leesss/aho1, visit my page and download the image processor there. It's pretty cool and comes with several sample images you can tinker with. The edge detection, threshold, scaling, biasing and sharpening filters are all there - written in *asm*. I've even done anti-aliasing and halftone generation but they require special hardware that is no longer in production to see the results from.

You'll be able to understand what we're talking about here much better with a usable testbed to see the effects. For instance take the SCALE1 image and run it thru a BIAS (subtractor) of 8 and a multiplier of 300. Then run an edge detector on it. Compare the results to what the edge detector does without prescaling or multiplying. Look at the PCBOARD image and do the same thing. Fiddle, see what does what to what.

We were using an image processing language based on these core .ASM routines with dBase-III to generate highly complex and detailed arrest reports and other forms for the local cops - back *before* windows 3.1 was released!

M
0
 
aho1Author Commented:
leesss,

I might as well award you the points (sorry Mark2150) so if you answer the question I'll hand them to you and close off this question.  I seem to have all that I need to develop this application.

aho.
0
 
mark2150Commented:
You don't have to wait for Leesss to answer. Simply select the "Accept Comment as Answer" box next to the comment that you liked best and the points will be his.

As I said, be sure to stop by and get the image processor. It's pretty cool and I can send some source if you need it.

M
0
 
leesssCommented:
aho1,

To be fair why don't you make 2 new questions just for us and we will claim them:

I suggest that mark2150 and I split the points because we are both right (using Sobel or sharpening matrix is a choice, with the latter having the flexibility to manipulate the image more, but then if you want to manipulate the image you can also use Roberts or Prewitt's matrices and do the thresthod as suggested by mark2150) and we both spent the time to do this.

After saying that I still think the frame difference could be a better solution (after all you are interested in what changes in the images and therefore telling you if something moved (etc.) in the frame.  For the method you use to detect that change you really don't care if it is edge detection or what but the one that, I think, give you speed and accuracy is important, unless you want to see the edges.)


0
 
mark2150Commented:
Don't worry about the points. I've got plenty.

Let me know if you have any luck with my DOS image processor (it'll run in a DOS full screen window under windows just fine...)

M
0
 
aho1Author Commented:
Thanks for all your help guys.  Should we decide that network performance is too slow I now have perefectly feasible solution.   It cerntainly has been fun digging into some of my old DI stuff.
0
All Courses

From novice to tech pro — start learning today.