Skip to content

Home

Jump to bottom
wzli edited this page Apr 18, 2020 · 18 revisions

Code Map Localization is an indoor 2D localization system that decodes floor printed binary patterns to achieve robust and accurate global positioning. The algorithm is designed to run in real-time under tight resource constraints (IE embedded micro-controllers), and works with image sensors as low as 20x20 pixels in resolution.

Currently supports:

  • USB cameras
  • ESP32 camera
  • PC simulation
  • ROS2 interface
  • Python binding

Use cases

Although many applications exist, the primary objective is to provide a reliable and extremely low-cost localization system for large fleets of autonomous indoor ground vehicles, as other existing systems usually become prohibitively expensive as the coverage area and fleet size scales up.

Case Examples:

  • For research purposes, it is often required to collect real-time “ground truth” localization data for mobile robots to evaluate various control and estimation algorithms.
  • For industrial purposes, autonomous warehouse robots often require accurate real-time localization data in order to maneuver in tight spaces and arrive at exact locations for loading/unloading/docking.
  • For hobbyist purposes, small robotics demos often require a localization system that is robust and portable with minimal setup (the floor pattern can be printed on a portable surface).

Compared to other methods

See Comparing Indoor Localization Systems, in brief:

Advantages:

  • Millimeter accurate global positioning everywhere. It is literally “ground truth”.
  • High update frequency, limited only by image sensor framerate.
  • Scales to any number of trackers without penalty.
  • Ultra-low cost.
    • Each module requires as much hardware as an optical mouse, which is a few dollars at scale.
      • The current development prototype cost less than $10 each.
    • Graphic flooring might be an investment depending on material. For reference, custom printed vinyl flooring stickers are about $5 per square meter at scale.
      • For demo purposes even a large format poster would suffice.
  • Can use and share existing imaging systems without requiring dedicated hardware. (Any floor pointing camera)

Drawbacks:

  • 2D only.
  • Requires floor printed positioning pattern.
  • Loses localization during high-speed motion.
    • Mostly dependent on camera configuration, image may be too smeared to decode at some movement threshold, especially for rolling shutter.
    • Visual odometry requires some overlap between successive frames, which decreases with movement speed.

How it works

see implementation details

Frequently Asked Questions

How large of an area can the system cover?

Coverage area depends on block size of the code used, which is configurable according to camera sensor quality and image processing resources. For reference, currently a block of 20x20 bits (containing up to ~20% random bit errors) can decode about 50,000 positions per axis, which translates to 50m by 50m if every bit is printed at 1mm (IE millimeter accuracy)

What makes this better than similar systems/algorithms that already exist?

  1. It is free and open-source.
  2. It is a complete localization system that works out of the box.
  3. It is designed for practical application, to run in real-time on common low cost hardware with meager resources.
  4. The core algorithm is portable to different systems, currently supporting simulation, usb camera, and embedded platforms.
  5. The binary code sequence embeds both position and direction data, which allows global heading/orientation to be decoded along with x and y position coordinates.

How is this different from putting QR codes on the floor?

  1. Each QR code occupies a distinct non-overlapping area. Code Map is a continuous positioning pattern where every sliding window block of bits decode to a unique position. This allows for much higher resolution in position.
  2. QR codes have dedicated locator patterns in the corners to distinguish itself within an image. Code Map assumes the majority of the image is the code and only ignores sections that fail to decode.
  3. Code Map was designed to be decoded many times per second (IE 50Hz) on a micro-controller. Hence the image processing pipeline is optimized to extract codes with very low image resolution requirements.
  4. QR codes use Reed-Solomon for error correction, Code map uses XOR binary matrix factorization (which is much more lightweight but is specific to extracting 1D vectors from 2D blocks).

How far does the camera have to be from the floor pattern?

It depends on how large the floor pattern is printed and the lens configuration of the image sensor. Ideally the length of 1 bit in the floor pattern should be projected onto 1.5 to 3 pixels on the sensor. For a crude reference, if the pattern is printed at 1mm resolution, the camera distance should be between 10cm - 20cm for a typical 60 degree FOV webcam.

Does the camera have to point perpendicular to the floor?

The short answer is YES. This is a choice by design because estimating and undoing image perspective distortions every frame in software requires higher computation and image resolution, which is not worth the trade-off considering micro-controller resources and the primary use case of fixed mounting a floor pointed camera for 2D navigation. However, usually there is some leeway virtue of bit error correction mechanisms and code redundancy across the frame. See Perspective and Homography for details.

Clone this wiki locally