This file is raw output from pdftotext and may not be ideal for distribution. If you are a maintainer for Hackipedia, please sit down when you have time and clean this text version up. Source PDF: /mnt/fw-js/docs/Algorithms/Machine vision/Machine Vision - Algorithm Implementation.pdf Like all conversions the text below should be fully readable as UTF-8 unicode text. --------------------------------------------------------------- Tutorial #3: Machine Vision Algorithm Implementation Dr. J.E. (Ned) Lecky LECKY ENGINEERING www.lecky.com nlecky@lecky.com Tutorial Outline ! Machine Vision Background ! Camera Interface Background ! Let’s Acquire Video! ! Basic Algorithms ! Regions of Interest ! Connectivity ! Crawling and Morphology ! Automatic Thresholding ! Edge Detection ! Intro to Algorithm Optimization Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 2 1 Machine Vision Background Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 3 MV Applications ! Five Major Categories ! Assembly Verification (Presence/Absence) ! Gauging (Metrology) ! Surface Flaw Detection ! Robot Guidance ! OCR/Barcode Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 4 2 Assembly Verification ! Favorite tools: average and variance ! Edge finding can be interesting, too Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 5 Gauging ! All I need is edge finding ! And calibration! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 6 3 Surface Flaw Detection ! Lighting becomes CRITICAL ! Sometimes a flaky inspection results Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 7 Robot Guidance ! Metrology-like, but also needs object recognition/sorting ! Many examples available Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 8 4 OCR/Barcode ! Wide range; huge market Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 9 This is Machine Vision ! Huge range of applications ! Huge range of industries ! Large set of very flexible tools required ! Let’s start making some! ! Step 1: We need to be able to get video images into our PCs Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 10 5 Camera Interface Background Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 11 Analog Video Alternatives Analog Camera Analog Transmission Scanning CCD Hardware ! Proprietary (Uncommon) A/D on Frame grabber ! Standards-based PC !NTSC !PAL Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 12 6 Digital Video Alternatives Digital Camera Scanning Digital Transmission CCD A/D Hardware 001010101010010010 ! Proprietary(Common) Board or Port ! Standards-based PC !Ethernet !Firewire (IEEE-1394) !USB/USB2 Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 13 Frame Grabber Alternatives ! Analog cameras are cheaper, and so more prevalent for now ! Two flavors of frame grabbers ! With memory ! Memoryless Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 14 7 Frame Grabber With Memory Analog Camera Analog Transmission Scanning CCD Hardware ! Acquire full image to A/D Frame Grabber frame grabber Video Memory ! Transfer (hopefully quickly) to host memory Mem CPU !ISA,EISA (ouch) !PCI (better) Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 15 Memoryless Frame Grabber Analog Camera Analog Transmission Scanning CCD Hardware ! Multiple Interrupt-driven A/D Frame Grabber transfers to host memory during acquisition Video Memory !ISA,EISA (ouch) Mem CPU !PCI (better) Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 16 8 Which Is Better? ! Hotly contested ! IfCPU does not service interrupt in time, video data will be lost with memoryless grabber, but… ! Memoryless FGBs are always cheaper ! Bottom Line ! For most applications, either will work! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 17 What About Digital Cameras? ! Video quality is typically better since no long- cable analog transmission noise ! Cameras significantly more expensive ! Rapid growth in this area due to 1394/USB2 ! These deliver a “memoryless” type model ! For now, analog cheaper and more prevalent ! And what you learn in this tutorial doesn’t really care where the video was digitized! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 18 9 Let’s Acquire Video! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 19 Acquisition Mechanics ! The interrupt handling for a “grab” is a bit nasty ! Fortunately, libraries usually exist that we can just call ! After acquisition, we would like to be able to mess with the pixels, and then display them Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 20 10 Sample Acquisition Program ! Not “algorithms,” but crucial pieces ! Four Key Pieces to Understand ! Hardware Initialization ! Acquisition Host Buffer Allocation ! Sample Processing Loop ! Acquisition ! Demo Image Processing ! Demo Image Annotation (Graphical Overlay) ! Image Display and File Output ! Deallocation and Cleanup Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 21 Some Basic Algorithms Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 22 11 We’re Ready for Algorithms ! It’simportant to see acquisition and display operations to truly understand machine vision algorithms ! Now, we can start considering some of those! ! A good starting place ! Bilevel Images Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 23 Why Bilevel Images? ! Easier to start out with simpler images ! Faster processing " good technique if it works ! Humans use them all the time ! Books Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 24 12 Creating a Bilevel Image ! Thresholding ! Since the input image is usually grayscale, we need to convert it to binary ! Our standard images are 8-bit monochrome (Y8) ! Intensities stored as unsigned chars (BYTEs), 0 – 255 ! Must pick a threshold level and convert pixels below it to 0 and above it to 255 Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 25 So Where are the Pixels? ! To operate on the pixels, we have to find them after acquisition ! Our model: the LEimage data structure ! Simple, and we can “borrow” a couple of trivial utilities Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 26 13 LEimage Structure ! Members x,y,x1,y1 only relevant for subimages (later) ! Image size dx,dy ! Member pix points to first pixel in first row ! Rat = Row Address Table ! Allows access with rat[y][x] syntax ! Other members unimportant for now struct LEimage { UINT x,y; UINT x1,y1; UINT dx,dy; PBYTE pix; PBYTE* rat; // many other members! }; Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 27 “Borrowed” Utilities! ! LEimage manipulation ! pLEimage p=levCreate(LEV_Y8,640,480); ! Creates image in memory, 640x480, Y8 ! levDestroy(p); ! Deallocates p ! pLEimage p2=levDuplicate(p); ! Creates new image identical in size to p and copies data to it ! levCopy(pSrc,pDst); ! Copies pSrc to pDst ! Both must have already been created using levCreate or levDuplicate ! Nice to not have to write stuff like this ourselves Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 28 14 Example Thresholding Program ! Thresh01 ! Shows simple threshold implementation taking an LEimage as an input ! Simple interactive +/- interface allows experimentation ! Execution Speed ! Look at the two versions… what’s different? ! Try Release vs. Debug! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 29 Convolution Example ! Classical3x3 convolution ! Great engine for many filtering operations Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 30 15 Regions of Interest Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 31 Working with Image Subsets ! Many times, we just want to look at a piece of the image ! Speed ! Multiple algorithms in one image need different processing ! We call these subsets Regions of Interest (ROIs) Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 32 16 Types of ROIs ! Our algorithms naturally work with pixel data in “rectangular” format ! For this reason, rectangular ROIs (RROIs) can be handled “in place” in the image ! Non traditional ROIs (rotated RROIs, annular segments, arbitrary lines) require pixel extraction Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 33 RROI Mechanics ! Let’s stick to the RROI! ! How to implement? ! Augment the Thresh algorithm to start and stop at a particular place, or ! Reprogram the RAT in the LEimage ! Add a utility function to make an LEimage RROI whose RAT merely points to the pixels in the source image Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 34 17 “Borrowed” RROIs! ! pLEimage roi = levRroiCreate(p,100,100,300,100); ! Roi is “owned” by p, and will be destroyed when p is destroyed pLEimage STDCALL levRroiCreate( pLEimage p, // master image UINT x,UINT y, // upper left corner of rect UINT dx,UINT dy); // rectangle dimensions roi Master LEimage rat Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 35 RROI Programming ! Easy to see the two alternatives in the code examples ! Thresh02- modify the algorithm ! Thresh03- use RROI structure ! Thresh03 is nice in that we have used identical algorithm code to process either an entire image or an RROI within it. This will be our model for programming! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 36 18 Connectivity Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 37 A Universal Algorithm ! Segmentation, Blob Analysis ! Implementation can be rather involved ! Easiest way to go (and often plenty adequate) is the labeling approach ! Start with our binary (thresholded) image… Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 38 19 Labeling ! Scan through the image until you // Driver for Mark4 UINT Label4(pLEimage p) find a black pixel { UINT label=0; ! Could do white for(UINT y=0; ydy; y++) instead, but we’ll for(UINT x=0; xdx; x++) { find black blobs if(p->rat[y][x]==0) { label++; ! Mark all } Mark4(p,x,y,label); “connected” } return label; friends with } unique label Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 39 Rattling About… ! The ugly part is // Recursive Labeler; // finds dark (pixel=0) blobs in p finding the rest of BOOL Mark4(pLEimage p,UINT x,UINT y, BYTE label) the pixels! { // mark this one p->rat[y][x]=label; ! This is a 4- // North connected if(y>0) if(p->rat[y-1][x]==0) approach Mark4(p,x,y-1,label); // South if(ydy-1) ! Just double the if(p->rat[y+1][x]==0) code for 8- Mark4(p,x,y+1,label); // West connectedness if(x>0) if(p->rat[y][x-1]==0) Mark4(p,x-1,y,label); // East if(xdx-1) if(p->rat[y][x+1]==0) Mark4(p,x+1,y,label); return TRUE; } Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 40 20 Please Don’t Run Those! ! There are some problems ! >255 blobs!? ! As in a fuzzy image! ! Quasi-infinite recursion ! As in a black or mostly black image! ! Both can be worked around ! We’ll still be limited to 255 blobs, though ! Now, some fixed up versions Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 41 Solid Labeling ! Watch the label wraparound! // Driver for Mark4 ! And, only keep UINT Label4(pLEimage p) { going if the UINT label=0; maxDepth=0; Mark4 was for(UINT y=0; ydy; y++) happy. for(UINT x=0; xdx; x++) { if(p->rat[y][x]==0) { if(label<255) label++; // quite important to check! else return label; if(!Mark4(p,x,y,label)) return label; } } return label; } Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 42 21 // North if(y>0) if(p->rat[y-1][x]==0) Solid Rattling if(!Mark4(p,x,y-1,label)) { depth--; return FALSE; } ! Track stack depth // South if(ydy-1) if(p->rat[y+1][x]==0) ! Give up if a lower if(!Mark4(p,x,y+1,label)) { depth--; Mark4 is unhappy } return FALSE; // West // Recursive Labeler; finds dark (pixel=0) blobs in p if(x>0) UINT maxDepth=0; if(p->rat[y][x-1]==0) BOOL Mark4(pLEimage p,UINT x,UINT y,BYTE label) if(!Mark4(p,x-1,y,label)) { { static UINT depth=0; depth--; return FALSE; depth++; } if(depth>maxDepth) maxDepth=depth; // East if(depth>5000) if(xdx-1) { if(p->rat[y][x+1]==0) printf("Too complex!\n"); if(!Mark4(p,x+1,y,label)) depth--; { return FALSE; depth--; } return FALSE; } // mark this one p->rat[y][x]=label; depth--; return TRUE; } Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 43 That One’s Safe to Try! ! Label01 Example program ! Looks like it works ! But now, I want more data! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 44 22 // Blob data extractor BOOL ExtractBlobData( pLEimage p,BYTE label, Pulling Info { PUINT xMin,PUINT yMin,PUINT xMax,PUINT yMax, PUINT area) BOOL fFoundFirst=FALSE; on a *area=0; for(UINT y=0; ydy; y++) for(UINT x=0; xdx; x++) Segment { if(p->rat[y][x]==label) { (*area)++; ! We just need to if(!fFoundFirst) { hunt for the fFoundFirst=TRUE; *yMin=*yMax=y; pixels with value } *xMin=*xMax=x; else x after labeling { *yMax=max(*yMax,y); ! You can do //*yMin=min(*yMin,y); *xMax=max(*xMax,x); // why //? much better than } *xMin=min(*xMin,x); this } } return fFoundFirst; } Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 45 Lets Try It ! Label02 Example Program ! Get some graphical feedback, too! ! Easy to add other things like centroid, length, major/minor axis, etc. Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 46 23 Crawling and Morphology Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 47 Why Is Perimeter Hard? ! Just count the edge pixels? ! No; disk diameter 17 has perimeter 53.4; counting either under- or over-estimates Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 48 24 What’s The Fix ! We need to realize that we’re crawling around the edge ! H/V moves are 1 pixel ! Diagonal moves are 1.414 pixel 3 3 D=7 3 3 3 3 H/V=12 3 3 Diag=8 3 3 3 3 3 3 p = πD = 7π = 21.991 3 3 3 3 3 3 p = 12 ⋅1 + 8 ⋅ 2 = 23.314 Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 49 // How many neighbors do I have with label? UINT Neighbors4(pLEimage p,UINT x,UINT y,BYTE How To Do label) { UINT count=0; PBYTE* rat=p->rat; It? if(rat[y-1][x]==label) if(rat[y+1][x]==label) count++; count++; if(rat[y][x-1]==label) count++; ! Step 1: Get if(rat[y][x+1]==label) count++; return count; me just the } // Remove non-edge blob pixels. Assumes image edge pixels is labeled BOOL BlobEdgeOnly(pLEimage pSrc,pLEimage pDst) on each blob { levCopy(pSrc,pDst); for(UINT y=1; ydy-1; y++) for(UINT x=1; xdx-1; x++) { BYTE label=pSrc->rat[y][x]; if(label) { UINT n=Neighbors4(pSrc,x,y,label); if(n==4) pDst->rat[y][x]=255; } } return true; Dr. J.E. (Ned) Lecky } Copyright c. 2000 Lecky Engineering 50 25 Now, We Can // E else if(p->rat[y][x+1]==label) { x++; Crawl } // SE *perim+=1; else if(p->rat[y+1][x+1]==label) BOOL CrawlBlobPerimeter( { pLEimage p,BYTE label, x++; PDOUBLE perim) y++; { *perim+=1.414; *perim=0; } // S for(UINT y=1; ydy-1; y++) else if(p->rat[y+1][x]==label) for(UINT x=1; xdx-1; x++) { if(p->rat[y][x]==label) y++; { *perim+=1; while(p->rat[y][x]==label) } { // SW p->rat[y][x]=0; else if(p->rat[y+1][x-1]==label) // NW { if(p->rat[y-1][x-1]==label) x--; { y++; x--; *perim+=1.414; y--; } *perim+=1.414; // W } else if(p->rat[y][x-1]==label) // N { else if(p->rat[y-1][x]==label) x--; { *perim+=1; y--; } *perim+=1; } } // NE return true; else if(p->rat[y-1][x+1]==label) } { x++; return false; y--; } *perim+=1.414; } Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 51 Perim01 Sample Program !A Few Things to Explore ! Crawling Behavior Printout ! Comment it out to run ! Are these good results ! Rerun label03, slightly enhanced ! Blob 4 A=912, D=34, P should be 106.8 ! Blob 5 A=929, D=35, P should be 109.9 ! Pretty good! Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 52 26 But There’s a Catch ! We saw that by changing the threshold, we can change the diameter of the dot ! But does the dot actually change? ! Of course not! ! So how do we get repeatable results using binary images? Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 53 Automatic Thresholding Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 54 27 Front Lighting Example ! Can be caused by camera variation or lighting variation Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 55 Back Lighting Example ! Always danger of saturating camera with direct illumination Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 56 28 Spatial Variation ! This is very commonplace, especially with large FOVs Dr. J.E. (Ned) Lecky Copyright c. 2000 Lecky Engineering 57 Automatic Thresholding // Simple histogrammer ! This is a huge // pass in a set of 256 accumulators void Histogram(pLEimage p,UINT bins[]) { area // clear the bins memset(bins,0,256*sizeof(UINT)); ! Basic idea int fOdd=p->dx&1; involves a // add em up! for(UINT y=0; ydy; y++) { statistical analysis PBYTE pp=p->rat[y]; PBYTE ppLim=pp+p->dx; of the pixel values if(fOdd) goto middle; while(pp