re removing distortion from bitmapped drawings in article apr sctc com boebert sctc com earl boebert writes let s say you have a scanned image of a line drawing in this case a boat but it could be anything on the drawing you have a set of reference points whose true x y positions are known now you digitize the drawing manually in this case using yaron danon s excellent digitize program that is you use a program which converts cursor positions to x y and saves those values when you click the mouse upon digitizing you notice that the reference point values that come out of the digitizing process differ in small but significant ways from the known true values this is understandable because the scanned drawing is a reproduction of the original and there are successive sources of distortion such as differential expansion and contraction of paper errors introduced in the printing process scanner errors and what have you the errors are not uniform over the entire drawing so global adjustments such as stretching contracting uniformly over x or y or rotating the whole drawing are not satisfactory so the question is does any kind soul know of an algorithm for removing such distortion in particular if i have three sets of points reference x y the known true values distortedreference x y the same points with known errors distorteddata x y other points with unknown errors what function of reference and distorted could i apply to distorteddata to remove the errors i suspect the problem could be solved by treating the distorted reference points as resulting from the projection of a bumpy d surface solving for the surface and then flattening it to remove the errors in the other data points it helps to have some idea of the source of the distortion or at least a reasonable model of the class of distortion below is a very short description of the process which we use if you have further questions feel free to poke me via e mail assume locally smooth distortion compute the delaunay triangulation of your x y points this defines the set of neighbors for each point if your data are not naturally convex you may have very long edges on the convex hull consider deleting these edges now there are two goals a move the distorteddata x y to the reference x y b keep the length e as measured from the current x y s as close as possible to the digitizedlength e as measured using the digitized x y s for every point compute a displacement based on a and b for example a for x y points for which you know the reference x y you can move alpha reference x y current x y this will slowly move the distortedreference x y towards the reference x y b for all other points examine the current length of each edge for each edge compute a displacement which would make that edge the correct length where correct is the digitizedlength take the vector sum of these edge displacements and move the point alpha sumofedgedisplacements this will keep the triangulated mesh consistent with your digitized mesh iterate until you are happy for example no point moves very much alpha and alpha need to be determined by experimentation consider how much you believe the reference x y i e do you absolutely insist on the final points exactly matching the references or do you want to balance some error in matching the reference against changes in length of the edges warning there are a couple of geometric invariants which must be observed essentially you can t allow the convex hull to change and you can t allow triangles to fold over neighboring triangles both of these can be handled either by special case checks on the motion of individual points or by periodically re triangulating the points using the current positions but still calculating digitizedlength from the original positions when we first did this the triangulation time was prohibitive so we only did it once if i were motivated to try and change code that has been working in production mode for years i might go back and re triangulate on every iteration if you have more compute power than you know what to do with you might consider having every point interact with every other point but first read up on linear solutions to the n body problem there are lots of papers in the last years of siggraph proceedings on springs constraints and energy calculations which are relevant the above method is described in more or less detail in inproceedings sloan author sloan jr kenneth r and david meyers and christine a curcio title reconstruction and display of the retina booktitle proceedings graphics interface vision interface address vancouver canada pages month may year techreport curcio b author christine a curcio and kenneth r sloan and david meyers title computer methods for sampling reconstruction display and analysis of retinal whole mounts number tr institution department of computer science university of washington address seattle wa month december year article curcio author christine a curcio and kenneth r sloan and david meyers title computer methods for sampling reconstruction display and analysis of retinal whole mounts journal vision research volume number pages year kenneth sloan computer and information sciences sloan cis uab edu university of alabama at birmingham a campbell hall uab station fax birmingham al
