Class FinderPatternFinder

  • Direct Known Subclasses:
    MultiFinderPatternFinder

    public class FinderPatternFinder
    extends java.lang.Object

    This class attempts to find finder patterns in a QR Code. Finder patterns are the square markers at three corners of a QR Code.

    This class is thread-safe but not reentrant. Each thread must allocate its own object.

    • Constructor Detail

      • FinderPatternFinder

        public FinderPatternFinder​(BitMatrix image)

        Creates a finder that will search the image for three finder patterns.

        Parameters:
        image - image to search
    • Method Detail

      • getImage

        protected final BitMatrix getImage()
      • getPossibleCenters

        protected final java.util.List<FinderPattern> getPossibleCenters()
      • centerFromEnd

        private static float centerFromEnd​(int[] stateCount,
                                           int end)
        Given a count of black/white/black/white/black pixels just seen and an end position, figures the location of the center of this run.
      • foundPatternCross

        protected static boolean foundPatternCross​(int[] stateCount)
        Parameters:
        stateCount - count of black/white/black/white/black pixels just read
        Returns:
        true iff the proportions of the counts is close enough to the 1/1/3/1/1 ratios used by finder patterns to be considered a match
      • foundPatternDiagonal

        protected static boolean foundPatternDiagonal​(int[] stateCount)
        Parameters:
        stateCount - count of black/white/black/white/black pixels just read
        Returns:
        true iff the proportions of the counts is close enough to the 1/1/3/1/1 ratios used by finder patterns to be considered a match
      • getCrossCheckStateCount

        private int[] getCrossCheckStateCount()
      • clearCounts

        @Deprecated
        protected final void clearCounts​(int[] counts)
        Deprecated.
      • shiftCounts2

        @Deprecated
        protected final void shiftCounts2​(int[] stateCount)
        Deprecated.
      • doClearCounts

        protected static void doClearCounts​(int[] counts)
      • doShiftCounts2

        protected static void doShiftCounts2​(int[] stateCount)
      • crossCheckDiagonal

        private boolean crossCheckDiagonal​(int centerI,
                                           int centerJ)
        After a vertical and horizontal scan finds a potential finder pattern, this method "cross-cross-cross-checks" by scanning down diagonally through the center of the possible finder pattern to see if the same proportion is detected.
        Parameters:
        centerI - row where a finder pattern was detected
        centerJ - center of the section that appears to cross a finder pattern
        Returns:
        true if proportions are withing expected limits
      • crossCheckVertical

        private float crossCheckVertical​(int startI,
                                         int centerJ,
                                         int maxCount,
                                         int originalStateCountTotal)

        After a horizontal scan finds a potential finder pattern, this method "cross-checks" by scanning down vertically through the center of the possible finder pattern to see if the same proportion is detected.

        Parameters:
        startI - row where a finder pattern was detected
        centerJ - center of the section that appears to cross a finder pattern
        maxCount - maximum reasonable number of modules that should be observed in any reading state, based on the results of the horizontal scan
        Returns:
        vertical center of finder pattern, or Float.NaN if not found
      • crossCheckHorizontal

        private float crossCheckHorizontal​(int startJ,
                                           int centerI,
                                           int maxCount,
                                           int originalStateCountTotal)

        Like crossCheckVertical(int, int, int, int), and in fact is basically identical, except it reads horizontally instead of vertically. This is used to cross-cross check a vertical cross check and locate the real center of the alignment pattern.

      • handlePossibleCenter

        @Deprecated
        protected final boolean handlePossibleCenter​(int[] stateCount,
                                                     int i,
                                                     int j,
                                                     boolean pureBarcode)
        Deprecated.
        only exists for backwards compatibility
        Parameters:
        stateCount - reading state module counts from horizontal scan
        i - row where finder pattern may be found
        j - end of possible finder pattern in row
        pureBarcode - ignored
        Returns:
        true if a finder pattern candidate was found this time
        See Also:
        handlePossibleCenter(int[], int, int)
      • handlePossibleCenter

        protected final boolean handlePossibleCenter​(int[] stateCount,
                                                     int i,
                                                     int j)

        This is called when a horizontal scan finds a possible alignment pattern. It will cross check with a vertical scan, and if successful, will, ah, cross-cross-check with another horizontal scan. This is needed primarily to locate the real horizontal center of the pattern in cases of extreme skew. And then we cross-cross-cross check with another diagonal scan.

        If that succeeds the finder pattern location is added to a list that tracks the number of times each location has been nearly-matched as a finder pattern. Each additional find is more evidence that the location is in fact a finder pattern center

        Parameters:
        stateCount - reading state module counts from horizontal scan
        i - row where finder pattern may be found
        j - end of possible finder pattern in row
        Returns:
        true if a finder pattern candidate was found this time
      • findRowSkip

        private int findRowSkip()
        Returns:
        number of rows we could safely skip during scanning, based on the first two finder patterns that have been located. In some cases their position will allow us to infer that the third pattern must lie below a certain point farther down in the image.
      • haveMultiplyConfirmedCenters

        private boolean haveMultiplyConfirmedCenters()
        Returns:
        true iff we have found at least 3 finder patterns that have been detected at least CENTER_QUORUM times each, and, the estimated module size of the candidates is "pretty similar"
      • squaredDistance

        private static double squaredDistance​(FinderPattern a,
                                              FinderPattern b)
        Get square of distance between a and b.
      • selectBestPatterns

        private FinderPattern[] selectBestPatterns()
                                            throws NotFoundException
        Returns:
        the 3 best FinderPatterns from our list of candidates. The "best" are those have similar module size and form a shape closer to a isosceles right triangle.
        Throws:
        NotFoundException - if 3 such finder patterns do not exist