Absolutely. It just needs to be large enough for the capture device to be able to discern between the codes various shapes.
That means though, that at the average distance of a billboard to the viewer, the code may actually need to be the size of the actual billboard.
Edit:
Also, it may prove impractical in some areas, as some places have bylaws against mobile phone use while driving, which is when the majority of billboards are viewed.