Nice and terse -- like on an EXAM!

{(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.

Reply to
Don Y
Loading thread data ...

Yup. Have fun.

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.

Tim Wescott 
Wescott Design Services 
 Click to see the full signature
Reply to
Tim Wescott

If they were "four points on the curve", then they wouldn't define *A* cubic bezier but, rather, a *family* of curves. Given that there are

4 points and that you need 4 points to uniquely define *a* cubic bezier, that seems the most obvious explanation. I.e., if encountered on an *exam*, you'd have to make some educated guess as to its meaning, right? How would the rest of the question make sense in the context of a "family of curves"? [You should be able to *casually* come up with curves where you can put all four points on a curve and dramatically change the characteristics of that curve without dislodging any of those points. Solution left as an exercise for the reader -- if you spend more than 10 seconds on it, you don't understand the problem!]

What "real number answer"? The only "numbers" that could apply *might* be things like total length of curve or net displacement, etc. Those are aspects of a particular curve but don't characterize/describe it.

If Pi=(Xi,Yi) then consider the curves: {P1, P2, P3, P4} -- as initially "given" {P1, P2, P4, P3} {P1, P3, P2, P4} {P1, P3, P4, P2} {P1, P4, P2, P3} {P1, P4, P3, P2} etc. Each use the same set of four points yet yield very different curves. Even holding the endpoints constant and swapping the two intermediary control points yields very different curves: {P1, P2, P3, P4} {P1, P3, P2, P4} that would be described differently. (try real numbers as examples)

Qm.n is an acknowledgement that we don't work in a continuous space. E.g., your "display" doesn't have infinite "precision"/resolution. So, while a curve might mathematically pass through (or *originate* at) the point (1/9, 1/3), you will only be able to plot points in that

*vicinity*. How close you can get to that point depends on the values of 'm' and 'n'.

Furthermore, any "characterization" of the curve would have to be well-behaved in boundary conditions. To create a concrete (non-abstract) example, consider how you would describe the curve {(0,0),(0,2),(1,2),(1,0)} in Q10.5? Then, again, in Q15.0! (oops! not quite so easy, eh? In fact, the very *nature* of the curve changes dramatically!)

Assuming a continuous, infinitely resolvable domain means you end up with bugs when reality and math diverge.

[Of course, I could have mentioned this -- along with the specific examples that I've been using in my ongoing email discussions on the subject -- but then I would be considered as too verbose or having obfuscated the question by including too much detail. All of which could have clarified the problem by explicitly pointing out the issues that folks invariably *wouldn't* have noticed from a CASUAL read. I'm sure those same folks would interpret this a posteriori explanation as too verbose, as well! And, try as I might, I simply couldn't figure out how to express the math as Haiku...]
Reply to
Don Y

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.

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!).

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.

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. 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.

I want to engage with your topics, I really do. You just make it too hard, unnecessarily.

Reply to
Clifford Heath

OK. Clearly you know way more about this than I do. So it was pointless to ask the question because you already know the answer.

Have fun.

Tim Wescott 
Wescott Design Services 
 Click to see the full signature
Reply to
Tim Wescott

If I *knew* the answer I wouldn't have asked or been engaged in the ongoing email discussions. It's not an easy problem to solve. If you'd played with various "example" point sets and seen the resulting "curves", you'd understand.

"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?"

Reply to
Don Y

You replied with a question that was not answered, but rather you were presented with other questions which look like an attempt at an answer. All from a guy who says he can't figure out how to write more concisely.

Does anyone understand what Don is asking?


Reply to

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.

-- glen

Reply to
glen herrmannsfeldt

OK. I am not going to do this for you, because I'm rather exasperated. But I will repeat my first answer in detail:

Step 1: Find wikipedia. If you can't do this, go back to the 1980's.

Step 2: Enter "Bezier" in the search window. If you can't figure out how to enter things in a search window, ask for help.

Step 3: Find the relevant page. Ditto on asking for help.

Step 4: Find the EASY AND VERY RELEVANT math under the heading "Cubic Besier Curves".

ONCE YOU HAVE DONE THAT, if you still don't understand, ask again.

Frankly, the only response that I could see if you had actually done that would be "whoa! nifty! this is what I needed!".

Tim Wescott 
Wescott Design Services 
 Click to see the full signature
Reply to
Tim Wescott

It's not a question of "understanding" (at least not on *my* part! :> ) Rather, the fact that the information I seek is simply not available.

(sigh) No, you clearly don't understand the question being asked.

Do you think I *didn't* use Wikipedia, Google, my bookshelf full of Computer Graphics texts and various other technical periodicals

*before* posing the question? Or, do you think that I simply couldn't RECOGNIZE the OBVIOUS ANSWER to my question before posting it, here?

Perhaps you've only a casual familiarity with cubic beziers? And, as such, aren't aware of (or haven't considered) the variety of different curves that can be generated from the canonical form? So, the idea of *characterizing* a curve based on the coefficients (parameters) plugged into said form doesn't mean anything to you?

Let's try something simpler. Pretend we're talking about *lines*! You'd expect the canonical form to be something like: y = mx + b Examining that equation, you'd characterize the plot it *would* generate (if you fed it into a fancy plotting program with appropriate values for 'm' and 'b') as: a line a line of slope of m (positive signifying "climbing with increasing x") a line with x- and y-intercepts of '-b/m' and 'b' So, if I *changed* m or b, the characteristics of that *line* would change, accordingly.

Beyond the naive representation, if you opted to code an algorithm to

*draw* said lines, you'd eventually stumble on a class of lines that don't fit that form: x = C (oops!) These you would *characterize* as "vertical lines" instead of "horizontal" or "diagonal" lines.

OK, lines are pretty boring. Let's try circles! You recognize: (x-X0)^2 + (y-Y0)^2 = R^2 and, based on a set of X0, Y0 and R, you'd characterize things of this form as: a circle a circle of radius R a circle centered at (X0,Y0) etc. You wouldn't even waste the time to feed that to the fancy graphing program -- you *know* what it's going to look like without burning all those electrons trying to render an image of it!

And, after a moment of thought, you'd realize that for R=0, this degenerates to a *point* -- at (X0, Y0).

Move on to ellipses (yeah, I'm using lots of keystrokes -- but introducing higher order constructs as we creep up on the Bezier's complexity!). You'd see: (x-X0)^2 / a^2 + (y-Y0)^2 / b^2 = 1 as the canonical form for an ellipse. And would characterize it as: an ellipse an ellipse "centered" at (X0,Y0) an ellipse having eccentricity sqrt(1-(b/a)^2) an ellipse having major/minor axis of lengths 2a and 2b etc. Again, you wouldn't bother graphing it as these characteristics are evident from a casual inspection of the equation.

Repeat this exercise with various higher-order polynomials and you can characterize aspects of those curves just from an examination of the appropriate coefficients (knowing the form of the polynomial). Parabolae ("holds water", "spills water"), hyperbolae, etc.

*NOW*, do the same for a cubic Bezier -- by moving the control points.

You will end up with: a simple curve (concave/convex -- though with potentially tightening *or* loosening radius an 'ess' shaped curve (to the left, then right; or vice versa) a 'double ess' curve a *loop* with "pigtails" a *cusp* a *closed* loop a straight line (segment) a line that folds back over some portion of itself a line that folds back over itself *twice* a *point* (!) (I think those are all of the cases)

As with each of the other classes of "curves" that I've discussed, here, all of this information is encoded in the parameters (control points) present in the standard form of the curve.

As *drawing* (plotting) a Bezier is relatively EXPEN$IVE, you wouldn't want to have to draw each candidate curve and then heuristically examine the DRAWN CURVE to identify which of these cases is represented in the rendering. (it's far more work to write a piece of code to analyze an arbitrary *image* than it would be to analyze the data that *drives* the creation of that image!)

[A colleague already stumbled upon a solution (in the theoretical sense) for this part of the problem. But, it falls down when you map it onto the numerical representations that you encounter in a computational environment -- limited precision, etc. And, falls down in a potentially *big* way -- unless you arbitrarily constrain the choices for the various parameters/"control points"]

Perhaps now you understand why lots of pretty equations on Wikipedia are completely USELESS in addressing this issue?

Reply to
Don Y
*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" :< )

So, instead, I post a very *terse* question -- then spend MORE keystrokes clarifying misunderstandings, etc.


Reply to
Don Y

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*!

Reply to
Don Y


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.


Reply to
George Neuner

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!

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.

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 (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).


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!

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 to
Don Y

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!

Many, many rambling words with no clear purpose later...

What was the issue again?


Reply to

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 = {

formatting link
}, doi = {10.1145/77055.77056}, acmid = {77056}, publisher = {ACM}, address = {New York, NY, USA}, }

A copy of which seems to be available, here:

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 to
Don Y

Sure, several!

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??

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 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 to
Don Y

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.

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.

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 to
Richard Damon

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!]

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.

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??

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.

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??

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 to
Don Y

[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 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.


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 '

Reply to
Don Y

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.