符号化をどうするかの問題ですが､一例として｡
ｷｬﾝﾊﾞｽを横4縦2固定､ﾀｲﾙの色を2bit(白､黒､青､赤)固定とすると
■■■■
□■■□
は､0101010100111100 の16bitで表現できます｡

とりあえず､一例として､一般的な画像形式で保存してみた画像のｻｲｽﾞを記載してみます｡
そういうことを聞いているんじゃないとも思いますが｡



見えにくいので拡大してみます｡(なんかぼやけちゃいましたが元は4×2の画像のはず)


さて､この画像を色んな形式で実際に保存してみました｡
16色ﾋﾞｯﾄﾏｯﾌﾟ：126 ﾊﾞｲﾄ
256色ﾋﾞｯﾄﾏｯﾌﾟ：1,086 ﾊﾞｲﾄ
24ﾋﾞｯﾄﾋﾞｯﾄﾏｯﾌﾟ：78 ﾊﾞｲﾄ
png：129 ﾊﾞｲﾄ
jpeg：709 ﾊﾞｲﾄ

大体そんな感じですが､jpgにしたら何故か色がくすんだり､元のﾃﾞｰﾀによって形式変換後のﾃﾞｰﾀｻｲｽﾞが変わったりと安定はしてません｡
一番小さいのが24ﾋﾞｯﾄのﾋﾞｯﾄﾏｯﾌﾟ(78ﾊﾞｲﾄ)ですが､他にも画像形式は沢山あるので､これが最低ではないということは明らかでしょう｡
容量制限のきつかった時代のﾌｧﾐｺﾝの画像形式などは面白いので一読の価値ありです｡
http://hackgames.geo.jp/Memo/NesGazou.html
http://postd.cc/nes-graphics-part-1/

さて､一般的な画像ﾌｧｲﾙ形式は汎用性が大切なので､ある程度あらゆる画像に対応する必要があります｡
https://ja.wikipedia.org/wiki/Windows_bitmap
などを読めば､わかります｡
先頭にBM (0x42, 0x4d)という2byteのﾃﾞｰﾀがあり､ちゃんとBMP形式であるかのﾁｪｯｸなどに使われるわけです｡ここが違ってるとそもそも破損ﾌｧｲﾙとして扱うとか｡
次に4byteのﾌｧｲﾙｻｲｽﾞを格納してる領域があります｡
他にも､ﾋﾞｯﾄﾏｯﾌﾟでも何色のﾋﾞｯﾄﾏｯﾌﾟであるか､などなど｡
今後の拡張のためやらｷﾘをよくするために予約領域なんていうのもあったりします｡
そして､ぶっちゃけこれらの情報､全部いるか？ ってなるといらないものも多いし､無駄に大きな格納領域を使っちゃっているところも多い(かも)｡(容量削減を追及するにあたっては)

つまるところは､事前の決め事はなに？ っていうのがはっきりしないと､最低って何なのか明らかになってきません｡
例えば､使う色の種類が､(黒､白､赤､＋α)の4種類だと2bitで表せますし､16色使うのであれば4bitかかりますが､
それでもやり方が色々あって､
･使う色の一覧を外部に用意してそこから参照する場合
･使う色の一覧を画像ﾌｧｲﾙ自体に持っていてそこから参照する方法
･ﾋﾞｯﾄの並び順のﾃﾞｰﾀ(各ﾋﾟｸｾﾙ)に色情報を直接持つ方法(RGBなどで)
とかですかね｡詳しくないんですけれど(突っ込み待ち)



要は､既存の(一般的な)ﾌｧｲﾙ形式でだと､最低なんﾋﾞｯﾄの画像ﾌｧｲﾙがあるかの答えはあるのでしょうけれど､一般的でないﾌｧｲﾙ形式も含めると答えは見つけるのが困難｡
なら､自分でﾌｧｲﾙ形式を作るとなると､どこまでが決め事なのか？ で答えが変わってくるはずです｡
例えば､例に上がった画像の幅､高さを内部に持つとしても､最大で8×8に対応するならば
高さに3bitの情報､幅に3bitの情報で6ﾋﾞｯﾄ追加になるわけですが(実際には3bitは扱いづらいので4bitずつ使うことも多かったりするとかしないとか)､
横の最大は4ﾏｽだったら､2bitで済みますし､縦の最大が2ﾏｽだったら1bitしか使いませんので､合わせて3bitで済む訳です｡

似顔絵が4ﾊﾟﾀｰﾝしかなくって､どの似顔絵の画像なのか？ を選ぶ方式だと､2bitで済んだりするわけですよね｡それが決め事が何なのか？ っていうことです｡

縦横のｻｲｽﾞ､使う色の種類の上限が決まってたら､その中で最適な(あるいは最適に近い､独自の)ﾌｧｲﾙ形式は考えられると思います｡
実際はそれﾌﾟﾗｽ､全体で扱う画像の量や種類も加味して考えるのでしょうけれど｡(例えば､全ての画像の幅が4ならば､画像ｻｲｽﾞは高さのﾃﾞｰﾀだけでよい､ｻｲｽﾞが固定ならば画像ｻｲｽﾞなんていらない､その他もろもろ)

長い割に多分いろいろ間違ってて､質問の意図も理解できてなくて自分でもなんだかなｰと思いますが､寂しいので回答してみました｡

なんのために知りたい情報なのか？ を追記するとわたしよりもまともでわかりやすい回答が得られると思います｡

以上

R 0000
1111

G 0000
1001

B 0000
1001
---------------
R(赤)G(緑)B(青)形式で分解すると上記のようになります｡
それぞれ､8bit(1ﾊﾞｲﾄ)なので､計 8x3=24bitで表すことは可能だと思います｡

■
＞4×2の情報がない

縦横情報を1ﾊﾞｲﾄx1ﾊﾞｲﾄで持つことにすると､

8bitx2 =16bit


■
ｻｲｽﾞ情報､色情報で､24bit+16bit =40bit (＝5ﾊﾞｲﾄ)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
■
情報であり限りは､暗黙の規定が必要なのは必要｡

文字だって､ｷｬﾗｸﾀｰｺｰﾄﾞが規定されてることを前提に､情報をﾋﾞｯﾄ化？できるわけで･･｡

また､文字(形)情報にしても､昔はﾋﾞｯﾄ情報だったものが､今はﾍﾞｸﾀｰ情報になってる｡