Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /* quirc - QR-code recognition library
  2.  * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>
  3.  *
  4.  * Permission to use, copy, modify, and/or distribute this software for any
  5.  * purpose with or without fee is hereby granted, provided that the above
  6.  * copyright notice and this permission notice appear in all copies.
  7.  *
  8.  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9.  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10.  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11.  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12.  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13.  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14.  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15.  */
  16.  
  17. /*#ifndef INT_MAX
  18. #define INT_MAX 2147483647
  19. #endif*/
  20. #include <limits.h>
  21. #include <string.h>
  22. #include <stdlib.h>
  23. #include <math.h>
  24. #include "quirc_internal.h"
  25.  
  26. /*----------------------------------------------------------------------------------------*/
  27.  
  28. /************************************************************************
  29.  * Linear algebra routines
  30.  */
  31.  
  32. static int line_intersect(const struct quirc_point *p0,
  33.                           const struct quirc_point *p1,
  34.                           const struct quirc_point *q0,
  35.                           const struct quirc_point *q1,
  36.                           struct quirc_point *r)
  37. {
  38.         /* (a, b) is perpendicular to line p */
  39.         int a = -(p1->y - p0->y);
  40.         int b = p1->x - p0->x;
  41.  
  42.         /* (c, d) is perpendicular to line q */
  43.         int c = -(q1->y - q0->y);
  44.         int d = q1->x - q0->x;
  45.  
  46.         /* e and f are dot products of the respective vectors with p and q */
  47.         int e = a * p1->x + b * p1->y;
  48.         int f = c * q1->x + d * q1->y;
  49.  
  50.         /* Now we need to solve:
  51.          *     [a b] [rx]   [e]
  52.          *     [c d] [ry] = [f]
  53.          *
  54.          * We do this by inverting the matrix and applying it to (e, f):
  55.          *       [ d -b] [e]   [rx]
  56.          * 1/det [-c  a] [f] = [ry]
  57.          */
  58.         int det = (a * d) - (b * c);
  59.  
  60.         if (!det)
  61.                 return 0;
  62.  
  63.         r->x = (d * e - b * f) / det;
  64.         r->y = (-c * e + a * f) / det;
  65.  
  66.         return 1;
  67. }
  68.  
  69. static void perspective_setup(double *c,
  70.                               const struct quirc_point *rect,
  71.                               double w, double h)
  72. {
  73.         double x0 = rect[0].x;
  74.         double y0 = rect[0].y;
  75.         double x1 = rect[1].x;
  76.         double y1 = rect[1].y;
  77.         double x2 = rect[2].x;
  78.         double y2 = rect[2].y;
  79.         double x3 = rect[3].x;
  80.         double y3 = rect[3].y;
  81.  
  82.         double wden = w * (x2*y3 - x3*y2 + (x3-x2)*y1 + x1*(y2-y3));
  83.         double hden = h * (x2*y3 + x1*(y2-y3) - x3*y2 + (x3-x2)*y1);
  84.  
  85.         c[0] = (x1*(x2*y3-x3*y2) + x0*(-x2*y3+x3*y2+(x2-x3)*y1) +
  86.                 x1*(x3-x2)*y0) / wden;
  87.         c[1] = -(x0*(x2*y3+x1*(y2-y3)-x2*y1) - x1*x3*y2 + x2*x3*y1
  88.                  + (x1*x3-x2*x3)*y0) / hden;
  89.         c[2] = x0;
  90.         c[3] = (y0*(x1*(y3-y2)-x2*y3+x3*y2) + y1*(x2*y3-x3*y2) +
  91.                 x0*y1*(y2-y3)) / wden;
  92.         c[4] = (x0*(y1*y3-y2*y3) + x1*y2*y3 - x2*y1*y3 +
  93.                 y0*(x3*y2-x1*y2+(x2-x3)*y1)) / hden;
  94.         c[5] = y0;
  95.         c[6] = (x1*(y3-y2) + x0*(y2-y3) + (x2-x3)*y1 + (x3-x2)*y0) / wden;
  96.         c[7] = (-x2*y3 + x1*y3 + x3*y2 + x0*(y1-y2) - x3*y1 + (x2-x1)*y0) /
  97.                 hden;
  98. }
  99.  
  100. static void perspective_map(const double *c,
  101.                             double u, double v, struct quirc_point *ret)
  102. {
  103.         double den = c[6]*u + c[7]*v + 1.0;
  104.         double x = (c[0]*u + c[1]*v + c[2]) / den;
  105.         double y = (c[3]*u + c[4]*v + c[5]) / den;
  106.  
  107.         ret->x = (int) rint(x);
  108.         ret->y = (int) rint(y);
  109. }
  110.  
  111. static void perspective_unmap(const double *c,
  112.                               const struct quirc_point *in,
  113.                               double *u, double *v)
  114. {
  115.         double x = in->x;
  116.         double y = in->y;
  117.         double den = -c[0]*c[7]*y + c[1]*c[6]*y + (c[3]*c[7]-c[4]*c[6])*x +
  118.                 c[0]*c[4] - c[1]*c[3];
  119.  
  120.         *u = -(c[1]*(y-c[5]) - c[2]*c[7]*y + (c[5]*c[7]-c[4])*x + c[2]*c[4]) /
  121.                 den;
  122.         *v = (c[0]*(y-c[5]) - c[2]*c[6]*y + (c[5]*c[6]-c[3])*x + c[2]*c[3]) /
  123.                 den;
  124. }
  125.  
  126. /************************************************************************
  127.  * Span-based floodfill routine
  128.  */
  129.  
  130. #define FLOOD_FILL_MAX_DEPTH            4096
  131.  
  132. typedef void (*span_func_t)(void *user_data, int y, int left, int right);
  133.  
  134. static void flood_fill_seed(struct quirc *q, int x, int y, int from, int to,
  135.                             span_func_t func, void *user_data,
  136.                             int depth)
  137. {
  138.         int left = x;
  139.         int right = x;
  140.         int i;
  141.         quirc_pixel_t *row = q->pixels + y * q->w;
  142.  
  143.         if (depth >= FLOOD_FILL_MAX_DEPTH)
  144.                 return;
  145.  
  146.         while (left > 0 && row[left - 1] == from)
  147.                 left--;
  148.  
  149.         while (right < q->w - 1 && row[right + 1] == from)
  150.                 right++;
  151.  
  152.         /* Fill the extent */
  153.         for (i = left; i <= right; i++)
  154.                 row[i] = to;
  155.  
  156.         if (func)
  157.                 func(user_data, y, left, right);
  158.  
  159.         /* Seed new flood-fills */
  160.         if (y > 0) {
  161.                 row = q->pixels + (y - 1) * q->w;
  162.  
  163.                 for (i = left; i <= right; i++)
  164.                         if (row[i] == from)
  165.                                 flood_fill_seed(q, i, y - 1, from, to,
  166.                                                 func, user_data, depth + 1);
  167.         }
  168.  
  169.         if (y < q->h - 1) {
  170.                 row = q->pixels + (y + 1) * q->w;
  171.  
  172.                 for (i = left; i <= right; i++)
  173.                         if (row[i] == from)
  174.                                 flood_fill_seed(q, i, y + 1, from, to,
  175.                                                 func, user_data, depth + 1);
  176.         }
  177. }
  178.  
  179. /************************************************************************
  180.  * Adaptive thresholding
  181.  */
  182.  
  183. static uint8_t otsu(const struct quirc *q)
  184. {
  185.         int numPixels = q->w * q->h;
  186.  
  187.         // Calculate histogram
  188.         unsigned int histogram[UINT8_MAX + 1];
  189.         (void)memset(histogram, 0, sizeof(histogram));
  190.         uint8_t* ptr = q->image;
  191.         int length = numPixels;
  192.         while (length--) {
  193.                 uint8_t value = *ptr++;
  194.                 histogram[value]++;
  195.         }
  196.  
  197.         // Calculate weighted sum of histogram values
  198.         unsigned int sum = 0;
  199.         unsigned int i = 0;
  200.         for (i = 0; i <= UINT8_MAX; ++i) {
  201.                 sum += i * histogram[i];
  202.         }
  203.  
  204.         // Compute threshold
  205.         int sumB = 0;
  206.         int q1 = 0;
  207.         double max = 0;
  208.         uint8_t threshold = 0;
  209.         for (i = 0; i <= UINT8_MAX; ++i) {
  210.                 // Weighted background
  211.                 q1 += histogram[i];
  212.                 if (q1 == 0)
  213.                         continue;
  214.  
  215.                 // Weighted foreground
  216.                 const int q2 = numPixels - q1;
  217.                 if (q2 == 0)
  218.                         break;
  219.  
  220.                 sumB += i * histogram[i];
  221.                 const double m1 = (double)sumB / q1;
  222.                 const double m2 = ((double)sum - sumB) / q2;
  223.                 const double m1m2 = m1 - m2;
  224.                 const double variance = m1m2 * m1m2 * q1 * q2;
  225.                 if (variance >= max) {
  226.                         threshold = i;
  227.                         max = variance;
  228.                 }
  229.         }
  230.  
  231.         return threshold;
  232. }
  233.  
  234. static void area_count(void *user_data, int y, int left, int right)
  235. {
  236.         ((struct quirc_region *)user_data)->count += right - left + 1;
  237. }
  238.  
  239. static int region_code(struct quirc *q, int x, int y)
  240. {
  241.         int pixel;
  242.         struct quirc_region *box;
  243.         int region;
  244.  
  245.         if (x < 0 || y < 0 || x >= q->w || y >= q->h)
  246.                 return -1;
  247.  
  248.         pixel = q->pixels[y * q->w + x];
  249.  
  250.         if (pixel >= QUIRC_PIXEL_REGION)
  251.                 return pixel;
  252.  
  253.         if (pixel == QUIRC_PIXEL_WHITE)
  254.                 return -1;
  255.  
  256.         if (q->num_regions >= QUIRC_MAX_REGIONS)
  257.                 return -1;
  258.  
  259.         region = q->num_regions;
  260.         box = &q->regions[q->num_regions++];
  261.  
  262.         memset(box, 0, sizeof(*box));
  263.  
  264.         box->seed.x = x;
  265.         box->seed.y = y;
  266.         box->capstone = -1;
  267.  
  268.         flood_fill_seed(q, x, y, pixel, region, area_count, box, 0);
  269.  
  270.         return region;
  271. }
  272.  
  273. struct polygon_score_data {
  274.         struct quirc_point      ref;
  275.  
  276.         int                     scores[4];
  277.         struct quirc_point      *corners;
  278. };
  279.  
  280. static void find_one_corner(void *user_data, int y, int left, int right)
  281. {
  282.         struct polygon_score_data *psd =
  283.                 (struct polygon_score_data *)user_data;
  284.         int xs[2] = {left, right};
  285.         int dy = y - psd->ref.y;
  286.         int i;
  287.  
  288.         for (i = 0; i < 2; i++) {
  289.                 int dx = xs[i] - psd->ref.x;
  290.                 int d = dx * dx + dy * dy;
  291.  
  292.                 if (d > psd->scores[0]) {
  293.                         psd->scores[0] = d;
  294.                         psd->corners[0].x = xs[i];
  295.                         psd->corners[0].y = y;
  296.                 }
  297.         }
  298. }
  299.  
  300. static void find_other_corners(void *user_data, int y, int left, int right)
  301. {
  302.         struct polygon_score_data *psd =
  303.                 (struct polygon_score_data *)user_data;
  304.         int xs[2] = {left, right};
  305.         int i;
  306.  
  307.         for (i = 0; i < 2; i++) {
  308.                 int up = xs[i] * psd->ref.x + y * psd->ref.y;
  309.                 int right = xs[i] * -psd->ref.y + y * psd->ref.x;
  310.                 int scores[4] = {up, right, -up, -right};
  311.                 int j;
  312.  
  313.                 for (j = 0; j < 4; j++) {
  314.                         if (scores[j] > psd->scores[j]) {
  315.                                 psd->scores[j] = scores[j];
  316.                                 psd->corners[j].x = xs[i];
  317.                                 psd->corners[j].y = y;
  318.                         }
  319.                 }
  320.         }
  321. }
  322.  
  323. static void find_region_corners(struct quirc *q,
  324.                                 int rcode, const struct quirc_point *ref,
  325.                                 struct quirc_point *corners)
  326. {
  327.         struct quirc_region *region = &q->regions[rcode];
  328.         struct polygon_score_data psd;
  329.         int i;
  330.  
  331.         memset(&psd, 0, sizeof(psd));
  332.         psd.corners = corners;
  333.  
  334.         memcpy(&psd.ref, ref, sizeof(psd.ref));
  335.         psd.scores[0] = -1;
  336.         flood_fill_seed(q, region->seed.x, region->seed.y,
  337.                         rcode, QUIRC_PIXEL_BLACK,
  338.                         find_one_corner, &psd, 0);
  339.  
  340.         psd.ref.x = psd.corners[0].x - psd.ref.x;
  341.         psd.ref.y = psd.corners[0].y - psd.ref.y;
  342.  
  343.         for (i = 0; i < 4; i++)
  344.                 memcpy(&psd.corners[i], &region->seed,
  345.                        sizeof(psd.corners[i]));
  346.  
  347.         i = region->seed.x * psd.ref.x + region->seed.y * psd.ref.y;
  348.         psd.scores[0] = i;
  349.         psd.scores[2] = -i;
  350.         i = region->seed.x * -psd.ref.y + region->seed.y * psd.ref.x;
  351.         psd.scores[1] = i;
  352.         psd.scores[3] = -i;
  353.  
  354.         flood_fill_seed(q, region->seed.x, region->seed.y,
  355.                         QUIRC_PIXEL_BLACK, rcode,
  356.                         find_other_corners, &psd, 0);
  357. }
  358.  
  359. static void record_capstone(struct quirc *q, int ring, int stone)
  360. {
  361.         struct quirc_region *stone_reg = &q->regions[stone];
  362.         struct quirc_region *ring_reg = &q->regions[ring];
  363.         struct quirc_capstone *capstone;
  364.         int cs_index;
  365.  
  366.         if (q->num_capstones >= QUIRC_MAX_CAPSTONES)
  367.                 return;
  368.  
  369.         cs_index = q->num_capstones;
  370.         capstone = &q->capstones[q->num_capstones++];
  371.  
  372.         memset(capstone, 0, sizeof(*capstone));
  373.  
  374.         capstone->qr_grid = -1;
  375.         capstone->ring = ring;
  376.         capstone->stone = stone;
  377.         stone_reg->capstone = cs_index;
  378.         ring_reg->capstone = cs_index;
  379.  
  380.         /* Find the corners of the ring */
  381.         find_region_corners(q, ring, &stone_reg->seed, capstone->corners);
  382.  
  383.         /* Set up the perspective transform and find the center */
  384.         perspective_setup(capstone->c, capstone->corners, 7.0, 7.0);
  385.         perspective_map(capstone->c, 3.5, 3.5, &capstone->center);
  386. }
  387.  
  388. static void test_capstone(struct quirc *q, int x, int y, int *pb)
  389. {
  390.         int ring_right = region_code(q, x - pb[4], y);
  391.         int stone = region_code(q, x - pb[4] - pb[3] - pb[2], y);
  392.         int ring_left = region_code(q, x - pb[4] - pb[3] -
  393.                                     pb[2] - pb[1] - pb[0],
  394.                                     y);
  395.         struct quirc_region *stone_reg;
  396.         struct quirc_region *ring_reg;
  397.         int ratio;
  398.  
  399.         if (ring_left < 0 || ring_right < 0 || stone < 0)
  400.                 return;
  401.  
  402.         /* Left and ring of ring should be connected */
  403.         if (ring_left != ring_right)
  404.                 return;
  405.  
  406.         /* Ring should be disconnected from stone */
  407.         if (ring_left == stone)
  408.                 return;
  409.  
  410.         stone_reg = &q->regions[stone];
  411.         ring_reg = &q->regions[ring_left];
  412.  
  413.         /* Already detected */
  414.         if (stone_reg->capstone >= 0 || ring_reg->capstone >= 0)
  415.                 return;
  416.  
  417.         /* Ratio should ideally be 37.5 */
  418.         ratio = stone_reg->count * 100 / ring_reg->count;
  419.         if (ratio < 10 || ratio > 70)
  420.                 return;
  421.  
  422.         record_capstone(q, ring_left, stone);
  423. }
  424.  
  425. static void finder_scan(struct quirc *q, int y)
  426. {
  427.         quirc_pixel_t *row = q->pixels + y * q->w;
  428.         int x;
  429.         int last_color = 0;
  430.         int run_length = 0;
  431.         int run_count = 0;
  432.         int pb[5];
  433.  
  434.         memset(pb, 0, sizeof(pb));
  435.         for (x = 0; x < q->w; x++) {
  436.                 int color = row[x] ? 1 : 0;
  437.  
  438.                 if (x && color != last_color) {
  439.                         memmove(pb, pb + 1, sizeof(pb[0]) * 4);
  440.                         pb[4] = run_length;
  441.                         run_length = 0;
  442.                         run_count++;
  443.  
  444.                         if (!color && run_count >= 5) {
  445.                                 static int check[5] = {1, 1, 3, 1, 1};
  446.                                 int avg, err;
  447.                                 int i;
  448.                                 int ok = 1;
  449.  
  450.                                 avg = (pb[0] + pb[1] + pb[3] + pb[4]) / 4;
  451.                                 err = avg * 3 / 4;
  452.  
  453.                                 for (i = 0; i < 5; i++)
  454.                                         if (pb[i] < check[i] * avg - err ||
  455.                                             pb[i] > check[i] * avg + err)
  456.                                                 ok = 0;
  457.  
  458.                                 if (ok)
  459.                                         test_capstone(q, x, y, pb);
  460.                         }
  461.                 }
  462.  
  463.                 run_length++;
  464.                 last_color = color;
  465.         }
  466. }
  467.  
  468. static void find_alignment_pattern(struct quirc *q, int index)
  469. {
  470.         struct quirc_grid *qr = &q->grids[index];
  471.         struct quirc_capstone *c0 = &q->capstones[qr->caps[0]];
  472.         struct quirc_capstone *c2 = &q->capstones[qr->caps[2]];
  473.         struct quirc_point a;
  474.         struct quirc_point b;
  475.         struct quirc_point c;
  476.         int size_estimate;
  477.         int step_size = 1;
  478.         int dir = 0;
  479.         double u, v;
  480.  
  481.         /* Grab our previous estimate of the alignment pattern corner */
  482.         memcpy(&b, &qr->align, sizeof(b));
  483.  
  484.         /* Guess another two corners of the alignment pattern so that we
  485.          * can estimate its size.
  486.          */
  487.         perspective_unmap(c0->c, &b, &u, &v);
  488.         perspective_map(c0->c, u, v + 1.0, &a);
  489.         perspective_unmap(c2->c, &b, &u, &v);
  490.         perspective_map(c2->c, u + 1.0, v, &c);
  491.  
  492.         size_estimate = abs((a.x - b.x) * -(c.y - b.y) +
  493.                             (a.y - b.y) * (c.x - b.x));
  494.  
  495.         /* Spiral outwards from the estimate point until we find something
  496.          * roughly the right size. Don't look too far from the estimate
  497.          * point.
  498.          */
  499.         while (step_size * step_size < size_estimate * 100) {
  500.                 static const int dx_map[] = {1, 0, -1, 0};
  501.                 static const int dy_map[] = {0, -1, 0, 1};
  502.                 int i;
  503.  
  504.                 for (i = 0; i < step_size; i++) {
  505.                         int code = region_code(q, b.x, b.y);
  506.  
  507.                         if (code >= 0) {
  508.                                 struct quirc_region *reg = &q->regions[code];
  509.  
  510.                                 if (reg->count >= size_estimate / 2 &&
  511.                                     reg->count <= size_estimate * 2) {
  512.                                         qr->align_region = code;
  513.                                         return;
  514.                                 }
  515.                         }
  516.  
  517.                         b.x += dx_map[dir];
  518.                         b.y += dy_map[dir];
  519.                 }
  520.  
  521.                 dir = (dir + 1) % 4;
  522.                 if (!(dir & 1))
  523.                         step_size++;
  524.         }
  525. }
  526.  
  527. static void find_leftmost_to_line(void *user_data, int y, int left, int right)
  528. {
  529.         struct polygon_score_data *psd =
  530.                 (struct polygon_score_data *)user_data;
  531.         int xs[2] = {left, right};
  532.         int i;
  533.  
  534.         for (i = 0; i < 2; i++) {
  535.                 int d = -psd->ref.y * xs[i] + psd->ref.x * y;
  536.  
  537.                 if (d < psd->scores[0]) {
  538.                         psd->scores[0] = d;
  539.                         psd->corners[0].x = xs[i];
  540.                         psd->corners[0].y = y;
  541.                 }
  542.         }
  543. }
  544.  
  545. /* Do a Bresenham scan from one point to another and count the number
  546.  * of black/white transitions.
  547.  */
  548. static int timing_scan(const struct quirc *q,
  549.                        const struct quirc_point *p0,
  550.                        const struct quirc_point *p1)
  551. {
  552.         int n = p1->x - p0->x;
  553.         int d = p1->y - p0->y;
  554.         int x = p0->x;
  555.         int y = p0->y;
  556.         int *dom, *nondom;
  557.         int dom_step;
  558.         int nondom_step;
  559.         int a = 0;
  560.         int i;
  561.         int run_length = 0;
  562.         int count = 0;
  563.  
  564.         if (p0->x < 0 || p0->y < 0 || p0->x >= q->w || p0->y >= q->h)
  565.                 return -1;
  566.         if (p1->x < 0 || p1->y < 0 || p1->x >= q->w || p1->y >= q->h)
  567.                 return -1;
  568.  
  569.         if (abs(n) > abs(d)) {
  570.                 int swap = n;
  571.  
  572.                 n = d;
  573.                 d = swap;
  574.  
  575.                 dom = &x;
  576.                 nondom = &y;
  577.         } else {
  578.                 dom = &y;
  579.                 nondom = &x;
  580.         }
  581.  
  582.         if (n < 0) {
  583.                 n = -n;
  584.                 nondom_step = -1;
  585.         } else {
  586.                 nondom_step = 1;
  587.         }
  588.  
  589.         if (d < 0) {
  590.                 d = -d;
  591.                 dom_step = -1;
  592.         } else {
  593.                 dom_step = 1;
  594.         }
  595.  
  596.         x = p0->x;
  597.         y = p0->y;
  598.         for (i = 0; i <= d; i++) {
  599.                 int pixel;
  600.  
  601.                 if (y < 0 || y >= q->h || x < 0 || x >= q->w)
  602.                         break;
  603.  
  604.                 pixel = q->pixels[y * q->w + x];
  605.  
  606.                 if (pixel) {
  607.                         if (run_length >= 2)
  608.                                 count++;
  609.                         run_length = 0;
  610.                 } else {
  611.                         run_length++;
  612.                 }
  613.  
  614.                 a += n;
  615.                 *dom += dom_step;
  616.                 if (a >= d) {
  617.                         *nondom += nondom_step;
  618.                         a -= d;
  619.                 }
  620.         }
  621.  
  622.         return count;
  623. }
  624.  
  625. /* Try the measure the timing pattern for a given QR code. This does
  626.  * not require the global perspective to have been set up, but it
  627.  * does require that the capstone corners have been set to their
  628.  * canonical rotation.
  629.  *
  630.  * For each capstone, we find a point in the middle of the ring band
  631.  * which is nearest the centre of the code. Using these points, we do
  632.  * a horizontal and a vertical timing scan.
  633.  */
  634. static int measure_timing_pattern(struct quirc *q, int index)
  635. {
  636.         struct quirc_grid *qr = &q->grids[index];
  637.         int i;
  638.         int scan;
  639.         int ver;
  640.         int size;
  641.  
  642.         for (i = 0; i < 3; i++) {
  643.                 static const double us[] = {6.5, 6.5, 0.5};
  644.                 static const double vs[] = {0.5, 6.5, 6.5};
  645.                 struct quirc_capstone *cap = &q->capstones[qr->caps[i]];
  646.  
  647.                 perspective_map(cap->c, us[i], vs[i], &qr->tpep[i]);
  648.         }
  649.  
  650.         qr->hscan = timing_scan(q, &qr->tpep[1], &qr->tpep[2]);
  651.         qr->vscan = timing_scan(q, &qr->tpep[1], &qr->tpep[0]);
  652.  
  653.         scan = qr->hscan;
  654.         if (qr->vscan > scan)
  655.                 scan = qr->vscan;
  656.  
  657.         /* If neither scan worked, we can't go any further. */
  658.         if (scan < 0)
  659.                 return -1;
  660.  
  661.         /* Choose the nearest allowable grid size */
  662.         size = scan * 2 + 13;
  663.         ver = (size - 15) / 4;
  664.         if (ver > QUIRC_MAX_VERSION) {
  665.                 return -1;
  666.         }
  667.  
  668.         qr->grid_size = ver * 4 + 17;
  669.         return 0;
  670. }
  671.  
  672. /* Read a cell from a grid using the currently set perspective
  673.  * transform. Returns +/- 1 for black/white, 0 for cells which are
  674.  * out of image bounds.
  675.  */
  676. static int read_cell(const struct quirc *q, int index, int x, int y)
  677. {
  678.         const struct quirc_grid *qr = &q->grids[index];
  679.         struct quirc_point p;
  680.  
  681.         perspective_map(qr->c, x + 0.5, y + 0.5, &p);
  682.         if (p.y < 0 || p.y >= q->h || p.x < 0 || p.x >= q->w)
  683.                 return 0;
  684.  
  685.         return q->pixels[p.y * q->w + p.x] ? 1 : -1;
  686. }
  687.  
  688. static int fitness_cell(const struct quirc *q, int index, int x, int y)
  689. {
  690.         const struct quirc_grid *qr = &q->grids[index];
  691.         int score = 0;
  692.         int u, v;
  693.  
  694.         for (v = 0; v < 3; v++)
  695.                 for (u = 0; u < 3; u++) {
  696.                         static const double offsets[] = {0.3, 0.5, 0.7};
  697.                         struct quirc_point p;
  698.  
  699.                         perspective_map(qr->c, x + offsets[u],
  700.                                                y + offsets[v], &p);
  701.                         if (p.y < 0 || p.y >= q->h || p.x < 0 || p.x >= q->w)
  702.                                 continue;
  703.  
  704.                         if (q->pixels[p.y * q->w + p.x])
  705.                                 score++;
  706.                         else
  707.                                 score--;
  708.                 }
  709.  
  710.         return score;
  711. }
  712.  
  713. static int fitness_ring(const struct quirc *q, int index, int cx, int cy,
  714.                         int radius)
  715. {
  716.         int i;
  717.         int score = 0;
  718.  
  719.         for (i = 0; i < radius * 2; i++) {
  720.                 score += fitness_cell(q, index, cx - radius + i, cy - radius);
  721.                 score += fitness_cell(q, index, cx - radius, cy + radius - i);
  722.                 score += fitness_cell(q, index, cx + radius, cy - radius + i);
  723.                 score += fitness_cell(q, index, cx + radius - i, cy + radius);
  724.         }
  725.  
  726.         return score;
  727. }
  728.  
  729. static int fitness_apat(const struct quirc *q, int index, int cx, int cy)
  730. {
  731.         return fitness_cell(q, index, cx, cy) -
  732.                 fitness_ring(q, index, cx, cy, 1) +
  733.                 fitness_ring(q, index, cx, cy, 2);
  734. }
  735.  
  736. static int fitness_capstone(const struct quirc *q, int index, int x, int y)
  737. {
  738.         x += 3;
  739.         y += 3;
  740.  
  741.         return fitness_cell(q, index, x, y) +
  742.                 fitness_ring(q, index, x, y, 1) -
  743.                 fitness_ring(q, index, x, y, 2) +
  744.                 fitness_ring(q, index, x, y, 3);
  745. }
  746.  
  747. /* Compute a fitness score for the currently configured perspective
  748.  * transform, using the features we expect to find by scanning the
  749.  * grid.
  750.  */
  751. static int fitness_all(const struct quirc *q, int index)
  752. {
  753.         const struct quirc_grid *qr = &q->grids[index];
  754.         int version = (qr->grid_size - 17) / 4;
  755.         const struct quirc_version_info *info = &quirc_version_db[version];
  756.         int score = 0;
  757.         int i, j;
  758.         int ap_count;
  759.  
  760.         /* Check the timing pattern */
  761.         for (i = 0; i < qr->grid_size - 14; i++) {
  762.                 int expect = (i & 1) ? 1 : -1;
  763.  
  764.                 score += fitness_cell(q, index, i + 7, 6) * expect;
  765.                 score += fitness_cell(q, index, 6, i + 7) * expect;
  766.         }
  767.  
  768.         /* Check capstones */
  769.         score += fitness_capstone(q, index, 0, 0);
  770.         score += fitness_capstone(q, index, qr->grid_size - 7, 0);
  771.         score += fitness_capstone(q, index, 0, qr->grid_size - 7);
  772.  
  773.         if (version < 0 || version > QUIRC_MAX_VERSION)
  774.                 return score;
  775.  
  776.         /* Check alignment patterns */
  777.         ap_count = 0;
  778.         while ((ap_count < QUIRC_MAX_ALIGNMENT) && info->apat[ap_count])
  779.                 ap_count++;
  780.  
  781.         for (i = 1; i + 1 < ap_count; i++) {
  782.                 score += fitness_apat(q, index, 6, info->apat[i]);
  783.                 score += fitness_apat(q, index, info->apat[i], 6);
  784.         }
  785.  
  786.         for (i = 1; i < ap_count; i++)
  787.                 for (j = 1; j < ap_count; j++)
  788.                         score += fitness_apat(q, index,
  789.                                         info->apat[i], info->apat[j]);
  790.  
  791.         return score;
  792. }
  793.  
  794. static void jiggle_perspective(struct quirc *q, int index)
  795. {
  796.         struct quirc_grid *qr = &q->grids[index];
  797.         int best = fitness_all(q, index);
  798.         int pass;
  799.         double adjustments[8];
  800.         int i;
  801.  
  802.         for (i = 0; i < 8; i++)
  803.                 adjustments[i] = qr->c[i] * 0.02;
  804.  
  805.         for (pass = 0; pass < 5; pass++) {
  806.                 for (i = 0; i < 16; i++) {
  807.                         int j = i >> 1;
  808.                         int test;
  809.                         double old = qr->c[j];
  810.                         double step = adjustments[j];
  811.                         double new;
  812.  
  813.                         if (i & 1)
  814.                                 new = old + step;
  815.                         else
  816.                                 new = old - step;
  817.  
  818.                         qr->c[j] = new;
  819.                         test = fitness_all(q, index);
  820.  
  821.                         if (test > best)
  822.                                 best = test;
  823.                         else
  824.                                 qr->c[j] = old;
  825.                 }
  826.  
  827.                 for (i = 0; i < 8; i++)
  828.                         adjustments[i] *= 0.5;
  829.         }
  830. }
  831.  
  832. /* Once the capstones are in place and an alignment point has been
  833.  * chosen, we call this function to set up a grid-reading perspective
  834.  * transform.
  835.  */
  836. static void setup_qr_perspective(struct quirc *q, int index)
  837. {
  838.         struct quirc_grid *qr = &q->grids[index];
  839.         struct quirc_point rect[4];
  840.  
  841.         /* Set up the perspective map for reading the grid */
  842.         memcpy(&rect[0], &q->capstones[qr->caps[1]].corners[0],
  843.                sizeof(rect[0]));
  844.         memcpy(&rect[1], &q->capstones[qr->caps[2]].corners[0],
  845.                sizeof(rect[0]));
  846.         memcpy(&rect[2], &qr->align, sizeof(rect[0]));
  847.         memcpy(&rect[3], &q->capstones[qr->caps[0]].corners[0],
  848.                sizeof(rect[0]));
  849.         perspective_setup(qr->c, rect, qr->grid_size - 7, qr->grid_size - 7);
  850.  
  851.         jiggle_perspective(q, index);
  852. }
  853.  
  854. /* Rotate the capstone with so that corner 0 is the leftmost with respect
  855.  * to the given reference line.
  856.  */
  857. static void rotate_capstone(struct quirc_capstone *cap,
  858.                             const struct quirc_point *h0,
  859.                             const struct quirc_point *hd)
  860. {
  861.         struct quirc_point copy[4];
  862.         int j;
  863.         int best = 0;
  864.         int best_score = INT_MAX;
  865.  
  866.         for (j = 0; j < 4; j++) {
  867.                 struct quirc_point *p = &cap->corners[j];
  868.                 int score = (p->x - h0->x) * -hd->y +
  869.                         (p->y - h0->y) * hd->x;
  870.  
  871.                 if (!j || score < best_score) {
  872.                         best = j;
  873.                         best_score = score;
  874.                 }
  875.         }
  876.  
  877.         /* Rotate the capstone */
  878.         for (j = 0; j < 4; j++)
  879.                 memcpy(&copy[j], &cap->corners[(j + best) % 4],
  880.                        sizeof(copy[j]));
  881.         memcpy(cap->corners, copy, sizeof(cap->corners));
  882.         perspective_setup(cap->c, cap->corners, 7.0, 7.0);
  883. }
  884.  
  885. static void record_qr_grid(struct quirc *q, int a, int b, int c)
  886. {
  887.         struct quirc_point h0, hd;
  888.         int i;
  889.         int qr_index;
  890.         struct quirc_grid *qr;
  891.  
  892.         if (q->num_grids >= QUIRC_MAX_GRIDS)
  893.                 return;
  894.  
  895.         /* Construct the hypotenuse line from A to C. B should be to
  896.          * the left of this line.
  897.          */
  898.         memcpy(&h0, &q->capstones[a].center, sizeof(h0));
  899.         hd.x = q->capstones[c].center.x - q->capstones[a].center.x;
  900.         hd.y = q->capstones[c].center.y - q->capstones[a].center.y;
  901.  
  902.         /* Make sure A-B-C is clockwise */
  903.         if ((q->capstones[b].center.x - h0.x) * -hd.y +
  904.             (q->capstones[b].center.y - h0.y) * hd.x > 0) {
  905.                 int swap = a;
  906.  
  907.                 a = c;
  908.                 c = swap;
  909.                 hd.x = -hd.x;
  910.                 hd.y = -hd.y;
  911.         }
  912.  
  913.         /* Record the grid and its components */
  914.         qr_index = q->num_grids;
  915.         qr = &q->grids[q->num_grids++];
  916.  
  917.         memset(qr, 0, sizeof(*qr));
  918.         qr->caps[0] = a;
  919.         qr->caps[1] = b;
  920.         qr->caps[2] = c;
  921.         qr->align_region = -1;
  922.  
  923.         /* Rotate each capstone so that corner 0 is top-left with respect
  924.          * to the grid.
  925.          */
  926.         for (i = 0; i < 3; i++) {
  927.                 struct quirc_capstone *cap = &q->capstones[qr->caps[i]];
  928.  
  929.                 rotate_capstone(cap, &h0, &hd);
  930.                 cap->qr_grid = qr_index;
  931.         }
  932.  
  933.         /* Check the timing pattern. This doesn't require a perspective
  934.          * transform.
  935.          */
  936.         if (measure_timing_pattern(q, qr_index) < 0)
  937.                 goto fail;
  938.  
  939.         /* Make an estimate based for the alignment pattern based on extending
  940.          * lines from capstones A and C.
  941.          */
  942.         if (!line_intersect(&q->capstones[a].corners[0],
  943.                             &q->capstones[a].corners[1],
  944.                             &q->capstones[c].corners[0],
  945.                             &q->capstones[c].corners[3],
  946.                             &qr->align))
  947.                 goto fail;
  948.  
  949.         /* On V2+ grids, we should use the alignment pattern. */
  950.         if (qr->grid_size > 21) {
  951.                 /* Try to find the actual location of the alignment pattern. */
  952.                 find_alignment_pattern(q, qr_index);
  953.  
  954.                 /* Find the point of the alignment pattern closest to the
  955.                  * top-left of the QR grid.
  956.                  */
  957.                 if (qr->align_region >= 0) {
  958.                         struct polygon_score_data psd;
  959.                         struct quirc_region *reg =
  960.                                 &q->regions[qr->align_region];
  961.  
  962.                         /* Start from some point inside the alignment pattern */
  963.                         memcpy(&qr->align, &reg->seed, sizeof(qr->align));
  964.  
  965.                         memcpy(&psd.ref, &hd, sizeof(psd.ref));
  966.                         psd.corners = &qr->align;
  967.                         psd.scores[0] = -hd.y * qr->align.x +
  968.                                 hd.x * qr->align.y;
  969.  
  970.                         flood_fill_seed(q, reg->seed.x, reg->seed.y,
  971.                                         qr->align_region, QUIRC_PIXEL_BLACK,
  972.                                         NULL, NULL, 0);
  973.                         flood_fill_seed(q, reg->seed.x, reg->seed.y,
  974.                                         QUIRC_PIXEL_BLACK, qr->align_region,
  975.                                         find_leftmost_to_line, &psd, 0);
  976.                 }
  977.         }
  978.  
  979.         setup_qr_perspective(q, qr_index);
  980.         return;
  981.  
  982. fail:
  983.         /* We've been unable to complete setup for this grid. Undo what we've
  984.          * recorded and pretend it never happened.
  985.          */
  986.         for (i = 0; i < 3; i++)
  987.                 q->capstones[qr->caps[i]].qr_grid = -1;
  988.         q->num_grids--;
  989. }
  990.  
  991. struct neighbour {
  992.         int             index;
  993.         double          distance;
  994. };
  995.  
  996. struct neighbour_list {
  997.         struct neighbour        n[QUIRC_MAX_CAPSTONES];
  998.         int                     count;
  999. };
  1000.  
  1001. static void test_neighbours(struct quirc *q, int i,
  1002.                             const struct neighbour_list *hlist,
  1003.                             const struct neighbour_list *vlist)
  1004. {
  1005.         int j, k;
  1006.         double best_score = 0.0;
  1007.         int best_h = -1, best_v = -1;
  1008.  
  1009.         /* Test each possible grouping */
  1010.         for (j = 0; j < hlist->count; j++)
  1011.                 for (k = 0; k < vlist->count; k++) {
  1012.                         const struct neighbour *hn = &hlist->n[j];
  1013.                         const struct neighbour *vn = &vlist->n[k];
  1014.                         double score = fabs(1.0 - hn->distance / vn->distance);
  1015.  
  1016.                         if (score > 2.5)
  1017.                                 continue;
  1018.  
  1019.                         if (best_h < 0 || score < best_score) {
  1020.                                 best_h = hn->index;
  1021.                                 best_v = vn->index;
  1022.                                 best_score = score;
  1023.                         }
  1024.                 }
  1025.  
  1026.         if (best_h < 0 || best_v < 0)
  1027.                 return;
  1028.  
  1029.         record_qr_grid(q, best_h, i, best_v);
  1030. }
  1031.  
  1032. static void test_grouping(struct quirc *q, int i)
  1033. {
  1034.         struct quirc_capstone *c1 = &q->capstones[i];
  1035.         int j;
  1036.         struct neighbour_list hlist;
  1037.         struct neighbour_list vlist;
  1038.  
  1039.         if (c1->qr_grid >= 0)
  1040.                 return;
  1041.  
  1042.         hlist.count = 0;
  1043.         vlist.count = 0;
  1044.  
  1045.         /* Look for potential neighbours by examining the relative gradients
  1046.          * from this capstone to others.
  1047.          */
  1048.         for (j = 0; j < q->num_capstones; j++) {
  1049.                 struct quirc_capstone *c2 = &q->capstones[j];
  1050.                 double u, v;
  1051.  
  1052.                 if (i == j || c2->qr_grid >= 0)
  1053.                         continue;
  1054.  
  1055.                 perspective_unmap(c1->c, &c2->center, &u, &v);
  1056.  
  1057.                 u = fabs(u - 3.5);
  1058.                 v = fabs(v - 3.5);
  1059.  
  1060.                 if (u < 0.2 * v) {
  1061.                         struct neighbour *n = &hlist.n[hlist.count++];
  1062.  
  1063.                         n->index = j;
  1064.                         n->distance = v;
  1065.                 }
  1066.  
  1067.                 if (v < 0.2 * u) {
  1068.                         struct neighbour *n = &vlist.n[vlist.count++];
  1069.  
  1070.                         n->index = j;
  1071.                         n->distance = u;
  1072.                 }
  1073.         }
  1074.  
  1075.         if (!(hlist.count && vlist.count))
  1076.                 return;
  1077.  
  1078.         test_neighbours(q, i, &hlist, &vlist);
  1079. }
  1080.  
  1081. static void pixels_setup(struct quirc *q, uint8_t threshold)
  1082. {
  1083.         if (QUIRC_PIXEL_ALIAS_IMAGE) {
  1084.                 q->pixels = (quirc_pixel_t *)q->image;
  1085.         }
  1086.  
  1087.         uint8_t* source = q->image;
  1088.         quirc_pixel_t* dest = q->pixels;
  1089.         int length = q->w * q->h;
  1090.         while (length--) {
  1091.                 uint8_t value = *source++;
  1092.                 *dest++ = (value < threshold) ? QUIRC_PIXEL_BLACK : QUIRC_PIXEL_WHITE;
  1093.         }
  1094. }
  1095.  
  1096. uint8_t *quirc_begin(struct quirc *q, int *w, int *h)
  1097. {
  1098.         q->num_regions = QUIRC_PIXEL_REGION;
  1099.         q->num_capstones = 0;
  1100.         q->num_grids = 0;
  1101.  
  1102.         if (w)
  1103.                 *w = q->w;
  1104.         if (h)
  1105.                 *h = q->h;
  1106.  
  1107.         return q->image;
  1108. }
  1109.  
  1110. void quirc_end(struct quirc *q)
  1111. {
  1112.         int i;
  1113.  
  1114.         uint8_t threshold = otsu(q);
  1115.         pixels_setup(q, threshold);
  1116.  
  1117.         for (i = 0; i < q->h; i++)
  1118.                 finder_scan(q, i);
  1119.  
  1120.         for (i = 0; i < q->num_capstones; i++)
  1121.                 test_grouping(q, i);
  1122. }
  1123.  
  1124. void quirc_extract(const struct quirc *q, int index,
  1125.                    struct quirc_code *code)
  1126. {
  1127.         const struct quirc_grid *qr = &q->grids[index];
  1128.         int y;
  1129.         int i = 0;
  1130.  
  1131.         if (index < 0 || index > q->num_grids)
  1132.                 return;
  1133.  
  1134.         memset(code, 0, sizeof(*code));
  1135.  
  1136.         perspective_map(qr->c, 0.0, 0.0, &code->corners[0]);
  1137.         perspective_map(qr->c, qr->grid_size, 0.0, &code->corners[1]);
  1138.         perspective_map(qr->c, qr->grid_size, qr->grid_size,
  1139.                         &code->corners[2]);
  1140.         perspective_map(qr->c, 0.0, qr->grid_size, &code->corners[3]);
  1141.  
  1142.         code->size = qr->grid_size;
  1143.  
  1144.         for (y = 0; y < qr->grid_size; y++) {
  1145.                 int x;
  1146.                 for (x = 0; x < qr->grid_size; x++) {
  1147.                         if (read_cell(q, index, x, y) > 0) {
  1148.                                 code->cell_bitmap[i >> 3] |= (1 << (i & 7));
  1149.                         }
  1150.                         i++;
  1151.                 }
  1152.         }
  1153. }
  1154.