Initial revision

1 files changed, 646 insertions, 0 deletions

diff --git a/inputmethods/handwriting/qimpenstroke.cpp b/inputmethods/handwriting/qimpenstroke.cpp
new file mode 100644
index 0000000..3567d6d
--- a/dev/null
+++ b/inputmethods/handwriting/qimpenstroke.cpp
@@ -0,0 +1,646 @@
+/**********************************************************************
+** Copyright (C) 2000 Trolltech AS.  All rights reserved.
+**
+** This file is part of Qtopia Environment.
+**
+** This file may be distributed and/or modified under the terms of the
+** GNU General Public License version 2 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.
+**
+** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+**
+** See http://www.trolltech.com/gpl/ for GPL licensing information.
+**
+** Contact info@trolltech.com if any conditions of this licensing are
+** not clear to you.
+**
+**********************************************************************/
+
+#include <qfile.h>
+#include <qtl.h>
+#include <math.h>
+#include <limits.h>
+#include <qdatastream.h>
+#include "qimpenstroke.h"
+
+#define QIMPEN_CORRELATION_POINTS   25
+//#define DEBUG_QIMPEN
+
+/*!
+  \class QIMPenStroke qimpenstroke.h
+
+  Handles a single stroke.  Can calculate closeness of match to
+  another stroke.
+*/
+
+QIMPenStroke::QIMPenStroke()
+{
+}
+
+QIMPenStroke::QIMPenStroke( const QIMPenStroke &st )
+{
+    startPoint = st.startPoint;
+    lastPoint = st.lastPoint;
+    links = st.links.copy();
+}
+
+QIMPenStroke &QIMPenStroke::operator=( const QIMPenStroke &s )
+{
+    clear();
+    //qDebug( "copy strokes %d", s.links.count() );
+    startPoint = s.startPoint;
+    lastPoint = s.lastPoint;
+    links = s.links.copy();
+
+    return *this;
+}
+
+void QIMPenStroke::clear()
+{
+    startPoint = QPoint(0,0);
+    lastPoint = QPoint( 0, 0 );
+    links.resize( 0 );
+    tsig.resize( 0 );
+    dsig.resize( 0 );
+    asig.resize( 0 );
+}
+
+/*!
+  Begin inputting a new stroke.
+*/
+void QIMPenStroke::beginInput( QPoint p )
+{
+    clear();
+    startPoint = p;
+    bounding = QRect();
+    internalAddPoint( p );
+}
+
+/*!
+  Add a point to the stroke's shape.
+  Returns TRUE if the point was successfully added.
+*/
+bool QIMPenStroke::addPoint( QPoint p )
+{
+    if ( links.count() > 500 ) // sanity check (that the user is sane).
+        return FALSE;
+
+    int dx = p.x() - lastPoint.x();
+    int dy = p.y() - lastPoint.y();
+    if ( QABS( dx ) > 1 || QABS( dy ) > 1 ) {
+	// The point is not adjacent to the previous point, so we fill
+	// in with a straight line.  Some kind of non-linear
+	// interpolation might be better.
+	int x = lastPoint.x();
+	int y = lastPoint.y();
+	int ix = 1;
+	int iy = 1;
+	if ( dx < 0 ) {
+	    ix = -1;
+	    dx = -dx;
+	}
+	if ( dy < 0 ) {
+	    iy = -1;
+	    dy = -dy;
+	}
+	int d = 0;
+	if ( dx < dy ) {
+	    d = dx;
+	    do {
+		y += iy;
+		d += dx;
+		if ( d > dy ) {
+		    x += ix;
+		    d -= dy;
+		}
+		internalAddPoint( QPoint( x, y ) );
+	    } while ( y != p.y() );
+	} else {
+	    d = dy;
+	    do {
+		x += ix;
+		d += dy;
+		if ( d > dx ) {
+		    y += iy;
+		    d -= dx;
+		}
+		internalAddPoint( QPoint( x, y ) );
+	    } while ( x != p.x() );
+	}
+    } else {
+	internalAddPoint( p );
+    }
+
+    return TRUE;
+}
+
+/*!
+  Finish inputting a stroke.
+*/
+void QIMPenStroke::endInput()
+{
+    if ( links.count() < 3 ) {
+	QIMPenGlyphLink gl;
+	links.resize(1);
+	gl.dx = 1;
+	gl.dy = 0;
+	links[0] = gl;
+    }
+
+    //qDebug("Points: %d", links.count() );
+}
+
+/*!
+  Return an indicator of the closeness of this stroke to \a pen.
+  Lower value is better.
+*/
+unsigned int QIMPenStroke::match( QIMPenStroke *pen )
+{
+    double lratio;
+
+    if ( links.count() > pen->links.count() )
+	lratio = (links.count()+2) / (pen->links.count()+2);
+    else
+	lratio =  (pen->links.count()+2) / (links.count()+2);
+
+    lratio -= 1.0;
+
+    if ( lratio > 2.0 ) {
+#ifdef DEBUG_QIMPEN
+	qDebug( "stroke length too different" );
+#endif
+	return 400000;
+    }
+
+    createSignatures();
+    pen->createSignatures();
+
+    // Starting point offset
+    int vdiff = QABS(startPoint.y() - pen->startPoint.y());
+
+    // Insanely offset?
+    if ( vdiff > 18 ) {
+	return 400000;
+    }
+
+    vdiff -= 4;
+    if ( vdiff < 0 )
+	vdiff = 0;
+
+    // Ending point offset
+    int evdiff = QABS(lastPoint.y() - pen->lastPoint.y());
+    // Insanely offset?
+    if ( evdiff > 20 ) {
+	return 400000;
+    }
+
+    evdiff -= 5;
+    if ( evdiff < 0 )
+	evdiff = 0;
+
+    // do a correlation with the three available signatures.
+    int err1 = INT_MAX;
+    int err2 = INT_MAX;
+    int err3 = INT_MAX;
+
+    // base has extra points at the start and end to enable
+    // correlation of a sliding window with the pen supplied.
+    QArray<int> base = createBase( tsig, 2 );
+    for ( int i = 0; i < 4; i++ ) {
+        int e = calcError( base, pen->tsig, i, TRUE );
+        if ( e < err1 )
+            err1 = e;
+    }
+    if ( err1 > 40 ) {  // no need for more matching
+#ifdef DEBUG_QIMPEN
+	qDebug( "tsig too great: %d", err1 );
+#endif
+        return 400000;
+    }
+
+    // maybe a sliding window is worthwhile for these too.
+    err2 = calcError( dsig, pen->dsig, 0, FALSE );
+    if ( err2 > 100 ) {
+#ifdef DEBUG_QIMPEN
+	qDebug( "dsig too great: %d", err2 );
+#endif
+	return 400000;
+    }
+
+    err3 = calcError( asig, pen->asig, 0, TRUE );
+    if ( err3 > 60 ) {
+#ifdef DEBUG_QIMPEN
+	qDebug( "asig too great: %d", err3 );
+#endif
+	return 400000;
+    }
+
+    // Some magic numbers here - the addition reduces the weighting of
+    // the error and compensates for the different error scales.  I
+    // consider the tangent signature to be the best indicator, so it
+    // has the most weight.  This ain't rocket science.
+    // Basically, these numbers are the tuning factors.
+    unsigned int err = (err1+1) * ( err2 + 60 ) * ( err3 + 20 ) +
+			vdiff * 1000 + evdiff * 500 +
+			(unsigned int)(lratio * 5000.0);
+
+#ifdef DEBUG_QIMPEN
+    qDebug( "err %d   ( %d, %d, %d, %d)", err, err1, err2, err3, vdiff );
+#endif
+
+    return err;
+}
+
+/*!
+  Return the bounding rect of this stroke.
+*/
+QRect QIMPenStroke::boundingRect()
+{
+    if ( !bounding.isValid() ) {
+	int x = startPoint.x();
+	int y = startPoint.y();
+	bounding = QRect( x, y, 1, 1 );
+
+	for ( unsigned i = 0; i < links.count(); i++ ) {
+	    x += links[i].dx;
+	    y += links[i].dy;
+	    if ( x < bounding.left() )
+		bounding.setLeft( x );
+	    if ( x > bounding.right() )
+		bounding.setRight( x );
+	    if ( y < bounding.top() )
+		bounding.setTop( y );
+	    if ( y > bounding.bottom() )
+		bounding.setBottom( y );
+	}
+    }
+
+    return bounding;
+}
+
+
+/*!
+  Perform a correlation of the supplied arrays.  \a base should have
+  win.count() + 2 * off points to enable sliding \a win over the
+  \a base data.  If \a t is TRUE, the comparison takes into account
+  the circular nature of the angular data.
+  Returns the best (lowest error) match.
+*/
+
+int QIMPenStroke::calcError( const QArray<int> &base,
+                           const QArray<int> &win, int off, bool t )
+{
+    int err = 0;
+
+    for ( unsigned i = 0; i < win.count(); i++ ) {
+        int d = QABS( base[i+off] - win[i] );
+        if ( t && d > 128 )
+            d -= 256;
+        err += QABS( d );
+    }
+
+    err /= win.count();
+
+    return err;
+}
+
+/*!
+  Creates signatures used in matching if not already created.
+*/
+void QIMPenStroke::createSignatures()
+{
+    if ( tsig.isEmpty() )
+	createTanSignature();
+    if ( asig.isEmpty() )
+	createAngleSignature();
+    if ( dsig.isEmpty() )
+	createDistSignature();
+}
+
+/*!
+  Create a signature of the tangents to the user's stroke.
+*/
+void QIMPenStroke::createTanSignature()
+{
+    int dist = 5; // number of points to include in calculation
+    if ( (int)links.count() <= dist ) {
+        tsig.resize(1);
+        int dx = 0;
+        int dy = 0;
+        for ( unsigned j = 0; j < links.count(); j++ ) {
+            dx += links[j].dx;
+            dy += links[j].dy;
+        }
+        tsig[0] = arcTan( dy, dx );
+    } else {
+        tsig.resize( (links.count()-dist+1) / 2 );
+        int idx = 0;
+        for ( unsigned i = 0; i < links.count() - dist; i += 2 ) {
+            int dx = 0;
+            int dy = 0;
+            for ( int j = 0; j < dist; j++ ) {
+                dx += links[i+j].dx;
+                dy += links[i+j].dy;
+            }
+            tsig[idx++] = arcTan( dy, dx );
+        }
+    }
+
+    tsig = scale( tsig, QIMPEN_CORRELATION_POINTS, TRUE );
+//    smooth(tsig);
+}
+
+/*!
+  Create a signature of the change in angle.
+*/
+void QIMPenStroke::createAngleSignature()
+{
+    QPoint c = calcCenter();
+
+    int dist = 3; // number of points to include in calculation
+    if ( (int)links.count() <= dist ) {
+        asig.resize(1);
+        asig[0] = 1;
+    } else {
+        asig.resize( links.count() );
+	QPoint current(0, 0);
+        int idx = 0;
+        for ( unsigned i = 0; i < links.count(); i++ ) {
+            int dx = c.x() - current.x();
+            int dy = c.y() - current.y();
+	    int md = QMAX( QABS(dx), QABS(dy) );
+	    if ( md > 5 ) {
+		dx = dx * 5 / md;
+		dy = dy * 5 / md;
+	    }
+            asig[idx++] = arcTan( dy, dx );
+	    current += QPoint( links[i].dx, links[i].dy );
+        }
+    }
+
+    asig = scale( asig, QIMPEN_CORRELATION_POINTS, TRUE );
+
+/*
+    if ( tsig.isEmpty() )
+        createTanSignature();
+
+    if ( tsig.count() < 5 ) {
+        asig.resize( 1 );
+        asig[0] = 0;
+    } else {
+        asig.resize( tsig.count() - 5 );
+
+        for ( unsigned i = 0; i < asig.count(); i++ ) {
+            asig[i] = QABS(tsig[i] - tsig[i+5]);
+        }
+    }
+*/
+}
+
+/*!
+  Create a signature of the distance from the char's center of gravity
+  to its points.
+*/
+void QIMPenStroke::createDistSignature()
+{
+    dsig.resize( (links.count()+1)/2 );
+    QPoint c = calcCenter();
+    QPoint pt( 0, 0 );
+
+    int minval = INT_MAX;
+    int maxval = 0;
+    int idx = 0;
+    for ( unsigned i = 0; i < links.count(); i += 2 ) {
+        int dx = c.x() - pt.x();
+        int dy = c.y() - pt.y();
+        if ( dx == 0 && dy == 0 )
+            dsig[idx] = 0;
+        else
+            dsig[idx] = dx*dx + dy*dy;
+
+        if ( dsig[idx] > maxval )
+            maxval = dsig[idx];
+        if ( dsig[idx] < minval )
+            minval = dsig[idx];
+        pt.rx() += links[i].dx;
+        pt.ry() += links[i].dy;
+        idx++;
+    }
+
+    // normalise 0-255
+    int div = maxval - minval;
+    if ( div == 0 ) div = 1;
+    for ( unsigned i = 0; i < dsig.count(); i++ ) {
+        dsig[i] = (dsig[i] - minval ) * 255 / div;
+    }
+
+    dsig = scale( dsig, QIMPEN_CORRELATION_POINTS );
+}
+
+
+/*!
+  Scale the points in a array to \a count points.
+  This is braindead at the moment (no smooth scaling) and fixing this is
+  probably one of the simpler ways to improve performance.
+*/
+QArray<int> QIMPenStroke::scale( const QArray<int> &s, unsigned count, bool t )
+{
+    QArray<int> d(count);
+
+    unsigned si = 0;
+    if ( s.count() > count ) {
+        unsigned next = 0;
+        for ( unsigned i = 0; i < count; i++ ) {
+            next = (i+1) * s.count() / count;
+            int maxval = 0;
+            if ( t ) {
+                for ( unsigned j = si; j < next; j++ ) {
+                    maxval = s[j] > maxval ? s[j] : maxval;
+                }
+            }
+            int sum = 0;
+            for ( unsigned j = si; j < next; j++ ) {
+                if ( t && maxval - s[j] > 128 )
+                    sum += 256;
+                sum += s[j];
+            }
+            d[i] = sum / (next-si);
+            if ( t && d[i] > 256 )
+                d[i] %= 256;
+            si = next;
+        }
+    } else {
+        for ( unsigned i = 0; i < count; i++ ) {
+            si = i * s.count() / count;
+            d[i] = s[si];
+        }
+    }
+
+    return d;
+}
+
+/*!
+  Add another point to the stroke's shape.
+*/
+void QIMPenStroke::internalAddPoint( QPoint p )
+{
+    if ( p == lastPoint )
+        return;
+
+    if ( !lastPoint.isNull() ) {
+        QIMPenGlyphLink gl;
+        gl.dx = p.x() - lastPoint.x();
+        gl.dy = p.y() - lastPoint.y();
+        links.resize( links.size() + 1 );   //### resize by 1 is bad
+        links[links.size() - 1] = gl;
+    }
+
+    lastPoint = p;
+    bounding = QRect();
+}
+
+/*!
+  Calculate the center of gravity of the stroke.
+*/
+QPoint QIMPenStroke::calcCenter()
+{
+    QPoint pt( 0, 0 );
+    int ax = 0;
+    int ay = 0;
+
+    for ( unsigned i = 0; i < links.count(); i++ ) {
+        pt.rx() += links[i].dx;
+        pt.ry() += links[i].dy;
+        ax += pt.x();
+        ay += pt.y();
+    }
+
+    ax /= (int)links.count();
+    ay /= (int)links.count();
+
+    return QPoint( ax, ay );
+}
+
+/*!
+  Calculate the arctan of the lengths supplied.
+  The angle returned is in the range 0-255.
+  \a dy and \a dx MUST be in the range 0-5 - I dont even check :-P
+*/
+int QIMPenStroke::arcTan( int dy, int dx )
+{
+    if ( dx == 0 ) {
+        if ( dy >= 0 )
+            return 64;
+        else
+            return 192;
+    }
+
+    if ( dy == 0 ) {
+        if ( dx >= 0 )
+            return 0;
+        else
+            return 128;
+    }
+
+    static int table[5][5] = {
+        { 32, 19, 13, 10, 8  },
+        { 45, 32, 24, 19, 16 },
+        { 51, 40, 32, 26, 22 },
+        { 54, 45, 37, 32, 27 },
+        { 56, 49, 42, 37, 32 } };
+
+    if ( dy > 0 ) {
+        if ( dx > 0 )
+            return table[dy-1][dx-1];
+        else
+            return 128 - table[dy-1][QABS(dx)-1];
+    } else {
+        if ( dx > 0 )
+            return 256 - table[QABS(dy)-1][dx-1];
+        else
+            return 128 + table[QABS(dy)-1][QABS(dx)-1];
+    }
+
+    return 0;
+}
+
+
+/*!
+  Silly name.  Create an array that has \a e points extra at the start and
+  end to enable a sliding correlation to be performed.
+*/
+QArray<int> QIMPenStroke::createBase( const QArray<int> a, int e )
+{
+    QArray<int> ra( a.count() + 2*e );
+
+    for ( int i = 0; i < e; i++ ) {
+        ra[i] = a[e - i - 1];
+        ra[a.count() + i] = a[a.count() - i - 1];
+    }
+    for ( unsigned i = 0; i < a.count(); i++ ) {
+        ra[i+e] = a[i];
+    }
+
+    return ra;
+}
+
+
+/*!
+  Smooth the points in an array.  Probably a bad idea.
+*/
+void QIMPenStroke::smooth( QArray<int> &sig)
+{
+    QArray<int> nsig = sig.copy();
+
+    int a;
+    for ( unsigned i = 1; i < sig.count()-2; i++ ) {
+        a = 0;
+        for ( int j = -1; j <= 1; j++ ) {
+            a += sig[ i + j ];
+        }
+        nsig[i] = a / 3;
+    }
+
+    sig = nsig;
+}
+
+/*!
+  Write the character's data to the stream.
+*/
+QDataStream &operator<< (QDataStream &s, const QIMPenStroke &ws)
+{
+    s << ws.startPoint;
+    s << ws.links.count();
+    for ( unsigned i = 0; i < ws.links.count(); i++ ) {
+        s << (Q_INT8)ws.links[i].dx;
+        s << (Q_INT8)ws.links[i].dy;
+    }
+
+    return s;
+}
+
+/*!
+  Read the character's data from the stream.
+*/
+QDataStream &operator>> (QDataStream &s, QIMPenStroke &ws)
+{
+    Q_INT8 i8;
+    s >> ws.startPoint;
+    ws.lastPoint = ws.startPoint;
+    unsigned size;
+    s >> size;
+    ws.links.resize( size );
+    for ( unsigned i = 0; i < size; i++ ) {
+        s >> i8;
+	ws.links[i].dx = i8;
+        s >> i8;
+	ws.links[i].dy = i8;
+	ws.lastPoint += QPoint( ws.links[i].dx, ws.links[i].dy );
+    }
+
+    return s;
+}
+
+