Home

bachelor thesis - SIRET Research Group

1. E a y uin gt Mh HR A a E O Figure 3 4 Edge detection example First picture shows the input image second picture displays calculated gradient map Bottom pictures both represent detected edges with upper 30 lower 10 and upper 20 lower 5 thresholds Canny operator 6 The whole first derivative edge detection process comprises mul tiple stages including 1 Image smoothing 2 Gradient approximation using first derivative operators 3 Non maxima suppression 4 Hysteresis thresholding or other approach to label edge pixels in the gradient map Each stage is handled by an individual component to support future extensions consult Figure 3 4 for examples Gradient Operator Component RGB Image GradientOperator Gradient Map Prior to edge detection gradient map needs to be computed from input image pixel intensities This is accomplished by applying first derivative operators depicted in Figure 3 5 while shifting a 3x3 in case of Sobel and Prewitt operators or 2x2 in case of Roberts Cross operator window over each image pixel Gradient magnitudes in X and Y directions are computed directly by the operator definition as a weighted sum of respective pixel intensities From their values we can guess approximated gradient directions in 45 degree ste
2. Figure 3 2 The first picture demonstrates bilinear interpolation principle while the second picture shows pixel triplets considered by the biquadratic interpolation algorithm Figure 3 3 Thresholding example Essential shape information is extracted by fil tering black color layer from the input picture Gaussian Smoothing Component RGB Image GaussianFilter RGB Image Processing of noisy images may reguire a preliminary smoothing step For its prop erties Gaussian smoothing has become a well established method even as a part of certain edge detection algorithms The component allows configuration of both the G parameter and the window size to obtain the desired smoothing effect Image Thresholding Component RGB Image RGBThresholding Binary Image In certain situations such as cartoon drawings maps low guality pictures plain thresholding still represents a robust and credible way to extract demanded features from the input image see Figure 3 3 The component allows user to specify a linear range of colors corresponding with image foreground rest of the pixels is ignored as background 3 2 Edge Detection Components Edge detection is a crucial step when extracting important shape features The present implementation relies for the most part on first derivative edge detection methods particularly on a set of methods which are often together denoted as the 22 WN Das AN A CN
3. Vectorization PolylineSimplification VECT SimplificationType RosinWest Figure 4 5 Scenario 2 Black and white drawing Data flow imprecise and have poor quality on the other hand for thin objects such as lines contouring is unnecessary Because of the intention to give a nice overview exam ple an image was chosen that is suitable for both skeleton and contour extraction consult Figure 4 5 4 3 Logo Even though not as simple as monochromatic drawings logo processing still intro duces no unsurpassable difficulties For most logos we could use simple RGB thresh olding to filter out important layers text border interior Edge detection is however more credible here as it works with local changes of image intensities and we need not bother to specify different color layers manually T he intensity contrasts are usually big within logos sometimes one must occupy himself with the setting of hysteresis thresholding bounds but this is not the case The resulting vector output has principially very high guality 5till we are interested in the removal of contained artifacts typically those are short one connected polylines A necessary step is to connect polylines together even the best edge detection result contains disconnected corners and small gaps here and there The respective network is depicted in Fig ure 4 6 In the given example it suffices to connect polylines blindly connecting polylines based on
4. object background important unimportant features and 29 Figure 3 7 Vectorization of segments example The input is segmented into 5 layers contours of contiguous regions are extracted afterward when it comes to edge detection it serves as a powerful mean of edge representation Unless stated otherwise in the following text we will stick to foreground background semantics by pixel neighbors we will mean adjacent foreground pixels only Morphologic Operator Component Binary Image ErosionDilatation Binary Image Morphologic operations are irreplaceable when handling binary image defects such as gaps curved objects borders Each image pixel with its respective neighbor hood is compared against a properly chosen mask For a foreground pixel in the original image dilatation operator marks neighboring pixels as foreground according to the mask Erosion is the direct opposite it preserves the foreground pixel only of its neighborhood fits the mask Erosion and dilatation operations can be successfully applied in seguence forming opening and closing operators Thinning Component Binary Image Thinning Binary Image Thinning algorithms are handy when you intend to polish results given by the edge detection or when there is need to find skeletons of thick objects Stentiford thinning algorithm 11 uses four erosion matrices The image is went through for each mask and pixels that fit th
5. widths which represents the maximum permitted deviation from the lossless vector 45 WinTopo Pro D Documents and SettingsshonzasPlochaimage_processingimages trademark logal png Oj x Fie Edit View Image Vector Window Help x SARS l sajo loo Mojo 2zUulls ss S O 6 gt T E ASE ESE Sii rx Zoom 1 R255 G 255 B 255 vector s 466 0 Y 209 0 Raster E 466 Y 33 Zz Figure 6 2 WinTopo application Obtained polylines can be set to break at intersections i e nodes are added at inter sections the other way is to let WinTopo intelligently decide polyline s continuation through intersections Last of all each vector can be assigned its color Compared to IVP Framework WinTopo offers no means of automatic vector data processing such as artifact removal polyline connection this is however more than compensated by the possibility to edit vector output directly Allowed user operations include vector addition and removal adding and removing vertices vector merging etc WinTopo also offers batch processing functionality you can specify a sequence of operations to execute on a set of input data As for the input and output WinTopo supports all traditional image formats as well as a regimen of vector formats WMF EMF DXF plaintext Screenshot of the application can be seen in Figure 6 2 6 2 Vextractor 3 80 Vextractor is yet another example of a stand alone vec
6. Framework almost completely aside from ordinary image thresholding and resizing it offers the following features e Thresholding in HSV HSL color space e Drightness contrast and gamma adjustment e Despeckle fill holes and prune filters e Heal and erode filters Edge detection is handled by multiple routines WinTopo contains Canny edge de tection method implementation seems to be similar to that in IVP Framework as well as Advanced Edge Detection option which finds edges of solid features in the image Thinning methods include Stentiford Zhang Suen and stair removal methods and a method described as their best combination to improve thinning outputs acute angle emphasis preprocessing is available WinTopo employs a two stage vectorization process First the raster image is thinned to one pixel lines then the vectors are extracted The resulting vectors are either polylines or arcs where needed suitable user can however suppress arc detection and rely merely on polyline representation For polylines WinTopo vec torization engine defaultly produces their lossless representation Smoothing option is available to reduce sharp turns in polylines which adjusts the vector vertices to make lines run smoothly from point to point while retaining maximum accuracy Polyline reduction option is present to reduce the quantity of produced vectors at the cost of lesser accuracy user can specify allowed tolerance in tenths of pixel
7. Listing 2 4 Attributes used in static port registration InputPort String name Type type bool mandatory OutputPort String name Type type bool oneConnection Listing 2 5 An example of a component s class declaration ComponentDescription public ref class GradientOperator public IIVPFComponent 4 public static enum class OpType Sobel Prewitt Roberts virtual void Initialize override virtual void Work override InputPort i1 IRGBImage typeid true event GetInputInterfaceEventHandler il OutputPort o1 IGradientMap typeid false event SetOutputInterfaceEventHandler ol event SetThumbnailEventHandler SetThumbnail Category Configuration Description Gradient operator type property OpType OperatorType lies possibility would be to implement these interfaces in the component s class but that s rather inadvisable aside from complicating class structure we re heading for big code redundancy here as we can see that the input and output types are often the same in multiple components That s where dynamic port registration steps in Fixed set of data containers is defined in containers d11 each containter imple menting certain interfaces these are data structures for images gradient maps line drawings In the Initilize function it s possible and required too to tie each port with an object that implements
8. Specialized Applications 2202 MY COCO aa AAA a Gydol 2 6 3 Multiple Object Processing lt lt lt lt 4 lt ov Component Catalogue 3 1 Image Processing Components lt lt lt lt lt lt lt lt 4 lt lt lt 0 000008 a 3 2 Edge Detection Components lt lt lt lt lt lt lt 4 yL 3 3 Segmentation Components lt lt lt lt lt lt lt lt lt lt D II ee eee 3 4 Binary Image Processing Components 0 3 5 Vector Processing Components 0 00004 ea 3 6 Line Drawing Output Components lt lt lt 2 lt lt lt lt 4 Domain Scenarios B NADO ea A a a a k RUN A boa OE 4 2 Black And White Drawing e Bee LOCO gr ds ea St le ae SB fa O es A A AA High Contrast Object s ccia 3 4 42 4 4 6 4 9 ae So AD Complex DOC TR p sate Se weet he dr n User Manual dal REGIEN AA ee Rae ee See SS oY 0 2 Stalin do e hee ee SN I a A SR oh HS Umtala Uom Gas as wa aS BS BS ww ww OLD ee Y Wy lb A 5 4 Program execution vs esa as RAS B aa A Ae we A 5 4 1 Console Application 4 dr v a S k n a aoe be be 5 4 2 Graphic User Interface Application 5 5 Graphic User Interface 0 000000 0000048 aU ANUCTMU en tc aa he as NAS is Re 10 11 13 13 13 14 14 15 16 16 16 17 19 19 19 20 21 21 22 24 29 28 92 34 34 34 36 37 37 O A Ae A GRE A Fn GY Yd i CA 23 RUPOM CHAR IO z hou un be WD SN D
9. konfigurace komponent Sou st pr ce je srovn n syst mu s jin mi aplikacemi nab zej c mi podobnou funkcionalitu Kl ov slova vektorizace extrakce tvar framework Title System for Image Vectorization Author Jan Kl ma Department Department of Software Engineering Supervisor Doc RNDr Tom s Skopal Ph D Supervisor s e mail address Tomas Skopal amp 9mff cuni cz Abstract The task of shape extraction is very complex and hasn t yet been satisfac torily solved Although there exist lots of algorithms for shape extraction the mere knowledge of such technigues doesn t give us an answer what methods should be used and how to combine them in order to obtain robust extraction method This thesis is devoted to creating a component system for image vectorization which is designed to allow easy configuration of shape extraction data flows The system s description is followed by a component catalogue that offers basic algorithms for im age processing vectorization and vector output handling Component configurations as well as typical network scenarios are covered briefly The proposed system is then compared to similar applications Keywords vectorization shape extraction framework 1 Introduction Shapes object boundaries present in an image can be regarded as medium level features that usually carry important semantic information shape recognition is also a crucial element of human sight T he ability to rel
10. or completely undesired By selecting the Run On Change menu option the network is run automatically from the place of last change this happens either when changing component s properties or when connecting ports When performing a network update exception reporting is suppressed 5 5 4 Component Manager Panel Component manager panel provides basic component related functionality Tree of all loaded components is displayed with top level nodes representing loaded libraries and child nodes loaded components Once the mouse enters component list area input output and worker components are highlighted unless a component is selected in the designer in which case component manager displays compatible components Upon clicking component s name component review is displayed including short component description port names and types User can add components into the component network two ways Left clicking the component in the manager and dragging it into the designer s area will instantiate the component generate its new unique name add it into the network and place its visual 43 representation in the designer at the position of drag drop Second way to instantiate components is suited to create sequential networks By double clicking component s name in the manager component is automatically added into the network and placed next to the last added component in the designer If its possible to connect this newly instantiated compon
11. satisfying as in Figure 3 14 The algorithm performs well as far as the input contains big connected shapes On the other hand it fails badly when processing largely unpreserved shapes with lots of noise Polyline Connection Component Line Drawing PolylineConnection Line Drawing Due to noise imprecise edge detection or overlap significant polylines might get divided into multiple disconnected parts lt is necessary to reconnect these parts again into whole pieces this is archieved nicely in Figure 3 15 Component imple ments algorithm that is described in its extended form in Altman s thesis on map digitalization 5 First of all candidate polylines are identified in the input These candidates are then iteratively connected until no further connections are possible User is offered several criteria for polyline connection The easiest way to connect polylines is to specify maximum gap between their endpoints which is usually only practicable for very small gaps it generates too many errors otherwise Second criterion is based on polylines orientation and gap sizes Optional settings include intersection handling the ability to ignore large gaps for collinear vectors as al Figure 3 15 Ideal situation to connect polylines Shapes are nicely preserved hence it s simple to reconnect polylines correctly Figure 3 16 Different types of angle measuring one side angles smaller angles X axis angles w
12. their orientation is also a smart choice here Typical data flow example is given in Figure 4 7 36 ImageFromFile GradientOperator Path file BMP OperatorType Sobel NonMaximaSuppression HysteresisThresholding BMP Lower 10 Upper 30 BMP La Vectorization ArtifactRemoval VECT RemoveSpuriousLoopArtifacts True RemoveShortUnconnectedPoylines True RemoveShort1ConnectedPolylines True PolylineSimplification PolylineConnection SimplificationType DouglasPeucker IMECT BlindConnect True Error 2 BlindConnectGap 30 BlindConnectSelfGap 10 VECT lt RemoveShortPolygons True Figure 4 6 Scenario 3 Logo MF IP Sue f ye WEBy V y 0 V gt Sl Fe M Por Su y a oe p NI O ya 2 nD Z gt E Figure 4 7 Scenario 3 Logo Data flow 4 4 High Contrast Object In case of high contrast objects i e when background is identified easily we basi cally need to choose from two alternatives We can use some segmentation algorithm to filter foreground from background or we can rely on edge detection It s hard to say which of these two approaches is the better one that rather depends on the particular input image In the example in Figure 4 9 both ways are shown on a simple image The output of segmentation algorithm is vectorized immediately and cleaned of artifacts the only artifacts in such output are small uninteresting poly gons almost the same applies to th
13. R UU WG mb Ed 5 0 4 Component Manager Panel 55 0 Property Page Panel a ja oc ur Se e Se Soe ke O 5 0 0 Thumbnails Panel uz 8 b ae eee os eke RR 6 Comparison With Similar Programs 6 1 WinTopo 3 2 Professional lt lt lt 2 a 4 I ee vs 0 VEXLLACIOL OS e a 6 4 5 be ho A RRS EA dod s Dos LD 4 ek a a O ck ee oe e A A 7 Conclusion amp Future Work 7 1 Framework Related Improvements lt lt lt lt lt lt lt 1 2 GUL Related Improvements lt lt lt lt lt 2 4 I I Appendices A XML document example N zev pr ce Syst m pro vektorizaci rastrovych obr zku Autor Jan Kl ma Katedra Katedra softwarov ho inzenyrstvi Vedouc bakal sk pr ce Doc RNDr Tom s Skopal Ph D E mail vedouc ho Tomas SkopalGmff cuni cz Abstrakt Extrakce tvar je rozs hl a st le otev en probl m P esto e je k dis pozici cel ada existuj c ch metod a algoritm nen jasn kter z t chto metod pou t a jak je zkombinovat ve snaze vytvo it robustn extrak n postup P edm tem pr ce je komponentov syst m pro vektorizaci rastrov ch obr zk navr en tak aby bylo mo n snadno konfigurovat r zn pr toky dat s t komponent Na popis syst mu navazuje katalog komponent nab zej c z kladn algoritmy pro zpracov n obr zk vektorizaci a pravy vznikl ho vektorov ho v stupu Stru n jsou t nab dnuty mo n sc n e zapojen a
14. Univerzita Karlova v Praze Matematicko fyzik ln fakulta BAKALARSKA PRACE Jan Klima Syst m pro vektorizaci rastrovych obrazku System for Image Vectorization Katedra softwarov ho inzenyrstvi Vedouc bakal sk pr ce Doc RNDr Tom s Skopal PhD Studijn program Informatika obecn informatika 2007 I would like to thank my supervisor Tomas Skopal for all the time he spent giving me invaluable feedback and support ideas I hereby certify that I wrote the thesis myself using only the referenced sources I agree with lending the thesis Prague August 7 2007 Jan Kl ma Contents 1 Introduction 2 IVP Framework 24 Comoponenn layer sis dd es a Mee as yn A 2 1 1 Primitive Types amp Metadata lt lt lt lt Ao MC CG ad as as me a a A Y Zd OMP ORONS zrak e eE bee ee a e A AA 6 AA NEL WO LK MAC Y O O II A A NR A 2 2 1 Component Manager lt lt 2 lt lt 2 2 lt a 2 22 Component Adapter lt lt lt 2 s I I I I 2 2 3 Component NetWork s c sm asaris HS BEAR dr EO 293 AMPL o r OU o se hg ak ae cd c Be ee Se WN A YA h 2A Application Level s sv 4068 OY oS ee ee we 18 we ee eee abc 2 9 Problems Related To Framework Design 2 2 5 1 Component Parametrization 0 2 5 2 Thumbnail Viewing boba oe ess MO ee ae 2 5 3 Line Drawing Representation amp Handling 2 6 Framework Discussion Le a se rasa wo a Ow a wo A 2 6 1 IVP Framework vs
15. ation which is almost impossible to reconstruct retroactively 3 5 Vector Processing Components Acquiring the vectorized shape form brings us halfway the shape extraction process Obtained data are seldom satisfactory more likely they appear as nothing more but a mess of short insignificant lines Hardest step awaits the attempt to reconstruct meaningful shapes Polyline Simplification Component Line Drawing PolylineSimplification Line Drawing For different reasons polylines and polygons may suffer from various irregularities It s also no exception that they contain much more information than required Poly line simplification while handling input defects also greatly reduces the size of vector data We can formulate the polyline approximation problem two ways e min e problem given the number of line segments find the approximation with the minimal error e min problem given the maximum allowed error find the approximation with the minimum number of line segments In both categories there exists plenty of approximation algorithms based on dynamic programming graph pruning finding the shortest path within a directed acyclic graph The methods are either optimal in relation to certain error mea sure such as L1 L2 Loo or suboptimal Optimal approaches mostly share the disadvantage of big time complexity in order of O n and for practical purposes they present no substantial improvement ove
16. c tivity information to effectively construct graph based line drawing representation which can be successively used to find artifacts or just temporarily hold connectiv ity information when it comes to removing primitives it modifies the connectivity information accordingly and decides whether its time to join some of the remaining primitives together to prevent degeneration CLineDrawing provides the basic line drawing representation capabilities with functions to add primitives specify their connectivity etc A typical scenario is that one obtains a line drawing input processes it somehow using CConnectivity and CAssoc data structures and saves it to a CLineDrawing container which is binded to one of the component s output ports 2 6 Framework Discussion The goal of this section is to compare approaches employed by the framework to different methods as well as to give some basic overview of framework s strengths and weaknesses 2 6 1 IVP Framework vs Specialized Applications Compared to specialized applications IVP Framework offers great room for ex perimentation either with inter component connections or with component specific configuration this is also its greatest strength along with maximum existing code reusability A domain where specialized applications are hardly beaten is the guality of produced outputs the goal of the IVP Framework is to find and polish sound shape extraction methods it cannot compete with a fin
17. connectivity information to each primitive This is done by designating each connectivity point with a natural number The seguence of connection numbers should contain no holes to allow fast and straightforward indexing i e with n being the number of connection points we designate each con nection point with a natural number from 0 1 n 1 set Each line primitive is assigned a pair of such connection numbers for polygons those two numbers are egual as depicted in Figure 2 5 Note that an unconnected primitive still consumes two connectivity points the worst case is that for m primitives we produce 2m connectivity points An idea crosses mind to assign all unconnected endpoints to only one connectivity point 0 for instance that is of course possible and would work well it however makes respective algorithms more complicated The resulting interface is shown in Listing 2 6 Containers dll library contains some data structures to cope with line drawings and or connectivity information The most important are e CAssoc data structure used to logically merge primitives together into bigger entities 18 e CConnectivity data structure used to handle connectivity information con nection point renaming artifact identification e CLineDrawing data structure that implements ILineDrawing interface de signed to hold all line drawing data CConnectivity data structure is the most notable of these three lt uses conne
18. drawings The second extraordinary interface is the IIVPFComponent interface which is the obligatory parent interface for all framework components Interfaces dll also contains definitions of three delegates that play an impor tant role in port and thumbnail system implementation those are shown in Listing 22 2we are referring to System Windows Forms PropertyGrid control 10 Listing 2 2 Important IVP Framework s delegates Object GetInputInterfaceEventHandler SetOutputInterfaceEventHandler Object inter SetThumbnailEventHandler IThumbnail thumb 2 1 3 Components Components are encapsulated in managed NET classes and loaded dynamically from dll files by the means of NET reflection currently all components are held in components dll library Each component inherits from IIVPFComponent interface which enforces basic component functionality the interface is shown in Listing 2 3 Listing 2 3 IIVPFComponent interface public interface class IIVPFComponent public void Initialize void Work j Initialize function serves two purposes within it default parameter initializa tion is recommended and moreover its body is the only allowed place for dynamic port registration Work function runs the component s algorithm Component specific parameters are implemented using NET property system Each public property of the class is considered to be a parameter and handled re spectively I
19. e children is used otherwise The method of Sklansky and Gonzales 10 inspects polyline points in their natu ral order hence it has only linear time complexity First point is retained decision whether to keep the other points is made upon gradual construction of conical inter sections the last point to fit within the intersection is kept the intermediate points are ignored Approximation approach published by Wall and Danielsson 12 merges points that satisfy certain criterion which here is the deviation area between the polyline and the approximating line segment divided by polyline length Some approximation results are depicted in Figure 3 11 Situation is a bit more complicated when it comes the polygons Polygon simpli fication can be thought of as a separated problem alternatively we can heuristically choose one initial point or line segment and handle the rest of the polygon with one of the preceding approaches for example with Sklansky Gonzales and Wall Danielsson methods it s clever to start from the point farthest from the polygon s center of gravity To keep things simple when utilizing the second approach cur rent implementation doesn t bother with potential degeneration and chooses starting conditions randomly i e it always retains the line segment between the first and the last point in the list 29 Figure 3 12 The most usual artifact types a short cycles b unconnected poly lines c one co
20. e edge detection output Once we have obtained artifact free output we can process it further with polyline simplification algorithms PolylineConnection component etc Check Figure 4 8 for the complete network 4 5 Complex Object There are image categories which IVP Framework currently has no chance of han dling those are mainly photos of complex scenes nature streets buildings cars The example given in this scenario is on the edge of current IVP Framework s capabilities Here we are to tackle vectorization of one complex object which is comprised of multiple parts therefore it s not immediately apparent which of these parts should be kept and which removed We are left no choice but to use edge detection in this case as both segmentation and thresholding approaches might fail easily No matter what thresholds are chosen for the hysteresis thresholding step the vectorized edge detection output always contains considerable amount of noise The decision to use ArtifactRemoval component would be well justified but as 37 ImageFromFile Segmentation Path file SegmentationType KMeansRGB BMP BMP NumberOfSegments 2 gt g BMP Canny Operator OperatorType Sobel Lower 10 s Upper 30 ArtifactRemoval RemoveShortPolygonArtifacts True ShortPolygonArtifactLength 400 BMP Vectorization ArtifactRemoval VECT RemoveSpuriousLoopArtifacts True gt RemoveShortUnconnectedP
21. e mask are deleted unless they are endpoints or connect more than one image component until there remain no points left to remove Zhang Suen approach 13 also comes with a set of erosion masks combined with more complicated removal criteria based on the crossing number and the number of neighbors Figure 3 8 shows comparison of these two approaches There s not always need for full fledged thinning process we often know that the binary image contains reasonably thin lines and just want to remove sharp turns on them Staircase removal algorithm inspects the image just once and smooths contained lines 20 EI View gt A lt gt dc Arm PAK id AC Pt P MTA STO S T yt PLK T DL TE T RL Tt Figure 3 8 A comparison of Stentiford and Zhang Suen thinning outputs Zhang Suen approach seems to produce smoother results with less artifacts k T Figure 3 9 Input binary image along with the respective contouring and thinning output Contour Extraction Component Binary Image Contouring Binary Image Skeleton is not the only potential representation of a thick object contour is often as much valuable as seen in Figure 3 9 Contours are extracted with sequential image tracing as described by Ablameyko 4 altough here we work with full image matrix instead of run length encoding Vectorization Component Binary Image Vectorization Line Drawing Vectorization component turns binary image into a set of pol
22. ell as bilateral connection check i e polyline A is connected to polyline B only if polyline B agrees 3 6 Line Drawing Output Components Vector data need to be saved to a file for further processing or similarity matching either in some well known format or as time series Line Drawing Save Component Line Drawing LDToFile file The component saves its input to a file using specified file format DXF textfile o Line Drawing Transformation Component Line Drawing LDToAngles file A component transforming input data to time series for the sake of similarity match ing Each primitive is first normalized by splitting it into a given number of egually long line segments The output representation is formed by the respective angles which can be measured as angles on one arbitrary side of the polyline polygon the 92 smaller angles between each pair of consecutive line segments or as angles formed by the line segment and the X axis an example is given in Figure 3 16 99 A Domain Scenarios Obtaining good vectorization results is impossible for large heterogenous image sets On the contrary as long as we work with distinguished collections of similar images we can use the component based framework to design typical scenarios each scenario being aimed for one particular shape extraction situation It would be foolish to think that we can get along with the implemented set of components even when proce
23. ely tuned application es pecially with that which is aimed to handle just a subset of the shape extraction problem Running algorithms in a component based environment also neccessarily implies some performance impact as well as increased memory consumption 2 6 2 Interfaces Modeling objects using interfaces is an applicable approach still 1t s far from being ideal Even if the components agree on the exchanged input output data they can hardly agree on their representation The interface representation is however fixed and it might fit some components more than others sometimes component might need to develop significant effort to adapt the input data to its needs It s also easy to imagine situations when this approach completely fails For example certain algorithms may need data with additional information which is not present in the existing interfaces e g line thickness or color in line drawings and because its impossible to alter the original interfaces the only remaining way is to use component ports somehow Lets follow the idea of colors here where can we get them Probably 19 where we extracted the former line drawing Will we use the same algorithm to extract line primitives or a different one In both cases we have problem either with code redundancy or with our inability to match colors with the primitives coming through another port 2 6 3 Multiple Object Processing The framework in its current form doesn t
24. en by the K means segmentation algorithm on feature vectors of RGB or RGBXY pixel values with euclidean distance K means represent a general approach commonly used for object clustering All we need for this method is a rule that binds an object to a defined feature vector and a measure to compare inter object distances Initially a set of K cluster centers is chosen either randomly or with a proper heuristic In each algorithm step objects are assigned to their nearest center Cluster centers are recomputed then as medians of respective assigned feature vectors The procedure stops at the moment when no objects longer change centers Segmentation Vectorization Component segment Map SegVectorization Line Drawing Contours of contiguous areas produced by the segmentation algorithm may or may not serve as useful shape descriptors One straightforward approach would be to turn area contours into a set of polygons which is in fact exactly what the compo nent does Care must be taken to ignore unreasonable contours such as contours containing image borders that seldom carry useful shape information The contigu ous areas are identified with respect to 4 connectivity Typical output is depicted in Figure 3 7 3 4 Binary Image Processing Components Binary images despite their simplicity play an important role in image process ing tasks Binary image can have different meanings depending on situation fore ground background
25. ent with the previously added one this connection is performed automatically too 5 5 5 Property Page Panel Property page displays properties of the currently selected component Property editation is test based first you must select the desired property field by clicking it which will also display short property description at the bottom of the property page Then you can edit the respective value finally you must confirm it by pressing Enter key or by leaving the property page confirmation is done automatically in some special cases such as the property page losing focus Upon entering an invalid value dialog box is shown that informs user about the error it s not possible to leave the property until a correct value is given 5 5 6 Thumbnails Panel Thumbnails panel can show outputs of some of the components To view compo nent s thumbnail you must select it first into the panel by right double clicking the corresponding component s box in the designer When doing it new thumbnail will appear in the panel which will be continuously updated in harmony with the com ponent network s operations Double clicking the thumbnail will open a full view window For both the thumbnail or its opened full view right clicking the area will open a context menu which allows to save the image to a file What you see is not always what gets saved into a file however this holds only when saving thumbnails or full views of line drawings Sa
26. ently Finally polyline approximation step is undertaken to smooth the result Forest areas visualized with dark green color present a bigger challenge as they contain gaps and there are patterns within the image drawn with the same color Upon extracting the respective color layer dilatation is performed to close or at least reduce the gaps The result is subseguently vectorized thanks to the fact that the forest areas are relatively large we can use ArtifactRemoval component to remove undesired objects including the mentioned hatch patterns 4 2 Black And White Drawing As for the monochromatic drawings the vectorization process is usually quite straight forward compared to other image types see Figure 4 4 for an example network We simply filter the black color layer by the means of thresholding in case of noisy pictures this step might reguire additional postprocessing by morphologic opera tors Further we must decide whether we want to extract drawing s contour or its skeleton and use appropriate components i e Thinning component for skeletons Contouring component for contours For thick objects obtained skeleton may be 34 ImageFromFile Path filename V BMP RGBThresholding Lower RGB 0 10 0 Upper RGB 10 128 10 y BMP ErosionDilatation OperationType Dilatation MaskType Box3x3 BMP RGBThresholding BMP Lower RGB 10 0 0 gt Upper RGB 128 10 10 PolylineSimplificatio
27. er Interface Application To run the graphic user interface execute ivpf gui exe main application window will appear immediately application window is shown in Figure 5 2 5 5 Graphic User Interface 5 5 1 Menu The upper part of the application window contains main application menu as well as application toolbar The functions offered by the toolbar are but a subset of those offered by the menu with the only purpose to make their use guicker Therefore it suffices to give description of menu functions see also Figure 5 3 for an image of the menu in its fully expanded state 41 Program Network Mew Cerler Property Page Ctrl F Run F5 Open CE Component Manager Ctrl M Stop Fo Save Ctrl 5 Thumbnails Ctrl T Run Gn Change Ctri R Save Os About Exit Figure 5 3 Expanded application menu Program menu contains the following items New creates a new empty component network user is asked to save the current network before proceeding Open opens an existing component network document to choose the input path open file dialog is shown first user is asked to save the current network before proceeding Save saves the current component network as an XML document user is queried to choose output path if the network hasn t been saved yet Save As saves the current component network user is always queried to choose the desired output path Exit terminates the application user
28. for bitmaps the situation complicates quickly with line drawings Lets make some initial agreement line drawing is composed of polylines and polygons which we will call line primitives or just primitives both considered to be infinitely thin Polylines and polygons are defined by a sequential list of points in R space in a polygon the first and the last point in the list are automatically thought to be connected We got to the first problem already how should we pass the polylines and polygons through an inter face Should we use some high level structure or rely on low level access Especially for polygons representation using a list of points can be misleading although the list has its start and its end polygon s points are naturally egual considering their position on the polygon Another problem arises when considering connectivity of particular primitives and the overall line drawing topology For two connected line primitives possible approach comes to mind to unify their endpoints so we can obtain connectivity in formation by comparing them This approach is unfortunately based on if then else testing having a set of primitives we would have to perform the comparison for every pair of primitives separately getting time complexity of O n and this computation would be necessary in each component that works with connectivity IVP Frame work takes a different path additional information about connectivity is attached to t
29. forcing parameters integrity We can seldom find a datatype that directly fits the parameter s range of values on the contrary parameter types are often complicated the most freguent non trivial types are ranges and intervals such as 0 100 0 0 00 NET doesn t have any built in mechanism to enforce these integrity requirements Therefore IVP Framework uses simple exception based approach to satisfy the reguirements each time we pass an illegal value to a property setter exception gets thrown which informs about unexpected error This approach works well with the PropertyGrid control still it has one big disadvantage we are left no mean to guess legal parameter values in advance One of the advisable work arounds would be to decorate each property with some framework specific metadata but for this approach to work well we would also need to write an eguivalent of the PropertyGrid control that respects such metadata from scratch Such component could then be highly user friendly i e displaying sliders or progress bars where needed which is impossible unless you have precise type information The implementation is however time consuming and the whole matter is only supplementary to the main framework s functionality that s why it ended up on the to do list 2 5 2 Thumbnail Viewing Thumbnail viewing represents the first step to create a collection of user friendly viewing and editing tools The thumbnail viewin
30. g mechanism is but a compromise between speed and desired functionality The problem lies in the fact that a compo nent is by no means limited in the way of storing its internal data Hence once we have to consider arbitrarily complex representations even of simple data creating thumbnail from such data can be costly We could of course specify a set of rules for data representation but that would often degrade component s performance The 16 chosen approach is natural let components choose their interior data representation although it implies slow and memory consuming thumbnail generation Through SetThumbnailEventHandler each component is allowed to register one object as its thumbnails creator Using the IThumbnail interface thumbnail data are generated the two currently supported data formats are NET bitmap and an array of GraphicsPath objects for line drawings In the GUI the obtained data are saved and processed small thumbnail is generated respecting the aspect ratio full view is also available whenever reguired The biggest performance bottleneck lies in thumbnail generation of bitmap objects there is generally no other choice how to generate the thumbnail bitmap but to set each pixel s color separately considering how slow it is to set separate pixels generating thumbnails this way often takes ages 2 5 3 Line Drawing Representation amp Handling Although it s usually simple to design interfaces and data structures
31. h serves as a mean to design run and evaluate component networks 15 2 5 Problems Related To Framework Design 2 5 1 Component Parametrization As mentioned before IVP Framework uses NET properties to implement compo nents parametrization Properties in NET are in fact nothing more but a syntactic sugar each property field is allowed to specify its corresponding accessor and setter methods We are mostly not interested in property access access scenarios are sim ple and reduce to Just reading parameters within a component or storing parameter values into a XML document Setting a property is a trickier operation not only because we have to tackle input parsing but also because we must respect demands made on property integrity i e among the set of possible datatype values certain values are forbidden to use Fortunately when it comes to parameter parsing NET gives us some strong means to get it done Primitive types implement their own conversion routines to convert them to or from a string Properties of composite types are inspected recursively using NET reflection and only leaf primitive subproperties get parsed In order to display composite property types in a PropertyGrid control NET concept of type converters is employed i e each property field of composite type must be decorated with a proper TypeConverter attribute otherwise it won t be editable in the PropertyGrid control The situation is worse when it comes to en
32. handy when comparing multiple versions of the same algorithm Both the port and property registration system is purely dynamic in JaGrLib being handled by a set of virtual functions and predefined constants Serialization and deserialization of components uses XML with the format be ing considerably more complicated and probably even more powerful for example component types are stored in the document along with their parent namespaces to distinguish between components of egual names such feature is currently unneces sary in IVP Framework considering its extent Compared to IVP Framework s graphic user interface JaGrLib is rather ad vanced lt s possible to edit multiple compositions simultaneously enjoying both undo and redo operations Module registration is contained in a separate window allowing to register or unregister components one by one An option to view reg istered modules approximately equals the IVP GUI s component manager In the design area components are also represented as boxes see Figure 6 3 compared to IVP Framework component specific parameters are contained directly within the component s box it s possible to undock the property window and move it to a dif ferent location though Component s ports are implemented in a clever way their position is in no way fixed but can be changed arbitrarily which finally results in nicer and better arranged compositions To simplify the composition even further com
33. he line drawing hence components that work with connectivity information have it at their disposal immediately The question still remains how to represent the connectivity information what complicates the situation is that polylines and polygons can be connected to other primitives in any of their points Therefore IVP Framework defines a set of constraints first for line drawing representation e A polyline is connected to other primitives merely in its endpoints e A polygon is connected to other primitives at most in one point this point is the first point is the list Aside from its simplicity this representation has some nice useful properties e g when it comes to do polygonal approximation there s no need to find maximal unconnected primitives those are naturally contained in the input Care must be 17 Listing 2 6 ILineDrawing interface public interface class ILineDrawing public maxsize NumberOfPrimitives maxsize NumberOfPoints maxsize primitive bool IsPolygon maxsize primitive VectorPoint GetPoint maxsize primitive maxsize point maxsize NumberOfConnectionPoints ConnectivityInfo ConnectionPoints maxsize primitive Figure 2 5 Line drawing along with its respective representation within the IVP Framework taken to avoid degenerate cases such as two mutually interconnected polylines which although being correct severely hamper further processing lt remains to say how to append
34. iably extract shapes would represent an essential step in many areas including computer vision search in image databases etc Shape Extraction The most frequent shape extraction technique is to vectorize the contiguous lines or areas within the image into a set of vectors polylines polygons arcs bezier curves Prior to this step the input raster needs to be preprocessed by various image processing algorithms such as smoothing edge detection thinning etc Vec torization step follows subsequently typically binary image is traced and vectors are extracted Unfortunately we have not finished our work yet the obtained vector output contains lots of undesired vectors as a result of noise poor image quality removal of such artifacts needs to be tackled Shapes amp Search in Image Databases With the rapidly growing volumes of image data similarity search in image databases is becoming even more important Text based image retrieval systems become useless as the requirements on manual annotation far exceed human possibilities Metadata based systems have similar problems because they usually require some additional explicit information to describe images and this information may be unavailable Generally we need to consider the real content of each particular image to obtain good retrieval results In image databases the task of content based similarity search is extremely difh cult due to completely unrestric
35. ing dll third party library required to im plement docking windows within the graphic user interface e networks directory containing sample component networks e images directory containing sample images Removing any of the mentioned files with the exception of samples will result in a program crash or undefined behavior During installation file association will be created that ties ivpf files with the framework 5 3 Uninstallation To uninstall the IVP Framework go to the Windows Control Panel Add Re move Programs and choose IVP Framework 40 El IYPF GUI Program view Network DIZ A AQ Gl a components dll ArtifactRemoval Contouring ErosionDilatation OperatorType Sobel GradientOperator HysteresisThresholding ImageToFile IterativePruning LDToAngles LDToFile NonMaximaSuppression PolylineConnection PolylineSimplification RGBThresholding Segmentation Segvectorization Thinning Vectorization ZeroCrossings OperatorType Input Output Both Gradient operator type Network finished Figure 5 2 Main application window of IVP Framework s GUI 5 4 Program execution 5 4 1 Console Application The console application can be run either from the command line or by double clicking any of the framework s document files T he exact command line syntax is ivpf console exe inputFile where inputFile is the name of an IVP Framework s document 5 4 2 Graphic Us
36. is asked to save the current network before proceeding View menu provides user with the following functionality Component Manager shows the component manager panel that allows user to add components into the network as well as to read information about components Property Page shows the property page panel which is the place for con figuring component specific parameters Thumbnails shows the thumbnails panel that allows user to view and save generated thumbnails Network menu contains these items Run runs the component network during the execution almost all user interface functionality is suppressed to not intervene in the execution process Stop stops the component network the working component if any is left to finish its work first Run On Change decides whether to run network every time user makes changes to the network s structure or component parameters 42 5 5 2 Designer The majority of the application s window is filled by the network designer which is a canvas to draw components and their connections Components are drawn as boxes each box containing some elementary information which includes component s name component s type as well as component s state represented as a semaphore Component s input and output ports are drawn as semicircles on the left for input ports or right side for output ports of the box Each component can be removed from the network by clicking the red cross in the up
37. itors used to view component properties in a PropertyGrid control 2 1 2 Interfaces Objects and data structures that figure in the shape extraction process are abstracted using NET interfaces and stored in interfaces dll library Each interface design is purely output oriented which corresponds with the mput output data propaga tion within a network Additional demand of transparency and simplicity low level access is made on the interfaces to assure that they are usable by every thinkable component For bitmaps the choice of interface representation is usually simple the problem becomes harder for vector data and will therefore be discussed in a separate chapter A simple example of a bitmap interface is given in Listing 2 1 Listing 2 1 IGradientMap interface example interface class IGradientMap 4 maxsize GradientMapWidth maxsize GradientMapHeight GradientMagnitude GetMagnitude maxsize y maxsize x bool IsDir0 maxsize y maxsize x bool IsDir45 maxsize y maxsize x bool IsDir90 maxsize y maxsize x bool IsDir135 maxsize y maxsize x There are two special interfaces that don t match any data structure or processed object The first is the IThumbnail interface Especially in the GUI we often need to review the guality of a component s output IThumbnail interface serves as a route through which components pass their thumbnail data as a NET bitmap or as an array of GraphicsPath objects in case of line
38. itude everywhere On the other hand areas with medium or low gradient magnitude gain importance when connected to high magnitude areas Practically the pixels are marked using depth first search on the gradient map Second Derivative Edge Detection Component RGB Image ZeroCrossings Binary Image Second derivative edge detection forms an alternative to the aforementioned methods In general it is much more sensitive to noise and false edge responses Using a simple mask the algorithm tries to roughly approximate the second derivative of intensities for each image point Consecutively it identifies pixels where the second derivative crosses zero and marks them as edges Use of threshold is preferred to filter doubtful responses 3 3 Segmentation Components Segmentation is usually defined as a procedure that takes an input image and di vides it into contiguous areas each area sharing some general properties low level 24 Figure 3 6 Input image along with the segmentation result composed of 3 layers semantic Good image segmentation may also well preserve shape information which is the reason for implementing following components Segmentation Component RGB Image Segmentation Segment Map The main goal of this component is to find an image segmentation approach to produce areas that well correspond with contained shapes consult Figure 3 6 for an example The component is presently driv
39. left invalidated The execution stops at the moment when there are no components left to run Execution of the whole network usually takes some time still we would like to be informed about network s progress Three events are provided to supply progress information one event informs the subscribers about changes in components states another event fires at the moment when the network finishes its work It might also happen that an exception gets thrown somewhere in the execution process namely when you set components with incorrect parameters such as invalid input or output file path Upon catching an exception special event is fired that returns exception description and the network execution is halted 2 3 XML Configuration In order to serialize and deserialize component network s configuration one needs to choose proper data format first Such format must have some fundamental proper ties e It should be plaintext oriented to support easy user modifications e It should should be transparent and well structured e It would to be wise to use some existing format for which NET contains built in parsing support 14 gr Component JM M OP d FF gt A x Initialize Work o Figure 2 4 Diagram showing component s life cycle First the component is cre ated by the Component Manager and wrapped within a Component Adapter Being added to a Component Network it is initia
40. lized first then it s ready to work indef initely until it s removed from the network In the IVP Framework the decision was made to use XML documents Although it s possible to give an exact format description using DTD we will get along with just intuitive description and examples The respective XML document is divided into three parts The first part con tained within the lt components gt element contains component specific information Each component name and type is encapsulated in a lt component gt element Compo nent parameters are stored within lt parameter gt tags with their names and values for properties of composite types these tags can be nested within each other Another part of the XML document contained within the lt connections gt ele ment reflects component connections Each connection between a pair of compo nents is stored in a lt connection gt element The last remaining part of the XML document contained within the lt gui gt ele ment supports GUI network editation and is not obligatory It contains information about GUI designer components locations and thumbnail settings An example of such XML document is given in Appendix A 2 4 Application Level Two applications are implemented that make the best of IVP Framework s capabil ities a simple console application that accepts a XML document and executes the respective network is accompanied by a full blown GUI application whic
41. low with the arrows representing their input output dependencies A is an input algorithm that vectorizes the input image into a set of line primitives B C and E F G are algorithm branches that transform their vector input somehow Algorithm D takes its two inputs and chooses one with respect to certain criteria Finally both D and G algorithms save their output in a specified format file stream Image and Vector Processing Framework utilizes this perspective of view and provides component based shape extraction environment with each component rep resenting one particular algorithm or a group of similar algorithms Components 8 GUI coc Components Figure 2 3 A diagram showing IVP Framework s Component Network and Appli cation layers can define their inputs and outputs as input output ports consecutively they are interconnected to form a component network Component network represents the high level shape extraction functionality and can be run on the demanded data Compared to specialized applications this approach seems to be very flexible as the user can alter the output of a component network several ways e By changing configuration of certain components e By changing component dependencies e By using different components Image and Vector Processing Framework is implemented under NET Frame work 2 0 with the C CLI being chosen as the main programming language this hardly matters though beca
42. lter what happens within the whole network Obviously rigid component network structure combined with fixed component parametrization can never lead to robust and widely usable shape extraction method instead we want the component network to evaluate outputs simultaneously By implementing specialized components that measure guality of produced outputs and set the network accordingly one could possibly hope to get good results even on large input data sets Similarly components are presently overmuch limited to contain fixed algorithmic functionality it could be advantageous to use some scripting language to directly specify what happens within the component 7 2 GUI Related Improvements Some of the possible GUI improvements are listed below e Improved set of output editing tools especially for line drawings manual out put refinement often comes handy e Built in batch processing currently batch processing is naturally available via input XML document editation i e by using some standalone macro processing tools AQ References a 2 3 4 5 6 10 11 L _ 12 13 Jagrlib http www cgg ms mff cuni cz jagrlib Vextractor http www vextrasoft com Wintopo http wintopo com S V Ablameyko Introduction to Interpretation of Graphic Images SPIE 1997 P Altman Digitalization of map Master s thesis Charles University Depart ment of Software and Computer Scie
43. n SimplificationType RosinWest Contouring BMP VECT Vectorization BMP PolylineConnection BlindConnect True BlindConnectGap 5 VECT MaximumAngleConnect True lt x MaximumGap 50 MaximumAngle 20 ConsiderEndSegment False ArtifactRemoval Vectorization RemoveJunctionNoiseArtifacts True VECT RemoveUnconnectedPolylineArtifacts True N VECT ArtifactRemoval RemoveJunctionNoiseArtifacts True RemoveUnconnectedPolylineArtifacts True RemoveShort1ConnectedPolylineArtifacts True RemoveShortPolygonArtifacts True RemoveSpuriousLoopArtifacts True PolylineSimplification SimplificationType RosinWest VECT RemoveShort1ConnectedPolylineArtifacts True RemoveShortPolygonArtifacts True RemoveSpuriousLoopArtifacts True Figure 4 2 Scenario 1 Map C A 7 WI NS E TN mill II Hia sq il i AT Milla TT fi CPA NA LC gy l FL k i i 7 Y VA YA AASA i 7 FF A ga e ho Ma WET TD S ALD PEEL Lf EE EAA CALS SA oN y YA M a k 4 6 2 p A DO NS ON Dee Ff Fns SR V Fa i y U dg J a k N 4 yr i A 3 Son L X Figure 4 3 Scenario 1 Map Data flow 30 ImageFromFile Contouring Vectorization PolylineSimplification Path file BMP VECT SimplificationType RosinWest gt gt BMP y J emp RGBThresholding Lower RGB 0 0 0 Upper RGB 128 128 128
44. n order to display properties in a PropertyGrid control parameters can be further described by the built in NET attributes such as CategoryAttribute DescriptionAttribute Each parameter of non trivial type must also define a corresponding type converter As already mentioned components exchange data by employing the concept of input and output ports Both types of ports are identified with an unique name and must specify appropriate data type with respect to interfaces defined in interfaces dll Input ports can be mandatory or non mandatory while the output ports can restrict the number of connections to one at most although this option is currently not used by any component one can easily imagine situations such as seguential data output components when it s essential Ports are modeled using NET events with the whole registration process having two stages static and dynamic To create a port one must declare a corresponding public event in the class either as an instance of GetInputInterfaceEventHandler for input ports or as an instance of SetOutputInterfaceEventHandler for output ports Such event must be also properly decorated with one of the attributes given in Listing 2 4 Attributes are needed to be able to obtain basic port information without instan tiating the class first This finishes the static registration phase To truly export the output data component needs to expose them using defined interfaces One 11
45. nce Education 2004 J Canny A computational approach to edge detection IEEE Trans Pattern Anal Mach Intell 8 6 679 698 1986 D H Douglas and T K Peucker Algorithms for the reduction of the number of points required to represent a line or its caricature Canadian Cartographer 10 2 112 122 1973 J Klima and T Skopal Shape extraction framework for similarity search in image databases In Proceedings of the Dateso 2007 Annual International Work shop on DAtabases TExts Specifications and Objects pages 89 102 2007 P L Rosin and G A W West Segmentation of edges into lines and arcs Image Vision Comput 7 2 109 114 1989 J Sklansky and V Gonzalez Fast polygonal approximation of digitized curves Pattern Recognition 12 5 327 331 1980 F Stentiford and R Mortimer Some new heuristics for thinning binary hand printed characters for ocr EEE Transactions on Systems Man and Cybernetics 13 1 81 84 1983 K Wall and P E Danielsson A fast sequential method for polygonal approxi mation of digitized curves Comput Vision Graph Image Process 28 3 220 227 1984 T Y Zhang and C Y Suen A fast parallel algorithm for thinning digital patterns Commun ACM 27 3 236 239 1984 90 A XML document example lt xml gt lt components gt lt component gt lt name gt IFF1 lt name gt lt type gt ImageFromFile lt type gt lt parameter gt lt name gt Path lt name gt lt value g
46. nnected polyline artifacts d spurious loops e insignificant junction connections Figure 3 13 Artifact removal example The former 349 primitives are cut down to just 18 with no loss of shape information Artifact Removal Component Line Drawing ArtifactRemoval Line Drawing Aside from polyline and polygon defects input vector data may contain artifacts at higher logical level i e with respect to topology and shape semantics These include redundant polylines or polygons of negligible size spurious loops or Junction artifacts for a complete list of distinguished artifacts check Figure 3 12 All the mentioned faults usually share mutual characteristics the involved polylines or polygons are short Obviously removing one artifact vector may uncover more input defects hence an iterative algotithm is employed to correct input data as much as possible Within one iteration all identifiable artifacts are marked and removed instanteously The algorithm ends upon reaching a specified number of iterations or when there are no artifacts left to remove Artifact identification is accomplished by checking connectivity of each primitive Figure 3 19 demostrates typical artifact removal situation Iterative Artifact Removal Component Line Drawing IterativePruning Line Drawing Artifact handling based on length is a sound policy still it doesn t anyhow guarantee the output to be suitably small and compact Choosing a specified n
47. nvalidated we cannot guess anything about the component s inner state the component s outputs are unreliable or inaccessible e Working component is running its algorithm at the moment e Ready component has finished executing successfully so we can rely on its outputs 2 2 3 Component Network Component network class administrates inter component connections and compo nent network execution consult Figure 2 4 for an example of component s life cycle Components can be added to or removed from a network freely as long as abiding some simple rules e g components must be identified uniquely component addition is handled solely by the component manager each component is wrapped within a component adapter etc Ports of existing components are connected together pair wise that means each connection is uniquely described by two pairs of component and port identifiers To execute the whole network components are went through starting from pure output components advancing to pure input components an alternative is to per form a local network update which instead of executing all components at once takes one component and starting from it it propagates changes through the rest of the network Prior to network execution all respective components are invalidated During the execution there might exist components that can t carry on with their work simply because they are never supplied their inputs Such components are ignored and
48. olylines True RemoveShort1ConnectedPolylines True RemoveShortPolygons True RemoveJunctionNoise True VECT SimplificationType WallDanielsson SegVectorization V VECT PolylineSimplification Error 5 PolylineSimplification VECT SimplificationType SklanskyGonzales gt Error 1 Figure 4 8 Scenario 4 High contrast object Figure 4 9 38 Scenario 4 High contrast object Data flow ImageFromFile Path file BMP OperatorType Sobel gt NonMaximaSuppression BMP jme Vectorization PolylineSimplification SimplicationType DouglasPeucker VECT Error 1 V VECT IterativePruning HysteresisThresholding BMP Lower 10 Upper 30 PolylineConnection DesiredNumberOfPrimitives 5 BlindConnect True ReductionFactor 50 VECT BlindConnectGap 30 BlindConnectSelfGap 30 MaximumAngleConnect True MaximumGap 30 MaximumAngle 20 ConsiderEndSegment True Figure 4 10 Scenario 5 Complex object f VN E lo gt gt E Gyf SA Y oe V E PON ET NI y zA fr m i T A j al M eae 4 i Ps A PZ D A Bez ers No E Figure 4 11 Scenario 5 Complex object Data flow long as we don t know anything about the input different approach comes to mind we may try to use Ite
49. omponents One example to tell it all consider a component that is supposed to draw lines In the IVP Framework the component would produce the desired output store it and stop its execution JaGrLib s component asks for an output Bitmask interface first then it immediately writes its output through the interface and passes it further in the network IVP Framework s component executes its algorithm in one defined function JaGrLib s components are not limited to have only one place of execution instead component s functionality is abstracted using interfaces too continuing our example the component implements LineRender interface This way JaGrLib is able to employ the concept of workers those are components that generate or produce networks s inputs e g LineWorker randomly generates desired number of lines by writing them into its output LineRender port 3JaGrLib is implemented in Java 47 width fs ES width Bz A Height 512 gt Height 512 G NDA Color Mode R y Bands fo 3 PNG file format Linezoin Disjoint SolidColorPen WindowTitle Preview BlackBackground 7 Bit streams using Jawa io Stream Type Output ae p Stream Mame sBresenham png 1 Repeat 1024 Seed E 3 Figure 6 3 An example of JaGrLib s composition JaGrLib has also support for some kind of output evaluation as already said it s primarily aimed for educational purposes evaluation is
50. onents user can experiment with differerent com ponent and network configurations Based on experiments a set of typical shape extraction scenarios is given along with examples of respective data flows Graphic user interface is described that allows user to configure component networks and review their outputs Finally the system is compared to other applications both commercial and academic 2 IVP Framework Image and Vector Processing Framework 8 was implemented to offer highly config urable shape extraction functionality It s based on some straightforward observa tions We have a set of resources at our disposal in the shape extraction process Generally speaking each resource fits into one of the two following categories e Objects and data structures such as images gradient maps polylines poly gons e Image and vector processing algorithms image filters edge detection thinning vectorization Algorithms can be thought of as black boxes we are in fact not at all interested in how they do their work but only in the produced results With this way of reasoning the whole shape extraction process reduces to nothing more than a data flow composed of algorithms that share and exchange processed data see Figure 2 2 for an example of such data flow m POLYLINE gt f A Sd 8 r 0 a M v VERTEX VW 8 J N i 0 Figure 2 2 Algorithms as black boxes Imaginary algorithms A G form a data f
51. oother and finely polished vector result Vectorization scenarios can be saved and loaded separately there is also present a nice generic set of ready to use scenarios including scenarios for drawings line arts maps outlines A vectorization wizard is implemented to guide user through the vectorization process Obtained vector result can be fully modified at the user level Batch processing is incorporated within the application it however only allows to select a single prepro cessing step and a vectorization scenario it s impossible to specify particular shape extraction steps individually 6 3 JaGrLib JaGrLib is a 2D 3D graphics library aimed for experimental and educational pur poses It seems to currently contain almost no algorithms suitable for shape extrac tion hence we will focus mostly on the library s structure and its respective graphic user interface which are both very interesting The overall approach taken in JaGrLib seems to be very similar to that in IVP Framework algorithms are encapsulated within components which can be connected to form complicated compositions Objects are abstracted using interfaces e g there are interfaces for line and arc renderers text renderers In the IVP Framework each component prepares its data which are read consecutively by successor compo nents JaGrLib mostly employs a different approach during component execution its data are passed immediately to the successor c
52. osy gt 242 lt posy gt lt component_panel gt lt name gt IF F 1 lt name gt lt top gt 232 lt top gt lt left gt 291 lt left gt lt component_panel gt lt component_panel gt lt name gt S1 lt name gt lt top gt 232 lt top gt lt left gt 159 lt left gt lt component_panel gt lt component_panel gt lt name gt SV1 lt name gt lt top gt 232 lt top gt lt left gt 30 lt left gt lt component_panel gt lt component_panel gt lt name gt ITF1 lt name gt lt top gt 232 lt top gt lt left gt 117 lt left gt lt component_panel gt lt designer gt lt thumbnails gt lt thumbnail gt IFF1 lt thumbnail gt lt thumbnail gt S1 lt thumbnail gt lt thumbnail gt SV1 lt thumbnail gt lt thumbnails gt lt gui gt lt xml gt 92
53. per right part of the component s box Left double click on an arbitrary spot of the component s box with the exception of component s ports will show a dialog that allows user to change the component s name Within the user interface component names are restricted to alfa numeric strings starting with an alphabet letter the framework allows to identify components with arbitrarily complex string identifiers in XML documents this feature is however denied in the user interface to ensure smooth identifier display if you want to use complex string identifiers you must modify XML documents directly Components can be moved across the designer when clicking left mouse button and holding it A simple left click will merely select the component To begin port connection user should left click a component s port Compatible ports will be highlighted immediately to finish the port connection user can left click any of the compatible ports If its possible to connect the ports it will be done error message will be displayed otherwise User has the chance to cancel port connection by right clicking any spot within the empty designer space Port disconnection is handled in the same way 1 e by clicking the port with a right mouse button To view component s thumbnail in the thumbnails panel user can select the component by double clicking it with the right mouse button 5 5 3 Run On Change Running the whole network at once is often unnecessary
54. ponents can be grouped into bigger entities For each component user is auto matically offered a list of similar components any of the listed components being a suitable replacement for the original one 48 7 Conclusion amp Future Work In the thesis basic overview of shape extraction problems was given Image and Vector Processing Framework was proposed as a mean to design run and polish shape extraction methods There is still huge amount of work ahead to achieve all the outlined goals both framework and GUI related 7 1 Framework Related Improvements What IVP Framework currently lacks is a powerful property system that would allow to exactly specify components parameter types such as ranges and intervals in an easy and transparent way e g using NET metadata Current implementation is temporary at best as it simply doesn t offer the desired level of friendliness both for component developers and potentional end users Structure of input and output data needs to be examined more closely in order to establish an approach to process multiple data layers even the whole concept of interfaces to represent objects fails sometimes and as long as we want to avoid components that only convert data from one representation to another we have to think of some trickier approach The major framework potential lies in an idea to extend components not only to have algorithmic functionality At present time the component has no means to a
55. ps Non Maxima Suppression Component Gradient Map NonMaximaSuppression Gradient Map 23 Figure 3 5 First order derivative operators Sobel Prewitt and Roberts Cross There s nothing to prevent gradient map created by first derivative gradient operators from containing thick areas of high gradient magnitude But having thick areas doesn t match our desire to identify edges preferably we would like the areas to be as thin as possible Non maxima suppression searches for peaks in gradient magnitude with respect to the gradient direction and ignores the pixels that lie on the gradient slope Tracing the gradient map sequentially all that is needed to be done is checking two adjoining pixels in the gradient direction once they both have lesser magnitude we found a gradient peak Hysteresis Thresholding Component Gradient Map HysteresisThresholding Gradient Map Hysteresis thresholding extracts edge pixels from a gradient map based on two thresh olds Each pixel with gradient magnitude greater than the upper threshold is marked as an edge pixel immediately Pixels with gradient magnitude greater than the lower threshold are marked as candidate pixels Candidate pixel is marked as edge pixel if and only if it lies on a candidate pixel chain which also contains at least one pixel with high gradient magnitude This partially resolves a common problem when trac ing edges even important edges don t have high gradient magn
56. r suboptimal methods Polyline approximation can be calculated for the whole line drawing or for each line primitive separately the former being a fundamentally harder problem The 28 Figure 3 11 Polyline simplification sample The input is simplified using the Rosin West and Wall Danielsson with e 5 algorithms Rosin West reduces the number of line segments from 1610 to 84 Due to large tolerated error Wall Danielsson produces coarser approximation with only 63 line segments component therefore processes primitives one by one with suboptimal min meth ods Douglas Peucker algorithm 7 for polyline simplification recursively splits the polyline in the point of maximum deviation from the approximating straight line segment as long as the approximation error exceeds some given threshold Rosin and West proposed a non parametric modification of the same approach 9 Series of recursive divisions define a binary tree with each two sibling nodes repre senting a better approximation of the parent polyline A measure of significance is defined as a ratio of the line segment length divided by the maximum deviation of the polyline from the approximating straight line segment Based on the significance the tree is traversed from leaves to the root At each node we compare the respective significance to its children If its greater than both of them parent approximation is kept and passed up in the tree approximation represented by th
57. rativePruning component to directly obtain the desired number of primitives In the given example in Figure 4 11 this approach works well in others in may fail The result can be polished by merging disconnected polylines or by polyline simplification Figure 4 10 shows the scheme of network configuration under this scenario 39 5 User Manual 5 1 Requirements e To run the application smoothly Microsoft Windows XP are recommended Windows Vista should run it too yet without any guarantee e Microsoft NET Framework 2 0 or any newer version containing 2 0 runtime is required e System with 512 MB of RAM is required To use full graphic user interface functionality at least 1 GB of RAM is recommended 5 2 Installation Before installation make sure that your system contains NET Framework 2 0 else you must install it first by running dotnetfx exe In order to install the framework run setup exe file and follow given instructions During the installation process you can choose destination program path Some of the installed files are listed below e containers dll containers and data structures e core dll IVP Framework s high level functionality e definitions dll IVP Framework s basic declarations types attributes e interfaces dll interfaces that describe processed objects e ivpf console exe framework s console application e ivpf gui exe framework s graphic user interface e WeifenLuo WinFormsUI Dock
58. revious knowledge of their contents Each added component is roughly inspected in order to get some basic component s description as well as port information Only here we can fully appreciate the idea of static port registration that enables us to read port information directly with no need to create component s instance first Once we obtain full list of components further processing is reguired to identify sets of mutually compatible components Considering their ports com ponents are also categorized into sets of e Pure input components components having no output ports e Pure output components components having no input ports e Worker components components having both input and output ports The component manager then exports the gathered information about compo nents through class properties Another component manager s duty is to care about components instantiation which cannot be done elsewhere serialization and deserialization 2 2 2 Component Adapter Obviously IIVPFComponent interface enforces the component classes only to contain minimal framework related information To connect components within a component network each component is wrapped within a component adapter The adapter provides each component with a unique string identifier representing component s name and creates data structures to represent component s port connections as well as component s current state The allowed component states are 13 e I
59. ssing one particular image type fixed network parametriza tion will still work for some images better then for others and certain inputs will get completely mishandled The purpose of this section is to give an overview of the experimentation results on various types of images drawings photos for each image type the example of an assembled network is given along with an example of a typical data flow Given networks are in no way comprehensive and could be improved by adding components the goal of the examples is but to give an idea of applicable approaches 4 1 Map When processing maps the interest usually lies in extraction of different map layers those are point marks buildings orientation points line features contour lines roads railroads or contiguous areas Figure 4 2 demontrates typical map processing network configuration In the example in Figure 4 3 we will try to extract contour lines and forest boundaries Both features are extracted first using RGB thresholding Contour lines need to be thinned for further processing which also carries a necessary artifact removal step artifacts are present thanks to thinning and also because there are marks in the map having the same color as contour lines Contour lines in the original map are disconnected this is a usual situation in almost all maps as there are extra symbols within the map that collide with contour lines hence we try to reconnect them consequ
60. support multiple input port connections that means it cannot handle input data of variable size This feature is simple to add though it hasn t been implemented yet for two reasons none of the currently implemented components reguires it and it s guestionable whether it s needed at all it might be favourable to use some layer concept instead i e each input is composed of several separate layers 20 3 Component Catalogue This section gives an overview of components already implemented in the IVP Frame work Those are mostly components designed to provide basic shape extraction functionality and to demonstrate framework potential All the proposed compo nents have no more than one input and one output port port types will be denoted by simplified notation input type component name output type Algorithm description follows where needed along with examples of input output transformations Component parametrization is mostly related to the described al gorithm hence parameter specifications are omitted user can familiarize himself with the parameters easily when using framework s GUI 3 1 Image Processing Components The first group of components aims to provide digital image processing functionality including image input output resampling thresholding and smoothing Image Load Save Components file ImageFromFile RGB Image RGB Image ImageToFile file Loading image into the network is usuall
61. t lena jpg lt value gt lt parameter gt lt component gt lt component gt lt name gt S1 lt name gt lt type gt Segmentation lt type gt lt parameter gt lt name gt NumberOfSegments lt name gt lt value gt 3 lt value gt lt parameter gt lt parameter gt lt name gt SegmentationType lt name gt lt value gt KMeansRGE lt value gt lt parameter gt lt component gt lt component gt lt name gt SV1 lt name gt lt type gt SegVectorization lt type gt lt component gt lt component gt lt name gt ITF1 lt name gt lt type gt ImageToFile lt type gt lt parameter gt lt name gt Path lt name gt lt value gt output dxf lt value gt lt parameter gt lt component gt lt components gt lt connections gt lt connection gt lt input_component gt S1 lt input_component gt lt output_component gt IFF1 lt output_component gt lt input_port gt il lt input_port gt lt output_port gt ol lt output_port gt lt connection gt lt connection gt lt input_component gt SV1 lt input_component gt lt output component gt S1 lt output_component gt lt input_port gt il lt input_port gt lt output_port gt ol lt output_port gt lt connection gt lt connections gt lt gui gt lt designer gt lt hminimum gt 2000 lt hminimum gt lt hmaximum gt 2000 lt hmaximum gt lt vminimum gt 2000 lt vminimum gt ol lt vmaximum gt 2000 lt vmaximum gt lt posx gt 301 lt posx gt lt p
62. ted origination of contained raster images The most general techniques of feature extraction are based on processing of low level features such as color histograms color moments etc Such methods however consider only local or global relationships between the pixels and don t capture high level informa tion In real world applications there exist high level feature extraction systems but these are usually restricted to domain specific databases e g databases of biometric features such systems cannot be used to manage heterogenous image collections When extracting shapes for the sake of similarity measuring we are not at all interested in a comprehensive vector representation instead we would like to capture the basic contained shape features and create a simple but powerful shape descriptor The desired shape descriptor must be small enough at most few kilobytes not only to perform real time similarity measuring but because otherwise we end up with huge clusters of meaningless vector data Thesis Contribution As mentioned before the process of shape extraction is a complex one with al most no general recommendations about individual extraction steps In this thesis a component based framework is introduced that allows management of various im age and vector processing algorithms Shape extraction scenarios are created by connecting components into complex networks A catalogue of basic components is proposed when using the comp
63. the specified interface which is one of the supplied containers or even the class itself The dynamic dynamic port registra tion is accomplished by firing respective SetOutputInterfaceEventHandler events In the Work function we can query framework to give us inputs by firing input ports Get InputInterfaceEventHandler events A sample component declaration is shown in Listing 2 5 12 2 2 Network Layer The high level functionality is contained within core d11 library which encompasses the means to identify and categorize components connect components into networks and run the networks The incorporated functionality is structured into three parts each part being implemented in a separate class of the same name e Component Manager handles components categorization instantiation e Component Adapter wraps instances of components e Component Network handles network creation and execution 2 2 1 Component Manager Component manager is the heart of the whole framework as it offers the most basic component handling capabilities First of all component manager loads components from dll files using NET reflection When processing input dll library it generates the list of all its public classes Each class is checked for IIVPFComponent inter face compatibility identified components are added to a component collection Such loading and identification approach guarantees smooth processing even of whole di rectories with no p
64. torization application Pro cessed image is viewed full size two separate parts of the application window are kept for image s thumbnail and zoomed detail To detect important features Canny edge detector is implemented alternatively there s an opportunity to use built in image segmentation algorithm compared to the segmentation approach in the IVP Frame work instead of keeping only the information about segments Vextractor associates each segment with its averaging color Vectorization turns the input into a set of polylines and arcs or circles by 46 tracing either center lines or contours of input objects The curvature of polylines is reduced to make them look smoother based on a given tolerance threshold this approach being possibly combined with spline approximation Vextractor contains some handy vector processing functions Bridges are re moved to form clean junctions dead end polyline artifacts are removed based on their length Disconnected contours are merged when close enough Orthogonal line recognition mode can be enabled to correct certain shapes The whole vectoriza tion process is rather different from the path taken in the IVP Framework IVP Framework doesn t bother with the guality of vectorization output it relies on suc cessive components artifact handling polyline reconnection etc On the contrary Vextractor works with the data more closely during the vectorization step which subseguently results in sm
65. umber of the most important line primitives is a preferable way in almost all situations and a very 30 Figure 3 14 The first picture shows line drawing containing 386 line primitives In the second picture there is the result of iterative artifact pruning containing 33 primitives hard problem to solve too With this component an experimental path was taken to find out if it s a good idea to prune primitives based on their length An upper bound on the desired number of primitives is selected by the user we cannot work with exact numbers here as removing one primitive might result in merging others As a first step primitives are sorted by their length in increasing order The algorithm works iteratively and tends towards the specified number of vectors in each iteration we expect to eliminate certain number of primitives the approximate number of primitives to eliminate can be specified in percents to affect the convergence speed there s however no direct relationship between the convergence speed and the guality of the produced output Elimination criterion is based on length short primitives are thrown out first and knowledge about artifacts which is similar to that used in the ArtifactRemoval component It might easily happen that we are unable to eliminate the desired number of primitives within one iteration In such case we eliminate ten percents of primitives blindly Despite the simplicity produced results are often guite
66. use all NET languages have roughly the same expres sive strength potential programmers can still develop components in the language of their own taste All compiled code if fully verifiable i e there is no unsafe or unmanaged code within the framework In this section we will pass through all the framework layers as depicted in Figure 2 3 and describe their function as well as give some handy implementation details for potential component developers 2 1 Component Layer 2 1 1 Primitive Types amp Metadata We need to establish some basic primitive types and framework rules first it would be otherwise impossible to agree on definitions of both processed objects and com ponents later on Primitive types include structures to represent image and vector points colors and connectivity information For C CLI users there is an additional list of typedefs to facilitate work with built in NET types such as different precisions of integers floats languages such as C don t have any direct equivalent of typedef construction NET offers the possibility to add metadata into its assemblies a set of metadata attributes is defined to further describe components enable port registration etc Concretely the resulting definitions dl1 library includes code gathered from e attributes h metadata attributes definition e config h C CLI typedefs e definitions h framework s primitive types e editors h general set of UITypeEd
67. ving a full view of bitmap data will always save the original bitmap no matter how it is stretched in the view window Thumbnails can be moved across the panel while holding left mouse button To remove a thumbnail select it and hit the Delete key 44 6 Comparison With Similar Programs There is plenty of image processing and vectorization applications varying in the level of their user friendliness features or availability In this section distinct appli cation examples will be given along with a straightforward comparison with the IVP Framework WinTopo 3 and Vextractor 2 represent professional commercial products both user friendly and powerful JaGrLib 1 doesn t fit into the category of vector pro cessing applications still it s an extensive framework based on similar ideas as the IVP Framework JaGrLib is also a representative of an open source system from the academic sphere It would be interesting to compare IVP Framework with the exist ing fully automatical specialized systems those are regrettably mostly unavailable no matter if they are academic or commercial 6 1 WinTopo 3 2 Professional WinTopo is a professional vectorization tool One thing that immediately catches one s eye is its maximal simplicity and user friendliness Almost all application window space is reserved for the view of processed image on which user can apply variety of both image and vector processing tools In image processing WinTopo beats IVP
68. y the first step in the majority of shape extraction tasks The ability to store images too comes handy when preprocessing large image sets or simply when there is need to use implemented image processing filters alone Image Resample Component RGB Image ImageResize RGB Image Input images might contain sampling defects they might be too large or have unac ceptably different sizes Resizing can be done absolutely by specifying desired output size or proportionally The component tackles resizing by implementing Nearest pixel Bilinear And Biguadratic interpolation algotithms Nearest pixel resampling is the most straightforward for each pixel of the output the corresponding input pixel is calculated using trivial scaling formula for big scale differences this approach works rather poorly producing substantially pixelized images Bilinear resampling takes 4 pixels to compute the resulting color first destination point s location is recomputed into input image coordinates Its 4 adjacent pixels are averaged using distance ratios between the recomputed point and the real input image pixels as seen in Figure 3 2 Biguadratic resampling is even gentler method that works with a 3x3 matrix of adjacent pixels These 9 pixels are divided into triplets and interpolated using guadratic functions Biguadratic resampling usually generates the nicest results of all the mentioned methods 21 intermediate interpolation dy2
69. ylines or polygons using the pixel chain vectorization method found in 4 and 5 It however investi gates the problem from a slightly different perspective using the concept of pixel linking Consider an arbitrary foreground pixel in fact we only need to decide which of the at most 8 neighbors should be linked to it Once we have a consistent set of rules that link a center pixel to its neighbors we can easily divide binary image into pixel chains between endpoints points with 1 link only and junctions points with more than 2 links These pixel chains are transformed into polylines immediately One trouble remains with closed cycles within the image hence an additional pass is needed to identify unprocessed pixels and turn those into polygons The following rule is employed for pixel linking Figure 3 10 Link pixel to all of its 4 connected neighbors Diagonally connected neighbor is linked to a center pixel Pal Figure 3 10 Model pixel linking situations In the first place center pixels are linked to 4 connected neighbors Diagonal neighbors are considered next only if it s inaccessible from the center using 4 connectivity For thick regions this approach still produces well defined but degenerated output Moreover the output is always intersection free which wouldn t hold if we trivially connected a pixel to all of its 8 connected neighbors Both polylines and polygons are stored along with connectivity inform

bachelor thesis - SIRET Research Group

Contents

Download Pdf Manuals

Related Search

Related Contents