Logo Search packages:      
Sourcecode: kanjipad version File versions  Download package

scoring.c

/* -*- mode: C; c-file-style: "bsd"; tab-width: 4 -*- */
/* scoring.c - The handwriting recognition engine
 * JStroke 1.x - Japanese Kanji handwriting recognition technology demo.
 * Copyright (C) 1997  Robert E. Wells
 * http://wellscs.com/pilot
 * mailto:robert@wellscs.com
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program (gpl.html); if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * Derived from prior work by Todd David Rudick on JavaDict and StrokeDic.
 * Makes use of KANJIDIC data from Jim Breen of Monash University.
 * Further credit details available at http://wellscs.com/pilot
 * See readme.txt, changelo, and gpl.html for more information.
 * -------------------------------------------------------------------------*/

#include "jstroke.h"
#include "memowrite.h"

#define diAngCostBase       52      // See angles.pl for derivation.
#define diAngCostScale      98      // See angles.pl for derivation.
#define diHugeCost          (((((ULong)24)*diAngCostScale)+diAngCostBase)*100)

#define diMaxScoreToSquare ((ULong) 0xffff)
#define diMaxScoreSquared  (diMaxScoreToSquare*diMaxScoreToSquare)

/* 2 for Kanji SJIS pair, 2+2 for spaces, 
 * 9 for SJIS:967B,
 * 1 for number sign, and 10 for numeric score, a billion served?
 */
#define diScoreTextLen (2 + 2+2 + 9 + 1 + 10)

#define diPathBufLen        16

CharPtr   StrokeScorerEvalItem(StrokeScorer *pScorer, CharPtr cpEntry,
                                             ULong* ipScore /*OUT*/);

ULong     StrokeDicScoreStroke(Byte* bpX, Byte* bpY, UInt iLen,
                                             CharPtr cpPath, UInt iPathLen,
                                             UInt iDepth);

CharPtr   StrokeScorerExtraFilters(StrokeScorer *pscorer,
                                                   CharPtr cp, ULong* ipScore /*OUT*/);

Long      StrokeScorerExtraEval(StrokeScorer *pscorer,
                                                char cArg, UInt iStroke);

ULong     SqrtULong(ULong val);

/* ----- SqrtULong ---------------------------------------------------------*/

ULong SqrtULong(ULong val) {
      ULong root, rootLo, rootHi;

      if (val == 0)
            return 0;
      else if (val == 1)
            return 1;
      else if (val >= diMaxScoreSquared)
            return diMaxScoreToSquare;

      rootLo = 1;
      rootHi = (val >> 1);          /* will be >= 1, since val > 1. */
      if (rootHi > diMaxScoreToSquare)
            rootHi = diMaxScoreToSquare;

      while ((root = ((rootLo + rootHi) >> 1)) > rootLo) {
            if ((root * root) <= val) {
                  rootLo = root;
            }
            else {
                  rootHi = root;
            }
      }

      return root;
}

/* ----- StrokeScorerCreate-------------------------------------------------*/
/* Create a StrokeScorer object. (Returns NULL if can't get memory) */

StrokeScorer *StrokeScorerCreate  (CharPtr cpStrokeDic, RawStroke *rsp,
                                                   UInt iStrokeCnt) {
      StrokeScorer *pScorer = (StrokeScorer *) MemPtrNew(sizeof(StrokeScorer));
      if (!pScorer) {
            ErrBox("Not enough memory.");
            return NULL;
      }

      pScorer->m_cpStrokeDic = cpStrokeDic;
      pScorer->m_pRawStrokes = rsp;
      pScorer->m_iStrokeCnt = iStrokeCnt;
      pScorer->m_iScoreLen = 0;

      pScorer->m_pScores = (ScoreItemPtr) MemPtrNew(diMaxListCount*sizeof(StrokeScorer));
      
      if (!pScorer->m_pScores) {
            ErrBox("Not enough memory.");
            MemPtrFree(pScorer);
            return NULL;
      }

      pScorer->m_cpPath = MemPtrNew(diPathBufLen+1);

      if (!pScorer->m_cpPath) {
            ErrBox("Not enough memory.");
            MemPtrFree(pScorer->m_pScores);
            MemPtrFree(pScorer);
            return NULL;
      }

      return pScorer;
}

/* ----- StrokeScorerDestroy-------------------------------------------------*/
/* Destroy a StrokeScorer object */

void StrokeScorerDestroy  (StrokeScorer *pScorer) {
      if (pScorer) {
            MemPtrFree (pScorer->m_pScores);
            MemPtrFree (pScorer->m_cpPath);
            MemPtrFree (pScorer);
      }
}

/* ----- StrokeScorerProcess-------------------------------------------------*/
/* Process some database entries (maximum iMaxCnt, -1 for all).
   Returns 0 when none remaining (should eventually return count remaining
   to facilitate a progressbar */

Long     StrokeScorerProcess  (StrokeScorer *pScorer, Long iMaxCnt) {
      CharPtr      cp, cpNext;
      ULong        iScore;
      Long         iCnt;
      ScoreItemPtr pScore, pScoreBase, pSrc;

      if (!pScorer) {
            ErrBox("StrokeScorerProcess: pScorer == NULL.");
            return 0;
      }

      pScoreBase = pScorer->m_pScores;

      /* Evaluate all the items in cpStrokeDic against Context,
       * and update ScoreItems list as we go.
       */

      iCnt = 0;
      for (cp = pScorer->m_cpStrokeDic; *cp; cp = cpNext) {

            iCnt++;
            if (iMaxCnt >= 0 && iCnt > iMaxCnt)
                  break;

            cpNext = StrokeScorerEvalItem(pScorer, cp, &iScore);

            for (pScore = pScoreBase+pScorer->m_iScoreLen-1;
                   pScore>=pScoreBase; pScore--) { 
                  if (iScore >= pScore->m_iScore)
                        break;
            }
            pScore++;

            /* If we have a top score, lets register it. */
            if (pScore < (pScoreBase + diMaxListCount)) {

                  /* Increase the score list length if it isn't full yet. */
                  if (pScorer->m_iScoreLen < diMaxListCount)
                        pScorer->m_iScoreLen++;

                  /* Push down all lower scores in the list to make room. */
                  for (pSrc = pScoreBase+pScorer->m_iScoreLen-2; pSrc >= pScore; pSrc--) {
                        pSrc[1].m_iScore = pSrc->m_iScore;
                        pSrc[1].m_cp     = pSrc->m_cp;
                  }

                  /* Actually store our info in the list. */
                  pScore->m_iScore = iScore;
                  pScore->m_cp = cp;
            }

      } /* for each stroke description... */

      if (cp)
            return 1;                     /* should be count remaining */
      else
            return 0;
}

/* ----- StrokeScorerTopPicks -----------------------------------------------*/
/* Return best diMaxListCount candidates processed so far */

ListMem*      StrokeScorerTopPicks (StrokeScorer *pScorer)
{
      ListMem*     pListMem;
      UInt         iTotStrLen, iListSize, iTotSize;
      CharPtr      cpList;
      CharPtr*     cppList;
      ScoreItemPtr pScore, pScoreBase;
      UInt         sJisVal;
      char         buf[10];

      if (!pScorer) {
            ErrBox("StrokeScorerTopPicks: pScorer == NULL.");
            return NULL;
      }

      /* If no list, just return an empty list. */
      if (pScorer->m_iScoreLen <= 0)
            return AppEmptyList();

      pScoreBase = pScorer->m_pScores;

      iTotStrLen = pScorer->m_iScoreLen * (diScoreTextLen + 1);

      iListSize = (pScorer->m_iScoreLen+1)*sizeof(CharPtr); /* One extra for NULL terminator */
      iTotSize = sizeof(ListMem) + iListSize + iTotStrLen;

      if (!(cpList = MemPtrNew(iTotSize))) {
            ErrBox("ERROR: no mem in top picks");
            return NULL;
      }

      pListMem = (ListMem *) cpList;      cpList += sizeof(ListMem);
      cppList = (CharPtr *) cpList; cpList += iListSize;
      
      pListMem->m_argc = pScorer->m_iScoreLen;
      pListMem->m_argv = cppList;   /* Copy now before we use it in loop... */

      for (pScore = pScoreBase; pScore < (pScoreBase+pScorer->m_iScoreLen); pScore++) {
            *cppList++ = cpList;
            *cpList++ = pScore->m_cp[0];
            *cpList++ = pScore->m_cp[1];
            *cpList++ = ' ';
            *cpList++ = ' ';

            *cpList++ = 'S';
            *cpList++ = 'J';
            *cpList++ = 'I';
            *cpList++ = 'S';
            *cpList++ = ':';

            // BUGFIX: Need to avoid sign extension.  -rwells, 19970926.
            sJisVal = ((pScore->m_cp[0] & 0xff) << 8) + (pScore->m_cp[1] & 0xff);

            StrIToH(buf, sJisVal);
            *cpList++ = buf[4];
            *cpList++ = buf[5];
            *cpList++ = buf[6];
            *cpList++ = buf[7];

            *cpList++ = ' ';
            *cpList++ = ' ';
            *cpList++ = '#';
            StrIToA(cpList, pScore->m_iScore); /* Null terminates */
            cpList += StrLen(cpList) + 1; /* Skip ascii number and null. */
      }
      *cppList = NULL;              /* NULL terminated argv vector, for luck. */
      return pListMem;
}

/* ----- StrokeScorerEvalItem -----------------------------------------------*/

CharPtr StrokeScorerEvalItem(StrokeScorer *pScorer, CharPtr cpEntry,
                                           ULong* ipScore /*OUT*/) {
      CharPtr cp = cpEntry;
      UInt    iStroke;
      CharPtr cpPath = pScorer->m_cpPath;
      CharPtr cpPathEnd;
      RawStroke* rsp;
      ULong   iThisScore;
      ULong   iScore = 0;

      MemoWriteLen(pScorer->m_cpStrokeDic, 2); /* DEBUG: tag trace with SJIS char. */

      if (*cp) cp++;                      /* Skip over first half SJIS char. */
      if (*cp) cp++;                      /* Skip over second half SJIS char. */

      /* The first char must have high order bit set,
       * and the second char MAY have high order bit set,
       * but a subsequent char with high order bit set must be
       * the beginning of the next entry.  -rwells, 970712.
       */

      /* Loop through stroke descriptions */
      for (iStroke = 0; iStroke < pScorer->m_iStrokeCnt; iStroke++) {

            cpPathEnd = cpPath;

            switch (*cp) {          /* Break out on first char value... */
            case 'A':               /* TDR='1' CLK=07:30 DEG=225 */
                  *cpPathEnd++ = 20; break; 
            case 'B':               /* TDR='2' CLK=06:00 DEG=180 */
                  *cpPathEnd++ = 16; break; 
            case 'C':               /* TDR='3' CLK=04:30 DEG=135 */
                  *cpPathEnd++ = 12; break; 
            case 'D':               /* TDR='4' CLK=09:00 DEG=270 */
                  *cpPathEnd++ = 24; break; 
            case 'F':               /* TDR='6' CLK=03:00 DEG=090 */
                  *cpPathEnd++ =  8; break; 
            case 'G':               /* TDR='7' CLK=10:30 DEG=315 */
                  *cpPathEnd++ = 28; break; 
            case 'H':               /* TDR='8' CLK=12:00 DEG=360 */
                  *cpPathEnd++ =  0; break; 
            case 'I':               /* TDR='9' CLK=01:30 DEG=045 */
                  *cpPathEnd++ =  4; break; 
            case 'J':               /* TDR='x' down   06:00 then 07:30 */
                  *cpPathEnd++ = 16; *cpPathEnd++ = 20; break; 
            case 'K':               /* TDR='y' down   06:00 then 04:30 */
                  *cpPathEnd++ = 16; *cpPathEnd++ = 12; break; 
            case 'L':               /* TDR='c' down   06:00 then 03:00 */
                  *cpPathEnd++ = 16; *cpPathEnd++ =  8; break; 
            case 'M':               /* TDR='b' across 03:00 then 06:00 */
                  *cpPathEnd++ =  8; *cpPathEnd++ = 16; break; 
            default:
                  goto NoMoreStrokes;
            } /* end switch on first char value */

            for (cp++; ; cp++) {    /* Loop through following chars for stroke */
                  switch (*cp) {          /* Break out on char value... */
                  case 'a':               /* TDR='1' CLK=07:30 DEG=225 */
                        *cpPathEnd++ = 20; break; 
                  case 'b':               /* TDR='2' CLK=06:00 DEG=180 */
                        *cpPathEnd++ = 16; break; 
                  case 'c':               /* TDR='3' CLK=04:30 DEG=135 */
                        *cpPathEnd++ = 12; break; 
                  case 'd':               /* TDR='4' CLK=09:00 DEG=270 */
                        *cpPathEnd++ = 24; break; 
                  case 'f':               /* TDR='6' CLK=03:00 DEG=090 */
                        *cpPathEnd++ =  8; break; 
                  case 'g':               /* TDR='7' CLK=10:30 DEG=315 */
                        *cpPathEnd++ = 28; break; 
                  case 'h':               /* TDR='8' CLK=12:00 DEG=360 */
                        *cpPathEnd++ =  0; break; 
                  case 'i':               /* TDR='9' CLK=01:30 DEG=045 */
                        *cpPathEnd++ =  4; break; 
                  case 'j':               /* TDR='x' down   06:00 then 07:30 */
                        *cpPathEnd++ = 16; *cpPathEnd++ = 20; break; 
                  case 'k':               /* TDR='y' down   06:00 then 04:30 */
                        *cpPathEnd++ = 16; *cpPathEnd++ = 12; break; 
                  case 'l':               /* TDR='c' down   06:00 then 03:00 */
                        *cpPathEnd++ = 16; *cpPathEnd++ =  8; break; 
                  case 'm':               /* TDR='b' across 03:00 then 06:00 */
                        *cpPathEnd++ =  8; *cpPathEnd++ = 16; break; 
                  default:
                        goto ThisStrokeDone;
                  } /* end switch on char value */
            } /* end loop through chars for stroke */
ThisStrokeDone:

            rsp = &(pScorer->m_pRawStrokes[iStroke]);

            iThisScore = StrokeDicScoreStroke(rsp->m_x, rsp->m_y, rsp->m_len,
                                                              cpPath, (cpPathEnd - cpPath),
                                                              0 /*depth*/);
            
            MemoWrite2d(" s", iStroke+1);
            MemoWrite2d("=", iThisScore); /* DEBUG: stroke score */

            if (iThisScore >= diMaxScoreToSquare)
                  iThisScore = diMaxScoreSquared;
            else
                  iThisScore = (iThisScore * iThisScore);

            if (iScore >= (diMaxScoreSquared - iThisScore))
                  iScore = diMaxScoreSquared;
            else
                  iScore += iThisScore;

      } /* end loop through stroke descriptions */
NoMoreStrokes:

      iScore = SqrtULong(iScore);
      *ipScore = iScore;

      MemoWrite2d(" is=", iScore); /* DEBUG: overall stroke score */

    /* Handle optional extra filters... may modify *ipScore, updates cp. */
      if (*cp == '|') {
            cp = StrokeScorerExtraFilters(pScorer, cp+1, ipScore);
      }

      if (iStroke != pScorer->m_iStrokeCnt)
            ErrBox("JStrokeDic miscount");
      if (!(*cp & 0x80) && (*cp != '\0'))
            ErrBox("JStrokeDic leftovers");


      MemoWrite2d(" fs=", *ipScore); /* DEBUG: final score */
      MemoWrite("\n");

      return cp;
}

/* ----- StrokeDicScoreStroke ---------------------------------------------- */

ULong StrokeDicScoreStroke(Byte* bpX, Byte* bpY, UInt iLen,
                                       CharPtr cpPath, UInt iPathLen,
                                                  UInt iDepth) {
      ULong iScore, iThisScore;
      Long iMid, iStep, iPathMid, iPathRest;
      Long iDifX, iDifY;
      UInt iAng32, iPath32, iDif32;

      if (iLen < 2 || iPathLen < 1)
            return diHugeCost;

      if (iPathLen == 1) {
            iDifX = bpX[iLen-1] - bpX[0];
            iDifY = bpY[0] - bpY[iLen-1]; /* Flip from display to math axes. */

            if (iDifX == 0 && iDifY == 0) /* Two samples at same place... */
                  return diHugeCost;

            /* Subdivide recursively while stroke is long and depth is shallow.
             * $$$ These values are pretty magic... review later. -rwells, 970719.
             * TDR used 20*20... -rwells, 970719.
             */
            if ((iDifX*iDifX + iDifY*iDifY) > (20*20) && iLen > 5 && iDepth < 4) {

                  iMid = iLen >> 1;

                  /* Note that we use the middle point on both sides... */

                  iScore  = StrokeDicScoreStroke(bpX, bpY, iMid+1,
                                                               cpPath, iPathLen, iDepth+1);

                  iScore += StrokeDicScoreStroke(bpX+iMid, bpY+iMid, iLen-iMid,
                                                               cpPath, iPathLen, iDepth+1);

                  return (iScore >> 1);

            } /* End if stroke is long, and depth is shallow... */

            /* Time to score this segment against desired direction. */
            
            iAng32 = Angle32(iDifX, iDifY);

            iPath32 = *cpPath;

            if (iAng32 >= iPath32)
                  iDif32 = iAng32 - iPath32;
            else
                  iDif32 = iPath32 - iAng32;

            return iDif32 * diAngCostScale + diAngCostBase;

      } /* end if path len is 1. */
      else {

            iScore = diHugeCost * iPathLen * 2;
            iPathMid = iPathLen >> 1;
            iPathRest = iPathLen - iPathMid;
            
            if (iLen < 20)
                  iStep = 1;
            else
                  iStep = iLen / 10;

            for (iMid = iPathMid; iMid < iLen - iPathRest; iMid += iStep) {

                  /* TDR original doesn't increase iDepth... -rwells, 970719. */

                  iThisScore  = StrokeDicScoreStroke(bpX, bpY, iMid+1,
                                                                     cpPath, iPathMid, iDepth+1);

                  iThisScore += StrokeDicScoreStroke(bpX+iMid, bpY+iMid, iLen-iMid,
                                                                     cpPath+iPathMid, iPathRest,
                                                                     iDepth+1);

                  /* TDR original doesn't divide sum by 2... -rwells, 970719. */
                  iThisScore >>= 1;

                  if (iThisScore < iScore)
                        iScore = iThisScore;

            } /* end for trials on various mid-point divisions of stroke... */

            return iScore;
      } /* end if path len is >1. */
}

/* ----- StrokeScorerExtraFilters ---------------------------------------------*/

CharPtr StrokeScorerExtraFilters(StrokeScorer *pScorer,
                                                 CharPtr cp, ULong* ipScore /*OUT*/) {
      char    c;
      char    cArg[2];
      Byte    iStroke[2];
      Long    iDiff, iVal[2];
      UInt    idx = 0;
      Boolean bMust = false;
  
      MemoWrite(" F(");

      cArg[0] = cArg[1] = 0;
      iStroke[0] = iStroke[1] = 0;

    /* Simple parser for Filter strings. assumes a1-b1 structure,
       * where a and b can be any single alphabetic cmd char, the 
       * numbers can be multiple digit, and b1 can optionally be 
       * followed by '!' to insist on the filter passing.  There can
       * be multiple filters but they have to be separated by '!' or
       * space(s).  The filter string is terminated by a null byte
       * or an 8-bit char, the beginning of the next entry.  
       * Leading spaces and trailing spaces are ignored. -rwells, 970722.
       */

      for (c = *cp; true; cp++, c = *cp) {
            switch (c) {

            case 'x': 
            case 'y':
            case 'i':
            case 'j':
            case 'a':
            case 'b':
            case 'l':
                  cArg[idx] = c;

                  MemoWrite2d(" c",idx);
                  MemoWrite("=");
                  MemoWriteLen(cArg+idx, 1);
                  break;

            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                  iStroke[idx] = iStroke[idx] * 10 + (c - '0');
                  MemoWrite2d(":", iStroke[idx]);
                  break;

            case '-':                     /* Switch to second arg when we see minus. */
                  idx = 1;
                  MemoWrite(" - ");
                  break;

            case '!':
                  bMust = true;
                  MemoWrite(" ! ");
                  /* FALLTHRU */

            case ' ':
            default:
                  MemoWrite2d(" @", idx);
                  MemoWrite(")");

                  /* If we are in the second argument, execute and reset. */
                  if (idx == 1) {
                        iVal[0] = StrokeScorerExtraEval(pScorer, cArg[0], iStroke[0]);
                        iVal[1] = StrokeScorerExtraEval(pScorer, cArg[1], iStroke[1]);
                        iDiff = (iVal[0] - iVal[1]);

                        MemoWrite(" ");
                        MemoWriteLen(cArg+0, 1);
                        MemoWrite2d("", iStroke[0]);
                        MemoWrite2d(":", iVal[0]);
                        
                        MemoWrite("-");
                        MemoWriteLen(cArg+1, 1);
                        MemoWrite2d("", iStroke[1]);
                        MemoWrite2d(":", iVal[1]);
                        
                        MemoWrite2d("=", iDiff);

                        if (iDiff < 0) {
                              iDiff = -iDiff;
                              if (bMust)
                                    iDiff = 9999999;
                              if (*ipScore < (diMaxScoreSquared-iDiff))
                                    *ipScore += iDiff;
                              else
                                    *ipScore = diMaxScoreSquared;
                        }
                        else {
                              if (*ipScore > iDiff)
                                    *ipScore -= iDiff;
                              else
                                    *ipScore = 0;
                        }

                        MemoWrite2d(" ips=", *ipScore);

                        /* Reset state for next filter... */
                        idx = 0;
                        bMust = false;
                        cArg[0] = cArg[1] = 0;
                        iStroke[0] = iStroke[1] = 0;
                  }

                  /* If this is a terminating char, break out of loop and return. */
                  if ((c & 0x80) || (c == '\0'))
                        goto ReturnNow;
            } /* end switch on char */
      } /* end for each char in filter spec... */
ReturnNow:
      return cp;
}

/* ----- StrokeScorerExtraEval ------------------------------------------------*/

Long StrokeScorerExtraEval(StrokeScorer *pScorer,
                                       char cArg, UInt iStroke) {
      Long  iVal, iSquared;
      Byte* bpX;
      Byte* bpY;
      UInt  iLen;
      RawStroke* rsp;

      iStroke--;                          /* Formula strokes are 1-based, my stroke
                                                 * array is 0-based. */

      if (iStroke >= pScorer->m_iStrokeCnt)
            return 0;                     /* Should not happen... */


      rsp = pScorer->m_pRawStrokes + iStroke;
      iLen = rsp->m_len;
      bpX = rsp->m_x;
      bpY = rsp->m_y;

      /* Heretofore we have left the coordinates as we got them, screen
       * coordinates with 0,0 in upper left, y increasing downward,
       * x increasing to the right.  And the extra filters agree with this.
       * -rwells, 970723.
       *
       * Removed the subtraction of Rect_x, Rect_y here - it will mess
       * up debugging messages if the client doesn't subtract them before-
       * hand, but otherwise should be harmless.
       *  - OWT, 970903
       */

      switch(cArg) {
      case 'x':
            return bpX[0];
      case 'y':
            return bpY[0];
      case 'i':
            return bpX[iLen-1];
      case 'j':
            return bpY[iLen-1];
      case 'a':
            return ((bpX[0] + bpX[iLen-1]) >> 1);
      case 'b':
            return ((bpY[0] + bpY[iLen-1]) >> 1);
      
      case 'l':
            /* These are byte values - they can't get very large,
             * so don't need to check against diMaxScoreToSquare...
             */
            iSquared = (((Long) bpX[0]) - ((Long)bpX[iLen-1]));
            iVal = iSquared * iSquared;

            iSquared = (((Long) bpY[0]) - ((Long)bpY[iLen-1]));
            iVal += iSquared * iSquared;

            return (Long) SqrtULong((Long) iVal);
      }
      
      return 0;                           /* Unrecognized cArg cmd char. */
}
/* ----- end of scoring.c --------------------------------------------------*/

Generated by  Doxygen 1.6.0   Back to index