Caracteristicas de Imagens II
Fitting
Etapas
pBorda
Borda=cadeia
de pixels
Borda=tem um
modelo
y  10x  3
Finding
Connected
Components
Fitting
Finding Connected Components
(Sequential Algorithm 4-connectivity)
1.
2.
Scan the binary image left to right top to bottom
If an unlabelled pixel has a value of 1, assign a new
label to it according to the following rules:
0
0
0
0


0 1 0 L
L 1 L L
L
L

0 1 0 L
3.
4.
L
M
1

L
M
L
(Set L=M)
Determine equivalence classes of labels.
In the second pass, assign the same label to all
elements in an equivalence class.
Rules for 8-connectivity
0 0 0 0 0 0

0 1
0 L
L 0 0 L 0 0

0 1
0 L
0 L 0
0 0 L 0 0 L

0 1
0 L
0 1
* * 0
L 1

0 L 0

0
0 L
0 0
L L
*
M
* L
*

1
M
* L
(Set L=M)
L
Least Squares Fit
Minimizeyi  (ax  b)
2
m,b
i
7,0
6,0
5,0
4,0
3,0
2,0
1,0
0,0
0
0,2
0,4
y_medido
0,6
y_est
0,8
1
Local maximum and local minimum
• Horizontal tangent plane
– Parallel to xy-plane
• Relative extrema
Alfer Demir
Condição de máximo ou mínimo
Ajuste de linha por LSF
  n
2
  ( yi  b  axi )   0
a  i 1

  n
2
(
y

b

ax
)
 i
0
i
b  i 1

n
n
2 ( yi  b  axi )(1)  0
2 ( yi  b  axi )( xi )  0
i 1
i 1
n
n
n
i 1
i 1
i 1
  xi yi  b xi  a xi2  0
n
n
i 1
i 1
  yi  bn  a xi  0
 xi yi   xi2
 i
Solve  i
  yi    xi
 i
  i
 x  a
i
i
n  b 

Ajuste de linha por LSF
EXCEL
LINEST(known_y's,known_x's,const,stats)
y
Minimizeyi  (mxi  c)
2
i
Minimizeaxi  byi  c
2
x
y
i
Line fitting can be max.
likelihood - but choice of
model is important
x
Distância euclidiana
ax  by  c  0
y
di
a  cos , b  sin 
a 2  b2  1
x
di  axi  byi  c
Minimização baseada na distância euclidiana
E  axi  byi  c
2
y
i
Minimize E, sugeito a:
a 2  b2  1
x
Minimizando com respeito a “c”
n
E
 0   (axi  byi  c)  0
c
i 1
n
n
i 1
i 1
n c   axi   byi
1 n
1 n
c  a  xi  b  yi
n i 1
n i 1
c  ax  by
Substituindo “c” de volta em E
E   a( xi  x )  b( yi  y )
2
i
 ( x1  x ) ( y1  y ) 


U
...

 (x  x) ( y  y) 
n
 n

a
n   
b
E  a( xi  x )  b( yi  y)  Un
2
2
i
E  n U Un  n Sn
T
T
T
Novo problema:
Minimize
E  n Sn
T
sugeito a:
n n 1
T
2
2

xi  n x

T
S  U U  
  xi yi  n x y
forma
quadrática
 x y  n xy 

y

n
y


S é simétrica e positiva definida.
i
i
2
i
2
Mínimo de formas quadráticas de matrizes
simétricas positivas definidas
Ax  x
Ax  Ix
A  Ix  0
b  x   0 
a  
    
 b

c    y   0 

b 
a  
2
det 
 0  A  B  C  0  1 , 2

c  
 b
a  i
 b

b 
 0
i    ,

c  i 
 0
i   0
Autovetores e autovalores de matrizes simétricas
positivas definidas
 Ai  i i  i
Ai  ii
T
i
i  0
T
i
A1  11
2T A1  12T1
A2  22
 A2    
T
1
T
2 1 2
(1  2 )   0
T
2 1
12T1  21T2
  0
T
2 1
Minimização como um problema de autovalores
p  xi  yj  x'1  y'2
2
y
p
1
T (p)  x'T (1 )  y'T (2 )  x' 11  y' 22
1 0   x'
x A x  x' y ' 
 

 0 2   y '
T
x
( x' ) 2  ( y' ) 2  1
f ( x' , y' )  1 ( x' )2  2 ( y' )2
mínimo
Minimização baseada na distância
euclidiana
Let theline be : ax  by  c  0
a 
Find theEigen Vectors  of thematrix
b 
2



x



i
 i 
2

x

i i

n





  xi   yi 

 i  i

 xi yi 
n
 i
Computec  a
x
i
i
n
b
y
i
i
n



  xi   yi  
 i  i

x
y

i i i

n

2



  yi 

i


2

i yi  n

Maximum Likelihood
Maximize the Log likelihood function L
L
2


i axi  byi  c
2 2
Given constraint
a 2  b2  1
Fitting as a Probabilistic Inference Problem
• Generative model
– The measurements are generated by a line
with additive Gaussian noise
– The likelihood function given by
– Maximum likelihood
Multiplicadores de Lagrange
E  n Sn
sugeito a: n n  1
T

Minimize
T
Minimize
L(n,  )  n S n   (n n 1)
L
0
a
T
L
0
b
T
L
0

a
n   
b
L  2S n  2n  0
S n  n
c  ax  by
Maximo e mínimo sugeito a restrições
f ( x, y)  49  x2  y 2
x  3 y  10  0
x  10 3 y
~
f ( y)  49  (10  3 y)2  y 2
~
f ( y)  51 60y  8 y 2
~
f ( y)
 60  16y  0
y
...
Multiplicador de Lagrange
f ( x, y)  49  x2  y 2
x  3 y  10  0
L( x, y,  )  49  x 2  y 2   ( x  3 y 10)  0
L( x, y,  )
L( x, y,  )
0
0
y
x
L( x, y,  )
0
...

Outliers
comportamento desejado
Who came from which line?
• Assume we know how many lines there
are - but which lines are they?
– easy, if we know who came from which line
• Strategies
– Incremental line fitting
– K-means
Fitting Curves
Fitting Curves – cont.
Distâncias algébrica e euclidiana
f ( x, y)  ax2  by2  c
y
f ( x, y)  0
f ( x, y)  1
x
Hough Transform
• There are three problems in model fitting
– Given the points that belong to a line, what is the
line?
– Which points belong to which line?
– How many lines are there?
• Hough transform is a technique for these
problems
– The basic idea is to record all the models on which
each point lies and then look for models that get
many votes
Hough Transform – cont.
• Straight line case
– Consider a single isolated edge point (xi, yi)
• There are an infinite number of lines that could
pass through the points
– Each of these lines can be characterized by
some particular equation
yi  mxi  c
Hough Transform – cont.
y
c
x
yi  mxi  c
m
c  ( xi )m  ( yi )
Hough Transform – cont.
c
c
m
m
ponto de maior
contribuição
Hough Transform – cont.
Hough Transform – cont.
• Hough transform algorithm
1. Find all of the desired feature points in the
image
2. For each feature point
For each possibility i in the accumulator that
passes through the feature point
Increment that position in the accumulator
3. Find local maxima in the accumulator
4. If desired, map each maximum in the
accumulator back to image space
Hough Transform – cont.
yi  mxi  c
m e c  [- +]
xi cos  yi sin   
y




x
0
w2  h2

Hough Transform – cont.
y
x
Hough Transform – cont.
y
x
Transformada de Hough
Transformada de Hough
Hough Transform – cont.
• Circles
– Hough transform can also be used for circles
( x  a)  ( y  b)  r
2
2
2
Hough Transform – cont.
Here the radius is fixed
Hough Transform – cont.
A 3-dimensional parameter space for circles in general
Hough Transform – cont.
• More complicated shapes
– As you can see, the Hough transform can be
used to find shapes with arbitrary complexity
as long as we can describe the shape with
some fixed number of parameters
– The number of parameters required indicates
the dimensionality of the accumulator
Generalized Hough Transform
• Some shapes may not be easily
expressed using a small set of parameters
– In this case, we explicitly list all the points on
the shape
– This variation of Hough transform is known as
generalized Hough transform
Mechanics of the Hough transform
•
•
•
Construct an array
representing , d
For each point, render
the curve (, d) into this
array, adding one at
each cell
Difficulties
–
how big should the cells
be? (too big, and we
cannot distinguish
between quite different
lines; too small, and
noise causes lines to be
missed)
•
How many lines?
–
•
Who belongs to which
line?
–
•
count the peaks in the
Hough array
tag the votes
Hardly ever satisfactory
in practice, because
problems with noise and
cell size defeat it
Curve Fitting by Hough
Transform
•
•
•
•
•
Let y=f (x,a) be the chosen parameterization of a target
curve.
Discretize the intervals of variation of a1,… ak and let
s1,… sk be the number of the discretized intervals.
Let A(s1,… sk) be an array of integer counters and
initialize all its elements to zero.
For each pixel E(i,j) such that E(i,j)=1, increment all
counters on the curve defined by y=f (x,a) in A.
Find all local maxima above certain threshold.
Curve Fitting by Hough
Transform
•
•
•
Suffer with the same problems as line fitting by Hough
Transform.
Computational complexity and storage complexity
increase rapidly with number of parameters.
Not very robust to noise
Deformable Contours
Tracking – cont.
Lip-Reading
Actor-Driven Facial Animation
Human-computer Interaction
Traffic Monitoring
Medical Image Analysis
Medical Image Analysis
SNAKE
• A snake is an active contour defined by
(s)  ( x(s), y(s))
– Was introduced first by Kass, Witkin, and Terzopoulos
– An energy is associate with each contour
1
Esnake   Eint ((s))  Eimage ((s))  Econ ((s))ds
0
SNAKE – cont.
• The internal energy term provides a
smoothness constraint on contours
 d ( s) 
 d( s) 

Eint   ( s)
   ( s)
2
 ds 
 ds 
2
2
2
– What kind of contours is preferred
SNAKE – cont.
• The image energy term provides an image
related measure
Eimage   | I  I |
– Should have a large gradient along the
contour, i.e., the contour should consist of
edge points
SNAKE – cont.
• The constraint term can be used to impose
additional constraints
– For example, some control points are
available and they should be very close to the
contour
• Called spring
– Some information may indicate the contours
should be as far as possible from some points
• Called volcano
SNAKE – cont.
• Minimization of the energy
– This is a standard variational problem
• In order to apply calculus of variations, one needs
to use a smooth representation of contours
– Minimization by steepest descent
• Requires the functional derivatives of the energy
SNAKE – cont.
Calibração da câmera
 A câmera é calibrada usando método de Tsai para a
reconstrução de elementos que não estão no plano do modelo.
 Erros de sobreposição
Algoritmo estendido
Imagem
A1
Filtragem para realce de linhas
A2
Extração de segmentos de retas longos
A3
Reconhecimento dos segmentos
B1 Cálculo da transformação projetiva planar preliminar
B2
Reconstrução da visualização do modelo
B3
Reajuste das Linhas
A4
Cálculo da transformação projetiva planar
A5
Calibração da câmera
Reajuste das linhas
 São usadas faixas de tolerância para descartar pontos distantes.
tolerância para reajuste das linhas reconstruídas
Reajuste das linhas
linha
reconstruída
pontos da
imagem
faixa de
tolerância
nova linha
localizada
A nova linha
localizada é obtida
pelo método dos
mínimos quadrados
Reajuste das linhas
Resultado do reajuste das linhas:
Cálculo da transformação projetiva planar
 Depois do reajuste das linhas do modelo na visualização,
uma nova transformação é encontrada e uma nova
reconstrução pode ser obtida.
Calibração da câmera
 A câmera é calibrada usando o método de Tsai, com erro
de sobreposição aceitável.
Trabalhando com uma seqüência
• Para a primeira imagem,
aplicamos o algoritmo
proposto por inteiro.
Próxima imagem da seqüência
A1
Filtragem para realce de linhas
B3
Reajuste das Linhas
• Para otimizar o processo, da
segunda imagem em diante,
tiramos proveito do resultado
da imagem anterior.
A4 Cálculo da transformação projetiva planar
A5
Calibração da câmera
• A transformação projetiva
planar final da imagem
anterior é usada como a
transformação preliminar para
a imagem corrente.
Reajuste dos segmentos


pontos da cena n
novo ajuste
posição do segmento na cena n-2
posição do segmento na cena n-1

estimativa de posição do segmento para cena n

Estimativa de posição do segmento na cena n dada suas posições nas cena n-1 e n-2.





Faixa de tolerância sem estimativa



Faixa de tolerância com estimativa
Algoritmo proposto
Primeira imagem da seqüência
Filtragem para realce de linhas
Reajuste dos segmentos
Extração de segmentos de retas
longos
Cálculo da transformação projetiva
planar
Reconhecimento dos segmentos
Cálculo da transformação projetiva
planar preliminar
Reconstrução da visualização do
modelo
Próxima imagem da
seqüência
Filtragem para realce de
linhas
Calibração da câmera
Heurística para determinar o limiar de
corte usado na segmentação
 Procura um patamar com valor máximo no gráfico que informa
o número de segmentos extraídos para cada valor do limiar de
corte.
9
Segmentos extraídos
8
7
6
5
4
3
2
1
0
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Limiar