Dithering — Parte II — Gerando os Pontilhados Ordenados

No artigo anterior “Dithering — Parte I — Halftone via Pontilhado Ordenado“, apresentamos uma máscara \(3 \times 3 \) que utilizamos para substituir dez tons de cinza para gerar uma imagem binária. Contudo, padrões utilizando máscaras de tamanho \(2 \times 2 \) ou de tamanhos superiores podem ser utilizados para criar um número maior de níveis de cinza.

Os padrões de máscaras com os tamanhos mencionados são ilustrados nas figuras abaixo






Devemos observar que quanto menor a máscara, menor serão a quantidade de pontos gerados por padrão. Isso terá consequência direta na qualidade da imagem binária, pois ela terá menos padrões para diferenciar os diferentes níveis de cinza da imagem original. Além disso, devemos observar que os pontos devem ser dispostos de maneira a minimizar efeitos indesejáveis na imagem resultante, por exemplo, a ocorrência de linhas horizontais ou verticais em uma parte da imagem. Outra consideração importante é que, se um pixel for preto no padrão \(i \), ele também será preto em todos os padrões \(j > i \), reduzindo a ocorrência de falsos contornos na imagem.

O uso de padrões de \(3 \times 3 \) pixels limita a resolução espacial para um terço em cada dimensão da imagem, entretanto, fornece dez níveis de cinza. Certamente, a escolha da relação entre a resolução espacial e a profundidade da imagem dependem de maior perspicácia visual e da distância da qual a imagem é observada.

Padrões maiores podem ser usados para criar um número maior de níveis de cinza. Padrões de tamanho \(n \times m \) geram \(nm + 1 \) arranjos distintos. Tal conjunto de padrões pode ser ilustrado por meios das matrizes abaixo, tal que um determinado padrão \(i \) é formado pela ativação dos elementos da matriz cujos valores são menores do que \(i \).


\( \begin{array}{| c | c | c | }
\hline
0 & 2 \\ \hline
3 & 1 \\
\hline
\end{array} \)


\( \begin{array}{| c | c | c | }
\hline
6 & 8 & 4 \\ \hline
1 & 0 & 3 \\ \hline
5 & 2 & 7 \\
\hline
\end{array} \)


\( \begin{array}{| c | c | c | }
\hline
3 & 0 & 4 \\ \hline
5 & 2 & 1 \\
\hline
\end{array} \)

Máscaras quadras maiores que três podem ser gerados a partir de matrizes de ordem \(2^n \times 2^n \), conforme a seguinte definição recursiva:


\(
D_n = \left[ \begin{array}{cc} 4 D_{n/2} + 2 U_{n/2} & 4 D_{n/2} \\ 4 D_{n/2} + U_{n/2} & D_{n/2} + U_{n/2} \\ \end{array} \right]
\hspace{80px}
n \ge 4
\)

onde \(D_2 \) é a seguinte matriz de ordem \(2 \times 2 \) :


\(
\begin{array}{| c | c | c | }
\hline
0 & 2 \\ \hline
3 & 1 \\
\hline
\end{array}
\)

e \(U_n \) é uma matriz \(n \times n\), cujos elementos são todos unitários.

Código

O código para gerar a máscara de padrões é descrito abaixo:

def generate_mask(n):
    """
    Return dot-pattern matrix of indicies for ordered dithering of 2^n order
 
    Parameters
    ----------
    * n: order of mask (must be even), integer
 
    Return
    ----------
    * mask: numpy matrix with dot patter order to generate ordered dithering
 
    Written by Pedro Garcia Freitas [sawp@sawp.com.br]
    Copyright 2011 by Pedro Garcia Freitas
 
    see: http://www.sawp.com.br
    """
    mask = array([[0, 2], [3,1]])
    mask_order = 2
    while mask_order < n:
        u = ones((mask_order, mask_order))
        m11 = 4 * mask + 2 * u
        m12 = 4 * mask
        m21 = 4 * mask + u
        m22 = mask + u
        top = concatenate((m11, m12), axis=1)
        down = concatenate((m21, m22), axis=1)
        mask = concatenate((top, down), axis=0)
        mask_order = 2 * mask_order
    return mask

Os padrões de pontos gerados pela máscara acima é implementado na função abaixo:

def generate_ordered_dithering(mask):
    """
    Return a set of ordered dithering dot patterns
 
    Parameters
    ----------
    * mask: numpy matrix with mask order
 
    Return
    ----------
    * dot_pattern: numpy matrix all dot patterns
 
    Written by Pedro Garcia Freitas [sawp @sawp.com.br]
    Copyright 2011 by Pedro Garcia Freitas
 
    see: http://www.sawp.com.br
    """
    (m, n) = mask.shape
    total = m * n - 1
    dot_pattern = [zeros((m, m))]
    for i in xrange(total):
        last = dot_pattern[i]
        new = (mask == i)
        dot_pattern.append(last + new)
    dot_pattern = array(dot_pattern)
    return dot_pattern

Para converter uma imagem em outra binária, usamos a seguinte função:

def ordered_dithering(image, masks):
    """
    Convert a grayscale image in binary halftone image with n levels.
 
    Parameters
    ----------
    * image: numpy matrix, original grayscale image
    * masks: numpy array, set with all dot patterns used in halftone
 
    Return
    ----------
    * binary: numpy matrix, dithered binary image
 
    Written by Pedro Garcia Freitas [sawp @sawp.com.br]
    Copyright 2011 by Pedro Garcia Freitas
 
    see: http://www.sawp.com.br
    """
    # create and rescale new image to fit levels
    (levels, m, n) = masks.shape
    (h, l) = image.shape
    (step_x, step_y) = masks[0].shape
    masked = (levels / 255.0) * image
    masked = ceil(masked)
    binary = zeros((m * h, n * l))
 
    # generate the halftoned image_path
    k = 0
    r = 0
    for i in xrange(h):
        for j in xrange(l):
            mask = int(masked[i, j])
            selected = masks[mask - 1]
            xs = i + k
            xf = i + k + step_x
            ys = j + r
            yf = j + r + step_y
            binary[xs:xf, ys:yf] = selected[:,:]
            r = r + step_x - 1
        r = 0
        k = k + step_y - 1
    return binary

Usamos estas funções da seguinte maneira:

# Testing
if __name__ == "__main__":
    im = imread('lena.jpg', flatten=True)
    im = imresize(im, 1.0/4.0)
    b = generate_mask(4)
    masks = generate_ordered_dithering(b)
    binary = ordered_dithering(im, masks)
    imsave('lena_binary.jpg', binary)

para obtermos o seguinte resultado:

Original
Halftoned