QR Code

• 2D barcodes have unique symbols which help the automated reader to determine the barcode's orientation.
• First try: I was trying to detect the markers using correlations techniques, but due to the fact that the markers can be in any size, angle and slight skew, I decided to abandon this method.
• Second try: Using the following method:
  
  • A thin horizontal or vertical "slice" of the marker can be used as a detector deducted from the observation that a slice is made of 5 sections [black white black white black] with a 1:1:3:1:1 ratio.
  • Horizontal & Vertical ratio detectors were used to detect the above ratio in every [B W B W B] sequence in x & y directions.
  • Each time such ratio slice is detected, an indication is being placed at the center of the slice's original placement.
  • 2 indications from the horizontal & vertical detectors at the same place, are forming an intersection point, hopefully at the center of the marker.
  • False alarms: false detections from the horizontal OR from the vertical detectors don't harm much because they don't form an intersection point by their own.
  • False intersection points will be ignored while trying to conclude barcode(s) out of the marker indications (intersection points) - this process is described later on in this document.

• Finding a marker using the 1:1:3:1:1 ratio sequence is difficult due to noise and due to rotation - rotated marker has different ratios in different places when scanning in x & y directions
• In order to overcome the above problem, there's a need to have a adaptive ratio rule
• Adaptive ratio rule: If the previous frame had marker indications around (neighborhood) of the middle point of the sequence in question, a softer ratio depending on the number of indications is used, e.g.:
  0.33:0.33:1:0.33:0.33 < ratio < 1.84:1.84:3.53:1.84:1.84
• Where is the data in the previous frame? where is the neighborhood of the current middle point of the sequence, located in the previous frame?

• First frames are being searched for markers without a "softer" ratio rule.
• After 2 consecutive frames having detected markers, an estimation of the markers' place in frame(t+1) is being made by observing the placement of the markers in frame(t) and their estimated placement around their position from frame(t) in frame(t-1)
• The placement estimation is simply concluded by continuing their movement vector.
• Having a placement estimation for each marker, a map of movement is generated - each pixel in around the area of each marker, is being mapped to another pixel for frame(t+1)
• Now frame(t+1) "knows" where each pixel probably came from thus allowing to check the correct neighborhoods in frame(t)

• 3 Markers Form 1 Barcode
• Which 3 Markers? There are real intersection points (markers) and there are false alarms - All possible triangles from all combinations of 3 points out of the detection alarms, are being examined.
• The triangles are sorted according to one of their angles that is the closest angle to 90 degree. Triangles that don't have such an angle are dismissed
• A Right triangle test is performed on each triangle by checking the ratio of its sides - 1:1:2^0.5. This ratio is relieved if a triangle vertices existed near by in the last frame
• Also checking the following: While passing through the sorted triangles - a check that the triangle has 2 equal length sides is being performed and also checking that the triangle is not too close to already chosen triangle from the sorted list.

• For each valid triangle detected in the frame - the position, the area and the rotation of the barcode is being calculated by the angle of the hypotenuse and the position of the marker that is not a part of the hypotenuse.
• Next, the barcode is being aligned (rotated) in a way that brings the marker-less corner to the bottom right side. Also, the barcode is scaled to a uniform size (80 x 80 pixels)
• After getting the image of the barcode, the encoded content of the barcode is not really decoded. Instead, once a barcode is detected, its image is being saved and each barcode detected later on, will be correlated with the saved barcode's dct image.
• If the correlation of the two images passes a certain threshold, the barcode is labeled the same as the saved barcode and the current barcode replaces the saved one. If not, the current detected barcode is being labeled as a new barcode and saved.
• If the correlation result is near the threshold than a question mark will appear, indicating that the barcode can't be categorized for certain.

Labeled QR Code

• The first result shows how 2 barcodes are detected and tracked throughout the movie. Used parameters: B\W Threshold: 0.8, DCT Corr Factor: 0.74
• The second result shows how 1 barcode is being tracked in non-optimal conditions (Mainly due to skew and low resolution). Used parameters: B\W Threshold: 0.4, DCT Corr Factor: 0.70
• The barcodes that appear in the right area of the screen, are the barcodes from the movie after rotation and scaling.

• Main Screen
• Settings Screen

• Contact me for source files