Blog cộng đồng về Công nghệ thông tin

Giải thuật Floyd-Steinberg

Có nhiều giải thuật, kết quả tốt thì càng chậm. Giải thuật Floyd-Steinberg có kết quả khá tốt.

Ở đây, xin trình bày giải thuật Floyd-Steinberg. Lí do của việc chọn giải thuật này là nó hàm chứa khái niệm khuyếch tán sai số lượng tử hoá rất sâu sắc.

Sai số lượng tử hóa

Quá trình biến đổi từ tín hiệu tương tự sang tín hiệu số gọi là lượng tử hóa. Quá trình này không thể tránh sai số. Tín hiệu số là liên tục nên độ chính xác vô hạn, trong khi độ chính xác của tín hiệu số phụ thuộc vào số bit dùng để mã hóa, mà số này có giới hạn. Đối với mỗi kênh ảnh (ví dụ R hoặc G hoặc B), 8 là số bit thường được sử dụng nhất.

Như vậy, tín hiệu số chỉ là tín hiệu xấp xỉ của tín hiệu tương tự ban đầu. Hiệu của giá trị của tín hiệu tương tự ban đầu và giá trị của tín hiệu số được xấp xỉ được gọi là sai số lượng tử hóa.

Khuyếch tán sai số lượng tử hóa

Floyd là nhà khoa học máy tính cực kì nổi tiếng với giải thuật Floyd để tìm tất cả đường đi ngắn nhất trong đồ thị. Năm 1978 ông nhận giải Turing, được coi là giải Nobel của khoa học máy tính.

Năm 1976, Floyd và Steinberg công bố giải thuật Floyd-Steinberg dithering. Mấu chốt của giải thuật này là khuyếch tán sai số lượng tử hoá của một điểm nhất định sang những điểm xung quanh. Do đó, tính trung bình trên cả tấm ảnh thu được, thì sai số gần như bằng 0.

Demo

Ảnh gốc và ảnh sau khi biến đổi (để ảnh càng xa mắt, thì hiệu ứng về độ xám càng mạnh).

Chương trình dưới được viết với tiêu chí dễ hiểu, hơn là tối ưu về tốc độ.

# Create binary halftone image from a color one, using Floyd-Steinberg algorithm

require 'rubygems'
require 'RMagick'
include Magick

BLACK     = 0
WHITE     = MaxRGB
THRESHOLD = MaxRGB/2

# 2D array containing image data
$data = nil

# Convert from color to grayscale image
def input
  color = Image.read('lena.png')[0]
  $data = Array.new(color.columns)
  color.columns.times do |x|
    $data[x] = Array.new(color.rows)
    color.rows.times do |y|
      $data[x][y] = color.pixel_color(x, y).intensity
    end
  end
end

def process
  columns = $data.size
  rows    = $data[0].size

  # Top to bottom, left to right
  rows.times do |y|
    columns.times do |x|
      i1 = $data[x][y]
      i2 = (i1 < THRESHOLD)? BLACK : WHITE
      e  = i1 - i2  # Quantization error

      $data[x    ][y    ] = i2
      $data[x + 1][y    ] += 7.0/16*e if x < columns - 2
      $data[x - 1][y + 1] += 3.0/16*e if x > 0 and y < rows - 2
      $data[x    ][y + 1] += 5.0/16*e if y < rows - 2
      $data[x + 1][y + 1] += 1.0/16*e if x < columns - 2 and y < rows - 2
    end
  end
end

# Write halftone image
def output
  columns = $data.size
  rows    = $data[0].size

  halftone = Image.new(columns, rows) { self.image_type = BilevelType }
  rows.times do |y|
    columns.times do |x|
      i = $data[x][y]
      halftone.pixel_color(x, y, Pixel.new(i, i, i))
    end
  end
  halftone.write('halftone.png')
end

def main
  input
  process
  output
end
main