Raster to Vecor Algorythm?
BlitzPlus Forums/BlitzPlus Programming/Raster to Vecor Algorythm?
| ||
| Hi. This is a personnal post. (It does not have anything to do with the other topic, which Bird is dealing with now - for those who know what topic I am talking about). I am back to my original duty - creating games, etc... I got this tool I have to finish, written in plain Blitz Plus, no external DLLS, etc... Now, I got a vector of ints, containning 50 x 50 ints. Each int represents a pixel. So, each int can be either 0 or 1 (reset or set, respectively). What I need is an algorythm that would take this 2d black and white bitmap, stored in memory, and convert it to a collection of vectors, in the form (x0, y0, x1, y1). Ideally, those vectors should be stored in an ordered way, that is, either clockwise or counter-clockwise. It is going to be used to convert hand-drawn polygons to real polygons (donīt ask :D). I have already managed to read the scanned bitmap, convert it to black and white and get rid of noise. But now I am not finding a good way to vectorize it. Remember: I must to it on the fly, so I am not interested in using auto-tracing utilities. It has to be done inside my code, in plain Blitz Plus. I already have a vague idea on how to do it, but was not able to find out wher the lines start/end. For instance, how would the fillowing pattern be vectorized? XXX....... ..XX...... ...XX..... ....X..... ....XXX... ......X... .....XXX.. ......XX.. .......X.. .......X.. My point is: I am not able to work on the algorythm before I am able to see what the generated lines would look like for such elementary patterns (10 x 10 pixels). Thanks, Rui Barbosa Jr. |
| ||
| It is easier to follow this way: [CODE] XXX....... ..XX...... ...XX..... ....X..... ....XXX... ......X... .....XXX.. ......XX.. .......X.. .......X.. [/CODE] Rui Barbosa Jr. |
| ||
| Hereīs what I THINK would be the vertices of the vectorized lines for the pattern above: [CODE] XXX....... ..XX...... ...XX..... ....X..... ....XXX... ......X... .....XXX.. ......XX.. .......X.. .......X.. Becomes: X......... ..X....... ....X..... .......... ....X..... ......X... .......X.. .......... .......... .......X.. [/CODE] Does anyone disagree? Do you believe the vertices should be placed at different positions? If someone figures a good selection of vertices for the pattern in the previous post, please tell me... Got my point? My problem is that I am not confident that I can choose the vertices myself, so how can I come up with an algorythm for it? Thanks, Rui Barbosa Jr. |
| ||
| Help, please? Rui Barbosa Jr. |
| ||
| Im not sure I fully understand what you are trying to acheive? a spline curve based on averaged positioning maybe? |
| ||
| I do not need it to be a spline. Actualy, it is supposed to be low-resolution. I have a 50 by 50 pixels grid, which has the black-and-white representation of a scanned black-and-white, hand-drawn, bitmap. The example in the previos posts is part of the output of a sample scan; dots are white pixels and Xīs are black pixels. What I need is to convert the pixel pattern to a POLYGON. So, I realized that the first step in doing that was to find the line vertices. But I actually NEED the result to be A POLYGON, not a spline or anything smooth. I donīt want to apply any kind of filtering either. I need the original pixels, to stay at their original positions - FOR THE VERTICES, only; all other pixels will be inserted by using the bresenham algorythm, so the final polygon will not (as expected) to be identical to the original pattern. But the vertices must stay ay the exact same positions as they where prior to vectorizing. Cheers, Rui Barbosa Jr. P.S.: iīve got to go to sleep. 02:57AM down here; connecting from home. |
| ||
| Since it's a small sample and all you need is a polygon here's a possible approach: 1)scan concentric circles emanating from center of sample. 2)count only pixels at minimum and maximum distances from center using 5 degree of arc increments (play with this increment), consider those as possible vertices. 3)Store in array of x,y coords. 4)Lastly, connect stored coords with lines (in same order as they were determined) To interpret results, will be the trick, because basically you need to know or determine the number of vertices from the original bitmap. If you know number of verts from original, your program can narrow down candidate verts. It won't work in every situation (especially concave polygons), but for convex polygons should be close. Andy_A |
| ||
| With a little more thought a more direct solution is to scan for vertices like a radar screen. 1) from center of bitmap, find pixels at minimum and maximum distance from center (min & max radii) at every 0.1 to 2 degree of arc increments (depending on required accuracy). Using Sin/Cos to get coords for every angle from 0 to 359.99 @ 0.1 degree increments. Start with a radius of 1 pixel to a max of Sqr(2)* 25 pixels at each angle to find min/max pixels 2) store min and max distance values (radius at which pixel was found) in an array with same number of elements as degrees scanned. A 0.1 angle increment requires 3600 element array x 3 (one element for min, one element for max and 1 element for current angle), a 1 degree increment only needs 360 x 3 elements. (ex Dim pixels(Angle#, minRadius#, maxRadius#) 3) now process stored min/max distances to determine if there is an average tendency for increasing distances, if so you are finding a convex vertex, decreasing distances indicate a concave vertex. Store these in a candidate distances and angles in a polygon array. 4)Convert the distance and angle x,y coords using Sin/Cos. Connect the dots with lines. Should work for polygons where sides do not intersect other sides and vertices do not overlap. |
| ||
| Hi there. I guess that the radar screen thing will work, but I would like you guys to take a look a the algo that I have already implemented. Also, I would like to explain why it failed. So, *maybe* you guys could help me find a way to fix this very simplistic algorythm. (Remember: Itīs got to be don on the fly, so the less sin/cos/sqr/floats I use, the better). [CODE] Algorythm Make Lines List is clear Result List backToFirstVertex <-- false repeat L <-- 0 v0x, v0y <-- Find The first Vertex of The Polygon vx, vy <-- Find Position of Closest Pixel d0 <-- Find direction of Closest Pixel d <-- d0 while d is same as d0 vx, vy <-- Find Position of Closest Pixel d <-- Find direction od Closest Pixel if (vx, vy) is same as (v0x, v0y) { backToFirstVertex <-- true Exit While } add 1 to L wend if backToFirstVertex { exit repeat } forever ; ; Got here, means that it either got back to ; the starting point ; or has changed its original direction ; Add to Vertex List: v0x, v1x, d, L return Algorythm Find Position of Closest Pixel is if current position plus (0, -1) is not empty { result <-- current position plus (0, -1) } if current position plus (+1, -1) is not empty { result <-- current position plus (+1, -1) } if current position plus (+1, 0) is not empty { result <-- current position plus (+1, 0) } if current position plus (+1, +1) is not empty { result <-- current position plus (+1, +1) } if current position plus (0, +1) is not empty { result <-- current position plus (0, +1) } if current position plus (-1, +1) is not empty { result <-- current position plus (-1, +1) } if current position plus (-1, 0) is not empty { result <-- current position plus (-1, 0) } if current position plus (-1, -1) is not empty { result <-- current position plus (-1, -1) } return Algorythm Find direction of Closest Pixel is if current position plus (0, -1) is not empty { result <-- 0 } if current position plus (+1, -1) is not empty { result <-- 1 } if current position plus (+1, 0) is not empty { result <-- 2 } if current position plus (+1, +1) is not empty { result <-- 3 } if current position plus (0, +1) is not empty { result <-- 4 } if current position plus (-1, +1) is not empty { result <-- 5 } if current position plus (-1, 0) is not empty { result <-- 6 } if current position plus (-1, -1) is not empty { result <-- 7 } return [/CODE] Of course the implementation is more complicated as it has to check if the target position is inside of the (0, 0) - (49, 49) bounding rectangle among other things. The algorythm above actualy works, but has the undesirable effect of finding the "smallest lines". This will explain the problem better: [CODE] .XXXX..... .....XXXX. .......... Would be considered to be two separeted 4 pixel long lines. See? Then I figured: well, while the last lineīs lenght is same as the previous one, then this line is still the same line. But I also figured that there are lines that look like this: .XXXX..... .....X.... ......XXXX [/CODE] So, what do you think I could do? I believe that the answer is not too far from what I am doing, but I just have not been able to pull it off my head :( Or it could not be that simple, at all... Any ideas? Thanks, Rui Barbosa Jr. |
| ||
| Rui, Here's the radar algo. It will always produce a list of 36 vectors at present. List can be changed by increasing or decreasing sample size. CAVEAT: It won't do a poly shaped like the outline of the letter "C" (well, not correctly). It take 860+ millisecs to process on a 1Ghz AMD, can be optimized by using readpixelfast. You could also store the image in a bank for further speed increase. make sure the polygon you draw does not have "holes/missing pixels" in lines defining polygon. Graphics 640,480,16,2 SetBuffer BackBuffer() Dim vec(360,1),vtx(360,1) Text 0,0,"Hold left mouse button to draw a polygon ih the box" Text 0,16,"Click right mouse button in box to begin vectorization" Text 0,48, "ESC To Exit" Flip Rect(50,80,52,52,False) Flip While Not MouseHit(2) If MouseDown(1) mx = MouseX() my = MouseY() If mx > 50 And mx < 101 And my > 80 And my < 131 Then Oval mx-1,my-1,2,2,True End If End If Flip Wend st = MilliSecs() ;get max values 360 degrees around center point For i = 0 To 359 mag(75, 105, i) Next ;look for increase/decrease at 10 degree intervals count = 0 lastMax=0 Max = 0 For i = 0 To 350 Step 10 increasing = 0 decreasing = 0 flat = 0 currentMax = 1 For j = 0 To 9 currentAngle = (i + j) Mod 360 previousAngle = (currentAngle + 359) Mod 360 nextAngle = (currentAngle + 1) Mod 360 If vec(currentAngle,1) > vec(previousAngle,1) And vec(currentAngle,1) < vec(nextAngle,1) Then currentMax = chkMax(lastMax,vec(nextAngle,1)) lastMax = currentMax incAngle = currentAngle increasing = increasing + 1 End If If vec(currentAngle,1) < vec(previousAngle,1) And vec(currentAngle,1) > vec(nextAngle,1) Then currentMax = chkMax(lastMax,vec(previousAngle,1)) lastMax = currentMax decAngle = currentAngle decreasing = decreasing + 1 End If If vec(previousAngle,1) < vec(currentAngle,1) And vec(currentAngle,1) = vec(nextAngle,1) Then currentMax = chkMax(lastMax, vec(currentAngle,1)) lastMax = currentMax flatAngle = currentAngle flat= flat + 1 End If If vec(previousAngle,1) = vec(currentAngle,1) And vec(currentAngle,1) > vec(nextAngle,1) Then currentMax = chkMax(lastMax, vec(currentAngle,1)) lastMax = currentMax flatAngle = currentAngle flat = flat + 1 End If If vec(previousAngle,1) = vec(currentAngle,1) And vec(currentAngle,1) = vec(nextAngle,1) Then flatAngle = currentAngle flat = flat + 1 End If Next If increasing >= decreasing And increasing >= flat Then useAngle = incAngle If flat >= increasing And flat >= decreasing Then useAngle = flatAngle If decreasing >= increasing And decreasing >= flat Then useAngle = decAngle count = count + 1 vtx(count,0) = Cos(useAngle)* vec(useAngle,1)+175 vtx(count,1) = Sin(useAngle)* vec(useAngle,1)+105 Next ;Draw the vectors in a box to the right Rect(150,80,52,52,False) For i = 1 To count-1 Line vtx(i, 0), vtx(i,1), vtx(i+1,0), vtx(i+1,1) Next Line vtx(count,0), vtx(count,1), vtx(1,0), vtx(1,1) ;connect last point to first point et = MilliSecs() - st Text 0,400,"Finished vectorizing" Text 0,415,"Elapsed Time: " + et Flip While Not KeyHit(1):Wend End ;This function finds pixels @ given angle ;and stores max values in vec() array Function mag(centerX%, centerY%, angle%) vec(1,1) = 1 For i% = 2 To 35 x% = Cos(angle) * i + centerX y% = Sin(angle) * i + centerY If x > 50 And x < 101 And y > 80 And y < 131 Then If (ReadPixel (x,y) And 16777215) <> 0 Then If i > 1 Then ;compare current max to previous max, save biggest max = chkMax( vec(angle,1), i) vec(angle,1) = max End If End If End If Next End Function Function chkMax(a,b) If a >= b Then Return a Else Return b End If ; Return max End Function Cheers, Andy |
| ||
| Hey, Andy_A ! Man, That one is perfect! Great alorythm... It really works VERY WELL. I donīt want to bother you, but do you think that my algorythm could somehow be changed so it could actualy work? Your solution is perfect, and I am going touse it, almost as it is (i will work on a bank, thou). But would like to hear from you what you think about the algo I wrote. Maybe you can find a fix for it. Cheers, Rui Barbosa Jr. |
| ||
| Yeah, I thought about your algo some more because it is inherently faster, and a possible fix is to average out the slope of the line between pixels Here's some pseudo-code
Starting with seed pixel
For i = 1 to 10
Find next pixel (clockwise, could be up,down or right)is slope 1?
YES: this is a vertical segment, increment magnitude of current vector by 1, slope(i) = 1
NO:
Is slope 0?
YES: this is a horizontal segment, inc mag of current vector by 1, slope(i) = 0
NO: get slope of line between pixels, slope(i) = calculated slope
count = count + 1
If i > 1 then
is ABS(slope(i)-slope(i-1)) greater than threshold value?
YES: Exit from loop
End If
Next i
For i = 1 to count
AVG = AVG + slope(i)
Next
vector = lengthOfLine with slope of AVG/count
Store in vector in array of length and slope
find pixel 10 searches away from seed pixel position and repeat process above until you encounter seed pixel again.
Connect the vectors
You could repeat the process above a couple of times to reduce vector count at the cost of losing accuracy. It should still be fast if your doing all of this in memory. That's all I can think of now. Andy |
| ||
| Hi Andy_A! Do you want to try something a little bit more difficult? Would you like a challenge? If so, the here it is: Take an input bitmap, just like the ones you can create with your rastr-to-vector program. Now, for each pixel in the original bitmap, store in the output array (same sizes = 50 x 50) the angle of the line each pixel is in. Angles should be specified with a programmable precision of, which could range from 2 degrees to 45 degrees, in 0.5 degrees steps. You should not modify the original positions of the pixels. The rpogram should only get the angle information for each pixel. Do you think you can help me? Please? If I can get this thing working, I will be able to finish my game engine - and I will put your name in the credits. Cheers, Rui Barbosa Jr. P.S.: How old are you? If you are at least 18 years old, please check our other post, on the Blitz Plus Forum: "Write Blitz Plus Games and Make REAL $$$". (I have no doubt you would be able to create something real cool for us - and get payed for it, with contract and everything - but please read that post, as I am not in charge of that matter anymore). |
| ||
| Hi Rui, Would be glad to try and help, so I am going to restate what I think you said to make sure I've got the right idea. 1) Start with a seed pixel 2) Find all consecutive pixels with same slope/angle and count that as a vector 3) repeat until done That method will only find angles of 0, 90, 180, 360, 45, 135, 225, and 315. It will also create a relatively long list of vectors. If you use the radar algo (slow as it is) and reduce the scanning angle increment from 1 to 0.5, you will end up with a smaller set of vectors than the pixel by pixel method. How do you wish to proceed? Regards, Andy P.S. Have read the other post, sounds very interesting and have replied to your email address (Marcos doesn't have his own email addy?). I'm mainly interested in the different pokers games and slots. |
| ||
| Hi Andy_A. Marcos is going to have his own address on monday. Hereīs the problem I need to find a solution for: 1. I have a 50 x 50 bitmap 2. This bitmap contains the noise-free scan of a hand-drawn polygon. 3. The line width ranges from 1 to 5 pixels. (Different hand-drawn segments can have different widths, in the same bitmap!) 4. I need to scan the bitmap, using your algorythm, which gave me very good results. 5. BUT, The vectors will be used only to find out what the angle for that 10 degrees arc is. I donīt erase the original pixels and replace them with the line described by the vector. What I have to do is: for every pixel inside of that 10 degrees arc, I store the angle associated to that pixel, which is exactly the angle of the line segment found to be the resulting vector for that arc. I hope you understood. Please, let me know if that was not clear. It would be great if you could create a function, which I could call and would do this, but it would be even better, if it allowed me to specify some parameters, so that I can change the specs later. Params would be: * Box Size (currently 50 pixels, but could be 100, for instance - or 128 pixels, etc...) * Radar Scan Accuracy (Currently 10 degrees, resulting in 36 vectors, but could be 1 degree, resulting in 360 vectors - or 5 degrees, etc...) These are the global vars the function would gave to work with: Dim workBitmap%(50, 50) ; Could be (100, 100) ; for instance. ; Holds the original bitmap ; Each cell is a pixel (0 or 1) Dim angle%(50, 50) ; Angle to be assigned to each ; pixel in the bitmap, in degrees. ; Integer angles only, ranging from ; 0 to 359 degrees. So, in a few words, this is what it has to accomplish: Assign values to the array angle%(50, 50), based on the original bitmap array workBitmap%(50, 50), using your radar algorythm. It would be nice to be able to specify the size (provided the arrays are DIMed accordingly). Also, it would be even better if one could specify the angle to be used by the radar algorythm. Please, understand that this doesnīt have anything to do with the company I work for (i.e. casino games). I am just asking you to help me figure out how to progress with my game engine. Thank you *so* much for your help, Andy. Cheers, Rui Barbosa Jr. |
| ||
| I thing I understand your requirements bettern now. Didn't take into account the different line width requirement, just traced the outline of the polygon. Will work on this after some rest (it's 2:07 am now). Will get back to you when I have something. Andy |
| ||
| Hi Andy_A! Thanks for your help. If you can help me with that... I was thinking about how this could be (efficiently) done. One method could be: While shooting the radar rays, looking for the max distance, set a flag for each pixel that was already scanned. Then, after that, use some kind of flood-fill algorythm (recursive would be fine, because there wouldnīt be too many pixels to paint), which would then assign the found angle to all pixels between the previous scan-ray and the current-one, or the current one and the next one. Cheers, Rui Barbosa Jr. P.S.: Thanks for your help. If you donīt feel like writting tht function, please let me know. At the moment, I am writting the hierarchy (bones) part of the engine, but will try to write that function, if you canīt help me. Anyway, when the engine is completed, I will add your name to the credits (as well as other people names - people who helped me on other aspects of the engine). |
| ||
| The radar ras2vec algo took 862+ ms (doh! I left debug on). It take about 750 ms without debug. Here are the new algo times with debug 222 ms without debug 153 ms BTW, those are all times for windowed mode (so I could see the pointer while testing) The new algo creates an exact copy of the sampled bitmap. Let me know if this is what you had in mind. ;=============================================================================== ; Programmer: Andy Amaya ; Program Name: Bitmap To Vectors ; Date: Nov 4, 2003 ; Version: 1.003 ;=============================================================================== Graphics 640,480,16,2 SetBuffer BackBuffer() ;set bitmap dimensions here Const imgWide% = 50 Const imgHigh% = 50 ;============================== Program Loop =================================== Repeat ;storage array for vectors ;placed in loop to reset elements to zero on every iteration Dim vec(imgWide, imgHigh, 1) Cls Text 0,0,"Hold left mouse button to draw a polygon in the box" Text 0,16,"Click right mouse button in box to begin vectorization" Text 0,48, "ESC To Exit" Text 5,80, "Draw sample bitmap" Flip ;set the parameters x = 100 y = 100 wide = imgWide high = imgHigh ;draw in the rectangle to create bitmap draw(x, y, wide, high) ;start the timer st = MilliSecs() ;convert raster image to vectors vectorize (x, y, wide, high) ;stop timer here, we're only measuring time to sample & vectorize et = MilliSecs() - st ;draw the stored vectors to the right of sampled bitmap drawVectors(x + wide + 10, y, wide, high) ;all done print elapsed time Text 160, 80,"Vector Drawing" Text 10,300,"Raster to Vector Conversion Complete." Text 10,315,"Elapsed Time: " + et Flip ;press a key to run again WaitKey() ;press ESC to exit Until KeyHit(1) End ;=============================== Functions ===================================== Function draw(x%, y%, wide%, high%) Rect(x-1, y-1, wide + 2, high + 2, False) Flip While Not MouseHit(2) If MouseDown(1) mx = MouseX() my = MouseY() If mx > x And mx < x + wide + 1 And my > y And my < y + high + 1 Then Oval mx-1, my-1, 2, 2, True End If End If Flip Wend End Function Function vectorize(x%, y%, wide%, high%) ;Read in pixel color values into an array For j% = y To y + high length = 0 ;reset length counter at start of each row For i% = x To x + wide pix% = ReadPixel (i,j) And 16777215 If pix > 0 Then pix = 1 ;is pixel ON? If pix = 1 Then ;is this the first pixel in the row? If i = x Then ;increase vector length length = length + 1 ;save x and y coords, and the length vec(i-x, j-y, 1) = length ;make lastX the beginning location of the new vector lastX = i-x ;save pixel state information for next iteration lastPix = 1 Else ;Not first pixel. Is the prior pixel position lit? If lastPix = 1 Then ;If YES, increase current vector length length = length + 1 ;update and save length of the current vector vec(lastX, j-y, 1) = length ;save pixel state information for next iteration lastPix = 1 Else ;If NO, this is a new vector ;set vector length to 1 length = 1 ;save the rowNum, then beginning column of new vector, and the length vec(i-x, j-y, 1) = length ;make lastX the beginning location of the new vector lastX = i-x ;save pixel state information for next iteration lastPix = 1 End If End If Else ;pixel is OFF ;reset lastPix to zero, lastPix = 0 ;reset length to zero length = 0 ;set vector array element to zero vec(i-x, j-y, 1) = 0 End If Next Next End Function Function drawVectors(x%, y%, wide%, high%) ;making a rectangle next to the drawing rectangle Rect(x-1, y-1, wide + 2, high + 2, False) For j% = 0 To high For i% = 0 To wide ;if length is one, it's a point If vec(i, j, 1) = 1 Then Plot x, y ;if length is greater than 1, it's a line If vec(i, j, 1) > 1 Then length = vec(i, j, 1) Line( i+x, j+y, i + x + length, j+y) End If Next Next End Function Cheers, Andy |
| ||
| Hi Andy_A. Yes, thatīs almost it... We need the angle of each pixel to be stored in the output array, thou. Actualy, the radar algorythm was just perfect. You would just need to take the angle computed by each vectorīs slope and store assign that angle to each pixel within that specific scan (10 degrees arc). Cheers, Rui Barbosa Jr. |
| ||
| Maybe you already did, but here it is some code I had (not mine though and I don't know the author). Function AngleBetween(x#,y#,xx#,yy#) ;Calculates the angle between two points. ;I had some problems with ATan2 so I wrote my own :p If xx-x=>0 And yy-y>=0 Then angle=ATan((yy-y)/(xx-x)) ElseIf xx-x<0 And yy-y>=0 Then angle=180+ATan((yy-y)/(xx-x)) ElseIf xx-x<0 And yy-y<0 Then angle=180+ATan((yy-y)/(xx-x)) ElseIf xx-x=>0 And yy-y<0 Then Angle=360+ATan((yy-y)/(xx-x)) End If Return angle End Function |
   |