[arrays] 수백만 개의 픽셀을 가진 2D unboxed 픽셀 배열에 권장되는 Haskell 표현은 무엇입니까?
Haskell의 이미지 처리 문제를 해결하고 싶습니다. 저는 비트 맵 (비트 맵)과 수백만 픽셀의 컬러 이미지로 작업하고 있습니다. 몇 가지 질문이 있습니다.
-
Vector.Unboxed과 중에서 무엇을 선택해야UArray합니까? 둘 다 unboxed 배열이지만Vector추상화는 특히 루프 융합과 관련 하여 많이 광고되는 것처럼 보입니다. 가Vector항상 좋은 것은? 그렇지 않은 경우 언제 어떤 표현을 사용해야합니까? -
컬러 이미지의 경우 16 비트 정수의 트리플 또는 단 정밀도 부동 소수점 숫자의 트리플을 저장하려고합니다. 이를 위해 중 하나입니다
Vector또는UArray사용에 쉽게? 더 많은 성능? -
흑백 이미지의 경우 픽셀 당 1 비트 만 저장하면됩니다. 여러 픽셀을 한 단어로 압축하여 여기에 도움이 될 수있는 사전 정의 된 데이터 유형이 있습니까? 아니면 제가 혼자입니까?
-
마지막으로, 내 배열은 2 차원입니다. 나는 “배열의 배열”(또는 벡터의 벡터)과 같은 표현에 의해 부과 된 추가 간접적 인 것을 다룰 수 있다고 생각하지만 인덱스 매핑을 지원하는 추상화를 선호합니다. 누구든지 표준 라이브러리 나 Hackage에서 추천 할 수 있습니까?
나는 기능적 프로그래머이며 돌연변이가 필요하지 않습니다. 🙂
답변
다차원 배열의 경우 Haskell의 현재 최상의 옵션은 repa 입니다.
Repa는 고성능, 일반, 다차원, 형태 다형성 병렬 배열을 제공합니다. 모든 숫자 데이터는 박스없이 저장됩니다. Repa 결합기로 작성된 함수는 프로그램을 실행할 때 명령 줄에서 + RTS -Nwhatever를 제공하면 자동으로 병렬 처리됩니다.
최근에는 일부 이미지 처리 문제에 사용되었습니다.
repa 사용에 대한 튜토리얼을 작성하기 시작했습니다 . 이미 Haskell 배열 또는 벡터 라이브러리를 알고있는 경우 시작하기에 좋은 곳입니다. 핵심 디딤돌은 단순한 인덱스 유형 대신 모양 유형을 사용하여 다차원 인덱스 (및 심지어 스텐실)를 처리하는 것입니다.
바디 수리-IO 패키지는 더 형식에 대한 지원이 필요하지만, 읽기, .BMP 이미지 파일 작성에 대한 지원이 포함되어 있습니다.
특정 질문에 대한 설명은 다음과 같은 그래픽입니다.
Vector.Unboxed와 UArray 중에서 어떤 기준을 선택해야합니까?
기본 표현은 거의 동일하지만, 주요 차이점은 벡터 작업을위한 API의 폭입니다. 일반적으로 목록과 연결하는 거의 모든 작업 (융합 기반 최적화 프레임 워크 사용)을 UArray가지고 있지만 거의 API가 없습니다.
컬러 이미지의 경우 16 비트 정수의 트리플 또는 단 정밀도 부동 소수점 숫자의 트리플을 저장하려고합니다.
UArray인덱싱에 임의의 데이터 유형을 사용할 수 있으므로 다차원 데이터를 더 잘 지원합니다. 이 가능하지만 Vector(인스턴스 작성하여 UA당신의 요소 유형을), 그것은의 기본 목표는 아니다 Vector– 대신,이 곳에 Repa효율적으로 저장 사용하여 사용자 정의 데이터 유형에 매우 쉽게 그것을 만드는 단계, 모양 인덱싱 덕분 입니다.
에서 Repa트리플 반바지의 유형은 다음과 같습니다.
Array DIM3 Word16즉, Word16의 3D 배열입니다.
흑백 이미지의 경우 픽셀 당 1 비트 만 저장하면됩니다.
UArrays는 Bool을 비트로 압축하고, Vector는 대신 비트 패킹을 수행하는 Bool 인스턴스를 사용합니다 Word8. 그러나 벡터에 대한 비트 패킹 구현을 작성하는 것은 쉽습니다. 여기 에 (구식) uvector 라이브러리에서 하나가 있습니다. 내부적으로는를 Repa사용 Vectors하므로 라이브러리 표현 선택을 상속한다고 생각합니다.
여러 픽셀을 단어로 압축하여 여기에 도움이 될 수있는 사전 정의 된 데이터 유형이 있습니까?
다양한 단어 유형에 대해 모든 라이브러리에 대해 기존 인스턴스를 사용할 수 있지만 패킹 된 데이터를 롤링 및 언 롤링하려면 Data.Bits를 사용하여 몇 가지 도우미를 작성해야 할 수도 있습니다.
마지막으로, 내 배열은 2 차원입니다.
UArray 및 Repa는 효율적인 다차원 배열을 지원합니다. Repa에는이를위한 풍부한 인터페이스도 있습니다. 벡터 자체는 그렇지 않습니다.
주목할만한 언급 :
- hmatrix , 선형 대수 패키지에 대한 광범위한 바인딩이있는 사용자 지정 배열 유형입니다.
vector또는repa유형 을 사용하도록 바인딩되어야합니다 . - ix-shapeable , 일반 배열에서보다 유연한 색인 생성
- 2D 이미지 조작을위한 Andy Gill의 라이브러리 인 칠판
- codec-image-devil , UArray에 다양한 이미지 형식 읽기 및 쓰기
답변
나에게 중요한 Haskell 배열 라이브러리의 기능을 검토하고 비교 테이블을 컴파일 했습니다 (스프레드 시트 만 : direct link ). 그래서 나는 대답하려고 노력할 것입니다.
Vector.Unboxed와 UArray 중에서 어떤 기준을 선택해야합니까? 둘 다 unboxed 배열이지만 벡터 추상화는 특히 루프 융합과 관련하여 많이 광고되는 것처럼 보입니다. Vector는 항상 더 나은가요? 그렇지 않은 경우 언제 어떤 표현을 사용해야합니까?
2 차원 또는 다차원 배열이 필요한 경우 UArray가 Vector보다 선호 될 수 있습니다. 그러나 Vector는 벡터를 조작하기위한 더 좋은 API를 가지고 있습니다. 일반적으로 Vector는 다차원 배열을 시뮬레이션하는 데 적합하지 않습니다.
Vector.Unboxed는 병렬 전략과 함께 사용할 수 없습니다. 나는 UArray를 둘 다 사용할 수 없다고 생각하지만, 적어도 UArray에서 boxed Array로 전환하고 병렬화가 boxing 비용을 능가하는 이점이 있는지 확인하는 것은 매우 쉽습니다.
컬러 이미지의 경우 16 비트 정수의 트리플 또는 단 정밀도 부동 소수점 숫자의 트리플을 저장하려고합니다. 이를 위해 Vector 또는 UArray가 사용하기 더 쉬울까요? 더 많은 성능?
이미지를 표현하기 위해 배열을 사용해 보았습니다 (그레이 스케일 이미지 만 필요했지만). 컬러 이미지의 경우 Codec-Image-DevIL 라이브러리를 사용하여 이미지를 읽고 / 씁니다 (DevIL 라이브러리에 바인딩), 회색조 이미지의 경우 pgm 라이브러리 (순수 Haskell)를 사용했습니다.
Array의 주요 문제는 랜덤 액세스 스토리지 만 제공한다는 것이지만, Array 알고리즘을 구축하는 많은 수단을 제공하지 않으며 배열 루틴 라이브러리를 사용할 준비가되어 있지도 않습니다 (선형 대수 라이브러리와 인터페이스하지 않고 컨볼 루션, fft 및 기타 변환을 표현할 수 없습니다).
기존 배열에서 새 배열을 만들어야 할 때마다 중간 값 목록 을 구성해야합니다 (예 : Gentle Introduction의 행렬 곱셈 에서). 배열 구성 비용은 종종 내 사용 사례 중 일부에서 목록 기반 표현이 더 빠르다는 점까지 더 빠른 임의 액세스의 이점보다 중요합니다.
STUArray가 도움이 될 수 있었지만 STUArray를 사용하여 다형성 코드 를 작성하는 데 필요한 수수께끼 유형 오류 및 노력과 싸우는 것을 좋아하지 않았습니다 .
따라서 배열의 문제는 수치 계산에 적합하지 않다는 것입니다. Hmatrix의 Data.Packed.Vector 및 Data.Packed.Matrix는 솔리드 매트릭스 라이브러리 (주의 : GPL 라이센스)와 함께 제공되기 때문에이 점에서 더 좋습니다. 성능면에서 행렬 곱셈에서 hmatrix는 충분히 빠르지 만 ( Octave보다 약간 느리지 만 ) 메모리가 많이 소모되었습니다 (Python / SciPy보다 몇 배 더 많이 소비 됨).
매트릭스에 대한 blas 라이브러리도 있지만 GHC7을 기반으로 빌드되지 않습니다.
나는 아직 Repa에 대한 경험이 많지 않았고 repa 코드를 잘 이해하지 못합니다. 내가보기에는 그 위에 작성된 행렬 및 배열 알고리즘을 사용할 준비가 된 매우 제한된 범위가 있지만 적어도 라이브러리를 통해 중요한 알고리즘을 표현할 수 있습니다. 예를 들어, 행렬 곱셈과 repa- 알고리즘의 컨볼 루션 에 대한 루틴이 이미 있습니다 . 불행히도 컨볼 루션은 이제 7×7 커널로 제한되는 것 같습니다 (나에게는 충분하지 않지만 많은 용도로 충분할 것입니다).
Haskell OpenCV 바인딩을 시도하지 않았습니다. OpenCV는 정말 빠르기 때문에 빠르지 만 바인딩이 완전하고 사용할 수있을만큼 좋은지 확실하지 않습니다. 또한 OpenCV는 본질적으로 매우 필수적이고 파괴적인 업데이트로 가득합니다. 그 위에 멋지고 효율적인 기능적 인터페이스를 디자인하는 것은 어렵다고 생각합니다. OpenCV 방식으로 가면 그는 모든 곳에서 OpenCV 이미지 표현을 사용하고 OpenCV 루틴을 사용하여 조작 할 수 있습니다.
흑백 이미지의 경우 픽셀 당 1 비트 만 저장하면됩니다. 여러 픽셀을 한 단어로 압축하여 여기에 도움이 될 수있는 사전 정의 된 데이터 유형이 있습니까? 아니면 제가 혼자입니까?
내가 아는 한 Unboxed Bool 배열은 비트 벡터 압축 및 압축 해제 를 처리합니다. 다른 라이브러리에서 Bool 배열의 구현을 살펴본 것을 기억하고 다른 곳에서는 이것을 보지 못했습니다.
마지막으로, 내 배열은 2 차원입니다. 나는 “배열의 배열”(또는 벡터의 벡터)과 같은 표현에 의해 부과 된 추가 간접적 인 것을 다룰 수 있다고 생각하지만 인덱스 매핑을 지원하는 추상화를 선호합니다. 누구든지 표준 라이브러리 나 Hackage에서 추천 할 수 있습니까?
벡터 (및 단순 목록) 외에도 다른 모든 배열 라이브러리는 2 차원 배열 또는 행렬을 나타낼 수 있습니다. 나는 그들이 불필요한 간접적 인 방향을 피한다고 생각합니다.
답변
이것은 귀하의 질문에 정확히 대답하지 않으며 실제로 는 하스켈도 아니지만 hackage 에서 CV 또는 CV-combinators 라이브러리를 살펴 보는 것이 좋습니다 . 그들은 opencv 라이브러리의 많은 유용한 이미지 처리 및 비전 연산자를 바인딩하고 머신 비전 문제를 훨씬 빠르게 처리합니다.
누군가가 repa 또는 그러한 배열 라이브러리를 opencv와 함께 직접 사용할 수있는 방법을 알아 내면 오히려 좋을 것입니다.
답변
문제의 모든 작업 등을 처리 할 수 있는 새로운 Haskell 이미지 처리 라이브러리 가 있습니다. 현재는 기본 표현에 Repa 및 Vector 패키지를 사용 하며 결과적으로 융합, 병렬 계산, 돌연변이 및 해당 라이브러리와 함께 제공되는 대부분의 다른 장점을 상속합니다. 이미지 조작에 자연스러운 인터페이스를 제공합니다.
- 임의 정밀도 2D 인덱싱와 박싱 화소 (
Double,Float,Word16, 등 ..) - 모든 필수 기능이 좋아
map,fold,zipWith,traverse… - RGB, HSI, 그레이 스케일, Bi-tonal, Complex 등 다양한 색 공간 지원
- 일반적인 이미지 처리 기능 :
- 이진 형태
- 회선
- 보간
- 푸리에 변환
- 히스토그램 플로팅
- 기타
- 픽셀과 이미지를 일반 숫자로 처리하는 기능.
- JuicyPixels 라이브러리를 통해 일반적인 이미지 형식 읽기 및 쓰기
가장 중요한 것은 순수한 Haskell 라이브러리이므로 외부 프로그램에 의존하지 않습니다. 또한 확장 성이 뛰어나고 새로운 색상 공간과 이미지 표현을 도입 할 수 있습니다.
그것은 여러 바이너리 픽셀을 포장한다하지 않는 것은 Word, 대신은을 사용 Word어쩌면 미래에 바이너리 픽셀 당 …
