%\chapter{Métodos Utilizados}\label{chapter:Métodos}
%\thispagestyle{myheadings}
\chapter{Algoritmos Implementados}
Neste capítulo são apresentadas as metodologias utilizadas neste trabalho para a segmentação de estrada, bem como as métricas definidas para avaliar os resultados. Serão descritos todos os passos dos algoritmos utilizados e as alterações necessárias para este caso particular.

Os algoritmos utilizados foram ``Lane Tracker'' e ``Real Time Detection of Lane Markers in Urban Streets'', estes destacaram dos restantes devia á metodologia usada para deteção das marcações da estrada. Estas metologias apresentavam melhores resultados face as propostas.

% -------------------------------------------------------------
% Real time Detection of Lane Markers in Urban Streets
% -------------------------------------------------------------
\section{Real time Detection of Lane Markers in Urban Streets}\label{sec:calteck}

\subsection*{Descrição}
A abordagem deste algoritmo encontra-se dividida em duas etapas. A primeira etapa é baseada na técnica da \textit{Inverse Perspective Mapping (IPM)}, que consiste no mapeamento de pontos na imagem de perspetiva corrigida. Esta imagem é depois binarizada de onde são obtidos somente os valores mais altos, onde são detetadas as linhas retas usando uma transformada de \textit{Hough} simplificada, seguida de um filtro de RANSAC para detetar as linhas curvas e, para refinar as retas encontradas anteriormente. Na segunda etapa, as linhas encontradas na imagem de perspetiva invertidas são revertidas para a imagem original onde é feita a correção e o seu prolongamento.

\subsection{Abordagem}
O primeiro passo deste algoritmo é gerar uma imagem de perspetiva invertida da estrada. Este processo tem como objetivo eliminar o efeito de perspetiva da estrada, ou seja, as linhas de marcação deixam de parecer que convergem no horizonte para estarem paralelas entre si, e ainda reduzir o tempo de processamento das imagens focando a nossa atenção somente numa região da imagem.

Para obter a imagem de perspetiva invertida da imagem original é necessário assumir que a estrada é completamente plana, e conhecer os parâmetros intrínsecos da câmara, distância focal e centro ótico, e ainda alguns parâmetros extrínsecos tais como a altura da câmera em relação ao plano da estrada, o angulo de \textit{pitch} e \textit{yaw}. Inicialmente foi definido o referencial mundo $\{F_{w}\} = \{X_{w},Y_{w},Z_{w}\}$ centrado com o centro ótico da câmara, o referencial da câmara $\{F_{c}\} = \{X_{c},Y_{c},Z_{c}\}$ e o referencial da imagem $\{F_{i}\} = \{u,v\}$ como representado na figura \ref{fig:ipm_coordenates}. 
%
%\begin{figure}[H]
%  \centering
%    \includegraphics[width=0.80\textwidth]{./Imagens/ipm_coordenadas.pdf}
%    \caption{Referenciais usados (retirada de \citep{mohamed_real_2008}).}
%    \label{fig:ipm_coordenates}
%\end{figure}
%

\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{./Imagens/ipm_coordenadas.pdf}
    \caption{Referenciais usados (retirada de \citep{mohamed_real_2008}).}
    \label{fig:ipm_coordenates}
\end{figure}

No referencial da câmara, o eixo $X_{c}$ está no plano do mundo $X_{w}Y_{w}$ e ângulo de \textit{pitch} $\alpha$ e de \textit{yaw} $\beta$ com o eixo ótico. A altura da câmara ao plano do chão é dada por \textit{h}. Para qualquer ponto do plano da imagem $^{i}P = \{u,v,1,1\}$, a sua projeção no plano da estrada é dada pela transformação homogénea (\ref{eq:trans_homo}).

\begin{equation}\label{eq:trans_homo}
^{g}_{i}T  =  h\begin{bmatrix}
      		 -\frac{1}{f_{u}}c_{2} & \frac{1}{f_{u}}s_{1}s_{2} & \frac{1}{f_u}c_uc_2-\frac{1}{f_{u}}c_{v}s_{1}s_{2}-c_{1}s_{2} & 0         	\\[0.3em]
      		 \frac{1}{f_{u}}s_{2} & \frac{1}{f_{v}}s_{1}c_{1} & -\frac{1}{f_{u}}c_{u}s_{2}-\frac{1}{f_{v}}c_{v}s_{1}c_{2}-c_{1}c_{2} & 0 \\[0.3em]
			0 & \frac{1}{f_{v}}c_{1} & -\frac{i}{f_{v}}c_{v}c_{1}+s_{1} & 0 \\[0.3em]
			0 & -\frac{1}{hf_{v}}c_{1} & \frac{1}{hf_{v}}c_{v}c_{1}-\frac{i}{h}s_{1} & 0 \\[0.3em]
     		\end{bmatrix}
\end{equation}

Por exemplo:  $^{g}P = {^{g}_{i}T*^{i}}P$ é o ponto no plano do chão correspondente ao ponto $^{i}P$ no plano da imagem, onde $\{f_{u},f_{v}\}$ são as distâncias focais verticais e horizontais, respetivamente, $\{c_{u},c_{v}\}$ são as coordenadas do centro focal em que $c_{1}=\cos\alpha$ ,$c_{2}=\cos\beta$, $s_{1}=\sin\alpha$ e $s_{2}=\sin\beta$. Estas transformações podem ser facilmente calculadas para centenas de pontos se usadas na forma matricial. A transformação inversa pode ser facilmente encontrada usando(\ref{eq:trans_inv}):
\begin{equation}\label{eq:trans_inv}
^{i}_{g}T = \begin{bmatrix}
				f_{u}c_{2}+c_{u}c_{1}s_{2} & c_{u}c_{1}c_{2}-s_{2}f_{u} & -c_{u}s_{1} & 0 \\[0.3em]
				s_{2}\left(c_{u}c_{1}-f_{v}s_{1}\right) & c_{2}\left(c_{v}c_{1}-f_{v}s_{1}\right) & -f_{v}c_{1}-c_{v}s_{1} & 0 \\[0.3em]
				c_{1}s_{2} & c_{1}c_{2} & -s_{1} & 0 \\[0.3em]
				c_{1}s_{2} & c_{1}c_{2} & -s_{1} & 0 \\[0.3em]
			\end{bmatrix}
\end{equation}

onde um ponto no plano do chão $^{g}P=\{x_{g},y_{g},-h,1\}$ pode ser descrito no plano da imagem em pixels por $^{i}P = {^{i}_{g}T^{g}}P$.

Usando estas duas transformações podemos projetar uma região de interesse da imagem original para um plano no chão. Na figura \ref{fig:ipm_sample} à direita podemos observar um exemplo de uma imagem de perspetiva invertida de uma região de interesse representada na imagem original a vermelho.

%\vspace{2mm}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.45\textwidth]{./Imagens/lane_search.pdf}
    	\includegraphics[width=0.35\textwidth]{./Imagens/IPM.pdf}
    \caption{Exemplo de imagem de perspetiva invertida. À esquerda: a imagem original com a região de interesse a vermelho. À direita: a respetiva imagem de perspetiva invertida correspondente à janela.}
    \label{fig:ipm_sample}
\end{figure}

\subsection*{Filtragem e binarização}
A imagem de perspetiva invertida é depois filtrada por um filtro gaussiano a duas dimensões. A direção vertical é uma suavização gaussiana, onde $\sigma_{y}$ é ajustado de acordo com a altura do segmento de linha a ser detetado: $ f_{v}\left(y\right)=\exp(-\frac{1}{2\sigma^2_{y}}y^2) $. A direção horizontal é a segunda derivada da gaussiana, onde $\sigma_{x}$ é ajustado de acordo com a largura esperada das linhas: $f_{u}\left(x\right)=\frac{1}{\sigma^2_x}\exp(-\frac{x²}{2\sigma²_x})\left(1-\frac{x²}{\sigma²_x}\right)$. O filtro é ajustado especificamente para linhas verticais bem destacadas em fundos pretos com larguras especificas.

O uso deste filtro separado permite uma implementação mais eficiente e muito mais rápida do que usar um filtro não separado. Na figura \ref{fig:ipm_filtro}, à esquerda, temos o elemento estruturante usado no filtro, o resultado da imagem depois de filtrada ao centro, e o resultado da imagem binarizada á direita. Como se pode ver pela imagem filtrada, existe uma resposta muito grande às linhas, onde só retemos os valores mais altos. Isto é feito selecionando q\% da imagem filtrada e removendo todos os valores abaixo desse limiar. Neste passo é assumido que o veículo se encontra quase paralelo às linhas.

\vspace{2mm}
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.5]{./Imagens/ipm_filtro.pdf}
    \caption{Imagem filtrada e binarizada. À esquerda: temos o elemento estruturante usado no filtro. No meio: a imagem depois de filtrada. À direita: a imagem depois de binarizada (retirado de \citep{mohamed_real_2008}).}
    \label{fig:ipm_filtro}
\end{figure}

\subsection*{Deteção das linhas}
Esta etapa é responsável pela deteção das linhas na imagem binarizada. São usadas duas técnicas: uma versão simplificada da transformada de \textit{Hough} para identificar as linhas existentes na imagem, seguido de um ``fitting'' de linhas utilizando RANSAC para um ajuste mais apropriado. É criado um histograma com o valor do total dos pixels de cada coluna da imagem, este histograma é suavizado por um filtro gaussiano, e seguidamente são encontrados os máximos para encontrar a posição das linhas, que será usada posteriormente para obter uma precisão superior, fazendo o ajuste a uma \textit{spline} ao máximo local e aos dois vizinhos mais próximos. Por fim, as linhas ``muito próximas'' são agrupadas para eliminar múltiplas deteções da mesma linha. Na figura \ref{fig:hough_line_grouping} podemos ver o resultado desta operação.

\begin{figure}[H]
  \centering
    \includegraphics[scale=0.4]{./Imagens/hough_line_grouping.pdf}
    \caption{À esquerda: histograma com o total dos pixels para cada coluna com os máximos locais a vermelho. À direita: Linhas detetadas depois de agrupadas (retirado de \citep{mohamed_real_2008}).}
    \label{fig:hough_line_grouping}
\end{figure}

O próximo passo é obter uma deteção mais precisa dos parâmetros que descrevem as linhas usando RANSAC. Para cada linha vertical detetada acima, é criada uma região de interesse à sua volta (fig. \ref{fig:ransac_fitting}).
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.6]{./Imagens/ransac_line_fitting.pdf}
    \caption{À esquerda: Região de interesse à volta de uma linha do passo anterior, e a vermelho a linha encontrada. À direita: Linhas resultantes deste passo (retirado de \citep{mohamed_real_2008}).}
    \label{fig:ransac_fitting}
\end{figure}

\subsection*{Deteção mais precisa dos parâmetros que descrevem as linhas utilizando RANSAC}


O passo anterior devolve um linha candidata na imagem, que depois é refinada neste passo. Para cada linha é criada uma região de interesse à sua volta onde é feito o ajuste das linhas. O ajuste é iniciado com as linhas da imagem anterior, pois são o ponto de partida para este passo. O ajuste usado é uma \textit{spline} de terceira ordem. Uma \textit{spline} é uma curva definida por dois ou mais pontos de controlo. Os pontos de controlo que ficam na curva são chamados de nós e os demais definem a tangente a curva. Neste caso são usadas \textit{splines} de Bézier, que são curvas polinomiais expressas pela interpolação linear entre alguns pontos representativos: os pontos de controle. Por exemplo, a \textit{spline} de Bézier representada na fig. \ref{fig:bezier_spline} é definida pelos pontos (A,B,C,D), é delimitada pelos nós A e D e nesses nós, a curva é tangente ao vetores AB e DC. Variando as posições dos pontos B e C, a curva apenas varia sua inclinação, mas continua passando pelos pontos A e D.

\begin{figure}[H]
  \centering
    \includegraphics[width=0.45\textwidth]{./Imagens/spline.pdf}
    \caption{Spline de Bézier com nós (A, D) e pontos de controle (A, B, C, D).}
    \label{fig:bezier_spline}
\end{figure}

Onde os pontos de controlo formam um polígono delimitador em torno da própria linha. A \textit{spline} de terceiro grau é definida por:
$$Q\left(t\right)=T\left(t\right)MP$$
\begin{equation}
= \begin{bmatrix}
	t^3 	&	t^2	&	t	&	1	\\[0.3em]
\end{bmatrix}
\begin{bmatrix}
	-1 	&	3	&	-3	&	1	\\[0.3em]
	3	&	-6	&	3	&	0	\\[0.3em]
	-3	&	3	&	0	&	0	\\[0.3em]
	1	&	0	&	0	&	0	\\[0.3em]
\end{bmatrix}
\begin{bmatrix}
	P_0	\\[0.3em]
	P_1	\\[0.3em]
	P_2	\\[0.3em]
	P_3	\\[0.3em]
\end{bmatrix}
\end{equation}
onde $t\in [0,1]$,  $Q\left(0\right)=P_0$ e $Q\left(1\right)=P_3$ e os pontos $P_1$ e $P_2$ controlam a forma da linha e $M$ o declive (fig.\ref{fig:spline_core}).
\begin{algorithm}[H]
\floatname{algorithm}{Algoritmo}
	\caption{Ajuste de linhas utilizando RANSAC }
	\begin{algorithmic} 
		\FOR{$i = 1$ to $numIterations$}
			\STATE $points=getRandomSample()$
			\STATE $spline=fitSpline(points)$
			\STATE $score=computeSplineScore(spline)$
		\IF{$score > bestScore$}
			\STATE $bestSpline=spline$
		\ENDIF
		\ENDFOR
	\end{algorithmic}
	\label{alg:ransac_fitting}
\end{algorithm}

O Algoritmo \ref{alg:ransac_fitting} descreve o ajuste de linhas utilizando RANSAC. Existem três funções básicas dentro do ciclo principal:
\begin{enumerate}
\item getRamdomSample(): Esta função retira amostras dos pontos disponíveis na região de interesse que foi passada para o passo de RANSAC. É usada uma abordagem de amostragem ponderada, cujos pesos são proporcionais ao valor do pixel da imagem binarizada. Isto ajuda a escolher pontos mais relevantes.

\item fitSpline(): Esta função usa um certo número de pontos e faz o ajuste da curva de Bézier usando o método dos mínimos quadrados. Dada uma amostra de $n$ pontos, é dado um valor $t_i \in [0,1]$ a cada ponto $ p_i=(u_i,v_i)$ na amostra, onde $t_i$ é proporcional à soma cumulativa da distância euclidiana do ponto $p_i$ ao primeiro ponto $p_1$ (~\ref{eq:ti}). Definindo o ponto $p_0=p_1$ e obtemos :
\begin{equation}\label{eq:ti}
t_i = \frac{\sum^i_{j=1}d(p_j,p_{j-1})}{\sum^n_{j=1}d(p_j,p_{j-1})} 
\hspace{8mm}
t_i = 1..n
\end{equation}
onde $d(p_i,p_j) = \sqrt{(u_i-u_j)²+(v_i-v_j)²}$. Isto força $t_1=0$ e $t_n=0$ o que corresponde ao primeiro e último ponto da linha, respetivamente. De seguida, as matrizes Q e T são definidas pela expressão (\ref{eq:Q_e_T})
\begin{equation}\label{eq:Q_e_T}
Q= \begin{bmatrix}
	p_1	\\[0.3em]
	...	\\[0.3em]
	p_n	\\[0.3em]	
	\end{bmatrix}
\hspace{8mm}
T=
\begin{bmatrix}
	t^3_1		&	t^2_1		&	t_1	&	1	\\[0.3em]
	 		&	...		&	 	&	 	\\[0.3em]
	t^3_n		&	t^2_n		&	t_n	&	1	\\[0.3em]
\end{bmatrix}
\end{equation}
e revolve-se a matriz $P$ usando a pseudo-inversa:
\begin{equation}
P=(TM)Q
\end{equation}
obtendo pontos de controlo para a linha que minimiza a soma do erro quadrático de correspondência ao pontos de amostra.

\item computeSplineScore(): no RANSAC normal poderíamos estar interessados em calcular a distância normal de cada ponto a uma \textit{spline} de terceiro grau para decidir o grau de confiança da linha, contudo, isto requer a resolução de uma equação de quinto grau para cada ponto. Em vez disso, seguiu-se uma abordagem mais eficiente: é calculado o grau de confiança da linha por iteração e depois é somado os valores dos pixels pertencentes à linha. Também é tida em conta a linearidade e comprimento da linha, penalizando as mais curtas e menos retilíneas. O grau de confiança é dado por:
\begin{equation}
score=s(1+k_1l'+k_2\theta')
\end{equation}
onde $s$ é o grau de confiança bruto da linha (a soma do valor dos pixels da linha), $l'$ o comprimento da linha normalizado definido por $l'=\frac{l}{v}-1$ e $l$ é o comprimento da linha e $v$ a altura da imagem, portanto $l'=0$ significa que a linha é mais comprida que o definido e $l'=-1$ que a linha é mais curta. $\theta'$ é a curvatura da linha normalizada definida por $\theta'=\frac{\theta-1}{2}$ onde $\theta$ é a média do cosseno dos ângulos entre as linhas de união entre os pontos de controlo, por exemplo, $\theta=\frac{(\cos\theta_1+\cos\theta_2)}{2}$, e $k_2$ e $k_1$ são fatores regularizadores (fig. \ref{fig:spline_core}). Esta fórmula para o grau de confiança faz com que as linhas mais longas e menos curvas sejam menos penalizadas que as mais curtas e curvas.
\end{enumerate}
%Na figura \ref{fig:ransac_fitting} podemos observar um exemplo do resultado deste algoritmo. Na imagem da esquerda temos a região de interesse a branco envolvendo a linha detetada a vermelho. Na imagem da direita temos as linhas resultantes deste processo.


\vspace{2mm}
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.3]{./Imagens/spline_core.pdf}
    \caption{Calculo do grau de confiança (retirado de \citep{mohamed_real_2008}).}
    \label{fig:spline_core}
\end{figure}

\subsection*{Pós-processamento}
O passo final deste algoritmo é o pós-processamento dos resultados obtidos nos passos anteriores para melhorar a localização da linha e prolonga-la na imagem (fig. \ref{fig:spline_localization}). Isto é feito na imagem de perspetiva após a projeção das linhas encontrada, onde são realizados os seguintes passos:
\begin{enumerate}
\item Localização: São retirados pontos equidistantes de amostragem da spline, através dos quais são traçados segmentos de reta normais a direção tangente da \textit{spline} nos pontos. Seguidamente são obtidos os perfis de tons de cinza para estes segmentos de reta, onde são localizados os máximos locais. Estes devolvem uma localização mais correta dos pontos da \textit{spline} e permitem uma deteção mais precisa das linhas da estrada.

\item Extensão: É feita uma extensão das \textit{splines} para as ajustar ainda mais às linhas da estrada. Isto é feito prolongando a \textit{spline} a partir pontos extremos ao longo da direção da sua tangente. Nestes novos segmentos de reta é efetuado novamente o passo de localização. Os novos pontos só são aceites caso se encontrem dentro de limites estabelecidos para os valores máximos de escala de tons de cinza e variação de orientação da \textit{spline} dominante.

\item Verificação geométrica: Após cada um dos passos anteriores é feita uma verificação geométrica das \textit{splines}; caso estas excedam os limites de curvatura e comprimento, são substituídas pelas \textit{splines} do passo anterior.
  
\end{enumerate}

\vspace{2mm}
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.3]{./Imagens/spline_localization.pdf}
    \caption{Localização e extensão da linha (retirado de \citep{mohamed_real_2008}).}
    \label{fig:spline_localization}
\end{figure}
\vspace{2mm}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.44\textwidth]{./Imagens/lane_search_with_lines.pdf}
    \includegraphics[width=0.45\textwidth]{./Imagens/lane_search_with_lines_extended.pdf}
    \caption{Esquerda: Linhas antes do pós-processamento a verde. Direita: Extensão das linhas após o pós-processamento a azul.}
    \label{fig:post_processing}
\end{figure}

\subsection{Implementação}
Para ser possível implementar este algoritmo no AtlasCar foram necessárias algumas alterações, nomeadamente ao nível da leitura das definições da câmara, da maneira como as imagens são lidas pelo algoritmo e processamento das mesmas. Para fazer o processamento das imagens foi utilizada a biblioteca OpenCV (Open Source Computer Vision Library) \citep{_opencv_2014}.

Assim, foi criado um módulo ROS que subscreve as mensagens de imagem e de configuração da câmara a usar, e gera um ficheiro com todas as configurações necessárias para o algoritmo. Essas configurações são calculadas por este módulo com base nos parâmetros intrínsecos e extrínsecos da câmara, tais como a distância focal e a transformação entre o referencial do carro e o da câmara.

Quando o algoritmo é iniciado, o primeiro passo é ler os ficheiros de configuração da câmara e das linhas, de onde são retiradas as configurações para criar a imagem de perspetiva invertida, filtros de RANSAC e parâmetros de binarização. 

Inicialmente, a leitura das imagens era feita a partir de ``frames'' individuais guardados previamente em disco, o que impossibilitava o uso de imagens de tempo real. Para resolver esta questão, as imagens são recebidas em mensagens de imagem ROS; porém, como as menssagens ROS não usam o mesmo formato que o \textit{OpenCV}, é necessário o uso da biblioteca \textit{CvBridge} que faz a conversão das imagens para poderem ser usadas no \textit{OpenCV} (fig. \ref{fig:cvbridge}).

\begin{figure}[H]
  \centering
    \includegraphics[scale=0.4]{./Imagens/cvbridge.pdf}
    \caption{Converter mensagens de imagens ROS em imagens do OpenCV.}
    \label{fig:cvbridge}
\end{figure}

A principal alteração feita no processamento deste algoritmo foi a introdução de um \textit{TopHat} antes do processamento da imagem de perspetiva invertida, para facilitar a extração de linhas em condições de luminosidade adversas como, por exemplo, sombras. O \textit{TopHat} é uma operação que extrai pequenos elementos e detalhes da imagem, e, é definido como a diferença entre a imagem original e a sua abertura morfológica.

Depois de encontradas e refinadas as linhas, são escolhidos os pontos extremos para gerar  um polígono representativo do espaço navegável da estrada. Os pontos pertencentes a esse poligono são publicados numa mensagem ROS.

\begin{figure}[H]
  \centering
    \includegraphics[scale=0.3]{./Imagens/poligon_road.pdf}
    \caption{Polígono representativo do espaço navegável criado a partir das linhas da estrada.}
    \label{fig:road_poligon}
\end{figure}
\clearpage
% -------------------------------------------------------------
% Lane Departure Warning System
% -------------------------------------------------------------

\section{Algoritmo ``Lane Tracker''}\label{sec:lane_departure}
Este algoritmo teve como base um exemplo da ``toolbox'' de visão artificial do \textit{Matlab} . Este exemplo deteta as linhas numa sequência de vídeo e notifica o condutor caso este mude de faixa de rodagem. Este exemplo demonstra a deteção de linhas com base na transformada de \textit{Hough}.
\subsection{Abordagem}
Neste algoritmo, a imagem é dividida em duas regiões, a superior e a inferior, e esta separação é feita por um valor fixo pré-determinado. Somente a parte inferior é usada para fazer a procura de linhas. Essa imagem é filtrada e seguidamente  binarizada onde é aplicada a transformada de Hough para detetar as linhas da estrada. As linhas encontradas são guardadas e serão usadas para comparação no ``frame'' seguinte.

Neste algoritmo existem três funções principais, que tem como input as coordenadas dos pontos extremos das linhas:

\begin{algorithm}[H]
\floatname{algorithm}{Algoritmo}

	\caption{Localização das linhas}
	\begin{algorithmic} 
		\FOR{$i = 1$ to $EndFrame$}
			\STATE $lanematching()$
			\STATE $departuredetect()$
			\STATE $colorandtype()$
		\ENDFOR
	\end{algorithmic}
	\label{alg:}
\end{algorithm}

\begin{enumerate}
\item lanematching(): Esta função localiza as linhas da estrada. Nesta função são calculadas as distâncias entre as linhas encontradas no ``frame'' atual e às guardadas, e são escolhidas as que melhor correspondem ás guardadas. Caso a linha guardada corresponda a linha encontrada, esta é adicionada ao repositório e o número de linhas guardadas é incrementado. 

\item departuredetect(): Esta função deteta a mudança de faixa. Para tal é procurada a linha que interseta o limite inferior da imagem da esquerda para direita e aquela que se encontra mais próxima do centro do limite inferior da imagem. Seguidamente, é calculada a distância da linha ao centro da imagem caso essa distância seja inferior a um valor pré-estabelecido.

\item colorandtype(): Esta função deteta a cor da linha amarelo/branco e se é tracejada/continua. São encontrados os pontos extremos das linhas com os quais é gerada uma região de interesse onde são procuradas as cores amarela e branca, usando o espaço de cor YCbCr.

\end{enumerate}

As linhas encontradas são desenhadas na imagem com a indicação da cor e do tipo de linha. Caso exista uma mudança de faixa esta é indicada ao utilizador assim como o lado para o qual esta mudança ocorre.
\clearpage
\subsection{Implementação}
Na implementação deste algoritmo foram usadas duas bibliotecas: OpenCV e Eigen, onde a Eigen é uma biblioteca de álgebra linear.

Para que a procura das linhas seja o mais exata e autónoma possível, foi usada uma região de procura dinâmica.
Para que a região de procura das linhas seja dinâmica, foi usado um algoritmo de crescimento de regiões já implementado no OpenCV para separar a imagem em estrada e o ambiente em redor: o \textit{watershed}. Para este procedimento é necessário definir as sementes das regiões de procura (fig. \ref{fig:watershed}). A separação das regiões é feita com base na média em y dos pontos pertencentes a linha de separação das regiões (fig. \ref{fig:separacao}).

\begin{figure}[H]
  \centering
    \includegraphics[width=0.47\textwidth]{./Imagens/watershed_regions.pdf}
    \includegraphics[width=0.47\textwidth]{./Imagens/wshed.pdf}
    \caption{Segmentação de regiões usando o \textit{watershed}. À esquerda: sementes usadas. À direita: Exemplo do resultado do crescimento de regiões.}
    \label{fig:watershed}
\end{figure}

\begin{figure}[H]
  \centering
    \includegraphics[width=0.47\textwidth]{./Imagens/watershed_regions_mid_line.pdf}
    \includegraphics[width=0.47\textwidth]{./Imagens/botom.pdf}
        \caption{Separação das regiões obtidas. À esquerda: Linha de separação calculada. À direita: Região de procura. }
    \label{fig:separacao}
\end{figure}
\clearpage
Depois de encontradas as linhas, é criado um polígono com os respetivos pontos extremos; esse polígono representa o espaço navegável da estrada (fig. \ref{fig:hough_road}). Estes postos são posteriormente publicados numa mensagem ROS.
\begin{figure}[H]
  \centering
  \includegraphics[width=0.47\textwidth]{./Imagens/hough_lines_selected.pdf}
    \includegraphics[width=0.47\textwidth]{./Imagens/poli_hough_road.pdf}
    \caption{Poligono representativo do espaço navegável da estrada.}
    \label{fig:hough_road}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Avaliação do desempenho 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Avaliação do desempenho}

Para ser possível avaliar os resultados obtidos, foi necessário gerar o ``ground-truth'' do ``dataset'' utilizado, para tal foi criada uma ferramenta em \textit{Matlab} capaz de registar o ``ground-truth'' gerado manualmente para cada ``frame'' individual. Este é representado por um polígono definido manualmente (fig. \ref{fig:maps}).
  
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.263]{./Imagens/maps.pdf}
    \includegraphics[scale=0.355]{./Imagens/groud_truth.pdf}
    \caption{Esquerda: Trajeto percorrido para geração do ``ground-truth''. Direita: Um exemplo do ``ground-truth'' gerado.}
    \label{fig:maps}
\end{figure}

A avaliação quantitativa dos métodos utilizados é feita num dataset de 300 ``frames'' com base no método desenvolvido por J. M. Alvarez
 \citep{m._alvarez_3d_2010}. Para tal, foram classificadas as diferentes regiões das imagem (fig. \ref{fig:image_regions}).

 \begin{figure}[!ht]
    \centering
    \qquad
    \begin{tabular}{|c|c|c|c|}
  		\cline{3-4}
  		\multicolumn{2}{c|}{} & 	\multicolumn{2}{c|}{Ground truth}\\ 
  		\cline{3-4}
		\multicolumn{2}{c|}{} & \begin{tabular}{c} Não\\estrada\end{tabular} &	Estrada \\
		\hline
		\multirow{2}{*}{ \begin{tabular}{c} ~\\Resultado\\do algoritmo\\sobre cada pixel \\ ~\end{tabular}}
		& \begin{tabular}{c} Não\\estrada\end{tabular} 	&	\begin{tabular}{c} ~\\True Negative\\(TN)	\\~\end{tabular}		 &	\begin{tabular}{c} ~\\False Negative\\(FN)\\~\end{tabular} \\
 		\cline{2-4}
  		& Estrada 		&	\begin{tabular}{c} ~\\False Positive\\(FP)	\\~\end{tabular}		&	\begin{tabular}{c} ~\\True Positive\\(TP)	\\~\end{tabular}	 \\
  		\hline
  	
	\end{tabular}
\\[0.5cm]
	\begin{tabular}{cc}
		\raisebox{\dimexpr-\height+\ht\strutbox}{\includegraphics[width=0.45\textwidth]{./Imagens/frame_145.pdf}} & 
    		\raisebox{\dimexpr-\height+\ht\strutbox}{\includegraphics[width=0.45\textwidth]{./Imagens/medidas_de_desempenho.pdf}}\\
    	\end{tabular}

    \caption{Medidas usadas para o cálculo do desempenho. Exemplo de caso concreto (frame nº145).}
    \label{fig:image_regions}
  \end{figure}
Para se obterem as regiões descritas anteriormente são avaliados todos os pixels individualmente da imagem gerada pelo algoritmo e comparados com a imagem do ground-truth. Desta avaliação resultam então as 4 regiões:

\begin{itemize}
	\item True Negative: Caso o pixel seja classificado como não pertencente a estrada e não pertença a esta.

	\item False Negative: Caso o pixel seja classificado como não pertencente a estrada mas pertença a esta.

	\item False Positive: Caso o pixel seja classificado como estrada e não pertença a esta.

	\item True Positive: Caso o pixel seja classificado como estrada e pertença a esta.

\end{itemize}


Com base neste método foram calculadas 3 medidas de desempenho: qualidade $\hat{g}$, rácio de deteção DR, precisão da deteção DA (tabela \ref{table:pixel_measure}).
  
\begin{table}[H]\caption{Medidas de desempenho usadas para avaliar a deteção no frame (adaptado de \citep{m._alvarez_3d_2010}).} 
\centering
\begin{tabular}{|c|c|}
	\hline
 	\textbf{Medida ponderada do pixel}	& \textbf{Definição}\\ \hline
 	Qualidade					& 
 	\begin{tabular}{c}~ \\ $\hat{g} = \frac{TP}{TP+FP+FN}$ \\ ~\end{tabular} \\\hline
 	Rácio de deteção				& 
 	\begin{tabular}{c}~ \\ $DR = \frac{TP}{TP+FP}$ \\ ~\end{tabular}\\ \hline
	Precisão da deteção			& \begin{tabular}{c}~ \\ $DA = \frac{TP}{TP+FN}$ \\ ~\end{tabular}\\ \hline
%	Eficácia						& \begin{tabular}{c}~ \\ $F = \frac{2PR}{P+R}$ \\ ~\end{tabular} \\
% 	\hline
\end{tabular}
\label{table:pixel_measure}
\end{table}

Para definir a validade dos resultados foi usado o VRI (Valid Road Index); quando uma dada percentagem (K) da estrada é corretamente classificada, o resultado é valido (VRI=1), caso contrário é invalido (VRI=0). Este método é utilizado para reduzir o erro inerente á segmentação manual das imagens para gerar o ``ground-truth''.
\begin{equation}
 VRI =
  \begin{cases}
    0 &  K<\frac{TP}{Ground-truth} \\
    1 &  K>\frac{TP}{Ground-thruth}
  \end{cases}
\end{equation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Calculo da distancia
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Estimativa da distância}
O uso de uma única câmara não proporciona um método direto de medição de profundidade, porque devido ao efeito de perspetiva não existe uma linearidade entre a posição de um objeto na imagem e a sua posição no plano da estrada. Para compensar este efeito recorreu-se à imagem de perspetiva invertida, onde o efeito de perspetiva é corrigido. 
Desta forma, é possível fazer o mapeamento de todos os pixels da imagem de perspetiva invertida para o plano da estrada de uma forma linear (fig. \ref{fig:distance}).

O mapeamento pode ser expresso por:
\begin{equation}\label{eq:mapeamento}
(\upsilon,\nu,1)^t=KTR(x,y,z,1)^t
\end{equation}
onde R é a matriz rotação:
\begin{equation}
R=\begin{pmatrix}
		1 &  0  & 0 & 0\\
		0 & \cos\theta & -\sin\theta & 0\\
		0 & \sin\theta & \cos\theta & 0\\
		0 & 0 & 0 & 1
\end{pmatrix}
\end{equation}
T a matriz translação
\begin{equation}
T=\begin{pmatrix}
	1 & 0 & 0 & 0\\
	0 & 1 & 0 & 0\\
	1 & 0 & 1 & -\frac{h}{\sin\theta}\\
	0 & 0 & 0 & 1\\
\end{pmatrix}
\end{equation}
e K a matriz com os parâmetros da câmara:
\begin{equation}
K=\begin{pmatrix}
	f*k_{\upsilon} & 0 & \upsilon_{0} & 0\\
	0 & f*k_{\nu} & \nu_{0} & 0\\
	0 & 0 & 1 & 0
\end{pmatrix}
\end{equation}
onde $f$ é a distancia focal da câmara e $(k_{\mu} *k_{\nu})$ o rácio de pixels.

A eq. \ref{eq:mapeamento} também pode ser expressa por:
\begin{equation}
\begin{pmatrix}
\upsilon \\
\nu \\
1
\end{pmatrix}
=
\begin{pmatrix}
p_{1,1} & p_{1,2} & p_{1,3} & p_{1,4}\\
p_{2,1} & p_{2,2} & p_{2,3} & p_{2,4}\\
p_{3,1} & p_{3,2} & p_{3,3} & p_{3,4}
\end{pmatrix}
\begin{pmatrix}
X_w \\
Y_w \\
Z_w \\
1
\end{pmatrix}
\end{equation}
Como só estamos interessados no plano do chão $(Y_w=0)$:
\begin{equation}
\begin{pmatrix}
\upsilon \\
\nu \\
1
\end{pmatrix}
=
\begin{pmatrix}
p_{1,1} & p_{1,3} & p_{1,4}\\
p_{2,1} & p_{2,3} & p_{2,4}\\
p_{3,1} & p_{3,3} & p_{3,4}
\end{pmatrix}
\begin{pmatrix}
X_w \\
Z_w \\
1
\end{pmatrix}
\end{equation}
Utilizando esta equação é possível fazer o mapeamento de todos os pixel da imagem de perspetiva invertida.

\begin{figure}[H]
  \centering
     \includegraphics[width=0.65\textwidth]{./Imagens/atlas_lines.pdf}
     \includegraphics[width=0.3\textwidth]{./Imagens/lines.pdf}

    \caption{Referenciais usados para o cálculo da distância.}
    \label{fig:distance}
\end{figure}
Da transformação de coordenadas da imagem para coordenadas mundo, obtemos a distância relativa da estrada á câmara. É então feita uma transformação para o referencial do carro como se pode observar na fig.\ref{fig:tfs}.
\vspace{-0.5cm}
\begin{figure}[H]
  \centering
     \includegraphics[width=0.5\textwidth]{./Imagens/tfs.pdf}
    \caption{Grafo de transformações utilizadas neste método.}
    \label{fig:tfs}
\end{figure}
