플로이드-스타인버그 디더링
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
플로이드-스타인버그 디더링은 오차 확산을 사용하여 이미지를 디더링하는 알고리즘이다. 이 알고리즘은 픽셀의 양자화 오차를 인접 픽셀로 분산시켜 시각적인 아티팩트를 줄인다. 이미지를 위에서 아래로, 왼쪽에서 오른쪽으로 스캔하며 각 픽셀 값을 양자화하고, 오차를 특정 비율로 주변 픽셀에 더하는 방식으로 작동한다. 일부 구현에서는 스캔 방향을 번갈아 가며 바꾸는 사행 스캔 방식을 사용하기도 한다.
더 읽어볼만한 페이지
- 컴퓨터 그래픽스 알고리즘 - 알파 합성
알파 합성은 이미지의 투명도를 표현하고 합성하는 기술로, 알파 채널을 사용하여 투명도 정보를 저장하고 스트레이트 알파와 프리멀티플라이드 알파 방식으로 이미지를 합성하며, PNG, TIFF, GIF 등 다양한 이미지 형식이 이를 지원한다. - 컴퓨터 그래픽스 알고리즘 - 클리어타입
클리어타입은 마이크로소프트에서 개발한 서브픽셀 렌더링 기술로, LCD와 같은 평판 모니터에서 텍스트 가독성을 향상시키기 위해 픽셀을 구성하는 서브픽셀을 개별적으로 제어하여 글꼴의 앤티에일리어싱 효과를 개선하고 텍스트를 더 부드럽게 보이도록 하는 기술이다.
| 플로이드-스타인버그 디더링 | |
|---|---|
| 개요 | |
 | |
| 알고리즘 종류 | 이미지 디더링 알고리즘 |
| 개발자 | 로버트 플로이드와 스탠버그 |
| 발표 연도 | 1976년 |
| |
| |
| 동작 방식 | |
| 주요 아이디어 | 양자화 오류를 이웃 픽셀로 분산시켜 시각적 아티팩트를 줄임 |
| 오류 확산 방식 | 주변 픽셀에 오류 값을 분산시키는 방식으로 작동 |
| 확산 가중치 | 오른쪽 픽셀: 7/16 아래쪽 왼쪽 픽셀: 3/16 아래쪽 픽셀: 5/16 아래쪽 오른쪽 픽셀: 1/16 |
| 처리 순서 | 래스터 스캔 순서 (왼쪽에서 오른쪽, 위에서 아래) |
| 장점 | 비교적 간단하고 효과적인 알고리즘 |
| 단점 | 오류 확산으로 인해 이미지에 시각적 노이즈가 발생할 수 있음 |
| 활용 분야 | |
| 일반적인 용도 | 이미지 압축 컴퓨터 그래픽스 디지털 이미지 처리 |
| 추가 정보 | |
| 다른 디더링 알고리즘 | 줄리안 보스크 디더링 최소 평균 오류 디더링 주문 디더링 |
2. 알고리즘 구현
플로이드-스타인버그 알고리즘은 오차 확산을 통해 디더링을 수행한다. 이 방식은 양자화 과정에서 발생하는 오차를 주변 픽셀로 분산시켜 전체 이미지의 시각적 품질을 높인다.
확산 계수는 원래 픽셀 값이 가장 가까운 사용 가능한 색상 사이의 중간 지점인 경우, 디더링된 결과가 체커보드 패턴이 되는 특징을 갖는다. 예를 들어, 50% 회색 데이터는 흑백 체커보드 패턴으로 디더링될 수 있다. 최적의 디더링을 위해서는 양자화 오차 계산이 결과를 왜곡하는 반올림 오류를 방지할 수 있을 정도로 충분한 정확도를 가져야 한다.
올바른 결과를 위해서는 컴퓨터에 저장된 이미지에 흔히 사용되는 sRGB 값을 직접 조작하는 대신 먼저 모든 값을 선형화해야 한다.
2. 1. 오차 확산 방식
플로이드-스타인버그 디더링은 오차 확산을 사용하여 현재 픽셀의 양자화 오차를 주변 픽셀로 분산시키는 방식으로 작동한다. 이 오차는 특정 비율에 따라 주변 픽셀로 더해지며, 이 비율은 다음과 같은 행렬로 표현된다.여기서 *는 현재 처리 중인 픽셀을 나타내며, 빈 픽셀은 이전에 처리된 픽셀이다. 알고리즘은 이미지를 위에서 아래로, 왼쪽에서 오른쪽으로 스캔하며 각 픽셀의 값을 양자화한다. 이때 발생하는 양자화 오차는 이미 양자화된 픽셀에는 영향을 주지 않고, 아직 처리되지 않은 주변 픽셀로 전송된다.
예를 들어, 여러 픽셀이 연속적으로 아래로 반올림된 경우, 다음 픽셀은 위로 반올림될 확률이 높아져 평균적인 양자화 오차는 0에 가까워진다.
확산 계수는 원래 픽셀 값이 사용 가능한 색상 사이의 중간값일 때, 디더링 결과가 체커보드 패턴을 나타내는 특징을 갖는다. 예를 들어, 50% 회색은 흑백 체커보드 패턴으로 디더링될 수 있다. 최적의 디더링 결과를 얻으려면 양자화 오차 계산 시 반올림 오류를 방지할 수 있도록 충분한 정확도를 확보해야 한다.
일부 구현에서는 스캔 방향이 가로 라인마다 번갈아 바뀌는 "사행 스캔" 또는 사행 변환 디더링 방식을 사용하기도 한다.
2. 2. 스캔 방향
이 알고리즘은 이미지를 위에서 아래로, 왼쪽에서 오른쪽으로 스캔하며 픽셀 값을 하나씩 양자화한다. 매번 양자화 오차는 이미 양자화된 픽셀에는 영향을 미치지 않으면서 인접 픽셀로 전송된다. 따라서 여러 픽셀이 아래로 반올림된 경우, 다음 픽셀이 위로 반올림될 가능성이 높아 평균적으로 양자화 오차가 0에 가깝게 된다.일부 구현에서는 스캔의 가로 방향이 라인 간에 번갈아 가며, 이를 "사행 스캔" 또는 사행 변환 디더링이라고 한다.
2. 3. 사행 스캔 (선택 사항)
일부 구현에서는 스캔의 가로 방향을 라인 간에 번갈아 가며 진행하는 "사행 스캔" 또는 사행 변환 디더링이라고 하는 방식을 사용하기도 한다.2. 4. 의사 코드
이 알고리즘은 오차 확산을 사용하여 디더링을 수행한다. 이는 잔여 양자화 오차를 픽셀의 인접 픽셀에 더하여 나중에 처리하도록 하는 방식이다. 오차는 다음과 같은 분포로 분산된다.| * | 7/16 | … | ||
| … | 3/16 | 5/16 | 1/16 | … |
별표(*)로 표시된 픽셀은 현재 스캔 중인 픽셀을 나타내며, 빈 픽셀은 이전에 스캔된 픽셀이다. 이 알고리즘은 이미지를 위에서 아래로, 왼쪽에서 오른쪽으로 스캔하며 픽셀 값을 하나씩 양자화한다. 매번 양자화 오차는 이미 양자화된 픽셀에는 영향을 미치지 않으면서 인접 픽셀로 전송된다. 따라서 여러 픽셀이 아래로 반올림된 경우, 다음 픽셀이 위로 반올림될 가능성이 높아져 평균적으로 양자화 오차가 0에 가깝게 된다.
확산 계수는 원래 픽셀 값이 가장 가까운 사용 가능한 색상 사이의 중간 지점인 경우 디더링된 결과가 체커보드 패턴이 되는 속성을 갖는다. 예를 들어 50% 회색 데이터는 흑백 체커보드 패턴으로 디더링될 수 있다. 최적의 디더링을 위해서는 양자화 오차 계산이 결과를 왜곡하는 반올림 오류를 방지할 수 있을 정도로 충분한 정확도를 가져야 한다.
올바른 결과를 얻으려면, 컴퓨터에 저장된 이미지에 흔히 사용되는 sRGB 값을 직접 조작하는 대신 먼저 모든 값을 선형화해야 한다.
일부 구현에서는 스캔의 가로 방향이 라인 간에 번갈아 가며, 이를 "사행 스캔" 또는 사행 변환 디더링이라고 한다.
위에 설명된 알고리즘은 다음 의사 코드에 나와 있다. 이는 8비트 정수, 16비트 정수 또는 [0, 1] 범위의 실수와 같은 픽셀 값의 대략적인 선형 인코딩에 적용된다.
:'''각''' ''y''를 위에서 아래로 '''반복'''
:'''각''' ''x''를 왼쪽에서 오른쪽으로 '''반복'''
::oldpixel := pixels[''x''][''y'']
::newpixel := find_closest_palette_color(oldpixel)
::pixels[''x''][''y''] := newpixel
::quant_error := oldpixel - newpixel
::pixels[''x'' + 1][''y''] := pixels[''x'' + 1][''y''] + quant_error × 7/16
::pixels[''x'' - 1][''y'' + 1] := pixels[''x'' - 1][''y'' + 1] + quant_error × 3/16
::pixels[''x''][''y'' + 1] := pixels[''x''][''y'' + 1] + quant_error × 5/16
::pixels[''x'' + 1][''y'' + 1] := pixels[''x'' + 1][''y'' + 1] + quant_error × 1/16
회색조 픽셀 값을 높은 비트 심도에서 낮은 비트 심도로 변환할 때 (예: 8비트 회색조를 1비트 흑백으로 변환할 때) `find_closest_palette_color()`는 간단한 반올림을 수행할 수 있다. 예를 들어 다음과 같다.
:find_closest_palette_color(oldpixel) = round(oldpixel / 255)
의사 코드는 픽셀 값이 유효한 값을 초과하도록 할 수 있다(예: 8비트 회색조 이미지에서 255보다 큼). 이러한 값은 중간 값을 클리핑하는 대신 `find_closest_palette_color()` 함수에서 처리해야 한다. 왜냐하면 후속 오류로 인해 값이 다시 범위 내로 들어올 수 있기 때문이다. 그러나 고정 폭 정수를 사용하는 경우 중간 값의 래핑으로 인해 흑백이 반전되므로 이를 방지해야 한다.
2. 5. 색상 변환
`find_closest_palette_color()` 함수는 원래 픽셀 값에 가장 가까운 팔레트 색상을 찾는 역할을 한다. 예를 들어, 8비트 그레이스케일을 1비트 흑백으로 변환하는 경우, 다음과 같이 간단한 반올림 연산을 사용할 수 있다.```
find_closest_palette_color(oldpixel) = round(oldpixel / 255)
```
의사 코드에서 픽셀 값이 유효한 값(예: 8비트 회색조 이미지에서 255)을 초과할 수 있다. 이러한 값은 중간 값을 클리핑하는 대신 `find_closest_palette_color()` 함수에서 처리해야 한다. 후속 오류로 인해 값이 다시 범위 내로 들어올 수 있기 때문이다. 하지만 고정 폭 정수를 사용하는 경우 중간 값의 래핑으로 인해 흑백이 반전될 수 있으므로 주의해야 한다.
`find_closest_palette_color()` 구현은 팔레트가 균등하게 분산되지 않은 경우 간단하지 않지만, 올바른 팔레트 색상을 선택하는 데 약간의 부정확성은 오차가 향후 픽셀로 전파되기 때문에 시각적 영향이 최소화된다. 최근접 이웃 검색을 3D로 자주 사용한다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com