Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and . It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Algorisme de Floyd-Steinberg (ca)
- Floydova–Steinbergova metoda (cs)
- Floyd-Steinberg-Algorithmus (de)
- Floyd–Steinberg dithering (en)
- Algoritmo de Floyd-Steinberg (es)
- Algoritme Floyd–Steinberg (in)
- Algorithme de Floyd-Steinberg (fr)
- Algoritmo di Floyd-Steinberg (it)
- 플로이드-스타인버그 디더링 (ko)
- フロイド-スタインバーグ・ディザリング (ja)
- Algorytm Floyda-Steinberga (pl)
|
| rdfs:comment
| - L'algorisme de Floyd-Steinberg s'utilitza en processament digital d'imatges. Aquest algorisme realitza un tramat (dithering) per la difusió de l'error de quantificació d'un píxel amb els seus veïns. En concret, 7/16 del seu error, s'afegirà al píxel de la dreta, 3/16 al píxel de la part inferior esquerra, 5/16 al píxel de la part inferior i 1/16 al píxel de la part inferior dreta. (ca)
- Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and . It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors. (en)
- L'algorithme de Floyd-Steinberg est un algorithme de réduction du nombre de couleurs utilisé en traitement d'images. Cet algorithme, publié pour la première fois en 1976 par Robert W. Floyd et , effectue une diffusion de l'erreur de quantification d'un pixel à ses voisins. (fr)
- L'algoritmo di Floyd-Steinberg è un algoritmo di dithering pubblicato nel 1976 da Robert W. Floyd e . Viene usato nei programmi di manipolazione delle immagini grafiche, ad esempio quando si converte un'immagine nel formato GIF, limitata a 256 tonalità di colore. (it)
- Floydova–Steinbergova metoda distribuce chyby je algoritmus sloužící ke změně barevné charakteristiky obrazu při zachování původní vizuální informace v co největší míře a byl poprvé představen v roce 1976 Robertem W. Floydem a Louisem Steinbergem. Tento algoritmus je běžně používán k úpravě obrázků. Například při převádění do formátu GIF dojde tímto převodem k omezení maximálního počtu barev na 256. (cs)
- Der Floyd-Steinberg-Algorithmus ist ein erstmals 1976 von Robert W. Floyd und veröffentlichter Dithering-Algorithmus. In der Bildbearbeitung findet er häufig Einsatz, um die Farbtiefe eines Bildes zu verringern (zum Beispiel beim Abspeichern einer GIF-Datei) ohne dabei den ursprünglichen Farbeindruck vollständig zu verlieren. In Pseudocode formuliert: (de)
- El algoritmo de Floyd-Steinberg se utiliza en Procesamiento digital de imágenes. Este algoritmo realiza un tramado para la difusión del error de cuantificación de un píxel con sus vecinos. En concreto, 7/16 de su error, se añadirá al píxel de la derecha, 3/16 al píxeles de la parte inferior izquierda, 5/16 al píxel de la parte inferior y 1/16 al píxel de la parte inferior derecha . Por ejemplo, considérese la matriz de los valores de los píxeles siguiente: Este algoritmo puede utilizar por una simple resolución del problema del camino más corto de la Teoría de Grafos. (es)
- Algoritme Floyd–Steinberg adalah algoritme pembauran galat citra yang diperkenalkan pada tahun 1976 oleh dan . Algoritme ini sering dipakai oleh perangkat lunak penyunting gambar untuk, misalnya, menyimpan gambar dalam format GIF yang terbatas 256 warna. Algoritme ini menggunakan pembauran galat yang memindahkan sisa galat kuantisasi tiap piksel ke piksel-piksel tetangganya untuk diurus nantinya. Persebaran galatnya dilakukan menurut aturan berikut (ditampilkan dalam peta piksel). cari_warna_palet_terdekat(piksel_lama) = bulatkan(piksel_lama / 256) (in)
- 플로이드-스타인버그 디더링은 1976년 로버트 플로이드와 가 고안한 영상 디더링 알고리듬이다. 이는 영상 편집 소프트웨어에서 널리 쓰이는데, 예를 들어 최대 256색만을 지원하는 GIF 형식으로 영상을 저장하기 위해 변환할 때 쓰일 수 있다. 이 알고리듬은 픽셀의 를 주위의 픽셀로 분산시킴으로써 디더링을 수행하며, 그 분포는 다음과 같다. 알고리듬은 영상을 왼쪽에서 오른쪽, 위에서 아래로 따라가면서 각각의 픽셀을 양자화한다. 양자화 오류는 주위의 픽셀로 이전되지만, 이미 양자화된 픽셀은 영향을 받지 않는다. 또한, 픽셀의 값이 반올림 결과 내림이 된 픽셀이 많을수록 다음 픽셀은 올림이 될 가능성이 커지며, 이로써 평균적인 양자화 오류는 0에 가까워진다. 구현 중에는 홀수번째 줄과 짝수번째 줄의 디더링이 별도로 이루어지기도 하는데, 이를 가리켜 "serpentine scanning"이라 한다. 알고리듬을 의사 코드로 표현하면 다음과 같다. 예를 들어, 16비트를 8비트로 변환할 경우 find_closest_palette_color는 간단히 find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256 (ko)
- フロイド-スタインバーグ・ディザリング（Floyd–Steinberg dithering）は画像用ディザリングアルゴリズムであり、1976年、ロバート・フロイドと Louis Steinberg が発表した。画像操作関係のソフトウェアで広く用いられており、例えば最大256色までしか使えないGIF形式への変換の際に使われている。 各ピクセルの量子化誤差をそれに隣接するピクセル群に拡散させることでディザリングを実現するアルゴリズムである。隣接ピクセルへの誤差の分配は次のようになる。 星印 (*) が現在見ているピクセルを表している。 このアルゴリズムでは、画像を左から右、上から下にスキャンし、ピクセルの値を1つずつ量子化していく。毎回の量子化誤差は隣接するピクセル群に分配されるが、既に量子化が済んだピクセルの値は変更しない。これにより、あるピクセルの値が量子化によって切り下げられたら、次のピクセルにその誤差が反映されて切り上げられることになり、全体として量子化誤差がゼロに近づくことになる。 実装によっては、水平のスキャン方向を毎回逆にすることもある（蛇行式または牛耕式）。 以下に擬似コードを示す。 例えばグレースケールにおいて色深度を16ビットから8ビットにする場合、find_closest_palette_color は次のように単純な丸めをすればよい。 (ja)
- Algorytm Floyda-Steinberga – algorytm redukcji palety barwnej lub tonalnej obrazu cyfrowego, opracowany w 1975 roku. Działanie algorytmu polega na kwantyzacji wykonywanej w taki sposób, by zminimalizować banding koloru, czyli efekt prostej redukcji palety barwnej lub tonalnej, przez kontrolowane rozpraszanie (ang. dithering) pikseli o kolorach z ograniczonej palety. W grafice komputerowej jest to jeden z najbardziej popularnych algorytmów rozpraszania. (pl)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| align
| |
| alt
| - Floyd–Steinberg dithering (en)
- no dithering (en)
- original picture (en)
|
| caption
| - Floyd–Steinberg dithering (en)
- no dithering (en)
- original picture (en)
|
| image
| - Dithering example dithered web palette.png (en)
- Dithering example undithered web palette.png (en)
- Dithering example undithered.png (en)
|
| total width
| |
| has abstract
| - L'algorisme de Floyd-Steinberg s'utilitza en processament digital d'imatges. Aquest algorisme realitza un tramat (dithering) per la difusió de l'error de quantificació d'un píxel amb els seus veïns. En concret, 7/16 del seu error, s'afegirà al píxel de la dreta, 3/16 al píxel de la part inferior esquerra, 5/16 al píxel de la part inferior i 1/16 al píxel de la part inferior dreta. (ca)
- Floydova–Steinbergova metoda distribuce chyby je algoritmus sloužící ke změně barevné charakteristiky obrazu při zachování původní vizuální informace v co největší míře a byl poprvé představen v roce 1976 Robertem W. Floydem a Louisem Steinbergem. Tento algoritmus je běžně používán k úpravě obrázků. Například při převádění do formátu GIF dojde tímto převodem k omezení maximálního počtu barev na 256. Algoritmus zpracovává vstupní pixely zleva doprava, shora dolů. Při zaokrouhlení vstupní intenzity vzniká chyba, tuto chybu si algoritmus zapamatuje a použije ji k modifikaci hodnot dalších pixelů. Chyba se distribuuje pouze mezi sousedními pixely, které ještě nebyly upravovány, tzn. že se upravuje vždy následující pixel na řádku a pixely na dalším řádku. V některých případech se směr distribuce chyby mění po každém řádku "cik-cak" (zig-zag) nebo má speciální trajektorii, např. Hilbertova křivka. Dalšími způsoby distribuce chyby jsou například matice od Stuckiho, Burkese, Jarvise. (cs)
- Der Floyd-Steinberg-Algorithmus ist ein erstmals 1976 von Robert W. Floyd und veröffentlichter Dithering-Algorithmus. In der Bildbearbeitung findet er häufig Einsatz, um die Farbtiefe eines Bildes zu verringern (zum Beispiel beim Abspeichern einer GIF-Datei) ohne dabei den ursprünglichen Farbeindruck vollständig zu verlieren. Der Algorithmus arbeitet nach dem Fehlerdiffusionsverfahren (error diffusion), d. h. der bei der Quantisierung auftretende Fehler (die Differenz zwischen Ausgangswert und quantisiertem Wert) eines jeden Pixels wird nach einem festen Schema auf die umliegenden Pixel verteilt. Dadurch erreicht der Algorithmus eine bessere Detailgenauigkeit als Ordered-Dither-Verfahren mit einer starren Maske. Der Fehler jedes Pixels P wird anteilig nach dem folgenden Schema auf die umliegenden Pixel verteilt: Mit dieser Verteilung kann der Algorithmus ohne separaten Puffer die gesamte Eingabe in einem einzigen Durchlauf abarbeiten. Bereits verarbeitete Pixel werden nicht geändert, während noch abzuarbeitende Pixel entsprechend den auftretenden Quantisierungsfehlern beeinflusst werden. In Pseudocode formuliert: for each y for each x oldpixel := pixel[x][y] newpixel := find_closest_palette_color (oldpixel) pixel[x][y] := newpixel quant_error := oldpixel - newpixel pixel[x+1][y ] := pixel[x+1][y ] + quant_error * 7 / 16 pixel[x-1][y+1] := pixel[x-1][y+1] + quant_error * 3 / 16 pixel[x ][y+1] := pixel[x ][y+1] + quant_error * 5 / 16 pixel[x+1][y+1] := pixel[x+1][y+1] + quant_error * 1 / 16 Die Diffusionskoeffizienten haben die Eigenschaft, dass im Falle mehrerer Pixel, die genau in der Mitte zwischen den zwei nächstgelegenen Farben der Zielpalette liegen, ein schachbrettartiges Muster entsteht. Ein Schwarz-Weiß-Dithering einer zu 50 Prozent grauen Fläche ergäbe demnach ein richtiges Schachbrett-Muster. (de)
- Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and . It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors. (en)
- L'algorithme de Floyd-Steinberg est un algorithme de réduction du nombre de couleurs utilisé en traitement d'images. Cet algorithme, publié pour la première fois en 1976 par Robert W. Floyd et , effectue une diffusion de l'erreur de quantification d'un pixel à ses voisins. (fr)
- El algoritmo de Floyd-Steinberg se utiliza en Procesamiento digital de imágenes. Este algoritmo realiza un tramado para la difusión del error de cuantificación de un píxel con sus vecinos. En concreto, 7/16 de su error, se añadirá al píxel de la derecha, 3/16 al píxeles de la parte inferior izquierda, 5/16 al píxel de la parte inferior y 1/16 al píxel de la parte inferior derecha . Por ejemplo, considérese la matriz de los valores de los píxeles siguiente: Si el valor del centro es cuantizado a cero y el error se difunde por el algoritmo de Floyd-Steinberg, la matriz resultante será la que se muestra a continuación: Este algoritmo puede utilizar por una simple resolución del problema del camino más corto de la Teoría de Grafos. (es)
- Algoritme Floyd–Steinberg adalah algoritme pembauran galat citra yang diperkenalkan pada tahun 1976 oleh dan . Algoritme ini sering dipakai oleh perangkat lunak penyunting gambar untuk, misalnya, menyimpan gambar dalam format GIF yang terbatas 256 warna. Algoritme ini menggunakan pembauran galat yang memindahkan sisa galat kuantisasi tiap piksel ke piksel-piksel tetangganya untuk diurus nantinya. Persebaran galatnya dilakukan menurut aturan berikut (ditampilkan dalam peta piksel). Piksel yang ditandai dengan tanda bintang adalah piksel yang sedang diolah dan bagian kosong adalah piksel-piksel yang telah diolah. Algoritme ini berjalan dari kiri ke kanan, lalu dari atas ke bawah, dan melakukan kuantisasi piksel demi piksel. Galat kuantisasi disebarkan ke piksel-piksel tetangganya tanpa mengubah nilai piksel yang sudah diolah sebelumnya. Jadi, bila beberapa piksel telah dibulatkan ke bawah, semakin tinggi peluang bahwa piksel selanjutnya akan dibulatkan ke atas sehingga rata-rata galat kuantisasinya adalah nol. Koefisien pembauran tersebut memiliki sifat bahwa, bila piksel asalnya berada di tengah-tengah dua nilai terdekat, hasil pembaurannya adalah pola papan catur. Misalnya, nilai abu-abu 50% dapat dibaurkan menjadi pola papan catur hitam dan putih. Untuk pembauran yang optimal, perhitungan galat kuantisasi harus memiliki akurasi yang cukup agar tidak ada galat pembulatan yang dapat memengaruhi citra. Berikut adalah kode semu algoritme Floyd–Steinberg seperti yang telah dijelaskan sebelumnya. Kode berikut dapat berjalan untuk pengodean linear nilai piksel, seperti bilangan bulat 8 bit dan 16 bit atau bilangan riil dalam rentang [0, 1]. untuk tiap y dari atas sampai bawah, untuk tiap x dari kiri sampai kanan, piksel_lama ← piksel[x][y] piksel_baru ← cari_warna_palet_terdekat(piksel_lama) piksel[x][y] ← piksel_baru galat ← piksel_lama - piksel_baru piksel[x + 1][y ] ← piksel[x + 1][y ] + galat * 7 / 16 piksel[x - 1][y + 1] ← piksel[x - 1][y + 1] + galat * 3 / 16 piksel[x ][y + 1] ← piksel[x ][y + 1] + galat * 5 / 16 piksel[x + 1][y + 1] ← piksel[x + 1][y + 1] + galat * 1 / 16 Ketika mengubah warna dari kedalaman 16 bit ke kedalaman 8 bit, fungsi cari_warna_palet_terdekat cukup membagi dan membulatkan saja, misalnya: cari_warna_palet_terdekat(piksel_lama) = bulatkan(piksel_lama / 256) Kode semu di atas dapat menghasilkan piksel di luar rentang yang sah. Nilai tersebut sebaiknya dipangkas dalam fungsi cari_warna_palet_terdekat daripada memangkas nilai di tengah perhitungan karena bisa saja nilainya akan kembali dalam rentang. Namun, dalam bilangan bulat berlebar tetap, nilai yang di luar rentang dapat diartikan sebagai lawannya yang menyebabkan warna putih menjadi hitam sehingga harus dihindari. (in)
- 플로이드-스타인버그 디더링은 1976년 로버트 플로이드와 가 고안한 영상 디더링 알고리듬이다. 이는 영상 편집 소프트웨어에서 널리 쓰이는데, 예를 들어 최대 256색만을 지원하는 GIF 형식으로 영상을 저장하기 위해 변환할 때 쓰일 수 있다. 이 알고리듬은 픽셀의 를 주위의 픽셀로 분산시킴으로써 디더링을 수행하며, 그 분포는 다음과 같다. 알고리듬은 영상을 왼쪽에서 오른쪽, 위에서 아래로 따라가면서 각각의 픽셀을 양자화한다. 양자화 오류는 주위의 픽셀로 이전되지만, 이미 양자화된 픽셀은 영향을 받지 않는다. 또한, 픽셀의 값이 반올림 결과 내림이 된 픽셀이 많을수록 다음 픽셀은 올림이 될 가능성이 커지며, 이로써 평균적인 양자화 오류는 0에 가까워진다. 구현 중에는 홀수번째 줄과 짝수번째 줄의 디더링이 별도로 이루어지기도 하는데, 이를 가리켜 "serpentine scanning"이라 한다. 알고리듬을 의사 코드로 표현하면 다음과 같다. for each y for each x oldpixel := pixel[x][y] newpixel := find_closest_palette_color(oldpixel) pixel[x][y] := newpixel quant_error := oldpixel - newpixel pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error 양자화 계수에는 만약 원래의 픽셀 값이 이용 가능한 가장 가까운 값들의 정확히 중앙값일 경우 디더링한 결과는 체스판과 같은 패턴을 이루는 성질이 있다. 예를 들어 50% 회색 데이터를 흑백으로 변환할 경우 흑백 체스판처럼 디더링될 수 있다. 최적화된 디더링을 위해서는 양자화 오류의 계산이 반올림 오류가 결과에 영향을 주지 않을만큼 정확해야 한다. 예를 들어, 16비트를 8비트로 변환할 경우 find_closest_palette_color는 간단히 find_closest_palette_color(oldpixel) = (oldpixel + 128) / 256 로 계산될 수 있다. (ko)
- フロイド-スタインバーグ・ディザリング（Floyd–Steinberg dithering）は画像用ディザリングアルゴリズムであり、1976年、ロバート・フロイドと Louis Steinberg が発表した。画像操作関係のソフトウェアで広く用いられており、例えば最大256色までしか使えないGIF形式への変換の際に使われている。 各ピクセルの量子化誤差をそれに隣接するピクセル群に拡散させることでディザリングを実現するアルゴリズムである。隣接ピクセルへの誤差の分配は次のようになる。 星印 (*) が現在見ているピクセルを表している。 このアルゴリズムでは、画像を左から右、上から下にスキャンし、ピクセルの値を1つずつ量子化していく。毎回の量子化誤差は隣接するピクセル群に分配されるが、既に量子化が済んだピクセルの値は変更しない。これにより、あるピクセルの値が量子化によって切り下げられたら、次のピクセルにその誤差が反映されて切り上げられることになり、全体として量子化誤差がゼロに近づくことになる。 実装によっては、水平のスキャン方向を毎回逆にすることもある（蛇行式または牛耕式）。 以下に擬似コードを示す。 for each y from top to bottom for each x from left to right oldpixel := pixel[x][y] newpixel := find_closest_palette_color(oldpixel) pixel[x][y] := newpixel quant_error := oldpixel - newpixel pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error 元のピクセル値が発色可能な色と色のちょうど中間だった場合、誤差拡散係数は市松模様のようなパターンを生成するように設定されている。例えば50%の灰色は白と黒の市松模様となる。最適なディザリングにするには、丸め誤差が結果に影響することを防止するため、量子化誤差を十分な精度で求める必要がある。 例えばグレースケールにおいて色深度を16ビットから8ビットにする場合、find_closest_palette_color は次のように単純な丸めをすればよい。 find_closest_palette_color(oldpixel) = oldpixel / 256 * 256 (ja)
- L'algoritmo di Floyd-Steinberg è un algoritmo di dithering pubblicato nel 1976 da Robert W. Floyd e . Viene usato nei programmi di manipolazione delle immagini grafiche, ad esempio quando si converte un'immagine nel formato GIF, limitata a 256 tonalità di colore. (it)
- Algorytm Floyda-Steinberga – algorytm redukcji palety barwnej lub tonalnej obrazu cyfrowego, opracowany w 1975 roku. Działanie algorytmu polega na kwantyzacji wykonywanej w taki sposób, by zminimalizować banding koloru, czyli efekt prostej redukcji palety barwnej lub tonalnej, przez kontrolowane rozpraszanie (ang. dithering) pikseli o kolorach z ograniczonej palety. W grafice komputerowej jest to jeden z najbardziej popularnych algorytmów rozpraszania. Podstawą algorytmu Floyda-Steinberga jest rozpraszanie błędów wprowadzonej redukcji. Dana jest funkcja kwantyzująca, przypisująca dowolnej barwie – barwę z palety docelowej. Piksele obrazu przetwarzane są w kolejnych rzędach, od lewej do prawej. Dla każdego przetworzanego piksela obliczany jest błąd, czyli różnica między wynikiem funkcji kwantyzującej a barwą oryginalną (w przypadku obrazu monochromatycznego jest to pojedyncza liczba, dla przestrzeni RGB – trzy, dla CMYK – cztery liczby). Wartość tej różnicy jest następnie dodawana z odpowiednimi współczynnikami do wartości jeszcze nie przetworzonych pikseli sąsiadujących z danym (zwykle przyjmuje się sąsiedztwo 3×3 lub 4×4). Ponieważ suma współczynników jest równa 1, średni błąd wewnątrz sąsiedztwa dowolnego piksela jest zerowy – gdy piksel zostanie nadmiernie rozjaśniony, jego sąsiedzi zostaną przyciemnieni i odwrotnie. W praktyce błąd nigdy nie jest zerowy z powodu błędów zaokrągleń i efektów brzegowych, ale wizualnie obraz przypomina oryginał. Algorytm Floyda-Steinberga stosuje się przy dostosowywaniu obrazu do formatu zapisu lub medium o ograniczonej palecie barwnej (format GIF, niektóre drukarki atramentowe). (pl)
|
| image style
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
