1

I have a heuristic in mind that should allow me to "score" data based on "novelty" that I would like to work in real-ish time.

In this case, I mean novelty in the sense that the data source is something like a video and I want to know when there is a statistically significant change in the stream.

For example, consider a video of a scene where the camera is turning to the right. As long as the velocity of the turn is constant, the data should be considered to be not-novel, or uninteresting. If a bird flies past in the opposite direction, then the parts of frame where the bird is flying past would be considered novel, and would be assigned a high score. If the scores were assigned per 16x16 block of pixels, when the bird reached center frame it might look like:

0 0 0 0 0 0 0
0 0 0 3 1 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0

As I understand it, there are algorithms that can do part of this for video compression, block Motion compensation and Global motion compensation, but the result of these algorithms seems to be a difference image that I would then need to digest further (average of differences), when all I want is a simple hash. That is, given the above 7x4 matrix:

0x00003200

The very first frame of the video, having no history, would be maximally novel:

0xFFFFFFFF

The cool thing would be to assign a score to the whole frame, and then for interesting frames break that up into smaller blocks, and for the interesting blocks another set, and so on, like a quadtree.

So to summarise, is there a short-cut to get from a series of frames to a single hash value for each frame, based on the most recent frames? Or is there a better way to do this that I'm not aware of?

Further refinements

Reusing the example matrix above, where there is a 3 the sample is more novel because the block where the bird is in this frame didn't have a bird there before, whereas the samples with a 1 are still somewhat novel because there is no longer a bird there, but not as much because that block has returned to what would be expected in the background.

This leads me to believe that there should be some kind of accumulating effect in the solution, because more than the very last frame needs to be taken into account.

  • 2
    Would measuring the entropy be a sufficient proxy for novelty? – GlenH7 Feb 14 '14 at 17:57
  • Possibly, although that leads me to wonder about how white noise would be treated. If the stream is just totally random, ie incompressible in the usual sense, then my definition for novelty would fall apart. Taken as a whole, there would be nothing statistically significant about the stream, but sections of the frame could appear to be very "novel." – jzx Feb 14 '14 at 18:43
  • 1
    @jzx: In addition to having your hash be based on image elements, it could also be based on color distributions (or other statistical analysis). E.g., a bird moving across the frame is a moving blob of what is probably a relatively stable color distribution, whereas white noise would probably (if you picked the right statistical analysis) show up as being mostly unchanging. – Brian Feb 14 '14 at 19:09
  • 1
    Agreed - and that's a valid concern. My initial read of your question was that you were looking for a way to measure entropy from frame to frame. "Novelty" adds a discriminant that indicates the change provides value (or is "not noise") but you didn't provide a means to make that determination. – GlenH7 Feb 14 '14 at 19:09
1

I would proceed like this:

  1. Acquire the new frame
  2. Compare every pixel color with the same pixel, but from n previous frames
  3. Assign a "novelty index" to that pixel (for example, the quadratic mean of the differences from every past n frames, maybe weighted with the frame temporal difference)
  4. Count the number of pixel whose "novelty index" overcome a "novelty threshold"
  5. If that number is above a certain "overall novelty threshold", that frame is novel

You can adapt this to a recursive approach, so that you decompose your frame in 4 areas, and so on, apply the algorithm and then backtrack to the top frame.

N.B.: I'm not a computer scientist neither a mathematician, so that's probably not the best approach!

  • While not ideal, I think this is a good enough starting point. – jzx May 22 '14 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.