PDF Morphs, mallards, and montages: computer-aided imagination

Free download. Book file PDF easily for everyone and every device. You can download and read online Morphs, mallards, and montages: computer-aided imagination file PDF Book only if you are registered here. And also you can download or read online all Book PDF file that related with Morphs, mallards, and montages: computer-aided imagination book. Happy reading Morphs, mallards, and montages: computer-aided imagination Bookeveryone. Download file Free Book PDF Morphs, mallards, and montages: computer-aided imagination at Complete PDF Library. This Book have some digital formats such us :paperbook, ebook, kindle, epub, fb2 and another formats. Here is The CompletePDF Book Library. It's free to register here to get Book file PDF Morphs, mallards, and montages: computer-aided imagination Pocket Guide.

Citations Publications citing this paper. Cellular automata-based generative design of pied-de-poule patterns using emergent behavior: case study of how fashion pieces can help to understand modern complexity Loe M. Feijs , Mj Marina Toeters. Ahmed and Oliver Deussen. Tuti Weaving Abdalla G.

Ahmed , Oliver Deussen. A novel line fractal pied de poule houndstooth Loe M. Feijs , Marina Toeters. References Publications referenced by this paper. Ralph E. Putting the Shadow in Shadow Weave. This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below! Morphs, mallards, and montages: computer-aided imagination Home Morphs, mallards, and montages: computer-aided imagination.

All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. The output media it offered were pretty limited: I could print out ASCII characters on a long scroll of paper, or punch out holes on a yellow strip of paper tape.

Our technologies are much more advanced now, but the fun of making pictures with computers is undiminished. One of the beauties of computer graphics is that we can build up our understanding and knowledge of something by experimenting with it. Once we have a start on how something works, another beauty of graphics comes into play: we can change it!

We can modify the code, play with the controls, and generally follow our intuition to develop new kinds of techniques for making images. As in so many aspects of life, everything begins by asking the right question.

This account is currently unavailable.

In other words, you need to come up with research topics. If you have students to advise, you may have to come up with topics for them as well. Research topics are basically questions. How do you even begin to tackle a question like this? What do you need to know? What equipment do you have to acquire or build? Nobody has a clue. If Introduction Introduction.

Morphs, Mallards, and Montages: Computer-Aided Imagination

But we still have too much ambiguity in this question to really give a good answer. This question contains the seeds of its own answer, because the question itself tells us what information to gather and how to evaluate it. While thinking about a topic, I frequently bounce back and forth between these logical and intuitive ways of thinking, which is a big part of the fun! The clearest indication of that is in the messy and often contradictory notes I make while working on a project, and in the nature of the code.

When I write software for a project, of course I try to write the cleanest and most careful code I can. The descriptions of the algorithms and techniques in this book are based on the best versions that I developed through this iterative development process. I usually leave the dead ends and false starts unmentioned. If I needed to write and debug! One place where I do go into mechanics is in the math. The math in this book serves the same function as the blueprints for a building. Think of the chapters as discussions of different buildings, each with pictures of their internal decoration and discussions of their designs.

As I mentioned, nothing in this book requires you to have any particular software or hardware. Everything begins with an observation or an idea, and then pencil and paper. I work on a dual-processor Pentium computer running Windows XP. I write my text using Visual SlickEdit, in the vi emulation mode I got used to the text editor vi while still an undergraduate, and the vi commands are burned deeply into my nervous system. For three-dimensional work, I use 3ds max by Discreet. To make most of the graphs and charts, I used Mathematica from Wolfram Research, which I also used to compute some of the data and to double-check my algebraic results.

They offer expertise, advice, support, feedback, and help, and I am very grateful to them all. WRAPPING UP Writing these columns has been an invigorating mixture of pleasingly hard work, original research, library reading, analytical thought, hands-off daydreaming, programming, writing, photography, and conversations. I hope you enjoy reading them as much as I enjoyed creating them! Some of these cards are shown in Figure 1. Anyone who sets out to create their own pop-up cards or books faces two tasks: design and construction.

Creating a great pop-up presents both artistic and technical challenges. Once you have an idea in mind, you need to think about the best way to bring it about: each pop-up mechanism has its own pros and cons in terms of design time, rigidity, durability, complexity, and construction. This is a time-consuming process of trial and error. The three V-folds represent mountains, and the curvy path that passes through them was the road I drove across the country.

Each iteration of the process can easily take a quarter-hour or more for even simple cards. Getting all the pieces to move in the right ways and not get bent or scrunched against each other is a challenging task. Once the card is successfully designed, then you have to actually make the thing.

My goal in creating my Assistant was not to create pop-up cards for viewing on the computer. That might be fun, but it seems to miss the point, which is the tactile pleasure in opening the card and the delight of feeling it open up.

The idea is to make it easier to design wonderful cards that can then be constructed and shared in the real world. The history of pop-up books blends together commerce, innovation, book publishing, personal creativity, and even world events. Movable books were not originally meant for children. Before that date, all books were for adults and usually serious in subject matter.

He divided each disc up into sectors like pie wedges and assigned one theme to each sector. The discs were then cut out and stacked up, so that one needed only to turn the wheels to understand nature, and thus also predict the future. Volvelles were particularly used for astrology. A Latin manuscript used volvelles to describe the motion of the planets over an almost year period from to Movable discs were also used for mathematics. In , Johannes Schoner, a Nurenberg professor, published a calculator in movable-disc form in Opera Mathematica.

The book presents the chest, abdomen, and viscera through seven highly-detailed, superimposed layers that were hinged at the neck. All of these books were hand-made. Movable devices made them even more appealing. Sayer took a single large sheet and folded it to create four panels, each of which could be opened to reveal a different scene or bit of verse. They created books that were based on the popular accordion, or peep-show style.

The idea was that many layers were stacked up one behind the other. The child opened the book by pulling the layers apart and setting them up on a table. The layers were connected by a ribbon that ran through each one and emerged from the rearmost layer.

Glassner, Andrew S.

When the child pulled this ribbon, the structures in each layer were pulled out and into position. Then the child peered through a hole in the front cover to view the newly-created diorama. From the s to about , Dean and Sons produced about 50 toy books based on this principle. By this time high-quality toy books had become a luxury item for the children of rich Europeans and Americans. In a German publisher named Ernest Nister started designing new mechanical books in his Nuremberg studio and printing them in Bavaria where costs were low and quality was high. Because he could afford to charge high prices, Nister was able to make very high-quality books and became the best-known publisher of them by the turn of the century.

Although Nister was the best-known publisher of movable books for children, a contemporary of his named Lothar Meggendorfer was setting a new standard for complexity and ingenuity. Meggendorfer was a mechanical wizard who created tiny metal rivets out of very tightly-wound thin copper wire. Some of the actions were even staged to occur in time-delayed sequences as the wire uncoiled from one rivet to the next.

His book The Circus has been described as one of the most soughtafter books of the nineteenth century. Between and Chapter One Chapter World War I put an end to what is now considered the Golden Age of mechanical books. These were called dimensional books because they were mostly about depth and perspective, rather than moving parts. First, they were able to lift themselves up when the book was opened degrees. Second, the action sometimes continued even after the book was open. For example, in one particularly clever construction the opening of the pages reveals a clown swinging on a trapeze.

Even after the book is completely open, the clown continues to swing back and forth. Although uncredited, it appears that Theodore Brown, an inventor who also worked on motion pictures, was the paper engineer who worked these surprises. Julian Wehr created a series of movable books featuring colorful, articulated people that moved in response to pulling a tab. At the same time, Czechoslovakian artist Viotech Kubasta created dozens of popular pop-up books based on fairy tales.

Today, many English-language books are designed in Europe and America, but almost all printed and constructed in Columbia, Mexico, and Singapore, where the tedious and painstaking cutting and assembly steps are less expensive. Publisher Waldo Hunt has estimated that, from to , a total of less than ten million pop-up books were produced in the entire world. Today, up to 25 million mechanical books are published annually, with to new titles appearing in English every year. Pop-up and movable books have also become popular for adults again. The easiest way to do that is to observe the works of the masters: buy great pop-up books and carefully disassemble them, learning the techniques of the best paper engineers by reverse-engineering their constructions.

The books I like the best are generally for children, where the designers are able to really cut loose and blend their talent for manipulating paper with beautiful illustrations and reality-bending shapes some great examples are listed in the Further Reading section. There are a few good books available on designing pop-ups. There are easily dozens of techniques; I casually reviewed my own work and counted at least two dozen different kinds of mechanisms. The good news is that a most of these techniques are based on just a handful of basic ideas.

Think of pop-ups like a guitar: there are only so many ways to pluck and strum the strings and rap on the body of the instrument, yet great guitarists are able to create a tremendous range of personally expressive and distinctive styles. I know from personal experience that the complexity of a card has a huge impact on how long it takes to build.

Remember that each cut and fold will have to be repeated for each card. That means that they are at their most effective when the card is open to a right angle. In the single-slit method, we fold the card and make a single cut. Typically we also make a single corresponding fold from the edge of Chapter One Chapter Figure 1. Despite its simplicity, this mechanism contains most of what we need to know about the geometry of pop-up cards.

Before we dig into the geometry, though, we should think about our options. I investigated two approaches to pop-up geometry: constraint systems and explicit modeling. But they have three big drawbacks for this application. First, the programs themselves are typically large and complex, which makes them hard to write and debug. Second, constraint systems are notoriously sensitive to issues of numerical stability. Calculations must be carried out very precisely, with a lot of attention given to the principles of numerical computation, including precision and rounding errors.

Even when the program itself is well designed, the inputs must obey the same standards. Constraint systems are very sensitive to seemingly small changes in the input. For example, d e Figure 1. These are photographs of paper models. Chapter One Chapter Some systems are able to break free of the region of bad answers and go hunting in a different and potentially more fruitful range of possible solutions, but this process can take a long time. But these problems seemed to me to make a constraint system an unlikely candidate for a small, interactive design program.

The alternative I followed was to write special-purpose code to explicitly calculate the geometry of the pop-up cards.

Items in search results

This approach has a few things going for it. One downside of writing the explicit geometry in the code is that it limits the designer to creating mechanisms that have already been prepared, so he or she cannot invent new mechanisms. I think this is a reasonable limitation, since there seem to be relatively few mechanisms in general use. If someone cooks up something surprisingly new, then it can be added to the library.

We begin with a card, or backing plane. Point A is on the central fold, and points C and D lie at equal distances from the fold along a line perpendicular to it. Before we make the cut, the line CD crosses the fold at point E. After the cut, I distinguish point E as that spot on the card where the cut crosses the fold, and point B as that point on the paper that is at the end of the folded segment.

The fold line itself is called LF. Points B and C do move. But a more general solution will prove useful later when we consider more complex types of cards. The key insight is to think of the construction in terms of spheres. The two points of intersection of the three spheres line on the dashed line that is perpendicular to the plane. Now imagine a plane through the centers of our three spheres, as shown in Figure 1. This line is called the radical axis. Since both of these points have the value 0 with respect to both circle equations, they must lie on the radical axis of those two circles.

This little bit of reasoning proves that if three circles are mutually intersecting, then their radical axes intersect at the unique point M. Our next step is to locate point M, given the three spheres. I do this by creating a plane for each pair of spheres. The plane contains the radical axis and is perpendicular to the plane that joins their centers. Of course, this is all the same information as the center, radii, and distances of the spheres.

Our plane passes through J with a normal parallel to C2 — C1. Intersecting any two of these planes gives us the dashed line of Figure 1. Which point do we want? Refer to Figure 1. If the circles of Figure 1. But this case never holds in our situation. The most extreme case is when the card is fully open or closed, and the circles are tangent; they never fully separate. Here the fold does not follow the crease of the backing card, but is at an angle to it. This variation gives the designer some more freedom to create slanted and forced-perspective effects.

In Figure 1. Although in action the card looks generally like Figure 1. The V-fold is one of the hardest pieces to design using paper and scissors, since one indirectly controls how much the plane leans back by changing the angle at the base of the piece when it is cut out; this angle is the V at the bottom of Figure 1. For example, the apex of the fold point E in Figure 1. So opening the card pops up the big V-fold, which then drives the smaller one to pop up as well. The tabs of a V-fold must be carefully glued in the right places, or the card may not open or close fully.

Depending on the placement of the V-fold on the support planes, it can be designed to fold either towards or away from the reader. When the planes of the V-fold become parallel to the support planes, all the folding lines become parallel to one another. Higher generations of V-folds work just like their parents, though they require a bit of care in programming to keep track of all the points during the opening and closing of the card.

The heart of any program lies in its data structures. For my Assistant, the most important data structure is the riser. A riser contains the information needed to position all the points of a single-slit or V-fold element. This recursion of risers pointing to risers ends with a special riser that is marked as the card. I maintain all of the risers in a list.

To position the risers, I simply start at the beginning of the list and look for a riser that can be positioned; that is, the risers it depends on have both already been positioned, and it has not already been positioned itself. The point is the sum of these two scaled vectors. I mark it as positioned and then continue running through the list. Since the risers are strictly hierarchical, this algorithm should always produce a completely-positioned card. The two coordinates associated with each point describe the scale factors on the edges of the riser the point depends on.

One of those edges is always the central edge of the riser. The entire card must be repositioned every time the designer changes the opening angle, which is typically a frequent operation. Here are the details behind the heart of the routine. Suppose we have three spheres, S1, S2, and S3, which have radii r1, r2 and r3. When two spheres intersect, the points in common form a circle.

We saw in Figure 1. Our plane passes through J with a normal parallel to C2 — C1 , shown in Figure 1. I package this up in a routine that takes as input two spheres and returns their plane of intersection. The three planes together are shown in Figure 1. I then normalize V that is, I scale it so that it has a length of 1. Now that we have a sphere and a parametric line, we can use standard ray-tracing techniques to intersect that line with any of the three spheres.

I use a library function that takes a line and a sphere and returns the two points of intersection. For numerical stability, I use the sphere with the largest radius if more than one sphere has the largest radius, I use one of them at random. Which one do we want? This choice is made at design time, of course, and is stored with the riser. I use the normal of the riser that is referenced by point D to categorize the two points: each point will be either on the positive or negative side of that riser.

The most common case is where the pop-up rises up from the card. This is useful when we want to position points on risers as they are moving around a fold axis. The line AB is shown by point A in orange and point B in yellow. The point to be rotated, Point P is in cyan off to one side. The point M in green is the point on AB that is closest to P. Essentially we rotate the point P in Figure 19 shows the vector H in red and V in purple. Essentially we rotate the point P in a point M: circle spanned by the normalized H and V vectors, and then re-center it to point M: Figure 1.

Basically that just means cascading a series of mechanisms one after the other. In terms of singleslit and V-fold mechanisms, it usually means placing a new mechanism on the card so that it is not powered by the central card fold, but rather by the induced creases Chapter The yellow ring shows the circle in this plane with center M and radius MP. The new point, Q, shown in red, lies on this circle. In terms of single-slit and V-fold mechanisms, it usually means placing a new mechanism on the card so that it is not powered by the central card fold, but rather by the induced creases of an earlier riser.

The Design Assistant I described in the last section handles this mechanism naturally, since it just involves placing the points of one riser with respect to an earlier one. But more importantly, each generation reduces the angle of the crease that the V-fold sits upon. When a V-fold sits on an open card, the two sides are flat.

As the sides come together at a smaller angle, as they do on higher-generation V-folds, it gets more difficult to both design and construct the card so it both works properly and looks good. The icebergs are V-folds. The ship is also a V-fold, based on one edge of a strap you can see the strap to the left of the ship since the card is still slightly open.

The books in the Further Reading section provide more details on these mechanisms. Of course, they can all be built with respect to any two risers, and built up in generations style one upon the other. The double slit, shown in Figure 1. The strap lets us do two things at once: displace the central fold to the left or right, and reverse the direction of the fold.

The geometry of the strap is easy to implement, since it always forms a parallelogram with the card. The two icebergs are standard V-folds that rise off the sides of the card. The ship is a V-fold that sits on one end of a strap that straddles the central fold.

Epub Dynamic Judaism The Essential Writings Of Mordecai M Kaplan

This is the schematic for Figure 1. The chairs are V-folds. The a b single-slit may be a little hard to see; think of the top of the strap as the slit. Many of the most surprising pop-up effects can be achieved through this kind of simple combination of basic mechanisms. The dragon pivots out of the card counterclockwise. At the extremes, you can shrink the side supports to create a mountain or tent, or shrink the support in the middle to make a valley.

The two chairs are built out of V-folds. That is, all the reader has to do is open the book or card, and the paper does its thing. There are a few popular mechanisms that allow the reader to take a more active role. In this mechanism, the page is actually made up of two sheets that sandwich the mechanism between them.

As the tab is pulled, the segment underneath tries to straighten out and bulges downward. You can get this effect for free if you use a complete collision-detection or constraint system, as I discussed earlier. The pull-tab is a nice way to create a card within a card. Really ambitious designers can include V-folds and other mechanisms inside this little mini-card, but one must be careful not to get carried away.

The risk is that people both adults and children often quite understandably think that if pulling the tab opens the mechanism, then pushing the tab should close it. Another popular technique is based on the idea of a wheel. The wheel has four parts, as shown in Figure 1. These holes can be of any shape and number as long as the card still holds together. A second card of the same size and shape except without the holes is usually made for the back. The two small parts in Figure 1.

The hub is easy to make once you know the secret! The assembly process is shown in Figure 1. The red dots in Figure 1. Notice that nothing gets glued to the wheel itself! Cut the wings so that the cuts in the center are just a little bit smaller than the disk cut out of the center of the wheel. When the whole sandwich is complete, you can a Chapter One Chapter The spokes on the unicycle turn when the wheel spins.

As the wheel turns the rider a rocks back and forth, as shown in the Figure. To make the rider rock, I perched the unicyclist on an arm that passes through a slot in the front of the card, as shown schematically in Figure 1. Inside the card, I attached a larger disk behind the wheel with the spokes printed on it, and then placed another hub on the outside of that disk. Thus as the main wheel goes around, the smaller hub on its edge goes with it. The rider is pulled up and down with the motion of the wheel and pivots when the wheel extends to the left or right of the slot.

This is bad enough when the card is opening, but it makes it almost impossible to close the card again without damaging it. One can certainly cook up all kinds of automatic schemes that move the points around algorithmically, and that will solve the technical side of the problem, but it may also change the aesthetics of the result. A really careful, algorithmically complete job of collision detection would certainly work well. It seemed easier to take a rough-and-ready approach inspired by the rendering technique of point sampling.

At each step, I completely position the card and then look for any edges that pass through any planes. If the designer clicks on any of those edges, a display shows all the angles where collisions occurred. The designer can then click to set the card to one of those angles, which will show the collision. This scheme is fast and has always worked for me. I bet you could get away with steps or even fewer, if the simulation time became too long.

So printing out the designed card is important. Gluing down the risers in the right position has always been tricky for me. But somehow we do have to provide tabs for gluing pieces into place. Note that these glue tabs are little trapezoids, not rectangles: particularly at the center of a V-fold, rectangular tabs would overlap. This would create an ugly bump and also make the card a little harder to close.

To help me assemble cards, I have a switch to turn on the printing of guide lines on each riser that has another riser built upon it. This is just a colored line where the riser should be glued down. I then print the tabs with the same color. So anywhere I see a red line, for example, I know that a riser with a red-colored tab should be glued down on that line.

One solution is to actually cut a slit where the riser meets the card, and then slip the tab through the slit, gluing it to the underside of the card. This requires a really sharp crease to make sure the mechanisms can rise and fall properly. A better approach would be to print the texture of the base riser on the tab of the riser that sits upon it, so that you can glue down the tab and the art is seamless.

This requires a color printer that can print on both sides of the page with very good registration. Of course, we could be lazy and print one piece per page, but that would be wasteful. What we really want to do is to pack the pieces together into the smallest number of pages.

Those algorithms can be complex. My simple technique is a greedy algorithm that packs the pieces in one at a time from largest to smallest. I begin by creating a data structure called a page, which contains a list of rectangles. This list begins with a single rectangle that spans the page. I run through the list of pieces as a one-time preprocess and sort them by the size of their bounding rectangles. I start with the largest rectangle and work my way down to the smallest, placing them as I go and creating new pages when necessary.

I try to position the bounding rectangle of the piece on this page, trying it in both horizontal and vertical orientations. In this way I tend to make a bunch of pages that start out with just one or two big pieces and a lot of empty space, but then that space gets nibbled away by the smaller pieces as they arrive and are placed. Without this rotation, the pieces would have taken up two pages. There is some wastage, and the pieces could surely be packed more tightly. Notice that the strap and one of the icebergs are rotated 90 degrees.

For example, we could have a foreground, several middle grounds, and a background. The system could then take these segmented regions of the photo, place them on a series of V-folds that are spaced roughly as the objects in the scene are spaced, and create a three-dimensional version of a photograph, sort of like Figure 1. Another fun project would be to create pop-ups automatically from three-dimensional scene descriptions.

The advantage is that the pieces can be made available on any image medium, from a printed journal to the web. Then someone just prints them out, assembles them, and enjoys the view. It would be interesting to automatically incorporate forcedperspective illusions onto the planes to give the card an even richer illusion of depth. For example, in Figure 1. There are many such possibilities, and it would be nice to provide them explicitly to the designer. I think that these are all rich research topics full of juicy pieces of geometry, optimization, segmentation, and interface design.

Carter and James Diaz Simon Schuster, Another book offers fewer mechanisms, but gives more detail on each one, including some preprinted pages for you to cut out and fold up; this book is Paper Engineering by Mark Hiner Tarquin Publications, Everyone has their favorite pop-up books. Like any other kind of books, what delights one person can leave another bored. These are by no means exhaustive lists, nor do they include all my favorites; that would take pages.

Some people do both the illustrations and paper engineering for their books. Robert Sabuda, one of the most respected paper engineers working today, has created an international online gallery of great pop-up work from all over the world. Three library web sites were invaluable to me in compiling my history of pop-up books. But even better, they contain many photographs of mechanical books through history. They show animated versions of the books being worked, and even provide videos of some books being opened.

Kramer MIT Press, Some of the material in this chapter was carried out while I worked at Microsoft Research. Lee, B. Tor, and E. Soo Computers Graphics, 20 1 , , pgs. Kergosien, Hironoba Gotoda, and Tosiyasu L. Milenkovic, K.

Daniels, and Z. The more people you tell, the less your secret is secure. So usually we try to control the spread of secrets as much as possible. Of all the ways to share a secret, perhaps the most dangerous is to write it down on paper in plain language. That has the advantages of permanence and some reduction in the need to repeat yourself verbally, but it runs a big risk: anyone who can get hold of the paper can read your secret, even years later. But then you have another problem, which is how to best destroy the paper. Both of these look like tall garbage cans with a mechanical unit on the top into which you feed sheets of paper.

The strip-cutters slice pages into parallel strips, usually ranging from 0. The cross-cutters add another step by cutting each of these strips into shorter segments, typically between 1. Using one of these shredding machines seems to me like using a simple lock on a door. So they run them through their strip-cut shredders, and then give the strips to their employees to use as disposable packing material.

The employees later give that material to the court to be used as evidence. Are the secrets that were printed on those documents safe? In the case of shredded documents, the pieces are vertical strips of paper containing pages of text. Other applications include repairing a broken object that has shattered or assembling a jigsaw puzzle. Chapter Two Chapter First, do I have two objects that are likely to be matches? Second, do they indeed match? Each 8. In practice, the left and right margins of each page are generally about 1.

If we eliminate these allwhite strips, then we have 6 inches of printed width, or strips per page. So if someone shredded pages, there would be about 96, strips, which often all go into a single bag below the shredder and get thrown away en masse. In contrast, jigsaw puzzles that are sold in the stores seem to max out at about pieces. A good matching test is important to make sure that pieces are correctly combined. It also needs to look for a good match, but be tolerant of near-matches. Furthermore, borders and edges are common features, and they might happen to align with the piece edges.

This is often the case for text. Consider a letter like a capital I, or lower-case L. These both have most of their information in a vertical line, aligned to the long side of the page. If the shredding machine cuts just to the left of one of these letters, there will be nothing shared between the two strips over this border. In fact, much printed text is this way: two strips that started out adjacent have frequent regions where corresponding regions of the two strips are opposite in color: one edge is black and the other is white.

Thus our matching test needs to be able to pick up on what similarities are available, and not overlypenalize mismatches. These are contradictory desires, of course, which is what makes matching functions so interesting! To make things easier, I used two sets of public-domain images to develop my reconstruction software. Figure 2. I decided to code things so that the score indicates the degree of mismatch. Thus the higher the score, the worse the match between the pieces. The principle at work here is coherence. After all, if the images were random noise that is, just black and white dots with no features , then matching up strips would be hopeless, since statistically no pair of strips would be any better than any other pair.

The most obvious place to start is just to compare the RGB values of adjacent pixels over the edge and add them up. By looking through the scrambled pieces, I found that the leftmost strip of this image was assigned strip number 69, and that the strip that was originally to its right became strip The scores range from a low of 15, for strip 27, to a high score of , Number 27 does seem to stand out, but perhaps we can improve 75 25 50 the data. In Figure 2. Consider the real world for a moment. Paper has variations, and scanners are noisy.

The ratio of the spike to the minimum value is about The scores range from a low of 8, for strip 27, to a high score of , Here I used the same value of 10 for 0. The noise 0. The ratio between that highest spike to the smallest value in the plot is about 28, which is a b nice improvement. My hypothesis is that since artists are using the same visual system as their audience, they tend to create works that are tailored to that system.

I encoded this observation into a metric D2 that weights the three color components individually. The scores range from a low of 2, for strip 27, to a high score of 81, In my experience this weighting of the colors can lead to a bit of an improvement for color images. Remember that our goal is to make the spike for slice 27 as unambiguous as possible. A useful way to crank up differences in data is to exponentiate them. This leads to a third metric, D3: 0. Experiments with text and color images have led me to settle on D3 for my testing function.

On each run, though, I have the opportunity to tweak all the variables, weights, thresholds, and exponents, in order to accommodate the peculiarities of different printers, scanners, paper types, etc. So that we can see how this metric performs on a larger problem, Figure 2. Those spikes are where the metric says the two pieces match up well. This basically pushes all the noise to zero and leaves just the spikes. Some of the spikes are in the same place as in Figure 2. If we could afford to run this metric on all the objects in the database, it suggests an easy way to get a good initial match: just compute all the pairings, and then threshold the result until just the right number of matches remain.

For example, when we have four images of ten strips each, there are 36 good pairings to be found. How might we use this data to assemble the pieces? First, we hardly ever talk about our unsuccessful ideas in print. Most research papers state the problem they want to solve, and then present the solution that worked. But where do we document the dead ends? We all go through them, and yet we never talk about them. Curiously, the number of strips involved changes the result, but not the general feel of the errors. What went wrong? But then when we hit the right edge of the picture, the best remaining strip to its right is essentially a random choice.

Then we start again. Thus we end up getting chunks of images that get smaller and smaller as we work to the right. This is encouraging, but still not quite right. As I thought about it more, I realized that this left-to-right growing approach could be endlessly tweaked, but was probably doomed in the long run. One big problem of course is that it requires access to all the pairing data, which for a large data set will be prohibitive. For Figure 2. The shame here is that this now removes the possibility of ever getting the CD pairing, which had a very low score.

Where is C to go? Obviously we can handle that as a special case, but if we prevent cycles of any size from forming, then single-piece cycles are prevented as well. I prevent the formation of cycles with a brute-force technique. Whenever I want to add a piece to either end of a cluster, I check the other end of the cluster to see if that piece is already there. If so, I skip adding that one in and move on to the next-best pairing. The only exception to this rule is when all the pieces have been placed; then the very last one will necessarily make a single big cycle that contains the whole database.

So to recap, I search the database for the lowest-scored pair and put those two pieces together. Then I search for the next lowest pair, and assemble those, and so on, until all the pieces have been placed. When I create the output image, I use the strip to the right of that border as my starting point. Suppose that we had a few thousand strips, or even a couple of orders of magnitude more. To work with large data sets, I scanned in some PDF pages of text for a set of columns I wrote in on quantum computing. There were 51 pages in all, with text in the middle six inches of the page, giving me horizontal inches of text.

Cutting those pages into 0. All the pairwise scores for this data set would mean creating and storing just under six million scores. Though one can imagine handling six million scores, if I had just pages to reassemble, that would be million scores, and things would be getting pretty well out of hand by that point. My approach was to sort the pieces that had a reasonable likelihood of belonging together into smaller bins. Then I could apply the clustering algorithm of the last section just to the contents of the bins.

For example, using just ten bins for the QC data set results in about strips per bin, which is even smaller than the image-based data sets I used above when each image was cut into 80 strips, there were strips to be assembled. Those data sets assembled in about a second on my little home PC using entirely unoptimized code.

If I had pages or about 12, strips , then using 60 bins would let us assemble the entire database in about a minute. A piece might appear in more than one bin if its left side matches one group and its right side another. The trick to this approach is to make sure that we get the right pieces into the bins. This is a question of heuristics, or approaches that seem to make sense but may not have a deep theoretical foundation. Basically I just thought about what tests might be good at picking up features between strips and tried them out.

I experimented with several different sorting heuristics, using both the QC data set, and the thin and wide image data sets. I set up as many bins as I wanted, each holding a range of luminances from 0 to 1. Since many of the text pieces were near midgray in average intensity, I used pretty big bins for the brightest and darkest ends, and smaller ones in the middle. For example, one bin might hold all sides with luminances in the range 0.

I call this sorter L, for luminance. That meant that pieces that ought to match never got the chance to see each other. So I opened up the range of each bin so that they overlap.

Shop by category

A factor f that the user can set determines how much the bins overlap. I call this overlapping luminance sorter Lf. I implemented a run-length metric that tries to get at some of this information. I start at the top of the page and count the lengths of continuous sequences of the same color. I save the length and color of the longest run, and the arithmetic average of all the runs. I used these values in different ways to create a few different sorters. One useful value comes from multiplying the longest-run color by its length, taking its luminance, and dividing by the average run-length.

In another sorter I use just the luminance of the color in the longest run, giving me sorter Sf. In practice, I use them all. So each strip gets run through each sorter and placed into a bin from that sorter. Then I score all the strips in each bin for all the sorters. That way if one of the sorters misses out on connecting two pieces that really belong together, one of the other sorters has a chance to catch it. For example, we might know that we were scanning in pages of text on standard American-sized letter paper. Printers generally need at least a half-inch of margin on both sides of the text.

If we found that we were making a cluster that was more than about 7. We could look for such features and give them weight in the sorting step. In the case of text, we could precede the matching process with a step of optical character recognition on the strip in both its original orientation, and after rotating it degrees. In the case of images, the problem is a little harder. As I mentioned above, some shredding machines cut the strips into smaller pieces. The top and bottom of many of these crosscut strips will be white since that edge will fall between lines of text.

Since these edges are all completely white, they will have near-perfect scores of zero or almost zero. My approach is to look for edges that are all the same color, within some threshold. If an edge is a single color or colors very close to a single color , then it simply does not take part in the matching process. Using just this simple test, I matched my QC data using strip lengths of 1.

I applied the sorting and clustering techniques above and got very good, but not perfect, results. I think a better sorting metric would go a long way here. A fun application of this technique is to solve jigsaw puzzles.


  • Account Options.
  • Chinese Perspectives on International Investment Law.
  • Nyambe: Ancestral Vault (A sourcebook for Nyambe)(d20 Fantasy Roleplaying).
  • Processing for Visual Artists?
  • Printed Citations to Xah Lee Site.
  • Programming - Best books online.

To test this out, I took a photograph and drew jigsaw-shaped pieces on it in Photoshop. I then wrote a program that broke the pieces apart and scattered them. To reconstruct the image, I simply used my assembly algorithm. This piece puzzle, shown in Figure 2. This really surprised me, since I was kind of looking forward to writing some code to account for the shape information of the pieces.

Finding a nice characterization of the shapes so that one could match them up quickly on a purely geometric basis would be an interesting project. When reconstructing a document, sometimes strips will be missing. Missing cross-cut pieces are more troublesome and will result in irregularly-shaped chunks of the original images.

If you are putting a vase back together again, one thing that helps is the fact that the vase has some thickness: the shapes go together not just based on a two-dimensional outline, like a jigsaw puzzle piece, but also in terms of how the edges are scalloped and shaped. Chapter Three Chapter Boats and ships do the same thing, as shown in Figure 3. Could the ducks be induced to make interesting patterns out of their overlapping wakes? There have been thousands of papers and hundreds of books written on the simulation of water, many of which are intricately detailed.

Figure 3. That air mixes with the other air in the room, creating a slightly higher air pressure on your skin. But water is not compressible. This principle is illustrated by a famous and probably apocryphal story of the Greek philosopher Archimedes of Syracuse who lived around B. The story begins with the King coming to Archimedes with a problem. The King had purchased a new crown of solid gold, but the King was suspicious and thought that perhaps the artisans who made the crown had cheated, and simply melted a layer of gold leaf over a core of some cheaper metal.

He asked Archimedes to determine if the crown really was solid gold, but with the condition that Archimedes not damage or alter the crown in any way. This seemed an impossible problem. Then one day Archimedes climbed into a bathtub, causing the water to slosh over the sides. So Archimedes dunked the crown into a tub of water and measured how much water spilled out. Then he weighed the crown, and divided the weight by the volume to get the average density of the crown. It turned out to be the density of gold, so it meant that unless the artisans had found a way to make another metal with the same density as gold which nobody knew how to do , then the crown was indeed made of solid gold after all.

In real life, of course, eventually that downward-moving water will hit the bottom and then move to the sides. Timman, A. Hermans, and G. Hsiao Delft University Press, The curve K is given by two expressions, which give us its x and y components. Basically this is a shape control that accommodates the fact that the wave gets larger as time goes on.

K is sometimes called a phase wave. In Notice that the waves all lie in a cone behind the duck. These cusps appear where the derivatives of K x and K y are both simultaneously zero with respect to the variable u. The Kelvin angle is where these are both zero simultaneously. If we plug this value for u into the curve K above, we get a point at about -1 The angle between the X axis and the line from -1 the origin to this point can be found from this triangle to be about I like geometric approaches in general for their intuitive appeal, but this one also helps us understand something about water waves in the process.

These are drawn as circles in Figure 3. An interesting 2 When many different waves of almost the same wavelength combine with each other, the result is that they tend to cancel out in some places and reinforce in other places. In Figure 3. So although the plane makes disturbances of many different frequencies, they all radiate away from the point at the same speed.

That means that the plane is moving faster than the waves are expanding. Looking closely at Figure 3. So in Figure 3. The circle was created when the plane was at point A, but the plane is now at point B. If we write c for the speed of sound, then the radius of the circle is ct. The situation will turn out to be somewhat different than the airplane because water waves of different wavelengths travel at different speeds. We say that C the waves have combined to create a series C of packets.

A B This is what happens to the water waves created by our duck. At each point the duck creates a variety of waves of slightly different wavelengths, but rather than b disturbing all the water uniformly, they create easily-discerned packets, as in Figure 3. How fast does the packet move? But the packet moves at the group velocity, which 3r in deep water is exactly half the phase velocity.

Fast-moving cars arrive at the tail of the pack and are forced to slow down, while cars near the front of the bunch are able to get back up to speed and drive away. These points Ci are the points that enclose the individual waves. But remember that these waves combine to form a packet, as in Figure 3.