Qual representação Haskell é recomendada para arrays de pixels 2D não encaixotados com milhões de pixels?

Quero resolver alguns problemas de processamento de imagem em Haskell. Estou trabalhando com imagens bitonais (bitmap) e coloridas com milhões de pixels. Eu tenho uma série de perguntas:

1. Em que base devo escolher entre Vector.Unboxede UArray? Ambos são arrays unboxed, mas a Vectorabstração parece muito anunciada, principalmente em torno da fusão de loops. É Vectorsempre melhor? Se não, quando devo usar qual representação?

2. Para imagens coloridas, desejarei armazenar triplos de números inteiros de 16 bits ou triplos de números de ponto flutuante de precisão única. Para isso, é Vectorou UArraymais fácil de usar? Mais desempenho?

3. Para imagens bitonais, terei de armazenar apenas 1 bit por pixel. Existe um tipo de dados predefinido que pode me ajudar aqui, reunindo vários pixels em uma palavra, ou estou sozinho?

4. Finalmente, meus arrays são bidimensionais. Suponho que poderia lidar com a indireção extra imposta por uma representação como "matriz de matrizes" (ou vetor de vetores), mas prefiro uma abstração que tenha suporte para mapeamento de índice. Alguém pode recomendar algo de uma biblioteca padrão ou do Hackage?

Sou um programador funcional e não necessito de mutação :-)

Para matrizes multidimensionais, a melhor opção atual em Haskell, na minha opinião, é o repa .

Repa fornece matrizes paralelas polimórficas de forma polimórfica de alto desempenho, regulares, multidimensionais. Todos os dados numéricos são armazenados fora da caixa. As funções escritas com os combinadores Repa são paralelas automaticamente, desde que você forneça + RTS - qualquer coisa na linha de comando ao executar o programa.

Recentemente, ele tem sido usado para alguns problemas de processamento de imagem:

• Detecção de borda em tempo real
• Convolução de estêncil paralela eficiente em Haskell

Comecei a escrever um tutorial sobre o uso de repa , que é um bom lugar para começar se você já conhece os arrays Haskell ou a biblioteca vetorial. O principal ponto de partida é o uso de tipos de forma em vez de tipos de índice simples, para lidar com índices multidimensionais (e até mesmo estênceis).

O pacote repa-io inclui suporte para leitura e gravação de arquivos de imagem .bmp, embora seja necessário suporte para mais formatos.

Abordando suas questões específicas, aqui está um gráfico, com discussão:

Com base em que devo escolher entre Vector.Unboxed e UArray?

Eles têm aproximadamente a mesma representação subjacente, no entanto, a principal diferença é a amplitude da API para trabalhar com vetores: eles têm quase todas as operações que você normalmente associa a listas (com uma estrutura de otimização orientada por fusão), embora UArraytenham quase sem API.

Para imagens coloridas, desejarei armazenar triplos de números inteiros de 16 bits ou triplos de números de ponto flutuante de precisão única.

UArraytem melhor suporte para dados multidimensionais, pois pode usar tipos de dados arbitrários para indexação. Embora isso seja possível Vector(escrevendo uma instância de UApara o seu tipo de elemento), não é o objetivo principal de Vector- em vez disso, é aqui que Repaentra, tornando muito fácil usar tipos de dados personalizados armazenados de maneira eficiente, graças ao indexação forma .

Em Repa, seu triplo de shorts teria o tipo:

Array DIM3 Word16

Ou seja, uma matriz 3D de Word16s.

Para imagens bitonais, terei de armazenar apenas 1 bit por pixel.

UArrays empacota Bools como bits, Vector usa a instância de Bool que faz o empacotamento de bits, em vez de usar uma representação baseada em Word8. No entanto, é fácil escrever uma implementação de empacotamento de bits para vetores - aqui está uma , da (obsoleta) biblioteca uvector. Por baixo do capô, Repausa Vectors, então acho que herda as escolhas de representação das bibliotecas.

Existe um tipo de dados predefinido que pode me ajudar aqui, reunindo vários pixels em uma palavra

Você pode usar as instâncias existentes para qualquer uma das bibliotecas, para diferentes tipos de palavras, mas pode ser necessário escrever alguns auxiliares usando Data.Bits para rolar e desenrolar dados compactados.

Finalmente, meus arrays são bidimensionais

UArray e Repa oferecem suporte a matrizes multidimensionais eficientes. Repa também possui uma interface rica para fazer isso. O vetor por si só não.

Menções notáveis:

• hmatrix , um tipo de array personalizado com ligações extensivas a pacotes de álgebra linear. Deve ser obrigado a usar os tipos vectorou repa.
• ix-shapeable , obtendo indexação mais flexível a partir de matrizes regulares
• quadro-negro , biblioteca de Andy Gill para manipulação de imagens 2D
• codec-image-devil , lê e escreve vários formatos de imagem para UArray

Uma vez eu revisei os recursos das bibliotecas de array Haskell que são importantes para mim e compilei uma tabela de comparação (apenas planilha: link direto ). Vou tentar responder.

Com base em que devo escolher entre Vector.Unboxed e UArray? Ambos são arrays unboxed, mas a abstração Vector parece muito anunciada, principalmente em torno da fusão de loops. O Vector é sempre melhor? Se não, quando devo usar qual representação?

UArray pode ser preferido em vez de Vector se for necessário arrays bidimensionais ou multidimensionais. Mas o Vector tem uma API melhor para manipular, bem, vetores. Em geral, o Vector não é adequado para simular matrizes multidimensionais.

Vector.Unboxed não pode ser usado com estratégias paralelas. Suspeito que o UArray também não possa ser usado, mas pelo menos é muito fácil alternar do UArray para o Array encaixotado e ver se os benefícios da paralelização superam os custos de encaixotamento.

Para imagens coloridas, desejarei armazenar triplos de números inteiros de 16 bits ou triplos de números de ponto flutuante de precisão única. Para este propósito, o Vector ou o UArray são mais fáceis de usar? Mais desempenho?

Tentei usar Arrays para representar imagens (embora precisasse apenas de imagens em tons de cinza). Para imagens coloridas, usei a biblioteca Codec-Image-DevIL para ler / gravar imagens (vinculações à biblioteca DevIL), para imagens em tons de cinza usei a biblioteca pgm (Haskell puro).

Meu maior problema com Array é que ele fornece apenas armazenamento de acesso aleatório, mas não fornece muitos meios de construir algoritmos de Array nem vem com bibliotecas prontas para usar de rotinas de array (não faz interface com bibliotecas de álgebra linear, não permite expressar convoluções, fft e outras transformações).

Quase toda vez que um novo Array deve ser construído a partir do existente, uma lista intermediária de valores deve ser construída (como na multiplicação de matrizes da Introdução Suave). O custo da construção do array geralmente supera os benefícios do acesso aleatório mais rápido, a ponto de uma representação baseada em lista ser mais rápida em alguns dos meus casos de uso.

STUArray poderia ter me ajudado, mas eu não gosto de lutar com erros de tipo enigmático e os esforços necessários para escrever código polimórfico com STUArray .

Portanto, o problema com os Arrays é que eles não são adequados para cálculos numéricos. Data.Packed.Vector e Data.Packed.Matrix da Hmatrix são melhores nesse aspecto, pois vêm acompanhados de uma biblioteca de matriz sólida (atenção: licença GPL). Em termos de desempenho, na multiplicação de matrizes, hmatrix era suficientemente rápido ( apenas um pouco mais lento que o Octave ), mas com muita fome de memória (consumia várias vezes mais que Python / SciPy).

Também existe uma biblioteca blas para matrizes, mas não se baseia no GHC7.

Ainda não tinha muita experiência com Repa e não entendo bem o código de repa. Pelo que vejo, ele tem uma gama muito limitada de algoritmos de matriz e array prontos para uso escritos em cima dele, mas pelo menos é possível expressar algoritmos importantes por meio da biblioteca. Por exemplo, já existem rotinas para multiplicação de matrizes e para convolução em algoritmos de reposição. Infelizmente, parece que a convolução agora está limitada a kernels 7 × 7 (não é o suficiente para mim, mas deve bastar para muitos usos).

Eu não tentei ligações Haskell OpenCV. Eles devem ser rápidos, porque o OpenCV é muito rápido, mas não tenho certeza se as ligações são completas e boas o suficiente para serem utilizadas. Além disso, o OpenCV por sua natureza é muito importante, cheio de atualizações destrutivas. Suponho que seja difícil projetar uma interface funcional agradável e eficiente em cima disso. Se alguém seguir o caminho do OpenCV, provavelmente usará a representação da imagem OpenCV em todos os lugares e usará as rotinas OpenCV para manipulá-las.

Para imagens bitonais, terei de armazenar apenas 1 bit por pixel. Existe um tipo de dados predefinido que pode me ajudar aqui, reunindo vários pixels em uma palavra, ou estou sozinho?

Até onde eu sei, os arrays não encaixotados de Bools cuidam de empacotar e descompactar vetores de bits. Lembro-me de olhar para a implementação de matrizes de Bools em outras bibliotecas e não vi isso em outro lugar.

Finalmente, meus arrays são bidimensionais. Suponho que poderia lidar com a indireção extra imposta por uma representação como "matriz de matrizes" (ou vetor de vetores), mas prefiro uma abstração que tenha suporte para mapeamento de índice. Alguém pode recomendar algo de uma biblioteca padrão ou do Hackage?

Além de Vector (e listas simples), todas as outras bibliotecas de array são capazes de representar arrays ou matrizes bidimensionais. Suponho que evitem vias indiretas desnecessárias.

Embora isso não responda exatamente à sua pergunta e nem seja um haskell como tal, eu recomendaria dar uma olhada nas bibliotecas de CV ou combinadores de CV no hackage. Eles vinculam os muitos operadores de processamento de imagem e visão bastante úteis da biblioteca opencv e tornam o trabalho com problemas de visão de máquina muito mais rápido.

Seria ótimo se alguém descobrisse como o repa ou alguma biblioteca de array poderia ser usada diretamente com o opencv.

Aqui está uma nova biblioteca de processamento de imagens Haskell que pode lidar com todas as tarefas em questão e muito mais. Atualmente ele usa os pacotes Repa e Vector para representações subjacentes, que consequentemente herdam fusão, computação paralela, mutação e a maioria dos outros itens que vêm com essas bibliotecas. Ele fornece uma interface fácil de usar que é natural para manipulação de imagens:

• 2D indexação e desembalados pixels com precisão arbitrária ( Double, Float, Word16, etc ..)
• todas as funções essenciais, como map, fold, zipWith, traverse...
• suporte para vários espaços de cores: RGB, HSI, escala de cinza, Bi-tonal, Complex, etc.
• funcionalidade de processamento de imagem comum:
  • Morfologia binária
  • Convolução
  • Interpolação
  • transformada de Fourier
  • Plotagem de histograma
  • etc.
• Capacidade de tratar pixels e imagens como números regulares.
• Ler e escrever formatos de imagem comuns por meio da biblioteca JuicyPixels

Mais importante ainda, é uma biblioteca Haskell pura, portanto, não depende de nenhum programa externo. Também é altamente extensível, novos espaços de cores e representações de imagem podem ser introduzidos.

Uma coisa que ele não faz é empacotar vários pixels binários em um Word; em vez disso, usa um Wordpor pixel binário, talvez no futuro ...