-
Notifications
You must be signed in to change notification settings - Fork 17
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Polygon/Any closed path filling algorithms #53
Comments
Worked out the Boundary fill algorithm julia> using Images,ImageDraw,ColorVectorSpace
julia> function boundaryfill(x::Int, y::Int, fill_color::T, boundary_color::T) where T<:Colorant
if (img[y, x] != boundary_color && img[y, x] !=fill_color)
if checkbounds(Bool, img, y, x) img[y, x] = fill_color end
boundaryfill(x + 1, y, fill_color, boundary_color)
boundaryfill(x, y + 1, fill_color, boundary_color)
boundaryfill(x - 1, y, fill_color, boundary_color)
boundaryfill(x, y - 1, fill_color, boundary_color)
end
img
end
boundaryfill (generic function with 1 method)
julia> img=load("test2.png")
512×768 Array{RGB{N0f8},2} with eltype RGB{Normed{UInt8,8}}
julia> img_new=boundaryfill(120,120,RGB(1),RGB(1))
julia> imshow(img)
julia> @time img_new=boundaryfill(120,120,RGB(1),RGB(1)) #for circle or any other polygon for that matter
0.013602 seconds (338.09 k allocations: 5.159 MiB)
julia> @time img_new=boundaryfill(20,20,RGB(1),RGB(1)) #for square,rectangle
0.003581 seconds (87.13 k allocations: 1.330 MiB) |
Worked out the Flood fill algorithm julia> using ColorTypes, FileIO, ImageDraw, BenchmarkTools
julia> img = load("test2-floodfill.png");
julia> fill_color = RGB(0);
julia> function floodfillcolor(img, x, y, current_color, fill_color)
if (img[y, x] != current_color || img[y, x] == fill_color) return end
if checkbounds(Bool, img, y, x) img[y, x] = fill_color end
floodfillcolor(img , x + 1, y, current_color, fill_color)
floodfillcolor(img , x - 1, y, current_color, fill_color)
floodfillcolor( img, x, y + 1, current_color, fill_color)
floodfillcolor( img, x, y - 1, current_color, fill_color)
end
floodfillcolor (generic function with 1 method)
julia> function floodfill(img, x, y, fill_color)
current_color = img[y,x]
floodfillcolor(img, x, y, current_color, fill_color)
end
floodfill (generic function with 1 method)
julia> @btime floodfill(img, 10,100, fill_color); # rectangle boundary #case-1
26.756 ns (0 allocations: 0 bytes)
julia> @btime floodfill(img, 51,200, fill_color); # circle boundary # case -2 # we would need 8-pixel for this particular case
25.912 ns (0 allocations: 0 bytes)
julia> @btime floodfill(img, 350,200, fill_color); # circle fill #case -3
28.483 ns (0 allocations: 0 bytes)
julia> @btime floodfill(img, 550,200, fill_color) ; # square fill # case-4
26.287 ns (0 allocations: 0 bytes)
Flood fill and boundary fill are both seed fill method(they need a starting point provided by user).In both the above comments.4-pixel methods are used,meaning they fill 4-directions(N,S,E,W) not 8-directions. Importance of 8-pixel method can be seen from case-2 of circle,in which it's incomplete as the next points don't fall into 4-directions. Flood fill is about replacing the colors(the previous color at the seed point) with fill_color in all directions around the seed.It's not about boundary color and more about finding a particular color and replacing it. |
Worked out scan-line fill algorithm julia > using ImageDraw, ColorTypes, BenchmarkTools,ColorVectorSpace
julia > struct edgetabletuple
initial::CartesianIndex
final::CartesianIndex
end
julia > img = draw(zeros(Gray{Bool},14,14), Polygon(vert));
julia > function createedgetable()
edgetable= []
push!(edgetable, edgetabletuple(CartesianIndex(2,2),CartesianIndex(5,2)))
push!(edgetable, edgetabletuple(CartesianIndex(5,2),CartesianIndex(7,4)))
push!(edgetable, edgetabletuple(CartesianIndex(7,4),CartesianIndex(8,4)))
push!(edgetable, edgetabletuple(CartesianIndex(8,4),CartesianIndex(10,2)))
push!(edgetable, edgetabletuple(CartesianIndex(10,2),CartesianIndex(13,5)))
push!(edgetable, edgetabletuple(CartesianIndex(13,5),CartesianIndex(11,7)))
push!(edgetable, edgetabletuple(CartesianIndex(11,7),CartesianIndex(10,6)))
push!(edgetable, edgetabletuple(CartesianIndex(10,6),CartesianIndex(8,8)))
push!(edgetable, edgetabletuple(CartesianIndex(8,8),CartesianIndex(8,11)))
push!(edgetable, edgetabletuple(CartesianIndex(8,11),CartesianIndex(13,11)))
push!(edgetable, edgetabletuple(CartesianIndex(13,11),CartesianIndex(13,13)))
push!(edgetable, edgetabletuple(CartesianIndex(13,13),CartesianIndex(6,13)))
push!(edgetable, edgetabletuple(CartesianIndex(6,13),CartesianIndex(6,11)))
push!(edgetable, edgetabletuple(CartesianIndex(6,11),CartesianIndex(2,11)))
push!(edgetable, edgetabletuple(CartesianIndex(2,11),CartesianIndex(5,8)))
push!(edgetable, edgetabletuple(CartesianIndex(5,8),CartesianIndex(4,8)))
push!(edgetable, edgetabletuple(CartesianIndex(4,8),CartesianIndex(4,7)))
push!(edgetable, edgetabletuple(CartesianIndex(4,7),CartesianIndex(4,6)))
push!(edgetable, edgetabletuple(CartesianIndex(4,6),CartesianIndex(5,5)))
push!(edgetable, edgetabletuple(CartesianIndex(5,5),CartesianIndex(2,2)))
return edgetable
end
#find ymin and ymax
julia > function yminmax(vert)
ymax = vert[1][1];
ymin = vert[1][1];
for i in 1:length(vert)
if(vert[i][2] > ymax)
ymax = vert[i][2]
elseif(vert[i][2] < ymin)
ymax = vert[i][2]
end
end
return ymin, ymax
end
julia > function findintersections(edgetable, yvalue)
points =[]
for i in 1:length(edgetable)
if(edgetable[i].final[2] > yvalue && edgetable[i].initial[2] > yvalue)
continue
end
if(edgetable[i].final[2] <= yvalue && edgetable[i].initial[2] <= yvalue)
continue
end
x=1
deltay = edgetable[i].final[1]-edgetable[i].initial[1]
deltax = edgetable[i].final[2]-edgetable[i].initial[2]
alpha = deltay/deltax
constant = edgetable[i].initial[1]
x = alpha * (yvalue - edgetable[i].initial[2]) + constant
if (x == -Inf || isnan(x) || x == Inf) continue end
push!(points,CartesianIndex(ceil(Int,x),yvalue))
end
return points
end
julia > function timetocolor(points, fill_color::T)where T<:Colorant
for i in 1:2:length(points)-1
draw!(img, LineSegment(points[i], points[i+1]),fill_color)
end
end
julia > function scanline(vert, fill_color::T) where T<:Colorant
ymin, ymax = yminmax(vert)
edgetable = createedgetable()
pyramid = []
for i in ymin:ymax
points = findintersections(edgetable, i)
points = sort!(points, by = x -> x[1])
timetocolor(points, fill_color)
push!(pyramid,img[:,:])
end
pyramid
end
julia > fill_color = Gray{Bool}(1.0)
julia > pyramid = scanline(vert, fill_color)
julia > @btime pyramid = scanline(vert, fill_color)
88.844 μs (1080 allocations: 37.63 KiB)
What I am thinking this particular one can be used for(this would be great for interactivity and visualization) : P.s: It's my own code,since I wasn't able to find any good implementation(or it was too difficult for me to comprehend the ones I found) 😄 to get inspiration from...so it's just supposed to work and not perform really :).I am pretty sure it's buggy,sure it'll mess up when odd points situation will arise,also I have feeling it will mess up inside/outside polygon in some cases |
I think 8-pixel/4-pixel methods could be added as keyword configuration,so yeah these are the good polygon filling algorithms...I would need some discussion and feedback before I go into implementing them as PRs :) |
@johnnychen94 Its been a week,can you give some feedback which is to be implemented and what each should do because they are used for different puposes? |
Sorry, I didn't notice that you're waiting for feedback. All of them look pretty good to me! We could perhaps follow the same design in ImageBinarization and gradually add all of them. Possibly, we could dispatch the implementation on the unified API abstract type AbstractPolyFillAlgorithm end
struct FloodFill <: AbstractPolyFillAlgorithm end
function draw!(img, poly::Vector{CartesianIndex{2}}, alg::FloodFill(), and_other_args...)
...
end So that users could: draw!(img, [CartesianIndex(2, 5), CartesianIndex(5, 3), CartesianIndex(3, 2)], FloodFill()) It's a little bit hard to review the code inside this issue because the issue is a sequential model, so I'll wait until a PR is formed, we can start the discussion with the simplest one and make our ground solid. Usually, we do one thing for each PR, so there're three PRs here 🚀 |
any plans to add unseeded methods? I tried to fill the contours calculated from an images, using I ended up using Skimage's |
Since this project is still WIP,these filling algorithms commonly used in computer graphics would be quite useful addition
References:
The text was updated successfully, but these errors were encountered: