Difficulty in resolving spatially overlapping barcodes is a major bottleneck for imaging-based spatial genomics methods. Here, we present an approach for untangling overlapping barcodes by using strong encoding and global optimization to reduce spurious solutions resulting from recombinations of barcodes. We demonstrate experimentally that cellular regions with average local densities of 127 barcodes per μm2 can be decoded with an estimated FDR of less than 4%, enabling a new type of super-resolution microscopy by coding.