■http://anond.hatelabo.jp/20081006220009

YourFileHostのCAPTCHA画像をなんとかするの続き。

その後、適当にいじったら、手元環境で1枚あたり25秒くらい→だいたい2.5秒くらいで判別できるようになった。このくらいなら使えるかな。

速度向上に一番効いたのは、Token#importで画像を比較しているところの修正。他は細かい手直し。

使い方は前のやつと変わってません。

あと、テストに100枚くらいCAPTCHA画像食わせてみたけど、とりあえず全部正しく判定できた。

動作確認用のスクリプト (run.rb)

カレントディレクトリ以下にある*.gifなCAPTCHA画像ファイルを適当に判別するスクリプト。動作確認用にどうぞ。

後述のdecaptcha.rbと同じディレクトリに適当に置いてchmod +xしてね。

#!/usr/local/bin/ruby
$LOAD_PATH << File::dirname(File::expand_path($0))
require 'decaptcha'

STDOUT.sync = true

Dir.glob('*.gif').sort.each do |file|
  correct = File::basename(file, '.*')
  puts "Processing file: #{file}"
  start_time = Time.now
  ret = DeCAPTCHA.decode(file)
  elapsed = Time.now - start_time

  puts "  Result: #{ret} (=> #{(correct == ret) ? "Ok" : "Fail"})"
  puts "  Elapsed time: #{elapsed}"
  puts
end

コード (decaptcha.rb)

#!/usr/local/bin/ruby
require 'rubygems'
require 'gd2'
require 'pp'

#
#= CAPTCHA画像解析モジュール
# CAPTCHA画像ファイルを食わすとあら不思議、Stringが出てくるよ。
# YourFileHostのやつに対応。
#
#== Usage
# decoded_str = DeCAPTCHA.decode("some_captcha_image.gif")  #=> String
# 失敗したらnilが返る。
#
module DeCAPTCHA
  DEBUG = false

  #=== CAPTCHA画像デコード
  # file::    画像ファイル名のパス
  # method::  未指定でよい。男は細かい事を気にするな。
  # returns:: CAPTCHA画像解析結果(String) or nil (デコード失敗時)
  def self.decode(file, method = DeCAPTCHA::Site::YourFileHost)
    return method.new(file).decode
  end



  #= CAPTCHA画像デコード用クラス
  # このクラスのサブクラスはimport, tokenize, stream_parseメソッドの
  # 実装を含む必要がある。
  class Site
    def initialize(file = nil)
      @pix = nil
      self.import(file) unless file.nil?
    end
    def decode
      return stream_parse(tokenize())
    end
  end

  #= YourFileHostのCAPTCHA画像を解析するクラス
  class Site::YourFileHost < Site
    def import(file)
      @pix = PixelMatrix.new.import(file)
      return self
    end

    # importしたイメージ(PixelMatrix)から、文字と思わしきパターンを
    # 抽出して上下マージンを切り取ってArrayにして返す。
    # returns:: Array of PixelMatrix
    def tokenize
      ret = []
      state = :initial
      for x in 0...@pix.width
        case state
        when :initial
          if !@pix.vline_blank?(x) then
            state = :tokenize
            pixel = PixelMatrix.new(0, 0, true)
            ret << pixel
            redo
          end
        when :tokenize
          if @pix.vline_blank?(x) then
            state = :initial
            next
          end
          x0 = pixel.width
          for y in 0...@pix.height
            pixel[x0, y] = @pix[x, y]
          end
        else
          raise 'NOTREACHED'
        end
      end

      ret.map! {|token| Token.new.import(token.cutoff_vmargin!) }
    end


    # PixelMatrixのArrayを受け取り、数字を判別。
    # tokens:: Array of PixelMatrix
    # returns:: String (判別結果)
    def stream_parse(tokens)
      rs = tokens.map {|x| x.guess.to_s }.join('')
      if rs.length != 4 then
        rs = nil
        if DEBUG then
          puts '- guess failed. dumping guess result of each token:'
          tokens.each_index do |i|
            print "##{i}:#{tokens[i].guess} "
            pp tokens[i].candidate
          end
          puts
        end
      end
      return rs
    end

    class Token
      @@digits = nil
      attr_accessor :candidate

      def initialize
        if @@digits.nil? then
          # 文字画像サンプルを作っておく
          @@digits = DIGITS_ASSOC.map {|digit|
            PixelMatrix.new(0, 0, true).import_array(digit) }
        end

        @candidate = Hash.new
      end

      # PixelMatrixを受け取り、文字画像サンプルと比較して
      # 一致率を計算しておく。
      # pixel:: PixelMatrix
      # returns:: self
      def import(pixel)
        @@digits.each_index do |i|
          digit = @@digits[i]

          if (digit.width - pixel.width).abs   > 4 or
             (digit.height - pixel.height).abs > 4 then
            @candidate[i] = -1  # サイズが違いすぎな場合、一致させない
            next
          end

          correct_bits = 0
          enlarged_width  = [digit.width,  pixel.width ].max
          enlarged_height = [digit.height, pixel.height].max
          for y in 0...enlarged_height
            dy = (y.to_f / digit.height * enlarged_height).to_i
            py = (y.to_f / pixel.height * enlarged_height).to_i
            for x in 0...enlarged_width
              dx = (x.to_f / digit.width * enlarged_width).to_i
              px = (x.to_f / pixel.width * enlarged_width).to_i
              correct_bits += 1 if digit[dx, dy] == pixel[px, py]
            end
          end

          @candidate[i] = correct_bits * 100 /
                          (enlarged_width * enlarged_height)
        end

        return self
      end

      # importのときの比較結果をもとに文字を推測
      # returns:: Fixnum or nil(失敗時)
      def guess
        digit, ratio = @candidate.sort {|a, b| a.last <=> b.last}.last
        digit = nil if ratio < 0 or ratio < 65
        return digit
      end
    end
  end


  #= 画素マトリックスクラス
  # 画像ファイルを食わせると、各ピクセル(画素)を2値(black(1) or white(0))に
  # 変換して、内部で保持する。
  # 以後、Matrixクラスのような感じで個々の画素にアクセスできる。
  class PixelMatrix
    BLACK = 1
    WHITE = 0

    attr_accessor :width
    attr_accessor :height

    # width::  幅
    # height:: 高さ
    # is_flexible:: 自動的に伸張するか
    def initialize(width = 0, height = 0, is_flexible = false)
      @matrix = Hash.new {|hash, key| hash[key] = Hash.new(WHITE)}
      @width, @height, @flexible = width, height, is_flexible
    end

    # file:: 画像ファイル名のパス
    # brightness_threshold:: 画素を黒とみなす閾値 (0 - 255, default: 0x40)
    # returns:: self (DeCAPTCHA::PixelMatrix)
    def import(file, brightness_threshold = 0x40)
      gd = GD2::Image.import(file)
      @width, @height = gd.width, gd.height

      self.each_with_axis do |x, y|
        color = gd[x, y]
        greyscale = (color.red + color.green + color.blue) / 3
        self[x, y] = (greyscale > brightness_threshold) ?
          WHITE :
          BLACK
      end
      return self
    end

    def import_array(array)
      array.each_with_index do |str, y|
        str.split('').each_with_index do |c, x|
          self[x, y] = c.to_i
        end
      end
      return self
    end

    # PixelMatrixを画像ファイルとしてexport
    # file:: 新たに作る画像ファイル名のパス
    def export(file)
      gd = GD2::Image::IndexedColor.new(@width, @height)
      gd.palette << GD2::Color::WHITE
      gd.palette << GD2::Color::BLACK
      self.each_with_axis do |x, y|
        gd[x, y] = {
          WHITE => GD2::Color::WHITE,
          BLACK => GD2::Color::BLACK,
        }[self[x, y]]
      end
      gd.export(file)
      return self
    end

    # 指定された位置の画素を返す。
    # returns:: PixelMatrix::BLACK(1) or WHITE(0)
    def [](x, y)
      if !@flexible and !in_range?(x, y) then
        raise RangeError
      end
      return WHITE if !@matrix.has_key?(y)  # XXX: for optimize
      return @matrix[y][x]
    end

    # 画素に値を設定。
    # returns:: PixelMatrix::BLACK(1) or WHITE(0)
    def []=(x, y, val)
      unless in_range?(x, y) then
        raise RangeError unless @flexible
        @width  = (x >= @width)  ? x + 1 : @width
        @height = (y >= @height) ? y + 1 : @height
      end

      @matrix[y][x] = val
    end

    def in_range?(x, y)
      ((0...@width) === x and (0...@height) === y)
    end

    # 指定された軸をもとに画素を走査し、Arrayに変換。
    # 例えば、to_a(:vertical, 10) とすると、x == 10 な列を取り出して
    # Arrayにして返す。
    #
    # axis:: 軸を指定 (:vertical または :horizontal)
    # pos:: 位置を指定。_axis_で指定した軸と直交する軸における位置を指定。
    def to_a(axis, pos)
      {:vertical => lambda {
        (0...@height).map {|y| self[pos, y]}
       },
       :horizontal => lambda {
        (0...@width).map  {|x| self[x, pos]}
       },
      }[axis].call
    end

    # returns:: Array
    def hline(y)
      self.to_a(:horizontal, y)
    end

    # returns:: Array
    def vline(x)
      self.to_a(:vertical, x)
    end

    # X軸方向に画素を走査。
    # y:: どの位置で走査するか
    # returns:: 指定された軸の上にドットが存在: false, 無い: true
    def hline_blank?(y)
      return true if @matrix.has_key?(y) == false # XXX: for optimize
      for x in 0...@width
        return false if self[x, y] == BLACK
      end
      return true
    end

    # Y軸方向に画素を走査。
    # x:: どの位置で走査するか
    # returns:: 指定された軸の上にドットが存在: false, 無い: true
    def vline_blank?(x)
      for y in 0...@height
        return false if self[x, y] == BLACK
      end
      return true
    end

    # 上下のマージンを削除した新しいPixelMatrixを返す。
    # returns:: PixelMatrix
    def cutoff_vmargin
      pixel = PixelMatrix.new(0, 0, true)
      head = 0
      tail = self.height - 1

      head.upto(tail) do |y|
        if !self.hline_blank?(y) then
          head = y
          break
        end
      end
      tail.downto(head) do |y|
        if !self.hline_blank?(y) then
          tail = y
          break
        end
      end

      head.upto(tail) do |y|
        0.upto(self.width - 1) do |x|
          pixel[x, y - head] = self[x, y]
        end
      end

      return pixel
    end
    
    # 自身の上下のマージンを削除する。cutoff_vmarginの破壊版。
    # 速度稼ぎのために直接@matrixを触ったり、すこしずるをしている。
    # 効率は、ほんの少しだけ速くなったような誤差の範囲のような感じ。
    # returns:: self (PixelMatrix)
    def cutoff_vmargin!
      head = 0
      tail = self.height - 1

      head.upto(tail) do |y|
        if !self.hline_blank?(y) then
          head = y
          break
        end
      end
      tail.downto(head) do |y|
        if !self.hline_blank?(y) then
          tail = y
          break
        end
        @matrix.delete(y) if @matrix.has_key?(y)  # XXX
      end

      if head > 0 then
        head.upto(tail) do |y|
          next if !@matrix.has_key?(y)            # XXX
          @matrix[y - head] = @matrix.delete(y)   # XXX
        end
      end
      self.height = tail - head + 1

      return self
    end
    
    def each_with_axis
      for x in 0...@width
        for y in 0...@height
          yield(x, y)
        end
      end
    end
  end
end

class DeCAPTCHA::Site::YourFileHost::Token
DIGITS_ASSOC = [
  # 0
  ["00000000011111110000000000",
   "00000001111111111110000000",
   "00000011111000001111000000",
   "00001111111100010011110000",
   "00011111100000110000111000",
   "00111111000000100001111000",
   "00111111110001000001111100",
   "01111111000010000011111110",
   "01111100000110000111111110",
   "01111111000100000111111110",
   "11111100001000001111111111",
   "11100000001000011111111111",
   "11111000010000011111111111",
   "11111000110000111111111111",
   "10000000100001111111111111",
   "01100001000001111111111110",
   "01100010000011111111111110",
   "01100010000111111111111110",
   "00111100000111111111111100",
   "00011100001111111111111000",
   "00001100011111111111111000",
   "00001111111111111111100000",
   "00000011111111111111000000",
   "00000000111111111100000000"],
  # 1
  ["00001",
   "00111",
   "11111",
   "11111",
   "10001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001",
   "00001"],
  # 2
  ["0000011111111110000000",
   "0001111111111111000000",
   "0011110000000010000000",
   "0110000000000100000000",
   "1100000000001100011110",
   "1000000000001000001111",
   "1000000000010000000111",
   "1000000000110001111111",
   "1000000000100001111111",
   "1000000001000000011111",
   "0100000011000001111111",
   "0011000010000111111110",
   "0011000110000001111110",
   "0000001100000111111100",
   "0000001000011111110000",
   "0000011000000111100000",
   "0000110000000000000000",
   "0000111111111111111111",
   "0001111111111111111110",
   "0011111111111111111100",
   "0011111111111111111100",
   "0111111111111111111000",
   "0111111111111111110000"],
  # 3
  ["000000011111111110000000",
   "000001111111111111100000",
   "000011100000011111111000",
   "000111000000111111111000",
   "000110000001111111111100",
   "000100000001111111111100",
   "000100000011111111111100",
   "000110000111111111111000",
   "000010000111111111111000",
   "000000001111111111100000",
   "000000011111111111000000",
   "000000011111111110000000",
   "000000000000001100000000",
   "000000000000011100011100",
   "000000000000111000111110",
   "000000000000110000001110",
   "000000000001110001111111",
   "110000000011100011111111",
   "111000000111000000111110",
   "011100000110001111111100",
   "001111001110000111111000",
   "000011111100000011100000",
   "000000011000111000000000"],
  # 4
  ["0000000000011",
   "0000000000011",
   "0000000000111",
   "0000000001111",
   "0000000001111",
   "0000000011111",
   "0000000111111",
   "0000000110111",
   "0000001100111",
   "0000011100111",
   "0000011000111",
   "0000110000111",
   "0001110000111",
   "0001100000111",
   "0011000000111",
   "0111000000111",
   "0111111111111",
   "1111111111111",
   "0000000000111",
   "0000000000111",
   "0000000000111",
   "0000000000111",
   "0000000000111"],
  # 5
  ["000000001111111111111110",
   "000000011111111111111100",
   "000000111111111111111100",
   "000000111111111111111000",
   "000001111111111111110000",
   "000011100000000000000000",
   "000011011111111110000000",
   "000111111111111111000000",
   "001111100000000111000000",
   "001110000000000110001100",
   "000000000000000100011110",
   "000000000000001100000110",
   "000000000000011000011111",
   "000000000000011001111111",
   "000000000000110000011111",
   "000000000001100000111111",
   "110000000001100111111110",
   "011000000011000001111110",
   "011100000110000011111100",
   "001111000110011111111000",
   "000111111100001111110000",
   "000001111100000011000000",
   "000000001000011000000000"],
  # 6
  ["000000000000000110000000",
   "000000010001111111111000",
   "000001110000011100111100",
   "000011100000011000001000",
   "000111000011111000000000",
   "001111000001110000000000",
   "001110000000111100000000",
   "011110001111111111100000",
   "011100000111000011110000",
   "011000000010000001111000",
   "011000011110000011111100",
   "010000111100000111111110",
   "100000001000000111111110",
   "100001111000001111111111",
   "000011110000011111111111",
   "000000100000011111111111",
   "000011100000111111111111",
   "001111000001111111111110",
   "000010000001111111111110",
   "001110000011111111111100",
   "000111000111111111111000",
   "000011111111111111110000",
   "000000111111111111000000",
   "000000000111111000000000"],
  # 7
  ["0011111111111110001111",
   "0011111111111100000011",
   "0111111111111000000110",
   "1111111111111000111100",
   "1111111111110000001100",
   "0000000000000000011000",
   "0000000000000011111000",
   "0000000011000000110000",
   "0000001110000011100000",
   "0000011110001111100000",
   "0000111100000011000000",
   "0001111000000110000000",
   "0001111000111110000000",
   "0011110000001100000000",
   "0011110000001000000000",
   "0011100011111000000000",
   "0011000001110000000000",
   "0001000000110000000000",
   "0000000111100000000000",
   "0000000111000000000000",
   "0000000011000000000000",
   "0000001110000000000000",
   "0000001100000000000000"],
  # 8
  ["0000000111111111110000000",
   "0000011111111111111100000",
   "0000001111100000011110000",
   "0000000001110000000111000",
   "0011000011111000000011100",
   "0011100001111100000011100",
   "0011110000001110000011100",
   "0001111000011111000111000",
   "0000111100000111101110000",
   "0000011110000001111100000",
   "0000001111000011111110000",
   "0000111111110000011111000",
   "0011110011111000001111100",
   "0111100001111100011111100",
   "0111000000111110000111110",
   "1111000000011111000000111",
   "1111000000001111100011111",
   "1111000000000011111000010",
   "0111100000000001111100000",
   "0011110000000000111110000",
   "0001111110000001111110000",
   "0000011111111111111000000",
   "0000000011111110000000000"],
  # 9
  ["000000111111111110000000",
   "000001111111111111100000",
   "000111111111111001111000",
   "001111111111110000010000",
   "011111111111110000010000",
   "011111111111100000100000",
   "011111111111000001100000",
   "111111111110000001000111",
   "111111111110000010000001",
   "111111111100000110000111",
   "011111111000000100011111",
   "011111111000001000001111",
   "001111110000011000011111",
   "001111100000010001111110",
   "000111110000100000011110",
   "000001111111100000111110",
   "000000011111000111111100",
   "000000000010000001111100",
   "000000000110000001111000",
   "000100001100011111110000",
   "000111001100001111100000",
   "000011111000001111000000",
   "000000010000110000000000"],
]
end
__END__

Permalink | トラックバック(3) | 21:28