Skip to content
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

Open
ashwanirathee opened this issue Mar 25, 2021 · 7 comments
Open

Polygon/Any closed path filling algorithms #53

ashwanirathee opened this issue Mar 25, 2021 · 7 comments

Comments

@ashwanirathee
Copy link
Member

ashwanirathee commented Mar 25, 2021

Since this project is still WIP,these filling algorithms commonly used in computer graphics would be quite useful addition

  • Boundary Fill Algorithm
    • 4- pixel method
    • 8- pixel method
  • Flood fill algorithm
  • Scan-line polygon filling

References:

@ashwanirathee
Copy link
Member Author

Worked out the Boundary fill algorithm
test2.png: https://i.imgur.com/ImGWeJm.png
Made with RectanglePoints and updated CirclePointRadius :)

MRE:

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)

Result:

@ashwanirathee
Copy link
Member Author

Worked out the Flood fill algorithm
flood fill algorithm is in both skimage and matlab
test2-floodfill.png: https://i.imgur.com/uqy0lX2.png

MRE:

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)

Result:

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.
Boundary fill avoids boundary_color and fills everything else inside the closed path with fill_color

@ashwanirathee
Copy link
Member Author

ashwanirathee commented Mar 26, 2021

Worked out scan-line fill algorithm
scan-fill is pretty popular because of how robust it is in nature
testimage: https://i.imgur.com/JQXW6Fv.png though it will be autocreated during the program

It's available in one form or other in skimage,matlab,matplotlib ,ImageDraw PIL module etc
vertices of the polygon : https://gist.github.com/ashwani-rathee/280c8c2a3d5dfed31821a57fcd015830
Algorithm needs vertices(better in a order) and fill color
MRE :

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) :

Result :

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
References:

@ashwanirathee
Copy link
Member Author

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 :)

@ashwanirathee
Copy link
Member Author

@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?

@johnnychen94
Copy link
Member

johnnychen94 commented Apr 1, 2021

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 draw!:

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 🚀

@babaq
Copy link

babaq commented Sep 7, 2021

any plans to add unseeded methods?

I tried to fill the contours calculated from an images, using Contour.jl, and don't know a easy way to find any seed inside many contours.

I ended up using Skimage's polygon, which don't need seed for input.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants