Discussion :

[thatslife]

bonjour,

j'ai une image représentant un texte. Elle est représenté sous forme d'une matrice de pixel binéarisé, c'est a dire que tous les caractères sont représenté par des pixels noirs et le fond de l'image est blanche.

Pour pouvoir faire un traitement de l'image il faut que je regarde si elle est "droite". Je dois donc détecter le meilleur angle de rotation si necessaire.

Et mon probleme est que je ne vois vraiment pas la méthode ou un algorithme efficace pour détecter cette angle. Si quelqu'un avait une piste que je pourrais suivre ...

Merci !

[NeMo_O]

Salut ! déjà je ne penses pas qu'il y ait un algo " exact " qui arrive a redresser l'image à 100 % mais il faudrait plutot passer par des approximations:

je n'ai pas d'idée super précise mais quand tu as du texte ( c'est généralement sur plusieurs lignes ) entre chaque ligne tu as des sortes de " bandes de pixels blancs "

à mon avis c'est justement ces lignes qu'il faudrait essayer de détecter et non le texte

ah tien en écrivant je pense à une idée qui pourrait être pas mal lol

j'essaye d'expliquer mon raisonnement en quelques étapes:

1) pour redresser ton image il suffit d'avoir l'orientation d'une seule ligne de texte ( donc à fortiori d'une seule " bande blanche " )

2) donc voilà mon idée : tu scannes pixel par pixel ( assez long je pense mais bon lol ) et dès que tu rencontres un noir tu t'arretes

3) ensuite le but est de tracer une droite "fictive" dont je te laisse trouver l'équation lol et voir si cette droite est juste collée au dessus ( ou en dessous ) de ta ligne de texte . autrement dit voir si elle est parallèle

4) pour cela je pense qu'il n'y a pas d'autre moyen que d'essayer " toutes " les droites possible et de voir celle qui se rapproche le plus du texte sans le couper ( celle qui ne coupe donc aucun pixel de texte )

5) enfin en supposant que tu avais défini un repere tu n'as plus qu'a choper la pente de la droite et à faire un changement de repere




Voila donc l'idée mais je doutes qu'elle ne marche exactement comme je t'ai dit parce que j'ai déja quelques contre exemples lol

Mais bon à toi de l'adapter éventuellement

[NeMo_O]

me revoilà déjà lol


moi qui parlais ci dessus d'approximations je pense justement à une qui pourrait faire marcher à 99% l'algo :p

le contre exemple que j'avais trouvé était :

par exemple ton texte est : " m m m m m "
ben si le programme trace une droite verticale entre deux m et collée à un m il risque de penser que c'est lorientation

j'ai donc pensé à créer une seconde image basée sur la première mais dès que tu rencontres un pixel tu met les pixel adjacents en noir aussi . cela grossirait le texte et il y aurait moins d'espace entre les lettres, donc moins de droites " faussement valables "

enfin bon c'est qu'une idée j'ai pas réfléchit 10ans la dessus lol

[thatslife]

Merci beaucoup déjà de t'etre penché sur ce probleme si rapidement.

Pour ton algo y'a deux trois petites explications que j'aurai besoin :

la droite que tu penses tracer elle est verticale ou horizontale car dans ton deuxieme post tu parles d'une droite verticale ?

Ensuite le probleme est que si l'image est trop incliné il n'y a pas de "bandes blanches" car sur chaque ligne il y aura des pixels, ceux memes inclinés vers la droite ou la gauche.

En y réfléchissant il y a pas mal de contres exemples ou de cas particuliers qui va etre délicat de gérer exhaustivement.

En tout cas merci beaucoup je continue a y réfléchir.

[NeMo_O]

arf c'est bien ce que je pensais je suis pas très clair dans mes explications lol mais un problème graphique par écrit c'est pas super évident lol ( demain ou après je te ferais une image représentant mon idée parce que la j'ai de la mécanique quantique a faire saleté :s lol )


mais c'est un problème intéressant et pas courant je vais en parler à un pote on va essayer de trouver un algo possible


PS : comment tu fais pour " scanner " les pixels d'une image lol ? c'est faisable en C ça lol ?

[souviron34]

bonjour,

j'ai une image représentant un texte. Elle est représenté sous forme d'une matrice de pixel binéarisé, c'est a dire que tous les caractères sont représenté par des pixels noirs et le fond de l'image est blanche.

Pour pouvoir faire un traitement de l'image il faut que je regarde si elle est "droite". Je dois donc détecter le meilleur angle de rotation si necessaire.

Et mon probleme est que je ne vois vraiment pas la méthode ou un algorithme efficace pour détecter cette angle. Si quelqu'un avait une piste que je pourrais suivre ...

Merci !

Sais-tu si le texte est à peu près centré ?

Moi je verrais bien un algo du style un peu "lancer de rayon" :

tu prends 1 point (par exemple le centre) et tu fais passer des droites à angle de plus en plus grand d'un bord à l'autre (à gauche et à droite), et tu parcources cette ligne en comptant les pixels noirs. Celle qui en aura le plus risque fort d'être l'orientation Tu fais par exemple par dichotomie :

-45 degrés
+45
0

et par exemple
0
+45
+22.5

etc..
etc..

Non ? C'est une idée...


[EDIT]
peut-être aussi soit faire de -90 à +90, soit une fois complété entre +45 et -45, faire entre -45 et + 45...
[/EDIT]

[NeMo_O]

oui je pensais à ça aussi mais c'est peu probable de fonctionner je m'explique:

si sur l'image il y a peu de mots par lignes et beaucoup de lignes:

un
deux
trois
quatre
...
n

alors ton algo va trouver une droite verticale


mais juste une petite précision thatslife , le texte sera quelconque sur l'image ou il aura toujours une certaine apparence ? ( par exemple les lignes seront-elles toujours remplies et il n'y aura jamais de passage à la ligne ? ou alors tout peut arriver ? )

[souviron34]

sinon le problème est similaire à ce qui est tenté d'être fait dans les OCR..

Cherche là-dedans il y aura sans doute un certain nombre de solutions...

[thatslife]

mais juste une petite précision thatslife , le texte sera quelconque sur l'image ou il aura toujours une certaine apparence ? ( par exemple les lignes seront-elles toujours remplies et il n'y aura jamais de passage à la ligne ? ou alors tout peut arriver ? )

Tout peut arriver ! Le texte n'est pas forcément unis, il peut y avoir des passages a la ligne, des lignes peu rempli...cependant je ne vais pas traiter les cas extremes : une page d'un mot uniquement, ou alors un très grand nombres de lignes composé d'un mot etc...

Pour l'instant j'essaye d'isoler une ligne et avec les pixels du bord gauche haut et droit et bord droit haut et bas j'essaye de déterminer un angle. Cependant il y a pas mal de police ou quand une phrase commence par une majuscule et bien ca peut etre ennuyant etc...


La méthode que tu propose souviron34 me parait également judicieuseuse mais un peu plus délicat à mettre en place et connaitrais tu des docs d'OCR où ils parlent des problemes de rotations ???

Merci beaucoup en tout cas à tous les deux !

[souviron34]

La méthode que tu propose souviron34 me parait également judicieuseuse mais un peu plus délicat à mettre en place et connaitrais tu des docs d'OCR où ils parlent des problemes de rotations ???

est ton ami

[thatslife]

Je suis tout a fait d'accord et désolé d'etre un peu lourd mais encore il faut savoir trouver ce que l'on recherche...

Parce qu'entre les logiciels completements commerciaux et toutes les methodes de rotations grace aux logiciels de retouche d'image je suis bien loin de mon probleme de programmation...

[souviron34]

je ne sais pas.. C'est un domaine des plus vastes...

Par contre j'ai eu une autre idée pour ton problème :

Si tu cherches d'abord par exemple un point noir . Puis tu étends en "suivant" et stockant les points noirs accolés et tu t'arrêtes dès que tu touches du blanc...
Tu répètes ça pour tous les pixels noirs non encore accolés..

En fait un truc itératif où tu stockes séparément tous les groupes de pixels noirs (les coordonnées).

Normalement (en dehors du bruit) tu devrait avoir isolé toutes les lettres.

Maintenant, tu devrait arriver à trouver une direction moyenne par "lettre", en prenant un angle de la lettre (une extrémité du groupe de pixels) et en suivant les pixels jusqu'à ce que ça change de direction ou que ça fourche. (style algo de bresenham)

Là tu fais un histogramme de ces directions, en mettant un "bin" par exemple tous les degrés..

Et tu prend les deux "bins" (ou les 2 pics) les plus forts : ça devrait te donner la direction et sa perpendiculaire....

Non ?? suis-je complètement dans les choux ??

[thatslife]

me revoila avec du nouveau !

Alors j'ai reussi a traiter mon probleme sur des cas simplifies, mais bon pour l'instant ca me convient tres bien avec une approximation relativement bonne de l'ordre du dixieme de degre donc go ahead

Je posterai ma solution tres bientot des que j'aurai fini toute ma partie.

Merci beaucoup a toutes les personnes qui m'ont aidees a resoudre ce probleme.

[NeMo_O]

ah oui pas bête moi en tout cas je trouves ton idée pas mal souviron

ptetre un peu compliquée à mettre en place mais je pense que ca devrait marcher dans tous les cas ^^

enfin le problème est résolu donc plus de soucis lol

[__moi]

Salut,
j'ai a peu pres le meme problem , je pense a cet algorithme:

1)parcours vertical de l'image pour trouver 2 points (qui sont horizontalement les plus bas de l'image;le premiers pixel noir et le dernier
2)puis je trace la droite entre le 2
3) je genere pls droite afin de trouver la solution desirable

que pensez vous??

[gronaze]

J'ai déjà eut le même problème pour des datamatrix, et la solution est de faire des histogrammes cumulés en x, en y et à 45°, puis de diviser l'angle en deux et ainsi de suite jusqu'à obtenir un maximum de l'histogramme.
EDIT: Il n'est pas forcement intéressant de travailler sur l'image complètes, seuls les bords suffisent, à toi de trouver la bonne largueur de bord.