Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

163
LINES

< > BotCompany Repo | #369 // Magic Wand Algorithm (optimized & including magicWandAll)

Lua code

get("#121") -- compareTables
get("#348") -- bright and rgb

maxSize = {width=100, height=50}
minSize = {width=4, height=4}
threshold = 0.5
wandSize = 2 -- magic wand size

local rectangles, img

function cloneRectangle(r)
  return newRectangle(r.x, r.y, r.width, r.height)
end

function newRectangle(x, y, w, h)
  return {x=x, y=y, width=w, height=h}
end

function contains(r, x, y)
  return x >= r.x and y >= r.y and x < r.x+r.width and y < r.y+r.width
end

function seen(x, y)
  for r, _ in pairs(rectangles) do
    if contains(r, x, y) then
      return true
    end
  end
return false
end

-- returns rectangle
function magicWand(image, x, y)
  if image ~= img then
    img, rectangles = image, {}
  end
  if seen(x, y) then return nil end
  local r = newRectangle(x, y, 1, 1)
  
  while true do
    local last = cloneRectangle(r)
    expandLeft(image, r)
    if tooLarge(r) then return nil end
    expandTop(image, r)
    if tooLarge(r) then return nil end
    expandRight(image, r)
    if tooLarge(r) then return nil end
    expandBottom(image, r)
    if tooLarge(r) then return nil end
    if compareTables(last, r) then
      if r.width >= minSize.width and r.height >= minSize.width then
        rectangles[r] = true
        return r
      else
        return nil
      end
    end
  end
end

function tooLarge(r)
  return maxSize ~= nil and (r.width > maxSize.width or r.height > maxSize.height)
end

function expandLeft(image, r)
  local newX = math.max(r.x - wandSize, 0)
  if newX == r.x then return end
  newX = searchFromLeft(image, newRectangle(newX, r.y, r.x-newX, r.height))
  r.width = r.width+r.x-newX
  r.x = newX
end

function searchFromLeft(image, r)
  for x = r.x, r.x+r.width-1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x
    end
  end
  return r.x+r.width
end

function expandRight(image, r)
  local newX = math.min(r.x + r.width + wandSize, image.width)
  if newX == r.x+r.width then return end
  newX = searchFromRight(image, newRectangle(r.x+r.width, r.y, newX-(r.x+r.width), r.height))
  r.width = newX-r.x
end

function searchFromRight(image, r)
  for x = r.x+r.width-1, r.x, -1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x+1
    end
  end
  return r.x
end

function expandTop(image, r)
  local newY = math.max(r.y - wandSize, 0)
  if newY == r.y then return end
  newY = searchFromTop(image, newRectangle(r.x, newY, r.width, r.y-newY))
  r.height = r.height+r.y-newY
  r.y = newY
end

function searchFromTop(image, r)
  for y = r.y, r.y+r.height-1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y
    end
  end
  return r.y+r.height
end

function expandBottom(image, r)
  local newY = math.min(r.y + r.height + wandSize, image.height)
  if newY == r.y+r.height then return end
  newY = searchFromBottom(image, newRectangle(r.x, r.y + r.height, r.width, newY-(r.y+r.height)))
  r.height = newY-r.y
end

function searchFromBottom(image, r)
  for y = r.y+r.height-1, r.y, -1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y+1
    end
  end
  return r.y
end

-- we're looking for dark pixels this time
function regionNotEmpty(image, r)
  --return image.clip(rectangle).anyPixelBrighterThan(threshold)
  for y=r.y, r.y+r.height-1 do
    for x=r.x, r.x+r.width-1 do
      if bright(rgb(image.getInt(x, y))) < threshold then
        return true
      end
    end
  end
  return false
end


function recttostring(r)
  return r.x..", "..r.y..", "..r.x+r.width..", "..r.y+r.height
end

function magicWandAll(image)
  local allrects = {}

  for y = 0, image.height-1, 2 do
    for x = 0, image.width-1, 2 do
      local r = magicWand(image, x, y)
      
      if r then
        allrects[recttostring(r)] = true
      end
    end
  end
  
  return allrects
end

Author comment

Began life as a copy of #363

test run  test run with input  download  show line numbers   

Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt, znullqslnikg

No comments. add comment

Snippet ID: #369
Snippet name: Magic Wand Algorithm (optimized & including magicWandAll)
Eternal ID of this version: #369/1
Text MD5: c93de8ac2039791bdd437ef966ef5e06
Author: stefan
Category: image recognition
Type: Lua code
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2015-02-02 20:20:05
Source code size: 4001 bytes / 163 lines
Pitched / IR pitched: No / Yes
Views / Downloads: 697 / 184
Referenced in: #368 - Magic Wand All size=4
#384 - Magic Wand All, optimized
#385 - Magic Wand All size=3
#386 - Magic Wand + Hashes
#398 - Magic Wand Algorithm (optimizing)
#3000188 - Answer for stefanreich(>> t search)
#3000202 - Answer for stefanreich (>> T conversion bot)
#3000238 - Answer for stefanreich (>> t power bot)
#3000382 - Answer for ferdie (>> t = 1, f = 0)
#3000383 - Answer for funkoverflow (>> t=1, f=0 okay)