Without loss of generality, let *X* = {*x*_{1},*x*_{2},…*,x _{l}*} and

Since we independently sample *m* frames from each sequence, the probability that *Z _{i} =* 1 for any

To simplify the notation, let *ρ*(*X,Y*) *=* vvs(*X,Y*;*ε*) and (*X,Y*) = vss* _{b}*(, ,

(28.19) |

To find an upper bound for *P _{err}*(

A sufficient condition for *P _{err}*(

For each term inside the summation on the right hand side of Equation (28.12), *d*(*x, y*) must be smaller than or equal to *ε.* If *d*(*x, y*) *≤ ε*, our assumption implies that both *x* and *y* must be in the same cluster *C* belonging to both [*X*]* _{ε}* and [

(28.20) |

Based on the definition of a Voronoi Cell, it is easy to see that *V _{X}*(

Finally, we note that [*X*]* _{ε}*⋂[

Without loss of generality, we assume that *x*_{1} is at the origin with all zeros, and *x*_{2} has *k* 1's in the rightmost positions. Clearly, *d*(*x*_{1}*,x*_{2}) *= k.* Throughout this proof, when we mention a particular sequence *Y* ∈ Γ, we adopt the convention that *Y =* {*y*_{1}, *y*_{2}} with *d*(*x*_{1},*y*_{1}) *≤ ε* and *d*(*x*_{2}*,y*_{2}) *≤ε.*

We first divide the region *A* into two partitions based on the proximity to the frames in *X*:

*A*_{1} := {*s* ∈ *A*: *g _{X}*(

We adopt the convention that if there are multiple frames in a video Z that are equidistant to a random vector *s, g _{Z}*(

Thus, *R* follows a binomial distribution of parameters *k* and 1/2. In this proof, we show the following relationship between *A*_{2} and *R*:

(28.21) |

With an almost identical argument, we can show the following:

(28.22) |

Since Vol(*A*) = Vol(*A*_{1}) + Vol(*A*_{2}), the desired result follows.

To prove Equation (28.21), we first show if *k/*2*≤R<k*/2+*ε*, then *s *∈ *A*_{2}. Assuming the definitions for *A* and *A*_{2}, we need to show two things: (1) *g _{X}*(

| | |

| | |

| 2 |

which implies that *g _{X}*(

| | |

| 2( |

*g _{Y}*(

Now we show the other direction: if *s ∈ A*_{2}, then *k/*2≤ *R<k*/2+ *ε.* Since *s ∈* *A*_{2}, we have *g _{X}*(

*L-ε<L + k*-2*R + ε* ⇓ *R<k/*2 *+ ε*

This completes the proof for Equation (28.21). The proof of Equation (28.22) follows the same argument with the roles of *x*_{1} and *x*_{2} reversed. Combining the two equations, we obtain the desired result.

We prove the case for video *X* and the proof is identical for *Y.* Since *s* ∈ *G*(*X*,*Y*;*ε*), we have *d*(*g _{X}*(

(28.23) |

*s* ∈ *G*(*X,Y*;*ε*) also implies that there exists *y* ∈ *Y* such that *d*(*y*, *g _{Y}* (

s),s) | | s),s) |

| s)) | |

| 2 |

Handbook of Video Databases: Design and Applications (Internet and Communications)

ISBN: 084937006X

EAN: 2147483647

EAN: 2147483647

Year: 2003

Pages: 393

Pages: 393

- Chapter II Information Search on the Internet: A Causal Model
- Chapter III Two Models of Online Patronage: Why Do Consumers Shop on the Internet?
- Chapter IV How Consumers Think About Interactive Aspects of Web Advertising
- Chapter XII Web Design and E-Commerce
- Chapter XIII Shopping Agent Web Sites: A Comparative Shopping Environment

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net