Processamento Geométrico - Scanner de curvasw3.impa.br/~jeaayres/resources/pdf/GP3.pdf ·...

PROCESSAMENTO GEOMéTRICOSCANNER DE CURVAS

José Eduardo de Almeida Ayres

Rio de Janeiro, 27 de março de 2018

Introdução

# Objetivo de amostrar a borda de uma curva em R2:

◦ Pode ser realizado através da função implícita.◦ Também é possível através de uma nuvem de pontos.

1 / 77

Scanner circular

# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0):

xc � r cos(t)yc � r sin(t)

# Amostram-se m pontos, os quais serão as origens dos raiosdisparados contra a curva:

0 : 2πm

:(2π − 2π

m

)# Um raio iniciado no par (x , y) termina no ponto simétrico

em relação à sua origem (−x ,−y).

2 / 77

-2.6 -2.4 -2.2 -2 -1.8

2.9

3

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8

Circle scanner, rays = 180, ray intervals = 10

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 180, ray intervals = 10

Tempo computacional: 0.01 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 180, ray intervals = 100

Tempo computacional: 0.03 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner, rays = 180, ray intervals = 100

Tempo computacional: 0.03 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner, rays = 180, ray intervals = 100

Tempo computacional: 0.03 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner, rays = 180, ray intervals = 100

Tempo computacional: 0.03 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 180, ray intervals = 1000

Tempo computacional: 0.27 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 180, ray intervals = 10000

Tempo computacional: 1.56 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner, rays = 180, ray intervals = 1000

Tempo computacional: 0.27 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner, rays = 180, ray intervals = 10000

Tempo computacional: 1.56 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner, rays = 180, ray intervals = 1000

Tempo computacional: 0.27 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner, rays = 180, ray intervals = 1000

Tempo computacional: 0.27 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 720, ray intervals = 1000

Tempo computacional: 0.85 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner, rays = 1440, ray intervals = 1000

Tempo computacional: 1.54 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner, rays = 720, ray intervals = 1000

Tempo computacional: 0.85 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner, rays = 1440, ray intervals = 1000

Tempo computacional: 1.54 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner, rays = 720, ray intervals = 1000

Tempo computacional: 0.85 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner, rays = 1440, ray intervals = 1000

Tempo computacional: 1.54 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner, rays = 720, ray intervals = 1000

Tempo computacional: 0.85 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner, rays = 1440, ray intervals = 1000

Tempo computacional: 1.54 segundos.

Scanner com anteparos

# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0):

xr � r cos(t)yr � r sin(t)

# Amostram-se, novamente m pontos, os quais serão,ordenadamente, usados como extremos dos anteparos.

23 / 77

Scanner com anteparos

# Dados, pontos sequenciais a e b obtidos da paratrização dacircunferência, temos os pontos iniciais dos n raios de cadaanteparo (nm raios no algoritmo):

t � 0 : 1/(n − 1) : 1

d � b − a

p0(t) � a + td

d⊥ �(−dy , dx)

|d |2d0 � point2line((0, 0), a , b)

p f (t) � p0 + 2d0d⊥

24 / 77

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000

Tempo computacional: 0.62 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000

Tempo computacional: 0.62 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000

Tempo computacional: 0.62 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000

Tempo computacional: 0.62 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.44 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.44 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.44 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.44 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000

Tempo computacional: 9.41 segundos.

Scanner com anteparos aleatórios

# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0), ∆r,∆θ ∼ U(0, 1) e re , θe ∈ [0, 1]:

xr � r(1 + re∆r) cos(t + 2πθr∆θ)yr � r(1 + re∆r) sin(t + 2πθr∆θ)

# Amostram-se, novamente m pontos, os quais serão,ordenadamente, usados como extremos dos anteparos.

34 / 77

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.69 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.69 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.69 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000

Tempo computacional: 1.69 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000

Tempo computacional: 8.37 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000

Tempo computacional: 8.37 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000

Tempo computacional: 8.37 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000

Tempo computacional: 8.37 segundos.

Scanner para pontos

# Tentar manter as mesmas abordagens anteriores, porémcom novos problemas a se resolver.

# não temos mais disponível o sinal da f (x , y), e é quaseimpossível um raio passar exatamente em um ponto.

# Abordar com distâncias, dados dois pontos p j e p j+1 de umsegmento de raio, e dado um ponto qualquer do conjundode dados ql , a partir da desigualdade triangular:

|p j+1 − ql |1 + |ql − p j |1 ≥ |p j+1 − p j |1

43 / 77

Scanner para pontos

# O ideal seria possuir a igualdade estrita, o que não épossível na prática, então façamos o uso de uma tolerânciaε:

|p j+1 − ql |1 + |ql − p j |1 − |p j+1 − p j |1 ≤ ε# Coleta-se todos os pontos que satisfaçam a desigualdade e

tomamos a média deles. Em cada raio, no primeirosegmento que possuir algum ponto.

# A escolha do ε pode gerar problemas, como o raioatravessando os primeiros pontos, por se usar um ε muitopequeno. Um valor bom, constatado para o parâmentro foi:

ε �rns

1000

44 / 77

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Points to scan

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Points to scan

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Points to scan

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Points to scan

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 4.37 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 4.37 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 4.37 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 5.12 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 5.12 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 5.12 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner points, rays = 180, ray intervals = 100

Tempo computacional: 5.12 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 42.88 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 41.77 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 41.77 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 41.77 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 41.77 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Rail scanner points, rays = 50, rails = 4, ray intervals = 1000

Tempo computacional: 74 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Rail scanner points, rays = 50, rails = 4, ray intervals = 1000

Tempo computacional: 74 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Rail scanner points, rays = 50, rails = 4, ray intervals = 1000

Tempo computacional: 74 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Rail scanner points, rays = 50, rails = 4, ray intervals = 1000

Tempo computacional: 74 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Rail scanner points, rays = 12, rails = 15, ray intervals = 1000

Tempo computacional: 38 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Rail scanner points, rays = 12, rails = 15, ray intervals = 1000

Tempo computacional: 38 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Rail scanner points, rays = 12, rails = 15, ray intervals = 1000

Tempo computacional: 38 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Rail scanner points, rays = 12, rails = 15, ray intervals = 1000

Tempo computacional: 38 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Rail scanner points, rays = 20, rails = 15, ray intervals = 1000

Tempo computacional: 79.2 segundos.

-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6

-0.2

-0.1

0

0.1

0.2

0.3

0.4Rail scanner points, rays = 20, rails = 15, ray intervals = 1000

Tempo computacional: 79.2 segundos.

-0.2 -0.1 0 0.1 0.2 0.3

2.1

2.15

2.2

2.25

2.3

2.35

2.4

2.45

2.5

2.55

2.6Rail scanner points, rays = 20, rails = 15, ray intervals = 1000

Tempo computacional: 79.2 segundos.

0 0.2 0.4 0.6 0.8 1 1.2

1.2

1.4

1.6

1.8

2

2.2

Rail scanner points, rays = 20, rails = 15, ray intervals = 1000

Tempo computacional: 79.2 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Points to scan

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Circle scanner points, rays = 180, ray intervals = 1000

Tempo computacional: 43.2 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Rail scanner points, rays = 20, rails = 15, ray intervals = 1000

Tempo computacional: 63.8 segundos.

-5 0 5

-5

-4

-3

-2

-1

0

1

2

3

4

5Rail scanner points, rays = 20, rails = 4, ray intervals = 1000

Tempo computacional: 27.7 segundos.