BRPI0721733A2

BRPI0721733A2 - mÉtodo e aparelho para definir um limite de detecÇço dada uma probabilidade falsa desejada

Info

Publication number: BRPI0721733A2
Application number: BRPI0721733-1A
Authority: BR
Inventors: Jun Tian; Jeffrey Adam Bloom; Peter Georg Baum
Original assignee: Thomson Licensing
Priority date: 2007-06-14
Filing date: 2007-06-14
Publication date: 2013-02-13
Also published as: CN101689290B; KR101383307B1; JP2010529810A; JP5238024B2; WO2008153526A1; US8315835B2; US20100121608A1; EP2165310A1; CN101689290A; EP2165310B1; KR20100018558A

Abstract

MÉTODO E APERLHO PARA DEFINIR UM LIMITE DE DETECÇçO DADA UMA PROBABILIDADE FALSA DESEJADA. Um método e aparelho são descritos para a determinação de um limite, incluindo a seleção de uma probabilidade de falso resultado desejada, e a seleção de um valor limite a partir de uma tabela de limites correspondente à probabilidade de falso resultado desejada. São também descritos um método e aparelho para determinar um limite correspondete a uma probabilidade de falso resultado desejada, incluindo o cálculo de uma probabilidade de falso resultado, o cálculo de um valor de diferença entre a probabilidade de falso resultado calculada e a probabilidade de falso resultado desejada, a comparação do valor de diferença com um primeiro valor predeterminado e a comparação do valor de diferença com um segundo valor predeterminado, quando um resultado da primeira etapa de comparação é positivo.

Description

"MÉTODO E APARELHO PARA DEFINIR UM LIMITE DE DETECÇÃO DADA UMA PROBABILIDADE FALSA DESEJADA"

CAMPO DA INVENÇÃO

A presente invenção refere-se à definição de um limite de detecção e, em especial à definição de um limite de detecção dada uma probabilidade de falso positivo desejada.

FUNDAMENTOS DA INVENÇÃO

É extremamente importante, em muitas aplicações de sinalização com marca d'á- gua que a probabilidade de falso positivo de um detector de marca d'água fique abaixo de um determinado valor. Um falso positivo ocorre quando o detector de marca d'água identifica incorretamente um trabalho não sinalizado com marca d'água como sinalizado com marca d'água. Um exemplo de um sistema no qual isso é importante é o uso de uma marca d'água em um conteúdo de vídeo a fim de indicar a um gravador ou aparelho de gravação que o material de vídeo não pode ser copiado. Quando um falso positivo ocorre durante uma gra- vação, o dispositivo de gravação que monitora essa marca d'água concluirá incorretamente que o conteúdo do vídeo não pode ser copiado e gravação será interrompida. Quando isso ocorre durante a gravação de uma cerimônia de casamento, o fabricante da câmera enfren- tará uma situação na qual os nubentes ficarão desolados. Quando isso acontece durante a transmissão televisiva de um programa popular, os fabricantes do gravador enfrentarão mui- tos clientes insatisfeitos. Assim, os fabricantes de gravador normalmente exigem que tal marca d'água de controle de cópia tenha uma probabilidade de falso positivo próxima à pro- babilidade da falha de um componente de hardware; na faixa dentre 1 erro em 109 detec- ções para 1 erro em 1012 detecções.

Para melhor entender o problema da probabilidade de falso positivo, considere a i- lustração da Figura 2a, que mostra duas distribuições. A distribuição à esquerda representa os valores de detecção que podem ser esperados quando um detector de marca d'água é aplicado a conteúdos que não contém marca d'água. A média dessa distribuição é zero e, na maioria das vezes, espera-se que possa chegar a próximo de zero. Esta é uma curva de probabilidade, para que a área sob a curva seja igual a 1,0. A distribuição à direita represen- ta os valores de detecção que podem ser esperados quando o detector é aplicado a um con- teúdo sinalizado com marca d'água. Neste caso, a média é M e o valor de detecção é ge- ralmente perto de Μ. A função de um limite é distinguir entre amostras destas duas distribui- ções. Considere o limite no ponto marcado T. Quando o valor de detecção excede T, pode- se concluir que o conteúdo vem da distribuição à direita. Quando o valor de detecção é infe- rior a T, pode-se concluir que o conteúdo vem da distribuição á esquerda. Como se pode observar a partir da Figura 2a, existem algumas amostras da distribuição à direita que estão abaixo do limite T. Essas são trabalhos marcados para os quais a detecção irá falhar, às vezes chamados de falsos negativos. De maneira similar, existem algumas amostras da distribuição à esquerda que excedem o limite. Estas são trabalhos não marcados que o de- tectar irá rotular conforme marcados. Estes são os falsos positivos.

A probabilidade de falso negativo pode ser aperfeiçoada ao reduzir o limite. Esta ação, no entanto, simultaneamente, irá aumentar a probabilidade de uma indicação de falso positivo. No exemplo apresentado, as duas distribuições se sobrepõem. Isso significa que um limite que elimina os erros não poderá ser selecionado. Em muitas aplicações de sinali- zação com marca d'água, o limite de detecção T é selecionado com base em uma exigência de probabilidade de falso positivo específica à aplicação. Deve-se notar que a probabilidade de falso positivo é independente do algoritmo embutido na marca d'água. Ela é simplesmen- te a área sob a curva à esquerda, que é maior que o limite T.

A Figura 2b mostra uma vista mais próxima da curva à esquerda nas proximidades do limite. A área sob a curva maior que o limite T é mostrada sombreada. Esta área repre- senta a probabilidade de falso positivo, a probabilidade de que uma marca d'água será de- tectada em um trabalho sem marcação. Dada a exigência de uma probabilidade de falso positivo, seria vantajoso se ter um

método e sistema para o estabelecimento de um limite mínimo que atenda à exigência da probabilidade de falso positivo.

Conforme usado no presente documento, "/" indica nomes alternativos para os componentes ou estruturas iguais ou semelhantes. Ou seja, uma "/" pode ser tomada no sentido de "ou", como usado no presente documento.

SUMÁRIO DA INVENÇÃO

A presente invenção resultou da tentativa de se resolver um problema no campo da sinalização com marca d'água e, em particular, no campo da sinalização digital com marca d'água de conteúdos de áudio e vídeo. Esta probabilidade de falso positivo é bem entendida por detectores que usam uma

medida de detecção de correlação normalizada. No entanto, em um esforço para aumentar a robustez da marca d'água, um número de pesquisadores propôs medidas de detecção que combinam múltiplas correlações normalizadas. Uma dessas medidas é a razão da maior correlação normalizada para a segunda maior quando um vetor extraído é comparado a múltiplos vetores de referência. Os presentes princípios se baseiam na análise da probabili- dade de falso positivo da medida de detecção de razão de correlação sob uma suposição razoável sobre a distribuição de trabalhos não sinalizados com marca d'água.

Os pesquisadores investigaram este problema quando a medida de detecção é uma correlação normalizada. (M.L. Miller e J.A. Bloom, "Computing the Probability of False Watermark Detection", Proceedinqs of the Third International Workshop on Information Hid- inq, pp. 146-158, 1999). Acredita-se que ninguém tenha trabalhado sobre o problema quan- do a medida de detecção é a razão de duas correlações normalizadas. Portanto, a presente invenção trata de um método e um sistema correspondente para configurar automaticamente o limite de detecção em um sistema de detecção de marca d'água quando a medida de detecção é a razão da maior correlação normalizada para a segunda maior correlação normalizada e uma probabilidade de falso positivo desejada é dada. Embora a presente invenção seja descrita em termos da determinação de um limite correspondente a uma probabilidade de falso positivo, esta não é assim limitada. O método e aparelho para a determinação de limites de acordo com a presente invenção podem ser usados para determinar um limite correspondente a qualquer probabilidade de falso resulta- do, por exemplo, uma probabilidade de falso negativo. Embora o método de determinação de limite de acordo com a presente invenção seja explicado em termos da detecção de mar- cas d'água, existem muitas outras áreas nas quais a determinação de limites é crítica^ como na área da imagiologia médica, do registro de áudio ou imagem, do reconhecimento de áu- dio ou imagem, do reconhecimento de padrões, e da detecção, identificação e classificação de objetos. Na área do reconhecimento de padrões, incluindo a análise de assinatura de radar e sonar, a determinação de limites no cenário "identificar amigo ou inimigo" é um e- xemplo de utilização extremamente crítica da presente invenção. No cenário "identificar a- migo ou inimigo", qualquer erro na identificação incorreta de amigo ou inimigo poderá ser mortal.

Um método e aparelho são descritos para a determinação de um limite, incluindo a seleção de uma probabilidade de falso resultado desejada e a seleção de um valor limite a partir de uma tabela de limites correspondente à probabilidade de um falso resultado dese- jada. São também descritos um método e aparelho para determinar um limite corresponden- te a uma probabilidade de falso resultado desejada, incluindo o cálculo de uma probabilida- de de falso resultado, o cálculo de um valor de diferença entre a probabilidade de falso re- sultado calculada e a probabilidade de falso resultado desejada, a comparação do valor de diferença para um primeiro valor predeterminado valor e a comparação do valor de diferença com um segundo valor predeterminado quando o resultado da primeira etapa de compara- ção é positivo.

BREVE DESCRIÇÃO DOS DESENHOS A presente invenção será melhor entendida a partir da descrição detalhada a seguir

quando lida em conjunto com os desenhos em anexo. Os desenhos incluem as seguintes figuras brevemente descritas abaixo, nas quais números similares nas figuras representam elementos similares:

A Figura 1a ilustra a interpretação geométrica de uma fórmula analítica em que m = 2.

A Figura 1b ilustra a interpretação geométrica de uma fórmula analítica em que m = 2. A Figura 1c mostra os resultados da comparação dos vetores sintéticos com as previsões utilizando a fórmula analítica.

A Figura 2a mostra duas distribuições - a probabilidade de valores de detecção pa- ra trabalhos marcados e não marcados.

A Figura 2b é uma vista mais próxima da distribuição de valores de detecção para

trabalhos não marcados ilustrados na Figura 1 na área do limite, T.

A Figura 3a é um fluxograma de uma modalidade do método de determinação de limite de acordo com a presente invenção.

A Figura 3b é um diagrama em blocos do aparelho ou módulo de determinação de limite da presente invenção.

A Figura 4a é um fluxograma de uma modalidade do método de determinação de limite da presente invenção.

A Figura 4b é um diagrama em blocos do aparelho ou módulo de determinação de

limite.

A Figura 5a é um fluxograma de uma modalidade alternativa do método de deter-

minação de limite da presente invenção.

A Figura 5b é um diagrama em blocos de uma modalidade alternativa do aparelho de determinação de limite da presente invenção.

DESCRIÇÃO DETALHADA DAS MODALIDADES PREFERIDAS Antes de o método e aparelho serem descritos, é necessário estabelecer uma base

matemática. Uma questão crítica para muitas aplicações de sinalização com marca d'água é a probabilidade de que o detector de marca d'água identifique incorretamente um trabalho não marcado como sinalizado com marca d'água. Esta probabilidade de falso positivo é bem entendida por detectores que usam uma medida de detecção de correlação normalizada. No entanto, em um esforço para aumentar a robustez da marca d'água, vários pesquisadores propuseram medidas de detecção que combinam múltiplas correlações normalizadas. Uma dessas medidas é a razão da maior correlação normalizada para a segunda maior quando um vetor extraído é comparado com múltiplos vetores de referência. Uma fórmula analítica para a probabilidade de falso positivo é derivada e validada com dados empíricos. A correla- ção tem um teorema que relaciona o processamento do domínio espacial e o processamen- to do domínio de freqüência através da Transformada de Fourier Discreta (DFT). Assim, as correlações podem ser realizadas nos domínios do tempo ou da freqüência. A correlação é utilizada no sentido de determinar o grau de similaridade entre conjuntos de dados

A sinalização com marca d'água digital é o processo de incorporação de uma men- sagem invisível em um trabalho digital (como um áudio sem costura, uma imagem estática, ou uma seqüência de imagens) com o objetivo de comunicar informações sobre esse traba- lho. As aplicações incluem uma comunicação de direito autoral, a autenticação do conteúdo, a dissuasão ou detecção de falsificação, um acompanhamento forense, ou um monitora- mento de difusão.

Os erros são inevitáveis, mesmo nos mais bem desenhados sistemas de sinaliza- ção com marca d'água. Um erro de falso positivo ocorre quando um detector de marca d'á- gua indica a presença de uma marca d'água em um trabalho não sinalizado com marca d'á- gua. Tal erro pode levar à prevenção equivocada de uma operação legítima ou a denúncia de um cliente inocente. Assim, a falsa probabilidade tornou-se uma questão crítica para mui- tas aplicações de sinalização com marca d'água. Esta probabilidade depende do algoritmo de detecção de marca d'água, a maneira na qual o detector é usado, e a distribuição de tra- balhos não sinalizados com marca d'água.

O problema de se analisar o comportamento da falsa detecção tem recebido pouca atenção na literatura relativa a marcas d'água. Um esquema de técnica anterior oferece um modelo para predizer a probabilidade de falso positivo nos métodos de sinalização com marca d'água baseados na correlação e mostra que um espectro não branco de uma marca d'água faz com que o conteúdo da imagem interfira na detecção da marca d'água. Outro esquema da técnica anterior inclui a probabilidade de falsa detecção em sua estrutura no sentido de discutir os sistemas de sinalização com marca d'água. Ainda, um outro esquema da técnica anterior apresenta um método preciso para calcular a probabilidade de falso posi- tivo ao utilizar um detector de correlação normalizada. Uma fórmula exata para a probabili- dade de falso positivo é provida sob a suposição de que os vetores extraídos de trabalhos não sinalizados com marca d'água sejam extraídos a partir de uma distribuição radialmente simétrica. Um outro esquema da técnica anterior ainda estuda a probabilidade de falso posi- tivo em exaustivas pesquisas geométricas. É mostrado que a imagem e a dependência de chave no detector de marca d'água resultam em uma diferente probabilidade de falso positi- vo para pesquisas geométricas.

Para muitas aplicações, um vetor extraído é comparado a um número de diferentes vetores de referência de marca d'água. Cada vetor de referência é associado a um símbolo de mensagem diferente. O símbolo de mensagem associado ao vetor de referência que tem a maior similaridade com o vetor extraído é relatado como o símbolo detectado. A certeza de detecção é o grau de similaridade. A medida de similaridade mais comum utilizado é a correlação normalizada. Ao usar a fórmula de um dos esquemas da técnica anterior, a exi- gência de probabilidade de falso positivo do aplicativo pode ser usada para definir um limite. Quando o valor de detecção excede o limite, o símbolo é relatado como presente, caso con- trário, o detector não relata nenhum símbolo.

Em um esforço para melhorar a robustez de tais técnicas, alguns pesquisadores propuseram medidas de segurança que combinam o maior valor de correlação com o se- gundo maior valor de correlação. Uma dessas abordagens considera a diferença entre es- ses dois valores como a segurança e outra considera a razão entre os dois valores como a segurança. Em ambos os casos, não existem análises de falsos positivos e, sem estas, não há como definir um limite e realizar uma comparação de robustez segura. Uma fórmula ana- lítica é obtida aqui para a probabilidade de falso positivo para a medida da razão de correla- ção e os dados empíricos para apoiar esta análise são apresentados.

A probabilidade de uma detecção de marca d'água falsa é determinada pelo dese- nho do detector de marca d'água e a distribuição do conteúdo não sinalizado com marca d'água processado pelo mesmo. O algoritmo incorporado não é relevante para computar essa probabilidade, pois se presume que nenhuma marca d'água tenha sido incorporada. Considere um detector de marca d'água de correlação normalizada específico, po-

rém típico. O trabalho de entrada é primeiro processado para extrair um vetor de caracterís- ticas n-dimensional, V. Exemplos de extração de marca d'água incluem várias combinações de transformadas de freqüência, média de blocos, forma espectral, branqueamento e sub- amostragem. Estes processos são destinados a aumentar a robustez, aumentar a razão sinal para ruído, aumentar a eficiência de detecção, e/ou aplicar a distribuição assumida pela medida de detecção.

O vetor de características extraído V é então comparado com um conjunto de veto- res de referência n-dimensionais (W1 W2, Wm} m < n, para obter uma medição de detecção de razão de correlação Dv. Cada vetor de referência normalmente representa um dos símbo- Ios de mensagem m e o símbolo associado ao vetor de referência mais similar ao vetor ex- traído é o símbolo relatado. Somente quando a medida de detecção excede um limite de detecção Τ, o detector relata uma detecção positiva. Caso contrário, nenhuma marca d'água é relatada como tendo sido detectada.

A fórmula exata para computar a medida de detecção é fundamental para determi- nar a probabilidade de falso positivo. A correlação normalizada é uma das técnicas mais comuns empregadas na medida de detecção. A correlação normalizada entre dois vetores n-dimensionais V e W1 é

r _ V-Wi

vw. ~

^V-VWi-Wi)

onde o símbolo · é o produto interno. Duas outras medidas de detecção publicadas com base na correlação normalizada são a diferença entre o maior e a segundo maior corre- lação de magnitude e a razão entre a maior e a segunda maior correlação de magnitude.

Considere a medida de detecção de razão de correlação. O conjunto de |CVWil © calculado para todos os vetores de referência m, Wi. Estes são, então, classificados do mai- or para o menor.

^ I ^V,Wn I ^V,Wnl I— " ' —I Cy W.m

A medida de detecção de razão de correlação é então definido como: ■ο,.ψ^,

V ,Wi 2

e ο símbolo de mensagem associado a Wn é relatado, quando Dv ultrapassa o limite de detecção. Note que Dv é sempre maior ou igual a 1.

Em seguida, a medida de detecção de razão de correlação (1) é estudada e uma fórmula analítica é derivada para a probabilidade de falso positivo, ou seja, P(DV > T), a pro- babilidade de que Dv > T para um trabalho não sinalizado com marca d'água, no qual T é o limite de detecção.

Considere o conjunto de vetores de referência (W1, W2, ... , Wm), onde |Wj| = Vw i.W e Wi .Wj = 0 para i Φ j. Em outras palavras, o conjunto (W1, W2... Wm,) é uma base ortonormal para um espaço de vetor m-dimensional. Quando m < n, este conjunto pode ser expandido para uma base ortonormal para o espaço vetorial n-dimensional, onde V e (W1) residem, ao acrescentar os vetores de comprimento unitário η - m ao conjunto, onde cada um é ortogonal a todos os outros e aos de (WiJ. Uma base ortonormal de η dimensões é indicada como (W1, W2,... Wm em + 2,... en}. Em álgebra linear, dois vetores em um espaço de produto interno é ortonormal se

forem ortogonais e ambos de comprimento unitário. Os vetores ortogonais são perpendicula- res uns aos outros. Ou seja, o seu produto interno é 0.

A projeção de dois vetores a partir de uma base ortonormal para outra representa uma rotação dos eixos e isso não muda o ângulo entre os vetores. Assim, a correlação nor- malizada entre dois vetores e a medida de detecção Dv são invariantes para transformações ortogonais. Considere a projeção de V sobre esta nova base (W1, W2, ... Wm em+1, em+2, ..., en} e que os coeficientes neste espaço sejam indicados (v1, v2, ..., vn}. Neste caso, a corre- lação normalizada pode ser escrita

V-Wi v,

c

V,W:

J(V-V)(WrWl) VF^7'

Uma vez que J-— é um fator comum'em todos os Cv,Wi para i = 1, 2, ...,m, o

\V - V

mesmo pode ser abandonado e |ν,| pode ser classificado diretamente,

I ν, |>| ν., |> ·... >| ν. .

I /1 l i /2 I —ι im

A medida de detecção de razão de correlação torna-se

^V=- (2)

V/2

e um evento de falso positivo Dv > T, é equivalente a

I Vil |> T-1 Vj I, de todos j # i1. (3)

Se partirmos do pressuposto que cada |ν,| tem a mesma probabilidade de ser o maior (uma suposição razoável, dado que o caso no qual nenhuma marca d'água foi incor- porada está sob investigação), neste caso a probabilidade de qualquer correlação normali- zada ser grande o suficiente para causar um falso positivo é m vezes maior do que a proba- bilidade de V1 causar um falso positivo. Isto é indicado como se segue:

Pfp = P (Dv >T) = m- P (Dy >T\il = 1). (4)

A partir da equação (2), fica claro que um evento de falso positivo é uma invariante escalar. Ou seja, se para algum vetor de característica V, a sua medida de detecção Dy é maior que o limite T, neste caso para uma versão em escala a.V = (O-V1, a.V2,..., a.vn} onde a é uma constante diferente de zero, Da v também é maior que T. Assim, V pode ser normali-

zado de tal modo que a sua norma 1 Lseja igual a J]" | ν,. |= 1. Isto descreve um ponto no

hiper-plano unitário Hn, = (X1, x2..., xn) | X1 |= 1} (que na verdade é uma união de 2n hi-

per-planos de dimensão η - 1). A distribuição de V no hiper-plano unitário Hn é importante para analisar o comportamento de detecção e, mais especificamente, a probabilidade de falso positivo.

Essa análise se aplica à utilização de características de detecção que produzem um

vetor de característica normalizada V que, para trabalhos não sinalizados com marca d'á- gua, pode ser aproximado por uma variável aleatória elaborada a partir de uma distribuição uniforme no hiper-plano unitário Hn. Como uma primeira hipótese, o vetor de característica normalizada V de um trabalho não sinalizado com marca d'água é uniformemente distribuído

na hiper-plano unitário Hn. A hipótese 1, combinada com o fato de que um evento de falsos positivos é invariante escalar, sugere que a probabilidade de falso positivo P(DV > T) é igual à porção de vetores de característica normalizada no hiper-plano unitário Hn de tal modo que as suas medidas de detecção sejam maiores que o limite T,

> T)^aiy,H D >T)

Area(Hn)

Um hiper-plano positivo COPIAR FÓRMULA e COPIAR FÓRMULA onde Hn+ é um

dos hiper-planos 2n em Hn para o qual todas as coordenadas são não negativas, é definido. Neste caso, por simetria, a equação (5) é equivalente a

Area(Hn)

A probabilidade de falso positivo na equação (6) é independente de n, a dimensão

do espaço vetorial, onde V e W1, residem. Uma prova disto segue, colocando um subscrito em Ρ, V e H para indicar a dimensão, neste caso:

/ \ ( " Ϊ Area{Vn+] > T)= Area = 1 - vn+I,v„+I >0,Dv > T ,

V (=i J onde Vn = {ν/, V2,..., v„}, e

( " λ Area(H„++1) = Areai £ V1 = 1 - vn+1, v„+1 > 0 .

V -=i /

Note que

Area(Z(v,= l-v„+1,vn+1 >0,Dv >T)= |(1 - V1141)-' ■ AreaiVn e H;,DVm >T)dvn.fl, e

AreaZlM = >0) = |(1-ν„+1Γ' . AreaiH:)dvn+, .

Combinando todo o acima exposto, conclui-se que

AreaiV^eHlytDy >T)

Pn+]iDy^>T) =

AreaiH+ )

= Areaj^Vi=I-vn+],v„+1 > 0,Dv^ > T)

AreaQHlV> =1~V,+l'Vn+l ^0)

= -AreajVn e /ÇZ)^ >7>fv„+1

[i\-vn^-AreaiHDdvn^

_ AreajVn ^ H;,DV >T) AreaiWn)

-PnjDv>T).

Assim, a probabilidade de falso positivo P(DV > T) é independente da dimensão η do vetor de característica. Em particular, P(DV > T) pode ser calculado ao definir η = m. Uma fórmula analítica para P (DV>T) pode ser obtida através de uma interpretação

geométrica da Equação 6, dada agora. Começando com m = 2, H2+={(xi1x2)1xí>0, e x1h-x2=I). Na Figura 1a, O = (0,0), A = (1,0), e B = (0,1). Todo o conteúdo não marcado produzirá uma detecção no segmento de linha AB. O segmento de laboratório AB é H2+. O ponto C = (c1, c2) onde c1=T^C2, representa o limite entre uma detecção positiva e uma negativa de detec- ção. Uma vez que todas as detecções positivas são detecções falsas, a probabilidade de um falso positivo é a razão do comprimento do segmento de linha AC para o todo, o comprimen- to do segmento de linha AB. Adicionar um ponto D = (c1, 0) sobre o segmento de linha AO. Esta é a projeção de C para x,. Então, uma vez que |AO| = |AD| + |DO| = c2 + c1 = c2 + Tc2 = (T+1)c2,

\AB\ \AO\ Γ + 1

Assim

P(DV >T) = 2 · P(Dy > T | Π = 1) =

Γ + 1

Quando m = 3, H3+ = {(xi,x2,x3)|xi s 0, e X1 + x2 + x3 = 1). Na Figura 1b, O = (0,0,0), A = (1, 0, 0), B = (0, 1, 0) e C = (0, 0, 1). O patch planar ABC é H3+. O ponto D = (d1,d2,0) é um ponto no segmento de linha AB tal que di = T.d2, e o ponto E = Ce1l 0, e3) é o ponto sobre o segmento de linha AC tal que e-, = T . e3 O ponto F é a interseção de CD e o BE. Então:

PjDv > T | /1 = I) = Are<ADFE) Area(ABC)

_ Area(ADC) - Area(CEF) Area(ABC)

_ Area(ADC) Area(CEF) Area(BCE) Area(ABC) Area(BCE) Area(ABC)

_\AD\ |£F| \CE\ ~\ÃB\~]ÊB\']CÃ\

= _1___1__T__

~T + l T + 2 T + \

2

(Τ + 1)(Y + 2)

_6_

Então P(DV > T) = 3 . P(DV > T |il = 1) = <7 + 0(7 + 2)

Quando m = 4, H/ = {(xi,x2,x3,x4)|xi > 0, e X1 + x2 + x3 + x4 = 1}. Então:

P(Dv>T|il = 1) =

Areajv e/Çv, >Γ·ν2ν, >Γ·ν3) Area(VeH;,V] >Γ·ν2,ν, >Γ·ν3,ν, <Τ·ν4) Area(Hl) Area(Hl)

2___2 T

(Τ + 1)(Γ + 2) (Τ + 1)(Γ + 2)(Τ + 3)

=_6_

(Τ + 1)(Τ + 2)(Τ + 3) ' _24_

EntãoP(Dv>T) = ^ + 1^ + 2Xr + 3>'

Continuando por dedução, pode-se obter uma fórmula analítica da probabilidade de falso positivo P(DV > T) para qualquer m, o que vem a ser:

Pfit = P(Dy > T) =-^-. (7)

fp V Π£'(Γ + 0 K '

Para verificar se a fórmula da equação (7) está correta, os resultados preditos fo-

ram comparados com os resultados obtidos a partir de 100.000 vetores sintéticos extraídos de uma unidade de uma distribuição uniforme de hiper-plano unitária. A dimensão do vetor de característica é 1024 (n = 1024). Há 8 vetores ortogonais de marca d'água no detector (m = 8). A Figura 1c mostra os resultados da comparação dos vetores sintéticos contra as pre- dições feitas pela equação (7). As predições da fórmula analítica corresponde aos resulta- dos experimentais muito de perto abaixo a pelo menos Pfp = 10"4

A Figura 3A é um fluxograma de uma modalidade do método de determinação de limite da presente invenção. Uma probabilidade de falso positivo desejada é aceita na etapa 305. Este requisito é específico ao ambiente de aplicação no qual a detecção de marca d'á- gua ocorre. Um limite é determinado na etapa 310 e emitido para o detector de marca d'á- gua na etapa 315. De acordo com a descrição acima, uma tabela de valores limites pode ser gerada tanto na inicialização ou em algum outro momento, antes ou durante a primeira de- terminação de limite. A equação 7 acima é usada para gerar a tabela de valores limites (ta- bela de limites). Um gerador de tabela usa a equação 7, juntamente com um valor limite ini- ciai ou mínimo, um limite máximo ou final e um tamanho de intervalo. A tabela de limites cria uma correspondência entre uma seleção de limites e as probabilidades de falso positivo que a mesma implica.

Para fins das modalidades da presente invenção descritas no presente documento, um valor limite inicial pode ser introduzido por um usuário ou selecionado. Quando selecio- nado, um valor limite inicial possível é o limite inferior de uma probabilidade de falso negati- vo. Além disso, correspondentemente, para o valor limite final, quando selecionado, um va- lor limite final possível é um limite superior da dita probabilidade de falso positivo. Os incre- mentos ou intervalos limites utilizados nos cálculos são selecionados com base, entre outros fatores, no armazenamento disponível a fim de armazenar a tabela de limites ou na precisão desejada dos cálculos.

A Figura 3b é um diagrama em blocos do aparelho ou módulo de determinação de limites da presente invenção. O aparelho ou módulo de determinação de limites aceita a probabilidade de falso positivo como entrada, determina o limite e transmite o limite para um detector de marca d'água. A Figura 4a é um fluxograma de uma modalidade do método de determinação de limite da presente invenção. Uma probabilidade de falso positivo desejada é aceita na etapa 405. O índice para a tabela de limites preparada na inicialização ou, de outra forma, no a- vanço é inicializado na etapa 410. A entrada de tabela é recuperada a partir da tabela com base no índice na etapa 415. Deve-se ter em mente que o índice pode não ser necessaria- mente inicializado para uma primeira entrada de tabela. Vários esquemas de pesquisa de tabelas são conhecidos no estado da técnica, incluindo um método binário, no qual o índice de tabela é inicializado aproximadamente no ponto intermediário da tabela. Isto é repetido de modo que toda a tabela não precise ser pesquisada. A entrada de tabela recuperada é comparada com a probabilidade de falso positivo desejada na etapa 420 e, se inferior à falsa probabilidade desejada, e não houver nenhuma outra entrada de limites superior ao limite recuperado e for menor que a probabilidade de falso positivo desejada, então o limite deter- minado é enviado para o gerador de marca d'água na etapa 425. Se puder existir entradas limites superiores à entrada de tabela de limites recuperada e também inferiores à probabili- dade de falso positivo desejada, então o índice da tabela é ajustado na etapa 430. A Figura 4b é um diagrama em blocos do aparelho ou módulo de determinação de

limites 435, que inclui um módulo de pesquisa de tabela 440 e um comparador 445. O mó- dulo de pesquisa de tabela recupera as entradas da tabela de limites a partir da tabela de limites previamente gerada usando um índice. O comparador 445 realiza a comparação e, se os critérios forem atendidos, emite o limite para o detector de marca d'água e, se os crité- rios não forem atendidos, em seguida, retorna para o módulo de pesquisa de tabela tendo ajustado o índice da tabela. O índice da tabela pode ser ajustado, quer pelo módulo de pes- quisa de tabela ou pelo comparador ou por outro módulo (não mostrado) que executa essa função.

A Figura 5a é um fluxograma de uma modalidade alternativa do método de deter- minação de limite da presente invenção. Nesta modalidade, uma tabela de limites não é preparada com antecedência, mas o limite é determinado através de cálculos iterativos. Na etapa 505, a probabilidade de falso positivo desejada é recebida ou aceita como entrada. Um valor limite inicial é selecionado na etapa 510. Deve-se notar que o valor limite inicial pode também ser introduzido por um usuário. O limite corrente é inicializado para o valor limite inicial que foi selecionado ou introduzido na etapa 515. O valor limite corrente é usado para calcular a probabilidade de falso positivo na etapa 520. O valor da diferença entre a probabilidade de falso positivo desejada e a probabilidade de falso positivo calculada é cal- culado na etapa 525. O valor da diferença é comparado a 0 e a um valor predeterminado ε na etapa 530. Se o valor da diferença for maior que ou igual a 0 e menor que um valor pre- definido ε, então o sistema irá emitir o valor limite corrente, T, para um detector de marca d'água na etapa 540. Se o valor da diferença for negativo ou maior que o valor ε, então o limite corrente será modificado na etapa 535 de acordo com o sinal e a magnitude do valor da diferença. O limite corrente modificado é utilizado para recalcular uma nova probabilidade de falso positivo usando o valor limite corrente. Esse processo continua até que o valor da diferença seja maior que ou igual a zero e abaixo do valor ε. Quando isso ocorre, o valor limite corrente, T, será enviado para um detector de marca d'água na etapa 540. O valor limite corrente produz uma probabilidade de falso positivo, menor que a probabilidade de falso positivo necessária / desejada, de no máximo ε.

A Figura 5b é um diagrama em blocos de uma modalidade alternativa do aparelho de determinação de limite 545 da presente invenção, incluindo o módulo calculador de pro- babilidade de falso positivo 550 e o comparador 555. O calculador de probabilidade de falso positivo 550 calcula um valor de probabilidade de falso positivo utilizando um valor limite (corrente) e também calcula a diferença entre um valor de falsa probabilidade desejada / necessária e o valor de probabilidade de falso positivo calculada. O comparador 555 realiza uma comparação entre o valor de diferença e 0 e também entre o valor de diferença e um valor predeterminado ε. Quando o valor da diferença é maior que ou igual a 0 e menor que um valor predefinido ε, então o sistema enviará o valor limite corrente, T, para um detector de marca d'água. Quando o valor da diferença é negativo ou maior que o valor ε, então o limite corrente é modificado de acordo com o sinal e a magnitude do valor da diferença. O limite corrente modificado é usado para re-calcular uma nova probabilidade de falso positivo usando o valor limite corrente. Esse processo continua até que o valor da diferença seja maior ou igual a zero ou abaixo do valor ε. Quando isso acontece, o valor limite corrente, T, será emitido para um detector de marca d'água. O valor limite corrente produz uma probabi- lidade de falso positivo menor que a probabilidade de falso positivo requerida / desejada, em no máximo ε.

É preciso entender que a presente invenção pode ser implementada em várias for- mas de hardware (por exemplo, em um chip ASIC), software, firmware, processadores de uso especial, ou combinação dos mesmos, por exemplo, dentro de um servidor, um disposi- tivo intermediário (como um ponto de acesso sem fio ou um roteador sem fio) ou dispositivo móvel. De preferência, a presente invenção é implementada como uma combinação de hardware e software. Além disso, o software é de preferência implementado como um pro- grama aplicativo tangivelmente incorporado em um dispositivo de armazenamento de pro- grama. O programa aplicativo pode ser carregado para, e executado por, uma máquina compreendendo qualquer arquitetura adequada. De preferência, a máquina é implementada em uma plataforma de computador tendo um hardware, como, por exemplo, uma ou mais unidades de processamento central (CPU), uma memória de acesso aleatório (RAM), e in- terfaces de entrada / saída (l/O). A plataforma de computador inclui ainda um sistema ope- racional ou código de micro-instruções. Os vários processos e funções descritos no presente documento podem fazer parte do código de micro-instrução ou parte do programa aplicativo (ou uma combinação destes), executados através do sistema operacional. Além disso, vá- rios outros dispositivos periféricos podem ser conectados à plataforma de computador, tal como um dispositivo de armazenamento de dados adicional e um dispositivo de impressão.

Deve-se ainda entender que, uma vez que alguns dos componentes de sistema constituinte e as etapas de método ilustradas nas figuras em anexo são de preferência im- plementados em um software, as conexões em questão entre os componentes de sistema (ou as etapas de processo) podem variar, dependendo da maneira na qual a presente in- venção é programada. Dado os presentes ensinamentos, uma pessoa com habilidade sim- ples na técnica relacionada será capaz de contemplar estas implementações ou configura- ções, como também implementações ou configurações similares, da presente invenção.

Claims

1. Método para determinar um limite, o dito método sendo CARACTERIZADO pelo fato de compreender as etapas de: - selecionar uma probabilidade de falso resultado desejada; e - selecionar um valor limite a partir de uma tabela de limites correspondente à dita probabilidade de falso resultado desejada.

2. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de com- preender ainda as etapas de: - criar a dita tabela de limites; - sendo que a dita etapa de criar compreende ainda: - o cálculo de cada entrada de probabilidade de falso resultado na dita tabefã de Ii- <formula>formula see original document page 16</formula> - o armazenamento da dita probabilidade de falso resultado calculada na dita Iabela de limites e do dito valor limite utilizado para calcular a dita entrada de probabilidade de falso resultado, quando T é o dito valor limite.

3. Método, de acordo com a reivindicação 2, CARACTERIZADO pelo fato de que a dita etapa de calcular é realizada utilizando um primeiro valor limite, um segundo valor I imite, e um intervalo limite, incrementando iterativamente o dito primeiro valor limite por meio do dito intervalo limite e calculando cada dita entrada de probabilidade de falso resultado da dita tabela de limites até que o dito primeiro valor limite fique igual ao dito segundo valor limite.

4. Método, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que a dita probabilidade de falso resultado é uma probabilidade de falso positivo e ainda pelo fato de que o dito primeiro valor limite é um limite inferior de uma probabilidade de falso negativo, e o dito segundo valor limite segundo é um limite superior da dita probabilidade de falso po- sitivo.

5. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a dita etapa de selecionar recupera o dito valor limite a partir da dita tabela de limites, sendo que o dito valor limite é um valor limite maior, tendo uma probabilidade de falso resullado menor que a dita probabilidade de falso resultado desejada.

6. Método para determinar um limite, o dito método sendo CARACTERIZADO pelo fato de compreender as etapas de: - selecionar uma probabilidade de falso resultado desejada; - calcular uma probabilidade de falso resultado; - calcular um valor de diferença entre a dita probabilidade de falso resultado calcu- lada e a dita probabilidade de falso resultado desejada; - comparar o dito valor de diferença com um primeiro valor predeterminado; e - comparar o dito valor de diferença com um segundo valor predeterminado quando um resultado da dita primeira etapa de comparar é positivo.

7. Método, de acordo com a reivindicação 6, CARACTERIZADO pelo fato de que a dita probabilidade de falso resultado é uma probabilidade de falso positivo, e compreenden- do ainda as etapas de: - selecionar um primeiro valor limite; e - modificar o dito primeiro valor limite quando os resultados de ambas as ditas eta- pas de comparar não são positivos.

8. Aparelho para determinar um limite, CARACTERIZADO pelo fato de compreen- der: - um meio para selecionar uma probabilidade de falso resultado desejada; e - um meios para selecionar um valor limite a partir de uma tabela de limites corres- pondente à dita probabilidade de falso resultado desejada.

9. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de compreender ainda: - um meio para criar a dita tabela de limites; - sendo que o dito meio para criar compreende ainda: - um meio para calcular cada entrada de probabilidade de falso resultado na dita ta- <formula>formula see original document page 17</formula> bela de limites usando '=· e - um meio para armazenar a dita probabilidade de falso resultado calculada na dita tabela de limites e o dito valor limite sendo usado para calcular a dita entrada de probabili- dade de falso resultado, quando T é o dito valor limite.

10. Aparelho, de acordo com a reivindicação 9, CARACTERIZADO pelo fato de que o dito meio para calcular é executado usando um primeiro valor limite, um segundo valor limite e um intervalo limite, iterativamente incrementando o dito primeiro valor limite por meio do dito intervalo limite e calculando cada dita probabilidade de falso resultado da dita tabela de limites até que o dito primeiro valor limite fique igual ao dito segundo valor limite.

11. Aparelho, de acordo com a reivindicação 10, CARACTERIZADO pelo fato de que a dita probabilidade de falso resultado é uma probabilidade de falso positivo e ainda pelo fato de que o dito primeiro valor limite é um limite inferior de uma probabilidade de falso negativo e o dito segundo valor limite segundo é um limite superior da dita probabilidade de falso positivo.

12. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que o dito meio para selecionar recupera o dito valor limite a partir da dita tabela de limites, sen- do que o dito valor limite é um maior valor limite tendo uma probabilidade de falso resultado menor que a dita probabilidade de falso positivo desejada. a

13. Aparelho para determinar um limite correspondente a uma probabilidade de fal- so resultado desejada, o aparelho sendo CARACTERIZADO pelo fato de compreender: - um meio para calcular uma probabilidade de falso resultado; - um meio para calcular um valor de diferença entre a dita probabilidade de falso re- sultado calculada e a dita probabilidade de falso resultado desejada; - um meio para comparar o dito valor de diferença com um primeiro valor predeter- minado; e - um meio para comparar o dito valor de diferença com um segundo valor prede- terminado quando um resultado da dita primeira etapa de comparaTé positivo.

14. Método, de acordo com a reivindicação 6, CARACTERIZADO pelo fato de que a dita probabilidade de falso resultado é uma probabilidade de falso positivo, e compreende ainda: - um meio para selecionar um primeiro valor limite; e - um meio para modificar o dito primeiro valor limite quando os resultados das duas ditas etapas de comparar não são positivos.