Estudos de otimização: Programação linear

Um dos tópicos de revisão de otimização que estou estudando é o de Programação Linear. Neste tipo de problema de otimização tanto a função objetivo quanto as restrições são funções lineares das variáveis.

Apesar de problemas deste tipo poderem ser expressos de diversas maneiras, a maneira abaixo, chamada de forma canônica, é frequentemente utilizada por materiais da área (e também por pacotes computacionais).

\[ \begin{cases} \textrm{minimize} f(x) = c^Tx \textrm{ s.a.}\\ Ax = b\\ x \geq 0 \end{cases} \]

Conversão para a forma canônica

Seguem abaixo alguns ajustes que podem ser feitos para converter um problema linear qualquer para sua forma canônica:

1. Se problema for \(maximize c^Tx\), converta-o para \(minimize -c^Tx\);
2. Se houverem restrições de \(\geq\) ou \(\leq\), adicione uma variável \(s_i\) para cada restrição e converta-as em restrições de igualdade da seguinte maneira: se \(A_ix \geq b\), então \(A_ix -s_i = b\); se \(A_ix \leq b\), então \(A_ix + s_i = b\).
3. Se houverem variáveis que podem ser negativas (sem restrição \(x_i \geq 0\)), faça a substituição \(x_i = x_i^{(+)} - x_i^{(-)}, x_i^{(+)} \geq 0, x_i^{(-)} \geq 0\).

As transformações (1) e (3) são relativamente fáceis de serem entendidas. No caso da transformação (2), é possível atribuir a \(s_i\) qualquer valor (pois s_i não faz parte da função objetivo). Desta maneira, se durante o proceso de otimização \(A_ix = b\), então basta que \(s_i = 0\).

O problema Dual

Todo problema de minimização (primal) em PL possui um problema de maximização (dual) relacionado de modo que ambos possuem o mesmo valor de função objetivo e é trivial encontrar a resposta de um a partir do outro.

Dado o problema linear na forma canônica acima, o problema dual consiste em:

\[ \begin{cases} \textrm{maximize} f(y) = b^Ty \textrm{ s.a.}\\ A^Ty \leq c\\ \end{cases} \]

A partir da solução ótima \(y^*\) do problema dual, é possível obter a solução ótima \(x^*\) do problema primal.

Seja \(u = c - A^Ty\). O vetor \(u\) contem a "distância" que cada restrição dual está da igualdade. Uma restrição somente restringe a função objetivo se está "saturada", ou seja, \(u_i = 0\). Desta maneira, podemos ignorar toda coluna de \(A\) tal que \(u_j \neq 0\), pois esta restrição não está ativa na solução do dual.Se o problem dual tiver solução única o número de componentes não zero de \(u\) será igual ao número de linhas de \(A\) (número de restrições primais). Logo, podemos obter \(x\) resolvendo o seguinte sistema linear:

\[ A[:,u_i = 0]x^* = b \].

As posições de x^* tal que \(u_i \neq 0\) são completadas com \(x^*_i = 0\), pois todas as restrições de \(A\) já são satisfeitas com igualdade pelas outras componentes de \(x^*_i\).

Exercício exemplo

Como exemplo, resolveremos um exercício simples de programação linear que ilustra os conceitos revistos.

Enunciado:

Uma startup busca fabricar máquinas de lavar falantes ao menor custo possível. Existem três maneiras de produzí-las: manualmente, semi automaticamente e automaticamente. A produção manual de uma máquina de lavar requer 1 minuto de trabalho qualificado, 40 minutos de trabalho não qualificado e 3 minutos de montagem. Para a produção semi automáticas os valores são, respectivamente, 4, 30 e 2 minutos e para a produção automática os valores são 8, 20 e 4 minutos. A startup dispões de 4500 minutos de trabalho qualificado, 36000 de trabalho não qualificado e 2700 minutos de montagem. Os custos de produção manual, semi automático e automático são, respectivamente, 70, 80 e 85 euros.

1. Formule o problema como um PL e dê uma solução.

No problema acima, as variáveis são o número \(x_1, x_2 e x_3\) de máquinas feitas por cada tipo de produção (manual, semi-automática e automática). O custo a ser minimizado é, portanto \(70x_1 + 80x_2 +85x_3\). Existem restrições quanto ao número de máquinas a serem produzidas e à capacidade de produção da fábrica (número de minutos para cada tipo de trabalho).

Abaixo o problema completo:

\[ \begin{cases} \textrm{minimize} f(x) = 70x_1 + 80x_2 +85x_3 \textrm{ s.a.}\\ x_1 + x_2 + x_3 = 999\\ x_1 + 4x_2 + 8x_3 \leq 4500\\ 40x_1 + 30x_2 + 20x_3 \leq 36000\\ 3x_1 + 2x_2 + 4x_3 \leq 2700\\ x \geq 0 \end{cases} \]

Solução usando scipy:

import numpy as np
from scipy.optimize import linprog
from numpy.linalg import solve

A_eq = np.array([[1,1,1]])
b_eq = np.array([999])

A_ub = np.array([
[1, 4, 8],
[40,30,20],
[3,2,4]])

b_ub = np.array([4500, 36000,2700])

c = np.array([70, 80, 85])

res = linprog(c, A_eq=A_eq, b_eq=b_eq, A_ub=A_ub, b_ub=b_ub,
bounds=(0, None))
print('Valor otimo:', res.values()[3], '\nX:', res.values()[4])

Valor otimo: 73725.0
X: [ 636.  330.   33.]

2. Converta o problema para sua forma canônica

Para converter o problema acima para a forma canônica é necessário adicionar variáveis de folga para as restrições de desigualdade. Desta forma, o problema se torna:

\[ \begin{cases} \textrm{minimize} f(x) = 70x_1 + 80x_2 +85x_3 \textrm{ s.a.}\\ x_1 + x_2 + x_3 = 999\\ x_1 + 4x_2 + 8x_3 + s_1 = 4500\\ 40x_1 + 30x_2 + 20x_3 + s_2 = 36000\\ 3x_1 + 2x_2 + 4x_3 + s_3 = 2700\\ x \geq 0, s \geq 0 \end{cases} \]

Solução usando scipy:

A = np.array([
[1, 1, 1, 0, 0, 0],
[1, 4, 8, 1, 0, 0],
[40, 30, 20, 0, 1, 0],
[3, 2, 4, 0, 0, 1]])

b = np.array([999, 4500, 36000, 2700])
c = np.array([70, 80, 85, 0, 0, 0])

res = linprog(c, A_eq=A, b_eq=b, bounds=(0, None))
print('Valor otimo:', res.values()[3], '\nX:', res.values()[4])

Valor otimo: 73725.0
X: [  636.   330.    33.  2280.     0.     0.]

Note que \(s_1 = 2280\) implica que \(x_1 + 4x_2 + 8x_3 \leq 4500\).

3. Apresente o dual do problema e mostre que ambas formulações obtem os mesmos resultados.

O problema dual correspondente é dado por:

\[ \begin{cases} \textrm{maximize} f(y) = 999y_1 + 4500y_2 + 360000y_3 + 2700y_4 \textrm{ s.a.} \\ y_1 + y_2 + 40y_3 + 3y_4 \leq 70 \\ y_1 + 4y_2 + 30y_3 + 2y_4 \leq 80 \\ y_1 + 8y_2 + 20y_3 + 4y_4 \leq 85 \\ y_2 \leq 0 \\ y_3 \leq 0 \\ y_4 \leq 0 \end{cases} \]

Solução usando scipy: Para a solução usando \(scipy\) podemos utilizar as variáveis declaradas anteriormente. Note que como linprog resolve problemas de minimização, o sinal da função objetivo está trocado.

res = linprog(-b, A_ub=A.T, b_ub=c, bounds=[(None,None), (None,None),
(None,None), (None,None)])
y = res.values()[4]
print('Valor otimo:', -res.values()[3], '\nY:', y)

u = c - A.T.dot(y)
Ar = A[:, np.abs(u)< 1e-10]
x_1 = solve(Ar, b)
print(x_1)
x = np.array([0.0] * len(c))
x[np.abs(u)< 1e-10] = x_1
x[np.abs(u)> 1e-10] = 0
print('Solucao X a partir de Y:', x)

Valor otimo: 73725.0
Y: [ 108.33333333    0.           -0.83333333   -1.66666667]
[  636.   330.    33.  2280.]
Solucao X a partir de Y: [  636.   330.    33.  2280.     0.     0.]

Resumo do Artigo "A Comparative Study of Staff Removal Algorithms"

O artigo "A Comparative Study of Staff Removal Algorithms" de Dalitz et al. apresenta um novo método para remoção de compasso em imagens de partituras e faz um estudo comparativo de diversos algoritmos da literatura. O estudo é baseado na deformação de um conjunto de imagens sintéticas usando diversos modelos que simulam condições reais de digitalização. Os autores buscam avaliar se existe um algoritmo que é mais robusto em todos os contextos.

Primeiramente, o artigo apresenta um esquema genérico de detecção de compasso (sem o objetivo de remoção) que resulta em uma aproximação poligonal das linhas. Para permitir o uso desta técnica com algoritmos de remoção de compasso o algoritmo genérico é modificado para estimar um "esqueleto" de cada linha do compasso. Este algoritmo é utilizado no restante do artigo como detector de linhas de compasso (para os algoritmos que necessitam de uma etapa de detecção).

Em seguida os autores fazem uma categorizam diversos algoritmos da área em quatro categorias:

1. Line Tracking: algoritmos que primeiro detectam as linhas do compasso e depois removem os pixeis em torno de cada uma das linhas. O critério usado para remoção muda conforme o método; Refs [3][16] e [19] do artigo.
2. Vector Fields: algoritmos deste tipo calculam, para cada pixel preto da imagem, um vetor cujo ângulo e comprimento é baseado no maior segmento de reta que contém somente pontos pretos; Ref [15] do artigo.
3. Runlength Analysis: estes algoritmos consideram somente as sequências de pontos verticais e/ou horizontais de mesma cor (runlengths) e analisam a vizinhança de cada runlength para decidir se ela pertence ou não a uma linha do compasso; Refs [14] e [17] do artigo.
4. Skeletonization: algoritmos que utilizam o esqueleto da imagem de partitura para decidir se um pixel é ou não parte de uma linha. O método apresentado pelos autores se encaixa nesta categoria. Ref [18] do artigo.

A última parte do artigo consiste na comparação entre os diversos algoritmos apresentados. As imagens foram geradas em programas de notação musical e posteriormente deformadas usando 10 modelos diferentes (Figura 1). Como as imagens foram geradas sinteticamente, é possível extrair o compasso delas a partir do arquivo gerado. Desta maneira, os datasets deformados são criados deformando simultaneamente a imagem de entrada (com as linhas) e a imagem de saída (sem as linhas).


A avaliação dos métodos é feita utilizando três medidas de erro diferentes (entre elas a comparação de pixels "pura") e usando o teste estatístico descrito em [Mao1999]. Todo o software e imagens usados estão disponíveis na página do MusicStaves.

Para as imagens originais "perfeitas", não existe nenhum algoritmo que obtém resultados significativamente melhores que os outros. Para o restante das deformações, o algoritmo apresentado pelos autores só não obteve o melhor desempenho na deformação Typeset Emulation.

(a) Original image.

(b) Curvature.

(c) Thickness.

(d) White speckles.

(e) Interruptions.

(f) Typeset.

(g) Kanungo

(h) Y-Variation.

(i) Rotation.

Figure 1. Deformations used to test the robustness of staff removal methods.

Referência completa: C. Dalitz, M. Droettboom, B. Pranzas, and I. Fujinaga, “A comparative study of staff removal algorithms,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 30, no. 5, pp. 753–766, 2008.  [Download]

[Mao1999] Song Mao and Tapas Kanungo. 2001. Empirical Performance Evaluation Methodology and Its Application to Page Segmentation Algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 23, 3 (March 2001), 242-256. DOI=10.1109/34.910877 [Download]

Resumo de Otimização: Mínimos Quadrados

Atualização: veja a parte 2 deste texto, onde apresento um método de solução direta do problema e uma formulação regularizada chamada Ridge Regression que evita overfitting. O método de Mínimos Quadrados (Least Squares) é utilizado para resolver sistemas "super"-determinados (ou impossíveis) , i.e. em que existem mais restrições que variáveis desconhecidas. Apesar de não ser possível encontrar uma solução que respeite todas as restrições simultaneamente, é possível calcular uma aproximação. O método de Mínimos Quadrados busca uma solução que minimize a a soma dos quadrados das diferenças entre o valor predito pelo modelo e o valor desejado. 

Dados pares de observações $(x_j, y_j), 1 \leq j \leq m, x_j \in \mathbb{R}^n, m > n$, queremos encontrar uma função $g(x; \theta), \theta \in \mathbb{R}^k$ tal que $g(x_j; \theta) = y_j$ para uma escolha adequada dos parâmetros $\theta$. A função $g(x; \theta)$ é o modelo utilizado e precisa ser definido previamente.

Idealmente, o modelo $g(x; \theta)$ seria flexível o suficiente para representar a transformação desejada. Na prática, porém, o modelo $g(x; \theta)$ pode somente aproximar o valor correto $y_j$ a partir de $x_j$. Desta forma, podemos definir o erro de aproximação do par $(x_j, y_j)$ como

\[ r_j(\theta) = g(x_j; \theta) - y_j \]

e minimizar a função objetivo

\[ f(\theta) =  \frac{1}{2}\sum^m_j [r_j(\theta)]^2 = \frac{1}{2}\sum^m_j [  g(x_j; \theta) - y_j    ]^2. \]

Ao minimizar $f(\theta)$ encontramos o vetor de parâmetros $\theta$ que "melhor" ajusta o modelo $g(x; \theta)$ aos dados $(x_j, y_j)$. Neste caso, "melhor" é definido como o vetor $\theta$ que minimiza a soma do quadrado dos erros. Por isto o nome de método de Mínimos Quadrados.

Justificativa estatística

Suponha que os $r_j(\theta)$ são independentes e identicamente distribuídos com média 0, variância $\sigma^2$ e função densidade de probabilidade $g_\sigma$. Sob estas condições, a probabilidade de observar os $r_j(\theta)$ correspondentes ao conjunto de dados $(x_j, y_j)$, dadas a variância $\sigma$ e o vetor de parâmetros $\theta$ é:

\[p( (x, y) ; \theta ; \sigma) = \prod_j^m g_\sigma( r_j(\theta) )  = \prod_j^m g_\sigma( g(x_j; \theta) - y_i ) \]

Fixadas as observações $(x_j, y_j)$ e $\sigma$, o valor "mais provável" de $\theta$ é o que maximiza $p( (x, y) ; \theta ; \sigma)$. Este estimador para $\theta$ é chamado de Estimador de Máxima Verossimilhança.

Suponha, então, que a distribuição dos $r_j$ é normal. Portanto,

\[ g_\sigma(r) = \frac{1}{\sqrt{2\pi \sigma^2}} \mathrm{exp}(-\frac{r^2}{2\sigma^2}), \]

e então,

\[p( (x, y) ; \theta ; \sigma) =   \frac{1}{(2\pi\sigma^2)^{m / 2}} \mathrm{exp}(-\frac{1}{2\sigma^2}  \sum_j^m [g(x_j; \theta) - y_i )]^2  ). \]

Para maximizar $p( (x, y) ; \theta ; \sigma)$ (dado $\sigma^2$ fixo) é necessário minimizar $\sum_j^m [g(x_j; \theta) - y_i )]^2$. Portanto, a estimativa de $\theta$ obtida pelo método de Mínimos Quadrados equivale ao estimador de máxima verossimilhança de $\theta$ (supondo que os erros $r_j$ são i.i.d. com distribuição normal de média 0 e variância fixa $\sigma^2$).

Modelos Lineares

Diversos problemas podem ser modelados utilizando funções $g(x; \theta)$ lineares em $\theta$. Podemos, portanto, escrever os resíduos como $r_j(\theta) = x_j^T\theta - y_j$.

Seja $J \in \mathbb{R}^{m\times n}$ tal que

\[ J =

\begin{pmatrix}
x_1^T \\
\dots \\
x_m^T\\
\end{pmatrix}, \]

então o problema de mínimos quadrados se reduz a minimizar a função

\[ f(\theta) = \frac{1}{2} || J\theta - y ||_2^2 \]

Modelos lineares são vantajosos pois a função acima pode ser minimizada globalmente. Isto não é necessariamente verdade para modelos não lineares em $\theta$.

Note que a função $g(x; \theta)$ deve ser linear em $\theta$, mas não necessariamente em $x$. Logo, a função

\[ g(x; \theta) = {x^{(1)}}^2  \theta_{(1)} + x^{(1)}x^{(2)}\theta_{(2)} \]

é um modelo válido para a estimação linear, pois ela equivale a construir um novo conjunto de dados $(x'_j, y_j)$, onde $x'_j = ({x^{(1)}_j}^2, x_j^{(1)}x_j^{(2)})$, e fazer a minimização linear "comum".

Exemplos usando Python

A biblioteca Scipy possui tanto a implementação do Método de Mínimos Quadrados para o caso linear quanto para o caso geral. Neste texto mostrarei como utilizar a função numpy.linalg.lstsq para estimar modelos lineares.

Iremos estimar duas funções diferentes. Ambas podem ser estimadas usando modelos lineares. A função $f_1$ é um polinômio de segundo grau e a $f_2$ é uma função de duas variáveis.

\[  f_1(x) = 2x^2 + 5x + 7 \]

\[  f_2(x_1, x_2) = 0.3x^3 - 0.2y^2 + 3y - xy + 5 \]

Estimação de polinômios 

 

Utilizaremos três modelos para estimar $f_1$:

\[ g_1(x) = p_1x + p_2 \]
\[ g_2(x) = p_1x + p_2x^2 + p_3 \]
\[ g_3(x) = p_1x + p_2x^2 + p_3x^3 + p_4 \]

 É esperado que o modelo $g_1$ possua erro grande, pois um polinômio de grau 1 não consegue aproximar um polinômio de grau 2. Por outro lado, tanto $g_2$ quanto $g_3$ deverão obter boas aproximações, sendo que em $g_3$ o componente $x^3$ deverá ser próximo de 0.

Primeiramente, iremos gerar nosso conjunto de observações de $f_1$. Em cada observação também adicionaremos um pequeno erro.

x_data = [1, 4, 7, 8, -2, 5, 6, 12, -3, -5, -10]
y_data = [2 * x*x + 5*x + 7 - (random.random() * 5 - 2.5) for x in x_data]

Agora, iremos definir a matrix $J$ para cada um dos modelos e aplicar a função lstsq para estimar os parâmetros de cada modelo.

m =  len(x_data)
x2 = np.array([x*x for x in x_data]).reshape((m, 1))
x3 = np.array([x*x*x for x in x_data]).reshape((m, 1))
x_data = np.reshape(x_data, (m, 1))
y_data = np.reshape(y_data, (m, 1))

ones = np.ones(m).reshape(m, 1)

J1 = np.hstack([x_data, ones])
J2 = np.hstack([x2, x_data, ones])
J3 = np.hstack([x3, x2, x_data, ones])

theta_g_1 = np.linalg.lstsq(J1, y_data )
theta_g_2 = np.linalg.lstsq(J2, y_data )
theta_g_3 = np.linalg.lstsq(J3, y_data )

Os resultados obtidos podem ser vistos nas figuras abaixo:

Como esperado, a estimação linear foi bem ruim e a quadrática deu resultados quase perfeitos. O polinômio de grau 3 também teve resultados bons e apresentou um coeficiente bem pequeno para o termo $x^3$.

Estimação (linear) de funções de várias variáveis

Utilizaremos 2 modelos para estimar a função $f_2$:

\[ g_1(x, y) = \theta_1 x + \theta_2 y + \theta_3 xy + \theta_4\]
\[ g_2(x, y) = \theta_1 x^2 + \theta_2 x y + \theta_3 y^2 + \theta_4 x + \theta_5 y + \theta_6\]
\[ g_3(x, y) = \theta_1 x^3 + \theta_2 x^2 y + \theta_3 x y^2 + \theta_4 y^3 + \theta_5 x^2 + \theta_6y^2 + \theta_7xy + \theta_8x + \theta_9y + \theta_{10}\] 

Primeiramente, geramos as observações usando o código abaixo. Note que é necessário um número muito maior de pontos para estimar funções mais complexas.


data = np.array([(random.randint(-50, 50), random.randint(-50, 50)) for i in range(100)])
y_data = [0.3*x**3 - 0.2*y**2 + 3*y - x*y + 5 - (random.random() * 5 - 2.5) for (x, y) in data]

Após, geramos os vetores com as componentes de cada modelo e as matrizes $J_1, J2$ e $J_3$.


m = data.shape[0]
x3  = np.array([x**3 for (x, y) in data]).reshape((m, 1))
x2  = np.array([x**2 for (x, y) in data]).reshape((m, 1))
x1   = np.array([x for (x, y) in data]).reshape((m, 1))
y3  = np.array([y**3 for (x, y) in data]).reshape((m, 1))
y2  = np.array([y**2 for (x, y) in data]).reshape((m, 1))
y1   = np.array([y for (x, y) in data]).reshape((m, 1))
x2y = np.array([x**2 * y for (x, y) in data]).reshape((m, 1))
y2x = np.array([x * y**2 for (x, y) in data]).reshape((m, 1))
xy  = np.array([x*y for (x, y) in data]).reshape((m, 1))
ones= np.ones(m).reshape((m, 1))

J_1 = np.hstack([x1, y1, xy, ones])
J_2 = np.hstack([x2, xy, y2, x1, y1, ones])
J_3 = np.hstack([x3, x2y, y2x, y3, x2, y2, xy, x1, y1, ones])

theta_g_1, err1, _, _ = np.linalg.lstsq(J_1, y_data)
theta_g_2, err2, _, _ = np.linalg.lstsq(J_2, y_data)
theta_g_3, err3, _, _ = np.linalg.lstsq(J_3, y_data)

Os resultados obtidos foram os seguintes:

 Erro: 3.73790848e+09

 Erro: 3.64574253e+09

Erro:  204.59062094

Os primeiros dois modelos, mais simples, resultaram em erros grandes pois eles não possuem algumas componentes do modelo original. Já o terceiro modelo obteve resultados muito bons, porém ele contém uma quantidade muito maior de parâmetros que o modelo original. Isto ocorre pois o modelo original, em geral, não é conhecido e acabamos incluindo componentes irrelevantes para a estimação de $y_i$.

Uma desvantagem do método de Mínimos Quadrados é que a minimização feita dificilmente zera algum $\theta_i$, pois ele pode super ajustar a curva utilizando pequenos coeficientes em componentes que podem ser irrelevantes. Desta maneira, o método não é capaz de detectar quais parâmetros/características são relevantes para um dado problema.

Comentários finais

A estimação utilizando o método de Mínimos Quadrados otimiza os parâmetros de um modelo de modo a minimizar a soma dos erros ao quadrado. Este método encontra mínimos globais se o modelo utilizado for linear (nos parâmetros a serem estimados) e é vantajoso quando se conhece ou se tem alguma intuição sobre a forma analítica do modelo original dos dados.
Atualização: veja a parte 2 deste texto, onde apresento um método de solução direta do problema e uma formulação regularizada chamada Ridge Regression que evita overfitting.

Trabalho remoto com Linux - Impressão

Neste post irei mostrar alguns comandos do linux para imprimir arquivos em um sistema remoto. É claro que estes comandos funcionam também em qualquer computador com Linux, mas eles são especialmente úteis quando nossos arquivos ficam guardados em um servidor e são disponibilizados via NFS ou SSH. Para rodá-los é necessário estar logado (usando SSH) em uma das máquinas de sua rede.

É importante lembrar que toda operação é executada nas impressoras conectadas à rede em que você está logado, ou seja, não é possível usá-los para imprimir um arquivo remoto em uma impressora na sua casa, por exemplo.

Listar impressoras conectadas

Para listar as impressoras, use o comando abaixo. Todos os comandos subsequentes recebem como parâmetro uma das impressoras listadas usando este comando.

$> lpstat -p -d

Ver a fila de impressão

 $> lpq -P impressora

Enviando trabalhos para impressão

$> lpr -Pimpressora arquivo.PDF

A opção page-range permite escolher um intervalo de páginas a serem impressas.

$> lpr -Pimpressora arquivo.PDF -o page-ranges=S-E

É só substituir S pelo número da primeira página e E pelo número da última.

Opções de impressão

Para listar as opções disponíveis execute

$> lpoptions -d impressora -l

Para ajustar a opção escolhida use

$> lpoptions -d impressora -o Opção=Valor

Esta opção é muito útil para fazer a impressora imprimir imagens coloridas em níveis de cinza. Na impressora que está disponível em minha rede isto é possível configurando a opção ColorMode como Gray usando o comando abaixo.

$>  lpoptions -d impressora -o ColorModel=Gray

A partir deste momento, suas as impressões feitas terão imagens impressas em níveis de cinza. Para garantir que a impressão saia realmente em preto e branco, eu costumo executar este comando logo antes de usar o lpr.

Para voltar a imprimir colorido use

$>  lpoptions -d impressora -o ColorModel=CMYK

Veja também:
Como deixar processos rodando sem estar logado.

Resumo de Local Binary Patterns

Local Binary Patterns (LBP) são descritores locais de textura propostos em [1] baseados na suposição de que a informação de uma textura é dividida em dois aspectos complementares: padrão e intensidade.

O LBP original considerava uma vizinhança 3x3 em torno de cada pixel e, para cada pixel, comparava-o com o pixel central e atribuía 1 para o pixel se ele é maior ou igual ao pixel central e 0 caso contrário. O código LBP de cada pixel é calculado como um número de 8 bits em que o limiar de cada pixel recebe os pesos abaixo. Por fim, é feito um histograma dos códigos LBP calculados. Este histograma representa a textura presente na imagem.

Pesos para a codificação do padrão contido em uma janela 3x3.

A formulação proposta em [2] apresenta um LBP mais geral baseado em vizinhanças circulares e com um número arbitrários de pontos.

Vizinhança circular usada no LBP genérico.

Seja I(x, y) uma imagem em níveis de cinza, g_c o nível de cinza de um ponto arbitrário (x, y) da imagem e P o número de pontos amostrados à distância R de (x, y).  Definimos os pontos g_p = I(x_p, y_p), onde

x_p = x + R cos(2πp/P),

y_p = y - R sin(2πp/P).

Os valores de I(x, y) são interpolados bilinearmente toda vez que (x, y) não estiverem no centro de um pixel.

Suponha que a textura da imagem I possa ser caracterizada pela distribuição conjunta dos P+1 pixels:

T = t(g_c, g₀, ..., g_P-1).

Sem perda de generalidade,

T = t(g_c, g₀ - g_c, ..., g_P-1 - g_c)

Suponha que o valor do ponto central gc é estatisticamente independente das diferenças, resultando em

T ≈ t(g_c)t(g₀ - g_c, ..., g_P-1 - g_c)

Desta maneira, a distribuição t(g₀ - g_c, ..., g_P-1 - g_c) pode ser usada para caracterizar o padrão da textura. Porém, estimar esta distribuição multi variada com precisão pode ser difícil. Para tornar as diferenças g_i - g_c robustas à variações nos níveis de cinza e melhorar a estimação de t, consideramos somente o sinal das diferenças. A distribuição estimada é:

t(s(g₀ - g_c), ..., s(g_P-1 - g_c))

O código LBP final é definido como

LBP_P,R(x_c, y_c) = ∑ s(g_p - g_c)2^p.

e codifica cada padrão observado como um número binário de P bits. Desta maneira, a distribuição dos padrões LBP_P,R(x_c, y_c) aproxima a textura original T

T ≈ t(LBP_P,R(x_c, y_c)).

A partir deste LBP genérico foram propostos diversas outras variantes deste métodos [3, 4]. Algumas aplicações notáveis do LBP são a segmentação não supervisionada de textura [5, 6] e a localização de faces [7].

Referências:

[1] Timo Ojala, Matti Pietikäinen, David Harwood, A comparative study of texture measures with classification based on featured distributions, Pattern Recognition, Volume 29, Issue 1, January 1996,

[2] Ojala, Timo, Matti Pietikainen, and Topi Maenpaa. "Multiresolution gray-scale and rotation invariant texture classification with local binary patterns." Pattern Analysis and Machine Intelligence, IEEE Transactions on 24.7 (2002): 971-987.

[3] Zhao, Guoying, and Matti Pietikainen. "Dynamic texture recognition using local binary patterns with an application to facial expressions." Pattern Analysis and Machine Intelligence, IEEE Transactions on 29.6 (2007): 915-928.

[4] Zhu, Chao, C-E. Bichot, and Liming Chen. "Multi-scale color local binary patterns for visual object classes recognition." Pattern Recognition (ICPR), 2010 20th International Conference on. IEEE, 2010.

 [5] Ojala, Timo, and Matti Pietikäinen. "Unsupervised texture segmentation using feature distributions." Image Analysis and Processing. Springer Berlin Heidelberg, 1997.

 [6] Ojala, Timo, and Matti Pietikäinen. "Unsupervised texture segmentation using feature distributions." Pattern Recognition 32.3 (1999): 477-486.

[7] Hadid, Abdenour, Matti Pietikainen, and Timo Ahonen. "A discriminative feature space for detecting and recognizing faces." Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on. Vol. 2. IEEE, 2004.

Resumo do artigo "The ICDAR 2013 Music Scores Competition: Staff Removal"

O artigo "The ICDAR 2013 Music Scores Competition: Staff Removal" apresenta os resultados da competição de remoção de compasso ocorrida no ICDAR 2013. Os autores descrevem o conjunto de imagens usado e os processamentos realizados para degradar as imagens para que elas se tornem similares a documentos históricos.  Também são apresentados os resultados da competição.

(Este resumo foca na descrição do conjunto de dados e nas métricas de avaliação de desempenho. Algumas informações foram retiradas do artigo "The ICDAR/GREC 2013 Music Scores Competition on Staff Removal")

O conjunto de dados utilizado na competição foi o CVC-MUSCIMA, que contém 1000 imagens de 20 partituras escritas por 50 músicos diferentes. Cada músico transcreveu as mesmas 20 páginas. Este conjunto de dados foi submetido à duas operações de degradação das imagens e as imagens são oferecidas tanto em binário como em níveis de cinza.

A primeira degradação adiciona ruído local de modo a imitar os traços de documentos antigos. São adicionados defeitos como pequenos borrões de tinta e falhas "brancas" nos traços da imagem.

A segunda deformação simula a digitalização de documentos deteriorados adicionando pequenas dobras e seções amassadas na imagem.

O conjunto de treinamento foi dividido em três partes:

1. TrainingSubset1: 1000 imagens geradas usando o modelo de distorção 3D com 2 meshes diferentes;
2. TrainingSubset2: 1000 imagens geradas com 3 níveis de ruído local;
3. TrainingSubset3: 2000 imagens geradas com combinações de distorção 3D e ruído local. Os parâmetros são os mesmos usados nos itens 1 e 2.

O conjunto de testes também foi dividido em 3 partes:

1. TestSubset1: 500 imagens geradas usando o modelo de distorção 3D com 2 meshes diferentes dos do treinamento;
2. TestSubset2: 500 imagens geradas com os mesmos 3 níveis de ruído local;
3. TestSubset3: 1000 imagens geradas com combinações de distorção 3D e ruído local. Os parâmetros são os mesmos usados nos itens 1 e 2 dos conjuntos de teste.

Os autores utilizaram 5 medidas de erro: Acurácia, Precisão, Recall, F-measure e Especificidade.

(Acurácia = taxa de erro, Precisão = TP/(TP + FP), Recall = TP/(TP + FN), Especificidade = TN/(TN + FP), F-measure= 2* (Precisão * Recall)/(Precisão + Recall) )

Os resultados de cada método podem ser vistos na tabela da última página do artigo [2].

Referências completas:

1. Visaniy, M.; Kieu, V.C.; Fornes, A.; Journet, N., "ICDAR 2013 Music Scores Competition: Staff Removal," Document Analysis and Recognition (ICDAR), 2013 12th International Conference on , vol., no., pp.1407,1411, 25-28 Aug. 2013. [Download]
2. V. Kieu, A. Fornes, M. Visani, and N. Journet, “The ICDAR/GREC 2013 Music Scores Competition on Staff Removal,” in 10th IAPR International Workshop on Graphics RECognition (GREC 2013), Bethlehem, PA, USA. [Download]

Trabalho remoto com Linux - Screen

Os sistemas baseados em Linux oferecem diversas facilidades para a criação de sessões remotas. Uma das grandes vantagens do trabalho remoto é a possibilidade de utilizar (e dividir com vários usuários) computadores com alto poder de processamento. Isto é especialmente importante na academia, pois frequentemente precisamos executar experimentos ou simulações demoradas e que demandam grande poder computacional. Neste post irei apresentar o básico sobre o screen, uma ferramenta do Linux que permite que um usuário deixe um programa rodando em uma máquina mesmo sem estar logado nela.

Primeiramente, logue por ssh em uma máquina remota de sua escolha e execute no terminal:

$> screen

O comando screen cria um novo terminal que pode ser desvinculado da sua sessão ssh. Ou seja, a sessão do screen continua aberta mesmo que você se desconecte ou que a conexão caia. Para demonstrar esta capacidade, digite o seguinte comando no terminal.

$> sleep 120; echo "Terminou"

Este comando imprimirá na tela "Terminou" após 2 minutos. Agora pressione as seguintes teclas.

(Ctrl + A) e em seguida D

Seu terminal do screen foi minimizado e você está de volta à sua sessão ssh usual. Só para deixar o exemplo mais real, se desconecte da máquina e conecte novamente.

Ao reconectar na máquina remota, precisamos indicar que desejamos retomar nossa sessão do screen. Para fazer isto use o seguinte comando:

$> screen -r

Agora estamos de volta ao terminal que abrimos anteriormente e o texto "Terminou" deverá estar escrito na tela. Note que toda vez que executamos o comando screen sem parâmetros será aberta uma nova sessão. Pessoalmente, costumo usar somente uma sessão por máquina. Podemos listar as sessões do screen usando o comando

$> screen -ls

e restaurar uma sessão específica usando

$> screen -r NOME_DO_SCREEN

Assim como uma janela do konsole ou gnome-terminal pode conter várias abas, uma sessão do screen também pode abrigar diversos terminais diferentes. Somente um terminal fica visível, mas todos estão sendo executados em paralelo. Para criar um novo terminal em seu screen aperte

(Ctrl + A) e em seguida C

Para ver quais terminais estão abertos em sua sessão use

(Ctrl + A) e em seguida W

O terminal com uma * ao lado do nome é o que está visível atualmente. Para navegar entre os terminais use

(Ctrl + A) e em seguida N

para ir para o próximo (Next) terminal e

(Ctrl + A) e em seguida P

para ir para o terminal anterior (Previous).

Estes são os principais comandos do screen para a execução de programas demorados em máquinas remotas. Deixe um comentário para qualquer dúvida ou esclarecimento. Sugestões também são benvindas.

Veja também:
Como imprimir em máquinas remotas.