(Computação Gráfica) Matrizes transformam imagens. Na atualidade, a maioria das pessoas dispõe de smartphones que possuem câmeras para registrar fotos (como selfies), vídeos curtos e longos, além de registros de terceiros, etc. Com a intensa utilização das redes sociais, muitas vezes é necessário realizar ajustes nesses registros - como rotacionar, redimensionar, cortar, entre outros. Atualmente, esses processos levam poucos minutos ou até segundos, dependendo da tarefa. Mas será que sempre foi assim? Uma das grandes aplicações da Álgebra Linear está na computação gráfica, permitindo a manipulação eficiente de imagens e vídeos. A seguir, encontre soluções para problemas desta natureza utilizando operações básicas com matrizes:
(a) Rotação de Imagem: Suponha que você tenha uma imagem representada por um conjunto de pontos em um plano 2D. Para rotacionar essa imagem em 90 graus no sentido horário, determine a matriz de rotação e aplique-a no ponto da imagem. Encontre a nova posição após a rotação.
(b) Redimensionamento de Imagem: O redimensionamento de uma imagem pode ser visto como uma operação de escala em um espaço vetorial. Dado um fator de escala , construa a matriz de transformação que, aplicada ao ponto , retorna o novo ponto correspondente à imagem redimensionada.
(c) Reflexão de Imagem: Um reflexo horizontal inverte as coordenadas de uma imagem ao longo do eixo vertical (ou seja, troca os valores de de cada ponto da imagem). Encontre a matriz que descreve essa transformação e aplique-a a um ponto da imagem.
Discuta como essas transformações são usadas em softwares de edição de imagem e vídeo.
8. (Matrizes Booleanas) Matrizes booleanas representam situações com dois estados. Uma matriz é dita do tipo Booleana se suas entradas forem iguais a ou . Estas matrizes são aplicadas computacionalmente para descrever situações em que pretende-se analisar objetos que assumem apenas duas possibilidades de estados. Vejamos alguns exemplos a seguir.
(a) Sejam três aeroportos brasileiros interligados por meio de vôos diretos ou por meio de voos com escala. A matriz a seguir mostra como estes aeroportos estão interligados, onde o valor 1 representa voos diretos e 0 voos com escala.
O elemento ai j representa vôos que saem de Ai e chegam em Aj. Quais rotas podem ser feitas apenas com vôos diretos?
(b) A matriz V^2 representa que tipo de situação em termos de conexão entre os aeroportos?
Discuta outras aplicações de matrizes booleanas em ciência da computação e áreas afins.
Passo 1
O enunciado traz dois temas principais de Álgebra Linear aplicados à Computação Gráfica e a Matrizes Booleanas.
– Na parte 7, vamos usar transformações lineares no plano 2D (rotação, escala e reflexão), representadas por matrizes 2times2, para obter as novas coordenadas de um ponto P=(x,y).
– Na parte 8, vamos interpretar uma matriz booleana V como matriz de adjacência de um grafo de aeroportos. Usaremos produto de matrizes para identificar rotas diretas e rotas em duas etapas.
Passo 2
Para rotacionar no sentido horário um ponto , lembramos que a rotação transforma
Logo a matriz de rotação deve satisfazer
Isso implica
e portanto
Passo 3
Para redimensionar um ponto por um fator de escala , a transformação linear multiplica ambas as coordenadas por . A matriz de escala é diagonal:
Passo 4
Uma reflexão horizontal em relação ao eixo vertical inverte o sinal da coordenada e mantém . Logo a matriz é
de onde
Passo 5
Na prática de edição de imagens e vídeos, essas matrizes são aplicadas a cada pixel (ou vértice de malha) de forma muito eficiente usando processamento paralelo em GPU. A composição de transformações (por exemplo, escalar depois rotacionar) é feita multiplicando as matrizes correspondentes antes de aplicar ao conjunto de pontos, reduzindo custo computacional.
Passo 6
A matriz booleana de adjacência dos aeroportos é
V= 1 & 0 & 1 0 & 1 & 1 1 & 0 & 1
Entradas 1 indicam vôos diretos Aito Aj. As rotas diretas possíveis são todas as pares (i,j) tais que Vij=1:
1to1,;1to3,;2to2,;2to3,;3to1,;3to3
Passo 7
O produto usual V^2=Vcdot V tem entrada
(V^2)ij=sumk=1^3 VikVkj,
que conta quantas maneiras de ir de Ai a Aj com exatamente dois trechos (uma escala). Calculando,
V^2= 2 & 0 & 2 1 & 1 & 2 2 & 0 & 2
Portanto (V^2)ij indica o número de rotas com uma escala entre Ai e Aj.
Passo 8
Além de modelar redes de vôos, matrizes booleanas e seus produtos (usando álgebra booleana ou contagens) aparecem em:
– Análise de conectividade em grafos (algoritmo de Warshall para caminho mínimo).
– Representação de redes sociais (amigos de amigos).
– Dependências em compiladores e sistemas de bancos de dados.
– Modelagem de circuitos lógicos (álgebra booleana).
Resposta
7(a) Matriz de rotação 90circ CW
R = 0 & 1 -1 & 0, P'=(y,,-x)
7(b) Matriz de escala
S = s & 0 0 & s, P'=(sx,;sy)
7(c) Matriz de reflexão horizontal
H = -1 & 0 0 & 1, P'=(-x,;y)
8(a) Rotas diretas (ito j) para Vij=1:
1to1,;1to3,;2to2,;2to3,;3to1,;3to3
8(b)
V^2= 2 & 0 & 2 1 & 1 & 2 2 & 0 & 2 ,
onde (V^2)ij é o número de rotas com uma escala entre Ai e Aj.