Hi Glen, On 7/28/2015 10:57 AM, glen herrmannsfeldt wrote:> Tim Wescott <seemywebsite@myfooter.really> wrote: >> On Mon, 27 Jul 2015 06:53:11 -0700, Don Y wrote: > >>> {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} defining a cubic bezier. >>> with Xi, Yi all expressed in Qm.n > >>> Define an efficient, closed-form expression/constant time algorithm to >>> characterize (describe) the curve. > >> Are these the control points, or four points on the curve? If they're >> the control points then I'm pretty sure that you can just scrape the real- >> number answer out of Wikipedia and it'll work right. It is, IIRC, >> straightforward adds and multiplies, so converting it to Qm.n should be >> easy. > > Metafont does it for appropriate values of m and n. > > As well as I remember it, Metafont has a routine that will take a > Qm.n value (Maybe with m=9 and n=22, plus sign) multiply it by > some value (generating a double length product) and dividing by > another value. As this is two instructions on many computers, it > is suggested to use an assembly routine, but he does it in > Pascal. > > Anyway, you might need wider intermediate values.It's not the actual *math* operations that are the problem. Rather, it is how the granularity bastardizes the "model space" *before* the math (even *perfect* math!) is applied! E.g., imagine drawing a circle of radius 1/2 centered at (0,0) where the only "resolvable" points are Qn.0! Depending on how you round, you either get a *point* at (0,0) or a *rhombus* having sides of length *sqrt(2)* or a *square* having sides of length *2*! For bezier curves, the many different shapes possible quickly become "compromised" by the underlying math. E.g., a curve can end up looking like a line; an 'S' can end up looking like a 'C', etc. So, your "abstract math" may indicate that a given set of coefficients (control points) will yield a *curve* but you end up with a *line* -- or even a *point*!
Nice and terse -- like on an EXAM!
Started by ●July 27, 2015
Reply by ●July 29, 20152015-07-29
Reply by ●July 29, 20152015-07-29
On Tue, 28 Jul 2015 15:16:59 -0500, Tim Wescott <seemywebsite@myfooter.really> wrote:>On Tue, 28 Jul 2015 09:33:10 -0700, Don Y wrote: > >>>>> {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} defining a cubic bezier. >>>>> with Xi, Yi all expressed in Qm.n > >> "Hmmm... how do I *predict* what the curve will look like just from an >> examination of this set of four points? >> Obviously they exactly define the curve so that information is encoded >> in them, *somehow*. Without bearing the expense of actually drawing >> them and examining them with human eyes, >> how can I extract that information algorithmically?" > > : >Step 4: Find the EASY AND VERY RELEVANT math under the heading "Cubic >Besier Curves".Tim, Don knows what a bezier is and how to compute the curve. What he wants is a way to guess the shape of the curve *without* computing it. He is trying to use curve fitting to do shape recognition, and I suspect what he wants is a quick, cheap way to filter out templates that can't possibly match. There's not a whole lot you can say about a cubic bezier just by looking at its point representation. If you have b = {p1,p2,p3,p4} and consider the vectors: ->p1p4, ->p1p2, ->p1p3 then you can you use dot product to tell whether its a line, a "C", or an "S", and in which direction it starts, by looking at on which side of ->p1p4 the control points lie. You can tell whether the half curve relatively is a hill or some kind of weird ass balloon by dropping perpendiculars from the control points to the _line_ p1p4 and noting whether the intersections lie on or outside the _segment_ p1p4. You can make (comparitive only) proportional guesses at amplitude by looking at the areas of the triangles /_p1p2p4 and /_p1p3p4. If you scale 2 beziers such that ->p1p4 is the same length in each, then you can do some rough proportional comparisons of these features. That's all I can think of offhand that is cheap and constant time to compute. I doubt any of it will help Don much ... I suspect he already knows all of these tricks and they are too blunt to be of use. George
Reply by ●July 29, 20152015-07-29
Hi George, On 7/28/2015 8:35 PM, George Neuner wrote:> On Tue, 28 Jul 2015 15:16:59 -0500, Tim Wescott > <seemywebsite@myfooter.really> wrote: > >> On Tue, 28 Jul 2015 09:33:10 -0700, Don Y wrote: >> >>>>>> {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} defining a cubic bezier. >>>>>> with Xi, Yi all expressed in Qm.n >> >>> "Hmmm... how do I *predict* what the curve will look like just from an >>> examination of this set of four points? >>> Obviously they exactly define the curve so that information is encoded >>> in them, *somehow*. Without bearing the expense of actually drawing >>> them and examining them with human eyes, >>> how can I extract that information algorithmically?" >> >> : >> Step 4: Find the EASY AND VERY RELEVANT math under the heading "Cubic >> Besier Curves". > > Tim, > > Don knows what a bezier is and how to compute the curve. What he > wants is a way to guess the shape of the curve *without* computing it.Exactly. I want to inspect the coefficients/parameters and *infer* the shape that would be evident (to a human observer) had I actually incurred the cost of drawing it and *presenting* it to the observer! Imagine actually *drawing* the curve -- even if you could do so "for free". Now, WITHOUT USING HUMAN EYES AND MEATWARE, how would you analyze the shape of the DRAWN CURVE? Are you going to design an image analysis package that can take a bitmap image and decide if it represents a closed loop, point, S, C, etc.? Sure sounds like a silly way of getting at the same data that is already encoded in the parameters (control points) defining that curve!> He is trying to use curve fitting to do shape recognition, and I > suspect what he wants is a quick, cheap way to filter out templates > that can't possibly match.Actually, I started on that path with the gesture recognizer (years? ago). Now, I have found the utility of the beziers at representing "general shapes" to be addictive and apply it in many other places.> There's not a whole lot you can say about a cubic bezier just by > looking at its point representation.Check your mail. There is actually a *lot* that can be said, "in theory" ("in practice", with a particular numerical representation, things get murky, fast!)> If you have b = {p1,p2,p3,p4} and consider the vectors: ->p1p4, > ->p1p2, ->p1p3 then you can you use dot product to tell whether its > a line, a "C", or an "S", and in which direction it starts, by looking > at on which side of ->p1p4 the control points lie. > > You can tell whether the half curve relatively is a hill or some kind > of weird ass balloon by dropping perpendiculars from the control > points to the _line_ p1p4 and noting whether the intersections lie on > or outside the _segment_ p1p4. > > You can make (comparitive only) proportional guesses at amplitude by > looking at the areas of the triangles /_p1p2p4 and /_p1p3p4. > > If you scale 2 beziers such that ->p1p4 is the same length in each, > then you can do some rough proportional comparisons of these features.If (at least) two points are coincident and the remaining points are coincident, then you have a point or a line segment. If p1 == p4 then you have a closed loop (or a point/line). etc. Additionally, knowing any of these things expedites other processing (e.g., including drawing the curves, finding length, curvature, subtended angle, convex hull determination, etc.) As each of these can, otherwise, be expensive operations, any "hints" can make things much more efficient. E.g., if you KNOW the Bezier represents a *line*, then why bother trying to COMPUTE it's curvature?? If you know it is a POINT, then why bother computing its (expensive) *length*? E.g., only a fool would process the following expression sequentially: X^A * Y * Z * 0 Likewise, that same fool would blindly apply quadratic formula to solving for roots of a quadratic! I.e., UNDERSTAND the math that you are using lest you blindly lead yourself (and your code) into a dead-end!> That's all I can think of offhand that is cheap and constant time to > compute. I doubt any of it will help Don much ... I suspect he > already knows all of these tricks and they are too blunt to be of use.The biggest problem is dealing with the fact that the "math" assumes you can represent rational numbers to infinite precision and for little cost. If that were the case, the two immediately preceding examples wouldn't bite people in the *ss!
Reply by ●July 29, 20152015-07-29
On 7/28/2015 10:49 PM, Don Y wrote:> > (sigh) No, you clearly don't understand the question being asked.Yeah! Now you are catching on. No one understands the question you are asking, but it's not because they know nothing about the concept. It's because it is so hard to understand what you write!> Let's try something simpler.Many, many rambling words with no clear purpose later...> Perhaps now you understand why lots of pretty equations on Wikipedia > are completely USELESS in addressing this issue?What was the issue again? -- Rick
Reply by ●July 29, 20152015-07-29
On 7/28/2015 8:15 PM, Don Y wrote:> *This* is how the email conversation started. I've elided things > that I don't want discussed in a public forum (e.g., the "what" > and "why" motivating the question). Of course, had I posted something > *this* long, *here*, folks with short attention spans wouldn't have > been able to make it to the end of the post... (I guess they've > never had to read or write 100's of pages of detailed specifications, > "rationales", etc. for their products; just bulleted "feature lists" :< )And *this* is the paper that I eventually found to address the *first* of these issues: @article{Stone:1989:GCP:77055.77056, author = {Stone, Maureen C. and DeRose, Tony D.}, title = {A Geometric Characterization of Parametric Cubic Curves}, journal = {ACM Trans. Graph.}, issue_date = {July 1989}, volume = {8}, number = {3}, month = jul, year = {1989}, issn = {0730-0301}, pages = {147--163}, numpages = {17}, url = {http://doi.acm.org/10.1145/77055.77056}, doi = {10.1145/77055.77056}, acmid = {77056}, publisher = {ACM}, address = {New York, NY, USA}, } A copy of which seems to be available, here: <http://graphics.pixar.com/people/derose/publications/CubicClassification/paper.pdf> Interestingly, the title: A Geometric Characterization of Parametric Cubic Curves mimics the way I posed the question: {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} defining a cubic bezier. with Xi, Yi all expressed in Qm.n Define an efficient, closed-form expression/constant time algorithm to characterize (describe) the curve. You can wade through the 17pp describing their process. And see how they characterize the curves using essentially the same sorts of descriptions that I site in my "lengthy" descriptions, up-thread. N.B. No genetic ties to the authors so I guess it must *take* a fair bit of words to express the concepts involved. *But*, they offer *pictures* for folks who can't deal with abstract mathematical concepts... (Hmmm... "picture", "thousand words"...) After reading it, you can *then* think about how it falls down with specific numerical encodings (precision, etc.).
Reply by ●July 29, 20152015-07-29
On 7/27/2015 9:59 PM, Clifford Heath wrote:> On 29/07/15 15:42, Don Y wrote: >> On 7/28/2015 8:35 PM, George Neuner wrote: >>> Don knows what a bezier is and how to compute the curve. What he >>> wants is a way to guess the shape of the curve *without* computing it. > >> Exactly. I want to inspect the coefficients/parameters and *infer* >> the shape that would be evident (to a human observer) had I actually >> incurred the cost of drawing it and *presenting* it to the observer! > >> Imagine actually *drawing* the curve -- even if you could do so "for >> free". Now, WITHOUT USING HUMAN EYES AND MEATWARE, how would you >> analyze the shape of the DRAWN CURVE? Are you going to design an >> image analysis package that can take a bitmap image and decide if >> it represents a closed loop, point, S, C, etc.? > >>> There's not a whole lot you can say about a cubic bezier just by >>> looking at its point representation. >> >> Check your mail. There is actually a *lot* that can be said, "in >> theory" ("in practice", with a particular numerical representation, >> things get murky, fast!) > > Have you actually used a drawing tool that allows you to adjust such a curve?Sure, several!> The reason why such tools are nice to use it that they're so intuitive; that > is, it's easy to know what to tweak to get the result you want. In other words, > it's just not as hard as you make out.You've totally missed the point. Please reread George's post -- if you can't stay focused on the task long enough to read *mine*. Or, do George's *fewer* words still leave you confused as to the intent??> The direction of departure from p1 is towards p2. The curvature is less at that > end (the curve turns towards its destination slower) if the distance between > them is greater. The same is true at the other end. > > There, I described the bezier curve in 38 words. I can't explain why you think > it's so complicated, or can't ask the question more simply.Because I am not *drawing* curves interactively! An *algorithm* is creating *models* as cubic beziers. And, another algorithm is using those *models* in its calculations. No human eyes ever *see* the curves. No one "notices" that this curve has degenerated to a point (due to the resolution of the underlying representational system).> As for the rest of your ramblings, my standard response: tl;dr. (Since you seem > to be Google-impaired, that means "too long; didn't read).As you're so great with google, find an answer to the question I asked -- not the question you *think* I asked! :> Note that the folks that I've corresponded with re: this exact topic managed to point me to the paper mentioned up-thread. So, clearly *they* "got it". Perhaps they have better reading skills? Or, *don't* suffer from ADHD?? I get it: you can't answer the question. And, don't care to learn anything in the process. [Sad how quickly some folks give up on learning and applying new concepts.]
Reply by ●July 29, 20152015-07-29
On 7/28/15 11:15 PM, Don Y wrote:> *This* is how the email conversation started. I've elided things > that I don't want discussed in a public forum (e.g., the "what" > and "why" motivating the question). Of course, had I posted something > *this* long, *here*, folks with short attention spans wouldn't have > been able to make it to the end of the post... (I guess they've > never had to read or write 100's of pages of detailed specifications, > "rationales", etc. for their products; just bulleted "feature lists" :< )But WHY is a very important part of properly answering a question, especially if it isn't fully defined. Looking at your original question, the "exam" answer would be: P(t) = (1-t)^3*P0 + 3(1-t)^2*t*P1 + 3(1-t)*t^2*P2 + t^3*P3 This equation fully describes the Bezier curve. (And is probably worthless to what you have eventually described as what you want). There were a couple of problems with the question. First, 4 points, by themselves, don't define a Bezier curve. Only when you assign meaning to the points (First and last are the starting and ending points, second defines direction of departure from the first, and the third the direction of arrival at the last). On an exam, you have the context of the course to provide this information, as a free standing question if forces a big assumption. The second, and biggest, is that "Describe" is a very ambiguous word. There are LOTS of ways to describe something.> > So, instead, I post a very *terse* question -- then spend MORE keystrokes > clarifying misunderstandings, etc.Terse as in omitting important information about what you REALLY want. This is the problem often with your questions. There seem to be invariably some details missing from the problem statement, often dealing with the sort of answer you are looking for, because you aren't looking for the "pat" answer. It requires thought to describe something unusual in text.> > -----8<-------8<-------8<------- > For example, given an equation of the form: > y = mx+ b > damn near everyone would describe this as something akin to: > a line > a line having slope 'm' > a line having slope 'm' with a y-intercept of 'b' > a line having x- and y-intercepts of '-b/m' and 'b' > etc. > > Similarly, given: > r^2 = (x-X0)^2 + (y-Y0)^2 > would be described as one of: > a circle > a circle having radius 'r' > a circle of radius 'r' centered at (X0,Y0) > etc. E.g., you *wouldn't* (typically) hear it described as: > a circle having an area of pi*r^2 units > > The same holds true for parabolae, ellipses, etc. Along > with polynomials of various degrees. > > The "equation" encodes the behavior of the "graph" while the > *coefficients* determine the CHARACTEISTICS of a particular > *instance*. E.g., a parabola that holds/spills water, an > ellipse with high eccentricity, a circle with a large diameter, > etc. >To start off, the forms you have provided, may be "classical" descriptions of those curves, but are actually special cases of the more general canonical expressions. A generalized equation for a line, is ax + by + c = 0 (Note, a given line will have a family of expressions of this form as we can scale the values, but it is difficult to factor that out, as any of the terms might be 0, The various rations of these terms give us a number of characteristics of the line (slope, intercept, etc). Similarly, for a quadratic, we get the generic equation: ax^2 + bxy + cy^2 + dx + ey + f = 0 (Note, not all values will lead to a curve, many lead to the empty set) Relationships between the coefficients (now not just ratios) give rise to various descriptions of the curve, things like if a = c != 0, and b = 0 then assuming you get a solution, it will be a circle (or the degenerate circle of a point) (and you can come up with an formula to give you the radius which if real, indicates that you do have a circle). Note here, that asking just to "Describe" the curve is a meaningless question, there are TOO MANY things that could be described about it. If given a particular question, we can look at how practical it would be to extract that characteristic from the description. But given an uncountably infinite question (describe), a "constant time" solution is impossible. Provide a finite list of characteristics that are desired, and it can be determined if closed form expressions for them can be obtained. If YOU don't provide the list of characteristics, you can't complain that the other person didn't give the ones you were interested in or provides stuff you didn't care about. Note also, the concept given of "graphing" the equation did meet the requirements, as a finite resolution graph of a Bezier curve can be computed in constant time. We have the same problem with
Reply by ●July 29, 20152015-07-29
On 7/28/2015 12:08 AM, Clifford Heath wrote:> On 29/07/15 20:01, Don Y wrote: >> [Sad how quickly some folks give up on learning and applying new concepts.] > > I have (and am) learning more than most people will ever conceive possible. In > part, I do it by avoiding wading thigh-deep in mounds of ill-constructed > verbiage. But I'll make an exception in this case. In fact, I often do for your > postings, because you often post genuinely interesting problems. That's what > makes the verbose style so disappointing. > > What are these "models" you speak of? How are they represented? You never > defined that.A bezier is a model. What "physical"/virtual entity it models is immaterial; it models a path/curve. If I post details of an application, then the discussion wanders off into "Why are you doing it THAT way? etc." If I answer (to be polite), then it's "more verbiage" -- and invariably it doesn't end up benefitting *me*. Their curiosity satisfied, the querant "goes silent" (nothing to say wrt the question posed). [Trust me, I've been here for more than 20 years. I *know* what sorts of replies I've encountered!]> Hint: The most concise model of a bezier *is* the definition of the four > points. That's why we use them. > > Your original question was this: > > {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} defining a cubic bezier. > with Xi, Yi all expressed in Qm.n > > Define an efficient, closed-form expression/constant time algorithm > to characterize (describe) the curve. > > You haven't defined what you mean by "characterize". How about giving us one or > two examples, in your first post (not 20 paragraphs, just a quick example!).Did you read the paper? Did you notice the title used effectively the same sort of wording? I.e., folks who are intimately concerned with Beziers would know what "characterizing" them would mean. Just like someone intimately familiar with circles would know how a *circle* would be characterized (repeating the definition I set forth {P1, P2, P3, P4} would obviously NOT be the sought after answer!) I systematically presented examples of how you would "characterize" different types of "curves/graphs/equations" so folks could see the common aspect in each of those characterizations. In each case, it boiled down to how parameters/coefficients affected the resulting graph/curve/plot/etc. And, that you could omit the "equation" and just use those parameters and a reference to the *type* of equation as being equivalent to actually specifying the equation (with coefficients) explicitly. If I said "a circle centered at (2,5) having radius of 8" you would, no doubt, have no problem *visualizing* it AND drafting the equation that represents it. An *algorithm* (without the benefit of human sight) could similarly take that characterization and use it, effectively, in its computations.> The most efficient expression to *describe* the curve is this: > {(X1,Y1), (X2,Y2), (X3,Y3), (X4,Y4)} > > Pretty simple, isn't it? And you wonder why we don't read your long versions, > when each sentence is just as lacking in coherence and/or clarity.Given that I *stated* THAT, *exactly*, wouldn't it seem obvious that the answer I sought was NOT "how can I describe the cubic Bezier described by THESE FOUR POINTS"? :> Would you ever expect an EXAM question to be answerable with "the answer is explicitly stated in the question, above"? If encountered on an exam, would you leave your answer BLANK? Or, would you invest some effort trying to understand what is LIKELY being asked??> If you want to know things like: does the curve form an S-shape, you can get > that from the angle between P1-P2 and P3-P4.What if P1=P2? P3=P4? P1=P2=P3=P4? Remember, this is an *algorithm* that is making these decisions/extracting this data. Not meatware.> But you need to ask for the kinds > of "characterization" you care about. In *64* paragraphs (yes, I counted), you > *eventually* danced around the idea... but far too late - you'd lost your > audience already.If you are intimately familiar with Beziers, you would recognize that they can be used to represent many different types of "curves". Note the authors of the cited article knew as much. And, expected their audience to know a similar amount. Otherwise, they could have titled their paper, "How to tell the SHAPE of a given cubic Bezier". Wouldn't that have been more informative??> I want to engage with your topics, I really do. You just make it too hard, > unnecessarily.Note that in the last few days, I've been accused of saying too much, and too little. I've been accused of not knowing how to use Wikipedia (and even the Internet itself!) or Google. From *my* perspective, it looks like folks want to be spoon fed; then complain that the spoon is in the way! Pick one, guys. You want terse? I'll keep my post REAALLY short and sweet. If you need more information, then I guess I won't be able to benefit from your deep experience! Because "followups" get met with the same complaint about verbosity. I posted the initial message that started off the email exchange on this subject. The folks I correspond directly with tolerate or welcome the detailed explanations. Most aren't interested in going back and forth trying to eek out each individual detail. And, are tolerant that someone else on the Cc list might not have the same depth of experience as they -- so learn to skim over details that they already understand. In the process, may pick up some "common terminology" -- or, at least, be able to refer back to the original message to figure out how a particular term is being used. Of course, these also tend to be folks with whom I have personal relationships; people who are genuinely interested in helping (instead of kvetching). I discuss many ideas in which I may not be expert and frequently screw up in my questions and explanations. But, without exception, folks invest the time to clarify my mistakes (sometimes typos, sometimes overloaded terms, etc.) and share their experience with me -- often in equally verbose detail. People here seem not to want to invest *any* time; "What value of X satisfies 3+X=5?" Folks *here* seem to act as if they are PAYING for each character they read. Yet, VOLUNTARILY "clicking" on the posts -- even when the author and LENGTH are apparent BEFORE clicking. Then, complaining that they did so -- projecting THEIR actions on to me ("Doctor, it hurts when I do this!" "Then stop doing that!") I respect many of the folks' here expertice. But the whining makes folks sound like little kids with 20 second attention spans. How the hell can you read a 1000 page datasheet (e.g., for an SoC) and keep focused -- but not see the thread running through a page or two of text?? I spend most of my time in email exchanges -- because I get RESULTS, there. Here, its just lots of effort with very LITTLE in terms of actual results (review my threads for proof!). At the end of the day, I expect this thread to be equally "unfruitful"; but, USENET gives me a way of "broadcasting" it to other colleagues in the hope that they respond via email (instead of pestering them with "incoming mail" that they might feel obligated to answer)
Reply by ●July 29, 20152015-07-29
Hi George, On 7/28/2015 8:35 PM, George Neuner wrote:> Don knows what a bezier is and how to compute the curve. What he > wants is a way to guess the shape of the curve *without* computing it. > He is trying to use curve fitting to do shape recognition, and I > suspect what he wants is a quick, cheap way to filter out templates > that can't possibly match.[While *you* know much of this, I'll clarify the original app for folks here -- as they can't seem to think in terms of how this information *might* be used.] The first app that these were applied to is a "gesture recognizer". Conceptually, this involves the user moving a body part through a (~2D) path -- the shape and orientation of which is recognized as a specific "gesture". For example, tracing out something (roughly) circular; or, perhaps just a horizontal or vertical line segment; or a zig-zag; or an 'S'-shape; or a 'C', 'U', 'upside-down U', 'backwards C', '<', '>', 'L', etc. You can create a "lexicon" of a large number of unique "gestures" without resorting to complex shapes -- or "multiple strokes" (e.g., a 'T' would require two strokes). Then, bind each gesture to a particular "action" and you've got a user interface! Note that you could be "tracing these out" with a finger on a touchpad (if your eyes don't work -- or, are "busy, elsewhere); a mouse on a tabletop; your *gaze* (if paralyzed); your wrist moving through space; etc. The actual mechanism is not important, the "motion" is! In my case, I used a touchpad and a fingertip to create the initial (rough) templates. Using a mouse results in "stilted" motion -- most folks are more adept at side-to-side motion with a mouse than front-to-back. Using a tablet shows too much "motion detail". A touchpad and finger can be used while your attention is elsewhere. [E.g., we all can make a "check mark" without watching our writing instrument on the page; likewise, can make a "checkmark gesture" without having to *watch* where our hands, eyes, arms, etc. happen to be.] Having collected the raw data (dots) from the touchpad, I imported them into Adobe Illustrator and scaled/translated them to fit a nominal "workspace" ("gesturespace?"). Then, manually fit cubic beziers (plural!) to the raw data. This smooths the roughness of the data, simplifies its representation and *reduces* the quantity of data -- to *3* points per curve (each "bezier segment" is normalized to an origin LOCAL TO EXACTLY THAT BEZIER of (0,0) thereby implicitly specifying the first point of the four normally required.) Then, extracted the beziers from the .AI file and converted them into my internal representation and encoding. Note that using a Bezier model allows me to represent arbitrary curves as well as points and straight lines! No need to have different "data types" in that template for each of these possibilities! (Imagine a 'U' -- straight segments and curved segments conjoined) With these individual "Bezier segments" tabulated, I reconstructed the original gesture templates -- concatenating one bezier to the end of a preceding bezier until the complete gesture was formed. I.e., the "origin" of the next Bezier "segment" is translated to the endpoint of the previous segment (translation does not alter the characteristics of the Bezier). This is encoded in (another) table. Still another table indicates which of these "paths" is associated with each NAMED gesture -- as well as simple transforms that can be applied to that template without altering the actual resulting gesture. E.g., you can draw a circle clockwise or counterclockwise; start it at the top or bottom, left or right -- and, in MOST cases, it will still be recognized as "CIRCLE". OTOH, there are some cases that may differentiate between "CIRCLE CW" and "CIRCLE CCW". This is handled in the "permitted transforms" applied to a particular "path" -- without changing the *shape* of that path or necessitating another *instance* of the path in the database. [i.e., this form of representation allows for greater data sharing between "different" -- though "visually" identical -- gestures] From each template (which consists of one or more concatenated Beziers), I look at the characterization (the purpose of this USENET topic) of the curve -- just by examining the 3 recorded (and one implied) control points. This gives me a quick assessment of what that curve WOULD look like if it had been rendered into a visible representation (which I am not going to do unless absolutely necessary -- because it is expensive!). So, I can tell if it is a line, point, concave/convex curve, 'S'-shaped, loop, etc. *Just* by quickly inspecting the 4 points! From that CHARACTERIZATION, I can determine the *features* of that curve "segment" (aspect ratio, "amount of ink", curviness, jaggedness, straightness, bounding box, etc.). E.g., knowing the curve is a point means it uses "0" ink; as a line, the amount of ink would be determined by the simple distance from start point to end point (the two OTHER points don't factor into the calculation -- AND, the calculation is EXACT!); as a simple curve, I would have to compute the "length" via an expensive process; an 'S' curve clues me in on the fact that I will need to cut the curve at it's inflection point and compute the *two* "lengths" independently, summing the result. With the features for each of the curves that comprise a particular gesture template, I can quickly compute the features for the entire template. (recall, some templates share "components" with other gestures! So, any computation is leveraged by the amount of sharing in play!) With a set of "valid" gestures known to be legal at this point in the "user dialog" (some gestures aren't recognized in some places), I can watch the user "issue" a new gesture. Then extract the "features" from *that* gesture instance. Examining the "legal" templates for compatible feature SETS, I can identify the templates that are *likely* to be good candidates for the issued gesture. Then, I can more scrupulously (expensively) compare the "issued gesture" to each of those templates to determine best/any/no fit. In the case of a "match", I can signal to the user interface that "Gesture <foo> has been recognized". It can respond accordingly. Meanwhile, I can use the data from the issued gesture -- along with all other previously issued gestures that I "recognized" as *that* template -- to *train*/modify/deform the template to better "fit" the data that have been historically encountered. If, in the process of "deforming" (re-forming?) a template, its CHARACTERISTICS change *noticeably* (e.g., a line degrades to a point), then I can back off on the deformation -- templates shouldn't be changing *that* much! OTOH, if the user *rejects* my conclusion, then I can use this issued gesture -- along with the *next* (iff SIMILAR!) gesture that is recognized to bias the model AGAINST recognizing the issued data as that rejected template. NO HUMAN IS WATCHING THE DETAILS OF THIS PROCESS. IT IS CODE WATCHING OTHER CODE. AND, IT RUNS *FOREVER* (years)! THERE'S NO "RESET/REBOOT". So, over time, the templates adapt to reflect the current "style" of the user. E.g., if a user starts to issue gestures "on a skew", then the templates end up skewed as well. "Recent history" has a greater impact on the deformations than "ancient history" so the templates try to reflect "now" instead of "then". At the same time, the "catalog of templates" are examined to ensure enough "difference" exists between each. E.g., so 'O' and '0' don't end up with templates that are too similar to support reliable differentiation when '0' AND 'O' happen to BOTH be legal gestures! Again, the (raw) data history of past "issued gestures" is reexamined to see how that "old data" would fare with the new set of templates. We *know* that each of those past gestures was recognized CORRECTLY (because the user ACCEPTED the recognizer's decision!) so we know what each set of raw data *should* be recognized as -- even with the revised models!! In this way, I don't have to wait for the user to issue countless NEW gestures in the FUTURE on which to test my new templates. I can harvest the OLD data to gauge the efficacy of the current template set (i.e., all those Bezier-built models) with less fear of having the new templates "misrecognizing" new gestures! Finally, if the user is "getting sloppy" (e.g., making his 'O' look too much like a '0', his 'L' like a '<', etc.), I can coax him into reexerting some discipline over his "inputs". E.g., suggesting "retraining" -- in the guise of the *device* needing to be reetrained (when, in fact, it is the *user* who is being retrained -- or, more correctly, the *two* resynchronizing their expectations) [See what I mean about not throwing away *any* data, George?? :> ] Time for bed.
Reply by ●July 29, 20152015-07-29
On 7/28/2015 3:08 AM, Clifford Heath wrote:> > I want to engage with your topics, I really do. You just make it too > hard, unnecessarily.Don is a tough guy to help. He is very sharp, so when he asks a question he already has a good understanding of the topic. But he doesn't know how to discuss a topic worth a hoot. I think he is the sort of designer who doesn't understand people so well and has trouble putting himself in your position. This thread contains many great examples of how he fails to connect the dots of communication. Most notable he has never explained the form of the solution he is looking for. He asks for a way to "characterize (describe) the curve" without adequately explaining what "characterize" means all because he doesn't grasp what others fail to understand about his "technically" correct question. I remember in college a student would ask a question but not convey his real point of confusion to the professor. Understandable, since he is lacking knowledge of the topic. But the professor would often fail to get what the question was really about. Sometimes this would be so obvious to me that I would raise my hand and explain it for him. lol Not much I can do to help Don though. It has been a long time since I worked with Bezier curves. Reading about them briefly doesn't give me a hint to a solution. I'm still struggling with how a B�zier curve might be "characterized". But I can see a small start. It should be easy to obtain the slope of the line at the end points. I don't know, but I suspect it should be possible to determine if the curve has a loop or not. I expect if he asked his question in a more math oriented group he would find an answer. This group has a lot of sharp people, but many of them are admittedly rather math challenged. Perhaps the comp.dsp group would be better, but I am sure they will want a reasonable definition of "characterize" before they will even start on an answer. -- Rick
